Page 304 -

6.1 2D and 3D feature-based alignment 283

amount of covariance in a given solution, which can actually have a wider spread (“longer
tails”) if the energy flattens out away from the local minimum where the optimal solution is
found.

6.1.5 3D alignment
Instead of aligning 2D sets of image features, many computer vision applications require the
alignment of 3D points. In the case where the 3D transformations are linear in the motion
parameters, e.g., for translation, similarity, and affine, regular least squares (6.5) can be used.

The case of rigid (Euclidean) motion,

2
E R3D = x − Rx i − t , (6.31)

i
i
which arises more frequently and is often called the absolute orientation problem (Horn
1987), requires slightly different techniques. If only scalar weightings are being used (as
opposed to full 3D per-point anisotropic covariance estimates), the weighted centroids of the
two point clouds c and c can be used to estimate the translation t = c − Rc. 8 We are then

left with the problem of estimating the rotation between two sets of points {ˆ x i = x i − c}

and {ˆ x = x − c } that are both centered at the origin.
i
i
One commonly used technique is called the orthogonal Procrustes algorithm (Golub and
Van Loan 1996, p. 601) and involves computing the singular value decomposition (SVD) of
the 3 × 3 correlation matrix
T T

C = ˆ x ˆ x = UΣV . (6.32)
i
T
The rotation matrix is then obtained as R = UV . (Verify this for yourself when ˆ x = Rˆ x.)
Another technique is the absolute orientation algorithm (Horn 1987) for estimating the
unit quaternion corresponding to the rotation matrix R, which involves forming a 4×4 matrix
from the entries in C and then finding the eigenvector associated with its largest positive
eigenvalue.
Lorusso, Eggert, and Fisher (1995) experimentally compare these two techniques to two
additional techniques proposed in the literature, but find that the difference in accuracy is
negligible (well below the effects of measurement noise).
In situations where these closed-form algorithms are not applicable, e.g., when full 3D
covariances are being used or when the 3D alignment is part of some larger optimization, the
incremental rotation update introduced in Section 2.1.4 (2.35–2.36), which is parameterized
by an instantaneous rotation vector ω, can be used (See Section 9.1.3 for an application to
image stitching.)
In some situations, e.g., when merging range data maps, the correspondence between
data points is not known a priori. In this case, iterative algorithms that start by matching
nearby points and then update the most likely correspondence can be used (Besl and McKay
1992; Zhang 1994; Szeliski and Lavall´ ee 1996; Gold, Rangarajan, Lu et al. 1998; David,
DeMenthon, Duraiswami et al. 2004; Li and Hartley 2007; Enqvist, Josephson, and Kahl
2009). These techniques are discussed in more detail in Section 12.2.1.

8 When full covariances are used, they are transformed by the rotation and so a closed-form solution for transla-
tion is not possible.