泊松重建算法原理介绍

本文出自CSDN点云侠，原文链接。爬虫自重，把自己当个人。

1、泊松重建算法

  泊松重建是Kazhdan M在2006年提出的基于八叉树和泊松方程的一种网格三维重建算法。其本质是一种隐函数表面重建算法，在空间中用一个表面来区分内外，直观理解为表面外、表面内。用0、1来表示内外表面，可以简单理解为若某一元素属于这个集合则为1，即表面内，若某一元素不属于这个集合则为0，即表面外。这个关系就是Kazhdan M提出的指示函数，利用指示函数，可以对空间内部的所有有效指示函数实现梯度计算，通过求解这个函数提取等值面，得到表面的过程，即构建泊松方程并对其求解的过程。
  在论述泊松重建之前，首先对算法内用到的八叉树进行了研究。八叉树是指，若树非空，那么树中任意节点的子节点要么为0个要么为8个，是用来表示三维空间的树状数据结构。任意一个立方体可以最少被分为八个等分的小立方体，用八叉树的每个节点可以表示每个小立方体，这八个字节点合起来就是其父节点表。如图1所示：

  将场景点云数据利用八叉树划分空间区域，将每个点放到正方形的空间里，设定某一阈值，如果该正方形内的数据点超过这个阈值，就将该正方体再次划分，直到每个小正方体包含的点数小于或等于这个阙值，每个小正方体就是一个叶节点，记其最大深度为D，用以存储目标物体的点云数据。
  以八叉树的结构存储实验获取的点云数据，极大地方便了算法在实现过程中数据的存储及检索。

2、泊松重建核心思想及原理

（1）核心思想
  泊松重建的核心思想为：将物体区分为几何体内部和几何体外部，物体点云数据的法向量可以标示内部和外部，通过隐式地拟合该物体的指示函数，得到该物体表面的估计，即通过将物体表面的离散的点的信息转化到连续的表面函数上，从而构建出表面。
  设某一物体为 M M M，该物体的表面为 δ M \delta M δM，其指数函数 χ M \chi_M χM​为：
χ M ( x ) = { 0 , x ∉ M 1 , ∈ M (1) \chi_M(x)= \begin{cases} 0,\quad x\notin M\\ 1, \in M \end{cases} \tag{1} χM​(x)={0,x∈/M1,∈M​(1)
其中点云法向量与 χ M \chi_M χM​的关系如图2所示：

  指数函数 χ M \chi_M χM​为分段函数，表示 q 0 q_0 q0​在表面内其值为1，在表面外的点其值为0。显然，若得到每一个点 q 0 q_0 q0​的 χ M ( q 0 ) \chi_M(q_0) χM​(q0​)，即可知道整个物体的表面。
  如果直接插值得到 χ M ( q 0 ) \chi_M(q_0) χM​(q0​)显然是不可能的，因为 χ M \chi_M χM​不具有连续性，直接插值得到0到1之间的没有意义，因此不能使用该算法。可以先用平滑滤波函数平滑指数函数。
（2）法向量到梯度空间
  首先，先用平滑函数 F ˉ \bar{F} Fˉ来平滑 χ M \chi_M χM​，对于任意点 p ∈ δ M p\in\delta M p∈δM，定义 N ⃗ δ M ( p ) \vec{N}_{\delta M}(p) N δM​(p)为指向内侧的表面法向量，规定 F ( q ) F(q) F(q)为平滑滤波器， F ( q − p ) F(q-p) F(q−p)表示 F F F沿 p p p方向的位移，因为指示函数 χ M \chi_M χM​不好求导，可以利用 χ M ∗ F ˉ \chi_M*\bar{F} χM​∗Fˉ两个函数的卷积的倒数近似求解 χ M \chi_M χM​，即：
Δ ( χ M ∗ F ˉ ) ( q 0 ) = Δ ∣ q = q 0 ∫ M F ˉ ( q − p ) d p = ∫ δ M F ˉ ( q 0 − p ) N ⃗ δ M ( p ) d p (2) \Delta(\chi_M*\bar{F})(q_0)=\Delta|_{q=q_0}\int_M\bar{F}(q-p)dp=\int_{\delta M}\bar{F}(q_0-p)\vec{N}_{\delta M}(p)dp\tag{2} Δ(χM​∗Fˉ)(q0​)=Δ∣q=q0​​∫M​Fˉ(q−p)dp=∫δM​Fˉ(q0​−p)N δM​(p)dp(2)
其中，*为卷积，此处为平滑滤波。这样就完成了从点云数据法向量到梯度空间的求解。
（3）梯度空间到向量场
  由于物体表面点的离散性， N ⃗ \vec{N} N 对于表面每个点 q q q未必都是已知的，即 N ⃗ δ M ( p ) \vec{N}_{\delta M}(p) N δM​(p)的分布是未知的，可以利用分段近似解决这个问题，通过观察 P = ( p i , n i ) P=(p_i,n_i) P=(pi​,ni​)来近似。
  初始离散样本点集记为 S S S， s s s为 S S S中的一个点 ( s ∈ S ) (s\in S) (s∈S)， s s s包含位置信息 ( s . p ) (s.p) (s.p)和法向量信息 ( s . N ⃗ ) (s.\vec{N}) (s.N )。将 δ M \delta M δM按照空间划分成不同表面区域 δ s \delta s δs，并且 s ∈ S s\in S s∈S， δ s ⊂ δ M \delta s\subset\delta M δs⊂δM。式(2)可以转化为积分求和，其中每个小的积分可以近似为常函数，可以用 s . p s.p s.p对应的函数和 δ s \delta s δs的面积的积分代替，如下式：
Δ ( χ M ∗ F ˉ ) ( q 0 ) = ∑ s ∈ S ∫ δ s F ˉ N ⃗ δ M ( p ) d p ≈ ∑ s ∈ S ∣ δ s ∣ F ˉ ( q − s . p ) s . N ⃗ = V ⃗ ( q ) (3) \Delta(\chi_M*\bar{F})(q_0)=\sum_{s\in S}\int_{\delta s}\bar{F}\vec{N}_{\delta M}(p)dp\approx \sum_{s\in S}|\delta s|\bar{F}(q-s.p)s.\vec{N}=\vec{V}(q) \tag{3} Δ(χM​∗Fˉ)(q0​)=s∈S∑​∫δs​FˉN δM​(p)dp≈s∈S∑​∣δs∣Fˉ(q−s.p)s.N =V (q)(3)
  假设样本点是均匀分布的，那么 ∣ δ s ∣ |\delta s| ∣δs∣即为常数可以省略，通过离散近似，由式(3) 即可得到向量空间 V ⃗ \vec{V} V 。
（4）转化为泊松方程
  向量空间 V ⃗ \vec{V} V 和指数函数 χ M \chi_M χM​满足下式，即为最终需要求解的问题：
Δ χ ⃗ = V ⃗ (4) \Delta \vec{\chi}=\vec{V}\tag{4} Δχ ​=V (4)
其中如果直接求解 χ ⃗ \vec{\chi} χ ​需要求解积分，向量空间 V ⃗ \vec{V} V 不一定是无旋场，通常意义上不能积分，将式(4)两边进行求导运算，得到式(5)：
Δ χ ⃗ = Δ ⋅ V ⃗ = Δ ⋅ Δ χ (5) \Delta \vec{\chi}=\Delta\cdot\vec{V}=\Delta\cdot\Delta {\chi}\tag{5} Δχ ​=Δ⋅V =Δ⋅Δχ(5)
  其中， Δ \Delta Δ为拉普拉斯算子， Δ ⋅ \Delta\cdot Δ⋅为散度算子，上式为泊松方程， χ ⃗ \vec{\chi} χ ​是要求解的函数，上式意思是梯度的散度等于向量场的散度。方程的解可以用拉普拉斯方程基本解与函数卷积求出，即可找到指示函数。

3、泊松算法流程

  泊松重建的输入是带有法向量的点云数据，在上一章节中已经完成了对点云数据法向量的求解，算法输出的是三角网格模型，其算法流程如下图所示：

1. 构建八叉树 g g g，存储点云数据，八叉树节点深度记为D，每一个节点 o ∈ g o∈g o∈g;
2. 设置函数空间 F F F为: F ( x , y , z ) = ( B ( x ) B ( y ) B ( z ) ) ∗ n F(x, y,z)=(B(x)B(y)B(z))^{*n} F(x,y,z)=(B(x)B(y)B(z))∗n，其中 ∗ n *n ∗n表示 n n n次卷积，所有的节点 o o o均有对应的空间函数 F F F。