一種快速的三維塊匹配圖像去噪方法*

韓玉蘭，宣士斌，b，c，劉香品

（廣西民族大學a.信息科學與工程學院；b.廣西混雜計算與集成電路設計分析重點實驗室；c.中國－東盟研究中心，廣西　南寧　530006）

一種快速的三維塊匹配圖像去噪方法*

韓玉蘭a，宣士斌a，b，c，劉香品a

（廣西民族大學a.信息科學與工程學院；b.廣西混雜計算與集成電路設計分析重點實驗室；c.中國－東盟研究中心，廣西南寧530006）

為了在不降低三維塊匹配算法（BM3D）效果的基礎上，提高其運算速度，提出一種基于積分圖的BM3D的加速算法.在新的算法中，首先利用高斯濾波器對原圖像進行粗去噪，再利用積分圖計算塊的相似性，在塊的相似度計算過程中不再進行濾波.在BM3D的第二步維納濾波中，經過對原算法計算過程進行相應的轉換，也可將積分圖應用于該階段.實驗表明，改進后的算法，不但保留了三維塊匹配算法在去噪方面好的性質，而且運算時間縮短了近1/4.

三維塊匹配；圖像去噪；高斯濾波器；積分圖；快速傅里葉變換

0　引言

圖像去噪作為圖像處理的基本技術之一，受到廣泛的重視.其目的是為了去除圖像獲取或者傳輸中的各種噪聲污染，其結果直接影響后繼的圖像處理與理解，是圖像預處理階段的重要工作.

目前已有多種圖像去噪的方法，其側重點各有不同.但其目的都是改善圖像質量，突出圖像本身的特征.近年來，較好的圖像去噪算法有基于稀疏表示的字典學習算法[1－2]，基于高斯尺度混合模型[3－5]，基于自適應DCT算法[6－7]和非局部濾波的算法[8－9]等，尤其是Buades[10]等提出的三維塊匹配算法（Block Matching 3D，BM3D）去噪效果最突出.

由于BM3D算法具有良好性能，所以一經提出很快引起了廣泛關注，基于BM3D算法的新理論與應用研究成果不斷被報道.黎思敏[11]根據圖像局部結構相似性提出了基于結構聚類的圖像去噪算法，該方法保護了圖像的結構信息，提高了BM3D算法的視覺效果.楊娟[12]根據三維塊匹配中3－D變換稀疏表達能力弱的問題提出基于形狀自適應PCA的三維塊匹配圖像去噪算法.不僅如此，在醫學圖像處理中，BM3D算法也得到廣泛應用[13].劉向樂[14]提出了小波域三維塊匹配圖像去噪，該方法明顯減少了運算量，但BM3D算法的本質結構并沒有改變.劉艷麗[15]提出一種魯棒、快速的非局部均值圖像去噪算法，文中把圖像金字塔分解和非局部思想結合起來，并通過引入積分圖和快速傅立葉變換[16]對算法加速，是一種快速有效的圖像去噪方法.因此，受積分圖和快速傅立葉變換來加速算法的啟發，筆者針對BM3D算法運算量大，運行時間長這一缺點，提出了一種BM3D圖像去噪的加速算法.

在提出的新算法中，首先利用高斯濾波器對原圖像進行粗去噪，再利用積分圖計算塊的相似性，在塊的相似度計算過程中不再進行濾波.在BM3D的第二步維納濾波中，通過對原算法計算過程進行細致分析，發現可以對原算法計算過程進行適當轉換，經轉換后也可利用積分圖降低該階段計算代價.實驗表明，改進后的算法不僅保留了原BM3D算法在去噪方面的良好效果，更重要的是加快了計算速度.

1　BM3D算法與積分圖理論

1.1BM3D算法去噪

BM3D算法是一種多尺度、非局部的濾波技術，算法的詳細過程已在文獻[10]中介紹，這里只對其一部分進行簡要說明.BM3D算法首先把圖像分成一定大小的塊，根據圖像塊之間的相似性，把具有相似結構的二維圖像塊組合在一起形成三維數組，然后用聯合濾波的方法對這些三維數組進行處理，最后通過逆變換，把處理后的結果返回到原圖像中，從而得到去噪后的圖像.算法主要為“分組”和“聯合濾波”兩部分.根據圖像結構的相似性，把具有相似結構的圖像塊組合在一起，并形成三維數組的過程稱為“分組”.根據數組中圖像塊的相似性來估計真實圖像的過程稱為“聯合濾波”.聯合濾波又分聯合硬閾值和聯合維納濾波兩部分，分別代表基礎估計和最終估計.

1.1.1聯合硬閾值

其中χ是屬于圖像域X?Z2的二維空間坐標，y是真實圖像，η是零均值的方差為σ2的高斯噪聲：

文獻[10]提出了一種粗糙的預濾波算法來計算圖像塊之間的距離.這個預濾波是通過對兩個圖像塊先實施一個正則二維線性變換后再對得到的變換系數進行閾值得到的.對于含噪圖像z，圖像塊ZχR和圖像塊Zχ之間的距離表示為

1.1.2聯合維納濾波

1.2積分圖原理

積分圖的概念由Viola提出并用于計算窗口圖像的Harr特征[17].圖像上任意一點（χ，y）的值是指從灰度圖像的左上角與當前點所圍成的矩形區域內所有像素點的灰度值之和.

定義對任意圖像g，其積分圖在（χ，y）處的灰度值ii（χ，y）為圖像g中該點左上方所有像素灰度值的積分.即

利用積分圖，如圖1陰影區域所示D，L2中以（χ0，y0）為左上頂點的子塊D的灰度值的積分為

圖1　利用積分圖計算窗口D積分示意圖Fig.1　Using SSI to compute the summed squared pixels in the rectangle D

2　快速的三維塊匹配圖像去噪算法

在BM3D算法中，它把圖像分成一定大小和形狀的塊.對每一個圖像塊，都要分別計算與其他的圖像塊的相似性，且在計算圖像塊之間距離的同時，進行粗糙的預濾波，如公式（1）所示.BM3D算法的計算量主要由計算塊相似度產生.由公式（1）可知，每計算一次圖像塊與參考塊之間的距離，都要進行一次濾波，那么在整幅圖像里尋找相似塊就會導致每一個像素點都要運算多次，這樣會導致重復計算，運算量非常大.因此，為了解決這個問題，筆者在計算塊相似度之前進行簡單的預濾波，在計算塊相似度時不再進行濾波，并利用積分圖來計算塊相似度.運用積分圖計算，圖像中的每個像素只需處理一次，從而有效降低計算復雜度，大大提高了塊匹配的速度.

筆者采用的預濾波是粗糙的高斯去噪，則圖像塊之間的距離由公式（1）變為：

基于此，第一步基礎估計中圖像塊之間的距離可求，即公式（1）.

圖2　鏡像圖像Fig.2　Mirrored image

同理，在第二步維納濾波去噪時，兩個圖像塊之間的距離由公式（3）求得，公式（3）可轉換為

綜上所述，圖像塊之間的距離都可應用積分圖來計算，并避免了塊匹配中像素的重復處理，大大減少了計算代價，提高了算法速度.

3　運算量

實際應用中，不僅視覺效果是去噪算法的評價標準，而且運算量和運算時間也是重要的指標.BM3D算法是塊匹配時運算量大，而文中提出的在塊匹配時應用積分圖和快速傅里葉變換則減少了運算量，對算法起到了加速的作用.我們知道BM3D去噪算法結合了非局部的思想，而它們都有一個問題，即圖像塊匹配所帶來的巨大運算負擔.塊匹配是通過歐氏距離來度量的，因此這里的瓶頸問題就是圖像比較窗口之間歐氏距離的計算.在非局部算法中，用S×S的搜索窗代替整個圖像，圖像中每個像素的計算量就是M2× S2，其中M2是比較窗口的大小.把這一過程轉化為計算積分圖和卷積.眾所周知，卷積是在傅立葉變換下的乘法，因此圖像中每個像素就只要S2次乘法.此外，傅里葉變換可以采用快速傅里葉變換來縮短運算時間，從而實現快速卷積.至于積分圖，在這個過程中只有加法運算，它和乘法運算相比時間復雜度可忽略不計.因此，計算的復雜性是S×S，所以轉換為積分圖和卷積運算要比原算法快M2倍.

原BM3D去噪算法的時間復雜度如下所示：

其中：前兩項是計算塊匹配的時間，第三項是通過正則三維線性變換的去噪時間，M×N是圖像的大小，N1×N1是比較窗口的大小，NS是搜索鄰域的邊長，Nstep是搜索窗的滑動步長.T2D和T3D分別是正則二維線性變換和正則三維線性變換.

根據積分圖和卷積的思想，本文算法的時間復雜度如下：

4　實驗結果和分析

在2.99GHz，2GB內存的AMD Athlon（tm）ⅡX2B24處理器下，使用工具MATLAB 7.10來實現算法，利用高斯濾波器對原圖像進行粗去噪時，筆者算法選用的模板尺寸（3×3），sigma取默認值0.5.分別從兩個方面對實驗結果進行對比和分析，一方面從實驗圖像的角度看，分別采用國際標準測試圖像和紋理復雜的圖像進行實驗分析，對兩種圖像均添加不同程度大小的噪聲，實驗結果表明本文提出改進的加速算法不僅有效去除噪聲，并且處理紋理復雜的圖像效果良好，保留了更多的圖像細節，同時針對不同大小的實驗圖像加速效果顯著.另一方面，通過在小波域應用BM3D算法，筆者提出的加速算法比原始的BM3D算法縮短運行時間近1/6，大大減少了運算量.

4.1標準圖像上的對比試驗

首先采用大小為512×512的Lena圖像，對其添加均值為0，標準差為σ＝25的高斯白噪聲，并分別用BM3D算法和本文算法對其去噪，實驗結果如圖3所示.通過對比觀察，圖3（d）比圖3（c）的圖像視覺效果更好，保留了更多的圖像細節.

對Lena圖像和House圖像分別加入標準差為15、20、25、30、35的高斯白噪聲（其中噪聲均值均為0）.表1列出了這兩幅圖像在不同噪聲水平下去噪后的峰值信噪比（PSNR）.從表中可以看出，筆者改進的算法峰值信噪比更高，去噪效果更好.

圖3　兩種算法去噪效果對比圖Fig.3　Comparison between the results obtained by BM3Dand that of our method for noisy image

表1　兩種算法效果對比Tab.1　Denoising Results in PSNR（in[dB]）

圖4是兩算法PSNR的對比圖（House圖像），更直觀地反映算法結果，由圖4可以看出，隨著噪聲的增大，本文算法的去噪效果越明顯.

圖4　本文算法和BM3D算法峰值信噪比的比較Fig.4　Comparison of PSNR between our method and BM3Dalgorithm

不僅如此，為了體現本文算法的有效加速，我們采用不同大小的圖片作比較，對比結果如表2所示（表中數據均為運行10次的平均值）.實驗結果表明，本文算法比BM3D算法運行時間縮短了近1/4.

表2　性能測試結果Tab.2　Performance results

4.2復雜圖像上的對比試驗

為了更好地說明算法的適用性，另選取一幅細節豐富的Baboon圖像（大小為512×512），在圖上提取了一個大小為15×15的圖像子塊，如圖5（a）所示，其中小方框為所取子塊，圖5（b）為放大后的子圖，圖5（c）為添加均值為0，標準差為σ＝20的高斯白噪聲子圖，圖5（d）為BM3D算法處理后結果，圖5（e）為使用本文算法對子圖處理后效果圖.從濾波結果不難看出，在一定程度上，圖5（e）要比圖5（d）更清晰，在子圖的邊緣分界處圖5（e）要比圖5（d）更分明，保留了更多細節.

圖5　圖像子圖加噪σ＝20前后結果對比Fig.5　Comparison of PSNR（σ＝20）between our method and BM3Dalgorithm

為進一步驗證算法，這里選用Baboon圖像和紋理復雜的Fingerprint圖像（大小為512×512）為實驗對象，對其分別添加標準差為20、30、40、50、60的高斯白噪聲（均值為0），實驗結果如表3所示，從表中不難看出，本文算法的去噪效果更高；圖6為兩算法PSNR的對比圖（Baboon圖像），圖7為Fingerprint圖像加噪（σ＝50）處理前后效果圖，對于紋理復雜的圖像，本文算法在保留BM3D算法的基礎上，可以保留更多紋理信息.綜上，結合表3、圖6和圖7得出，對于紋理和細節復雜的圖像，本文算法不僅從主觀視覺上質量有所改進，在客觀評價標準上，更是優于BM3D算法.

表3　兩種算法效果對比Tab.3　Denoising Results in PSNR（in[dB]）

圖6　本文算法和BM3D算法峰值信噪比的比較Fig.6　Comparison of PSNR between our method and BM3Dalgorithm

圖7　兩種算法去噪效果對比圖Fig.7　Comparison between the results obtained by BM3D and that of our method for noisy image

通過選用較小尺寸的復雜紋理圖片（這里是人臉圖像）作比較，獲得如表4所示的對比實驗結果，表中時間數據均是計算10次的平均值，由表4可以看出，在復雜紋理圖像的條件下，對于不同大小的實驗對象，本文算法加速效果顯著，比BM3D算法時間縮短1/4.

表4　性能測試結果Tab.4　Performance results

4.3與其他濾波方法的比較

文獻[14]提出的是小波域三維塊匹配的圖像去噪（WBM3D），該方法首先對含噪圖像利用塔式分解理論進行分解，然后對小波分解后的高頻分量利用BM3D算法去噪處理，最后用處理后的結果進行小波逆變換逐層重構得到去噪圖像.因此，為了證明本文加速算法的有效性，我們在小波域應用本文算法和BM3D算法，對比兩種算法的實驗結果，如表5所示.由表可知，小波域的BM3D去噪算法，本文算法要比原始的BM3D算法縮短運行時間近1/6，大大減少了運算量.

表5　在小波域性能測試結果Tab.5　Performance results in wavelet

5　結語

筆者受積分圖和快速傅里葉變換加速算法的啟發，提出了一種快速的三維塊匹配圖像去噪方法.該方法在保留原BM3D算法效果的基礎上，提高了運算速度.本文算法中，首先利用高斯濾波器對原圖像進行粗去噪，再利用積分圖計算塊的相似性，在塊的相似度計算過程中不再進行濾波.在BM3D的第二步維納濾波中，經過對原算法計算過程進行相應的轉換，也將積分圖應用于該階段.實驗結果表明，在不同紋理特征的圖像下，從主觀視覺和客觀評價標準上都可以得出，改進后的算法不僅在三維塊匹配算法去噪方面有所提升，而且運算時間縮短了1/4左右.

[1]Elad M，Aharon M.Image Denoising via Sparse and Redundant Representations over Learned Dictionaries[J].IEEE Transactions on Image Process，2006，15（2）：3736－3745.

[2]Li Shutao，Yin Haitao，Fang Leyuan.Group－sparse representation with dictionary learning for medical image denoising and fusion[J].IEEE Transactions on Biomedical Engineering，2012，59（12）：3450.

[3]David K.Hammond and Eero P.Simoncelli.Image Modeling and Denoising With Orientation－Adapted Gaussian Scale Mixtures[J]. IEEE Transactions on Image Processing，2008，17（11）：2089－2101.

[4]Goossens B，Piˇzurica A，Philips W.Image Denoising Using Mixtures of Projected Gaussian Scale Mixtures[J].IEEE Transactions on Image Processing，2009，18（8）：1689－1702.

[5]Rakvongthai Y，Vo P N.Complex Gaussian Scale Mixtures of Complex Wavelet Coefficients[J].IEEE Transactions on Signal－Processing，2010，58（7）：3545－3556.

[6]Foi A，Katkovnik V，Egiazarian K.Pointwise Shape－Adaptive DCT for High－quality Denoising and Deblocking of Grayscale and Color Images[J].IEEE Transactions on Image Processing，2007，16（5）：1395－1411.

[7]Bergmann?rjan，Christiansen Oddvar，Lie Johan，Lundervold Arvid.Shape－Adaptive DCT for Denoising of 3DScalar and Tensor Valued Images[J].Journal of Digital Imaging，2009，22（3）：297－308.

[8]Tasdizen T.Principal Neighborhood Dictionaries for Non－local Means Image Denoising[J].IEEE Transactions on Image Processing，2009，18（12）：2649－2660.

[9]B.K.ShreyamshaKumar.Image denoising based on non－local means filter and its method noise thresholding[J].Signal Image and Video Processing，2013，7（6）：1211－1227.

[10]Dabov K，Foi A，Katkovnik V，et al.Image Denoising by Sparse 3DTransform－domain Collaborative Filtering[J].IEEE Transactions on Image Processing，2007，16（8）：2080－2095.

[11]黎思敏，何坤，龍輝，等.基于結構聚類的圖像去噪[J].計算機應用研究，2013，30（4）：1234－1236.

[12]楊娟，賈振紅，覃錫忠，等.基于形狀自適應PCA的三維塊匹配圖像去噪[J].計算機工程，2013，39（3）：241－244.

[13]畢一鳴，馬建華，劉楠，等.基于Anscombe變換域BM3D濾波的低劑量CT重建[J].計算機工程與應用，2010，46（13）：216－220.

[14]劉向樂，馮象初.小波域三維塊匹配圖像去噪[J].計算機工程與應用，2010，46（16）：185－187.

[15]Liu YL，Wang J，Chen X et al.A robust and fast non－local means algorithm for image denoising[J].JOURNAL OF COM－PUTER SCIENCE AND TECHNOLOGY，2008，23（2）：270－279.

[16]殷松峰，王一程，曹良才，等.基于快速傅里葉變換和積分圖的快速相關匹配[J].光子學報，2010，39（12）：2246－2250.

[17]Viola P，Michael J.Rapid object detection using a boosted cascade of simple features[C].In Proc.IEEE CVPR，Hanoii，USA，2001：511－518.

[責任編輯 蘇 琴]

[責任校對 黃招揚]

Image Denoising with a Fast Block－Matching and 3D Filtering Algorithm

HAN Yu－lana，XUAN Shi－bina，b，c，LIU Xiang－pina
（a.School of Information Science and Engineering；b.Guangχi Key Laboratory of Hybrid Computation and IC Design Analysis；c.The China－ASEAN Study Center of Guangχi University for Nationalities，Guangχi University for Nationalities，Nanning530006，China）

In order to reduce the computation time an accelerated algorithm which based on the efficient Summed Square Image（SSI）scheme is proposed in this paper.The new algorithm uses Gaussian filter to do the coarse denoising for original image first，and then SSI scheme is introduced to calculate the similarity of block.Besides，in the second process of BM3Dwhich called wiener filtering，integral image can also be applied after the corresponding conversion of the original algorithm.Experiments have shown that the proposed algorithm not only retains the superior performance of BM3Dalgorithm，but also reduces the operation time by about 3times.

block－matching and 3Dfiltering；gaussian filter；image denoising；summed square image；fast fourier transform

TN911.73

A

1673－8462（2015）02－0073－08

2015－01－03.

廣西自然科學基金項目（2012GXNSFAA053227）；廣西民族大學中國－東盟研究中心項目（KT201325）；廣西民族大學研究生教育創新計劃項目（gxun－chx2014088）.

韓玉蘭（1989－），女，吉林松原人，廣西民族大學碩士研究生，研究方向：圖像處理、視頻處理；宣士斌（1964－），男，安徽無為人，博士，廣西民族大學教授，碩士生導師，研究方向：圖像處理與模式識別.