Bundle Adjustment — A Modern Synthesis

1 Bundle Adjustment A Modern SynthesisBillTriggs1, , , one-Alpes,655avenuedel paper is a survey of the theory and methods of photogrammetricbundleadjustment, :thechoiceofcostfunctionandrobustness;nu mericaloptimizationincludingsparseNewton methods,linearlyconvergentapproximations ,updatingandrecursivemeth-ods; gauge (datum) invariance; and quality control. The theory is developed :BundleAdjustment,SceneReconstruction,Ga ugeFreedom,SparseMa-trices, IntroductionThispaperisasurveyofthetheor yandmethodsofbundleadjustmentaimedatthec omputervisioncommunity, ,butmanyseemtobelittleknowninvision, ,wehopetoforestallsomeofthisduplicationo feffort,correctsomecommonmisconceptions, andspeedprogressinvisual reconstruction by promoting interaction between the vision and adjustmentistheproblemofrefiningavisualr econstructiontoproducejointlyoptimal3D structure and viewing parameter (camera pose and/or calibration) ,andjointlythatthesolutionissimultaneous lyoptimalwith respect to both structure and camera variations.

2 The name refers to the bundles This work was supported in part by the European Commission Esprit LTR projectCu-muli(B. Triggs), the UK EPSRC project GR/L34099 (P. McLauchlan), and the Royal Society(A. Fitzgibbon). We would like to thank A. Zisserman, A. Gr un and W. F orstner for , , (Eds.):VisionAlgorithms 99,LNCS1883, 372, Springer-VerlagBerlinHeidelberg2000 BundleAdjustment AModernSynthesis 299of light rays leaving each 3D feature and converging on each camera centre, which are adjusted optimally with respect to both feature and camera positions. Equivalently unlikeindependent model methods,whichmergepartialreconstructions withoutupdatingtheirinternalstructure allofthestructureandcameraparametersarea djustedtogether inonebundle.

3 Bundleadjustmentisreallyjustalargesparse geometricparameterestimationproblem,thep arametersbeingthecombined3 Dfeaturecoordinates, , photogrammetry, industrial metrology, surveying and geodesy. Adjustment com-putationsareamajorcommonthemethrough outthemeasurementsciences,andoncethebasi ctheoryandmethodsareunderstood,theyareea sytoadapttoawidevarietyofprob-lems. Adaptation is largely a matter of choosing a numerical optimization scheme , Bundle Adjustment and similar Adjustment computations are formulatedasnonlinearleastsquaresproblem s[19,46,100,21,22,69,5,73,109].Thecostfu nctionis assumed to be quadratic in the feature reprojection errors, and robustness is , ,andmanyincludeadditionalpenaltiesrelate dtooverfitting, model selection and system performance (priors, MDL).

4 For this reason, ,thecostwillbemodelledas a sum of opaque contributions from the independent information sources (individualobservations,priordistributio ns, ). , (costcontributionsareusuallysparsefuncti onsoftheparameters)andobject-centredsoft wareorganization, : Optimization / Bundle Adjustment is slow :Suchstatementsoftenappearinpapersintrod ucingyetanotherheuristicStructurefromMot ion(SFM) is almost always due to the unthinking use of a general-purpose ,andusuallyconsiderablymoreefficientandf lexible than the newly suggested method ( 6,7). That is why Bundle Adjustment re-mainsthedominantstructurerefinementte chniqueforrealapplications,after40yearso fresearch. Only linear algebra is required :Thisisarecentvariantoftheabove, techniques use only linear algebra, and Bundle Adjustment is simpler than manyinthatitonlysolveslinearsystems:itma kesnouseofeigen-decompositionorSVD, Any sequence can be used :Manyvisionworkersseemtobeveryresistantt otheideathat reconstruction problems should be planned in advance ( 11), and results checkedafterwardstoverifytheirreliabilit y( 10).

5 Systembuildersshouldatleastbeawareoftheb asic techniques for this, even if application constraints make it difficult to use extraordinary extent to which weak geometry and lack of redundancy can maskgrosserrorsistooseldomappreciated, [34,50,30,33]. PointPis reconstructed accurately :Inreconstruction,justastherearenoabsolu tereferences for position, there are none for uncertainty. The 3D coordinate frame isitselfuncertain, inherit its uncertainty, so statements about them are meaningless until the , : Flexibility:Bundleadjustmentgracefullyha ndlesaverywidevarietyofdifferent3 Dfeature and camera types (points, lines, curves, surfaces, exotic cameras), scene types(includingdynamicandarticulatedmode ls,sceneconstraints),informationsources( 2 Dfeatures,intensities,3 Dinformation,priors)anderrormodels(inclu dingrobustones).

6 Ithasnoproblemswithmissingdata. Accuracy:Bundleadjustmentgivespreciseand easilyinterpretedresultsbecauseitusesacc urate statistical error models and supports a sound, well-developed quality controlmethodology. Efficiency:Mature Bundle algorithms are comparatively efficient even on very largeproblems. They use economical and rapidly convergent numerical methods and ,ascomputervisionreconstructiontechnolog ymatures, (notably,moreeffectiveuseofproblemstruct ureandsparseness), 2,andthechoiceoferrormetricorcostfunctio n 3. 4givesarapidsketchoftheoptimizationtheor y we will use. 5 discusses the network structure (parameter interactions and char-acteristicsparseness) of implementation strategies for Adjustment computations: 6 covers second orderNewton-likemethods,whicharestillthe mostoftenusedadjustmentalgorithms; 7coversmethodswithonlyfirstorderconverge nce(mostofthead hocmethodsareinthisclass);and 8 discusses solution updating strategies and recursive filtering Bundle methods.

7 9returnstothetheoreticalissueofgaugefree dom(datumdeficiency),includingthetheoryo finnerconstraints. 10goesintosomedetailonqualitycontrolmeth odsformonitoringtheaccuracyandreliabilit yoftheparameterestimates. 11givessomebriefhintsonnet-workdesign, ,reliablereconstruction. 12completes the body of the paper by summarizing the main conclusions and giving Agivesabriefhistoricaloverviewofthedevel opmentofbundlemethods, AModernSynthesis 301 Bgivessometechnicaldetailsofmatrixfactor ization,updatingandcovariancecalcula-tio n methods. C gives some hints on designing Bundle software, and pointers to references:Culturaldifferencessometimesm akeitdifficultforvisionworkersto read the photogrammetry literature.

8 The collection edited by Atkinson [5] and themanual by Karara [69] are both relatively accessible introductions to close-range (ratherthanaerial) [46,21,22].Kraus[73] is probably the most widely used photogrammetry textbook. Brown s early surveyof Bundle methods [19] is well worth reading. The often-cited manual edited by Slama[100] is now quite dated, although its presentation of Bundle Adjustment is still & Ghiliani [109] is a text devoted to Adjustment computations, with an emphasison surveying. Hartley & Zisserman [62] is an excellent recent textbook covering visiongeometry from a computer vision viewpoint. For nonlinear optimization, Fletcher [29]andGillet al[42]arethetraditionaltexts,andNocedal& Wright[93] ,Bj orck[11]issuperlative,andLawson&Hansonis a good older text.

9 For more general numerical linear algebra, Golub & Van Loan [44] al[26]andGeorge&Liu[40] , , ,[62] :Thestructure,cameras,etc.,beingestimate dwillbeparametrizedbyasinglelargestate ,butwelinearizethislocallyandworkwithsma lllinearstatedisplacementsdenoted ( ) (x),withresidual prediction error z(x) z z(x).However,observationsandpredictioner rorsusuallyonlyappearimplicitly,throught heirinfluenceon thecost functionf(x)=f(predz(x)). The cost function sgradientisg dfdx, anditsHessianisH JacobianisJ x, zarenx, Projection Model and Problem The Projection ,itusuallyalsorecoverstheposes(positions andorientations)ofthecamerasthattookthei mages, , ,points,lines,planes,curves, ,farmorecomplicatedscenemodelsarepossibl e,involving, ,complexobjectslinkedbyconstraintsorarti culations,photometryaswellasgeometry,dyn amics, andonereasonforthinkingthattheyhaveacons iderablefutureinvision parametricmodel can be handled, any model thatpredictsthe valuesofsomeknownmeasurementsordescripto rsonthebasisofsomecontinuousparametricre presentationoftheworld, , ,buttheaffineandorthographicprojectionsa resometimesusefulfordistantcameras,andmo reexoticmodelssuchaspush-broomandrationa lpolynomialcamerasareneededforcertain applications [56,63].

10 In addition to pose (position and orientation), and simpleinternalparameterssuchasfocallengt handprincipalpoint,realcamerasalsorequir evari-oustypesofadditional parameterstomodelinternalaberrationssuch asradialdistortion[17 19,100,69,5].Forsimplicity,supposethatth esceneismodelledbyindividualstatic3 DfeaturesXp,p= ,imagedinmshotswithcameraposeandinternal calibrationparametersPi,i= There may also be further calibration parametersCc,c= , constantacross several images ( , depending on which of several cameras was used). We aregivenuncertainmeasurementsxipofsomesu bsetofthepossibleimagefeaturesxip(thetru eimageoffeatureXpinimagei).Foreachobserv ationxip,weassumethatwehaveapredictive modelxip=x(Cc,Pi,Xp)based on the parameters, that can be used toderiveafeature prediction error: xip(Cc,Pi,Xp) xip x(Cc,Pi,Xp)(1)In the case of image observations the predictive model is image projection, but estimate the unknown 3D feature and camera parameters from the observations,andhencereconstructthescene ,weminimizesomemeasure(discussedin 3) ,startingfromgiveninitialparameterestima tes( ,fromsomeapproximatereconstructionmethod ).