Talking about Several Common Digital Halftone Algorithms
We are a big printing company in Shenzhen China . We offer all book publications, hardcover book printing, papercover book printing, hardcover notebook, sprial book printing, saddle stiching book printing, booklet printing,packaging box, calendars, all kinds of PVC, product brochures, notes, Children's book, stickers, all kinds of special paper color printing products, game cardand so on.
For more information please visit
http://www.joyful-printing.com. ENG only
http://www.joyful-printing.net
http://www.joyful-printing.org
email: info@joyful-printing.net
Halftone technology has been used in printing for more than a century and has been used in digital output devices for more than 40 years. With the increasing use 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 its applications in printing and image output, digital halftone technology is also used in the fields of compression storage, textiles and medicine. Therefore, digital halftone technology has important theoretical significance and use value.
As we all know, digital halftone technology refers to a technology that realizes the optimal reproduction of images on binary (or multi-color binary) coloring devices based on human visual characteristics and image coloring characteristics using tools such as mathematics and computers. . The digital halftone is a low-pass characteristic of the human eye. When viewed at a certain distance, the human eye regards a spatially close portion of the image as a whole. With this characteristic, the local average gray scale of the halftone image observed by the human eye approximates the local average gray value of the original image, thereby forming a continuous tone effect as a whole.
Many algorithms have been proposed based on the application characteristics of digital halftones and different fields. When classifying according to the processing method of the algorithm, it can be divided into point processing algorithm, neighborhood processing algorithm and iterative method. The point processing algorithm is the simplest method that uses a digital approach to simulate the traditional contact screening process in the printing industry, where each pixel unit in a halftone image produced depends only on the gradation of the pixel. 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 continuously modulated image to be processed to obtain the pixel value of the halftone image. The more typical of these algorithms is the error diffusion algorithm; the iterative method is an iterative processing algorithm that requires multiple comparison calculations to obtain an optimal halftone image. Therefore, it has the largest amount of calculation. This article mainly introduces several representative digital halftone algorithms.
First, ordered dither algorithm (ordered dither)
In this screening algorithm, the input image is compared to a periodic threshold matrix (or called a screening matrix). A threshold matrix, where N defines the period of the threshold matrix.
For a particular threshold matrix t(n), its ordered jitter screening algorithm can be described as follows:
(1)The input image should be normalized, ie 0 ≤ x(n) ≤ 1. When h(n)=0, the halftone output pixel is a white point, and when h(n)=1, the halftone out pixel is a black dot. The threshold matrix determines the order in which the dots become black dots as the brightness decreases, which 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 divided into point-aggregated ordered jitter and point-discrete ordered jitter. The screening matrix of point-gathered ordered jitter is carefully designed to simulate the halftone processing. When the pixel density of the continuously adjusted image is reduced, the dots will be generated around the pixels. The design rules for point discrete ordered jitter are proposed by Bayer. His research indicates that the visibility of non-ideal artificial textures can be obtained by Fourier analysis of the dot patterns of different brightness levels. When the dot pattern of a uniform color block has components at different wavelengths, the component corresponding to the longest wavelength in the finite wavelength is the component with the highest visibility. Based on this standard, Bayer designed an optimized screening matrix, and the halftone image obtained by applying the point discrete and ordered jitter of this matrix contains more visible details.
Although the point-discrete ordered jitter preserves more details, due to the "addition of dots", point-aggregated ordered jitter is often used in practical applications. The dot gain is caused by the non-ideal nature of the printer, although it can be assumed that an ideal printer can produce dots with pre-defined geometries such as squares, but dots are created due to the diffusion of ink from pre-defined geometries to surrounding pixels. Increase the phenomenon. When the pixel density of the continuously adjusted image is lowered, the dot will be generated from the surrounding pixels, so the dot-gathered ordered jitter is more likely to prevent the dot gain, thereby reducing the dot gain effect in the halftone image as a whole.
Second, the error diffusion algorithm (Error Diffusion)
The error diffusion algorithm is a popular and halftone effect algorithm, which was first proposed by Floyed-Steinberg. This algorithm requires neighborhood processing, which provides a higher halftone quality for the press and does not cause dot gain, resulting in a rich halftone image with an anisotropic distribution of pixels.
The basic idea is to first quantize the image pixels according to a certain scan path threshold, and then spread the quantization error to adjacent unprocessed pixels in a certain way. The schematic diagram of error diffusion is shown in Figure 1.
Figure 1 Error diffusion schematic
Where Q(.) is the threshold quantization function, u(m,n) is the sum of the gray value of the pixel and the partial quantization error. When u(m,n) is greater than the threshold, the Q(.) value is l, otherwise the value is Is 0. e(m,n) is the quantization error, x(m,n) is the input signal, x(m,n)∈[0,1]. Threshold processing of u(m,n) results in a representation signal b(m,n), b(m,n)∈[0,1]. H is an error diffusion filter with a filter coefficient of h(k, l) and is present.
The error diffusion algorithm can be expressed by the following formula:(2)-(4)
Third, point diffusion method (Dot Diffusion)
The point spread halftone algorithm proposed by Knuth is an algorithm that provides parallel processing while attempting to preserve the advantages of error diffusion. The point spread algorithm has only one design parameter, the class matrix C, which determines the order in which the pixels are processed by halftones. The position of a continuous tone image pixel is divided into IJ classes, and I and J are invariant integers. Table 1 is an example of a classic matrix with 64 numbers in the table.
Table 1 8×8 optimization class matrix
To define a continuous tone image whose pixel values are normalized, for a fixed k, we process all pixels belonging to class k and define halftone pixel values as follows:
(5)The error, by observing the eight fields, replaces the continuous tone values of those neighborhoods with higher class numbers with the original continuous tone image pixel values (for example, those that have not been processed by halftones). In short, a neighborhood with a higher number of classes is replaced with:
For right-angle neighborhoods, (6-a)
For diagonal neighborhoods, (6-b)
Among them, it is to ensure that the sum of errors added to all neighborhoods is exactly. The right-angle neighborhood has an additional parameter 2 because the errors in the horizontal and vertical directions are more noticeable than the errors in the diagonal direction.
After that, the continuous tone pixel with the class number k+1 is also treated similarly. The current pixel value is no longer the original continuous tone pixel value, but is adjusted according to the formula (6). After the algorithm is aborted, The signal is a halftone result.
Figure 2 Error spreads from one pixel to the neighborhood
Figure 2 illustrates the process of point spread. The numbers in the matrix are the elements of the class matrix, the circled numbers are the associated weight values of the diffusion coefficients, and the neighborhoods with higher class numbers of 33 are 58, 45, 42, 40. , 63, 47. The error produced at 33 is divided into corresponding aliquots according to the sum of the correlation weights of the diffusion coefficients, which in this example is 2+1+2+1+2+1=9. Then assign e in the right-angle neighborhood and 2e in the diagonal neighborhood. Since there are 64 levels in total, the algorithm is completed in 64 steps.
Fourth, iterative halftone algorithm
The idea of the iterative halftone algorithm is to first obtain the initial halftone image by a simple method, and then iteratively process the initial halftone image, so that the halftone image obtained by each process has smaller error, and finally the visual maximum. 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 is capable of correctly reproducing rich tones. However, based on the computational complexity of this algorithm, the iterative halftone algorithm is generally difficult to use in real-time processing and can only be used as a standard test program.
The direct binary search method (DBS) applies an HVS model and a device model to reduce the visible error between the rendered halftone image and the continuous tone image. The HVS model is represented by a linear shift invariant low pass filter. The frequency response of this filter is defined as follows:
(7)
Where is the frequency variable of the corresponding angle of the retina, L is the average brightness, c = 0.525 d = 3.91.
Let e[m,n] define the error image and define (8)
Where f[m,n] is a continuous tone image and g[m,n] is a corresponding halftone image, the visible error between the halftone image and the continuous tone image can be expressed as (9)
Where X corresponds to the raster of the addressable point of the output device; and the printed point is convolved with the filter, we will assume a larger range.
The total error between the entire halftone image produced by DBS and the original image is:
(10)Substituting (9) into (10), E can be calculated as follows
(11)Among them is the cross correction function between the discrete points of the printable grid.
DBS uses an iterative exchange program to reduce the error E. This algorithm scans the entire halftone image in order from left to right and top to bottom, starting from the randomly obtained initial halftone image, for each of the halftone images. The pixel evaluates the effect of inverting the pixel and the value of the halftone image obtained by exchanging its value with the surrounding eight pixels. If any of the changes reduces the error, the transformation that causes the error reduction is preserved, and the above process is repeatedly performed on the halftone image until the entire process has no transformation operation, and the DBS algorithm ends.
V. Summary
In general, in these halftone algorithms, the best halftone image quality produced is an iterative algorithm, but due to the complexity of the computation, it is generally not used in real-time processing algorithms. The error diffusion algorithm is currently the most popular halftone algorithm, and the resulting halftone image has no obvious moiré and good visual effect. The dithering algorithm is simple to implement, but it has certain defects in tone reproduction, spatial resolution and visible texture. The point spread algorithm implements parallel processing, but the quality of halftone image needs to be improved.