Fitting Parameterized Three-dimensional Models to Images(9)

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

theHouseholderalgorithminordertosolveproblemsthatareequallyill-conditioned[9,16].Giventhestabilizationmethodsdescribedbelow,thenormalequationsareneversuf cientlyill-conditionedtorequiremorethansingle-precision oatingpointarithmetic,andthereforearemoreef cientinpracticethananyofthecompetingmethods.Evenifhigherprecisionwererequired,thetrade-offsforsingleversusdoubleprecisioncomputationonmodernhardwarewouldlikelyfavorthenormalequations.

4.2Ef cientcomputationofpartialderivatives

OneofthemostexpensiveaspectsofimplementingthissolutionmethodiscalculatingtheJacobianmatrixofpartialderivatives.Therefore,wehavedevelopedmethodsforusingpre-computationandshareddatastructurestoreducethesecosts.Inaddition,aspecialtechniqueisusedtohandlederivativeswithrespecttofull3-Drotationsinordertoeliminatesingularitiesandincreasetherateofconvergence.

Asdescribedearlierinthesectiononmodelrepresentation,allmodelpointsareleavesinatreeof“frame”datastructures.Eachframerepresentsarotationortranslationwithrespecttoitsparent.Therefore,bytracingbacktotherootofthetreefromeachmodelpoint,itispossibletoidentifythesetofvariabletransformationsthatin uencethatpoint.Eachframedatastructurealsocontainsprecomputedresultsforthecurrentviewthatcanbeusedbyallpointswhichdependonthatframeinordertocomputetheirpartialderivativeswithrespecttothatframe’sparameters.Asthereareusuallymanypointsin uencedbyeachframe,anyprecomputationofresultsfortheframeisfarmoreef cientthancomputingthemforeachpoint.

Itispossiblethatthesameparameterwillappearinmorethanoneframealongapaththroughthetree(e.g.,thelast2jointsofahuman ngerdonotmoveindependently,butdependonasingleparameteroftendoncontraction).Thiscaseiseasilyhandledbysimplysummingallofthepartialderivativesforaparticularparameter.

Eachtypeofframetransformationrequiresdifferentprecomputedresults,sothesearede-scribedindividuallyasfollows.

Translation.Eachvariabletranslationframecontainsa3-Dvectorgivingthedirectionalderiva-tiveincamera-centeredcoordinateswithrespecttothatframe’svariable.Asallpointsdepend-ingonthatframewillhavethissamedirectionalderivative,nofurthercomputationisrequired.Rotationaboutoneaxis.Eachvariablerotationframecontainsthe3-Dangularvelocityvectorandtheoriginofrotationforthecurrentviewpoint.Thedirectionalderivativeofeachpointthatdependsontheframeiscomputedbytakingthecrossproductoftheangularvelocityvectorwiththevectorfromtheoriginofrotationtothepoint.

Rotationaboutthreeaxes.Ifwecomposethreerotationsaboutindividualaxesinordertocom-puteanarbitrary3-Drotation,singularitiescaneasilyresultwherethesequentialcompositionofthethreerotationsfailtospecifyindependentdirectionsofrotation.Therefore,werepresentfullthree-degree-of-freedomrotationswitha3by3rotationmatrix,andcomputecorrectionsabouteachofthecoordinateaxestobecomposedwiththisrotation.Thisalsohasthebene t

9