Economy & Finance

Two-dimensional landmark-based position estimation from a single image

Description
This paper addresses the problem of self-location for a mobile robot equipped with a single camera moving in an indoor environment. The robot is provided with a two-dimensional map where the position and some attributes of landmark points are stored.
Published
of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
  Proceedingsot’tbe1998IEEEInternationalConference onRobotics&AmonlationLeuven,Belgimn.Moy199S Two-DimensionalLandmark-basedPositionEstimationfromaSingleImage’ Antonio J.MuilozandJavierGonzalezDepartarnentodeIngenieriadeSistemasyAutomatic,UniversidaddeMalagaCampusTeatinos,29080Malaga,SPAIN.E-mail:ajmunoz@ctima.uma.esE-mail:jgonzalez@ctima.uma.es Abstract Thispaperaddressestheproblemofself-locationfor a mobilerobotequippedwithasinglecameramovinginanindoorenvironment.Therobotisprovidedwitha two- dimensionalmapwherethepositionandsomeattributesoflandmarkpointsarestored.Theproposedalgorithmfirstdeterminestheobservationraysofverticaledgesextractedfiomoneimageandthenfindsaninterpretationfortheserqsinterms of thelandmarkpoints.Thisinter-pretationisdrivenbyaset-basedapproachthatcompelstheactualposetolieinasolutionregionandnottovio-latethelandmarkattributes.Basedontheray-landmarkmatchesprovidedbytheselectedinterpretation,anopti-mizationprocedureisusedtocomeupwiththeposeforwhichthemeansquareangularerrorisminimum,Finally,wepresentexperimentalresultsthatdemonstratetheper-formanceofthesystem. 1.Introduction Theproblemofself-locationforamobilerobothasbeenstudiedbymanyresearchersandavarietyoftechniqueshavebeenproposedforsolvingit.Thesetechniquesvarysignificantlydependingonthetypeofenvironmentinwhichthemobilerobothastonavigate,onthepriorknowl-edgeoftheenvironment,onthetasktorealizeand,ofcourse,onthetypeofsensorusedbytherobot[1].AttheUniversityofMalagaweareinvestigatingtheproblemofestimatingthepose(positionandorientation)foramobilerobotequippedwithasinglecameramovinginanindoorenvironment.Weassumethattherobothasatwo-dimensionalmapwherethepositionsandsomeat-tributesofverticallandmarks(verticallyorientedpartsoffixedobjectssuchasdoors,walljunctions,windows,etc.)arestored.Theproblemcanbedividedintothreesteps:1)1.ThisworkhasbeensupportedbytheSpanishGovernmentundertheCICYTprojectTAP96-0763.detectfeaturesintheimagethatcorrespondtoverticallandmarksoftheenvironment,2)findthebestinterpreta-tionofthedirections(rays)tothesefeaturesthatisconsis-tentwiththelandmarkattributes,and3)computeaposefromthosematches.Inthispaperwedealwiththetwolat-tertmoblems. . I 7 /: rl . .—— —— Figure1.-Thelandmark-basedposeestimationproblem.Webelievethatverticallandmarksareattractivebe-causetheyappearveryfrequentlyinatypicalindoorenvi-ronmentandtheycanbeeasilyandreliablyextractedfromtheimage.Providedthatthecameraismountedparalleltothefloor,verticallandmarksoftheenvironmentwillprojectasverticalfeaturesontotheimageplaneand,there-fore,thecorrespondenceproblemcanbeformulatedinthetwo-dimensionalplane(asshowninfigure1).SimilarapproacheshavebeenproposedbySugihara[2]andKrotkov[3].However,theydonotdealwiththeeffectsofobserving falsepositive (detectingfeaturesthatdonotcorrespondtoaknownlandmark).AnotherrelatedworkistheonereportedbySutherlandandThompson[4]forun-structuredenvironments,wherethelandmarksaremoun-tainpeaksofatopographicmap.Theyanalyzehow0-7803-4300-x-5/98 10.00@  99 IEEE3709  measurementerrorsaffecterrorsinthelocalizationandproposeasimplealgorithmtoexploitthegeometricprop-ertiesoflandmarkin the environmentinorder todecreaseerrorsinthelocalization.Theresultspresentedbyallofthemarelimitedtosimulateddata.Unliketheabovereferredworks,thealgorithmwepresenthereincludessomeattributesforthelandmarksinordertoeftlcientlysearchthetreeandimprovetherobust-nessofthealgorithm,rulingoutthepossibilityoferrone-ousmatching.Also,aroughestimateoftherobotlocationprovidedbythedead-reckoningsystemisconsideredtosimpli~thesearchbypredictingwhichlandmarkscouldmatchwitheachray.falsepositive   image \ ray rj j f(focallength)Figure2.-Extractingraysfromverticaledgesofanimagebyusingthepin-holecameramodel. zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA 2. ProblemStatement Let(x,y,et)bethetripletthatdefinesthelocalrobotcoor-dinatesystem{u,v}withrespecttotheworldcoordinatesystemW(seefigure1a).Let M={ml,....mk} bethesetoflandmarkpointsstoredinthemapandexpressedintheworldcoordinatesystem W. Let R={rl,....rn} bethesetofraysextractedfromanimagetakenattherobotpose(x,y, a . Intuitively,arayrishouldcorrespondtoalandmarkmj,denotedbythepair  ri,mj), ifriistherayobtainedfortheverticaledgewhichistheprojectionofmjontotheimage.Sincetheraysarenotdistinguishablefromeachother,wecannotestablishsuchaone-to-onecorrespondencebe-tweenraysandlandmarks.Insteadtheproblemhastobeformulatedgloballybylookingforan admissibleinterpre-tation of thewholesetofrays R. Intheidealcasewhenraysandlandmarkpointsfromthemapareerror-flee,aninterpretationissaidtobeadmis-sibleifthereexistaposefromwhereeachrayof R piercesthelandmarkpointspecifiedbytheinterpretation.Noticethatinthiscasebothproblemscorrespondenceandposees-timationaresolvedsimultaneouslyasanelementarygeo-metricproblem(see[2]formoredetail).Inpractice,sinceerrorsareinevitablypresentintherays1(weassumethatthelandmarksareerror-fi-ee),theabovecriterionisnolongervalidandthereforeitisnecessarytointroducesomeuncertaintymodel.Inaddition,aninterpretationshouldac-countforraysthathaveno-correspondencetoanyknownlandmark(falsepositive)aswellasfortheopposite,thatis,landmarksofthemapthathavenotbeendetectedintheim-age.Obviously,inthesecases,thecorrespondenceproblemresultinamoredifficulttaskthatsuffersfromtheambigui-typroblemandrequiresareliablemodelingoftheerrorsinvolved.Inparticular,ourapproachconsidersthattheer-rorsintheobservationarewithinatolerance.Thisleadstoaset-basedalgorithmthatcombinesinformationviainter-sectionofdifferentuncertaintyregions.OfthiskindisalsotheworkreportedbyAtiyaandHagerforlocalizingamo-bilerobot[5].Accordingtotheset-basedapproachiftworegionsAandBareknowntocontaintheactualposeoftherobot,thenAnBmustalsocontainthatpose.Consequently,eachnewregionthatweincorporatetotheproblemactuatesasanadditionalconstraintthatprovidesatighterboundoftheunknownpose.Thefirstconstraintregioncomesfromtheuncertaintyinthedead-reckoningposePo=(xo,yo,so).Wemodelthisun-certaintyasacircleCoofradio a, centeredat(x.ye).Sim-ilarly,amaximumangularerrorof+acrrorisconsideredfortheorientation ao. Thisuncertaintyregionisconsideredtobeproportionaltothedistancetraversedbytherobot.Additionalconstraintregionscomefromthefactthattheviewpointfromwheretwolandmarksareobservedwithagivenanglemustlieonacircumference[2,3].Sincetheerrorintheraysiswithinatolerance,theviewpointisre-strictedtolieonathickenedringasshowninfigure3a.Next,wedescribethisinmoredetail.1.Mostly,theseerrorsarecausedbytheimperfectlocalizationoftheverticaledgesintheimageaswellaserrorsintroducedbythecameramodelbeingused. 3710  -----... ‘j (a)“ lllj Illi ntk ~ ‘Jk IJ (b)Figure3.-(a)Theerrorbetweentworayscon~raintstheviewpokttoathickenedring.(b)Atypicaluncertaintyregionwhenthreepairsray-landmarkareestablished.Let812= 1- 2betheanglebetweentheraysr]andr2,wherer)1and 2aretheorientationmeasuredfortherayr]and r2, respectively(seefigure 2). Assumingboundeder-rorsfor~1and1 2,therealvalueofe12iswithintheuncer-taintyinterval[f312-,e12+1,where‘kSPqistheuncertainty-1rayshavebeenmatched,andringdefinedby(ehk+,ehk-,nZPmq),witi(r P)beingwhatevercorrespondencepairpreviouslyestablished.Fig-ure3billustratesthiscasefork=3andh=2. zyxwvutsrqponmlkjih 3. ConstructingtheInterpretationTree Takingintoaccounttheabovementionedregion-basedap-proach,theproposedalgorithmconstructsatreewithallthepossibleadmissibleinterpretations,namedthe interpre-tationtree. FollowingtheterminologyusedbyGrimson[6],theinterpretationtreeisagraphwherealevel“i”rep-resentsallpossiblelandmarksthatcouldbematchedwiththerayriaccordingtotheconstraintregionderivedfromtheprevioushypothesizedmatches.Thus,acompletebranch,fromtheroottoaleaf,representsanadmissiblein-terpretationforalltheraysextractedfromtheimage.Inor-dertoaccountforraysthatdonotcorrespondtoanyknownlandmarkthealgorithmincludesanulllandmark(“@”).Toefficientlyconstructtheinterpretationtree,thealgo-rithmmakesuseofthreeadditionallyconstraints:landmarkordering,predictionofvisiblelandmarks,andattributecompatibility. Landmarkordering.Themapis assumedtobeasingleconnectedpolygonwherethelandmarksarethevertices.Thus,wecartcreateacircularlistsortedonthebasisoftherelativeconnectionbetweenthem.Thislandmarkorderingpermitstoprunesignificantlytheinterpretationtree,sincetheyalwayshavetoappearintheimageinagivenorder.Forexample,ifarayriispairedtoaIancharkm}thenri+l(thefollowingrayontherightofri)mustfinditscorre-spondencepairamongthelandmarksontherightof mj Obviously,thisassumptionlimitsthelandmarksstoredinthemaptothoseconnectedbyopaquesurfaces(i.e.walls). e12-e12- Ienor 412e=or ande12 e12 1~rror  2error Now,letussupposethattheray rl matchestheland-markmi,makingthecorrespondencepair(rl,mj).men,alandmarkmjbecomesacandidatetomatch r2 onlyiftheuncertaintyring12Sijdelimitedby two circlesCij+andCU-anddefinedbythe parameters e12 ,e12-, rni, rnj),iflter- sects theuncertaintyregionCo,thatis,if Con12Sij= R2 0(seefigure3a).Similarly,givenagenericray rbthe landmarkmqisconsideredtobeaconsistentcandidatetomatchrkonlyif ‘k-1n ‘kspq Predictionofvisiblelandmarks. Sinceonlyasmallpor-tionofthemap(ingeneral)isvisiblefromaparticularpo-sitionandorientationoftherobot,landmarkpredictiongreatlydecreasesthesizeoftheinterpretationtreebyre-ducingthenumberoflandmarksthatcanpossiblymatchtheextractedrays.Astheabsoluteorientationqiofagivenrayriisaffectedbybotherrorsinrobotposeanderrors intheorientation angle i,thecandidatelandmarkstomatchtoriarewithintheregionofthemapdelimitedbythelinesq+andq-,whicharedefinedbytheworst-caseanglesgivenby(figure4):?li+=a.+Uerror+‘ i+  ierror?li-n a.-aemor Oi-  ierror where~-1isthe constraintregionobtainedoncethefirst 3711  Figure4.-Regionwhereanycandidatelandmarktomatchtherayqhastolie. Attributecompatibility The motivationofusingat-tributesisnotthatofpermittingtheindividualmatchingofeachray,butdiscardinglandmarksthatareincompatiblewiththeattributesextractedforagivenray.Inparticular,weconsiderthefollowingtwoattributes:- Verticalposition ofthelandmarks.Theendpointsofverticaledgeassociatedtoarayshouldbewithintheprojectionofthelandmarkontotheimageplane.- Shading inbothsidesofthelandmarks(lefiandright).Threedifferentsituationsmayoccur:“dark-to-bright”,“bright-to-dark”and“undefined”.Thelatterindicatesthatthelandmarkmayappearintheimageindistinctlyeitherasapositivediscontinuity(dark-to-bright)orasnegative(bright-to-dark),dependingontheenviron-mentallightingconditionsandontheobservationangle.Ofthistypeare,forexample,thecomersofthewalls.Thisattributeiscomparedwiththesignofthesecondderivativeoftheverticaledgeassociatedtotheray,Besidesincreasingtheefficiencyintheconstructionofthetree,theattributecompatibilityprovidesrobustnesstothealgorithmbyweedingoutinconsistentpairings. 4.ComputingtheRobotPose Once theinterpretationtree hasbeenconstructed,allitsbranchesaretraversedinordertoselectthebestinterpreta-tion.Wesupposeitistheonewhichcontainsthelargestsetofpairs,letsay“n”.Fromthisinterpretation,therobotposep=(x,y,a)isestimatedbyminimizingtheerrorfunction:IIIiII(I,~, JeTe)= zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA iqx,y,   (1 e; k=] (1)whereek=sin(bk)istheangularerrorinvolvedinthepair@k=(rj,mi)whichisgivenby(seefigure5):(xi -x)cos a+ j)+ yi -y)sin(a+ j)siniZik=~(2) ./ ray rj/-/@/6“//// -f’ X,y \(Ctfli+7t/2)-—.-—.—-—a x F@re5.- Angularerror~kinvolvedinthepair  rj,n ). Sincethisoptimizationproblemisnon-linearweusetheGauss-Newtoniterativealgorithmtosolveit[7].Inthismethod,solving(1)isequivalenttofindasolutionofe+JA=O(3)whereeistheerrorvector,Aisthedifferencevectorbe-tweenthetransformationparametersonsuccessiveitera-tions(pt=pt-l+At.]),and Jis theJacobian: J= K ] obtainedthroughthepartialderivativesofequation(2).Inordertothealgorithmtoconverge,theinitialposep.mustlieintheuncertaintyregion,forexampleavertexoftheso-lutionregionG.Sinceequation(3)isoverdeterminedforn>3weusethepseudoinverseoftheJacobiantofindaleastsquarefitofA:AD – JTJ -lJT~ (4)Equation(4)issolvediterativelyforthedisplacementvectorAuntiltheabsolutevalueofitselementsislessthansometoleranceorthenumberofiterationsexceedsapresetvalue. 3712  Intheeventthattwoormoreinterpretationsreachthesamenumberofpairs,allofthemareconsideredascandi-dateandtheonethatprovidestheminimumofthecostfunctionisselected.~.........1’A’L.-............................... 381m........ ,1 ;; 2nl, Ii e tripodPOW I ‘J Figure6.-Mapofthehallwayusedintheexperimentswherethesixposesofthetripodaremarked.Thelowerpartofthefigureillustratesthecirclescorrespondingtothebestinterpretationoftheraysobtainedatpose5(seefigure2). 5.ExperimentalResultsandDiscussions Thealgorithmsdevelopedinthisresearchhavebeentestedinthescenarioshowninfigure7,whosemapcontaining64landmarkappearsinfigure6.ThevisionsystemconsistsofaCCD-camerawitha8mm.objectiveconnectedtoaframe-grabberwith768x576pixelsofresolution.Forpre-cisionpurposesandtofacilitatethesurvey,thecamerahasbeenmountedonacalibratedtripod,insteadofourmobilerobot.Sothatthetripodposeswereeasilysurveyedusingatapemeasureandastandardprotractor.Theodometricposeswerechosenasthesurveyedposesplusanarbitraryoffsetgreaterthan0.5m.inpositionand7deginorientation.Theradiusofthedead-reckoningun-certaintycirclewasconsideredtobe1m.,whiletheorien-tationerrorwas+10deg.Toaccountforerrorsinthelandmarks,theerrorsoftheextractedrayswasinflatedUIIto+0.34deg.(equivalentto+6pixelsoferror).(a)(b)Figure7.-(a)Imagetakenatlocation1showingtheverticaledgesextracted.Thereflectiveverticallinesonthefloorhavenotbeendetectedsinceasignificantlyhighthresholdhasbeenusedforthelineextractoralgorithm.(b)Theresultinguncertaintyregionandestimatedpose.Inordertodemonstratetheperformanceofthealgorithmwehavetesteditintwodifferentcases:followingapathalongthehallway(withmanymatchesandlongdistances)androtatingaboutafixedposition(withfewmatchesandshortdistances).Table1:Errorsinthe6estimatedposesalongthehallway.Inthefirstexperiment,thetripodwasmanuallyplacedatthesixposesmarkedinthemapoffigure6.Theerrorsintheestimatedposes,shownintable1,areextremelysmallforthefirstfourlocationssinceasignificantnumberofmatches,almostsymmetricallydistributedalongthehallway,areestablished.Also,thissymmetrygivesrisetouncertaintyregionsappreciablyalignedwiththecorridor 3713
Search
Similar documents
View more...
Tags
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x