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

陳玲玲，周旭東，謝傢成，劉 乾

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

陳玲玲，周旭東，謝傢成，劉 乾

(揚(yáng)州大學(xué)信息工程學(xué)院，江蘇 揚(yáng)州 225127)

針對(duì)仿射非局部均值(ANLM)算法對(duì)圖像去噪過程中出現(xiàn)用時(shí)過長(zhǎng)的問題，提出了一種快速仿射非局部均值去噪(F-ANLM)算法。通過對(duì)算法的研究和用時(shí)分析得知，仿射變換和關(guān)于仿射不變相似性度量的計(jì)算這2個(gè)模塊占時(shí)最多，因此從這2個(gè)部分入手提出優(yōu)化策略。算法首先使用仿射協(xié)變結(jié)構(gòu)張量其特征向量的夾角代替尺寸不變特征變換(SIFT)算子的主方向，簡(jiǎn)化了仿射變換過程；然后將ANLM方法中的仿射不變相似性度量改寫為離散卷積的形式，使用快速傅里葉變換減少卷積的運(yùn)算量，加速仿射協(xié)變特征區(qū)域之間相似性度量的計(jì)算。實(shí)驗(yàn)證明，F(xiàn)-ANLM方法簡(jiǎn)化了仿射變換和仿射不變相似性度量的計(jì)算，與原來ANLM算法相比，速度得到很大的提升。

非局部；結(jié)構(gòu)張量；仿射不變；卷積；相似性度量；快速傅里葉

為了抑制圖像中的噪聲，BUADES等[1]提出了非局部均值(non-local means，NLM)算法，利用圖像的非局部自相似性，收集最相似的圖像塊進(jìn)行加權(quán)平均得到當(dāng)前像素值，去噪效果得到了很大地提升。但隨著圖像中噪聲水平等級(jí)的提高，NLM算法在去噪效果以及保留圖像輪廓紋理等高頻細(xì)節(jié)信息上，出現(xiàn)了過度平滑的現(xiàn)象。為了提高其去噪性能，ZHAN等[2]用一種非局部SUSAN邊緣檢測(cè)算子來自適應(yīng)地調(diào)整圖像像素的平滑系數(shù)。此外，圖像塊的大小也影響去噪效果，文獻(xiàn)[3-4]提出利用局部噪聲方差和圖像局部結(jié)構(gòu)來對(duì)圖像塊尺寸進(jìn)行分類。DELEDALLE等[5]提出形狀自適應(yīng)塊的非局部方法(non-local methods with shape-adaptive patches，NLM-SAP)，即使用不同形狀塊來增加相似塊的個(gè)數(shù)，緩解“塊效應(yīng)”。TIAN等[6]提出基于核函數(shù)選擇的NLM去噪方法，用新的核函數(shù)代替指數(shù)函數(shù)。文獻(xiàn)[7]通過改進(jìn)的混合魯棒權(quán)重函數(shù)來計(jì)算圖像塊的相似性權(quán)重。FEDOROV和BALLESTER[8]利用仿射非局部均值去噪(affine non-local means denoising，ANLM)算法將仿射變換應(yīng)用于NLM方法，去噪效果得到顯著提升。

由于NLM在相似度計(jì)算中存在大量重復(fù)運(yùn)算，文獻(xiàn)[9]使用平方和圖像和快速傅里葉加快相似度計(jì)算，文獻(xiàn)[10]在此基礎(chǔ)上結(jié)合Laplacian金字塔再次提高算法效率。本文從減少算法運(yùn)行時(shí)間出發(fā)對(duì)ANLM算法進(jìn)行改進(jìn)：首先利用結(jié)構(gòu)張量簡(jiǎn)化仿射變換中旋轉(zhuǎn)角度的計(jì)算，再將仿射不變相似性度量改寫成離散卷積形式，用快速傅里葉變換加速相似度的計(jì)算。實(shí)驗(yàn)結(jié)果表明，本文提出的快速仿射非局部均值去噪(fast affine non-local means denoising，F(xiàn)-ANLM)算法能夠大大減少ANLM算法的運(yùn)行時(shí)間。

1 仿射非局部均值

ANLM算法考慮利用結(jié)構(gòu)張量生成穩(wěn)定且獨(dú)立的仿射協(xié)變區(qū)域，以形成橢圓圖像塊，在圖像塊之間加入仿射變換增加相似塊的個(gè)數(shù)，提高圖像去噪質(zhì)量。并提出，若直接用圖像的梯度對(duì)結(jié)構(gòu)張量進(jìn)行估計(jì)，可能會(huì)造成結(jié)果的不穩(wěn)定；若張量具有仿射協(xié)變性，那么對(duì)于任意一個(gè)仿射變換，則有

其中，()為關(guān)于圖像結(jié)構(gòu)張量的自相關(guān)矩陣；為仿射變換矩陣。對(duì)于張量()，可以將其與一個(gè)以為中心，半徑為的橢圓區(qū)域聯(lián)系，即

當(dāng)張量具有仿射協(xié)變性(,)=-1(,)，這意味張量可用來構(gòu)造經(jīng)過適當(dāng)仿射變換的仿射協(xié)變區(qū)域，這些區(qū)域是大小自適應(yīng)的橢圓塊。根據(jù)文獻(xiàn)[11]對(duì)仿射協(xié)變結(jié)構(gòu)張量的迭代過程的陳述，可將結(jié)構(gòu)張量重新定義為

將高斯噪聲看作是隨機(jī)方向上的附加梯度，數(shù)量為，即噪聲圖像的結(jié)構(gòu)張量為

橢圓圖像塊可以通過對(duì)噪聲圖像的結(jié)構(gòu)張量進(jìn)行奇異值分解得到，其大小與有關(guān)。結(jié)合式(2)和(3)可知：仿射變換后，圖像上的點(diǎn)可以表示為：?()=()，其中，為仿射變換矩陣。

要完全確定，需要找到旋轉(zhuǎn)角度。ANLM首先將仿射協(xié)變橢圓塊歸一化為圓，然后對(duì)圓進(jìn)行仿射變換即旋轉(zhuǎn)。在變換過程中，選擇使用尺度不變特征變換(scale-invariant feature transform，SIFT)特征點(diǎn)描述子計(jì)算旋轉(zhuǎn)的角度，將梯度方向直方圖中的主能量作為圖像塊的主方向。旋轉(zhuǎn)圓形區(qū)域需與主梯度方向?qū)R，實(shí)現(xiàn)圓形區(qū)域的旋轉(zhuǎn)不變性。

仿射變換增加了相似塊的個(gè)數(shù)，將中心塊和仿射協(xié)變區(qū)域中像素點(diǎn)逐一進(jìn)行相似度比較，最后加權(quán)平均得到當(dāng)前像素點(diǎn)的估計(jì)值。

2 快速仿射非局部均值

通過對(duì)ANLM方法用時(shí)分析可知：計(jì)算量主要集中在SIFT旋轉(zhuǎn)配準(zhǔn)和計(jì)算放射不變相似性度量上。ANLM算法流程如圖1所示。

圖1 ANLM算法流程圖

以像素點(diǎn)和為中心的2個(gè)相似塊圖像之間的距離可表示為

其中，為圓形圖像塊區(qū)域，使用指數(shù)函數(shù)將距離轉(zhuǎn)換為相似性，則2個(gè)圖像塊之間的權(quán)重函數(shù)為

為了對(duì)像素點(diǎn)處的圖像塊進(jìn)行去噪處理，使用其相似性值()作為權(quán)重，平均像素點(diǎn)處圓形塊內(nèi)部的所有像素點(diǎn)，并旋轉(zhuǎn)圖像塊進(jìn)行匹配，用加權(quán)平均值給出去噪后的圖像塊，即

假設(shè)圖像的大小為×，以像素點(diǎn)為中心的搜索窗口邊長(zhǎng)為，其大小則為×，圓形圖像塊的半徑為，則其外接矩陣的大小為2×2()，還需對(duì)圓形圖像塊應(yīng)用仿射變換，即計(jì)算一個(gè)圖像塊與其相似塊之間加權(quán)歐氏距離需要22，則整幅圖像時(shí)間復(fù)雜度為(222)。研究發(fā)現(xiàn)，在圖1虛線框部分(計(jì)算圖像塊旋轉(zhuǎn)方向和相似性的過程中)存在大量的復(fù)雜計(jì)算，為了提高ANLM算法效率，構(gòu)造了F-ANLM算法。主要分2步：①簡(jiǎn)化仿射變換；②加速仿射不變相似度的計(jì)算。

2.1 計(jì)算旋轉(zhuǎn)角度

ANLM將仿射變換關(guān)系化成圓形鄰域的旋轉(zhuǎn)，選擇使用SIFT特征點(diǎn)描述子，將梯度方向直方圖的主能量作為圖像塊的主方向，旋轉(zhuǎn)圓形塊需與主梯度方向?qū)R。但研究發(fā)現(xiàn)，這種關(guān)于梯度方向的估計(jì)方法會(huì)使角度存在±20°的誤差，而且算法復(fù)雜度高，計(jì)算量較大。為了提高運(yùn)算速度，本文采用仿射協(xié)變區(qū)域計(jì)算給定位置的結(jié)構(gòu)張量求取主方向[12]。

結(jié)構(gòu)張量是一個(gè)關(guān)于圖像的二階矩陣，ANLM中利用張量形成仿射協(xié)變區(qū)域，為保證局部鄰域的旋轉(zhuǎn)不變性，本文提出利用圓形鄰域求取像素點(diǎn)的結(jié)構(gòu)張量，即

文獻(xiàn)[12]指出，特征向量可以表示特征值所在的方向，該方向與圖像局部鄰域方向一致。因此對(duì)上式的結(jié)構(gòu)張量進(jìn)行特征分解：得到2個(gè)特征值及所對(duì)應(yīng)的特征向量，像素點(diǎn)鄰域內(nèi)的主方向可以表示為

其中，,1為結(jié)構(gòu)張量的最大特征值所對(duì)應(yīng)的特征向量。因此，圓形塊的旋轉(zhuǎn)角度求解可以直接簡(jiǎn)化成求取結(jié)構(gòu)張量的特征向量夾角。

2.2 FFT仿射不變相似性度量

積分圖像作為加速計(jì)算相似度經(jīng)典算法，只適用于方形鄰域。仿射非局部均值最終是求2個(gè)圓形圖像塊之間的相似度，積分圖像并不適用，即考慮將歐氏距離重寫成離散卷積的形式

卷積可以借助快速傅里葉變換(fast Fourier transform，F(xiàn)FT)進(jìn)行加速處理，且計(jì)算與圖像塊的形狀大小無關(guān)。與積分圖像的思想一致，傅里葉變換是將復(fù)雜函數(shù)表示成三角函數(shù)或是其積分的線性組合?？焖俑道锶~變換是對(duì)離散傅里葉(discrete Fourier transform，DFT)的加速算法，其是基于逐步加倍的思想，在頻域中讓積分求和變?yōu)槌朔ǎ瑴p少卷積運(yùn)算的時(shí)間。DFT可表示為

快速傅里葉可看成是DFT和IDFT (inverse discrete Fourier transform) 2部分組成，采用分治思想使多項(xiàng)式能夠快速地進(jìn)行點(diǎn)值和系數(shù)之間的轉(zhuǎn)換。在圖像中，計(jì)算多項(xiàng)式的乘法，可用矩陣相乘的形式替代。卷積使用由表示的2D離散傅里葉變換及其逆-1來計(jì)算，先對(duì)塊按行做一維離散傅里葉變換，再對(duì)結(jié)果按列重復(fù)操作；逆-1即先按列再按行做傅里葉變換。卷積滿足

其中，為高斯加權(quán)函數(shù)；()為搜索窗口內(nèi)的圖像；令=+，即為搜索窗口內(nèi)的位移。()和()像素值的平方差可以通過位移表示，因此權(quán)重函數(shù)可以表示為

2.3 F-ANLM去噪算法

F-AMLN算法在仿射變換和仿射不變相似性度量上進(jìn)行優(yōu)化，加快了運(yùn)行速度，算法步驟如下：

步驟1.輸入干凈圖像，添加白高斯噪聲，得到噪聲圖像；

在解決科學(xué)問題或社會(huì)挑戰(zhàn)的同時(shí)，會(huì)聚研究往往融合各學(xué)科特點(diǎn)形成新的創(chuàng)新方式，或開發(fā)新的科技產(chǎn)品，從而更好地推動(dòng)創(chuàng)新模式和創(chuàng)新經(jīng)濟(jì)的發(fā)展。

步驟2.將圖像分成31×31的矩形塊，利用sobel算子求梯度圖像，再求取每個(gè)像素點(diǎn)的結(jié)構(gòu)張量()；

步驟3.對(duì)()進(jìn)行奇異值分解，得到特征值和對(duì)應(yīng)的特征向量，由特征值計(jì)算得到橢圓協(xié)變區(qū)域的長(zhǎng)短軸，形成以為中心的橢圓圖像塊；

步驟4.利用像素點(diǎn)的自相關(guān)矩陣()1/2對(duì)橢圓圖像塊進(jìn)行歸一化，使橢其變?yōu)楣潭ò霃綀A形圖像塊W，利用雙線性插值法進(jìn)行像素插值；

步驟5.計(jì)算圓形圖像塊S的結(jié)構(gòu)張量，奇異值分解后得到最大特征值所對(duì)應(yīng)的特征向量,1，通過反正切函數(shù)得到旋轉(zhuǎn)角度θ；

步驟6.將圓形塊S旋轉(zhuǎn)θ度，使得仿射協(xié)變區(qū)域具有旋轉(zhuǎn)不變性；

步驟7.將中心塊和相似圖像塊之間的距離寫成離散卷積形式，計(jì)算高斯核函數(shù)；

步驟8.分別計(jì)算以像素點(diǎn)為中心的圓形圖像塊和以為中心的相似塊的平方和；

步驟9.使用DFT和IDFT對(duì)圓形塊在傅里葉變換域中執(zhí)行一個(gè)逐項(xiàng)相乘和2個(gè)2D-FFT操作，快速實(shí)現(xiàn)卷積運(yùn)算；

步驟10. 計(jì)算權(quán)重函數(shù)得當(dāng)前像素點(diǎn)估計(jì)值。

3 實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證本文算法的可行性和有效性，從運(yùn)行時(shí)間和去噪效果2個(gè)角度設(shè)計(jì)實(shí)驗(yàn)。其中時(shí)間是使用Python自帶的計(jì)時(shí)器進(jìn)行計(jì)時(shí)，去噪效果評(píng)價(jià)標(biāo)準(zhǔn)采用的是峰值信噪比PSNR，實(shí)驗(yàn)環(huán)境為Python 3.7。測(cè)試圖片采用4張灰度圖像(lena，house，peppers，monkey)，通過對(duì)原圖添加白高斯噪聲，檢測(cè)算法在不同的噪聲等級(jí)和圖像下的去噪能力及用時(shí)。由仿射非局部均值算法經(jīng)驗(yàn)可知，當(dāng)參數(shù)=31，max=5，=11時(shí)算法去噪效果較好，因此實(shí)驗(yàn)采用此參數(shù)作為標(biāo)準(zhǔn)進(jìn)行實(shí)驗(yàn)，有

3.1 快速仿射非局部均值

首先，通過第一組實(shí)驗(yàn)來是驗(yàn)證F-ANLM的去噪性能。將原始NLM、ANLM和本文F-ANLM進(jìn)行對(duì)比實(shí)驗(yàn)，圖2為噪聲指數(shù)是30時(shí)的3種算法去噪效果圖；表1驗(yàn)證了3種算法在不同圖像和噪聲等級(jí)下的PSNR (peak signal noise ratio)值。

圖2 3種算法的去噪效果圖

表1 3種算法在不同噪聲等級(jí)下PSNR值

從實(shí)驗(yàn)結(jié)果可以看出，在圖像去噪質(zhì)量上，本文算法未損耗ANLM算法的去噪性能。

3.2 比較R和D的用時(shí)情況

以lena圖(512×512)和house圖(256×256)為例，將本文算法中仿射變換和仿射不變相似性度量在不同噪聲等級(jí)下的用時(shí)與ANLM進(jìn)行比較，其變化趨勢(shì)如圖3，4所示。

圖3 Lena算法用時(shí)變化趨勢(shì)圖

圖4 House算法用時(shí)變化趨勢(shì)圖

圖3和圖4的柱狀圖表示lena和house圖在ANLM和F-ANLM算法中仿射變換的運(yùn)行時(shí)間，折線圖為仿射不變相似性度量的運(yùn)行時(shí)間。綜合比較運(yùn)用結(jié)構(gòu)張量計(jì)算旋轉(zhuǎn)角度的時(shí)間比SIFT快約10～15倍，運(yùn)用FFT計(jì)算相似度的速度大約提升13～20倍。

3.3 比較不同尺寸的圖像對(duì)速度的影響

從上述實(shí)驗(yàn)可以看出，本文算法的速度受噪聲等級(jí)影響較小，變化趨勢(shì)不明顯。研究發(fā)現(xiàn)，運(yùn)行速度受圖像大小影響較大，時(shí)間比率隨著圖像大小的增大而增大，圖像大小在500×500以下時(shí)，速度提升不明顯，但大于500×500時(shí)，本文算法性能體現(xiàn)出了明顯的優(yōu)勢(shì)。為驗(yàn)證此結(jié)果，選取128×128，256×256，512×512，750×750和1024×1024的圖片各5張進(jìn)行實(shí)驗(yàn)，噪聲等級(jí)=25，取每種尺寸圖像運(yùn)行時(shí)間的平均值進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果見表2。從結(jié)果可以看出，2種算法的時(shí)間比率隨著圖像尺寸的增大而增大。

表2 2種算法在各尺寸下的運(yùn)行時(shí)間

4 結(jié)束語

本文在ANLM算法基礎(chǔ)上，從減少運(yùn)行時(shí)間的角度出發(fā)，對(duì)其2個(gè)部分進(jìn)行了改進(jìn)。首先簡(jiǎn)化仿射變換，使用仿射協(xié)變結(jié)構(gòu)張量特征向量的夾角來替換SIFT算子進(jìn)行主方向的計(jì)算，然后將仿射不變相似性度量改寫成離散卷積的形式，使用FFT對(duì)其進(jìn)行加速運(yùn)算。實(shí)驗(yàn)結(jié)果表明，本文提出的F-ANLM算法對(duì)基于仿射非局部均值算法加速方法具有可行性，在不損耗ANLM性能的基礎(chǔ)上速度提升的很快，效果極佳。

[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] 蕭澍, 胡靖, 王彥芳. 橢圓窗口和參數(shù)自適應(yīng)的非局部均值算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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] 陸海青, 葛洪偉. 混合魯棒權(quán)重和改進(jìn)方法噪聲的兩級(jí)非局部均值去噪[J]. 計(jì)算機(jī)工程與科學(xué), 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

國(guó)家自然科學(xué)基金項(xiàng)目(61801417)

National Natural Science Foundation of China (61801417)

陳玲玲(1994–)，女，江蘇鹽城人，碩士研究生。主要研究方向?yàn)槟Ｊ阶R(shí)別與圖像處理。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–)，男，山西長(zhǎng)治人，副教授，博士。主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、模式識(shí)別與圖像處理。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