Gamma Correction

Gamma correction is a pixel translation operation used in image processing. It takes each pixel of an image and exponentiates it with a constant - the Gamma, the result of which is multiplied with a normalization factor to yield the output pixel value.

Implementation

Gamma correction can be implemented in a number of ways. For demonstrating and evaluating the PACO LUT core, three implementations were used in comparison. Input images are expected to use 24 bits per color component, 72 bits per pixel in total.
The implementation itself uses a gamma exponent of 1.99 and a normalization factor of 1.

PACO LUT implementation

The PACO LUT implementation uses a lookup-table of 128 values and performs linear interpolation with an additional 12 bits of the input flowing into interpolation.

Software Lookup-table

To speed up gamma correction evaluation at the cost of memory usage, one can take advantage of the limited bit width of image data.
In common image formats, each color component is represented with 8 bits of data, thus such a lookup-table would require 256 entries, each 8 bit wide.
For high-quality images of 24 bits per color already require more than 48 MiB of lookup-table data.
To serve as a viable comparison with the PACO LUT implementation, this approach was implemented on the Rocket SoC as well.

Trivial implementation

The trivial method of converting pixel values to floating-points, applying the aforementioned operation and re-encoding the result to the output format.
This approach is easy to implement but takes the most processor time for computation.
Due to complications with the floating-point unit on the Rocket SoC, this implementation was executed on the host machine and used for quality reference.

Comparison of results

Visual comparison

Below you can find a visual comparison of algorithm output for a test image with a resolution of 512 by 512 pixels and 8 bits per color channel. The image shows from left to right: Original image, output of the PACO LUT implementation, output of the Software Lookup-table and the reference output done by the trivial implementation. To the naked eye, the results of all three implementations are almost identical. In fact, the bit values only differ in the least significant bits.

Numerical comparison

For a numerical comparison, the PACO LUT was evaluated for a uniform subset of the entire input domain: Values 0, 16, 32, …, 2²⁴.
The return values are compared to exact results obtained through the trivial algorithm. To ensure the precision of the reference value, computation was performed using MPFR floating-point numbers with 1024 significant bits.
This experiment was conducted for different gamma values (0.05, 0.75, 1.25, 1.99). The results of the experiments can be found in the table and figure below (percentages are relative 2²⁴):

The error distribution was scaled to show the interesting subset. Outliers to the right do not exceed 0.001%. The figure shows a significant dependency between the gamma exponent and error distribution, however error magnitude occurences converge to 0 at a magnitude of about 0.1%.

Timing comparison

In this comparison, clock cycles were counted in the computation of gamma correction with different algorithms. The table below shows the number of cycles elapsed during the computation of various input pixels. For each input pixel the value is retrieved from memory and then subjected to the gamma correction computation.
The first column shows cycles elapsed without any computation (just memory retrieval), the second one shows time required by the software lookup-table, followed by the PACO LUT implementation. The final column shows the speedup in clock cycles and, in parentheses, the speedup accounting for memory retrieval overhead.

This data shows a linear relationship between inputs and processing time for all executions and a speedup of approximately 1.38 of the PACO LUT relative to the fastest native implementation (software-based lookup-table).
It shows that through cache misses and subsequent memory lookup overhead, the single-instruction PACO LUT execution outperforms the software solution in terms of speed of execution.

Reconfiguration overhead

Both the software and PACO LUT implementations do not directly compare to the trivial implementation as they involve ahead-of-time knowledge of the gamma exponent and corresponding precomputation of data.
In the following we analyze the penalty of re-computing a lookup table for 8 bits of input data (256 value Lookup table).

The PACO LUT uses up to 19 bits of information to compute its output ( 7 bits of segment addresses and 11 bits of interpolation ) thus the full 256 possible inputs must be computed to adjust the LUT for a new gamma value.
In addition to this, the raw data points must be translated to base and incline values for the PACO LUT.

To test the overhead of reconfiguration, a fixed-point implementation of the trivial algorithm was written to be run on the Rocket SoC. While this implementation is very slow, it gives a rough estimation of reconfiguration overhead. The table below shows reconfiguration time and speedup for reconfiguration with various gamma values:

We see that the reconfiguration overhead for both LUT versions are roughly equal and the majority of time is consumed during fixedpoint computation.
Due to a jitter in the computation it is not possible to state accurate comparisons of configuration time without computation time.
Using data from the timing comparison we also see that during recomputation using fixed-point values, about 49 to 69 thousand pixels could have been processed with the PACO LUT (45 to 63 thousand using the software LUT). This corresponds to a greyscale image of about 256 by 256 pixels.

Conclusion

We have seen that gamma correction can be approximated very efficiently using the PACO LUT implementation. Compared to software-based lookup-table implementation, which consists of only a single lookup, a speedup of 38% was achieved while keeping the approximation error below 0.1%.