Optimal color half-tone patterns for raster-scan images.

BACKGROUND OF THE INVENTION

Field of the Invention

The invention relates to the making of half-tone images of colored originals with reduced Moire effects for printing purposes. More particularly it relates to methods by which the original is scanned optically point by point and the readings obtained are converted to digital form from which the half-tone version is constructed by electronic means, often by computer. The computed half-tone signals are then presented to a printing plate or intermediate imaging material by a further scanning procedure.

Of particular importance in colored images are possible unacceptable Moire effects resulting from the use of several superimposed half-tone images for the different color separations. In the older half-tone technique where physical half-tone screens were used, these Moire patterns were reduced to imperceptible levels by crossing the screens for the several colors at specific angles whose values for three or four color printing were quite critical. This technique is not available where there are no physical screens as in laser printed images.

Background of the Invention

In the art of printing, half-tone systems have long been used to represent pictorial subjects where tone gradation is important. This was and frequently still is accomplished by the use of a photomechanical system in which a fine cross-hatch screen covers the pictorial image during exposure at a suitable stage in the photographic process leading to the printing plate. By this means the image is divided up into a multitude of regularly spaced very small (subliminal) dots whose size varies with the image density being reproduced. With the use of full color printing of subjects, three or four printing plates, one for each of the separate primary color images have to be prepared. The use of identical half-tone screens for each of these color separations can result in very pronounced and objectionable Moire patterns when the several successive print impressions are made. These Moire effects can be reduced to imperceptible levels by crossing the screen directions with one another. In the practice of the art it has long been known that a suitable set of screen angles for four color printing is 45°, 0°, +15°, and -15° (See reference to this art in Chapter 13 of "Principles of Color Reproduction", by J. A. _G. Yule, John Wiley & Sons Inc. NY., 1967).

In the conventional half-tone system, the original continuous tone picture is represented in the print by regularly spaced high density dots of ink. The dots are sufficiently closely spaced that the unaided human eye cannot distinguish them. The changing size of the dots give the impression of changing tone, and by suitable control of the process the original tones can be reproduced faithfully. With full color originals, suitable control of the process of making the individual half-tone color separations can give faithful reproductions in full color. These photomechanical processes are slow and painstaking, particularly when high quality results requiring considerable manual correction and human judgement are involved.

The transmission of images over telegraph wires based on a process of photoelectric raster scanning was introduced early in the twentieth century. It was also applied to transmitting color images (U.S. 2,185,806; U.S. 2,413,706). The application of this technique to half-tone plate making by Hardy and others (U.S. 2,136,340; _U._S. 2,190,185; U.S. 2,190,186; U.S. 2,294,644) heralded an era of faster and more automatic plate making and correction. Methods were developed for scanning colored originals (U._S. 2,165,168; _U._S. 2,253,086; U.S. 2,571,322) and treating the readings and output by analog devices to produce color separations suitable for color printing plate making with a considerable saving in time.

The combination of these two techniques for the making of color half-tone images was found to suffer from the Moire pattern problem known earlier to photomechanical plate makers. Wurzburg (U.S. 2,185,139) made color half-tone separations by the photoelectric raster scanning methods, where he physically rotated both the original picture and the reproduction on the raster scanning devices to give different equivalent screen angles for the different colors. Screen angle choice was based on the photomechanical art already existing.

In the photoelectric raster scanning systems, conversion of analogue scanning signals to digital form was found to facilitate manipulation of the signals by computing circuits, as in the electronic formation of half-tone dot patterns (U.S. 3,629,496). Such methods gave color originals suffering from Moire patterns in the resulting prints. Patterns of dots of equal size but with separation distances depending on density in the original were found to reduce the Moire patterns (U.S. 3,197,558; U.S. 3,580,995) because of the absence of repeating patterns of dots. Direct simulation of the use in color work of four contact screens at different screen angles has been achieved by computing techniques coupled with four different dot generators (U.S. 3,911,480). Choice of the angles used is based on earlier experience with contact screens.

A different approach has been taken to the problems presented by photoelectric scanning methods. This involves the representation of a variable size half-tone dot by a matrix of smaller dots whose number in the matrix is varied to provide half-tone dot size changes and therefore density changes. (U.S. 3,604,486; U.S. 4,439,789). No change of size or optical density of these smaller dots is involved. Only their presence or absence is considered. This system therefore lends itself to the use of digital signals and their attendant high speed computing means. Enhanced tonal reproduction has been achieved by using a variable pixel area (the area assigned to a single matrix unit) in such matrix systems (U.S. 4,084,259).

In four color printing the separations have been represented by matrix pixels in which the distribution of dots for the same density is varied from one separation to another. This is said to reduce Moire effects (U.S. 3,922,484). This technique of Moire reduction has been expanded by randomizing the distribution of dots in the pixel matrix (U.S. 4,468,706) building on earlier monochrome work (U.S. 3,629,496).

The randomized pixel matrix method of reducing Moire effects has been approached in a separate manner often termed "ordered dither". The raster scan identifies signals corresponding to all the dot positions in the pixel matrix but the presence or absence of a dot in the reproduction is determined by a predetermined matrix of threshold values - one for each dot position in the pixel matrix (U.S. 4,193,096: U.S. 4,342,051; U.S. 4,496,987).

As was reported above, U.S. 2,185,139 and U.S. 3,911,480 describe raster scan methods to reduce Moire effects which generate half-tone screen dots with different screen angles for the different color separations. This method has been enhanced in U.S. 4,419,690. A variation to this method has been taught in U.S. Patent 4,443,060 wherein quadratic raster meshes of adjacent dots are expanded or contracted in their two diagonal directions. Different expansions/contractions are used for the different color separations.

The non-patent literature contains considerable detailed discussion of the application of raster scanning to half-tone image production. The following papers are representative: "Half-tone Method with Edge Enhancement and Moire Suppression", P.G. Roetling, JOSA 66, 985 (1976). In this method, detail corresponding to the spatial frequency of the half-tone screens is suppressed. "Random Nucleated Halftone Screen," J. P. Allebach, PS & E 22.89 (1978). These screens suppress Moire effects by the introduction of random elements.

"An Optimum Algorithm for half-tone Generation for Displays and Hard Copies," T. M. Holladay, Proc. Soc. for Information Display, 21., 185 (1980). This describes electronically produced screens with different screen angles.

"A New Evaluation Method of Image Quality of Digital Halftone Images Obtained by Ordered Dither Method", _K. Kinoshita et al., _J. Imaging Technology, 10.181 (1984).

The present invention approaches the problem of Moire fringes in color half-tone images from the standpoint that the mathematical functions describing the half-tone patterns for the individual separations should be orthogonal with one another. There appears to have been no earlier disclosure of such an approach and none of the mathematical investigations in the literature suggest such an approach.

SUMMARY OF THE INVENTION

The invention provides a method of designing screen functions for raster-scan generated sets of images comprising two or more color separation images, which sets of generated images have reduced Moire patterns or are free from Moire pattern problems. The method does not use the equivalent of different screen angles for the separations nor is the technique of ordered dither used. The half-tone dot matrixes in a given separation are disposed at a single uniform pitch not at variable pitch as taught in some of the known art.

To readily understand the practice of the present invention, many of the terms used in this area of technology should be defined and understood. The term "font" was first used in imaging or printing technology to distinguish between complete sets of printing characters, either by style and/or size. Italics are, for example, a type of font, distinguishable from Gothic. With changes in technology, the use of the term font has also changed. With respect to raster-scan images, font refers to the style and size of the smallest image area, the pixel. The style and size of the pixel are determined by the number, size and arrangement of digital dots within each pixel. It is generally assumed in the use of the term font that for each of the four respective color images, there should be shared common characteristics. These common characteristics, when applied to half-toning a real image, result in a consistent half-tone texture for all tonal values.

As is well understood in the art, the pixel is the smallest area of informational content within the picture or image. The pixel is also referred to in raster-scan images as a composite of digital dots. The composites or pixels contain digital dots of a predetermined size, number and array. The periodic spacing of the centers of these pixels is determined by the screen function. The digital half-tone process produces a binary half-tone image by applying a threshold requirement periodically, the periodicity of the applied requirement corresponds to dimensions within the image. This in effect creates a mathematical half-tone screen. At each addressable point, a two-dimensional array of threshold values is used to determine if that addressable point should be made black or remain white. The period over which this threshold value is applied is determined by the screen function. The screen function may extend over several continuous tone image pixels, or may include only a fraction of a single pixel, depending upon the scale of the image and the number of pixels. The screen functions are either algebraic, numeric or mathematic representations and can have different fundamental frequencies in the X and Y dimensions. The screen functions include within themselves the frequency spectrum description of the font chosen.

When half-tone patterns are created by a raster-scan device, there must eventually be some periodicity in x and y directions. Any change in color mixing that occurs within this "longest period" cell then repeats over the print. If there is some net shift (registration) dependent color bias in this cell, the same error repeats across the image giving some global color error. A worse situation exists, if the shift does not remain constant over the image, for then the color error slowly changes from cell to cell, producing color Moire.

This invention presents a method of reducing color Moire by picking functions for the half-tone patterns that produce within each cell the same degree of color overlap regardless of the registration of the color separations. Such "orthogonal" functions can be defined in small cells and in the Cartesian coordinate system so natural to the raster-scan process. The color bias in each cell is reduced to zero so that no global color error results. If there is no error within each cell, regardless of registration in each cell, there will be no slowly varying color bands produced when registration is not constant across the image.

Certain definitions are particularly useful in understanding the present invention. Cross-correlation of two mathematic functions describing the spatial array of two superimposed screen patterns is defined as the normalized summation over the whole area of the patterns of the point by point product of the two functions. Cross-correlation function is here defined as the formulaic or numerical representation of values of cross-correlation between the two screen functions as one screen function is moved relative to the other along each of the rectangular lines characterizing columns and rows of half-tone dots. Orthogonal - Two math functions are orthogonal when the cross-correlation function is a constant, including zero, for all values of displacement.

The difficulty in using such orthogonal functions is that they show ideal color mixing only for a particular combination of tones. It is necessary to keep the same basic half-tone pattern as tonal values increase or decrease to avoid texture changes in the background half-tone functions. This means that orthogonal basis functions must be chosen to be fairly robust, exhibiting similar color mixing properties for a wide range of dot sizes with the dot centers remaining in the same relative locations.

A good measure of the color mixing properties of different half-tone functions is given by the average cross-correlation function. The total area is known a priori as the relative area covered by at least two colors of ink, as for example the relative area covered by cyan ink and the relative area covered by magenta ink. The relative amounts of white, pure cyan, pure magenta, and cyan plus magenta areas (and hence the net color), are determined by measuring (or calculating) just one of these parameters. The relative pure white area can then be associated with the average cross-correlation function of the half-tone patterns. By calculating this cross-correlation for different combinations of tone values of the different colors, a fairly good idea of how the half-tone functions will perform with a real image can be obtained.

Generalized mathematical analysis along these lines shows that pairs of screen functions satisfying the requirements will be characterized by the fact that at least one screen function must have an even number of repeat distances in the cell. This criterion is not sufficient to ensure that images formed by the screen functions will be Moire free. The requirement may vary with the color densities (half tone dot size) and with the font (rules for distributing the spots within the half-tone dot matrix as the tone varies).

This invention teaches, therefore, that the choice of the optimum screen functions chosen from the ensemble given by the mathematical analysis described above, can be made by numerically evaluating the white area fraction for the cell for various registration off-sets of the two color half-tone functions. Using a computer and a simple computer program, this can be done for a number of off-sets in the two major cartesian directions x and y of the raster scan. Uniformity of the white area fraction over the range of off-sets then indicates an absence of Moire problem. The procedure is carried our for various tone level combinations of the colors using the half-tone font intended for the imaging process. When three or four screen color separations are being used, this series of calculations is carried out for each possible pair of screen patterns in the set. From these results a final choice of suitable screen functions is made.

DESCRIPTION OF THE DIAGRAMS

<ul id="ul0001" list-style="none"><li>Figure 1 illustrates a repeat distance cell comprising an array of 24x24 digital image units. These have been addressed in this case to give 50% half-tone dots of which there are exactly two in each direction.</li><li>Figures 2(1) through 2(9) show various half-tone patterns representing mathematic equivalents of digital image units.</li></ul>

DETAILED DESCRIPTION OF THE INVENTION

As was described above the choice of optimum screen functions is taken in the following major steps: <ul id="ul0002" list-style="none"><li>1. Select fonts and associated screen functions for the several color separations.</li><li>2. Select a finite repeat cell for each possible combination of screen functions, the cell width and height of each cell containing an even number of cycles of at least one of the two screen functions in each of the two directions (columns and rows).</li><li>3. Compute the white area fraction for each screen combination at a series of off-set values (i.e., values indicating some lack of registration), and repeat the computation for a number of tone combinations of the color separations.</li><li>4. If the white area fraction uniformity is not sufficiently good (i.e., reducing the variation in the white area fraction as the offset is varied and registration is changed, the better the color constancy), return to step 2 and select further screen functions.</li></ul>

The Ensemble of Screen Functions for Step 2

The raster screened functions in one dimension f₁(x), f₂(x), etc. may be represented by rectangular pulse trains of unit amplitude, the value 0 representing a colored area and the value 1 representing a white area. For two screen functions having a₁ and a₂ complete cycles in the minimum repeat cell length L (chosen so that a₁ and a₂ have no common factor) the Fourier decomposition of the first function is given by <chemistry id="chem0001" num="0001"><img file="EP0254448A2_D0001.tif" /></chemistry>where ω₀ = 2n and m is an integer, L and similarly for f₂(x), where d_l and d₂ are the respective pulse widths.

The coincidence area where both functions provide color, as a function of the registration offset of the screens, t, is given by the average cross-correlation function of the two screen functions <chemistry id="chem0002" num="0002"><img file="EP0254448A2_D0002.tif" /></chemistry>where k is an integer and the discrete frequency components are at multiples of ω'₀ = a₁a₂ω₀.

The Fourier transform of the cross-correlation function is <chemistry id="chem0003" num="0003"><img file="EP0254448A2_D0003.tif" /></chemistry>

In the case of 50% half-tone dots <chemistry id="chem0004" num="0004"><img file="EP0254448A2_D0004.tif" /></chemistry>and thus <chemistry id="chem0005" num="0005"><img file="EP0254448A2_D0005.tif" /></chemistry>

To make the average cross-correlation function a constant independent of t, at least one of a₁ or a₂ must be even. We then get an invariant white area fraction over the cell and therefore no Moire effect.

Two dimensional screen functions introduce considerable complexity into the analysis but we may illustrate the results by the particular case where the screen function h (x,y) is given by <ul id="ul0003" list-style="none"><li>h_n(x.y) = f_n(x).gn^(y) in which</li><li>f_n(x) has pulse width d_n and an cycles per cell length L</li><li>g (y) has pulse width wand b_n cycles per cell length L</li></ul> where the subscript n represents the individual color separation screens.

It can be shown that the average cross-correlation function for square waves (50% half-tone functions) for offsets u and v in the x and y direction is ^R₁₂(u,v) ₌<chemistry id="chem0006" num="0006"><img file="EP0254448A2_D0006.tif" /></chemistry>to make R₁₂ (u,v) constant, independent of "registration" offsets u and v, either 1) at least one of a₁ and a₂ must be even, and/or 2) at least one of b_l and b₂ must be even.

This is a very specialized case, but provides a good staring criterion for designing two-dimensional half-tone patterns with good color mixing properties.

The general case for two-dimensional patterns becomes too complex for any closed-form expression for cross-correlation to be readily helpful. It is more practical, in general, to write a simple program to evaluate numerically the "% white area" for various registration offsets of two color half-tone functions.

Remembering that the screen functions give 0 for color areas and 1 for white, the fractional white area over a cell L by M units may be calculated by the summations <chemistry id="chem0007" num="0007"><img file="EP0254448A2_D0007.tif" /></chemistry>Figure 1 shows an example cell for one screen function. In this case there are 24 x 24 sub-units in the cell. The value of W(u,v) is evaluated over the L and M values of (u,v) covering the repeat distances of the cell. Uniformity of these values over the whole range of (u,v) values indicates no color variation over the cell and hence over any combination of cells.

This has been done in the Examples below and has proven a useful tool in a more rigorous evaluation of half- tone patterns for color printing. The initial design of the patterns follows the criterion for optimum color mixing in the "square wave" case which for two color patterns each individually covering 50%, should leave 25% "white" area regardless of registration. The numerical evaluation program then helps determine how robust the patterns are, that is, how well they maintain uniform color mixing for non-50% cases. The goal is to design patterns that show a nearly constant white area for various combinations of tones independent of registration effects.

While it was shown that only one of f_l(x), ^g_l(^y), f₂(x), and 9_?(y) is required to have an even number of cycles per half-tone cell for registration independent color mixing at 50%, practical examples show the more robust patterns to be those where one of the "x" functions and one of the "y" functions have an even number of cycles per cell.

With a set of four color separations A, B, C, and D these white fraction calculations must be satisfied for all pairs of screens, AB, BC, CD, AD, BD, CA. Very effective color Moire suppression has been achieved for a real test image using 12 x 12 half-tone matrixes, optimized using this program.

The following examples of calculated white fractions illustrate the evaluation and selection of screen functions.

The figures representing the half-tone patterns of Examples 1-9 are shown as Figures 2(1) through 2(9).

Examples 1 and 2 illustrate the effects expected from identical half-tone pattern frequencies used for the pair of separations. Substantial variations in white area percentage is seen in these results. Examples 3-6 illustrate an orthogonal pair of patterns exhibiting "robustness" i.e., no change in the high uniformity of white percent as the half-tone densities are varied.

Examples 7-9 illustrate an orthogonal pair of patterns showing perfect uniformity of white percentage at 50% dot areas but significant white percent variation at other half-tone densities.

Example 1

Fig. 2(1) Identical half-tone patterns at 50% showing potential color variation vs. registration. <tables id="tabl0001" num="0001"><img file="EP0254448A2_D0008.tif" /></tables>

Example 2

Fig. 2(2) Identical half-tone patterns at different densities, still color variations. <tables id="tabl0002" num="0002"><img file="EP0254448A2_D0009.tif" /></tables>

Example 3

_Fig. 2(3) "Orthogonal" half-tone patterns at 50% showing ideal color mixing - no registration dependence. <tables id="tabl0003" num="0003"><img file="EP0254448A2_D0010.tif" /></tables>

Example 4

Fig. 2(4) Same orthogonal patterns as Example 3 but now for highlight densities - still good color uniformity vs. registration. <tables id="tabl0004" num="0004"><img file="EP0254448A2_D0011.tif" /></tables>

Example 5

Fig. 2(5) Same patterns as Example 3 but for combined shadow/highlight densities - again, good uniformity. <tables id="tabl0005" num="0005"><img file="EP0254448A2_D0012.tif" /></tables>

Example 6

Fig. 2(6) Same patterns as Example 3 for shadow densities. <tables id="tabl0006" num="0006"><img file="EP0254448A2_D0013.tif" /></tables>

Example 7

Fig. 2(7) Different "orthogonal" patterns at 50% - perfect color mixing. <tables id="tabl0007" num="0007"><img file="EP0254448A2_D0014.tif" /></tables>

Example 8

Fig. 2(8) Same patterns as Example 7 for shadow densities - significant color variation. <tables id="tabl0008" num="0008"><img file="EP0254448A2_D0015.tif" /></tables>

Example 9

Fig. 2(9) Same patterns as Example 7 for highlight densities - again, registration-dependent color shifts. <tables id="tabl0009" num="0009"><img file="EP0254448A2_D0016.tif" /></tables>

A particularly well-suited application of these half-tone patterns has been the printing of four-color ink jet images. The specific ink jet writer used was constrained to addressing only points on a Cartesian grid (as in most raster scan devices), and the areal density of available points is low. Attempts to create well-defined "classical" screen angles resulted in an extremely coarse half-tone texture, but the use of half-tone patterns as described in this patent proposal for the various colors, produced relatively "fine-grained" images without objectionable color Moire patterns.

All half-tone patterns were defined in a 24x24 dot grid. The black separation (which carries most of the image detail information) was half-toned with a pattern using a four-dot period (six cycles per unit cell). The magenta and cyan separations used half-tone functions with 3x4 and 4x3 cycles per unit cell (respectively). Finally, the yellow separation (which has the lowest visibility and generally exhibits the least problems with color Moire) was half-toned with both a fairly coarse two-cycle by two-cycle pattern and a 3x3 cycle pattern.

Both yellow patterns produced images with consistent colors throughout (no obvious color banding or Moire effects). While the 3x3 pattern might be expected to show more interference with the cyan and magenta patterns (due to the common frequency in one dimension), the yellow ink itself was fairly pure and showed little color crosstalk with the others.