It is challenging to extend the support region of state-of-the-art local edge-preserving filtering approaches to the entire input image on account of huge memory cost and heavy computational burden. In this paper, we propose an O(N) time recursive non-local edge-aware filter. A novel graph and a linear time algorithm are presented to effectively propagate information across the entire image. In this graph, information is propagated along all directions to avoid visual artifacts. Both the intensity similarity and the spatial affinity are utilized to estimate the similarity of neighboring pixels, and the distance of any two pixels is the length of the path between these two pixels on a binary tree. Specifically, the input image is filtered at four directions, namely left-to-right, right-to-left, top-to-bottom and bottom-to-top. In each pass, the un-normalized output and the normalization constant of the root node are computed recursively from leaf nodes to the root node on a binary tree in linear time. The filtering output is the average of the outputs for these four directions. A comparison with other non-local edge-aware filters is presented to show the advantages of our approach. Extensive experiments demonstrate that our recursive non-local edge-preserving filter is effective in a variety of computer vision and image processing applications, including edge-aware filtering, detail enhancement, stylization, and stereo matching.

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.