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

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

Reliableextractionofamanageablenumberofpoten-tiallycorrespondingimageelementsisanecessarybutcertainlynotasuf cientprerequisiteforsuccessfulwide-baselinematching.WithtwosetsofDRs,thematchingproblemcanbeposedasasearchinthecorrespondencespace[4].FormingacompletebipartitegraphonthetwosetsofDRsandsearchingforagloballyconsistentsubsetofcorrespondencesisclearlyoutofquestionforcomputationalreasons.Recently,awholeclassofstereomatchingandobjectrecognitionalgorithmswithcommonstructurehasemerged[1,3,7,9,10,13,15,18,20,21].Thesemethodsexploitlocalinvariantdescriptorstolimitthenumberoftentativecorrespondences.Importantdesigndecisionsatthisstageinclude:(1)thechoiceofmeasurementregions,i.e.thepartsoftheimageonwhichinvariantsarecomputed,(2)themethodofselectingtentativecorrespondencesgiventheinvariantdescriptionand(3)thechoiceofinvariants.Typically,DRsortheirscaledversionserveasmeasurementregionsandtentativecorrespondencesareestablishedbycomparinginvariantsusingMahalanobisdistance[14,16,21].Asasecondnoveltyofthepresentedapproach,arobustsimilaritymeasureforestablishingtentativecorrespondencesisproposedtoreplacetheMahalanobisdistance.Therobustnessoftheproposedsimilaritymeasureallowsustouseinvariantsfromacollectionofmeasurementregions,evensomethataremuchlargerthantheassociatedDR.Measurementsfromlargeregionsareeitherverydiscriminative(itisveryunlikelythattwolargepartsoftheimageareidentical)orcompletelywrong(e.g.iforientationordepthdiscontinuitybecomespartoftheregion).Theformerhelpsestablishingreliabletentative(local)correspondences,thein uenceofthelatterislimitedduetotherobustnessoftheapproach.

Findingepipolargeometry(EG)consistentwiththelargestnumberoftentative(local)correspondencesisthe nalstepofallwide-baselinealgorithms.RANSAChasbeenbyfarthemostwidelyadoptedmethodsince[19].ThepresentedalgorithmtakesnovelstepstoincreasethenumberofmatchedregionsandtheprecisionoftheEG.TheroughEGestimatedfromtentativecorrespondencesisusedtoguidethesearchforfurtherregionmatches.Itrestrictslocationtoepipolarlinesandprovidesanestimateofaf nemappingbetweencorrespondingregions.Thismappingallowstheuseofcorrelationto lteroutmismatches.Theprocesssigni cantlyincreasesprecisionoftheEGestimate;the nalaverageinlierdistance-from-epipolar-lineisbelow0.1pixel.FordetailsseeSection3.Relatedwork.Sincethein uentialpaperbySchmidandMohr[16]manyimagematchingandwide-baselinestereoalgorithmshavebeenproposed,mostcommonlyusingHarrisinterestpointsasDRs.TellandCarlsson[18]proposedamethodwherelinesegmentsconnectingHarrisinterestpointsformmeasurementregions.Themeasure-mentsarecharacterisedbyscaleinvariantFouriercoef -cients.TheHarrisinterestdetectorisstableoverarangeofscales,butde nesnoscaleoraf neinvariantmeasurement

region.Baumberg[1]appliedaniterativeschemeoriginally

proposedbyLindebergandGa

rding[6]toassociateaf ne-invariantmeasurementregionswithHarrisinterestpoints.In[10],MikolajczykandSchmidshowthatascale-invariantMRcanbefoundaroundHarrisinterestpoints.In[11],theapproachwascombinedwithBaumberg’siterationtoobtainanaf ne-invariantdetector.In[13],PritchettandZissermanformgroupsoflinesegmentsandestimatelocalhomo-graphiesusingparallelogramsasmeasurementregions.TuytelaarsandVanGoolintroducedtwonewclassesofaf ne-invariantDRs,onebasedonlocalintensityextrema[21]theotherusingpointandcurvefeatures[20].Inthelatterapproach,DRsarecharacterisedbymeasurementsfrominsideanellipse,constructedinanaf neinvariantmanner.Lowe[7]describesthe‘ScaleInvariantFeatureTransform’approachwhichproducesascaleandorientation-invariantcharacterisationofinterestpoints.

Therestofthepaperisstructuredasfollows.MSERarede nedandtheirdetectionalgorithmisdescribedinSection2.InSection3,detailsofanovelrobustmatchingalgorithmaregiven.ExperimentalresultsonoutdoorandindoorimagestakenwithanuncalibratedcameraarepresentedinSection4.Presentedexperimentsaresummar-izedandthecontributionsofthepaperarereviewedinSection5.

2.Maximallystableextremalregions

Inthissection,weintroduceanewtypeofimageelementsusefulinwide-baselinematching—theMaximallyStableExtremalRegions.Theregionsarede nedsolelybyanextremalpropertyoftheintensityfunctionintheregionandonitsouterboundary.

Theconceptcanbeexplainedinformallyasfollows.Imagineallpossiblethresholdingsofagray-levelimageI:Wewillrefertothepixelsbelowathresholdas‘black’andtothoseaboveorequalas‘white’.IfwewereshownamovieofthresholdedimagesIt;withframetcorrespondingtothresholdt;wewouldsee rstawhiteimage.Subsequentlyblackspotscorrespondingtolocalintensityminimawillappearandgrow.Atsomepointregionscorrespondingtotwolocalminimawillmerge.Finally,thelastimagewillbeblack.Thesetofallconnectedcomponentsofallframesofthemovieisthesetofallmaximalregions;minimalregionscouldbeobtainedbyinvertingtheintensityofIandrunningthesameprocess.Theformalde nitionoftheMSERconceptandthenecessaryauxiliaryde nitionsaregiveninTable1.

Inmanyimages,localbinarizationisstableoveralargerangeofthresholdsincertainregions.Suchregionsareofinterestsincetheypossesthefollowingproperties: Invariancetoaf netransformationofimageintensities. Covariancetoadjacencypreserving(continuous)trans-formationT:D!Dontheimagedomain.