Abstract:
An apparatus and method for converting an input image with a plurality of pixels to an output image using an N-dimensional conversion table with a plurality of nodes. The apparatus has a set of RAMS for storing odd-indexed nodes and even-indexed nodes for each dimension of the N-dimensional table. The apparatus also has means for retrieving for each pixel a set of output color values corresponding to nodes adjacent to the pixel in the conversion table. Finally, the apparatus has means for interpolating within each set of output color values to produce the output image.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The invention relates in general to image processing. More particularly, this invention relates to a method and apparatus that accelerates color space conversion by employing a multi-dimensional and multi-port memory.  
         [0003]     2. Description of the Related Art  
         [0004]     Color Copiers or other imaging devices capture an image from an input device and attempt to create a suitable duplicate on an output device.  
         [0005]     The input device has inherent properties and characteristics with regard to the sensing process in a document. An example of an input device is a Charged Coupled Device (“CCD”) scanner. A CCD sensor is typically composed of three sensors for each pixel to be sensed. Each of the three sensors responds to a different wavelength of light. Typically, the wavelengths are close to Red, Green and Blue (RGB).  
         [0006]     The output device has inherent characteristics with regard to the process of creating an image. One such example is a color laser printer. The output device typically creates an image using four different colors, i.e. Cyan, Magenta, Yellow and Black (CMYK).  
         [0007]     Color Management is defined as the task of accurately converting color information of one form or space to that of another space. This might be compared to the way that points in space or in a graph can be converted from a Euclidean space to a Spherical or other coordinate system.  
         [0008]     The classical “textbook” method for converting color from one representation to another is by matrix multiplication. A three-component (e.g. RGB) element is multiplied by 3×3 matrix to generate a value in the new space. Industry standards exist for these matrices, such as those used in color television or JPEG compression.  
         [0009]     The matrix-multiplication method demands that the conversion process be rather ordinary, in that the three-dimensional surface generated is continuous and without irregularities. For best results, one might desire that a different 3×3 matrix value set be used to convert various regions of the input color space. This is rather cumbersome, and the typical implementation is by table lookup.  
         [0010]     The lookup process uses a table, usually implemented in memory such as SRAM or DRAM, that provides an output value for every input value. However, such a method requires a large amount of memory. For example, table-based color space conversion from RGB to CMYK would ideally translate every incoming 24-bit RGB value to a unique CMYK value. This would require a table with 16 million entries of 32 bits, or 64 MB of memory.  
         [0011]     Due to practical limits on the size of the memory that can be used to store the color lookup table, only discrete data points, or nodes, are stored in the color lookup table. As a result, it is often necessary to interpolate between a set nodes adjacent to a given image color to determine the desired output color for a destination device.  
         [0012]     Typically, the adjacent nodes are separately accessed from the lookup table, thus requiring multiple accesses to memory. For example, in the three-dimensional RGB input space, a set of eight nodes forming a cube around a color pixel must be accessed. This proves to be inefficient, given the plurality of pixels in input images.  
         [0013]     Therefore, the need arises for an image processing device that allows for a single access of memory for interpolation of data points, thereby expediting input image conversion.  
         [0014]     In U.S. Pat. No. 6,246,396, Gibson discloses an apparatus for converting an input image in an input color space to an output image in an output color space. Gibson does not interleave memory by placing odd and even indices into separate lookup tables. The subject invention separates odd and even indices for all three dimensions, resulting in eight separate lookup tables.  
       SUMMARY OF THE INVENTION  
       [0015]     Accordingly, one object of the present invention is to provide an image processing device that expedites color space conversion.  
         [0016]     A second object of the invention is to provide an image processing device that allows for a single access of memory for interpolation of data points.  
         [0017]     A third object of the invention is to provide an image processing device color space conversion in multiple dimensions.  
         [0018]     A fourth object of the invention is to provide an image processing device color space conversion using multiple ports.  
         [0019]     To achieve these and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention provides an apparatus and method for converting an input image with a plurality of pixels to an output image using an N-dimensional conversion table with a plurality of nodes. The apparatus has a set of RAMS for storing odd-indexed nodes and even-indexed nodes for each dimension of the N-dimensional table. The apparatus also has means for retrieving for each pixel a set of output color values corresponding to nodes adjacent to the pixel in the conversion table. Finally, the apparatus has means for interpolating within each set of output color values to produce the output image. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0020]      FIG. 1  is a graphical depiction of a prior art lookup table in three-dimensions.  
         [0021]      FIG. 2  is a graphical depiction of a three-dimensional lookup table separating odd and even indices along the X-axis.  
         [0022]      FIG. 3  is a graphical depiction of a three-dimensional lookup table in accordance with the present invention.  
         [0023]      FIG. 4  is a diagram illustrating address increment hardware for the present invention.  
         [0024]      FIG. 5  is a graphical depiction of the distribution of RAMS within a three-dimensional lookup table for the present invention.  
         [0025]      FIG. 6  is a diagram illustrating the hardware configuration for the lookup table of  FIG. 5 . 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0026]     Referring now to  FIG. 1 , a graphical depiction of a prior art lookup table in three-dimensions is shown. The three-dimensional lookup table can be envisioned as a cube  10  containing nodes  11  at predetermined addresses along the X, Y and Z axes.  
         [0027]     Still referring to  FIG. 1 , an input color  12  contains address components X 1 , Y 1  and Z 1 . Typically, input color  12  will not coincide exactly with the predetermined address of a node. Therefore, address components X 1 , Y 1  and Z 1  are used to determine 8 vertices V 1  thru V 8  adjacent to input color  12 . Vertices V 1  thru V 8  all fall within a cube. Given the index coordinate of (x,y,z), for example, the following locations will be read: (x,y,z), (x,y+1,z), (x,y,z+1), (x,y+1,z+1), (x+1,y,z), (x+1,y+1,z), (x+1,y,z+1) and (x+1,y+1,z+1). An output value corresponding to input color  12  is approximated by interpolation of vertices V 1  thru V 8 .  
         [0028]     Still referring to  FIG. 1 , obtaining an output value for input color  12  requires separately accessing vertices V 1  thru V 8 . This is because the lookup table is implemented on a single SRAM. Because a single memory bank is used, 8 separate accesses to memory are necessary to process every pixel in a given input image. This proves to be an inefficient process for color space conversion.  
         [0029]     With reference to  FIG. 2 , a graphical depiction of a three-dimensional lookup table separating odd and even indices along the X-axis is shown. In this embodiment, each half of the lookup table  20  is implemented on a separate SRAM. By dividing the lookup table  20  into two pieces  21  and  22 , vertices V 1  thru V 4  can be accessed at the same time as vertices V 5  thru V 8 . All 8 vertices need not be separately accessed from memory. Instead, 2 groups, each containing 4 nodes, can be simultaneously accessed from their respective SRAM. This procedure cuts the time to access the 8 nodes surrounding input color  12  in half.  
         [0030]     Referring now to  FIG. 3 , a graphical depiction of a three-dimensional lookup table in accordance with the present invention is shown. The lookup table separates odd and even indices along the X-axis, Y-axis and Z-axis. In this embodiment, each of the eight portions of the lookup table is implemented on a separate SRAM. By dividing the lookup table into cubes  31  thru  38 , vertices V 1  thru V 8  corresponding to input color  12  can be accessed at the same time. Instead of performing separate accesses to memory for each these vertices, all output values of the vertices are simultaneously obtained.  
         [0031]     With reference to  FIG. 4 , a diagram illustrating address increment hardware for the present invention is shown. For purposes of this example, a 1-dimensional table with 17 elements will be used. The index into the table is a five-bit number with valid values from binary 00000b to 10000b, or from 0 to 16 inclusive. Given an algorithm that requires simultaneous access to two table elements at indices (or addresses) of n and n+1, the table is split into two separate tables with one containing the contents of all the even addresses and another containing all of the odd addresses. When the index into the table is even (e.g. 0, 2, 4 . . . ) then the index of 000b (the three most significant bits of the index value) into each table will in fact retrieve the values from addresses 00000b and 00001b from the original table.  
         [0032]     Still referring to  FIG. 4 , when the index is an odd value, then the even table address needs to be incremented. For example, if the 4 most significant bits of the input color are 0101b, then locations 0101b and 0110b will be accessed from the original un-split table. In the split table arrangement, only the 3 most significant bits of the input color are used, so the input address would be 010b. At address 0010, values of 4 and 5 will be retrieved, but the subsequent value from the even table is needed. Hence when the four most significant bits of the input color are odd, the address to the even table must be incremented in order to retrieve the desired values from entries n and n+1 of the original, un-split table. This concept must be extended to all three dimensions.  
         [0033]     Referring now to  FIG. 5 , a graphical depiction illustrating the distribution of RAMS within a three-dimensional lookup table for the present invention is shown. This embodiment shows a 17×17×17 lookup table formed as a cube  50 . The lookup table is composed of a 16×16×16 core  51  implemented in 8 RAMS.  
         [0034]     Still referring to  FIG. 5 , faces  52  thru  54 , edges  55  thru  57  and corner  58  form a skin around core  51 . Faces  52  thru  54  are 1×16×16 each, edges  55  thru  57  are 1×1×16 each, and corner  58  is 1×1×1. Faces  52  thru  54 , edges  55  thru  57  and corner  58  are implemented on RAMS separate from the core. Like the core, the additional RAMS are implemented by separating odd and even indices in the appropriate number of dimensions. This allows for simultaneous access of vertices V 1  thru V 8  for input color  12 .  
         [0035]     With reference to  FIG. 6 , a diagram illustrating the hardware for lookup table of  FIG. 5  is shown. For purposes of this embodiment, 24-bit incoming color data will be used. Only the four most significant bits of each color component are used to index into the table, and the lower four bits will be used for a three-dimensional interpolation within the 8 value cube that is supplied by the table.  
         [0036]     Still referring to  FIG. 6 , index values 0 thru 14 within the 4-bit range of 0 thru 15 will only access the inner 8 RAMS, i.e. RAMS 0 thru 7. The inner 8 RAMS represent core  50  in  FIG. 5 . When any of the color components equals 15, some components will be retrieved from the outer 8 RAMS, i.e. RAMS 8 thru 15. The outer 8 RAMS represent faces  52  thru  54 , edges  55  thru  57  and corner  58  in  FIG. 5 .  
         [0037]     Still referring to  FIG. 6 , hardware  60  includes address generation logic  61  for accessing RAMS 0 thru 15. Address generation logic  61  determines which points of the eight vertices of the cube will come from which RAMS.  
         [0038]     Other embodiments of the invention will appear to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples to be considered as exemplary only, with a true scope and spirit of the invention being indicated by the following claims.