针对传统的基于单线激光雷达的匹配方法在多障碍物环境下匹配精度低的问题, 提出了一种基于图论的匹配方法。该方法从数据点集中提取出具有凹凸性质的特征点, 提取对应的线段并构建属性图模型, 将点集配准问题转化为属性图匹配问题。与传统的基于线段的匹配算法相比, 所提方法基于图模型引入了更多的线段之间的几何关系, 使算法可以适用于多障碍物环境以及动态多障碍物环境; 与传统的基于点的匹配方法相比, 该方法依据特征点组成的线段进行几何意义上的匹配, 通过属性图模型快速找到局部观测数据与全局数据的最佳匹配, 提升了运算效率, 同时也避免了传统方法易陷入局部最优解的缺点。

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.