Two questions about the same image
A denoising model asks for a real intensity at each pixel. A binary segmentation instead asks which pixels belong to an object. These are different outputs, but a useful connection is hidden in the boundary of a level set. If an edge joins pixels whose intensities are and , it crosses the level precisely for . Its contrast is therefore the total length of the interval of levels it crosses. Adding this observation over edges turns total variation into an integral of boundary costs.
Definition 2.4.1
(Graph total variation and cut)
Let be a finite undirected graph with nonempty vertex set , with a nonnegative weight for each edge . For and , define
Each undirected crossing edge is counted once. An empty edge set or zero edge weights are allowed. Write , using a strict inequality consistently.
No geometric grid, smoothness or probabilistic assumption is needed for the finite statements below.
Theorem 2.4.2
(Finite graph coarea formula)
For every ,
The integrand is a bounded step function with bounded support (unless it is identically zero), so this is an ordinary finite integral.
Proof
(Edge by edge, as an integral over levels)
For any two real numbers , the indicators and differ exactly on the half-open interval between and . Consequently
Apply this identity to each edge and exchange the finite sum and integral. At any fixed , the sum of weighted absolute indicator differences is exactly . Endpoint choices change at most finitely many levels and do not change the integral. This proves the identity.
Common mistake
(Counting each crossing edge twice)
Summing over ordered pairs with and is correct, but summing over ordered pairs counts every crossing edge twice, and the same happens to if it is summed over ordered pairs. If only one of the two quantities is doubled, the coarea identity appears to fail by a factor of two. Both sums here run over undirected edges, each counted once.
Worked example 2.4.3
(Coarea on a weighted triangle)
Take vertices , all three edges, weights , , , and . Then
For the set is and for it is empty; both have cut zero. For , , whose crossing edges are and , so the cut is on an interval of length . For , , whose crossing edges are and , so the cut is on an interval of length . The integral is . The edge crosses every level in , which is exactly its contribution ; the graph need not be a chain.
A single denoised image supplies many optimal cuts
Fix data and . Consider the quadratic TV problem
Its continuous coercive objective is strictly convex, so a unique minimizer exists.
Definition 2.4.4
(Level- binary objective)
For a level , define the binary objective
Selecting a pixel with reduces the data term; a boundary between selected and unselected pixels costs edge weight.
This binary objective depends on : a threshold of the denoised image is not claimed to minimize an arbitrary segmentation energy.
Theorem 2.4.5
(Threshold optimality)
For every real , the strict superlevel set minimizes over all subsets of . The minimizer of need not be unique. Sets obtained as varies are nested, because they come from the same .
Proof
(An edge certificate tight on every superlevel boundary)
Orient every edge once and define on the oriented edge . The graph-TV optimality certificate gives an edge vector with
For completeness, this certificate follows by projecting onto the compact convex set : the projection inequality yields the minimizer and equality in the support-function representation of TV, edge by edge. Conversely, this certificate proves optimality by the subgradient inequality.
For any subset , the box constraint gives . For , equality holds: a crossing edge has a nonzero intensity difference with the same orientation sign as its indicator difference, and the certificate forces to the corresponding signed weight; a noncrossing edge contributes zero. Thus, for every ,
The first inequality holds because includes precisely the negative terms and excludes all positive terms; zero terms may be included or omitted. The second uses and the box bound. This proves the assertion for every , including levels equal to a pixel value.
Proof X-ray
One certificate, a lower bound for every level
Substituting into the binary objective gives, for every subset ,
Each part of the certificate then has one job. Stationarity is what allows this rewriting. The box bound makes the bracket nonnegative for every ; it is the only place the weights enter. The sign condition makes the bracket vanish for every superlevel set at once, because each edge crossing a level set of has with the same sign as . What remains, , is minimized by collecting exactly the negative terms, which is the definition of a superlevel set; zero terms are the source of ties. The coarea formula is never used: an identity averaged over could not show that each individual level is optimal.
The non-strict set is also a minimizer. To see this, use a level just below with no pixel value strictly between it and , then take the limit in the finitely many affine objective values. Other minimizers at a tie need not belong to either of these two sets.
Three-pixel calculation
Worked example 2.4.6
(A chain with two boundaries)
Take the chain with unit edge weights, and . With edges oriented left to right, set and . Then and . Both differences in are positive, so satisfies the edge certificate. Hence this is the unique TV minimizer.
At , its superlevel set is . The cut contains only edge , and
For comparison, , , and . The theorem checks all eight subsets, not just these comparisons. At , strict thresholding gives , while non-strict thresholding gives ; each has value . The middle pixel is exactly at the threshold, so equality creates a genuine segmentation tie.
A second example shows how a level equal to the largest denoised value produces a tie.
Worked example 2.4.7
(Two pixels with a partially shrunk contrast)
Take one edge of weight , and . With the edge oriented , the choice gives . Its difference is and , so the certificate holds and is the minimizer. The contrast shrinks from to ; the mean is unchanged.
For , . At the four subsets give , , and , so is the unique minimizer. At the edge case , the strict set is empty with , while the non-strict set has . The other two subsets give and . Both threshold conventions minimize, as the theorem and the remark on non-strict sets predict.
Counterexample mode
Thresholding the TV solution is not thresholding the data
For two vertices with one unit edge, and , the TV minimizer is . At the strict set is empty, while the non-strict set is both vertices; both minimize with value zero. Thresholding the data instead gives , whose objective is here, also a minimizer by coincidence. At , however, the data threshold still gives with value , whereas both vertices have value . Thresholding noisy data is therefore not generally equivalent to thresholding the TV solution.
Exercises
Exercise 2.4.8
(A four-vertex chain has unit weights and . List its distinct strict superlevel sets on the open intervals between its values and verify the coarea formula numerically.)
Foundation
Solution(3)
- 1
List the superlevel sets
The sets are for , for , for , for , and empty for .
- 2
Compute their cuts
The cuts are respectively ; for instance is crossed by all three edges.
- 3
Compare the integral with TV
The integral is , matching . Isolated endpoints contribute nothing to the integral.
Exercise 2.4.9
(Two vertices are joined by one edge of weight , the data are with , and . Determine the denoised image and the thresholds for which its strict superlevel set is a singleton.)
Core
Solution(2)
- 1
Find the denoised image
The mean is preserved and the output contrast is . Hence . When this is the certificate ; when the value is feasible.
- 2
Read off the singleton thresholds
The strict superlevel set is the singleton exactly when and . If , no strict superlevel set is a singleton.
Exercise 2.4.10
(In the chain example with and , find all minimizers of . Explain why checking only the strict superlevel set would miss one.)
Core
Solution(3)
- 1
Tabulate the data terms
At the per-pixel terms are , and each edge crossing costs .
- 2
Enumerate the eight subsets
and . The other six subsets give (empty set), (), (), (), () and ().
- 3
Identify the minimizers
The minimizers are exactly and . The strict set excludes the pixel whose denoised value equals , so it finds only one of them.
Exercise 2.4.11
(For arbitrary data, prove that minimizes if and minimizes it if . Is the minimizer necessarily unique at the second endpoint?)
Foundation
Solution(2)
- 1
Apply the threshold theorem
For every , so ; for no , so . The threshold theorem says these sets minimize .
- 2
Test uniqueness at the endpoint
Uniqueness at can fail: in the two-vertex example with , and , at both the empty set and have .