Visual+simultaneous+localization+and+mapping-+a+survey

ArtifIntellRev(2015)43:55–81DOI10.1007/s10462-012-9365-8Visualsimultaneouslocalizationandmapping:asurveyJorgeFuentes-Pacheco·JoséRuiz-Ascencio·JuanManuelRendón-ManchaPublishedonline:13November2012©SpringerScience+BusinessMediaDordrecht2012AbstractVisualSLAM(simultaneouslocalizationandmapping)referstotheproblemofusingimages,astheonlysourceofexternalinformation,inordertoestablishthepositionofarobot,avehicle,oramovingcamerainanenvironment,andatthesametime,ys,theproblemofSLAMisconsideredsolvedwhenrangesensorssrSLAMfordynamic,complexandlargescaleenvironments,usingvisionasthesoleexternalsensor,putervisiontechniquesemployedinvisualSLAM,suchasdetection,descriptionandmatchingofsalientfeatures,imagerecognitionandretrieval,amongothers,ectiveofthisarticleistopro-videnewresearchersinthefieldsVisualSLAM·Salientfeatureselection·Imagematching·Dataassociation·Topologicalandmetricmaps1IntroductionTheproblemofautonomousnavigationofmobilerobotsisdividedintothreemainareas:localization,mappingandpathplanning(Cyrill2009).Localizationconsistsindes-Pacheco·-Ascencio(B)CentroNacionaldeInvestigaciónyDesarrolloTecnológico,Cuernavaca,Morelos,Méxicoe-mail:josera@s-Pachecoe-mail:jorge_fuentes@ón-ManchaUniversidadAutónomadelEstadodeMorelos,Cuernavaca,Morelos,Méxicoe-mail:rendon@123

lobservationsofthesurroundingsintoasingleconsistentmodelandpathplannilly,mappingandlocalizationwerestudiedindependently,ansthat,forbeingpreciselylocalizedinanenvironment,acorrectmapisnecessary,butinordertoconstructagoodmaptly,thisproblemisknownasSimultaneousLocalizationandMapping(SLAM).Whencamerasareemployedastheonlyexteroceptivesensor,msvision-basedSLAM(Seetal.2005;Lemaireetal.2007)orvSLAM(Solà2007)SLAMsystemscanbecomple-mentedwithinformationfromproprioceptivesensors,proachisknownasvisual-inertialSLAM(JonesandSoatto2011).However,whenvisionisusedastheonlysystemofperception(withoutmakinguseofinfor-mationextractedfromtherobotodometryorinertialsensors)itcanbecalledvision-onlySLAM(Pazetal.2008;Davisonetal.2007)orcamera-onlySLAM(MilfordandWyeth2008).ManyvisualSLAMsystemsfailwhenworkunderthefollowingconditions:inexternalenvironments,indynamicenvironments,inenvironmentswithtoomanyorveryfewsalientfeatures,inlargescaleenvironments,duringerraticmoveasuccessfulvisualSLAMsystemistheabilitytooperatecorrectlydespitethesediffiantapplicationsofSLAMareorientedtowardsautomaticcarpilotingonunre-hearsedoff-roadterrains(Thrunetal.2005a);rescuetasksforhigh-riskordifficult-naviga-tionenvironments(Thrun2003;Piniésetal.2006);planetary,aerial,terrestrialandoceanicexploration(Olsonetal.2007;Artiedaetal.2009;Stederetal.2008;Johnsonetal.2010);aug-mentedrealityapplicationswherevirtualobjectsareincludedinreal-worldscenes(Chekhlovetal.2007;KleinandMurray2007);visualsurveillancesystems(Meietal.2011);medicine(Auatetal.2010;Grasaetal.2011),articleadetailedstudyofvisualSLAMispresented,usly,DurrantandBaileypresentedatuto-rialdividedintotwopartsthatsummarizestheSLAMproblem(DurrantandBailey2006;BaileyandDurrant2006).Thelattertutorialdescribesworksthatarecenteredontheuseoflaserrange-findersensors,rly,ThrunandLeonard(2008)presentedanintroductiontotheSLAMproblem,analyzedthreeparadigmsofsolution(thefirstisbasedontheExtendedKalmanFilter,andtheothertwouseoptimizationtechniquesbasedongraphsandparticlefilters)heless,theabove-mentionedatherhand,KragicandVincze(2009)presentareviewofcomputervisionforroboticsinageneralcontext,consideriticleisstructuredinthefollowingway:.3,theuseofcamerasastheonlyextn4describesthetypeofsalientfeaturesthatcanbeextractedandthedescriptorsusedton6givesadetailedreviewofthedifferentmethodstosolvethen8ectionpresentsbibliographicreferences.123

Visualsimultaneouslocalizationandmapping572SimultaneouslocalizationandmappingDuringtheperiodof1985–1990,ChatilaandLaumond(1985)andSmithetal.(1990)melater,thisproblemreceivedthenameofSLAM(simultaneouslocalizationandmapping).ThereadermayrefertothetutorialofDurrantandBailey(2006),BaileyandDurrant(2006)publicationsofNewmanetal.(2002)andAndradeandSanfeliu(2002)itisalsoknownasCML(ConcurrentMappingandLocalization).SLAMorCMListheprocesswherebyanentity(robot,vehicleorevenacentralprocessingunitwithsensordevicescarriedbyaperson)hasthecapacityforbuildingaglobalmapofthevisitedenvironmentand,atthesametime,rtobuildamapfromtheenvironment,theentitymustpossesssensorsthatallowittopeensorsareclassifiheexteroceptivesensorsitispossibletofind:sonar(Tardósetal.2002;Ribasetal.2008),rangelasers(Nüchteretal.2007;Thrunetal.2006),cameras(Seetal.2005;Lemaireetal.2007;Davison2003;Bogdanetal.2009)andglobalpositioningsystems(GPS)(Thrunetal.2005a).tion,onlylocalviewsoftheenvironmentcanbeobtainedusingthefiensorsandsoheless,theyhavethefollowingproblems:notusefulinhighlyclutteredenvironmentsorforrecog-nizingobjects;bothareexpensive,heavyandconsistoflargepiecesofequipment,makingtheirusediffitherhand,aGPSsensordoesnotworkwellinnarrowstreets(urbancanyons),underwater,onotherplanets,oceptivesensorsallowtheentitytoobtainmeasurementslikevelocity,amplesare:encoders,llowobtaininganincrementalestimateoftheentity’smovementsbymeansofadead-reckoningnavigationmethod(alsoknownasdeduced-reckoning),butduetotheirinherentnoisetheyarenotsufficienttohaveanaccurateestimationoftheentity’spositionallthetime,eendemonstratedinsomeinvestigations(Castellanosetal.2001;Majumderetal.2005;Nützietal.2010),tomaintainanaccurateandrobustestimationoftherobotpositionitisnr,theadditionofsensorsincreasesthecost,weightandpowerrequirementsofasystem;therefore,itisimportanttoinvestigatehowanentitymaylocateitselfandcreateamapwithonlycameras.3CamerasastheonlyexteroceptivesensorsInthelast10years,publishedarticlesreflectacleartendencyforusingvisionastheonlyexternalsensorialperceptionsystemtosolvetheproblemofSLAM(Pazetal.2008;Davisonetal.2007;KleinandMurray2007;SáezandEscolano2006;PiniésandTardós2008).Themainreasonforthistendencyisattributedtothecapabilityforasystembasedoncamerastoobtainrangeinformation,andalsoretrievingtheenvironment’sappearance,colorandtexture,givingarobotthepossibilityofintegratingormore,camerasarelessexpensive,lighterandhave123

unately,theremightbeerrorsinthedataduetothefollow-ingreasons:insufficientcameraresolution,lightingchanges,surfaceswithlackoftexture,blurredimagesduetofastmovements,firstworksonvisualnavigationwerebasedonabinocularstereoconfiguration(Seetal.2002;Olsonetal.2003).However,-inmanycasesitisdifficulttohavearnativeistouseapairofmonocularcameras(forexamplewebcams),whichleadstoconsiderdifferentaspectssuchas:(a)thecamerasynchronizationthroughtheuseofhardwareorsoftware,(b)thedifferentresponsesofeachCCDsensortocolorandluminance,and(c)themechanicalalignmentaccordingtothegeometryschemechosen(parallelorconvergentaxes).Worksalsoexistthatmakeuseofmulti-camerarigswithorwithoutoverlappingbetweentheviews(KaessandDellaert2010;Carreraetal.2011)andcameraswithspeciallenssuchaswide-angle(Davisonetal.2004)oromnidirectional(ScaramuzzaandSiegwart2008)withthegoalofincreasingvisualrangeandthusdecrease,tosomeextent,ly,RGB-D(colorimagesanddepthmaps)sensorshavebeenusedtomapindoorenvironments(Huangetal.2011),ndentlyoftheconfigurationused,camerashavetobecalibrated(manuallyoff-lineorautomaticallyon-line).Calibrationestimatesintrinsicandextrinsicparameters,thefirstdependonthecamera’sgeometry(focallengthandprincipalpoint),whiletheseconddependonthecamera’spositioninspace(rotationandtranslationwithrespecttosomecoordinatesystem).Thenecessaryparametersareusuallyestimatedfromasetofimagesthatcontainmultipleviewsofacheckerboardcalibrationpattern,torelatetheimage’scoordinateswiththereal-worldcoordinates(HartleyandZisserman2003).Manytoolsexisttoexecutetheprocessofcalibration,someofthemare:thecalibrationfunctionsofOpenCV(2009)(basedontheZhangalgorithm(Zhang2000)),CameraCalibrationToolboxforMatlab(Bouguet2010),TsaiCameraCalibrationSoftware(Willson1995),OCamCalibToolboxforomnidi-rectionalcameras(Scaramuzza2011),andMulti-CameraSelf-Calibrationtocalibrateseveralcameras(atleast3)(Svoboda2011).Ifthecameracalibrationisperformedoff-line,thenitisassumedthattheintrinsicproper-tiesofthecamthemostpopularoption,heless,theintrinsiccamerainformationmaychangeduetosomeenvironmentalfac-torsoftheenvironment,rmore,arobotthatworksinrealworldconditionscanbehitordamaged,whichcouldinvalidatethepreviouslyacquiredcalibration(Kochetal.2010).Stereoconfigurations(binocular,trinocularormultiplecameraswiththeirfieldsofvisionpartiallyoverlapped)offertheadvantageofbeingabletoeasilyandaccuratelycalculatethereal3Dpositionsofthelandmarkscontainedinthescene,bymeansoftriangulation(HartleyandSturm1997),ksofKonoligeandAgrawal(2008),Konoligeetal.(2009),Meietal.(2009)calizationandmappingisbeingdonewithasinglecamera,themapwillsufferfromascaleambiguityproblem(Nistér2004;Strasdatetal.2010a).Toobtain3Dinformationfromasinglecamera,re:(a)withtheknowledgeoftheintrinsicparametersonly;withthisalternativetheenvironmentstructureandtsdeterminediftherealdistancebetweentwopointsinspaceisknown;and(b)whereonlycorrespondencesareknown;inthiscase,thereconstructionismadeuptoaprojectivetransformation.123

Visualsimultaneouslocalizationandmapping59Theideaofutilizingonecamerahasbecomepopularsincetheemergenceofsinglecam-eraSLAMorMonoSLAM(Davison2003).Thisisprobablyalsobecauseitisnoweasiertoaccessasinglecamerathanastereopair,throughcellphones,nocularapproachoffersaverysimple,flterisapartiallyobservableproblem,wheresensorsdonotprovidesufficientusesalandmarkinitializationprob-lem,wheresolutionscanbedividedintotwocategories:delayedandundelayed(Lemaireetal.2007;Vidaletal.2007).AsalientfeaturetrackingacrossmultipleobservationshasoughmanycontributionshavebeenmadetovisualSLAM,sualSLAMsystemssufferfromlargeaccumulatederrorswhiletheenvironmentisbeingexplored(orfailcompletelyinvisuallycomplexenvironments),whichleadsrimaryreasonsexist:(1)First,generallyitisassumedthatcameramovementissmoothandthattherewillbeconsistencyintheappearanceofsalientfeatures(Davison2003;Nistéretal.2004),veassumptionsarehighlyrelatedtotheseiginatesaninaccuracyincamerapositionwhencapturingimageswithlittletextureorthatareblurredduetorapidmovementsofthesensor(ibrationorquickdirectionchanges)(PupilliandCalway2006).Thesephenomenaaretypicalwhenthecameraiscarriedbyaperson,humanoidrobots,andquad-rotorhelicopters,ofalleviatingthisproblemtosomeextentisbytheuseofkeyframes(see“AppendixI”)(Mouragnonetal.2006;KleinandMurray2008).Alternatively,Prettoetal.(2007)andMeiandReid(2008)analyzetheproblemofvisualtrack,mostofresearchersassumethattheenvironmentstoexplorearestaticandthattheyonlycontainstationaryandrigidelements;isnotconsidered,themovingelementswilloriginatefalsematcfirstapproachestothisproblemareproposedbyWangetal.(2007);WangsiripitakandMurray(2009);Miglioreetal.(2009),aswellasLinandWang(2010).Third,remanysimilartextures,suchastherepeatedarchitecturalelements,meobjectssuchastraffikesitdifficulttorecognizeapreviouslyexploredareaandalsotodoSLAMonlargeextensionsofland.(2)(3)4SalientfeatureselectionWewillmakeadifferencebetweensalientfeaturesandlandmarks,ingtoFrintropandJensfelt(2008),alandmarkisaretherhand,asalientfeatureisaregionoftheimagedescribedbyits2Dposition(ontheimage)andan123

survey,thetermsalientfeatureisusedasageneralizationthatcanincludepoints,regions,ientfeaturesthatareeasiesttolocate,arethoseproducedbyartificiallandmarks(FrintropandJensfelt2008).Theselandmarksareaddedintentionallytotheenvironmentwiththepurposeofservingasanaidfornavigation,sorcirclessituatedontheflandmarkshavetheadvantagethattheirappearanceisknowninadvance,r,thellandmarksarethosethatexisthabituallyintheenvironment(Seetal.2002).Forindoorenvironmoorenvironments,treetrunks(Asmar2006),regions(Matasetal.2002),orinterestpoints(Lowe2004)restpointisanimagepixelwithsuchaneighbd-qualityfeaturehasthefollowingproperties:itmustbenotable(easytoextract),precise(itmaybemeasuredwithprecision)andinvarianttorotation,translation,scaleandilluminationchanges(Lemaireetal.2007).Therefore,agood-qualiientfeatureextractionprocessiscomposedoftwophases:ectcriptioncoarianceofthedescriptortochangesinpositionandorientationwillpermittoimprovetheimagematchinganddataassociationprocesses(describedinSect.5).4.1DetectorsInthemajorityofSLAMsystemsbasedonvision,naturalfeaturespresenteverywherehavebeenused,suchascorners,interestpoints,ectionofthetypeoffeaturestobeusamplesare:Harriscor-nersdetector(HarrisandStephens1988),Harris-LaplaceandHessian-Laplacepointsdetectors,aswellastheirrespectiveaffineinvariantsversionsHarris-AffineandHessian-Affine(MikolajcczykandSchmid2002);DifferenceofGaussians(DoG)usedonSIFT(ScaleInvariantFeatureTransform)(Lowe2004);MaximallyStableExtremalRegions(MSERs)(Matas2002),FAST(FeaturesfromAcceleratedSegmentTest)(RostenandDrummond2006)andtheFast-HessianusedonSURF(SpeededUpRobustFeatures)(Bayetal.2006).Mikolajczyketal.(2005)madeanevaluationoftheperformanceofthesealgorithmswithrespecttoviewpoint,zoom,rotation,out-of-focus,sian-AffineandMSERdetectorshadthebestperfor-mance,MSERwasthemostrobustwithrespecttoviewpointandlightingchanges,andtheHessian-Affi(TuytelaarsandMikolajczyk2008)thesedetectorsandsomeothersareclassified,takingintoconsiderationtheirrepeatability,precision,robustness,effiorityofvisualSLAMsystemsusecornersaslandmarksduetothr,EadeandDrummond(2006a)proposetouseedgesegmentscallededgeletsinareal-timeMonoSLAMsystem,allohorsdemonstratedthatedgesaregoodfeaturesfortrackingandSLAM,duetotheirinvarianceto123

Visualsimultaneouslocalizationandmapping61lighting,ofedgesasfeatureslookspromising,sinceedgesarelittleaffectedbyblurringcausedbythesuddenmovementsofthecamera(KleinandMurray2008).Nonetheless,therhand,Geeetal.(2008)andMartinezandCalway(2010)investigatethefusionoffeatures(,linesandplanarstructures)inasinglemap,withthepurposeofincreasingtheprecisionofSLAMsystemsandcreatingabetterrepresentationoftheenvironment.4.2DescriptorsOneofthemostcommonlyuseddescriptorsforobjectrecognitionisthehistogram-typeSIFTdescriptor,proposedbyLowe(2004),whichisbasedonthespatialdistributionoflocalfeaturesintheneighborhoodofthesalientpoint,ukthankar(2004)proposeamodificationtoSIFTcalledPCA-SIFT,whosemainideaistoobtainadescructiotogram-typedescriptorshavethepropertyofbeinginvarianttotranslation,rotation,andscale,ustiveevaluationofseveraldescriptionalgorithmsandapro-posalforanextensionoftheSIFTdescriptor(GradientLocation-OrientationHistogram-GLOH)maybefoundin(MoreelsandPerona2005)and(MikolajcczykandSchmid2005),(Giletal.2009)appearsacomparativestudyofdluationisbasedonthenumberofcorrectandincorrectmatchesfoundthroughvideosequenceswithsignificantchangesinscale,workitisdemonstratedthatSURFdescriptorron,theauthorsmanifestthatSIFTdoesnotdemonstrategreatstability,whichmeansthatmanyofthelandmarksdetectedtlytherearemanyvariantsthatimprovetheperformanceoftheSIFTalgorithm,forexample:ASIFT,whichincorporatesinvariancetoaffinetransformations(MorelandYu2009),BRIEF(BinaryRobustIndependentElementaryFeatures)(Calonderetal.2010);ORB,afastbinarydescrip-torbasedonBRIEFbutrotationinvariantandresistanttonoise(Rubleeetal.2011);PIRF(Position-InvariantRobustFeature)(Kawewongetal.2010)andGPU-SIFT,animplemen-tationofSIFTonaGPU(GraphicsProcessingUnit)inordertomakeprocessinginparallelandinrealtime(Sinhaetal.2006).5TheimagematchinganddataassociationproblemsInstereocorrespondence,theimagematchingconsistsinsearchingforeachelementinoneimage,chingtechniquescanbedividedintotwocategories:echniquesarenecessaryduringthestreaofrobotnavigation,thedataassociationconsistsinrelatingthesensor’smeasurementswiththeelementsalreadyinsidetherobot’smap(NeiraandTardós2001).Thisproblemalsoinvolvesdeterminingiftficientimagematchiorswillrapidlyleadtoincorrectmaps.123

s-Pachecoetal.5.1ShortbaselinematchingBaselineisthelineseedifferencebetweentheimagestakenfromdifferentviewpointissmall,thecorrespondingpointwillhavealmostthesamepositionandappearanceinbothimages,case,thepointischaracterizedsimplybytheintensityvaluesofasetofsampledpixelsfromarectangularwindow(alsoknownaspatch)ensityvaluesofthepixelsarecomparedbymeansofcorrelationmeasureslikecrosscorrelation,sumofsquareddifferencesandsumofabsolutedifferences,(CiganekandSiebert2009)es(KonoligeandAgrawal2008;Nistéretal.2004)manifestthatthemeasureofnormalizedcrossedcorrelation(NCC)(Davison2003)and(Moltonetal.2004)anhomographyiscalculatedtodeformthepatchandmakethecorrespondenceswithNCCinvarianttoviewpoints,unately,thecorrageregionwithrepeatedtexture,rtbaselinecorrespondences,itisimportanttotakeintoaccountthedimensionsofthepatchaswellasthedimensionsofthesearchregion,otherwiseerrorswillappear(Nistéretal.2004).Forexample,patchesthataretoolittlearegoodforspeed,buttendtogeneratecommendedtousepatchesofapproximately9×9or11×11pixelsandplacethepatchoveracorner,sinceinsucharegionthegradientoftheimagehastwoormoredominantdirectionsand,consequently,ofdescriptorsisunnecessaryforframetoframeshortbaselinematching,butiftrackingfailsandthecameraislost,vantageofshortbaselineisthatdepthcomputationisverysensitivetonoise,easurementsofimage’scoordinates,r,itispossibletometal.(2006),Cannons(2008)andLepetitandFua(2005)presentastudyofthestate-of-the-artoftechniquestoperformtrackingbasedonfeatures,contoursorregions.5.2LongbaselinematchingWhenworkingwithlongbaselines,imagespresentbigchangesinscaleorperspective,weatesadif-ficultcorrespondenceproblem,seeSect.3ofBrownetal.(2003).Datafromtheimageintheneighborhoodofapointaredistortedbychangesinviewpointandlighting,iestwaytofindcorrespondencesistocompareallthefeaturesofanimageversusallthefeaturesofsomeotherimage(approachknownas“bruteforce”).Unfortunately,thisprocessgrowsinaquadraticmannerforthenumberofextractedfeatures,ntyears,therehasbeenconsiderableprogressinthedevelopmentofmatchingalgorithmsfothesealgorithmsobtainadescriptorforeachdetectedfeature,calculatedissimi-123

Visualsimultaneouslocalizationandmapping63laritymeasuresbetweendescriptorsandusedatastructurestoperformthesearchofpairsquicklyandeffireseveraldissimilaritymeasures,suchasEuclideandistance,Manhattandis-tance,Chi-Squaredistance,astructurescanbebalancedbinarytreescalledkd-trees(BeisandLowe1997;SilpaandHartley2008)orhashtables(GraumanandDarrell2007).Therearealsocriteriafordecidingwhentwofeaturesmustbeassociated(MikolajcczykandSchmid2005).Someexamplesare:(a)distancethreshold:twofeaturesarerelevantifthedistancebetweentheirdescriptorsisbelowathreshold;(b)nearestneigh-bor:AandBarerelatedifdescriptorBistheclosestneighborofthedescriptorAandifthedistancebetweenthemisbelowathreshold,and(c)nearestneighbordistanceratio:thisapproachissimilartonearestneighborexceptthatthethresholdisappliedtotheratioofdistancesofthecurrentpixeltothefigthefirstcri-teriondescribedabove,afeatureofthefirstredifferenttechniquestodisambiguatethesecandidatematches,forexample:bymeansofrelaxationtechniques(Zhangetal.1994)orconsideringcollectionsofpoints(Dufournaudetal.2004).polarconstraintestablishesthat:anecessaryconditionforxandx′tobecorrespondingpoints,isthatthepointx′havetobeontheepipolarlineofx(HartleyandZisserman2003).InthiswaythetailsmaybefoundinTuytelaarsandVan-Gool(2004);ZhangandKosecka(2006)andMatasetal.(2002).Otherresearcheslike(LepetitandFua2006;Grauman2010;Kulisetal.2009;Özuysaletal.2010)-formulatestheproblemofcorrespondenceasaproblemofclassification,pecificcaseofSLAMapplicationsinrealtime,thiscouldnotloeless,(Hinterstoisseretal.2009;TaylorandDrummond2009)haveproposedfastermethodsforachievingon-linelearning,retal.(2009),Lietal.(2010)andGuetal.(2010)proposeadifferentimagecorre-spondenceapproach,whameway,Sanromáetal.(2010)proposeaniterativematchingalgorithmbasedongraphs,unately,theseresearchesarestilllimitedbigh-qualitydescriptorsorevendifferentecorrespondencesareusedinsideaSLAMsystem,-fore,itisnecessarytouserobustestimatorsasRANSAC(RandomSampleConsensus),PROSAC(ProgressiveSampleConsensus),amongothers,rativeanalysisoftheseestimatorscanbefoundin(Ragurametal.2008).Theestimatorsarecommonestimatesaglobalrelationshipadaptingdata,andatthesametimeclassifiesdataunderinliers(datawhichisconsistentwiththerelationship)andoutliers(notconsistentwiththerelationship).Duetotheabilityoftoleratingalargeamountofoutliers,thisalgorithmisapopularoptiontosolvealargevarietyofestimationproblems.123

rnativetoRANSACispresentedbyChliandDavison(2008,2009),whichpro-poseaBaymatchingperformsasearchonlyinpartsoftheimagewhereitismostlikelytofindtruepositives,reducingthenumberofoutgorithitationofthethisproblem,Handaetal.(2010)proposeanextensionallowingmanaginghundredsoffeaturesinreal-time,measuretheperformanceofmatchingalgorithmsisbymeansoftheReceiverOperatingCharacteristiccurve,orROCcurve(Fawcett2006).Thisisagraphicalrepresen-tationinvolvingthecomputationoftruepositives,falsepositives,falsenegativesandtruenegatives,ruepositivesarethenumberofcorrectmatches,falsenegativesarematchesthatwerenotcorrectlydetected,falsepositivesarematchesthatareipapersoftheinformationretrievalliterature(Majumderetal.2005),thefollowingtwometricsareused:precision(numberofcorrectmatchesdividedbythetotalnumberoffoundcorrespondences)andrecall(numberofcorrectmatchesdividedbythetotalnumberofexpectedcorrespondences).5.3DataassociationinvisualSLAMThedataassociationprobleminsociationhasparticularcases,as:loopclosuredetection,kidnappedrobot(orcamera),andmulti-sessionandcooperativemapping;whicharedescribedinthefollowinglines:5.3.1LoopclosuredetectionLoopclosuredetectionconsistsinrecognizingaplacethathasalreadybeenvisitedinacyclicalexcursionofarbitrarylength(HoandNewman2007;Clementeetal.2007;Meietal.2010).Thisproblemhasbeenoneofthegreatesisproblemarisesanotheronecalledpercep-tualaliasing(Angelietal.2008;CumminsandNewman2008);presentsaproblemevenwhenusingcamerasassensorsduetotherepetitivefeaturesoftheenvironment,ys,oopclosuredetectionmethodmusingtoWilliamsetal.(2009)detectionmethodsforloopclosuresinvisualSLAMcanbedividedintothreecategories:(1)maptomap;(2)imagetoimage;and(3)riesdiffermainlyaboutwheretheassociationdataaretakenfrom(metricmapspaceorimagespace).HowevertheidealwouosuredetectionisanimportantproblemforanySLAMsystem,andtakingintoaccountthatcamerashavebecomeaverycommonsensorforroboticapplications,ewman(2007)proposetouseasimilaritymatrixtocodetherelatmonstratebymeansofasinglevaluedecompositionthatitispossibletodetectloopclosures,despiteofthepres-123

VisualsimultaneouslocdDrummond(2008)presentaunifiedmethodtorecoverfromtrackingfailuresasoproposeasystemcalledGraphSLAMwhereeachnodestoreslartodetectfailuresorloopclosures,theymodelappearanceasaBagofVisualWords(BoVW)tofindthenodesthathaveasimilarappearanceinthecurrentvideoimage(see“AppendixII”).Angelietal.(2008)presentamethodtodetectloopclosuresunderaschemeofBayessianfilteringandamethodofincrementalBoVW,wherethepsandNewman(2008)pro-poseaprobabilisticframeworktorecognizeplaces,hthelearningofagenerativemodelofappearance,theydemonstratethatnotonlyitispossibletocomputetheresemblanceoftwoobservations,butalsotheprobabilitythattheybelongtothesameplace;and,thus,theycalculateaprobabilitydistributionfunction(pdf)y,Meietal.(2010)proposeanewtopometricrepresentationoftheworld,basedonco-visibility,whichallowstosimplifydataasloopclosureworksdescribedabove,aimtoachieveaprecisionof100%.ThisisduetothefactthatasinglefalontextofSLAM,falsepositivesaregraverthanfalsenegatives(Magnussonetal.2009).Falsenega,inordertodeterminetheefficiencyofaloopclosuredetector,therecallrateshouldbeashighaspossible,withaprecisionof100%.5.3.2KidnappedrobotIntheproblemofthekidnappedrobot,robotpossecanoccuriftherobotisputbackintoanalreadymappedzone,withouttheknowledgeofitsdisplacementwhileitisbeingtransportedtothatplace,orwhenrobotperformsblindmovementsduetoocclusions,temporarysensormalfunction,orfastcameramovements(EadeandDrummond2008;Chekhlovetal.2008;Williamsetal.2007).Chekhlovetal.(2008)proposeasystemcapableoftoleratingtheuncertaintyaboutcam-eraposeandrecoverfromminortrackconsistsingeneratingadescriptor(basedonSIFT)ation,itusesanindexbasedonlow-ordercoeffimsetal.(2007)presentare-localizationmodulethatmonitorstheSLAMsystem,detectstrackingfailures,determinesthecameraposeinthemapland-localizationisperformedbyalandmarkrecognitionalgorithmusingtherandomizedtreesclassifiertechniqueproposedbyLepetitandFua(2006)findthecamerapose,candidateposesaregeneratsaselectionofsetsofthreepotentialmatches,then,allthecosesareevaluatedseekewithalargeconsensusisfound,thatposeisassumedtobecorrect.123

s-Pachecoetal.5.3.3Multi-sessionandcooperativemappingThemulti-sessionandcooperativemappingconsistsinaligntwoormorepartialmapsoftheenvironmentcollectedbyarobotindifferentperiodsofoperationorbyseveralrobotsatthesametime(visualcooperativeSLAM)(HoandNewman2007;Giletal.2010;Vidaletal.2011).Inthepast,theproblemofassociatingmeasurementswithlandmarksonthemapwassolvedthroughalgorithmssuchasNearestNeighbor,SequentialCompatibilityNearestNeighborandJointCompatibilityBranchandBound(NeiraandTardós2001).However,thesetechniquesaresimilarbecausetheyworkonlyifagoodinitialguessoftherobotinthemapisavailable(CumminsandNewman2008).6SolutionstothevisualSLAMproblemThetechniquesusedtosolvethevisualSLAMproblemcanbedividedintothreemaingroups:(a)classicones,basedonprobabilisticfilters,withwhichthesystemmaintainsaprobabi-listicrepresentationofboththeposeoftherobotandthelocationofthelandmarksintheenvironment,(b)thetechniquesemployingStructurefromMotion(SfM)inanincremental(causal)manner,andfinally(c)ollowingsectionssomedetailsofeachofthesetechniquesaredescribed.6.1ProbabilisticfiltersMtheseare:theExtendedKalmanFilter(EKF),FactoredSolutiontoSLAM(FastSLAM),Maxi-mumLikelihood(ML)andExpectancyMaximization(EM)(Thrunetal.2005b).Thefirsttwotechniqueslistedabovearethemostcommonlyusedbecausetheyofferthepproachesaresuc-cessfulonasmallscale,buthavealimitedcapabildologyforbuildingmapsinanincremental(causal)way,wasfirstpresentedintheworkofSmithetal.(1990).Smithetal.(1990)introducedtheconceptofstochasticmapanddevelo-basedapproachtoSLAMischaracterizedbyastatevectorcomposedoftheloca-tionoftheentityandsomemapelements,estimertaintyisrepresentedbyprobabilitydensityfunctions(pdfs).Itissupposedthattherecursivepropagatihasthedisadvantageofbeingparticularlysensitivetobadassociations,oneincorrectmeasurementcanleadtothedivergenceoftheentirefiplexityofEKFisquadraticwithrespecttothenumberoflandmarksonthemap,beingdiffiiteraturetherearedifferentmethodstoreducethiscomplexitythroughtechniquessuchas:AtlasFramework(Bosseetal.2003),CompressedExtendedKalmanFilter(CEKF)(Guivant2002),SparseExtendedInformationFilter(SEIF)(Thrunetal.2002),DivideandConquerinO(n)givenbyPazetal.(2008)orConditionallyIndependentSubmaps(CI-Submaps)developedbyPiniésandTardós(2008).FastSLAMwasproposedbyMontemerloetal.(2002)andlaterimprovedin(Montemerlo2003).ThismethodmaintainsanentityposedistributionasasetofRao-Blackwellizedpar-ticles,whereeachparticlerepresentsatrajectoryoftheentity,maintainsitsownmapusing123

Visualsimultaneouslocalizationandmapping67theEKF,hasanhypothesisontheassociationofdata(multiplehypotheses)orithmconsistsofaparticlegenerationprocessandare-samplingprocess,putationalcostofthissolutionislogarithmic,O(plogn),wheainproblemisthatthereisnowaytodeterminethenumbe,manyparticlesrequirealotofmemoryandcomputingtime,n(2003)wasthefirsttopresentareal-timemonocularprobabilisticsystem,chniqueofSLAM,performsimultaneously3Dmetricmap-pingofpointsandlocationat30framespersecond,usingonlyadigitalfirewire(IEEE-1394)idersthecompletecameramovement(6gdl):position(x,y,z)andorientation(pitch,yawandroll).Davison’sworkhasthelimitationofonlyworkinginconfinedandindoorspaces,presentsaninconvenientduetotheinabilityofthemodeltoproperlydealingwithsuddenmovements,ore,thedistancethatthesalientfeaturescanbemovedbetweenframesisverysmall,inordertoensuretracking(otherwise,itcouldturnouttobeveryexpensive,sincealargeregiontosearchforfeaturesisproposed).TofaceerraticmovementofthecamerawithMonoSLAM,Geeetal.(2008)developedanoptimizedversion,capableofoperatingat200Hzusinganextendedmotionmodelthattakesintoaccountacceleration,andlinearandangularvelocties;however,itsperformanceinrealtimeislimitedtoonlyafewseconds,easethenumberofmaintainedlandmarksonthemap,EadeandDrummond(2006b)usedaparticlefiltertechniqueinspiredbythemethodproposedbyMontemerloetal.(2002),hodofEadeandDrummondisabletotrackupto30teetal.(2007)proachisbasedonahierarchicalmappingtechniqueandarobustdataassociationalgorithmbasedonGeometricConstraintsBranchandBound(GCBB)capableofperforminglargeloopsclosure(250mapprox.).Asmentionedabove,oneprobleminthemonocularvisualSLAMistheinitializationofthelandmarks,s,Davison(2003)usesadelayedinitializationtechnique,whileMontieletal.(2006)proposeatechniquecalledinversedepthparametrization,whichperformsanundelayedlandmarkinitializationinanEKF-SLAMsystemfromthefirstmomenttheyaredetected.6.2StructurefrommotionStructurefromMotion(SfM)techniquesallowtocompute3Dstructureofthesceneandcamerapositionfromasetofimages(Pollefeysetal.2004).ndardprocedure(carriedoutoff-line)istoextractsalientfeaturesofincomingimages,tomatchthemandperformanon-linearoptimizationcalledBundleAdjustment(BA)tominimizethere-projectionerror(Triggsetal.1999;Engelsetal.2006).SfMallowsahighprecisioninthelocatiethis,severalproposalshavebeenmadeusingSFMtolocatewithprecisionwhilecreatingagoodrepresentationoftheenvironment.123

hodtosolvetheproblemofSfMincrementallyisthevisualodometrypublishedbyNistéretal.(2004).Visualodometryconsistindeterminesimultaneouslythecameraposeforeachvideoframeandthepositionoffeaturesin3Dworld,nonetal.(2006,2009)usesavisualodometrysimilartoNister’sproposal,butaddingatechniquecalledLocalBundleAdjustment,ualodometryallowtoworkwiththousandsoffeaturesperframe,ndMurray(2007)presentamonocularmethodcalledParallelTrackingandMapping(PTaM).Itusesanapproachbasedonkeyframes(see“AppendixI”)firstthreadofexecutionperformthetaskofrobustlytrack-ingalotoffeatures,stempres(KonoligeandAgrawal2008;Konoligeetal.2009)theauthorsuseatechniquecalledFrameSLAMandView-BasedMaps,methodsarebasedonmakingarepresentationofthemapasa“skeleton”consistingofanon-linearconstraintgraphbetweenframes(ratherthanindividual3Dfeatures).esultsshowagoodperformanceonlongtrajectories(approximately10km)lyStrasdatetal.(2010b)haverecognizedthatinordertoincreaseaccuracyofthepositionofamonocularSLAMsystemitisrecommendedtoincreasethenumberoffeatures(essentialpropertyofSfM)ratherthanthenumberofframes;aswellas,thatBundleAdjust-mentoptimizationtechniquesarebetterthanfir,theymanifestthatthefiltermightbebenefialSLAMsystemwouldexploitthebenefitsofbothSfMtechniquesandprobabilisticfilters.6.3Bio-inspiredmodelsMilfordetal.(2004)usemodelsofthehippocampus(responsibleforspatialmemory)Mcangenerateconsistenterimentscarriedoutin(MilfordandWyeth2008;Gloveretal.2010)showsagootionithastheability(Milford2008)alargerstudyofRatSLAMandotherbiologicalandnavigationsystemsofbees,ants,t(2010)examinesthebehaviorofantsindesertghthisresearchfocusesonunderstandinghowantsnavigateusingvisualinformation,theauthorstatesthattheproposedsolutionwouldbeviableandeasytoimplementinarobot.7Representdoccupiedenvironmentspaces(obstacles)redif-ferenttypesofmapsreportedintheliterature,broadlydividedinmetricandtopologicalmaps.123

Visualsimultaneouslocalizationandmapping69Metricmapscapturethegeometricpropertiesoftheenvironment,whereasetricmapscategoryitcanbeconsideredtheoccupancygridmaps(Gutmannetal.2008)andlandmark-basedmaps(KleinandMurray2007;Seetal.2002;SáezandEscolano2006;Mouragnonetal.2006).Gridmapsmodelfreeandoccupiedspacebymeansofadiscretizationoftheenvironmentinformofcells,whichmaycontain2D,rk-basedmapsident(2002)performsadetailedstudyonthetopicopresentationthroughlandmarks,onlyisolatedlandmarksfromthestructureoftheenvironmentarecaptured,minimizingthus,heforegoing,thesetypesofmapsarenotidealforobstacleavoidanceorpathplan-ning,r,whenthedeterminationoftheposeoftheentityismoreimportantthanthemap,gicalmapsrepresenttheenvironmentasalistofsignificantplacesthatareconnectedbyarcs(similartoagraph)(Fraundorferetal.2007;EadeandDrummond2008;Konoligeetal.2009;Botterilletal.2010).Arepresentationoftheworldbasedongraphssimplifir,itisneces-sarytoperformaglobaloptimizationofthemaptoreducelocalerror(Freseetal.2005;Olsonetal.2006).AtutorialtoformulatetheSLAMproblembymeansofgraphscanbeconsultedin(Grisettietal.2010).Otherrelevantschemesbasedongraphsarethefollowing:KonoligeandAgrawal(2008),Konoligeetal.(2009)builtasequenceofrelativeposesbetweenframes,owresultsover10kmtrajectoriesusingstereovision,althoughitrequirespositionsgeneratedbyanIMU(InertialMeasurementUnit)horsstatethattheirschemeisapplicabletomonoc-ularSLAM,ralternativeispresentedbyMeietal.(2009),whichmanagestomaintainaconstantcomplexityintimetoopti-mizelocalsub-mapsconsistinnerateatrajectoryofapproximately2km,itationofthetopologicalrepresentationisthelackofmetricinformation,uently,BazeilleandFilliat(2010);Angelietal.(2009)andKonoligeetal.(2011)proposestrategiesftly,rearestillanumberofchallengestobeovercome,astheabilitytoeditthegraphwhendetectingwrongestimationsoftheposition,orthegenerationofglobalmapsofverylargedimensions(lifelongmapping).SeveraldatasetscontainingrealimagesequencesfortheevaluationofvisualSLAMsys-temsaredescribedin“AppendixIII”.Thekeycharacteristicsoically,wereport:(1)theauthornameanditsrespectivereference,(2)thetypeofsensingdeviceused,(3)thecoreofthevisualSLAMsolution,(4)thekindofenvironmentrepresentation,(5)detailsofthefeatureextractionprocess,(6)theabilityandrobustnessofthesystemtooperateunderavarietyofconditions:movingobjects,abruptmovementsandlargeenvironments,andalsotoperformloopclosures,and(7)thetypeofenvironmentusedtotesttheperformanceofthesystem.123

Table1SummaryofsomesystemsreviewedCoreofthesolutionDetectorMonoSLAM(EKF)VisualOdometryMetricMetricMetricFast-10HarriscornersNitzbergoperatorMetricHarriscornersMetricShiandTomasioperatorDescriptorImagepatchesImagePatchesImagepatchesImagepatchesImagepatchesTypeofmapFeatureextraction70123MetricMetricMetricTopologicalMetricTopologicalMetricHarrisaffineregions128DSIFTImagepatchesImagepatchesAppearance-basedmatchingImagepatches16DSIFTImagepatchesGlobalEntropyMinimizationAlgorithmVisualodometry+LocalbundleadjustmentParallelTrackingandMapping(Visualodometry+Bundleadjustment)DelayedstateformulationHierarchicalmap+EKFEKFShiandTomasioperatorHarriscornersRatSLAM(modelsoftherodenthippocampus)VisualodometryGraphSLAMConditionallyindependentdivideandconquer(EKF)SIFT(differenceofgaussians)ScalespaceextremadetectorShiandTomasioperatorAuthorTypeofsensingdeviceDavison(2003)MonocularcameraNistéretal.(2004)StereoormonocularcamerasSáezandEscolano(2006)StereocameraMouragnonetal.(2006)MonocularcameraKleinandMurray(2007)MonocularcameraHoandNewman(2007)Clementeetal.(2007)MonocularcameraandlaserMonocularcameraLemaireetal.(2007)Milford(2008)StereoormonocularcamerasMonocularcameraScaramuzzaandSiegwart(2008)OmnidirectionalcameraEadeandDrummond(2008)l.(2008)Stereocamera

Descriptor128DSIFT+LocalhuehistogramsU-SURF128DVisualsimultaneouslocalizationandmappingImagepatchesRandomtreesignaturesImagepatches+16DSIFTImagePatchesImagepatches128DSIFT71noeirtuctaaretFxefoeppyaTmnoitfuoleosroeChtfogneeicpsiynvTeesddeunitnoc1reolbhtuTaAecn)sssenerrreeeaninnffirrfsfisooduAcc(a-gsssTiiifrrrFttorrssrttIaaaaassSHHFFHaaFFcirteM+lllllaaaaccaicccciriiiigtgggoegooolclcclloMoloiroiirrooptpttppo+poeoeeooTTMTMMTTellaeegcnydpu+llsirnp)tnasndadyapPyteumnurrtrlnbtVioiusoe+aalsbtieaepmenlyntnvwmtenPpMAMndaoseac+roazdepd-onritiiriemd)oammafoveAíorditthFetttgoaemAeBtpsipscsealltMFdelFSurKmatmaidulds-jaEocxnjmBaetaKsBFAndacKla(onoEuil(s+drdeaadouRnuBjaei+opad+s+udbaFAEaFCViHxmtSEOViUaaMaarrIrreeegemam+mirmanaaacaaaocrecrrrrrreceaadamallalmramuurettlalalacceniutcucucoou-coc-cioonnmaonoeotlneooanrnuorMMCmpoMeotSMMMetS)8002)(0n1a)092))m0(08w10es0tr00ó2()e2)2Nd.9al(0(0l0eta02aade2D(t()edsllialai8gimnailrtems0leegé0oasiitnmtiun2nlsleoeACi(oiaPKWKBM123Detector

72Table1continuedCoreofthesolutionMovingobjects?NoNoNoYesNoNoNoNoNoNoNoNoYesNoNoNoNoNoNoNoIndoorOutdoorOutdoor/IndoorOutdoor/indoorIndoorLoopclosureevents?Thekidnappedrobotprob-lem?Large-scalemapping?TypeofmapCopewithTypeofenvironment123MonoSLAM(EKF)VisualOdometryMetricMetricMetricMetricMetricMetricMetricMetricTopologicalNoYesYesNoYesYesYesYesNoNoNoYesYesYesNoYesOutdoor/indoorOutdoorOutdoorOutdoorGlobalEntropyMinimizationAlgorithmVisualodometry+LocalbundleadjustmentParallelTrackingandMapping(Visualodometry+Bundleadjustment)DelayedstateformulationHierarchicalmap+EKFEKFRatSLAM(modelsoftherodenthippocampus)VisualodometryMetricTopologicalGraphSLAMNoYesNoYesNoYesYesYesOutdoorOutdoor/indoorAuthorTypeofsensingdeviceDavison(2003)MonocularcameraNistéretal.(2004)SáezandEscolano(2006)StereoormonocularcamerasStereocameraMouragnonetal.(2006)MonocularcameraKleinandMurray(2007)MonocularcameraHoandNewman(2007)Clementeetal.(2007)MonocularcameraandlaserMonocularcameraLemaireetal.(2007)Milford(2008)uzzaandSiegwart(2008)OmnidirectionalcameraEadeandDrummond(2008)Monocularcamera

Table1continuedTypeofmapMovingobjects?NoNoNoYesLoopclosureevents?Thekidnappedrobotprob-lem?Large-scalemapping?CopewithTypeofenvironmentAuthorTypeofsensingdeviceCoreofthesolutionPazetal.(2008)Topological+MetricNoTopologicalYesYesNoYesNoNoYesStereocameraMetricOutdoor/indoorAngelietal.(2008)MonocularcameraConditionallyindependentdivideandconquer(EKF)EKFIndoorOutdoorVisualsimultaneouslocalizationandmappingCumminsandNewman(2008)MetricTopologicalMetricMetricNoYesYesYesYesYesYesYesNoYesYesNoPiniésandTardós(2008)MonocularCameramountedonapan-tiltMonocularcameraFastAppearanceBasedMapping(FAB-MAP)YesYesYesNoOutdoorOutdoorOutdoorOutdoorKonoligeetal.(2009)Williams(2009)KaessandDellaert(2010)TopologicalBotterilletal.(2010)Conditionallyindependentlocalmaps(EKF)Stereocamera+IMUVisualodometry+SparsebundleadjustmentMonocularcameraHierarchicalmap+EKF+VisualodometryMulti-camerarigExpectationmaximization+StandardbundleadjustmentMonocularcameraOdometríavisual+BagofwordsYesYesYesTopological+MetricYesYesYesYesYesOutdoor/indoorOutdoor73123Meietal.(2010)StereocameraVisualodometry+Relativebundleadjustment+FAB-MAP

s-Pachecoetal.8ConclusionsThisworkverifiesthatthereisagreatconcduemainlytothefactthatacameraisanidealsensor,sinceitislight,passive,haslow-energyconsumption,r,theuseofvisionrequiresreliablealgorithmswithgoodperformanceandconsistentundervariablelightconditions,occlusionsorchangesinappearanceoftheenvironmentduetomovingpeopleorobjects,theapparitionoffeature-lessregions,ore,SLAMsystemsusingviatchingandthedataassociationarestillopenresearchareasinthefiectorandthedescriptorchosendirectlyaffecttheperformanceofthesystemtotrackthesalientfeatures,recognizeareaspreviouslyseen,buildaconsistentmodeloftheenvironment,ulartodataassociationistheneedfornavigationinthelongterm,ineptanceofabadassociationwillcauseseriouserrorsintheentireSLAMsystem,meaningthatbore,itiancebasedmethodstcommontechniqueinthiscategoryistheBoVW,duetoitsspeedtofir,se,thistechniquehasnotbeenyetthoroughlytestedtodetectimageswithlargevariationsofviewpointorscale,whicharetransformationsthatoftenoccurduringtheloopclosuredetection,,itdoesnottakeintoaccountthespatialdistributionbetweenthedetectedfeaturesand3Dgeometricinformation,ghtherehavebeenseveralproposalstobuildlifelongmaps,thisissueremainsatopicofinterest,aswellastheabilitytobuildma,therearenostandardsforevaluatingandcomparingthegeneraleffieless,thereareseveralindicatorsthatmaycharacterizetheirperformance,suchasthedegreeofhumanintervention,accuracyoflocation,mapconsistency,realtimeoperationandthecontrolofcomputationalcostthatariseswiththegrowthofthemap,ledgmentsThispaperhasbeenmadepossiblethankstothegeneroussupportfromthefollowinginstitutionswhichwearepleasedtoacknowledge:CONACYT(ConsejoNacionaldeCienciayTecnología)andCENIDET(CentroNacionaldeInvestigaciónyDesarrolloTecnológico).AppendixI:KeyframesAkeyframeisavideoframethatisdifferentenoughfromitspredecessorinthesequence,mesarealsousedtoestimateeffiiestwaytoclassifyavideoframeasakeyframeistocompareavideoframewithrespecttoanothertakenearlier,selectingthosethatmaximizeboththedistanceatwhichtheywerecapturedandthenumberoffeature123

Visual(Zhangetal.2010)acomparativestudyofdifferenttechnixII:Bagofvisualwords(BoVW)Recently,mostcontributionstosolvedataassociationinvisualSLAMuseBoVW(SivicandZisserman2003)anditsimprovedversioncalledVocabularytree(NistérandStewenius2006).TheBoVWhasseenagreatsuccessintheareaofinformationretrieval(Manningetal.2008)andcontent-basedimageretrievaldevelopedbythecomputervisioncommunity,duetoitsspeedinfir,thistechnethisproblemtosomeextent,spatialinfor-mationisnormallyintroducedinthelastphaseofretrieval,conductingapost-verificationtakingintoaccounttheepipolarconstraint(Angelietal.2008)or,recently,bymeansofConditionalRandomFields(Calonderetal.2010).ThisverificationallowsrejectingthoserecoveressicmodelofBoVWdescribesimagesasasetoflocalfeaturescallVWschemesgenerateanoff-linevocabularybymeansofaK-meansclustering(butanyothercanbeused)ofdescriptorsfromalargecorpusoftrainingimages(HoandNewman2007;CumminsandNewman2008).AnalternativeandmoreeffectiveapproachistodynamicallyconstructthechemeisdescribedbyAngelietal.(2008)andBotterilletal.(2010).Somevisualwotcommonschemetoassigneachwordaspecifiinestheimportanceofthewordsintheimage(TF-TermFrequency)andtheimpor-tanceofthewordsinthecollection(IDF-InverseDocumentFrequency).Inaddition,thereareotherschemes,whicharedividedintolocal(SquaredTF,Frequencylogarithm,Binary,BM25TF,amongothers)andglobal(ProbabilisticIDF,SquaredIDF,etc.)(Tirillyetal.2010).Aninvertedindexisusedtospeedupqueries,neentryforeachwordoftheimagecollection,ixIII:DatasetstotestvisualSLAMsystemsSomepublicdatasetsavailabletotestthevisualSLAMsystemsare:(a)NewCollegeandCityCentreDatasets(outdoor)(Cummins2008),usedbyCumminsandNewman(2008);(b)TheNewCollegeVisionandLaserDataSet(outdoor)(Smith2012),capturedbySmithetal.(2009)(c)Bovisa(outdoor)andBicocca(indoor)DatasetsofRawseedsproject(Rawseeds2012),capturedbyCerianietal.(2009);(d)TheCheddarGorgeDataSet(outdoor),capturedbySimpsonetal.(2012)andRGB-Ddatasets(indoor)(Sturm2012)(Sturmetal.2011).ReferencesAguilarW,FrauelY,EscolanoFetal(2009)isComput27(7):897–910123

eJ,SanfeliuA(2002):Pro-ceedingsofthe16thIAPRinternationalconferenceonpatternrecognition,vol2,pp693–696AngeliA,DoncieuxS,FilliatD(2008):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomationAngeliA,DoncieuxS,MeyerJ(2009):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp4300–4305ArtiedaJ,SebastianJ,CampoyPetal(2009)lRobotSyst55(4):299–321AsmarD(2006)tation,UniversityofWaterloo,CanadaAuatC,LopezN,SoriaC,etal(2010)SLAMalgorit:10.1186/1743-0003-7-10BaileyT,DurrantH(2006)Simultaneouslocalizationandmapping(SLAM):botAutomMag13(3):108–117BayH,TuytelaarsT,VanL(2006)SURF::ProceedingsoftheEuropeanconferenceoncomputervisionBazeilleS,FilliatD(2010)CombiningodometryantJOperRes44(4):365–377BeisJ,LoweD(1997)Shapeindexin:ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognition,pp1000–1006BogdanR,SundaresanA,MorissetBetal(2009)Leavingflatland:effilIssueonThree-DimensionalMapping26(10):841–862BosseM,NewmanP,LeonardJ,etal(2003):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp1899–1906BotterillT,MillsS,GreenR(2010)Bag-Robot28(2):204–226Bouguet(2010):///bouguetj/calib_doc/.Z,BurschkaD,HagerG(2003)ansPatternAnalMachIntell25(8):993–1008CadenaC,Gálvez-LópezD,RamosF,etal(2010):Proceed-ingsoftheIEEEinternationalconferenceonintelligentrobotsandsystems,pp5182–5189CalonderM,LepetitV,etal(2010)BRIEF::ProceedingsoftheEuropeanconferenceoncomputervisionCannonsK(2008)calreportCSE-2008-07,YorkUniversity,DepartmentofComputerScienceandEngineeringCarreraG,AngeliA,AndrewD(2011):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomationCastellanosJ,TardósJD,NeiraJ(2001)ansRobotAutom17(6):908–914CerianiS,FontanaG,GiustiAetal(2009)RawseedsgrRobots27(4):353–371ChatilaR,LaumondJ(1985):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,vol2,pp138–145ChekhlovD,MayolW,CalwayA(2007)Ninjaonaplane:automa:Proceedingsofthe6thIEEEandACMinternationalsymposiumonmixedandaugmentedreality,pp1–4ChekhlovD,MayolW,CalwayA(2008):ProceedingsoftheBritishmachinevisionconference,pp363–372ChliM,DavisonA(2008):ProceedingsoftheEuropeanconferenceoncomputervision::10.1007/978-3-540-88682-2_7ChliM,DavisonA(2009)utonomSyst57(12):1173–1187CiganekB,SiebertJ(2009),NewYork,pp194–195ClementeL,DavisonA,ReidI,etal(2007):Pro-ceedingsofrobotics:scienceandsystemsconferenceCollettM(2010):PsycholCogniSci107(25):11638–11643123

Visualsimultaneouslocalizationandmapping77Cummins(2008):///~mobile/IJRR_2008_d06March2012CumminsM,NewmanP(2008)FAB-MAP:botRes27(6):647–665CyrillS(2009)erTractsinAdvancedRobotics,vol55,ISBN:978-3-642-01096-5DavisonA(2003):ProceedingsoftheIEEEinternationalconferenceoncomputervision,vol2,pp1403–1410DavisonA,GonzálezY,KitaN(2004):5thIFAC/EURONsymposiumonintelligentautonomousvehiclesDavisonA,ReidI,MoltonN(2007)MonoSLAM:ansPatternAnalMachIntell29(6):1052–1067DufournaudY,SchmidC,HoraudR(2004)VisImageUnd-erst93(2):175–194DurrantH,BaileyT(2006)Simultaneouslocalizationandmapping(SLAM):botAutomMag13(2):99–110EadeE,DrummondT(2006a):ProceedingsoftheBritishmachinevisionconferenceEadeE,DrummondT(2006b):ProceedingsoftheIEEEconferenceoncom-putervisionandpatternrecognition,vol1,pp469–476EadeE,DrummondT(2008)UnifieedingsoftheBritishMachinevisionconferenceEngelsC,StewéniusH,NistérD(2006):PhotogrammetriccomputervisionFawcettT(2006)nRecognLett27(8):861–874FraundorferF,EngelsC,NisterC(2007)Topologicalmapping,:ProceedingsoftheIEEEinternationalconferenceonintelligentrobotsandsystems,pp3872–3877FreseU,LarssonP,DuckettT(2005)AmulansRobot,pp196–207,ISSN1552-3098FrintropS,JensfeltP(2008)ansRobot24(5):1054–1065GeeA,ChekhlovD,CalwayA,MayolW(2008)ansRobot24(5):980–990GemeinerP,DavisonA,VinczeM(2008)Impro:Proceedingsofrobotics:scienceandsystemsIVGilA,MartínezO,BallestaM,ReinosoO(2009)AcomparativeevasAppl21(6):905–920GilA,ReinosoO,BallestaM,JuliáM(2010)Multi-robotvisualSLAMusingarao-blackwellizedparticlefiutonomSyst58(1):68–80GloverA,MaddernW,MilfordM,etal(2010)FAB-MAP+RatSLAM::ProceedingsoftheIEEEinternationalconferenceonroboticsandautomationGrasaO,CiveraJ,MontielJ(2011):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp4816–4821GraumanK(2010)EffiACM53(6):84–94GraumanK,DarrellT(2007)Pyramidmatchhashing::ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognitionGrisettiG,KümmerleR,StachnissC,BurgardW(2010)ansIntellTranspSystMag2(4):31–43GuS,ZhengY,TomasiC(2010):ProceedingsoftheEuropeanconferenceoncomputervision,pp663–676GuivantJ(2002)Effitation,Uni-versityofSydney,AustraliaGutmannJ,FukuchiM,FujitaM(2008)botRes27(10):1117–1134HandaA,ChliM,StrasdatH,DavisonA(2010):ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognition,pp1546–1533HarrisC,StephensM(1988):Proceedingsofthefourthalveyvisionconference,pp147–151HartleyR,SturmP(1997)VisImageUnderst68(2):146–157123

yR,ZissermanA(2003)Multipleviewgeometryincomputervision,dge,ISBN:HinterstoisserS,KutterO,NavabN,etal(2009)Real-timelearningofaccuratepatchrectifi:Pro-ceedingsoftheIEEEconferenceoncomputervisionandpatternrecognitionHoK,NewmanP(2007)mputVis74(3):261–286HuangA,BachrachA,HenryP,etal(2011)VisualodometryandmappingforautonomousflationalsymposiumonroboticsresearchJohnsonM,PizarroO,WilliamsS,MahonI(2010)Generationandvisualizationoflarge-scaRobot27(1):21–51JonesE,SoattoS(2011)Visual-inertialnavigation,mappingandlocalization:botRes30(4):407–430KaessM,DellaertF(2010)VisImageUnderst114:286–296KawewongA,TangruamsubS,HasegawaO(2010)Position-invariransInformSyst9:2587–2601KeY,SukthankarR(2004)PCA-SIFT::ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognition,vol2,pp506–513KleinG,MurrayD(2007):Proceedingsofthe6thIEEEandACMinternationalsymposiumonmixedandaugmentedrealityKleinG,MurrayD(2008):ProceedingsoftheEuropeanconferenceoncomputervision,pp802–815KochO,WalterM,HuangA,TellerS(2010):Pro-ceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp2423–2430KonoligeK,AgrawalM(2008)FrameSLAM:ansRobot24(5):1066–1077KonoligeK,BowmanJ,ChenJ(2009)View-basedmaps,In:Proceedingsofrobotics:scienceandsystemsKonoligeK,Marder-EppsteinE,MarthiB(2011):Pro-ceedingsoftheIEEEinternationalconferenceonroboticsandautomationKragicD,VinczeM(2009)rendsRobot1(1):1–78,ISBN:978-1-60198-260-5KulisB,JainP,GraumanK(2009)ansPatternAnalMachIntell31(12):2143–2157LemaireT,BergerC,JungIetal(2007)Vision-basedSLAM:mputVis74(3):343–364LepetitV,FuaP(2005)rendsComputGraphComputVis1(1):1–89LepetitV,FuaP(2006)ansPatternAnalMachIntell28(9):1465–1479LiH,KimiE,HuangX,HeL(2010)Objectmatchingwithalocallyaffine-invariantconstraintIn:ProceedingsoftheInternationalconferenceonpatternrecognition,pp1641–1648LinK,WangC(2010)Stereo-basedsimultaneouslocalization,:ProceedingsoftheIEEEinternationalconferenceonintelligentrobotsandsystems,pp3975–3980LoweD(2004)mputVis60(2):91–110MagnussonM,AndreassonH,etal(2009)Automaticappearance-basedimensionalMappingPart2,26(12):892–914ManningC,SchützeH,RaghavanP(2008)Introductiontoinformationretrieval,CambridgeUniversityPress,Cambridge,ISBN:MajumderS,SchedingS,DurrantH(2005):ProceedingsofAustralianconferenceonroboticsandautomationMartinezJ,Calway(2010):ProceedingsoftheBritishmachinevisionconference,pp1–11MatasJ,ChumO,etal(2002):ProceedingsoftheBritishmachinevisionconferencevol22,no.10,pp761–767MeiC,ReidI(2008):ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognition,pp1–8MeiC,SibleyG,CumminsM,etal(2009)Aconstant-timeeffi:ProceedingsoftheBritishmachinevisionconferenceMeiC,SibleyG,CumminsMetal(2010)RSLAM:mputVision94(2):1–17123

Visualsimultaneouslocalizationandmapping79MeiC,SommerladeE,SibleyC,etal(2011)Hiddenviewsynthesisu:ProceedingsoftheIEEEInternationalconferenceonroboticsandautomation,vol8,pp4240–4245MiglioreD,RigamontiR,MarzoratiD,etal(2009)Useasinglecameraforsimultaneousloca:ICRAworkshoponsafenavigationinopenanddynamicenvironments:applicationtoautonomousvehiclesMikolajcczykK,SchmidC(2002)Anaffi:ProceedingsoftheEuropeanconferenceoncomputervision,pp128–142MikolajcczykK,SchmidC(2005)ansPatternAnalMachIntell27(10):1615–1630MikolajczykK,TuytelaarsT,SchmidSetal(2005)AcomparisionofaffimputVis65:43–72MilfordM(2008)Robotnavigationfromnature:simultaneous,localisation,mapping,andpathplanningbasedonhippocampalmodels,erTractsinAdvancedRobotics,ISBN:3540775196MilfordM,WyethG(2008)MappansRobot24(5):1038–1053MilfordM,WyethG,PrasserD(2004)RatSLAM::ProceedingoftheIEEEinternationalconferenceonroboticsandautomation,vol1,pp403–408MoltonN,DavisonA,ReidI(2004):ProceedingsoftheBritishmachinevisionconferenceMontemerloM(2003)FastSLAM:afactoredsolutiontothesimultaneouslocalizationandmappingproblemwithunknowndataassociation,Dissertation,CarnegieMellonUniversity,USAMontemerloM,ThrunS,KollerD,etal(2002)FastSLAM:a:ProceedingsoftheAAAInationalconferenceonartificialintelligence,pp593–598MontielJ,CiveraJ,DavisonA(2006)Unifi:Pro-ceedingsofrobotics:scienceandsystemsMorelJ,YuG(2009)ASIFT:anewframeworkforfullyaffimagingSci2(2):438–469MoreelsP,PeronaP(2005):Proceed-ingsoftheIEEEinternationalconferenceoncomputervision,pp800–807MouragnonE,DhomeM,DekeyserF,etal(2006):Proceedingsoftheinternationalconferenceonpatternrecognition,pp1027–1031MouragnonE,LhuillierM,DhomeM,etal(2009)isComput,pp1178–1193,ISSN:0262-8856NeiraJ,TardósJD(2001)D:Pro-ceedingsoftheIEEEinternationalconferenceonroboticsandautomation17(6):890–897NewmanP,LeonardJ,NeiraJ,TardósJ(2002)Exploreandreturn:ex:ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,vol2,pp1802–1809NistérD(2004)AnefficientsolutiontothefiansPatternAnalMachIntell26(6):756–770NistérD,SteweniusH(2006):ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognition,vol2,pp2161–2168NistérD,NaroditskyO,BergenJ(2004):ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognitionvol1,pp652–659NüchterA,LingemannK,HertzbergJetal(2007)6DSLAM—Robot24(8):699–722NütziG,WeissS,ScaramuzzaD,SiegwartR(2010):10.1007/s10846-010-9490-zOlsonC,MatthiesL,SchoppersM,MaimoneM(2003)utonomSyst43(4):215–229OlsonE,LeonardJ,TellerS(2006):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp2262-2269OlsonC,MatthiesL,WrightJetal(2007)VisImageUnderst105(1):73–85OpenCV(2009)OpenCV::///documentation/camera_calibration_and_3d_cesed06March2012123

s-Pachecoetal.ÖzuysalM,CalonderM,LepetitV,FuaP(2010)ansPatternAnalMachIntell32(3):448–461PazL,PiniésP,TardósJD,NeiraJ(2008)ansRobot24(5):946–957PiniésP,TardósJD,NeiraJ(2006):Proceedin3074–3079PiniésP,TardósJD(2008)LargescaleSLAMbuildingconditionallyindependentlocalmaps:ansRobot24(5):1094–1106PollefeysM,VanL,VergauwenMetal(2004)mputVis59(3):207–232PrettoA,MenegattiE,PagelloE(2007):IEEE-RASinternationalconferenceonhumanoidrobots,pp532–538PupilliM,CalwayA(2006):ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognition,vol1,pp1244–1249RaguramR,FrahmJ,PollefeysM(2008)Acomparativeanalysisof:ProceedingsoftheEuropeanconferenceoncomputervision,pp500–513Rawseeds(2012):///rs/d06March2012RibasD,RidaoP,TardósJDetal(2008)Robot25(11):898–921RostenE,DrummondT(2006):ProceedingsoftheEuropeanconferenceoncomputervision,pp430–443RubleeE,RabaudV,KonoligeK,BradskiG(2011)ORB:aneffi:ProceedingsoftheIEEEinternationalconferenceoncomputervisionScaramuzza(2011)OcamCalibtoolbox::///site/scarabotix/d06March2012ScaramuzzaD,SiegwartR(2008)AppearanceguideansRobot24(5):1015–1026SeS,LoweD,LittleJ(2002)MobilerobotlocalizatbotRes21(8):735–758SeS,LoweD,LittleJ(2005)ansRobot21(3):364–375SáezJ,EscolanoF(2006):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp1548–1555SanromáG,AlquézarR,SerratosaF(2010)GraphmatchingusingSIFTdescriptors—:13thjointIAPRinternationalworkshoponstructural,syntacticandstatisticalpatternrecognition,pp254–263SilpaC,HartleyR(2008):ProceedingsoftheIEEEconferenceoncomputervisionandpatternrecognitionSinhaS,FrahmJ,PollefeysM,GencY(2006):WorkshoponedgecomputingusingnewcommodityarchitecturesSivicJ,ZissermanA(2003)Videogoogle::Proceed-ingsoftheIEEEinternationalconferenceoncomputervisionSimpsonR,CullipJ,RevellJ(2012):///misc/BAE_RSJCJR_d06March2012Smith(2012):///NewCollegeData/.Ac-cesed06March2012SmithR,SelfM,CheesemanP(1990):er,NewYork,pp167–193,ISBN:0-387-97240-4SmithM,BaldwinI,ChurchillWetal(2009)botRes28(5):595–599SolàJ(2007)Multi-cameraVSLAM::ProceedingsoftheIEEEinternationalconferenceonintelligentrobotsandsystems,workshoponvisualSLAMStederB,GrisettiG,StachnissCetal(2008)VisualSLAMforflansRobot24(5):1088–1093Sturm(2012):///data/datasets/d06March2012SturmJ,MagnenatS,etal(2011):ProceedingsoftheRGB-Dworkshoponadvancedreasoningwithdepthcamerasatrobotics:scienceandsystemsconference123

Visualsimultaneouslocalizationandmapping81StrasdatH,MontielJ,DavisonA(2010a)eedingofrobotics:scienceandsystemsStrasdatH,MontielJ,DavisonA(2010b)Real-timemonocularSLAM:whyfilter?.In:ProceedingsoftheIEEEinternationalconferenceonroboticsandautomationSvoboda(2011):///~svoboda/SelfCal/cesed06March2012TardósJD,NeiraJ,NewmanPetal(2002)botRes21:311–330TaylorS,DrummondT(2009):ProceedingsoftheBritishmachinevisionconferenceThrunS(2002)Roboticmapping:ingartificialintelligenceinthenewmillennium,ISBN:1-55860-811-7ThrunS(2003):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,vol3,pp4270–4275ThrunS,LeonardJ(2008)erHandbookofRobotics;Siciliano,KhatibEditors,ISBN:978-3-540-23957-4,pp871–886ThrunS,KollerD,GhahramaniZ,etal(2002)Simultaneousmappingandlocalizationwithsparseextendedinformationfilters:calReportCMU-CS-02-112,CarnegieMellonThrunS,MontemerloM,DahlkampHetal(2005a)Stanley:Robot23(9):661–692ThrunS,BurgardW,FoxD,(2005b)Press,NewYork,ISBN:ThrunS,MontemerloM,AronA(2006):Proceedingsofrobotics:scienceandsystemsTirillyP,ClaveauV,GrosP(2010):Proceedingsoftheinternationalconferenceonmultimediainformationretrieval,pp323–333TriggsB,MclauchlanP,HartleyR,FitzgibbonA(1999)Bundleadjustment—:Pro-ceedingsoftheinternationalworkshoponvisionalgorithms:theoryandpractice,pp298–375TuytelaarsT,MikolajczykK(2008)Localinvariantfeaturedetectors:rendsComputGraphVisTuytelaarsT,Van-GoolL(2004)MatchingwidelyseparatedviewsbasedonaffimputVis59(1):61–85VidalT,BrysonM,SukkariehS,etal(2007):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp4114–4119VidalT,BergerC,SolaJ,LacroixS(2011)LargescalemultiplerobotutonomSyst,pp654–674WangC,ThorpeCh,ThrunSetal(2007)Simultaneouslocalization,botRes26(9):889–916WangsiripitakS,MurrayD(2009):ProceedingsoftheIEEEinternationalconferenceonroboticsandautomation,pp375–380WilliamsB(2009),thesis,OxfordUni-versity,EnglandWilliamsB,KleinG,ReidI(2007):ProceedingsoftheIEEEinternationalconferenceoncomputervisionWilliamsB,CumminsM,NeiraJ,NewmanP,ReidI,TardósJD(2009)utonomSyst57(12):1188–1197Willson(1995):///~rgw/d06March2012YilmazA,JavedO,ShahM(2006)Objecttracking:putSurv38(4):1–45ZhangZ(2000)AflansPatternAnalMachIntell22(11):1330–1334ZhangW,KoseckaJ(2006):Proceedingsofthethirdinternationalsymposiumon3ddataprocessing,visualization,andtransmissionZhangZ,DericheR,FaugerasO,LuongQ(1994)ArobusttechniqueformatchingtwoulvolumeonComputerVision78(1):87–119ZhangH,LiB,YangD(2010):ProceedingsoftheIEEEinternationalconferenceonintelligentrobotsandsystems,pp2071–2076123