基于alpha shapes 算法的相邻航带点云重叠区提取

张 凡，奚冰柔，申 键，池典赐

（广东省海洋发展规划研究中心，广东 广州）

引言

机载激光lidar（Light Detection And Ranging）测量属于条带式测量的一种，具有空中作业覆盖面广、高精度、高密度、高效率、产品丰富等特点。由于扫描角和航高的限制，不能一次性完成整个测区的数据采集工作，因此为实现作业区全覆盖测量，必须规划多条飞行航线，航带规划布设需保证相邻航线间保持20%以上重叠度[1-2]。但系统误差以及测量随机误差的共同影响，造成相邻航带间同名特征存在三维空间偏移，对后续获取高精度地形数据产生明显影响，为了提高点云数据质量，有必要消除或减少航带区域间的差异。因此要得到完整、精确的点云就需要进行点云配准，确定一个合适的坐标变换矩阵，将不同航带的点云数据集中到统一的坐标系之下，消除相邻航带点云之间的空间偏差。而相邻航带间重叠区同名特征信息较为丰富，能够获得相似特征间的一致性对应关系，经过旋转、平移将不同坐标系下的三维数据集转换到统一坐标系下，有效的消除物体在扫描过程中产生的空间偏差，提升点云数据质量，为后续生成无缝产品。因此重叠区提取对于寻求相邻数据集间重叠区同名相似特征具有重要作用。

本文根据点云轮廓线交集原理实现相邻航带充重叠区提取。首先利用alphashapes 算法完成条带点云的轮廓边界提取，通过设置alpha 圆半径参数，计算点点之间的距离公式进行存储，然后通过引入K-D 树（K-Dimension tree）结构快速搜索的优势，加快alpha shapes算法中圆心坐标计算和轮廓线判断的速率，设置搜索半径并判断点云数量是否满足阈值要求，最后根据PCL（Point cloud Libarary）构建多边形滤波器，分别对相邻航带进行滤波，最终完成相邻航带重叠区的提取工作。实验证明该方法可以完整有效的提取相邻航带间重叠区域，为后续的点云配准工作奠定数据基础。

1 alpha shapes 算法原理

alpha shapes 算法是由Edelsbrunner 等[3]提出的一种可以从离散的空间点集中抽象出其直观形状的方法，如图1，该方法主要适用于多种形状的点云轮廓边界提取，例如可有效地用于提取多种类型建筑物点云边界[4-6]，同时王林振[7]将二维alpha shapes 轮廓提取算法提升至三维空间中，通过地物边界所包含的三维坐标信息，将其划分水下点云类别，实现水深点云滤波。

图1 alpha shapes 提取边界示意图

综上所述，alpha shapes 算法主要适用于点密度较为均匀的数据集[8]。基本原理为若该点集有n 个点构成，可以组成n(n-1)条线段，可以在点集A 中，过任意两点P,Q绘制半径为alpha 的圆，其中给定半径能够确定两点的圆会有两个，且圆心O 是关于弦中心对称，如果这个圆内没有其它的点存在，则认为P,Q 为边界点，其连线PQ为边界线段。本文alpha shapes 具体算法流程如下：

步骤1：设定alpha shapes 算法中alpha 圆半径参数，遍历计算点云数据集中每一条线段PQ；

步骤2：如果PQ 线段的长度大于直径，则认为超出搜索范围，无法找到经过这两个点的圆；

步骤3：依据图2 几何计算关系，分别求出两个圆的圆心O1、O2；

图2 alpha shapes 算法几何关系

步骤4：计算出PQ 的方向向量V，求解PQ 的中点坐标M，并计算V 的垂直向量H；

步骤5：计算PQ 弦长L，根据圆心坐标O=M±D*H公式，解算圆心O 到弦长的距离D；

步骤6：若两个圆中存在任一个圆内部不包含点集A 中的点，则认为P,Q 为边界点；

步骤7：最终获得点云轮廓边界。

该算法中在初始计算过程中，需要遍历计算数据集中每一个点到所有点的之间的线段距离，当数据量庞大时，程序中的两次循环会消耗很多的时间，导致算法的计算效率下降。KD 树结构是一种对k 维空间中数据点进行存储以便对其进行快速检索的树形数据结构，主要应用加速多维空间关键数据的搜索，因此利用K-D 树结构加快算法的时间效率问题，流程如图3 所示。

图3 本文alpha shapes 算法中流程图

2 航带重叠区提取

为了提高计算机的运行效率，减少算法的迭代量，目前大部分点云配准算法研究重点是针对相邻航带的重叠区域进行处理，计算变换矩阵。例如Behan[9]提出的在重叠区布设控制网，进行地面控制点和机载航带点云间的联合平差，解算变换参数；Burman[10]在相邻航带重叠区域利用点云高程、强度信息生成栅格影像进行航带平差；李天烁等[11]根据两站（多站）点云重叠区局部点云的强度信息，生成栅格数据辅助完成点云配准工作。

本文根据机载航带布设条件，认为相邻航带点云数据必有交叉重叠的特性，符合情况如图4，在满足规范要求情况下，点云数据集A 的部分边界必会包围点云数据集B 的部分区域，两者的边界交叉的区域C 则被认为是点云的重叠区域。点云轮廓线提取完成后，可以通过PCL 中的hull.reconstruct(*多边形，边界点)重建封闭多边形，最后利用CropHull 滤波器进行多边形滤波，该模块可通过设置参数提取封闭多边形内部点或者外部点。

图4 交叉重叠示意图

3 试验结果与分析

3.1 alpha shapes 算法提取边界

本文中涉及算法是利用VS2022、PCL 配置环境在windows 平台下编写实现，为进一步验证alpha shapes算法提取相邻航带点云重叠区的有效性，首先通过4 组不同形状的简易点云进行试验，试验结果发现alpha shapes 算法中alpha 圆半径设置越小，在点云内部中凹区域提取轮廓线就会越细致，表现出的点云边界点的连续性越强，试验结果如图5 所示，其中白色代表提取的点云轮廓边界，结果表明，该算法能够有效的对点云数据的边界做出判断，准确的提取点云轮廓，同时也说明该算法在本次试验的4 组样本中对于简易形状的点云边界提取具有可靠性。

图5 4 组不同形状点云边界提取结果

然而在实际测量过程当中，存在航线布设覆盖范围中存在地物的不规则性，且设备传感器性能的影响，导致所扫描的lidar 点云数据存在理想状况不一致，例如由于道路、桥梁或建筑物存在大量的平面结构，激光反射信号强，点云数据密度高，且整体结构表现出明显的规则边界，而对于植被类数据，由于激光信号的穿透性、反射性与树木枝干、叶片的密集程度相关，整体呈现的数据较为离散。因此为验证在实际测量过程中，该算法在提取更加复杂且不规则点云边界的有效性，本文采用两组不同区域的机载激光lidar 相邻航带间数据进行点云轮廓边界提取试验，试验数据信息如表1 所示。

表1 试验数据信息

该数据集的获取环境受机载lidar 扫描数据特性影响，背向扫描物体一侧由于遮挡激光信号，导致无法穿透物体表面，出现数据缺失，无反射信息，造成数据不完整，而且边缘数据受传感器设备和探测环境的影响，边缘部分呈现数据密度稀少、不规则的特征，数据空洞部分较多。根据上诉简易点云试验过程总结，在对5 条航带点云数据边界提取过程中，设定的K-D 树搜索半径参数R 为5.0，alpha 圆半径参数为2.0，最终两组试验点云轮廓线提取结果如图6、7 所示。试验结果中，白色代表提取的的点云轮廓边界，可以发现在5 条航线数据边缘规则区域，alpha shapes 算法提取的点云边界符合边界的走向，也呈现出边界顶点较为连续，而且对于数据中存在的空洞部分，通过该算法设置的参数也能准确的进行识别并能够提取数据内边缘的轮廓边界，同时在数据边缘呈现数据稀少的区域，虽然提取的边界点比较密集，但更加说明该算法对于数据边缘离散出表现的更加敏感，即使存在较小的空洞区域，通过调整设置的alpha 圆半径参数，该算法也可以有效提取，也进一步证明了该算法在整体提取点云轮廓边界方面具有可靠性和鲁棒性。

图6 航带边界提取结果

图7 航带边界提取结果

3.2 航带重叠区域提取

根据点云轮廓线提取结果，利用PCL 中封装后的CropHull 模块进行多边形滤波，提取多边形内部的点云，例如，利用航带1 点云轮廓作为边界矢量提取航带2数据，得到航带1 和航带2 中航带2 的重叠区域，同理提取航带1 重叠区域，最后滤波得到的两组不同区域相邻航带间重叠区结果如图8，图中白色区域为提取的重叠区结果，结果表明利用alpha shapes 算法提取的重叠区结果符合实际测量工作中相邻航带间的重叠特征，可以有效的为后续点云数据处理和特征分析提供数据基础。

图8 相邻航带重叠区

上述重叠区域提取结果中并不会存在重复的点，免去了删除重复值索引，即使提取边界的时候会有重复值的记录，但最后滤波构建多边形时也并不影响滤波的结果，该方法在距离之上没有下功夫，只是单纯设定K-D树半径域值以及查找圆的半径（圆的直径K-D 树的邻域半径），通过提取的效果来确定是否保留结果。

4 结论

本文针对相邻航带重叠区提取，通过alpha shapes算法遍历检测点云轮廓，为加快算法点云轮廓线目标查找和数值计算效率检测效率，引入K-D 树结构计算原始点云中所有邻域点的圆心坐标，并经过两组样本实验，证明了该方法在实现点云轮廓线提取的有效性，最后根据相邻航带点云轮廓线创建多边形，利用PCL 中的多边形滤波器分别提取相邻航带交集处重叠区域。根据数据处理结果来看，提取的相邻航带重叠区符合实际地区的重叠区形状，而且对于重叠区的地势特征并没有带来损失，为航带配准奠定了数据基础。