Identification of duplicates within an image space

• US 8,995,771 B2
• Filed: 04/30/2012
• Issued: 03/31/2015
• Est. Priority Date: 04/30/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zhang, Lei, Wang, Xin-Jing, Ma, Wei-Ying
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): TORRES, JOSE
• Application Number:
  US13/459,777
• Publication Number:
  US 20130287302A1
• Time in Patent Office: 1,065 Days
• Field of Search: None
• US Class Current: 382/190
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/24 Classification techniques

Abstract

Implementations for identifying duplicate images in an image space are described. An image space is partitioned into a plurality of coarse clusters based on signatures of the images within the image space. The signatures are determined from compact descriptors of the images. Refined clusters that include one or more images of an individual coarse cluster are created based on pair-wise comparisons of the compact descriptors of images in the coarse cluster, and the refined clusters are identified as sets of duplicate images. The refined clusters are grown by searching in similar coarse clusters for images to add to the refined clusters.

Claims

1. A method comprising:

partitioning a plurality of images of an image space into a plurality of coarse clusters, the partitioning based at least in part on signatures of the plurality of images determined from compact descriptors of the plurality of images;

creating a refined cluster that includes one or more images of an individual coarse cluster based at least in part on pair-wise comparisons of the compact descriptors, from which the signatures are determined, of images of the individual coarse cluster;

identifying the refined cluster as a set of duplicate images; and

searching another coarse cluster of images for ones of the other coarse cluster to add to the refined cluster based at least in part on an average of the compact descriptors of the images of the refined cluster.

2. The method of claim 1, wherein the searching is at least partly in response to an identification of the other coarse cluster as being similar to the individual coarse cluster based at least in part on a Hamming distance between a quantized binary signature of the average compact descriptor and another signature associated with the other coarse cluster.

3. The method of claim 1, wherein the searching further comprises determining whether associated compact descriptors of the other coarse cluster have a similarity to the average of compact descriptors that is greater than a threshold similarity.

4. The method of claim 1, wherein the partitioning of the plurality of images into the plurality of coarse clusters includes placing images with identical signatures into the same coarse clusters.

5. The method of claim 1, further comprising quantizing the compact descriptors using mean values of dimensions of the compact descriptors to generate the signatures.

6. The method of claim 1, further comprising using Principal Component Analysis to compress raw global features of the plurality of images into the compact descriptors.

7. The method of claim 1, wherein the creating of the refined cluster includes identifying whether any images of the coarse cluster have associated compact descriptors within a threshold distance from an initial image of the refined cluster.

8. The method of claim 1, further comprising:

extracting raw global features from a plurality of images of the image space, the raw global features including gray block features, edge directional histograms, and non-edge ratios; and

compressing the raw global features to create the compact descriptors of the plurality of images.

9. A system, comprising:

memory;

one or more processors;

a partition module stored on the memory and executable by the one or more processors to partition an image space into a plurality of coarse clusters based at least in part on signatures of images within the image space, the signatures determined from compact descriptors of the plurality of images;

a cluster module stored on the memory and executable by the one or more processors to create refined clusters within the plurality of coarse clusters based at least in part on pair-wise comparisons of the compact descriptors, from which the signatures are determined, of images within individual ones of the coarse clusters;

a growth module stored on the memory and executable by the one or more processors to search similar coarse clusters for images to add to the refined clusters based at least in part on an average of the compact descriptors of the images of the refined clusters; and

an output module stored on the memory and executable by the one or more processors to output the refined clusters as sets of duplicate clusters.

10. The system of claim 9, wherein the growth module is further executable to identify the similar coarse clusters based at least in part on Hamming distances between the coarse clusters and the refined clusters.

11. The system of claim 9, wherein the growth module is further executable to search the similar clusters for the images to add to the refined clusters by determining whether associated compact descriptors of the images to add are within a threshold distance of the average compact descriptors of the refined clusters.

12. The system of claim 9, wherein the cluster module is further executable to:

initialize the refined clusters to include first images; and

add second images of the coarse clusters to the refined clusters based at least in part on second compact descriptors of the second images being within a certain distance threshold of first compact descriptors of the first images.

13. The system of claim 9, wherein the partition module creates the individual ones of the plurality of coarse clusters such that they include no images with non-duplicate signatures.

14. The system of claim 9, further comprising a feature extraction module stored on the memory and executable by the one or more processors to compress raw global features of the plurality of images into the compact descriptors using Principal Component Analysis.

15. The system of claim 14, wherein the feature extraction module is further executable to quantize the compact descriptors using mean values of dimensions of the compact descriptors to generate the signatures.

16. The system of claim 9, wherein the partition module is further executable to:

extract raw global features from a plurality of images of an image space, the raw global features including gray block features, edge directional histograms, and non-edge ratios; and

compress the raw global features to create the compact descriptors of the plurality of images.

17. One or more computer-readable storage media comprising a plurality of instructions executable by one or more processors of a computing system to cause the computing system to:

extract raw global features from a plurality of images of an image space, the raw global features including gray block features, edge directional histograms, and non-edge ratios;

compress the raw global features into corresponding compact descriptors of the plurality of images;

quantize the compact descriptors using mean values of dimensions of the compact descriptors to generate signatures for the plurality of images;

partition the image space into a plurality of coarse clusters such that groups of images with matching signatures are placed together into coarse clusters;

create one or more refined clusters within individual ones of the plurality of coarse clusters such that at least one of the one or more refined clusters include two or more images whose compact descriptors are within a threshold distance from one another;

grow the refined clusters by searching similar coarse clusters for images whose compact descriptors are within another threshold distance from averages of the compact descriptors of the refined clusters; and

output the refined clusters as sets of duplicate images.

18. The one or more computer-readable storage media of claim 17, wherein the plurality of instructions is further executable to cause the computing system to:

initialize images within the individual ones of the plurality of coarse clusters as belonging to separate refined clusters; and

merge together two or more of the separate refined clusters within the individual ones of the plurality of coarse clusters based at least in part on comparisons of corresponding compact descriptors of images of the separate refined clusters to determine whether the corresponding compact descriptors are within the threshold distance from one another.

19. The one or more computer-readable media of claim 17, wherein the plurality of instructions are further executable to cause the computing device to determine the similar coarse clusters based at least in part on Hamming distances between the plurality of coarse clusters.

20. The one or more computer-readable media of claim 17, wherein the plurality of instructions are further executable to utilize Principal Component Analysis to compress the raw global features into the corresponding compact descriptors.