定位动捕背后，VR的算法都有哪些？

雷锋网按：本文作者系VR行业资深从业者。

via： news.livedoor.com

2016年，VR如龙卷风一样席卷了整个科技圈，一时间，恨不得所有行业都要跟VR搭上边才能体现其与时俱进的创新性，也有越来越多的人开始了解并走进VR，当然其中不乏一些凑热闹的人。正所谓，这年头吹牛的时候不整点专业的词都不好意思唬人。笔者简单整理了几个VR中常用到的算法供大家参考。这些看起来非常高大上的算法，你了解几个呢？

1、FK算法

运动分为正向运动和反向运动。 F K是 forward kinematics的缩写， 即正向动力学；IK是Inverse Kinematics的缩写，即反向运动学。人体的分级结构骨架，由许多采用分级方式组的环节链构成，包括分级结构关节或链，运动约束和效应器，由效应器带动所有部分同时运动。

例如，肩关节、肘关节、腕关节及其子骨骼就是一条环节链，也就是运动链，是整个人体运动链上的一条分支，而我们的身体即是利用运动链对运动进行控制的。已知链上各个关节旋转角，求各关节的位置信息和末端效应器(end effector)的位置信息，这是正向运动学的问题；而己知末端效应器的位置信息，反求其祖先关节的旋转角和位置，这就是反向运动学。

首先，我们先一起详细了解一下FK，即正向动力学。

正向动力学认为子级关节会跟随父级关节的运动，而子级关节又可以独立运动而不影响到父级关节的状态。以人体运动为例，当我们举起手臂时，腕关节会随其父级肘关节上抬，肘关节会随其父级肩关节的旋转而移动。担当腕关节旋转时，其上级关节都不会发生运动，这就是典型的正向动力学运动方式。因此，如果我们已知运动链上每个关节的旋转角，就可以控制其子级关节的运动。

正向动力学的优势是计算简单，运算速度快，缺点是需指定每个关节的角度和位置，而由于骨架的各个节点之间有内在的关联性，直接指定各关节的值很容易产生不自然协调的动作。 应用于VR动作捕捉行业时使用者需要在每一个骨骼分支都佩戴动捕设备，使用不方便。

正向动力学被应用于VR动捕技术中，具体实现流程是：

使用者身上每一个骨骼分支都佩戴动作捕捉节点，例如手部、小臂、大臂、肩膀构成一条链。动作捕捉节点获取每个骨关节在运动过程中的旋转角，将旋转角应用到FK算法中，与相对应的骨骼长度一起即可计算出子关节和末端效应器的位置信息，再利用这些信息控制整个人体模型的运动。

应用：动作捕捉技术。

2、 IK算法

接下来我给大家介绍一下IK，即反向动力学。

上文已经介绍了IK算法所要解决的问题，我再以投球动作为例说明：如果我们知道出球的起始位置、最终位置和路径，那么投球者手臂等的转动即可按反向运动学自动算出。 反向运动学方法在一定程度上减轻了正向运动学方法的繁琐工作，是生成逼真关节运动的最好方法之一。

求解IK问题的方法有很多，大致可以分为两大类：

解析法 （AnalyticSolutiosn）：可以求得所有的解，对于自由度较少的IK链，求解速度较快，比较适合应用于自由度较少的控制中，便于实时控制。但随着关节数量的增加，解析法求解方程的复杂度也急剧增加。所以解析法只适合自由度比较少的链，不适合复杂的IK链。

数值法 （Numerialsolutions）：数值法的优势在于通用性和灵活性，能处理自由度较多的比较复杂的具有分层结构的IK链，并且能较容易的实现在IK链中加入新的约束条件。数值法实际上是一种反复逼近，不断迭代的方法。由于IK问题的复杂性，数值法的不足之处在于高计算量，由于是反复迭代进行求解，所以所求结果未必准确。

由于反向动力学可以解决定位问题，所以VR动作捕捉技术、手势识别技术均可应用IK算法。 我以动作捕捉技术为例说明具体实现流程如下：

动作捕捉技术是通过使用称为跟踪器的专门的传感器来记录运动者的运动信息。 然后，我们就可以利用所记录下来的数据来产生动画运动。

利用IK算法进行动作捕捉的大体流程如下：

• 首先在VR内容中建立人体模型，然后为人体模型预留数据接口；

• 利用硬件获取末端效应器的位置信息，然后利用IK（反向动力学）算法计算出人体运动数据，包括关节旋转角和位置等；

• 再将这些信息赋予人体模型预留的接口，驱动人体模型按照佩戴硬件的目标人物动起来，并显示在内容中。

应用：动作捕捉技术、手势识别技术。

3、PNP

PNP准确来说是一个问题，PNP 问题是由 Fisher 和 Bolles于 1981 年提出的。

PNP 问题的具体表述如下： 在已知给定n个特征点中任意两个特征点之间的距离以及这两个特征点与光心所成的角度，来求解各特征点与光心的距离，这就是PNP问题。 PNP的主要用处 就是可以确定目标物体上的n个特征点在摄像机坐标系下的坐标，然后根据标定获取的摄像机内外部参数，求算出特征点在世界坐标系下的坐标值，最终给出目标的位姿信息。

PNP 问题是一种基于单幅图像的定位解算方法，在VR目标定位和姿态解算上得到广泛的应用。

求解PNP问题的方法有很多，大致可以分为两大类，非迭代算法和迭代算法：

非迭代算法主要是针对 P3P、P4P 等特征点较少的PNP 问题进行研究，主要是应用数学代数算法直接求解被测目标的相对位姿，并且还推导出多种解析算法。 非迭代算法运算量小算法计算速度快，但是受系统误差影响较大，而且解算精度一般情况下都不高，主要被应用于迭代算法的初值计算。非迭代算法求解主要对象是针对于6个以上异面特征点或是有4个以上共面特征点两种情况。

迭代算法应用于求解PNP问题时，是基于不存在图像噪声假设条件下进行推导的，得出解析解相对于摄像机特征像点的位置误差的敏感度特别高。而为了克服噪声的影响，提高位姿解算精度，多采用PNP迭代算法进行位姿信息的求解，其主要思路是将PNP 问题进一步表示为一种受约束的非线性优化问题，通过求解得到被测目标相对位姿的数值解。该处理方法的优化变量空间为N+6维（N为点特征数），迭代计算量较大，又受初始值解算精度影响，因此算法通常会收敛到局部最小值或收敛到错误解，而不是全局最小值。

可能上述的描述会比较抽象，这里我以P3P为例，为大家举例说明：

如上图：O 为相机光心，目标的三个特征点 A， B ，C 与光心 O 之间的长度分别为 x， y， z ，已知三条线间的夹角为α，β，γ， |AB|=c ，|AC|=b  |BC|=a，利用α，β，γ和a，b，c求解 x， y， z，这就是P3P问题。

P3P 问题特征点数目只有3个，可以直接使用非迭代算法，其方程描述如下：

设 A'，B'，C'分别是 A， B，C在摄像机成像平面上的点，则在求得 x ，y，z 后，利用A'， B' ，C'坐标， 根据摄像机的成像关系，就可解算的特征点在摄像机坐标系下的坐标 。

PNP算法可以应用于VR的定位技术，如红外光学定位技术，用来获取位姿信息。

具体实现流程：

• 摄像机获取目标物体的图像，然后在图像中提取出特征点；

• 再利用PNP算法获得特征点在摄像机坐标系下的坐标；

• 然后利用旋转理论将摄像机坐标系下的坐标转换到世界坐标系下，最终获得世界坐标系下特征点的信息。

 

应用：红外光学定位等VR定位技术。此外，PNP获取的位姿信息还可以应用到IK算法中，共同实现VR动作捕捉。

4、POSIT算法

实际上，POSIT算法是上文提到的PNP问题迭代算法的一种，之所以特别提出来说是因为POSIT算法具有收敛域广和算法速度快的优点，在VR行业中得到非常广泛的应用。迭代算法作为 PnP 问题解法的一个分支，相比于非迭代解法而言可以避免求解非线性方程组，在一定程度上减少了计算复杂度，POSIT 算法即是迭代算法的典型代表。

POSIT 算法输入为至少 4个非共面的三维物体表面的三维特征点坐标及其对应的图像上二维特征点的坐标，它是基于三维物体上所有点都具有相同深度（忽略物体内部各点的深度差异）的弱投影假设实现的。

首先通过正交投影和尺寸变换关系求得三维物体位姿参数的初值（POS, Pose from Orthography and Scaling 算法），然后利用此初值对起始特征点进行重投影，将重投影所得的新的点作为新的位姿测量参数，重新运行 POS 算法，经过反复迭代直到满足所需的精度。

POSIT算法具有以下优点：相对于传统迭代算法，POSIT 不需要一个近似的初始姿态估计；算法易于编写代码实现，传说中在 MATLAB 环境下只需要25 行必要的代码就是它了；相对于数值迭代算法，POSIT 算法的时间只是相当于前者的 10%。

应用：红外光学定位等VR定位技术。

以上我介绍了几个VR中比较常用的问题和算法，文章涉及内容不深，只做简单科普。如果您是行业小白，又想了解VR，希望我的文章能够帮到你。

雷锋网注：本文为雷锋网 (搜索“雷锋网”公众号关注) 独家约稿，转载请联系授权，并保留出处和作者，不得删减内容。