System for rendering color images

Abstract

An image is rendered on a display having a limited number of primary colors by (104) combining input data representing the color of a pixel to be rendered with error data to form modified input data, determining in a color space the simplex (208—typically a tetrahedron) enclosing the modified input data and the primary colors associated with the simplex, converting (210) the modified image data to barycentric coordinates based upon the primary colors associated with the simplex and (212) setting output data to the primary having the largest barycentric coordinate. calculating (214) the difference between the modified input data and the output data for the pixel, thus generating error data, applying (106) this error data to at least one later-rendered pixel, and applying the output data to the display and thus rendering the image on the display. Apparatus and computer-storage media for carrying out this process are also provided.

Claims

1. A system for producing a color image, the system comprising: a display device having a plurality of pixels, each of which is arranged to display any one of a plurality of primary colors; and a computing device in communication with the display device, the computing device being configured to render color images on the display device by: receiving input data representing colors to be displayed at each of the plurality of pixels; combining the input data with error data to create modified input data; determining in a color space a simplex enclosing the modified input data, wherein the vertices of the simplex comprise a subset of the display primary colors that is smaller than the complete set of display primary colors, hereafter a simplex primary color; setting output data for a first pixel corresponding to one of the simplex primary colors; and calculating a difference between the modified input data for the first pixel and the output data for the first pixel, thereby generating new error data for the first pixel; combining input data for a second pixel with the new error data for the first pixel to create new modified input data for the second pixel; determining in the color space a new simplex enclosing the modified input data and the new modified input data for the second pixel, wherein the vertices of the new simplex comprise a subset of the display primary colors that is smaller than the complete set of display primary colors, hereafter a new simplex primary color; and setting output data for the second pixel corresponding to one of the new simplex primary colors.

2. The system of claim 1, wherein the computing device evaluates the modified input data to determine whether it is within a measured color gamut of the display and, if the modified input data is outside the measured color gamut of the display, further modifies the modified input data by projecting the modified input data on to the measured color gamut of the display to produce projected input data which are used in place of the modified input data.

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

4. The system of claim 2, wherein the projected input data is used for the generation of the error data.

5. The system of claim 1, wherein the color space is three-dimensional so that the simplex is a tetrahedron.

6. The system of claim 1, wherein the new error data for the first pixel is used in the processing of input data for a third pixel.

7. The system of claim 1, wherein the display device is an electrophoretic display.

8. The system of claim 1, wherein the display device includes a controller, and the computing device sends the output data for the first pixel and the output data for the second pixel to the controller.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 of the accompanying drawings is a schematic flow diagram of a prior art palette based error diffusion method.

(2) FIG. 2 is a schematic flow diagram, similar to that of FIG. 1, but illustrating a preferred method of the present invention.

DETAILED DESCRIPTION

(3) The present invention is based upon the recognition that the transient and pattern jumping artifacts discussed above result from the fact that the quantizer (108 in FIG. 1) has available to it an under-constrained list of primaries. In a three dimensional color space, any color in the device gamut can be rendered by dithering only four primaries, and the present invention is based upon constraining the choice of primaries in an appropriate way to ensure that only a restricted set of primaries are used during quantization.

(4) The subset of primaries that can used in a dither pattern to represent a given color is not unique; for example in a three dimensional color space, any set of four or more primaries which define a volume in the color space enclosing the given color can be used in a dither pattern. Even if one restricts the subset of primaries to only four, any set of four primaries which define a tetrahedron enclosing the given color can be used. However, to avoid pattern jumping artifacts, the assignment of subsets of primaries to particular colors should be made in such a way that any parametric path through color space results in a smooth change in proportions of the various primaries used with respect to the parameter. This can be achieved by decomposing the total gamut of the system (the convex hull of all the primaries) into tetrahedra with primaries as vertices and then assigning to each color to be rendered the subset of primaries corresponding to the vertices of its enclosing tetrahedron. This may be effected by Delaunay triangularization, which decomposes the convex hull of the primaries into a set of tetrahedra, the circumspheres of which do not enclose any vertex from another tetrahedron. This is convenient, but other decompositions of the color gamut may also be beneficial; for example, to reduce halftone graininess, the subsets of primaries could be chosen to have low variation in lightness. It will be appreciated that the decomposition methods can be generalized to color spaces of any number of dimensions by the use of the appropriate simplexes for the numbers of dimensions involved instead of using tetrahedra in a three dimensional space.

(5) A preferred embodiment of the process of the invention is illustrated in FIG. 2 of the accompanying drawings, which is a schematic flow diagram generally similar to FIG. 1. As in the prior art method illustrated in FIG. 1, the method illustrated in FIG. 2 begins at an input 102, where color values x.sub.i,j are fed to a processor 104, where they are added to the output of an error filter 106 to produce a modified input u.sub.i,j. (Again, this description assumes that the input values x.sub.i,j are such that the modified inputs u.sub.i,j are within the color gamut of the device.) If this is not the case, some preliminary modification of the inputs or modified inputs may be necessary to ensure that they lie within the appropriate color gamut.) The modified inputs u.sub.i,j are, however, fed to a gamut projector 206.

(6) The gamut projector 206 is provided to deal with the possibility that, even though the input values x.sub.i,j are within the color gamut of the system, the modified inputs u.sub.i,j may not be, i.e., that the error correction introduced by the error filter 106 may take the modified inputs u.sub.i,j outside the color gamut of the system. In such a case, it would not be possible to choose a subset of primaries for the modified input u.sub.i,j since it would lie outside all defined tetrahedra. Although other ways of this problem can be envisioned, the only one which has been found to give stable results is to project the modified value u.sub.i,j on to the color gamut of the system before further processing. This projection can be done in numerous ways; for example, projection may be effected towards the neutral axis along constant lightness and hue. However, the preferred projection method is to project towards the input color until the gamut boundary is reached.

(7) The projected input u′.sub.i,j values are fed to a simplex finder 208, which returns the appropriate subset of primaries {P.sub.ks}, to a processor 210, which also received the projected input u′.sub.i,j values, and converts them to barycentric coordinates of the tetrahedron (or other simplex) defined by the subset of primaries {P.sub.ks}. Although it might appear that the subset of primaries {P.sub.ks} should be based on those assigned to the input pixel color x.sub.i,j, this will not work; the subset of primaries must be based upon the projected input u′.sub.i,j values. The output λ of processor 210 is supplied to a quantizer 212, the function of which is very different from that of the quantizer 108 shown in FIG. 1. Instead of performing conventional error diffusion, the quantizer 212 chooses the primary associated with the largest barycentric coordinate. This is equivalent to a barycentric thresholding with the threshold (⅓, ⅓, ⅓)(see the aforementioned Arad et al. document), which is not equivalent to the minimum distance determination carried out by quantizer 108 in FIG. 1. The output y.sub.i,j from quantizer 212 is then sent to the device controller in the usual manner, or stored.

(8) The output y.sub.i,j values, and either the modified input values u.sub.i,j or the projected input values u′.sub.i,j (as indicated by the broken lines in FIG. 2), are supplied to a processor 214, which calculates error values e.sub.i,j by:
e.sub.i,j=u′.sub.i,j−y.sub.i,j or
e.sub.i,j=u.sub.i,j−y.sub.i,j
(depending upon which set of input values are being used) and passes this error signal on to the error filter 106 in the same way as described above with reference to FIG. 1.

(9) In theory, it would appear that the error values e.sub.i,j should be calculated using the original modified input values u.sub.i,j rather than the projected input values u′.sub.i,j, since it is the former which accurately represents the difference between the desired and actual colors of the pixel; in effect, using the latter values “throws away” the error introduced by the projection step. Empirically, it has been found that which set of input values is used does not have a major effect on the accuracy of the color representation. Furthermore, in deciding whether to use the input values before or after the projection in the error calculation, it is necessary to take account of the type of projection effected by the gamut projector 206. Some types of projection, for example projection along lines of constant hue and lightness, provide a continuous and fixed extension of the quantizer domain boundaries to the out-of-gamut volume, and thus permit the use of the unprojected input values in the error calculation without risk of instability in the output values. Other types of projection do not provide both a continuous and fixed extension of the quantizer domain boundaries; for example, projection towards the input color until the gamut boundary is reached fails to provide a fixed extension of the quantizer domain boundaries but instead the quantizer domains change with input values, and in these cases the projected input values should be used to determine the error value, since using the unprojected values could result in an unstable method in which error values could increase without limit.

(10) From the foregoing, it will be seen that the present invention can provide improved color in limited palette displays with fewer artifacts than are obtained using conventional error diffusion techniques. The present invention may be used in display systems capable of displaying a continuum of colors (or at least a very large number of colors) but in which the available primaries are not evenly spread throughout the color gamut; for example interference based displays which control a gap width can display a large number of colors at each pixel, but with a pre-determined structure among the primaries, which lie on a one-dimensional manifold. The present invention may also be used with electrochromic displays.

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

(12) It will be apparent to those skilled in the art that numerous changes and modifications can be made in the specific embodiments of the invention described above without departing from the scope of the invention. Accordingly, the whole of the foregoing description is to be interpreted in an illustrative and not in a limitative sense.