Geometric coding for billion-scale partial-duplicate image search

• US 9,412,020 B2
• Filed: 11/09/2012
• Issued: 08/09/2016
• Est. Priority Date: 11/09/2011
• Status: Active Grant

• Current Assignee: University of Science and Technology of China (Chinese Academy of Sciences), Texas State University System, Board of Regents of the University of Texas System (University of Texas System)
• Original Assignee: University of Science and Technology of China (Chinese Academy of Sciences), Texas State University System, Board of Regents of the University of Texas System (University of Texas System)
• Inventors: Tian, Qi, Zhou, Wengang, Li, Houqiang, Lu, Yijuan
• Primary Examiner(s): Chawan, Sheela C
• Application Number:
  US14/357,376
• Publication Number:
  US 20140314324A1
• Time in Patent Office: 1,369 Days
• Field of Search: 382/197, 382/181, 382/224, 382/276, 382/305, 382/190, 382/195, 382/201, 382/168, 382/170, 382/228, 382/209, 382/232, 382/251, 382/253, 707/687, 707/723, 707/705, 707/722, 707/E17.024, 707/E17.022, 707/E17.026, 707/E17.02, 707/763, 707/748, 707/749, 707/692
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations

Abstract

Most of large-scale image retrieval systems are based on Bag-of-Visual-Words model. However, traditional Bag-of-Visual-Words model does not well capture the geometric context among local features in images, which plays an important role in image retrieval. In order to fully explore geometric context of all visual words in images, efficient global geometric verification methods have been attracting lots of attention. Unfortunately, current existing global geometric verification methods are either computationally expensive to ensure real-time response. To solve the above problems, a novel geometric coding algorithm is used to encode the spatial context among local features for large scale partial duplicate image retrieval. With geometric square coding and geometric fan coding, our geometric coding scheme encodes the spatial relationships of local features into three geo-maps, which are used for global verification to remove spatially inconsistent matches. This approach is not only computationally efficient, but also effective in detecting duplicate images with rotation, scale changes, occlusion, and background clutter.

Claims

1. A method of analyzing digital images comprising:

extracting features from a first image and a second image;

quantizing the extracted features by creating a feature vector;

comparing the feature vectors of the first image with the feature vectors of the second image to determine matching pairs of feature vectors

performing geometric coding to encode the relative spatial positions of the feature vectors, wherein performing geometric coding comprises forming a geo-map of the first image and a geo-map of the second image;

performing spatial verification of one or more matching pairs of feature vectors using the determined relative spatial positions of the feature vectors, wherein performing spatial verification of one or more matching pairs of feature vectors comprises comparing the geo-map of the first image to the geo-map of the second image;

removing false matching pairs of feature vectors between the first image and the second image based on the spatial verification; and

comparing the remaining matching pairs of feature vectors to determine if the first image is the same as the second image.

2. The method of claim 1, wherein extracting features from the first and second images comprises generating scale invariant feature transform (SIFT) features for the digital images.

3. The method of claim 1, further comprising rotating the image to align the one of the feature vectors with a predetermined orientation.

4. The method of claim 1, wherein the geo-map of the first image and the geo-map of the second image are formed using geometric square coding.

5. The method of claim 4, wherein geometric square coding comprises dividing an image plane of an image into regular squares relative to a feature vector of the image and checking whether other feature vectors are inside or outside of the square.

6. The method of claim 1, wherein the geo-map of the first image and the geo-map of the second image are formed using geometric fan coding.

7. The method of claim 6, wherein geometric fan coding comprises dividing an image plane of an image into regular fan regions relative to a feature vector of the image and checking whether other feature vectors are inside or outside of the fan regions.

8. The method of claim 1, further comprising storing the quantized images as visual words, wherein a visual word comprises an orientation value, scale value, x-value, and y-value.

9. The method of claim 1, wherein the first digital image is stored in an image databases and wherein the second image is obtained from a web site.

10. A system, comprising:

a processor;

a memory coupled to the processor and configured to store program instructions executable by the processor to perform the method comprising;

extracting features from a first image and a second image;

quantizing the extracted features by creating a feature vector;

comparing the feature vectors of the first image with the feature vectors of the second image to determine matching pairs of feature vectors

performing geometric coding to encode the relative spatial positions of the feature vectors, wherein performing geometric coding comprises forming a geo-map of the first image and a geo-map of the second image;

performing spatial verification of one or more matching pairs of feature vectors using the determined relative spatial positions of the feature vectors, wherein performing spatial verification of one or more matching pairs of feature vectors comprises comparing the geo-map of the first image to the geo-map of the second image;

removing false matching pairs of feature vectors between the first image and the second image based on the spatial verification; and

comparing the remaining matching pairs of feature vectors to determine if the first image is the same as the second image.

11. The system of claim 10, wherein the system further comprises:

an off-line component, the offline component comprising a database of images;

an on-line component, the online component configured to retrieve internet images to compare to the database of images;

a feature extraction sub-component shared by the on-line component and the off-line component, wherein the feature extraction sub-component produces a reduced representation set of features, and wherein the sub-component produces the same feature extraction on the database images and the internet images; and

a feature quantization sub-component shared by the on-line component and the off-line component, wherein the feature quantization sub-component quantizes the features into feature vectors.

12. A tangible, non-transitory computer readable storage medium comprising program instructions stored thereon, wherein the program instructions are computer-executable to perform the method comprising:

extracting features from a first image and a second image;

quantizing the extracted features by creating a feature vector;

comparing the feature vectors of the first image with the feature vectors of the second image to determine matching pairs of feature vectors

performing geometric coding to encode the relative spatial positions of the feature vectors, wherein performing geometric coding comprises forming a geo-map of the first image and a geo-map of the second image;

performing spatial verification of one or more matching pairs of feature vectors using the determined relative spatial positions of the feature vectors, wherein performing spatial verification of one or more matching pairs of feature vectors comprises comparing the geo-map of the first image to the geo-map of the second image;

removing false matching pairs of feature vectors between the first image and the second image based on the spatial verification; and

comparing the remaining matching pairs of feature vectors to determine if the first image is the same as the second image.