基于邻域栅格筛选的点云边缘点提取方法*

高 阁，李 鹏

（滁州学院 地理信息与旅游学院，安徽 滁州239001）

随着近年来激光扫描技术的发展，三维点云技术也得到了飞速发展。由于可以快速获取被测物体丰富的三维空间信息，且不需要与目标物体进行接触。因此被越来越多的领域所青睐。点云边缘作为描述物体的重要特征，能够用较少的数据点对物体进行清晰的描述。在建筑特征提取[1-2]，逆向工程[3-5]，空洞修复[6]，数据精简[7]等方面都有着广泛的应用。

许多学者对边缘点的提取做出了研究：张志佳等[8]首先对数据进行栅格组织，通过比较栅格内投影点所对应深度的平均值与其八邻域栅格的深度差判断栅格内是否存在边缘点，再对栅格内的投影点进行升序排列筛选出其中的边缘点。王宗跃等[9]通过对点集进行格网组织，在排除掉非边缘格网后再使用Alpha shape算法[10]进行边缘点提取，提升了Alpha shape算法在提取边缘点时的效率。丁承君等[11]借助PCL点云库实现了对点云边缘的提取，通过对待测点与k个邻近点组成向量的夹角进行排序，大于连续夹角的最大差值的点即为边缘点。朱汉华等[12]通过对数据进行三角化构成三角网，最终得到边缘点的连线。这些方法往往倾向于对点云边缘进行更为精细的提取，花费的时间较高。在实际应用时，过于精细的边缘点反而可能会导致拟合出的轮廓线偏离实际位置[1]。

针对这些问题，本文提出了一种快速边缘点提取方法，首先将数据投影到二维平面，再通过四邻域分析筛选出包含边缘点的栅格并判断出边缘点在栅格中的位置，最终得到数据的边缘点。同时，通过追踪包含有边缘点的栅格，还可以实现对边缘点的快速排序，得到边缘点的顺序关系。试验结果证明，本方法可以实现对点云数据边缘的快速提取，并可以根据使用需要对边缘点的精细程度进行控制。

1 原理与方法

1.1 空间投影和栅格建立

点云数据包含的坐标信息有三个维度，为了提高计算效率，本文首先对三维点云进行“伪投影”。通过在后续计算中忽略数据中的其中一个维度，将原本使用的三维坐标系更改为对应的二维坐标系，完成对数据的“伪投影”。这样既可以达到投影的效果，又不需要改变原始点云数据。具体步骤如下：

首先计算点云在三个维度间的最大和最小值之差Dx、Dy和Dz，选取差值最小的维度方向作为投影方向。以Dz的数值最小为例，在后续处理计算中忽略每个点的Z坐标值，并将计算时使用的坐标系更改为X-Y系，在效果上相当于将数据中的所有点都投影到了XOY平面中。

由于投影会造成投影方向上的长度压缩，为了避免提取出的边缘点的间隔不均匀，在进行栅格划分前先通过式（1）计算x维度相对于y维度在投影后产生的长度压缩比例R，随后根据DX、Dy的值，在XOY平面中建立矩形栅格空间，栅格空间的行数L和列数W通过对式（2）取整得到，式中的常数项保证了栅格空间在进行点云填充后仍然能够在四周保留空栅格用于后续处理，

最后将投影中的点云依次填充到栅格空间中的对应位置，每个点在填充时所对应的栅格空间的行列数Gl和Gw通过对式（3）取整后得到，

图1 展示了伪投影和栅格填充效果。

图1 伪投影和栅格填充效果

1.2 边缘点筛选

在进行边缘点筛选时，需要先确定栅格内是否包含有边缘点，再将其中最靠近边缘的点取出。在上文建立的栅格空间中，可以根据是否包含数据点将其中的栅格分为实栅格和空栅格，根据是否包含边缘点将实栅格分为边缘点栅格和非边缘点栅格。由于空栅格会有规律的存在于边缘栅格的周围，因此可以将实栅格邻域的空栅格的分布情况作为判断依据，判断其是否为边缘栅格，以及边缘点在其中的位置。

每个实栅格都有四个由边连接的相邻栅格和四个由点连接的相邻栅格，由于边缘点的分布在空间上是连续的，所以通过由边连接的四个邻域就可以有效的对边缘栅格以及边缘点在其中的位置进行判断。以图2为例，N为待判断的实栅格，设置四个由边连接的邻域栅格Nu、Nd、Nl、Nr为空栅格时，对应的值分别为1、2、4、8，而为实栅格时，对应的值为0。

图2 邻域空栅格对应的值

设置常数J=Nu+Nd+Nl+Nr用于表示栅格周围空栅格的分布情况。当J等于1时，代表当前实栅格仅有上邻域栅格为空栅格，判定该栅格为边缘栅格，取最靠近边缘位置的数据点作为边缘点提取；当J等于5时，代表当前实栅格的左方和上方为空栅格，选取最靠近左上角的点作为边缘点提取。同理，表1展示了所有J值对应的边缘点位置情况。

表1 边缘点位置判断

1.3 边缘点排序

由于所有边缘栅格在空间分布上是连续的，且每个栅格只会提取出一个点，因此在使用本方法提取边缘点后可以很容易对这些边缘点排序。具体操作如下：

标记所有含有边缘点的栅格为待排序栅格，任意选取一个包含边缘点的栅格，标记该栅格为初始栅格，沿顺时针方向依次对该栅格周围的八个栅格进行判断，当发现待排序的边缘栅格时，将其设置为新的中心栅格继续进行上述判断，同时删除上一个中心栅格的待排序标记。以此类推，当中心栅格回到初始栅格位置时，排序结束。为了避免数据中有多个边缘环，还需要查看在一次排序后是否仍留有没有排序的边缘点，若有，则需要在剩余的点中再进行一次排序操作，直到没有边缘点存在。

以图3为例，N为当前判断栅格，图中数字为判断顺序，图3左N位置为初始栅格，沿顺时针方向依次对N的八个邻域栅格进行判断，在4号栅格发现了边缘栅格，于是4号栅格成为了新的待判断栅格，产生了图3中的情况。当N在图3右位置时，在2号栅格找到了初始栅格，说明在排序过程中边缘点已经形成闭环，排序完成。由于每一个栅格都对应一个边缘点，上述过程中中心栅格的转移顺序即为边缘点的排列顺序。

图3 边缘点排序

2 实验结果与分析

为了验证本文方法的有效性，使用C++语言对本文方法进行了实现。实验使用Visual Studio 2019编译器，CPU为英特尔i5-8300H。为了测试方法的效果和速度，本文设置了两组实验分别对本文方法的提取效果和提取速度进行了测试。

2.1 边缘点的提取效果测试

为了测试算法对边缘点的提取效果，选取了四种不同类型的数据，分别由大到小对栅格长度进行设置，提取效果如图4所示。

图4 不同栅格长度下边缘点的提取效果

从图4中可以看出，本方法可以对多种类型数据的边缘点进行有效提取，且对象中出现的空洞边缘也能够得到识别与处理。同时提取的边缘点间隔均匀，贴近与真实物体的边缘。此外，针对所需边缘点的细节情况不同，设置不同的栅格大小，可以对边缘点的数量和精细程度进行控制。图4下数据中有两个大小不同的间隙，在对栅格的边长由小到大依次进行调整后，可以看到两个宽度不同的间隙随着栅格边长的增加而依次消失了。在实际使用中，可以根据这一特性对栅格的大小进行控制，从而对不需要的细节进行剔除。

2.2 边缘点的提取速度测试

为了验证本方法的效率，在保证边缘提取质量的前提下采用不同大小的数据分别使用本文方法和文献[11]方法进行对比。表2为边缘点位置判断。

表2 边缘点位置判断

可以看出，本文方法在时间消耗上明显优于文献[11]方法，并且随着数据量的增加优势会更加明显。由于本文方法的时间复杂度仅为O（n），相较现有的大部分方法在时间花费上更有优势，且这一优势会随着数据量的增加而增加。

3 结束语

文章提出的这种能够快速精准提取点云边缘的方法，通过对数据进行栅格划分，利用边缘栅格与空栅格的空间分布关系，筛选出包含有边缘点的栅格并从中提取出对应的边缘点。根据边缘栅格的分布特点，能够快速地完成边缘点的排序。实验结果表明，本方法具有有效性和快速性。虽然本方法难以严格地提取所有的边缘点，但由于每个提取出的每个边缘点都是所处栅格内最靠近边缘位置的点，更能反映出物体轮廓的真实情况。