This software implements the hierarchical image segmentation method presented in a sequence of papers by Sharon et al. and Galun et al (see references below). Please note that the method and the software provided here are patented in (Brandt, Sharon and Basri) and may be used for research proposes only. If you use this software please provide a proper citation according to the details at the bottom of this page.

This fast, multiscale segmentation algorithm is inspired by Algebraic MultiGrid techniques (developed as fast PDE solvers with unstructured grids, see Brandt, McCormick and Ruge). The algorithm returns a full hierarchy of segments in time that is linear in the number of pixels in the image. It constructs a pyramid of graphs, which adaptively represents aggregates of pixels of similar properties. At fine levels these aggregates represent regions of homogenous intensities. At coarser levels the aggregates represent coherent regions of more complex properties (such as intensity variations at various scales and various texture measures). In this pyramid, aggregates at fine levels may belong to several larger aggregates, at coarser scales, with different weights. This weighted aggregation allows the algorithm, to avoid local, pre-mature decisions. As a result of this process segments that are distinct from their surroundings emerge as salient nodes at some level of the pyramid.

The pyramid is constructed from fine (bottom) to coarse (top). During the construction of the pyramid we collect statistics of the aggregates that include shape, intensity variability, and filter responses and use these statistics to characterize the texture in the respective regions. We use these coarse scale measurements to influence the construction of higher levels in the pyramid. This allows us to effectively handle texture. Top-down sweeps are applied to better separate the segments and to clean undesired filter responses along the boundaries of regions. These operations lead to state-of-the-art segmentation results on challenging images. The pyramid so constructed provides a rich, multiscale representation of the image. It makes explicit the salient segments in the image at all levels, and provides a description of their shape, intensity, and texture.

References:

Achi Brandt, Eitan Sharon, and Ronen Basri, "Method and Apparatus for Data Clustering Including Segmentation and Boundary Detection", U.S. Patent and Trademark Office Application No. PCT/US01/43991, July, 2003, assigned to Yeda Research and Development Co., Ltd., Nov. 2000.

Eitan Sharon, Meirav Galun, Dahlia Sharon, Ronen Basri, and Achi Brandt, "Hierarchy and adaptivity in segmenting visual scenes," Nature, Vol. 442(7104): 719-846, 2006.

Meirav Galun, Eitan Sharon, Ronen Basri, and Achi Brandt, "Texture segmentation by multiscale aggregation of filter responses and shape elements", IEEE International Conference on Computer Vision (ICCV), Vol. I: 716-723, 2003.

Eitan Sharon, Achi Brandt, and Ronen Basri, "Fast multiscale image segmentation," IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Vol. I: 70-77, 2000.

Eitan Sharon, Achi Brandt, and Ronen Basri, "Segmentation and boundary detection using multiscale intensity measurements," IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2001.


Citation:

@article{sharon06Hierarchy,
   author = {Sharon, Eitan and Galun, Meirav and Sharon, Dahlia and Basri, Ronen and Brandt, Achi },
  issn = {0028-0836},
  journal = {Nature},
  month = {June},
  number = {7104},
  pages = {719-846},
  publisher = {Nature Publishing Group},
  title = {Hierarchy and adaptivity in segmenting visual scenes},
  volume = {442},
  year = {2006}
  }