## 3 Experiments
### Middlebury Dataset  
The Middlebury benchmark [9] provides a standard to compare different stereo matching algorithms. In the early datasets [35; 39], stereo images are created under restricted conditions for indoor scenes with ground truth generated by structured light. Many approaches achieve quite satisfactory results on these stereo pairs. Therefore, they provide more challenging stereo pairs for natural real scenes with large low textural regions. Stereo Pairs from Restricted Conditions: We use the four testing stereo images (_Tsukuba, Venus, Cones, Teddy_) used for evaluation on the benchmark and stereo images in both Middlebury 2005 and Middlebury 2006 datasets [9; 35] to evaluate the performances of our method, SGM and its variants. As most of these stereo images contain rich texture, we adopt _intensity + gradient_ to compute matching cost of corresponding pixels. For pixel \((i,j)\) at candidate disparity \(l\), the matching cost can be formulated as  
\[C_{i,j}(l)=(1-\lambda)\cdot\min(||I_{i,j}-I_{i-l,j}^{{}^{\prime}}||,\tau_{1})+ \lambda\cdot\min(||\
abla_{x}I_{i,j}-\
abla_{x}I_{i-l,j}^{{}^{\prime}}||,\tau_ {2}) \tag{17}\]  
Here, \(\
abla_{x}\) is the gradient in \(x\) direction, \(I_{i,j}\) and \(I_{i-l,j}^{{}^{\prime}}\) are the color vectors of pixel \((i,j)\) and corresponding pixel \((i-l,j)\) in the other image. Parameter \(\lambda\) balances the intensity term and the gradient term, and \(\tau_{1}\), \(\tau_{2}\) corresponds to the truncation values for these two terms, respectively. In our experiments, they are 0.89, 7/255 and 2/255 and remain the same in various methods. Then we perform optimization along each tree and fuse the outputs to obtain the aggregated cost. The initial disparity image is obtained by Equation (5). Table 2 presents the percentage of error pixel in non-occluded region and corresponding rankings for kinds of cost aggregation methods. Our method achieves the smallest average error rate and ranks the first among these approaches. BF and GF are local methods which aggregate costs in a local support window, since they generate high quality disparity images for stereo pairs containing a lot of details, such as _Cones_ and _Rocks2_. GF attempts  
Figure 4: _Stable_ disparities propagate along a minimum spanning tree. Blue and blown nodes correspond to _stable_ and _unstable_ pixels respectively. (**a**) Disparities of _Stable_ pixels propagate from leaf nodes to root node. (**b**) Disparities of _Stable_ pixels propagate from root node to leaf nodes. to preserve the structure of reference image in the filtering result, since GF shows better edge-preserving property than BF and achieves lower error rate. NL and ST are tree-based filtering approaches which aggregate cost in the whole image by recursively traversing the tree in two passes. Although all pixels are taken into account, they only use intensity difference to estimate the similarity of any two pixels on the tree and tend to overuse smooth constraint in low textural area, resulting in an increase of error rate. SGM and its variants, including our method, incorporate information from multiple directions and produce more accurate disparity image. Table 3 lists average error rates of several non-local cost aggregation methods. We can see that our method outperforms other approaches in most metrics. The error rate of SGM8 is lower than that of SGM4 for the initial disparity image. The reason for this is that SGM8 propagates information along eight directions; thus, reliable information can propagate into occluded and weakly textured regions to deal with the ambiguity of these pixels. However, the error rates of final disparity image for SGM4 is lower than that of SGM8. One reason for this is that most of these stereo pairs are high texture images, so that aggregated costs along four directions are robust enough to generate accurate disparity image for these stereo pairs. Another reason is that streak artifacts in the results of SGM8 are more severe than that of SGM4.