随着激光扫描技术的不断发展，基于点云数据的模型重建技术已经广泛应用于变形监测、文物保护与复原、工业制造、逆向工程、三维城市等重要领域^[1-4]，点云数据处理已经成为了研究热点问题。而在点云数据处理过程中，点云边界点的提取是一项重要的工作。点云边界特征是能够表达实物模型原始边界特征的数据点，它不仅作为表达曲面的重要几何特征，而且作为求解曲面的定义域，对实体模型重建起着重要的作用^[5]。因此，在包含明确边界信息的点云数据中，如果需要对点云进行精简，必须首先进行边界点的提取并将其保留下来，继而保证后续模型重建的质量。

现有的点云边界特征点的提取算法大致包括以下3类：①在三角格网模型的基础上，通过判断一个点的邻接点是否都能通过三角网格的边组成闭合曲线来获取边界点^[6-8]；②首先利用空间栅格对点云进行空间划分，基于种子边界栅格识别与生长法提取点云数据中的边界点^[9]；③对点云进行最小二乘平面上投影，然后通过邻近点分布均匀性进行边界点提取^[10]。Shi等^[11]提出通过k-均值聚类与三维格网划分的方法提取边界点，避免由于保留的伪边界点引起边界特征的缺失，但该方法需要迭代判断边界的聚类是否合适，带来了计算负担；黄文明等^[12]提出了一种基于k邻域均匀性分布的改进算法，用均匀性度量值替换原来的角度标准差对边界点进行判定。为进一步提高提取边界点的效率，借鉴上述两种方法，本文提出一种改进的点云边界提取方法，通过k-均值聚类将点云划分为许多个子集群，根据三维格网划分方法探测出边界集群，在边界集群中通过象限识别提取出边界点。

1 快速的点云边界点提取方法 1.1 k-均值聚类

在执行点云数据k-均值聚类算法的过程中，最为关键的是聚类中心的初始化，因为初始化的聚类中心点不同，会产生不同的聚类结果^[13]。本文选取点云数据中均匀分布的k个点作为初始的聚类中心，具体的操作步骤如下。

1) 输入点云数据，创建kd-tree(k-dimensional tree, k维树)索引，完成点云邻域划分。

2) 选择点云数据中任意点，按照固定半径D搜索邻近点，并将搜索到的所有邻近点标记。其中，固定半径D大小需要由用户设定，或者综合分析所有点的最优邻域半径大小得到。

3) 选择未被标记的点作为初始聚类中心。

在聚类中心初始化完成以后，将点云数据中剩余的点按照标准的k-均值聚类方法分配到每个聚类中心的聚类集群中^[13]。

1.2 边界集群探测

为了提取边界点，在对点云数据进行k-均值聚类后，需要探测边界集群。由于初始化的聚类中心是均匀分布的，因此边界集群很容易被识别。图 1为二维空间的边界集群识别的基本方法。对于每个聚类集群的中心点，设定合适的搜索半径，依据勾股定理可知，当以$\sqrt{2} D $为搜索半径时，该聚类中心周围的8个邻近聚类中心就可以被包含到搜索范围中，为了保证搜索的准确度，将搜索半径扩大到$\sqrt{3} D $。如果某个聚类中心的搜索到的邻近聚类中心少于6，则可以认为该聚类为边界集群。在三维空间中，依据以上搜索原则，设定半径为$\sqrt{3} D $的空间球形搜索范围，实现点云边界集群的探测。

1.3 边界点提取

本文采用邻近点与聚类中心点的坐标差值作为判断标准。在确定边界聚类集群后，针对每个边界集群进行边界点的判断与提取。首先通过最小二乘拟合边界集群局部平面，然后依次判断边界集群内的每个点是否为边界点。对于集群内任一点p，将集群内的其他采样点分别与p进行坐标求差，即构建以采样中心点p为坐标原点的三维坐标系，并以差值结果作为点云的新坐标，即创建xpy，xpz和ypz三个空间平面，分别平行于xoy，xoz和yoz原点坐标轴平面。统计位于xpy、xpz、ypz三个平面两侧的点云数量，并分别计算每个平面两侧点云数量的比值，若有一个平面两侧的点云数量之比大于设定的阈值δ，则认为点p为边界点(图 2)。

2 实验与结果

利用来自Hoppe的个人主页的Nascar数据和Hypersheet数据来验证本文算法的有效性和可靠性。图 3(a)和图 3(d)分别为Nascar数据模型的两个侧面；图 3(b)和图 3(e)为本文改进算法提取到的Nascar数据的边界点。从图 3中可以看出，Nascar模型的车窗、车轮及底部其他重要边界被准确地提取出来了，边界点分布均匀清晰。Nascar模型的顶部突起部分之所以没有保留，是因为本文定义的边界点是开放区域的边界，并不包含拐点和尖锐点。图 4(a)为Hypersheet点云数据；图 4(b)为该模型的边界点提取效果，从图中可以看出的Hypersheet的外边界圈也十分明显。

本文还实现了文献[12]提出的边界提取方法，图 3(c)、3(f)及图 4(c)为提取的边界点。对比两种方法提取的结果：①从整体上看，两种方法的效果相当，均提取出了两个点云数据的完整边界；②局部细节上，本文方法提取的边界点分布更为均匀；并且对于Nascar模型，本文方法能够准确地提取位于边界上的拐点，如图 5所示。

为了对比分析两种方法的效率，调整算法的参数，使提取的边界点数量大致相同，统计提取边界点所用的时间如表 1所示。从表 1中可以看出，本文方法通过k-均值聚类首先探测到边界点所在的集群，然后对边界集群适用象限识别方法提取边界点，无需对点云中所有点进行象限判断，大大节约了算法时间。

综上所述，相比于文献[12]方法，本文方法在提取效果和效率上均有显著的改进。

3 结束语

为了加快点云边界特征的提取效率，本文提出了一种k-均值聚类与象限识别相结合的点云边界快速提取方法，通过k-均值聚类方法将点云数据进行了空间划分，对划分得到的许多个空间子集，依据三维格网划分方法进行了边界集群探测，在边界集群中通过象限识别法提取了边界点。实验结果表明，与传统方法相比较，本文方法能够更加高效率地提取分布更为均匀的边界特征点，对点云数据的后续处理具有重要意义。