Robust feature extraction within 3D environments is a crucial requirement for many autonomous robotic and tracking applications. 3D Laser range finders and cameras provide extremely rich data about an environment. However, the algorithms which attempt to compress the vast data sets produced by these sensors into features, tend to be fragile in the presence of sensor noise, or computationally expensive. This paper presents a 3D feature extraction technique which greatly compresses 3D range data based on principal component analysis (PCA). PCA can provide a greatly compressed vector set, representing the dominant directions of data points, thus grouping them into planes or lines. It is shown however, that the naive application of PCA to full, 3D, point cloud data sets, results in a poor representation of the dominant data directions. Therefore, a combination of a panoramic camera and 3D laser range finder is used to extract robust planes from 3D range data. The panoramic camera image is first filtered with the Mean Shift algorithm to smooth segments within it, whilst preserving the integrity of the segment edges. These segments are then used to guide the PCA, through an approximate image to range space calibration, to act on the corresponding individual segments of range data. The application of PCA to segmented subsets of 3D point cloud data sets, will be shown to be robust for the detection of planes in both indoor and urban, outdoor environments.

With few exceptions, most of the existing noise reduction and data segmentation algorithms are only suited to image data. Therefore, an adaptive smoothing algorithm, with model-based masks, within a scale space framework is proposed for range data in this paper. This algorithm smoothes range data that conform to predefined, geometric models, while leaving other data points unaffected. The convergence of the algorithm in yielding dominant features is shown based on its compliance with the anisotropic diffusion concept. The weights of the smoothing masks are adaptively calculated according to the Mahalanobis distances between range data and model-based predictions. These behave as the diffusion coefficient in the anisotropic diffusion equation, thus satisfying the requirements of the causality criterion that no new features are introduced from fine to coarse scales. The computational complexity of this algorithm is examined and compared to that of the well-known RANSAC feature extraction algorithm. Unlike RANSAC, it has the advantage that the computational complexity is less affected by increasing the order of the model, and is independent of the number of model outliers. The proposed algorithm can be used to smooth range data in multiscale space by increasing the number of smoothing iterations. Robust, robot-occlusion-invariant features are then easily extracted from the smoothed data by least squares fitting algorithms.