Research on Multiplicative Congruence and Pseudo-random Frequency Modulation Screening Method(I)

Abstract : This paper studies the basic principles and techniques of frequency-modulated screening in color desktop publishing system with the aid of existing amplitude-modulated screening RIP and multiplicative congruence pseudo-random number sequence distribution elements. The multiplicative congruential method is used to generate the pseudo-random number sequence, and the correct selection method of the X0, A, M parameters of the multiplicative congruential random function suitable for frequency-modulated screening requirements is found out. Studies have shown that using a pseudo-random function, the color separation of the image file is frequency-modulated and screened, and then the existing amplitude modulation screening RIP can achieve the output of the image's frequency modulation and screening; by selecting different starting points of the random number sequence, Or use different random number sequences to ensure that no texture phenomenon occurs in the same area with large grayscale values ​​in the image.

Keywords: frequency modulation screening; amplitude modulation screening; multiplicative congruence; pseudo-random number; raster image processor

Dot technology is the basic way to reproduce continuous tone images. At present, in the lithography and letterpress printing that are generally used, in principle, the ink film thickness at the ink dot-net is certain, and the tone and color of the image are expressed by changing the dot size (area ratio) of the separation dot. , the so-called halftone technology. The traditional screening technology is characterized in that the dot spacing is fixed (determined by the number of screens), the dot is concentrated in the center of the grid, and its area size (corresponding to the strength or amplitude of the carrier signal in the electronic system) is a function of the tone information. It is called AMS-Amplitude Modulation Screening. For more than one hundred years, AM has experienced the development of glass screens, contact screens, and dot-net generators. It has formed rational grids, irrational grids, and composite grids, etc. [6]. From the 90s to the 1990s, the amplitude-modulated screening technology was basically mature. Due to the regular distribution of dots, it is determined that the amplitude modulation screen is easy to generate interference fringes when the amplitude modulation screening is used for multicolor printing. The screen angle of the color separation must be strictly controlled, and the midtone tone shift occurs due to the corners of the dots. When the number of screen lines is low, Loss of image detail, these drawbacks restrict the development of color reproduction technology.

FM screening is a brand-new technology that began research in the early 1980s and was introduced into the market in the 1990s [6,8,9]. It is characterized by the fact that in the unit area (mesh) that corresponds to the amplitude modulation dot, Names are not uniform, in this article are called point elements) the size is the same, the location is randomly distributed, the degree of density of its distribution, that is, the frequency of spatial distribution is a function of image tone information, so it is called frequency modulation screening (FMS-FrequencyModulationScreening). ). In the image of FM screening, there are only a certain number of randomly distributed point elements in the unit mesh. As a whole, there is no visible “net point” in the traditional grid. The distribution of point elements is irregular, so there is no problem with the angle of the screen. Basically eliminates the interference fringes, there is no intermediate level jump phenomenon, and the level reproduction is even and beautiful. Since the dot element is small, the resolution and sharpness of the image are greatly improved, and the fine resolution of the high-resolution amplitude modulation net can be obtained with a low resolution, and the overlay of the high-resolution point elements is small, so that the print quality can be increased. Because there is no concept of screen angle, the overprint accuracy of printing equipment is not high, which provides the possibility for ordinary printing houses to print high-quality color printing products with mid-range laser imagesetters and printers [7]. Because of its prominent advantages, FM screening technology has received people's attention as soon as it appears. The rapid development over the past few years, AGFA, Linotype-Hell, UGRA/KOHAN, Japan Screen, and other companies have launched their own FM screening technology, in the offset printing, flexographic printing, news printing and other fields have excellent development prospects. However, due to the small number of ink-jet screens for FM screens, the requirements for paper, ink, and equipment are high, and there are problems in promotion and application. It is an urgent task for the printing industry in China to research and develop FM screening theory and technology suitable for general printing conditions and to promote it in production.

1 point element random distribution principle

Figure 1 is a schematic diagram of the contrast between the amplitude modulation network point and the FM network point when the gray value is 24 (the number of dots is 8×8 and the number of gray levels is 64+1). When using the laser electronic screening system to realize amplitude modulation and screening, the gray value of the pixel of the input image is compared with the screening threshold value in the dot model memory (SPM). If the former is greater than or equal to the latter, the laser beam is exposed and generated. Make ink, otherwise it will not be exposed. The screening threshold is regularly arranged in the cell grid. From the center of the grid to the edge of the grid, the screening threshold is gradually increased from small to large, so as to ensure that the dots formed by the pixel's gray value are small to large. The center of the grid expands around until it fills the entire grid [1]. It can be seen that to make the ink dots randomly distributed in the grid, the key is to break the threshold distribution rule in the dot pattern memory so that a certain number of ink dots determined by the gray value of the input image pixels are in the unit network. The grid randomly and uniformly spreads out, ie, a random number sequence of distribution point elements is established within the unit grid. The right side of FIG. 1 shows the distribution order of the FM screening point elements implemented by some algorithm. However, in order to avoid the similar distribution of the dot positions of the same gray value, the fixed dot pattern memory is generally not used in FM screening. Even if the pixel gray value is the same, the number of point elements is the same, but the order of the distribution may be different, thereby realizing Random screening.

Generating a real random number generally requires the use of physical methods, such as the use of radioactive material, or the inherent noise of an electronic computer. However, such a sequence of random numbers cannot be duplicated and cannot be recalculated by the program, and verification is difficult. Furthermore, it is expensive to add additional equipment such as random number generators and circuit links [2]. Therefore, it is practically all to use the mathematical recurrence formula to generate, for a given initial value ξ1, determine ξn+1 (n=1, 2,...). This method is semi-empirical in nature and can only be approximated by random numbers, so it is called pseudo-random number. The use of pseudo-random numbers has two major problems: First, after the recursive formula and the initial value are determined, the entire random number sequence is also uniquely determined, ie, the requirements for independent random numbers cannot be satisfied; second, the resulting random numbers exist. Cyclical cycling. Therefore, when using the pseudo-random method to implement stochastic screening, we must appropriately choose the recursive formula that generates pseudo-random numbers, strive to improve the independence of the pseudo-random number, and distribute evenly over the grid, and we must ensure the period of the pseudo-random number. Greater than the total number of points in the grid.

2 Multiplicative Congruence Pseudo-random Screening Method

Since the primary goal of this study is to explore the basic techniques for implementing FM screening in DTP systems, detailed comparisons of recursive formulas are left for later. Therefore, in the mathematical method of generating pseudo-random numbers, the author prefers the method of multiplicative congruence with better statistical properties, convenient and rapid generation of random numbers, and wider use. The recurrence formula is Xi+1=AXi(modM)(2). That is, the next random number is obtained by multiplying the previous random number by the A-to-M remainder, and is called the multiplicative congruential method. In the multiplicative congruence method, how to use the three parameters X0, A, and M is the key to determining whether it can quickly generate a random number sequence that meets the requirements. According to the literature [2][3][4], it is usually M=2l A=8q±3 X0=2t+1(3) where l, q, and t all take positive integers, and require M and X0 to be prime, X0 is coprime with A [2]. Literature [3] pointed out that M in equation (3) is actually a period of random numbers that can be generated. The required number of random numbers is smaller than the number of random numbers that can be generated. Generally, the number of required random numbers is M/. 4, and the coefficient A generally takes the closest value to A 2l/2 while satisfying the formula A=8q±3. For random screening, the dot matrix structure usually takes 16×16, and the random number is between 1 and 256. Therefore, we take M=256×4=1024, that is, l=10. And 2l/2=210/2=32, take A=35,29,43,37,27,21 (ie, q is 4, 5, 3 respectively), take X0=1, and calculate the result as shown in Table 1. Show. If you use 256 more than 256 random numbers, each random number appears 4 times. X0 takes the same result as the other odd numbers, and when the even number is taken, the period T becomes smaller. This shows that the parameters cannot be selected as such. Document [4] pointed out that taking M = 2l, where l is the length of a digit tail on a digital computer, the maximum possible period for generating a random number is T = 2l-2. Theoretical analysis and statistical tests show that when the value of A is too small or its binary form is arranged in a regular manner, no statistically ideal random number sequence can be generated. Especially for multiplicative congruential method: A=52s+1(4)

From Table 2, we can see that although the maximum number of cycles is as described in [3], T=2l-2, the number of random numbers between 1 and 256 is 64, and the remainder cannot be used directly, even if 256 is used again. It is also the case that multiple codes appear, so the parameters cannot be used this way.

After repeated experiments, the author found that when M takes about 2 l prime numbers, such as M = 1021, 1019, 1033, A takes a proper positive integer (even number, odd number can be), the maximum period of random numbers generated is T = M- 1, a random positive integer less than 256 is exactly 256 (proof of mathematics proof about the maximal period of the pseudo-random number generated by an arbitrary prime M, equal to M-1, as discussed elsewhere).