A framework for scalable vision-only navigation

ˇSiniˇsaSegvi´c,AnthonyRemazeilles,AlbertDiosiandFran¸coisChaumette

INRIA/IRISA,CampusdeBeaulieu,F-35042RennesCedex,France

Abstract.Thispaperpresentsamonocularvisionframeworkenablingfeature-orientedappearance-basednavigationinlargeoutdoorenviron-mentscontainingothermovingobjects.Theframeworkisbasedonahybridtopological-geometricalenvironmentrepresentation,constructedfromalearningsequenceacquiredduringarobotmotionunderhu-mancontrol.Theframeworkachievesthedesirednavigationfunctional-itywithoutrequiringaglobalgeometricalconsistencyoftheunderlyingenvironmentrepresentation.Themainadvantageswithrespecttocon-ventionalalternativesareunlimitedscalability,real-timemappingandeffortlessdealingwithinterconnectedenvironmentsoncetheloopshavebeenproperlydetected.Theframeworkhasbeenvalidatedindemanding,clutteredandinterconnectedenvironments,underdifferentimagingcon-ditions.Theexperimentshavebeenperformedonmanylongsequencesacquiredfrommovingcars,aswellasinreal-timelarge-scalenavigationtrialsrelyingexclusivelyonasingleperspectivecamera.Theobtainedresultsimplythatagloballyconsistentgeometricenvironmentmodelisnotmandatoryforsuccessfulvision-basedoutdoornavigation.

1Introduction

Thedesignofanautonomousmobilerobotrequiresestablishingacloserela-tionbetweentheperceivedenvironmentandthecommandssenttothelow-levelcontroller.Thisnecessitatescomplexspatialreasoningrelyingonsomekindofin-ternalenvironmentrepresentation[1].Inthemainstreammodel-basedapproach,amonolithicenvironment-centredrepresentationisusedtostorethelandmarksandthedescriptionsofthecorrespondingimagefeatures.Theconsideredfea-turesareusuallygeometricprimitives,whiletheirpositionsareexpressedincoordinatesofthecommonenvironment-wideframe[2,3].Duringthenaviga-tion,thedetectedfeaturesareassociatedwiththeelementsofthemodel,inordertolocalizetherobot,andtolocatepreviouslyunobservedmodelelements.However,thesuccessofsuchapproachdependsdirectlyontheaccuracyoftheunderlyingmodel.Thisposesastrongassumptionwhichimpairsthescalabilityand,dependingontheinput,maynotbeattainableatall.

Thealternativeappearance-basedapproachemploysasensor-centredrepre-sentationoftheenvironment,whichisusuallyamultidimensionalarrayofsensorreadings.Inthecontextofcomputervision,therepresentationincludesasetof

⋆

ThisworkhasbeensupportedbytheFrenchnationalprojectPreditMobivip,bytheprojectRobeaBodega,andbytheEuropeanMCIIFprojectAViCMaL.

key-imageswhichareacquiredduringalearningstageandorganizedwithinagraph[4].Nodesofthegraphcorrespondtokey-images,whilethearcslinktheimagescontainingarequirednumberofcommonlandmarks.ThisisillustratedinFigure1.Thenavigationbetweentwoneighbouringnodesisperformedusing

(a)(b)

Fig.1.Appearance-basednavigation:thesketchofanavigationtask(a),andthesetoffirsteightimagesfromtheenvironmentrepresentationformingalineargraph(b).Notethatthegraphhasbeenconstructedautomatically,asdescribedin3.1.

welldevelopedtechniquesfromthefieldofmobilerobotcontrol[5].Differenttypesoflandmarkrepresentationshavebeenconsideredintheliterature,fromtheintegralcontentsofaconsideredimage[6]andglobalimagedescriptors[4],tomoreconventionalpointfeaturessuchasHarriscorners[2,7].Weconsiderthelatterfeature-orientedapproach,inwhichthenextintermediatekey-imageisreachedbytrackingcommonfeaturesfromthepreviouskey-image.Here,itiscriticaltorecognizelandmarkswhichrecentlyenteredthefieldofview,orre-gainedanormalappearanceafterocclusion,motionblurorilluminationdistur-bances.Estimatinglocationsofinvisiblefeatures(featureprediction)isthereforeanessentialcapabilityinfeature-orientednavigation.

Wepresentanovelframeworkforscalablemappingandlocalization,enablingrobustappearance-basednavigationinlargeoutdoorenvironments.Theframe-workispresentedinabroaderframeofanenvisionedlong-termarchitecture,whilemoredetailscanbefoundin[8,9].Mappingandnavigationareconsideredseparatelyasaninterestingandnotcompletelysolvedproblem.Theemployedhierarchicalenvironmentrepresentation[4,10]featuresagraphofkey-imagesatthetop,andlocal3Dreconstructionsatthebottomlayer.Theglobaltopolog-icalrepresentationensuresanoutstandingscalability,limitsthepropagationofassociationerrorsandsimplifiesconsistencymanagementininterconnectedenvi-ronments.Ontheotherhand,thelocalgeometricmodelsenableaccuratefeaturepredictions.Westrivetoobtainthebestpredictionspossible,andfavourlocaloverglobalconsistencybyavoidingaglobalenvironmentmodel.Theresultsofdemandingrobotcontrolexperimentsdemonstratethatagloballyconsistent3Dreconstructionisnotrequiredforasuccessfullarge-scalevision-basednavigation.Anappearance-basednavigationapproachwithfeaturepredictionhasbeendescribedin[11].Simplifyingassumptionswithrespecttothemotionoftherobot

havebeenused,whilethepredictionwasimplementedusingintersectionofthetwoepipolarlines,whichhasimportantlimitations[12].Theneedforfeaturepredictionhasbeenalleviatedin[7],wherethepreviouslyunseenfeaturesfromthenextkey-imageareintroducedusingwide-baselinematching[13].Asimilarapproachhasbeenproposedinthecontextofomnidirectionalvision[14].Inthiscloselyrelatedwork,featurepredictionbasedonpointtransfer[12]hasbeenemployedtorecoverfromtrackingfailures,butnotforfeatureintroductionaswell.However,wide-baselinematching[14,7]ispronetoassociationerrorsduetoambiguouslandmarks.Inourexperiments,substantiallybetterfeatureintroductionhasbeenachievedbyexplotingthepointtransferpredictions.Incomparisonwithmodel-basednavigationapproachessuchastheonede-scribedin[3],ourapproachdoesnotrequireaglobalconsistency.Byposingweakerrequirements,weincreasetherobustnessofthemappingphase,likelyobtainbetterlocalconsistencies,cancloseloopsregardlessoftheextentoftheaccumulateddriftandhavebetterchancestosurvivecorrespondenceerrors.Notableadvanceshavebeenrecentlyachievedinmodel-basedSLAM[15].Nev-ertheless,currentimplementationshavelimitationswithrespecttothenumberofmappedpoints,sothatapriorlearningstepstillseemsanecessityinrealisticnavigationtasks.Ourapproachhasnoscalingproblems:experimentswith15000landmarkshavebeenperformedwithoutanyperformancedegradation.

Thepaperisorganizedasfollows.Theenvisionedarchitectureforvision-basednavigationisdescribedinSection2.ImplementationdetailsofthecurrentimplementationaredescribedinSection3.Section4providestheexperimentalresults,whiletheconclusionisgiveninSection5.

2Theenvisionedarchitecture

Thepresentedworkisanincrementalsteptowardsasystemforappearance-basednavigationininterconnectedstructuredenvironments,whichisalong-termresearchgoalinourlaboratory[16].Thedesiredautonomoussystemwouldbecapabletoautonomouslynavigateinpreviouslymappedenvironment,to-wardsagoalspecifedbyadesiredgoal-image.Thedevisedarchitectureassumesoperationinthreedistinctphases,asillustratedinFigure2(a).

Themappingphasecreatesatopological–geometricalenvironmentrepresen-tationfromalearningsequenceacquiredduringarobotmotionunderahumancontrol.Thekey-imagesareselectedfromthelearningsequenceandorganizedwithinagraphinwhichthearcsaredefinedbetweennodessharingacertainnumberofcommonfeatures.Thematchingfeaturesintheneighbouringnodesareusedtorecoveralocal3Dreconstruction,whichisassignedtothecorre-spondingarc.Thesefeaturesareconsideredfortrackingwhenevertherobotarrivesclosetotheviewpointsfromwhichthetwokey-imageswereacquired.Thetaskpreparationphaseisperformedafterthenavigationtaskhasbeenpresentedtothenavigationsystemintheformofadesiredgoal-image,asillus-tratedinFigure2(b).Theinitialtopologicallocalizationcorrespondstolocatingthecurrentandthedesiredimagesintheenvironmentgraphbycontent-based

(a)(b)

Fig.2.Theenvisionedarchitectureforfeature-orientedappearance-basednavigation(a),Theentrieswhichareconsideredandimplementedinthisworkaretypesetinbold.Theillustrationofthethreeproceduresfromthetaskpreparationphase(b).

imageretrieval[16].Thetwoimagesareconsequentlyinjectedintothegraphusingthecorrespondencesobtainedbywide-baselinematching.Finally,theop-timaltopologicalpathisdeterminedusingashortestpathalgorithm.Thenodesofthedeterminedpathdenoteintermediatemilestonesthroughwhichtherobotissupposedtonavigatetowardsthedesiredgoal.

Thenavigationphaseinvolvesavisualservoingprocessingloop[17],inwhichthepointfeaturesfromimagesacquiredinreal-timeareassociatedwiththeircounterpartsinthekey-images.Thus,twodistinctkindsoflocalizationarere-quired:(i)explicittopologicallocalization,and(ii)implicitfine-levellocalizationthroughthelocationsofthetrackedlandmarks.Topologicallocationcorrespondstothearcoftheenvironmentgraphincidenttothetwokey-imageshavingmostcontentincommonwiththecurrentimage.Itisextremelyimportanttomain-taininganaccuratetopologicallocationasthenavigationproceeds,sincethatdefinesthelandmarksconsideredforlocalization.Duringthemotion,thetrack-ingmayfailduetoocclusions,motionblur,illuminationeffectsornoise.Featurepredictionallowstodealwiththisproblemandresumethefeaturetrackingontheflywhileminimizingthechancesforcorrespondenceerrors.

3Scalablemappingandlocalization

InthebroadercontextpresentedinSection2,wemainlyaddressthemappingandthenavigationphase,whichhavebeenimplementedwithinthemappingandlocalizationcomponentsoftheframework.

Bothcomponentsrelyonfeaturetrackingandtwo-viewgeometry.Thede-visedmulti-scaledifferentialtrackerwithwarpcorrectionandcheckingprovidescorrespondenceswithfewoutliers.BadtracksareidentifiedbyathresholdRonRMSresidualbetweenthewarpedcurrentfeatureandthereferenceappearance.Theemployedwarpincludesisotropicscalingandaffinecontrastcompensation[18].Thetwo-viewgeometryisrecoveredinacalibratedcontextbyrandomsampling,withthefive-pointalgorithm[19]asthehypothesisgenerator.

Forsimplicity,theactualimplementationallowsonlylinearorcirculartopo-logicalrepresentations.Thisobviatestheneedforthelocalizationandplanningprocedures,whichwehaveaddressedpreviously[16].Theresultingimplementa-tionofthetaskpreparationphaseisdescribedalongthelocalizationcomponent.3.1

Themappingcomponent

Themappingcomponentconstructsalinearenvironmentgraphandannotatesitsnodesandarcswithprecomputedinformation.Thenodesofthegraphareformedbychoosingthesetofkey-imagesIi.Thesameindexingisusedforarcsaswell,bydefiningthatarciconnectsnodesi−1andi(cf.Figure3).Ifthegraphiscircular,arc0connectsthelastnoden−1withthenode0.EachnodeisassignedthesetXioffeaturesfromIi,denotedbydistinctiveidentifiers.EacharcisassignedanarrayofidentifiersMidenotinglandmarkslocatedinthetwoincidentkey-images,andannotatedwiththerecoveredtwo-viewgeometriesWi.

Fig.3.Thelinearenvironmentgraph.NodescontainimagesIi,extractedfeaturesXiandscalefactorssi.ArcscontainmatcharraysMiandthetwo-viewgeometriesWi.ThefigurealsoshowsthecurrentimageIt,whichisconsideredin3.2.Ifthetopologicallocationisi+1,thefeaturesconsideredfortrackingbelongtoWi,Wi+1andWi+2.

TheelementsofWiincludemotionparametersRiandti(|ti|=1),andmet-riclandmarkreconstructionsQi.Thetwo-viewgeometriesWiaredeliberatelynotputintoanenvironment-wideframe,sincecontradictingscalesequencescanbeobtainedalongthegraphcycles.Thescaleratiosibetweentheincidentge-ometriesWiandWi+1isthereforestoredinthecommonnodei.NeighbouringpairsofgeometriesWi+1andWi+2needtohavesomefeaturesincommon,Mi+1∩Mi+2=∅,inordertoenablethetransferoffeaturesfromthenexttwokey-images(Ii+1,Ii+2)onthepath(cf.3.2).Quantitatively,aparticulararcofthemapcanbeevaluatedbythenumberofcorrespondences|Mi|andtheestimateofthereprojectionerrorσ(Wi)[12].Differentmapsofthesameenvi-ronmentcanbeevaluatedbythetotalcountofarcsinthegraph|{Mi}|,andbytheparametersoftheindividualarcs|Mi|andσ(Wi).Itisusuallyfavourabletohavelessarcs,sincethatensuresasmallerdifferenceinlinesofsightbetweentherelevantkey-imagesandtheimagesacquiredduringnavigation.

Thedevisedmappingsolutionusesthetrackertofindthestablestpointfea-turesinagivensubrangeofthelearningsequence.ThetrackerisinitiatedwithallHarrispointsintheinitialframeofthesubrange.Thefeaturesaretrackeduntilthereconstructionerrorbetweenthefirstandthecurrentframeofthesub-rangerisesaboveapredefinedthresholdσ.Thenthecurrentframeisdiscarded,whilethepreviousframeisregisteredasthenewnodeofthegraph,andthewholeprocedureisrepeatedfromthere.Thisissimilartovisualodometry[20],exceptthatweemploylargerfeaturewindowsandmoreinvolvedtracking[18]inordertoachievemoredistinctivefeaturesandlongerfeaturelifetimes.Toensureaminimumnumberoffeatureswithinanarcofthegraph,anewnodeisforcedwhentheabsolutenumberoftrackedpointsfallsbelown.

Theabovematchingschemecanbecomplementedbywide-baselinematching[13]whentherearediscontinuitiesinthelearningsequencecausedbyalargemovingobject,ora“framegap”duetobadacquisition.Sucheventsarereflectedbyageneraltrackingfailureinthesecondframeofanewsubrange.

Wide-baselinematchingisalsousefulforconnectingacycleintheenviron-mentgraph.Totestwhetherthelearningsequenceisacquiredalongacircularphysicalpath,thefirstandthelastkey-imagearesubjectedtomatching:acir-culargraphiscreatedonsuccess,andasimplelineargraphotherwise.Incaseofamonolithicgeometricmodel,theloopclosingprocesswouldneedtobefol-lowedbyasophisticatedmapcorrectionprocedure,inordertotrytocorrecttheaccumulatederror.Duetotopologicalrepresentationatthetop-level,thisoperationproceedsreliablyandsmoothly,regardlessoftheextentofthedrift.3.2

Thelocalizationcomponent

Intheproposedframework,thetrackedfeaturesbelongeithertotheactualarc(topologicallocation),orthetwoneighbouringarcsasillustratedinFig-ure3.Wefocusonon-linefacetsofthelocalizationproblem:(i)robustfine-levellocalizationrelyingonfeatureprediction,and(ii)maintenanceofthetopologi-callocationasthenavigationproceeds.Nevertheless,forcompleteness,wefirstpresentaminimalisticinitializationprocedureusedintheexperiments.TheinitializationprocedureThenavigationprogramisstartedwiththefollowingparameters:(i)mapoftheenvironment,(ii)initialtopologicallocationoftherobot(indexoftheactualarc),and(iii)calibrationparametersoftheattachedcamera.Thisisimmediatelyfollowedbywide-baselinematching[13]ofthecurrentimagewiththetwokey-imagesincidenttotheactualarc.Fromtheobtainedcorrespondences,theposeisrecoveredintheactualgeometricframe,allowingtoprojectthemappedfeaturesandtobootstraptheprocessingloop.FeaturepredictionandtrackingresumptionThepointfeaturestrackedinthecurrentimageItareemployedtoestimatethecurrenttwo-viewgeometriesWt:i(Ii,It)andWt:i+1(Ii+1,It)towardsthetwoincidentkey-images,usingthesameprocedureasin3.1.Anaccurateandefficientrecoveryofthethree-view

geometryisdevisedbyadecomposedapproachrelatedto[21].Theapproachreliesonrecoveringtherelativescalebetweenthetwoindependentlyrecoveredmetricframes,byenforcingtheconsistencyofthecommonstructure.Themainadvantageswithrespecttothe“goldenstandard”method[12]aretheutilizationofpairwisecorrespondences(whichisofparticularinterestforforwardmotion),andreal-timeperformance.Thus,thethree-viewgeometry(It,Ii,Ii+1)isrecov-eredbyadjustingtheprecomputedtwo-viewgeometryWi+1towardsthemoreaccurate(intermsofreprojectionerror)ofWt:iandWt:i+1(seeFigure3).Thegeometry(It,Ii+1,Ii+2)isrecoveredfromWi+2andWt:i+1,while(It,Ii−1,Ii)isrecoveredfromWiandWt:i.Currentimagelocationsoflandmarksmappedintheactualarci+1arepredictedbythegeometry(It,Ii,Ii+1).Landmarksfromthepreviousarciandthenextarci+2aretransferredbygeometries(It,Ii−1,Ii)and(It,Ii+1,Ii+2),respectively.

Pointtransferisperformedonlyiftheestimatedreprojectionerroroftheemployedcurrentgeometryiswithinthesafetylimits.Thepredictionsarerefined(orrejected)byminimizingtheresidualbetweenthewarpedcurrentfeatureandthereferenceappearance.Asintracking,theresultisacceptediftheprocedureconvergesnearthepredictedlocation,withanacceptableresidual.Ananalogousprocedureisemployedtochecktheconsistencyofthetrackedfeatures,whichoccasionally“jump”totheoccludingforeground.

MaintainingthetopologicallocationMaintainingacorrecttopologicallo-cationiscriticalinsharpturnswherethetrackedfeaturesdiequicklyduetothecontactwiththeimageborder.AnincorrecttopologicallocationimpliesasuboptimalintroductionofnewfeaturesandmaybefollowedbyafailureduetoinsufficientfeaturesforcalculatingWt:iandWt:i+1.Bestresultshavebeenob-tainedusingageometriccriterion:atransitionistakenwhenthereconstructedcameralocationovertakesthenextkey-imageIi+1.Thiscanbeexpressedas󰀋−Ri+1⊤·ti+1,tt:i+1󰀌<0.Thedecisionisbasedonthegeometryrelatedtothenextkey-imageWt:i+1,whichisgeometricallyclosertothehypothesizedtransition.Backwardstransitionscanbeanalogouslydefinedinordertosupportreversemotionoftherobot.Aftereachtransition,thereferenceappearances(references)areredefinedforallrelevantfeaturesinordertoachievebettertracking.Foraforwardtransition,referencesforthefeaturesfromtheactualgeometryWi+1aretakenfromIi+1,whilethereferencesforthefeaturesfromWi+2aretakenfromIi+2(cf.Figure3).Previouslytrackedpointsfromgeome-triesWi+1andWi+2areinstantlyresumedusingtheirpreviouspositionsandnewreferences,whilethefeaturesfromWiarediscontinued.

4Experimentalresults

Theperformedexperimentsincludemapping,off-linelocalization,andnaviga-tion(real-timelocalizationandcontrol).Off-linesequencesandreal-timeimageshavebeenacquiredoftheroboticcarCycabunderhumanandautomaticcontrol.

4.1Mappingexperiments

Wefirstpresentquantitativemappingresultsobtainedonthelearningsequenceifsic5,correspondingtothereverseofthepathshowninFigure1(a).Theanalysiswasperformedintermsofthegeometricmodelparametersintroducedin3.1:(i)|Mi|(ii)σ(Wi),and(iii)|{Mi}|.Figure4(a)showsthevariationof|Mi|andσ(Wi)alongthearcsofthecreatedenvironmentgraph.

Aqualitativeillustrationoftheinter-nodedistance(and|{Mi}|)ispresentedinFigure4(b)asthesequenceofrecoveredkey-imageposes(commonglobalscalehasbeenenforcedforvisualisationpurposes).Thefiguresuggeststhatthemap-pingcomponentadaptsthedensityofkey-imagestotheinherentdifficultyofthescene.Thedensenodes7-14correspondtothefirstdifficultmomentofthelearningsequence:approachingthetraversebuildingandpassingunderneathit.Nodes20to25correspondtothesharpleftturn,whilepassingveryclosetoabuilding.Thehardconditionspersistedaftertheturnduetolargefeature-lessbushesandareflectingglasssurface:thisisreflectedindensenodes26-28,cf.Figure4(c).Thenumberoffeaturesinarc20isexceptionallyhigh,whiletheincidentnodes19and20areveryclose.Theanomalyisduealargeframegapcausingmostfeaturetrackstoterminateinstantly.Wide-baselinematchingsucceededtorelatethekey-image19anditsimmediatesuccessorwhichconse-quentlybecamekey-image20.Theerrorpeakinarc21iscausedbyananothergapwhichhasbeensuccessfullybridgedbythetrackeralone.

10 8 6 4 2 0 200 100 50 0 5 10 15index

20 25 0npointsstdevnpoints 1502827262524232221181920stdev01234567891011121314151617(a)(b)

(c)

Fig.4.Themappingresultsonthesequenceifsic5containing1900imagesacquiredalonga150m

path:countsofmappedpointfeatures|Mi|andreprojectionerrorsσ(Wi)(a),thereconstructedsequenceofcameraposes(b),andthe28resultingkey-images(c).

Thesecondgroupofexperiments,concernsthelearningsequencelooptakenalongacircularpathofapproximately50m.Weinvestigatethesensitivityofthemappingalgorithmwithrespecttothethreemainparametersdescribedin3.1:(i)minimumcountoffeaturesn,(ii)maximumallowedreprojectionerrorσ,and(iii)theRMSresidualthresholdR.Thereconstructionsobtainedfor4

differentparametertriplesarepresentedinFigure5.Thepresenceofnode0’indicatesthatthecycleatthetopologicallevelhasbeensuccessfullyclosedbywide-baselinematching.Ideally,nodes0’and0shouldbeveryclose;theextentofthedistanceindicatesthemagnitudeoftheerrorduetotheaccumulateddrift.Reasonableandusablerepresentationshavebeenobtainedinallcases,despitethesmoothplanarsurfacesandvegetationwhicharevisibleinFigure5(bottom).Theexperimentsshowthatthereisadirectcouplingbetweenthenumberofarcs|{Mi}|andthenumberofmappedfeatures|Mi|.Thus,itisbeneficialtoseekthesmallest|{Mi}|ensuringacceptablevaluesforσ(Wi)and|Mi|.ThelastmapinFigure5(top-right)wasdeliberatelyconstructedusingsuboptimalparameters,toshowthatourapproachessentiallyworksevenincasesinwhichenforcingtheglobalconsistencyisdifficult.Thenavigationcansmoothlyproceeddespiteadiscontinuityintheglobalgeometricreconstruction,sincethelocalgeometriesare“elastically”gluedtogetherbythecontinuoustopologicalrepresentation.

260’770’00320’280’00

n=100,σ=1,R=4n=50,σ=2,R=6n=50,σ=4,R=6n=25,σ=2,R=6

Fig.5.Reconstructedposesobtainedonsequenceloop,fordifferentsetsofmappingparameters(top).Actualkey-imagesofthemapobtainedforn=50,σ=4,R=6(bottom).Thismapwillbeemployedinlocalizationexperiments.

4.2Localizationexperiments

Inthelocalizationexperiments,wemeasurequantitativesuccessinrecogniz-ingthemappedfeatures.TheresultsaresummarizedinFigure6,wherethecountsoftrackedfeaturesareplottedagainstthearcsoftheemployedmap.Wefirstpresenttheresultsofperformingthelocalizationontwonavigationsequencesobtainedforsimilarrobotmotionbutunderdifferentillumination.Figure6(a)showsthattheproposedfeaturepredictionschemeenableslargescaleappearance-basednavigation,asfaraspuregeometryisconcerned.Fig-ure6(b)showsthatusefulresultscanbeobtainedevenunderdifferentlightingconditions,whenthefeaturelossattimesexceed50%.

90 80 70 60 50 40 30 20 10Total pointsTracked maxTracked avg 0 5 10 15 20 25 90 80 70 60 50 40 30 20 10Total pointsTracked maxTracked avg 0 5 10 15 20 25 80 70 60 50 40 30 20 10 0Avg tracked 1st roundAvg tracked 2nd round 0 5 10 15 20 25(a)(b)(c)

Fig.6.Quantitativelocalizationresults:processingifsic5(a)andifsic1(b)onamapbuiltonifsic5,andusingthemapfromFigure5overtworoundsofloop(c).

Thecapabilityofthelocalizationcomponenttotraversecyclicmapswastestedonasequenceobtainedfortworoundsroughlyalongthesamecircularphysicalpath.Thisisaquitedifficultscenariosinceitrequirescontinuousandfastintroductionofnewfeaturesduetopersistentchangesofviewingdirection.Thefirstroundwasusedformapping(thisisthesequenceloop,discussedinFigure5),whilethelocalizationisperformedalongthecombinedsequence,in-volvingtwocompleterounds.Duringtheacquisition,therobotwasmanuallydrivensothatthetwotrajectoriesweremorethan1mapartatseveralocca-sionsduringtheexperiment.Nevertheless,thelocalizationwassuccessfulinbothrounds,assummarisedinFigure6(c).Allfeatureshavebeensuccessfullylocatedduringthefirstround,whiletheoutcomeinthesecondrounddependsontheextentofthedivergencebetweenthetwotrajectories.4.3

Navigationexperiments

Inthenavigationexperiments,theCycabwascontrolledinreal-timebyvisualservoing.Thesteeringangleψhasbeendeterminedfromaveragexcomponentsofthecurrentfeaturelocations(xt,yt)∈Xt,andtheircorrespondencesinthenextkey-image(x∗,y∗)∈Xi+1:ψ=−λ(xt−x∗),whereλ∈R+.Oneofthelarge-scalenavigationexperimentsinvolvedareferencepathofapproximately750m,offeringavarietyofdrivingconditionsincludingnarrowsections,slopesanddrivingunderabuilding.Anearlierversionoftheprogramhasbeenusedallowingacontrolfrequencyofabout1Hz.Thenavigationspeedwassetac-cordinglyto30cm/sinturns,andotherwise80cm/s.Themapwasbuiltonalearningsequencepreviouslyacquiredundermanualcontrol.Therobotsmoothlycompletedthepathdespiteapassingcaroccludingthemajorityofthefeatures,asshowninFigure7.Severalsimilarencounterswithpedestrianshavebeenprocessedinagracefulmannertoo.Thesystemsucceededtomapfeatures(andsubsequentlytofindthem)inseeminglyfeaturelessareaswheretheroadandthegrassoccupiedmostofthefieldofview.Theemployedenvironmentrepresenta-tionisnotveryaccuratefromtheglobalpointofview.Nevertheless,thesystemsucceedstoperformlargeautonomousdisplacements,whilealsobeingrobusttoothermovingobjects.Weconsiderthisasastrongindicationoftheforthcomingpotentialtowardsrealapplicationsofvision-basedautonomousvehicles.

Fig.7.Imagesobtainedduringtheexecutionofanavigationexperiment.Thepointsusedfornavigationre-appearafterbeingoccludedanddisoccludedbyamovingcar.

5Conclusion

Thepaperdescribedanovelframeworkforlarge-scalemappingandlocalization,basedonpointfeaturesmappedduringalearningsession.Thepurposeoftheframeworkistoprovide2Dimagemeasurementsforappearance-basednaviga-tion.Thetrackingoftemporarilyoccludedandpreviouslyunseenfeaturescanbe(re-)startedon-the-flyduetofeaturepredictionbasedonpointtransfer.2Dnavigationand3Dpredictionsmoothlyinteractthroughahierarchicalenviron-mentrepresentation.Thenavigationisconcernedwiththeuppertopologicallevel,whilethepredictionisperformedwithinthelower,geometricallevel.

Incomparisonwiththemainstreamapproachinvolvingamonolithicgeomet-ricrepresentation,theproposedframeworkenablesrobustlarge-scalenavigationwithoutrequiringageometricallyconsistentglobalviewoftheenvironment.Thispointhasbeendemonstratedintheexperimentwithacircularpath,inwhichthenavigationbridgesthefirstandthelastnodeofthetopologyregardlessoftheextentoftheaccumulatederrorintheglobal3Dreconstruction.Thus,theproposedframeworkisapplicableevenininterconnectedenvironments,whereaglobalconsistencymaybedifficulttoenforce.

Thelocalizationcomponentrequiresimagingandnavigationconditionssuchthatenoughofthemappedlandmarkshaverecognizableappearancesintheacquiredcurrentimages.Theperformedexperimentssuggestthatthiscanbeachievedevenwithverysmallimages,formoderate-to-largechangesinimagingconditions.Thedifficultsituationsincludefeaturelessareas(smoothbuildings,vegetation,pavement),photometricvariations(strongshadowsandreflections),andthedeviationsfromthereferencepathusedtoperformthemapping,duetocontrolerrorsorobstacleavoidance.

Inthecurrentimplementation,themappingandlocalizationthroughputon320×240gray–levelimagesis5Hzand7Hz,respectively,usinganotebookcomputerwithaCPUroughlyequivalenttoaPentium4at2GHz.Mostoftheprocessingtimeisspentwithinthepointfeaturetracker,whichusesathree-levelimagepyramidinordertobeabletodealwithlargefeaturemotioninturns.Thecomputationalcomplexityisanimportantissue:withmoreprocessingpowerwecoulddealwithlargerimagesandmapmorefeatures,whichwouldresultinevengreaterrobustness.Nevertheless,encouragingresultsinreal-timeautonomousrobotcontrolhavebeenobtainedevenonverysmallimages.Inthelightoffutureincreaseinprocessingperformance,thissuggeststhatthetimeofvision-basedautonomoustransportationsystemsisgettingclose.

References

1.DeSouza,G.N.,Kak,A.C.:Visionformobilerobotnavigation:asurvey.IEEETrans.PAMI24(2)(2002)

2.Burschka,D.,Hager,G.D.:Vision-basedcontrolofmobilerobots.In:Proc.ofICRA,Seoul,SouthKorea(2001)1707–1713

3.Royer,E.,Lhuillier,M.,Dhome,M.,Chateau,T.:Localizationinurbanenvi-ronments:MonocularvisioncomparedtoadifferentialGPSsensor.In:Proc.ofCVPR.Volume2.,Washington,DC(2005)114–121

4.Gaspar,J.,Santos-Victor,J.:Vision-basednavigationandenvironmentalrepresen-tationswithanomni-directionnalcamera.IEEETrans.RA16(6)(2000)890–8985.Samson,C.:Controlofchainedsystems:applicationtopathfollowingandtime-varyingpointstabilization.IEEETrans.AC40(1)(1995)64–77

6.Matsumoto,Y.,Inaba,M.,Inoue,H.:Explorationandnavigationincorridorenvironmentbasedonomni-viewsequence.In:Proc.ofIROS,Takamatsu,Japan(2000)1505–1510

7.Chen,Z.,Birchfield,S.T.:Qualitativevision-basedmobilerobotnavigation.In:Proc.ofICRA,Orlando,Florida(2006)2686–2692ˇ8.Segvi´c,S.,Remazeilles,A.,Diosi,A.,Chaumette,F.:Largescalevisionbasednavi-gationwithoutanaccurateglobalreconstruction.In:Proc.ofCVPR,Minneapolis,Minnesota(2007)

ˇ9.Di´osi,A.,Remazeilles,A.,Segvi´c,S.,Chaumette,F.:Experimentalevaluationof

anurbanvisualpathfollowingframework.In:Proc.ofIFACSymposiumonIAV,Toulouse,France(2007)

10.Bosse,M.,Newman,P.,Leonard,J.,Soika,M.,Feiten,W.,Teller,S.:AnATLAS

frameworkforscalablemapping.In:Proc.ofICRA,Taiwan(2003)1899–190611.Hager,G.D.,Kriegman,D.J.,Georghiades,A.S.,Ben-Shalar,O.:Towarddomain-independentnavigation:dynamicvisionandcontrol.In:Proc.ofICDC,Tampa,Florida(1998)1040–1046

12.Hartley,R.I.,Zisserman,A.:MultipleViewGeometryinComputerVision.Cam-bridgeUniversityPress,Cambridge,UK(2004)

13.Mikolajczyk,K.,Schmid,C.:Scaleandaffineinvariantinterestpointdetectors.

Int.J.Comput.Vis.60(1)(2004)63–8614.Goedem´e,T.,Nuttin,M.,Tuytelaars,T.,Gool,L.V.:Omnidirectionalvisionbased

topologicalnavigation.Int.J.Comput.Vis.(2007)toappear.

15.Davison,A.:Real-timesimultaneouslocalisationandmappingwithasinglecam-era.In:Proc.ofICCV,Nice,France(2003)1403–1410

16.Remazeilles,A.,Chaumette,F.,Gros,P.:3Dnavigationbasedonavisualmemory.

In:Proc.ofICRA,Orlando,Florida(2006)2719–2725

17.Chaumette,F.,Hutchinson,S.:Visualservocontrol,partI:Basicapproaches.

IEEERoboticsandAutomationmagazine13(4)(2006)82–90ˇ18.Segvi´c,S.,Remazeilles,A.,Chaumette,F.:Enhancingthepointfeaturetrackerbyadaptivemodellingofthefeaturesupport.In:Proc.ofECCV,Graz,Austria(2006)112–12419.Nist´er,D.:Anefficientsolutiontothefive-pointrelativeposeproblem.IEEE

Trans.PAMI26(6)(2004)756–77020.Nist´er,D.,Naroditsky,O.,Bergen,J.:Visualodometry.In:Proc.ofCVPR,Wash-ington,DC(2004)652–659

21.Lourakis,M.,Argyros,A.:Fasttrifocaltensorestimationusingvirtualparallax.

In:Proc.ofICIP,Genoa,Italy(2005)169–172