HK1258161B - Method for rendering color images - Google Patents

Description

Method for rendering color images

RELATED APPLICATIONS

This application relates to U.S. publication No. 2014/0340430; U.S. publication No. 2016/0091770; and U.S. patent nos. 9,383,623 and 9,170,468. Other related applications and patents are discussed below.

Technical Field

The invention relates to a method for rendering a color image. More particularly, the invention relates to a method for halftoning (halftoning) a color image with a limited set of primary colors available, and the limited set may not be well structured. The method of the present invention is particularly, but not exclusively, for use in a colour electrophoretic display.

Background

Halftoning has been used in the printing industry for decades to represent gray tones by covering each pixel of white paper with a different proportion of black ink. Similar halftone schemes may be used with CMY or CMYK color printing systems, with the color channels varying independently of each other.

However, there are many color systems in which the color channels cannot be varied independently of each other, because each pixel can display any one of a limited set of primary colors (such systems may be referred to hereinafter as "limited palette display" or "LPD"); the ECD patent color display is of this type. To produce other colors, the primary colors must be spatially dithered to produce the correct color perception. It is known to achieve such spatial dithering by using only the primary colors at the vertices of the tetrahedron containing the desired color for any desired color; see, for example:

arad, n., Shaked, d., Baharav, z., & Lin, Q. (1999), Barycentric Screening, and

ostromoukhov, Victor, and Roger D.Hersch, "Multi-color and diagnostic," Proceedings of the 26th annular conference on Computer graphics and interactive technology, ACM Press/Addison-Wesley Publishing Co., 1999.

Both of these documents implement dithering by a threshold array based screening method, which is a simple dithering method that has been found not to give good results in ECD patent displays.

Standard dithering algorithms, such as error diffusion algorithms (where the "error" introduced by printing one pixel in a particular color different from the color theoretically required for that pixel is distributed between adjacent pixels, thereby producing an overall correct color perception) can be used for limited-color displays. However, such standard algorithms are usually intended for use with "well-structured" finite palettes, in the sense that the distance in the appropriate color space between the primary colors is substantially constant. There is considerable literature on the problem of designing an optimal palette that performs well in terms of error diffusion; see, for example:

kolpatzik, Bernd W., and Charles A. Bouman. "Optimized Universal Color Pattern Design for Error diffusion." Journal of Electronic Imaging 4.2(1995):131- "143.

However, in ECDs and similar limited palette displays, where the limited palette is defined by colors that can be generated by the system, the limited palette may not be well structured, i.e., the distances between the various primary colors in the color space may differ greatly from each other.

FIG. 1 of the accompanying drawings is a schematic flow chart diagram of a prior art palette-based error diffusion method, generally designated 100. At input 102, a color value x_i,jAre fed to the processor 104 where they are added to the output of the error filter 106 (described below) to produce a modified input u in the processor 104_i,j. Modified input u_i,jIs fed to a quantizer 108, the quantizer 108 also receiving the palette of output devices P_kThe details of. The quantizer 108 determines the appropriate color for the pixel under consideration, given by:

and feeds the appropriate color to the device controller (or stores the color value for later transmission to the device controller). Modified input u_i,jAnd output y_i,jAre fed to the processor 110, the processor 110 calculates an error value e_i,jWherein:

ei_,j＝ui_,j-yi_,j

then the error value e_i,jThe error filter 106 is fed to the error filter 106, and the error filter 106 is used to distribute the error values over one or more selected pixels. For example, if error diffusion is performed on pixels from top to bottom in the image and from left to right in each row, error filter 106 may distribute the error over the next pixel in the row being processed, and the three nearest neighbors of the pixel processed in the next row down. Alternatively, the error filter 106 may distribute the error over the next two pixels in the row being processedAnd the nearest neighbors of the pixels processed in the next two rows down. It should be appreciated that the error filter need not apply the same proportion of error to each pixel of the distributed error; for example, when the error filter 106 distributes the errors over the next pixel in the row being processed, and three nearest neighbors of the pixel being processed in the next row down, it may be appropriate to distribute more errors to the next pixel in the row being processed and to the pixel immediately below the pixel being processed, and to distribute fewer errors to the two diagonal neighbors of the pixel being processed.

Unfortunately, it has been found that if one attempts to use conventional error diffusion methods such as that shown in fig. 1 for ECDs and similar limited color palette displays, severe artifacts are created which may render the resulting image unusable. For example, in one type of artifact (hereinafter referred to as a "transient" artifact), when stepping from one input color to the next very different color, the spatial transient may be so long that the output never reaches the correct average value even over the size of the object to be rendered. In another type of artifact (hereinafter referred to as the "mode-hopping" artifact), for a constant color input image, the output hops between two different sets of primary colors at seemingly random locations in the image. Although the two sets of primaries should ideally produce an output close to the requested color, the resulting output is not robust, as small variations in the system may result in such switching between the two sets, and texture variations at such jumps are also noticeable and unpleasant.

Disclosure of Invention

The present invention seeks to provide a method of rendering a colour image which can be used with palettes which are not well constructed and which can be large, without producing transient and mode-hopping artefacts to which standard error diffusion methods are susceptible.

In one aspect, the present invention provides a method of rendering an image on a display, the method comprising:

receiving input data representing a color of a pixel to be rendered;

combining the input data with error data generated from at least one pixel of a previous rendering to form modified input data;

determining a simplex surrounding the modified input data in a color space, and a display primary associated with the simplex;

converting the modified image data into barycentric coordinates based on the simplex, and setting the output data as a primary color having the largest barycentric coordinate;

calculating a difference between the modified input data and the output data of the pixel, thereby generating error data of the pixel;

applying the error data thus generated to at least one later rendered pixel; and

the output data of the plurality of pixels is provided to a display, thereby rendering an image on the display.

In one form of the process, the modified input data is tested to determine if it is within the gamut of the display, and if the modified input data is outside the gamut, the modified input data is further modified by being projected onto the gamut. The projection may be achieved along a line of constant brightness and hue towards the neutral axis of the color space. Alternatively, the projection may be effected towards the color represented by the input data of the pixel until the gamut boundary is reached. Typically, the color space used will be three-dimensional, such that the simplex will be a tetrahedron. The error data may, and typically will, be distributed over more than one pixel. For example, if the method of the present invention is implemented using a top-to-bottom and left-to-right pixel processing order, the error data will typically be distributed over at least the pixels to the right and the pixels below the pixel being rendered. Alternatively, the error data may be distributed over the pixel to the right of the pixel being rendered and three pixels below and adjacent to the pixel being rendered. In particular, in the latter case, it is not necessary to distribute an equal proportion of error data over all the pixels over which it is dispersed; for example, when the error is distributed over the pixel on the right and three adjacent pixels in the next row, it may be advantageous to allocate more error data to two pixels sharing an edge with the pixel being rendered (as compared to two pixels sharing only a vertex).

The invention extends to an apparatus comprising: a display device having a plurality of pixels, each pixel being arranged to display any one of a plurality of primary colors; and a computing device capable of executing the method of the present invention and supplying its output data to a display device, thereby causing the display device to display an image.

The invention also extends to a non-transitory computer storage medium comprising instructions which, when executed by a processor, cause the processor to perform the method of the invention.

Drawings

As already noted, fig. 1 of the accompanying drawings is a flow chart of a prior art method for rendering a color image.

Fig. 2 is a similar flow chart illustrating the method of the present invention.

Detailed Description

The invention is based on the following recognition: the transients and mode skip artifacts discussed above are due to the fact that the quantizer (108 in fig. 1) has an under-constrained primary list available. In a three-dimensional color space, any color in the device gamut can be rendered by dithering only four primary colors, and the invention is based on constraining the selection of primary colors in an appropriate way to ensure that only a limited set of primary colors is used during quantization.

The subset of primary colors that can be used in dither patterns to represent a given color is not unique; for example, in a three-dimensional color space, any set of four or more primary colors defining a volume surrounding a given color in the color space may be used in the dither pattern. Even if the subset of primary colors is limited to only four, any set of four primary colors defining a tetrahedron enclosing a given color may be used. However, in order to avoid mode-hopping artifacts, subsets of the primary colors should be assigned to particular colors in such a way that any parametric path through the color space results in a smooth change of the proportions of the various primary colors used with respect to the parameters. This may be achieved by decomposing the overall color gamut of the system (convex hull of all primary colors) into tetrahedrons having the primary colors as vertices and then assigning to each color to be rendered a subset of the primary colors corresponding to the vertices of its bounding tetrahedrons. This can be achieved by Delaunay triangulation, which decomposes the convex hull of the primary colors into a set of tetrahedra whose circumscribed sphere does not enclose any vertex from another tetrahedron. This is convenient, but other decompositions of the gamut may also be beneficial; for example, to reduce halftone granularity, a subset of the primary colors may be selected to have low luminance variation. It should be understood that the decomposition method can be generalized to color spaces of any number of dimensions by using a suitable simplex for the number of dimensions involved instead of using tetrahedrons in three-dimensional space.

A preferred embodiment of the process of the present invention is shown in figure 2 of the accompanying drawings, figure 2 being a schematic flow chart substantially similar to figure 1. As in the prior art method shown in FIG. 1, the method shown in FIG. 2 begins with an input 102 in which a color value x_i,jAre fed to a processor 104 where they are added to the output of an error filter 106 to produce a modified input u_i,j. (Again, this description assumes an input value x_i,jSuch that the modified input u_i,jWithin the color gamut of the device. If this is not the case, some preliminary modification of the input or modified input may be necessary to ensure that they are within the appropriate color gamut. ) However, modified input u_i,jIs fed to a gamut projector 206.

The gamut projector 206 is provided to handle the following possibilities: even if the value x is input_i,jModified input u within the gamut of the system_i,jOr may not be within the gamut of the system, i.e., the error correction introduced by the error filter 106 may modify the input u_i,jOutside the color gamut of the system. In this case, it is not possible to use the modified input u_i,jA subset of the primary colors is chosen because it will lie outside all defined tetrahedra. Although other ways of this problem may be envisaged, it has been found that the only way to give a stable result is to modify the value u before further processing_i,jProjected onto the color gamut of the system. Such projection can be accomplished in a variety of ways; for example, the projection may be along a constant brightness and hue towards the neutral axis. However, a preferred projection method is to project towards the input color until the gamut boundary is reached.

Input u 'of projection'_i,jThe values are fed to a simplex finder which feeds a subset P of the appropriate primary colors_ksReturning to processor 210, processor 210 also receives projected input u'_i,jValues and convert them to a subset of primary colors P_ksThe coordinates of the center of gravity of the defined tetrahedron (or other simplex). Although it appears that the primary colors are a subset P_ksShould be based on the color x assigned to the input pixel_i,jBut this does not work; the subset of primary colors must be based on the projected input u'_i,jThe value is obtained. The output λ of the processor 210 is provided to a quantizer 212, the function of the quantizer 212 being very different from that of the quantizer 108 shown in fig. 1. The quantizer 212 selects the primary color associated with the largest barycentric coordinate instead of performing conventional error diffusion. This is equivalent to center of gravity thresholding (see Arad et al, supra) using thresholds (1/3,1/3,1/3), which do not correspond to the minimum distance determination performed by quantizer 108 in fig. 1. The output y from the quantizer 212 is then_i,jTo the device controller in the usual manner, or stored.

Output y_i,jValue and modified input value u_i,jOr the projected input value u'_i,j(shown as a dashed line in FIG. 2) is provided to the processor 214, and the processor 214 calculates an error value e by_i,j：

e_i,j＝u’_i,j-y_i,jOr

e_i,j＝u_i,j-y_i,j

(depending on which set of input values is being used) and passes the error signal to the error filter 106 in the same manner as described above with reference to fig. 1.

Theoretically, it seems that the original modified input value u should be used_i,jRather than the projected input value u'_i,jCalculating an error value e_i,jBecause the former accurately represents the difference between the desired color and the actual color of the pixel; in fact, the errors introduced by the projection step are "discarded" using the latter values. Empirically, it has been found that which set of input values to use does not have a significant impact on the accuracy of the color representation. Furthermore, the type of projection implemented by the gamut projector 206 must be considered in deciding whether to use the input values before or after the projection in the error calculation. Certain types of projection, such as along lines of constant hue and brightness, provide a continuous and fixed extension of the quantizer domain boundaries into the out-of-gamut volume, thus allowing the use of un-projected input values in the error calculation without the risk of instability of the output values. Other types of projections do not provide a continuous and fixed extension of the quantizer domain boundaries; for example, projecting an input color until a gamut boundary is reached fails to provide a fixed extension of the quantizer gamut boundary, but the quantizer gamut varies with the input value, and in these cases the projected input value should be used to determine the error value, since using an un-projected value may result in an unstable approach, where the error value may be increased without limit.

From the foregoing, it can be seen that the present invention can provide improved color in a limited color palette display with fewer artifacts than are obtained using conventional error diffusion techniques. The invention may be used in display systems capable of displaying continuous colors (or at least very many colors), but where the available primary colors are not uniformly spread over the entire color gamut; for example, an interference-based display that controls the gap width may display a large number of colors at each pixel, but with a predetermined structure among the primary colors, which is located on a one-dimensional manifold (one-dimensional manifold). The invention may also be used with electrochromic displays.

For further details of color display systems to which the present invention may be applied, the reader is referred to the above ECD patent (which also discusses electrophoretic displays in detail) and the following patents and publications:

U.S. Pat. Nos. 6,017,584; 6,545,797, respectively; 6,664,944, respectively; 6,788,452, respectively; 6,864,875, respectively; 6,914,714, respectively; 6,972,893, respectively; 7,038,656, respectively; 7,038,670, respectively; 7,046,228; 7,052,571, respectively; 7,075,502, respectively; 7,167,155, respectively; 7,385,751, respectively; 7,492,505, respectively; 7,667,684, respectively; 7,684,108, respectively; 7,791,789, respectively; 7,800,813, respectively; 7,821,702, respectively; 7,839,564, respectively; 7,910,175, respectively; 7,952,790, respectively; 7,956,841, respectively; 7,982,941, respectively; 8,040,594, respectively; 8,054,526, respectively; 8,098,418, respectively; 8,159,636, respectively; 8,213,076, respectively; 8,363,299, respectively; 8,422,116, respectively; 8,441,714, respectively; 8,441,716, respectively; 8,466,852, respectively; 8,503,063, respectively; 8,576,470, respectively; 8,576,475, respectively; 8,593,721, respectively; 8,605,354, respectively; 8,649,084, respectively; 8,670,174, respectively; 8,704,756, respectively; 8,717,664, respectively; 8,786,935, respectively; 8,797,634, respectively; 8,810,899, respectively; 8,830,559, respectively; 8,873,129, respectively; 8,902,153, respectively; 8,902,491, respectively; 8,917,439, respectively; 8,964,282, respectively; 9,013,783, respectively; 9,116,412, respectively; 9,146,439, respectively; 9,164,207, respectively; 9,170,467, respectively; 9,170,468, respectively; 9,182,646, respectively; 9,195,111, respectively; 9,199,441, respectively; 9,268,191, respectively; 9,285,649, respectively; 9,293,511, respectively; 9,341,916, respectively; 9,360,733, respectively; 9,361,836, respectively; 9,383,623, respectively; and 9,423,666; and U.S. patent application publication No. 2008/0043318; 2008/0048970, respectively; 2009/0225398, respectively; 2010/0156780, respectively; 2011/0043543, respectively; 2012/0326957, respectively; 2013/0242378, respectively; 2013/0278995, respectively; 2014/0055840, respectively; 2014/0078576, respectively; 2014/0340430, respectively; 2014/0340736, respectively; 2014/0362213, respectively; 2015/0103394, respectively; 2015/0118390, respectively; 2015/0124345, respectively; 2015/0198858, respectively; 2015/0234250, respectively; 2015/0268531, respectively; 2015/0301246, respectively; 2016/0011484, respectively; 2016/0026062, respectively; 2016/0048054, respectively; 2016/0116816, respectively; 2016/0116818, respectively; and 2016/0140909.

Claims (13)

1. A method of rendering an image on a plurality of pixels of a display, wherein each pixel of the plurality of pixels is capable of displaying any one of a set of primary colors, the method comprising:

receiving input data (102) representing colors of the plurality of pixels to be rendered;

sequentially for each pixel of the plurality of pixels:

comparing the input data with error data generated from at least one pixel of a previous rendering (e)_i,j) Combining (104) to form modified input data (u)_i,j)；

Determining (208) input data (u) surrounding the modification in a color space_i,j) And a display primary color P associated with said simplex_ks}；

Inputting the modified numberAccording to (u)_i,j) Converting (210) to barycentric coordinates based on said simplex and converting the output data (y) of said pixels_i,j) Setting (212) as the primary color with the largest barycentric coordinate; and

calculating (214) the modified input data (u)_i,j) And output data (y) of said pixel_i,j) Difference between them, thereby generating error data (e) of the pixel_i,j)；

Error data (e) to be generated thereby_i,j) Applying (106) to at least one later rendered pixel; and

outputting data (y) of the plurality of pixels_i,j) Is provided to the display to render the image on the plurality of pixels of the display.

2. The method according to claim 1, further comprising testing (206) the modified input data (u)_i,j) To determine whether it is within a color gamut of the display and, if the modified input data is outside the color gamut, further modify the modified input data by projecting the modified input data onto the color gamut.

3. The method of claim 2, wherein the projection of the modified input data is effected along a line of constant brightness and hue towards a neutral axis of the color space.

4. The method of claim 2, wherein the projection of the modified input data is effected towards a color represented by the input data of the pixel until a gamut boundary is reached.

5. Method of claim 2, wherein the projected input data (u'_i,j) For conversion (210) to barycentric coordinates and for generation (214) of the error data.

6. The method of claim 2, wherein theProjected input data (u'_i,j) For conversion (210) to barycentric coordinates, but modified image data (u) before said projection_i,j) For the generation (214) of the error data.

7. The method of claim 1, wherein the color space is three-dimensional such that the simplex is a tetrahedron.

8. The method according to claim 1, wherein the error data (e)_i,j) Distributed over more than one pixel.

9. The method according to claim 1, wherein the error data (e)_i,j) Distributed over at least four pixels.

10. The method of claim 9, wherein a proportion of the error data applied to different pixels is varied.

11. The method of claim 1, wherein the display is an electrophoretic display.

12. An apparatus, comprising: a display having a plurality of pixels, each pixel arranged to display any one of a plurality of primary colors; and a computing device capable of performing the method of any one of claims 1 to 11 and supplying output data of the plurality of pixels thereof to the display, thereby causing the display to display an image.

13. A non-transitory computer storage medium comprising a program that, when executed by a processor, causes the processor to perform the method of any one of claims 1 to 11.