A General Purpose Segmentation Algorithm Using Analytically Evaluated Random Walks

Friday, February 24, 2006 - 1:25pm - 2:25pm
Leo Grady (Siemens AG)
An ideal segmentation algorithm could be applied equally to the problem of
isolating organs in a medical volume or to editing a digital photograph
without modifying the algorithm, changing parameters, or sacrificing
segmentation quality. However, a general-purpose, multilabel 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 problem from potential theory,
these probabilities may be computed analytically and deterministically.
The algorithm is developed on an arbitrary, weighted, graph in order to
maximize the broadness of application. I will illustrate the use of this
approach with examples from several segmentation problems (without
modifying the algorithm or the single free parameter), compare the
behavior of the algorithm to other approaches and discuss the theoretical
properties that describe its behavior. Time permitting, new results on a
solution to the combinatorial Plateau problem on a weighted complex will
also be given, with application to 3D image segmentation.

More information on this research may be found online at: