Setting and conventions
Global thresholding is the simplest segmentation rule. One number is chosen, and each pixel is labeled dark or bright by comparing its intensity with . The rule ignores pixel positions. It looks only at the intensity values, and so only at the histogram. This note states the finite-image model precisely, derives the objective used by Otsu's threshold rule, and records both what the rule guarantees and what it does not.
Definition 11.1.1
(Threshold classes and class statistics)
Let an image have pixels with real intensities . The ordering of the indices is arbitrary. A threshold defines
The equality convention matters: a pixel with goes to the low class . A threshold is admissible when both classes are nonempty. For an admissible we write and , so that and . We also define
All variances here are population-normalized: we divide by the number of terms, not by one less. This choice is part of the definition of the method, and the identities below depend on it. Nonemptiness is not a technicality either. If , then is undefined, and no formula involving it means anything.
Fitting two constants
Fix an admissible threshold. Suppose we model the image as piecewise constant in intensity: every pixel in is approximated by a constant , and every pixel in by . The squared error of this fit is
For a single class and any constant , write and expand:
The middle sum equals by the definition of . So the error is , which is minimized exactly at . The best two-constant fit therefore has error
where is the within-class variance. Choosing a threshold to minimize means choosing the dark/bright split whose best two-level approximation has the smallest sum of squared errors (SSE). That is the modeling content of the rule. It is a statement about fitting intensities. It says nothing about recognizing objects.
The variance decomposition
Theorem 11.1.2
(Mixture mean and variance decomposition)
For every admissible threshold ,
Writing for the between-class variance, this says .
Proof
(Splitting the finite sums by class)
Mean. Since and partition ,
Dividing by gives .
Variance. Apply the class-wise expansion from the previous section with . The cross term vanishes again because , so
Add over and divide by :
It remains to simplify the last two terms. From the mean identity and ,
Hence
which equals .
Proof X-ray
One expansion, used twice
The proof has one computational idea: the expansion of about the class mean. The previous section used it with an arbitrary constant to show that is the best constant; the proof uses it again with . Both times the cross term vanishes for the same reason, .
The hypotheses enter at identifiable points. Nonemptiness is needed before and exist at all. The partition property is used twice: to split into the two class sums, and to add the two class expansions into the single total . Population normalization is what makes the class terms read , so that dividing by produces exactly the weights that also appear in the mean identity. With divisors , the same sums would carry weights instead of , and the identity would no longer hold for .
The closing step converts two terms measuring distance to the global mean into one term measuring the distance between the class means. It uses only , which is the mean identity rearranged, and .
Since does not depend on , we have for every admissible . Minimizing and maximizing therefore select exactly the same thresholds. This equivalence holds only when , and are all computed from the same pixels with the same population normalization. Mixing in other normalizations destroys it.
Definition 11.1.3
(Otsu's threshold rule)
Among the admissible thresholds of an image, Otsu's threshold rule chooses one that maximizes the between-class variance , or equivalently minimizes the within-class variance .
Common mistake
(Sample variances break the equivalence)
Replacing by the sample variance looks harmless, but the weighted sum is not . Minimizing and maximizing can therefore select different thresholds, and is undefined whenever a class contains a single pixel. The exercise on the data below exhibits both effects. Every variance in the rule is population-normalized.
Which thresholds are genuinely different
Let be the distinct observed intensities. The partition depends only on which levels satisfy . Consider three cases:
- If , then is empty.
- If , then is empty.
- If for some , then is the set of pixels with intensity at most .
So the admissible thresholds form the interval , and they induce exactly distinct partitions . Every in the half-open interval gives the same labels. Because is a function of the partition, it is constant on each such interval.
Existence. If , the set of admissible partitions is finite and nonempty, so attains a maximum on it. The optimal threshold set is a union of intervals . When a single representative is needed, one may report , which is the largest dark level, or the midpoint of the interval. Either choice is a convention and has no further mathematical significance.
Constant images. If , so that every , then empties and empties . In this case no admissible threshold exists, and the rule is simply not defined. It is not true that the rule "returns ". A constant image contains no two-class split to choose.
Ties between distinct partitions. Different partitions can attain the same maximum. For the data the two candidates are and . Both have and , so . A tie-breaking rule must be stated explicitly, for instance "smallest ". Otherwise the output is not well defined.
Tied intensities. Pixels with equal intensity always fall in the same class, since no threshold separates equal numbers. Changing the convention to produces the same family of partitions, now indexed by . The reported threshold values change; the achievable labelings do not.
Worked example 11.1.4
(Four pixels with intensities )
Here , the levels are , , and
Candidate . The classes are and , so , and . Check: . The deviations in are , so and . Therefore
Candidate . The classes are and , so , and . Check: . The deviations in are , so and . Therefore
Both rows satisfy , as the theorem requires. The second partition wins. Every produces the optimal labels , so and are equally valid answers. The threshold is invalid because it leaves empty, and so is any .
The explorer below lets you edit an eight-level histogram and checks exactly on every candidate partition, including a tie, the constant image where no threshold is admissible, and a positive affine change of intensity.
Positive affine changes of intensity
Suppose the intensities are rescaled as with , as happens with a change of display units or a linear gain and offset.
Proposition 11.1.5
(Positive affine changes of intensity)
Let with . A threshold is admissible for if and only if is admissible for , and the two thresholds induce the same partition of the pixels. On every such partition, and are multiplied by . Consequently the optimal threshold set for is the image of the optimal threshold set for under .
Proof
(Order is preserved and every deviation scales by a)
Because , we have . The partitions available for are therefore exactly those available for , with threshold corresponding to .
On a fixed partition, the class means transform as . Every deviation equals , so each variance is multiplied by . The weights are unchanged. Hence and . Multiplying every score by the same positive constant preserves the ranking, so the maximizing partitions are identical and the optimal threshold intervals map by .
If , the order of intensities reverses and the dark and bright labels swap. Since is symmetric in the two classes, the same unordered split remains optimal, but the equality convention now attaches to the other side.
Computing the objective efficiently
Let level occur times. Form the prefix count and the prefix intensity sum
and set and , where . Then , and therefore
Only the indices are evaluated. This automatically omits the empty partitions, and it never splits tied intensities, because prefixes are taken over whole levels and never over individual sorted pixels.
Common mistake
(Scanning sorted pixels instead of intensity levels)
An implementation that sorts the pixels and evaluates the score after every pixel position, rather than after every distinct level, also scores splits that separate equal intensities. For , the cut after the first gives , and , yet no threshold produces this partition: every puts both pixels of value in . If such a split ever scored highest, the reported threshold would not reproduce the labels that were scored. Accumulate over the levels , or skip any position whose next sorted value is equal.
For arbitrary real data, sorting costs and the scan costs . For integer intensities in , building the histogram costs and the scan costs . For integer data, the numerator above is an integer; rational scores can be compared by cross-multiplication in exact arithmetic if the integer representation is sufficiently large to avoid overflow.
In floating point, computing variances as "mean of squares minus square of mean" can suffer cancellation when the values are large and nearly equal. The difference of sums above can also cancel when large intensities share a common offset. Centering values before accumulation can reduce this problem; stable summation and adequate precision may still be needed.
None of this provides a statistical guarantee. In exact arithmetic the procedure computes an optimizer of a stated finite objective, and that is all it does. Floating-point evaluation may change the comparison of close scores.
Relation to two-means clustering
For a fixed partition, is exactly the two-means cost, because each cluster center is optimally placed at its class mean. The difference lies in which partitions are searched. Two-means clustering allows any split of the pixels into two nonempty groups. The threshold rule allows only the ordered splits, in which every dark intensity lies below every bright one. The threshold rule is therefore an exact optimizer over a restricted family. Whether the unrestricted optimum always lies in that family is a separate question, which requires its own proof, and we do not use any such claim here.
No: for real intensities every optimal two-means partition is a threshold split, so the rule is the exact two-means optimum.
A natural next question
Can the best two-means split interleave intensities?
No: for real intensities every optimal two-means partition is a threshold split, so the rule is the exact two-means optimum.
No. At an optimal split the means differ, since equal means give , below any threshold split. A pixel strictly nearer the other mean could be moved with the centers fixed, lowering the cost. If pixels at the midpoint lay in both groups, moving one across keeps the fixed-center cost but shifts a mean, and recomputing that mean lowers the cost strictly. Either way optimality fails, so the groups are separated by the midpoint and the threshold search loses nothing.
What the histogram cannot see
Counterexample mode
Same histogram, different spatial structure
Consider two one-dimensional pixel rows:
Both rows contain two pixels of intensity and two of intensity . The only admissible partition is induced by . For both rows, , , , and .
The output labels are for row A and for row B. Row A has one adjacent pair with different labels, while row B has three. The scores are identical, because adjacency never enters . The rule contains no smoothness term, so no conclusion about shape, connectedness or boundaries can be drawn from it.
The next computations show the same limitation from other directions.
Worked example 11.1.6
(Noise turns a clean split into an alternating one)
Take an intended labeling of a row whose clean intensities are , and suppose the observed intensities are , so that . The three candidates give:
| Split | Weights | Class means | |
|---|---|---|---|
| and | |||
| and | |||
| and |
The middle split wins. Its labels are , which disagree with the intended labels at positions 2 and 5. The output also alternates from pixel to pixel, because nothing in the objective discourages it.
Worked example 11.1.7
(A single bright pixel outweighs two moderate ones)
Consider nine pixels: six at , two at , and one at . Suppose the intended foreground is all three nonzero pixels.
- The split gives .
- The split gives .
The rule therefore isolates the single bright pixel and assigns the two pixels at to the background, contrary to the intended labels. A small class far from the rest can dominate the objective through the factor .
Uneven illumination. Consider the row with intended labels background, object, background, object. Here the right half is lit more brightly. The intended object set corresponds to intensities , which is not of the form for any , because lies between and . No global threshold, optimal or otherwise, can produce these labels.
The threshold rule partitions intensities. It does not recognize objects, and it carries no guarantee of matching any particular intended segmentation.
Exercises
Exercise 11.1.8
(For the intensities , find all admissible thresholds, compute as a weighted sum of the class means, compute , and , and discuss ties.)
Foundation
Solution(3)
- 1
List the admissible thresholds
The levels are and , so the admissible thresholds are , and all of them induce the single partition . For the class is empty, and for the class is empty.
- 2
Compute the scores on the partition
Here , and , so . Both classes are constant, so and . The between-class variance is . Every deviation from is , so .
- 3
Interpret the ties
All tie, but trivially, since they give identical labels. There is no tie between distinct partitions, because only one partition exists. The value is the smallest possible.
Exercise 11.1.9
(Verify the affine invariance proposition on under .)
Foundation
Solution(3)
- 1
Transform the data and the candidate intervals
The transformed data are with . The candidate thresholds are and , the images of and under .
- 2
Score both candidates
For , the classes are with mean and , so . For , the class means are and , so .
- 3
Compare with the original scores
Both scores are the original ones multiplied by , so the same partition wins and the optimal interval is , the image of .
Exercise 11.1.10
(For , compare and using and using with . Comment on the overall optimum and on the pixels with value .)
Core
Solution(4)
- 1
Score the threshold
The classes are with and with . This gives , while .
- 2
Score the threshold
The classes are with mean and , and with . This gives , while .
- 3
Compare the rankings
Key step
The population criterion prefers , but the sample-normalized version prefers . The ranking flips, and the identity does not hold in general with replaced by .
- 4
Locate the overall optimum and the tied pixels
Over all candidates, the population optimum is , where and . There , so would require division by zero, and is undefined at the true optimum. The two pixels with value are inseparable: a split with one dark and one bright is not threshold-induced and is never scored.
Exercise 11.1.11
(Compare the images and . Then prove that permuting the pixel positions permutes the output labels in the same way.)
Core
Solution(3)
- 1
Score both images
Both images contain two pixels at and two at . The only admissible partition gives , and for both.
- 2
Count boundary edges
With 4-neighbor adjacency, a grid has four edges. In two edges join pixels with different labels, and in all four do. The scores are identical even though the boundary structure differs.
- 3
Prove the general statement
Let be a permutation of the indices and set . The multiset of intensities is unchanged, and , , and are symmetric functions of the multiset on each side of the threshold, so every threshold receives the same score and the optimal threshold set is unchanged. The label of pixel is , the original label of pixel . Spatial rearrangement is invisible to the rule.