首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >EPnP:一种复杂度为O(N)的求解PnP问题的方法

EPnP:一种复杂度为O(N)的求解PnP问题的方法

作者头像
3D视觉工坊
发布于 2020-12-11 08:51:32
发布于 2020-12-11 08:51:32
3.5K0
举报

在三维视觉中,经常出现的一种情况是:我们已知一组点的三维坐标,和相机拍摄这些点时获取的二维坐标。如何通过这些二位点的坐标,(结合已知的三维坐标信息),确定出相机在世界坐标系中的位姿,即旋转矩阵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.

上述内容,如有侵犯版权,请联系作者,会自行删文。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 3D视觉工坊 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
相机图像标定
假设你现在已经拍摄了脚的多张各个角度的2D照片,那么如何将这些照片转化成一个3D数字化形状呢?首先第一步,你要对摄像机进行定标,比如确定摄像机的焦距、摆放位置和角度等。
vv彭
2020/10/27
9780
POSIT算法的原理–opencv 3D姿态估计[通俗易懂]
POSIT算法,Pose from Orthography and Scaling with Iterations, 比例正交投影迭代变换算法:
全栈程序员站长
2022/11/01
1.6K0
POSIT算法的原理–opencv 3D姿态估计[通俗易懂]
【SLAM】视觉SLAM:一直在入门,从未到精通
上周的组会上,我给研一的萌新们讲解什么是SLAM,为了能让他们在没有任何基础的情况下大致听懂,PPT只能多图少字没公式,这里我就把上周的组会汇报总结一下。
小白学视觉
2022/05/22
2K1
【SLAM】视觉SLAM:一直在入门,从未到精通
计算机视觉-相机标定(Camera Calibration)
在图像测量过程以及机器视觉应用中,为确定空间物体表面某点的三维几何位置与其在图像中对应点之间的相互关系,必须建立摄像机成像的几何模型,这些几何模型参数就是摄像机参数。在大多数条件下这些参数必须通过实验与计算才能得到,这个求解参数的过程就称之为相机标定。简单来说是从世界坐标系换到图像坐标系的过程,也就是求最终的投影矩阵 P P P的过程。 无论是在图像测量或者机器视觉应用中,摄像机参数的标定都是非常关键的环节,其标定结果的精度及算法的稳定性直接影响摄像机工作产生结果的准确性。因此,做好摄像机标定是做好后续工作的前提,是提高标定精度是科研工作的重点所在。其标定的目的就是为了相机内参、外参、畸变参数。
全栈程序员站长
2022/09/02
1.3K0
计算机视觉-相机标定(Camera Calibration)
探究高空视频全景AR技术的实现原理
笔者认为现阶段AR技术的应用是还是比较坑爹的,大都是噱头多但是实用的成分少,拿出来做做DEMO是可以,但是难以在实际的项目中落地产生实际的经济价值。一方面是很难在业务上难以找到合适的应用场景(可能管线相关的项目算一个),另一方面技术上也存在一些难以突破的问题。不管是手持设备还是AR眼镜,这些比较适合AR的硬件性能还是太弱了,导致其重建的空间信息与现实部分的空间信息存在较大的差距,这样的话就谈不上对现实的增强了。
charlee44
2025/03/01
1901
探究高空视频全景AR技术的实现原理
基于Python进行相机校准
为了校准相机,我们对3D对象(例如图案立方体)成像,并使用3D对象与其2d图像之间的3D-2D点对应关系来查找相机参数。
小白学视觉
2020/09/24
1.4K0
基于Python进行相机校准
ceres实现的pnp解算后的位姿优化代码详解
这篇文章作为基础文章也是本文的学习和理解的过程,在将会给出更多的注释和“废话”帮助自己理解。同时有错误的话欢迎各位朋友留言指教。
点云PCL博主
2022/01/27
2.4K0
SFM原理简介「建议收藏」
小孔模型成的是倒像,为了表述与研究的方便,我们常常将像面至于小孔之前,且到小孔的距离仍然是焦距f,这样的模型与原来的小孔模型是等价的,只不过成的是正像,符合人的直观感受。 在这种情况下,往往将小孔称作光心(Optical Center)。
全栈程序员站长
2022/06/24
2.5K0
SFM原理简介「建议收藏」
无人机红外相机的畸变矫正
目前采用的主流相机畸变矫正模型基本都是Brown-Conrady模型,原论文:Decentering Distortion of Lenses
zstar
2023/11/08
1.4K0
无人机红外相机的畸变矫正
相机标定——张正友棋盘格标定法
其中,R为旋转矩阵,t为平移向量,因为假定在世界坐标系中物点所在平面过世界坐标系原点且与Zw轴垂直(也即棋盘平面与Xw-Yw平面重合,目的在于方便后续计算),所以zw=0,可直接转换成式1的形式。其中变换矩阵
全栈程序员站长
2022/08/24
7.5K0
相机标定——张正友棋盘格标定法
综述 | 相机标定方法
在图像测量过程以及机器视觉应用中,为确定空间物体表面某点的三维几何位置与其在图像中对应点之间的相互关系,必须建立相机成像的几何模型,这些几何模型参数就是相机参数。在大多数条件下这些参数(内参、外参、畸变参数)必须通过实验与计算才能得到,这个求解参数的过程就称之为相机标定(或摄像机标定)。无论是在图像测量或者机器视觉应用中,相机参数的标定都是非常关键的环节,其标定结果的精度及算法的稳定性直接影响相机工作产生结果的准确性。因此,做好相机标定是做好后续工作的前提,提高标定精度是科研工作的重点所在。
AI算法与图像处理
2019/08/29
8960
综述 | 相机标定方法
万字长文|线性代数的本质课程笔记完整合集!
线性代数中最基础,最根源的组成部分是向量,那么什么是向量呢?从不同学生的视角看,有以下三种观点:
石晓文
2019/09/25
8050
万字长文|线性代数的本质课程笔记完整合集!
原创 | 《相机标定》深入理解原理与实战(一)
首先来看相机标定的意义,我们都知道,我们拍摄的图片是二维的,但是真实世界是三维的。一个场景是如何从三维变成二维的呢?相机起到的就是这个作用。我们可以把相机看成一个函数,输入是一个三维的场景,输出是我们获得的二维的图片,这里可以认为是灰度图。我们平时看到的 RGB 彩色图是通过 RGB 三通道来实现的,每个通道可以认为是一张灰度图。从三维世界到二维世界的这个映射关系是不可逆的,也就是说无法仅通过一张二维图来得到真实的三维世界。
数据派THU
2021/09/29
4K0
原创 | 《相机标定》深入理解原理与实战(一)
66. 三维重建——相机几何模型和投影矩阵
在文章29. 小孔相机中,我介绍了小孔相机的成像模型。如果你看了这篇文章,你应该至少有了一个重要印象,即相机是一个将三维物体投影为二维图像的设备。
HawkWang
2022/01/19
3K0
66. 三维重建——相机几何模型和投影矩阵
优化知多少之简述SLAM中的优化
在学习SLAM的过程中,我们会遇到各种BA问题,关于优化问题,有局部优化、全局优化、非线性优化、图优化、位姿图优化、BA优化等,那这些东西到底是什么意思? BA BA全称Bundle Adjustme
用户9831583
2022/06/16
2K0
优化知多少之简述SLAM中的优化
总结 | 相机标定的基本原理与改进方法
确定空间某点的三维几何位置与其在图像中对应点之间的相互关系,必须建立相机成像的几何模型(各个坐标系),这些坐标系之间的转换参数就是相机参数,求解参数的过程叫做相机标定(摄像机标定)。建立立体视觉系统所需要的各个坐标系,包括世界坐标系、相机坐标系、以及图像坐标系(物理和像素坐标系)。
3D视觉工坊
2020/12/11
3.5K0
总结 | 相机标定的基本原理与改进方法
机器视觉-相机内参数和外参数
一句话就是世界坐标到像素坐标的映射,当然这个世界坐标是我们人为去定义的,标定就是已知标定控制点的世界坐标和像素坐标我们去解算这个映射关系,一旦这个关系解算出来了我们就可以由点的像素坐标去反推它的世界坐标,当然有了这个世界坐标,我们就可以进行测量等其他后续操作了~上述标定又被称作隐参数标定,因为它没有单独求出相机的内部参数,如相机焦虑,相机畸变系数等~一般来说如果你仅仅只是利用相机标定来进行一些比较简单的视觉测量的话,那么就没有必要单独标定出相机的内部参数了~至于相机内部参数如何解算,相关论文讲的很多~
小白学视觉
2022/02/14
1K0
机器视觉-相机内参数和外参数
双眼可以测距和建立立体环境,双摄像头可以吗?
这方面一直是计算机视觉的研究热点,并且已经有了不错的成果!本人研究生阶段主要做三维重建,简单写一些自己所了解的。
3D视觉工坊
2023/04/30
7770
双眼可以测距和建立立体环境,双摄像头可以吗?
OpenGL矩阵变换的数学推导
说起OpenGL的矩阵变换,我是之前在我们的项目天天P图、布丁相机中开发3D效果时才比较深入地研究了其中的原理,一直想写这篇文章,由于很忙(lǎn),拖了很久,再不写我自己也要忘了。 一开始时,也只是知道怎么去用这些矩阵,却不知道这些矩阵是怎么得来的,当出现一些莫名其妙的问题时,如果不了解其中的原理,就不知道如何解决,于是想彻底搞懂其中的原理,还好自己对数学挺有兴趣,于是从头到尾把推导过程研究了一遍,总算掌握了其中的奥秘,不得不佩服OpengGL的设计者,其中的数学变换过程令人陶醉,下面我们一起来看看。 这
天天P图攻城狮
2023/04/10
1.4K0
OpenGL矩阵变换的数学推导
OpenGL坐标转换推导(十一)
之前我们已经提到在OpenGL中,所有物体都是在一个3D空间里的,但是屏幕都是2D像素数组,所以OpenGL会把3D坐标转变为适应屏幕的2D像素,最终投射到2D的屏幕上去。所以对于每一个顶点坐标都会依次进行model、view、projection三种变换。这三种变换实现代码如下:
PengJie
2021/01/10
2.7K0
相关推荐
相机图像标定
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档