Full Dithering: 24bit->256 colour dithering in the HSV colour space

[happymonster]

I've seen a few threads on dithering lately and I've done some work in the past on this aspect of drawing, both with hand drawn art and using programming to see what works best. The work I've done is rather experimental but I think it might be of interest to some people here, as well as being useful in your own artwork.

A year or so ago I wanted to see how to get the best results via programming to colour reduce a 24bit truecolour image to a fixed palette 256 colour picture.
I deliberately chose a fixed palette as adaptive palette reduction in paint programs is already very good, but fixed colour palettes I've seen are normally pretty poor. They are often variations on a 332 bit RGB colourspace which covers most of the palette range but is pretty poor in every other way (only 8 shades for a start).

As artists will know, HSV colourspace is closer to how we actually see and is also a better way of approaching dithering (and probably computer art in general).

I proceeded along the following assumptions:

+ Our eyes are most sensitive to detecting differences in luminance (this can be seen in black and white photography and how easy it is to tell shades apart)
+ Our eyes are less sensitive in detecting difference in hue (one example of this is that JPEG's reduce the hue channel data without the average person noticing, another is putting say a blue and a green next to each other of the same brightness in noticing the edges)
+ Our eyes are least sensitive in detecting differences in saturation (this can be seen by the difficulties in seeing differences between a grey and a desaturated version of the same brightness when next to each other)

There is nothing new about dithering in hue and saturation dimensions of course. On the Amiga the Bitmap Brothers often differed various shades of two hues together to make a third hue in their games. However I think there is more potential when using a limited palette for this kind of dithering that is often used, as luminance dithering is easier to do and much more common and well known.

So we now have the order of importance for selecting colours for each HSV dimension in the fixed palette. Because we are least sensitive to saturation we will have one range of grey shades and then fully saturated shades of the hues. This effectively only gives us a one bit scale for saturation and even another range of half-saturated colours would be very useful when dithering, but would take up too many colours in our 256 colour fixed palette to be done.

We now add 8 hues (I also tried 7 with an increased number of shades per hue, but 8 provides a bit more hue coverage). The 8 hues are pretty close to the colours of a rainbow, but each hue's luminance value is adjusted so it is the same brightness to all other hues for that shade. What I mean by that is that a yellow is not blended with a full red, but more of a pink colour (as pure red can't reach the brightness of a full yellow). By doing this we can now dither across the hue dimension without also dithering across the luminance dimension (which is what makes the dithering so noticable when the two colours are quite different in brightness)

So with 8 different hues and 1 grey scale 'hue' we can have 28 shades x 9 hues for 252 palette entries. We use the final 4 entries for a pure black and white and a very dark grey and slightly dim white, to make a total shading range of 32 for each colour:



Now we need a dither pattern to blend between the hues, saturation and luminance dimensions so I used a 64 shade 8 x 8 ordered dither pattern.

I tested the program I made with a variety of images and you can find a selection of some of these (original and colour reduced version) below. With only 256 colours you are always trying to find the best balance between gaps in hue coverage, saturation coverage and shading, especially in a fixed colour palette. The results tend to be higher in dithering across the images compared to other fixed colour palettes, but the dithering is much less noticable overall. In fact even when magnified the images work better overall, and the dithering is less noticable than with other methods when seen at distance.


Landscape test photo
(low detail clouds with testing of grey clouds against bright blue sky, high texture detail in rocks, grass and building with varying hues from orange to green)

Original: http://www.retroidea.com/Fixed256/output6_24.png
Fixed palette (222 colours): http://www.retroidea.com/Fixed256/output6.png


Human test photo
(Fashion style picture of Keira Knightly, showing low contrast and detail areas such as skin areas and background as well as other areas of high detail and contrast such as facial features, and hair)

Original: http://www.retroidea.com/Fixed256/output4_24.png
Fixed palette (128 colours): http://www.retroidea.com/Fixed256/output4.png


Computer art pixel painting
(Old truecolour demo picture to test against this more artifical image)

Original: http://www.retroidea.com/Fixed256/output2_24.png
Fixed palette (245 colours): http://www.retroidea.com/Fixed256/output2.png


Photo scene
(Difficult test of saturation blending with subtle hues and a range of details and contrast)

Original: http://www.retroidea.com/Fixed256/output1_24.png
Fixed palette (157 colours): http://www.retroidea.com/Fixed256/output1.png


These images aren't perfect and there are errors in hue, saturation and some obvious dithering areas. But I hope it shows the potential of dithering in Hues and Saturation and creating the illusion of more colours.

I hope it helps!
Richard

[Tourist]

Thanks for the post, this is interesting.  The results are good.

to blend ... I used a 64 shade 8 x 8 ordered dither pattern.

Could you elaborate on this?  I look at the results and I don't understand what this is.  There are many areas that have 3 or 4 colors interwoven rather than a simple dithered pattern.  I can't visualize the conversion.

Is this different than a direct color conversion with error propagation to adjacent pixels?

Thanks again,
Tourist

[ptoing]

My guess is that there are 64 possible patterns of dither (which is the max for 8x8 ordered) but each 8x8 block gets converted in passes or something, so you get blocks of different densities and colour drawn on top of each other.

Here I made an example with 3 colours and a 4x4 matrix which has 16 (well 15) possible ditherpatterns and a singlecolour block


I think my image holds all the possible dither overlays if there are only 3 passes, where the little colour tripple always shows which was the order.
The first is black background, then white dither and then red dither over the top.

I reckon this is what happymonsters tool does. It checks the colour and whatnot of each 8x8 block, which then gets quantised into an appropriate dither pattern which is done in passes with any of the given colour and perhaps it even does more passes than colours used, like you could go red over white over black over white or something to get even more variants (guessing here)

[Tourist]

I spent some time reading about ordered dithering on Wikipedia http://en.wikipedia.org/wiki/Ordered_dithering and some Google links and that helped quite a bit.  It's difficult to find information on color dithering but I guess one can dither in each of the HSV components separately and get the proper results.

So the algorithm for an 8x8 ordered dither would look like:
1) Take source pixels an 8x8 block at a time (mod the x and y positions)
2) Take source pixel brightness/lightness scaled to a 0-64 range to match the dither matrix.
3) Add value from the dither matrix (based on the position in the 8x8 block)
4) Compare this to a threshold (65)
5) Scale the source pixel brightness to the 0-31 range for the palette and add one if the threshold was exceeded in step 4.  Or do you just divide the total in step (4) by 4 to scale it down to a 0-31 range?

Then do similar effort with the saturation, except there are only two results, gray and not gray.
If gray, use the gray scale hue, otherwise to the same sort of routine with the hues to get the best color.

Or did you use multiple passes like Ptoing's  image?

Dumb questions:
This works fine for color reduction, but I don't see how to use it effectively when creating an image from scratch.  How can this be adapted to creating pixel art?

If the lightness only scales from 0-32, why not use a smaller matrix than 8x8?  A 6x6 seems to be a closer fit.

Several links suggested that error diffusion is superior to ordered dithering.  Do you have an opinion one way or the other?  I can't tell if either is better for pixel art, mostly because I can't see how to apply them outside of color reduction.

Thanks,
Tourist

Edit: I also ran across the idea that dithering is the method of sacrificing space to define additional colors, while anti-aliasing is is the method of sacrificing colors to define additional space.  I thought it was a neat idea, if not exactly relevant to the thread.

[happymonster]

The program only works at one pixel at a time, but it then looks at all three HSV dimensions for that pixel.

First it will work out the difference in the true colour hue and the closest one in the palette. Based on that value it converts the difference to one of the 64 dither patterns and alters the hue for that pixel if this matches a lit pixel in the 8 x 8 dither pattern.

Then saturation is checked and the dither pattern is again checked (but this time with the pattern vertically flipped), this is try to reduce the same pixels being hit for all 3 passes. Note that this pass can turn a previously modified hue pixel into greyscale. But actually precision of hue recognisation decreases with de-saturation anyway.

Finally the brightness / luminance is calculated and the pixel is brightened by one scale if the appropriate dither pattern pixel is lit (the patten is flipped horizontally in this pass).

The interleaving patterns you describe are where the 3 passes combine to create the final colour image. With more complicated area of high contrast some of this information is lost, but as with JPEG and other compression techniques errors in high contrast / detail areas aren't so noticable.

In terms of pixel art, colours could be chosen from a palette similar to the one I use here to ensure that dithered blending work with across hues. Also you could do the same with an appropriate grey value or two rather than using a few more de-saturated shades (thus saving palette entries).

[Tourist]

Flipping the matrix around for each check is a great idea.

The breakdown of HSV to prioritize luminance first, then hue, then saturation works very well.

Tourist

[happymonster]

Cheers!

One quick example I forgot to mention:

16 colours, black and 5 shades of red, 5 shades of blue and 5 shades of grey (all of the same shade). Now not only do you have these colours, but you can mix red with blue to make purple / violet and use the greys to show a range from saturated to de-saturated for those colours. You could also replace the greys with another hue.

Hues closer together on the colour wheel blend better though, so red-green-blue might look a bit obvious I suppose.

One earlier question, I use 8 x 8 rather than 6 x 6 as in we are dealing in the saturation dimension we only have grey or a full colour, so we have potentially a 256 colour range (I suppose I could have looked at 16 x 16).

[happymonster]

Diablo III in 800 x 600 and 256 colours (as used in Diablo I and II I believe).
http://www.retroidea.com/Fixed256/output8.png


(If only we had another range of de-saturated colours.. sigh!)

[happymonster]

Hmm.. Well I had hoped for a little bit more interest in this approach from pixel artists here. However if not then I will see what other cool things I can come up with!

[Helm]

Well how much more interest in an automated filter did you expect? I'm not demeaning the hard work you put into it but still.