Horn's Method: Absolute Orientation via Unit Quaternions

Paper Information

Citation: Horn, B. K. P. (1987). Closed-form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America A, 4(4), 629-642. https://doi.org/10.1364/JOSAA.4.000629

Publication: Journal of the Optical Society of America A, 1987

Additional Resources:

• Kabsch Algorithm: NumPy, PyTorch, TensorFlow, and JAX (tutorial with differentiable implementations of the related SVD-based method)

A Quaternion Approach to Point Set Registration

This Method paper presents a closed-form solution to the absolute orientation problem: given corresponding points measured in two different coordinate systems, find the optimal rotation, translation, and scale that maps one set onto the other. While the Kabsch algorithm (1976) solved the rotation subproblem via eigendecomposition of $\tilde{\mathsf{R}}\mathsf{R}$, Horn’s approach uses unit quaternions to represent rotation, reducing the problem to finding the eigenvector of a $4 \times 4$ symmetric matrix associated with its largest eigenvalue.

The Absolute Orientation Problem

Given $n$ point pairs ${\mathbf{r}_{l,i}}$ and ${\mathbf{r}_{r,i}}$ measured in “left” and “right” coordinate systems, find the transformation:

$$ \mathbf{r}_r = s , R(\mathbf{r}_l) + \mathbf{r}_0 $$

where $s$ is a scale factor, $R$ is a rotation, and $\mathbf{r}_0$ is a translation, minimizing the sum of squared residual errors:

$$ \sum_{i=1}^{n} \lVert \mathbf{r}_{r,i} - s , R(\mathbf{r}_{l,i}) - \mathbf{r}_0 \rVert^2 $$

Prior methods either used iterative numerical procedures or selectively discarded constraints (e.g., Thompson’s and Schut’s three-point methods). Horn derives a direct solution that uses all available information from all points simultaneously.

Decoupling Translation, Scale, and Rotation

Horn shows that the three components of the transformation can be solved sequentially.

Translation: After centering both point sets at their centroids ($\bar{\mathbf{r}}_l$ and $\bar{\mathbf{r}}_r$), the optimal translation is:

$$ \mathbf{r}_0 = \bar{\mathbf{r}}_r - s , R(\bar{\mathbf{r}}_l) $$

Scale: Horn derives three formulations (asymmetric left, asymmetric right, and symmetric). The symmetric version, which ensures the inverse transformation yields the reciprocal scale, is:

$$ s = \left( \frac{\sum_{i=1}^{n} \lVert \mathbf{r}’_{r,i} \rVert^2}{\sum_{i=1}^{n} \lVert \mathbf{r}’_{l,i} \rVert^2} \right)^{1/2} $$

the ratio of root-mean-square deviations from the respective centroids.

Rotation: After removing translation and scale, the remaining problem is to find the rotation $R$ that maximizes:

$$ \sum_{i=1}^{n} \mathbf{r}’_{r,i} \cdot R(\mathbf{r}’_{l,i}) $$

The Quaternion Eigenvector Solution

Horn represents rotation using unit quaternions $\dot{q} = q_0 + i q_x + j q_y + k q_z$ with $\lVert \dot{q} \rVert = 1$. A rotation acts on a vector (represented as a purely imaginary quaternion $\dot{r}$) via the composite product:

$$ \dot{r}’ = \dot{q} , \dot{r} , \dot{q}^* $$

Using the $4 \times 4$ matrix representations of quaternion products, the objective function becomes a quadratic form:

$$ \dot{q}^T N \dot{q} $$

where $N$ is a real symmetric $4 \times 4$ matrix whose elements are combinations of the sums of products $S_{xx}, S_{xy}, \ldots, S_{zz}$ from the $3 \times 3$ cross-covariance matrix $M = \sum_i \mathbf{r}’_{l,i} \mathbf{r}’^T_{r,i}$:

$$ N = \begin{bmatrix} (S_{xx} + S_{yy} + S_{zz}) & S_{yz} - S_{zy} & S_{zx} - S_{xz} & S_{xy} - S_{yx} \\ S_{yz} - S_{zy} & (S_{xx} - S_{yy} - S_{zz}) & S_{xy} + S_{yx} & S_{zx} + S_{xz} \\ S_{zx} - S_{xz} & S_{xy} + S_{yx} & (-S_{xx} + S_{yy} - S_{zz}) & S_{yz} + S_{zy} \\ S_{xy} - S_{yx} & S_{zx} + S_{xz} & S_{yz} + S_{zy} & (-S_{xx} - S_{yy} + S_{zz}) \end{bmatrix} $$

The trace of $N$ is always zero. The unit quaternion maximizing $\dot{q}^T N \dot{q}$ is the eigenvector corresponding to the most positive eigenvalue of $N$.

The Characteristic Polynomial

The eigenvalues satisfy a quartic $\lambda^4 + c_3 \lambda^3 + c_2 \lambda^2 + c_1 \lambda + c_0 = 0$ where:

• $c_3 = 0$ (trace of $N$ is zero, so the four roots sum to zero)
• $c_2 = -2 \operatorname{Tr}(M^T M)$ (always negative, guaranteeing both positive and negative roots)
• $c_1 = -8 \det(M)$
• $c_0 = \det(N)$

When points are coplanar (including the common case of exactly three points), $\det(M) = 0$, so $c_1 = 0$ and the quartic reduces to a biquadratic solvable in closed form.

Coplanar Points and the Three-Point Case

For coplanar measurements, the quartic simplifies to $\lambda^4 + c_2 \lambda^2 + c_0 = 0$, yielding:

$$ \lambda_m = \left[ \frac{1}{2} \left( (c_2^2 - 4c_0)^{1/2} - c_2 \right) \right]^{1/2} $$

Horn also provides a geometric interpretation for the coplanar case: first rotate one plane into the other (about their line of intersection), then solve a 2D least-squares rotation within the shared plane.

Comparison with the Kabsch Algorithm

Both methods solve the same underlying optimization problem but approach it differently:

Horn emphasizes a symmetry property: the inverse transformation should yield exactly the inverse parameters. This holds automatically for the quaternion rotation but requires a specific (symmetric) choice of scale formula.

Citation

@article{horn1987closed,
  title={Closed-form solution of absolute orientation using unit quaternions},
  author={Horn, Berthold K. P.},
  journal={Journal of the Optical Society of America A},
  volume={4},
  number={4},
  pages={629--642},
  year={1987},
  publisher={Optica Publishing Group},
  doi={10.1364/josaa.4.000629}
}