Transcript Point set alignment - Department of Computer Science

Point set alignment
Closed-form solution of absolute
orientation using unit quaternions
Berthold K. P. Horn
Department of Electrical Engineering, University of Hawaii at Manoa
Presented by Ashley Fernandes
Abstract
• Finding relationship between coordinate
systems (absolute orientation)
• Closed-form
• Use of quaternions for rotation
• Use of centroid for translation
• Use of root-mean-square deviations for
scale
Disadvantages of previous
methods
• Cannot handle more than three points
• Do not use information from all three
points
• Iterative instead of least squares
Introduction - Transformation
Transformation between two
Cartesian coordinate systems
Translation
Rotation
Scaling
Introduction - Method
•
•
•
•
Minimize error
Closed-form solution
Use of quaternions
Symmetry of solution
Coordinate systems
Selective discarding constraints
X axis
Y axis
Z axis
l
Maps points from left hand to right hand coordinate system
Rotation
Finding the translation
Measured coordinates in left and right hand systems
Form of translation
Scale factor
Translational offset
Rotated vector from left coordinate system
Residual error
To be minimized
Centroids of sets of measurements
Centroids
New coordinates
Error term
where
Sum of squares of errors
Centroids of sets of measurements
Translation, when r’o = 0
Error term, when r’o = 0
Total error term to be minimized
Finding the scale
Total error term, since
To minimize w.r.t. scale s, first term should be zero, or
Symmetry in scale
Suppose we tried to find
, or so we hope.
But,
or
Instead, we use
Total error becomes
To minimize w.r.t. scale s, first term should be zero, or
Scale
Why unit quaternions
• Easier to enforce unit magnitude
constraint on quaternion than orthogonal
constraint on matrix
• Closely allied to geometrically intuitive
concept of rotation by an angle about an
axis
Quaternions
Representation
If
Multiplication
Quaternions
Multiplication expressed as product of
orthogonal matrix4x4 and vector4
Quaternions
Dot product
Square of magnitude
Conjugate
Product of quaternion and its conjugate
Inverse
Unit quaternions and rotation
if
We use the composite product
Note that this is similar to
Also, note that
which is purely imaginary.
Relationship to other notations
If angle is Θ
and axis is unit vector
Composition of rotations
First rotation
Second rotation
Since
Combined rotation
Finding the best rotation
We must find the quaternion
Let
that maximizes
and
Finding the best rotation
What we have to maximize
Finding the best rotation
where
and
Introducing the matrix3x3
that contains all the information required to solve the least-squares problem for
rotation.
where
Then,
and so on.
Eigenvector maximizes matrix
product
Unit quaternion that maximizes
is eigenvector corresponding to most positive eigenvalue of N.
Eigenvalues are solutions of quartic in
that we obtain from
After selecting the largest positive eigenvalue
by solving
we find the eigenvector
Nature of the closed-form solution
• Find centroids rl and rr of the two sets of
measurements
• Subtract them from all measurements
• For each pair of coordinates, compute
x’lx’r, x’ly’r, … z’lz’r of the components of
the two vectors.
• These are added up to obtain Sxx, Sxy,
…Szz.
Nature of the closed-form solution
• Compute the 10 independent elements of the
4x4 symmetric matrix N
• From these elements, calculate the coefficients
of the quartic that must be solved to get the
eigenvalues of N
• Pick the most positive root and use it to solve
the four linear homogeneous equations to get
the eigenvector. The quaternion representing
the rotation is a unit vector in the same direction.
Nature of the closed-form solution
• Compute the scale from the symmetrical
form formula, i.e. the ratio of the rootmean-square deviations of the
measurements from their centroids.
• Compute the translation as the difference
between the centroid of the right
measurements and the scaled and rotated
centroid of the left measurement.
Thank you.
The end.