Image Thresholding

Image thresholding is a pointwise transformation that maps a grayscale image $I(x,y)$ to a binary image $B(x,y) \in \{0, 1\}$ using a decision rule based on intensity alone:

Here $T$ is the threshold. When $T$ is a single scalar applied uniformly across the image, this is global thresholding. When $T$ becomes a function $T(x,y)$ that varies with position — typically computed from statistics of a local neighborhood around each pixel — this is adaptive or local thresholding. The central assumption behind global thresholding is that the image's histogram is bimodal: pixels cluster into two populations (say, dark text and light paper), each forming a peak, separated by a valley. The threshold should sit in that valley. Otsu's method, introduced by Nobuyuki Otsu in 1979, formalizes "sitting in the valley" as an optimization problem: choose $T$ to maximize the separation between the two resulting pixel classes, measured by between-class variance, without needing to know the true distributions in advance. Global thresholding fails when illumination is uneven — a single valley in the histogram does not exist, or worse, the same object intensity appears bright in one image region and dark in another due to a shadow or gradient light source. Adaptive thresholding solves this by computing a local threshold from a window around each pixel, most commonly the local mean or a Gaussian-weighted local mean, minus a constant offset $C$ to bias toward the darker class. This lets the decision surface bend and follow illumination changes across the image, at the cost of more computation and new tunable parameters (window size, offset).

Step 1: Build the histogram. For an 8-bit grayscale image with $L = 256$ possible intensities, compute $h[i]$, the count of pixels with intensity $i$, for $i = 0, \dots, L-1$. This requires one pass over all $N$ pixels.

Step 2: Global fixed threshold (simplest case). If a threshold is known in advance — from calibration, a fixed scanner setting, or domain knowledge — apply it directly: ``` function GLOBAL_THRESHOLD(image, T): for each pixel (x, y) in image: output(x, y) = 1 if image(x, y) >= T else 0 return output ``` This is $O(N)$ and needs no histogram. It is fragile: if lighting shifts, $T$ must be re-tuned by hand.

Step 3: Iterative (isodata) threshold selection. A simple automatic method starts with a guess and refines it by alternately splitting the histogram and recomputing the midpoint of the two class means: ``` function ISODATA_THRESHOLD(histogram, levels): T = mean intensity of entire histogram # initial guess repeat:

# split pixels into two classes by current T mu_low = mean intensity of pixels with value < T mu_high = mean intensity of pixels with value >= T T_new = (mu_low + mu_high) / 2 if |T_new - T| < epsilon: break T = T_new return T ``` This converges because each iteration moves $T$ toward the midpoint of two means that themselves depend on $T$ — a fixed-point iteration that is monotone and bounded, hence convergent for well-behaved (bimodal) histograms.

Step 4: Otsu's method — the standard automatic global threshold. Otsu's method treats every possible threshold $t \in \{0, \dots, L-1\}$ as a candidate split of the histogram into class $C_0$ (intensities $\le t$) and class $C_1$ (intensities $> t$), and picks the $t$ that maximizes the between-class variance:

where $\omega_0(t), \omega_1(t)$ are the class probabilities (fraction of pixels in each class) and $\mu_0(t), \mu_1(t)$ are the class means. The key algorithmic trick is that all four quantities can be updated incrementally as $t$ sweeps from $0$ to $L-1$, using cumulative sums, so the entire search is a single linear pass over $L$ gray levels rather than $L$ independent full passes over $N$ pixels. ``` function OTSU_THRESHOLD(histogram, L): N = sum(histogram) # total pixel count sum_total = Σ_{i=0}^{L-1} i histogram[i] w0 = 0.0 # running weight (probability) of class 0 sum0 = 0.0 # running weighted intensity sum of class 0 best_var = -infinity best_t = 0 for t = 0 to L - 1: w0 += histogram[t] / N if w0 == 0: continue w1 = 1 - w0 if w1 == 0: break # no pixels left in class 1 sum0 += t histogram[t] mu0 = sum0 / (w0 N) mu1 = (sum_total - sum0) / (w1 N) between_var = w0 w1 (mu0 - mu1)^2 if between_var > best_var: best_var = between_var best_t = t return best_t ```

Step 5: Apply the chosen threshold. Once $T$ (fixed, isodata, or Otsu) is known, apply `GLOBAL_THRESHOLD` above — an $O(N)$ pass.

Step 6: Adaptive thresholding for uneven illumination. Instead of one global $T$, compute a local threshold per pixel from a window $W$ centered at $(x,y)$: ``` function ADAPTIVE_THRESHOLD(image, window_size, C): integral = COMPUTE_INTEGRAL_IMAGE(image) # for O(1) window sums half = window_size / 2 for each pixel (x, y) in image: local_mean = WINDOW_MEAN(integral, x, y, half) T_local = local_mean - C output(x, y) = 1 if image(x, y) >= T_local else 0 return output ``` The integral image (summed-area table) is what keeps this efficient: precomputing it in one $O(N)$ pass lets any rectangular window sum be fetched in $O(1)$ via four array lookups, so the whole adaptive pass remains $O(N)$ regardless of window size. A Gaussian-weighted variant replaces the box mean with a weighted local mean, trading a small constant-factor slowdown (or a separable convolution, still $O(N)$ for fixed kernel support) for smoother, less blocky thresholds.

Time complexity. Building the histogram requires one pass over all $N$ pixels: $O(N)$. Otsu's search sweeps the $L$ possible thresholds once, maintaining running sums $w_0$ and $\text{sum}_0$ incrementally in constant time per level, giving $O(L)$ for the search. Since $L$ is a small fixed constant (256 for 8-bit images, independent of image size), the dominant cost is $O(N)$ for the histogram build plus $O(N)$ for the final pixelwise apply, so total time is $O(N + L) = O(N)$ for any practical image where $N \gg L$. This is the same asymptotic class as simply reading the image once — thresholding is essentially free beyond I/O. A naive implementation that recomputes $\omega_0, \omega_1, \mu_0, \mu_1$ from scratch for every candidate $t$ costs $O(L^2)$ or $O(L \cdot N)$; the incremental cumulative-sum formulation is what brings this down to $O(L)$, and is the reason Otsu's method is practical for real-time use.

Space complexity. The histogram needs $O(L)$ space. The output binary image needs $O(N)$ space (or $O(N/8)$ if packed as bits). No auxiliary structures beyond a few running scalars are needed for Otsu's search itself. For adaptive thresholding, computing the integral image costs $O(N)$ time and $O(N)$ space, and after that every window-mean query is $O(1)$ regardless of window size $w$, so the total remains $O(N)$ rather than the naive $O(N w^2)$ of recomputing each window sum from scratch.

Correctness of Otsu's method. The argument rests on a classical variance decomposition. For any split of the pixel population into two classes with the global variance $\sigma_T^2$ fixed (a property of the image, independent of $t$), it is a standard fact from statistics that

where $\sigma_W^2(t)$ is the within-class variance (weighted average of each class's internal variance) and $\sigma_B^2(t)$ is the between-class variance defined above. Because $\sigma_T^2$ does not depend on $t$, maximizing $\sigma_B^2(t)$ over $t$ is exactly equivalent to minimizing $\sigma_W^2(t)$ over $t$. So Otsu's method, though phrased as "maximize between-class separation," is simultaneously performing the more intuitive operation "minimize the spread inside each class" — the threshold that makes each class as internally homogeneous as possible. This equivalence is not a heuristic approximation; it follows algebraically from the total-variance decomposition and holds for every histogram, bimodal or not.

Correctness of the incremental update. The class weight $\omega_0(t) = \sum_{i \le t} h[i]/N$ and weighted sum $\text{sum}_0(t) = \sum_{i \le t} i \cdot h[i]$ both satisfy simple recurrences,

so each can be updated in $O(1)$ from the previous value, which is exactly what the pseudocode does; this is why the $L$-level sweep costs $O(L)$ total rather than $O(L)$ per level.

Honesty about tradeoffs. Otsu's method is optimal only under its own objective — it finds the global optimum of between-class variance in $O(L)$ time, which is provably correct as a maximization, but that objective is a good proxy for "correct segmentation" only when the histogram is genuinely (or approximately) bimodal with comparable class sizes and variances. It can pick poor thresholds when one class vastly outnumbers the other, when noise creates spurious peaks, or when the true separation is not variance-based (e.g., textured regions with same mean, different texture). Adaptive thresholding trades this global optimality for local robustness: it has no single "correct" objective being maximized, and its quality depends entirely on choosing window size and offset $C$ appropriately for the spatial scale of both the object and the illumination gradient.

Consider a small 8-level (toy) grayscale image so histogram counts are easy to track by hand. Suppose the histogram (gray levels 0–7, $L=8$) over $N=20$ pixels is:

This is bimodal: a dark cluster around levels 0–2 (10 pixels) and a bright cluster around levels 5–7 (10 pixels), separated by an empty valley at levels 3–4. $\text{sum\_total} = \sum i \cdot h[i] = 0(2)+1(5)+2(3)+3(0)+4(0)+5(2)+6(4)+7(4) = 0+5+6+0+0+10+24+28 = 73$ Trace `OTSU_THRESHOLD`, tracking $w_0$, $\mu_0$, $\mu_1$, and $\sigma_B^2(t)$ at each candidate $t$:

The loop stops before $t=7$ since $w_1$ would hit 0. The maximum $\sigma_B^2(t) = 6.503$ occurs at both $t=2$ and $t=3$ (a tie, since $h[3]=0$ contributes nothing); the algorithm as written keeps the first maximum found (strict `>` comparison), so `best_t = 2`. This correctly lands the threshold in the empty valley between the two clusters, at the boundary of the dark class — exactly where a human would draw the line. Any $t$ in $\{2, 3, 4\}$ produces an identical binary segmentation here, since no pixels exist at levels 3 or 4; the tie is a harmless artifact of the empty valley, not an error. For contrast, imagine a second scene: the same object but photographed with a light gradient, so the left half of the image is globally brighter by +2 levels. A single global $T=2.5$ (roughly the Otsu cutoff above) would now misclassify part of the left-half background as foreground, because "bright due to lighting" and "bright due to being foreground" become indistinguishable to a global rule. This is precisely the scenario adaptive thresholding is designed for: a local window mean on the left half would sit near the local background level even though it is elevated, and subtracting the local mean (minus $C$) recovers the correct local decision boundary that a single global $T$ cannot express.

Otsu's method is named for the Japanese electrical engineer who formalized the variance-maximization criterion still taught as the default automatic threshold selector today.

Document scanning and OCR pipelines use adaptive thresholding as a mandatory first stage: scanned pages rarely have uniform illumination, and OCR accuracy depends heavily on clean binarization before character segmentation. Barcode and QR code readers apply Otsu-style or adaptive thresholding to convert camera frames into clean black-and-white modules under variable lighting from phone flashes or ambient light. Medical and microscopy imaging pipelines use thresholding to isolate cells, nuclei, or tissue regions from background stain, often as a preprocessing step before connected-component counting. Industrial machine vision systems on assembly lines threshold parts against a controlled background for fast defect detection, exploiting the $O(N)$ speed of thresholding for high-throughput inspection. Thresholding is also embedded inside larger pipelines: it commonly feeds directly into Region Growing Segmentation as a seed-selection or homogeneity criterion, and its binary output is almost always cleaned with Morphological Operations like erosion, dilation, opening, and closing before any downstream shape or contour analysis. Even modern deep-learning segmentation systems sometimes use adaptive thresholding on network confidence maps to convert soft probability outputs into hard binary masks.

Ask the tutor: How would you extend Otsu's method to automatically choose two thresholds for a three-class (dark/mid/bright) image?