Image analysis – Color image processing – Color correction
Reexamination Certificate
1999-05-17
2002-05-14
Au, Amelia M. (Department: 2623)
Image analysis
Color image processing
Color correction
C358S518000, C358S525000
Reexamination Certificate
active
06389161
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention is in the field of electronic production technology and is directed to a method for interpolation of color values for color space transformation from an input color space into an output color space.
In reproduction technology, print masters for printed pages are produced that contain all elements to be printed such as texts, graphics and images. In the case of electronic production of print masters, these elements are present in the form of digital data. The data for an image are generated, for example, in that the image is scanned point-by-point and line-by-line in a scanner, each picture element is resolved into color components, and the color components are digitized. Usually, images are resolved into the color components red, green and blue (RGB) in a scanner, i.e. into the components of a three-dimensional color space. However, other color components are required for color printing. These are the inks cyan, magenta, yellow and black (C, M, Y, K) given four-color printing, i.e. the components of a four-dimensional color space. In special instances such as packaging printing, even more inks can be added, for example gold, silver, chocolate brown, etc. For prints with especially high quality (high fidelity printing), for example, seven inks are employed (C, M, Y, K, R, G, B), i.e. the image data must be transformed into a seven-dimensional color space.
Such color space transformations are required in reproduction technology because there are different color spaces for different devices such as scanner, monitor, proof output, printing machine, etc., these different color spaces respectively optimally describing the color properties of the device. All devices have their limitations and special characteristics in the presentation of the colors, and all devices have properties of this type that are different. The color components of the various color spaces are allocated to one another with a color space transformation, so that, for example, RGB color values that a scanner identified are transformed into the CMYK color values of a printing process so that the print has the same colors as the image original.
Such an allocation can be realized with the assistance of a table memory (lookup table). When, for example, RGB color values are to be transformed into CMYK color values, the table memory must have a memory location for every possible value combination of the RGB color components, the allocated CMYK color components being stored therein. An RGB image is then transformed into the CMYK color space in that the RGB color values of every picture element are applied to the table memory as an address and the allocated CMYK color values are read out. This simple allocation method, however, has the disadvantage that the table memory can be very large and, thus, expensive. When each of the RGB components was digitized with eight bits, i.e. has 2
8
=256 density levels, there are 256
3
=16,777,216 possible value combinations of the RGB color components. The table memory must thus have 16,777,216 memory cells, each with a 4-byte word length (one respective byte for C, M, Y, K). The table memory thus becomes 64 M bytes large.
In order to reduce the size of the table memory, the prior art utilizes a combination of table memory and interpolation method for realizing a color space transformation. The allocations for all possible value combinations of the input color components are then not stored in the table memory; rather, only those for a coarser, regular grid of values in the input color space. The grid is formed in that only every k
th
value is taken as a grid point in every component direction. For the example of the RGB color space and for k=8, thus, every eighth value of the 256 possible values is taken in every components as grid point. The grid, accordingly, has 256/8=32 grid points in each component direction, i.e. 32×32×32=32,768 grid points for the entire color space. The allocated components of the output color space (for example, CMYK) are stored in the table memory as supporting values for every grid point. The output values are interpolated from the neighboring supporting values for input color values that lie between the grid points.
The interpolation methods for the color space transformation known from the prior art are usually limited to three-dimensional input color spaces such as, for example, the RGB color space. They cannot be applied to a four-dimensional or multi-dimensional input color space such as, for example, the CMYK color space or the seven-dimensional CMYKRGB color space or, given an expansion to more than three dimensions, they require a great deal more expense or, respectively, calculating time. In European published application 0 487 304, all eight corner points of a sub-cube in the three-dimensional L*a*b* color space are employed for the interpolation. In European published application 0 615 379, the color values are likewise interpolated from all eight corner points of a sub-space in the RGB color space, whereby the grid points, however, are not equidistant, i.e. the sub-space is not cube-shaped.
In German Letters Patent 28 13 519, the cube-shaped sub-space is divided into 5, 6 or 24 tetrahedrons, the tetrahedron in which the point P should lie is determined from the spacings of the point P to be interpolated from the sides of the sub-cube, and the color value is then interpolated from the four corner points of this tetrahedron.
In German Published Application 42 34 985, the sub-cube of the three-dimensional input color space is likewise divided into six tetrahedrons and the four corner points of a tetrahedron are then interpolated.
In U.S. Pat. No. 5,428,465, each sub-cube in the RGB color space is divided by a diagonal parting plane into two prisms each having six corner points, and the color values in the inside of a prism are interpolated from the six corner points. In the same way, the sub-cubes of a three-dimensional color space with a luminance component and two color difference components are divided in U.S. Pat. No. 5,504,821 into two prisms each having 6 corner points and the color values within a prism are interpolated from all 6 corner points.
In GB Published Application 2 053 619, the sub-cubes are divided into three pyramids with respectively 5 corner points and the color values within a pyramid are interpolated from the corner points.
In U.S. Pat. No. 5,313,314, a four-dimensional “sub-cube” having 16 corner points is divided into 24 sub-members each having five corner points, and the five corner points of the sub-member are then interpolated.
In European Letters Patent 0 533 712, a general transformation from an n-dimensional into an m-dimensional color space is disclosed, whereby the components of the input color space are imaged by pre-processing onto a three-dimensional color space, and the general n-dimensional transformation is thus reduced to a three-dimensional transformation.
The majority of known interpolation methods for color space transformation are limited to a three-dimensional input color space in that a sub-cube is divided into a plurality of sub-members. To that end, the components of a color value to be interpolated are divided into multiples of the edge length of a sub-cube and remainders. As a rule, a plurality of more significant bits indicates the multiple values and the remaining, low significance bits indicate the remainders. The multiple values of the components indicate in which sub-cube the color value to be interpolated lies. The remainders indicate further in which sub-member of the sub-cube the color value to be interpolated lies. A determination of the sub-member in which the point P to be interpolated lies is made by extensive comparison operation of the low-significant bits, the corner points of the sub-member are determined by an address calculation, and the corresponding supporting values are taken from a three-dimensional grid table memory and are interpolated. The methods are involved and involve a great number
Au Amelia M.
Wu Jingge
LandOfFree
Method of interpolation in an n-dimensional color space does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of interpolation in an n-dimensional color space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of interpolation in an n-dimensional color space will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2880017