Fast multiscale image segmentation

Abstract

We introduce a fast, multiscale algorithm for image segmentation Our algorithm uses modern numeric techniques to nd an approximate solution to normal - ized cut measures in time that is linear in the size of the image with only a few dozen operations per pixel In just one pass the algorithm provides a complete hi - erarchical decomposition of the image into segments The algorithm detects the segments by applying a pro - cess of recursive coarsening in which the same mini - mization problem is represented with fewer and fewer variables producing an irregular pyramid During this coarsening process we may compute additional inter - nal statistics of the emerging segments and use these statistics to facilitate the segmentation process Once the pyramid is completed it is scanned from the top down to associate pixels close to the boundaries of seg - ments with the appropriate segment The algorithm is inspired by algebraic multigrid (AMG) solvers of min - imization problems of heat or electric networks We demonstrate the algorithm by applying it to real im - ages