Random Walks for Image Segmentation

Introduction

This paper presents a novel multi-label and interactive image segmentation algorithm that draws analogies to electric network circuits solutions from electrical engineering. Treating the image as a purely discrete object - a graph, this algorithm can be extended to surface meshes or space-variant images as well. The paper demonstrates the proposed algorithm’s speed and robustness to noise and weak boundaries while also being able to avoid the “small cut” solutions.

Method

Modeling the image as a connected and an undirected graph, $$ G = (V,E) $$ $$\boldsymbol{Vertices:} \ v \ \in V $$ $$\boldsymbol{Edges:} \ e \ \in E \subset V X V$$ $$\boldsymbol{Weights:} \ w(e_{i,j}) = w_{ij}$$ where the degree of the $i^{th}$ vertex is given by $$ d_i = \sum_{j} w(e_{i,j}) $$

The function chosen to represent edge weights typically has to be one which maximizes the entropy of the resulting weights. Using the Gaussian weighting function modified to handle vector valued data, we have $$ w_{ij} = exp (-\beta \left\lVert g_i - g_j\right\rVert^2) $$

The value of $\beta$ has been empirically chosen to be 1.

Using each pixel $p$, $q$ in the image, create the combinatorial Laplacian matrix $L_{pq}$ such that $$ L_{pq} = \begin{cases} d_p, & \text{if}\ p = q \\ -w_{pq}, & \text{if $v_p$ and $v_q$ are adjacent} \\ 0, & \text{otherwise} \end{cases} $$

When the matrix $L$ is constructed, it can be divided into 4 sub-matrices as follows $$ L = \begin{bmatrix} L_M & B \ B^T & L_U \end{bmatrix} $$

where

• $L_M$ represents the Laplacian matrix corresponding to the marked/seeded nodes.

• $B$ represents the relationship of a marked node to an unmarked node.

• $B^T$ is the transpose of the matrix $B$, and represents the relationship of an unmarked node to a marked node.

• $L_U$ represents the Laplacian matrix corresponding to the unmarked nodes.

Also, denoting the probability of label $s$ at node $v_i$ with the function $Q(v_j) = s$, calculate $$ m_j^s = \begin{cases} 1 & \text{if}\ Q(v_j) = s \\ 0, & \text{otherwise} \end{cases} $$

Using these equations, this becomes a combinatorial Dirichlet problem whose solution can be found by solving $$ L_U X = -B^T M $$

Since the probabilities at any node must sum up to one, then the above equation means that only $K-1$ sparse linear systems need to be solved.

Circuit Analogy

This problem can also be formulated as an electrical circuits equivalent. For each seeded point, turn by turn set its potential to be 1V and the other points to be grounded. Then, using circuit theory, the conductances (inverse of resistance, depicting the ease of flow of electric current) of the graph edges can be calculated, and they would have values between 0 and 1, which is also the range of probability values that they can assume. Moreover, the turn-by-turn approach of setting one seed potential to be zero also means that by the principle of superposition from circuit theory, the sum of the potentials must sum to one. The paper also presents a derivation of the above set of equations using Ohm’s Law and Kirchhoff’s Current and Voltage Laws.

Results and Discussion

The only free parameter in the algorithm is $\beta$, which has been chosen to be 1. The segmentation results shown in the paper demonstrate excellent segmentation performance, far superior to the contemporary algorithms.

The paper uses relationships between random walks, combinatorial potential theory, trees, and electric circuits to generate multi-label segmentations in images. The proposed segmentation algorithm is robust to noise, unlike graph cuts and intelligent scissors (which is susceptible to weak boundaries). Moreover, the random walker algorithm also outputs probabilities which can be seen as “confidence” values of the segmentation. The solution is guaranteed to have no isolated regions of a particular label that do not contain a seed point, and the solution for the potentials using the circuit theory analogy is unique.