Global registration of multiple 3D point sets via optimization on a manifold
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23)
-
Specification