Image segmentation based on the hybrid total variation model and the K-means clustering strategy

Baoli  Shi; Zhi-Feng  Pang; Jing  Xu

doi:10.3934/ipi.2016022

Article Contents

2016, Volume 10, Issue 3: 807-828. Doi: 10.3934/ipi.2016022

This issue Previous Article A gradient-based method for atmospheric tomography Next Article Error bounds and stability in the $l_{0}$ regularized for CT reconstruction from small projections

Image segmentation based on the hybrid total variation model and the K-means clustering strategy

1.
College of Mathematics and Statistic, Henan University, Kaifeng 475004, Henan
2.
School of Statistic and Mathematics, Zhejiang Gongshang University, Hangzhou 310012

Received: May 31, 2014

Revised: March 31, 2016

Published: July 2016

Abstract Related Papers Cited by

Abstract

The performance of image segmentation highly relies on the original inputting image. When the image is contaminated by some noises or blurs, we can not obtain the efficient segmentation result by using direct segmentation methods. In order to efficiently segment the contaminated image, this paper proposes a two step method based on the hybrid total variation model with a box constraint and the K-means clustering method. In the first step, the hybrid model is based on the weighted convex combination between the total variation functional and the high-order total variation as the regularization term to obtain the original clustering data. In order to deal with non-smooth regularization term, we solve this model by employing the alternating split Bregman method. Then, in the second step, the segmentation can be obtained by thresholding this clustering data into different phases, where the thresholds can be given by using the K-means clustering method. Numerical comparisons show that our proposed model can provide more efficient segmentation results dealing with the noise image and blurring image.

Keywords:

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

Citation:

Related Papers

Cited by

References

[1]	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 (2011), 112-129.doi: 10.1007/s11263-010-0406-y.
[2]	Y. Boykov, O. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Ananlysis and Machine Intelligence, 23 (2001), 1-18.
[3]	K. Bredies, K. Kunisch and T. Pock., Total generalized variation, SIAM Journal on Imaging Sciences, 3 (2010), 492-526.doi: 10.1137/090769521.
[4]	X. Bresson, S. Esedoglu, P. Vandergheynst, J. Thiran and S. Osher, Fast global minimization of the active contour/snake model, Journal of Mathematical Imaging and Vision, 28 (2007), 151-167.doi: 10.1007/s10851-007-0002-0.
[5]	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.
[6]	Y. Boykov, V. Kolmogorov, D. Cremers and A. Delong, An integral solution to surface evolution PDEs via geo-cuts. Proc. ECCV LCNS, 3953 (2006), 409-422.doi: 10.1007/11744078_32.
[7]	Y. Boykov, O. Veksler and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (2001), 1222-1239.
[8]	X. Cai, R. Chan and T. Zeng, A two-stage image segmentation method using a convex variant of the Mumford-Shah model and thresholding, SIAM Journal on Image Science, 6 (2013), 368-390.doi: 10.1137/120867068.
[9]	J.-F. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration, SIAM: Multiscale Modeling and Simulation, 8 (2009), 337-369.doi: 10.1137/090753504.
[10]	V. Caselles, R. Kimmel and G. Sapiro, Geodesic active contours, International Journal of Computer Vision, 22 (1997), 61-79.
[11]	A. Chambolle, D. Cremers and T. Pock, A convex approach to minimal partitions, SIAM Journal on Image Science, 5 (2012), 1113-1158.doi: 10.1137/110856733.
[12]	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.
[13]	T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration, SIAM Journal on Scientific Computing, 22 (2000), 503-516.doi: 10.1137/S1064827598344169.
[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]	C. Chen, B. He and X. Yuan, Matrix completion via an alternating direction method, IMA Journal of Numerical Analysis, 32 (2012), 227-245.doi: 10.1093/imanum/drq039.
[16]	A. Delong, A. Osokin, H. Isack and Y. Boykov, Fast approximate energy minimization with label costs, International Journal of Computer Vision, 96 (2012), 1-27.doi: 10.1007/s11263-011-0437-z.
[17]	S. Esedoglu and Y. Tsai, Threshold dynamics for the piecewise constant Mumford-Shah functional, Journal of Computational Physics, 211 (2006), 367-384.doi: 10.1016/j.jcp.2005.05.027.
[18]	Y. Gu, L.-L. Wang and X.-C. Tai, A direct approach towards global minimization for multiphase labeling and segmentation problems, IEEE Transactions on Image Processing, 21 (2012), 2399-2411.doi: 10.1109/TIP.2011.2182522.
[19]	L. Grady, The piecewise smooth Mumford-Shah functional on an arbitrary graph, IEEE Transactions on Image Processing, 18 (2009), 2547-2561.doi: 10.1109/TIP.2009.2028258.
[20]	M. Kass, A. Witkin and D. Terzopoulos, Snakes: Active contour models, International Journal of Computer Vision, 1 (1988), 321-331.doi: 10.1007/BF00133570.
[21]	J. Lellmann, B. Lellmann, F. Widmann and C. Schnorr, Discrete and continuous models for partitioning problems, International Journal of Computer Vision, 104 (2013), 241-269.doi: 10.1007/s11263-013-0621-4.
[22]	J. Lellmann, J. Kappes, J. Yuan, F. Becker and C. Schnoor, Convex multi-class image labeling by simplex-constrainted total variation, Scale Space and Variational Methods in Computer Vision, 5567 (2009), 150-162.
[23]	J. Lellmann and C. Schnoor, Continuous multiclass labeling approaches and algorithms, Journal of Imaging Science, 4 (2011), 1049-1096.doi: 10.1137/100805844.
[24]	F. Li, M. Ng, T. Y. Zeng and C. Shen, A multiphase image segmentation method based on fuzzy region competition, SIAM Journal on Scientific Computing, 3 (2010), 277-299.doi: 10.1137/080736752.
[25]	F. Li, C. Shen, J. Fan and C. Shen, Image restoration combining a total variational filter and a fourth-order filter, Journal of Visual Communication and Image Representation, 18 (2007), 322-330.doi: 10.1016/j.jvcir.2007.04.005.
[26]	J. Lie, M. Lysaker and X.-C. 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]	J. Lie, M. Lysaker and X.-C. Tai, A binary level set model and some applications to Mumford-Shah image segmentation, IEEE Transactions on Image Processing, 15 (2006), 1171-1181.doi: 10.1109/TIP.2005.863956.
[28]	M. Lysaker, A. Lundervold and X. Tai, Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time, IEEE Transactions on Image Processing, 12 (2003), 1579-1590.doi: 10.1109/TIP.2003.819229.
[29]	D. Krishnan, Q. Pham and A. Yip, A primal-dual active-set algorithm for bilaterally constrained total variation deblurring and piecewise constant Mumford-Shah segmentation problems, Advances in Computational Mathematics, 31 (2009), 237-266.doi: 10.1007/s10444-008-9101-8.
[30]	B. Macqueen, Some methods for classification and analysis of multivariate observations, In: Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, 1 (1967), 281-297.
[31]	A. Marquina and S. J. Osher, Image super-resolution by TV-regularization and Bregman iteration, Journal of Scientific Computing, 37 (2008), 367-382.doi: 10.1007/s10915-008-9214-8.
[32]	D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Communications on Pure and Applied Mathematics, 42 (1989), 577-685.doi: 10.1002/cpa.3160420503.
[33]	C. Nieuwenhuis, E. Toppe and D. Cremers, A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model, International Journal of Computer Vision, 104 (2013), 223-240.doi: 10.1007/s11263-013-0619-y.
[34]	K. Papafitsoros and C. Schonlieb, A combined first and second variational approach for image reconstruction, Journal of Mathematical Imaging and Vision, 48 (2014), 308-338.doi: 10.1007/s10851-013-0445-4.
[35]	T. Pock, A. Chambolle, H. Bischof and D. Cremers, A convex relaxation approach for computing minimal partitions, In: IEEE Conference on Computer Vision and Pattern Recognition(CVPR), (2009), 810-817.doi: 10.1109/CVPR.2009.5206604.
[36]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[37]	S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, In Proceedings of the Second International Conference on Scale Space and VariationalMethods in Computer Vision, 5567 (2009), 464-476.doi: 10.1007/978-3-642-02256-2_39.
[38]	R. Schafer, R. Mersereau and M. Richaards, Constrained iterative restoration algorithms, Proceedings of the IEEE, 69 (1981), 432-450.doi: 10.1109/PROC.1981.11987.
[39]	O. Tobias and R. Seara, Image segmentation by histogram thresholding using fuzzy sets, IEEE Transactions on Image Processing, 11 (2002), 1457-1465.doi: 10.1109/TIP.2002.806231.
[40]	L. Vese and T. Chan, A multiphase level set framework for image segmentation using the Mumford-Shah model, International Journal of Computer Vision, 50 (2002), 271-293.
[41]	X. Wang, D. Huang and H. Xu, An efficient local Chan-Vese model for image segmentation, Pattern Recognit, 43 (2010), 603-618.doi: 10.1016/j.patcog.2009.08.002.
[42]	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.
[43]	J. Yang and Y. Zhang, Alternating direction algorithms for $l^1$ problems in compressive sensing, SIAM Journal on Scientific Computing, 33 (2011), 250-278.doi: 10.1137/090777761.
[44]	J. Yuan, E. Bae, X.-C. Tai and Y. Boykov, A continuous max-flow approach to Potts model, 11th European Conference on Computer Vision (ECCV), 6316 (2010), 379-392.doi: 10.1007/978-3-642-15567-3_28.
[45]	J. Yuan, E. Bae, X.-C. Tai and Y. Boykov, A study on continuous max-flow and min-cut approaches, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), (2010), 2217-2224.doi: 10.1109/CVPR.2010.5539903.
[46]	J. Yuan, C. Schnörr and G. Steidl, Total-variation based piecewise affine regularization, Scale Space and Variational Methods in Computer Vision, 5567 (2009), 552-564.doi: 10.1007/978-3-642-02256-2_46.
[47]	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), 243-252.
[48]	R. Zhang, X. Bresson and X.-C. Tai, Four color theorem and convex relaxation for image segmentation with any number of regions, Inverse Problems and Imaging, 7 (2013), 1099-1113.doi: 10.3934/ipi.2013.7.1099.
[49]	S. Zhu and A. Yuille, Region competition: Unifying snakes, region growing, and Bayes/MDL for multi-band image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 18 (1996), 884-900.