点云表面重建经典算法-四面体剖分+图割

最近看OpenMVS时，发现网上关于在恢复得到稠密三维点云后如何进一步获取三维网格的资料几乎是没有。这部分核心其实在于如何将问题抽象成一个基于点云的四面体剖分的标注问题，也就是如何构建一个图割问题。本文记录下笔者对构建这个图割问题的理解。如果有错误，欢迎评论指出。

一.算法步骤

1.四面体剖分

基本定义

二维三角剖分在三维上的推广，其基本的组成单元为四面体(cell)，由四个顶点（vertex），四个面（face），6个边 （edge）组成。对于一组三维散点，其四面体剖分可以看成是对其凸包的一个划分，而划分的基本结构为四面体。多个四面体间的关系是要么不相交，要么共享一个共同的面（face）、一条边（edge）或一个顶点（vertex）。当然这个剖分还满足一些其它的性质，这里只做形象的理解就不做介绍了。图1中展示了对一个球和正方体的四面体剖分[4]。注意face是一个三角形。

infinite cell

为了处理cell，会引入辅助的infinite vertex，与凸包上的面构成了新的infinite cell，便于处理凸包边界面的特殊情况。图2是一个示例。这里注意 1）对边界cell进行构建；2）infinite vertex并不是一个实际物理位置；3）infinite cell位于凸包之外；4）infinite cell可以有多个。

2.图割问题构建

构建图结构

由于三维图不好画，这里以二维进行说明[2]。图3中，每个小黑点为vertex，所绘制的三角形（即cell）为这组vertex的一个剖分，c为相机中心，p为观测vertex。注意图中的每条边其实代表一个face。

图4中，大黑点代表cell，构成图结构的一个节点；如果两个cell共享一个共同的face，那么这两个cell连接构成了图结构的一条有向边 [5]。此步得到的图结构可以用于二值标注任务。一个cell要么被标记为内部，要么被标记为外部，表面被隐式地生成为位于不同标记cell之间的face的集合。为方便叙述，后文记这部分节点为剖分节点。

进一步地，图割问题构建了两个额外的节点，称为源点（source，本例为outside）和汇点（sink，本例为inside）（注：根据文献来看，这两个节点的可以设置为相机中心，也可以设置为上述提到的infinite cell）。这两个节点及与它们与其他节点连接的边在剖分里没有对应关系，仅仅是为了用于标注问题而引入的。为叙述方便，后文记剖分节点之间的边为n-link，outside/inside节点与剖分节点之间的边为t-link[6]。

计算图结构的边权重

这里继续以图4所示的一个观测点和一个相机为例。当前观测点到相机的视线 pc→所穿过的cell应该标注为outside，在观测点p后方的cell应标记注为inside。更具体地说，这种可见性约束可归纳成3个准则：重建曲面应经过视线起点p; 视线穿过的最后一个cell应标注为outside；与视线相交的face应受到惩罚[1]。

这段话可能不好理解，可以配合图5理解。图中有一个球形物体、一面墙壁和地面，物体、墙壁和地面所在空间是"内"空间，在图中显示为蓝色。图中有三个传感器，每个传感器都有多条光线，不同传感器的光线用不同颜色表示。可以看到，图中清晰的展示出了两种空间：由蓝色显示的空间由于存在实体而未被光线穿过，为“内”空间。其余不存在实体的空间被光线穿过，属于"外"空间。两类空间的交界处正好是点云表面。

首先是t-link边的权重，视线穿过的最后一个cell与outside形成的t-link边获得$α_s$的加权，视线起点后的第一个cell（注：实际计算中会沿着 cp→再移动一定距离，所以在图中会发现多了一条横向的n-link边）与inside形成的t-link边获得${\alpha }_t$的加权。

然后是n-link边的权重，具体包含两项：

一项为$w_{vis}={\alpha }_{vis}(1-e^{-d^2/2{\sigma }^2})$，其中${\alpha }_{vis}$为正常数；$d$为观测点到视线与face交点的距离；$\sigma$为点云的容忍参数；

另一项为 $w_{qual}=1-mincos(\varphi ),cos(\psi )$，其中$\varphi$和$\psi$定义如图6所示，为face相邻的两个cell的外接球与face所在平面的夹角（注：该项为平滑项，会提升重建曲面的质量）。

求解最小割

对所有的观测点-相机点对进行如上计算，完成对图中边权重的赋值后，我们通过求解图结构的最小割，使得能量$E(S)=E_{vis}(S)+{\lambda }_{qual}{E}_{qual}(S)$最小。在最小割过程中，图结构的不连通边得到了一组face，构成了最终的重建曲面S。

二.参考资料

[1] Robust and efficient surface reconstruction from range data

[2] Robust Surface Reconstruction from Noisy Point Clouds using Graph Cuts

[3] A visibility-based surface reconstruction method on the GPU

[4] 3D Triangulations: User Manual

[5] https://www.cnblogs.com/qingsunny/archive/2013/05/05/3060767.html

[6] 锦恢：基于 Graph Cut 的可交互式图像分割——原理与代码实现

[7] 顾及点云结构特征的快速点云表面重建算法