Speeding Up Matching with Preemptive Filters

The candidate pair list has been reduced as far as position and appearance allow, and matching still takes eleven hours. Most of that time is spent on pairs that produce nothing: two frames that are close enough to be candidates and share no usable ground, or share it at an angle that defeats the descriptors.

The insight behind preemptive filtering is that those pairs can usually be identified cheaply. Comparing the strongest hundred descriptors takes two percent of the time of comparing all five thousand, and if the strongest hundred produce almost nothing, the full comparison will too. This page covers that and three related economies, with the ordering that keeps each one safe. It extends matching strategies for large and linear surveys.

# Where the time actually goes

Matching a pair has three parts: loading the descriptors, comparing them, and geometrically verifying the result. Comparison dominates, and its cost is the product of the two feature counts — five thousand against five thousand is twenty-five million comparisons per pair.

Two consequences follow. Halving the feature count per image quarters the matching time, which is a much better return than any constant-factor optimisation. And a pair that will fail can be rejected before most of that cost is incurred, provided the rejection test is cheap and correlates with the outcome.

The preemptive test that works is simply the match rate among the strongest features. Features are ordered by response, the strongest are the most repeatable, and if the top hundred produce five matches rather than forty, the pair is not going to succeed.

Figure 1 — Where the two percent buys back the fifty-eight.

# Minimal reproducible solution

import cv2
import numpy as np


def preemptive_match(desc_a: np.ndarray, desc_b: np.ndarray,
                     *, preview: int = 100, min_preview_matches: int = 8,
                     ratio: float = 0.8) -> dict:
    """Test a pair on its strongest features before committing to the full match.

    Descriptors must be ordered by feature response for this to work — the
    premise is that the strongest features are the most repeatable, so a poor
    match rate among them predicts a poor match rate overall.
    """
    matcher = cv2.BFMatcher(cv2.NORM_L2)

    head_a = desc_a[:preview]
    head_b = desc_b[:preview]
    if len(head_a) < 10 or len(head_b) < 10:
        return {"proceed": False, "reason": "too few features to test"}

    preview_pairs = matcher.knnMatch(head_a, head_b, k=2)
    preview_good = [m for m, n in preview_pairs if m.distance < ratio * n.distance]

    if len(preview_good) < min_preview_matches:
        return {"proceed": False, "preview_matches": len(preview_good),
                "reason": "preview match rate too low"}

    full_pairs = matcher.knnMatch(desc_a, desc_b, k=2)
    good = [m for m, n in full_pairs if m.distance < ratio * n.distance]
    return {"proceed": True, "preview_matches": len(preview_good),
            "matches": len(good), "matches_obj": good}

The threshold needs calibrating once per camera and scene type, and calibrating it is straightforward: run without preemption on a few hundred pairs, record the preview count and the final count for each, and choose the preview threshold that rejects the most failures while losing almost no successes.

# Choosing the threshold from data

import numpy as np


def calibrate_preview_threshold(preview_counts: np.ndarray,
                                final_counts: np.ndarray,
                                *, success_threshold: int = 30,
                                max_loss: float = 0.01) -> dict:
    """Pick a preview threshold that loses at most `max_loss` of good pairs.

    The asymmetry is deliberate: rejecting a pair that would have matched
    costs reconstruction strength, while accepting one that will not costs
    only time. The threshold is chosen to protect against the first.
    """
    preview = np.asarray(preview_counts)
    final = np.asarray(final_counts)
    succeeded = final >= success_threshold

    best = None
    for t in range(1, 41):
        kept = preview >= t
        lost = float((succeeded & ~kept).sum() / max(succeeded.sum(), 1))
        if lost > max_loss:
            break
        rejected_failures = float(((~succeeded) & ~kept).sum() / max((~succeeded).sum(), 1))
        best = {"threshold": t, "good_pairs_lost": lost,
                "failures_rejected": rejected_failures}
    return best or {"threshold": 1, "note": "no threshold is safe on this data"}

# Three other economies

A feature budget per image. Matching cost is quadratic in the feature count, so capping at two thousand strongest features rather than extracting ten thousand cuts the cost by a factor of twenty-five. The reconstruction loses little: tie points are already far denser than the adjustment needs, and the features dropped are the weakest.

Reduced descriptor precision. Float descriptors compared in single precision are twice as fast as double and indistinguishable in outcome. Binary descriptors are faster still by a large factor, at some cost in matching quality on difficult imagery.

Early geometric rejection. A pair with enough raw matches can still fail geometric verification. Running a cheap fundamental-matrix estimate on a subset before the full one rejects those early.

import cv2
import numpy as np


def feature_budget(keypoints, descriptors, *, budget: int = 2000):
    """Keep the strongest features, which is where the repeatability is."""
    if len(keypoints) <= budget:
        return keypoints, descriptors
    order = np.argsort([-kp.response for kp in keypoints])[:budget]
    return [keypoints[i] for i in order], descriptors[order]


def early_geometric_check(pts_a: np.ndarray, pts_b: np.ndarray,
                          *, sample: int = 200, min_inlier_ratio: float = 0.2) -> bool:
    """Cheap geometric plausibility test on a subset of the matches."""
    if len(pts_a) < 20:
        return False
    idx = np.random.default_rng(0).choice(len(pts_a),
                                          size=min(sample, len(pts_a)), replace=False)
    _, mask = cv2.findFundamentalMat(pts_a[idx], pts_b[idx], cv2.FM_RANSAC, 3.0, 0.99)
    if mask is None:
        return False
    return float(mask.mean()) >= min_inlier_ratio

Figure 3 — Filter on geometry, not on how hard a pair looked.

# Edge-case matrix

The loop-closure row deserves an exemption in code. Appearance candidates are precisely the structurally valuable pairs, and they often have lower match rates than adjacent frames because they view the same ground from a different time and angle. Applying the same preview threshold to them discards the pairs the vocabulary tree was run to find.

# Verification snippet

import numpy as np


def preemption_report(decisions: list[dict], *, success_threshold: int = 30) -> dict:
    """What preemption actually saved and cost on a real run."""
    rejected = [d for d in decisions if not d["proceed"]]
    proceeded = [d for d in decisions if d["proceed"]]
    successes = [d for d in proceeded if d.get("matches", 0) >= success_threshold]

    return {"pairs": len(decisions),
            "rejected_early": len(rejected),
            "rejection_rate": len(rejected) / max(len(decisions), 1),
            "proceeded": len(proceeded),
            "success_rate_among_proceeded": len(successes) / max(len(proceeded), 1),
            "estimated_time_saved": len(rejected) * 0.98 / max(len(decisions), 1),
            "note": ("preemption is paying for itself"
                     if len(rejected) > 0.2 * len(decisions) else
                     "few rejections — the candidate list is already tight and "
                     "preemption is adding overhead")}

The last branch matters. On a tightly selected candidate list where most pairs succeed, the preview costs two percent on every pair and rejects almost none, so it is a small net loss. Preemption pays when the candidate list is generous, which is exactly when it is needed.

Figure 2 — A measured threshold rather than a chosen one.

# Ordering the filters safely

The filters interact, and the order decides whether each remains safe.

Apply the feature budget first, because it changes what “the strongest hundred” means and therefore invalidates any threshold calibrated before it. Then the preview test, which is cheap and rejects most failures. Then the full comparison, and only then the geometric verification, which is the most expensive per surviving pair and the most decisive.

Calibrating the preview threshold after the budget is set, and re-calibrating whenever the budget changes, is the discipline that keeps the whole arrangement from silently discarding good pairs. A budget change of a factor of two roughly doubles the preview match count for the same pair, and a threshold calibrated at the old budget becomes far too lenient.

# When to escalate

• Matching is still too slow with every filter applied. The candidate list is the lever. Tighten the spatial radius after checking connectivity, or split the survey into blocks.
• The reconstruction weakened after adding preemption. The threshold is too high, or appearance candidates were not exempted. Re-calibrate against measured pairs.
• Preemption rejects almost nothing. The candidate list is already tight; remove the preview and save its two percent.

# Related

• Matching Strategies for Large and Linear Surveys
• Parallel Processing Strategies for Alignment
• Fixing SIFT vs ORB Performance in UAV Photos

← Matching Strategies for Large and Linear Surveys