图像处理理系列文章基本都是我本科毕设论文同步发布，这个项目以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 排序滤波器原理

传统的软件排序算法有许多种，例如冒泡排序、插入排序、选择排序等[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.1.2 基于3点比较器的排序

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

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

3.11.1.3 并行全比较排序

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

图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)=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。

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.3.2 请求响应模式

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

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

3.11.3.3 IP核GUI

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

图3-11-7 RF核的GUI

3.11.4 仿真

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

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

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

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

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

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

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

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

3.11.5 资源和时序

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

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
色原みたび-夏空間