Motivation
A detector returns locations that may be repeatable across images. It does not tell us which detected point in the second image corresponds to a point in the first. A descriptor summarizes the appearance around a point as a vector; comparing these vectors produces tentative pairs. The subsequent registration fit needs geometric agreement as well: a good appearance match can still refer to another, similar-looking object. We will build a small pipeline and state exactly what its probability calculation does and does not guarantee.
Definitions
Definition 5.2.1
(Descriptor distance)
Let and be detected positions in two images, with descriptors . For real-valued descriptors choose, for example, Euclidean distance . A descriptor is not the point position: its coordinates encode chosen local image measurements. Comparing descriptors requires compatible construction and scaling. A binary descriptor normally needs a distance such as Hamming distance instead; Euclidean distance on arbitrary encodings is not automatically meaningful.
Definition 5.2.2
(Ratio test)
For each source descriptor, order the target distances as , retaining their target indices. Given at least two target descriptors, , and a chosen , accept the nearest target only if
The ratio measures distinctiveness among available candidates, not the probability of correctness. Strict inequality rejects a positive-distance tie. If both nearest distances are zero, the ratio is undefined and we reject as ambiguous; with fewer than two candidates there is no ratio to calculate. A lone exact match with passes, but may still be geometrically wrong.
Common mistake
(Applying the ratio threshold to squared distances)
Many implementations store squared distances. With nearest distances and and , the ratio is , so the match is rejected. Comparing the squared ratio with the same would accept it. The equivalent squared-distance condition is , here , which is false.
Definition 5.2.3
(Mutual nearest check)
A mutual nearest check additionally requires the chosen source to be a nearest source of the target; the policy for ties must be stated.
This filters some many-to-one matches but does not prove correctness. An absolute distance bound can reject poor matches that happen to be distinctive; its scale depends on the descriptor and must be chosen for the data. Neither test resolves repeated texture, occlusion or a true match absent from the candidate set.
Geometric consensus
Definition 5.2.4
(Forward residual and consensus inlier)
For a tentative pair and transform , define the forward residual in target-coordinate units. For a specified threshold , call the pair a consensus inlier when .
This label describes agreement with a particular model, not the unknowable true identity of the pair. A threshold must reflect measurement noise and units; changing image resolution without changing it changes the test.
For translation , one pair proposes . Score the proposal against all tentative pairs; retain a high-consensus model and refit it using the selected pairs. For a two-dimensional orientation-preserving similarity, two pairs with distinct source points can determine a candidate if their target points are also distinct; degenerate samples must be rejected. More general models need their own minimum sample size and degeneracy checks. After a consensus fit, inspect the spatial distribution of residuals and the alignment on data not used to choose the model. A large consensus on one repeated pattern need not represent the desired object.
Concept lensGeometric
Appearance and geometry answer different questions
Descriptor distances compare local appearance. A geometric residual asks whether an entire proposed transformation explains a pair of positions. A convincing pipeline needs both, and a coherent false pattern can pass both tests if it supports another transformation.
Theorem/proposition
Theorem 5.2.5
(Probability of drawing an all-inlier sample)
Let be integers with , , , and . Fix tentative pairs, of which exactly are true inliers. A trial chooses distinct pairs uniformly without replacement; trials are independent and each starts again from all pairs. The probability that one trial contains only true inliers is
where the numerator is zero when . The probability of at least one all-inlier sample in trials is . For , to make this probability at least it suffices and is necessary that
If no finite number works; if one trial suffices. This is a sampling guarantee, not a guarantee that the estimated transform is accurate or selected as the winner.
Once a consensus set has been chosen, the refit for a translation model has a closed form.
Proposition 5.2.6
(Least-squares translation refit)
Let be a nonempty finite set of tentative pairs with offsets . The translation minimizing is unique and equals the mean offset .
Proof sketch or proof idea
Proof
(Counting subsets and independent trials)
There are equally likely subsets, and precisely contain only inliers. Each trial fails with probability . Independence between trials gives the product for all failures; taking the complement proves the formula. For , taking logarithms reverses the inequality when dividing by the negative number ; rounding up gives the smallest integer .
Proof X-ray
What the sampling probability leaves out
Each assumption in the statement is used once. Uniform choice of an -subset makes the count ratio a probability, with equally likely outcomes. Sampling without replacement is why the favorable outcomes are the -subsets of the inlier set. With replacement and order, the count would be out of ; that is the source of the common approximation , which is generally not exact here. Independence is used only between trials, in the product ; the pairs inside one trial are not independent and need not be.
The key move in the bound is the division by , which is negative for and reverses the inequality. At that logarithm is zero and at it is undefined, which is why both cases are stated separately. The event counted is the drawing of an all-inlier sample. Degeneracy, noise, thresholding, and model selection lie outside the proof.
The refit is an elementary completion of the square.
Proof
(Completing the square for the mean offset)
Since , expand around :
because the cross term vanishes. The second sum does not depend on , and the first is zero exactly when .
Worked examples
Worked example 5.2.7
(A distinctive descriptor can still be wrong)
Let and target descriptors be , and . The two smallest distances are and ; with the first passes because . Suppose actually belongs to a different repeated object and the true counterpart is occluded. The test still passes: it only compares the supplied candidates. If squared distances are used, the equivalent test is , not .
Worked example 5.2.8
(Translation consensus with one outlier)
Take four tentative pairs , , , and . Their proposed offsets are . At threshold , the first proposal has three inliers and the last has one. Refitting translation by least squares to the first three offsets gives their mean and zero residual on those three. Fitting all four instead gives , illustrating the influence of one gross mismatch. The consensus method has not proved the three pairs are true; it has found a model supported by them.
Worked example 5.2.9
(Exact finite sampling probability)
With , , and , the exact per-trial probability is , not . Three independent trials give success probability . For at least , seven trials are needed: and .
Common mistakes
Counterexample mode
A large false consensus
Imagine four correct pairs sharing translation and six mismatches sharing translation . With , the two offsets are apart, so no translation can accept both groups. Both groups fit exactly, but maximum consensus chooses the six mismatches. Geometric agreement alone does not identify which physical object is intended. Additional prior information, wider image context, or independent verification is needed.
Sampling confidence is the other place where a correct formula is easily over-read.
Common mistake
(Reading the sampling bound as a registration guarantee)
Do not interpret the confidence formula using an estimated inlier fraction as an unconditional guarantee: the fraction and the assumption of independent uniform trials must themselves be justified. Nor does increasing repair an inappropriate transform, an excessive threshold or an unrepresentative candidate set. Refitting is useful but may change which pairs meet the threshold, so any iterative reclassification needs a stated stopping rule; monotonic improvement of every desired quantity is not automatic.
Summary
Descriptors propose local matches; ratio and mutual checks remove some ambiguity. Geometric consensus tests whether proposed pairs support a common model, and refitting uses the resulting set. Sampling confidence quantifies the chance of drawing an all-inlier subset under explicit assumptions, not certainty of correct image registration.
Exercises
Exercise 5.2.10
(With nearest distances and and , decide acceptance. Repeat using squared distances and state the correct threshold.)
Foundation
Solution(2)
- 1
Apply the ratio test
, so the match is accepted.
- 2
Rewrite it for squared distances
, so it is again accepted; the squared threshold is .
Exercise 5.2.11
(Three target descriptors have distances from a source. Can the ratio test distinguish the two closest targets? What changes if distances are ?)
Foundation
Solution(2)
- 1
Examine the double zero
The ratio is , undefined, so the test rejects the source as ambiguous.
- 2
Examine the single zero
The ratio is and passes any positive threshold, although correctness is not guaranteed.
Exercise 5.2.12
(Five translation offsets are . Use to score proposals and , then give the least-squares refit for the larger consensus and for all five offsets.)
Core
Solution(2)
- 1
Score both proposals
The two distinct offsets are distance five apart, which exceeds ; the scores are four and one.
- 2
Refit by the mean offset
The selected four average to ; all five average to .
Because: The least-squares translation is the mean offset.
Exercise 5.2.13
(Among six pairs, four are true inliers. For independent trials of two distinct uniformly sampled pairs, compute the chance of at least one all-inlier trial in two trials. Explain why it is not the chance of correct final registration.)
Core
Solution(3)
- 1
Compute the per-trial probability
.
- 2
Combine two independent trials
.
- 3
State what is not covered
Degenerate samples, noise, model selection and a competing false consensus can still prevent correct registration.