Fitting Parameterized Three-dimensional Models to Images(14)

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

Sinceisadiagonalmatrix,isalsodiagonalbutwitheachelementonthediagonalsquared.Thismeansthatthecomputationalcostofthestabilizationistrivial,aswecan rst

andthensimplyaddsmallconstantstothediagonalthataretheinverseofthesquareform

ofthestandarddeviationofeachparameter.Ifisnon-zero,thenweaddthesameconstantsmultipliedbytotherighthandside.Iftherearefewerrowsintheoriginalsystemthanparameters,wecansimplyaddenoughzerorowstoformasquaresystemandaddtheconstantstothediagonalstostabilizeit.

5.3Forcingconvergence

Evenafterincorporatingthisstabilizationbasedonapriormodel,itispossiblethatthesystemwillfailtoconvergetoaminimumduetothefactthatthisisalinearapproximationofanon-linearsystem.Wecanforceconvergencebyaddingascalarparameterthatcanbeusedtoincreasetheweightofstabilizationwheneverdivergenceoccurs.Thenewformofthissystemis

Thissystemminimizes

ManypeopleinthevisioncommunitywillrecognizethisasanexampleofregularizationusingaTikhonov[33]stabilizingfunctional,ashasbeenappliedtomanyareasoflow-levelvision(Poggioetal.[28]).Inthiscase,theparametercontrolsthetrade-offbetweenapprox-

,andminimizingthedistanceofthesolutionfromitsoriginalimatingthenewdata,

.startingposition,priortonon-lineariteration,

Theuseofthisparametertoforceiterativeconvergenceforanon-linearsystemwas rststudiedbyLevenberg[17]andlaterreducedtoaspeci cnumericalprocedurebyMarquardt

[24].Theyrealizedthatastheparameterisincreased,thesolutionwouldincreasinglycor-respondtopuregradientdescentwithsmallerandsmallerstepsizes,alongwithitspropertiesofguaranteed(butslow)convergence.Fordecreasing,theprobleminsteadmovesovertoNewton’smethod,withitsfastquadraticconvergencenearthesolutionbutthepossibilityofdivergencewhenstartingtoofaraway.Therefore,Marquardtsuggestedthesimplesolutionofmonitoringtheresidualofeachsolutionandincreasingbyfactorsof10untiltheresidualde-creased;otherwise,isdecreasedbyafactorof10oneachiteration.Thisdoesnotguaranteeanyparticularrateofconvergenceandcan,ofcourse,convergetoalocalratherthanglobalminimum.However,ithasprovedhighlyeffectiveinpracticeandisoneofthemostwidelyusedmethodsfornon-linearleast-squares.

Marquardtdidnotassumeanypriorknowledgeoftheweightingmatrix,butinstead

.estimatedeachofitselementsfromtheeuclideannormofthecorrespondingcolumnof

allowsthealgorithmtoperformmuchbetterwhenacolumnInourcase,theavailablityof

ofisnearzero.Italsogivesthestabilizationamuchmorepredictablebehavior.Increasingthevalueofwillessentiallyfreezetheparametershavingtheloweststandarddeviationsand

14