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
Convolutional Random Walk Networks for Semantic Image Segmentation
Gedas Bertasius1, Lorenzo Torresani2, Stella X. Yu3, Jianbo Shi1
1University of Pennsylvania,2Dartmouth College,3UC Berkeley ICSI
{gberta,jshi}@seas.upenn.edu lt@dartmouth.edu stella.yu@berkeley.edu
Abstract
Most current semantic segmentation methods rely on
fully convolutional networks (FCNs). However, their use of
large receptive ﬁelds 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 mod-
els often fail to capture semantic relationships between ob-
jects, which causes spatially disjoint predictions. To over-
come 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 tradi-
tional FCNs, which renders training and testing more chal-
lenging.
In this work we introduce a simple, yet effective Convo-
lutional Random Walk Network (RWN) that addresses the
issues of poor boundary localization and spatially frag-
mented predictions with very little increase in model com-
plexity. Our proposed RWN jointly optimizes the objectives
of pixelwise afﬁnity and semantic segmentation. It com-
bines 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.
1. Introduction
Fully convolutional networks (FCNs) were ﬁrst intro-
duced in [20] where they were shown to yield signiﬁcant
improvements in semantic image segmentation. Adopt-
ing the FCN approach, many subsequent methods have
achieved even better performance [6, 27, 8, 12, 17, 6, 27, 8,
19, 23]. However, traditional FCN-based methods tend to
suffer from several limitations. Large receptive ﬁelds in the
Input
 DeepLab [6]
 DeepLab-CRF [6]
Figure 1: Examples illustrating shortcomings of prior se-
mantic segmentation methods. Segments produced by
FCNs are poorly localized around object boundaries, while
Dense-CRF produce spatially-disjoint object segments.
convolutional layers and the presence of pooling layers lead
to low spatial resolution in the deepest FCN layers. As a re-
sult, their predicted segments tend to be blobby and lack ﬁne
object boundary details. We report in Fig. 1 some examples
illustrating typical poor localization of objects in the outputs
of FCNs. Recently, Chen at al. [6] addressed this issue by
applying a Dense-CRF post-processing step [15] on top of
coarse FCN segmentations. However, such approaches of-
ten fail to accurately capture semantic relationships between
objects and lead to spatially fragmented segmentations (see
an example in the last column of Fig. 1).
To address these problems several recent methods in-
tegrated CRFs or MRFs directly into the FCN frame-
work [27, 19, 17, 5]. However, these new models typi-
cally involve (1) a large number of parameters, (2) com-
plex loss functions requiring specialized model training or
(3) recurrent layers, which make training and testing more
complicated. We summarize the most prominent of these
approaches and their model complexities in Table 1.
We note that we do not claim that using complex loss
functions always makes the model overly complex and too
difﬁcult to use. If a complex loss is integrated into an FCN
framework such that the FCN can still be trained in a stan-
dard fashion, and produce better results than using stan-
dard losses, then such a model is beneﬁcial. However, in
the context of prior segmentation methods [27, 19, 17, 5],
such complex losses often require: 1) modifying the net-
work structure (casting CNN into an RNN) [27, 5], or 2)
using a complicated multi-stage learning scheme, where
different layers are optimized during a different training
stage [19, 17]. Due to such complex training procedures,
1arXiv:1605.07681v3  [cs.CV]  8 May 2017
[6] [5] [23] [27] [19] RWN
requires post-processing? 3777 7 7
uses complex loss? 7773 3 7
requires recurrent layers? 7373 7 7
model size (in MB) 79 79 961 514 >1000 79
Table 1: Summary of recent semantic segmentation mod-
els. For each model, we report whether it requires: (1) CRF
post-processing, (2) complex loss functions, or (3) recur-
rent layers. We also list the size of the model (using the
size of Caffe [13] models in MB). We note that unlike prior
methods, our RWN does not need post-processing, it is im-
plemented using standard layers and loss functions, and it
also has a compact model.
which are adapted for speciﬁc tasks and datasets, these
models can be quite difﬁcult to adapt for new tasks and
datasets, which is disadvantageous.
Inspired by random walk methods [21, 3, 24], in this
work we introduce a simple, yet effective alternative to tra-
ditional FCNs: a Convolutional Random Walk Network
(RWN) that combines the strengths of FCNs and ran-
dom walk methods. Our model addresses the issues of
(1) poor localization around the boundaries suffered by
FCNs and (2) spatially disjoint segments produced by dense
CRFs. Additionally, unlike recent semantic segmentation
approaches [23, 27, 19, 17], our RWN does so without sig-
niﬁcantly increasing the complexity of the model.
Our proposed RWN jointly optimizes (1) pixelwise afﬁn-
ity and (2) semantic segmentation learning objectives that
are linked via a novel random walk layer, which enforces
spatial consistency in the deepest layers of the network. The
random walk layer is implemented via matrix multiplica-
tion. As a result, RWN seamlessly integrates both afﬁnity
and segmentation branches, and can be jointly trained end-
to-end via standard back-propagation with minimal modiﬁ-
cations to the existing FCN framework. Additionally, our
implementation of RWN requires only 131additional pa-
rameters. Thus, the effective complexity of our model is
the same as the complexity of traditional FCNs (see Ta-
ble 1). We compare our approach to several variants of the
DeepLab semantic segmentation system [6, 7], and show
that our proposed RWN consistently produces better per-
formance over these baselines for the tasks of semantic seg-
mentation and scene labeling.
2. Related Work
The recent introduction of fully convolutional networks
(FCNs) [20] has led to remarkable advances in semantic
segmentation. However, due to the large receptive ﬁelds
and many pooling layers, segments predicted by FCNs tend
to be blobby and lack ﬁne object boundary details. Recently
there have been several attempts to address these problems.
These approaches can be divided into several groups.The work in [4, 6, 25, 14, 4] used FCN predictions as
unary potentials in a separate globalization model that re-
ﬁnes the segments using similarity cues based on regions
or boundaries. One disadvantage of these methods is that
the learning of the unary potentials and the training of the
globalization model are completely disjoint. As a result,
these methods often fail to capture semantic relationships
between objects, which produces segmentation results that
are spatially disjoint (see the right side of Fig. 1).
To address these issues, several recent methods [27, 19,
17] have proposed to integrate a CRF or a MRF into the net-
work, thus enabling end-to-end training of the joint model.
However, the merging of these two models leads to a dra-
matic increase in complexity and number of parameters.
For instance, the method in [27], requires to cast the original
FCN into a Recurrent Neural Network (RNN), which ren-
ders the model much bigger in size (see Table 1). A recent
method [5] jointly predicts boundaries and segmentations,
and then combines them using a recurrent layer, which also
requires complex modiﬁcations to the existing FCN frame-
work.
The work in [19] proposes to use local convolutional lay-
ers, which leads to a signiﬁcantly larger number of parame-
ters. Similarly, the method in [17] proposes to model unary
and pairwise potentials by separate multi-scale branches.
This leads to a network with at least twice as many parame-
ters as the traditional FCN and a much more complex multi-
stage training procedure.
In addition to the above methods, it is worth mentioning
deconvolutional networks [23, 12], which use deconvolu-
tion and unpooling layers to recover ﬁne object details from
the coarse FCN predictions. However, in order to effec-
tively recover ﬁne details one must employ nearly as many
deconvolutional layers as the number of convolutional lay-
ers, 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 func-
tions or new complex layers [27, 5, 19, 17]. Finally, un-
like 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 the-
ory [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
 Exp
   Ground Truth     Segmentation
      Segmentation            Random Walk Layerˆy=AfAffinity Learning BranchPairwise L1  Distances
n⇥n⇥mRow-Normalization:n⇥n⇥3
f2Rn2⇥mA2Rn2⇥n2W2Rn2⇥n2F2Rn2⇥n2⇥kFigure 2: The architecture of our proposed Random Walk Network (RWN) (best viewed in color). Our RWN consists
of two branches: (1) one branch devoted to the segmentation predictions , and (2) another branch predicting pixel-level
afﬁnities. These two branches are then merged via a novel random walk layer that encourages spatially smooth segmentation
predictions. The entire RWN is jointly optimized end-to-end via a standard back-propagation algorithm.
the development of PageRank [24] and Personalized PageR-
ank [3], which are widely used for many applications. Let
G= (V;E)denote an undirected graph with a set of ver-
ticesVand a set of edges E. Then a random walk in
such graph can be characterized by the transition probabil-
ities between its vertices. Let Wbe a symmetric nn
afﬁnity matrix, where ndenotes the number of nodes in
the graph and where Wij2[0;1]denotes how similar the
nodesiandjare. In the context of a semantic segmen-
tation problem, each pixel in the image can be viewed as
a separate node in the graph, where the similarity between
two nodes can be evaluated according to some metric (e.g.
color or texture similarity etc). Then let Dindicate a diag-
onalnnmatrix, which stores the degree values for each
node:Dii=Pn
j=1Wijfor alljexcepti=j. Then, we can
express our random walk transition matrix as A=D1W.
Given this setup, we want to model how the information
in the graph spreads if we start at a particular node, and
perform a random walk in this graph. Let ytbe an1vec-
tor denoting a node distribution at time t. In the context of
the PageRank algorithm, ytmay indicate the rank estimates
associated with each of the nWeb pages at time t. Then,
according to the random walk theory, we can spread the
rank information in the graph by performing a one-step ran-
dom walk. This process can be expressed as yt+1=Ayt,
whereyt+1denotes a newly obtained rank distribution after
one random walk step, the matrix Acontains the random
walk transition probabilities, and ytis the rank distribution
at time step t. Thus, we can observe that the information
among the nodes can be diffused, by simply multiplying the
random walk transition probability matrix A, with the rank
distribution ytat a particular time t. This process can be
repeated multiple times, until convergence is reached. For a
more detailed survey please see [21, 24].
Difference from MRF/CRF Approaches. CRFs andMRFs have been widely used in structured prediction prob-
lems [16]. Recently, CRFs and MRFs have also been inte-
grated into the fully convolutional network framework for
semantic segmentation [27, 19, 17]. We want to stress that
while the goals of CRF/MRF and random walk methods are
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 im-
plement 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, ran-
dom 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
the use of standard convolution and matrix multiplication
operations, our RWN can be trivially trained via standard
back-propagation in an end-to-end fashion.
4. Convolutional Random Walk Networks
In this work, our goal is to integrate a random walk pro-
cess into the FCN architecture to encourage coherent se-
mantic segmentation among pixels that are similar to each
other. Such a process introduces an explicit grouping mech-
anism, which should be beneﬁcial in addressing the issues
of (1) poor localization around the boundaries, and (2) spa-
tially fragmented segmentations.
A schematic illustration of our proposed RWN architec-
ture is presented in Fig. 2. Our RWN is a network com-
posed of two branches: (1) one branch that predicts seman-
tic segmentation potentials, and (2) another branch devoted
to predicting pixel-level afﬁnities. These two branches are
merged via a novel random walk layer that encourages spa-
tially coherent semantic segmentation. The entire RWN can
be jointly optimized end-to-end. We now describe each of
the components of the RWN architecture in more detail.
4.1. Semantic Segmentation Branch
For the semantic segmentation branch, we present results
for several variants of the DeepLab segmentation systems,
including DeepLab-LargeFOV [6], DeepLab-attention [7],
and DeepLab-v2, which is one of the top performing seg-
mentation systems. DeepLab-largeFOV is a fully convolu-
tional adaptation of the VGG [26] architecture, which con-
tains 16convolutional layers. DeepLab-attention [7], is a
multi-scale VGG based network, for which each multi-scale
branch focuses on a speciﬁc part of the image. Finally,
DeepLab-v2 is a multi-scale network based on the resid-
ual network [11] implementation. We note that even though
we use a DeepLab architecture in our experiments, other ar-
chitectures such as [2] and many others could be integrated
into our framework.
4.2. Pixel-Level Afﬁnity Branch
To learn the pairwise pixel-level afﬁnities, we employ a
separate afﬁnity learning branch with its own learning ob-
jective (See Fig. 2). The afﬁnity branch is connected with
the inputnn3RGB image, and low-level conv1_1and
conv1_2layers. The feature maps corresponding to these
layers arennin width and height but they have a differ-
ent number of channels ( 3;64;and64respectively). Let k
be the total number of afﬁnity learning parameters (in our
casek= 3 + 64 + 64 = 131 ). Then, let Fbe a sparse
n2n2kmatrix that stores L1distances between each
pixel and all of its neighbors within a radius R, according
to each channel. Note that the distances are notsummed
up across the kchannels, but instead they are computed and
stored separately for each channel. The resulting matrix F
is then used as an input to the afﬁnity branch, as shown in
Figure 2.
The afﬁnity branch consists of a 11kconvolutional
layer and an exponential layer. The output of the exponen-
tial layer is then attached to the Euclidean loss layer and is
optimized to predict the ground truth pixel afﬁnities, which
are obtained from the original semantic segmentation an-
Input
 DeepLab_v2
 RWN_v2
Figure 3: A ﬁgure illustrating the segmentation results of
our RWN and the DeepLab-v2 network. Note that RWN
produced segmentations are spatially smoother and produce
less false positive predictions than the DeepLab-v2 system.
notations. Speciﬁcally, we set the ground truth afﬁnity be-
tween two pixels to 1if the pixels share the same semantic
label and have distance less than Rfrom each other. Note
thatF, which is used as an input to the afﬁnity branch, is a
sparse matrix, as only a small fraction of all the entries in F
are populated with non-zero values. The rest of the entries
are ignored during the computation.
Also note that we only use features from RGB, conv1_1
andconv1_2layers, because they are not affected by pool-
ing, and thus, preserve the original spatial resolution. We
also experimented with using features from deeper FCN
layers such as fc6, and fc7. However, we observed that
features from deeper layers are highly correlated to the
predicted semantic segmentation unary potentials, which
causes redundancy and little improvement in the segmen-
tation performance. We also experimented with using more
than one convolutional layer in the afﬁnity learning branch,
but observed that additional layers provide negligible im-
provements in accuracy.
4.3. Random Walk Layer
To integrate the semantic segmentation potentials and
our learned pixel-level afﬁnities, we introduce a novel ran-
dom walk layer, which propagates the semantic segmenta-
tion information based on the learned afﬁnities. The random
walk layer is connected to the two bottom layers: (1) the fc8
layer containing the semantic segmentation potentials, and
(2) the afﬁnity layer that outputs a sparse n2n2random
walk transition matrix A. Then, let fdenote the activa-
tion values from the fc8layer, reshaped to the dimensions
ofn2m, wheren2refers to the number of pixels, and
mis the number of object classes in the dataset. A single
random walk layer implements one step of the random walk
Method aero bike bird boat bottle bus car cat chair cow table dog horse mbike person plant sheep sofa train tv mean overall
DeepLab-largeFOV 79.8 71.5 78.9 70.9 72.1 87.9 81.2 85.7 46.9 80.9 56.5 82.6 77.9 79.3 80.1 64.4 77.6 52.7 80.3 70.0 73.8 76.0
RWN-largeFOV 81.6 72.1 82.3 72.0 75.4 89.1 82.5 87.4 49.1 83.6 57.9 84.8 80.7 80.2 81.2 65.7 79.7 55.5 81.5 74.0 75.8 77.9
DeepLab-attention 83.4 76.0 83.0 74.2 77.6 91.6 85.2 89.1 54.4 86.1 62.9 86.7 83.8 84.2 82.4 70.2 84.7 61.0 84.8 77.9 79.0 80.5
RWN-attention 84.7 76.6 85.5 74.0 79.0 92.4 85.6 90.0 55.6 87.4 63.5 88.2 85.0 84.8 83.4 70.1 85.9 62.6 85.1 79.3 79.9 81.5
DeepLab-v2 85.5 50.6 86.9 74.4 82.7 93.1 88.4 91.9 62.1 89.7 71.5 90.3 86.2 86.3 84.6 75.1 87.6 72.2 87.8 81.3 81.4 83.4
RWN-v2 86.0 50.0 88.4 73.5 83.9 93.4 88.6 92.5 63.9 90.9 72.6 90.9 87.3 86.9 85.7 75.0 89.0 74.0 88.1 82.3 82.1 84.3
Table 2: Semantic segmentation results on the SBD dataset according to the per-pixel Intersection over Union evaluation
metric. From the results, we observe that our proposed RWN consistently outperforms DeepLab-LargeFOV , DeepLab-
attention, and DeepLab-v2 baselines.
process, which can be performed as ^y=Af, where ^yindi-
cates the diffused segmentation predictions, and Adenotes
the random walk transition matrix.
The random walk layer is then attached to the softmax
loss layer, and is optimized to predict ground truth semantic
segmentations. One of the advantages of our proposed ran-
dom walk layer is that it is implemented as a matrix mul-
tiplication, which makes it possible to back-propagate the
gradients to both (1) the afﬁnity branch and (2) the segmen-
tation branch. Let the softmax-loss gradient be an n2m
matrix@L
@^y, wheren2is the number of pixels in the fc8layer,
andmis the number of predicted object classes. Then the
gradients, which are back-propagated to the semantic seg-
mentation branch are computed as@L
@f=AT@L
@^y, whereAT
is the transposed random walk transition matrix. Also, the
gradients, that are back-propagated to the afﬁnity branch
are computed as@L
@A=@L
@^yfT, wherefTis amn2matrix
that contains transposed activation values from the fc8layer
of the segmentation branch. We note that@L
@Ais asparse
n2n2matrix, which means that the above matrix mul-
tiplication only considers the pixel pairs that correspond to
the non-zero entries in the random walk transition matrix A.
4.4. Random Walk Prediction at Testing
In the previous subsection, we mentioned that the pre-
diction in the random walk layer can be done via a simple
matrix multiplication operation ^y=Af, whereAdenotes
the random walk transition matrix, and fdepicts the activa-
tion values from the fc8layer. Typically, we want to apply
multiple random walk steps until convergence is reached.
However, we also do not want to deviate too much from our
initial segmentation predictions, in case the random walk
transition matrix is not perfectly accurate, which is a rea-
sonable expectation. Thus, our prediction scheme needs to
balance two effects: (1) propagating the segmentation in-
formation across the nodes using a random walk transition
matrix, and (2) not deviating too much from the initial seg-
mentation.
This tradeoff between the two quantities is very simi-
lar to the idea behind MRF and CRF models, which try to
minimize an energy formed by unary and pairwise terms.
However, as discussed earlier, MRF and CRF methods tend
to use 1) grid structure graphs and 2) various approximateinference techniques to propagate segmentation informa-
tion globally. In comparison, our random walk approach
is advantageous because it can use 1) any arbitrary graph
structure and 2) an exact matrix multiplication operation to
achieve the same goal.
Let us ﬁrst denote our segmentation prediction after t+1
random walk steps as ^yt+1. Then our general prediction
scheme can be written as:
^yt+1=A^yt+ (1)f (1)
wheredenotes a parameter [0;1]that controls the
tradeoff between (1) diffusing segmentation information
along the connections of a random walk transition matrix
and (2) not deviating too much from initial segmentation
values (i.e. the outputs of the last layer of the FCN). Let us
now initialize ^y0to contain the output values from the fc8
layer, which we denoted with f. Then we can write our pre-
diction equation by substituting the recurrent expressions:
^yt+1= (A)t+1f+ (1)tX
i=0(A)if (2)
Now, because we want to apply our random walk pro-
cedure until convergence we set t=1. Then, because
our random walk transition matrix is stochastic we know
thatlimt!1(A)t+1= 0 . Furthermore, we can write
St=Pt
i=0Ai=I+A+A2+:::+At, whereIis
an identity matrix, and where Stdenotes a partial sum of
random walk transitions until iteration t. We can then write
StASt=IAt+1, which implies:
(IA)St=IAt+1(3)
From our previous derivation, we already know that
limt!1(A)t+1= 0, which implies that
S1= (IA)1(4)
Thus, our ﬁnal prediction equation, which corresponds
to applying repeated random walk steps until convergence,
can be written as
^y1= (IA)1f (5)
Input
 DeepLab_v2-CRF
 RWN_v2
Figure 4: Comparison of segmentation results produced by
our RWN versus the DeepLab-v2-CRF system. It can be no-
ticed that, despite not using any post-processing steps, our
RWN predicts ﬁne object details (e.g., bike wheels or plane
wings) more accurately than DeepLab-v2-CRF, which fails
to capture some these object parts.
In practice, the random walk transition matrix Ais pretty
large, and inverting it is impractical. To deal with this prob-
lem, we shrink the matrix (IA)using a simple and ef-
ﬁcient technique presented in [1], and then invert it to com-
pute the ﬁnal segmentation. In the experimental section, we
show that such a prediction scheme produces solid results
and is still pretty efﬁcient ( 1 second per image). We also
note that we use this prediction scheme only during test-
ing. During training we employ a scheme that uses a single
random walk step (but with a much larger radius), which is
faster. We explain this procedure in the next subsection.
4.5. Implementation Details
We jointly train our RWN in an end-to-end fashion for
2000 iterations, with a learning rate of 105,0:9momen-
tum, the weight decay of 5105, and 15samples per batch.
For the RWN model, we set the tradeoff parameter to
0:01. During testing we set the random walk connectivity
radiusR= 5 and apply the random walk procedure un-
til convergence. However, during training we set R= 40 ,
and apply a single random walk step. This training strategy
works well because increasing the radius size eliminates the
need for multiple random walk steps, which speeds up the
training. However, using R= 5 and applying an inﬁnite
number of random walk steps until convergence still yields
slightly better results (see study in 5.4), so we use it dur-
ing testing. For all of our experiments, we use a Caffe li-
brary [13]. During training, we also employ data augmen-
tation techniques such as cropping, and mirroring.
5. Experimental Results
In this section, we present our results for semantic seg-
mentation on the SBD [10] dataset, which contains objects
and their per-pixel labels for 20Pascal VOC classes (ex-
cluding the background class). We also include scene label-Method mean IOU overall IOU
DeepLab-largeFOV-CRF 75.7 77.7
RWN-largeFOV 75.8 77.9
DeepLab-attention-CRF 79.9 81.6
RWN-attention 79.9 81.5
DeepLab-v2-CRF 81.9 84.2
RWN-v2 82.1 84.3
DeepLab-DT 76.6 78.7
RWN 76.7 78.8
Table 3: Quantitative comparison between our RWN model
and several variants of the DeepLab system that use a dense
CRF or a domain-transfer (DT) ﬁlter for post-processing.
These results suggest that our RWN acts as an effective
globalization scheme, since it produces results that are
similar or even better than the results achieved by post-
processing the DeepLab outputs with a CRF or DT.
ing results on the commonly used Stanford background [9]
and Sift Flow [18] datasets. We evaluate our segmenta-
tion results on these tasks using the standard metric of the
intersection-over-union (IOU) averaged per pixels across all
the classes from each dataset. We also include the class-
agnostic overall pixel intersection-over-union score, which
measures the per-pixel IOU across all classes.
We experiment with several variants of the DeepLab
system [6, 7] as our main baselines throughout our exper-
iments: DeepLab-LargeFOV [6], DeepLab-attention [7],
and DeepLab-v2.
Our evaluations provide evidence for four conclusions:
In subsections 5.1, 5.2, we demonstrate that our pro-
posed RWN outperforms DeepLab baselines for both
semantic segmentation, and scene labeling tasks.
In subsection 5.1, we demonstrate that, compared to
the dense CRF approaches, RWN predicts segmenta-
tions that are spatially smoother.
In Subsection 5.3, we show that our approach is more
efﬁcient than the denseCRF inference.
Finally, in Subsection, 5.4, we demonstrate that our
random walk layer is beneﬁcial and that our model is
ﬂexible to use different graph structures.
5.1. Semantic Segmentation Task
Standard Evaluation. In Table 2, we present semantic
segmentation results on the Pascal SBD dataset [10], which
contains 8055 training and 2857 testing images. These re-
sults indicate that RWN consistently outperforms all three
of the DeepLab baselines. In Figure 3, we also compare
qualitative segmentation results of a DeepLab-v2 network
and our RWN model. We note that the RWN segmenta-
tions contain fewer false positive predictions and are also
spatially smoother across the object regions.
0 2 4 6 8 10 12 14 16 18 200.20.250.30.350.40.450.50.55
Trimap Width (in Pixels)Pixel Classification Error (%)Localization Around the Boundaries Error
  
DeepLab
RWNFigure 5: Localization error around the object boundaries
within a trimap. Compared to the DeepLab system (blue),
our RWN (red) achieves lower segmentation error around
object boundaries for all trimap widths.
Furthermore, in Table 3, we present experiments where
we compare RWN with models using dense CRFs [15] to
post-process the predictions of DeepLab systems. We also
include DeepLab-DT [5], which uses domain-transfer ﬁl-
tering to reﬁne the segmentations inside an FCN. Based on
these results, we observe that, despite not using any post-
processing, our RWN produces results similar to or even
better than the DeepLab models employing post-processing.
These results indicate that RWN can be used as a global-
ization mechanism to ensure spatial coherence in semantic
segmentation predictions. In Figure 4 we present qualita-
tive results where we compare the ﬁnal segmentation pre-
dictions of RWN and the DeepLab-v2-CRF system. Based
on these qualitative results, we observe that RWN captures
more accurately the ﬁne details of the objects, such as the
bike wheels, or plane wings. The DeepLab-v2-CRF system
misses some of these object parts.
Localization Around the Boundaries. Earlier we
claimed that due to the use of large receptive ﬁelds and
many pooling layers, FCNs tend to produce blobby seg-
mentations that lack ﬁne object boundary details. We want
to show that our RWN produces more accurate segmenta-
tions around object boundaries the traditional FCNs. Thus,
adopting the practice from [15], we evaluate segmentation
accuracy around object boundaries. We do so by counting
the relative number of misclassiﬁed pixels within a narrow
band (“trimap”) surrounding the ground truth object bound-
aries. We present these results in Figure 5. The results show
that RWN achieves higher segmentation accuracy than the
DeepLab (DL) system for all trimap widths considered in
this test.
Spatial Smoothness. We also argued that applying the
dense CRF [15] as a post-processing technique often leads
to spatially fragmented segmentations (see the right side of
Fig. 1). How can we evaluate whether a given method pro-
duces spatially smooth or spatially fragmented segmenta-Method MF AP
DeepLab-largeFOV-CRF 0.676 0.457
RWN-largeFOV 0.703 0.494
DeepLab-attention-CRF 0.722 0.521
RWN-attention 0.747 0.556
DeepLab-v2-CRF 0.763 0.584
RWN-v2 0.773 0.595
Table 4: Quantitative comparison of spatial segmentation
smoothness. We extract the boundaries from the predicted
segmentations and evaluate them against ground truth ob-
ject boundaries using max F-score (MF) and average pre-
cision (AP) metrics. These results suggest that RWN seg-
mentations are spatially smoother than the DeepLab-CRF
segmentations across all baselines.
tions? Intuitively, spatially fragmented segmentations will
produce many false boundaries that do not correspond to
actual object boundaries. Thus, to test the spatial smooth-
ness of a given segmentation, we extract the boundaries
from the segmentation and then compare these boundaries
against ground truth object boundaries using the standard
maximum F-score (MF) and average precision (AP) met-
rics, as done in the popular BSDS benchmark [22]. We per-
form this experiment on the Pascal SBD dataset and present
these results in Table 4. We can see that the boundaries ex-
tracted from the RWN segmentations yield better MF and
AP results compared to the boundaries extracted from the
different variants of the DeepLab-CRF system. Thus, these
results suggest that RWN produces spatially smoother seg-
mentations than DeepLab-CRF.
5.2. Scene Labeling
We also tested our RWN on the task of scene labeling
using two popular datasets: Stanford Background [9] and
Sift Flow [18]. Stanford Background is a relatively small
dataset for scene labeling. It contains 715images, which
we randomly split into 600training images and 115test-
ing images. In contrast, the Sift Flow dataset contains 2489
training examples and 201testing images. For all of our
experiments, we use the DeepLab-largeFOV [6] architec-
ture since it is smaller and more efﬁcient to train and test.
To evaluate scene labeling results, we use the overall IOU
evaluation metric which is a commonly used metric for this
task. In Table 5, we present our scene labeling results on
both of these datasets. Our results indicate that our RWN
method outperforms the DeepLab baseline by 2:57%, and
2:54% on these two datasets, respectively.
5.3. Runtime Comparisons
We also include the runtime comparison of our RWN ap-
proach versus the denseCRF inference. We note that us-
ing a single core of a 2:7GHz Intel Core i7 processor, the
denseCRF inference requires 3.301 seconds per image on
Input Image
Iteration 0Iteration 50
Figure 6: A ﬁgure illustrating how the probability predic-
tions change as we apply more random walk steps. Note
that the RWN predictions become more reﬁned and bet-
ter localized around the object boundaries as more random
walk steps are applied.
average on a Pascal SBD dataset. In comparison, a single
iteration of a random walk, which is simply a sparse matrix
multiplication, takes 0.032 seconds on average on the same
Pascal SBD dataset. A DeepLab_v2 post-processed with
denseCRF achieves 81:9%IOU score on this same Pascal
SBD dataset. In comparison, RWN_v2 with a single ran-
dom walk iteration and with R=40 (radius) achieves 82:2%
IOU, which is both more accurate and more than 100times
more efﬁcient than the denseCRF inference.
5.4. Ablation Experiments
Optimal Number of Random Walk Steps. In Figure 7,
we illustrate how the IOU accuracy changes when we use a
different number of random walk steps. We observe that the
segmentation accuracy keeps increasing as we apply more
random walk steps, and that it reaches its peak performance
when the random walk process converges, which indicates
the effectiveness of our random walk step procedure. In
Figure 6, we also illustrate how the predicted object seg-
mentation probabilities change as we apply more random
walk steps. We observe that the object boundaries become
much better localized as more iterations of random walk are
applied.
Radius Size. To analyze the effect of a radius size in
the RWN architecture, we test alternative versions of our
model with different radii sizes. Our results indicate, that
the RWN model produces similar results with different radii
in the interval of R > 3andR < 20if the random walk
step process is applied until convergence. We also note
that, if we select R= 40 , and apply a random walk step
only once , we can achieve the segmentation accuracy of
75:5%and77:6%according to the two evaluation metrics,
0 5 10 15 20 25 30 40 50 60 inf0.7350.740.7450.750.7550.760.765
Number of Random Walk StepsIOU AccuracyAccuracy versus the Number of Random Walk Steps
  
Mean−class IOUFigure 7: IOU accuracy as a function of the number of ran-
dom walk steps. From this plot we observe that the seg-
mentation accuracy keeps improving as we apply more ran-
dom walk steps and that it reaches its peak when the random
walk process converges.
DeepLab-largeFOV RWN-largeFOV
Stanford-BG 65.74 68.31
Sift-Flow 67.31 69.85
Table 5: Scene labeling results on the Stanford Background
and Sift-Flow datasets measured according to the overall
IOU evaluation metric. We use a DeepLab-largeFOV net-
work as base model, and show that our RWN yields better
results on both of these scene labeling datasets.
respectively. In comparison, choosing R= 5 and apply-
ing random walk until convergence yields the accuracies of
75:8%and77:9%, which is slightly better. However, note
that selecting R= 40 , and applying multiple random walk
steps does not yield any improvement in segmentation ac-
curacy. These experiments show the ﬂexibility of our model
compared to the MRF or CRF models, which typically use
graphs with a ﬁxed grid structure. Our model has the ability
to use different graph structures depending on the problem.
6. Conclusion
In this work, we introduced Random Walk Networks
(RWNs), and showed that, compared to traditional fully
convolutional networks (FCNs), they produce improved ac-
curacy for the same model complexity. Our RWN addresses
the issues of 1) poor localization around the segmentation
boundaries and 2) spatially disjoint segmentations. Addi-
tionally, our implementation of RWN uses only 131addi-
tional learnable parameters ( 0:0008% of the original num-
ber of the parameters in the network) and it can be easily
integrated into the standard FCN learning framework for a
joint end-to-end training. Finally, RWN provides a more
efﬁcient alternative to the denseCRF approaches.
Our future work includes experimenting with alterna-
tive RWN architectures and applying RWN to new domains
such as language processing or speech recognition.
References
[1] Pablo Arbelaez, J. Pont-Tuset, Jon Barron, F. Marqués, and
Jitendra Malik. Multiscale combinatorial grouping. In Com-
puter Vision and Pattern Recognition (CVPR) , 2014. 6
[2] Vijay Badrinarayanan, Ankur Handa, and Roberto Cipolla.
Segnet: A deep convolutional encoder-decoder architecture
for robust semantic pixel-wise labelling. arXiv preprint
arXiv:1505.07293 , 2015. 4
[3] Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. Fast
incremental and personalized pagerank. Proc. VLDB En-
dow., 4(3):173–184, December 2010. 2, 3
[4] Gedas Bertasius, Jianbo Shi, and Lorenzo Torresani. Se-
mantic segmentation with boundary neural ﬁelds. In The
IEEE Conference on Computer Vision and Pattern Recog-
nition (CVPR) , June 2016. 2
[5] Liang-Chieh Chen, Jonathan T. Barron, George Papandreou,
Kevin Murphy, and Alan L. Yuille. Semantic image seg-
mentation with task-speciﬁc edge detection using cnns and a
discriminatively trained domain transform. CVPR , 2016. 1,
2, 7
[6] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos,
Kevin Murphy, and Alan L. Yuille. Semantic image segmen-
tation with deep convolutional nets and fully. In ICLR , 2015.
1, 2, 4, 6, 7
[7] Liang-Chieh Chen, Yi Yang, Jiang Wang, Wei Xu, and
Alan L. Yuille. Attention to scale: Scale-aware semantic
image segmentation. CVPR , 2016. 2, 4, 6
[8] Jifeng Dai, Kaiming He, and Jian Sun. Boxsup: Exploiting
bounding boxes to supervise convolutional networks for se-
mantic segmentation. In The IEEE International Conference
on Computer Vision (ICCV) , December 2015. 1
[9] S. Gould, R. Fulton, and D. Koller. Decomposing a scene
into geometric and semantically consistent regions. In Pro-
ceedings of the International Conference on Computer Vi-
sion (ICCV) , 2009. 6, 7
[10] Bharath Hariharan, Pablo Arbelaez, Lubomir Bourdev,
Subhransu Maji, and Jitendra Malik. Semantic contours from
inverse detectors. In International Conference on Computer
Vision (ICCV) , 2011. 6
[11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.
Deep residual learning for image recognition. In The IEEE
Conference on Computer Vision and Pattern Recognition
(CVPR) , June 2016. 4
[12] Seunghoon Hong, Hyeonwoo Noh, and Bohyung Han. De-
coupled deep neural network for semi-supervised semantic
segmentation. In NIPS) , December 2015. 1, 2
[13] Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey
Karayev, Jonathan Long, Ross Girshick, Sergio Guadarrama,
and Trevor Darrell. Caffe: Convolutional architecture for fast
feature embedding. arXiv preprint arXiv:1408.5093 , 2014.
2, 6
[14] Iasonas Kokkinos. Surpassing humans in boundary detection
using deep learning. CoRR , abs/1511.07386, 2015. 2[15] Philipp Krähenbühl and Vladlen Koltun. Efﬁcient inference
in fully connected crfs with gaussian edge potentials. In
J. Shawe-Taylor, R.S. Zemel, P.L. Bartlett, F. Pereira, and
K.Q. Weinberger, editors, Advances in Neural Information
Processing Systems 24 , pages 109–117. Curran Associates,
Inc., 2011. 1, 7
[16] John D. Lafferty, Andrew McCallum, and Fernando C. N.
Pereira. Conditional random ﬁelds: Probabilistic models for
segmenting and labeling sequence data. In Proceedings of
the Eighteenth International Conference on Machine Learn-
ing, ICML ’01, pages 282–289, San Francisco, CA, USA,
2001. Morgan Kaufmann Publishers Inc. 3
[17] Guosheng Lin, Chunhua Shen, Ian D. Reid, and Anton
van den Hengel. Efﬁcient piecewise training of deep
structured models for semantic segmentation. CoRR ,
abs/1504.01013, 2015. 1, 2, 3
[18] Ce Liu, Jenny Yuen, and Antonio Torralba. Nonparametric
Scene Parsing via Label Transfer , pages 207–236. Springer
International Publishing, Cham, 2016. 6, 7
[19] Ziwei Liu, Xiaoxiao Li, Ping Luo, Chen Change Loy, and
Xiaoou Tang. Semantic image segmentation via deep parsing
network. In ICCV , 2015. 1, 2, 3
[20] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully
convolutional networks for semantic segmentation. In The
IEEE Conference on Computer Vision and Pattern Recogni-
tion (CVPR) , June 2015. 1, 2
[21] Laszlo Lovasz. Random walks on graphs: A survey, 1993.
2, 3
[22] D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database
of human segmented natural images and its application to
evaluating segmentation algorithms and measuring ecologi-
cal statistics. In Proc. 8th Int’l Conf. Computer Vision , vol-
ume 2, pages 416–423, July 2001. 7
[23] Hyeonwoo Noh, Seunghoon Hong, and Bohyung Han.
Learning deconvolution network for semantic segmentation.
InComputer Vision (ICCV), 2015 IEEE International Con-
ference on , 2015. 1, 2
[24] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
Winograd. The pagerank citation ranking: Bringing order
to the web. Technical Report 1999-66, Stanford InfoLab,
November 1999. Previous number = SIDL-WP-1999-0120.
2, 3
[25] Xiaojuan Qi, Jianping Shi, Shu Liu, Renjie Liao, and Ji-
aya Jia. Semantic segmentation with object clique potential.
InThe IEEE International Conference on Computer Vision
(ICCV) , December 2015. 2
[26] K. Simonyan and A. Zisserman. Very deep convolu-
tional networks for large-scale image recognition. CoRR ,
abs/1409.1556, 2014. 4
[27] Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-
Paredes, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang
Huang, and Philip Torr. Conditional random ﬁelds as recur-
rent neural networks. In International Conference on Com-
puter Vision (ICCV) , 2015. 1, 2, 3