Localization using a Region-Based k-Nearest Neighb

LocalizationusingaRegion-Basedk-NearestNeighbourSearchBrianMcKinnonApril13,2004AbstractThispaperexploresamethodofperforminglocalizationonlocalvisionmobilerobots.Itdescribesamethodofprocessingimages,extractingregions,andcomparingthoseregionsagainstadatabaseofpreprocessedimages.Localizationisachievedusingthek-nearestneighbouralgorithmasthebasisforapproximatingthecurrentposition.Initialresultsareprovidedthatshowthepotentialofthismethod.1IntroductionTheabilitytomaintainanaccurateestimateofaroboticagent’spositionandorientationiscrucialinanyreal-worldapplication.Theprocessoflocalizingisanessentialcomponentofbothmappingandpathplanning.Thesethreecomponentsprovideagatewaybetweenthehigh-levelbehaviours,andthelow-levelmotorcontrols.Currently,thereisagrowingmarketforrobotsthatcanoperateautonomouslyinindustrial,office,andconsumerenvironments.Eachpossessesuniquechallenges,anddemandstheabilitytooperatewithoutfailure.Roboticsocceriscurrentlyanimportantarenafordevelopingandtestinglocalizationsystems.Itrequiresgoalorientedpathplanning,inawelldefinedenvironment.Figure1showsthestandardmarkersassociatedwithasoccerfieldincludeboundaryandcentrelines,goalandpenaltykickboxes,andalargecen-trecircle.Thedimensionsofthefieldarewelldefinedforeachleaguesinthecompetition.Thesecurrentlyincludethesmall-size,medium-size,and4-leggedrobotleagues.Theproblemoflocalizationisamplifiedinthisenvironmentbythepresenceofothersoccerplayers,thatproduceunpredictableocclusionofonboardsensors.Currently,theselocalizationsystemsrelyonartificialland-marksthatareplacedaroundthefieldatknownlocations.Thismeansthatlocalizationcanbesolvedthroughtriangulationoffieldmarkers.However,theselandmarksareslowlybeingremovedtoenforcethegoalofoperatingwithinanaturalenvironment.Inanygivenenvironment,thereisawealthofnaturalfeaturesthatcanbeusedtodetermineone’spositionandorientation.Allsolutionstolocalizationrequiretheabilitytointerpretandrepresentsensoryinformationinawaythat1Figure1:Thestandardfieldlayoutinasoccergame.Imageisfromfindabalancebetweencompactnessandcompleteness.Completnesstoallowdistinctionofindependentlocationinanenvironment,compactnesssinceitisunreasonabletostorealltherawsensordata.Vision-basedlocalizationisanintuitivemethodtoconsider,sinceweashumansrelyonvisiondatatodetermineourpositions.Visionprovidesfarmoredetailedinformationthancanbeacheivedthroughdistancesensors(sonar,laser)alone.Infigure2,itiseasytodeterminethatyouareinakitchen,sincetherearesomanydistictfeatures.Thepresenceofthesefeaturesmakesvisualdataaverygoodcandidateforperforminglocalization.Thereisapricehowever,sinceprocessingimagesiscomputationallyexpensivewhencomparedwithdistancesensors.Inthispaper,theproblemofvision-basedlocalizationwillbebrokenintotwoseparateprocesses.Thefirstisrelatedtoimageprocessing,withthegoalofperformingextractionandrepresentationofregionswithinacapturedimage.Thiswillincludeastudyofthemethodscurrentlybeingresearched,aswellasadescriptionoftheproposedsystem.Thesecondprocessinvolveslocalizingtheagentbasedonasetofpreprocessedimagesofknownlocationsandorien-tations.Avarietyoflocalizationsystemswillbeexamined,includingsimilarvisionbased,andmoretraditionaldistancesensorbasedsystems.2RelatedWorkBothregionextractionandlocalizationareactiveareasofresearch.Thereareawidevarietyofsolutionscurrentlybeinginvestigated,manyoftheseyieldingpromisingresultsfortheimprovementofanagent’sperformance.2Figure2:Thispicturedemonstratestheamountofinformationavailablefromvisualdata.2.1RegionExtractionandMatchingThetwomostimportantstepsinregionextractionareidentificationandrep-resentationoffeaturesintheimage.Researchisstillactiveinthisarea,sincecurrentsystemsencounterenvironmentsthatcausefailureratestobecomeun-manageable.Examplesofsystemscurrentlybeingstudiedinclude[7][4]and[5].2.1.1ScaleInvariantFeatureExtractionIn[7]anobjectrecognitionsystemisintroducedthathasbecomeknownasScaleInvariantFeatureExtraction(SIFT).Itusesafeaturerepresentationthatisinvarianttoscaling,translation,rotation,andpartiallyinvarianttochangesinillumination.Theoutputofthissystemisasetcontainingtheorientation,position,relativelocation,andcolourgradientofkeyfeatureswithinanimage.ScaleinvarianceisachievedthroughtheuseoftheGaussiankernelasdescribedin[6].Forrotationalinvarianceandefficiency,keylocationsareselectedatthemaximaandminimafromthedifferenceoftheGaussianfunctionappliedinscalespace.Athresholdisappliedtothegradientmagnitudeforrobustness.Thisisusefulsinceilluminationchangesmaygreatlyaffectthegradientmagni-tude,howeveritshouldhavelittleimpactonthedirection.Onceasetofkeysaredefinedforagivenobject,liveimagesarescannedandobjectsareselectedusingabest-bin-firstsearchmethod.Binscontainingatleastthreeentriesforanobjectarematchedtoknownobjectsusingaleastsquareregression.Ex-perimentalresultsshowthatthesystemiseffectiveatdetectingknownobjects,eveninthepresenceofocclusion,sinceonlythreekeysarenecessaryforamatchtooccur.Thiscanbeseeninfigure3.Usingthismethod,alocalizationsystemhasbeenimple