Title: CONVOLUTIONAL CRFS FOR SEMANTIC SEGMENTA-TION

Abstract: For the challenging semantic image segmentation task the best performing models have traditionally combined the structured modelling capabilities of Conditional Random Fields (CRFs) with the feature extraction power of CNNs. In more recent works however, CRF post-processing has fallen out of favour. We argue that this is mainly due to the slow training and inference speeds of CRFs, as well as the difficulty of learning the internal CRF parameters. To overcome both issues we propose to add the assumption of conditional independence to the framework of fully-connected CRFs. This allows us to reformulate the inference in terms of convolutions, which can be implemented highly efficiently on GPUs .Doing so speeds up inference and training by two orders of magnitude. All parameters of the convolutional CRFs can easily be optimized using backpropagation. Towards the goal of facilitating further CRF research we have made our implementations publicly available.

1. INTRODUCTION:

Semantic image segmentation, which aims to produce a categorical label for each pixel in an image, is a very import task for visual perception. Convolutional Neural Networks have been proven to be very strong in tackling semantic segmentation tasks (Long et al., 2015; Chen et al., 2018; 2017; Zhao et al., 2017) . While simple feed-forward CNNs are extremely powerful in extracting local features and performing good predictions utilizing a small field of view, they lack the capability to utilize context information and cannot model interactions between predictions directly. Thus it has been suggested that such deep neural networks may not be the perfect model for structured predictions tasks such as semantic segmentation (Zhao et al., 2017; Lin et al., 2016; Zheng et al., 2015) . Several authors have successfully combined the effectiveness of CNNs to extract powerful features, with the modelling power of CRFs in order to address the discussed issues (Lin et al., 2016; Chandra & Kokkinos, 2016; Zheng et al., 2015) . Despite their indisputable success, structured models have fallen out of favour in more recent approaches (Wu et al., 2016; Chen et al., 2017; Zhao et al., 2017) .

We believe that the main reasons for this development are that CRFs are notoriously slow and hard to optimize. Learning the features for the structured component of the CRF is an open research problem (Vemulapalli et al., 2016; Lin et al., 2016) and many approaches rely on entirely hand-crafted Gaussian features (Krähenbühl & Koltun, 2011; Zheng et al., 2015; Schwing & Urtasun, 2015; Chen et al., 2018) . In addition, CRF inference is typically two orders of magnitude slower than CNN inference. This makes CRF based approaches too slow for many practical applications. The long training times of the current generation of CRFs also make more in-depth research and experiments with such structured models impractical.

To solve both of these issues we propose to add the strong and valid assumption of conditional independence to the existing framework of fully-connected CRFs (FullCRFs) introduced by Krähenbühl & Koltun (2011) . This allows us to reformulate a large proportion of the inference as convolutions, which can be implemented highly efficiently on GPUs. We call our method convolutional CRFs (ConvCRFs). Backpropagation (Rumelhart et al., 1986 ) can be used to train all parameters of the ConvCRF. Inference in ConvCRFs can be performed in less then 10ms. This is a speed increase of two-orders of magnitude compared to FullCRFs. We believe that those fast train and inference speeds will greatly benefit future research and hope that our results help to revive CRFs as a popular method to solve structured tasks.

2. RELATED WORK:

Recent advances in semantic segmentation are mainly driven by powerful deep neural network architectures (Krizhevsky et al., 2012; Simonyan & Zisserman, 2015; He et al., 2016; Wu et al., 2016) . Following the ideas introduced by Long et al. (2015) , transposed convolution layers are applied at the end of the prediction pipeline to produce high-resolution output. Atrous (dilated) convolutions (Chen et al., 2015a; Yu & Koltun, 2015) are commonly applied to preserve spatial information in feature space.

Many architectures have been proposed (Noh et al., 2015; Ronneberger et al., 2015; Badrinarayanan et al., 2017; Paszke et al., 2016; Teichmann et al., 2016; Wu et al., 2016) , based on the ideas above. All of those approaches have in common that they primarily rely on the powerful feature extraction provided by CNNs. Predictions are pixel-wise and conditionally independent (given the common feature base of nearby pixels). Structured knowledge and background context is ignored in these models.

One popular way to integrate structured predictions into CNN pipelines is to apply a fully-connected CRF (FullCRF) (Krähenbühl & Koltun, 2011) on top of the CNN prediction (Chen et al., 2015a; Zheng et al., 2015; Schwing & Urtasun, 2015; Lin et al., 2016; Chandra & Kokkinos, 2016) . Utilizing the edge-awareness of CRFs, FullCRFs have been successfully utilized to solve weakly-and semisupervised segmentation tasks (Li et al., 2018; Triggs & Verbeek, 2008; He & Zemel, 2009; Tang et al., 2018) . Tang et al. (2018) propose to use a CRF based loss function. All of those approaches can benefit from our contributions.

Parameter Learning in CRFs FullCRFs rely on hand-crafted features for the pairwise (Gaussian) kernels. In their first publication Krähenbühl & Koltun (2011) optimized the remaining parameters with a combination of expectation maximization and grid-search. In a follow-up work Krähenbühl & Koltun (2013) proposed to use gradient descent. The idea utilizes, that for the message passing the equation

(k G * Q) = k G * Q holds.

This allows them to train all internal CRF parameters, using backpropagation, without being required to compute gradients with respect to the Gaussian kernel k G . However the features of the Gaussian kernel cannot be learned with such an approach. CRFasRNN (Zheng et al., 2015) uses the same ideas to implement joint CRF and CNN training. Like Krähenbühl and Koltuns (2013) approach this requires hand-crafted pairwise (Gaussian) features.

Quadratic optimization (Chandra & Kokkinos, 2016; Vemulapalli et al., 2016) has been proposed to learn the Gaussian features of FullCRFs. These approaches however do not fit well into many deep learning pipelines. Another way of learning the pairwise features is piecewise training (Lin et al., 2016) . An additional advantage of this method is that it avoids repeated CRF inference, speeding up the training considerably. This approach is however of an approximate nature and inference speed is still very slow.

Inference speed of CRFs In order to circumvent the issue of very long training and inference times, some CRF based pipelines produce an output which is down-sampled by a factor of 8 × 8 (Chandra & Kokkinos, 2016; Lin et al., 2016) . This speeds up the inference considerably. However this harms their predictive capabilities. Deep learning based semantic segmentation pipelines perform best when they are challenged to produce a full-resolution prediction (Long et al., 2015; Yu & Koltun, 2015; Chen et al., 2017) . To the best of our knowledge, no significant progress in inference speed has been made since the introduction of FullCRFs (Krähenbühl & Koltun, 2011) .

3. FULLY CONNECTED CRFS:

In the context of semantic segmentation most recent CRF based approaches are based on the Fully Connected CRF (FullCRF) model introduced by Krähenbühl & Koltun (2011) . Consider an input image I consisting of n pixels and a segmentation task with k classes. A segmentation of I is then modelled as a random field X = {X 1 , . . . , X n }, where each random variable X i takes values in {1, . . . , k}, i.e. the label of pixel i. Solving argmax X P (X|I) then leads to a segmentation X of the input image I. P (X|I) is modelled as a CRF over the Gibbs distribution:

P (X = x| Ĩ = I) = 1 Z(I) exp(-E(x|I)) (1)

where the energy function E(x|I) is given by

EQUATION

The function ψ u (x i |I) is called unary potential. The unary itself can be considered a segmentation of the image and any segmentation pipeline can be used to predict the unary. In practise most newer approaches (Chen et al., 2018; Schwing & Urtasun, 2015; Zheng et al., 2015) utilize CNNs to compute the unary.

The function ψ p (x i , x j |I) is the pairwise potential. It accounts for the joint distribution of pixels i, j.

It allows us to explicitly model interactions between pixels, such as pixels with similar colour are likely the same class. In FullCRFs ψ p is defined as weighted sum of Gaussian kernels k

(1)

EQUATION

where w (m) are learnable parameters. The feature vectors f I i can be chosen arbitrarily and may depend on the input Image I. The function µ(x i , x j ) is the compatibility transformation, which only depends on the labels x i and x j , but not on the image I.

A very widely used compatibility function (Krähenbühl & Koltun, 2011; Chen et al., 2018; Zheng et al., 2015) is the Potts model

µ(x i , x j ) = 1 [xi =xj]

. This model tries to assign pixels with similar features the same prediction. Zheng et al. (2015) propose to use 1 × 1 convolutions as compatibility transformation. Such a function allows the model to learn more structured interactions between predictions.

FullCRFs utilize two Gaussian kernels with hand-crafted features. The appearance kernel uses the raw colour values I j and I i as features. The smoothness kernel is based on the spatial coordinates p i and p j . The entire pairwise potential is then given as:

EQUATION

where w (1) , w (2) , as well as θ α , θ β and θ γ are the only learnable parameters of the model. Most CRF based segmentation approaches (Chen et al., 2018; Zheng et al., 2015; Schwing & Urtasun, 2015) utilize the very same handcrafted pairwise potentials proposed by Krähenbühl & Koltun (2011) .

CRFs are notoriously hard to optimize and utilizing hand-crafted features circumvents this problem.

3.1. MEAN FIELD INFERENCE:

Inference in FullCRFs is achieved using the mean field algorithm (see Algorithm 1). All steps of algorithm 1, other then the message passing, are highly parallelized and can be implemented easily and efficiently on GPUs using standard deep learning libraries. (For details see (Zheng et al., 2015) ).

The message passing however is the bottleneck of the CRF computation. Exact computation is quadratic in the number of pixels and therefore infeasible. Krähenbühl & Koltun (2011) instead proposed to utilize the permutohedral lattice (Adams et al., 2010) approximation, a high-dimensional filtering algorithm. The permutohedral lattice however is based on a complex data structure. While there is a very sophisticated and fast CPU implementation, the permutohedral lattice does not follow the SIMD (Nickolls et al., 2008) paradigm of efficient GPU computation. In addition, efficient gradient computation of the permutohedral lattice approximation, is also a non-trivial problem. This is the underlying reason why FullCRF based approaches use hand-crafted features.

Algorithm 1 Mean field approximation in fully connected CRFs

1: Initialize: Qi ← 1 Zi exp(-ψ u (x i |I)) "softmax" 2: while not converged do 3: Qi (l) ← i =j w (m) k (m) g (f I i , f I j ) Qi (l) Message Passing 4: Qi (x i ) ← l ∈L µ(x i , l ) Qi (l) Compatibility Transformation 5: Qi (x i ) ← ψ u (x i |I) + Qi (x i ) Adding Unary Potentials 6: Qi (x i ) ← normalize( Qi (x i ))

e.g. softmax 7: end while

4. CONVOLUTIONAL CRFS:

The convolutional CRFs (ConvCRFs) supplement FullCRFs with a conditional independence assumption. We assume that the label distribution of two pixels i, j are conditionally independent, if for the Manhattan distance d holds d(i, j) > k. We call the hyperparameter k filter-size. This locality assumption is a very strong assumption. It implies that the pairwise potential is zero, for all pixels whose distance exceed k. This reduces the complexity of the pairwise potential greatly. The assumption can also be considered valid, given that CNNs are based on local feature processing and are highly successful. This makes the theoretical foundation of ConvCRFs very promising, strong and valid assumptions are the powerhouse of machine learning modelling.

4.1. EFFICIENT MESSAGE PASSING IN CONVCRFS:

One of the key contribution of this paper is to show that exact message passing is efficient in ConvCRFs. This eliminates the need to use the permutohedral lattice approximation, making highly efficient GPU computation and complete feature learning possible. Towards this goal we reformulate the message passing step to be a convolution with truncated Gaussian kernel and observe that this can be implemented very similar to regular convolutions in CNNs.

Consider an input P with shape [bs, c, h, w] where bs, c, h, w denote batch size, number of classes, input height and width respectively. For a Gaussian kernel g defined by feature vectors f 1 . . . f d , each of shape [bs, h, w] we define its kernel matrix by

EQUATION

where θ i is a learnable parameter. For a set of Gaussian kernels g 1 . . . g s we define the merged kernel matrix K as K := s i=1 w i • g i . The result Q of the combined message passing of all s kernels is now given as:

EQUATION

This message passing operation is similar to standard 2d-convolutions of CNNs. In our case however, the filter values depend on the spatial dimensions x and y. This is similar to locally connected layers (Chen et al., 2015b) . Unlike locally connected layers (and unlike 2d-convolutions), our filters are however constant in the channel dimension c. One can view our operation as convolution over the dimension c1 .

It is possible to implement our convolution operation by using standard CNN operations only. This however requires the data to be reorganized in GPU memory several times, which is a very slow process. Profiling shows that 90 % of GPU time is spend for the reorganization of data. We therefore opted to build a native low-level implementation, to gain an additional 10-fold speed up.

Efficient computation of our convolution can be implemented analogously to 2d-convolution (and locally connected layers). The first step is to tile the input P in order to obtain data with shape [bs, c, k, k, h, w] . This process is usually referred to as im2col and the same as in 2dconvolutions (Chetlur et al., 2014) . 2d-convolutions proceed by applying a batched matrix multiplication over the spatial dimension. We replace this step with a batched dot-product over the channel dimension. All other steps are the same.

4.2. ADDITIONAL IMPLEMENTATION DETAILS:

For the sake of comparability we use the same design choices as FullCRFs in our baseline ConvCRF implementation. In particular, we use softmax normalization, the Potts model as well as the same handcrafted gaussian features as proposed by Krähenbühl & Koltun (2011) . Analogous to Krähenbühl & Koltun (2011) we also apply gaussian blur to the pairwise kernels. This leads to an increase of the effective filter size by a factor of 4.

In additional experiments we investigate the capability of our CRFs to learn Gaussian features.

Towards this goal we replace the input features p i of the smoothness kernel with learnable variables. Those variables are initialized to the same values as the hand-crafted version, but are adjusted as part of the training process. We also implement a learnable compatibility transformation using 1 × 1 convolution, following the ideas of Zheng et al. (2015) .

5. EXPERIMENTAL EVALUATION:

Dataset: We evaluate our method on the challenging PASCAL VOC 2012 (Everingham et al.) image dataset. Following the literature (Long et al., 2015; Wu et al., 2016; Chen et al., 2018; Zhao et al., 2017) we use the additional annotation provided by (Hariharan et al., 2011) resulting in 10 582 labelled images for training. Out of those images we hold back 200 images to fine-tune the internal CRF parameters and use the remaining 10 382 to train the unary CNN. We report our results on the 1464 images of the official validation set.

Unary: We train a ResNet101 (He et al., 2016) to compute the unary potentials. We use the ResNet101 implementation provided by the PyTorch (Paszke et al., 2017) repository. A simple FCN (Long et al., 2015) is added on top of the ResNet to decode the CNN features and obtain valid segmentation predictions. The network is initialized using ImageNet Classification weights (Deng et al., 2009) and then trained on Pascal VOC data directly. Unlike many other projects, we do not train the network on large segmentation datasets such as MS COCO (Lin et al., 2014) , but only use the images provided by the PASCAL VOC 2012 benchmark.

The CNN is trained for 200 epochs using a batch size of 16 and the adam optimizer (Kingma & Ba, 2014) . The initial learning rate is set to 5 × 10 -5 and polynomially decreased (Liu et al., 2015; Chen et al., 2018) by multiplying the initial learning rate with ((1 -step max_steps ) 0.9 ) 2 . An L 2 weight decay with factor 5 × 10 -4 is applied to all kernel weights and 2d-Dropout (Tompson et al., 2015) with rate 0.5 is used on top of the final convolutional layer. The same hyperparamters are also used for the end-to-end training.

The following data augmentation methods are applied: Random horizontal flip, random rotation (±10°) and random resize with a factor in (0.5, 2). In addition the image colours are jittered using random brightness, random contrast, random saturation and random hue. All random numbers are generated using a truncated normal distribution. The trained model achieves validation mIoU of 71.23 % and a train mIoU of 91.84 %.

CRF: Following the literature (Krähenbühl & Koltun, 2011; Chen et al., 2018; Zheng et al., 2015; Lin et al., 2016) , the mean-field inference of the CRF is computed for 5 iterations in all experiments.

5.1. CONVCRFS ON SYNTHETIC DATA:

To show the capabilities of Convolutional CRFs we first evaluate their performance on a synthetic task. We use the PASCAL VOC (Everingham et al.) dataset as a basis, but augment the ground-truth towards the goal to simulate prediction errors. The noised labels are used as unary potentials for the CRF, the CRF is then challenged to denoise the predictions. The output of the CRF is then compared to the original label of the Pascal VOC dataset.

Towards the goal of creating a relevant task, the following augmentation procedure is used: First the ground-truth is down-sampled by a factor of 8. Then, in low-resolution space random noise is added to the predictions and the result is up-sampled to the original resolution again. This process simulates inaccuracies as a result of the low-resolution feature processing of CNNs as well as prediction errors similar to the checkerboard issue found in deconvolution based segmentation networks (Gao et al., 2017; Odena et al., 2016) . Some examples of the augmented ground-truth are shown in Figure 1 .

In our first experiment we compare FullCRFs and ConvCRFs using the exact same parameters. To do this we utilize the hand-crafted Gaussian features. The remaining five parameters (namely w (1) , w (2) , as well as θ α , θ β and θ γ ) are initialized to the default values proposed by Krähenbühl & Koltun (2011) . Note that this gives FullCRFs a natural advantage. The performance of CRFs however is very robust with respect to these five parameters (Krähenbühl & Koltun, 2011) .

The results of our first experiment are given in performance of ConvCRFs with the same parameters can be explained by our exact message passing, which avoids the approximation errors compared of the permutohedral lattice approximation. We provide a visual comparison in Figure 1 where ConvCRF clearly provide higher quality output. The FullCRF output shows approximation artefacts at the boundary of objects. In addition we note that ConvCRFs are faster by two orders of magnitude, making them favourable in almost every use case.

5.2. DECOUPLED TRAINING OF CONVCRFS:

In this section we discuss our experiments on Pascal VOC data using a two stage training strategy.

First the unary CNN model is trained to perform semantic segmentation on the Pascal VOC data.

Those parameters are then fixed and in the second stage the internal CRF parameters are optimized with respect to the CNN predictions. The same unary predictions are used across all experiments, to reduce variants between runs.

Decoupled training has various merits compared to an end-to-end pipeline. Firstly it is very flexible. A standalone CRF training can be applied on top of any segmentation approach. The unary predictions are treated as a black-box input for the CRF training. In practice this means that the two training stages do not need to interface at all, making fast prototyping very easy. Additionally decoupled training keeps the system interpretable. Lastly, piecewise training effectively tackles the vanishing gradient problem (Bengio et al., 1994) , which is still an issue in CNN based segmentation approaches (Wu et al., 2016) . This leads to overall faster, more robust and reliable training.

For our experiments we train the CRF models on the 200 held-out images from the training set and evaluate the CRF performance on the 1464 images of the official Pascal VOC dataset. We compare the performance of the ConvCRF with filter size 11 to the unary baseline results as well as a FullCRF trained following the methodology of DeepLab (Chen et al., 2018) .

We report our results in implementation utilizing a learnable compatibility transformation as well as learnable Gaussian features performs best. Model output is visualized in Figure 3 .

5.3. END-TO-END LEARNING WITH CONVCRFS:

In this section we discuss our experiments using an end-to-end learning strategy for ConvCRFs. In end-to-end training the gradients are propagated through the entire pipeline. This allows the CNN and CRF model to co-adapt and therefore to produce the optimum output w.r.t the entire network. The down-side of end-to-end training is that the gradients need to be propagated through five iterations of the mean-field inference, resulting in vanishing gradients (Zheng et al., 2015) .

We train our network for 250 epochs using a training protocol similar to CRFasRNN (Zheng et al., 2015) . Zheng et al. propose to first train the unary potential until convergence and then optimizing the CRF and CNN jointly. Like Zheng et al. (2015) we greatly reduce the learning rate to 10 -10 during the second training stage. We use a batch size of 16 for the first and 8 for the second training stage. In this regard we differ from Zheng et al. (2015) , who proposes to reduce the batch size to 1 for the second training stage.

The entire training process takes about 30 hours using four 1080Ti GPUs in parallel. We believe that the fast training and inference speeds will greatly benefit and ease future research using CRFs. We compare our ConvCRF to the approach proposed in CRFasRNN (Zheng et al., 2015) and report the results in Table 3 . Overall we see that ConvCRF slightly outperforms CRFasRNN at a much higher speed.

6. CONCLUSION:

In this work we proposed Convolutional CRFs, a novel CRF design. Adding the strong and valid assumption of conditional independence enables us to remove the permutohedral lattice approximation. This allows us to implement the message passing highly efficiently on GPUs as convolution operations. This increases training and inference speed by two orders of magnitude. In addition we observe a modest accuracy improvement when computing the message passing exactly. Our method also enables us to easily train the Gaussian features of the CRF using backpropagation.

In future work we will investigate the potential of learning Gaussian features further. We are also going to examine more sophisticated CRF architectures, towards the goal of capturing context information even better. Lastly we are particularly interested in exploring the potential of ConvCRFs in other structured applications such as instance segmentation, landmark recognition and weakly supervised learning. 

:

Note that the operation refereed to as convolution in the context of NNs is actually known as crosscorrelation in the signal processing community. The operation we want to implement however is a "proper" 1d-convolution. This operation is related to but not the same as 1d-convolution in NNs.

Figures and Tables:

Figure 1: Visualization of the synthetic task. Especially in the last example, the artefacts from the permutohedral lattice approximation can clearly be seen at object boundaries.

Figure 3: Visualization of results on Pascal VOC data using a decoupled training strategy. Examples 2 and 4 depict failure cases, in which the CRFs are not able to improve the unary.

Performance comparison of CRFs on the synthetic benchmark. The speed tests have been done on a Nvidia GeFore GTX 1080 Ti GPU and an Intel Xeon E5-2630 CPU. The images are processed in full resolution. ConvCRF utilize GPU computation while FullCRF inference is computed on CPU. Conv7 denotes a ConvCRF with filter size 7.

Table content: <table><tr><td>Method</td><td colspan="7">Unary FullCRF Conv5 Conv7 Conv11 Conv13 Conv15</td></tr><tr><td>Speed [ms]</td><td>68</td><td>647</td><td>7</td><td>13</td><td>26</td><td>34</td><td>45</td></tr><tr><td colspan="2">Accuracy [%] 86.60</td><td>94.79</td><td>97.13</td><td>97.13</td><td>98.97</td><td>98.99</td><td>98.95</td></tr><tr><td>mIoU [%]</td><td>51.87</td><td>84.37</td><td>90.90</td><td>92.98</td><td>93.74</td><td>93.89</td><td>93.71</td></tr></table>

It can be seen that ConvCRFs outperform FullCRFs significantly. This shows that ConvCRFs are structurally superior to FullCRFs. The better Training and validation mIoU over time for decoupled training. +C uses convolutions as compatibility transformation and +T learns the features for the smoothness kernel.

Table content: <table><tr><td>Score [%]</td><td>71.2 71.4 71.6 71.8 72.0 72.2 72.4</td><td>0</td><td colspan="3">50 Conv11 (raw) Conv11 (smooth) 100 Validation mIoU 150 200 Epoch 71.23 72.37 250 72.30 72.07 72.04 300 Conv11+T (raw) Conv11+C (smooth) unary (smooth) unary (raw) Conv11+C+T (smooth) Conv11+C+T (raw) Conv11+C (raw) Conv11+T (smooth)</td><td>Score [%]</td><td>68.5 69.0 69.5 70.0 70.5 71.0</td><td>0</td><td>50 Conv11 (raw) Conv11 (smooth) 100 Conv11+T (raw) Conv11+T (smooth) Conv11+C (raw) Conv11+C (smooth) Conv11+C+T (raw) Conv11+C+T (smooth) Train mIoU 150 Epoch unary (raw) unary (smooth)</td><td>200 68.37 70.83 250 70.90 69.29 69.26 300</td></tr><tr><td/><td/><td/><td colspan="3">(a) Validation mIoU over time</td><td/><td/><td/><td>(b) Train mIoU over time</td></tr><tr><td colspan="4">Figure 2: Method</td><td colspan="6">Unary DeepLab ConvCRF Conv+T Conv+C Conv+CT</td></tr><tr><td/><td/><td colspan="2">mIoU [%]</td><td>71.23</td><td>72.02</td><td colspan="2">72.04</td><td/><td>72.07</td><td>72.30</td><td>72.37</td></tr><tr><td/><td/><td colspan="2">Accuracy [%]</td><td>91.84</td><td>94.01</td><td colspan="2">93.99</td><td/><td>94.01</td><td>94.01</td><td>94.03</td></tr><tr><td/><td/><td colspan="3">train mIoU [%] 68.37</td><td>68.61</td><td colspan="2">69.26</td><td/><td>69.29</td><td>70.90</td><td>70.83</td></tr></table>

Performance comparison of CRFs on validation data using decoupled training. +C uses convolutions as compatibility transformation and +T learns the Gaussian features. The same unaries were used for all approaches, only the CRF code from DeepLab was utilized.

Table content: <table/>

Table 2, the training curves are visualized in Figure2. In all experiments, applying CRFs boost the performance considerably. The experiments also confirm the observation of Section 5.1, that ConvCRF perform slightly better than FullCRFs. We also observe that the ConvCRF Performance comparison of end-to-end trained CRFs.

Table content: <table><tr><td>Method</td><td colspan="3">Unary CRFasRNN ConvCRF</td></tr><tr><td>mIoU [%]</td><td>71.23</td><td>72.12</td><td>73.06</td></tr><tr><td>Accuracy [%]</td><td>93.80</td><td>94.08</td><td>94.27</td></tr><tr><td colspan="2">train mIoU [%] 91.84</td><td>93.70</td><td>93.71</td></tr></table>

Peer review (iclr2019):
 The authors propose an efficient method to perform message passing on a truncated Gaussian kernel CRF. The main contributions are the definition of a specific form of truncated Gaussian kernel that allows for fast message passing via convolutions, and the implementation of such parallelized message passing on GPU. In my opinion, the paper fails to convey the main idea in a clear and precise manner, the notation is mixed and often confusing, furthermore there are a number of sentences that should be rephrased to be less sensationalist, or removed. The experiments seem to show performance in par with the FullCRF on decoupled training, which seem in contrast with the much bigger performance gain of the first experiment on syntetic data. No discussion has been provided as to the possible reasons of this performance gap, although the experimental settings appear to be similar. Finally, in the last experiments with end-to-end training the authors report a performance improvement over CRFasRNN, a 3 years old paper that is far away in terms of performance with the current SOTA on Pascal VOC. The authors base on a different network than that of the CRFasRNN baseline (i.e., the difference is not only in the CRF implementation, but rather the whole network before the CRF in the proposed method), it is therefore difficult to say whether the performance improvement is due to the ResNet101 + FCN unary potentials, which is not a contribution of this manuscript, or to the proposed CRF. In general, I believe that the considerable speed gain of the proposed method might be enough to justify a publication, but the paper should be phrased in that sense if that was the intention of the authors. It is unclear to me whether the main contribution they claim is segmentation performance (IoU) or speed or both. The main contributions of this work should be stated clearly, and the modelling differences w.r.t. the FullCRF model that they aim to improve should be more explicit in the text rather than let to the reader to infer comparing the formulas. On these grounds, I suggest a major revision of the paper and I don*t recommend publication at this stage. MAJOR 1) I firmly advocate against making strong claims, unless supported by solid proofs. I strongly recommend to rephrase, if not remove, exaggerate claims such as: a) "[deep networks] lack the capability to utilize context information and cannot model interactions between predictions directly". This is simply not true. Any CNN with enough layers will exploit contextual information. Furthermore, any autoregressive model will model the interaction between predictions directly. See e.g., "RiFCN: Recurrent Network in Fully Convolutional Network for Semantic Segmentation of High Resolution Remote Sensing Images" by Mou et Al., "ReSeg: A Recurrent Neural Network-based Model for Semantic Segmentation" by Visin et Al., or "Predicting Deeper into the Future of Semantic Segmentation" by Luc et Al. for video semantic segmentation. b) "CRF inference is two orders of magnitude slower than CNN inference": this, of course, depends on the kind of CRF. c) "The long training times of the current generation of CRFs also make more in-depth research and experiments with such structured models impractical": again, not true. While it*s true that CRFs tend to be slow, research with such models is not impractical and indeed there are papers that focus exactly on that (among the others, some of the ones cited in this manuscript). d) "we propose to add the strong and valid assumption of conditional independence": as with every assumption, this is an approximation. I wouldn*t claim it to be valid nor invalid, as it is simply a modeling choice. e) "Predictions are pixel-wise and conditionally independendent (given the common feature base of nearby pixels). Structured knowledge and background context is ignored in these models.". It*s unclear what is meant by "structured knowledge", but to my best understanding this sentence is misleading or wrong. Background context is considered by CNN-based models, as well as the general structure in the image. f) "In the context of semantic segmentation most CRF based approaches are based on the Fully Connected CRF". CRFs have been used much earlier than 2011, before Fully Connected CRF was published. g) "This makes the theoretical foundation of ConvCRF very promising, strong and valid assumptions are the powerhouse of machine learning modelling." The authors here propose a logical, but quite obvious, approximation, i.e., to constrain the CRF to model dependencies in a local neighborhood. This is the same implicit assumption of many other Gaussian kernels and algorithms for approximated inference. For how it*s surely valid, and possibly strong, I don*t see how it can make a "theoretical foundation". The self-congratulatory closure is unnecessary, and inappropriate. 2) While CRFs have been used for a long time on visual data, the citations in this work focus mostly on the last few years. I suggest to add at least one of the following: * “Discriminative fields for modeling spatial dependencies in natural images" 2003 * "Multiscale conditional random fields for image labelling" 2004 * “Textonboost: Joint appearance, shape and context modeling for mulit-class object recognition and segmentation,” 2006 It could also be beneficial to the reader to add to the references broad overview works, such as "An Introduction to Conditional Random Fields" by Charles Sutton and Andrew McCallum, 2011, and/or "Structured prediction and learning in computer vision" by Nowozin and Lampert, 2011. 3) Line 5 of the algorithm adds the unary potentials at each iteration of message passing. Can you elaborate on the motivation behind this choice? The algorithm is already initialized with such potentials, and to my best knowledge unary potentials are not usually added in the mean field message passing loop. It would be interesting to compare the performance of the algorithm with and without this addition. 4) Sec4.1 reports that the filters are constant over the channel dimension c and that, in other words, this can be seen as applying the convolution over the dimension c. I fail to understand this sentence. My understanding from the formula is that the same kernel is applied to all the channels of the input, i.e., the channels of the input fed to the CRF are all processed in the same way. This should be explained clearly and the reasoning behind this choice should be explained as well. Furthermore, if I am not mistaken the authors learn a different filter in each position *of the input* rather than reusing the same filters at every position. This choice should be clarified and discussed. 5) Regarding the implementation, is there a reason not to apply a convolution with a flipped kernel to compute the cross-correlation? Also, IIRC if the kernel is symmetric (as should be for a Gaussian kernel) convolution and cross-correlation are the same. 6) The notation is often ambiguous and at times unnecessarely heavy. I strongly recommend to go over the manuscript and use a consistent notation, making sure that every element of the notation is introduced before or right after it*s used. In particular, a) Sec3: in the text, a segmentation instance is referred to as X, while in the formula as .hat x. .tilde I is never introduced. k_{.alpha} is defined but I believe never used (I suggest to drop the name if there is no reference to it). Is there a reason to drop the subscript G in the FullCRF pairwise potential? Or conversely, is there a reason to have it everywhere else? Furthermore, there doesn*t seem to be a difference between k_G, k_g and g, I suggest to use only one consistent notation to refer to the Gaussian kernels throughout the paper. It*s also unclear if the I superscript is needed for the feature vectors. b) Sec4.1, The shape of the Gaussian kernels is the same as that of the input. I believe that the input in this context refers to a patch and not to the whole image. If so, this should be specified, otherwise the dimensions of the kernel should be referred to with a different letter than those of the input. c) Sec4.1, I believe dx and dy refer to the in-kernel displacement. Their semantic is not clear from the text and should be defined properly. d) Sec4.1, the feature vectors are defined in the text as f_1..f_d. The formula of the kernel uses f_i^{(d)} instead. It*s unclear what the superscripts stands for and whether it is actually useful or redundant. e) Sec4.1, x and y are not defined, I suspect they refer to the position of the pixel, which was previously encoded as p_i and p_j. Once again, the notation should be consistent across the manuscript. f) In the definition of the convCRFs, w is used for the width of the input, w_i for the weights of the kernels. In the FullCRF, w^{(1)} and w^{(2)} for the potentials, w^{(m)} for the sum over the kernels. k is used for the kernel dimension, k_G to refer to the kernel itself, as well as g. The notation could be made less ambiguous and consistent (superscript vs subscript semantics). g) Sec3, the number of pixel is defined as n but in Formula 2 N is used instead. g) Vectors and matrices should be bold-face. The use of capital letters for constants might also improve the readability of the manuscript. 7) The experiments with the Conv (ConvCRF?) variants of Table 2 are not discussed in the text. 8) Although Sec5.2 concludes with "The experiments also confirm the observation of Sec5.1, that ConvCRF performs slightly better than FullCRF", Sec5.1 reported that "it can be seen that ConvCRFs outperform FullCRFs significantly". The authors should decide whether the results are slightly better or outperform the baseline. In general a in-depth discussion on the performance of the algorithm is missing. 9) Sec5.3, it*s unclear what this sentence means "introduce an auxiliary unary loss to counterbalance the vanishing gradient problem". If such a term has been added, it should be reported in a formula and it*s effectiveness should be supported by experimental data. MINOR m1) In the related work, the sentence "transposed convolution layers are applied at the end of the prediction pipeline ot produce high-resolution output" seems to suggest these are always applied, while many recent methods rely on bilinear upsampling to recover the original resolution. Please rephrase it accordingly. m2) In Parameter learning in CRF: "the idea utilizes, that for the message passing the identity .. is valid." This sentence doesn*t make any sense to me. Is it possible it is a leftover? m4) In Sec3, the features vectors [...] may depend on the input image I. I am confused as to when they might be independent of the image. Can you elaborate on that? m5) In Sec3, it*s unclear to me what the vertical bar in the Pot model stands for. I believe the correct formula should be 1_{[xi != xj]}. m6) In mean field inference, Algorithm 1 does not refer to FullCRFs. m7) End of page 6, "Note that this gives FullCRFs a natural advantage. The performance of CRFs however is very robust [...]". Why is this an advantage for FullCRFs? How does that relate to the following sentence? m8) Sec4.1, the authors claim that one of the key contribution of the paper is that exact message passing is efficient. Given the locality assumption, message passing is approximate - which is also why it*s efficient. The authors could instead argue that using convolutions is faster and possibly leads to better final performance than using the permutohedral lattice approximation (although it*s unclear whether this is the case from the experiments), with proper reference to compelling results in this direction. Finally, a few typos: * Abstract, space missing after GPUs * Introduction, Convolutional Neuronal -> Convolutional Neural * Introduction, order of magnitude slower then -> than * Introduction, to slow -> too slow * Parameter learning in CRF: missing space before proposed to use gradient descent * Parameter learning in CRF: gradient decent -> descent * Parameter learning in CRF: extra comma after "another advantage of this method is" * Sec 3: "weighted sum of Gaussian kernels", the apex of the second should be "M" I believe. * Sec 3: "can be chosen arbitrary" -> arbitrarily * Sec 5.2, beginning of page 8: then -> than