PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical structure-and-motion recovery from uncalibrated images

Roberto Toldo, Riccardo Gherardi, Michela Farenzena, Andrea Fusiello

arXiv:1506.00395v1cs.CV

TL;DR

Structure-and-motion seeks to recover camera motion and 3D scene geometry from image matches, with computational efficiency and reliance on ancillary information as central challenges. Samantha uses a hierarchical pipeline with autocalibration for uncalibrated images. The authors report improved computational performance and error containment over sequential approaches, with almost linear complexity in the number of tie-points and images.

  • Problem

    Structure-and-motion must recover scene geometry and camera motion while addressing computational complexity and the amount of ancillary information required.

    Source: §1 · p. 2, §1.1 · p. 2

  • Method

    Samantha organizes images in a dendrogram and computes structure and motion hierarchically, with autocalibration to estimate camera internal parameters from images.

    Source: §1 · p. 2

  • Results

    The authors report improved computational performance by one order of magnitude on average and improved error containment over sequential approaches.

    Source: §1.3 · p. 4

  • Takeaways & Limitations

    Samantha is presented as a scalable approach, with almost linear complexity in the number of tie-points and images.

    Source: §10 · p. 25

    The local bundle-adjustment strategy is sub-optimal because it omits images in B that share no tie-points with A, though a final global adjustment can be run.

    Source: §6 · p. 12

Abstract

from arXiv · show

This paper addresses the structure-and-motion problem, that requires to find camera motion and 3D struc- ture from point matches. A new pipeline, dubbed Samantha, is presented, that departs from the prevailing sequential paradigm and embraces instead a hierarchical approach. This method has several advantages, like a provably lower computational complexity, which is necessary to achieve true scalability, and better error containment, leading to more stability and less drift. Moreover, a practical autocalibration procedure allows to process images without ancillary information. Experiments with real data assess the accuracy and the computational efficiency of the method.

1. Introduction

Structure-and-motion must recover scene geometry and camera motion while addressing computational efficiency and reliance on ancillary information. Samantha organizes recovery hierarchically and includes practical autocalibration for unordered, uncalibrated images.

1. Introduction

  • Samantha represents image groups as a dendrogram and builds the complete model bottom-up, with a one-order complexity reduction when the tree is well balanced.The hierarchy also partitions work into smaller instances that can be parallelized and is described as less sensitive to initialization and drift than sequential approaches.Source: §1 · p. 2

1.1. Structure-and-motion: related work.

  • Existing structure-and-motion pipelines face computational complexity, dominated by bundle adjustment, as well as varying requirements for camera calibration and other ancillary data.Prior approaches include partitioning and hierarchical methods, but some are limited to video sequences or process selected images incrementally.Source: §1.1 · pp. 2–3

1.2. Autocalibration: related work.

  • Autocalibration estimates camera internal parameters from images, avoiding dependence on EXIF data that may be absent or inconsistent.Prior work includes methods based on the dual image of the absolute quadric and branch-and-bound formulations.Source: §1.2 · p. 3

1.3. Overview

  • The pipeline performs keypoint matching, clusters images into a dendrogram, and computes structure and motion by traversing it from leaves to root.At each node it performs stereo modeling, resection-intersection, or model merging, with bundle adjustment; autocalibration is performed on partial models during traversal.Source: §1.3 · p. 4
  • The authors report that the hierarchical paradigm improves computational performance by one order of magnitude on average and improves overall error containment.The latest Samantha version revises matching and autocalibration and aims to reduce user intervention; experiments assess accuracy, convergence, and speed.Source: §1.3 · pp. 4–5

2. Keypoint detection and matching

The keypoint stage automatically extracts and matches image features to produce input for geometric structure-and-motion recovery. Its broad phase builds a sparse, connected epipolar graph; its narrow phase estimates pairwise geometry and links matches into tracks.

2. Keypoint detection and matching

  • The fully automatic matching procedure prunes outliers, and its epipolar-graph recovery procedure is new.Keypoints are grouped into tracks; inconsistent tracks and tracks shorter than three frames are discarded, and each retained track represents a tie-point.Source: §2 · p. 5, §2.3 · p. 7

2.1. Keypoint detection.

  • The detector finds scale-space extrema of the scale-normalized Laplacian, paired with a 128-dimensional radial descriptor that performs comparably to SIFT.The authors state that this detector-descriptor combination avoids patent issues.Source: §2.1 · p. 5

2.2. Matching: broad phase.

  • In the broad phase, matching a small constant number of high-scale descriptors per image supports reducing candidate image-pair matching from O(n2) toward O(n).The method uses approximate nearest neighbors to build an image-pair match-count histogram; graph connectivity can fail to reach m-edge-connectedness if the required spanning-tree hypothesis does not hold.Source: §2.2 · pp. 5–6
  • The broad phase builds an epipolar subgraph designed to be almost m-edge-connected, rather than matching every image pair.It uses a maximum spanning tree and repeated edge removals; the strategy favors high-weight pairs while seeking stronger connectivity.Source: §2.2 · pp. 5–6

2.3. Matching: narrow phase.

  • The narrow phase rejects non-injective matches and uses dominant-angle clusters to speed matching, at the cost of losing some matches at cluster borders.A pair is discarded if fewer than 20% of its matches remain after MSAC; tracks shorter than three frames are also removed.Source: §2.3 · pp. 6–7
  • The narrow phase estimates homographies and fundamental matrices with MSAC, refines inliers, and selects the more likely model using GRIC.MSAC scores inliers by fit and gives outliers a fixed penalty; spatial bucketing separates sample keypoints.Source: §2.3 · p. 6

3. Clustering images

The method clusters images by overlap and processes the resulting tree from leaves to root, solving smaller instances separately before combining them.

3. Clustering images

  • Images are clustered by overlap and processed bottom-up, breaking structure-and-motion into smaller instances that are separately solved and combined.Source: §3 · p. 7
  • Image affinity accounts for shared tie-points and how broadly their projections spread across each image; the clustering distance is 1 − a_i,j.The affinity uses the Jaccard index of visible tie-point sets and the convex-hull area of their projections relative to image area.Source: §3 · p. 7
  • Simple linkage merges clusters by nearest-neighbor distance, producing elongated clusters suited to image sequences sweeping an area or building.Tracks of length two are cut as a heuristic to remove less reliable correspondences, though the pipeline can use them.Source: §3 · pp. 7–8

4. Hierarchical structure-and-motion

Samantha builds a structure-and-motion model through hierarchical image clustering, applying stereo modeling, resection-intersection, or model merging at each node. Its best-case complexity is lower than the sequential approach when the tree is balanced, while an unbalanced tree retains sequential complexity.

4. Hierarchical structure-and-motion

  • Each tree node represents a partial independent model, and merges perform stereo modeling, resection-intersection, or fusion of two nontrivial models.Processing proceeds bottom-up from seed image pairs to the complete model; a merge is discarded if its corresponding modeling operation fails.Source: §4 · p. 8, Figure 3 · p. 8

4.1. Stereo-modeling.

  • Stereo modeling estimates relative orientation from the essential matrix, triangulates tie-points, and refines the two-camera model with bundle adjustment.Pair selection requires many shared tie-points and a sufficiently large baseline; sanity checks reject unsuitable pairs before or after modeling.Source: §4.1 · p. 9

4.2. Intersection.

  • Intersection triangulates track points and prunes ill-conditioned solutions and high-reprojection-error points; failed points are retried as their tracks gain images.The condition-number threshold is 10^4 in the reported experiments.Source: §4.2 · p. 9

4.3. Resection

  • Resection adds an image by estimating its external camera parameters from 3D–2D correspondences, then updates tie-points by intersection and refines the model.The method uses PPnP inside MSAC, followed by nonlinear reprojection-error minimization.Source: §4.3 · p. 9

4.4. Merging two models.

  • Model merging registers one partial model to another using a similarity transformation from shared tie-points, then updates intersections and bundle-adjusts the result.The framework is independent of the initial image pair and is described as better able to cope with drift than the standard sequential approach.Source: §4.4 · pp. 9–10

4.5. Complexity analysis.

  • O(n^4) best-case time for Samantha compares with O(n^5) for sequential structure-and-motion; an unbalanced tree falls back to O(n^5).The best case assumes a well-balanced dendrogram; the analysis counts bundle-adjustment cost, which dominates other operations.Source: §4.5 · p. 10

5. Dendrogram balancing

The clustering rule promotes balanced dendrograms because the hierarchical method reaches its best-case complexity only when the tree is well balanced. Its parameter trades balance against clustering quality.

5. Dendrogram balancing

  • A well-balanced tree enables the hierarchical method’s O(n^4) best-case complexity, while an unbalanced tree loses that gain.The worst case is equivalent to sequential single-image additions and has O(n^5) complexity.Source: §5 · p. 11
  • Each sweep merges the closest pair among the ℓ closest cluster pairs, balancing nearest-neighbor distance against a preference for smaller combined clusters.The pair’s cardinality is the sum of the two cluster sizes.Source: §5 · p. 11
  • Balancing is controlled by ℓ: at ℓ = 1, clustering is standard agglomerative clustering with no balancing; at ℓ ≥ n/2, a perfectly balanced tree results, but clustering is poor because distance is largely disregarded.Figure 4 shows tree height reduced from 14 to 9, with more initial pairs in the resulting dendrogram.Source: §5 · p. 11

6. Local bundle adjustment

Local bundle adjustment reduces the images used during model merging, but is suboptimal compared with a full adjustment; a full adjustment can be run at the end.

6. Local bundle adjustment

  • During merging, local bundle adjustment optimizes all images in the smaller model and only the larger-model images sharing tracks with it.Other larger-model images stay fixed but their tie-points anchor the overlapping subset; tie-points linking only non-overlapping images are excluded, making the step suboptimal, though a full adjustment can be run at the end.Source: §6 · pp. 11–12

7. Uncalibrated hierarchical structure-and-motion

The section adapts the pipeline to uncalibrated images: models begin projective and are upgraded to Euclidean form through autocalibration once they contain enough images.

7.1. Autocalibration

  • Autocalibration estimates a Euclidean upgrade by searching internal parameters for two cameras, scoring the resulting cameras, then refining the best solution nonlinearly.The score evaluates skew, aspect ratio, and principal-point location.Source: §7.1 · p. 12, §7.1.2 · p. 14

7.1.1. Estimation of the plane at infinity.

  • Given two projection matrices and their internal parameters, a closed-form estimate of plane-at-infinity vector r uses rotation constraints; approximate calibration yields an approximate Euclidean model.Orthogonality constraints determine r so the upgraded camera block is a rotation, up to scale.Source: §7.1.1 · pp. 12–13

7.1.2. Estimation of the internal parameters.

  • The internal-parameter search samples focal lengths with centered principal points, scores upgraded cameras against skew, aspect-ratio, and principal-point expectations, then refines the minimum.The authors report convergence failures when focal-space sampling is too sparse, in practice below twenty values in either direction.Source: §7.1.2 · pp. 13–14
  • Autocalibration starts on two-image models for conditioning, but those upgrades remain approximate and projective until sufficient image cardinality; later, bundle adjustment refines intrinsics.The procedure is no longer performed after the model reaches sufficient cardinality.Source: §7.1.2 · pp. 14–15

7.2. Projective stereo-modeling.

  • Two uncalibrated images first produce a projective stereo model; a plane-at-infinity estimate based on rough focal lengths supplies a better-conditioned starting point before triangulation and bundle adjustment.The canonical camera pair’s plane at infinity passes through the second camera center, which the method replaces with a better estimate.Source: §7.2 · p. 15

7.3. Resection-intersection.

  • For resection of an uncalibrated image, DLT estimates the full camera matrix, whereas PPnP estimates only external camera parameters.Source: §7.3 · p. 15

7.4. Merging two models.

  • When merging projective and Euclidean partial models, DLT estimates the projectivity that places the projective model in the Euclidean reference frame; bundle adjustment follows.Source: §7.4 · p. 15

8. Parameter Settings

The section reports parameter choices and heuristics intended to make Samantha automatic in most cases, while keeping user-settable parameters interpretable.

Parameter strategy

  • Samantha’s parameter strategy avoids free parameters where possible, makes settings data-dependent, and provides intelligible user choices with defaults intended for most scenarios.Source: §8 · p. 15

Keypoint detection and matching

  • Keypoint selection retains the strongest responses; broad matching uses 300 high-scale keypoints per image and six feature-space neighbors, while m=8 is the reported connectivity default.Source: §8 · pp. 15–16

Matching

  • Narrow-phase matching caps MSAC at 1,000 iterations, dynamically updates that bound as inliers are found, and prunes weak matches using descriptor ratio and surviving-inlier thresholds.Source: §8 · p. 16

Clustering

  • After ℓ=3, computing time stabilizes around 30% of the ℓ=1 baseline, without significant change in reconstructed images or tie-points.Figure 5 plots these quantities as percentages against ℓ, using ℓ=1 as the baseline.Source: §8 · p. 16, Figure 5 · p. 17

Autocalibration

  • Autocalibration is stopped once cluster cardinality meets its feasibility condition; four cameras suffice when skew and aspect ratio are known or guessed.The authors keep the threshold low because they observed projective alignment to be fairly unstable and prefer similarity transforms sooner.Source: §8 · p. 17

Bundle adjustment and final reconstruction

  • Full bundle adjustment runs until clusters become Euclidean and again at the end; camera intrinsics are fixed after bundle adjustment with 25 cameras, while final intersection adds length-two tracks after optimization.Source: §8 · p. 17

9. Experiments

The experiments assess Samantha’s reconstruction accuracy, autocalibration, and runtime on real datasets, including qualitative comparisons with VisualSFM. Results are generally accurate, with notable VisualSFM failures on two qualitative tests and laser-comparison residuals that vary with dataset conditions.

9.1. Qualitative evaluation.

  • Samantha produced a complete, correct Navona model while VisualSFM produced a partial, incorrect one; on S. Giacomo, Samantha was visually correct while VisualSFM placed cameras outside the square and reconstructed walls incorrectly.The Br`a and Duomo di Pisa comparisons were visually correct for both pipelines.Source: §9.1 · p. 18, Figure 9 · p. 20, Figure 8 · p. 20

9.2. Comparison against control points.

  • In cited evaluations where reference internal camera parameters were available, autocalibration yielded focal-length errors of 2.3% in one case and 0.2% in another.Source: §9.1 · p. 18, §9.2 · p. 21
  • After alignment, Samantha’s GCP RMS errors were 22 mm for Ventimiglia, 86 mm for Termica, and 3.4 mm for Herz-Jesu-P25.The Termica error was within the reported uncertainty of the measured camera positions.Source: §9.2 · p. 21, Figure 11 · p. 22, Figure 12 · p. 22

9.3. Comparison against laser data

  • After registration to laser data, Samantha’s residual average distances were 73 mm for Duomo di Pisa, 140 mm for S. Giacomo, and 360 mm for Br`a.Br`a’s laser survey included features absent from the photographs, and the authors suggest this mismatch and larger GSD may explain its higher residual.Source: §9.3 · p. 24, Table 5 · p. 24, Figure 15 · p. 24

9.4. Running Times.

  • Running times were generally comparable; VisualSFM was faster on small datasets, while Samantha appeared to scale better as image counts increased.The authors attribute much of the pattern to matching, since VisualSFM considers all possible image pairs by default.Source: §9.4 · p. 25, Table 6 · p. 25

10. Conclusions

The paper presents Samantha as a hierarchical framework for uncalibrated structure-and-motion, with an almost-linear complexity in tie-points and images. Coupled with its self-calibration approach, it is presented as a method for generic datasets without ancillary information.

10. Conclusions

  • Samantha’s hierarchical framework improves on the sequential approach in computational complexity and overall error containment, with almost-linear complexity in tie-points and images.The paper describes its self-calibration approach as enabling generic-dataset structure-and-motion without external ancillary information.Source: §10 · p. 25

Appendix A. Edge-connectedness of G′.

The appendix argues that the method’s graph G′ is m-edge-connected when m independent spanning trees can be extracted from G.

Appendix A. Edge-connectedness of G′.

  • G′ is m-edge-connected if m independent spanning trees can be extracted from G, because their disjoint paths provide unit-capacity flow for every node pair.The proof invokes the equivalence between k-edge-connectivity and maximum flow of at least k between every node pair.Source: Appendix A · p. 25
Loading 1506.00395v1…