# American Institute of Mathematical Sciences

• Previous Article
Convergence analysis of the weighted state space search algorithm for recurrent neural networks
• NACO Home
• This Issue
• Next Article
Sparse inverse incidence matrices for Schilders' factorization applied to resistor network modeling
2014, 4(3): 209-225. doi: 10.3934/naco.2014.4.209

## Two-step methods for image zooming using duality strategies

 1 College of Science, Nanjing University of Posts and Telecommunications, Nanjing, 210023, China 2 Department of Information and Computing Science, Changsha University, Changsha, 410003, China 3 College of Mathematics and Econometrics, Hunan University, Changsha, 410082, China

Received  November 2013 Revised  July 2014 Published  September 2014

In this paper we propose two two-step methods for image zooming using duality strategies. In the first method, instead of smoothing the normal vector directly as did in the first step of the classical LOT model, we reconstruct the unit normal vector by means of Chambolle's dual formulation. Then, we adopt the split Bregman iteration to obtain the zoomed image in the second step. The second method is based on the TV-Stokes model. By smoothing the tangential vector and imposing the divergence free condition, we propose an image zooming method based on the TV-Stokes model using the dual formulation. Furthermore, we give the convergence analysis of the proposed algorithms. Numerical experiments show the efficiency of the proposed methods.
Citation: Tingting Wu, Yufei Yang, Huichao Jing. Two-step methods for image zooming using duality strategies. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 209-225. doi: 10.3934/naco.2014.4.209
##### References:
 [1] G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations,, Springer-Verlag, (2002). doi: 10.1007/978-0-387-44588-5. [2] T. Barbu and V. Barbu, A PDE approach to image restoration problem with observation on a meager domain,, Nonlinear Analysis: Real World Applications, 13 (2012), 1206. doi: 10.1016/j.nonrwa.2011.09.014. [3] S. Battiato, G. Gallo and F. Stanco, A locally adaptive zooming algorithm for digital images,, Image and Vision Computing, 20 (2002), 805. doi: 10.1016/S0262-8856(02)00089-6. [4] L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming,, USSR Computational Mathematics and Mathematical Physics, 7 (1967), 200. doi: 10.1016/0041-5553(67)90040-7. [5] J. F. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration,, Multiscale Modeling and Simulation, 8 (2009), 337. doi: 10.1137/090753504. [6] Y. Cao, J. X. Yin, Q. Liu and M. H Li, A class of nonlinear parabolic-hyperbolic equations applied to image restoration,, Nonlinear Analysis: Real World Applications, 11 (2010), 253. doi: 10.1016/j.nonrwa.2008.11.004. [7] A. Chambolle, An algorithm for total variation minimization and applications,, J. Math. Imag. Vis., 20 (2004), 89. doi: 10.1023/B:JMIV.0000011325.36760.1e. [8] A. Chambolle, Total variation minimization and a class of binary MRF models,, In EMMCVPR 05, 3757 (2005), 136. doi: 10.1007/11585978_10. [9] A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. [10] T. F. Chan, G. H. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration,, SIAM Journal on Scientific Computing, 20 (1999), 1964. doi: 10.1137/S1064827596299767. [11] T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration,, SIAM Journal on Scientific Computing, 22 (2000), 503. doi: 10.1137/S1064827598344169. [12] T. Chan and J. Shen, Image Processing and Analysis-Variational, PDE, Wavelet, and Stochastic Methods,, SIAM Publisher, (2005). doi: 10.1137/1.9780898717877. [13] D. Q. Chen, L. Z. Cheng and F. Su, A new tv-stokes model with augmented Lagrangian method for image denoising and deconvolution,, Journal of Scientific Computing, 51 (2012), 505. doi: 10.1007/s10915-011-9519-x. [14] H. Z. Chen, J. P. Song and X. C. Tai, A dual algorithm for minimization of the LLT model,, Adv. Comput. Math., 31 (2009), 115. doi: 10.1007/s10444-008-9097-0. [15] F. F. Dong, Z. Liu, D. X. Kong and K. F. Liu, An improved LOT model for image restoration,, J. Math. Imag. Vis., 34 (2009), 89. doi: 10.1007/s10851-008-0132-z. [16] C. A. Elo, Image Denoising Algorithms Based on the Dual Formulation of Total Variation,, Master Thesis, (2009). [17] C. A. Elo, A. Malyshev and T. Rahman, A dual formulation of the TV-Stokes algorithm for image denoising,, In SSVM, 5567 (2009), 307. [18] E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman,, UCLA CAM Report 09-31, (2009), 09. [19] R. Gao, J. P. Song and X. C. Tai, Image zooming algorithm based on partial differential equations technique,, International Journal of Numerical Analysis and Modeling, 6 (2009), 284. [20] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM Journal on Imaging Sciences, 2 (2009), 323. doi: 10.1137/080725891. [21] J. Hahn, C. L. Wu and X. C. Tai, Augmented Lagrangian method for generalized TV-Stokes model,, UCLA CAM Report 10-30, (2010), 10. [22] B. S. He and X. M. Yuan, Linearized alternating direction method with Gaussian back substitution for separable convex programming,, Numerical Algebra, 3 (2013), 247. doi: 10.3934/naco.2013.3.247. [23] B. S. He and X. M. Yuan, On the O(1/n) convergence rate of Douglas-Rachford alternating direction method,, SIAM J. Num. Anal., 50 (2012), 700. doi: 10.1137/110836936. [24] R. Q. Jia, H. Zhao and W. Zhao, Convergence analysis of the Bregman method for the variational model of image denoising,, Appl. Comput. Harmon. Anal., 27 (2009), 367. doi: 10.1016/j.acha.2009.05.002. [25] W. Litvinov, T. Rahman and X. C. Tai, A modified TV-Stokes model for image processing,, SIAM J. Sci. Comput., 33 (2011), 1574. doi: 10.1137/080727506. [26] M. Lysaker, A. Lundervold and X. C. Tai, Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time,, IEEE Trans. Image Process., 12 (2003), 1579. [27] M. Lysaker, S. Osher and X. C. Tai, Noise removal using smoothed normals and surface fitting,, IEEE Trans. Image Process., 13 (2004), 1345. doi: 10.1109/TIP.2004.834662. [28] E. Maeland, On the comparison of interpolation methods,, IEEE Trans. Med. Imag., 7 (1988), 213. [29] S. Osher, M. Burger, D. Goldfarb, J. J. Xu and W. T. Yin, An iterative regularization method for total variation-based image restoration,, Multiscale Model. Simul., 4 (2005), 460. doi: 10.1137/040605412. [30] Z. F. Pang and Y. F. Yang, A projected gradient algorithm based on the augmented Lagrangian strategy for image restoration and texture extraction,, Image and Vision Computing, 29 (2011), 117. [31] Z. F. Pang and Y. F. Yang, A two-step model for image denoising using a duality strategy and surface fitting,, Journal of Computational and Applied Mathematics, 235 (2010), 82. [32] J. A. Parker, R. V. Kenyon and D. E. Troxel, Comparison of interpolating methods for image resampling,, IEEE Trans. Med. Imag., 2 (1983), 31. [33] E. Polidori and J. L. Dugelay, Zooming using iterated function systems,, Fractals, 5 (1997), 111. [34] T. Rahman, X. C. Tai and S. Osher, A TV-Stokes denoising algorithm,, In SSVM, 4485 (2007), 473. doi: 10.1007/978-3-540-72823-8_41. [35] R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1969). [36] L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. [37] P. V. Sankar and L. A. Ferrari, Simple algorithms and architecture for B-spline interpolation,, IEEE Transactions on Pattern Analysis Machine Intelligence, 10 (1988), 271. doi: 10.1109/34.3889. [38] X. C. Tai, S. Borok and J. Hahn, Image denoising using TV-Stokes equation with an orientation-matching minimization,, In SSVM, 5567 (2009), 490. [39] X. C. Tai, S. Osher and R. Holm, Image inpainting using TV-Stokes equation,, In Image Processing Based on Partial Differential Equations, (2006), 3. [40] X. C. Tai and C. L. Wu, Augmented Lagrangian method, dual Methods and split Bregman iteration for ROF model,, In SSVM, 5567 (2009), 502. [41] M. Tao and J. Yang, Alternating direction algorithms for total variation deconvolution in image reconstruction,, TR0918, (2009). [42] T. T. Wu, Y. F. Yang and Z. F. Pang, A modified fixed-point iterative algorithm for image restoration using fourth-order PDE model,, Appl. Num. Math., 62 (2012), 79. doi: 10.1016/j.apnum.2011.10.004. [43] Y. F. Yang, T. T. Wu and Z. F. Pang, Image-zooming technique based on Bregmanized nonlocal total variation regularization,, Optical Engineering, 50 (2011). doi: 10.1117/1.3625417. [44] W. T. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for l1-minimization with applications to compressed sensing,, SIAM J. Imaging Sciences, 1 (2008), 143. doi: 10.1137/070703983. [45] Y. You and M. Kaveh, Fourth-order partial differential equation for noise removal,, IEEE Trans. Image Process., 9 (2000), 1723.

show all references

##### References:
 [1] G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations,, Springer-Verlag, (2002). doi: 10.1007/978-0-387-44588-5. [2] T. Barbu and V. Barbu, A PDE approach to image restoration problem with observation on a meager domain,, Nonlinear Analysis: Real World Applications, 13 (2012), 1206. doi: 10.1016/j.nonrwa.2011.09.014. [3] S. Battiato, G. Gallo and F. Stanco, A locally adaptive zooming algorithm for digital images,, Image and Vision Computing, 20 (2002), 805. doi: 10.1016/S0262-8856(02)00089-6. [4] L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming,, USSR Computational Mathematics and Mathematical Physics, 7 (1967), 200. doi: 10.1016/0041-5553(67)90040-7. [5] J. F. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration,, Multiscale Modeling and Simulation, 8 (2009), 337. doi: 10.1137/090753504. [6] Y. Cao, J. X. Yin, Q. Liu and M. H Li, A class of nonlinear parabolic-hyperbolic equations applied to image restoration,, Nonlinear Analysis: Real World Applications, 11 (2010), 253. doi: 10.1016/j.nonrwa.2008.11.004. [7] A. Chambolle, An algorithm for total variation minimization and applications,, J. Math. Imag. Vis., 20 (2004), 89. doi: 10.1023/B:JMIV.0000011325.36760.1e. [8] A. Chambolle, Total variation minimization and a class of binary MRF models,, In EMMCVPR 05, 3757 (2005), 136. doi: 10.1007/11585978_10. [9] A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. [10] T. F. Chan, G. H. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration,, SIAM Journal on Scientific Computing, 20 (1999), 1964. doi: 10.1137/S1064827596299767. [11] T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration,, SIAM Journal on Scientific Computing, 22 (2000), 503. doi: 10.1137/S1064827598344169. [12] T. Chan and J. Shen, Image Processing and Analysis-Variational, PDE, Wavelet, and Stochastic Methods,, SIAM Publisher, (2005). doi: 10.1137/1.9780898717877. [13] D. Q. Chen, L. Z. Cheng and F. Su, A new tv-stokes model with augmented Lagrangian method for image denoising and deconvolution,, Journal of Scientific Computing, 51 (2012), 505. doi: 10.1007/s10915-011-9519-x. [14] H. Z. Chen, J. P. Song and X. C. Tai, A dual algorithm for minimization of the LLT model,, Adv. Comput. Math., 31 (2009), 115. doi: 10.1007/s10444-008-9097-0. [15] F. F. Dong, Z. Liu, D. X. Kong and K. F. Liu, An improved LOT model for image restoration,, J. Math. Imag. Vis., 34 (2009), 89. doi: 10.1007/s10851-008-0132-z. [16] C. A. Elo, Image Denoising Algorithms Based on the Dual Formulation of Total Variation,, Master Thesis, (2009). [17] C. A. Elo, A. Malyshev and T. Rahman, A dual formulation of the TV-Stokes algorithm for image denoising,, In SSVM, 5567 (2009), 307. [18] E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman,, UCLA CAM Report 09-31, (2009), 09. [19] R. Gao, J. P. Song and X. C. Tai, Image zooming algorithm based on partial differential equations technique,, International Journal of Numerical Analysis and Modeling, 6 (2009), 284. [20] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM Journal on Imaging Sciences, 2 (2009), 323. doi: 10.1137/080725891. [21] J. Hahn, C. L. Wu and X. C. Tai, Augmented Lagrangian method for generalized TV-Stokes model,, UCLA CAM Report 10-30, (2010), 10. [22] B. S. He and X. M. Yuan, Linearized alternating direction method with Gaussian back substitution for separable convex programming,, Numerical Algebra, 3 (2013), 247. doi: 10.3934/naco.2013.3.247. [23] B. S. He and X. M. Yuan, On the O(1/n) convergence rate of Douglas-Rachford alternating direction method,, SIAM J. Num. Anal., 50 (2012), 700. doi: 10.1137/110836936. [24] R. Q. Jia, H. Zhao and W. Zhao, Convergence analysis of the Bregman method for the variational model of image denoising,, Appl. Comput. Harmon. Anal., 27 (2009), 367. doi: 10.1016/j.acha.2009.05.002. [25] W. Litvinov, T. Rahman and X. C. Tai, A modified TV-Stokes model for image processing,, SIAM J. Sci. Comput., 33 (2011), 1574. doi: 10.1137/080727506. [26] M. Lysaker, A. Lundervold and X. C. Tai, Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time,, IEEE Trans. Image Process., 12 (2003), 1579. [27] M. Lysaker, S. Osher and X. C. Tai, Noise removal using smoothed normals and surface fitting,, IEEE Trans. Image Process., 13 (2004), 1345. doi: 10.1109/TIP.2004.834662. [28] E. Maeland, On the comparison of interpolation methods,, IEEE Trans. Med. Imag., 7 (1988), 213. [29] S. Osher, M. Burger, D. Goldfarb, J. J. Xu and W. T. Yin, An iterative regularization method for total variation-based image restoration,, Multiscale Model. Simul., 4 (2005), 460. doi: 10.1137/040605412. [30] Z. F. Pang and Y. F. Yang, A projected gradient algorithm based on the augmented Lagrangian strategy for image restoration and texture extraction,, Image and Vision Computing, 29 (2011), 117. [31] Z. F. Pang and Y. F. Yang, A two-step model for image denoising using a duality strategy and surface fitting,, Journal of Computational and Applied Mathematics, 235 (2010), 82. [32] J. A. Parker, R. V. Kenyon and D. E. Troxel, Comparison of interpolating methods for image resampling,, IEEE Trans. Med. Imag., 2 (1983), 31. [33] E. Polidori and J. L. Dugelay, Zooming using iterated function systems,, Fractals, 5 (1997), 111. [34] T. Rahman, X. C. Tai and S. Osher, A TV-Stokes denoising algorithm,, In SSVM, 4485 (2007), 473. doi: 10.1007/978-3-540-72823-8_41. [35] R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1969). [36] L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. [37] P. V. Sankar and L. A. Ferrari, Simple algorithms and architecture for B-spline interpolation,, IEEE Transactions on Pattern Analysis Machine Intelligence, 10 (1988), 271. doi: 10.1109/34.3889. [38] X. C. Tai, S. Borok and J. Hahn, Image denoising using TV-Stokes equation with an orientation-matching minimization,, In SSVM, 5567 (2009), 490. [39] X. C. Tai, S. Osher and R. Holm, Image inpainting using TV-Stokes equation,, In Image Processing Based on Partial Differential Equations, (2006), 3. [40] X. C. Tai and C. L. Wu, Augmented Lagrangian method, dual Methods and split Bregman iteration for ROF model,, In SSVM, 5567 (2009), 502. [41] M. Tao and J. Yang, Alternating direction algorithms for total variation deconvolution in image reconstruction,, TR0918, (2009). [42] T. T. Wu, Y. F. Yang and Z. F. Pang, A modified fixed-point iterative algorithm for image restoration using fourth-order PDE model,, Appl. Num. Math., 62 (2012), 79. doi: 10.1016/j.apnum.2011.10.004. [43] Y. F. Yang, T. T. Wu and Z. F. Pang, Image-zooming technique based on Bregmanized nonlocal total variation regularization,, Optical Engineering, 50 (2011). doi: 10.1117/1.3625417. [44] W. T. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for l1-minimization with applications to compressed sensing,, SIAM J. Imaging Sciences, 1 (2008), 143. doi: 10.1137/070703983. [45] Y. You and M. Kaveh, Fourth-order partial differential equation for noise removal,, IEEE Trans. Image Process., 9 (2000), 1723.
 [1] Wenye Ma, Stanley Osher. A TV Bregman iterative model of Retinex theory. Inverse Problems & Imaging, 2012, 6 (4) : 697-708. doi: 10.3934/ipi.2012.6.697 [2] Francisco J. Ibarrola, Ruben D. Spies. A two-step mixed inpainting method with curvature-based anisotropy and spatial adaptivity. Inverse Problems & Imaging, 2017, 11 (2) : 247-262. doi: 10.3934/ipi.2017012 [3] Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial & Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543 [4] Angelamaria Cardone, Dajana Conte, Beatrice Paternoster. Two-step collocation methods for fractional differential equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2709-2725. doi: 10.3934/dcdsb.2018088 [5] Raffaele D'Ambrosio, Martina Moccaldi, Beatrice Paternoster. Numerical preservation of long-term dynamics by stochastic two-step methods. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2763-2773. doi: 10.3934/dcdsb.2018105 [6] Philippe Angot, Pierre Fabrie. Convergence results for the vector penalty-projection and two-step artificial compressibility methods. Discrete & Continuous Dynamical Systems - B, 2012, 17 (5) : 1383-1405. doi: 10.3934/dcdsb.2012.17.1383 [7] Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems & Imaging, 2014, 8 (1) : 53-77. doi: 10.3934/ipi.2014.8.53 [8] Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 [9] Yulan Lu, Minghui Song, Mingzhu Liu. Convergence rate and stability of the split-step theta method for stochastic differential equations with piecewise continuous arguments. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 695-717. doi: 10.3934/dcdsb.2018203 [10] Michael Hintermüller, Monserrat Rincon-Camacho. An adaptive finite element method in $L^2$-TV-based image denoising. Inverse Problems & Imaging, 2014, 8 (3) : 685-711. doi: 10.3934/ipi.2014.8.685 [11] Jianhong (Jackie) Shen, Sung Ha Kang. Quantum TV and applications in image processing. Inverse Problems & Imaging, 2007, 1 (3) : 557-575. doi: 10.3934/ipi.2007.1.557 [12] Jiaping Yu, Haibiao Zheng, Feng Shi, Ren Zhao. Two-grid finite element method for the stabilization of mixed Stokes-Darcy model. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 387-402. doi: 10.3934/dcdsb.2018109 [13] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 [14] Jing Xu, Xue-Cheng Tai, Li-Lian Wang. A two-level domain decomposition method for image restoration. Inverse Problems & Imaging, 2010, 4 (3) : 523-545. doi: 10.3934/ipi.2010.4.523 [15] Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171 [16] Wei Wan, Haiyang Huang, Jun Liu. Local block operators and TV regularization based image inpainting. Inverse Problems & Imaging, 2018, 12 (6) : 1389-1410. doi: 10.3934/ipi.2018058 [17] Yangang Chen, Justin W. L. Wan. Numerical method for image registration model based on optimal mass transport. Inverse Problems & Imaging, 2018, 12 (2) : 401-432. doi: 10.3934/ipi.2018018 [18] Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems & Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409 [19] Byung-Soo Lee. Strong convergence theorems with three-step iteration in star-shaped metric spaces. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 371-379. doi: 10.3934/naco.2011.1.371 [20] Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855

Impact Factor: