可进化可重构图像滤波器的设计

1、第49卷第6期2010年12月复旦学报(自然科学版)JournalofFudanUniversity(NaturalScience)Vol.49No.6Dec.2010文章编号:04277104(2010)06070907可进化可重构图像滤波器的设计刘少腾,来金梅,陈利光,童家榕,鲍丽春11112(1.复旦大学专用集成电路与系统国家重点实验室,上海201203;2.北京航天飞控中心,北京100094)摘要:设计了一种新型的可重构、可进化图像滤波器.可重构电路采用了一种全新的可配置电路网络结构.该结构将功能运算单元以Benes拓扑结构互联,取代现有的MUX加功能运算单元的结构,使其具有更多条输出

2、路径,更多运算单元参与到了进化中以提高进化效率.在运算单元设计方面,利用FPGA中特有的丰富LUT逻辑资源优势,设计了一种仅通过LUT配置码来控制其功能的P运算单元,节约资源且扩充了运算单元可执行的功能选项.借助于模拟退火遗传算法,通过对可重构电路配置码(基因)的不断改进和优化,该滤波器可以很好地滤除图像中的高斯噪声和椒盐噪声.实验结果表明:经过100万代进化,对于高斯噪声,噪声图像的平均每像素误差Mdpp=32.11,滤波后Mdpp=16.74,滤波质量优于一般高斯滤波器和现有的MUX加功能运算单元的可进化滤波器;对于椒盐噪声,噪声图像Mdpp=6.22,滤波后Mdpp=3.44,有效滤除了

3、噪声.关键词:可进化硬件;图像滤波器;可重构电路;Benes拓扑结构中图分类号:TN402文献标志码:A可进化硬件(evolvablehardware,EHW)1指的是在与外部环境相互作用时,能自主、动态地改变其自身结构和行为的硬件电路.其基本特征是具有自组织、自适应和自修复能力,因而在图像滤波、智能化通信网络、模式识别与人工智能等方面有着广泛的应用前景.作为一种典型的可进化硬件,可进化图像滤波器主要由3部分组成:进化算法、适应度评估、可配置结构阵列3,参见图1.在可进化图像滤波器应用领域,代表性的研究成果包括:L.Sekanina的可进化图像滤波器452和P.N.Kumar6的可进化图像滤波

4、器.L.Sekanina和P.N.Kumar所设计的滤波器中,其共同点在于可配置电路采用了多路选择器(MUX)加运算单元的结构,见图2.其中运算单元由4位基因码控制,用以选择16种已有功能的一种.两人的实验结果从不同的角度说明了这种结构可以用于可进化图像滤波应用.但是这种常见的可配置结构还存在需要改进的地方.首先MUX需要一定的基因码来控制,从而加长了进化基因长度,加重了进化算法的负担,同时MUX所占用的大量硬件资源也不可忽视.其次,总是有运算单元未被选中,这些没被选中的单元消耗了基因码和硬件资源,却没有在进化中充分发挥效率.再次,由收稿日期:20091221基金项目:国家高技术研究发展计划(

5、863计划)(2007AA01Z285)资助项目作者简介:刘少腾(1984),男,硕士研究生;陈利光,男,博士后,通讯联系人,Email:chenlg.710复旦学报(自然科学版)第49卷于这种结构最后1级只有1个输出端口,局限了能够实际参与到进化评估的运算单元的数目.本文从提高进化效率和扩大滤波应用范围2方面着手,提出了一种全新的可配置电路网络(configurablecircuitnetwork,CCN)结构.这种结构将功能运算单元以Benes网络拓扑结构互联,以克服如上所述的MUX及输出端口数目限制所带来的缺陷;同时,结合FPGA中丰富的查找表(LUT)资源,设计了仅通过改变LUT配置码

6、来改变其功能的P型运算单元,这样不但节约了资源,而且扩充了运算单元可执行的功能选项.本文分别用带有高斯噪声图像和带有椒盐噪声的图像来对这种新结构进行评测.与采用L.Sekanina所设计的可重构结构搭建成的滤波器和采用P.N.Kumar所设计的可重构结构搭建成的滤波器,及一般高斯滤波器的滤波结果进行比较,本文所提出的滤波器经过100万代进化,对于高斯噪声,噪声图像的平均每像素误差Mdpp=32.11,其滤波结果为Mdpp=16.74,滤波质量优于以上提到的2种可进化滤波器和一般高斯滤波器;对于椒盐噪声,噪声图像Mdpp=6.22,滤波后图像Mdpp=3.44,有效滤除了噪声.71可重构、可进化

7、图像滤波器结构可进化滤波器3大基本组成和运行流程如图1.根据图1,将本文所设计的可重构、可进化图像滤波器的3个重要组成部分:可配置电路网络、进化算法、适应度评估,分别介绍如下.1.1可配置电路网络(CCN)本文所设计的CCN结构如图3所示,整个网络采用不带反馈的Benes网络拓扑结构.采用这种结构的目的在于,在减少网络所用资源的同时,使网络中的每一个节点都可以找到输出途径,从而参与到进化评估中来.整个网络有16个8bit输入端和16个8bit输出端.根据图像滤波基本原理,采用3 3窗口,每次有9点参与滤波.其中,16个输入端中,前9个分别对应19号像素点,后7个输入端对应像素点中的除4号和9号

8、以外的像素点.整个网络的基本运算单元由E,P2种单元组成.每个E型和P型单元都有2个输入端,标为A和B,以及2个输出端,标为Y和Z.除了整个网络第一列的P型单元的输入端,和最后一列的P型单元输出端Y和Z为8bit之外,其余在网络内部的各个运算单元,其输入和输出都为10bit.这样做的原因是由于虽然参与运算的基本单位是8bit的像素点,范围从0255,但是考虑到进位保留,因而网络内部单元都需要采用10bit的宽度,直到最后输出时才舍弃高2位.对于P型单元,由于P型单元的每个输入端都为10bit,所以每个单元中都包含10个元胞,分别对应于输入端A和B的每一位.其中,每一个元胞又包含了2个3输入查找

9、表(LUT)和一条进位链C.2个3输入查找表(LUT)的3个输入端分别接A,B的相应位和上一级元胞传递过来的进位链,2个LUT的输出端则分别接Y和Z的相应位,进位链C则负责将本元胞产生的进位传递到下一级的元胞.相邻的2个元胞间的进位链C的方向是从较低位传向较高位.考虑到用到进位链的机会不多,为了节约配置码起见,进位链C的功能预设为2种,分别为加法运算的进位和比较运算的进位,由一位配置码负责选择.设计进位链的目的在于,实现A+B和AB,AB等功能时,需有低位到高位的进位参与进来.在P型单元的元胞中,2个输出端Y和Z之间存在反演对称性.比如通过LUT将Y配置为Y=A,则对应的Z的表达式必为Z=B.

10、Y和Z的具体关系是:将Y表达式中的A和B互换就可以得到就得到Z的表达式.这样做的好处是可以节省配置码,只需要配置好输出Y的LUT,然后用同样的配置码,只需交换LUT输入端A和B的位置,就得到Z.同时考虑到反演对称性,Y和Z表达式中的A和B可互换,所以只需要7位配置码就可以配置这2个LUT.如图3所示,考虑到参与滤波运算的最小单位是像素,为了不破坏像素的整体性,每个P单元的10个元胞都必须配置成相同的.综上,加上进位链所需的一位配置码,配置每个P单元共消耗8位配置码.每个P单元可能实现的功能有27-1种,极大地丰富了运算单元可执行的运算种类.对于E型运算单元,其运算功能主要以移位为主.每个E单元

11、的2个输入A、B和2个输出端Y、Z都为10bit.具体而言,每个E单元可以执行16种功能运算的一种,根据4位配置码来选择实现的运算功能.E单元能够实现的运算与其相对应的配置码如表1所示.比如,当需要某一个E单元实现输入A右移8第6期刘少腾等:可进化可重构图像滤波器的设计7112位,B右移2位的运算,则将它的配置码设为0001.另外,从表1可以看到,E单元输出Z端和Y端同样满足反演对称性.图3可配置电路网络(CCN)Fig.3Thestructureofreconfigurablecircuitnetwork表1E类单元可实现功能和对应配置码Tab.1FunctionsofclassEunita

12、ndcorrespondingconfigurationcode配置码0000000100100011010001010110输出Y,ZY1;Z1;Y2;Z2;Y=(A4);Z=(A4);Y2;Z2;Y1;Z1;Y=A1;Z=B1;Y=A2;Z=B2;配置码1000100110101011110011011110输出Y,ZY=A3;Z=B3;Y=A1+B2;Z=B1+A2;Y=max(A,B);Z=min(A,B)Y=min(A,B);Z=max(A,B)Y=A;Z=B;Y=B;Z=A;Y3;Z3;以上CCN电路对比文献5及文献6中的结构,其主要特点如下:!本文取消了MUX,而采用固定互联结构

13、.这样不但避免了由于MUX的局限性导致的运算单元无法参与到进化评估的问题,而且还可以将节省的配置码和资源完全用于功能单元上,从而提升了进化效率,以期得到更好的进化结果.!采用多个输出端口(总共16个)端口,并对其同时进行评估,进一步确保网络中的每个运算单元712复旦学报(自然科学版)第49卷都能找到通往输出端的通路,都参与到了进化和评估,从而可以进一步提高进化效率和进化结果.基本运算单元分为2类,一类是可以仅通过改变LUT的内容,而不需要改变互联等资源就可以实现运算功能改变的单元,这类单元称作P.还有一类则是无法仅仅通过改变LUT内容,还必须配合互联!改变才能改变其运算功能的单元,这类单元称为

14、E.2种单元有机地糅合在一起的目的在于:在减少配置码和面积的同时,还能具有更多种运算功能,从而可能得到更好的进化结果.1.2进化算法进化算法关系着进化速度的快慢和进化结果的好坏.目前常用的进化算法是基因算法(GA),本文采用的算法为结合了模拟退火算法(SA)的改进型基因算法.该算法的流程如图4.本文采用该算法时,初始化采用随机生成的方法产生初始种群,种群数目设为18.选择方法为轮盘赌选择,交叉方式设为一致交叉,变异概率为5%,运行代数设为100万代.1.3适应度评估由于有16个输出端口,所以对于每一组配置码,需要对全部16个输出端口输出的图像进行评估,但只记录其中最好的一个端口的适应度值和端口

15、号,然后将适应度值和端口号同时反馈回给算法.完成预定的进化代数后,用适应度最高的一组染色体#码重新配置CCN,并用该染色体#码配置下,16个端口中适应度最好的那一个为输出端.这样,就通过进化完成了一个图像滤波器.适应度评估采用计算绝对偏差的方法,即经CCN网络滤波后的图像与理想的无噪声图像进行比较.N-2N-2fitness=i=1i-1ideal(i,j)-filtered(i,j);其中ideal(i,j)是无噪声图像在(i,j)这一点上的像素值,而filtered(i,j)是经过滤波后在(i,j)这点上的像素值.2图像滤波器的整体结构以上介绍了可进化滤波器的3大重要组成部分,作为电路,本

16、文所设计的可重构、可进化滤波器整体结构如图5.其中,处理器用来运行进化算法,并通过FIFO输出配置码.存储部分由SRAM、FLASH和片上BRAM(blockRAM)3部分组成.BRAM存放含有噪声的待滤波图像数据.FLASH用来存储适应度评估时用到的无噪声完美图像数据,SRAM用来存储滤波后的图像数据.除了介绍的几部分之外,整体电路中还包括控制电路、接口电路(FIFO)和图像数据的缓冲器部分.第6期刘少腾等:可进化可重构图像滤波器的设计7133实验结果本文所提出的可重构、可进化图像滤波器的可行性验证借助了AlteraCyclone2FPGA的DE2开发板进行实验.用Cyclone2中的处理器

17、Nios%来运行进化算法,系统中其他的硬件资源则在FPGA中综合生成.开发板上的一些存储资源也同样被使用,如SDRAM,SRAM和FlashRAM等.衡量滤波效果时,普遍采用平均每像素误差(meandifferenceperpixel,Mdpp),Mdpp的计算方法如下:N-2N-2Mdpp=i=1i=1original(i,j)-filtered(i,j)(N-2);其中,original(i,j)是无噪声图像中的像素(i,j),也是滤波所能达到的最理想结果,filtered(i,j)则是实际滤波后的像素(i,j).Mdpp越小,意味着图像质量从数据上来看越好.实验结果如图6和图7.图6的6

18、幅图依次为:(a)待滤波的被高斯噪声(variance=0.03,mean=0)玷污的图像;(b)采用高斯滤波器滤波的结果;(c)完美无噪声图像;(d)经本文可配置结构CCN进行可进化滤波后的图像;作为参考和对比,在本文的平台和算法下(e)采用L.Sekanina文章中5的可重构电路搭建的滤波器的滤波结果和(f)采用P.N.Kumar文章中6的可重构电路搭建的滤波器的滤波结果.数据见表2.图6用不同方法滤除图像中高斯噪声的结果Fig.6FilteredresultsofGaussiannoise表2不同滤波器滤除高斯噪声的结果Tab.2FilteredresultsofGaussiannois

19、e可配置结构方案本文CCN结构一般高斯滤波器L.SekaninaMUX结构5P.N.Kumars滤波器6滤波后Mdpp16.7417.8122.6222.50表3不同滤波器滤除椒盐噪声的结果Tab.3Filteredresultsofsaltpeppernoise可配置结构方案滤波后Mdpp3.443.453.42本文CCN结构L.SekaninaMUX结构5P.N.Kumars滤波器6图7(见第714页)的5幅图依次为:(a)待滤波的被椒盐噪声(5%噪声)玷污后的图像;(b)完美无噪声图像;(c)采用本文可配置结构进行可进化滤波后的图像;和作为参考和对比,在本文的平台和算法下(e)经采用L.

20、Sekanina文章中5的可重构电路搭建的滤波器的滤波结果和(f)采用P.N.Kumar文章714复旦学报(自然科学版)第49卷中6的可重构电路搭建的滤波器的滤波结果.具体数据见表3.图7用不同方法滤除图像中椒盐噪声的结果Fig.7Filteredresultsofsaltpeppernoise从图6和图7中以及表2和表3的对比中,可以清楚地看出,本文提出的可进化滤波器可以对高斯噪声和椒盐噪声进行有效滤波.对于椒盐噪声,滤波的改进是非常明显的,大量噪声被滤除.从数据上来看,噪声图像Mdpp=6.22,滤波后图像Mdpp=3.44.有效地降低了Mdpp值.在本文的平台和算法下进行可进化时,采用L

21、.Sekanina的可重构电路的滤波器,采用P.N.Kumar的可重构电路的滤波器和采用本文提出的CCN结构的滤波器,在椒盐噪声上表现大致相当.但是对于高斯噪声,采用本文CCN的滤波器的滤波结果为Mdpp=16.74,不但优于传统高斯滤波器(Mdpp=17.81),而且还优于采用L.Sekanina的结构的滤波器(Mdpp=22.62)和采用P.N.Kumar结构的滤波器(Mdpp=22.50).因此,本文提出的CCN结构的能够出色地完成滤波要求,完全可以应用于可进化滤波领域.本文相比以上传统图像滤波进化电路能取得较好的进化结果的原因在于:传统含有MUX结构的可进化电路中大量配置码消耗在了MU

22、X上,进化算法负担大而实际能参与进化的运算不多.而本文的CCN结构中,所有的配置码都用在了更有效率的运算单元上,并且所有运算单元均能参与进化,故能得到较好的进化结果.另一方面,结合同时对多个输出进行评估的方法,相比只针对一路输出的传统评估方法,在评估的全面性上更有优势,从而能提升进化的效率.此外,从表4的数据对比中也可以看出,尽管进化100万代所需时间基本一致,但本文所提出的可重构CCN结构在资源消耗上更有优势.本文的可重构CCN结构仅消耗了5210个LE,少于L.Sekanina所使用的传统结构(8004LE).和P.N.Kumar的结构(5848LE).综上所述,本文提出的可重构CCN结构

23、能够出色地完成滤波要求,而且在资源利用上有一定优势,可以应用于可进化滤波领域.与传统进化电路中的多路选择器(MUX)加运算单元的可重构电路不同,本文采用了一种新型可重构电路网络CCN,完成了对高斯滤波器和椒盐噪声滤波器的进化.通过实验数据表明,进化所得到的高斯噪声和椒盐噪声滤波器能够滤除相应的噪声.并且由于采用了基于FPGA结构的设计,在资源利用率上得到了优化.表4可配置结构部分资源及时间消耗(进化100万代)Tab.4Resourcesconsumedonthereconfigurablecircuitandthetimespendon1milliongenerationsevolve可配置

24、结构本文CCN结构L.SekaninaMUX结构P.N.Kumar结构资源/LE521080045848运行时间/h&4&4&4第6期刘少腾等:可进化可重构图像滤波器的设计715本文提出的CCN这一概念,并不局限于本文所采用的Benes拓扑结构.CCN还可以是树状结构、网状结构、蝴蝶状结构等等拓扑结构.根据不同的可进化需要,可以采用不同的结构,并且将该结构与所采用的FPGA硬件结构相联系,这也是我们下一步的研究方向.参考文献:1GreenwoodGW,TyrrellAM.Introductiontoevolvablehardware:Apracticalguidefordesigningsel

25、fadaptivesystemsM.American:AJohnWiley&Son,Inc.Publication,2007:9.2SekaninaL.TowardsevolvableIPcoresforFPGAsC/OLProceedingsofthe2003NASA/DodConferenceonEvolvableHardware2003IEEE.(20030711)20090408.http:/xpls/abs_all.jsp?arnumber=1217659&tag=1.3SekaninaL,DrabekV.Theoryandapplication

26、sofevolvableembeddedsystemsC/OL11thIEEEInternationalConferenceandWorkshopontheEngineeringofComputerBasedSystems.(20040527)20080408.http:/xpls/abs_all.jsp?arnumber=1515451.4VasicekZ,SekaninaL.AnareaefficientalternativetoadaptivemedianfilteringinFPGASC/OLFieldProgrammableLogicandApp

27、lications.(20070829)20090403.http:/xpls/abs_all.jsp?arnumber=4380650&tag=1.5VasicekZ,SekaninaL.EvaluationofanewplatformforimagefilterevolutionJ.Computation,1999,3(3):167196.6KumarPN,SureshS,PerinbamJRP.DigitalimagefilterdesignusingevolvablehardwareC/OLFourthAnnualACISInternational

28、ConferenceonComputerandInformationScience.(20050716)20090408.http:/xpls/abs_all.jsp?arnumber=1515451.7MirfakhraeiN,TangYQ.PerformanceanalysisofBenesnetworksundernonuniformtrafficC/OLConvergingTechnologiesforTomorrowsApplications:16691673vol.3.(19960627)20070503.http:ieeexplore.iee

29、/xpls/abs_all.jsp?arnumber=535291&tag=1.8GonzalezRC,WoodsRE.DigitalimageprocessingM.3rdEd.American:AddisonWseley,1992:116134.AnEvolvableandReconfigurableImageFilterLIUShaoteng,LAIJinmei,CHENLiguang,TONGJiarong,BAOLichun2.BeijingSpaceFlightControlCenter,Beijing100094,China)Abstract:Anewreconfigurableandevolvableimagefilterisdescribed.Aconfigurablecircuitnetwork(CCN)isusedasreconfigurablepartofthisevolvablefilter.InsteadoftraditionalMUXandfunctionunitstructure,thisCCNstructureutilizesBenesne