Abstract
Image segmentation can be elegantly solved by optimum-path forest and minimum cut in graph. Given that both approaches exploit similar image graphs, some comparative analysis is expected between them. We clarify their differences and provide their comparative analysis from the theoretical point of view, for the case of binary segmentation (object/background) in which hard constraints (seeds) are provided interactively. Particularly, we formally prove that some optimum-path forest methods from two distinct region-based segmentation paradigms, with internal and external seeds and with only internal seeds, indeed minimize some graph-cut measures. This leads to a proof of the necessary conditions under which the optimum-path forest algorithm and the min-cut/max-flow algorithm produce exactly the same segmentation result, allowing a comparative analysis between them.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Allène, C., Audibert, J.Y., Couprie, M., Cousty, J., Keriven, R.: Some links between min-cuts, optimal spanning forests and watersheds. In: Mathematical Morphology and its Applications to Signal and Image Processing (ISMM), pp. 253–264. MCT/INPE (2007)
Audigier, R., Lotufo, R.A.: The tie-zone watershed: Definition, algorithm and applications. In: Proceedings of IEEE International Conference on Image Processing (ICIP 05), pp. 654–657 (2005)
Audigier, R., Lotufo, R.A.: Watershed by image foresting transform, tie-zone, and theoretical relationships with other watershed definitions. In: Proc. of the 8th Intl. Symposium on Mathematical Morphology (ISMMâ07), pp. 277–288 (2007)
Audigier, R., Lotufo, R.A.: Seed-relative segmentation robustness of watershed and fuzzy connectedness approaches. In: XX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), pp. 61–68. Belo Horizonte, MG Oct 2007. IEEE CPS
Bai, X., Sapiro, G.: Distance cut: interactive segmentation and matting of images and videos. In: IEEE Intl. Conf. on Image Processing (ICIP), vol. 2, pp. 249–252. San Antonio, Texas (2007)
Bergo, F.P.G., Falcão, A.X., Miranda, P.A.V., Rocha, L.M.: Automatic image segmentation by tree pruning. J. Math. Imaging Vis. 29(2–3), 141–162 (2007)
Beucher, S., Meyer, F.: The morphological approach to segmentation: The watershed transformation. In: Mathematical Morphology in Image Processing, pp. 433–481. Dekker, New York (1993). Chap. 12
Boykov, Y., Funka-Lea, G.: Graph cuts and efficient N-D image segmentation. Int. J. Comput. Vis. 70(2), 109–131 (2006)
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)
Boykov, Y.Y., Jolly, M.-P.: Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In: International Conference on Computer Vision (ICCV), vol. 1, pp. 105–112 (2001)
Carballido-Gamio, J., Belongie, S.J., Majumdar, S.: Normalized cuts in 3D for spinal MRI segmentation. IEEE Trans. Med. Imag. 23(1), 36–44 (2004)
Ciesielski, K.C., Udupa, J.K.: Affinity functions: recognizing essential parameters in fuzzy connectedness based image segmentation. In: Proc. of SPIE on Medical Imaging: Image Processing, vol. 7259 (2009)
Ciesielski, K.C., Udupa, J.K., Saha, P.K., Zhuge, Y.: Iterative relative fuzzy connectedness for multiple objects with multiple seeds. Comput. Vis. Image Underst. 107(3), 160–182 (2007)
Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watersheds, minimum spanning forests, and the drop of water principle. Technical Report IGM2007-01, Université de Marne-la-Vallée (2007)
Cox, I.J., Rao, S.B., Zhong, Y.: Ratio regions: a technique for image segmentation. In: Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 557–564 (1996)
Falcão, A.X., Bergo, F.P.G.: Interactive volume segmentation with differential image foresting transforms. IEEE Trans. Med. Imag. 23(9), 1100–1108 (2004)
Falcão, A.X., Udupa, J.K., Miyazawa, F.K.: An ultra-fast user-steered image segmentation paradigm: Live-wire-on-the-fly. IEEE Trans. Med. Imag. 19(1), 55–62 (2000)
Falcão, A.X., da Cunha, B.S., Lotufo, R.A.: Design of connected operators using the image foresting transform. In: Proc. of SPIE on Medical Imaging, vol. 4322, pp. 468–479 (Feb 2001)
Falcão, A.X., Costa, L.F., da Cunha, B.S.: Multiscale skeletons by image foresting transform and its applications to neuromorphometry. Pattern Recogn. 35(7), 1571–1582 (2002)
Falcão, A.X., Bergo, F.P.G., Miranda, P.A.V.: Image segmentation by tree pruning. In: XVII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), pp. 65–71. IEEE Press, New York (2004)
Falcão, A.X., Stolfi, J., Lotufo, R.A.: The image foresting transform: Theory, algorithms, and applications. IEEE Trans. Pattern Anal. Mach. Intell. 26(1), 19–29 (2004)
Falcão, A.X., Miranda, P.A.V., Rocha, A.: A linear-time approach for image segmentation using graph-cut measures. In: 8th Intl. Conf. on Advanced Concepts for Intelligent Vision Systems (ACIVS), LNCS, vol. 4179, pp. 138–149. Antwerp, Belgium, Springer, Berlin (2006)
Ford, L., Fulkerson, D.: Flows in Networks. Princeton University Press, Princeton (1962)
Fowlkes, C., Belongie, S., Malik, J.: Efficient spatiotemporal grouping using the Nyström method. In: Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 231–238 (2001)
Grau, V., Mewes, A.U.J., Alcaniz, M., Kikinis, R., Warfield, S.K.: Improved watershed transform for medical image segmentation using prior information. IEEE Trans. Med. Imag. 23(4), 447–458 (2004)
Herman, G.T., Carvalho, B.M.: Multiseeded segmentation using fuzzy connectedness. IEEE Trans. Pattern Anal. Mach. Intell. 23(5), 460–474 (2001)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147–159 (2004)
Lei, T., Udupa, J.K., Saha, P.K., Odhner, D.: Artery-vein separation via MRA—An image processing approach. IEEE Trans. Med. Imag. 20(8) (2001)
Liang, L., Rehm, K., Woods, R.P., Rottenberg, D.A.: Automatic segmentation of left and right cerebral hemispheres from MRI brain volumes using the graph cuts algorithm. NeuroImage 34(3), 1160–1170 (2007)
Lotufo, R.A., Falcão, A.X.: The ordered queue and the optimality of the watershed approaches. In: Mathematical Morphology and its Applications to Image and Signal Processing. vol. 18, pp. 341–350. Kluwer Academic, Dordrecht (2000)
Miranda, P.A.V., Falcão, A.X., Rocha, A., Bergo, F.P.G.: Object delineation by κ-connected components. EURASIP J. Adv. Signal Process. 2008, 467928 (2008). doi:10.1155/2008/467928
Miranda, P.A.V., Falcão, A.X., Udupa, J.K.: CLOUDS: A model for synergistic image segmentation. In: Proc. of the 5th IEEE Intl. Symp. on Biomedical Imaging: From Nano to Macro (ISBI), pp. 209–212. Paris, France, May 14–17th, 2008
Miranda, P.A.V., Falcão, A.X., Udupa, J.K.: Synergistic arc-weight estimation for interactive image segmentation using graphs. Technical Report IC-08-21, Institute of Computing, University of Campinas (Sep 2008)
Moonis, G., Liu, J., Udupa, J.K., Hackney, D.B.: Estimation of tumor volume with fuzzy-connectedness segmentation of MR images. Am. J. Neuroradiol. 23, 356–363 (2002)
Nguyen, H.T., Worring, M., van den Boomgaard, R.: Watersnakes: energy-driven watershed segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 25(3), 330–342 (2003)
Protiere, A., Sapiro, G.: Interactive image segmentation via adaptive weighted distances. IEEE Trans. Image Process. 16(4), 1046–1057 (2007)
Roerdink, J.B.T.M., Meijster, A.: The watershed transform: Definitions, algorithms and parallelization strategies. Fundam. Inform. 41, 187–228 (2000)
Sá, A.M., Vieira, M.B., Montenegro, A.A., Carvalho, P.C.P., Velho, L.: Actively illuminated objects using graph-cuts. In: XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), pp. 45–52. IEEE Press, New York (2006)
Saha, P.K., Udupa, J.K.: Relative fuzzy connectedness among multiple objects: theory, algorithms, and applications in image segmentation. Comput. Vis. Image Underst. 82, 42–56 (2001)
Sarkar, S., Boyer, K.L.: Quantitative measures of change based on feature organization: eigenvalues and eigenvectors. In: Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 478–483 (1996)
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888–905 (2000)
Tsai, Y.P., Lai, C.C., Hung, Y.P., Shih, Z.C.: A Bayesian approach to video object segmentation via merging 3-D watershed volumes. IEEE Trans. Circuits Syst. Video Technol. 15(1), 175–180 (2005)
Udupa, J.K., Samarasekera, S.: Fuzzy connectedness and object definition: theory, algorithms, and applications in image segmentation. Graph. Models Image Process. 58, 246–261 (1996)
Udupa, J.K., Saha, P.K.: Fuzzy connectedness and image segmentation. Proc. IEEE 91(10), 1649–1669 (2003)
Udupa, J.K., Saha, P.K., Lotufo, R.A.: Relative fuzzy connectedness and object definition: Theory, algorithms, and applications in image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 24, 1485–1500 (2002)
Vicente, S., Kolmogorov, V., Rother, C.: Graph cut based image segmentation with connectivity priors. In: Computer Vision and Pattern Recognition, pp. 1–8, Jun 2008
Viola, P., Jones, M.: Rapid object detection using a boosted cascade of simple features. In: International Conference on Computer Vision and Pattern Recognition (CVPR), vol. 1, pp. 511–518 (2001)
Wang, S., Siskind, J.M.: Image segmentation with minimum mean cut. In: International Conference on Computer Vision (ICCV), vol. 1, pp. 517–525, Jul 2001
Wang, S., Sinkind, J.M.: Image segmentation with ratio cut. IEEE Trans. Pattern Anal. Mach. Intell. 25(6), 675–690 (2003)
Wu, Z., Leahy, R.: An optimal graph theoretic approach to data clustering: theory and its applications to image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 15(11), 1101–1113 (1993)
Zheng, D., Zhao, Y., Wang, J.: An efficient method of license plate location. Pattern Recogn. Lett. 26(15), 2431–2438 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Miranda, P.A.V., Falcão, A.X. Links Between Image Segmentation Based on Optimum-Path Forest and Minimum Cut in Graph. J Math Imaging Vis 35, 128–142 (2009). https://doi.org/10.1007/s10851-009-0159-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-009-0159-9