Asymptotic Non-local Means Image Denoising Algorithm
-
摘要: 非局部平均去噪算法(Non-local means denoising algorithm, NLM)是图像处理领域具有里程碑意义的算法, NLM的提出开启了影响深远的非局部方法. 本文从以下两个方面来重新探讨非局部平均算法: 1) 针对NLM算法运算复杂度高的问题, 基于互相关(Cross-correlation, CC)和快速傅里叶变换(Fast Fourier transformation, FFT)构造了一种快速算法; 2) NLM在滤除噪声的同时会模糊图像结构信息, 在强噪声条件下更是如此. 针对这一问题, 提出了一种渐近非局部平均图像去噪算法, 该算法利用方差的性质来控制滤波参数. 数值实验表明, 快速算法较之经典算法, 在标准参数配置下运行速度可提高27倍左右; 渐近非局部平均图像去噪算法较之经典非局部平均图像去噪算法, 去噪效果显著改善.Abstract: Non-local means denoising (NLM) algorithm is a milestone algorithm in the field of image processing. The proposal of NLM has opened up the non-local method which has a deep influence. This paper performed a revisit for NLM from two aspects as follows: 1) To alleviate the high computational complexity problem of NLM, a fast algorithm was constructed, which was based on cross-correlation and fast Fourier transform; 2) NLM always blur structures and textures during the noise removal, especially in the case of strong noise. To solve this problem, an asymptotic non-local means (ANLM) image denoising algorithm is put forward, which uses the property of noise variance to control the filtering parameters. Numerical experiments illustrate that the fast algorithm is 27 times faster than classical implementation with standard parameter configuration, and the ANLM obtain better denoising effect than classical NLM.
-
表 1 三种去噪算法运行速度的比较
Table 1 Comparison of running speeds of three denoising algorithms
图像块
尺寸搜索区域
尺寸NLM运行
时间 (s)NLM-P运行
时间 (s)FNLM运行
时间 (s)NLM与NLM-P
运行时间之比值NLM与FNLM
运行时间之比值NLM-P与FNLM
运行时间之比值3 × 3 21 × 21 232.79 19.41 7.17 11.99 32.46 2.71 3 × 3 31 × 31 505.64 42.01 10.53 12.04 48.02 3.99 3 × 3 51 × 51 873.02 113.04 13.95 7.72 62.58 8.10 3 × 3 101 × 101 5 024.73 160.10 48.49 31.38 103.62 3.30 5 × 5 21 × 21 236.12 18.29 8.68 12.91 27.20 2.11 5 × 5 31 × 31 512.77 39.90 12.74 12.85 40.25 3.13 5 × 5 51 × 51 911.16 108.04 16.19 8.43 56.28 6.67 5 × 5 101 × 101 5 159.80 154.83 53.13 33.33 97.12 2.91 7 × 7 21 × 21 250.77 19.21 11.28 13.05 22.23 1.70 7 × 7 31 × 31 547.50 42.29 16.51 12.95 33.16 2.56 7 × 7 51 × 151 913.15 114.37 19.75 5.58 46.24 5.79 7 × 7 101 × 101 5 328.55 163.56 59.96 32.58 88.87 2.73 9 × 9 21 × 21 256.49 18.54 13.40 13.83 19.14 1.38 9 × 9 31 × 31 560.17 39.63 20.70 14.13 27.06 1.91 9 × 9 51 × 51 969.08 108.74 23.35 8.91 41.50 4.66 9 × 9 101 × 101 5 516.60 154.75 67.41 35.65 81.84 2.30 表 2 三种去噪算法对灰度图像的效果比较
Table 2 Effect comparison of three denoising algorithms on gray images
图像 算法 25 30 50 75 100 PSNR/SSIM PSNR/SSIM PSNR/SSIM PSNR/SSIM PSNR/SSIM Camera 256 × 256 NLM 28.23/0.77 27.27/0.73 24.26/0.57 21.82/0.41 20.17/0.30 PNLM 28.39/0.82 27.58/0.79 24.96/0.71 22.59/0.61 21.02/0.52 ANLM 28.07/0.83 27.43/0.81 25.35/0.73 23.32/0.64 21.80/0.56 Lena 512 × 512 NLM 30.11/0.89 29.13/0.87 26.21/0.78 23.75/0.67 22.00/0.58 PNLM 30.58/0.89 29.72/0.88 27.18/0.81 25.07/0.73 23.65/0.67 ANLM 30.59/0.90 29.80/0.89 27.57/0.83 25.72/0.77 24.35/0.71 Boat 512 × 512 NLM 28.17/0.85 27.21/0.82 24.53/0.72 22.48/0.61 21.04/0.53 PNLM 28.40/0.85 27.51/0.82 24.99/0.72 23.17/0.63 22.07/0.56 ANLM 28.55/0.86 27.74/0.84 25.50/0.75 23.73/0.67 22.58/0.61 Finger 512 × 512 NLM 26.57/0.93 25.43/0.91 21.84/0.79 19.18/0.63 17.73/0.51 PNLM 26.41/0.93 25.45/0.91 22.15/0.78 19.22/0.57 17.64/0.40 ANLM 26.41/0.94 25.63/0.93 23.00/0.83 20.40/0.68 18.58/0.52 B Fly 512 × 512 NLM 28.09/0.85 27.12/0.82 23.88/0.69 20.61/0.54 18.39/0.41 NLM 27.78/0.88 26.98/0.86 24.32/0.79 21.44/0.68 18.99/0.56 ANLM 27.61/0.89 26.84/0.87 24.65/0.80 22.44/0.72 20.45/0.63 Man 512 × 512 NLM 28.28/0.85 27.39/0.82 24.87/0.71 22.83/0.61 21.35/0.53 PNLM 28.45/0.84 27.62/0.81 25.32/0.71 23.61/0.62 22.51/0.56 ANLM 28.63/0.86 27.89/0.83 25.83/0.75 24.20/0.67 23.08/0.61 Baboon 512 × 512 NLM 24.53/0.81 23.66/0.77 21.60/0.63 20.27/0.52 19.36/0.44 PNLM 24.61/0.81 23.75/0.76 21.51/0.59 20.23/0.47 19.61/0.40 ANLM 24.62/0.83 23.88/0.79 21.83/0.64 20.57/0.53 19.90/0.45 Straw 256 × 256 NLM 24.67/0.80 23.50/0.74 20.71/0.55 19.16/0.39 18.27/0.31 PNLM 24.94/0.81 23.78/0.75 20.66/0.51 18.96/0.32 18.25/0.24 ANLM 24.96/0.83 24.04/0.78 21.23/0.58 19.37/0.40 18.51/0.32 Barbara 512 × 512 NLM 28.26/0.89 27.11/0.87 24.05/0.76 21.92/0.65 20.54/0.57 PNLM 28.76/0.90 27.64/0.88 24.51/.078 22.45/0.68 21.30/0.60 ANLM 28.72/0.91 27.82/0.89 25.08/0.81 23.02/0.71 21.82/0.65 Montage 256 × 256 NLM 30.31/0.83 29.17/0.78 25.54/0.62 22.21/0.44 20.24/0.33 PNLM 30.56/0.88 29.50/0.86 26.41/0.79 23.51/0.69 21.31/0.59 ANLM 30.60/0.89 29.65/0.87 27.04/0.80 24.50/0.71 22.28/0.62 House 256 × 256 NLM 30.60/0.78 29.43/0.74 25.92/0.57 23.20/0.41 21.43/0.30 PNLM 31.30/0.83 30.26/0.81 26.97/0.73 24.31/0.62 22.74/0.54 ANLM 31.28/0.84 30.47/0.82 27.85/0.75 25.35/0.66 23.58/0.58 Hill 512 × 512 NLM 28.21/0.83 27.33/0.79 24.94/0.68 23.08/0.58 21.68/0.51 PNLM 28.37/0.82 27.51/0.78 25.31/0.66 23.87/0.57 23.01/0.52 ANLM 28.69/0.84 27.94/0.81 25.86/0.71 24.38/0.62 23.44/0.57 Couple 512 × 512 NLM 27.50/0.84 26.52/0.80 24.03/0.69 22.16/0.58 20.84/0.50 PNLM 27.76/0.84 26.74/0.80 24.27/0.67 22.68/0.57 21.71/0.51 ANLM 28.12/0.86 27.21/0.83 24.79/0.72 23.22/0.62 22.20/0.56 Peppers 256 × 256 NLM 28.61/0.79 27.58/0.75 24.45/0.60 21.76/0.45 20.00/0.34 PNLM 29.04/0.83 28.08/0.80 25.12/0.72 22.40/0.62 20.64/0.53 ANLM 28.75/0.84 27.93/0.81 25.51/0.74 23.34/0.65 21.64/0.57 -
[1] 许录平. 数字图像处理学, 北京: 科学出版社, 2007. 86−88Xu Lu-Ping. Digital Image Processing. Beijing: Publishing House of Science, 2007. 86−88 [2] Huang H C, Lee T C M. Data adaptive median filters for signal and image denoising using a generalized SURE criterion. IEEE Signal Processing Letters, 2006, 13(9): 561−564 doi: 10.1109/LSP.2006.874463 [3] Yuan S Q, Tan Y H. Impulse noise removal by a global-local noise detector and adaptive median filter. Signal Processing, 2006, 86(8): 2123−2128 doi: 10.1016/j.sigpro.2006.01.009 [4] Huang X D, Woolsey G A. Image denoising using wiener filtering and wavelet thresholding. In: Proceedings of the 2000 IEEE Multimedia and Expo, New York, USA: IEEE, 2000. 1759−1762 [5] Sendur L, Selesnick I W. Bivariate shrinkage functions for wavelet-based denoising exploiting interscale dependency. IEEE Transactions on Signal Processing, 2002, 20(11): 2744−2756 [6] Portilla J, Strela V, Wainwright M J, Simoncelli E P. Image denoising using scale mixtures of Gaussians in the wavelet domain. IEEE Transactions on Image Processing, 2003, 12(11): 1338−1351 doi: 10.1109/TIP.2003.818640 [7] Alleyne, D. A two-dimensional Fourier transform method for the measurement of propagating multimode signals. The Journal of the Acoustical Society of America, 1991, 89(3): 1159−1168 doi: 10.1121/1.400530 [8] Elad M, Aharon M. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing, 2006, 15(12): 3736−3745 doi: 10.1109/TIP.2006.881969 [9] Sun D, Gao Q W, Lu Y X, Huang Z X, Li T. A novel image denoising algorithm using linear Bayesian MAP estimation based on sparse representation. Signal Processing, 2014, 100: 132−145 doi: 10.1016/j.sigpro.2014.01.022 [10] 纪建, 徐双星, 李晓. 基于形态成分分析和Contourlet变换的自适应阈值图像去噪方法. 模式识别与人工智能, 2014, 27(6): 561−568 doi: 10.3969/j.issn.1003-6059.2014.06.012Ji Jian, Xu Shuang-Xing, Li Xiao. An adaptive thresholding image denoising method based on morphological component analysis and contourlet transform. Pattern Recognition and Artificial Intelligence, 2014, 27(6): 561−568 doi: 10.3969/j.issn.1003-6059.2014.06.012 [11] 凤宏晓, 侯彪, 焦李成, 卜晓明. 基于非下采样Contourlet域局部高斯模型MAP的SAR图像相干斑抑制. 电子学报, 2010, 38(4): 811−816Feng Hong-Xiao, Hou Biao, Jiao Li-Cheng, Bu Xiao-Ming. SAR image despeckling based on local Gaussian model and MAP in NSCT domain. Acta Electronica Sinica, 2010, 38(4): 811−816 [12] Yin M, Liu W, Zhao X, Guo Q W, Bai R F. Image denoising using trivariate prior model in nonsubsampled dual-tree complex contourlet transform domain and non-local means filter in spatial domain. Optik-International Journal for Light and Electron Optics, 2013, 124(24): 6896−6904 doi: 10.1016/j.ijleo.2013.05.132 [13] Tomasi C, Manduchi R. Bilateral filtering for gray and color images. In: Proceedings of the 6th IEEE International Conference on Computer Vision, Bombay, India: IEEE, 1998. 839−846 [14] Buades A, Coll B, Morel J M. A non-local algorithm for image denoising. In: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, USA: IEEE, 2005. II: 60−65 [15] Dabov K, Foi A, Katkovnik V, Egiazarian K. Image denoising by sparse 3-D transform-domain collaborative filtering. IEEE Transactions on Image Processing, 2007, 16(8): 2080−2095 doi: 10.1109/TIP.2007.901238 [16] Verma R, Pandey R. Grey relational analysis based adaptive smoothing parameter for non-local means image denoising. Multimedia Tools and Applications, 2018, 77(19): 25919−25940 doi: 10.1007/s11042-018-5828-5 [17] Tasdizen T. Principal neighborhood dictionaries for nonlocal means image denoising. IEEE Transactions on Image Processing, 2009, 18(12): 2649−2660 doi: 10.1109/TIP.2009.2028259 [18] Grewenig S, Zimmer S, Weickert J. Rotationally invariant similarity measures for nonlocal image denoising. Journal of Visual Communication and Image Representation, 2011, 22(2): 117−130 doi: 10.1016/j.jvcir.2010.11.001 [19] Wu Y, Tracey B, Natarajan P, Noonan J P. Probabilistic non-local means. IEEE Signal Processing Letters, 2013, 20(8): 763−766 doi: 10.1109/LSP.2013.2263135 [20] 蔡斌, 刘卫, 郑重, 汪增福. 一种改进的非局部均值去噪算法. 模式识别与人工智能, 2016, 29(1): 1−10Cai Bin, Liu Wei, Zheng Zhong. Wang Zeng-Fu. An improved non-local means denoising algorithm. Pattern Recognition and Artificial Intelligence, 2016, 29(1): 1−10 [21] Bo L, Lv J R, Luo X G, Wang H J, Wang S. A novel and fast nonlocal means denoising algorithm using a structure tensor. The Journal of Supercomputing, 2019, 75(2): 770−782 doi: 10.1007/s11227-018-2611-3 [22] Nguyen M P, Chun S Y. Bounded self-weights estimation method for non-local means image denoising using minimax estimators. IEEE Transactions on Image Processing, 2017, 26(4): 1637−1649 doi: 10.1109/TIP.2017.2658941 [23] Jacques F. Parameter-free fast pixelwise non-local means denoising. Image Processing on Line, 2014, 4: 300−326 doi: 10.5201/ipol.2014.120 [24] 黄智, 付兴武, 刘万军. 混合相似性权重的非局部均值去噪算法. 计算机应用, 2016, 36(2): 556−562 doi: 10.11772/j.issn.1001-9081.2016.02.0556Huang Zhi, Fu Xing-Wu, Liu Wan-Jun. Non-local means denoising algorithm with hybrid similarity weight. Journal of Computer Applications, 2016, 36(2): 556−562 doi: 10.11772/j.issn.1001-9081.2016.02.0556 [25] 张选德, 冯象初, 王卫卫, 魏立力. 求同存异的非局部图像去噪. 中国科学: 信息科学, 2013, 43(7): 907−919Zhang Xuan-De, Feng Xiang-Chu, Wang Wei-Wei, Wei Li-Li. Exploit the similarity while preserving the difference for nonlocal image denoising. Scientia Sinica (Informationis), 2013, 43(7): 907−919