Contrast Limited Adaptive Histogram Equalization

mediumFREEPoint OperatorsEnhancementCV: Image Processing

Implement Contrast Limited Adaptive Histogram Equalization (CLAHE) for local contrast enhancement, which is an improvement over traditional histogram equalization. CLAHE is essential in image processing as it helps to enhance the contrast of images by dividing them into smaller regions, called tiles, and applying histogram equalization to each tile.

The process involves dividing the image into square tiles of tile_size $\times$ tile_size pixels (default $8 \times 8$ ) and applying histogram equalization to each tile. Tiles at the right/bottom border may be smaller if the image size is not a multiple of tile_size. This is done by computing the histogram of each tile, which represents the distribution of pixel intensities, and then clipping the histogram at a threshold to limit contrast amplification. The clipping threshold is typically set to a fraction of the total number of pixels in the tile, preventing over-amplification of noise in homogeneous regions.

Here are the key steps:

Divide the image into tiles of size $n \times n$ .
Compute the histogram of each tile, which represents the distribution of pixel intensities.
Clip the histogram at a threshold to limit contrast amplification. For a tile of $N$ pixels the threshold is $T = \text{clip\_limit} \cdot N / 256$ . The total clipped excess $E$ is shared equally among all 256 bins, adding $\lfloor E / 256 \rfloor$ to every bin.
Compute each tile's CDF from its clipped histogram and map that tile's pixels through it. Each tile is mapped independently, so this simplified version skips the bilinear blending between neighbouring tiles that full CLAHE uses to hide tile seams.

The mapping for intensity $v$ normalises the CDF to $[0, 255]$ , truncating to an integer:

\text{out}(v) = \left\lfloor \frac{\text{CDF}(v) - \text{CDF}_{\min}}{\text{CDF}_{\max} - \text{CDF}_{\min}} \times 255 \right\rfloor

where $\text{CDF}_{\min}$ is the smallest non-zero CDF value and $\text{CDF}_{\max}$ the largest. If a tile is uniform ( $\text{CDF}_{\max} = \text{CDF}_{\min}$ ), its pixels are left unchanged. Return a uint8 array with the same shape as the input.

H(i) = \sum_{x=1}^{n} \sum_{y=1}^{n} \delta(f(x,y) - i)

This technique is widely used in medical imaging to enhance the visibility of details in images.

Example

Input

image = 8×8 tile with rows of 100, 101, 102, 103, 100, 101, 102, 103
tile_size = 8
clip_limit = 2.0

Output

rows map to 0, 85, 170, 255, 0, 85, 170, 255

Reasoning

Input: one $8 \times 8$ tile ( $N = 64$ pixels) whose rows cycle through the grey levels 100, 101, 102, 103, so each level fills 16 pixels. With clip_limit $= 2.0$ the threshold is $T = 2.0 \cdot 64 / 256 = 0.5$ .
Clip: each of the four occupied bins drops from 16 to $0.5$ . The excess is $E = 4 \times 15.5 = 62$ , and $\lfloor 62 / 256 \rfloor = 0$ , so no bin gets anything back.
CDF: accumulating the clipped bins gives $0.5, 1.0, 1.5, 2.0$ at levels 100–103, so $\text{CDF}_{\min} = 0.5$ and $\text{CDF}_{\max} = 2.0$ .
Map: $\frac{\text{CDF}(v) - 0.5}{1.5} \times 255$ sends $100 \to 0$ , $101 \to 85$ , $102 \to 170$ , $103 \to 255$ . The rows therefore become 0, 85, 170, 255, 0, 85, 170, 255.
Notice: four grey levels only 3 apart get stretched across the full $0$ – $255$ range. Clipping made all four bins equal, so the output steps are evenly spaced. A tile holding a single grey level would come back unchanged instead.

Constraints

image: 2D grayscale array [0-255]
tile_size: Size of each tile (default 8)
clip_limit: Histogram clip limit (default 2.0)
Return: Enhanced image

Learn this in

Image FormationCV Study Plan

More from CV: Image Processing

Frequency Domain Filteringhard Separable Filter Optimizationhard Frequency Component Energyeasy Low-Pass Filter (Frequency)medium 1D DFTmedium

Concept primer

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.

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.

Step-by-Step Strategy

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

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

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.

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

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

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.

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.

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.

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.

solution.py

Python 3.13

Test results