Model-based halftoning using direct binary search

In this work, we propose a new method to generate halftone images which are visually optimized for the display device. The algorithm searches for a binary array of pixel values that minimizes the difference between the perceived displayed continuous-tone image and the perceived displayed halftone image. The algorithm is based on the direct binary search (DBS) heuristic. Since the algorithm is iterative, it is computationally intensive. This limits the complexity of the visual model that can be used. It also impacts the choice of the metric used to measure distortion between two perceived images. In particular, we use a linear, shift- invariant model with a point spread function based on measurement of contrast sensitivity as a function of spatial frequency. The non-ideal spot shape rendered by the output devices can also have a major effect on the displayed halftone image. This source of non-ideality is explicitly accounted for in our model for the display device. By recursively computing the change in perceived mean-squared error due to a change in the value of a binary pixel, we achieve a substantial reduction in computational complexity. The effect of a trial change may be evaluated with only table lookups and a few additions.