Ordered dithering

Ordered dithering is any image dithering algorithm which uses a pre-set threshold map tiled across an image. 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.

In this example, 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.

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.

The first threshold maps were designed by hand to minimise the perceptual difference between a grayscale image and its two-bit quantisation for up to a 4x4 matrix. ^[1]

An optimal threshold matrix is one that for any possible quantisation of color has the minimum possible texture so that the greatest impression of the underlying feature comes from the image being quantised. It can be proven that for matrices whose side length is a power of two there is an optimal threshold matrix.^[2] The map may be rotated or mirrored without affecting the effectiveness of the algorithm.

\mathbf {M_{2}} ={\frac {1}{4}}{\begin{bmatrix}0&2\\3&1\\\end{bmatrix}}

\mathbf {M_{4}} ={\frac {1}{16}}{\begin{bmatrix}0&8&2&10\\12&4&14&6\\3&11&1&9\\15&7&13&5\\\end{bmatrix}}

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

This threshold map (for sides with length as power of two) is also known as a Bayer matrix or, when unscaled, an index matrix. For threshold maps whose dimensions are a power of two, the map can be generated recursively via:

\mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}{\begin{bmatrix}(2n)^{2}\mathbf {M} _{n}&(2n)^{2}\mathbf {M} _{n}+2\mathbf {J} _{n}\\(2n)^{2}\mathbf {M} _{n}+3\mathbf {J} _{n}&(2n)^{2}\mathbf {M} _{n}+\mathbf {J} _{n}\end{bmatrix}}=\mathbf {J} _{2}\otimes \mathbf {M} _{n}+{\frac {1}{n^{2}}}\mathbf {M} _{2}\otimes \mathbf {J} _{n},

where $\mathbf {J} _{n}$ are $n\times n$ matrices of ones and $\otimes$ is the Kronecker product.

While the metric for texture that Bayer proposed could be used find optimal matrices for sizes that are not a power of two, such matrices are uncommon as no simple formula for finding them exists, and relatively small matrix sizes frequently give excellent practical results (especially when combined with other modifications to the dithering algorithm).

This function can also be expressed using only bit arithmetic:^[3]

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

Pre-calculated threshold maps

Rather than storing the threshold map as a matrix of $n$ × $n$ integers from 0 to $n^{2}$ , depending on the exact hardware used to perform the dithering, it may be beneficial to pre-calculate the thresholds of the map into a floating point format, rather than the traditional integer matrix format shown above.

For this, the following formula can be used:

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

This generates a standard threshold matrix.

for the 2×2 map:

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

this creates the pre-calculated map:

{\begin{bmatrix}0.0&0.5\\0.75&0.25\\\end{bmatrix}}

Additionally, normalizing the values to average out their sum to 0 (as done in the dithering algorithm shown below) can be done during pre-processing as well by subtracting 1⁄2 of the largest value from every value:

Mpre(i,j) = Mint(i,j) / n^2 – 0.5 * maxValue

creating the pre-calculated map:

{\begin{bmatrix}-0.375&0.125\\0.375&-0.125\\\end{bmatrix}}

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 (without performing normalization by subtracting 1⁄2), or equivalently, to compare the pixel's value to the threshold: if the brightness 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 lack of normalization 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 produces incorrect results especially when using a small or arbitrary palette, so proper normalization should be preferred.

Two images mimicking a gradient of 140 × 140 = 19600 different colors. Both images use the same 64 colors. The image on the right has been dithered. The dithering was done using a non-normalizing dithering algorithm, causing the image to have a slight over-representation of bright pixels.

In other words, the algorithm performs the following transformation on each color $c$ of every pixel: $c'=\mathrm {nearest\_palette\_color} {\mathopen {}}\left(c+r\times \left(M(x{\bmod {n}},y{\bmod {n}})-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 $2 3 N$ evenly distanced 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 ${\textstyle r\approx {\frac {255}{N}}}$ . (1⁄2 is again the normalizing term.)

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 values read from the threshold map should preferably scale into the same range as the minimal difference between distinct colors in the target palette. Equivalently, 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 24 bpp image to 15 bpp (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]}

A variable palette: pattern dithering

Non-Bayer approaches

The above thresholding matrix approach describes the Bayer family of ordered dithering algorithms. A number of other algorithms are also known; they generally involve changes in the threshold matrix, equivalent to the "noise" in general descriptions of dithering.

Halftone

Halftone dithering performs a form of clustered dithering, creating a look similar to halftone patterns, using a specially crafted matrix.

Void and cluster

The Void and cluster algorithm uses a pre-generated blue noise as the matrix for the dithering process.^[4] The blue noise matrix keeps the Bayer's good high frequency content, but with a more uniform coverage of all the frequencies involved shows a much lower amount of patterning.^[5]

The "voids-and-cluster" method gets its name from the matrix generation procedure, where a black image with randomly initialized white pixels is gaussian-blurred to find the brightest and darkest parts, corresponding to voids and clusters. After a few swaps have evenly distributed the bright and dark parts, the pixels are numbered by importance. It takes significant computational resources to generate the blue noise matrix: on a modern computer a 64×64 matrix requires a couple seconds using the original algorithm.^[6]

This algorithm can be extended to make animated dither masks which also consider the axis of time. This is done by running the algorithm in three dimensions and using a kernel which is a product of a two-dimensional gaussian kernel on the XY plane, and a one-dimensional Gaussian kernel on the Z axis.^[7]

References

^ Lippel, Kurland (December 1971). "The Effect of Dither on Luminance Quantization of Pictures". IEEE Transactions on Communication Technology. 19 (6): 879–888. doi:10.1109/TCOM.1971.1090773.
^ 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. Retrieved 2012-07-19.
^ Joel Yliluoma. “Arbitrary-palette positional dithering algorithm”
^ Ulichney, Robert A (1993). "The void-and-cluster method for dither array generation" (PDF). Retrieved 2014-02-11.
^ Wronski, Bart (31 October 2016). "Dithering part three – real world 2D quantization dithering".
^ Peters, Christoph. "Free blue noise textures". momentsingraphics.de.
^ Wolfe, Alan; Morrical, Nathan; Akenine-Möller, Tomas; Ramamoorthi, Ravi (2022). Spatiotemporal Blue Noise Masks. The Eurographics Association. doi:10.2312/sr.20221161. ISBN 978-3-03868-187-8. S2CID 250164404.

Ordered Dithering (Graphics course project, Visgraf lab, Brazil)
Dithering algorithms (Lee Daniel Crocker, Paul Boulay and Mike Morra)

External links

Matlab implementation of various dithering methods
anim8gdx, Java implementation of various (mostly ordered) dithering methods

[lippelkurland-1] Lippel, Kurland (December 1971). "The Effect of Dither on Luminance Quantization of Pictures". IEEE Transactions on Communication Technology. 19 (6): 879–888. doi:10.1109/TCOM.1971.1090773.

[bayermatrix-2] 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. Retrieved 2012-07-19.

[3] Joel Yliluoma. “Arbitrary-palette positional dithering algorithm”

[voidcluster-4] Ulichney, Robert A (1993). "The void-and-cluster method for dither array generation" (PDF). Retrieved 2014-02-11.

[5] Wronski, Bart (31 October 2016). "Dithering part three – real world 2D quantization dithering".

[6] Peters, Christoph. "Free blue noise textures". momentsingraphics.de.

[7] Wolfe, Alan; Morrical, Nathan; Akenine-Möller, Tomas; Ramamoorthi, Ravi (2022). Spatiotemporal Blue Noise Masks. The Eurographics Association. doi:10.2312/sr.20221161. ISBN 978-3-03868-187-8. S2CID 250164404.

[1]

[2]

[3]

[4]

[5]

[6]

[7]