Image Histogram Equalization

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:

1. Analyze distribution: compute histogram and CDF from the input image.
2. Create a lookup table (LUT): use the CDF-based formula to compute a new intensity value for each possible input intensity (0–255).
3. 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].

1. Get image size and flatten if convenient

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

2. Compute histogram $h[i]$

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

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

3. Compute CDF

cdf = hist.cumsum()

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

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

5. 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)

6. Create the mapping (lookup table)

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

7. 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.