18 — Random walks for image segmentation

In this 2006 paper, Leo Grady poses $n$-dimensional image segmentation as a graph-theory problem, and uses several models to improve performance of conventional watershed segmentation. In particular, he represents an image as a graph where edge-weights are some function $\omega$ on pixel $i$ with intensity $g$. In particular, the paper uses the Gaussian weight function as an example:

This function can be replaced with any other function on pixels (e.g. incorporating color or local texture) as a pre-processing step on the graph.

Once these weights have been computed, “seeds” are placed in the graph (using manual placement). These seeds are then modeled in one of several ways:

Diffusion. The node can be represented as neighboring cells where diffusion takes place according to $\frac{du}{dt} = \nabla^2 u$. Just like diffusion is limited through porous membranes, this analogy makes the resultant segmentation robust to holes in boundaries in the image.

Electric circuit. Combining Kirchoff’s and Ohm’s laws, Grady derives a function to operate as a matrix-wise operation over a dense $n$-dimensional pixel space, essentially modeling each pixel as a nodal point with resistors connecting it to its neighbors.

These equations are combined in a MATLAB package the author freely distributes, but he notes that the operations take place in evaluated-MATLAB rather than compiled C, and are therefore much slower than a theoretical compiled counterpart (a $512\times512$ image takes ~2s to run on state-of-the-art 2006 hardware).

I like this work both because it models image segmentation using processes that mimic nature and because, in today’s climate, non-neural-net approaches to image-segmentation are strangely uncommon to read about.