# Ordered dithering

In this example (Lenna), the original photograph is shown on left. The version on the right shows the effect of quantizing it to 16 colors and dithering using the 8×8 ordered dithering pattern.
The characteristic 17 patterns of the 4×4 ordered dithering matrix can be seen clearly when used with only two colors, black and white. Each pattern is shown above the corresponding undithered shade.

Ordered dithering is an image dithering algorithm. It is commonly used to display a continuous image on a display of smaller color depth. For example, Microsoft Windows uses it in 16-color graphics modes. The algorithm is characterized by noticeable crosshatch patterns in the result.

## Threshold map

The algorithm reduces the number of colors by applying a threshold map M to the pixels displayed, causing some pixels to change color, depending on the distance of the original color from the available color entries in the reduced palette.

Threshold maps come in various sizes:

 ${\displaystyle {\frac {1}{4}}\times {\begin{bmatrix}0&2\\3&1\\\end{bmatrix}}}$ ${\displaystyle {\frac {1}{9}}\times {\begin{bmatrix}0&7&3\\6&5&2\\4&1&8\\\end{bmatrix}}}$ ${\displaystyle {\frac {1}{16}}\times {\begin{bmatrix}0&8&2&10\\12&4&14&6\\3&11&1&9\\15&7&13&5\\\end{bmatrix}}}$ ${\displaystyle {\frac {1}{64}}\times {\begin{bmatrix}0&48&12&60&3&51&15&63\\32&16&44&28&35&19&47&31\\8&56&4&52&11&59&7&55\\40&24&36&20&43&27&39&23\\2&50&14&62&1&49&13&61\\34&18&46&30&33&17&45&29\\10&58&6&54&9&57&5&53\\42&26&38&22&41&25&37&21\\\end{bmatrix}}}$

The map may be rotated or mirrored without affecting the effectiveness of the algorithm. This threshold map (for sides with length as power of two) is also known as an index matrix or Bayer matrix.[1]

Arbitrary size threshold maps can be devised with a simple rule: First fill each slot with a successive integers. Then reorder them such that the average distance between two successive numbers in the map is as large as possible, ensuring that the table "wraps" around at edges.[citation needed] For threshold maps whose dimensions are a power of two, the map can be generated recursively via:

${\displaystyle \mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}\times {\begin{bmatrix}4\times \mathbf {M} _{n}&4\times \mathbf {M} _{n}+2\\4\times \mathbf {M} _{n}+3&4\times \mathbf {M} _{n}+1\end{bmatrix}}}$

The recursive expression can be calculated explicitly using only bit arithmetic:[2]

M(i, j) = bit_reverse(bit_interleave(bitwise_xor(i, j), i)) / n ^ 2


## Pre-calculated threshold maps

Rather than storing map as a matrix of ${\displaystyle n}$×${\displaystyle n}$ integers from 0 to ${\displaystyle n^{2}}$, depending on the exact hardware used to perform the dithering, it may be beneficial to pre-calculate the thresholds of the map. For this, the following formula can be used:

Mpre(i,j) = (Mint(i,j)+1) / n^2


This generates a standard threshold matrix.

for the 2×2 map:

 ${\displaystyle {\frac {1}{4}}\times {\begin{bmatrix}0&2\\3&1\\\end{bmatrix}}}$

this creates the pre-calculated map:

 ${\displaystyle {\begin{bmatrix}0.25&0.75\\1.0&0.5\\\end{bmatrix}}}$

Additionally, the subtraction with 0.5 can be done during pre-processing as well:

Mpre(i,j) = (Mint(i,j)+1) / n^2 - 0.5


creating the pre-calculated map:

 ${\displaystyle {\begin{bmatrix}-0.25&0.25\\0.5&0\\\end{bmatrix}}}$

Yet another option is to instead change the range of color values to range 0—${\displaystyle n^{2}}$ (for a ${\displaystyle n}$×${\displaystyle n}$). Note however that this operation has to happen once for every pixel, and should thus only be performed if storing the threshold map as integers (instead of floating point numbers) is crucial.

## Algorithm

The ordered dithering algorithm renders the image normally, but for each pixel, it offsets its color value with a corresponding value from the threshold map according to its location, causing the pixel's value to be quantized to a different color if it exceeds the threshold.

For most dithering purposes, it is sufficient to simply add the threshold value to every pixel, or equivalently, to compare that pixel's value to the threshold: if the value of a pixel is less than the number in the corresponding cell of the matrix, plot that pixel black, otherwise, plot it white.

This slightly increases the average brightness of the image, and causes almost-white pixels to not be dithered. This is not a problem when using a gray scale palette (or any palette where the relative color distances are (nearly) constant), and it is often even desired, since the human eye perceives differences in darker colors more accurately than lighter ones, however, it cause incorrect results especially when using a small or arbitrary palette, so proper offsetting should be preferred.

A color scale shown undithered and dithered. The reduced palette on the right has 8 red tones, 8 green tones, and their intersections, for a total of 64 colors, whereas the original image has 140 in both directions, for a total of 19600 colors. Notice how the bottom-right square is not dithered

The algorithm performs the following transformation on each color c of every pixel:

${\displaystyle c'=\mathrm {nearest\_palette\_color} {\mathopen {}}\left(c+r\times \left(M(x{\bmod {n}},y{\bmod {n}})-{\frac {1}{2}}\right){\mathclose {}}\right)}$

where M(i, j) is the threshold map on the i-th row and j-th column, c is the transformed color, and r is the amount of spread in color space. Assuming an RGB palette with 23N evenly chosen colors where each color (a triple of red, green and blue values) is represented by an octet from 0 to 255, one would typically choose:

${\displaystyle r\approx {\frac {255}{N}}}$

The values read from the threshold map should preferably scale into the same range as the minimal difference between distinct colors in the target palette.

Because the algorithm operates on single pixels and has no conditional statements, it is very fast and suitable for real-time transformations. Additionally, because the location of the dithering patterns always stays the same relative to the display frame, it is less prone to jitter than error-diffusion methods, making it suitable for animations. Because the patterns are more repetitive than error-diffusion method, an image with ordered dithering compresses better. Ordered dithering is more suitable for line-art graphics as it will result in straighter lines and fewer anomalies.

The size of the map selected should be equal to or larger than the ratio of source colors to target colors. For example, when quantizing a 24bpp image to 15bpp (256 colors per channel to 32 colors per channel), the smallest map one would choose would be 4×2, for the ratio of 8 (256:32). This allows expressing each distinct tone of the input with different dithering patterns.[citation needed]

## Notes

1. ^ Bayer, Bryce (June 11–13, 1973). "An optimum method for two-level rendition of continuous-tone pictures" (PDF). IEEE International Conference on Communications. 1: 11–15. Archived from the original (PDF) on 2013-05-12.
2. ^ Joel Yliluoma. “Arbitrary-palette positional dithering algorithm