Reconstructing the World: SfM, SLAM & Bundle Adjustment

From Two Views to Many

In Guide 3 we squeezed geometry out of exactly two photos: given matched points across a left and right image, the epipolar constraint let us recover how the two cameras were posed relative to each other and triangulate a handful of 3D points. That is a beautiful result, but it is also tiny. A real landmark — a cathedral, a statue, a mountain face — is captured in hundreds of photos taken by different people, from different angles, at different times of day, in no particular order. The question of this guide is: how do we turn that messy pile of images into a single, coherent 3D model?

The answer is Structure from Motion (SfM). The name is literal: as a camera "moves" around a scene, the way points shift between images encodes both the structure (where the 3D points are) and the motion (where every camera was). The output is two things at once: the pose of every single camera, and a point cloud — a set of 3D coordinates of the scene's surface points. Recovering that geometry from raw photos is exactly what we mean by 3D reconstruction, and SfM is the classical engine that does it.

The dominant strategy is incremental SfM: rather than solving for all cameras at once, we grow the reconstruction one camera at a time, like building a jigsaw outward from a confident first piece. Below is the whole pipeline as a narrative. The later sections of this guide then zoom into the genuinely hard parts — the optimization that keeps it all honest (bundle adjustment) and the step that fills it in densely (multi-view stereo).

Detect & match features. In every image, find repeatable keypoints (corners, blobs) and describe each with a vector. Match these descriptors between image pairs to guess which pixels in different photos are the same physical point.
Initialize from a good pair. Pick two images with many reliable matches and a wide-enough baseline, and run the exact two-view geometry from Guide 3 to recover their relative pose and triangulate a first batch of 3D points.
Register the next camera. Find an unused image that sees many of the 3D points we already have. Because we know both the 3D points and where they appear as pixels in this new image, we can solve directly for the new camera's pose (this is the PnP / resectioning step).
Triangulate more points. With the new camera placed, any matches it shares with earlier cameras that are not yet in the model become new 3D points, growing the cloud.
Refine and repeat. Periodically clean up errors with bundle adjustment (Section 3), then loop back to register the next camera until every usable image is in.

Feature Tracks Across Images

SfM is only as good as the correspondences it is fed, so let's look at the raw data it runs on. Earlier computer-vision guides introduced feature detectors and descriptors such as SIFT: algorithms that find distinctive, repeatable keypoints in an image and summarize the neighborhood around each one as a vector (a descriptor) engineered to stay roughly the same when the viewpoint rotates, the camera moves closer, or the lighting changes. That invariance is the whole point — it lets the same real-world corner of a window produce a near-identical descriptor in two photos taken minutes and meters apart.

Now define the key object: a feature track. A track is one physical 3D point as seen across many images, chained together through pairwise matches. If keypoint A in image 1 matches keypoint B in image 2, and B matches keypoint C in image 3, then A–B–C form one track — a single thread following that one window corner through the whole photo collection. Think of CCTV: to follow one person through a building you don't need a single magic camera; you stitch together the same person spotted in frame after frame from different cameras. A feature track is exactly that, but the "person" is a fixed point on a surface and the "cameras" are your photos.

There is a catch: descriptor matching is heuristic and produces plenty of wrong matches — two different windows on a repetitive façade can look almost identical. A wrong match poisons a track and drags the whole reconstruction off. The fix is geometric verification. For each candidate image pair we estimate the fundamental matrix from Guide 3 inside a robust RANSAC loop: matches that obey the epipolar constraint (each point lies near its partner's epipolar line) are kept as inliers; matches that violate it are thrown out as outliers, no matter how similar their descriptors looked. Only matches that survive this geometric test are trusted enough to build tracks from.

Bundle Adjustment: The Optimization Heart

Incremental SfM has a quiet disease: it accumulates error. Each new camera is registered against points that were themselves estimated from earlier, slightly-imperfect cameras. Tiny mistakes compound, and after a hundred cameras the model can bend or drift noticeably — straight walls bow, a loop of cameras around a statue fails to close. The cure is bundle adjustment (BA): instead of trusting the chain of incremental estimates, we step back and jointly refine every camera's parameters and every 3D point's position at once, by a single global criterion.

That single criterion is the reprojection error. Here is the picture behind the name: from each 3D point, draw the ray of light that travels to a camera and lands on its image plane as a pixel — the predicted projection. We also have where that point was actually observed (the feature track told us). The gap between predicted and observed pixel is the error. "Bundle" refers to the bundle of rays leaving each 3D point toward all the cameras that see it; we "adjust" the cameras and points so every bundle converges as tightly as possible onto the real observations.

\min_{\{K_j,R_j,t_j\}_j,\;\{X_i\}_i}\;\sum_{i}\sum_{j}\bigl\lVert\, x_{ij}-\pi\!\left(K_j,R_j,t_j,X_i\right)\bigr\rVert^{2}

Bundle adjustment minimizes total squared reprojection error over all points and all cameras at once.

Let's unpack every symbol. X_i is the i-th 3D point in the world (three numbers, its xyz coordinates). Camera j is described by its intrinsics K_j (the focal length and principal point from Guide 1 — how it turns directions into pixels) and its pose (R_j, t_j) (a rotation R_j and translation t_j saying where the camera sits and which way it faces). The function \pi(\cdot) is the projection function from Guide 1: it takes a world point, moves it into camera j's frame, and flattens it through the lens into a predicted pixel. x_{ij} is where point i was actually observed in image j (a 2D pixel from the feature track). The norm \lVert\cdot\rVert measures the pixel distance between prediction and observation, and we square it. The double sum \sum_i\sum_j runs over every (point, camera) observation in the whole dataset — every rung of every track. Crucially, the \min is taken over both sets of unknowns at once: all the 3D points \{X_i\} and all the camera parameters \{K_j,R_j,t_j\} are nudged together to drive the total mismatch down.

A concrete feel for the numbers: suppose a 3D point currently projects to pixel (102, 247) in some image, but the feature track says it was actually observed at (100, 250). The residual is (2, −3), contributing 2^2+3^2 = 13 squared pixels to the sum. With a million such observations, the total might start in the millions; a successful BA might pull the average residual below one pixel, so each point sits almost exactly where every camera saw it. Because \pi is nonlinear (it divides by depth), this is a giant nonlinear least-squares problem, solved iteratively with the Levenberg–Marquardt algorithm — a method that blends gradient descent (safe, small steps when far off) with Gauss–Newton (fast, big steps when close), so it converges robustly.

Why is this even tractable when there can be tens of thousands of cameras and millions of points — millions of unknowns? The saving grace is sparsity. Each LM step solves a linear system built from the Jacobian (the matrix of how every residual changes with respect to every unknown). But each 3D point appears in only a handful of cameras, and each camera sees only a slice of the points — so almost every point-camera pair contributes nothing, and the Jacobian (and the resulting normal-equation matrix) is overwhelmingly zeros. Solvers exploit this with the Schur complement trick: because the point block of the matrix is block-diagonal (points don't directly couple to each other, only through shared cameras), you can cheaply eliminate the millions of point variables first, leaving a much smaller dense system in just the camera parameters to solve, then back-substitute for the points. That single structural fact is what turns an impossible problem into a routine one.

# Bundle adjustment as nonlinear least squares (conceptual pseudocode).
# Unknowns: poses (R, t) and intrinsics K for each camera, plus every 3D point X.

def residuals(cameras, points, observations):
    r = []
    for (i, j, x_obs) in observations:          # point i seen in camera j at pixel x_obs
        x_pred = project(cameras[j], points[i]) # pi(K_j, R_j, t_j, X_i) -> predicted pixel
        r.append(x_obs - x_pred)                # 2D reprojection residual
    return stack(r)

# Solve with Levenberg-Marquardt; the optimizer needs the Jacobian J = d(residuals)/d(unknowns).
# J is SPARSE: residual (i, j) depends ONLY on point i and camera j, nothing else.
solution = levenberg_marquardt(
    residual_fn = residuals,
    init        = (cameras, points),
    jacobian    = sparse_jacobian,   # exploit block structure
    linear_solve = schur_complement, # eliminate the many point vars first, solve for cameras
)
# Objective being minimized:  sum over observations of || x_obs - project(cam, X) ||^2

BA in skeleton: define the reprojection residuals, then let Levenberg–Marquardt minimize their squared sum using the sparse Jacobian and the Schur complement.

Going Dense: Multi-View Stereo

After SfM and bundle adjustment, what exactly do we have? Extremely accurate camera poses and intrinsics — but only a sparse point cloud, because we placed one 3D point per feature track, and tracks live only at distinctive keypoints (corners, textured spots). The flat wall between two windows produced no keypoints, so it is simply empty in our cloud. That is fine for knowing where the cameras were, but useless as a model of the surface. To get a model you can render or 3D-print, we need a point at (nearly) every pixel.

Multi-view stereo (MVS) is the step that fills it in. Its key move is to freeze the camera poses that SfM worked so hard to compute, and treat them as ground truth. With the cameras fixed, MVS computes a dense depth for almost every pixel, fusing evidence from many overlapping views. The most direct way to picture this is as Guide 2's stereo, generalized: in Guide 2 we had a tidy left/right rig with known geometry; MVS does the same triangulation, but using your many arbitrary photos, now that SfM has told us exactly where each one was taken from.

How does it actually find depth without matched keypoints? By testing hypotheses and checking photo-consistency. For a given pixel in a reference image, MVS guesses a depth, which places that pixel at a specific 3D location; it then projects that 3D location into the neighboring views (using their known poses) and asks: do the small image patches around all those projected positions actually look alike? If yes, the depth guess is probably right; if the patches clash, it's wrong. Modern methods like PatchMatch make this efficient by not testing every depth blindly: they start from random guesses, then propagate good depths to neighboring pixels (surfaces are mostly smooth, so a pixel's correct depth is usually close to its neighbor's) and randomly refine, converging fast to a depth map per image.

Each image thus yields its own depth map — its own per-pixel depth estimate. The final move is depth-map fusion: back-project all those per-image depths into 3D, where they should agree, and merge them into one consistent dense point cloud, rejecting points that only one view believes in and averaging out the noise where many views agree. The result is the dense 3D reconstruction — millions of points blanketing the surface rather than thousands at corners.

SLAM: Reconstruction in Real Time

Everything so far has been offline: gather all the photos first, then grind through SfM, BA, and MVS at leisure. But a robot, a drone, or an AR headset cannot wait. It needs to understand the world as it moves through it, right now. That is the job of visual SLAM — Simultaneous Localization And Mapping. The name states the chicken-and-egg bind precisely: to know where you are (localization) you need a map, but to build a map you need to know where you are. SLAM does both at once, online, frame by frame, from a camera moving through an unknown environment.

It helps to contrast SLAM with SfM head-on, because geometrically they are siblings — both estimate camera poses and 3D structure from images by minimizing reprojection error. The difference is the constraints they live under. SfM is batch and offline: it sees every image up front, can process them in any order, and can afford an expensive global bundle adjustment. SLAM is sequential and latency-bound: frames arrive in time order, it cannot peek at the future, and it must return a pose for the current frame within milliseconds or the robot crashes. SLAM trades some of SfM's accuracy and global optimality for the one thing SfM cannot offer — answers right now.

To meet that deadline, SLAM splits the work into two threads running in parallel. Tracking runs on every incoming frame and does the fast job: estimate the camera's pose right now by matching the frame against the current map. Mapping runs slower in the background and does the heavy job: extend and refine the 3D map. The bridge between them is the keyframe — rather than mapping from all 30 frames per second (mostly redundant), SLAM promotes only occasional frames that add genuinely new viewpoint as keyframes, and builds the map from those.

Two more pieces make SLAM robust over long journeys. First, a local (windowed) bundle adjustment runs continuously over just the most recent handful of keyframes and the points they see — the same reprojection-error optimization from Section 3, but small enough to finish in real time, keeping the recent estimate tight without re-solving the entire history. Second, and critically, loop closure: as you wander, small errors accumulate into drift, so when you return to a place you've seen before, your estimated position has slowly slid away from the truth. A loop-closure detector recognizes the revisited scene ("I've been here!"), adds a constraint linking now to then, and a global optimization snaps the whole trajectory and map back into alignment — folding the drift away in one correction.

From Points to Surfaces

MVS hands us a dense point cloud — millions of 3D points blanketing the surface — but a cloud is still just disconnected dots. It has gaps between points, no notion of inside versus outside, and nothing to catch the light. The last classical step is meshing: converting those points into a watertight surface, a connected web of triangles with no holes, that genuinely separates solid from empty space.

The standard tool is Poisson surface reconstruction, and its intuition is elegant. Alongside each point we have (or can estimate) a surface normal — the little arrow saying which way the surface faces, i.e. which side is "outside." Poisson reconstruction looks for a single smooth surface whose own normals agree, everywhere, with that field of measured normals. Picture all those tiny arrows as a wind blowing outward from the true surface; Poisson finds the one watertight skin that everywhere points along the wind. Because it solves for one global smooth surface, it naturally bridges small gaps and smooths away noise, giving a clean mesh rather than a fuzzy blob.

A bare grey mesh still doesn't look real, though — it has shape but no skin. The finishing step is texturing: for each triangle, we look back at the original photos that saw it (we still have every camera's pose from SfM!), pick the views with the best, least-distorted look at that patch, and paste the actual image colors onto the surface. Stitched and color-balanced across hundreds of source photos, the result is a photoreal 3D model you can spin around and light from any angle.

Calibrate (Guide 1): model how each camera turns 3D directions into pixels — its intrinsics and the projection function π.
Match (Guide 2 & this guide): detect features, match them across images, and chain reliable matches into geometrically-verified feature tracks.
Two-view geometry (Guide 3): from a good initial image pair, recover relative pose via the epipolar constraint and triangulate the first 3D points.
SfM + bundle adjustment (this guide): add cameras one by one (PnP), triangulate more points, and jointly refine everything by minimizing reprojection error.
Multi-view stereo (this guide): freeze the poses and compute a dense per-pixel depth, then fuse the depth maps into a dense point cloud.
Mesh + texture (this guide): reconstruct a watertight surface (Poisson) and paint it with colors from the source photos for a photoreal model.

Step back and notice what we've built across Guides 1–4: a complete, explicit, geometric path from a folder of ordinary photos to a textured 3D model — every stage justified by camera geometry, every number something you could point at and explain. This is classical multi-view geometry at its mature best. The final guide in this track takes a different bet: instead of representing the scene as explicit points, meshes, and triangulated geometry, it learns a representation — neural networks for 3D reconstruction that predict depth, and scene encodings like NeRF and Gaussian Splatting that store the whole world as optimized parameters. They keep the camera geometry you learned here, but replace the points-and-surfaces machinery with something learned. Same goal, new tools — that's where we head next.