The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-IPI-1030

“Shape Matching and Image Segmentation Using Stochastic Labeling”

by Bir Bhanu

August 1981

New results are presented in the areas of shape matching of nonoccluded and occluded objects in two dimensions, surface approximation by polygons, shape matching of objects in three dimensions, and segmentation of images having unimodal distributions. The same stochastic labeling technique is used in both shape matching and segmentation with various extensions.

Shape matching is viewed as a segment matching problem. Unlike the previous work in shape matching of 2-D objects, the technique is based on a stochastic labeling procedure which explicitly maximizes a criterion function based on the ambiguity and inconsistency of classification. To reduce the computation time, the technique is hierarchical and uses results obtained at low levels to speed up and improve the accuracy of results at higher levels. This basic technique has been extended to the situation where various objects partially occlude each other to form an apparent object and our interest is to find all the objects participating in the occlusion. In such a case several hierarchical processes are executed in parallel for every participating object in the occlusion and are coordinated in such a way that the same segment of the apparent object is not matched to the segments of the different actual objects. These techniques have been applied to two-dimensional shapes represented by polygons and the power of the techniques is demonstrated by the examples taken from synthetic, aerial, industrial and microscope images, where the matching is done after using the actual segmentation methods.

In three dimensional scene analysis, a method based on a laser triangulation principle to acquire 3-D data is described. The problems related with the 3-D data acquisition and geometric processing are addressed. A method is given for representing three dimensional objects, such as complicated automobile castings, by a set of convex planar faces. The major advantage of this method is that it is applicable to a composite object and not restricted to single range view which was the limitation of the previous work in 3-D scene analysis. This method is used to obtain the surface representation of a 3-D object in terms of faces approximated by polygons. The hierarchical stochastic labeling technique used in 2-D shape matching is applied to do the shape matching of 3-D objects based on matching the faces of the unknown view against the faces of the model. Thus the segment matching problem of 2-D becomes face matching problem in 3-D. The objective here is to match the individual views of the object taken from any vantage point. The results of partial shape recognition can be used to determine the orientation of the object in 3-D space.

Further the stochastic labeling technique used for shape matching has been applied for the segmentation of images having unimodal gray level distributions. Unimodal histograms are typically obtained when the image consists mostly of a large background region with other small but significant regions. This is true for most biological and aerial images. The technique provides the control over the relaxation process by choosing three parameters which can be tuned to obtain the desired segmentation results at a faster rate compared to the classical nonlinear relaxation method. Aerial and biological examples are presented.

The techniques developed here have the potential of being useful in industrial automation, navigation and military applications.

To download the report in PDF format click here: USC-IPI-1030.pdf (33.8Mb)