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, \ | 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>. | |||
In general, quaternion multiplication does not commute: <math>q_1 * q_2 \neq q_2 * q_1</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 | 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> | |||
}} |