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

作者：Shen Jianhong^*

来源：SIAM Review, 2009, 51(3): 567-589.

DOI：10.1137/060653317

• halftoning
• human vision system (HVS)
• spatial smoothing
• entropy
• least squares
• random fields
• stochastic gradient descent
• Markov random walks
• Bernoulli flipping
• stochastic convergence
• blue noise

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.

• 出版日期2009-9