stereo

BinocularStereoPhilipposMordohaiUniversityofNorthCarolinaatChapelHillSeptember21,20062Outline•Introduction•Costfunctions•Challenges•Costaggregation•Optimization•Binocularstereoalgorithms3StereoVision•Matchsomething–Feature-basedalgorithms–Area-basedalgorithms•Applyconstraintstohelpconvergence–Smoothness/Regularization–Ordering–Uniqueness–Visibility•Optimizesomething(typically)–Needenergy/objectivefunctionthatcanbeoptimized4BinocularDatasetsMiddleburydata()5Challenges•Ill-posedinverseproblem–Recover3-Dstructurefrom2-Dinformation•Difficulties–Uniformregions–Half-occludedpixels6PixelDissimilarity•Absolutedifferenceofintensities•c=|I1(x,y)-I2(x-d,y)|•Intervalmatching[Birchfield98]–Considerssensorintegration–Representspixelsasintervals7AlternativeDissimilarityMeasures•RankandCensustransforms[ZabihECCV94]•Ranktransform:–DefinewindowcontainingRpixelsaroundeachpixel–Countthenumberofpixelswithlowerintensitiesthancenterpixelinthewindow–Replaceintensitywithrank(0..R-1)–ComputeSADonrank-transformedimages•Censustransform:–Usebitstring,definedbyneighbors,insteadofscalarrank•Robustagainstilluminationchanges8RankandCensusTransformResults•Noisefree,randomdotstereograms•Differentgainandbias9Outline•Introduction•Costfunctions•Challenges•Costaggregation•Optimization•Binocularstereoalgorithms10SystematicErrorsofArea-basedStereo•Ambiguousmatchesintexturelessregions•Surfaceover-extension[OkutomiIJCV02]11SurfaceOver-extension•ExpectedvalueofE[(x-y)2]forxinleftandyinrightimageis:•CaseA:σF2+σB2+(μF-μB)2forw/2-λpixelsineachrow•CaseB:2σB2forw/2+λpixelsineachrowRightimageLeftimageDisparityofbacksurface12SurfaceOver-extension•Discontinuityperpendiculartoepipolarlines•DiscontinuityparalleltoepipolarlinesRightimageLeftimageDisparityofbacksurface13Over-extensionandshrinkage•Turnsoutthat:fordiscontinuitiesperpendiculartoepipolarlines•And:fordiscontinuitiesparalleltoepipolarlines26ww22ww14RandomDotStereogramExperiments15RandomDotStereogramExperiments16OffsetWindowsEquivalenttousingminnearbycostResult:lossofdepthaccuracy17DiscontinuityDetection•Useoffsetwindowsonlywhereappropriate–Bi-modaldistributionofSSD–Pixelofinterestdifferentthanmodewithinwindow18Outline•Introduction•Costfunctions•Challenges•Costaggregation•Optimization•Binocularstereoalgorithms19CompactWindows•[VekslerCVPR03]:Adaptwindowssizebasedon:–Averagematchingerrorperpixel–Varianceofmatchingerror–Windowsize(tobiastowardslargerwindows)•Pickwindowthatminimizescost20IntegralImageSumofshadedpartComputeanintegralimageforpixeldissimilarityateachpossibledisparityACDBShadedarea=A+D-B-CIndependentofsize21ResultsusingCompactWindows22Rod-shapedfilters•Insteadofsquarewindowsaggregatecostinrod-shapedshiftablewindows[KimCVPR05]•Searchforonethatminimizesthecost(assumethatitisaniso-disparitycurve)•Typicallyuse36orientations23LocallyAdaptiveSupportApplyweightstocontributionsofneighboringpixelsaccordingtosimilarityandproximity[YoonCVPR05]24LocallyAdaptiveSupport•SimilarityinCIELabcolorspace:•Proximity:Euclideandistance•Weights:25LocallyAdaptiveSupport:Results26LocallyAdaptiveSupport:Results27Outline•Introduction•Costfunctions•Challenges•Costaggregation•Optimization•Binocularstereoalgorithms28Constraints•Resultsofun-sophisticatedlocaloperatorsstillnoisy•Optimizationrequired•Needconstraints–Smoothness–Ordering–Uniqueness–Visibility•Energyfunction:2)(leftpSprightdpleftpIIleftSpppdd21)(),...,,(21ndddE29OrderingConstraint•IfAisontheleftofBinreferenceimage=thematchforAhastobeontheleftofthematchofBintargetimage•Violatedbythinobjects•But,usefulfordynamicprogrammingImagefromSunetal.CVPR0530DynamicProgrammingLeftimageRightimageleftSrightSpp+dpleftSrightSpqLeftocclusiontRightocclusions2)(rightqleftpIIocclCocclC31ResultsusingDynamicProgramming32DynamicProgrammingwithouttheOrderingConstraint•TwoPassDynamicProgramming[KimCVPR05]–Usereliablematchesfoundwithrod-shapedfiltersas“groundcontrolpoints”–Noordering–Secondpassalongcolumnstoenforceinter-scanlineconsistency33DynamicProgrammingwithouttheOrderingConstraint•UseGPU[GongCVPR05]–Calculate3-Dmatrix(x,y,d)ofmatchingcosts–Aggregateusingshiftable3x3window–Findreliablematchesalonghorizontallines–Findreliablematchesalongverticallines–Fillinholes•Matchreliability=costofscanlinepassingthroughmatch–costofscanlinenotpassingthroughmatch34NearReal-timeResults10-25framesperseconddependingonimagesizeanddisparityrange35Semi-globaloptimization•Optimize:E=Edata+E(|Dp-Dq|=1)+E(|Dp-Dq|1)[HirshmüllerCVPR05]–Usemutualinformationascost•NP-hardusinggraphcutsorbeliefpropagation(2-Doptimization)•Insteaddodynamicprogrammingalongmanydirections–Don’tusevisibilityororderingconstraints–Enforceuniqueness–Addcosts36ResultsofSemi-globaloptimization37ResultsofSemi-globaloptimizationNo.1overallinMiddleburyevaluation(at0.5errorthresholdasofSep.2006)382-DOptimization•Energy:DataTerm+Regularization•FindminimumcostcutthatseparatessourceandtargetstcutL(p)p“cut”xylabelsxyDisparitylabels39Scanlinevs.Multi-scanlineoptimizationL(p)p“cut”xylabelslabelsxL(p)pDy