
\section*{Acknowledgements}




This work was partially supported by the Big Data Collaboration Research grant from SenseTime Group (CUHK Agreement No. TS1610626), the Early Career Scheme (ECS) of Hong Kong (No. 24204215), and the 973 Program under contract No. 2015CB351802.


\section{Conclusion}
We presented an efficient video semantic segmentation framework
with two key components:
adaptive feature propagation and adaptive key-frame schedule.
Particularly, our specially designed schedule scheme can achieve low latency
in an online setting.
The results on both Cityscapes and CamVid showed that
our method can yield a substantially better tradeoff between accuracy
in latency, compared to previous methods.
In future, we will
explore more model compression approaches which can further reduce the overall
computation cost and latency for a practical system.

\section{Experiment}
\label{sec:exper}

We evaluated our framework on two challenging datasets,
Cityscapes~\cite{cordts2016cityscapes} and CamVid~\cite{brostow2009semantic},
and compared it with state-of-the-art approaches.
Our method, with lowest latency, outperforms previous methods significantly.

\subsection{Datasets and Evaluation Metrics}

\emph{Cityscapes}~\cite{cordts2016cityscapes} is set up for urban scene
understanding and autonomous driving. It contains snippets of street scenes
collected from $50$ different cities, at a frame rate of $17$ fps.
The training, validation, and test sets respectively
contain $2975$, $500$, and $1525$ snippets.
Each snippet has $30$ frames, where the $20$-th frame is annotated
with pixel-level ground-truth labels for semantic segmentation with $19$
categories. The segmentation accuracy is measured by the pixel-level
\emph{mean Intersection-over-Union (mIoU)} scores.

\emph{Camvid}~\cite{brostow2009semantic} contains $701$ color images
with annotations of $11$ semantic classes.
These images are extracted from driving videos captured at daytime and dusk.
Each video contains $5000$ frames on average,
with a resolution of $720 \times 960$ pixels.
Totally, there are about $40K$ frames.


\subsection{Evaluation on Cityscapes Dataset}

\input{tab_cityscapes.tex}

We compared our low-latency video semantic segmentation framework with recent
state-of-the-art methods, following their evaluation protocol.
Table~\ref{tab:cityscapes} shows the quantitative comparison.
The baseline is per-frame segmentation with the full ResNet.
Our adaptive feature propagation with fixed-interval schedule
speeds up the pipeline, reducing
the per-frame runtime from $360$ ms to $151$ ms
while decreasing the performance by $4.9\%$.
Using adaptive key frame selection, the performance is boosted by $1.6\%$.
While these schemes reduce the overall runtime, they are not able
to reduce the maximum latency, due to the heavy computation on key frames.
The low-latency scheduler effectively tackles this issue, which
substantially decreases the latency to $119$ ms (about $1/3$ of the baseline
latency) while maintaining a comparable performance (with just a minor drop).

From the results, we also see that other methods proposed recently
fall short in certain aspects.
In particular, Clockwork Net~\cite{shelhamer2016clockwork} has the same latency, but at the cost of significantly
dropped performance.
DFF~\cite{zhu2017deep} maintains a better performance, but at the expense
of considerably increased computing cost and dramatically larger latency.
Our final result, with low latency schedule for video segmentation, outperforms
previous methods by a large margin. This validates the effectiveness of
our entire design.

In addition to the quantitative comparison, we also shows some visual results in
Fig.~\ref{fig:cityscapes_show}. Our method can successfully learn the video
segmentation even when the frames vary significantly. In what follows, we
will investigate the design for each module respectively.


\begin{table}[tbp]
\begin{center}
\begin{tabular}{c|ccc}
\hline
Method & mIOU \\
\hline
Clockwork Propagation~\cite{shelhamer2016clockwork} & 56.53\% \\
Optical Flow Propagation~\cite{zhu2017deep} & 69.2\%\\
\hline
Unified Propagation &	58.73\% \\
Weight By Image Difference &	60.12\% \\
Adaptive Propagation Module (no fuse) &	68.41\% \\
Adaptive Propagation Module (with fuse) &	\textbf{75.26\%} \\
\hline
\end{tabular}
\vspace{0.1cm}
\caption{\small
    Comparison of different feature propagation modules.
}
\label{tab:propagation_fixed}
\end{center}
\end{table}

\begin{figure}[t]
\centering
\includegraphics[width=0.9\linewidth]{update_ratio_iou.pdf}%
 \caption{\small
    Comparison of different scheduling schemes.
 }
 \label{schedule_result}
\end{figure}






\vspace{-7pt}
\paragraph{Comparison on Feature Propagation}

We begin by evaluating the effectiveness of our proposed adaptive propagation
module. To evaluate the specific performance gain on this module, we fix the
scheduling scheme as previous methods, namely selecting a key-frame per $5$
frames.

Table~\ref{tab:propagation_fixed} shows the quantitative comparison.
We compared our method with a globally learned unified propagation, for which the
result is not satisfactory. It reveals that the spatially variant weight is
quite important in our solution.
We also compared to a baseline, where the weights are directly set by
the differences of the input pixel values, our learned propagation weights
also perform better.
Our experiment also shows that the fuse with the low-level features
from the current frame by \emph{AdaptNet} achieves significant
performance improvements (from $68.41\%$ to $75.26\%$), which may be ascribed
to the strong complementary information learned by the fuse model.

Compared to recently proposed methods for feature propagation,
our adaptive propagation module still performs significantly better.
Particularly, Clockwork directly replaces parts of the current features with
previous ones, and therefore the derived representation is not adapted to
current changes, thus resulting in poor performance.
The optical flow based method DFF~\cite{zhu2017deep} relies on the optical
flows to propagate features and shows substantially better accuracies
as compared to Clockwork, due to its better adaptivity.
Yet, its performance is sensitive to the quality of the Flownet, and
it ignores the spatial relationship on the feature space.
These factors limit its performance gain, and hence it is still inferior
to the proposed method.

\vspace{-7pt}
\paragraph{Comparison on Scheduling}
\label{exp_adaptive_schedule}

We also studied the performance of the adaptive scheduling module for
key frame selection, given our feature propagation module.
Note that a good schedule not only reduces the frequency of key frames,
but also increases the performance given a fixed number of key frames.
Hence, we conducted several experiments to compare different schedule methods
across different key-frame intervals.

Specifically, we compared
fixed rate schedule, threshold schedule, and also our adaptive schedule module.
Fig.~\ref{schedule_result} shows the results.
Under each key-frame interval, our adaptive schedule always outperforms
the other two.
We believe the reason why the proposed method outperforms the
threshold schedule is that the intermediate
feature maps is not specially optimized for key-frame selection.
They may contain noises and perhaps many other irrelevant factors.


\begin{table}[tbp]
\centering

\begin{tabular}{c|ccc}
\hline
Modules & Time (ms) & R \\
\hline
Lower part of network $S_l$  &61 & 16.9\%\\
Higher part of network $S_h$  &299  & 83.1\%\\
Basic Network &360 & 100\% \\
\hline
Adaptive Schedule Module  &20 & 5.5\%\\
Adaptive Propagation Module &38 & 10.5\%\\
\hline
Non-Key Frame &119 & 33\%\\
\hline
\end{tabular}
}
\vspace{0.1cm}
\caption{Latency analysis for each module of our network.
The second column (R) shows the ratio of the latency
to the time spent by the basic network.
}
\label{tab:latency}
\end{table}

\vspace{-7pt}
\paragraph{Cost and Latency Analysis}
We analyzed the computation cost of each component in our pipeline, and
then the overall latency of our method. The results are in Table~\ref{tab:latency}.
With the low-latency scheduling scheme,
the total latency of our pipeline is equal to the sum
of the lower part of the network $S_l$,
adaptive key-frame selection, adaptive feature propagation,
which is $0.119s$ ($33\%$ of the basic network).
On the contrary, all previous methods fail to reduce latency in
their system design, despite that they may reduce the overall cost
in the amortized sense. Hence, they are not able to meet the latency requirements
in real-time applications.





\input{tab_camvid.tex}


\begin{figure*}[ht]
    \centering
    \includegraphics[width=0.96\textwidth]{figures/cityscapes_show_update.pdf}
    \caption{Visual Results for Cityscapes Dataset: our method can achieve significant improvement shown as the red rectangle.}
    \label{fig:cityscapes_show}
\end{figure*}

\begin{figure*}[ht]
    \centering
    \includegraphics[width=0.96\textwidth]{figures/camvid_show_update.pdf}
    \caption{Visual Results for Camvid Dataset: our method can achieve significant improvement shown as the red rectangle.}
    \label{fig:camvid_show} \vspace{-0.3cm}
\end{figure*}


\subsection{CamVid Dataset}

We also evaluated our method on CamVid, another video segmentation dataset,
and compard it with multiple previous methods that have reported performances
on CamVid, which range from traditional methods to various CNN or RNN based methods.
In Table~\ref{tab:camvid},
we report the pixel accuracy and average per-Class Accuracy(CA),
which can reduce the dominated effect on majority classes.
We can see our framework still performs the best.
The consistently good performances on both datasets show that
our adaptive framework for video segmentation method is in general beneficial
to video perception.
Qualitative results on this dataset are shown in Fig.~\ref{fig:camvid_show}.






\section{Video Segmentation Framework}
\label{sec:frmwork}


We develop an efficient framework for
video semantic segmentation.
Our goal is to reduce not only the overall computing cost
but also the maximum latency, while maintaining competitive performance.
Specifically, we adopt the basic paradigm of
the state-of-the-art frameworks~\cite{shelhamer2016clockwork,zhu2017deep},
namely, propagating features from key frames to others by exploiting
the strong correlations between adjacent frames.
But we take a significant step further, overcoming the limitations
of previous work with new solutions to two key problems:
(1) \emph{how to select the key frames} and
(2) \emph{how to propagate features across frames}.



\begin{figure*}
    \centering
   
    \includegraphics[width=0.91\textwidth]{figures/frmwork_scratch_reduce.pdf}
    \caption{\small
        The overall pipeline.
        At each time step $t$, the lower-part of the CNN $S_l$ first computes
        the low-level features $F_l^t$. Based on both $F_l^k$ (the low-level
        features of the previous key frame) and $F_l^t$, the framework will
        decide whether to set $I^t$ as a new key frame. If yes, the high-level
        features $F_h^t$ will be computed based on the expensive higher-part
        $S_h$; otherwise, they will be derived by propagating from $F_h^k$
        using spatially variant convolution. The high-level features,
        obtained in either way, will be used in predicting semantic labels.
    }
    \label{fig:frmwork}
\end{figure*}

\subsection{Framework Overview}
\label{sub:overview}


Previous works usually select key frames based on
fixed intervals~\cite{zhu2017deep} or simple heuristics~\cite{shelhamer2016clockwork},
and propagate features based on optical flows that are costly
to compute~\cite{zhu2017deep} or CNNs with fixed kernels.
Such methods often lack the capability of handling complex variations
in videos, \eg~the changes in camera motion or scene structures.
In this work, we explore a new idea to tackle these problems --
\emph{taking advantage of low-level features}, \ie~those from lower layers of a CNN.
Specifically, low-level features are inexpensive to obtain,
yet they provide rich information about the characteristics of the underlying frames.
Hence, we may select key frames and propagate features more effectively
by exploiting the information contained in the low-level features,
while maintaining a relatively low computing cost.


Figure~\ref{fig:frmwork} shows the overall pipeline of our framework.
Specifically, we use a deep convolutional network
(ResNet-101~\cite{he2015deep} in our implementation) to extract visual features
from frames. We divide the network into two parts, the lower part $S_l$
and the higher-part $S_h$. The low-level features derived from $S_l$
will be used for selecting key frames and controlling how high-level
features are propagated.

At runtime, to initialize the entire procedure, the framework will feed
the first frame $I^0$ through the entire CNN and obtain both
low-level and high-level features.
At a later time step $t$, it performs the computation \emph{adaptively}.
In particular, it first feeds the corresponding frame $I^t$ to $S_l$,
and computes the low-level features $F_l^t$.
Based on $F_l^t$, it decides whether to treat $I^t$ as a new key frame,
depending on how much it deviates from the previous one.
If the decision is \emph{``yes''}, it will continue to feed $F_l^t$ to
$S_h$ to compute the high-level features $F_h^t$,
and then the segmentation map (via pixel-wise classification).
Otherwise, it will feed $F_l^t$ to a \emph{kernel predictor}, obtain a set
of convolution kernels therefrom, and use them to propagate
the high-level features from the previous key frame via spatially variant
convolution.


Note that the combined cost of kernel prediction and spatially variant
convolution is dramatically lower than computing the high-level features
from $F_l^t$ ($38$ ms vs $299$ ms).
With our design, such an
adaptive propagation scheme can maintain reasonably high accuracy
for a certain range ($7$ frames) from a key frame.
Moreover, the process of deciding whether $I^t$ is a key frame is
also cheap ($20$ ms).
Hence, by selecting key frames smartly and propagating features
effectively, we can significantly reduce the overall cost.

\vspace{-0.16cm}
\subsection{Adaptive Selection of Key Frames}
\label{sub:keyframe}



An important step in our pipeline is to decide which frames
are the key frames.
A good strategy is to select key frames more frequently
when the video is experiencing rapid changes, while reducing the
computation when the observed scene is stable. Whereas this has been
mentioned in previous literatures, what dominate the practice are still
fixed-rate schedulers~\cite{zhu2017deep} or those based on simple thresholding of
feature variances~\cite{shelhamer2016clockwork}.


According to the rationale above,
a natural criterion for judging whether a frame should be chosen as a new key frame
is the \emph{deviation} of its segmentation map from that of the previous key frame.
This can be formally defined as the fraction of pixels at which
the semantic labels differ.
Intuitively, a large deviation implies significant changes and
therefore it would be the time to set a new key frame.

However, computing the \emph{deviation} as defined above requires
the segmentation map of the current frame, which is expensive to obtain.
Our approach to this problem is to leverage the low-level
features to \emph{predict} its value.
Specifically, we conducted an empirical study on both Cityscapes and Camvid
datasets, and found that there exists strong correlation between the difference
in low-level features and the deviation values.
Greater differences in the low-level features usually indicate larger deviations.


Motivated by this observation, we devise a small neural network to make
the prediction. Let $k$ and $t$ be the indexes of two frames, this network
takes the differences between their low-level features,
\ie~$(F_l^t - F_l^k)$, as input, and predicts the segmentation deviation,
denoted by $\mathrm{dev}_S(k, t)$.
Specifically, our design of this prediction network comprises
two convolutional kernels with $256$ channels, a global pooling and a fully-connected layer
that follows.
In runtime, at time step $t$, we use this network to predict the
deviation from the previous key frame, after the low-level features are
extracted. As shown in Figure~\ref{fig:selectkey}, we observed that
the predicted deviation would generally increases over time.
If the predicted deviation goes beyond a pre-defined threshold,
we set the current frame as a key frame, and computes its high-level
features with $S_h$, the higher part of the CNN.


\begin{figure}[t]
    \centering
    \includegraphics[width = 1.0\linewidth]{figures/adaptive_schedule.pdf}
    \caption{\small
        Adaptive key frame selection.
        As we proceed further away from the key frame, the predicted deviation
        of the segmentation map, depicted with blue dots, gradually increases.
        In our scheme, when the deviation goes beyond
        a pre-defined threshold, the current frame will be selected
        as a new key frame.
    }
    \label{fig:selectkey}
\end{figure}


\subsection{Adaptive Feature Propagation}
\label{sub:propagate}


As mentioned, for a frame $I^t$ that is not a key frame, its high-level features
will be derived by propagating from the previous key frame,
which we denote by $I^k$.
The question of \emph{how to propagate features effectively and efficiently}
is nontrivial. Existing works often adopt either of the following two approaches.
1) \emph{Follow optical flows}~\cite{zhu2017deep}.
While sounding reasonable, this way has two drawbacks:
(a) The optical flows are expensive to compute.
(b) Point-to-point mapping is often too restrictive.
For high-level feature maps, where each feature actually captures the visual
patterns over a neighborhood instead of a single site, a linear combination
may provide greater latitude to express the propagation more accurately.
2) \emph{Use translation-invariant convolution}~\cite{mahasseni2017budget}.
While convolution is generally less expensive and offers greater flexibility,
using a fixed set of convolution kernels uniformly across the map
is problematic. Different parts of the scene have different motion patterns,
\eg~they may move towards different directions,
therefore they need different weights to propagate.


Motivated by this analysis, we propose to propagate the features
by \emph{spatially variant convolution}, that is, using convolution
to express linear combinations of neighbors, with the kernels varying
across sites. Let the size of the kernels be $H_K \times H_K$,
then the propagation from
the high-level features of the previous key frame ($F_h^k$)
to that of the current frame ($F_h^t$) can be expressed as
{\small
\begin{equation} \label{eq:svconv}
    F_h^t(l, i, j) =
    \sum_{u=-\Delta}^{\Delta} \sum_{v=-\Delta}^{\Delta}
    W^{(k,t)}_{ij}(u, v) \cdot F_h^k(l, i - u, j - v).
\end{equation}
}
Here, $\Delta = \left\lfloor {H_K / 2} \right\rfloor$,
$F_h^t(l, i, j)$ is the feature value at $(i, j)$ of the $l$-th channel
in $F_h^t$,
$W^{(k,t)}_{ij}$ is an $H \times H$ kernel used to compute
the feature at $(i, j)$ when propagating from $F_h^k$ to $F_h^t$.
Note that the kernel values are to assign weights
to different neighbors, which are dependent on the feature location
$(i, j)$ but shared across all channels.


\begin{figure}[t]
    \centering
    \includegraphics[height=250pt]{figures/adaptive_propagation.png}%
    \caption{\small
        Adaptive feature propagation.
        Let $t$ refer to the current frame and $k$ the previous key frame.
        When the low-level features $F_l^t$ are computed,
        the kernel weight predictor will take both $F_l^k$ and $F_l^t$
        as input, and yield a series of convolution kernels, each for
        a different location. Then the high-level features in the previous
        key frame $F_h^k$ will be propagated to the current time step
        via spatially variant convolution using the predicted kernels.
        Finally, the high-level features will be used in pixel-wise label
        prediction.
    }
    \label{propagation}
\end{figure}


There remains a question
-- how to obtain the spatially variant kernels $W_{ij}^{(k,t)}$.
Again, we leverage low-level features to solve the problem.
In particular, we devise a \emph{kernel weight predictor},
which is a small network that takes the low-level features of both
frames, $F_l^k$ and $F_l^t$, as input, and produces the kernels
at all locations altogether.
This network comprises three convolutional layers interlaced with ReLU
layers. The output of the last convolutional layer is of size
$H_K^2 \times H \times W$, where $H \times W$ is the spatial size
of the high-level feature map. This means that it outputs an $H_K^2$-channel
vector at each location, which is then repurposed to be a kernel of size
$H_K \times H_K$ for that location.
This output is then converted to normalized weights via a softmax layer
to ensure that the weights of each kernel sum to one.
With the weights decided on the low-level features, we allow the kernels
to be adapted to not only the locations but also the frame contents,
thus obtaining great expressive power.


To increase the robustness against scene changes, we fuse the low-level
features $F_l^t$ with the propagated high-level feature $F_h^t$
for predicting the labels.
Unlike in original Clockwork Net~\cite{shelhamer2016clockwork},
where low- and high-level features are simply concatenated,
we introduce a low-cost \emph{AdaptNet} to adapt the low-level features
before it is used for prediction.
The \emph{AdaptNet} consists of three convolution layers  and each layer has a small number of channels.
The \emph{AdaptNet} is jointly learned with the weight predictor
in model training. In this way, the framework can learn to exploit the
complementary natures of both components more effectively.


\subsection{Low-Latency Scheduling}
\label{sub:low_latency}


Low latency is very important in many real-world applications,
\eg~surveillance and autonomous driving.
Yet, it has not received much attention in previous works.
While some existing designs~\cite{shelhamer2016clockwork} can reduce the
overall cost in an amortized sense, the maximum latency is not decreased
in this design due to the heavy computation at key frames.

Based on the framework presented above, we devise a new scheduling scheme
that can substantially reduce the maximum latency. The key of our approach
is to introduce a \emph{``fast track''} at key frames.
Specifically, when a frame $I^t$ is decided to be a key frame, this scheme
will compute the segmentation of this frame through the \emph{``fast track''},
\ie~via feature propagation. The high-level features resulted from the
fast track are temporarily treated as the new key frame feature and placed
in the cache.
In the mean time, a \emph{background process} is launched to compute the
more accurate version of $F_h^t$ via the \emph{``slow track''} $S_h$,
\emph{without blocking} the main procedure.
When the computation is done, this version will replace the cached features.

Our experiments show that this design can significantly reduce the maximum
latency (from $360$ ms to $119$ ms), only causing
minor drop in accuracy (from $76.84\%$ to $75.89\%$). Hence, it is a very
effective scheme for real-world applications, especially those
with stringent latency constraints.
Note that the low-latency scheme cannot work in isolation.
This good balance between performance and latency can only be achieved
when the low-latency scheme is working with the adaptive key-frame selection
and the adaptive feature propagation modules presented above.

\section{Implementation Details}
\label{sec:implement}

Our basic network is a ResNet-101~\cite{he2015deep} pretrained on ImageNet.
We choose \texttt{conv4\_3} as the split point between the lower and higher
parts of the network.
The low-level features $F_l^t$ derived from this layer has $1024$ channels.
The lower part consumes about $1/6$ of the total inference time.
In general, the model can achieve higher accuracy
with a heavier low-level part, but at the expense of higher computing cost.
We chose \emph{conv4\_3} as it attains a good tradeoff
between accuracy and speed on the validation sets.

The \emph{adaptive key frame selector} takes the low-level features
of the current frame $F_l^t$ and that of the previous key frame $F_l^k$
as input. This module first reduces the input features
to $256$ channels with a convolution layer with $3 \times 3$ kernels
and then compute their differences, which are subsequently
fed to another convolution layer with
$256$ channels and $3 \times 3$ kernels.
Finally, a global pooling and a fully-connected layer
are used to predict the deviation.

The \emph{kernel weight predictor} in
the \emph{adaptive feature propagation} module (see Fig.~\ref{propagation})
has a similar structure, except that the input features are
concatenated after being reduced to $256$ channels,
the global pooling is removed, and
the fully-connected layer is replaced by a convolution layer with
$1 \times 1$ kernels and $81$ channels.
The \emph{AdaptNet} also reduces the low-level features to $256$ channels by a
convolution layer with $3 \times 3$ kernels, and then pass them to
two two convolution layers with $256$ channels and $3 \times 3$ kernels.
For non-key frames, the adapted low-level features, \ie~the output of the
\emph{AdaptNet} are fused with the propagated high-level features.
The \emph{fusion} process takes the concatenation of both features as input,
and sends it through a convolution layer with $3\times3$ kernels and $256$
channels.

During training, we first trained basic network with respective
ground-truths and fixed it as the feature extractor. Then, we finetuned the adaptive propagation module and the adaptive schedule module, both of which can take a pair of frames
that are $l$ steps apart as input ($l$ is randomly chosen in $[2, 10]$).
Here, we choose the pairs such that
in each pair the first frame is treated as the key frame, and the second
one comes with annotation. For the adaptive propagation module, the kernel predictor and the AdaptNet
are integrated into a network. This integrated network can produce
a segmentation map for the second frame in each pair through
keyframe computation and propagation. This combined network is trained
to minimize the loss between the predicted segmentation (on the second frame
of each pair) and the annotated groundtruth.
For training the adaptive schedule module, we generated the segmentation maps of all unlabelled frames  as auxiliary labels based on the trained basic network and computed the deviation of the segmentation maps between key frame and current frame as the regression target.
The training images were randomly cropped to $713\times713$ pixels. No other data argumentation methods were used.

\section{Introduction}
\label{sec:intro}




Semantic segmentation, a task to divide observed scenes into semantic regions,
has been an active research topic in computer vision.
In recent years, the advances in
deep learning~\cite{krizhevsky2012imagenet,simonyan2014very,he2015deep} and
in particular the development of Fully Convolutional Network (FCN)~\cite{long2015fully}
have brought the performance of this task to a new level.
Yet, many existing methods for semantic segmentation were devised for parsing
images~\cite{long2015fully,chen2014semantic,liu2015semantic,noh2015learning,zhao2016pyramid}.
How to extend the success of segmentation techniques to video-based
applications (\eg~robotics, autonomous driving, and surveillance) remains
a challenging question.


The challenges of video-based semantic segmentation consist in two aspects.
On one hand, videos usually involve significantly larger volume of data
compared to images. Particularly, a video typically contains $15$ to $30$
frames per second. Hence, analyzing videos requires much more computing
resources.
On the other hand, many real-world systems that need video
segmentation, \eg~autonomous driving, have strict requirments
on the \emph{latency} of response, thus making the problem even more challenging.


\begin{figure}[t]
    \centering
    \includegraphics[width = 0.92\linewidth]{figures/latency_accuracy.pdf}
    \caption{\small
        Latency and mIoU performance on Cityscapes~\cite{cordts2016cityscapes} dataset.
        Methods involved are NetWarp~\cite{gadde2017semantic},
        PSPNet~\cite{zhao2016pyramid}, Deeplab~\cite{chen2016deeplab},
        PEARL~\cite{jin2016video}, DFF~\cite{zhu2017deep},
        Clockework~\cite{shelhamer2016clockwork} and Ours.
        Our method achieves the lowest latency while maintaining competitive
        performance.
    }
    \label{fig:latency_acc}
\end{figure}


Previous efforts on video semantic segmentation mainly fall into two classes,
namely \emph{high-level modeling} and \emph{feature-level propagation}.
The former~\cite{fayyaz2016stfcn,nilsson2016semantic} integrates frame-wise analysis via a sequential model. The methods
along this line usually add additional levels on top, and therefore are unable
to reduce the computing cost.
The latter, such as Clockwork Net~\cite{shelhamer2016clockwork} and
Deep Feature Flow~\cite{zhu2017deep}, instead attempts to reuse the features
in preceding frames to accelerate computation.
Such methods were designed to reduce the overall cost in an
\emph{amortized} sense, while neglecting the issue of \emph{latency}.
Moreover, from a technical standpoint, existing methods exploit temporal
correlations by treating all locations \emph{independently} and \emph{uniformly}.
It ignores the different characteristics between smooth regions and boundaries,
and lacks the flexibility of handling complex variations.
Fig.~\ref{fig:latency_acc} compares the performance/latency tradeoffs
of various methods. We can see that previous methods fall short
in either aspect.



Our primary goal in this work is to reduce not only the overall cost but also
the maximum latency, while maintaining competitive performance
in complicated and ever-changing scenarios.
Towards this goal, we explore a new framework.
Here, we adopt the idea of feature sharing, but move beyond the limitations
of previous methods in two important aspects.
(1) We introduce an \emph{adaptive feature propagation} component, which
combines features from preceding frames via
\emph{spatially variant convolution}. By adapting the combination weights
locally, it results in more effective use of previous features and thus
higher segmentation accuracy.
(2) We \emph{adaptively allocate} the keyframes on demand based on
accuracy prediction and incorporate a parallel scheme to coordinate
keyframe computation and feature propagation.
This way not only leads to more efficient use of computational resources
but also reduce the maximum latency.
These components are integrated into a network.



Overall, the contributions of this work lie in three key aspects.
\textbf{(1)} We study the issue of latency, which is often overlooked
in previous work, and present a framework that achieves low-latency
video segmentation.
\textbf{(2)} We introduce two new components: a network using spatially
variant convolution to propagate features adaptively and an adaptive
scheduler to reduce the overall computing cost and ensure low latency.
\textbf{(3)} Experimental results on both Cityscapes and CamVid demonstrate
that our method achieve competitive performance as compared to
the state of the art with remarkably lower latency.

\section{Model Formulation}
\label{sec:model}
Our proposed framework is based on the insight that the content of  adjacent frames over a video move smothly and there representatoins of deep network change slowly corespondingly as showed in~\cite{shelhamer2016clockwork}. So processing video frame by frame is not needed, and the keyframe-based method is proposed to reduce the overall cost in work of Clockwork network~\cite{shelhamer2016clockwork} and
Deep Feature Flow (DFF)~\cite{zhu2016deep}. Naturally, we should ask the question: when is frame selected as the keyframe and can we reduce the overall cost and maintain a low-latency at the same time?

To answer the question, we design a scheduling module to determine the keyframe adaptively and an adaptive feature propagation module to reduce the overall cost. The maximum latency can be reduced by a schedule scheme and improved further by parameters and computation share with both modules and the per-frame prediction network. The time steps of our low-latency pipeline is viewed in Fig~\ref{model_details}. Only at time step $T_1$ both low part and high part of basic network are forwarded to obtain the label and cache the high-level feature, which cause the maxinum latency of the whole video. At next time step, the low part of basic network(figure~\ref{model_details}(a)) is forwarded to provide the low level feature for schedule module(figure~\ref{model_details}(b)) and feature progagation module(figure~\ref{model_details}(c)). Whether high part of basic network is forwarded or not depends on the output of adaptive schedule. When the adaptive schedule outputs $no$, the high part of basic network is not excuted and save the computation cost as showed in $T_2,T_3$. When it ouputs $yes$, the high part of basic network is excuted underlying and the pipeline is not blocked as showed in $T_4$. At the same time, although the frame is labeled as keyframe, the feature propagation module still propagate the high level feature from previous keyframe and its output is just cached to be propagated at the next time steps as showed in $T_5$, thus reducing the maxinum latency.

In what follows, we will start to introduce schedule scheme of our low-latency pipeline to illustrate how the componets work togather to achieve the goal in a global perspective, then explain  the mechanism of all components of schedule scheme: the basic network structure, the adaptive feature propagation module and adaptive schedule module respectively. 





\begin{figure*}[t]
\centering

 \includegraphics[width = 1.0\linewidth]{pipeline}%
 \caption[model compare]{Time steps of our low-latency pipeline. Note some inputs of purple block at each time step is omited, the whole structure of which can be viewed in (c). At time step $T_{1}$, all componets of basic network (a) are ran to obtain label and the output of high part of network($S_{h}$) is cached. At time step $T_{i}(i>1)$, whether $S_h$ is forwarded or not depends on the output of adaptive schedule (b). When $S_h$ is scheduled (showed as $T_4$), its output is cached and will be propagated to future frame at next time steps(showed as $T_5$), otherwise it's not excuted (showed as $T_2,T_3$).} \label{model_details}
\end{figure*}




\subsection{Low Latency Schedule Scheme}
Latency is very important for real-world applications
while it has not received much attention from previous work.
Given  the basic network module(detailed in subsection\ref{subsec:basic_network}), the feature propagation module(detailed in subsection\ref{subsec:feature_prop}) and the adaptive schedule prediction module(detailed in subsection\ref{subsec:schedule_pred}),
we combine them into a late key-frame replacement schedule scheme to reduce latency.





The core of our designed scheduler is that, even if the key frame is detected in frame $t$, we still get temporal high level feature $\hat{\mathcal{F}}_h^t$ from propagation as showed as $T_4$ in Fig.~\ref{model_details}.
So the overall latency is reduced by not blocking by feature forward in heavy high-level network $S_h$.
The accurate high level feature $\mathcal{F}_h^t$ is updated afterwards as key-frame reference for future frame propagation.
Although the low latency propagation will hurt performance to some extent, our adaptive feature propagation and adaptive schedule will compensate the system as a whole. The overall algorithm is illustrated in Algorithm~\ref{alg}. To summarize, such late key-frame replacement schedule pipeline is very effective for real applications.






\begin{algorithm}[t]
\caption{Late Key-Frame Feature Replacement Scheduling}\label{alg}
\begin{algorithmic}[1]
\State Forward $S_l$, $S_h$ and cache key frame feature $\mathcal{F}_l^k$ and $\mathcal{F}_h^k$ at $t=1$ and initilize it as key frame
\For {time $t > 1$} 
\State $\mathcal{F}_l^t \gets$ Forward network $S_l$
\State $\hat{\mathcal{F}}_h^t$ $\gets$ adaptive propagation module
\State Predict final result based on $\hat{\mathcal{F}}_h^t$
\State \textit{is\_keyframe} $\gets$ adaptive schedule module
\If {\textit{is\_keyframe}}
\State $\mathcal{F}_h^t \gets$ Forward $S_h$
\State Label frame $t$ as key frame
\State Cache $\mathcal{F}_l^t$ and $\mathcal{F}_h^t$ as key frame feature
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}








\subsection{Basic Network}
\label{subsec:basic_network}
We use ResNet101~\cite{he2015deep} as our baseline model given its superior performance on semantic segmentation. We divide the network into two parts: $S_l$ and $S_h$, as shown in Figure~\ref{model_details} (a) in separate dash boxes.
Specifically, the lower part of the network, denoted as $S_l$, contains layers from the input to the layer \texttt{conv4\_3}. The higher part of the network, denoted as $S_h$, contains the layers afterwards.

The lower part of the network works as a feature extractor for key frame prediction, adaptive propagation, and as well adaptive scheduling. Generally the computation cost for $S_l$ is much smaller than that of $S_h$.
In practice, we can set a different intermediate layer as the separating point or even increase the number of separating layers based on the trade-off between speed and performance.

During video processing, the lower part of the network $S_l$ is executed at each frame, and its output feature map $\mathcal{F}_l$ is utilized as input to the adaptive propagation module. The adaptive propagation module predicts spatially variant propagation weights based on $\mathcal{F}_l$, which is further utilized to control the
propagation of the higher-layer features $\mathcal{F}_h$ from the key-frame to current frame.
Then the adaptive scheduler determines whether current frame should become the next key-frame based on $\mathcal{F}_l$. The higher layer of the network $S_h$ is only executed when it is labeled as a key frame.


\subsection{Adaptive Feature Propagation}
\label{subsec:feature_prop}

Our feature propagation module as shown in Fig.\ref{propagation} is aimed to propagate
$\mathcal{F}_h^k$, the high-level features of the key frame, to $\mathcal{F}_h^c$,
that of the current frame. As the illustraction in Fig.\ref{propagation} , the high level feature $F_{h}^c(i,j)$ is similar to its neighbors in $\mathcal{F}_h^k$ as shown in red block in Fig.\ref{propagation} . We express this similarity by weighting the feature within its neighbors in $\mathcal{F}_h^k$ into $\mathcal{F}_h^c$. Further, as shown different red blocks in Fig.\ref{propagation} , the feature $F_{h}^c(i,j)$ in different location has its own adaptive weights. We use a small net to predict the adaptive weights which recieve the intermediate lower layer feature $\mathcal{F}_l$ as the input.
We use the intermediate lower layer feature $\mathcal{F}_l$ as the input for weight propagation for three reasons. First, it contains more semantic information than the raw input. Second, the shared computation on $S_l$ reduces the overall computation compared to a complete optical flow net. Moreover, we learn a weighted propagation, instead of a strict point-to-point propagation as optical flow, which introduces more freedom to our system.


\begin{figure}[t]
\centering
 \includegraphics[width = 1\linewidth]{figures/adaptive_propagation}%

 \caption{ Adaptive feature propagation. The high level feature $F_{h}^c(i,j)$ is similar to its neighbors in $\mathcal{F}_h^k$, and different location has different similarity as different red blocks shown. When $\mathcal{F}_h^k$ is propagated to $F_{h}^c$ it should have its own adaptive combination weights, denoted as the heatmap in feature map which is learned
 by a adaptive propagation module.}\label{propagation}
\end{figure}


Our weight propagation module is detailed as in Fig.~\ref{model_details} (c). The high level feature $F_{h}^c(i,j)$ at each location in current frame is obtained by applying the sum of weights in its neighour window of key frame with $H \times H$ size.  Each location has its own propagation weights and the weights are shared cross different channels. The propagation pattern at each location for high level feature is predicted by a fully convolution net. It contains $3$ convolutional layers together with interlaced ReLU layers. The output of the weight propagation module at each location is converted into probability values via a softmax layer,
which is a map of size $H \times H$, representing the $H \times H$ weights to fuse the high-level feature $\mathcal{F}_h$. The example is shown as Fig\ref{propagation} , the heatmap represents the weights and  the brightness value represents the corresponding weight magnitude. We encode the $H \times H$ dimensional feature to channels to adapt to the structure of FCN. In our experiments, we set $H = 9$.
In this way, we can get a different weight combination for different location based on the current observations of low-level features.


After we got the propagation weights, the adaptive propagation can then be formulated as a spatially variant convolution operator. Specifically, given $\mathcal{F}_h$, the high-level feature map for the key frame, the high-level features for the current frame can be computed as
\begin{equation}
F_{h}^c(l,i,j) = W_{ij} \cdot \mathcal{F}_{h}^k(l,i, j)
\end{equation}
where $W_{ij}$ is the output of the weighted propagation module at location $(i, j)$ and shared cross different channel $l$.




The entire propagation works as a spatially variant depth-wise convolution, to apply different weight to different location and each channel shares weights. It is easy for back propagation, and can be trained end-to-end with other modules. Compared to Clockwork Network~\cite{shelhamer2016clockwork}, which directly replaces history features and fuses via subsequent convolution layers, it is more flexible and powerful due to the spatial variability.
Compared to Deep Feature Flow~\cite{zhu2016deep}, it shares the low-level computation, and provides a weighted propagation than point-to-point propagation, which is more robust in feature space.

To increase robustness when scene changes frequently, in addition to the propagated high level feature $\mathcal{F}_h^c$,
we also fuse the output of $\mathcal{F}_l^c$ as in Clockwork Net. Instead of simple concatenation as Clockwork Net, we first apply a AdaptNet to $\mathcal{F}_l^c$, then concatenate the $\mathcal{F}_h^c$, and finally use the fuse module to output the label. The AdaptNet is critial. The low level feature $\mathcal{F}_l^c$ is not suitable to predict semantic label directly and can be further learned by AdaptNet. What's more important, when combined with progapated hight level feature $\mathcal{F}_h^c$ it can learn the complementary information which can't caught by weight propagation due to sudden move. The details of AdaptNet and fuse module follows the section \ref{sec:exper}


\subsection{Adaptive Schedule Prediction}
\label{subsec:schedule_pred}
As illustraction of Fig.\ref{schedule}, a natural video segmentation system should arrange more computation resources to difficult regions or with large temporal change frames, and reduce computation when the video sequence is stable. Although many previous works discussed this issue, none of them actually provided an elegant mechanism to achieve this. Till now, what dominate the practice are still simple fixed-rate schedulers or those based on thresholds of feature map variance.

The key to achieve the adaptive scheduling is a suitable loss to assist learning. We treat this as predicting the accuracy of current frame label based on the low-level feature observations. The accuracy is defined to be the fraction of pixels at which both key-frame and current labels are the same. Intuitively, if the final accuracy is high, it should provide confident patterns even in low level feature.
In our design, such prediction is accomplished by a small network with a few convolution layers.

\begin{figure}[t]
\centering
 \includegraphics[width = 1\linewidth]{figures/adaptive_schedule}%

 \caption{ Adaptive schedule. The labels propagated from key frame have different accuracy among sequences,
 which are shown as the blue dot in the top.
 So it is natural that the frame which varies large from previous frames
 should be denoted as key frame and needs more computation.}\label{schedule}
\end{figure}

We treat the label predicted by a pretrained model as an auxiliary label $l$. By analyizing the relation between $ \mathcal{F}_l$ and lable $l$, we run the pretrained baseline network for each video sequence on both Cityscapes and Camvid dataset, to get the low level feature $ \mathcal{F}_l$ and output semantic label $l$, then compute $\vert \mathcal{F}_l^k - \mathcal{F}_l^t \vert $ and $acc(l^k,l^t)$. We all found that when $\vert \mathcal{F}_l^k - \mathcal{F}_l^t \vert $ is bigger, the value of $acc(l^k,l^t)$ is smaller, which implies that the differences among feature maps $\mathcal{F}_l^k$ have a strong relationship with label stability. During the video sequence, the feature difference is strongly related to the accuracy difference. It can also be validated by the two consecutive frames , which has low feature difference and high accuracy difference.

In particular, the adaptive schedule module takes the difference of $\mathcal{F}_l$ as the input, and after three convolutional layers with 128 channels and a fully connected layers, it regress the accuracy of current frame with full key frame inference. An illustration of this adaptive schedule prediction module is shown in Figure~\ref{model_details} (b).
At inference time, when the prediction for the adaptive schedule module is lower than a threshold, we label it as a key-frame. The thershold is based on the curve of key-frame update ratio and mIou as descripted in section\ref{exp_adaptive_schedule}. We choose the point that attain the best balance between the update ratio and mIOU on validation set, by looking at the curve of update ratio vs. mIOU. Our experiment validate that the threshold of the predicted accuracy is more robust than the threshold of feature difference.










\section{Related Work}
\label{sec:related}



\paragraph{Image Semantic Segmentation}

Semantic segmentation predicts per-pixel semantic labels given the input image.
The Fully Convolutional Network (FCN)~\cite{long2015fully} is a seminal work
on this topic, which replaces fully-connected layers in a
classification network by convolutions to achieve pixel-wise prediction.
Extensions to this formulation mainly follow two directions.
One is to apply
Conditional Random Fields (CRF) or their variants on top of
the CNN models to increase localization
accuracy~\cite{chen2014semantic,liu2015semantic,zheng2015conditional}.
The other direction explores multi-scale architectures to combine
both low-level and high-level
features~\cite{chen2015attention,hariharan2015hypercolumns}.
Various improved designs were proposed in recent years.
Noh \etal~\cite{noh2015learning} proposed to learn a deconvolution network
for segmentation.
Badrinarayanan \etal~\cite{badrinarayanan2015segnet} proposed SegNet,
which adopts an encoder-decoder architecture and leverages max pooling indices
for upsampling.
Paszke \etal~\cite{paszke2016enet} focused on the efficiency and developed ENet,
a highly efficient network for segmentation.
Zhao \etal~\cite{zhao2016pyramid} presented the PSPNet, which
uses pyramid spatial pooling to combine global and local cues.
All these works are purely image-based. Even if applied to videos,
they work on a per-frame basis without considering the temporal relations.


\vspace{-9pt}
\paragraph{Video Semantic Segmentation}

Existing video semantic segmentation methods roughly fall in two categories.
One category is to improve the accuracy by exploiting temporal continuity.
Fayyaz~\etal~\cite{fayyaz2016stfcn} proposed a spatial-temporal LSTM
on per-frame CNN features.
Nilsson and Sminchisescu~\cite{nilsson2016semantic} proposed gated recurrent
units to propagate semantic labels.
Jin~\etal~\cite{jin2016video} proposed to learn discriminative features
by predicting future frames and combine both the predicted results and
current features to parse a frame.
Gadde~\etal~\cite{gadde2017semantic} proposed to combine the features
wrapped from previous frames with flows
and those from the current frame to predict the segmentation.
While these methods improve the segmentation accuracy by exploting
across-frame relations, they are built on per-frame feature computation
and therefore are not able to reduce the computation.

Another category focuses instead on reducing the computing cost.
Clockwork Net~\cite{shelhamer2016clockwork} adapts mutli-stages FCN
and directly reuses the second or third stage features of preceding
frames to save computation.
Whereas the high level features are relatively stable,
such simple replication is not the best practice in general, especially
when signficant changes occur in the scene.
The DFF~\cite{zhu2017deep} propagates the high level feature from the key frame to
current frame by optical flow learned in a flow network~\cite{fischer2015flownet}
and obtains better performance.
Nevertheless, the separate flow network increases the computational
cost; while the per-pixel location transformation by optical flow
may miss the spatial information in the feature field.
For both methods, the key frame selection is crucial to the overall performance.
However, they simply use fixed-interval schedules~\cite{shelhamer2016clockwork,zhu2017deep}
or heuristic thresholding schemes~\cite{shelhamer2016clockwork},
without providing a detailed investigation.
Moreover, while being able to reduce the overall cost, they do not decrease
the maximum latency.



There are also other video segmentation methods but with different settings.
Perazzi~\etal~\cite{perazzi2016benchmark} built a large scale video \emph{object
segmentation} dataset, which concerns about segmenting the foreground objects
and thus are different from our task, parsing the entire scene.
Khoreva~\etal~\cite{khoreva2016learning}
proposed to learn smooth video prediction from static images by combining
the results from previous frames.
Caelles~\etal~\cite{caelles2016one} tackled this problem
in a semi-supervised manner.
Mahasseni~\etal~\cite{mahasseni2017budget} developed
an \emph{offline} method, which relies on a Markov decision process to
select key frames, and propagate the results on key frames to others
via interpolation.
This method needs to traverse the video frames back and forth,
and therefore is not suitable for the online settings discussed in this paper.



