Motivation
Two images can disagree because objects have moved, because the camera has moved, or because brightness and noise have changed. Registration estimates a geometric correspondence. Segmentation assigns pixels to regions. Feature detection seeks locations whose local structure is informative for matching or description. These tasks influence one another, but their unknowns and failure modes differ. A sharp edge may define an excellent region boundary while providing very little information about motion along that edge.
This note builds elementary models for all three tasks and explains where multiscale processing enters. The goal is not to claim that a small collection of formulas solves general vision. Instead, precise low-dimensional examples reveal which information a model uses, which ambiguities remain, and which optimization statements are actually justified.
The direction of an image warp deserves attention at the beginning. We compare a fixed image with a moving image sampled as . Thus a positive translation parameter moves the sampling location in to the right. A displayed object can appear to move in the opposite direction after resampling. Writing the comparison equation prevents a verbal sign convention from becoming an implementation error.
Definitions
Let be sample locations and let be differentiable near them. Translation registration minimizes
This assumes that translation and approximate brightness constancy are reasonable. Rotation, occlusion, contrast changes, and deformation require different models or additional variables. Values away from the sampling grid also require interpolation; the chosen interpolant determines the derivatives used by an algorithm.
At a current parameter , put and let row of be . The first-order model is , and the Gauss–Newton increment minimizes . The matrix is a local structure tensor. Its eigenvalues measure which displacement directions change the sampled intensities to first order. The tensor depends on image scale, noise and intensity units, so a fixed numerical threshold is not a universal criterion for a good feature.
For segmentation, let the observed intensities be . A binary labeling with fixed region levels has data energy
A spatial regularizer may add over neighboring pixels. This term counts label changes on the chosen graph, so it encourages shorter discrete boundaries. It also couples decisions that were independent in . The binary problem is different from the convex relaxation obtained by allowing labels in .
For multiscale analysis on , define the Gaussian
Assume the image is bounded or otherwise satisfies conditions that make these convolutions and derivatives valid. The scale parameter changes the amount of averaging; it is not merely a graphical zoom. Finite images need an explicit boundary extension before this infinite-domain formula is approximated numerically.
Theorem/proposition
Theorem 3.1.1
(When a linearized translation is identifiable)
The least-squares increment has a unique minimizer if and only if is positive definite. Equivalently, there is no nonzero displacement orthogonal to every sampled gradient. In that case
This is a statement about the linearized problem at , not a guarantee of a unique global registration for .
Theorem 3.1.2
(Optimal binary labels for fixed region levels)
If and there is no spatial penalty, a label minimizes exactly when each pixel is assigned to its closer level. Thus label one is required when , label zero when , and either label is optimal at equality. For a fixed nonempty region, the level minimizing its sum of squared errors is its arithmetic mean.
The nonempty condition prevents division by zero when estimating a region level. An alternating algorithm can update labels and then means, decreasing the energy at each step, while still depending on initialization. Monotonic decrease is weaker than convergence to a global optimum. Empty-region handling is part of the algorithm and must be specified rather than hidden inside a mean formula.
Proof sketch or proof idea
Proof
(Identifiability of the linearized increment)
For any displacement , . This vanishes exactly when all gradient projections vanish, so is positive definite exactly when no nonzero is orthogonal to every sampled gradient. Expanding,
If is positive definite, is strictly convex, and its unique minimizer solves the normal equation , which gives . Conversely, if for nonzero , then for every real , so no minimizer can be unique. A least-squares minimizer still exists; it may be selected using a pseudoinverse, but that selection does not make the missing direction observable.
Proof X-ray
Uniqueness needs information in every direction
The whole proof rests on the identity : the structure tensor is a Gram matrix, so its positive definiteness is a spanning condition on the sampled gradients, just as independent columns identify a linear system's unknowns. The converse direction is the instructive one. It does not need any estimate: a single nonzero with gives a whole line of minimizers, because the quadratic model cannot see motion along at all. A straight edge supplies gradients normal to that edge only and leaves tangential motion invisible; calling the edge “high contrast” scales but does not repair its rank. Several differently oriented edges or a corner supply the missing direction. Finally, nothing in the argument concerns itself: the conclusion holds for the model at , which is why the theorem disclaims global uniqueness.
Proof
(The midpoint rule and the mean)
For segmentation the energy is a sum of terms depending on separate labels, so each label can be chosen independently. Subtracting the label-zero cost from the label-one cost gives
Since , this is negative exactly when ; its zero gives the tie. For a region of size , let . Completing the square yields
The final term is uniquely minimized at the mean.
The identity also explains how intensity noise and within-region variation contribute to the residual even at the best constant fit, so a positive residual alone does not show that the segmentation failed.
Worked examples
Worked example 3.1.3
(The aperture problem as an exact nullspace)
Let and suppose the fixed image satisfies on the sampled region. Then . Every sample gradient is , so . The horizontal parameter is determined as , but every vertical value gives the same data and energy. This is a global ambiguity in this special linear image, not merely a weakness of a local optimizer. Adding more samples of the same ramp improves precision horizontally without adding any vertical information.
Worked example 3.1.4
(Two gradient directions determine a local increment)
Suppose two sampled gradients are and , and the residual vector is . Then , , and . The increment is , which makes the linearized residual zero. This does not prove that the true warped-image residual vanishes after the full step: neglected second derivatives can matter. An actual algorithm should evaluate the original energy and may shorten the step.
Worked example 3.1.5
(A boundary penalty can remove an isolated label)
Take a three-pixel path with intensities and fixed levels , . Without regularization, is the unique optimal label vector and has zero data cost. It has two label changes, so with boundary weight its total cost is . The all-zero labeling has cost one and no boundary. Enumerating the eight label vectors shows that for the isolated middle region is optimal, at it ties with all zero, and for all zero is the unique optimum. Spatial regularization can remove a small true feature as well as a noisy one.
Gaussian scales compose according to . One proof completes the square in the convolution integral; alternatively, independent centered Gaussian displacements have covariances that add. Thus two rounds of smoothing with the same standard deviation do not produce standard deviation ; they produce . Differentiation commutes with smoothing when the integral is justified, so . This replaces differentiation of noisy samples by differentiation after averaging, while introducing a scale-dependent loss of detail.
To see this tradeoff quantitatively, take . Gaussian smoothing multiplies it by . Large spatial frequencies are suppressed much more strongly than small ones. A small high-frequency noise perturbation becomes less prominent, but a genuine fine stripe is attenuated by the same factor. An intensity pattern alone does not tell the filter which of those interpretations is correct.
Concept lensGeometric
Edges, corners, and the tensor's eigenvalues
When both tensor eigenvalues are small, the patch has little first-order texture. One large eigenvalue indicates an edge-like patch with an ambiguous direction. Two sufficiently large eigenvalues indicate locally informative two-dimensional structure. These are quantitative descriptions of the local brightness model, rather than semantic labels for objects. An eigenvalue threshold should be interpreted relative to noise, scale, and intensity units.
A coarse-to-fine registration method smooths and samples images at several resolutions, estimates a displacement at a coarse level, then refines it at finer levels. It can bring a large pixel displacement into the range where linearization is useful. When a coarse grid spacing is twice a fine spacing, a translation measured in coarse pixel units must be multiplied by two before fine-grid refinement. Smoothing should precede downsampling to reduce aliasing. Neither operation guarantees success: repeated texture can generate several plausible alignments, and coarse smoothing may erase the feature needed to select the correct one.
For binary segmentation, graph boundary penalties and continuum perimeter models are related but not identical without a stated limiting procedure. An axis-aligned graph may charge diagonal boundaries differently. For feature detection, gradient magnitude alone emphasizes edges, whereas a structure tensor tests directional diversity. For registration, a feature correspondence may suggest an initial transformation, but the transformation's parameter count and geometric degeneracies still determine whether it can be estimated.
Common mistakes
Counterexample mode
Local full rank does not ensure global uniqueness
The periodic image can have a full-rank collection of gradients on a suitable patch. Yet translations differing by produce exactly the same image for integers . A positive definite local tensor rules out infinitesimal ambiguity at that location; it cannot distinguish repeated global patterns. A bounded search domain or external information may be necessary to select an alignment.
The remaining mistakes all arise from carrying a conclusion beyond the hypotheses used to prove it. Do not compute a region mean when the region is empty, and do not interpret a decreasing alternating energy as a certificate of a global minimum.
Common mistake
(Using the midpoint rule after adding a boundary penalty)
The threshold theorem assumes no spatial term. In the three-pixel example with , the middle intensity lies above the midpoint , yet the unique optimum labels it zero. Once neighboring labels are coupled, a pixel's best label depends on its neighbors' labels.
Common mistake
(Adding standard deviations when smoothing twice)
Smoothing with and then is smoothing with , not : variances add. Reporting overstates the averaging, and for a sinusoid of angular frequency it predicts the multiplier instead of the correct .
Common mistake
(Reading a small linearized residual as a small registration error)
In registration, a small linearized residual is not the same quantity as a small nonlinear residual; the full step must be evaluated in . Interpolation, boundary handling, occlusion, and brightness changes can also dominate the result even when the normal equations are solved accurately. Report the geometric convention and the image scale with estimated displacements. Without those units and conventions, two correct numerical values may appear contradictory.
Summary
Registration estimates geometric parameters, segmentation estimates region labels, and features summarize local image structure. A structure tensor identifies the directions visible to linearized translation. Fixed-level segmentation has an exact threshold rule only without spatial coupling. Gaussian scale space provides controlled averaging, and its variances add under composition. Multiscale algorithms can improve an optimization's starting point, while leaving fundamental ambiguities and lost features unresolved.
Exercises
Exercise 3.1.6
(Suppose all sampled gradients equal . Compute , identify its nullspace, and explain which translations cannot be distinguished to first order.)
Foundation
Solution(3)
- 1
Form the tensor
.
- 2
Find the eigenvectors
has eigenvalue and has eigenvalue zero, so the nullspace is spanned by .
- 3
Interpret
Only the sum of the translation components changes the first-order model. A displacement along leaves every gradient projection zero, regardless of contrast or sample count.
Exercise 3.1.7
(With fixed levels and , find every optimal unregularized label for intensities . Then compute the best constant level for the nonempty region containing intensities one and four.)
Foundation
Solution(2)
- 1
Apply the midpoint rule
The midpoint is . The first intensity must have label zero, the third label one, and the middle may have either label. These are the only optimal labelings because costs separate by pixel, so the optimal label vectors are exactly and .
- 2
Fit the region level
For the two-element region the mean is . Its squared residual is , and completing the square proves this is the minimum.
Exercise 3.1.8
(Smooth successively with Gaussian standard deviations three and four. Find the resulting standard deviation and the attenuation factor for a sinusoid of angular frequency in one coordinate.)
Foundation
Solution(2)
- 1
Add the variances
Key step
, so the result is smoothing with standard deviation five.
- 2
Compute the multiplier
The sinusoid multiplier is . Multiplying the two original factors and gives the same result. Adding standard deviations would give seven and would describe a different amount of smoothing.
Exercise 3.1.9
(A displacement estimated on a grid with spacing four times the target grid is in coarse pixel units. Convert it to fine pixel units. Explain why rescaling alone does not establish that the estimate is correct, and give a repeated-pattern example.)
Core
Solution(3)
- 1
Rescale
The estimate is fine pixels.
- 2
Separate units from evidence
Rescaling changes coordinate units, not evidence for correspondence.
- 3
Exhibit an ambiguity
A stripe pattern repeated every eight fine pixels has identical alignments after translations by whole periods in its repetition direction. Coarse sampling can add further ambiguity, so the estimate must be checked against the original comparison model and any available geometric constraints.