×

Efficient global minimization methods for image segmentation models with four regions. (English) Zbl 1331.68263

Summary: We propose an exact global minimization framework for certain variational image segmentation models, such as the Chan-Vese model, involving four regions. A global solution is guaranteed if the data term satisfies a certain condition. We give a theoretical analysis of the condition for \(L^p\) type of data terms, such as in the Chan-Vese model and Mumford Shah model for \(p=2\). We show experimentally that the condition tends to hold in practice for \(p\geq 2\) and also holds in many cases for more advanced data terms. If the condition is violated, convex and submodular relaxations are proposed which are not guaranteed to produce exact solutions, but tend to do so in practice. We also build up simple convex relaxations for some other four region segmentation models, including Potts’ model. Algorithms are proposed which are very efficient compared to related work due to the simple and compact formulations.

MSC:

68U10 Computing methodologies for image processing
65K10 Numerical optimization and variational techniques

Software:

MAXFLOW
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mumford, D., Shah, J.: Optimal approximation by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 42, 577-685 (1989) · Zbl 0691.49036 · doi:10.1002/cpa.3160420503
[2] Chan, T., Vese, L.A.: Active contours without edges. IEEE Image Proc. 10, 266-277 (2001) · Zbl 1039.68779 · doi:10.1109/83.902291
[3] Vese, L.A., Chan, T.F.: A new multiphase level set framework for image segmentation via the Mumford and Shah model. Int. J. Comput. Vis. 50, 271-293 (2002) · Zbl 1012.68782 · doi:10.1023/A:1020874308076
[4] Boykov, Yuri, Kolmogorov, Vladimir: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26, 359-374 (2001) · Zbl 1005.68964
[5] Greig, D.M., Porteous, B.T., Seheult, A.H.: Exact maximum a posteriori estimation for binary images. J. R. Stat. Soc. Ser. B 51, 271-279 (1989)
[6] Boykov, Yuri, Veksler, Olga, Zabih, Ramin: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1222-1239 (2001) · doi:10.1109/34.969114
[7] Bae, Egil, Yuan, Jing, Tai, Xue-Cheng: Global minimization for continuous multiphase partitioning problems using a dual approach. Int. J. Comput. Vis. 92(1), 112-129 (2011) · Zbl 1235.68244 · doi:10.1007/s11263-010-0406-y
[8] Brown, E.S., Chan, T.F., Bresson, X.: A convex relaxation method for a class of vector-valued minimization problems with applications to Mumford-Shah segmentation. UCLA, Applied Mathematics, CAM-report-10-43, July, 2010
[9] Lellmann, J., Becker, F., Schnörr, C.: Convex optimization for multi-class image labeling with a novel family of total variation based regularizers. In: IEEE International Conference on Computer Vision (ICCV), pp. 646-653 (2009) · Zbl 1286.94018
[10] Lellmann, J.; Kappes, J.; Yuan, J.; Becker, F.; Schnörr, C.; Tai, X-C (ed.); Mórken, K. (ed.); Lysaker, M. (ed.); Lie, K-A (ed.), Convex multi-class image labeling by simplex-constrained total variation, 150-162 (2009), New York
[11] Pock, T., Chambolle, A., Bischof, H., Cremers, D.: A convex relaxation approach for computing minimal partitions. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Miami, Florida (2009) · Zbl 1202.49031
[12] Zach, C., Gallup, D., Frahm, J.-M., Niethammer, M.: Fast global labeling for real-time stereo using multiple plane sweeps. In: Vision, Modeling and Visualization Workshop (VMV) (2008) · Zbl 0513.90026
[13] Goldluecke, B., Cremers, D.: Convex relaxation for multilabel problems with product label spaces. In: Proceedings of the 11th European conference on Computer vision, ECCV’10, pp. 225-238. Springer, Berlin, Heidelberg (2010). · Zbl 1290.49060
[14] Strekalovskiy, E., Goldluecke, B., Cremers, D.: Tight convex relaxations for vector-valued labeling problems. In: IEEE International Conference on Computer Vision (ICCV) (2011) · Zbl 1279.68326
[15] Ishikawa, Hiroshi: Exact optimization for markov random fields with convex priors. IEEE Trans. Pattern Anal. Mach. Intell. 25, 1333-1336 (2003) · doi:10.1109/TPAMI.2003.1233908
[16] Chan, T.F., Esedoḡlu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math., 66(5):1632-1648 (electronic), (2006) · Zbl 1117.94002
[17] Bae, E., Yuan, J., Tai, X.C., Boykov, Y.: A fast continuous max-flow approach to non-convex multilabeling problems. Technical report CAM10-62, UCLA, CAM (2010)
[18] Yuan, J., Bae, E., Tai, X.C.: A study on continuous max-flow and min-cut approaches. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 2217-2224. San Francisco (2010)
[19] Yuan, Jing, Bae, Egil, Tai, Xue-Cheng, Boykov, Yuri: A spatially continuous max-flow and min-cut framework for binary labeling problems. Numerische Mathematik 126(3), 559-587 (2014) · Zbl 1290.49060 · doi:10.1007/s00211-013-0569-x
[20] Liu, Liman, Tao, Wenbing: Image segmentation by iteratively optimization of multiphase multiple piecewise constant model and four-color relabeling. Pattern Recognit. 44(12), 2819-2833 (2011) · Zbl 1218.68175 · doi:10.1016/j.patcog.2011.04.031
[21] Zhang, R., Bresson, X., Chan, T.F., Tai, X.-C.: Four color theorem and convex relaxation for image segmentation with any number of regions. UCLA, Applied Mathematics, CAM-report-13-16 (2013) · Zbl 1272.68450
[22] Hodneland, Erlend, Tai, Xue-Cheng, Gerdes, Hans-Hermann: Four-color theorem and level set methods for watershed segmentation. Int. J. Comput. Vis. 82(3), 264-283 (2009) · doi:10.1007/s11263-008-0199-4
[23] Bae, E., Tai, X.-C.: Efficient global minimization for the multiphase Chan-Vese model of image segmentation. In: Proceedings of the 7th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition. LNCS, vol. 5681, pp. 28-41. Springer, New York (2009) · Zbl 1235.68244
[24] Bae, E.: Efficient global minimization methods for variational problems in imaging and vision. (Phd thesis, University of Bergen, https://bora.uib.no/handle/1956/5017), August 2011 · Zbl 1012.68782
[25] Bae, Egil; Tai, Xue-Cheng; Tai, X-C (ed.); Mórken, K. (ed.); Lysaker, M. (ed.); Lie, K-A (ed.), Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation, 1-13 (2009), New York · Zbl 1296.94023 · doi:10.1007/978-3-642-02256-2_1
[26] Brown, E.S., Chan, T.F., Bresson, X.: Completely convex formulation of the Chan-Vese image segmentation model. International Journal of Computer Vision. (2011) doi:10.1007/s11263-011-0499-y · Zbl 1254.68271
[27] Lie, J., Lysaker, M., Tai, X.C.: Piecewise constant level set methods and image segmentation. In: Scale Space and PDE Methods in Computer Vision, pp. 573-584. Springer, New York (2005) · Zbl 1119.68489
[28] Lie, J., Lysaker, M., Tai, X.C.: A binary level set model and some applications to Mumford-Shah image segmentation. IEEE Trans. Image Process. 15(5), 1171-1181 (2006) · Zbl 1286.94018 · doi:10.1109/TIP.2005.863956
[29] Meyer, Y.: Oscillating patterns in image processing and nonlinear evolution equations, volume 22 of University Lecture Series. American Mathematical Society, Providence, RI, 2001. The fifteenth Dean Jacqueline B. Lewis memorial lectures · Zbl 0987.35003
[30] Strang, Gil: Maximal flow through a domain. Math. Program. 26, 123-143 (1983) · Zbl 0513.90026 · doi:10.1007/BF02592050
[31] Pock, T., Schoenemann, T., Graber, G., Bischof, H., Cremers, D.: A convex formulation of continuous multi-label problems. In: ECCV ’08, pp. 792-805 (2008) · Zbl 1039.68779
[32] Bae, E., Lellmann, J., Tai, X.-C.: Convex relaxations for a generalized chan-vese model. In: 9th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition. Lecture Notes in Computer Science, vol. 8081, pp. 223-236. Springer, New York (2013)
[33] Boykov, Y., Kolmogorov, V.: Computing geodesics and minimal surfaces via graph cuts. In: ICCV ’03: Proceedings of the Ninth IEEE International Conference on Computer Vision, p. 26. IEEE Computer Society, Washington, DC (2003).
[34] Geman, S.; Geman, D., Stochastic relaxation, gibbs distributions, and the bayesian restoration of images, 452-472 (1990), San Francisco
[35] Fulkerson, D., Ford, L.: Flows in Networks. Princeton University Press, Princeton (1962) · Zbl 0106.34802
[36] Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147-159 (2004) · doi:10.1109/TPAMI.2004.1262177
[37] Kolmogorov, Vladimir, Rother, Carsten: Minimizing nonsubmodular functions with graph cuts: a review. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1274-1279 (2007) · doi:10.1109/TPAMI.2007.1031
[38] Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 01 optimization. Math. Program. 28, 121-155 (1984) · Zbl 0574.90066 · doi:10.1007/BF02612354
[39] Rother, C., Kumar, S., Kolmogorov, V., Blake, A.: Digital tapestry. In: IEEE Proceedings of the Computer Vision and Pattern Recognition (2005)
[40] El-Zehiry, N.Y., Grady, L.: Combinatorial optimization of the discretized multiphase Mumford-Shah functional. Int. J. Comput. Vis. (2013) doi:10.1007/s11263-013-0617-0 · Zbl 1304.68191
[41] Berkels, B.: An unconstrained multiphase thresholding approach for image segmentation. In: SSVM, pp. 26-37 (2009) · Zbl 0174.20705
[42] Hyman, J.M., Shashkov, M.J.: Natural discretizations for the divergence, gradient, and curl on logically rectangular grids. Comput. Math. Appl. 33(4), 81-104 (1997) · Zbl 0868.65006 · doi:10.1016/S0898-1221(97)00009-6
[43] Ito, Kazufumi, Kunisch, Karl: Lagrange Multiplier Approach to Variational Problems and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2008) · Zbl 1156.49002 · doi:10.1137/1.9780898718614
[44] Ekeland, Ivar, Téman, Roger: Convex Analysis and Variational Problems. Society for Industrial and Applied Mathematics, Philadelphia (1999) · Zbl 0939.49002 · doi:10.1137/1.9781611971088
[45] http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/
[46] Chambolle, Antonin, Cremers, Daniel, Pock, Thomas: A convex approach to minimal partitions. SIAM J. Imaging Sci. 5(4), 11131158 (2012) · Zbl 1256.49040 · doi:10.1137/110856733
[47] Federer, H.: Geometric Measure Theory. Springer, New York (1969) · Zbl 0176.00801
[48] Vol’Pert, A.I.: Spaces BV and quasilinear equations. Mat. Sb. (N.S.) 73(115), 255302 (1967)
[49] Chambolle, Antonin: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1), 89-97 (2004) · Zbl 1366.94048
[50] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303-320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[51] Boyle, J.P., Dykstra, R.: A method for finding projections onto the intersection of convex sets in hilbert spaces. In: Advances in Order Restricted Statistical Inference (Iowa City, Iowa, 1985). Lecture Notes in Statistics, vol. 37, p. 2847. Springer, Berlin, 1986 (1985) · Zbl 0603.49024
[52] Hodneland, E.: Segmentation of digital images. Cand. Scient Thesis, Department of Mathematics, University of Bergen. Available online at www.mi.uib.no/tai (2003) · Zbl 0574.90066
[53] Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the piecewise smooth Mumford-Shah functional. In: IEEE International Conference on Computer Vision (ICCV). Kyoto (2009)
[54] Yuan, J., Bae, E., Tai, X.-C., Boykov, Yuri: A continuous max-flow approach to potts model. In: European Conference on Computer Vision. LNCS, vol. 6316, pp. 379-392 (2010)
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.