Enhanced error-diffusion method for color or black-and-white reproduction

0001The present invention relates to reproduction of digital image data for printing and visualization purposes, and in particular provides a method for generating digital halftone images using an enhanced error distribution technique. The enhanced error distribution technique features (a) error-distribution coefficients that are input-signal dependent, and (b) thresholds that are stored in a threshold mask which is well-dispersed and has a limited number of levels. The inventive technique is particularly effective for binary physical output devices, such as ink-jet printers or the like.

0002Digital computers commonly store images in bitmap format such that each pixel of the image has a gray level, such as a gray level that ranges between 0 and 255 (i.e., an 8-bit system). Each gray level represents an increment of gray between a pure black value and a pure white value. In the case of color images, three color separations each include gray level values for each pixel of the image, and if eight bits are used for each color separation, results in the possibility of representing 16,777,216 different colors (commonly called "24-bit color").

0003Examples of how such images may be formed include the possibility of scanning an ordinary continuous tone photograph into a digital computer, so as to form bitmap image data at a particular pixel resolution, such as 300 or 600 dots per inch. The bitmap image data might thereafter be compressed using any of a variety of standard image compression techniques (such as "JPEG" or "GIF"), but before use even compressed images are uncompressed to bitmap image format.

0004Bitmap images containing gray level pixels are unprintable by today's printers, because such printers can only print one (or, at most, a limited small number of) density value at each pixel. For example, at each pixel, a conventional laser beam printer or ink-jet printer is able to do only one of two things: (1) apply colorant (such a black or colored toner or ink) resulting in a completely filled in or black pixel, or (2) refrain from applying colorant resulting in a completely white pixel. Since each pixel of the original image data has up to 256 different gray levels, it can be seen that a tremendous amount of information is lost during the printing process where, for each pixel, only a black or white value can be printed.

0005Recently, printers have become available which print a variable size dot at each pixel, but the amount of variation in the dot is only a few different levels, such as four. Accordingly, it can be seen that even with the most modern printers available, a tremendous amount of information is lost when printing a gray-level image or a color image with each color separation plane represented by gray levels.

0006A wide variety of halftoning processes have been proposed so as to minimize the information lost when printing, and so as to produce visually acceptable printed images of gray level images. "Halftoning" is a process by which gray-level pixels in a bitmap image are converted to binary pixels for printout by a conventional printer. (Of course, in a situation where a printer can print multiple levels for each pixel, "halftoning" refers to the process by which gray level pixels are converted to corresponding N-ary values for printout by such a multi-level printer.) Good halftoning processes should satisfy the following criteria: <ol id="ol0001" compact="compact"><li>(1) The local mean intensity of the reproduction should follow the intensity level of corresponding areas of the original image;</li><li>(2) Small details should not be lost in reproduction;</li><li>(3) No visible artifacts should be created, such as low-frequency beatings, bandings, worm-like structure, Moire effects, etc.;</li><li>(4) To the extent that structural artifacts are unavoidable in the halftoning process, such structural artifacts should be filtered as much as possible by the human visual system;</li><li>(5) Textures present in the original should be of the same nature as textures in the reproduction, meaning that such textures should have the same shape and same visual appearance;</li><li>(6) The reproduction should have an overall visually pleasing appearance.</li></ol>

0007In low-resolution bi-level printing devices, such as ink-jet printers and laser beam printers operating in the range between 300 and 800 dpi, individual dots are still visible, and groups of individual dots are therefore necessarily visible as well. Accordingly, a good halftoning process needs to deal with visible dots and groups of individual dots.

0008A large variety of halftoning processes for printing are known in the art. The most popular halftoning processes are ordered dithering methods and error-distribution (or error-diffusion) methods. Ordered dithering methods use spatial dithering in order to obtain clustered-dot or dispersed-dot repetitive binary patterns on output devices. Error distribution (or error-diffusion) methods produce dispersed non-repetitive patterns whose mean density is more-or-less proportional to the intensity of the input signal.

0009For high-resolution devices, i.e., those devices operating above around 800 dpi, ordered dithering methods are usually preferable. Images produced using ordered dithering methods are generally visually pleasing, and produce an illusion of spatial continuity even when images are rendered on a binary device. Both theoretical and practical research has confirmed that the human visual system filters out medium sized diagonally-oriented structures. Thus, "classical" clustered-dot dithering techniques are extremely popular.

0010One weak point of most ordered dithering methods, however, is their inherent property of low-pass filtering. Low-pass filtering causes small details whose size is smaller than the size of a cluster dot to be rendered poorly, and sometimes even lost. A second weak point is the so-called "banding effect". The banding effect is caused since classical methods can reproduce only a fixed number of intensity levels, set by the surface area of the cluster. The banding effect leads to displeasing bandings that are visually apparent in the image, giving a false contouring effect.

0011For these reasons, when ordered dithering methods are applied to low resolution binary printing devices (that is, those operating in the range between 300 and 800 dpi), poor image printing is often the result. (The popularity of ordered dithering methods in low resolution devices can be explained by the relative ease with which such methods are implemented in software.)

0012Error distribution methods work by comparing the gray level of a target pixel with a threshold value, printing a black (or colored) or a white pixel based on the comparison, determining the error between the black or white pixel actually printed and the actual gray value of the target pixel, and distributing the error to pixels adjacent the target pixel.

0013Error-distribution methods solve at least the problem of small-detail rendering when low-resolution printing devices are used. Due to their inherent edge enhancement property, which is well-documented in the art, the error distribution methods of this class are sometimes preferable for use in output devices operating at low resolution. Error-distribution methods also have weaknesses. Weaknesses to which the present invention is addressed are described as follows.

0014First, images produced with error distribution methods often contain aperiodic visible structures which form worm-like chains of varying length. Such worm-like chains, which are well documented in the art, are most readily apparent in highlight or shadow regions, and examples are illustrated in <figref idref="f0001">Figure 1</figref>. In <figref idref="f0001">Figure 1</figref>, <figref idref="f0010">10</figref> represents a printout of standard error distribution halftoning of an 8x4 grid of patches, with each patch having a constant gray level. The 8x4 grid of <figref idref="f0001">Figure 1</figref> includes patches only in light light gray areas, and does not include patches of darkness exceeding around 10% gray. Worm-like chains are clearly shown at 11 and 12. Particularly in cases of low-resolution printers, where the individual printing dots are clearly visible, viewers who expect to see completely disordered patches of gray are displeased when viewing patches containing worm-like chains such as those shown at 11 and 12.

0015A second drawback inherent to most error distribution methods is the problem of unstable formation of patches having highly repetitive structures. Such structures are illustrated in <figref idref="f0002">Figure 2</figref>, which shows a gray level wedge proceeding from full black (at an image intensity level of 0) to full white (at an image intensity level of 1). Repetitive structures are clearly visible throughout the gray wedge, particularly at 14, 15, 16 and 17. Not only is the presence of highly repetitive structures visually displeasing, but it also plays an important role in the non-linear behavior of printing processes which use error distribution methods.

0016Noticeable efforts have been made in the past, in order to diminish the inherent problems of existing error distribution methods and to increase the quality of the images produced by such methods. In particular, efforts which address the problem of worm-like chains in highlight and shadow areas, and which address the problem of repetitive structures, include the following.

0017<patcit id="pcit0001" dnum="US5014333A"><text>U.S. Patent No. US-A-5,014,333 to Miller and Morton </text></patcit>discloses an error-propagation halftoning method where a periodic spatial distribution of the threshold values is used, instead of constant threshold values in a "standard" error-distribution method and where in very light and very dark areas the propagated errors are attenuated. The main advantage of this method is said to be in effecting smooth transition between dither and diffusion processes.

0018<patcit id="pcit0002" dnum="US5341228A"><text>U.S. Patent, US-A-5,341,228 to Parker and Mitsa </text></patcit> discloses a halftoning method where a big threshold matrix is used. This threshold matrix is prepared in such a way that the resulting bi-level image exhibits the characteristics of so-called blue-noise, which is said to be pleasant for visual perception. This patent also proposes an alternative method for producing dispersed-dot dither matrices.

0019<patcit id="pcit0003" dnum="US4962542A"><text>U.S. Patent No. US-A-4,962,542 to Klees </text></patcit> discloses a halftoning method where a recursive spatial filter interchanges the value of a control pixel with that of the value of a predetermined surrounding pixel in a mark when a specific image pattern occurs in the digital image. The main goal of this method appears to be elimination of visible grain patterns from the bi-level output image.

0020<patcit id="pcit0004" dnum="US5150429A"><text>U.S. Patent No. US-A-5,150,429 to Miller </text></patcit>and Smith discloses a halftoning method where an image processor performs error diffusion by thresholding an incoming gray pixel to black or white, by comparing the difference between the black or white print value and the incoming pixel gray level, and by superimposing the difference on the next pixel gray level. The threshold value is read out from a threshold matrix which has been modulated with a pattern which is complementary to the known artifact pattern of the error diffusion process. The main goal of this method appears to be elimination of visible artifacts from the bi-level output image.

0021<patcit id="pcit0005" dnum="US5243443A"><text>U.S. Patent No. US-A-5,243,443 to Eschbach </text></patcit> discloses a halftoning method where a combination of halftoning and error diffusion initially determines a best fit halftone cell, according to the terms of the inventor, and propagates the halftoning error in order to maintain gray density. The main goal of this method appears to be a reduction of visible error-diffusion artifacts in the output image.

0022<patcit id="pcit0006" dnum="US5313287A"><text>U.S. Patent No. US-A-5,313,287 to Barton</text></patcit> discloses an error-diffusion halftoning method where the direction of processing scan lines of a source image is selected with blue noise, in order to reduce directional and start-up anomalies. Error diffusion threshold values are modulated with blue noise. Error terms in the error diffusion process are distributed according to a special three-weight filter. It appears that the goal of this method is to reduce visible error-diffusion artifacts in the output image.

0023<patcit id="pcit0007" dnum="US4920501A"><text>U.S. Patent No. US-A-4,920,501 to Sullivan and Miller</text></patcit> discloses a method of producing a binary bit image pattern having a minimal visual noise for each density level in an image. The patterns are produced by employing a stochastic combinatorial minimization technique and a human visual system modulation transfer function.

0024<nplcit id="ncit0001" npl-type="s"><text>R. Eschbach in "Reduction Of Artifacts In Error Diffusion By Means Of Input-Dependent Weights", Journal of Electronic Imaging, October 1993, Vol. 2(4), pp. 352-358</text></nplcit>, proposes two different error distribution matrices, one for highlights and one for mid-tones. The problem of visibility of the transition between these two areas is mentioned, and a solution based on randomizing the location of the transition boundary is proposed. The author claims that in highlights the worm-like structures are greatly reduced by mean of a modified error-diffusion matrix.

0025Although the above illustrates the efforts undertaken to address the problem of worm-like chains in highlight areas, and the problem of repetitive structural artifacts, there exists the need for further improvement.

0026The present invention improves currently existing error diffusion techniques by addressing the problems of worm-like chains in highlights and shadows, and at the same time addressing the problem of structural artifacts. Specifically, error diffusion according to the invention suppresses considerably worm-like structural chains in highlight and shadow areas, and diminishes considerably structural artifacts in standard error diffusion techniques, thereby improving tone reproduction curves.

0027Exemplary outputs of improved error diffusion according to the invention are presented in <figref idref="f0003">Figures 3</figref> and <figref idref="f0004">4</figref>, which respectively correspond to outputs of prior art techniques in <figref idref="f0001">Figures 1</figref> and <figref idref="f0002">2</figref>. Thus, considering <figref idref="f0003">Figure 3</figref> with respect to the prior art output of <figref idref="f0001">Figure 1</figref>, it can be seen that the existence of worm-like chains in highlight areas (and correspondingly in shadow areas) is suppressed considerably when using error improved error diffusion according to the invention. Likewise, in considering <figref idref="f0004">Figure 4</figref> in conjunction with <figref idref="f0002">Figure 2</figref>, it can be seen that structural artifacts are diminished considerably yielding an improved gray scale wedge from pure black to pure white.

0028Conventional error-diffusion halftoning distributes error using a 3x3 error distribution matrix whose coefficients are fixed regardless of the gray-level intensity of the target pixel. For example, Floyd-Steinberg in 1976 proposed a 3x3 error distribution matrix that is still in widespread use today and whose coefficients are: <maths id="math0001"><math display="block"><mfrac><mn>1</mn><mn>16</mn></mfrac><mfenced open="|" close="|"><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>7</mn></mtd></mtr><mtr><mtd><mn>3</mn></mtd><mtd><mn>5</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></math><img file="EP0808055B1_D0001.tif" /></maths>

0029According to a first aspect of the present invention, there is provided a method for generating a threshold mask, as set out in claim 1.

0030According to a second aspect of the present invention, there is provided an error diffusion halftoning process, as set out in claim 8.

0031According to a third aspect of the present invention, there is provided an image processing apparatus, as set out in claim 18.

0032Further advantageous developments and modifications of the first to third aspects are set out in respective dependent claims.

0033This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiment thereof in connection with the attached drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

0034<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> is a 4x8 grid of constant gray level patches of highlights, and <figref idref="f0003">Figure 3</figref> is the same 4x8 grid of constant level gray patches produced by the enhanced error diffusion technique of the present invention.</li><li><figref idref="f0002">Figure 2</figref> is a gray level wedge produced by error diffusion techniques in the prior art showing structural artifacts, and <figref idref="f0004">Figure 4</figref> is a corresponding gray level wedge produced by the enhanced error diffusion techniques of the present invention.</li><li><figref idref="f0005">Figure 5</figref> is a view showing the outward appearance of representative computing equipment which incorporates enhanced error diffusion according to the invention.</li><li><figref idref="f0006">Figure 6</figref> is a detailed block diagram showing the internal construction of <figref idref="f0005">Figure 5</figref></li><li><figref idref="f0007">Figure 7</figref> is a functional block diagram which stresses functional connectivity of some of the elements of the <figref idref="f0006">Figure 6</figref> block diagram.</li><li><figref idref="f0008">Figure 8</figref> is a functional view of a color management system including enhanced error diffusion according to the invention.</li><li><figref idref="f0009">Figure 9</figref> is a flow diagram showing operation of the color management of <figref idref="f0008">Figure 8</figref>.</li><li><figref idref="f0010">Figure 10</figref> is a block diagram showing an apparatus for performing enhanced error diffusion according to the invention.</li><li><figref idref="f0011">Figure 11</figref> is a flow diagram showing enhanced error diffusion performed by the apparatus of <figref idref="f0010">Figure 10</figref>.</li><li><figref idref="f0012">Figure 12</figref> is a flow diagram for explaining how to obtain error distribution matrices for use in enhanced error diffusion according to the invention.</li><li><figref idref="f0013">Figure 13</figref> is a flow diagram for explaining how to explain threshold masks for use in enhanced error diffusion according to the invention.</li><li><figref idref="f0014">Figure 14(a)</figref> is a view showing an intermediate output obtained during calculation of a threshold mask according to the invention, and <figref idref="f0014">Figure 14(b)</figref> is a histogram of the <figref idref="f0014">Figure 14(a)</figref> view.</li><li><figref idref="f0015">Figures 15(a)</figref> and <figref idref="f0016">16(a)</figref> are views showing threshold masks obtained according to the invention, and <figref idref="f0015">Figures 15(b)</figref> and <figref idref="f0016">16(b)</figref> are histograms of values in <figref idref="f0015">Figures 15(a)</figref> and <figref idref="f0016">16(a)</figref>, respectively.</li><li><figref idref="f0017">Figure 17(a)</figref> is a view showing scaled values of a threshold mask according to the invention, and <figref idref="f0017">Figure 17(b)</figref> is a histogram showing a histogram of values in <figref idref="f0017">Figure 17(a)</figref>.</li></ul>

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

0035<figref idref="f0005">Figure 5</figref> is a view showing the outward appearance of representative computing equipment which incorporates enhanced error diffusion according to the invention. Shown in <figref idref="f0005">Figure 5</figref> is computing equipment 20 such as an IBM PC or PC-compatible computer having a windowing operating system such as a Microsoft Windows operating system. Computing equipment 20 is provided with a display monitor 23 having a display screen 22 on which computing equipment 20 displays images to the user. Computing equipment 20 is further provided with a floppy disk drive 24 with which removable floppy disk media may be read or written, fixed disk drive 25 for storing data files and application program files, a keyboard 26 for permitting input of text data and manipulation of objects displayed on display screen 22, and a pointing device 27 such as a mouse or the like which is also provided to permit manipulation of objects on display screen 22. A conventional color printer 30, such as a color bubble jet printer, is also provided. Also provided are connections to a network 31 or to an ordinary voice telephone line 32, both for sending and receiving color image data as well as other files such as files which include program instruction sequences by which computing equipment 20 is operated.

0036While a bubble jet printer is presently preferred, any color printer which forms full color images by mixing colorants in amounts set by corresponding color component values, such as a color laser beam printer or color thermal wax printer or the like, is suitable in the practice of the invention.

0037In accordance with operator instructions, and under control of the windowing operating system, stored application programs such as graphics application programs, drawing application programs, desktop publishing application programs and the like, are selectively activated to process and to manipulate data. Also in accordance with operator instructions, and based on those stored application programs, commands are issued to display images on monitor 23 and to print images appearing on monitor 23, and those images are then printed on printer 30 as described more fully hereinbelow.

0038<figref idref="f0006">Figure 6</figref> is a detailed block diagram showing the internal construction of computing equipment 20. As shown in <figref idref="f0006">Figure 6</figref>, computing equipment 20 includes a central processing unit (CPU) 40 such as programmable microprocessor interfaced to a computer bus 41. Also interfaced to computer bus 41 is display interface 44, network interface 45 for interfacing to network 31, fax/modem/telephone interface 46 for interfacing to telephone 32, printer interface 47, and floppy disk drive interface 49.

0039Main memory 51 such as random access memory (RAM) interfaces to computer bus 41 so as to provide CPU 40 with access to memory storage. In particular, when executing stored application program instruction sequences such as those associated with application programs stored on disk 25, CPU 40 loads those instruction sequences from disk 25 (or other storage media such as media accessed via network 31 or floppy disk drive 24) into main memory 51 and executes those stored program instruction sequences out of main memory 51.

0040ROM (read only memory) 52 is provided for storing invariant instruction sequences such as start-up instruction sequences or basic input/output operating system (BIOS) sequences for operation of keyboard 26.

0041As shown in <figref idref="f0006">Figure 6</figref>, and as previously mentioned, fixed disk 25 stores program instruction sequences for the windowing operating system and for various application programs such as a graphics application program, a drawing application program, a desktop publishing application program, and the like. In addition, stored on fixed disk 25 are color image files such as are displayed on monitor 23 or printed on printer 30 under control of a designated application program. Fixed disk 25 also stores a monitor driver 33 which controls how RGB color primary values are provided to display interface 44, and color management system 34 which is a printer driver for controlling how CMYK color component values are provided to printer interface 47 for printout by printer 30. Enhanced error diffusion according to the invention, in this embodiment of the invention, resides in color management system 34. Other device drivers are also stored on fixed disk 25, for providing appropriate signals to the various devices (such as the network) connected in computing equipment 20.

0042Ordinarily, application programs and drivers stored on disk 25 need first to be installed by the user onto disk 25 from other computer readable media on which those programs and drivers are initially stored. For example, it is customary for a user to purchase a floppy disk or other computer readable media on which a copy of color management system 34 is stored. The user would then install color management system 34 onto disk 25 by inserting the purchased floppy disk into floppy disk drive 24 and by commanding CPU 40 to copy color management system 34 from the floppy disk onto disk 25. It is also possible for the user, via telephone 32 and modem interface 46, or via network 31 and network interface 45, to download color management system 34 from a computerized bulletin board to which the drivers had previously been uploaded.

0043<figref idref="f0007">Figure 7</figref> is a functional block diagram showing how computer 20 interacts with monitor 23 and printer 30. Shown in <figref idref="f0007">Figure 7</figref> are computer 20 with monitor driver 33, color management system 34, CPU 40, RAM 51 and ROM 52, all arranged functionally rather than structurally, as in <figref idref="f0006">Figure 6</figref>.

0044As mentioned above, using keyboard 26, an operator can cause CPU 40 to execute stored program instructions which cause color images to be displayed on monitor 23 and which cause corresponding color images to be printed on color printer 30. Specifically, and in cooperation with the stored program instructions in the application program stored on disk 25, CPU 40 derives a color image for display on monitor 23. CPU provides the color image to monitor driver 33 which in turn derives gray-level RGB values for each pixel in the monitor 23. The RGB values are provided via display interface 44 to monitor 23 where those values are displayed. Since monitor 23 is a continuous tone analog device, the color image displayed on monitor 23 from the derived RGB values is a continuous tone image based on the gray-levels of each of the R.G and B values.

0045Upon request, CPU 40 also feeds a color image to color management system 34 for printing by color printer 30. Color management system 34 derives binary CMYK values for each pixel of the color image based on the gray-level RGB color values provided from CPU 40. The color management system 34 allows selection, ordinarily by the user but in some cases automatically by CPU 40, of one of plural rendering modes, here, a perceptual rendering mode, a colorimetric rendering mode, and a business graphics rendering mode. Enhanced error diffusion according to the invention, in this embodiment of the invention, operates during the perceptual rendering mode, but it is possible to incorporate gray component replacement according to the invention in any or all of the rendering modes. Whichever one of the plural modes is selected, however, the ultimate purpose of color management system 34 is to halftone-process the gray-level RGB values provided from CPU 40 so as to obtain binary CMYK values, and to provide the binary CMYK values to printer 30 for printing.

0046More particularly, for each pixel of an image on monitor 23, color management system 34 converts the gray-level RGB value of the pixel into a binary halftone value for each of the CMYK color components printed by printer 30. For example, if each pixel of the image on monitor 23 is represented by a 24-bit RGB value (i.e., eight bits for R, eight bits for G, and eight bits for B), color management system 34 obtains a digital halftone value in which each of the CMYK color components is represented by a single bit indicating whether a dot of the respective color component is to be printed at a corresponding pixel position by printer 30.

0047Thereafter, color management system 34 feeds the CMYK values via printer interface 46 to printer 30 where they are stored in bitmap memory 37 within printer 30. Bitmap memory 37 may store a full bitmap image of the printed image, or it may store only a band or partial bitmap image. When sufficient color data, namely binary halftoned CMYK data, is stored in bitmap memory 37, a color print head 36 reciprocates across a platen adjacent a sheet of paper. In a preferred embodiment, print head 36 includes 32 ink jet nozzles arranged in a four column by eight row pattern. The nozzles in the first column all eject droplets of cyan ink; the nozzles in the second column all eject droplets of magenta ink; the nozzles in the third column all eject droplets of yellow ink; and the nozzles in the fourth column all eject droplets of black ink. The nozzles are controlled independently in accordance with the color data in bitmap memory 37 such that in one reciprocation of print head 36 across the platen, eight rows of pixels are printed.

0048<figref idref="f0008">Figure 8</figref> is a view showing the functional arrangement of color management system 34. The color management system shown in <figref idref="f0005">Figure 5</figref> includes plural different rendering modes, in which at least one rendering mode such as the perceptual rendering mode incorporates enhanced error diffusion according to the invention. As shown in <figref idref="f0008">Figure 8</figref>, color management system 34 includes a rendering mode selector 60 which allows selection between one of the plural rendering modes of the color management system. Preferably, rendering mode selector 60 is a user manipulable graphical user interface which allows a user, after commanding an image to be printed, to select one of the plural rendering modes by which color management system 34 is able to render the image. Alternatively, it is also possible for rendering mode selector 60 to be actuatable automatically under control of CPU 40, in which case CPU 40 would make automatic selection of the proper rendering mode. Such automatic selection may, for example, be made based on the type of application software which is generating the image, based on data or image type, based on data structure, based on a histogram or other analysis of color distribution in the image, or the like. For example, all .BMP type data might have perceptual rendering automatically selected, while vector graphics might have business graphics rendering automatically selected, and so on.

0049Based on the mode selected by rendering mode selector 60, gray-level values for each of the RGB input colors from CPU 40 are fed for appropriate processing to the selected one of the plural rendering modes, so as to generate printer binary CMYK colorant values.

0050<figref idref="f0009">Figure 9</figref> is a flow diagram used for explaining operation of color management system 34 shown in <figref idref="f0008">Figure 8</figref>.

0051In step S901, a user issues a command to print. Flow then advances to step S902 in which a rendering mode is selected. Specifically, as mentioned above in connection with <figref idref="f0008">Figure 8</figref>, step S902 utilizes rendering mode selector 60 so as to select one of the plural different rendering modes included in color management system 34. Selection can be manual by the user or automatic by computer, although automatic selection with manual override is preferred.

0052If a perceptual rendering mode is selected in step S902, then flow advances to step S903 in which perceptual rendering is performed in accordance with perceptual rendering process steps 61. Perceptual rendering in accordance with step S903, which includes enhanced error diffusion according to the invention, is described in further detail in connection with <figref idref="f0010 f0011 f0012 f0013 f0014 f0015 f0016 f0017">Figures 10 through 17(b)</figref>. Thereafter, binary CMYK values derived in perceptual rendering step S903 are provided to printer 30 for printing (step S906).

0053If in step S902 colorimetric rendering is selected, then flow advances to step S904 in which colorimetric rendering is performed in accordance with colorimetric rendering process steps 62. Any suitable colorimetric rendering process steps may be used, as will be apparent to those skilled in the art. Thereafter, CMYK values derived in colorimetric rendering step S904 are provided to printer 30 for printing (step S906).

0054If in step S902 business graphics rendering is selected, then flow advances to step S905 in which business graphics rendering is performed in accordance with business graphics rendering process steps 63. Any suitable business graphics rendering may be used, as will be apparent to those skilled in the art. Thereafter, CMYK values derived in business graphics rendering step S905 are provided to printer 30 for printing (step S906).

0055<figref idref="f0010">Figure 10</figref> is a simplified block diagram of an apparatus for carrying out enhanced error diffusion according to the invention. The apparatus shown in <figref idref="f0010">Figure 10</figref> might be implemented as a physical apparatus, but more preferably the apparatus of <figref idref="f0010">Figure 10</figref> is implemented as software steps in connection with perceptual rendering process steps 61 (step S903).

0056As shown in <figref idref="f0010">Figure 10</figref>, enhanced error distribution according to the invention includes an input gray scale image storage section 110 for storing gray-level values for each of the RGB color components of an output image. Comparator 120 operates on each pixel of the gray level values stored in gray level image storage second 110, and for each pixel compares the gray level value with a threshold obtained from threshold mask storage section 140. Based on the comparison, comparator 120 outputs a binary 1 for the pixel if a white output is desired, or a binary 0 for the pixel if a colored (or black) output is desired. The output is stored in halftone image storage section 150. Error between the binary output stored in halftone image storage section 150 and the gray level value in the gray-level image storage section 110 is output to error distribution unit 130. Error distribution unit 130 calculates how the error is to be distributed to adjacent pixels, based on an error distribution coefficient table 135. Error distribution table 135 stores a table of 3x3 error distribution matrices, with one of the error distribution matrices being selected based on the gray level value stored in gray scale image storage section 110. Error distribution unit 130 selects the appropriate error distribution matrix based on the gray level value, and distributes error from comparator 120 to adjacent pixels in gray-scale image storage section 110. The process is thereupon repeated for each x-y pixel address 105, as generated by path generator 100 which is used to generate the scanning path through image data in storage section 110, such as a serpentine scanning path, a scan-line scanning path, a blue-noise-modified scanning path, and the like.

0057<figref idref="f0011">Figure 11</figref> is a flow diagram showing operation of the <figref idref="f0010">Figure 10</figref> arrangement. In step S1101, and based on an x,y address generated by path generator 100, a gray-level value V_in is obtained from gray-scale image storage section 110 at address (x,y). A threshold T is obtained from threshold mask storage section 140, also at position (x,y). In this regard, it should be understood that threshold mask storage section 140 stores a threshold mask which contains a large number of threshold values arranged in a generalized UxV matrix arrangement which preferably is square and which preferably is large (U,V ≥ 256).

0058In step S1103, comparator 120 compares V_in to T. If V_in is smaller than T, meaning that the gray level value V_in is darker than threshold T, comparator 120 sets the output pixel V_out to 0 (i.e., to a black, or colored, pixel printed output). On the other hand, if V_in is not less than T, then comparator 120 sets output V_out equal to 1 (i.e., no colorant, or a white pixel).

0059In either event, flow then advances to step S1106 in which comparator 120 calculates an error E between V_out and V_in, and sends the error E to error distribution unit 130. Based on the gray level value V_in for the pixel under consideration, an error distribution matrix M_ed is selected from error distribution coefficient table 135. Using the selected error distribution matrix M_ed, error distribution unit 130 distributes error E to adjacent pixels (step S1108). The distributed error is added back into appropriate gray level values for adjacent pixels, as currently stored in gray-scale image storage section 110.

0060In step S1109, if path generator 100 determines that more pixels still need to be processed, then flow returns to step S1101 for such processing. Otherwise, processing is completed, and binary halftone values stored in image storage section 150 are printed by output device 160.

0061In the present embodiment, intensities of gray-level images are assumed to be within the range of 0 and 1, where 0 represents a fully colored component (i.e., full red, green or blue) and 1 represents a completely uncolored value (i.e., white). Any linear normalization processes, well known in the art, can be applied to bring intensity values in different ranges into that assumed by the present disclosure, or those in the present disclosure can be transformed into any other range, such as 0 to 255. Furthermore, without loss of generality, it can be said that the disclose invention is able to manipulate gray-level intensity in the range of V_min to V_max, where V_min and V_max designate minimum and maximum gray level intensities.

0062The terms "pixel" and "individual cell" are used equally in the present disclosure in order to designate the smallest addressable entity of the image, which has an intensity attribute The output device 160 is able to interpret the set of pixels of the produced digital halftone image, whose output bi-level values stored in the output bi-level image storage unit 150 are equal to 0, as being blackened pixels, e.g. pixels, where a physical colored substrate is put on the output support. Otherwise, the pixels whose output bi-level values stored in the output bi-level image storage unit 150 are equal to 1,are not colored: they preserve the color of the output support.

[Path Generator 100]

0063The disclosed method is a sequential one. The order of the sequence of coordinates (<i>x,y</i>) of the pixels to be processed influences the quality of the produced image. This influence is well known in the art. If P(<i>i</i>) is the sequence of coordinates (<i>x</i>,<i>y</i>) of the pixels to be processed, the goal of the path generator unit 100 is to generate a sequence of integer pixel coordinates (<i>x,y</i>), 0≤=<i>x</i>≤W_out; 0≤=<i>y</i>≤H_out; (W_out and H_out are the width and the height of the output image) in such a way that all pixels are processed sequentially.

0064The simplest path generation scheme, the so-called scan-line path, is defined as follows: <maths id="math0002"><math display="block"><mi>P</mi><mfenced><mi>i</mi><mfenced><mi>x</mi><mi>y</mi></mfenced></mfenced><mo>=</mo><mfenced><mi>i</mi><mfenced><mi>mod</mi><mspace width="1em" /><msub><mi>W</mi><mi mathvariant="italic">out</mi></msub></mfenced><mo>,</mo><mi mathvariant="italic">floor</mi><mfenced><mfrac><mi>i</mi><msub><mi>W</mi><mi mathvariant="italic">out</mi></msub></mfrac></mfenced></mfenced></math><img file="EP0808055B1_D0002.tif" /></maths> where W_out is the width of the output image, the operator "mod" is a modulo-division operator details, the "<i>floor(x)</i>" function is defined as "the biggest integer smaller or equal to <i>x</i>", and where successive values of integer <i>i</i> give the sequence of processed pixels.

0065There are several variants of path sequences used in the art: left-ward scan-lines instead of right-ward scan-lines; alternative left-ward and right-ward scan-lines for respectively odd and even scan-lines (serpentine or boustrophedon); upward, downward or alternative upward-downward scan-lines, etc.

0066The disclosed method has been implemented using boustrophedon path. Nevertheless, other path generation schemes such as scan-line may be applied.

[Error Distribution]

0067The comparator and error distribution unit, which comprises the comparator 120, the error distribution unit 130, the threshold mask storage 140 and the error distribution coefficient tables 135 operates on a set of intensity values of the input image V_in(<i>x</i>,<i>y</i>) stored in the input gray-scale image storage until 110. The set of input intensity values V_in(<i>x</i>,<i>y</i>) is compared, in the comparator 120, with the threshold value T(<i>x,y</i>). According to the result of this comparison, the output value V_out(<i>x,y</i>) of the pixel (<i>x,y</i>) is set to one of two possible values: <maths id="math0003"><math display="block"><mi>V</mi><mfenced><mi>x</mi><mi>y</mi></mfenced><mo>=</mo><mfenced><mtable><mtr><mtd><mn mathvariant="italic">1</mn><mo>≡</mo><mi mathvariant="italic">no ink</mi><mo mathvariant="italic">;</mo><mspace width="1em" /><mi mathvariant="italic">if</mi><mspace width="1em" /><msub><mi mathvariant="italic">V</mi><mi mathvariant="italic">in</mi></msub><mfenced><mi>x</mi><mi>y</mi></mfenced><mo>></mo><mi>T</mi><mfenced><mi>x</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi mathvariant="italic">xdim</mi></mfenced><mo>,</mo><mi>y</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi mathvariant="italic">ydim</mi></mfenced></mfenced></mtd></mtr><mtr><mtd><mn>0</mn><mo>≡</mo><mi mathvariant="italic">ink</mi><mo>;</mo><mspace width="1em" /><mi mathvariant="italic">if</mi><mspace width="1em" /><msub><mi mathvariant="italic">V</mi><mi mathvariant="italic">in</mi></msub><mfenced><mi>x</mi><mi>y</mi></mfenced><mo>≤</mo><mi>T</mi><mfenced><mi>x</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi mathvariant="italic">xdim</mi></mfenced><mo>,</mo><mi>y</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi mathvariant="italic">ydim</mi></mfenced></mfenced></mtd></mtr></mtable></mfenced></math><img file="EP0808055B1_D0003.tif" /></maths> where (mod <i>n</i>) designates modulo-n arithmetic; and <i>xdim</i> and <i>ydim</i> are horizontal and vertical dimensions of the matrix T(<i>x,y</i>).

0068The threshold value T(<i>x,y</i>) may be constant (e.g. T(<i>x,y</i>)=.5) or may depend on the input intensity level (threshold function becomes T(<i>x</i>,<i>y</i>,V_in(<i>x,y</i>)) in this case) or on coordinates (<i>x,y</i>) (threshold modulation). The disclosed method has been implemented using a perturbation well-dispersed threshold mask having a limited number of levels which is stored in the threshold mask storage 140. The output value V_out(<i>x,y</i>) is carried out towards the output bi-level image storage until 150.

0069The difference E between the output value V_out(<i>x,y</i>) and the intensity value of the input image V_in(<i>x,y</i>) is re-distributed between several pixels of the weighted sum image which have not yet been processed. This re-distribution is performed by the error distribution unit 130: <maths id="math0004"><math display="block"><mi>E</mi><mo>=</mo><msub><mi>V</mi><mi mathvariant="italic">out</mi></msub><mfenced><mi>x</mi><mi>y</mi></mfenced><mo>-</mo><msub><mi>V</mi><mo>∈</mo></msub><mfenced><mi>x</mi><mi>y</mi></mfenced><mspace width="5em" /><mn>0</mn><mo>≤</mo><mfenced><mi>u</mi><mi>v</mi></mfenced><mo>&lt;</mo><msub><mi>N</mi><mi mathvariant="italic">ed</mi></msub></math><img file="EP0808055B1_D0004.tif" /></maths><maths id="math0005"><math display="block"><msub><mi>V</mi><mi mathvariant="italic">in</mi></msub><mo>⁢</mo><mfenced><mi>x</mi><mo>-</mo><mfrac><mrow><msub><mi>N</mi><mi mathvariant="italic">ed</mi></msub><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>+</mo><mi>u</mi><mo>,</mo><mi>y</mi><mo>-</mo><mfrac><mrow><msub><mi>N</mi><mi mathvariant="italic">ed</mi></msub><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>+</mo><mi>v</mi></mfenced><mo>=</mo><msub><mi>V</mi><mi mathvariant="italic">in</mi></msub><mo>⁢</mo><mfenced><mi>x</mi><mo>-</mo><mfrac><mrow><msub><mi>N</mi><mi mathvariant="italic">ed</mi></msub><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>+</mo><mi>u</mi><mo>,</mo><mi>y</mi><mo>-</mo><mfrac><mrow><msub><mi>N</mi><mi mathvariant="italic">ed</mi></msub><mo>-</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>+</mo><mi>v</mi></mfenced><mo>+</mo><mi>E</mi><mo>•</mo><msub><mi>M</mi><mi mathvariant="italic">ed</mi></msub><mfenced><mi>u</mi><mi>v</mi></mfenced></math><img file="EP0808055B1_D0005.tif" /></maths> where N_cd is the size of the square matrix of error-distribution coefficients M_cd(<i>u,v</i>) stored in the error distribution coefficient table 135.

0070The square matrix of error-distribution coefficients M_cd(<i>u,v</i>) of odd size Ned, stored in the error distribution tables 862, characterizes the error distribution process. For example, the size N_cd of the square matrix of error-distribution coefficients M_cd(<i>u,v</i>) may be N_cd=3. There are several matrices of error-distribution coefficients known in the art. For example, the distribution according to the well-known Floyd-Steinberg distribution scheme uses a 3x3 matrix M_cd(<i>u,v</i>): <maths id="math0006"><math display="block"><msub><mi>M</mi><mi mathvariant="italic">ed</mi></msub><mfenced><mi>u</mi><mi>v</mi></mfenced><mo>=</mo><mfrac><mn>1</mn><mn>16</mn></mfrac><mfenced open="|" close="|"><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>7</mn></mtd></mtr><mtr><mtd><mn>3</mn></mtd><mtd><mn>5</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mfenced></math><img file="EP0808055B1_D0006.tif" /></maths>

0071The preferred embodiment performs error distribution using a selected one of plural 3-dimensional matrix of error-distribution coefficients M_cd(<i>u,v</i>,V_in (<i>x,y</i>)), stored in the error distribution coefficient table 135. For any input signal intensity gray level g=V_in(<i>x,y</i>), a 2-dimensional 3x3 square matrix of error-distribution coefficients M_cd(<i>u,v,g</i>) is defined: <maths id="math0007"><math display="block"><msub><mi>M</mi><mi mathvariant="italic">ed</mi></msub><mfenced><mi>u</mi><mi>v</mi><mi>g</mi></mfenced><mo>=</mo><mfrac><mn>1</mn><mi>S</mi></mfrac><mfenced><mi>g</mi></mfenced><mo>⋅</mo><mfenced open="|" close="|"><mtable><mtr><mtd><msub><mi>m</mi><mn>11</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>12</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>13</mn></msub><mfenced><mi>g</mi></mfenced></mtd></mtr><mtr><mtd><msub><mi>m</mi><mn>21</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>22</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>23</mn></msub><mfenced><mi>g</mi></mfenced></mtd></mtr><mtr><mtd><msub><mi>m</mi><mn>31</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>32</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>33</mn></msub><mfenced><mi>g</mi></mfenced></mtd></mtr></mtable></mfenced></math><img file="EP0808055B1_D0007.tif" /></maths>

0072Only four elements of this matrix are non-zero and are effectively used in the error distribution process: the elements m₂₃, m₃₁, m₃₂ and m₃₃ when the scan-line is processed in left-to-right order, and the elements m₂₁, m₃₁, m₃₂ and m₃₃ where the scan-line is processed in right-to-left order. For the sake of simplicity, only the set of elements {m₂₃, m₃₁, m₃₂, m₃₃} is considered. For the right-to-left pass, the elements m₂₃ and m₂₁ are interchanged, as well as the elements m₃₃ and m₃₁.

[Error Diffusion Coefficient Table]

0073The disclosed method uses different error-distribution coefficient matrices M_cd(<i>u,v</i>) for different intensities of the input signal g=V_in(<i>x,y</i>). In fact, the error distribution coefficient table 135 can be seen as a 3-dimensional table M_cd(<i>u, v, g</i>).

0074Typically, the input signal is often represented as a set of 8-bit sampled gray-scale values. In such a case, 256 different matrices M_cd(<i>u,v</i>) which correspond to 256 gray levels of the input signal are stored in the error-distribution coefficient table 135.

0075This section describes the process of building the error- distribution coefficient table, as illustrated in <figref idref="f0013">Figure 13</figref>. Two particular matrices M_cd(<i>u,v,g</i>) are defined which have turned out to be particularly effective for error-diffusion in two ranges of values of the input signal: the matrix M₁(<i>u,v,g</i>) in highlights and in shadows (step S1201), and the matrix M₂(u,v,g) in mid-tones (step S1202): <maths id="math0008"><math display="block"><msub><mi>M</mi><mn>1</mn></msub><mfenced><mi>u</mi><mi>v</mi><mi>g</mi></mfenced><mo>=</mo><mfrac><mn>1</mn><mn>3</mn></mfrac><mfenced open="|" close="|"><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>2</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr></mtable></mfenced><mo>=</mo><mfrac><mn>1</mn><msub><mi>S</mi><mn>1</mn></msub></mfrac><mfenced open="|" close="|"><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><msub><mi>a</mi><mn>23</mn></msub></mtd></mtr><mtr><mtd><msub><mi>a</mi><mn>31</mn></msub></mtd><mtd><msub><mi>a</mi><mn>32</mn></msub></mtd><mtd><msub><mi>a</mi><mn>33</mn></msub></mtd></mtr></mtable></mfenced></math><img file="EP0808055B1_D0008.tif" /></maths> for highlights and shadows, i.e., where <maths id="math0009"><math display="block"><mi>g</mi><mo>⊂</mo><mfenced open="[" close="]"><mn>0</mn><msub><mi>g</mi><mn>1</mn></msub></mfenced></math><img file="EP0808055B1_D0009.tif" /></maths><maths id="math0010"><math display="block"><mi>g</mi><mo>⊂</mo><mfenced open="[" close="]"><msub><mi>g</mi><mn>1</mn></msub><mn>255</mn></mfenced></math><img file="EP0808055B1_D0010.tif" /></maths><maths id="math0011"><math display="block"><msub><mi>M</mi><mn>2</mn></msub><mfenced><mi>u</mi><mi>v</mi><mi>g</mi></mfenced><mo>=</mo><mfrac><mn>1</mn><mn>8</mn></mfrac><mfenced open="|" close="|"><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>3</mn></mtd></mtr><mtr><mtd><mn>2</mn></mtd><mtd><mn>2</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mfenced><mo>=</mo><mfrac><mn>1</mn><msub><mi>S</mi><mn>2</mn></msub></mfrac><mfenced open="|" close="|"><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><msub><mi>b</mi><mn>23</mn></msub></mtd></mtr><mtr><mtd><msub><mi>b</mi><mn>31</mn></msub></mtd><mtd><msub><mi>b</mi><mn>32</mn></msub></mtd><mtd><msub><mi>b</mi><mn>33</mn></msub></mtd></mtr></mtable></mfenced></math><img file="EP0808055B1_D0011.tif" /></maths> for mid-tones, i.e., where <maths id="math0012"><math display="block"><mi>g</mi><mo>⊂</mo><mfenced open="[" close="]"><msub><mi>g</mi><mn>2</mn></msub><msub><mi>g</mi><mn>3</mn></msub></mfenced></math><img file="EP0808055B1_D0012.tif" /></maths>

0076In the interval [g₁,g₂] between dark grays and mid-tones, the following process which is illustrated at step S1203 ensures smooth transition between error-distribution with the matrix M₁(<i>u,v,g</i>) and error-distribution with the matrix M₂(<i>u,v,g</i>): <ul id="ul0002" list-style="none" compact="compact"><li>step A1: for every gray-level intensity level <i>g</i>, calculate intermediate coefficients im₂₃(<i>g</i>), im₃₁(<i>g</i>), im₃₂(<i>g</i>), im₃₃(<i>g</i>) and is (<i>g</i>) according to the following formulae. The formulae apply a weighted average to the values of M₁ and M₂, with the weight depending on gray-level g: <maths id="math0013"><math display="block"><msub><mi mathvariant="italic">im</mi><mn>23</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>a</mi><mn>23</mn></msub><mo>+</mo><mfrac><mrow><mfenced><mi>g</mi><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced><mo>•</mo><mfenced><msub><mi>b</mi><mn>23</mn></msub><mo>-</mo><msub><mi>a</mi><mn>23</mn></msub></mfenced></mrow><mfenced><msub><mi>g</mi><mn>2</mn></msub><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced></mfrac></math><img file="EP0808055B1_D0013.tif" /></maths><maths id="math0014"><math display="block"><msub><mi mathvariant="italic">im</mi><mn>32</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>a</mi><mn>32</mn></msub><mo>+</mo><mfrac><mrow><mfenced><mi>g</mi><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced><mo>•</mo><mfenced><msub><mi>b</mi><mn>32</mn></msub><mo>-</mo><msub><mi>a</mi><mn>32</mn></msub></mfenced></mrow><mfenced><msub><mi>g</mi><mn>2</mn></msub><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced></mfrac></math><img file="EP0808055B1_D0014.tif" /></maths><maths id="math0015"><math display="block"><msub><mi mathvariant="italic">im</mi><mn>31</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>a</mi><mn>31</mn></msub><mo>+</mo><mfrac><mrow><mfenced><mi>g</mi><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced><mo>•</mo><mfenced><msub><mi>b</mi><mn>31</mn></msub><mo>-</mo><msub><mi>a</mi><mn>31</mn></msub></mfenced></mrow><mfenced><msub><mi>g</mi><mn>2</mn></msub><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced></mfrac></math><img file="EP0808055B1_D0015.tif" /></maths><maths id="math0016"><math display="block"><msub><mi mathvariant="italic">im</mi><mn>33</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>a</mi><mn>33</mn></msub><mo>+</mo><mfrac><mrow><mfenced><mi>g</mi><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced><mo>•</mo><mfenced><msub><mi>b</mi><mn>33</mn></msub><mo>-</mo><msub><mi>a</mi><mn>33</mn></msub></mfenced></mrow><mfenced><msub><mi>g</mi><mn>2</mn></msub><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced></mfrac></math><img file="EP0808055B1_D0016.tif" /></maths><maths id="math0017"><math display="block"><mi mathvariant="italic">is</mi><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>S</mi><mn>1</mn></msub><mo>+</mo><mfrac><mrow><mfenced><mi>g</mi><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced><mo>•</mo><mfenced><msub><mi>S</mi><mn>2</mn></msub><mo>-</mo><msub><mi>S</mi><mn>1</mn></msub></mfenced></mrow><mfenced><msub><mi>g</mi><mn>2</mn></msub><mo>-</mo><msub><mi>g</mi><mn>1</mn></msub></mfenced></mfrac></math><img file="EP0808055B1_D0017.tif" /></maths></li><li>Step A2: for every gray-level intensity level <i>g</i>, calculate the greatest common divisor D(<i>g</i>)=gcd(im₂₃(<i>g</i>), im₃₁(<i>g</i>), im₃₂(<i>g</i>), im₃₃(<i>g</i>), is (<i>g</i>)).</li><li>Step A3: for every gray-level intensity level <i>g</i>, calculate all elements of the matrix M_cd(<i>u,v,g</i>): <maths id="math0018"><math display="block"><msub><mi>m</mi><mn>23</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><mfrac><mrow><msub><mi mathvariant="italic">im</mi><mn>23</mn></msub><mfenced><mi>g</mi></mfenced></mrow><mrow><mi>D</mi><mfenced><mi>g</mi></mfenced></mrow></mfrac></math><img file="EP0808055B1_D0018.tif" /></maths><maths id="math0019"><math display="block"><msub><mi>m</mi><mn>32</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><mfrac><mrow><msub><mi mathvariant="italic">im</mi><mn>32</mn></msub><mfenced><mi>g</mi></mfenced></mrow><mrow><mi>D</mi><mfenced><mi>g</mi></mfenced></mrow></mfrac></math><img file="EP0808055B1_D0019.tif" /></maths><maths id="math0020"><math display="block"><mi>S</mi><mfenced><mi>g</mi></mfenced><mo>=</mo><mfrac><mrow><mi mathvariant="italic">is</mi><mfenced><mi>g</mi></mfenced></mrow><mrow><mi>D</mi><mfenced><mi>g</mi></mfenced></mrow></mfrac></math><img file="EP0808055B1_D0020.tif" /></maths><maths id="math0021"><math display="block"><msub><mi>m</mi><mn>31</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><mfrac><mrow><msub><mi mathvariant="italic">im</mi><mn>31</mn></msub><mfenced><mi>g</mi></mfenced></mrow><mrow><mi>D</mi><mfenced><mi>g</mi></mfenced></mrow></mfrac></math><img file="EP0808055B1_D0021.tif" /></maths><maths id="math0022"><math display="block"><msub><mi>m</mi><mn>33</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><mfrac><mrow><msub><mi mathvariant="italic">im</mi><mn>33</mn></msub><mfenced><mi>g</mi></mfenced></mrow><mrow><mi>D</mi><mfenced><mi>g</mi></mfenced></mrow></mfrac></math><img file="EP0808055B1_D0022.tif" /></maths><maths id="math0023"><math display="block"><msub><mi>m</mi><mn>11</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>m</mi><mn>12</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>m</mi><mn>13</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>m</mi><mn>21</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><msub><mi>m</mi><mn>22</mn></msub><mfenced><mi>g</mi></mfenced><mo>=</mo><mn>0</mn></math><img file="EP0808055B1_D0023.tif" /></maths><maths id="math0024"><math display="block"><msub><mi>M</mi><mi mathvariant="italic">ed</mi></msub><mfenced><mi>u</mi><mi>v</mi><mi>g</mi></mfenced><mo>=</mo><mfrac><mn>1</mn><mrow><mi>S</mi><mfenced><mi>g</mi></mfenced></mrow></mfrac><mo>•</mo><mfenced open="|" close="|"><mtable><mtr><mtd><msub><mi>m</mi><mn>11</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>12</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>13</mn></msub><mfenced><mi>g</mi></mfenced></mtd></mtr><mtr><mtd><msub><mi>m</mi><mn>21</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>22</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>23</mn></msub><mfenced><mi>g</mi></mfenced></mtd></mtr><mtr><mtd><msub><mi>m</mi><mn>31</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>32</mn></msub><mfenced><mi>g</mi></mfenced></mtd><mtd><msub><mi>m</mi><mn>33</mn></msub><mfenced><mi>g</mi></mfenced></mtd></mtr></mtable></mfenced></math><img file="EP0808055B1_D0024.tif" /></maths></li></ul>

0077In the interval [<i>g</i>₃,<i>g</i>₄] between highlights and mid-tones, an algorithm similar to previously disclosed one can be applied. In the particular case when the highlights, dark grays and mid-tones are defined by numbers <i>g</i>₁=8, <i>g</i>₂=32, <i>g</i>₃=223 and <i>g</i>₄=247, this algorithm produces the set of coefficients {<i>m</i>₂₃(<i>g</i>), <i>m</i>₃₁(g), <i>m</i>₃₂(<i>g</i>), <i>m</i>₃₃(<i>g</i>)} shown in the Appendix.

[Well-Dispersed Threshold Mask]

0078The disclosed method uses a perturbation well-dispersed threshold mask having a limited number of levels which is stored in the threshold mask storage 140, in matrix form. This matrix contains set of threshold values T(<i>x,y</i>) may be constant (e.g. T(<i>x,y</i>)=.5) or may depend on the input intensity level (threshold function becomes T(<i>x,y,</i>V_in(<i>x,y</i>)) in this case) or on coordinates (<i>x,y</i>) (threshold modulation). The disclosed method has been implemented using a perturbation well-dispersed threshold mask having a limited number of levels which is stored in the threshold mask storage 140. The output value V_out(<i>x,y</i>) is carried out towards the output bi-level image storage unit 150.

0079This section describes the best expected mode for building well-dispersed threshold mask used in the disclosed enhanced error-diffusion method. This particular well-dispersed threshold mask has only three intensity levels. Without loss of generality, it can be stated that by employing very similar techniques one can obtain other masks, with limited number of intensity levels: 2-, 3-, 4-, 5-or, in general, <i>n</i>-level well-dispersed threshold masks, where <i>n</i> is a small number.

0080It has been observed that the Floyd-Steinberg error-diffusion method has its biggest structure artifacts when the intensity level of the input signal is close to small rational numbers: 1/2, 1/3, 2/3, 1/4, 3/4 etc. Structure artifact means that a set of perfectly structured patches of arbitrary shape is incorporated between randomly dispersed structures. <figref idref="f0002">FIG. 2</figref> illustrates this phenomenon. Non-linear behavior of almost all printing devices, and especially strong dot gain of current ink-jet printers accentuate harmful nature of structure artifacts. Namely, the areas 15, 16 and 17 in <figref idref="f0002">Figure 2</figref> appear particularly odd when printed with real ink-jet printers.

0081On the other hand, it has been observed that the same Floyd-Steinberg error-diffusion method produces much more even and stable results when the intensity level of the input signal is close to irrational numbers such as <maths id="math0025"><math display="block"><mfrac><mn>1</mn><mi>e</mi></mfrac><mo>≈</mo><mn>0.367879</mn><mspace width="4em" /><mfrac><mn>1</mn><mi mathvariant="normal">π</mi></mfrac><mo>≈</mo><mn>0.31831</mn><mspace width="5em" /><mfrac><mn>1</mn><mi mathvariant="normal">φ</mi></mfrac><mo>≈</mo><mn>0.618034</mn></math><img file="EP0808055B1_D0025.tif" /></maths> where e is the exponential constant e (base of natural logarithms), with numerical value 2.71828...; π is pi, with numerical value 3.14159...; φ is the golden ratio φ=(1+ Sqrt[5])/2, with numerical value 1.61803....

0082The best mode of the disclosed enhanced error-diffusion method employs an original iterative technique for building a well-dispersed multi-level threshold masks which is based on the observation mentioned above. This technique may be subdivided into several steps, which are illustrated in <figref idref="f0013">Figure 13</figref>, as follows: <ul id="ul0003" list-style="none" compact="compact"><li>Step B1: Produce a square bi-level halftone patch using any error-diffusion method (e.g. Floyd-Steinberg error-distribution scheme or an error-distribution scheme with other distribution coefficients), which corresponds to an irrational constant input intensity level. Threshold is constant and equals to 0.5 in this step. <figref idref="f0014">Figure 14(a)</figref> illustrates the step B1. In a preferred implementation, the input intensity level g for this first patch is chosen as g=1/φ=0.618034.</li><li>Step B2: Invert the values of the square bi-level halftone patch produced in the step B1. Inversion means that the pixels of the patch having the value of 0 receive the value of 1, and vice versa.</li><li>Step B3: Produce a square bi-level halftone patch using the same error-diffusion method that in the step B1, which corresponds to an irrational constant input intensity level. Use the square halftone patch produced in the previous steps as basic threshold mask. <figref idref="f0015">Figure 15(a)</figref> illustrates the step B3. In a preferred implementation, the input intensity level g for this second patch is chosen as g=1/φ³;=0.236068.</li><li>Step B4: Invert the value of the square bi-level halftone patch produced in the step B3 and average it together with the mask produced in B2.</li></ul>

0083One pass of steps B1-B4 is sufficient for building a 3-level well-dispersed multi-level threshold mask. When the number of levels in well-dispersed multi-level threshold mask is bigger than 3, the steps B3 and B4 should be repeated iteratively.

0084The main idea which governs the iterative technique described above is the fact that (a) the first-iteration bi-level pattern obtained in step B1 has visually pleasant dispersion structure and (b) all successive patterns obtained in steps B3-B4 are built upon the first-iteration mask. This means that, according to the above-described technique, a pseudo-random distribution obtained during the <i>n-th</i> step contains the distribution obtained during (<i>n-1</i>)-th step, as a subset. Consequently, all halftone masks are dependent, and by averaging all masks (which inherently adds all masks together), one can obtain a multi-level mask whose levels individually have very similar visual appearance and very similar well-dispersed nature. <figref idref="f0016">Figure 16(a)</figref> illustrates this technique of building multi-level well-dispersed mask.

0085The matrix shown in <figref idref="f0016">Figure 16(a)</figref> can be rearranged in such a way that all three levels are symmetrically spaced around the intensity <i>g</i>₀=0.5, as shown in <figref idref="f0017">Figure 17(a)</figref>. The distance d between go and two other intensity levels influences the force of the effect of scattering the structure effect. By increasing <i>d</i>, one reinforces the randomness of the halftoned output image, when the 3-level dispersed mask is used as basic threshold matrix. On the contrary, by diminishing <i>d,</i> one makes the halftoned output image closer to the result obtained with conventional error-diffusion, with no threshold modulation.

0086It is emphasized that several changes may be applied on the above-described system without departing from the teaching of the invention. It is intended that all the mater contained in the present disclosure, or shown in the accompanying drawings, shall be interpreted as illustrative rather than limiting.

[Advantages]

0087The invented method was conceived in order to cope with several drawbacks and imperfections of different halftoning methods known in the art, which are described in the section Description Of The Related Art.

0088The disclosed method improves the following aspects of the Floyd-Steinberg popular error-diffusion scheme: (1) it suppress wormy structures in highlights and dark grays, proper to Floyd-Steinberg error-diffusion; (2) it have smoother tone reproduction curve, with respect to Floyd-Steinberg's one; and (3) it diminishes considerably structure artifacts of the Floyd-Steinberg error-diffusion scheme.

0089The disclosed method is simple, highly understandable, and may be implemented in the printer driver in very efficient way.

0090The invention has been described with respect to a particular illustrative embodiment. It is to be understood that the invention is not limited to the above described embodiment and that various changes and modifications may be made by those of ordinary skill in the art without departing from the scope of the claims.

APPENDIX

0091<tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="6"><colspec colnum="1" colname="col1" colwidth="11mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="11mm" /><thead><row><entry valign="top">g</entry><entry valign="top">m₂₃(g)</entry><entry valign="top">m₃₁(g)</entry><entry valign="top">m₃₁(g)</entry><entry valign="top">m₃₃(g)</entry><entry valign="top">S(g)</entry></row></thead><tbody><row><entry>0</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>1</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>2</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>3</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>4</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>5</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>6</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>7</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>8</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>9</entry><entry>377</entry><entry>6</entry><entry>190</entry><entry>3</entry><entry>576</entry></row><row><entry>10</entry><entry>185</entry><entry>6</entry><entry>94</entry><entry>3</entry><entry>288</entry></row><row><entry>11</entry><entry>121</entry><entry>6</entry><entry>62</entry><entry>3</entry><entry>192</entry></row><row><entry>12</entry><entry>89</entry><entry>6</entry><entry>46</entry><entry>3</entry><entry>144</entry></row><row><entry>13</entry><entry>349</entry><entry>30</entry><entry>182</entry><entry>15</entry><entry>576</entry></row><row><entry>14</entry><entry>19</entry><entry>2</entry><entry>10</entry><entry>1</entry><entry>32</entry></row><row><entry>15</entry><entry>335</entry><entry>42</entry><entry>178</entry><entry>21</entry><entry>576</entry></row><row><entry>16</entry><entry>41</entry><entry>6</entry><entry>22</entry><entry>3</entry><entry>72</entry></row><row><entry>17</entry><entry>107</entry><entry>18</entry><entry>58</entry><entry>9</entry><entry>192</entry></row><row><entry>18</entry><entry>157</entry><entry>30</entry><entry>86</entry><entry>15</entry><entry>288</entry></row><row><entry>19</entry><entry>307</entry><entry>66</entry><entry>170</entry><entry>33</entry><entry>576</entry></row><row><entry>20</entry><entry>25</entry><entry>6</entry><entry>14</entry><entry>3</entry><entry>48</entry></row><row><entry>21</entry><entry>293</entry><entry>78</entry><entry>166</entry><entry>39</entry><entry>576</entry></row><row><entry>22</entry><entry>143</entry><entry>42</entry><entry>82</entry><entry>21</entry><entry>288</entry></row><row><entry>23</entry><entry>31</entry><entry>10</entry><entry>18</entry><entry>5</entry><entry>64</entry></row><row><entry>24</entry><entry>17</entry><entry>6</entry><entry>10</entry><entry>3</entry><entry>36</entry></row><row><entry>25</entry><entry>265</entry><entry>102</entry><entry>158</entry><entry>51</entry><entry>576</entry></row><row><entry>26</entry><entry>251</entry><entry>114</entry><entry>154</entry><entry>57</entry><entry>576</entry></row><row><entry>27</entry><entry>251</entry><entry>114</entry><entry>154</entry><entry>57</entry><entry>576</entry></row><row><entry>28</entry><entry>61</entry><entry>30</entry><entry>38</entry><entry>15</entry><entry>144</entry></row><row><entry>29</entry><entry>79</entry><entry>42</entry><entry>50</entry><entry>21</entry><entry>192</entry></row><row><entry>30</entry><entry>115</entry><entry>66</entry><entry>74</entry><entry>33</entry><entry>288</entry></row><row><entry>31</entry><entry>223</entry><entry>138</entry><entry>146</entry><entry>69</entry><entry>576</entry></row><row><entry>32</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>33</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>34</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>35</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>36</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>37</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>38</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>39</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>40</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>41</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>42</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>43</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>44</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>45</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>46</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>47</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>48</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>49</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>50</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>51</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>52</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>53</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>54</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>55</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>56</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>57</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>58</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>59</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>60</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>61</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>62</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>63</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>64</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>65</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>66</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>67</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>68</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>69</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>70</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>71</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>72</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>73</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>74</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>75</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>76</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>77</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>78</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>79</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>80</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>81</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>82</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>83</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>84</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>85</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>86</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>87</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>88</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>89</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>90</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>91</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>92</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>93</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>94</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>95</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>96</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>97</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>98</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>99</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>100</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>101</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>102</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>103</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>104</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>105</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>106</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>107</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>108</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>109</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>110</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>111</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>112</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>113</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>114</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>115</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>116</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>117</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>118</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>119</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>120</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>121</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>122</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>123</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>124</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>125</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>126</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>127</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>128</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>129</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>130</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>131</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>132</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>133</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>134</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>135</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>136</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>137</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>138</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>139</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>140</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>141</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>142</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>143</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>144</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>145</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>146</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>147</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>148</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>149</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>150</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>151</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>152</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>153</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>154</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>155</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>156</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>157</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>158</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>159</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>160</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>161</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>162</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>163</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>164</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>165</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>166</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>167</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>168</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>169</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>170</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>171</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>172</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>173</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>174</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>175</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>176</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>177</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>178</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>179</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>180</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>181</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>182</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>183</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>184</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>185</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>186</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>187</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>188</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>189</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>190</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>191</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>192</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>193</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>194</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>195</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>196</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>197</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>198</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>199</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>200</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>201</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>202</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>203</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>204</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>205</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>206</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>207</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>208</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>209</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>210</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>211</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>212</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>213</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>214</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>215</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>216</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>217</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>218</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>219</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>220</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>221</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>222</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>223</entry><entry>3</entry><entry>2</entry><entry>2</entry><entry>1</entry><entry>8</entry></row><row><entry>224</entry><entry>223</entry><entry>138</entry><entry>146</entry><entry>69</entry><entry>576</entry></row><row><entry>225</entry><entry>115</entry><entry>66</entry><entry>74</entry><entry>33</entry><entry>288</entry></row><row><entry>226</entry><entry>79</entry><entry>42</entry><entry>50</entry><entry>21</entry><entry>192</entry></row><row><entry>227</entry><entry>61</entry><entry>30</entry><entry>38</entry><entry>15</entry><entry>144</entry></row><row><entry>228</entry><entry>251</entry><entry>114</entry><entry>154</entry><entry>57</entry><entry>576</entry></row><row><entry>229</entry><entry>43</entry><entry>18</entry><entry>26</entry><entry>9</entry><entry>96</entry></row><row><entry>230</entry><entry>265</entry><entry>102</entry><entry>158</entry><entry>51</entry><entry>576</entry></row><row><entry>231</entry><entry>17</entry><entry>6</entry><entry>10</entry><entry>3</entry><entry>36</entry></row><row><entry>232</entry><entry>31</entry><entry>10</entry><entry>18</entry><entry>5</entry><entry>64</entry></row><row><entry>233</entry><entry>143</entry><entry>42</entry><entry>82</entry><entry>21</entry><entry>288</entry></row><row><entry>234</entry><entry>293</entry><entry>78</entry><entry>166</entry><entry>39</entry><entry>576</entry></row><row><entry>235</entry><entry>25</entry><entry>6</entry><entry>14</entry><entry>3</entry><entry>48</entry></row><row><entry>236</entry><entry>307</entry><entry>66</entry><entry>170</entry><entry>33</entry><entry>156</entry></row><row><entry>237</entry><entry>157</entry><entry>30</entry><entry>86</entry><entry>15</entry><entry>288</entry></row><row><entry>238</entry><entry>107</entry><entry>18</entry><entry>58</entry><entry>9</entry><entry>192</entry></row><row><entry>239</entry><entry>41</entry><entry>6</entry><entry>22</entry><entry>3</entry><entry>72</entry></row><row><entry>240</entry><entry>335</entry><entry>42</entry><entry>178</entry><entry>21</entry><entry>576</entry></row><row><entry>241</entry><entry>19</entry><entry>2</entry><entry>10</entry><entry>1</entry><entry>32</entry></row><row><entry>242</entry><entry>349</entry><entry>30</entry><entry>182</entry><entry>15</entry><entry>576</entry></row><row><entry>243</entry><entry>89</entry><entry>6</entry><entry>46</entry><entry>3</entry><entry>144</entry></row><row><entry>244</entry><entry>121</entry><entry>6</entry><entry>62</entry><entry>3</entry><entry>192</entry></row><row><entry>245</entry><entry>185</entry><entry>6</entry><entry>94</entry><entry>3</entry><entry>288</entry></row><row><entry>246</entry><entry>377</entry><entry>6</entry><entry>190</entry><entry>3</entry><entry>576</entry></row><row><entry>247</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>248</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>249</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>250</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>251</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>252</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>253</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>254</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row><row><entry>255</entry><entry>2</entry><entry>0</entry><entry>1</entry><entry>0</entry><entry>3</entry></row></tbody></tgroup></table></tables>