Random Walks for Image Segmentation Random Walks for Image Segmentation
Paper summary Image segmentation have been a topic of research in computer vision domain for decades. There have been a multitude of methods proposed for segmentation, but most have been dependent on a high level user input which guides the contour or boundaries towards the real boundaries. In order to come close to a fully automated or partially automated solution, a novel method is proposed for performing multilabel, interactive image segmentation using Random Walk algorithm as the fundamental driver of segmentation. The problem is formulated as follows: given a small number of pixels with user-defined (or pre-defined) labels, assign the the probability that a random walker starting at each unlabeled pixel will first reach one of the pre-labeled pixels. The current pixel is then assigned the label corresponding to the max of this probability. This leads to high-quality segmentations of an image into $K$ different components. The algorithm is based on image graphs, where image pixels are represented as graphs connected by edges to its 8-connected neighbours. In this paper, a novel approach to $K$-class image segmentation problem is proposed which utilizes user-defined seeds representing the example regions of the image belonging to $K$ objects. Each seed specifies a location with a user-defined label. The algorithm labels an unseeded pixel by resolving the question: Given a random walker starting at this location, what is the probability that it first reaches each of the K seed points? It will be shown that this calculation may be performed exactly without the simulation of a random walk. By performing this calculation, the algorithm assigns a K-tuple vector to each pixel that specifies the probability that a random walker starting from each unseeded pixel will first reach each of the K seed points. A final segmentation may be derived from these K-tuples by selecting for each pixel the most probable seed destination for a random walker. The graph weights are determined to be a function of the pixel intensities, specifically $w_{ij}$ = $exp(-(g_i - g_j)^2)$. The algorithm works by biasing the random walker to avoid crossing sharp intensity gradients, which leads to a quality segmentation that respects object boundaries (including weak boundaries). The algorithm exposes only one free variable $\beta$, and can be combined with other approaches involving pre- and post-filtering techniques. Additionally, the algorithm provides on-the-fly correction of previous detected boundary in an computationally efficient way.

ShortScience.org allows researchers to publish paper summaries that are voted on and ranked!

Sponsored by: and