深度学习 CNN 3D 重构面试问题 3D 重构算法

网格处理

泊松重建

        Possion重建是Kazhdan等2006年提出的网格重建方法[1]。Possion重建的输入是点云及其法向量，输出是三维网格。Poisson有公开的源代码[2]。PCL中也有Poisson的实现。

        它的核心思想是点云代表了物体表面的位置，其法向量代表了内外的方向。通过隐式地拟合一个由物体派生的指示函数，可以给出一个平滑的物体表面的估计。

参考： 从点云到网格（三）Poisson重建： 

相机标定

5-点算法

        5-点算法是指相机内参数已知的情况下，已知二幅图像之间的 5 组图像对应点，如何求取二幅图像之间的本质矩阵，进而分解出对应的旋转矩阵和平移向量的一种方法。 5-点算法由 David Nister 于 2004 年提出（ Nister 2004），现已成为为基于图像的三维重建的一种广泛使用的方法。 5-点算法涉及大量的数学推导，有兴趣的学生可参阅这篇文章。

       5-点算法尽管理论上比较复杂，也不能得到唯一解（最多有 10组解），但在具体应用中，不正确的解可以通过其它对应点快速剔除，且作者提供了算法代码，所以，目前基于图像的三维重建，人们基本都使用 5-点算法。

        也许，人们会提的一个问题是，既然 5-点算法得到的多个解可以通过其它对应点剔除，为什么不直接用多组对应点求解本质矩阵呢？这样得到的解的个数会更少。当有 8-组对应点时，理论上可以得到唯一的本质矩阵。这主要是因为实际应用中，二幅图像之间会匹配到大量对应点，但这些对应点中有很多是错误对应点。为了提高估计的鲁棒性，人们一般在 RANSAC （ RANdom SAmplying Consensus ） (Fischler & Bolles 1981) 框架下进行估计，即反复提取待估计问题的最小点集（ minimal set） , 然后对估计的结果进行验证，而 5-组对应点是能够求取本质矩阵的最小点集。

参考： http://vision.ia.ac.cn/zh/teaching/index.html 第四章

光束法平差（Bundle Adjustment）

        也可能翻译为束调整、捆集调整、捆绑调整，或者最小化重投影误差（高翔slam---第七讲）等等。

        本质是一个优化模型（一个图优化模型），其目的是最小化重投影误差

              

光束：所谓bundle，来源于bundle of light，其本意就是指的光束，这些光束指的是三维空间中的点投影到像平面上的光束，而重投影误差，正是利用这些光束来构建的，因此称为光束法，强调光束也正是描述其优化模型是如何建立的。

平差：由于测量仪器的精度不完善和人为因素及外界条件的影响，测量误差总是不可避免的。为了提高成果的质量，处理好这些测量中存在的误差问题，实际观测值的个数，往往要多于确定未知量所必须观测的个数，也就是要进行多余观测。有了多余观测，势必在观测结果之间产生矛盾，测量平差的目的就在于消除这些矛盾而求得观测量的最可靠结果，并评定测量成果的精度。测量平差采用的原理就是“最小二乘法”。（百度词条）

重投影：也就是指的第二次投影；第一次投影指的就是相机在拍照的时候三维空间点投影到图像上，然后我们利用这些图像对一些特征点进行三角定位（triangulation，很多地方翻译为三角化或者三角剖分等等，即利用几何信息构建三角形来确定三维空间点的位置，相关内容请参考对极几何）；最后利用我们计算得到的三维点的坐标（注意不是真实的）和我们计算得到的相机矩阵（当然也不是真实的）进行第二次投影（第二次投影到图像平面上），通过最小化两次在图像平面上投影的误差，达到优化相机参数的目的。

        Bundle adjustment优化的是sum of reprojection error（重投影误差的和），这是一个（geometric distance）几何距离[为什么要minimize geometric distance可以参考[Hartley00]]，可以转换成一个least squares problem（最小二乘问题）， 如果nosie是gaussian，那就是一个最大似然估计（maximum likelihood estimator），是这种情况下所能得到的最优解了。 

        这个reprojection error的公式是非线性的，所以这个least squares problem得用迭代法来求解：一般都是用Gauss-Newton 法或者LM算法迭代求解。

        Bundle adjustmen由于是特定的形式，所以可以化成sparse matrix (稀疏矩阵)的形式，这样计算量大大减小了。不论GN,LM，中间都要解一个Ax=b形式的linear system，一般情况下算法的效率就取决于解这个linear system的效率。所以说到底，这些nonlinear least squares problem，最后也就是解一个linear system。这个linear system你可以直接解，也可以用QR分解，乔姆斯基分解 ，或者奇异值分解法来解。

robust cost(*cost也可以叫做loss, 统计学那边喜欢叫risk) function了，比较常用的有huber, cauchy等等。

• BA一种启发式的阻尼高斯牛顿法，在几何视觉中广泛使用
• BA有效性的关键在于提供理想的初始值

参考：Bundle Adjustment---即最小化重投影误差 

Bundle Adjustment简述 

点云配准

ICP算法（迭代最近点）

ICP算法能够使不同的坐标下的点云数据合并到同一个坐标系统中，首先是找到一个可用的变换，配准操作实际是要找到从坐标系1到坐标系2的一个刚性变换。

ICP算法本质上是基于最小二乘法的最优配准方法。该算法重复进行选择对应关系点对， 计算最优刚体变换，直到满足正确配准的收敛精度要求。

ICP 算法的目的是要找到，待配准点云数据与参考云数据之间的，旋转参数R和平移参数 T，使得两点数据之间满足某种度量准则下的最优匹配。