Image matching system using topologically equivalent correspondences

• US 8,867,866 B2
• Filed: 04/14/2014
• Issued: 10/21/2014
• Est. Priority Date: 01/16/2009
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Ruzon, Mark R., Tanguay, Donald
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): HEIDEMANN, JASON E
• Application Number:
  US14/252,566
• Publication Number:
  US 20140226868A1
• Time in Patent Office: 190 Days
• Field of Search: None
• US Class Current: 382/305
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A method, system and computer program product for matching images is provided. The images to be matched are represented by feature points and feature vectors and orientations associated with the feature points. First, putative correspondences are determined by using feature vectors. A subset of putative correspondences is selected and the topological equivalence of the subset is determined. The topologically equivalent subset of putative correspondences is used to establish a motion estimation model. An orientation consistency test is performed on the putative correspondences and the corresponding motion estimation transformation that is determined, to avoid an infeasible transformation. A coverage test is performed on the matches that satisfy orientation consistency test. The candidate matches that do not cover a significant portion of one of the images are rejected. The final match images are provided in the order of decreasing matching, in case of multiple images satisfying all the test requirements.

Claims

1. A computer-implemented method for matching a query image, comprising:

under control of one or more computer systems configured with executable instructions,

determining one or more corresponding images each having at least a respective portion of features that correspond to a portion of features of the query image; and

for each corresponding image of the one or more corresponding images,

determining one or more respective subsets of the respective portion of the features of the corresponding image that are topologically equivalent to a the subset of the portion of features of the query image;

generating one or more transformations each corresponding to a respective subset of the features of the corresponding image that are determined to be topologically equivalent to the subset of the features of the query image; and

determining whether the corresponding image matches the query image based at least in part upon performing motion estimation using each transformation corresponding to the respective subset of the features of the corresponding image that are determined to be topologically equivalent.

2. The computer-implemented method of claim 1, wherein determining the one or more corresponding images includes:

determining the features of the query image; and

for each image of a plurality of images,

determining the respective features of the image;

determining a number of the features of the query image that are visually similar to the respective features of the image; and

determining that the image is one of the one or more corresponding images based upon the number of the features meeting a specified threshold.

3. The computer-implemented method of claim 2, wherein a feature of the query image is determined to be visually similar to a respective feature of the image based upon a vector dot product, of the feature of the query image and the respective feature of the image, being greater than a predefined value.

4. The computer-implemented method of claim 1, wherein determining the one or more respective subsets of the features of the corresponding image that are topologically equivalent to the subset of the features of the query image include:

for each corresponding image of the one or more corresponding images,

connecting two features in the subset of the features of the query image to form a first straight line;

connecting two respective features in the respective subset of the features of the corresponding image to form a second straight line;

for one or more remaining features in the respective subset of the features of the query image,

computing a first signed distance of a respective remaining feature from the first straight line;

computing a second signed distance of a remaining feature in the query image from the second straight line;

upon the respective remaining feature lying on the first straight line or the remaining feature lying on the second straight line, performing a same-order test including determining that the respective subset is not topologically equivalent based on a first order of the two respective features and the respective remaining feature with respect to the first straight line and a second order of the two features and the remaining feature with respect to the second straight line not being the same; and

upon the respective remaining feature not lying on the first straight line and the remaining feature not lying on the second straight line, performing a same-side test including determining that the respective subset is not topologically equivalent based on a sign or the first signed distance and a sign of the second signed distance not being equal; and

determining that the respective subset is topologically equivalent based on successfully evaluating each of the one or more remaining features using one of the same-order test or the same-side test.

5. The computer-implemented method of claim 1, further comprising:

for each corresponding image of the one or more corresponding images,

determining whether each transformation of the one or more transformations is consistent with respect to orientations of the subset of the features of the query image,

wherein the motion estimation is performed using each transformation determined to be consistent with respect to the orientations of the subset of the features of the query image.

6. The computer-implemented method of claim 5, wherein determining whether each transformation is consistent with respect to the orientations of the subset of the features of the query image includes:

for each feature in the subset of the features of the query image and for each respective feature in the respective subset of the features of the corresponding image,

determining a first offset by displacing the feature from the respective feature in a direction of an orientation of the feature;

applying the transformation to the first offset to generate a second offset; and

determining the transformation to be consistent upon the orientation of the respective feature and the orientation of the second offset being within a predefined tolerance limit.

7. The computer-implemented method of claim 1, wherein determining whether the corresponding image matches the query image includes:

for each corresponding image of the one or more corresponding images and for each transformation of the one or more transformations,

determining a set of inliers based on the motion estimation using the transformation; and

determining a first coverage by the set of inliers with respect to the corresponding image and a second coverage by the set of inliers with respect to the query image,

wherein the corresponding image matches the query image based at least in part upon a ratio of the first coverage and the second coverage being within a specified threshold.

8. The computer-implemented method of claim 7, wherein the first coverage and the second coverage each comprise at least one of:

(a) a polygon formed by a convex hull of the set of inliers or (b) a smallest axis-aligned bounding rectangle that encloses the set of inliers.

9. The computer-implemented method of claim 1, wherein the motion estimation is based on a Random Sample Consensus (RANSAC) algorithm or a variation thereof.

10. A non-transitory computer-readable storage medium for matching a query image including instructions that, upon being executed by at least one processor of a computing device, cause the computing device to:

determine one or more corresponding images each having at least a respective portion of features that correspond to a portion of features of the query image; and

for each corresponding image of the one or more corresponding images,

determine one or more respective subsets of the respective portion of the features of the corresponding image that are topologically equivalent to a the subset of the portion of features of the query image;

generate one or more transformations each corresponding to a respective subset of the features of the corresponding image that are determined to be topologically equivalent to the subset of the features of the query image; and

determine whether the corresponding image matches the query image based at least in part upon performing motion estimation using each transformation corresponding to the respective subset of the features of the corresponding image that are determined to be topologically equivalent.

11. The non-transitory computer-readable storage medium of claim 10, wherein the instructions, upon being executed to cause to the computing device to determine the one or more corresponding images, includes causing the computing device to:

determining the features of the query image; and

for each image of a plurality of images,

determining the respective features of the image;

determining a number of the features of the query image that are visually similar to the respective features of the image; and

determining that the image is one of the one or more corresponding images based upon the number of the features meeting a specified threshold.

12. The non-transitory computer-readable storage medium of claim 11, wherein a feature of the query image is determined to be visually similar to a respective feature of the image based upon a vector dot product, of the feature of the query image and the respective feature of the image, being greater than a predefined value.

13. The non-transitory computer-readable storage medium of claim 10, wherein the instructions, upon being executed to cause to the computing device to determine the one or more respective subsets of the features of the corresponding image that are topologically equivalent to the subset of the features of the query image include:

for each corresponding image of the one or more corresponding images,

connect two features in the subset of the features of the query image to form a first straight line;

connect two respective features in the respective subset of the features of the corresponding image to form a second straight line;

for one or more remaining features in the respective subset of the features of the query image,

compute a first signed distance of a respective remaining feature from the first straight line;

compute a second signed distance of a remaining feature in the query image from the second straight line;

upon the respective remaining feature lying on the first straight line or the remaining feature lying on the second straight line, perform a same-order test including determining that the respective subset is not topologically equivalent based on a first order of the two respective features and the respective remaining feature with respect to the first straight line and a second order of the two features and the remaining feature with respect to the second straight line not being the same; and

upon the respective remaining feature not lying on the first straight line and the remaining feature not lying on the second straight line, perform a same-side test including determining that the respective subset is not topologically equivalent based on a sign of the first signed distance and a sign of the second signed distance not being equal; and

determine that the respective subset is topologically equivalent based on successfully evaluating each of the one or more remaining features using one of the same-order test or the same-side test.

14. The non-transitory computer-readable storage medium of claim 10, wherein the instructions, upon being executed by the at least one processor, further cause the computing device to:

for each corresponding image of the one or more corresponding images,

determine whether each transformation of the one or more transformations is consistent with respect to orientations of the subset of the features of the query image,

wherein the motion estimation is performed using each transformation determined to be consistent with respect to the orientations of the subset of the features of the query image.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions, upon being executed to cause to the computing device to determine whether each transformation is consistent with respect to the orientations of the subset of the features of the query image, includes causing the computing device to:

for each feature in the subset of the features of the query image and for each respective feature in the respective subset of the features of the corresponding image,

determine a first offset by displacing the feature from the respective feature in a direction of an orientation of the feature;

apply the transformation to the first offset to generate a second offset; and

determine the transformation to be consistent upon the orientation of the respective feature and the orientation of the second offset being within a predefined tolerance limit.

16. The non-transitory computer-readable storage medium of claim 10, wherein the instructions, upon being executed to cause to the computing device to determine whether the corresponding image matches the query image, includes causing the computing device to:

for each corresponding image of the one or more corresponding images and for each transformation of the one or more transformations,

determine a set of inliers based on the motion estimation using the transformation; and

determine a first coverage by the set of inliers with respect to the corresponding image and a second coverage by the set of inliers with respect to the query image,

wherein the corresponding image matches the query image based at least in part upon a ratio of the first coverage and the second coverage being within a specified threshold.

17. The non-transitory computer-readable storage medium of claim 16, wherein the first coverage and the second coverage each comprise at least one of:

(a) a polygon formed by a convex hull of the set of inliers or (b) a smallest axis-aligned bounding rectangle that encloses the set of inliers.

18. A system for matching a query image, comprising:

at least one processor; and

memory including instructions that, upon being executed by the at least one processor, cause the system to;

obtain a request to match at least a portion of content in the query image to a respective portion of content in one or more of a plurality of database images;

determine one or more corresponding images, from among the plurality of database images, each having at least a respective portion of features that correspond to a portion of features of the query image;

for each corresponding image of the one or more corresponding images,

determine one or more respective subsets of the respective portion of the features of the corresponding image that are topologically equivalent to a subset of the portion of features of the query image;

generate one or more transformations each corresponding to a respective subset of the features of the corresponding image that are determined to be topologically equivalent to the subset of the features of the query image; and

determine whether the corresponding image matches the query image based at least in part upon performing motion estimation using each transformation corresponding to the respective subset of the features of the corresponding image that are determined to be topologically equivalent; and

provide information relating to the at least one corresponding image determined to match the query image in response to the request.

19. The system of claim 18, wherein the instructions, upon being executed by the at least one processor, further cause the system to:

for each corresponding image of the one or more corresponding images,

determine whether each transformation of the one or more transformations is consistent with respect to orientations of the subset of the features of the query image,

wherein the motion estimation is performed using each transformation determined to be consistent with respect to the orientations of the subset of the features of the query image.

20. The system of claim 18, wherein the instructions, upon being executed to cause the system to determine whether the corresponding image matches the query image, include causing the system to:

for each corresponding image of the one or more corresponding images and for each transformation of the one or more transformations,

determine a set of inliers based on the motion estimation using the transformation; and

determine a first coverage by the set of inliers with respect to the corresponding image and a second coverage by the set of inliers with respect to the query image,

wherein the corresponding image matches the query image based at least in part upon a ratio of the first coverage and the second coverage being within a specified threshold.