Least-Squares Halftoning via Human Vision System and Markov Gradient Descent (LS-MGD): Algorithm and Analysis.

ALGORITHMS; LEAST squares; VISION; MARKOV processes; DIGITAL image processing; DIGITAL printing; QUANTUM dots

Halftoning is the core algorithm governing most digital printing or imaging devices, by which images of continuous tones are converted to ensembles of discrete or quantum dots. It is through the human vision system (HVS) that such fields of quantum dots can be perceived to be almost identical to the original continuous images. In the current work, we propose a least-squares-based halftoning model with a substantial contribution from the HVS model, and we design a robust computational algorithm based on Markov random walks. Furthermore, we discuss and quantify the important role of spatial smoothing by the HVS and rigorously prove the gradient-descent property of the Markov-stochastic algorithm. Computational results on typical test images further confirm the performance of the new approach. The proposed algorithm and its mathematical analysis are generically applicable to similar discrete or nonlinear programming problems. [ABSTRACT FROM AUTHOR]

Copyright of SIAM Review is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)