Four color theorem and convex relaxation for image segmentation with any number of regions

Ruiliang Zhang; Xavier Bresson; Tony  F. Chan; Xue-Cheng Tai

doi:10.3934/ipi.2013.7.1099

Article Contents

2013, Volume 7, Issue 3: 1099-1113. Doi: 10.3934/ipi.2013.7.1099

This issue Previous Article A fast modified Newton's method for curvature based denoising of 1D signals Next Article

Four color theorem and convex relaxation for image segmentation with any number of regions

1.
Hong Kong University of Science and Technology, Hong Kong
2.
City University of Hong Kong, Department of Computer Science, Hong Kong
3.
University of Bergen, University of Bergen Bergen

Received: May 31, 2012

Revised: February 28, 2013

Published: July 2013

Abstract Related Papers Cited by

Abstract

Image segmentation is an essential problem in imaging science. One of the most successful segmentation models is the piecewise constant Mumford-Shah minimization model. This minimization problem is however difficult to carry out, mainly due to the non-convexity of the energy. Recent advances based on convex relaxation methods are capable of estimating almost perfectly the geometry of the regions to be segmented when the mean intensity and the number of segmented regions are known a priori. The next important challenge is to provide a tight approximation of the optimal geometry, mean intensity and the number of regions simultaneously while keeping the computational time and memory usage reasonable. In this work, we propose a new algorithm that combines convex relaxation methods with the four color theorem to deal with the unsupervised segmentation problem. More precisely, the proposed algorithm can segment any a priori unknown number of regions with only four intensity functions and four indicator (``labeling") functions. The number of regions in our segmentation model is decided by one parameter that controls the regularization strength of the geometry, i.e., the total length of the boundary of all the regions. The segmented image function can take as many constant values as needed.

Keywords:

Mathematics Subject Classification: Primary: 68U10, 52B55; Secondary: 65K10.

Citation:

Related Papers

Cited by

References

[1]	K. Appel and W. Haken, Every planar map is four colorable, Illinois Journal of Mathematics, 21 (1977), 429-567.
[2]	E. Bae and X. Tai, Efficient global minimization for the multiphase chan-vese model of image segmentation, Energy Minimization Methods in Computer Vision and Pattern Recognition, 5681 (2009), 28-41.doi: 10.1007/978-3-642-03641-5_3.
[3]	E. Bae and X. Tai, Efficient global minimization methods for image segmentation models with four regions, UCLA CAM Report, 11 (2011), p. 82.
[4]	E. Bae, J. Yuan and X. Tai, Simultaneous convex optimization of regions and region parameters in image segmentation models, UCLA CAM Report 11-83, (2011).doi: 10.1007/978-3-642-34141-0_19.
[5]	E. Bae, J. Yuan, X. Tai and Y. Boykov, A study on continuous max-flow and min-cut approaches part ii: Multiple linearly ordered labels, UCLA CAM Report, (2010), pp. 10-62.
[6]	E. Bae, J. Yuan, X. Tai and Y. Boykov, A fast continuous max-flow approach to non-convex multilabeling problems, Efficient global minimization methods for variational problems in imaging and vision, (2011).
[7]	E. Bae, J. Yuan and X.-C. Tai, Global minimization for continuous multiphase partitioning problems using a dual approach, International Journal of Computer Vision, 92 (2009), 112-129.doi: 10.1007/s11263-010-0406-y.
[8]	Y. Boykov and V. Kolmogorov, An experimental comparison of Min-Cut/Max-Flow algorithms for energy minimization in vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (2004), 1124-1137.
[9]	X. Bresson, S. Esedoglu, P. Vandergheynst, J. Thiran and S. Osher, Fast global minimization of the active contour/snake models, Journal of Mathematical Imaging and Vision, 28 (2007), 151-167.doi: 10.1007/s10851-007-0002-0.
[10]	E. Brown, T. Chan and X. Bresson, A convex relaxation method for a class of Vector-valued minimization problems with applications to Mumford-Shah segmentation, UCLA CAM Report 10-43, (2010).
[11]	E. S. Brown, T. F. Chan and X. Bresson, Completely convex formulation of the chan-vese image segmentation model, International Journal of Computer Vision, 98 (2012), 103-121.doi: 10.1007/s11263-011-0499-y.
[12]	V. Caselles, R. Kimmel and G. Sapiro, Geodesic Active Contours, International Journal of Computer Vision, 22 (1997), 61-79.
[13]	T. Chan, S. Esedoglu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM Journal on Applied Mathematics, 66 (2006), 1632-1648.doi: 10.1137/040615286.
[14]	T. Chan and L. Vese, Active contours without edges, IEEE Transactions on Image Processing, 10 (2001), 266-277.doi: 10.1109/83.902291.
[15]	D. Donoho, De-Noising by soft-thresholding, IEEE Transactions on Information Theory, 41 (1995), 613-627.doi: 10.1109/18.382009.
[16]	V. Estellers, D. Zosso, R. Lai, J. Thiran, S. Osher and X. Bresson, An efficient algorithm for level set method preserving distance function, UCLA CAM Report 21 (2011), 4722-4734.doi: 10.1109/TIP.2012.2202674.
[17]	S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (1984), 721-741.
[18]	T. Goldstein and S. Osher, The split bregman method for l1 regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343.doi: 10.1137/080725891.
[19]	E. Hodneland, X.-C. Tai and H.-H. Gerdes, Four-color theorem and level set methods for watershed segmentation, International Journal of Computer Vision, 82 (2009), 264-283.doi: 10.1007/s11263-008-0199-4.
[20]	J. Z. Huang, M. K. Ng, H. Rong and Z. Li, Automated variable weighting in k-means type clustering, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27 (2005), 657-668.doi: 10.1109/TPAMI.2005.95.
[21]	S. Kang, B. Sandberg and A. Yip, A regularized k-means and multiphase scale segmentation, Inverse Problems and Imaging, 5 (2011), 407-429.doi: 10.3934/ipi.2011.5.407.
[22]	S. Kim and M. Kang, Multiple-region segmentation without supervision by adaptive global maximum clustering, Image Processing, IEEE Transactions on, 21 (2012), 1600-1612.doi: 10.1109/TIP.2011.2179058.
[23]	F. T. Leighton, A graph coloring algorithm for large scheduling problems, Journal of Research of the National Bureau of Standards, 84 (1979), 489-506.doi: 10.6028/jres.084.024.
[24]	J. Lellmann, J. Kappes, J. Yuan, F. Becker and C. Schnörr, Convex multi-class image labeling by simplex-constrained total variation, in "Scale Space and Variational Methods in Computer Vision" (SSVM 2009), X.-C. Tai, K. Mórken, M. Lysaker, and K.-A. Lie, eds., Springer, 5567 (2009), 150-162.doi: 10.1007/978-3-642-02256-2_13.
[25]	J. Lellmann and C. Schnörr, Continuous multiclass labeling approaches and algorithms, SIAM J. Imaging Sci., 4 (2011), 1049-1096.doi: 10.1137/100805844.
[26]	J. Lie, M. Lysaker and X. Tai, A variant of the level set method and applications to image segmentation, Mathematics of computation, 75 (2006), 1155-1174.doi: 10.1090/S0025-5718-06-01835-7.
[27]	L. Liu and W. Tao, Image segmentation by iterative optimization of multiphase multiple piecewise constant model and Four-Color relabeling, Pattern Recognition, 44 (2011), 2819-2833.doi: 10.1016/j.patcog.2011.04.031.
[28]	T. Lu, P. Neittaanmäki and X. Tai, A parallel splitting up method and its application to Navier-Stokes equations, Applied Mathematics Letters, 4 (1991), 25-29.doi: 10.1016/0893-9659(91)90161-N.
[29]	C. Michelot, A finite algorithm for finding the projection of a point onto the canonical simplex of Rn, Journal of Optimization Theory and Applications, 50 (1986), 195-200.doi: 10.1007/BF00938486.
[30]	D. Mumford and J. Shah, Optimal approximations of piecewise smooth functions and associated variational problems, Communications on Pure and Applied Mathematics, 42 (1989), 577-685.doi: 10.1002/cpa.3160420503.
[31]	S. Osher and J. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, 79 (1988), 12-49.doi: 10.1016/0021-9991(88)90002-2.
[32]	T. Pock, A. Chambolle, D. Cremers and H. Bischof, A convex approach for computing minimal partitions, in IEEE Conference on Computer Vision and Pattern Recognition, 2009, pp. 810-817.doi: 10.1109/CVPR.2009.5206604.
[33]	R. Potts and C. Domb, Some generalized order-disorder transformations, Mathematical Proceedings of the Cambridge Philosophical Society, 48 (1952), 106-109.doi: 10.1017/S0305004100027419.
[34]	G. Rosman, L. Dascal, X. Tai and R. Kimmel, On semi-implicit splitting schemes for the beltrami color image filtering, Journal of Mathematical Imaging and Vision, 40 (2011), 199-213.doi: 10.1007/s10851-010-0254-y.
[35]	B. Shafei and G. Steidl, Segmentation of images with separating layers by fuzzy c-means and convex optimization, Journal of Visual Communication and Image Representation, 23 (2012), 611-621.doi: 10.1016/j.jvcir.2012.02.006.
[36]	P. Strandmark, F. Kahl and N. Overgaard, Optimizing Parametric Total Variation Models, in International Conference on Computer Vision, (2009), pp. 2240-2247.
[37]	G. Strang, Maximal Flow Through A Domain, Mathematical Programming, 26 (1983), 123-143.doi: 10.1007/BF02592050.
[38]	W. Tao and X. Tai, Multiple piecewise constant with geodesic active contours (mpc-gac) framework for interactive image segmentation using graph cut optimization, Image and Vision Computing, 29 (2011), 499-508.doi: 10.1016/j.imavis.2011.03.002.
[39]	L. Vese and T. Chan, A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model, International Journal of Computer Vision, 50 (2002), 271-293.
[40]	Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM Journal on Imaging Sciences, 1 (2008), 248-272.doi: 10.1137/080724265.
[41]	C. Wu and X. Tai, Augmented Lagrangian method, dual methods, and split bregman iteration for ROF, Vectorial TV, and High Order Models, SIAM Journal on Imaging Sciences, 3 (2010), 300-339.doi: 10.1137/090767558.
[42]	J. Yuan, E. Bae, Y. Boykov and X.-C. Tai, A continuous max-flow approach to minimal partitions with label cost prior, Scale Space and Variational Methods in Computer Vision, (2012), pp. 279-290.doi: 10.1007/978-3-642-24785-9_24.
[43]	J. Yuan, E. Bae and X. Tai, A study on continuous max-flow and min-cut approaches, in "Computer Vision and Pattern Recognition" (CVPR), 2010 IEEE Conference on, IEEE, 2010, pp. 2217-2224.doi: 10.1109/CVPR.2010.5539903.
[44]	J. Yuan, E. Bae, X. Tai and Y. Boykov, A continuous Max-Flow approach to potts model, Computer Vision-ECCV 2010, 6316 (2010), 379-392.doi: 10.1007/978-3-642-15567-3_28.
[45]	C. Zach, D. Gallup, J. Frahm and M. Niethammer, Fast global labeling for real-time stereo using multiple plane sweeps, in "Vision, Modeling, and Visualization," 2008, pp. 243-252.