陈玲玲，周旭东，谢傢成，刘 乾

快速仿射非局部均值图像去噪

陈玲玲，周旭东，谢傢成，刘 乾

(扬州大学信息工程学院，江苏 扬州 225127)

针对仿射非局部均值(ANLM)算法对图像去噪过程中出现用时过长的问题，提出了一种快速仿射非局部均值去噪(F-ANLM)算法。通过对算法的研究和用时分析得知，仿射变换和关于仿射不变相似性度量的计算这2个模块占时最多，因此从这2个部分入手提出优化策略。算法首先使用仿射协变结构张量其特征向量的夹角代替尺寸不变特征变换(SIFT)算子的主方向，简化了仿射变换过程；然后将ANLM方法中的仿射不变相似性度量改写为离散卷积的形式，使用快速傅里叶变换减少卷积的运算量，加速仿射协变特征区域之间相似性度量的计算。实验证明，F-ANLM方法简化了仿射变换和仿射不变相似性度量的计算，与原来ANLM算法相比，速度得到很大的提升。

非局部；结构张量；仿射不变；卷积；相似性度量；快速傅里叶

为了抑制图像中的噪声，BUADES等[1]提出了非局部均值(non-local means，NLM)算法，利用图像的非局部自相似性，收集最相似的图像块进行加权平均得到当前像素值，去噪效果得到了很大地提升。但随着图像中噪声水平等级的提高，NLM算法在去噪效果以及保留图像轮廓纹理等高频细节信息上，出现了过度平滑的现象。为了提高其去噪性能，ZHAN等[2]用一种非局部SUSAN边缘检测算子来自适应地调整图像像素的平滑系数。此外，图像块的大小也影响去噪效果，文献[3-4]提出利用局部噪声方差和图像局部结构来对图像块尺寸进行分类。DELEDALLE等[5]提出形状自适应块的非局部方法(non-local methods with shape-adaptive patches，NLM-SAP)，即使用不同形状块来增加相似块的个数，缓解“块效应”。TIAN等[6]提出基于核函数选择的NLM去噪方法，用新的核函数代替指数函数。文献[7]通过改进的混合鲁棒权重函数来计算图像块的相似性权重。FEDOROV和BALLESTER[8]利用仿射非局部均值去噪(affine non-local means denoising，ANLM)算法将仿射变换应用于NLM方法，去噪效果得到显著提升。

由于NLM在相似度计算中存在大量重复运算，文献[9]使用平方和图像和快速傅里叶加快相似度计算，文献[10]在此基础上结合Laplacian金字塔再次提高算法效率。本文从减少算法运行时间出发对ANLM算法进行改进：首先利用结构张量简化仿射变换中旋转角度的计算，再将仿射不变相似性度量改写成离散卷积形式，用快速傅里叶变换加速相似度的计算。实验结果表明，本文提出的快速仿射非局部均值去噪(fast affine non-local means denoising，F-ANLM)算法能够大大减少ANLM算法的运行时间。

1 仿射非局部均值

ANLM算法考虑利用结构张量生成稳定且独立的仿射协变区域，以形成椭圆图像块，在图像块之间加入仿射变换增加相似块的个数，提高图像去噪质量。并提出，若直接用图像的梯度对结构张量进行估计，可能会造成结果的不稳定；若张量具有仿射协变性，那么对于任意一个仿射变换，则有

其中，()为关于图像结构张量的自相关矩阵；为仿射变换矩阵。对于张量()，可以将其与一个以为中心，半径为的椭圆区域联系，即

当张量具有仿射协变性(,)=-1(,)，这意味张量可用来构造经过适当仿射变换的仿射协变区域，这些区域是大小自适应的椭圆块。根据文献[11]对仿射协变结构张量的迭代过程的陈述，可将结构张量重新定义为

将高斯噪声看作是随机方向上的附加梯度，数量为，即噪声图像的结构张量为

椭圆图像块可以通过对噪声图像的结构张量进行奇异值分解得到，其大小与有关。结合式(2)和(3)可知：仿射变换后，图像上的点可以表示为：ʹ()=()，其中，为仿射变换矩阵。

要完全确定，需要找到旋转角度。ANLM首先将仿射协变椭圆块归一化为圆，然后对圆进行仿射变换即旋转。在变换过程中，选择使用尺度不变特征变换(scale-invariant feature transform，SIFT)特征点描述子计算旋转的角度，将梯度方向直方图中的主能量作为图像块的主方向。旋转圆形区域需与主梯度方向对齐，实现圆形区域的旋转不变性。

仿射变换增加了相似块的个数，将中心块和仿射协变区域中像素点逐一进行相似度比较，最后加权平均得到当前像素点的估计值。

2 快速仿射非局部均值

通过对ANLM方法用时分析可知：计算量主要集中在SIFT旋转配准和计算放射不变相似性度量上。ANLM算法流程如图1所示。

图1 ANLM算法流程图

以像素点和为中心的2个相似块图像之间的距离可表示为

其中，为圆形图像块区域，使用指数函数将距离转换为相似性，则2个图像块之间的权重函数为

为了对像素点处的图像块进行去噪处理，使用其相似性值()作为权重，平均像素点处圆形块内部的所有像素点，并旋转图像块进行匹配，用加权平均值给出去噪后的图像块，即

假设图像的大小为×，以像素点为中心的搜索窗口边长为，其大小则为×，圆形图像块的半径为，则其外接矩阵的大小为2×2()，还需对圆形图像块应用仿射变换，即计算一个图像块与其相似块之间加权欧氏距离需要22，则整幅图像时间复杂度为(222)。研究发现，在图1虚线框部分(计算图像块旋转方向和相似性的过程中)存在大量的复杂计算，为了提高ANLM算法效率，构造了F-ANLM算法。主要分2步：①简化仿射变换；②加速仿射不变相似度的计算。

2.1 计算旋转角度

ANLM将仿射变换关系化成圆形邻域的旋转，选择使用SIFT特征点描述子，将梯度方向直方图的主能量作为图像块的主方向，旋转圆形块需与主梯度方向对齐。但研究发现，这种关于梯度方向的估计方法会使角度存在±20°的误差，而且算法复杂度高，计算量较大。为了提高运算速度，本文采用仿射协变区域计算给定位置的结构张量求取主方向[12]。

结构张量是一个关于图像的二阶矩阵，ANLM中利用张量形成仿射协变区域，为保证局部邻域的旋转不变性，本文提出利用圆形邻域求取像素点的结构张量，即

文献[12]指出，特征向量可以表示特征值所在的方向，该方向与图像局部邻域方向一致。因此对上式的结构张量进行特征分解：得到2个特征值及所对应的特征向量，像素点邻域内的主方向可以表示为

其中，,1为结构张量的最大特征值所对应的特征向量。因此，圆形块的旋转角度求解可以直接简化成求取结构张量的特征向量夹角。

2.2 FFT仿射不变相似性度量

积分图像作为加速计算相似度经典算法，只适用于方形邻域。仿射非局部均值最终是求2个圆形图像块之间的相似度，积分图像并不适用，即考虑将欧氏距离重写成离散卷积的形式

卷积可以借助快速傅里叶变换(fast Fourier transform，FFT)进行加速处理，且计算与图像块的形状大小无关。与积分图像的思想一致，傅里叶变换是将复杂函数表示成三角函数或是其积分的线性组合。快速傅里叶变换是对离散傅里叶(discrete Fourier transform，DFT)的加速算法，其是基于逐步加倍的思想，在频域中让积分求和变为乘法，减少卷积运算的时间。DFT可表示为

快速傅里叶可看成是DFT和IDFT (inverse discrete Fourier transform) 2部分组成，采用分治思想使多项式能够快速地进行点值和系数之间的转换。在图像中，计算多项式的乘法，可用矩阵相乘的形式替代。卷积使用由表示的2D离散傅里叶变换及其逆-1来计算，先对块按行做一维离散傅里叶变换，再对结果按列重复操作；逆-1即先按列再按行做傅里叶变换。卷积满足

其中，为高斯加权函数；()为搜索窗口内的图像；令=+，即为搜索窗口内的位移。()和()像素值的平方差可以通过位移表示，因此权重函数可以表示为

2.3 F-ANLM去噪算法

F-AMLN算法在仿射变换和仿射不变相似性度量上进行优化，加快了运行速度，算法步骤如下：

步骤1.输入干净图像，添加白高斯噪声，得到噪声图像；

在解决科学问题或社会挑战的同时，会聚研究往往融合各学科特点形成新的创新方式，或开发新的科技产品，从而更好地推动创新模式和创新经济的发展。

步骤2.将图像分成31×31的矩形块，利用sobel算子求梯度图像，再求取每个像素点的结构张量()；

步骤3.对()进行奇异值分解，得到特征值和对应的特征向量，由特征值计算得到椭圆协变区域的长短轴，形成以为中心的椭圆图像块；

步骤4.利用像素点的自相关矩阵()1/2对椭圆图像块进行归一化，使椭其变为固定半径圆形图像块W，利用双线性插值法进行像素插值；

步骤5.计算圆形图像块S的结构张量，奇异值分解后得到最大特征值所对应的特征向量,1，通过反正切函数得到旋转角度θ；

步骤6.将圆形块S旋转θ度，使得仿射协变区域具有旋转不变性；

步骤7.将中心块和相似图像块之间的距离写成离散卷积形式，计算高斯核函数；

步骤8.分别计算以像素点为中心的圆形图像块和以为中心的相似块的平方和；

步骤9.使用DFT和IDFT对圆形块在傅里叶变换域中执行一个逐项相乘和2个2D-FFT操作，快速实现卷积运算；

步骤10. 计算权重函数得当前像素点估计值。

3 实验及结果分析

为验证本文算法的可行性和有效性，从运行时间和去噪效果2个角度设计实验。其中时间是使用Python自带的计时器进行计时，去噪效果评价标准采用的是峰值信噪比PSNR，实验环境为Python 3.7。测试图片采用4张灰度图像(lena，house，peppers，monkey)，通过对原图添加白高斯噪声，检测算法在不同的噪声等级和图像下的去噪能力及用时。由仿射非局部均值算法经验可知，当参数=31，max=5，=11时算法去噪效果较好，因此实验采用此参数作为标准进行实验，有

3.1 快速仿射非局部均值

首先，通过第一组实验来是验证F-ANLM的去噪性能。将原始NLM、ANLM和本文F-ANLM进行对比实验，图2为噪声指数是30时的3种算法去噪效果图；表1验证了3种算法在不同图像和噪声等级下的PSNR (peak signal noise ratio)值。

图2 3种算法的去噪效果图

表1 3种算法在不同噪声等级下PSNR值

从实验结果可以看出，在图像去噪质量上，本文算法未损耗ANLM算法的去噪性能。

3.2 比较R和D的用时情况

以lena图(512×512)和house图(256×256)为例，将本文算法中仿射变换和仿射不变相似性度量在不同噪声等级下的用时与ANLM进行比较，其变化趋势如图3，4所示。

图3 Lena算法用时变化趋势图

图4 House算法用时变化趋势图

图3和图4的柱状图表示lena和house图在ANLM和F-ANLM算法中仿射变换的运行时间，折线图为仿射不变相似性度量的运行时间。综合比较运用结构张量计算旋转角度的时间比SIFT快约10～15倍，运用FFT计算相似度的速度大约提升13～20倍。

3.3 比较不同尺寸的图像对速度的影响

从上述实验可以看出，本文算法的速度受噪声等级影响较小，变化趋势不明显。研究发现，运行速度受图像大小影响较大，时间比率随着图像大小的增大而增大，图像大小在500×500以下时，速度提升不明显，但大于500×500时，本文算法性能体现出了明显的优势。为验证此结果，选取128×128，256×256，512×512，750×750和1024×1024的图片各5张进行实验，噪声等级=25，取每种尺寸图像运行时间的平均值进行对比，实验结果见表2。从结果可以看出，2种算法的时间比率随着图像尺寸的增大而增大。

表2 2种算法在各尺寸下的运行时间

4 结束语

本文在ANLM算法基础上，从减少运行时间的角度出发，对其2个部分进行了改进。首先简化仿射变换，使用仿射协变结构张量特征向量的夹角来替换SIFT算子进行主方向的计算，然后将仿射不变相似性度量改写成离散卷积的形式，使用FFT对其进行加速运算。实验结果表明，本文提出的F-ANLM算法对基于仿射非局部均值算法加速方法具有可行性，在不损耗ANLM性能的基础上速度提升的很快，效果极佳。

[1] BUADES A, COLL B, MOREL J M. A review of image denoising algorithms, with a new one[J]. Multiscale Modeling & Simulation, 2005, 4(2): 490-530.

[2] ZHAN Y, ZHANG X M, DING M Y. SUSAN controlled decay parameter adaption for non-local means image denoising[J]. Electronics Letters, 2013, 49(13): 807-808.

[3] ZENG W L, LU X B. Region-based non-local means algorithm for noise removal[J]. Electronics Letters, 2011, 47(20): 1125-1127.

[4] 萧澍, 胡靖, 王彦芳. 椭圆窗口和参数自适应的非局部均值算法[J]. 计算机辅助设计与图形学学报, 2020, 32(1): 79-89.

XIAO S, HU J, WANG Y F. Non-local means with elliptical window and adaptive parameter[J]. Journal of Computer-Aided Design & Computer Graphics, 2020, 32(1): 79-89 (in Chinese).

[5] DELEDALLE C A, DUVAL V, SALMON J. Non-local methods with shape-adaptive patches (NLM-SAP)[J]. Journal of Mathematical Imaging and Vision, 2012, 43(2): 103-120.

[6] TIAN J, YU W Y, XIE S L. On the kernel function selection of nonlocal filtering for image denoising[C]//2008 International Conference on Machine Learning and Cybernetics. New York: IEEE Press, 2008: 2964-2969.

[7] 陆海青, 葛洪伟. 混合鲁棒权重和改进方法噪声的两级非局部均值去噪[J]. 计算机工程与科学, 2018, 40(7): 1227-1236.

LU H Q, GE H W. Two-stage non-local means denoising based on hybrid robust weight and improved method noise[J]. Computer Engineering & Science, 2018, 40(7): 1227-1236 (in Chinese).

[8] FEDOROV V, BALLESTER C. Affine non-local means image denoising[J]. IEEE Transactions on Image Processing, 2017, 26(5): 2137-2148.

[9] WANG J, GUO Y W, YING Y T, et al. Fast non-local algorithm for image denoising[C]//2006 International Conference on Image Processing (ICIP). New York: IEEE Press, 2006: 1429-1432.

[10] LIU Y L, WANG J, CHEN X, et al. A robust and fast non-local means algorithm for image denoising[J]. Journal of Computer Science & Technology, 2008(2): 270-279.

[11] ZUO C L, JOVANOV L, LUONG H Q, et al. Rotation invariant similarity measure for non-local self-similarity based image denoising[C]//2015 IEEE International Conference on Image Processing (ICIP). New York: IEEE Press, 2015: 1618-1622.

[12] BAGHAIE A, YU Z Y. Structure tensor based image interpolation method[J]. International Journal of Electronics and Communications, 2015, 69(2): 515-522.

Fast affine non-local means image denosing

CHEN Ling-ling, ZHOU Xu-dong, XIE Jia-cheng, LIU Qian

(School of Information Engineering, Yangzhou University, Yangzhou Jiangsu 225127, China)

To address the problem of high time consumption of the affine non-local mean (ANLM) algorithm in the denoising process, a fast affine non-local mean denoising (F-ANLM) algorithm was proposed. Through time analysis of the affine non-local mean algorithm, it was known that the two modules, the affine transformation and the calculation of the affine invariant similarity measure, were the most time-consuming. Therefore, the optimization strategy was proposed from these tworegards. The algorithm first employed the included angle of the feature vector of the affine covariant structure tensor instead of the main direction of the SIFT operator, and then rewrote the affine invariant similarity measure in the ANLM method into the form of discrete convolution. In addition, the Fast Fourier Transform was adopted to reduce the amount of convolution operation and accelerate the calculation of similarity measures between affine covariant feature regions. Experiments show that the F-ANLM algorithm can simplify the calculation of affine transformation and affine invariant similarity measures, and greatly increase the speed compared with the original ANLM algorithm.

non-local; structure-tensor; affine-invariant; convolution; similarity-measure; Fast-Fourier

TP 391

10.11996/JG.j.2095-302X.2021050762

A

2095-302X(2021)05-0762-05

2021-01-04；

2021-02-23

4 January，2021；

23 February，2021

国家自然科学基金项目(61801417)

National Natural Science Foundation of China (61801417)

陈玲玲(1994–)，女，江苏盐城人，硕士研究生。主要研究方向为模式识别与图像处理。E-mail：729325664@qq.com

CHEN Ling-ling (1994-), female, master student. Her main research interests cover pattern recognition and image processing. E-mail：729325664@qq.com

周旭东(1979–)，男，山西长治人，副教授，博士。主要研究方向为机器学习、模式识别与图像处理。E-mail：xdzhou@yzu.edu.cn

ZHOU Xu-dong (1979-), male, associate professor, Ph.D. His main research interests cover machine learning, pattern recognition and image processing. E-mail：xdzhou@yzu.edu.cn