A Taxonomy and Evaluation of Dense Two-Frame …

1 A Taxonomy and Evaluation of Dense Two-FrameStereo correspondence AlgorithmsDaniel ScharsteinRichard SzeliskiDept. of Math and Computer ScienceMicrosoft ResearchMiddlebury CollegeMicrosoft CorporationMiddlebury, VT 05753 Redmond, WA matching is one of the most active research areas incomputer vision. While a large number of algorithms forstereo correspondence have been developed, relatively lit-tle work has been done on characterizing their this paper, we present a Taxonomy of Dense , two-framestereo methods. Our Taxonomy is designed to assess the dif-ferent components and design decisions made in individualstereo algorithms. Using this Taxonomy , we compare exist-ing stereo methods and present experiments evaluating theperformance of many different variants. In order to estab-lish a common software platform and a collection of datasets for easy Evaluation , we have designed a stand-alone,flexible C++ implementation that enables the Evaluation ofindividual components and that can easily be extended to in-clude new algorithms.

2 We have also produced several newmulti- frame stereo data sets with ground truth and are mak-ing both the code and data sets available on the Web. Finally,we include a comparative Evaluation of a large set of today sbest-performing stereo IntroductionStereo correspondence has traditionally been, and continuesto be, one of the most heavily investigated topics in computervision. However, it is sometimes hard to gauge progress inthe field, as most researchers only report qualitative resultson the performance of their algorithms. Furthermore, a sur-vey of stereo methods is long overdue, with the last exhaus-tive surveys dating back about a decade [7, 37, 25]. Thispaper provides an update on the state of the art in the field,with particular emphasis on stereo methods that (1) operateon two frames under known camera geometry, and (2) pro-duce adensedisparity map, , a disparity estimate at goals are two-fold:1.

3 To provide ataxonomyof existing stereo algorithmsthat allows the dissection and comparison of individualalgorithm components design decisions;2. To provide atest bedfor the quantitative evaluationof stereo algorithms. Towards this end, we are plac-ing sample implementations of correspondence algo-rithms along with test data and results on the Web emphasize calibrated Two-Frame methods in order to fo-cus our analysis on the essential components of stereo cor-respondence. However, it would be relatively straightfor-ward to generalize our approach to include many multi-framemethods, in particular multiple-baseline stereo [85] and itsplane-sweep generalizations [30, 113].The requirement of Dense output is motivated by modernapplications of stereo such as view synthesis and image-based rendering, which require disparity estimates in all im-age regions, even those that are occluded or without , sparse and feature-based stereo methods are outsidethe scope of this paper, unless they are followed by a surface-fitting step, , using triangulation, splines, or seed-and-grow begin this paper with a review of the goals and scope ofthis study, which include the need for a coherent taxonomyand a well thought-out Evaluation methodology.

4 We alsoreviewdisparity spacerepresentations, which play a centralrole in this paper. In Section 3, we present our taxonomyof Dense Two-Frame correspondence algorithms. Section 4discusses our current test bed implementation in terms ofthe major algorithm components, their interactions, and theparameters controlling their behavior. Section 5 describesour Evaluation methodology, including the methods we usedfor acquiring calibrated data sets with known ground Section 6 we present experiments evaluating the differentalgorithm components, while Section 7 provides an overallcomparison of 20 current stereo algorithms. We conclude inSection 8 with a discussion of planned future Motivation and scopeCompiling a complete survey of existing stereo methods,even restricted to Dense Two-Frame methods, would be aformidable task, as a large number of new methods are pub-lished every year. It is also arguable whether such a surveywould be of much value to other stereo researchers, besidesbeing an obvious catch-all reference.

5 Simply enumeratingdifferent approaches is unlikely to yield new , a comparative Evaluation is necessary to assessthe performance of both established and new algorithms andto gauge the progress of the field. The publication of a simi-lar study by Barronet al.[8] has had a dramatic effect on thedevelopment of optical flow algorithms. Not only is the per-formance of commonly used algorithms better understoodby researchers, but novel publications have to improve insome way on the performance of previously published tech-niques [86]. A more recent study by Mitiche and Bouthemy[78] reviews a large number of methods for image flow com-putation and isolates central problems, but does not provideany experimental stereo correspondence , two previous comparative pa-pers have focused on the performance of sparse featurematchers [54, 19]. Two recent papers [111, 80] have devel-oped new criteria for evaluating the performance of densestereo matchers for image-based rendering and tele-presenceapplications.

6 Our work is a continuation of the investiga-tions begun by Szeliski and Zabih [116], which comparedthe performance of several popular algorithms, but did notprovide a detailed Taxonomy or as complete a coverage ofalgorithms. A preliminary version of this paper appearedin the CVPR 2001 Workshop on stereo and Multi-BaselineVision [99].An Evaluation of competing algorithms has limited valueif each method is treated as a black box and only finalresults are compared. More insights can be gained by exam-ining the individual components of various algorithms. Forexample, suppose a method based on global energy mini-mization outperforms other methods. Is the reason a betterenergy function, or a better minimization technique? Couldthe technique be improved by substituting different matchingcosts?In this paper we attempt to answer such questions byproviding a Taxonomy of stereo algorithms. The taxonomyis designed to identify the individual components and de-sign decisions that go into a published algorithm .

7 We hopethat the Taxonomy will also serve to structure the field andto guide researchers in the development of new and Computational theoryAny vision algorithm , explicitly or implicitly, makes as-sumptions about the physical world and the image formationprocess. In other words, it has an underlying computationaltheory [74, 72]. For example, how does the algorithm mea-sure the evidence that points in the two images match, ,that they are projections of the same scene point? One com-mon assumption is that of Lambertian surfaces, , surfaceswhose appearance does not vary with viewpoint. Some al-gorithms also model specific kinds of camera noise, or dif-ferences in gain or important are assumptions about the worldor scene geometry and the visual appearance of from the fact that the physical world consistsof piecewise-smooth surfaces, algorithms have built-insmoothness assumptions (often implicit) without which thecorrespondence problem would be underconstrained and ill-posed.

8 Our Taxonomy of stereo algorithms, presented in Sec-tion 3, examines both matching assumptions and smoothnessassumptions in order to categorize existing stereo , most algorithms make assumptions about cameracalibration and epipolar geometry. This is arguably the best-understood part of stereo vision; we therefore assume inthis paper that we are given a pair of rectified images asinput. Recent references on stereo camera calibration andrectification include [130, 70, 131, 52, 39]. RepresentationA critical issue in understanding an algorithm is the represen-tation used internally and output externally by the stereo correspondence methods compute a univalueddisparity functiond(x,y)with respect to a reference image,which could be one of the input images, or a cyclopian view in between some of the approaches, in particular multi-view stereo meth-ods, use multi-valued [113], voxel-based [101, 67, 34, 33,24], or layer-based [125, 5] representations.

9 Still other ap-proaches use full 3D models such as deformable models[120, 121], triangulated meshes [43], or level-set methods[38].Since our goal is to compare a large number of methodswithin one common framework, we have chosen to focus ontechniques that produce a univalueddisparity mapd(x,y)as their output. Central to such methods is the concept of adisparity space(x,y,d). The termdisparitywas first intro-duced in the human vision literature to describe the differ-ence in location of corresponding features seen by the leftand right eyes [72]. (Horizontal disparity is the most com-monly studied phenomenon, but vertical disparity is possibleif the eyes are verged.)In computer vision, disparity is often treated as synony-mous with inverse depth [20, 85]. More recently, several re-searchers have defined disparity as a three-dimensional pro-jective transformation (collineation or homography) of 3-Dspace(X,Y,Z).

10 The enumeration of all possible matchesin such a generalized disparity space can be easily achievedwith aplane sweepalgorithm [30, 113], which for everydisparitydprojects all images onto a common plane using2a perspective projection (homography). (Note that this isdifferent from the meaning of plane sweep in computationalgeometry.)In general, we favor the more generalized interpretationof disparity, since it allows the adaptation of the search spaceto the geometry of the input cameras [113, 94]; we plan touse it in future extensions of this work to multiple images.(Note that plane sweeps can also be generalized to othersweep surfaces such as cylinders [106].)In this study, however, since all our images are taken on alinear path with the optical axis perpendicular to the cameradisplacement, the classical inverse-depth interpretation willsuffice [85]. The(x,y)coordinates of the disparity spaceare taken to be coincident with the pixel coordinates of areference imagechosen from our input data set.