Fast variable window for stereo correspondence using integral images

OlgaVeksler

NECLaboratoriesAmerica,4IndependenceWayPrinceton,NJ08540

olga@nec-labs.com

Abstract

Wedevelopafastandaccuratevariablewindowap-proach.Thetwomainideasforachievingaccuracyarechoosingausefulrangeofwindowsizes/shapesforeval-uationanddevelopinganewwindowcostwhichisparticu-larlysuitableforcomparingwindowsofdifferentsizes.ThespeedofourapproachisduetotheIntegralImagetech-nique,whichallowscomputationofourwindowcostoveranyrectangularwindowinconstanttime,regardlessofwin-dowsize.OurmethodranksinthetopfourontheMiddle-burystereodatabasewithgroundtruth,andperformsbestoutofmethodswhichhavecomparableefficiency.

1Introduction

Area-basedmatchingisanoldandstillwidelyusedmethodfordensestereocorrespondence[11,12,13,7,6].Inthisapproachoneassumesthatapixelissurroundedbyawindowofpixelsatapproximatelyequaldisparity.Thusthecostforpixelptohavedisparitydisestimatedbytakingawindowofpixelsaroundpintheleftimage,shiftingthiswindowbydintherightimageandcomputingthediffer-encebetweenthesetwowindows.Somecommonwindowcostsaresumofsquaredorabsolutedifferences,normal-izedcorrelation,etc.Afterallwindowcostsarecomputed,apixelisassignedthedisparitywiththebestwindowcost.Thewellknownproblemwiththisapproachisthatwhiletheassumptionofawindowatapproximatelyequaldispar-ityisusuallyvalid,theshapeandsizeofthatwindowisunknownbeforehand.Ignoringthisproblem,mostmethodsusearectangularwindowoffixedsize.Inthiscasetheim-plementationisveryefficient.Usingthe“slidingcolumn”methodof[3]therunningtimeisindependentofthewin-dowsize,itislinearinthenumberofpixelsanddisparities.Asearlyas[11],researchersrealizedthatkeepingwin-dowsizefixedforallpixelsleadstosystematicerrors.Forareliableestimateawindowmustbelargeenoughtohavesufficientintensityvariation.Butontheotherhandawin-dowmustbesmallenoughtocontainonlypixelsatapprox-

imatelyequaldisparity.Furthermoreneardisparitybound-arieswindowsofdifferentshapesareneededtoavoidcross-ingthatboundary.Thusaswindowsizeisincreasedfromsmalltolarge,theresultsrangefromaccuratedisparityboundariesbutnoisyinlowtextureareastomorereliableinlowtextureareasbutblurreddisparityboundaries.Thereisnogoldenmiddlewhereresultsarebothreliableinlowtextureareasanddisparityboundariesarenotblurred.

Sincefixedwindowalgorithmsclearlydonotperformwell,therehasbeensomeworkonvaryingwindowsizeand/orshape.Suchvariablewindowmethodsfacetwomainissues.Firstisdesigninganappropriatewindowcost,sincewindowsofdifferentsizesand/orshapesaretobecom-pared.Secondisefficientlysearchingthespaceofpossiblewindowsfortheonewiththebestcost.Theearliestvariablewindowapproachis[11].Theyusenormalizedcorrelationforthewindowcost,andchangewindowsizeuntilthereissignificantintensityvarianceinawindow.Howeverrelyingonlyonintensityvarianceisnotenough,sinceitmaycomeatthecostofcrossingadisparityboundary.

Theadaptivewindow[9]usesanuncertaintyofdispar-ityestimateasthewindowcost.Forthiswindowcost,theyneedamodelofdisparityvariationwithinawindow,andalsoinitialdisparityestimate.Thentofindthebestwin-dow,theyusegreedylocalsearch,whichisveryinefficient.Whilethismethodiselegant,itdoesnotgivesufficientim-provementoverthefixedwindowalgorithm.Theproblemmightbeitssensitivitytotheinitialdisparityestimate.Anotherpopularmethod[8,5,4,10]isthemultiplewin-dow.Foreachpixel,asmallnumberofdifferentwindowsareevaluated,andtheonewiththebestcostisretained.Usuallywindowsizeisconstant,butshapeisvaried.Typi-calwindowcostisrelativelysimple,forexampletheSSD.Tobeefficient,thismethodseverelylimitsthenumberofwindows,underteninalloftheabovepapers.Becausewindowshapeisvaried,atdiscontinuitiesthismethodper-formsbetterthanthefixedwindowmethod.Howevertherearestillproblemsinlowtextureregions,sincethenumberofdifferentwindowsizestriedisnotnearlyenough.

In[15]acompactwindowalgorithmisdeveloped.Win-dowcostistheaveragewindowerrorplusbiastolargerwin-

dows.Efficientoptimizationovermany“compact”windowshapesisdoneusingtheminimumratiocyclealgorithm.Whilethismethodperformswell,itdoesnotseemtobeefficientenoughforrealtimeimplementation.

Weproposeanewvariablewindowalgorithm.Ourmainideaistofindausefulrangeofwindowsizesandshapestoexplorewhileevaluatinganovelwindowcostwhichworkswellforcomparingwindowofdifferentsizes.Toefficientlysearchthespaceofwindows,weusetheintegralimagetechnique,longknowningraphics[2]1andrecentlyintro-ducedinvision[16].Withthistechnique,aslongaswin-dowcostisafunctionofsumoftermsdependingonindi-vidualimagepixels,thecostoveranarbitraryrectangularwindowcanbecomputedinconstanttime.Manyusefulwindowcostssatisfythisrestriction.

Ournovelwindowcostistheaverageerrorinawin-dowwithbiastolargerwindowsandsmallererrorvariance.Experimentallywefoundthatthiscostassignslowernum-berstowindowswhicharemorelikelytolieatthesamedisparity.Thiscostissimilartotheonein[15],howeverweaddbiastosmallervariance.Thisimprovestheresults,sincepatchesofpixelswhichlieatthesamedisparitytendtohavelowererrorvariance.Variancecannotbehandledby[15]duetotherestrictionsoftheiroptimizationmethod.Usingthewindowcostaboveandtheintegralimagesweaimtoefficientlyevaluateausefulrangeofwindowsofdifferentsizesandshapes.Wefoundthatlimitingwindowshapestojustsquaresworkswellenough.Furthermoredueespeciallytothevarianceterminourwindowcost,win-dowswithlowercoststendtolieatapproximatelythesamedisparity.Thereforewindowcostsareupdatedforallpix-elsinawindow,notjustthepixelinthecenterasdoneinmosttraditionalareabasedmethods.Thisallowsrobustper-formanceneardiscontinuities,whereoneneedswindowsshapesnotcenteredatthemiddlepixel.Eventhoughcom-putingawindowcosttakesconstanttime,updatingthecostforallpixelsinthewindowwouldtaketimelinearinthewindowsize,ifdonenaively.Weusedynamicprogram-mingtoachieveconstantupdatetimeonaverage.

Thusthealgorithmworksbyexploringallsquarewin-dowsbetweensomeminimumandmaximumsize.Usingtheobservationthatforafixedpixel,thefunctionofthebestwindowsizeiscontinuousalmosteverywhere,wefur-therreducethenumberofwindowevaluationstojustsixwindowsperpixelonaverage.Sothealgorithmisfast,itsrunningtimeislinearinthenumberofpixelsanddispari-ties,anditissuitableforrealtimeimplementation.

WeshowresultsontheMiddleburydatabasewithgroundtruthwhichwascompiledbyD.ScharsteinandR.Szeliski,andhasbecomeastandardbenchmarkforperformanceevaluationandcomparisontootheralgorithms.Forthere-sults,seehttp://www.middlebury.edu/stereo/.Ourmethod

1In

graphicstheyarecalledsummedareatables.

(a)I(x,y)isthesumoff(b)EfficientcomputationintheshadedareaofI(x,y)

Figure1.

ranksinthetop4(atthesubmissiontime),anditperformsbestoutofmethodswhichhavecomparableefficiency.

2IntegralImage

Inthissectionweexplainhowtheintegralimageworks[2,16].Supposewehaveafunctionfrompixelstorealnumbersf(x,y),andwewishtocomputethesumofthisfunctioninsomerectangular≤i≤󰀆

areaoftheimage,thatis:f(i,j).

x′x,y′≤j≤y

Thestraightforwardcomputationtakesjustlineartime,ofcourse.Howeverifweneedtocomputesuchsumsoverdistinctrectanglesmanytimes,thereisamoreefficientwayusingintegralimages,whichrequiresjustaconstantnum-berofoperationforeachrectangularsum.Andunlikethe“slidingcolumn”methodof[3],therectanglesdonothavetobeoffixedsize,theycanbeofarbitrarysize.Letusfirstcomputetheintegral󰀆image

I(x,y)=f(x,y).

x′≤x,y′≤y

ThatisI(x,y)holdsthesumofallf(x,y)termstotheleft

andabove(x,y),andincluding(x,y),seeFig.1(a).Theintegralimagecanbecomputedinlineartimeforall(x,y),withjustfourarithmeticoperationsperpixel.Westartinthetopleftcorner,keepgoingfirsttotherightandthendown,andusetherecursionI(x,y)=f(x,y)+I(x−1,y)+I(x,y−1)−I(x−1,y−1)withtheappropriatemodi-ficationattheimageborders.Whythisworksisapparentfromfigure1(b).PixelswiththesmallplussignsarethecontributionsfromI(x−1,y),pixelswiththelargerplussignsarethecontributionsfromI(x,y−1),andpixelswiththeminussignsarethecontributionsfromI(x−1,y−1).Aftertheintegralimageiscomputed,followingtheaboveideas,thesumoff(x,y)inarectanglewithcornersat(x,y)and(x′,y′)canbecomputedwithfourarithmeticoperationsviaI(x,y)−I(x′−1,y)−I(x,y′−1)+I(x′1,y′−1),withappropriatemodificationsattheborder.Thus

−withalinearamountofprecomputation,thesumoff(x,y)overanyrectanglecanbecomputedinconstanttime.

3WindowCost

Inthissectionwedescribethewindowcostwhichwefoundtoworkwellforevaluationwhetherallpixelsinawindowlieatapproximatelythesamedisparity.Wealsoshowhowtocomputethiscostusingtheintegralimages.Firstweneedtodescribeourmeasurementerror.

SupposeL(x,y)istheintensityofpixel(x,y)intheleftimageandR(x,y)istheintensityof(x,y)intherightim-age.Toevaluatehowlikelyadisparitydisforanindivid-ualpixel(x,y),somekindofmeasurementerrored(x,y)whichdependsonL(x,y)andR(x−d,y)isused.Oneofthesimplestised(x,y)=|L(x,y)−R(x−d,y)|.Wehow-everusetheonedevelopedin[1],whichisinsensitivetoimagesamplingartifacts(theseareespeciallypronounced

intexturedareasofanimage).FirstwedefineR

ˆasthelin-earlyinterpolatedfunctionbetweenthesamplepointsontherightscanline,andthenwemeasurehowwelltheintensityat(x,y)intheleftimagefitsintothelinearlyinterpolatedregionsurrounding(x−d,y)intherightimage

eld(x,y)=minx′∈[x−d−1

2,x−d+12]|L(x,y)−Rˆ(x′,y)|.Forsymmetry,

erd(x,y)=

min

ˆx′∈[x−12,x+12]

|L

(x′,y)−R(x−d,y)|.Finally,ed(x,y)=min󰀁elr

versionsofsamplinginsensitived(x,y),e(x,y)󰀂.Forothererrorseed

[14].

NowwecandefineourwindowcostCd(W).HereWisarectangularsetofpixels,anddissomedisparity,sinceawindowisevaluatedatsomedisparity.

C(W)=e+α·var(e)+√β

dW+γ.(1)

Thefirstterminequation(1)isjustmenterrorinthewindow:e=ofthistermisobvious:the󰀅theaveragemeasure-(x,y)∈W

ed(x,y)

.Thein-clusionlower|Wthe|measurementerror,themorelikelydisparitydisforpixelsinW.Wenormalizebywindowsize|W|sincewewillbecomparingwindowsofdifferentsizes.Thesecondof󰀃󰀅theerrorsinawindow:var(e)=󰀅termisthe(x,y)∈W

(evarianced(x,y))2

|(x,y)∈W

e)

−d(x,y|W|󰀄2

W|=e2termbecausewefoundexperimentally−(e)2.Weincludethevariancethatthepixelswhich

belongtothesamedisparitytendtohavenotjustsmalleraverageerrorbutalsosmallererrorvariance.

Thelastterminequation(1)issmallerforlargerwin-dows,soitimplementsbiastolargerwindows.Thistermiscrucialinuntexturedregions,wherethefirsttwoterms

areapproximatelyequalforallwindows,andlargerwin-dowsshouldbepreferredforareliableperformance.Lastly,

α,β,γareparametersassigningrelativeweightstotermsinequation(1).Weholdthemconstantforallexperiments.Tocomputethewindowcostinequation(1)efficiently,wefirstcomputetheintegralimagesoff(x,y)=ed(x,y)andofg(x,y)=(ed(x,y))2.Thenfromsection2isobvi-ousthatbotheandvar(e)canbecomputedinconstanttimeusingtheseintegralimages,andthusourwindowcostoveranarbitraryrectanglecanbecomputedinconstanttime.

4EfficientSearchforMinimumWindow

Inthissectionweexplainadynamicprogrammingtech-niquewhichgreatlyimprovesourefficiency.Inourvariablewindowalgorithm(whichisfullydescribedinSec.5),wewillfacethefollowingsubproblem.Supposeforeachim-agepixel(x,y)wearegivenonefixedsizerectangularwin-dowwithitsupperleftcornerat(x,y)andwiththebottomrightcornerinanylocation.Thiscollectionofwindowscanbeindexedbythecoordinatestheupperleftwindowcorners,sinceforeach(x,y)thereisexactlyonewindowwiththeupperleftcornerat(x,y).SoletW(x,y)denoteawindowfromthiscollection,where(x,y)istheupperleftcorner.Eventhoughthereisonlyonewindowperpixel,eachpixeltypicallybelongstomanywindows(butisthetopleftcornerofonlyoneofthewindows).Theproblemistoassigntoeachpixel(x,y)thecostoftheminimumcostwindowitbelongsto.Ifdonenaively,solvingthisproblemtakestimelinearinthesizeofthelargestW(x,y)timestheimagessize,whichistoocostly.Howeverwecansolvethisprobleminexpectedlineartimeintheimagesize,thatiswecanremovethewindowsizedependence.

LetM(x,y)denotethecostoftheminimumcostwindow(x,y)belongsto.BesidescomputingM(x,y)wealsoneedtocomputethecoordinatesofthebottomrightcorneroftheminimumcostwindow,denotedby(Mx(x,y),My(x,y)).Westartintheupperleftcorneroftheimage,andfollowthedirectionfirsttotherightandthendown.ComputingM(x,y),Mx(x,y),My(x,y)istrivialfor(x,y)intheupperleftcorneroftheimage,sincesuch(x,y)isinonlyonewindow.Theargumentproceedsbyin-duction.SupposeweneedtocomputeM(x,y),Mx(x,y),My(x,y)forsome(x,y)andthesethreequantitieswerealreadycomputedforallpixelstotheleftandabove(x,y).Therearefourpossiblecases:

case1:Mx(x−1,y)≥xandMy(x,y−1)≥ycase2:Mx(x−1,y)≥xandMy(x,y−1)M(x−1,y)andthecostofthewindowW(x,y).Inthiscase,M(x,y),Mx(x,y)andMy(x,y)canbecomputedinconstanttime.Incase2,M(x,y)istheminimumofcostofwindowW(x,y),M(x−1,y),andcostsofwindowsW(x,y1)wherey1rangesfromy−1toy−k+1withkequaltothemaximumwindowheightinthegivencollec-tionofwindows.Thusincase2theworkisproportionaltothemaximumwindowheight.Case3issimilartocase2,theworkthereisproportionaltothemaximumwindowwidth.Finallycase4istheworst,weneedtoexaminecostsofallwindowswhichcontain(x,y),sotheworkispro-portionaltothemaximumwindowsize.Fromexperiments,cases1,2,3,4areapproximatelydistributedat70,14,14,and2percent,respectively.SotheexpectedrunningtimetocomputeM(x,y)forall(x,y)isroughlylinear.

5VariableWindowAlgorithm

Inthissectionwedescribeourvariablewindowalgo-rithm.Ouroverallgoalistoevaluateausefulrangeofwindowsofdifferentsizesandshapesinasmallamountoftime,usingthecostfunctioninsection3,andintegralimagesofsection2forefficiency.Therearethreemainideasinourapproachwhichgiveusefficiencyandaccu-racy.Firstwelimitwindowshapestojustsquares.Secondwindowcostsareupdatedforallpixelsinawindow,notjustthepixelinthemiddle.Thirdthecontinuitypropertiesofthebestwindowsizeforafixedpixelareexploitedtoevenfurtherreducethenumberofwindowevaluations.Wenowdescribeandmotivatetheseideasindetail.

Wefoundthatwecanlimitwindowshapestosquaresandstillachievegoodresults.Thiswaywecanexploremanydifferentwindowsizes(whichiscrucialforgoodper-formanceinuntexturedregions)whiledrasticallyreducingthenumberofwindowevaluation.Welimitwindowstosquaressolelyforefficiency.Butinterestinglyifwerunouralgorithmallowinganyrectangularshapes,theresultsdonotimprovebymuch,whileefficiencysuffersalot.Thisislikelybecauseweneedtofindalargeenoughpatchofpixelsatapproximatelyequaldisparity,butwedonotnecessarilyneedtoconformascloselyaspossibletotheactualshapeofthepatchofpixelsatthesamedisparity,asisthecasewhenusingmoregeneralwindowshapes(rectanglesasopposedtosquares).Thusouralgorithmevaluatessquarewindowsbetweensomeminimumandmaximumallowedsizes.

Thesecondideaistousewindowcostasanestimatenotjustforthepixelinthecenterofthewindow,butforallpix-elsinthewindow.Wecanaffordthisbecauseourwindowcostisparticularlygoodforevaluatingwhetherallpixelsinawindowlieatapproximatelythesamedisparity,espe-ciallyduetothevarianceinequation(1).Thisidealeadstobetterperformanceatdisparityboundaries,wherewindowsnotcenteredatthemiddlepixelareneededtoavoidcross-

Figure2.Bestwindowsizes

ingadisparityboundary.Weneedefficientimplementation,however.Whilecomputingasquarewindowcosttakescon-stanttime,updatingthecostnaivelyforallwindowpixelstakestimelinearinthewindowsize,whichistoocostly.Weusethedynamicprogrammingalgorithminsection4forefficientwindowcostupdate.LetW(x,y:x′,y′)de-noteawindowwithitsupperleftcornerat(x,y)andthebottomrightcornerat(x′,y′).Wefixadisparitydandforeachpixel(x,y)weevaluatecostsofallsquarewindowsin{Wand(x,uyare:x′,y′)|l≤(x′theminimumand−x)maximum=(y′l−yallowed)≤u}window,whereheights.ThenweretainonlytheW(x,y:x′,y′)withthesmallestcost.Thusforeach(x,y)wehaveonlyonewin-dowW(x,y:x′,y′)andsowecanusethealgorithminsection4.Thatisforallpixelswecanfindtheminimumcostretainedwindoweachpixelbelongstoinlinearoveralltime.Thenthisprocessisrepeatedforalldisparities.Notethatinthisapproach,manysquarewindowsarenotused.ThatisifcostofW(x,y:x1,y1)isgreaterthanthecostofW(x,y:x2,y2),thenW(x,y:x1,y1)isdiscarded.Wedothisforefficiency.Howeverwhenwecomparetheper-formanceofthisapproachwiththemuchlessefficiental-ternativeofupdatingwindowcostsforallsquarewindows,resultsareslightlyworse,insteadofexpectedbetter.Thisisprobablybecauseifsomewindowisdiscarded,itismorelikelytocrossadisparityboundarythanaretainedwindow,andthusshouldnotbeusedintheupdateofwindowcosts.Therunningtimeofthealgorithminthepreviouspara-graphinlinearinthenumberofpixelstimesnumberofdisparitiestimesmaximumwindowheight.Howeverwecanspeedupourmethodfurtherbygettingridofwin-dowheightdependency.Fig.2showsthesizesofthebestW(x,y:x′,y′)foreach(x,y)inaportionofsomescene.Thebrighterthecolor,thelargerthewindowsize.Noticethatformostpixels,thebestwindowsizeiscontinuousei-therfromtheleftortheright.Weexploitthiscontinuityasfollows.Fortheleftmostpixelofeachlinewewillcom-putethebestwindowsearchingthroughthewholerangebetweenthesmallestandlargestwindowsizes.Fortherestofpixelsonthatlineweusepreviouswindowsizetolimitthesearchrange.Thatissupposefor(x,y)thebestwindowisW(x,y:x′,y′),andsowindowheightisk=x′For(x+1,y)wearegoingtoevaluateonlythewindows−x+1.withheightsbetweenk−1andk+1.Ofcoursewewillmissthecorrectbestsizesforsomepixelsintheimage,but

AlgorithmLayeredBeliefprop.Disc.pres.Var.Win.GraphcutsGC+occl.GraphcutsMultiw.cutComp.win.RealtimeBay.diff.CooperativeSSD+MFStoch.diff.GeneticPix-to-PixMaxFlowScanl.opt.Dyn.prog.ShaoMMHMMax.Surf.

Tsukubaalluntexdisc1.581.068.81.150.426.31.781.229.712.351.6512.171.941.099.51.270.436.91.861.009.48.086.5325.33.363.5412.94.254.4715.06.4911.6212.33.493.6514.85.233.8024.73.954.0815.52.962.6615.05.127.0614.62.982.0015.15.086.7811.94.124.6312.39.677.0435.69.7613.8524.411.1010.7042.0

all

0.340.981.171.281.300.360.420.611.611.321.452.032.212.452.212.313.474.064.844.254.765.51

Sawtoothuntex0.000.300.080.230.060.000.140.460.450.350.722.290.720.902.761.793.002.643.713.191.875.56

disc3.354.835.557.096.343.653.764.607.879.219.2913.4113.9710.5813.9614.9314.1911.9013.2630.1422.4927.39all1.521.001.611.231.792.791.690.531.671.534.002.573.742.452.496.302.169.4410.106.016.484.36

Venusuntex2.960.762.251.162.615.392.300.312.181.807.213.526.822.412.8911.372.2414.5915.016.7010.364.78

disc2.69.19.0613.356.92.55.48.013.212.318.426.413.021.823.014.621.718.217.143.931.341.1

Mapalldisc0.375.20.845.30.323.330.242.90.313.91.7910.12.399.40.263.30.334.00.8111.40.202.50.222.40.669.41.317.81.0410.90.506.83.1316.01.8410.23.3314.02.3633.08.4212.74.1727.9

Figure3.Middleburystereoevaluationtable

forthesepixelsthebestwindowsizeislikelytobecon-tinuousfromtheright.Thereforewerepeattheabovealgo-rithmbyvisitingpixelsonemoretimebutnowfromrighttoleft.Thatiswecomputethebestwindowsizefortheright-mostpixelofeachline,andusethissizetolimittherangeofwindowsforpixelstotheleft.Betweentheleft-to-rightandright-to-leftvisitations,thewindowwiththebestcostwins.Thusthenumberofwindowevaluationsperpixelissixonaverage,andsotherunningtimeofthefinalversionisasmallconstanttimesthenumberpixelsanddisparities,makingitsuitableforrealtimeimplementation.

6ExperimentalResults

InthissectionwepresentexperimentalresultsontheMiddleburydatabase.Theyprovidestereoimagerywithgroundtruth,evaluationsoftware,andcomparisonwithotheralgorithms.Thisdatabasehasbecomeabenchmarkfordensestereoalgorithmevaluation.Resultsofeval-uationandalltheimagescanbefoundonthewebviahttp://www.middlebury.edu/stereo.Foralltheexperiments,wesetα=1.5,β=7,γ=−2,andminimumandmaxi-mumwindowsizesto4by4and31by31squares.

Fig.3summarizestheresultsofevaluation.Thefirstcol-umnlistsnamesthe22evaluatedstereoalgorithms.Theal-gorithmsarearrangedroughlyintheorderofperformance,withthebetteronesontop.Thenext4columnsgiveper-centageerrorseachalgorithmmakesonthefourscenesfromthedatabase.Acomputeddisparityiscountedasan

errorifitismorethanonepixelawayfromthetruedis-parity.Eachofthesefourcolumnsisbrokeninto3sub-columns:theall,disc,anduntexcolumnsgivethetotaler-rorpercentageeverywhere,intheuntexturedareas,andneardiscontinuities,respectively.

Inthistable,ouralgorithm(Var.Win.)isintheboldface.Itistheforthbestinthedatabaseranking(atthesub-missiontime),althoughtherankinggivesjustaroughideaoftheperformanceofanalgorithm,sinceitishardtocomeupwitha“perfect”rankingfunction.Ourmethodperformsbestoutoflocalmethods,thatisthosenotrequiringcostlyglobaloptimization.TherunningtimesfortheTsukuba,Sawtooth,Venus,andMapscenesare4,7,7,and4secondsrespectively,onPentiumIII600Mhz.Ouralgorithmismoreefficientandperformsbetterthanthecompactwindowal-gorithm[15],whichismostrelated.Eventhough[15]usesmoregeneral“compact”windowshapes,weperformbet-terprobablyduetoabetterwindowcost.Ourwindowcostcannotbehandledby[15]duetorestrictionsoftheiropti-mizationprocedure.Figs.4and5showtheresultsonthesceneandmapstereopairsfromtheMiddleburydatabase.

7ConclusionsandFutureWork

Wepresentedafastandaccuratevariablewindowalgo-rithm.Oneofthemainideasofthealgorithmistoexploreausefulrangeofinterestingwindowshapesandsizes,takingadvantageofthecontinuitypropertiesofthebestwindowsize.Anotherideaisanovelwindowcostwhichworks

Figure4.Tsukubascene:leftimage,truedisparities,ourresult

Figure5.Mapscene:Leftimage,truedisparities,ourresult

wellforevaluatingwhetherallpixelsinawindowlieatapproximatelythesamedisparity.Toachievelineareffi-ciency,ouralgorithmtakesadvantageoftheintegralimagetechniquetoquicklycomputewindowcostsoverarbitraryrectangularwindows.Thustherunningtimeisasmallcon-stanttimesthenumberofpixelsanddisparities,makingitsuitableforrealtimeimplementation.Inthefutureweplantoexplorebetterwindowcosts,orlearnawindowcostfromthegroundtruthintheMiddleburydatabase.Anotherdirec-tionofresearchistofindbetterwayofexploitingcontinuitypropertiesofthebestwindowsize.

[4]A.FusielloandV.Roberto.Efficientstereowithmultiple

windowing.InCVPR,pages858–863,1997.

[5]D.Geiger,B.Ladendorf,andA.Yuille.Occlusionsand

binocularstereo.IJCV,14:211–226,1995.

[6]D.Gennery.Modellingtheenvironmentofanexploringve-hiclebymeansofstereovision.InPh.D.,1980.

[7]M.Hannah.Computermatchingofareasinstereoimagery.

InPh.D.thesis,1978.

[8]S.IntilleandA.Bobick.Disparity-spaceimagesandlarge

occlusionstereo.InECCV94,pages179–186,1994.

[9]T.KanadeandM.Okutomi.Astereomatchingalgorithm

withanadaptivewindow:Theoryandexperiment.TPAMI,16:920–932,1994.

[10]S.Kang,R.Szeliski,andJ.Chai.Handlingocclusions

indensemulti-viewstereo.InCVPR01,pagesI:103–110,2001.

[11]M.Levine,D.O’Handley,andG.Yagi.Computerdetermi-nationofdepthmaps.CGIP,2:131–150,1973.

[12]K.Mori,M.Kidode,andH.Asada.Aniterativepredic-tionandcorrectionmethodforautomaticstereocomparison.CGIP,2:393–401,1973.

[13]D.Panton.Aflexibleapproachtodigitalstereomapping.

PhEngRS,44(12):1499–1512,December1978.

[14]R.SzeliskiandD.Scharstein.Symmetricsub-pixelstereo

matching.InECCV02,pageII:525ff.,2002.

[15]O.Veksler.Stereomatchingbycompactwindowsviamini-mumratiocycle.InICCV01,pagesI:540–547,2001.

[16]P.ViolaandM.Jones.Robustreal-timefacedetection.In

ICCV01,pageII:747,2001.

Acknowledgments

WewouldliketothankProf.ScharsteinandDr.Szeliskiforprovidingthestereoimagesandevaluation.

References

[1]S.BirchfieldandC.Tomasi.Apixeldissimilaritymeasure

thatisinsensitivetoimagesampling.TPAMI,20(4):401–406,April1998.

[2]F.Crow.Summed-areatablesfortexturemapping.InPro-ceedingsofSIGGRAPH,1984.

[3]O.Faugeras,B.Hotz,H.Mathieu,T.Vi´eville,Z.Zhang,

P.Fua,E.Th´eron,L.Moll,G.Berry,J.Vuillemin,P.Bertin,andC.Proy.Realtimecorrelation-basedstereo:algorithm,implementatinosandapplications.TechnicalReport2013,INRIA,1993.