Structure-from-Motion Revisited

1 Structure-from-Motion RevisitedJohannes L. Sch onberger1,2 , Jan-Michael Frahm11 University of North Carolina at Chapel Hill2 Eidgen ossische Technische Hochschule Z Structure-from-Motion is a prevalent strat-egy for 3D reconstruction from unordered image collec-tions. While incremental reconstruction systems havetremendously advanced in all regards, robustness, accu-racy, completeness, and scalability remain the key problemstowards building a truly general-purpose pipeline. We pro-pose a new SfM technique that improves upon the state ofthe art to make a further step towards this ultimate full reconstruction pipeline is released to the public asan open-source IntroductionStructure-from- motion (SfM) from unordered imageshas seen tremendous evolution over the years.

2 The earlyself-calibrating metric reconstruction systems [42, 6, 19,16, 46] served as the foundation for the first systems onunordered Internet photo collections [48, 53] and urbanscenes [45]. Inspired by these works, increasingly large-scale reconstruction systems have been developed for hun-dreds of thousands [1] and millions [20, 62, 51, 47] to re-cently a hundred million Internet photos [30]. A varietyof SfM strategies have been proposed including incremen-tal [53, 1, 20, 62], hierarchical [23], and global approaches[14, 61, 56]. Arguably, incremental SfM is the most popularstrategy for reconstruction of unordered photo its widespread use, we still have not accomplishedto design a truly general-purpose SfM system.

3 While theexisting systems have advanced the state of the art tremen-dously, robustness, accuracy, completeness, and scalabilityremain the key problems in incremental SfM that prevent itsuse as a general-purpose method. In this paper, we proposea new SfM algorithm to approach this ultimate goal. Thenew method is evaluated on a variety of challenging datasetsand the code is contributed to the research community as anopen-source implementation namedCOLMAP available This work was done at the University of North Carolina at Chapel 1. Result of Rome with 21K registered out of 75K Review of structure -from-MotionSfM is the process of reconstructing 3D structure fromits projections into a series of images taken from differentviewpoints.

4 Incremental SfM (denoted as SfM in this paper)is a sequential processing pipeline with an iterative recon-struction component (Fig. 2). It commonly starts with fea-ture extraction and matching, followed by geometric verifi-cation. The resulting scene graph serves as the foundationfor the reconstruction stage, which seeds the model witha carefully selected two-view reconstruction, before incre-mentally registering new images, triangulating scene points,filtering outliers, and refining the reconstruction using bun-dle adjustment (BA). The following sections elaborate onthis process, define the notation used throughout the paper,and introduce related Correspondence SearchThe first stage is correspondence search which findsscene overlap in the input imagesI={Ii|i= }and identifies projections of the same points in overlappingimages.

5 The output is a set of geometrically verified imagepairs Cand a graph of image projections for each each imageIi, SfM detects setsFi={(xj,fj)|j= }of local features at loca-tionxj R2represented by an appearance features should be invariant under radiometric and ge-ometric changes so that SfM can uniquely recognize themin multiple images [41]. SIFT [39], its derivatives [59], andmore recently learned features [9] are the gold standard interms of robustness. Alternatively, binary features providebetter efficiency at the cost of reduced robustness [29].Correspondence SearchIncremental ReconstructionImagesReconstructionInitia lizationBundle AdjustmentTriangulationFeature ExtractionMatchingGeometric VerificationImage RegistrationOutlier FilteringFigure 2.

6 Incremental Structure-from-Motion , SfM discovers images that see the samescene part by leveraging the featuresFias an appearancedescription of the images. The na ve approach tests everyimage pair for scene overlap; it searches for feature cor-respondences by finding the most similar feature in imageIafor every feature in imageIb, using a similarity met-ric comparing the appearancefjof the features. This ap-proach has computational complexityO(N2IN2Fi)and isprohibitive for large image collections. A variety of ap-proaches tackle the problem of scalable and efficient match-ing [1, 20, 37, 62, 28, 50, 30]. The output is a set of poten-tially overlapping image pairsC={{Ia,Ib} |Ia,Ib I, a < b}and their associated feature correspondencesMab Fa third stage verifies the po-tentially overlapping image pairsC.

7 Since matching isbased solely on appearance, it is not guaranteed that cor-responding features actually map to the same scene , SfM verifies the matches by trying to estimate atransformation that maps feature points between images us-ing projective geometry. Depending on the spatial config-uration of an image pair, different mappings describe theirgeometric relation. A homographyHdescribes the trans-formation of a purely rotating or a moving camera capturinga planar scene [26]. Epipolar geometry [26] describes therelation for a moving camera through the essential matrixE(calibrated) or the fundamental matrixF(uncalibrated),and can be extended to three views using the trifocal ten-sor [26]. If a valid transformation maps a sufficient numberof features between the images, they are considered geo-metrically verified.

8 Since the correspondences from match-ing are often outlier-contaminated, robust estimation tech-niques, such as RANSAC [18], are required. The outputof this stage is a set of geometrically verified image pairs C,their associated inlier correspondences Mab, and optionallya description of their geometric relationGab. To decide onthe appropriate relation, decision criterions like GRIC [57]or methods like QDEGSAC [21] can be used. The outputof this stage is a so-called scene graph [54, 37, 49, 30] withimages as nodes and verified pairs of images as Incremental ReconstructionThe input to the reconstruction stage is the scene outputs are pose estimatesP={Pc SE(3)|c= }for registered images and the reconstructed scenestructure as a set of pointsX={Xk R3|k= }.

9 Initializes the model with a carefullyselected two-view reconstruction [7, 52]. Choosing a suit-able initial pair is critical, since the reconstruction maynever recover from a bad initialization. Moreover, the ro-bustness, accuracy, and performance of the reconstructiondepends on the seed location of the incremental from a dense location in the image graph withmany overlapping cameras typically results in a more robustand accurate reconstruction due to increased redundancy. Incontrast, initializing from a sparser location results in lowerruntimes, since BAs deal with overall sparser problems ac-cumulated over the reconstruction from a metric reconstruc-tion, new images can be registered to the current model bysolving the Perspective-n-Point (PnP) problem [18] usingfeature correspondences to triangulated points in alreadyregistered images (2D-3D correspondences).

10 The PnP prob-lem involves estimating the posePcand, for uncalibratedcameras, its intrinsic parameters. The setPis thus ex-tended by the posePcof the newly registered image. Sincethe 2D-3D correspondences are often outlier-contaminated,the pose for calibrated cameras is usually estimated usingRANSAC and a minimal pose solver, [22, 34]. For un-calibrated cameras, various minimal solvers, [10], orsampling-based approaches, [31], exist. We propose anovel robust next best image selection method for accuratepose estimation and reliable triangulation in Sec. newly registered image must observeexisting scene points. In addition, it may also increase scenecoverage by extending the set of pointsXthrough triangu-lation.