Error diffusion
Encyclopedia
Error diffusion is a type of halftoning
in which the quantization
residual is distributed to neighboring pixel
s that have not yet been processed. Its main use is to convert a multi-level image into a binary
image, though it has other applications.
Unlike many other halftoning methods, error diffusion is classified as an area operation, because what the algorithm does at one location influences what happens at other locations. This means buffering is required, and complicates parallel processing
. Point operations, such as ordered dither
, do not have these complications.
Error Diffusion has the tendency to enhance edges in an image. This can make text in images more readable than in other halftoning
techniques.
1790723 for his invention
, "Facsimile system." The patent, which issued in 1931, describes a system for transmitting image
s over telephone or telegraph lines, or by radio. Ranger's invention permitted continuous tone
photograph
s to be converted first into black and white, then transmitted to remote locations, which had a pen moving over a piece of paper. To render black, the pen was lowered to the paper; to produce white, the pen was raised. Shades of gray were rendered by intermittently raising and lowering the pen, depending upon the luminance
of the gray desired.
Ranger's invention used capacitors to store charges, and vacuum tube
comparators to determine when the present luminance, plus any accumulated error, was above a threshold (causing the pen to be raised) or below (causing the pen to be lowered). In this sense, it was an analog version of error diffusion.
images based on a simple kernel:
where "
" denotes a pixel in the current row which has already been processed (hence diffusing error to it would be pointless), and "#" denotes the pixel currently being processed.
Nearly concurrently, J F Jarvis, C N Judice, and W H Ninke of Bell Labs
disclosed a similar method which they termed "minimized average error," using a larger kernel:
In the discussion which follows, it is assumed that the number of quantization states in the error diffused image is two per channel, unless otherwise stated.
The current pixel is compared to a half-gray value. If it is above the value a white pixel is generated in the resulting image.
If the pixel is below the half way brightness, a black pixel is generated.
The generated pixel is either full bright, or full black, so there is an error in the image.
The error is then added to the next pixel in the image and the process repeats.
Two dimensional error diffusion reduces the visual artifacts.
The simplest algorithm is exactly like one dimensional error diffusion, except half the error is added to the next pixel, and one quarter of the error is added to the pixel on the next line below, and one quarter of the error is added to the pixel on the next line below and one pixel forward.
The kernel is:
where "#" denotes the pixel currently being processed.
Further refinement can be had by dispersing the error further away from the current pixel, as in the matrix given above in Enter the digital era. The sample image at the start of this article is an example of two dimensional error diffusion.
However, better visual results may be obtained by first converting the color channels into a perceptive color model that will separate lightness, hue and saturation channels, so that a higher weight for error diffusion will be given to the lightness channel, than to the hue channel. The motivation for this conversion is that human vision better perceives small differences of lightness in small local areas, than similar differences of hue in the same area, and even more than similar differences of saturation on the same area.
For example, if there is a small error in the green channel that cannot be represented, and another small error in the red channel in the same case, the properly weighted sum of these two errors may be used to adjust a perceptible lightness error, that can be represented in a balanced way between all three color channels (according to their respective statistical contribution to the lightness), even if this produces a larger error for the hue when converting the green channel. This error will be diffused in the neighboring pixels.
In addition, gamma correction
may be needed on each of these perceptive channels, if they don't scale linearly with the human vision, so that error diffusion can be accumulated linearly to these gamma-corrected linear channels, before computing the final color channels of the rounded pixel colors, using a reverse conversion to the native non gamma-corrected image format and from which the new residual error will be computed and converted again to be distributed to the next pixels.
It should also be noted that, due to limitations of precision during the numeric conversion between color models (notably if this conversion is not linear or uses non integer weights), additional roundoff errors may occur that should be taken into account into the residual error.
. Tone scale linearization may be applied to the source image to get the printed image to look correct.
make the next generated pixel be black. Dark to light transitions tend to result in the next
generated pixel being white. This causes an edge enhancement effect at the expense of gray level
reproduction accuracy. This results in error diffusion having a higher apparent resolution than
halftone
methods. This is especially beneficial with images with text in them such as the typical facsimile.
This effect shows fairly well in the picture at the top of this article. The grass detail and the text on the sign is well preserved,
and the lightness in the sky, containing little detail. A cluster-dot halftone
image of the same resolution would be much less sharp.
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...
in which the quantization
Quantization (image processing)
Quantization, involved in image processing, is a lossy compression technique achieved by compressing a range of values to a single quantum value. When the number of discrete symbols in a given stream is reduced, the stream becomes more compressible. For example, reducing the number of colors...
residual is distributed to neighboring 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 that have not yet been processed. Its main use is to convert a multi-level image into a binary
Binary file
A binary file is a computer file which may contain any type of data, encoded in binary form for computer storage and processing purposes; for example, computer document files containing formatted text...
image, though it has other applications.
Unlike many other halftoning methods, error diffusion is classified as an area operation, because what the algorithm does at one location influences what happens at other locations. This means buffering is required, and complicates parallel processing
Parallel processing
Parallel processing is the ability to carry out multiple operations or tasks simultaneously. The term is used in the contexts of both human cognition, particularly in the ability of the brain to simultaneously process incoming stimuli, and in parallel computing by machines.-Parallel processing by...
. Point operations, such as ordered dither
Dither
Dither is an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images...
, do not have these complications.
Error Diffusion has the tendency to enhance edges in an image. This can make text in images more readable than in other halftoning
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...
techniques.
Early history
Richard Howland Ranger received United States patentPatent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
1790723 for his invention
Invention
An invention is a novel composition, device, or process. An invention may be derived from a pre-existing model or idea, or it could be independently conceived, in which case it may be a radical breakthrough. In addition, there is cultural invention, which is an innovative set of useful social...
, "Facsimile system." The patent, which issued in 1931, describes a system for transmitting image
Image
An image is an artifact, for example a two-dimensional picture, that has a similar appearance to some subject—usually a physical object or a person.-Characteristics:...
s over telephone or telegraph lines, or by radio. Ranger's invention permitted continuous tone
Continuous tone
A continuous tone image is one where each color at any point in the image is reproduced as a single tone, and not as discrete halftones, such as one single color for monochromatic prints, or a combination of halftones for color prints....
photograph
Photograph
A photograph is an image created by light falling on a light-sensitive surface, usually photographic film or an electronic imager such as a CCD or a CMOS chip. Most photographs are created using a camera, which uses a lens to focus the scene's visible wavelengths of light into a reproduction of...
s to be converted first into black and white, then transmitted to remote locations, which had a pen moving over a piece of paper. To render black, the pen was lowered to the paper; to produce white, the pen was raised. Shades of gray were rendered by intermittently raising and lowering the pen, depending upon the luminance
Luminance
Luminance is a photometric measure of the luminous intensity per unit area of light travelling in a given direction. It describes the amount of light that passes through or is emitted from a particular area, and falls within a given solid angle. The SI unit for luminance is candela per square...
of the gray desired.
Ranger's invention used capacitors to store charges, and vacuum tube
Vacuum tube
In electronics, a vacuum tube, electron tube , or thermionic valve , reduced to simply "tube" or "valve" in everyday parlance, is a device that relies on the flow of electric current through a vacuum...
comparators to determine when the present luminance, plus any accumulated error, was above a threshold (causing the pen to be raised) or below (causing the pen to be lowered). In this sense, it was an analog version of error diffusion.
Enter the digital era
Floyd and Steinberg described a system for performing error diffusion on digitalDigital
A digital system is a data technology that uses discrete values. By contrast, non-digital systems use a continuous range of values to represent information...
images based on a simple kernel:
where "
" denotes a pixel in the current row which has already been processed (hence diffusing error to it would be pointless), and "#" denotes the pixel currently being processed.Nearly concurrently, J F Jarvis, C N Judice, and W H Ninke of Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
disclosed a similar method which they termed "minimized average error," using a larger kernel:
Algorithm Description
Error diffusion takes a monochrome or color image and reduces the number of quantization levels. A popular application of error diffusion involves reducing the number of quantization states to just two per channel. This makes the image suitable for printing on binary printers such as black and white laser printers.In the discussion which follows, it is assumed that the number of quantization states in the error diffused image is two per channel, unless otherwise stated.
One-dimensional error diffusion
The simplest form of the algorithm scans the image one row at a time and one pixel at a time.The current pixel is compared to a half-gray value. If it is above the value a white pixel is generated in the resulting image.
If the pixel is below the half way brightness, a black pixel is generated.
The generated pixel is either full bright, or full black, so there is an error in the image.
The error is then added to the next pixel in the image and the process repeats.
Two-dimensional error diffusion
One dimensional error diffusion tends to have severe image artifacts that show up as distinct vertical lines.Two dimensional error diffusion reduces the visual artifacts.
The simplest algorithm is exactly like one dimensional error diffusion, except half the error is added to the next pixel, and one quarter of the error is added to the pixel on the next line below, and one quarter of the error is added to the pixel on the next line below and one pixel forward.
The kernel is:
where "#" denotes the pixel currently being processed.
Further refinement can be had by dispersing the error further away from the current pixel, as in the matrix given above in Enter the digital era. The sample image at the start of this article is an example of two dimensional error diffusion.
Color error diffusion
The same algorithms may be applied to each of the red, green, and blue (or cyan, magenta, yellow, black) channels of a color image to achieve a color effect on printers such as color laser printers that can only print single color values.However, better visual results may be obtained by first converting the color channels into a perceptive color model that will separate lightness, hue and saturation channels, so that a higher weight for error diffusion will be given to the lightness channel, than to the hue channel. The motivation for this conversion is that human vision better perceives small differences of lightness in small local areas, than similar differences of hue in the same area, and even more than similar differences of saturation on the same area.
For example, if there is a small error in the green channel that cannot be represented, and another small error in the red channel in the same case, the properly weighted sum of these two errors may be used to adjust a perceptible lightness error, that can be represented in a balanced way between all three color channels (according to their respective statistical contribution to the lightness), even if this produces a larger error for the hue when converting the green channel. This error will be diffused in the neighboring pixels.
In addition, 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...
may be needed on each of these perceptive channels, if they don't scale linearly with the human vision, so that error diffusion can be accumulated linearly to these gamma-corrected linear channels, before computing the final color channels of the rounded pixel colors, using a reverse conversion to the native non gamma-corrected image format and from which the new residual error will be computed and converted again to be distributed to the next pixels.
It should also be noted that, due to limitations of precision during the numeric conversion between color models (notably if this conversion is not linear or uses non integer weights), additional roundoff errors may occur that should be taken into account into the residual error.
Error diffusion with several gray levels
Error Diffusion may also be used to produce output images with more than two levels (per channel, in the case of color images). This has application in displays and printers which can produce 4, 8, or 16 levels in each image plane, such as electrostatic printers and displays in compact mobile telephones. Rather than use a single threshold to produce binary output, the closest permitted level is determined, and the error, if any, is diffused as described above.Printer considerations
Most printers overlap the black dots slightly so there is not an exact one-to-one relationship to dot frequency (in dots per unit area) and lightnessLightness (color)
Lightness is a property of a color, or a dimension of a color space, that is defined in a way to reflect the subjective brightness perception of a color for humans along a lightness–darkness axis. A color's lightness also corresponds to its amplitude.Various color models have an explicit term for...
. Tone scale linearization may be applied to the source image to get the printed image to look correct.
Edge enhancement versus lightness preservation
When an image has a transition from light to dark the error diffusion algorithm tends tomake the next generated pixel be black. Dark to light transitions tend to result in the next
generated pixel being white. This causes an edge enhancement effect at the expense of gray level
reproduction accuracy. This results in error diffusion having a higher apparent resolution than
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...
methods. This is especially beneficial with images with text in them such as the typical facsimile.
This effect shows fairly well in the picture at the top of this article. The grass detail and the text on the sign is well preserved,
and the lightness in the sky, containing little detail. A cluster-dot 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...
image of the same resolution would be much less sharp.