Partition min-hash for partial-duplicate image determination

• US 8,452,106 B2
• Filed: 03/23/2010
• Issued: 05/28/2013
• Est. Priority Date: 03/23/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ke, Qifa, Isard, Michael A., Lee, David Changsoo
• Primary Examiner(s): Zarka, David
• Assistant Examiner(s): MOTSINGER, SEAN T
• Application Number:
  US12/729,250
• Publication Number:
  US 20110235908A1
• Time in Patent Office: 1,162 Days
• Field of Search: None
• US Class Current: 382/195
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• 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/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

Images in a database or collection of images are each divided into multiple partitions with each partition corresponding to an area of an image. The partitions in an image may overlap with each other. Min-hash sketches are generated for each of the partitions and stored with the images. A user may submit an image and request that an image that is a partial match for the submitted image be located in the image collection. The submitted image is similarly divided into partitions and min-hash sketches are generated from the partitions. The min-hash sketches are compared with the stored min-hash sketches for matches, and images having partitions whose sketches are matches are returned as partial matching images.

Claims

1. A method comprising:

receiving a first image at a computing device through a network;

dividing the first image into a plurality of partitions by the computing device;

for each partition of the first image, generating one or more min-hash sketches for the partition by the computing device;

storing the generated one or more min-hash sketches for each partition of the first image by the computing device;

dividing the first image into a grid of elements;

determining one or more min-hashes of each element; and

storing the computed one or more min-hashes of each element.

2. The method of claim 1, further comprising:

receiving a second image;

dividing the second image into a plurality of partitions;

for each partition of the second image, generating one or more min-hash sketches for the partition; and

determining if the first image matches the second image using the min-hash sketches of the first image and the min-hash sketches of the second image.

3. The method of claim 2, wherein determining if the first image matches the second image using the min-hash sketches of the first image and the min-hash sketches of the second image comprises determining if any of the min-hash sketches of the first image matches any of the min-hash sketches of the second image, and if so, determining that the first image matches the second image.

4. The method of claim 2, wherein determining if the first image matches the second image using the min-hash sketches of the first image and the min-hash sketches of the second image comprises determining if all of the min-hash sketches of the first image match a min-hash sketch of the second image, and if so, determining that the first image matches the second image.

5. The method of claim 1, wherein each partition comprises a plurality of elements and determining a min-hash sketch for a partition comprises:

retrieving the stored one or more min-hashes for each element of the partition; and

selecting a minimum retrieved min-hash as the min-hash sketch for the partition.

6. The method of claim 1, wherein the partitions are overlapping partitions.

7. The method of claim 1, wherein the partitions are multi-scale.

8. The method of claim 1, wherein determining one or more min-hash sketches for a partition comprises, for each of a plurality of hash functions:

determining a min-hash of a visual word from the partition using the hash function; and

adding the determined min-hash to a sketch of the partition.

9. A method comprising:

receiving a first image at a computing device;

determining a plurality of features of the first image by the computing device;

generating a min-hash sketch of the first image by the computing device;

determining a geometric relationship for a pair of features from the plurality of determined features of the first image by the computing device;

associating the geometric relationship with the sketch by the computing device;

storing the min-hash sketch and the associated geometric relationship for the first image by the computing device;

receiving a second image;

generating a min-hash sketch of the second image;

determining if the min-hash sketch of the first image matches the min-hash sketch of the second image; and

if it is determined that the min-hash sketch of the first image matches the min-hash sketch of the second image;

determining a plurality of features from the of the second image;

determining a geometric relationship for a pair of features from the plurality of determined features of the second image; and

determining if the geometric relationship for the pair of features from the first image matches the geometric relationship for the pair of features from the second image, and if so, determining that the first image matches the second image.

10. The method of claim 9, wherein the features comprise visual words.

18. The method of claim 9, further comprising:

dividing the first image into a grid of elements;

determining one or more min-hashes of each element; and

storing the computed one or more min-hashes of each element.

11. A system comprising:

at least one computing device; and

an image matcher adapted to;

receive a first image;

divide the first image into a plurality of partitions, wherein the partitions are overlapping partitions;

for each partition of the first image, generate one or more min-hash sketches for the partition; and

store the generated min-hash sketches for each partition of the first image.

12. The system of claim 11, wherein the image matcher is further adapted to:

receive a second image;

divide the second image into a plurality of partitions;

for each partition of the second image, generate one or more min-hash sketches for the partition; and

determine if the first image matches the second image using the min-hash sketches of the first image and the min-hash sketches of the second image.

13. The system of claim 12, wherein the first and second images are received from the same image collection.

14. The system of claim 12, wherein the image matcher determines if the first image matches the second image using the min-hash sketches of the first image and the min-hash sketches of the second image by determining if any of the min-hash sketches of the first image matches any of the min-hash sketches of the second image, and if so, determining that the first image matches the second image.

15. The system of claim 12, wherein the image matcher determines if the first image matches the second image using the min-hash sketches of the first image and the min-hash sketches of the second image by determining if all of the min-hash sketches of the first image match a min-hash sketch of the second image, and if so, determining that the first image matches the second image.

16. The system of claim 12, wherein the image matcher is further adapted to:

determine a pair of features of a partition of the first image;

determine a first geometric relationship for the pair of features of the partition of the first image; and

store the geometric relationship for the pair of features with the min-hash sketch of the partition.

17. The system of claim 16, wherein the image matcher is further adapted to:

determine a pair of features of a partition of the second image;

determine a second geometric relationship for the pair of features of the partition of the second image; and

determine if the first image matches the second image using the min-hash sketches of the first image, the min-hash sketches of the second image, and the first and second geometric relationship.

19. The system of claim 11, wherein the image matcher divides the first image into a grid of elements, determines one or more min-hashes of each element, and stores the computed one or more min-hashes of each element.

20. The system of claim 11, wherein the partitions are multi-scale.