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

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 frame-work, 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.

By: Chai Wah Wu, Gerhard R. Thompson, Mikel J. Stanich

Published in: RC22849 in 2003


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .