Image segmentation in GraphLab

I got the following question from Doug Epps:

Hi,

I'm interested in implementing "Random Walks for Image Segmentation" (Leo Grady) using graphlab. The author posts a matlab implementation, and I've ported that to python happily. But I'm interested in doing it for large graphs.

Do you have any pointers on how to implement random-walks in graphlab ? I've looked a bit at the linear solver docs and they seem more how to run matlab/graphlab together, rather than how to code a linear solver in the package.

Graphlab looks very well done, thanks for making a great library avail.

-doug

Doug also supplied me a link for this paper's matlab code.

I briefly read the mentioned paper, and it seems that the image segmentation is represented as a
linear system. You may ask what is the relation between a linear system and random-walks?
A good overview of this relation is given by Doyle and Snell in their seminal paper: Random Walks and Electrical Networks.

To verify this i have also taken a look at the attached Matlab code. The Matlab code requires Graph Analysis Toolbox. And indeed the Matlab code solves a 2D Dirichlet equations using a linear system solver. (Specific solver function is called dirichletboundary).

Regarding the specific application at hand, it seems like a pretty cool application so I thought to give some more details about it. In a nutshell, the paper proposes to perform segmentation as follows.
Few seeds or cluster heads are manually selected by the user. Each seed is the starting node of a random walk. The image is segmented by the result of the random walk - each pixel is assigned to the seed which will most likely get to it using a random walk on the image graph.

The figures below are created using Leo Grady's Matlab demo code. The first image is the original picture, where the green point marks the foreground color in the area we want to segment and the blue point is marks the background color. (Total of two segments).

The second image shows the computed answer. The black pixels are more likely
to be reached from the foreground seed.

The third image shows the boundary between the segments:

Random walk probabilities:

And now back to GraphLab: GraphLab has three implemented iterative solvers: Gaussian BP, Jacobi and Conjugate Gradient. The simplest way to operate those solvers is to create a text file in sparse matrix market format. My suggestion is to first create the linear system in Matlab and export it to sparse matrix market using the mmwrite.m script. First verify that the iterative solvers are working in the desired accuracy on smaller images.  After everything is working satisfactory, then it is also possible to prepare all the problem in GraphLab. If you are working in Python you can try our Java/Jython interface to GraphLab.