Image matching using orientational consistency

• US 8,548,279 B1
• Filed: 02/21/2013
• Issued: 10/01/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: Tanguay, Donald, Ruzon, Mark Andrew
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): HEIDEMANN, JASON E
• Application Number:
  US13/773,451
• Time in Patent Office: 222 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 an image to one or more of a plurality of images, comprising:

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

determining one or more of a plurality of images putatively corresponding to a first image, each putatively corresponding image having a plurality of putative correspondences with the first image;

for each putatively corresponding image and for each transformation of one or more transformations corresponding to one or more subsets of the plurality of putative correspondences between the first image and the putatively corresponding image, performing an orientation consistency test on the transformation to determine validity of the transformation; and

determining one or more matching images from the one or more of the plurality of images putatively corresponding to the first image based at least in part upon performing motion estimation using at least one of the one or more transformations determined to be valid according to the orientation consistency test.

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

for each putatively corresponding image, performing a topological equivalence test on each subset of the one or more subsets of the plurality of putative correspondences between the first image and the putatively corresponding image to determine validity of the subset,

wherein performing the orientation consistency on each transformation of the one or more transformations corresponding to the one or more subsets of the plurality of putative correspondences includes performing the orientation consistency on each subset determined to be valid according to the topological equivalence test.

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

performing a coverage test for each putatively corresponding image,

wherein determining the one or matching images includes determining that a first coverage of the putatively corresponding image with respect to a second coverage of the first image meets a predefined threshold.

4. The computer-implemented method of claim 1, wherein performing the orientation consistency test on each transformation of the one or more transformation comprises:

for each feature point and putatively corresponding feature point in one of the one or more subsets of the plurality of putative correspondences corresponding to the transformation,

determining a first offset point by displacing the feature point from the putatively corresponding feature point in a direction of an orientation of the feature point;

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

determining the transformation to be valid when an orientation of the corresponding feature point and an orientation of the second offset point are within a predefined tolerance limit.

5. The computer-implemented method of claim 4, wherein the predefined tolerance limit is less than or equal to 0.1 radians.

6. The computer-implemented method of claim 1, wherein determining the one or more of the plurality of images putatively corresponding to the first image comprises:

determining first feature points of the first image; and

for each second image of the plurality of images,

determining second feature points of the second image;

determining that a first feature point of the first image and a second feature point of the second image comprise a putative correspondence when the first feature point and the second feature point are determined to be visually similar; and

determining that the second image comprises one of the one or more of the plurality of images putatively corresponding to the first image when a number of putative correspondences between the first image and the second images meets a specified threshold.

7. The computer-implemented method of claim 1, wherein determining the one or matching images from the one or more of the plurality of images putatively corresponding to the first image comprises:

for each putatively corresponding image,

for each transformation of the at least one of the one or more transformations determined to be valid according to the orientation consistency test,

determining a number of inliers using the transformation and the plurality of putative correspondences between the first image and the putatively corresponding image; and

retaining the transformation as a best transformation based on the number of inliers of the transformation being greater than a number of inliers of a current best transformation; and

determining the putatively corresponding image comprises one of the one or more matching images when the number of inliers of the best transformation meets a specified threshold.

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

selecting one of the one or more matching images when a number of inliers for the one of the one or more matching images is greater than a predefined number of inliers and has an approximation error less than a predefined threshold.

9. A computer-implemented method for matching a query image to one or more of a plurality of database images, comprising:

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

obtaining a request to match a query image to one or more of a plurality of database images;

determining one or more of the plurality of database images putatively corresponding to the query image, each putatively corresponding database image having a plurality of putative correspondences with the query image;

for each putatively corresponding database image and for each transformation of one or more transformations corresponding to one or more subsets of the plurality of putative correspondences between the query image and the putatively corresponding database image, performing an orientation consistency test on the transformation to determine validity of the transformation;

determining one or more matching images from the one or more of the plurality of database images putatively corresponding to query image based at least in part upon performing motion estimation using at least one of the one or more transformations determined to be valid according to the orientation consistency test; and

providing at least one of the one or more matching images in response to the request.

10. The computer-implemented method of claim 9, further comprising:

for each putatively corresponding database image, performing a topological equivalence test on each subset of the one or more subsets of the plurality of putative correspondences between the query image and the putatively corresponding database image to determine validity of the subset,

wherein performing the orientation consistency on each transformation of the one or more transformations corresponding to the one or more subsets of the plurality of putative correspondences includes performing the orientation consistency on each subset determined to be valid according to the topological equivalence test.

11. The computer-implemented method of claim 9, further comprising:

performing a coverage test for each putatively corresponding database image,

wherein determining the one or matching images includes determining that a first coverage of the putatively corresponding database image with respect to a second coverage of the query image meets a predefined threshold.

12. The computer-implemented method of claim 9, wherein performing the orientation consistency test on each transformation of the one or more transformation comprises:

for each feature point and putatively corresponding feature point in one of the one or more subsets of the plurality of putative correspondences corresponding to the transformation,

determining a first offset point by displacing the feature point from the putatively corresponding feature point in a direction of an orientation of the feature point;

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

determining the transformation to be valid when an orientation of the corresponding feature point and an orientation of the second offset point are within a predefined tolerance limit.

13. The computer-implemented method of claim 9, wherein determining the one or more of the plurality of database images putatively corresponding to the query image comprises:

determining first feature points of the query image; and

for each database image of the plurality of database images,

determining second feature points of the database image;

determining that a first feature point of the query image and a second feature point of the database image comprise a putative correspondence when the first feature point and the second feature point are determined to be visually similar; and

determining the database image comprises one of the one or more of the plurality of putatively corresponding database images when a number of putative correspondences between the query image and the database image meets a specified threshold.

14. The computer-implemented method of claim 9, wherein determining the one or matching images from the one or more of the plurality of database images putatively corresponding to the query image comprises:

for each putatively corresponding database image,

for each transformation of the at least one of the one or more transformations determined to be valid according to the orientation consistency test,

determining a number of inliers using the transformation and the plurality of putative correspondences between the query image and the putatively corresponding database image; and

retaining the transformation as a best transformation based on the number of inliers of the transformation being greater than a number of inliers of a current best transformation; and

determining the putatively corresponding database image comprises one of the one or more matching images when the number of inliers of the best transformation meets a specified threshold.

15. A computer-implemented method for matching a query image to one or more of a plurality of database images, comprising:

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

obtaining a request to match a query image to one or more of a plurality of database images;

determining a plurality of feature points, a plurality of orientations, and a plurality of feature vectors for the query image, each of the plurality of feature points corresponding to one of the plurality of orientations and one of the plurality of feature vectors;

determining one or more of the plurality of database images putatively corresponding to the query image, a database image of the plurality of database images putatively corresponding to the query image when a number of putative correspondences between the database image and the query image meets a first specified threshold, the putative correspondences comprising a portion of the plurality of feature points of the query image and a portion of a plurality of putatively corresponding feature points of the database image being determined to be visually similar;

for each database image putatively corresponding to the query image,

generating one or more transformation corresponding to one or more subsets of the putative correspondences between the database image and the query image;

performing an orientation consistency test to determine validity of each of the one or more transformations;

performing motion estimation using at least one of the one or more transformations determined to be valid according to the orientation consistency test; and

determining whether the database image matches the query image based at least in part upon the motion estimation using the at least one of the one or more transformations resulting in a number of inliers meeting a second specified threshold, the inliers comprising the putative correspondences fitting the at least one of the one or more transformations; and

providing at least one database image determined to match the query image in response to the request.

16. The computer-implemented method of claim 15, wherein performing the orientation consistency test to determine the validity of each of the one or more transformation comprises:

for each feature point and putatively corresponding feature point in the one or more subsets of the putative correspondences,

determining a first offset point by displacing the feature point from the putatively corresponding feature point in a direction of an orientation of the feature point;

applying one of the one or more transformations to the first offset point to generate a second offset point; and

determining the one of the one or more transformations to be valid when an orientation of the corresponding feature point and an orientation of the second offset point are within a predefined tolerance limit.

17. The computer-implemented method of claim 16, wherein the predefined tolerance limit is less than or equal to 0.1 radians.

18. A system for matching a query image to one or more of a plurality of databases images, comprising:

at least one processor; and

a memory device including instructions that, when executed by the at least one processor, cause the system to;

obtain a request to match a query image to one or more of a plurality of database images;

determine one or more of the plurality of database images putatively corresponding to the query image, each putatively corresponding database image having a plurality of putative correspondences with the query image;

for each putatively corresponding database image and for each transformation of one or more transformations corresponding to one or more subsets of the plurality of putative correspondences between the query image and the putatively corresponding database image, perform an orientation consistency test on the transformation to determine validity of the transformation;

determine one or more matching images from the one or more of the plurality of database images putatively corresponding to query image based at least in part upon performing motion estimation using at least one of the one or more transformations determined to be valid according to the orientation consistency test; and

provide at least one of the one or more matching images in response to the request.

19. The system of claim 18, wherein the instructions when executed further cause the system to:

for each putatively corresponding database image, perform a topological equivalence test on each subset of the one or more subsets of the plurality of putative correspondences between the query image and the putatively corresponding database image to determine validity of the subset,

wherein the instructions to cause the system to perform the orientation consistency on each transformation of the one or more transformations corresponding to the one or more subsets of the plurality of putative correspondences includes instructions to cause the system to perform the orientation consistency on each subset determined to be valid according to the topological equivalence test.

20. The system of claim 18, wherein the instructions to cause the system to perform the consistency test on each transformation of the one or more transformation comprise instructions to cause the system to:

for each feature point and putatively corresponding feature point in one of the one or more subsets of the plurality of putative correspondences corresponding to the transformation,

determine a first offset point by displacing the feature point from the putatively corresponding feature point in a direction of an orientation of the feature point;

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

determine the transformation to be valid when an orientation of the corresponding feature point and an orientation of the second offset point are within a predefined tolerance limit.

21. The system of claim 18, wherein the instructions to cause the system to determine the one or more of the plurality of database images putatively corresponding to the query image comprise instructions to cause the system to:

determine first feature points of the query image; and

for each database image of the plurality of database images,

determine second feature points of the database image;

determine that a first feature point of the query image and a second feature point of the database image comprise a putative correspondence when the first feature point and the second feature point are determined to be visually similar; and

determine the database image comprises one of the one or more of the plurality of putatively corresponding database images when a number of putative correspondences between the query image and the database image meets a specified threshold.

22. A non-transitory computer-readable storage medium for matching an image to one or more of a plurality of images including instructions that, when executed by at least one processor of a computing device, cause the computing device to:

determine one or more of a plurality of images putatively corresponding to a first image, each putatively corresponding image having a plurality of putative correspondences with the first image;

for each putatively corresponding image and for each transformation of one or more transformations corresponding to one or more subsets of the plurality of putative correspondences between the first image and the putatively corresponding image, perform an orientation consistency test on the transformation to determine validity of the transformation; and

determine one or more matching images from the one or more of the plurality of images putatively corresponding to the first image based at least in part upon performing motion estimation using at least one of the one or more transformations determined to be valid according to the orientation consistency test.

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

perform a coverage test for each putatively corresponding image,

wherein the instructions to cause the computing device to determine the one or matching images include instructions to cause the computing device to determine that a first coverage of the putatively corresponding image with respect to a second coverage of the first image meets a predefined threshold.

24. The non-transitory computer-readable storage medium of claim 22, wherein the instructions when executed to cause the computing device to perform the orientation consistency test on each transformation of the one or more transformation comprise instructions when executed to cause the computing device to:

for each feature point and putatively corresponding feature point in one of the one or more subsets of the plurality of putative correspondences corresponding to the transformation,

determine a first offset point by displacing the feature point from the putatively corresponding feature point in a direction of an orientation of the feature point;

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

determine the transformation to be valid when an orientation of the corresponding feature point and an orientation of the second offset point are within a predefined tolerance limit.

25. The non-transitory computer-readable storage medium of claim 22, wherein the instructions when executed to cause the computing device to determine the one or matching images from the one or more of the plurality of images putatively corresponding to the first image comprises:

for each putatively corresponding image,

for each transformation of the at least one of the one or more transformations determined to be valid according to the orientation consistency test,

determine a number of inliers using the transformation and the plurality of putative correspondences between the first image and the putatively corresponding image; and

retain the transformation as a best transformation based on the number of inliers of the transformation being greater than a number of inliers of a current best transformation; and

determine that the putatively corresponding image comprises one of the one or more matching images when the number of inliers of the best transformation meets a specified threshold.