Efficient RANSAC for Point‐Cloud Shape Detection

TLDR

The paper proposes an automatic algorithm for detecting basic shapes in unorganized point clouds. The method decomposes the point cloud into a hybrid structure of shape proxies and residual points using random sampling to identify planes, spheres, cylinders, cones, and tori, enabling applications such as measurement, registration, compression, rendering, classification, meshing, simplification, approximation, and reverse engineering. The algorithm automatically represents CAD models as shape proxies, remains robust to outliers and noise, scales to millions of points within a minute, and is simple and easy to implement.

Abstract

Abstract In this paper we present an automatic algorithm to detect basic shapes in unorganized point clouds. The algorithm decomposes the point cloud into a concise, hybrid structure of inherent shapes and a set of remaining points. Each detected shape serves as a proxy for a set of corresponding points. Our method is based on random sampling and detects planes, spheres, cylinders, cones and tori. For models with surfaces composed of these basic shapes only, for example, CAD models, we automatically obtain a representation solely consisting of shape proxies. We demonstrate that the algorithm is robust even in the presence of many outliers and a high degree of noise. The proposed method scales well with respect to the size of the input point cloud and the number and size of the shapes within the data. Even point sets with several millions of samples are robustly decomposed within less than a minute. Moreover, the algorithm is conceptually simple and easy to implement. Application areas include measurement of physical parameters, scan registration, surface compression, hybrid rendering, shape classification, meshing, simplification, approximation and reverse engineering .