System and method to match images using topologically equivalent correspondences

• US 8,401,342 B2
• Filed: 01/16/2009
• Issued: 03/19/2013
• 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 A., Tanguay, Donald
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): HEIDEMANN, JASON E
• Application Number:
  US12/321,235
• Publication Number:
  US 20100183229A1
• Time in Patent Office: 1,523 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 with a plurality of images, an image being represented by a set of feature points and a corresponding set of feature vectors, the method comprising:

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

finding putatively corresponding images from the plurality of images based at least in part on a number of putative correspondences between each of the plurality of images and the query image being greater than a predefined value;

performing a topological equivalence test on each of a plurality of subsets of the putative correspondences between each of the putatively corresponding images and the query image; and

finding candidate matches by performing motion estimation using each of the plurality of subsets of the putative correspondences between each of the putatively corresponding images and the query image passing the topological equivalence test.

2. The method of claim 1, wherein the putatively corresponding images are further based on the number of the putative correspondences being greater than a value based on a number of the putative correspondences found in others of the plurality of images.

3. The method of claim 1, wherein the putative correspondences comprise each feature vector of one of the plurality of images and each feature vector of the query image having a vector dot product that is greater than a predefined value.

4. The method of claim 1, wherein performing the topological equivalence test on one subset of the plurality of subsets of the putative correspondences between one of the putatively corresponding images and the query image comprises:

connecting two feature points in the one of the putatively corresponding images to form a first straight line, the two feature points selected from the one subset;

connecting two corresponding feature points in the query image to form a second straight line;

for one or more remaining feature points in the one subset;

computing a first signed distance of one of the one or more remaining feature points in the one of the putatively corresponding images from the first straight line;

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

if the one of the one or more remaining feature points lies on the first straight line or the corresponding remaining feature point lies on the second straight line, performing a same-order test, the same-order test including determining that the one subset is not topologically equivalent based on an order of the two feature points and the remaining feature point with respect to the first straight line and an order of the two corresponding feature points and the corresponding remaining feature point with respect to the second straight line not being the same; and

if the one of the one or more remaining feature points does not lie on the first straight line and the corresponding remaining feature point does not lie on the second straight line, performing a same-side test, the same-side test including determining that the one 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

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

5. The method of claim 1, further comprising:

determining a coverage of the query image and a coverage of each of the candidate matches; and

rejecting one of the candidate matches when a maximum of the coverage of the one of the candidate matches and the coverage of the query image is less than a predefined threshold.

6. The method of claim 1, wherein performing the motion estimation on one subset of the plurality of subsets of the putative correspondences between one of the putatively corresponding images and the query image comprises:

computing a transformation between corresponding feature points in the one subset of the plurality of subsets of the putative correspondences;

computing a set of inliers from each of the putative correspondences between the one of the putatively corresponding images and the query image using the transformation; and

retaining the transformation as a best transformation based on a number of the set of inliers of the transformation being greater than a number of inliers of a current best transformation.

7. The method of claim 6, further comprising:

performing an orientation consistency test on the one subset of the plurality of subsets of the putative correspondences.

8. The method of claim 7, wherein performing the orientation consistency test on the one subset of the plurality of subsets of the putative correspondences comprises:

determining offset points for each of the feature points in one of two images, wherein each offset point is displaced from the feature point in a direction of an orientation of the feature point, the feature points selected from a subset of the plurality of subsets of the putative correspondences between one of the putatively corresponding images and the query image, the two images comprising the one of the putatively corresponding images and the query image;

applying the transformation to the offset points and the feature points in the one of the two images;

determining expected orientations based on displacements between the feature points in another of the two images and the transformed offset points; and

discarding the transformation when one of the expected orientations differs from an orientation of one of the transformed feature points in the one of the two images by a predefined limit.

9. The method of claim 1, further comprising identifying one or more sequences of final matches from the candidate matches by selecting a candidate match whose number of inliers is greater than a predefined number of inliers and whose approximation error is less than a predefined threshold.

10. The method of claim 1, further comprising identifying one or more sequences of final matches from the candidate matches.

11. The method of claim 10, wherein identifying the one or more sequences of the final matches comprises:

sorting the candidate matches by decreasing number of inliers;

creating at least one sequence of final matches with a first candidate match having the greatest number of inliers as a first element of the at least one sequence;

appending each remaining candidate match to an existing sequence if the area of the intersection of a polygon enclosing the inliers of the remaining candidate match and a polygon enclosing the inliers of a first element of an existing sequence is greater than a predefined threshold; and

creating a new sequence including the remaining candidate match when the area of the intersection of a polygon enclosing the inliers of the remaining candidate match and a polygon enclosing the inliers of the first element of an existing sequence falls below a predefined threshold for all existing sequences.

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

13. A system for matching a query image with a plurality of images, an image being represented by a set of feature points and a corresponding set of feature vectors, the system comprising:

a putative correspondence module for finding putatively corresponding images from the plurality of images based at least in part on a number of putative correspondences between each of the plurality of images and the query image being greater than a predefined value;

a topological equivalence module for performing a topological equivalence test on each of a plurality of subsets of the putative correspondences between each of the putatively corresponding images and the query image;

a motion estimation module for performing motion estimation using each of the plurality of subsets of the putative correspondences between each of the putatively corresponding images and the query image passing the topological equivalence test; and

a final identification module for identifying one or more sequences of the putatively corresponding images that match the query image based on the motion estimation.

14. The system of claim 13, wherein the putative correspondences comprise each feature vector of one of the plurality of images and each feature vector of the query image having a vector product that is greater than a predefined value.

15. The system of claim 13, wherein the motion estimation module comprises an orientation consistency check module adapted for:

determining offset points for each of the feature points in one of two images, wherein each offset point is displaced from the feature point in a direction of an orientation of the feature point, the feature points selected from a subset of the plurality of subsets of the putative correspondences between one of the putatively corresponding images and the query image, the two images comprising the one of the putatively corresponding images and the query image;

applying the transformation to the offset points and the feature points in the one of the two images;

determining expected orientations based on displacements between the feature points in another of the two images and the transformed offset points; and

discarding the transformation when one of the expected orientations differs from an orientation of one of the transformed feature points in the one of the two images by a predefined limit.

16. The system of claim 13, wherein the topological equivalence module for performing a topological equivalence test on each of a plurality of subsets of the putative correspondences between each of the putatively corresponding images and the query image is adapted for:

connecting two feature points in one of the putatively corresponding images to form a first straight line, the two feature points selected from the one subset;

connecting two corresponding feature points in the query image to form a second straight line;

for one or more remaining feature points in the one subset;

computing a first signed distance of one of the one or more remaining feature points in the one of the putatively corresponding images from the first straight line;

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

if the one of the one or more remaining feature points lies on the first straight line or the corresponding remaining feature point lies on the second straight line, performing a same-order test, the same-order test including determining that the one subset is not topologically equivalent based on an order of the two feature points and the remaining feature point with respect to the first straight line and an order of the two corresponding feature points and the corresponding remaining feature point with respect to the second straight line not being the same; and

if the one of the one or more remaining feature points does not lie on the first straight line and the corresponding remaining feature point does not lie on the second straight line, performing a same-side test, the same-side test including determining that the one 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

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

17. The system of claim 13, wherein the final identification module is adapted to select one or more images matching the query image when a number of inliers for a candidate match is greater than a predefined number of inliers, and the candidate match has an approximation error less than a predefined threshold.

18. The system of claim 13, wherein the final identification module further comprises a coverage module for determining a coverage of the query image and a coverage of a candidate match, the final identification module rejecting the candidate match where a maximum of the coverage of the candidate match and the coverage of the query image is less than a predefined threshold.

19. The system of claim 13, wherein the motion estimation module calculates motion estimation by using a Random Sample Consensus (RANSAC) algorithm or a variation thereof.

20. A non-transitory computer-readable storage medium including instructions for matching a query image with a plurality of images, an image being represented by a set of feature points and a corresponding set of feature vectors, the instructions when executed by a processor of a computing system, cause the computing system to:

find putatively corresponding images from the plurality of images based at least in part on a number of putative correspondences between each of the plurality of images and the query image being greater than a predefined value;

perform a topological equivalence test on each of a plurality of subsets of the putative correspondences between each of the putatively corresponding images and the query image; and

find candidate matches by performing motion estimation using each of the plurality of subsets of the putative correspondences between each of the putatively corresponding images and the query image passing the topological equivalence test.

21. The non-transitory computer-readable storage medium of claim 20, wherein the putative correspondences comprise each feature vector of one of the plurality of images and each feature vector of the query image having a vector dot product that is greater than a predefined value.

22. The non-transitory computer-readable storage medium of claim 20, wherein the instructions when executed further cause the computing system to:

determine offset points for each of the feature points in one of two images, wherein each offset point is displaced from the feature point in a direction of an orientation of the feature point, the feature points selected from a subset of the plurality of subsets of the putative correspondences between one of the putatively corresponding images and the query image, the two images comprising the one of the putatively corresponding images and the query image;

apply the transformation to the offset points and the feature points in the one of the two images;

determine expected orientations based on displacements between the feature points in the other of the two images and the transformed offset points corresponding to the feature points in the one of the two images; and

discard the transformation when one of the expected orientations differs form an orientation of one of the transformed feature points in the one of the two images by a predefined limit.

23. The non-transitory computer-readable storage medium of claim 20, wherein the instructions when executed to perform the topological equivalence on one subset of the plurality of subsets of the putative correspondences between one of the putatively corresponding images and the query image comprise instructions when executed to cause the computing system to:

connect two feature points in the one of the putatively corresponding images to form a first straight line, the two feature points selected from the one subset;

connect two corresponding feature points in the query image to form a second straight line;

for one or more remaining feature points in the one subset;

compute a first signed distance of one of the one or more remaining feature points in the one of the putatively corresponding images from the first straight line;

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

if the one of the one or more remaining feature points lies on the first straight line or the corresponding remaining feature point lies on the second straight line, perform a same-order test, the same-order test including determining that the one subset is not topologically equivalent based on an order of the two feature points and the remaining feature point with respect to the first straight line and an order of the two corresponding feature points and the corresponding remaining feature point with respect to the second straight line not being the same; and

if the one of the one or more remaining feature points does not lie on the first straight line and the corresponding remaining feature point does not lie on the second straight line, perform a same-side test, the same-side test including determining that the one 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 one subset is topologically equivalent based on successfully evaluating each of the one or more remaining feature points using one of the same-order test or the same-side test.

24. The non-transitory computer-readable storage medium of claim 20, wherein the instructions when executed further cause the computing system to identify one or more sequences of final matches from the candidate matches by selecting a candidate match whose number of inliers is greater than a predefined number of inliers and whose approximation error is less than a predefined threshold.

25. The non-transitory computer-readable storage medium of claim 24, wherein the instructions when executed further cause the computing system to:

determine a coverage of the query image and a coverage of each of the candidate matches; and

reject one of the candidate matches when a maximum of the coverage of the candidate match and the coverage of the query image is less than a predefined threshold.

26. The non-transitory computer-readable storage medium of claim 20, wherein the motion estimation is based on a Random Sample Consensus (RANSAC) algorithm or a variation thereof.