Image Dithering — How to Deceive your Eyes?
An introduction to image dithering that turns fewer colors into more.
Dithering is a means to randomize the quantization error and is widely used in digital audio, video, and grayscale or colored images. For example, the human ear is sensitive to the audio with cyclical error, and we usually introduce “dithering” to convert error to random noise that ears are hard to notice. This article focuses on the application in image processing and shows you how image dithering deceives your visual system.
+ Dithering in the image domain
In image processing, there comes a problem when you render an image on display with a smaller color depth (also called color resolution). It sometimes exists a color banding effect.
Think about that you want to draw a target color with grayscale value = 90, but only three colors available in the palette, black (grayscale value = 0), gray (grayscale value = 128), and white (grayscale value = 255), where the color cannot mix. Under this circumstance, you can only choose gray since it is most visually similar to the target (in math way, 128-90 < 90-0). For any color not in the palette, you are forced to pick up the one, closest but not equal to the target, to simulate it. Therefore, different target colors may share the same color resulting in a color band. Here is an illustration of it.
We can see that the right-hand side shows an unsmooth gradient from black to white since there are many more subtle shades of gray (as shown on the left-hand side) that can only simulate by the closest color match from the palette (one of the nine base colors). To make the gradient smoother, or more formally, to simulate colors more similar to the desired colors and let them be looked natural from a distance is what image dithering does.
+ How dithering works?
But how image dithering makes sense to turn fewer colors into more? It utilizes that the human eyes tend to mix colors close to one another. Take a look at the following six patches.
Imagine each of six patches is exactly a pixel, and which one is the result that looks more likely to gray? The right bottom one. In this case, we take the same number of black and white colors to simulate gray since 50% black+50% white = gray. Extend this idea to adopt different ratios of the two base colors, and thus we can use black and white colors to achieve grayscale. The more (ideally, N×N) squares in one patch, the more (ideally, N×N+1) gray levels can be generated. Each level represents what percentage of (ideally, how many) squares fill with white. The more, the brighter. For example, 75% black mixing with 25% white will result the color with grayscale value = 64 (i.e., 256 × 25%).
There are several algorithms designed to perform image dithering and can be roughly divided into three categories, averaging dithering, ordered dithering, and error-diffusion dithering (we discuss 8-bit grayscale image for dithering).
+ Averaging dithering
It is exactly an image binarization process (like Otsu thresholding) that turns a grayscale into a binary image. Each pixel is compared to a fixed threshold that is averaged all over the pixel values and then undergoes quantization (greater than threshold becomes white, otherwise black).
This method is quite simple but in the loss of details and contouring since it utilizes the global information that may introduce numerous noise for thresholding. As you can see from the right-hand side result, the hair is mixed with the background, and the suit is all colored in black without any crease detail.
+ Ordered dithering
It divides an image into several patches with the size of m×n pixels. Each pixel in one patch no longer compares to a fixed threshold (as used in averaging dithering) but a corresponding value defined in the threshold map (or called matrix). Take the M2 map as an example. Supposedly we attempt to process the pixel located at the right-top of one patch. What ordering dithering does is checking whether the grayscale value of that pixel is greater than 128 (= 256×2/4). If so, the pixel is changed to white, otherwise black.
For an n×n map, it can generate (2^(n²)) - 1 different pattern using black and white colors. The bigger the map size is, the more patterns can be used. The threshold map whose dimensions are a power of two is also called the index matrix or Bayer matrix.
As you can see in the M4 map, the numbers [0, 15] are labeled in one of the four colors (red, green, blue, and orange). Each color includes four numbers that are sorted from left-top to right-bottom and then from right-top to left-bottom. With this characteristic, it greatly shows crosshatch patterns after applying the threshold map.
Here are the ordered dithering results. Although they adopt only black and white to simulate grayscale, the idea to turn several black/white individual colors into “patten” makes them meaningful to preserve the detail of the input image as more as possible. It is why ordering dithering does much better than averaging dithering. Also, the larger-size map allows more subtle to be kept in each patch, and thus the dithering result looks more similar to the input.
+ Error diffusion dithering
It finds the closest available color (i.e., quantization) for each pixel indicated with a star (*) and diffuses the scaled quantization error (i.e., the difference between the closest available color and the original color) to the four neighboring pixels.
Floyd-Steinberg (FS, for short) dithering, the commonly used error-diffusion dithering approach, scans the pixels from left to right and top to down and adopts the above coefficients in the diffusion process. Here is an example, and we quantize each pixel into 0 and 255 by the threshold value 128. Given the initial state as follows.
… 239 2513 15 129
In the first run, 239 is to be processed. Since 239>128, 239 becomes 255, and the quantization error 16 (=255–239) sequentially diffuses to neighboring pixels. The right pixel: 25+16×7/16=32, left-bottom: 13+16×3/16=16, below pixel: 15+16×5/16=20, and right-bottom: 129+16×1/16=130.
… 255 3216 20 130
In the second run, 32 is to be processed. Since 32<128, 32 becomes 0, and the error 32 (=32–0) is also spread to the neighbors. The left-bottom pixel: 20+32×3/16=26, and below pixel: 130+32×5/16=140.
… 255 016 26 140
After going through all the pixels, we will get
… 255 00 0 255
Let take a look at the FS dithering results.
The middle one reduces 256 (=2⁸) grayscale colors to only 8 base colors, but it shows few differences to the input image. However, when using only 2 base colors, the ordered dithering result preserves more background details than FS dithering (right-hand side result) does.
Interestingly, if we skip the error-diffusion process in FS dithering, we will get undesirable results (especially the case that uses 2 base colors). This greatly shows the importance of the error-diffusion design.
+ More try
Although averaging dithering, ordered dithering, and error-diffusion dithering are both have quantization processes, only the last one outputs more than two colors.
Say the former two categories have the same quantization rule as the error-diffusion dithering, what is about the results? For averaging dithering, we can refer to the results of FS dithering without error-diffusion; For ordered dithering, as illustrated follow, from left to right, the output image is made of 4, 16, and 64 quantized colors, respectively. Although more color is used, the results are even worse than those of the original version due to the low contrast. That is why they use only black and white colors in ordered dithering (can enhance the contrast for better performance).
+ Takeaway
- Image dithering compensates for lack of color resolution.
- Since the human eyes tend to do spatial averaging for colors close to one another, we can use black and white color dithering to create an illusion of grayscale.
