vision systems attempt to recover useful information about the three-dimensional world from huge image arrays of sensed values. Since direct interpretation of large amounts of raw data by computer is difficult, it is often convenient to partition (segment) image arrays into low-level entities (groups of pixels with similar properties) that can be compared to higher-level entities derived from representations of world knowledge. Solving the segmentation problem requires a mechanism for partitioning the image array into low-level entities based on a model of the underlying image structure. Using a piecewise-smooth surface model for image data that possesses surface coherence properties, we have developed an algorithm that simultaneously segments a large class of images into regions of arbitrary shape and approximates image data with bivariate functions so that it is possible to compute a complete, noiseless image reconstruction based on the extracted functions and regions. Surface curvature sign labeling provides an initial coarse image segmentation, which is refined by an iterative region growing method based on variable-order surface fitting. Experimental results show the algorithm's performance on six range images and three intensity images. Index Terms--Image segmentation, range images, surface fitting. I. INTR~DUCTI~N C OMPUTER vision systems attempt to recover useful information about the three-dimensional (3-D) world from huge image arrays of sensed values. Since direct interpretation of large amounts of raw data by computer is difficult, it is often convenient to partition (segment) image arrays into low-level entities (groups of pixels with particular properties) that can be compared to higher-level entities derived from representations of world knowledge. Solving the segmentation problem requires a mechanism for partitioning the image array into useful entities based on a model of the underlying image structure. In most easily interpretable images, almost all pixel values are statistically and geometrically correlated with neighboring pixel values. This pixel-to-pixel correlation, or spatial coherence, in images arises from the spatial coherence of the physical surfaces being imaged. In range images, where each sensed value measures the distance to physical surfaces from a known reference surface, the pixel values collectively exhibit the same spatial coher- ence properties as the actual physical surfaces they represent. This has motivated us to explore the possibilities of a surface-based image segmentation algorithm that uses the spatial coherence (surface coherence) of the data to organize pixels into meaningful groups for later visual processes. Many computer vision algorithms are based on inflexible, unnecessarily restricting assumptions about the world and the underlying structure of the sensed image data. The following assumptions are common: 1) all physical objects of interest are polyhedral, quadric, swept (as in generalized cylinders), convex, or combinations thereof; 2) all physical surfaces are planar, quadric, swept, or convex; 3) all image regions are rectangular or regularly shaped and are approximately constant in brightness; and 4) all image edges are linear or circular. The extensive research based on these assumptions solves many important application problems, but these assumptions are very limiting when analyzing scenes containing real-world objects with free-form, sculptured surfaces. Therefore, we have developed an image segmentation algorithm based only on the assumption that the image data exhibits SUTface coherence in the sense that the image data may be interpreted as noisy samples of a piecewise-smooth surface function. A preliminary grouping of pixels is based on the sign of mean and Gaussian surface curvature. This initial, coarse segmentation is refined by an iterative region growing procedure based on variable-order bivariate surface fitting. The order of the surface shape hypotheses is automatically controlled byjtting surfaces to the image data and testing the sur-ucejts by 1) checking the spatial distribution of the signs of residual fitting errors (the regions test) and 2) comparing the mean square residual error of the fit to a threshold proportional to an estimate of the image noise variance. In this iterative process, images are not only segmented into regions of arbitrary shape, but the image data in those regions is also approximated with flexible bivariate functions such that it is possible to compute a complete, noiseless image reconstruction based on the extracted functions and regions. We believe that an explicit image description based on flexibly shaped approximating functions defined over arbitrary connected image regions can be useful in many computer vision applications, but will be critically important to object reconstruction and object recognition algorithms based on range imaging sensors when object volumes are bounded by free-form, smooth surfaces. Although this segmentation algorithm may be most useful for range images, it is capable of segmenting any type 0162-8828/88/0300-0167$01.00 0 1988 IEEE
In the original paper REF , noisy image and range data are modeled as piecewise smooth surfaces.
Segmentation through variable-order surface fitting
IEEE Trans. Pattern Anal. Mach. Intell.
IEEE Trans. Pattern Anal. Mach. Intell.
Computer Science