This thesis describes an algorithm for efficient segmentation of point cloud data into local planar surface regions. This is a problem of generic interest to researchers in the computer graphics, computer vision, artificial intelligence and robotics community where it plays an important role in applications such as object recognition, mapping, navigation and conversion from point clouds representations to 3D surface models. Prior work on the subject is either computationally burdensome, precluding real time applications such as robotic navigation and mapping, prone to error for noisy measurements commonly found at long range or requires availability of co-registered color imagery. The approach we describe consists of 3 steps: (1) detect a set of candidate planar surfaces, (2) cluster the planar surfaces merging redundant plane models, and (3) segment the point clouds by imposing a Markov Random Field (MRF) on the data and planar models and computing the Maximum A-Posteriori (MAP) of the segmentation labels using Bayesian Belief Propagation (BBP). In contrast to prior work which relies on color information for geometric segmentation, our implementation performs detection, clustering and estimation using only geometric data. Novelty is found in the fast clustering technique and new MRF clique potentials that are heretofore unexplored in the literature. The clustering procedure removes redundant detections of planes in the scene prior to segmentation using BBP optimization of the MRF to improve performance. The MRF clique potentials dynamically change to encourage distinct labels across depth discontinuities. These modifications provide improved segmentations for geometry-only depth images while simultaneously controlling the computational cost. Algorithm parameters are tunable to enable researchers to strike a compromise between segmentation detail and computational performance. Experimental results apply the algorithm to depth images from the NYU depth dataset which indicate that the algorithm can accurately extract large planar surfaces from depth sensor data.
