Unifying the random walker algorithm and the SIR model for graph clustering and image segmentation

In this paper, we explore the image segmentation task using a graph clustering approach. We formulate this clustering as a diffusion scheme whose steady state is determined by the Random Walker (RW) method. Then, we discover the equivalence of this diffusion with the Susceptible - Infected - Recovered (SIR) model, a well-studied epidemic propagation model. We further argue that using a Region Adjacency Graph (RAG) exploits the clustering properties and leads to a dimensionality reduction. Finally, we propose a novel method called Normalized Random Walker (NRW) algorithm which extends the RW method. Qualitative and quantitative experiments validate the efficiency and robustness of our method, with respect to parameter tuning, seed quality and location.