EPnP：一种复杂度为O(N)的求解PnP问题的方法 点击上方“3D视觉工坊”，选择“星标” 干货第一时间送达 在三维视觉中，经常出现的一种情况是：我们已知一组点的三维坐标，和相机拍摄这些点时获取的二维坐标。如何通过这些二位点的坐标，（结合已知的三维坐标信息），确定出相机在世界坐标系中的位姿，即旋转矩阵R和平移向量t？这个问题称作Perspective-n-Point 问题，简称PnP问题。 简单来说，由于R矩阵有3个自由度，平移向量t也有3个，所以提供3组对应点构成约束即可求解出。但利用更多的对应点，可以求的更加精准，为此出现了很多方法，但这些方法的计算复杂度都很高，复杂度随着匹配点个数N的增加往往呈指数上涨，达到图片，甚至有的达到了图片。而EPnP[1]方法的随着点数N的增加，复杂度仅为线性增加，具有优良的性质。在这里将介绍EPnP的基本思路，并简要介绍具体方法，而略去复杂的计算技巧。 图片 （图：EPnP算法与其它算法对比，随3D点数量增加时的计算用时变化情况） 一、基本思路 1. EPnP方法首先对空间中的所有3D点，计算4个控制点，控制点描述了这些3D点的空间分布，得到的控制点的坐标在世界坐标系下； 2. 之后通过相机拍摄的2D点，表示出控制点在相机坐标系下的坐标； 3. 由空间3D点得到的控制点的坐标为世界坐标系，而由相机拍摄的2D点得到的控制点坐标在相机坐标系，二者虽不同，但两个控制点间的距离是对应相同的，由此确定控制点在相机坐标系下的坐标； 4. 此时我们已知了4个控制点在世界坐标系和相机坐标系下的坐标，之后利用任意3D-3D匹配方法，即可计算R和t. 二、一些细节 1. 利用空间的3D点计算控制点 EPnP的巧妙之处在于，利用所有3D点得到了4个控制点，再利用控制点去计算，避免了后续计算的复杂。控制点我们用图片进行表示，对于每个3D点图片，应满足： 图片 即4个控制点通过加权可以表示任何一个3D点，且权重和为1。这样的组合可以有无数种，但根据资料和经验表明[2]，将一个控制点选为点云的重心，剩下的3个按照点云的主方向依次选取，类似于PCA确定主方向的方法进行选取，具有更好地计算精度。（至于为什么可以这样组合加权，谈一下个人的理解：当系数和为1时，2个不共线向量线性组合可以表示两个向量终点构成的一条直线；3个不共面向量可以表示张成的一个平面；那么4个点既可充分表示空间中的任意一点） 具体计算过程如下：对所有3D点{图片}，设共有N个： a) 计算3D点的中心点图片，控制点图片 b) 每个3D点减去中心，构成C矩阵：图片 c) 对矩阵图片进行SVD分解，对应的3个奇异向量即为控制点图片 d) 对于每一个具体的3D点，利用图片，与图片，构成了4个方程，即可求出具体的图片。 2. 控制点在相机坐标系下的坐标表示 我们假设在相机坐标系中，控制点为图片，根据相机投影模型，可以写出： 图片 可以得到两组方程： 图片 图片 我们可以发现，式中只有控制点在相机坐标系中的坐标为未知量，另图片，对应的系数写成一个矩阵M，则有方程：Mx=0，其中M的维度是2Nx12，N是所有3D点，也是所有相机拍摄的2D点的个数。等式为0意味着x必定在M的右零空间，也就是M的0奇异值对应的向量张成的空间，等价于图片的0特征值对应的特征向量张成的空间。 那么实际上是图片的特征值是什么样子的呢？论文中给出了解释，当相机参数不同时，0特征值的数量不同（这在一定程度上可以理解成，相机模型不同，具有的自由度不同），但至多有4个，并绘制了特征值的曲线，从下图可以看出第9~12个特征值都接近为0。 图片 （图：相机不同焦距f下，图片的特征值取值；可以看出最小的几个为0，最多有4个） 3. 控制点在相机坐标系下的求解 具体的求解时，根据2的分析，我们已知图片可以写成图片矩阵零特征值的线性组合，即： 图片 其中图片表示特征向量，K代表当前相机模型下有多少个0特征值，而图片即为线性组合的系数。在实际应用中，时常假设有4个0特征值（如果不是，大不了有几个的图片算为0即可），那么我们的目标是求解图片，因为图片已经能够通过M求解出来。 求解时，利用“两个控制点在世界坐标系下坐标的距离，与在相机坐标系下坐标的距离相同”，来进行计算，这是一个超定问题，因为存在6个方程（4个控制点，有图片种不同的组合），却只有4个未知数（图片），所以求解的是一个最小二乘问题，即 图片 其中图片表示第i和j个控制点在相机坐标系中的距离。然而具体的求解有涉及了一些数学知识，详见[3]。至此计算出了线性组合的系数图片，由此能够得到相机坐标系下的控制点坐标。 4. 之后利用任何3D-3D算法，即可轻易得到R和t。 三、一些补充说明 1. 文章提到，这种方法复杂度最高的一步是根据M矩阵计算图片，这一步的复杂度是随着N（3D点数）的增加而线性增加的，所以算法的复杂度是图片； 2. 文章提到，在利用这种方法计算出R和t后，可以利用其它迭代方法进行进一步精确地计算，由于已经提供了很好的初值，所以迭代也会很快； 3. 个人认为，将众多3D点计算出有限的控制点，充分利用了全部信息并降低了数据维度，是EPnP算法的精妙之处。 图片 （图：论文中的实验结果） 备注：本文作者为我们「3D视觉从入门到精通」星球特邀嘉宾。 参考文献： 1. EPnP: An Accurate O(n) Solution to the PnP Problem. 2. Multiple view geometry in computer vision. 3. Cryptanalysis of the HFE public key cryptosystem by relinearization. 上述内容，如有侵犯版权，请联系作者，会自行删文。