2-
Frequency domain investigation and Blue Noise
Representing signals in the frequency domain can often simplify complexity
seen in the spatial domain. This is indeed the case with dither patterns.
It allows us a mean to examine the distribution of energy and its consequences
on the quality of the patterns. As it is the flat regions of an image where
the nature of dither is most important, the focus will be on the power spectrum
of patterns that result from the dithering of a single fixed gray level. The
DC or frequency center point contributes to the macroscopic average, or gray
level, of the dither pattern. As this datum is already known, it contributes
to nothing to aiding our interpretation of the nature of the distribution
of pixels that make up the dither pattern, and so is omitted in resulting
plots.
This turns out to be equivalent to the power spectrum of the quantization
error between the original image and the dithered one, because for a uniform
gray level image, they are scaled versions of one another.
However two dimensional spectral plots can also afford to be made more succinct.
Most well formed patterns share the characteristic of being isotropic. This
leads to a metric that summarizes the spectrum radially. Figure X shows the segmenting of a spectral
period into concentric annuli. Averaging the power spectrum in each annulus
results in a radially averaged power spectrum, where these averages are plotted
against the radial frequency, the radial distance from the DC center point
of the annulus. As with the horizontal or vertical spatial frequency, this
radial frequency is in units of inverse spatial sample periods.
Tadial frequency can go as high as 1/√2 at the high frequency corners
; these high frequency corners correspond to a checkerboard pattern, the highest
2-D pattern possible.
The power spectrum also needs to be normalized for the gray level g, which
we will specify as ranging grom g=0 (black) to g=1 (white). Spectral energy
increases as the number of minority pixels in a bitonal pattern increases,
peaking at g=0.5, and so the spectral values are divided by the gray level
variance.
Figure X shows the measured radially averaged power spectrum for white noise
patterns. Using the normalization described above, we can plot the spectra
for different gray levels on the same plot, and compare them.
The spatial contrast sensitivity function is shown in Figure X
In order for the quantization error to be perceived as little as possible,
we see that we must avoid frequency components in the low frequencies, because
the high frequencies are not perceived by the human vision.
The viewing distance is related to the width of the CSF, and we can relate
the viewing distance to the principal frequency at a particular gray level
in the case of Bayer dithering to determine how far we have to be from a display
not to see the artefacts.
This acknowledges the optimality of the
Bayer dithering matrix among all ordered dither matrices. However, the structured
natured of this is reflected in the spike in the spectrum at the end of the
range, for all gray levels.
The kind of spectrum we are looking for is often referred to in the literature
as “blue noise”. Ideally, a well-formed dither pattern should have the unstructured
nature of white noise without the low frequency components.
I describe now the process for building a blue noise
mask, along with the result of my experiments.
A blue noise mask is a template, usually of smaller size than the image
(which doesn’t introduce any problem since it is built with wrap-around properties,
as we shall see). A blue noise mask is independent from the image to be halftoned.
We want to design a matrix with coefficients ordered in the order according
to which the pixels are to be turned on, as the gray level increases. The
mask can be viewed as a collection of dot profiles, the binary matrices obtained
by thresholding the mask with a certain gray level g, for all values of the
gray level.
The dot profiles have to be related to one another, and the relationship
can be expressed in this way : the dot profile for a gray level g1>g2
is to be designed from the dot profile of g2 such that all pixels
turned on in the first dot profile are also turned on in the second. This
condition cannot be explained by spectral consideration, because we have only
properties for the spectrum of a fixed gray level. However we can understand
it the following way : If two different gray levels are present in an image,
the boundary between those should not introduce any discontinuities in the
dot repartition. Thus, the profiles of the higher gray level should be include
the dots presents in the lower one.
The actual mask design comprises
three main phases. First, we design a dot pattern for a certain
gray level, which is arbitrary, but presents the characteristics of blue noise.
To do this, I started with a white noise pattern, and improved it to get
blue noise by moving the pixels one at a time, from a very dense region, to
the less dense. I have used a gaussian filter to detect high and low densities.
Then we have to iteratively generate the dot profiles for the
other gray levels. From our starting point, we first generate the ones corresponding
to the gray levels below the first one, and then the ones above it, both starting
from the initial blue noise pattern. For both ways, I still use my void/cluster finding filter.
I believe the size of the mask should be
chosen in relation to the average area of uniform gray levels, such that we
never see any regular pattern reproduced across the image. What that means
is that we have to relate the spectrum of the original image to the spectrum
of the quantization error in some way.
