四元数计算旋转方法的复杂度比较

0. 四元数相关知识概要

四元数是一种扩展的复数。像复数$n=a+bi$的形式，四元数形如

$$\mathbf{q}=q_0+q_{1}i+q_{2}j+q_{3}k$$

$$\mathbf{q}=[s,\vec{v}],s=q_0\in \mathbf{R},v=[q_1,q_2,q_3{]}^T\in {\mathbf{R}}^3$$
其中$s$称为实部，$\vec{v}$称为虚部。如果虚部为0，则称为实四元数，实部为0则称为虚四元数。

在计算机图形学、计算机视觉等学科中，常使用单位四元数表示旋转。相比欧拉角和旋转矩阵，四元数有其独到优势。

1 四元数乘法计算$qp{q}^{-1}$

1.1 四元数乘法和求逆

令$q_a=s_a+x_a\vec{i}+y_a\vec{j}+z_a\vec{k}$，$q_b=s_b+x_b\vec{i}+y_b\vec{j}+z_b\vec{k}$

四元数的共轭和模定义为：

$$\begin{array}{rl}& 共轭：{\mathbf{q}}_{\mathbf{a}}^{\ast }=[s_a,-\overrightarrow{v_a}]\\ & 模：||{\mathbf{q}}_{\mathbf{a}}||=\sqrt{s_a^2+x_a^2+y_a^2+z_a^2}\end{array}$$

则乘法和求逆如下：
$$\begin{array}{rl}& 乘法：{\mathbf{q}}_{\mathbf{a}}{\mathbf{q}}_{\mathbf{b}}=[s_a{s}_b-{\overrightarrow{v_a}}^T\overrightarrow{v_b},s_a\overrightarrow{v_b}+s_b\overrightarrow{v_a}+\overrightarrow{v_a}\times \overrightarrow{v_b}]\\ & 求逆：{\mathbf{q}}^{-1}=[\frac{q^{\ast }}{||q|{|}^2}]\end{array}$$

1.2 $p^{\prime }=qp{q}^{-1}$的计算量

设$P=\left[\begin{array}{c}x\\ y\\ z\end{array}\right]$为一三维矢量，表示某空间点。为了计算其变换后的坐标，需要将其转换为一纯虚四元数：$p=0+x\vec{i}+y\vec{j}+z\vec{k}$。因此，忽略掉加减法的计算量，仅考虑乘除运算，计算一次$qp{q}^{-1}$需要一次求逆和两次四元数乘法，总共要24次实数乘法（忽略掉与p的实部0相乘的次数）和1次实数除法。

2 先转换为旋转矩阵R，再计算RP

设单位四元数$$\mathbf{q}=q_0+q_{1}i+q_{2}j+q_{3}k$$

则有，

$$R=\left[\begin{array}{cccc}1-2q_2^2-2q_3^2& 2q_1{q}_2+2q_0{q}_3& 2q_1{q}_3-2q_0{q}_2& \\ 2q_1{q}_2-2q_0{q}_3& 1-2q_1^2-2q_3^2& 2q_2{q}_3+2q_0{q}_1& \\ 2q_1{q}_3+2q_0{q}_2& 2q_2{q}_3-2q_0{q}_1& 1-2q_1^2-2q_2^2& \end{array}\right]$$

感兴趣可以参考这篇博客证明

忽略掉加减法的计算量，仅考虑乘除运算，计算旋转矩阵最少需要3*9=27次乘法（因为$2q_1{q}_2$等项只需计算一次记录下来，实际被使用两次）。
完成对P的旋转变换最少需要$\underset{\text{计算旋转矩阵}}{\underbrace{27}}+\underset{\text{旋转矩阵乘三维点}}{\underbrace{9}}=36$次乘法。

3. 结论

在仅有一个三维点需要旋转的情况下，计算旋转矩阵进行旋转变换的方法需要的乘法次数更多（27>24）；但是当应用同一个姿态参数（旋转变换）的点数量大于1时，旋转矩阵只要计算一次后，可以保存下来重复使用，因此同一个点的平均乘法次数将更少。

所以应用中还是计算旋转矩阵进行旋转变换更好！