Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2002-05-24
2004-08-24
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S601000, C345S604000, C345S606000, C345S589000, C345S597000
Reexamination Certificate
active
06781596
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods and apparatus for converting color values. More particularly, this invention relates to methods and apparatus for converting color values using a color lookup table as may be used in a print output device, such as a copier, printer, facsimile, or other suitable device.
BACKGROUND OF THE INVENTION
A color image often is composed of an array of pixels, with each pixel including multiple color components. For example, in a three-color system, an electronic scanner may be used to separate a color image into red, green and blue (“RGB”) color components, with each color component represented numerically. Thus, in an 8-bit, three color system, each pixel may be represented by three color values, with each color value being a number in the range between 0 and 255. For example, the color values of a pixel in an 8-bit RGB system may be expressed as (20, 88, 201), where the numbers 20, 77 and 201 represent the values of the read, green and blue components, respectively, for that pixel.
Color output devices, such as color printers, typically produce output images using cyan, magenta, yellow, and sometimes black colorants. Accordingly, color output devices typically represent imagesusing cyan, magenta and yellow (“CMY”) color components (i.e., a three color system), or cyan, magenta, yellow and black (“CMYK”) color components (i.e., a four-color system). To reproduce a color image on a color output device, therefore, the image data typically must be converted from one color component system (e.g., RGB) to another system (e.g., CMY). In particular, the input color values of each pixel must be converted to respective output color values to accurately reproduce the image on a print medium. For example, an input pixel having RGB values of (20, 77, 201) may correspond to an output pixel having CMY values of (100, 82, 0).
More generally, it is often desirable to convert color values from a first color system to a second color system. One known method for converting color values uses a lookup table that provides a corresponding set of second color values for each set of first color values. In an 8-bit system, each first color component may have any value between 0 and 255. Thus, in a three-color system, each pixel may be represented by any one of over 16 million different combinations of first color values (256
3
=16,777,216). Due to memory constraints, however, it is impractical for each of the possible combinations of first color values to be listed in the lookup table. Instead, a “sparse” lookup table is created that includes regularly spaced or intermittent combinations of first color values. For example, if a three-dimensional lookup table includes only thirty-three entries per dimension the lookup table will have 35,937 entries (33
3
), which may be practically implemented in computer memory.
Referring to
FIG. 1
, each component of the first color value, for example, red, green or blue, can be visualized as corresponding to a respective axis in three dimensional space
10
. A sparse lookup table can be visualized as including multiple points within three dimensional space
10
. For example, point
20
may correspond to first color value (192, 168, 232), point
22
may correspond to first color value (200, 168, 232), point
24
may correspond to first color value (200, 168, 224), point
26
may correspond to first color value (192, 168, 224), point
28
may correspond to first color value (192, 160, 224), point
30
may correspond to first color value (192, 160, 232), point
32
may correspond to first color value (200, 160, 232) and point
34
may correspond to first color value (200, 160, 224).
For each point in the lookup table, there is also an associated second color value. Thus, point
20
may correspond to second color value (28, 36, 0), point
22
may correspond to second color value (25, 38, 0), point
24
may correspond to second color value (24, 37, 0), point
26
may correspond to second color value (27, 36, 0), point
28
may correspond to second color value (28, 41, 0), point
30
may correspond to second color value (29, 42, 0), point
32
may correspond to second color value (27, 42, 0) and point
34
may correspond to second color value (25, 42, 0).
Because a sparse lookup table includes only a subset of all possible first color combinations, many first color values will map to a point within this three dimensional space that does not correspond to one of the lookup table entries. For example, point
36
in
FIG. 1
depicts a first color value that does not correspond to any entry in the lookup table. Instead, point
36
is surrounded by the eight entries corresponding to points
20
,
22
,
24
,
26
,
28
,
30
,
32
and
34
.
One conventional technique for assigning second color values to the set of first color values represented by point
36
is to interpolate between the known second color values associated with the surrounding lookup table entries. More particularly, interpolation is performed between the second color values that correspond to some or all of the eight first color values that define the surrounding cube. Examples of such commonly known interpolation techniques are trilinear (e.g., as described in Kasson et al. U.S. Pat. No. 5,390,035), tetrahedral (e.g., as described in Sakamoto et al. U.S. Pat. No. 4,275,413), cubic (e.g., as described in Murakami et al. U.S. Pat. No. 5,930,388 (“Murakami”)), prism (e.g., as described in Murakami), and other suitable interpolation techniques.
One problem with previously known interpolation techniques occurs when one of the second color values saturates at the low end (e.g., output value of 0) or high end (e.g., output value of 255) of the color value scale. An example of this “saturation error” is depicted in
FIG. 2
, which shows an array corresponding to a portion of a single dimension of the lookup table of FIG.
1
. In particular,
FIG. 2
illustrates an array having first color values at points
40
,
42
,
44
,
46
and
48
. In general, each point in the lookup table is associated with multiple second color components (e.g., three second color components such as in a CMY color space). For simplicity, only a single second color value is shown associated with each point in FIG.
2
. Thus, points
40
,
42
,
44
,
46
and
48
have associated second color values
25
,
15
,
5
,
0
and
0
, respectively.
Point
50
depicts a first color value that does not correspond to any entry in the lookup table, but instead is located halfway between points
44
and
46
. Conventional linear interpolation techniques produce a second color value of ((5+0)÷2)=2.5 associated with point
50
. However, this result is incorrect. In particular, assuming that the distance between second color components associated with points
42
and
44
(15−5=10 units) equals the distance between second color components associated with points
44
and
46
, and assuming linearity in this region, the second color component associated with point
46
should have a value of −5. Because color component values are typically represented as unsigned numbers, however, the −5 value typically is clipped to 0. If the second color component value of point
46
were not so clipped, however, linear interpolation would produce a correct value of ((5+(−5))÷2)=0 for the second color component associated with point
50
.
Although not shown in
FIG. 2
, the same saturation problem occurs at the other end of the color value scale. In particular, conventional linear interpolation techniques produce erroneous values when a second color component saturates at the high end of the color scale (e.g., 255 for an 8-bit color system). One consequence of the saturation-value interpolation error is that color components that should have 0 values actually contain non-zero values, and therefore look “dirty.” This effect is most apparent with a light color component (e.g., light yellow) because any contamination of the color components is r
Bella Matthew C.
Electronics for Imaging, Inc.
Rahmjoo Mike
Trosino James
LandOfFree
Methods and apparatus for converting color values does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for converting color values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for converting color values will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3330003