# [FPGA] Fast rough Gamma Correction for video stream processing

Engineering is often about finding a solution for a specific problem :)

The problem here was to resize an HDMI stream before splitting it to different smaller LCD panels. In that specific case the resizing can be done with a basic 2D filter (FIR or averager). But before doing the filtering, which is a linear operation, you need to remove the gamma correction. There are a lot of good article on that topic. To add more challenge, this system needs to run on an FPGA, a Spartan 6, so we only have few multipliers available but not divider or other fancy stuff.

Gamma in computer system is usually 1.8 or 2.2 (sometimes 2.5) so for a 8bit gamma encoded stream the linear space range can be 0 – 21467 or 0 – 196965, It means either 15 or 18 bits. There are two problems with this system:

• Raising to non integer power is complicated with only multiplier and logic.
• Doing a nth root without divider is also a non trivial problem.

If the precision and the quality of the stream are not the main concern it is possible to simplify all the processing chain by simply choosing Ɣ = 2. In that case the Gamma Expansion is really simple, especially in FPGA with DSP Block. The maximum data path size is 16bit. The main advantage is in the Gamma Compression process. It is possible to implement a « bit shift only » approximation of the SQRT function.

This BitShift SQRT is in fact a mix between a small LUT and The Hero’s Method. By using only 1 round of this method we can get a reasonably good SQRT approximation (you can add a negative offset to the result to reduce worst case error).

If we limit the first approximation to be a Power of 2 we can do the first round of Hero’s Method by using only adder and bitshift, making it a 1 cycle simple SQRT approximation. A special care needs to be taken about values near zero to avoid sub-optimal results. A cleaner figure show the worst case error.

Quick explanation:

`SQRT(x) ~= (a + (x/a))/2`

If we accept to use only integer value for input and output we can write:

`SQRT(x) ~= (a + (x >> log2(a)) >> 1`

Where a = 2n with n ∈ . For example:

```x = 16384
a = 128
sqrt(x) = (128 + (16384 >> log2(128))) >> 1
```

Since 128 is already the Square Root of 16384 the result is exact on the first round. The convergence is dependent on the distance between the approximation point and the real sqrt(x). In our case the worst case will be half way between 1282 and 2562.

```x = 32768
sqrt(x) ~= 181,02
a = 128 or a = 256
fstsqrt(x) ~= 191
```

In conclusion this method is precise enough for our use but becomes near useless when log2(x) > 16 bits

Here a quick example with Lena :)

Before Gamma processing:

After Gamma processing (no other processing involved):

Image are almost the same (which is good), we will see, in a future article, why Gamma correction is an important factor in Image processing.

If you want to experiment with it, you can get source file from this page. It include python script to transform BMP to BRAM data and BRAM to BMP, Fast SQRT Verilog source, Testbench top Verilog and batch file. The sources aren’t clean nor optimized but they are just an example of the concept.

Scilab script used to draw various set of graphics:

```clear;

approx_point = 256;

pix_range = (0:65535);

real_sq = sqrt(pix_range);
plot(pix_range, real_sq, 'red');

fast_sq_256 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_256), 'green');

approx_point = 128;
fast_sq_128 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_128), 'yellow');

approx_point = 64;
fast_sq_64 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_64), 'blue');

approx_point = 32;
fast_sq_32 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_32), 'green');

approx_point = 16;
fast_sq_16 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_16), 'yellow');

approx_point = 8;
fast_sq_8 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_8), 'blue');

approx_point = 4;
fast_sq_4 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_4), 'green');

approx_point = 2;
fast_sq_2 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_2), 'blue');

approx_point = 1;
fast_sq_1 = int(int(approx_point + (int(pix_range / approx_point))) / 2);
plot(pix_range, int(fast_sq_1), 'green');

// Process difference between approx and  sqrt
dif_1 = fast_sq_1-sqrt(pix_range);
dif_2 = fast_sq_2-sqrt(pix_range);
dif_4 = fast_sq_4-sqrt(pix_range);
dif_8 = fast_sq_8-sqrt(pix_range);
dif_16 = fast_sq_16-sqrt(pix_range);
dif_32 = fast_sq_32-sqrt(pix_range);
dif_64 = fast_sq_64-sqrt(pix_range);
dif_128 = fast_sq_128-sqrt(pix_range);
dif_256 = fast_sq_256-sqrt(pix_range);

figure();

plot(pix_range,dif_1,'red');
plot(pix_range,dif_2,'green');
plot(pix_range,dif_4,'blue');
plot(pix_range,dif_8,'yellow');
plot(pix_range,dif_16,'black');
plot(pix_range,dif_32,'red');
plot(pix_range,dif_64,'green');
plot(pix_range,dif_128,'blue');
plot(pix_range,dif_256,'yellow');

figure();

subplot(521);
plot(pix_range,dif_1,'red');
subplot(522);
plot(pix_range,dif_2,'red');
subplot(523);
plot(pix_range,dif_4,'red');
subplot(524);
plot(pix_range,dif_8,'red');
subplot(525);
plot(pix_range,dif_16,'red');
subplot(526);
plot(pix_range,dif_32,'red');
subplot(527);
plot(pix_range,dif_64,'red');
subplot(528);
plot(pix_range,dif_128,'red');
subplot(529);
plot(pix_range,dif_256,'red');

figure();

subplot(521);
plot(pix_range,dif_1-dif_2,'red');
plot(pix_range,dif_1-dif_4,'green');
subplot(522);
plot(pix_range,dif_2-dif_4,'red');
plot(pix_range,dif_2-dif_8,'green');
subplot(523);
plot(pix_range,dif_4-dif_8,'red');
plot(pix_range,dif_4-dif_16,'green');
subplot(524);
plot(pix_range,dif_8-dif_16,'red');
plot(pix_range,dif_8-dif_32,'green');
subplot(525);
plot(pix_range,dif_16-dif_32,'red');
plot(pix_range,dif_16-dif_64,'green');
subplot(526);
plot(pix_range,dif_32-dif_64,'red');
plot(pix_range,dif_32-dif_128,'green');
subplot(527);
plot(pix_range,dif_64-dif_128,'red');
plot(pix_range,dif_64-dif_256,'green');
subplot(528);
plot(pix_range,dif_128-dif_256,'red');
subplot(529);
plot(pix_range,dif_256,'red');
```

Quick Verilog view:

````default_nettype none

module fast_sqrt(clk, in, in_valid, out, out_valid);

input wire clk;
input wire [15:0]in;
input wire in_valid;

output wire [7:0]out;
output reg out_valid = 0;

// Lookup Table to choose the approximation point
// We check the range to choose the point

reg [15:0] apoint = 0;
reg [15:0] shifter = 0;

// to be implemented offset correction
reg [7:0] offset = 0;

always @*
begin
if(in[15] == 1'b1) begin // > 32768
apoint = 256;
shifter = 8;
offset = 0;
end else if((in[13] | in[14]) == 1'b1) begin // > 8192
(......) // LUT Continued
end else begin // > 0
apoint = 1;
shifter = 0;
offset = 0;
end
end

// Newton one pass
// sqrt(x) = ( approx + (x / approx)) / 2

reg [7:0]sqrt_res = 0;

always @(posedge clk)
begin
sqrt_res > shifter)) >> 1;
out_valid <= in_valid;
end

assign out = sqrt_res - offset;

endmodule```
Publicités

## 4 réflexions au sujet de « [FPGA] Fast rough Gamma Correction for video stream processing »

1. How does this compare with Chebyschev polynomial approximation over the same range? If multiplying and adding aren’t expensive, that’s what I’d do. Good cites include Numerical Recipes or Wikipedia.