Method for computing the location and orientation of an object in three dimensional space

• US 6,580,821 B1
• Filed: 03/30/2000
• Issued: 06/17/2003
• Est. Priority Date: 03/30/2000
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Roy, Sebastien
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): GORADIA, SHEFALI DINESH
• Application Number:
  US09/538,208
• Time in Patent Office: 1,174 Days
• Field of Search: 382/287, 382/154, 382/216, 382/201, 382/118, 382/285, 382/190, 382/195, 382/203, 382/291, 382/115
• US Class Current: 382/154
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 40/172 Classification, e.g. identification

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.

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).

2. The method of claim 1, wherein the number of feature points marked in step (a) is in the range of 8-12.

3. The method of claim 1, further comprising, after step (a), the step of computing a predetermined number of perturbed points derived from each of the feature points wherein the computation of step (b) is on all possible subsets of three two-dimensional points marked in the query image, and in addition on the corresponding perturbed points.

4. The method of claim 3, wherein the predetermined number of perturbed points are obtained by sampling from a spherical Gaussian distribution.

5. The method of claim 1, after step (d), further comprising the steps of:

(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.

10. The computer program product of claim 9, wherein the number of feature points marked is in the range of 8-12.

11. The computer program product of claim 9, further comprising computer readable program code means for computing a predetermined number of perturbed points derived from each of the feature points wherein the computation in (b) is on all possible subsets of three two-dimensional points marked in the query image, and in addition on the corresponding perturbed points.

12. The computer program product of claim 11, wherein the predetermined number of perturbed points are obtained by sampling from a spherical Gaussian distribution.

13. The computer program product of claim 9, further comprising:

(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).

18. The method of claim 17, wherein the number of feature points marked in step (a) is in the range of 8-12.

19. The method of claim 17, further comprising, after step (a), the step of computing a predetermined number of perturbed points derived from each of the feature points wherein the computation of step (b) is on all possible subsets of three two-dimensional points marked in the query image, and in addition on the corresponding perturbed points.

20. The method of claim 19, wherein the predetermined number of perturbed points are obtained by sampling from a spherical Gaussian distribution.

21. The method of claim 17, after step (d), further comprising the steps of:

(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.