An Efficient Smoothing and Thresholding Image Segmentation Framework with Weighted Anisotropic-Isotropic Total Variation

doi:10.1007/s42967-023-00339-w

Abstract

Abstract: In this paper, we design an efficient, multi-stage image segmentation framework that incorporates a weighted difference of anisotropic and isotropic total variation (AITV). The segmentation framework generally consists of two stages: smoothing and thresholding, thus referred to as smoothing-and-thresholding (SaT). In the first stage, a smoothed image is obtained by an AITV-regularized Mumford-Shah (MS) model, which can be solved efficiently by the alternating direction method of multipliers (ADMMs) with a closed-form solution of a proximal operator of the $\ell_1-\alpha \ell_2$ regularizer. The convergence of the ADMM algorithm is analyzed. In the second stage, we threshold the smoothed image by K-means clustering to obtain the final segmentation result. Numerical experiments demonstrate that the proposed segmentation framework is versatile for both grayscale and color images, efficient in producing high-quality segmentation results within a few seconds, and robust to input images that are corrupted with noise, blur, or both. We compare the AITV method with its original convex TV and nonconvex TV^p(0<p<1) counterparts, showcasing the qualitative and quantitative advantages of our proposed method.

Key words: Image segmentation, Non-convex optimization, Mumford-Shah(MS) model, Alternating direction method of multipliers(ADMMs), Proximal operator

Kevin Bui, Yifei Lou, Fredrick Park, Jack Xin. An Efficient Smoothing and Thresholding Image Segmentation Framework with Weighted Anisotropic-Isotropic Total Variation[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1369-1405.

TrendMD

References

[1] Alpert, S., Galun, M., Basri, R., Brandt, A.: Image segmentation by probabilistic bottom-up aggregation and cue integration. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 315-327 (2007)
[2] Ambrosio, L., Tortorelli, V.M.: Approximation of functional depending on jumps by elliptic functional via Γ-convergence. Commun. Pure Appl. Math. 43(8), 999-1036 (1990)
[3] Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: 2007 ACM-SIAM Symposium on Discrete Algorithms (SODA’07), pp. 1027-1035 (2007)
[4] Bar, L., Chan, T.F., Chung, G., Jung, M., Kiryati, N., Mohieddine, R., Sochen, N., Vese, L.A.: Mumford and Shah model and its applications to image segmentation and image restoration. In: Scherzer, O. (ed.) Handbook of Mathematical Methods in Imaging, pp. 1095-1157. Springer, New York, NY (2011). https://doi.org/10.1007/978-0-387-92920-0_25
[5] Beck, A.: First-Order Methods in Optimization. SIAM, Philadelphia (2017)
[6] Benninghoff, H., Garcke, H.: Efficient image segmentation and restoration using parametric curve evolution with junctions and topology changes. SIAM J. Imaging Sci. 7(3), 1451-1483 (2014)
[7] Birkholz, H.: A unifying approach to isotropic and anisotropic total variation denoising models. J. Comput. Appl. Math. 235(8), 2502-2514 (2011)
[8] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends^® Mach. Learn. 3(1), 1-122 (2011)
[9] Bui, K., Park, F., Lou, Y., Xin, J.: A weighted difference of anisotropic and isotropic total variation for relaxed Mumford-Shah color and multiphase image segmentation. SIAM J. Imaging Sci. 14(3), 1078-1113 (2021)
[10] Burdescu, D.D., Brezovan, M., Ganea, E., Stanescu, L.: A new method for segmentation of images represented in a HSV color space. In: Advanced Concepts for Intelligent Vision Systems: 11th International Conference, ACIVS 2009, Bordeaux, France, September 28-October 2, 2009. Proceedings 11, pp. 606-617. Springer (2009)
[11] Cai, X., Chan, R., Nikolova, M., Zeng, T.: A three-stage approach for segmenting degraded color images: smoothing, lifting and thresholding (SLaT). J. Sci. Comput. 72(3), 1313-1332 (2017)
[12] Cai, X., Chan, R., Zeng, T.: A two-stage image segmentation method using a convex variant of the Mumford-Shah model and thresholding. SIAM J. Imaging Sci. 6(1), 368-390 (2013)
[13] Cao, W., Sun, J., Zongben, X.: Fast image deconvolution using closed-form thresholding formulas of $L_q\left(q=\frac{1}{2}, \frac{2}{3}\right)$ regularization. J. Vis. Commun. Image Represent. 24(1), 31-41 (2013)
[14] Chambolle, A.: Finite-differences discretizations of the Mumford-Shah functional. ESAIM: Math. Model. Numer. Anal. 33(2), 261-288 (1999)
[15] Chambolle, A., Dal Maso, G.: Discrete approximation of the Mumford-Shah functional in dimension two. ESAIM: Math. Model. Numer. Anal. 33(4), 651-672 (1999)
[16] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120-145 (2011)
[17] Chan, R., Yang, H., Zeng, T.: A two-stage image segmentation method for blurry images with Poisson or multiplicative gamma noise. SIAM J. Imaging Sci. 7(1), 98-127 (2014)
[18] Chan, R.H., Ng, M.K.: Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(3), 427-482 (1996)
[19] Chan, T.F., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66(5), 1632-1648 (2006)
[20] Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266-277 (2001)
[21] Chan, T.F., Yezrielev Sandberg, B., Vese, L.A.: Active contours without edges for vector-valued images. J. Vis. Commun. Image Represent. 11(2), 130-141 (2000)
[22] Chang, H., Lou, Y., Duan, Y., Marchesini, S.: Total variation-based phase retrieval for Poisson noise removal. SIAM J. Imaging Sci. 11(1), 24-55 (2018)
[23] Chang, H., Lou, Y., Ng, M.K., Zeng, T.: Phase retrieval from incomplete magnitude information via total variation regularization. SIAM J. Sci. Comput. 38(6), A3672-A3695 (2016)
[24] Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3869-3872. IEEE (2008)
[25] Chen, T.-W., Chen, Y.-L., Chien, S.-Y.: Fast image segmentation based on K-means clustering with histograms in HSV color space. In: 2008 IEEE 10th Workshop on Multimedia Signal Processing, pp. 322-325. IEEE (2008)
[26] Chen, X., Ng, M.K., Zhang, C.: Non-Lipshitz l_p-regularization and box constrained model for image reconstruction. IEEE Trans. Image Process. 21(12), 4709-4721 (2012)
[27] Clarke, F.: Functional Analysis, Calculus of Variations and Optimal Control, vol. 264. Springer, Heidelberg (2013)
[28] Condat, L.: Discrete total variation: new definition and minimization. SIAM J. Imaging Sci. 10(3), 1258-1290 (2017)
[29] Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889-916 (2016)
[30] Dice, L.R.: Measures of the amount of ecologic association between species. Ecology 26(3), 297-302 (1945)
[31] Ding, L., Han, W.: αl₁-βl₂ regularization for sparse recovery. Inverse Probl. 35(12), 125009 (2019)
[32] Esedoglu, S., Tsai, Y.-H.R.: Threshold dynamics for the piecewise constant Mumford-Shah functional. J. Comput. Phys. 211(1), 367-384 (2006)
[33] Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015-1046 (2010)
[34] Ge, H., Chen, W., Ng, M.K.: New restricted isometry property analysis for l₁-l₂ minimization methods. SIAM J. Imaging Sci. 14(2), 530-557 (2021)
[35] Getreuer, P.: Chan-Vese segmentation. Image Process. Line 2, 214-224 (2012)
[36] Gobbino, M.: Finite difference approximation of the Mumford-Shah functional. Commun. Pure Appl. Math. 51(2), 197-228 (1998)
[37] Goldstein, T., Bresson, X., Osher, S.: Geometric applications of the split Bregman method: segmentation and surface reconstruction. J. Sci. Comput. 45(1/2/3), 272-293 (2010)
[38] Goldstein, T., Osher, S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2(2), 323-343 (2009)
[39] Gu, S., Xie, Q., Meng, D., Zuo, W., Feng, X., Zhang, L.: Weighted nuclear norm minimization and its applications to low level vision. Int. J. Comput. Vis. 121(2), 183-208 (2017)
[40] Han, D., Sun, D., Zhang, L.: Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math. Oper. Res. 43(2), 622-637 (2018)
[41] Hartigan, J.A., Wong, M.A.: A k-means clustering algorithm. J. R. Stat. Soc.: Ser. C (Appl. Stat.) 28(1), 100-108 (1979)
[42] Hintermüller, M., Tao, W.: Nonconvex TV^q-models in image restoration: analysis and a trust-region regularization-based superlinearly convergent solver. SIAM J. Imaging Sci. 6(3), 1385-1415 (2013)
[43] Hou, Z.: A review on MR image intensity inhomogeneity correction. Int. J. Biomed. Imaging 2006, 049515 (2006)
[44] Huang, Z.-K., Liu, D.-H.: Segmentation of color image using EM algorithm in HSV color space. In: 2007 International Conference on Information Acquisition, pp. 316-319. IEEE (2007)
[45] Jung, M.: Piecewise-smooth image segmentation models with L¹ data-fidelity terms. J. Sci. Comput. 70(3), 1229-1261 (2017)
[46] Jung, M., Kang, M., Kang, M.: Variational image segmentation models involving non-smooth data-fidelity terms. J. Sci. Comput. 59(2), 277-308 (2014)
[47] Lanza, A., Morigi, S., Sgallari, F.: Constrained TV^P-l₂ model for image restoration. J. Sci. Comput. 68(1), 64-91 (2016)
[48] Le Thi, H.A., Pham Dinh, T.: DC programming and DCA: thirty years of developments. Math. Program. 169(1), 5-68 (2018)
[49] Li, C., Kao, C.-Y., Gore, J.C., Ding, Z.: Minimization of region-scalable fitting energy for image segmentation. IEEE Trans. Image Process. 17(10), 1940-1949 (2008)
[50] Li, F., Ng, M.K., Zeng, T.Y., Shen, C.: A multiphase image segmentation method based on fuzzy region competition. SIAM J. Imaging Sci. 3(3), 277-299 (2010)
[51] Li, F., Osher, S., Qin, J., Yan, M.: A multiphase image segmentation based on fuzzy membership functions and L1-norm fidelity. J. Sci. Comput. 69(1), 82-106 (2016)
[52] Li, F., Zhu, Y.: Smoothing and clustering guided image decolorization. Image Anal. Stereol. 40(1), 17-27 (2021)
[53] Li, P., Chen, W., Ge, H., Ng, M.K.: l₁-αl₂ minimization methods for signal and image reconstruction with impulsive noise removal. Inverse Probl. 36(5), 055009 (2020)
[54] Li, X., Yang, X., Zeng, T.: A three-stage variational image segmentation framework incorporating intensity inhomogeneity information. SIAM J. Imaging Sci. 13(3), 1692-1715 (2020)
[55] Li, Y., Wu, C.L., Duan, Y.: The TV_p regularized Mumford-Shah model for image labeling and segmentation. IEEE Trans. Image Process. 29, 7061-7075 (2020)
[56] Lou, Y., Osher, S., Xin, J.: Computational aspects of constrained L₁-L₂ minimization for compressive sensing. In: Le, T., Hoai, A., Pham, D., Tao, N., Ngoc, T. (eds.) Modelling, Computation and Optimization in Information Systems and Management Sciences, pp. 169-180. Springer (2015)
[57] Lou, Y., Yan, M.: Fast L₁-L₂ minimization via a proximal operator. J. Sci. Comput. 74(2), 767-785 (2018)
[58] Lou, Y., Yin, P., He, Q., Xin, J.: Computing sparse representation in a highly coherent dictionary based on difference of L₁ and L₂. J. Sci. Comput. 64(1), 178-196 (2015)
[59] Lou, Y., Zeng, T., Osher, S., Xin, J.: A weighted difference of anisotropic and isotropic total variation model for image processing. SIAM J. Imaging Sci. 8(3), 1798-1823 (2015)
[60] Luong, Q.-T.: Color in computer vision. In: Chen, C.H., Pau, L.F., Wang, P.S.P. (eds.) Handbook of Pattern Recognition and Computer Vision, pp. 311-368. World Scientific, Singapore (1993)
[61] Martin, D., Fowlkes, C., Tal, D., Malik, J.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Eighth IEEE International Conference on Computer Vision, 2001. ICCV 2001. Proceedings, vol. 2, pp. 416-423. IEEE (2001)
[62] Merriman, B., Bence, J.K., Osher, S.J.: Motion of multiple junctions: a level set approach. J. Comput. Phys. 112(2), 334-363 (1994)
[63] Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 42(5), 577-685 (1989)
[64] Ng, M.K., Chan, R.H., Tang, W.-C.: A fast algorithm for deblurring models with Neumann boundary conditions. SIAM J. Sci. Comput. 21(3), 851-866 (1999)
[65] Ono, S.: L₀ gradient projection. IEEE Trans. Image Process. 26(4), 1554-1564 (2017)
[66] Paschos, G.: Perceptually uniform color spaces for color texture analysis: an empirical evaluation. IEEE Trans. Image Process. 10(6), 932-937 (2001)
[67] Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnam 22(1), 289-355 (1997)
[68] Pham Dinh, T., Le Thi, H.A.: A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8(2), 476-505 (1998)
[69] Pock, T., Chambolle, A., Cremers, D., Bischof, H.: A convex relaxation approach for computing minimal partitions. In: IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009, pp. 810-817. IEEE (2009)
[70] Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford-Shah functional. In: 2009 IEEE 12th International Conference on Computer Vision, pp. 1133-1140. IEEE (2009)
[71] Potts, R.B.: Some generalized order-disorder transformations. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 48, pp. 106-109. Cambridge University Press, Cambridge (1952)
[72] Rahimi, Y., Wang, C., Dong, H., Lou, Y.: A scale-invariant approach for sparse signal recovery. SIAM J. Sci. Comput. 41(6), A3649-A3672 (2019)
[73] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, vol. 317. Springer, Heidelberg (2009)
[74] Storath, M., Weinmann, A.: Fast partitioning of vector-valued images. SIAM J. Imaging Sci. 7(3), 1826-1852 (2014)
[75] Sural, S., Qian, G., Pramanik, S.: Segmentation and histogram generation using the HSV color space for image retrieval. In: Proceedings. International Conference on Image Processing, vol. 2, pp. II-II. IEEE (2002)
[76] Toure, S., Diop, O., Kpalma, K., Maiga, A.S.: Best-performing color space for land-sea segmentation. In: 2018 41st International Conference on Telecommunications and Signal Processing (TSP), pp. 1-5. IEEE (2018)
[77] Vese, L.A., Chan, T.F.: A multiphase level set framework for image segmentation using the Mumford and Shah model. Int. J. Comput. Vision 50(3), 271-293 (2002)
[78] Wang, C., Tao, M., Chuah, C.-N., Nagy, J., Lou, Y.: Minimizing L₁ over L₂ norms on the gradient. Inverse Probl. 38(6), 065011 (2022)
[79] Wang, C., Tao, M., Nagy, J.G., Lou, Y.: Limited-angle CT reconstruction via the L₁/L₂ minimization. SIAM J. Imaging Sci. 14(2), 749-777 (2021)
[80] Wang, C., Yan, M., Rahimi, Y., Lou, Y.: Accelerated schemes for the L₁/L₂ minimization. IEEE Trans. Signal Process. 68, 2660-2669 (2020)
[81] Wang, D., Wang, X.-P.: The iterative convolution-thresholding method (ICTM) for image segmentation. Pattern Recogn. 130, 108794 (2022)
[82] Wang, X.-F., Huang, D.-S., Huan, X.: An efficient local Chan-Vese model for image segmentation. Pattern Recogn. 43(3), 603-618 (2010)
[83] Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1(3), 248-272 (2008)
[84] Wu, T., Mao, Z., Li, Z., Zeng, Y., Zeng, T.: Efficient color image segmentation via quaternion-based L₁/L₂ regularization. J. Sci. Comput. 93(1), 9 (2022)
[85] Wu, T., Shao, J., Gu, X., Ng, M.K., Zeng, T.: Two-stage image segmentation based on nonconvex l₂-l_p approximation and thresholding. Appl. Math. Comput. 403, 126168 (2021)
[86] Wu, T., Zhao, Y., Mao, Z., Shi, L., Li, Z., Zeng, Y.: Image segmentation via Fischer-Burmeister total variation and thresholding. Adv. Appl. Math. Mech. 14(4), 960-988 (2022)
[87] Xu, Z., Chang, X., Xu, F., Zhang, H.: L_1/2 regularization: a thresholding representation theory and a fast solver. IEEE Trans. Neural Netw. Learn. Syst. 23(7), 1013-1027 (2012)
[88] Yin, P., Lou, Y., He, Q., Xin, J.: Minimization of l_1-2 for compressed sensing. SIAM J. Sci. Comput. 37(1), A536-A563 (2015)
[89] You, J., Jiao, Y., Lyu, X.L., Zeng, T.: A nonconvex model with minimax concave penalty for image restoration. J. Sci. Comput. 78(2), 1063-1086 (2019)
[90] Zeng, C., Wu, C.L.: On the edge recovery property of noncovex nonsmooth regularization in image restoration. SIAM J. Numer. Anal. 56(2), 1168-1182 (2018)
[91] Zhang, S., Xin, J.: Minimization of transformed L₁ penalty: closed form representation and iterative thresholding algorithms. Commun. Math. Sci. 15(2), 511-537 (2017)
[92] Zhang, S., Xin, J.: Minimization of transformed L₁ penalty: theory, difference of convex function algorithm, and robust application in compressed sensing. Math. Program. 169(1), 307-336 (2018)