C-MCL Superpixels

Important: Hover over the image mosaic to see the corresponding clusters (the image can take a couple of seconds to appear).


C-MCL Superpixels stands for Compact Markov Cluster Algorithm: it generates homogeneous superpixels using a Markov random walks. We exploit Markov clustering (MCL) as the methodology, a generic graph clustering method based on stochastic flow circulation. In particular, we introduce a new graph pruning strategy called compact pruning in order to capture intrinsic local image structure, and thereby keep the superpixels homogeneous, i.e. uniform in size and compact in shape. Further, this new pruning scheme comes with three advantages: faster computation, smaller memory footprint, and straightforward parallel implementation. Through comparisons with other recent standard techniques, we show that the proposed algorithm achieves good results at a decent computational speed.

In practice, C-MCL produces superpixels similar to Normalized-Cut Superpixels but is around 10 times faster.
If speed is important, we found that the superpixels generated by SLIC are slightly less compact but are otherwise very good in terms of boundary recall and under-segmentation error. They can be computed more than 10 times faster than our method.


You can run C-MCL using the binary provided: mcl_superpixels_binary_2013_05_07.7z
Requirement: Windows7 64bits, NVIDA card with CUDA capability > 2.0.

Publication & patents

Perbet Frank, and Atsuto Maki. "Homogeneous Superpixels from Random Walks." MVA. 2011.
MCLsuperpixels_MVA2011.pdf - Suplementary material

Patent: US20120251003


We ran different algorithms on the The Berkeley Segmentation Dataset:

  • C-MCL: Compact Markov Cluster Algorithm, our algorithm
  • MCL: The original MCL method
  • SLIC
  • Normalized-cut
  • Turbopixels
  • Lattice
  • Quickshift
  • Graph-based

  • All the results can be found here. Be patient, the page can take a while to load due to the number of images.

    You can find further evaluations here.