Introduction to the Random Walker Algorithm: Graph-Theoretic Electrical Potentials for Multi-Label Medical Image Segmentation

In the seminal paper "Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials" by Leo Grady and Gareth Funka-Lea, the random walker algorithm was formally introduced. This work was presented at the 8th ECCV04 Workshop on Computer Vision Approaches to Medical Image Analysis and Mathematical Methods in Biomedical Image Analysis, held in Prague, Czech Republic on May 15th, 2004. Published by Springer-Verlag, the full paper is accessible via: [http://cns.bu.edu/~lgrady/grady2004multilabel.pdf](http://cns.bu.edu/~lgrady/grady2004multilabel.pdf). The algorithm operates by constructing a weighted graph where image pixels correspond to nodes, with edge weights typically based on intensity gradients. Users specify seed points for different labels, and the solution computes the probability that a random walker starting at each unlabeled pixel first reaches a particular seed. This probability calculation reduces to solving a Laplace equation with Dirichlet boundary conditions at seed points, implemented efficiently using sparse linear algebra solvers like Conjugate Gradient methods. The approach demonstrates robustness to noise and weak boundaries by leveraging global graph connectivity rather than local gradients alone.