Spectral grouping using the Nystrom method

Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation. However, due to the computational demands of these approaches, applications to large problems such as spatiotemporal data and high resolution imagery have been slow to appear. The contribution o...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2004-02, Vol.26 (2), p.214-225
Main Authors: Fowlkes, C., Belongie, S., Chung, F., Malik, J.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Cluster Analysis
Computer Graphics
Eigenvalues and eigenfunctions
Graph theory
Histograms
Image Enhancement - methods
Image Interpretation, Computer-Assisted - methods
Image resolution
Image segmentation
Information Storage and Retrieval - methods
Layout
Numerical Analysis, Computer-Assisted
Partitioning algorithms
Pattern Recognition, Automated
Pixel
Prototypes
Reproducibility of Results
Sensitivity and Specificity
Signal Processing, Computer-Assisted
Spatiotemporal phenomena
Subtraction Technique
User-Computer Interface
Video Recording - methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation. However, due to the computational demands of these approaches, applications to large problems such as spatiotemporal data and high resolution imagery have been slow to appear. The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning making it feasible to apply them to very large grouping problems. Our approach is based on a technique for the numerical solution of eigenfunction problems known as the Nystrom method. This method allows one to extrapolate the complete grouping solution using only a small number of samples. In doing so, we leverage the fact that there are far fewer coherent groups in a scene than pixels.
ISSN:0162-8828
1939-3539
DOI:10.1109/TPAMI.2004.1262185