Improving the colour bleeding into dark image areas

After having developed many images with FDC, I've gained more experience, on the practical side, of its strengths and weaknesses. The only pronounced weakness is the colour bleeding into black or very dark image areas. Mathematically speaking, it's not astonishing that this happens if one considers the filters that are used for obtaining the chroma values.

So I've recently been contemplating about ways to improve this...

What are 'good' chroma values?

When demosaicking a uniformly coloured image area at low iso, any algorithm is practically perfect. Problems arise in areas where pronounced and/or high frequency changes in luminance induce artefacts in chrominance. Then you get false colour artefacts. They are, typically, crazy high chroma values.

Areas of colour bleeding are also characterised by having chroma values that are much higher than they should ideally be.

So 'good' chroma values are basically chroma values that are as low as possible, without losing relevant image information.

This brought me to the idea to use also chroma values of the original Markesteijn algorithm. Why throw them away if you have them already?

So the idea is to use the chroma of either Markesteijn or of the frequency domain approach, depending on which of the two is less saturated.

So in other words, I tried using that chroma which has the lowest absolute value.

After saving the chroma of Markesteijn, this is as easy as two additional lines of code:

cbcr[0] = ((ABS(cbcr[0]) < ABS(cb)) ? cbcr[0] : cb);
cbcr[1] = ((ABS(cbcr[1]) < ABS(cr)) ? cbcr[1] : cr);

The results are rather pleasing. For lower iso images, this yields very clean and artefact-free images. For higher iso images, from around 1.600 upwards, the original FDC approach is still better because this hybrid approach introduces more chroma noise. 

This approach looks really promising, so I'll prepare a fork along these lines on my GitHub repository one of these days.

To be continued...

FDC is in darktable 2.4.0rc0 :-)

Quite a lot going on since the last posts. Frequency domain chroma became more polished in the meanwhile, and is now part of darktable 2.4.0rc0. Needless to say that this is a nice milestone for me.  😀

I take the occasion to link to a more functional description of the algorithm, for the geeks out there.

As the next step, I'm now looking into performance improvements. Maybe symmetric properties of the filter kernels can be exploited, and probably SSE2 is a good option. More to come...

Finding the balance

Filter training

It's a while ago since my last blog post. In the meanwhile, I made quite some progress in several areas of the demosaicking algorithm.

Most notably, I managed to implement an algorithm to train the filters on real reference images. This is one contributor allowing to reduce the filter size from the initially used 31x31 filters to the 11x11 and 9x9 filters used now. I also found out how different training images can have substantial impact on the shape of the resulting filters.

Furthermore, I added additional lowpass filtering in the chroma domain.

Lots and lots of experiments, simulations (calculating CPSNR from mosaicking and subsequently demosaicking reference images), and pixel-peeping lead to the present setup.

And even the present setup is not absolutely perfect...

X-Trans triangle of challenges

The reason is that the X-Trans colour filter array makes reconstruction of chroma information a rather challenging task. In the most common approaches, like the Markesteijn algorithm, areas of high spatial frequency in luminance cause plenty of false colour artifacts.

The most straightforward approach to dealing with these artifacts is any kind of lowpass filtering, especially in the chroma domain. However, by the time that the most pronounced artifacts are reduced, the image can look dull; in the most extreme cases, the image might start looking nearly like a black-and-white image. In any case desaturation, especially in areas of colour transition, will occur.

My initial approaches with rather wide 31x31 filters were efficiently suppressing false colour artifacts without causing too much desaturation. As a positive side effect, they also showed very good results for high ISO images. But, these first approaches were suffering from quite pronounced colour bleeding.

         ... can't have it all ...

1. The Markesteijn algorithm, especially in its one-pass variant, is a typical example of an extreme approach to be found in the lower left corner of the above triangle. There is practically no colour bleeding, there are no subdued colors, but there are—as a consequence—plenty of false colour artifacts.
2. Any application of massive lowpass filtering leads to the situation as depicted at the top corner of the above triangle. The image can look dull; in the most extreme cases, the image might start looking nearly like a black-and-white image. In any case desaturation, especially in areas of colour transition, will occur.
3. The initial approaches described in this blog were representing the situation as found in the lower right corner of the above triangle. The rather wide 31x31 filters looked like a good remedy to the false colour artifacts at first sight. But in the end, these filters caused rather unacceptable colour bleeding.

So my present setup forms a compromise. There are still false colour artifacts, but to a much lesser degree. If aliasing is still present, it is usually so weak that just a little bit of bilateral filtering can solve this residual aliasing. The colour response in areas of colour transitions is slightly subdued, but this appears to be well tolerable. A tiny bit of colour bleeding is still present, but at normal viewing distances this does not really constitute a problem.

If you want to try

As usual, you can find the latest changes in the GitHub repository of the darktable fork.

Many thanks

My special thanks goes to François Guerraz, for pointing me to the use of the quick select algorithm and for making an extra menu entry in the GUI of the darktable fork. Furthermore, I'd like to thank J. Liles for plenty of testing and feedback.

Next steps

I do not think that the visual quality of the algorithm as such can still be vastly improved. Any improvement in one area will likely lead to a deterioration in another area. As a next step I'll look into performance improvements because the algorithm is computationally intensive.

Improved filter size

Similarly good results as with the 31x31 filters can indeed be obtained with smaller, asymmetric filters.

A darktable fork serving as proof-of-concept can be found here: https://github.com/ILiebhardt/darktable.git.

For trying, just compile, deactivate openCL (only C code thus far), and choose ‚1 pass Markesteijn‘ as demosaicking method (doesn’t work for 3-pass, and wouldn’t really yield advantages, either).

First proof of concept

I have a first working proof of concept ready, and the results look very promising. The source code can be found here.

By now, I also came across publication [5], a paper that could have saved me quite a bit of work.
;-) 

In the end, though, it was fun to do the according adaptations myself.

To recall from the first post: I am using the method of [3], [4] and [5] only for chroma. For luma and for establishing directionality, I use the open source Markesteijn algorithm. I found this to deliver superior results than using either of the two algorithms in its pure form.

This latter algorithm, as many other attempts to tackle this CFA, suffers from severe false colour artifacts in image areas where luminance has a high spatial frequency.

Sample images

Here are some sample images from such difficult image areas for comparison. Image pairs are first Markesteijn, followed by my combined approach using frequency domain chroma. Markesteijn is 3 pass. None of the output has further noise processing or median filtering.

Markesteijn 3 pass

Frequency Domain Chroma

Markesteijn 3 pass

Frequency Domain Chroma

Markesteijn 3 pass

Frequency Domain Chroma

Visual evaluation

The images resulting from demosaicking by the combined method employing frequency domain chroma look notably cleaner. The last image pair, for example, is part of a concrete flower pot, and should be grey, with only traces of greenish brown from moss. This is well achieved by the combined method, whereas the 3 pass Markesteijn algorithm alone struggles.

Next steps

Presently, the filters used are 31x31. This filter size is most certainly overkill. So the next challenge will be to reduce filter size whilst maintaining image quality. [4] suggests rectangular filters supporting the directionality, and I am intending to do the same here.

Ultimately, the aim would be to move from the initial proof of concept towards a more workable prototypic implementation.

References

[5] M. Rafinazari and E. Dubois, “Demosaicking algorithm for the Fujifilm X-TRANS color filter array,” in Proc. International Conference on Image Processing (ICIP2014), Paris, France, October 2014, pp. 660-663.

Starting the challenge...

About a year ago, I took a first shot at demosaicking images taken with a color filter array of the X-Trans type. This first shot was basically a gradient based approach using guided filtering, extending the ideas of [1] and [2] to the X-Trans color filter array.

The code is available at https://github.com/ILiebhardt/xtrans.

However, I was never satisfied with the results in chroma. Although the approach can restore luma information reasonably well, it fails to do so for chroma. The reason is that the X-Trans pattern provides for a more limited spatial resolution of chroma information than the Bayer pattern. Most gradient based approaches make implicit assumptions as to the spatial resolution of chroma information. While this goes wrong for Bayer sensors without AA filter, it goes even seriously wrong for X-Trans sensors.

A more tailored approach

An ideal method would take account of the more limited spatial resolution of chroma information of the X-Trans sensor. It would demosaick chroma 'accepting' this limitation, without the attempt to 'over-estimate' chroma - an approach that can only fail for the X-Trans sensor.

While looking for possible approaches, I came across the work of Eric Dubois et. al., which seems to be more in line with above considerations. Interesting starting points are [3] and [4].

It appears possible to apply this approach to the X-Trans pattern. Playing around with some Matlab sample code, this approach seems to be very good in restoring chroma information. It seems to be weaker in restoring luma information and also a bit weaker in finding directionality.

So an idea seems to be to combine a gradient based approach with such a frequency-domain approach. In such a combination, the gradient based approach would ideally be used for restoring luma and for finding directionality, whereas the frequency-domain approach would be used for restoring chroma.

My idea is to use the open source Markesteijn algorithm, which is based on AHD, as gradient based approach. To the best of my knowledge, the frequency-domain algorithm of Dubois et. al. is not patented.

This blog will serve to keep track of ideas and progress, to show sample images, and to accompany any (potential) progress from this idea, via a first proof of concept, towards (if feasible) a real implementation.

References

[1] Kaiming He, Jian Sun, and Xiaoou Tang: 'Guided Image Filtering' in TPAMI 2013, further info also here: http://research.microsoft.com/en-us/um/people/kahe/eccv10/

[2] Daisuke Kiku, Yusuke Monno, Masayuki Tanaka and Masatoshi Okutomi: 'Residual interpolation for color image demosaicking' Proceedings of IEEE International Conference on Image Processing (ICIP), pp.2304-2308, 2013.

[3] Dubois, E.: 'Frequency-Domain Methods for Demosaicking of Bayer-Sampled Color Images', IEEE Signal Processing Letters, Vol. 12, No. 12, December 2005.

[4] Leung, B., Jeon, G., Dubois E.: 'Least-Squares Luma-Chroma Demultiplexing

Algorithm for Bayer Demosaicking', IEEE Transactions on Image Processing