Image Histogram Equalization

mediumFREEWhat is Computer Vision?Image ProcessingCV: Introduction to Computer Vision

Implement histogram equalization to enhance image contrast using NumPy.

Histogram equalization redistributes pixel intensities to achieve a more uniform histogram, improving contrast in images with concentrated intensity ranges.

Algorithm:

Compute histogram $h[i]$ = count of pixels with intensity $i$
Compute cumulative distribution function: $CDF[i] = \sum_{j=0}^{i} h[j]$
Normalize CDF to range [0, 255]: $CDF_{norm}[i] = \frac{CDF[i] - CDF_{min}}{(M \times N) - CDF_{min}} \times 255$
Map each pixel: $output[x,y] = CDF_{norm}[input[x,y]]$

Where $M \times N$ is the total number of pixels and $CDF_{min}$ is the minimum non-zero CDF value.

Edge cases:

If every pixel has the same intensity, the denominator $(M \times N) - CDF_{min}$ is 0; in that case return an image of the same shape filled with 255.
Fractional normalized values are truncated (rounded down) to integers.

Example

Input

image = [[50, 50], [50, 50]]

Output

[[255, 255], [255, 255]]

Reasoning

Input: image is a $2 \times 2$ grayscale image, each entry an intensity in $[0, 255]$ . Here all four pixels are 50, so $M \times N = 4$ .
Histogram: only intensity 50 occurs, so $h[50] = 4$ and $h[i] = 0$ for every other $i$ .
CDF: $CDF[i] = 0$ for $i < 50$ and $CDF[i] = 4$ for $i \ge 50$ . The smallest non-zero value is $CDF_{min} = 4$ .
Normalize: $CDF_{norm}[50] = \frac{4 - 4}{4 - 4} \times 255 = \frac{0}{0}$ , which is undefined. A single-intensity image has no range to stretch, so the edge-case rule applies and every pixel becomes 255.
Output: [[255, 255], [255, 255]], the same $2 \times 2$ shape, all integers.
Notice: with more than one intensity, the darkest present value always maps to 0 and the brightest to 255. For pixels 10, 20, 20, 30 the CDF values are 1, 3, 4, giving $\frac{0}{3}, \frac{2}{3}, \frac{3}{3}$ of 255, i.e. 0, 170, 255.

Constraints

image: 2D numpy array with values in [0, 255]
Return: Equalized image with same shape, values in [0, 255]
Output values should be integers

Learn this in

Image FormationCV Study Plan Image ProcessingCV Study Plan

More from CV: Introduction to Computer Vision

Sparse Matrix Operations for Imagesmedium Multi-Scale Feature Pyramidhard Implement Prewitt Edge Detectorhard Connected Components Labelinghard K-Means Color Quantizationmedium

Concept primer

Histogram equalization is a global contrast enhancement technique that operates purely on pixel intensities, not spatial structure. You treat the image as a collection of gray levels (0–255 for 8-bit), look at how often each intensity occurs (the histogram), and then remap these intensities so that their cumulative distribution becomes approximately linear. This spreads out frequently occurring intensities over a wider range, making dark regions lighter and bright regions darker where needed, thereby increasing overall contrast.

Mathematically, you build a cumulative distribution function (CDF) from the histogram and then use this CDF as a mapping function from old intensities to new ones. To avoid mapping all low intensities to zero, you subtract the smallest non-zero CDF and normalize by the total number of pixels, scaling the result back to the range $[0, 255]$ . The key idea: pixels with similar original intensities get mapped to more diverse output intensities, flattening the histogram and revealing more detail in low-contrast regions.

1. Background Knowledge (Key Concepts)

Histogram: For a grayscale image with intensities $i \in \{0,1,\dots,255\}$ , the histogram $h[i]$ is the count of pixels having value $i$ . This describes how intensities are distributed across the image.
CDF for intensities: The cumulative distribution function is

CDF[i] = \sum_{j=0}^{i} h[j]

It tells you how many pixels have intensity $\leq i$ . Normalizing this CDF gives a function that maps original intensities to new ones.

Equalization formula: Given total pixels $M \times N$ , and $CDF_{\min}$ as the smallest non-zero CDF value, the normalized CDF is

CDF_{\text{norm}}[i] = \frac{CDF[i] - CDF_{\min}}{(M \times N) - CDF_{\min}} \times 255

This produces a mapping into $[0,255]$ that you apply to every pixel.

2. Algorithm / Approach Pattern

This problem fits a common “precompute mapping, then apply it” pattern:

Analyze distribution: compute histogram and CDF from the input image.
Create a lookup table (LUT): use the CDF-based formula to compute a new intensity value for each possible input intensity (0–255).
Remap pixels via lookup: replace each pixel’s value with its mapped value from the LUT.

In NumPy terms, you:

Compute histogram over possible values.
Compute cumulative sum to get CDF.
Normalize CDF into 0–255.
Use the result as an indexing array to transform the whole image at once (vectorized).

3. Step-by-Step Strategy (Implementation Outline)

Assume input is a 2D NumPy array img with dtype uint8 and values in [0, 255].

Get image size and flatten if convenient

M, N = img.shape
total = M * N

Compute histogram $h[i]$

Use np.bincount or manual counting, with length 256:

hist = np.bincount(img.ravel(), minlength=256)

Compute CDF

cdf = hist.cumsum()

Find $CDF_{\min}$ (minimum non-zero CDF)

cdf_nonzero = cdf[cdf > 0]
cdf_min = cdf_nonzero # or cdf[cdf > 0].min()

Normalize CDF to [0, 255]

Follow the given formula, watch the types:

cdf_norm = (cdf - cdf_min) / (total - cdf_min) * 255
# Clip and cast to uint8
cdf_norm = np.clip(cdf_norm, 0, 255).astype(np.uint8)

Create the mapping (lookup table)

cdf_norm already has length 256, so it’s a LUT: mapping[i] = cdf_norm[i].

Apply mapping to the image

Use the image values as indices:

out = cdf_norm[img]

out is your equalized image.

4. Common Pitfalls

Integer vs float division: If you do the normalization with integer arrays, the division will truncate and most values may become 0. Ensure at least one operand is float:

cdf_norm = (cdf - cdf_min) * 255.0 / (total - cdf_min)

Forgetting to handle zero CDF: If you do not subtract $CDF_{\min}$ , many low intensities might map to 0, causing loss of detail in dark regions. Always use the minimum non-zero CDF as specified.
Not clipping or casting: The normalized CDF can contain out-of-range values due to numerical issues; always clip to [0, 255] and cast to uint8.
Assuming non-8-bit input: This formula assumes 8-bit grayscale (256 levels). If the image has a different range, you must adjust the number of bins and scale accordingly.
Using loops instead of vectorization: Looping over each pixel in Python is slow. Use the LUT with NumPy indexing (out = lut[img]) for efficiency.

5. Time & Space Complexity

Let $L$ be the number of gray levels (256 for 8-bit) and $N = M \times N$ be total pixels.

Time complexity:
Histogram computation: $O(N)$
CDF computation: $O(L)$
Mapping pixels using LUT: $O(N)$ Overall: $O(N + L) \approx O(N)$ for 8-bit images.
Space complexity:
Histogram, CDF, and LUT arrays: $O(L)$
Output image: $O(N)$ Additional over input: $O(N + L)$ , which is dominated by $O(N)$ for large images.

solution.py

Python 3.13

Test results