Image analysis – Pattern recognition – Classification
Reexamination Certificate
2000-02-17
2004-01-06
Au, Amelia M. (Department: 2721)
Image analysis
Pattern recognition
Classification
C382S164000, C382S166000
Reexamination Certificate
active
06674907
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to color image quantization, and more particularly to such quantization using a hierarchical color perception model.
BACKGROUND OF THE INVENTION
Color images, such as those captured using a digital video camera, a capture device for an analog video camera, a digital camera, or a scanner for existing photos, typically have a multitude of colors. For example, an image that is captured using a 24-bit color depth can have up to 2
24
different colors. While this makes for a very realistic image, the vast number of colors in the image means that the image takes up a lot of memory, which is inconvenient for storage and transmission purposes. Furthermore, applications such as computer vision (and image understanding) applications have difficulty understanding the perceptual objects (e.g., a person in a photo, a tree in the photo, etc.) that make up an image when there are so many colors in the image.
Therefore, color image quantization reduces the number of colors in an image to a predetermined number, such as only sixteen, as one example. It does this by determining an appropriate palette, or table, of a reduced number of colors, and then mapping the color of each pixel to a color from the palette, typically to the palette color that is closest to the original color of the pixel. In this way, the storage size of the image is effectively compressed, since far less data is needed to describe the colors of the image. An added advantage is that applications such as computer vision applications may then have an easier time understanding the objects that make up an image, where the objects each have fairly distinct color boundaries from one another.
Generally, color image quantization approaches within the prior art achieve a similarity between the source image and the quantized image based on the intensity difference between the two images, or based on another pixel-based measurement, such as a color histogram. However, such approaches do not provide higher-level information, such as the spatial connectivity among pixels, which is necessary for applications such as image segmentation and object recognition. While some approaches do take into account some of the spatial distribution among the colors of the images, they still usually do not provide enough higher-level information that is required in computer vision and other applications.
For these and other reasons, therefore, there is a need for the present invention.
SUMMARY OF THE INVENTION
The invention relates to color image quantization using a hierarchical perceptual color model. In one embodiment, a method constructs a clustering space of an image made up of a number of pixels, based on a color perception model. The clustering space includes a number of significant pixels, such that each of the significant pixels does not have a parent pixel within the clustering space, while the hierarchically lesser remaining pixels have at least one parent that is a significant pixel. The colors of the image are then quantized based on these significant pixels. Each of the remaining pixels then has its colors mapped to one of the quantized colors.
In one particular embodiment, constructing the clustering space of the image involves growing a perceptible color region, such as a disk, for each pixel, and building a relationship graph of hierarchical parent-child relationships of the pixels based on these perceptible color regions. A perceptible color region in one particular embodiment is grown by using a multi-scale edges approach. The relationship graph in one particular embodiment is built for each pair of overlapping regions by determining which region has a greater size, such that the region which has the greater size is the parent, and the region having the lesser size is the child.
Embodiments of the invention provide for advantages not found within the prior art. A color quantized image according to an embodiment of the invention has its colors chosen based on the non-overlapping perceptible color regions. Because these regions are themselves grown based on a color perception model, this means that the colors that are selected are comparable to what is visually significant to a human. Thus, inasmuch as colors are useful in determining the boundaries among objects within the image, quantizing the image according to colors selected based on a color perception model means that the resulting color quantized image yields useful higher-level information for computer vision and other applications.
The invention includes computer-implemented methods, machine-readable media, computerized systems, and computers of varying scopes. Other aspects, embodiments and advantages of the invention, beyond those described here, will become apparent by reading the detailed description and with reference to the drawings.
REFERENCES:
patent: 5047842 (1991-09-01), Bouman et al.
patent: 5519789 (1996-05-01), Etoh
Ikonomkais et al. “Region Growing an Region Merging ImageSegmentation.” IEEE, Digital Signal Processing Proceedings, v. 1 1997, 299-302.*
Velho et al. “Color Image Quantization by Pairwise Clustering.” IEEE, Computer Graphics and Image Processing, 1997, 203-210.*
Wan et al. “A New Approach to Image Retrieval with Hierarchical Color Clusterin.” IEEE, Circuits and Ssytems for Vidoe Technology, v. 8, 1998, 628-643.*
Celenk. “Hierarchical Color Clustering for Segmentation of Textured Images.” IEEE, Systems Theory, 1997, 483-487.*
Ikonomakis et al. “A Region-Based Color Image Segmentation Scheme”. SPIE Conference on Visual Communications and Image Processing, vol. 3653, Jan. 1999, pp. 1202-1209.*
KM Kim et al, Color image quantization using weighted distortion message of HVS color activity, Proc. of ICIP, vol. 3, pp. 1035-1039 (1996).
WS Kim et al, Color image palette construction based on the HIS color system for minimizing the reconstruction error, Proc. of ICIP, vol. 3, pp. 1041-1044 (1996).
P. Scheunders, A genetic approach towards optimal image quantization, Proc. of ICIP, vol. 3, pp. 1031-1034 (1996).
N. Chaddha et al, Color quantization of images based on human vision perception, Proc of ICASSP, vol. 5, pp. 89-92, 1994.
D. Comaniciu, P. Meer, Robust analysis of feature spaces: color image segmentation, Proc of CVPR, pp. 750-755, 1997.
Y. Deng et al, Peer Group Filtering and Perceptual Color Image Quantization, Proc of IEEE Int'l Symposium on Circuits and Systems (ISCAS), vol. 4, pp. 21-24, 1999.
X. Wu, Color quantization by dynamic programming and principal analysis, in ACM Transactions on Graphics, vol. 11, No. 4, Oct. 1992, pp. 348-372.
Chen Wei-Jun
Shum Heung-Yeung
Au Amelia M.
LaRose Colin
Lyon Richard T.
Lyon & Harr LLP
LandOfFree
Color image quantization using a hierarchical color... 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 image quantization using a hierarchical color..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Color image quantization using a hierarchical color... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3232556