Optimal halftoning over hexagonal grids

J. Bacca Rodríguez, A. J.González Lozano, G. R. Arce, D. L. Lau

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


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.

Original languageEnglish
Title of host publicationColor Imaging XI
Subtitle of host publicationProcessing, Hardcopy, and Applications - Proceedings of SPIE-IS and T Electronic Imaging
StatePublished - 2006
EventColor Imaging XI: Processing, Hardcopy, and Applications - San Jose, CA, United States
Duration: Jan 17 2006Jan 19 2006

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
ISSN (Print)0277-786X


ConferenceColor Imaging XI: Processing, Hardcopy, and Applications
Country/TerritoryUnited States
CitySan Jose, CA


  • Digital Halftoning
  • Direct Binary Search
  • Error Diffusion
  • Hexagonal Grids

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Optimal halftoning over hexagonal grids'. Together they form a unique fingerprint.

Cite this