Fitting Parameterized Three-dimensional Models to Images

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

FittingParameterizedThree-DimensionalModelstoImages

DavidG.Lowe

ComputerScienceDepartment

UniversityofBritishColumbia

Vancouver,B.C.,CanadaV6T1Z4

Email:lowe@cs.ubc.ca

Abstract

Model-basedrecognitionandmotiontrackingdependsupontheabilitytosolveforprojectionandmodelparametersthatwillbest ta3-Dmodeltomatching2-Dimagefeatures.Thispaperextendscurrentmethodsofparametersolvingtohandleobjectswitharbitrarycurvedsurfacesandwithanynumberofinternalpa-rametersrepresentingarticulations,variabledimensions,orsurfacedeformations.Numericalstabilizationmethodsaredevelopedthattakeaccountofinherentinac-curaciesintheimagemeasurementsandallowusefulsolutionstobedeterminedevenwhentherearefewermatchesthanunknownparameters.TheLevenberg-Marquardtmethodisusedtoalwaysensureconvergenceofthesolution.Thesetechniquesallowmodel-basedvisiontobeusedforamuchwiderclassofprob-lemsthanwaspossiblewithpreviousmethods.Theirapplicationisdemonstratedfortrackingthemotionofcurved,parameterizedobjects.

ThispaperhasbeenpublishedinIEEETransactionsonPatternAnalysisandMachineIntelligence,13,5(May1991),pp.441–450.

1

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

1Introduction

Model-basedvisionallowspriorknowledgeoftheshapeandappearanceofspeci cobjectstobeusedduringtheprocessofvisualinterpretation.Reliableidenti cationscanbemadebyidentifyingconsistentpartialmatchesbetweenthemodelsandfeaturesextractedfromtheimage,therebyallowingthesystemtomakeinferencesaboutthescenethatgobeyondwhatisexplicitlyavailablefromtheimage.Byprovidingthislinkbetweenperceptionandpriorknowledgeofthecomponentsofthescene,model-basedrecognitionisanessentialcomponentofmostpotentialapplicationsofvision.

Oneimportantcomponentofmodel-basedvisionistheabilitytosolveforthevaluesofallviewpointandmodelparametersthatwillbest tamodeltosomematchingimagefeatures.Thisisimportantbecauseitallowssometentativeinitialmatchestoconstrainthelocationsofotherfeaturesofthemodel,andtherebygeneratenewmatchesthatcanbeusedtoverifyorrejecttheinitialinterpretation.Thereliabilityofthisprocessandthe nalinterpretationcanbegreatlyimprovedbytakingaccountofallavailablequantitativeinformationtoconstraintheunknownparametersduringthematchingprocess.Inaddition,parameterdeterminationisnecessaryforidentifyingobjectsub-categories,forinterpretingimagesofarticulatedor exibleobjects,andforroboticinteractionwiththeobjects.

Inmostcases,itispossibletosolveforallunknownparametersfora3-Dmodelfrommatchestoasingle2-Dimage.However,insomecircumstances—suchaswhenboththesizeanddistanceofthemodelisunknown—theaccuracyofparameterdeterminationcanbesub-stantiallyimprovedbysimultaneously ttingthemodeltoimagestakenfrommorethanoneviewpoint.Themethodspresentedherecanbeusedineithersituation.

Thelocationsofprojectedmodelfeaturesinanimageareanon-linearfunctionoftheview-pointandmodelparameters.Therefore,thesolutionisbasedonNewton’smethodoflineariza-tionanditerationtoperformaleast-squaresminimization.Thisisaugmentedbyastabilizationmethodthatincorporatesapriormodeloftherangeofuncertaintyineachparameterandesti-matesofthestandarddeviationofeachimagemeasurement.Thisallowsusefulapproximateso-lutionstobeobtainedforproblemsthatwouldotherwisebeunderdeterminedorill-conditioned.Inaddition,theLevenberg-Marquardtmethodisusedtoalwaysforceconvergenceofthesolu-tiontoalocalminimum.Thesetechniqueshaveallbeenimplementedandtestedaspartofasystemformodel-basedmotiontracking,andtheyhavebeenfoundtobereliableandef cient.2Previousapproaches

AttemptstosolveforviewpointandmodelparametersdatebacktotheworkofRoberts[30].Althoughhissolutionmethodswerespecializedtocertainclassesofobjects,suchasrectangularblocks,Robertsclearlyunderstoodthevalueofquantitativeparameterdeterminationformakingvisionrobustagainstmissingandnoisydata.Unfortunately,therewerefewattemptstobuilduponthisworkformanyyearsfollowingitsinitialpublication.

In1980,theauthor[19]presentedageneraltechniqueforsolvingforviewpointandmodel

2

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

parametersusingNewton’smethodfornonlinearleast-squaresminimization.Sincethattimethemethodhasbeenusedsuccessfullyinanumberofapplications,anditalsoprovidesthestartingpointfortheworkpresentedinthispaper.Theapplicationofthemethodtorobustmodel-basedrecognitionhasbeendescribedbyLowe[20,21,22],McIvor[26],andWorrall,Baker&Sullivan[34].Bray[2]hasappliedthemethodtomodel-basedmotiontrackingofrigidobjects.Ishiietal.[14]describetheapplicationofthisworktotheproblemoftrackingtheorientationandlocationofarobothandfromasingleviewofLEDtargetsmountedonthewrist.Theirpaperprovidesadetailedanalysisthatshowsgoodaccuracyandstability.Goldberg&Lowe[8]describetheapplicationandtestingofanumberofmoreadvancednumericalmethodsforthisproblem.

Inrecentyears,therehasbeenaconsiderableincreaseinthenumberofpublicationsonparametersolvingformodel-basedvision,withmostoftheworkaimedatsolvingforviewpointparametersofrigidobjects.Liuetal.[18]andKumar[15]haveexaminedalternativeiterativeapproachestosolvingfortheviewpointparametersbyseparatingthesolutionforrotationsfromthosefortranslations.However,Kumarshowsthatthisapproachleadstomuchworseparameterestimatesinthepresenceofnoisydata.Therefore,headoptsasimilarsimultaneousminimizationasisusedintheworkabove.AquitedifferentapproachbasedontheuseofeliminationmethodstoprovidetheinitialproblemformulationhasbeenproposedbyPonceandKriegman[29].ThisalsousesNewton’smethodforthe nalparameterdeterminationbasedonleast-squaresminimization.

Haralicketal.[11]haveexperimentedwithrobustmethodssuchasiterativereweightinginordertoallowforoutlierscausedbyincorrectmatches.However,theirresultsshowthatevenoneoutlieramong20correctmatchesleadstoalargeincreaseinexpectederrorfollowingreweighting.Thealternativethatisusedinthispaperistoprovideahigher-levelsearchprocessthatconsidersothersetsofmatcheswhenthe rstsetfailstoresultinanaccurate tofthemodel.

2.1Theproblemofmultiplesolutions

Muchworkhasbeenpublishedoncharacterizingtheminimumamountofdataneededtosolveforthesixviewpointparameters(assumingarigidobject)andonsolvingforeachofthemulti-plesolutionsthatcanoccurwhenonlythisminimumdataisavailable.FischlerandBolles[6]showthatuptofoursolutionswillbepresentfortheproblemofmatching3modelpointsto3imagepoints,andtheygiveaprocedureforidentifyingeachofthesesolutions.Asolutionforthecorresponding4-pointproblem,whichcanalsohavemultiplesolutionsundersomecir-cumstances,isgivenbyHoraudetal.[12].HuttenlocherandUllman[13]showthatthe3-pointproblemhasasimplesolutionfororthographicprojection,whichisasuf cientlycloseapprox-imationtoperspectiveprojectionforsomeapplications.Theyusetheterm“alignment”torefertothesolutionforviewpointparametersduringthemodel ttingprocess.Inthemostvaluabletechniqueformanypracticalapplications,Dhomeetal.[4]giveamethodfordeterminingallsolutionstotheproblemofmatching3modellinesto3imagelines.Theyshowthatthisispar-ticularlyusefulforgeneratingstartingpositionsfortheiterativetechniquesusedinthispaper

3

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

whentherearemultiplesolutions.

Thisworkondeterminingallpossibleexactsolutionswillnodoubtbeimportantforsomespeci cvisionapplications,butitisprobablynotthebestapproachforpracticalparameterdeterminationingeneralmodel-basedvision.Oneproblemwiththesemethodsisthattheydonotaddresstheissueofill-conditioning.Evenifaproblemhasonlyoneanalyticsolution,itwilloftenbesuf cientlyill-conditionedinpracticetohaveasubstantialnumberandrangeofsolutions.Secondly,allthesemethodsdealwithspeci cpropertiesofthesixviewpointparameters,andthereislittlelikelihoodthattheycanbeextendedtodealwithanarbitrarynumberofinternalmodelparameters.Finally,thesemethodsfailtoaddresstheproblemofwhattodowhenthesolutionisunderconstrained.Thestabilizationmethodsdescribedinthispaperallowanapproximatesolutiontobeobtainedevenwhenaproblemisunderconstrained,aswilloftenbethecasewhenmodelscontainmanyparameters.

Possiblythemostconvincingreasonforbelievingthatitisnotnecessarytodetermineallpossiblesolutionsisthefactthathumanvisionapparentlyalsofailstodoso.Thewell-knownNeckercubeillusionillustratesthathumanvisioneasilyfallsintoalocalminimuminthedeter-minationofviewpointparameters,andseemsunabletoconsidermultiplesolutionsatonetime.Rock[31],pp.22ffsummarizesthewayinwhichhumanperceptionseemstoalwaysadoptoneparticularperceptionatanytimeeveninthefaceofcompletelyindeterminatecontinuousvariables.Theperceptioncansuddenlychangetoanewstablepositioninthefaceofnewin-formation,whichmaycomeinternallyfromothercomponentsofthevisualsystem(attention)aswellasfromtheexternalstimulus.Thisbehaviorisconsistentwithastabilizedminimiza-tionapproachfordeterminingtheparametervalues,inwhichtheprocesscanbeinitiatedfromnewstartingpointsasnewinformationbecomesavailable.Theextremelygoodperformanceofhumanvisioninmostrecognitionproblems,inspiteofitspotentialforgettingstuckinfalselocalminima,indicatesthatlocalminimamaynotbeamajorproblemwhendeterminingmodelparameters.

Itisworthnotingthattheparametersolvingproblemissimpli edwhenaccurate3-Dim-agedataisavailable(asfromascanninglaserrange nder),sincethisavoidssomeofthenon-linearitiesresultingfromprojection.ExamplesofsolutionstothisproblemaregivenbyFaugeras&Hebert[5]andGrimson&Lozano-P´erez[10].However,inthispaperwerestrictourattentionto tting3-Dmodelsto2-Dimagefeatures.

3Objectandscenemodeling

Mostresearchinmodel-basedvisionhasbeenbasedonmodelsofsimplepolyhedral3-Dob-jects.Whiletheyaresimpletoworkwith,theyareclearlyinadequateforrepresentingmanyreal-worldobjects.Someresearchhasbeenbasedonmodelsbuiltfromcertainclassesofvol-umetricprimitives,mostnotablygeneralizedcylinders[1,3]andsuperquadrics[27].Whiletheseareattractivebecauseoftheirabilitytocapturecommonsymmetriesandrepresentcertainshapeswithfewparameters,theyareill-suitedformodelingmanynaturalobjectsthatdonotexhibitthesetofregularitiesincorporatedintotheprimitives.

4

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

Camera-centered

stretching subpart

Figure1:Modelpoints(incircles)arerepresentedasleavesinatreeofrotationortranslationtransformations.Thepositionandpartialderivativesofeachpointincamera-centeredcoordi-natesisdeterminedbythetransformationsalongthepathbacktotheroot.

The eldthathasmostthoroughlyexaminedtheproblemofrepresentingthevisualappear-anceofarbitraryobjectsiscomputergraphics.Thelessonsfromdevelopmentsinthat eldarequiteclear:complexanalyticrepresentationshavegivenwaytosimplelocalapproximationsasthemostcost-effectivesolution.Themostcommonformsoflocalapproximationnowusedformodelrepresentationpriortorenderingarepolygonalsurfacepatches,withtheappropriateinterpolationinthevariousparametersofinterestfordisplay.Sinceanarbitraryfunctioncanbeapproximatedtoanydesireddegreeofaccuracybyusingenoughsimplelocalapproximations,theonlyimportantissueatthislevelofrepresentationisoneofef ciency.Experienceincom-putergraphicshastendedtoshowthattheincreasednumberofapproximatingpatchesrequiredforsimplelinearapproximationsismorethancompensatedforbythespeedwithwhichtheycanbemanipulated.Ofcourse,morecomplexsplinesandvolumetricprimitivesmaystillbeusedformodelinputorotherhigher-levelreasoning.

Aswithcomputergraphics,visionisbasedupontheartofapproximation.Ofcourse,itisimportanttoapproximatetheappropriatemeasurements,asotherwiseanapproximationinonequantitymayintroduceunwantederrorsinitsderivativesorotherfunctionsthatdependuponit.Inmodel-basedvision,weareconcernedwithcorrectlyapproximatingthosefunctionsthatwillbematchedwithimagemeasurements.Inthecaseofedge-basedmatching,thiswill

5

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

includetheprojectedlocations,tangents,curvatures,anddiscontinuitiesofedges.Ifshadingorsurfacepropertieswerebeingmatched,thensurfacecurvaturesmustalsobeapproximated.Wehavedevelopedamodelingsystemthatallowsthesequantitiestobemodeledasafunctionofviewpointandinternalmodelparameterstoanydesireddegreeofaccuracyandusedforef cientparametersolving.

Althoughmodel-basedvisioncanlearnmuchfromcomputergraphics,themodelingre-quirementsalsohaveimportantdifferences.Inmodel-basedmatchingto2-Dimages,themod-elsarematchedtoderivedimagefeaturesratherthanbeingusedtogeneratedensesurfacedescriptions.Forexample,itisimportanttobeabletodirectlycalculatethepositionsofoc-cludingcontours,whichisnotpossibleinmanymodelingsystemsdevelopedforcomputergraphics.Sincethemodelsareprojectedandmanipulatedintheinner-loopofthematchingprocess,itisimportantthatallpossiblesourcesofef ciencyparticulartothevisiondomainbeexploited.Inaddition,certainquantitiesthatdonotoccuringraphicsapplications,suchasderivativeswithrespecttomodelparameters,mustbeef cientlyrepresentedandcomputed.Forallthesereasons,itisnecessarytodevelopamodelingsystemaimedatvisionratherthanadoptingexistingsystemsdevelopedforgraphics.

Asimplemodelinglanguagehasbeendevelopedthatcanbeusedtodescribearbitrarymod-elsandtheirinternalparametersforuseinmodel-basedvision.Thelanguageisusedtode neandname3-Dpoints,edgesandsurfacepatches,aswellasmodelparametersde ningrotationsandtranslations.Eachmodelpointisaleafinatreeofcoordinatetransformationsthatrep-resentanycombinationofpreviousrotationsandtranslationsspeci edbydifferentparameters(seeFigure1).Thesamemechanismisusedtohandlebothviewpointparametersandinternalmodelparameters,sotherootofthistreerepresentsthecameracoordinateframe.

Whenaninternalmodelisbuiltfromadescriptioninthislanguage,adensepointernetworkisconstructedthatlinkseachedgeelementtoitsadjoiningsurfacepatchesandendpoints.Acachingmechanismisusedsothatthevisibilityofeachsurfacepolygonandtheprojectionofeachpointiscalculatedonlyonce,unlikeinmostgraphicsmodelingsystems.Becauseeachpointonasurfaceorlinemaymoveindependentlybybeingattachedtodifferentframes,itispossibletospecifyarbitrary exiblemotionsofmodels.Forexample,thelineconnectingthepointsFandGinFigure1canstretchunderthein uenceofparameterandrotateinconjunctionwithanothermodelsubpartunderthein uenceofparameter(eachtranslationframespeci esatranslationdirectionandeachrotationspeci esarotationaxis).

Edgesarelabeledaccordingtowhethertheylieonasmoothsurfaceorformadiscontinuity.Bycachingarecordofthesurfacenormalforthepatchoneachsideofeachedge,thevisibil-ityandlocationsoftheoccludingboundariesandsurfacediscontinuitiescanbegeneratedveryef ter,wewilldescribehowthemodelrepre-sentationenablestheef cientcomputationofpartialderivativesofimagefeatureswithrespecttoeachparameter.

6

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

Figure2:Anexampleofamodelwithcurvedsurfacesandaninternalparameterspecifyingrotationofthehandle.Theunderlyingapproximatingpatchesareshownontheleft,andthegeneratedcontoursformatchingareshownontheright.

4Solvingforviewpointandmodelparameters

Projectionfrom3-Dto2-Disanon-linearoperation.Fortunately,however,itisasmoothandwell-behavedtransformation.Rotationindepthpriortoprojectiontransformstheprojectedpointsasafunctionofthecosineoftherotationangle.Translationtowardsorawayfromthecameraintroducesperspectivedistortionasafunctionoftheinverseofthedistance.Translationparalleltotheimageplaneisalmostentirelylinear.Translationsandrotationsassociatedwithinternalmodelparametershaveeffectsthatareidenticaltotheviewpointparameters,butappliedtoonlyasubsetofthemodelpoints.Allofthesetransformationsaresmoothandwellbehaved.Therefore,thisproblemisapromisingcandidatefortheapplicationofNewton’smethod,whichisbasedonassumingthatthefunctionislocallylinear.Whilethisdoesrequirestartingwithanappropriateinitialchoicefortheunknownparametersandfacestheriskofconvergingtoafalselocalminimum,wewillseebelowthatstabilizationmethodscanbeusedtomakethismethodhighlyeffectiveinpractice.

7

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

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

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

thatthederivativescanbecomputedinanextremelyef cientform.Forexample,thedirec-tionalderivativeofapointwithrespecttoanincrementalrotationaboutthe-axisisthevector

,whereandrefertothecoordinatesofthevectorfromtheoriginofrotationtothepoint.

Oncethedirectionalderivativesofeachmodelpointhavebeencomputed,itissimplya

.Perspectiveprojectionofamodelpointmatterofprojectingtheseintoimagecoordinates

incamera-centeredcoordinatestoproduceanimagepointisgivenasfollows:

and

whereisaconstantproportionaltothefocallengthofthecameralens.Weincludeanotherconstant,,specifyingthewidth-to-heightaspectratioofeachpixelintheoriginalimage,asmostcurrentvideostandardshavenon-squareaspectratios.Takingthepartialderivativeofeachoftheabovefunctionswithrespecttoaparameter,weget

and

Herethepartialderivativesof,andwithrespectto

directionalderivativescalculatedearlier.aresimplythecomponentsofthe

4.3Measuringperpendicularerrorsforcurves

Themethodsabovewouldbesuf cientifwehadmatchesbetweenpointsonthemodelandpointsintheimage.However,inmostcasesthematcheswillactuallybebetweenprojectedcontoursofthemodelandpartialedgesintheimage.Sincetheprecisepositionoftheend-pointsofimageedgesareunknown(andmaybedisplacedduetoocclusion),itisnecessarytominimizeonlytheperpendiculardistancefrompointsonanimageedgetotheprojectedmodelcurve.

Itmightbethoughtthatself-occludingedgesofcurvedsurfaceswouldrequirespecialtreat-ment,astheactualmodeledgethatformssuchanoccludingcontourwillshiftwithchangesinviewpoint.However,thesurfacenormalatsuchanoccludingpointisexactlyperpendiculartotheviewingdirection,andthereforetheinstantaneousmotionofthecontourprojectedintotheimageiszeroasnearbypointsonthesurfacereplaceit.Forlargerrotations,theerrorintro-ducedbynon-linearityiseasilyhandledthroughthesameiterationsthatcompensateforothernon-linearities.

Inordertomeasuretheperpendiculardistancefromanimagepointtoaprojected2-Dmodelline,itisusefultoexpresstheprojectedmodellineinthefollowingform:

10

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

whereistheorientationofthelinewithrespecttothe-axisandisthesignedperpendicular

intotheleftsideofdistanceofthelinefromtheorigin.Ifwesubstituteanimagepoint

thisequationandcalculateanew,thenthesignedperpendiculardistanceofthispointfrom

.Thepartialderivativeofthisperpendicularerrormeasureisjustalinearthelineis

combinationofthepartialderivativesofand:

Inpractice,wecalculateandfrom2points,

bethelengthofthelinebetweenthesepoints:and,ontheline.Let

then

and

Theperpendicularerrorismeasuredbetweenselectedpointsontheimagecurveandtheperpendicularprojectionofthispointontotheclosestsegmentoftheprojectedmodelcurve.Thisdeterminationoftheclosestmatchingpointisupdatedoneachiterationofconvergence.

4.4Determiningastartingpositionforconvergence

Worrall,Baker&Sullivan[34]havestudiedtherangeofconvergencefortheauthor’searlierversionofthisalgorithmusingMonteCarlotechniques.Theyfoundthatthealgorithmwouldconvergetothecorrectsolutioninvirtuallyeverycaseforrotationerrorsoflessthan90degrees(translationerrorshavealmostnoeffect).Thenumberofiterationsriseswithincreasingerrorsuptoanaverageofabout6iterationsat90degrees.Withthestabilizationmethodsdescribedinthenextsection,convergenceissigni cantlyimprovedovereventheselevels.

Therefore,theaccuracyrequirementsfordeterminingtheinitialstartingpositionarequiteminimal.Forthemotiontrackingproblemwhichservesasourinitialfocus,wesimplyusetheparameterestimatesfromthepreviousframeaddedtoavelocityestimateforeachparameterobtainedfromtheprevious2frames.Forageneralrecognitionproblem,propertiesoftheimagematchesthatarebeing ttedcanbeusedtodetermineinitialparameterestimates.Forrotationindepth,eachmatchcanvoteforameandirectionfromwhichitisvisible(veryfewmodelfeaturesarevisiblefromallviewpoints)andthesedirectionvectorscanbeaveraged.Forrotationintheimageplane,wecanprojectthemodelfromtheestimatedrotationindepthandtaketheaverageimagerotationbetweenprojectedmodeledgesandthematchingimageedges.Estimatesfortranslationcanbemadebymatchingthecentersofgravityandstandarddeviationsfromthecentersofgravityfortheprojectedmodelfeaturesandimagefeatures.See

[21]foranexampleofcalculatinginitialestimatesforarecognitionproblem.

Ifthereareonlyaboutasmanymatchesasareneededtosolveforthedegreesoffreedom,thenitispossiblethatthereismorethanonelocalminimum.Thisproblemcanbeovercome

11

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

bystartingwithsomeextramatches(thesolutionadoptedintheauthor’sapplications),byattemptingtoconvergefromseveralstartingpositions,orbyusingananalyticmethodappliedtosubsetsofthematches(asinDhomeetal.[4])tocomputeacandidatesetofstartingpositions.Yetanotherapproachistoconstructaninverselookuptablethatmapsfeaturemeasurementsintoapproximateviewpointparameterestimates.SuchanapproachhasbeenusedbyThompsonandMundy[32]forverticesandbyGoad[7]forawiderangeofarbitrarymodelfeatures.5Stabilizingthesolution

Aslongastherearesigni cantlymoreconstraintsonthesolutionthanunknowns,Newton’smethodasdescribedabovewillusuallyconvergeinastablemannerfromawiderangeofstart-ingpositions.However,inbothrecognitionandmotiontrackingproblems,itisoftendesirabletobeginwithonlyafewofthemostreliablematchesavailableandtousethesetonarrowtherangeofviewpointsforlatermatches.Evenwhentherearemorematchesthanfreeparameters,itisoftenthecasethatsomeofthematchesareparallelorhaveotherrelationshipswhichleadtoanill-conditionedsolution.Theseproblemsarefurtherexacerbatedbyhavingmodelswithmanyinternalparameters.

5.1Specifyingapriormodel

Alloftheseproblemscanbesolvedbyintroducingpriorconstraintsonthedesiredsolutionthatspecifythedefaulttobeusedintheabsenceoffurtherdata.Inmanysituations,thedefaultso-lutionwillsimplybetosolveforzerocorrectionstothecurrentparameterestimates.However,forcertainmotiontrackingproblems,itispossibletopredictspeci c nalparameterestimatesbyextrapolatingfromvelocityandaccelerationmeasurements,whichinturnimplynon-zeropreferencesforparametervaluesinlateriterationsofnon-linearconvergence.

Anyofthesepriorconstraintsonthesolutioncanbeincorporatedbysimplyaddingrowstothelinearsystemstatingthevaluethatwewishtoassigneachparameter:

Theidentitymatrixaddsonerowforspecifyingthevalueofeachparameter,andspeci esthedesireddefaultvalueforparameter.

Theobviousproblemhereisthatthereisnospeci cationofthetrade-offsbetweenmeetingtheconstraintsfromthedataversusthoseofthepriormodel.Theappropriatesolutionistoweighteachrowofthematrixequationsothateachelementoftheright-handsidehasthesamestandarddeviation.Therefore,asweminimizetheerrorvector,eachconstraintwillcontributeinproportiontothenumberofstandarddeviationsfromitsexpectedvalue.

Wewillnormalizeeachrowofthesystemtounitstandarddeviation.Iftheimagemea-surementsareinpixels,thenleavingthesewithastandarddeviationof1isalreadyagood rstestimatefortheerrorinmeasuringthepositionofimagefeatures.Inourmatchingalgorithm,

12

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

wealsotakeaccountofpotentialambiguitiesinthematchtoincreasethestandarddeviation(i.e.,reducetheweighting)formatchesthatexhibitmorethanonenearbyalternative,sothatuncertaintiesinthecorrectmatchfornearbyalternativestranslateintotheappropriateuncer-taintiesinposition.

Themoreimportantnormalizationistoweightthepriormodelaccordingtothestandardde-viationsinthepriorestimatesforeachparameter.Thisisrelativelystraightforwardinthecaseofmotiontracking,wherelimitsontheaccelerationofeachparameterfromframetoframecanbeexpressedasastandarddeviation.However,inthecaseofmodel-basedrecognitionfromanyviewpoint,itmayseemthattherangeofexpectedvaluesisin nite.Infact,eachparameterislimitedduringconvergencebecauseweareassumedtobestartingfromsomeinitialapprox-imationtotheviewpoint.Therefore,therotationparameterswillhaveastandarddeviationof

,andthetranslationswillbelimitedtomaintainingthepositionoftheobjectwithinatmost

theimageframe.Internalmodelparameterswillhavestandarddeviationscorrespondingtoalargefractionoftheirvalidrangeofmovement.Thesedeviationsmaybelargeincomparisontothosearisingfromtheimagemeasurements,buttheystillplayasubstantialroleinstabilizingthesolutionforill-conditionedproblems.Infactthestandarddeviationscanbemadeseveraltimessmallerwithoutanadverseeffectonthedegreetowhichthe nalsolution tsthedatameasurements,becausethenon-lineariterativesolutioncanresetthestartingpointofthepriormodeltotheresultsofeachpreviousiteration.

5.2Ef cientcomputationofstabilization

Thepriorestimatesoftheparametervalueswillbeweightedbyadiagonalmatrix

eachweightisinverselyproportionaltothestandarddeviation,,forparameter:inwhich

Thismatrixisusedtoscaleeachrowofthepriormodelinthelowerpartofequation(2).Weassumethattheconstraintsbasedonimagemeasurementsintheupperpartoftheequationarealreadyscaledtohaveunitstandarddeviation.

Wewillminimizethissystembysolvingthecorrespondingnormalequations:

Whichmultipliesoutto

13

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

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

Figure3:Twoiterationsofconvergenceareshownfordetermining3-Dviewpointandtheheightofthepyramidfrompartialmatchesto2-Dimagesegments.Perpendicularerrorsbeingminimizedaredisplayedasgraybarsbetweenmodelandimageedges.

thereforesolve rstforthosewithhigherstandarddeviations.Forourproblem,thisimpliesthatconvergencefordif cultproblemswillproceedbysolving rstfortranslationsandthenproceedingonsubsequentiterationstosolveforrotationsand nallyshort-rangeinternalmodelparameters.

6Resultsofimplementation

Allofthemethodsforobjectmodelingandparametersolvingdescribedabovehavebeenim-plementedinabout4000linesofCcode.Averysimpleexampleofmodel ttingisshowninFigure3.Themodelisapyramidwithaninternalparameterallowingforvariableheight.Themodelwasprojectedfromoneparticularsetofparametervalues,andrandomintervalsofsome

15

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

Figure4:Animagefromamotionsequenceofapersonusingahanddrill.

oftheprojectedsegmentswerechosenformatching.ThemodelparameterswerechangedtoproducethestartingparameterestimatesshowninFigure3(b).Inthis gure,theperpendicularerrorsbeingminimizedaredisplayedasgraybarsbetweentheprojectedmodelsegmentsandthematchingimagesegments.Figures3(c)and3(d)showtheoutputfollowingthe rsttwoiter-ationsofthestabilizedalgorithmpresentedabove.Thisfastrateofconvergencewithinacoupleofiterationsistypicaloverawiderangeofinitialparametervalues(uptoatleast60degreeer-rorsinrotationparameters).SeeWorrall,Baker&Sullivan[34]forasystematicexplorationofconvergenceoverawiderangeoferrors,evenpriortotheadditionofthestabilizationandLevenberg-Marquardtmethods.Infact,divergenceisrelativelyrare,soitisuncommonfortheLevenberg-Marquardtmethodtotakeeffect;however,itscomputationalcostisalsolow,soitisprobablyofpracticalvalue.

6.1Applicationtomotiontracking

Oneinitialapplicationofthesemethodshasbeentotheproblemofmodel-basedmotiontrack-ing.ADatacubeimageprocessorwasusedtoimplementMarr-Hildreth[25]edgedetectioninrealtimeon512by485pixelimages.Theimagecontainingtheseedgepointsistransferredto

16

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

Figure5:EdgesextractedfromtheimageofFigure4usingtheCannyedgedetector.Super-imposedontheseedgesarethemodelfromitspreviousestimatedviewpoint,nearbymatchingedges,andperpendicularerrorstobeminimized.

aSun3/260,wheretheedgesarelinkedintolistsonthebasisoflocalconnectivity.Afairlysimplematchingtechniqueisusedtoidentifytheimageedgesthatareclosesttothecurrentprojectedcontoursofa3-Dmodel.Thefewbestinitialmatchesareusedtoperformoneit-erationoftheviewpointsolution,thenfurthermatchesaregeneratedfromthenewviewpointestimate.Upto5iterationsofthisprocedureareperformed,withagraduallynarrowingrangeofimagelocationswhicharesearchedforpotentialmatches(thishelpstoeliminateanyfalseoutliermatches).Forsimplemodelswithstraightedges,allofthesestepscanbeperformedinlessthan1second,resultinginasystemthatcanperformrobustbutratherslowreal-timemo-tiontracking.Wehaverunthissystemforthousandsofframesatatimebyholdinganobjectinfrontofthevideocameraandslowlymovingit.Correctnessofthemotiontrackingcanbeeasilyjudgedinrealtimebywatchingawire-framemodelsuperimposedontheimagefromthecurrentsetofparameterestimates.Wearecurrentlyexploringtheuseofparallelarchitec-turesthatcouldgreatlyspeedtheoperationofthissystemsothatitperformsatvideoratesforcomplexobjectmodels.

17

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

Figure6:Thenewmodelpositionandhandlerotationafteroneiterationofmodel tting.Newmatchestoimageedgesareshownwithheavylines.

Figures4–7showtheoperationofthesystemforoneframeofmotiontracking.However,duetothecomplexityofthemodel,thisversionrequiresabout6secondsofprocessingperframeonaSun3/260anddoesnotoperateinrealtime.Figure4showsanimageofahanddrillfromwhichedgesareextractedwithasimpli edversionoftheCannyedgedetector.InFigure5,themodelisshownsuperimposedontheseedgesfromthepreviousbestestimateofitscurrentviewpoint.Asimplematchingalgorithmisusedthat ndsimageedgesthatareclosetotheprojectedmodelcurvesoverthemaximumpossiblelengthoftheedge.Thesematchesarerankedaccordingtotheirlengthandaverageseparation,andthebestonesarechosenforminimization.TheselectedmatchesareshownwithheavylinesinFigure5alongwithperpendicularbarsmarkingtheerrorsbetweenmodelandimagecurvesthatareminimized.Afteroneiterationofmodel tting,thenewmodelpositionisshowninFigure6alongwithanewsetofimagematchesgeneratedfromthisposition.Notethattherotationofthehandleisafreeparameteralongwiththeviewpointparameters.Afterthisseconditerationofconvergence,the nalresultsofmodel ttingareshownsuperimposedontheoriginalimageinFigure7.Notethatduetoocclusionanderrorsinlow-leveledgedetection,this nalresultisbasedon

18

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

Figure7:Aftertheseconditerationofconvergence,themodelisshownsuperimposedontheoriginalimage.

onlyasmallsubsetofthepredictedimageedges.However,duetotheoverconstrainednatureoftheproblem,inwhichfarmoremeasurementsareavailablethanunknownparameters,the nalresultcanbereliableandaccurate.

7Conclusionsandfuturedirections

Thispaperhaspresentedgeneralmethodsfor ttingmodelswitharbitrarycurvedsurfacesandanynumberofinternalparameterstomatchedimagefeatures.Considerableattentionhasbeengiventoissuesofrobustnessandef ciency,andthesetechniquesshouldserveasapracticalbasisformodel ttinginmostapplicationsofmodel-basedvision.

Thereareanumberofdirectionsinwhichthesemethodscouldbefurtherimproved.Oneisindealingwithobjectsthathaveverylargenumbersofvariableparameters.Sincethecomplex-

inthenumberofvariables,itwouldlikelybemoreityofsolvingalinearsystemrisesas

ef cienttopartitionproblemswithverylargenumbersofparametersintosmallersubsets.Thesimultaneoussolutionmethodwouldbeusedforallparameterswithlargerangesofuncertainty,buttheremainingoneswouldbesolvedforonthebasisoflocalindependentoptimization.Thiswouldbecomeparticularlyimportantifgenericclassesofobjectsaremodeled,aswasdonein

19

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

theAcronymsystem[3],inwhichalmosteverydimensionoftheobjectisvariable.

Whilethispaperextendsthemodelingandparametersolvingcomponentsofavisionsys-temsothattheycanworkwithcurvedobjects,thereisstillmuchresearchtobedoneregardinglow-levelcurvesegmentationandgrouping.Theauthorhasdevelopedsomemulti-scalecurvesmoothingmethods[23]thatwouldbesuitablefortheinitialcurvedescription,butmuchre-mainstobedoneatthelevelofgroupingandindexinginordertoproduceafullygeneralsystemforrecognitionofcurvedobjects.Bymakinguseofpropertiessuchascurvature,smoothnessandhigher-levelgroupings,itshouldbepossibletomakemajorgainsinthereliabilityofmatch-ing.

References

[1]Binford,ThomasO.,“Visualperceptionbycomputer,”IEEESystemsScienceandCybernetics

Conference,Miami(1971).

[2]Bray,AlistairJ.,“Trackingobjectsusingimagedisparities,”ImageandVisionComputing,8,1

(1990),4–9.

[3]Brooks,RodneyA.,“Symbolicreasoningamong3-Dmodelsand2-Dimages,”Arti cialIntelli-

gence,17(1981),285-348.

[4]Dhome,M.,M.Richetin,prest´e,andG.Rives,“Determinationoftheattitudeof3-Dobjects

fromasingleperspectiveview,”IEEEPAMI,11,12(1989),1265–78.

[5]Faugeras,O.D.,andM.Hebert,“Therepresentation,recognitionandlocatingof3-Dobjects,”The

InternationalJournalofRoboticsResearch,5,3(1986),27–52.

[6]Fischler,MartinA.andRobertC.Bolles,“Randomsampleconsensus:Aparadigmformodel

ttingwithapplicationstoimageanalysisandautomatedcartography,”CommunicationsoftheACM,24,6(1981),381-395.

[7]Goad,Chris,“Specialpurposeautomaticprogrammingfor3Dmodel-basedvision,”inFromPixels

toPredicates,ed.AlexPentland,(AblexPublishingCo.,1986),371-391.

[8]Goldberg,RobertR.,andDavidG.Lowe,“Veri cationof3-Dparametricmodelsin2-Dimage

data,”Proc.ofIEEEWorkshoponComputerVision,Miami(November1987),pp.255-257.

[9]Golub,GeneH.,andCharlesF.VanLoan,MatrixComputations,2ndEdition,TheJohnsHopkins

UniversityPress,Baltimore(1989).

[10]Grimson,Eric,andThom´asLozano-P´erez,“Model-basedrecognitionandlocalizationfromsparse

rangeortactiledata,”Int.JournalofRoboticsResearch,3(1984),3-35.

[11]Haralick,R.M.,H.Joo,C.Lee,X.Zhuang,V.G.Vaidya,andM.B.Kim,“Poseestimationfrom

correspondingpointdata,”IEEETrans.onSystems,ManandCybernetics,19,6(1989),1426–1446.

20

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

[12]Horaud,R.,B.Conio,O.Leboulleux,colle,“Ananalyticsolutionfortheperspective

4-pointproblem,”puterVisionandPatternRecognition,SanDiego(June1989),500–507.

[13]Huttenlocher,DanielP.,andShimonUllman,“Objectrecognitionusingalignment,”Proc.First

Int.Conf.onComputerVision,London,England(June1987),102–111.

[14]Ishii,M.,S.Sakane,M.KakikuraandY.Mikami,“A3-Dsensorsystemforteachingrobotpaths

andenvironments,”TheInternationalJournalofRoboticsResearch,6,2(1987),pp.45–59.

[15]Kumar,Rakesh,“Determinationofcameralocationandorientation,”Proc.DARPAImageUnder-

standingWorkshop,PaloAlto,Calif.(1989),870–879.

[16]Lawson,CharlesL.,andRichardJ.Hanson,SolvingLeastSquaresProblems,Prentice-Hall,En-

glewoodCliffs,NJ(1974).

[17]Levenberg,K.,“Amethodforthesolutionofcertainnon-linearproblemsinleastsquares,”Quart.

Appl.Math.,2(1944),164–168.

[18]Liu,Y.,T.S.HuangandO.D.Faugeras,“Determinationofcameralocationfrom2-Dto3-Dline

andpointcorrespondences,”IEEEPAMI,12,1(1990),28–37.

[19]Lowe,DavidG.,“Solvingfortheparametersofobjectmodelsfromimagedescriptions,”Proc.

ARPAImageUnderstandingWorkshop(CollegePark,MD,April1980),121–127.

[20]Lowe,DavidG.,PerceptualOrganizationandVisualRecognition(Boston,Mass:KluwerAca-

demicPublishers,1985).

[21]Lowe,DavidG.,“Three-dimensionalobjectrecognitionfromsingletwo-dimensionalimages,”

Arti cialIntelligence,31,3(March1987),355-395.

[22]Lowe,DavidG.,“Theviewpointconsistencyconstraint,”InternationalJournalofComputerVi-

sion,1,1(1987),57-72.

[23]Lowe,DavidG.,“Organizationofsmoothimagecurvesatmultiplescales,”InternationalJournal

ofComputerVision3,2(June1989),119–130.

[24]Marquardt,DonaldW.,“Analgorithmforleast-squaresestimationofnonlinearparameters,”Jour-

nal.Soc.Indust.AppliedMath.,11,2(1963),431–441.

[25]Marr,David,andEllenHildreth,“Theoryofedgedetection,”Proc.RoyalSocietyofLondon,B,

207(1980),187-217.

[26]McIvor,AlanM.,“AnanalysisofLowe’smodel-basedvisionsystem,”Proc.FourthAlveyVision

Conference,Univ.ofManchester(August1988),73–78.

[27]Pentland,AlexP.,“Perceptualorganizationandtherepresentationofnaturalform,”Arti cialIn-

telligence,28,3(1986),293-331.

21

本文来源：https://www.bwwdw.com/article/4hem.html