Anticorrelation digital halftoning

A new class of digital halftoning algorithms is introduced. Anti-correlation digital halftoning (ACDH) combines the idea of a well-known dangerous game, Russian roulette, with the statistical approach to bilevel quantization of digital images. A representative of the class, serpentine anti-correlation digital halftoning, is described and compared to error diffusion, ordered dither, and other important digital halftoning techniques. Serpentine ACDH works very well. It causes fewer unpleasant correlated artifacts and less contouring than the benchmark algorithms. The quantization noise spectra associated with serpentine ACDH possess beneficial characteristics related to properties of the vision system. The term "violet noise" is proposed to describe quantization noise with stronger bias in favor of high-frequency components than that of blue noise. Novel techniques for color visualization of the noise spectra and the corresponding phase spectra are introduced, and the relative significance of the magnitudes and phases of the discrete Fourier transform of the quantization noise is studied. Unlike popular algorithms based on error diffusion, serpentine ACDH does not enhance edges. This should be good for its application to digital holography. A simple input preprocessing technique allows one to introduce edge enhancement if desired, while keeping it more isotropic than that of error diffusion. The relation between unwanted transient boundary effects and edge enhancement accompanying error diffusion is examined, and approaches to reduction of boundary effects are considered. Serpentine ACDH does not cause significant boundary effects. The average intensity representation by different algorithms is studied for constant input levels (serpentine ACDH does remarkably well). The results of subjective testing are compared to the predictions of the popular one-channel models of the vision system. Printing at high resolutions and its application to medical imaging are studied. ACDH is shown to be extendable to multilevel halftoning and color quantization. Prospects for ACDH research are discussed.