一种中值滤波的快速算法

《一种中值滤波的快速算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1999年9月重庆大学学报(自然科学版)Vol.22第22卷第5期JournalofChongqingUniversity(NaturalScienceEdition)Sep.1999文章编号:1000-582x(1999)0520013204X一种中值滤波的快速算法11221靳斌,郭永彩,杨冠玲,何振江,谢利利(11重庆大学光电信息工程学院,重庆400044;21华南师范大学应用物理系,广州510631)摘要:给出了一种中值滤波的快速算法,该算法利用了两次中值滤波的窗口内数据的相关性。在中值滤波过程中,除了第一个中值要用传统排序算法求得,以后的中值都是通过把新进入窗口元

2、素在前一次排好的序列进行对分查找和内插操作求得。为了便于窗口移动,设计了一种数据结构,可以快速用新移入数据覆盖移出数据,大大减小计数量,还给出了窗口按/之0字形路线移动的2维中值滤波方法。关键词:排序;中值滤波;图象处理中图分类号:TP273文献标识码:A在粉尘速度场测量中,粉尘信息被各种随机噪声干扰(如CCD散粒噪声,测试场的热噪声),所以有必要进行局部平滑处理。平均值滤波是一种可以减小随机噪声影响的常用算法,但是也会使粉尘图象的边缘模糊化,为以后处理带来困难。中值滤波是窗口内数据由大到小排列,取序列中间的值作为均值。它即可以克服噪声影响,也保护了原始信号的细节信息,所

3、以中值滤波是粉尘速度场测量中不可或缺的滤波算法。中值滤波的主要运算是对窗口内数据排序。文献[1]提出把相邻两次的中值滤波合并为一次进行,只需一次排序,从而把总的排序次数减少一半。文献[2]是通过对有序列元素的快速查找内插实现中值滤波,速度比文献[1]有所提高。笔者提出的中值滤波算法,是基于前一次排好得到的有序序列,将新进入窗口元素通过设计的一种数据结构来找到新元素在窗口中的起始位置,然后通过对分查找和内插,调整窗口中元素的顺序,找到新元素在窗口中的新位置,使窗口成为有序序列,实现中值滤波,其效率比文献[2]有较大提高。1算法原理及实现如图1,一般的中值滤波是将滤波窗口w(

4、0),w(1),,,w(2N)(N为自然数)输入原始信号,进行排序,找到中值,其比较次数为(M-2N)(2N+1)N1若设M=512,N=10,则比X收稿日期:1998210207基金项目:广东省自然科学基金资助项目(970306);广东省高教厅自然科学重点科研项目资助基金(粤高教科[1997]号)作者简介:靳斌(19692),男,重庆人,重庆大学博士生。从事光电技术及系统领域研究。14重庆大学学报(自然科学版)1999年图1窗口移动示意图较次数为(512-2@10)(2@10+1)10=103320次,另外还有相当多的交换运算,可见计算量较大,上述中值滤波的缺点是:窗口

5、每移动一步,更换一个元素就要重新更换窗口数据,重新排序,浪费较大计算量,要想利用原窗口的有序序列就要能找到新元素应放到窗口有序序列的哪一位置,针对该情况设计的窗口数据结构为:struct{floatElement;unsignedcharSequence;}w[2N+1];unsignedcharMap[2N+1];初始时Map[2N+1]={0,1,2,,,2N}w[i].Sequence是进入窗口的顺序,w[i].Squence=j%(2N+1),j等于原始信号下标,w[i].Element是原始信号的内容,Map是一个映射,将窗口数据顺序映射到窗口数据的下标Map[

6、w[i].Sequence]=i,这样随着窗口沿信号滑动,新原始数据就可以通过下标j,i=map[j%2N+1]找到应存在窗口中的那一元素w[i].同时考虑w是一个有序序列,插入窗口的新元素与其左右元素对比就可以知道它该向窗口的哪一方向调整,因此可在部分窗口上采用对分查[3]找算法,如图2所示。若新元素的窗口中存放的初始位置为Position,经对分查找算法得到新元素的位置为k,当k

7、移一个序号填序,另将新元素存入w(k),由此调整好的新窗口序列的w(N)即为窗口中值,其操作如下。不断移动窗口就可实现对原信号进行中值滤波。图2对分查找算法文献[2]中找进入窗口元素的位置用对分查找算法(序列长2N+1)在平均情况下比较次数为log2(n+1)-1次,而本文采用映射方式。文献[2]找新进入窗口元素的调整后的位置用对分查找算法(序列长2N+1)在平均情况下比较次数为log2(2N+1)+1次;而本文也用对分算法序列长n<2N+1(n为部分窗口的长度,n=1,2,3,,,2N),比较次数log2(2n+1)+1次,