The wide baseline stereo problem ,i.e.the problem of establishing correspondences between apair of images taken from different view points is studied.A new set of image elements that are put into correspondence,the so called extremal regions,is introduced.Extremal regions possess highly desirable properties

ImageandVisionComputing22(2004)761–767

/locate/imavis

Robustwide-baselinestereofrommaximallystableextremalregions

J.Matasa,b,*,O.Chuma,M.Urbana,T.Pajdlaa

a

´m13CZ12135,CzechRepublicDepartmentofCybernetics,CenterforMachinePerception,CTUPrague,Karlovona

b

CVSSP,UniversityofSurrey,GuildfordGU27XH,UK

Received12March2003;receivedinrevisedform11February2004;accepted12February2004

Abstract

Thewide-baselinestereoproblem,i.e.theproblemofestablishingcorrespondencesbetweenapairofimagestakenfromdifferentviewpointsisstudied.

Anewsetofimageelementsthatareputintocorrespondence,thesocalledextremalregions,isintroduced.Extremalregionspossesshighlydesirableproperties:thesetisclosedunder(1)continuous(andthusprojective)transformationofimagecoordinatesand(2)monotonictransformationofimageintensities.Anef cient(nearlinearcomplexity)andpracticallyfastdetectionalgorithm(nearframerate)ispresentedforanaf nelyinvariantstablesubsetofextremalregions,themaximallystableextremalregions(MSER).

Anewrobustsimilaritymeasureforestablishingtentativecorrespondencesisproposed.Therobustnessensuresthatinvariantsfrommultiplemeasurementregions(regionsobtainedbyinvariantconstructionsfromextremalregions),somethataresigni cantlylarger(andhencediscriminative)thantheMSERs,maybeusedtoestablishtentativecorrespondences.

ThehighutilityofMSERs,multiplemeasurementregionsandtherobustmetricisdemonstratedinwide-baselineexperimentsonimagepairsfrombothindoorandoutdoorscenes.Signi cantchangeofscale(3.5£),illuminationconditions,out-of-planerotation,occlusion,locallyanisotropicscalechangeand3Dtranslationoftheviewpointareallpresentinthetestproblems.Goodestimatesofepipolargeometry(averagedistancefromcorrespondingpointstotheepipolarlinebelow0.09oftheinter-pixeldistance)areobtained.q2004ElsevierB.V.Allrightsreserved.

Keywords:Wide-baselinestereo;Distinguishedregions;Maximallystableextremalregions;MSER;Robustmetric

1.Introduction

Findingreliablecorrespondencesintwoimagesofascenetakenfromarbitraryviewpointsviewedwithpossiblydifferentcamerasandindifferentilluminationconditionsisadif cultandcriticalsteptowardsfullyautomaticreconstructionof3Dscenes[5].Acrucialissueisthechoiceofelementswhosecorrespondenceissought.Inthewide-baselineset-up,localimagedeformationscannotberealisticallyapproximatedbytranslationortranslationwithrotationandafullaf nemodelisrequired.Correspondencecannotbethereforeestablishedbycomparingregionsofa xed(Euclidean)shapelikerectanglesorcirclessincetheirshapeisnotpreservedunderaf netransformation.

*Correspondingauthor.Address:DepartmentofCybernetics,Centerfor

´m13CZ12135,CzechMachinePerception,CTUPrague,Karlovona

Republic.Tel.:þ420-2-24357212;fax:þ420-2-24357385.

E-mailaddresses:matas@cmp.felk.cvut.cz(J.Matas);chum@cmp.felk.cvut.cz(O.Chum).

0262-8856/$-seefrontmatterq2004ElsevierB.V.Allrightsreserved.

doi:10.1016/j.imavis.2004.02.006

Inmostimagesthereareregionsthatcanbedetectedwithhighrepeatabilitysincetheypossessomedistinguish-ing,invariantandstableproperty.Wearguethatsuchregionsof,ingeneral,data-dependentshape,calleddistinguishedregions(DRs)inthepaper,mayserveastheelementstobeputintocorrespondenceeitherinstereomatchingorobjectrecognition.

The rstcontributionistheintroductionofanewsetofDRs,thesocalledextremalregions.Extremalregionshavetwodesirableproperties.Thesetisclosedundercontinuousone-to-one(andthusperspective)transformationofimagecoordinatesand,secondly,itisclosedundermonotonictransformationofimageintensities.Anef cient(nearlinearcomplexity)andpracticallyfastdetectionalgorithmispresentedforanaf nelyinvariantstablesubsetofextremalregions,themaximallystableextremalregions(MSER).RobustnessofaparticulartypeofDRdependsontheimagedataandmustbetestedexperimentally.Successfulwide-baselineexperimentsonindoorandoutdoordatasetspresentedinSection4demonstratethepotentialofMSERs.