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

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

Fig.3.Wash.Epipolargeometryanddensematchedregionswithfullyaf ne

distortion.

stablethresholdsexistandasystemofnestedsubsetsisoutputinthiscase.FinallyweremarkthatMSERscanbede nedonanyimage(evenhigh-dimensional)whosepixelvaluesarefromatotallyorderedset.

3.Theproposedrobustwide-baselinealgorithmDistinguishedregiondetection.Asa rststep,theDRsaredetected—theMSERscomputedontheintensityimage(MSERþ)andontheinvertedimage(MSER2).

Fig.4.EstimatedEGonanoutdoor

scene.

Measurementregions.Ameasurementregionofarbi-trarysizemaybeassociatedwitheachDR,iftheconstructionisaf ne-covariant.Smallermeasurementregionsarebothmorelikelytosatisfytheplanarityconditionandnottocrossadiscontinuityindepthororientation.Ontheotherhand,smallregionsarelessdiscriminative,i.e.theyaremuchlesslikelytobeunique.Increasingthesizeofameasurementregioncarriestheriskofincludingpartsofbackgroundthatarecompletelydifferentinthetwoimagesconsidered.Clearly,theoptimalsizeofaMRdependsonthescenecontentanditisdifferentforeachDR.In[21],TuytelaarsandVanGooldoubletheellipticalDRtoincreasediscriminability,whilekeepingtheprobabilityofcrossingobjectboundariesatanacceptablelevel.

Intheproposedalgorithm,measurementregionsareselectedatmultiplescales:theDRitself,1.5,2and3timesscaledconvexhulloftheDR.Sincematchingisaccomplishedinarobustmanner,webene tfromtheincreaseofdistinctivenessoflargeregionswithoutbeingseverelyaffectedbyclutterornon-planarityoftheDR’monly,MahalanobisdistancehasbeenusedinMRmatching.However,thenon-robustnessofthismetricmeansthatmatchingmayfailbecauseofasinglecorruptedmeasure-ment(thishappenedintheexperimentsreportedbelow).Invariantdescription.Inallexperiments,rotationalinvariants(basedoncomplexmoments)[8]wereusedafterapplyingatransformationthatdiagonalisestheregionscovariancematrixoftheDR.Incombination,thisisanaf binationofrotationalandaf nelyinvariantgeneralisedcolourmoments[12]gaveasimilarresult.Ontheirown,theaf neinvariantsfailedonproblemswithalargescalechange.

Robustmatching.Ameasurementtakenfromanalmostplanarpatchofthescenewithstableinvariantdescriptionwillbereferredtoasa‘goodmeasurement’.Unstablemeasurementsorthosecomputedonnon-planarsurfaces

or

Fig.5.Cylindricalbox.Epipolargeometry(top)andmatchedregions(bottomleft).Fullyaf nedistortion,anon-planarobject,texturedsurfaceandstrongspecularre ectionsarepresentinthescene.SHOUT(bottomright),ascenewithachangeofilluminationspectralpowerdistribution.