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

2023.27 科学技术创新基于 alpha shapes 算法的相邻航带点云重叠区提取张凡，奚冰柔，申键，池典赐（广东省海洋发展规划研究中心，广东 广州）引言机载激光 lidar（Light Detection And Ranging）测量属于条带式测量的一种，具有空中作业覆盖面广、高精度、高密度、高效率、产品丰富等特点。由于扫描角和航高的限制，不能一次性完成整个测区的数据采集工作，因此为实现作业区全覆盖测量，必须规划多条飞行航线，航带规划布设需保证相邻航线间保持20%以上重叠度1-2。但系统误差以及测量随机误差的共同影响，造成相邻航带间同名特征存在三维空间偏移，对后续获取高精度地形数据产生明显影响，为了提高点云数据质量，有必要消除或减少航带区域间的差异。因此要得到完整、精确的点云就需要进行点云配准，确定一个合适的坐标变换矩阵，将不同航带的点云数据集中到统一的坐标系之下，消除相邻航带点云之间的空间偏差。而相邻航带间重叠区同名特征信息较为丰富，能够获得相似特征间的一致性对应关系，经过旋转、平移将不同坐标系下的三维数据集转换到统一坐标系下，有效的消除物体在扫描过程中产生的空间偏差，提升点云数据质量，为后续生成无缝产品。因此重叠区提取对于寻求相邻数据集间重叠区同名相似特征具有重要作用。本文根据点云轮廓线交集原理实现相邻航带充重叠区提取。首先利用 alphashapes 算法完成条带点云的轮廓边界提取，通过设置 alpha 圆半径参数，计算点点之间的距离公式进行存储，然后通过引入 K-D 树（K-Di原mension tree）结构快速搜索的优势，加快 alpha shapes算法中圆心坐标计算和轮廓线判断的速率，设置搜索半径并判断点云数量是否满足阈值要求，最后根据 PCL（Point cloud Libarary）构建多边形滤波器，分别对相邻航带进行滤波，最终完成相邻航带重叠区的提取工作。实验证明该方法可以完整有效的提取相邻航带间重叠区域，为后续的点云配准工作奠定数据基础。1alpha shapes 算法原理alpha shapes 算法是由 Edelsbrunner 等3提出的一种可以从离散的空间点集中抽象出其直观形状的方法，如图 1，该方法主要适用于多种形状的点云轮廓边界提取，例如可有效地用于提取多种类型建筑物点云边界4-6，同时王林振7将二维 alpha shapes 轮廓提取算法提升至三维空间中，通过地物边界所包含的三维坐标信息，将其划分水下点云类别，实现水深点云滤波。综上所述，alpha shapes 算法主要适用于点密度较为均匀的数据集8。基本原理为若该点集有 n 个点构成，可以组成 n(n-1)条线段，可以在点集 A 中，过任意两点 P,Q作者简介院张凡（1993-），男，硕士，助理工程师，研究方向：机载点云数据处理与分析。摘要：相邻航带点云重叠区提取是实现点云配准工作的前提，本文利用 alpha shapes 算法原理，并结合K-D 树快速查找的优势完成航带点云的轮廓边界提取，最后根据 PCL 中多边形滤波器提取点云边界包含区域，完成相邻航带点云重叠区提取工作。本文试验首先根据简易点云完成初步试验，总结参数的设置情况，最后根据实际作业情况采用两组不同区域相邻航带点云进一步完成对该算法有效性进行验证，结果表明该方法原理简单，设置参数少，对数据边界提取有较强的鲁棒性，且重叠区输出结果可靠。关键词：点云配准；alpha shapes 算法；点云轮廓；重叠区点云中图分类号院P229.1文献标识码院A文章编号院2096-4390渊2023冤27-0089-04图 1alpha shapes 提取边界示意图89-科学技术创新 2023.27绘制半径为 alpha 的圆，其中给定半径能够确定两点的圆会有两个，且圆心 O 是关于弦中心对称，如果这个圆内没有其它的点存在，则认为 P,Q 为边界点，其连线 PQ为边界线段。本文 alpha shapes 具体算法流程如下：步骤 1：设定 alpha shapes 算法中 alpha 圆半径参数，遍历计算点云数据集中每一条线段 PQ；步骤 2：如果 PQ 线段的长度大于直径，则认为超出搜索范围，无法找到经过这两个点的圆；步骤 3：依据图 2 几何计算关系，分别求出两个圆的圆心 O1、O2；步骤 4：计算出 PQ 的方向向量 V，求解 PQ 的中点坐标 M，并计算 V 的垂直向量 H；步骤 5：计算 PQ 弦长 L，根据圆心坐标 O=M依D*H公式，解算圆心 O 到弦长的距离 D；步骤 6：若两个圆中存在任一个圆内部不包含点集A 中的点，则认为 P,Q 为边界点；步骤 7：最终获得点云轮廓边界。图 2alpha shapes算法几何关系该算法中在初始计算过程中，需要遍历计算数据集中每一个点到所有点的之间的线段距离，当数据量庞大时，程序中的两次循环会消耗很多的时间，导致算法的计算效率下降。KD 树结构是一种对 k 维空间中数据点进行存储以便对其进行快速检索的树形数据结构，主要应用加速多维空间关键数据的搜索，因此利用 K-D 树结构加快算法的时间效率问题，流程如图 3 所示。2航带重叠区提取为了提高计算机的运行效率，减少算法的迭代量，目前大部分点云配准算法研究重点是针对相邻航带的重叠区域进行处理，计算变换矩阵。例如 Behan9提出的在重叠区布设控制网，进行地面控制点和机载航带点云间的联合平差，解算变换参数；Burman10在相邻航带重叠区域利用点云高程、强度信息生成栅格影像进行航带平差；李天烁等11根据两站（多站）点云重叠区局部点云的强度信息，生成栅格数据辅助完成点云配准工作。本文根据机载航带布设条件，认为相邻航带点云数据必有交叉重叠的特性，符合情况如图 4，在满足规范要求情况下，点云数据集 A 的部分边界必会包围点云数据集 B 的部分区域，两者的边界交叉的区域 C 则被认为是点云的重叠区域。点云轮廓线提取完成后，可以通过PCL 中的 hull.reconstruct(*多边形，边界点)重建封闭多边形，最后利用 CropHull 滤波器进行多边形滤波，该模块可通过设置参数提取封闭多边形内部点或者外部点。图 4交叉重叠示意图3试验结果与分析3.1alpha shapes 算法提取边界本文中涉及算法是利用 VS2022、PCL 配置环境在windows 平台下编写实现，为进一步验证 alpha shapes算法提取相邻航带点云重叠区的有效性，首先通过 4 组不同形状的简易点云进行试验，试验结果发现 alphashapes 算法中 alpha 圆半径设置越小，在点云内部中凹区域提取轮廓线就会越细致，表现出的点云边界点的连续性越强，试验结果如图 5 所示，其中白色代表提取的点云轮廓边界，结果表明，该算法能够有效的对点云数据的边界做出判断，准确的提取点云轮廓，同时也说明该算法在本次试验的 4 组样本中对于简易形状的点云边界提取具有可靠性。半径K邻域查找原始点云计算邻域内所有点圆心坐标以圆心点作为中心点对原始点云进行半径查找设定alpha shapes半径RR包含的点云个数为2个是否点云轮廓点图3本文 alpha shapes算法中流程图90-2023.27 科学技术创新图 54组不同形状点云边界提取结果然而在实际测量过程当中，存在航线布设覆盖范围中存在地物的不规则性，且设备传感器性能的影响，导致所扫描的 lidar 点云数据存在理想状况不一致，例如由于道路、桥梁或建筑物存在大量的平面结构，激光反射信号强，点云数据密度高，且整体结构表现出明显的规则边界，而对于植被类数据，由于激光信号的穿透性、反射性与树木枝干、叶片的密集程度相关，整体呈现的数据较为离散。因此为验证在实际测量过程中，该算法在提取更加复杂且不规则点云边界的有效性，本文采用两组不同区域的机载激光 lidar 相邻航带间数据进行点云轮廓边界提取试验，试验数据信息如表 1 所示。表 1试验数据信息该数据集的获取环境受机载 lidar 扫描数据特性影响，背向扫描物体一侧由于遮挡激光信号，导致无法穿透物体表面，出现数据缺失，无反射信息，造成数据不完整，而且边缘数据受传感器设备和探测环境的影响，边缘部分呈现数据密度稀少、不规则的特征，数据空洞部分较多。根据上诉简易点云试验过程总结，在对 5 条航带点云数据边界提取过程中，设定的 K-D 树搜索半径参数 R 为 5.0，alpha 圆半径参数为 2.0，最终两组试验点云轮廓线提取结果如图 6、7 所示。试验结果中，白色代表提取的的点云轮廓边界，可以发现在 5 条航线数据边缘规则区域，alpha shapes 算法提取的点云边界符合边界的走向，也呈现出边界顶点较为连续，而且对于数据中存在的空洞部分，通过该算法设置的参数也能准确的进行识别并能够提取数据内边缘的轮廓边界，同时在数据边缘呈现数据稀少的区域，虽然提取的边界点比较密集，但更加说明该算法对于数据边缘离散出表现的更加敏感，即使存在较小的空洞区域，通过调整设置的 alpha 圆半径参数，该算法也可以有效提取，也进一步证明了该算法在整体提取点云轮廓边界方面具有可靠性和鲁棒性。3.2航带重叠区域提取根据点云轮廓线提取结果，利用 PCL 中封装后的CropHull 模块进行多边形滤波，提取多边形内部的点云，例如，利用航带 1 点云轮廓作为边界矢量提取航带 2数据，得到航带 1 和航带 2 中航带 2 的重叠区域，同理提取航带 1 重叠区域，最后滤波得到的两组不同区域相邻航带间重叠区结果如图 8，图中白色区域为提取的重叠区结果，结果表明利用alpha shapes算法提取的重叠区结果符合实际测量工作中相邻航带间的重叠特征，可以有效的为后续点云数据处理和特征分析提供数据基础。上述重叠区域提取结果中并不会存在重复的点，免去了删除重复值索引，即使提取边界的时候会有重复值的记录，但最后滤波构建多边形时也并不影响滤波的结果，该方法在距离之上没有下功夫，只是单纯设定 K-D树半径域值以及查找圆的半径（圆的直径 K-D 树的邻域半径），通过提取的效果来确定是否保留结果。航带序号 点云数量 点云范围 1 188 358 444x692 2 136 201 397x588 3 62 938 259x449 4 98 722 349x500 5 89 136 344x442 （左：航带 1；中：航带 2；右：航带 3）图 6航带边界提取结果（左：航带 4；右：航带 5）图 7航带边界提取结果91-科学技术创新 2023.274结论本文针对相邻航带重叠区提取，通过 alpha shapes算法遍历检测点云轮廓，为加快算法点云轮廓线目标查找和数值计算效率检测效率，引入 K-D 树结构计算原始点云中所有邻域点的圆心坐标，并经过两组样本实验，证明了该方法在实现点云轮廓线提取的有效性，最后根据相邻航带点云轮廓线创建多边形，利用 PCL 中的多边形滤波器分别提取相邻航带交集处重叠区域。根据数据处理结果来看，提取的相邻航带重叠区符合实际地区的重叠区形状，而且对于重叠区的地势特征并没有带来损失，为航带配准奠定了数据基础。参考文献1彭检贵,马洪超,邬建伟,等.一种去除机载 LiDAR 航带重叠区冗余点云的方法 J.计算机工程与应用,2012,48(32):33-38+112.2宋袁龙,刘正军,燕琴,等.机载 LiDAR 旁向重叠区域冗余数据的消除算法J.测绘科学,2013,38(5):162-163+169.3Edelsbrunner H,Kirkpatrick D G,Seidel R.On theshape of a set of points in the plane J.InformationTheory IEEE Transactions on,1983,29(4):551-559.4惠振阳,胡海瑛,李娜，等.改进的 Alpha-shapes 建筑物轮廓线提取算法 J.激光与光电子学进展,2022,59(10):447-455.5伍阳,王丽妍,胡春霞，等.可变半径 Alpha Shapes 提取机载 LiDAR 点云建筑物轮廓 J.中国图象图形学报,2021,26(4):910-923.6王秋燕,陈犀力.基于 Alpha Shapes 算法的 LIDAR 数据建筑物轮廓线提取 J.智能建筑与智慧城市,2019(2):23-25.7王林振.基于 Alpha shapes 算法的机载激光测深点云分类研究D.上海：上海海洋大学,2017.8孙艺哲,李季,刘斌,等.基于改进 Alpha Shapes 算法的农机作业面积测量J.中国农机化学报,2019,40(8):144-148.9Behan A,Maas H G,Vosselman G.Steps towardsQuality Improvement of AirborneLaser Scanner DataJ.Internet Publication,Delft University of Technology,Faculty of Civil Engineering and Geosciences,Sectionof Photogrammetry and Remote Sensing,2000.10Burman H.Laser strip adjustment for data calibra原tion and verification J.International Archives of Pho原togrammetry and Remote Sensing,2002(34):67-72.11李天烁,王晏民,胡春梅.基于激光反射强度的点云自动配准研究J.测绘通报,2014(S2):143-145+150.Extraction of Adjacent Airband PointCloud Overlap Area Based on AlphaShapes AlgorithmZhang Fan,Xi Bingrou,Shen Jian,Chi Dianci（Guangdong Provincial Marine Development Planning and Research Center,Guangzhou，China）Abstract:In this paper,the outline boundary extraction of the adjacent airband point cloud is completedby using the principle of alpha shapes algorithm and the advantage of K-D tree fast search,and finally thepoint cloud boundary inclusion area is extracted according to the polygon filter in PCL to complete the ex原traction of adjacent airband point cloud overlap area.The results show that the method has simple principle,few setting parameters,strong robustness to data boundary extraction,and reliable output results in overlap原ping areas.Key words:point cloud registration;alpha shapes algorithm;point cloud outline;overlapping area pointclouds图 8相邻航带重叠区92-