Multiple View Geometry and Convex Optimization

MultipleViewGeometryandConvexOptimizationKristyKarenWanYenSimAthesissubmittedforthedegreeofDoctorofPhilosophyatTheAustralianNationalUniversitySeptember2007c
KristyKarenWanYenSim,September2007Chapters5and6ofthisthesiswerepublishedasjointpaperswithmysupervisor,Prof.RichardHartley,whoguidedmeinthedefinitionoftheproblem,andtheapproachtaken.Otherwise,thisthesisisentirelymyownwork.KristyKarenWanYenSim18September2007AbstractMultipleViewGeometryisanareaofcomputervisionthatisconcernedwithrecov-eringthegeometricalinformationinastationaryscenegivenmultipleviewsofthescene.Optimizationisatoolthatisofgreatimportanceinmultipleviewgeometry.Indeed,manycoreproblemsinmultipleviewgeometryaresolvedbyformulatingthemasoptimizationproblems.Theseoptimizationmethodsarethenusuallysolvedusinglinearmethodsbasedonthesingularvaluedecompositionoriterativeestimationalgorithmsbasedonmin-imizingtheL2norm.Whilelinearmethodsyieldclosed-formsolutions,areeasytoimplementandcomputationallyefficient,theirdisadvantageisthatthequantitybe-ingminimizedisnotgeometricallyorstatisticallymeaningful.Ontheotherhand,L2algorithmsarestatisticallyoptimalbuttheyareoftenslow,reliantongoodinitializa-tionandpronetoconvergencetolocalminimaandinfeasiblesolutions.Theaimofthisthesisistoinvestigatetheuseofconvexoptimizationtechniquesinmultipleviewgeometry.Onekeyadvantageofconvexoptimizationmethodsistheexistenceofasingleminima.Hence,thereisnoproblemwithfallingintoalocalminimumunlikeL2algorithms.Convexoptimizationalsohastheadvantagethatthecostfunctionbeingminimizedtypicallyhasageometricalmeaningunlikelinearmethods.Onthecomputationalsideofthings,convexmethodsarerelativelyfastandquiteeasytoimplement.Inaddition,withconvexmethods,weareabletoaddconstraintstotheoptimiza-tionmethodstherebyallowingustoincorporateanypriorknowledgeaboutthesolu-tionintotheoptimizationproblem.Indoingso,wealsoreducethesearchspaceandpreventconvergencetoinfeasiblesolutions.Overall,wefoundconvexoptimizationtobeaviablealternativetothelinearandL2estimationalgorithmstypicallyusedinmultipleviewgeometry.iiiAcknowledgementsMythanksgo,firstandforemost,toRichardHartley.Thankyouforyourwisdom,advice,guidance,supportandpatience.Ihavelearnedmuchfromyouovertheyearsand,undoubtedly,thisthesiscouldnothavebeenwrittenwithoutyou.Also,thankyoutoRobertWilliamsonandAlexanderSmolaforyouradviceandguidancethroughouttheyears.Iwouldalsoliketothankthefollowingpeopleinthecomputervisioncommu-nitywhomIhavemetalongtheway:GarethLoyforintroducingmetocomputervision;BarbaraCaputoforyourassistanceinthefirstyearofthePhD;FrederikSchaf-falitzkyforyourhelpwithtargetjrintheearlyyears;FredrikKahlforprovidingmewiththevisionarytoolboxinMatlab;NoahSnavelyforprovidingtheNotreDamedataset;NiklasPetterssonforallyourhelpinprocessingthelargeNotreDamedatasetandforprovidingmewithaccesstomorecomputingpoweratatimewhenitwasmuchneeded;ShyjanMahamudforbeingactingsupervisorwhentheneedarose;andHong-DongLiandJae-HakKimforgeneraldiscussionsoncomputervision.ThankyoualsotoManfredDoudarfortipsonC++andpropercodingpractice.Finally,thankyoutomyfamilyand,lastbutcertainlynotleast,AndyandNiklas.Thankyouforalwaysbeingthere.ivContentsAbstractiiiAcknowledgementsiv1Introduction11.1WhatisComputerVision?...........................11.2MultipleViewGeometry............................21.3MultipleViewGeometryandOptimization.................51.4MultipleViewGeometryandConvexOptimization............71.5ThesisContributionsandOutline.......................92BasicConceptsinMultipleViewGeometry122.1Notation.....................................122.22DProjectiveGeometry............................122.33DProjectiveGeometry............................182.4Single-ViewGeometry.............................192.5Two-ViewGeometry..............................232.6Three-ViewGeometry.............................262.7Cheirality.....................................293BasicConceptsinConvexOptimization343.1Notation.....................................343.2ConvexSets...................................353.3ConvexFunctions................................393.4ConvexOptimizationProblems........................463.5Second-OrderConeProgramming......................514MultipleViewGeometryandOptimization-AReviewandComparison584.1Notation.....................................584.2HomographyEstimation............................594.3CameraResectioning..............................644.4Triangulation..................................674.5Reconstruction..................................71vContentsvi4.6Conclusion....................................775CameraMotionRecoveryandtheL∞Norm795.1Notation.....................................805.2VisualOdometry................................805.3ComputingImagePointTracks........................815.4ComputingCameraRotations.........................825.5ComputingCameraTranslations.......................835.6Experiments...................................1095.7Conclusion....................................1186OutlierRemovalandtheL∞Norm1196.1ABriefReview.................................1196.2