Towards Linear-Time Incremental Structure from Motion

Changchang Wu

article20133DV1,408 citations

Demonstrates that incremental structure from motion can operate in linear time by combining preemptive feature matching, efficient conjugate gradient bundle adjustment, and periodic re-triangulation to enable fast, highly scalable 3D reconstructions.

Listen

Large-scale 3D reconstruction from massive photo collections—known as structure from motion—is increasingly important for mapping, virtual tourism, and computer vision. However, traditional incremental reconstruction pipelines scale poorly, historically suffering from high computational costs that make processing thousands of images slow and computationally expensive.

The article demonstrates that incremental 3D reconstruction can achieve near-linear scaling in practice. It introduces an optimized reconstruction framework that drastically reduces processing time while preserving high geometric accuracy, without requiring specialized camera calibrations, vanishing point detection, or geographic positioning data.

The authors evaluated their approach across five diverse datasets ranging from 1,000 to over 32,000 images, including photo collections of Rome and video sequences. The framework introduces preemptive feature matching using scale-sorted features to filter out unlikely image pairs, schedules full mathematical optimizations geometrically based on percentage model growth, and applies scheduled re-triangulation of failed feature matches to correct drift errors without explicit loop-detection routines. Tests were executed on a single commodity desktop computer equipped with a graphics processor.

The analysis yielded several key findings. First, preemptive matching eliminated up to 95% of unnecessary image comparison pairs while preserving the vast majority of useful matches. Second, major optimization and filtering steps scaled linearly in practice rather than polynomially. Third, the system reconstructed a complex model containing over 15,000 cameras for Rome in roughly 1.67 hours on a single machine, operating 8 to 19 times faster per camera than prior cluster-based methods and over 55 times faster than standard baseline tools. Finally, spatial accuracy improved over existing benchmarks, achieving a median GPS positioning error of 0.89 meters compared to 1.16 meters in prior work.

These results demonstrate that large-scale 3D mapping and modeling can be performed rapidly at a fraction of previous computational costs, eliminating the need for expensive multi-node server clusters. Faster turnaround times and reduced hardware requirements significantly lower operational budgets and facilitate scalable real-time processing pipelines.

Organizations handling large image collections should consider adopting geometric optimization schedules and preemptive matching strategies within their reconstruction pipelines. Future development should explore adaptive thresholds for preemptive matching to avoid splitting sparse models, as well as error-guided scheduling for global optimization passes.

Although the major processing stages scaled linearly in practical tests up to 15,000 cameras, the theoretical worst-case complexity remains quadratic, meaning performance trends could degrade on extremely massive datasets. Additionally, aggressively high thresholds in preemptive matching can occasionally discard weak visual links in occluded areas, requiring careful parameter selection for challenging scenes.

University of Washington http reconstruction video streams linear-time incremental structure from motion incremental SfM algorithm multicore bundle adjustment

Wu (2013).pdf

Paper: Building Rome in a day, Sameer Agarwal et al. (2009). This work introduces scalable bundle adjustment architectures and preconditioned conjugate gradient solvers for city-scale 3D reconstructions, providing the foundational optimization efficiency that Wu's linear-time incremental SfM directly builds upon.
Paper: Modeling the World from Internet Photo Collections, Noah Snavely et al. (2008). This foundational paper establishes the classic incremental Structure-from-Motion pipeline using SIFT matching and iterative bundle adjustment that Wu accelerates toward linear-time complexity.
Paper: An efficient solution to the five-point relative pose problem, David Nister (2004). This paper presents the exact, minimal five-point relative pose solver that serves as a standard building block for initial two-view geometry in incremental SfM systems.
Paper: In Defense of the Eight-Point Algorithm, Richard I. Hartley (1997). Hartley's normalized eight-point algorithm provides essential, well-conditioned linear epipolar geometry estimation fundamental to camera initialization in multi-view reconstruction pipelines.
Paper: Distinctive Image Features from Scale-Invariant Keypoints, David G. Lowe (2004). SIFT provides the invariant feature detection and matching mechanism upon which large-scale incremental Structure-from-Motion pipelines rely to register overlapping views.

Paper: Structure-from-Motion Revisited, Johannes L. Schönberger et al. (2016). Building directly on the fast incremental SfM strategies and retriangulation schemes of systems like VisualSFM, this paper introduces COLMAP with comprehensive algorithmic enhancements for robustness, accuracy, and completeness.
Paper: Pixelwise View Selection for Unstructured Multi-View Stereo, Johannes L. Schönberger et al. (2016). This work extends sparse reconstructions generated by incremental SfM pipelines by introducing robust pixelwise view-selection multi-view stereo to recover dense 3D geometry.
Paper: MVSNet: Depth Inference for Unstructured Multi-view Stereo, Yao Yao et al. (2018). MVSNet builds downstream from sparse SfM camera poses and points to infer high-resolution dense multi-view stereo depth maps using learned 3D cost volumes.
Paper: 3D Gaussian Splatting for Real-Time Radiance Field Rendering, Bernhard Kerbl et al. (2023). This method takes the sparse point clouds and calibrated camera poses produced by incremental Structure-from-Motion pipelines as input initialization to optimize real-time 3D Gaussian radiance fields.

Cover for Towards Linear-Time Incremental Structure from Motion

Abstract

The time complexity of incremental structure from motion (SfM) is often known as O(n^4) with respect to the number of cameras. As bundle adjustment (BA) being significantly improved recently by preconditioned conjugate gradient (PCG), it is worth revisiting how fast incremental SfM is. We introduce a novel BA strategy that provides good balance between speed and accuracy. Through algorithm analysis and extensive experiments, we show that incremental SfM requires only O(n) time on many major steps including BA. Our method maintains high accuracy by regularly re-triangulating the feature matches that initially fail to triangulate. We test our algorithm on large photo collections and long video sequences with various settings, and show that our method offers state of the art performance for large-scale reconstructions. The presented algorithm is available as part of VisualSFM at http://homes.cs.washington.edu/~ccwu/vsfm/.

Topics

http reconstruction video streams preconditioners compressed video

Keywords

linear-time incremental structure from motion incremental SfM algorithm multicore bundle adjustment preemptive feature matching scene graph skeletal graphs

1. Introduction
2. Related Work
3. Preemptive Feature Matching
4. How Fast Is Bundle Adjustment?
5. Incremental Structure from Motion
5.1. How Fast Is Incremental SfM?
5.2. Re-triangulation (RT)
6. Experiments
6.1. Feature Matching
6.2. Incremental SfM
6.3. Reconstruction Quality and Speed
6.4. Discussions
7. Conclusions and Future Work
References

Knowls

Knowl 1 — Geometric Sequence Scheduling for Full Bundle Adjustment in Incremental SfM
theoretical result
In incremental Structure from Motion (SfM), executing a full Bundle Adjustment (BA) after adding every constant number $\alpha$ of cameras results in a cumulative BA time of:

$\sum_{i=1}^{\lfloor n/\alpha \rfloor} T_{\text{BA}}(i \cdot \alpha) = O\left(\sum_{i=1}^{\lfloor n/\alpha \rfloor} (i \cdot \alpha)\right) = O\left(\frac{n^2}{\alpha}\right)$

where $n$ is the total number of cameras and $T_{\text{BA}}(m) = O(m)$ is the time required to bundle adjust a model of $m$ cameras using Preconditioned Conjugate Gradient (PCG).

Under geometric sequence scheduling, a full BA is executed only when the number of cameras in the current reconstruction increases relatively by a fixed ratio $r > 0$ (such as $r = 0.05$ , corresponding to a $5\%$ relative growth). The cumulative time spent on all full BAs across the entire reconstruction of $n$ cameras is:

$\sum_{i=0}^{\infty} T_{\text{BA}}\left(\frac{n}{(1+r)^i}\right) = O\left(\sum_{i=0}^{\infty} \frac{n}{(1+r)^i}\right) = O\left(\frac{n}{r}\right) = O(n)$

To prevent error accumulation during the intervals between full optimizations, partial BAs are executed after adding each new camera (or every small constant number of cameras). A partial BA optimizes only a fixed number of recently added cameras (e.g., 20 cameras) and their associated 3D scene points. Because each partial BA optimizes $O(1)$ camera and point parameters, it executes in $O(1)$ time, yielding a cumulative partial BA time of $O(n)$ across $n$ image additions.
Knowl 2 — Time Complexity of Bundle Adjustment with Preconditioned Conjugate Gradient
theoretical result
Bundle adjustment (BA) optimizes camera parameters and 3D point coordinates $x$ by minimizing the sum of squared reprojection errors $f(x)$ :

$x^* = \arg\min_x \|f(x)\|^2$

In the Levenberg-Marquardt (LM) algorithm, parameter updates $\delta$ are computed at each step by solving the regularized linear system:

$(J^T J + \Lambda)\delta = -J^T f$

where $J$ is the Jacobian matrix of $f(x)$ , $\Lambda$ is a non-negative diagonal damping matrix, and $H_\Lambda = J^T J + \Lambda$ is the augmented Hessian matrix.

For a reconstruction with $n$ cameras, $p = O(n)$ 3D points, and $q = O(n)$ feature observations:
- Computing the augmented Hessian requires $O(q) = O(n)$ space and time.
- By utilizing GPU/multicore implementations that perform implicit matrix-vector multiplications of the Hessian and Schur complements directly from the $O(n)$ space Jacobian matrices, explicit formation of the $O(n^2)$ Schur complement matrix is avoided.
- The execution time $T_{\text{cg}}$ of a single Conjugate Gradient (CG) iteration scales linearly with the number of cameras $n$ , requiring $O(n)$ time.
- Preconditioned Conjugate Gradient (PCG) using a block-Jacobi preconditioner solves the linear system in $O(\sqrt{\kappa})$ iterations, where $\kappa$ is the condition number of the system. In practice, PCG converges in an average of 20 CG iterations per LM step.
- Across diverse datasets, LM converges in an average of 37 iterations per BA (with $93\%$ of BAs converging within 100 LM iterations).
Because the numbers of LM and CG iterations are bounded by $O(1)$ in practice (capped at 100 LM steps per BA and 100 CG iterations per LM step), the overall time complexity of a single full bundle adjustment is $O(n)$ .
Knowl 3 — Retriangulation of Under-Reconstructed Camera Pairs for Drift Correction
model/method
In incremental Structure from Motion (SfM), cumulative drift in camera poses occurs when early inaccurate pose estimates prevent correct 2D feature matches from triangulating under strict reprojection and angle thresholds. The ongoing loss of correct 2D-3D constraints leads to severe trajectory drift.

To correct drift without explicit loop detection, camera pairs are evaluated for under-reconstruction:
- An image pair is designated as under-reconstructed if the ratio of their shared triangulated 3D points to their verified 2D feature matches is low.
- Re-triangulation (RT) is triggered according to a geometric progression when the model size grows by a relative ratio $r'$ (such as $r' = 0.25$ , corresponding to a $25\%$ increase in camera count).
- During an RT step, feature matches between under-reconstructed image pairs that previously failed triangulation are re-triangulated using an enlarged reprojection error threshold.
- Immediately following RT, a full bundle adjustment and point filtering pass are performed to integrate the newly recovered 3D points and globally refine camera poses.
Because RT and its subsequent full BA are invoked on a geometric schedule with ratio $r'$ , the cumulative execution time of all RT steps over an $n$ -camera reconstruction is $\sum_{i=0}^\infty O(n / (1+r')^i) = O(n/r') = O(n)$ .
Knowl 4 — Preemptive Feature Matching Algorithm
algorithm
Preemptive feature matching reduces the computational cost of pairwise feature matching in large image collections by testing candidate pairs on a small subset of the largest-scale features before committing to full feature matching.
Input: Image set {I_1, ..., I_n}, candidate pair list P, subset size h = 100, threshold t_h, max features k_max = 8192
Output: Verified pairwise feature matches and relative two-view geometries
for each image I_i in {I_1, ..., I_n} (in parallel) do
    Detect scale-invariant keypoints
    Sort keypoints in descending order of their scale parameter
end for
for each candidate pair (I_a, I_b) in P (in parallel) do
    Match the first h top-scale features of I_a and I_b using nearest neighbor with distance ratio test and mutual nearest-neighbor constraint
    Let m(h) be the number of resulting matches
    if m(h) < t_h then
        Skip to next pair (reject candidate pair)
    else
        Match full feature sets (up to k_max top-scale features) of I_a and I_b
        Estimate two-view epipolar geometry using RANSAC
    end if
end for
Sorting features by decreasing scale takes $O(n)$ total preprocessing time. Top-scale features have roughly an $h/\max(k_1, k_2)$ probability of preserving a match (where $k_1, k_2$ are the total feature counts), compared to $h^2 / (k_1 k_2)$ for uniform random sampling. For image pairs that fail the threshold test, matching cost is reduced by a factor of roughly $h^2 / (k_1 k_2)$ .
Knowl 5 — Incremental Structure from Motion Pipeline with Mixed Optimization and Retriangulation
algorithm
The incremental SfM algorithm iteratively incorporates cameras into a growing 3D reconstruction, balancing execution speed and accuracy using mixed bundle adjustments and scheduled retriangulations.
Input: Image set with verified pairwise feature matches, full BA growth ratio r = 0.05, RT growth ratio r_prime = 0.25, partial BA window size w = 20
Output: Estimated camera poses and 3D point cloud
Initialize 3D reconstruction from a verified two-view model
Let n_last_full be the number of cameras at last full BA (initially size of seed model)
Let n_last_rt be the number of cameras at last RT (initially size of seed model)
while there exist unadded images with 2D-3D correspondences do
    Select next camera with sufficient 2D-3D correspondences and estimate its pose
    Triangulate new 3D points from its feature matches
    Let n_curr be current number of reconstructed cameras

    if (n_curr - n_last_full) / n_last_full >= r then
        Run full Bundle Adjustment on all cameras and 3D points
        Filter all 3D points exceeding reprojection error or below minimum angle
        n_last_full = n_curr
    else
        Run partial Bundle Adjustment on the w most recently added cameras and their points
        Filter only the 3D points modified during the partial BA
    end if

    if (n_curr - n_last_rt) / n_last_rt >= r_prime then
        Identify under-reconstructed image pairs
        Re-triangulate failed matches of under-reconstructed pairs with relaxed error threshold
        Run full Bundle Adjustment and point filtering
        n_last_rt = n_curr
        n_last_full = n_curr
    end if
end while
All bundle adjustments use Preconditioned Conjugate Gradient (PCG) with a block-Jacobi preconditioner, capped at a maximum of 100 Levenberg-Marquardt iterations per BA and 100 CG iterations per LM step.
Knowl 6 — Time Complexity of Point Filtering and Resection Tracking in Incremental SfM
theoretical result
In incremental Structure from Motion, point filtering and camera resection tracking contribute to the overall reconstruction complexity as follows:
1. Point Filtering:
- Partial filtering: After a partial Bundle Adjustment (BA), only the 3D points modified by the $O(1)$ locally adjusted cameras require verification against reprojection error and triangulation angle thresholds. This takes $O(1)$ time per added image, summing to $O(n)$ across the reconstruction.
- Full filtering: Following a full BA, checking all $p = O(n)$ points takes $O(n)$ time. Because full BAs occur according to a geometric sequence with ratio $r$ , the cumulative time across all full filtering passes is bounded by $\sum_{i=0}^\infty O(n / (1+r)^i) = O(n/r) = O(n)$ .
1. Resection Candidate Tracking:
- Potential 2D-3D correspondences are tracked incrementally using feature matches from newly added images.
- Assuming each image matches $O(1)$ other images in large-scale datasets, updating correspondence tables takes $O(1)$ time per iteration, and adding a camera takes $O(1)$ time, totaling $O(n)$ time for $n$ cameras.
1. Practical vs Theoretical Time Complexity:
- Finding subsets for partial BA, identifying matching image subsets for resection, and comparing candidate cameras without spatial indexing take $O(n)$ scan time per camera addition, totaling $O(n^2)$ theoretical time.
- However, in reconstructions up to 15,065 cameras, the $O(n)$ BA and filtering components dominate runtime, resulting in practical execution times that scale approximately linearly with $n$ .

Knowl 7 — Reconstruction Runtime and Scalability on Large-Scale Datasets

data/table

The incremental SfM method was evaluated on five datasets spanning 1,164 to 32,768 input images on a single workstation (Intel Xeon 5680 3.33 GHz, 24 cores, 12 GB RAM, NVIDIA GTX 480 GPU). Reconstruction parameters include full BA growth ratio $r$ , partial BA frequency, and retriangulation growth ratio $r'$ . Performance metrics are the number of reconstructed cameras $n$ , number of observations $q$ , total reconstruction time $t$ , time per reconstructed camera $t/n$ , and time per observation $t/q$ .

Dataset	Full BA	Partial BA	RT	$n$	$q$	$t$	$t/n$	$t/q$
Central Rome	$r = 5\%$	Every Image	$r' = 25\%$	15065	12903K	1.67h	0.40s	0.47ms
Central Rome	$r = 25\%$	Every Image	$r' = 50\%$	15113	12958K	1.32h	0.31s	0.37ms
Central Rome	$r = 5\%$	Every 3 Images	$r' = 25\%$	14998	12599K	1.03h	0.25s	0.29ms
Central Rome	DISCO (Crandall et al., 2011)			14754	21544K	13.2h	3.2s	2.2ms
Central Rome	Bundler (Snavely et al., 2006)			13455	5411K	82.0h	22.0s	54.0ms
Arts Quad	$r = 5\%$	Every Image	$r' = 25\%$	5624	5839K	0.59h	0.38s	0.37ms
Arts Quad	$r = 25\%$	Every Image	$r' = 50\%$	5598	5850K	0.42h	0.27s	0.26ms
Arts Quad	$r = 5\%$	Every 3 Images	$r' = 25\%$	5461	5530K	0.53h	0.35s	0.35ms
Arts Quad	DISCO (Crandall et al., 2011)			5233	9387K	7.7h	5.2s	2.9ms
Arts Quad	Bundler (Snavely et al., 2006)			5028	10521K	62.0h	44.0s	21.0ms
Loop	$r = 5\%$	Every Image	$r' = 25\%$	4342	7196K	3251s	0.75s	0.45ms
Loop	$r = 25\%$	Every Image	$r' = 50\%$	4342	7574K	1985s	0.46s	0.26ms
Loop	$r = 5\%$	Every 3 Images	$r' = 25\%$	4341	7696K	3207s	0.74s	0.41ms
St. Peter's	$r = 5\%$	Every Image	$r' = 25\%$	1267	2706K	583s	0.46s	0.22ms
St. Peter's	$r = 25\%$	Every Image	$r' = 50\%$	1267	2760K	453s	0.36s	0.16ms
St. Peter's	$r = 5\%$	Every 3 Images	$r' = 25\%$	1262	2668K	367s	0.29s	0.14ms
Colosseum	$r = 5\%$	Every Image	$r' = 25\%$	1157	1759K	591s	0.51s	0.34ms
Colosseum	$r = 25\%$	Every Image	$r' = 50\%$	1087	1709K	205s	0.19s	0.12ms
Colosseum	$r = 5\%$	Every 3 Images	$r' = 25\%$	1091	1675K	471s	0.43s	0.28ms

For default settings ( $r=5\%$ , partial BA every image, $r'=25\%$ ), a breakdown of total time $t$ shows that BA steps dominate computation (e.g., Central Rome: total 6010 s, full BA 2008 s, partial BA 2957 s, adding cameras 549 s, filtering 247 s). On $t/n$ , this approach is $8\times$ to $19\times$ faster than DISCO (which ran on a 200-core cluster) and $55\times$ to $163\times$ faster than Bundler.

Knowl 8 — Yield and Pair Reduction of Preemptive Feature Matching

data/table

The effectiveness of preemptive matching was evaluated by comparing full pairwise matching against preemptive filtering using the top $h = 100$ scale-ordered features under match thresholds $t_h \in \{2, 4, 8\}$ . The putative yield $Y_p(h)$ and inlier yield $Y_i(h)$ are defined as:

$Y_p(h) = \frac{m_p(h)}{h} \quad \text{and} \quad Y_i(h) = \frac{m_i(h)}{h}$

where $m_p(h)$ is the number of putative matches and $m_i(h)$ is the number of inlier matches found among the top $h$ features.

	Without Preemptive Matching					Using Preemptive Matching ( $h=100$ )
Dataset	Pairs to	Pairs With	Feature		$t_h$	Pairs to	Pairs With	Feature
	Match	15+ Inliers	Matches	$n$		Match	15+ Inliers	Matches	$n$
Central Rome	N/A	N/A	N/A	N/A	4	13551K	540K	67M	15065
Arts Quad	15402K	192K	32M	5624	4	521K (3%)	62K (32%)	25M (78%)	4272
Arts Quad	15402K	192K	32M	5624	2	4308K (28%)	121K (63%)	29M (91%)	5393
Loop	709K	329K	158M	4342	4	269K (38%)	235K (71%)	150M (95%)	4342
Loop	709K	329K	158M	4342	8	151K (21%)	150K (46%)	135M (85%)	4342
St. Peter's	812K	217K	21M	1267	4	46K (6%)	38K (18%)	9.1M (43%)	1211
St. Peter's	812K	217K	21M	1267	8	220K (27%)	100K (46%)	14M (67%)	1262
Colosseum	677K	54K	6.8M	1157	4	23K (3%)	13K (24%)	4.1M (60%)	517+426
Colosseum	677K	54K	6.8M	1157	2	149K (22%)	28K (52%)	5.4M (79%)	1071

All reconstructions utilized $r = 5\%$ and $r' = 25\%$ . Matching the top 100 features achieved an average throughput of 73,000 pairs per second across 24 threads. For St. Peter's with $t_h = 4$ , evaluating only $6\%$ of pairs recovered $43\%$ of all feature matches and enabled reconstruction of 1,211 out of 1,267 cameras. Setting $t_h = 2$ preserved weak visual links, preventing model fragmentation in challenging scenes like the Colosseum.

Knowl 9 — Camera Pose Accuracy Evaluated Against GPS Ground Truth
empirical result
Reconstruction accuracy was quantitatively evaluated on the Arts Quad dataset (6,514 input images), which includes ground truth GPS coordinates for 348 images. The incremental SfM reconstruction (configured with $r = 5\%$ full BA growth and $r' = 25\%$ retriangulation growth) successfully reconstructed 261 of the 348 ground-truth images.

A 3D similarity transformation between the estimated camera center coordinates and their Euclidean GPS coordinates was computed using RANSAC. Under the optimal similarity transformation, the reconstructed camera positions achieved:
- A mean position error of 2.5 meters.
- A median position error of 0.89 meters.
In comparison, the global MRF-based optimization method DISCO (Crandall et al., 2011) reported a median error of 1.16 meters on the same dataset, demonstrating that the incremental pipeline with mixed BA and scheduled retriangulation maintains high geometric accuracy while reducing computational cost.

Coverage note — None was omitted; the extracted knowls cover all principal contributions of the paper, including preemptive feature matching, bundle adjustment complexity analysis, geometric scheduling, retriangulation, overall incremental SfM pipeline, and empirical benchmarks against DISCO and Bundler.

References

1.S. Agarwal, N. Snavely, S. Seitz, and R. Szeliski. Bundle adjustment in the large. In ECCV, pages II: 29–42, 2010. 2, 3
2.S. Agarwal, N. Snavely, I. Simon, S. M. Seitz, and R. Szeliski. Building Rome in a day. In ICCV, 2009. 1, 2, 7
3.M. Byrod and K. Astrom. Conjugate gradient bundle adjustment. In ECCV, pages II: 114–127, 2010. 2, 3
4.D. Crandall, A. Owens, N. Snavely, and D. P. Huttenlocher. Discrete-continuous optimization for large-scale structure from motion. In CVPR, 2011. 1, 2, 5, 6, 7, 8
5.J. Frahm, P. Fite Georgel, D. Gallup, T. Johnson, R. Raguram, C. Wu, Y. Jen, E. Dunn, B. Clipp, S. Lazebnik, and M. Pollefeys. Building rome on a cloudless day. In ECCV, pages IV: 368–381, 2010. 1, 2
6.R. Gherardi, M. Farenzena, and A. Fusiello. Improving the efficiency of hierarchical structure-and-motion. In CVPR, pages 1594–1600, 2010. 2
7.A. Kushal, B. Self, Y. Furukawa, C. Hernandez, D. Gallup, B. Curless, and S. Seitz. Photo tours. In 3DimPVT, 2012. 1
8.X. Li, C. Wu, C. Zach, S. Lazebnik, and J. Frahm. Modeling and recognition of landmark image collections using iconic scene graphs. In ECCV, 2008. 1, 2
9.M. A. Lourakis and A. Argyros. SBA: A Software Package for Generic Sparse Bundle Adjustment. ACM Trans. Math. Software, 36(1):1–30, 2009. 3
10.D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60:91–110, 2004. 2
11.D. Nister and H. Stewenius. Scalable recognition with a vocabulary tree. In CVPR, pages 2161–2168, 2006. 1
12.J. R. Shewchuk. An introduction to the conjugate gradient method without the agonizing pain, 1994. 3
13.S. N. Sinha, D. Steedly, and R. Szeliski. A multi-stage linear approach to structure from motion. In ECCV RMLE workshop, 2010. 2
14.N. Snavely, S. Seitz, and R. Szeliski. Photo tourism: exploring photo collections in 3D. In SIGGRAPH, pages 835–846, 2006. 1, 3
15.N. Snavely, S. M. Seitz, and R. Szeliski. Skeletal graphs for efficient structure from motion. In CVPR, 2008. 1, 2
16.C. Wu, S. Agarwal, B. Curless, and S. M. Seitz. Multicore bundle adjustment. In CVPR, 2011. 2, 3

Citation

MLA

Wu, C. “Towards Linear-Time Incremental Structure from Motion”. 2013 International Conference on 3D Vision, 2013, pp. 127–34, https://doi.org/10.1109/3DV.2013.25.

APA

Wu, C. (2013). Towards Linear-Time Incremental Structure from Motion. 2013 International Conference on 3D Vision, 127–134. https://doi.org/10.1109/3DV.2013.25

Chicago

Wu, C. 2013. “Towards Linear-Time Incremental Structure from Motion”. 2013 International Conference on 3D Vision, 127–34. https://doi.org/10.1109/3DV.2013.25.

Harvard

Wu, C. (2013) “Towards Linear-Time Incremental Structure from Motion”, 2013 International Conference on 3D Vision. IEEE, pp. 127–134. Available at: https://doi.org/10.1109/3DV.2013.25.

Vancouver

1. Wu C (2013) Towards Linear-Time Incremental Structure from Motion. In: 2013 International Conference on 3D Vision. IEEE, pp 127–134

BibTeX

@inproceedings{Wu_2013, title={Towards Linear-Time Incremental Structure from Motion}, url={http://dx.doi.org/10.1109/3DV.2013.25}, DOI={10.1109/3dv.2013.25}, booktitle={2013 International Conference on 3D Vision}, publisher={IEEE}, author={Wu, Changchang}, year={2013}, month=June, pages={127–134} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Towards Linear-Time Incremental Structure from Motion

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Geometric Sequence Scheduling for Full Bundle Adjustment in Incremental SfM

Knowl 2 — Time Complexity of Bundle Adjustment with Preconditioned Conjugate Gradient

Knowl 3 — Retriangulation of Under-Reconstructed Camera Pairs for Drift Correction

Knowl 4 — Preemptive Feature Matching Algorithm

Knowl 5 — Incremental Structure from Motion Pipeline with Mixed Optimization and Retriangulation

Knowl 6 — Time Complexity of Point Filtering and Resection Tracking in Incremental SfM