Global registration of multiple 3D point sets via optimization on a manifold

• US 7,831,090 B1
• Filed: 06/30/2006
• Issued: 11/09/2010
• Est. Priority Date: 06/30/2006
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Lee, Pei Yean, Krishnan, Shankar, Moore, John Barrett, Venkatasubramanian, Suresh
• Primary Examiner(s): Chawan; Sheela C
• Application Number:
  US11/480,044
• Time in Patent Office: 1,593 Days
• Field of Search: 382/128, 382/154, 382/100, 382/141, 382/145, 382/181, 382/190, 382/195, 382/205, 382/148, 382/172, 382/168, 382/152, 382/149, 342/96, 342/90, 600/429, 600/443, 600/426, 600/427, 345/419, 345/422, 435/6, 435/91.2, 250/491.1, 250/306, 250/310, 250/311, 250/559.42, 606/130, 536/24.3, 128/916, 356/237.1, 356/237.2, 356/601, 356/613, 430/504, 430/903, 430/111.41, 430/505, 430/957, 430/544, 430/359, 430/212, 430/523, 430/904, 430/122.51, 430/506, 430/84, 430/379, 430/567, 348/126, 348/128, 348/616, 702/189
• US Class Current: 382/154
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

A method for registering multiple 3D point sets by determining optimal relative positions and orientations of the 3D point sets. Initial values are determined for the rotation matrices corresponding to the relative orientations of reference frames of the 3D point sets. A registration error cost function is optimized on a product manifold of all of the rotation matrices to determine optimal values of the rotation matrices. The optimal values of the rotation matrices are used to determine optimal values for translation vectors corresponding to the relative positions of the reference frames of the 3D point sets. The 3D point sets are registered on a common reference frame using the optimal rotation matrices and the optimal translation vectors.

Claims

1. A method for registering a plurality of 3D point sets by determining optimal relative positions and orientations of the 3D point sets, comprising:

generating, by one or more scanners, a plurality of 3D point sets, each 3D point set representing a view of a surface of an object;

determining initial values of rotation matrices corresponding to the 3D point sets based on correspondence values of the 3D point sets;

optimizing a cost function on a product manifold of the rotation matrices using the initial values to determine optimal values of the rotation matrices; and

calculating optimal values of translation vectors corresponding to the 3D point sets based on the optimal values of the rotation matrices;

wherein the optimizing step comprises;

calculating updated values of the rotation matrices based on the initial values to reduce a value of the cost function;

determining whether the cost function is locally minimized based on the updated values;

if the cost function is not minimized, setting the initial values to be the updated values and repeating the optimizing step; and

if the cost function is minimized, determining the updated values to be the optimal values of the rotation matrices;

wherein the step of calculating updated values of the rotation matrices comprises;

constructing a local approximation of the cost function in a neighborhood of the initial values on the product manifold;

calculating a gradient of the local approximation of the cost function;

calculating a Hessian of the local approximation of the cost function;

calculating a descent direction based on the gradient of the local approximation of the cost function and the Hessian of the local approximation of the cost function;

calculating a step length to reduce the cost function based on the calculated descent direction; and

calculating the updated values on the product manifold using the descent direction and the step length.

2. The method of claim 1, wherein the step of determining initial values of rotation matrices comprises:

determining the initial values using a closed form solution for optimal values of the rotation matrices in a noise free case.

3. The method of claim 1, wherein the step of determining initial values of rotation matrices comprises:

constructing a matrix M based on the correspondence values;

determining singular vectors of the matrix M; and

determining the initial values based on the singular vectors.

4. The method of claim 1, wherein the constructing step comprises:

constructing the local approximation of the cost function in the neighborhood of the initial values using a second order Taylor expansion.

5. The method of claim 1, wherein the step of calculating a descent direction comprises:

if the Hessian of the local approximation of the cost function is positive semidefinite, calculating the descent direction based on the gradient and the Hessian of the local approximation of the cost function; and

if the Hessian of the local approximation of the cost function is not positive semidefinite, calculating the descent direction based on the gradient and a positive semidefinite portion of the Hessian of the local approximation of the cost function.

6. The method of claim 1, wherein the step of calculating a step length comprises:

performing a backtracking line search in the calculated descent direction.

7. The method of claim 1, wherein the step of calculating updated values of the rotational matrices comprises:

using the calculated descent direction and step length to map to a point on the product manifold in the neighborhood of the initial values via a local parameterization of the product manifold in the neighborhood of the initial values.

8. The method of claim 1, wherein the step of determining whether the cost function is locally minimized comprises:

comparing a norm of the gradient of the local approximation of the cost function for the updated values of the rotation matrices to an error threshold;

if the norm of the gradient of the local approximation of the cost function for the updated values of the rotation matrices is greater than the error threshold, determining that the cost function is not minimized; and

if the norm of the gradient of the local approximation of the cost function for the updated values of the rotation matrices is less than or equal to the error threshold, determining that the cost function is minimized.

9. A method for registering a plurality of 3D point sets by determining optimal relative positions and orientations of the 3D point sets, comprising:

generating, by one or more scanners, a plurality of 3D point sets, each 3D point set representing a view of a surface of an object;

determining initial values of rotation matrices corresponding to the 3D point sets based on correspondence values of the 3D point sets;

optimizing a cost function on a product manifold of the rotation matrices using the initial values to determine optimal values of the rotation matrices; and

calculating optimal values of translation vectors corresponding to the 3D point sets based on the optimal values of the rotation matrices;

wherein the cost function is a function representing registration error between common points in overlapping 3D point sets.

10. The method of claim 9, wherein the cost function represents least squares registration error.

11. A computer readable medium storing computer program instructions for performing a method for registering a plurality of 3D point sets by determining optimal relative positions and orientations of the 3D point sets, the computer program instructions defining the steps of:

determining initial values of rotation matrices corresponding to the 3D point sets based on correspondence values of the 3D point sets;

optimizing a cost function on a product manifold of all of the rotation matrices using the initial values to determine optimal values of the rotation matrices; and

calculating optimal values of translation vectors corresponding to the 3D point sets based on the optimal values of the rotational matrices;

wherein the computer program instructions defining the optimizing step further define the steps of;

constructing a local approximation of the cost function in a neighborhood of the initial values on the product manifold;

calculating a gradient of the local approximation of the cost function;

calculating a Hessian of the local approximation of the cost function;

calculating a descent direction based on the gradient of the local approximation of the cost function and the Hessian of the local approximation of the cost function;

calculating a step length to reduce the cost function based on the calculated descent direction;

calculating updated values of the rotation matrices on the product manifold using the descent direction and the step length.

12. The computer readable medium of claim 11, wherein the computer program instructions defining the step of determining initial values of rotation matrices further define the step of:

determining the initial values using a closed form solution for optimal values of the rotation matrices in a noise free case.

13. The computer readable medium of claim 11, wherein the computer program instructions defining the step of determining initial values of rotation matrices further define the steps of:

constructing a matrix M based on the correspondence values;

determining singular vectors of the matrix M constructed based on the correspondence values; and

determining the initial values based on the singular vectors.

14. The computer readable medium of claim 11, wherein the computer program instructions defining the constructing step further define the step of:

constructing the local approximation of the cost function in the neighborhood of the initial values using a second order Taylor expansion.

15. The computer readable medium of claim 11, wherein the computer program instructions defining the step of calculating a descent direction further define the steps of:

if the Hessian of the local approximation of the cost function is positive semidefinite, calculating the descent direction based on the gradient and the Hessian of the local approximation of the cost function; and

if the Hessian of the local approximation of the cost function is not positive semidefinite, calculating the descent direction based on the gradient and a positive semidefinite portion of the Hessian of the local approximation of the cost function.

16. The computer readable medium of claim 11, wherein the computer program instructions defining the step of calculating a step length further define the step of:

performing a backtracking line search in the calculated descent direction.

17. The computer readable medium of claim 11, wherein the computer program instructions defining the step of calculating updated values of the rotational matrices further define the step of:

using the calculated descent direction and step length to map to a point on the product manifold in the neighborhood of the initial values via a local parameterization of the product manifold in the neighborhood of the initial values of the rotation matrices.

18. The computer readable medium of claim 11, wherein the computer program instructions defining the optimizing step further define the steps of:

comparing a norm of the gradient of the local approximation of the cost function for the updated values of the rotation matrices to an error threshold;

if the norm of the gradient of the local approximation of the cost function for the updated values of the rotation matrices is greater than the error threshold, setting the initial values of the rotation matrices to be the updated values of the rotation matrices and repeating the optimizing step; and

if the norm of the gradient of the local approximation of the cost function for the updated values of the rotation matrices is less than or equal to the error threshold, determining the updated values of the rotation matrices to be the optimal values of the rotation matrices.

19. A system comprising:

means for determining initial values of rotation matrices corresponding to 3D point sets based on correspondence values of the 3D point sets;

means for optimizing a cost function on a product manifold of all of the rotation matrices using the initial values to determine optimal values of the rotation matrices; and

means for calculating optimal values of translation vectors corresponding to the 3D point sets based on the optimal values of the rotation matrices;

wherein the means for optimizing comprises;

means for constructing a local approximation of the cost function in a neighborhood of the initial values on the product manifold;

means for calculating a gradient of the local approximation of the cost function;

means for calculating a Hessian of the local approximation of the cost function;

means for calculating a descent direction based on the gradient of the local approximation of the cost function and the Hessian of the local approximation of the cost function;

means for calculating a step length to reduce the cost function based on the calculated descent direction; and

means for calculating updated values of the rotational matrices on the product manifold using the descent direction and the step length.

20. The system of claim 19, wherein the means for constructing comprises:

means for constructing the local approximation of the cost function in the neighborhood of the initial values using a second order Taylor expansion.

21. The system of claim 19, wherein the means for calculating a descent direction comprises:

means for calculating a first descent direction based on the gradient and the Hessian of the local approximation of the cost function;

means for calculating a second descent direction based on the gradient and a positive semidefinite portion of the Hessian of the local approximation of the cost function; and

means for selecting one of the first and second descent directions based on whether the Hessian of the local approximation of the cost function is positive semidefinite.

22. The system of claim 19, wherein the means for calculating a step length comprises:

means for performing a backtracking line search in the calculated descent direction.

23. The system of claim 19, wherein the means for calculating updated values of the rotational matrices comprises:

means for using the calculated descent direction and step length to map to a point on the product manifold in the neighborhood of the initial values via a local parameterization of the product manifold in the neighborhood of the initial values.