Color Conversion Method

The present invention relates to methods for converting from one colour space to another colour space and to a printing process whereby output is printed on a device having a limited or restricted gamut of colours.

Each printing device for the printing of colour images has a measurable gamut or range of colours which it is able to reproduce from any primary colours that it may utilise. This gamut varies from output device to output device, in addition to some variation between output devices of the same kind.

Colour images are often stored and printed in different colour spaces. For example, colour images displayed on a CRT-type device are normally stored in a Red, Green and Blue (RGB) format. This corresponds to the relevant primary colours (RGB) utilised in most CRT-type displays. Colour printing devices normally work in a subtractive colour space that comprises the Cyan, Magenta, Yellow (CMY) or Cyan, Magenta, Yellow and black (CMYK) colour spaces. Methods for conversion from one colour space to another are well known, with common methods utilising a sparse lookup table and interpolation between data points.

The CIE co-ordinate system defines three standard primaries (X, Y and Z) that represent the amount of spectral energy of a particular colour. Instruments, called colourimeters, measure the tri-stimulus values of X, Y and Z. Methods are know for mathematically transforming from RGB space or CMYK space to XYZ space and vice versa.

Unfortunately, these methods often require multiple table lookups, in addition to multiplication operations that are required to be performed as part of the interpolation process. Therefore, if it is desired to perform the conversion process within a standard microcomputer system it is likely that these known methods will take an unacceptably long time to complete the colour conversion process of a whole image.

Additionally, as previously mentioned, each output device has its own range or gamut of possible colours that it may print. Therefore, even if the colour conversion process has been carried out from one colour space to another, there is no guarantee that the colour derived in the second colour space will fall within the gamut of the output device. Further processing will be necessary in order to map the unprintable colours to those which are within the gamut of the printing device.

On the one hand, if it is desired to faithfully reproduce an image, extra inks and unique printing processes must be employed. If the goal is to make a pleasing rather than exact reproduction, it has been found that it is unnecessary to reproduce the exact image colour. It is of some importance, however, to attempt to maintain the relative differences between different initial colours.

Referring now to FIG. 1, there is shown an example of a conventional CIE chromaticity diagram. The gamut area 1 represents the gamut output by a CRT-type display device. The gamut 2 could represent the gamut of colours printable on a paper printing device such as an ink jet printer.

It is therefore seen that there is a problem when it is desired to print out an image displayable on a CRT-type device on, say, an ink jet printing device. The ink jet printing device will be unable to print colours e.g. 3 which are outside of its gamut 2 but within the gamut 1 of the CRT-type device.

Colour images intended to be displayed on a first colour display device having a first colour gamut are displayed on a second colour display device having a second colour gamut which is different than the first colour gamut. First, a plurality of input extrema colour values (RGB) are determined within the first colour gamut and at the extrema of the first colour gamut of the first colour display device. Next, a plurality of output extrema colour values (R'G'B') are determined corresponding to the input extrema colour values (RGB) within the second colour gamut and at the extrema of the second colour gamut of the second colour display. A mapping is determined for substantially all the values within the first colour gamut to substantially all the values within the second colour gamut, with the relative value of difference between colour values relative to the extent of the first colour gamut and differences between corresponding colour values of the second colour gamut relative to the extent of the second colour gamut being preserved. The mapping includes determining colour correction function mapping values within the second colour gamut to color gamut values of the second color gamut. The color correction function includes a number of free parameters, the values of which are determined by measurement of output colour values of the second colour display device using a colourimeter. The measurement may be made in an alternative colour space and converted to the colour space of the second colour gamut of the second colour display device, with the conversion utilizing a predetermined number of the output extrema values to determine the conversion. The conversion may include utilizing a barrier function to ensure that the converted measurements are within the second colour gamut of the second colour display device.

A preferred embodiment of the present invention is described below with reference to the accompanying drawings in which:

FIG. 1 illustrates the CIE gamut space of different output devices;

FIG. 2 is a CIE diagram illustrating a first method of mapping from one printer device colour space to a second printer device colour space;

FIG. 3 is a CIE diagram showing a second method of mapping from one printer device colour space to a second printer device colour space;

FIG. 4 illustrates, in three dimensions, the different colour spaces of various output devices;

FIG. 5 illustrates a barrier function used in the numerical optimisation procedure utilised in the preferred embodiment;

FIG. 6 illustrates the problem of "dot gain" experienced by printing devices, and

FIG. 7 is a flow chart indicative of processing colour images.

In the preferred embodiment of the present invention, an attempt is made to preserve the relative colour differences between any two absolute colours at the expense of a remapping of the colours to be printed.

Referring now to FIG. 2 there is shown a first method of mapping from the CRT type gamut 1 to the ink jet gamut space 2. In this method, points outside the ink jet gamut space 2 are mapped to the closest point on the surface of the gamut space 2. For example, the colour 5 which is within the coloured gamut 1 of the CRT type device is mapped to the colour 6 which lies on the edge of the gamut 2 of the ink jet printing device. Similarly, the colour 7 which is outside the ink jet printer gamut 2 is mapped to the colour 8, which is again on the edge of the gamut 2 of the ink jet type printing device. Those colours e.g. 10 which lie within the gamut space 2 of the ink jet type printing device are mapped to themselves and their values are not altered. The mapping of FIG. 2 is designed to optimise "absolute" colour accuracy. Those colours which are inside the ink jet colour gamut 2 are prefectly reproduced. Those outside the ink jet colour gamut are "clamped" to the nearest points on the boundary.

Referring now to FIG. 3, there is shown the method of colour gamut matching utilised in the preferred embodiment where the strategy adopted is to optimise the mapping to make relative distances between different colours in the image remain the same. The Red R, Green G and Blue B "corners" of the CRT gamut 1 are mapped to the Red R', Green G' and Blue B' corners of the ink jet gamut 2. This mapping is carried out regardless of the absolute colour values of these corners. Those colours in the interior of the CRT gamut are mapped so as to preserve their relative differences from the R, G, and B corners as well as from each other. For example, in FIG. 3, the point G is mapped to the point G', the point B is mapped to the point B' and the point R is mapped to the point R'. Additionally, the point 10 is mapped approximately to the point 11 and the point 12 is mapped approximately to the point 13.

Referring now to FIG. 4, there is shown the extension of the ideas of FIG. 3 into three dimensions in XYZ space. A first colour cube 15 represents the RGB colour cube of displayable colours by a CRT type device. Of course, it is evident to those skilled in the art, that colour "cube" 15 may not necessarily be an exact cube and can take the form of a parallelepiped or other volume.

Similarly, colour "cube" 16 represents those colours displayable by an ink jet printing device. Colour correction cube 16 can be "skewed" or "rotated" relative to colour correction cube 15.

The ink jet printing device normally relies on four colour inks, being Cyan, Magenta, Yellow and blacK (CYMK). the black portion of ink is normally obtained in accordance with the following equations: ##EQU1## However, an ink jet printing device is normally a "binary" type device in that normally only two levels of output are possible for each primary colour output comprising either the presence or absence of ink. Therefore, the normal equations 1, 2 are modified to take into account the ink jet printer's binary nature such that if C, M and Y are all to be turned on they are replaced by K. This is expressed by the following pseudo code:

A number of assumptions are made in the implementation of the colour mapping of the preferred embodiment. Firstly, it is assumed that all points in the interior of both colour cubes are physically achieved by mixing various amounts of the corner colours and, secondly, that no point exterior to each cube is physically achieved by mixing colours from its corners. These assumptions are not often valid as measurements with a colourimeter can easily show that the assumptions are violated in practice. Therefore, methods will be discussed to allow the minimisation of errors caused by physical deviations from these theoretical assumptions.

Further, it will be assumed that there is a one to one, non-linear mapping function which models the distortion caused by the half toning and/or printing by the ink jet printing device. As such a function exists, an inverse must also exist and this inverse is the colour correction function which is required. If such an inverse can be found, then, theoretically, it can be used to correct all the colour distortions of the ink jet printing device resulting in a printing system which will preserve relative colour. In practice, it is only possible to approximate this inverse function. The method of constructing an inverse approximation, as shown in FIG. 7 consists of the following four steps:

1. A functional form of the universe is assumed to exist (61, FIG. 7). This functional form will map the point (r,g,b) from the three dimensional RGB space of input values to points on a mathematically identical RGB space. The INPUT points to this function will represent the OUTPUT of the ink jet printer system. The OUTPUT points of this function will represent the INPUT to the ink jet printing system. It is further assumed that the eight corner points (FIG. 4) will map to themselves. The function will further have a number of free parameters, c0,c1,c2, . . . , which are set to optimise the fit between the function and measured experimental data. The function can therefore be written as:

where c0, c1 etc represent the free parameters, Rprint represents the red portion of the colour space value of the ink jet printer, and Rin presents the red portion of the value input to the ink jet system.

2. The various RGB colour sample points are printed utilising the target ink jet printing system and their corresponding colour values are measured using a colourimeter (62, FIG. 7). The points printed and measured should include the eight corners of the RGB colour cube 16 of FIG. 4. The measurements taken by the colourimeter can be utilised in fitting the colour correction function. One suitable method is to print out a 5.times.5.times.5 grid of equally spaced colour points in the input colour space of the ink jet printing system.

3. The sample points printed out are then measured in a linear colour space such as XYZ. If measurements are required to be formed in a non-linear form of colour space, such as CIE or Lab, the measured numbers must first be transformed into a linear space.

In order to fit the colour correction function (Equation 3), it is necessary to express these XYZ numbers as RGB coordinates (63, FIG. 7), and then fit the colour correction function (64, FIG. 7), as described in more detail later. As set out previously, it is assumed that the corner points of the colour cube 15 are mapped to the corner points of the RGB colour cube 16. The other printed colours are assigned coordinates in RGB space by comparing their measured colour values with the measured colours of the corners of the RGB cube 15.

The sample data points printed by the above process and measured by the colourimeter will consist of pairs of Rin, Gin, Bin input values and Xprint, Yprint, Zprint output values as follows:

Of course, this assumes that the points are measured in a linear space such as XYZ, however, methods are known to transform from a nonlinear space such as CIE or Lab to XYZ.

In order to fit the colour correction function, the output colours must be expressed in RGB coordinates. Therefore, it is required that for all data points, the pairs as set out in Equation 4 be transformed into the following form:

As mentioned previously, it is assumed that the corner points of colour cube 15 are correctly mapped to the corner points of colour cube 16. Thus, as a result of this assumption we have the following relationship: ##EQU2##

As colourimeter measurements have been made of these corner points, the colourimeter measurements of the other measured sample points can be expressed as convex linear combinations of the above corner point measurements. The convex linear combination weightings or coefficients can then lead to an assignment of RGB print values to these measured points.

If the colourimeter measurements for the eight corner points are as follows:

and if the printed RGB gamut is assumed to be of a cubic nature, and the measurement space is assumed to be linear, it is possible to calculate the XYZ measurements for other RGB print values by the use of trilinear interpolation which can be determined as follows: ##EQU3##

Since measurements have been taken for various (Xprint, Yprint, Zprint) it can be assumed that Equation 8 can be utilised to estimate values for the variable Rprint, Gprint, Bprint by minimisation of the error in the predicted (Xpredict, Ypredict, Zpredict) output value. The error between predicted and actual values can be expressed as an error function of the following form:

Conjugate direction methods can then be utilised with respect to Equation 9 to choose (Rprint, Gprint, Bprint) so as to minimise the error over all the data samples. Conjugate direction methods are numerical methods utilised for minimising non-linear functions in multiple variables. Conjugate direction methods are well known to those skilled in the art of numerical analysis and appear in a number of standard texts. For example, reference is made to the text "Linear and Nonlinear Programming" by David G Luenberger, Second Edition, 1984, Addison-Wesley Publishing Company, Reading, Mass. and to the standard text "Numerical Recipies in C, The Art of Scientific Computing" by Press et al, published by Cambridge University Press 1992.

As the colour cube 16 is not a perfect cube and as a result of a number of the assumptions made, and because of noise in the measured data, the application of well known conjugate direction methods directly to the above formulas can yield values which are well outside the admissible range of colour cube 16. Simply moving these values to the closest points on colour cube 16 was found to not yield the best RGB values in the admissible range. A better method is to utilise a barrier function in the conjugate gradient direction method optimisation procedure. The utilisation of a barrier functions is more fully described in the above texts. The barrier function can be used to confine the RGB values to the admissible range during optimisation. A barrier function of the following form is suitable: ##EQU4##

The barrier function takes the form as shown in FIG. 5 with an asymptotic value of plus infinity at x=1.

By adding the barrier function to the error objective, the objective function is caused to go to positive infinity for small deviations outside the admissible colour range. The new objective function is therefore: ##EQU5## wherein "s" is a scaling factor which determines how far outside the admissible colour range the solution values are allowed.

Setting s to positive infinity will, in theory, prevent any deviation from the admissible range. However, this also has the known effect of driving the condition number of the corresponding Hessian of the optimisation problem to infinity, which will dramatically slow or stop convergence of the conjugate direction methods. Experiment has found that a value of s=300 is a good compromise value to use.

The object of equation 9 is easily minimised using a conjugate direction method. In the present case, Powell's conjugate direction method was found to be adequate to optimise equation 11. The optimisation is performed for every measured sample point, to give a (Rprint, Gprint, Bprint) vector. These vector values are then used to fit the colour correction function.

4. Fitting the Colour Correction Function

The fitting of the colour correction function (64, FIG. 7) to the measured data is a nonlinear process and, as such, a nonlinear fitting method must be utilised. To fit the colour correction function, an error function is again constructed, however this error function measures the average deviation of predicted data from the measured data. Conjugate direction methods can then be used on this error function in order to find its minimum. The error function utilised is a simple sum of the squares error function of the following form: ##EQU6##

The free parameters c.sub.j of the above formula can be adjusted to give the minimum error using a conjugate direction method. The colour correction function maps points from the three dimensional RGB space

to points in a mathematically identical RGB space. As noted previously, the INPUT points to the colour correction function represent the OUTPUT of the ink jet printing system, and the OUTPUT points of the colour correction function represent the INPUT to the ink jet printing system. It is further assumed that the eight corner points map to themselves. Further, as noted previously, the function has a number of free parameters c.sub.j which are required to be optimised.

The colour correction function is the inverse of a print distortion function which can be written in the following form:

In the present embodiment, the form of the print distortion function is first derived and then inverted to obtain the colour correction function.

Several considerations enter into the choice of the colour correction function's actual form. These considerations include:

1. The function should be able to accurately approximate physical reality.

2. The function should be able to be efficiently programmed for incorporation into driver software for a microcomputer or the like so that an inordinate delay does not occur in the printing of images.

3. The function should have as few free parameters, c.sub.j, as possible so that fewer measurements are needed to obtain a good fit to the sample data without overfitting occurring.

One popular colour correction function, utilised with CRT type devices, is the "gamma correction" function which takes the following form: ##EQU7##

However, this function was found to provide poor quality results when applied to printing devices such as ink jet printers. This is most probably as a result of its intended purposes, which is in use for CRT type displays and hence there is no physical reason why it should produce good results for an ink jet printing system. A more thorough analysis can therefore be undertaken as to the physical operation of a printer such as an ink jet type printer. These physical principles of operation can then be used to construct a more suitable print distortion function which can then be inverted to provide the colour correction function.

The most significant distortion in devices such as ink jet printing devices is that caused by "dot gain". Ink jet printing devices, such as the Canon BJ600, work on the principal of ejection ink onto paper in the form of a large array of dots or pixels. Commonly, these devices can eject 300 or 400 dots per inch. Methods, commonly known as halftoning, are utilised so that the collation of the dots printed approximates a desired full coloured image. In a first, oversimplified representation, each dot can be considered uniform and modelled for example as a uniformed sized round dot 40 of FIG. 6. Unfortunately, in practice, when a single dot is ejected onto paper or the like, it is absorbed by the paper and "spreads out" such that it has a non-uniform boundary and each dot has a variation in size as shown by the dot 41 of FIG. 6. Also, when a series of dots 42-44 are printed close together, the moisture from a first dot 42 can effect subsequent dots e.g. 43 such that their combined area is again substantially increased. These problems are well known to those in the printing art, and fall under the general heading of "dot gain".

The problems of dot gain appear to be physically unavoidable and the amount of dot gain depends on the details of the arrangement of the dots on a page. A very simple and robust assumption is that the dots of ink are projected onto the page in a random distribution. The random distribution assumption leads to the following differential equation for the amount of colour produced by a given amount of ink ejected on a page: ##EQU8##

In this equation C is the amount of colour, I is the amount of ink, and G is the amount that each dot "spreads out" when printed and can be considered a measure of the dot gain. This differential equation states that the fraction of uncoloured or uncovered paper which is coloured by a small amount of ink is given by the dot gain G. The differential equation of Equation 16 can be easily integrated to yield

with the boundary condition that C=0 when I=0. Equation 17 in its present form implies that the colour coverage never reaches 100%. Equation 17 can be renormalised such that colour coverage at I=1 is equal to 100%. This renormalisation takes the following form: ##EQU9## Thus Equation 18 represents a form of the print distortion function. In order to obtain the colour correction function, Equation 18 must be inverted. This inversion takes the following form: ##EQU10## Equation 19 applies only to one colour of ink. Ink jet printing devices, printing on, for examples white paper, utilise a "subtractive" colour printing process. One form of well known full colour subtractive colour printing process utilises three colours of ink, being Cyan, Magenta and Yellow with methods for transferring from one colour printing process to the other being well known.

The utilisation of three subtractive colour inks yields the following series of equations: ##EQU11## The cyan, magenta and yellow CMY values can be easily converted to and from corresponding RGB values utilising the following relationship. ##EQU12##

Reasonably good results are produced when utilizing Equation 20 as the colour correction function is free of the parameter G and the results produced were found to be reasonably good. Equation 20 has the advantage of being easy to fit using conjugate gradient methods as it only has one free parameter G. Further, it would be easy to implement in ink jet printer driver software. However, Equation 20 has a number of significant disadvantages. These include:

(i) The conversion of CMY to K is totally ignored in the above equations.

(ii) The dot gain is not constant but rather appears to be a function of the total amount of ink or moisture on the page. More ink on a page means that more moisture is present and this normally tends to change the tendency for a particular ink to interfuse into the paper. This unwanted effect tends to destroy the possibility of independently correcting for each colour.

These effects can be modelled by making the dot gain a function of the amount of ink on the page. The amount of ink on the page can be roughly modelled as follows: ##EQU13##

The functional form of the relationship between the dot gain G and the total amount of ink is not known. However, assuming that the functional form is reasonably well behaved, it will have a Taylor's series expansion of the following form:

where g.sub.0, g.sub.1 etc are unknown constants. This Taylor's series expansion can be truncated and the parameters fitted to the certain measured colourimeter data. Substantial improvement can result from using the second linear term, but no substantial improvement normally results from using higher order terms. Therefore, the Taylor's series expansion of Equation 23 is truncated to take the following form:

The final form for the colour correction function is therefore: ##EQU14##

The above function is a reasonably simple one and has only two free parameters, g.sub.0 and g.sub.1. Fitting g.sub.0 and g.sub.1 to a set of 125 measured colourimeter values can be performed in reasonable computer time using Powell's conjugate direction method. Tests have shown that the results yield excellent colour reproduction on ink jet printing devices such as Canon Inc's BJ600. Different types of paper will produce different dot gains and hence lead to different values for g.sub.0 and g.sub.1.

The foregoing describes only one main embodiment of the present invention, with minor modifications. Further modifications obvious to those skilled in the art, can be made thereto without departing from the scope of the invention.

Appendix 1 sets out a C code program for performing the first Powell method optimisation, Appendix 2 sets out C code source for performing the second Powell optimisation, Appendix 3 sets out various non-standard library functions utilised by Appendix 1 and 2. ##SPC1##