1、Learnable Tree Filter for Structure-preserving Feature TransformLin Song1 Yanwei Li2,3 Zeming Li4Gang Yu4Hongbin Sun1 Jian Sun4Nanning Zheng11 Institute of Artificial Intelligence and Robotics, Xian Jiaotong Univeristy.2 Institute of Automation, Chinese Academy of Sciences.3 University of Chinese Ac

2、ademy of Sciences. 4 Megvii Inc. (Face+). , ,hsun, , lizeming, yugang, AbstractLearning discriminative global features plays a vital role in semantic segmentation. And most of the existing methods adopt stacks of l

3、ocal convolutions or non-local blocks to capture long-range context. However, due to the absence of spatial struc- ture preservation, these operators ignore the object details when enlarging receptive fields. In this paper, we propose the learnable tree filter to form a generic tree filter- ing modu

4、le that leverages the structural property of minimal spanning tree to model long-range dependencies while preserving the details. Furthermore, we propose a highly efficient linear-time algorithm to reduce resource consumption. Thus, the designed modules can be plugged into existing deep neural netwo

5、rks conveniently. To this end, tree filtering modules are embedded to formulate a unified framework for semantic segmentation. We conduct extensive ablation studies to elaborate on the effectiveness and efficiency of the proposed method. Specifically, it attains bet- ter performance with much less o

6、verhead compared with the classic PSP block and Non-local operation under the same backbone. Our approach is proved to achieve consistent improvements on several benchmarks without bells-and-whistles. Code and models are available at/StevenGrove/TreeFilter-Torch.1 IntroductionScene

7、perception, based on semantic segmentation, is a fundamental yet challenging topic in the vision field. The goal is to assign each pixel in the image with one of several predefined categories. With the developments of convolutional neural networks (CNN), it has achieved promising results using impro

8、ved feature representations. Recently, numerous approaches have been proposed to capture larger receptive fields for global context aggregation 15, which can be divided into local and non-local solutions according to their pipelines.Traditional local approaches enlarge receptive fields by stacking c

9、onventional convolutions 68 or their variants (e.g., atrous convolutions 9, 2). Moreover, the distribution of impact within a receptive field in deep stacks of convolutions converges to Gaussian 10, without detailed structure preservation (the pertinent details, which are proved to be effective in f

10、eature representation 11, 12). Considering the limitation of local operations, several non-local solutions have been proposed to model long-range feature dependencies directly, such as convolutional methods (e.g., non-local operations 13, PSP 3 and ASPP modules 2, 14, 15) and graph-based neural netw

11、orks 16 18. However, due to the absence of structure-preserving property, which considers both spatialEqual contribution. This work was done in Megvii Research.Corresponding author.33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada.Figure 1: Toy illustration o

12、f the tree filtering module. Given a detail-rich feature map from low-level stage, we first measure the dissimilarity between each pixel and its quad neighbours. Then, the MST is built upon the 4-connected planar graph to formulate a learnable tree filter. The edge between two vertices denotes the d

13、istance calculated from high-level semantics. Red edges indicate the close relation with vertex k. The intra-class inconsistency could be alleviated after feature transform.distance and feature dissimilarity, the object details are still neglected. Going one step further, the abovementioned operatio

14、ns can be viewed as coarse feature aggregation methods, which means they fail to explicitly preserve the original structures when capturing long-range context cues.In this work, we aim to fix this issue by introducing a novel network component that enables efficient structure-preserving feature tran

15、sform, called learnable tree filter. Motivated by traditional tree filter 19, a widely used image denoising operator, we utilize tree-structured graphs to model long- range dependencies while preserving the object structure. To this end, we first build the low-level guided minimum spanning trees (MS

16、T), as illustrated in Fig. 1. Then the distance between vertices in MST are calculated based on the high-level semantics, which can be optimized in backpropagation. For example, the dissimilarity wk,m between vertex k and m in Fig. 1 is calculated from semantic- rich feature embeddings. Thus, combin

17、ed with the structural property of MST, the spatial distance and feature dissimilarity have been modeled into tree-structured graph simultaneously (e.g., the distance between vertex k and its spatially adjacent one n has been enlarged in Fig. 1, for that more edges with dissimilarities are calculate

18、d when approaching n). To enable the potential for practical application, we further propose an efficient algorithm which reduces theO(N 2) complexity of bruteforce implementation to linear-time consumption. Consequently, different from conditional randomfields (CRF) 2022, the formulated modules can

19、 be embedded into several neural network layers for differentiable optimization.In principle, the proposed tree filtering module is fundamentally different from most CNN based methods. The approach exploits a new dimension: tree-structure graph is utilized for structure- preserving feature transform

20、, bring detailed object structure as well as long-range dependencies. With the designed efficient implementation, the proposed approach can be applied for multi-scale feature aggregation with much less resource consumption. Moreover, extensive ablation studies have been conducted to elaborate on its

21、 superiority in both performance and efficiency even comparing with PSP block 3 and Non-local block 13. Experiments on two well-known datasets (PASCAL VOC 2012 23 and Cityscapes 24) also prove the effectiveness of the proposedmethod.2 Learnable Tree FilterTo preserve object structures when capturing

22、 long-range dependencies, we formulate the proposed learnable tree filter into a generic feature extractor, called tree filtering module. Thus, it can be easily embedded in deep neural networks for end-to-end optimization. In this section, we firstly introduce the learnable tree filtering operator.

23、And then the efficient implementation is presented for practical applications. The constructed framework for semantic segmentation is elaborated at last.2.1 FormulationFirst, we represent the low-level feature as a undirected graph G = (V, E), with the dissimilarity weight for edges. The vertices V

24、are the semantic features, and the interconnections of them can11be denoted as E. Low-level stage feature map, which contains abundant object details, is adopted as the guidance for 4-connected planar graph construction, as illustrated in Fig.1. Thus, a spanning tree can be generated from the graph

25、by performing a pruning algorithm to remove the edges with the substantial dissimilarity. From this perspective, the graph G turns out to be the minimum spanning tree (MST) whose sum of dissimilarity weights is minimum out of all spanning trees. The property of MST ensures preferential interaction a

26、mong similar vertices. Motivated by traditional tree filter 19, a generic tree filtering module in the deep neural network can be formulated as:yi = 1zXS (Ei,j ) f (xj) .(1)i jWhere i and j indicatetheindexofvertices, denotesthesetofallvertices in thetreeG, x represents the input encoded features an

27、d y means the output signal sharing the same shape with x. Ei,j is a hyperedge which contains a set of vertices traced from vertex i to j in G. The similarity function S projects the features of the hyperedge into a positive scalar value, as described in Eq. 2. The unary function f () represents the

28、 feature embedding transformation. zi is the summation of similarityS(Ei,j) alone with j to normalize theresponse.S (Ei,j) = exp (D (i, j) ,where D (i, j) = D (j, i) =X(k,m)Ei,jk,m.(2)According to the formula in Eq. 1, the tree filtering operation can be considered as one kind of weighted-average fi

29、lter. The variable k,m indicates the dissimilarity between adjacent vertices (k and m) that can be computed by a pairwise function (here we adopt Euclidean distance). The distance D between two vertices (i and j) is defined as summation of dissimilarity k,m along the path in hyperedge Ei,j. Note tha

30、t D degenerates into spatial distance when is set to a constant matrix. Since actually measures pairwise distance in the embedded space, the aggregation along the pre-generated tree considers spatial distance and feature difference simultaneously.yi = 1ziXf (xj)YXYexp(k,m) ,where zi =exp(k,m) . (3)j

31、(k,m)Ei,jj (k,m)Ei,jmThe tree filtering module can be reformulated to Eq. 3. Obviously, the input feature xj and dissimi- larity k,m take responsibility for the output response yi. Therefore, the derivative of output with respect to input variables can be derived as Eq. 4 and Eq. 5. V i in Eq. 5 is

32、defined with the childrenof vertex m in the tree whose root node is the vertex i. yi = S (Ei,j) f (xj) ,(4)xjzixj yi = S (Ei,k ) S (Ek,m)X S (E) f (x ) y z.(5)k,mzik,mmjV im,jji mIn this way, the proposed tree filtering operator can be formulated as a differentiable module, which can be optimized by

33、 the backpropagation algorithm in an end-to-end manner.2.2 Efficient ImplementationLet N denotes the number of vertices in the tree G. The tree filtering module needs to be accumulated N times for each output vertex. For each channel, the computational complexity of brute force imple- mentation is O

34、(N 2) that is prohibitive for practical applications. Definition of the tree determinesthe absence of loop among the connections of vertices. According to this property, a well-designeddynamic programming algorithm can be used to speed up the optimization and inferenceprocess.We introduce two sequen

35、tial passes, namely aggregation and propagation, which are performed by traversing the tree structure. Let one vertex to be the root node. In the aggregation pass, the process is traced from the leaf nodes to the root node in the tree. For a vertex, its features do not update until all the children

36、have been visited. In the propagation pass, the features will propagate from the updatedvertex to their children recursively.XAggr()i = i +S (Ei,j) Aggr()j.(6)par(j)=iProp()i = Ag gr()ri = r(7)S Epar(i),i Prop()par(i) + 1 S2 Ei,par(i)Aggr()i)i 6=rThe sequential passes can be formulated into the recu

37、rsive operators for the input : the aggregation pass and the propagation pass are respectively illustrated in Eq. 6 and Eq. 7, where par(i) indicates the parent of vertex i in the tree whose root is vertex r. Prop()r is initialized from the updated value Aggr()r of root vertex r.Algorithm 1 Linear t

38、ime algorithm for Learnable Tree FilterInput: Tree GN(N 1)2; Input feature xRCN ; Pairwise distance RN ; Gradient of lossw.r.t. output feature RCN ; channel C, vertex N ; Set of vertices .Output: Output feature y; Gradient of loss w.r.t. input feature loss , w.r.t. pairwise distance loss .Preparatio

39、n:xr = Uniform(). RootvertexsampledwithuniformdistributionT =BFS(G, r). Breadth-firsttopologicalorderfor Aggr and PropJ = 1 R1N.All-onesmatrixfornormalizationcoefficientForward:1. , z = Aggr(f (x), J ). Aggregation from leaves to root2. , z = Prop(, z). Propagation from root to leaves3. y = /z. Norm

40、alizedoutputfeatureBackward:1. , = Aggr(/z, y/z). Aggregation from leaves to root2. , = Prop(, ). Propagation from root to leavesxx3. loss = f(x) . Gradientoflossw.r.t. input feature4. for i T r doj = par(i). Parentofvertex iis = i i + i i 2S(Ei,j)i i. Gradient of unnormalized output featureiz = izi

41、 + izi 2S(Ei,j )izi. Gradient of normalization coefficienti,ji ii,j loss = S(Ei,j ) P (s z ). Gradient of loss w.r.t. pairwise distanceendAs shown in the algorithm 1, we propose a linear-time algorithm for the tree filtering module, whose proofs are provided in the appendix. In the preparation stage

42、, we uniformly sample a vertex as the root and perform breadth-first sorting (BFS) algorithm to obtain the topological order of tree G. The BFS algorithm can be accelerated by the parallel version on GPUs and ensure the efficiency of the following operations.To compute the normalization coefficient,

43、 we construct an all-ones matrix as J. Since the embedded feature f (x) is independent of the matrix J, the forward computation can be factorized into two dynamic programming processes. Furthermore, we propose an efficient implementation for the backward process. To reduce the unnecessary intermedia

44、te process, we combine the gradient of module and loss function. Note that the output y and normalization coefficient z have been already computed in the inference phase. Thus the key of the backward process is to compute the intermediate variables and . The computation of these variables can be acc

45、elerated by the proposed linear time algorithm. And we adopt another iteration process for the gradient of pairwise distance.Figure 2: Overview of the proposed framework for semantic segmentation. The network is composed of a backbone encoder and a naive decoder. GAP denotes the extra global average

46、 pooling block. Multi-groups means using different feature splits to generate multiple groups of tree weights. The right diagram elaborates on the process details of a single stage tree filtering module, denoted as the green node in the decoder. Red arrows represent upsample operations. Best viewed

47、in color.Computational complexity. Since the number of batch and channel is much smaller than the vertices in the input feature, we only consider the influence of the vertices. For each channel, the computational complexity of all the processes in algorithm 1, including the construction process of M

48、ST and the computation of pairwise distance, isO(N ), which is linearly dependent on the numberof vertices. It is necessary to point out that MST can be built in linear time using Contractive Boruvkaalgorithm if given a planar graph, as is designed in this paper. Note that the batches and channels a

49、re independent of each other. For the practical implementation on GPUs, we can naturally perform the algorithm for batches and channels in parallel. Also, we adopt an effective scheduling scheme to compute vertices of the same depth on the tree parallelly. Consequently, the proposed algorithm reduce

50、s the computational complexity and time consumption dramatically.2.3 Network Architecture for SegmentationBased on the efficient implementation algorithm, the proposed tree filtering module can be easily embedded into deep neural networks for resource-friendly feature aggregation. To illustrate the

51、effectiveness of the proposed module, here we employ ResNet 8 as our encoder to build up a unified network. The encoded features from ResNet are usually computed with output stride 32. To remedy for the resolution damage, we design a naive decoder module following previous works 14, 15. In details,

52、the features in the decoder are gradually upsampled by a factor of 2 and summed with corresponding low-level features in the encoder, similar to that in FPN 25. After that, the bottom- up embedding functions in the decoder are replaced by tree filter modules for multi-scale feature transform, as int

53、uitively illustrated in Fig. 2.To be more specific, given a low-level feature map Ml in top-down pathway, which riches in instance details, a 4-connected planar graph can be constructed easily with the guidance of Ml. Then, the edges with substantial dissimilarity are removed to formulate MST using

54、the Boruvka 26 algorithm. High level semantic cues contained in Xl are extracted using a simplified embedding function (Conv 1 1). To measure the pairwise dissimilarity in Eq. 2 (l in Fig. 2), the widely used Euclideandistance 27 is adopted. Furthermore, different groups of tree weights l are genera

55、ted to capturecomponent dependent features, which will be analyzed in Sec 3.2. To highlight the effectiveness oftheproposedmethod, thefeaturetransformation f () issimplified to identitymapping, wheref (Xl) = Xl. Thus, the learnable tree filter can be formulated by the algorithm elaborated onSec. 2.1

56、. Finally, thelow-levelfeaturemap Ml isfusedwiththeoperationoutput yl usingpixel-wise summation. For multi-stage feature aggregation, the building blocks (green nodes in Fig. 1) are applied to different resolutions (Stage 1 to 3 in Fig. 1). An extra globalaveragepooling operation is added to capture

57、 global context and construct another tree filtering module (Stage 4). The promotion brought by the extra components will be detailed discussed in ablation studies.3 ExperimentsIn this section, we firstly describe the implementation details. Then the proposed approach will be decomposed step-by-step to reveal the effect of each component. Comparisons with several state-of-the-art benchmarks on PASCAL VOC 2012 23 and Cityscapes 24 are presented at last.3.1 Implementation DetailsFollowing traditional protocols 3, 15, 28, ResNet 8 is adopted as ou