Stereo Matching: Evaluation of Three Algorithms and Two Cost Functions

The stereo matching or correspondence problem, which consists of finding the disparity map of a pair of stereo images, is an integral part of many computer vision techniques. For instance, Digital Elevation Model (DEM) generation from Synthetic Aperture Radar (SAR) images uses stereoscopy to deal with steep mountain regions that contain forests, and stereo matching is an integral part of the stereoscopy technique. Furthermore, automatic stereo processing, for which stereo matching is a critical component, is heavily used in obstacle detection and avoidance for unmanned vehicles and automated manufacturing processes, among many other applications. Stereo matching algorithms perform a combination of the following steps: cost computation, cost (support) aggregation, disparity computation/optimization, and disparity refinement. Depending upon how they compute/optimize the disparity of each pixel, they are classified as local or global algorithms. Due to its computational complexity, stereo matching is one of the most researched topics in computer vision. This thesis performs a comparative performance study of six stereo matching codes. The codes employ (i) three different minimization algorithms, full version of graph cut, one iteration version of graph cut, and simulated annealing, and (ii) two cost functions, which are based on Absolute Difference (AD) and Normalized Cross Correlation (NCC). In addition, it includes the results of experiments that determine parameters of a cost function based on Zero Mean Normalized Cross Correlation (ZNCC). The execution time, final cost of minimization, output quality, and power and energy consumption are the performance metrics used in the evaluation. The results of the study show that the graph-cut stereo matching codes, in comparison to the simulated annealing codes, provide savings in execution time and energy consumption of up to 35%. In addition, it was discovered that by using a version of the graph-cut codes that performs a single alpha expansion (GC-1-Iter), the savings in execution time and energy increase up to 85%. Furthermore, the graph-cut codes provide better disparity maps, with up to 52% lower root mean square (RMS) errors than those produced by their simulated annealing counterparts. This demonstrates that the graph-cut stereo matching algorithm is promising for applications executed on field-deployable systems and other energy-constrained systems