Learning Fast and Robust Target Models for Video Object Segmentation

Introduction

The problem of video object segmentation (VOS) has a variety of important applications, including object boundary estimation for grasping , autonomous driving , surveillance and video editing . The task is to predict pixel-accurate masks of the region occupied by a specific target object, in every frame of a given video sequence. This work focuses on the semi-supervised setting, where a target ground truth mask is provided in the first frame. Challenges arise in dynamic environments with similar background objects and when the target undergoes considerable appearance changes or occlusions. Successful video object segmentation therefore requires both robust and accurate target pixel classification.

Aiming to achieve a robust target-specific segmentation, several methods fine-tune a generic segmentation network on the first frame, given the ground-truth mask. Although capable of generating accurate segmentation masks under favorable circumstances, these methods suffer from low frame-rates, impractical for many real world applications. Moreover, fine-tuning is prone to overfit to a single view of the scene, while degrading generic segmentation functionality learned during offline training. This limits performance in more challenging videos involving drastic appearance changes, occlusions and distractor objects . Further, the crucial fine-tuning step is not included in the offline training stage, which therefore does not simulate the full inference procedure.

Recent works address these limitations by employing internal models of the target and background appearance. They are based on, e.g., feature concatenation , feature matching or Gaussian models . Such generative models have the advantage of facilitating efficient closed-form solutions that are easily integrated into neural networks. A drawback to these methods is the demand for large amounts of data in order to learn representations applicable for the internal models . Due to the limited availability of annotated video data, these methods rely heavily on pre-training on image segmentation and synthesized VOS data via augmentation techniques. On the other hand, discriminative methods generally yield superior predictive power and have thus been preferred in many vision tasks, including image recognition , object detection and tracking . In this work, we therefore tackle the problem of integrating a discriminative model of the target appearance into a VOS architecture.

Our approach integrates a light-weight discriminative target model and a segmentation network, for modeling the target appearance and generating accurate segmentation masks. Operating on deep features, the proposed target model learns during inference to provide robust segmentation scores. The segmentation network is designed to process features with the segmentation scores as guidance. During offline training the network learns to accurately adhere to object edges and to suppress erroneous classification scores from the target model, see Figure 1. To learn the network parameters, we propose a training strategy that simulates the inference stage. This is realized by optimizing the target model on reference frames in each batch, and back-propagating the segmentation errors on corresponding validation frames. Contrary to fine-tuning based methods, the target adaption process is thus fully simulated during the offline training stage. During inference we keep the segmentation network fixed, while the target-specific learning is entirely performed by the target appearance model. Consequently, the segmentation network is target agnostic, retaining generic object segmentation functionality.

Unlike previous state-of-the-art methods, our discriminative target model requires no pre-training for image and synthetic video segmentation data. Our final approach, consisting of a single network architecture, is trained on VOS data in a single phase. Further, the employment of Gauss-Newton based optimization enables real-time video segmentation. We perform experiments on the DAVIS and YouTube-VOS 2018 datasets and demonstrate the impact of the components of our proposed approach in an ablative analysis. We further compare our approach to several state-of-the-art methods. Despite its simplicity, our approach achieves an overall score of 76.7 on DAVIS 2017 and 72.1 on YouTube-VOS, while operating at 22 frames per second (FPS). We also evaluate a faster version of our approach that achieves a speed of 41 FPS, with only a slight degradation in segmentation accuracy.

Related work

The task of video object segmentation has seen extensive study and rapid development in recent years, largely driven by the introduction and evolution of benchmarks such as DAVIS and YouTube-VOS .

First-frame fine-tuning: Most state-of-the-art approaches train a segmentation network offline, and then fine-tune it on the first frame to learn the target-specific appearance. This philosophy was extended by additionally fine-tuning on subsequent video frames. Other approaches further integrate optical flow as an additional cue. While obtaining impressive results on the DAVIS 2016 dataset, the extensive fine-tuning leads to impractically long run-times. Furthermore, such extensive fine-tuning is prone to overfitting, a problem only partially addressed by heavy data augmentation .

Non-causal methods: Another line of research approaches the VOS problem by allowing non-causal processing . In this work, we focus on the causal setting in order to accommodate real-time applications.

Mask propagation: Several recent methods employ a mask-propagation module to improve spatio-temporal consistency of the segmentation. In , the model is learned offline to predict the target mask through refinement of the previous frame’s segmentation output. To further avoid first-frame fine-tuning, some approaches concatenate the current frame features with the previous mask and a target representation generated in the first frame. Unlike these methods, we do not explicitly enforce spatio-temporal consistency through mask-propagation. Instead, we use previous segmentation masks as training data for the discriminative model.

Feature matching: Recent methods incorporate feature matching to locate the target object. Rather than fine-tuning the network on the first frame, these methods first construct appearance models from features corresponding to the initial target labels. Features from incoming frames are then classified using techniques inspired by classical clustering methods or feature matching . In , a dynamic memory is used to combine feature matching from multiple previous frames.

Tracking: Efficient online learning of discriminative target-specific appearance models has been explored in visual tracking . Recently, optimization-based trackers have achieved impressive results on benchmarks. These methods train convolution filters using efficient optimization to discriminate between target and background. The close relation between the two problem domains is made explicit in , where object trackers are used as external components to locate the target. Gauss-Newton has previously been used in object segmentation for pose estimation of known object shapes. In contrast, we do not employ off-the-shelf trackers to predict the target or rely on target pose estimation. Instead we take inspiration from the optimization-based learning of a discriminative model, in order to capture the target object appearance.

Method

In this work, we tackle the problem of predicting accurate segmentation masks of a target object, defined in the first frame of the video. This is addressed by constructing two network modules, $D$ and $S$, specifically designed for target modeling and segmentation respectively. The target model $D({\bf x};{\bf w})$ takes features ${\bf x}$ as input and generates a coarse, but robust, segmentation output ${\bf s}=D({\bf x};{\bf w})$ of the target object. It is parametrized by the weights ${\bf w}$, which are solely learned during inference using the first-frame ground-truth, in order to capture the appearance of the target object.

The coarse segmentation scores ${\bf s}$, generated by the target model $D$, is passed to the segmentation network $S({\bf s},{\bf x};\theta)$, additionally taking backbone features ${\bf x}=F(I)$. The parameters $\theta$ of the segmentation network is only trained during the offline training stage to predict the final high-resolution segmentation of the target. The coarse segmentation ${\bf s}$ thus serves as a robust guide, indicating the target location. Crucially, this allows the segmentation network to remain target agnostic, and learn generic segmentation functionality. Since $S$ is trained with coarse segmentation inputs ${\bf s}$ generated by the target model, it learns to enhance its prediction and correct mistakes.

During inference, we update the target model using the segmentation masks generated by $S$. Specifically, the mask and associated features are stored in a memory $\mathcal{M}$. Before the next incoming frame, we further adapt our model to the target appearance by re-optimizing $D$ over all samples in $\mathcal{M}$. In contrast to simply re-training on the latest frame, adding more training data to $\mathcal{M}$ over time, reduces the risk for model drifting. Our full VOS architecture is illustrated in Figure 2.

We aim to develop a powerful and discriminative target appearance model, capable of differentiating between the target and background image regions. To successfully accommodate the VOS problem, the model must be robust to appearance changes and distractor objects. Moreover, it needs to be easily updated with new data and efficiently trainable. To this end, we employ a light-weight linear model $D({\bf x};{\bf w})$ realized as two convolutional layers,

with parameters ${\bf w}$. These are trained exclusively during inference with image features ${\bf x}$ and the target segmentation mask ${\bf y}$ given in the first video frame. It then takes input feature maps ${\bf x}$ from subsequent video frames and outputs coarse segmentation scores ${\bf s}$. The factorized formulation (1) is used for efficiency, where the first layer ${\bf w}_{1}$ reduces the feature dimensionality and the second layer ${\bf w}_{2}$ computes the actual segmentation scores.

Fundamental to our approach, the target model parameters ${\bf w}$ must be learned with minimal computational impact. To enable the deployment of fast converging optimization techniques, we adopt an $L^{2}$ loss given by,

Optimization: We employ the Gauss-Newton (GN) based strategy from to optimize the parameters ${\bf w}$. In comparison to the commonly used gradient descent based approaches, this strategy has significantly faster convergence properties . In each iteration, the optimal increment $\Delta{\bf w}$ is found using a quadratic approximation of the loss in (2)

Here, $r_{{\bf w}}$ contains the residuals (2) as $\sqrt{\gamma_{k}}{\bf v}_{k}\cdot({\bf y}_{k}-U(D({\bf x}_{k})))$ and $\sqrt{\lambda_{j}}{\bf w}_{j}$ and $J_{{\bf w}}$ is the Jacobian of the residuals $r_{{\bf w}}$ at ${\bf w}$ and. The objective (3) results in a positive definite quadratic problem, which we minimize over $\Delta{\bf w}$ with Conjugate Gradient (CG) descent . We then update ${\bf w}\leftarrow{\bf w}+\Delta{\bf w}$ and execute the next GN iteration.

Pixel weighting: To address the imbalance between target and background, we employ a weight mask ${\bf v}$ in (2) to ensure that the target influence is not too small relative to the usually much larger background region. We define the target influence as the fraction of target pixels in the image $\hat{\kappa}_{k}=N^{-1}\sum_{n}{\bf y}_{k}(n)$, where $n$ is the pixel index and $N$ the total number of pixels. The weight mask is then defined as

2 Segmentation Network

While the target model provides robust but coarse segmentation scores, the final aim is to generate an accurate segmentation mask of the target at the original image resolution. To this end, we introduce a segmentation network, that processes the coarse score ${\bf s}$ along with backbone features. The network consists of two types of building blocks: a target segmentation encoder (TSE) and a refinement module (see Figure 3). From these we construct a U-Net based architecture for object segmentation as in . Unlike most state-of-the-art methods for semantic segmentation , the U-Net structure does not rely on dilated convolutions, but effectively integrates low-resolution deep feature maps. This is crucial for reducing the computational complexity of our target model during inference.

The segmentation network takes features maps ${\bf x}^{d}$ as input from multiple depths in the backbone feature extractor network, with decreased resolution at each depth $d$. For each layer, ${\bf x}^{d}$ along with the coarse scores ${\bf s}$ are first processed by a TSE block $T^{d}$. The refinement module $R^{d}$ then inputs the resulting segmentation encoding generated by $T^{d}$ and the refined outputs ${\bf z}^{d+1}$ from the preceding deeper layer ${\bf z}^{d}=R^{d}(T^{d}({\bf x}^{d},{\bf s}),{\bf z}^{d+1})$. The refinement modules are comprised of two residual blocks and a channel attention block (CAB), as in . For the deepest block we set ${\bf z}^{d+1}$ to an intermediate projection of ${\bf x}^{d}$ inside $T^{d}$. The output ${\bf z}^{1}$ at the shallowest layer is processed by two convolutional layers, providing the final refined segmentation output $\hat{{\bf y}}$.

Target segmentation encoder: Seeking to integrate features and scores, we introduce the target segmentation encoder (TSE). It processes features in two steps, as visualized in Figure 3 (right). First, we project the backbone features to 64 channels to reduce the subsequent computational complexity. We maintain 64 channels throughout the segmentation network, keeping the number of parameters low. After projection, the features are concatenated with the segmentation score ${\bf s}$ and encoded by three convolutional layers.

3 Offline Training

We learn the parameters in our segmentation network offline by training on VOS training data. To this end, we propose a training scheme to simulate the inference stage. The network is trained on samples consisting of one reference frame and one or more validation frames. These are all randomly selected from the same video sequence. A training iteration is then performed as follows: We first optimize the target model weights ${\bf w}$, described in Section 3.1, based on the reference frame. We then apply our full network, along with the learned target model, on the validation frames to predict the target segmentations. The parameters in the network are learned by back-propagating through the binary cross-entropy loss with respect to the ground-truth masks.

During offline training, we only learn the parameters of the segmentation network, and freeze the weights of the feature extractor. Since the target model only receives backbone features, we can pre-learn and store the target model weights for each sequence. The offline training time is therefore not significantly affected by the learning of $D$.

The network is trained in a single phase on VOS data. We select one reference frame and two validation frames per sample and train the segmentation network with the ADAM optimizer . We start with the learning rate $\alpha=10^{-3}$, moment decay rates $\beta_{1}=0.9,\beta_{2}=0.999$ and weight decay $10^{-5}$, and train for about $10^{6}$ iterations, split into 120 epochs. The learning rate is then reduced to $\alpha=10^{-4}$, and we train for another 60 epochs. With pre-learned target model weights, the training is completed in less than a day.

4 Inference

During inference, we optimize the target model parameters ${\bf w}_{1}$ and ${\bf w}_{2}$ on the current dataset $\mathcal{M}_{i}$ every $t_{s}$-th frame. For efficiency, we keep the first layer of the target model ${\bf w}_{1}$ fixed during updates. Setting $t_{s}$ to a large value reduces the inference time and regularizes the update of the target model. On the other hand, it is important that the target model is updated frequently, for objects that undergo rapid appearance changes. In our approach we set $t_{s}=8$. The framework supports multi object segmentation by employing a target model for each object and fuse the final refined predictions with softmax aggregation as in . We only require one feature extraction per image, since the features ${\bf x}_{i}$ are common for all target objects.

5 Implementation details

We implement our method in the PyTorch framework and use a ResNet , pre-trained on ImageNet , as the feature extractor $F$. Following the naming convention in Table 1 of , we extract four feature maps from the outputs of the blocks conv2_x through conv5_x. The target model $D$ accepts features from conv4_x and produces 1-channel score maps. Both the input features and output scores have a spatial resolution 1/16th of the input image.

Target model: The first layer ${\bf w}_{1}$ has $1\times 1$ kernels reducing input features to $c=96$ channels while ${\bf w}_{2}$ has a $3\times 3$ kernel with one output channel. During first-frame optimization, ${\bf w}_{1}$ and ${\bf w}_{2}$ are randomly initialized. Using the data augmentation (see the supplementary material), we generate a initial dataset $\mathcal{M}_{0}$ of 5 image and label pairs. We then optimize ${\bf w}_{1}$ and ${\bf w}_{2}$ with the Gauss-Newton algorithm outlined in Section 3.1 with $N_{\text{GN}}=5$ GN steps. We apply $N_{\text{CG}}=10$ CG iterations in all GN steps but the first one. Since the initialization is random, we reduce the number of iterations to $N_{\text{CGi}}=5$ in the first step. In the target model update step we use $N_{\text{CGu}}=10$ CG iterations, updating ${\bf w}_{2}$ every $t_{s}=8$ frame, while keeping ${\bf w}_{1}$ fixed. We employ the aforementioned settings with a ResNet-101 backbone in our final approach, denoted Ours in the following sections.

We additionally develop a fast version, named Ours-fast, with a ResNet-18 backbone and fewer optimization steps. Specifically, we set $N_{\text{GN}}=4$, $N_{\text{CGi}}=5$, $N_{\text{CG}}=10$ and $N_{\text{CGu}}=5$.

Experiments

We perform experiments on three benchmarks: DAVIS 2016 , DAVIS 2017 and YouTube-VOS . For YouTube-VOS, we compare on the official validation set, with withheld ground-truth. For ablative experiments, we also show results on a separate validation split of the YouTube-VOS train set, consisting of 300 videos not used for training. Following the standard DAVIS protocol, we report both the mean Jaccard $\mathcal{J}$ index and mean boundary $\mathcal{F}$ scores, along with the overall score $\mathcal{J\&F}$, which is the mean of the two. For comparisons on YouTube-VOS, we report $\mathcal{J}$ and $\mathcal{F}$ scores for classes included in the training set (seen) and the ones that are not (unseen). The overall score $\mathcal{G}$ is computed as the average over all four scores, defined in YouTube-VOS. In addition, we compare the computational speed of the methods in terms of frames per second (FPS), computed by taking the average over the DAVIS 2016 validation set. For our approach, we used a V100 GPU and included all steps in Algorithm 1 to compute the frame rates. Further results and analysis are provided in the supplement.

We analyze the contribution of the key components in our approach. All compared approaches are trained using the YouTube-VOS training split.

Base net: We construct a baseline network to analyze the impact of our target model $D$. This is performed by replacing $D$ with an offline-trained target encoder, and retraining the segmentation network $S$. As for our proposed network we keep the backbone $F$ parameters fixed. The target encoder is comprised of two convolutional layers, taking reference frame features from ResNet blocks conv4_x and the corresponding target mask as input. Features (conv4_x) extracted from the test frame are concatenated with the output from the target encoder and processed with two additional convolutional layers. The output is then passed to the segmentation network $S$ in the same manner as for the coarse segmentation score ${\bf s}$ (see Section 3.2). We train this model with the same methodology as for our network.

F.-T: We integrate a first-frame fine-tuning strategy into our network to compare this to our discriminative target model. For this purpose, we create an initial dataset $\mathcal{M}_{0}$ with 20 samples using the same sample generation procedure employed for our approach (section 3.1). We then fine-tune all components of the network, except for the feature extractor, with supervision on the target model (loss in (2)) and the pre-trained segmentation network (binary cross-entropy loss) using the ADAM optimizer with 100 iterations and a batch size of four. In this setting we omitted the proposed optimization strategy of the target model and instead initialize the parameters randomly before fine-tuning.

$D$-only - no update: To analyze the impact of the segmentation network $S$, we remove it from our architecture and instead let the target-specific model $D$ output the final segmentations. The coarse target model predictions are upsampled to full image resolution through bilinear interpolation. In this version, we only train the target model $D$ on the first frame, and refrain from subsequent updates.

$D$-only: We further enable target model updates (as described in Section 3.4) using the raw target predictions.

Ours - no update: For a fair comparison, we evaluate a variant of our approach with the segmentation network, but without any update of the target model $D$ during inference.

Ours: Finally, we include target model updates with segmentation network predictions to obtain our final approach.

In Table 1, we present the results in terms of the $\mathcal{J}$ score on a separate validation split of the YouTube-VOS training dataset. The base network, not employing the target model $D$, achieves a score of $49.8\%$. Employing fine-tuning on the first frame leads to an absolute improvement of $6\%$. Remarkably, using only the linear target model $D$ is on par with online fine-tuning. While fine-tuning an entire segmentation network is prone to severe overfitting to the initial frame, our shallow target model has limited capacity, acting as an implicit regularization mechanism that benefits robustness and generalization to unseen aspects of the target and background appearance. Including updates results in an absolute improvement of $1.6\%$, demonstrates that we benefit from online updates despite the coarseness of the target mode generated labels. Further adding the segmentation network $S$ (Ours - no update) leads to a major absolute gain of $8.3\%$. This improvement stems from the offline-learned processing of the coarse segmentations, yielding more accurate mask predictions. Finally, the proposed online updating strategy additionally improves the score to $71.4\%$.

2 Comparison to state-of-the-art

We compare our method to recent approaches on the YouTube-VOS, DAVIS 2017 and DAVIS 2016 benchmarks. We provide results for two versions of our approach: Ours and Ours (fast) (see Section 3.5). Many compared methods include additional training data or employ models that have been pre-trained on segmentation data. For fair comparison we classify methods into two categories: “seg” for methods employing segmentation networks, pre-trained on e.g PASCAL or MS-COCO and “synth” for methods that perform additional training on synthetic VOS data generated from image segmentation datasets.

YouTube-VOS : The official YouTube-VOS validation dataset has 474 sequences with objects from 91 classes. Out of these, 26 classes are not present in the training set. We provide results for Ours and Ours (fast), both trained on the YouTube-VOS 2018 training set. We compare our method with the results reported in , that were obtained by retraining the methods on YouTube-VOS. Additionally, we compare to PReMVOS, AGAME , RVOS and STM . The results are reported in Table 2.

Among the methods using additional training data, OSVOS , OnAVOS and PReMVOS employ first-frame fine-tuning, leading to inferior frame-rates below $0.3$ FPS. In addition to fine-tuning, PReMVOS constitutes a highly complex framework, encompassing multiple components and cues: mask-region proposals, optical flow based mask predictions, re-identification, merging and tracking modules. In contrast, our approach is simple, consisting of a single network together with a light-weight target model. Remarkably, our approach significantly outperforms PReMVOS by a relative margin of $5.2\%$, yielding a final $\mathcal{G}$-score of $72.1$. The recent STM method has the highest performance, employing feature matching with a dynamic memory to predict the target.

RVOS is trained only on YouTube-VOS, achieving a $\mathcal{G}$-score of $56.8$ by employing recurrent networks. In addition to recurrent networks, S2S employs first-frame fine-tuning, achieving a $\mathcal{G}$-score of $64.4$ with a significantly slower frame-rate compared to RVOS. In AGAME a generative appearance model is employed, resulting in a $\mathcal{G}$-score of $66.1$. We further report results from a version of STM (YV18), where training has been performed solely on YouTube-VOS. This significantly degrades the performance to a $\mathcal{G}$-score of $68.2$. Ours outperforms all previous methods when only video data from YouTube-VOS has been used for training. We believe that, since our target model already provides robust predictions of the target on its own, our approach can achieve high performance without extensive training on additional data. Notably, Ours-fast, maintains an impressive $\mathcal{G}$-score of $65.7$, while being significantly faster than all previous methods at $41.3$ FPS.

DAVIS 2017 : The validation set for DAVIS 2017 contains 30 sequences. We provide results for Ours and Ours-fast, trained a combination of the YouTube-VOS and DAVIS 2017 train splits, such that DAVIS 2017 is traversed eight times per epoch, and YouTube-VOS once. We report the results on DAVIS 2017 in Table 3. As in the YouTube-VOS comparison above, we categorize the methods with respect to usage of training data. Since our approaches (Ours and Ours-fast) and AGAME , RVOS , STM and FEELVOS all include the YouTube-VOS during training, we add a third category denoted “yv”.

OnAVOS , OSVOS-S , MGCRN , PReMVOS employ extensive fine-tuning on the first-frame, experiencing impractical segmentation speed. The methods RGMP , AGAME , RANet and FEELVOS all employ mask-propagation, which is combined with feature matching in the latter three methods. Ours outperforms these methods with an $\mathcal{J\&F}$ score of $76.7$. In addition, Ours-fast is significantly faster than all previous approaches, maintaining a $\mathcal{J\&F}$ score of $70.2$. Our method is only outperformed by PReMVOS and the recent STM, achieving $\mathcal{J\&F}$ scores of $77.8$ and $81.8$ respectively. PReMVOS, however, suffer from extremely slow frame rates: approximately 500 times lower than ours. Moreover, our approach outperforms PReMVOS on the more challenging and large scale YouTube-VOS (Table 2) by a large margin.

We also evaluate our approach when only trained on DAVIS 2017, denoted Ours (DV17). We compare this approach to the methods FAVOS , AGAME (DV17) and STM (DV17) , which have also only been trained on the DAVIS 2017 train split. Our method significantly outperform all these methods with a $\mathcal{J\&F}$ score of $68.8$. Moreover, this result is superior to OnAVOS, OSVOS-S, RANet, RVOS, RGMP and comparable to AGAME and FEELVOS despite their use of additional training data.

DAVIS 2016 : Finally, we evaluate our method on the 20 validation sequences in DAVIS 2016, corresponding to a subset of DAVIS 2017 and report the results in Table 3. Our methods perform comparable to the fine-tuning based approaches PReMVOS, MGCRN , OnAVOS and OSVOS-S. Further, Ours outperforms AGAME, RGMP, OSNM, FAVOS and FEELVOS.

3 Qualitative Analysis

State-of-the-art: We compare our approach to some state-of-the-art methods in Figure 4. By using an early and a late frame from each video sequence, we study how the methods cope with large target deformations over time. In the first sequence (first and second row), the fine-tuning based OSVOS-S struggles as the target pose changes. While the mask-propagation in RGMP and generative appearance model in AGAME are accurate on fine details, they both fail to segment the red target, possibly due to occlusions. In the second and third sequences (rows three to six), all of the above methods fail to robustly segment the different targets. In contrast, our method accurately segments all targets in these challenging video sequences.

Target model: Some examples of the coarse segmentation scores and the final segmentation output are visualized in Figures 1 and 5. In most cases, the target model provides robust segmentation scores of the target object. It however struggles is some cases where the target object contains thin or small structures or details. An example is the challenging kite lines in the kite-surfing sequence, which are not accurately segmented. This is likely due to the coarse feature maps the target model is operating on. It also have problems separating almost identical targets such as the sheep. On the other hand, the model successfully handles very similar targets as in the gold-fish sequence (row 2 in Figure 1).

Conclusion

We propose video object segmentation approach, integrating a light-weight but highly discriminative target appearance model and a segmentation network. We find that despite its simplicity, a linear discriminative model is capable of generating robust target predictions. The segmentation network converts the predictions into high-quality object segmentations. The target model is efficiently trained during inference. Our method operates at high frame-rates and achieves state-of-the-art performance on the YouTube-VOS dataset and competitive results on DAVIS 2017 despite trained on limited data.

Acknowledments: This work was supported by the ELLIIT Excellence Center at Linköping-Lund for Information Technology, Autonomous Systems and Software Program (WASP) and the SSF project Symbicloud.

References

Initial sample generation

Detailed Quantitative Results

In this section we report some additional quantitative results.

We analyze how the amount of training data impacts the performance of our approach. For this purpose we train our model on subsets of the YouTube-VOS training set containing 100%, 50%, 25% and 0% of the YouTube-VOS 2018 training split (excluding the validation split used to analyzing our approach as in Section 4 in the paper). For the version using 0% of the data, called “Ours D-only”, we only apply or target appearance model, which is trained during inference, thus requiring no offline training. As shown in Table 4, the performance improves as we increase the amount of training data from 0 to 100 percent of the YouTubeVOS training split. Already at 25 percent our approach outperforms recent methods such as AGAME (see Table 2 in the paper). At 50 percent, our approach surpasses all compared methods in Table 2 in the paper, that are trained only on the full YouTube-VOS training set. Remarkably, our target model without the segmentation (Ours D-only), consisting of a linear filter that requires no pre-training, obtains a $\mathcal{G}$-score superior to the methods OSVOS , OnAVOS and the recent RVOS (see Table 2 in the paper).

2 Algorithm runtime analysis

We investigate the runtime for the different steps in our proposed VOS approach in Algorithm 1 in the main paper. All runtimes have been computed by averaging over the DAVIS 2016 evaluation split.

Figure 7 shows how execution in frame 1 (the init phase, steps 1 and 2 in Algorithm 1) changes vs the size of the initial sample memory (or dataset) $\mathcal{M}_{0}$, when segmenting a single object. We present relative runtimes of the maximum time spent using all steps with $|\mathcal{M}_{0}|=20$ The time spent during data augmentation is dominated by the inpainting which is performed only once, on the first frame, and hence it is appears constant.

In addition, Table 5 shows the distribution of average time spent on each step in one frame in the forward phase. This is in the steady-state situation, after the sample memory is filled (here $|\mathcal{M}_{i}|=80$), averaged over the last $t_{s}=8$ frames of the sequence.

Since the DAVIS videos are quite short, the init phase accounts for 41 percent of the total runtime when evaluating the Ours variant on DAVIS2016. On a per video basis, the initialization requires between 31 (for “cows” with 104 frames) and 60 percent (for “car-shadow” with 40 frames) of the total runtime.

From figure 7, we conclude that the first-frame initialization (algorithm steps 1-2) scales approximately linearly with $|\mathcal{M}_{0}|$. The per-frame (forward phase) processing (Algorithm 1 steps 3-9) is dominated by the model update training and feature extraction. Theoretically, the complexity of both phases scale linearly with the number of iterations in their respective optimization steps (step 2 and 9) as well as linearly with the number of targets.

3 Parameter sensitivity

Figure 9 reports the mean $\mathcal{J}$ as functions of the memory learning rate $\eta$ and target model update interval $t_{s}$ (defined in Section 3.4 in the paper). The experiments are performed on the YouTubeVOS validation split, defined in Section 4 in the paper. It is apparent that the method is rather insensitive to either parameter.

In addition, Table 6 shows the mean $\mathcal{J}$ as functions of the size of the initial training dataset $\mathcal{M}_{0}$. We test two variants of our method, one trained on YouTubeVOS data and one trained on both YouTubeVOS and DAVIS data. We evaluate on our own YouTubeVOS validation split and the DAVIS validation set. We observe that the YouTubeVOS evaluation is insensitive to the choice of $|\mathcal{M}_{0}|$. While still achieving a competitive $\mathcal{J}$-score without initial data augmentation, our approach obtains the best performance using four additional augmented samples in $\mathcal{M}_{0}$.