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.
- C. Fowlkes, S. Belongie, F. Chung, J. Malik. "Spectral Grouping Using the Nyström Method",
TPAMI. 26 (2) p.214-225
- S. Belongie, C. Fowlkes, F. Chung, J. Malik.
"Spectral Partitioning with Indefinite Kernels using the Nyström Extension",
ECCV, Copenhagen, (May 2002).
- C. Fowlkes, S. Belongie, J. Malik. "Efficient Spatiotemporal Grouping Using the Nyström Method",
CVPR, Hawaii, (December 2001).