Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T23:17:06.816Z Has data issue: false hasContentIssue false
  • English
  • Français

Merging grid maps of different resolutions by scaling registration

Published online by Cambridge University Press:  20 March 2015

Liang Ma ,
Jihua Zhu ,
Li Zhu ,
Shaoyi Du  and
Jingru Cui
Liang Ma
Affiliation:
Institute of Artificial Intelligence and Robotics, Xi'an Jiaotong University, P. R. China
Jihua Zhu*
Affiliation:
School of Software Engineering, Xi'an Jiaotong University, P. R. China
Li Zhu
Affiliation:
School of Software Engineering, Xi'an Jiaotong University, P. R. China
Shaoyi Du
Affiliation:
Institute of Artificial Intelligence and Robotics, Xi'an Jiaotong University, P. R. China
Jingru Cui
Affiliation:
School of Software Engineering, Xi'an Jiaotong University, P. R. China
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

This paper considers the problem of merging grid maps that have different resolutions. Because the goal of map merging is to find the optimal transformation between two partially overlapping grid maps, it can be viewed as a special image registration issue. To address this special issue, the solution considers the non-common areas and designs an objective function based on the trimmed mean-square error (MSE). The trimmed and scaling iterative closest point (TsICP) algorithm is then proposed to solve this well-designed objective function. As the TsICP algorithm can be proven to be locally convergent in theory, a good initial transformation should be provided. Accordingly, scale-invariant feature transform (SIFT) features are extracted for the maps to be potentially merged, and the random sample consensus (RANSAC) algorithm is employed to find the geometrically consistent feature matches that are used to estimate the initial transformation for the TsICP algorithm. In addition, this paper presents the rules for the fusion of the grid maps based on the estimated transformation. Experimental results carried out with publicly available datasets illustrate the superior performance of this approach at merging grid maps with respect to robustness and accuracy.

Keywords

Multi-robot systemsGrid map mergingScaling transformationIterative closest pointImage registration
Type
Articles
Information
Robotica , Volume 34 , Issue 11 , November 2016 , pp. 2516 - 2531
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Smith, R. C. and Cheeseman, P., “On the representation and estimation of spatial uncertainty,” Int. J. Robot. Res. 5 (4), 56–68 (1986).CrossRefGoogle Scholar
2. Thrun, S., Burgard, W. and , D. Fox, Probabilistic Robotics (MIT Press, Cambridge, MA, USA, 2005).Google Scholar
3. Thrun, S. and Liu, Y., “Multi-Robot SLAM with Sparse Extended Information Filers,” Robotics Research (Springer-Verlag, Berlin, Germany, 2005) pp. 254–266.Google Scholar
4. Carpin, S., Birk, A. and Jucikas, V., “On map merging,” Robot. Auton. Syst. 53 (1), 1–14 (2005).CrossRefGoogle Scholar
5. Huang, W. H. and Beevers, K. R., “Topological map merging,” Int. J. Robot. Res. 24 (8), 601–613 (2005).CrossRefGoogle Scholar
6. Birk, A. and Carpin, S., “Merging occupancy grid maps from multiple robots,” IEEE Proc. 94 (7), 1384 (2006).CrossRefGoogle Scholar
7. Howard, A., Parker, L. E. and Sukhatme, G. S., “Experiments with a large heterogeneous mobile robot team: exploration, mapping, deployment and detection,” Int. J. Robot. Res. 25 (5–6), 431–447 (2006).CrossRefGoogle Scholar
8. Fox, D., Ko, J., Konolige, K., imketai, B., Schulz, D. and Stewart, B., “Distributed multirobot exploration and mapping,” IEEE Proc. 94 (7), 1325–1339 (2006).CrossRefGoogle Scholar
9. Carpin, S., “Fast and accurate map merging for multi-robot systems,” Auton. Robot. 25 (3), 305–316 (2008).CrossRefGoogle Scholar
10. Lina, M.P., Tardos, J.D., Neria, J., “Divide and Conquer: EKF SLAM in O(n),” IEEE Trans. Robot. 24 (5), 1107–1120.Google Scholar
11. Zhu, J., Du, S., Ma, L., Yuan, Z. and Zhang, Q., “Merging grid maps via point set registration,” Int. J. Robot. Autom. 28 (2), 180–191 (2013).Google Scholar
12. Whyte, H. D. and Bailey, T., “Simultaneous localization and mapping (SLAM): Part I. Essential algorithms,” IEEE Robot. Autom. Mag. 13, 99–108 (2006).CrossRefGoogle Scholar
13. Besl, P. J. and McKay, N. D., “A method for registration of 3-D shapes,” IEEE Trans. Pattern Anal. Mach. Intell. 14 (2), 239–256 (1992).CrossRefGoogle Scholar
14. Chetverikov, D., Stepanov, D. and Krsek, P., “Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm,” Image Vis. Comput. 23 (3), 299–309 (2005).CrossRefGoogle Scholar
15. Phillips, J. M., Liu, R. and Tomasi, C., “Non-common Area Robust ICP for Minimizing Fractional RMSD,” Proceedings of International Conference on 3-D Digital Imaging and Modeling (3DIM-07), (2007) pp. 427–434.Google Scholar
16. Du, S., Zheng, N., Ying, S. and Wei, J., “ICP with Bounded Scale for Registration of mD Point Sets,” Proceedings of the IEEE International Conference on Multimedia and Expo (ICME), (2007) pp. 1291–1294.Google Scholar
17. Ying, S., Peng, J., Du, S. and Qiao, H., “A scale stretch method based on ICP for 3D data registration,” IEEE Trans. Autom. Sci. Eng. 6 (3), 559–565 (2010).CrossRefGoogle Scholar
18. Zhu, J. H., Zheng, N. N., Yuan, Z. J., Du, S. Y. and Ma, L., “Robust scaling iterative closest point algorithm with the bidirectional distance measurement,” Electron. Lett. 46 (24), 1604–1605 (2010).CrossRefGoogle Scholar
19. Zhu, J., Meng, D., Li, Z., Du, S. and Yuan, Z., “Robust registration of partially overlapping point sets via genetic algorithm with growth operator,” IET Image Process. 8 (10), 582–590 (2014).CrossRefGoogle Scholar
20. Fischler, M. A. and Bolles, R. C., “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” Commun. ACM 24 (6), 381–395 (1981).CrossRefGoogle Scholar
21. Brown, M. and Lowe, D. G., “Automatic panoramic image stitching using invariant features,” Int. J. Comput. Vis. 74 (1), 59–73 (2007).CrossRefGoogle Scholar
22. Lowe, D. G., “Distinctive image features from scale-invariant keypoints,” Int. J. Comput. Vis. 60 (2), 91–110 (2004).CrossRefGoogle Scholar
23. Censi, A., Iocchi, L. and Grisetti, G., “Scan Matching in the Hough Domain,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), vol. 2 (2005) pp. 2739–2744.Google Scholar
24. Blanco, J. L., González-Jiménez, J. and Fernández-Madrigal, J., “A robust, multi-hypothesis approach to matching occupancy grid maps,” Robotica 31 (5), 687–701 (2013).CrossRefGoogle Scholar
25. Wurm, K.M., Hornung, A., Bennewitz, M., Stachniss, C. and Burgard, W., “OctoMap: A probabilistic, flexible, and compact 3D map representation for robotic systems,” Auton Robot. 34 (3), 189–206 (2013).Google Scholar
26. Mulchrone, K. F., “Application of Delaunay triangulation to the nearest neighbor method of strain analysis,” J. Struct. Geol. 5 (5), 689–702 (2003).CrossRefGoogle Scholar
27. Greenspan, M. and Yurick, M., “Approximate k-d Tree Search for Efficient ICP,” Proceedings of International Conference on 3-D Digital Imaging and Modeling (3DIM-03), (2003) pp. 442–448.Google Scholar
28. Nuchter, A., Lingemann, K. and Hertzberg, J., “Cached k-d Tree Search for ICP algorithms,” Proceedings of International Conference on 3-D Digital Imaging and Modeling (3DIM-07), (2007) pp. 419–426.Google Scholar
29. Hwang, Y., Han, B. and Ahn, H. K., “A Fast Nearest Neighbor Search Algorithm by Nonlinear Embedding,” Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), (2012) pp. 3053–3060.Google Scholar
30. Nuchter, A., Elseberg, J., Schneider, P. and Paulus, D., “Study of parameterizations for the rigid body transformations of the scan registration problem,” Comput. Vis. Image Und. 114 (8), 358–367 (2010).CrossRefGoogle Scholar
31. Stachniss, C., “Robotics Datasets,” [Online]. Available at: http://www.informatik.uni-freiburg.de/~stachnis/datasets.html.Google Scholar
32. Eliazar, A. and Parr, R., “DP-SLAM,” [Online]. Available at: http://www.cs.duke.edu/~parr/dpslam/.Google Scholar
33. Bibby, J., “Axiomatisations of the average and a further generalisation of monotonic sequences,” J. Glasgow Math. 15, 63–65 (1974).CrossRefGoogle Scholar
34. Chae, H. C. and Hwajoon, K., “The validity checking on the exchange of integral and limit in the solving process of PDEs,” Int. J. Math. Anal. 8 (22), 1089–1092 (2014).CrossRefGoogle Scholar
35. Thrun, S., Thayer, S. et al., “Autonomous exploration and mapping of abandoned mines,” IEEE Robot. Autom. Mag. 11 (4), 79–91 (2003).CrossRefGoogle Scholar