Image analysis – Color image processing
Reexamination Certificate
1999-12-07
2003-09-09
Wu, Jingge (Department: 2623)
Image analysis
Color image processing
C345S604000
Reexamination Certificate
active
06618500
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention relates to digital image processing and display. More particularly, this invention relates to the quantization of digital color images.
2. Description of Related Art
Raster images are typically composed of a plurality of individual pixels, each pixel having a particular color and location associated with it. The color of the pixel can be expressed in terms of the intensities of three color variables in a color model. Representative color model systems include RGB (red, green, and blue), CMY (cyan, magenta, and yellow), YIQ (“Y” representing luminance and “I” and “Q” representing chromaticity), HSV (hue, saturation, and value), also known as HSB (hue, saturation, and brightness), and HLS (hue, lightness, and saturation).
Using the RGB color model as an example, by defining colors in terms of their red, green, and blue components, all of the colors in the spectrum can be represented as points in a three-dimensional color cube, each axis representing one of the three primary colors. The intensity of each color component is normalized to a value between zero and one, zero indicating the complete absence of that component and one indicating full saturation. In a 24-bit true color image, the intensity for each RGB component is stored as an eight bit value, which provides 256 different intensity levels for each primary color, for a total of 2
24
(over 16 million) colors. Each of these unique colors can be plotted as discrete locations on the three-dimensional color cube.
It is often desirable to reduce the total number of colors in an image in a process known as color quantization, which enables the color information from a true color image to be conveyed with fewer bits than that used for the original image. In a typical quantization, all of the colors in a true color image are mapped to a color palette, or color look up table (CLUT), wherein each of the 2
24
unique colors are mapped to one of the colors in the CLUT. In one form, the CLUT includes 256 unique colors. Using such a color palette, the CLUT's 256 colors are indexed using integer numbers ranging from zero to 255. All of the colors actually present within a true color image are mapped to one of the 256 colors in the CLUT, which allows the colors from the true color image to be stored using only eight bits per pixel. While some color resolution may be lost during the quantization process, careful selection of the colors to be represented in the palette can minimize the impact on final image quality. For example, an analysis of the colors present in an image can be used to create an adaptive palette, which is a palette for which the selected colors to be used for quantization of an image are tuned to that particular image.
One method for selecting the colors in the CLUT is known as the popularity algorithm. This method determines which colors that appear most often in the image, and these colors are chosen as the entries for the CLUT. After the CLUT entries are chosen, each of the unique colors in the original image is mapped to one of the colors selected as a CLUT color entry. Ideally, each unique color should be mapped to the CLUT entry nearest to that unique color on the three-dimensional color cube, which would provide the closest approximation of that unique color. However, computing the absolute Cartesian distances between each unique color as mapped on the color cube and each of the CLUT entries for each individual pixel requires significant computational processing and large amounts of memory. There has not heretofore been proposed an efficient method for mapping pixels to the nearest CLUT entry.
To determine which CLUT entry to associate with each pixel, a method known as the median-cut algorithm has been used. Using this method, the three-dimensional color cube is divided such that each CLUT color entry represents an equal number of pixels in the image. This is accomplished by creating a histogram of color values for each axis, and dividing the cube at the centers of this histogram using a plane orthogonal to that axis such that equal numbers of pixels remain on either side of the plane. This process is repeated for each axis until the color cube is divided into enough volumes to fill the CLUT. A CLUT entry is then assigned to each volume by computing the average of all the pixel values in that volume. Then, when quantizing the image, each pixel is mapped to the CLUT entry for the volume in which that pixel is located, thus approximating the closest CLUT entry for each pixel.
This approximation significantly reduces the processing that would be needed if absolute distances were determined for each pixel. However, because of the use of dividing planes orthogonal to the axes, the volumes associated with each CLUT entry are shaped in the form of a parallelepiped. Thus, pixels located in the outer corners of the volumes may in fact be closer to a CLUT entry corresponding to an adjacent volume, resulting in a less accurate color quantization. Another limitation of this approach is that the dividing planes are only formed orthogonal to one of the three axes. In an actual image, the concentration of pixel locations do not necessarily align perfectly with these axes. It has been proposed to analyze the densities of pixel locations in the color cube, and to rotate the axes so that the sides of the volumes better align with the layout of the pixels. Although this provides some improvement, it does not overcome the fundamental problem associated with dividing the color cube into volumes having sides which are all aligned in the same directions.
Thus, a disadvantage of the existing algorithms for color quantization is that they fail to effectively map the original image pixels to the selected CLUT entries. It is far too processor-intensive to determine the absolute distances between each discrete location and the CLUT entries on the color cube in order to identify the closest CLUT entry. On the other hand, using only the rough geometric approximation of the median-cut algorithm requires less computation, but may result in inferior image quality. Accordingly, there is a need for an improved color conversion method which minimizes the computational loads while accurately preserving the original image quality.
SUMMARY
To perform a color conversion, all of the colors in an image are represented by a smaller number of color entries in a color look-up table (CLUT). In accordance with the present invention, minimal surface theory is applied to the formation of spherical volumes in a color cube. The number of spherical volumes and the corresponding number of colors selected is a function of the desired amount of color compression. A sphere-creating process is then performed in which spheres centered on the center of each volume are created having a radius R. All of the pixels falling within a sphere are identified and associated with the volume center point about which that particular sphere is centered. Each sphere has attributed to it the color of a CLUT entry corresponding to the color of the sphere's center point. The radii of the spheres are incrementally increased, and all of the pixels falling within the enlarged spheres are associated with the corresponding CLUT entry.
The process of enlarging the spheres and associating additional pixels is repeated. As these spheres increase in size, they will begin to intersect and overlap with adjacent spheres. Because each location in the color cube must be associated with exactly one CLUT entry, the locations located within an overlapping region should be associated with the closest volume center point. Minimal surface theory teaches that the minimum distance between two points is a plane. Thus, as the surfaces of the expanding spheres approach and intersect adjacent spheres, planes will form between the spheres, and these planes are used to demarcate borders of the volumes associated with each volume center point. Unlike prior art methods, these planes will not necessarily form parallel to one of the sides of the color cub
Mayer Fortkort & Williams PC
Sony Corporation
Williams Esq. Karin L.
Wu Jingge
LandOfFree
Color conversion matrix based on minimal surface theory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Color conversion matrix based on minimal surface theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Color conversion matrix based on minimal surface theory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3062553