Advanced Search
Article Contents
Article Contents

Nonlinear diffusion based image segmentation using two fast algorithms

  • * Corresponding author: Lu Tan

    * Corresponding author: Lu Tan 
Abstract Full Text(HTML) Figure(7) / Table(4) Related Papers Cited by
  • In this paper, a new variational model is proposed for image segmentation based on active contours, nonlinear diffusion and level sets. It includes a Chan-Vese model-based data fitting term and a regularized term that uses the potential functions (PF) of nonlinear diffusion. The former term can segment the image by region partition instead of having to rely on the edge information. The latter term is capable of automatically preserving image edges as well as smoothing noisy regions. To improve computational efficiency, the implementation of the proposed model does not directly solve the high order nonlinear partial differential equations and instead exploit the efficient alternating direction method of multipliers (ADMM), which allows the use of fast Fourier transform (FFT), analytical generalized soft thresholding equation, and projection formula. In particular, we creatively propose a new fast algorithm, normal vector projection method (NVPM), based on alternating optimization method and normal vector projection. Its stability can be the same as ADMM and it has faster convergence ability. Extensive numerical experiments on grey and colour images validate the effectiveness of the proposed model and the efficiency of the algorithms.

    Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Effects of our model. The first row: initial curves. The second row: the results obtained by ADMM and NVPM. (a2) and (b2) from ADMM, (c2) and (d2) from NVPM

    Figure 2.  Effects of GAC and PSAC modelsw. The first and the fourth column: initial curves. The second and the fifth column: final curves of GAC model. The third and the sixth column: final curves of PSAC model

    Figure 3.  Plots of parametric errors and energy curves. The first row is obtained by ADMM. The second row is obtained by NVPM

    Figure 4.  Effects of our model, GAC model and PSAC model. The first column: initial curves. The second column: the results of our model obtained by ADMM (top) and NVPM (bottom). The third column: the results of GAC model. The last column: the results of PSAC model

    Figure 5.  Non-threshold solutions of our methods. The first column: final results of $ \phi $. The second column: zoomed small sub-regions (red rectangles in (c1) and (d1)) for detail comparison

    Figure 6.  Effects of our model, GAC model and PSAC model on colour images. (a1), (b1) and (c1): initial curves. (a2), (b2) and (c2): results of our model via ADMM (a2), NVPM (b2) and NVPM* (c2). (a3), (b3) and (c3): GAC model results. (a4), (b4) and (c4): results of PSAC model

    Figure 7.  Plots of parametric errors and energy curves. The first row is obtained by our model using ADMM. The second row is obtained by our model using NVPM*

    Table 1.  Potential functions for the regularization term

    $ \varphi(|\nabla\phi|) $ source
    (ⅰ) $ |\nabla\phi|^p, 0<p\leq2 $ [21]
    (ⅱ) $ \sqrt{1+|\nabla\phi|^2} $ [31]
    (ⅲ) $ \sqrt{1+|\nabla\phi|^2}-1 $ [1]
    (ⅳ) $ \frac{|\nabla\phi|^2}{1+|\nabla\phi|^2} $ [15]
    (ⅴ) $ \log(1+|\nabla\phi|^2) $ [19]
    (ⅵ) $ \log(\cosh(|\nabla\phi|)) $ [13]
    (ⅶ) $ 1-\lambda^2e^{-\frac{|\nabla\phi|^2}{2\lambda^2}} $ [22]
    (ⅷ) $ \lambda^2\log(1+\frac{|\nabla\phi|^2}{\lambda^2}) $ [23]
    (ⅸ) $ 2\lambda^2(\sqrt{1+\frac{|\nabla\phi|^2}{\lambda^2}}-1) $ [12]
    (ⅹ) $ |\nabla\phi|-\alpha\log(1+\frac{|\nabla\phi|}{\alpha}) $ [17]
     | Show Table
    DownLoad: CSV

    Table 2.  Comparisons of iterations and time using different methods

    Image Methods Iterations Time (sec)
    Fig. 1 (a2)
    PF (ⅰ)
    ADMM 3 0.062
    NVPM 3 0.047
    NVPM* 3 0.039
    Fig. 1 (b2)
    PF (ⅲ)
    ADMM 7 0.162
    NVPM 6 0.132
    NVPM* 6 0.122
    Fig. 1 (c2)
    PF (ⅴ)
    ADMM 5 0.155
    NVPM 5 0.145
    NVPM* 5 0.141
    Fig. 1 (d2)
    PF (ⅶ)
    ADMM 3 0.094
    NVPM 3 0.083
    NVPM* 3 0.076
     | Show Table
    DownLoad: CSV

    Table 3.  Comparisons of iterations and time using different methods

    Image Methods Iterations Time (sec)
    Fig. 4 (a2)
    PF (ⅱ)
    ADMM 6 0.184
    NVPM 6 0.178
    NVPM* 6 0.175
    Fig. 4 (b2)
    PF (ⅳ)
    ADMM 16 0.215
    NVPM 9 0.118
    NVPM* 8 0.109
     | Show Table
    DownLoad: CSV

    Table 4.  Comparisons of iterations and time using different methods

    Image Methods Iterations Time (sec)
    Fig. 6 (a2)
    PF (ⅵ)
    ADMM 6 0.336
    NVPM 5 0.273
    NVPM* 5 0.264
    Fig. 6 (a2)
    PF (ⅷ)
    ADMM 7 0.389
    NVPM 7 0.318
    NVPM* 7 0.296
    Fig. 6 (b2)
    PF (ⅸ)
    ADMM 5 0.175
    NVPM 5 0.168
    NVPM* 5 0.162
    Fig. 6 (b2)
    PF (ⅹ)
    ADMM 5 0.183
    NVPM 5 0.172
    NVPM* 5 0.163
    Fig. 6 (c2)
    PF (ⅵ)
    ADMM 11 2.389
    NVPM 11 2.052
    NVPM* 11 2.043
    Fig. 6 (c2)
    PF (ⅸ)
    ADMM 10 1.998
    NVPM 10 1.805
    NVPM* 9 1.626
     | Show Table
    DownLoad: CSV
  • [1] R. Acar and C. R. Vogel, Analysis of bounded variation penalty methods for ill-posed problems, Inverse Problems, 10 (1994), 1217-1229.  doi: 10.1088/0266-5611/10/6/003.
    [2] R. AndreaniL. D. Secchin and P. J. Silva, Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 28 (2018), 2574-2600.  doi: 10.1137/17M1125698.
    [3] G. Aubert and P. Kornprobst, Mathematical Problems in Images Processing, Applied mathematical sciences, 2006.
    [4] G. Aubert and L. A. Vese, Variational method in image recovery, SIAM Journal on Numerical Analysis, 34 (1997), 1948-1979.  doi: 10.1137/S003614299529230X.
    [5] L. Ambrosio and V. M. Tortorelli, Approximation of functional depending on jumps by elliptic functional via Gamma-convergence, Communications on Pure and Applied Mathematics, 43 (1990), 999-1036.  doi: 10.1002/cpa.3160430805.
    [6] E. BaeX. C. Tai and W. Zhu, Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours, Inverse Problems and Imaging, 11 (2017), 1-23.  doi: 10.3934/ipi.2017001.
    [7] X. BressonS. EsedogluP. VandergheynstJ. P. 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.
    [8] V. CasellesR. Kimmel and G. Sapiro, Geodesic active contours, International Journal of Computer Vision, 22 (1997), 61-79.  doi: 10.1109/ICCV.1995.466871.
    [9] F. CatteP.-L. LionsJ.-M. Morel and T. Coll, Image selective smoothing and edge detection by nonlinear diffusion, SIAM Journal on Numerical Analysis, 29 (1992), 182-193.  doi: 10.1137/0729012.
    [10] T. F. ChanB. Y. Sandberg and L. A. Vese, Active contours without edges for vector-valued images, Journal of Visual Communication and Image Representation, 11 (2000), 130-141.  doi: 10.1006/jvci.1999.0442.
    [11] T. F. Chan and L. A. Vese, Active Contours without Edges, IEEE Transactions on Image Processing, 10 (2001), 266-277.  doi: 10.1109/83.902291.
    [12] P. CharbonnierL. Blanc-FeraudG. Aubert and M. Barlaud, Two deterministic half-quadratic regularization algorithms for computed imaging, IEEE International Conference on Image Processing, 2 (1994), 168-172.  doi: 10.1109/ICIP.1994.413553.
    [13] P. CharbonnierL. Blanc-FeraudG. Aubert and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Transactions on Image Processing, 6 (1997), 298-311.  doi: 10.1109/83.551699.
    [14] L. J. Deng, R. Glowinski and X.-C. Tai, A New Operator Splitting Method for Euler's Elastica Model, preprint, arXiv: 1811.07091.
    [15] S. Geman and D. E. McClure, Statistical methods for tomographic image reconstruction, Bulletin of the ISI, 52 (1987), 5-21. 
    [16] T. GoldsteinB. O'DonoghueS. Setzer and R. Baraniuk, Fast alternating direction optimization methods, SIAM Journal on Imaging Sciences, 7 (2014), 1588-1623.  doi: 10.1137/120896219.
    [17] P. J. Green, Bayesian reconstructions from emission tomography data using a modified EM algorithm, IEEE Transactions on Medical Imaging, 9 (1990), 84-93.  doi: 10.1109/42.52985.
    [18] L. Gun, L. Cuihua and Z. Yingpan, et al., An improved speckle-reduction algorithm for SAR images based on anisotropic diffusion, Multimedia Tools and Applications, 76 (2017), 17615-17632. doi: 10.1007/s11042-015-2810-3.
    [19] T. Hebert and R. Leahy, A generalized EM algorithm for 3-D Bayesian reconstruction from Poisson data using Gibbs priors, IEEE Transactions on Medical Imaging, 8 (1989), 194-202.  doi: 10.1109/42.24868.
    [20] 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.
    [21] M. Nikolova, Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers, SIAM Journal on Numerical Analysis, 40 (2002), 965-994.  doi: 10.1137/S0036142901389165.
    [22] M. Nikolova, Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares, Multiscale Modeling & Simulation, 4 (2005), 960-991.  doi: 10.1137/040619582.
    [23] P. Perona and J. Malik, Scale space and edge detection using anisotropic diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, 12 (1990), 629-639.  doi: 10.1109/34.56205.
    [24] H. K. RafsanjaniM. H. Sedaaghi and S. Saryazdi, An adaptive diffusion coefficient selection for image denoising, Digital Signal Processing, 64 (2017), 71-82.  doi: 10.1016/j.dsp.2017.02.004.
    [25] L. Tan, L. Li, W. Liu, et al., A Novel Euler's Elastica based Segmentation Approach for Noisy Images via using the Progressive Hedging Algorithm, preprint, arXiv: 1902.07402.
    [26] L. Tan, W. Liu and L. Li et al., A fast computational approach for illusory contour reconstruction, Multimedia Tools and Applications, 78 (2019), 10449-10472. doi: 10.1007/s11042-018-6546-8.
    [27] L. TanW. Liu and Z. Pan, Color image restoration and inpainting via multi-channel total curvature, Applied Mathematical Modelling, 61 (2018), 280-299.  doi: 10.1016/j.apm.2018.04.017.
    [28] L. TanZ. PanW. LiuJ. DuanW. Wei and G. Wang, Image segmentation with depth information via simplified variational level set formulation, Journal of Mathematical Imaging and Vision, 60 (2018), 1-17.  doi: 10.1007/s10851-017-0735-3.
    [29] L. Tan, W. Wei and Z. Pan, et al., A High-order Model of TV and Its Augmented Lagrangian Algorithm, Applied Mechanics and Materials, 568 (2014), 726-733. doi: 10.4028/www.scientific.net/AMM.568-570.726.
    [30] L. A. Vese and T. F. Chan, A multiphase level set the framework for image segmentation using the Mumford and Shah model, International journal of computer vision, 50 (2002), 271-293. 
    [31] C. R. Vogel and M. E. Oman, Iterative methods for total variation denoising, SIAM Journal on Scientific Computing, 17 (1996), 227-238.  doi: 10.1137/0917016.
    [32] B. Wang, X. Yuan and X. Gao et al., A hybrid level set with semantic shape constraint for object segmentation, IEEE Transactions on Cybernetics, 49 (2019), 1558-1569. doi: 10.1109/TCYB.2018.2799999.
    [33] S. Yan, X. Tai, J. Liu, et al., Convexity Shape Prior for Level Set based Image Segmentation Method, preprint, arXiv: 1805.08676.
    [34] M. Yashtini and S. H. Kang, A fast relaxed normal two split method and an effective weighted TV approach for Euler's elastica image inpainting, SIAM Journal on Imaging Sciences, 9 (2016), 1552-1581.  doi: 10.1137/16M1063757.
    [35] S. ZhengZ. XuH. YangJ. Song and Z. Pan, Comparisons of different methods for balanced data classification under the discrete non-local total variational framework, Mathematical Foundations of Computing, 2 (2019), 11-28.  doi: 10.3934/mfc.2019002.
    [36] Z. Zhou, Z. Guo and D. Zhang, et al., A nonlinear diffusion equation-based model for ultrasound speckle noise removal, Journal of Nonlinear Science, 28 (2018), 443-470. doi: 10.1007/s00332-017-9414-1.
    [37] W. Zhu, A numerical study of a mean curvature denoising model using a novel augmented Lagrangian method, Inverse Problems and Imaging, 11 (2017), 975-996.  doi: 10.3934/ipi.2017045.
  • 加载中




Article Metrics

HTML views(2542) PDF downloads(287) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint