Efficient, high quality halftoning algorithms

Direct binary search (DBS) is an iterative technique that produces high quality halftone images. However, it requires a great deal of computation. We introduce more efficient halftoning algorithms that generate halftone images with quality approaching that of DBS. We first present a look-up-table (LUT) based halftoning algorithm. Unlike the screening algorithm, the stacking constraint for LUT is not necessarily satisfied. This algorithm improves halftone image quality compared with screening. Secondly we present a new error diffusion halftoning algorithm for which the filter weights and the quantizer thresholds vary depending on input pixel value. We also propose an error diffusion system with parallel scan that uses variable weight locations to reduce worms. Although error diffusion may produce halftone images with better quality than screening, it is inherently a serial process. We introduce a pinwheel error diffusion method that binarizes an image in subdivided blocks. The blocks are processed in two separate groups to avoid boundary artifacts between the adjacent blocks. The algorithm is well-suited for implementation with a processor that has only limited local storage, or with multiple processors operating in parallel. Finally, we present a clustered minority pixel error diffusion halftoning algorithm for which the quantizer threshold is modified based on the past output and a dot activation map. The halftone image quality is further improved by using different error diffusion weights for different input gray levels