Quaternion: Difference between revisions

Created page with " ==Background== Quaternions are a number space that can be represented as a 4D point <math>q = (q_0, q_1, q_2, q_3) = (q_0, \mathbb{q})</math> with unit norm. Here, <math>\mat..."
 
 
(47 intermediate revisions by the same user not shown)
Line 1: Line 1:
Quaternions are a number system which can be used to represent [[rotations]] in 3D space.
Double quaternion allows representing 4D rotations using two quaternions. 
[[Dual quaternion]] allows represent both rotations and translations in 3D space. 
The algebra of quaternions, double quaternions, and dual quaternions is called Clifford algebras.


==Background==
==Background==
Quaternions are a number space that can be represented as a 4D point <math>q = (q_0, q_1, q_2, q_3) = (q_0, \mathbb{q})</math> with unit norm. Here, <math>\mathbf{q}</math> represented the ''imaginary'' part.
Quaternions are a number space that can be represented as a 4D point <math>q = (q_0, q_1, q_2, q_3) = (q_0, \mathbf{q})</math> with unit norm.
Here, <math>\mathbf{q}</math> represents the ''imaginary'' part: <math>q_1 \mathbf{i}+q_2 \mathbf{j}+q_3 \mathbf{k}</math>.
 
The conjugate is <math>\bar{q} = (q_0, -\mathbf{q})</math>.
===Multiplication===
Multiplication is <math>q*p = (q_0 p_0 - \mathbf{q} \cdot \mathbf{p}, q_0 \mathbf{p} + p_0 \mathbf{q} + \mathbf{q} \times \mathbf{p})</math>. 
 
Similar to imaginary numbers, <math>\mathbf{i}^2=\mathbf{j}^2=\mathbf{k}^2=\mathbf{i}\mathbf{j}\mathbf{k}=-1</math>. 
Multiplication between bases follow cross product rules: <math>\mathbf{i} * \mathbf{j} = \mathbf{k}</math> and <math>\mathbf{j} * \mathbf{i} = -\mathbf{k}</math>.


Conjugation is <math>\bar{q} = (q_0, -\mathbf{q}</math>.
In general, quaternion multiplication does not commute: <math>q_1 * q_2 \neq q_2 * q_1</math>


Multiplication is <math>q * p = (q_0 p_0 - \mathbf{q} \cdot \mathbf{p}, q_0 \mathbf{p} + p_0 \mathbf{q} + \mathbf{q} \times \mathbf{p})</math>.
Intuition: Left multiplication by a quaternion is a 4D rotation plus a scaling operation.


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


Line 15: Line 28:
<math>R(q*p) = R(q) \cdot R(p)</math>
<math>R(q*p) = R(q) \cdot R(p)</math>


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


===Slurp===
===Slurp===
Slerp, or ''spherical linear interpolation'' is done as:
Slerp, or ''spherical linear interpolation'' is done as:
<math display="block">
<math display="block">
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}
\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}
</math>
</math>
Here <math>\phi</math> is the angle between the two quaternions: <math>\cos(\phi) = q_0 \cdot q_1</math>.
Here <math>\phi</math> is the angle between the two unit quaternions: <math>\cos(\phi) = q_0 \cdot q_1</math>.
 
===Distance Metrics===
There are multiple ways to calculate the distance between two quaternions. See [https://math.stackexchange.com/questions/90081/quaternion-distance Stackexchange].
* <math>\theta = \cos^{-1}( \langle q_1, q_2 \rangle)</math>
** Note that this loss can be misleading for rotations because of double cover:
** <math>R(q_1) = R(-q_1)</math> but <math>\cos^{-1}(x) \neq \cos^{-1}(-x)</math>
** Thus some people use the distance below.
* <math>\theta = \cos^{-1}(2 \langle q_1, q_2 \rangle^2 - 1)</math>


==Spatial Alignment Problem==
==Spatial Alignment Problem==
Line 36: Line 57:


===Cross-term maximization===
===Cross-term maximization===
It can be shown that the least squares minimization problem can be converted to a cross-term maximization:
It can be shown that the least squares minimization problem can be converted to a cross-term maximization:
<math>
<math>
\begin{aligned}
\begin{aligned}
Line 53: Line 74:
===Algebraic Solutions===
===Algebraic Solutions===
There are expressions for solving the eigenvalues of <math>M</math>.
There are expressions for solving the eigenvalues of <math>M</math>.
==Orientation-Frame Alignment Problem==
An orientation frame are the columns of the <math>SO(3)</math> orientation matrix. 
In this problem, we assume we have <math>n</math> paired orientation frames, <math>\{p_k\}</math> and <math>\{r_k\}</math> which we want to align using quaternion <math>q</math>.
===Geodesic arc-length distance===
For two unit quaternions <math>q_1</math> and <math>q_2</math>, the geodesic arc length is <math>\alpha</math> where <math>q_1 \cdot q_2 = \cos \alpha</math>. 
Because of sign ambiguity, <math>R(q_2) = R(-q_2)</math>, we take the minimum value:
<math display="block">
d_{geodesic}(q_1, q_2) = \min(\alpha, \pi-\alpha) \text{ where }
0 \leq d_{geodesic}(q_1, q_2) \leq \frac{\pi}{2}
</math>
The least-squares optimization is:
<math display="block">
\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*}
</math>
===Chord distance===
The geodesic least squares cannot be solved using linear algebra. 
Instead you can use ''chord distance'': 
<math>
\begin{aligned}
d_{\text{chord}}(q_1, q_2) &= \min(\Vert q_1 - q_2 \Vert, \Vert q_1 + q_2 \Vert)\\
& 0 \leq d_{\text{chord}}(q_1, q_2) \leq \sqrt{2}
\end{aligned}
</math>
In this case, our least squares problem is:
<math display="block">
\mathbf{S}_{\text{chord}} = \sum_{k=1}^{N}\left( \min( \Vert (q*p_k) - r_k \Vert, \Vert (q*p_k)+r_k \Vert ) \right)^2
</math>
==Double Quaternions==
Note that double quaternions are different from dual quaternions. 
Double quaternions are written as <math>q_1 + \epsilon q_2</math> with <math>\epsilon^2 = 1</math> and applied to a quaternion <math>p</math> representing a point as <math>q_1 p \bar{q}_2</math>. 
Dual quaternions are written as <math>q_1 + \varepsilon q_2</math> with <math>\varepsilon^2 = 0</math> and applied to a dual quaternion <math>p</math> representing a point as <math>(q_1 + \varepsilon q_2) p (\bar{q}_1 + \varepsilon \bar{q}_2)</math>
===Cayley Factorization===
See [Federico Thomas].
Any 4D rotation matrix can be decomposed into a right and a left isoclinic rotation matrix: 
<math>R = R^L R^R = R^R R^L</math> 
<math>R^R</math> and <math>R^L</math> can be viewed as a matrix representation of single double quaternion <math>(q_1, q_2)</math>. 
For a double quaternion, the 4D rotation written is <math>x' = q_1 x q_2</math>.
The product of left and right isoclinic rotation matrices commute. 
Furthermore, the product of two left isoclinic rotation matrices is a left isoclinic rotation matrix. Same with right. 
Thus, <math>R_1 R_2 = (R_1^L R_1^R) (R_2^L R_2^R) = (R_1^L R_2^L) (R_1^R R_2^R) = R</math>. 
This shows that the composition of two double quaternions will be a double quaternion.
===Approximating 3D Translations using Double quaternions===
See Ge ''et. al.''<ref name="ge1998double"></ref>
<!-- {{hidden | Algebraic Verification |
Suppose our point is <math>\mathbf{x} \in \mathbb{R}^3</math> and our translation has direction <math>\mathbf{d} \in \mathbb{R}^3</math> with distance <math>d</math>.
Let <math>q=1+\frac{d}{2}\mathbf{n}</math> and <math>q^* = 1-\frac{d}{2}\mathbf{n}</math>. 
<math>
\begin{aligned}
q(1+\mathbf{x})(q^*)^* &= (1+\frac{d}{2}\mathbf{n})(1+\mathbf{x})(1+\frac{d}{2}\mathbf{n})\\
&= [(1 - \frac{d}{2} \mathbf{n} \cdot \mathbf{x}) + (\frac{d}{2}\mathbf{n} + \mathbf{x} + \frac{d}{2}\mathbf{n} \times \mathbf{x})](1+\frac{d}{2}\mathbf{n})\\
&= \left(1 - \frac{d}{2} \mathbf{n} \cdot \mathbf{x} - ((\frac{d}{2}\mathbf{n} + \mathbf{x} + \frac{d}{2}\mathbf{n} \times \mathbf{x})) \cdot \frac{d}{2} \mathbf{n}\right) + \left(\frac{d}{2}\mathbf{n} + \mathbf{x} + \frac{d}{2}\mathbf{n} \times \mathbf{x} +\frac{d}{2}\mathbf{n} + (\frac{d}{2}\mathbf{n} + \mathbf{x} + \frac{d}{2}\mathbf{n} \times \mathbf{x})\times(\frac{d}{2}\mathbf{n})\right)\\
&= c + \left(d\mathbf{n} + \mathbf{x} + \frac{d}{2}\mathbf{n} \times \mathbf{x} + (\frac{d}{2}\mathbf{n}\times(\frac{d}{2}\mathbf{n}) + \mathbf{x}\times(\frac{d}{2}\mathbf{n}) + (\frac{d}{2}\mathbf{n} \times \mathbf{x})\times(\frac{d}{2}\mathbf{n}))\right)\\
&= c + \left(d\mathbf{n} + \mathbf{x} + \frac{d}{2}\mathbf{n} \times \mathbf{x} + (0 + \mathbf{x}\times(\frac{d}{2}\mathbf{n}) + 0)\right)\\
&= c + \left(d\mathbf{n} + \mathbf{x} + \frac{d}{2}\mathbf{n} \times \mathbf{x} - \frac{d}{2}\mathbf{n}\times \mathbf{x}\right)\\
&= c + \left(\mathbf{x} + d\mathbf{n}\right)\\
\end{aligned}
</math>
}} -->
==Dual Quaternions==
{{main | Dual quaternion}}
Dual quaternions are used to represent 3D rotations and translations together.
==Combined Point + Frame Alignment Problem==
Given a spatial profile matrix <math>M(E)</math> and orientation frame profile matrix <math>U(S)</math>, we can normalize the scale to have unit-eigenvalue and then apply linear interpolation with dimensional constant <math>\sigma</math>:
<math display="block">
\Delta_{xf}(t, \sigma) = q \cdot \left[ (1-t) \frac{M(E)}{\epsilon_{x}} + t \sigma \frac{U(S)}{\epsilon_{f}} \right] \cdot q
</math>
Or alternatively, we can use slerp:
<math display="block">
q(t) = \operatorname{slerp}(q_{x:opt}, q_{f:opt}, t)
</math>


==Resources==
==Resources==
* [https://arxiv.org/pdf/1804.03528.pdf The Quaternion-Based Spatial Coordinate and Orientation Frame Alignment Problems by Andrew Hanson] [https://journals.iucr.org/a/issues/2020/04/00/ib5072/ib5072.pdf Edited Paper]
* [https://arxiv.org/pdf/1804.03528.pdf The Quaternion-Based Spatial Coordinate and Orientation Frame Alignment Problems by Andrew Hanson] [https://journals.iucr.org/a/issues/2020/04/00/ib5072/ib5072.pdf Edited Paper]
* [https://www.researchgate.net/publication/265550132_Approaching_Dual_Quaternions_From_Matrix_Algebra Approaching Dual Quaternions From Matrix Algebra by Federico Thomas]
* Double Quaternions for Motion Interpolation by Q.J. Ge, Amitabh Varshney, Jai P. Menon, Chu-Fei Chang
* [https://probablydance.com/2017/08/05/intuitive-quaternions/ Less Weird Quaternions by Malte Skarupke]
** Derives rotations as a sequence of reflection and quaternion algebra from wedge products.
** Presents quaternions as a sequence of (90 deg rotation + scaling) operations in 3D space.
==References==
{{reflist|refs=
<ref name="ge1998double">Q.J. Ge, Amitabh Varshney, Jai P. Menon, Chu-Fei Chang (1998) Double Quaternions for Motion Interpolation</ref>
}}