Generating search results based on duplicate image detection

• US 7,860,317 B2
• Filed: 04/04/2006
• Issued: 12/28/2010
• Est. Priority Date: 04/04/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Fan, Xin, Ma, Wei-Ying, Xie, Xing, Zhou, Yinghua
• Primary Examiner(s): Werner; Brian P
• Assistant Examiner(s): Drennan; Barry
• Application Number:
  US11/278,575
• Publication Number:
  US 20070237426A1
• Time in Patent Office: 1,729 Days
• Field of Search: 382/305
• US Class Current: 382/195
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A method and system for searching for content relating to a target or query image by identifying duplicate images with associated content is provided. An image search system identifies visual parts of objects within the target image based on analysis of two or more versions of the target image. The image search system identifies visual parts based on analysis of the versions. The image search system then identifies images of an image database that have visual parts that are similar to the visual parts of the target image. The image search system may rank the identified images based on their likelihood of being duplicates of the target image and provide their associated content as the search result ordered according to the ranking of the images.

Claims

1. A system for identifying an image that matches a target image based on visual parts of the target image, comprising:

a collection of images, each image having salient points, each salient point having a feature vector;

a first version and a second version of the target image, each version having salient points;

a memory storing computer-executable instructions of

a component that identifies matching points, each matching point being a salient point of the first version of the target image for which there is only one salient point of the second version of the target image with a similar feature, such that a salient point of the first version is not a matching point when the similarity between that salient point of the first version and the most similar salient point of the second version is too close to the similarity between that salient point of the first version and the second most similar salient point of the second version;

a component that identifies groups of matching points such that the matching points are proximate to each other in the first version and their matching points are also proximate to each other in the second version wherein a group represents a visual part, the component identifies a group by;

selecting a first matching point;

selecting a second matching point;

selecting a third matching point; and

when the second matching point and the third matching point are within a certain radius of the first matching point in both the first version and the second version, designating the first matching point, the second matching point, and the third matching point as being a group; and

a component that identifies an image from the collection of images that matches the target image by comparing features of salient points of the images to features of the salient points of the visual parts of the target image, the image being identified based on number of salient points of the image that match salient points of the visual parts of the target image;

a component that ranks identified images based on the number of visual parts of the identified images that correspond to a visual part of the target image; and

a processor for executing the computer-executable instructions stored in the memory.

2. The system of claim 1 including:

a component that identifies salient points within each version of the target image; and

a component that generates a feature to represent each salient point.

3. The system of claim 2 wherein the component that identifies salient points and the component that generates a feature are based on a scale-invariant feature transform algorithm.

4. The system of claim 1 wherein a group includes three matching points.

5. The system of claim 1 wherein similarity is based on a distance metric in feature space.

6. The system of claim 1 including a component that identifies salient points within each version of the target image and generates a feature to represent each salient point based on a scale-invariant feature transform algorithm, and wherein a group includes three matching points.

7. A system for identifying whether an image is similar to a target image having a first version and a second version, comprising:

a memory storing computer-executable instructions of

a component that identifies visual parts of the target image, a visual part being identified as salient points of the first version with a feature of each salient point being similar to a feature of a matching salient point of the second version and the salient points of a visual part being proximate to each other in the first version and their matching points being proximate to each other in the second version, a visual part comprising three matching points such that two of the matching points are within a certain radius of the third matching point in both the first version and the second version; and

a component that determines whether an image is similar to the target image by identifying visual parts of the target image that are also visual parts of the image; and

a processor for executing the computer-executable instructions stored in the memory.

8. The system of claim 7 including an image store that maps features of salient points of images to images and wherein the component that determines selects candidate images from the image store that have features of salient points that are similar to features of the salient points of the visual part and indicates that an image is similar to the target image based on a count of visual parts of the target image that is similar to visual parts of the image.

9. The system of claim 7 wherein the component that determines whether an image is similar to the target image factors in proximity to each other of salient points of the image with similar features.

10. The system of claim 7 including a component that generates features for salient points of an image.

11. The system of claim 10 including a component that generates a mapping of features of salient points of images to images.

12. The system of claim 7 wherein a salient point of the second version does not match a salient point of the first version when their features are similar to the feature of another salient point of the second version.

13. The system of claim 7 wherein similarity is based on a distance metric in feature space.

14. The system of claim 7 including a component that identifies salient points within each version of the image and generates a feature to represent each salient point based on a scale-invariant feature transform algorithm, wherein a salient point of the second version does not match a salient point of the first version when their features are similar to the feature of another salient point of the second version, and wherein a group includes three matching points.

15. A system for searching for content, comprising:

a content store that maps features of salient points of images to images and maps images to content;

a memory storing computer-executable instructions of

a component that receives a first version and a second version of a target image;

a component that generates features of salient points of the target image;

a component that identifies matching points of the target image by comparing features of salient points of the first version to features of salient points of the second version, such that a salient point of the first version is not a matching point when the similarity between that salient point of the first version and the most similar salient point of the second version is too close to the similarity between that salient point of the first version and the second most similar salient point of the second version;

a component that identifies visual parts of the target image as a group of three or more matching points based on proximity of salient points of the matching points of the group to each other within a version of the target image, such that each of the matching points of a group are within a certain radius of another matching point of the group in both the first version and the second version;

a component that identifies images with features of salient points that are similar to the features of the salient points of the visual parts of the target image; and

a component that provides the content associated with the identified images as a search result; and

a processor for executing the computer-executable instructions stored in the memory.

16. The system of claim 15 wherein a visual part is identified as salient points of the first version with a feature of each salient point being similar to a feature of a matching salient point of the second version and the salient points of a visual part being proximate to each other and their matching points being proximate to each other.

17. The system of claim 15 wherein the identified images are ranked according to a count of the corresponding visual parts.