A multilevel banded graph cuts method for fast image segmentation
Authors:
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (15505499) , 259-265 Vol. 1
Abstract
In the short time since publication of Boykov and Jolly's seminal paper [2001], graph cuts have become well established as a leading method in 2D and 3D semi-automated image segmentation. Although this approach is computationally feasible for many tasks, the memory overhead and supralinear time complexity of leading algorithms results in an excessive computational burden for high-resolution data. In this paper, we introduce a multilevel banded heuristic for computation of graph cuts that is motivated by the well-known narrow band algorithm in level set computation. We perform a number of numerical experiments to show that this heuristic drastically reduces both the running time and the memory consumption of graph cuts while producing nearly the same segmentation result as the conventional graph cuts. Additionally, we are able to characterize the type of segmentation target for which our multilevel banded heuristic yields different results from the conventional graph cuts. The proposed method has been applied to both 2D and 3D images with promising results.Keywords
This publication has 12 references indexed in Scilit:
- Multigrid and multi-level swendsen-wang cuts for hierarchic graph partition2004
- Lazy snapping2004
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images2002
- Multilevelk-way Partitioning Scheme for Irregular GraphsJournal of Parallel and Distributed Computing, 1998
- Multiresolution Gauss-Markov random field models for texture segmentationIEEE Transactions on Image Processing, 1997
- Restriction of a Markov random field on a graph and multiresolution statistical image modelingIEEE Transactions on Information Theory, 1996
- A Fast Level Set Method for Propagating InterfacesJournal of Computational Physics, 1995
- Digital topology: Introduction and surveyComputer Vision, Graphics, and Image Processing, 1989
- A renormalization group approach to image processing problemsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1989