Image analysis – Color image processing
Reexamination Certificate
1998-12-28
2001-06-12
Tadayon, Bijan (Department: 2721)
Image analysis
Color image processing
C382S165000
Reexamination Certificate
active
06246790
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data management and more particularly to retrieving images using color correlograms.
BACKGROUND OF THE INVENTION
With the rapid proliferation of the Internet and the World Wide Web, the amount of digital image data accessible to users has grown enormously. Image databases are becoming larger and more widespread, and there is a growing need for effective and efficient image retrieval systems. That is, systems that extract from a large collection of images ones that are “similar” to an image of interest to the user. Most existing image retrieval systems adopt the following two-step approach to search image databases: (i) indexing: for each image in the database, a feature vector capturing certain essential properties of the image is computed and stored in a featurebase, and (ii) searching: given a query image, its feature vector is computed, compared to the feature vectors in the featurebase, and images most similar to the query image are returned to the user.
For a retrieval system to be successful, the feature defined for an image should have certain desirable qualities: (i) the difference between pre-selected features of two images should be large if and only if the images are not “similar”, (ii) the feature should be fast to compute, and (iii) the size of the feature should be small.
Color histograms are commonly used as feature vectors for images. Though the histogram is easy to compute and seemingly effective, it is liable to cause false positive matches, especially where databases are large, and is not robust to large appearance changes. Recently, several approaches have attempted to improve upon the histogram by incorporating spatial information with color. Many of these methods are still unable to handle large changes in appearance. For instance, the color coherence vector (CCV) method uses the image feature(s), e.g. spatial coherence of colors and pixel position, to refine the histogram. These additional features improve performance, but also require increased storage and computation time.
It remains desirable to have an efficient and accurate means of identifying and retrieving images which allows for changes in the appearance of the image content such as viewing angle and magnification.
It is an object of the present invention to provide a method and apparatus to perform efficient image comparisons.
It is another object of the present invention to provide a method and apparatus to provide a method and apparatus to perform image comparisons which allow for significant changes in the image such as viewing position, background, lighting, and focus.
It is another object of the present invention to provide a method and apparatus which enables efficient image retrieval from a database.
SUMMARY OF THE INVENTION
The problems of image retrieval are solved by the present invention of providing and using a color correlogram. The color correlogram of the present invention is a three-dimensional representation indexed by color pairs and distance between pixels which expresses how the spatial correlation of color changes with distance in a stored image. The color correlogram includes spatial correlation of colors, combines both the global and local distributions of colors, is easy to compute, and is small from a data storage perspective. The color correlogram is robust in tolerating large changes in the appearance of a scene caused by changes in viewing positions, changes in the background scene, partial occlusions, and magnification that causes radical changes in shape.
To create a color correlogram, the colors in the image are quantized into m color values, c
1
. . . c
m
. Also, the distance values D
⊂
[d] to be used in the correlogram are determined where [d] is the set of distances between pixels in the image, and where dmax is the maximum distance measurement between pixels in the image. Each entry (i, j, k) in a table, which can be used to define or represent the color correlogram, is the probability of finding a pixel of color c
j
at a selected distance k from a pixel of color c
i
.
A color autocorrelogram is a restricted version of the color correlogram that considers color pairs of the form (i,i) only.
Any norm for comparing vectors, for example the standard L
1
norm may be used to compare color correlograms/color autocorrelograms.
Experimental evidence shows that the color correlogram outperforms not only color histograms but also more recent histogram refinements such as the color coherence vector method for image indexing and retrieval.
The present invention together with the above and other advantages may best be understood from the following detailed description of the embodiments of the invention illustrated in the drawings, wherein:
REFERENCES:
patent: 4962540 (1990-10-01), Tsujiuchi et al.
patent: 4979225 (1990-12-01), Tsujiuchi et al.
patent: 4998286 (1991-03-01), Tsujiuchi et al.
patent: 5105466 (1992-04-01), Tsujiuchi et al.
patent: 5208911 (1993-05-01), Newman et al.
patent: 5247583 (1993-09-01), Kato et al.
patent: 5343538 (1994-08-01), Kasdan
patent: 5363454 (1994-11-01), Udagawa et al.
patent: 5420979 (1995-05-01), Madden et al.
patent: 5430690 (1995-07-01), Abel
patent: 5432906 (1995-07-01), Newman et al.
patent: 5537488 (1996-07-01), Menon et al.
patent: 5565962 (1996-10-01), Yoshimoto
patent: 5583614 (1996-12-01), Hasuo et al.
patent: 5586197 (1996-12-01), Tsujimura et al.
patent: 5608820 (1997-03-01), Vaidyanathan
patent: 5630037 (1997-05-01), Schindler
patent: 5633952 (1997-05-01), Outa et al.
patent: 5644765 (1997-07-01), Shimura et al.
patent: 5652881 (1997-07-01), Takahashi et al.
patent: 5689575 (1997-11-01), Sako et al.
patent: 5828779 (1998-10-01), Maggioni
patent: 5845009 (1998-12-01), Marks et al.
patent: 6043909 (2000-03-01), Holub
Huang Jing
Kumar Shanmugasundaram Ravi
Mitra Mandar
Zhu Wei-Jing
Alavi Amir
Cohen Jerry
Cornell Research Foundation Inc.
Erlich Jacob N.
Perkins Smith & Cohen LLP
LandOfFree
Image indexing using color correlograms does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image indexing using color correlograms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image indexing using color correlograms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531700