11institutetext: Oregon State University
11email<EMAIL_ADDRESS>
# Space Time Recurrent Memory Network

Hung Nguyen  Chanho Kim  Fuxin Li

###### Abstract

Transformers have recently been popular for learning and inference in the
spatial-temporal domain. However, their performance relies on storing and
applying attention to the feature tensor of each frame in video. Hence, their
space and time complexity increase linearly as the length of video grows,
which could be very costly for long videos. We propose a novel visual memory
network architecture for the learning and inference problem in the spatial-
temporal domain. We maintain a fixed set of memory slots in our memory network
and propose an algorithm based on Gumbel-Softmax to learn an adaptive strategy
to update this memory. Finally, this architecture is benchmarked on the video
object segmentation (VOS) and video prediction problems. We demonstrate that
our memory architecture achieves state-of-the-art results, outperforming
transformer-based methods on VOS and other recent methods on video prediction
while maintaining constant memory capacity independent of the sequence length.

###### Keywords:

memory network, transformer, video object segmentation, vos, video prediction

##  1 Introduction

Network architectures for spatial-temporal reasoning are of fundamental
importance to computer vision systems. Most real-life reasoning problems are
presented in space-time, including but not limited to autonomous driving,
video object segmentation, navigation, planning, etc. A great earlier example
of a spatial-temporal reasoning model is the convolutional LSTM [40] in which
a convolutional network generates a spatially indexed memory tensor and
recurrently updates the memory tensor over time as the network processes more
input frames.

There are two main benefits to the recurrent memory model. First, it is
online, meaning that the system can generate appropriate output at any given
time of the sequence. The system would do so by taking into account the memory
which has evolved through all the previous frames, hence potentially taking
into account long-term information. Second, the memory size is constant, as
the memory is updated at each time with the new information from each frame.
Such properties make the recurrent memory model ideal for embodied systems
that require real-time processing.

However, one drawback of the convolutional LSTM or other similar approaches is
that the memory may confuse itself over multi-modality. Since there is only
one feature tensor stored as memory, the system often has to face a dilemma
when two equally valuable templates exist: they have to either only remember
one of them or somehow combine them into one template. However, the
combination may become more ambiguous and lead to reduced performance when
many diverse templates need to be remembered. Another drawback of such
approaches is that they do not handle object motion well when strong
information about moving objects in the scene. Although the memory could be
indexed spatially, such indexing is rigid. As a result, when the object moves
in space, the stored memory at the indexed location may not be accurate
anymore.

More recently, spatio-temporal transformers (STM) [32] were proposed as a
different approach for spatio-temporal reasoning. Motivated by transformers in
natural language processing, each of previous frames forms two spatially-
indexed feature tensors called the query and the key in STM. Then, a new frame
is also converted to the query and key tensors, which are used to match with
the previous frames to compute attention weights. These weights are used in a
weighted sum of the spatially-indexed value tensors of the previous frames.
STM has achieved state-of-the-art performance in Video Object Segmentation
(VOS) which is one of the most important and difficult spatio-temporal
reasoning problems. However, similarly with most transformer approaches, STM
needs to compute and store tensors for each frame, leading to significantly
increased time and memory cost for long videos. The walkaround in [32] and
many subsequent work [56, 6] was to store one set of memory tensors for every
5th frame, but this would not extend easily to videos with thousands of
frames.

Figure 1: The overview of our framework. We evaluate our framework on VOS and
video prediction. Our framework consists of two stages. 1) Memory Update: In
this stage, the memory encoder generates a new feature map $X_{t}$ by taking
the current frame and its corresponding object masks as input in the case of
VOS (taking 3 consecutive frames as input in the case of video prediction).
This feature map is then used to update the memory (Sec. 3.2). 2) Inference
stage: The query encoder generates a feature map $X_{t+1}^{q}$ by taking the
query image as input in the case of VOS (taking three consecutive query frames
as input in the case of video prediction). The space-time memory read module
takes the feature map and current memory as input and retrieves information
relevant to the target task as another feature map (Sec. 3.3). This output
feature map from the memory read module is finally decoded into our predicted
mask (or the next frame in the case of video prediction) which will be then
used to update the memory again. (Best viewed in color)

In this paper, we propose a novel memory network, the Space-Time Recurrent
Memory Network (STReMN, pronounced as “strem”) which attempts to retain a
constant-sized memory while enabling online processing for spatio-temporal
reasoning problems. Our network maintains a memory with a fixed number of
separate memory slots which are updated through time (Fig. 1). Our main
novelty is an algorithm based on Gumbel-Softmax that learns the memory update
strategy based on the new input information and current memory slots. This
strategy helps us locate the memory slot that will be discarded automatically
and maintain constant memory with minimal loss of information. This kind of
memory structure has more potential to scale up to long videos beyond a few
seconds. In this paper, we apply it to practical tasks such as VOS and video
prediction. We believe that it can also be applicable to many spatio-temporal
reasoning problems.

Our contributions can be summarized as follows:

  * •

We introduce a novel space-time memory network which has a constant number of
slots. The proposed memory network can handle a long sequence of images
efficiently without increasing the size of the memory when the length of the
image sequence grows.

  * •

We propose a novel memory update module which can be trained to select one of
the memory slots for deletion and update it with the new information in the
new input frame after deletion. We show that the learned update module
outperforms other hand-engineered memory update rules.

  * •

We evaluate the proposed memory model on two important spatio-temporal
reasoning tasks: VOS and video prediction. We obtain state-of-the-art
performance with the proposed memory model, outperforming recent transformer-
based models on the VOS task as well as other recent methods on the video
prediction task.

##  2 Related Work

Implicit Memory. Long short-term memory (LSTM) [14] improves over vanilla
recurrent networks (RNN) by allowing the cell state (memory) to stay constant
if there is no additional input. It also includes input and forget gates which
allow information to be filtered before being used to update the memory. These
gates are usually implemented with fully connected layers and hence cannot be
applied to spatial-temporal sequences. [40] replace the linear layers with
convolutional layers instead hence generating spatially-indexed memory that
can be used for spatio-temporal inference. PredRNN [50] modifies RNN by
allowing the memory state to flow vertically through stacked RNN layers and
horizontally through time. Causal LSTM [48] improves upon PredRNN by proposing
the Highway Unit allowing the gradient to flow quickly to long-range input.
E3D-LSTM [49] uses 3d conv and attention module to improve the RNN. MIM [51]
models the stationary and non-stationary properties in the spatial-temporal
dynamics by exploiting differential signal between adjacent recurrent states.
However, most of these architectures only have a single memory vector/tensor
which struggles to capture multiple appearances of objects in video reasoning
problems [22].

Explicit Memory. Neural Turing Machine (NTM) [10] extended the traditional RNN
with an external memory. NTM architecture includes a controller and a memory
bank. These two components interact with each other through multiple read and
write heads similar to the attention model in transformers. The controller
receives information, interacts with the memory through read and write heads
to retrieve related information, remove old information, and save new ones if
useful. Based on the retrieved information, a corresponding response is
returned. However, it is non-trivial to scale NTM’s memory for visual tasks
which require spatial information.

Space Time Memory (STM) and other variants. STM [32] is a network based on the
transformer idea that utilizes an convolutional encoder to encode the features
of each frame to 2 tensors, key and value. In the reading stage, STM matches
the query frame and template frames at potentially different spatial
locations. The computed attention score are then used for a weighted sum of
the features from each frame. STM does not update existing memory slots and
simply concatenates the feature tensors of each new frame. One advantage of
this simple mechanism is that the information on each template is not
contaminated by other ones. However, it is potentially time and memory
consuming since old templates are never removed and the memory grows linearly
w.r.t. the number of frames. To reduce the time/memory costs, STM uses a
simple heuristic to add a new template every 5 frames, but its time/memory
consumption can still be a significant issue in longer sequences. STCN [6]
improves STM by proposing a more efficient feature extractor and a change to
the attention mechanism (i.e. using the L2 similarity instead of cosine
similarity). However, the memory problem still persists in STCN.

Transformer with Efficient Memory for VOS. GC [27] compresses the memory of
STM by constructing a global memory by averaging the memory of past frames and
rearranging the order of the attention operation. While GC maintains a
constant-size memory like our method, its performance on VOS is not as strong
as the original STM’s performance possibly due to the use of simple average
operation. PAM [47] also introduces a compact memory representation for the
STM framework. Memory updates are performed only when significant changes
between frames exist to avoid updating the memory with redundant information.
Also, instead of performing memory updates with full images, pixel-wise memory
updates are utilized in order to store only relevant information to the target
object in the memory. Although PAM builds more efficient memory
representations than STM does, its memory size still increases over time as
there is no deletion operation. In contrast to PAM, our method maintains a
fixed-size memory regardless of the video length, while still achieving
competitive performance.

Transformer with Efficient Memory for Other Tasks. Other transformer variants
with efficient memory have been proposed for NLP and other vision tasks. [9]
improves upon the transformer network by storing previous hidden states in a
fixed-size queue. The queue helps the model to trade-off the context length
for the memory size. [35] trade-offs the granularity of the memory for the
context length by compressing multiple hidden states before adding them to the
memory. Therefore, the queue can keep more information, given the same size
queue as in [9]. [24] augments the transformer model with a recurrent memory
which utilizes a fixed number of memory slots. The proposed memory is similar
to ours in the sense that it also adopts the recurrent architecture with the
fixed number of memory slots. However, their target task is video captioning,
so the memory is not spatially indexed. Note that spatially-indexed memory
models are significantly larger hence one cannot afford to fully-connect the
memory and learn all the updates which means network design becomes more
important. [3] proposes an efficient video transformer model that utilizes
local space-time attention with a fixed-size temporal window and demonstrates
that the proposed model is much more efficient than a video transformer that
utilizes full space-time attention, while still being effective at capturing
long-term dependencies for the video classification task. Our work is
different from this work in the sense that we model long-term information by
maintaining and updating the fixed-size memory over time rather than modeling
it through multiple local space-time attention operations.

##  3 Methods

###  3.1 Overview

Our framework includes a Query Encoder ($QE$), a Memory Encoder ($ME$), a
Decoder ($D$), and a fixed-size memory
$Mem=\\{X^{M}_{1},X^{M}_{2},\dots,X^{M}_{K}\\}$ as shown in Fig. 1. $QE$ takes
the query image $I_{t}$ as input and outputs the query feature map
$X^{q}_{t}$. $QE$ can also serve as $ME$ if $ME$ does not take any additional
data as input. In many VOS algorithms (but not all), $ME$ also takes an object
mask $M_{t}$ as input in addition to the image, so a separate network should
be set for $ME$. In this case, $ME$ takes $(I_{t},M_{t})$ as input and
produces a spatially-indexed feature tensor $X^{M}_{t}$. Both $QE$ and $ME$
are implemented using convolutional neural networks (CNN). The new memory
feature $X^{M}_{t}$ at each step is fed into the memory update process (Sec.
3.2). To generate the output at step $t+1$, the query feature $X^{q}_{t+1}$ is
matched with the memory using attention-based operation described in Sec. 3.3.
The readout feature map is decoded to desired output using a Decoder
implemented with upsampling CNN layers similar to U-Net[37]. The following
subsections describe our memory update and inference process in detail.

Figure 2: Proposed memory update module

###  3.2 Memory Update Process

Let $K$ and $n$ be the maximum number and the current number of slots in the
memory. If $n<K$, new templates are simply added to the memory. If $n=K$, then
a template must be removed from one of the memory slots to create an empty
slot for the new template. One way to select a slot is to use a rule-based
approach. However, there are many different rules that one can choose, so
figuring out the best rule is not trivial, and the best rule may also be
dependent on the task. In this work, instead of relying on hand-engineered
rules, we propose to learn the selection operation via attention. The
attention weights over memory slots are generated by a network that takes the
new input frame and the current memory as input (Fig. 2). By learning the
selection operation, we remove the need for manually finding the best rules
for different tasks and instead let the network to come up with the best one
during training.

We obtain attention weights over memory slots as follows. Given the new
template $X^{q}_{t}$ (i.e., query feature map) and stored templates
$X^{M}_{1},X^{M}_{2},\dots,X^{M}_{K}$ in the memory, we learn convolutional
layers to convert the query feature map $X^{Q}_{t}$ into a new update key map
$U^{Q}_{t}$ and convert the memory feature maps $X^{M}$ into the new update
key maps $U^{M}$ respectively. We then compute the similarity score between
$U^{Q}_{t}$ and each of $U^{M}_{1},U^{M}_{2},\dots,U^{M}_{K}$ by using the
following similarity function:

$s_{i}=S(U^{Q}_{t},U^{M}_{i})=\frac{1}{HW}\sum_{p}\max_{q}\frac{U^{Q}_{t}(p)\cdot
U^{M}_{i}(q)}{||U^{Q}_{t}(p)||||U^{M}_{i}(q)||}$ (1)

where $s_{i}$ is the similarity score between the stored template in the $i$th
memory slot and the new template, and $U_{i}(p)$ is the update key map of the
$i$-th slot at the spatial location $p$. Note that this similarity function
offers maximal flexibility in terms of matching, allowing pixels from anywhere
in the images to match with each other. Such flexibility is necessary when the
object is stored at different locations in different templates due to the
motion and deformation of the object. Because of the encoding step, feature
maps such as $U^{Q}$ and $U_{i}^{M}$ would have already encoded local shape
and texture information, so each pixel of such feature maps is likely to
represent a part of the object. Hence, intuitively, Eq. (1) allows deformable
matching over different parts of the object.

Once we compute all the similarity scores $s_{1},s_{2},\dots,s_{K}$ for $K$
templates in the memory, we obtain the attention vector by using Gumbel
Softmax [19]:

$\mathbf{a}^{soft}=[a^{soft}_{1},a^{soft}_{2},\dots,a^{soft}_{K}]=\text{Gumbel-
Softmax}([s_{1},s_{2},\dots,s_{K}])$ (2)
$a^{soft}_{i}=\frac{exp((s_{i}+g_{i})/\tau)}{\Sigma_{j=1}^{K}exp((s_{j}+g_{j})/\tau)}$
(3)

where $g_{1}...g_{k}$ are iid sampled from the Gumbel(0,1) distribution, and
$\tau$ is a hyperparameter which is set to $1$ in our experiments. We utilize
Straight-Through Gumbel-Softmax [19] which converts $\mathbf{a}^{soft}$ to a
one-hot vector $\mathbf{a}^{hard}$ with the argmax function in the forward
pass and still allows gradients to be computed by using $\mathbf{a}^{soft}$ in
the backward pass. Note that the update key feature maps are learned, which
allows the network to avoid always selecting a slot that stores the most
similar appearance to that of the input feature map $X^{q}_{t}$ for deletion.
Once we obtain the hard attention vector $\mathbf{a}^{hard}$, we update each
memory slot as follows:

$X^{M}_{i}=(1-a^{hard}_{i})X^{M}_{i}+a^{hard}_{i}X^{q}_{t}.$ (4)

Since $\mathbf{a}^{hard}$ is a one-hot vector in the forward pass, Eq. (4)
allows us to remove the template in the selected slot completely and add the
new template to the slot.

Note that our update process is different from the memory update processes in
other memory networks such as the Gated Recurrent Units (GRU) [8] or Neural
Turing Machines (NTM) [10] in two ways. First, in both GRU and NTM, soft
attention weights are used to mix the information of the current input with
the information of the memory during the memory update. Second, these
approaches selectively take the information in the current input by using the
attention weights defined over the input. In contrast, we dedicate a new
memory slot for the input $X_{t}$ as shown in Eq. (4). An intuition for this
choice is that the new information is fresh and might be the most relevant to
instant predictions. Also, in our framework, it is much easier to understand
what kind of information that the model keeps in the memory because our memory
stores the selected frames in the memory rather than fusing all the
information across the frames into the memory.

As for the information fusion across the frames, we have actually implemented
a fusion module in which the template selected for deletion is fused to other
templates in the memory before its deletion. However, in our experiments, the
model with the fusion module did not outperform the model without the fusion
module. Please refer to the supplementary document for more details about the
fusion module we implemented and the results we obtained.

###  3.3 Inference Stage

In the inference stage, the query frames go through the Query Encoder to be
encoded into a feature map and converted into a key-value pair ($k^{Q}$,
$v^{Q}$). Similarly, each template in the memory is converted into a key-value
pair, and all templates are concatenated to form ($k^{M}$, $v^{M}$). $k^{Q}$
and $v^{Q}$ contain information from the query frame, and $k^{M}$ and $v^{M}$
carry information of the past frames that are currently stored in the memory.
Then each pixel $i$ of the query template is densely matched with every pixel
$j$ of memory’s templates through the attention mechanism similar to [32]:

$y_{i}=\left[\frac{1}{\Sigma_{j}\exp(k_{i}^{Q\top}k^{M}_{j})}\exp(k_{i}^{Q\top}k^{M}_{j})v^{M}_{j},v^{Q}_{i}\right]$
(5)

where $1\leq i\leq HW$, $1\leq j\leq KHW$, and $[\cdot,\cdot]$ is the
concatenation. y is then decoded into the output with a standard U-Net decoder
without highway connections. Note that the decoder receive information from
the encoder only through the memory, which reduced storage costs during both
the training and inference times.

##  4 Experiments

We conduct experiments on two difficult video tasks, video object segmentation
and video prediction. They are described in the subsequent subsections.

###  4.1 Video object segmentation

The VOS problem is chosen as a benchmark because of following reasons. First,
VOS requires both long and short term memory to segment the objects
efficiently. Second, the variation of appearance of the object throughout the
video is significant, which requires the network to keep a diverse memory.
Finally, the segmentation task requires the network to preserve a huge number
of spatial details, which is a challenging task for memory networks and a
spatially-indexed memory is necessary.

####  4.1.1 Implementation Details

The architectures of the encoder and decoder are the same as those of [32].
However, we replace batch normalization [17] with group normalization [52] in
our backbone - Resnet 50 [13]. This makes the training more stable because of
the small batch size that we use due to memory constraints. The network uses 6
memory blocks including: 1 block for the ground truth (1st frame), 1 block for
the latest frame, and 4 blocks for intermediate frames. Post-processing is
also employed to remove some false positive predictions that are far away from
the object in the previous frame. Please refer to the supplementary document
to see the details of our post-processing.

Training. The model is trained in two stages: pre-training with images and
fine-tuning with videos. In the pre-training stage, consistent with prior work
[32], we create short clips consisting 5 frames by using images from COCO
[28], ECSSD [54], SBD [12], MSRA10k [7], and HKUIS [25]. We minimize the cross
entropy loss using the Adam optimizer [23] with learning rate $10^{-4}$. In
the fine-tuning stage, we randomly extract video clips consisting of 10 frames
from videos in the DAVIS and Youtube training set. We fine-tune the model with
the Adam optimizer with the cosine learning rate scheme between
$[10^{-5},10^{-7}]$. We use $384\times 384$ as the input image resolution in
both stages.

####  4.1.2 Ablation Experiments.

We first compare our learned memory update module with rule-based memory
update modules. We implement the following memory update rules as our
baselines.

  * •

A: Remove the oldest template in the memory (queue).

  * •

B: Remove the newest template in the memory (stack).

  * •

C: Drop one of the templates in the memory randomly.

  * •

D: Select $K$ frames randomly among all the previous frames and store the
corresponding templates in the memory.

  * •

E: Keep only the first and the most recent frame in the memory.

  * •

F: Remove the template that stores the most similar appearance to that of the
newest template.

Table 1 shows the results of our ablation experiments. The proposed model
outperforms other baselines that are implemented with the rule-based memory
update modules. This shows that the network can learn what to keep in the
memory effectively when the number of memory slots is limited.

Table 1: Results on DAVIS test-dev with different memory update strategies. Memory models | J | F | Mean
---|---|---|---
(A) Remove oldest | 73.3 | 80.0 | 76.7
(B) Remove newest | 72.9 | 79.2 | 76.0
(C) Random drop | 72.4 | 78.7 | 75.5
(D) Random select | 73.7 | 80.1 | 76.9
(E) Keep the first and last frame | 71.5 | 78.8 | 75.2
(F) Drop the most similar template | 73.5 | 80.2 | 76.9
(Ours) Learned | 74.8 | 81.8 | 78.3

We also report the model performance with different numbers of memory slots.
As shown in Table 2, increasing the number of the slots leads to better
performance in general. For the VOS task, we achieve the best performance with
6 slots.

Table 2: Results on DAVIS test-dev with different number of memory slots. Num slots | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---
J&F | 76.3 | 76.9 | 77.8 | 78.3 | 77.3

####  4.1.3 Results on the DAVIS 2017 and Youtube 2018 Dataset.

Table 3: Results on the DAVIS 2017 dataset while fine-tuning on both DAVIS and
Youtube.

|  |  | Validation | Test-dev
---|---|---|---|---
Method | Backbone | Memory size | J | F | Avg | J | F | Avg
STM [32] | Resnet 50 | linear growth | 79.2 | 84.3 | 81.8 | 69.3 | 75.2 | 72.2
STM [32] | Resnet 50 | constant | 77.7 | - | - | - | - | -
KMN [39] | Resnet 50 | linear growth | 80.0 | 85.6 | 82.8 | 74.1 | 80.3 | 77.2
EGM [30] | Resnet 50 | linear growth | 80.2 | 85.2 | 82.8 | - | - | -
CFBI [55] | Resnet 101 | N/A | 79.1 | 84.6 | 81.9 | 71.1 | 78.5 | 74.8
SwiftNet [47] | Resnet 50 | linear | 78.3 | 83.9 | 81.1 | - | - | -
A-Game [21] | Resnet 101 | N/A | 67.2 | 72.7 | 70 | - | - | -
FEELVOS [45] | DeepLab v3 | N/A | 69.1 | 74.0 | 71.5 | 55.1 | 60.4 | 57.8
PAM [47] | Resnet 50 | linear growth | 78.3 | 83.9 | 81.1 | - | - | -
RMNet [53] | Resnet 50 | linear growth | 81.0 | 86.0 | 83.5 | 71.9 | 78.1 | 75.0
LCM [15] | Resnet 50 | linear growth | 80.5 | 86.5 | 83.5 | 74.4 | 81.8 | 78.1
STCN [6] | Resnet 50 | linear growth | 82.2 | 88.6 | 85.4 | 73.1 | 80.0 | 76.5
STReMN | Resnet 50 | constant | 81.3 | 86.1 | 83.7 | 74.8 | 81.8 | 78.3
STReMN-MS | Resnet 50 | constant | 83.4 | 88.2 | 85.8 | 75.6 | 82.7 | 79.1

Table 4: Results on Youtube VOS 2018 validation set. R50/101: use resnet
50/101 as backbone.

Methods | Seen | Unseen |
---|---|---|---
| J | F | J | F | Avg
GC (R50) [27] | 72.6 | 75.6 | 68.9 | 75.7 | 73.2
EGM(R50) [30] | 80.7 | 85.1 | 74.0 | 80.9 | 80.2
CFBI(R101) [55] | 81.1 | 85.8 | 75.3 | 83.4 | 81.4
PReMVOS(R101) [31] | 71.4 | 75.9 | 56.5 | 63.7 | 66.9
A-Game(R101) [21] | 67.8 | - | 60.8 | - | 66.1
KMN (R50) [39] | 81.4 | 85.6 | 72.8 | 84.2 | 80.9
STM(R50) [32] | 79.7 | 84.2 | 72.8 | 80.9 | 79.4
LCM(R50) [15] | 82.2 | 86.7 | 75.7 | 83.4 | 82.0
PAM(R50) [47] | 77.8 | 81.8 | 72.3 | 79.5 | 77.8
RMNet(R50) [53] | 82.1 | 85.7 | 75.7 | 82.4 | 81.5
STCN(R50) [6] | 81.9 | 86.5 | 77.9 | 85.7 | 83.0
STReMN (R50) | 79.6 | 83.8 | 76.1 | 84.1 | 80.9
STReMN-MS (R50) | 80.7 | 85.0 | 77.6 | 85.5 | 82.2

DAVIS 2017 includes 60 videos, 30 videos, and 30 videos in the training,
validation, and test-dev sets respectively. The objects range from common
classes such as human or dog to rare classes such as string, car wheel, and
drone. The number of frames in each video can be up to 130 frames. Youtube
2018 includes 3471 training videos with dense object annotations at 6 fps and
474 validation videos which comprise of both seen and unseen object categories
in the training set. The length of each video can be up to 180 frames. The
methods are evaluated using the mean region similarity J and the mean contour
accuracy F [34].

Note that we only compare our method with other methods that are trained on
the training set and tested on the validation and testing sets. The online
fine-tuning methods [33][4][46][2][1][26][16][36], which fine-tune the models
on each testing video separately, are not general memory models and hence
orthogonal to our work. We also exclude the AOT approach [56] in our
comparison as their contributions are in utilizing local attention which
allows the model to better focus on the foreground regions and combining
multiple single object predictions efficiently, which is orthogonal to our
contributions of designing constant-size memory. Since our method is general,
it can be plugged into other methods such as [56] in order to address the
memory size issue for long videos.

We present two versions of STReMN. We implement STReMN with the STM backbone
and our proposed memory mechanism. We also use the Atrous Spatial Pyramid
Pooling (ASPP) layer [5] on top of the memory-decoded feature map. We
implement STReMN-MS with the multiscale testing from CFBI [55]. Table 3 shows
our results on the DAVIS 2017 validation and test-dev sets, when fine-tuned on
both the DAVIS and the YouTube datasets. As shown in Table 3, STReMN matches
the performance of all the linear-size memory models on the validation set and
is better than several other networks with larger backbone and memory. STReMN-
MS achieves SOTA performance on both the DAVIS validation and test-dev set.

Table 4 shows our result on the Youtube 2018 validation set. With marginal
performance difference to the best performing one, STCN, our best model ranks
second both on average and on objects unseen during the training. We believe
that our performance on this dataset is still very competitive compared to
that of STCN, considering our method utilizes constant-size memory rather than
linear-size memory used in STCN.

####  4.1.4 Qualitative Results.

In Fig. 3, we show some qualitative results on the DAVIS 2017 dataset. The
results show that our model is able to capture a variety of object poses,
maintain long-term memory after partial occlusion, and adapt well to most of
the appearance changes. However, our model still fails to retrieve extremely
small objects such as the phones held by the pink girl in some frames.
Besides, on the camel video, the model can ignore most but not completely the
second camel. This suggests that the model could not completely grasp the
concept of a single object. Other potential solutions are adding more global
context by using self attention or designing a better decoder to remove these
background noises. More visual examples are discussed in the supplementary
material.

Figure 3: Qualitative results (Best viewed in color).

###  4.2 Video prediction

Another task we chose to benchmark our approach is video prediction. In this
task, the model needs to predict $N$ frames in the future given the first $M$
observed frames. Therefore, this task requires the memory to preserve both the
spatial information (e.g. object appearance and background texture) and the
temporal information (e.g. motion pattern).

Implementation details. As no ground truth segmentation mask is available, we
use the same encoder for both the query and the memory. The input at step $t$
is the stack of 3 consecutive video frames $(I_{t-3},I_{t-2},I_{t-1})$. The
stacked video frames allows the memory to keep both appearance and motion
patterns. The encoder is implemented with 6 CNN blocks. Each block consists of
2 CNN layers followed by group normalization and Leaky RELU. The decoder
includes 6 deconvolution blocks. Each block has 2 deconvolution layers
followed by group normalization and leaky RELU. The memory module is the same
as in the model for VOS and includes 5 slots.

Training. For a fair comparison, our model is not pretrained on other
datasets. The model is trained using Adam optimizer with learning rate set to
$10^{-3}$ to minimize the shrinkage loss [29] on $L_{1}$ and $L_{2}$ and the
scale invariant gradient loss [43]. The final model is obtained by averaging
model weight on different timesteps having high SSIM scores.

Human3.6M [18]: The Human3.6M dataset captures complex motion from general
human actions. We follow [11] to use the walking videos with scene S1, S5, S6,
S7, and S8 for training and S9 and S11 for testing. Each video is resized to
$128\times 128$. In both training and testing, the model predicts 4 frames in
the future given the first 4 observed frames. Our approach outperforms other
memory models by a significant margin on 3 different metrics mean squared
error (MSE), mean average error (MAE), and SSIM as shown in Table 5.
Structural similarity index measure (SSIM) is a perceptual-based metric.
Higher SSIM shows that our model can produce frames with better structural
contents.

KTH [38]: This dataset has 25 people performing 6 types of action on 4
different scenes. The first 16 people are for training and the rest for
testing. The videos are resized to $128\times 128$. In training, the model is
provided with the first 10 frames of the video and trained to predict the next
20 frames. We achieve comparable results with PredRNN on PSNR based on MSE and
SSIM (i.e. structure similarity) while outperforming it on LPIPS which
measures the perceptual similarity based on the features extracted from pre-
trained AlexNet. Therefore, LPIPS measures the human perception on the
generated frames better than the previous 2 metrics as shown in [57].

We show that our model can predict perceptually reasonable feature frames in
Fig. 4. More results will be shown in the supplementary.

Table 5: Video prediction results.

| Human 3.6 | KTH
---|---|---
Method | MSE/10 | MAE/100 | SSIM$\uparrow$ | PSNR$\uparrow$ | SSIM$\uparrow$ | LPIPS$\downarrow$
ConvLSTM [40] | 50.4 | 18.9 | 0.776 | 23.58 | 0.712 | 0.231
Causal LSTM [48] | 45.8 | 17.2 | 0.851 | - | - | -
MIM [51] | 42.9 | 17.8 | 0.79 | - | - | -
E3D-LSTM [49] | 46.4 | 16.6 | 0.869 | - | - | -
PredRNN [50] | 48.4 | 18.9 | 0.781 | 27.55 | 0.839 | 0.204
MCnet + Residual [44] | - | - | - | 26.29 | 0.806 | -
TrajGRU [41] | - | - | - | 26.97 | 0.790 | -
DFN [20] | - | - | - | 27.26 | 0.794 | -
Conv-TT-LSTM [42] | - | - | - | 27.62 | 0.815 | 0.204
STReMN | 37.89 | 14.04 | 0.906 | 27.44 | 0.834 | 0.134

Figure 4: Qualitative results for video prediction.

###  4.3 Memory Analysis

In this section, we further investigate the behavior of the learned memory
update modules in the VOS task. First, let us define $d^{K}[t]$ as the number
of memory templates that are $t$ frames before the query frame in the memory
with $K$ templates. The first frame (where the ground truth mask is provided)
and the previous frame are ignored because they are always included in the
memory. $d[t]$ is normalized with $\Sigma_{t}d^{K}[t]$ so that it sums to $1$.
As shown in Fig. 5, the behaviors of the memory with different $K$ are
consistent: they preserve the recent frames (i.e. short distance) with a
higher likelihood, but maintains a sufficient amount of long-term frames (i.e.
long distance).

In addition, we take a look into the memory at the end of the video. Frames
that were retained in the memory usually show significantly distinct
appearances. For example, in the carousel video in the DAVIS test-dev dataset,
at frame $68$, the memory preserves frames 0 (ground truth), 17, 18, 29, 32,
and 67 (the newest frame), shown in Fig. 6. It can be noted that from frame 19
to 29, a shadow is cast on the horse. From frame 29 to 34, the horse is
partially occluded. This shows that our memory can capture some important
moments when there are significant appearance changes.

Figure 5: Percentage of memory templates that appear t frames before the
query. Figure 6: Carousel frames around memory templates

##  5 Conclusion

In this paper, we propose a novel constant-size memory network architecture
with the potential for scaling up to long videos. The main novelty is to learn
an adaptive memory update rule using the Gumbel softmax operator. This allows
our model to reason about information of past frames with a fixed size memory
of several slots. We showed that our model worked well on two difficult tasks
including video object segmentation and video prediction. We achieved state-
of-the-art results on DAVIS 2017 validation and test-dev set and competitive
results on YouTube-VOS. Our results on the video prediction also showed that
the proposed memory architecture outperforms other memory architectures. In
the future, we hope that our model can be extended to other tasks such as
video reasoning, reinforcement learning, and embodied AI.

## References

  * [1] Bao, L., Wu, B., Liu, W.: Cnn in mrf: Video object segmentation via inference in a cnn-based higher-order spatio-temporal mrf. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 5977–5986 (2018)
  * [2] Bhat, G., Lawin, F.J., Danelljan, M., Robinson, A., Felsberg, M., Van Gool, L., Timofte, R.: Learning what to learn for video object segmentation. In: European Conference on Computer Vision. pp. 777–794. Springer (2020)
  * [3] Bulat, A., Perez-Rua, J., Sudhakaran, S., Martínez, B., Tzimiropoulos, G.: Space-time mixing attention for video transformer. arXiv preprint arXiv:2106.05968 (2021)
  * [4] Caelles, S., Maninis, K.K., Pont-Tuset, J., Leal-Taixé, L., Cremers, D., Van Gool, L.: One-shot video object segmentation. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 221–230 (2017)
  * [5] Chen, L.C., Zhu, Y., Papandreou, G., Schroff, F., Adam, H.: Encoder-decoder with atrous separable convolution for semantic image segmentation. In: Proceedings of the European conference on computer vision (ECCV). pp. 801–818 (2018)
  * [6] Cheng, H.K., Tai, Y.W., Tang, C.K.: Rethinking space-time networks with improved memory coverage for efficient video object segmentation. In: NeurIPS (2021)
  * [7] Cheng, M., Mitra, N.J., Huang, X., Torr, P.H.S., Hu, S.: Global contrast based salient region detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 37(3), 569–582 (2015). https://doi.org/10.1109/TPAMI.2014.2345401
  * [8] Cho, K., van Merrienboer, B., Bahdanau, D., Bengio, Y.: On the properties of neural machine translation: Encoder-decoder approaches. CoRR abs/1409.1259 (2014), http://arxiv.org/abs/1409.1259
  * [9] Dai, Z., Yang, Z., Yang, Y., Carbonell, J., Le, Q., Salakhutdinov, R.: Transformer-XL: Attentive language models beyond a fixed-length context. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. pp. 2978–2988. Association for Computational Linguistics, Florence, Italy (Jul 2019). https://doi.org/10.18653/v1/P19-1285, https://aclanthology.org/P19-1285
  * [10] Graves, A., Wayne, G., Danihelka, I.: Neural turing machines. CoRR abs/1410.5401 (2014), http://arxiv.org/abs/1410.5401
  * [11] Guen, V.L., Thome, N.: Disentangling physical dynamics from unknown factors for unsupervised video prediction. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2020)
  * [12] Hariharan, B., Arbelaez, P., Bourdev, L., Maji, S., Malik, J.: Semantic contours from inverse detectors. In: International Conference on Computer Vision (ICCV) (2011)
  * [13] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [14] Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural computation 9(8), 1735–1780 (1997)
  * [15] Hu, L., Zhang, P., Zhang, B., Pan, P., Xu, Y., Jin, R.: Learning position and target consistency for memory-based video object segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 4144–4154 (June 2021)
  * [16] Hu, Y.T., Huang, J.B., Schwing, A.G.: Maskrnn: Instance level video object segmentation. arXiv preprint arXiv:1803.11187 (2018)
  * [17] Ioffe, S., Szegedy, C.: Batch normalization: Accelerating deep network training by reducing internal covariate shift. In: International conference on machine learning. pp. 448–456. PMLR (2015)
  * [18] Ionescu, C., Papava, D., Olaru, V., Sminchisescu, C.: Human3.6m: Large scale datasets and predictive methods for 3d human sensing in natural environments. IEEE Transactions on Pattern Analysis and Machine Intelligence 36(7), 1325–1339 (jul 2014)
  * [19] Jang, E., Gu, S., Poole, B.: Categorical reparameterization with gumbel-softmax. ICLR (2017)
  * [20] Jia, X., De Brabandere, B., Tuytelaars, T., Gool, L.V.: Dynamic filter networks. In: Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 29. Curran Associates, Inc. (2016), https://proceedings.neurips.cc/paper/2016/file/8bf1211fd4b7b94528899de0a43b9fb3-Paper.pdf
  * [21] Johnander, J., Danelljan, M., Brissman, E., Khan, F.S., Felsberg, M.: A generative appearance model for end-to-end video object segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2019)
  * [22] Kim, C., Li, F., Rehg, J.M.: Multi-object tracking with neural gating using bilinear lstm. In: Proceedings of the European Conference on Computer Vision (ECCV). pp. 200–215 (2018)
  * [23] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. In: ICLR (2015), http://arxiv.org/abs/1412.6980
  * [24] Lei, J., Wang, L., Shen, Y., Yu, D., Berg, T.L., Bansal, M.: Mart: Memory-augmented recurrent transformer for coherent video paragraph captioning. In: ACL (2020)
  * [25] Li, G., Yu, Y.: Visual saliency based on multiscale deep features. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 5455–5463 (June 2015)
  * [26] Li, X., Loy, C.C.: Video object segmentation with joint re-identification and attention-aware mask propagation. In: Proceedings of the European Conference on Computer Vision (ECCV). pp. 90–105 (2018)
  * [27] Li, Y., Shen, Z., Shan, Y.: Fast video object segmentation using the global context module. In: Vedaldi, A., Bischof, H., Brox, T., Frahm, J. (eds.) Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part X. Lecture Notes in Computer Science, vol. 12355, pp. 735–750. Springer (2020). https://doi.org/10.1007/978-3-030-58607-2_43, https://doi.org/10.1007/978-3-030-58607-2_43
  * [28] Lin, T.Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., Zitnick, C.L.: Microsoft coco: Common objects in context. In: European conference on computer vision. pp. 740–755. Springer (2014)
  * [29] Lu, X., Ma, C., Ni, B., Yang, X., Reid, I., Yang, M.H.: Deep regression tracking with shrinkage loss. In: Proceedings of the European conference on computer vision (ECCV). pp. 353–369 (2018)
  * [30] Lu, X., Wang, W., Martin, D., Zhou, T., Shen, J., Luc, V.G.: Video object segmentation with episodic graph memory networks. In: ECCV (2020)
  * [31] Luiten, J., Voigtlaender, P., Leibe, B.: Premvos: Proposal-generation, refinement and merging for video object segmentation. In: Asian Conference on Computer Vision (2018)
  * [32] Oh, S.W., Lee, J.Y., Xu, N., Kim, S.J.: Video object segmentation using space-time memory networks. In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) (October 2019)
  * [33] Perazzi, F., Khoreva, A., Benenson, R., Schiele, B., Sorkine-Hornung, A.: Learning video object segmentation from static images. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 2663–2672 (2017)
  * [34] Pont-Tuset, J., Perazzi, F., Caelles, S., Arbeláez, P., Sorkine-Hornung, A., Van Gool, L.: The 2017 davis challenge on video object segmentation. arXiv:1704.00675 (2017)
  * [35] Rae, J.W., Potapenko, A., Jayakumar, S.M., Hillier, C., Lillicrap, T.P.: Compressive transformers for long-range sequence modelling. In: International Conference on Learning Representations (2020), https://openreview.net/forum?id=SylKikSYDH
  * [36] Robinson, A., Lawin, F.J., Danelljan, M., Khan, F.S., Felsberg, M.: Learning fast and robust target models for video object segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7406–7415 (2020)
  * [37] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: MICCAI (2015)
  * [38] Schuldt, C., Laptev, I., Caputo, B.: Recognizing human actions: a local svm approach. In: Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004. vol. 3, pp. 32–36 Vol.3 (2004). https://doi.org/10.1109/ICPR.2004.1334462
  * [39] Seong, H., Hyun, J., Kim, E.: Kernelized memory network for video object segmentation. In: European Conference on Computer Vision. pp. 629–645. Springer (2020)
  * [40] Shi, X., Chen, Z., Wang, H., Yeung, D.Y., Wong, W.K., Woo, W.C.: Convolutional lstm network: A machine learning approach for precipitation nowcasting. Advances in neural information processing systems 2015, 802–810 (2015)
  * [41] Shi, X., Gao, Z., Lausen, L., Wang, H., Yeung, D.Y., Wong, W.k., WOO, W.c.: Deep learning for precipitation nowcasting: A benchmark and a new model. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 30. Curran Associates, Inc. (2017), https://proceedings.neurips.cc/paper/2017/file/a6db4ed04f1621a119799fd3d7545d3d-Paper.pdf
  * [42] Su, J., Byeon, W., Kossaifi, J., Huang, F., Kautz, J., Anandkumar, A.: Convolutional tensor-train lstm for spatio-temporal learning. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.F., Lin, H. (eds.) Advances in Neural Information Processing Systems. vol. 33, pp. 13714–13726. Curran Associates, Inc. (2020), https://proceedings.neurips.cc/paper/2020/file/9e1a36515d6704d7eb7a30d783400e5d-Paper.pdf
  * [43] Ummenhofer, B., Zhou, H., Uhrig, J., Mayer, N., Ilg, E., Dosovitskiy, A., Brox, T.: Demon: Depth and motion network for learning monocular stereo. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 5038–5047 (2017)
  * [44] Villegas, R., Yang, J., Hong, S., Lin, X., Lee, H.: Decomposing motion and content for natural video sequence prediction. ICLR (2017)
  * [45] Voigtlaender, P., Chai, Y., Schroff, F., Adam, H., Leibe, B., Chen, L.C.: Feelvos: Fast end-to-end embedding learning for video object segmentation. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) pp. 9473–9482 (2019)
  * [46] Voigtlaender, P., Leibe, B.: Online adaptation of convolutional neural networks for the 2017 davis challenge on video object segmentation. In: The 2017 DAVIS Challenge on Video Object Segmentation-CVPR Workshops. vol. 5 (2017)
  * [47] Wang, H., Jiang, X., Ren, H., Hu, Y., Bai, S.: Swiftnet: Real-time video object segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 1296–1305 (June 2021)
  * [48] Wang, Y., Gao, Z., Long, M., Wang, J., Philip, S.Y.: Predrnn++: Towards a resolution of the deep-in-time dilemma in spatiotemporal predictive learning. In: International Conference on Machine Learning. pp. 5123–5132. PMLR (2018)
  * [49] Wang, Y., Jiang, L., Yang, M.H., Li, L.J., Long, M., Fei-Fei, L.: Eidetic 3d lstm: A model for video prediction and beyond. In: International conference on learning representations (2018)
  * [50] Wang, Y., Long, M., Wang, J., Gao, Z., Yu, P.S.: Predrnn: Recurrent neural networks for predictive learning using spatiotemporal lstms. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. pp. 879–888 (2017)
  * [51] Wang, Y., Zhang, J., Zhu, H., Long, M., Wang, J., Yu, P.S.: Memory in memory: A predictive neural network for learning higher-order non-stationarity from spatiotemporal dynamics. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 9154–9162 (2019)
  * [52] Wu, Y., He, K.: Group normalization. In: Proceedings of the European conference on computer vision (ECCV). pp. 3–19 (2018)
  * [53] Xie, H., Yao, H., Zhou, S., Zhang, S., Sun, W.: Efficient regional memory network for video object segmentation. In: CVPR (2021)
  * [54] Yan, Q., Xu, L., Shi, J., Jia, J.: Hierarchical saliency detection. 2013 IEEE Conference on Computer Vision and Pattern Recognition pp. 1155–1162 (2013)
  * [55] Yang, Z., Wei, Y., Yang, Y.: Collaborative video object segmentation by foreground-background integration. In: Proceedings of the European Conference on Computer Vision (2020)
  * [56] Yang, Z., Wei, Y., Yang, Y.: Associating objects with transformers for video object segmentation. In: Advances in Neural Information Processing Systems (NeurIPS) (2021)
  * [57] Zhang, R., Isola, P., Efros, A.A., Shechtman, E., Wang, O.: The unreasonable effectiveness of deep features as a perceptual metric. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 586–595 (2018)

##  Appendix 0.A Running Time Analysis

The time complexity of the space-time read for each query in STM is dominated
by $O(\frac{T}{\gamma}N^{2}(D_{k}+D_{v}))$ where $T$ is the number of frames
before the query frame, $\gamma$ is a constant deciding the sampling frequency
(i.e the memory will keep once every $\gamma$ frames in the video) for the
memory ($\gamma=5$ in the STM model), $N$ is the number of pixels, and $D_{k}$
and $D_{v}$ are the dimensionality of the keys and values respectively. For
STReMN, the number of memory slots is set to a small constant $M$ (up to $6$
in our experiments). Thus, our attention complexity is
$O(MN^{2}(D_{k}+D_{v}))$. Besides, to update the memory, our model first
transforms the memory template and the new input. The complexity of this
process is $O((M+1)ND_{k}^{2})$, which is similar to the key-val
transformation in the STM. Then the model measures the similarity between the
new input and every memory template - $O(MN^{2}D_{k})$. Therefore, the time
complexity of STReMN is $(O(MN^{2}(D_{k}+D_{v})+(M+1)ND_{k}^{2})$. Usually,
the number of pixels is at a higher order than $D_{k}$, hence in terms of
big-O we achieve linear speed-up w.r.t. STM.

In our model, the complexity for memory reading at each time step is
independent on the position of the query. In STM, the complexity depends on
the number of frames before the query. Therefore, STReMN is significantly
faster than STM in long videos more than $50$ frames.

##  Appendix 0.B Memory Fusion

In this section, we investigate the effect of the fusion module that we
briefly mentioned in Sec. 3.2 of the main paper. It is reasonably to think
about some kind of memory fusion to combine the information from multiple
slots. However in practice this is difficult for spatially-indexed memory such
as ours, because one would have to first align different memory slots
spatially that were potentially taken from different points of time and
objects might have undergone nonlinear motion already between these times.
Hence, some special designs are needed to align the features to make this
fusion happen.

Note that based on the experiment results, we did not utilize this module in
the system, but it is presented here as a negative result, by which we hope to
generate some food for thought for future practitioners especially because
memory fusion sounds like a plausible idea.

This module was proposed to combine the information from the deleted template
with other templates in the memory. Let $X_{i}^{M}$ be the deleted template,
and $X_{j}^{M}$ be the target memory template. Before being deleted,
$X_{i}^{M}$ is used to update $X_{j}^{M}$. First, we apply an input filter on
$X_{i}^{M}$ to get $X_{i}^{{}^{\prime}M}$ as follows:

$\displaystyle X^{A}_{j}$ $\displaystyle=FAM(X^{M}_{i},X^{M}_{j})$ (6)
$\displaystyle FAM(X^{M}_{i},X^{M}_{j})$
$\displaystyle=Softmax(X^{M}_{i}(X^{M}_{j})^{T})X^{M}_{j}$ (7) $\displaystyle
r$ $\displaystyle=\sigma(f([X_{i}^{M},X^{A}_{j}]))$ (8) $\displaystyle
X^{\prime M}_{i}$ $\displaystyle=r\odot X^{M}_{i}$ (9)

where $f$ is implemented with a CNN, $\sigma$ is the sigmoid function, and
$\odot$ is the Hadamard product. $FAM$, feature alignment module, is used to
align pixels from $X_{j}^{M}$ to $X_{i}^{M}$ in case the target object’s
position changes. Finally, $X_{j}^{M}$ is updated with $X_{i}^{{}^{\prime}M}$
as follows:

$\displaystyle X^{A}_{i}$ $\displaystyle=FAM(X^{M}_{j},X^{\prime M}_{i})$ (10)
$\displaystyle z$ $\displaystyle=\sigma(h([X^{A}_{i},X^{M}_{j}]))$ (11)
$\displaystyle\hat{X}^{M}_{j}$ $\displaystyle=(1-z)\odot X^{M}_{j}+z\odot
tanh(g([X^{A}_{i},X^{M}_{j}]))$ (12)

This was done before our proposed learning-based template updating algorithm,
hence at that time we tested different strategies to choose the target
template to update such as updating the least or most similar template or
updating every other templates in the memory. We show the results of updating
the least similar template in Table 6. The result of the ”without Fusion”
model was obtained by simply removed the fusion module from the model. The
weight was reused without retraining. The result shows that the fusion module
was trying to learn an identity function and hence unnecessary. When we used
other strategies such as updating the most similar template, we obtained
similar results to the one shown in Table 6. Hence, we finally decided to drop
the fusion module based on those experiment results.

Table 6: Results of the fusion module on DAVIS 17 test-dev. Note that based on this negative result, we did not utilize this module in the final system | with Fusion | without Fusion
---|---|---
J&F | 76.7 | 76.7

It is still unclear to us whether this task would not require memory fusion
because the length of the video is still not long enough (usual videos of
$30-100$ frames would be well-covered with the current approach of storing a
few templates and matching them) in the current benchmarks, or is it because
that it is difficult to learn a good fusion module because of the alignment
difficulties under deformable motion. In the future we plan to try the
algorithm on very long (1000+ frames) videos and examine whether some memory
fusion would bring some benefits over there.

##  Appendix 0.C Memory Analysis

In this section, we show what is stored in the memory. In Fig. 7, the frames
stored in the memory usually show significant appearance changes. Please refer
the the caption for more details.

Figure 7: After the memory frame 20, the person turns around. The same happens
for the memory frame 26. These events make the target appearance change
significantly. It can be seen that the memory learned to store useful frames
that have different appearances

##  Appendix 0.D Video Prediction - Qualitative Results

We show more qualitative results in Fig. 8. In Fig. 9, we show some failure
cases of our model. In these 2 videos, our model fails to predict the correct
position of the arms probably because the arms are moving fast.

Figure 8: Qualitative results for video prediction. Figure 9: Qualitative
results for video prediction - Failure cases.

##  Appendix 0.E Video Object Segmentation - Qualitative Results.

We show more qualitative results for the VOS task in Fig. 10 and failure cases
in Fig. 11. Fig. 11 shows that our method sometimes assigns the same object ID
to different objects when there are multiple objects of the same types in the
scene.

Figure 10: Qualitative results for VOS. Figure 11: Qualitative results for VOS
- Failure cases.