A line segments extraction based undirected graph from 2D laser scans

A novel algorithm to find line segments is proposed from the sequence of points taken by a laser scan, which consists of over segmentation, undirected graph generation and line segments extraction. Firstly, the self-adaptive IEPF method is used to over segment raw points into sub-groups. Secondly, the undirected graph is generated based on merge probability function of sub-groups. Thirdly, according to the main edges, the energy function of undirected graph partition and corresponding minimization method, line segments are extracted. The primary contributions of the work are the main edge, undirected graph and minimization method of energy function, which are more proper to noisy laser scan data. The experimental comparison with 6 state-of-the-art methods, using 2D laser scan data obtained by laser profile sensor and laser range finder, shows better performance and robustness of the new algorithm.