Graph Clustering for Image Segmentation


Graph-based clustering using 4 infections/labels.

Overview

This work focuses on developing supervised graph-based clustering methods by studying graph-diffusion processes. Inspired by the Susceptible-Infected-Recovered (SIR) model in mathematical epidemiology, we develop two new algorithms based on the Random Walker algorithm. The first one is called Normalized Random Walker (NRW) and introduces the nodal degree information in the diffusive scheme hence the steady state of NRW.

The second method is the Normalized Lazy Random Walker (NLRW) that incorporates a free parameter α to express the tendency of nodes to maintain their infection status. Both methods delivered competitive results compared to other methods and can be directly applied to arbitrary graphs (such as the Region Adjacency Graph or a k-nearest neighbor graph), regular 2D grids (pixel-based versions of the NRW and the NLRW) and 3D point clouds.

Steps of our method (left to right): Original image with seeds, NRW graph-based clustering, NRW result converted to a pixel image.

People

Christos Bampis (Univ. of Texas Austin, USA), cbampis@gmail.com
Petros Maragos

Publications

C. Bampis and P. Maragos,
Unifying the random walker algorithm and the SIR model for graph clustering and image segmentation,
Proc. IEEE Int’l Conf. Image Processing (ICIP), Sept. 2015.
C. G. Bampis, P. Maragos and A. C. Bovik,
Graph-Driven Diffusion and Random Walk Schemes for Image Segmentation,
IEEE Transactions on Image Processing, vol. 26, no. 1, pp. 35-50, Jan. 2017.

Software

Architecture
The released implementation is written in Matlab for fast prototyping and research purposes.Usage
The code contains routines for the steady-state solutions of NRW and RW as well as the NRW and RW diffusion schemes.

Dependencies
The released implementation is self-contained. Useful routines from the Graph Analysis Toolbox developed by Grady are also included.

Current Version
The current version (version 2 – December 2016) is an updated version of our earlier software implementation release (version 1 – December 2015). The current implementation contains both the steady state and diffusion-based schemes using NRW, NLRW and RW.
The algorithms behind this software implementation are described in the following paper, which should be cited if you use our code in your published research work:

C. G. Bampis, P. Maragos and A. C. Bovik, Graph-Driven Diffusion and Random Walk Schemes for Image Segmentation, IEEE Transactions on Image Processing, vol. 26, no. 1, pp. 35-50, Jan. 2017.

The earlier implementation release (version 1 – December 2015) was based on our earlier work:

C. Bampis and P. Maragos, Unifying the random walker algorithm and the SIR model for graph clustering and image segmentation,
Proc. IEEE Int’l Conf. Image Processing (ICIP), Sept. 2015.

Author and Contact Information
The author of the code release is Christos Bampis. For any questions/comments feel free to contact Christos Bampis cbampis@gmail.com.

The software can be downloaded here: [download software]