Dead-End Elimination as a Heuristic
for Min-Cut Image Segmentation

Mala L. Radhakrishnan Sara L. Su
MIT Chemistry MIT CSAIL
In Proceedings of ICIP 2006

ABSTRACT

We apply the dead-end elimination (DEE) strategy from protein design as a heuristic for the max-flow/min-cut formulation of the image segmentation problem. DEE combines aspects of constraint propagation and branch-and-bound to eliminate solutions incompatible with global optimization of the objective function. Though DEE can be used for segmentation into an arbitrary number of regions, in this paper we evaluate only the case of binary segmentation. We provide a runtime analysis and evaluation of DEE applied to two min-cut algorithms. Preliminary results show that DEE consistently reduces the search space for the Edmonds-Karp algorithm; tuning DEE as a heuristic for Boykov-Kolmogorov and other algorithms is future work.

FILES

Mala L. Radhakrishnan and Sara L. Su. Dead-End Elimination as a Heuristic for Min-Cut Image Segmentation. In Proceedings of the 13th IEEE International Conference on Image Processing, Atlanta, GA, October 2006.

Paper: PDF
Supplement: PDF

@inproceedings{Radhakrishnan:06:DEE,
  author = "Mala L. Radhakrishnan and Sara L. Su",
  title = "Dead-End Elimination as a Heuristic for Min-Cut Image Segmentation",
  booktitle = "Proceedings of the 13th IEEE International Conference on Image Processing",
  location = "Atlanta, Georgia",
  month = "October",
  year = "2006",
}

ACKNOWLEDGEMENTS

Implementation advice from Michael Altman and comments from Vladimir Kolmogorov, Sylvain Paris, and Bruce Tidor helped improve this paper. We thank David Karger for suggesting a simplified interpretation of the heuristic and Frédo Durand for input images. The authors were supported by a DOE CSGF fellowship under grant number DE-FG02-97ER25308 and a National Science Foundation graduate fellowship.