Matching Strategies for Large and Linear Surveys
Feature matching compares images pairwise, and the number of pairs grows with the square of the survey. Two hundred images is twenty thousand pairs and a few minutes; ten thousand images is fifty million pairs and a week. No amount of faster matching changes the shape of that curve — only matching fewer pairs does.
Which pairs to skip is the whole problem, and getting it wrong in either direction is expensive: too many pairs and the job never finishes, too few and the reconstruction fragments into submodels that will not merge. This page covers building a candidate pair graph, the approaches that scale, and the specific failure of corridor surveys, where the geometry provides almost no redundancy. It extends automated image alignment and feature matching workflows.
Audience and prerequisites. Python 3.10+, a survey with camera positions in EXIF, and familiarity with feature detection algorithms for drone imagery.
Prerequisites
| Library / tool | Minimum version | Install command | Role |
|---|---|---|---|
numpy |
≥ 1.24 | pip install numpy |
Pair graph arithmetic |
scipy |
≥ 1.10 | pip install scipy |
Spatial indexing for neighbour queries |
opencv-python |
≥ 4.8 | pip install opencv-python |
Feature extraction and matching |
networkx |
≥ 3.2 | pip install networkx |
Graph connectivity analysis |
| OpenSfM / ODM | ≥ 0.9 | see the setup guide | Where the pair list is consumed |
Conceptual architecture
Three strategies select pairs, and they are complementary rather than alternatives.
Spatial pairing uses the camera positions from EXIF. Two images taken a hundred metres apart at eighty metres altitude cannot overlap, so the pair need not be tested. This removes the overwhelming majority of candidates at effectively no cost and is always worth doing.
Sequential pairing adds the images immediately before and after each frame in capture order. On a flight line those are the strongest matches available, and they are cheap to include.
Appearance-based pairing — a vocabulary tree or a similar index — finds images that look alike regardless of where they were taken. It is what catches loop closures on a corridor and the cross-line matches that tie a grid together, and it is the only strategy that works when positions are missing.
Figure 1 — Four strategies at survey scale. The first is not slow; it is infeasible.
Step 1: Build the spatial pair graph
import numpy as np
from scipy.spatial import cKDTree
def spatial_pairs(positions_enu: np.ndarray, altitude_m: float,
*, fov_deg: float = 84.0, margin: float = 1.2) -> set:
"""Candidate pairs from camera positions and the sensor footprint.
The radius is derived from the geometry rather than guessed: two frames
can only overlap if their centres are closer than one footprint width,
and the margin covers terrain relief and attitude variation.
"""
swath = 2.0 * altitude_m * np.tan(np.radians(fov_deg / 2.0))
radius = swath * margin
tree = cKDTree(positions_enu[:, :2])
pairs = set()
for i, neighbours in enumerate(tree.query_ball_point(positions_enu[:, :2], radius)):
for j in neighbours:
if j > i:
pairs.add((i, j))
return pairs
Deriving the radius from the footprint rather than accepting a default is what makes this safe across altitudes. A fixed hundred-metre radius is generous at 50 m altitude and excludes genuine overlaps at 120 m, and the failure it produces — a reconstruction that fragments over part of the site — looks like a matching problem rather than a configuration one.
Step 2: Add sequential and appearance candidates
def sequential_pairs(n_images: int, *, window: int = 4) -> set:
"""Each image paired with its neighbours in capture order."""
return {(i, j) for i in range(n_images)
for j in range(i + 1, min(i + window + 1, n_images))}
def combine_strategies(spatial: set, sequential: set,
appearance: set, *, cap: int | None = None) -> dict:
"""Union the strategies, with an optional cap on the total.
Capping by removing the lowest-priority spatial pairs rather than by
truncating the union preserves the sequential and appearance pairs, which
are the ones holding the graph together.
"""
combined = sequential | appearance | spatial
if cap is None or len(combined) <= cap:
return {"pairs": combined, "capped": False, "count": len(combined)}
protected = sequential | appearance
removable = sorted(spatial - protected)
keep = cap - len(protected)
if keep < 0:
raise ValueError("the protected pairs alone exceed the cap")
return {"pairs": protected | set(removable[:keep]), "capped": True,
"count": cap, "dropped": len(removable) - keep}
Step 3: Check the graph is connected before matching anything
A pair graph that splits into components produces a reconstruction that splits into submodels, and discovering that after six hours of matching is avoidable — connectivity is a property of the graph, computable in seconds.
import networkx as nx
def analyse_graph(pairs: set, n_images: int) -> dict:
"""Connectivity and weak points of the candidate pair graph.
Articulation points are the images whose removal would disconnect the
graph. On a corridor survey they are common and they are exactly where a
reconstruction breaks, so finding them before matching is worth the call.
"""
graph = nx.Graph()
graph.add_nodes_from(range(n_images))
graph.add_edges_from(pairs)
components = list(nx.connected_components(graph))
isolated = [n for n in graph.nodes if graph.degree(n) == 0]
articulation = list(nx.articulation_points(graph)) if nx.is_connected(graph) else []
return {"images": n_images, "pairs": len(pairs),
"components": len(components),
"largest_component": max((len(c) for c in components), default=0),
"isolated_images": isolated[:20],
"articulation_points": len(articulation),
"median_degree": int(np.median([d for _, d in graph.degree()])),
"connected": len(components) == 1,
"note": ("the graph is connected" if len(components) == 1 else
f"the graph has {len(components)} components — the reconstruction "
"will fragment")}
A median degree below about eight is a warning sign on a grid survey: it means the pair selection is tight enough that individual match failures will disconnect images. The remedy is a larger radius or more appearance candidates, both of which cost matching time and are cheaper than a fragmented reconstruction.
Step 4: Handle the corridor case explicitly
A corridor survey — a road, a pipeline, a river — is the geometry where matching strategies matter most, because the structure is one-dimensional. Every image overlaps only its neighbours along the line, so the graph is a chain, and a chain accumulates error without bound: small orientation errors compound along its length and the far end drifts.
Three measures address it, and they work together rather than as alternatives.
Fly more than one line. Two parallel lines with cross-overlap turn a chain into a ladder, which constrains the drift enormously for perhaps thirty percent more flight time.
Add cross passes. A perpendicular line every few hundred metres ties the two sides of the corridor together and gives the adjustment the geometry it otherwise lacks.
Place control along the length. A chain anchored at both ends and the middle cannot drift as far as one anchored only at the start. The control discipline is in ground control point optimization.
Figure 2 — The structural difference a second flight line makes, which is more than a linear improvement.
Step 5: Split the survey when it will not fit at all
Past a certain size, no pair-selection strategy makes a survey tractable in one reconstruction: the bundle adjustment itself becomes the constraint, because its memory and time grow faster than linearly in the number of cameras. The remedy is to reconstruct in overlapping blocks and merge.
Splitting well matters more than splitting at all. Blocks must overlap substantially — a quarter of their extent is a reasonable default — and the overlap must contain structure, not water or bare field, because the merge is a registration and needs features to register on.
import numpy as np
def split_into_blocks(positions_enu: np.ndarray, *, max_images: int = 2500,
overlap_fraction: float = 0.25) -> list[dict]:
"""Partition a survey into overlapping blocks along its longest axis.
Splitting along the longest axis keeps each block as compact as possible,
which matters because a long thin block has the same weak geometry as a
corridor and inherits its drift.
"""
xy = positions_enu[:, :2]
extent = xy.max(axis=0) - xy.min(axis=0)
axis = int(np.argmax(extent))
order = np.argsort(xy[:, axis])
n_blocks = int(np.ceil(len(order) / max_images))
if n_blocks <= 1:
return [{"indices": order.tolist(), "block": 0}]
per_block = int(np.ceil(len(order) / n_blocks))
pad = int(per_block * overlap_fraction)
blocks = []
for b in range(n_blocks):
start = max(b * per_block - pad, 0)
end = min((b + 1) * per_block + pad, len(order))
blocks.append({"block": b, "indices": order[start:end].tolist(),
"overlap_images": pad})
return blocks
The merge itself uses shared control points or shared tie points and is covered in merging submodels with shared control points. What matters at this stage is that the blocks were designed to be mergeable, because a merge between blocks that share only a thin strip of featureless ground fails in a way that no amount of merging effort recovers.
Step 6: Measure the graph rather than guessing at it
The parameters on this page — radius, window, candidate count — are all trade-offs between matching time and reconstruction strength, and the right values differ by survey. Measuring is cheap enough to do per job.
import numpy as np
def sweep_radius(positions_enu: np.ndarray, altitude_m: float,
multipliers=(0.8, 1.0, 1.2, 1.5, 2.0)) -> list[dict]:
"""Pair count and graph connectivity against the spatial radius.
The useful shape is a knee: connectivity improves steeply up to a point
and the pair count keeps growing quadratically afterwards. Choosing at
the knee is a measured decision rather than a default.
"""
rows = []
for m in multipliers:
pairs = spatial_pairs(positions_enu, altitude_m, margin=m)
graph = analyse_graph(pairs, len(positions_enu))
rows.append({"margin": m, "pairs": len(pairs),
"components": graph["components"],
"median_degree": graph["median_degree"],
"connected": graph["connected"]})
return rows
def choose_margin(sweep: list[dict], *, min_degree: int = 8) -> dict:
"""The smallest radius that gives a connected graph with enough redundancy."""
viable = [r for r in sweep if r["connected"] and r["median_degree"] >= min_degree]
if not viable:
return {"margin": max(r["margin"] for r in sweep),
"note": "no radius in the sweep gave an adequately connected graph — "
"the imagery or the overlap is the limit"}
best = min(viable, key=lambda r: r["pairs"])
return {"margin": best["margin"], "pairs": best["pairs"],
"median_degree": best["median_degree"],
"note": "smallest radius meeting the connectivity requirement"}
Running that sweep takes seconds — it builds graphs rather than matching anything — and it replaces the most commonly guessed parameter in the whole pipeline with a measurement. On a survey where the answer turns out to be 1.0 rather than the usual 1.2, it also halves the matching time for nothing.
When positions are missing or wrong
Spatial pairing depends on camera positions, and two situations remove that dependency in different ways.
Positions absent entirely. Some datasets arrive with metadata stripped, or from aircraft that never recorded it. Appearance-based pairing is then the only option, and it works — it is what large-scale reconstruction from internet photographs uses — at the cost of being slower per image and needing a vocabulary tree built or supplied.
Positions present and wrong. More dangerous, because the pipeline trusts them. A survey with a hemisphere error, a datum mismatch or a handful of frames carrying the previous flight’s coordinates produces a spatial pair graph that excludes the pairs that genuinely overlap and includes pairs that do not. The reconstruction then fragments for reasons that appear to be about matching.
A cheap guard catches the second case before the pair graph is built: the positions of a survey should form a recognisable flight pattern, with consecutive frames a plausible distance apart.
import numpy as np
def sanity_check_positions(positions_enu: np.ndarray, *, capture_interval_s: float,
max_speed_m_s: float = 25.0) -> dict:
"""Do these positions look like a flight?"""
steps = np.linalg.norm(np.diff(positions_enu[:, :2], axis=0), axis=1)
implied_speed = steps / max(capture_interval_s, 1e-9)
problems = []
if (implied_speed > max_speed_m_s).sum() > 0.02 * len(steps):
problems.append(f"{(implied_speed > max_speed_m_s).sum()} steps imply "
"impossible speeds — some positions belong to another flight")
if float(np.median(steps)) < 0.5:
problems.append("consecutive frames are almost co-located — positions may be "
"truncated or quantised")
extent = positions_enu[:, :2].max(axis=0) - positions_enu[:, :2].min(axis=0)
if float(extent.max()) > 50_000:
problems.append(f"the survey spans {extent.max() / 1000:.0f} km — check for a "
"hemisphere or datum error")
return {"median_step_m": float(np.median(steps)),
"max_implied_speed": float(implied_speed.max()),
"problems": problems}
Running that before the pair graph turns a fragmented reconstruction into an ingest error, which is the same move this site makes everywhere: check the cheap property first, and fail where the fix is cheap.
Parameter deep-dive
| Parameter | Typical | Effect |
|---|---|---|
| Spatial radius | 1.2 × swath | Too small fragments; too large is quadratic again |
| Sequential window | 4 | Cheap; always include |
| Vocabulary tree candidates | 20–50 per image | Catches loop closures and cross-line ties |
| Pair cap | 500 per image | Bounds the runtime on dense surveys |
| Minimum degree | 8 | Below it, single failures disconnect images |
| Corridor line count | ≥ 2 | Turns a chain into a ladder |
| Cross-pass spacing | 300–500 m | Ties the corridor together |
| Submodel merge threshold | 20 shared points | Below it, merging is unreliable |
Verification and output inspection
import numpy as np
def matching_report(pairs: set, successful: set, n_images: int) -> dict:
"""How many candidate pairs actually matched, and where the failures are.
A low overall success rate is normal — the candidate list is deliberately
generous — but images whose pairs all failed are the ones that will be
dropped from the reconstruction, and they are worth naming.
"""
per_image = {i: 0 for i in range(n_images)}
for a, b in successful:
per_image[a] += 1
per_image[b] += 1
degrees = np.array(list(per_image.values()))
orphans = [i for i, d in per_image.items() if d == 0]
weak = [i for i, d in per_image.items() if 0 < d < 3]
return {"candidates": len(pairs), "matched": len(successful),
"success_rate": len(successful) / max(len(pairs), 1),
"median_degree": float(np.median(degrees)),
"orphans": orphans[:20], "orphan_count": len(orphans),
"weakly_connected": len(weak),
"healthy": len(orphans) == 0 and float(np.median(degrees)) >= 6}
Figure 3 — Three strategies, and the choice depends on the geotags.
Troubleshooting
Matching never finishes. The pair list is effectively exhaustive. Check that camera positions were read and that the spatial radius is derived from the footprint.
The reconstruction splits into submodels. The pair graph was disconnected, or matching failed along a weak section. Analyse the graph before matching next time.
A corridor survey drifts at the far end. A chain graph with no redundancy. Add a second line, cross passes and control along the length.
Some images are dropped entirely. They are orphans in the match graph — usually over water, bare soil or in a turn with motion blur.
Adding more candidate pairs does not help. The limit is the imagery rather than the selection. Look at feature counts per image before adding pairs.
Matching succeeds and the reconstruction is still weak. Pairs matched but with few inliers each. Check the inlier counts rather than the pair counts.