title: Spectral grouping using the Nyström method.
abstract: 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 Nyström 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.
authors.affiliation: Electrical Engineering and Computer Science Division, University of California at Berkeley, Berkeley, CA 94720, USA. fowlkes@cs.berkeley.edu
authors.forename: Charless
authors.initials: C
authors.lastname: Fowlkes
authors.forename: Serge
authors.initials: S
authors.lastname: Belongie
authors.forename: Fan
authors.initials: F
authors.lastname: Chung
authors.forename: Jitendra
authors.initials: J
authors.lastname: Malik
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003196:Computer Graphics; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012815:Signal Processing, Computer-Assisted; D013382:Subtraction Technique; D014584:User-Computer Interface; D014741:Video Recording / Q000379:methods