A Transductive Approach for Video Object Segmentation

Semi-supervised video object segmentation aims to separate a target object from a video sequence, given the mask in the first frame. Most of current prevailing methods utilize information from additional modules trained in other domains like optical flow and instance segmentation, and as a result they do not compete with other methods on common ground. To address this issue, we propose a simple yet strong transductive method, in which additional modules, datasets, and dedicated architectural designs are not needed. Our method takes a label propagation approach where pixel labels are passed forward based on feature similarity in an embedding space. Different from other propagation methods, ours diffuses temporal information in a holistic manner which take accounts of long-term object appearance. In addition, our method requires few additional computational overhead, and runs at a fast $\sim$37 fps speed. Our single model with a vanilla ResNet50 backbone achieves an overall score of 72.3 on the DAVIS 2017 validation set and 63.1 on the test set. This simple yet high performing and efficient method can serve as a solid baseline that facilitates future research. Code and models are available at \url{https://github.com/microsoft/transductive-vos.pytorch}.


Introduction
Video object segmentation addresses the problem of extracting object segments from a video sequence given the annotations in the starting frame. This semi-supervised setting is challenging as it requires the system to generalize to various objects, deformations, and occlusions. Nevertheless, video object segmentation has received considerable attention because of its broad practical applications in surveillance, self-driving cars, robotics, and video editing.
Despite the simplicity of the formulation, video object segmentation is closely related to many other visual problems, such as instance segmentation [19], object reidentification [13], optical flow estimation [15], and object Equal contribution. Work done when Yizhuo was an intern at MSRA. tracking [5]. As these tasks share similar challenges with video object segmentation, previous efforts [29,30] attempt to transfer the modules trained for such tasks into video object segmentation pipeline. More specifically, optical flow and tracking encourage local dependencies by estimating displacements in nearby frames, while instance segmentation and object re-identification enforces global dependencies by learning invariances to large appearance changes. The integration of such modules allows a significant performance improvement in video object segmentation.
The idea of enforcing local and global dependencies has been a central topic in general semi-supervised learning [49,14] (also known as transductive inference). The basic assumptions are: 1) nearby samples tend to have the same label and 2) samples that lie on the same manifold should should have the same label. The local and global dependencies describe a sufficiently smooth affinity distribution, so that label propagation on the unlabeled data gives reliable estimates. Prior classical approaches that realize this idea include random walk [37], graph-cut [6] and spectral methods [4].
This inspires us to explore a unified approach for semisupervised video object segmentation without the integration of the modules derived from other domains. We model the local dependency through a spatial prior and a motion prior. It is based on the assumption that spatially nearby pixels are likely to have same labels and that temporally distant frames weakens the spatial continuity. On the other hand, we model the global dependency through visual appearance, which is learned by convolutional neural networks on the training data.
The inference follows the regularization framework [49] which propagates labels in the constructed spatio-temporal dependency graph. While label propagation algorithms have been explored in the recent literature for video object segmentation [41,9,22,36,34], the manner in which they learn and propagate affinity is sparse and local, i.e., learning pixel affinities either between adjacent frames or between the first frame and a distant frame. We observe that there exists much smooth unlabeled structure in a temporal volume that these methods do not exploit. This may cause failures when handling deformations and occlusions. In contrast, our label propagation approach attempts to capture all frames which span the video sequence from the first frame to the frame preceding the current frame. To limit the computational overhead, sampling is performed densely within the recent history and sparsely in the more distant history, yielding a model that accounts for object appearance variation while reducing temporal redundancy.
In its implementation, our model does not rely on any other task modules, additional datasets, nor dedicated architectural designs beyond a pretrained ResNet-50 model from the ImageNet model zoo [20]. During inference, perframe prediction involves only a feed-forward pass through the base network plus an inner product with the prediction history. Thus the inference is fast and also not affected by the number of objects. Experimentally, our model runs at a frame rate of 37 per second, achieving an overall score of 72.3% on Davis 2017 validation set, as well as 63.1% on Davis 2017 test set. Our model also achieves a competitive overall score of 67.8% on the recent Youtube-VOS validation set. Our method is competitive to current prevailing methods while being substantially simpler and faster. We hope the model can serve as a simple baseline for future works.

Related Work
We review related work on video object segmentation in the semi-supervised setting. For an overview of unsupervised and interactive video object segmentation, we refer readers to other papers [11,12,2,39,27,28].
Single frame models.
In the past few years, methods with leading performance have been based on finetuning the model on the single annotated frame and performing inference on individual test frames. These methods basically learn an objectness prior and spatial continuity without con-sidering temporal information. The convolutional neural network architecture plays an important role for finetuning on a single frame to be effective. OSVOS [7] is the pioneering work in this direction. Lucid [25] seeks to augment the data specifically for each video from only a single frame of ground truth. OnAVOS [42] mines confident regions in the testing sequence to augment the training data. The later work of OSVOS-S [31] integrates semantic information from an instance segmentation model to boost performance. PReMVOS [30], CNN-MRF [3], and DyeNet [29] also build on top of single frame models.
The effectiveness of single frame models demonstrates that optimizing a domain-specific spatial smoothness term greatly enhances performance. However, finetuning via gradient descent generally takes tens of seconds per video, which can make it impractical for many applications.

Propagation-based models.
Propagation-based methods embed image pixels into a feature space and utilize pixel similarity in the feature space to guide label propagation. In methods such as VideoMatch [22,9], only pixels in the first frame are used for reference in computing pixel similarity. Since no finetuning at run time is involved, propagation-based models run much faster than the aforementioned single frame models, but the lack of domainspecific finetuning leads to performance that is much worse. Later works [36,45,34,41] explore adding the preceding frame to the first frame as reference, which significantly improves performance and leads to greater temporal smoothness. However, this local and sparse propagation scheme suffers from the drifting problem [16].
Long-range spatio-temporal models. There are two lines of work which attempt to optimize over a dense long-range spatio-temporal volume. The first [45,21] builds a recurrent neural network which uses the estimate from the previous frame to predict the object segmentation in the current frame. The whole model is learned via backpropagation through time. However, such models are sensitive to estimation errors in the previous frame.
The second direction is based on graphical models [17,38,26,48,8,32] (i.e., Markov Random Fields) defined over the spatio-temporal domain. These works were popular prior to deep learning, and employed edge potentials defined by handcrafted features such as SIFT. The models are computationally expensive and no longer competitive to learning-based methods.
Relation to other vision problems. As the above methods suggest, video object segmentation is closely related to a variety of computer vision problems such as instance segmentation, object re-identification, and optical flow estimation and tracking. Many recent methods integrate components for these other tasks into the video object segmentation pipeline. For example, OSVOS-S [31] includes a instance segmentation module; PReMVOS [30] and DyeNet [29] incorporate a object re-identification module; CNN-MRF [3], MaskTrack [34] and MaskRNN [21] rely on optical flow estimation. The integration of other modules heavily depends on transfer learning from other datasets. Though performance improvement is observed, it usually involves further complications. For example, instance segmentation becomes less useful when the video encounters a new object category which is not present in instance segmentation model. Optical flow [15] suffers from occlusions which would mislead label propagation.

Most relevant works.
Space-time memory network (STM) [33] is a significant work and most similar with ours. Ours is developed independently from STM, while STM is published earlier than ours. The insight that exploiting dense long-term information is similar. However, the transductive framework in the proposed approach, which stems from the classical semi-supervised learning, brings theoretical foundations to video object segmentation. Moreover, in the implementation, ours is much simpler and more efficient which does not require additional datasets, and infers all objects simultaneously.

Approach
In contrast to much prior work on finetuning a model on a single annotated frame or transferring knowledge from other related tasks, our approach focuses on fully exploiting the unlabeled structure in a video sequence. This enables us to build a simple model that is both strong in performance and fast in inference.
We first describe a generic semi-supervised classification framework [49] and then adapt it to online video object segmentation in a manner that follows our ideas.

A Transductive Inference Framework
Let us first consider a general semi-supervised classification problem. Suppose that we have a dataset D = {(x 1 , y 1 ), (x 2 , y 2 ), (x l , y l ), x l+1 , ..., x n }, which contains l labeled data pairs and n − l unlabeled data points. The task is to infer the labels {ŷ i } n i=l+1 for the unlabeled data {x l+1 , ..., x n } based on all the observation D. Inference of the unlabeled data is formulated in prior work [49] as a transductive regularization framework, where w ij encodes the similarity between data points (x i , x j ), and d i denotes the degree d i = j w ij for pixel i. The first term is a smoothness constraint that enforces similar points to have identical labels. The second term is a fitting constraint, which penalizes solutions that deviate from the initial observations. The parameter µ balances these two terms. Semi-supervised classification amounts to solve the following optimization problem, It is shown [49] that the above energy minimization problem can be solved by iterative algorithm as follows. Let S = D −1/2 WD −1/2 be the normalized similarity matrix constructed from w ij . Iteratively solve forŷ(k) until convergence, as 1 where α = µ/(µ + 1), and y(0) = [y 1 , y 2 , ..., y n ] T is the initial observation of the label clamped with supervised labels. The typical value of α is 0.99. The power of this transduction model comes from the globalized model it builds over the dense structures in the unlabeled data.

Online Video Object Segmentation
Based on this general framework [49], we build a transductive model for semi-supervised video object segmentation that accounts for dense long-range interactions.
This gives rise to three challenges. First, video frames stream sequentially, so the model must work in an online fashion, where the inference of one frame should not depend on future frames. Second, the number of pixels in one video can scale into the tens of millions. A similarity matrix over all the pixels would thus be intractable to compute. Third, an effective similarity measure W needs to be learned between pixels in a video sequence.
For the algorithm to run online, it is assumed that the predictions on all prior frames have been determined when the current frame t arrives. We therefore approximate the Eqn 3 by expanding the inference procedure through time, S 1:t→t+1 represents the similarity matrix S that is only constructed between pixels up to the t-th frame and the pixels in the t + 1-th frame. Since no labels are provided beyond the first frame, the prior term y(0) is omitted for the frame t + 1. For time t+1, the above propagation procedure is equivantly minimizing a set of smoothness terms in the spatiotemporal volume, where i indexes the pixels at the target time t + 1, j indexes the pixels in all frames prior to and including time t.

Label Propagation
Given the annotations on the starting frame of a video, we process the remaining frames sequentially, propagating labels to each frame based on Eqn. 4. The quality of video object segmentation heavily depends on the similarity metric S, whose core component is the the affinity matrix W. 1 Note that there exists a closed-form solution to the Eqn 2 shown in [49]. However, this requires the inverse of matrix S which is often computationally demanding when S is a large matrix. Similarity metric. In order to build a smooth classification function, the similarity metric should account for global high-level semantics and local low-level spatial continuity. Our similarity measure w ij includes an appearance term and a spatial term, where f i , f j are the feature embeddings for pixels p i , p j through a convolutional neural network. loc(i) is the spatial location of pixel i. The spatial term is controlled by a locality parameter σ. Learning of the appearance model is described in the next section.

Frame sampling.
Computing a similarity matrix S over all the previous frames is computationally infeasible, as long videos can span hundreds of frames or more. Inspired by Temporal Segment Networks [43], we sample a small number of frames in the observance of the temporal redundancy in videos.
Specifically, as in Figure 3, we sample a total of 9 frames from the preceding 40 frames: the 4 consecutive frames before the target frame to model the local motion, and 5 more frames sparsely sampled from the remaining 36 frames to model long-term interactions. We find this sampling strategy to strike a good balance between efficiency and effectiveness. Detailed ablations about the choice of frame sampling are presented in the experiments.
A simple motion prior. Pixels that are more distant in the temporal domain have weaker spatial dependencies. To integrate this knowledge, we use a simple motion prior where a smaller σ = 8 is used when the temporal references are sampled locally and densely, and a larger σ = 21 is employed when the reference frames are distant. We find this simple motion model to be effective for finding longterm dependencies.

Learning the appearance embedding
We learn the appearance embedding in a data-driven fashion using a 2D convolutional neural network. The embedding aims to capture both short-term and long-term variations due to motion, scale and deformations. The embedding is learned from the training data in which each frame from the video is annotated with the segmented object and the object identity.
Given a target pixel x i and we consider all pixels in the prior frames as references. Denote f i and f j the feature embeddings for pixel x i and a reference pixel x j . Then the predicted labelŷ i of x i is given bŷ where the reference indexes j, k span the temporal history before the current frame. We show detailed ablations on how sampling the historical frames affects the learning quality. We optimize the embedding via a standard cross-entropy loss on all pixels in the target frame,

Implementation Details
We use a ResNet-50 to train the embedding model. The convolution stride of the third and the fourth residual blocks is set to 1 to maintain a high-resolution output. We add one additional 1 × 1 convolutional layer to project the feature to a final embedding of 256 dimensions. The embedding model produces a feature with a total stride of 8.
During training, we take the pretrained weights from the ImageNet model zoo, and finetune the model on the Davis 2017 [35] training set for 240 epochs and Youtube-VOS [46] for 30 epochs. We apply the standard augmentations of random flipping and random cropping of size 256 × 256 on the input images. We use a SGD solver with an initial learning rate of 0.02 and a cosine annealing scheduler. The optimization takes 16 hours on 4 Tesla P100 GPUs, with a batch size of 16, each containing 10 snippets from a video sequence.

Without Motion
With Motion Figure 4: The effect of our simple motion model. Distant frames have weaker spatial priors on the location of objects, thus reducing the drifting problem.
During tracking, we extract features at the original image resolution of 480p. The results of each video frame are predicted sequentially online.

Results
In this section, we first describe our experimental settings and datasets. Then we show detailed ablations on how the transductive approach takes advantage of unlabeled structures in the temporal sequence to significantly improve the performance. Results are conducted on various datasets to compare with the state-of-the-art. Finally, we discuss temporal stability and the relationship to optical flow. Our method is abbreviated as TVOS in the result tables.

Experimental Setup
Datasets. We evaluate our method on the Davis 2017 [35], and Youtube-VOS [46] datasets. Our model is trained on the respective training set and evaluated on the validation set. For Davis 2017, we also train our model on the combined train-val set, and submit the results on the testing set on the evaluation server.
Davis 2017 contains 150 video sequences and it involves multiple objects with drastic deformations, heavy and prolonged occlusions, and very fast motions. High-definition annotations are available for all frames in the training sequences. Youtube-VOS is the largest dataset for this task to-date, containing 4453 training sequences and 474 validation sequences. It captures a comprehensive collection of 94 daily object categories. However, the frame rate of the video is much lower than videos in Davis (5 fps compared to 24 fps).
Evaluation metrics. We use the standard evaluation metric of mean intersection over union (mIoU), averaged across objects and summed over all frames. The mIoU is evaluated on both the full objects (J measure) and only on the object boundaries (F measure). The global metric (G measure) is the average of the J and F measures. Youtube-   VOS also includes a separate measure of seen objects and unseen objects to measure the generalization ability. In Section 4.4, we provide a discussion of temporal stability.

Ablation Study
Dense local and global dependencies. While most prior works focus on optimizing single frame models, the key idea of this paper is to build dense long-term models over the spatio-temporal volume. In Table 2, we summarize the effect of such long-term potentials which capture both local and global dependency. Each row is an appearance embedding model trained with different reference frame sampling strategies. Each column corresponds to a tracking sampling strategy. We study the following settings: one reference frame preceding the target frame, 3 consecutive frames preceding the target frame, 9 consecutive frames preceding the target frame, uniform sampling of 9 frames in the preceding 40 frames, and our sparse sampling of 9 frames in the preceding 40 frames as in Figure 3. We find that tracking over a longer term generally improves the performance, and denser sampling near the target frame is helpful. For learning the appearance embedding, training with 9 consecutive frames produces the best results, while longer ranges do not always lead to improvements. This may be due to very long ranges covering almost the entire video reduces the variations in the dataset, which leads to worse generalization for training.
In Figure 5, we show some qualitative examples for long range tracking. Using 9 consecutive frames yields more stable predictions than using only the previous frame. Adding the spatial term smooths the object boundaries. A long range of 40 frames enables the model to re-detect objects after heavy occlusions.
Transferred representations. In the last rows of Table 2, we also test the tracking performance for models pretrained on ImageNet but without further training on the DAVIS dataset. The transferred ImageNet model obtains a mean J measure of 54.8%, which is actually better than some prior methods [47,10] trained with additional Davis data. Also, even an unsupervised pretrained model on images obtains performance competitive to network modulation [47] using our transductive inference algorithm. Two recent unsupervised pretrained models on ImageNet are investigated [44,18]. Since no domain-specific training is involved for the appearance embedding, the evaluation of transferred representations clearly validates the effective-Methods FT J F J &F Speed OnAVOS [42] 61.0 66.1 63.6 0.08 DyeNet [29] 67.3 71.0 69.1 0.43 CNN-MRF [3] 67.2 74.2 70.7 0.03 PReMVOS [30] 73.9 81.7 77.8 0.03 Modulation [47] 52.  ness of dense long-term modeling. The simple motion prior. As a weak spatial prior for modeling the dependency between distant frames, our simple motion model reduces noise from the model predictions and leads to about 1% improvement. Figure 4 displays two concrete examples. More complicated motion models, such as a linear motion model [1], may be even more effective.

Quantitative Results
In Table 1, we first give a brief overview of the current leading methods, including those that use first-frame finetuning (CNN-MRF [3], DyeNet [29], PReMVOS [30]) and those that do not (FEELVOS [41], STM [33] and our TVOS). For DyeNet and PReMVOS, their sub-modules are learned on dedicated datasets such as optical flow on Flying Chairs, object proposal on MSCOCO, and object segmentation on PASCAL VOC. Since Davis is much smaller than the large-scale datasets, it remains unknown how much of the gains can be attributed to knowledge transfer or to the methods themselves. Therefore, the mentioned methods are not directly comparable with our method. FEELVOS, STM and ours are much simpler, as they do not rely on additional modules for this problem. STM additionally requires heavy pretraining on large-scale image datasets.
It is also important to note that for PreMVOS, DyeNet, CNN-MRF, they are not able to run tracking in an online fashion. They use information from future frames to stabilize prediction for the target frame. Also, instead of using the first frame from the given video for training, they use the first frames from the entire test-dev set for training. Propagation-based methods are able to track objects sequentially online.
DAVIS 2017. We summarize our results on the Davis 2017 validation set in Table 3, and on the Davis 2017 testdev set in Table 4. On the validation set, our method performs slightly better than STM [33]    of training data, while surpassing other propagation-based methods which do not need fine-tuning, by 4% for mean J and 3% for mean J&F . In comparison to finetuning based methods, our TVOS also outperforms DyeNet and CNN-MRF by 2% while being significantly simpler and faster. We train our model on the combined training and validation set for evaluating on the test-dev set. We find that there is a large gap of distribution between the Davis 2017 test-dev and validation sets. Heavy and prolonged occlusions among objects belonging to the same category are more frequent in the test-dev, which favors methods with re-identification modules. As a result, we are 4 − 5% lower than DyeNet and CNN-MRF on the test-dev set. FEELVOS is even more negatively affected, performing 8% lower than ours in terms of mean J&F . STM [33] does not provide an evaluation on the test set.
Youtube-VOS. We summarize the results on youtube-VOS validation set in Table 5. Ours surpasses all prior works except STM [33], which relies on heavy pretraining on a variety of segmentation datasets such as saliency detection and instance segmentation. Without pretraining, STM obtains a comparable result of 68.1%. We also test the generalization ability of our model trained on DAVIS train-val and test on Youtube-VOS val. The transferred model shows great generalization ability with an overall score of 67.4% Speed analysis. During tracking, we cache the appearance embeddings for a history up to 40 frames. Inference  per frame thus only involves a feed-forward pass of the target frame through the base network, and an additional dot product of target embeddings to prior embeddings. Computation is also constant of any number of objects. This makes our algorithm extremely fast, with a runtime of 37 frames per second on a single Titan Xp GPU. Figure 1 compares current algorithms on their trade-off between speed and performance. Ours is an order of magnitude faster than prior methods, while achieving the results comparable to stateof-the-art methods.

Discussions
Temporal stability. Temporal stability is often a desirable property in video object segmentation, as sharp inconsistencies may be disruptive to downstream video analysis. However, temporal stability is typically not included as an evaluation criterion. Here, we give qualitative examples showing the difference in temporal stability between our model and the state-of-the-art PreMVOS [30].
In Figure 6, we show examples of per-frame evaluation along video sequences. Although the state-of-the-art integrates various temporal smoothing modules, such as opti-cal flow, merging and tracking, we observe the detectionbased method to be prone to noise. For example, objects are lost suddenly, or being tagged with a different identity. Our method, on the other hand, makes temporally consistent predictions.
Does our model learn optical flow? Our method learns a soft mechanism for associating pixels in the target frame with pixels in the history frames. This is similar to optical flow where hard correspondences are computed between pixels. We examine how much our learned model aligns with optical flow.
We take two adjacent two frames and calculate the optical flow from our model as ∆d i = j s ij ∆d ij , where s ij is the normalized similarity, and ∆d ij is the displacement between i, j. Figure 7 shows an example visualization of the flow. Compared to the optical flow computed by FlowNet2 [23], our flow makes sense on objects that would be segmented, but is much more noisy on the background. We have further added a spatial smoothness constraint on the computed optical flow for jointly learning the embeddings, as widely used for optical flow estimation [15,24]. We observe that the constraint smooths the optical flow on the background, but fails to regularize the model for tracking. Adding the term consistently hurts the performance of video object segmentation.

Conclusion
We present a simple approach to semi-supervised video object segmentation. Our main insight is that much more unlabeled structure in the spatio-temporal volume can be exploited for video object segmentation. Our model finds such structure via transductive inference. The approach is learned end-to-end, without the need of additional modules, additional datasets, or dedicated architectural designs. Our vanilla ResNet50 model achieves competitive performance with a compelling speed of 37 frames per second. We hope our model can serve as a solid baseline for future research.