User:Renderedartwork/sandbox

In this example image, the photograph shown on left has been quantized to 16 colors and dithered using the 8x8 ordered dithering pattern.

Ordered dithering is an image dithering algorithm. It is used by programs that need to give the illusion of a continuous grey-scale or large range of colors, when the output device in fact can only display a very small number of colors or greys. For example, Microsoft Windows uses it in 16-color graphics modes, it is also used extensively in digital printing.

Ordered dithering operates on each primary color (Red, Green and Blue for a display and Cyan, Magenta, Yellow and Black for a printer) independently. For example, in an RGB device the image is separated in to Red, Green and Blue monochrome images, each one is dithered and then the image is re-combined in to a color image afterwards. As images are normally stored in computer memory as primary colors, the separation and re-combination will often involve no actual work. This is also true for dithering CMYK images, no special allowance is made for the K channel.

Ordered dithering works equally well when the number of output levels is 2 (i.e. binary) or more (often known as "greyscale").

Dither Matrix

The Dither Matrix is how ordered dithering determines what value to set each output pixel. This is a rectangular matrix in which every element is numbered from 1 to the number of elements. The integer numbers are contiguous and do not repeat, they are called the Rank of the element. Different matrices produce very different dither patterns.

The matrix is then normalised, depending on the number of input levels and number of output levels. The normalisation factor is calculated like this:

deltaQ = (INPUT_LEVELS-1) / (OUTUT_LEVELS-1)

The normalised elements in the Dither Matrix are called Rank'.

Application of the Dither Matrix

Dithering the image can be done in place (i.e. without another memory buffer) and can be done in parallel. The matrix may be rotated or mirrored without affecting the algorithm. This Dither Matrix is also known as a threshold map, an index matrix or Bayer matrix.

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 stays always the same relative to the display frame, it is less prone to jitter than error-diffusion methods, making it suitable for animations.

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 4x2, for the ratio of 8 (256:32). This allows expressing each distinct tone of the input with different dithering patterns.

Binary Output

For binary output the Dither matrix can be used as a threshold map. Each pixel is compared against its corresponding Rank' in the dither matrix. If the source pixel is greater than the Rank' then the output is 1 or on, otherwise the pixel is 0 or off.

In pseudocode:

for each y
   for each x
      original_pixel := pixel[x][y]
      if original_pixel > dither_matrix[x mod M][y mod N] then 
        pixel[x][y] := 1
      else
        pixel[x][y] := 0
      endif

The "mod" operator is used to determine which element of the Dither matrix (which has width M and height N) to compare the pixel with. If the original pixel exceeds the threshold, then it is set on otherwise it is set off.

Greyscale output

There are two methods to extend the Dither matrix to work with greyscale output.

Use the Dither matrix as a threshold map (as in binary), but use it to go between grey-levels

This is the method used in PostScript. This technique starts by determining which two grey-levels that the input pixel lies between, called the lower and upper levels. For example, if it were a 4 level output (0,1,2,3) and a 256 level input then 7 would map to between 0 and 1, 99 would map between 1 and 2. It then determines whether to use the upper or lower level (in this example, it must determine for "99" whether to place a 1 or a 2), by applying the threshold map.

In pseudocode:

for each y
   for each x
      original_pixel := pixel[x][y]
      lower_level := floor( (original_pixel * OUTPUT_LEVELS) / INPUT_LEVELS )
      upper_level := lower_level + 1
      normalised_pixel := original_pixel - lower_level * (INPUT_LEVELS / OUTPUT_LEVELS)
      if normalised_pixel > dither_matrix[x mod M][y mod N] then 
        pixel[x][y] := upper_level
      else
        pixel[x][y] := lower_level
      endif

Use the Dither matrix directly to calculate the output grey-level

The output value can be calculated directly from the Dither matrix, using the following algorithm

In pseudocode:

deltaQ := (INPUT_LEVELS-1) / (OUTUT_LEVELS-1)
for each y
   for each x
      original_pixel := pixel[x][y]
      pixel[x][y] := (original_pixel + dither_matrix[x mod M][y mod N])  / deltaQ

Generation of the Dither matrix

Bayer Matrix

Images dithered with the Bayer Matrix are easily distinguished by their noticeable crosshatch patterns. This type of matrix is designed to be optimal for image detail .

Different sizes of threshold maps exist:

${\frac {\displaystyle 1}{\displaystyle 5}}{\begin{bmatrix}1&3\\4&2\\\end{bmatrix}}$ ${\frac {\displaystyle 1}{\displaystyle 10}}{\begin{bmatrix}3&7&4\\6&1&9\\2&8&5\\\end{bmatrix}}$ ${\frac {\displaystyle 1}{\displaystyle 17}}{\begin{bmatrix}1&9&3&11\\13&5&15&7\\4&12&2&10\\16&8&14&6\\\end{bmatrix}}$

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

Arbitrary size threshold maps can be devised with a simple rule: First fill each slot with a successive integer starting from 1. 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.

Void & Cluster

A dither matrix created using the Void & Cluster method are optimal for blue noise and as such are designed the minimise the visual impact of the dithering

.

References

• Ordered Dithering (Graphics course project, Visgraf lab, Brazil)
• Dithering algorithms (Lee Daniel Crocker, Paul Boulay and Mike Morra)
• Arbitrary-palette positional dithering algorithm (Joel Yliluoma)

Category:Image processing Category:Articles with example pseudocode