# Linear Time Non-Local Cost Aggregation on Complementary Spatial Tree Structures
## 4 Results and Discussions
### Stereo Matching
#### 4.1.1 Middlebury Dataset  
The Middlebury dataset contains kinds of indoor artificial scenes taken under a controlled environment with pixel-level accuracy ground truth generated by structured light. We adopt pixel-based truncated absolute differences of both color vector and gradient to measure the proximity of matching pixels. Thus, the initial matching cost of pixel \((i,j)\) at disparity \(l\) can be computed by  
\[\mathrm{C}_{i,j}(l)=(1-\lambda)\cdot\min(||l_{i,j}-l_{i-l,j}^{\prime}||,\tau_{ 1})+\lambda\cdot\min(||\
abla_{x}l_{i,j}-\
abla_{x}l_{i-l,j}^{\prime}||,\tau_{ 2}), \tag{9}\] \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Method** & **NL** & **ST** & **GF (r = 9)** & **GF (r = 18)** & **FCGF** & **BF (r = 9)** & **BF (r = 18)** & **Ours** \\ \hline Time (ms) & 1.6 & 2.0 & 145 & 145 & 268 & 1075 & 4638 & 40 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Running time comparison of typical cost aggregation methods for each cost slice. where \(I_{i,j}\) and \(I_{i-l,j}^{{}^{\prime}}\) are the color vectors of two candidate matching pixels \((i,j)\) and \((i-l,j)\) in the left and right images, \(\
abla_{x}\) is the gradient operation in the \(x\) direction. \(\lambda\) balances the gradient and color terms. \(\tau_{1}\), and \(\tau_{2}\) correspond to the truncation values of these two terms. In our experiments, \(\lambda\), \(\tau_{1}\), and \(\tau_{2}\) are 0.89, 7/255, and 2/255, respectively. Both left and right images are used as guidance images to generate corresponding disparity images. We use the left-right consistency check to classify pixels into _stable_ and _unstable_, and the non-local refinement method [16] is adopted to propagate reliable disparities from _stable_ pixels to _unstable_ ones. Table 3 lists the error rate of non-occluded and all regions for typical cost aggregation methods. Our method outperforms BF, LRNL, FCGF, NL, DT, and ST at all metrics. NL, ST, and FCGF are all tree-based non-local filters. ST enforces tight connections for pixels in a neighborhood by building pixel-level and region-level tree structures so that the over-smoothing problem of NL can be alleviated, leading to better results. FCGF reduces the supports of neighboring pixels and generates noisy disparity images. DT can only propagate informative messages along the horizontal or vertical direction in each pass since it produces the worst results among these approaches. Both BF and GF take advantage of local structures to evaluate the similarity of neighboring pixels. However, GF adopts a linear model aiming to preserve the structure of the guidance image so that it produces more satisfactory results. We perform cost aggregation on two spatial trees, which balances the information propagated along all directions. After post-processing, our method generates competitive or even better results than GF. Moreover, our approach is more efficient than GF, as shown in Table 2.  
Figure 3 presents the final disparity images of typical cost aggregation methods. All these approaches can correctly estimate the disparities of pixels in highly textured regions. BF and GF assume all pixels in the support window on a disparity plane. NL and FCGF utilize the MST of the input image to build long-range connections. However, they tend to overuse the piece-wise constant assumption. Thus, BF, GF, NL, and FCGF produce many erroneous disparities in slant surfaces, as indicated by the boxes in the first row of Figure 3b-e. Compared with BF and GF, NL and FCGF weaken the constraints from neighboring pixels. Hence, NL and FCGF produce better results in regions containing fine-scale details, as indicated by the boxes in the second row in Figure 3b-e. Our method overcomes these shortages by recursive filtering and balancing the information propagated in all directions. Thus, our approach can successfully preserve fine-scale details in highly textured regions and alleviate the over-smoothing problem in slant surfaces, as shown in Figure 3f.