【FPGA/图像处理】局部滤波器-排序滤波器

少女dtysky

世界Skill

时刻2015.05.21

图像处理理系列文章基本都是我本科毕设论文同步发布,这个项目以LGPL许可被发布在F-I-L。排序滤波器是一种非线性局部滤波器,它首先将窗口内的每个像素根据色彩的值进行排序,随后根据所给的序号得出最后的结果。排序滤波器的应用十分广泛,其中最常用的是中值滤波器,即为序号为窗口总大小的一半时的情况,此时滤波的结果是原窗口所有像素的中值,除此之外常用的还有极值滤波器,即得出窗口中的极大值或者极小值。排序滤波器常被用于去除椒盐噪声,或者作为后续处理的预处理,相比于均值滤波,排序滤波器能够比较好得保留边界特征。本节将会介绍如何用FPGA实现排序滤波器。
这个IP核的资源在这里:
RankFilter


3 算法实现

明确了设计和架构,便可以进行算法的实现。本章将会说明如何实现图像处理的算法,以及如何运用它们。

3.11 局部滤波器-排序滤波器

排序滤波器是一种非线性局部滤波器,它首先将窗口内的每个像素根据色彩的值进行排序,随后根据所给的序号得出最后的结果。排序滤波器的应用十分广泛,其中最常用的是中值滤波器,即为序号为窗口总大小的一半时的情况,此时滤波的结果是原窗口所有像素的中值,除此之外常用的还有极值滤波器,即得出窗口中的极大值或者极小值。排序滤波器常被用于去除椒盐噪声[16],或者作为后续处理的预处理,相比于均值滤波,排序滤波器能够比较好得保留边界特征。本节将会介绍如何用FPGA实现排序滤波器。

3.11.1 原理

排序滤波器的基本原理见图3-11-1,将像素作为基本元素,一个窗口可以看做是一个列表,对于一个3x3的均值滤波器,列表大小为9。排序滤波器列表中所有的元素进行排序,随后根据序号“rank”得出结果,即式3-11-1所示,之后用这个结果来取代窗口的中心像素点。故可知,排序滤波器的核心在于给一个列表的所有元素进行排序。

图3-11-1 排序滤波器原理
图3-11-1 排序滤波器原理

Q=sorted(I)[rank]        (3111)Q=sorted(I)[rank]\ \ \ \ \ \ \ \ (3-11-1)

传统的软件排序算法有许多种,例如冒泡排序、插入排序、选择排序等[17],这些算法有一个共同的特点是在最好的状况下时间复杂度为O(n),同时根据不同状况需求的排序次数不定,对于FPGA而言这是不可接受的。用FPGA实现时,在流水线模式下,必须要保证排序次数对于拥有任何元素的列表都是确定的,并且由于直到第一个结果输出前每次都要保留整个列表的元素,如果排序周期过长,所造成的资源消耗是巨大的,所以必须找到一个周期确定并且非常快速的排序算法。

3.11.1.1 使用奇偶互换网络的冒泡排序

一种排序算法是使用奇偶互换网络的冒泡排序[3],它在冒泡排序的基础上进行改进,如图3-11-2所示,这是一个大小为9的列表进行排序的结构,每个周期都进行若干次两两排序,并将首或者尾元素进行保留,在9个周期后得到结果,可见,这种排序结构可以保证对于任何周期的排序周期一定,但时间复杂度仍然为O(n),这意味着对于n个元素的列表,需要经过n个周期才能得到排序的结果,并且需要消耗$n^2$个像素的寄存器资源,当n值变大时这个消耗往往是难以接受的。

图3-11-2 使用奇偶互换网络的冒泡排序
图3-11-2 使用奇偶互换网络的冒泡排序

3.11.1.2 基于3点比较器的排序

另一种适用于FPGA的排序算法是基于3点比较器的排序[18],它的原理如图3-11-3所示,可见,这实际上是对3.11.1.1中算法的改进,对于大小为9的列表,它将排序周期从9减少到了3,大大提升了效率。但这种排序算法适用性太为狭窄,基本只可能用于3x3的窗口,考虑到本库的通用性,无法满足需求。

图3-11-3 基于3点比较器的排序
图3-11-3 基于3点比较器的排序

3.11.1.3 并行全比较排序

适用于本库的排序算法为并行全比较排序[19],其基本原理如图3-11-4所示,首先为列表中的每个元素建立一个比较计数寄存器,在第一个周期将此元素和其他的元素进行并行比较,将比较的结果写入比较计数寄存器的对应位,之后对每一次寄存器中“1”的个数进行统计,统计得到的结果即为该元素经过排序后的序号。

图3-11-4 并行全比较排序
图3-11-4 并行全比较排序

可见,此排序算法的核心是两次统计,第一次是某一元素和其他元素大小关系的统计,第二次是比其他元素大的情况的次数统计。第一次统计可以用一个二维数组来实现,但有一个边界的问题,就是如果出现相同的元素该如何处理[20],这里的处理方式是原序号在前优先的原则,序号为0的元素和所有元素进行比较,根据比较结果修改比较计数寄存器0的第n位和比较计数寄存器n的第0位,而后序号为1的元素便不和序号为0的元素进行比较,只比教剩下的元素,将比较计数寄存器定义为二维数组big_flag,则代码如下:

for (i = 0; i < `full_win_width; i = i + 1) begin
    always @(posedge clk)
        big_flag[i][i] <= 0;
end
for (i = 0; i < `full_win_width; i = i + 1) begin
    for (j = i + 1; j < `full_win_width; j = j + 1) begin
        always @(posedge clk) begin
            if(reg_in_data[i] >= reg_in_data[j]) begin
                big_flag[i][j] <= 1;
                big_flag[j][i] <= 0;
            end else begin 
                big_flag[i][j] <= 0;
                big_flag[j][i] <= 1;
            end
        end
    end
end

第二个实质上是若干次的加法,加法的个数由列表的大小确定,考虑到每个相加的数据位数均为1,所以一个周期内的多次加法是可以被接受的,但由于FMax的权衡,仍然要进行同3.10中一样的加法分级拆分,在若干次试验之后,最终将这个次数定为了8次,即一个周期内可以进行八次加法,由此,加法的级数由公式3-11-2确定。

综上,此排序的时间复杂度为O(log8(n),加上第一次的统计时间,本模块最终的时间复杂度和空间复杂度如式3-11-3和3-11-4所示。

O(n)=log8(n1)+2        (3112)O(n)=\lfloor{log_8(n - 1)}\rfloor + 2\ \ \ \ \ \ \ \ (3-11-2)

O(n)=n(log8(n1)+2)ColorWidth        (3113)O(n)=n * (\lfloor{log8(n - 1)}\rfloor + 2) * ColorWidth\ \ \ \ \ \ \ \ (3-11-3)

最终的排序查找输出相当于利用一个RAM完成,这之前需要使用一个编码器来完成最终序号的查找,编码器的输入位数为窗口的全大小,当窗口宽度大于5时综合器无法实现,所以此模块的窗口宽度被限定为2-5。

3.11.2 设计

根据原理可知,RankFilter核(以下简称RF核)核心是两次统计,它们分别由二维数组和分级加法实现。加法的分级可以使用verilog中的generate语句来批量生成,生成的流水线级数依赖于根据窗口宽度计算得出的某个参数,我将此参数命名为sum_stage。另外,还需要一个rank端口来确定输出的序号值。综上,一个RF核需要的配置参数和端口如表3-11-1与表3-11-2。

名字 类型 范围 默认值 说明
work_mode 无符号 0为流水线模式,1为请求响应模式 0 工作模式
window_width 无符号 2 - 15 3 窗口的宽度和高度。
color_width 无符号 1 - 12 8 色彩位宽。
sum_stage 无符号 取决于窗口宽度,为int(log8(window_width^2)) + 1。 3 加法级数。
full_win_bits 无符号 取决于窗口大小 4 窗口总大小的位宽。
表3-11-1 配置参数


名字 端口 类型 范围 默认值 说明
clk 输入 无符号 Clock.
rst_n 输入 无符号 复位,低有效。
rank 输入 无符号 full_win_bits - 1 : 0 输出序号,如果是整个窗口大小的一半,模块工作为中值滤波器,等等。
in_enable 输入 无符号 输入数据使能,在流水线模式下,它是另一个复位信号,在请求响应模式下,只有在它有效的时候in_data才会被真正地改变。
in_data 输入 无符号 color_width * window_width * window_width - 1 : 0 输入数据,必须和in_enable同步输入。
out_ready output 无符号 输出数据有效,在两种模式下,这个信号都会在out_data可以被读取的时候有效。
out_data output 无符号 color_width - 1 : 0 输出数据,将会和out_ready同步输出。
表3-11-2 端口

3.11.3 实现

根据3.11.2的设计便可以实现一个RF核,流水线模式和请求响应模式实现如下。

3.11.3.1 流水线模式

保证地址和数据同步流水化输出,在复位时二者皆输出为0,实现如下:
in_enable或rst_n为低时,系统复位,输出无效;否则加法级数加2个周期后第一个结果被输出,并且每一个clk的上升沿都会送入一个窗口进行处理,第一个输出有效之后,每一个周期都将送出一个结果,波形如图3-11-5。

图3-11-5 流水线模式时序
图3-11-5 流水线模式时序

3.11.3.2 请求响应模式

基本与3.11.3.1一致,但只有in_enable的上升沿时才会有窗口被输入,波形如图3-11-6。

图3-11-6 请求响应模式时序
图3-11-6 请求响应模式时序

3.11.3.3 IP核GUI

完成功能后对RF核进行了封装,封装如图3-11-7。

图3-11-7 RF核的GUI
图3-11-7 RF核的GUI

3.11.4 仿真

RF核虽然对于所有图像都有意义,但一般用于灰度图像的处理,所以我选取了两张灰度图像仿真源,并且考虑到仿真压力,仅测试了宽度为3和5的窗口,分别为中值和极大值的情况,原始图像如图3-11-8。

图3-11-8 原始测试图像
图3-11-8 原始测试图像

使用HDL功能仿真和软件仿真的结果进行PSNR的计算,仿真结果如图3-11-9所示。

图3-11-9 仿真结果
图3-11-9 仿真结果,从左上依次为流水线模式下的HDL功能仿真结果,请求响应模式下的HDL功能仿真结果,软件仿真结果

仿真结果的清晰图像如图3-11-10、3-11-11与3-11-12,可见中值滤波器的确可以在模糊的同时保留边缘,并且窗口越大越模糊,而极值滤波器将会损失更多细节,但能够让边缘更加明晰。

图3-11-10 3x3窗口的中值滤波结果
图3-11-10 3x3窗口的中值滤波结果

图3-11-11 5x5窗口的中值滤波结果
图3-11-11 5x5窗口的中值滤波结果

图3-11-12 3x3窗口的极值滤波结果
图3-11-12 3x3窗口的极值滤波结果

3.11.5 资源和时序

最终实现与窗口大小关系很大,此处只对色彩位宽为8,窗口大小为3和5时的情况进行分析,根据Vivado生成的报表,主要资源耗费如表3-11-3。

窗口大小 Slice LUTs* Slice Registers
3x3 377 228
5x5 2715 1262
表3-11-3 主要资源耗费

同时根据时序报告,3x3窗口下最大的Data Path Delay(数据路径延迟)为3.705ns,即:

FMax = 269.90MHz

即说明,RF核在流水线模式下,理论上在处理1080p全高清图像时可以达到130帧。

5x5窗口下最大的Data Path Delay(数据路径延迟)为6.196ns,即:

FMax = 161.39MHz

即说明,RF核在流水线模式下,理论上在处理1080p全高清图像时可以达到77帧。
可见二者的资源耗费可以接受,但FMax均不理想,这是由于最后的输出实际上实现的是一个读延迟周期的分布式RAM,这种RAM的FMax本身就比较低,并且可以加上一级流水线进行优化,便可以大大提升FMax,考虑时效问题,此处暂且不再进行讨论。 由于数据路径延迟和应用的最终约束设置强相关,所以仅供参考。

3.11.6 分析与结论

PSNR如表3-11-5。

1-3-4 1-3-8 1-5-12 1-5-24 2-3-4 2-3-8 2-5-12 2-5-24 Total
1000000.00 1000000.00 1000000.00 1000000.00 1000000.00 1000000.00 1000000.00 1000000.00 1000000.00
表3-11-5 PSNR

PSNR均值为最大值,RF核与软件等效,同时资源消耗可以接受,设计成功。


参考文献

[3] Donald G.Bailey.基于FPGA的嵌入式图像处理系统设计[M].原魁,何文浩,肖晗译.北京:电子工业出版社,2013
[17] 达文姣,任志国,王龙平等.静态链表上排序算法的研究[J].自动化与仪器仪表,2011,(2):12-14.DOI:10.3969/j.issn.1001-9227.2011.02.006.
[18] 李新春,赵璐.基于中值滤波算法滤波器的FPGA实现[J].计算机系统应用,2011,20(9):82-85,72.DOI:10.3969/j.issn.1003-3254.2011.09.018.
[19] 师廷伟,金长江.基于FPGA的并行全比较排序算法[J].数字技术与应用,2013,(10):126-127.
[20] 李飞飞,刘伟宁,王艳华等.改进的中值滤波算法及其FPGA快速实现[J].计算机工程,2009,35(14):175-177.DOI:10.3969/j.issn.1000-3428.2009.14.061.


感谢

仿真图像来源:
LM7-.410
色原みたび-夏空間

如果不是自己的创作,少女是会标识出来的,所以要告诉别人是少女写的哦。