Robust wide baseline stereo from maximally stable extremal r(3)
时间:2025-04-03
时间:2025-04-03
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.
…… 此处隐藏:2156字,全部文档内容请下载后查看。喜欢就下载吧 ……上一篇:设计素描教案
下一篇:基于模块化的自动装配方法