The direct binary search (DBS) algorithm employs a search heuristic to minimize the mean-squared perceptually filtered error between the halftone and continuous-tone original images. Based on an efficient method for evaluating the effect on the mean squared error of trial changes to the halftone image, we show that DBS also minimizes in a pointwise sense the absolute error under the same visual model, but at twice the viewing distance associated with the mean-squared error metric. This dual interpretation sheds light on the convergence properties of the algorithm, and clearly explains the tone bias that has long been observed with halftoning algorithms of this type. It also demonstrates how tone bias and texture quality are linked via the scale parameter, the product of printer resolution and viewing distance. Finally, we show how the tone bias can be eliminated by tone-correcting the continuous-tone image prior to halftoning it.

The direct binary search (DBS) algorithm is an iterative method designed to minimize one metric of error between the grayscale original and halftone image. This metric incorporates a model for the human visual system. To achieve the optimization, an initial halftone is adjusted until a local minimum of the metric is achieved at each pixel. However this local minimum can be shown to simultaneously minimize another metric of error using another visual model; this alternative metric and visual model combination are referred to as the dual interpretation of DBS. An analysis of this dual reveals the origin of tone reproduction bias in DBS. Many model based halftoning algorithms are effected by this problem. The dual can also be used to quantify the perceived tone reproduction capabilities of DBS and provides insight on why DBS yield very high quality halftones. Despite the complexity of the DBS algorithm it can be implemented with surprising efficiency. We demonstrate how the algorithm simultaneously exploits two different visual models and error metrics to efficiently yield very high quality halftones.

The direct binary search (DBS) algorithm is an iterative method which minimizes a metric of error between the grayscale original and halftone image. This is accomplished by adjusting an initial halftone until a local minimum of the metric is achieved at each pixel. The metric incorporates a model for the human visual system (HVS). In general, the DBS time complexity and halftone quality depend on three factors: the HVS model parameters, the choice of initial halftone, and the search strategy used to update the halftone. Despite the complexity of the DBS algorithm, it can be implemented with surprising efficiency. We demonstrate how the algorithm exploits the model for the HVS to efficiently yield very high quality halftones.