Floyd-Steinberg dithering experiments

I figured I might as well dump this here instead of on the dev mailing list.

A while ago I started work on implementing Floyd-Steinberg dithering in the OHR when importing backdrops/tilesets, which is an algorithm to reduce an image to a palette by dithering when there's no exact match to the desired colour in the master palette. It turns out that this isn't just a simple algorithm, rather there many (sometimes very sophisticated) variants which give worse or better results. I just grabbed some code off the internet of the most basic implementation possible and slotted it in, and compared to GIMP (which also provides Floyd-Steinberg) and the existing dumb-as-rocks approach.

Results: http://tmc.castleparadox.com/pics/FSdither/demo.html

This is only two test images (which I thought were going to be hard cases), but GIMP does surprisingly badly on them. Maybe it's not optimised for the case where the palette used is too far from optimal. In fact something has gone terribly wrong on the blue water and roofs of the Vikings tileset; that might be a bug. On the other hand, when converting images to the "web216" palette, which apparently is far better than the OHR's default for this sort of thing, the results are more like what I expected.

The biggest problem with the results are the waves in the water in the Vikings tileset; they're blurry. I'd like to try to port code from pngquant, which I suspect has the best palette reduction algorithm in existence, and tries to preserve edges. I think that getting the right colours is actually far less important than preserving edges, gradients, and colour differences. It's also possible that I provide lots of parameters that people can tweak to try to improve the results. The old method can also remain an option.

Optimising dithering is fun. But on the other hand, it's a far better use of time to switch the engine to a 24-bit bitdepth than to work on this.

That is pretty cool! Your implementation does look better that the one The Gimp uses.

I notice that it dithers the transparent color in the vikings tileset.



Probably true :)

Since you have already implemented this, maybe it is worth leaving in as an option when you import a backdrop/tileset? Although 24-but would be great, the dithering could be a really desirable stylistic choice for some games.

Making this an optional feature is a great idea IMO! I'd love to toy around with it!

---

"One can never improve enough nor should one stop trying to improve."

Yay, one more reason to move on up to 24bit! I actually do like dither stylistically. Though I choose to pre-dither my art in photoshop before importing, just because it allows me to choose different types of dither, and the colours I want to use.

While we're on the topic of dither, I should mention that I developed this neat little trick I do for my art sometimes. Essentially I draw pixel art, double it in size with a nearest neighbour algorithm, then dither the result. I can take this even further by reducing the image size to 50%, back up to double, and repeat. This results in plenty of weird dither patterns which is sometimes nice to looks at.

Here's a little example with some art I just recently made. I used my own choice of dither colours to get some unexpected results:

After doubling size, and pattern dither:


After reducing size, the re-enlarging:


After another dither with custom palette:


After a subsequent reduction, and re-enlargement:


...I like the shapes that start to form out of the dither algorithm. It's really nice for abstract art, this example isn't as nice since it had so much structure to begin with.

---

⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
⍠ C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases

I actually used this technique for my new blog header:

---

⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
⍠ C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases

Ooh, trippy!

---

"One can never improve enough nor should one stop trying to improve."

The suspect that the reason that the GIMP does worse on some cases but better on others (when using web216, mostly (which actually appears to contain 256 colours...)) is that it computes colour distance based on HSV or at least weighted RGB, whereas I'm still using simple unweighted RGB. I would like to try HSV actually.



Oh, that's already a solved problem. When you import it asks you to pick the background colour (you can press ESC to skip that step), and then it doesn't dither that. In that example I skipped that because I forgot that the background shouldn't be dithered.

However bleed between tiles is still a serious problem. I guess that could be special-cased as well, though.


What options does Photoshop have for dithering? Would it be possible to see what its results are for those two images (to the OHR palette)?

Goodness gracious, those dither patterns look like Rule 110!
That first, non-distorted, dithered image is a really nice effect. I think mixing resolutions in that way in games is an intriguing (and modern) style. I've also seen lots of interesting patterns emerging incidentally through my research topic, and would like to create some tools to generate them for artistic purposes.

Like it would iterate through the tileset tile-by-tile and dither them each one-by one?



I had to google that, and it is cool!

Yes. Also, pngquant uses a variety which tries not to bleed colour over edges (and to preserve edges), which might be sufficient.

However pngquant is going to need some significant patching in order to be useable; it's written to always compute the optimal palette itself, and there's all kinds of internal auxiliary palettes and data structures.

@TMC: I'm a little confused as of how to import the palette in to the dither option window in Photoshop. When I click load custom palette it asks me for a .act file, and I have no idea what that is. I suppose I could do the color selection 1 by 1 using the eyedrop tool but I don't have time tonight.

The index options in Photoshop are as follows:

-First you can select a premade palette, or make/import your own

-Then you have an option to "force" primary colours, black & white, web colours, or custom colours

-You then choose how many colours you want to "force" your image into

-You can check/uncheck transparency

-The dither options are: Diffusion, Pattern, and Noise

-For the diffusion dither you can select the % amount of diffusion and whether you want to preserve exact colours

If you want to try testing some stuff yourself, photoshop is free as a trial version via Adobe's site I believe... I actually got photoshop as a trial originally then followed some online instruction on how to manipulate it's code in order to make it think I purchased it, but I'm sure a 10-day trial or whatever should do the trick for you.

If you get photoshop, the index and subsequent dither menu is accessed by going: Image -> Mode -> Index Color...

You must have an image open to access this menu of course.

---

⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
⍠ C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases

'fraid I don't know how to import a palette in Photoshop. I didn't realise a trial was available, but I still don't with a Windows box (had a VM with XP, but it complained I'd changed the hardware too many times and revoked the key and locked down).

Error-diffusion is probably Floyd-Steinberg, or a more complicated algorithm. The more complicated versions aren't really noticeably different from F-S. GIMP also has pattern dithering. F-S is deterministic, but non-deterministic versions of it with added noise also exist, which is probably similar to PS's noise option. It's interesting that several colour weighting options exist.

Thinking more about it, it might be a better idea to try to create an error diffusion algorithm specific to pixel art, weighted to avoid highly noticeable dithering, rather than to reuse pngquant's approach.