The general idea behind halftoning is to render an image using a very limited number of colors. On this blog, I’ll focus particularly on rendering black and white images. The following image is the Lena test image, and its grayscale version (converted in MATLAB). I’ll be using these for most of the approaches that I show, for ease of comparison.

So, halftoning! Basically, you want the full-tone image to have the same average intensity as the output image. The simplest way to do this is by looking at the cumulative distribution function (CDF) of the image’s intensity. With the CDF and average intensity of the image, a threshold value can be found. Any pixels brighter than the threshold become white, and the rest are made black. A quick aside about images: they tend to range in value from 0-255 (black – white), but I prefer working on a scale of 0-1, so I’ve rescaled things appropriately. The following plot shows the CDF for Lena.

The x-axis is the intensity of the image, and the y-axis is the CDF. The average intensity of the image is about 0.38, so we find the x-value for y = (1-0.38), which gives a threshold of 0.43. For each pixel in the image, all the intensities brighter than 0.43 are white, and darker are black.

And that turns out OK. Not great, but that’s to be expected since it’s the simplest approach to digital halftoning. There are so many improvements and variations to be made!

The above lacked any explicit math, which I will remedy here. Define the intensities of the grayscale image as I with average intensity \bar{I}, and the output black and white image as B. We want to find a threshold, t, so that for B = (I > t), \bar{I} = \frac{N[B==1]}{N[B]} = \frac{N[I > t]}{N[I]} = 1- \frac{N[I \leq t]}{N[I]} . Here N represents the number of pixels that fulfill its argument. The definition of B is a pixel-wise comparison such that ‘true’ values are white, and ‘false’ values are black.

The threshold is found using the CDF of I, defined as F_I(i) = N \left[ I \leq i \right]/N \left[I \right] . Using the above relation between I and t, we have F_I(t) = 1- \bar{I}. Thus, we can find t from inversion of the CDF as t = F_I^{-1}(1- \bar{I}). Practically, this is done using interpolation.