Partitionless Halftoning

We’ve looked at two halftoning methods using thresholding: either directly on the image, or using a pattern. These require making subdivisions of the image to get any decent spatial resolution. Instead, we can specify properties of the pattern such that the pattern itself acts as a threshold. The black and white image can then be found from direct pixel-wise comparison of the pattern and image: any points in the image brighter than the pattern become white, and darker become black.

To figure out the sort of pattern needed, let’s pretend that the image and pattern are independent random variables: I and Q. These have probability distributions p_I(x) and p_Q(x). For simplicity, let’s say that both range continuously from 0 to 1. Since we’re making a black and white image, B = (I>Q), we want the average of that image to be \bar{I}, or E(I). Because the brightness ranges from 0 to 1, this average brightness is the probability that I>Q. The following equations express that in equations, then expand via probability theory.

\begin{aligned} \bar{I} &= E(I) = p(I>Q) \\ \bar{I} &= \int_0^1 y \, p_I(y) dy \\ &= \int_0^1 p_I(y) \left( \int_0^y p_Q(x) dx \right) dy \end{aligned}

For these integrals to be equal, Q needs a uniform probability distribution:

\begin{aligned}\int_0^1 p_I(y) \left( \int_0^y 1 dx \right) dy &= \int_0^1 p_I(y) \left( y \right) dy \\ &= \bar{I}\end{aligned}

Great! Now we know that as long as the intensity of the pattern uniformly ranges from 0 to 1, we can just do local comparisons of the image and the pattern. In terms of images, this means that the pattern needs to have an equalized histogram.

Simple, right? Well, kinda. It turns out that that’s neglecting the spatial distribution of the pattern. For example, the following images use triangle waves of different wavelengths as the pattern. All of them have a uniform distribution of brightness, but very different spatial scales.

When the spatial scale of the pattern is too small, that limits the available range, and the assumption of a continuous distribution breaks down. When the pattern scale is too big, this blurs the small scales in the image. Ideally, the pattern should change at a scale smaller than the smallest important variations in the image, but still have enough pixels to approximate a continuous distribution.

The easiest way to deal with this is to increase the effective resolution of the image, by resizing the image via bilinear interpolation or somesuch. This may not be an option sometimes, such as when the halftoned image needs to have the same number of pixels as the original. With that constraint, smoothing could be the way to go. The following image compares an unsmoothed image with images blurred across 1/4 and 1/2 of the wavelength.

That gets rid of the sharp bits on the image, and still looks decent from a distance.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.