多种中值滤波算法在可重构架构上的映射实现

葛 伟 齐 志 温 闻 曹 鹏 时龙兴

(东南大学国家专用集成电路系统工程技术研究中心，南京210096)

椒盐噪声是由图像传感器、传输信道、解码处理等过程产生的随机黑白相间的亮暗点，在图像处理应用中会使后续的图像分割、特征提取、图像识别等操作困难.去除椒盐噪声的有效手段是使用中值滤波器［1］，既可以减少图像噪声，又可以获得比线性滤波器更好的边缘保护效果，因而在现代图像处理应用中被广泛用于平滑和去噪.

针对中值滤波算法的高性能设计和优化已经进行了大量的研究.文献［2-3］以FPGA芯片为平台构建中值滤波的处理模块，分别实现对256×320×16 bit图像和128×128×8 bit灰度图像的中值滤波处理;但是，受限于硬件设计中对缓存大小设计的约束，传统设计无法灵活处理具有不同分辨率参数的图像.文献［4-5］根据FPGA的硬件结构特点对传统中值滤波排序算法进行优化，采用3×3的搜索模板，分别实现分辨率为640×480和1 024×1 024像素的灰度图像实时处理;然而，这种设计仅能实现搜索窗口大小固定为3×3的中值滤波算法，无法为算法提供搜索框大小参数的选择.文献［6］对传统的冒泡排序系统进行优化设计，采用双端口排序器和扫描线FIFO缓存在内的方法获得3×107像素/s的最大处理视频数据流能力;文献［7］采用串行输入、并行处理的方法实现最高4×107像素/s的像素处理速率;这2种设计方法针对快速中值滤波算法进行了特殊的硬件设计，无法满足多种滤波算法进行设计空间探索的需要.通过以上分析可知，基于FPGA芯片的中值滤波实现方法受到ASIC实现方法仅能针对固定参数实现特定算法的限制，无法满足高性能实时处理中对多种滤波算法多种参数的灵活需求.

针对现有中值滤波算法实现过程中存在的问题，本文采用可重构计算方法，基于可重构硬件架构具有的并行计算资源和动态功能配置灵活性的特点，实现能够支持不同分辨率图像、不同搜索窗大小的多种中值滤波算法，满足高性能中值滤波算法实时处理和灵活高效的需求.

1 中值滤波算法分析

中值滤波［1］是一种能有效抑制图像噪声并提高信噪比的非线性滤波技术，可在滤除椒盐噪声的同时保护目标图像边缘.该算法利用邻域像素值进行排序，将排序后的中间结果作为最终像素输出，即

式中，median()为中值滤波函数;f(x，y)为输入像素值;g(x，y)为输出像素值;S为搜索模板窗口.

排序过程的伪码如下:

分析伪码可知，对于搜索窗口为3×3的中值滤波，每次循环迭代需要对9个元素进行排序，至少完成5个元素从小到大的排序.

文献［8］基于传统的中值滤波器设计提出了一种二维中值滤波快速算法.这种算法减少了单次计算的输入数据量，简化后续计算所需步骤，有利于硬件的流水实现.

传统中值滤波算法会过滤掉小于搜索模板窗口1/2宽度的线条，同时还会导致曲线部分模糊.混合中值滤波算法［9］采用3步排序的方法，考虑空域图像的不同权重值，分别从不同方向对像素值进行排序，对边缘的保护效果优于传统中值滤波算法.

由此可知，中值滤波算法存在以下2个特点:①比较操作需要对2个输入数据进行排序，同时需要按照数值的大小返回2个输出数据;②中值滤波算法需要经过多次迭代才能获得最终的滤波结果，每次迭代都涉及数据在多个数组之间的传递.这2个特点可用于指导可重构架构的优化设计.

2 可重构架构平台

可重构计算［10］的概念在20世纪60年代被提出，即通过一个非柔性可编程的处理器加上一组柔性可重构数字逻辑实现可重构计算系统.可重构计算方法结合了ASIC专用电路和通用处理器的特点，既可以获得高性能并行计算能力，又能灵活实现不同算法，在计算密集型应用［11-12］和多标准通信算法［13］中有广泛的应用前景.

图1 可重构系统架构模板

如图1所示，本文采用的可重构系统架构模板类似于MorphoSys［12］的计算结构，自顶向下包括6个功能模块.可重构计算阵列(reconfigurable cell array，RCA)由二维重构单元(reconfigurable cell，RC)以及阵列内的分布式寄存器文件(distributed register file，DRF)组成，负责执行计算密集任务.其中，RC作为基本的计算功能单元，可以执行算术、逻辑或访存操作，其结构如图2所示.DRF散布于RCA内，用于暂存计算过程中产生的临时数据，实现多个RC间的数据传递与共享.全局数据存储器(global data memory，GDM)缓存计算阵列的外部数据，满足阵列间的数据交换和寄存功能.配置寄存器文件(context register file，CRF)用于缓存动态重构过程中所需的配置信息.数据流控制器(data flow controller，DFC)完成数据从阵列外到阵列内的传输、转换和拼接功能，实现外部存储器、片上存储器以及阵列间的数据交换.配置流控制器(context flow controller，CFC)实现配置文件从外部存储器读入CRF，同时控制 RCA配置信息的更新和加载.系统接口(system connect interface，SCI)包括配置接口和访存接口2个部分:① 系统控制内核通过配置接口实现对重构计算阵列的初始化配置;②DFC和CFC则通过多端口的访存接口实现对存储器的操作.根据不同的设计需求，可重构系统架构模板可以参数化实现不同的阵列规模、互联方式、数据位宽、DRF容量，同时可以定义RC是否具有访存功能.

图2 RC的结构示意图

3 针对中值滤波算法的重构架构优化

为了能够满足多种中值滤波算法的高效实现，根据理论分析总结的算法特点，针对可重构计算架构中RC的双端口输出设计和分布式跨域寄存器设计进行优化.

在中值滤波算法关键的比较排序操作中，需要对2个输入数据进行比较，按照数值的大小返回2个数据.传统RC通常采用双输入、单输出的端口设计［11-13］，这种设计能够满足通常的算术逻辑运算，却无法实现比较排序操作.因此，本文设计的RC如图2所示，拥有2个输出端口:输出A和输出B.通过配置信息寄存器，设置相应的比较排序操作码，RC即可对输入数据A和B进行比较，输出A端口为较大数值，输出B端口为较小数值.排序比较操作完成之后，设置使能标志C和CN.

图3 快速中值滤波算法示例

利用可重构计算单元RC的排序算子，并参考文献［6］提出的3输入排序器方法，本文实现了由重构单元RC组成的多输入排序器.如图3所示的5输入排序器中，p1～p4分别输入2个重构为比较排序功能的RC，p5则输入1个重构为路由功能的RC.经过5级流水线后可以获得5个输入数据经过比较排序之后的大、中、小3个数值.同时，以文献［4］中提到的经典收缩排序方法为基础，通过级联多个排序器可以实现快速中值滤波器和混合中值滤波器.相比传统中值滤波，采用多个小规模排序器的级联组合，可以减少输入计算数据之间的依赖，提高重构资源的利用率.以图3中5×5搜索模板窗口的快速中值滤波算法为例，首先对搜索窗中每一列按照像素值从小到大进行5输入排序，然后对排序后的第1行、中间行和最后1行进行5输入排序，最后选取第1行的最大值、中间行的中间值和最后1行的最小值进行3输入排序.同理，5×5搜索模板窗口的混合中值滤波如图4所示，以目标像素P(x，y)为中心，分别选取平行于搜索窗口边缘的像素和45°方向的像素进行9输入排序.然后，利用前面获得的2个中值结果与目标像素进行3输入排序.最终获得5×5搜索模板窗口大小下快速中值滤波算法的输出结果.

图4 混合中值滤波算法示例

中值滤波算法需要经过多次迭代才能获得最终的结果，每次迭代都涉及数据在多个数组之间的传递.在可重构架构中，数据在由RC组成的排序器中具有良好的局部性，然而级联的排序器之间存在着长距离的数据传输.为了满足高性能硬件设计并减少互联线面积，可重构架构［11，13］通常采用局部互联线实现短距离的数据传输，利用RC作为数据路由单元实现长距离的数据交换.这样的设计会导致阵列计算由于等待数据而停顿，严重时导致算法受限于架构约束而无法映射实现.中值滤波算法在可重构架构上的高性能实现依赖于有效的数据交换和传输.因此，为了解决可重构架构中长距离数据传输的困难，本文提出了分布式跨域寄存器(distributed cross-register files，DCRF)设计.

DCRF用于实现RCA内部的数据缓存和交换，采用多输入、多输出的数据访存形式，每行和每列各共享一组寄存器.如图5所示，每个RC可以操作2组寄存器，分别对应跨行寄存器和跨列寄存器组，每个RC在同一时间仅能操作一组寄存器，多个RC间的读写操作通过多路选择器进行选择.为了避免不同的RC在同一时刻写相同的分布式寄存器，DCRF采用了2种方法:①在映射中增加架构约束［14］条件，避免将多个写操作映射到同一个DCRF;②当硬件中出现多个RC同时改写一个DCRF的情况，则根据RC的标号从大到小进行优先级划分.

图5 分布式跨域寄存器示例

DCRF不仅提供了同一行、同一列的数据传输交换机制，而且能够提供更大范围内长距离的数据传输方案.利用位于行列焦点的RC进行数据传递，可以在2个计算周期中完成数据在整个计算阵列上的传输.如图5所示，当位于阵列(m，n)的RC输出数据需要传递到位于阵列(1，1)时，可以通过位于(m，1)的RC进行数据传递.在运行时刻Ti，RC(m，n)将数据写入跨行寄存器组中，在时刻Ti+1时，RC(m，1)通过数据交换指令将DCRF跨行寄存器组1中的数据写入跨列寄存器组，这样在时刻Ti+2时，RC(1，1)即可以在跨列寄存器中获得RC(m，n)的输出数据，从而实现级联的排序器之间长距离数据传输.

4 实验与分析

本文采用SMIC 130 nm COMS工艺实现100 MHz系统频率，同时考虑中值滤波算法的数据特性，设置可重构架构模板参数.16 bit数据位宽的RC按照8×8的二维排列方式组成RCA阵列，每个RC与相邻的RC通过8 NN连接方式实现全互联.可重构阵列的每行或每列均包含容量为2、数据位宽为16 bit的DCRF.全局寄存器共4个，与所有RC全互联连接.具有访存功能的RC共有32个，RC的访存请求在仲裁器整合之后，以4 byte对齐连续猝发的方式进行存取，访存返回的数据再根据请求分发到各个RC中.

表1给出了多种中值滤波算法在不同搜索模板窗口参数下的实验结果.重构阵列在3×3搜索窗口可以获得最高75.21×106像素/s的像素处理速率.在传统中值滤波算法的可重构实现中，随着搜索模板窗口的不断扩大以及计算复杂度的增加，图像处理能力从75.21×106像素/s迅速下降到3.19×106像素/s，小于快速中值滤波算法的10.89×106像素/s和混合中值滤波算法的12.27×106像素/s.

表1 多种中值滤波算法在不同搜索模板窗口下像素处理速率 106像素/s

利用快速中值滤波算法对不同分辨率的图像进行滤波处理，得到不同搜索模板窗口参数下的图像实时处理的每秒帧率.采用本文提出的可重构快速中值滤波算法对 QCIF，CIF，QVGA，VGA图像分别进行3×3，5×5，7×7搜索模板窗口的中值滤波，结果见表2.由表可知，在VGA分辨率、7×7搜索窗口条件下，可实现的最大处理速率为35.97帧/s，在QCIF分辨率、3×3搜索窗口条件下，可以实现高达2 967.71帧/s的处理速率.图6为图像在不同搜索窗大小下的滤波效果对比示意图.由图可知，采用重构方法可以根据不同的设计需求实现不同算法复杂度的中值滤波算法.

表2 快速中值滤波算法对不同分辨率图像的实时处理速率帧/s

图6 不同大小搜索窗滤波效果

采用不同架构设计方法实现中值滤波算法的性能对比结果见表3.采用SMIC 130 nm CMOS工艺，使得本文的设计可以在100 MHz系统主频下获得比现有实现方法更高的像素处理速率75.21×106像素/s.利用FPGA器件，采用ASIC的实现方法仅能针对特定算法实现固定参数的中值滤波算法，其芯片资源利用率受限于器件的型号和容量.由对比数据可知，采用可重构的实现方法获得0.34×103像素/门的单位门数图像处理速率.采用可重构方法需要提供额外的重构和路由控制功能，虽然增加了电路的硬件资源开销，但是可以灵活实现多种不同的中值滤波算法，并可以根据不同的应用场合采用不同大小的搜索窗口(如3×3，5×5，7×7).对比FPGA器件的实现方法，可重构计算方法的单位电路性能处于合理范围.在单位频率性能的对比中，本文采用的可重构方法可以获得最高0.75×106像素/MHz的单位频率图像处理速率，虽然不能达到 ASIC 设计［3，5，7］的图像处理速率0.94×106～1.00 ×106像素/MHz，但是借助先进设计工艺所带来的性能提升，可重构灵活的计算模式完全可以满足算法的设计空间探索需求.

表3 不同架构的图像处理性能对比

5 结论

本文在粗颗粒度可重构架构上实现多种中值滤波算法，利用可重构架构中二维的并行计算资源和高效的数据传输结构，为快速实现图像应用的滤波算法提供有效参考.实验采用 SMIC 130 nm COMS工艺实现100 MHz系统主频，可以获得中值滤波算法在3×3搜索模板窗口下最高75.21×106像素/s的像素处理速率.与其他实现方案相比，设计不仅提高了处理性能，而且提供了灵活实现多种算法的能力.

References)

［1］Tukey J W.Exploratory data analysis［M］.Boston，USA:Addison-Wesley，1977:5-23.

［2］石婷，张红雨，黄自立.基于 StratixⅡ EP2S60的改进中值滤波器的设计及实现［J］.国外电子元器件，2007(1):12-15.Shi Ting，Zhang Hongyu，Huang Zili.Design and realization of improved median based on StratixⅡEP2S60［J］.Global Electronic Components，2007(1):12-15.(in Chinese)

［3］李雷鸣，张焕春，张波.一种基于FPGA的图像中值滤波器的硬件实现［J］.电子工程师，2004，30(2):48-50.Li Leiming，Zhang Huanchun，Zhang Bo.The realization of image median filter based on FPGA ［J］.Electronics Engineer，2004，30(2):48-50.(in Chinese)

［4］Vega-Rodríguez M A，Sánchez-Pérez J M，Gómez-Pulido J A.An FPGA-based implementation for median filter meeting the real-time requirements of automated visual inspection systems［C］//Proceedings of the 10th Mediterranean Conference on Control and Automation.Lisbon，Portugal，2002:42-49.

［5］Lu Y，Dai M，Jiang L，et al.Sort optimization algorithm of median filtering based on FPGA ［C］//Proceedings of IEEE 2010 International Conference on Machine Vision and Human-Machine Interface.Kaifeng，China，2010:250-253.

［6］Bates G L，Nooshabadi S.FPGA implementation of a median filter［C］//Proceedings of IEEE 10th Annual Conference on Speech and Image Technologies for Computing and Telecommunications.Brisbane，Australia，1997:437-440.

［7］Maheshwari R，Rao S，Poonach E.FPGA implementation of median filter［C］//Proceedings of the tenth International Conference on VLSI Design:VLSI in Multimedia Applications.Hyderabad，India，1997:523-524.

［8］Huang T，Yang G，Tang G.A fast two-dimensional median filtering algorithm ［J］.IEEE Transactions on Acoustics，Speech and Signal Processing，1979，27(1):13-18.

［9］Davies E R.Machine vision:theory，algorithms，practicalities［M］.Amsterdam，Holland:Elsevier，2004:51-54.

［10］Estrin G.Organization of computer systems:the fixed plus variable structure computer［C］//Proceedings of Western Joint IRE-AIEE-ACM Computer Conference.San Francisco，USA，1960:33-40.

［11］Min Z，Leibo L，Shouyi Y，et al.A reconfigurable multi-processor SoC for media applications［C］//Proceedings of 2010 IEEE International Symposium on Circuits and Systems(ISCAS).Paris，France，2010:2011-2014.

［12］Singh H，Ming-Hau L，Guangming L，et al.Morpho-Sys:an integrated reconfigurable system for data-parallel and computation-intensive applications［J］.IEEE Transactions on Computers，2000，49(5):465-481.

［13］Yamada H，Yamagishi T，Suzuki T，et al.A multimodal wireless baseband core using a coarse-grained dynamic reconfigurable processor［C］//Proceedings of 2011 IEEE Cool Chips い.Yokohama，Japan，2011:1-3.

［14］Vassiliadis S，Soudris D. Fine-and coarse-grain reconfigurable computing［M］.Berlin:Springer，2007:255-297.