Multi-Robot Grid Map Stitching Method Combining Graph Features

doi:10.3778/j.issn.1002-8331.2012-0118

Abstract

Abstract: Existing gird map stitching methods tend to degrade the matching accuracy significantly when the map overlap area is small, the map features are few, and there are self-similarities and non-rigid deformations in the map. In this paper, a multi-robot gird map stitching method for combining graph features is presented. First, it extracts the ORBs of the gird map to be matched and coarsely matches them, then builds a median [K]-nearest-neighbor map between the ORBs. Then it builds an optimal transport objective function and fuses the ORBs and map features to build a transport cost matrix, and builds a broadening node filter to solve the optimal match by Sinkhorn algorithm and the rigid body transformation between the two gird maps by RANSAC. In this paper, it experimentally verifies that the method has high stitching accuracy and can cope with low overlap rate and less obvious features, shows fast computation speed, and analyzes the influence of relevant parameters on the performance of the method.

Key words: graph matching, optimal transport, multi-robot, image stitching

摘要： 现有的栅格地图拼接方法在地图重叠区域较小、地图特征较少、地图存在自相似性和非刚性形变的情况下匹配精度往往会大幅度下降甚至失配，提出了一种融合图特征的多机器人栅格地图拼接方法。提取待匹配栅格地图的ORB特征点并粗匹配，接下来建立ORB特征点之间的中值[K]近邻图；建立最优传输目标函数并融合ORB特征和图特征构建传输代价矩阵，同时建立增广节点筛选通过Sinkhorn算法求解最优匹配，RANSAC算法求解两张栅格地图之间的刚体变换，实现多机器人栅格地图的配准和拼接。通过实验验证了该方法具备较高的拼接精度，可应对重叠率低、特征不太明显的场景，展现出了较快的计算速度，并分析了相关参数对算法表现的影响。

关键词: 图匹配, 最优传输, 多机器人, 图像拼接

HUANG Xiaohang, ZENG Bi, LIU Jianqi, WANG Minghui. Multi-Robot Grid Map Stitching Method Combining Graph Features[J]. Computer Engineering and Applications, 2022, 58(14): 299-305.

黄小杭, 曾碧, 刘建圻, 汪明慧. 融合图特征的多机器人栅格地图拼接方法[J]. 计算机工程与应用, 2022, 58(14): 299-305.

References

[1] DURRANT-WHYTE H，BAILEY T.Simultaneous localization and mapping：part I[J].IEEE Robotics & Automation Magazine，2006，13（2）：99-110.
[2] BAILEY T，DURRANT-WHYTE H.Simultaneous localization and mapping（SLAM）：part II[J].IEEE Robotics & Automation Magazine，2006，13（3）：108-117.
[3] FILIPENKO M，AFANASYEV I.Comparison of various SLAM systems for mobile robot in an indoor environment[C]//2018 International Conference on Intelligent Systems（IS），2018：400-407.
[4] AZZAM R，TAHA T，HUANG S，et al.Feature-based visual simultaneous localization and mapping：a survey[J].SN Applied Sciences，2020，2（2）：1-24.
[5] HUANG B，ZHAO J，LIU J.A survey of simultaneous locali-
zation and mapping[J].arXiv：1909.05214，2019.
[6] KONOLIGE K，FOX D，LIMKETKAI B，et al.Map merging for distributed robot navigation[C]//IEEE/RSJ International Conference on Intelligent Robots & Systems，2003.
[7] CARPIN S，BIRK A.Stochastic map merging in rescue environments[C]//Robot Soccer World Cup.Berlin，Heidelberg：Springer，2004：483-490.
[8] CARPIN S，BIRK A，JUCIKAS V.On map merging[J].Robotics and Autonomous Systems，2005，53（1）：1-14.
[9] BIRK A，CARPIN S.Merging occupancy grid maps from multiple robots[J].Proceedings of the IEEE，2006，94（7）：1384-1397.
[10] CARPIN S.Fast and accurate map merging for multi-robot systems[J].Autonomous Robots，2008，25（3）：305-316.
[11] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.
[12] 贾松敏，李雨晨，王可，等.RTM框架下基于分层拓扑结构的多机器人系统地图拼接[J].机器人，2013，35（3）：292-298.
JIA Songmin，LI Yuchen，WANG Ke，et al.Map stitching for multi-robot systems based on hierarchical topology under RTM framework[J].Robotics，2013，35（3）：292-298.
[13] 祝继华，周颐，王晓春，等.基于图像配准的栅格地图拼接方法[J].自动化学报，2015，41（2）：285-294.
ZHU Jihua，ZHOU Yi，WANG Xiaochun，et al.Grid map merging approach based on image registration[J].Acta Automatica Sinica，2015，41（2）：285-294.
[14] 唐宏伟，孙炜，杨凯，等.基于SURF特征的多机器人栅格地图拼接方法[J].电子测量与仪器学报，2017，31（6）：859-868.
TANG Hongwei，SUN Wei，YANG Kai，et al.Grid map merging approach of multi-robot based on SURF feature[J].Journal of Electronic Measurement and Instrumentation，2017，31（6）：859-868.
[15] 李雅梅，苏龙.一种基于局部特征的栅格地图拼接方法[J].计算机应用与软件，2020，37（1）：110-115.
LI Yamei，SU Long.A grid map merging approach based on local feature[J].Computer Applications and Software，2020，37（1）：110-115.
[16] 卫恒，吕强，梁建，等.基于ORB的多机器人SLAM地图融合算法[J].装甲兵工程学院学报，2018，32（1）：85-89.
WEI Heng，LV Qiang，LIANG Jian，et al.Multi-robot SLAM map fusion algorithm based on ORB[J].Journal of Academy of Armored Force Engineering，2018，32（1）：85-89.
[17] KARAMI E，PRASAD S，SHEHATA M.Image matching using SIFT，SURF，BRIEF and ORB：performance comparison for distorted images[J].arXiv：1710.02726，2017.
[18] MUJA M，LOWE D.FLANN-fast library for approximate nearest neighbors user manual[Z].Vancouver，BC，Canada：University of British Columbia.Computer Science Department，2009.
[19] AGUILAR W，FRAUEL Y，ESCOLANO F，et al.A robust graph transformation matching for non-rigid registration[J].Image and Vision Computing，2009，27（7）：897-910.
[20] SARLIN P E，DETONE D，MALISIEWICZ T，et al.Superglue：learning feature matching with graph neural networks[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition，2020：4938-4947.
[21] CUTURI M.Sinkhorn distances：lightspeed computation of optimal transport[C]//Advances in Neural Information Processing Systems，2013：2292-2300.
[22] KNIGHT P A.The Sinkhorn-Knopp algorithm：convergence and applications[J].SIAM Journal on Matrix Analysis and Applications，2008，30（1）：261-275.
[23] HUITL R，SCHROTH G，HILSENBECK S，et al.TUMindoor：an extensive image and point cloud dataset for visual indoor localization and mapping[C]//2012 19th IEEE International Conference on Image Processing，2012：1773-1776.