Image retrieval system using a query image

• US 6,285,995 B1
• Filed: 06/22/1998
• Issued: 09/04/2001
• Est. Priority Date: 06/22/1998
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Krishnamachari, Santhana, Abdel-Mottaleb, Mohammed S.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US09/102,474
• Time in Patent Office: 1,170 Days
• Field of Search: 707/3, 707/6, 707/2, 382/229, 382/103, 709/219
• US Class Current: 707/737
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

An image retrieval system contains a database with a large number of images. The system retrieves images from the database that are similar to a query image entered by the user. The images in the database are grouped in clusters according to a similarity criterion so that mutually similar images reside in the same cluster. Each cluster has a cluster center which is representative for the images in it. A first step of the search to similar images selects the clusters that may contain images similar with the query image, by comparing the query image with the cluster centers of all clusters. A second step of the search compares the images in the selected clusters with the query image in order to determine their similarity with the query image.

Claims

1. 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 wherein the cluster centers are not selected from the resepective candidate images; and

presentation means for presenting at least the candidate image with the largest image similarity.

2. An image retrieval system according to claim 1, in which at least one of the cluster centers is represented by a color histogram which is the average of respective color histograms of a number of representative images in the particular cluster.

3. 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:

calculating an average for each of the clusters as the respective cluster center;

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.

4. 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, wherein the cluster centers are not selected from the respective images.

5. A method according to claim 4, further comprising the step of determining the similarity between each respective cluster and each other one of the clusters, wherein

the step of defining the cluster includes merging the two clusters with the largest mutual similarity into one new cluster, and

the step of determining a cluster center includes determining an average from the respective subset of images as a cluster center for the new cluster.

6. A method according to claim 5, wherein the similarity between two clusters is determined on the basis of the average of the similarities between all pairs of as images in the two clusters.

7. A method according to claim 5, wherein the cluster center of the new cluster is determined on the basis of images selected from respective ones of the two clusters that had been selected for merging into the new cluster.

8. A method according to claim 4, further comprising a cluster center optimization step including:

determining the similarity between at least one of the images and each of the cluster centers and

if that image has a larger similarity with the cluster center of another cluster than with the cluster center of its own cluster, moving that image to that other cluster.

9. A system for organizing images in a database, the system comprising:

clustering means for 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

center determining means for determining a cluster center for each of the clusters by determining average image values from the images in the cluster.

10. A database with a plurality of images, the database comprising:

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

a cluster center for each of the clusters representing average image values of the respective subset of images.