[CV] 7. Structure from Motion(SfM)

What is Structure from Motion (SfM), and how is it different from camera calibration and triangulation?

Structure from Motion (SfM) reconstructs a 3D scene and camera poses using only multiple 2D images.

The difference is what each method already knows:

*table in pict

→ SfM is harder because it must estimate camera motion and 3D structure together

What are the inputs and outputs of SfM and why is it called “Structure from Motion”?

• Input: multiple images of a static scene, taken from different viewpoints

• Outputs:

  • Camera poses : where each camera is and how it is oriented

  • 3D point cloud: the reconstructed positions of scene points

• It is called as Structure from Motion because changing camera viewpoints provide information about the scene’s 3D structure

• No known checkerboard or 3D measurements are required

What do Photo Tourism and city-scale reconstruction demonstrate about SfM?

They show that SfM can reconstruct 3D scenes from large, unordered photo collections.

• Photo Tourism(2006): Combined thousands of tourist photos of landmarks into 3D reconstructions that users could explore

• Building Rome in a Day(2009):Reconstructed Roman landmarks using approximately 150,000 photos and parallel computing

• Reconstructing the World in Six Days(2015): Scaled reconstruction roughly 100 million images

Lesson: SfM works not only with controlled videos but also with large, uncontrolled internet photo collections

What is the mathematical problem formulation of SfM?

Suppose we have m images observing n fixed 3D points.

The projection relationship is:

*form in pict

Goal: Estimate all m camera matrices and n 3D points, so their projection match the observed pixels

→ the difficulty is that both P and X are unknown

What is scale ambiguity in SfM, and why can’t images alone determine the real-world scale?

Scale ambiguity: SfM can recover a scene’s shape but not its actual physical size

• for example: a reconstructed building could be 10 meters or 100 meters tall while producing the same images if the whole scene and camera positions are scaled together

• *form in pict

  for a simple scale transformation, Q scales the scene

• Why? Images contain no absolute distance reference

• Solution: use a known distance, object size, or GPS information to establish real-world scale

What is the general transformation ambiguity in SfM?

SfM can produce different 3D reconstructions that still explain the same 2D images.

• If we transform the 3D points using an invertible matrix Q, and adjust the cameras using its inverse:

  *form in pict

the projected pixels remain unchanged.

Meaning: Images alone cannot always tell us which transformed reconstruction is the original one.

Depending on camera constraints, this produces projective, affine, or similarity ambiguity.

What is projective ambiguity, and what geometric properties does it preserve?

Projective ambiguity occurs when we have no camera calibratin constraints

• the reconstruction can be transformed using any invertible 4×4 matrix Q

• It preserves:

  • Straight lines

  • Which points lie on the same lines or planes(incidence)

• It does not necessarily preserve:

  • parallel lines

  • Angles

  • Distances

• Example: A cube may become distorted, skewed shape while still producing the same images

What is affine ambiguity and how is it different from projective ambiguity

Affine ambiguity: allows the scene to be stretched, sheared, rotated, or translated while preserving parallelism

*form in pict

• It preserves:

  • Parallel lines

  • Ratios of lengths along the same line

  • Straight lines

• But it does not necessarily preserve angles or actual distance

• Different: Affine reconstruction keeps more geometric information than projective reconstruction

What is similarity ambiguity, and why is it closer to the true 3D scene?

Similarity ambiguity : the reconstructed scene has the correct shape and proportions, but may differ in scale, rotation, and position.

*form in pict

• It preserves angles and relative proportions.

• Example: A building looks correctly shaped, but its reconstructed height might be 1 unit instead of 10 meters.

→ This is the usual ambiguity remaining in calibrated SfM.

What is the hierarchy of ambiguities in SfM?

The hierarchy goes from least geometric information preserved to most:

*table in pict

Key idea: Stronger camera or scene constraints reduce ambiguity.

Most practical SfM systems recover a scene up to similarity, unless additional measurements fix its absolute scale.

What is the difference between Affine SfM and Projective SfM?

Remember: Affine SfM is easier mathematically, while Projective SfM is more general and widely used.

Why is Affine SfM a good approximation for distant scenes?

When a scene is far from the camera compared with its own size, the depth differences between its points have a relatively small effect on their projected size.

Therefore, we can approximate the camera using parallel projection instead of full perspective projection.

This makes the equations linear and easier to solve.

Why is SfM described as a "chicken-and-egg" problem?

To triangulate 3D points, we normally need known cameras.

But to estimate cameras through ordinary calibration, we normally need known 3D points.

In SfM, neither is known.

Therefore, SfM must use relationships between multiple images to estimate both, then improve them together.

Why does SfM usually reconstruct a scene only up to scale, even when the camera geometry is accurate?

Accurate relative camera geometry tells us the shape and relative positions of objects, but not their real-world units.

For example, SfM may correctly estimate that one wall is twice as long as another, without knowing whether they measure 2 and 4 meters or 20 and 40 meters.

To recover absolute scale, we need an external measurement such as a known distance or GPS.

What is the general affine projection equation, and how does it differ from perspective projection?

In affine camera projects a 3-D point using:

$$x=AX+t$$

where:

• $x$: 2D image point

• $A$: 2×3 projection matrix

• $X$: 3-D point

• $t$: 2-D translation

Unlike perspective projection, there is no division by depth

Why important? This makes affine projection linear, allowing SfM to use matrix factorisation

What is the Affine SfM problem formulation?

Given m images observing n 3D points:

*form in pict

• We know only the observed 2D pixel positions

• The reason is unique only up to an affine transformation, which has 12 degrees of freedom(DoF)

How do we count the knowns and unknowns in Affine SfM?

Each 2D correspondence gives two known values : x and y

• For m images and n points:

  • Knowns:$2mn$

  • Camera unknowns: $8m$ → 6 matrix values + 2 translation values per camera

  • 3-D point unknowns: $3n$

  • Affine ambiguity: 12 DoF

• Therefore, the necessary counting condition is:

  $$2mn\=> 8m+3n-12$$

• Example: With 2 views, at least 4 point correspondences are needed by this count

• Purpose: Check whether enough observations exist to potentially solve the problem. It does not guarantee a unique solution in every camera configuration

What is the first step in Affine SfM, and why do we center the data?

Step 1: Centre the observed 2D points

For each image:

1. Calculate the centroid(average position) of its observed points

2. Subtract the centroid from every point in the image

→ Why? This removes the translation term from the affine equations, leaving a simple linear relationship between centered 2D and 3D points

Remember: Centering removes the translation component before matrix factorisation

Second step : What is the measurement matrix D in Affine SfM, and how is it constructed?

Step 2: Build the measurement matrix D

Stack the centered 2D observations from all images into one matrix

• Each image contributes 2 rows: x and y coordinates

• Each 3-D point contributes 1 column

• therefore, the matrix can be written as $D=MS$

  where:

  • M : Camera motion matrix, size 2m x 3

  • S: 3-D shape matrix, size 3xn

• Goal: Separate the observed image data into camera motion and 3D structure

Why must the Affine SfM measurement matrix have rank at most 3?

$$D=MS$$

where:

• M has only 3 columns

• S has only 3 rows

Therefore:

$$rank(D) \=< 3$$

Meaning: Even with many images and points, ideal affine observations depend on only 3 underlaying 3-D dimensions. Real measurements contain noise, so D may have a higher numerical rank

→ Solution: Use SVD to find its best rank-3 approximation

3rd Step: How does SVD recover camera motion in 3-D structure in Affine SfM?

Step 3: Factorise D using SVD

*form in pict

The process is:

1. Apply SVD to the measurement matrix

2. Keep only the 3 largest singular values and their singular vectors

3. Discard the remaining components as noise

4. Split the retained factors to estimate M (camera motion) and S (3D shape)

SVD separate the 2D measurements into estimates of camera motion and scene structure

→ This is the Tomasi–Kanade factorization method (1992).

Why is the Affine SfM factorisation not unique?

*form in pict

Meaning: Different camera-motion and 3D-shape matrices can explain the same image measurements.

→ This is the remaining affine ambiguity.

• After centering removes translation, the unresolved 3×3 transformation has 9 DoF.

→ Solution: Add metric constraints, such as orthonormal camera axes, to reduce the ambiguity toward similarity.

What happens when some 3D points are not visible in every image?

The measurement matrix D will contain missing entries

This happens when points are:

• Occluded by other objects

• Outside a camera’s field of view

→ ordinary complete-matrix factorization assumes all measurements are present

→ Solution: use low-rank matrix completion to estimate missing values while maintaining the low-rank structure

This is sometimes called the Netflix problem, because a similar mathematical problem occurs when predicting missing ratings

What is Projective SfM, and how is it formulated?

Projective SfM reconstructs camera matrices and 3D points using the full perspective camera model

*form in pict

Unlike Affine SfM, Projective SfM includes perspective effects.

→ However, without calibration constraints, the reconstruction remains ambiguous under a general 4×4 projective transformation

How are degrees of freedom counted in Projective SfM?

For m images and n points:

• Knowns: 2mn

• Camera unknowns: 11m - 11DoF per projective camera

• 3D points using unknowns: 3n

• Projective ambiguity: 15 DoF

The necessary counting condition is:

$2mn \=> 11m+3n-15$

Example: With 2 cameras, at least 7 correspondences are needed by this count.

Why important? It explains why enough images and matching points are necessary.

What is the main difference between Global SfM and Incremental SfM?

Global SfM:

• estimates reliable relative poses between image pairs first

• Combine them to estimates all camera poses together

• The reconstruct and refine the scene

Incremental SfM:

• Starts with 1 image pair

• Builds an initial 3D reconstruction

• Adds 1 camera at a time, triangulating and refining as it grows

→ Difference: Global SfM solves camera poses jointly; Incremental SfM builds the reconstruction step by step

What is the first step of the Global SfM pipeline?

The first step is feature detection and matching

1. Detect local features such as SIFT in each image

2. Describe the features using descriptors designed to tolerate viewpoint and lighthing changes

3. Match similar descriptors between image pairs

4. Use RANSAC and the fundamental matrix F to reject incorrect matches

Goal: Find reliable 2D correspondences before estimating camera geometry

What are correspondence tracks and why are they needed?

Correspondence track connects observations of the same 3D point across multiple images

Example:

• Image 1 point A matches Image 2 point B

• Image 2 point B matches Image 3 point C

• All 3 are combined into one track

→ Each track represents 1 unknown 3D point, with multiple 2D observations

→ Why important? SfM needs to know which pixels across many images belong to the same scene point, not just which pixels match in one pair

How does Global SfM estimate pairwise relative camera poses ?

For N images, there are at most:

$[N(N-2)] /2$ possible image pairs

• However, only pairs with enough reliable overlap are useful

• For each reliable pair:

  1. Find and verify feature correspondences

  2. Estimate the essential matrix E

  3. Decompose E to recover the relative rotation R_ij and translation direction t_ij

• Result: A collection of relative camera poses

• These are still pairwise estimates, not yet one consistent global reconstruction

What is rotation and translation averaging and why is it needed?

Pairwise pose estimates describe camera relationships 2 cameras at a time

• Because of noise, these relationships may disagree

• Rotation and translation averaging combines them into one globally consistent camera configuration

  • Rotation averaging: Estimates a global orientation fir every camera

  • Translation averaging: Estimates consistent camera positions from relative translation directions

→ Goal: make all cameras agree within one shared coordinate system

What is rotation averaging and why can’t pairwise rotations be inconsistent?

Rotation averaging estimates one global rotation for each camera using many noisy pairwise rotations

• For example, rotating from camera 1 to 2, then 2 to 3, should agree with the direct rotation from 1 to 3

• But noise can cause:

  $R\_12 R\_13$ $≠$ $R\_13$

Goal: find global rotations that best satisfy all pairwise relationships

→ This produces a more consistent set of camera orientations

How does rotation averaging measure disagreement and solve it?

Ideally, the measured relative rotation agrees with the rotations predicted by the global camera poses:

*form in pict

This measures the difference between two rotation matrices.

Overall process:

1. Minimize the squared disagreements across camera pairs.

2. Use a linear approximation to obtain initial rotations.

3. Project the results back to valid rotation matrices using SVD.

4. Refine them on the rotation space SO(3) using small iterative corrections.

5. Use robust losses, such as Huber, to reduce the effect of incorrect pairwise estimates.

→ Remember: Rotation averaging makes noisy camera orientations globally consistent.

What is translation averaging and why is it difficult?

Translation averaging estimates the global positions of all cameras

• The difficulty is that the pairwise translation estimates usually provide only a direction, not the true distance

• For example: we may know camera B is tothe right of camera A, but not exactly of how many meters away

• Different image pairs also contain noise and unknown local scales

• Goal: combine these direction constraints into one consistent camera layout

How does the cross-product trick help translation averaging?

Let:

• $c_i,c_j$ : Global positions of two cameras

• $t_j$ : Observed direction between them

The vector connecting the cameras should be parallel to $t\_ij$

Parallel vectors have a cross product of zero:

$t\_ij$ x $(c_j-c_i)=0$

Why useful?

• Removes the need to know the distance between the cameras.

• Produces equations linear in camera positions.

• Allows many camera-pair constraints to be solved together.

What is gauge freedom in translation averaging and how is it resolved?

Gauge freedom: estimated camera layout can be shifted or scaled without changing the observed relative directions

The lecture identifies:

• 3DoF for global translation

• 1DoF for global scale

Solution:

1. Fix one camera at the origin

2. Set the distance to a second camera to 1 unit

3. Estimate all other positions relative to these choices

→ These constraints choose a consistent reference frame; they do not reveal the real-world scale

How does BA complete Global SfM, and what are its advantages and disadvantages?

After estimating the global camera poses and reconstructing 3D points, BA refines them together

It minimizes reprojection error:

*form in pict

BA needs a good initial estimate because the optimization is non-convex

• Global SfM advantages:

  • Less drift, since camera poses are solved jointly

  • Less dependent on a particular starting image pairs also

  • Suitable for large, unordered photo collections

• Disadvantages:

  • sensitive to inaccurate pairwise pose estimates

  • Global nonlinear optimization can be difficult

What are the complete steps of Incremental SfM?

Incremental SfM reconstrust the scene 1 camera at a time

Steps:

1. Select an initial image pair with many reliable matches and a suitable baseline

2. Initialize intrinsics K using available EXIF metadata, such as focal length

3. Estimate relative pose R and t using the five-point algorithm

4. Triangulate matching points to build the first 3D model

5. Choose the next image with strong matches to the existing model

6. Register the new camra using RANSAC, then triangulate new points

7. Run bundle adjustment to improve the growing reconstruction

8. Repeat until the desired images are registered

→ Optionally, use GPS or ground control pints to align the final model with real-world coordinates

Remember: Initialize → Triangulate→ Add camera → Refine →Repeat

How should we choose the initial image pair in Incremental SfM?

We need both many reliable matches and good baseline

Why?

• many matches help stimate camera pose reliably

• A suitable wider baseline improves triangulation accuracy

→ Ideal choice: A pair with good overlap and sufficient camera separation

What is the next-best-viewed problem in Incremental SfM?

The next-best-viewed problem is deciding which image to add next to the growing reconstruction

Too similar to existing views:

• provides little new 3D information

• May produce uncertain triangulation

Too different:

• may have too few matching features

• Make camera poses estimation unreliable

Good strategy: Choose an image that observes many already-triangulated points and provides useful new geometry

→ Why important? A poor choice can introduce errors that affect later reconstruction steps

What are the main challenges that can cause Incremental SfM to fail?

Common problems include:

1. Degenerate camera configurations

   • Pure camera rotation or planar scenes can be explained by a homography

   • They may not provde enough information for reliable 3D reconstruction

2. Incorrect matches

   • some outliers survive pairwise RANSAC but become inconsistent across additional views

3. Repetitive structures

   • Similar windows , columns, or tiles may be matched incorrectly

4. Drift

   • Small camera-pose errors accumulate as more images are added

5. Loop closure

   • Previously visited locations may no longer align because of accumulated drift

→ Incremental SfM must control errors at every step because mistakes can spread through reconstruction

Why can repetitive structures cause catastrophic SfM failures?

Repeated objects, such as identical windows or columns, can look almost the same in different parts of a building.

• The algorithm may match a feature to the wrong repeated object.

• These incorrect matches may even pass RANSAC if they are geometrically consistent within an image pair.

→ Result: The reconstructed building may become folded, distorted, or incorrectly connected.

→ Solution: Detect and down-weight ambiguous repetitive matches before they affect the 3D model.

What are drift and loop closure in Incremental SfM?

• Drift happens when small camera-pose errors accumulate over many reconstruction steps.

  • Example: A camera moves around a building and returns to its starting location, but the estimated final position does not match the original one.

• Loop closure corrects this by:

  • Detecting that a previously visited place has been seen again.

  • Matching the current image with an earlier image.

  • Adding constraints between these distant parts of the trajectory.

  • Adjusting the reconstruction to reduce accumulated drift.

→ Remember: Drift is the accumulated error; loop closure helps correct it.

What is Visual SLAM, and how is it different from ordinary SfM?

Visual SLAM stands for Visual Simultaneous Localization and Mapping.

→ It estimates camera poses and builds a map from a continuous video stream, often in real time.

What software is commonly used for SfM?

• Bundler: One of the earliest publicly available complete SfM systems.

• OpenMVG: Open-source library for multi-view geometry and SfM.

• OpenSfM: Open-source SfM system.

• VisualSFM: GPU-accelerated SfM with a graphical interface.

• COLMAP: Widely used SfM and multi-view stereo pipeline.

Key idea: These tools implement the geometric methods used to reconstruct 3D scenes from images.

What are the main real-world applications of SfM?

SfM is useful whenever we need to recover 3D structure or camera motion from images.

1. 3D modeling and surveying: Reconstruct buildings, terrain, and objects from photographs.

2. Robot navigation and mapping: Help robots estimate their location and build maps.

3. Virtual and augmented reality: Place virtual objects consistently within a real 3D environment.

4. Visual effects: Recover camera movement from real footage so computer-generated objects match the original camera motion.

Key idea: SfM connects ordinary 2D images to useful 3D models and camera trajectories.