A Unified Framework for Digital Halftoning and Dither Mask Construction: Variations on a Theme and Implementation Issues

Abstract

We present a unified algorithmic framework for some classes of digital halftoning algorithms including Direct Binary Search (DBS) and dither mask generation algorithms such as Void and Cluster, BIPPSMA, and clustered dot with blue noise interpolation. Although these algorithms are different and used in different ways, e.g. Direct Binary Search is a global halftoning process, whereas dither masks are used in point halftoning processes, we show that they are all variations of a core algorithm. This makes it easier to compare the performance of these algorithms. Furthermore, by viewing these algorithms in the same framework, algorithmic extensions and implementation tricks and techniques among these algorithms can be more easily shared and their benefits exploited. The core algorithm is essentially an optimization algorithm using pixel swapping where the cost function describes the perceptual difference between the halftone image and the color image when viewed at a distance. We compare various algorithms in the literature as they are cast in this framework. In particular, this framework allows us to derive a more efficient implementation of DBS.