J. Newbern, V. Michael Bove, Jr.

Abstract

Halftoning or quantizing by means of a threshold array is simple, fast, and easily parallelized: a matrix of threshold values is tiled across the image and each output pixel is colored white if the image value exceeds the threshold value and is colored black otherwise. The computational efficiency and locality of the compare operation makes this technique suitable for applications in printing and motion video quantization. In the past, threshold arrays have generally been used with regular-appearing patterns such as clustered- dot 'classical' halftoning or Bayer's dispersed-dot patterns. Ulichney has presented a heuristic method for generating blue- noise threshold arrays which do not appear regular, and offer the visual advantages of error-diffusion without its computational costs. Such heuristic methods are capable of generating high-quality threshold arrays, but they are not flexible or controllable enough to enable tuning for particular applications or output device characteristics. We present instead a genetic method for generating a blue-noise threshold array that optimizes a set of criteria encoded in a fitness function, which can be specified to reward any desired attributes. Although the genetic method is computationally intensive, the cost is incurred only once, and the resulting array can be used for millions of images. We compare images halftoned using our arrays with other blue-noise array and error-diffusion methods, and examine the spectral characteristics of the resulting patterns.