Digital Halftoning

Introduction

Halftoning is the representation of different shades of gray by suitably placed black marks on white paper. Because of the low-pass spatial-frequency properties of the human eye, the dots become invisible if they are close enough together.

Digital halftoning means deciding how to place the dots by using computer algorithms, as opposed to the old-fashioned analog methods (mostly photographic). The netpbm package contains a program to do this, called pgmtopbm. The man page for pgmtopbm says that Robert Ulichney's book “Digital Halftoning” is the standard reference on this subject; and indeed, it's a fine book. However, it doesn't deal extensively with the transfer function of real printers; we must deal with this problem separately.

pgmtopbm

One very confusing feature of pgmtopbm is that it doesn't convert a standard displayable PGM image directly to a halftone. That's because the PGM standard calls for the image data to be compensated for the nonlinearity of a standard monitor display (see the discussion of gamma). Instead, it tacitly assumes that the input data are proportional to the reflectance of the printed image. That is, a uniform gray area with data values of 127 (nearly half of the maximum 255) will be transformed into a halftone in which about half the pixels are white and half are black.

gray127.pgm gray127 via -fs gray127 via -hilbert gray127 gamma-corrected For example, here are (from left to right) just such a gray square, with all data values equal to 127; its default conversion by pgmtopbm to a mixture of black (50.2% of the pixels) and white (49.8%) pixels with pgmtopbm; conversion using pgmtopbm's -hilbert option; and a gamma-corrected version of intensity 127/255 as bright as pure white, which ought to appear about as bright as the two squares to its left. You can see that the halftoned versions are much lighter than the original image, and about the same average brightness as the gamma-corrected version at the extreme right of the row of squares.


I have to say “about”, because most computer monitors have a problem analogous to that of laser printers: the image is made up of overlapping dots instead of distinct square pixels. (The main difference here is that the dots are light instead of dark.) Unless you have a well-adjusted LCD screen, you probably won't see the same brightness on the three right squares above. But, in any case, you should see the middle (halftoned) squares closer in color to the extreme right square than to the extreme left one.


Halftoning algorithms

Floyd-Steinberg

The pgmtopbm program contains several algorithms. The default is “boustrophedonic Floyd-Steinberg dithering” — a mouthful in any language. But the basic idea is very simple: the grayscale image is scanned (alternately from left to right, and right to left), and the program compares the current input gray value with a weighted mean of the differences (“errors”) between the printed dots and the gray values in a small region around the current point. When the printing falls half a dot below the integrated grayness (so to speak), another dot is printed. Any remaining surplus or deficit is carried forward, to keep the average gray level correct. The idea is that the accumulated error should never exceed half a black pixel.

Because of the accumulated-error accounting, this type of halftoning is also known as “error diffusion”. As explained in Ulichney's book, it tends to produce regular patterns that can appear quite distracting at some gray levels.

Another drawback is the production of occasional “glitches” in an otherwise uniform area; you can see such artifacts in the second square above.

A more serious problem, in our situation, is the isolation of single white pixels that are completely surrounded by black ones, when the gray level is near or below half-maximum brightness. Because of the overlapping-dot problem, Floyd-Steinberg makes pictures that print much too dark on a laser printer.

Hilbert-curve

The man page for  pgmtopbm  suggests the Hilbert-curve method to mitigate this problem. This is a modification of Floyd-Steinberg; instead of simply tracing along the rows of the image, the program follows a space-filling curve, laying down clumps of pixels instead of isolated ones. (The default clump size is 5 pixels, but you can select other sizes.)

Indeed, this alleviates the problem somewhat (see the third square in the row above). But we have traded a big loss in resolution for a modest improvement in grayscale rendition. The picture now looks quite grainy.

Furthermore, the Hilbert-curve method still tends to produce distracting patterns in the halftoned image. And the grayscale rendition, while much improved, is still not completely correct.

Other methods are available; but you begin to see that there's more to this problem than just selecting a dithering algorithm.

 

Copyright © 2006 – 2008, 2012 Andrew T. Young


Back to the . . .
introduction to image scanning

or the GF home page

or the website overview page