CENTERFOR MACHINEPERCEPTION Algebraic solutions to absolute pose problems CZECHTECHNICAL Martin Bujnˇa´k UNIVERSITY [email protected] CTU–CMP–2012–20 September 26, 2012 Availableat S ftp://cmp.felk.cvut.cz/pub/cmp/articles/bujnak/Bujnak-TR-2012-20.pdf I S ThesisAdvisor: Toma´sˇPajdla E H I gratefully acknowledge EC project MRTN-CT-2004-005439 VISION- TRAIN,whichsupportedmyresearch. T D ResearchReportsofCMP,CzechTechnicalUniversityinPrague,No.20,2012 5 h 36 Publishedby 2 P 3- CenterforMachinePerception,DepartmentofCybernetics 1 2 FacultyofElectricalEngineering,CzechTechnicalUniversity 1 N Technicka´ 2,16627Prague6,CzechRepublic S fax+420224357385,phone+420224357637,www: http://cmp.felk.cvut.cz S I Algebraic solutions to absolute pose problems. A Dissertation Presented to the Faculty of the Electrical Engineering of the Czech Technical University in Prague in Partial Fulfillment of the Re- quirementsforthePh.D.DegreeinStudyProgrammeNo.P2612-Electrotech- nics and Informatics, branch No. 3902V035 - Artificial Intelligence and Bio- cybernetics,by Martin Bujnˇa´k Prague,September2012 ThesisAdvisor: Ing.Toma´sˇ Pajdla,Ph.D. CenterforMachinePerception DepartmentofCybernetics FacultyofElectricalEngineering CzechTechnicalUniversityinPrague Karlovona´meˇst´ı13,12135Prague2,CzechRepublic fax: +420224357385,phone: +420224357465 http://cmp.felk.cvut.cz Abstract Estimatinginternalandexternalcameracalibrationisaverybasicelementinmanycomputer vision applications. Camera localization, structure from motion, scene reconstruction, object localization, tracking and recognition are just a few examples of such applications. This thesis focuses on minimal algorithms for estimating camera calibration, i.e. algorithms which use all possibleconstraintsandminimalnumberofinputs,forexamplepointcorrespondencesbetween 2D and 3D space, to calculate the camera pose and other camera parameters such as unknown focallengthorcoefficientsmodelinglensdistortion. In this work, we first study the absolute pose problem for a calibrated camera, which was an intensively studied problem in the past and many solutions were already developed. The problemitselfcanbeformulatedasasimplesystemofpolynomialequations. Researchesinthe pastfocusedonhowtosolvethisproblem,searchedfordifferentsolutions,comparednumerical stability, speed, or studied how to calculate the camera pose from more than three 2D-to-3D pointcorrespondences. Wereviewthestate-of-the-artandpresentourownformulationstothis problembasedonthewellknowninvariantsandpropertiesoftheproblem. Weprovidesolutions toourformulationsusingdifferentmethodsforsolvingsystemofpolynomialequations. Nextweprovidesolutionstotheabsoluteposeforacamerawithoutcompleteinternalcalibra- tionorforacamerawheresomeadditionalinformationaboutthesceneisknown. Inparticular, absoluteposeofacameracalibrateduptoanunknownfocallengthoracamerawithunknown focallengthandunknownradialdistortion. Furthermore,wedescribespecialcaseswhensome of the scene or camera priors are known, for example, scene is planar, scene is non-planar or whenverticaldirectionofacameraisknownfromagyroscopeoravanishingpoint. Themain contributionofthisthesisisinfindingminimalorfindingoptimalsolutionstotheseproblems. Weformulateallstudiedproblems,fromverybasicrelationsbetween3Dspaceand2Dmea- surements, show different formulations and how can different invariants be helpful in reducing the number of unknowns or to simplify the problem. All our formulations lead to systems of polynomialequations. Weshowhowtosolvethesesystemsusingmethodsforsolvingsystems of polynomial equations, which we developed during our research. Solution the problems are evaluated with high level of detail and with focus on important properties such as numerical stabilityandresistancetonoiseindata. Wecompareournewsolverswiththestate-of-the-arton syntheticandrealdata. In this thesis we further present a general method which speeds up most of the presented solvers and can be also used to speed up other solvers based on eigenvalue computation. We have also found the connection between methods for converting basis of an ideal to a basis withrespecttothelexicographicorderingandcalculationofthecharacteristicpolynomialofan actionmatrix. Acknowledgments IwouldliketoexpressmythankstomycolleaguesatCMPwhoIhadthepleasureofworking with,especiallytoZuzanaKu´kelova´ forherideasandcollaborativeeffortsinalargepartofmy work. I am greatly indebted to Toma´sˇ Pajdla and Radim Sˇa´ra for guiding me throughout my re- search. Theirfriendlysupport,patienceandtheoreticalandpracticalhelphavebeenparamount to the successful completion of my PhD study. I also would like to thank to my family and to myfriendsforalltheirsupportthatmadeitpossibleformetofinishthisthesis. I gratefully acknowledge EC project MRTN-CT-2004-005439 VISIONTRAIN, which sup- portedmyresearch. Contents 1 Introduction 1 2 Contribution of the thesis 5 2.1 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 State-of-the-Art 9 3.1 Absoluteposeofacalibratedcamera . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.1 Non-minimalsolutions . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.1.2 Iterativemethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Absoluteposeofanuncalibratedcamera . . . . . . . . . . . . . . . . . . . . . 13 3.3 Absoluteposewithunknownfocallength . . . . . . . . . . . . . . . . . . . . 13 3.4 Unknownfocallengthandradialdistortion . . . . . . . . . . . . . . . . . . . 14 4 Solving systems of polynomial equations 15 4.1 Systemofpolynomialequations . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Hiddenvariablemethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3 Gro¨bnerbasismethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 Polynomialeigenvaluemethod . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.5 Automaticsolvergenerator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.6 Randominstancesinafiniteprimefield . . . . . . . . . . . . . . . . . . . . . 20 4.6.1 Basicfiniteprimefieldarithmetics . . . . . . . . . . . . . . . . . . . . 21 4.6.2 Randomrotationsinafiniteprimefield . . . . . . . . . . . . . . . . . 23 4.6.3 Creatinga3Dsceneinafiniteprimefield . . . . . . . . . . . . . . . . 23 5 Absolute pose for a calibrated camera 27 5.1 Problemformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 AnglesandDistances. Cosinelaw . . . . . . . . . . . . . . . . . . . . . . . . 28 5.3 Camerarigidmotion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3.1 Distancebetweenpoints . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3.2 Ratiosofdistances . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.4 Homographyandcameraabsolutepose . . . . . . . . . . . . . . . . . . . . . 32 5.5 Syntheticexperiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5.1 Numericalstability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6 Absolute pose for a camera with an unknown focal length 39 vii Contents 6.1 Problemformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.1.1 Usingdistances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.1.2 Usingratiosofdistances . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2 Hiddenvariablesolverrevisited . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.3 Gro¨bnerbasissolverrevisited. . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.4 Creatinganoptimalratiosolver . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.4.1 Reducinginputequations . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.4.2 Exhaustivesearchforthebestsolver . . . . . . . . . . . . . . . . . . . 50 6.5 Creatinganoptimaldistancesolver . . . . . . . . . . . . . . . . . . . . . . . . 55 6.5.1 Exhaustivesearchforthebestsolver . . . . . . . . . . . . . . . . . . . 56 6.5.2 Singlesolutioncase . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.6 Rotationmatrixparametrizedusingquaternions . . . . . . . . . . . . . . . . . 60 6.7 Projectionmatrixparametrizedusinganullspace . . . . . . . . . . . . . . . . 62 6.7.1 Solverforaplanarscene . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.7.2 Generalsolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.8 Algorithmcomparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.8.1 Syntheticdatasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.8.2 Algorithmsaccuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.8.3 Syntheticnoisetests . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.8.4 Realdataexperiment . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7 An unknown focal length and a radial distortion 73 7.1 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.2 Absoluteposeforacamerawithunknownfocallengthandradialdistortionfor anon-planarscene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7.3 Absoluteposeforacamerawithunknownfocallengthandradialdistortionfor planarscene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.4.1 Syntheticdatasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.4.2 Numericalstability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.4.3 Experimentwithsyntheticnoise . . . . . . . . . . . . . . . . . . . . . 80 7.4.4 Computationalcomplexity . . . . . . . . . . . . . . . . . . . . . . . . 81 7.4.5 GeneralSolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 7.4.6 Realdataexperiment . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8 Known vertical direction 85 8.1 Problemformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.2 Absoluteposeofacalibratedcamerawithknownupdirection . . . . . . . . . 88 8.3 Absoluteposeofacamerawithunknownfocallengthandradialdistortionand knowncameraupdirection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 8.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 viii