When converting a pixel to a lower bit depth, some resolution is lost. If we are converting an area of pixels of (approximately) the same colour, we can give a better idea of the original colour by means of dithering.
Dithering means displaying neighbouring pixels in different colours in such a way that the average colour of these pixels is the colour we want. Suppose we want to give the visual effect of a grey area using only black `*' and white ` ' pixels. We could dither the pixels like this:
******************************** * * * * * * * * * * * * * * *
************* * * * * * * * * * * * * * * * * *
******************************** * * * * * * * * * * * * * * *
************* * * * * * * * * * * * * * * * * *
******************************** * * * * * * * * * * * * * * *
************* * * * * * * * * * * * * * * * * *
******************************** * * * * * * * * * * * * * * *
************* * * * * * * * * * * * * * * * * *
******************************** * * * * * * * * * * * * * * *
************* * * * * * * * * * * * * * * * * *
1 | 0.75 | 0.5 | 0.25 | 0
Note that the numbers at the bottom indicate the grey level, with 1 being
black and 0 being white. When viewed from a proper distance, it appears as if
there is indeed a gradient of greyscales. The dithering is done by filling
each area with a specific greyscale with tiles of 2x2 pixels, with the tile
pattern chosen according to the colour that the area should have:
+--+ +--+ +--+
|**| | *| | *|
|* | |* | | |
+--+ +--+ +--+
dark (75% black) medium (50% black) light (25% black)
Note that the grey level corresponds precisely to the relative amount of black
pixels in the tile pattern. Other tiles with the same number of black pixels
could be used instead of these. We may say that at some positions within the
tile, the colour we are trying to display is rounded down, and at other
positions, it is rounded up. We may assign a rounding bias to each pixel in
the tile:
0.25 0.75 0.50 0.00We may dither any picture by dividing it into tiles, and then rounding each pixel value up or down according to the rounding bias at that position. More precisely, the rounding bias is added to the pixel value, and then, it is rounded down. For example, consider the following picture:
0.00 0.00 0.25 0.25 0.50 0.75 0.75 0.75 ..--+ooo . = 0
0.00 0.25 0.50 0.75 0.75 0.75 1.00 1.00 .-+oooOO - = 0.25
0.50 0.50 0.75 0.75 0.75 0.75 0.75 0.75 ++oooooo + = 0.50
0.25 0.50 1.00 1.00 1.00 0.75 0.50 0.50 -+OOOo++ o = 0.75
O = 1.00
data appearance
we first add the rounding biases to each pixel according to its position:
+-----------+-----------+-----------+-----------+ | 0.25 0.75 | 0.50 1.00 | 0.75 1.50 | 1.00 1.50 | | 0.50 0.25 | 1.00 0.75 | 1.25 0.75 | 1.50 1.00 | +-----------+-----------+-----------+-----------+ | 0.75 1.25 | 1.00 1.50 | 1.00 1.50 | 1.00 1.50 | | 0.75 0.50 | 1.50 1.00 | 1.50 0.75 | 1.00 0.50 | +-----------+-----------+-----------+-----------+Now, we round it down:
0 0 0 1 0 1 1 1 ...*.*** 0 0 1 0 1 0 1 1 ..*.*.** 0 1 1 1 1 1 1 1 .******* 0 0 1 1 1 0 1 0 ..***.*.This algorithm may be generalised to colour dithering by rounding red, green, and blue individually, using the same round bias. Here's the code for converting 24-bit (8 bits red, 8 bits green, 8 bits blue) to 7-bit (2 bits red, 3 bits green, 2 bits blue).
long convert_888_to_232(long srcpix, int round_bias) {
return( (((( (( (srcpix>>16)&0xff)*0xc0)>>8)+ round_bias ) &0xc0) >>1)
| (((( (( (srcpix>>8 )&0xff)*0xe0)>>8)+(round_bias>>1)) &0xe0) >>3)
| (((( (( srcpix &0xff)*0xc0)>>8)+ round_bias ) &0xc0) >>6)
);
}
srcpix is a 24-bit truecolour pixel value (rrrrrrrrggggggggbbbbbbbb).
round_bias is the bias to use for this pixel. The return value is a 7-bit
truecolour pixel value (rrgggbb). The round_bias may be determined in a
variety of ways. XDPaint uses 8x8 tiles, with a rather arbitrary choice of
round bias for each pixel (this should be improved!):
convert_888_to_232(srcpix, ( ( (x&7)+((y&7)<<3))) * 0x25) & 0x3f );Here's how this works out: