Chinese Journal of Computers   Full Text
Title	Research on Balancing Clustered Dot Density for Hybrid Halftone Dithering Algorithm
Authors	XU Guo-Liang1),2) TAN Qing-Ping1)
Address	1)(College of Computer, National University of Defense Technology, Changsha 410073) 2)(College of Computer and Communication, Hunan University, Changsha 410082)
Year	2009
Issue	No.8(1550—1559)
Abstract &   Background	Abstract This study found that the ratio between the clustered dot density in shadow and highlight area is roughly 1∶2, based on existing hybrid halftone algorithms. The ratio will bring unwanted constraint to increase clustered dot density. The hybrid halftone algorithms formed clustered dot with a geometric divide of a halftone plane. With the theorems deducted from Euler formula, a new algorithm to optimize the ratio is proposed. In the experiment to test the new algorithm, the ratio between clustered dot densities in shadow and highlight was improved to 0.903919 from original 0.502195. Keywords halftone; hybrid halftone; dithering algorithm; dithering matrix; Voronoi diagram; Delaunay triangulation Background Hybrid dithering algorithm, as a halftone method, is most promising for printing industry. After analyzing existing algorithms to produce hybrid halftone dithering matrix with a geometric divide, this paper found that clustered dot density in shadow and highlight area had big differences. This will bring unwanted constraint to increase clustered dot density. The hybrid halftone dithering matrix is usually constructed from a 2D geometric divide, such as Voronoi diagram, where the centre of each area of the divide is randomly and uniformly distributed across the halftone plane. The vertex of the Voronoi region will be the centre of shadow clustered dot and center point of the region will be the centre of light clustered dot. The ratio between the number of vertex and area is approximately 2:1 when Voronoi diagram is used as the geometric divide, which is shown by theorem 1 of this paper. As theorem 2 of this paper indicates, the clustered dot density in shadow equals to the clustered density in light if the geometric divide used to produce the dithering matrix is composed of quadrilaterals only. Therefore, to merge triangles of Delaunay triangulation as much as possible is the objectives of our optimizing algorithm while keeping the resulting geometric divide could be tiled seamlessly. The algorithm to construct clustered dot dithering array follows 6 steps: (1)generate a uniformly distributed and seamless connected clustered dot centre; (2)make a 2D point set by extending the boundary seamlessly; (3)calculate Voronoi region from the point set above; (4)connect all the center of the region sharing the same edge as boundary in order to obtain a Delaunay divide; (5)merge the triangle to optimize the geometric divide to make the dithering array; (6)produce the dithering array with the geometry divide above and smooth the clustered do shape with Gaussian filter. In experiment to test the new algorithm, the ratio between clustered dot densities in shadow and highlight is improved to 0.903919 from original 0.502195. The authors have been engaged in research and development of halftone products for printing industry since 1997 and was financially supported by Science and Technology Bureau, Hunan Province in 2005 under contract 05GK3023. The objective of this research is to develop quality halftone method for current printing process. The halftone product ESK (Engraving Screening Kits) has been used in more than 70 engraving plate making factories in China and other Asian countries.