Fast segmentation of range imagery into planar regions

Abstract

A technique is presented for rapidly dividing surfaces in range imagery into regions satisfying a common homogeneity criterion. The result is a segmentation of the range information into approximately planar surface regions. Key features that enhance that algorithm's speed include the development of appropriate region descriptors and the use of fast region comparison techniques for segmentation decisions. The algorithm is a split-and-merge segmentation approach, where the homogeneity criteria is based on a 3-parameter planar surface description technique. The three parameters are two angles describing the orientation of the normal to the local best fit plane and the original range value. Speed is achieved because both the region splitting and the rejection of merge possibilities can often be based on simple comparisons of only the two orientation parameters. A fast, but more complex region-to-region range continuity test is also developed, for use when the orientation homogeneity tests are inconclusive. The importance of merge ordering is considered, and in particular, an effective ordering technique based on dynamic criteria relaxation is demonstrated. Example segmentations of simple and complex range data images are shown, and the effects of noise and preprocessing are examined. © 1989.