Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

A Balanced Dithering Technique


December 1998/A Balanced Dithering Technique/Sidebar

Ordered Dither and Error Diffusion Dither


Dithering is a subject that could cover an entire book, and indeed such a book has been written. Digital Halftoning by Robert Ulichney [1] discusses and analyzes several well-known dithering techniques. Of all dithering algorithms, the two most common are ordered dither and error diffusion dither. Both of these algorithms run through the source image scan line by scan line; they do not employ a Hilbert curve or other space-filling curves.

For the following discussion I will assume that we are given a gray-scale image with 256 shades of gray, which are assigned intensity values from 0 to 255 (for black to white respectively), and that we are dithering the image to a bi-level, black-and-white image.

Ordered dither algorithms use a fixed matrix; two common approaches are "clustered dot ordered dither" and "dispersed dot ordered dither." The halftoning procedure used in newspapers is an example of clustered dot dither.

The ordered dither algorithm compares the gray level of a pixel to a level in a dither matrix. Depending on this comparison, the pixel is set to either black or white. The matrix contains threshold values between 0 and 255. The size of the matrix and the arrangement of the values have an important effect on the dither process. When a picture is larger than the dither matrix (and it usually is), the matrix is tiled over the image. Every pixel in the source image is compared to only one level in the dither matrix. Neighboring pixels have no effect on the dither result.

Error diffusion dither algorithms spread the error (caused by quantizing a pixel) over neighboring pixels; the best known example of error diffusion dither is the "Floyd Steinberg" dither. In error diffusion, the value of a pixel is compared to a single threshold of 50 percent gray (that is, when black is 0 and white is 255, each pixel is compared to 128). The pixel is set to either black or white, based on that comparison. After outputting the dithered pixel, the algorithm calculates the difference between the source pixel and the output pixel (a simple subtraction), and then it spreads this difference (the "error") over neighboring pixels. In other words, the algorithm changes the source image as it goes through it. The error is partitioned between pixels to the right of the current pixel and pixels below the current pixel. The "diffusion" part of the error diffusion algorithm is thus two-dimensional.

The ordered dither matrices have the advantage that the dither operation is a point process. The value to which a pixel is quantized depends only on the pixel color and its position. With error diffusion dithers, the dither result of any pixel also depends on the dither results of its neighboring pixels. This means that modifying one pixel in the source image can provoke changes in a large area of the dithered result.

The error diffusion dither algorithms have the advantage that they create images containing less low-frequency content, which makes the dithered pictures more detailed and more attractive (see Digital Halftoning, page 236). More important still is that error diffusion dither does not require a uniform color palette when dithering to a gray scale or to a reduced color palette. On computer displays, dithering is often used in combination with color quantization, which seeks to produce an optimized palette. The error diffusion algorithms can exploit an optimized (and probably non-uniform) palette. The ordered dither must use either a uniform palette or a subset of the optimized palette for dithering.

Especially in the case of (frame) animation, the "point process" attribute of ordered dither is important, because it can dramatically reduce the size of the delta between one frame and the next. On the other hand, for best image quality, the value of an optimal palette (and a dither that can exploit that full palette) should not be underestimated. Hence, the focus on new dither algorithms that combine these features.

The Riemersma dither algorithm presented here is a compromise: it is an area process instead of a point process, and the produced dither is coarser than that of the error diffusion algorithm. The number of neighboring pixels that are affected by the dither value of the current pixel can be selected; I regard 16 neighboring pixels as a minimum to get a respectable dither. In the main article, I said that the accumulated error list used in Riemersma dither should be at least 16 entries long. In the case of Riemersma dither (but not other dithering algorithms) these two statements really amount to the same thing: a respectable dither requires that a change in one pixel adds to the accumulated error that affects the dither value of at least 16 subsequent pixels along the Hilbert curve.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.