CO-LOCATION VISUAL PATTERN MINING FOR NEAR-DUPLICATE IMAGE RETRIEVAL

• US 20100088295A1
• Filed: 10/03/2008
• Published: 04/08/2010
• 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
• Granted Patent: US 8,073,818 B2
• Time in Patent Office: Days
• US Class Current: 707/705
• 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 method comprising, performing near-duplicate image retrieval, including by detecting visual patterns in images, representing the visual patterns as visual pattern vectors, and using the visual pattern vectors and visual word vectors to determine similarity between images.

2. The 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 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 each image'"'"'s similarity with a query image, including by obtaining a query visual pattern vector for the query image, and for each image, determining a visual pattern vector and computing a visual pattern-based similarity score by evaluating similarity between the visual pattern vector for that image and the query visual pattern vector.

4. The 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 according to their visual pattern-based similarity scores, and re-ranking the set of most similar database images by evaluating similarity for each image via a visual word vector corresponding to that image and a query visual word vector corresponding to the query image.

5. The 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 each image'"'"'s similarity with a query image, including by obtaining a query visual word vector for the query image, and for each image, determining a visual word vector and computing a visual word-based similarity score by evaluating similarity via the visual word vector for that image and the query visual word vector.

6. The method of claim 5 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 according to their visual word-based similarity scores, and re-ranking the set of most similar database images by evaluating similarity for each image via a visual pattern vector corresponding to that image and a query visual pattern vector corresponding to the query image.

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

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

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

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

11. 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 each database image'"'"'s similarity 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 that database image'"'"'s similarity to the query image.

12. The system of claim 11 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.

13. The system of claim 11 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 that database image'"'"'s similarity to the query image by ranking database images according to each image'"'"'s similarity score with the query image via visual pattern vector-based scoring, selecting a set of most similar images based on the visual pattern vector-based ranking, and re-ranking the set according to each image'"'"'s word vector-based similarity score with respect to the query word vector.

14. The system of claim 11 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 that database image'"'"'s similarity to the query image by ranking database images according to each image'"'"'s similarity score with the query image via visual word vector-based scoring, selecting a set of most similar images based on the visual word vector-based ranking, and re-ranking the set according to each image'"'"'s pattern vector-based similarity score with respect to the query pattern vector.

15. The system of claim 11 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 that database image'"'"'s similarity to the query image by adding a word-based similarity score based upon the visual word vector of an image and the query visual word vector to a pattern-based similarity score based upon the visual pattern vector of the image and the query visual pattern word vector to determine an overall similarity score.

16. The system of claim 11 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 that database image'"'"'s similarity to the query image by merging an image'"'"'s visual word vector and pattern vector into a first merged vector, merging the query visual word vector and with the query visual pattern vector into a second merged vector, and determining a similarity score based on similarity between the first merged vector and the second merged vector.

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

19. The one or more computer-readable media of claim 17 wherein using the first and second similarity scores according to a 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.

18. One or more computer-readable media having computer-executable instructions, which 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, 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 that database image; and

using the first and second similarity scores according to a usage model.

20. The one or more computer-readable media of claim 18 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.