Some New Results on Optimality and Complexity of PDE-Based Segmentation Algorithms

Thursday, October 19, 2000 - 2:00pm - 2:40pm
Keller 3-180
Ilya Pollak (Purdue University)
We will present a very simple nonlinear diffusion equation and show its utility for image segmentation. We will show that it may be interpreted both as a variant of the Perona-Malik equation, and as the steepest descent equation for the total variation. Its analysis in 1-D will reveal it to be an exact solver of certain maximum likelihood detection/estimation problems. The major advantage over other methods to solve these problems is O(N log N) computational complexity in one spatial dimension. Finally, we will show our method to be a robust estimator (in the spirit of H-infinity estimation) for a restricted class of 1-D problems. Experiments suggest that the 2-D version of our algorithm retains robustness properties of the 1-D version. A remaining challenge is to extend our 1-D theoretical results to 2-D, designing fast and optimal image segmentation algorithms.