February Fourier Talks 2008

A general purpose image segmentation algorithm using analytically evaluated random walks

An ideal image segmentation algorithm could be applied equally to the problem of isolating organs in a medical acquisition volume or to editing a digital photograph without modifying the algorithm, changing parameters, or sacrificing segmentation quality. However, a general-purpose, multiway segmentation of objects in an image/volume remains a challenging problem. In this talk, I will describe a recently developed approach to this problem that inputs a few training points from a user (e.g., from mouse clicks) and produces a segmentation by computing the probabilities that a random walker leaving unlabeled pixels/voxels will first strike the training set. By exact mathematical equivalence with a combinatorial Laplace equation, these probabilities may be computed analytically and deterministically. The algorithm is developed on an arbitrary, weighted, graph in order to maximize the breadth of application. I will illustrate the use of this approach with examples from several image segmentation problems (without modifying the algorithm or the single free parameter), compare this algorithm to other approaches and discuss the theoretical properties that describe its behavior.