SCALABLE NEAR DUPLICATE IMAGE SEARCH WITH GEOMETRIC CONSTRAINTS

• US 20100195914A1
• Filed: 02/02/2009
• Published: 08/05/2010
• Est. Priority Date: 02/02/2009
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Isard, Michael, Sun, Jian, Ke, Qifa, Wu, Zhong
• Granted Patent: US 8,254,697 B2
• Time in Patent Office: Days
• US Class Current: 382/201
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

Methods are disclosed for finding images from a large corpus of images that at least partially match a query image. The present method makes use of feature detectors to bundle features into local groups or bundles. These bundled features are repeatable and much more discriminative than an individual SIFT feature. Equally importantly, the bundled features provide a flexible representation that allows simple and robust geometric constraints to be efficiently enforced when querying the index.

Claims

1. A method of processing an image to enable indexing and comparison of the image against other similarly processed images, the method comprising the steps of:

(a) identifying local regions of interest within the image by a first feature detection scheme;

(b) identifying local points of interest within the image by a second feature detection scheme;

(c) defining bundled features by grouping together the local points of interest that occur within a given local region of interest; and

(d) comparing bundled features of a first image to bundled features of a second image to determine if the first and second images are at least partial matches of each other.

2. The method of claim 1, wherein said step (a) of identifying local regions of interest within the image by a first feature detection scheme comprises the step of identifying local regions of interest within the image by MSER.

3. The method of claim 1, wherein said step (b) of identifying local points of interest within the image by a second feature detection scheme comprises the step of identifying local points of interest within the image by SIFT.

4. The method of claim 1, wherein said step (d) of comparing bundled features of a first image to bundled features of a second image comprises the step of finding a bundled feature in the first image and a bundled feature in the second image that share at least two common local points of interest.

5. The method of claim 1, wherein said step (d) of comparing bundled features of a first image to bundled features of a second image comprises the steps of determining the relative positions of local points of interest along first and second perpendicular axes within bundles in the first and second images, and comparing the relative positions between bundles in the first and second images.

6. The method of claim 1, further comprising the step of defining a feature descriptor for each local point of interest within a bundled feature.

7. The method of claim 6, further comprising the step of quantizing the feature descriptor for each local point of interest into one or more visual words.

8. The method of claim 7, further comprising the step of indexing the one or more visual words by storing a visual word together with an inverse hit list of all bundled features within which the visual word appears.

9. The method of claim 7, further comprising the step of indexing the one or more visual words by storing a visual word together with an inverse hit list using a global location space, wherein each word is followed by the global locations assigned to each of its appearances in the images.

10. A method of finding candidate images from a large corpus of images that at least partially match a query image, the method comprising the steps of:

(a) identifying local regions of interest within the candidate and query images by a first feature detection scheme;

(b) identifying local points of interest within the candidate and query images by a SIFT feature detection scheme;

(c) defining bundled features within the candidate and query images by grouping together the local points of interest that occur within a given local region of interest;

(d) comparing bundled features of the query image to bundled features of a candidate image to find a bundled feature in the query image and a bundled feature in the candidate image that share at least two common local points of interest;

(e) determining the relative positions of local points of interest along first and second perpendicular axes within bundles in the query image and candidate image; and

(f) comparing the relative positions determined in said step (e) between bundles in the first image and the query image.

11. The method recited in claim 10, wherein said step (a) of identifying local regions of interest comprises the step of identifying local regions of interest by MSER.

12. The method of claim 10, further comprising the step of defining a k-dimensional descriptor for each local point of interest within a bundled feature.

13. The method of claim 12, further comprising the step of quantizing the k-dimensional descriptor for each local point of interest into one or more visual words.

14. The method of claim 13, further comprising the step of indexing the one or more visual words by storing a visual word together with an inverse hit list of all bundled features within which the visual word appears.

15. The method recited in claim 10, further comprising the step of scoring a similarity between the query image and the candidate images, the scoring based at least in part on the number of local points of interest shared between bundled features of the query image and bundled features in the candidate images, and the scoring based in part on a correlation between the positions of the local points of interest in the query image and the positions of the local points of interest in the candidate images, the matched candidate images being ranked based on which candidate images achieve the highest scores.

16. A computer storage medium having computer-executable instructions for programming a processor to perform a method of finding candidate images from a large corpus of images that at least partially match a query image, the method comprising the steps of:

(a) identifying local regions of interest within the candidate and query images by a first feature detection scheme;

(b) identifying local points of interest within the candidate and query images by a second feature detection scheme;

(c) defining bundled features within the candidate and query images by grouping together the local points of interest that occur within a given local region of interest;

(d) determining feature descriptors for the local points of interest in the query and candidate images;

(e) processing visual words based on the feature descriptors determined in said step (d); and

(f) comparing one or more visual words from the query image to one or more visual words of a candidate image to determine if the candidate image is at least a partial match to the query image.

17. The computer storage medium of claim 16, wherein the visual words processed in step (e) include information relating to the bundled features defined in said step (c), the information relating to the bundled features being used in said step (f) of comparing one or more visual words from the query image to one or more visual words of a candidate image.

18. The computer storage medium of claim 16, further comprising the step (g) of determining a position of the local points of interest along an axis within bundles of the query image and along the same axis within bundles of the candidate images.

19. The computer storage medium of claim 18, further comprising the step of encoding the positional information determined in said step (g) into the visual words and using that encoded information in said step (f) of comparing one or more visual words from the query image to one or more visual words of a candidate image.

20. The computer storage medium of claim 18, further comprising the step of scoring a similarity between the query image and the candidate images, the scoring based at least in part on a similarity between one or more bundled features of the query image and one or more bundled features of the candidate images, the matched candidate images being ranked based on which candidate images achieve the highest scores.