Homogeneous Superpixels from Markov Random Walks
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E95-D No.7 pp.1740-1748
- Publication Date
- 2012/07/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E95.D.1740
- Type of Manuscript
- Special Section PAPER (Special Section on Machine Vision and its Applications)
- Category
- Segmentation
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Frank PERBET, Bjorn STENGER, Atsuto MAKI, "Homogeneous Superpixels from Markov Random Walks" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 7, pp. 1740-1748, July 2012, doi: 10.1587/transinf.E95.D.1740.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.1740/_p
Copy
@ARTICLE{e95-d_7_1740,
author={Frank PERBET, Bjorn STENGER, Atsuto MAKI, },
journal={IEICE TRANSACTIONS on Information},
title={Homogeneous Superpixels from Markov Random Walks},
year={2012},
volume={E95-D},
number={7},
pages={1740-1748},
abstract={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.},
keywords={},
doi={10.1587/transinf.E95.D.1740},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Homogeneous Superpixels from Markov Random Walks
T2 - IEICE TRANSACTIONS on Information
SP - 1740
EP - 1748
AU - Frank PERBET
AU - Bjorn STENGER
AU - Atsuto MAKI
PY - 2012
DO - 10.1587/transinf.E95.D.1740
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2012
AB - 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.
ER -
English
