Motivation
Motion estimation and segmentation both turn image evidence into hidden variables, but they require different algorithms. A smooth motion model may lead to a positive-definite linear system. A binary region model may lead to a minimum cut on a network. Calling both problems energy minimization does not make their guarantees interchangeable: one proof uses a quadratic spectrum, while the other uses nonnegative capacities and flow conservation.
This unit develops both algorithms far enough to make their claims checkable. Optical flow shows how a physical-looking equation can leave a direction unidentified. Graph cuts show how a nonconvex binary search can nevertheless have an exact global certificate for a restricted class of pair interactions. Each construction also supplies a counterexample to careless generalization.
Brightness constancy, smooth motion, fixed region levels, and rational network capacities are explicit assumptions used below. They are modeling choices, not assertions about every image.
Definitions
Definition 7.1.1
(Optical-flow constraint)
Suppose a differentiable image sequence is constant along a moving image point with velocity . The chain rule gives the optical-flow constraint
At one point this is one scalar equation for two velocity components. In a small window, assuming a common velocity gives weighted least squares with rows and right-hand entries , where . A unique unregularized estimate needs the weighted gradients to span the plane.
Definition 7.1.2
(Regularized dense flow energy)
For a dense field, stack horizontal and vertical components into . Let apply each pixel's gradient to its velocity, let collect temporal derivatives, and let apply spatial differences separately to both components. The regularized energy is
The small magnitude penalty makes uniqueness explicit. It also introduces bias, so it should not be described as measured motion information. With , one complete solver is .
Definition 7.1.3
(Binary segmentation energy and its cut network)
Let , and fix nonnegative unary costs and nonnegative edge weights . The binary energy is
Its network has a source , a sink , and one node per pixel; label zero means the source side. It has arcs with capacity , arcs with capacity , and, for each neighbor pair, both directed arcs with capacity . The capacity of a cut sums only arcs directed from its source side to its sink side.
The levels used to compute unary costs are fixed during this optimization.
Theorem/proposition
Theorem 7.1.4
(A convergent finite optical-flow solver)
For the stated , is symmetric positive definite and the unique minimizer is . If , gradient iteration converges from every initial vector. Its error obeys
This convergence concerns the fixed linearized brightness model, not the original nonlinear image warp.
The second result replaces spectral control by a combinatorial certificate on the network just defined.
Theorem 7.1.5
(Exact binary cuts and a finite max-flow certificate)
For the constructed network, every binary labeling has cut capacity exactly and every cut defines a labeling. With rational capacities, augmenting flow along residual source-to-sink paths terminates after capacities are scaled to integers. On termination, residual reachability defines a minimum cut whose capacity equals the feasible flow value. The resulting labeling is therefore a global minimizer of the fixed binary energy.
The theorem is deliberately restricted to nonnegative attractive pair interactions. Many motion objectives and multilabel segmentation energies do not have this exact form. A globally optimal cut for fixed region levels also need not jointly optimize the unknown levels and the labels.
Zero-capacity arcs are legitimate, and the residual search advances only along strictly positive residual capacity. Keeping that distinction is what handles ties and already saturated edges correctly.
Proof sketch or proof idea
Proof
(Positive definiteness and spectral contraction)
For any nonzero , . Differentiation gives the minimizer. Subtract its normal equation from the update to obtain . The spectral theorem gives orthonormal eigenvectors, and the step condition puts every factor strictly inside . Taking the largest factor magnitude proves geometric convergence. If is removed, uniqueness instead needs when ; smoothness alone does not necessarily supply that condition.
Proof
(Cut capacity, the flow bound, and termination)
For a cut, a label-zero node contributes its arc to the sink, namely , while a label-one node contributes its arc from the source, namely . A neighbor pair contributes zero on the same side and exactly one crossing arc of capacity on opposite sides. Adding the contributions proves energy equality.
A feasible flow respects capacities and conserves flow at every nonterminal node. Summing conservation over any source-side set shows that flow value equals net flow leaving that set and is at most its outgoing cut capacity. This is the lower-bound certificate. Start with zero flow. A residual forward arc has remaining capacity; a residual backward arc permits cancellation of existing flow. Find a residual path, for example with breadth-first search, and augment by its smallest residual capacity. Feasibility and conservation persist. With integral capacities the increase is a positive integer, while the value is bounded by total capacity leaving the source. Thus finitely many augmentations occur. Rational capacities can first be multiplied by a common denominator; this simple termination argument does not claim the resulting bound is efficient in input bit length.
When no residual path remains, let the source-side set consist of nodes reachable from the source by positive residual capacity. Every original arc leaving this set is saturated, and every arc entering it has zero flow, since otherwise its backward residual arc would extend reachability. Consequently net outgoing flow equals cut capacity. The universal flow lower bound then proves both are optimal. This explains why the final flow and cut together are a certificate, whereas an arbitrary plausible labeling is not.
Proof X-ray
Where the cut certificate uses each hypothesis
The proof has three separate parts, and each uses a different assumption. Energy equality uses only the label convention: label zero on the source side is what makes carry . The flow bound uses nonnegativity: the zero flow is feasible only because every capacity is at least zero, and the inequality "value at most cut capacity" drops the incoming crossing flow because it is nonnegative. Termination uses integrality: each augmentation raises the value by at least one, and the value is bounded, so a counting argument closes; for arbitrary real capacities this count gives no bound.
The one non-obvious move is the choice of cut at termination. Instead of searching all cuts, the proof takes the residual-reachable set . Two facts about then turn the inequality into an equality: arcs leaving are saturated, or a forward residual arc would leave ; arcs entering are empty, or a backward residual arc would leave . With equality between one flow and one cut, the universal bound makes the flow maximal and the cut minimal at once, and energy equality transfers minimality to the labeling. A negative capacity breaks the argument at its first step, which is why submodularity, which keeps , is the condition that matters below.
The motion proof is shorter by comparison: positive definiteness supplies uniqueness, and the step condition supplies contraction in every eigendirection.
Worked examples
Worked example 7.1.6
(Smoothness cannot identify uniform tangential motion)
Let . Its brightness equation is , independent of . Even a spatial smoothness penalty leaves every constant vertical velocity equally plausible, because its differences vanish. For a single pixel with magnitude penalty , minimizing gives . Uniqueness has been supplied by a prior and the horizontal component is biased. It would be wrong to report the zero vertical value as measured evidence of no vertical motion.
Worked example 7.1.7
(An explicit cut with a matching flow)
Take two pixels with observed intensities zero and two, region levels zero and two, and squared-error unary costs. Their cost pairs are and . Put pair weight one. Labelings have energies . The network has source-to-first capacity four, second-to-sink capacity four, and interpixel capacities one in each direction; the other terminal capacities are zero. Send one flow unit along source, first pixel, second pixel, sink. The cut separating the first pixel from the second has capacity one. Equal feasible flow and cut values prove global optimality of without relying on exhaustive enumeration.
Worked example 7.1.8
(Representing an asymmetric submodular pair)
Suppose a pair potential has values . Set , , and . Then , as checking all four labels confirms. Add the linear terms to the pixel unaries. A negative unary value is made nonnegative by subtracting that pixel's smaller unary value from both alternatives and recording the removed constant. The pair capacity remains nonnegative and the minimizing labels are unchanged.
In general the same representation works whenever , the binary submodularity condition. Solving the four scalar equations gives the displayed . The condition is exactly what makes . Terms and constants must be accumulated before building terminal capacities. Forgetting a constant changes the reported objective value even when it happens not to change the labels, which invalidates a numerical certificate comparing flow with original energy.
For registration beyond translation, use an affine warp with parameter order . A residual has Jacobian row
where derivatives are evaluated at the warped point. Weighted least squares yields a six-parameter increment when these rows span six-dimensional parameter space. Merely choosing three noncollinear image locations is not sufficient for this intensity-only formulation: each intensity residual supplies only one scalar constraint, and gradient directions also matter. Rewarp, recompute derivatives, and check the original residual after an increment; a line search can reject a step that increases it. Coarse-to-fine initialization can improve the range of useful linearization, while repeated texture and occlusion still create ambiguities.
Concept lensStructural
Fixed evidence and changing unknowns
A graph cut optimizes labels with the unary evidence held fixed. Re-estimating region means afterwards changes those costs and creates a new problem. Alternating exact cuts and exact means for nonempty regions does not increase the joint squared-error energy; retain the previous level if a region is empty. This nonincreasing sequence need not find its global optimum. Likewise, solving a linearized warp exactly does not globally solve the nonlinear registration problem that produced it.
Common mistakes
Counterexample mode
A repulsive pair does not give a nonnegative cut edge
For and , the representation requires . A negative capacity is incompatible with the flow proof and cannot be inserted into this network. This shows failure of the stated attractive-cut construction under the chosen label convention; it does not prove all reformulations impossible. For a single pair, complementing one variable changes the interaction, but multiple interacting pairs may not admit one consistent relabeling that repairs them all.
Optical flow measures apparent brightness motion, which can differ from physical surface motion under changing illumination or reflection. Spatial regularization can also spread errors across a true motion boundary.
Common mistake
(Swapping the terminal-arc convention)
With label zero on the source side, must carry . Building with instead minimizes the energy with every unary pair exchanged. In the two-pixel example the swapped network has capacities for the first pixel and for the second; its minimum cut has capacity one and returns , whose true energy is nine, the worst of the four labelings.
Common mistake
(An iteration limit is not an optimality certificate)
A stopped augmentation routine is certified only when no positive-residual path remains. After an arbitrary iteration limit, the current flow value is still a valid lower bound, and the best labeling found is an upper bound; the honest report is the gap between them. Only a zero gap certifies the labeling.
Summary
Brightness constancy leads to local and dense flow models, whose identifiability must be separated from regularization. A positive-definite finite quadratic has a provably convergent gradient algorithm. Binary attractive segmentation has an exact cut construction and a max-flow optimality certificate. Submodularity characterizes the nonnegative pair coefficient used here, while nonlinear warps, changing region levels, repulsive interactions, and sampling effects require separate guarantees.
Exercises
Exercise 7.1.9
(Two window constraints are and . Compute the unregularized least-squares velocity and its structure tensor. Why is this different from repeating the first constraint twice?)
Foundation
Solution(2)
- 1
Solve the two independent equations
The rows are and , so and ; the solution is . The structure tensor is the sum of , namely .
- 2
Compare with a repeated constraint
Both directions are independently constrained. Repeating only the horizontal equation gives tensor and leaves the vertical component free; extra samples need not supply extra rank.
Exercise 7.1.10
(If has eigenvalues one and four, find the allowable constant gradient step interval. Give the contraction factor for step and explain what happens at step .)
Foundation
Solution(3)
- 1
Apply the step condition
With , the condition is .
Because: The theorem requires .
- 2
Compute the eigenmode factors at
The factors are and , so the norm contraction factor is .
- 3
Examine the endpoint
The second factor is , producing an undamped sign oscillation for a nonzero error in that direction. The open upper endpoint in the theorem is necessary.
Exercise 7.1.11
(A pair potential has values . Compute its nonnegative edge weight and unary coefficients. Verify the four values.)
Core
Solution(2)
- 1
Compute the coefficients
, , and .
- 2
Check all four labelings
Thus , giving zero, three, one, two in the stated order. The constant is zero, and both capacities and unary contributions are nonnegative in this example.
Exercise 7.1.12
(Prove that for any feasible flow and any cut, cut capacity minus flow value is nonnegative. If a proposed labeling has energy five and a feasible flow has value four, what is certified and what remains unknown?)
Core
Solution(3)
- 1
Write the flow value across the cut
Flow value equals outgoing crossing flow minus incoming crossing flow.
Because: Sum conservation over the source-side nodes.
- 2
Bound each term
Key step
Outgoing flow is at most outgoing capacity and incoming flow is nonnegative, so the value is at most the cut capacity.
- 3
Interpret the numbers
The optimum lies between four and five, so the proposed labeling is at most one energy unit above optimum. Equality of the two values would certify exact optimality, but the current unequal pair does not determine which intermediate value is attainable.