Image retrieval system

• US 6,754,675 B2
• Filed: 07/16/2001
• Issued: 06/22/2004
• Est. Priority Date: 06/22/1998
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Abdel-Mottaleb, Mohammed S., Krishnamachari, Santhana
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US09/906,354
• Publication Number:
  US 20020087538A1
• Time in Patent Office: 1,072 Days
• Field of Search: 707/3, 707/104, 707/6, 707/2, 707/10, 382/229, 382/103, 382/219, 382/130, 709/219
• US Class Current: 1/1
• 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. A program segment for an image retrieval system, the program segment stored on a processor readable medium, the program segment comprising:

a program portion for querying a database with clusters, each cluster comprising a respective set of candidate images and a cluster center which is representative for that set, wherein the cluster center for a given cluster comprising more than one candidate image is not selected from the respective candidate images;

a program portion for comparing the query image with respective cluster centers to establish respective cluster similarities between the query image and the respective clusters; and

a program portion for selecting at least the cluster with the largest cluster similarity with the query image.

2. The program segment of claim 1, comprising a program portion 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.

3. The program segment of claim 2, comprising a program portion for presenting at least the candidate image with the largest image similarity.

4. The program segment of claim 1, wherein 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.

5. A program segment for organizing images in a database, the program segment stored on a processor readable medium, the program segment comprising:

a program portion 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

a program portion for determining a cluster center for each of the clusters, wherein the cluster centers are not selected from the respective candidate images for a cluster comprising more than one candidate image.

6. The program segment of claim 5, comprising a program portion for determining the similarity between each respective cluster and each other one of the clusters, wherein

the program portion for defining the cluster includes a program portion for merging two clusters with a largest mutual similarity into one new cluster, and

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

7. The program segment of claim 6, wherein the similarity between two clusters is determined on the basis of the average of the similarities between all pairs of images in the two clusters.

8. The program segment of claim 6, 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.

9. The program segment of claim 5, further comprising a program portion for cluster center optimization comprising:

a program portion for determining the similarity between at least one of the images and each of the cluster centers; and

a program portion for moving that image to an other cluster if that image has a larger similarity with the cluster center of that other cluster than with the cluster center of its own cluster.

10. The program segment of claim 5, comprising a program portion for retrieving images from the database, the program portion for retrieving images from the database comprising:

a program segment for comparing a query image with respective cluster centers to establish respective cluster similarities between the clusters and the query image; and

a program segment for selecting at least the cluster with the largest cluster similarity with the query image.

11. The program segment of claim 10, comprising a program portion for 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.

12. The program segment of claim 11, comprising a program portion for presenting at least the candidate image with the largest image similarity.

13. An apparatus for organizing images in a database, the apparatus comprising:

a 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

a means for determining a cluster center for each of the clusters, wherein the cluster centers are not selected from the respective candidate images for a cluster comprising more than one candidate image.

14. The apparatus of claim 13, comprising a means for determining the similarity between each respective cluster and each other one of the clusters, wherein

the means for defining the cluster includes a means for merging two clusters with a largest mutual similarity into one new cluster, and

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

15. The apparatus of claim 14, wherein the similarity between two clusters is determined on the basis of the average of the similarities between all pairs of images in the two clusters.

16. The apparatus of claim 14, 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.

17. The apparatus of claim 13, further comprising a means for cluster center optimization comprising:

a means for determining a similarity between at least one of the images and each of the cluster centers; and

a means for moving that image to an other cluster if that image has a larger similarity with the cluster center of that other cluster than with the cluster center of its own cluster.

18. The apparatus of claim 13, comprising a means for retrieving images from the database, the means for retrieving images from the database comprising:

a means for comparing a query image with respective cluster centers to establish respective cluster similarities between the clusters and the query image; and

a means for selecting at least the cluster with the largest cluster similarity with the query image.

19. The apparatus of claim 18, comprising a means for 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.

20. The apparatus of claim 19, comprising a means for presenting at least the candidate image with the largest image similarity.

21. The apparatus of claim 13, wherein the cluster center for at least one of the clusters is determined on the basis of an average of all images of the respective cluster.