TY - GEN
T1 - A multilevel banded graph cuts method for fast image segmentation
AU - Lombaert, Herve
AU - Sun, Yiyong
AU - Grady, Leo
AU - Xu, Chenyang
PY - 2005
Y1 - 2005
N2 - In the short time since publication of Boykov and Jolly's seminal paper [3], 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 will yield different results from the conventional graph cuts. The proposed method has been applied to both 2D and 3D images with promising results.
AB - In the short time since publication of Boykov and Jolly's seminal paper [3], 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 will yield different results from the conventional graph cuts. The proposed method has been applied to both 2D and 3D images with promising results.
UR - https://www.scopus.com/pages/publications/33745155997
U2 - 10.1109/ICCV.2005.13
DO - 10.1109/ICCV.2005.13
M3 - Contribution to conference proceedings
AN - SCOPUS:33745155997
SN - 076952334X
SN - 9780769523347
T3 - Proceedings of the IEEE International Conference on Computer Vision
SP - 259
EP - 265
BT - Proceedings - 10th IEEE International Conference on Computer Vision, ICCV 2005
T2 - Proceedings - 10th IEEE International Conference on Computer Vision, ICCV 2005
Y2 - 17 October 2005 through 20 October 2005
ER -