×

Fuzzy connectedness image segmentation in graph cut formulation: a linear-time algorithm and a comparative analysis. (English) Zbl 1255.68222

Summary: A deep theoretical analysis of the graph cut image segmentation framework presented in this paper simultaneously translates into important contributions in several directions.
The most important practical contribution of this work is a full theoretical description, and implementation, of a novel powerful segmentation algorithm, \(\text{GC}_{\text{max}}\). The output of \(\text{GC}_{\text{max}}\) coincides with a version of a segmentation algorithm known as iterative relative fuzzy connectedness, IRFC. However, \(\text{GC}_{\text{max}}\) is considerably faster than the classic IRFC algorithm, which we prove theoretically and show experimentally. Specifically, we prove that, in the worst case scenario, the \(\text{GC}_{\text{max}}\) algorithm runs in linear time with respect to the variable \(M=|C|+|Z|\), where \(|C|\) is the image scene size and \(|Z|\) is the size of the allowable range, \(Z\), of the associated weight/affinity function. For most implementations, \(Z\) is identical to the set of allowable image intensity values, and its size can be treated as small with respect to \(|C|\), meaning that \(O(M)=O(|C|)\). In such a situation, \(\text{GC}_{\text{max}}\) runs in linear time with respect to the image size \(|C|\).
We show that the output of \(\text{GC}_{\text{max}}\) constitutes a solution of a graph cut energy minimization problem, in which the energy is defined as the \(\ell_{\infty}\) norm \(\|F_P\|_{\infty}\) of the map \(F_P\) that associates, with every element \(e\) from the boundary of an object \(P\), its weight \(w(e)\). This formulation brings IRFC algorithms to the realm of the graph cut energy minimizers, with energy functions \(\|F_P\|_q\) for \(q\in [1,\infty]\). Of these, the best known minimization problem is for the energy \(\|F_P\|_1\), which is solved by the classic min-cut/max-flow algorithm, referred to often as the Graph Cut algorithm.
We notice that a minimization problem for \(\|F_P\|_q\), \(q\in [1,\infty)\), is identical to that for \(\|F_P\|_1\), when the original weight function \(w\) is replaced by \(w^q\). Thus, any algorithm \(\text{GC}_{\text{sum}}\) solving the \(\|F_P\|_1\) minimization problem, solves also one for \(\|F_P\|_q\) with \(q\in [1,\infty)\), so just two algorithms, \(\text{GC}_{\text{sum}}\) and \(\text{GC}_{\text{max}}\), are enough to solve all \(\|F_P\|_q\)-minimization problems. We also show that, for any fixed weight assignment, the solutions of the \(\|F_P\|_q\)-minimization problems converge to a solution of the \(\|F_P\|_{\infty}\)-minimization problem ( \(\|F_P\|_{\infty} =\lim_{q\to\infty} \|F_P\|_q\) is not enough to deduce that). An experimental comparison of the performance of \(\text{GC}_{\text{max}}\) and \(\text{GC}_{\text{sum}}\) algorithms is included. This concentrates on comparing the actual (as opposed to provable worst scenario) algorithms’ running time, as well as the influence of the choice of the seeds on the output.

MSC:

68U10 Computing methodologies for image processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming

Software:

MAXFLOW
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Audigier, R., Lotufo, R.A.: Duality between the watershed by image foresting transform and the fuzzy connectedness segmentation approaches. In: Proceedings of the 19th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI’06), Manaus (AM), Brazil (2006)
[2] Audigier, R., Lotufo, R.A.: Relationships between some watershed definitions and their tie-zone transforms. Image Vis. Comput. 28, 1472–1482 (2010) · Zbl 05842350 · doi:10.1016/j.imavis.2009.11.002
[3] Bertrand, G.: On topological watersheds. J. Math. Imaging Vis. 22, 2–3 (2005) 217–230
[4] Beucher, S.: The watershed transformation applied to image segmentation. In: 10th Pfefferkorn Conf. Signal and Image Processing in Microscopy and Microanalysis, pp. 299–314 (1992)
[5] Boykov, Y., Funka-Lea, G.: Graph cuts and efficient N-D image segmentation. Int. J. Comput. Vis. 70, 109–131 (2006) · Zbl 05062740 · doi:10.1007/s11263-006-7934-5
[6] Boykov, Y., Jolly, M.: Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In: Proceedings of ICCV, Part I, pp. 105–112 (2001)
[7] Boykov, Y., Kolmogorov, V.: Computing geodesics and minimal surfaces via graph cuts. In: International Conference on Computer Vision, vol. I, pp. 26–33 (2003)
[8] 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, 1124–1137 (2004) · Zbl 05112231 · doi:10.1109/TPAMI.2004.60
[9] Boykov, Y., Veksler, O.: Graph cuts in vision and graphics: Theories and applications. In: Paragios, N., Chen, Y., Faugeras, O. (eds.) Handbook of Mathematical Models in Computer Vision, pp. 79–96. Springer, Berlin (2006)
[10] Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1222–1239 (2001) · doi:10.1109/34.969114
[11] Boykov, Y., Kolmogorov, V., Cremers, D., Delong, A.: An integral solution to surface evolution PDEs via geo-cuts. In: International Conference on Computer Vision, vol. III. LNCS, vol. 3953, pp. 409–422 (2006)
[12] BrainWeb repository. http://mouldy.bic.mni.mcgill.ca/brainweb/anatomic_normal_20.html
[13] Carvalho, B.M., Gau, C.J., Herman, G.T., Kong, Y.T.: Algorithms for fuzzy segmentation. Pattern Anal. Appl. 2, 73–81 (1999) · Zbl 05467201 · doi:10.1007/s100440050016
[14] Carvalho, B.M., Herman, G.T., Kong, Y.T.: Simultaneous fuzzy segmentation of multiple objects. Discrete Appl. Math. 151, 65–77 (2005) · Zbl 1101.68922
[15] Ciesielski, K.C., Udupa, J.K.: Affinity functions in fuzzy connectedness based image segmentation I: Equivalence of affinities. Comput. Vis. Image Underst. 114, 146–154 (2010) · Zbl 05690692 · doi:10.1016/j.cviu.2009.09.006
[16] Ciesielski, K.C., Udupa, J.K.: Affinity functions in fuzzy connectedness based image segmentation II: Defining and recognizing truly novel affinities. Comput. Vis. Image Underst. 114, 155–166 (2010) · Zbl 05690693 · doi:10.1016/j.cviu.2009.09.005
[17] Ciesielski, K.C., Udupa, J.K.: Region-based segmentation: Fuzzy connectedness, graph cut, and other related algorithms. In: Deserno, T.M. (ed.) Biomedical Image Processing, pp. 251–278. Springer, Berlin (2011) · Zbl 1255.94012
[18] Ciesielski, K.C., Udupa, J.K.: A framework for comparing different image segmentation methods and its use in studying equivalences between level set and fuzzy connectedness frameworks. Comput. Vis. Image Underst. 115, 721–734 (2011) · Zbl 06019205 · doi:10.1016/j.cviu.2011.01.003
[19] Ciesielski, K.C., Udupa, J.K., Saha, P.K., Zhuge, Y.: Iterative relative fuzzy connectedness for multiple objects, allowing multiple seeds. Comput. Vis. Image Underst. 107(3), 160–182 (2007) · Zbl 05182841 · doi:10.1016/j.cviu.2006.10.005
[20] Couprie, C., Grady, L., Najman, L., Talbot, H.: Anisotropic diffusion using power watersheds. In: International Conference on Image Processing (ICIP), Sep. 2010, vol. 10, pp. 4153–4156 (2010)
[21] Couprie, C., Grady, L., Najman, L., Talbot, H.: Power watersheds: A unifying graph-based optimization framework. IEEE Trans. Pattern Anal. Mach. Intell. 33(7), 1384–1399 (2011) · doi:10.1109/TPAMI.2010.200
[22] Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: Minimumspanning forests and the drop of water principle. IEEE Trans. Pattern Anal. Mach. Intell. 31(8), 1362–1374 (2009) · doi:10.1109/TPAMI.2008.173
[23] Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: Thinnings, shortest path forests, and topological watersheds. IEEE Trans. Pattern Anal. Mach. Intell. 32(5), 925–939 (2010) · doi:10.1109/TPAMI.2009.71
[24] Falcão, A.X., Udupa, J.K., Miyazawa, F.K.: An ultra-fast user-steered image segementation paradigm: Live-wire-on-the-fly. IEEE Trans. Med. Imaging 19(1), 55–62 (2000) · doi:10.1109/42.832960
[25] 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) · Zbl 05110384 · doi:10.1109/TPAMI.2004.1261076
[26] Fan, X., Yang, J., Cheng, L.: A novel segmentation method for MR brain images based on fuzzy connectedness and FCM. Lect. Notes Comput. Sci. 3613, 505–513 (2005) · doi:10.1007/11539506_64
[27] Herman, G.T., Carvalho, B.M.: Multiseeded segmentation using fuzzy connectedness. IEEE Trans. Pattern Anal. Mach. Intell. 23, 460–474 (2001) · Zbl 05111269 · doi:10.1109/34.922705
[28] 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) · Zbl 05110424 · doi:10.1109/TPAMI.2006.19
[29] 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) · Zbl 1490.68285 · doi:10.1007/s10851-009-0159-9
[30] Miranda, P.A.V., Falcão, A.X., Udupa, J.K.: Cloud bank: A multiple clouds model and its use in MR brain image segmentation. In: Proceedings of the Sixth IEEE International Symposium on Biomedical Imaging from Nano to Macro (ISBI), Boston, pp. 506–509 (2009)
[31] Miranda, P.A.V., Falcão, A.X., Udupa, J.K.: Synergistic arc-weight estimation for interactive image segmentation using graphs. Comput. Vis. Image Underst. 114(1), 85–99 (2010) · Zbl 05690687 · doi:10.1016/j.cviu.2009.08.001
[32] Najman, L.: On the equivalence between hierarchical segmentations and ultrametric watersheds. J. Math. Imaging Vis. 40(3), 231–247 (2011) · Zbl 1255.68258 · doi:10.1007/s10851-011-0259-1
[33] Nyul, L.G., Falcao, A.X., Udupa, J.K.: Fuzzy-connected 3D image segmentation at interactive speeds. Graph. Models Image Process. 64, 259–281 (2003)
[34] Park, J., Keller, J.: Snakes on the watershed. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1201–1205 (2001) · Zbl 05112426 · doi:10.1109/34.954609
[35] Pednekar, A., Kakadiaris, I.A.: Image segmentation based on fuzzy connectedness using dynamic weights. IEEE Trans. Image Process. 15(6), 1555–1562 (2006) · Zbl 05453238 · doi:10.1109/TIP.2006.871165
[36] Rosenfeld, A.: Fuzzy digital topology. Inf. Control 40, 76–87 (1979) · Zbl 0404.68071 · doi:10.1016/S0019-9958(79)90353-X
[37] Rosenfeld, A.: On connectivity properties of grayscale pictures. Pattern Recognit. 16, 47–50 (1983) · doi:10.1016/0031-3203(83)90007-9
[38] Rosenfeld, A.: The fuzzy geometry of image subsets. Pattern Recognit. Lett. 2, 311–317 (1984) · doi:10.1016/0167-8655(84)90018-7
[39] Saha, P.K., Udupa, J.K.: Relative fuzzy connectedness among multiple objects: Theory, algorithms, and applications in image segmentation. Comput. Vis. Image Underst. 82(1), 42–56 (2001) · Zbl 1011.68558 · doi:10.1006/cviu.2000.0902
[40] Saha, P.K., Udupa, J.K.: Iterative relative fuzzy connectedness and object definition: Theory, algorithms, and applications in image segmentation. In: Proceedings of IEEE Workshop on Mathematical Methods in Biomedical Image Analysis, Hilton Head, South Carolina, pp. 28–35 (2002)
[41] Saha, P.K., Udupa, J.K., Odhner, D.: Scale-based fuzzy connectedness image segmentation: Theory, algorithms, and validation. Comput. Vis. Image Underst. 77, 145–174 (2000) · Zbl 05690795 · doi:10.1006/cviu.1999.0813
[42] Shafarenko, L., Petrou, M., Kittler, J.: Automatic watershed segmentation of randomly textured color images. IEEE Trans. Image Process. 6, 1530–1544 (1997) · doi:10.1109/83.641413
[43] Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 888–905 (2000) · Zbl 05111961 · doi:10.1109/34.868688
[44] Sinop, A.K., Grady, L.: A seeded image segmentation frame–work unifying graph cuts and random walker which yields a new algorithm. In: Proc. of ICCV’07 (2007)
[45] Udupa, J.K., Samarasekera, S.: Fuzzy connectedness and object definition: Theory, algorithms, and applications in image segmentation. Graph. Models Image Process. 58(3), 246–261 (1996) · Zbl 05473573 · doi:10.1006/gmip.1996.0021
[46] 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) · Zbl 05112633 · doi:10.1109/TPAMI.2002.1046162
[47] Zhuge, Y., Udupa, J.K., Saha, P.K.: Vectorial scale-based fuzzy connected image segmentation. Comput. Vis. Image Underst. 101, 177–193 (2006) · Zbl 05011899 · doi:10.1016/j.cviu.2005.07.009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.