Share Email Print
cover

Proceedings Paper

Graph theoretic approach to segmentation of MR images
Author(s): Zhenyu Wu; Richard M. Leahy
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 1 July 1991
PDF: 13 pages
Proc. SPIE 1450, Biomedical Image Processing II, (1 July 1991); doi: 10.1117/12.44290
Show Author Affiliations
Zhenyu Wu, Univ. of Southern California (United States)
Richard M. Leahy, Univ. of Southern California (United States)


Published in SPIE Proceedings Vol. 1450:
Biomedical Image Processing II
Alan Conrad Bovik; Vyvyan Howard, Editor(s)

© SPIE. Terms of Use
Back to Top