A fast incremental map segmentation algorithm based on spectral clustering and quadtree

Abstract

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.