Gradient Projection Algorithm for Total Variation Image Restoration by Adaptive Steplength Selection Rules
-
摘要: 针对图像去噪问题，本文基于全变差对偶公式提出一个新的梯度投影算法.算法采用改进的非单调线搜索和自适应BB（Barzilai-Borwein）步长，有效地改善了Chambolle梯度投影算法收敛慢的缺点.数值结果表明新算法优于一些已有的梯度投影算法.Abstract: We propose a new gradient projection algorithm for image denoising based on the dual of total variation. The new method exploits nonmonotone line-search and adaptive steplength selection based on strategies for alternation of the well-known Barzilai-Borwein rules. The proposed method is much faster than the Chambolle's gradient projection algorithm. Numerical results illustrate the efficiency of this method.
-
图 2 Boat(1 024×1 024)梯度投影的相对范数vs. CPU时间(秒)
Fig. 2 Relative norm of projected gradient vs. CPU time (s) of Boat (1 024×1 024)
图 3 Cameraman( $Tol\, =\, 10^{-4}$ )和Barbara( $Tol\, =\, 10^{-6})$ MGPSSABB的去噪结果
Fig. 3 Denoising results of MGPSSABB of Cameraman ( $Tol\, =\, 10^{-4}$ ) and Barbara ( $Tol\, =\, 10^{-6}$ )
图 4 四个算法的对偶间隙vs. CPU时间(秒) (Tol=10−6)
Fig. 4 Duality gap vs. CPU time(s) for four algorithms (Tol=10−6)
表 1 数值结果
Table 1 Numerical results
Image Algorithm Niter Time(s) RMSE Shape(128×128) Chambolle 737 2.06 0.0739 Chambolle1 592 1.86 0.0738 MChambolle 196 0.81 0.0412 GPSSABB 182 0.70 0.0414 MGPSSABB 130 0.61 0.0414 Lena(256×256) Chambolle 352 5.79 0.0829 Chambolle1 272 4.73 0.0827 MChambolle 129 3.62 0.0221 GPSSABB 152 4.13 0.0214 MGPSSABB 85 2.34 0.0214 Peppers(512×512) Chambolle 389 35.80 0.0525 Chambolle1 298 26.27 0.0520 MChambolle 124 19.77 0.0520 GPSSABB 124 19.67 0.0079 MGPSSABB 92 15.79 0.0079 Boat(1024×1024) Chambolle 388 141.80 0.0078 Chambolle1 300 117.05 0.0078 MChambolle 140 101.66 0.0078 GPSSABB 156 107.90 0.0078 MGPSSABB 97 67.16 0.0078 
下载: 导出CSV
表 2 Cameraman (256 × 256)迭代步数和CPU时间(秒)
Table 2 Number of iterations (Iter) and CPU time (s) of Cameraman (256 × 256)
Algorithms Tol=10−2 Tol=10−3 Tol=10−4 Tol=10−6 Iter Time(s) Iter Time(s) Iter Time(s) Iter Time(s) Chambolle 27 0.45 163 3.18 822 16.04 14625 271.89 GPCL 32 0.59 114 1.98 549 10.19 10116 187.28 GPLS 18 0.53 132 5.38 607 26.22 12100 550.32 GPBBM 20 0.56 128 3.24 596 16.99 11032 295.31 GPBBM(3) 20 0.58 72 1.78 292 7.53 3186 79.15 SQPBBM 14 0.50 43 1.95 167 7.66 2532 105.18 GPBBsafe 16 0.33 47 1.05 165 4.23 2398 73.68 GPBBNM 16 0.34 48 1.06 162 3.42 2974 62.19 GPABB 16 0.45 47 1.23 179 4.68 2276 49.45 GPSSABB 13 0.41 48 1.36 146 4.31 1372 38.50 MGPSSABB 13 0.37 47 1.33 129 3.67 678 18.90
下载: 导出CSV
表 3 Barbara (512 × 512)迭代步数和CPU时间(秒)
Table 3 Number of iterations (Iter) and CPU time (s) of Barbara (512 × 512)
Algorithms Tol=10−2 Tol=10−3 Tol=10−4 Tol=10−6 Iter Time(s) Iter Time(s) Iter Time(s) Iter Time(s) Chambolle 27 3.04 131 14.27 536 60.47 8583 939.73 GPCL 24 2.78 79 9.31 331 37.10 5854 641.63 GPLS 36 6.61 90 20.90 319 77.84 5532 1316.20 GPBBM 20 3.03 84 13.32 340 52.10 6096 872.62 GPBBM(3) 20 2.89 74 11.31 229 34.94 2588 365.88 SQPBBM 14 2.75 33 7.71 106 23.20 1530 325.25 GPBBsafe 15 2.09 40 5.76 118 18.75 1494 290.38 GPBBNM 15 2.42 41 5.55 116 15.69 1467 194.15 GPABB 14 2.43 35 5.91 125 21.23 1123 180.51 GPSSABB 12 2.03 34 5.97 104 19.25 878 159.95 MGPSSABB 14 2.39 37 6.26 90 15.55 431 86.31
下载: 导出CSV
-
[1] Rudin L I, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 1992, 60(1-4): 259-268 doi: 10.1016/0167-2789(92)90242-F [2] Aubert G, Kornprobst P. Mathematical Problems in Image Processing. Berlin: Springer, 2002. [3] Chan T, Shen J H. Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods. Philadelphia: SIAM, 2005. [4] 王诗言, 于慧敏.基于全变分的运动分割模型及分裂Bregman算法.自动化学报, 2015, 41(2): 396-404 http://www.aas.net.cn/CN/abstract/abstract18618.shtmlWang Shi-Yan, Yu Hui-Min. Motion segmentation model based on total variation and split Bregman algorithm. Acta Automatica Sinica, 2015, 41(2): 396-404 http://www.aas.net.cn/CN/abstract/abstract18618.shtml [5] 张瑞, 冯象初, 王斯琪, 常莉红.基于稀疏梯度场的非局部图像去噪算法.自动化学报, 2015, 41(9): 1542-1552 http://www.aas.net.cn/CN/abstract/abstract18729.shtmlZhang Rui, Feng Xiang-Chu, Wang Si-Qi, Chang Li-Hong. A sparse gradients field based image denoising algorithm via non-local means. Acta Automatica Sinica, 2015, 41(9): 1542-1552 http://www.aas.net.cn/CN/abstract/abstract18729.shtml [6] Chan T F, Golub G H, Mulet P. A nonlinear primal-dual method for total variation-based image restoration. SIAM Journal on Scientific Computing, 1999, 20(6): 1964-1977 doi: 10.1137/S1064827596299767 [7] Chambolle A. An algorithm for total variation minimization and applications. Journal of Mathematical Imaging and Vision, 2004, 20(1): 89-97 http://cn.bing.com/academic/profile?id=2144275666&encoded=0&v=paper_preview&mkt=zh-cn [8] Chambolle A. Total variation minimization and a class of binary MRF models. In: Proceedings of the 5th International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition. St. Augustine, FL, USA: Springer, 2005. 136-152 [9] 任福全, 邱天爽.基于二阶广义全变差正则项的模糊图像恢复算法.自动化学报, 2015, 41(6): 1166-1172 http://www.aas.net.cn/CN/abstract/abstract18691.shtmlRen Fu-Quan, Qiu Tian-Shuang. Blurred image restoration method based on second-order total generalized variation regularization. Acta Automatica Sinica, 2015, 41(6): 1166-1172 http://www.aas.net.cn/CN/abstract/abstract18691.shtml [10] Zhang B X, Zhu Z B, Li S A. A modified spectral conjugate gradient projection algorithm for total variation image restoration. Applied Mathematics Letters, 2014, 27: 26-35 doi: 10.1016/j.aml.2013.08.006 [11] Xiao Y H, Wu S Y, Qi L Q. Nonmonotone Barzilai-Borwein gradient algorithm for l1 regularized nonsmooth minimization in compressive sensing. Journal of Scientific Computing, 2014, 61(1): 17-41 doi: 10.1007/s10915-013-9815-8 [12] Loris I, Bertero M, De Mol C, Zanella R, Zanni L. Accelerating gradient projection methods for l1-constrained signal recovery by steplength selection rules. Applied and Computational Harmonic Analysis, 2009, 27(2): 247-254 doi: 10.1016/j.acha.2009.02.003 [13] Huang Y K, Liu H W, Zhou S. An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization. Applied Mathematics Letters, 2015, 45: 12-17 doi: 10.1016/j.aml.2015.01.003 [14] Xiao Y H, Jin Z F. An alternating direction method for linear-constrained matrix nuclear norm minimization. Numerical Linear Algebra with Applications, 2012, 19(3): 541-554 doi: 10.1002/nla.v19.3 [15] Yu G H, Qi L Q, Dai Y H. On nonmonotone Chambolle gradient projection algorithms for total variation image restoration. Journal of Mathematical Imaging and Vision, 2009, 35(2): 143-154 doi: 10.1007/s10851-009-0160-3 [16] Dai Y H, Fletcher R. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numerische Mathematik, 2005, 100(1): 21-47 doi: 10.1007/s00211-004-0569-y [17] Bertsekas D P. Nonlinear Programming. Nashua: Athena Scientific, 1999. [18] Frassoldati G, Zanghirati G, Zanni L. New adaptive stepsize selections in gradient methods. Journal of Industrial and Management Optimization, 2008, 4(2): 299-312 doi: 10.3934/jimo [19] Barzilai J, Borwein J M. Two-point step size gradient methods. IMA Journal of Numerical Analysis, 1988, 8(1): 141-148 doi: 10.1093/imanum/8.1.141 [20] Birgin E G, Martínez J M, Raydan M. Nonmonotone spectral projected gradient methods on convex sets. SIAM Journal on Optimization, 2000, 10(4): 1196-1211 doi: 10.1137/S1052623497330963 [21] Grippo L, Lampariello F, Licidi S. A nonmonotone line search technique for Newton's method. SIAM Journal on Numerical Analysis, 1986, 23(4): 707-716 doi: 10.1137/0723046 [22] Zhu M Q, Wright S J, Chan T F. Duality-based algorithms for total-variation image restoration. Computational Optimization and Applications, 2010, 47(3): 377-400 doi: 10.1007/s10589-008-9225-2 [23] Ekeland I, Témam R. Convex Analysis and Variational Problems. Philadelphia: SIAM, 1999. -
图(4) / 表(3)
计量
- 文章访问数: 2258
- HTML全文浏览量: 502
- PDF下载量: 1713
- 被引次数: 0
