Quaternion

Background

Quaternions are a number space that can be represented as a 4D point \(\displaystyle q = (q_0, q_1, q_2, q_3) = (q_0, \mathbf{q})\) with unit norm.
Here, \(\displaystyle \mathbf{q}\) represents the imaginary part: \(\displaystyle q_1 \mathbf{i}+q_2 \mathbf{j}+q_3 \mathbf{k}\).

Conjugation is \(\displaystyle \bar{q} = (q_0, -\mathbf{q})\).

Multiplication is \(\displaystyle q * p = (q_0 p_0 - \mathbf{q} \cdot \mathbf{p}, q_0 \mathbf{p} + p_0 \mathbf{q} + \mathbf{q} \times \mathbf{p})\).

Rotations

Quadratically conjugating a quaternion as follows is equivalent to applying a rotation on \(\displaystyle \mathbf{x}=(x,y,z)\): \(\displaystyle q * (c,x,y,z)*\bar{q} = (c, R(q) \cdot \mathbf{x})\)
Here, \(\displaystyle R(q)=R(-q)\) is a two-to-one mapping from quaternions to 3x3 rotation matrices.

Quaternion multiplication corresponds to composing rotations:
\(\displaystyle R(q*p) = R(q) \cdot R(p)\)

The quaternion \(\displaystyle q=(\cos(\theta/2), \hat{n}_1 \sin(\theta/2), \hat{n}_2 \sin(\theta/2), \hat{n}_3 \sin(\theta/2))\) is equivalent to the rotation around axis \(\displaystyle \hat{n}\) by angle \(\displaystyle \theta\).

Slurp

Slerp, or spherical linear interpolation is done as: \[ \operatorname{slerp}(q_0, q_1, s) \equiv q(s)[q_0, q_1] = q_0 \frac{\sin((1-s)\phi)}{\sin \phi} + q_1 \frac{\sin(s\phi)}{\sin \phi} \] Here \(\displaystyle \phi\) is the angle between the two quaternions: \(\displaystyle \cos(\phi) = q_0 \cdot q_1\).

Spatial Alignment Problem

Also known as the RMSD problem.

Let \(\displaystyle \{y_k\}\) be a data array with N columns of D-dimensional points, known as the reference structure.
Let \(\displaystyle \{x_k\}\) be a data array of matched points, known as the test structure.
The goal is to rotation \(\displaystyle \{x_k\}\) by a rotation matrix \(\displaystyle R_{D} \in SO(D)\) to minimize the mean squared distance: \[ \mathbf{S}_D = \sum_{k=1}^{N} \Vert R_D \cdot x_k - y_x \Vert^2 \] The paper by Hanson focuses on 3D points.

Cross-term maximization

It can be shown that the least squares minimization problem can be converted to a cross-term maximization:
\(\displaystyle \begin{aligned} \mathbf{S}_D &= \sum_{k=1}^{N} \Vert R_D x_k - y_k \Vert^2\\ &= \sum_{k=1}^{N} (R_D x_k - y_x)^T(R_D x_k - y_k)\\ &= \sum_{k=1}^{N} ( x_k ^T R_D^T - y_k^T)(R_D x_k - y_k)\\ &= \sum_{k=1}^{N} ( x_k ^T R_D^T - y_k^T)(R_D x_k - y_k)\\ &= \sum_{k=1}^{N} - 2(R_D x_k) \cdot y_k\\ \end{aligned} \)

So minimization of \(\displaystyle \mathbf{S}_D\) is equivalent to maximization of \(\displaystyle \sum_{k=1}^{N} (R_D x_k) \cdot y_k = tr R_d \cdot E\) where \(\displaystyle E_{ab} = \sum_{k=1}^{N} [x_k]_a [y_k]_b = [X \cdot Y^T]_{ab}\). This is also equivalent to solving \(\displaystyle \delta(q) = q M(E) q^t\).

Algebraic Solutions

There are expressions for solving the eigenvalues of \(\displaystyle M\).

3D Orientation-Frame Alignment Problem

An orientation frame are the columns of the \(\displaystyle SO(3)\) orientation matrix.
In this problem, we assume we have \(\displaystyle n\) paired orientation frames, \(\displaystyle \{p_k\}\) and \(\displaystyle \{r_k\}\) which we want to align using quaternion \(\displaystyle q\).

Geodesic arc-length distance

For two unit quaternions \(\displaystyle q_1\) and \(\displaystyle q_2\), the geodesic arc length is \(\displaystyle \alpha\) where \(\displaystyle q_1 \cdot q_2 = \cos \alpha\).
Because of sign ambiguity (\(\displaystyle R(q_2) = R(-q_2)\), we take the minimum value: \[ d_{geodesic}(q_1, q_2) = \min(\alpha, \pi-\alpha) \text{ where } 0 \leq d_{geodesic}(q_1, q_2) \leq \frac{\pi}{2} \]

The least-squares optimization is: \[ \begin{align*} \mathbf{S}_{geodesic} &= \sum_{k=1}^{N}(\operatorname{arccos} |(q*p_k) \cdot r_k|)^2\\ &= \sum_{k=1}^{N}(\operatorname{arccos} |q \cdot (r_k * \bar{p}_k)|)^2 \end{align*} \]

Resources

• The Quaternion-Based Spatial Coordinate and Orientation Frame Alignment Problems by Andrew Hanson Edited Paper