Sub-Markov random walk for image segmentation

Xingping Dong, Jianbing Shen, Ling Shao, Luc Van Gool

Research output: Contribution to journalArticlepeer-review

186 Citations (Scopus)
6 Downloads (Pure)


A novel sub-Markov random walk (subRW) algorithm with label prior is proposed for seeded image segmentation, which can be interpreted as a traditional random walker on a graph with added auxiliary nodes. Under this explanation, we unify the proposed subRW and other popular random walk (RW) algorithms. This unifying view will make it possible for transferring intrinsic findings between different RW algorithms, and offer new ideas for designing novel RW algorithms by adding or changing auxiliary nodes. To verify the second benefit, we design a new subRW algorithm with label prior to solve the segmentation problem of objects with thin and elongated parts. The experimental results on both synthetic and natural images with twigs demonstrate that the proposed subRW method outperforms previous RW algorithms for seeded image segmentation.
Original languageEnglish
Pages (from-to)516-527
Number of pages12
JournalIEEE Transactions on Image Processing
Issue number2
Early online date3 Dec 2015
Publication statusPublished - 1 Feb 2016

Cite this