📘

Image Histogram Equalization

EasyPreprocessing, Array/Math 📚 Computer Vision 1

Histogram equalization is a technique used in image preprocessing to modify the intensity values such that the distribution of pixel intensities is approximately uniform. This process is useful for increasing contrast by making sure all moments of the intensity values take predefined values.

The process involves two main steps:

Compute the Cumulative Histogram (CDF): Calculate the cumulative proportion of pixels $c_k$ for each intensity level $k$ by normalizing the cumulative sum of the histogram $h$ by the total number of pixels $N$ :

$c_k = \frac{\sum_{l=1}^{k} h_l}{N}$

Apply Transformation: Map the original intensity value $p_{ij}$ to the new intensity value $x_{ij}$ using the calculated cumulative proportion and the maximum intensity value $K$ :

$x_{ij} = K \cdot c_{p_{ij}}$

Your task is to take a flat 1D array representing grayscale pixel intensities (where the maximum possible intensity $K$ is 10) and return the transformed array after applying histogram equalization.

Example:

Input:

intensities = [2, 3, 3, 5, 5, 5, 7, 7, 7, 7]
max_k = 10
# Total pixels N = 10

Output:

[1, 3, 3, 6, 6, 6, 10, 10, 10, 10]

Reasoning:

Calculate histogram counts for each intensity level
Compute CDF: $c_k = \frac{\text{cumulative count}}{N}$ $c_{k} = \frac{cumulative count}{N}$
- $c_2 = 0.1$ , $c_3 = 0.3$ , $c_5 = 0.6$ , $c_7 = 1.0$
Apply transformation: $x_{ij} = K \cdot c_{p_{ij}}$ $x_{ij} = K \cdot c_{p_{ij}}$
- Intensity 2 → $10 \times 0.1 = 1$
- Intensity 3 → $10 \times 0.3 = 3$
- Intensity 5 → $10 \times 0.6 = 6$
- Intensity 7 → $10 \times 1.0 = 10$

Constraints:

The input array contains positive integer intensity values
The maximum possible intensity $K$ is 10
The output array elements must be rounded down to the nearest integer (floor)

More from Computer Vision 1

Semi-Global Matching Cost AggregationHard Compute Depth Map from DisparityMedium Stereo Rectification CheckEasy Oriented BRIEF DescriptorHard Gaussian Scale SpaceMedium

1. Background Knowledge

Histogram equalization transforms an image's pixel intensities to achieve a uniform intensity distribution, enhancing contrast by spreading out clustered values across the full range. For grayscale images, it uses the histogram $h_k$ (frequency of intensity $k$ ) and cumulative distribution function (CDF) $c_k = \frac{$ \sum_{l=0}^{k} $h_l}{N}$ , where $N$ is total pixels, to map original intensity $p$ to $x = \lfloor K \cdot c_p \rfloor$ (here $K=10$ ). This assumes discrete intensities (0 to $K$ ) and flooring for integer output. Prerequisites: basic array operations, counting frequencies, prefix sums for CDF.

2. Algorithm Approach

Standard global histogram equalization (HE) computes the histogram, normalizes to CDF, and applies a monotonic mapping. Variants like bi-histogram equalization (BBHE) split the histogram at mean/median to preserve brightness, but basic HE suffices here. For 1D arrays with small $K=10$ , use array-based histogram (size 11) and lookup table for transformation—efficient and exact.

3. Step-by-Step Strategy

Compute histogram: Create array hist[0..10] where hist[k] = count of pixels == k.
Build CDF: cdf = hist/N, then cdf[k] = cdf[k-1] + hist[k]/N for $k=1$ to 10.
Scale and floor: For each original pixel $p$ , new value = $\lfloor 10 \cdot$ \text{cdf} $[p] \rfloor$ .
Transform array: Map all pixels using CDF lookup; return new array.

Pseudocode:

def histogram_equalization(pixels, K=10):
 N = len(pixels)
 hist = * (K + 1)
 for p in pixels:
 hist[p] += 1
 cdf = [0.0] * (K + 1)
 cdf = hist / N
 for k in range(1, K + 1):
 cdf[k] = cdf[k-1] + hist[k] / N
 result = []
 for p in pixels:
 result.append(int(K * cdf[p])) # floor division
 return result

4. Common Pitfalls

Off-by-one indexing: Ensure histogram covers 0 to 10; intensities are positive integers (assume ≥0 per constraints).
Floating-point precision: Use float for CDF, but floor to int for output—avoid rounding up.
Empty bins: CDF handles zeros naturally (plateaus), preserving monotonicity.
Normalization: Divide by exact $N$ , not approximate; skip if $N=0$ (edge case).
Input validation: Assume valid positives ≤10; no clamping needed.

5. Time & Space Complexity

Time: $O(N + K)$ —single pass for histogram ( $O(N)$ ), CDF build ( $O(K)$ ), transformation ( $O(N)$ ). With $K=10$ , effectively $O(N)$ .
Space: $O(N + K)$ —input/output arrays plus small histogram/CDF. Optimal for streaming if in-place possible.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.