Motivation
Knowing that a plane induces a homography does not tell us which matrix matches two photographs. We must infer that matrix from measured correspondences, some noisy and some entirely wrong. A geometric model, an estimator and an outlier-selection rule are distinct objects. A correct camera model can be fitted badly, while an inaccurate model can fit a small selected region surprisingly well.
The earlier warping note developed projective geometry and sampling. Here the unknown transformation is the object of estimation. We ask how linear constraints determine it, why coordinate normalization helps numerical scaling without repairing missing information, and what a robust random-sampling calculation actually guarantees. We also estimate a small intrinsic-camera model from known camera-coordinate points, carefully separating that task from unrestricted calibration using unknown poses.
This separation matters in a panorama. Matching repeated windows can produce a strong but incorrect consensus. Points on one straight edge cannot constrain every projective degree of freedom. A large number of trials cannot repair a sample distribution that never produces a usable configuration. The goal is an auditable alignment procedure whose assumptions remain visible after a plausible-looking overlay has been obtained.
Definitions
Definition 1.29.1
(Linear constraints and the algebraic estimate)
Write finite matched points as and . Let the rows of the unknown matrix be . Eliminating the homogeneous scale gives two linear equations per match:
Stack these as , where lists the matrix entries. The equations also admit zero, so exact estimation seeks a nonzero null vector up to scale. With noisy data, minimize subject to ; a right singular vector for the smallest singular value solves that algebraic problem. The estimated matrix still needs invertibility and finite-denominator checks.
Definition 1.29.2
(Point normalization)
Normalize each image's points separately. Subtract its centroid and multiply both coordinates by a positive scalar so their root-mean-square distance from the origin is . This is defined when that RMS distance is positive. Let the homogeneous similarity matrices be . Estimate from normalized points and return
Normalization changes the algebraic objective under noise. It is a useful scaling convention, not a claim of universal statistical optimality. It preserves exact geometric constraints because the coordinate changes are invertible. A pixel reprojection residual is instead , where dehomogenizes a vector with nonzero last coordinate.
Definition 1.29.3
(Restricted intrinsic calibration)
For a restricted intrinsic calibration, suppose camera-coordinate ratios , are known, square pixels and zero skew are assumed, and unknowns are one focal scale and principal point . Then , . This is a linear least-squares problem in three parameters. Unknown scene pose, distortion or unequal focal scales would require a different model.
Definition 1.29.4
(Good subset in random sampling)
For robust sampling, fix a set of correspondences with true inliers. A trial draws a uniformly random subset of four distinct matches; independent trials redraw from the full set. Call a subset good when it contains only inliers and each of its source and target quadruples consists of four distinct finite points with no three collinear. This definition concerns sample content, not whether a noisy fit later wins the scoring competition.
Theorem/proposition
Theorem 1.29.5
(Four projective frames give a one-dimensional linear nullspace)
Suppose four source points and four corresponding target points are finite, distinct, and no three in either set are collinear. Their eight linear equations have rank eight. Every nonzero null vector reshapes to the same invertible homography up to nonzero scale. Repeated or collinear configurations do not satisfy this theorem.
Theorem 1.29.6
(Robust-sampling confidence depends on the actual trial distribution)
For the independent four-subset trials above, let be the fraction of all-inlier subsets that are nondegenerate, assuming . Then
For , failure probability at most requires
When no finite count suffices; when it is one, one trial suffices. These are sampling guarantees, not guarantees that the selected alignment is correct.
The familiar power describes independent draws with replacement. It is not the exact probability for a subset of four distinct matches. If the implementation discards degenerate subsets before counting trials, a counted trial has a conditional distribution. Its success probability is , not the unconditioned value above. Confidence arithmetic must match the actual counting rule.
Proof sketch or proof idea
Proof
(Rank eight from a projective frame)
The first three source points form a homogeneous basis. In that basis the fourth has three nonzero coefficients: a zero coefficient would put it on the line through two basis points. Rescale the three basis representatives so the fourth is their sum. Do the same for the target frame. In these coordinates, any matrix satisfying the first three correspondences must be diagonal, including the possibility of zero diagonal entries. The fourth correspondence forces all three diagonal entries equal. Thus the solution space consists exactly of scalar multiples of identity in frame coordinates. Transforming back gives one null direction, an invertible nonzero representative and rank eight.
The scale factors in this proof may be zero only for the zero matrix: if the fourth image scale were zero, the three nonzero frame coordinates force every diagonal entry zero. This observation closes a small gap that a degree-of-freedom count alone leaves open. An eight-equation count does not independently prove rank eight.
Proof X-ray
Where the frame argument uses each hypothesis
Each hypothesis is spent at a specific point. No three collinear, applied to the source points, makes the first three a basis and forces all three coefficients of the fourth to be nonzero; applied to the target points, it does the same on the other side. The non-obvious move is to use these two frames as coordinate systems. The system of eight equations in nine unknowns then collapses to the statement "the matrix is diagonal with equal entries", which can be read off. The fourth correspondence is the only place that ties the three diagonal entries together.
Drop the collinearity hypothesis and the fourth point may have a zero coefficient. The diagonal entry attached to the missing basis vector is then unconstrained, so the null space is larger, as in the counterexample later in this unit. Invertible coordinate changes such as point normalization leave this rank unchanged, so they cannot repair a degenerate configuration; they only improve the numerical conditioning of a singular-vector computation. Inspect singular values to tell a mathematically missing direction from a weakly constrained one.
Proof
(Counting good subsets and trials)
For sampling, there are equally likely subsets and all-inlier subsets. The valid fraction supplies . A failed trial has probability ; independent repetitions multiply those failure probabilities. Taking logarithms gives the bound, remembering that is negative. Adaptive sampling, dependent reuse or changing match sets require a new probability model.
The restricted camera design has rows and . Its rank is three exactly when the normalized scene points are not all identical. Indeed, a homogeneous parameter perturbation obeys and . If , both coordinate lists must be constant. If two normalized points differ, and both offsets vanish. A single planar-image homography with unknown pose does not supply these known ratios, so it does not justify using this small calibration proof for unrestricted intrinsic recovery.
Worked examples
Worked example 1.29.7
(Estimate and normalize an exact four-match map)
Match to . The matrix
satisfies every equation and is unique up to scale by the frame theorem. Source centroid is and RMS distance , so its scale is two. Target centroid is and RMS distance , giving scale . In normalized coordinates the map is . Denormalizing recovers the displayed matrix. The centering removes translations from this particular normalized map, but does not make all homographies affine.
Worked example 1.29.8
(A fully determined restricted camera calibration)
Known normalized points are , with measured pixels . The first point gives the principal point directly, . Either nonzero normalized coordinate gives , and the remaining equations agree. Distinct normalized points guarantee rank three. If all points lay on the same camera ray, increasing could be compensated by changing the offsets, leaving the observations unchanged. This example estimates actual parameters under a restricted known-pose model; it does not solve general camera calibration.
Worked example 1.29.9
(Why a subset probability changes the trial count)
Let , , and every all-inlier quadruple be valid. Then . To make failure probability at most requires 41 independent raw trials. Using instead would suggest 22, which is unjustified for this distinct-subset experiment. If only half the all-inlier subsets are valid, the actual probability is and the count becomes 83. These numbers assume the inlier labels and valid fraction describe the fixed match set; estimating them optimistically from the winning model does not create the same guarantee.
An explicit robust alignment loop now has a clear meaning: draw a subset under the stated rule, reject degenerate configurations, estimate a normalized candidate, check its validity over the intended image region, score geometric residuals on all matches, retain a selected consensus, and refit using its matches. A final nonlinear refinement may minimize geometric error directly. Refitting or refinement changes the estimator, so report the residual definition and selection threshold rather than only the random-trial count.
Concept lensStructural
A mosaic alignment is a collection of mutually constrained frames
Pairwise maps should agree around overlap cycles when one geometric model applies. Three attractive local overlays can still produce a drifting cycle. Choose one image frame as an anchor, inspect cycle and reprojection residuals, and distinguish model failure from isolated correspondence errors. A blending stage acts on intensities after this geometry and cannot certify those frame constraints.
Coordinate thresholds should also be traceable. A threshold stated in normalized coordinates is not automatically the same pixel tolerance in both images. Symmetric transfer error uses both and and needs valid denominators in both directions. A large residual may come from a false match, lens distortion or genuine depth parallax; declaring every such point an outlier can hide the fact that no single homography fits the scene of interest.
Common mistakes
Counterexample mode
Many exact matches on one edge do not calibrate a plane map
Identity and agree at every point . A hundred exact correspondences on that line cannot distinguish them. Normalizing the coordinates or running more random trials does not add a second geometric direction. The repair is to obtain spatially distributed nondegenerate matches or use a genuinely lower-dimensional model with an honestly narrower goal.
Common mistake
(Trusting a singular vector from near-degenerate data)
A software routine always returns a smallest singular vector, but near-degenerate data can leave several singular values almost equal, so the returned direction is not meaningfully determined. Inspect the spectrum, not only the vector.
Common mistake
(Reading a large consensus as a truth certificate)
Repetitive patterns or one dominant wrong surface can support a misleading matrix with many inliers. A small algebraic residual is also not a pixel uncertainty: coordinate scaling and the errors-in-variables structure both change its meaning.
Common mistake
(A least-squares fit is not automatically a camera)
A negative fitted focal scale in the stated convention is a warning about the data or the model, not an acceptable camera merely because least squares is defined. If skew, distortion or pose is unknown, state and estimate those quantities explicitly instead of silently reusing a proof whose known normalized coordinates no longer exist.
Summary
Homography estimation starts from homogeneous linear constraints, whose rank is established by a projective-frame argument. Normalization improves coordinate scaling while preserving exact information limits. Restricted camera calibration has a separate explicit design-rank condition. Robust alignment requires both geometric validity and a sampling model that matches the implementation; trial confidence measures the chance to examine a good sample, not the truth of the final mosaic.
Exercises
Quick check
(For the four-match example, map and verify that denormalization gives the same result. Explain why adding an exact fifth match cannot remove the overall scale ambiguity.)
Solution · Answer
The point maps to . The normalized point is ; applying the normalized diagonal map gives , then dividing by and adding target centroid gives . Multiplying every entry of by the same nonzero constant never changes dehomogenization, no matter how many exact matches are added.
Quick check
(Known normalized camera points are and , with pixels and . Estimate and justify rank three even though all horizontal normalized coordinates agree.)
Solution · Answer
The vertical difference gives , hence . Then and . The normalized points differ vertically, forcing in the homogeneous design proof; horizontal variation is not separately necessary for this shared-focal-scale model.
Quick check
(With , , all all-inlier quadruples valid, find the exact good-subset probability and the number of independent raw trials for failure at most . What can be concluded if all five inliers are collinear?)
Solution · Answer
The probability is , requiring 63 trials. If all inliers are collinear, , so the probability of a nondegenerate all-inlier homography sample is zero. The inlier fraction alone cannot establish finite confidence for identifying a full homography.
Quick check
(Suppose and for one raw draw. Find good probability per raw trial and per accepted-valid trial. Explain why the two trial counts cannot be used interchangeably.)
Solution · Answer
A raw trial has good probability . Conditioning on acceptance gives . Accepted trials exclude some raw draws, so the same numeric count represents different amounts of sampling. The independence and conditional-distribution assumptions must hold for whichever count is used; neither version guarantees that a later consensus selector chooses the correct model.