Co-location visual pattern mining for near-duplicate image retrieval

• US 8,073,818 B2
• Filed: 10/03/2008
• Issued: 12/06/2011
• Est. Priority Date: 10/03/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Duan, Manni, Xie, Xing
• Primary Examiner(s): Dang, Thanh-Ha
• Application Number:
  US12/245,590
• Publication Number:
  US 20100088295A1
• Time in Patent Office: 1,159 Days
• Field of Search: 707/706, 707/749, 707/687, 707/692, 707/723, 707/748, 707/763
• US Class Current: 707/687
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/56 having vectorial format
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations

Abstract

Described is a technology in which image near-duplicate retrieval is performed using similarities between patterns of query image words and patterns of database image words. In general, the image retrieval problems resulting from visual polysemy are reduced by using such visual patterns. Visual word vectors and visual pattern vectors are determined for the query image and a database image. These four vectors are used to determine similarity between the database image and the query image. The similarity scores may be used for ranking and/or re-ranking the database image similarity to the query image relative to other database images'"'"' similarity scores. Also described is expanding a query visual word of the query image to a set of visual words that are visual synonyms with the query visual word, to help reduce image retrieval problems resulting from visual synonymy.

Claims

1. In a computing environment, a computer-implemented method comprising:

performing near-duplicate image retrieval with a computer processor, including detecting, with the computer processor, visual patterns in images, representing the visual patterns as visual pattern vectors, and using the visual pattern vectors and visual word vectors to determine, with the computer processor, similarity between images by ranking database images according to a similarity of each given database image with a query image, including by obtaining a query visual pattern vector for the query image, and for each given image, determining a visual pattern vector and computing a visual pattern-based similarity score for the given image by selecting a set of most similar database images based on a ranking of the database images according to the visual pattern-based similarity scores, and re-ranking the set of most similar database images by evaluating similarity for each specific image in the set of most similar database images via a visual word vector corresponding to the specific image and a query visual word vector corresponding to the query image.

2. The computer-implemented method of claim 1 further comprising, reducing visual synonymy effects in the near-duplicate image retrieval by extending a query visual word to a set of visual words that are visual synonyms with the query visual word.

3. The computer-implemented method of claim 1 wherein using the visual pattern vectors and visual word vectors to determine similarity between images comprises, ranking database images according to similarity of each database image with a query image, including by obtaining the query visual word vector for the query image, and for each given database image, determining a visual word vector and computing a visual word-based similarity score by evaluating similarity via the visual word vector for the given database image and the query visual word vector.

4. The computer-implemented method of claim 3 wherein using the visual pattern vectors and visual word vectors to determine similarity between images further comprises, selecting a set of most similar database images based on a ranking of the database images according to the visual word-based similarity scores, and re-ranking the set of most similar database images by evaluating similarity for each specified image via a visual pattern vector corresponding to the specified image and a query visual pattern vector corresponding to the query image.

5. The computer-implemented method of claim 1 further comprising, ranking images according to similarity scores computed based upon visual word vectors corresponding to the images, and re-ranking at least some of the visual word vector-ranked database images by computing similarity scores based upon visual pattern vectors corresponding to the images.

6. The computer-implemented method of claim 1 wherein performing the near-duplicate image retrieval comprises, ranking images by computing combined similarity scores between pairs of images, including, for each pair of images, combining a similarity score computed from visual word vectors of the images with a similarity score computed from visual word vectors of the images.

7. The computer-implemented method of claim 1 wherein performing the near-duplicate image retrieval comprises merging a visual word vector with a visual pattern vector for a first image into a first merged vector, merging a visual word vector with a visual pattern vector for a second image into a second merged vector, and determining a similarity score from the first merged vector and the second merged vector.

8. The computer-implemented method of claim 1 further comprising, mining quantitative patterns from database images, including images in which the patterns contain duplicate items.

9. In a computing environment, a system comprising:

a query image processing subsystem that determines a query image word vector for the query image and a query pattern word vector for the query image, and a database image ranking subsystem that ranks database images with respect to similarity of each database image to the query image, including obtaining an image word vector and a pattern word vector for each database image, and, for each database image, using the query image word vector for the query image, the query pattern word vector for the query image, the image word vector for the database image, and the pattern word vector for the database image to determine a score for the similarity of each database image to the query image wherein the database image ranking subsystem uses the query image word vector for the query image, the query pattern word vector for the query image, the image word vector for the database image, and the pattern word vector for the database image to determine a score of the similarity of the database image to the query image by ranking database images according to a similarity score, for each image with the query image via visual word vector-based scoring, selecting a set of most similar images based on the ranking according to the visual word vector-based scoring, and re-ranking the set according to the similarity of each image pattern vector-based similarity score with respect to the query pattern word vector; and

the system further comprising a computer processor being a functional component of the system and activated by the query image processing system and database image ranking system to facilitate determining the query image word vector and query pattern word vector and ranking the database images.

10. The system of claim 9 wherein the query image processing subsystem includes a query expanding mechanism that extends a query visual word of the query image to a set of visual words that are visual synonyms with the query visual word, for use in determining similarity with the database images.

11. The system of claim 9 wherein the database image ranking subsystem uses the query image word vector for the query image, the query pattern word vector for the query image, the image word vector for the database image, and the pattern word vector for the database image to determine a score for the similarity of each database image to the query image by ranking database images according to a similarity score, for each image with the query image via visual pattern vector-based scoring, selecting a set of most similar images based on the ranking according to the visual pattern vector-based scoring, and re-ranking the set according to the word vector-based similarity score for each image with respect to the query image word vector.

12. The system of claim 9 wherein the database image ranking subsystem uses the query image word vector for the query image, the query pattern word vector for a given query image, the image word vector for the given database image, and the pattern word vector for the database image to determine a score for the similarity of the given database image to the query image by adding a word-based similarity score based upon the image word vector of an image and the query image word vector to a pattern-based similarity score based upon the pattern word vector of the image and the query pattern word vector to determine an overall similarity score.

13. The system of claim 9 wherein the database image ranking subsystem uses the query image word vector for the query image, the query pattern word vector for the query image, the image word vector for a given database image, and the pattern word vector for the given database image to determine a score for similarity of the given database image to the query image by merging the image word vector and pattern word vector of an image into a first merged vector, merging the query image word vector and with the query pattern word vector into a second merged vector, and determining a similarity score based on similarity between the first merged vector and the second merged vector.

14. The system of claim 9 further comprising a database image indexing subsystem that determines visual pattern vectors and visual word vectors for the database images.

15. One or more computer storage media having computer-executable instructions, the computer storage media being a hardware storage media, the instructions, when executed, perform steps, comprising:

receiving a query image;

determining a visual word vector for the query image;

determining a visual pattern vector for the query image;

determining similarity with each image of a set of database images, including, for each image of the set of database images, computing a first similarity score by evaluating the visual word vector for the query image with a visual word vector for each database image and computing a second similarity score by evaluating the visual pattern vector for the query image with a visual pattern vector for each database image; and

using the first and second similarity scores according to a usage model by ranking the set of database images based on one of the first and second similarity scores, and re-ranking a selected set of highest ranked database images in the set of database images based on another of the first and second similarity score.

16. The one or more computer storage media of claim 15 wherein using the first and second similarity scores according to the usage model comprises ranking database images based on the first and second similarity scores according to a pre-ranking usage model, according to a re-ranking usage model, according to a similarity merging usage model, or according to a vector merging usage model.

17. The one or more computer storage media of claim 15 having further computer-executable instructions comprising, expanding a query visual word of the query image to a set of visual words that are visual synonyms with the query visual word.