Structure from Motion

Take a dozen tourist snapshots of a cathedral. Every image is flat — a rectangle of pixels with no depth information. Yet a computer can, from those images alone, reconstruct a 3D point cloud of the building: the position of every stone corner, the lean of every column, even the rough distance between cameras.

The method is called Structure from Motion (SfM). The key insight is that motion creates parallax: when the same point in the world appears in two photos taken from different positions, the shift in its pixel location encodes the geometry of the scene. Collect enough of those shifts and you can solve for both the 3D positions of the scene points and the pose (position and orientation) of every camera — simultaneously.

There is a catch. The joint estimation of camera poses and scene geometry is a nonconvex optimization problem. The algorithm alternates between incremental reconstruction and a global refinement called bundle adjustment, whose cost landscape is riddled with local minima. Getting a globally good solution is not guaranteed, and the problem grows quickly as more images are added.

The demo below simulates the core SfM loop on a small synthetic scene. A set of 3D points defines the hidden world; virtual cameras snap 2D projections of those points; then the algorithm triangulates the observed correspondences and refines the result.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="scene-wrap">
  <canvas id="canvas" width="460" height="260"></canvas>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-add" type="button">{{btn_add}}</button>
  <button id="btn-ba" type="button">{{btn_ba}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend">
  <span class="dot true-pt"></span> {{legend_true}}
  <span class="dot recon-pt"></span> {{legend_recon}}
  <span class="dot cam-pt"></span> {{legend_cam}}
</div>

/* {{c_styles}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.scene-wrap { background: #eef2f6; border-radius: 10px; overflow: hidden; margin-bottom: .5rem; }
canvas { display: block; width: 100%; max-width: 460px; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; color: #1d3557; }
.status.ok { color: #0a7d33; }
.status.warn { color: #b45309; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.legend { font-size: .8rem; color: #555; display: flex; gap: .9rem; align-items: center; flex-wrap: wrap; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.true-pt { background: #2196f3; }
.recon-pt { background: #e63946; }
.cam-pt { background: #f4a261; }

// Code not found

Click Add camera to introduce a new viewpoint. Each new camera projects all scene points, adds Gaussian noise to mimic real-image uncertainty, and the system re-triangulates every correspondence. Click Run bundle adjustment to apply a gradient-descent refinement that minimizes reprojection error — notice how the noisy cloud tightens. Reset starts fresh. The asymmetry to note: adding one camera is cheap; refining the entire reconstruction jointly scales with the square of the total number of observations.

What makes SfM hard is not any one step — it is the joint recovery of all unknowns at once.

• Triangulation of a single point given known cameras is a simple linear problem: solve an over-determined system $Ax = 0$ in closed form.
• Camera pose estimation given known 3D points (the PnP problem) is also efficient: solved in $O(n)$ with RANSAC to handle outliers.
• Bundle adjustment — refining all camera poses and all 3D point positions simultaneously to minimize total reprojection error — is a large nonconvex least-squares problem. With $m$ cameras and $n$ points, the parameter vector has $6m + 3n$ entries and the Jacobian has $O(mn)$ rows.
• The standard solver is Levenberg-Marquardt (LM), which exploits the sparse block structure of the Jacobian to run in near-linear time per iteration. But LM only finds a local minimum; it can converge to a bad solution if the initialization is poor.
• Degenerate configurations (all cameras in a line, all points in a plane) make the problem rank-deficient; the reconstruction is then undefined up to a projective transformation.

SfM is not NP-hard in the classical decision-problem sense, but it belongs to the family of non-convex optimization problems where no polynomial-time algorithm is known to find the global optimum. The gap between "check a proposed reconstruction" (trivially linear) and "find the best one" (hard in practice) is the same philosophical divide as in P vs NP.

"Reconstruct geometry from images alone" is one of the most practically useful things a computer can do, and SfM is at the heart of it:

• Cultural heritage and archaeology: scanners like COLMAP and Agisoft Metashape let archaeologists create millimeter-accurate 3D models of sites, sculptures, and artifacts from photographic surveys — without touching the originals.
• Autonomous vehicles: self-driving systems build and maintain HD maps by running SfM offline on dashcam footage; the same structure is then used to localize the vehicle in real time.
• Augmented and virtual reality: the "spatial computing" inside devices like Apple Vision Pro depends on SfM-style continuous reconstruction to understand the room around you.
• Aerial surveying and GIS: drones fly a grid pattern over farmland or disaster zones; SfM fuses hundreds of images into orthophoto mosaics and digital elevation models used by agronomists and emergency managers.
• Medical imaging: SfM variants are used in endoscopy and surgical robotics to estimate the 3D shape of tissue from a moving camera.

The hard nonconvex core means every deployment involves heuristics, robust estimators, and careful initialization — a reminder that real-world non-convex optimization is as much engineering art as it is science.

Structure from Motion is a beautiful inversion: start from the shadows that 3D reality casts on flat sensors, and work backward to the world that cast them. Feature matching links images; triangulation gives rough depth; bundle adjustment pulls everything into a globally consistent shape — at the cost of solving a large, nonconvex least-squares problem with no polynomial-time guarantee of finding the best answer.

Every time your phone stitches a panorama, a drone produces a survey map, or a heritage scanner preserves a crumbling statue, that hard optimization is running quietly in the background. The 3D world is real; the algorithm that recovers it is doing something genuinely difficult, and understanding why it is difficult is the first step toward building systems that handle it gracefully.