# Linear Time Non-Local Cost Aggregation on Complementary Spatial Tree Structures
## 4 Results and Discussions
### Optical Flow Estimation  
Optical flow estimation aims to estimate the change in spatial location of objects with respect to time from image sequences. Supposing label \(l\) corresponding to vector \((u,v)\) denotes the motion in the \(x\) and \(y\) directions, the matching cost of pixel \((i,j)\) at label \(l\) can be computed by  
\[C_{i,j}(l)= (1-\lambda)\cdot\min(\parallel I_{i,j}-I_{i-u,j-v}^{{}^{\prime}} \parallel,\tau_{1})+\lambda\cdot\min(\parallel\] \[\
abla_{x}I_{i,j}-\
abla_{x}I_{i-u,j-v}^{{}^{\prime}}\parallel+ \parallel\
abla_{y}I_{i,j}-\
abla_{y}I_{i-u,j-v}^{{}^{\prime}}\parallel,\tau_ {2}), \tag{13}\]  
where \(\
abla_{y}\) is the gradient in the \(y\) direction. The other variables are the same as that in stereo matching, and the values of parameters \(\lambda\), \(\tau_{1}\), and \(\tau_{2}\) remain the same. We use left and right images as the guidance images to derive the initial flow fields and adopt the same strategies as stereo matching to refine them. To generate flow maps with sub-pixel accuracy, we use bicubic interpolation to upscale input images, which only leads to an increase in the label space. In practice, we use an upscaling parameter of four and compare our results with that of GF, which has been proven to outperform many cost aggregation methods in optical flow estimation. Figure 8 presents the initial flow maps of GF and our method with pixel-level accuracy on the Middlebury flow dataset [35]. These two methods can correctly estimate the motion of the main structures in the input image. The non-local property of our approach alleviates the ambiguity in homogeneous and occluded regions by encouraging informative messages to propagate in a wide range, as marked by the arrow in the bottom left. Another advantage  
Figure 6: Disparity images and corresponding error maps of our approach using the handcrafted feature and deep features to compute the matching costs on the KITTI 2012 dataset [25]. From top to bottom: Input reference image, disparity image using the handcrafted feature, disparity image using deep ones extracted by PSMNet [24], error map of disparity image using the handcrafted feature, error map of disparity image using deep features extracted by PSMNet [24]. Figure 7: Disparity images and corresponding error maps of our approach using the handcrafted and deep ones to compute the matching costs on the KITTI 2015 dataset [26]. is that our method can correctly preserve the discontinuities in flow maps where foreground and background are similar, as marked by the arrow in the top right. We quantitatively compare our method with GF on _Dimetrodon_, _Grove2_, and _RubberWhale_ images with ground truth provided by [PERSON] et al. [35]. The end-point error (EDE) and average angular error (AE) are adopted to evaluate the performance of these two methods. Table 8 presents the initial and final flow maps. Figure 9 shows examples of flow maps and close-ups with sub-pixel accuracy. Our method outperforms GF on _RubberWhale_ as it contains large textureless regions with unreliable matching costs. GF only utilizes matching costs over a local support window and fails to solve the ambiguity in these regions. GF obtains lower errors in both initial and final flow maps on _Groves2_. The reason is that our strategy attempts to approximate the geodesic distances in both spatial and intensity spaces. Thus, reliable information cannot propagate in a long range under these circumstances, leading to erroneous flow, as shown in the close-ups in Figure 9. However, this can be amended by reducing \(\beta\) in Equation (8). Moreover, our method is more efficient than GF.