GB2318943A - Image colour conversion - Google Patents

Abstract

The method transforms image points in an input colour space to image points in an output colour space using a first set of control points (P0 - P7) arranged at the corners of cubes in the input colour space and a second set of control points (P8) in input colour space which are within the cubes, each control point having a corresponding value in output colour space, and interpolating between the output values according to the control points. Preferably the first set of control points comprises a cube lattice of 9x9x9 points and the second set comprises a further 512 points at the centre of respective cubes. The second set provides a separate 8x8x8 lattice of control points and they are stored in a separate table. The second set of points significantly improves the accuracy of colour conversion without unduly increasing the memory required for storing control points.

Description

2318943 METHOD FOR COLOR IMAGE CONVERSION RELATED CASE INFORMATION This

application is a continuation-in-part of my co-pending application number 08/399,241 filed March 1, 1995 and 081504,406 filed July 20, 1995, both entitled Method For Multi-Variable Digital Data Storage and Interpolation, both of which are incorporated herein by this reference.

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates generally to color image processing, and more particularly, to a method for converting an image from an input color space (such as for a color CRT monitor) to an output color space (such as for a color printer).

is Statement of the Art

All color sensations we experience with our eyes can theoretically be represented by three color vectors in a three-dimensional space, which may be referred to as a tristimulus space or a color space. The fundamentals of such three-dimensional constructs are discussed in the literature, such as Principles ofColor Technology, by Billmeyer and Saltzman, published by John Wiley & Sons, Inc., NY, copyright 1981 (2d. ed.) and Color Science: Concepts and Methods, Quantitative Data and Formulae, by Wyszecki and Stiles, published by John Wiley & Sons, Inc., copyright 1982 (2d ed.), particularly pages 119 - 130.

A variety of trichromatic model systems have been developed, including the red, green, blue (RGB) model; the cyan, magenta, yellow (and black) (CMY(K)) model; the hue, saturation, value (HSV) model; the hue, lightriess, saturation (HLS) model; the luminance, red-green scale, yellow-blue scale (Lab) model; and the YIQ model used in commercial color television broadcasting; and others. Such works as Fundamentals ofInteractive Computer Graphics, by Foley and Van Dam, Addison-Wesley Pdblishing Company, particularly pages 606 - 62 1, describe a variety of tri-variable color models.

1 Color input and output devices, such a scanners, cathode ray tube (CRI) video monitors, and printers, present color images in a device-dependentfashion. For example, CRT guns are driven by RGB values (voltage levels or other input signal functions, referred to hereinafter as data triplets) that are stored in a frame buffer. The color produced by a CRT on a pixel of its screen for a given RGB triplet of values is unique to each particular model of video monitor device. The same RGB triplet may produce a very different color or hue when displayed on a different model CRT and still a different color on a print medium (such as paper) printed with a color printer.

Color transformation (also referred to in the art as color correction and cross rendering) between model systems in digital data processing presents many problems. The transformation of data from one device to another device is difficult because the color matching relationship between those systems are generally non-linear. Therefore, a crucial problem is the maintaining of color integrity between an original image from an input device (such as a color scanner, CRT monitor, digital camera, computer software/firinware is generation. and the like) and a translated copy at an output device (such as a color laser printer. color inkJet printer. and the like).

As discussed in the reference materials cited above, colors can be constructed as renderings of the additive primary colors, red, green, and blue (RGB), or of the subtractive primary colors, cyan. magenta. yellow and black (CMYK). A transformation may require going from an RGB color space, for example, a computer video monitor, to a CWK color space. for example, a color ink-jet printer. A transformation from one color space to another requires complex, non-linear computations in multiple dimensions. The use of very large look-up tables, e.g. 50 megabytes, containing data.to approximate a transformation is generally used to go from an RGB system to a CWK system to correlate a wide spectrum of color hues. (Note: To maintain black color purity in CWK printing, a separate black ink or toner is usually provided rather than printing all three cyan, magenta and yellow colors as a composite black; the use of such a separate black rendition mechanism is assumed for the purpose of disclosing the present invention.) A lookup table of input versus output data can be generated for any set of devices. There are a variety of methods for building a device-dependent look-up table fora particular device. U.S. PatentNo.

3,893. 166 (Pugsley) provides an example. However, memory is relatively expensive in the 2 current market, especially in view of the low-cost nature of many of the current color printers.

Therefore, there is a need for a process that transforms the color values from one particular device color space into the color space of another device in a fast, economical manner.

Bytes of data correlated in three dimensions can be represented as a cubic lattice construct with each corner of a cube representing a data point. The total look-up table is made of many such cubes as shown in Fig. 1 for an RGB, or other model, color space construct. However, to store atypical printer color transformation data point value for every monitor RGB value in a look-up table would require about fifty megabytes of memory, which is cost prohibitive in the state-of-the-art. Thus, it is economical to store only a limited number of data points and to use interpolation methods to derive intermediate data points within the lattice.

Transforming CRT video monitor RGB triplets into printer RGB (or CMY, or is CMYK) values can be accomplished by utilizing color measurement tools and device indepedenicolor spaces. Device-independentcolor provides accurate color matching based on an absolute color standard, such as that developed by the Commission Internationale LEclairage (CIE), referred to as the CIE Lab color space.

A device-independentcolor space provides a way for describing the appearance of a color without referring to the mechanism that produced the color. First, a flinction is constructed that transforms RGB data points from the color space of a monitor (that is, the table of input-output correlations) into a device-independentcolor space, e.g., the CIE Lab color space. Second, a function is constructed that transforms color data points from the device-independentcolor space, the CIE Lab color space, into the color space of a particular printer. Using these two functions, the monitor RGB data values can be transformed to Lab data triplets, and the Lab data triplets transformed into the printer data triplets, thus providing printer output that matches the original output as viewed on the CRT monitor.

However, in addition to the data storage and access problems referred to above, the mapping of the monitor RGB values into printer RGB values is time intensive to perform on each and every colored pixel in an image before completely printing that image. Therefore, it is economical to pre-compute and store the printer output RGB values for a subset of 3 monitor input RGB values and then to use a fast interpolation algorithm to approximate the transform function for intermediate RGB values, namely those that have not been pre computed and stored Note that even though the printer typically prints in subtractive CMY(K) colors, the output printer color space is in RGB. It has been found to be algorithmically easier to first transform the input monitor RGB color space into a printer RGB color space, and then convert the output RGB values into the subtractive CMY(K) color space.

After the output RGB color space values are obtained, they are "halftonecr' to produce CMY(K) "binary" values that the printer can use. Halfioning is required because color printers are typically binary devices. In other words, for each pixel they can only print at two levels -- they either print a dot or do not print a dot at that pixel. On the other hand, the output RGB values typically have 256 potential levels for each pixel. Halfto g algorithms print binary dots in a dithered fashion to give the appearance of a continuous tone image. The need to halftone the image is one of the causes of graininess sometimes is associated with dot printers.

In making the transform from one tristimulus system to another, trilinear or quadri linear interpolation methods as would be known to a person skilled in the art have beenused. One purported device for an algorithmic interpolation solution using the Lab model is described briefly in Electronic Engineering Times, November 9, 1992, page 35, High-speedprocessor transforms colors, by Junko Yoshida. However, Yoshidas "new algorithm" itself is not disclosed. A commonality of such interpolator solutions is that they must access data for the three or more variables simultaneously, namely, in parallel, in order to obtain the fastest speed, requiring either redundant data tables or complex storage access mechanisms. Moreover, such interpolation methods require multiplication and division operations that require complex and expensive hardware.

In my previous patent application, Serial No. 08/504,406 filed July 20, 1995 entitled Method For Multi-Variable Digital Data Storage and Interpolation, I disclose a color interpolation cube having 729 (9x9x9) control points for each axis in the input color space. These control points are stored in a table, and then for any given point in the input color cube, the resulting output values are derived by a fast interpolating method. For reasons discussed below, this number of control points is derived from the formula (2m + 1)n, where n is the number of axes (typically three) in the input color space and the variable 4 m determines the number of control points along each axis. The number 729 results from choosing m=3.

However, if m is increased by one (m=4), the number of control points increases to 4913 (17 x 17 x 17). This number of control points increases the amount of color accuracy of the color conversion, but also unfortunately also requires about 7 times the memory storage. In the current market of low-cost printers, the extra cost of memory storage is a substantial disadvantage. There is a need for a color image conversion method that allows for an increase in the accuracy of the color conversion without unduly increasing the memory required for storage of the control points.

SUMMARY OF THE INVENTION

The invention provides a method of transforming a set of image points from an input color space to an output color space. A first set of control points is provided in the input color space, the first set of control points being arranged at the corners of cubes in the first is color space. A second set of control points is also provided in the first color space, the second set o f control points being positioned inside the cubes. Both the first and second set of control points have a corresponding set of output values in the output color space. Output values in the output color space for the image points are interpolated based on the first and second set of control points.

In a preferred embodiment, the second set of control points are positioned at the centers of the cubes- The input color space is preferably an RGB color space for presentation on a computer monitor, and the output color space is pref6rably a printer color space. In this case, the output values are preferably converted to a color space involving at least the colors CMY.

In a preferred embodiment, the interpolating step includes the step of subdividing the cubes into a first level of subcubes, the corner points for the first level of subcubes being interpolated from the first and second set of control points. This method preferably further comprises the step of subdividing each subcube of the first level of subcubes into a second level of subcubes, the corner points of the second level of subcubes being interpolated from the corner points of the first level of subcubes. In a highly preferred embodiment, the method further comprises the steps of continuing to subdivide the subcubes into further levels of subcubes until a predetermined final level of subcubes have been achieved, and providing output values for the image points based the corner points of the subcube, of the final level, in which the image points reside. The output values for the image points may be taken as the output values for one of the corner points of the subcube, of the final level, in which the image points reside.

The invention provides a color image conversion method providing an increase in the accuracy of the color conversion without unduly increasing the memory required for storage of the control points.

DESCRIPTION OF THE DRAWINGS

Fig. 1 is a spatial representation of a generic lattice memory organization construct in accordance with the present invention.

Fig. 2 is an extracted "data cube" from the lattice memory organization construct of data as shown in Fig. 1.

Fig. 3 is a depiction of a first level subdivision into octant spatial regions of the is extracted data cube as shown in Fig. 2.

Fig. 4 is a depiction of a second level subdivision of the spatial regions of the extracted data cube as shown in Fig. 3.

Fig. 5 is a depiction of intermediate data points used for the subdivision steps as shown in Figs. 3 and 4.

Fig. 6 is a flow chart of an interpolation method using 9x9x9 control points.

Fig. 7 is the extracted "data cub6" of Fig. 2 with an extra control point p8 in the center of the cube.

Fig. 8 is a flow chart of an interpolation method using both the 9x9x9 and 8x8x8 control points.

The drawings referred to in this description should be understood as not being drawn to scale except if specifically noted.

DETAILED DESCRIPTION OF THE ILLUSTRATED EMBODIMENT

Reference is made now in detail to a specific embodiment of the present invention, which illustrates the best mode presently contemplated by the inventor(s) for practicing the invention. Alternative embodiments are also briefly described as applicable. V;hile the invention is described in terms of transforming a first exemplary RGB space (CRT monitor) 6 to a second exemplary RGB space (printer), it is not intend as a limitation on the scope of theinvention. The general method and apparatus disclosed herein is expandable for interpolation of any type of non-linear data that can be represented as a multidimensional construct.

As mentioned above, a solution to the color space transformation problem is to pre compute the printer output RGB values for a subset of monitor input RGB values and then to use a fast interpolation algorithm to approximate the transform function for intermediate RGB values, that is, those that have not been pre-computed and stored. The present invention uses a data storage and numerical subdivision technique not requiring complex multiplier and divider circuitry to provide a fast and accurate method for interpolating the pre-computed color transform function.

If an NkNxN color table is used, indexed from 0 to N- 1 on each side, and ROB values vary from 0 to 255, the indexes of the eight data points that must be read and interpolated from the table are:

is (R (M) / 255), (G (N-1) 1255), (B (M) 1255) (R (N- 1) / 255), (G (N- 1) / 255), (B (N- 1) / 255) +1 (R (M) 1255), (G (M) 1255)+1, (B (N-1) / 255) (R (NA) / 255), (G (M) / 255)+1, (B (N-1) / 255)+1 (R (M) / 255)+l, (0 (M) 1255)+1, (B (M) 1255) (R (N- 1) / 255), (G (N- 1) / 255), (B (N- 1) / 255)+1 (R (M) 1255)+1, (G (M) / 255)+1, (B (M) / 255) (R (N- 1) / 255)+ 1, (G (N- 1) 1255)+1, (B (N- 1) 1255)+1 Unfortunately, multiples and divides are slow for real-time processing. What has generally been done to quickly compute the table locations that must be looked up for interpolation is to restrict the table size to 2' + 1 steps in each dimension, which leads to color maps that are, for example, 9x9x9or 17x17x17in size. With this restriction, the table can be indexed by just looking at a set of the most significant bits from the input RGB, and applying some simple addition. For the above example, with a table of size (2m - 1, which results in a 9x9x9 table, the above computations become:

7 (R >> (8-m)), (G >> (8-m)), (B >> (8-m)) (R >> (8-m)), (G >> (8-m)), (B >> (8-m)) + 1 (R >> (8-m)), (G >> (8-m)) + 1, (B >> (8-m)) (R >> (8-m)), (G >> (8-m)) + 1, (B >> (8-m)) + 1 (R >> (8-m)) + 1, (G >> (8-m)), (B >> (8-m)) (R >> (8-m)) + 1, (G >> (8-m)), (B >> (8-m)) + 1 (R >> (8-m)) + 1, (G >> (8-m)) + 1, (B >> (8-m)) (R >> (8-m)) + 1, (G >> (8-m)) + 1, (B >> (8-m)) + 1 where >> is a bitwise rightshift operator.

Fig. 1 represents a continuum of color data formulated as a lattice construct for color data in which three axes, X-axis for Green, Y-axis for Red, and Z-axis for Blue, define the data points in a tristimulus space. Each corner of each cube in the lattice represents a stored data point. It is common practice to use eight bit (one byte) digital data values. Therefore, is in the implementation of the present invention, an exemplary CRT monitor to printer RGB transform, data points are pre-computed for 729 (derived from (2 3 + 1) RGB values, equally spaced over the color space of the monitor., that is, data across the spec is stored in nine equal steps -- 0 to 8 - in each of the CRT Red, Green and Blue axes. Note that the methodology of the present invention works for any (2m + 1 r data set, where (2m + 1) is the density of data points stored, that is, the number of samples per dimension in the specific implementation, and i n" is the number of variables in the first data construct.

In the exemplary case of a tristimulus color space. a tri-variable data set, n = 3. Inthis implementation m = 3, Which gives nine data gradations per dimensional axis. Thus, a total of 729 data points are provided.

These data points form the three dimensional lattice as shown in Fig. 1. Generally, the data base of this construct comprises a predetermined number of output data values for driving output devices (such as an ink-jet pen controller) correlated to given input data values for that specific output apparatus.

In Fig. 2, a cube is extracted from the lattice. In accordance with the present invention, a standard is established in which the lower left back (LLB) corner, pO, represents 8 the minimum RGB values for that specific color space and the upper right front (URF) corner, p7, represents the maximum RGB values for that specific color space. In another annotation, it may be represented as:

pO Rminy Gminy B.j. and p7 -- Rmax, Gm&x, Bmax.

For a pixel to be printed, an RGB input value is received (see also, Fig. 6. step 601). For any specific pixel to be printed by a device capable of generating millions of color variations, it is highly probable that the color to be printed lies within the boundaries of a cube of eight of the stored 729 RGB values; i.e., it is not one of the specific hues stored, but lies within one of those stored memory cubic constructs.

The upper three bits of each of the eight bit RGB values are used to index into the color map data construct lattice to extract the eight data points that surround the RGB value to be derived by interpolation (Fig. 6, step 603).

For example, assume the input values to the lattice are:

(1) R = 00 10 1100 (=44) is G= 10100101 (=165),and B = 0 11110 11 (= 123).

The upper three bits of each of these values are (2) R= 001 (=1) G= 101 (=5) B= 011 (=3), and used to obtain (or may be understood to be 1ndexed to") a particular cube of the entire lattice, namely the cube of Fig. 2, extracted from Fig. 1, in which LLB data point pO would be "up" one from the origin on the Red axis, "left" five from the origin on the Green axis, and "ouC three from the origin on the Blue axis. In essence, the upper three bits provide the "address" in the lattice to obtain eight data points that surround the desired value; the desired output RGB value is guaranteed to be contained within the cube described by these eight data points, pO through pT If the input is indexed is one of the stored data points that data point is output (Fig. 6, step 605).

Also, a rough approximation for a transform could be produced by using one of these eight points, or an average of these points -- the "center" of the extracted cube -- as the output value. This would produce a mapping that, in this example of 729 store values, 9 provides 1241 possible output values - each corner plus each center. However, this approximation is still not adequate for most applications.

Repetitive subdivisicn - importantly requiring no complex mathematical computations and associated hardware -- is used to provide a means for computing a more accurate result in accordance with the method.of the present invention.

Turning to Fig. 3, a mapping of bit triplets to octants subcubes of the original cube of Fig. 2 is demonstrated. In other words, the LLF octant subcube, bits 0, 0, 1, is displaced "0" in the Red axis, @pop in the Green axis, and "I " in the Blue axis. All eight octant subcube "addresses" are similarly derived (Fig. 6, step 607).

The five lower order bits of the RGB values given in (1) above are now used to control the subdivision of the cube formed by the eight data points extracted using the upper three bits in (2) in Fig. 2 to interpolate the sought after transformation color (Fig. 6, step 609). That is. the bits that guide the subdivision routine are:

(3) R=01100 is G=00101.and B=11011.

The highest order bit from each of the five bits of each color axis of each data triplet dictates the first subdivision:

(4) R=0 G 0, and B 1.

Given these three bits. eight new data points are computed from the original data points by subdivision. These data points are, again for the purpose of this example, the corners of the LLF octant subcube, denoted:

(5) sO = (p 1 -pO)/2 51 =PI s2 = (p3-pO)/2 s3 = (p3-pl)/2 0 = (p5-pO)/2 s5 = (p5-pl)/2 s6 = (p7-pO)/2 center of data cube of Fig. 3) s7 = (p7-p 1)12, as shown in Fig. 4.

The intermediate points between corners of a cube that are computed to allow subdivision may be computed many different ways, simulating a number of interpolation methods. For example, as shown in Fig. 5, data values for the intermediate points shown as iO... i 18 can be computed to simulate tetrahedral interpolationas shown in TABLE 1. Such simple algorithms can be provided for trilinear or other interpolation method as would be known in the art as desired.

TABLE 1 i O=(pO+p 1)/2 i 1 =(pO+p2)/2 i2=(p 1 +p3)/2 B=(p2+p3)/2 i4-(pO+p3Y2 3=(pO+p4)12 i6=(p 1 +p5)/2 i7=(p4+p5)/2 i8=(pO+pS)/2 i9=(p2+p6)12 i10=(p4+p6)/2 i 11 =(pO+p6)/2 i 12=(p 1 +p3)/2 i 13=(p2+p3)/2 i 14=(pG+pJ3)/2 i 15=(p5+p7)/2 i16=(pl+p7)/2 i 1 7=(p4+p7)/2 i 1 8=(pO+p7)12 In practice. by using such simulations, division by 2 is simply a binary right shit so expensive division operational hardware is not needed. Also, all of the intermediate points is do not need to be computed with each subdivision; only seven points since one is always redundant (see s 1 above) and only the data points of the next octant as determined to contain the data point of interest as determined from the next significant bits of the string used.

In effect, these eight new data points, sO through s7, define an octant of the original cube and the desired output value is within the octant subcube. We have reached a level of accuracy where 4096 output values are mapped to the input values if the "cente?' or average value of the eight new data points is provided as the transform result. More accurate interpolation requires further subdivision.

For a second subdivision, the second bit from each of the five bit strings shown in (3)) above are used:

(6) R 1 G 0, and B= 1.

As shown again in Fig. 4, in the same manner that the original cube pO p7 was subdivided, this results in a second subdivision octant cube of the first subdivision octant subcube sO - sT Again, the sought after output data point is in a cube where the desired output RGB output color value is contained. As the eight newly derived data points are relatively closer in value, the new cube in which the data point is guaranteed to be contained is yet a closer interpolation of the desired output value than was the first subcube, points sO through sT The process is continued with the third bit, then the fourth bit, then the fifth bit, resulting in three more subdivisions (five total) from the eight bit string of the original RGB triplet (Fig. 6, step 611 et seq.). Thus, after five such subdivisions, an interpolated set of 16,777,216 output values, each corresponding to an output RGB value has been mapped from the original 729 stored value set. In this example, the fifth subdivision is the final level of subdivision. Either one of the "smallest" (fifth subdivision) subcube corner values or some average of these eight converged data points is returned as the correct output, RGW (Fig. 6, step 619) for the given input function.

Note also, the method of the present invention allows a trade of speed for accuracy on a per-image basis. Fewer subdivisions require less data processing time. For example, selecting to use fewer subdivisions provide a valid, although less accurate, color space mapping, but may be perfectly adequate for a business graphic, such as a simple bar chart.

A computer artist, less interested in speed than reproduction quality would use all five subdivision iterations. This feature also could be utilized in real-time and time-critical applications adaptively to convert large images with less accuracy than small images. Fast image preview and draft image printing can be made faster by sacrificing some accuracy.

Furthermore. the level of subdivision can also vary within a particular set of color data. More subdivision can be provided in the parts of the color map where high accuracy is needed and less where it is not. For example, there are subtle color changes at the near neutral axis more than in very saturated colors; therefore, saturated color areas do not need to be computed as accurately. This would provide optimal solutions to the accuracy versus throughput trade. To implement this, one would pre-compute the level of subdivision needed in each "cube" of the color map based on perceptual metrics and store that value along with the color data. During the real-time execution, the level of subdivision would be guided with this data.

12 A problem with this disclosed interpolation method is that, because of the (2m + 1 table size, in order to increase the accuracy of the color data, the number of control points along each axis of the color cube must be almost doubled. For example, if a 9x9x9 color map is not accurate enough, a 17x 1 7x 17 color map must be used, which requires almost seven times the memory storage. Going from a 9x9x9 to a 11 x 11 x 11 map, for example is not practical because computing table locations based on RGB becomes expensive.

Fig. 7 illustrates a cube similar to the cube shown in Fig. 2, except that it has an additional control point pS exactly in the center of the cube. Each of the 512 cubes in the lattice described in reference to Fig. 1 has such a center control point p& Note that this midpoint p8 is the same as interpolated point s6 shown in Fig. 4. In the earlier described algorithm, the values for s6 were interpolated using the fast interpolating algorithm.

However, with this improved method, these center points pg are established control points that are stored in memory in a separate table of the size 2m.

The memory storage format for these center points is essentially a lattice within a is lattice. In addition to looking up the 8 corner points for interpolation, as described above, the midpoint p8 is also looked up. The additional look-up to find the midpoint is simply:

midpoint = (R >> (8-m)), (G >> (8-m)), (B >> (8-m)) indexed into the midpoint table.

This interpolation method gains an additional control point in each of the cubes exemplified in Fig. 2, resulting in additional color accuracy. Yet this additional accuracy is achieved by adding only an additional 5 12 (WA) data points, which added to the existing 729 (9x9x9) results in a total of 1241 total data points. This is significantly less than 4913 datapoints that would exist in a 17x 1 7x 17 lattice, which would result from indexing m from 3 to 4 in the formula (2m + If with n--3.

Fig. 8 illustrates a flow chart similar to that of Fig. 6, except that it discloses a method utilizing both the 9x9x9 control points at the corners of the cubes and the additional 8x8A control points at the centers of the cubes as shown in Fig. 7. In this algorithm, in step 803, the method reads both the 8 cube corners (from the 9x9x9 table) and the center (from the 8x8x8 table) for the appropriate cube based on the high order bits. In step 805, the 13 method asks if the image point in question is actually on one of the 9 control points in question (i.e., is it one of points pO through p8 of Fig. 7).

At step 809, if the algorithm is on the first subdivision into subcubes, then the algorithm takes a center point pg from the gxgxg table for the appropriate subcube corner point. After the first subdivision into subcubes, no further control points need to be taken from the UW table. At step 809, no interpolation is needed to derive existing corner points (either previously taken from tables or previously interpolated).

Even though this 9x9x9 + 8xW system has far fewer control points than a 17x 1 7x 17 table, it nevertheless has the same color resolution along the important "gray" axis (the axis in the color cube going from white to black). Both the 93 + 83 table and the 173 tables have 17 points along the gray axis. Accurate representation of this neutral axis is one of the most important aspects of color reproduction.

In addition, the center of each of the cubes in a lattice representation is the point fbnhest from any of the original 9x9x9 control points. If additional data is to be added to is an existing color table. these midpoints are the optimal location. in terms of the spacing of the device input color space.

Furthermore. when used in conjunction with the interpolation algorithm that is described. this data format does not decrease the throughput (numberof pages printed per minute) of the printer. If the center control points were not provided in a table, the interpolating algorithm would need to compute these points. Retrieving these control points from a table in memory is at least as fast as computing them, if not faster.

Therefore, the disclosed improved method provides increased color accuracy, and yet does not unduly add to the amount of memory needed for the increased color accuracy.

14

Claims (9)

1. I claim: 1. A method (Fig. 8) of transforming a set of image points from

   an input color space (Fig. 1) to an"[ color space, comprising: providing a first set of control points (pOplp2,p3,p4,p5,p6,p7) in said input color space, said first set of control points being arranged at the corners of cubes (Fig. 7) in said input color space; providing a second set of control points (p8) in said input color space, said second set of control points being positioned inside said cubes; each said first and second control points having a corresponding set of output values in said output color space; and interpolating output values for said image points based on said first and second set of control points.
2. 2. A method (Fig. 8) according to claim 1, wherein said second set of control points (p8) are positioned at the centers of said cubes (Fig. 7).
3. 3. A method (Fig. 8) according to any preceding claim, wherein said first color space (Fig. 1) is an RGB color space for presentation on a computer monitor.
4. 4. A method (Fig. 8) according to any preceding claim, wherein said output color space is adapted for printing on a color printer.
5. 5. A method (Fig. 8) according to any preceding claim, wherein said output values are converted to a color space involving at least the colors CMY.
6. 6. A method (Fig. 8) according to any preceding claim, wherein said interpolating step includes the step of subdividing (809) said cubes into a first level of subcubes (809), the corner points for said first level of subcubes being interpolated from said first and second set of control points (pO,p 1,p2,p3,p4,p5,p6,p7,p8).

   1-5
7. 7. A method (Fig. 8) according to any preceding claim, further comprising the step of subdividing (809) each subcube of said first level of subcubes into a second level of subcubes, the corner points of said second level of subcubes being interpolated from the corner points of said first level of subcubes.
8. 8. A method (Fig. 8) according to any preceding claim, flirther comprising the steps of. continuing to subdivide said subcubes into further levels of subcubes until a predetermined final level of subcubes have been achieved; and providing output values for said unage points based on the subcube of said final level in which said image points reside.
9. 9. A method (Fig. 8) according to any preceding claim, wherein said output values for said image points are taken as the output values for one of the corner points of said subcube, of said final level in which said image points reside.

   1(0