基于图论的单线激光雷达数据匹配方法

张元; 杨志卿

doi:10.3788/IRLA201847.1226001

基于图论的单线激光雷达数据匹配方法

doi: 10.3788/IRLA201847.1226001

张元^1,2,
杨志卿^1,2

1.
中国科学院半导体研究所,北京 100089;
2.
中国科学院大学材料科学与光电技术学院,北京 100049

基金项目:

国家重点研发计划（2016YFB0101001）

详细信息

作者简介:
张元(1991-),男,硕士生,主要从事点云处理与识别方面的研究。Email:zhangyuan@semi.ac.cn

中图分类号: TP242

Single-line LiDAR data matching method based on graph theory

Zhang Yuan^1,2,
Yang Zhiqing^1,2

1.
Institute of Semiconductors,Chinese Academy of Sciences,Beijing 100089,China;
2.
College of Materials Science and Opto-Electronic Technology,University of Chinese Academy of Sciences,Beijing 100049,China

摘要: 针对传统的基于单线激光雷达的匹配方法在多障碍物环境下匹配精度低的问题，提出了一种基于图论的匹配方法。该方法从数据点集中提取出具有凹凸性质的特征点，提取对应的线段并构建属性图模型，将点集配准问题转化为属性图匹配问题。与传统的基于线段的匹配算法相比，所提方法基于图模型引入了更多的线段之间的几何关系，使算法可以适用于多障碍物环境以及动态多障碍物环境；与传统的基于点的匹配方法相比，该方法依据特征点组成的线段进行几何意义上的匹配，通过属性图模型快速找到局部观测数据与全局数据的最佳匹配，提升了运算效率，同时也避免了传统方法易陷入局部最优解的缺点。
- 扫描匹配 /
- 属性图匹配 /
- 位姿估计 /
- 单线激光雷达 /
- 地图创建
Abstract: Aiming at the problem of low registration accuracy of traditional laser scan matching method under multi-obstacle environment, a matching method based on graph theory was proposed. In this method, concave and convex points were extracted from the data points, then the corresponding line segments were extracted and the attribute graph model was constructed. The point set registration problem was transformed into an attribute graph matching problem. The registration parameters were determined by comparing the observed graph model with the reference model. Compared with the traditional matching algorithm based on line segments, the proposed algorithm introduces more geometric attributes between line segments, which have better robustness in multi-obstacle environment or dynamic multi-obstacle environment. Compared with the traditional matching method based on points or feature points, the proposed algorithm constructs the attribute graph model based on the more specific feature points, say convex points and concave points. In this way, the proposed algorithm not only improves the operation efficiency, but also avoids the local minima problem in multi-obstacle environment and dynamic multi-obstacle environment.
- scan matching /
- attributed graph matching /
- pose estimation /
- single line lidar /
- mapping

[1]	Wang F, Wang K, Lai S, et al. An efficient UAV navigation solution for confined but partially known indoor environments[C]//IEEE International Conference on Control Automation, 2014, 1351-1356.
[2]	Shu L, Xu H, Huang M. High-speed and accurate laser scan matching using classified features[C]//IEEE International Symposium on Robotic and Sensors Environments, 2013:61-66.
[3]	Thrun S. Robotic Mapping:A Survey[M]//Lakemeyer G, Nebel B. Exploring artificial intelligence in the new millennium. San Francisco:Morgan Kaufmann Publishers, 2002:1-35.
[4]	Besl P J, Mckay N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2):239-256.
[5]	Feng L, Milios E. Robot pose estimation in unknown environments by matching 2D range scans[J]. Journal of Intelligent Robotic Systems, 1997, 18(3):249-275.
[6]	Cox I J. Blanche-an experiment in guidance and navigation of an autonomous robot vehicle[J]. Robotics Automation IEEE Transactions on, 1991, 7(2):193-204.
[7]	Censi A. An ICP variant using a point-to-line metric[C]//IEEE International Conference on Robotics and Automation, 2008:19-25.
[8]	Veeck M, Veeck W. Learning polyline maps from range scan data acquired with mobile robots[C]//IEEE International Conference on Intelligent Robots and Systems, 2004, 2:1065-1070.
[9]	Gutmann J, Weigel T, Nebel B. A fast, accurate and robust method for self-localization in polygonal environments using laser range finders[J]. Advanced Robotics, 2001, 14(8):651-667.
[10]	Borges G A. A split-and-merge segmentation algorithm for line extraction in 2D range images[C]//IEEE International Conference on Pattern Recognition, 2000, 1:1441.
[11]	Xie Yichen, Chen Jian, Yan Bin, et al. Distance feature set intersection for 3D feature matching[J]. Infrared and Laser Engineering, 2014, 43(8):2728-2732. (in Chinese)谢易辰, 陈健, 闫镔, 等. 三维特征点距离特征集合求交匹配算法[J]. 红外与激光工程, 2014, 43(8):2728-2732.
[12]	Mohamed H A, Moussa A M, Elhabiby M M, et al. Improved real-time scan matching using corner features[J]. ISPRS-International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2016,XLI-B5:533-539.
[13]	Zhang Hui, Qu Ying, Hai Dan, et al. Real-time map building based on clustering for mobile robots[J]. Journal of Computer Applications, 2009, 29(8):2116-2119. (in Chinese)张辉, 渠瀛, 海丹,等. 基于聚类匹配的移动机器人地图实时创建算法[J]. 计算机应用, 2009, 29(8):2116-2119.
[14]	Jia Yonghong, Yue Qingxing, Fu Xiujun, et al. Approach of identifying symbols in scanning map based on morphology[J]. Infrared and Laser Engineering, 2007, 33(S2):303-306. (in Chinese)贾永红, 岳庆兴, 付修军, 等. 基于数学形态学的扫描地图点状符号识别方法[J]. 红外与激光工程, 2007, 33(S2):303-306.
[15]	Li Haichao, Zhang Guangjun. Novel corner matching algorithm based on rotational invariants[J]. Infrared and Laser Engineering, 2008, 37(3):561-564. (in Chinese)李海超, 张广军. 基于旋转不变的角点匹配方法[J]. 红外与激光工程, 2008, 37(3):561-564.
[16]	Xavier J, Pacheco M, Castro D, et al. Fast line, arc/circle and leg detection from laser scan data in a player driver[C]//IEEE International Conference on Robotics and Automation, 2005:3930-3935.
[17]	Van Wyk B J, Van Wyk M A. A pocs-based graph matching algorithm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(11):1526-1530.

[1]	李荣华, 王蒙, 周唯, 付佳茹. 双模态信息融合的飞行目标位姿估计方法 . 红外与激光工程, 2023, 52(3): 20220618-1-20220618-16. doi: 10.3788/IRLA20220618
[2]	范伟, 刘博, 蒋贇. 基于体光栅窄带光学滤波的激光雷达收发波长动态匹配技术研究 . 红外与激光工程, 2022, 51(7): 20210639-1-20210639-7. doi: 10.3788/IRLA20210639
[3]	熊芝, 许航, 张刘港, 郭志豪, 伍楚奇, 冯维, 翟中生, 周维虎, 董登峰. 基于加权加速正交迭代算法的相机位姿估计 . 红外与激光工程, 2022, 51(10): 20220030-1-20220030-9. doi: 10.3788/IRLA20220030
[4]	朱祯悦, 吕淑静, 吕岳. 基于图匹配网络的小样本违禁物品分割算法 . 红外与激光工程, 2021, 50(11): 20210075-1-20210075-9. doi: 10.3788/IRLA20210075
[5]	张鹏泉, 杜铁钧, 史屹君. 掺Tm光纤MOPA准相位匹配单程倍频的单频激光器 . 红外与激光工程, 2020, 49(7): 20200112-1-20200112-5. doi: 10.3788/IRLA20200112
[6]	王鹤, 李泽明. 激光测距仪与相机信息融合过程中位姿标定方法 . 红外与激光工程, 2020, 49(4): 0413002-0413002-8. doi: 10.3788/IRLA202049.0413002
[7]	马乐, 陆威, 姜鹏, 刘迪, 王鹏辉, 孙剑峰. 基于匹配滤波的Gm-APD激光雷达三维重构算法研究 . 红外与激光工程, 2020, 49(2): 0205006-0205006. doi: 10.3788/IRLA202049.0205006
[8]	李云辉, 霍炬, 杨明. 基于图模型的小尺寸飞行器地面试验中位姿估计方法 . 红外与激光工程, 2020, 49(4): 0413003-0413003-8. doi: 10.3788/IRLA202049.0413003
[9]	庄子波, 陈星, 台宏达, 宋德龙, 徐丰田, 邢志伟. 双激光雷达的水平风场估计方法 . 红外与激光工程, 2019, 48(10): 1005008-1005008(8). doi: 10.3788/IRLA201948.1005008
[10]	荆根强, 袁鑫, 段发阶, 洪汉玉, 彭璐. 激光位移计在线校准数据序列匹配方法 . 红外与激光工程, 2019, 48(5): 506006-0506006(10). doi: 10.3788/IRLA201948.0506006
[11]	范晓婷, 李奕, 罗晓维, 张凝, 韩梦芯, 雷建军. 基于光场结构特性与多视点匹配的深度估计 . 红外与激光工程, 2019, 48(5): 524001-0524001(8). doi: 10.3788/IRLA201948.0524001
[12]	张文豪, 李松, 张智宇, 刘芮, 马跃. 利用波形匹配实现卫星激光测高脚点精确定位的方法 . 红外与激光工程, 2018, 47(11): 1117007-1117007(8). doi: 10.3788/IRLA201847.1117007
[13]	马鹏阁, 陈恩庆, 庞栋栋, 羊毅. 基于快速贝叶斯匹配追踪的激光大气信道估计 . 红外与激光工程, 2017, 46(9): 922002-0922002(7). doi: 10.3788/IRLA201746.0922002
[14]	刘玉, 陈凤, 王盈, 黄建明, 魏祥泉. 基于激光雷达的航天器相对位姿测量技术 . 红外与激光工程, 2016, 45(8): 817003-0817003(6). doi: 10.3788/IRLA201645.0817003
[15]	夏文泽, 韩绍坤, 曹京亚, 王亮, 翟倩. 激光雷达距离估计技术 . 红外与激光工程, 2016, 45(9): 906005-0906005(6). doi: 10.3788/IRLA201645.0906005
[16]	马辰昊, 付跃刚, 宫平, 欧阳名钊, 张书瀚. 一种激光雷达复合式扫描方法及试验 . 红外与激光工程, 2015, 44(11): 3270-3275.
[17]	刘常杰, 刘洪伟, 郭寅, 刘邈, 张宾, 叶声华. 基于扫描激光雷达的列车速度测量系统 . 红外与激光工程, 2015, 44(1): 285-290.
[18]	李兴东, 李满天, 郭伟, 陈超, 孙立宁. TOF激光相机六自由度位姿变换估计 . 红外与激光工程, 2015, 44(7): 2231-2238.
[19]	曹晓倩, 马彩文. 基于最优斜面参数估计的局部立体匹配算法 . 红外与激光工程, 2014, 43(3): 973-978.
[20]	汪鲁才, 易锡年, 陈小天, 刘鑫. 自适应连续多级分区与初始阈值估计的快速模板匹配方法 . 红外与激光工程, 2013, 42(4): 1106-1111.

点击查看大图

计量

文章访问数: 560
HTML全文浏览量: 142
PDF下载量: 40
被引次数: 0

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

留言板

基于图论的单线激光雷达数据匹配方法

doi: 10.3788/IRLA201847.1226001

作者简介:
张元(1991-),男,硕士生,主要从事点云处理与识别方面的研究。Email:zhangyuan@semi.ac.cn

Single-line LiDAR data matching method based on graph theory

计量

基于图论的单线激光雷达数据匹配方法

doi: 10.3788/IRLA201847.1226001

1. 中国科学院半导体研究所,北京 100089;

2. 中国科学院大学材料科学与光电技术学院,北京 100049

作者简介:
张元(1991-),男,硕士生,主要从事点云处理与识别方面的研究。Email:zhangyuan@semi.ac.cn

English Abstract

Single-line LiDAR data matching method based on graph theory

1. Institute of Semiconductors,Chinese Academy of Sciences,Beijing 100089,China;

2. College of Materials Science and Opto-Electronic Technology,University of Chinese Academy of Sciences,Beijing 100049,China

全文HTML

目录

留言板

基于图论的单线激光雷达数据匹配方法

doi: 10.3788/IRLA201847.1226001

作者简介: 张元(1991-),男,硕士生,主要从事点云处理与识别方面的研究。Email:zhangyuan@semi.ac.cn

Single-line LiDAR data matching method based on graph theory

计量

出版历程

基于图论的单线激光雷达数据匹配方法

doi: 10.3788/IRLA201847.1226001

1. 中国科学院半导体研究所,北京 100089; 2. 中国科学院大学 材料科学与光电技术学院,北京 100049

作者简介: 张元(1991-),男,硕士生,主要从事点云处理与识别方面的研究。Email:zhangyuan@semi.ac.cn

English Abstract

Single-line LiDAR data matching method based on graph theory

1. Institute of Semiconductors,Chinese Academy of Sciences,Beijing 100089,China; 2. College of Materials Science and Opto-Electronic Technology,University of Chinese Academy of Sciences,Beijing 100049,China

全文HTML

目录

作者简介:
张元(1991-),男,硕士生,主要从事点云处理与识别方面的研究。Email:zhangyuan@semi.ac.cn

1. 中国科学院半导体研究所,北京 100089;

2. 中国科学院大学材料科学与光电技术学院,北京 100049

作者简介:
张元(1991-),男,硕士生,主要从事点云处理与识别方面的研究。Email:zhangyuan@semi.ac.cn

1. Institute of Semiconductors,Chinese Academy of Sciences,Beijing 100089,China;

2. College of Materials Science and Opto-Electronic Technology,University of Chinese Academy of Sciences,Beijing 100049,China