A fast incremental map segmentation algorithm based on spectral clustering and quadtree
A fast incremental map segmentation algorithm based on spectral clustering and quadtree
复制标题
基于谱聚类和四叉树的快速增量地图分割算法
DOI：
10.1177/1687814018761296
复制
发表时间：
2018-02
影响因子：
2.1
通讯作者：
Lijun Zhao
中科院分区：
文献类型：
--
作者：
Yafu Tian;Ke Wang;Ruifeng Li;Lijun Zhao
目前，最先进的同时定位和映射方法能够生成大规模和密集的环境地图。一个主要原因可能是地图分区策略的应用。有效的地图分割方法将降低同时定位和地图创建算法的时间复杂度，更重要的是，它将使机器人对一个地方有拟人化的理解。本文提出了一种基于四叉树和谱聚类的地图分割算法。首先利用四叉树对地图进行层次化组织，然后利用用户友好的准则构造相应的四叉树Laplacian矩阵，从而利用矩阵的稀疏性有效地解决谱聚类问题。在本文中，我们进一步提供了一个实时的，增量的，并行的算法，可以在多核CPU/GPU上实现，以提高所提出的基本算法的性能。我们的算法在多种环境下进行了验证，包括模拟和真实世界的数据，结果表明，该算法可以提供一个正确的和用户友好的分割结果在很短的运行时间。
Currently, state-of-the-art simultaneous localization and mapping methods are capable of generating large-scale and dense environmental maps. One primary reason may be the applications of map partitioning strategies. An efficient map partitioning method will decrease the time complexity of simultaneous localization and mapping algorithm and, more importantly, will make robots understand a place anthropomorphically. In this article, we propose a novel map segmentation algorithm based on quadtree and spectral clustering. The map is first organized hierarchically using quadtree, and then a user-friendly criterion is utilized to construct the corresponding Laplacian matrix for quadtree so that spectral clustering can be solved efficiently based on the sparse property of the matrix. In this article, we go further to provide a real-time, incremental, parallel algorithm that can be implemented on multi-core CPU/GPU to enhance the performance of the proposed basic algorithm. Our algorithms are verified under multiple environments including both simulation and real-world data, and the results reveal that the algorithm can provide a correct and user-friendly segmentation result in a short runtime.
登录
查看更多内容
DOI：
10.1007/1-4020-2721-4_1
发表时间：
2011-04
期刊：
--
影响因子：
--
作者：
B. Ya
通讯作者：
B. Ya
DOI：
--
发表时间：
2007-01
期刊：
--
影响因子：
--
作者：
Stephen Friedman;H. Pasula;D. Fox
通讯作者：
Stephen Friedman;H. Pasula;D. Fox
DOI：
10.1109/icma.2016.7558709
发表时间：
2016-08
期刊：
2016 IEEE International Conference on Mechatronics and Automation
影响因子：
--
作者：
Yafu Tian;Ke Wang;Ruifeng Li;Lijun Zhao
通讯作者：
Yafu Tian;Ke Wang;Ruifeng Li;Lijun Zhao
DOI：
10.1109/34.868688
发表时间：
2000-08-01
影响因子：
23.6
作者：
Shi, JB;Malik, J
通讯作者：
Malik, J
DOI：
10.1007/978-1-4612-0653-8
发表时间：
1996-11
期刊：
--
影响因子：
--
作者：
R. Bhatia
通讯作者：
R. Bhatia