Abstract
After presenting an introduction to a more traditional graph-based 2D segmentation technique, this chapter presents an in-depth overview of two state-of-the-artgraph-based methods for segmenting three-dimensional structures in medical images: graph cuts and the Layered Optimal Graph Image Segmentation of Multiple Objects and Surfaces (LOGISMOS) approach. In each case, an overview of the underlying optimization problem is presented first (i.e., the formulation of an energy/cost function and the specified constraints), followed by the graph-based representation of the optimization problem which enables the globally optimal solution to be found in polynomial time. In particular, in the 2D case, a 2D boundary segmentation optimization problem is transformed into that of finding a minimum-cost path in a graph. In the graph-cuts approach, a 3D object/background labeling problem is transformed into that of finding a minimum s–t cut in a graph, and in the LOGISMOS approach, a single or multiple 3D surface segmentation problem is first transformed into that of finding a minimum-cost closure in a graph (which is further transformed into finding a minimum s–t cut in a graph). For each approach, example applications and extensions are also presented.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Boykov, Y., Jolly, M.-P.: Interactive organ segmentation using graph cuts. In: Medical Image Computing and Computer-Assisted Intervention (MICCAI) 2000. Lecture Notes in Computer Science, vol. 1935, pp. 276–286. Springer, Berlin (2000)
Boykov, Y., Jolly, M.-P.: Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In: IEEE International Conference on Computer Vision (ICCV) 2001, pp. 105–112. IEEE, New York (2001)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1222–1239 (2001)
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26(9), 1124–1137 (2004)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147–159 (2004)
Boykov, Y., Funka-Lea, G.: Graph cuts and efficient N-D image segmentation. Int. J. Comput. Vis. 70(2), 109–131 (2006)
Wu, X., Chen, D.Z.: Optimal net surface problems with applications. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2380, pp. 775–775. Springer, Berlin (2002)
Wu, X., Chen, D.Z., Li, K., Sonk, M.: The layered net surface problems in discrete geometry and medical image segmentation. Int. J. Comput. Geom. Appl. 17(3), 261–296 (2007)
Li, K., Wu, X., Chen, D.Z., Sonka, M.: Optimal surface segmentation in volumetric images—a graph-theoretic approach. IEEE Trans. Pattern Anal. Mach. Intell. 28(1), 119–134 (2006)
Garvin, M.K., Abràmoff, M.D., Wu, X., Russell, S.R., Burns, T.L., Sonka, M.: Automated 3-D intraretinal layer segmentation of macular spectral-domain optical coherence tomography images. IEEE Trans. Med. Imaging 28(9), 1436–1447 (2009)
Yin, Y., Zhang, X., Williams, R., Wu, X., Anderson, D.D., Sonka, M.: LOGISMOS—layered optimal graph image segmentation of multiple objects and surfaces: cartilage segmentation in the knee joint. IEEE Trans. Med. Imaging 29(12), 2023–2037 (2010)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT, Cambridge (2001)
Delong, A., Boykov, Y.: Globally optimal segmentation of multi-region objects. In: International Conference on Computer Vision (ICCV), Tokyo, pp. 285–292 (October 2009)
Song, Q., Bai, J., Han, D., Bhatia, S., Sun, W., Rockey, W., Bayouth, J., Buatti, J., Wu, X.: Optimal co-segmentation of tumor in PET-CT images with context information. IEEE Trans. Med. Imaging 32(9), 1685–1697 (2013)
Mu, Y., Zhou, B.: Co-segmentation of image pairs with quadratic global constraint in MRFs. In: Proceedings of the 8th Asian Conference on Computer Vision, Part II, Tokyo, pp. 837–846 (2007)
Mukherjee, L., Singh, V., Dyer, C.R.: Half-integrality based algorithms for cosegmentation of images. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Miami, pp. 2028–2035 (2009)
Hochbaum, D.S., Singh, V.: An efficient algorithm for co-segmentation. In: Proceedings of the International Conference on Computer Vision, Kyoto, pp. 269–276 (2009)
Rother, C., Minka, T., Bake, A., Kolmogorov, V.: Cosegmentation of image pairs by histogram matching—incorporating a global constraint into MRFs. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, pp. 993–1000 (2006)
Batra, D., Kowdle, A., Parikh, D., Luo, J., Chen, T.: Interactively co-segmentating topically related images with intelligent scribble guidance. Int. J. Comput. Vis. 93(3), 273–292 (2011)
Thedens, D.R., Skorton, D.J., Fleagle, S.R.: A three-dimensional graph searching technique for cardiac border detection in sequential images and its application to magnetic resonance image data. In: Proceedings of Computers in Cardiology, Chicago, pp. 57–60 (1990)
Thedens, D.R., Skorton, D.J., Fleagle, S.R.: Methods of graph searching for border detection in image sequences with applications to cardiac magnetic resonance imaging. IEEE Trans. Med. Imaging 14(1), 42–55 (1995)
Boykov, Y., Veksler, O., Zabih, R.: Markov Random Fields with efficient approximations. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Santa Barbara, pp. 648–655 (1998)
Ishikawa, H., Geiger, D.: Segmentation by grou** junctions. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Santa Barbara, pp. 125–131 (1998)
Greig, D., Porteous, B., Seheult, A.: Exact maximum a posteriori estimation for binary image. J. R. Stat. Soc. Ser. B 51, 271–279 (1989)
Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48(4), 686–701 (2001)
Glocker, B., Komodakis, N., Paragios, N., Glaser, C., Tziritas, G., Navab, N.: Primal/dual linear programming and statistical atlases for cartilage segmentation. In: Ayache, N., Ourselin, S., Maeder, A. (eds.) Medical Image Computing and Computer-Assisted Intervention (MICCAI 2007). Lecture Notes in Computer Science, vol. 4792, pp. 536–543. Springer, Berlin (2007)
Roy, S., Cox, I.: A maximum-flow formulation of the n-camera stereo correspondence problem. In: Proceedings of International Conference on Computer Vision (ICCV), Bombay, pp. 492–499 (1998)
Kolmogorov, V., Zabih, R.: Computing visual correspondence with occlusions using graph cuts. In: Proceedings of International Conference on Computer Vision (ICCV), Vancouver, pp. 508–515, July 2001
Glocker, B., Komodakis, N., Paragios, N., Tziritas, G., Navab, N.: Inter and intra-modal deformable registration: continuous deformations meet efficient optimal linear programming. In: Proceedings of the 20th International Conference on Information Processing in Medical Imaging (IPMI). Lecture Notes in Computer Science, vol. 4584, pp. 408–420. Springer, Berlin (2006)
Kleinberg, J., Tardos, E.: Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, New York City, pp. 14–23 (1999)
Archer, A., Fakcharoenphol, J., Harrelson, C., Krauthgamer, R., Talvar, K., Tardos, E.: Approximate classification via earthmover metrics. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, pp. 1079–1089 (2004)
Chuzhoy, J., Naor, S.: The hardness of metric labeling. SIAM J. Comput. 36(5), 1376–1386 (2007)
Chekuri, C., Khanna, A., Naor, J., Zosin, L.: A linear programming formulation and approximation algorithms for the metric labeling problem. SIAM J. Discrete Math. 18(3), 608–625 (2005)
Gupta, A., Tardos, E.: Constant factor approximation algorithms for a class of classification problem. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), Portland, pp. 652–658 (2000)
Dubes, R., Jain, A.: Random field models in image analysis. J. Appl. Stat. 16, 131–164 (1989)
Picard, J.C.: Maximal closure of a graph and applications to combinatorial problems. Manag. Sci. 22, 1268–1272 (1976)
Song, Q., Bai, J., Garvin, M.K., Sonka, M., Buatti, J., Wu, X.: Optimal multiple surface segmentation with shape and context priors. IEEE Trans. Med. Imaging 32(2), 376–386 (2013)
Ahuja, R.K., Hochbaum, D., Orlin, J.B.: A cut based algorithm for the convex dual of the minimum cost network flow problem. Algorithmica 39, 189–208 (2004)
Kass, M., Witkin, A., Terzopoulos, D.: Snakes: active contour models. Int. J. Comput. Vis. 1(4), 321–331 (1987)
Amini, A.A., Weymouth, T.E., Jain, R.C.: Using dynamic programming for solving variational problems in vision. IEEE Trans. Pattern Anal. Mach. Intell. 12(9), 855–867 (1990)
Amini, A.A., Weymouth, T.E., Jain, R.C.: On active contour models and balloons. CVGIP: Image Underst. 53(2), 211–218 (1991)
Amini, A.A., Weymouth, T.E., Jain, R.C.: A dynamic finite element surface model for segmentation and tracking in multidimensional medical images with application to cardiac 4D image analysis. Comput. Med. Imaging Graph. 19(1), 69–83 (1995)
Caselles, V., Catte, F., Coll, T., Dibos, F.: A geometric model for active contours. Numerische Mathematik 66, 1–31 (1993)
Malladi, R., Sethian, J.A., Vemuri, C.: Shape modeling with front propagation: a level set approach. IEEE Trans. Pattern Anal. Mach. Intell. 17(2), 158–175 (1995)
Osher, S., Paragios, N.: Geometric Level Set Methods in Imaging, Vision, and Graphics. Springer, New York (2003)
Liu, X., Chen, D., Tawhai, M., Wu, X., Hoffman, E., Sonka, M.: Optimal graph search based segmentation of airway tree double surfaces across bifurcations. IEEE Trans. Med. Imaging 32(3), 493–510 (2013)
Liu, X., Chen, D.Z., Wu, X., Sonka, M.: Optimal graph-based segmentation of 3D pulmonary airway and vascular trees across bifurcations. In: First International Workshop on Pulmonary Image Analysis, at the 11th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), New York City, pp. 103–111 (September 2008)
Garvin, M.K., Abràmoff, M.D., Kardon, R., Russell, S.R., Wu, X., Sonka, M.: Intraretinal layer segmentation of macular optical coherence tomography images using optimal 3-D graph search. IEEE Trans. Med. Imaging 27(10), 1495–1505 (2008)
Lee, K., Abràmoff, M.D., Niemeijer, M., Garvin, M.K., Sonka, M.: 3-D segmentation of retinal blood vessels in spectral-domain OCT volumes of the optic nerve head. In: Proceedings of SPIE Medical Imaging 2010: Biomedical Applications in Molecular, Structural, and Functional Imaging, vol. 7626, San Diego, p. 76260V-8. SPIE (2010)
Quellec, G., Lee, K., Dolejsi, M., Garvin, M.K., Abràmoff, M.D., Sonka, M.: Three-dimensional analysis of retinal layer texture: identification of fluid-filled regions in SD-OCT of the macula. IEEE Trans. Med. Imaging 29(6), 1321–1330 (2010)
Lee, K., Niemeijer, M., Garvin, M.K., Kwon, Y.H., Sonka, M., Abràmoff, M.D.: Segmentation of the optic disc in 3-D OCT scans of the optic nerve head. IEEE Trans. Med. Imaging 29(1), 159–168 (2010)
Antony, B.J., Abràmoff, M.D., Lee, K., Sonkova, P., Gupta, P., Kwon, Y., Niemeijer, M., Hu, Z., Garvin, M.K.: Automated 3D segmentation of intraretinal layers from optic nerve head optical coherence tomography images. In: Proceedings of SPIE Medical Imaging 2010: Biomedical Applications in Molecular, Structural, and Functional Imaging, vol. 7626, San Diego, p. 76260U-12. SPIE (2010)
Song, Q., Wu, X., Liu, Y., Smith, M., Buatti, J., Sonka, M.: Optimal graph search segmentation using arc-weighted graph for simultaneous surface detection of bladder and prostate. In: Yang, G.-Z., Hawkes, D., Rueckert, D., Noble, A., Taylor, C. (eds.) Medical Image Computing and Computer-Assisted Intervention—MICCAI 2009. Lecture Notes in Computer Science, vol. 5762, pp. 827–835. Springer, Berlin (2009)
Song, Q., Wu, X., Liu, Y., Sonka, M., Garvin, M.K.: Simultaneous searching of globally optimal interacting surfaces with shape priors. In: 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, pp. 2879–2886 (June 2010)
Song, Q., Liu, Y., Liu, Y., Saha, P., Sonka, M., Wu, X.: Graph search with appearance and shape information for 3-D prostate and bladder segmentation. In: Jiang, T., Navab, N., Pluim, J., Viergever, M. (eds.) Medical Image Computing and Computer-Assisted Intervention—MICCAI 2010. Lecture Notes in Computer Science, vol. 6363, pp. 172–180. Springer, Berlin (2010)
Caselles, V., Kimmel, R., Sapiro, G.: Geodesic active contours. Int. J. Comput. Vis. 22, 61–97 (1997)
Song, Q., Chen, M., Bai, J., Sonka, M., Wu, X.: Surface-Region context in optimal multi-object Graph-Based segmentation: robust delineation of pulmonary tumors. In: Szekely, G., Hahn, H. (eds.) Information Processing in Medical Imaging. Lecture Notes in Computer Science, vol. 6801, pp. 61–72. Springer, Berlin (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Garvin, M.K., Wu, X. (2014). Graph Algorithmic Techniques for Biomedical Image Segmentation. In: Saha, P., Maulik, U., Basu, S. (eds) Advanced Computational Approaches to Biomedical Engineering. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41539-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-41539-5_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41538-8
Online ISBN: 978-3-642-41539-5
eBook Packages: Computer ScienceComputer Science (R0)