Graph theoretic approach to segmentation of MR images

Publisher Website
Google Scholar
Abstract
A novel graph theoretic approach to image segmentation is presented, and its application to tissue segmentation in MR images of the human brain is demonstrated. An undirected adjacency graph G is used to represent the image with each vertex of G corresponding to a homogeneous component of the image. Each component may be a single pixel or a connected region which, under a suitable criterion, is homogeneous. All pairs of nodes corresponding to spatially connected pixels or regions in the image are linked by arcs in G. A flow capacity, assigned to each arc, is chosen to reflect the probability that the pair of linked vertices belong to the same region or tissue type. The segmentation is achieved through clustering vertices in G by removing arcs of G to form mutually exclusive subgraphs. The subgraphs formed by the clustering algorithm are optimal in the sense that the largest inter-subgraph maximum flow is minimized. Each of the resulting subgraphs then represents a homogeneous region of the image. Using a suitable choice of the arc capacity function, this approach can be used to segment the image either by searching for statistically homogeneous regions (texture segmentation) or by searching for closed region boundaries (edge detection). A direct implementation of the new segmentation algorithm requires the construction of a flow equivalent spanning tree for G. As the size of the graph G increases, constructing an equivalent tree becomes very inefficient. In order to overcome this problem, an algorithm for hierarchically constructing and partitioning a partially equivalent tree of much reduced size has been developed. This hierarchical algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree of G.© (1991) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

This publication has 0 references indexed in Scilit: