# 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:

http://www.cns.bu.edu/~lgrady/

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:

http://www.cns.bu.edu/~lgrady/