Error diffusion


Error diffusion

Error diffusion is a type of halftoning in which the quantization residual is distributed to neighboring pixels which 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.

Early history

Richard Howland Ranger received United States patent 1790723 for his invention, "Facsimile system." The patent, which issued in 1931, describes a system for transmitting images 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 photographs 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.

Enter the digital era

Floyd and Steinberg described a system for performing error diffusion on digital images based on a simple kernel:

: frac{1}{16}left [egin{array}{ccccc}- & # & 7 \ 3 & 5 & 1 end{array} ight]

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: J F Jarvis, C N Judice, and W H Ninke, A survey of techniques for the display of continuous tone pictures on bilevel displays. "Computer Graphics and Image Processing," 5:1:13-40 (1976).]

: frac{1}{48}left [egin{array}{ccccc}- & - & # & 7 & 5 \ 3 & 5 & 7 & 5 & 3 \ 1 & 3 & 5 & 3 & 1 end{array} ight]

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:: frac{1}{4}left [egin{array}{cc} # & 2 \ 1 & 1 end{array} ight]

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.

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 lightness. Tone scale linearization may be applied to the source image to get the printed image to look correct.

Edge Enhancement vs. Lightness Preservation

When an image has a transition from light to dark the error diffusion algorithm tends to make the next generated pixel be black. Dark to light transitions tend to result in the nextgenerated pixel being white. This causes an edge enhancement effect at the expense of gray levelreproduction 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.

ee also

Halftone

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Diffusion (disambiguation) — Diffusion is a time dependent random process causing a spread in space. Diffusion may also refer to: In physical sciences Molecular diffusion, spontaneous dispersion of mass (distinct from migration, caused by an external force) Conduction of… …   Wikipedia

  • Diffusion Monte Carlo — (DMC) is a quantum Monte Carlo method that uses a Green s function to solve the Schrödinger equation. DMC is potentially numerically exact, meaning that it can find the exact ground state energy within a given error for any quantum system. When… …   Wikipedia

  • error-function diffusion — difuzija pagal paklaidų funkciją statusas T sritis radioelektronika atitikmenys: angl. error function diffusion vok. Fehlerfunktionsdiffusion, f rus. диффузия в соответствии с функцией ошибок, f pranc. diffusion en fonction d erreurs, f …   Radioelektronikos terminų žodynas

  • diffusion en fonction d'erreurs — difuzija pagal paklaidų funkciją statusas T sritis radioelektronika atitikmenys: angl. error function diffusion vok. Fehlerfunktionsdiffusion, f rus. диффузия в соответствии с функцией ошибок, f pranc. diffusion en fonction d erreurs, f …   Radioelektronikos terminų žodynas

  • Radiative transfer equation and diffusion theory for photon transport in biological tissue — Photon transport in biological tissue can be equivalently modeled numerically with Monte Carlo simulations or analytically by the radiative transfer equation (RTE). However, the RTE is difficult to solve without introducing approximations. A… …   Wikipedia

  • Fick's laws of diffusion — For the technique of measuring cardiac output, see Fick principle. Molecular diffusion from a microscopic and macroscopic point of view. Initially, there are solute molecules on the left side of a barrier (purple line) and none on the right. The… …   Wikipedia

  • Fick's law of diffusion — Fick s laws of diffusion describe diffusion and can be used to solve for the diffusion coefficient D . They were derived by Adolf Fick in the year 1855. First law Fick s first law relates the diffusive flux to the concentration field, by… …   Wikipedia

  • Dither — For other uses, see Dither (disambiguation). Provincial definition of to dither from The Rural Economy of Yorkshire: Comprizing the Management of Landed Estates, and the Present Practice of Husbandry in the Agricultural Districts of that County,… …   Wikipedia

  • Floyd-Steinberg dithering — is an image dithering algorithm first published in 1976 by Robert W. Floyd and Louis Steinberg. It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restricted to a maximum of 256… …   Wikipedia

  • Rounding — This article is about numerical rounding. For lip rounding in phonetics, see Labialisation. For other uses, see Rounding (disambiguation). Rounding a numerical value means replacing it by another value that is approximately equal but has a… …   Wikipedia