Data reduction is required in data handling processes, where too much data is present for practical applications using the data. Generally speaking, digital images--images that have been discretized in both spatial coordinates and in brightness levels such as those acquired by scanning--are often large, and thus make desirable candidates for at least one form of data reduction. Notably, these digital images do not usually change very much between neighboring pixels, even when the visual appearance of the image varies dramatically throughout its entirety.
It is obviously desired to reproduce color images such that the colors in the copy exactly, or at least closely match the corresponding colors in the original image. Since image input and output devices are often quite different, reproducing an accurate color image often requires some form of color conversion to be applied to the imaging data before it is output. Systems and methods for converting original input device dependent image signals to output device dependent image signals are known to those skilled in the art. Issued U.S. patents which address such techniques include U.S. Pat. No. 5,077,604 to Kivolowitz et al., issued Dec. 31, 1991; U.S. Pat. No. 5,087,126 to Pochieh, issued Feb. 11, 1992; and U.S. Pat. No. 5,528,386 to Rolleston et al., issued Jun. 8, 1996. To one extent or another, each of these prior art systems and methods generally involve applying the input device dependent signals (i.e. RGB) to one or another systems of look-up tables by which they are converted to printer or other output device dependent signals (i.e. CMY or CMYK).
Full color correction in digital images is an image processing operation which typically takes place in two steps. First, each pixel in the image is corrected from 3-D input device dependent (i.e. RGB) or device independent (i.e. YCrCb, R'G'B', XYZ, or L*a*b) color space to a 3-D output device dependent color space (i.e. R"G"B" or CMY). Next, a conversion to CMYK takes place, which may include under-color removal (UCR), gray-component replacement (GCR) and linearization processes. Typically, the two color correction steps are accomplished in a single operation using a three-dimensional look-up table carrying out three-dimensional interpolation such as that described in U.S. Pat. No. 5,581,376 to Harrington. The color correction portion of the process may also be represented as the combination of two phases: a 3-3 color space correction (i.e. RGB-R'G'B') followed by a device-dependent color space transformation operation (i.e. R'G'B'-CMYK for four color devices). Unfortunately, use of the above described full color correction methods in the processing of digital image data requires large amounts of computer resources and use substantial amounts of CPU time. For this reason, color correction is typically applied to some reduced set of data related to the image rather than to the full digital image itself. The ability to separate the color correction process into two steps forms the basis for the present invention, where the more difficult of the two steps, namely the 3-3 color correction, can be performed on a substantially smaller amount of digital data so as to significantly expedite the overall correction process. The advantage is that the 3-3 color space correction operation may be performed on approximately 25% of the previously required information.
The time required for color conversions such as those described above is directly proportional to the amount of data to which it is applied, particularly during the first phase of color correction. More specifically, phase 1 color correction is typically very complex, and is preferably performed on a small number of pixels. The conversion which takes place in phase 2 is much simpler and is may be performed on a large amount of data. Thus, it is desirable in many applications to employ some form of data reduction in order to facilitate rapid processing of image data during phase 1 of the operation. In addition to compression, subsampling schemes are used in scanners, digital copiers or other devices that are used to reproduce, store or process color documents. Briefly, a subsampling scheme involves selecting some subset of the available original image data for subsequent image processing operations. This substantially reduces the volume of data that is subsequently generated and converted during phase 1, preferably with little or no impact on the appearance of the reproduced image.
The present invention may be used to reduce the resources required to reproduce a digital color image. Rather than performing color conversion on all of the pixels in an image, the method disclosed subsamples the image by selecting a subset of pixels for phase 1 color correction. Color values are then assigned to the remaining pixels by interpolation. The interpolation error is then added to the color corrected image, and that image subjected to phase 2 color conversion.
The following disclosures may be relevant to aspects of the present invention:
U.S. Pat. No. 4,275,413 to Sakamoto et al. issued Jun. 23, 1981 discloses a color space transformation where information is placed into lookup tables and stored in a memory--where the lookup table relates input color space to output color space. Sakarioto teaches a "unit cube interpolation unit" having known vertices. The lookup table is commonly a three dimensional table since color is typically defined with three variables.
U.S. Pat. No. 4,887,150 to Chiba et al. issued Dec. 12, 1989, discloses a device for converting RGB image signals first into CMY image signals, and then into CMYK signals. The color converting device includes a divider for dividing the image signals into achromatic and chromatic color components for each picture element; a first converter for converting the chromatic color components so divided into a first color conversion data; a second converter for converting the achromatic color component into a second color conversion data, or into a third color conversion data; an adder for summing the first and second color conversion data to provide the three color printing data, or an output circuit for outputting both the first color conversion data and third color conversion data as the four color printing data.
U.S. Pat. No. 5,187,570 to Hibi et a. issued Feb. 16, 1993, discloses a system for converting color image signals from one type to another, such as RGB to CMY. The system uses linear compression to convert values from one type of color signal to the other. A mono color image outputting system applies a color correction separated color signals in the input section and converts them into recording signals of color material, before outputting a color image. In the mono color outputting system, a gradation property of value data in the input section is linearly compressed to correspond to a gradation property of value data in the output section.
U.S. Pat. No. 5,270,808 to Tanioka issued Dec. 14, 1993, discloses a color image processing method and apparatus therefor, in which the input image data are converted into a color coordinate system represented by luminosity and hue, for example L*a*b* space. The colors reproducible on the output device, for example a printer, are also converted into this coordinate system. An average value is calculated over plural pixels in the vicinity of an object pixel to be digitized, and plural average values are then obtained by including the object pixel selected at each of the reproducible colors. The input image signal is digitized to the closest one of the plural average signals. The digitization error generated upon digitization is distributed to the succeeding pixels with weighted ratios. This method achieves faithful color reproduction, matching the colors reproducible on the recording or display device.
U.S. Pat. No. 5,293,228 to Marti issued Mar. 8, 1994, discloses a method for the coding of images represented by source signals by means of which a luminance signal is formed by linear combination, using positive coefficients of the source signals, and at least one color signal, the luminance and color signals being digitized, sampled at the same resolution, and subjected to a reversible mathematical transformation in the frequency domain.
U.S. Pat. No. 5,483,360 to Rolleston et al. issued Jan. 9, 1996, discloses a method of calibrating a color printer. First the color printer is operated to print color samples on a particular medium. The color samples are then optically measured to determine a colorimetic response of the printing apparatus to the printer signals.
U.S. Pat. No. 5,581,376 to Harrington issued Dec. 3, 1996, teaches the conversion of input device signals Rs, Gs, Bs, generated by an image input terminal, to calorimetric values Rc, Gc, Bc, the calorimetric values being processed to generate address entries into a lookup table to convert them to Cx, Mx, Yx, Kx colorant signals or any multi-dimensional output color space, which includes but is not limited to CMYK or spectral data. Values not directly mapped may be determined using tetrahedral interpolation over a hexagonal lattice where the lattice is formed by offsetting every other row in at least one dimension.
U.S. Pat. No. 5,625,755 to Shu issued Apr. 29, 1997, discloses an image processing method and apparatus which processes image data line by line using an error diffusion or dithering process to generate a halftoned image in which the radius of a dot representing a pixel is/dpi.English Pound.r.English Pound. .sqroot.2/dpi. The method and apparatus selectively performs the halftone process on every other pixel to reduce in consumption and computation time while maintaining a high resolution.
United States Statutory Invention Registration Number H1684, by deQueiroz et al., titled "Fast Preview Processing for JPEG Compressed Images", issued Oct. 7, 1997, assigned to the assignee of the present invention, discloses a method of rapidly decompressing a document image compressed using transform coding for scaling and previewing purposes. A fast algorithm is derived by utilizing a fraction of all available transform coefficients representing the image. The method is particularly efficient using the discrete cosine transform which is used in the JPEG ADCT algorithm. In JPEG ADCT, a very fast and efficient implementation is derived for a resolution reduction factor of 16 to 1 (4 to 1 in each direction) without needing any floating point arithmetic operations.
Pending U.S. patent application Ser. No. 08/721,130 by deQueiroz, titled "Method and Apparatus for Processing of a JPEG Compressed Image", filed Sep. 26, 1996, and assigned to the assignee of the present invention, discloses a method and apparatus for processing images that have been compressed using a discrete cosine transform operation, and particularly JPEG compressed images. The rotation of image blocks is accomplished by sign inversion and transposition operations to accomplish intrablock operations. Subsequently, one of a number of alternative methods is employed to accomplish the same image processing on an interblock level, thereby enabling the rotation or mirroring of compressed images.
Pending U.S. patent application Ser. No. 08/770,765 by Klassen et al., titled "Color Correction of a Compressed Image", filed Dec. 19, 1996, and assigned to the assignee of the present invention, discloses a method for color correcting digital images that have been compressed. Aspects of the color correction are carried out on the compressed image data to improve computational efficiency. One of a number of alternative methods is employed to accomplish the color correction on lossy or losslessly compressed images. A second, simplified phase of the color correction may be applied subsequently to the decompressed image data in certain embodiments.
Pending U.S. patent application Ser. No. 08/770,768 by deQueiroz et al., titled "Multiresolution Color Correction Using Wavelet Transforms", filed Dec. 19, 1996, and assigned to the assignee of the present invention, discloses a color correction method which includes decomposing the original image into sub bands, applying the application to one or more sub bands and then recomposing the image, prior to color correction and color space transformation. The color correction may be applied to one of the lower resolution sub bands and a simpler color space transformation to the final image as a way to reduce the amount of computation.
Pending U.S. patent application Ser. Nos. 09/004,295 and 09/004,650 by Klassen et al., both titled "Method of Correcting Luminance and Chrominance Data in Digital Color Images", filed Jan. 8, 1998, and assigned to the assignee of the present invention, disclose methods and apparatus' for improving the efficiency of color correcting subsampled luminance and chrominance based data. More specifically, the inventions are directed to applying a full conversion between color spaces for one pixel in a selected pixel block. Chrominance values are assigned to the remaining pixels based upon their luminance values relative to the luminance value of the converted pixel.
All of the references cited herein ire incorporated by reference for their teachings.
Accordingly, although known apparatus and processes are suitable for their intended purposes, a need remains for a method and apparatus for converting color signals of a first type to equivalent color signals of a second type, wherein the color signals have been derived from an image that has a plurality of pixels arranged in two-dimensional space.