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

J.Matasetal./ImageandVisionComputing22(2004)761–767

763

Table1

De nitionsusedinSection2

ImageIisamappingI:D,Z2!S:Extremalregionsarewellde nedonimagesif:

1.Sistotallyordered,i.e.re exive,antisymmetricandtransitivebinaryrelation#exists.InthispaperonlyS¼{0;1;…;255}isconsidered,butextremalregionscanbede nedon,e.g.real-valuedimagesðS¼RÞ2.Anadjacency(neighbourhood)relationA,D£Disde ned.InthispaperP4-neighbourhoodsareused,i.e.p;q[DareadjacentðpAqÞiffd

i¼1lpi2qil#1

RegionQisacontiguoussubsetofD;i.e.foreachp;q[Qthereisasequencep;a1;a2;…;an;qandpAa1;aiAaiþ1;anAq

(Outer)RegionBoundary Q¼{q[D\Q:’p[Q:qAp};i.e.theboundary QofQisthesetofpixelsbeingadjacenttoatleastonepixelofQbutnotbelongingtoQ

ExtremalRegionQ,Disaregionsuchthatforallp[Q;q[ Q:IðpÞ.IðqÞ(maximumintensityregion)orIðpÞ,IðqÞ(minimumintensityregion)

MaximallyStableExtremalRegion(MSER).LetQ:1Extremal;…;Qi21region;Qi;…Qbeasequenceofnestedextremalregions,i.e.Qi,Qiþ1ipismaximallystableiffqðiÞ¼lQiþD\Qi2Dl=lQilhasalocalminimumatip(l·ldenotescardinality).D[Sisaparameterofthe

method

Stability,sinceonlyextremalregionswhosesupportisvirtuallyunchangedoverarangeofthresholdsisselected.

Multi-scaledetection.Sincenosmoothingisinvolved,bothvery neandverylargestructurearedetected. ThesetofallextremalregionscanbeenumeratedinOðnloglognÞ;wherenisthenumberofpixelsintheimage.Enumerationofextremalregionsproceedsasfollows.First,pixelsaresortedbyintensity.ThecomputationalcomplexityofthisstepisOðnÞifthecardinalityofthesetSofimageintensitiesissmall,e.g.thetypical{0;…;255};sincethesortcanbeimplementedasBINSORT[17].Aftersorting,pixelsareplacedintheimage(eitherindecreasingorincreasingorder)andthelistofconnectedcomponentsandtheirareasismaintainedusingtheef cientunion- ndalgorithm[17].Thecomplexityofourunion- ndimplementationisOðnloglognÞ;i.e.almostlinear1.Importantly,thealgorithmisveryfastinpractice.TheMSERdetectiontakesonly0.14sonaLinuxPCwiththeAthlonXP1600þprocessorforan530£350imageðn¼185;500Þ:

Theprocessproducesadatastructurestoringtheareaofeachconnectedcomponentasafunctionofintensity.Amergeoftwocomponentsisviewedasterminationofexistenceofthesmallercomponentandaninsertionofallpixelsofthesmallercomponentintothelargerone.Finally,intensitylevelsthatarelocalminimaoftherateofchangeoftheareafunctionareselectedasthresholdsproducingMSER.Intheoutput,eachMSERisrepresentedbyposition

1

Evenfaster(butmorecomplex)connectedcomponentalgorithmsexistwithOðnaðnÞÞcomplexity,whereaistheinverseAckermanfunction;aðnÞ#4forallpracticaln:

Fig.1.Bookshelf.Estimatedepipolargeometryonindoorscenewithsigni cantscalechange.Inthecutouts,thechangeintheresolutionofdetectedDRsisclearlyvisible.

ofalocalintensityminimum(ormaximum)andathreshold.ExamplesofMSERsareshowninFigs.1,2and5.

Notes.Althoughthesetofextremalregionsiscovariantwithanyone-to-onecontinuoustransformationoftheimagedomainandthuscovarianttoprojectivetransformation,theprocessoftheselectionofthemaximallystablesubsetisaf ne-covariant.TheMSERsarethereforeonlyaf ne-covariant.

Thestructureoftheabovealgorithmandofanef cientwatershedalgorithm[22]isessentiallyidentical.However,thestructureoftheoutputofthetwoalgorithmsisdifferent.TheSwatershedisapartitioningofD;i.e.asetofregionsRi:Ri¼D;Rj>Rk¼Y:Inwatershedcomputation,focusisonthethresholdswhereregionsmerge(andtwowatershedstouch).Suchthresholdareoflittleinteresthere,sincetheyarehighlyunstable—aftermerge,theregionareajumps.InMSERdetection,weseekarangeofthresholdsthatleavesthewatershedbasineffectivelyunchanged.DetectionofMSERisalsorelatedtothresholding.Everyextremalregionisaconnectedcomponentofathresholdedimage.However,noglobalor‘optimal’thresholdissought,allthresholdsaretestedandthestabilityoftheconnectedcomponentsevaluated.TheoutputoftheMSERdetectorisnotabinarizedimage.Forsomepartsoftheimage,multiple

Fig.2.Valbonne.Estimatedepipolargeometryandpointsassociatedtothematchedregionsareshowninthe rstrow.Cutoutsinthesecondrowshowmatched

bricks.