Image Histograms

An image is a function $I(x, y)$ mapping pixel coordinates to intensity values, typically integers in $[0, L-1]$ with $L = 256$ for 8-bit grayscale images. The histogram of that image is the function

i.e., the number of pixels whose intensity equals $i$. Dividing by the total pixel count $N = \sum_i h(i)$ gives the normalized histogram $p(i) = h(i)/N$, which can be interpreted as an empirical probability mass function over intensity values — the probability that a randomly chosen pixel has value $i$. From the normalized histogram, the cumulative distribution function (CDF) is

a non-decreasing function that rises from $0$ to $1$ as $i$ sweeps from $0$ to $L-1$. The CDF is the workhorse behind histogram equalization: it tells you what fraction of the image is at or below a given brightness, and inverting it (approximately, since it's a step function) lets you remap intensities to achieve a target distribution. For color images, one must choose what to histogram. A common mistake is to compute a joint 3-D histogram over (R, G, B), which is expensive ($256^3$ bins) and usually too sparse to be useful directly. The standard practical approaches, building on Color Spaces, are: (1) compute three separate 1-D histograms, one per channel; (2) convert to a luminance/chrominance space such as YCbCr or HSV and histogram only the luminance (Y or V) channel, which corresponds to how humans perceive brightness and contrast; or (3) compute coarser joint histograms (e.g., 2-D chrominance histograms with fewer bins) for tasks like color-based object tracking or image retrieval. Choosing luminance-only equalization for color images is important — equalizing R, G, and B independently shifts hue and produces color casts, whereas equalizing only luminance preserves color while boosting contrast.

Building the histogram. The computation is a single linear pass: initialize an array of $L$ counters to zero, then for every pixel increment the counter corresponding to its intensity. ``` function COMPUTE_HISTOGRAM(image, L): h = array of L zeros for each pixel (x, y) in image: i = image[x, y] # intensity in [0, L-1] h[i] = h[i] + 1 return h ```

Normalizing and building the CDF. ``` function NORMALIZE_AND_CDF(h, N, L): p = array of L zeros C = array of L zeros running = 0 for i = 0 to L - 1: p[i] = h[i] / N running = running + p[i] C[i] = running # C[L-1] should equal 1.0 return p, C ```

Histogram equalization. The goal is to find a monotonic mapping $T: [0, L-1] \to [0, L-1]$ so that the output histogram is as close to uniform as possible — spreading intensities evenly across the full range to maximize contrast. The classical result from information theory is that the CDF itself, rescaled, is exactly this mapping:

``` function HISTOGRAM_EQUALIZE(image, L): h = COMPUTE_HISTOGRAM(image, L) N = total number of pixels p, C = NORMALIZE_AND_CDF(h, N, L) T = array of L zeros for i = 0 to L - 1: T[i] = round((L - 1) * C[i]) output = new image, same size as input for each pixel (x, y) in image: output[x, y] = T[image[x, y]] return output ```

Histogram matching (specification). Sometimes the goal is not a uniform histogram but to match a reference image's distribution — useful for making two photos of the same scene under different lighting comparable. ``` function HISTOGRAM_MATCH(image, reference, L): h1 = COMPUTE_HISTOGRAM(image, L) h2 = COMPUTE_HISTOGRAM(reference, L) _, C1 = NORMALIZE_AND_CDF(h1, sum(h1), L) _, C2 = NORMALIZE_AND_CDF(h2, sum(h2), L)

# For each source level, find the target level whose CDF is closest T = array of L zeros j = 0 for i = 0 to L - 1: while j < L - 1 and C2[j] < C1[i]: j = j + 1 T[i] = j output = new image, same size as input for each pixel (x, y) in image: output[x, y] = T[image[x, y]] return output ```

Otsu's thresholding. This algorithm uses the histogram alone to pick a threshold $t$ that splits the image into two classes (e.g., foreground/background) by maximizing the between-class variance — equivalently minimizing the within-class variance, since their sum is the fixed total variance of the image. ``` function OTSU_THRESHOLD(h, L): N = sum(h) total_mean = sum(i h[i] for i in 0..L-1) / N best_t = 0 best_between_var = -infinity w0 = 0 # weight (pixel count) of class 0, running sum0 = 0 # intensity sum of class 0, running for t = 0 to L - 2: w0 = w0 + h[t] if w0 == 0: continue w1 = N - w0 if w1 == 0: break sum0 = sum0 + t h[t] mean0 = sum0 / w0 mean1 = (N total_mean - sum0) / w1 between_var = w0 w1 * (mean0 - mean1)^2 # up to constant 1/N^2 if between_var > best_between_var: best_between_var = between_var best_t = t return best_t ``` The following diagram shows the full pipeline: an image feeds a histogram, which feeds a CDF, which feeds the equalization mapping, which produces a contrast-stretched output.

Time complexity. Building the histogram requires visiting every pixel exactly once: $O(N)$ time for $N = WH$ pixels, regardless of $L$. Computing the CDF and the equalization mapping $T$ is a single pass over $L$ bins: $O(L)$. Applying $T$ to every pixel is another $O(N)$ pass. Total: $O(N + L)$, and since $L = 256 \ll N$ for any realistic image, this is effectively linear in the number of pixels, with a tiny constant-size lookup table doing the heavy lifting. This is why histogram operations are so fast in practice — a 12-megapixel image is equalized with two linear scans and a 256-entry table, not per-pixel neighborhood computation.

Space complexity. The histogram itself needs $O(L)$ space (256 counters for 8-bit images), and the output image needs $O(N)$ space if not done in place. The histogram is thus a case of extreme compression: an $N$-pixel image is summarized in $L \ll N$ numbers.

Correctness of equalization — why the CDF is the right mapping. Treat pixel intensity as a continuous random variable $X$ with density $p_X$ and CDF $C_X$. A classical fact from probability theory (the probability integral transform) states that if $Y = C_X(X)$, then $Y$ is uniformly distributed on $[0,1]$, provided $C_X$ is continuous and strictly increasing. Proof sketch: for $y \in [0,1]$,

which is exactly the CDF of a uniform random variable. So mapping each pixel through its own CDF theoretically yields a perfectly flat (uniform) histogram — maximum entropy, hence maximum contrast in the information-theoretic sense. In practice intensities are discrete (integer levels), so $C(i)$ is a step function, not strictly increasing or continuous, and the transform is only approximate: bins with zero probability get "skipped over," and the output histogram is not exactly flat — it is a redistribution of the same pixel counts into fewer, taller bins with gaps, which still measurably increases the spread of intensities and hence contrast, just not perfectly uniformly. This is an honest limitation: exact equalization is a continuous-distribution ideal; discrete equalization is its best achievable discrete approximation, and it is idempotent-adjacent — applying it twice does not damage the image further because the second CDF is already nearly flat.

Correctness of Otsu's threshold. The total variance of intensities decomposes, for any binary split at threshold $t$ into classes $C_0 = \{0,\dots,t\}$ and $C_1 = \{t+1,\dots,L-1\}$, as

where $\sigma_{\text{between}}^2(t) = w_0(t)\, w_1(t)\, [\mu_0(t) - \mu_1(t)]^2$, with $w_0, w_1$ the class probabilities and $\mu_0, \mu_1$ the class means. Since $\sigma_{\text{total}}^2$ is fixed (independent of $t$), maximizing $\sigma_{\text{between}}^2(t)$ is equivalent to minimizing $\sigma_{\text{within}}^2(t)$ — Otsu's method computes the cheaper of the two, the between-class term, in a single $O(L)$ pass by maintaining running weights and sums, exactly as in the pseudocode. Because the histogram already summarizes all pixels, no re-scan of the image is needed once $h$ is built, giving total cost $O(N + L)$: one histogram pass plus one Otsu pass over 256 bins.

Tradeoffs. The histogram is spatially blind by construction: two images with wildly different content but the same intensity distribution produce identical histograms — a checkerboard and random static of the same mean and spread are indistinguishable to a histogram, which is why histogram-based methods are always paired with spatial techniques (Point Operations, edge detection, segmentation refinement) rather than used alone for anything beyond gross statistics.

Consider a tiny $4 \times 4$ grayscale image with $L = 8$ levels (values 0–7) instead of 256, so the arithmetic is traceable by hand:

$N = 16$ pixels. Counting occurrences of each level gives the raw histogram:

Normalize by $N = 16$ and accumulate the CDF:

Now compute the equalization mapping $T(i) = \mathrm{round}((L-1)\cdot C(i)) = \mathrm{round}(7 \cdot C(i))$:

Apply $T$ to every pixel of $I$:

Before equalization, the used range was $\{1,2,3,4\}$, spanning only 4 of 8 levels, clustered in the lower-middle. After equalization the used range is $\{1,4,6,7\}$, spread much closer to the full $[0,7]$ span — exactly the contrast-boosting effect predicted by the theory, even though (as expected for a discrete, small-sample case) the output is not perfectly uniform: level 4 still holds 6 pixels because levels 2 and 3's probability mass gets compressed into it. This illustrates precisely the "approximate, not exact" nature of discrete equalization discussed above. Now trace Otsu's method on the same histogram to find a threshold. Total mean:

Sweep $t$ from 0 to 6, tracking $w_0, \mu_0, \mu_1$, and $\sigma^2_{\text{between}} = w_0 w_1 (\mu_0-\mu_1)^2$:

The maximum between-class variance occurs at $t=1$ ($\approx 0.960$), so Otsu's method selects threshold 1: pixels with value $\le 1$ (the three 1's) form the background class, and everything $\ge 2$ forms the foreground class — a sensible split given that value 1 is visually the darkest, isolated cluster in this histogram.

The image histogram itself has no single named inventor — it is a direct application of the basic statistical concept of a frequency distribution, formalized in probability theory long before computers existed, to the pixel arrays that became analyzable once digital image processing matured in the 1960s–70s. The individuals below shaped the surrounding theory and the algorithms built on top of the histogram.

Histograms and histogram-derived operations are embedded in nearly every image pipeline in production today. Camera image signal processors (ISPs) use live histograms to drive auto-exposure and auto-contrast decisions in real time, adjusting sensor gain before a frame is even fully rendered. Medical imaging software (X-ray, CT, MRI viewers) relies on CLAHE-style adaptive equalization to reveal soft-tissue detail without saturating bone or air regions. Document scanning and OCR pipelines use Otsu's method as the default automatic binarization step to separate text from background before character recognition. Content-based image retrieval systems use color and intensity histograms (often combined with spatial pooling, since raw histograms ignore layout) as a fast, robust pre-filter before more expensive feature matching. Video encoders and scene-change detectors compare frame histograms to cheaply flag hard cuts. Finally, histograms underlie evaluation and calibration tools throughout the field: understanding intensity distributions is the direct prerequisite for the family of intensity remapping functions studied under Point Operations, and histogram comparison metrics build on the same distributional thinking used in classic Digital Images and Sampling analysis of dynamic range.

Ask the tutor: How would you adapt Otsu's method to find two thresholds for segmenting an image into three classes instead of two?