February  2017, 11(1): 1-23. doi: 10.3934/ipi.2017001

Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours

1. 

Norwegian Defence Research Establishment, P.O. Box 25, NO-2027 Kjeller, Norway

2. 

Department of Mathematics, University of Bergen, P.O. Box 7803, NO-5020 Bergen, Norway

3. 

Department of Mathematics, University of Alabama, Box 870350, Tuscaloosa, AL 35487, USA

* Corresponding author: Wei Zhu

Received  September 2015 Revised  April 2016 Published  January 2017

Fund Project: The first author is supported by the Norwegian Research Council eVita project 214889.

In this paper, we propose an image segmentation model where an $L^1$ variant of the Euler's elastica energy is used as boundary regularization. An interesting feature of this model lies in its preference for convex segmentation contours. However, due to the high order and non-differentiability of Euler's elastica energy, it is nontrivial to minimize the associated functional. As in recent work on the ordinary $L^2$-Euler's elastica model in imaging, we propose using an augmented Lagrangian method to tackle the minimization problem. Specifically, we design a novel augmented Lagrangian functional that deals with the mean curvature term differently than in previous works. The new treatment reduces the number of Lagrange multipliers employed, and more importantly, it helps represent the curvature more effectively and faithfully. Numerical experiments validate the efficiency of the proposed augmented Lagrangian method and also demonstrate new features of this particular segmentation model, such as shape driven and data driven properties.

Citation: Egil Bae, Xue-Cheng Tai, Wei Zhu. Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours. Inverse Problems & Imaging, 2017, 11 (1) : 1-23. doi: 10.3934/ipi.2017001
References:
[1]

L. Ambrosio and S. Masnou, A direct variational approach to a problem arising in image reconstruction, Interfaces Free Bound, 5 (2003), 63-81.   Google Scholar

[2]

L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction, Free boundary problems (Trento, 2002), Internat. Ser. Numer. Math., Birkh{a"}user, Basel,, 147 (2004), 17-26.   Google Scholar

[3]

L. Ambrosio and V. M. Tortorelli, Approximation of functionals depending on jumps by elliptic functionals via Gamma convergence., Comm. Pure Appl. Math., 43 (1990), 999-1036.  doi: 10.1002/cpa.3160430805.  Google Scholar

[4]

E. BaeJ. Shi and X.-C. Tai, Graph Cuts for Curvature Based Image Denoising, IEEE Transactions on Image Processing, 20 (2011), 1199-1210.  doi: 10.1109/TIP.2010.2090533.  Google Scholar

[5]

K. BrediesT. Pock and B. Wirth, A convex, lower semicontinuous approximation of Euler's elastica energy, SIAM J. Math. Anal., 47 (2015), 566-613.  doi: 10.1137/130939493.  Google Scholar

[6]

C. Brito-Loeza and K. Chen, Multigrid algorithm for high order denoising, SIAM J. Imaging. Sciences, 3 (2010), 363-389.  doi: 10.1137/080737903.  Google Scholar

[7]

V. CasellesR. Kimmel and G. Sapiro, Geodesic active contours, Int. J. Comput. Vision, 22 (1997), 61-79.  doi: 10.1109/ICCV.1995.466871.  Google Scholar

[8]

T. Chan and L. A. Vese, Active contours without edges, IEEE Trans. Image Process., 10 (2001), 266-277.  doi: 10.1109/83.902291.  Google Scholar

[9]

T. Chan and S. Esedoglu, Aspects of total variation regularized L1 function approximation, SIAM J. Appl. Math., 65 (2005), 1817-1837.  doi: 10.1137/040604297.  Google Scholar

[10]

T. ChanS. Esedoglu and M. Nikolova, Algorithms for finding global minimizers of denoising and segmentation models, SIAM J. Appl. Math., 66 (2006), 1632-1648.  doi: 10.1137/040615286.  Google Scholar

[11]

T. ChanS. H. Kang and J. H. Shen, Euler's elastica and curvature based inpaintings, SIAM J. Appl. Math., 63 (2002), 564-592.   Google Scholar

[12]

T. Chan and W. Zhu, Level set based shape prior segmentation, Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2005), 1164-1170.  doi: 10.1109/CVPR.2005.212.  Google Scholar

[13]

Y. ChenH. TagareS. ThiruvenkadamF. HuangD. WilsonK. GopinathR. Briggs and E. Geiser, Using prior shapes in geometric active contours in a variational framework, Int. J. Comput. Vision, 50 (2002), 315-328.   Google Scholar

[14]

D. CremersF. TischhauserJ. Weickert and C. Schnorr, Diffusion Snakes: Introducing statistical shape knowledge into the Mumford--Shah functional, Int. J. Comput. Vision, 50 (2002), 295-313.   Google Scholar

[15]

E. De Giorgi, Some remarks on Γ-convergence and least squares methods, in Composite Media and Homogenization Theory, G. Dal Maso and G.F. Dell' Antonio (Eds.) Birkhauser, Boston, (1991), 135–142.  Google Scholar

[16]

M. P. do Carmo, Differential Geometry of Curves and Surfaces, Prentice-Hall, Inc. , 1976.  Google Scholar

[17]

Y. DuanY. WangX.-C. Tai and J. Hahn, A fast augmented Lagrangian method for Euler's elastica model, SSVM 2011, LSCS, 6667 (2012), 144-156.   Google Scholar

[18]

N. El-Zehiry and L. Grady, Fast global optimization of curvature, Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2010), 3257-3264.  doi: 10.1109/CVPR.2010.5540057.  Google Scholar

[19]

M. Elsey and S. Esedoglu, Analogue of the total variation denoising model in the context of geometry processing, SIAM J. Multiscale Modeling and Simulation, 7 (2009), 1549-1573.  doi: 10.1137/080736612.  Google Scholar

[20]

S. Esedoglu and R. March, Segmentation with depth but without detecting junctions, J. Math. Imaging and Vision., 18 (2003), 7-15.  doi: 10.1023/A:1021837026373.  Google Scholar

[21]

M. Hintermüller, C. N. Rautenberg and J. Hahn, Functional-analytic and numerical issues in splitting methods for total variation-based image reconstruction, Inverse Problems, 30 (2014), 055014. Google Scholar

[22]

M. KassA. Witkin and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vision, 1 (1988), 321-331.  doi: 10.1007/BF00133570.  Google Scholar

[23]

M. LeventonW. Grimson and O. Faugeraus, Statistical shape influence in geodesic active contours, Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2000), 316-323.   Google Scholar

[24]

P. L. Lions and B. Mercier, Splitting algorithms for the sume of two nonlinear opertors, SIAM J. Numer. Amal., 16 (1979), 964-979.  doi: 10.1137/0716071.  Google Scholar

[25]

R. March and M. Dozio, A variational method for the recovery of smooth boundaries, Image and Vision Computing, 15 (1997), 705-712.  doi: 10.1016/S0262-8856(97)00002-4.  Google Scholar

[26]

S. Masnou, Disocclusion: A variational approach using level lines, IEEE Trans. Image Process., 11 (2002), 68-76.  doi: 10.1109/83.982815.  Google Scholar

[27]

S. Masnou and J. M. Morel, Level lines based disocclusion, Proc. IEEE Int. Conf. on Image Processing, Chicago, IL, (1998), 259-263.  doi: 10.1109/ICIP.1998.999016.  Google Scholar

[28]

D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685.  doi: 10.1002/cpa.3160420503.  Google Scholar

[29]

M. MyllykoskiR. GlowinskiT. Kärkkäinen and T. Rossi, A new augmented Lagrangian approach for L1-mean curvature image denoising, SIAM J. Imaging Sci., 8 (2015), 95-125.  doi: 10.1137/140962164.  Google Scholar

[30]

M. Nitzberg, D. Mumford and T. Shiota, Filering, Segmentation, and Depth, Lecture Notes in Computer Science, 662, Springer Verlag, Berlin, 1993.  Google Scholar

[31]

S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed-algorithm based on Hamilton-Jacobi formulations, J. Comput. Phys., 79 (1988), 12-49.  doi: 10.1016/0021-9991(88)90002-2.  Google Scholar

[32]

S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2003.  Google Scholar

[33]

D. PengB. MerrimanS. OsherH. K. Zhao and M. Kang, A PDE-based fast local level set method, J. Comput. Phys., 155 (1999), 410-438.  doi: 10.1006/jcph.1999.6345.  Google Scholar

[34]

R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 1 (1976), 97-116.  doi: 10.1287/moor.1.2.97.  Google Scholar

[35]

L. RudinS. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm, Physica D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[36]

T. Schoenemann, F. Kahl and D. Cremers, Curvature Regularity for Region-Based Image Segmentation and Inpainting: A Linear Programming Relaxation, IEEE International Conference on Computer Vision (ICCV), 2009. doi: 10.1109/ICCV.2009.5459209.  Google Scholar

[37]

T. SchoenemannF. KahlS. Masnou and D. Cremers, A linear framework for region-based image segmentation and inpainting involving curvature penalization, Int. J. Comput. Vision, 99 (2012), 53-68.  doi: 10.1007/s11263-012-0518-7.  Google Scholar

[38]

E. Strekalovskiy and D. Cremers, Generalized ordering constraints for multilabel optimization, IEEE International Conference on Computer Vision, ICCV 2011, (2011), 2619-2626.  doi: 10.1109/ICCV.2011.6126551.  Google Scholar

[39]

X. C. TaiJ. Hahn and G. J. Chung, A fast algorithm for Euler's Elastica model using augmented Lagrangian method, SIAM J. Imaging Sciences, 4 (2011), 313-344.  doi: 10.1137/100803730.  Google Scholar

[40]

C. Wu and X. C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, Vectorial TV, and high order models, SIAM J. Imaging Sciences, 3 (2010), 300-339.  doi: 10.1137/090767558.  Google Scholar

[41]

F. YangK. Chen and B. Yu, Homotopy method for a mean curvature-based denoising model, Appl. Numer. Math., 62 (2012), 185-200.  doi: 10.1016/j.apnum.2011.12.001.  Google Scholar

[42]

W. Zhu and T. Chan, A variational model for capturing illusory contours using curvature, J. Math. Imaging Vision, 27 (2007), 29-40.  doi: 10.1007/s10851-006-9695-8.  Google Scholar

[43]

W. Zhu and T. Chan, Image denoising using mean curvature of image surface, SIAM J. Imaging Sciences, 5 (2012), 1-32.  doi: 10.1137/110822268.  Google Scholar

[44]

W. ZhuX. C. Tai and T. Chan, Image segmentation using Euler's elastica as the regularization, J. Sci. Comput., 57 (2013), 414-438.  doi: 10.1007/s10915-013-9710-3.  Google Scholar

[45]

W. ZhuX. C. Tai and T. Chan, Augmented Lagrangian method for a mean curvature based image denoising model, Inverse Probl. Imag., 7 (2013), 1409-1432.  doi: 10.3934/ipi.2013.7.1409.  Google Scholar

show all references

References:
[1]

L. Ambrosio and S. Masnou, A direct variational approach to a problem arising in image reconstruction, Interfaces Free Bound, 5 (2003), 63-81.   Google Scholar

[2]

L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction, Free boundary problems (Trento, 2002), Internat. Ser. Numer. Math., Birkh{a"}user, Basel,, 147 (2004), 17-26.   Google Scholar

[3]

L. Ambrosio and V. M. Tortorelli, Approximation of functionals depending on jumps by elliptic functionals via Gamma convergence., Comm. Pure Appl. Math., 43 (1990), 999-1036.  doi: 10.1002/cpa.3160430805.  Google Scholar

[4]

E. BaeJ. Shi and X.-C. Tai, Graph Cuts for Curvature Based Image Denoising, IEEE Transactions on Image Processing, 20 (2011), 1199-1210.  doi: 10.1109/TIP.2010.2090533.  Google Scholar

[5]

K. BrediesT. Pock and B. Wirth, A convex, lower semicontinuous approximation of Euler's elastica energy, SIAM J. Math. Anal., 47 (2015), 566-613.  doi: 10.1137/130939493.  Google Scholar

[6]

C. Brito-Loeza and K. Chen, Multigrid algorithm for high order denoising, SIAM J. Imaging. Sciences, 3 (2010), 363-389.  doi: 10.1137/080737903.  Google Scholar

[7]

V. CasellesR. Kimmel and G. Sapiro, Geodesic active contours, Int. J. Comput. Vision, 22 (1997), 61-79.  doi: 10.1109/ICCV.1995.466871.  Google Scholar

[8]

T. Chan and L. A. Vese, Active contours without edges, IEEE Trans. Image Process., 10 (2001), 266-277.  doi: 10.1109/83.902291.  Google Scholar

[9]

T. Chan and S. Esedoglu, Aspects of total variation regularized L1 function approximation, SIAM J. Appl. Math., 65 (2005), 1817-1837.  doi: 10.1137/040604297.  Google Scholar

[10]

T. ChanS. Esedoglu and M. Nikolova, Algorithms for finding global minimizers of denoising and segmentation models, SIAM J. Appl. Math., 66 (2006), 1632-1648.  doi: 10.1137/040615286.  Google Scholar

[11]

T. ChanS. H. Kang and J. H. Shen, Euler's elastica and curvature based inpaintings, SIAM J. Appl. Math., 63 (2002), 564-592.   Google Scholar

[12]

T. Chan and W. Zhu, Level set based shape prior segmentation, Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2005), 1164-1170.  doi: 10.1109/CVPR.2005.212.  Google Scholar

[13]

Y. ChenH. TagareS. ThiruvenkadamF. HuangD. WilsonK. GopinathR. Briggs and E. Geiser, Using prior shapes in geometric active contours in a variational framework, Int. J. Comput. Vision, 50 (2002), 315-328.   Google Scholar

[14]

D. CremersF. TischhauserJ. Weickert and C. Schnorr, Diffusion Snakes: Introducing statistical shape knowledge into the Mumford--Shah functional, Int. J. Comput. Vision, 50 (2002), 295-313.   Google Scholar

[15]

E. De Giorgi, Some remarks on Γ-convergence and least squares methods, in Composite Media and Homogenization Theory, G. Dal Maso and G.F. Dell' Antonio (Eds.) Birkhauser, Boston, (1991), 135–142.  Google Scholar

[16]

M. P. do Carmo, Differential Geometry of Curves and Surfaces, Prentice-Hall, Inc. , 1976.  Google Scholar

[17]

Y. DuanY. WangX.-C. Tai and J. Hahn, A fast augmented Lagrangian method for Euler's elastica model, SSVM 2011, LSCS, 6667 (2012), 144-156.   Google Scholar

[18]

N. El-Zehiry and L. Grady, Fast global optimization of curvature, Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2010), 3257-3264.  doi: 10.1109/CVPR.2010.5540057.  Google Scholar

[19]

M. Elsey and S. Esedoglu, Analogue of the total variation denoising model in the context of geometry processing, SIAM J. Multiscale Modeling and Simulation, 7 (2009), 1549-1573.  doi: 10.1137/080736612.  Google Scholar

[20]

S. Esedoglu and R. March, Segmentation with depth but without detecting junctions, J. Math. Imaging and Vision., 18 (2003), 7-15.  doi: 10.1023/A:1021837026373.  Google Scholar

[21]

M. Hintermüller, C. N. Rautenberg and J. Hahn, Functional-analytic and numerical issues in splitting methods for total variation-based image reconstruction, Inverse Problems, 30 (2014), 055014. Google Scholar

[22]

M. KassA. Witkin and D. Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vision, 1 (1988), 321-331.  doi: 10.1007/BF00133570.  Google Scholar

[23]

M. LeventonW. Grimson and O. Faugeraus, Statistical shape influence in geodesic active contours, Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (2000), 316-323.   Google Scholar

[24]

P. L. Lions and B. Mercier, Splitting algorithms for the sume of two nonlinear opertors, SIAM J. Numer. Amal., 16 (1979), 964-979.  doi: 10.1137/0716071.  Google Scholar

[25]

R. March and M. Dozio, A variational method for the recovery of smooth boundaries, Image and Vision Computing, 15 (1997), 705-712.  doi: 10.1016/S0262-8856(97)00002-4.  Google Scholar

[26]

S. Masnou, Disocclusion: A variational approach using level lines, IEEE Trans. Image Process., 11 (2002), 68-76.  doi: 10.1109/83.982815.  Google Scholar

[27]

S. Masnou and J. M. Morel, Level lines based disocclusion, Proc. IEEE Int. Conf. on Image Processing, Chicago, IL, (1998), 259-263.  doi: 10.1109/ICIP.1998.999016.  Google Scholar

[28]

D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685.  doi: 10.1002/cpa.3160420503.  Google Scholar

[29]

M. MyllykoskiR. GlowinskiT. Kärkkäinen and T. Rossi, A new augmented Lagrangian approach for L1-mean curvature image denoising, SIAM J. Imaging Sci., 8 (2015), 95-125.  doi: 10.1137/140962164.  Google Scholar

[30]

M. Nitzberg, D. Mumford and T. Shiota, Filering, Segmentation, and Depth, Lecture Notes in Computer Science, 662, Springer Verlag, Berlin, 1993.  Google Scholar

[31]

S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed-algorithm based on Hamilton-Jacobi formulations, J. Comput. Phys., 79 (1988), 12-49.  doi: 10.1016/0021-9991(88)90002-2.  Google Scholar

[32]

S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2003.  Google Scholar

[33]

D. PengB. MerrimanS. OsherH. K. Zhao and M. Kang, A PDE-based fast local level set method, J. Comput. Phys., 155 (1999), 410-438.  doi: 10.1006/jcph.1999.6345.  Google Scholar

[34]

R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 1 (1976), 97-116.  doi: 10.1287/moor.1.2.97.  Google Scholar

[35]

L. RudinS. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm, Physica D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[36]

T. Schoenemann, F. Kahl and D. Cremers, Curvature Regularity for Region-Based Image Segmentation and Inpainting: A Linear Programming Relaxation, IEEE International Conference on Computer Vision (ICCV), 2009. doi: 10.1109/ICCV.2009.5459209.  Google Scholar

[37]

T. SchoenemannF. KahlS. Masnou and D. Cremers, A linear framework for region-based image segmentation and inpainting involving curvature penalization, Int. J. Comput. Vision, 99 (2012), 53-68.  doi: 10.1007/s11263-012-0518-7.  Google Scholar

[38]

E. Strekalovskiy and D. Cremers, Generalized ordering constraints for multilabel optimization, IEEE International Conference on Computer Vision, ICCV 2011, (2011), 2619-2626.  doi: 10.1109/ICCV.2011.6126551.  Google Scholar

[39]

X. C. TaiJ. Hahn and G. J. Chung, A fast algorithm for Euler's Elastica model using augmented Lagrangian method, SIAM J. Imaging Sciences, 4 (2011), 313-344.  doi: 10.1137/100803730.  Google Scholar

[40]

C. Wu and X. C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, Vectorial TV, and high order models, SIAM J. Imaging Sciences, 3 (2010), 300-339.  doi: 10.1137/090767558.  Google Scholar

[41]

F. YangK. Chen and B. Yu, Homotopy method for a mean curvature-based denoising model, Appl. Numer. Math., 62 (2012), 185-200.  doi: 10.1016/j.apnum.2011.12.001.  Google Scholar

[42]

W. Zhu and T. Chan, A variational model for capturing illusory contours using curvature, J. Math. Imaging Vision, 27 (2007), 29-40.  doi: 10.1007/s10851-006-9695-8.  Google Scholar

[43]

W. Zhu and T. Chan, Image denoising using mean curvature of image surface, SIAM J. Imaging Sciences, 5 (2012), 1-32.  doi: 10.1137/110822268.  Google Scholar

[44]

W. ZhuX. C. Tai and T. Chan, Image segmentation using Euler's elastica as the regularization, J. Sci. Comput., 57 (2013), 414-438.  doi: 10.1007/s10915-013-9710-3.  Google Scholar

[45]

W. ZhuX. C. Tai and T. Chan, Augmented Lagrangian method for a mean curvature based image denoising model, Inverse Probl. Imag., 7 (2013), 1409-1432.  doi: 10.3934/ipi.2013.7.1409.  Google Scholar

Figure 1.  Two vectors $\nu$, $\mathbf{a}$ and a possible unit vector $\mathbf{b}$ that maximizes the function $\psi(\mathbf{b})$.
Figure 2.  The original image (the first row) and the segmentation results (the second row) with different curvature parameter $b$. Two features can be observed from these results: 1) data driven property: as the parameter $b$ increases, objects of relatively small size will be omitted in the final segmentation; 2) shape driven property: with the same parameter $b$, among those objects with equal areas, the one without a convex shape is taken out from the final segmentation (see the staircase-like shape). In this experiment, the other parameters are: $a=10^{-4},r_{1}=50,r_{2}=20,r_{3}=5$
Figure 3.  The original image and the segmentation result. The result demonstrates that the invisible part of the hat can be restored by the proposed segmentation model with a relatively large curvature parameter $b$. In this experiment, the parameters are $a=10^{-3},b=80, r_{1}=60,r_{2}=40,r_{3}=10$
Figure 4.  The original image and the segmentation result. The result shows that only the ''cap" part of the mushroom is captured while the ''stem" is omitted in order to form a convex segmentation contour by the proposed segmentation model with a relatively large curvature parameter $b$. In this experiment, the parameters are $a=10^{-4},b=18, r_{1}=20,r_{2}=10,r_{3}=5$
Figure 5.  The effect of the curvature parameter $b$ on the final segmentation results. One may observe that the smaller the parameter $b$ is chosen, the more salient the indentation of the hat would be. In these two experiments, all the other parameters are the same as those in Fig. 3
Figure 6.  The effect of the curvature parameter $b$ on the final segmentation results. One can see that once the parameter $b$ is chosen smaller, more part of the stem will be allowed in the final segmentation. In these two experiments, all the other parameters are the same as those in Fig. 4
Figure 7.  The plots of relative residuals (Eq. 43), relative errors in Lagrange multipliers (Eq. 44), and relative error in $u^{k}$ (Eq. 45) for the two examples ''hat" (Left column) and ''mushroom" (Right column). These plots demonstrate the convergence of the iteration process
Table 1.  Augmented Lagrangian method for the $ECV$-$L^{1}$ segmentation model
1. Initialization: $\phi^{0}$, $q^{0}$, $\mathbf{p}^{0}$, $\mathbf{n}^{0}$, and $\mathbf{\lambda}_{1}^{0}$, $\lambda_{2}^{0}$, $\mathbf{\lambda}_{3}^{0}$.
      For $k \geq 1$, do the following steps (Step $2\sim 4$):
2. Compute an approximate minimizer $(\phi^{k},q^{k},\mathbf{p}^{k},\mathbf{n}^{k})$ of the augmented Lagrangian functional with the fixed Lagrangian multiplier $\mathbf{\lambda}_{1}^{k-1}$, $\lambda_{2}^{k-1}$, $\mathbf{\lambda}_{3}^{k-1}$:
$(32)\;\;\;\;\;\;\;\;\;\;(\phi^{k},q^{k},\mathbf{p}^{k},\mathbf{n}^{k}) \approx \mbox{argmin } \mathcal{L}(\phi,q,\mathbf{p},\mathbf{n}, \mathbf{\lambda}_{1}^{k-1}, \lambda_{2}^{k-1}, \mathbf{\lambda}_{3}^{k-1}).$
3. Update the Lagrangian multipliers
                  $\mathbf{\lambda}_{1}^{k} = \mathbf{\lambda}_{1}^{k-1}+r_{1}(\mathbf{p}^{k}-\nabla \phi^{k})$
                  $\lambda_{2}^{k} = \lambda_{2}^{k-1}+r_{2}(q^{k}-\nabla\cdot \mathbf{n}^{k})$
                  $\mathbf{\lambda}_{3}^{k} = \mathbf{\lambda}_{3}^{k-1}+r_{3}(|\mathbf{p}|\mathbf{n}^{k}-\mathbf{p}^{k}),$
4. Measure the relative residuals and stop the iteration if they are smaller than a threshold $\epsilon_{r}$.
1. Initialization: $\phi^{0}$, $q^{0}$, $\mathbf{p}^{0}$, $\mathbf{n}^{0}$, and $\mathbf{\lambda}_{1}^{0}$, $\lambda_{2}^{0}$, $\mathbf{\lambda}_{3}^{0}$.
      For $k \geq 1$, do the following steps (Step $2\sim 4$):
2. Compute an approximate minimizer $(\phi^{k},q^{k},\mathbf{p}^{k},\mathbf{n}^{k})$ of the augmented Lagrangian functional with the fixed Lagrangian multiplier $\mathbf{\lambda}_{1}^{k-1}$, $\lambda_{2}^{k-1}$, $\mathbf{\lambda}_{3}^{k-1}$:
$(32)\;\;\;\;\;\;\;\;\;\;(\phi^{k},q^{k},\mathbf{p}^{k},\mathbf{n}^{k}) \approx \mbox{argmin } \mathcal{L}(\phi,q,\mathbf{p},\mathbf{n}, \mathbf{\lambda}_{1}^{k-1}, \lambda_{2}^{k-1}, \mathbf{\lambda}_{3}^{k-1}).$
3. Update the Lagrangian multipliers
                  $\mathbf{\lambda}_{1}^{k} = \mathbf{\lambda}_{1}^{k-1}+r_{1}(\mathbf{p}^{k}-\nabla \phi^{k})$
                  $\lambda_{2}^{k} = \lambda_{2}^{k-1}+r_{2}(q^{k}-\nabla\cdot \mathbf{n}^{k})$
                  $\mathbf{\lambda}_{3}^{k} = \mathbf{\lambda}_{3}^{k-1}+r_{3}(|\mathbf{p}|\mathbf{n}^{k}-\mathbf{p}^{k}),$
4. Measure the relative residuals and stop the iteration if they are smaller than a threshold $\epsilon_{r}$.
Table 2.  Alternating minimization method for solving the subproblems.
1. Initialization: $\widetilde{\phi}^{0}=\phi^{k-1}$, $\widetilde{q}^{0}=q^{k-1}$, $\widetilde{\mathbf{p}}^{0}=\mathbf{p}^{k-1}$, and $\widetilde{\mathbf{n}}^{0}=\mathbf{n}^{k-1}$.
2. For fixed Lagrangian multiplier $\mathbf{\lambda}_{1}=\mathbf{\lambda}_{1}^{k-1}$, $\lambda_{2}=\lambda_{2}^{k-1}$, and $\mathbf{\lambda}_{3}=\mathbf{\lambda}_{3}^{k-1}$, solve the following subproblems :
$(33)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{\phi}^{1} = \mbox{argmin } \mathcal{L}(\phi,\widetilde{q}^{0},\widetilde{\mathbf{p}}^{0},\widetilde{\mathbf{n}}^{0}, \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
$(34)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{q}^{1} = \mbox{argmin } \mathcal{L}(\widetilde{\phi}^{1},q,\widetilde{\mathbf{p}}^{0},\widetilde{\mathbf{n}}^{0}, \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
$(35)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{\mathbf{p}}^{1} = \mbox{argmin } \mathcal{L}(\widetilde{\phi}^{1},\widetilde{q}^{1},\mathbf{p},\widetilde{\mathbf{n}}^{0}, , \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
$(36)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{\mathbf{n}}^{1} = \mbox{argmin } \mathcal{L}(\widetilde{\phi}^{1},\widetilde{q}^{1},\widetilde{\mathbf{p}}^{1},\mathbf{n}, \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
3. $(\phi^{k},q^{k},\mathbf{p}^{k},\mathbf{n}^{k})=(\widetilde{\phi}^{1},\widetilde{q}^{1},\widetilde{\mathbf{p}}^{1}, \widetilde{\mathbf{n}}^{1})$.
1. Initialization: $\widetilde{\phi}^{0}=\phi^{k-1}$, $\widetilde{q}^{0}=q^{k-1}$, $\widetilde{\mathbf{p}}^{0}=\mathbf{p}^{k-1}$, and $\widetilde{\mathbf{n}}^{0}=\mathbf{n}^{k-1}$.
2. For fixed Lagrangian multiplier $\mathbf{\lambda}_{1}=\mathbf{\lambda}_{1}^{k-1}$, $\lambda_{2}=\lambda_{2}^{k-1}$, and $\mathbf{\lambda}_{3}=\mathbf{\lambda}_{3}^{k-1}$, solve the following subproblems :
$(33)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{\phi}^{1} = \mbox{argmin } \mathcal{L}(\phi,\widetilde{q}^{0},\widetilde{\mathbf{p}}^{0},\widetilde{\mathbf{n}}^{0}, \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
$(34)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{q}^{1} = \mbox{argmin } \mathcal{L}(\widetilde{\phi}^{1},q,\widetilde{\mathbf{p}}^{0},\widetilde{\mathbf{n}}^{0}, \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
$(35)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{\mathbf{p}}^{1} = \mbox{argmin } \mathcal{L}(\widetilde{\phi}^{1},\widetilde{q}^{1},\mathbf{p},\widetilde{\mathbf{n}}^{0}, , \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
$(36)\;\;\;\;\;\;\;\;\;\;\;\;\widetilde{\mathbf{n}}^{1} = \mbox{argmin } \mathcal{L}(\widetilde{\phi}^{1},\widetilde{q}^{1},\widetilde{\mathbf{p}}^{1},\mathbf{n}, \mathbf{\lambda}_{1}, \lambda_{2}, \mathbf{\lambda}_{3}) $
3. $(\phi^{k},q^{k},\mathbf{p}^{k},\mathbf{n}^{k})=(\widetilde{\phi}^{1},\widetilde{q}^{1},\widetilde{\mathbf{p}}^{1}, \widetilde{\mathbf{n}}^{1})$.
Table 3.  The presentation of the sizes, the numbers of iterations, and the computational time for the two real images.
ImageSize of imageNumber of iterationsTime (sec)
Fig. 3$321\times 481$1600472.3
Fig. 4$481\times 321$1600480.8
ImageSize of imageNumber of iterationsTime (sec)
Fig. 3$321\times 481$1600472.3
Fig. 4$481\times 321$1600480.8
[1]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[2]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[3]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020031

[4]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[5]

Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168

[6]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[7]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[8]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[9]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[10]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[11]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[12]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457

[13]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[14]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[15]

Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316

[16]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[17]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[18]

Zhouchao Wei, Wei Zhang, Irene Moroz, Nikolay V. Kuznetsov. Codimension one and two bifurcations in Cattaneo-Christov heat flux model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020344

[19]

Shuang Chen, Jinqiao Duan, Ji Li. Effective reduction of a three-dimensional circadian oscillator model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020349

[20]

Barbora Benešová, Miroslav Frost, Lukáš Kadeřávek, Tomáš Roubíček, Petr Sedlák. An experimentally-fitted thermodynamical constitutive model for polycrystalline shape memory alloys. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020459

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (76)
  • HTML views (169)
  • Cited by (14)

Other articles
by authors

[Back to Top]