ipol.im » pub » algo »  
Self-Similarity Driven Demosaicking
edit This workshop may eventually be submitted and published.
  1. Overview
  2. References
  3. Algorithm description
  4. On Line Demo: Try It!
  5. Source Code
  6. Examples

Overview

Digital cameras record only one color component per pixel, red, green or blue. Demosaicking is the process by which from such a matrix of values one can infer a whole color information, thus interpolating the two missing color values per pixel. The selected color configuration of the sensor usually follows the Bayer color filter array, CFA. Out of a group of four pixels, two are green (in quincunx), one is red and one is blue. The Self Similarity driven Demosaicking (SSD) treats the Bayer CFA configuration, but the proposed algorithm is easily adapted to other CFA configurations.

The basic observation used in demosaicking algorithms is that in the Bayer CFA configuration, a higher resolution is obtained in the interpolated green channel. For this reason, most methods first interpolate the green channel and then use it to drive the interpolation of the red and blue channels. The second key observation is that at the same time the high frequencies of the sub-sampled red and blue channels (second derivatives) can be used to interpolate the green channel. The first method proposing the use of these observations was the Hamilton-Adams algorithm [1].

adams mosaic

Adams-Hamilton algorithm

The green channel is horizontally or vertically interpolated at each pixel depending on the green first derivatives and the red and blue second derivatives as follows.

  1. Calculate horizontal gradient
    ΔH = |G4 - G6| + |R5 - R3 + R5 - R7|
  2. Calculate vertical gradient
    ΔV = |G2 - G8| + |R5 - R1 + R5 - R9|
  3. If ΔH > ΔV,
      G5 = (G2 + G8)/2 + (R5 - R1 + R5 - R9)/4
    Else if ΔH < ΔV,
      G5 = (G4 + G6)/2 + (R5 - R3 + R5 - R7)/4
    Else
      G5 = (G2 + G8 + G4 + G8)/4 + (R5 - R1 + R5 - R9 + R5 - R3 + R5 - R7)/8

The red and blue channels are interpolated taking into account the already filled green channel. A bilinear interpolation is applied to the differences R-G and B-G as originally proposed by Cok [2].

The use of the high frequencies of the sub-sampled red and blue channels (second derivatives) has been incorporated by all advanced algorithms. We will use the Hamilton-Adams algorithm as initialization.

The SSD demosaicking method is divided in two steps. In the first step by the image geometry is reconstructed by using its non-local self-similarity. In the second step the colors are updated by transferring information from the green to the red and blue channels. The second step is called chrominance regularity. It subsumes the observation, underlying most algorithms, that the high frequencies of the three channels are very similar. The first step instead performs a non-local estimate taking advantage of all image self-similarities. This step is crucial for the retrieval of fine geometric structure close to the Nyquist frequency.

[1] J. Hamilton Jr and J. Adams Jr, “Adaptive color plan interpolation in single sensor color electronic camera,” 1997, uS Patent 5,629,734.

[2] D. Cok, “Signal processing method and apparatus for producing interpolated chrominance values in a sampled color image signal,” 1987, uS Patent 4,642,678.

References

  1. A. Buades, B. Coll, J.M. Morel, C. Sbert "Self similarity driven demosaicking", IEEE Transactions on Image Processing, Vol. 18(6), pp:1192-1202, 2009.

Algorithm description

The self similarity driven step (NL_h)

The missing color values at a pixel p are interpolated by averaging original CFA values of the same channel with a similar color neighborhood in the initialization image u0 = (r0, g0, b0). In other terms, color inter-correlation is enforced by computing the distance in the three-channel image.

Denote by Ωu the set of pixels where the channel u ∈ {r, g, b} was originally available in the CFA. The averaging process for a pixel p reads,

NL_h u(p) =\frac{1}{C_u (p)} \sum_{q \in\Omega_u} w(p,q) \ u(q), \quad w(p,q) = e^{-\frac{1}{h^2}\sum_{t\in W} \|u_0(p+t)-u_0(q+t)\|^2 }
with p ∉ Ωu where Cu(p) is the normalization factor, equal to the sum of the weights. The weight w(p, q) depends on the Euclidean distance of the two color windows centered at p and q. Thus, pixels with a small patch Euclidean distance will have a larger weight in the average.

In order to gradually correct the erroneous structures and artifacts of the initial image, a coarse to fine strategy that refines at each step the similarity search by reducing the value of h from 32 to 1 is used.

Chromatic regularization (CR)

In contrast with all mentioned algorithms the similarity driven algorithm does not involve at this point any color regularization step. Indeed, it merely transports color values from known to unknown positions. Since the similarity driven super-resolution step fills in all color channels, the chromatic regularity assumption can be applied to the chrominance (U, V) instead of the differences red - green and blue - green. Recall that

Y = a_r r +a_g g + a_b b, \quad U = r-Y, \quad V = b-Y

with ar = 0.299, ag = 0.587 and ab = 0.114. Notice that the green dominates in this linear combination. This coordinate system aims at separating the geometric information contained in Y from the chromatic information U, V, and gives more importance to the green channel.

The chromatic regularity step (CR) decomposes the color image into the YUV components. A median of the coordinates U and V in a 3 × 3 neighborhood is applied obtaining U0 and V0. This median is applied to all the pixels independently of the CFA mask.

The RGB components are obtained from Y U0V0, and the original values of the CFA are put back at pixels where they are known.

Final algorithm

The final method alternates each iteration (with decreasing h) of the self-similarity driven algorithm NL_h and the chromatic regularity step CR(u). This final strategy is summarized in the following pseudo-code which takes as input the values of the CFA mask, I,

u0 <- Initial_Interpolation(I);
for h in {16,4,1} do {
    u <- NL_h(u0);
    u <- CR(u); u0 <- u;
}
Output <- u;

Parameters

For computational purposes the search for similar pixels of the self similarity step is restricted to a search window of 15×15 around each pixel. Even if many similar pixels can be found far away, there is usually enough information kept by taking a large search window.

The window comparison is performed by a flat Euclidean distance on a 3×3 neighborhood. This window has shown to be robust (27 values) and small enough to take care of details and fine structure.

On Line Demo: Try It!

An on-line demo of this algorithm is available.

The demo permits to simulate the Bayer CFA and apply the demosaick it by using the Self Similarity Driven Demosaicking algorithm.

Source Code

A C implementation is provided.

It should compile on any system since it's only strict ANSI C and is distributed under the GPL licence.

Basic compilation and usage instructions are included in the README.txt file. This code requires libtiff and is limited to 8bit RGB TIFF image files.

The same code is used for the online demo.

Examples

The examples below illustrate several aspects of the demosaicking algorithm. We display the original image, the Hamilton-Adams algorithm applied to the simulated CFA and the SSD demosaicking algorithm. We remind that the Adams-Hamilton is used as initialization for the SSD algorithm.

Structures at a critical frequency are difficult to interpolate. The SSD algorithm is able to correctly reconstruct the patterns by involving both the self similarity and the chromatic regularity.

original Hamilton-Adams SSD
original Hamilton-Adams SSD
original Hamilton-Adams SSD
original Hamilton-Adams SSD

When in an image zone, the channels do not have exactly the same high frequencies, artifacts can appear. The non local regularization permits to attenuate this erroneous pattern.

original Hamilton-Adams SSD
original Hamilton-Adams SSD
π