Half-Tone Conversion Mask for Digital Images

The present invention relates in general to digital image processing systems and is particularly directed to a mechanism for generating a half-tone image mask through which the encoded grey scale values of respective pixels of a digital image are thresholded to binary values of a half-toned digital image.

Recent improvements in their spatial and data resolution capabilities have made digital image processing systems attractive for a number of photoprocessing applications. In still image photography, for example, once an image (such as a multilevel grey scale image captured on photographic film or a high resolution digital camera) has been digitized and stored in an attendant data base, it is optimized for reproduction by a variety of reproduction devices. Unfortunately, a number of digital image output devices, such as dot matrix printers, laser printers, etc., possess only binary output capability; namely, they can print only two tone (e.g. black and white) images. As a result, in order to reproduce a continuous tone or grey scale image by way of such a device, the grey scale levels of the original digital image must be encoded or `half-toned` into binary values (e.g. 0=black and 1=white), from which respective pixel representative signals are produced.

Because the reduced digital code resolution of the binary values constitutes a significant reduction in image content (loss of grey scale code width), the mechanism through which the half-toning of the original digital image takes place should be designed so that the binary image takes on the appearance of an image having grey scale or continuous tone qualities.

Such a half-toning mechanism may be represented spatially as `dithering` mask M[A][B], or array of A rows and B columns, with entries in the M[i][j] array being greater than or equal to 0.0 and less than 1.0, where [i][j] denotes a pixel location. Also, [i] is greater than or equal to 0 and less than or equal to A, and [j] is greater than or equal to 0 and less than or equal to B. Respective grey scale values of a corresponding array of pixels of the original digital image are compared with entries in the mask. Depending upon whether a respective grey scale value of the digital image is larger than a threshold value of an associated matrix location of the mask, as effectively spatially superimposed upon the digital image, the grey scale value will be converted to a half-tone value of either zero or one.

Thus, when the half-toning mask M is applied to a grey scale-valued pixel of an original image, a half-toned output value H[i][j] may be defined in accordance with the mask M by the condition:

if the grey-scale value at [I][J] is greater than or equal to M[i%A][j%B], then output H[i][j]=0 (black); otherwise output H[i][j]=1 (white),

where i%A denotes the remainder of the integer division i/A, and j%B denotes the remainder of the integer division j/B.

One conventionally employed half-toning mechanism employs a white noise source, such as a pseudo-random number distribution function, to establish the entries of the mask. Because the spectral power of white noise is equally strong at every frequency, the half-toned image tends to contain low frequency, visually disturbing artifacts. One proposal to solve this problem and provide a more desirable masking technique, is described by B. E. Bayer in an article entitled "An optimum method for two-level rendition of continuous-tone pictures," IEEE Int. Conf. Commun., 1:11-15 (1973). The Bayer mechanism takes advantage of the reduced sensitivity of the human visual system to very high frequency signals, by using a family of fixed half-tone masks of sizes 2.sup.m .times.2.sup.m and 2.sup.m+1 .times.2.sup.m, which employ an optimal thresholding criterion involving low spectral power at low frequencies.

Unfortunately, the generation of conventional masks is often computationally intensive and, depending upon image requirements, particularly in the case of very high resolution images (e.g. 1024.times.2048 pixel arrays), the masks themselves may be of such a size as to require an extraordinarily large memory space within which to store the threshold values.

In accordance with the present invention, the complexity of threshold value generation and data entry storage of conventional half-tone masks are substantially simplified by algebraically dispersing the threshold values throughout a dithering half-tone mask array in a manner that avoids the formation clusters of threshold values of nearly the same values, and also allows the threshold values to be either computed and stored for a variety of mask array sizes, or calculated `on the fly` during the half-tone conversion of the original digital image.

Pursuant to the invention, the mask itself is characterized by an N.times.M array of mask value locations associated with at least a portion of the pixels of the digital image. The size of the mask array may contain a relatively small number of pixel locations, which is applied spatially to mutually contiguous subsets or sub-arrays of pixels of a relatively high resolution digital image (e.g. 1024.times.2048). For example, a mask array size of 9.times.13, 13.times.19, 19.times.28, etc., may be fed to half-tone convert mutually adjacent portions of a high spatial resolution grey scale image to a binary output image. (The dimension pairs are relatively prime elements of a third order minimum recurrence, described below.) Although the mask may also be made large enough to encompass the entire image of interest, respective threshold values of the mask may be computed `on the fly` so as to obviate the need to prestore all of the threshold values of the mask.

Each of the locations of the mask array is assigned a respectively different grey scale/half-tone conversion threshold value. These threshold values are distributed among the locations of the mask array in accordance with a two-dimensional analog of the Golden Mean. Specifically, as one proceeds through the mask array, the next sequential location is specified in accordance with fractional parts of integral multiples of a two-dimensional analog of the Golden Mean. Each successive mask location is assigned a respectively different (sequentially larger) grey scale to half-tone conversion threshold. These threshold values are successive integers 0 through K, where K is one less than M.times.N-1. Advantageously, the use of a two-dimensional analog of the Golden Mean to algebraically distribute the threshold values results in a dispersion of successive threshold value integers, so that any half-tone image obtained by the mask is not contaminated with low-frequency, visually disturbing artifacts. In effect, the use of a distribution operator that effectively assigns successive mask coordinate locations in accordance with fractional parts of integral multiples of a two-dimensional analog of the Golden Mean.

In accordance with a preferred embodiment of the invention, a relatively high spatial resolution mask having a two-dimensional size of 1278.times.1873 has been found to both approximate one of the coordinate fractional factors of the distribution operator with very low error (the ratio 1873/1278 approximates the coordinate fractional factor to seven decimal places, i.e. the error is on the order of 3.times.10.sup.-8), and to produce output images that have been observed by the human visual system to possess high grey level quality.

FIG. 1 diagrammatically illustrates a digitizing apparatus of the type described in U.S. patent application Ser. No. 582,305, filed Sep. 14, 1990, now U.S. Pat. No. 5,218,455, issued Jun. 8, 1993, entitled "Multiresolution Digital Imagery Photofinishing System," by S. Kristy, assigned to the assignee of the present application; and

FIG. 2 diagrammatically illustrates the contents of a 13.times.9 embodiment of half tone mask derived by a two-dimensional application of the Golden Mean in accordance with the present invention.

Before describing in detail the improved half-tone conversion mask in accordance with the present invention, it should be observed that the present invention resides primarily in what is effectively a prescribed augmentation of the control software employed by the micro-controller within a digital image processing system, so as to permit a binary-based output device, such as a dot matrix printer, to effectively print a binary image in such a manner that the reproduced image takes on the appearance of an image having grey scale or continuous tone qualities. Consequently, the configuration of the overall system in which the mask of the present invention is employed has been illustrated in the drawings by a readily understandable block diagram, which shows only those specific details that are pertinent to the present invention, so as not to obscure the disclosure with details which will be readily apparent to those skilled in the art having the benefit of the description herein. Thus, the block diagram illustration is primarily intended to illustrate the major components of a digital image processing system in a convenient functional grouping, whereby the present invention may be more readily understood.

FIG. 1 diagrammatically illustrates a digitizing apparatus of the type described in U.S. patent application Ser. No. 582,305, filed Sep. 14, 1990, now U.S. Pat. No. 5,218,455, issued Jun. 8, 1993, entitled "Multiresolution Digital Imagery Photofinishing System," by S. Kristy, assigned to the assignee of the present application and the disclosure of which is herein incorporated. Such an apparatus may employ a high resolution opto-electronic film scanner 12, the output of which is coupled to a an image processing workstation 13 having a host digitized image processor (host computer) 14 and an associated video display terminal (VDT) 15. Scanner 12 may contain a very high resolution sensor pixel array (e.g. a 3072.times.2048 pixel matrix) capable of generating high spatial density-representative output signals which, when converted into digital format, yield `digitized` photographic image files from which high quality prints may be obtained. Scanner 12 is shown as being optically coupled with a photographic recording medium, such as a 35 mm color film strip 16. Film strip 16 may contain plurality (e.g. a set of twenty-four or thirty-six) 36 mm.times.24 mm color image frames. For each scanned image frame, high resolution scanner 12 outputs digitally encoded data, representative of the opto-electronic response of its high resolution imaging sensor pixel array, onto which a respective photographic image frame of film strip 16 is projected by the scanner's input lens system.

This digitally encoded data, or a `digitized` image, is supplied in the form of an imaging pixel array-representative bit map, resolved to a prescribed grey level code width (e.g. eight bits), to a host processor 14. Host processor 14 contains an image encoding and storage operator through which each high resolution digitized image file is stored. Digitized images are retrieved for reproduction by a variety of devices the resolution of which may vary from device to device, such as a digitally driven dot matrix or laser jet printer 18.

Where the digital image output device, such as dot matrix printer 18, possesses only binary output capability, a half tone, thresholding mask is used to convert the eight bit codes (which define the grey levels of the original digital image) into an array of binary values (e.g. 0=black and 1=white), from which respective pixel representative signals for driving the printer are produced. In accordance with the present invention, the mask is constructed such that its threshold values are dispersed algebraically throughout a dithering half-tone array in a manner that avoids the formation of clusters of threshold values of nearly the same values (which would tend to produce localized artifacts in the output image), and also allows the threshold values to be either computed and stored for a variety of mask array sizes, or calculated `on the fly` during the half-tone conversion of the original digital image.

A 9.times.13 embodiment of half tone mask according to the present invention is diagrammatically illustrated in FIG. 2 as comprising an N=9 row.times.M=13 columns array of half-toning threshold values capable of being spatially associated with a two-dimensional portion or segment of the pixels of the digital (grey tone) image. For the size of the mask array of the present example, containing a relatively small number (13.times.9=117) of pixel locations, the mask is applied spatially to mutually contiguous subsets or sub-arrays of pixels of the high resolution digital image (e.g. 1024.times.2048) output by the scanner.

Each of the locations of the mask array is assigned a respectively different grey scale/half-tone conversion threshold value. These threshold values are distributed among the rows and columns of the half-tone mask array in accordance with a two-dimensional analog of the Golden Mean. Specifically, as one proceeds through the (N=9.times.M=13) pixel thresholding locations of the mask array, the next array location in the order of assigning sequentially increasing or incremented threshold values is specified in accordance with fractional parts of integral multiples of a two-dimensional analog of the Golden Mean, to be described more fully below. For N=8, G.sub.n =9 and G.sub.n+1 =13 are two relatively prime adjacent elements of the G sequence. For the 9.times.13 mask array of FIG. 2, such fractional parts correspond to successive matrix increments of delta N=4, delta M=4. (The increment 4 is chosen as the difference G.sub.n +1-SG.sub.n.) Thus, beginning with the upper left hand corner of the mask array as the zeroeth coordinate location (0,0), the threshold value of (0) is assigned. Traversing the matrix in accordance with fractional parts of integral multiples of a two-dimensional analog of the Golden Mean, the next coordinate location of the mask is (4,4) to which the threshold value of (1) is assigned. Continuing through the matrix in accordance with fractional parts of integral multiples of a two-dimensional analog of the Golden Mean, the next coordinate location of the mask is (8,8) to which the threshold value of (2) is assigned. The next coordinate location is (12,12), which is modulo-translated in accordance with the size of the mask to the coordinate location (12,3) to which the next numerical value in the sequence from zero to (N.times.M-1) or (3) is assigned. This process is repeated until all 117 successive values of the mask have been assigned. Namely, each successive mask location is assigned a respectively different (sequentially larger) grey scale to half-tone conversion threshold. These threshold values are successive integers 0 through K, where K is one less than M.times.N. In practice, these numbers are to be considered scaled to interval 0-1 by division by M-1.

A close examination of the threshold value distribution within the 13.times.9 mask array of FIG. 2 reveals the non-clustering, dispersive property of the use of a two-dimensional application of the Golden Mean in accordance with the present invention. Among the 13 columns of the array, numerically successive values of the mask are optimally spatially spread apart from one another, so that `clumps` of nearly equal threshold values do not occur. As an example for a sequence of values the range of which is an order of magnitude fraction of the range of the set of values of which the entire mask is comprised, for example values 0-12 out of the mask set of values 0-117, each of values 0,1,2, . . . 11,12 is associated with a respectively different column of the mask array and at a row position that effectively spatially spreads the value set. An examination of the matrix reveals that the same is true of successive sets of thirteen values of the range.

Advantageously, the use of a two-dimensional analog of the Golden Mean to algebraically distribute the threshold values yields a spatial dispersion of successive threshold value integers, so that clusters or clumps of threshold values of nearly the same value are avoided, and any half-tone image obtained by the mask is not contaminated with low-frequency, visually disturbing artifacts. In effect, the use of a distribution operator that effectively assigns successive mask coordinate locations in accordance with fractional parts of integral multiples of a two-dimensional analog of the Golden Mean results in each sequential mask value coordinate being definable in terms of an analog of the Fibonacci sequence given by G.sub.1 =G.sub.2 =G.sub.=3 =1 and G.sub.n =G.sub.n-1 +G.sub.n-3 for N>3.

As noted previously, pursuant to a preferred embodiment of the invention, a relatively high spatial resolution mask having a two-dimensional size of 1278.times.1873 has been found to both approximate one of the coordinate fractional factors of the distribution operator with very low error (the ratio 1873/1278 approximates the coordinate fractional factor to seven decimal places, i e the error is on the order of 3.times.10.sup.-8) and will produce output images that have been observed by the human visual system to possess high grey level quality.

Using two adjacent, relatively prime elements in the G sequence: G.sub.8 =9 and G.sub.9 =13, the 13.times.9 embodiment of half tone mask diagrammatically illustrated in FIG. 2 may be derived by the use of the C-language computer code sequence set forth in Table 1, below.

Where run-time computation for storage space is an issue, the mask values may be calculated as a function of the pixel coordinates at the time the mask value for that coordinate is required. With reference to the mask threshold values set forth in Table 1, for the 13.times.9 mask of the present example, the top (zeroeth) row of the mask array consists of multiples of the column size, and the left (zeroeth) column of a mask consists of multiples of the row size. The mask takes the form of an addition table modulo A.times.B; i.e. M[i][j]=M[i][0]+M[0][j] modulo A.times.B. Thus, a considerable savings in memory is realizable by simply computing and saving the mask threshold value and saving the row zero and column zero of the mask (A+B locations instead of A.times.B).

However, the calculations of M[i][0] and M[0][j] may be easily carried out only as they are needed (with the opportunity also of removing calculations from nested `for` loops to achieve run-time performance). Both row zero and column zero are the arithmetic progressions (modulo A.times.B):

M[0][j]=j M[0][1] M[i][0]=i M[1][0].

The two numbers, M[0][1] and M[1][0], expressed as the code constants change.sub.-- on.sub.-- move.sub.-- right and change.sub.-- on.sub.-- move.sub.-- down, respectively, in the C-language routine, set forth below in Table 2, may be readily determined using the Euclidean algorithm (the gcd algorithm).

It should be observed that the pair of operations consisting of addition of a constant followed by the conditional `subtract 1` can be implemented in hardware by computing two possible right-hand sides (for the first pair, these are M+col.sub.-- delta and M+(col.sub.-- delta-1)) and choosing the second one, if and only if that one is positive.

The two numbers, M[0][1] and M[1][0], expressed as the code constants change.sub.-- on-move-right and change.sub.-- on.sub.-- move.sub.-- down, respectively, in the C-language routine, set forth below in Table 2, may be readily determined using the Euclidean algorithm (the god algorithm).

It should be observed that the pair of operations consisting of addition of a constant followed by the conditional 'subtract AB' can be implemented in hardware by computing two possible right-hand sides (for the first pair, these are M+col.sub.-- delta and M+(col delta-1)) and choosing the second one, if and only if that one is positive.

Rather than generate a finite mask of a fixed, and reduced number of threshold values, such as the 13.times.9 array of FIG. 2, which is to be applied to multiple mutually contiguous subsets of the image, an effectively `infinite` mask may be generated using the two-dimensional analog of the Golden Mean directly. In accordance with the present invention, such a two-dimensional Golden Mean-based distribution of successive (increasing) values may be defined as:

M[i][j]=((.alpha.i+.beta.j)),

where ((x)) denotes the fractional portion of x, i.e., ((x))=x-[x],

.alpha. is the unique real root of .alpha.(.alpha.+1).sup.2 =0, and

.beta.=.alpha.(.alpha.+1). .alpha..apprxeq.0.4656 and .beta..apprxeq.0.6823. (.alpha. can be rapidly approximated by Newton's iteration.)

The two-dimensional pair (.alpha.,.beta.) is derived on the basis of an exercise in Diophantine analysis to simulate, in two dimensions, the behavior of the Golden Mean, .tau. in one dimension. .tau..apprxeq.0.618033 satisfies the equation .tau.(.tau.+1)=1, and is the irrational number which is the most difficult to approximate by rational numbers.

The quadratic irrational ##EQU1## where F.sub.n is the Fibonacci number. (The first few Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . . ; each number in this sequence is the sum of the preceding two numbers.) The cubic irrational pair (.alpha., .beta.) satisfies a similar equation.

A sequence of numbers, G.sub.n, may be defined using a rule similar to the Fibonacci rule: G.sub.n=1 =G.sub.n +G.sub.n-2, and starting with G.sub.1 =G.sub.2 =G.sub.3 =1. The first 25 numbers in this sequence are: 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023. ##EQU2##

Other associated relationships are: .beta..sup.2 =.alpha. and .beta..sup.-1 =.alpha.+1.

As noted earlier, in accordance with a preferred embodiment of the invention, the mask dimensions are 1278.times.1873; the ratio 1873/1278 approximates .alpha.+1 to seven decimal places (i.e., the error is approximately 3.times.10.sup.-8, and will produce output images that have been observed by the human visual system to possess high grey level quality. Any smaller mask's dimension's ratio is useful to only four decimal places; to improve on the above ratio requires mask sizes over 58425.times.85626 (the ratio 85626/58425 only reduces the error by half, yet these two parameters are not relatively prime--so even higher parameters are required).

As will be appreciated from the foregoing description, the complexity of threshold value generation and data entry storage of conventional half-tone masks are substantially simplified in accordance with the present invention, by algebraically dispersing the threshold values throughout a dithering half-tone mask array in a manner that both avoids clusters or clumping of nearly equal threshold values, and allows the threshold values to be either computed and stored for a variety of mask array sizes, or calculated `on the fly` during the half-tone conversion of the original digital image.

Among the advantages of the present invention are its ability to be applied to masks of several different sizes, which need not be saved in any file or memory. The masks can be computed using a simple rule implemented using a very small program (or, in hardware, a small number of registers, adders, constants, and gates), which allows the mask's individual values to be computed as they are used. The subjective appearance of the rendered images is has been determined to be of high quality, being relatively free of vertical, horizontal, or 45-degree angled visual artifacts.

While I have shown and described several embodiments in accordance with the present invention, it is to be understood that the same is not limited thereto but is susceptible to numerous changes and modifications as known to a person skilled in the art, and I therefore do not wish to be limited to the details shown and described herein but intend to cover all such changes and modifications as are obvious to one of ordinary skill in the art.