Method and Apparatus for Converting Data Representations of an Image Between Color Spaces

1. Field of the Invention

The invention relates to a color image processing system and more particularly to a method of reversibly converting a color image between a first color space and a second color space with minimal loss of image integrity.

2. Description of the Prior Art

In the prior art it is common to convert an image from one color space to another. These conversions are necessary because the red-green-blue (RGB) color space that is used to display images on a display device such as a cathode-ray-tube (CRT) is not readily compressible when digitally recorded. To efficiently store the information, a luminance-chrominance (YCrCb) color space has been developed which enables the digital representation of the image to be much more greatly compressed. International standards have been developed for converting the representation of these different color spaces from one form to another. The Comite Consultalif International des Radiocommunications (CCIR) has established the formulas in standard CCIR 601 for converting between the luminance-chrominance (YCrCb) color space and the red-green-blue (RGB) color space. The formulas for converting RGB to YCrCb are:

The formulas for converting YCrCb to RGB are:

Using floating point arithmetic the conversion from one color space to the other can be achieved without loss of integrity as the calculations can be made as required to ensure that the ultimate result of any particular conversion is not subject to a rounding error. Also, such a conversion requires that each color point in each color space be convertible to a color point in the other color space. In the situation where each point of the color space is represented by three elements, such as Red, Green and Blue, each element can have one of 256 values or, in other words, the color space can represent 256.times.256.times.256=16.7 million colors. The conversion of each point to a corresponding point in the other color space can be very time consuming and requires large amounts of storage space.

One way of overcoming the time delays and storage constraints in performing the floating point conversion has been the development of a set of look-up tables whereby a point in a first color space is directly converted to a point in the second color space by looking up the corresponding value in a look-up table. For this table look-up process to provide effective and speedy conversion it is essential that the number of values in the tables and the number of tables be reduced to the minimal number necessary to enable a human viewer of an image to obtain a reasonably valid perception of the image when displayed.

The table look-up process for converting from YCrCb to RGB works satisfactorily in those situations where the image is to be converted once and then discarded, for example, when an image is printed. However, when the image is to be kept and displayed or manipulated a plurality of times where it is necessary to convert the image back and forth between the two color spaces, the quality of the image can deteriorate substantially because of rounding errors in the conversion process. As these errors compound with each conversion the quality of the resulting image becomes less and less acceptable.

The image distortion is similar to the following problem with photocopying a sample of text many times. A clean original sample of text on a page may be photocopied and will produce an accurate copy of the page. If you then photocopy the copy, a copy is produced with some amount of distortion. As you continue to photocopy the resultant copies, the distortion of the original sample increases with each copy until the point where the text becomes illegible.

The present invention compensates for the rounding errors by providing a process for generating and tuning the color space conversion look-up tables to maintain the reproducability of each original color point. Application of the look-up tables for converting YCrCb data into RGB data stabilizes 99.07% of the RGB data after the first conversion. The remaining 0.93% of the RGB data stabilizes after four conversions, ie. distortion will not propagate. For converting RGB data into YCrCb data, 99.93% of the YCrCb data stabilizes after the first conversion. The remaining 0.07% of the YCrCb data stabilizes after 3 conversions, again preventing propagation of errors.

It is accordingly a primary object of the present invention to enable multiple conversions of an image between one color space and another with minimal distortion to the data representation of the image.

A particular object is to provide multiple conversions of an image stored in YCrCb color space to an RGB color space and back to YCrCb color space without propagating any distortion to the data representation of the image.

It is a further object to tune look-up tables for conversion of images between RGB and YCrCb color spaces so that the image information is substantially stable over an infinite number of conversions.

It is a further object to apply the look-up tables in a computer program for converting image data within a micro-processor based system.

These and other objects of the present invention are achieved by generating a set of tables for converting data from a first color point in a color space to a corresponding color point in the other color space. The conversion of data is repeated a sufficient number of times to enable distortion errors from one conversion to the next to be detectable.

In the case where the color space is represented by 256 distinct values for each color point, the conversion process would be for RGB, 256.times.256.times.256=16.7 million conversions. After the conversion has been run n number of times, where n is sufficient to enable changes to be detectable, the values of the RGB color points and the YCrCb color points that do not compare from conversion to conversion identify points that must be changed or tuned. Each identified point is analyzed to determine the direction the point has moved between conversion n and conversion n-1. As a consequence of the analysis, the table look-up points for the identified points are adjusted accordingly and the conversion process repeated until such time as no values in the table change between conversions.

Additionally, the accuracy of the conversion process can be substantially enhanced initially by minimizing the rounding errors in the conversion process. This is achieved by increasing the precision for each component by multiplying each component by a suitable multiplying factor such as 2 or 4 when calculating the table value and then dividing the result by the multiplying factor to more precisely select the appropriate table value.

The invention provides an improved process for transforming a first form of color representation and a second form of color representation using look-up tables to represent said colors consisting of the steps of:

a) transforming all colors in said first form of color representation using said look-up tables to said second form of color representation

b) transforming all color in said second form of color representation transformed during said first transforming step to said first form of color representation,

repeating said steps a) and b) a plurality of times,

comparing the results of each subsequent transformation to the results of previous representations and

where said results do not compare, altering said representation so as to compensate for said non-comparison and

retrying said transformation steps until said transformations do not alter.

The invention also provides a processor for processing images comprising first an image processor comprising first means for storing images in a first color space, second means for storing images in a second color space, a first storage means for storing a first set of tuned tables for converting an image stored in a first color space to an image stored in a second color space, a second storage means for storing a second set of tuned tables for converting an image stored in said second color space to an image stored in said first color space, first addressing means for addressing said tables in said first storage means in response to image information received from said first means for storing, said tables in said first storage means providing an output representative of said image information in said second color space, second addressing means for addressing said tables in said second storage means in response to image information received from said second means for storing, said tables in said second storage means providing an output representative of said image information in said first color space, whereby an image can be repetitively converted from one color space to the other with no loss of integrity in the image.

FIGS. 1a and 1b show a flow diagram of the process of generating and tuning tables for converting between the RGB color space and the YCrCb color space.

FIG. 2 is a partial computer program illustrating a data setup and conversion from RGB to YCrCb, and then from RGB back to YCrCb.

FIG. 3 is a computer program subroutine illustrating the conversion from RGB to YCrCb applying the round-trip tables.

FIG. 4 is a computer program subroutine illustrating the conversion from YCrCb to RGB applying the round-trip tables.

In the following detailed description certain specific terminology is used for the sake of clarity and specific examples and embodiments are described. For example, the invention is described in relation to the conversion between YCrCb and RGB color spaces whereas it may be equally useful in converting between other color spaces. It is understood that the invention is not intended to be limited and should not be so construed, inasmuch as the invention is capable of many forms and variations as defined within the scope of the appended claims.

As set forth hereinabove, a primary object of the present invention is to enable reversible conversion between two representations of an image in color space where look-up tables are used to represent the conversion between the two color spaces. In the case where the image is to be represented in either the YCrCb color space or the RGB color space a total of 9 tables have been selected as sufficient to convert the image points. 5 tables are used for converting the image from RGB to YCrCb and 4 tables for converting from YCrCb to RGB.

The generation of the look-up tables involves the conversion from RGB to YCrCb and the conversion from YCrCb to RGB. In a preferred embodiment, the first conversion is from an input of three bytes per color point. Each byte represents a red, green or blue component for each color point. The resulting output from these bytes selecting values from the tables is a three byte output representative of the Y, Cr and Cb components of the color point. Each byte consists of 8 bits which can represent up to 256 distinct values. In the preferred embodiment, the representations of R,G,B,Y,Cr and Cb allow up to 256 valid levels for each component.

The overall process for generating a set of reusable integer look-up tables for conversion of image information between the RGB color space and the CrCb color space is illustrated by the flow diagram shown in FIG. 1.

As illustrated at 1, a set of integer look-up tables are generated. For conversion between RGB and YCrCb, a set of 9 tables is required. One table represents all valid values of 0.299R, one all valid values of 0.587G, one all valid values of 0.114B, the fourth, all valid values of 0.713(R-Y)+128, the fifth, all valid values of 0.564(B-Y)+128, the sixth for 1.402(Cr-128), the seventh for 0.714(Cr-128), the eighth for 0.344(Cb-128), and the ninth for 1.772(Cb-128).

These tables are selected so as to approximate the floating point calculations needed to conform to the CCIR 601 formulas for converting between RGB to YCrCb which are:

for 0=<R,G,B,Y,Cr,Cb<=255, a range bounded by a byte, or 8 bits.

After each point in each of the nine tables is determined, as illustrated at 2, selected tables are multiplied by a fixed factor so as to ensure that any error created by rounding off of the calculations to an integer value is minimized. For the RGB to YCrCb conversion, the R,G and B tables are multiplied by 4 to increase the precision of the table values.

Then at 3, all combinations of R, G and B (all RGB points) are converted to YCrCb using the look-up tables and then back to RGB.

As indicated at 4, the conversion procession is repeated a plurality of times. Although the number of times can be any number, the inventor has found that repeating the conversion process 5 times is usually adequate.

After the conversion is performed the selected number of times, the generated values from application of the tables between the last and second last conversion cycle are compared. Although this is the preferred manner of identifying the problem points, as it minimizes the number of problem points, other comparisons such as between the 3rd and the 5th conversion could be used.

The points in the tables that do not compare are modified as indicated at 6.

Performance of this modification requires that the nature of the variance in the problem point from conversion cycle to conversion cycle be understood. This involves identifying the components of the CCIR equations and how the components relate to each other. A simple analysis of the components on their own is performed. The problem points are ordered in accordance with the value of the components that produced them. Where a specific value of a component occurs a large number of times within the set of problem points, then that component is identified as a candidate for modification. In addition, the distribution of the combinations of components is analyzed to find any combination of values that occur a large number of times.

After the points selected for modification are identified, the value in the look-up table is adjusted either upwardly or downwardly depending upon:

1) The direction in which the problem point at n is moving from the corresponding point at n-1 and

2) The direction the problem point at n is away from the corresponding original floating point value as compared to the same point n-1 was in relation to the floating point value.

3) The direction the problem point is moving from the specific iteration of the point, ie n.

4) The existence of a "hole" in the table data, for example the following values 195, 196, 198, 199 have a hole between 196 and 198 so that either 196 or 198 could be tuned with a value of 197.

As illustrated at 8, a new set of modified integer look-up tables is generated and the conversion and comparison steps repeated as indicated at 10 and 11. The process can be repeated a number of times until a stabilized set of integer look-up tables has been generated, however, the inventor has found that performing the conversion and comparison steps twice was sufficient to provide a stabilized set of tables for the RGB to YCrCb conversion.

The invention will be more fully understood from the following explanation of specific examples of the application of the inventive concepts.

The tables generated for converting from RGB to YCrCb in accordance with the CCIR 601 formulas are as follows:

The look-up table values for Cr are based on the value of (R-Y) and is bounded by valid Cr values. The range of the table for valid Cr values is from -179 to +178. The table is as follows:

The look-up table values for Cb is based on the value of (B-Y) and is bounded by valid Cb values. The range of valid Cb values is from -227 to +226. The table is as follows:

The accuracy of the table look-up procedure can be substantially improved if the tables are multiplied by a fixed factor. This procedure then reduces the errors resulting from rounding off the floating point numbers from which the look-up tables are derived. For example, the Red, Green and Blue tables for converting to Y are multiplied by four and after the R, G and B table values are added together the resultant is divided by four and rounded upward if the rounding value is greater than or equal to 0.75. The look-up tables as modified by the fixed factor 4 would be as follows:

Using these tables the Y value for a particular entry point is selected by summing the 4.times.0.299R, 4.times.0.587G and 4.times.0.144B values from the tables and dividing the result by 4 and rounding the result off at 0.75. For example, if the entry point for the R value is 136, the R value from the table would be 4.times.(136.times.0.299)=162, if the entry point for the G value were 212, the G value from the table would be 4.times.(212.times.0.587)=498 and if the entry point for the B value were 36, the B value from the table would be 4.times.(36.times.0.114)=16 where the value for R was 162.656 and is rounded to 162, G was 497.776 and is rounded to 498 and B was 16.416 and is rounded to 16. The sum of the values for R, G and B (162+498+16) is 676 and is then divided by 4 to give a value for Y of 169.

In a similar manner, integer look-up tables for converting from YCrCb to RGB are also constructed in accordance with the CCIR 601 formulas. This conversion from YCrCb to RGB uses four look-up tables. The input to the look-up tables comprises three bytes, one for each of the Y, Cr and Cb components. The output from the tables is three bytes, one for each of the components R, G and B. One look-up table indexed by 1.402(Cr-128) is used to generate R. The R table is constructed as follows:

To obtain the integer value for R, the integer value for Y is added to the look-up result from the R table.

The look-up table for calculating B is indexed by 1.772(Cb-128) and is based on the following table:

To calculate the integer value for B, the value for Y is added to the table value for the corresponding Cr value.

The calculation of the G value requires two look-up tables. The first table is indexed by 0.714(Cr-128) and the second table by 0.344(Cb-128). Also, to improve the accuracy of the conversion (double roundoff error), the G tables are multiplied by a fixed factor. In the preferred imbodiment, the multiplication factor of 2 has provided satisfactory results for the G tables. The tables are as follows:

As with the tables for converting from RGB to Y, the tables for converting from Cr and Cb to G are rounded up if the calculation leaves a decimal remainder of 0.75 or greater and down otherwise.

The G value is calculated by summing the values for the corresponding Cr and Cb values from the above tables, dividing the resulting sum by two and subtracting that value from the corresponding value for Y.

When the complete set of tables for converting RGB to YCrCb and YCrCb to RGB are completed, each of the 256.times.256.times.256=16,777,216 possibilities for every combination of each set of tables are computed. The calculations for each set of tables are performed a plurality of times so as to enable identification of any of the combinations which continue to change as a result of rounding errors occurring during the conversion.

After the round-trip conversion has been performed a plurality of n times, the points within the integer look-up tables that have changed from one conversion to the next are identified. The particular technique used to identify the problem points is to compare the n value of the point to the (n-1) value. When the integer values are found to differ, the integer value in the table is changed either to a next greater or a next lower value depending upon whether the value of the point is increasing or decreasing between conversion cycles (n-1) and (n) and whether the value is moving towards or away from the corresponding precisely calculated floating point value for the original point between conversion cycles (n-1) and (n).

To better illustrate this concept a small portion of the round-trip calculations between RGB and YCrCb is illustrated by the following example and reference to the tables 1 through 9 shown in Appendix A.

Starting with the RGB color point 15, 10, 112, the results of converting between RGB and YCrCB four times follows:

The results clearly indicate the color points are not stable as the G value distorts after the first iteration, which then causes additional distortion at the third iteration of R and B. The distortion from these untuned tables is propagating without any limit. ##STR1##

At this point, after the first conversion, G has moved. R and B are correct, but the movement in G may cause the next calculation of Y to move.

Start the second conversion. ##EQU1##

Now convert YCrCb.sub.2 to RGB.sub.3 ##EQU2##

From the above results, it would appear that the problem point is with the first production of G. We know that G has increased in order for that to occur, either Y is too large (which we know it is not) or the 2GCr+2GCb part is too small.

and because the precision of 2 is added, we must divide by 2

Therefore the table value is probably off in one or both of the tables which makes both a candidate for tuning. If, for example, both positions were tuned:

Then from the first conversion above ##EQU3## and for the next conversion Y is back to its original value

In summary,

2GCr(-6) was tuned to -9 and is now tuned to -8

2GCb(50) was tuned to 34 and is now tuned to 35

This adjustment process is carried out for each problem point in the tables. After each problem point is adjusted, the newly generated set of tables are put through the conversion process again and any changes after n cycles are again noted and adjusted. The process can be repeated the number of times necessary to obtain complete stabilization of the tables.

As each problem point is identified and corrected, the tables become closer and closer to being tuned so that continuous round-trip conversions from one set of tables to the other does not create a change or propagate a distortion in the data value. At this stage, the tables stabilize and the final set of tables can be used to convert an image representation between the YCrCb color space and the RGB color space without any deterioration in the quality of the resulting image. The final set of round-trip tables generated by this described process are shown in Table 10 through Table 18 of Appendix A.

An example conversion from a RGB color point to an YCrCb color point follows using the data from the final tables (10 through 18) starting with a RGB color point of 5, 12, 58. We determine Y from Table 10, the value indexed by R=5 is 6, from Table 11, the value indexed by G=12 is 28, and from Table 12, the value indexed by B=58 is 26. Therefore Y=(6+28+26)/4, or Y=15. Note, division by 4 is required to remove the encoded precision from the table entries.

Next, we determine a value of Cr. To determine the index into Table 13, the value or R-Y must be determined which in this example is 5-15=-10. The value of Cr is determined by starting at the table location 0 point and indexing back to find Cr=121.

Finally, we determine a value of Cb. To determine the index into Table 8, the value B-Y must be determined, which in this example is 58-15=43. The value of Cb is determined by starting at the table location 0 point and indexing forward to find Cb=152.

Therefore for a RGB color point of 5, 12, 58 we have a YCrCb color point of 15, 121, 152. As a check of the results, the actual equations yield the following:

Now, the example will continue the round-trip and convert the YCrCb color point back to the original RGB color point. Continuing with YCrCB of 15, 121, 152 we first determine R. The index into Table 14 is Cr=121. Starting from the table location 0 point, the value from the table is -10. Therefore, R=Y-10=15-10=5. Note with this value there is zero distortion from the resultant round-trip.

Next we determine a value of G. The index into Table 15 is Cr=121 and the index into Table 16 is Cb=152. The respective values from these tables are -10 and 17. Therefore G=Y-(-10)/2-(17)/2=15+5-8=12. Again, note this value has zero distortion from the resultant round-trip.

Finally, we determine a value of B. The index into Table 18 is Cb=152 and the value from the table is 43. Therefore B=Y+43=15+43=58, noting zero distortion from the resultant round-trip.

The conversion process between the RGB color point and the YCrCb color point may be embodied in a computer program. FIG. 2 illustrates a partical data area with a setup and call sequence to complete a pair of color point conversions using the round-trip tables 10 through 18. FIG. 3 illustrates an example subroutine to execute the RGB conversion to YCrCB and FIG. 4 illustrates an example subroutine to execute the YCrCb conversion to RGB.

The tables generated and tuned by the present invention assure reproducible, repeatable results while preserving the color quality of a stored image. In short, the tables minimize divergence of subsequent reproductions of an image from its original stored state and a stable state of the image is reached after a fixed minimal number of conversions. The use of integer value look-up tables also ensures that conversions between RGB and YCrCb can be performed very rapidly. These qualities are very useful in applications such as image editors and image processing systems where image data, compressed in the YCrCb color space, must be translated to the RGB color space before any display screen editing can be performed and then translated back to the YCrCb color space so that the image can be stored in an efficiently and reproducibly compressed state.

While the invention has been described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes can be made to the architecture without departing from the spirit and scope of the invention. Accordingly, the invention shall be limited only as specified in the following claims.