Linear time manageable edge-aware filtering on complementary tree structures.

Typical non-local edge-aware filtering methods build long-range connections by deriving a minimum spanning tree (MST) from the input image. Each pixel on the MST only connects to a sub-set of pixels in the 8-connected neighborhood, resulting in piece-wise constant output with fake edges among sub-trees for the unbalanced information propagation along eight directions. In this paper, we propose two complementary spatial trees to incorporate information from the entire image. The structure of each tree depends on the spatial relationships of neighboring pixels. The distances between any two pixels in both spatial space and intensity space are the shortest distances on each tree. We introduce an efficient algorithm to recursively compute the output and the normalization constant on each tree with linear time complexity. For each pixel, we first calculate the outputs from eight subtrees and then fuse them to obtain the result on each tree structure. The final filtering output of our method is the weighted average of the results from two complementary spatial trees. Moreover, we present a distance mapping scheme to adjust the intensity distance between neighboring pixels, enabling our method to filter out a manageable degree of low-amplitude structures while sharpening major edges. Extensive experiments in graphic applications, such as image denoising, JPEG artifact removal, tone mapping, detail enhancement, and colorization, demonstrate the effectiveness and versatility of our method. [Display omitted] • Novel complementary trees to estimate the geodesic distance between any two pixels. • Efficient algorithms with linear time complexity to compute the weighted average of all pixels in the input image. • A distance mapping scheme in intensity space to manageably filter out low-amplitude structures. • Quantitative evaluation and qualitative comparison on various graphic applications to show the effectiveness and the versatility of our approach. [ABSTRACT FROM AUTHOR]