Method for computing the location and orientation of an object in three dimensional space
First Claim
1. A method for computing the location and orientation of an object in three-dimensional space, the method comprising the steps of:
- (a) marking a plurality of feature points on a three-dimensional model and corresponding feature points on a two-dimensional query image;
(b) for all possible subsets of three two-dimensional feature points marked in step (a), computing the four possible three-dimensional rigid motion solutions of a set of three points in three-dimensional space such that after each of the four rigid motions, under a fixed perspective projection, the three three-dimensional points are mapped precisely to the three corresponding two-dimensional points;
(c) for each solution found in step (b), computing an error measure derived from the errors in the projections of all three-dimensional marked points in the three-dimensional model which were not among the three points used in the solution, but which did have corresponding marked points in the two-dimensional query image;
(d) ranking the solutions from step (c) based on the computed error measure; and
(e) selecting the best solution based on the ranking in step (d).
1 Assignment
0 Petitions
Accused Products
Abstract
A method for computing the location and orientation of an object in three-dimensional space. The method comprises the steps of: (a) marking a plurality of feature points on a three-dimensional model and corresponding feature points on a two-dimensional query image; (b) for all possible subsets of three two-dimensional feature points marked in step (a), computing the four possible three-dimensional rigid motion solutions of a set of three points in three-dimensional space such that after each of the four rigid motions, under a fixed perspective projection, the three three-dimensional points are mapped precisely to the three corresponding two-dimensional points; (c) for each solution found in step (b), computing an error measure derived from the errors in the projections of all three-dimensional marked points in the three-dimensional model which were not among the three points used in the solution, but which did have corresponding marked points in the two-dimensional query image; (d) ranking the solutions from step (c) based on the computed error measure; and (e) selecting the best solution based on the ranking in step (d). Also provided is a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of the present invention and a computer program product embodied in a computer-readable medium for carrying out the methods of the present invention.
-
Citations
24 Claims
-
1. A method for computing the location and orientation of an object in three-dimensional space, the method comprising the steps of:
-
(a) marking a plurality of feature points on a three-dimensional model and corresponding feature points on a two-dimensional query image;
(b) for all possible subsets of three two-dimensional feature points marked in step (a), computing the four possible three-dimensional rigid motion solutions of a set of three points in three-dimensional space such that after each of the four rigid motions, under a fixed perspective projection, the three three-dimensional points are mapped precisely to the three corresponding two-dimensional points;
(c) for each solution found in step (b), computing an error measure derived from the errors in the projections of all three-dimensional marked points in the three-dimensional model which were not among the three points used in the solution, but which did have corresponding marked points in the two-dimensional query image;
(d) ranking the solutions from step (c) based on the computed error measure; and
(e) selecting the best solution based on the ranking in step (d). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
(i) choosing a subset of the solutions from step (c) based on the ranking of step (d);
(ii) computing a predetermined number of perturbed points derived from each of the subset of the solutions;
(iii) repeating step (b) on the predetermined number of perturbed points; and
(iv) repeating step (c) for each solution found in step (iii);
wherein the ranking of step (d) is based on the error computed in both steps (c) and (iv).
-
-
6. The method of claim 5, wherein the subset of solutions chosen is a predetermined portion of the ranked solutions.
-
7. The method of claim 6, wherein the predetermined portion is the top 10% of the ranked solutions.
-
8. The method of claim 5, wherein the predetermined number of perturbed points are obtained by sampling from a spherical Gaussian distribution.
-
9. A computer program product embodied in a computer-readable medium for computing the location and orientation of an object in three-dimensional space, the computer program product comprising:
-
(a) computer readable program code means for marking a plurality of feature points on a three-dimensional model and corresponding feature points on a two-dimensional query image;
(b) computer readable program code means for computing, for all possible subsets of three two-dimensional feature points marked, the four possible three-dimensional rigid motion solutions of a set of three points in three-dimensional space such that after each of the four rigid motions, under a fixed perspective projection, the three three-dimensional points are mapped precisely to the three corresponding two-dimensional points;
(c) computer readable program code means for computing, for each solution, an error measure derived from the errors in the projections of all three-dimensional marked points in the three-dimensional model which were not among the three points used in the solution, but which did have corresponding marked points in the two-dimensional query image;
(d) computer readable program code means for ranking the solutions based on the computed error measure; and
(e) computer readable program code means for selecting the best solution based on the ranking. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
(i) computer readable program code means for choosing a subset of the solutions from (c) based on the ranking of (d);
(ii) computer readable program code means for computing a predetermined number of perturbed points derived from each of the subset of the solutions;
(iii) computer readable program code means for repeating (b) on the predetermined number of perturbed points; and
(iv) computer readable program code means for repeating (c) for each solution found in (iii);
wherein the ranking of (d) is based on the error computed in both (c) and (iv).
-
-
14. The computer program product of claim 13, wherein the subset of solutions chosen is a predetermined portion of the ranked solutions.
-
15. The computer program product of claim 14, wherein the predetermined portion is the top 10% of the ranked solutions.
-
16. The computer program product of claim 13, wherein the predetermined number of perturbed points are obtained by sampling from a spherical Gaussian distribution.
-
17. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for computing the location and orientation of an object in three-dimensional space, the method comprising the steps of:
-
(a) marking a plurality of feature points on a three-dimensional model and corresponding feature points on a two-dimensional query image;
(b) for all possible subsets of three two-dimensional feature points marked in step (a), computing the four possible three-dimensional rigid motion solutions of a set of three points in three-dimensional space such that after each of the four rigid motions, under a fixed perspective projection, the three three-dimensional points are mapped precisely to the three corresponding two-dimensional points;
(c) for each solution found in step (b), computing an error measure derived from the errors in the projections of all three-dimensional marked points in the three-dimensional model which were not among the three points used in the solution, but which did have corresponding marked points in the two-dimensional query image;
(d) ranking the solutions from step (c) based on the computed error measure; and
(e) selecting the best solution based on the ranking in step (d). - View Dependent Claims (18, 19, 20, 21, 22, 23, 24)
(i) choosing a subset of the solutions from step (c) based on the ranking of step (d);
(ii) computing a predetermined number of perturbed points derived from each of the subset of the solutions;
(iii) repeating step (b) on the predetermined number of perturbed points; and
(iv) repeating step (c) for each solution found in step (iii);
wherein the ranking of step (d) is based on the error computed in both steps (c) and (iv).
-
-
22. The method of claim 21, wherein the subset of solutions chosen is a predetermined portion of the ranked solutions.
-
23. The method of claim 22, wherein the predetermined portion is the top 10% of the ranked solutions.
-
24. The method of claim 21, wherein the predetermined number of perturbed points are obtained by sampling from a spherical Gaussian distribution.
Specification