一种基于图论的自适应滤波算法

汪云飞，毕笃彦，马时平

(空军工程大学 航空航天工程学院，陕西 西安，710038)

摘要：针对脉冲噪声特点，提出一种基于图论的自适应滤波(SAFG)算法。该算法首先设置全局阈值标识出所有可能的噪声点；然后，对每一噪声点进行局部操作，通过比较不同滤波窗口的置信度，自适应调整窗口大小，选择合适的置信滤波窗口；最后，采取两步滤波策略，利用窗口中的非噪声点信息对噪声点进行修复。仿真实验结果表明：SAFG算法不仅能有效抑制强脉冲噪声的干扰，而且可较好地保留图像的细节特征，滤波性能均比经典的中值滤波(MF)和维纳滤波算法的强。

关键词：图像滤波；图论；脉冲噪声；置信窗口；置信度

中图分类号：TP391          文献标志码：A         文章编号：1672-7207(2013)10-4117-07

A self-adaptive filter algorithm based on graph theory

WANG Yunfei, BI Duyan, MA Shiping

(Aeronautics and Astronautics Engineering College of Air Force Engineering University, Xi’an 710038, China)

Abstract: In light of the characteristics of impulse noise, a novel self-adaptive filter based on graph theory(SAFG) approach was presented. The first step of this algorithm was to identify the impulse noise nodes of image by setting global threshold; Then, each identified node was partially operated. By comparing confidence degrees of different filter windows, the size of window was self-adaptively adjusted, so the filter window for each noise node was chosen. Finally, a two-step filter strategy was adopted, maked use of the un-noise information around noise node in this confidence filter window to restore noise nodes. The results demonstrate that the filter capabilities of the proposed SAFG algorithm can not only effectively suppress the strong impulse noise disturbing, but also preserve the image details well. It is better than traditional median-filter(MF) algorithm and Wiener filter algorithm.

Key words: image filters; graph theory; impulse noise; confidence window; confidence degree

图像在采集或传输的过程中，由于技术缺陷或人为因素总会受到不同程度的噪声干扰，使获取的图像质量常达不到预期要求，给后续处理带来困难。在这些干扰噪声中，脉冲噪声(即椒盐噪声)作为一种较难去除的干扰经常出现，很多学者对其进行了深入研究，发现基于次序统计模型的中值滤波(MF)算法^[1]对脉冲噪声有明显的滤除效果；在此基础上又陆续出现了一些改进的MF算法^[2-5]，但这些算法在应用时仍存在一些局限性，如：(1) 参数设置困难^[4]；(2) 只适用于低密度的脉冲噪声，对于高密度的脉冲噪声滤波效果不理想，且随着噪声密度的增强性能逐渐接近于MF算法^[2-3]；(3) 很难在滤波效果和图像清晰度之间取得较好的平衡^[2-4]。近年来，图论因为能描述图像的拓扑结构得到广泛关注^[6-10]。本文作者提出一种基于图论的自适应滤波(SAFG)算法，该算法将图理论引入MF算法，使滤波窗口可自适应地根据图像信息进行拉伸，取得良好的滤波效果。SAFG算法的滤波过程分为：(1) 标识噪声点；(2) 自适应选择滤波窗口；(3) 修复噪声点。

1  标识噪声点

经典的MF算法采用大小固定的滤波窗口对图像I进行滤波，该方法在滤波的同时亦对I中的非噪声点进行相同处理，引入其他噪声，使图像的细节信息受到损失而变得模糊；在强脉冲噪声干扰的情况下，一些噪声点还会聚集成较大的块状区域，此时，MF算法的滤波模型将不再适用。

根据以上分析，SAFG算法采取只对噪声点处理的思路，这样不仅能够降低计算量，而且不会引入其他噪声，为此需要先对噪声点进行标识。脉冲噪声实际上由随机白强度和随机黑强度产生，表现为数值很大或很小的像素点。若图像I的大小为M×N，M，N∈Z⁺，将其抽象为1幅无向图G={V，E}(其中V，E分别对应图G的结点集和边集)，采用8连接的图拓扑结构，用I_ij指代结点v_ij处的特征向量，此处为像素。， ，。因为噪声点的像素非常接近于I_max和I_min，因此，设置阈值T=(I_max-I_min)·σ，σ取经验值0＜σ≤0.05，式(1)从全局角度将图G的结点划分为噪声点集A和非噪声点集，满足，，集合A中包含的结点v_ij即为标识出的噪声点。

   (1)

2  自适应选择滤波窗口

2.1  置信滤波窗口

，需要选择窗口w_ij对v_ij进行滤波，其中且。令集合且为w_ij的置信集，若B_ij的元素个数为n，则；在w_ij中定义B_ij内结点v_pq的权重函数w_pq为

           (2)

式(2)起到归一化的作用，确保w_pq分布在区间上；而β＞0是一个可调节参数，用来调整w_pq的值在范围内的相对差异度。定义w_ij的置信度C_ij为

               (3)

改写式(2)为，将该式抽象为函数y=clnx，其中c＜0，0＜x≤1。因为lnx单调递增，所以，与等价；而，所以，y=clnx单调递减，可得，即

        (4)

式(4)中C_ij实际上反映w_ij中非噪声点v_pq间像素值I_pq的差异程度，客观地衡量用w_ij中非噪声点恢复I_ij的可靠性；对于不同的w_ij，令w_ij(k)代表v_ij的第k级滤波窗口，B_ij(k)为w_ij(k)的置信集，C_ij(k)代表w_ij(k)的置信度。通过比较不同w_ij(k)的C_ij(k)选择出的w_ij(k)叫置信滤波窗口，在不考虑结点空间位置的条件下，C_ij(k)值越大，表明用w_ij(k)恢复I_ij的准确度越高。

2.2  扩展滤波窗口

令N₈(m)代表结点m的8邻域集，，Q(k)指代w_ij(k)的边缘结点集，且，则w_ij可按照扩展算法1从w_ij(k)扩展为w_ij(k+1)；扩展的两级滤波窗口形式如图1所示。

算法1  滤波窗口的扩展。

(1) 若集合，，k=k+1，更新Q(k)；否则转至步骤2。

(2) 取，查找N₈(m)，若且，；；跳至步骤(1)。

图1  结点v_ij的两级扩展窗口

Fig. 1  Two levels of expansion window for v_ij node

3  修复噪声点

SAFG算法本质上靠的近邻域中所有非噪声点对I_ij进行修复，而近邻域是由w_ij(k)体现的，比较不同w_ij(k)的C_ij(k)仅从像素值的差异度上说明选择w_ij(k)的合理性，并未考虑结点间的相对位置信息。若B_ij(k)中的结点相对于v_ij的欧氏距离过大，则亦会使w_ij(k)恢复的可靠性下降。所以，SAFG算法设置，即w_ij(k)最多可扩展为T_w级滤波窗口。w_ij(k)恢复时仍然按照标准的中值滤波方法，用f_Median表示中值滤波算子，假设w_ij(k)中参与滤波的B_ij中结点个数为n，则

(5)

考虑到k≤T_w时，若B_ij(k)全为，即出现噪声点数超过的“超级块”，此时w_ij(k)无法对v_ij滤波，因此，本文提出的SAFG算法在滤波时分两步执行：(1) 选择合适的w_ij(k)对进行滤波，将无法处理的v_ij保存到集合D中；(2) 若D不为，将D设为A并更新，寻找第1个存在非噪声点的w_ij作为v_ij的滤波窗口即可，流程如下所示。

算法2  SAFG算法。

(1) 标识噪声点。将原始图像I映射为图G=(V，E)，由公式(1)得到A和。

(2) 选择置信滤波窗口。

步骤1： ，赋初值k=1，，令。

步骤2：计算w_ij(k)的B_ij(k)，若B_ij(k)为，转至步骤3；否则，转至步骤4。

步骤3：由算法1的方法将w_ij(k)扩展为w_ij(k+1)，k=k+1，转至步骤2。

步骤4：若，扩展w_ij(k)为w_ij(k+1)，转至步骤5；否则，。

步骤5：由式(2)和(3)算出C_ij(k)和C_ij(k+1)，若，则将w_ij(k)作为置信滤波窗口，转至步骤7；否则，k=k+1，转至步骤6。

步骤6：若，扩展w_ij(k)为w_ij(k+1)，转至步骤5；否则，将w_ij(k-1)作为置信滤波窗口，转至步骤7。

(3) 噪声点修复。

步骤7：采用式(5)对v_ij进行滤波。

步骤8：重复步骤(1)至(7)直到对所有进行处理。

步骤9：若D为，算法结束；否则，跳至步骤10。

步骤10：将A=D，不断扩展w_ij(k)，满足，直到，将w_ij(k)作为置信滤波窗口，采用式(5)对v_ij进行滤波，直到处理完A中所有噪声点，算法结束。

4  实验结果及分析

实验环境为：操作系统Windows XP SP3，1.8 GHzCPU，2 GB内存，采用Matlab编程语言对本文SAFG算法进行测试，SAFG算法中式(1)在固定脉冲噪声密度的条件下伴随δ变化对噪声点的标识精度见表1~3。为了简单仅测试灰度图像，且添加的脉冲噪声密度均为0.8。表1~3中：R_TP为检测率；R_FP为虚警率，R_ACC为精确度^[11]。从表1~3可知：δ在0.05的范围内虚警率较低，能够达到较高的精度。因此，采用SAFG算法时，取σ为0.03，而β取100，T_w取4(这2个参数值根据经验选取，大量实验表明这2个参数值对很多图像均能取得良好的滤波效果，具有较强的鲁棒性，一般不用调整)，本文用信噪比R_SN^[11-12]、均方根误差E_RMS^[13]、平均结构相似度I_MSSIM^[14]这3种不同的客观评价指标，分别比较SAFG算法、MF算法和维纳滤波算法对几幅经典灰度图像的滤波^[15]性能，其中MF算法采用3×3和5×5这2种滤波窗口；维纳滤波采用3×3的滤波窗口，所有灰度图像添加密度为[0，0.8]之间的脉冲噪声，且。

表1  Baboon噪声点标识精度(512×512)

Table 1  Identify accuracy for noise points of Baboon

表2  Lena噪声点标识精度(512×512)

Table 2  Identify accuracy for noise points of Lena

表3  Fruits噪声点标识精度(512×512)

Table 3  Identify accuracy for noise points of Fruits

对于Lena图像，噪声图像的信噪比R_SN变化范围为[3.989 0，24.040 4]，SAFG算法滤波后R_SN变化范围为[11.551 2，34.357 7]，E_RMSE的变化范围为[0.305 8，24.040 2]，I_MSSIM的变化范围为[0.929 1，0.999 8]；3×3窗口的MF算法滤波后R_SN变化范围为[5.104 0，14.885 0]，E_RMSE的变化范围为[2.877 5，8.873 0]，I_MSSIM的变化范围为[0.057 5，0.987 3]；5×5窗口的MF算法滤波后R_SN变化范围为[6.191 5，12.191 1]，E_RMSE的变化范围为[3.852 3，7.852 3]，I_MSSIM的变化范围为[0.107 2，0.946 0]；3×3窗口的维纳算法滤波后R_SN变化范围为[3.849 3，14.611 3]，E_RMSE的变化范围为[2.969 7，10.251 9]，I_MSSIM的变化范围为[0.100 9， 0.858 8]，曲线比较结果如图2(a)~(c)所示。

对于Baboon图像，噪声图像的R_SN变化范围为[3.949 7，23.976 7]，SAFG算法滤波后R_SN变化范围为[6.741 9，27.386 6]，E_RMSE的变化范围为[0.681 8，7.343 8]，I_MSSIM的变化范围为[0.744 8，0.999 1]；3×3窗口的MF算法滤波后R_SN变化范围为[4.102 4，7.418 9]，E_RMSE的变化范围为[6.793 1，9.951 6]，I_MSSIM的变化范围为[0.059 9，0.916 3]；5×5窗口的MF算法滤波后R_SN变化范围为[4.385 7，6.234 6]，E_RMSE的变化范围为[7.785 5，9.632 3]，I_MSSIM的变化范围为[0.095 1，0.734 1]；3×3窗口的维纳算法滤波后R_SN变化范围为[3.472 7，6.484 9]，E_RMSE的变化范围为[7.564 3，10.699 9]，I_MSSIM的变化范围为[0.153 4，0.813 4]，曲线比较结果如图2(d)~(f)所示。

对于Fruits图像，噪声图像的R_SN变化范围为[3.969 8，23.955 57]，SAFG算法滤波后R_SN变化范围为[12.109 3，34.479 2]，E_RMSE的变化范围为[0.292 9，3.847 9]，I_MSSIM的变化范围为[0.906 5，0.995 6]；3×3窗口的MF算法滤波后R_SN变化范围为[5.122 5，15.479 1]，E_RMSE的变化范围为[2.610 6，8.601 4]，I_MSSIM的变化范围为[0.028 9，0.978 8]；5×5窗口的MF算法滤波后R_SN变化范围为[6.188 4，11.996 9]，E_RMSE的变化范围为[3.898，7.608]，I_MSSIM的变化范围为[0.064 6，0.899 3]；3×3窗口的维纳算法滤波后SNR变化范围为[7.062 1，12.821 5]，E_RMSE的变化范围为[3.545 0，6.880 0]，I_MSSIM的变化范围为[0.143 0，0.842 8]，曲线比较结果如图2(g)~(i)所示。

从图2可见：(1) 对于低密度的脉冲噪声，MF算法的滤波性能要普遍好于维纳滤波算法，且随着噪声密度的增强两种算法的滤波性能趋于一致；(2) 当脉冲噪声的密度较低时，MF算法采用3×3的窗口滤波性能要好于5×5的窗口，当脉冲噪声的密度较高时，MF算法采用5×5的窗口滤波性能要好于3×3的窗口，说明对于强脉冲噪声的滤除，适当扩展滤波窗口确实能够提高算法的性能；(3) SAFG算法的滤波性能始终优于MF算法和维纳滤波算法，尤其在高密度脉冲噪声的条件仍能保持较高的信噪比，获得良好的滤波效果。

MF算法和SAFG算法在强脉冲噪声的条件下，对Lena，Baboon，Fruits及彩色图像Barbara的实际滤波效果如图3所示，其中图3(a)，(c)，(e)和(g)所示为原始图像；图3(b)，(d)和(f)所示为添加80%的脉冲噪声后SAFG算法的实际滤波效果图，图3(h)所示为添加90%的脉冲噪声后SAFG算法的实际滤波效效果图。从图3可见：SAFG算法滤波后能很好地保留原图的细节特征。为从客观上进行定量比较，采用式(6)的l₂范数^[11]来衡量滤波前后图像的清晰度变化，其中代表原始图像，为滤波后的图像，M，N和Z分别代表图像的维数。式(6)的结果越小，说明滤波前后图像之间差异越少，图像越清晰；反之，图像越模糊。表4所示为图像清晰度比较结果。从表4可知SAFG算法对脉冲噪声的滤除效果确实强于经典的MF算法，使恢复的图像更加清晰，在滤波效果和图像清晰度间取得较好的平衡。此外，还需注意的是：SAFG算法对彩色RGB图像处理时，先分别对每层图像面板进行滤波处理，后将滤波结果叠加生成最终结果，对较大的彩色kidman图像(711×1 024)添加密度为0.9的脉冲噪声，SAFG算法处理的流程及实际效果如图4所示。

图2  滤波质量比较

Fig. 2  Comparison of filter quality

图3  实际滤波效果比较

Fig. 3  Comparison of actual filter effect

 (6)

图4  彩色图像处理流程

Fig. 4  Flow of color image processing

表4  图像清晰度比较

Table 4  Comparison of image clarity

5  结论

(1) 针对脉冲噪声的滤除提出一种SAFG算法，该算法以图论为基础，能充分获取图像的像素及拓扑结构信息，且只有σ，β和T_w这3个简单参数需要设置，尤其适用于高密度的强脉冲噪声滤除，SAFG算法本质上仍属于MF算法的改进型，但滤波性能比经典的MF算法和维纳滤波算法都要强很多。究其原因在于以下3点：一是滤波窗口的大小可自动根据图像局部信息进行调节；二是为了应对噪声块过大的情况提出2步滤波策略，需要注意的是第1步滤波时所恢复的噪声点可靠性已经下降，所以，在参与第2步滤波时只考虑离噪声点最近且存在非噪声点的w_ij进行滤波。

(2) SAFG算法仍存在一些不足之处，主要体现在：1) 全局标识噪声点时参数σ只是凭经验选取，很难准确标识出所有噪声点；2) 局部滤波时置信窗口的选取比较费时，其运算量随脉冲噪声密度的增强而不断加大。

参考文献：

[1] Singh C, Chauhan R P S, Singh D. Comparative study of image enhancement using median and high pass filtering methods[J]. Journal of Information and Operations Management, 2012, 3(1): 96-98.

[2] WANG Gaihua, LI Dehua, PAN Weimin, et al. Modified switching median filter for impulse noise removal[J]. IEEE Signal Processing, 2010, 90(2): 3213-3218.

[3] ZHANG Shufang, ZHANG Tao, QU Guangcai, et al. A new adaptive weighted median filter algorithm[J]. Elsevier Energy Procedia, 2011, 13(5): 2987-2993.

[4] Kal K, Toh V, Ashidi N. Noise adaptive fuzzy switching median filter for salt-and-pepper noise reduction[J]. IEEE Signal Processing Letters, 2010, 17(3): 281-284.

[5] Schulte S, Morillas S, Gregori V, et al. A new fuzzy color correlated impulse noise reduction method[J]. IEEE transactions on image processing, 2007, 16(10): 2565-2575.

[6] Diestel H. Graph theory[M]. 4th Ed. German: Springer-Verlag, 2010: 451-471.

[7] Couprie C, Grady L. Power watersheds: A new image segmentation framework extending graph cuts, random walker and optimal spanning forest[C]//Proceedings of the 12th International Conference on Computer Vision(ICCV). Kyoyo: IEEE Press, 2009: 731-738.

[8] 李佐勇, 刘传才. 融合视觉感知和等周理论的图像阈值分割[J]. 中国图像图形学报, 2011, 16(3): 370-376.

LI Zuoyong, LIU Chuanzai. Image thresholding based on human visual perception and isoperimetric theory[J]. Joural of Image and Graphics, 2011, 16(3): 370-376.

[9] 孔丁科, 汪国昭. 基于局部图划分多相活动轮廓图像分割模型[J]. 电子与信息学报, 2010, 32(9): 2127-2132.

KONG Dingke, WANG Guozhao. Localized graph-cuts based multiphase active contour model for image segmentation[J]. Journal of Electronics & Information Technology, 2010, 32(9): 2127-2132.

[10] WU Yongcheng, YANG Xin, XU Min. Graph cuts medical image segmentation algorithm based on k-means clustering[J]. Computer Engineering, 2011, 37(5): 232-234.

[11] Frank Y. Image processing and pattern recognition: fundamentals and techniques[M]. Hoboken, New Jersey, USA: John Wiley, 2010: 1-350.

[12] Fawcett T. An introduction to ROC analysis[J]. Pattern Recognition Letters, 2006, 27: 861-874.

[13] Jyothi V, Rajash B, Krishna R. Image fusion using evolutionary algorithm(GA)[J]. International Journal of Computer Application in Technology, 2011, 2(2): 322-326.

[14] Wang Z, Bovik A, Sheikh H, et al. Image quality assessment: From error visibility to structural similarity[J]. IEEE Transaction Image Process, 2004, 13(4): 600-612.

[15] Venkateswara R, Satya P, Mohan R. Implementation of impulse noise reduction method to color images using fuzzy logic[J]. Global Journal of Computer Science and Technology, 2011, 11(22): 70-75.

(编辑  邓履翔)

收稿日期：2012-08-17；修回日期：2012-10-08

基金项目：国家自然科学基金资助项目(61175029)

通信作者：汪云飞(1985-)，男，陕西西安人，博士研究生，从事图像滤波和分割研究；电话：13629286615；E-mail：wyfpost@163.com