Due to freedoms afforded by digital printers, the idea of printing isolated pixels in an effort to minimize halftone visibility (the visibility of the individual dots to a human viewer) emerged as an alternative to clustered-dot dithering. By maintaining the size of printed dots for all gray levels as individual pixels, new dispersed-dot halftoning techniques varied, according to tone, the spacing between printed dots, earning the name frequency modulated or FM halftoning. Early FM halftoning techniques were proposed by Bayer [9] and Bryngdahl [10] and produced an ordered arrangement of isolated dots. These techniques, like AM halftoning schemes, quantized each pixel independently of its neighbors (point process) according to a dither array but with consecutive thresholds dispersed as much as possible. The problem associated with these early FM techniques is that, as in the case of Bayer's dither array (Fig. 3.1 (left)), resulting halftoned images (Fig. 3.1 (right)) suffered from a periodic structure that added an unnatural appearance [11].
3.1 What is error diffusion?
For a better approach to FM halftoning, Floyd and Steinberg [12] proposed error diffusion (Fig. 3.2) as an adaptive technique that quantized each pixel according to a statistical analysis of an input pixel and its neighbors, leading to a stochastic arrangement of printed dots. While this neighborhood process had higher computational complexity, the resulting patterns had apparent spatial resolutions much higher than those achieved by clustered dots (Fig. 3.3); furthermore, as a stochastic patterning of dots, the patterns eliminated the occurrence of the moire that was produced by the superimposing of two or more regular patterns.
Figure 3.2 The error diffusion algorithm.
In error diffusion, each input pixel,
, is processed one at a time usually in a left-to-right, row-by-row scanning path. The output pixel
is determined by adjusting and thresholding the input pixel such that:
where
is the diffused quantization error accumulated during previous iterations as:
with
and
. Using vector notation,
can be expressed as:
where
and
. For the error filter
, Floyd and Steinberg proposed the kernel of Fig. 3.4.
Figure 3.3 Grayscale image halftoned using Floyd's and Steinberg's error diffusion algorithm.
Figure 3.4 Floyd and Steinberg’s original four-weight error filter kernel.
Anastassiou [13] noted that error diffusion was a 2D instance of delta-sigma modulation, and as such, Weissbach
et al [14] showed that the power spectrum,
, of the output image of error diffusion was related to the power spectrums,
and
, of the input and error images as:
where:
is a high-pass filter (assuming
was low-pass) derived from the 2D discrete Fourier transform of the error filter. Knox [15] later showed that the error image was not white-noise but was strongly correlated with the input image and even contained a linear component of the input image. Being that
was a high-pass filter meant that
contained an additional high-pass version of the input image
. It is due to the relationship between
and
that error diffusion is considered to be an inherently high-pass filter operation, but even so, edge sharpening is a common operation applied to an image prior to halftoning with error diffusion [16].
3.2 What is blue noise?
What is so appealing about the dither patterns created by error diffusion is that they are composed exclusively of high frequency spectral components. Based on the sensitivity of the human visual system to low-frequency graininess, error diffusion creates halftone patterns far superior to AM halftoning or Bayer's dither, exhibiting much higher spatial detail without adding perceptually disturbing or artificial textures. Ulichney [11] describes these dither patterns, produced by error diffusion, as
blue-noise where for a given gray level
, the ideal pattern has minority pixels separated in an isotropic manner by an average distance of
, the blue-noise
principle wavelength, such that
where
is the minimum distance between addressable points on the display. The resulting power spectrum then has spectral components with frequencies greater than or equal to
, the blue-noise
principal frequency, such that
Ulichney uses the term “blue” as a reference to the high frequency spectral components of white light. The term “noise” refers to the randomness of the patterns.
Figure 3.3 The minority pixels of blue-noise separated by an average distance of
.
To statistically characterize the spatial arrangement of dots in a blue-noise pattern, Lau
et al [17] suggest relying on the spatial and spectral statistics developed for point processes. In this framework, a point process,
, is a statistical model governing the location of points in
(2-D real space). A sample set,
, of
is then noted as the set of points
, but for some area
is a scalar quantity equal to the number of
's in
. To relate the framework to digital halftoning, Lau
et al define error diffusion as a point process with a binary dither pattern,
, representing gray level
defining a sample set
such that
indicates that the pixel
is a minority pixel (a white pixel on a black background or a black pixel on a white background).
Figure 3.4 Diagram illustrating the point process
, a sample
of the process, and the scalar quantity
as a function of the subset
of
.
The quantity
is a scalar random variable that can be characterized in terms of its moments. The first-order moment or the expected value of
is referred to as the
intensity , and its relationship to the gray level
is defined as:
For a point process to be
stationary, the statistical characteristics of
must be invariant to translation. If a process is stationary, then the intensity is constant for all
where
is the unconditional probability that the sample at location
is a minority pixel.
Additional insight into
is gained by conditioning the probability distribution of
given that a point lies at a given location. The result is a conditional distribution referred to as the
Palm distribution [18]. A particular measure under the Palm distribution of
is the quantity
:
the ratio of conditional probability that a minority pixel exists at
given that a minority pixel exists at
to the unconditional probability that a minority pixel exists at
.
, referred to as the
reduced second moment measure, may be thought of as the influence of a minority pixel at
on the pixel
. That is, is a minority pixel at
more or less likely to occur because a minority pixel exists at
? If
, then the likelihood of a minority pixel at
is increased relative to
while
indicates the likelihood is decreased.
Figure 3.5 A (left) blue-noise dither pattern with its corresponding (center) reduced second moment measure
and (right) power spectrum estimate
.
For stationary processes,
may be written as
where
is the distance between
and
and
is the direction to
from
. For a point process to be
isotropic, the statistical characteristics of
must be invariant to rotation; therefore, if
is also isotropic, then
. The quantity
is commonly referred to as the
pair correlation,
, defined explicitly as:
the ratio of the expected number of minority pixels located in the ring
under the condition that
is a minority pixel to the unconditional expected number of minority pixels located in
.
In view of Fig. 3.5, blue-noise halftones are characterized in terms of the pair correlation
by noting that: (1) few or no neighboring pixels lie within a radius of
; (2) for
, the expected number of minority pixels per unit area approaches
with increasing
; and (3) the average number of minority pixels within the radius
increases sharply near
. The resulting pair correlation for blue-noise is therefore of the form in Fig. 3.6 (top) where
shows: (a) a strong inhibition of minority pixels near
, (b) a decreasing correlation of minority pixels with increasing
, and (c) a frequent occurrence of the inter-point distance
, the principle wavelength, indicated by a series of peaks at integer multiples of
. The principle wavelength is indicated in Fig. 3.6 (top) by a diamond located along the horizontal axis.
Figure 3.6 The (top) pair correlation and (bottom) RAPSD of the ideal blue-noise pattern with principal wavelength
and corresponding principal frequency
.
In the spectral domain, blue-noise halftones are characterized by the
radially averaged power spectral density (RAPSD),
, defined as:
the average power within a series of annular rings,
, that partition the spectral domain where
is the number of frequency samples in the annular ring
with center radius
[11].
is the power spectrum estimate of the point process,
, calculated using Bartlett's method of averaging periodograms [19] such that:
where
represents the two dimensional, discrete Fourier transform of the sample
,
is the total number of pixels in the sample
, and
is the total number of periodograms being averaged to form the estimate.
Shown in Fig. 3.6 (bottom) is the RAPSD of the ideal blue-noise pattern -- showing three distinct features: (a) little or no low frequency spectral components, (b) a flat, high frequency (blue-noise) spectral region and (c) a spectral peak at cutoff frequency
. Ulichney notes that blue-noise dither patterns are better than white-noise (where
for all
) due to the absence of any spectral components in the range
. Comparing any two halftoning algorithms, the visually preferred is the one that minimizes the amount of spectral content that exists at frequencies below
.
Figure 3.7 Jarvis's, Judice's, and Ninke's proposed error filter.
Figure 3.8 Stucki's proposed error filter.
Noting the gray-scale ramps of Fig. 3.9, Floyd's and Steinberg's error diffusion is clearly not the ideal blue-noise halftoning algorithm due to strong diagonal correlations are extreme gray levels (
near 0 and 1) and due to periodic textures at
near multiples of 1/4 and 1/3. In light of these artifacts, many modifications to Floyd's and Steinberg's original algorithm have since been introduced. The earliest modifications involved new error filters. Shown in Fig. 3.7 and 3.8 are the Jarvis
et al [20] and the Stucki [21] filters with their corresponding gray-scale ramps shown in Fig. 3.9 (b) and (c).
(a) Floyd's and Steinberg's error filter
(b) Jarvis's, Judice's, and Ninke's error filter
(c) Stucki's error filter
(d) Floyd's and Steinberg's error filter with a serpentine raster scan
(e) Ulichney's perturbed filter weight scheme
Figure 3.9 The halftoned gray-scale ramps produced using several variations of error diffusion.
A second approach to modifying error diffusion involved the raster scanning order to which pixels of the input image were processed. Using a serpentine left-to-right and then right-to-left scanning order (Fig. 3.9 (d)) breaks up many of the artifacts found using Floyd's and Steinberg's filter weights near gray level 1/3 and also alleviates some the hysteresis artifacts found near extreme gray levels [11]. Other more radical approaches to raster scans include the use of space-filling curves such as the Hilbert or Peano curves [22].
A third approach to modifying error diffusion, that was first proposed by Ulichney [16], involved randomizing the error-filter weights at each pixel. Specifically, Ulichney prescribed grouping the filter weights into pairs such that weights of similar value where paired together. Ulichney would then add a random value to one member of the pair, subtracting the same value from the other member. In this way, the weights would always sum to 1. To avoid negative filter weights, the maximum magnitude to the random value would be a percentage (like 50%) of the smaller of the two weights within a pair. Shown in Fig. 3.9 (e) is the gray-scale ramp created using Floyd's and Steinberg's filter (paired as 1/16 with 3/16 and 5/16 with 7/16) with a 50% maximum perturbation value.
For a completely different approach to halftoning that generates very pleasing dither patterns, Analoui and Allebach [23] introduced direct binary search (DBS) as to obtain the absolute best arrangement of binary dots for representing a continuous tone image. DBS is an optimization routine that iteratively processes each pixel of the binary image, one at at time, by either swapping the current pixel with one of its eight nearest neighbors or toggling the bit from 1 to 0 or 0 to 1 according to the modeled visual cost between the binary image and the continuous-tone original. If neither a swap nor a toggle reduces the overall visual cost, then the pixel is left unchanged. The algorithm quits when after processing the entire halftoned image, no swaps or toggles occur. Being a steepest descent type optimization, DBS is susceptible to local minimum extrema, and the quality of the final halftone image is affected by the initial or seed dither pattern.
3.3 What is threshold modulation?
Threshold modulation with low level white-noise was also proposed by Ulichney and carried a lower computational cost than modulating multiple error filter weights. This technique was later shown by Eschbach and Knox [24] to be equivalent to adding high-pass filtered white-noise to the input image prior to halftoning. While the resulting halftone patterns did not show any great improvement in their blue-noise characteristics, threshold modulation became a very powerful tool for edge sharpening. Eschbach and Knox showed that modulating the threshold by a scalar multiple of the current input pixel created a halftoned image with sharper edges. They showed that varying the threshold of error diffusion by the function
was equivalent to applying ordinary error diffusion to the input image
where:
If
(a scalar multiple of the current input pixel), then
is equivalent to adding a high-pass version of
to itself prior to halftoning -- leading to sharper edges in the apparent image
. Figure 3.10 shows the resulting halftone images produced by Floyd's and Steinberg's error diffusion on a serpentine raster scan with Knox's and Eschbach's threshold modulation where
= 0 and 3.
Figure 3.10 The gray-scale images produced using Floyd's and Steinberg's error filter with a serpentine raster scan illustrating threshold modulation for edge enhancement with (left)
= 0 and (right)
= 3.
3.4 What are blue noise dither arrays?
A real drawback for error diffusion is its computational complexity. Being a neighborhood operation, error diffusion requires additional storage for intermediate error terms [25]. So a novel advancement in halftoning that evolved from Ulichney's blue-noise model is Void-and-Cluster and blue-noise dither arrays -- dither arrays constructed to produce dither patterns that closely imitate those produced by error diffusion. While typically much larger than those of AM halftoning (128 by 128 or 256 by 256 versus 8 by 8 or 16 by 16), these masks are employed in the exact same manner as clustered-dot ordered dither arrays. Shown in Fig. 3.11 is a sample mask, produced by Void-and-Cluster, and its corresponding halftoned image.
Figure 3.11 A (left) 128 by 128 blue-noise mask and (right) its corresponding gray-scale image.
