Structural segmentation of 3-D point-cloud data is an important step in the acquisition, recognition and visual representation of objects from point data. Associating groups of points that are consistent with structural surface elements allows decision making based on object components that are much more meaningful that the points alone. Processing begins by filtering the 3-D point-cloud data to smooth surfaces and remove noise. Filtering is essential for accurate surface-normal estimation. Our point filtering algorithm steps a 3-D box through the data, using an efficient search algorithm that employs priority queues for sequential sorting in x, y, and z. Filtering is based on the computation of a best planar fit at each box location. After filtering, processing continues by again
stepping through the data and computing local surface normals at each filtered point. We then compute a Minimum Spanning Tree (MST) with nodes consisting of the filtered points, edges established by proximity, and edge weights set as the Euclidean distance between local surface normals. A modified range tree that is
computed on the fly from unsorted point data is used in implementing the MST. We then employ a novel procedure to determine the edges that should be broken, leaving subgraphs that represent structural surfaces. These surfaces have been used for visual display of 3-D LADAR data, extraction of surfaces for automatic detection of buildings, and differentiation between man-made and natural objects.