An-Efficient-Solution-to-the-Five-Point-Relative-P

AnEfficientSolutiontotheFive-PointRelativePoseProblemDavidNist´erSarnoffCorporationCN5300,Princeton,[e-mail]ficientalgorithmicsolutiontotheclassicalfive-pointrelativeposeproblemispresented.Theproblemistofindthepossiblesolutionsforrelativecameraposebetweentwocalibratedviewsgivenfivecorrespondingpoints.Thealgo-rithmconsistsofcomputingthecoefficientsofatenthde-greepolynomialinclosedformandsubsequentlyfindingitsroots.Itisthefirstalgorithmwellsuitedfornumericalim-plementationthatalsocorrespondstotheinherentcomplex-ityoftheproblem.Weinvestigatethenumericalprecisionofthealgorithm.Wealsostudyitsperformanceundernoiseinminimalaswellasover-determinedcases.Theperfor-manceiscomparedtothatofthewellknown8and7-pointmethodsanda6-pointscheme.Thealgorithmisusedinarobusthypothesize-and-testframeworktoestimatestruc-tureandmotioninreal-timewithlowdelay.Thereal-timesystemusessolelyvisualinputandhasbeendemonstratedatmajorconferences.Keywords:ImagingGeometry,Motion,RelativeOrien-tation,StructurefromMotion,CameraCalibration,Ego-motionEstimation,SceneReconstruction.1.IntroductionReconstructionofcamerapositionsandscenestructurebasedonimagesofscenefeaturesfrommultipleviewpointshasbeenstudiedforovertwocenturies,firstbythepho-togrammetrycommunityandmorerecentlyincomputervi-sion.Intheclassicalsetting,theintrinsicparametersofthecamera,suchasfocallength,areassumedknownapri-ori.Thiscalibratedsettingiswherethefive-pointprob-lemarises.Giventheimagesoffiveunknownscenepointsfromtwodistinctunknownviewpoints,whatarethepossi-blesolutionsfortheconfigurationofthepointsandcam-eras?Clearly,onlytherelativepositionsofthepointsandcamerascanberecovered.Moreover,theoverallscaleofPreparedthroughcollaborativeparticipationintheRoboticsConsortiumsponsoredbytheU.S.ArmyResearchLaboratoryundertheCollaborativeTechnologyAllianceProgram,CooperativeAgreementDAAD19-01-2-0012.TheU.S.GovernmentisauthorizedtoreproduceanddistributereprintsforGovernmentpurposesnotwithstandinganycopyrightnotationthereon.theconfigurationcanneverberecoveredsolelyfromim-ages.Apartfromthisambiguity,thefive-pointproblemwasprovenbyKruppa[19]tohaveatmostelevensolutions.Thiswaslaterimprovedupon[3,4,6,22,16],showingthatthereareatmosttensolutionsandthattherearetensolu-tionsingeneral(includingcomplexones).Thetensolutionscorrespondtotherootsofatenthdegreepolynomial.How-ever,Kruppa’smethodrequiresthenon-trivialoperationoffindingallintersectionsbetweentwosexticcurvesandthereisnopreviouslyknownpracticalmethodofderivingthecoefficientsofthetenthdegreepolynomialinthegeneralcase.Afewalgorithmssuitablefornumericalimplemen-tationhavealsobeendevised.In[44]a60×60sparsematrixisbuilt,whichissubsequentlyreducedusinglinearalgebratoa20×20non-symmetricmatrixwhoseeigenval-uesandeigenvectorsencodethesolutiontotheproblem.In[32]anefficientderivationisgiventhatleadstoathirteenthdegreepolynomialwhoserootsincludethesolutionstothefive-pointproblem.Thesolutionpresentedinthispaperisarefinementofthis.Abettereliminationthatleadsdirectlyinclosedformtothetenthdegreepolynomialisused.Thus,anefficientalgorithmthatcorrespondsexactlytotheintrin-sicdegreeofdifficultyoftheproblemisobtained.Forthestructureandmotionestimationtoberobustandaccurateinpractice,morethanfivepointshavetobeused.Theclassicalwayofmakinguseofmanypointsistomini-mizealeastsquaresmeasureoverallpoints,seeforexam-ple[18].Ourintendedapplicationforthefive-pointalgo-rithmisasahypothesisgeneratorwithinarandomsampleconsensusscheme(RANSAC)[8,26].Manyrandomsam-plescontainingfivepointcorrespondencesaretaken.Eachsampleyieldsanumberofhypothesesfortherelativeori-entationthatarescoredbyarobuststatisticalmeasureoverallpointsintwoormoreviews.Thebesthypothesisisthenrefinediteratively.Suchahypothesize-and-testarchitecturehasbecomethestandardwayofdealingwithmismatchedpointcorrespondences[41,48,14,24]andhasmadeauto-maticreconstructionsspanninghundredsofviewspossible[1,34,7,25].Therequirementofpriorintrinsiccalibrationwasre-laxedinthelastdecade[5,12,14],leadingtohigherflex-ibilityandlesscomplicatedalgorithms.So,whyconsiderthecalibratedsetting?Apartfromthetheoreticalinterest,oneanswertothisquestionconcernsstabilityandunique-nessofsolutions.Enforcingtheintrinsiccalibrationcon-straintsoftengivesacrucialimprovementofboththeaccu-racyandrobustnessofthestructureandmotionestimates.Currently,thestandardwayofachievingthisisthroughaninitialuncalibratedestimatefollowedbyiterativerefine-menttobringtheestimateintoagreementwiththecalibra-tionconstraints.Whentheintrinsicparametersareknownapriori,thefive-pointalgorithmisamoredirectwayofen-forcingthecalibrationconstraintsexactlyandobtainingaEuclideanreconstruction.Theaccuracyandrobustnessim-provementsgainedbyenforcingthecalibrationconstraintsareparticularlysignificantforplanarornearplanarscenesandscenesthatappearplanarintheimagery.Theuncali-bratedmethodsfailwhenfacedwithcoplanarscenepoints,sincethereisthenacontinuumofpossiblesolutions.Ithasbeenproposedtodealwiththisdegeneracyusingmodelse-lection[43,35],switchingbetweenahomographicmodelandthegeneraluncalibrated