Real-time detection of planar regions in unorganized point clouds

• O(nlogn) deterministic technique for plane detection in unorganized point clouds.
• Fast and robust clustering solution for detecting sets of almost coplanar points.
• Efficient voting scheme for detecting planar regions in unorganized point clouds.
• Real-time plane detection in point clouds with up to 105 samples.

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 techniques are computationally expensive, being unable to achieve real-time performance for datasets containing tens of thousands of points, even when detection is performed in a non-deterministic way. We present a deterministic technique for plane detection in unorganized point clouds whose cost is O(nlogn) in the number of input samples. It is based on an efficient Hough-transform voting scheme and works by clustering 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.