Contrast Enhancement through Localized Histogram Equalization

Histogram Equalization

To enhance the contrast of a monochrome image:

• Construct a histogram of the grey levels present.
  • 256 bins representing 0 through 255
  • Each bin is the number of pixels with that grey level
• Remap the grey levels so the histogram is (roughly) flat.
  • To ensure that every collection of N adjacent bins has the same pixel count:
    • All pixels within one bin in the input image will be within one (possibly different) bin in the output image. That is, two pixels with equal grey level in the input image will have equal grey level in the output image.
    • For some adequately small value of N (i.e., at some adequately fine scale), collections of N adjacent bins will not have the same pixel count.
  • To ensure that every bin has the same pixel count:
    • The pixels must be dithered to equally fill all bins, including those that would not have had any pixels at all. Note that dithering adds a (pseudo)random value to the pixel's grey level.
    • Two pixels with equal grey level in the input image will not necessarily have equal grey level in the output image.
• Remapping without dithering seems the most appropriate for scientific data — improve the visual information as much as possible without intentionally adding randomness.

Input image (a portion of a cuneiform tablet):

Result of histogram equalization:

To enhance the contrast of a color image, you could simply apply histogram equalization to the red, green, and blue color planes.

Alternative, convert the R,G,B data to H,S,I (Hue, Saturation, Intensity), apply histogram equalization to the intensity channel only, and convert back to R,G,B.

The Problem

Images typically have both large-scale and small-scale variation in intensity, representing features of varying sizes. From an image-processing perspective, an image contains information at varying frequencies, bounded at the low and high ends by the overall image dimensions and the pixel spacing, respectively. Conventional histogram equalization can improve the visibility of local (high-frequency) features only within limits imposed by the overall (low-frequency) variation.

The above image pair demonstrates this — the input image has large-scale variation at a period twice the size of the image. The intensity varies from dimmest at upper-left to brightest at lower-right. The local contrast is improved throughout the image, but not as much as could be possible.

If the image could be segmented into self-similar regions, a histogram could be constructed for each region, and applied for remapping only the pixels within its region. But the image above indicates that large-scale variation will frequently be relatively smooth and not amenable to segmentation.

One Possible Solution — Localized Histogram Equalization

As a simple solution, apply histogram equalization independently to small regions of the image. Most small regions will be very self-similar. If the image is made up of discrete regions, most small regions will lie entirely within one or the other region. If the image has more gradual large-scale variation, most small regions will contain only a small portion of the large-scale variation.

I have written software to remap each pixel based on the histogram of the circular region centered at that pixel. As a quick preview of the results:

Input image (a portion of a cuneiform tablet):

Global histogram equalization (i.e., all pixels are remapped with one histogram based on the entire image:

Histogram equalization based on a region of radius of 100 pixels:

Histogram equalization based on a region of radius of 50 pixels:

Histogram equalization based on a region of radius of 25 pixels:

Histogram equalization based on a region of radius of 12 pixels:

The last image is not particularly useful, but the other results of localized histogram equalization show what I think are improved visualization. Compared to the global histogram equalization, radii of 100, 50, and 25:

• Improve the contrast between the signs at the right and their background.
• Sharpen the signs at right.
• Increase the contrast in the unused portion of the tablet at left.

Localized histogram equalization is obviously a form of high-pass filtering, in which low-frequency information (large-scale intensity variation) is blocked.

Data Used

The cuneiform tablet is item "Spalding 1, Ur III", on loan from Gordon Young. The input data was obtained by simply scanning the tablet on a flatbed document scanner at 600 dpi. Thumbnails of the original unenhanced scans are:

Cuneiform tablet, Spalding 1, Ur III, faces

Obverse face	Reverse face
1st row	1st row (over top edge)
2nd row	2nd row
3rd row	3nd row
4th row	4th and 5th row
5th row

Cuneiform tablet, Spalding 1, Ur III,
vertical edge with rotations

Obverse 30 degrees	Reverse 45 degrees	Edge

The 600 dpi resolution results in the following dimensions of the regions considered when remapping each pixel:

Detailed Results

Click here for detailed results — all full-resolution images enhanced with localized histogram equalization over radii of 10, 25, 50, and 100 pixels, as compared to global histogram equalization. Warning — this is a large page — approximately 8 MB!

Computational Complexity

This is the bad news.... the computational complexity increases with order O(n²m²) with image length and width of n pixels and region radius of m pixels. The radii used were chosen to double in size, and thus each step quadrupled in processing time. The 100-pixel radius took approximately 64 times as long as the 12-pixel radius. Luckily I had a DS-10 Alpha server available, which could process images at approximately three times the speed of a K6-333 platform. For an 883x252 pixel image, with a radius of only 10 pixels, the processing times were:

• DS-10 — 85.292 CPU seconds
• K6-333 — 224.55 CPU seconds

For larger images and a radius of 100, four to eight hours of processing time were required on the DS-10. Obviously field data collection would be separated from archival processing!

Note that both the DS-10 and K6-333 were running Linux and the program was compiled with the gcc Gnu C/C++ compiler. Compaq has released a C/C++ compiler for use on Alphas running Linux, and their compiler should provide better performance.

Applications to 3-D Data

Localized histogram equalization can enhance the images used to visualize 3-D data — click here to see that page.

References

The following provided the motivation and initial guidance: "Contrast Limited Adaptive Histogram Equalization," Karel Zuiderveld, Graphics Gems IV, Paul Heckbert, editor, Academic Press, 1994. However, that work described subdividing the image into 16x16 blocks, calculating the histogram of each such block, and interpolating between remappings for points.

© Bob Cromwell Jul 2008. Created with /bin/vi, hosted on OpenBSD with Apache.    Root password available here