Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2000-07-26
2004-10-26
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S596000, C345S592000, C345S600000, C345S601000, C345S610000
Reexamination Certificate
active
06809740
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The present invention relates to data mapping using a sparse lookup table in a manner that approximates linear interpolation. More specifically, the present invention relates to mapping of data by quantizing data samples and accessing a lookup table such that the average of the output data for a neighborhood of samples converges to a result that is comparable with or approximates the result that would have been obtained using linear interpolation.
2. The Prior State of the Art
Printing an image using a computer printer or another image forming system often involves processing color image data by converting the image data from a first color space to a second color space. For example, image data is often stored or received by a computer in a red, green, blue (“RGB”) format, while many computer printers utilize a cyan, magenta, yellow (“CMY”) or cyan, magenta, yellow, black (“CMYK”) format. Such formats are examples of image data that can exist in any number of color spaces. The process of converting color image data from a first color space to a second color space represents but one example of a general mathematical problem of evaluating a multivariable function given specific values of the input variables.
There exist several techniques for converting image data from a first color space to a second color space. In practice, image data typically includes a plurality of samples, each being represented by multiple values associated with the different color components in a color space. For example, each sample of RGB data includes a red component, a green component, and a blue component. One approach for converting such RGB image data to CMY data uses a set of three equations defining C, M and Y as linear functions of R, G, and B. Assuming the R, G, and B components of the image data are represented by eight bits of data, in which case the intensity of each of the three components has a value between 0 and 255, the linear approach for converting RGB to CMY can be defined as C=255−R; M=255−G; Y=255−B. This approach is relatively computationally efficient, since each sample can be converted by performing only three calculations, none of which is a division operation. However, in practice, this direct approach introduces unacceptable errors because the available colorants used in image forming systems do not behave in the linear fashion described in the foregoing equations.
A second technique is to obtain a set of higher order polynomials that define CMY(K) as functions of RGB. This analytic method can reduce errors, since it can more closely approximate the actual behavior of specific colorants that are used in image forming systems. However, as the analytic polynomials are taken to higher orders, the number of calculations per sample increases. Moreover, any set of higher order polynomials are adapted only to a specific set of colorants, and any change in the colorants and the associated color conversion functions would require a new set of polynomials.
FIG. 1
graphically illustrates the technique for directly calculating the value of a function, f(x), based on the known value of x. Conceptually,
FIG. 1
represents the conversion method that uses a set of higher order polynomials to convert image data from a first color space to a second color space, although
FIG. 1
illustrates the problem in only one dimension, whereas RGB to CMY(K) conversion requires a three-dimensional solution. In
FIG. 1
, the known value of x can be used to directly calculate the value of f(x) (shown at
10
) to any desired degree of accuracy that is limited only by the degree of the polynomial function and by the computing resources dedicated to the process.
The two foregoing techniques for converting image data from a first color space to a second color space involve direct calculation of values in the second color space using functions that are defined with any desire degree of accuracy. Other methods for converting image data from first color space to a second color space involve lookup tables in which the values of CMY(K) as a function of RGB are pre-calculated and stored for use during the conversion process. The lookup table eliminates direct calculation of the color values at runtime, but requires memory to be accessed for each sample. A lookup table used for converting RGB to CMY(K) can be described as having three dimensions, that when fully populated, has 16,777,216 entries (e.g., 256×256×256), assuming eight bit values for each of the RGB components of the image data, which also corresponds to the number of colors that can be defined by such image data. As can be readily understood, a fully populated lookup table can require a prohibitive amount of memory. Although a fully populated lookup table can yield results having any desired degree of accuracy, the memory and computational requirements make them impractical in most image forming systems.
These memory and computational requirements can be reduced using a sparsely populated lookup table that includes entries for fewer than all of the possible combinations of RGB values. Empirically, it has been found that the curvature of the color conversion functions can be adequately approximated by using a lookup table having 17 lattice points for each color dimension. This technique requires a lookup table having fewer than 5,000 entries.
FIG. 2A
illustrates the conversion function of
FIG. 1
having been defined by a series of discrete points
12
that can be used in a lookup table, as opposed to being defined by a continuous curve.
FIG. 2B
conceptually illustrates a sparsely populated lookup table
20
having three dimensions that can be used to convert image data from a first color space (e.g., RGB) to a second color space (e.g., CMY(K)). Only some of the data points
22
defined in lookup table
20
are illustrated in
FIG. 2B
for purposes of clarity. In a fully populated lookup table, each possible sample, represented by eight bit values of R, G, and B would map to a single point in a lookup table, which in turn would correspond to a set of CMY(K) values. In the sparse lookup table
20
, only a relatively small number of values of R, G and B map directly to a lattice points
22
. Those samples that map directly to a lattice point
22
yield the corresponding CMY(K) values associated with the lattice point. The vast majority of RGB values, however, map to a position in the sparsely populated lookup table that does not coincide with a lattice point. In order to evaluate the conversion functions for such samples of image data, a method of approximating the value of the conversion functions is used.
One conventional way of approximating the value of the conversion functions involves truncating specified numbers of bits from the RGB values to obtain index values that map directly to lattice points in the sparsely populated lookup table. For purposes of illustration, the analogous one dimensional truncation technique is illustrated in
FIG. 3
, in which the value of f(x) is to be approximated based on the known value of x. In
FIG. 3
it is assumed that the input data defines x with eight bits of accuracy, while f(x) has been defined at 17 discrete points, each of which corresponds to an entry in a lookup table. Truncation of the eight bit input data by four bits results in quantized input data including the four most significant bits, which can be mapped to one of the lookup table entries as shown by the stairstep pattern
30
a
. Truncation in this matter effectively results in the values of the input data being rounded down to the next entry of the lookup table. For example, input data having a value of 127 (0111 1111) when truncated indexes the same lookup table entry and yields the same output data as an input value of 96 (0111 0000). Accordingly, the samples are quantized, meaning that the same output value is generated for a range of input values.
In an image forming system, such as a computer printer, the result can be a color artif
Bella Matthew C.
Brady John A.
Lexmark International Inc.
Rahmjoo Manucher
LandOfFree
Dithered quantization using neighborhood mask array to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dithered quantization using neighborhood mask array to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dithered quantization using neighborhood mask array to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3324307