Contrast Limited Adaptive Histogram Equalization

1. Background Knowledge

Histogram equalization is a point operation that remaps pixel intensities so that the output histogram is (approximately) uniform. For a grayscale image with intensities in $[0, L-1]$, you compute the histogram $h(k)$, its normalized version $p(k)$, then the cumulative distribution function (CDF) $c(k) =$\sum_{i=0}$^k p(i)$. The new value of a pixel with intensity $x$ is $y = (L-1) \cdot c(x)$. This is global: it uses the histogram of the whole image, so it can over-enhance noise and may wash out local details.

CLAHE (Contrast Limited Adaptive Histogram Equalization) makes this process local and controlled. The image is divided into small tiles; each tile gets its own histogram equalization, so local contrast is boosted where needed. To avoid excessive amplification of noise in nearly flat regions, CLAHE introduces a clip limit on histogram bins: if a bin count exceeds this limit, the excess is redistributed, effectively limiting the local contrast gain. Finally, because each tile has its own mapping, simple tiling would cause block boundaries. CLAHE removes these artifacts by bilinearly interpolating between neighboring tiles’ mappings for each pixel.

---

2. Algorithm / Approach

High-level pattern:

• Treat CLAHE as:
• “Local histogram equalization” per tile,
• With histogram clipping + redistribution,
• Combined via spatial interpolation instead of hard tile borders.
• Precompute, for each tile, a lookup table (LUT) of size $L$ (number of gray levels) that maps input intensity $\rightarrow$ output intensity in that tile.
• For each pixel:
• Find the 4 surrounding tiles,
• Read the 4 LUT outputs for its intensity,
• Combine them with bilinear interpolation based on the pixel’s relative position.

Implementation-wise, this is a two-phase algorithm:

• Phase 1: per-tile preprocessing and LUT computation.
• Phase 2: per-pixel interpolation using those LUTs.

---

3. Step-by-Step Strategy

Assume a single-channel (grayscale) image, height $H$, width $W$, and an $n_r \times n_c$ grid of tiles.

1. Define tiling

• Choose number of tiles in rows and cols, e.g. $n_r = n_c = 8$.
• Tile size:
• tile_h = ceil(H / n_r)
• tile_w = ceil(W / n_c)
• For each tile $(i, j)$, compute its pixel bounds (handle last tiles that may be smaller).

2. Compute histogram and clip per tile For each tile $(i,j)$:

• Initialize histogram array hist[L] = 0.
• Loop over pixels in that tile and increment hist[intensity].
• Compute clip limit (depends on problem statement; commonly proportional to average bin count):
• Example idea (not code): clip_limit = clip_factor * (tile_pixel_count / L)
• Clip each bin:
• If hist[k] > clip_limit, accumulate excess: excess += hist[k] - clip_limit, and set hist[k] = clip_limit.
• Redistribute excess uniformly over all bins:
• add = excess / L, remainder = excess % L.
• Add add to all bins, then distribute 1 extra to remainder bins if you want exact conservation.
• Result: a clipped & redistributed histogram.

3. Build CDF and LUT per tile For tile $(i,j)$:

• Compute cumulative histogram: cdf[k] = sum_{t=0..k} hist[t].
• Normalize to get mapping:
• Let min_cdf = first non-zero cdf (optional, but helps keep dark background dark).
• Total pixels in tile: N_tile.
• For each intensity $k$:
• $$\text{lut}$[k] =$\text{round}\left( \frac{cdf[k] - min_cdf}{N_tile - min_cdf}\cdot (L-1) \right) (clamp to $[0, L-1]$).
• Store lut in a tile_LUT[i][j] array of size $(n_r, n_c, L)$.

4. Prepare for interpolation

• For a pixel at coordinates $(y, x)$:
• Compute its tile coordinates in continuous form:
• fy = y / tile_h (float), fx = x / tile_w.
• ty = floor(fy), tx = floor(fx) (tile indices).
• Clamp ty to [0, n_r-1], tx to [0, n_c-1].
• Neighboring tiles:
• ty1 = min(ty+1, n_r-1), tx1 = min(tx+1, n_c-1).
• Local fractional positions inside the tile grid:
• dy = fy - ty, dx = fx - tx in $[0,1]$.

5. Bilinear interpolation of LUT outputs For each pixel:

• Let its original intensity be v.
• Get 4 LUT-mapped values:
• v00 = tile_LUT[ty][tx][v]
• v01 = tile_LUT[ty][tx1][v]
• v10 = tile_LUT[ty1][tx][v]
• v11 = tile_LUT[ty1][tx1][v]
• Compute bilinear interpolation:
• First in x:
• top = v00 * (1 - dx) + v01 * dx
• bottom = v10 * (1 - dx) + v11 * dx
• Then in y:
• out = top * (1 - dy) + bottom * dy
• Round and clamp out to [0, L-1] and write to output image.

6. Edge conditions

• On borders (first/last row/column of tiles), the set of 4 tiles may collapse to 2 or 1 because ty1 == ty or tx1 == tx; bilinear interpolation naturally reduces to linear or constant in those cases.

---

4. Common Pitfalls

• Wrong clip limit interpretation:
• Using an absolute clip count without accounting for tile area and bin count can make clipping too aggressive or ineffective.
• Not redistributing the clipped excess:
• Just clipping without redistribution violates histogram mass conservation and changes brightness unintentionally.
• Block artifacts:
• Applying each tile’s LUT directly (no interpolation) will cause clear seams between tiles.
• Incorrect interpolation weights (dx, dy relative to pixel vs. tile centers) can still produce visible artifacts.
• Off-by-one / boundary errors:
• Incorrect tile bounds or rounding can leave pixels unprocessed or processed by the wrong tile.
• Ignoring image type and range:
• Make sure you know if intensities are 0–255 (uint8) or 0–1 (float) and build histograms/LUTs accordingly.
• CDF normalization issues:
• If all pixels in a tile have the same intensity, N_tile - min_cdf can go to zero; in that case, mapping should be constant.

---

5. Time & Space Complexity

Let:

• $H, W$ = image height and width,
• $N = H \cdot W$,
• $L$ = number of gray levels (usually 256),
• $T = n_r \cdot n_c$ = number of tiles,
• Average tile size $\approx N / T$.

Time complexity

• Per-tile histogram computation: each pixel visited once → $O(N)$.
• Per-tile clipping, redistribution, and CDF + LUT: $O(L)$ per tile → $O(T \cdot L)$.
• Per-pixel interpolation (constant work per pixel): $O(N)$.

Overall:

• $O(N + T \cdot L)$. With typical parameters (small $T$, $L=256$), this is effectively linear in the number of pixels: $O(N)$.

Space complexity

• Image + output: $O(N)$.
• Tile LUTs: $T \cdot L$ entries → $O(T \cdot L)$.
• Temporary histograms/CDF: $O(L)$.

Overall: $O(N + T \cdot L)$; in practice dominated by $O(N)$ memory for the images.