# Linear Time Non-Local Cost Aggregation on Complementary Spatial Tree Structures
###### Abstract
Thus, fake edges appear when filtering along these MST-based non-local filters. Domain transform (DT) [19] defined an isometric transformation between a real line and curves on a 2D image manifold, which means that 1D edge-aware filtering can be implemented with linear time complexity. [PERSON] et al. [20] utilized the 1D edge-aware filter in DT to perform cost aggregation. Although it is very efficient, informative messages can only propagate along the horizontal or vertical directions in each pass, resulting in stripe artifacts in the disparity image. Our goal is to present novel tree structures which can propagate information along all edges efficiently. This work is motivated by two key observations: first, the similarity of neighboring pixels can be evaluated by their intensity distance since there is no need to extract the tree structure from the guidance image with extra computation; second, adjacent pixels with similar intensity tend to possess similar disparities, which suggests that informative messages should propagate along all edges. With the rapid advance in machine learning, many approaches [21; 22; 23; 24] take advantage of CNNs to extract features with semantic information or to perform cost aggregation directly. Deep CNNs with a large receptive field can extract high-level semantic information from the guidance image, so that the matching cost generated by deep features shows better robustness, even for pixels in homogeneous areas. However, features learned by CNNs have low positioning accuracy and are also less distinctive than handcrafted features. Therefore, an investigation of these two kinds of features in evaluating the similarity of corresponding pixels is necessary. The integration of handcrafted features and features learned by CNNs may help to improve the generalization ability of deep learning-based approaches. In this paper, we first propose an efficient non-local cost aggregation method that performs filtering along two complementary spatial tree structures, as shown in Figure 1a,b. The weight between any two pixels on each tree is the sum of the geodesic distances in both the spatial and intensity spaces and the final aggregated cost is the sum of the outputs from these two trees. The two spatial trees complement each other to balance the information propagated in all directions. The filtering procedure along each tree is implemented by aggregating costs along eight sub-trees. The eight sub-trees for Figure 1a are shown in (c) and (d), and they are (e) and (f) for Figure 1b. The filtering output on each sub-tree can be obtained by recursively aggregating costs from leaf nodes to the root node with linear time complexity. The only difference between performing cost aggregation along these two trees is filtering order. Experimental results in stereo matching and optical flow estimation validate the effectiveness of our method. Then, we compare handcrafted features and deep features extracted by CNNs in computing matching costs. In summary, our main contributions are:  
* Novel complementary spatial tree structures are proposed to perform non-local cost aggregation. * Linear time complexity algorithms are presented to aggregate informative messages in all directions. * A comparison of handcrafted features and deep features extracted by CNNs in computing matching costs. * Experimental results in stereo matching and optical flow estimation show the effectiveness of our approach, which turns out our method outperforms typical MST-based non-local cost aggregation methods on the Middlebury [8] and KITTI [25; 26] datasets. The rest of this paper is organized as follows. We elaborate on our linear time non-local cost aggregation method based on two complementary spatial tree structures in Section 2. In Section 3, we provide the implementation and computational complexity of our algorithm. Experimental comparisons showing the superiority of our method are given in Section 4. Conclusion and future work are presented in Section 5.