Homogeneous Superpixels from Markov Random Walks

Frank PERBET  Bjorn STENGER  Atsuto MAKI 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E95-D  No.7  pp.1740-1748
Publication Date: 2012/07/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Machine Vision and its Applications)
Category: Segmentation
Keyword: 
superpixels,  Markov clustering,  compact pruning,  sparse matrix computation, 

Full Text: PDF(15.2MB)

Summary: 
This paper presents a novel algorithm to generate homogeneous superpixels from 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 graph pruning strategy called compact pruning in order to capture intrinsic local image structure. The resulting superpixels are homogeneous, i.e. uniform in size and compact in shape. The original MCL algorithm does not scale well to a graph of an image due to the square computation of the Markov matrix which is necessary for circulating the flow. The proposed pruning scheme has the advantages of faster computation, smaller memory footprint, and straightforward parallel implementation. Through comparisons with other recent techniques, we show that the proposed algorithm achieves state-of-the-art performance.