Digital Halftoning: Algorithm Engineering Challenges

Tetsuo ASANO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.2   pp.159-178
Publication Date: 2003/02/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: 
Keyword: 
approximation algorithm,  combinatorial optimization,  matrix rounding,  network flow,  

Full Text: PDF>>
Buy this Article




Summary: 
Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. This paper surveys how algorithm engineering can contribute to digital halftoning or what combinatorial problems are related to digital halftoning. A common criterion on optimal digital halftoning leads to a negative result that obtaining an optimal halftoned image is NP-complete. So, there are two choices: approximation algorithm and polynomial-time algorithm with relaxed condition. Main algorithmic notions related are geometric discrepancy, matrix (or array) rounding problems, and network-flow algorithms.