Digital Halftoning

Halftoning or analog halftoning is a process that simulates shades of gray by varying the size of tiny black dots arranged in a regular pattern. This technique is used in printers, as well as the publishing industry. If you inspect a photograph in a newspaper, you will notice that the picture is composed of black dots even though it appears to be composed of grays. This is possible because of the spatial integration performed by our eyes. Our eyes blend fine details and record the overall intensity [1]. Digital halftoning is similar to halftoning in which an image is decomposed into a grid of halftone cells. Elements (or dots that halftoning uses in simulates shades of grays) of an image are simulated by filling the appropriate halftone cells. The more number of black dots in a halftone cell, the darker the cell appears. For example, in Figure 4, a tiny dot located at the center is simulated in digital halftoning by filling the center halftone cell; likewise, a medium size dot located at the top-left corner is simulated by filling the four cells at the top-left corner. The large dot covering most of the area in the third image is simulated by filling all halftone cells.

Figure 4.1 A sample of digital halftoning

Three common methods for generating digital halftoning images are

  1. patterning
  2. dithering
  3. error diffusion

Patterning

Patterning is the simplest of the three techniques for generating digital halftoning images. It generates an image that is of higher spatial resolution than the source image. The number of halftone cells of the output image is the same as the number of pixels of the source image. However, each halftone cell is subdivided into a 4x4 grid. Each input pixel value is represented by a different number of filled squares in the halftone cell. Since a 4x4 grid can only represents 17 different intensity levels, the source image must be quantized. Figure 4.2 shows Rylander's recursive patterning matrices, which will be used in listing 4.1, and a sample of the patterning operation.

Figure 4.2 Rylander's recursive patterning matrices

Figure 4.3 The Patterning operation


NAME

pattern - generates a digital halftoning image of the input image via patterning.

SYNOPSIS

pattern(input_file_name, output_file_name)

DESCRIPTION

pattern generates a digital halftoning image from an input image using the patterning technique. The program pattern reads an input image, quantizes the pixel values, and maps each pixel to its corresponding pattern. The resulting image is 16 times larger than the original. The generated image is written to the output file as a TIFF file. A word of caution: "patterning" requires a large number of computations, images of size less than 100x100 are recommended.

EXAMPLES

pattern('PAINTER.TIF', 'pa_ptr.tif')

This example generates a digital halftoning image from PAINTER using the patterning technique (Figure 4.4)

a. Original PAINTER b. Digital halftoning image of PAINTER via patterning

Figure 4.4 Digital halftoning via patterning


Dithering

Another technique used for generating digital halftoning images is dithering. Unlike patterning, dithering creates an output image with the same number of dots as the number of pixels in the source image. Dithering can be thought of as thresholding the source image with a dither matrix. The matrix is laid repeatedly over the source image. Wherever the pixel value of the image is greater than the value in the matrix, a dot on the output image is filled. A well-known problem of dithering is that it produces artifacts of patterns introduced by fixed thresholding matrices. Figure 4.5 shows a sample of the dithering operation.

Figure 4.5 The dithering operation

Listing 4.2 is a MATLAB implementation of the dithering process.


NAME

dither - generates a digital halftone image via dithering

SYNOPSIS

dither(input_file_name, output_file_name)

dither(input_file_name, output_file_name, dmatrix)

DESCRIPTION

The first synopsis uses a default dither matrix to threshold the input image. The default dither is

This matrix is a rectangle dither matrix extracted from a 450 dither matrix. 450 dither matrices can make artifacts less obvious. The second synopsis, on the other hand, uses the dither matrix defined by the user. dither reads in an input image, compares each pixel with the corresponding element in the dither matrix, generates the output image, and writes it to the output file, which is in TIFF format. A word of caution: since "dither" requires a large number of computations, images of size less than 100x100 are recommended.

EXAMPLES

dither('LENA.TIF', 'di_le.tif')

This example generates a digital halftone image from LENA using the default dither matrix (Figure 4.5a.)

dither('S_PAINTER.TIF', 'di_spa.tif', [105,135,30;90,67.5,120;45,15,45;])

This example generates a digital halftone image from PAINTER using a dither matrix defined by the user (Figure 4.5b.)

a. Dithered LENAb. Dithered PAINTER

Figure 4.5 Examples of dithering output images


Error Diffusion

Error diffusion is another technique used for generating digital halftoned images. It is often called spatial dithering. Error diffusion sequentially traverses each pixel of the source image. Each pixel is compared to a threshold. If the pixel value is higher than the threshold, a 255 is outputted; otherwise, a 0 is outputted. The error - the difference between the input pixel value and the output value - is dispersed to nearby neighbors. Error diffusion is a neighborhood operation since it operates not only on the input pixel, but also its neighbors. Generally, neighborhood operations produce higher quality results than point operations. Error diffusion, when compared to dithering, does not generate those artifacts introduced by fix thresholding matrices. However, since error diffusion requires neighborhood operations, it is very computationally intensive.

Listing 4.3 is a MATLAB implementation of the error diffusion algorithm


NAME

error_diffusion - generates a digital halftoned image using error diffusion

SYNOPSIS

error_diffusion(input_file_name, output_file_name, threshold)

DESCRIPTION

error_diffusion generates a digital halftoned image using error diffusion. It reads an input image, compares each pixel with the input threshold, and sets the output to 0 or 255. The quantization error is then computed and dispersed to input pixels to the right and below the current pixel with different weights. The weights used in this implementation were first specified by Floyd and Steinberg (1975). Figure 4.6 shows Floyd and Steinberg's error filter. The output image is written into the output file in TIFF format. A word of caution: since "error_diffusion" requires excessively intensive computations, images of size less than 70x70 are recomended.
threshold--the value that determines the output to be 0 or 255. It is usually set to 128

Figure 4.6 Floyd and Steinberg's Error Filter

EXAMPLES

error_diffusion('LENA.TIF', 'ed_le.tif', 128)

This example error diffuses LENA using 150 as the threshold (Figure 4.7a).

error_diffusion('PAINTER.TIF', 'ed_pa.tif', 150)

This example error diffuses PAINTER using 128 as the threshold (Figure 7.6b).

a. Error-diffused LENAb. Error-diffused PAINTER

Figure 4.7 Examples of error_diffusion output images