A CACHING SYSTEM FOR INTERPOLATION PROCESSING
Technical Field
The present invention relates to the interpolation of data values, and, more particularly, to the use of a cache memory in association with data interpolation processing.
Background
In an imaging system having color graphics, it is desirable to display color images on many types of devices such as computer display screens and printers. Due to inherent differences between display devices, color image data that represents a certain color in one device may not correspond to the same color when displayed on another device. These differences are due, at least in part, to characteristics of elements such as the inks that are used in ink-jet printers and the phosphors that are used in CRT monitors to produce a visible image.
Similarly, characteristics of color toners and the electrophotographic process play a role in determining what the output of a color laser printer looks like. A display device such as a monitor may utilize an RGB color space, in which each color is defined in terms of its red, green, and blue components, whereas another device such as a printer may employ a different color space to define colors, such as CMYK in which a color is represented in terms of cyan, magenta, yellow and black components. To ensure consistent color reproduction between devices, it is often necessary to modify, or translate, color data when transmitting it between devices. There are several methods in which this is presently done and, in general, most methods include the use of a color look-up table (LUT).
The color LUT functions to translate color data corresponding to a first I/O device (a source device) to color data corresponding to a second I/O device (a destination device). The LUT stores color values corresponding to the destination device and functions such that when it is indexed, according to source device color image values, it outputs translated color image data values which provide accurate reproduction of the source device color in the destination device. Color image data in a LUT can be graphically represented as an N- dimensional geometric structure, where each dimension (or axis) of a space defined thereby corresponds to one component of an input color value. Hence, a graphical representation may portray a color space defined by N axes disposed in N dimensions. Each axis in a graphical representation may correspond to values associated with a particular range of color values stored in a LUT. For example, the graphical representation may correspond to a three-dimensional lattice structure, or cubic color space, wherein values associated with three color attributes, such as red, green and blue (RGB), each correspond to one of the three axes.
Because the number of colors in an entire color gamut is greater than that which can be reasonably stored in a color transformation LUT, a LUT's entire color range may be represented by sampled increments, or indexed, in discrete values. The LUT is accessed according to index data corresponding to the discrete values which are close to exact input values. A number of related discrete output values are produced by the LUT are then interpolated to arrive at the final derived result.
Interpolation processing involves the use of calculations based on geometry to determine output values for reliable color reproduction of source device color on a destination device. The objective of the interpolation process is to approximate a color translation transfer function for each represented color. For example, where a source device is a video display, and a destination device is a printer, interpolation may operate by taking color image data values for individual pixels from the video display and applying a known transform to determine corresponding color image data values in a device-independent color space, such as the CIE-standard ABC color space. These device- independent values are then further translated into the color space of the printer to provide accurate color reproduction of the pixel in a printed point on the printer.
In a color translation processing system which utilizes a color translation LUT to transform color image data, the LUT data is typically stored in the main memory of a computer or printer. Main memory is typically implemented with dynamic random-access memory (DRAM). While inexpensive, this type of memory is relatively slow for the purposes of color translation processing. Cumulatively, the repeated accessing of main memory, in order to access LUT data, results in slow output processing. To alleviate this problem, conventional color data processing systems may store entire color translation LUTs in an associated high speed memory, which usually consists of a high speed static random access memory (SRAM). While offering much faster access to the data values in the LUT, the trade-off in using SRAM is that it is very expensive. Large, high-speed color printers, which use SRAM to provide real-time interpolation of LUT data values, are extremely expensive. Summary
To address the foregoing limiations associated with prior art systems, the present invention provides methods in accordance with independent claims 1, 3, and 4, an apparatus in accordance with independent claims 6 and 10, and a system in accordance with independent claim 8. Further advantageous features, aspects and details of the invention are set forth in the dependent claims, the following description and the drawings. The claims are to be understood as a first non-limiting approach of defining the invention in general terms. In one embodiment of the invention, the interpolation process is employed to translate color image data generated in a source device for use in a destination device. A system which incorporates the present invention stores data values in a cache, which define a color unit subspace that surrounds a point to be interpolated, and performs multi-dimensional interpolation in accordance with this space. In accordance with one aspect of the invention, the cache memory is preferably a single-entry cache, i.e. it stores a single tagged entry that contains the minimal set of parameters needed to define a destination device color subspace for interpolation. The stored subspace is interpolated in concert with input image data, to produce output values for accurate reproduction of input image color on the destination device.
In one aspect of the present invention, the LUT contents are stored in a main memory, such as a DRAM, and only those data values in the LUT corresponding to a source device subspace region surrounding a data point under consideration are loaded into cache memory for interpolation processing. Hence, the cache requirements are significantly reduced, while interpolation processing efficiency and speed are maintained. Corresponding cost savings are realized by the reduced requirement for cache memory, because only that amount of high speed memory sufficient to store data which corresponds to the unit subspace of the source device is required to carry out the color translation. Brief Description of the Drawings
Other features and advantages of the invention will become readily apparent from the drawings and detailed description set out below.
Figure 1 depicts a conventional image processing system having a display device and a printer.
Figure 2 depicts an image upon which the present invention might operate.
Figure 3 depicts a graphically represented color space having a unit subspace which has single integer dimensions and surrounds an image point to be processed.
Figure 4 depicts an image processing arrangement incorporating the invention.
Detailed Description To facilitate an understanding of the present invention, it is described hereinafter with reference to its implementation in a color imaging system of the type where image data is converted from one color space to another color space, and wherein the data is interpolated as part of the conversion. This particular example is one which can employ the principles of the invention to achieve significant gains in image processing time with minimal expense. It will be appreciated, however, that this embodiment is not the only practical application of the invention. Rather, it can be successfully employed in any environment where interpolation of a large number of data values is carried out, particularly where successive data values do not differ from one another by an appreciable amount.
Figure 1 depicts a conventional color imaging system 20 having a CPU 22, a display monitor 26, and a printer 24. The CPU 22 has an interpolation processor 28 with an attached SRAM memory 30 for storing a look-up table that is used to convert source device color data into device-independent color data. The printer 24 may be a high speed color printer, and contain a color processing circuit 32 with an associated SRAM memory 34 which stores the contents of another LUT for converting device-independent color values into corresponding color values for the printer. Operation of the system 20 for transformation of a color image appearing on the display 26 into color data values for the printer 24 might proceed as follows. After entering into a print mode, the interpolation processor 28 utilizes the color transformation LUT stored in its associated memory 30 to transform image data corresponding to the display 26 into device-independent color data, which is transmitted to the printer. Within the printer, the color processing circuit 32 accesses the SRAM memory 34 for LUT data to perform color translation processing of the received image data into its color space. Provision of the large SRAM memory 34 enhances color processing speed and printer output speed. However, the cost of the printer 24 can be significant due to the presence of this high-speed memory.
An exemplary embodiment of an imaging system incorporating the present invention is described below with reference to Figures 2-4. The following description corresponds to an exemplary color translation scenario wherein a source device consists of a video monitor and a destination device consists of a color printer. In the example described, input image data can be graphically represented in three-dimensions and corresponds to display pixel color values for red, green, and blue (RGB) content. Output image data also is three-dimensional and corresponds to printed pixel color values for a device- independent color space, e.g., Cie-based ABC, or to cyan, magenta, and yellow components in a CMY color space. It will be appreciated, however, that the invention is applicable to interpolation systems in which the input data and the output data can have any number of components, and that the number of components in the input data need not be the same as the number of components in the output data.
Figure 2 depicts an exemplary image upon which image processing in accordance with the invention might be employed. This image depicts an outdoor scene with mountains in the background. As seen in the figure, an image can comprise large regions in which the color data may be substantially similar between adjacent image points, such as a blue sky 36. Hence, color data for contiguous picture elements, or pixels, 38 in such a region varies only slightly. A system incorporating the invention exploits this phenomenon by using fast memory, e.g. cache memory, to maintain those portions of a color transformation LUT corresponding to a source color space region surrounding an image data point undergoing processing. When processing color data for such an input data point 38, there is a high likelihood that the LUT data values needed to interpolate that color data will be the same as those needed to process the immediately preceding input data point. Thus, an arrangement in accordance with the invention utilizes the data corresponding to a preceding input data point to avoid accessing the LUT from the slower main memory.
Figure 3 depicts a three-dimensional color space 39 where the X, Y, and Z axes may represent, for example, RGB, CIE-based ABC or CMY values. The color space data can be stored in a LUT. As discussed above, LUTs typically do not contain every value in a color gamut because to do so would consume inordinate amounts of memory. Instead, the range of colors is represented by samples of discrete values shown by the index markings 40 on each of the X, Y, and Z axes. An input image point 42 corresponds to a display value for a given pixel on a video display. The point 42 resides within the source color space. In the depicted example, the X, Y, and Z values for the point 42 are approximately 3.7, 4.4, and 3.6, respectively. These are the input image values.
In a method incorporating the present invention, a determination is made to define a unit subspace, within the source color space, which surrounds the source input image point 42. In the present three-dimensional example, this unit subspace is depicted as a cube 44 which is defined by eight data points. For other geometries, the unit subspace may have a different shape which is defined by a different number of data points. The unit subspace is determined by pairs of adjacent discrete index values on each axis, between which the input data point falls. Hence, the X dimension of the unit subspace is defined by the single unit between discrete X values 3 and 4, the Y dimension of the unit subspace is defined by the single unit between discrete Y values 4 and 5, and the Z dimension of the unit subspace is defined by the single unit between discrete Z values 3 and 4. Each of the eight corners of the unit subspace cube 44 represents a boundary point which defines the subspace. The unit subspace boundary points are used to index a transformation LUT which contains corresponding output data for a destination color space. In the present example, where the destination device operates in a CMY color space, each data point on the cube 44 might contain corresponding component values for cyan, magenta and yellow. Of course, the destination device may employ a different color space such as CMYK, in which case the LUT output contains additional information corresponding to K (black) component values. These corresponding component values of the destination device color space are stored in a cache memory. The output image data point for the destination device falls within these stored values.
A conventional cache memory is organized to include a number of cache entries, where each cache entry includes cache data and an address tag. In the context of the present invention, the data held in the cache is selected LUT entries from main memory for a unit subspace. The address tag indicates an address in main memory where the contents of the cache is stored. Whenever a processing unit or I/O device initiates a memory access, the address of the desired data is sent to the cache. The cache compares the address with all of its address tags to see if it presently contains a copy of the data. If it does contain the data, it reads the data from its own high speed RAM and delivers it to the processing unit or I/O device. This is termed a "cache hit," and is usually much faster than reading the same data directly from main memory. If the cache does not contain the data, however, a cache miss occurs and the cache system fetches the data at the corresponding address in the main memory and provides it to the processing unit.
In a system in accordance with a preferred implementation of the present invention, the cache memory is a single-entry cache. That is, the cache need only have the capacity required to store a unit subspace of the input data. In the present example, where a three-dimensional source color space is involved, the cache stores all of the color component values at each of the eight data points that correspond to the respective boundary points of the cube. In a preferred embodiment, a cache hit is determined by examining a point which constitutes an origin of the source unit subspace. In the above-described example, the origin of the source unit subspace is the point (3,4,3) (see Figure 3). In practice, this is done by first determining the origin of a unit subspace for an input image pixel and making a comparison to see if this unit subspace origin is equal to the origin point of the unit subspace of the preceding input image pixel. If equal, the system uses the destination color space data already stored in the cache. If not equal, the remainder of the unit subspace boundary values are determined for the input data point, and the LUT is indexed accordingly, to obtain new unit subspace values. Alternate techniques for determination of whether cache data is appropriate for subsequent processing may be utilized in order to achieve a desired result. Once the appropriate set of data points has been retrieved from the LUT, they are interpolated to determine the final value for the pixel in the destination device. For example, in the above-described example, the fractional portions of the RGB input image values (.7, .4, and .6) can be used for interpolation processing to determine the corresponding CMY output values within the destination device color space. The interpolation process itself is known, and therefore is not described in detail herein.
After processing is performed for a given source device input image pixel, the next source device pixel is selected, and a determination is made whether that pixel's image data values fall within the unit subspace data already stored in the cache. If a cache hit results, the cache data is used by the interpolator for interpolation processing of the pixel's input values. Otherwise, the main memory is accessed to obtain a different set of data values from the LUT. Figure 4 shows a diagram of a computer system 12 incorporating the present invention. The system 12 includes a CPU 14, a display 15, and a printer 5. In a preferred embodiment, color transformation processing is handled by a color interpolation processor 9 which may be located in the printer 5, or within the CPU 14, or in a separate device 19 located between the printer 5 and the CPU 14. The color interpolation processor may, for example, be an application specific integrated circuit (ASIC). The color interpolation processor includes a cache memory 11 which may be provided within the color processor 9, or as a separate device 17. Input image data is provided to the interpolation processor 9. A determination is made whether input image data received by the interpolation processor 9 corresponds to subspace data presently stored in the cache memory 11. If so, processing of the input image data is performed from the information in the cache. If not, the LUT 13 in the main-memory 7 is accessed to fetch the necessary data for a source data subspace corresponding to the new input image data. The interpolation processor 9 performs interpolation processing based upon the newly retrieved data, and stores it in the cache memory 11.
The foregoing description relates to an example in which both the input and output data are three-dimensional. It should be noted that the input and output data may have any number of dimensions, and that the number of dimensions of input data may not necessarily be equal to the number of dimensions of the output data. It should further be appreciated that, while described with respect to color processing, the invention may be applied to interpolation processing of other image attributes such as grayscale, half tones, hues, and shading.
In the exemplary embodiment that is directed to the processing of image data, the cache contains a single entry which comprises a unit subspace of the source color space. In this particular application, the properties of images, where a large number of successive data points may have values which are the same as, or close to, one another, enables high processing throughput to be achieved with a minimal size cache. For other applications, it will be appreciated that a larger cache which stores multiple subspace entries, or data points for a subspace which is larger than a unit subspace, can be used.
Further in this regard, while the invention is particularly suited to the interpolation of image data, it is not limited thereto. Rather, it is applicable to any type of system in which successive data values that may not differ significantly from one another are to be processed. Although the invention has been described and depicted with respect to Figures 1 through 4, those skilled in the art will appreciate and understand that several variations of the invention, as described, may be made without departing from the scope and spirit of the present invention as set forth in the following claims.