Four commonly used digital halftone algorithms

As we all know, digital halftone technology refers to a technology based on human visual characteristics and image rendering characteristics, using mathematical, computer and other tools to achieve optimal reproduction of images on binary (or multi-color binary) rendering devices. . Digital halftones utilize the low-pass nature of the human eye. When viewed at a certain distance, the human eye sees spatially close parts of the image as a whole. With this feature, the local average grayscale of the halftone image observed by human eyes is approximately similar to the local average grayscale value of the original image, so that a continuous tone effect is formed as a whole.

Halftone technology has been used in the printing industry for more than a century, and has been used in digital output devices for more than 40 years. With the increasing popularity of digital output devices such as laser printers, inkjet printers, digital printers, digital cameras, and plasma displays, digital halftone technology has received widespread attention from manufacturers and research institutions. In addition to the application of digital halftone technology in printing and image output, it is also used in areas such as compression storage, textiles, and medicine. Therefore, digital halftone technology has important theoretical significance and use value.

According to digital halftone application characteristics and different fields, many algorithms have been proposed. When the algorithm is classified according to the processing method of the algorithm, it can be divided into a point processing algorithm, a neighborhood processing algorithm and an iterative method. Point processing algorithms are the simplest methods that use digital methods to simulate the traditional contact screening process in the printing industry. Each pixel unit in the resulting halftone image depends only on the gradation of the pixels. Among them, the most important methods are the halftone template method and the dithering method; the neighborhood processing algorithm calculates a plurality of pixels in the neighborhood of the continuous tone image pending pixel to obtain the pixel value of the halftone image. Typical of these algorithms is the error diffusion algorithm; the iterative method is an iterative processing algorithm, which requires multiple comparisons to obtain an optimal halftone image. Therefore, the maximum amount of calculations. Here are four representative digital halftone algorithms:

1, Dot Diffusion (Dot Diffusion)

Knuth's point spread halftone algorithm is an algorithm that attempts to preserve the advantages of error diffusion while providing parallel processing. The point diffusion algorithm has only one kind of design parameter, namely the class matrix C, which determines the order in which the pixels are halftone processed. The position of a continuous tone image pixel is divided into IJ classes, and I and J are all constant integers.

2. Iterative halftone algorithm

The idea of ​​an iterative halftone algorithm is to use a simple method to get the initial halftone image first, and then iteratively process the original halftone image so that the halftone image obtained each time has a smaller error, and finally get the most visual Excellent halftone image. The advantage of the iterative halftone algorithm is that the resulting halftone image has excellent visual effects, essentially no structural texture, and can reproduce rich tones correctly. However, based on the computational complexity of this algorithm, iterative halftoning algorithms are generally difficult to use in real-time processing applications and can only be used as a standard test program.

3, error diffusion algorithm (Error Diffusion)

Error diffusion algorithm is a popular and halftone effect algorithm, this algorithm was first proposed by Floyed-Steinberg. This algorithm requires neighborhood processing, it can provide a higher halftone quality for the printer and does not cause dot gains, resulting in a rich hue in the halftone image and anisotropic distribution of the pixel points.

The basic idea is to first quantize the image pixels according to a certain scanning path threshold, and then spread the quantization error to adjacent unprocessed pixels in a certain way.

DBS uses an iterative exchange procedure to reduce the error E. This algorithm starts with a randomly obtained initial halftone image and scans the entire halftone image from left to right and from top to bottom, for each of the halftone images. Pixels, evaluating the effect of pixel negation and the quality of the halftone image obtained by swapping its value with the surrounding eight pixels. If any of the changes reduce the error, such a transformation that causes the error to be reduced is retained, and the above process is repeatedly performed on the halftone image until the entire process does not have any transformation operation, and the DBS algorithm ends.

4, ordered dither algorithm (ordered dither)

In this screening algorithm, the input image is compared with a one-cycle threshold matrix (or a screening matrix). The threshold matrix, where N defines the period of the threshold matrix.

For a particular threshold matrix t(n), the ordered jitter screening algorithm can be described as follows:

The input image should be normalized, ie 0≤x(n)≤1. When h(n)=0, the halftone output pixels are white dots, and when h(n)=1, halftone pixels are black dots. The threshold matrix determines the order in which the dots become black when the brightness is reduced, and it also determines the quality of the halftone image. The ordered dithering algorithm has different characteristics with different designs of the threshold matrix. The simplest threshold matrix is ​​a matrix in which each pixel is a fixed value: t(n)=0.5. If an ordered dithering algorithm with such a threshold matrix is ​​applied to the image, most of the details of the continuous tone image are lost, and the resulting corresponding halftone image has a large distortion compared to the original continuous tone image.

In general, ordered jitter is classified into point-aggregated ordered jitter and point-discrete ordered jitter. The dot-clustered ordered jittering screening matrix was carefully designed to simulate the halftoning process. When the pixel density of the continuous tone image decreases, dots will be generated around the pixel. The design rule of discrete discrete ordered jitter is proposed by Bayer. His research indicates that the visibility of non-ideal artificial textures can be obtained by Fourier analysis of the dot patterns at different brightness levels. When the dot pattern of a uniform patch has components at different wavelengths, the component with the longest wavelength in the limited wavelength is the component with the highest visibility. Based on this standard, Bayer designed an optimized screening matrix. The halftone image obtained using the discrete discrete ordered jitter of this matrix contains more visible details.

Although the discrete discrete ordered jitter retains more details, due to the “net point increase”, point aggregated ordered jitter is often used in practical applications. Dot gain is caused by the printer's non-ideal nature. Although it can be assumed that an ideal printer can produce dots with predefined geometric shapes such as squares, dots will be generated due to ink spreading from the predefined geometry to surrounding pixels. Increase the phenomenon. When the pixel density of the continuous tone image decreases, the dots will be generated from the surrounding pixels, so that the point-aggregate-ordered jitter more easily prevents the dots from increasing, thereby reducing the dot gain effect in the halftone image as a whole.

In general, in these halftoning algorithms, the best halftone image quality is the iterative algorithm, but it is generally not used in real-time processing algorithms because of the excessively complex computational complexity. The error diffusion algorithm is currently the most popular halftone algorithm. The halftone image produced by it has no obvious moiré, and the visual effect is better. The dithering algorithm is simple to implement, but it has some defects in terms of tone reproduction, spatial resolution and visible texture. The point diffusion algorithm implements parallel processing, but the halftone image quality still needs improvement.