Dither
Encyclopedia
Dither is an intentionally applied form of noise
used to randomize quantization error
, preventing large-scale patterns such as color banding in images. Dither is routinely used in processing of both digital audio and digital video data, and is often one of the last stages of audio production to compact disc
.
, 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 dither results 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, but far less sensitive to random noise at all frequencies.
In 1987, Lipshitz and Vanderkooy pointed out that different noise types, with different probability density function
s, behave differently when used as dither signals, and suggested optimal levels of dither signals for audio.
The final version of audio that goes onto a compact disc
contains only 16 bit
s per sample, but throughout the production process a greater number of bits are typically used to represent the sample. In the end, the digital data must be reduced to 16 bits for pressing onto a CD and distributing.
There are multiple ways to do this. One can, for example, simply discard the excess bits — called truncation. One 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
For any original waveform, the process of reducing the waveform amplitude by 20% results in regular errors. Take for example a sine wave that, for some portion, matches the values above. Every time the sine wave's value hit "3.2," the truncated result would be off by 0.2, as in the sample data above. Every time the sine wave's value hit "4.0," there would be no error since the truncated result would be off by 0.0, also shown above. The magnitude of this error changes regularly and repeatedly throughout the sine wave's cycle. It is precisely this error which manifests itself as distortion
. What the ear hears as distortion is the additional content at discrete frequencies created by the regular and repeated quantization error.
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. 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 0.2, and the other times it is –0.8. This still results in repeating, quantifiable error.
Another plausible solution would be to take 4.8 and round it so that the first four times out of five it rounded up to 5, and the fifth 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, non-repeating error in the result. This is done through dither.
We calculate a series of random numbers between 0.0 and 0.9 (ex: 0.6, 0.1, 0.3, 0.6, 0.9, 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.0 or 0.1 are added to 4.8) and the rest of the times it will truncate to 5, but each given situation has a random 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:
. Any number has the same random probability
of surfacing.
TPDF stands for "Triangular Probability Density Function," equivalent to a roll of two dice (the sum of two independent samples of RPDF).
Gaussian PDF is equivalent to a roll of a large number of dice. The relationship of probabilities of results follows a bell-shaped, or Gaussian curve, typical of dither generated by analog sources such as microphone preamplifiers. If the bit depth of a recording is sufficiently great, that noise will be sufficient to dither the recording.
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 a filtering process that shapes the spectral energy of quantization error, typically to either de-emphasise frequencies to which the ear is most sensitive or separate the signal and noise bands completely. If dither is used, its final spectrum depends on whether it is added inside or outside the feedback loop of the noise shaper: if inside, the dither is treated as part of the error signal and shaped along with actual quantization error; if outside, the dither is treated as part of the original signal and linearises quantization without being shaped itself. In this case, the final noise floor is the sum of the flat dither spectrum and the shaped quantization noise. While real-world noise shaping usually includes in-loop dithering, it is also possible to use it without adding dither at all, in which case the usual harmonic-distortion effects still appear at low signal levels.
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 noise shaping is appropriate, and can effectively lower the audible noise level by putting most of that noise in a frequency range where it is less critical.
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 pixel
s 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.
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 (contours) 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).
used in mobile phone
s and inexpensive digital camera
s, show a much 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 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.
Some LCDs may use temporal dithering to achieve a similar effect. By alternating each pixel's color value rapidly between two approximate colors in the panel's color space (also known as Frame Rate Control
), a display panel which natively supports 18-bit color (6 bits per channel) can represent a 24-bit "true" color image (8 bits per channel).
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 browser
s. 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.
But even when the total number of available colors in the display hardware is high enough when rendering full color digital photographs, as those 15- and 16-bit RGB Hicolor 32,768/65,536 color modes, banding can be evident to the eye, especially in large areas of smooth shade transitions (although the original image file has no banding at all). Dithering the 32 or 64 RGB levels will result in a pretty good "pseudo truecolor" display approximation, which the eye cannot resolve as grainy. Furthermore, images displayed on 24-bit RGB hardware (8 bits per RGB primary) can be dithered to simulate somewhat higher bit depth, and/or to minimize the loss of hues available after a gamma correction
. High-end still image processing software, as Adobe Photoshop
, commonly uses these techniques for improved display.
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 in many graphics editing programs. 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.
s 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; error-diffusion algorithms typically produce images that more closely represent the original than simpler dithering algorithms.
Dithering methods include:
(SBS) is a nonlinear optical effect
that limits the launched optical power in fiber optic systems. This power limit can be increased by dithering the transmit optical center frequency, typically implemented by modulating the laser's bias input.
Other well-written papers on the subject at a more elementary level are available by:
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:
More recent research in the field of dither for audio was done by Lipshitz, Vanderkooy, and Wannamaker at the University of Waterloo
:
Noise
In common use, the word noise means any unwanted sound. In both analog and digital electronics, noise is random unwanted perturbation to a wanted signal; it is called noise as a generalisation of the acoustic noise heard when listening to a weak radio transmission with significant electrical noise...
used to randomize quantization error
Quantization error
In analog-to-digital conversion, the difference between the actual analog value and quantized digital value is called quantization error or quantization distortion. This error is either due to rounding or truncation...
, preventing large-scale patterns such as color banding in images. Dither is routinely used in processing of both digital audio and digital video data, and is often one of the last stages of audio production to compact disc
Compact Disc
The Compact Disc is an optical disc used to store digital data. It was originally developed to store and playback sound recordings exclusively, but later expanded to encompass data storage , write-once audio and data storage , rewritable media , Video Compact Discs , Super Video Compact Discs ,...
.
Etymology
The term "dither" was published in books on analog computation and hydraulic controlled guns shortly after the war. The concept of dithering to reduce quantization patterns was first applied by Lawrence G. Roberts in his 1961 MIT master's thesis and 1962 article though he did not use the term dither. By 1964 dither was being used in the modern sense described in this article.In digital processing and waveform analysis
Dither is often used in digital audio and video processing, where it is applied to bit-depth transitions; it is utilized in many different fields where digital processing and analysis are used — especially waveform analysis. These uses include systems using digital signal processingDigital signal processing
Digital signal processing is concerned with the representation of discrete time signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing...
, such as digital audio
Digital audio
Digital audio is sound reproduction using pulse-code modulation and digital signals. Digital audio systems include analog-to-digital conversion , digital-to-analog conversion , digital storage, processing and transmission components...
, digital video
Digital video
Digital video is a type of digital recording system that works by using a digital rather than an analog video signal.The terms camera, video camera, and camcorder are used interchangeably in this article.- History :...
, digital photography
Digital photography
Digital photography is a form of photography that uses an array of light sensitive sensors to capture the image focused by the lens, as opposed to an exposure on light sensitive film...
, seismology
Seismology
Seismology is the scientific study of earthquakes and the propagation of elastic waves through the Earth or through other planet-like bodies. The field also includes studies of earthquake effects, such as tsunamis as well as diverse seismic sources such as volcanic, tectonic, oceanic,...
, RADAR
Radar
Radar is an object-detection system which uses radio waves to determine the range, altitude, direction, or speed of objects. It can be used to detect aircraft, ships, spacecraft, guided missiles, motor vehicles, weather formations, and terrain. The radar dish or antenna transmits pulses of radio...
, weather forecasting
Weather forecasting
Weather forecasting is the application of science and technology to predict the state of the atmosphere for a given location. Human beings have attempted to predict the weather informally for millennia, and formally since the nineteenth century...
systems and many more.
The premise is that quantization
Quantization (signal processing)
Quantization, in mathematics and digital signal processing, is the process of mapping a large set of input values to a smaller set – such as rounding values to some unit of precision. A device or algorithmic function that performs quantization is called a quantizer. The error introduced by...
and re-quantization of digital data yields error. If that error is repeating and correlated
Correlation
In statistics, dependence refers to any statistical relationship between two random variables or two sets of data. Correlation refers to any of a broad class of statistical relationships involving dependence....
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 dither results in less determinable artifacts. The field of audio is a primary example of this — the human ear
Ear
The ear is the organ that detects sound. It not only receives sound, but also aids in balance and body position. The ear is part of the auditory system....
functions much like a Fourier transform
Fourier transform
In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
, wherein it hears individual frequencies. The ear is therefore very sensitive to distortion
Distortion
A distortion is the alteration of the original shape of an object, image, sound, waveform or other form of information or representation. Distortion is usually unwanted, and often many methods are employed to minimize it in practice...
, or additional frequency content that "colors" the sound differently, but far less sensitive to random noise at all frequencies.
Digital audio
In audio, dither can be useful to break up periodic limit cycles, which are a common problem in digital filters. Random noise is typically less objectionable than the harmonic tones produced by limit cycles.In 1987, Lipshitz and Vanderkooy pointed out that different noise types, with different probability density function
Probability density function
In probability theory, a probability density function , or density of a continuous random variable is a function that describes the relative likelihood for this random variable to occur at a given point. The probability for the random variable to fall within a particular region is given by the...
s, behave differently when used as dither signals, and suggested optimal levels of dither signals for audio.
In an analog system, the signal is continuous, but in a PCM digital system, the amplitude of the signal out of the digital system is limited to one of a set of fixed values or numbers. This process is called quantizationQuantization (sound processing)In signal processing and digital audio, quantization is the process of approximating a continuous range of values by a relatively small set of discrete symbols or integer values...
. Each coded value is a discrete step... if a signal is quantized without using dither, there will be quantization distortion related to the original input signal... In order to prevent this, the signal is "dithered", a process that mathematically removes the harmonics or other highly undesirable distortions entirely, and that replaces it with a constant, fixed noise level.
The final version of audio that goes onto a compact disc
Compact Disc
The Compact Disc is an optical disc used to store digital data. It was originally developed to store and playback sound recordings exclusively, but later expanded to encompass data storage , write-once audio and data storage , rewritable media , Video Compact Discs , Super Video Compact Discs ,...
contains only 16 bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s per sample, but throughout the production process a greater number of bits are typically used to represent the sample. In the end, the digital data must be reduced to 16 bits for pressing onto a CD and distributing.
There are multiple ways to do this. One can, for example, simply discard the excess bits — called truncation. One 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
For any original waveform, the process of reducing the waveform amplitude by 20% results in regular errors. Take for example a sine wave that, for some portion, matches the values above. Every time the sine wave's value hit "3.2," the truncated result would be off by 0.2, as in the sample data above. Every time the sine wave's value hit "4.0," there would be no error since the truncated result would be off by 0.0, also shown above. The magnitude of this error changes regularly and repeatedly throughout the sine wave's cycle. It is precisely this error which manifests itself as distortion
Distortion
A distortion is the alteration of the original shape of an object, image, sound, waveform or other form of information or representation. Distortion is usually unwanted, and often many methods are employed to minimize it in practice...
. What the ear hears as distortion is the additional content at discrete frequencies created by the regular and repeated quantization error.
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. 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 0.2, and the other times it is –0.8. This still results in repeating, quantifiable error.
Another plausible solution would be to take 4.8 and round it so that the first four times out of five it rounded up to 5, and the fifth 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
Oversampling
In signal processing, oversampling is the process of sampling a signal with a sampling frequency significantly higher than twice the bandwidth or highest frequency of the signal being sampled...
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, non-repeating error in the result. This is done through dither.
We calculate a series of random numbers between 0.0 and 0.9 (ex: 0.6, 0.1, 0.3, 0.6, 0.9, 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.0 or 0.1 are added to 4.8) and the rest of the times it will truncate to 5, but each given situation has a random 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:
Usage
Dither should be added to any low-amplitude or highly-periodic signal before any quantization or re-quantization process, in order to de-correlate the quantization noise from the input signal and to prevent non-linear behavior (distortion); the lesser the bit depth, the greater the dither must be. The result of the process still yields distortion, but the distortion is of a random nature so the resulting noise is, effectively, de-correlated from the intended signal. Any bit-reduction process should add dither to the waveform before the reduction is performed.Different types
RPDF stands for "Rectangular Probability Density Function," equivalent to a roll of a dieDice
A die is a small throwable object with multiple resting positions, used for generating random numbers...
. Any number has the same random probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
of surfacing.
TPDF stands for "Triangular Probability Density Function," equivalent to a roll of two dice (the sum of two independent samples of RPDF).
Gaussian PDF is equivalent to a roll of a large number of dice. The relationship of probabilities of results follows a bell-shaped, or Gaussian curve, typical of dither generated by analog sources such as microphone preamplifiers. If the bit depth of a recording is sufficiently great, that noise will be sufficient to dither the recording.
Colored Dither is sometimes mentioned as dither that has been filtered to be different from white noise
White noise
White noise is a random signal with a flat power spectral density. In other words, the signal contains equal power within a fixed bandwidth at any center frequency...
. 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
Noise shaping
Noise shaping is a technique typically used in digital audio, image, and video processing, usually in combination with dithering, as part of the process of quantization or bit-depth reduction of a digital signal...
is a filtering process that shapes the spectral energy of quantization error, typically to either de-emphasise frequencies to which the ear is most sensitive or separate the signal and noise bands completely. If dither is used, its final spectrum depends on whether it is added inside or outside the feedback loop of the noise shaper: if inside, the dither is treated as part of the error signal and shaped along with actual quantization error; if outside, the dither is treated as part of the original signal and linearises quantization without being shaped itself. In this case, the final noise floor is the sum of the flat dither spectrum and the shaped quantization noise. While real-world noise shaping usually includes in-loop dithering, it is also possible to use it without adding dither at all, in which case the usual harmonic-distortion effects still appear at low signal levels.
Which types to use
If the signal being dithered is to undergo further processing, 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). This is the lowest power ideal dither, in that it does not introduce noise modulation (constant noise floor) and completely eliminates the harmonic distortion from *quantization*. 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 noise shaping is appropriate, and can effectively lower the audible noise level by putting most of that noise in a frequency range where it is less critical.
Digital photography and image processing
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
to create the illusion of color
Color
Color or colour is the visual perceptual property corresponding in humans to the categories called red, green, blue and others. Color derives from the spectrum of light interacting in the eye with the spectral sensitivities of the light receptors...
depth in images with a limited color palette (color quantization
Color quantization
In computer graphics, color quantization or color image quantization is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as visually similar as possible to the original image. Computer algorithms to perform color...
). In a dithered image, colors not available in the palette are approximated by a diffusion of colored pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
s from within the available palette. The human eye perceives the diffusion as a mixture of the colors within it (see color vision
Color vision
Color vision is the capacity of an organism or machine to distinguish objects based on the wavelengths of the light they reflect, emit, or transmit...
). Dithering is analogous to the halftone
Halftone
Halftone is the reprographic technique that simulates continuous tone imagery through the use of dots, varying either in size, in shape or in spacing...
technique used in printing
Printing
Printing is a process for reproducing text and image, typically with ink on paper using a printing press. It is often carried out as a large-scale industrial process, and is an essential part of publishing and transaction printing....
. Dithered images, particularly those with relatively few colors, can often be distinguished by a characteristic graininess, or speckled appearance.
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 (contours) 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 LCDsLiquid crystal display
A liquid crystal display is a flat panel display, electronic visual display, or video display that uses the light modulating properties of liquid crystals . LCs do not emit light directly....
used in mobile phone
Mobile phone
A mobile phone is a device which can make and receive telephone calls over a radio link whilst moving around a wide geographic area. It does so by connecting to a cellular network provided by a mobile network operator...
s and inexpensive digital camera
Digital camera
A digital camera is a camera that takes video or still photographs, or both, digitally by recording images via an electronic image sensor. It is the main device used in the field of digital photography...
s, show a much 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 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.
Some LCDs may use temporal dithering to achieve a similar effect. By alternating each pixel's color value rapidly between two approximate colors in the panel's color space (also known as Frame Rate Control
Frame Rate Control
Frame Rate Control is a method for achieving higher color quality in low color resolution display panels such as TN+film LCD.Most TN panels represent colors using only 6 bits per RGB color, or 18 bit in total, and are unable to display the 16.7 million color shades that are available from...
), a display panel which natively supports 18-bit color (6 bits per channel) can represent a 24-bit "true" color image (8 bits per channel).
Dithering such as this, in which the computer's display hardware is the primary limitation on color depth
Color depth
In computer graphics, color depth or bit depth is the number of bits used to represent the color of a single pixel in a bitmapped image or video frame buffer. This concept is also known as bits per pixel , particularly when specified along with the number of bits used...
, is commonly employed in software such as web browser
Web browser
A web browser is a software application for retrieving, presenting, and traversing information resources on the World Wide Web. An information resource is identified by a Uniform Resource Identifier and may be a web page, image, video, or other piece of content...
s. 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.
But even when the total number of available colors in the display hardware is high enough when rendering full color digital photographs, as those 15- and 16-bit RGB Hicolor 32,768/65,536 color modes, banding can be evident to the eye, especially in large areas of smooth shade transitions (although the original image file has no banding at all). Dithering the 32 or 64 RGB levels will result in a pretty good "pseudo truecolor" display approximation, which the eye cannot resolve as grainy. Furthermore, images displayed on 24-bit RGB hardware (8 bits per RGB primary) can be dithered to simulate somewhat higher bit depth, and/or to minimize the loss of hues available after a gamma correction
Gamma correction
Gamma correction, gamma nonlinearity, gamma encoding, or often simply gamma, is the name of a nonlinear operation used to code and decode luminance or tristimulus values in video or still image systems...
. High-end still image processing software, as Adobe Photoshop
Adobe Photoshop
Adobe Photoshop is a graphics editing program developed and published by Adobe Systems Incorporated.Adobe's 2003 "Creative Suite" rebranding led to Adobe Photoshop 8's renaming to Adobe Photoshop CS. Thus, Adobe Photoshop CS5 is the 12th major release of Adobe Photoshop...
, commonly uses these techniques for improved display.
Another useful application of dithering is for situations in which the graphic file format is the limiting factor. In particular, the commonly-used GIF
GIF
The Graphics Interchange Format is a bitmap image format that was introduced by CompuServe in 1987 and has since come into widespread usage on the World Wide Web due to its wide support and portability....
format is restricted to the use of 256 or fewer colors in many graphics editing programs. 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.
Algorithms
There are several algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s 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
Error diffusion
Error diffusion is a type of halftoning in which the quantization residual is distributed to neighboring pixels that have not yet been processed...
process; error-diffusion algorithms typically produce images that more closely represent the original than simpler dithering algorithms.
Dithering methods include:
- Thresholding (also average dithering): each pixel value is compared against a fixed threshold. This may be the simplest dithering algorithm there is, but it results in immense loss of detail and contouring.
- Random dithering was the first attempt (at least as early as 1951) to remedy the drawbacks of thresholding. Each pixel value is compared against a random threshold, resulting in a staticky image. Although this method doesn't generate patterned artifacts, the noise tends to swamp the detail of the image. It is analogous to the practice of mezzotintMezzotintMezzotint is a printmaking process of the intaglio family, technically a drypoint method. It was the first tonal method to be used, enabling half-tones to be produced without using line- or dot-based techniques like hatching, cross-hatching or stipple...
ing. - Patterning dithers using a fixed pattern. For every pixel in the image the value of the pattern at the corresponding location is used as a threshold. Neighboring pixels do not affect each other, making this form of dithering suitable for use in animations. Different patterns can generate completely different dithering effects.
- HalftoneHalftoneHalftone is the reprographic technique that simulates continuous tone imagery through the use of dots, varying either in size, in shape or in spacing...
dithering looks similar to halftone screening in newspapers. This is a form of clustered dithering, in that dots tend to cluster together. This can help hide the adverse effects of blurry pixels found on some older output devices. - Ordered ditheringOrdered ditheringOrdered dithering is an image dithering algorithm. It is commonly used by programs that need to provide continuous image of higher colors on a display of less color depth. For example, Microsoft Windows uses it in 16-color graphics modes...
produces a cross-hatch pattern. This is a form of dispersed dithering. Because the dots don't cluster, the result looks much less grainy. Though simple to implement, this dithering algorithm is not easily changed to work with free-form, arbitrary palettes.(Original) Threshold Random Halftone Bayer (ordered) 
- Halftone
- Error-diffusionError diffusionError diffusion is a type of halftoning in which the quantization residual is distributed to neighboring pixels that have not yet been processed...
dithering is a feedback process that diffuses the quantization error to neighbouring pixels.- Floyd–Steinberg dithering only diffuses the error to neighbouring pixels. This results in very fine-grained dithering.
- Jarvis, Judice, and Ninke dithering diffuses the error also to pixels one step further away. The dithering is coarser, but has fewer visual artifacts. It is slower than Floyd–Steinberg dithering because it distributes errors among 12 nearby pixels instead of 4 nearby pixels for Floyd–Steinberg.
- Stucki dithering is based on the above, but is slightly faster. Its output tends to be clean and sharp.
- Burkes dithering is a simplified form of Stucki dithering that is faster, but less clean than Stucki dithering.
Floyd–Steinberg Jarvis, Judice & Ninke Stucki Burkes 
- Error-diffusion dithering (continued):
- Sierra dithering is based on Jarvis dithering, but it's faster while giving similar results.
- Two-row Sierra is the above method modified by Sierra to improve its speed.
- Filter Lite is an algorithm by Sierra that is much simpler and faster than Floyd–Steinberg, while still yielding similar (according to Sierra, better) results.
- Atkinson dithering resembles Jarvis dithering and Sierra dithering, but it's faster. Another difference is that it doesn't diffuse the entire quantization error, but only three quarters. It tends to preserve detail well, but very light and dark areas may appear blown out.
- Even toned screening is a patentSoftware patentSoftware patent does not have a universally accepted definition. One definition suggested by the Foundation for a Free Information Infrastructure is that a software patent is a "patent on any performance of a computer realised by means of a computer program".In 2005, the European Patent Office...
ed modification of Floyd–Steinberg dithering intended to reduce visual artifacts, in particular to produce more even dot patterns in highlights and shadows.Sierra Two-row Sierra Sierra Lite Atkinson 
In optical fiber systems
Stimulated Brillouin ScatteringBrillouin scattering
Brillouin scattering, named after Léon Brillouin, occurs when light in a medium interacts with time dependent optical density variations and changes its energy and path. The density variations may be due to acoustic modes, such as phonons, magnetic modes, such as magnons, or temperature gradients...
(SBS) is a nonlinear optical effect
Nonlinear optics
Nonlinear optics is the branch of optics that describes the behavior of light in nonlinear media, that is, media in which the dielectric polarization P responds nonlinearly to the electric field E of the light...
that limits the launched optical power in fiber optic systems. This power limit can be increased by dithering the transmit optical center frequency, typically implemented by modulating the laser's bias input.
See also
- Digital audioDigital audioDigital audio is sound reproduction using pulse-code modulation and digital signals. Digital audio systems include analog-to-digital conversion , digital-to-analog conversion , digital storage, processing and transmission components...
- Quantization (signal processing)Quantization (signal processing)Quantization, in mathematics and digital signal processing, is the process of mapping a large set of input values to a smaller set – such as rounding values to some unit of precision. A device or algorithmic function that performs quantization is called a quantizer. The error introduced by...
- Anti-aliasingAnti-aliasingIn digital signal processing, spatial anti-aliasing is the technique of minimizing the distortion artifacts known as aliasing when representing a high-resolution image at a lower resolution...
- Lossy data compressionLossy data compressionIn information technology, "lossy" compression is a data encoding method that compresses data by discarding some of it. The procedure aims to minimize the amount of data that need to be held, handled, and/or transmitted by a computer...
External links
- "Dither - Not All Noise Is Bad"
- 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"
Both Nika Aldrich and Bob Katz
Bob Katz
Bob Katz is an audio mastering engineer who is known for his book on audio mastering. Katz has mastered three Grammy award-winning albums and one nominated album. He has received acclaim from audiophiles and his book on mastering has received acclaim, and some reviewers consider it the "definitive...
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"
- Dither Vibration Example
More recent research in the field of dither for audio was done by Lipshitz, Vanderkooy, and Wannamaker at the University of Waterloo
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
: