Scalable near duplicate image search with geometric constraints

• US 8,254,697 B2
• Filed: 02/02/2009
• Issued: 08/28/2012
• Est. Priority Date: 02/02/2009
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Isard, Michael, Ke, Qifa, Sun, Jian, Wu, Zhong
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US12/364,090
• Publication Number:
  US 20100195914A1
• Time in Patent Office: 1,303 Days
• Field of Search: 382/181, 382/209, 382/190, 382/195, 382/201, 382/100, 382/154, 382/168, 382/173, 382/176, 382/276, 382/155, 382/159, 382/103, 382/217, 382/218, 382/219, 382/293, 382/294, 382/305
• US Class Current: 382/209
• 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, where by the first feature detection scheme comprises the step of identifying local regions of interest within the image by (MSER) maximally stable extremal regions;

(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 (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) scale invariant feature transform.

3. 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.

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 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.

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

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

7. The method of claim 6, 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.

8. The method of claim 6, 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.