Feature Tracks & Correspondence Across Many Views

"I have been photographed from forty-three angles and recognized in all of them. My therapist says I should stop calling it surveillance and start calling it a track."

A Frequently Observed Corner Point

Chapter 13 ended with a complete two-view toolkit: match keypoints, estimate the essential matrix, recover pose, triangulate. Pointing that toolkit at a folder of two hundred photos raises three questions it cannot answer. Which of the 19,900 possible pairs are worth matching at all? Among the pairs we do match, which matches survive geometric scrutiny? And how do we discover that the corner of a windowsill detected in image 12 is the same corner detected in images 13, 47, and 181, when no single pairwise match connects 12 to 181 directly? The answers are, in order: pair selection, geometric verification, and track building. Together they convert a pile of images into the data structure every reconstruction algorithm actually consumes.

1. From Pairs to a Match Graph Beginner

The organizing object is the match graph (also called the scene graph or view graph): one node per image, one edge per image pair that shares verified correspondences, with the matches themselves stored on the edge. For a small collection the construction is brute force: detect and describe keypoints in every image once, then match every pair. The cost structure is worth internalizing immediately. Feature extraction is linear in the number of images $N$, but pairwise matching is quadratic: $\binom{N}{2}$ pairs, each costing a descriptor-space search. At $N = 200$ that is 19,900 matching problems; at $N = 10{,}000$ it is fifty million, which is why Section 5 below is about avoiding exhaustive matching entirely.

The listing below builds the verified match graph for a directory of photos with the tools you already own: SIFT detection from Chapter 10, ratio-test matching, and essential-matrix verification from Chapter 13, here with the camera intrinsics $K$ known from a Chapter 12 calibration.

import itertools
from pathlib import Path

import cv2
import numpy as np

paths = sorted(Path("scene").glob("*.jpg"))
sift = cv2.SIFT_create(nfeatures=4000)

feats = []                                   # per-image (keypoints, descriptors)
for p in paths:
    img = cv2.imread(str(p), cv2.IMREAD_GRAYSCALE)
    feats.append(sift.detectAndCompute(img, None))

K = np.array([[1200.0, 0, 960], [0, 1200.0, 540], [0, 0, 1]])  # from calibration
bf = cv2.BFMatcher(cv2.NORM_L2)

graph = {}                                   # (i, j) -> list of (kp_idx_i, kp_idx_j)
for i, j in itertools.combinations(range(len(paths)), 2):
    knn = bf.knnMatch(feats[i][1], feats[j][1], k=2)
    good = [m for m, n in knn if m.distance < 0.8 * n.distance]
    if len(good) < 30:                       # too little evidence: skip the pair
        continue
    pi = np.float32([feats[i][0][m.queryIdx].pt for m in good])
    pj = np.float32([feats[j][0][m.trainIdx].pt for m in good])
    E, inl = cv2.findEssentialMat(pi, pj, cameraMatrix=K,
                                  method=cv2.USAC_MAGSAC, threshold=1.5)
    if E is None or inl is None or inl.sum() < 30:
        continue                             # no consistent epipolar geometry
    keep = inl.ravel().astype(bool)
    graph[(i, j)] = [(good[t].queryIdx, good[t].trainIdx)
                     for t in np.flatnonzero(keep)]

n_pairs = len(paths) * (len(paths) - 1) // 2
print(f"{len(graph)} verified edges out of {n_pairs} candidate pairs")
# 214 verified edges out of 19900 candidate pairs

Note the shape of the printed result: out of nearly twenty thousand candidate pairs, a couple of hundred carry real geometric signal. A typical photo collection is sparse in exactly this way, because most image pairs simply do not overlap. The match graph makes that sparsity explicit and gives later stages a map of what connects to what: its connected components are the independently reconstructable pieces of the scene, and its edge weights (inlier counts) will drive the seed-pair and next-view choices of Section 14.2.

2. Geometric Verification: Edges You Can Trust Intermediate

The ratio test filters ambiguity, but as Chapter 10 warned, confidently wrong matches sail through it. The verification step in the listing above is therefore not optional hygiene; it is the difference between a match graph and a rumor mill. Fitting an essential matrix with RANSAC enforces the one constraint that binds all true matches in a pair: they must be consistent with a single rigid camera motion. Surviving inliers are matches that vote for the same epipolar geometry; everything else is discarded before it can poison the graph.

One refinement matters in practice. Some image pairs are related by a homography rather than general epipolar geometry: pairs that look at a flat wall, or pairs taken from nearly the same position with the camera merely rotated, the panorama case from Chapter 13. For such pairs an essential matrix is poorly determined and triangulation from them is hopeless, because rays from coincident centers never converge. Production systems fit both models, $E$ and $H$, and store which one explains the matches better (COLMAP records exactly this on every edge). A pair whose inliers are mostly explained by $H$ is kept for connectivity but flagged as a poor source of 3D structure, a flag that Section 14.2 will read when it chooses its initialization pair.

3. Stitching Matches into Tracks Intermediate

A pairwise match says keypoint $a$ in image $i$ corresponds to keypoint $b$ in image $j$. Matches are transitive in principle: if $(i,a) \leftrightarrow (j,b)$ and $(j,b) \leftrightarrow (k,c)$, then $(i,a)$, $(j,b)$, $(k,c)$ are all observations of one physical 3D point, even if images $i$ and $k$ were never matched against each other. The maximal sets obtained by closing this relation transitively are the feature tracks. Formally, build a graph whose nodes are (image, keypoint) pairs and whose edges are all verified matches; tracks are its connected components. Figure 14.1.1 shows the two layers of the construction side by side.

Computing connected components over a few million (image, keypoint) nodes calls for the classic union-find (disjoint-set) structure: near-constant-time merging with path compression. The implementation below also applies the one consistency filter no track builder should skip: a legitimate physical point can appear at most once per image, so any track containing two keypoints from the same image has merged two different 3D points via a bad match and must be rejected (or split, in more careful systems).

from collections import defaultdict

class UnionFind:
    def __init__(self):
        self.parent = {}
    def find(self, x):
        self.parent.setdefault(x, x)
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        self.parent[self.find(a)] = self.find(b)

uf = UnionFind()
for (i, j), pairs in graph.items():          # graph from the previous listing
    for a, b in pairs:
        uf.union((i, a), (j, b))             # node = (image index, keypoint index)

components = defaultdict(list)
for node in list(uf.parent):
    components[uf.find(node)].append(node)

tracks = []
for members in components.values():
    images = [im for im, _ in members]
    if len(members) >= 3 and len(set(images)) == len(images):
        tracks.append(sorted(members))       # consistent: one keypoint per image

lengths = np.array([len(t) for t in tracks])
print(f"{len(tracks)} tracks, mean length {lengths.mean():.1f}, max {lengths.max()}")
# 23741 tracks, mean length 4.6, max 41

The track-length histogram this prints is a diagnostic worth a glance on every dataset. Long tracks (a point seen in many views) are gold: they constrain many cameras at once and triangulate accurately. A healthy collection of a few hundred overlapping photos typically yields mean track lengths between 4 and 7. If almost everything has length 2, your pair selection is too sparse or your scene has little revisitation; if a few tracks have implausible lengths spanning unrelated parts of the collection, repeated structure is gluing distinct points together, which brings us to the failure modes.

4. Why Tracks Go Wrong Intermediate

Transitivity is the power and the danger of track building. One bad match anywhere in a chain welds two unrelated physical points into a single track, and the error propagates: a track contaminated in images 3 and 4 misleads triangulation in images 5 through 9. The classic culprits are repeated structure (identical windows, tiles, lampposts: the same trap flagged in Chapter 10, now with global consequences) and self-similar texture at low resolution. The single-image consistency filter above catches many such merges, because gluing two points usually eventually claims two detections in some image. The rest are caught downstream by geometric residuals: Section 14.2 discards track observations with large reprojection error, and the robust losses of Section 14.3 mute whatever survives.

5. Pair Selection at Scale Advanced

Exhaustive matching at $N = 10{,}000$ images means $5 \times 10^7$ pairs; at internet scale it is out of the question. The escape is to predict which pairs overlap before matching them, and three families of strategies cover practice. Sequential matching exploits capture order: in video or a walking capture, each frame is matched only against its $w$ temporal neighbors (plus occasional long-range checks for revisits), turning the quadratic cost linear. Retrieval-based matching treats pair selection as image search: compress every image into a compact global signature, query each image against the rest, and match only the top-$k$ most similar. The classical signature is the bag-of-visual-words vector over quantized descriptors, accelerated by a vocabulary tree; this is precisely the retrieval machinery that Chapter 16 develops in full, and its modern replacement is a learned global descriptor such as NetVLAD. Prior-based matching uses whatever side information exists: GPS tags, capture timestamps, or a previous coarse reconstruction.

All of this, extraction, matching, verification, and the bookkeeping database, is a solved engineering problem, and unless you are building a custom pipeline you should not rewrite it.