|
|
|
“Hierarchical and Graph Theoretic Approaches to Image Segmentation and Pattern Classification”
by Zhenyu Wu
May 1992
This dissertation addresses the problems of image segmentation and pattern classification. Two new image segmentation schemes are proposed: hierarchical and graph theoretic. The later scheme is based on a novel graph theoretic approach to data clustering, also developed in this research work. These segmentation methods are applied to the problem of tissue classification of magnetic resonance (MR) images of the human brain.
The hierarchical segmentation scheme uses an unsupervised, region based approach. The images under study are modeled as a mosaic of homogeneous subimages where the pixel intensities in each subimage are characterized by a homogeneous Gauss-Markov random field (GMRF) with unknown parameters. The segmentation seeks to group the pixels into regions which, under a suitable hypothesis, are homogeneous. An analysis of homogeneity testing for GMRFs is presented and two tests are proposed: the hierarchical likelihood ratio test and the dispersion test. Based on the homogeneity tests a hierarchical segmentation approach is suggested. The image is represented by a quadtree, and a split and merge procedure is applied to find large homogeneous regions within the image. This is followed by a segmentation refinement step involving connected component labeling and region growing, in which most of the unclassified pixels will be attached to the neighboring regions to which they are most similar. The idea here is to allow the algorithm to learn about the image by first clustering the `easy' pixels while delaying decisions on the `hard' pixels until more information has been gathered. Finally, a clustering procedure, either a constrained maximum likelihood agglomerative approach or a graph theoretic approach, is used to reduce the number of segmented regions. One difficulty encountered in implementing the algorithm is evaluating the likelihood for irregularly shaped regions when the GMRF model is used. A new highly accurate approximation for the determinant of the covariance matrix based on eigenanalysis is proposed to overcome this problem. This hierarchical scheme may be applied to segment either textured or non-textured images.
A novel graph theoretic approach for data clustering is developed using network flow theory. The data to be clustered are represented by an undirected adjacency graph G with arc capacities assigned to reflect the similarity between the linked vertices. Clustering is achieved by removing arcs of selected minimum cuts in G to form mutually exclusive subgraphs such that the largest inter-subgraph maximum flow is minimized. For graphs of moderate size ~ 1000 vertices), the optimal solution is obtained through partitioning a flow and cut equivalent tree of G, which can be efficiently constructed using the Gomory-Hu algorithm. However for larger graphs this approach is impractical. New theorems for subgraph condensation are derived and are then used to develop a fast algorithm which hierarchically constructs and partitions a partially equivalent tree of much reduced size. This algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices. Using this clustering algorithm, an edge based image segmentation is developed. Each pixel of the image corresponds to a vertex of an undirected graph G and the segmentation is achieved by effectively searching for closed contours of edge elements (equivalent to minimum cuts in G), which consist mostly of strong edges, while rejecting contours containing isolated strong edges. This method is able to accurately locate region boundaries and at the same time guarantees the formation of closed edge contours.