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–767765

atdiscontinuitiesindepthororientationwillbereferredtoas‘corruptedmeasurements’.

Therobustsimilarityiiscomputedasfollows.ForeachmeasurementMAonregionA;kregionsB1;…;BkfromtheotherimagewiththecorrespondingithmeasurementMiB;…;MiBnearesttoMiAaresuggesting1k

foundandavoteiscastcorrespondenceofAandeachofB1;…;Bk:Thevotesaresummedoverallmeasurements.

TheDRswiththelargestnumberofvotesarethecandidatesfortentativecorrespondences.Experimentally,wefoundthatksetto1%ofthenumberofregionsgivesgoodresults.Thenumberofregionsistypicallyinthe102–103rangeandkisthusbetween1and10.Inthecurrentimplementation216invariantsateachscale,i.e.atotalof864measurementsareused(i[½1;864 ;irunsthroughallscalesandallinvariants).The216rotationalinvariantsaredescribedindetailin[8].Thechoiceoffourscaleswasmadebytrialanderrorandasacompromisebetweenspeedandperformance.

Probabilisticanalysisofthelikelihoodofthesuccessoftheprocedureisnotsimple,sincethedistributionofinvariantsandtheirnoiseisimage-dependent.Wethereforeonlysupposethatcorruptedmeasurementsspreadtheirvotesrandomly,notconspiringtocreateahighscoreandthatgoodmeasurementsaremorelikelytovoteforcorrectmatches.

Tentativecorrespondencesusingcorrelation.Invariantdescriptionisusedasapreliminarytest.The nalselectionoftentativecorrespondencesisbasedoncorrelation.First,transformationsthatdiagonalisethecovariancematrixoftheDRsareapplied.Theresultingcircularregionsarecorrelated(forallrelativerotations).Thisprocedureisdoneef cientlyinpolarcoordinatesfordifferentsizesofcircles.

RoughEGisestimatedbyapplyingRANSACtothecentresofgravityofDRs.Subsequently,theprecisionoftheEGestimateissigni cantlyimprovedbythefollowingprocess.First,anaf netransformationbetweenpairsofpotentiallycorrespondingDRs,i.e.theDRsconsistentwiththeroughEG,iscomputed.Correspondenceofcovariancematricesde nesanaf netransformationuptoarotation.Therotationisdeterminedfromepipolarlines[2].Next,DRcorrespondencesareprunedandonlythosewithcorrelationoftheirtransformedimagesaboveathresholdareselected.Inthenextstep,RANSACisappliedagain,butthistimewithaverynarrowthreshold.The monly,DRsdifferinminutedifferencesthatrendertheircentresofgravityinconsistentwiththe neEG,butthecentresoftheconvexhullsarepreciseenough.Theprecisionofthe nalEG,estimatedlinearlybytheeightpointalgorithm(withoutbundleadjustmentorradialdistortioncorrection)issurprisinglyhigh.Theaveragedistanceofinliersfromepipolarlineisbelow0.1pixel,seeTable3.

4.Experiments

Thefollowingexperimentswereconducted:

Bookshelf,(Fig.1).TheBOOKSHELFscenetestsper-formanceunderaverylargescalechange.Thecorrespond-ingDRsintheleftviewarecon nedonlytoasmallpartoftheimagesincetherestofthesceneisnotvisibleinthesecondview.Differentresolutionofdetectedfeaturesisevidentintheclose-up.

Valbonne,(Fig.2).Thisoutdoorscenehasbeenanalysedintheliterature[13,14].Repetitivepatternssuchasbricksarepresent.Thepartofthescenevisibleinbothviewscoversasmallfractionoftheimage.

Wash,(Fig.3).Resultsonthisimagesethavebeenpresentedin[21].Thecameraundergoessigni canttranslationandrotation.Theorderingconstraintisnotablyviolated,objectsappearondifferentbackgrounds.

Kampa,(Fig.4),isanexampleofanurbanoutdoorscene.Arelativelylargefractionoftheimagesiscoveredbychangingsky.Repeatingwindowsmadematchingdif cult.Cylindricalbox,(Fig.5,topandbottomleft),showsametalboxonatextured oor.Theregionsmatchedontheboxdemonstrateperformanceonanon-planarsurface.Asigni cantchangeofilluminationandastrongspecularre ectionispresentinthesecondimagethatwastakenwitha ash(thisstronglydecreasesthenumberofMSERþ).

Shout,(Fig.5,bottomright).Thisscenehasbeenusedin[21].Sincethespectralpowerdistributionoftheillumina-tionandthepositionoflightsourcesissigni cantlydifferent,weincludedthetesttodemonstrateperformanceinvariableilluminationconditions.

ResultsaresummarizedinTables2and3.Table2showsthenumberofdetectedDRsintheleft£rightimagesforbothtypesoftheDRs(MSER2andMSERþ).ThenumberoftentativecorrespondencesisgiveninthelastcolumnofTable2.Table3showsthenumberofcorrespondencesestablishedindifferentstagesofthealgorithm.Column‘TC’repeatsthenumberoftentativecorrespondences.Column‘roughEG’displaysthenumberoftentativecorrespondencesconsistentwiththeroughestimateoftheEG.Theratioof‘TC’and‘roughEG’determinesthespeedoftheRANSACalgorithm.

Table2

NumbersofDRsdetectedintheleftandrightimagesinthe‘leftDRs’£‘rightDRs’formatNo.ofMSER2MSERþTCBookshelf511£908349£48885Valbonne906£1012761£95049Wash1026£714542£448171Kampa1015£914659£652303Cyl.box1043£627788£3963Shout

298£348

80£93

151

ThenumberoftentativecorrespondencesisgivenintheTCcolumn.