the coarse FCN predictions. However, in order to effectively recover ﬁne details one must employ nearly as many
deconvolutional layers as the number of convolutional layers, which yields a large growth in number of parameters
(see Table 1).
Unlike these prior methods, our implementation of RWN
needs only 131additional parameters over the base FCN.
These additional parameters represent only 0:0008% of the
total number of parameters in the network. In addition, our
RWN uses standard convolution and matrix multiplication.
Thus, it does not need to incorporate complicated loss functions or new complex layers [27, 5, 19, 17]. Finally, unlike the methods in [4, 6, 25, 14] that predict and reﬁne the
segmentations disjointly, our RWN model jointly optimizes
pixel afﬁnity and semantic segmentation in an end-to-end
fashion. Our experiments show that this leads to spatially
smoother segmentations.
3. Background
Random Graph Walks. Random walks are one of
the most widely known and used methods in graph theory [21]. Most notably, the concept of random walks led to
FC8 ActivationsDeepLab FCN Architecture
RGB ImageSparse Pairwise L1 Distances    Sparse Pixel    Similarity Matrix1 x 1 x k conv
   Ground Truth   Pixel Similarities
Most current semantic segmentation methods rely on fully convolutional
networks (FCNs). However, their use of large receptive fields and many pooling
layers cause low spatial resolution inside the deep layers. This leads to
predictions with poor localization around the boundaries. Prior work has
attempted to address this issue by post-processing predictions with CRFs or
MRFs. But such models often fail to capture semantic relationships between
objects, which causes spatially disjoint predictions. To overcome these
problems, recent methods integrated CRFs or MRFs into an FCN framework. The
downside of these new models is that they have much higher complexity than
traditional FCNs, which renders training and testing more challenging.
  In this work we introduce a simple, yet effective Convolutional Random Walk
Network (RWN) that addresses the issues of poor boundary localization and
spatially fragmented predictions with very little increase in model complexity.
Our proposed RWN jointly optimizes the objectives of pixelwise affinity and
semantic segmentation. It combines these two objectives via a novel random walk
layer that enforces consistent spatial grouping in the deep layers of the
network. Our RWN is implemented using standard convolution and matrix
multiplication. This allows an easy integration into existing FCN frameworks
and it enables end-to-end training of the whole network via standard
back-propagation. Our implementation of RWN requires just $131$ additional
parameters compared to the traditional FCNs, and yet it consistently produces
an improvement over the FCNs on semantic segmentation and scene labeling.
Gedas Bertasius Lorenzo Torresani Stella X. Yu Jianbo Shi