Dither

Encyclopedia : D : DI : DIT : Dither

---

This article refers to dither and dithering as a technical term in digital signal processing, and the fields audio; video; and digital imaging. In this context, dither is only distantly related to the common as "a state of indecision" or "to be nervously irresolute in acting or doing."

Dither is a form of noise, or 'erroneous' signal or data which is added to sample data for the purpose of minimizing quantization error. Dither is routinely used in processing of both digital audio and digital video data. Jitter is not synonymous with dither.

Origin of the word \"dither\"

Dither in digital processing and waveform analysis

Dither most often surfaces in the field of digital audio, where it is applied to rate conversions and (usually optionally) to bit-depth transitions, but is utilized in many different fields where digital processing and analysis is used — especially waveform analysis. This includes any system using digital signal processing, such as digital audio, digital video, digital photography, seismology, RADAR, weather forecasting systems and many more.

The premise is that quantization and re-quantization of digital data yields error. If that error is repeating and correlated to the signal, the error that results is repeating, cyclical, and mathematically determinable. In some fields, especially where the receptor is sensitive to such artifacts, cyclical errors yield undesirable artifacts. In these fields we use dither to result in less determinable artifacts. The field of audio is a primary example of this — the human ear functions much like a Fourier transform, wherein it hears individual frequencies. The ear is therefore very sensitive to distortion, or additional frequency content that "colors" the sound differently. The ear is far less sensitive to random noise at all frequencies.

Digital audio

The final version of audio that goes onto a compact disc contains only 16 bits, but throughout the audio editing process the digital data grows in bit depth as computation occurs. The more math we do, the larger the samples grow in bit depth — just like adding, multiplying, or dividing decimal numbers. In the end, the digital data must be returned to 16 bits for pressing onto a CD and distributing.

There are multiple ways in which one can return the data to 16 bits. They can, for example, simply lop off the excess bits — called truncation. They can also round the excess bits to the nearest value. Each of these methods, however, results in predictable and determinable errors in the result. Take, for example, a waveform that consists of the following values:

1   2   3   4   5   6   7   8

If we reduce our waveform by, say, 20% then we end up with the following values:

0.8 1.6 2.4 3.2 4.0 4.8 5.6 6.4

If we truncate these values we end up with the following data:

0   1   2   3   4   4   5   6

If we instead round these values we end up with the following data:

1   2   2   3   4   5   6   6

If any waveform, comprising the original values, were to be processed by multiplying each value by .8, the result would contain errors, and the errors would be manifested as repeatable. A repeating sine wave quantized to the original sample values, for example, would experience the same error every time its supposed value was "3.4" in that the truncated result would be off by .4. Any time the supposed value was "5" the error after processing and truncation would be 0. Therefore, the error amount would change repeatedly as the values change. The result is cyclical behavior in the error, which manifests itself as additional frequency content on the waveform (harmonic distortion). The ear hears this as distortion, or the presence of additional frequency content.

We cannot avoid error resulting in this process. Taking a 2 digit number (4.8) and turning it into a 1 digit number (4 or 5) is going to result in error, and that is unavoidable. What we want to do, however, is create a system wherein that error does not repeat as the values repeat.

A plausible solution would be to take the 2 digit number (say, 4.8) and round it one direction or the other. For example, we could round it to 5 one time and then 4 the next time, etc., etc. This would make the long-term average 4.5 instead of 4, so that over the long-term the value is closer to its actual value. This, on the other hand, still results in determinable (though more complicated) error. Every other time the value 4.8 comes up the result is an error of .2, and the other times it is -.8. This still results in repeating, quantifiable error.

Another plausible solution would be to take 4.8 and round it so that four times out of five it rounded up to 5, and the other time it rounded to 4. This would average out to exactly 4.8 over the long term. Unfortunately, however, it still results in repeatable and determinable errors, and those errors still manifest themselves as distortion to the ear (though oversampling can reduce this).

This leads to the dither solution. Rather than predictably rounding up or down in a repeating pattern, what if we rounded up or down in a random pattern? If we came up with a way to randomly toggle our results between 4 and 5 so that 80% of the time it ended up on 5 then we would average 4.8 over the long run but would have random, unrepeating error in the result. This is done through dither.

We calculate a series of random numbers between 0 and .9 (ex: .6, .4, .5, .3, .7, etc.) and we add these random numbers to the results of our equation. Two times out of ten the result will truncate back to 4 (if 0 or .1 are added to 4.8) and the rest of the times it will truncate to 5, but each given situation has a random, but 20% chance of rounding to 4 or 80% chance of rounding to 5. Over the long haul this will result in results that average to 4.8 and a quantization error that is random — or noise. This "noise" result is less offensive to the ear than the determinable distortion that would result otherwise.

Audio samples: [media] (16-bit original) [media] (turncated to 6 bits) [media] (dithered to 6 bits)

When to add dither

Dither must be added before any quantization or re-quantization process in order to prevent non-linear behavior (distortion), the lesser the bit depth, the greater the dither must be. The results of the process still yield distortion, but the distortion is of the noise so its results are effectively noise. Any bit-reduction process should add dither to the waveform before the reduction is performed.

Different types of dither

RPDF stands for "Rectangular Probability Density Function," equivalent to a roll of a dice. Any number has the same random probability of surfacing.

TPDF stands for "Triangular Probability Density Function," equivalent to a roll of two dice. The number sums have different probabilities of surfacing:

1/1 = 2

1/2 2/1 = 3

1/3 2/2 3/1 = 4

1/4 2/3 3/2 4/1 = 5

1/5 2/4 3/3 4/2 5/1 = 6

1/6 2/5 3/4 4/3 5/2 6/1 = 7

2/6 3/5 4/4 5/3 6/2 = 8

3/6 4/5 5/4 6/3 = 9

4/6 5/5 6/4 = 10

5/6 6/5 = 11

6/6 = 12

7 is far more likely to surface than 2 or 12, and the relationship between these probabilities is said to be "triangular."

Gaussian PDF is equivalent to a roll of infinite dice. The relationship of probabilities of results follows a bell-shaped, or Gaussian curve. Gaussian PDF dither is closest in proximity to the sound of natural atmospheric noise, tape hiss, etc.

Colored Dither is sometimes mentioned as dither that has been filtered to be different from white noise. Some dither algorithms use noise that has more energy in the higher frequencies so as to lower the energy in the critical audio band.

Noise shaping is not actually dither, but rather a feedback process that has dither within it. It is used for the same purposes.

Which dither to use

If the signal being dithered is to undergo any further processing at all then it should be processed with TPDF dither that has an amplitude of two quantization steps (so that the dither values computed range from, say, -1 to +1, or 0 to 2). If colored dither is used at these intermediate processing stages then the frequency content can "bleed" into other, more noticeable frequency ranges and become distractingly audible.

If the signal being dithered is to undergo no further processing — it is being dithered to its final result for distribution — then colored dither or noiseshaping are appropriate, and can effectively lower the audible noise level by putting most of that noise in areas where it is less critical.

Digital photography and image processing

Dithering is a technique used in computer graphics to create the illusion of color depth in images with a limited color palette (color quantization). In a dithered image, colors not available in the palette are approximated by a diffusion of colored pixels from within the available palette. The human eye perceives the diffusion as a mixture of the colors within it (see color vision). Dithering is analogous to the halftone technique used in printing. Dithered images, particularly those with relatively few colors, can often be distinguished by a characteristic graininess, or speckled appearance.

Dithering examples

Reducing the color depth of an image can often have significant visual side-effects. If the original image is a photograph, it is likely to have thousands, or even millions of distinct colors. The process of constraining the available colors to a specific color palette effectively throws away a certain amount of color information.

A number of factors can affect the resulting quality of a color-reduced image. Perhaps most significant is the color palette that will be used in the reduced image. For example, an original image (Figure 1) may be reduced to the 216-color "web-safe" color palette. If the original pixel colors are simply translated into the closest available color from the palette, no dithering occurs (Figure 2). Typically, this approach results in flat areas and a loss of detail, and may produce patches of color that are significantly different from the original. Shaded or gradient areas may appear as color bands, which may be distracting. The application of dithering can help to minimize such visual artifacts, and usually results in a better representation of the original (Figure 3). Dithering helps to reduce color banding and flatness.

One of the problems associated with using a fixed color palette is that many of the needed colors may not be available in the palette, and many of the available colors may not be needed; a fixed palette containing mostly shades of green would not be well-suited for images that do not contain many shades of green, for instance. The use of an optimized color palette can be of benefit in such cases. An optimized color palette is one in which the available colors are chosen based on how frequently they are used in the original source image. If the image is reduced based on an optimized palette, the result is often much closer to the original (Figure 4).

The number of colors available in the palette is also a contributing factor. If, for example, the palette is limited to only 16 colors, the resulting image could suffer from additional loss of detail, and even more pronounced problems with flatness and color banding (Figure 5). Once again, dithering can help to minimize such artifacts (Figure 6).

Applications

Display hardware, including early computer video adapters and many modern LCDs used in mobile phones and inexpensive digital cameras, are capable of showing a smaller color range than more advanced displays. One common application of dithering is to more accurately display graphics containing a greater range of colors than the hardware is capable of showing. For example, dithering might be used in order to display a photographic image containing millions of colors on video hardware that is only capable of showing 256 colors at a time. The 256 available colors would be used to generate a dithered approximation of the original image. Without dithering, the colors in the original image might be simply be "rounded off" to the closest available color, resulting in a new image that is a poor representation of the original. Dithering takes advantage of the human eye's tendency to "mix" two colors in close proximity to one another.

Dithering such as this, in which the computer's display hardware is the primary limitation on color depth, is commonly employed in software such as web browsers. Since a web browser may be retrieving graphical elements from an external source, it may be necessary for the browser to perform dithering on images with too many colors for the available display. It was due to problems with dithering that a color palette known as the "web-safe color palette" was identified, for use in choosing colors that would not be dithered on displays with only 256 colors available.

Another useful application of dithering is for situations in which the graphic file format is the limiting factor. In particular, the commonly-used GIF format is restricted to the use of 256 or fewer colors. Images in other file formats, such as PNG, may also have such a restriction imposed on them for the sake of a reduction in file size. Images such as these have a fixed color palette defining all the colors that the image may use. For such situations, graphical editing software may be responsible for dithering images prior to saving them in such restrictive formats.

Dithering algorithms

There are several algorithms designed to perform dithering. One of the earliest, and still one of the most popular, is the Floyd-Steinberg dithering algorithm, developed in 1975. One of the strengths of this algorithm is that it minimizes visual artifacts through an error-diffusion process; the Floyd-Steinberg algorithm typically produces images that more closely represent the original than simpler dithering algorithms.

Other dithering methods include:

• Average dithering: one of the simplest dithering techniques, based on selecting an average tone and choosing pixel colors based on how close they are to the average
• Ordered dithering: produces a cross-hatch dithering pattern similar to the halftones used by print newspapers
• Random dithering: introduces a random element to each pixel, resulting in a staticky image
• Albie dithering: a method similar to Floyd-Steinberg, but optimized for display on interlaced monitors

References

Much of the research in the field of dither for (at absolute least) the audio industry was done by Lipshitz, Vanderkooy, and Wannamaker at the University of Waterloo.

See also

• Digital audio
• Quantization (signal processing)

External links

• [What is Dither?] Article previously published in Australian HI-FI with visual examples of how audio dither sharply reduces high order harmonic distortion.

Other well-written papers on the subject at a more elementary level are available by:

• Aldrich, Nika. "[Dither Explained (pdf)]"
• Katz, Bob. [The Secrets of Dither]"

Both Nika Aldrich and Bob Katz are esteemed experts in the field of digital audio and have books available as well, each of which are far more comprehensive in their explanations:

• Aldrich, Nika. "[Digital Audio Explained]"
• Katz, Bob. "[Mastering Audio]"

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?