在三维视觉中,经常出现的一种情况是:我们已知一组点的三维坐标,和相机拍摄这些点时获取的二维坐标。如何通过这些二位点的坐标,(结合已知的三维坐标信息),确定出相机在世界坐标系中的位姿,即旋转矩阵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.
上述内容,如有侵犯版权,请联系作者,会自行删文。