一种用于中值滤波的改进均值划分算法①

刘海峰, 张 超, 罗 江, 林福良



一种用于中值滤波的改进均值划分算法①

刘海峰, 张 超, 罗 江, 林福良

(北京控制与电子技术研究所信息系统工程重点实验室, 北京 100038)

图像滤波是很多图像处理算法在图像预处理阶段采用的处理措施, 而中值滤波不仅能够有效地去除图像中的噪声, 而且可以保持图像的边缘细节, 从而成为首选的图像滤波方法. 由于中值滤波需要使用排序操作, 其计算时间复杂度较高, 而且在滤波窗口较大时, 导致图像滤波耗费较长的时间, 不能满足海量、高分辨率图像实时滤波处理的需求. 在研究中值滤波基础上, 提出一种改进的基于均值划分的快速中值滤波算法, 实验表明, 该算法可以有效地降低图像中值滤波的时间消耗, 特别是在大尺度图像中, 当滤波窗口较大时, 能够显著降低图像滤波时间, 同时, 能够与传统中值滤波保持一致的效果, 进一步增强了大尺度图像实时处理能力.

图像滤波; 中值滤波; 均值划分; 滤波时间; 滤波效果

由于受到环境、采集设备等各种因素的影响, 传感器获取的图像往往受到噪声的干扰, 使得图像存在质量退化现象. 因此, 在绝大多数图像处理过程中, 图像预处理[1]通常是首要的操作, 如图像滤波、图像校正、灰度变换等, 其中图像滤波是最重要的图像预处理操作, 包括高斯滤波[2]、中值滤波[3]、双边滤波[4]、均值滤波[5]等.

中值滤波作为一种非线性平滑滤波方法, 不仅能够有效的消除图像中的随机噪声, 而且不会使图像边缘变得模糊, 能够有效保护原始图像信号, 得到了广泛的应用. 然而, 传统中值滤波需要对滤波窗口内的所有图像数据进行排序操作, 排序操作需要大量的数据比较和移动, 使得中值滤波花费较长的时间, 不能满足海量、大尺度图像实时处理的要求.

为提高中值滤波的速度, 出现了很多改进算法. 例如, 针对灰度图像, 文献[6]提出了一种基于查表法的快速中值滤波方法, 然而, 该方法只适用于8位灰度图像. 文献[7]则充分利用滤波窗口之间的相关性, 提出了一种快速中值滤波算法, 该算法充分利用滑动窗口的先验信息, 考虑移入像素值和移出像素值的位置关系, 达到像素数据的快速插入与删除, 然而该方法不适用于序列相关性差的场合, 如前后两次中值滤波的窗口不存在大量的重叠区域以及只对符合条件的区域进行滤波[8]. 文献[9]提出了一种均值加速中值滤波算法, 虽然该算法可以有效提升滤波速度, 但是其滤波结果与传统中值滤波结果相差较大, 本文受该算法启发, 提出了改进措施, 在提升滤波速度的同时, 使得滤波结果与传统中值滤波结果保持一致.

1　传统中值滤波算法

传统的中值滤波算法就是从一个数据集合中找出其中值. 对于二维图像信号, 以窗口中心为原点的中值滤波的定义为:

图1 二维图像中值滤波窗口示意图

二维图像的中值滤波算法对窗口的形状没有限制, 常用的窗口形状[10]包括: 矩形、十字形、圆形等, 如图2所示为窗口大小为5*5的窗口形状:

(a) 矩形(b) 十字形(c) 圆形

中值滤波算法最核心的操作就是排序, 其主要使用快速排序算法, 而快速排序的平均时间复杂度为, 此处为待排序的数据数目. 快速排序需要进行大量的数据比较和移动操作, 当数据量较大时会耗费较多的时间, 从而使得中值滤波算法不能满足实时性要求.

2　改进的均值划分快速中值滤波算法

2.1 算法原理

传统的中值滤波算法需要对所有数据进行排序, 对于大尺度图像, 当滤波窗口较大时, 整个中值滤波需要耗费较长时间. 本文算法借鉴文献[9]的“均值加速”思想, 提出改进的均值划分法, 减少参与排序的数据量, 从而达到降低中值滤波时间的目的.

图3给出了基于文献[9]提出的均值加速中值滤波算法的一个分析示例.

图3 文献[9]滤波算法示例, 终止条件为当前集合元素数目大于N/2. 可以看出, 提取的中值存在错误

图4 5*5的滤波窗口及滤波中心

从图3可以看出, 其不能正确找出滤波窗口中真正的中值, 其原因就在于没有设计好对排序集合选择的策略, 导致选择了一个不合适的集合进行排序, 从而得到错误的滤波中值.

本文提出的改进的基于均值划分的快速中值滤波算法的基本原理与均值加速法相似, 即: 对于滤波窗口覆盖的图像像素集合, 首先计算该集合中所有像素值的均值, 然后以均值将集合划分为大于等于均值的像素集合以及小于均值的像素集合, 分别记录这两类集合的像素数目, 接着, 只对像素数目超过滤波窗口总像素数目一半的集合重复以上操作, 并分别累加这两类集合元素的数目, 直到某次分解的两类集合元素数目都小于滤波窗口总像素数目的一半, 最后, 只对两类集合累加数目超过滤波窗口总像素数目一半的集合进行排序.

相比较均值加速算法, 本文算法在划分过程中增加了统计每类集合像素数目的策略, 从而解决了不能找到真正滤波中值的问题.

图5给出了图3中的示例采用本文提出的改进的基于均值划分的快速中值滤波算法得到的滤波过程:

从图5中可以看出, 采用本文设计的选择划分排序集合的策略后, 能够正确的选择排序集合, 在减少参与排序数据量的同时, 减少了排序划分的时间, 而且取得与传统中值滤波相同的效果.

2.2 算法原理及流程

本文提出改进的基于均值划分的快速中值滤波算法, 通过引入排序集合选择策略, 可以正确选择对最后一次划分得到的排序集合, 该策略的核心是: 在每次划分后都重新统计大于等于均值的集合的元素数目, 以及小于均值的集合的元素数目, 当某次划分得到的两个集合的元素数目都小于滤波窗口总像素数目的一半时, 选择累加元素数目超过滤波窗口总元素数目一半的集合作为最终的排序集合.

图5 本文提出的改进的基于均值划分的快速中值滤波算法的滤波过程, 可以得到正确的滤波中值

图6给出了本文提出的改进的基于均值划分的中值滤波算法的流程图, 其基本步骤如下:

图6 本文提出的改进的基于均值划分的中值滤波算法流程图, 增加了集合选择策略

上述步骤中的第7)和第8)体现了集合选择策略, 该策略是根据集合和集合累计元素数量与滤波窗口像素数目一半的关系进行集合选择的, 同时, 不同的集合选择, 采用的排序规则也不同, 即: 当集合的累计元素数目超过滤波窗口图像像素数目的一半时, 则对集合进行排序, 排序规则为由大到小排序; 而当集合的累计元素数目超过滤波窗口图像像素数目的一半时, 则对集合进行排序, 而采用的排序规则为由小到大排序.

考虑到在均值划分过程中需要对数据进行移动, 如果移动的数据过多, 反而增加时间消耗, 为此, 本文将终止条件限制为原始滤波窗口的一半, 以便在移动数据量最小与排序量最小之间达到平衡.

图8给出了采用本文提出的改进的基于均值划分的快速中值滤波算法的另一个时间例子, 滤波窗口及滤波中心如图7所示. 通过人工计算得出该实际例子的中值为76, 由图8的滤波结果可以看出, 利用本文提出的滤波算法可以正确获取滤波窗口的中值.

图7 滤波窗口及滤波中心

此外, 由图5与图8可以看出, 对于选择大于等于均值的集合(即)进行排序时采用的是由大到小的排序方式; 而对于选择小于均值的集合(即)进行排序时采用的是由小到大的排序方式, 目的是保持提取中值位置公式的一致性.

3　实验与分析

为验证本文提出的改进的基于均值划分的快速中值滤波算法的有效性, 将本文算法用于大尺度图像的中值滤波处理, 并与传统的中值滤波算法进行对比, 比较的指标为中值滤波耗费的时间. 同时, 与文献[9]提出的均值加速中值滤波算法进行比较, 由于这两种方法的计算时间复杂度相同, 因此, 此处采取的指标为中值滤波的效果, 即检验两种算法是否能够保持传统中值滤波算法的效果.

图8 本文提出的改进的基于均值划分的快速中值滤波算法的另一个例子, 可以得到正确的中值

实验采用的计算机为联想台式机, CPU主频3.2GHz, 内存4GB, 分别采用分辨率为256*256、512*512、1024*1024三种图像进行滤波实验, 通过改变滤波窗口大小来观察滤波时间的变化, 滤波窗口大小范围为3*3到25*25.

3.1 与传统中值滤波时间比较

图9到图11分别给出了在256*256、512*512、1024*1024三种分辨率图像上进行中值滤波的时间耗费对比曲线图, 在计算时, 每取一种滤波窗口, 连续运行100次取平均滤波时间.

可以看出, 本文算法在较小的滤波窗口时, 并不比传统中值滤波算法节省时间, 相反, 需要的滤波时间可能更多, 这主要是因为, 本文提出的改进的基于均值划分的中值滤波算法需要对滤波窗口内的像素进行划分, 该过程涉及到较多的数据比较和移动, 在滤波窗口较小时, 虽然最后一次快速排序的数据量大量减少, 但是加上前期数据划分产生的数据比较和移动开销可能会超过对整个滤波窗口的快速排序的时间开销, 因此, 导致整个图像的耗时较长.

图9 本文算法与传统中值滤波算法在分辨率为256*256图像上的对比

图10 本文算法与传统中值滤波算法在分辨率为512*512图像上的对比

图11 本文算法与传统中值滤波算法在分辨率为1024*1024图像上的对比

然而, 随着滤波窗口的增大, 本文提出的算法优势越来越明显, 特别是当滤波窗口大于9*9时, 本文算法耗时要少于传统中值滤波算法, 而且随着滤波窗口的增大, 节省的滤波时间越来越多, 而这种优势, 对于大尺度图像滤波更明显.

由此可以得出, 本文提出的算法更适用于较大的滤波窗口, 而且, 对于图像分辨率越大的图像, 采用本文提出算法的优势越明显.

3.2 与文献[9]滤波效果比较

本文算法还与文献[9]提出的改进中值滤波算法进行了滤波效果对比, 图12和图13给出了三种中值滤波算法的效果图, 分辨率分别为512*512的灰度图像和256*256的彩色图像, 滤波窗口大小都设定为11*11(注: 滤波窗口大小对比较滤波效果无影响).

从图12中可以看出, 本文算法的滤波效果能够保持与传统中值滤波算法一致, 而文献[9]提出的改进中值滤波算法由于提取滤波窗口中值时产生了错误, 导致图像滤波结果出现了畸变, 在中值滤波后的图像中出现了大片的斑点, 已经导致图像内容的改变, 造成滤波图像失真.

(a) 传统中值滤波效果

(b) 本文算法滤波效果

(c) 文献[9]中值滤波效果

由图13同样可以看出, 本文算法能够保持与传统中值滤波算法相同的效果, 而文献[9]提出的改进中值滤波同样出现了斑点, 造成彩色图像颜色发生变化, 从而导致彩色图像发生畸变.

(a) 传统中值滤波效果

(b) 本文算法滤波效果

(c) 文献[9]中值滤波效果

为了进一步进行对比, 分别计算本文提出的算法和文献[9]提出的算法与传统中值滤波算法的结果进行做差比较, 即: 将两幅图像中对应的位置做图像减法[11], 取绝对误差, 并累加整幅图像的所有绝对误差以及计算整幅图像平均绝对误差(也可以采用均方误差[12]), 比较结果如表1所示.

表1 本文算法和文献[9]及传统中值滤波效果计算对比结果(单位: 像素值)

通过表1可以看出, 本文提出的中值滤波算法与传统中值滤波算法的结果图像进行做差计算得到的绝对误差和与平均绝对误差都为0, 这说明了, 本文提出的滤波算法能够保持与传统中值滤波算法相同的滤波结果. 而文献[9]中的滤波算法与传统滤波结果的比较不管是绝对误差和, 还是平均绝对误差都不为零, 这说明了, 文献[9]中的滤波算法不能保持与传统中值滤波算法相同的滤波效果, 也即改变了中值滤波的本质功能.

综上所述, 可以得出, 本文提出的改进的基于均值划分的中值滤波算法, 不仅能够在滤波时间上要快于传统的中值滤波算法, 而且, 在滤波效果上与传统中值滤波算法保持了一致性, 同时, 本文算法也能够适用于彩色图像的中值滤波, 由算法原理可知, 本文算法既适用于8位位深的图像, 也适用于16位甚至更高位深的图像. 此外, 滤波效果要优于文献[9]提出的改进中值滤波算法. 通过与传统中值滤波算法的比较可以得出, 本文算法具有较强的实用性, 特别是在较大滤波窗口条件下对大尺度图像滤波时, 时间效能更加明显, 进一步提升了海量、高分辨率图像的实时处理能力.

4　结语

本文在研究传统中值滤波以及其他的中值滤波算法的基础上, 通过分析现有改进中值滤波算法存在的缺点, 引入排序集合选择策略, 进而提出了一种用于中值滤波的改进均值划分算法, 该算法不仅能够加快大尺度图像中值滤波的滤波速度, 而且避免了基于均值加速算法的不足, 能够保持与传统中值滤波算法具有相同的滤波效果, 对于海量、大尺度图像的实时处理具有重要应用价值. 此外, 本文提出的中值滤波算法不仅适用于灰度图像, 而且也适用于彩色图像; 同时, 本文算法也适用于其他需要中值滤波的应用场景, 如雷达信号.

1 王红君,施楠,赵辉,岳有军.改进中值滤波方法的图像预处理技术.计算机系统应用,2015,24(5):237–240.

2 王怀野,张科,李言俊.一种自适应各项异性高斯滤波方法. 计算机工程与应用,2004,(10):18–19.

3 Hanji G, Latte MV. Novel median filter for impluse noise suppression from digital images. International Journal of Computer Application, 2014, 106(8): 18–21.

4 杨学志,徐勇,方静,卢洁,左美霞.结合区域分割和双边滤波的图像去噪新算法.中国图象图形学报,2012,17(1): 40–48.

5 陈乃金,周鸣争,潘冬冬.一种新的维纳滤波图像去高速噪声算法.计算机系统应用,2010,19(3):111–114.

6 Huang TS. A fast two-dimensional median filtering algorithm. IEEE Trans. on ASSP, 1979, 27(1): 13–18.

7 朱冰莲,潘哲明,李单单.一种中值滤波的快速算法.信号处理,2008,24(4):684–686.

8 顾茂松,杨小冈,缪栋.一种基于局部差别的基准图去噪方法. 弹箭与制导学报,2007,1:280–182.

9 张丽,陈志强,高文焕,康克军.均值加速的快速中值滤波算法.清华大学学报(自然科学版),2004,44(9):1157–1159.

10 曹治华,宋斌恒.多种形状窗口下的快速中值滤波算法.计算机应用研究,2006,3:85–88.

11 李继良,于策,孙济洲,商朝晖,陈锦言,曹玮,张旭明.基于OpenMP的并行图像相减算法实现与分析.天文研究与技术,2011,8(2):146–152.

12 Shukla HS, Kumar N, Tripathi RP. Median filter based wavelet transform for multilevel noise. International Journal of Computer Applications, 2014, 107(14): 11–14.

Improved Mean Division Algorithm for Median Filtering

LIU Hai-Feng, ZHANG Chao, LUO Jiang, LIN Fu-Liang

(Science and Technology on Information Systems Engineering Laboratory, Beijing Institute of Control and Electronic Technology, Beijing 100038, China)

Image filter is the method for image pre-processing in many image processing algorithms. Since, median filter not only can smooth image noise, but also can hold the image edge, it becomes the most used method in image filter. Median filter needs sorting operation, its time complex is very high. When filter window becomes larger, median filter will need more time, it cannot be used in large image real-time processing. Based on the median filter research, a faster median filter algorithm which is based median division is proposed. The proposed algorithm can reduce filter time effectively, especially in large scale image, when filter window is large, it becomes more remarkable. Compared with the traditional median filter algorithm, the proposed algorithm filter result can hold the preference as same as the traditional median filter algorithm, and it can be used on gray and color image. The experiment shows that the proposed median filter algorithm not only speeds up image filter speed, but also improves the real-time of image processing.

image filter; median filter; mean division; filter time; filter result

2016-06-20;

2016-08-11

[10.15888/j.cnki.csa.005673]