Rendering using at least two levels of gray

An indication of any target point internal to a first color space is received. The target point is rendered in a second color space using one of at least two levels of gray colorant and at most two primary colorants out of three primary colorants in the second color space.

RELATED APPLICATIONS

BACKGROUND

Colors are defined by light wavelengths. A particular set of wavelengths of light corresponds to one true color. Representing an image, however, as a collection of light wavelengths is often inconvenient for image processing. Therefore, a variety of systems have been developed to represent images in data formats that are more convenient for storing, displaying, and otherwise manipulating images. Each of these systems can be referred to as a color space. Different devices often use different color spaces. Color space conversion is the process of converting an image from one color space to another.

Color spaces can be quite large. For example, display devices, such as computer monitors, televisions, and projectors, often use mixtures of red (R), green (G), and blue (B) color components, or “primaries.” The color of each pixel displayed on a screen can be defined as some combination of these RGB primaries. If each color in an RGB color space is represented, for example, using 8-bits per primary or “channel”, then each pixel in an image may comprise three bytes of color information. In which case, this 8-bit/channel RGB color space can theoretically display 224, or about 16.77 million, different colors.

Mapping in excess of 16 million data points from one color space to another can be time consuming and resource intensive. Therefore, many color conversion techniques rely on interpolation. To interpolate data points, a certain number of data points are first mapped from one color space to another using any of a number of mathematical or experimental approaches. These data points comprise a set of “control points,” having predetermined values in both color spaces. Then, when a data point is encountered that has not already been mapped, a value for the data point in the second color space can be estimated based on the position of the data point relative to the control points in the first color space.

DETAILED DESCRIPTION

In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the embodiments of the present invention. However, those skilled in the art will understand that the present invention may be practiced without these specific details, that the present invention is not limited to the depicted embodiments, and that the present invention may be practiced in a variety of alternative embodiments. In other instances, well known methods, procedures, components, and circuits have not been described in detail.

Parts of the description will be presented using terminology commonly employed by those skilled in the art to convey the substance of their work to others skilled in the art. Also, parts of the description will be presented in terms of operations performed through the execution of programming instructions. As well understood by those skilled in the art, these operations often take the form of electrical, magnetic, or optical signals capable of being stored, transferred, combined, and otherwise manipulated through, for instance, electrical components.

Various operations will be described as multiple discrete steps performed in turn in a manner that is helpful for understanding the embodiments of the present invention. However, the order of description should not be construed as to imply that these operations are necessarily performed in the order they are presented, nor even order dependent. Lastly, repeated usage of the phrase “in one embodiment” does not necessarily refer to the same embodiment, although it may.

Various embodiments of the present invention provide a technique for color space conversion and interpolation. Embodiments of the present invention use one or more colorant boundaries that define boundary surfaces and/or regions in a first color space to limit certain colorants or sub-colorants in a second color space. As discussed below, embodiments of the present invention can be used for a variety of applications, including 100% gray component replacement (GCR) with multiple levels of gray colorant.

FIG. 1illustrates one embodiment of color correspondences between a red, green, and blue (RGB) color space and a cyan, magenta, and yellow (CMY) color space. Although embodiments of the present invention are described below primarily with respect to color conversions between RGB and various forms of CMY color spaces, the embodiments of the present invention are not limited to the illustrated color conversions and can be used for color conversions between any of a variety of color spaces.

Computer monitors, televisions, and projectors usually generate color using red, green, and blue light, so these display devices often use RGB color spaces. Imaging devices, such as color printers, do not usually generate light, but instead print reflective colorants, such as cyan, magenta, and yellow, so these display devices often use CMY color spaces. An RGB to CMY color conversion is likely to occur each time a color document is printed from a computer.

As shown inFIG. 1, a combination of M and Y, with no C, produces R. Similarly, a combination of Y and C, with no M, produces G. And, a combination of C and M, with no Y, produces B. Using this type of color correspondence, a color space can be created to map RGB to CMY. For a conversion from RGB to CMY, the RGB colorants are often referred to as secondary colorants and the CMY colorants are often referred to as primary colorants.

FIG. 2illustrates one embodiment of a color cube200for mapping RGB and CMY colors. Cube200has an origin210, and three primary axes220,230, and240, one for each of the RGB colors. Axis220is a color transition for R intensity, ranging from zero at the origin210up to a maximum. Axis230similarly corresponds to G intensity, and axis240similarly corresponds to B intensity. The origin210is black (K), where RGB are all zero. Where RGB are all maximum, the color is white (W) at point250.

Cube200similarly includes a coordinate system for the CMY colors inverted over the RGB coordinate system. That is, the W point250is the origin for the CMY colors where CMY are all zero, and the K point210is where CMY are all maximum. The CMY colors have three primary axes,225,235, and245. Axis225is a color transition for C intensity, ranging from a minimum at point250up to a maximum. C intensity is inversely related to R intensity on axis220. Similarly, axis235corresponds to M intensity, and is inversely related to G intensity on axis230. And, axis245corresponds to Y intensity, and is inversely related to B intensity on axis240.

In the ideal situation, there would be a one-to-one, linear correspondence between the two coordinate systems, and converting RGB to CMY would simply be a matter converting a point in the RGB coordinate system to the same point in the CMY coordinate system. In reality, however, converting between RGB and CMY color spaces can be much more complicated due to various factors that make a one-to-one, linear correspondence between the two coordinate systems very unlikely.

The colorants, the print mechanism, and the print medium are all examples of factors that can complicate how an RGB color space maps to a CMY color space. For example, toners, inks, and waxes are often used as colorants in CMY color spaces. Each colorant, or sub-colorant, is usually comprised entirely of one particular color intensity, or shade of color. For the case in which the colorant is a liquid colorant, the density of tiny droplets of the colorant can be changed in order to change the appearance of the color's intensity. That is, each droplet of a colorant may be the same intensity, but depending on how many droplets are deposited in a given area, the colorant appears more or less intense. The high end of the intensity range for a given colorant is often where the print medium becomes saturated with the colorant and the intensity cannot be increased. The low end of the intensity range for a given colorant is often where the droplets are scattered so sparsely so as to be individually distinguishable to the naked eye, potentially making the image look grainy. The intensity ranges of just C, M, and Y colorants alone are often inadequate to fully represent the intensity ranges of RGB colorants.

One way to increase the intensity ranges is to use additional colorants and/or sub-colorants. For instance, a CMYK color space adds a black (K) colorant. In a CMYK color space, K can be used to make darker colors, potentially increasing the intensity range. A CMYKlclm color space adds a cyan sub-colorant, low-dye cyan (lc), and a magenta sub-colorant, low-dye magenta (lm). lc and lm can be used to smooth out the lighter colors, also potentially increasing the intensity range. Various embodiments of the present invention also use a CMYlclmKgGrz color space which adds three sub-colorants of gray, light gray (g), medium gray (Gr), and black (z). K and z may represent two different types of black for different types of images, such as text verses photographs.

As used herein, the word “colorant” refers to a particular general color, such as red (R), green (G), blue (B), cyan (C), magenta (M), yellow (Y), black (K), and gray. Colorants can include various sub-colorants, such as dark cyan (C) and light cyan (lc) for cyan, dark magenta (M) and light magenta (lm) for magenta, and light gray (g), medium gray (Gr), and black (z) for gray. Note that a capital letter designation can be used to refer to either a particular general color, as in the CMY colorants, or a darker shade of a particular color, as in a dark cyan (C) sub-colorant and a dark magenta (M) sub-colorant.

In the color cube ofFIG. 2, it may be desirable to limit darker colorants to regions of darker true colors near the origin210. Otherwise, in lighter regions, the darker colorants will likely be so sparsely scattered that the image will appear grainy. Limiting colorants in this way is often referred to as color separation.

A subset of color conversions can be stored in the look-up table (LUT), and then an interpolation approach can be used to estimate color conversions for additional data points based on the data points in the table. In one embodiment, conversions are calculated for a set of control points. Control points are often selected along at least 13 control lines in a color space. The color space inFIG. 2shows one of the control lines, control line260. Control line260extends between the K point210and the W point250. Control line260is referred to as the neutral control line, or neutral axis, because it passes through the middle of the color space. Data points along the neutral axis represent shades of gray, ranging from black (K) at210out to white (W) at250.

Twelve more control lines are illustrated inFIGS. 3 and 4. InFIG. 3, six control lines,320,330,340,335,345, and325, extend from the K point210to each of the six colorants RGB and CMY, respectively. InFIG. 4, six control lines,420,430,440,425,435, and445, similarly extend from the W point250to each of the six colorants RGB and CMY, respectively.

FIG. 5illustrates one embodiment of control points510on a control line500. Control line500has control points510at particular intervals over the length of the control line.

Table 1 below illustrates a LUT for an RGB to CMY color conversion for various control points. The CMY color space comprises CMYlclmKgGz channels, with 8-bits per channel. The position of each control point in the RGB space is indicated as a number of steps or intervals along each of the three RGB axes from the black (K) origin at 0, 0, 0 out to white (W) at 16, 16, 16. In the CMY color space, various sub-colorants are limited by a number of colorant boundaries. Specifically:Gr bound 12,z bound 8, andCM bound 8.

This set of colorant boundaries is defined in terms of steps away from the RGB origin at 0, 0, 0. “Gr bound 12” indicates that medium gray (Gr) is bounded at the twelfth step away from the origin along the gray axis, or neutral axis, from K to W. “z bound 8” indicates that black (z) is bounded at the eighth step away from the origin along the neutral axis from K to W. “CM bound 8” indicates that both dark cyan (C) and dark magenta (M) are bounded at the eighth step away from the origin in the directions of the cyan and magenta transitions, C to W and M to W, respectively. In other embodiments, any number of approaches can be used to define a LUT and colorant boundaries within the LUT.

Entries in Table 1 are organized into a number of transitions, starting with control points along the neutral axis from black to white. The next set of entries define additional control points along the white to red, and red to black, control lines. Subsequent sets of entries define additional control points along control lines for white to green to black, white to blue to black, white to yellow to black, white to magenta to black, white to cyan to black. In addition to control points along these 13 control lines, Table 1 also defines some control points along control lines from yellow to red, yellow to green, cyan to blue, and magenta to blue.

The colorant boundaries define boundary points along many of the transitions for certain colorants. For instance,FIG. 6illustrates the transitions defined by Table 1 for one surface of the color cube, surface CWMB, where B is 16 in the RGB space. Surface CWMB comprises five control lines, CW, WM, MB, BC, and WB. In the direction of decreasing C intensity630, C is bounded at step8. So, each control line crossing step8in the direction630includes a C boundary point650. In the direction of decreasing M intensity620, M is also bounded at step8. So, each control line crossing step8in the direction620includes an M boundary point640.

In the illustrated embodiment, a boundary point is defined to include none of the colorant or sub-colorant being bounded. Furthermore, steps beyond the boundary point along a given transition in Table 1 are also defined to include none of the colorant or sub-colorant being bounded. So, inFIG. 6, control points along segments635include no C, control points along segments625include no M, and control points along segment645include neither C nor M.

The set of control points defined in Table 1 can be used to interpolate the values of other points.FIG. 7illustrates one embodiment of an interpolation for a target point700from the control points of Table 1. A set of interpolation points710,720,730, and740are identified by extending out from control point700to the transitions defined in Table 1. If an interpolation point is a control point that has been previously defined in Table 1, the value of the control point in the CMY color space can be taken from the table. If, however, an interpolation point falls between two control points on a transition, the value of the interpolation point itself can be interpolated using, for instance, any of a variety of one-dimensional interpolations based on the values of neighboring control points on the control line.

A one-dimensional interpolation is usually some form of distance weighted average of the values of the linear neighbors. By defining a boundary point to include none of the colorant or sub-colorant being bounded, any interpolation point on a transition beyond a boundary point will also include none of the colorant or sub-colorant being bounded. For instance, point710can include both C and M because point710is before the boundary point. Point720, however, will not include C or M, and points730and740will not include M but may include C.

Once the values of all the interpolation points are defined, the value of target point700can be determined using, for instance, any of a variety of two-dimensional interpolations. Since some of the interpolation points can include C and M, target point700can also include both C and M.

The colorant boundaries are intended to constrain the darker colorants to the darker regions of the color space. If darker colorants are allowed into lighter regions, the darker colorants are too often sparsely distributed in the lighter regions, causing the image to look grainy. Merely defining boundary points based on the colorant boundaries, however, may be inadequate to reduce or eliminate graininess. That is, the darker colorant area750where darker colorants are used may extend deeply into the light colorant area760.

Therefore, embodiments of the present invention use the colorant boundaries to define boundary surfaces in the RGB color space.FIG. 8illustrates one embodiment of edges of these boundary surfaces. A path is formed through the color space to connect bounding points corresponding to the M colorant boundary into M boundary line810. Another path is formed to connect bounding points corresponding to the C colorant boundary into C boundary line820.

When interpolating target point800, the set of interpolation points870,871,872, and873are taken from control lines or from the boundary lines, whichever is encountered first. If any of the interpolation points are not already available in Table 1, they can be linearly interpolated from the predetermined values in Table 1. Since boundary points are defined to include none of the colorant or sub-colorant being bounded, points interpolated along a boundary line based on the boundary points at either end will similarly include none of the colorant or sub-colorant being bounded. Since the boundary lines are limited in this way, points on the surface past the boundaries lines will also include none of the colorant or sub-colorant being bounded. In other words, boundary lines810and820divide the surface CWMB into four regions, region830with no C or M, region840with both C and M, region850with C but no M, and region860with M but no C. The dark colorants are not permitted to extend into the lighter regions of the color space.

Boundary lines for a particular colorant boundary can be extended into higher dimensions to form boundary surfaces. For instance,FIG. 9illustrates one embodiment of an M boundary surface920. That is, just as boundary line810was formed inFIG. 8for surface CWMB, additional boundary lines can be formed in surfaces WYRM, GYRK, and CGKB based on the M boundary point910. The four boundary lines comprise the edges of M boundary surface920. Points on surface920can be interpolated using any of a variety of two-dimensional interpolation techniques based on the boundary points along the edges of surface920. Since all points around the edges of surface920include no M colorant, no point on surface920will include M either.

When interpolating points below surface920, the sets of interpolation points will only include points below or on surface920. When interpolating points above surface920, the sets of interpolation points will only include points above or on surface920. Since surface920includes no M colorant, no point above surface920will include M either. In other words, surface920divides the color space into lighter region930where M is not used and a darker region940where M can be used.

FIG. 10illustrates one embodiment of a C boundary surface1020that is formed based on a C boundary point1010much like the M boundary surface920fromFIG. 9. Like surface920, surface1020divides the color space into a lighter region1030where C will not be used and a darker region1040where C can be used.

In addition to boundary surfaces that span the entire color space, embodiments of the present invention can also form smaller boundary surfaces within a color space, and piece those smaller boundary surfaces into three-dimensional boundary regions. For instance,FIG. 11illustrates one embodiment of a boundary region defined by the black (z) colorant boundary from Table 1. Unlike the C colorant boundary that bounded C only in the direction of decreasing C intensity, the z colorant boundary can be defined to bound z in the direction of decreasing gray intensity. In other words, a z boundary point1120can be located on each transition out from the origin, including the neutral axis1110. Edges and surfaces can then be formed by connecting the boundary points. The surfaces collectively form the boundary region1130. Since the colorant boundary is at the same step location on each transition out from the origin, boundary region1130is a cube. With each z boundary point defined to include no z sub-colorant, the edges, surfaces, and exterior volume around boundary region1130can similarly be interpolated to include no z sub-colorant.

FIG. 12illustrates one embodiment of a boundary region defined by the medium gray (Gr) colorant boundary from Table 1. As with the z boundary region, Gr boundary points1210can be located on each transition out from the origin, and edges and surfaces can then be formed by connecting the boundary points. The surfaces collectively form the boundary region1220. With each Gr boundary point defined to include no Gr sub-colorant, the edges, surfaces, and exterior volume around boundary region1220can similarly be interpolated to include no z sub-colorant.

In some embodiments of the present invention, certain points are stored as they are interpolated so that they can be used along with the control points for future color conversions. These points can be, for example, various points on the surfaces defined by the control lines.FIG. 13illustrates19control lines in a color cube, lines KR, KG, KB, KC, KM, KY, KW, WR, WG, WB, WC, WM, WY, CG, GY, YR, RM, MB, and BC. The 19 control lines divide the color cube into six tetrahedra, KWMR, KWBM, KWCB, KWGC, KWYG, and KWRY. Each tetrahedron includes four triangular surfaces bounded by the neutral axis KW, one primary colorant corner, C, M, or Y, and one secondary colorant corner, R, G, or B.

FIG. 14illustrates the KWMR tetrahedron1410defined by control lines KW, WR, RM, MK, and WM. Using the colorant boundaries from Table 1, three boundary surfaces, z boundary1420, Gr boundary1430, and M boundary1440, can be defined within tetrahedron1410. That is, as described above, each boundary surface can be defined by connecting boundary points among neighboring control lines. Boundary points along the edges of each boundary surface can be linearly interpolated from the boundary points at either end of the edges. And, points on the surfaces of tetrahedra1410can be interpolated using two-dimensional interpolations based on the control points along the control lines and the boundary points along the boundary edges.

By defining the boundary points on the control lines to include none of the colorant or sub-colorant being bounded, the boundary points on the boundary edges, as well as boundary points within the boundary surfaces, will be similarly limited. By limiting all the edge boundary points, the two-dimensional interpolations on the surfaces of the tetrahedron will lead to areas that are also similarly limited. Then, a three-dimensional interpolation of any point within the tetrahedron that relies on interpolation points from the tetrahedra surfaces and/or boundary surfaces will lead to volumes that are similarly limited as well.

In other embodiments, any of a variety surface shapes and volumes can be defined using control lines and colorant boundaries. For example,FIG. 15illustrates one embodiment of a stepped boundary surface1530. Rather than defining a single boundary for magenta, the illustrated embodiment includes two bounds, bound1510and bound1520. Bound1510allows M to be used further along the MW and RY transitions than bound1520allows M to be used along the BC and KG transitions. Each step in surface1530may correspond to one or more steps or intervals between control points along the BM and MW transitions. Any number of techniques can be used to define the paths connecting the boundary points. For example, a path may take a shortest distance between boundary points on neighboring control lines and may evenly distribute any steps over the path's length.

FIG. 16illustrates yet another shape for a boundary region. Rather than constraining dark colorants near the origin, light gray (g) boundary region1630constrains the g sub-colorant to lighter portions of the color space. This may help conserve g ink, for instance. Without boundary region1630, g ink may be used for colors throughout the color space, potentially using a disproportionately large amount of g ink compared to other inks.

In the illustrated embodiment, region1630can be defined using two components for the colorant boundary. That is, the colorant boundary includes one boundary point1610along the YK transition and a second boundary point1620along the neutral axis transition. The two boundary points together define the rectangular volume of region1630.

FIG. 17illustrates yet another shape for a boundary region.FIG. 17departs from the color space defined by Table 1. The color space ofFIG. 17includes a dark green colorant that is constrained to a region near the G corner of the color space. That is, the dark green colorant boundary comprises three components, boundary point1710along the GY transition, boundary1720along the GK transition, and boundary1730along the GC boundary. As discussed above, the boundary points can be connected to form a boundary surface that defines the dark green boundary region1740. And, as discussed above, by defining the boundary points to include no dark green, none of the boundary points along the edges or surface of region1740will include dark green, effectively constraining the colorant.

In addition to constraining dark colorants to dark regions to reduce graininess, and in addition to constraining light colorants to light regions to conserve ink, embodiments of the present invention can be used for a wide variety of other applications. For instance, various embodiments of the present invention can be used for gray component replacement (GCR).

FIG. 18illustrates a mixture of C, M, and Y primary colorant intensities for a particular true color. A mixture of equal intensities of C, M, and Y produces a shade of gray, referred to as the gray component1810. Beyond the gray component1810, the true color is actually determined by the intensities of just two primary colorants, C and M in the illustrated embodiment.

To the extent that the two primary colorants mix in equal amounts, that portion of the mixture can be referred to the secondary component1820. The word “secondary” is used because the equal mixture of two primary colorants produces a secondary colorant, R, G, or B. Referring back toFIG. 1, the figure shows that C and M together will produce the secondary colorant B.

To the extent that one primary colorant intensity is higher than any of the others, that portion of the mixture can be referred to as the primary component1830. Just as every color can be defined as some mixture of C, M, and Y, every color can also be defined as some mixture of gray component, secondary component, and primary component.

In a CMY color space, the gray component can be created using near-equal mixtures of C, M, and Y colorants. Gray component replacement (GCR) is the practice of replacing that equal mixture, at least in part, with a gray colorant, such as black (K). GCR can provide a great many advantages, such as reduced total ink usage, reduced global hue shift, improved metamerism, improved gamut, and increased sharpness.

The gray component is present in colors throughout a color space. If a black colorant is used to replace the gray component everywhere, the black may make lighter regions appear grainy. That is, to provide light intensities of gray using a black colorant, droplets of black will likely be so sparsely dispersed that they are individually discernable to the naked eye. One approach to reducing grain is partial gray component replace. For example, black may be used over only part of the color space and a mixture of lc, lm, and Y may be used elsewhere for lighter shades of gray. As another example, a lighter gray colorant may be used for gray component replacement in lighter regions, and a mixture of C, M, and Y may be used in darker regions. In either situation, grain may be reduced, but many of the advantages of GCR are also diminished.

Therefore, embodiments of the present invention use multiple levels of gray colorant to provide 100% GCR throughout a color space. In other words, embodiments of the present invention can render every color in a CMY color space using no more than two primary colorants plus some amount of two or more levels of gray colorant. A primary colorant in this context includes any and all of its sub-colorants. So, for instance, a shade of green can be rendered using one or more sub-colorants of gray, such as g and Gr for example, and one or more sub-colorants of up to two primary colorants, such as C, lc, and Y for example.

By providing 100% GCR with multiple levels of gray, embodiments of the present invention can reduce or eliminate grain while providing the many advantages afforded by GCR. Grain is reduced by using lighter intensity gray dots in lighter regions of the color space so that dot densities are higher and individual dots are less visible.

Any number of approaches can be used to implement 100% GCR with multiple levels of gray, such as dot replacement rules or the boundary surface approaches described above. For example, dot replacement rules can filter data points for sparse densities of darker colorants and replace the dark colorants with higher densities of lighter colorants. Table 1 above provides a good example using boundary surfaces.

In Table 1, all of the gray colors along the neutral axis from black to white are entirely rendered using g, Gr, and z. z is bounded to the region near the origin, as shown inFIG. 12. Gr is bounded to a somewhat larger region extending from the origin, as shown inFIG. 13. g can be used anywhere in the color space.

Or, alternatively, as shown inFIG. 16, a slightly different definition can be used for a g colorant boundary to constrain g to lighter regions of the color space, potentially reducing consumption of g ink. A tetrahedral boundary scheme, such as the one shown inFIGS. 13 and 14, is particularly well suited for 100% GCR with multiple levels of gray because each tetrahedron comprises the gray axis, one primary colorant corner, and one secondary colorant corner.

FIGS. 19-25demonstrate operational flows for various embodiments of the present invention.

InFIG. 19, an indication of a target point is received in a first color space at1910. For instance, the indication may be a set of three step values in an RGB color space, such as those shown in Table 1. Alternately, the indication may be an index to a look-up table or an address to a memory location. At1920, a set of interpolation points are identified for the target point in the first color space from which to interpolate a value for the target point in a second color space. The set of interpolation points includes at least one boundary point in a boundary surface defined by a colorant boundary. For example, this could involve branching out from the target point in two or three dimensions to control lines and boundary surfaces, whichever is encountered first.

FIG. 20illustrates one embodiment for defining a boundary surface. At2010, a first bounding point is identified among control points of a first control line. At2020, a second bounding point is identified in a neighboring control line. Additional bounding points are identified along a path connecting the first and second bounding points at2030. The path may be a straight line or it may be more complex including, for example, a number of steps roughly following a diagonal connection between two neighboring bounding points.

At2040, the process moves on to the next neighboring control line and control point, and more bounding points are identified along the path to the next neighboring control point at2050. The process repeats itself, adding additional sets of bounding points along edges of the bounding surface, until the edges of the bounding surface are all defined at2060. Then, internal bounding points can be identified at2070as, for example, a set of points within a planar region bounded by the edges of the bounding surface.

FIG. 21illustrates one embodiment of a multi-step interpolation process once a set of interpolation points have been identified for a particular target point. At2110, the process starts by checking a look-up table (LUT) for any previously defined data points. These points could include control points, boundary points along boundary edges, boundary points within boundary surfaces, points on surfaces defined by control lines, and the like that may have been previously added to the table.

At2120, for an interpolation point that is on a control line, but is not a control point, the process performs a one-dimensional interpolation based on the predetermined control points on the control line to either side of the interpolation point.

At2130, for an interpolation point that is on an edge of a boundary surface, but is not available in the LUT, the process performs a one-dimensional interpolation based on the control points (boundary points) at either end of the edge.

At2140, for an interpolation point within a boundary surface, the process acquires values for a set of edge points of the boundary surface that correspond to the interpolation point and performs a two-dimensional interpolation based on the values of the edges points. In other words, interpolating the value of a point within a boundary surface can involve two iterations of interpolation. First, some edge points may need to be linearly interpolated. Then, the values of the edges points can be used in a two-dimensional interpolation to get the value of the point within the surface. The same process can be used for interpolation points on surfaces defined by control lines.

At2150, the target point is interpolated based on the values of the set of interpolation points. This could be a three-dimensional interpolation using, for instance, distance weighted, average values of the interpolation points. Other interpolation techniques can be used. At2160, the illustrated embodiment adds the interpolated values of control line, edge, surface, and/or target points to the LUT for future reference.

FIG. 22illustrates one embodiment of selecting a set of interpolation points. At2210, the process extends out from a target point in at least two directions. For a target point on a control line or boundary edge, the two directions may be to either side of the target point along the control line or boundary edge. For a target point on a surface defined by a set of control lines or on a boundary surface, the process may extend out in four directions, such as in the positive and negative directions of primary colorant axes parallel to the surface. For a target point not on a line, edge, or surface, the process may extend out in six directions, such as the positive and negative direction of all three primary axes.

At2220, if a point on a control line is encountered in a given extension, that point can be selected for the set of interpolation points and the extension can be stopped. At2230, if a point on a surface of the color space is encountered in a given extension, that point can be selected for the set of interpolation points and the extension can be stopped. Similarly, at2240, if a point is encountered in a given extension on either a surface or edge of a colorant boundary, that point can be selected for the set of interpolation points and the extension can be stopped.

FIG. 23illustrates one embodiment of both identifying and interpolating a set of boundary points for a color space having one colorant boundary that defines a multi-surface boundary region. At2310, the process identifies a pair of bounding points corresponding to a particular colorant boundary and located along neighbor control lines in a first color space. At2320, the process linearly interpolates values of points at intervals along a path connecting the pair of boundary points. The interpolated points along the path comprise an edge of a boundary surface. Additional boundary points are identified and additional values are interpolated along edges of the boundary surface until all the edges of the surface have been defined at2330.

Next, bounding points within the surface are interpolated. These surface bounding points may include points spread over the surface at particular intervals. For each surface bounding point, a set of surface interpolation points is identified at2340. The surface interpolation points may be boundary points located along the edges of the boundary surface in particular directions from the corresponding surface bounding point. At2350, each surface bounding point is interpolated based on the corresponding set of surface interpolation points.

At2360, the process loops back to2310through2350to identify and interpolate additional boundary surfaces until all of the boundary surfaces of a boundary region are identified. For instance, in the case of the z boundary fromFIG. 12above, the process may repeat for at least the three boundary surfaces of the z boundary region1230that are internal to the color cube. Alternately, the process may repeat for all six surfaces of region1230.

Next, points within the boundary region are interpolated. These internal points may include points spread throughout the region at particular intervals. For each internal point, a set of internal interpolation points is identified at2370. These may be located along the boundary surfaces in particular directions from the corresponding internal point. At2380, each internal point is interpolated based on the corresponding set of internal interpolation points.

Next, points outside the boundary region are interpolated. These external points may include points spread throughout the color space at particular intervals, outside the boundary region. For each external point, a set of external interpolation points is identified at2390. These may be located along the boundary surfaces, and/or surfaces defined by the set of control lines, in particular directions from the corresponding internal point. At2395, each external point is interpolated based on the corresponding set of external interpolation points. This may involve an intermediate interpolation step to get values for some of the points located on surfaces defined by the set of control lines.

FIG. 24illustrates one embodiment in a color space having multiple colorant boundaries. At2410, a plurality of colorant boundaries are identified in a first color space. These could include, for instance, the z, Gr, C, and M boundaries used in Table 1 above. At2420, one boundary region is defined in the first color space for each colorant boundary.

FIG. 25illustrates one embodiment of 100% gray component replacement (GCR) using multiple levels of gray ink. At2510, an indication of a target point is received. The target point is internal to a first color space. That is, the target point is not located on one of the external surfaces of the color space. Each external surface may be rendered using just two primary colorants, so gray component replacement might not be needed for the external surfaces.

At2520, the target point is rendered in a second color space using at least one of at least two levels of gray colorant and at most two primary colorants out of three primary colorants in the second color space.

FIGS. 19-25illustrate a number of implementation specific details. Other embodiments may not include all of the illustrated elements, may arrange the elements in a different order, may combine or separate one or more of the elements, and may include additional elements.

FIG. 26illustrates one embodiment of a hardware system intended to represent a broad category of devices such as personal computers, workstations, embedded systems, and/or imaging devices such as color printers. In the illustrated embodiment, the hardware system includes processor2610coupled to high speed bus2605, which is coupled to input/output (I/O) bus2615through bus bridge2630. Temporary memory2620is coupled to bus2605. Permanent memory2640is coupled to bus2615. I/O device(s)2650is also coupled to bus2615. I/O device(s)2650may include a display device, a keyboard, one or more external network interfaces, a printing mechanism, etc.

Certain embodiments may include additional components, may not require all of the above components, or may combine one or more components. For instance, temporary memory2620may be on-chip with processor2610. Alternately, permanent memory2640may be eliminated and temporary memory2620may be replaced with an electrically erasable programmable read only memory (EEPROM), wherein software routines are executed in place from the EEPROM. Some implementations may employ a single bus, to which all of the components are coupled, or one or more additional buses and bus bridges to which various additional components can be coupled. Those skilled in the art will be familiar with a variety of alternate internal networks including, for instance, an internal network based on a high speed system bus with a memory controller hub and an I/O controller hub. Additional components may include additional processors, a CD ROM drive, additional memories, and other peripheral components known in the art.

In one embodiment, the present invention, as described above, is implemented using one or more hardware systems such as the hardware system ofFIG. 26. Where more than one computer is used, the systems can be coupled to communicate over an external network, such as a local area network (LAN), an internet protocol (IP) network, etc. In one embodiment, the present invention is implemented as software routines executed by one or more execution units within the computer(s). For a given computer, the software routines can be stored on a storage device, such as permanent memory2640.

Alternately, as shown inFIG. 27, the software routines can be machine executable instructions2710stored using any machine readable storage medium2720, such as a diskette, CD-ROM, magnetic tape, digital video or versatile disk (DVD), laser disk, ROM, Flash memory, etc. The series of instructions need not be stored locally, and could be received from a remote storage device, such as a server on a network, a CD ROM device, a floppy disk, etc., through, for instance, I/O device(s)2650ofFIG. 26.

From whatever source, the instructions may be copied from the storage device into temporary memory2620and then accessed and executed by processor2610. In one implementation, these software routines are written in the C programming language. It is to be appreciated, however, that these routines may be implemented in any of a wide variety of programming languages.

In alternate embodiments, the present invention is implemented in discrete hardware or firmware, such as identification circuitry or defining circuitry to identify or define boundary surfaces, interpolation circuitry for interpolating based on the boundary surfaces, and rendering circuitry for gray component rendering. For example, one or more application specific integrated circuits (ASICs) could be programmed with one or more of the above described functions of the embodiments of the present invention. In another example, one or more functions of the embodiments of the present invention could be implemented in one or more ASICs on additional circuit boards and the circuit boards could be inserted into the computer(s) described above. In another example, programmable gate arrays could be used to implement one or more functions of embodiments of the present invention. In yet another example, a combination of hardware and software could be used to implement one or more functions of the embodiments of the present invention.

Thus, gray component replacement using multiple levels of gray is described. Whereas many alterations and modifications of the embodiments of the present invention will be comprehended by a person skilled in the art after having read the foregoing description, it is to be understood that the particular embodiments shown and described by way of illustration are in no way intended to be considered limiting. Therefore, references to details of particular embodiments are not intended to limit the scope of the claims.