Histogram Equalization
Scott Lawrence
February 2006
0. Table Of Contents
enable javascript to see the table of contents
1. Introduction

There are often times when working with the display of visual data that the target dynamic range of the display technology is different than the source data. There are also times when much of the data in an image is mostly confined to a very small section in the dynamic range of the data. There are many ways to stretch the data to 'fit' the display range, or just to modify it to look good on the display.

The images used for these examples have been acquired through the WASP IR sensors. The sensors have a 12 bit per pixel range. That is to say that any pixel can be in the range [0, 2^12), or [0, 4096). On top of that, most of the "interesting" data is usually within a 500 value range within that data. How do we take those 500 values, and stretch them to fill the screen? How do we do this without losing the other 3500 value levels of data, which may be important?

2. Normalization

Figure 1: Basic "0-0, max-max" normalization



Figure 2: Histogram

Figure 1 shows the image data stretched to fill the [0..255] range of the display with no logic. That is to say that '0' in the original image is '0' in the result image, and '4096' in the original image is '255' in the result image. As you can see, the contrast in it is horrible, and it is very difficult to make out any real detail. If you look at the green histogram in Figure 2, you can see why. Most of the content of the image is only about 1/4 of the full range. (Histograms are explained in the next section.)

As we can see from Figure 1, something must be done to the image data to make it easier to discern details and features. The data and range of the data values is fine for computational purposes, but not for human consumption. One way to do this is via Normalization.

The general concept of Normalization is that you pick a low value and a high cutoff value and map those to be a range in the resulting image. Generally, you will map them to [0..256) for most modern display systems. A quick way to do this is to pick 'minimum' and 'maximum' cutoff values in the range of the sample data, and scale the data between them. You can scale the data linearly or non-linearly, depending on the application. That is to say that everything at or below the 'minimum' cutoff maps to '0' in the display, and everything at or above the 'maximum' cutoff maps to 255 in the dsplay. The values between 'minimum' and 'maximum' are converted to values in the [0, 256) range.

3. Histograms

A histogram basically shows how many of each value of pixel there are in an image. the count of '0' values is over on the left, the count of '4096' values is over on the right. The horizintal shows the "bins" that contain the counts of the number of pixels in that value. The height is usually scaled such that the total height of the graph is the largest count value in the entire histogram. If every bin contained '5' items, then the height would be '5'.

    101	/* the number of bins needn't be related to anything else */
    102	int numberOfBins = 500;
    103
    104	/* where we store the counts */
    105	int histogramData[ numberOfBins ];
    106
    107	/* this contains the "height" of the "tallest" bin */
    108	int histogramMax = 0;
    109
    110	/* start with a cleared array */
    111	memset( histogramData, numberOfBins, sizeof( int )); 
    112
    113	for( i = 0 ; i < (width * height) ; i++ ) {
    114		/* 1. get the sample from the source image */
    115		int sample = sourceData[ i ];
    116
    117		/* 2. find which bin it gets stored in, based on intensity */
    118		int idx = (sample * numberOf Bins) / 4096;
    119
    120		/* 3. since we have a different number of bins to 
    121		      intensity levels, we need to accumulate into 
    122		      the histogramData array */
    123		histogramData[ idx ]++;
    124
    125		/* 4. Adjust our max, if applicable */
    126		histogramMax = ( histogramData[idx] > histogramMax )?
    127				histogramData[idx] :
    128				histogramMax;
    129	}

The 'histogramData' basically counts the number of pixels at each of the associated values. Each elemnet of this array is called a 'bin'. The number of bins can be up to the number of intensity levels of the source data. For ours, that would be 4096. Anything above that is not necessary. It can be smaller than that, but not too small, otherwise all of your data will fit into one or two bins, giving poor results later. For the above example, there are 500 bins.

The math on line 118 converts the range from the source data intensity levels to the number of bins in the histogram.

The resulting histogram contains statistical information about how often a sample with each intensity occurs within the source image data. We also now know the value in the bin with the highest amount, since that's in 'histogramMax'. We can use this to scale the other bins vertically proportionaly when we render the histogram to the screen.

4. Cutoffs

Figure 3: Good cutoff values (Cyan)



Figure 4: Poor cutoff values (Cyan)

Another method to scale this imagery is the use of a stretched normalization with cutoffs. For this one, you would basically say "everything below 'x' intensity is considered '0' in the resulting image, and everything above 'y' intensity is considered '255' in the resulting image." From there, everything in the range is stretched appropriately. This can have decent results, as shown in Figure 3. It can aslo have poor results, if the cutoffs are chosen poorly, as shown in Figure 4. The cutoffs in these images are shown as cyan vertical lines on the histogram.




Figure 5: Automatic cutoffs (Magenta)

This can be made more dynamic by employing a percentage level cutoff (shown as a horizontal magenta line in the above images). A histogram is generated of the data. Then a cutoff value is determined based on a percentage of 'histogramMax' largest bin. If 'histogramMax' was 200, and we had a 10% cutoff, then the cutoff value would be 20. We then iterate from the left '0', and from the right '4096', and find the lowest and highest bins that contain this value as a count. Those bins then determine the cutoffs as above. Results of this are shown in Figure 5.

Another way to look at this is to look down the magenta line, in from the sides. Once it hits the histogram data in green, that's where it sets the 'minimum' and 'maximum' cutoff levels.

5. Histogram Equalization

But what if we want to represent all of the data appropriately, without driving a bunch of intensity data to the rails, as it were? We can do that by using Histogram Equalization.


Figure 6: Equalization Curve (Yellow)

Figure 6 shows another image, this time with a yellow graph overlayed on top of the histogram and image data. The horizontal of this is the same as the above graphs. The horizontal is the value of the pixel in the source image data. The vertical ranges from 0 to (width x height). This data is generated like so:

    300	eqBins[ 0 ] = histogramData[ 0 ];
    301
    302	for( bin = 1 ; bin < numberOfBins ; bin++ ) {
    303		eqBins[ bin ] = eqBins[ bin-1 ]
    304				+ histogramData[ bin ];
    305	}

In a nutshell, each bin in the resulting 'eqBins' array contains an accumulation of all of the histogram values up to that point. We can take this generated data, and now use that to determine intensity scaling.

The horizontal of that graph is the source pixel intensity. If you think of the vertical as the target pixel intensity, you can easily convert from one range to the other. After we've generated the above tables for an image, we can start equalizing that image.

The process, once the histogram is completed, is basically just a few table lookups and a few range scales. Here it is in C form:

    400	for( i = 0 ; i < (width * height ) ; i++ ) {
    401		/* 1. get the source sample */
    402         int sample = sourceData[ i ];
    403
    404 	/* 2. scale the sample to the proper bin number */
    405         int binNo = (sample * numberOf Bins) / 4096;
    406
    407		/* 3. retrieve the value in that bin number */
    408		int v = histEq[ binNo ];
    409
    410		/* 4. scale that value to screen range */
    411		int dest = (v * 256) / histogramMax;
    412
    413		/* 5. store that value in the screen buffer */
    414		screenData[ i ] = dest;
    415	}

And that's basically it. The result is that the image contrast is scaled such that the range with the most detail (the steep portion of the yellow graph) gets the most range on the resulting image. The image might result in a fairly "harsh" quality to it, but for most cases, where the data is distributed decently over a range of bins, it works out reasonably well.

6. Histogram Equalization Gone Bad...

Figure 7: Too few bins, too much change

There are times when this does not work out very well. Generally when there is too much data in too few bins, like you see in the above Figure 7. The result from Histogram Equalization is usually a fair bit more "harsh" looking than other methods, but this is a bit extreme. In this case, a manual approach is probably the best bet, and is shown in the following Figure 8.


Figure 8: Manual approach to data similar to Fig. 7

I could see a system where it would analyze the slope of the equalization curve (Yellow) and if it's above a certain steepness, it could switch over to another method automatically. A procedure to perform this is beyond the scope of this article.