4-
Model-based halftoning
We present a halftoning technique which searches for a halftone which minimizes a global measure of error based
on models of the human visual system (can also include a model of the output
printer, but we consider only displays). The halftone which minimizes the
error is found iteratively. The interest of this approach is not a practical
application, because the computational cost is discouraging. However, such
searches for optimality are theoretically very useful, because they allow
us to see how far we are from the optimum, with different methods.
We have implemented a computationally efficient (takes only a few minutes
and about 12 passes over the image to find an optimum on matlab for a 256x256
grayscale image) algorithm using direct binary search. The DBS algorithm proceeds
by transforming an initial halftone into one which locally minimizes the visual
model response to the color image. Since this minimum is local, it is not
unique, and an important drawback of this method is that the result is dependent
on the starting point.
Let’s start with the description of the algorithm : the global
mean squared error between the perceived halftone image and the perceived
original image is computed. We model the low pass characteristic of the eye
with a luminance spatial frequency response function (model by Daly)
We compute this error efficiently by computing first the autocorrelation
function of the filter, Cpp and the correlation between the error
and the filter, Cpe. As explained in [], the error is a function
of those two. Each time we try a change, we can evaluate the consequences
of this change on the error by using only four values of these matrix. If
the change we tried effectively reduces the error, then it is accepted, and
this time we need to change as many values of Cpe as there are
values in Cpp. This is acceptable though, because especially in
the last passes over the image, we try much more changes than the number we
accept.
This way, the process scans the image, for each pixel it tries both changing
the value of this pixel, or swaping it with one of its neighbours. If the
error decreases, the change is validated, the error is updated, and it proceeds
to the next pixel.
It keeps scanning the image until the error decreases less than 0.1 % in
an entire image scan.
We consider then that a local minimum has been found.
We can visualize in figure X the evolution of the error as a function of
time, with different starting points, reaching different stable points (local
optima)
We show several plots of the result for our test images.
The reader should note that the algorithm only ensures convergence toward
a local minimum, with varying performance depending on the starting point.
This is illustrated in the following plot
|
|
|
|
|
Starting point : Blue noise mask (7 cycles to converge) |
Starting point : Bayer matrix ( 6 cycles to converge) |
Starting point : Error diffusion (4 cycles to converge) |
The grid on the images is due to the scaling performed by the softwares.
To view the real image, you should download it and display it with your favorite
viewer.
Let’s look at the generalization of this procedure for color images : Once
again, the data we have to work with has to be expressed in terms of the visual
pathways, which have different modulation transfer functions (low pass for
the luminance, very low pass for the opponent channels)
We have to compute the following linear transformation :
in order to have the image in the color space we want, and then filter the
three channels independently with
the contrast sensitivity functions, for both the original and halftoned image,
and take the mean squared error of those two. This gives us our error measure.
The algorithm will have to be modified a little bit, but we should still
be able to exploit most of the low complexity ideas her.