×

zbMATH — the first resource for mathematics

Completely convex formulation of the Chan-Vese image segmentation model. (English) Zbl 1254.68271
Summary: The active contours without edges model of T. F. Chan and L. A. Vese [IEEE Trans. Image Process. 10, No. 2, 266–277 (2001; Zbl 1039.68779)] is a popular method for computing the segmentation of an image into two phases, based on the piecewise constant Mumford-Shah model. The minimization problem is non-convex even when the optimal region constants are known a priori. In [SIAM J. Appl. Math. 66, No. 5, 1632–1648 (2006; Zbl 1117.94002)], the second author, S. Esedoḡlu and M. Nikolova provided a method to compute global minimizers by showing that solutions could be obtained from a convex relaxation. In this paper, we propose a convex relaxation approach to solve the case in which both the segmentation and the optimal constants are unknown for two phases and multiple phases. In other words, we propose a convex relaxation of the popular \(K\)-means algorithm. Our approach is based on the vector-valued relaxation technique developed in [{T. Goldstein}, the third author and S. Osher, Geometric applications of the split Bergmann method: segmentation and surface reconstruction. UCLA CAM Report 09-77 (2009)] and [the authors, A convex relaxation method for a class of vector-valued minimization problems with applications to Mumford-Shah segmentation. UCLA CAM Report 10-43 (2010)]. The idea is to consider the optimal constants as functions subject to a constraint on their gradient. Although the proposed relaxation technique is not guaranteed to find exact global minimizers of the original problem, our experiments show that our method computes tight approximations of the optimal solutions. Particularly, we provide numerical examples in which our method finds better solutions than the method proposed in [the second author et al., loc. cit.], whose quality of solutions depends on the choice of the initial condition.

MSC:
68T45 Machine vision and scene understanding
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alberti, G., Bouchitté, G., & Dal Maso, G. (1999). The calibration method for the Mumford-Shah functional. Comptes Rendus de L’Académie Des Sciences. Series 1, Mathematics, 329(3), 249–254. · Zbl 0948.49005
[2] Ambrosio, L., Fusco, N., & Pallara, D. (2000). Functions of bounded variation and free discontinuity problems. Oxford: Clarendon Press. · Zbl 0957.49001
[3] Arrow, K., Hurwicz, L., & Uzawa, H. (1958). Stanford mathematical studies in the social sciences: Vol. II. Studies in linear and non-linear programming. With contributions by H. B. Chenery, S. M. Johnson, S. Karlin, T. Marschak, R. M. Solow. Stanford: Stanford University Press. · Zbl 0091.16002
[4] Bae, E., & Tai, X.-C. (2009). Graph cut optimization for the piecewise constant level set method applied to multiphase image segmentation. In International conference on scale space and variational methods in computer vision (pp. 1–13). · Zbl 1296.94023
[5] Bae, E., Yuan, J., & Tai, X.-C. (2009). Global minimization for continuous multiphase partitioning problems using a dual approach. International Journal of Computer Vision, 92(1), 112–129. · Zbl 1235.68244
[6] Bae, E., Yuan, J., Tai, X.-C., & Boykov, Y. (2010). A study on continuous max-flow and min-cut approaches. Part II: multiple linearly ordered labels (UCLA CAM Report 10-62).
[7] Berkeley Dataset. http://www.eecs.berkeley.edu/CS/vision .
[8] Bertsekas, D. P. (1982). Constrained optimization and Lagrange multiplier methods. New York: Academic Press. · Zbl 0572.90067
[9] Bresson, X., Esedoglu, S., Vandergheynst, P., Thiran, J., & Osher, S. (2007). Fast global minimization of the active contour/snake models. Journal of Mathematical Imaging and Vision, 28(2), 151–167. · Zbl 05193728
[10] Brown, E. S., Chan, T. F., & Bresson, X. (2009). Convex formulations for piecewise constant Mumford-Shah image segmentation (UCLA CAM Report 09-66).
[11] Brown, E. S., Chan, T. F., & Bresson, X. (2010). A convex relaxation method for a class of vector-valued minimization problems with applications to Mumford-Shah segmentation (UCLA CAM Report 10-43).
[12] Chambolle, A., Cremers, D., & Pock, T. (2008). A convex approach for computing minimal partitions (Technical report TR-2008-05). Bonn: Dept. of Computer Science, University of Bonn.
[13] Chambolle, A., & Pock, T. (2010). A first-order primal-dual algorithm for convex problems with applications to imaging (R.I. 685). CMAP, Ecole Polytechnique. · Zbl 1255.68217
[14] Chan, T. F., Esedoḡlu, S., & Nikolova, M. (2006). Algorithms for finding global minimizers of image segmentation and denoising models. SIAM Journal on Applied Mathematics, 66(5), 1632–1648. · Zbl 1117.94002
[15] Chan, T. F., & Vese, L. A. (2001). Active contours without edges. IEEE Transactions on Image Processing, 10(2), 266–277. · Zbl 1039.68779
[16] El-Zehiry, N., Xu, S., Sahoo, P., & Elmaghraby, A. (2007). Graph cut optimization for the Mumford-Shah model. In IASTED international conference on visualization, imaging and image processing (pp. 182–187).
[17] Esser, E., Zhang, X., & Chan, T. F. (2010). A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences, 3(4), 1015–1046. · Zbl 1206.90117
[18] Evans, L. C., & Gariepy, R. F. (2000). Measure theory and fine properties of functions. Boca Raton: CRC Press. · Zbl 0804.28001
[19] Federer, H. (1959). Curvature measures. Transactions of the American Mathematical Society, 93(3), 418–491. · Zbl 0089.38402
[20] Fleming, W., & Rishel, R. (1960). An integral formula for total gradient variation. Archiv der Mathematik, 11(1), 218–222. · Zbl 0094.26301
[21] Goldluecke, S., & Cremers, D. (2010). Convex relaxation for multilabel problems with product label spaces. In European conference on computer vision (pp. 225–238).
[22] Goldstein, T., Bresson, X., & Osher, S. (2009). Geometric applications of the split Bregman method: segmentation and surface reconstruction. Journal of Scientific Computing, 45(1–3), 272–293. · Zbl 1203.65044
[23] Goldstein, T., Bresson, X., & Osher, S. (2009). Global minimization of Markov random fields with applications to optical flow (UCLA CAM Report 09-77). · Zbl 1262.68174
[24] Ishikawa, H. (2003). Exact optimization for Markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10), 1333–1336. · Zbl 05112455
[25] Lellmann, J., Becker, F., & Schnörr, C. (2009). Convex optimization for multi-class image labeling with a novel family of total variation based regularizers. In International conference on computer vision (pp. 646–653).
[26] Lellmann, J., Kappes, J., Yuan, J., Becker, F., & Schnörr, C. (2009). Convex multi-class image labeling by simplex-constrained total variation. In International conference on scale space and variational methods in computer vision (pp. 150–162).
[27] Lellmann, J., & Schnörr, C. (2010). Continuous multiclass labeling approaches and algorithms (Tech. Rep.). Heidelberg: University of Heidelberg. · Zbl 1231.90311
[28] Lie, J., Lysaker, M., & Tai, X.-C. (2006). A binary level set model and some applications to Mumford-Shah image segmentation. IEEE Transactions on Image Processing, 15(5), 1171–1181. · Zbl 1286.94018
[29] Lieb, E. H., & Loss, M. (2001). Analysis. Providence: Am. Math. Soc. · Zbl 0966.26002
[30] MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability (pp. 281–297). · Zbl 0214.46201
[31] Mumford, D., & Shah, J. (1989). Optimal approximations of piecewise smooth functions and associated variational problems. Communications on Pure and Applied Mathematics, 42, 577–685. · Zbl 0691.49036
[32] Osher, S., & Sethian, J. A. (1988). Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics, 79(1), 12–49. · Zbl 0659.65132
[33] Pock, T., Chambolle, A., Bischof, H., & Cremers, D. (2009). An algorithm for minimizing the Mumford-Shah functional. In IEEE conference on computer vision (ICCV).
[34] Pock, T., Cremers, D., Bischof, H., & Chambolle, A. (2010). Global solutions of variational models with convex regularization. SIAM Journal on Imaging Sciences, 2(3), 1122–1145. · Zbl 1202.49031
[35] Pock, T., Schoenemann, T., Graber, G., Bischof, H., & Cremers, D. (2008). A convex formulation of continuous multi-label problems. In European conference on computer vision (ECCV) (pp. 792–805).
[36] Popov, L. D. (1980). A modification of the Arrow-Hurwitz method of search for saddle points. Matematičeskie Zametki, 28(5), 777–784, 803. · Zbl 0456.90068
[37] Shekhovtsov, A., Kovtun, I., & Hlavác, V. (2008). Efficient MRF deformation model for non-rigid image matching. Computer Vision and Image Understanding, 112(1), 91–99. · Zbl 05363063
[38] Strandmark, P., Kahl, F., & Overgaard, N. C. (2009). Optimizing parametric total variation models. In International conference on computer vision (pp. 2240–2247).
[39] Strang, G. (1983). Maximal flow through a domain. Mathematical Programming, 26(2), 123–143. · Zbl 0513.90026
[40] Weizmann Dataset. http://www.weizmann.ac.il/\(\sim\)vision .
[41] Yuan, J., Bae, E., Tai, X.-C., & Boykov, Y. (2010). A study on continuous max-flow and min-cut approaches. Part I: binary labeling (UCLA CAM Report 10-61).
[42] Zach, C., Gallup, D., Frahm, J. M., & Niethammer, M. (2008). Fast global labeling for real-time stereo using multiple plane sweeps. In Vision, modeling, and visualization (pp. 243–252).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.