Method and apparatus for determining camera pose from point correspondences

• US 7,359,526 B2
• Filed: 03/11/2004
• Issued: 04/15/2008
• Est. Priority Date: 03/11/2003
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Nister, David
• Primary Examiner(s): Mehta; Bhavesh M.
• Assistant Examiner(s): ALLISON, ANDRAE S
• Application Number:
  US10/798,726
• Publication Number:
  US 20040227820A1
• Time in Patent Office: 1,496 Days
• Field of Search: 382/154, 382/199, 382/294, 382/285, 382/107, 382/106, 382/291, 345/207
• US Class Current: 382/100
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 10/147 Details of sensors, e.g. sensor lenses fingerprint or palmprint sensors G06V40/13; vascular sensors G06V40/145; eye sensors G06V40/19
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

A method and apparatus for determining camera pose from point correspondences. Specifically, an efficient solution to the classical five-point relative pose problem is presented. The problem is to find the possible solutions for relative camera motion between two calibrated views given five corresponding points. The method consists of computing the coefficients of a tenth degree polynomial and subsequently finding its roots. The method is well suited for numerical implementation that also corresponds to the inherent complexity of the problem. The method is used in a robust hypothesize- and-test framework to estimate structure and motion in real-time.

Claims

1. A method for determining camera pose from a plurality of point correspondences between at least two images, comprising:

selecting a plurality of five point correspondences from the plurality of point correspondences;

generating at least one hypothesis from each of said five point correspondences based on a tenth degree polynomial generated by

extracting a nullspace of a 5×

9 matrix;

expanding in accordance with cubic constraints;

applying Gauss-Jordan elimination; and

expanding determinant polynomials of two 4×

4 polynomial matrices to obtain said tenth degree polynomial directly;

scoring said plurality of hypotheses for determining a best hypothesis; and

generating rotation and translation information of said camera pose from said best hypothesis.

2. The method of claim 1, wherein intrinsic parameters associated with said plurality of point correspondences are considered calibrated.

3. The method of claim 2, wherein said intrinsic parameters include focal length.

4. The method of claim 1, wherein said rotation and translation information are derived from an essential matrix, E.

5. The method of claim 4, wherein said essential matrix E is a 3×

3 matrix that satisfies;

${\mathrm{EE}}^T<br><br>E-\frac{1}{2}<br><br><br><br>\mathrm{trace}<br><br>\left({\mathrm{EE}}^T\right)<br><br>E=0.$

6. The method of claim 1, wherein said scoring step comprises:

scoring said plurality of hypotheses against a first subset of a plurality of observations;

retaining a subset of said scored hypotheses;

scoring said retained subset of said scored hypotheses against a second subset of the plurality of observations;

retaining a subset of said second scored hypotheses; and

repeating said scoring and retaining steps for the plurality of observations.

7. An apparatus for determining camera pose from a plurality of point correspondences between at least two images, comprising:

means for selecting a plurality of five point correspondences from the plurality of point correspondences;

means for generating at least one hypothesis from each of said five point correspondences based on a tenth degree polynomial generated by

extracting a nullspace of a 5×

9 matrix;

expanding in accordance with cubic constraints;

applying Gauss-Jordan elimination; and

expanding determinant polynomials of two 4×

4 polynomial matrices to obtain said tenth degree polynomial directly;

means for scoring said plurality of hypotheses for determining a best hypothesis; and

means for generating rotation and translation information of said camera pose from said best hypothesis.

8. The apparatus of claim 7, wherein intrinsic parameters associated with said plurality of point correspondences are considered calibrated.

9. The apparatus of claim 8, wherein said intrinsic parameters include focal length.

10. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for determining camera pose from a plurality of point correspondences between at least two images, comprising of:

selecting a plurality of five point correspondences from the plurality of point correspondences;

generating at least one hypothesis from each of said five point correspondences based on a tenth degree polynomial generated by

extracting a nullspace of a 5×

9 matrix;

expanding in accordance with cubic constraints;

applying Gauss-Jordan elimination; and

expanding determinant polynomials of two 4×

4 polynomial matrices to obtain said tenth degree polynomial directly;

scoring said plurality of hypotheses for determining a best hypothesis; and

generating rotation and translation information of said camera pose from said best hypothesis.

11. The computer-readable medium of claim 10, wherein intrinsic parameters associated with said plurality of point correspondences are considered calibrated.

12. The computer-readable medium of claim 11, wherein said intrinsic parameters include focal length.

13. The computer-readable medium of claim 10, wherein said scoring step comprises:

scoring said plurality of hypotheses against a first subset of a plurality of observations;

retaining a portion of said scored hypotheses;

scoring said retained portion of said scored hypotheses against a second subset of the plurality of observations;

retaining a portion of said second scored hypotheses; and

repeating said scoring and retaining steps for the plurality of observations.

14. A method for scoring a plurality of hypotheses for determining a best hypothesis, where rotation and translation information of a camera pose can be derived from said best hypothesis, comprising:

scoring the plurality of hypotheses against a first subset of a plurality of observations;

retaining a portion of said scored hypotheses;

scoring said retained subset of said scored hypotheses against a second subset of the plurality of observations;

retaining a portion of said second scored hypotheses; and

repeating said scoring and retaining steps for the plurality of observations.