Halftoning is a process of transforming a gray scale image to a halftone (only black
and white). It creates the illusion of gray-scale by varying the average dot density in
local regions of images. Halftoning takes the advantage of the fact that eyes integrate
intensity of small image regions as in Fig.1.6. However, spatial resolution must be
sacrificed (output image will be larger than the original), which refers to image
itself based on direct manipulation pixels, for gray-scale resolution unless the output
device can be over-sampled as most ink-jet printers.
A gray scale image is transformed to a halftoned image in the domain of printing
media by using physical filters, lights, and film. The illusion of gray scale is obtained
by varying sizes and shapes of ink dots. However, digital halftoning cannot be done
this way since digital images consist of identically shaped pixels, which is either
black or white. The main problem is to decide whether this pixel should be white or
black.
Now, consider the solutions of digital halftoning consisting of bi-level thresholding
and font/pattern replacement.
Bi-level Thresholding: Bi-level thresholding requantizes an image using one bit
color. If the gray-scale of a pixel is less than some threshold value, then set the
output to be black otherwise set the output to be white. Fig.1.8 shows the process of
the bi-level thresholding method, when the bi-level thresholding process is applied
for gray scale images with the range from zero to 255. Fig.1.8 shows the diagram of
bi-level thresholding.
A key parameter of bi-level thresholding is a threshold value. There are several
ways in deriving a threshold. The threshold value may be the center of available gray
scale range. For example, if the gray scale range is from zero to 255, a threshold
value can be set to 128. Pixel values that are higher than 128 will be set to 255,
whereas pixel values that are lower than or equal to 128 will be set to zero. The
threshold can be also set as an average of all pixels in an image or the average of the
maximum and minimum value of gray scale pixels in an image. For example, if the
maximum and minimum values of gray scale pixels are 200 and 100, respectively,
then the threshold is set to be 150. Moreover, the threshold can be set adaptively
based on the local values of pixels. For example, gray scale images can be divided
to be several 3×3 pixels. Then, compute the average value of each 3×3 pixels and
set this average value as a threshold of bi-level thresholding for the underlying 3×3
pixels.
Fig.1.9 shows examples of results obtained from bi-level thresholding. The results
from the adaptive threshold method are better than those of absolute or fixed
threshold. This comes from the fact that the absolute threshold does not take variations
of pixel values in the local area into account. Therefore, it tends to produce
very dark or very bright halftoned images.
Patterning: Patterning method represents each pixel by a block of cells consisting
of only black and white. It is often used, when an output device has more
spatial resolution than a source image. For example, when an output device has a
resolution of 640×480, the effective solution with 3×3 patterning matrix becomes
214×160. Input gray scale is converted into ten output levels as shown in Fig.1.10.
Each patterning matrix is represented by the average value of black and white pixels
in the matrix. For example, pattern number 0 and 9 have the average values of pixels
equaling zero and 255, respectively, whereas pattern 3 and 4 have the average values
of pixels equaling 85 and 113, respectively
To decide which pattern will be used to replace the considering pixel, a gray
scale image pixel will be compared with the average pixel values of all ten patterns.
The pattern with the closest average value of pixels will be selected to represent the
underlying pixel. Consider the example in Fig.1.11. Each pixel of a 3×3 matrix of
pixels is compared with the average values of all patterns. Then, a pattern is selected
to replace a pixel. It is obvious that the image size will increase nine times. In other
words, a spatial resolution is sacrificed to represent a gray scale image with only
black and white pixels.
Fig.1.12 shows various patterns with the same average intensity. However, the
three rightmost patterns will leave stripes in various directions. Fig.1.13 shows an
example of stripes in a digital halftoned image. The leftmost pattern is preferred
to the leftmost three to represent the patterns. To be more specific, patterns giving
stripes on the final results will not be selected.
Moreover, the differences in the patterns for successive intensity levels are minimized.
For the adjacent pattern, only one pixel change from one pattern to another
is allowed. For instance, from Fig.1.14, two changes of pixels from pattern 2 to 3
are not allowed. Fig.1.15 shows the comparison between the