Hierarchical encryption matching algorithm for adjacent strip splicing in airborne LiDAR bathymetry

doi:10.11947/j.AGCS.2025.20240458

Abstract

Abstract:

The complex system integration errors and the high dynamism of the marine environment pose numerous challenges for the adjacent strip splicing in airborne LiDAR Bathymetry (ALB). Existing methods primarily rely on spatial geometric features to establish correspondence, lacking thorough analysis and optimization of this correspondence. Potential outliers in the correspondence significantly impact the accuracy of spatial alignment. To address this, a hierarchical encryption matching algorithm for adjacent strip splicing in ALB is proposed. Our algorithm leverages the robustness of graph space and dynamic optimization mechanism to mitigate the effects of potential mismatches. Firstly, calculate the multi-scale features of ALB point cloud and select points with stable and significant features as feature points. Secondly, based on feature points, a global graph matching is constructed to facilitate the coarse alignment between adjacent strips. Then, an encrypted local graph model is constructed within the neighborhood of the globally matched nodes. Finally, a dynamic mechanism featuring one-to-many and bidirectional matching is employed to identify the optimal matching and eliminate outliers of correspondence. Our algorithm divides the process of adjacent ALB strips splicing into two levels: coarse alignment and fine registration. In the coarse alignment phase, the stability of the global graph structure is fully leveraged. For fine registration, a dynamic optimization strategy utilizing a local neighborhood encryption graph model is employed, effectively bolstering the robustness of correspondence by harnessing local information. The experiment employed measured point cloud data from three regions featuring different carriers and shapes. It compared the performance of RANSAC-ICP, 3D-NDT, MCM algorithms, and features matching algorithms for verification purposes. The accuracy was assessed using rotation error, translation error, and overall error. Balancing accuracy and efficiency, the results demonstrate that the algorithm proposed exhibits significant advantages.

Key words: airborne LiDAR bathymetry, strip splicing, hierarchical graph matching, dynamic optimization, correspondence

CLC Number:

P229

Dongdong PU, Hongzhou CHAI, Yongzhong OUYANG, Chao DONG. Hierarchical encryption matching algorithm for adjacent strip splicing in airborne LiDAR bathymetry[J]. Acta Geodaetica et Cartographica Sinica, 2025, 54(8): 1439-1451.

Figures/Tables 17

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Tab. 1

Tab. 2

Tab. 3

Fig. 7

Tab. 4

Tab. 5

Fig. 8

Tab. 6

Fig. 9

Tab. 7

Tab. 8

References 27

[1]	宋艳朋, 梁佳. 机载激光测深数据处理研究综述[J]. 测绘与空间地理信息, 2023, 46(7): 45-47, 53.
	SONG Yanpeng, LIANG Jia. Overview of research on data processing of airborne laser bathymetry[J]. Geomatics & Spatial Information Technology, 2023, 46(7): 45-47, 53.
[2]	刘焱雄, 郭锴, 何秀凤, 等. 机载激光测深技术及其研究进展[J]. 武汉大学学报(信息科学版), 2017, 42(9): 1185-1194.
	LIU Yanxiong, GUO Kai, HE Xiufeng, et al. Research progress of airborne laser bathymetry technology[J]. Geomatics and Information Science of Wuhan University, 2017, 42(9): 1185-1194.
[3]	GUENTHER G C, THOMAS R W L, LAROCQUE P E. Design considerations for achieving high accuracy with the SHOALS bathymetric LiDAR system[C]//Proceedings of 1996 Laser Remote Sensing of Natural Waters: from Theory to Practice. St. Petersburg: SPIE, 1996: 54-71.
[4]	YANG Bisheng, CHEN Chi. Automatic registration of UAV-borne sequent images and LiDAR data[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 101: 262-274.
[5]	张凡, 徐文学, 唐玲, 等. 机载激光测深数据配准方法比较[J]. 南京信息工程大学学报(自然科学版), 2021, 13(6): 678-685.
	ZHANG Fan, XU Wenxue, TANG Ling, et al. Comparison of airborne LiDAR bathymetry data registration methods[J]. Journal of Nanjing University of Information Science & Technology (Natural Science Edition), 2021, 13(6): 678-685.
[6]	BESL P J, MCKAY N D. A method for registration of 3D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.
[7]	CHETVERIKOV D, STEPANOV D, KRSEK P. Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm[J]. Image and Vision Computing, 2005, 23(3): 299-309.
[8]	贺岩, 陶邦一, 俞家勇, 等. 机载激光测深技术及应用[J]. 中国激光, 2024, 51(11): 284-314.
	HE Yan, TAO Bangyi, YU Jiayong, et al. Development of airborne LiDAR bathymetric technology and application[J]. Chinese Journal of Lasers, 2024, 51(11): 284-314.
[9]	YANG Fanlin, SU Dianpeng, ZHANG Kai, et al. Mosaicing of airborne LiDAR bathymetry strips based on Monte Carlo matching[J]. Marine Geophysical Research, 2017, 38(3): 303-311.
[10]	JI Xue, YANG Bisheng, TANG Qiuhua, et al. A coarse-to-fine strip mosaicing model for airborne bathymetric LiDAR data[J]. IEEE Transactions on Geoscience and Remote Sensing, 2021, 59(10): 8129-8142.
[11]	XU Wenxue, ZHANG Fan, JIANG Tao, et al. Feature curve-based registration for airborne LiDAR bathymetry point clouds[J]. International Journal of Applied Earth Observation and Geoinformation, 2022, 112: 102883.
[12]	XU Wenxue, JIANG Zhengkun, GUO Yadong, et al. Registration of airborne LiDAR bathymetry seafloor point clouds based on the adaptive matching of corresponding points[J]. IEEE Geoscience and Remote Sensing Letters, 2024, 21: 3366416.
[13]	HUANG Xiaoshui, MEI Guofeng, ZHANG Jian. Cross-source point cloud registration: challenges, progress and prospects[J]. Neurocomputing, 2023, 548: 126383.
[14]	MONJI-AZAD S, HESSER J, LÖW N. A review of non-rigid transformations and learning-based 3D point cloud registration methods[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2023, 196: 58-72.
[15]	HUANG Rong, XU Yusheng, YAO Wei, et al. Robust global registration of point clouds by closed-form solution in the frequency domain[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2021, 171: 310-329.
[16]	张广运, 韩一, 张荣庭, 等. 基于空间一致性的同平台点云配准方法[J]. 测绘学报, 2023, 52(5): 789-797. DOI: . doi: 10.11947/j.AGCS.2023.20220262
	ZHANG Guangyun, HAN Yi, ZHANG Rongting, et al. A spatial consistency-based point cloud registration method for the same platform[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(5): 789-797. DOI: . doi: 10.11947/j.AGCS.2023.20220262
[17]	WEINMANN M, JUTZI B, MALLET C. Semantic 3D scene interpretation: a framework combining optimal neighborhood size selection with relevant features[J]. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2014, II-3: 181-188.
[18]	WEINMANN M, JUTZI B, HINZ S, et al. Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 105: 286-304.
[19]	LIVI L, RIZZI A. The graph matching problem[J]. Pattern Analysis and Applications, 2013, 16(3): 253-283.
[20]	JIA Shoujun, LIU Chun, WU Hangbin, et al. Incremental registration towards large-scale heterogeneous point clouds by hierarchical graph matching[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2024, 213: 87-106.
[21]	FU Kexue, LIU Shaolei, LUO Xiaoyuan, et al. Robust point cloud registration framework based on deep graph matching[C]//Proceedings of 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Nashville: IEEE, 2021: 8889-8898.
[22]	YAN Li, DAI Jicheng, TAN Junxiang, et al. Global fine registration of point cloud in LiDAR SLAM based on pose graph[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(2): 26-35.
[23]	ZANFIR A, SMINCHISESCU C. Deep learning of graph matching[C]//Proceedings of 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Salt Lake City: IEEE, 2018: 2684-2693.
[24]	MUNKRES J. Algorithms for the assignment and transportation problems[J]. Journal of Society for Industrial and Applied Mathematics, 1957, 5(1): 32-38.
[25]	LU Fan, CHEN Guang, LIU Yinlong, et al. Sparse-to-dense matching network for large-scale LiDAR point cloud registration[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45(9): 11270-11282.
[26]	PANKAJ D S, NIDAMANURI R R. A robust estimation technique for 3d point cloud registration[J]. Image Analysis & Stereology, 2016, 35(1): 15-28.
[27]	STOYANOV T, MAGNUSSON M, ANDREASSON H, et al. Fast and accurate scan registration through minimization of the distance between compact 3D NDT representations[J]. The International Journal of Robotics Research, 2012, 31(12): 1377-1393.

数据	RMSE	Max_D	Min_D
区域Ⅰ	0.893	0.921	0.321
区域Ⅱ	1.030	1.372	0.293
区域Ⅲ	0.945	1.376	0.404

数据	δ₁/m	δ₂	δ₃/(个/m³)	δ₄/m
区域Ⅰ	1.3	0.08	0.2	3.7
区域Ⅱ	0.5	0.02	0.3	2.8

数据	方法	对应点数量	RE/rad	TE/m	OE/m
区域Ⅰ	单一尺度	275	0.136	0.201	0.115
区域Ⅰ	多尺度	167	0.103	0.105	0.086
区域Ⅱ	单一尺度	496	0.140	0.173	0.103
区域Ⅱ	多尺度	289	0.091	0.090	0.062

数据	算法	RE/rad	E/m	OE/m
区域Ⅰ	RANSAC	0.251	0.364	0.388
区域Ⅰ	全局图匹配	0.109	0.136	0.105
区域Ⅱ	RANSAC	0.219	0.231	0.250
区域Ⅱ	全局图匹配	0.097	0.102	0.099

数据	方法	对应点数量	RE/rad	TE/m	OE/m
区域Ⅰ	方法1	854	0.046	0.092	0.054
	方法2	854	0.023	0.056	0.035
	方法3	612	0.015	0.040	0.031
区域Ⅱ	方法1	1121	0.038	0.081	0.046
	方法2	1121	0.020	0.045	0.032
	方法3	946	0.011	0.032	0.028