一种快速并行中值滤波算法的实现.doc

文章编号：1007-757X(2011)08-0050-03 一种快速并行中值滤波算法的实现 辛月兰 摘 要：介针对传统中值滤波算法计算量大、耗时较长的缺点提出了一种快速并行中值滤波算法。对于 3×3 滑动窗口，窗 口的 9 个数据是并行传给计算比较模块的，第二级的计算也是并行进行的。新算法有效减少了重复比较操作的执行，同时也 大幅减少了比较次数。对于 3×3 滑动窗口，新算法的比较次数为 13 次，相对于传统中值滤波的 30 次，比较次数少了 2 倍 多。比较次数的减少，意味着算法复杂度的降低和图像滤波处理速度的提高。并且通过仿真实验可知，对于椒盐噪声的滤除， 算法能够达到与中值滤波同样的视觉处理效果。 关键词：并行处理；中值滤波；预处理；快速算法；图像处理 中图分类号：0246 文献标志码：A 0 引言 十分适用于在实时处理器上做并行处理。 实际图像在采集、形成、传输过程中，不可避免会受到 噪声干扰，严重影响视觉效果，对后续的边缘检测、图像分 割、特征提取、模式识别等产生影响。因此，去噪是一项非 常重要的预处理步骤 [1] 。 中值滤波是一种常用的抑制噪 声的非线性方法, 它可以克服线性滤波如最小均方滤波和 均值滤波给图像边缘带来的模糊, 从而获得较为满意的复 原效果; 它能较好地保护边界, 对于消除图像的椒盐噪声非 常有效, 但有时会失掉图像中的细线和小块的目标区域[2 -3]。 理想的滤波算法应该只对噪声点进行处理, 而保留信 号灰度值不变。Sun and Neuvo[4]和 Florencio and Schafer[5] 分别提出了开关中值滤波的方法, 更好地保留了图像细节, 但噪声点判断方法是通过假定噪声水平上的硬阈值方法, 使得其推广能力受到了限制。H. L. Eng 和 K. K. Ma[6]提出 噪声自适应软开关中值滤波( NASM) 算法, 它是一种软阈 值的判断方法, 这种算法自适应性虽然比其它的开关中值 滤波算法强, 但其计算时间随噪声密度的增大而增加, 如当 噪声密度为 70%时, NASM 算法所用的时间大约为中值滤 波算法的 17 倍, 因此不能满足实时图像处理。 常规中值滤波算法一般都采用排序的思想[7-9]，但是 这种算法存在循环迭代结构和计算次数不确定性的缺陷，同 时需要处理的数据量大。因此本文针对传统中值滤波算法计 算量大、耗时较长的缺点提出了一种快速并行中值滤波算 法。与传统算法相比，此算法通过巧妙设计，避免了大量的 重复比较操作，比较次数较传统算法少了 2 倍多，且该算法 ————————————— 基金项目：国家自然科学基金资助项目[项目批准号。 1 传统的中值滤波 中值滤波是由 Tukey 首先提出的一种典型的非线性滤 波技术。它在一定的条件下可以克服线性滤波器如最小均方 滤波、均值滤波等带来的图像细节模糊，而且对滤除脉冲干 扰及图像扫描噪声非常有效。由于在实际运算过程中不需要 图像的统计特征，因此使用方便。 传统的中值滤波一般采用含有奇数个点的滑动窗口， 用窗口中各点灰度值的中值来代替指定点的灰度值。对于奇 数个元素，中值是指按大小排序后中间的数值；对于偶数个 元素，中值是指排序后中间两个元素灰度值的平均值。中值 滤波也是一种典型的低通滤波器，主要用来抑制脉冲噪声， 它能够彻底滤除尖波干扰噪声，同时又具有能够较好地保护 目标图像边缘的特点。 二维中值滤波的定义为： g（x,y）=med{f(x-k,y-i),(k,i∈W)} (1) 其中, med 表示取中值操作,f(x,y)，g(x,y)分别为原始 图像和处理后图像，W 为二维模板。 中值的计算在于对滑动窗口内像素的排序操作。要进 行排序，就必须对序列中的数据像素做比较和交换，数据元 素之间的比较次数是影响排序速度的一个重要因素。传统的 排序串行算法是基于冒泡排序法，若窗口内像素为 m 个， 则每个窗口排序需要做 m(m-2)/2 次像素的比较操作，时间 复杂度为 O（m2）。此外，常规的滤波算法使窗口每移动一 次，就要进行一次排序，这种做法实际上包含了大量重复比 作者简介：辛月兰( 1973- )，女，青海乐都人，青海师范大学物理系，硕士。研究方向：图像处理、模式识别，西宁，810008  较的过程。若一幅图像的大小为 N ? N，则整个计算需要 O （m2N2）时间，从而可以看出,用软件的思路去求滤波窗口 为 m ? n 的中值,要进行 3(n2*m2-1)/8 次比较运算,对于 3×3 滑动窗口,比较运算次数为 30 次;对于 7×7 窗口,运算次数达 到 900 次,当窗口较大时计算量很大，耗费时间较长。 medmed，最小值组中最大值为 minmax，滤波结果的输出像 素值为 wi