随着3维激光扫描技术的快速发展，在逆向工程领域通过3维扫描仪获取的模型点云数据精度越来越高，但随之而来的是点云数据量极其庞大，在进行曲面重建、光顺等点云数据处理时大量消耗计算机资源和时间，因此，点云精简是点云数据处理中一个重要的研究课题。

在散乱点云数据精简方面，国内外学者做了大量研究。Sun等人^[1]提出了包围盒法进行点云精简，其原理是首先对散乱点云建立最小包围盒，然后将包围盒等分为多个小栅格，最后针对每个小栅格寻找距离栅格中心最近的点代替立方体中的所有点。包围盒法虽然可以达到均匀的效果但精简后特征丢失严重。Martin等人^[2]提出了均匀网格法，该方法同样在最小包围盒的基础上建立均匀栅格，然后在每个栅格中计算数据点在$Z $坐标方向上到栅格的距离并按大小排列，最后利用图像处理中的中值滤波原理按照距离取位于中间值的数据点代表该栅格中的所有点，该方法未考虑特征点，依然存在模型特征大量丢失的问题。Lee等人^[3]在均匀网格的基础上提出了非均匀网格法，通过计算每个网格中数据点的法矢偏差，大于阈值的网格则继续划分直到法矢偏差小于给定阈值，非均匀网格法能够保留部分模型特征。Kim等人^[4]通过栅格法建立点云$k $邻域，然后计算数据点的曲率，根据曲率精简数据点。Han等人^[5]提出一种能够保留边缘数据点的点云简化算法，通过八叉树建立$k $邻域，以法向量为依据检测并保留边缘特征点，非边缘点则根据其到邻域切平面的距离平均值为度量进行点云精简，该算法保留的边缘点大部分为曲面尖锐点，边界数据点的保留效果并不理想。史宝全等人^[6]提出了基于聚类的点云简化方法，首先对点云进行栅格划分，每个栅格中选取距离栅格中心最近的数据点作为初始的聚类中心，依据法向量的变化进行迭代细分，最后对所有类进行均值漂移处理获得精简点云。聚类精简法精简后的点云分布均匀，可以保留部分模型特征，但是由于使用栅格法提供的初始聚类中心将导致迭代次数增加。

基于以上分析，提出一种自适应K-means聚类点云精简算法，利用自适应八叉树提供与模型密度相关的初始化聚类中心以加快聚类收敛速度，在较平坦区域中聚类精简可达到点云分布均匀无空洞的效果。采用多判别参数法以识别模型的曲面尖锐点及边界特征点，并将曲率差大于阈值的聚类进行迭代细分以保留模型细节特征，可降低点云精简时的误差。

该算法首先运用多判别参数混合的点云特征提取方法^[7]检测并保留散乱点云中的特征点，包括曲面突变点及非封闭点云的边界点，以最大限度降低精简后的失真现象；然后针对点云建立自适应八叉树为K-means聚类提供初始化聚类中心；最后将聚类结果中的特征点剔除并更新聚类信息，将聚类细分以保留细节特征。

八叉树是一种用于表示3维空间的树结构，每个内部节点拥有8个子节点，分割结束条件一般为递归深度，而自适应八叉树的的分割结束条件则为节点中数据点的个数。自适应八叉树应用于散乱点云时其分割的结束条件可以是节点中所包含数据点的个数、点法向夹角或曲率的标准差等，因此当分割结束条件为节点中点云数据点的个数时其叶子节点的分布较为均匀，而用于非均匀点云模型时在密度较高的区域分布密集，而在点云密度较低的区域分布稀疏，因此当自适应八叉树应用于点云空间分割时其叶子节点的分布具有点云密度相关性^[8]。

K-means聚类是数据挖掘中的经典算法之一，属于重要的无监督学习方法，广泛应用于机器智能、模式识别和图形图像等领域^[9]。该算法以欧式距离为相关性的度量，将数据点划分为$K $个簇，每个簇中的数据点具有相似性，因此应用于散乱点云精简时可将具有相似性的数据点聚类，然后依照精简策略进行精简可达到较好的精简效果。K-means聚类在选取初始化聚类中心后不断迭代更新聚类中心直至评价函数收敛，具有速度快、可用于大型数据等优点，但是聚类结果的好坏依赖于初始化聚类中心的选择及$ K$值大小。

定义输入的散乱点云数据集为$\boldsymbol{P} = \left\{ {{p_i}\left( {{x_i}, {y_i}, {z_i}} \right)|i = 1, 2, \cdots, N} \right\} $，具体算法流程如下：

1) 点云数据中特征点的检测。计算数据点曲率${C_i} $、点法向与邻域点法向夹角的平均值${\theta _i} $、点到邻域中心的距离${D_{1i}} $、点到邻域点的平均距离${D_{2i}} $这4个参数定义特征阈值和特征判别参数特征判别参数大于阈值的点即为特征点。

2) 自适应K-means聚类初始化。针对散乱点云数据建立自适应八叉树，其分割结束条件设定为节点中包含的数据点个数${O_n} $，分割结束后记录八叉树中非空叶子节点的数量和距离叶子节点盒子中心最近的数据点分别作为K-means聚类的$K $值和初始化聚类中心，然后迭代更新聚类直至准则函数的变化值小于容差$\varepsilon $。

3) 聚类细分。遍历聚类将其中的特征点剔除，更新剔除特征点后的聚类中心、数据点和评价函数，为了保留点云模型的细节特征，计算每个聚类中数据点之间的最大曲率差，将最大曲率差大于设定阈值的聚类进行迭代细分，聚类细分后再次更新聚类信息，最后保留距离聚类中心最近的数据点。

本文提出的自适应K-means聚类精简方法可以处理点云分布均匀及非均匀的数据点集，且适用于封闭及片状的点云模型。在使用特征检测方法识别并保护点云特征点的前提下进行精简，进行点云精简时将含有细小特征的聚类继续迭代细分以保留点云的细节特征。本文精简方法分为特征点检测、聚类初始化和聚类细分3步进行。

为了尽量减弱点云精简带来的模型特征和边缘边界等区域的收缩、失真现象，本文在点云精简之前首先进行模型特征点和边界点的检测并保护，防止在后续的点云精简操作中误删特征点，点云模型的特征提取将在后续的点云精简中极大地降低精简误差。

采用文献[7]中多参数混合的散乱点云特征检测方法对模型的特征点进行识别和保护，当数据点经检测为特征点时令其bool运算标志位feature point = true，在点云精简中此标志位为true的点予以保留。具体检测方法如下：

针对每个数据点及其$k $邻域计算点到邻域中心的距离${D_{1i}} $和点到邻域点距离的平均值${D_{2i}} $，使用PCA (principal component analysis)方法计算法向夹角平均值${\theta _i} $和曲率${C_i} $，根据以上4个参数定义特征阈值和特征判别参数特征判别参数大于阈值的点即为特征点。定义特征判别参数为

$ {t_i} = \frac{{\alpha {C_i} + \beta {\theta _i} + \gamma {D_{1i}}}}{{{D_{2i}}}} $

(1)

式中，α、β和γ分别为曲率、法矢夹角和点到邻域重心距离控制系数，定义判别阈值为

$ {T_i} = \frac{{\eta \sum\limits_{i = 1}^N {{w_i}} }}{N} $

(2)

式中，${w_i} = \frac{{{C_i} + {\theta _i} + {D_{1i}}}}{{{D_{2i}}}} $，$\eta $为特征点数量控制系数，可根据精简率控制特征点数量，$N $为点云数据点个数，${t_i} \ge {T_i} $时即可判别数据点${p_i} $为特征点。

如图 1所示为将特征提取算法应用于不同模型的提取效果，其中wilhelm为点云分布相对均匀的模型，由提取效果可见模型面部特征提取准确，边缘清晰；而nokia为非均匀的模型，具有强弱特征、连续变化曲线以及内外边缘，特征提取难度较大，由提取结果可见模型特征提取清晰准确。

K-means聚类结果的好坏依赖于初始化聚类中心以及$K $值的选择，而传统K-means聚类中$K $值为操作人员凭借经验指定，然后随机选出$K $个初始化聚类中心，而不同的初始化聚类中心将产生不同的聚类结果，因此造成了聚类结果不稳定，算法多次运行产生聚类结果的评价函数值并不统一^[10]。为了获得优良的聚类结果，Hansen等人^[11]提出了一种多次重启动K-means聚类算法选取聚类中心，但此方法耗时较多。K-means+ +方法^[12]依据每个聚类中心距离最大的原则选择初始化聚类中心，当聚类数目即$K $值不大时可以取得较好的结果，但是当$K $值偏大时算法在选择初始化聚类中心时将消耗大量时间。

由于散乱点云数据量庞大且模型复杂，将K-means聚类用于点云精简时就需要精简快速结果准确，因此本文运用自适应八叉树为K-means聚类提供初始化聚类中心，保证初始化聚类中心的分布相对均匀，用于非均匀的点云数据时初始化聚类中心能够与密度的变化相关，以减少聚类的迭代次数同时有利于聚集相近特征的数据点，达到精简快速结果准确的目的。

如图 2所示为将自适应八叉树应用于数据点为34 834的bunny点云模型给K-means聚类提供不同的$K $值及对应初始化聚类中心结果，可见不同$K $值的初始化聚类中心分布较为均匀。其中$K $值由自适应八叉树提供，通过改变八叉树的分割结束条件${O_n} $获得不同$K $值，进而取得不同比率的精简结果。

为了验证本文初始化聚类中心选择方法的有效性，如表 1所示在容差$\varepsilon $不变的前提下将本文方法与传统K-means法应用于bunny模型进行对比。由于传统K-means法的初始化具有随机性，重复运行可产生不同结果，因此将其运行10次，记录迭代的最高和最低次数，并计算平均迭代次数、平均评价函数和聚类运行的平均时间，而本文算法不具有随机性，因此迭代次数等数据不变。由表 1数据对比可知K-means聚类采用本文方法选取的初始化聚类中心时其迭代次数及评价函数值均小于传统的方法，因此通过自适应八叉树为K-means聚类提供初始化聚类中心的方法是可行的。

一般情况下，点云精简后的失真现象多发生在特征区域。由于本文已将点云模型中的强特征点进行检测并保护，因此可以极大的降低点云精简误差。当聚类处于模型中的平坦区域时可以将距离中心最近的数据点代替整个聚类，但是在曲面变化不大的区域仍然有较多弱特征存在，若采用同样的精简策略将会丢失过多细小特征。文献[13]中通过计算每个聚类中数据点之间的最大法向量偏差值与用户设定的阈值进行对比，大于阈值的聚类则继续分割为两个子聚类，再将新生成的聚类判断是否细分，直至满足最大法向量偏差值小于阈值或聚类中只剩下一个数据点为止。借鉴文献[13]中的方法，考虑到在特征区域聚类的细分将耗费大量时间且本文已将强特征点识别并保护，而且法向量计算较为复杂，因此本文的聚类细分主要考虑保留细小特征点，具体方法为：遍历所有聚类，将包含特征点的聚类选出并剔除特征点后更新中心，然后针对每个聚类采用PCA方法计算其包含数据点之间的最大曲率差，与设定的阈值${T_n} $进行比较，大于阈值的聚类则继续迭代细分为两个子聚类，重复细分直至满足中止条件即最大曲率差小于阈值或只剩下一个数据点为止。

如图 3所示在检测相同数量的强特征点以及聚类参数不变的前提下，对bunny模型进行自适应K-means聚类精简中采用细分后的精简结果与未细分的对比情况。由图 3可以看出，采用聚类细分后的精简结果比未细分的多保留了860个细节特征点，大都分布与强特征区域附近，由此可见，采用最大曲率差进行聚类细分的方法是可行的，而细节特征点的数量可通过改变阈值${T_n} $获得。

所提出的自适应K-means聚类的点云精简算法采用C++语言编写，使用OpenGL库函数进行显示，运行平台配置为Intel Core i3-2330M 2.2 GHz，内存4.0 GB。

本文提出的散乱点云精简算法需设定7个参数，分别为$k、\alpha 、\beta 、\gamma 、\eta 、{O_n}、{T_n} $，其中前5个参数主要用于点云模型特征检测，关于参数的详细介绍参见文献[7]。本文中$\eta $通常设置为1.0，可根据精简率选取，dragon及wilhelm模型参数为$k = 8、\alpha = 10、\beta = 0.2、\gamma = 1.5 $；fandisk模型参数为$k = 4、\alpha = 20、\beta = 0.2、\gamma = 1.5 $；saddle模型参数为$k = 16、\alpha = 5、\beta = 0.2、\gamma = 0.5 $。${O_n} $值关系到K-means聚类初始化中的$K $值大小以及对应初始化聚类中心的分布，间接影响点云的精简率，${T_n} $则决定聚类细分时保留细节特征点的数量，dragon模型的${O_n} = 27、{T_n} = 0.008 $；wilhelm模型的${O_n} = 30、{T_n} = 0.008 $；fandisk模型的${O_n} = 18、{T_n} = 0.007 $；saddle模型的${O_n} = 22、{T_n} = 0.0004 $。

为了验证本文算法的可行性，将其应用于两种不同的模型进行精简，一种为封闭的dragon模型，该模型实际尺寸较小，特征复杂且数据量庞大；另一种为片状点云模型wilhelm，该模型尺寸较大，具有大量的边界信息。设定精简比例为1/5、1/10及1/15，并使用Geomagic 12.0计算平均误差，精简效果如图 4和图 5所示。dragon模型的点云数据点数量为437 645，当精简比例为1/5时正负方向上的平均误差${\Delta _{{\rm{avg}}}} $为0.19×10^-4、-0.24×10^-4，1/10时${\Delta _{{\rm{avg}}}} $为0.67×10^-4、-0.69×10^-4，1/15时${\Delta _{{\rm{avg}}}} $为0.56×10^-3、-0.47×10^-3。wilhelm模型的点云数据点数量为43 638，当精简比例为1/5时正负方向上的平均误差为${\Delta _{{\rm{avg}}}} $为0.007 9、-0.012，1/10时${\Delta _{{\rm{avg}}}} $为0.014、-0.019，1/15时${\Delta _{{\rm{avg}}}} $为0.019、-0.025。从两种不同的模型精简效果可见，精简后的点云在特征区域保留了大量的数据点，平坦区域数据点相对较少但分布均匀没有空洞现象发生，且片状点云模型的边界数据保留较好。

为了验证本文算法的有效性，将本文方法应用于点云模型进行精简，并于曲率精简法和栅格精简法进行对比。在模型的选取中为了体现算法的适应性，因此选择两种不同的模型：一种为封闭的点云模型fandisk，点云数据点数量为55 355，该模型包含直线、连续变化的曲线特征，且点云分布不均匀；另一种为片状的点云模型saddle，点云数据点数量为12 341，该模型曲面过渡平缓，具有大量的边界信息，点云精简中如果边界数据未能加以保护将发生较为严重的边界收缩现象。

图 6和图 7分别为fandisk和saddle模型采用1/5精简比例时采用栅格法、曲率法及本文算法的精简效果和误差对比，可以看出，栅格法精简效果整体较为均匀，但特征信息丢失严重导致精简误差较大，平均误差${\Delta _{{\rm{avg}}}} $分别为0.24×10^-3、－0.31×10^-2及0.057、－0.077；曲率法精简结果中特征区域数据点分布密集而平坦区域稀疏，因而产生大量的空洞，其精简平均误差${\Delta _{{\rm{avg}}}} $为0.44×10^-3、－0.53×10^-3和0.056、－0.110，误差值均小于栅格法；本文算法精简结果中模型特征清晰，平坦区域数据点分布均匀无空洞，细节特征处数据点分布较平坦区域密集，能够较好地保留细节特征，精简误差为${\Delta _{{\rm{avg}}}} $ = 0.29×10^-3、－0.41×10^-3和${\Delta _{{\rm{avg}}}} $ = 0.037、－0.094，均小于栅格法及曲率法。

在精简比例同为1/5的前提下，针对fandisk和saddle两个不同模型，将采用栅格法、曲率法及本文方法进行精简时的运行时间进行对比，如表 2所示为3种算法运行时间的对比情况，可知本文方法在运行时间上大于其他2种方法，主要原因在于采用聚类精简时需进行迭代更新聚类信息等待评价函数收敛，因此本文方法耗时较长。

由于曲率法及栅格法检测片状点云边界数据点的能力较弱，导致精简过程中边界信息大量丢失，精简后的模型边界收缩严重，而本文精简算法保留了片状点云的边界数据点，因此精简结果中边界收缩较小。由于图 6和图 7中的平均误差为geomagic软件计算得来，该误差仅反映精简后点云数据构成的区域与原始点云对应区域之间的偏差情况，因此该误差无法评估片状点云精简后因边界信息丢失而发生的边界收缩误差，为了准确地表达片状点云精简产生的边界收缩情况，引用点云配准中ICP(iterative closest point)算法的残余误差${E_{{\rm{data}}}} $^[14-15]对文中的边界收缩情况进行度量，其中${E_{{\rm{data}}}} $为

$ {E_{{\rm{data}}}} = \frac{1}{{N'}}\sum\limits_{i = 1}^{N'} {{{\left\| {{p_i}-{q_i}} \right\|}^2}} $

(3)

式中，${N'} $为离散后数据点个数，${{p_i}} $为saddle点云的原始边界数据点，${{q_i}} $为精简后点云边界数据点中与${{p_i}} $所对应最近的数据点。

计算两条边界之间的残余误差具体方法为：将图 7中4片点云的边界进行提取，然后分别将不同方法精简后点云的边界与原始点云边界合并，最后离散采样两条曲线的数据点计算其残余误差，为了更加清晰地看到边界的收缩变化情况，本文已将模型旋转了一定角度以获得较为明显的边界曲线对比图像。如图 8所示为saddle原始点云边界与3种精简方法精简后点云边界之间的残余误差情况。

根据图 8中3种方法精简后点云边界的收缩情况对比可知：使用曲率法进行点云精简后其边界收缩导致的残余误差最大，为${E_{{\rm{data}}}} $=4.835 22，原因在于曲率精简法在低曲率区域会保留较少的点，而当边界区域较为平坦时采用曲率法精简将会丢失大量边界信息；栅格法精简时虽然未考虑点云的曲率及边界信息，但是其数据点的采样相对均匀，因此使用栅格法进行点云精简后边界收缩的残余误差小于曲率法，为${E_{{\rm{data}}}} $=0.324 267；由于本文方法具有识别并保护片状点云边界特征点的能力，因此进行点云精简后边界收缩量很小，其残余误差${E_{{\rm{data}}}} $=0.030 805，小于栅格法和曲率法。

提出了一种自适应K-means聚类的散乱点云精简方法，以多判别参数混合方法检测模型特征点，采用自适应八叉树为K-means聚类提供初始化聚类中心和$K $值，在聚类结果中将特征点剔除并更新聚类信息，将更新后聚类中数据点之间的最大曲率差大于设定阈值的聚类进一步迭代细分以保留细节特征信息。将本文方法与栅格和曲率法精简的效果进行了对比，结果显示，采用本文方法精简的点云特征清晰准确，平坦及低曲率区域点云分布均匀无空洞，低曲率处点云密度稍高于平坦区域，应用于封闭曲面的点云数据时精简误差小于栅格和曲率法精简效果，而应用于片状点云精简时模型的边界信息保留较好，由边界收缩而产生的误差较小。

本文方法应用于封闭或片状的点云模型时均可得到较好的精简效果，但对于具有薄壁特征的点云模型时会出现特征点误判和聚类不准确的情况，原因在于建立点云拓扑关系及聚类时附近数据点寻找错误；另外由于本文采用聚类的方式进行点云精简操作，在面对百万数量的点云时，存在着时间效率较低的问题。因此下一步研究工作将会考虑改变建立点云拓扑关系的方式以适应具有薄壁特征的点云模型；同时在面对百万数量级别的点云时，可在聚类的迭代更新操作中将类中心点变化较小的簇采用类中心不变的策略以减少计算量，提高精简效率。