基于Walsh-Hadamard投影的快速Nonlocal-Means图像去噪.pdfNLM改进论文

文件名称: 基于Walsh-Hadamard投影的快速Nonlocal-Means图像去噪.pdf

所属分类: 图像处理

开发工具:

文件大小: 879kb

下载次数: 0

上传时间: 2019-07-02

提供者: irwi*****

下载 (879kb)

不能下载？报告错误

详细说明：NLM改进论文，可供算法工程师参考，Walsh-Hadamard投影。382 宇航学报第32卷 NL- means模型利用观测图像中其它像素点的窗口内,将算法的计算复杂度降为o(m2·n2t2) 加权和来表示当前点图像像素值的估计,即2-1 即便如此, NL-means去噪算法的计算量还是比较 X()=NL()=∑o(i,Y()(2)大,特别是比较窗口和搜索窗口的尺寸较大时,算法权值o(i,j代表了像素点i和j的相关性, Buade速度较慢。提出使用以像素点和j为中心的图像块的欧式距由式(3)可知,对于目标像素点i和待匹配像素点j,其 NL-means模型的权值o(i,j)对于邻域的欧离平方去计算权值,即: Y,)-Y(,) 式距离成幂指数的衰减,若它们的距离较大时权值 zexu (3)则很小,而由式(2)可知像素j对目标点i的去噪结其中(1)为归一化函数,h是控制权值计算衰退速果影响很小由此可以看出,为了提高N-mms算度的参数,ψ,代表以像素点讠为中心的邻域像素块。法的计算效率,最重要的是如何快速丢弃那些最终在实际的NL- means图像去噪任务中,对于图像中无法匹配的图像块,从而避免了不必要的计算量。每一个像素点i,通过式(2)和式(3)的计算即可获各国学者不断提出了各种关于权值计算的加速算法,以改善算法的计算速度和性能,总的来说有如下得当前点的估计值X(i),遍历图像中所有的像素,两条具体途径: 即可得到噪声图像的 NL-means去噪结果X。 (1)在图像空间域中提取某种特征,从待匹配 NL- means模型的一经提出,迅速成为图像去噪的大量数据块中预选可能配准的块,除去大量不可领域的热点。随后,各国学者针对 NL-means模型做能配准的块,减小了所需计算的图像块数量; 了不少改进,主要的工作集中在提高算法效果和提 (2)在对两个图像块进行欧式距离计算时,使高计算效率两个方面。用某些简化的算法去获取欧式距离的近似值,以减在提高算法效果上,们考虑使用不同的图像少每一对图像块匹配的计算强度,或者快速地丢弃块相似性度量,获取更多的相似性点对,提高模型的距离过大的图像块。适应性,从而去提高图像去噪算法的效果,如前人的改进方法更多地考虑使用拒绝策略去除 Sun13提出了考虑增加±90°和1809旋转,水平、垂些主观上认为不合适的块,如: Mahmoudi2提出直和主次两条对角线的镜像这七种欧式距离计算时使用图像块的均值和方向这两个特征对图像块进行的图像块变化模型,更好地获取了图像中的冗余信预分类,在权值计算的时候,只考虑均值和方向相近息获得了优于传统 NL-means模型的去噪效果;的图像块进行比较,其它块的权值设为零,从而减少 Ji9提出使用具有旋转不变特性的 Zemike矩去计了计算量; Coupe(2)在 Mahmoudi工作的基础上,发算图像块间的相似性,从而获得更多的相似像素,提现图像块的方向特征易受所含的噪声影响,特别是高了算法的去噪效果; Kleinschmidt20提出了一种同对于平坦性区域,他提出使用图像块的均值和标准时对亮度、尺度和旋转变化稳健的块匹配方法。差进行预分类,获得了较好的加速性能和理想的去在 NL-means模型中,权值o(i,j用来衡量图噪效果;Brox21大量数据的管理方式出发,提出像中不同像素间的相似度,权值计算的有效性对相种基于聚类树( cluster tree)的NL- means算法。似度的精度起着重要作用,从而直接影响去噪算法该算法利用了二元树( binary tree结构去管理输入的效果。考虑传统NL- means模型,由式(3)可知,图像中大量交叠的图像块,将它们按照距离进行聚去噪算法通过对图像中每一点对的邻域ψ组成的向类,最终形成聚类树的数据管理结构。其中,每一个量进行欧式距离计算,从而进行权值的选取,其计算叶节点(lea)包含了一些类似的图像块,它们是距量是必须要考虑的问题。例如:对于图像的尺寸为m离小于一定阈值的图像块集合。在具体的权值计算 xm,所使用邻域图像块的尺寸为nxn的 NL-means时,该算法只考虑同类的图像块,缩小了搜索的范算法,其权值的计算复杂度为o(m·n2),计算量很围,进而提髙了算法的计算速度,在纹理图像去噪中大,占据了NL- means算法大部分的计算时间。获得了较好的加速效果 Buades提出将权重的搜索窗口限定在一定的txt 总的来说,研究者们所提出的各种方法都试图万方数据第2期张志等:基于 Walsh- Hadamard投影的快速 Nonlocal- Means图像去噪绕开图像块之间的欧式距离计算这一计算强度较大的步骤,这些算法在块匹配的步骤中有的使用其它些图像块距离的计算,或使用部分数据信息代替整体数据信息,还有使用均值、方向、方差等特征首先将图像块进行分类,和使用聚类树的结构将图像块进行聚类管理,最终使用拒绝策略,快速地丢弃大量不符合要求的待比较图像块,获得了不错的加速效果。然而,上述算法的思想在某种意义上是启发式( heuristic)的,在理论上并不完全等同于基于欧图1投影方法式距离测度的传统NL- means模型的算法,在实际的 Fig 1 Projection method 权值计算过程中,可能计算了实际上不符合匹配要求的图像块,使得算法加速性能受到影响,或者丢弃了实际上符合要求的图像块,使得算法去噪效果受由于欧式范数满足 Cauchy-Schwartz不等式,即到了影响 ‖u'd‖≤‖u‖·‖d (5) 本文提出一种基于投影的NL- means图像去噪从式(4)(5)可得的加速方法。与前人研究工作的不同之处在于,所 dis(p,W)=|p-wl‖ 提出的算法并不绕开欧式距离计算这一计算强度较 d≥a(P") 大的步骤使用一种在理论上完全等同于欧式距离计算的快速投影算法,从而在不损失图像去噪性能 1up-uw= dist, (p, w)(6) 的同时达到加速的目的。式(6)建立了空间域点的欧式距离dst(P,w)与其投影 2甚于投影的NL- means图像去噪算法空间上相应点的欧式距离之间的联系。当存在一组投影向量u1…un,可分别计算距离向量d对u的投影,可针对 NL-means的权值计算模型,可从中归结出得投影值b,=a2a,原始欧式距离可推导为一个模式匹配的问题:对于一个尺寸为nxn的图像 dist2(p,w)≥b(U'U)b 块,如何有效地从t2-1个nxn的图像块集合中寻其中:U=[1…Ln],b=(b1…bn)。由上式可以看找到欧式距离小于阈值T的图像块,并且获取相应出,当投影向量u1…ln为正交基的时候,p,w之间的的欧式距离。欧式距离平方的下界变为bb。当U的秩为n2时等号 2.1投影方法成立。此时,投影向量是完备的,投影值欧式距离平方投影方法是一类数据表示方法的统称,它将空间 bb等同于pw在空间域的欧式距离平方域数据投影到一些投影向量上,通过投影向量上的投由此可知,针对 NL-means去噪模型中的块匹配影值的信息获取比原始数据空间域表示更加优良的算法,可利用投影的思想,将图像块投影到一定的正性质,已广泛地运用于特征提取图像压缩和模式识交投影基函数上,然后通过计算每一个投影向量的别中。首先简单阐述投影方法的基本概念,给出空间欧式距离之和去不断逼近真实的两点间欧式距离, 域图像块之间的欧式距离计算及其投影值的欧式距直到这组投影函数是完备的,此时可以获得空间域离计算的等价条件,在理论上说明了基于投影的NL 中两点间的欧式距离。同时在计算过程中,能够通 means方法和经典NL- means方法的一致性。过快速地丢弃一些距离累积超过阈值的匹配对,以如图1所示,D,聊为中两个向量,用以表达到算法加速的目的。示两个nXn的图像块,两者之间的距离为 2.2投影向量的选取 dist(p,)=‖p-w‖=‖d‖=√ad(4) 如何选择合适的投影函数,对 NL-means模型加设向量u为一个投影向量,d在向量u上的投影为速算法的有效性起着决定性作用。在投影方法的运 b,即用中,人们根据实际需求提出了很多完备正交的投万方数据 384 字航学报第32卷影函数基,如Har函数系、正交小波、PCA等。然特性要求。而,分析本文的具体模型,对于投影向量的选取,必2.3基于 Walsh- Hadamard投影的NL. neans加速须考虑其两种特性要求: 算法 (1)投影向量必须具有较好的能量集中特性。为利用WH投影达到算法加速的目的,本文设这可以保证在计算最初若干个投影后即可最大限度计了一种基于WH投影的NL- means加速算法。算的接近两个待匹配图像块的真实欧式距离,以便于法示意图如图2所示,具体的步骤如下: 算法预先丢弃一些不合适的匹配图像块,节省计算基准图像块吋间,达到加速的目的,这也是本文考虑使用投影方法的出发点; (2)投影向量的生成和投影运算必须是快速和高效的,以保证投影向量自身的运算不至于在匹配算法中额外增加太大的计算负担。这样以来,小波待匹配变换由于其计算的复杂性就不适合本文算法的使 :图像块对用,而PCA变换这类变基的降维方法由于其基函数需要适应数据的要求,也被排除在外了。本文选择 Walsh-Hadamard(WH)变换核作为投影向量。Wash函数是1923年由美国数学家JL. 逐点的WH变换 Walsh提出的, Walsh函数系是一个完备正交函数系, 其值只能取+1和-1。按行列排列次序不同可将 s4x8598:880 23 Walsh函数分为三种定义方法:一种是按照 Walsh排列来定义;另一种是按照 Paley排列来定义;第三种是按照 Hadamard排列来定义。 Hadamard排序的 Walsh 6 按 sequency排序函数是由2”阶 Hadamard矩阵得到的,而 Hadamard 待匹配的WH向量对矩阵的一个重要优点在于它具有简单的递推关系,即图2基于 WalshHadamard投影的 NI.means加速算法高阶矩阵可用两个低阶矩阵的 Kronecker积②推导求 Fig 2 Fast NL-means image denoising algorithm with 得。两个基本WH矩阵如下: alshHadamard projection H1=(1],H2= (8) 在初始化步骤中,按照预设的比较窗口大小将输入的含噪声图像Y进行逐点的图像块选取,然而阶数较高的WH矩阵,可以利用矩阵的 Kronecker后进行WH投影,随后将获得的投影值按照序增排积运算,由低阶WH矩阵递推得到,即: 列成一个二维数组M,M的列数为所考虑WH投影 H2,=H2②H2 H1(9)基函数的数目,行数为总的图像块数量,由于传统 H H DEmeans模型采用的是逐点的邻域,列数也就等于 Hel-Or等人的研究表明,对于图像块匹配任原始图像中像素点的个数;然后根据 NL-means模型务来说,图像块对以序增排序的前几个WH核的投中的方法进行权值计算,对于基准图像块P和匹配影即可获得图像大部分的能量,这说明了WH核具窗口内待匹配图像块w,从矩阵M中选取各自对应有良好的能量集中特性,也就是具有良好的维数削的WH投影向量值P.和w,按照序增方向的顺序减能力;另外,WH核可使用自迭代生成,其只有+1i依次递增计算距离的平方和∑ds'(p(i) 和-1二值,投影计算仅需要处理整数的加法和减 w,(i),当其大于一定阈值,该匹配算法终止,返法,不需要进行浮点运算,且有快速算法,所以WH 回。该匹配对无法匹配,直到将当前点对所有的核的生成和投影运算的计算速度很快。因此,选择 WH基计算完毕,此时返回到两个图像块之间的欧 WH基函数作为投影核,能够较好的满足前述两个万方数据第2期张志等:基于 Walsh- Hadamard投影的快速 Nonlocal-Means图像去噪 385 式距离平方;当遍历所有匹配窗口时,该基准图像客观比较使用了峰值信噪比( Peak Signal to Noise 块p的匹配结束,通过计算权值及加权灰度值即可Raio,PSNR)和结构相似度( Structural Similarity, 获得当前点的去噪结果;遍历全图,可获得图像的 SM)两个参数。SSIM参数是Wang等人最近提出去噪结果。的图像质量评价度量,用以度量两幅图像间的结在具体的WH变换的计算中,可以使用 Ouyang构性失真。对于两个图像矩阵X,Y而言,具体数学等最近提出的滑动窗口快速WH变换,其对于每表示为一个窗口的每一个投影向量平均仅需1.5次加法运 Q(x, Y) Puxur 2oxUr (10) 算,所以对于整个图像进行逐点WH投影的计算量 Uxor ux+ Ay or+ or 相对于即便限定搜索窗口的 NL-means方法计算复其中p和a分别代表图像灰度值的均值和标准差, 杂度O(2·m2n2)来说也是很小的,几乎可以忽ox代表协方差,当图像完全一致时,sM为1 略。更重要的是,由于WH投影具有良好的能量集中特性,所以在计算距离dist(p.(i)-w(i) 时,按照序增方向排列的前若干个WH投影值即可获取绝大部分图像的能量,对于最终结果大于允许阈值的点,在最初的若干个投影计算中即可被滤除算法的高效性得到了保障。 3仿真实验及结果 (a) Barbara(512×512) (b) House(256×256) 为证明本文提出加速算法的有效性,根据算法图3标准测试图像框架做了仿真实验,并与传统的 NL-means方法 Fig 3 Standard test images (NLM)以及 Coupe(C.NLM)2和Brox(BNLM)1231 参数的设置在NL- means图像去噪算法中起着所提出的加速方法进行了对比。本文的实验平台为重要的作用,主要包括:比较窗口大小n、搜索窗口 Windows XP操作系统,Malb7.6(R2008a)软件和大小t滤波衰退参数h等。本文根据相关文献的结 Microsoft Visual C++6.0编译器, Intel Core"2论.3),选取比较窗口大小为8×8,搜索窗口大小 Duo CPU E74002.8CHt微机,2GB内存。实验选23×23,滤波衰退参数h设为0.7倍的标准差,将拒取两幅不同尺寸的标准测试图像:512×512的Bar-绝阈值T设定为6倍的噪声方差。B-NLM方法的结 bara和256×256的 House图像“,如图3所示(为果由原文作者提供的可执行文件在同配置硬件平台便于显示,已将图像缩至一定比例)。分别从算法的64位 Linux环境下( Ubuntu9.10)运行获得的去的计算时间和去噪效果上进行了比较,去噪效果的噪效果及加速性能。表1图像去噪实验结果的定量比较 Table 1 Quantitative comparison of image denoising results barbara House PSNR/db SSIM 百分比/%5NR/b 百分比/% NLM 31.6393 0.9023 100.00 33.1693 0.8550 100.00 C-NIM 31.2992 0.8951 41.83 32.9097 0.8546 54.53 R-NLM 31.1785 0.8796 63.34 32.7911 0.8288 57.07 WH-NLM 31.6783 0.9028 24.94 33.2138 0.8567 29.25 表1给出了两幅实验图像在四种算法下的去噪种加速算法使用的是启发式的拒绝策略,在算法加效果,其中噪声标准差设为15,加速效果由所占标速的同时可能会造成匹配块的误丢弃,所以去噪效准NLM算法计算时间的百分比来表示,其数值是通果较标准的NLM算法有一定的损失;本文算法由于过20次重复实验所获得的平均值。本身等价于两个图像块的欧式距离的计算,所以在从表1中可以看出,由于CNLM和BNLM两获得优于CNIM和BNLM算法加速效果的同时并万方数据 386 宇航学报第32卷没有造成图像去噪效果的损失。并且由于设定了拒放大图,如图4所示。图4(a)给出的是原始 Barba- 绝阈值,也将大量的欧式距离大于阈值的不符合块ma图像,图4(b)是其相应的噪声图像,图4(c)为标图像排除出权重的计算,所以算法效果较标准的准NLM算法的结果,图4(d)为CNLM算法的结 NLM算法有略微提升。果,图4(e)为B-NLM算法的结果,图4(f)为本文算为展示几种 NL-means算法的图像去噪效果,由法的结果。从图中可以看出,本文算法在去噪效果于它们在整体上质量相差不大,为节省篇幅,以Bar-上与标准NLM算法的结果比较接近,在细节上略优 bara图像为例,给出了几种算法的去噪效果的细节于其它两种加速算法。 (c) 图4结果图像细节放大图的比较(a)真实图像:(b)噪声图像;(c)标准NLM算法; (d)CNLM算法;(e)B-NM算法;(f)本文算法 Fig. 4 Comparison of partially magnified images. (a) Ground trth:(b) Noisy image (e)Standard NL-means algorithm:(d)C-NLM algorithm:(e)BNLM algorithm;(f) Proposed algorithm 4结论匹配的计算量,提高了计算效率。与其它用拒绝策略提高算法计算速度的研究工本文提出了一种基于投影的 NL-means图像去作不同之处在于,本文所提出的算法并不绕开欧式噪加速算法。首先分析了传统 NL-means算法的计距离计算这一计算强度较大的步骤,而是使用一种算瓶颈,在前人工作的基础上,提出使用 Walsh-Had-快速 Walsh-Hadamard投影算法,其优点在于:利用 amard变换将图像投影到一组完备正交的 Walsh- Walsh-Hadamard基的完备性,使得投影值的匹配计 Hadamard基上。在图像块匹配时,利用其较好的能算等价于空间域的像素值的匹配计算,匹配算法的量集中特性,在使用少量投影值的计算时就能够将效果在理论上不会受到损失;同时由于 Walsh-Had 不可能匹配的图像块排除,从而大幅削减了图像块amar基的能量集中特性,算法可以快速地丢弃不万方数据第2期张志等:基于 Walsh- Hadamard投影的快速 Nonloca- Means图像去噪 387 可能匹配的图像块,达到算法加速的目的。理论和[15]EadM, Aharon M. Image denoising via sparse and redundant 实验结果证明,本文的方法在图像去噪效果不受到 representations over learned dictionaries[ J].IEEE Transactions on image Processing, 2006, 15(12 ) 3736-3745 损失的情况下,算法的计算效率得到了提升。 [16] Efros A A, Leung T K. Texture synthesis by non-parametric sa pling[ C]. IEEE International Conference on Computer Vision 参考文献 (ICCV1999), Corfu, Greece, September 20-25, 1999. [1] Perona P, Malik J. Scale-space and edge detection using aniso- [17] Zhang D, Wang Z. Image information restoration based on long ange correlation[ J]. IEEE Transactions on Circuits and Systems tropic diffusion[ J]. IEEE Transactions on Pattern Analysis and for Video Technology, 2002, 12(5): 331-341 Machine Intelligence, 1990, 12(7): 629-639 [18]Sun W F, Peng Y H, Hwang W L. Modified similarity metric for [2]Rudin L, Osher S, Fatemi E. Nonlinear total variation based non-local means algorithm [J ]. Electronics Letters, 2009, 45 noise removal algorithms[J]. Physica D, 1992, 60(1-4) [19 Ji Z Q, Sun Q S, et al. 3] Roth S, Black M J. Fields of experts: A framework for learning means algorithm for image denoising[ J]. Information Processing image priors[ C]. IEEE Conference on Computer Vision and Pat ttr,2009,109(23-24):1238-1244 tern Recognition( CVPR2005), San Diego, USA, June 20-26, [20] Kleinschmidt 0, Brox T, Cremers D. Nonlocal texture filtering 2005 with efficient tree structures and invariant patch similarity meas- [4] Roth S, Black M J. Fields of experts[ J]. International Journal ures[C]. International Workshop on Local and Non-Local Ap. of Computer Vision, 2009, 82(2): 205-229 proximation in Image Processing, Lausanne, Switzerland, august [5] Tappen M F, Liu C, Adelson E H, et al. Learning gaussian con 23-24,2008 ditional random fields for low-level vision[ C]. IEEE Conference [21] Mahmoudi M, Sapiro G. Fast image and video denoising via non- on Computer Vision and Pattem Recognition( CVPR2007),Min- similar ne sJ]. IEEE neapolis, USA, June 18-23, 2007 Letters,2005,12(12):839-842 6] Liu C, Szeliski R, Kang S B, et al. Automatic estimation and re [22] Coupe P, Yger P, Prima S, et al. An optimized block wise nonlo- moval of noise from a single image[J]. IEEE Transactiong on cal means denoising filter for 3-D magnetic resonance images[J] Pattern Analysis and Machine Intelligence, 2008, 30(2 ): 299 IEEE Transactions on Medical Imaging, 2008, 27 (4):425 314. [7 Mallat S. A wavelet tour of signal processing[ M 0 [23] Brox T, Kleinschmidt 0, Cremers D. Efficient nonlocal means Academic Press, 1997 for denoising of textural pattems[ J]. IEEE Transactions on Im- [8]焦李成,谭山.图像的多尺度几何分析:回顾和展望[门].电 age Processing,2008,17(7):1083-1092 子学报,2003,31(12A):1975-1981.[ Jiao Li-Cheng,Tan [24] Hel-Or Y, Hel-Or H. Real-time pattern matching using projec- Shan. Development and prospect of image multiscale geometric a- tion kernels[ J]. IEEE Transactions on Pattern Analysis and Ma alysis[J]. Acta Electronica Sinica, 2003, 31(12A): 1975 chine Intelligence, 2005, 27(9): 1430-1445 1981.] [25 Ouyang W, Cham W K. Fast algorithm for Walsh-Hadamard [91 Takeda H, Farsiu S, Milanfar P. Kernel regression for image processing and reconstruction[J]. IEEE Transactions on Image transform on sliding windows[ J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(1):165-171 Processing,2007,16(2):349-366. 26] Portilla J, Strela V, Wainwright M J, et al. Image denoising u- [10 Tomasi C, Manduchi R. Bilateral filtering for gray and color ima sing scale mixtures of Gaussians in the wavelet domain[ J]. IEEE ges[ C]. IEEE International Conference on Computer Vision Transactiong on Image Processing, 2003, 12(11): 1338-1351 (ICCV1998), Bombay, India, January 4-7, 1998 [ 27] Wang Z, Bovik A C, Sheikh H R, et al. Image quality assess- [11 Elad M. On the bilateral filter and inn prove it[J IEEE ment:from error visibility to structural similarity[J]. IEEE Transactions on Image Processing, 2002, 11(10):1141-1151 Transactions on Image Processing, 2004, 13 (4): 600-612 [12 Buades A, Coll B, Morel J M. A review of [28]Van-De-Ville D, Kocher M. SURE-based non-local means[ J] rithms, with a new one[ J]. Multiscale Modeling and Simulation IEEE Signal Processing Letters, 2009, 16(11):973-976 2005,4(2):490-530 [13 Buades A, Coll B, Morel JM. nonlocal image and movie denis- ing[ J]. International Journal of Computer Vision, 2008, 76 作者简介:张志(1982-),男,博土,主要从事图像处理、分析与理解等方面的研究 (2):123-139 [14] Dabov K, Foi A, Katkovnik V, et al.Im 通信地址:北京市2861信箱六分箱(10085) 电话:(010)66919834-865 3-D transform-domain collaborative filtering[ J]. IEEE Transac- E-mail:zhizh.zhanggmail.com tions on Image Processing, 2007, 16(8): 2080-2095 (编辑:余未) 万方数据

(系统自动生成,下载前可以参看下载内容)