Simplest Color Balance

This workshop may eventually be submitted and published.

Overview
References
Online Demo
Algorithm
Implementation
Examples

Nicolas Limare nicolas.limare@cmla.ens-cachan.fr, CMLA, ENS Cachan, CNRS, UniverSud
Jean-Michel Morel morel@cmla.ens-cachan.fr, CMLA, ENS Cachan, CNRS, UniverSud
Ana Belén Petro anabelen.petro@uib.es, TAMI, Universitat de les Illes Balears
Catalina Sbert catalina.sbert@uib.es, TAMI, Universitat de les Illes Balears

Overview

Color balance algorithms attempt to correct underexposed images, or images taken in artificial lights or special natural lights, such as sunset. They also translate the raw R,G,B values given by a CCD or CMOS matrix into more standard perceptual colors.

There are many sophisticated algorithms in the literature performing color balance or other color contrast adjustments. The performance of these many color correction algorithms can be evaluated by comparing their result to the simplest possible color balance algorithm proposed here. The assumption underlying this algorithm is that the highest values of R, G, B observed in the image must correspond to white, and the lowest values to obscurity. If the photograph is taken in darkness, the highest values can be significantly smaller than 255. By stretching the color scales, the image becomes brighter. If there was a colored ambient light, for example electric light where R and G dominate, the color balance will enhance the B channel. Thus the ambient light will lose its yellowish hue. Although it does not necessarily improves the image, the simplest color balance always increases its readability.

The algorithm simply stretches, as much as it can, the values of the three channels Red, Green, Blue (R, G, B), so that they occupy the maximal possible range [0, 255]. The simplest way to do so is to apply an affine transform ax+b to each channel, computing a and b so that the maximal value in the channel becomes 255 and the minimal value 0.

However, many images contain a few aberrant pixels that already occupy the 0 and 255 values. Thus, an often spectacular image color improvement is obtained by "clipping" a small percentage of the pixels with the highest values to 255 and a small percentage of the pixels with the lowest values to 0, before applying the affine transform. Notice that this saturation can create flat white regions or flat black regions that may look unnatural. Thus, the percentage of saturated pixels must be as small as possible.

The proposed algorithm provides both a white balance and a contrast increasing. However, note that this algorithm is not a real physical white balance: It won't correct the color distortions of the capture device or restore the colors or the real-world scene captured as a photography. Such corrections would require a captured sample of known real-world colors or a model of the lighting conditions.

References

Wikipedia contributors, "Color balance", Wikipedia, The Free Encyclopedia (accessed January 14, 2010).
Marc Ebner, "Color Constancy", John Wiley & Sons, 2007, p. 104.

Online Demo

With the online demonstration, you can try this algorithm on your own images and set the desired percentage of saturated pixels.

Algorithm

The naive color balance is a simple pixel-wise affine transform mapping the input minimum and maximum measured pixel values to the output space extrema. As we explained before, a potential problem with this approach is that two noise pixels, each at a color space extrema, are enough to inhibit any image transform by this naive color balance.

A more robust approach consists in mapping the V_min and V_max to the output space extrema, with V_min and V_max defined such that a small user-defined proportion of the pixels have values out of the [V_min, V_max] interval.

Implementation

Our input image is an array of N numeric values in the [min, max] interval. The output is a corrected array of the N updated numeric values. Multiple channel images are processed independently on each channel with the same method.

We will perform a color balance on this data with the saturation level s in [0, 1[; for example, 0% saturation means s=0, 3% saturation means s=0.03, and this balance will saturate at most N×s pixels, half at the beginning and half at the end of the histogram. We can't ensure to saturate exactly N×s pixels because the distribution of the pixels' values is discrete.

Sorting Method

V_min and V_max, the saturation extrema, can be seen as quantiles of the pixel's values distribution, e.g. first and 99th centiles for 2% saturation.

Thus, an easy way to compute V_min and V_max is to sort the pixel values, and pick the quantiles from the sorted array. This algorithm would be described as follow:

sort the pixel values The original values must be kept for further transformation by the bounded affine function, so the N pixels must first be copied before sorting.
pick the quantiles from the sorted pixels With a saturation level s in [0, 1[, we want to saturate N × s pixels, so V_min and V_max are taken from the sorted array at positions N x s / 2 and N x ( 1 - s / 2) - 1.
saturate the pixels According to the previous definitions of V_min and V_max, the number of pixels with values lower than V_min or higher than V_max is at most N × s. The pixels (in the original unsorted array) are updated to V_min (resp. V_max) if their value is lower than V_min (resp. higher than V_max).
affine transform The image is scaled to [min, max] with a transformation of the pixel values by the function f such that f(x) = (x - V_min) × (max - min) / (V_max - V_min) + min.

Histogram Method

Sorting the N pixel values requires O(N log(N)) operations and a temporary copy of these N pixels. A more efficient implementation is achieved by an histogram-based variant, faster (O(N) complexity) and requiring less memory (O(max - min) vs. O(N)).

build a cumulative histogram of the pixel values The cumulative histogram bucket labeled i contains the number of pixels with value lower or equal to i.
pick the quantiles from the histogram V_min is the lowest histogram label with a value higher than N × s / 2, and the number of pixels with values lower than V_min is at most N × s / 2. If s = 0 then V_min is the lowest histogram label, i.e. the minimum pixel value of the input image. V_max is the label immediately following the highest histogram label with a value lower than or equal to N × ( 1 - s / 2), and the number of pixels with values higher than V_max is at most N × s / 2. If s = 0 then V_max is the highest histogram label, i.e. the maximum pixel value of the input image.
saturate the pixels
affine transform Same as for the sorting method.

Pseudo-code

The following steps presented for images with pixel values in the 8 bit integer space (min = 0, max = 255) with one color channel only. See the following remarks for higher-precision image. Hereafter is the basic implementation, refinements are available in the proposed source code.

image[i] are the pixel values, N is the number of pixels, histo is an array of 256 unsigned integers, with a data type large enough to store N, initially filled with zeros. The arrays indexes start at 0.

// build the cumulative histogram
for i from 0 to N-1
    histo[image[i]] := histo[image[i]] + 1
for i from 1 to 255
    histo[i] := histo[i] + histo[i - 1]
// search vmin and vmax
vmin := 0
while histo[vmin + 1] <= N * s / 2
    vmin := vmin + 1
vmax := 255 - 1
while histo[vmax - 1] > N * (1 - s / 2)
    vmax := vmax - 1
if vmax < 255 - 1
    vmax := vmax + 1
// saturate the pixels
for i from 0 to N - 1
    if image[i] < vmin
        image[i] := vmin
    if image[i] > vmax
        image[i] := vmax
// rescale the pixels
for i from 0 to N-1
    image[i] := (image[i] - vmin) * 255 / (vmax - vmin)

Higher Precision

For 16 bit integer pixel values, the histogram array method can be used, and needs 65.536 buckets (256 Kb on a 32 bit system, 512 Kb on a 64 bit system, to be compared with the 128 Kb used for a 256×256 image). But the determination of vmin and vmax would benefit of a faster search method, like bisection.

For 32 bit integer pixel values, the histogram size (4.294.967.296 buckets) becomes a problem and can't be properly handled in memory. We can switch to a multi-step process:

build an histogram with buckets containing more than one single pixel value, such that the histogram size is limited (256 buckets for example, each for a pixel value interval);
search for the buckets containing vmin and vmax;
restart the histogram construction and search on a subdivision of these buckets.

If an exact precision isn't required, the latest refinements can be skipped.

For floating-point data, the pixel value can no more be used as an array index, and associative array histograms (only for little images) or multi-step histograms have to be used, for example by rounding the floating-point values as a first step.

Note that the proposed pseudo-code can also be used for images with integer pixel values (as produced by common image capture devices and found in common image formats) stored as floating-point data (often desired for image processing), by converting the pixel value image[i] to its integer equivalent while filling the histogram.

Special Cases

If the image is constant (all pixels have the same value v), then, according to the described implementation and pseudo-code, the histogram values are 0 for labels lower than v, and N for labels higher or equal to v, and then for any value of s in [0,1[, V_min = v, V_max = v.

This (V_min = V_max) can also happen for non-constant image, the general case being images with less than N × s / 2 pixels with values above or below a median value v.

That case must be handled by setting all the pixels to the value v.

Source Code

An ANSI C implementation is provided and distributed under the GPL licence.

source code : zip tar/gz
source code documentation : zip tar/gz online

Basic compilation and usage instructions are included in the README.txt file. This code requires the libtiff library and only handles 8bit RGB TIFF images files.

This source code includes two implementations of the color balance: a simple one, based on qsort(), with O(N log(N)) algorithmic complexity, and another, based on the histogram algorithm, with O(N) algorithmic complexity. The affine transform is enhanced with a faster lookup table method.

The histogram code is used for the online demo.

Examples

We show from left to right the original image, and its color balanced result with 0%, 1%, 2% and 3% of the pixels saturated. It is quite apparent that some saturation is almost always necessary, but that the needed percentage is variable.

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

Here, the 0% saturation already gives a result, and 1% is optimal. Notice how the orange ambient light has been corrected to more daylight image.

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

histograms In fact, a white thin rim surrounds this image! This rim occupies more than 2% of the image. Hence, the 3% threshold is the right one.

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

histograms Like the preceding ones, this image in completely unnatural blue light is often used to illustrate color balance, or color contrast adjustment algorithms. A trivial affine transform corrects it adequately by removing the bluish effect. A still more contrasted result is obtained by saturating only 1%.

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

histograms The same remarks as for the preceding one apply to this image.

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

histograms Even a good quality image can benefit from a moderate 1% color balance. A contrast improvement is noticeable when switching between the 0% and 1% versions.

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

histograms There is no real good solution for this sunset image. The colors are strongly blue/orange and will stay so. By pushing too far the saturation (3%), the orange pixels diminish and a completely unnatural blue color is created.

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

histograms This image and the following two have been used in recent papers on color perception theory (Retinex).

original image	balanced 0%	balanced 1%	balanced 2%	balanced 3%

histograms

Examples on Grayscale Images

We present two examples on grayscale images. The algorithm is the same, since the three channels are equal. In the first image we observe a small improvement of the image. In the second, the improvement is more significant, but we lose the little details in the image.