Fitting Parameterized Three-dimensional Models to Images(8)

Model-based recognition and motion tracking depends upon the ability to solve for projection and model parameters that will best fit a 3-D model to matching 2-D image features. This paper extends current methods of parameter solving to handle objects with

4.1Newton’smethodandleast-squaresminimization

Ratherthansolvingdirectlyforthevectorofnon-linearparameters,,Newton’smethodcom-putesavectorofcorrections,,tobesubtractedfromthecurrentestimateforoneachitera-

istheparametervectorforiteration,then,tion.If

Givenavectoroferrormeasurements,,betweencomponentsofthemodelandtheimage,wewouldliketosolveforanthatwouldeliminatethiserror.Basedontheassumptionoflocallinearity,theaffectofeachparametercorrection,,onanerrormeasurementwillbemultipliedbythepartialderivativeoftheerrorwithrespecttothatparameter.Therefore,wewouldliketosolveforinthefollowingmatrixequation:

whereJistheJacobianmatrix:

Eachrowofthismatrixequationstatesthatonemeasurederror,,shouldbeequaltothesumofallthechangesinthaterrorresultingfromtheparametercorrections.Ifalltheseconstraintscanbesimultaneouslysatis edandtheproblemislocallylinear,thentheerrorwillbereducedtozeroaftersubtractingthecorrections.

Iftherearemoreerrormeasurementsthanparameters,thissystemofequationsmaybeoverdetermined(infact,thiswillalwaysbethecasegiventhestabilizationmethodspresentedbelow).Therefore,wewill ndanthatminimizesthe2-normoftheresidualratherthansolvesforitexactly:

min

Since

solutionasthenormalequations,,itcanbeshownthatthisminimizationhasthesame

whereisthetransposeofJ.Thisminimizationismakingtheassumptionthattheoriginalnon-linearfunctionislocallylinearovertherangeoftypicalerrors,whichistruetoahighdegreeofapproximationfortheprojectionfunctionwithtypicalerrorsinimagemeasurements.

andTherefore,oneachiterationofNewton’smethod,wecansimplymultiplyout

inthenormalequations(1)andsolveforusinganystandardmethodforsolvingasystemoflinearequations.Manynumericaltextscriticizethisuseofthenormalequationsaspotentiallyunstable,andinsteadrecommendtheuseofHouseholderorthogonaltransformationsorsingularvaluedecomposition.However,aclosestudyofthetrade-offsindicatesthatinfactthenormalequationsprovidethebestsolutionmethodforthisproblem.ThesolutionusingthenormalequationsrequiresonlyhalfasmanyoperationsastheHouseholderalgorithm(andanevensmallerfractionwithrespecttoSVD),butrequiresaprecisionoftwicetheword-lengthof

8