the same (i.e. to globally propagate information in the graph
structures), the mechanism to achieve this objective is very
different in these two approaches. While MRFs and CRFs
typically employ graphs with a ﬁxed grid structure (e.g., one
where each node is connected to its four closest neighbors),
random walk methods are much more ﬂexible and can implement any arbitrary graph structure via the afﬁnity matrix
speciﬁcation. Thus, since our proposed RWN is based on
random walks, it can employ any arbitrary graph structure,
which can be beneﬁcial as different problems may require
different graph structures.
Additionally, to globally propagate information among
the nodes, MRFs and CRFs need to employ approximate
inference techniques, because exact inference tends to be
intractable in graphs with a grid structure. Integrating such
approximate inference techniques into the steps of FCN
training and prediction can be challenging and may require
lots of domain-speciﬁc modiﬁcations. In comparison, random walk methods globally propagate information among
the nodes via a simple matrix multiplication. Not only is
the matrix multiplication efﬁcient and exact, but it is also
easy to integrate into the traditional FCN framework for
both training and prediction schemes. Additionally, due to
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