【FPGA/图像处理】算术系统

少女dtysky

世界Skill

时刻2015.05.11

图像处理系列文章基本都是我本科毕设论文同步发布,这个项目以LGPL许可被发布在F-I-L。图像处理中会用到一些基本的数学运算,这些运算构成一个算术系统,对于FPGA而言,如何在资源和运行频率之间保持平衡是一个基本的考量。本节将会说明如何在FPGA中实现符号数、定点数和函数的一些运算。


3 算法实现

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

3.1 算术系统

图像处理中会用到一些基本的数学运算,这些运算构成一个算术系统,对于FPGA而言,如何在资源和运行频率之间保持平衡是一个基本的考量。本节将会说明如何在FPGA中实现符号数、定点数和函数的一些运算。

3.1.1 Verilog的符号系统

在VerilogHDL2001的标准[7]中,符号系统被加入,在使用时只需要加一个"signed"标志便可以将某一个变量标记成符号数,例如:

reg signed[7 : 0] num;

这表示定义了一个八位的寄存器型符号数num。
在Verilog中,符号数是以如表3-1-1的形式存在的,这也是目前DSP中最流行的符号系统。可见,所有的正数以原码形式保存,而负数则以2的补码的形式存在,2的补码的公式定义如式3-1-1。

$$X = -2^{N-1} + \sum_{n=0}^{N-2}x_n 2^n\ \ \ \ \ \ \ \ (3-1-1)$$

其在Verilog中的求得方式如下:

comp = {true_sign, ~true_num + 1}

其中comp表示补码,true_sign表示原码的符号位,true_num表示原码的数据位,可见,2的补码实质上就是在保留符号位的前提下,对数据位的每一位取反后整体加1。

Decimal Value Signed Representation
3 3'b011
2 3'b010
1 3'b001
0 3'b000
-1 3'b111
-2 3'b110
-3 3'b101
-4 3'b100
表3-1-1 3bits的符号数

在实际使用中,考虑到与软件系统的兼容性,由于软件系统底层的符号系统一般也是使用2的补码对负数进行处理,所以所有具有符号数输入的模块都要求采用补码形式,对于原码,我提供了一个原码转换补码的模块,模块实现如下:

module True2Comp(
    true,
    complement);
    parameter data_channel = 1;
    parameter data_width = 17;
    input[data_channel * data_width - 1 : 0] true;
    output[data_channel * data_width - 1 : 0] complement;
    genvar i;
    generate
        `define h (i + 1) * data_width - 1
        `define l i * data_width
        for (i = 0; i < data_channel; i = i + 1) begin
            assign complement[`h : `l] = true[`h] == 0 ? 
                true[`h : `l] : {1'b1, ~true[`h - 1 : `l] + 1};
        end
        `undef h
        `undef l
    endgenerate
endmodule

此核为T2C核,T2C核的原理是——如果输入是正数,返回原码,否则对每一位进行取反,然后整体加1。T2C核可以完成任何位任何通道的原码到补码的转换。
Verilog中符号数的计算包含加法和乘法,减法使用相反数的加法代替,除法则需要专用电路实现,在简单应用中往往采用移位或者查找表来实现,这里不做讨论。在图像处理中,符号数的运算会涉及溢出问题,由于可以设置足够的保护位来防止运算本身的溢出,所以唯一需要考虑的溢出就是图像意义下的溢出,比如色彩为数为8的时候,255就是一个溢出上限,而由于一般状况下色彩和坐标都应当正值,所以0一般都作为一个溢出下限,所以这个时候需要一套舍入系统来完成结果的舍入,这一系统将在3.1.3中讨论。

3.1.2 定点数系统

在FPGA的图像处理所需要的算术系统中,另一个重要的系统是定点数系统,它的存在可以让FPGA进行小数运算,这对于图像增强或者几何变换等操作是必要的。一般而言,可以把定点数系统看做是整数系统的一个扩展,或者说将整数系统看做定点数系统的一个特例。在定点数系统中,我们人为地在某两个数字之间插入一个小数点的标志,来分割整数部分和小数部分,如表3-1-2所示。它和整数系统唯一不同的地方在于,整数系统的这个小数点永远处于最低位的右侧。同时,定点数所表示的数值与一致,均为式3-1-2的形式,包括符号定点数的计算公式也是与式3-1-1一致的,但n的范围则由原来的

([0, \infty])

,扩展到了

([-\infty, \infty])

,所以表3-1-2表示的实际上是3.5。
$$X = \sum x_n2^n\ \ \ \ \ \ \ \ (3-1-2)$$

Integral part Point Fractional part
0 1 0 1
.
1 0 0 0
表3-1-2 4bits.4bits的定点数

定点数的运算和整数运算过程基本一致,不同的是我们需要根据小数运算的规则对结果进行分割,来确立整数位和小数位,比如对于乘法,就需要将原先两个乘数的小数位的位宽相加,作为结果的小数位位宽,如表3-1-3。

Src1 0 1 . 1 0
Src2 0 1 . 1 0
Res 0 0 1 0 . 0 1 0 0
表3-1-3 定点数的乘法

3.1.3 舍入系统

由于图像处理所操作的数据基本都是有范围限制的整数,所以一个舍入系统是必要的,这个系统的作用在于对溢出的数据进行合理的截断,以及将小数舍入的整数。在这个项目中,我选择的是就近舍入,即将舍入到最近的数字,这也是软件算术系统中所广泛使用的。比如,对于一个16bits,定点位为8的定点数,其舍入规则如式3-1-3所示。

$$Res=\left\{\begin{aligned} 0 && Src < 0 \\255 & & Src>255\\ x + 1 & & Src = x.(5-9)\ \& \ x>0 \\x - 1 & & Src = x.(0-4)\ \& \ x>0 \\x - 1 & & Src = x.(5-9)\ \& \ x<0 \\x + 1 & & Src = x.(0-4)\ \& \ x<0 \ \end{aligned}\right.\ \ \ \ \ \ \ \ (3-1-3)$$

对于溢出,一个简单的边界检查便可以达到目的,而对于定点数的小数向整数的舍入,则需要先将定点数转换为原码,而后进行截断,再转换为补码,而后根据原来的补码进行最终的舍入,下面的FR核完成了这个功能:

module FixedRound(
    clk,
    fixed_num,
    round
    );
    parameter num_width = 42;
    parameter fixed_pos = 16;
    input clk;
    input signed [num_width - 1 : 0] fixed_num;
    output signed [num_width - fixed_pos - 1 : 0] round;
    reg signed [num_width - 1 : 0] num_true;
    reg signed [num_width - fixed_pos - 1 : 0] num_comp, tmp_comp;
    reg signed [num_width - fixed_pos - 1 : 0] reg_round;
    assign round = reg_round;
    always @(posedge clk) begin
        num_orig <= fixed_num[num_width - 1] == 0 ? fixed_num : 
            {fixed_num[num_width - 1], ~(fixed_num[num_width - 2 : 0] - 1)};
        num_comp <= num_orig[num_width - 1] == 0 ? num_orig[num_width - 1 : fixed_pos] : 
            {num_orig[num_width - 1], ~num_orig[num_width - 2 : fixed_pos] + 1};
        tmp_comp <= num_comp;
        //Why not use num_comp[25] to judge? : if 0
        case(num_orig[num_width - 1])
            0 : reg_round <= tmp_comp[fixed_pos - 1] == 0 ? num_comp : num_comp + 1;
            1 : reg_round <= tmp_comp[fixed_pos - 1] == 0 ? num_comp : num_comp - 1;
            default : /* default */;
        endcase
    end
endmodule

FR核的原理是,定点符号数fixed_num首先被转换为了原码num_true,而后将小数部分进行了整体的截断,之后再转换为了补码num_comp,最后根据num_true的符号位和fixed_num定点位后的第一位一位,即小数点后的第一位的值来确定舍入方式。如果这一位是1,则代表在十进制中,被舍入数的小数点后第一位大于5,否则小于5,之后根据四舍五入法则进行舍入即可。

3.1.4 函数

图像处理中会用到一些函数,最为常见的就是三角函数,在一些几何变换中这些函数非常有用,对于一些实现方式而言,函数的计算可以交由软件进行,在FPGA部分则不需要关心传来参数的具体意义,直接计算即可,这种做法的好处是泛用性强,但不够直观,所以当需要一定的直观性的时候,就需要一种方式来让FPGA直接得出这些函数的值。例如,如果想用FPGA求得三角函数的值,最常见的做法就是建立一个LUT(Lookup Table,查找表),这相当于建立了一个经验公式,来快速地获得限定范围内函数的值,以下代码便定义了一个sin函数的0-359度的查找表,表的键值对由python脚本计算:

module SinLUT(angle, value);
    input[8 : 0] angle;
    output[17 : 0] value;
    reg[17 : 0] reg_value;
    assign value = reg_value;
    always@(*) begin
        case(angle)
            0 : reg_value <= 18'b000000000000000000;
            1 : reg_value <= 18'b000000010001110111;
            2 : reg_value <= 18'b000000100011101111;
            3 : reg_value <= 18'b000000110101100101;
            ......
            359 : reg_value <= 18'b100000010001110111;
            default: reg_value <= 0;
        endcase
    end
endmodule

参考文献

[7] IEEE Standard Verilog Hardware Description Language," IEEE Std 1364-2001 , vol., no., pp.0_1,856, 2001
doi: 10.1109/IEEESTD.2006.99495

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