高级检索

ISSN1001-3806CN51-1125/TN 网站地图

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

长测距地基点云密度自适应平面分割算法

安奥博 陈茂霖 赵立都 马成林 刘祥江

引用本文:
Citation:

长测距地基点云密度自适应平面分割算法

    作者简介: 安奥博(1999-),男,硕士研究生,现主要从事地面激光点云3维建模方面的研究.
    通讯作者: 陈茂霖, maolinchen@cqjtu.edu.cn
  • 基金项目:

    自然资源部城市国土资源监测与仿真重点实验室开放基金资助项目 KF-2021-06-102

    国家自然科学基金资助项目 41801394

    重庆交通大学研究生科研创新项目 2022S0090

  • 中图分类号: TN958.98;V557+.4

Density adaptive plane segmentation from long-range point cloud

    Corresponding author: CHEN Maolin, maolinchen@cqjtu.edu.cn ;
  • CLC number: TN958.98;V557+.4

  • 摘要: 为了解决长测距地面激光点云高密度变化的问题,采用了一种密度自适应的平面分割方法。首先基于估算理论点间距构建动态邻域搜索范围,联合内指标和香农熵确定最佳邻域并计算维度特征;然后根据最佳邻域、维度特征、法向量和点面距设计区域增长规则,得到初步分割结果;最终通过面片合并优化分割结果,并在最长扫描距离为1 km的单站地面激光扫描数据进行了实验验证。结果表明,该方法分割准确率达到95%,召回率达到92%,能够准确对长测距地基点云中的建筑物平面进行分割;与传统香农熵方法相比,本文中使用动态邻域搜索范围可以显著提高算法效率。该方法能高效准确地从大场景点云中提取建筑物平面,为城市3维建模提供了参考。
  • 图 1  算法流程图

    Figure 1.  Algorithm flow chart

    图 2  水平夹角直方图构建

    Figure 2.  Construction of horizontal angular interval histograms

    图 3  维度特征

    Figure 3.  Dimensionality feature

    图 4  边界分割结果

    a—传统区域增长 b—改进区域增长

    Figure 4.  Edge segmentation result

    a—traditional region growing  b—improved region growing

    图 5  原始数据

    Figure 5.  Original data

    图 6  地面滤波结果

    Figure 6.  Result of the ground filtering

    图 7  最佳邻域半径选择

    a—动态邻域搜索范围下的有效范围筛选 b—有效范围内的最佳邻域半径

    Figure 7.  Optimal neighborhood radius selection

    a—valid range filtering of dynamic neighborhood search range  b—optimal neighborhood radius in the valid range

    图 8  聚类结果

    Figure 8.  Clustering results

    图 9  理论最佳邻域半径与实验最佳邻域半径对比图

    Figure 9.  Comparison of theoretical optimal neighborhood radius and true optimal neighborhood radius

    图 10  最佳邻域半径的相对误差

    Figure 10.  Relative error of true optimal neighborhood radius

    图 11  面片合并

    a—距离阈值0.1 m  b—距离阈值0.5 m  c—距离阈值1 m

    Figure 11.  Patch combination

    a—distance threshold of 0.1 m  b—distance threshold of 0.5 m  c—distance threshold of 1 m

    图 12  平面分割结果

    Figure 12.  Plane segmentation results

    表 1  CSF参数

    Table 1.  Parameters of CSF

    method cloth resolution/m classification threshold/m iterations rigidness/(N·m-1)
    CSF 1.2 0.02 500 2
    下载: 导出CSV

    表 2  算法参数

    Table 2.  Algorithm parameters

    object ζ/% δ/m φ/(°)
    long-range TLS point cloud 70 0.05 0.05
    下载: 导出CSV

    表 3  分割结果评价

    Table 3.  Analysis of segmentation result

    method precision/% recall/% time/s
    traditional method (the fixed radius 0.461 m) 33 20
    Shannon entropy based on the fixed neighborhoods search range 92 93 5400
    the proposed method (optimal neighborhood radius) 95 92 600
    下载: 导出CSV
  • [1]

    GRUEN A, LI Zh, WANG X H. 3D city modeling with TLS (three line scanner) data[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2003, 34(5): 24-27.
    [2]

    FRYSKOWSKA A, WALCZYKOWSKI P, DELIS P, et al. ALS and TLS data fusion in cultural heritage documentation and modeling[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2015, 40(5): 147-150.
    [3]

    RABBANI T, van den HEUVEL F A, VOSSELMANN G. Segmentation of point clouds using smoothness constraint[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006, 36(5): 248-253.
    [4]

    ADAMS R, BISCHOF L. Seeded region growing[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, 16(6): 641-647. doi: 10.1109/34.295913
    [5]

    BORRMANN D, ELSEBERG J, LINGEMANN K, et al. The 3D Hough transform for plane detection in point clouds: A review and a new accumulator design[J]. 3D Research, 2011, 2(2): 1-13. doi: 10.1007/3DRes.02(2011)1
    [6]

    FISCHLER M A, BOLLES R C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395. doi: 10.1145/358669.358692
    [7]

    QU Y, PAN Q, YAN J. Flight path planning of UAV based on heuristically search and genetic algorithms[C]//31st Annual Conference of IEEE Industrial Electronics Society. IECON 2005. Raleigh, USA: IEEE, 2005: 45-49.
    [8]

    CHE E, OLSEN M J. Fast edge detection and segmentation of terrestrial laser scans through normal variation analysis[J]. ISPRS Annals of Photogrammetry, Remote Sensing & Spatial Information Sciences, 2017, 4(2): 51-57.
    [9]

    MINEO C, PIERCE S G, SUMMAN R. Novel algorithms for 3D surface point cloud boundary detection and edge reconstruction[J]. Journal of Computational Design and Engineering, 2019, 6(1): 81-91. doi: 10.1016/j.jcde.2018.02.001
    [10] 金建国. 聚类方法综述[J]. 计算机科学, 2014, 41(11A): 288-293.

    JIN J G. Review of clustering method[J]. Computer Science, 2014, 41(11A): 288-293(in Chinese). 
    [11]

    NING X, ZHANG X, WANG Y, et al. Segmentation of architecture shape information from 3D point cloud[C]//Proceedings of the 8th International Conference on Virtual Reality Continuum and its A-pplications in Industry. Yokohama, Japan: Association for Computing Machinery, 2009: 127-132.
    [12] 卢维欣, 万幼川, 何培培, 等. 大场景内建筑物点云提取及平面分割算法[J]. 中国激光, 2015, 42(9): 0914004.

    LU W X, WAN Y Ch, HE P P, et al. Extracting and plane segmenting buildings from large scene point cloud[J]. Chinese Journal of Lasers, 2015, 42(9): 0914004 (in Chinese). 
    [13]

    XIA S, CHEN D, WANG R, et al. Geometric primitives in LiDAR point clouds: A review[J]. IEEE Journal of Selected Topics in A-pplied Earth Observations and Remote Sensing, 2020, 13(1): 685-707.
    [14]

    BALLARD D H. Generalizing the Hough transform to detect arbitrary shapes[J]. Pattern Recognition, 1981, 13(2): 111-122. doi: 10.1016/0031-3203(81)90009-1
    [15]

    BOLLES R C, FISCHLER M A. A RANSAC-based approach to model fitting and its application to finding cylinders in range data[C]// International Joint Conference on Artificial Intelligence, 1981. Vancouver, Canada: Citeseer, 1981: 637-643.
    [16]

    TARSHA-KURDI F, LANDES T, GRUSSENMEYER P. Hough-transform and extended RANSAC algorithms for automatic detection of 3D building roof planes from lidar data[C]//ISPRS Workshop on Laser Scanning 2007 and SilviLaser 2007. Espoo, Finland: International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2007: 407-412.
    [17]

    ZHAO B, HUA X, YU K, et al. Indoor point cloud segmentation using iterative gaussian mapping and improved model fitting[J]. IEEE Transactions on Geoscience and Remote Sensing, 2020, 58(11): 7890-7907. doi: 10.1109/TGRS.2020.2984943
    [18]

    WU Y, LI G, XIAN C, et al. Extracting pop: Pairwise orthogonal planes from point cloud using RANSAC[J]. Computers & Graphics, 2021, 94(1): 43-51.
    [19] 王果, 沙从术, 王健. 考虑局部点云密度的建筑立面自适应分割方法[J]. 激光与光电子学进展, 2015, 52(6): 061001.

    WANG G, SHA C Sh, WANG J. Study on segmentation of building facade considering local point cloud density[J]. Laser & Optoelectronics Progress, 2015, 52(6): 061001 (in Chinese). 
    [20]

    DEMANTKÉ J, MALLET C, DAVID N, et al. Dimensionality based scale selection in 3D lidar point clouds[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2012, 38(5): 97-102.
    [21]

    BELTON D, LICHTI D D. Classification and segmentation of terrestrial laser scanner point clouds using local variance information[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006, 36(5): 44-49.
    [22]

    WU H, ZHANG X, SHI W, et al. An accurate and robust region-growing algorithm for plane seg-mentation of TLS point clouds using a multiscale tensor voting method[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2019, 12(10): 4160-4168.
    [23] 张昕怡, 陈茂霖, 刘祥江, 等. 顾及点密度与未知角分辨率的地面点云分类[J]. 激光技术, 2023, 47(1): 59-66.

    ZHANG X Y, CHEN M L, LIU X J, et al. Classification of terrestrial point cloud considering point density and unknown angular re-solution[J]. Laser Technology, 2023, 47(1): 59-66(in Chinese). 
    [24] 杨必胜, 董震, 魏征, 等. 从车载激光扫描数据中提取复杂建筑物立面的方法[J]. 测绘学报, 2013, 42(3): 411-417.

    YANG B Sh, DONG Zh, WEI Zh, et al. Extracting complex building facades from mobile laser scanning data[J]. Acta Geodaetica Et Cartographica Sinica, 2013, 42(3): 411-417 (in Chinese). 
    [25]

    de SOUTO M C P, COELHO A L V, FACELI K, et al. A comparison of external clustering evaluation indices in the context of imbalanced data sets[C]//2012 Brazilian Symposium on Neural Networks. Curitiba Paraná, Brazil: IEEE, 2012: 49-54.
  • [1] 王博刘晓东李君豪陈泰宇刘容麟 . 基于邻域特征的网点激光打孔定位算法研究. 激光技术, 2019, 43(5): 591-596. doi: 10.7510/jgjs.issn.1001-3806.2019.05.001
    [2] 巩育江庞亚军王汞白振旭 . 基于几何特征的点云分割算法研究进展. 激光技术, 2022, 46(3): 326-336. doi: 10.7510/jgjs.issn.1001-3806.2022.03.006
    [3] 吴侃敖建锋方茜 . 地面3维激光扫描技术建筑物特征线提取. 激光技术, 2012, 36(4): 553-556. doi: 10.3969/j.issn.1001-806.2012.04.030
    [4] 时磊虢韬彭赤石书山杨立任曦胡伟 . 电力线激光点云的分割及安全检测研究. 激光技术, 2019, 43(3): 341-346. doi: 10.7510/jgjs.issn.1001-3806.2019.03.010
    [5] 阎得科敬嘉雷霍晶郝培育 . 雪崩管最佳倍增因子线性化温控技术研究. 激光技术, 2018, 42(3): 374-378. doi: 10.7510/jgjs.issn.1001-3806.2018.03.016
    [6] 袁蓓姚红兵张永康佟艳群孟春梅 . 遮光法测量铝薄板高压加载下的动态特征量. 激光技术, 2011, 35(1): 19-21,125. doi: 10.3969/j.issn.1001-3806.2011.01.006
    [7] 赵小侠罗文峰张相武李院院杨森林 . 基于LIBS技术的黄铜等离子体特征参量的研究. 激光技术, 2013, 37(1): 93-96. doi: 10.7510/jgjs.issn.1001-3806.2013.01.023
    [8] 许本志齐丽君王伟朱晓王海林朱广志朱长虹 . 复合激光打孔最佳匹配参量的研究. 激光技术, 2018, 42(1): 5-10. doi: 10.7510/jgjs.issn.1001-3806.2018.01.002
    [9] 闫德立高尚李韶华霍萌 . 基于激光雷达的道路不平度及可行驶区域检测. 激光技术, 2022, 46(5): 624-629. doi: 10.7510/jgjs.issn.1001-3806.2022.05.007
    [10] 刘建熊鹰蒋小华蒋明 . 含能材料激光诱导起爆特征波长解析. 激光技术, 2013, 37(6): 816-819. doi: 10.7510/jgjs.issn.1001-3806.2013.06.025
    [11] 李彬袁丰波李福南韦海英张屹 . 同轴监测激光深熔焊熔池小孔的特征分析. 激光技术, 2017, 41(2): 255-259. doi: 10.7510/jgjs.issn.1001-3806.2017.02.022
    [12] 杜亮亮高向东张南峰季玉坤 . 激光焊接裂纹磁光成像频域特征分析. 激光技术, 2020, 44(2): 226-231. doi: 10.7510/jgjs.issn.1001-3806.2020.02.016
    [13] 王春勇谢俊卞保民李振华 . 提高激光雷达测距精度的最佳信号门限比. 激光技术, 2007, 31(4): 408-411.
    [14] 林成虎任靖日贺春林 . 激光原位碳化铬-镍基复合涂层的组织特征. 激光技术, 2014, 38(2): 186-190. doi: 10.7510/jgjs.issn.1001-3806.2014.02.009
    [15] 李竹曼高向东张南峰 . 大功率碟片激光焊接状态多特征融合分析法. 激光技术, 2017, 41(5): 764-768. doi: 10.7510/jgjs.issn.1001-3806.2017.05.029
    [16] 梁希豪杨寅冯亮杜星王清平 . 基于测风激光雷达银川机场动量下传大风特征研究. 激光技术, 2023, 47(3): 432-438. doi: 10.7510/jgjs.issn.1001-3806.2023.03.023
    [17] 熊征曾晓雁 . 化学反应热效应对激光熔凝区几何特征的影响. 激光技术, 2007, 31(5): 462-464,468.
    [18] 刘壮方菊李元成张晓兵 . 飞秒激光加工SiC/SiC复合材料厚板的孔型特征研究. 激光技术, 2022, 46(6): 736-741. doi: 10.7510/jgjs.issn.1001-3806.2022.06.004
    [19] 苏绍兴于艳玲费旺林仕君伍文丞曹宇张健唐霞辉 . 高功率光纤激光焊接铝合金焊缝成形特征研究. 激光技术, 2017, 41(3): 322-327. doi: 10.7510/jgjs.issn.1001-3806.2017.03.004
    [20] 黎倩郑佳锋朱克云张文玲许皓琳张杰 . 基于激光测风雷达的低空急流结构特征研究. 激光技术, 2020, 44(5): 557-562. doi: 10.7510/jgjs.issn.1001-3806.2020.05.006
  • 加载中
图(12) / 表(3)
计量
  • 文章访问数:  1624
  • HTML全文浏览量:  934
  • PDF下载量:  16
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-07-14
  • 录用日期:  2022-08-26
  • 刊出日期:  2023-09-25

长测距地基点云密度自适应平面分割算法

    通讯作者: 陈茂霖, maolinchen@cqjtu.edu.cn
    作者简介: 安奥博(1999-),男,硕士研究生,现主要从事地面激光点云3维建模方面的研究
  • 1. 重庆交通大学 智慧城市学院,重庆 400074
  • 2. 自然资源部城市国土资源监测与仿真重点实验室,深圳 518038
基金项目:  自然资源部城市国土资源监测与仿真重点实验室开放基金资助项目 KF-2021-06-102国家自然科学基金资助项目 41801394重庆交通大学研究生科研创新项目 2022S0090

摘要: 为了解决长测距地面激光点云高密度变化的问题,采用了一种密度自适应的平面分割方法。首先基于估算理论点间距构建动态邻域搜索范围,联合内指标和香农熵确定最佳邻域并计算维度特征;然后根据最佳邻域、维度特征、法向量和点面距设计区域增长规则,得到初步分割结果;最终通过面片合并优化分割结果,并在最长扫描距离为1 km的单站地面激光扫描数据进行了实验验证。结果表明,该方法分割准确率达到95%,召回率达到92%,能够准确对长测距地基点云中的建筑物平面进行分割;与传统香农熵方法相比,本文中使用动态邻域搜索范围可以显著提高算法效率。该方法能高效准确地从大场景点云中提取建筑物平面,为城市3维建模提供了参考。

English Abstract

    • 近年来,地面激光扫描(terrestrial laser scanning, TLS)作为测绘领域的高新技术,能够高精度、高效地获取地物的空间坐标,广泛应用于古建筑物测绘和城市建模等领域[1], 特别是丰富的立面信息,使城市精细化建模成为可能[2]。由于原始点云呈现无序性和散乱性,需要分割等方法识别场景中的几何基元,点云分割是建筑物提取、几何特征识别和建筑重建的重要步骤。

      点云分割算法分为3类:特征聚类[3]、区域增长[4]和模型拟合[5-6]。特征聚类方法分为边缘提取和聚类两个步骤,传统方法利用法向量变化来提取边缘,边缘质量受边界点法向量估算精度的影响[7]。为避免边界点法向量的直接估算,CHE等人利用最近邻点构建多个三角形的法向量夹角选择边界点[8],MINEO等人通过邻域在投影平面上的包含路径确定真实边界点[9]。聚类算法有k均值聚类算法、k最近邻算法(k-nearest neighbor, KNN)算法和基于密度的聚类算法(density-based spatial clustering of applications with noise, DBSCAN)等[10]。此类方法易受噪声的影响,同时,点云密度不均匀直接影响邻域的确定。区域增长算法实质上是种子点根据判断准则(距离阈值,法向量阈值)的生长过程,其中,平面拟合残差广泛应用于此类算法中[11],如LU等人使用主成分分析法将平面点为种子点,单独将边界点划分至分割结果,保证边界处分割的准确性[12]。模型拟合算法是依据预设模型与原始点云的拟合进行点云分割,使用的几何基元决定着分割精度[13],其中效果较好的是霍夫变换(Hough transform, HT)[14]和随机采样一致性(random sample consensus, RANSAC)[15]两种方法,后者效率和准确度较高[16]。尽管目前对RANSAC的研究已较为深入[17-18],但时间复杂度的影响使得模型拟合算法较难应用到大场景点云中。

      随着扫描硬件的优化,地面激光扫描的测程不断增加,增加了激光扫描的覆盖范围、应用场景,但也带来了场景内点云密度显著变化等问题,目前已有的分割方法较少考虑和讨论密度变化对分割的影响。邻域选择是密度变化带来的影响之一,适应于低密度区域的邻域参数可能难以在高密度区域形成有效邻域[19]。已有方法通常通过设置固定搜索范围来解决邻域尺度不统一的问题,并通过香农熵[20]、曲率一致性水平[21]等指标选择搜索范围内的最佳邻域,但算法效率易受搜索范围大小的影响,例如,在最大扫描距离为1 km、角分辨率为0.06°的点云中,点间距从毫米级到米级,为固定邻域范围带来问题。WU等人通过拟合半变异函数设计多尺度张量的尺度范围来解决显著密度变化的影响,尽管此范围为动态范围,但拟合半变异函数的计算对算法效率影响较大[22]

      针对上述问题,本文中提出了一种基于动态邻域搜索范围的平面分割算法,该算法由角分辨率和扫描距离等因素动态生成邻域搜索范围以消除显著密度变化的影响;根据最佳邻域和局部几何特征(法向量、点面距和维度特征)确定种子点和生长规则,提高点云分割的质量。

    • 本文中的算法首先通过布料模拟滤波(cloth simu- lation filter, CSF) 过滤地面点, 基于随机非地面点邻域估算角分辨率, 并依据角分辨率和扫描距离估算理论点间距。然后面向单点理论点间距$d_{i}(i=1, 2, \cdots, N$; $N$为点云总数), 设计满足局部密度的动态邻域搜索范围, 为避免此范围过大影响效率, 按一定间隔$d_{i}$取值作为聚类半径, 使用$\mathrm{KNN}$算法聚类, 在此基础上使用内指标评价聚类结果得到最佳聚类半径, 以此半径为中心$d_{i}$为区间左右跨度提取有效子集, 并在有效子集中通过香农熵确定最佳邻域和维度特征。根据维度特征提取建筑物和种子点, 在最佳邻域中依据局部几何特征(点面距, 法向量) 设计生长规则进行平面分割, 最终通过面片合并优化结果。算法流程见图 1

      图  1  算法流程图

      Figure 1.  Algorithm flow chart

    • 角分辨率是地面激光扫描仪水平或垂直相邻激光束之间的夹角,针对扫描仪采集参数未知的情况,使用随机点邻域分析估算理论角分辨率。

      对于非地面点云, 随机选取$n$个点$P_{c}(c=1, 2, \cdots$, $n)$, 使用$\mathrm{KNN}$算法搜索其$k$个最近邻点$P_{c_{j}}(j=1, 2$, $\cdots, k)$, 并计算出$P_{c_{j}}$与$P_{c}$的水平夹角(或垂直夹角)。同时, 以$\Delta$为区间宽度建立直方图, 统计每个区间内的点数, 如图 2所示。根据采集原理, 与$P_{c}$所在扫描线相邻的扫描线上的邻近点最多[23], 故将点数最多区间内水平夹角(或垂直夹角) 的平均值作为角分辨率。为了降低参数$\Delta$对角分辨率估算的影响, 区间宽度$\Delta \in$ $\left[0.005^{\circ}, 0.015^{\circ}\right]$, 取值间隔为$0.001^{\circ}$, 分别构建不同$\Delta$下的直方图。取所有角分辨率的中间值, 即为最终的角分辨率。

      图  2  水平夹角直方图构建

      Figure 2.  Construction of horizontal angular interval histograms

    • 地面激光点云密度与扫描距离直接相关,基于不同扫描距离下的理论点间距设计邻域是解决密度变化问题的有效思路。根据角分辨率和扫描距离,理论点间距di表示为:

      $ d_{i}=\beta \times D_{i} $

      (1)

      式中, $\beta$为角分辨率对应的弧度, $D_{i}$为$i$点的扫描距离。

      任一点的最佳邻域,其邻域半径在理论点间距的1~10倍之间[24],即任一点的动态邻域搜索范围为$\left[d_{i}, 10 d_{i}\right]$, 该范围充分考虑局部点云密度,但仍有较多无效子集,使用香农熵查找最佳邻域的效率受无效子集影响较大,依据聚类结果的有效性评价指标去除无效子集。

    • 在动态邻域搜索范围内取$I$倍的$d_{i}(I=1, 2, \cdots, 10)$为聚类半,以此为中心获取有效子集,并通过香农熵计算最佳邻域和维度特征。聚类结果的有效性评价指标可以分为两类:内部指标和外部指标[25]。内部指标仅依靠分类后数据集自身的特征对结果进行评判,外部指标需要借助数据真实情况进行对比分析,可以验证内部指标的有效性。考虑到算法效率,本文中使用戴维森-堡丁内(Davies-Bouldin,DB)指标来确定最佳倍数。

      若聚类结果为$C=\left\{c_{1}, c_{2}, \cdots, c_{m}\right\}, \mathrm{DB}$指标[25]的计算如下:

      $ S=\frac{\sum\limits_\limits{a=1}^{m} \max _\limits{a<b \leqslant m} \frac{\operatorname{avg}\left(c_{a}\right)+\operatorname{avg}\left(c_{b}\right)}{d\left(c_{a}, c_{b}\right)}}{m} $

      (2)

      式中, $S$表示DB指标大小; $\operatorname{avg}\left(c_{a}\right)$和$\operatorname{avg}\left(c_{b}\right)$分别表示$a$类、$b$类点间距的平均值; $d\left(c_{a}, c_{b}\right)$表示$a$类和$b$类几何中心的距离, $a, b=1, 2, \cdots, m$, 且$a<b$。

      根据DB指标最小的原则篮选最佳聚类结果, 其聚类半径对应$d_{i}$的倍数为$I_{1}$。取$\left[\left(I_{1}-1\right) d_{i}, \left(I_{1}+1\right) d_{i}\right]$为动态邻域搜索范围内的有效子集, 并在此范围内取香农熵最小值为最佳邻域。香农熵E[20]的计算如下:

      $ \begin{gathered} E=-\frac{\sqrt{\lambda_{1}}-\sqrt{\lambda_{2}}}{\sqrt{\lambda_{1}}} \ln \left(\frac{\sqrt{\lambda_{1}}-\sqrt{\lambda_{2}}}{\sqrt{\lambda_{1}}}\right)- \\ \frac{\sqrt{\lambda_{2}}-\sqrt{\lambda_{3}}}{\sqrt{\lambda_{1}}} \ln \left(\frac{\sqrt{\lambda_{2}}-\sqrt{\lambda_{3}}}{\sqrt{\lambda_{1}}}\right)-\frac{\sqrt{\lambda_{3}}}{\sqrt{\lambda_{1}}} \ln \left(\frac{\sqrt{\lambda_{3}}}{\sqrt{\lambda_{1}}}\right) \end{gathered} $

      (3)

      式中, $\lambda_{1}, \lambda_{2}, \lambda_{3}$为邻域拟合平面的特征值, 分别代表三轴方向的残差, 且$\lambda_{1} \geqslant \lambda_{2} \geqslant \lambda_{3}$, 在有效子集中根据$E$最小的原则篮选最佳邻域, 并结合$\lambda_{1}, \lambda_{2}$和$\lambda_{3}$得到点所属维度$F$ :

      $ F=\operatorname{argmax}\left(\left[\frac{\sqrt{\lambda_{1}}-\sqrt{\lambda_{2}}}{\sqrt{\lambda_{1}}}, \frac{\sqrt{\lambda_{2}}-\sqrt{\lambda_{3}}}{\sqrt{\lambda_{1}}}, \frac{\sqrt{\lambda_{3}}}{\sqrt{\lambda_{1}}}\right]\right) $

      (4)

      式中,F∈[0, 2],分别对应1维特征(线状点)、2维特征(平面点)、3维特征(离散点),如图 3所示。

      图  3  维度特征

      Figure 3.  Dimensionality feature

    • 区域增长算法的两个关键问题是种子点的选取和生长准则。传统的方法依赖于法向量和点间距,由于边界点法向量的估算精度较低,边界处分割结果有较大误差,如图 4a所示,同时点间距直接受点云密度的影响。基于上述问题,联合最佳邻域和维度特征,改进的方法如下:

      图  4  边界分割结果

      Figure 4.  Edge segmentation result

      (1) 按每一类平面点的比例,筛选建筑物,在各建筑物中执行下述操作。

      (2) 设置空集合,随机选取一平面点进入集合作为种子点。

      (3) 在种子点的最佳邻域中搜索待生长点,将满足以下两个条件的平面点加入集合中。

      $ \max \left(\left|\boldsymbol{n} \cdot \boldsymbol{n}_1\right|, \left|\boldsymbol{n} \cdot \boldsymbol{n}_2\right|\right) \leqslant \delta $

      (5)

      $ \arccos \left(\left|\boldsymbol{n}_1 \cdot \boldsymbol{n}_2\right|\right) \leqslant \varphi $

      (6)

      式中, $\boldsymbol{n}$表示以种子点为起点、以待生长点为终点的向量; $\boldsymbol{n}_{1} 、\boldsymbol{n}_{2}$分别为种子点、待生长点的法向量; $\delta$为点面距阈值; $\varphi$为法向量夹角阈值。

      (4) 选取集合中未进行生长的点作为新的种子点,重复第(3)步过程,直至满足条件的平面点全部进入集合,即为一个平面。

      (5) 当前建筑物中是否存在未进入任何集合的平面点?若是,则新设空集合,并从当前建筑物剩余平面点中随机选择一点进入集合作为种子点,重复第(3)、第(4)步过程。直至全部平面点已进入某一集合。

      平面不仅包含平面点,也包含诸如边界等的线状点,由于区域增长仅针对平面点进行设计,此时的分割结果并不包含线状点,需要将每个建筑物簇中的线状点按距离分配至最近平面以得到初步平面分割结果。同时由于地物遮挡,平面部分信息丢失,存在过分割的情况,面片合并是解决此问题的常用方法,原理是基于法向量夹角阈值和最近邻距离阈值对两个邻近平面进行判断,将满足要求的面片合并,得到完整平面,如图 4b所示。

    • 本文中使用最大扫描距离为1 km的TLS数据进行算法有效性的测试,数据采集于重庆市来福士广场,如图 5所示。场景中一共有5330542个点,建筑物平均点间距为[0.012 m, 0.623 m]。区域Ⅰ、区域Ⅱ、区域Ⅲ的平均扫描距离分别为850 m、20 m、500 m。

      图  5  原始数据

      Figure 5.  Original data

    • 重庆市地形复杂,为准确过滤地面点,根据实验经验,CSF的参数如表 1所示。地面点主要集中在测站点,测站处的地面滤波结果见图 6

      表 1  CSF参数

      Table 1.  Parameters of CSF

      method cloth resolution/m classification threshold/m iterations rigidness/(N·m-1)
      CSF 1.2 0.02 500 2

      图  6  地面滤波结果

      Figure 6.  Result of the ground filtering

      利用随机邻域点分析方法得到的水平角分辨率和垂直角分辨率均为0.0357°。在动态邻域搜索范围中选取I倍的di作为KNN聚类半径得到10个聚类结果,通过DB内指标选取最佳聚类结果,同时使用人工分割结果计算Rand外部指标[25],对选取结果进行验证,如图 7所示。内外指标确定出最佳聚类结果对应的I相同,验证了DB指标的合理性。此时区域Ⅰ、区域Ⅱ和区域Ⅲ的聚类结果如图 8所示, 不同颜色代表不同的类或平面。在此基础上,使用香农熵进一步在有效子集内选取最佳邻域半径的系数,见图 7b

      图  7  最佳邻域半径选择

      Figure 7.  Optimal neighborhood radius selection

      图  8  聚类结果

      Figure 8.  Clustering results

      为验证基于有效子集计算的邻域半径为最佳值,随机选取30个点,基于整个动态邻域搜索范围计算香农熵E最小值,以得到理论上的最佳邻域半径,并与本文中的算法得到的邻域半径进行对比,如图 9所示。其中相对误差都小于1%,如图 10所示。

      图  9  理论最佳邻域半径与实验最佳邻域半径对比图

      Figure 9.  Comparison of theoretical optimal neighborhood radius and true optimal neighborhood radius

      图  10  最佳邻域半径的相对误差

      Figure 10.  Relative error of true optimal neighborhood radius

      表 2中设置了点云分割的相关参数。根据实验经验,平面点比例阈值ζ设置为60%~80%,点面距阈值δ设置为0.05 m~0.15 m,法向量夹角阈值φ为0.05°~ 0.15°时,点云分割效果较好。

      表 2  算法参数

      Table 2.  Algorithm parameters

      object ζ/% δ/m φ/(°)
      long-range TLS point cloud 70 0.05 0.05

      初始分割结果存在过分割现象,如图 11a所示。进行面片合并,将法向量夹角阈值设为0.15°,将最近邻距离阈值设置为0.5 m,效果如图 11b所示。若将最近邻距离阈值设置为1 m,此区域将存在欠分割,如图 11c所示。因此,在长测距点云中,选取合适的最近邻距离阈值可有效消除过分割并避免欠分割。

      图  11  面片合并

      Figure 11.  Patch combination

      最终分割结果如图 12所示。根据准确率和召回率进行精度评价,见表 3。本文中的算法与使用固定距离阈值(平均点间距)的区域增长算法相比,准确度和召回率提高了60%左右,与使用固定搜索范围的香农熵算法相比,查询时间由5400 s降为600 s。

      图  12  平面分割结果

      Figure 12.  Plane segmentation results

      表 3  分割结果评价

      Table 3.  Analysis of segmentation result

      method precision/% recall/% time/s
      traditional method (the fixed radius 0.461 m) 33 20
      Shannon entropy based on the fixed neighborhoods search range 92 93 5400
      the proposed method (optimal neighborhood radius) 95 92 600
    • 面向点云密度变化在地基点云分割中带来的邻域选择问题,提出一种基于动态邻域搜索范围的长测距地基点云平面分割方法。实验结果表明:本文中的平面分割方法的准确率达到95%,召回率达到92%,能有效满足显著密度变化点云分割的需要。同时,与基于固定搜索范围的方法相比,本文中使用动态邻域的方法可以将最佳邻域查询时间由5400 s缩短至600 s,在保证分割精度的基础上显著提高分割效率。结合最佳邻域和维度特征改进区域生长算法,消除了密度变化对平面分割的影响,保证了边界处分割的准确性。下一步研究将联合多站TLS点云进行平面分割,并根据分割结果实现建筑物重建。

参考文献 (25)

目录

    /

    返回文章
    返回