Pixelation
General => General Discussion => Topic started by: happymonster on March 27, 2010, 06:11:48 pm
-
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:
(http://www.retroidea.com/Fixed256/palette.png)
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 (http://www.retroidea.com/Fixed256/output6_24.png)
Fixed palette (222 colours): http://www.retroidea.com/Fixed256/output6.png (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 (http://www.retroidea.com/Fixed256/output4_24.png)
Fixed palette (128 colours): http://www.retroidea.com/Fixed256/output4.png (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 (http://www.retroidea.com/Fixed256/output2_24.png)
Fixed palette (245 colours): http://www.retroidea.com/Fixed256/output2.png (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 (http://www.retroidea.com/Fixed256/output1_24.png)
Fixed palette (157 colours): http://www.retroidea.com/Fixed256/output1.png (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
-
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
-
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
(http://ptoing.net/post/ditherpass.png)
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)
-
I spent some time reading about ordered dithering on Wikipedia http://en.wikipedia.org/wiki/Ordered_dithering (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.
-
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).
-
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
-
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).
-
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 (http://www.retroidea.com/Fixed256/output8.png)
:)
(If only we had another range of de-saturated colours.. sigh!)
-
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! ;)
-
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.
-
I thought that people might be interested in seeing what you can do with dithering with hues and saturated colours rather than just with different shades. That is not used that much as far as I can see.
Secondly, I think the results are pretty good for a fixed palette, and perhaps naively I thought that artists might be best placed to see that. This is at least in comparison to other fixed palette I've seen. I admit this alone has little practical use now, but I can't help but wonder if it would have been useful when games were restriced to only 256 colours.
Finally, if people can have an in-depth conversation about the technicalities about AA or sel-out, then I would hope to have interest in areas such as this too. :P
-
I was very impressed with the downsampling of the Diablo image, true and I did zoom in and pay attention to the technique, for one.
I expect pixel artists to be more interested in techniques and effects they can manually produce though. So if from this as a starting point you develop some manual dithering technique which saturation-slides instead of hue-slides to achieve some effect that is new, I'm sure people will jump on that much more.
-
That's also true. I'm not sure how well the latest versions of promotion or photoshop handle colour spaces but if there is no easy way to alter the hue without the luminance also being affected then at least people could pick colours from the palette image I posted, or maybe an expanded image. Then at least they will be able to mix colours with less visible patterning in the dithering (albeit with all monitors and peoples eyesights being different)
I suppose the stumbling block here is that with few colours you want to have a full range of shades, where as this technique lends itself more to groups of identical shades of different hues.
-
That's also true. I'm not sure how well the latest versions of promotion or photoshop handle colour spaces but if there is no easy way to alter the hue without the luminance also being affected
no, although
LCH color space (http://en.wikipedia.org/wiki/LCH_color_space#CIE_L.2AC.2Ah) is capable of altering hue with relatively minor shifts in perceived intensity (much much much lower than HSV, or even HSL)
(that page makes it look a bit more complex than it is. LCH is simply a transform of the LAB colorspace into polar coordinates.)
LAB has the same properties, except you cannot alter hue directly.
Photoshop seems to use LAB for it's Color mode.
then at least people could pick colours from the palette image I posted, or maybe an expanded image. Then at least they will be able to mix colours with less visible patterning in the dithering (albeit with all monitors and peoples eyesights being different)
I suppose the stumbling block here is that with few colours you want to have a full range of shades, where as this technique lends itself more to groups of identical shades of different hues.
Yes. I've generated an 'optimal' 256-color LCH palette, which matches more the general trend in good pixel art of having every color in the palette be a unique brightness. I've tried arranging it, I think that it's nearly impossible to make a really good palette that does not possess the aforementioned property; I could only arrange it into ramps, but not into exactly-aligned ramps of the same length.
(http://img.photobucket.com/albums/v449/neota/edits/palette-1.png)
-
Now I'm just being silly! Diablo III in 32 colours (amiga style) :P
http://www.retroidea.com/Fixed256/output9.png (http://www.retroidea.com/Fixed256/output9.png)
-
I'd love to see you do one of these with Arne's palette. Just for giggles :)
-
Wouldn't work I'm afraid.. Arne's palette has a full range of shades so that a red say won't have the same luminance as any other hue. This works for 16 colours as a larger range of shades is more important than mixing colours really.
-
I just realised I was making a silly error with the de-saturated colours. Now fixed and the subtleness of colours blending into grey is captured much better. This goes some way to avoid having a separate set of desaturated hues and shades. Also made the overall saturation more faithful:
http://www.retroidea.com/Fixed256/output11.png (http://www.retroidea.com/Fixed256/output11.png)
Also, I managed to squeeze in a few more shades to the 32 colour version, which improves the detail a little. Also improved the hues a little and added the revised de-saturation code:
http://www.retroidea.com/Fixed256/output10.png (http://www.retroidea.com/Fixed256/output10.png)