Histogram Equalization

Computer Vision

Medium

Problem

Theory

Histogram equalization is an image processing technique that adjusts the contrast of an image by redistributing pixel intensity values. The goal is to spread out the most frequent intensity values, effectively increasing the global contrast. This transforms images with narrow intensity ranges into images that utilize the full available range.

Why Histogram Equalization?

Enhance contrast: Images with poor lighting or limited dynamic range become more visually informative.

Standardize images: Different images captured under varying conditions can be normalized to similar intensity distributions.

Preprocessing for analysis: Many computer vision algorithms perform better on contrast-enhanced images.

Reveal hidden details: Features in dark or washed-out regions become visible after equalization.

Understanding Image Histograms

An image histogram shows the distribution of pixel intensities:

X-axis: Intensity values (0 to 255 for 8-bit grayscale)

Y-axis: Number of pixels at each intensity level

Narrow histogram: Low contrast - pixels clustered in small intensity range

Wide histogram: High contrast - pixels spread across full intensity range

Skewed histogram: Image is predominantly dark (left-skewed) or bright (right-skewed)

The Equalization Goal

Transform the histogram to be approximately uniform - each intensity level should have roughly the same number of pixels.

Before: Histogram peaked at certain values, sparse elsewhere

After: Histogram approximately flat across all intensity levels

Effect: Maximizes information entropy of the image

Mathematical Foundation

The transformation is based on the cumulative distribution function (CDF) of pixel intensities.

Step 1 - Compute histogram:

h(k) = \text{number of pixels with intensity } k

For k = 0, 1, 2, ..., L-1 where L is the number of intensity levels (typically 256).

Step 2 - Compute probability distribution:

p(k) = \frac{h(k)}{N}

Where N is the total number of pixels.

Step 3 - Compute cumulative distribution function (CDF):

\text{CDF}(k) = \sum_{j=0}^{k} p(j)

Step 4 - Apply transformation:

s_k = \text{round}((L-1) \cdot \text{CDF}(k))

The new intensity s_k for each original intensity k is the CDF scaled to the output range.

Worked Example

Small image (4x4 pixels, intensities 0-7):

Pixel values: [0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 7]

Step 1 - Compute histogram:

• h(0) = 1
• h(1) = 2
• h(2) = 3
• h(3) = 2
• h(4) = 4
• h(5) = 2
• h(6) = 1
• h(7) = 1

Total pixels N = 16

Step 2 - Compute probabilities:

• p(0) = 1/16 = 0.0625
• p(1) = 2/16 = 0.125
• p(2) = 3/16 = 0.1875
• p(3) = 2/16 = 0.125
• p(4) = 4/16 = 0.25
• p(5) = 2/16 = 0.125
• p(6) = 1/16 = 0.0625
• p(7) = 1/16 = 0.0625

Step 3 - Compute CDF:

• CDF(0) = 0.0625
• CDF(1) = 0.0625 + 0.125 = 0.1875
• CDF(2) = 0.1875 + 0.1875 = 0.375
• CDF(3) = 0.375 + 0.125 = 0.5
• CDF(4) = 0.5 + 0.25 = 0.75
• CDF(5) = 0.75 + 0.125 = 0.875
• CDF(6) = 0.875 + 0.0625 = 0.9375
• CDF(7) = 0.9375 + 0.0625 = 1.0

Step 4 - Compute new intensities (L=8):

• s(0) = round(7 * 0.0625) = round(0.44) = 0
• s(1) = round(7 * 0.1875) = round(1.31) = 1
• s(2) = round(7 * 0.375) = round(2.63) = 3
• s(3) = round(7 * 0.5) = round(3.5) = 4
• s(4) = round(7 * 0.75) = round(5.25) = 5
• s(5) = round(7 * 0.875) = round(6.13) = 6
• s(6) = round(7 * 0.9375) = round(6.56) = 7
• s(7) = round(7 * 1.0) = round(7) = 7

Transformation mapping: 0→0, 1→1, 2→3, 3→4, 4→5, 5→6, 6→7, 7→7

The intensities are now more spread out across the range.

The CDF as a Transformation Function

The CDF naturally creates a transformation that:

Stretches common intensities: Regions with many pixels (high histogram bars) get mapped to wider output ranges.

Compresses rare intensities: Regions with few pixels get compressed.

Monotonic: The transformation preserves ordering - brighter pixels stay brighter.

Properties of Histogram Equalization

Automatic: No parameters to tune - the algorithm adapts to each image.

Deterministic: Same input always produces same output.

Reversible in theory: The mapping function could be inverted (though information is lost due to rounding).

Global operation: Uses statistics from entire image.

Handling Different Bit Depths

8-bit images: L = 256 intensity levels (0-255)

16-bit images: L = 65536 intensity levels (0-65535)

Floating-point images: Must be quantized or handled differently

The formula scales appropriately with L.

Limitations of Global Histogram Equalization

Over-enhancement: Can amplify noise in uniform regions.

Loss of local contrast: Global statistics may not suit all image regions.

Unnatural appearance: Aggressive equalization can create artificial-looking results.

Background noise amplification: Dark regions with sensor noise become more visible.

Adaptive Histogram Equalization (AHE)

Addresses limitations by applying equalization locally:

Process:

1. Divide image into small tiles
2. Equalize each tile independently
3. Interpolate at tile boundaries to avoid artifacts

CLAHE (Contrast Limited AHE):

• Limits contrast amplification by clipping histogram
• Redistributes clipped pixels uniformly
• Prevents over-enhancement

Color Image Equalization

For color images, options include:

Equalize each channel independently: Can cause color shifts

Convert to HSV/LAB, equalize intensity only: Preserves color relationships

• Convert to HSV
• Equalize V (value) channel
• Convert back to RGB

Equalize luminance in LAB space: Often best results

Computational Considerations

Histogram computation: O(N) where N is number of pixels

CDF computation: O(L) where L is number of intensity levels

Transformation: O(N) - apply lookup table to each pixel

Total complexity: O(N + L), effectively O(N) since typically L << N

Memory: O(L) for histogram and CDF arrays

Relationship to Probability Theory

Histogram equalization performs a probability integral transform:

Original distribution: PDF given by normalized histogram

Target distribution: Uniform distribution

CDF transformation: Maps any distribution to uniform

This is a fundamental technique in probability and statistics for generating uniform random variables from arbitrary distributions.

Where Histogram Equalization Shows Up

• Medical Imaging: Enhancing X-rays, MRIs, CT scans for better diagnosis

• Satellite Imagery: Improving contrast in remote sensing images

• Security Systems: Enhancing surveillance footage

• Document Scanning: Improving readability of scanned documents

• Photography: Automatic contrast adjustment in image editors

• Computer Vision Preprocessing: Normalizing images before feature extraction

• Microscopy: Enhancing biological specimens

• Astronomy: Processing telescope images with limited dynamic range

• Quality Control: Inspecting manufactured parts with varying lighting

• Face Recognition: Normalizing facial images for consistent input

Examples

Hints

1. Build a 256-bin histogram, then convert it into a cumulative count array.
2. Use the first positive cumulative count as the lower endpoint of the mapping.

Requirements

• Build a 256-bin histogram and its cumulative sum
• Use round() (not floor or ceil) when mapping to new values
• Handle the edge case where all pixels are the same value

Constraints

• Image has at least one pixel
• Pixel values are integers in [0, 255]
• Return a 2D list of integers with the same shape as input
• Time limit: 300 ms

Starter Code

def histogram_equalize(image: list) -> list:
    """
    Returns the histogram-equalized grayscale image.
    """
    # Write code here
    pass

Test Cases