This week, I spent my time to understand and test the demosaicing algorithms in C.

Finding the Right Algorithm

I had done a lot of searching through the Internet, try to figure out what is the best algorithm to be used, and implement it in C program so that I could test it and visualize the effect of it. There are many open source software that provides demosaicing, such as Darktable, RawTherapee, and TISCamera. RawTherapee has a default demosaicing algorithm, which is the Aliasing Minimization and Zipper Elimination (AmaZE), and it is very popular among the RawTherapee community. However, I found that this algorithm is extremely complicated and requires a lot of computation, which is not suitable for designing of the accelerator.

Other than AmaZE, I also found two useful demosaicing algorithm that provide better demosaic effect, the Pixel Pattern Grouping (PPG) algorithm and the Threshold-based Variation of Number Gradient (VNG) algorithm. PPG is the default demosaicing algorithm for darktable, which recommended by darktable for fast demosaicing, whereby AmaZE is the second option of demosacing algorithm for darktable.

PPG algorithm is relatively simpler than the VNG algorithm, as it has less computation in the algorithm, but having a drawback that the red and blue pixels computation would only starts after the green pixels are computed. Meanwhile, VNG algorithm requires a computation of threshold to select the number of gradients that would be take into account for next interpolation computation.

The Difficulty of Implementation

Initially, my plan was to justify these algorithm by justifying the artifacts that would be produced by each algorithm. Thus, I tried to implement the PPG in C code and tested it out first. However, I began to realize the mistake when I talked with my supervisor about it. I had neglected the factor that each algorithm that would be implemented as hardware later, would have difficulty and limitations. One of the simplest example was, there is no multiplication or division in hardware implementation, any multiplication or division should be done in a power of 2, so that it could be done by shifting the bits.

Besides, a lot of things that need to be taken into account with, was the usage each pixels, and how many cycles would it takes for each computation? Would it actually costs more time to compute the algorithm in hardware, rather than implementing it in software? These uncertainties should be solved and eliminated by drawing out the schematic for the algorithm.

Also, keeping in my mind on these limitations, I found that VNG algorithm would be more unpractical to be implemented, as it has more complicated computation compared to PPG algorithm.

The Comparison of Bilinear Interpolation and PPG

As I implemented the algorithm in C, I compiled the program and tested using sample images. By using darktable, the comparison of these two algorithm can be seen from the images below:

Bilinear

Image after Bilinear interpolation

PPG

Image after PPG demosaicing

I realize that the artifacts that had been produced may not be visible seen unless it is zoomed into pixel form. But in overall, PPG algorithm would produce a better result than the Bilinear interpolation, with less artifacts.