Isoperimetric graph partitioning for image segmentation

Author

Grady, Leo ; Schwartz, Eric L.

Author_Institution

Dept. of Imaging & Visualization, Siemens Corp. Res., Princeton, NJ, USA

Volume

28

Issue

3

fYear

2006

fDate

3/1/2006 12:00:00 AM

Firstpage

469

Lastpage

475

Abstract

Spectral graph partitioning provides a powerful approach to image segmentation. We introduce an alternate idea that finds partitions with a small isoperimetric constant, requiring solution to a linear system rather than an eigenvector problem. This approach produces the high quality segmentations of spectral methods, but with improved speed and stability.

Keywords

graph theory; image segmentation; linear systems; high quality segmentations; image segmentation; isoperimetric constant; isoperimetric graph partitioning; linear system; spectral graph partitioning; spectral methods; Application software; Computer architecture; Computer vision; Equations; Graph theory; Image representation; Image segmentation; Linear systems; Partitioning algorithms; Stability; Index Terms- Graph-theoretic methods; algorithms; applications.; computer vision; graph algorithms; graphs and networks; image representation; special architectures; Algorithms; Artificial Intelligence; Computer Graphics; Image Enhancement; Image Interpretation, Computer-Assisted; Information Storage and Retrieval; Pattern Recognition, Automated; Reproducibility of Results; Sensitivity and Specificity; Subtraction Technique;

fLanguage

English

Journal_Title

Pattern Analysis and Machine Intelligence, IEEE Transactions on

Publisher

ieee

ISSN

0162-8828

Type

jour

DOI

10.1109/TPAMI.2006.57

Filename

1580491