Pixel Grouping for Color Filter Array Demosaicing

This paper describes a new color filter array demosaicing algorithm that makes use of some properties of natural scene images to reduce some of the common artifacts introduced by the demosaicing process. Preliminary studies showed that the performance of the algorithm is generally comparable to both Variable Number of Gradients and Linear Color Correction I, and succeeds in addressing some of the problems exhibited by these two algorithms in specific cases.

The the algorithm and its implementation were both developed in the afternoon and the evening of April 3rd, 2003.

Principles of Pixel Grouping

The development of the Pixel Grouping algorithm is primarily guided by the observation that natural scene images are usually composed of numerous groups of pixels, that pixels in the same group are reasonably connected to each other, and have approximately the same brightness and color. By identifying which pixels are in the same group, we can obtain better estimates to the missing colors in the pixels, and improve the appearance of the generated images.

Only the green (luminance) channel is interpolated through the identification of pixel groups. The red and blue channels are generated by a hybrid color correction and modified smooth hue-transition algorithm that enhances clarity along the edges.

Algorithm Description

The algorithm makes use of various techniques from existing algorithms and tries to combine them in an effective manner. Therefore if you are already familiar with some other color filter array demosaicing algorithms, in particular Variable Number of Gradients and Linear Color Correction I, then this one should also be easy to understand. The following array will be used throughout the description.

Interpolation of the green values at blue or red pixels: consider estimating G13 at R13. First calculate gradients in four directions as follows:

ΔN = |R3-R13|×2+|G8-G18|
ΔE = |R13-R15|×2+|G12-G14|
ΔW = |R11-R13|×2+|G12-G14|
ΔS = |R13-R23|×2+|G8-G18|

Determine which direction has the smallest gradient and then use that information to estimate G13 as follows:

ΔN is minimum: G13 = (G8×3+R13+G18-R3)/4
ΔE is minimum: G13 = (G14×3+R13+G12-R15)/4
ΔW is minimum: G13 = (G12×3+R13+G14-R11)/4
ΔS is minimum: G13 = (G18×3+R13+G8-R23)/4

Interpolation of the blue and red values at green pixels: consider estimating B8 and R8 at G8.

B8 = hue_transit(G7, G8, G9, B7, B9)
R8 = hue_transit(G3, G8, G13, R3, R13)

function hue_transit (l1, l2, l3, v1, v3) =
  if (l1<l2<l3 or l1>l2>l3)
  then return v1+(v3-v1)×(l2-l1)/(l3-l1)
  else return (v1+v3)/2+(l2×2-l1-l3)/4

Interpolation of the blue or red values at red or blue pixels: consider estimating B13 at R13.

Δne = |B9-B17|+|R5-R13|+|R13-R21|+|G9-G13|+|G13-G17|
Δnw = |B7-B19|+|R1-R13|+|R13-R25|+|G7-G13|+|G13-G19|
if (Δne ≤ Δnw)
then B13 = hue_transit(G9, G13, G17, B9, B17)
else B13 = hue_transit(G7, G13, G19, B7, B19)

And that is it.

Comparison with Existing Algorithms

So how does it perform? Well, you can judge for yourselves. Shown below are cropped and magnified results of the same RAW image obtained through the following methods:

1. Variable Number of Gradients
2. Linear Color Correction I
3. Pixel Grouping
4. Adobe Photoshop RAW plug-in
5. Unprocessed data straight from the camera

The RAW image was shot with a Minolta DiMAGE 7i camera, and for Variable Number of Gradients and Linear Color Correction I, the implementations in Jeremy Rosenberger's excellent ImageCooker are used as references. The Adobe Photoshop RAW plug-in generated output is made with default settings, and kindly provided by Dalibor Jelinek to be included here.

As you can see, the Adobe RAW plug-in actually does much more than mere performing the demosaic process; apparently the brightness, contrast, and color of the image have also been adjusted to suitable levels. Therefore the Adobe RAW plug-in produced image will appear better-looking than the others, but brightness, contrast, and color are all irrelevant to the performance of the underlying demosaic algorithm, so you should try to disregard the differences in these areas. I have found that the plug-in also exhibits quite a few interesting traits, and you can read my report of findings here.

Discussions on Common Cause of Artifacts

As you can see, the Variable Number of Gradients and Linear Color Correction I samples above exhibits some interesting image artifacts. During the development of Pixel Grouping algorithm I have studied these artifacts closely, and below is what I think some of them comes from:

• Zipper: This effect can be seen in the top horizontal line of the first (left-most) crop of the Variable Number of Gradients and Adobe RAW plug-in samples. Zipper effects are characterized by the lines of dots along horizontal or vertical lines in regular intervals (one dot every two pixels). Someone had suggested that this is caused by misusing different gradients, but I think the real cause is the non-uniform handling of different interpolation cases. Many algorithms separate the interpolation of red/blue values into different cases (for example, estimation of R7 and R8 belong to different cases), and if the algorithms in different cases failed to be consistent to each other, zippers will appear in the final image.
• Isolated Dots: This effect can be found in the first three images of the Variable Number of Gradients, Linear Color Correction I, and Adobe RAW plug-in samples. They appear mostly along edges (third image) and at the end points of lines (at A and C in the first image); lighter area gets light dots and darker area gets dark dots. This effect is most likely caused by the algorithms' efforts to produce sharp edges, and estimates at other pixels nearby (which are also considered as part of the edges) were over-compensated as a result.
• Strips: This effect can be seen in the fourth image of the Variable Number of Gradients and Linear Color Correction I samples. Just look for 45° top-right to bottom-left dark strips in the green area. The exact cause is not known, but I believe it has something to do with the design of both algorithms to search for large patterns of color, so that only the 45° direction gradient is used.
• Localized Color Inconsistencies: This effect can be found in the last image of the Variable Number of Gradients, Linear Color Correction I, and Pixel Grouping samples. Correct rendering of the scene should produce a uniform metallic grey that only differs in brightness. This kind of artifact is caused by the drastic change in luminance over a small area (less than 3×3 pixels), so that the demosaic algorithms have difficulty determining the accurate color of the scene. Observe that the Adobe RAW plug-in performed amazingly (close to unbelievably) well in this case.

Naturally the Pixel Grouping algorithm has been engineered to eliminate most of these artifacts (with the exception of localized color inconsistencies).

Notes on Using Pixel Grouping

So does that mean Pixel Grouping is the ultimate demosaic algorithm everyone has been searching for? Unfortunately not. Dalibor Jelínek had performed extensive analysis and trials to the algorithm, and concluded that Variable Number of Gradients is still the king when it comes to processing natural scenes, which usually contains lots of varying gradients and subtle texture details. In these cases Pixel Grouping tends to turn out images that are blocky and thus unfavorable.

From the designer's perspective, Pixel Grouping is optimized for artificial scenes with uniform colors and clear boundaries between regions that usually appear in printed matter (such as text documents or the panel of the multi-meter in the sample image), thus it may not do as well under other conditions. So which algorithm should you use to process your images? Well, the answer to that question depends on personal taste as well as the scenes in your images. When in doubt, process it with each algorithm, and compare the results with your own eyes.

Sample MRW and Reference Implementation

Reference implementation of the Pixel Grouping algorithm is available as a patch against Jeremy Rosenberger's ImageCooker version 0.3. You can freely use the reference implementation under the terms of the GNU General Public License. The algorithm is named "PixelGrouping" and can be invoked just like other interpolators. The MRW file used to generate the comparison samples above can also be downloaded here, the image is compressed with bzip2, and you may need tools like UltimateZip to open the file under Windows. Note that the compressed MRW file is still over 5MB in size, so please be easy on the server and avoid unnecessary downloads.

• Reference Pixel Grouping implementation
• Sample MRW file

Pixel Grouping is now also implemented in a number of RAW file converters (which mainly deals with Minolta's MRW format). Some of the links are provided below:

• Vector's RAW Deal (Win32 Platforms)
• Dalibor Jelínek's PhotoShop RAW plug-in (Win32 PhotoShop)

Acknowledgments

Here I would like to thank those without whom the work can never reach its present stage. Lots of people had previously worked on color filter array demosaicing algorithms, and it is only by building on their results that enabled me to come up with something even better. Ting Chen's survey on algorithms proved to be particularly valuable in bringing me up to speed on the current state of demosaicing algorithms. Jeremy Rosenberger's ImageCooker is used extensively during the development of this algorithm; even though it is a little bit weak on the documentation side, his well written and well structured code makes it possible to build the reference implementation to work on within such a short time frame. Dalibor Jelínek had provided numerous technical assistance and analysis to this algorithm, which had greatly enhanced my own understanding to its behavior under different circumstances. Finally I must thank my parents, who funded my DiMAGE 7i camera which gave me the motivation to conduct this work you see here.

If you have any opinions, suggestions, or critics, please write to me so I can make further improvements. If you like the algorithm or find it useful, please consider send me an email message or a postcard from where you live (my address can be found on my main homepage in the parent directory).