Deep Learning Techniques for Video Instance Segmentation: A Survey

Video segmentation aims to isolate and identify elements within a video. In particular, video segmentation encompasses several distinct tasks: video object segmentation, video semantic segmentation, and video instance segmentation, as shown in Fig. 1. To help readers better grasp the extent of this survey, this section elaborates and compares these tasks. It is also important to note the difference between ”objects” and ”instances”. An object in the context of VIS refers to a general category of items in a video frame (e.g., in a street scene, the objects could be pedestrians, cars, traffic signs, and buildings). An ”instance” refers to an individual occurrence of an object category. For example, if there are multiple cars in a video frame, VIS would differentiate between each individual car by assigning it a unique label. Therefore, an object category encompasses multiple instances of that class of object.

Video Object Segmentation: Video Object Segmentation (VOS) is a binary segmentation task that requires the model to segment foreground objects from the background of a video [32, 26, 19]. In other words, rather than segmenting every pixel in a frame, VOS only segments those pixels associated with the salient object. The classification results are binary, without separation of different instances of the same class of objects. VOS is the earliest video segmentation task and it serves as the basis for others.

Video Semantic Segmentation: Semantic segmentation was originally proposed for image processing, which requires the model to categorize each pixel in an image into a class [33, 34]. Later, the concept of semantic segmentation was applied to videos, known as video semantic segmentation (VSS) [35, 36]. Compared with VOS, VSS associates every pixel in a frame with one of multiple semantic categories. It is not necessary to discriminate different instances.

Video Instance Segmentation: In 2019, Yang et al. [3] introduced the VIS task, which requires the detection, segmentation, and tracking of individual instances of objects in videos. In the same year, Voigtlaender et al. [37] extended the Multi-Object Tracking (MOT) [6] to instance segmentation tracking and coined the term “Multi-Object Tracking and Segmentation” (MOTS), which is similar to VIS. The only difference between VIS and MOTS is that MOTS requires that masks do not overlap during evaluation [38]. Therefore, in this survey, the two terms, VIS and MOTS, are used interchangeably. Compared with VOS and VSS, VIS segments salient objects in each frame and allocates the results into multiple classes, while identifying and tracking individual instances.

As there are numerous deep neural networks, the most popular ones used in existing deep-learning schemes for VIS are introduced below.

Convolutional Neural Network (CNN): A CNN is a popular deep neural network that automatically extracts features from images using its convolution kernels [39, 16, 40]. CNNs are widely applied in image and video regions, such as object detection, object tracking, action recognition, etc [40].

Recurrent Neural Network (RNN): An RNN is a deep neural network designed for sequential data or time series data, as it retains context information via cycles in the network [41]. As a result, several famous RNNs, such as the Long Short-Term Memory Network (LSTM), are widely adopted in VIS schemes to learn sequential visual features frame-by-frame with the help of CNNs [42].

Graph Neural Network (GNN): A GNN is a deep neural network designed for graph data, which captures dependency relationships among nodes via message passing between the nodes of graphs and conducts node, edge, and graph level predictions [43]. In VIS, the GNN is typically used to model the relationships among instances for better instance tracking and segmentation [44].

Transformers: A Transformer is a popular deep neural network with a self-attention mechanism that enables the global perception of a long sequence of tokenized inputs by automatically amplifying the key tokens [21]. Vision Transformer (ViT) is a kind of Transformer that breaks down input images into a sequence of patches and then tokenizes them. Because of its outstanding performance, ViT is used for a growing number of computer vision tasks, such as image classification [45], object detection [46, 47], and VIS [48]. Transformer is able to detect and segment objects at the frame level following the design of DEtection TRansformer (DETR) [46]. Transformer also offers long-range dependency modeling and temporal feature linkage for better instance tracking [49].

Backbone, Neck, and Head: To complete complex tasks in computer vision, deep-learning paradigms are typically composed of multiple kinds of deep neural networks organized as backbone, neck, and head [19, 21]. In particular, a backbone is responsible for extracting features from the input, a neck aggregates and refines the features extracted by the backbone, while a head is responsible for making predictions. These concepts are carried over into the deep-learning paradigms for VIS.

Multi-stage feature processing involves multiple feature processing and transformation stages in the neck, with each stage building upon the representations learned in the previous one. Earlier stages typically capture frame-level features and propose several Regions of Interests (RoIs), while later stages aggregate features and process abstract patterns and semantic information for tasks, such as object detection, object classification, instance segmentation, and instance tracking across frames. Popular multi-stage feature processing architectures for VIS include MaskTrack R-CNN [3] and TrackR-CNN [37], which are extended from a famous image instance segmentation network Mask R-CNN [124].

When proposing the VIS task in [3], Yang et al. extended Mask R-CNN [124] to MaskTrack R-CNN by adding a post-processing stage for tracking instances across video frames. Specifically, they utilize the memory queue to store the features of previously identified instances. A tracking head is embedded into Mask R-CNN to compare the similarity between the newly detected instance and the identified instances. When introducing the MOTS task in [37], the authors proposed a TrackR-CNN network extended from Mask R-CNN [124]. In particular, the 3D-CNN is used for feature extraction [36]. On top of the feature maps, the first stage utilizes a Region Proposal Network (RPN) [125] to generate the proposal of target objects. In the second stage, several headers are used to predict the class, box, binary mask, and association vector for each RoI. The Euclidean distances between the association vectors are computed to associate the detected instances over time into tracks. As early works on VIS, MaskTrack R-CNN and TrackR-CNN [3, 37] simply extend the image instance segmentation architecture (Mask R-CNN), thus exhibiting several shortcomings, including segmentation precision, instance tracking consistency, occlusion resistance, and computational complexity. Most subsequent VIS schemes improve certain aspects and take these two schemes as benchmarks.

In terms of instance tracking, the authors of [50] utilized a CNN to extract features from multiple frames simultaneously and a Siamese network [5] with cosine similarity to track the temporal features. Theoretically, this scheme avoids using the computationally expensive 3D-CNN, thus improving computing efficiency to some extent. However, the additional overheads for getting RoI proposals from multiple frames and the ensuing feature similarity comparison increase computational complexity. Besides, the randomly sampled frames from the video sequence cannot ensure the reliability of feature comparison. Similar to [50], Porzi et al. [51] introduced a tracking head component to Mask R-CNN. The method accepts output from both the region segmentation head and the corresponding RoI features from the Feature Pyramid Network (FPN) [126]. While the method eliminates the need for memory caching for existing instances, it also limits the capability of identifying re-appearing instances. To improve the performance of instance tracking and re-identification, the authors of [52] proposed a bi-directional tracker, known as Instance-Pixel Dual-Tracker (IPDT). Based on the RoI proposals, the categories of objects are first calibrated to filter out false-positive classes within the global context of the video. Then, IPDT bidirectionally tracks instance-level and pixel-level embeddings, aiming at infusing the instance-level concept and discriminating overlapping instances. Instead of treating a video as an array of frames, in [53], the authors treat it as a tree composed of multiple tracklets in order to better track the re-appearing instances. In particular, a tracklet association algorithm, UnOVOST, was proposed based on Mask R-CNN [53]. In the first stage, segments in consecutive frames are combined into short tracklets that contain segments from the same object by using spatiotemporal consistency cues. In the second stage, these short tracklets are merged into long-term tracks using decision trees, which are pruned based on the appearance similarity. Their approach improves the performance of long-distance instance tracking. However, the computational complexity and memory overhead are relatively higher when compared with those from frame-level tracking approaches. By adopting UnOVOST, in [38], the authors obtained first place in the 2019 YouTube-VIS challenge. Apart from decision trees, researchers have employed dynamic programming to identify global optimal assignments of instances across frames [54]. A prominent advantage of these schemes is the improved understanding of instances across frames and better segmentation performance on overlaps, as compared with those from early VIS schemes MaskTrack R-CNN and TrackR-CNN.

A typical way to train a semi-supervised VIS model is to propagate masks of one or several keyframes to the entire video or video clips. As an example, a bi-directional instance segmentation method was proposed by Tran et al. in [55]. The work formulates a forward and backward propagation strategy to utilize masks in neighboring frames as references for instance segmentation at the current frame. The following year, Tran et al. introduced a multi-referenced guided instance segmentation scheme [56]. After the first round of mask propagation, reliable frames are cached in memory as references for the second round of mask propagation. However, this two-pass processing approach is inefficient for dealing with long videos. Similarly, in [57], Bertasius et al. proposed to propagate the instance features in a specific frame to the whole video clip by comparing the difference of the feature tensors, which enables a clip-level instance tracking. The approach performs better than MaskTrack R-CNN when handling overlapping instances. However, it appears to be challenging to separate dense instances in videos and identify fine-grained instance features [127], as it relies too heavily on the mask prediction of Mask R-CNN. Inspired by the findings in [128], the authors of [58] introduced a propose-reduce paradigm for semi-supervised VIS. Specifically, based on Mask R-CNN, a sequence propagation head is appended to generate instance sequence proposals based on multiple keyframes in the video. Then, redundant proposals involving the same instances are reduced through various non-maximum suppression (NMS) techniques. This propose-reduce strategy is straightforward for tracking instances in long videos. Nonetheless, it is by no means trivial to strike a good balance between computing overhead and instance tracking performance when adjusting the number of sequence proposals. A more effective keyframe selection method is required to improve performance and computational efficiency.

Instead of mask propagation, another way to train a semi-supervised VIS model is to utilize the Inter-pixel Relation Network (IRNet) [129]. IRNet is a CNN architecture built on a Class Attention Map (CAM). The CAM locates distinct instances and approximates their rough boundaries with only image-level supervision. In [59], Liu et al. adopted IRNet with optical flow to assign similar labels to pixels with similar motion. Temporal consistency is leveraged to propagate trustworthy predictions between adjacent frames, in order to recover missing instances between frames. The method is superior to other image instance segmentation schemes, however, there is still a gap in precision when compared with supervised VIS schemes. Similarly, in [60], Ruiz et al. proposed a weakly supervised learning strategy for MOTS based on gradient-weighted CAM (Grad-CAM) [130]. In essence, Grad-CAM is a class-discriminative localization technique that predicts a coarse localization heat map for the target concept. Since multi-task learning is incorporated in their scheme for predicting masks, bounding boxes, and classes simultaneously, Grad-CAM is utilized to locate the foreground mask based on the output of the classification branch.

Several studies leverage attention mechanisms to improve the detection, segmentation, and tracking capabilities of conventional multi-stage feature processing schemes. In [61], Liu et al. embedded a spatiotemporal attention network to MaskTrack R-CNN. The aim is to focus on the instances belonging to pre-defined categories by estimating the attention on two consecutive frames. In [62], Fu et al. introduced a frame-level attention module and an object-level attention module to Mask R-CNN for better RoI and object proposals. In [63], Abrantes et al. adopted the Transformer to conduct frame-level instance segmentation, followed by the temporal attention refinement of masks within tracklets. Similarly, in [64], a temporal attention module and a spatial attention module were incorporated into Mask R-CNN to refine the instance-aware representations in videos. A recurrent Transformer-based refinement strategy was used with Mask R-CNN to predict low-dimensional mask embeddings and improve performance [65]. However, such partially attention-improved schemes typically bring further complexity and computational overhead to classical multi-stage feature processing frameworks, with marginal improvement in performance. By abolishing the classical multi-stage feature-processing design, the work in [66] decoupled the VIS schemes into three sub-tasks, i.e. segmentation, tracking, and refinement, with each of them handled by a different attention module. After segmenting instances at the frame level, a cross-attention mechanism [46] is leveraged to model the inter-frame association, thus tracking instances and achieving online VIS. Besides, an offline refiner module based on Transformer is devised for exploiting the context information from the entire video to refine the output of instance tracking.

In terms of efficiency, some researchers focus on reducing the computational complexity of models for VIS so that they can be applied to vehicles and other edge devices. Dong et al. [67] introduced a lightweight VIS network, which regresses a group of fixed edge points in a polar coordinate system, rather than predicting conventional instance masks. After extracting features with the FPN, the centroid of instances is predicted based on the heat map, which is then utilized for predicting polar masks. The approach is capable of real-time tracking on mobile edge computing platforms. Another idea to improve computational efficiency is eliminating the predefined set of anchor boxes [131]. Liu et al. [68] extended FCOS [131], an anchor box-free and proposal-free object detection model, to VIS by incorporating an additional tracking head and a mask head. Target instances are dynamically divided into sub-regions based on their bounding box for fine-grained instance segmentation. The tracking head directly models object movements using object detection centers generated with FCOS to track instances. However, for these efficiency-focused methods, overcoming the occlusion and motion blur issues as well as improving segmentation precision remain challenging tasks.

The multi-branch feature processing architecture consists of multiple branches working in parallel to process different aspects or representations of the input data. The branches typically process features for different subtasks, and the outputs of these branches are often fused or combined to achieve VIS. Through multiple branches, the model can capture complementary information and learn robust and discriminative representations. In fact, multi-branch architectures typically can yield improved performance as compared to single-branch architectures, but at the expense of increased parameters and computational overhead during training and inference. Some representative studies utilizing this architecture are as follows.

The saliency map is a crucial cue for VIS to focus its search on salient regions in each frame [132, 35]. Standing on the viewpoint of two subtasks, semantic instance segmentation (SIS) and salient object segmentation (SOS), Le et al. [69] proposed a Semantic Instance - Salient Object (SISO) framework with two branches in charge of these two subtasks, respectively. In terms of semantic instance segmentation, instance masks with high confidence at each frame are propagated and integrated into instances in later frames. In terms of salient object segmentation, a 3D fully convolutional network (3D-FCN) [133] is adopted to compute salient region masks. By fusing the features from these two branches and integrating an identity-tracking module, semantic salient instances in the video are finally segmented. In [70], Lin et al. proposed a similar idea that simultaneously captures features shared by all instances (i.e., SOS) and discriminates different instances by instance-specific features (i.e. SIS). The framework consists of two branches, one of which is dedicated to an instance-agnostic module, and the other to an instance-specific module. The features from both branches are then fused by an attention-guided decoder, followed by a final prediction module. Similarly, Ge et al. [71] designed two branches based on the correlation matrix, with one generating coarse instance score maps and the other separating the foreground from the background. In [72], the authors argued that instance understanding matters in VOS and developed a two-branch network. The instance segmentation branch explores the instance features of the current frame while the VOS branch performs spatiotemporal matching with the memory bank. Despite yielding a good performance by adopting models pre-trained on public datasets, fine-tuning the models for both branches is more challenging than for multi-stage schemes. Besides, compared to single-branch approaches, multi-branch schemes typically have more parameters and lower processing efficiency.

Another method for solving VIS is assigning two branches to perform the detect and track operations, respectively. In [73], a Hybrid Task Cascade (HTC) [134] method was devised to conduct image instance segmentation, and SiamMask [135] was utilized to track objects. Two original SiamMasks are cascaded to better predict the mask of instances. However, when dealing with overlapping instances, the performance is significantly influenced by the image instance segmentation module. To deal with situations where instances vanish and then re-appear, some researchers introduce a memory bank beside the instance mask prediction branch to store representative motion patterns [74]. Before being fed to a decoder to predict the target mask, the encoded mask features in the current frame are combined with the motion pattern representations retrieved from the memory bank, which improves robustness toward occlusion and fast-moving objects. However, the performance is subject to the motion patterns learned in previous frames. The extra computational and storage overheads caused by ConvLSTM and the memory bank are also non-negligible.

As the You Only Look Once (YOLO) [136] algorithm becomes popular for object detection in images, an extended variant, named YOLACT [75, 76], demonstrated its effectiveness in VIS. The two-branch design of YOLACT for prototype mask generating and mask coefficient prediction enables efficient image-level instance segmentation. The effectiveness of YOLACT under severe occlusions was validated in [77]. Based on YOLACT, in [78, 79], the authors proposed SipMask. The model makes greater preservation of the spatial information contained within an instance by dividing mask prediction into several sub-mask predictions. In addition to image-level instance segmentation tasks, SipMask is validated as effective for VIS tasks. Although it is an efficient solution for VIS, the scheme lacks the utilization of temporal information across frames in video. An idea to improve YOLACT was proposed by adding another tracking decoder branch to produce embedding vectors for all instances [137]. Denoted as YolTrack, it improves the inference speed to a real-time level, but at the expense of accuracy and precision. Moreover, in [80], the FPN features from two adjacent frames were fused to explore temporal correlations. The approach comprises two branches of YOLACT for frame-level instance segmentation and an additional temporal branch for fusion features between two consecutive frames. Nevertheless, the approach lacks the comprehension and tracking of instances in long videos, especially when dealing with instances that disappear and re-appear. On the other hand, to improve the efficiency of YOLACT for use on edge devices, the authors of [81] proposed YolactEdge. It reduces the computational overhead on non-keyframes of the video by computing only a subset of the features.

Multi-branch design of the Siamese network [5] is naturally ideal for tracking instances across different frames by comparing their feature embeddings. To allow the tracking clues to better assist in detection, the work in [82] proposed an association module based on a Siamese network. It extracts re-identification embedding features in consecutive frames to improve segmentation in the current processing frame. In [83], a novel crossover learning scheme was devised for VIS based on the Siamese network, named CrossVIS. In particular, crossover learning enables dynamic filters to learn background-irrelevant representations of the same instance at two different frames. Based on the Siamese network, contrastive learning appears to be an efficient way to learn representations. The work in [84] made the embeddings of the same instance closer and the embeddings of different instances farther apart in the embedding space by comparing the adjacent frames. The method achieved an overall first place in the 2022 YouTube-VIS challenge [85]. Another contrastive learning-based VIS strategy proposed in [86] aimed to improve instance association accuracy. Inspired by [138], a bi-directional spatiotemporal learning scheme was introduced for training. Although the Siamese network provides efficient feature comparison for instance tracking between consecutive frames in a video, it is nevertheless challenging for these schemes to understand a long video and re-identify those vanish and re-appearing instances. To improve robustness against occlusions and reappearance, identification and association modules were leveraged to predict identification numbers and track instances [87]. The identification module detects new instances, assigns them identities, and encodes them into embeddings for further propagation across frames. With embeddings of the last frame stored, the association module effectively aids in propagating information from previous frames to the current frame. The approach obtains good performance for solving occluded VIS tasks. Subsequently, in [88], the authors proposed a grid-structured VIS model, i.e., VISOLO, based on the image instance segmentation scheme, SOLO [139, 140]. Specifically, each frame in the video is divided into uniform grids. They serve as the basic unit for creating semantic category scores and instance masks. Then, the memory-matching module, which caches feature maps of previous frames, calculates the similarity measure between grids in different frames for instance tracking. The grid-level features, in comparison with convolutional features, are easier to reuse and share across numerous modules. This allows the method to preserve a longer history of feature maps and improve robustness against occlusions and reappearance.

As Transformers arise in VIS, there are various proposed schemes that use the Siamese network to build inter-frame attention between the target frame and the referring frame. In [89], the authors introduced an intra-frame attention module with shared weight to the Siamese network for linking both instance- and pixel-level features in each frame. Besides, an inter-frame attention module is used to fuse hybrid temporal information and learn temporal consistency across frames. Similar attention-based temporal context fusion was adopted in studies reported in [90, 85, 84, 91] for inter-frame instance association. Although inter-frame attention is useful for tracking instances across different frames, it is challenging to effectively select reference keyframes in long videos in a way that reduces computational complexity while improving the accuracy of instance tracking. As a result, an inter-clip attention scheme based on Transformers was proposed in [92]. Specifically, by comparing the similarity of features of both target and referring clips, the instance sequences in the target video are learned in a few-shot manner. However, only limited evidence on the effectiveness of the method was provided.

Knowledge distillation [141] is a machine learning method that transfers knowledge from a large model (teacher) to a smaller one (student). It allows an online VIS model to learn a wealth of knowledge from an offline model for consistent instance tracking and segmentation. Kim et al. [93] proposed an offline-to-online knowledge distillation (OOKD) for VIS. The devised query filtering and association (QFA) module filters out bad queries and links the instance features between offline and online models. By encoding object-centric features from a single frame and augmenting them with long-range global context distilled from the teacher model, the model demonstrates state-of-the-art feature matching and instance tracking capabilities.

Point cloud is also an effective way to learn instance representation. In [94, 95], the authors built two 2D point clouds in two separate branches to learn features from the foreground and surrounding area. The features for segmentation, such as offset, color, category, and position, can be extracted from cloud points. However, the precision of the scheme highly relies on the number of points utilized, while the use of more points results in a significantly heavier computational burden.

Hybrid feature processing architectures integrate multi-stage and multi-branch architectures into an integrated framework. With multi-stage processing in each branch, the features are aggregated and processed at higher semantic levels, enabling better performance on each subtask. On the other hand, with multi-branch processing different subtasks of VIS, the features are learned in a robust and discriminative manner. However, hybrid architectures are typically more complex than multi-stage and multi-branch architectures, raising concerns among researchers on whether the improved performance compensates for the higher computational burden. The works discussed below are some examples of hybrid feature processing architectures characterized by a multi-branch encoder-decoder design.

Without initial masks in the first frame, the variational autoencoder was incorporated into Mask R-CNN to aid in capturing spatial and motion information shared by all instances [96]. Specifically, there is one encoder in the architecture for generating latent distribution, along with three parallel decoders assigned to three different branches. These branches are in charge of learning semantic information, providing attentive cues to reduce false negatives, and aggregating features from the encoder. However, the architecture almost doubles the complexity of the original Mask R-CNN model. Another similar work based on the encoder-decoder model is [97, 98]. Based on features from the image encoder, three decoders, spike decoder, position decoder, and appearance decoder, produce the latent distribution, offset vectors, and appearance embedding, respectively. Empirical results show that the approach outperforms MaskTrack R-CNN in AP by $3.5\%$ while being two times slower.

Considering the high annotation cost for VIS, a two-stage network was proposed in [99]. It includes a two-branch discrimination network (D-Net) for video object proposals and a two-branch target-aware tracking network (T-Net) for associating object proposals. In D-Net, one branch estimates the salient objects, whereas the other branch predicts the instance pixels. By comparing the object proposals in the current frame with historical tracking results, T-Net generates a segmentation score prediction for the target object. Although accuracy is slightly improved, the method places a large amount of computing overhead on both training and inference due to the lengthy and complex design. On the other hand, a semi-supervised framework requiring only bounding-box labels was developed in [100]. Optical flow in a branch is exploited to capture the temporal motion among instances, while depth estimation is used in another branch to provide spatial correlation between instances. A series of pseudo labels for salient instances are generated by leveraging the features from both optical flow and depth estimation branches. A bounding-box supervised puzzle solver further refines and assembles the sub-optimal masks and recovers the original instances. The method is comparable to fully supervised TrackR-CNN and MaskTrack R-CNN in performance. Nevertheless, there is still room for improvement in terms of long-video understanding and identifying re-appearing instances. Besides, it is promising to remove the reliance on bounding box labels during training.

The integrated feature processing architecture typically extracts features of all frames in a video or clip together to build a 3D spatiotemporal feature volume. By aggregating the spatiotemporal features, the model, which typically consists of an encoder-decoder design, automatically learns the high-level representations of diverse instances across time and space, followed by a final prediction. Integrated architecture offers an elegant design when compared with multi-stage and multi-branch architectures, and gains popularity as the self-attention mechanism becomes widely used. However, it usually necessitates a lengthy training process, more training data, and more computational and memory resources. The works that utilize integrated feature processing architecture are reviewed, as follows.

In 2020, Athar et al. [101] adopted an FPN to extract different scales of feature maps. The feature maps are then stacked along the temporal dimension for decoding using a 3D-CNN model. However, the performance of this method largely depends on the capability of the 3D-CNN model to build the 3D mask tube. Precisely segmenting the 3D mask tube requires large memory consumption for storing more fine-grained spatiotemporal features. In order to extract background-irrelevant features and track instances throughout the entire scene, Brasó et al. [102] constructed a graph on a set of frames with each node representing an object detection. Then, feature embeddings obtained by the CNN are propagated across the graph for several iterations using neural message passing [142] for predicting instance masks for each RoI. Although the GNN is a promising solution for learning instance association and background-irrelevant features at the video level, its computational complexity is highly sensitive to the instance density in frames and the video length.

As the self-attention mechanism of Transformers helps direct attention to the features of target instances at the image level [46], many attempts have been made to exploit this merit for 3D spatiotemporal feature extraction in VIS. In [103], Cheng et al. extended a Transformer-based image instance segmentation model, i.e., Mask2Former [143], to VIS. Masked attention is applied to the 3D spatiotemporal features for directly predicting a 3D mask for each instance across time. Choudhuri et al. [104] demonstrated that employing absolute position encoding like [103] could cause object queries to heavily rely on the positions of the instances, causing an inability to recognize instance position changes. Thus, they proposed relative object queries on relative positional encoding for the Transformer to better capture an instance’s position changes over frames. In [49], the authors extended the Transformer-based image object detection model DETR [46] to VIS. Denoted as VisTR, the method consists of an instance sequence matching module to supervise the instance sequence across frames, as well as an instance sequence segmentation module to accumulate the mask features and predict the final mask sequences. These Transformer-based schemes generate a sequence of instance predictions concurrently using all frames in a video or clip as the input, resulting in a substantial computational and memory overhead. To reduce computational and storage overhead, Hwang et al. [105] proposed a clip processing pipeline. It yields better performance over those per-frame methods and less memory usage over those per-video methods. Specifically, two Transformers are designed, one encodes each frame independently, and the other exchanges information between frames.

Note that the self-attention mechanism of Transformers typically involves explosive computations and memory overheads over the space-time inputs of the entire video, as it has quadratic complexity with respect to the input sequence [144]. Deformable attention [144] achieves smaller computational complexity than full attention, as it only pays attention to a small number of key sampling points around a reference point assigned to each query. As a result, a multi-level deformable attention scheme, named SeqFormer [106], was designed to encompass both frame- and instance-level attention queries on videos. In particular, SeqFormer first performs independent frame-level box queries using deformable attention [144]. Then, the instance query is conducted based on the features extracted by box queries on each frame, which generates the final segmentation mask sequence. Following SeqFormer [106], Zhang et al. [107] indicated the importance of multi-scale temporal information for VIS. They proposed TAFormer to incorporate both spatial and temporal multi-scale deformable attention modules in an encoder. While TAFormer performs marginally better than SeqFormer, it has more tuning parameters and computational complexity. Apart from deformable attention, the MSG-Transformer [145] is a computation-efficient variant of the self-attention mechanism in computer vision. Instead of applying full attention to images, MSG-Transformer adopts local attention to subregions, and introduces an additional messenger token to each subregion for exchanging information across different subregions. As a result, the work in [108] extended the MSG-Transformer to VIS to enable efficient computation, named TeViT. In particular, TeViT constructs patch tokens along with messenger tokens on all frames in the video, and shifts messenger tokens across the time dimension for capturing temporal contextual information. Compared with VisTR, TeViT achieves better video processing speed and instance segmentation precision. Additionally, SeaFormer [146], a lightweight ViT with squeeze-enhanced axial attention, was leveraged to produce an efficient VIS scheme for mobile devices [109]. To speed up the convergence of VisTR, EfficientVIS was proposed in [110] by leveraging the clip processing pipeline. In particular, EfficientVIS extends Sparse R-CNN [47] with self-attention to support clip-level queries and proposals. However, the performance of clip-level queries and proposals in EfficientVIS is highly subject to the precision of spatiotemporal RoI [124] on video clips. On the other hand, considering that the dense spatiotemporal features extracted from videos are the key reasons for high computational complexity, VITA [111] was formulated to extract only object-aware context through a frame-level object detector. By collecting the frame-level object tokens for the entire video, VITA builds the relationships between every detected object and achieves global video understanding. Moreover, a simple and computation-efficient Transformer-based VIS scheme, i.e., MinVIS [112], was developed. MinVIS only trains a query-based image instance segmentation model. In the post-processing step, the instances are tracked by bipartite matching of query embeddings across frames. MinVIS also supports sub-sampling the annotated frames in training videos to further improve training efficiency.

In terms of annotation-efficient VIS, based on Mask2Former [103], the work in [113] introduced MaskFreeVIS to substitute the requirement for mask annotations with bounding box annotations during the training. Specifically, BoxInst [147], a bounding-box supervised image instance segmentation approach, is extended with the Temporal KNN-patch Loss (TK-Loss). The method identifies one-to-many matches across frames through an efficient patch-matching step, followed by a K-nearest neighbor selection. Empirical studies demonstrate that MaskFreeVIS outperforms certain fully-supervised models like EfficientVIS [110].

The recurrent feature processing architecture involves recurrently extracting and processing features from frames along the temporal axes. By recurrently propagating the features of past frames to the current frame, the recurrent architecture design allows a model to track instances in videos with marginal memory overhead. In addition to RNNs, as ViT becomes prominent, some works also propagate the object queries in Transformers in this way, therefore they are included in this section. The following are some studies that utilize recurrent feature processing architectures.

The temporal dimension of videos allows features to be processed in a recurrent manner according to the temporal flow of frames. One recurrent model to process spatiotemporal features in video is ConvLSTM [148, 114]. It extends LSTM with convolutional structures to better capture spatiotemporal correlations. Specifically, Sun et al. [114] proposed a contextual pyramid ConvLSTMs to process multi-level spatiotemporal features extracted by the FPN, followed by a Mask R-CNN header [124] for predicting the instances in the next frame. The method has the benefit of being fast for real-time applications and for making fine-grained use of the features. There is another scheme, namely APANet, that improves ConvLSTM by adaptively aggregating spatiotemporal contextual information acquired at various scales to more accurately predict future frames [115]. The connections among each pair of ConvLSTM units are determined by neural architecture search (NAS). In a nutshell, these ConvLSTM-based schemes require significant memory due to many spatiotemporal features being cached, causing them to struggle to comprehend long videos.

In addition to ConvLSTM, several researchers also employed a GNN along with LSTM to propagate information for tracking [116, 117]. In particular, a graph is built on the past and current detected instances. It is then utilized to produce output embeddings for association. The embeddings are then fed to LSTM for historical information aggregating and future tracking. It is obvious that GNN aids in building better associations of instances across frames. However, the approach heavily depends on the accuracy of instance detection. A false or missed detection in specific frames may have a huge impact on the scoring of instance connections, thus affecting the tracking and segmentation of instances in a video. A similar idea of adopting GNN for VIS was proposed in [44]. Two consecutive frames, a reference frame and a target frame, are utilized to construct a graph and obtain aggregated spatiotemporal features. Without the help of ConvLSTM or LSTM, the method caches the history mask information in memory and achieves a similar effect of mask propagation.

Recently, the self-attention mechanism is being increasingly utilized to construct query-based VIS schemes [149], where query proposals are typically propagated across frames for tracking instances [104]. Meinhardt et al. [118] proposed a query-based VIS scheme, i.e., TrackFormer, based on Deformable DETR [144]. It enables the transformer to detect and track objects in videos in a frame-by-frame manner. The tracking-by-attention paradigm and the concept of auto-regressive track queries are defined. Similarly, Koner et al. [119] proposed a Transformer-based online VIS framework, denoted InstanceFormer. It incorporates a memory queue to propagate the representation, location, and semantic information of prior instances to achieve better instance tracking consistency. Considering the aforementioned methods only handle inter-frame associations, Heo et al. [120] argued that the main bottleneck in processing long videos is building inter-clip associations. As a result, they proposed a clip-level query propagation approach, i.e., GenVIS, based on VITA [111]. In particular, GenVIS stores clip-level decoded object queries in the memory. With the joint effort of decoded object queries propagated from the latest clip, GenVIS achieves state-of-the-art performance in long-distance instance tracking with a small computational overhead.

To enhance temporal consistency in query propagation across frames, the work in [121] employed additional clip-level queries for fusing information from all the frames. The scheme combines the designs of recurrent and integrated instance queries, thus improving the temporal consistency and robustness of query propagation on VIS tasks. However, the design increases computational complexity and memory overhead, and sacrifices the ability of real-time inference. Apart from introducing additional clip-level queries, caching instance features from previous frames is also helpful in improving temporal consistency. The work in [48] introduced InsPro, which propagates query-proposal pairs from the previous frame to the current frame based on a set of instance queries. By caching instance features in historical frames and calculating intra-query attention, the method takes advantage of temporal clues in videos and copes well with occlusion and motion blur. In [122], the authors constructed contrastive items and added noise to the relevant embeddings in the memory bank during training to simulate identity switching in real-world scenarios, in order to better associate instances across time. Another way to improve the temporal consistency and robustness of query propagation is to directly rectify the effect of noisy features accumulated during occlusion and abrupt changes. Hannan et al. [123] proposed Gated Residual Attention for VIS (GRAtt-VIS), which uses gate activation as a mask for self-attention. The mask restricts the unrepresentative instance queries in the self-attention and keeps crucial information for long-term tracking. Compared with [121], the approach reduces computational complexity, alleviates memory overhead, and supports online processing. However, the shortcoming appears in tracking identities pertaining to crossover trajectories.