基于边界保留的k-means聚类点云精简算法研究

常俊飞，赵利民，王瀚斌

(1.辽宁工程技术大学 测绘与地理科学学院，辽宁 阜新 123000;2.广东省核工业地质局二九二大队，广东 河源 517001;3.中国电建集团北京勘测设计研究院有限公司, 北京 100024)

由于测量技术的不断发展，对物体表面的测量精度和效率也越来越高，测量得到的数据量非常大，存在着大量的冗余数据，增加了后续建模等工作的难度。因此如何提取点云数据中反映曲面特征的点，去除冗余数据，即对测量数据进行精简有助于提高建模效率和建模质量，是逆向工程中的一项关键技术。数据精简的最佳效果是使精简后的数据点云具有较少的数据量，同时又能保证不丢失物体表面的细节特征，且速度越快越好。已有研究人员和科学工作者提出了多种方法，但均存在不完善之处[1-12]。因此，本文针对传统的栅格法与曲率法对数据模型进行精简时很容易剔除特征点，具有较高的误判率，导致精简后的数据不能较好地突出点云数据的特征，使重构后的实体模型精度下降等问题，提出基于边界保留的k-means聚类算法对点云进行自适应精简。

1 K-means聚类算法的基本思想

1967年，MacQueen J提出了k-means聚类算法，用来处理数据聚类的问题[13]，该算法由于其算法简便，又较早提出，因此在科学和工业领域的应用极为广泛。该算法解决的是将含有n个数据点(实体)的集合划分为k个类簇Cj的问题(j=1，2，…，k)。算法首先随机选取k个数据点作为k个类簇的初始簇质心，集合中每个数据点被划分到与其距离最近的簇质心所在的类簇之中，形成k个聚类的初始分布。对分配完的每一个类簇计算新的簇质心，然后继续进行数据分配过程，这样迭代若干次后，若簇质心不再发生变化，则说明数据对象全部分配到自己所在的类簇中，聚类准则函数收敛，否则继续进行迭代过程，直至收敛。这里的聚类准则函数一般采用聚类误差平方和准则函数。该算法的一个特点即是在每一次的迭代过程中都要对全体数据点的分配进行调整，然后重新计算簇质心，进入下一次的迭代过程，若在某一次迭代过程中，所有数据点的位置没有变化，相应的簇质心也没有变化，此时标志着聚类准则函数已经收敛，算法结束。然而，k均值聚类算法对初始质心的依赖性较强，不同集群的初始化会产生不同的结果，为了避免初始化质心带来聚类不稳定的问题，使用k-d树来进行质心的初始化，并且可以保证质心均匀分布。

2 算法的基本流程

目前，K-means聚类多应用于数据挖掘、模式识别、决策支持、机器学习及图像分割等领域。2016年张帆等利用K-means聚类算法进行了DEM的简化，效果较好。因此，本文提出基于边界保留的k-means聚类算法对点云进行精简，算法包括3个步骤：初始化、点云模型边界提取及划分和簇细分。

2.1 初始化

1)在三维空间中，使用输入的点数N建立一个k-d树；

2)fori=1 toN；

3)if不是标定点，那么以固定半径对的邻域进行搜索；

4)标记固定半径的邻域；

5)end if；

6)end for；

7)选择非标记点作为初始聚类质心。

图1为k均值聚类的一个例子。

图1 初始化示意图

2.2 点云模型边界提取和划分

三维点云不仅包含物体的平面信息，还包含物体的高程信息，但是根据人们的习惯，X，Y组成的二维平面携带的细节信息相对较多，因此为了在保留点云边界的同时不影响算法效率，仅获取X-Y两个方向的边界，Z轴信息不会缺失[14]。所以只需将模型的X，Y两个方向的边界点云提取即可，具体步骤如下：

1)根据所有点云数据的X坐标大小进行升序排列，排序完成后，将点云数据按照从小到大的顺序进行分组，并将每组的个数阈值设为T(T是根据点云的疏密情况来选择不同的值)；

2)对每组中的点云数据进行Y坐标值的比较，记录下最大值和最小值点，并保留；

3)同理，根据所有点云数据的Y坐标大小进行升序排列，排序完成后，将点云数据按照从小到大的顺序进行分组，并将每组的个数阈值设为T;

4)对每组中的点云数据进行X坐标值的比较，记录下最大值和最小值点，并保留；以此操作，可以提取模型边界。

对边界点提取后，要判定该边界点所在的簇是否远离了簇质心，如若远离，需要对该簇进行分解，关于距离 “远近”的判定，文献[15]给出相应的判定准则，具体如下：

1)计算该质心与邻近质心的距离，并求其均值，记为DC；

2)计算边界点所在簇的所有点的平均距离，最大值记为MaxDM；

3)如果MaxDM大于DC，边界簇的质心远离边界；

4)该边界簇将被细分为两个新的子簇，一个质心位于原始的质心点，另一个位于簇中所有元素平均距离最大的地方；

5)使用k均值聚类算法重新对点云进行聚类，直至满足要求。

2.3 簇细分

一般来说，在低曲率区域，簇成员在彼此的空间域和功能域是非常相似的，因此簇质心可以代表整个簇。而在高曲率区域，簇成员可能存在更细致的特征而在彼此的空间域和功能域是不相似的。如果用簇质心来代替整个簇，那么有些特征将会消失。为了准确，初始簇被递归分解为小的子簇直到成员在彼此的空间域和功能域是相似的。Pauly 等引入层次聚类方法，采用从上到下的方式把点云分为小的子集。如果簇单元的大小超过用户指定的大小或者变化阈值的上限，那么它将会被分解，然后，分解过程将从原始的输入数据开始，很明显点云作为一个大的集群将会消耗很多时间[5]。Lee 等采用基于八叉树的空间分解方法，把三维网格立方体递归划分为8个叉，并把该点的法向量的标准偏差作为细分的标准。由于每一次每个立方体分为8个叉，所以将会有很多点留在高曲率区域[4]。在本节中，应用点的曲率偏差来评价特征区域中的相似性。其优点是不仅可以确定簇成员是否相似，也可以找到存在偏差的位置。具体步骤如下：

1)对簇中每个点进行估计曲率计算，分别记为ki，并将最大曲率值和最小曲率值记为kmax和kmin；

2)设置曲率偏差阈值Kth，若簇中kmax-kmin

3)若簇中kmax-kmin>Kth，那么说明簇中的点处在曲率变化比较大的地方，需要对该簇进行分解为两个新的子簇，其中曲率最大值和曲率最小值的点分别为新的簇质心；

4)使用标准k均值聚类步骤把簇中的其他成员分配为两个新的质心，然后生成两个子簇；

5)重复以上步骤，直到新生成的簇满足终止条件。终止条件是当法向量偏差的最大值小于给定的限差Kth，或者簇中只有一个点。

通过以上算法可以得出，低曲率区域的点云由于曲率变化小，可以由簇质心代替。高曲率区域的点云曲率差较大，会不断分解为多个簇，特征不会消失。

2.4 点云精简误差评定

为了评定精简后点云的准确性，计算原始点集S和简化后点集S′间的最大误差和平均误差。

(1)

(2)

3 实验与分析

为了验证本文算法的优越性，分别使用栅格法、曲率法和本文提出的算法对叶片模型、兔子模型、Dragon模型和Horse模型进行精简(所使用模型已经进行去噪处理)。

叶片模型的精简结果如图2所示，3种方法基本上都能保持模型的基本形状。图2(a)为原始点云数据，点数为113 432个。其中图2(b)使用的是栅格法，该方法精简后点数为68 592个，由于网格的大小一定，针对性不强，某些高曲率区域精简点数较多，特征不明显，精简效果不好。图2(c)使用的是曲率法，精简后点云数为68 614个，该方法虽然突出了模型曲率较高的地方，但是在曲率较高的地方保留的点太多，而在曲率较低的地方保留的点数又太少，模型特征消失，达不到重构目的，而且某些边缘信息也已丢失，精简效果不好。图2(d)使用本文提出的新方法k均值聚类精简算法，精简后点数为68 579个，该方法在低曲率区域保留了均匀分布的点，而在高曲率区域则保留了必要密度的较多的点，而且边缘特征也得到保留，效果比栅格法和曲率法好。

图3为兔子模型精简示意图。图3(a)表示的是原始点云数据，共有33 791个点。图3(b)表示的是使用栅格法精简后点云模型，点云个数为16 966个。由图可知，虽然该方法达到了精简的目的，但它只是根据距离进行精简，并没有考虑模型本身的曲率及特征，精简效果不好。图3(c)表示使用曲率法精简后的点云模型，点云个数为16 869个。由图可知，曲率法虽考虑了模型本身的曲率高低，但该方法过于突出曲率，致使高曲率区域保留的点太多以致冗杂，低曲率区域的点太少而致某些特征模糊或者消失，精简效果一般。图3(d)使用的是本文提出的算法， 精简后点数为16 912个。由图可知，在高曲率区域，相对于曲率法而言，本文方法在保留曲率特征的情况下保留点数较少，在低曲率区域保留相对均匀的点来突出模型的特征，并且保留了某些边缘特征(如兔子后肢的下面部分)。

图2 叶片模型精简图

图4为Dragon模型的点云精简示意图。其中图4(a)为原始点云数据，点数为29 959个，图4(b)使用栅格法，该方法精简后点数为18 012个，由于网格的大小一定，针对性不强，在曲率突变处精简效果不好，如龙的触角和尾巴等处，特征已经消失，重构精度低。图4(c)使用的是曲率法，精简后点云数为17 975个，该方法虽然突出考虑了模型的曲率，但是在曲率较高的地方保留的点太多(如龙的身体上边界和龙尾边界部位)，在曲率较低的地方保留的点数又太少。而且该方法未考虑边界，使得边界平坦区域的某些点云(如图中圆圈部分)消失，精简效果一般。图4(d)使用的是本文提出的新方法，精简后点数为17 983个，由于该方法考虑了边界，所以边界点云保留完整，而且在低曲率区域保留了均匀分布的点，在高曲率区域则保留了必要密度的较多的点，特征保持较好，效果优于栅格法和曲率法。

图4 Dragon模型精简示意图

图5为Horse模型的点云精简示意图。图5(a)为原始点云数据，点数为48 484个。图5(b)使用的是栅格法，该方法精简后点数为19 390个，由于网格的大小一定，有些网格包含的点云数量较多则精简的也越多，相反，网格内包含的点数少则精简的少，该方法不考虑模型的曲率高低，精简后模型特征不突出，精简效果一般。图5(c)使用的是曲率法，精简后点云数为19 394个，该方法虽然考虑了模型的曲率，但是在曲率低的地方保留的点数太少(如马的身体部位)，在头部和腿部等曲率高的部位保留的点数太多，而且该方法未考虑边界，使得某些边缘特征丢失(如图中马的耳朵和后蹄部位)，精简效果一般。图5(d)使用的是本文提出的新方法，精简后点数为19 411个，边界特征保留较好，而且在低曲率区域保留了均匀分布的点，在高曲率区域则保留了必要密度的较多的点，精简效果较好。

图5 Horse模型精简示意图

为了更加直观地显示不同方法精简后的效果，把结果用表格的形式呈现出来，并且计算原始点集S和简化后点集S′间的最大误差、平均误差和运行时间，结果如表1所示。

由表1可知，通过3种方法对叶片模型、兔子模型、Dragon模型和Horse模型的精简率基本相同，但是从原始点集S和简化后点集S′间的最大误差和平均误差可知，本文提出的算法使得精简后的数据与原点云数据的差别较小，更好的保留了物体特征。但由于本文算法进行了聚类和曲率计算，所以运行时间要稍高于传统的栅格法和曲率法，这也是后续所要研究的内容。

表1 简化结果对比图

续表1

4 结 论

针对传统的栅格法与曲率法对数据模型进行精简时很容易剔除特征点，具有较高的误判率，导致精简后的数据不能较好的突出点云数据的特征，使重构后的实体模型精度下降的问题，本文提出基于边界保留的K-means聚类算法对点云进行精简。该方法在精简过程中不仅考虑了模型边界，还考虑了模型的曲率高低。从而在精简过程中不仅在曲率较低处保留一些均匀分布的点，在曲率较高的地方保留必要的密集点，而且保持边界的完整性，精简效果优于传统的栅格法和曲率法。但该算法的时间消耗要稍稍高于栅格法和曲率法，这也是下一步所需要改进的地方。