Demosaicing

Demosaicing (or de-mosaicing, demosaicking), also known as color reconstruction, is a digital image processing algorithm used to reconstruct a full color image from the incomplete color samples output from an image sensor overlaid with a color filter array (CFA) such as a Bayer filter. It is also known as CFA interpolation or debayering.

Most modern digital cameras acquire images using a single image sensor overlaid with a CFA, so demosaicing is part of the processing pipeline required to render these images into a viewable format.

Many modern digital cameras can save images in a raw format allowing the user to demosaic them using software, rather than using the camera's built-in firmware.

Goal

The aim of a demosaicing algorithm is to reconstruct a full color image (i.e. a full set of color triples) from the spatially undersampled color channels output from the CFA. The algorithm should have the following traits:

Avoidance of the introduction of false color artifacts, such as chromatic aliases, zippering (abrupt unnatural changes of intensity over a number of neighboring pixels) and purple fringing
Maximum preservation of the image resolution
Low computational complexity for fast processing or efficient in-camera hardware implementation
Amenability to analysis for accurate noise reduction

Background: color filter array

A color filter array is a mosaic of color filters in front of the image sensor. Commercially, the most commonly used CFA configuration is the Bayer filter illustrated here. This has alternating red (R) and green (G) filters for odd rows and alternating green (G) and blue (B) filters for even rows. There are twice as many green filters as red or blue ones, catering to the human eye's higher sensitivity to green light.

Since the color subsampling of a CFA by its nature results in aliasing, an optical anti-aliasing filter is typically placed in the optical path between the image sensor and the lens to reduce the false color artifacts (chromatic aliases) introduced by interpolation.^[1]

Since each pixel of the sensor is behind a color filter, the output is an array of pixel values, each indicating a raw intensity of one of the three filter colors. Thus, an algorithm is needed to estimate for each pixel the color levels for all color components, rather than a single component.

Illustration

To reconstruct a full color image from the data collected by the color filtering array, a form of interpolation is needed to fill in the blanks. The mathematics here is subject to individual implementation, and is called demosaicing.

In this example, we use Adobe Photoshop's bicubic interpolation to simulate the circuitry of a Bayer filter device such as a digital camera.

The image below simulates the output from a Bayer filtered image sensor; each pixel has only a red, green or blue component. The corresponding original image is shown alongside the demosaiced reconstruction at the end of this section.


	Bayer filter samples

Red	Green	Blue

A digital camera typically has means to reconstruct a whole RGB image using the above information. The resulting image could be something like this:


Original	Reconstructed

The reconstructed image is typically accurate in uniform-colored areas, but has a loss of resolution (detail and sharpness) and has edge artifacts (for example, the edges of letters have visible color fringes and some roughness).

Algorithms

Simple interpolation

These algorithms are examples of multivariate interpolation on a uniform grid, using relatively straightforward mathematical operations on nearby instances of the same color component. The simplest method is nearest-neighbor interpolation which simply copies an adjacent pixel of the same color channel. It is unsuitable for any application where quality matters, but can be useful for generating previews given limited computational resources. Another simple method is bilinear interpolation, whereby the red value of a non-red pixel is computed as the average of the two or four adjacent red pixels, and similarly for blue and green. More complex methods that interpolate independently within each color plane include bicubic interpolation, spline interpolation, and Lanczos resampling.

Although these methods can obtain good results in homogeneous image regions, they are prone to severe demosaicing artifacts in regions with edges and details when used with pure-color CFAs.^[2] However, linear interpolation can obtain very good results when combined with a spatio-spectral (panchromatic) CFA.^[3] One could exploit simple formation models of images for demosaicing. In natural images within the same segment, the ratio of colors should be preserved. This fact was exploited in an image sensitive interpolation for demosaicing. ^[4]

Pixel correlation within an image

More sophisticated demosaicing algorithms exploit the spatial and/or spectral correlation of pixels within a color image.^[5] Spatial correlation is the tendency of pixels to assume similar color values within a small homogeneous region of an image. Spectral correlation is the dependency between the pixel values of different color planes in a small image region.

These algorithms include:

Variable Number of Gradients (VNG)^[6] interpolation computes gradients near the pixel of interest and uses the lower gradients (representing smoother and more similar parts of the image) to make an estimate. It is used in first versions of dcraw, and suffers from color artifacts.
Pixel Grouping (PPG)^[7] uses assumptions about natural scenery in making estimates. It has fewer color artifacts on natural images than the Variable Number of Gradients method; it was introduced in dcraw from rel. 8.71 as "Patterned Pixel Grouping".
Adaptive Homogeneity-Directed (AHD) is widely used in the industry. It selects the direction of interpolation so as to maximize a homogeneity metric, thus typically minimizing color artifacts.^[8] It has been implemented in recent versions of dcraw.^[9]
Aliasing Minimization and Zipper Elimination (AMaZE) designed by Emil J. Martinec is slow but has great performance, especially on low noise captures. Implementations of AMaZE can be found in RawTherapee and darktable.

Video super-resolution/demosaicing

It has been shown that super-resolution and demosaicing are two faces of the same problem and it is reasonable to address them in a unified context.^[10] Note that both these problems face the aliasing issue. Therefore, especially in the case of video (multi-frame) reconstruction, a joint super-resolution and demosaicing approach provides the optimal solution.

Trade-offs

Some methods may produce better results for natural scenes, and some for printed material, for instance. This reflects the inherent problem of estimating pixels that are not definitively known. Naturally, there is also the ubiquitous trade-off of speed versus quality of estimation.

Use in computer image processing software

When one has access to the raw image data from a digital camera, one can use computer software with a variety of different demosaicing algorithms instead of being limited to the one built into the camera. A few raw development programs, such as RawTherapee and darktable, give the user an option to choose which algorithm should be used. Most programs, however, are coded to use one particular method. The differences in rendering the finest detail (and grain texture) that come from the choice of demosaicing algorithm are among the main differences between various raw developers; often photographers will prefer a particular program for aesthetic reasons related to this effect.

The color artifacts due to demosaicing provide important clues for identifying photo forgeries.^[11]

References

^ Adrian Davies; Phil Fennessy (2001). Digital imaging for photographers (Fourth ed.). Focal Press. ISBN 978-0-240-51590-8.
^ Lanlan Chang; Yap-Peng Tan (2006). "Hybrid color filter array demosaicking for effective artifact suppression" (PDF). Journal of Electronic Imaging. 15: 2. Bibcode:2006JEI....15a3003C. doi:10.1117/1.2183325. Archived from the original (PDF) on 2009-12-29.
^ Hirakawa, K., & Wolfe, P. J. (2007, September). Color Filter Array Design for Enhanced Image Fidelity. In 2007 IEEE International Conference on Image Processing (Vol. 2, pp. II-81). IEEE.
^ Kimmel, R. (1999). Demosaicing: Image reconstruction from color CCD samples. IEEE Transactions on image processing, 8(9), 1221-1228.
^ Lanlan Chang; Yap-Peng Tan (2006). "Hybrid color filter array demosaicking for effective artifact suppression" (PDF). Journal of Electronic Imaging. 15: 013003. Bibcode:2006JEI....15a3003C. doi:10.1117/1.2183325. Archived from the original (PDF) on 2009-12-29.
^ Ting Chen. "Interpolation using a Threshold-based variable number of gradients". Archived from the original on 2012-04-22.
^ Chuan-kai Lin, Portland State University (2004). "Pixel Grouping for Color Filter Array Demosaicing". Archived from the original on 2016-09-23.
^ Kiego Hirakawa; Thomas W. Parks (2005). "Adaptive homogeneity-directed demosaicing algorithm" (PDF). IEEE Transactions on Image Processing. 14 (3): 360–369. Bibcode:2005ITIP...14..360H. doi:10.1109/TIP.2004.838691. PMID 15762333. S2CID 37217924.
^ Decoding raw digital photos in Linux Archived 2016-10-19 at the Wayback Machine, Dave Coffin.
^ Sina Farsiu; Michael Elad; Peyman Milanfar (2006). "Multi-Frame Demosaicing and Super-Resolution of Color Images" (PDF). IEEE Transactions on Image Processing. 15 (1): 141–159. Bibcode:2006ITIP...15..141F. CiteSeerX 10.1.1.132.7607. doi:10.1109/TIP.2005.860336. PMID 16435545. S2CID 2989394.
^ YiZhen Huang; YangJing Long (2008). "Demosaicking recognition with applications in digital photo authentication based on a quadratic pixel correlation model" (PDF). Proc. IEEE Conference on Computer Vision and Pattern Recognition: 1–8. Archived from the original (PDF) on 2010-06-17.

External links

HowStuffWorks: How Digital Cameras Work, More on Capturing Color, with a demosaicing algorithm at work animation
Interpolation of RGB components in Bayer CFA images, by Eric Dubois
Color Demosaicing Using Variance of Color Differences by King-Hong Chung and Yuk-Hee Chan
Hybrid color filter array demosaicking for effective artifact suppression by Lanlan Chang and Yap-Peng Tan
Image Demosaicing: A Systematic Survey by Xin Li, Bahadir Gunturk and Lei Zhang
Demosaicking: Color Filter Array Interpolation in Single-Chip Digital Cameras, B. K. Gunturk, J. Glotzbach, Y. Altunbasak, R. W. Schafer, and R. M. Mersereau
Spatio-Spectral Color Filter Array Design for Enhanced Image Fidelity, Keigo Hirakawa and Patrick J. Wolfe
Effective Soft-Decision Demosaicking Using Directional Filtering and Embedded Artifact Refinement, Wen-Tsung Huang, Wen-Jan Chen and Shen-Chuan Tai
Similarity-based Demosaicking by Antoni Buades, Bartomeu Coll, Jean-Michel Morel, Catalina Sbert, with source code and online demonstration
A list of existing demosaicing techniques
Interactive site simulating Bayer data and various demosaicing algorithms, allowing custom images(dead)
Geometry-based Demosaicking by Sira Ferradans, Marcelo Bertamio and Vicent Caselles with source code and reference paper. (dead)
A comprehensive list of demosaicing codes and binaries available online Archived 2016-04-21 at the Wayback Machine (dead)

[1] Adrian Davies; Phil Fennessy (2001). Digital imaging for photographers (Fourth ed.). Focal Press. ISBN 978-0-240-51590-8.

[2] Lanlan Chang; Yap-Peng Tan (2006). "Hybrid color filter array demosaicking for effective artifact suppression" (PDF). Journal of Electronic Imaging. 15: 2. Bibcode:2006JEI....15a3003C. doi:10.1117/1.2183325. Archived from the original (PDF) on 2009-12-29.

[3] Hirakawa, K., & Wolfe, P. J. (2007, September). Color Filter Array Design for Enhanced Image Fidelity. In 2007 IEEE International Conference on Image Processing (Vol. 2, pp. II-81). IEEE.

[4] Kimmel, R. (1999). Demosaicing: Image reconstruction from color CCD samples. IEEE Transactions on image processing, 8(9), 1221-1228.

[5] Lanlan Chang; Yap-Peng Tan (2006). "Hybrid color filter array demosaicking for effective artifact suppression" (PDF). Journal of Electronic Imaging. 15: 013003. Bibcode:2006JEI....15a3003C. doi:10.1117/1.2183325. Archived from the original (PDF) on 2009-12-29.

[6] Ting Chen. "Interpolation using a Threshold-based variable number of gradients". Archived from the original on 2012-04-22.

[7] Chuan-kai Lin, Portland State University (2004). "Pixel Grouping for Color Filter Array Demosaicing". Archived from the original on 2016-09-23.

[8] Kiego Hirakawa; Thomas W. Parks (2005). "Adaptive homogeneity-directed demosaicing algorithm" (PDF). IEEE Transactions on Image Processing. 14 (3): 360–369. Bibcode:2005ITIP...14..360H. doi:10.1109/TIP.2004.838691. PMID 15762333. S2CID 37217924.

[9] Decoding raw digital photos in Linux Archived 2016-10-19 at the Wayback Machine, Dave Coffin.

[10] Sina Farsiu; Michael Elad; Peyman Milanfar (2006). "Multi-Frame Demosaicing and Super-Resolution of Color Images" (PDF). IEEE Transactions on Image Processing. 15 (1): 141–159. Bibcode:2006ITIP...15..141F. CiteSeerX 10.1.1.132.7607. doi:10.1109/TIP.2005.860336. PMID 16435545. S2CID 2989394.

[11] YiZhen Huang; YangJing Long (2008). "Demosaicking recognition with applications in digital photo authentication based on a quadratic pixel correlation model" (PDF). Proc. IEEE Conference on Computer Vision and Pattern Recognition: 1–8. Archived from the original (PDF) on 2010-06-17.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]