Real-Time Detection of Planar Regions in Unorganized Point Clouds

Automatic detection of planar regions in point clouds is an important step for many graphics, image processing, and computer vision applications. While laser scanners and digital photography have allowed us to capture increasingly larger datasets, previous approaches for planar region detection are computationally expensive, precluding their use in real-time applications. We present an O(n log n) technique for plane detection in unorganized point clouds based on an efficient Hough-transform voting scheme. It works by clustering sets of approximately co-planar points and by casting votes for these clusters on a spherical accumulator using a trivariate Gaussian kernel. A comparison with competing techniques shows that our approach is considerably faster and scales significantly better than previous ones, being the first practical solution for deterministic plane detection in large unorganized point clouds.