An image histogram counts how often each intensity occurs, but ignores where those pixels are. A cumulative histogram can define a monotone intensity map that redistributes levels. The discrete calculation is useful precisely because its limitations are visible: repeated input values cannot be split by a single deterministic pointwise map.
From counts to a monotone map
Definition 12.1.1
(Equalization map of a discrete histogram)
Take a nonempty grayscale image with pixels and integer levels , where . Let count pixels at level , and define
Here is the empirical cumulative distribution. The equalization map sends each pixel of level to the output level , and the output count of level is the number of pixels sent to .
Proposition 12.1.2
(Equalization preserves order and pixel count)
For the map above:
- is an integer with , and ;
- if then ;
- for every output level , and .
Proof
(Monotonicity from nonnegative counts)
Since each , the partial sums are nondecreasing in . Since , we get , hence for all . Therefore , and because is an integer the floor is an integer in ; at it equals .
The floor function is nondecreasing, so a composition of the nondecreasing with multiplication by and then the floor is nondecreasing. Finally each of the pixels at level lands in output level , so output level receives exactly the pixels from the input levels with . The sets partition , so .
Proof X-ray
What the proof does and does not give
The hypotheses are used in separate places. The nonnegativity gives monotonicity of ; the total gives and keeps inside the output range; is needed only so that is defined. The one non-obvious point is the last line of the proof: the output counts are obtained by summing input counts over the fibers of , so the proof computes but never says it equals .
That is why the conclusion is only conservation of pixels. Monotonicity lets different levels merge, because the floor is not injective, and a level that is not in the image of has . Nothing in the argument makes the output histogram flat: discrete mass at one input level can be larger than , and it moves as a block.
This unit explicitly uses the floor rule above. Other implementations use different rounding or subtract a minimum nonzero cumulative value before scaling; they can produce different results, and the latter needs a separate constant-image rule when its denominator vanishes. Equal input levels remain equal under , and the order of different levels cannot reverse, although distinct levels can merge.
Four pixels, four levels
Worked example 12.1.3
(Equalizing a four-pixel image)
Let , , and . Then
The output counts are : level 1 is unused, and the two pixels originally at level 1 both become level 2. There is no pixel at input level 2, so its mapped value does not itself contribute a count. The output histogram is not uniform even though the operation uses a cumulative distribution.
Common mistake
(Expecting a flat output histogram)
Equalization does not make the output counts equal. In the example above the output counts are , not . Level 1 stays empty because takes the mass of the input level that had two pixels. Likewise, an input level with zero pixels (level 2 here) contributes nothing to the output counts, even though is defined.
Worked example 12.1.4
(A uniform histogram and a constant image)
Let and with . Then and , the identity map: a histogram that is already flat is left unchanged.
For a constant image with every one of pixels at level , , so and . All five pixels move to level ; the whole image is mapped to one output level, which is the boundary behavior used again below.
Matching a target histogram
Definition 12.1.5
(Quantile matching map)
Suppose a target probability histogram on the same output levels is , with and . Set , and define
Each pixel of level is sent to the output level .
Proposition 12.1.6
(The quantile map is well defined and monotone)
The set in the definition of is nonempty for every , and implies .
Proof
(Nonempty set, nested sets)
Because and , the level belongs to the set, so the minimum exists. If , then , so every with also satisfies . The set for is therefore contained in the set for , and the minimum of a subset is at least the minimum of the set: .
Mapping through is one precise histogram-matching rule. It need not reproduce the target exactly because an input intensity's mass moves together.
Worked example 12.1.7
(Matching the four-pixel image to a target)
For the four-pixel source above, take target probabilities , with cumulative values . Then , and the output counts exactly match that particular target. Exact matching here is an example, not a general guarantee.
Common mistake
(Assuming matching reproduces the target)
Use the same source, with , and the target , so . Then because , while because the first with is . The output counts are , not the target's : the two pixels at input level 1 move together and cannot be split between level 0 and level 3.
Counterexample mode
A tied population cannot always be redistributed
If all input pixels have the same level, every deterministic pointwise intensity map sends them to one output level. It cannot produce a target that assigns positive mass to two distinct levels. Under the floor equalization rule above, the one occupied input level has , so every pixel becomes . Spatial tie-breaking or randomization could split tied pixels, but that is a different algorithm with different properties.
Computing counts, the cumulative map and the mapped image costs arithmetic operations with histogram storage, excluding the input and output images. This is a grayscale intensity operation; independently mapping color channels can alter color relationships. A global histogram alone contains no spatial information, so a flatter histogram does not by itself guarantee better local contrast or visual quality.
Exercises
Quick check
(For the four-pixel equalization example, how many output pixels have level 2?)
Add the input counts over the levels with .
Solution · Answer
Two: , and .
Quick check
(Can a monotone map reverse the order of two input intensities?)
Compare and for .
Solution · Answer
No, though it can map them to the same level.
Quick check
(With all input pixels at one intensity, can the stated deterministic map give a two-level output histogram?)
Each input level has one image under the map.
Solution · Answer
No; all tied inputs share one output value.
Quick check
(Why does the target quantile set always contain a level?)
Compare with .
Solution · Answer
, so the level always qualifies.
Exercise 12.1.8
(A six-pixel image has levels and counts . Find the equalization map and the output counts.)
Core
Use .
Solution(3)
- 1
Compute the cumulative distribution
- 2
Apply the floor rule
Because: with .
- 3
Collect the output counts
Output level receives pixels, output level receives pixels, and levels and are empty. The output counts are , which sum to .