Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-07-16
2004-06-22
Pardo, Thuy N. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C382S103000, C382S130000, C382S219000, C382S229000
Reexamination Certificate
active
06754675
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to an image retrieval system comprising:
a database with candidate images,
entry means for entering a query image,
comparison means for comparing the query image with one of the candidate images, and
presentation means for presenting at least the candidate image with the largest similarity with the query image.
The invention further relates to a method for retrieving images from a database with candidate images, the method comprising the steps of:
inputting a query image;
comparing the query image with candidate images to establish respective similarities between these candidate images and the query image; and
presenting at least the candidate image with the largest image similarity with the query image.
The invention further relates to a method for organizing images in a database.
The invention further relates to a system for organizing images in a database.
The invention further relates to a database with a plurality of images.
Image retrieval systems are of importance for applications that involve large collections of images. Professional applications include broadcast stations where a piece of a video may be identified through a set of shots and where a shot of video is to be retrieved according to a given image. Also movie producers must be able to find back scenes from among a large number of scenes. Furthermore art museums have large collections of images, from their paintings, photos and drawings, and must be able to retrieve images on the basis of some criterion with respect to their contents. Consumer applications include maintaining collections of slides, photos and videos, from which the user must be able to find back items, e.g. on the basis of similarity with a specified query image.
An image retrieval system and a method as described above, are known from the article “Tools and Techniques for Color Image Retrieval”, John R. Smith and Shih-Fu Chang, Proc. SPIE-Int. Soc. Opt. Eng (USA), Vol. 2670, pp. 426-437. The image retrieval system comprises a database with a large number of images. A user searching for a particular image specifies a query image as to how the retrieved image or images should look like. Then the system compares the stored images with the query image and ranks the stored images according to their similarity with the query image. The ranking results are presented to the user who may retrieve one or more of the images. The comparison of the query image with a stored image to determine the similarity may be based on a number of features derived from the respective images. The image feature or features used for comparison are called a feature vector. The article describes the usage of a color histogram as such a feature vector. When using the RGB (Red, Green and Blue) representation of an image, a color histogram is computed by quantizing the colors within the image and counting the number of pixels of each color. To determine the similarity, a number of techniques are described to compare the two color histograms of the respective images. An example of such technique is the histogram intersection, where the similarity is the sum over all histogram bins of the minimal value of the pair of corresponding bins of the two histograms.
In a practical set up, the number of images can be very large. On the Internet for example, the number of images can be of the order of millions and is ever growing. Even if the time to compare the query image with a candidate image is very short, the cumulative time needed to compare the query image with all images in the database will be long. It is a drawback of the known system that a user searching for an image in such a large database must wait a long time after having submitted the query image in the system.
SUMMARY OF THE INVENTION
It is an object of the invention to provide an image retrieval system of the kind set forth in which the time for finding candidate images similar with the query image is reduced. This object is achieved according to the invention in an image retrieval system comprising:
a database with clusters, each cluster comprising a respective set of candidate images and a cluster center which is representative for that set;
entry means for entering a query image;
cluster comparison means for comparing the query image with respective cluster centers to establish respective cluster similarities between the query image and the respective clusters;
selection means for selecting at least the cluster with the largest cluster similarity with the query image;
image comparison means for comparing the query image with the candidate images in the selected clusters to establish respective image similarities between the query image and the respective candidate images; and
presentation means for presenting at least the candidate image with the largest image similarity.
By selecting one or more clusters that are most similar with the query image and subsequently comparing the query image with only the candidate images in the selected clusters, fewer comparisons are needed. This reduces the time needed to find the candidate images that are similar with the query image. Since the number of clusters is much smaller than the number of images, the number of additional comparisons for comparing the query image with the clusters is much smaller than the number of saved comparisons because of not comparing the query image with the images in the not selected clusters. Clustering of the candidate images into clusters according to their similarity does not require the presence of any query image. Therefore, the clustering is done in advance and is not done at the time the user is actually searching for images on the basis of the query image. So the time needed to cluster the images does not add to the waiting time the user of the system experiences when searching.
An embodiment of the image retrieval system according to the invention is defined in claim
2
. The similarity between images may be determined on the basis of their color histograms. The average of the respective histograms of a number of representative images of a cluster can advantageously be used as a representation for the whole cluster.
It is a further object of the invention to provide a method for retrieving images of the kind set forth with a reduced time for finding candidate images similar with the query image. This object is achieved according to the invention in a method for retrieving images from a database comprising clusters, each cluster comprising a respective set of candidate images and a cluster center which is representative for that set, the method comprising the steps of:
inputting a query image;
comparing the query image with respective cluster centers to establish respective cluster similarities between the clusters and the query image;
selecting at least the cluster with the largest cluster similarity with the query image;
comparing the query image with respective candidate images of the selected clusters to establish respective image similarities between these candidate images and the query image; and
presenting at least the candidate image with the largest image similarity.
By first determining which of the clusters are similar with the query image and by subsequently comparing the query image with only the images in those clusters, far fewer comparisons are needed. This greatly reduces the time needed to find the candidate images that are similar with the query image.
It is a further object of the invention to provide a method for organizing images in a database, which resulting database allows to find images that are similar with a given query image in a reduced time. This object is achieved according to the invention in a method for organizing images in a database, the method comprising the steps of:
defining clusters each comprising a subset of the images, whereby the images in a cluster are similar with each other and whereby at least one of the clusters comprises more than one image, and
determining a cluster center for each of the clusters.
By grouping mutually similar images in
Abdel-Mottaleb Mohammed S.
Krishnamachari Santhana
Koninklijke Philips Electronics , N.V.
Pardo Thuy N.
Thorne Gregory L.
LandOfFree
Image retrieval system 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 retrieval system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image retrieval system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3365398