Model based direct binary search halftone optimization with a dual interpretation

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