System and method to match images

• US 20100183229A1
• Filed: 01/16/2009
• Published: 07/22/2010
• 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
• Granted Patent: US 8,401,342 B2
• Time in Patent Office: Days
• US Class Current: 382/197
• 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 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

a. finding putatively corresponding images from the plurality of images by finding putative correspondences between one of the plurality of images and the query image;

b. checking topological equivalence between a subset of putative correspondences between one of the putatively corresponding images and the query image; and

c. finding candidate matches by performing motion estimation using the subset of putative correspondences between one of the putatively corresponding images and the query image.

2. The method of claim 1, wherein the putatively corresponding images are selected from the plurality of images whose number of putative correspondences is greater than both a predefined value and a value based on the number of putative correspondences found in the plurality of images.

3. The method of claim 1, wherein finding a putative correspondence comprises finding a vector dot product between a feature vector of one of the plurality of images and a feature vector of the query image that is greater than a predefined value.

4. The method of claim 1, wherein finding a candidate match comprises computing a set of inliers from the set of putative correspondences between the query image and a putatively corresponding image obtained by the estimated motion.

5. The method of claim 4 further comprising measuring a percentage of area enclosed by the inliers of both a candidate match and the query image and rejecting the candidate match when a maximum of two percentages is less than a predefined threshold.

6. The method of claim 1, wherein performing the motion estimation comprises computing a transformation between corresponding feature points in a subset of putative correspondences.

7. The method of claim 6 further comprising performing an orientation consistency test on the feature points in the subset of putative correspondences.

8. The method of claim 7 further comprising:

a. determining an offset point for the feature point in the subset of putative correspondences in one of the images, wherein the offset point is displaced from its corresponding feature point in the direction of the orientation of that feature point;

b. transforming the offset point to generate a second offset point corresponding to the feature point in the subset of putative correspondences in the other image; and

c. discarding the transformation when orientation between the feature point in the subset of putative correspondences in the other image and its corresponding transformed offset point differs from its estimated orientation 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 one or more sequences of final matches comprises:

a. sorting the sequence of candidate matches by decreasing number of inliers;

b. appending the candidate match to an existing sequence if the area of the intersection of a polygon enclosing the inliers of a candidate match in the query image and a polygon enclosing the inliers of a first element of an existing sequence in the query image is greater than a predefined threshold; and

c. creating a new sequence consisting of the candidate match when the area of the intersection of a polygon enclosing the inliers of a candidate match in the query image and a polygon enclosing the inliers of the first element of an existing sequence in the query image falls below a predefined threshold for all existing sequences.

12. The method of claim 1, wherein the motion estimation is performed by using a transformation generated using the RANSAC procedure.

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

a. finding putatively corresponding images from the plurality of images by finding putative correspondences between one of the plurality of images and the query image; and

b. finding candidate matches by performing motion estimation using the subset of putative correspondences between one putatively corresponding image and the query image and performing an orientation consistency test on the feature points in the subset of putative correspondences.

14. The method of claim 13 further comprising checking the topological equivalence between a subset of putative correspondences between one of the putatively corresponding images and the query image prior to performing the orientation consistency test.

15. The method of claim 13, wherein performing the orientation consistency test further comprises:

a. determining an offset point for the feature point in the subset of putative correspondences in one of the images, wherein the offset point is displaced from its corresponding feature point in the direction of the orientation of that feature point;

b. transforming the offset point to generate a second offset point corresponding to the feature point in the subset of putative correspondences in the other image; and

c. discarding the transformation when orientation between the feature point in the subset of putative correspondences in the other image and its corresponding transformed offset point differs from its estimated orientation by a predefined limit.

16. The method of claim 13, wherein finding a candidate match comprises computing a set of inliers from the set of putative correspondences between the query image and a putatively corresponding image obtained by the estimated motion.

17. The method of claim 13 further comprising identifying one or more sequences of final matches from the candidate matches.

18. The method of claim 17, wherein identifying one or more sequences of final matches comprises selecting a candidate match when a number of inliers for the candidate match is greater than a predefined number of inliers and has an approximation error less than a predefined threshold.

19. A 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:

a. finding putatively corresponding images from the plurality of images by finding putative correspondences between one of the plurality of images and the query image;

b. finding candidate matches by performing motion estimation using a subset of putative correspondences between one of the putatively corresponding images and the query image; and

c. measuring a percentage of area enclosed by inliers of both a candidate match and the query image, and rejecting the candidate match when a maxima of the two percentages is less than a predefined threshold.

20. A 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

a. finding putatively corresponding images from the plurality of images by finding putative correspondences between one of the plurality of images and the query image;

b. finding candidate matches by performing motion estimation using the subset of putative correspondences between one of the putatively corresponding images and the query image; and

c. identifying one or more sequences of final matches from the candidate matches, the method comprising;

i. sorting the sequence of candidate matches by decreasing number of inliers;

ii. appending the candidate match to an existing sequence if the area of the intersection of a polygon enclosing the inliers of a candidate match in the query image and a polygon enclosing the inliers of a first element of an existing sequence in the query image is greater than a predefined threshold; and

iii. creating a new sequence consisting of the candidate match when the area of the intersection of a polygon enclosing the inliers of a candidate match in the query image and a polygon enclosing the inliers of the first element of an existing sequence in the query image falls below a predefined threshold for all existing sequences.

21. 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. a putative correspondence module for finding putatively corresponding images from the plurality of images using the set of feature vectors;

b. a motion estimation module for checking the topological equivalence of a subset of putative correspondences between one putatively corresponding image and the query image and for performing motion estimation on the putatively corresponding images using the subset of putative correspondences; and

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

22. The system of claim 21, wherein the putative correspondence module comprises a vector-dot product module, the vector-dot product module adapted for:

a. computing a vector dot product between feature vectors of one of the plurality of images and feature vectors of the query image to find putative correspondences; and

b. selecting putatively corresponding images from the plurality of images when the number of putative correspondences is greater than a predefined value.

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

a. determining an offset point for the feature point in the subset of putative correspondences in one of the images, wherein the offset point is displaced from its corresponding feature point in the direction of the orientation of that feature point;

b. transforming the offset point to generate a second offset point corresponding to the feature point in the subset of putative correspondences in the other image; and

c. discarding the transformation when orientation between the feature point in the subset of putative correspondences in the other image and its offset point exceeds a predefined limit.

24. The system of claim 21, wherein the motion estimation module further comprises an inliers computing module for computing inliers from the set of putative correspondences between the query image and a putatively corresponding image using the transformation.

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

26. The system of claim 21, wherein the final identification module rejects candidate matches where a maximum of percentage of area enclosed by inliers of both a candidate match and the query image is less than a predefined threshold.

27. The system of claim 21, wherein the motion estimation module calculates motion estimation by using a transformation generated using the RANSAC procedure.

28. A computer program product 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 computer program product comprising instructions stored in a computer readable medium performing:

a. finding putatively corresponding images from the plurality of images by finding putative correspondences between one of the plurality of images and the query image;

b. checking topological equivalence between a subset of putative correspondences between one of the putatively corresponding images and the query image; and

c. finding candidate matches by performing motion estimation using the subset of putative correspondences between one of the putatively corresponding images and the query image