16 January 2006 Optimal halftoning over hexagonal grids
Author Affiliations +
Halftoning approaches to image rendering on binary devices have traditionally relied on rectangular grids for dot placement. This practice has been followed mainly due to restrictions on printer hardware technology. However, recent advances on printing devices coupled with the availability of efficient interpolation and resampling algorithms are making the implementation of halftone prints over alternate dot placement tessellations feasible. This is of particular interest since blue noise dithering principles indicate that the visual artifacts at several tone densities, which appear in rectangular-grid halftones, can be overcome through the use of hexagonal tessellations. 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 these. In this paper, these optimal dithering mechanisms are developed through modifications of the Direct Binary Search (DBS) algorithm extensively used for rectangular grids. Special attention is given to the effects of the new geometry on the Human Visual System (HVS) models and on the efficient implementation of the hexagonal-grid DBS. This algorithm provides the best possible output at the expense of high computational complexity, and while the DBS algorithm is not practical in most applications, it provides a performance benchmark for other more practical algorithms. Finally, a tone-dependent, hexagonal-grid, error-diffusion algorithm is developed, where the DBS algorithm is used to optimize the underlying filter weights. The characteristics of the HVS are thus implicitly used in the optimization. Extensive simulations show that hexagonal grids do indeed reduce disturbing artifacts, providing smoother halftone textures over the entire gray-scale region. Results also show that tone-dependent error-diffusion can provide comparable results to that of the DBS algorithms but at a significantly lower computational complexity.
© (2006) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
J. Bacca Rodríguez, A. J. González Lozano, G. R. Arce, and D. L. Lau "Optimal halftoning over hexagonal grids", Proc. SPIE 6058, Color Imaging XI: Processing, Hardcopy, and Applications, 605811 (16 January 2006); doi: 10.1117/12.643527; https://doi.org/10.1117/12.643527


Model-based clustered-dot screening
Proceedings of SPIE (January 15 2006)
Uniform rosette for moire-free color halftoning
Proceedings of SPIE (January 28 2007)
Human vision and image rendering is the story over,...
Proceedings of SPIE (July 16 1998)
Model-based color halftoning using direct binary search
Proceedings of SPIE (December 20 1999)

Back to Top