Study On Key Algorithms Used In Digital Halftoning System

With the development of Textile Printing of our country, the technique of digital halftoning is required to be improved urgently, in order to meet the needs of the growing market and the challenges of the world market. How to improve the efficiency of the halftoning process and the quality of the halftoning results is the key problem of designing the digital halftoning system by using digital image processing technology. Some efforts have been performed on several key issues in the dissertation. The main contributions of the thesis include:On the study of the moire problem, this thesis proposes an algorithm for building stochastic-dot screens based on the dither matrix to avoid the moire pattern. To choose the visiting path that meets the demand of digital halftoning, we study several kinds of visiting paths and analyze them by using Fourier-analysis.On the study of improving the efficiency of digital halftoning, this thesis proposes an improved incremental Delaunay triangulation algorithm. The traditional incremental algorithm has the advantages of utilizing less system memory, inserting points dynamically, easy to implement, and so on. However, the efficiency of the traditional incremental algorithm is low, which will affect the efficiency of the halftoning process. We present a simple enhancement for locating the point to be inserted by using the topological relationships between the triangles. The triangle containing the inserted point can now be found faster.On the study of the homogenization of the screen dots, this thesis proposes a homogenization algorithm based on the error diffusion algorithm. Traditionally, to avoid the moire pattern, the screen dots are required to be distributed randomly. Although the random visiting paths meet the demand perfectly, they will also bring some screen dots that with long and narrow shapes which will affect the quality of the halftoning images. The maximal screen surface of different dots will also vary considerably. The homogenization algorithm we proposed is to weaken the negative effects brought by the random visiting paths while maintaining the efficiency of the halftoning algorithm. Our method is based on the idea of the error diffusion algorithm, by diffusing the error between the surface of the dot and the average surface of all dots to the adjacent dots to reduce the surface difference between different dots.Based on the algorithms mentioned above, we develop a prototype system of digital halftoning. The system process is designed according to process of digital halftoning. The core of each module is the algorithm studied in our thesis. In addition, the interactive model is provided for selecting different algorithms for the Delaunay triangulation, the way to determine the maximal screen dot surface, and so on. This prototype system is for the purpose of studying and improving the key algorithms in digital halftoning. It is also a helpful exploration on digital halftoning.