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.
Perbet Frank, and Atsuto Maki. "Homogeneous Superpixels from Random Walks." MVA. 2011.
MCLsuperpixels_MVA2011.pdf - Suplementary material
We ran different algorithms on the The Berkeley Segmentation Dataset:
You can find further evaluations here.