Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2000-06-07
2004-08-03
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S601000
Reexamination Certificate
active
06771275
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to data processing systems and more specifically to systems and methods for using look-up tables to convert data from one format to another.
BACKGROUND OF THE INVENTION
Data processing equipment, such as computers, digital scanners, and printers, typically represent images of physical objects through signals or data in predetermined formats. For example, an image of a physical object is often processed for display on a monitor by representing the image as a map of pixels. Each pixel has associated by intensity levels of red (R), green (G), and blue (B) components. For various reasons, such an “RGB” representation of the image works well for displaying images on a computer display monitor. However, other representations may be better suited for use with other types of output devices. For example, color printers commonly use signals in a “CMYK” format, which provides separate intensity values for cyan (C), magenta (M), yellow (Y) and black (K (for “key”)).
Since it is desirable to be able to both display an image on a computer monitor and print the image using the same computer system, schemes have been devised for converting images from one format to another (i.e. color conversion schemes). Color conversion is only one aspect of a more generic problem that is often addressed by data processing equipment: transforming one type of signal or data to another type of signal or data. Transformation is traditionally performed using two techniques, either alone or in combination. The first technique is a computational methodology that uses computational transformations and the second is a lookup table methodology that at least one “look-up table” holding conversion values.
Computational transformations are widely known and are well suited where mathematical relationships can be readily applied to mappings. For example, simple computational operations on a Celsius temperature reading will yield a corresponding Fahrenheit temperature reading (e.g. t
f
=9/5t
c
+32° F.).
Look-up tables are extremely helpful where a discrete set of inputs maps to a discrete set of outputs or where there is no readily processed mathematical relationship that corresponds to the desired mapping. For instance, one might use a look-up table to convert part numbers from one manufacturer to equivalent part numbers from another manufacturer. Through interpolation, lookup tables may also be used to map information that is continuous rather than discrete. The lookup table may specify discrete reference points to which interpolation may be applied to obtain the converted value. For example, conversion of distances from metric to English units can be performed trivially using linear interpolation or extrapolation from a look-up table having only two data points.
Traditionally, in situations where both computational and look-up table approaches are available to accomplish a transformation, there has been a tradeoff in determining which to use. Computationally intense approaches consume relatively more processing resources than approaches based on look-up tables. However, where the mappings involved are not limited to linear relationships, very large amounts of memory are needed for a look-up table to provide accurate and precise transformations over a wide range of inputs. It is common to use look-up tables of more than two dimensions. As might be expected, implementation of such multi-dimensional look-up tables can easily call for large amounts of memory. Accessing a multi-dimensional look-up table traditionally involves accessing a number of entries surrounding an index pointer to obtain point values, and then interpolating such surrounding point values using some form of linear interpolation. For example, tetrahedral interpretation uses four surrounding points, and tri-linear interpretation uses eight surrounding points.
When it is necessary to access a significant number of points that are not sequential or closely adjacent in the space defined by the look-up table's structure, significant computational overhead is incurred. The impact of such multi-dimensional table processing is exacerbated, beyond the generalized interpolation overhead, in systems having a heavily “pipelined” memory architecture. Sometimes, increasing a table size sufficiently to avoid interpolation altogether, or at least permit the use of simple linear interpolation, imposes an unacceptable memory requirement. Look-up table memory requirements grow exponentially with the dimensionality of the table, so doubling the linear size (number of entries) along each of the dimensions of a three-dimensional look-up table increases the memory requirements by a factor of eight.
Image processing applications involve great amounts of data that often need to be processed very quickly. For example, raster-printing methods require image data to be processed quickly enough to have print data for a portion of a page ready when the print head of the print engine reaches the corresponding portion on the paper. Real-time video display requires pixel information to be processed much more quickly. Accordingly, image processing applications have tested the limits of known systems and methods for transformation using computational and look-up table techniques.
SUMMARY OF THE INVENTION
The system and method of the present invention provides additional processing capacity to conventional signal and data processing equipment by using a look-up table that includes both sampled data entries and difference values (also known as “differentials”). The difference values correspond to the rates of change from each table entry and its neighbors in the table.
Also in accordance with the present invention, an interpolated table value is determined using a single sampled data entry and difference values corresponding to that entry.
In one aspect of the invention, the difference values correspond to first-order differences.
In another aspect of the invention, the table maps between RGB values and CMYK values.
In still another aspect of the invention, the contents of a computer-readable medium causes a computer to perform interpolation using a look-up table having sampled data entries and difference values corresponding thereto.
In yet another aspect of the invention, a computer-readable memory device is encoded with a data structure that includes a lookup table with sampled data entries and corresponding difference values, the look-up table configured to provide interpolated output in response to application of selected data entries and difference values to an interpolation engine.
In accordance with an additional aspect of the present invention, a method converts a red, green, blue (RGB) color value into a cyan, magenta, yellow, key (CMYK) color value. In this method the nearest sampled RGB point to the input RGB point is found and the RGB components of the distance from the sampled point to the input point are calculated. The table entry for the sampled RGB point contains a base value for a selected one of the cyan, magenta, yellow or key output as well as difference values for that output primary along each of the RGB input primary axes. An interpolated value is determined for the selected primary using the base value and the summed products of the difference values in the RGB axes and the distance from the input RGB point to the sampled RGB point. The interpolated value becomes the output value for the selected primary in the cyan, magenta, yellow or key value. Each output primary is determined in this manner.
The features and advantages described in the specification are not all-inclusive, and particularly, many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims hereof. Moreover, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter, resort to the clai
Andree Fred W.
Cook Craig C.
Pratt Steven J.
Lahive & Cockfield LLP
Oak Technology, Inc.
Razavi Michael
Yang Ryan
LandOfFree
Processing system and method using a multi-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processing system and method using a multi-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing system and method using a multi-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3287354