AMG-based Fast Multiscale Image Segmentation

Eitan Sharon, Achi Brandt, and Ronen Basri
Dept. of Applied Math
The Weizmann Inst. of Science
Rehovot, 76100, Israel.


We introduce a fast, multiscale algorithm for image segmentation. Our algorithm uses recursive hierarchical coarsening to detect distinctive segments at different scales. The process is derived from algebraic multigrid solvers of minimization problems associated with heat or electric networks. Our algorithm coarsens the image by producing an irregular pyramid in which block nodes represent collections of pixels of arbitrary shapes. During this coarsening process we may compute additional statistics of the emerging segments and use these statistics to facilitate the segmentation process. The execution time of this algorithm is linear in the size of the image with only several dozen operations per pixel. We demonstrate the properties of the algorithm by running it on several line drawings and real images.