Feature Extraction and Scene Interpretation for Map-Based Navigation and Map Building

Abstract

A scheme for extracting environment features from 1D range data and their interpretation is presented. Segmentation is done by deciding on a measure of model fidelity which is applied to adjacent groups of measurements. The extraction process is considered to include a subsequent matching step where segments which belong to the same landmark are to be merged while keeping track of those which originate from distinct features. This is done by an agglomerative hierarchical clustering algorithm with a Mahalanobis distance matrix. The method is discussed with straight line segments which are found in a generalized least squares sense using polar coordinates including their first-order covariance estimates. As a consequence, extraction is no longer a real time problem on the level of single range readings, but must be treated on the level of whole scans. Experimental results with three commercially available laser scanners are presented. The implementation on a mobile robot which performs a...