Error diffusion is a type of
halftoning
Halftone is the reprographic technique that simulates continuous-tone imagery through the use of dots, varying either in size or in spacing, thus generating a gradient-like effect.Campbell, Alastair. The Designer's Lexicon. ©2000 Chronicle, ...
in which the
quantization residual is distributed to neighboring
pixel
In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device.
In most digital display devices, pixels are the ...
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
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 video data, and is often ...
, 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 is the reprographic technique that simulates continuous-tone imagery through the use of dots, varying either in size or in spacing, thus generating a gradient-like effect.Campbell, Alastair. The Designer's Lexicon. ©2000 Chronicle, ...
techniques.
Early history
Richard Howland Ranger
Richard Howland Ranger (13 June 1889 – 10 January 1962) was an American electrical engineer, music engineer and inventor. He was born in Indianapolis, Indiana, the son of John Hilliard and Emily Anthen Gillet Ranger, He served in the U.S. Ar ...
received United States
patent
A patent is a type of intellectual property that gives its owner the legal right to exclude others from making, using, or selling an invention for a limited period of time in exchange for publishing an enabling disclosure of the invention."A ...
1790723 for his
invention
An invention is a unique or novel device, method, composition, idea or process. An invention may be an improvement upon a machine, product, or process for increasing efficiency or lowering cost. It may also be an entirely new concept. If an ...
, "Facsimile system." The patent, which issued in 1931, describes a system for transmitting
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
s over telephone or telegraph lines, or by radio.
[Richard Howland Ranger, Facsimile system. United States Patent 1790723, issued 3 February 1931.] Ranger's invention permitted
continuous tone
A continuous tone image (contone for short, or CT even shorter) 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 ...
photograph
A photograph (also known as a photo, image, or picture) is an image created by light falling on a photosensitive surface, usually photographic film or an electronic image sensor, such as a CCD or a CMOS chip. Most photographs are now create ...
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
Grey (more common in British English) or gray (more common in American English) is an intermediate color between black and white. It is a neutral or achromatic color, meaning literally that it is "without color", because it can be compose ...
were rendered by intermittently raising and lowering the pen, depending upon the
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, is emitted from, or is reflected from a particular area, and falls with ...
of the gray desired.
Ranger's invention used capacitors to store charges, and
vacuum tube
A vacuum tube, electron tube, valve (British usage), or tube (North America), is a device that controls electric current flow in a high vacuum between electrodes to which an electric potential difference has been applied.
The type known as ...
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
Analog or analogue may refer to:
Computing and electronics
* Analog signal, in which information is encoded in a continuous variable
** Analog device, an apparatus that operates on analog signals
*** Analog electronics, circuits which use analog ...
version of error diffusion.
Digital era
Floyd and Steinberg described a system for performing error diffusion on
digital
Digital usually refers to something using discrete digits, often binary digits.
Technology and computing Hardware
*Digital electronics, electronic circuits which operate using digital signals
** Digital camera, which captures and stores digital ...
images based on a simple kernel:
: