IMAGE CLUSTERING

• US 20110305399A1
• Filed: 06/10/2010
• Published: 12/15/2011
• Est. Priority Date: 06/10/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zitnick, Charles, Sagula, Rafael, Chandrashekar, Ashok
• Granted Patent: US 8,625,907 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures

Abstract

A database of images may be accessed. A feature set may be computed for each image, respectively. Each feature set includes feature integers quantized from interest points of a corresponding image. An initial set of clusters of the feature sets is found based on min hashes of the feature sets. Given the clusters of feature sets, descriptors for each of the clusters are computed, respectively, by selecting feature integers from among the feature sets in a cluster. The clusters are then refined by comparing at least some of the feature sets with at least some of the cluster descriptors, and based on such comparing adding some of the feature sets to clusters whose feature descriptors have similarity to the feature sets.

Claims

1. A method implemented by one or more computers to cluster images, the method comprising:

accessing a set of images, each image having a corresponding feature set, respectively;

perform a first clustering step comprising forming initial clusters of the feature sets;

computing cluster descriptors for the initial clusters, respectively, where a descriptor for a given initial cluster is computed by selecting feature integers from among the feature sets in the given initial cluster, each feature set in the given initial cluster corresponding to a different one of the images in the set of images;

refining the initial clusters by comparing at least some of the feature sets of the images with at least some of the cluster descriptors, and based on such comparing moving some of the features sets from corresponding initial clusters to other initial clusters.

2. A method according to claim 1, wherein a feature set of an image comprises a set of integers obtained by quantizing descriptors computed from features of the image.

3. A method according to claim 1, wherein the forming of the initial clusters comprises computing min hashes of the feature sets.

4. A method according to claim 3, wherein the forming of the initial clusters further comprises sorting the min hashes of the feature sets and forming clusters of the feature sets that have matching min hashes.

5. A method according to claim 3, wherein the min hash of a feature set comprises a concatenation of multiple different min hashes of the feature set.

6. A method according to claim 6, wherein whether a feature set is moved to another cluster is determined based on the number of feature integers common to both the feature set and the cluster descriptor of the other cluster.

7. A method according to claim 6, wherein the number of feature integers is determined by using a reverse lookup table that maps feature integers to clusters.

8. One or more computer-readable storage storing information to enable one or more computers to perform a process, the process comprising:

accessing a plurality of feature sets of respective images, each feature set of an image comprising a plurality of features of the image;

for each feature set, given a feature set, computing a plurality of sketches, each sketch of the feature set comprising a concatenation of hashes of the feature set;

placing the feature sets in clusters based on the respective sketches;

adding a set of the feature sets to a set of the clusters, where, for a given one of the features sets in the set of features, and for a given one of the clusters in the set of clusters, a determination is made whether to add the given feature set to the given cluster based on the features of the given feature set and based on features from among the feature sets in the given cluster; and

based on the added-to clusters of feature sets, storing information indicating which images belong to which clusters.

9. One or more computer-readable storage according to claim 8, wherein the features of a feature set were computed based on image analysis of the corresponding image, the features representing features of subject matter in the image.

10. One or more computer-readable storage according to claim 8, wherein each feature set comprises a bag of features, and the features of each feature set comprise features from a feature dictionary.

11. One or more computer-readable storage according to claim 10, wherein the features of a feature set are computed by mapping features of the images to nearest words in the feature dictionary and using those words as the features of the feature sets.

12. One or more computer-readable storage according to claim 8, wherein the hashes of the sketches comprise min hashes, the min hashes having been computed based on random permutations of the feature sets.

13. One or more computer-readable storage according to claim 8, wherein the hashes are computed from a locality sensitive hashing function.

14. One or more computer-readable storage according to claim 13, wherein the locality sensitive hashing function comprises a Min Hash function.

15. A computing device comprising:

memory storing a plurality of feature sets, each feature set comprising a plurality of features of a corresponding image;

a processor executing instructions that access the feature sets and store in the memory information indicating clusters of the feature sets, the clusters having been computed by the processor computing min hashes of the feature sets and determining which feature sets belong to which clusters based on which feature sets have min hashes with common values;

the processor computing and storing in the memory cluster descriptors for the clusters, respectively, a cluster descriptor comprising a plurality of features from the feature sets in the corresponding cluster; and

the processor altering the clusters stored in the memory by adding some of the feature sets to some of the clusters, where the processor determines whether to add a feature set to a cluster based on the features in the feature set and based on the cluster descriptor for the feature set.

16. A computing device according to claim 15, wherein the features of a feature set for an image comprise quantizations of interest points in the image.

17. A computing device according to claim 15, wherein a min hash of a feature set comprises a concatenation of individual min hashes from different permutations of the feature set.

18. A computing device according to claim 15, wherein for each cluster the processor removes features from the cluster descriptors, where a feature is removed based on how commonly it occurs among the feature sets.

19. A computing device according to claim 18, wherein how commonly a feature occurs is computed using TF/IDF over the set of features in the feature sets.

20. A computing device according to claim 15, determining scores for respective clusters based on features in respective cluster descriptors, and eliminating clusters based on the scores.