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

Socpus ID

17444450599 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/17444450599

This document is currently not available here.

Share

COinS