Object similarity search in high-dimensional vector spaces

• US 7,941,442 B2
• Filed: 04/18/2007
• Issued: 05/10/2011
• Est. Priority Date: 04/18/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Ming Jing, Ma, Wei-Ying, Wang, Bin, Li, Zhiwei
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US11/737,075
• Publication Number:
  US 20080263042A1
• Time in Patent Office: 1,483 Days
• Field of Search: 707/100, 707/3, 780/780, 780/803
• US Class Current: 707/780
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

An object search system generates a hierarchical clustering of objects of a collection based on similarity of the objects. The object search system generates a separate hierarchical clustering of objects for multiple features of the objects. To identify objects similar to a target object, the object search system first generates a feature vector for the target object. For each feature of the feature vector, the object search system uses the hierarchical clustering of objects to identify the cluster of objects that is most “feature similar” to that feature of the target object. The object search system indicates the similarity of each candidate object based on the features for which the candidate object is similar.

Claims

1. A method in a computing device with a processor and a memory for identifying an object similar to a target object, the method comprising:

providing a collection of objects, the objects being images, each image in the collection represented by a plurality of values, each value corresponding to a feature of a plurality of features, each feature representing a characteristic of the image;

for each of the plurality of features of objects in the collection, generating by the computer system for the feature a cluster index data structure for the collection of objects, the cluster index data structure defining clusters of objects that are feature similar based on the values of feature, such that for each feature, the objects in the collection are clustered differently based on the values for that feature;

for each of the plurality of features of the target object, identifying by the computer system, from the cluster index data structure for that feature, clusters of candidate objects that are feature similar to the target object based on the values of that feature; and

for candidate objects, indicating by the computer system similarity of the candidate object to the target object based on the number of identified clusters containing the candidate object.

2. The method of claim 1 wherein the generating of a cluster index data structure for a feature includes, for each object in the collection, generating a hash code representing the feature for that object, and clustering objects that are feature similar using the hash code to represent the feature of an object.

3. The method of claim 2 wherein the clustering includes generating high-level clusters of objects that are feature similar based on high-order bits of the hash codes.

4. The method of claim 3 wherein the clustering includes, for each high-level cluster, generating initial low-level clusters of objects that are feature similar and merging clusters whose objects are most feature similar.

5. The method of claim 4 wherein the merging is performed until the number of clusters satisfies a merging termination criterion.

6. The method of claim 4 wherein similarity between clusters is based on the maximum distance between the hash code of an object in one cluster and the hash code of an object in another cluster.

7. The method of claim 6 wherein the distance is a Hamming distance.

8. The method of claim 1 wherein the indicating of similarity is based on the number of features for which a candidate object is feature similar to the target object.

9. The method of claim 8 wherein each feature has a feature weight indicating contribution of that feature to the similarity.

10. The method of claim 1 including ranking the candidate objects based on the indicated similarity.

11. A computer-readable storage medium encoded with instructions for controlling a computing device to generate a cluster index data structure for each of a plurality of features for a collection of images for use in identifying similar images, by a method comprising:

for each of the plurality of features of the images, generating the cluster index data structure for the feature defining clusters of images that are feature similar based on the feature by;

for each image of the collection, generating a hash code representation of the feature of the image;

generating high-level clusters of the images based on similarity between the hash codes of the images; and

for each high-level cluster,

generating initial low-level clusters of images within the high-level cluster based on similarity of the hash codes of the images; and

merging the generated low-level clusters based on similarity of hash codes between images of the low-level clusters to be merged until a merging termination criterion is satisfied.

12. The computer-readable storage medium of claim 11 wherein the hash code is generated using principal component analysis.

13. The computer-readable storage medium of claim 12 wherein the high-level clusters are clusters of images with the same high-order bit values.

14. The computer-readable storage medium of claim 12 wherein the generated low-level clusters are clusters of images with the same next-higher-ordered bit values.

15. The computer-readable storage medium of claim 12 wherein similarity between clusters is measured by the maximum Hamming distance between hash codes of images of one cluster and hash codes of images of the other cluster.

16. The computer-readable storage medium of claim 11 including

identifying images similar to a target image by

for each feature, identifying, from the cluster index data structure for that feature, candidate images that are feature similar to the target image based on that feature;

and

for candidate images, indicating similarity of the candidate image to the target image based on the features for which the candidate image is feature similar to the target image.

17. A computing system for identifying images of a collection that are similar to a target image, comprising:

a data structure storing, for each a plurality of features of images, a cluster index data structure defining clusters of images that are feature similar based on the feature;

a memory storing computer-executable instructions of

a component that, for each feature, identifies, from the cluster index data structure for that feature, candidate images that are feature similar to the target image based on that feature; and

a component that, for candidate images, indicates similarity of the candidate image to the target image based on the features for which the candidate image is feature similar to the target image; and

a processor for executing the computer-executable instructions stored in the memory.

18. The computing system of claim 17 wherein the cluster index data structure for a feature stores, for each image in the collection, a hash code representing the feature for that image, and wherein images are clustered that are feature similar using the hash code to represent the feature of an image.

19. The computer system of claim 17 wherein the target image is provided in a search request and including a component that ranks the candidate images based on the indicated similarity of the images.