# Linear Time Non-Local Cost Aggregation on Complementary Spatial Tree Structures
###### Abstract  
Studies on many dense correspondence tasks in the field of computer vision attempt to find spatially smooth results. A typical way to solve these problems is by smoothing the matching costs using edge-preserving filters. However, local filters generate locally optimal results, in that they only take the costs over a small support window into account, and non-local filters based on a minimum spanning tree (MST) tend to overuse the piece-wise constant assumption. In this paper, we propose a linear time non-local cost aggregation method based on two complementary spatial tree structures. The geodesic distances in both the spatial and intensity spaces along the tree structures are used to evaluate the similarity of pixels, and the final aggregated cost is the sum of the outputs from these two trees. The filtering output of a pixel on each tree can be obtained by recursively aggregating the costs along eight sub-trees with linear time complexity. The only difference between the filtering procedures on these two spatial tree structures is the order of the filtering. Experimental results in optical flow estimation and stereo matching on the Middlebury and KITTI datasets demonstrate the effectiveness and efficiency of our method. It turns out that our method outperforms typical non-local filters based on the MST in cost aggregation. Moreover, a comparison of handcrafted features and deep features learned by convolutional neural networks (CNNs) in calculating the matching cost is also provided. The code will be available soon. complementary tree structure; linear time complexity; non-local edge-aware filter; recursive propagation; stereo matching; cost aggregation +
Footnote †: journal:  
ccs  
methods [10; 11; 12]. The weight between any two pixels depends on the spatial affinity and the intensity similarity. [PERSON] and [PERSON] [12] introduced the bilateral filter (BF) into stereo matching, which computes the weights from both the left and right support windows. However, the computational cost of BF is \(O(r^{2})\) time, where \(r\) is the radius of the support window. [PERSON] et al. [13] proposed a local linear model to build the relationship between the guidance image and filtering output; they named this a guided filter (GF). It has linear time complexity and outperforms many local approaches in both speed and accuracy [14]. However, the squared window used in BF and GF lacks spatial adaptivity, which results in many erroneous disparities at boundaries. In order to find a structure adaptive support window, [PERSON] et al. [15] adaptively built an upright cross skeleton for each pixel with varying arm lengths, relying on the connectivity constraint and color similarity. They also presented an efficient algorithm to construct a shape-adaptive support window for each pixel on the fly, while local filtering methods only take pixels in the support region into account, struggling to deal with the ambiguity in large homogeneous regions. Non-local edge-aware filters extend the support region to the whole image by extracting tree structures from the guidance image. The filtering procedure is recursively performed along these trees with linear time complexity. [PERSON] [16] proposed the non-local filter (NL), which derives an MST from the guidance image by removing large gradients. It is more natural to measure the similarity of pixels along the MST. However, the structure of an MST is susceptible to highly textured regions. [PERSON] et al. [17] constructed the segment tree (ST) by creating tree structures at both the pixel level and region level. [PERSON] et al. [18] replaced the box filter in GF by an MST to extend the support region of GF to the whole image; they called this a fully connected guided filter (FCGF). However, it tends to weaken the support from neighboring pixels and also results in an increase in the computational cost. Another drawback of these MST-based non-local filters is that messages only propagate along a part of the edges in a four-connected neighborhood.