A new optimal approach to segmentation of 2D range scans to line sections

Abstract

In order to obtain a compact and exact representation of 2D range scans, UKF (unscented Kalman filter) and CDKF (central difference Kalman filter) were proposed for extracting the breakpoint of the laser data. Line extraction was performed in every continuous breakpoint region by detecting the optimal angle and the optimal distance in polar coordinates, and every breakpoint area was constructed with two points. As a proof to the method, an experiment was performed by a mobile robot equipped with one SICK laser rangefinder, and the results of UKF/CDKF in breakpoint detection and line extraction were compared with those of the EKF (extended Kalman filter). The results show that the exact geometry of the raw laser data of the environments can be obtained by segmented raw measurements (combining the proposed breakpoint detection approach with the line extraction method), and method UKF is the best one compared with CDKF and EKF.

Keywords

line extraction / breakpoint detection / unscented Kalman filter / central difference Kalman filter / extended Kalman filter

References

[1] JENSFELF P, CHRISTERNSEN H I. Laser based position acquisition and tracking in and indoor environment [C]// Proceedings of the IEEE International Symposium on Robotics and Automation. Saltillo, 1998: 331–338.

[2] FangZ., TongG.-f., XuX.-he.. A robust and efficient algorithm for mobile robot localization [J]. Acta Automatica Sinica, 2007, 33(1): 48-53

[3] StrackA., FerreinA., LakemeyerG.. Laser-based localization with sparse landmarks [C]. Proc RoboCup Symposium, 2005, Osaka, Springer Press: 569-576

[4] ZhangY.-s., GuoR., LiuY., JiaZ.-y., GuoD.-min.. On-line locating method on micro swimming robot inside pipe [J]. Journal of Harbin Institute of Technology, 2004, 36(10): 1382-1384

[5] VANDORPE J, van BRUSSEL H, XU H. Exact dynamic map building for a mobile robot using geometrical primitives produced by a 2D range finder [C]// Proceedings of the IEEE International Conference on Robotics and Automation. Minneapolis, 1996: 901–908.

[6] PFISTER S T, ROUMELIOTIS S I, BURDICK J W. Weighted line fitting algorithms for mobile robot map building and efficient data representation [C]// Proceedings of the IEEE International Conference on Robotics and Automation. Taipei, 2003: 1304–1311.

[7] BorgesG. A., AldonM. J.. Line extraction in 2D range images for mobile robotics [J]. Journal of Intelligent and Robotic Systems, 2004, 40(3): 267-297

[8] HARATI A, SIEGWART R. A new approach to segmentation of 2D range scans into linear regions [C]// Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. San Diego, 2007: 2083–2088.

[9] PREMEBIDA C, NUNES U. Segmentation and geometric primitives extraction from 2D laser range data for mobile robot application [C]// Proceedings of 5th National Festival of Robotics. Coimbra, 2005.

[10] ForsythD. A., PonceJ.Computer vision: A modern approach [M], 2003, London, Prentice Hall

[11] ARRAS K O, SIEGWART Y. Feature extraction and scene interpretation for map-based navigation and map building [C]// Proceedings of the SPIE, Mobile Robotics XII. Pittsburgh, 1997: 42–53.

[12] NGUYEN V, MARTINELLI A, TOMATIS N, SIEGWART R. A comparison of line extraction algorithms using 2D laser rangefinder for indoor mobile robotics [C]// Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Edmonton, 2005: 929–1934.

[13] AdamasM. D., KerstensA.. Tracking naturally occurring indoor features in 2D and 3D with lidar range/amplitude data [J]. International Journal of Robotics Research, 1998, 17(9): 907-923

[14] BorgesG. A., AldonM. J.. Line extraction in 2D range images for mobile robotics [J]. Journal of Intelligent and Robotic Systems, 2004, 40(3): 267-297

[15] ZHANG S, XIE L, ADAMS M, TANG F. Geometrical feature extraction using 2D range scanner [C]// Proceedings of IEEE International Conference on Control and Automation. Montreal, 2003: 901–905.

[16] JULIER S J. The scaled unscented transformation [C]// Proceedings of the American Control Conference. Anchorage, 2002: 4555–4559.

[17] JulierS. J., UhlmannJ., Durrant-WhyteH. F.. A new method for the nonlinear transformation of means and covariances in filters and estimators [J]. IEEE transactions on Automatic Control, 2000, 45(3): 477-482

[18] NorgaardM., PoulsenN., RavnO.. New developments in state estimation for nonlinear systems [J]. Automatica, 2000, 36(11): 1627-1638

[19] ItoK., XiongK.. Gaussian filters for nonlinear filtering problems [J]. IEEE Transactions on Automatic Control, 2000, 45(5): 910-927