Blue noise methods for hexagonal grids and multitone dithering

The problem of digital halftoning originates in the need to reproduce physically a continuous tone image with a limited set of colors. The advent of the ink-jet printer increased the demand for practical high-quality halftoning algorithms that, in general, comply with the principles of blue noise dithering introduced by Ulichney. This work focuses on optimal image rendering algorithms for printing devices, addressing the need for new algorithms that support new printing technologies.; The first sections deal with printing devices with alternative printing lattices. These mechanisms abandon the traditional rectangular grid in favor of hexagonal tessellations. This is of particular interest since blue noise dithering principles indicate that the visual artifacts at several intensities, which appear in rectangular-grid halftones, can be overcome through the use of hexagonal sampling. While the spectral analysis of blue noise dithering provides the desired spectral characteristics one must attain, it does not provide the dithering structures needed to achieve them. This research project develops such optimal dithering mechanisms for hexagonal grids through modifications of the Direct Binary Search (DBS) algorithm. Special attention is given to the effects of the new geometry on the Human Visual System (HVS) model and on the efficient implementation of the algorithm. DBS provides the best possible output at the expense of high computational complexity and while it is not practical in most applications, it provides a performance benchmark for other more practical algorithms.; Latter sections of this dissertation focus on optimal dithering structures for printers that are able to display multiple shades of gray instead of the traditional black and white. Unlike the case of hexagonal grids, a blue noise model for this problem does not exist, as a result, multilevel halftoning (multitoning) algorithms have been developed as unguided extensions of halftoning algorithms. Patterns generated with these algorithms cannot be qualified objectively without the guidelines given by such theory leading to subjective, unmeasurable improvements.; This work develops the theory and design of multitone blue-noise dithering. Here, arbitrary multitone dot patterns are modeled as a layered superposition of stack-constrained binary patterns, allowing the formulation of a simple optimization framework that exploits the HVS model. Blue-noise multitones exhibit minimum energy at low frequencies and a staircase-like, ascending, spectral pattern at higher frequencies. For a given set of inks, a procedure to determine their optimal concentration is described. The optimum spectral profile is thus described by a corresponding set of principal frequencies and amplitudes whose calculation requires the definition of a correlation structure governing the interaction between patterns of dots of different intensities, and whose values are uniquely defined by the ink intensities and concentrations. Efficient algorithms for the generation of multitone, blue-noise dither patterns are introduced based on the concept of threshold decomposition.