Interactive guide · Part 16 of 20

Structure-from-Motion Pipelines

Every earlier part of this series built one piece of machinery in isolation — a fundamental or essential matrix between a pair (Part 6), a homography (Part 8), a triangulated point (Part 10), a resectioned camera (Part 11), a bundle-adjustment cost that cleans everything up at once (Part 15). A real system like COLMAP is the wiring diagram that turns those pieces into a pipeline: feed it an unordered folder of photos, and it has to decide which pairs overlap, where to start, how to grow one image at a time without drifting apart, and when to stop and re-optimize. This page is that wiring diagram, its "grow everything at once" alternative, and the honest fine print on what an uncalibrated reconstruction actually hands you before a further step called self-calibration is applied.

From "a folder of photos" to a reconstruction

Setup

Hand a real SfM system an unordered pile of JPEGs and it has no idea which ones overlap, in what order, or from where. Feature extraction and matching is the front end that this entire series has quietly assumed away — detect distinctive points in every image (SIFT, ORB, or a learned matcher) and match them pairwise — and it stays out of scope here; this page picks up exactly where a bag of candidate 2D–2D matches per image pair is already sitting on disk. What this page covers is everything from there to a globally consistent set of camera poses and 3D points: how to decide which candidate pairs are real, where to start, how to grow one image at a time without the whole thing drifting apart, a "grow everything at once" alternative, and what you actually get back when no camera was ever calibrated.

Geometric verification: from "probably overlaps" to "confirmed pair"

Stage 1 · turning matches into structure

Feature matching alone is naive — two images can share many "matches" that are pure coincidence (repeated texture, a matching algorithm's false positives) with no real geometric relationship behind them. Geometric verification is the fix: for every candidate pair, fit a fundamental matrix F (Part 6) or, if the shared scene is planar or the pair is a near-pure rotation, a homography H (Part 8) — both via RANSAC (Part 7), since the raw match list is full of outliers. A pair only survives if enough matches turn out to be RANSAC inliers of a consistent F or H.

inlier count(i, j) ≥ τ ⟹ keep the pair (i, j) as a real, geometrically-confirmed edge

This is the step that turns "these two images probably show the same place" into "these two images are related by an actual rigid geometric transform, and here is exactly which matches to trust." The surviving pairs and their inlier correspondences are the only raw material the rest of the pipeline touches — everything below assumes matches have already been verified this way.

⚠️ In real COLMAP-style systems this verification also has to guard against pure rotation or degenerate-planar pairs slipping through as if they were general 3D structure — exactly the epipolar-geometry degeneracies from Part 6. Those pairs aren't discarded outright (a homography fit still confirms they overlap), but they're flagged as unsuitable for the next step.

🎯 Learning goal: the view graph is the map the whole pipeline navigates. Every image pair either survives geometric verification (solid teal edge, thickness ∝ inlier count) or is rejected (faint gray dashed). Drag the verification threshold up and watch edges drop out — past the point where the graph splits into disconnected components, no single reconstruction is even possible, which is exactly why Steps 2–3 are graph problems.

Verification threshold: min inliers to accept a pair

Choosing the seed pair

Stage 2 · the one decision the whole reconstruction inherits

Incremental SfM needs to start somewhere: a single seed pair whose relative pose is recovered from E/F (Part 6/10), triangulated into the very first 3D points, and used to set the entire reconstruction's coordinate frame and scale. Every later camera and every later point is built relative to this pair, so a bad choice here can doom the whole reconstruction before it starts.

The naive criterion — "pick the pair with the most inlier matches" — is wrong on its own. A pair photographed from almost the same spot (near-pure rotation, or a tiny baseline) can have hundreds of clean inliers and still be nearly degenerate for triangulation: the two viewing rays to any 3D point are almost parallel, so a tiny bit of pixel noise swings the triangulated depth wildly (exactly the ill-conditioning Part 6 warns about for near-planar or near-rotation-only pairs). The real criterion balances two things at once:

score(i, j) = inliers(i, j), subject to median triangulation angle(i, j) > θ₀ (e.g. a few degrees)

i.e. among pairs with enough inlier matches, prefer the one with the widest baseline / largest triangulation angle — the angle at a 3D point between the two rays back to each camera — while still being well short of 180° (a pair that barely overlaps at all). Wide-enough-but-not-degenerate seed geometry is what gives the very first triangulated points, and therefore every PnP solve that follows, a stable numerical footing.

Growing the reconstruction, one image at a time

Stage 3 · the incremental loop

With the seed pair triangulated (Part 10), the pipeline repeats a loop until no image can be added:

1. Pick the next image with the most 2D–3D correspondences to already-reconstructed points
2. Register it: solve its pose via PnP + RANSAC against the growing 3D point set (Part 11)
3. Triangulate new points visible in this image and at least one already-registered image (Part 10)
4. Local bundle adjustment: refine just the newest camera and recently-added points (Part 15)
5. Periodically: global bundle adjustment over every camera and point so far (expensive, done less often)
6. Retriangulation: retry points that failed or triangulated poorly earlier — often because their baseline was too small back then — now that more views are available

Step 2 is the direct callback to Part 11: every new image is a fresh PnP problem, using the 2D–3D correspondences between its own feature matches and points already sitting in the reconstruction — no two-view geometry needed for it at all, only 3D structure the pipeline already trusts. Local BA (step 4) keeps each registration step cheap by only touching what just changed; global BA (step 5) is the expensive but necessary occasional cleanup that lets far-apart parts of the reconstruction correct each other, which purely local refinement never does.

💡 Why local and global BA: local BA alone is fast but myopic — errors it can't see (because they live in cameras it isn't touching) just sit there and compound. Global BA alone would be correct but far too slow to run after every single image. Real pipelines interleave both: local BA after most images, global BA every N images or when the reconstruction has grown by some fraction.

Working example: an incremental SfM run

Interactive

🎯 Learning goal: watch the seed-pair criterion actually get computed and chosen, then watch each new camera get resected by real linear PnP against the growing point cloud, with reprojection error tracked live.

A small synthetic scene — 22 scattered 3D points and 7 cameras swept along an arc, each with a limited image frustum so no single camera sees every point — stands in for a real photo set. Click Step to advance the pipeline one stage at a time, or Run to play it through: geometric verification (inlier counts + triangulation angle per pair, computed for real from the synthetic correspondences), seed-pair selection, seed triangulation, then for every remaining camera a real DLT-based linear PnP solve (build the 2n×11 design matrix from its 2D–3D correspondences to already-reconstructed points, solve by least squares, then project the recovered rotation onto the nearest true rotation matrix), followed by triangulating newly-visible points and a Gauss-Newton point refinement pass.

Drag to orbit, scroll to zoom.

true points unregistered cameras registered cameras reconstructed points

⚠️ What's simplified here: matches are the exact synthetic correspondences (no real feature matching or RANSAC needed, since nothing is an outlier), the seed pair's absolute pose is taken directly from ground truth rather than decomposed from E (Part 6/10 already cover that decomposition — re-deriving it here would just repeat that page), and both "local" and "global" BA in this demo refine only 3D point positions, holding camera poses fixed, to keep the linear algebra tractable in-browser. Everything else — the seed-selection scoring, the PnP solve, the triangulation, the point refinement, the reprojection-error readout — is computed live from the synthetic data on every step, not scripted.

How incremental SfM breaks

Honesty

The incremental loop's core weakness is baked into its structure: every registration step only ever corrects the image and points it's currently touching.

Drift. Each PnP solve and each local BA pass has some small residual error. Over a long chain of hundreds or thousands of images, those small errors don't cancel — they accumulate, and the reconstruction can slowly curve away from the true camera path even while every individual step looked fine in isolation.

Broken loops. Walk a camera around a building and eventually it comes back to where it started. If drift has accumulated along the way, the incremental reconstruction's "return" doesn't line up with its "start" — the loop doesn't close, leaving a visible seam. Fixing this needs either periodic global BA catching up (expensive, only a partial fix) or explicit loop-closure detection that recognizes "this new image is actually revisiting an old one" and adds that constraint directly — the same problem the SLAM literature (Part 19) deals with online, in real time.

🎯 Learning goal: register 12 cameras one at a time around a physical loop, using only noisy relative-pose "odometry" — exactly the incremental loop above, in plan view. Drift accumulates every step; the walk never ends where it started. Then trigger loop-closure detection: the revisit adds one constraint connecting the last camera back to the first, and a pose-graph relaxation redistributes the accumulated error around the whole loop instead of letting it pile up at the seam. Watch the drift-vs-camera-index curve collapse.

Left: top-down camera path. Black dashed = true circle; red = incremental registration with noisy odometry (the seam at the start/end is the broken loop); teal = after loop closure + pose-graph relaxation. Right: per-camera registration error vs. camera index, before (red) and after (teal) closure.

Odometry noise per step

Degenerate seed pairs. Since every later camera and point is built relative to the seed pair's frame and scale, a seed pair chosen with too narrow a baseline (Step 2 above) doesn't just produce a bad first triangulation — it can leave the whole reconstruction poorly scaled and numerically unstable from the very first image onward, with no later step able to fully undo it.

The alternative: global SfM

Solve for everything at once, not one image at a time

Incremental SfM's drift is a direct consequence of solving cameras in sequence. Global SfM avoids that by solving for every camera pose simultaneously, in two decoupled averaging stages run over all the pairwise two-view estimates at once, rather than growing a chain:

1. Rotation averaging — given many pairwise relative rotations R⁅₁⁆₂ (from two-view estimation on every verified pair), find one global rotation R⁅ per camera that best agrees with all of them: R⁅₁⁆₂ ≈ R⁅₂R⁅₁ᵗ
2. Translation averaging — given many pairwise translation directions t⁅₁⁆₂ (only a direction, not a scale — Part 10's two-view scale ambiguity, now showing up per-pair across the whole graph), solve for globally consistent camera positions/scale
3. One global triangulation pass, then a single global bundle adjustment — not many rounds of local BA

Both averaging stages are consensus problems: rotation averaging is essentially finding the point in the rotation group SO(3) that's closest, on average, to a whole graph of noisy pairwise rotation constraints, and it uses the same robust-loss ideas from Part 15's bundle-adjustment cost to keep a handful of bad pairwise estimates from corrupting the whole average.

⚠️ The trade-off, honestly: global methods never accumulate incremental drift, and both averaging stages parallelize far more easily than a strictly sequential incremental chain. But they're more exposed to outliers: one badly-estimated pairwise rotation gets averaged directly into the global solve instead of being locally contained the way a single bad PnP registration is in the incremental loop. And global methods have traditionally handled very unstructured or loosely-connected photo sets (lots of small disjoint clusters, weak overlap between them) less gracefully than incremental SfM's opportunistic "just add whatever connects next" growth.

Hierarchical SfM is the middle ground: reconstruct small, well-connected clusters of images independently — with either method — then merge the clusters pairwise into one global reconstruction. It gets some of global SfM's parallelism without demanding that the entire averaging problem be well-conditioned all at once.

Stratified reconstruction: what "uncalibrated" actually gets you

The missing chapter — projective, affine, metric

Everything above quietly assumed known camera intrinsics K. Drop that assumption and correspondences alone can no longer pin down the true, metric scene. A camera P⁅ and a point X̃ only ever interact through the product P⁅X̃, so replacing every camera with P⁅H₄⁻¹ and every point with H₄X̃ leaves every image measurement unchanged for any invertible 4×4 matrix H₄ — an uncalibrated reconstruction is only projective. Self-calibration claws that ambiguity back in two conceptual stages: locate the plane at infinity π∞ to reach an affine reconstruction, then pin down the absolute dual quadric Ω*∞ — whose image in every camera is (up to scale) that camera's inverse image of the absolute conic ω = K⁻ᵗK⁻¹ (Part 1) — to reach a metric one.

🎯 Full derivation: the actual self-calibration solve — recovering ω = K⁻ᵗK⁻¹ from images alone via Kruppa's equations / the absolute dual quadric, and upgrading the reconstruction to metric — is derived and demonstrated in Part 17.

Working example: projective vs. metric

Interactive

🎯 Learning goal: apply a genuine projective (not just affine) H₄ to both cameras and points at once, verify the reprojection error stays exactly zero, then watch a simplified known-K upgrade pull the shape back toward metric.

Six true cameras and a scattered cloud of 3D points are set up with known K. Apply H₄ injects a genuine projective distortion — a small plane-at-infinity vector v, so that X̃′ = H₄X̃ divides every point by v₳X + 1 — into both the cameras and the points at once, and recomputes reprojection error from scratch to prove it's still exactly zero. Upgrade (assume known K) then reconstructs a metric-ish shape from the distorted cameras alone, using nothing but the shared, known K.

Drag to orbit, scroll to zoom.

true (metric) projective (H₄ applied) upgraded

Distortion strength ‖v‖

⚠️ The simplified-but-real path taken here: the injected H₄ only ever moves the plane at infinity (a pure projective skew, not a general affine shear too), which leaves every camera's translation exactly recoverable and corrupts only its rotation column — a deliberately easy case. The upgrade step exploits that directly: it computes K⁻¹ times each distorted camera's linear part, projects the result onto the nearest rotation matrix (reusing the same nearest-rotation step from the PnP demo above), keeps the translation as-is, and retriangulates every point against the original, unchanged pixel observations using these corrected cameras. That is a real, working shortcut for this restricted case — not the general Kruppa/absolute-dual-quadric solve from the previous step, which would also need to handle affine shear and doesn't get to assume the distortion is small.

✓

Cheat sheet

Recap

Piece	What it is
Incremental pipeline	verify pairs (F/H + RANSAC) → pick seed pair (inliers + wide baseline) → triangulate seed → loop: PnP-register next image → triangulate new points → local BA → occasional global BA → retriangulate stragglers
Seed-pair criterion	most inliers subject to a large-enough triangulation angle — never the narrowest-baseline pair, however many inliers it has
Incremental failure modes	drift (small per-step errors compound over a long chain), broken loops (drift means a revisited viewpoint doesn't line up → global BA / loop closure), a degenerate seed pair poisoning the whole reconstruction's scale
Global SfM	rotation averaging (many pairwise R⁅₁⁆₂ → one R⁅ per camera) then translation averaging (many pairwise directions t⁅₁⁆₂ → global positions/scale), then one global triangulation + one global BA
Incremental vs. global trade-off	global avoids drift and parallelizes better, but one bad pairwise estimate corrupts the averaging directly, and it traditionally handles sparse/disjoint image sets less gracefully
Hierarchical SfM	reconstruct small well-connected clusters independently, then merge clusters — middle ground between incremental and global
Projective stratum	what correspondences alone give you with unknown K: true scene up to any invertible H₄ — P⁅X̃ = (P⁅H₄⁻¹)(H₄X̃) is unobservable
Projective → affine	pinned down by locating the plane at infinity π∞ (a transform is affine iff it fixes π∞)
Affine → metric	pinned down by the absolute dual quadric Ω*∞, whose image in each camera is (up to scale) ω⁻¹ = (K⁻ᵗK⁻¹)⁻¹ — ties straight back to Part 1's K/ω

Every piece is now on the table. The closing part places all of it in context: dense reconstruction, real-time SLAM, and the learned methods reshaping the field. Continue: beyond classical multi-view geometry →