0 引言

近年，在逆向工程、地质地形建模、智慧城市、生物医学等领域，点云的曲面重构技术得到了大量研究和广泛应用^[1]。点云曲面重构的本质是实现数据点模型到曲面模型的转变。隐式曲面重构因能够较好地重建出形状复杂的点云模型的表面，使得许多学者进行了大量研究。

文献[2]提出的径向基函数曲面重构方法重构的曲面细节特征较好，但在重构数据量大的点云时，将迅速增大计算量，且降低曲面重构效果，也存在重构曲面不够光滑的问题。文献[3]提出的基于元球造型技术的隐式曲面重建算法能很好地逼近没有尖锐特征的物体，但对非封闭模型会出现变形。文献[4]提出的基于椭球约束的隐式曲面重构方法对小规模封闭模型点云效果较好，但对于大规模散乱点云，其效率低下且有突出冗余。文献[5]提出的保特征的隐式曲面重构方法先对点云数据建立八叉树拓扑结构，再进行局部二次曲面求解，最后求解全局未知参数，对小规模的散乱点云通过调节采样点的邻近点数量能得到较优的重构效果，但在未知量的求取过程中，人为参与过多，求解繁琐且效率不高。文献[6]通过对原始点云进行八叉树划分，建立粗、细层数据，再进行径向基隐式曲面重构，对非封闭模型可能存在失真的情况，对闭合点云数据质量较好，但设定参数是通过多次实验人为选取，不能达到智能计算。

基于以上分析，本文提出一种基于隐式函数的大规模散乱点云自适应重构方法，首先利用自适应八叉树提供与模型密度相关的分割区域点云数据，以分解处理含数万个点的点云；然后在各子区域建立基于径向基函数的隐式元球模型，以保证局部曲面的光滑性，利用自适应差分进化算法智能求解元球模型隐式函数；最后利用改进的对数指数加权拼接算法对局部曲面进行光滑拼接，以生成一个高质的整体曲面模型。

1 散乱点云的分割

为了在微机上实现数据量庞大的散乱点云数据的曲面重构，利用分而自治的思想^[7]，建立点云模型的三维空间八叉树结构。本文是以采样点数据为输入来求取拟合曲面，以递归深度或边长小于设定阈值为分割终结条件的传统八叉树分割法将增加计算量和降低算法效率。因此本文采用以节点包含的点的数量为划分终结条件的自适应八叉树，详细步骤见文献^[8]。

2 点云的隐式曲面重构

2.1 径向基函数隐式曲面表示

本文由于是将大规模的散乱点云先分割再进行曲面重构的，因此采用一种紧支撑径向基隐式函数来表示重构曲面，即metaball模型函数^[9-10]，直接对采样点进行曲面拟合，无需点的法向量等信息。其一般形式为：

2.2 基于差分进化算法的隐式曲面求解

差分进化(Differential Evolution，DE)算法是模仿自然界生物进化发展规律形成的一种随机启发式搜索和群体智能优化方法，借鉴了“优胜劣汰、适者生存”的原则。本文将大规模的散乱点云进行分割后，在分割的子区域建立隐式曲面函数，再运用差分进化算法自适应求解metaball中心C={c_k(c_kx，c_ky，c_kz)|k=1，2，…，m}、metaball半径ek和形状参数?姿k，最后得到最佳逼近的隐式曲面函数f(x)。首先确定目标函数和适应度函数，并进行种群的初始化；然后根据差分进化算法的变异、交叉、选择操作不断迭代；最后找出最优的metaball中心、metaball半径和形状参数。

2.2.1 目标函数的建立

点云的曲面重构是为了尽可能拟合原始点云数据的最佳逼近曲面，所以本文将平均残差平方和(Residual Mean Squares，RMS)最小作为差分进化算法的目标，采用的目标函数为：

式中，p_i∈P是原始点云数据中的点，n为点云中点的数量。

2.2.2 适应度函数

在差分进化算法中，本文需要制定一个衡量解的优劣并增加解的辨识度的标准，即建立适应度函数。本文的目标函数是平均残差平方和最小，RMS值越小的个体，其适应度值f_fit应越大，说明个体越优良，被选择的概率就越大。差分进化算法是对适应度函数值的最大化进行寻优，而本文metaball模型参数的优化选择则是最小化寻优问题，因此需要将适应度函数作如下转换：

2.2.3 种群实数编码和初始化

本文需利用差分进化算法智能优化求解使目标函数最小的metaball中心、半径和形状参数(共5个变量)，可描述为(c_kx，c_ky，c_kz，e_k，λ_k)。

(1)编码

差分进化算法采用的是实数编码，如果编码范围(搜索空间)过大，DE收敛慢或早熟(收敛至局部最优)，或退化为随机搜索。编码范围越小，DE收敛速度越快，配准效率越高。因此，确定一个有限且尽可能小的编码范围是必要的。本文需求解的变量c_kx∈[x_min，x_max]，c_ky∈[y_min，y_max]，c_kz∈[z_min，z_max]，e_k∈(0，d]，λ_k∈(0，100]，其中x_min，x_max、y_min，y_max、z_min，z_max分别为点云P在X、Y、Z三个坐标方向上的最小值和最大值，d为构造的包含点云P的立方体包围盒的对角线长度值。

(2)初始化

在搜索空间中随机产生I个个体，每个个体由J维向量组成。

式中，J=5；T_MAX、T_MIN分别为第j个变量在搜索空间的最大值、最小值；r为0～1之间的随机数。

2.2.4 差分进化操作

(1)变异

在第g代从种群中随机选择3个个体T_p1、T_p2和T_p3，且i≠p₁≠p₂≠p₃，则变异操作为：

式中，CF为变异因子，T_{p2 j(g})-T_{p3 j(g)}为差异化变量；p₁、p₂和p₃为随机整数，表示个体在种群中的序号，为加快收敛速度个体，p₁可选择为当代种群的最好个体。

针对传统差分进化算法在整个求解过程中变异因子CF始终不变可能导致算法效率下降与过早收敛的问题，本文采用了自适应的变异因子公式^[12]。

(2)交叉

交叉操作是为了增加种群的多样性，具体操作为：

式中，r为0～1之间的随机数，CR为交叉因子。

针对传统差分进化算法在整个求解过程中交叉因子CR始终不变可能导致过早收敛和收敛变慢的问题，本文采用了自适应的交叉因子公式^[12]。

(3)选择

选择操作是为了确定进入下一代种群的个体，具体为：

式中，f_fit(v_i)为个体v_i的适应度值，f_fit(T_i)为个体T_i的适应度值。

3 隐式曲面光滑拼接

本文选用文献[13]提出的对数指数加权拼接算法并加以改进，对局部隐式曲面进行光滑拼接，以得到一张原始点云模型所描述的完整曲面。该方法是对各分割区域两两相邻拼接，通过不断递归，实现所有局部曲面的光滑拼接，最终得到完整的曲面模型。拼接函数为：

式中，f₁和f₂分别为需拼接的两相邻分割区域的隐式曲面函数，α为拼接控制参数。α的取值关系到拼接的光滑程度，在文献[13]中给出的是0.1～10之间的取值范围，需根据多次实验的效果来人为确定α的取值。在此基础上，本文利用差分进化算法来自适应地得到控制参数α的最优值。

3.1 建立目标函数和适应度函数

为保证原始点云尽可能在拼接后的曲面上，建立的目标函数为：

式中， p_i为两相邻区域的原始点云中的点，n为两相邻区域的原始点云数量。

则相应的适应度函数为：

3.2 算法步骤

本文提出的自适应隐式曲面光滑拼接算法进化操作与文中2.2节类似，则算法步骤为：

(1)在变量域[0.1，10]初始化随机种群M；

(2)依次进行变异、交叉和选择操作，直到满足进化终止条件，得到最优α值的拼接函数；

(3)在分割区域递归进行基于自适应差分进化算法的拼接函数求解，并进行隐式曲面拼接操作；

(4)输出完整曲面模型，算法结束。

4 实验结果及分析

本文提出了一种对大规模散乱点云数据实现快速、高质地曲面重构的方法，所提出的算法采用C++和MATLAB语言编写，在主频3.20 GHz、内存8 GB的Intel Core i5-6500的计算机上实现。隐式曲面绘制是利用Marching Cube算法^[14]提取零等值面。实验中所有原始点云模型均来自斯坦福大学计算机图形学实验室。

4.1 不同类型点云的重构效果

为验证本文算法的有效性，将其应用于2种不同规模点云进行重构，以体现本文算法在不同规模点云模型的鲁棒性。如图1所示，图1(a)为bunny点云，该模型规模较小；图1(b)为bunny曲面模型，可见本文算法对规模较小的模型能较好地重构出曲面，表面光滑且细节特征较好；图1(c)为dragon点云，该模型规模较大且特征较复杂；图1(d)为重构出的dragon曲面模型，可以看出重构曲面细节特征还原度好，表面也非常光滑。

表1给出了本文算法处理以上2种模型的统计信息，包括原始点云的点数、重构时间和拟合误差。将每一个原始点坐标代入拼接函数，进而计算出所有点的残差平方和，选取全局残差平方和的最大值为最大拟合误差，计算出所有点的残差平方和的平均值为平均拟合误差。从表1可以得出，本文算法对不同规模的点云都具有很好的适应性，重构效果好，耗时也在可接受范围内。

4.2 不同重构算法重构结果对比

为验证本文算法的有效性，将本文算法与文献[3]、文献[6]的算法进行对比分析。在模型的选取上为了体现算法的适应性，选择两种不同的模型：一种为封闭的点云模型horse；另一种为未封闭的点云模型hand。两类模型的重构效果图如图2、图3所示。

图2(a)为horse原始点云；图2(b)为采用文献[3]算法重构出的曲面，可见表面光滑但细节特征有所丢失；图2(c)为采用文献[6]算法重构出的曲面，可见细节特征有所体现，但表面不够光滑；图2(d)为采用本文算法重构出的曲面，可见表面光滑且细节特征较明显。从表2对horse模型重构的统计信息也可得出本文算法的重构效果最好，但时间上因为需要对原始点云先分割再拼接，所以不够理想。

图3(a)为hand原始点云；图3(b)重构出的曲面较明显的问题是在手腕处因为没有点数据控制形状所以严重走样；图3(c)重构出的曲面因为在重构过程中产生了额外的零水平集所以部分失真；图3(d)采用本文算法重构出的曲面表面光滑，在未封闭的手腕处无冗余突出，效果最好。从表2对hand模型重构的统计信息也可得出本文算法的重构曲面平均拟合误差最小，虽然用时不是最少的，但算法性能比是最高的。

5 结论

本文提出了一种自适应重构大规模散乱点云的方法，采用自适应八叉树分割出局部点云，以自适应差分进化算法智能求解局部点云的隐式曲面函数，采用改进的拼接算法以得到完整的曲面模型。将本文方法与文献[3]、文献[6]方法的重构效果进行了对比，结果显示，采用本文方法重构出的曲面表面光滑，细节特征清晰准确，在未封闭区域无突出冗余。虽然本文方法对大规模点云的重构是非常有效的，但是为保证较好的细节特征，是以增大分割量为代价的，导致了重构时间的增加。因此，如何平衡好重构效果和耗时的关系是下一步的研究内容。

参考文献

[1] 莫建文，庞建铿，袁华.基于VTK的三维点云曲面重建研究[J].电子技术应用，2015，41(4)：156-158.

[2] 符艳青.基于改进的径向基函数网络的3D隐式曲面重构算法研究[D].杭州：中国计量学院，2014.

[3] 刘圣军，韩旭里，金小刚.空间采样点的隐式曲面表示与优化[J].中国图象图形学报，2011，16(3)：480-487.

[4] 韩燮，武敬民，韩慧妍，等.基于椭球约束的径向基函数隐式曲面重建[J].图学学报，2014，35(4)：504-510.

[5] 田建磊.一种保特征的隐式曲面算法[J].计算机工程与应用，2011，47(1)：208-210.

[6] 张娟，侯进，吴婷婷，等.三维散乱点云模型的快速曲面重建算法[J].计算机辅助设计与图形学学报，2018，30(2)：235-243.

[7] 刘恩江，宋云胜，梁吉业.基于数据划分的核岭回归加速算法[J].中国科学技术大学学报，2018，48(4)：284-289.

[8] 陈龙.散乱点云特征提取和聚类精简技术研究[D].绵阳：西南科技大学，2017.

[9] BLINN J.A generalization of algebraic surface drawing[C].Conference on Computer Graphics & Interactive Techniques.ACM，1982.

[10] NISHIMURA H，HIRAI M，KAWAI T，et al.Object modeling by distribution function and a method of image generation[J].The Transactions of the Institute of Electronics and Communication Engineers of Japan，1985，J68-D(4)：718-825.

[11] MURAKAMI S，ICHIHARA H.On a 3D display method by metaball technique[J].Journal of the Electronics Communication，1987，70(8)：1607-1615.

[12] 杨从锐，钱谦，王锋，等.改进的自适应遗传算法在函数优化中的应用[J].计算机应用研究，2018，35(4)：1042-1045.

[13] 武敬民.三维点云处理及隐式曲面三维重构技术的研究与实现[D].太原：中北大学，2014.

[14] LORENSEN W E，CLINE H E.Marching cubes：a high resolution 3D surface construction algorithm[J].ACM Siggraph Computer Graphics，1987，21(4)：163-169.

作者信息:

江 盟1，2，蔡 勇1，2，张建生1，2

(1.西南科技大学 制造科学与工程学院，四川 绵阳621010；

2.制造过程测试技术省部共建教育部重点实验室，四川 绵阳621010)