Skip navigation.

UCSD Computer Vision

Spectral Clustering Using the Nyström Extension

Serge Belongie


Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation. However, due to the computational demands of such methods, applications to large problems such as spatiotemporal data and high resolution imagery have been slow to appear. The contribution of this work 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 extrapolation of the complete grouping solution using only a small number of ``typical'' samples. In doing so, we successfully exploit the fact that there are far fewer coherent groups in an scene than pixels.

More info on:

Non UCSD Vision People also Involved

Charless Fowlkes

Fan Chung

Jitendra Malik

Related Publications

Fowlkes C., Belongie S., Chung F., Malik J., "Spectral Grouping Using the Nyström Method", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 214-225, Feburary, 2004. [BibTex][pdf]
Belongie S., Fowlkes C., Chung F R K., Malik J., "Spectral Partitioning with Indefinite Kernels using the Nyström Extension", ECCV, Copenhagen, Denmark, Springer Verlag, 2002. [BibTex][pdf]
Fowlkes C., Belongie S., Malik J., "Efficient Spatiotemporal Grouping Using the Nyström Method", CVPR, December, 2001. [BibTex][pdf]