Convergent Smoothing and Segmentation of Noisy Range Data in Multiscale Space

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.