Title
Graph-Theoretic Algorithms For Image Segmentation
Abstract
Image segmentation partitions a digital image into disjoint regions, each region is homogeneous, while adjacent regions are not. A variety of methods have been used to perform segmentation, but only a few utilize graph theory. We introduce a new approximation method for partitioning based on cutsets. During domain-dependent feature analysis, a complete, weighted graph, Kn, is produced. Nodes correspond to pixels or groups of pixels, and edge weights measure the similarity between nodes. Partitioning seeks to minimize the inter-segment and maximize the intra-segment similarity. Given such a weighted graph, our method determines a maximal spanning tree. Of the 2n-1 possible partitions, only those fundamental cutsets corresponding to the edges in a spanning tree are evaluated. Our implementations include adaptation of three similarity measures using this approach. One was proposed by Wu and Leahy. Another was due to Shi and Malik. The third is our contribution. The effectiveness of the three similarity measures on a number of actual images is demonstrated.
Publication Date
1-1-1999
Publication Title
Proceedings - IEEE International Symposium on Circuits and Systems
Volume
6
Document Type
Article
Personal Identifier
scopus
Copyright Status
Unknown
Socpus ID
17444450599 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/17444450599
STARS Citation
Scanlon, James and Deo, Narsingh, "Graph-Theoretic Algorithms For Image Segmentation" (1999). Scopus Export 1990s. 3825.
https://stars.library.ucf.edu/scopus1990/3825