Multilevel halftoning over hexagonal grids

Digital halftoning has traditionally been thought as a simple binary modulation algorithm that is able to produce only black and white dots. The arrangement of these dots was also restricted to the use of rectangular grids mainly due to lack of proper printing hardware to display images in other placement grids. With recent advancements in printing technology, printers are now able to generate dots of more than two quantified levels and place them over alternate tessellations, such as hexagonal grids. Moreover, model-based halftoning techniques have been incorporated into traditional halftoning methods to maximize image quality. In this paper, we propose a new algorithm exploiting model-based halftoning over hexagonal grids. This algorithm employs either binary halftoning or multi-level halftoning using gray level separation, and implements a hexagonal version of the classic Floyd-Steinberg filter for error diffusion. A printer model is also integrated in the algorithm to account for the overlapping of adjacent dots in printing. Simulation results show that this approach reduces dot clustering and eliminates undesirable visual artifacts while providing smoother halftone textures over the entire gray-scale region. The new method also has similar computational complexity to the conventional error diffusion algorithm.