总结！聊一聊三种三维重建经典算法（立体激光球）

作者：PCIPG-晨艺| 来源：3DCV

添加*dddvisiona，备注：3D点云，拉你入群。文末附行业细分群。

1 什么是三维重建

在计算机视觉中，三维重建是指根据单视图或者多视图的图像重建三维信息的过程。由于单视频的信息不完全，因此三维重建需要利用经验知识，而多视图的三维重建(类似人的双目定位)相对比较容易，其方法是先对摄像机进行标定，即计算出摄像机的图像坐标系与世界坐标系的关系，然后利用多个二维图像中的信息重建出三维信息。如下图所示，故三维重建可以简单理解为相机摸象的过程。

1、深度图 (depth) 每个像素值代表的是物体到相机xy平面的距离，由深度摄像头获取

2、点云(point cloud) 某个坐标系下的点的数据集，由三维激光雷达获取

3、网格(mesh) 全部由三角形组成的多边形网格

4、体素 (Voxel) 三维空间中的一个有大小的点，一个小方块，相当于是三维空间种的像素。

景物的深度图像由Kinect在Windows平台下拍摄获取，同时可以获取其对应的彩色图像。为了获取足够多的图像，需要变换不同的角度来拍摄同一景物，以保证包含景物的全部信息。具体方案既可以是固定Kinect传感器来拍摄旋转平台上的物体；也可以是旋转Kinect传感器来拍摄固定的物体。

推荐学习3D视觉工坊三维点云课程：

[1]

[2]

受到设备分辨率等限制，它的深度信息也存在着许多缺点。为了更好的促进后续基于深度图像的应用，必须对深度图像进行去噪和修复等图像增强过程。目前深度相机输出的depth图还有很多问题，比如对于光滑物体表面反射、半/透明物体、深色物体、超出量程等都会造成深度图缺失。而且很多深度相机是大片的深度值缺失，这对于算法工程师来说非常头疼。

整个计算过程实际上是从世界坐标系到像素坐标系（不考虑畸变）的过程，用一幅图来总结其转换关系：

世界坐标系：描述环境中任何物体的位置。
相机坐标系：在相机上建立的坐标系，为了从相机的角度描述物体位置而定义，作为沟通世界坐标系和图像/像素坐标系的中间一环。单位为m。以相机的光心为坐标原点，X 轴和Y 轴分别平行于图像坐标系的 X 轴和Y 轴，相机的光轴为Z 轴，用（Xc, Yc, Zc）表示其坐标值。
图像坐标系(image coordinate system)：描述物体从相机坐标系到图像坐标系的投影透射关系，方便进一步得到像素坐标系下的坐标。以图像平面的中心为坐标原点，X轴和Y 轴分别平行于图像平面的两条垂直边，用( x , y )表示其坐标值。图像坐标系是用物理单位（例如毫米）表示像素在图像中的位置。
像素坐标系(pixel coordinate system)：描述物体成像后的像点在数字图像上（相片）的坐标，是我们真正从相机内读取到的信息所在的坐标系。单位为个（像素数目）。以图像平面的左上角顶点为原点，X 轴和Y 轴分别平行于图像坐标系的 X 轴和Y 轴，用(u , v )表示其坐标值。数码相机采集的图像首先是形成标准电信号的形式，然后再通过模数转换变换为数字图像。每幅图像的存储形式是M × N的数组，M 行 N 列的图像中的每一个元素的数值代表的是图像点的灰度。这样的每个元素叫像素，像素坐标系就是以像素为单位的图像坐标系。

对于多帧通过不同角度拍摄的景物图像，各帧之间包含一定的公共部分。为了利用深度图像进行三维重建，需要对图像进行分析，求解各帧之间的变换参数。深度图像的配准是以场景的公共部分为基准，把不同时间、角度、照度获取的多帧图像叠加匹配到统一的坐标系中。计算出相应的平移向量与旋转矩阵，同时消除冗余信息。点云配准除了会制约三维重建的速度，也会影响到最终模型的精细程度和全局效果。因此必须提升点云配准算法的性能。三维深度信息的配准按不同的图像输入条件与重建输出需求被分为：粗糙配准、精细配准和全局配准等三类方法。配准过程中，匹配误差被均匀的分散到各个视角的多帧图像中，达到削减多次迭代引起的累积误差的效果。值得注意的是，虽然全局配准可以减小误差，但是其消耗了较大的内存存储空间，大幅度提升了算法的时间复杂度。

经过配准后的深度信息仍为空间中散乱无序的点云数据（如下图），仅能展现景物的部分信息。因此必须对点云数据进行融合处理，以获得更加精细的重建模型。

以Kinect传感器的初始位置为原点构造体积网格，网格把点云空间分割成极多的细小立方体，这种立方体叫做体素(Voxel)。为了解决体素占用大量空间的问题，提出了TSDF (Truncated Signed Distance Field，截断符号距离场)算法（如下图），该方法只存储距真实表面较近的数层体素，而非所有体素。因此能够大幅降低KinectFusion的内存消耗，减少模型冗余点。

通过为所有体素赋予TSDF（Truncated Signed Distance Field，截断有效距离场）值，来隐式的模拟表面。下图所示，计算出TSDF值，即此体素到重建表面的最小距离值。当TSDF值大于零，表示该体素在表面前；当TSDF小于零时，表示该体素在表面后；当TSDF值越接近于零，表示该体素越贴近于场景的真实表面。于是形成重建的表面。

1、原理基于八叉树和泊松方程的一种网格三维重建算法，利用指示函数，可以对空间内部的所有有效指示函数实现梯度计算，通过求解这个函数提取等值面，得到表面的过程，即构建泊松方程并对其求解的过程。2、算法流程

3、核心代码

//----------------------------------法线估计------------------------------------pcl::NormalEstimation<pcl::PointXYZ,pcl::Normal>n;//法线估计对象pcl::PointCloud<pcl::Normal>::Ptrnormals(newpcl::PointCloud<pcl::Normal>);//存储估计的法线pcl::search::KdTree<pcl::PointXYZ>::Ptrtree(newpcl::search::KdTree<pcl::PointXYZ>);tree->setInputCloud(cloud);n.setInputCloud(cloud);n.setSearchMethod(tree);n.setKSearch(10);n.compute(*normals);//-------------------------------连接法线和坐标---------------------------------pcl::PointCloud<pcl::PointNormal>::Ptrcloud_with_normals(newpcl::PointCloud<pcl::PointNormal>);pcl::concatenateFields(*cloud,*normals,*cloud_with_normals);//---------------------------------泊松重建-------------------------------------pcl::search::KdTree<pcl::PointNormal>::Ptrtree2(newpcl::search::KdTree<pcl::PointNormal>);tree2->setInputCloud(cloud_with_normals);pcl::Poisson<pcl::PointNormal>pn;pn.setSearchMethod(tree2);pn.setInputCloud(cloud_with_normals);pn.setDepth(6);//设置将用于表面重建的树的最大深度pn.setMinDepth(2);pn.setScale(1.25);//设置用于重建的立方体的直径与样本的边界立方体直径的比值pn.setSolverDivide(3);//设置块高斯-塞德尔求解器用于求解拉普拉斯方程的深度。精度pn.setIsoDivide(6);//设置块等表面提取器用于提取等表面的深度平滑度pn.setSamplesPerNode(10);//设置每个八叉树节点上最少采样点数目八叉树节点上的采样点数速度pn.setConfidence(false);//设置置信标志，为true时，使用法线向量长度作为置信度信息，false则需要对法线进行归一化处理pn.setManifold(false);//设置流行标志，如果设置为true，则对多边形进行细分三角话时添加重心，设置false则不添加pn.setOutputPolygons(false);//设置是否输出为多边形(而不是三角化行进立方体的结果)。

4、结果展示

1、算法流程给出三维空间中的n个顶点，求解由这n个顶点构成的凸包表面

1）首先任选4个点形成的一个四面体(初始凸包)然后每次新加一个点P分两种情况：a. P在凸包内，则可以跳过。b. P在凸包外，对于某边，找到从这个点可以“看见”的包含该边的面S（能不能看见可以用法向量来计算，看点是否在面外侧），删除这些面S，然后用S的除该边外的另外两边与点P新构成两个面。这样遍历所有边，就将P加入该凸包中，并形成了新的凸包。2）遍历所有点，最后得到整个点集的凸包。2、核心代码

//---------------------对上述点云构造凸包-----------------------pcl::ConvexHull<pcl::PointXYZ>hull;//创建凸包对象hull.setInputCloud(cloud);//设置输入点云hull.setDimension(3);//设置输入数据的维度(2D或3D)vector<pcl::Vertices>polygons;//设置pcl:Vertices类型的向量，用于保存凸包顶点pcl::PointCloud<pcl::PointXYZ>::Ptrsurface_hull(newpcl::PointCloud<pcl::PointXYZ>);//该点云用于描述凸包形状hull.setComputeAreaVolume(true);//设置为真，则调用qhr库来计算凸包的总面积和体积hull.reconstruct(*surface_hull,polygons);//计算3D凸包结果floatArea=hull.getTotalArea();//获取凸包的总面积floatVolume=hull.getTotalVolume();//获取凸包的总体积cout<<"凸包的面积为："<<Area<<endl;cout<<"凸包的体积为："<<Volume<<endl;

3、结果展示

1、原理在三维层面上来讲，该算法我们可以想象为一个球在一堆点集中进行滚动，符合条件的三个点即会构成一个多边形，这个条件是一种“空球法则” (类似于空圆法则)，也就是说这个球除三个基本点之外不会包含其他的点。

从右图中可以看出，球并没有滚到P11和P12两个点，那么这时我们猜想：如果缩小球的半径，是否就可以遍历更多的点，从而输出的点云就更加的清晰完整呢？2、核心代码

pcl::ConcaveHull<pcl::PointXYZ>cavehull;cavehull.setInputCloud(cloud);cavehull.setAlpha(0.001);vector<pcl::Vertices>polygons;cavehull.reconstruct(*surface_hull,polygons);//重建面要素到点云

3、结果展示设置半径分别为0.5、0.1、0.05、0.02时，得到下面四种结果