{'fraction_non_alphanumeric': 0.03208007478510682, 'fraction_numerical': 0.012996192343646686, 'mean_word_length': 4.880933226065969, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ORDNet: Capturing Omni-Range Dependencies for Scene Parsing

Learning to capture dependencies between spatial positions is essential to many visual tasks, especially the dense labeling problems like scene parsing. Existing methods can effectively capture long-range dependencies with self-attention mechanism while short ones by local convolution. However, there is still much gap between long-range and short-range dependencies, which largely reduces the models' flexibility in application to diverse spatial scales and relationships in complicated natural scene images. To fill such a gap, we develop a Middle-Range (MR) branch to capture middle-range dependencies by restricting self-attention into local patches. Also, we observe that the spatial regions which have large correlations with others can be emphasized to exploit long-range dependencies more accurately, and thus propose a Reweighed Long-Range (RLR) branch. Based on the proposed MR and RLR branches, we build an Omni-Range Dependencies Network (ORDNet) which can effectively capture short-, middle- and long-range dependencies. Our ORDNet is able to extract more comprehensive context information and well adapt to complex spatial variance in scene images. Extensive experiments show that our proposed ORDNet outperforms previous state-of-the-art methods on three scene parsing benchmarks including PASCAL Context, COCO Stuff and ADE20K, demonstrating the superiority of capturing omni-range dependencies in deep models for scene parsing task.


I. INTRODUCTION
S CENE parsing [1] [2][3] [4] aims to divide the entire scene into different segments and predict the semantic category for each of them. It is a fundamental task in computer vision and image processing, challenged by the complexity of natural scenes that usually contain multiple elements of various categories, including discrete objects (e.g., person, cat) and stuff (e.g., sky, river, grass). The elements within a scene may be spatially dependent upon each other. For example, a ship usually appears on the sea rather than on the road. Such dependencies of spatial positions can be exploited to boost the prediction accuracy further. Mainstream scene parsing models built on Fully Convolutional Networks [5] incorporate carefully designed modules to exploit spatial context information. For example, Deeplabv2 [6] uses an Atrous Spatial Pyramid Pooling (ASPP) module to sample feature maps in parallel with different atrous rates to enlarge the receptive field of filters; PSPNet [1] performs pooling operations at multiple grid scales for the same goal. With a larger receptive field, these networks are able to extract broader scales of spatial context information. However, these methods model the dependencies between positions in an implicit way.
Self-attention mechanism [7] is able to capture long-range dependencies between positions explicitly and has been applied to scene parsing [8] [9] with a remarkable performance boost. The key idea behind self-attention is that the response at a certain position is a weighted sum of features at all the positions. In this way, all the positions are related to each other and arXiv:2101.03929v1 [cs.CV] 11 Jan 2021 provide the network with a global receptive field. Long-range dependencies captured by self-attention can be combined with short-range ones captured by local convolution, leading to rich context information for dense labeling problems.
However, long-range dependencies do not always work well for scene parsing tasks since a position is often less correlated with the positions far away from it, compared with those which are nearer. Moreover, information from distant positions may not be beneficial to building discriminative features. In Fig. 1(b), we visualize the attention map between a certain position and all the positions in the image computed in the self-attention process, where brighter color represents higher attention weight. The specified position is denoted as a green cross in Fig. 1(a). We find that in the conventional self-attention mechanism, the feature of this position would aggregate information from a wide area of the input image. For example, in the second row of (b), the position on the cat receives information from distant ones of the image, like those on the window and curtain. However, there is no apparent correlation between the window, curtain, and cat. Thus the long-range dependencies captured from these positions are not useful for the model to classify a certain position on the cat. When we restrict self-attention to a local patch of the image, the visualized attention map is more concentrated on the surrounding area of the specified position. For example, in the second row of Fig. 1 (c), self-attention is restricted to the bottom-right 1/4 patch of the image. The attention map between the specified position and all the positions within the patch mainly focuses on the head and body parts of the cat, indicating that useful middle-range dependencies among positions are captured. Benefiting from the close correlations within the same category, context information aggregated from these dependencies can severe as more valid guidance for the model to classify the specified position. Based on this observation, we devise a novel Middle-Range (MR) branch which restricts the self-attention mechanism to local patches of the input feature in order to fill the gap between long-range and short-range dependencies for complete context extraction.
Furthermore, we analyze the attention map generated with conventional self-attention and find that each position contributes different attention weights to others for context aggregation. For each position, the total value of attention weights that it contributes to others reveals its correlation with other positions as well as its importance to the global context. A larger value implies that the position has stronger correlations with most of the other positions. Thus, the features of positions contributing higher attention weights to others encode the common patterns of the whole image, including main elements appearing in the scene, large-area continuous background, etc. These patterns contain useful global context information which is crucial to scene understanding. By emphasizing features of the positions with larger contributions, long-range dependencies can be captured more accurately and adaptively to complicated scene elements, which can enhance the aggregation of global context by self-attention. We instantiate this idea with a Reweighed Long-Range (RLR) branch to modulate feature responses according to the attention weights contributions of each position.
With the newly proposed MR and RLR branches, we build an Omni-Range Dependencies Network (ORDNet) in which short-range, middle-range, and reweighed long-range dependencies collaborate seamlessly to achieve adaptability to diverse spatial region contents and relationships in natural scene images. The ORDNet is general and can be applied to any FCN backbone for learning more discriminative feature representations.
Our main contributions are summarized as follows: • We devise a Middle-Range (MR) branch which explicitly captures middle-range dependencies within local patches of scene image, filling the gap between long-range and short-range dependencies. • We also propose a Reweighed Long-Range (RLR) branch to emphasize features of the positions which encode common patterns, so that more accurate and adaptive long-range dependencies could be captured. • With the above two branches, we develop a novel Omni-Range Dependencies Network (ORDNet) which effectively integrates short-range, middle-range and reweighed long-range dependencies to extract comprehensive context information for accurate scene parsing. Our ORDNet outperforms previous state-of-the-art methods on three popular scene parsing benchmarks, including PASCAL-Context [10], COCO Stuff [11] and ADE20K [2] datasets, which well demonstrates its effectiveness.

A. Semantic Segmentation
The goal of semantic segmentation is to assign category labels to the pixels of foreground objects and stuff in the scene, rather than segmenting the entire scene as scene parsing does. By expanding the set of pre-defined categories on which the model to segment, semantic segmentation serves as a basic technology of scene parsing. In recent years, remarkable progress has been achieved based on Fully Convolutional Networks [5] (FCNs). FCN replaces the fully-connected layers of the image classification network (e.g., VGG16 [12]) with convolution layers and introduces transposed convolution and skip layers to predict pixel-level labels. The many pooling layers in FCN increase the receptive field of convolution filters, and meanwhile reduce the resolution of feature maps, leading to inaccurate semantic masks. In order to maintain the resolution of feature maps while enjoying the increased receptive field of convolution filters, DeepLab [13] integrates atrous convolution into CNN, which boosts segmentation performance largely and becomes the de-facto component of latter segmentation methods.
Many deep models [14][15] [16] have proposed various approaches to aggregate local spatial context information to refine the feature representations and achieved great performances. Later works further propose to aggregate the important multi-scale spatial context information based on the last feature map of an FCN backbone. For example, DeepLab v2 [6]   . Given an input image, the extracted feature X of a CNN backbone is fed into a Middle-Range (MR) branch and a Reweighed Long-Range (RLR) branch to capture the middle-range and reweighed long-range dependencies respectively. The outputs of these two branches are then concatenated along the channel dimension and fused by a 1 × 1 convolution. An identity skip connection of X is added to ease optimization. The fused feature is fed into an FCN Head to predict the logit map and then upsampled 8 times to obtain the final parsing mask.
image-level features into ASPP to get a global receptive field. PSPNet [1] performs pooling operations at multiple grid scales in order to aggregate multi-scale contextual information.
In addition to extracting context information from feature maps, EncNet [18] uses a Context Encoding Module which exploits semantic category prior information of the scenes to provide global contexts. Recent DANet [8] and CFNet [9] exploit the self-attention mechanism to effectively capture long-range dependencies, which outperform previous multiscale context aggregation methods in semantic segmentation and scene parsing. InterlacedSSA [19] proposes a factorized self-attention approach to approximately capture long-range dependencies with low computational costs, which achieves comparable performance with DANet and CFNet. Different from the above methods, in this paper we further propose to capture middle-range dependencies and reweighed longrange dependencies to provide richer semantic information than vanilla self-attention. Our Omni-Range Dependencies Network (ORDNet) can fill the semantic gap between original long-range and short-range dependencies, and also capture more accurate long-range dependencies by feature reweighing, achieving more comprehensive scene understanding.

B. Attention Mechanism
Attention mechanism is first introduced in [20] for neural machine translation, and later widely applied to various tasks like machine translation [21], VQA [22][23] [24] and image captioning [25]. [26] is the first work to apply self-attention for capturing long-range dependencies within input sentences, achieving noticeably boosted performance in machine translation. In [7], self-attention mechanism is further extended to vision tasks and a non-local network is proposed to capture long-range dependencies. For image tasks, self-attention methods compute the response at a position as a weighted sum of the features at all positions in the input feature maps, in which way the receptive field for the current position can go beyond local convolution kernels to cover the whole feature map. Self-attention mechanism is widely adopted in vision tasks such as semantic segmentation [8] [27], GANs [28] and image de-raining [29]. Inspired by [7], we propose a new self-attention architecture to capture omni-range dependencies of positions, where the Middle-Range (MR) branch restricts self-attention to patches to model middle-range dependencies and the Reweighed Long-Range (RLR) branch further emphasizes features of positions which encode common patterns of the image to obtain more accurate long-range dependencies. Compared with previous works, our method conforms better to practical spatial relations between semantic regions and achieves higher performance on several benchmarks.
In addition to self-attention, researchers also explore other attention methods to refine feature maps by adjusting their scales. SENet [30] utilizes a squeeze-and-excitation process to recalibrate feature channels with signals pooled from the entire feature maps. The first squeeze operator conducts global average pooling to generates a channel descriptor as the global information embedding. The second excitation operator maps the channel descriptor to a set of channel-specific weights with two successive fully connection layers. Finally, the channelspecific weights are multiplied with original features to rescale the channel responses. CBAM [31] and BAM [32] apply SE operation to both channel and spatial dimensions. Our proposed reweighed long-range branch serves as a spatial recalibration module to some extent. Compared with the spatial branch in CBAM, which is based on the single response of the current position, our RLR branch reweighs the feature responses according to correlations among all positions of the entire feature map so that positions encoding common patterns and main elements of the scene can be emphasized to form a more discriminative feature representation.

III. METHOD
A. Revisiting Self-Attention Self-attention mechanism computes the response at a position as a weighted sum of the features at all positions in the input feature maps. In this way, each position of the input feature can interact with others regardless of their spatial distance. The network can then effectively capture long-range dependencies among all the spatial positions. The overall workflow of selfattention is illustrated in the top area of Fig. 3. Given an input feature X = [x 1 ; x 2 ; ...; x HW ] ∈ R HW ×C and an output feature Y = [y 1 ; y 2 ; ...; y HW ] ∈ R HW ×C , which are

Self-Attention
Self-Attention  both reshaped to the matrix form, self-attention mechanism computes the output as

Self-Attention
where i is the index of a position of the output feature Y and j is the index enumerating all the positions of the input feature X. H, W and C are the height, width, and channel dimensions of X. N (X) serves as a normalization factor which is set as HW . v(·) is the value transform function implemented as a 1 × 1 convolution, v(x j ) ∈ R Cv is the transformed feature. attn ij indicates the attention weight contributed by position j to position i, which is defined as where q(·) and k(·) are the query and key transform functions, q(x i ) ∈ R Cq and k(x j ) ∈ R C k are transformed features respectively. In this work, we implement both q(·) and k(·) as 1 × 1 convolutions. Eq. (1) computes the response at query position i as a weighted sum of the features of all positions. Conventional self-attention, as described above, can effectively capture long-range dependencies, which well complements convolution layers that capture short-range dependencies within a local region. However, exploiting context information from too distant positions is sometimes problematic since a position is often less correlated with those far away from it. A position tends to have stronger correlations with those are moderately near from it, where middle-range dependencies are contained within this context. Therefore, it is necessary to fill the gap between short-range and longrange dependencies and capture various correlations among entities in the scene. Also, during the process of self-attention operation, the features of the positions which contribute significant attention weights to others usually encode common patterns contained in the scene. These patterns are beneficial to the comprehensive understanding of sophisticated scenes and deserve appropriate emphasis for better capturing long-range dependencies. Based on the two observations, we propose a novel Omni-Range Dependencies Network (ORDNet) which consists of a Middle-Range (MR) branch and a Reweighed Long-Range (RLR) branch to mine middle-range dependencies and refine long-range dependencies respectively for better scene understanding (see Fig. 2). We will elaborate on the MR branch in III-B and the RLR branch in III-C. The overall architecture of ORDNet will be described in detail in III-D.

B. Middle-Range Branch
Conventional self-attention exploits all positions of a feature map to update the feature of each query position. By analyzing correlation patterns among ground-truth mask patches in Fig. 4, we observe that a query position tends to have stronger correlations with the positions near to it compared with those which are distant. To demonstrate this, we randomly select 1, 000 images from PASCAL-Context [10] dataset and divide the ground-truth masks into 2 × 2 and 4 × 4 patches along the height and width dimensions. We further calculate correlations inside and between patches by taking the average of corresponding similarity values: where sim(·, ·) computes the similarity between two positions, which is either 1 or 0. We define the similarity between a pair of positions as whether their semantic labels are the same: Here l i and l j denote the ground-truth category labels of position i and j; p n and p m represent the n-th and m-th patch, and Ω p n and Ω p m denote the set of all the positions belonging to them respectively; | · | means cardinality of their sets. The visualized correlation matrices are shown in Fig. 4 (a) and (b). We can observe that the values of the top left and bottom right elements, as well as their surroundings, are much larger (darker color) than those of the rest regions, which indicates intra-patch correlations are stronger than inter-patch ones. Moreover, pixels within the same or near patches tend to share the same label. Visualization of the attention map in Fig. 1 also demonstrates that conducting self-attention in local patches can capture middle-range dependencies among nearby similar positions instead of original long-range dependencies among all the positions.
Middle-range dependencies captured from local patches are able to provide more relevant context information than longrange dependencies, considering the higher intra-patch correlations than inter-patch ones. We then develop a Middle-Range (MR) branch to capture such more informative middle-range dependencies to complement with long-range dependencies. As illustrated in Fig. 3, our MR branch explicitly divides the input feature maps into 2 × 2 patches and conducts selfattention operation within each patch separately. The output Y m is then recovered to the original spatial dimensions. We narrow the self-attention range from the entire feature map to patch level so that the local nature of the feature can be exploited. Benefited from the complementarity among shortrange, middle-range and long-range dependencies, the network can adapt to diverse spatial relationships between different scene elements. We use 2 × 2 patches for all the experiments. We also have tried to divide features into 4 × 4 patches but found diminishing return, possibly due to limited receptive field. Experimental results are shown in Tab. II. This means the pixels within the same or closer patches tend to have the same label. Furthermore, intra-patch correlation is usually stronger than inter-patch correlation.

C. Reweighed Long-Range Branch
During the self-attention process, the multiplication between query and key features will generate an attention map where each element indicates the attention weight between each pair of positions. We observe that some positions contribute larger attention weights to other positions, which implies that there are stronger correlations between these positions and other ones. Features of these positions usually encode common patterns like main elements appearing in the scene and largearea continuous background. These positions may be crucial to the global context during the self-attention process. By emphasizing features of these essential positions, the longrange dependencies modeled by self-attention is able to be more accurate. Therefore, we propose a Reweighed Long-Range (RLR) branch to selectively enhance features of these positions which contribute large attention weights to others.

Reshape
Self Attention + Fig. 5. Our proposed Reweighed Long-Range (RLR) branch. A self-attention module takes backbone feature as input X and outputs attended feature Y l along with the attention map Attn ∈ R HW ×HW . Then Attn is summed up along each column and fed into a sigmoid function to get the attention contribution vector, which is then reshaped to H × W to obtain the global attention weight contribution map Attng ∈ R H×W . The output feature Z l is attained by multiplying Attng with Y l elementwisely. Note that the difference between Attn and Attng is that each element of Attn denotes the attention weights between a pair of positions in X, whereas each element of Attng denotes the summation of contribution of current position to all the positions.
As illustrated in Fig 5, given an input feature X ∈ R H×W ×C , we first feed it to a self-attention module to output an attended feature Y l ∈ R H×W ×C via Equation (1) and the attention map Attn ∈ R HW ×HW via Equation (2). attn ji ∈ Attn can be viewed as an attention weight contributed by position i to position j. We compute the global attention weight contribution at position i by summing up all the attention weights it contributes to other positions and further employ a simple gated mechanism as below: Here σ(·) is the sigmoid function and is applied to normalize the scale of Attn g . The spatial dimensions of the global attention weight contribution map Attn g = [attn 1 g ; attn 2 g ; ...; attn HW g ] are H × W after reshaping operation. Through Equation (5) we obtain attn i g , i.e., the normalized attention weight contribution of position i to all the positions, which measures the effect of position i on the global context of self-attended features. We finally multiply Y l ∈ R H×W ×C with Attn g ∈ R H×W elementwisely using the broadcasting rule to get Z l ∈ R H×W ×C as the output of this branch: By multiplied with the global attention weight contribution Attn g , the feature at each position is reweighed according to its contribution to other positions. Features of positions which encode common patterns of the scene could be emphasized for better representation. Experimental results in Table I shows that our RLR branch improves the performance without introducing extra parameters.

D. Omni-Range Dependencies Network
We here explain our proposed Omni-Range Dependencies Network (ORDNet) in detail. The architecture of our ORDNet is illustrated in Fig. 2. We use ResNet101 [33] pretrained on ImageNet [34] as the backbone network to extract visual features. To enlarge the receptive field as well as maintain feature resolution, we replace the strided convolutions in the last two stages of ResNet with atrous convolutions, with stride set as 1 and dilation rates set as 2 and 4 respectively. We also follow [18] to replace the first 7×7 convolution of ResNet with 3 consecutive 3 × 3 convolutions. The resolution of the output feature from backbone network X ∈ R H×W ×C is 1/8 of the original image. X is then fed into our proposed two branches to capture middle-range and reweighed long-range dependencies in visual feature. After getting the output features Z m and Z l from these two branches, we concatenate them along the channel dimension. Then a 1 × 1 convolution is applied on the concatenated feature to reduce its channel dimensions to the same number of the input feature. We also add a shortcut connection from input feature X to the fused output of two branches to ease optimization. The fused output feature is then passed into an FCN head for final mask prediction, and we further upsample the prediction result by 8 times to match the original resolution. In practice, our proposed two branches can be easily plugged into a segmentation network due to the residual nature and further enhance feature representations.
The concurrent work InterlacedSSA [19] proposes a factorized self-attention method similar to our MR branch for semantic segmentation. The motivation of InterlacedSSA is to decrease the computation/memory cost of self-attention mechanism by factorizing it into two consecutive self-attention processes occurred in patches. However, the motivation of our MR branch is to demonstrate the effectiveness of capturing middle-range dependencies by restricting self-attention in feature patches. Moreover, the factorized self-attention in InterlacedSSA still aims to capture long-range dependencies among positions by stepwise information propagation. However, the factorized self-attention in our MR branch aims to explicitly capture middle-range dependencies among positions to fill the semantic gap between long-range and short-range dependencies for more comprehensive scene understanding. It serves as an additional information source to complement with reweighed self-attention and normal convolutions. In summary, our ORDNet can make self-attention more comprehensive in aggregating information, while InterlacedSSA can reduce the computational budget of self-attention. InterlacedSSA makes a step forward over our middle-range branch and the contributions of us and InterlacedSSA are complementary.

E. Loss Functions
Our full loss function L F ull contains two parts namely standard cross-entropy loss L CE and Lovasz-hinge loss [35] L IoU , which are formulated as follows: L IoU (y * ,ỹ) = −Jaccard(y * ,ỹ) where y * denotes ground-truth mask,ỹ denotes predicted logits, α 1 and α 2 are weights for different loss terms, K denotes the number of semantic categories.

IV. EXPERIMENTS A. Experimental Setup
Training: We conduct all the experiments using Py-Torch [36] on three scene parsing benchmarks, including PASCAL-Context [10], COCO Stuff [11] and ADE20K [2]. We also evaluate our model on PASCAL VOC 2012 dataset [37] for semantic segmentation task. We choose dilated FCN [38] as the baseline model and plug our MR and RLR branches between the ResNet backbone and FCN head. The output prediction is bilinearly upsampled by 8 times to match the input size. We initialize the backbone with an ImageNet [39] pretrained model and other layers including MR branch, RLR branch and the FCN head are randomly initialized. We adopt the SGD optimizer with momentum set to 0.9 and weight decay set to 0.0001 to train the network. We use the polynomial learning rate scheduling lr = baselr * (1 − iter total iter ) power . The base learning rate is set to 0.004 for ADE20K dataset and 0.001 for other datasets. The channel dimension C of the input feature X for our MR branch and RLR branch is 2048. Self-attention contains three linear layers to transform the input feature, namely query (q), key (k) and value (v). To reduce the memory cost, we set the output channel dimensions of query and key layers C q = C k = 256 and set C v = 512 for all the selfattention modules we used. Our MR branch adopts 2 × 2 patches to capture middle-range dependencies. We conduct all the experiments on 4 NVIDIA TITAN RTX GPU cards. For data augmentation, We apply random flipping, random cropping and random resize between 0.5 and 2 for all datasets. When comparing with other methods, we adopt both standard cross-entropy loss and Lovasz-hinge loss [35] as our full loss function to train the network. Loss weights α 1 and α 2 are both set as 1.0. For the whole scene parsing dataset ADE20K, we follow [18] and the standard competition benchmark [2] to calculate mIoU by ignoring background pixels. When training our ORDNet on PASCAL-Context dataset, we also ignore the pixels of background category following [18] [8].
Evaluation: As prior works [18][8] [9] show that employing multi-scale testing during evaluation is able to bring significant performance gain in semantic segmentation and scene parsing, we follow the best practice in [18] to average the predictions of different scales as the final results. During evaluation, the input image is first resized according to a set of different scales {0.5, 0.75, 1.0, 1.25, 1.5, 1.75}, then cropped to a pre-defined image size for training. The cropped image is randomly flipped and fed into the segmentation network. The output logits are cropped and averaged across above scales as final prediction. For the consideration of fairness, we adopt multi-scale testing when comparing with state-of-the-art methods. Mean Intersection of Union (mIoU) and pixel accuracy (pixAcc) are adopted as evaluation metrics.

B. Ablation Studies
We conduct both quantitative and qualitative ablation experiments on the test set of PASCAL-Context dataset [10] to verify the effectiveness of our MR and RLR branches and their variants. We train our model for 50 epochs with batch size of 16. Following [9], we use the most common 59 categories of PASCAL-Context without the background category for ablation studies. MR and RLR branches: Experimental results of our proposed two branches are illustrated in Table I. The dilated FCN baseline yields mIoU of 45.30%. After combining with basic self-attention (Basic SA) [7], the mIoU can increase significantly by 4.15%, which forms a strong baseline for our method. Upon the basic self-attention mechanism (Basic SA), adding our Middle-Range branch (Basic SA + MR) is able to achieve 0.81% improvement in mIoU, which demonstrates that more comprehensive scene context information can be extracted by integrating middle-range dependencies into the segmentation network to complement with long-range dependencies captured by original self-attention. Adding our Reweighed Long-Range branch (Basic SA + RLR) can also bring 0.81% mIoU gain over the Basic SA baseline, indicating that emphasizing features of positions which encode the common patterns of scenes is able to capture more accurate longrange dependencies to achieve better understanding of scenes. Furthermore, the RLR branch introduces no extra parameters over the strong Basic SA baseline while outperforming it by a large margin. When incorporating our proposed two branches together, our Omni-Range Dependencies Network (ORDNet) is capable of obtaining a further improvement with 1.22% mIoU gain and 0.74% pixAcc gain due to the effective complementarity between short-range (captured by convolutions), middle-range and reweighed long-range dependencies. After utilizing a deeper backbone network, our ORDNet can further achieve the performance boost to 3.58% and 1.63% gains in mIoU and pixAcc, respectively.
Qualitative results: Qualitative comparison with baseline Basic SA [7] are shown in Fig 6. Our ORDNet obtains better parsing results in both global and local parts. For example, in the 4-th row of (d) and (e), Basic SA produces muddled result with nonexistent categories, while our ORDNet is able to understand the entire scene correctly and generate coherent parsing map in the assistance of omni-range dependencies. Also in the 1-st and 6-th rows of (d) and (e), our ORDNet can fix local prediction errors in Basic SA, e.g., missing tiny sheeps and confusing ear, which indicates the superiority of integrating middle-range and reweighed long-range dependencies into the segmentation network. There are also some failure cases in Fig 6. For instance, our model fails to identify the "background" category (two pillars, snowboard) in the 3-rd and 4-th row. The reason is that we ignore the pixels of "background" category when training our ORDNet on PASCAL-Context dataset following [18] [8]. Therefore, our ORDNet cannot identify the "background" category and predicts other labels for these pixels, which has no harm to the performance. We also observe other poor results like inaccurate boundaries in the last row of Fig 6. We suppose the reason is that our ORDNet cannot aggregate enough boundary details from low resolution feature maps. Exploiting low level features from the CNN backbone may alleviate this problem.
Number of patches in MR branch: We also conduct analysis on 2 × 2 patches and 4 × 4 patches in our MR branch only. Experimental results are shown in Table II. Given the same input size, conducting self-attention over 2 × 2 patches reduce FLOPs from 94.50G to 62.27G and reduce mIoU from 49.45% to 48.75%. Conducting self-attention over 4 × 4 patches could reduce FLOPs from 94.50G to 51.17G given the same input size. However, it does not work as well as original self-attention (MR nopatch) or 2 × 2 patches MR branch. Enlarging crop size to 640 has limited improvement but results in larger FLOPs which is larger than 2 × 2 patches (Second row). We suppose that dividing feature map into too many patches for self-attention will bring about fragmented receptive field, leading to inferior performance. Note that we only compare variants of MR branch without integrating with Basic SA, thus the mIoU and PixAcc of 2 × 2 patches MR branch in Table II are lower than those in Table I.   Variants of RLR branch: We evaluate different versions of RLR branch. Experiment results are shown in Table III. All the models are based on ResNet50. Attention-in means that Attn g is obtained by summing up Attn along each row so that each element of Attn g denotes the contribution of all positions to the current position. Attention-out means that Attn g is obtained by summing up Attn along each column so that each element of Attn g denotes the contribution of current position to all others. We also try different normalization methods for Attn g , including Softmax and Sigmoid functions. Results in  Table III show that calculating Attn g as attention-out attains better performance than attention-in and combining attentionout with sigmoid normalization achieves the best performance on PASCAL-Context dataset.
Fusing methods for MR and RLR branches: We compare different approaches to fuse the outputs of our proposed MR and RLR branches on the test set of PASCAL-Context. Experiment results are presented in Table IV concatenation followed by a 1×1 convolution, we also explore Attention to Scale [40] and Channel Selection [41] for feature fusion. Attention to scale obtains a selection weight map for each branch and each position of the fused feature will receive a weighted summation of the features at the same positions from the two branches. Instead of spatial dimension, Channel Selection obtains the selection weight vector for each branch and conduct weighted summation along channel dimension. Experiment results indicate that simply concatenating the two features and fusing them with a 1×1 convolution achieves the best performance. A possible reason is that for features from our two branches, normal convolution fusing them along both spatial and channel dimensions, while Attention to Scale and Channel Selection perform fusion only along spatial dimension or channel dimension, respectively.
Visualization of RLR branch: To further illustrate the proposed RLR branch, we visualize the attention maps and parsing results of our model with RLR branch only in Fig 7. Column (b) visualizes of global attention weight contribution map Attn g , i.e., summation of attention weights contributed by each position to all the positions. We can observe that areas with larger attention weight contribution (brighter color) usually represent common patterns of the scene, e.g., sky, grass and wall which serve as large-area continuous background. As shown in column (d) and (e), by emphasizing common pattern regions, our RLR branch is able to correct erroneous predictions made by basic self-attention and make the network understand the scene contents more comprehensively.

C. Results on PASCAL-Context
PASCAL-Context dataset [10] contains 4, 998 images for training and 5, 105 images for testing. All images are densely annotated with 60 categories in total including background. We train our model for 80 epochs with batch size of 16 when comparing with state-of-the-art methods. The image crop size is set to 480. We use the total 60 categories including the most frequent 59 categories and the background category to evaluate our method as prior works [52][18] [9] do. Compared methods and results are shown in Table V. Our ORDNet achieves 54.5% mIoU which outperforms previous state-of-the-art methods. SGR+ [55] and DeepLab-v2 [6] utilize additional COCO Stuff [11] and COCO [59] data to pretrain their models. RefineNet-152 [52] and MSCI [54] adopt deeper backbone network to boost performance. Recent CFNet [9] integrates the Context Encoding module from EncNet [18] and obtains 54.0% mIoU. InterlacedSSA [19]  further boosts the performance to 54.1% mIoU via factorized self-attention similar to our MR branch. Our ORDNet achieves better performance than above methods without using extra pretraining data, deeper backbone network or other context aggregation modules. It is demonstrated that capturing omnirange dependencies is more effective in providing richer semantic information for scene parsing.

D. Results on COCO Stuff
COCO Stuff dataset [11] contains 10, 000 images from MSCOCO dataset [59] with dense annotations of 80 thing (e.g. book, clock) and 91 stuff categories (e.g. flower). We  [58] generates a scale-and shape-variant semantic mask for each pixel to confine its contextual region for more adaptive context aggregation. DANet [8] employs spatial and channelwise self-attention to further improve performance. Recent InterlacedSSA [19] proposes a factorized approach similar to our MR branch to accelerate self-attention. Our method outperforms these methods with a large margin and achieves a new state-of-the-art result of 40.5% mIoU with no external knowledge used. This result indicates that capturing omnirange dependencies is more effective than merely modeling long-range dependencies in conventional self-attention.

E. Results on ADE20K
ADE20K [2] is a large scene parsing benchmark with 150 categories including stuff and objects. It contains 20, 210 images for training and 2, 000 for validation. We train our model for 120 epochs on the training set with batch size of 16 and report mIoU and pixAcc results on the validation set. As the average image size of ADE20K dataset is larger than others, we adopt image crop size of 576 on ADE20K. Comparison with previous state-of-the-art methods is shown in Table VII. PSPNet-269 [1] uses a much deeper backbone network than other methods. EncNet [18] and CFNet [9] exploit prior information of semantic categories appearing in the scene to improve performance. InterlacedSSA [19] introduces factorized self-attention similar to our MR branch and obtain 45.04% mIoU. Our method achieves 45.39% mIoU which outperforms previous methods without using deeper backbone, category prior or external knowledge like [55]. As mentioned in the Section 4.1 of InterlacedSSA, the 0.2% improvement of their method is not neglectable considering the improvements on ADE20K is very challenging. Therefore, results of our method demonstrate capturing omni-range dependencies is also effective in challenging and complicated scenes.
To further demonstrate the effectiveness of our ORDNet, we evaluate our model on the test set. The experiment results are shown in Table VIII. Our model without finetuning on validation set achieves 56.67 final score and surpasses most other methods. The final score denotes the average of PixAcc and mIoU. For fair comparison, we further finetune our model on the train+val set of ADE20K for 20 epochs, with the same training scheme except that the initial learning rate is set to 1e − 4. Our ORDNet achieves a final score of 56.86 on the test set with a single model and ranks at the 2-nd place on the leaderboard of MIT Scene Parsing Benchmark. Our single model surpasses the 3-rd place, Adelaide, which ensembles multiple models. The 1-st place, SenseCUSceneParsing achieves 57.21 final score by ensembling multiple models as well. Its single model trained only on the training set achieves 55.38 while our ORDNet achieves 56.67 with the same setting.

F. Results on PASCAL VOC 2012
We also evaluate the proposed ORDNet on PASCAL VOC 2012 dataset [37] with 21 categories for semantic segmentation task. We adopt the augmented dataset [62] which contains 10, 582 images for training, 1, 449 images for validation and 1, 456 images for testing. We first train on the augmented train + val set for 60 epochs with initial learning rate of 1e−3. Then we finetune the model on the original PASCAL VOC training set for another 20 epochs with learning rate of 1e−4. We adopt ResNet101 as backbone network and the image crop size is set to 480. Our ORDNet achieves 83.3% mIoU on PASCAL VOC 2012 test set without using COCO pretraining or additional context aggregation modules. It is demonstrated that our method can also adapt to foreground object segmentation task by capturing omni-range dependencies.

G. Analysis of Computational Overhead
As shown in TABLE IX, all the models are run on a single NVIDIA TITAN XP GPU card to report computational overhead. InterlacedSSA is superior to other methods including ours in terms of speed and memory cost. It is a natural result since the main idea of InterlacedSSA is to decrease the computational budget of self-attention via feature factorization. While the main idea of our ORDNet is to demonstrate the effectiveness of capturing omni-range dependencies by our MR and RLR branches, which outperforms InterlacedSSA on all the datasets we adopted in this paper. Reducing computational complexity is not one of our claims. Comparing with Basic SA and DANet, our ORDNet actually has a moderate computational overhead since we reduce the channel dimensions of query, key and value layers in our MR and RLR branches to 256, 256 and 512 respectively, but our ORDNet achieves higher performances. We will explore how to reduce its time and memory costs in the future work. V. CONCLUSION AND FUTURE WORK In this paper, we address the scene parsing problem which requires the model to segment the entire scene instead of foreground objects. We propose a novel Omni-Range Dependencies Network (ORDNet) which restricts the scope of selfattention to local patches to capture middle-range dependencies and meanwhile selectively emphasizes spatial regions contributing significant attention weights to others to model more accurate long-range dependencies. By integrating middlerange, reweighed long-range and short-range dependencies captured by local convolutions together, our ORDNet can aid models in adapting to various spatial scales and relationships in the complicated natural images, thus strengthening local and global feature representations. Extensive experiments on four scene parsing and segmentation benchmarks demonstrate its superior performance. Furthermore, our ORDNet can be applied to other visual tasks for capturing omni-range dependencies due to its generality and plug-and-play property. In the future, we hope to apply the ORDNet to other visual tasks and study how to further reduce its computing budget.