Halftoning Research at HP Labs

Digital image halftoning is the process of reducing the bit-depth of an  image for display on devices capable of reproducing smaller number of graylevels than those present in the original high bit-depth (a.k.a. continuous-tone image) image. Image halftoning takes advantage of the spatial averaging of the human eye to distribute the quantization error in such a way that the reduced bit-depth image is visually close to the continuous-tone image as possible. The classic example  is a bi-level printer that is capable of either placing a dot of ink/toner on the paper or not (hence the word halftone). Printed images that appear to have continuous shades are created by an ingenious spatial distribution of dots using a halftoning algorithm. Halftoning theory is used in a number of image rendering systems such as printers, projectors and displays.

The challenge in image halftoning is to tailor the halftoning algorithm to a rendering device in order to optimize the output quality. For example, inkjet printers are able to reproduce isolated printer dots very well and could also allow multiple drops of ink at the same location. Laser printers require dot-clusters for a stable printing process. They also allow modification of the pulse width of lasers to produce dots of different sizes (this process is called pulse width modulation, a.k.a PWM). Artifacts due to the interactions among color planes and due to printing process imperfections are also key concerns. A good halftoning algorithm must utilize such information to deliver output that is of high visual quality.

Conventional halftoning relies on dot size modulation (a.k.a. amplitude modulation (AM)) to reproduce tones since the dot centers are laid out on a fixed grid. The dot sizes increase to represent a darker tone and decrease to represent a lighter tone. Halftoning methods that use a fixed dot size (of typically one pixel) and modulate the density or frequency of the dots to reproduce continuous-tone are called FM (frequency modulation) methods. Thus the dots get closer together to represent a darker tone and further apart to represent a lighter tone. Halftones generated by FM halftoning methods are refered to as blue-noise halftones since their pattern power spectra are concentrated in the high-frequencies.  AM-FM halftones (a.k.a green-noise halftones) are hybrid halftones that aim to achieve a balance that takes advantage of the desirable qualities of both AM and FM halftones.

Selected HP Labs published contributions

1.   Theory of blue-noise halftoning

2.    The void and cluster method for dither array generation

3.    ColorSmooth dither

4.    Image Resolution Enhancement Technology (IRET)

5.    ImageSmart halftoning

6.    Error diffusion with minimum brighness variation

7.  Theory of donut filters for optimal AM-FM screening

Contact:
For more information about halftoning research at HP Labs, please e-mail Qian Lin (qian.lin@hp.com), Robert Ulichney (bob.ulichney@hp.com) or Niranjan Damera-Venkata (niranjan.damera-venkata@hp.com)