Prototypical Cross-Attention Networks for Multiple Object Tracking and Segmentation
Authors: Lei Ke
Xia Li
Martin Danelljan
Yu-Wing Tai
Chi-Keung Tang
Fisher Yu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: multiple object tracking and segmentation
video instance segmentation
efficient cross-attention networks
space-time memory

Abstract: Multiple object tracking and segmentation requires detecting, tracking, and segmenting objects belonging to a set of given classes. Most approaches only exploit the temporal dimension to address the association problem, while relying on single frame predictions for the segmentation mask itself. We propose Prototypical Cross-Attention Network (PCAN), capable of leveraging rich spatio-temporal information for online multiple object tracking and segmentation. PCAN first distills a space-time memory into a set of prototypes and then employs cross-attention to retrieve rich information from the past frames. To segment each object, PCAN adopts a prototypical appearance module to learn a set of contrastive foreground and background prototypes, which are then propagated over time. Extensive experiments demonstrate that PCAN outperforms current video instance tracking and segmentation competition winners on both Youtube-VIS and BDD100K datasets, and shows efficacy to both one-stage and two-stage segmentation frameworks. Code and video resources are available at http://vis.xyz/pub/pcan.

Prototypical Cross-Attention Networks for Multiple Object Tracking and Segmentation
Lei Lei Kel.2
Xia Li'
Martin Danelljan'
Yu- Yu-Wing Tai Chi-Keung Tang²
Fisher Yu'
'ETH Zürich
PKKUST
SKuaishou Technology
(1keab, citan)/ ust. hk, Sxia.li,mane martin jtwp:aimaaaainaaeellaaaaaaaaaaea jamelljan) ee, www..e..ee................... ch
yuxingogmail com, i0yf.io
Abstract
Multiple object tracking and segmentation requires detecting, tracking, and seg- menting objects belonging to a set of given classes. Most approaches only exploit the temporal dimension to address the association problem, while relying on sin- gle frame predictions for the segmentation mask itself. We propose Prototypical Cross-Attention Network (PCAN), capable of leveraging rich spatio-temporal in- formation for online multiple object tracking and segmentation. PCAN first distills space-time memory into a set of prototypes and then employs cross-attention to retrieve rich information from the past frames. To segment each object, PCAN of contrastive foreground
adopts prototypical appearance module to learn and background prototypes. which are then propagated over time. Extensive exper- iments demonstrate that PCAN outperforms current video instance tracking and segmentation competition winners on both Youtube- VIS and BDD100K datasets, and shows efficacy to both one-stage and two-stage segmentation frameworks. Code and video resources are available at http: /vvi..vii//// httv/vvi.s//ppui//e
Introduction
Multiple object tracking and segmentation (MOTS), also known as Video Instance Segmentation (VIS), is important problem with many real-world applications, including autonomous driving [10, 26] and video analysis [4, 46]. The task involves tracking and segmenting all objects within a video from given set of semantic classes. We witnessing rapidly growing research interest MOTS
thanks to the introduction of large scale benchmarks [46, 50, 37J. State-of-the-art methods [46, 5, 37, 29] for MOTS mainly follow the beekiing-b--deecctinn paradigm, where objects are first detected and segmented in individual frames and then associated over time.
Although methods based the popular tracking-b--detectton by-detection philosophy have shown promising results, temporal modeling is limited to the object association phase [46, 5, 22] and only between two adjacent frames [37, 18]. On the other hand, the temporal dimension carries rich information about the scene. The information encoded in multiple temporal views an object has the potential of improving the quality of predicted segmentation, localization, and categories. However, effectively and efficiently leveraging the rich temporal information remains a challenge. While sequential modeling has been applied for video processing [40, 41, 9, 28, 12], these methods generally operate directly on the high-resolution deep features, requiring large computational and memory consumption, which greatly limits their use.
We propose Prototypical Cross-Attention Module, termed PCAM, to leverage temporal information for multiple object tracking and segmentation. As illustrated in Figure the module first distills spatio- temporal information into condensed prototypes using clustering based on Expectation Maximization. The resulting prototypes, composed of Gaussian Components, yield rich and generalizable yet compact representation of the past visual features. Given a deep feature embedding of the current
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Memory
Posales
Paspaare
Mehyarrl
III
Frame Prototypes
Instance Prototypes
Previous Frames
Protolypical Croes-Altention
Feature Extractor
Memory Altention
Classification
Dotection
Segmentation
Query
Association
Prediction
Figure 1: We propose Prototypical Cross-Attention Network for MOTS, which first condenses the space-time memory and high-resolution frame embeddings into frame-level and instance-level prototypes. These are then employed to retrieve rich temporal information from past frames by our efficient prototypical cross-attention operation.
frame, PCAM then employs prototypical cross-attention read relevant information from prior frames.
Based the noise-reduced clustered video features information, we further develop a Prototypical Cross-Attentin Network (PCAN) for MOTS, that integrates the general PCAM at two stages in the network: on the frame-level and instance-level. The former reconstructs and aligns temporal past frame features with current frame, while the instance level integrates specific information about each object in the video. For robustness object appearance change, PCAN represents each object instance by learning sets of contrastive foreground and background prototypes, which are propagated an online manner. With a limited number of prototypes for each instance or frame, PCAN efficiently performs long-range feature aggregation and propagation in video with linear complexity. Consequently, our PCAN outperforms standard non-local attention [40] and video transformer [41] on both the large-scale Youtube- VIS and BDD 100K MOTS benchmarks.
Our main contributions summarized follows: We introduce the PCAN module for efficiently utilizing long-term spatio-tempone video information. (ii) We develop a MOTS approach that employs PCAN on frame and instance-level. (iii) We further represent the appearance each video tracklet with contrastive foreground and background prototypes, which are propagated over time. (iv) We extensively analyze our approach. Our PCAN outperforms previous approaches on the challenging self-driving dataset BDD100K [50] and the semantically diverse YouTuube VIS dataset [46].
2 Related work
Video instance segmentation (VIS) Existing VIS methods [46, 2, 21] widely adapt the two- stage paradigm of Mask R-CNN [11] and its variants [13, 15] by adding an additional tracking branch. Thus, their typical pipelines first detect regions of interest (Rols) and then use the instance features after RolAlign to regress object mask and associate cross-frame instances. More recent works [5, 18, 22, 48] employ one-stage instance segmentation method, e.g. the anchor-free FCOS detector [34]. which predicts linear combination of mask bases [3] as its final segmentation. The aforementioned approaches make very limited use of temporal information to enhance the quality of the segmentation, instead relying on single image-based mask prediction, or only model short-term temporal correlation between two consecutive frames [18, 30]. In the context of long-term temporal association, the offline method VisTr [41] adapts vision transformer [6] for VIS, but suffers from a huge computational burden and memory consumption due to the dense pixel-level attention operations over long sequences. Compared to these methods, our PCAN temporally aggregates and propagates the prototypical features with both the long-term benefit and linear complexity.
Multiple Object Tracking and Segmentation (MOTS) Similar to VIS, MOTS methods [37, 27, 29] mainly follow the tracking-by-dee -eddeccctionn paradigm. Objects are first detected and segmented, followed

---

by association between frames. Track R-CNN [37] integrates temporal context feature from two neighboring frames using 3D convolutions. TrackFormer [25] performs joint object detection and tracking by recurrently using Transformers, while Stem-Seg [1] adopts short 3D convolutional spatio-temporal volume to learn pixel embedding by treating segmentation as a bottom-up grouping. In contrast, our approach clusters appearance features in long spatio-temporal volume with explicit foreground and background prototypes that are updates online. Besides, the mixture Gaussian components in instance appearance module equips PCAN stronger modeling ability compared to instance-level average pooling [33, 49] or single Gaussian model [51, 14].
Temporal attention models Video understanding usually requires long-range sequential modeling of relations between spatio-temporal locations. Recently, datention-basee approaches, such as non-local attention [40, 39, 28, 12] and transformers [8, 35, 16]. have been successfully adopted in video classification and action recognition. These tasks [23, 32, 43] involve dense pixel-level attention, leading to quadratic complexity in the sequence length, thus making them excessively expensive for long sequences. Improved temporal attention models mainly include double attention mechanism [7] on image recognition with global-local decomposition, and clustered attention Transformer [38] for language sequence modeling. Besides, recent prototypical methods [19, 45] use the EM algorithm for single-image semantic segmentation few-shot learning [33]. Unlike these methods, our PCAN
uses compact prototypical representation both for temporal feature aggregation and compact instance
appearance feature propagation.
3 Method
We propose an approach for Multiple Object Tracking and Segmentation. Given video sequence, the goal is to detect, track, and segment objects from predefined set of object categories. Specifically, we consider the online setting, where the predictions only depend on current and past frames.
3.1 Traditional Cross-Attention
To utilize the rich temporal information to improve the segmentation prediction, recent approaches [28, 12] have employed cross-attention. We consider past spatio-temporal information encoded in memory M, consisting of deep features of size x W x T x C. The memory encapsulates valuable information about the past appearances and predictions of objects and background in a scene. To attend to the memory, the information is first separately embedded into key k" and value y.M feature vectors. The keys are used to address relevant memories whose corresponding values are returned. The standard memory reading process is a non-local operation computed as the weighted sum,
1 HxWXT
Σ
exp(k? k2 >
Vi Z
where k denotes query key map, which is predicted from the current frame. Further, and j are the index of each query and the memory location, and Z, Σ, exp(k? k)") is the normalizing factor.
Although proven effective, the standard attention operation (1) is known suffer from poor computa- tional and memory scaling properties [20]. In particular, since all queries are matched to all keys, it experiences quadratic scaling ((HW) of computations in the spatial size HW of the feature map. This is particularly problematic for segmentation tasks, where fine- the-grained high-resolution information desired to improve the quality of the predictions.
3.2 Prototypical Cross-Attention
To address the aforementioned limitations of the standard cross-attention, we introduce the proto- typical cross-attention to first condense sets of high-resolution feature vectors in the past frames. Our approach is based on a clustered memory M.. We call these clusters prototypes, since they correspond representative items in the memory. While clustering effectively reduces the number of items in the memory, it also serves to deprecate noisy information, leading to a more generalizable and robust representation of the memory.
To employ an attention mechanism, similar to (1), we require a clustering of the memory that generates principled continuous and differentiable clustering assignment function. We therefore
3

---

Cross-atteation
Reconsinuttd Framc Fouture Yt
protelypes
protetypes
Attention Sum
N
Pioel-level embedaing 6(O)
Multi-l evel Temponil
Appregation
Openiiio
Assignment Probubiiity
MXW
y;
Claseriiation
K-1
Key enbeldinn k
Value embedding iy
Key enbbelding
Value endoalding
Detection
Memary M
Scymenmation
Cocvs
Concs
CHANWW
Hacdboes RTS
Memory
Current Frame Feature
Current
Figure 2: Overview of our frame-level prototypical cross-attention. For a frame i in the memory we first perform GMM-based clustering achieve the key ky and value V prototypes. Given the key encoding k, of the current frame, we attend to the prototypes to generate the reconstructed feature yı- which are then aggregated temporally and fused with the current value encoding Vt.
cluster the keys in the memory by fitting a Gaussian Mixture Model (GMM),
exp (-
p(k)
N 2 pkk j).
pkk=== = (2TO²)
2 | - kg
(2)
Here, N denotes the number of Gaussian mixtures, D) is the feature dimension of the keys. We use constant variance parameter o² and uniform cluster priors p(= =j) t. where denotes the latent cluster assignment variable. The component means k" represent the prototype keys in the memory. We generate the clustering (2) using the standard Dnnectation-Maximizzale
algorithm.
The GMM allows to compute soft cluster assignment by evaluating the posterior probability of the latent assignment variable z. Using Bayes rule, the probability of a key value k to be assigned to the jth prototype derived as,
p(= j(k) = =
exp
23
k
E p(k|2 l)p(z =)) E exp
2 k
k(ll))
The resulting cluster assignment thus be written SoftMax operation, where the corresponding logits are provided by the negative cluster distance | - kj I|² scaled with temperature of 20
Since the clustering is performed in the key space of the memory, we next retrieve the corresponding value prototypes. To this end, we employ the key cluster assignment probabilities in (3) to compute the values for each memory prototype,
HxW Σ p(== M
For attending to our clustered memory, we first predict the key encodings k0 of the query image. We then read from the clustered memory by computing the average over the value prototypes v. weighted with the cluster assignment probabilities.
N
Σ p(= p(==
1
Σ exp
1
kg v4.
(5)
Z,
202
The final attention operation has much similarity with the original dot- cross attention (1). Note that the key-query similarity in our approach is measured by Euclidian distance instead of dot-product. Importantly, our formulation (5) attends to reduced of N prototypes, while the
original attention (I) requires attending to the full spatio-temporal memory of size H x W x T.

---

3.3 Prototypical Cross-Attention Network
Here, we propose the Prototypical Cross-Attention Network (PCAN) for MOTS by integrating our prototypical cross-attention module into both the frame-level and instance-level. The former aims to align and aggregate temporal frame features stored in memory, while the latter is for propagating the instance appearance features over time and produce instance cross- attentonnn maps to help segmentation. Besides, we also design a prototypical instance appearance module to represent each video tracklet with contrastive mixture foreground and background prototypes.
3.3.1 Frame-level Prototypical Cross-Attention
In Figure 2, prototypical cross-attention first produces prototypes by fitting a Gaussian mixtures model (2) to the feature in the memory. To provide further flexibility when dynamically updating the memory M, we first perform frame-wise clustering for each reference frame feature at index to compute the N key prototypes 1- and retrieve the corresponding value embeddings {v J=1
using (4) for each memory frame independently. The key and value features are predicted using two parallel convolutional layers.
Frame-wise prototypical memory attention Given the query key encoding ky of the current frame 4, we perform prototypical cross-attention to each memory frame independently using our formulation (3) as,
Yu
1 Zí
exp (T20 IKk -
20
v
Z
exp
20
k
KHIP) (6)
Note that the index refers to a spatial coordinate in the current frame. The resulting feature map Yi can intuitively be seen as a projection of features from frame to the current frame. This projection essentially aligns the condensed feature information in frame with the current frame.
Temporal feature aggregation Since frame-wise attention does not fuse temporal information, we perform a temporal aggregation. The temporal information y; in (6) from different frames are fused linear combination, weighted by the feature similarity with the current frame. Specifically, the temporally aggregated representation is obtained as
exp(yss Yi.)
wHy
WA
exply= Yos)
i=1
Note that f = t in the sum refers to the value embedding ya vi extracted from the current frame. The contribution of each frame i is thus weighted by the similarity to this current frame prediction using the attention weights wi. This strategy ensures that incorrect or dissimilar regions suppressed when computing the final aggregated feature embedding yt. To handle object with large-scale variation and produce more fine- -reggiiieed instance mask prediction, we further extend temporal aggregation multi-level using different levels of the extracted FPN features, as detailed in the supplementary material.
3.3.2 Instance-level Prototypical Cross-Attention
Contrastive foreground and background representation In additional to the condensed frame-level representation, for more accurate segmentation results, we further encode each tracked object with compact and robust appearance prototypes. To further empower our proposed attention mechanism, we utilize the initially detected object mask to identify each foreground instance. We then separately model the extracted foreground and background features using GMM (2). We denote the resulting foreground prototypes as k,, and background prototypes as kzj. The former thus focuses on the appearance of the specific object, creating rich and dynamic appearance model. When employed in our prototypical cross- cross-attention framework (Section 3.2), it provides tne-grained attention from localized prototypes that naturally learn to focus specific parts of views of the object, as visualized in Fig. 3. Furthermore, the background prototypes k,,, capture valuable information about the background appearance, which can greatly alleviate the segmentation process. For each object instance attend to the foreground and background prototypes separately using (3). The results
5

---

Thee?
Manorid Franc Exbeidis
[-T
Maneril Frans Endochdnn
Canas Frazse Entosking
|
Peadive
Negalive
FSM
Ineticce Attrnszn
Trregrenn
Backggeandd
Faceurazal
Hadkgpordd
Toregrend
Backymerd
Fiaal Madi Profiction
Figure 3: Our instance-level prototypical attention with foreground and background prototypes and temporal propagation. The foreground/backgrounn attention maps from (bottom) demonstrate the localized and discriminative appearance representation. Temporal Segmentation Module (TSM) takes the current frame, initial mask, and instance attention maps as input and generates the final mask.
concatenated together with the initial mask detection to the Temporal Segmentation Head (TSM) for final prediction, as illustrated in Figure
Tracklet feature propagation and updating To effectively model the object appearance change and preserve the most relevant information, we design a recurrent instance appearance updating scheme. From the first video frame where object appears, the accumulated prototypes k kú, for the instance are propagated the subsequent frames and updated with new appearance prototypes k,j. k,, using an update rate À as,
kij - A)K[-1.5 + Akit.
kiy = (1 A)Kī-15 + Akij.
(8)
Figure also reveals the consistency of the attended region of specific prototype j.
4 Experiments
Here, we present comprehensive evaluation and analysis of our approach. Experiments performed on two large scale datasets, namely YouTube- VIS [46] and BDD100K [50].
4.1 Experiment setup
Youtube-VIS YouTube- VIS-2019 [46] dataset contains 2,883 high quality videos with 131k anno- tated object instances belonging to 40 diverse categories. The task is simultancously classifying, segment and track object instances belonging to these categories. The evaluation metrics for this task are adaptation of the Average Precision (AP) and Average Recall (AR) of image instance segmentation.
BDD100K We also evaluate the large-scale tracking and segmentation dataset of BDD100K [50], which is a challenging self-driving dataset with 154 videos (30,817 images) for training. 32 videos (6,475 images) for validation, and 37 videos (7, 17484 images) for testing. The dataset provides 8 annotated categories for evaluation, where the images in the tracking set are annotated per 5 FPS with 30 FPS frame rate. We adopt the well-established MOTS metrics [37] to our task.
Implementation details We implement PCAN based on two different existing MOTS approaches. For Youtube-VIS we adopt ResNet with FPN pre-trained on COCO as the backbone, and build our segmentation tracker on the one-stage segmentation model [5]. Both the instance and frame cross-attention is built on the extracted FPN features. Our model is trained with initial learning rate 0.0025 on 4 GPUs using SGD, and executes with speed of 15.0 FPS on ResNet-50. Similar to [46, 22, 18], we use the input size x60x640 for training. On BDD100K, we build PCAN by extending the two-stage MOT method [29] with our temporal segmentation modules. We follow the same training strategy of QDTrack-mots [29]. More details can be found in supplemental material.

---

Table Comparison with state-of-the-an on the YouTube- VIS validation set. Results are reported in terms of mask accuracy (AP) and recall (AR), Asterisks denote concurrent works on arXiv.
Method
Backbone
Type
Online
AP
APso
AP7s
AR1
AR10
VisTr" [41]
ResNet-50
Transformer
35.6
56.8
37.0
35.2
40.2
OSMN [47]
ResNet-50
Two-stage
23.4
36.5
25.7
28.9
31.1
FEELVOS [36]
ResNet-50
Two-stage
26.9
42.0
29.7
29.9
33.4
SERT [42]
ResNet-50
Two-stage
26.1
42,9
26.
27.8
31.3
WaskTrack R-CNN [46]
ResNet-50
Two-stage
30.3
51.1
32.6
31.0
35.5
STEm-Seg [1]
ResNet-50
One-stage
x
30.6
50.7
33.5
31.6
37.1
SipMask [S]
ResNct-50
One-stage
V
32.5
53.0
33.3
33.5
38.9
STMask [18]
ResNet-50
One-stage
33.5
52.1
36.9
31.1
39.2
SG-Nct" [22]
ResNct-50
One-stage
34.8
56.1
36.8
35.8
40.8
PCAN (Ours)
ResNet-50
One-stage
36.1
54.9
39.4
36.3
41.6
STMask [18]
ResNet-101
One-stage
36.3
55,2
39.9
33.7
42.0
SG-Net" [22]
ResNet-101
One-stage
36.3
57.1
39.6
35.9
43.0
PCAN (Ours)
ResNet-101
One-stage
37.6
57.2
41.3
37.2
43.9
Table 2: State-of-the-art comparison on the BDD100K segmentation tracking validation set. I: ImageNet. C: COCO. S: Cityscapes. B: BDD100K. "-fix" means adopting the pretrained model from the BDD100K tracking set, fixing the existing parts, and only training the added mask head.
Method
Pretrained
Online
mMOTSAf
mMOTSP1
mIDFt
ID sw.
mAPt
SortloU
I, I.C.S
10.3
59.9
21.8
15951
22.2
MaskTrackRCNN [36]
I,C,
12.3
59.9
26.2
9116
22.0
STEm-Seg [1]
I,C,
x
12.2
58.2
25.4
8732
21.8
QDTrack-mots [29]
I,C,
V
22.5
59.6
40.8
1340
22,4
QDTrack-mots-fix [29]
B,
V
23.5
66.3
44.5
973
25.5
PCAN (Ours)
I, B
27.4
66.7
45.1
876
26.6
4.2
State-of-the-Art Comparison
We compare approach with the state-of-the-art methods the aforementioned large-scale MOTS/VIS benchmarks Youtube-Ve VIS and BDDI00K, where PCAN outperforms all existing meth- ods without bells and whistles, and shows efficacy both one-stage and two-stage segmentation frameworks, We follow the official metrics of each benchmark to evaluate our model.
Youtube-VIS VIS The results of Youtube-VIS benchmark is in Table where PCAN achieves the best mask AP of 36.1% 6% using ResNet-50 and 37.6% using ResNet- 101 respectively, while being an online method. Our approach consistently surpasses most recent SOTA methods, including STMask [18] and SG-Net [22] by significant margin. These methods only conduct temporal modeling between two adjacent frames for feature correlation. Compared to baseline SipMask [5], single-image based segmentation with object centerness association, PCAN improves the mask AP from 32.5% to 36. 1,, which shows the effectiveness long-term temporal modeling in helping object tracking and segmentation.
BDD100K Table 2 shows our results BDDI00K tracking and segmentation benchmark, where PCAN outperforms the strong baseline methods MaskTrackRCNN [46] and QDTrack-mots [29]. Our approach achieves large advantage in mMOTSA. with over points gain and around 10% ID switches decrease. MOTSA measures segmentation as well as tracking quality, while ID Switches measure the performance of identity consistency. The significant adyancements demonstrate that our method with prototypical cross-attention enables more accurate pixel-wise object tracking by effectively exploiting temporal information.
4.3 Ablation study and analysis
We conduct detailed ablation studies on Youtube- VIS validation set, where we investigate the effect of our proposed prototypical cross-attention components for MOTS during training and testing.
Effect of frame-level prototypical cross-attention module study the importance of temporal information amount, conduct ablation study models with different input temporal window

---

Table 3: Results of varying temporal memory
Table 4: Effect of multi-layer prototypical fea- ture fusion with tube length 4 on You YouTube- VIS.
length in our PCAN on YouTube VIS.
Length
AP
AP
APTs
AR
AR
FPN Layer
AP
AP
AP7s
AR1
AR10
32.5
53.0
33.3
33.5
38.9
P3
30.8
$1.7
32.0
32.6
37.0
2
33.7
53.8
35.3
33,9
39,5
P4
32.0
51.5
34.1
32.6
37.2
4
33.9
54,0
36.8
34.1
40.0
P5
32.9
52.1
35.9
33.2
38.6
34.2
53.7
37.6
34.4
40.3
P3-P4
33.1
52.3
35.6
33.6
38.5
16
34.6
53.7
38.3
40.5
P3-P5
33,9
54.0
36.8
34.1
40.0
32
35.4
53.8
39.1
35.9
41.0
Table 5: Comparison with non-local attention [39] and transformer [6, 41] on YouTube-VIS,
Prototypical Cros-Attention
Non-local Attention
Transformer (Multi-Head Self-Attention
Length
AP
FLOPP(B) Memory(M)
FL.OP((B)
Memory(M)
FLOPs(B)
Memory(M)
33.7
5.8
323
33.2
24.3
2497
24.6
103.8
5321
33.9
12.0
652
33.3
49.1
4763
25.8
387.2
9844
34.2
23.7
1419
33.6
99.6
9631
28.3
1413.3
18762
vlo Irame
PCAM
We franne
PCAM
wio Instoncc
PCAM
We instance
PCAM
Figure Qualitative impact of our PCAM on YouTube- -IS.. Mask colors encode object identity. Our frame-level PCAM (second row) helps provide consistent detections and preserve identities compared to the baseline (first row). The instance-level PCAM (fourth row) provides more accurate masks, while further improving identity consistency compared to not employing our module (third row).
lengths in Table 3. A temporal length of 1 thus means that no prior temporal information guidance is used during video instance segmentation. By varying the frame length from to 32, the mask AP increases from 32.5% 35.4%, which reveals that richer temporal information with multiple views of segmented object indeed brings more gain to model performance. For the number of frame-level prototypes, we used 64 during training and testing. The results on YouTube- VIS in Table show that the precision saturates for larger numbers of prototypes.
Effect of multi-layer temporal aggregation Since perform temporal feature aggregation the extracted FPN features, to help deal with objects with partial occlusion and large-scale variation, we also study the effect of using different levels of the extracted FPN features. In Table 4, select the FPN feature map from P3-P5 layers for (excluding P6 and P7 due to impractical computation cost), and perform prototypical temporal aggregation each FPN layer. We find that multi-layer information also important to final model performance.
Computation and memory efficiency In Table 5 analyze different attention mechanisms. Compared to standard space-time memory reading using non-local attention [39, 28] or recent popular transformer [41, 6] with multi-head self-attention layer, the prototypical cross-attention with condensed prototypes not only enjoys high accuracy advantage, but also largely reduces the memory consumption and computation amount. For input tube length the prototypical memory consumption less than 10% the transformer with negligible FLOPs computation due to the small number of representative prototypes in (5).
Effect instance-level prototypical appearance module We analyze the instance-level prototypical cross-attention module, which represents each video tracklet using the contrastive prototypes. In

---

Table Ablation study on number of instance- level prototypes on YouTube-VIL
Table 7: Ablation on instance-level EM feature propagation and updating on YouTube VIS.
Pos. Proto. Number
Neg. Proto. Number
AP
APsc
version
AP
so
32.5
53.0
32.4
52.3
No instance prototype propagation
33.5
53.2
32.1
52.4
Using initial instance prototype
33.0
52.8
Update momentum 0.2
34.3
53,8
5
33.1
52.6
Update momentum 0.5
34.0
53.6
54.1
50
33.6
53.8
Table Ablation on number of frame- level prototypes on YouTube- VIS.
Table Results of varying EM iterations for our PCAN on YouTube- VIS.
Proto. Number
APs0
Iteration number
AP
AP7o 76
AR;
AR
8
32.6
52.8
33.3
53.4
35,8
33.2
38.8
16
33.1
53.3
2
33.7
53.9
36.4
33.6
39.3
32
33.9
53.5
33.7
54.1
36.5
33,9
39.5
64
34.2
53.7
33.9
54.0
36.8
34.1
40.0
128
34.1
53.8
8 33.6
53.6
36.1
33.7
39.3
Table 6, we study the influence of instance prototype number and the effect foreground brrroounndd-akrrouuddd contrasting. Using both positive and negative prototypes improves AP from 32.5% to 33.9%. Compared to the single prototype representation, the GMM demonstrate a stronger appearance modeling ability. We further find that the performance saturates when the number is larger than 60. In the Figure 6 and supplementary file, we provide additional instance cross-attention maps visualization to highlight the various attended regions.
In Table 7, we investigate the effectiveness of instance prototype (including the both positive and negative ones) propagation in an online manner, and compared it with using the instance prototype the initial frame or current frame. We find that updating object prototypes recurrently with momentum of 0.2 improves video segmentation AP of 1.3%.
Influence of EM iteration number We study the influence of EM iteration number T during condensing pes and the results are shown in Table 9. Using temporal memory length 4, we iterations from 6, and the improvement starts to saturate when T 2 We use the same iteration number during training and test.
find that the accuracy gains of PCAN increase with
Ablation study on KITTI-MOTS We also train PCAN on the KITTI-MOTS [37] training set and conduct ablations on the instance and frame PCAMs. Table 10, PCAN with window size on val set also shows significant improvements compared to the TrackR-CNN [37] (a two-stage tracker based on Mask R-CNN) on the benchmark. Note that many published methods on MOTTI-MOTS such Vip-DeepLab [31 EagerMOT [17] and MOTSFusion [24]. 3D bounding boxes, LIDAR point clouds, or optical flow (PointTrack [44]). In contrast, our method only relies on RGB images.
Qualitative analysis In Figure 4, we showcase qualitative ablation results of PCAN on Youtube-VIs, Compared to the baseline, we see that our model results more consistent segmentation and better tracking using prototypical -atss-attention module. We also provide visual results on BDD100K in Figure 5, where PCAN produces robust tracking and segmentation results even under large object appearance change (first row) or low illumination (second row). In the 3rd row, PCAN has limitations handling missing detections (the person in the first frame) with limited appearance information under extreme lighting, and produce tracking errors in the second frame when visible parts of the same car is totally different across frame and with low appearance similarity.
Cross-Attentin Visualization In Figure 6, we visualize instance-level prototypical cross-attention of the interested car for both the corresponding foreground and background regions on three continu- ous frames on BDD 100K, where the attended region of each object prototype reveals the implicit unsupervised temporal consistency. More visualization cases on instance and frame cross-attention maps and relevant analysis in the supplementary file.
Societal impact PCAN has high potential impact in important applications, such as transportation, sports analysis, and self-driving vehicles. However, this powerful technology can be deployed in human monitoring and surveillance as well which raise ethical and privacy issues. Potential negative impact be avoided by enforcing strict and secure data privacy regulation such as the GDPR.

---

Table 10: Ablation study of PCAN on KITTI-MOTS [37] validation set.
Method
Car-MOTSA
Ped-MOTSA
Car-MOTSP
Ped-MOTSP
SrackR-CNN [37]
87.8
65.1
87.2
75.7
PCAN w/o frame PCAM
87.3
65.3
86.9
75.0
PCAN w/o instance PCAM
87.8
65.8
87.1
75.5
PCAN (Ours)
89.6
66.4
88.3
76.1
Figure 5: Qualitative results of our method on BDD100K. PCAN produces robust tracking and segmentation results under large motion and appearance changes (1st row) and heavy traffic in low-light conditions (2nd row). In the 3rd row, PCAN misses detection (the person to the left in Ist frame), and produces tracking errors (2nd frame) when it covers totally different regions of the with low appearance similarity. Zoom for better view. Video results are in the suppl. file.
Foreground
Background
Foreground
Rackground
Foreground
Background
Input video frames
Predictions
Attention Sum!
Instance Attention Maps
Figure 6: Instance cross-attes attsnttttnttonn maps visualization for the car specified by the red dotted bounding box on BDD100K. We select the first four gnreground/backgroon one focuses on specific car sub-regions with implicit unsupervised temporal consistency over time. proper technology management education, and having an open dialogue among various stakeholders on how such technology should be deployed and regulated.
prototypes as example, where each
Conclusion
We present PCAN, new online method for MOTS. PCAN first distills the space-time memory into a frame-level and instance-level prototypes, followed by cross-attention retrieve rich information from the past frames. In contrast to most previous MOTS methods with limited temporal consideration, PCAN efficiently performs long-term temporal propagation and aggregation, and achieves large performance gain on the two largest MOTS benchmarks with low computation and memory cost. We validate the efficacy PCAN on both the existing one-stage and two-stage trackers. We believe PCAN will significantly benefit more video understanding tasks in the future.
10

---

Acknowledgments and Disclosure of Funding
This research is supported in part by the Research Grant Council of the Hong Kong SAR under grant no. 16201818 and Kuaishou Technology.
References
[1] Ali Athar, Sabarinath Mahadevan, Aljoša Okep, Laura Leal-Taixé, and Bastian Leibe. Stem-seg: Spatio- temporal embeddings for instance segmentation in videos. In ECCV, 2020.
[2] Gedas Bertasius and Lorenzo Torresani. Classifying, segmenting, and tracking object instances in video
with mask propagation. In CVPR. 2020.
[3] Daniel Bolya, Chong Zhou, Fanyi Xiao, and Yong Jae Lee. Yolact: Real-time instance segmentation. In
ICCV, 2019.
[4] Sergi Caelles, Kevis-Kokinn Maninis, Jordi Pont-Tuset, Laura Leal- Laixe Daniel Cremers, and Luc Van Gool. One-shot vidco object segmentation. In CVPR, 2017.
[5] Jiale Cao, Rao Muhammad Anwer, Hisham Cholakkal, Fahad Shahbaz Khan, Yanwei Pang, and Ling Shao. Sipmask: Spatial information preservation for fast image and video instance segmentation. In ECCV, 2020.
[6] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In ECCV. 2020.
[7] Yunpeng Chen, Yannis Kalantidis, Jianshu Li. Shuicheng Yan, and Jiashi Feng. ne-nets: Double attention networks. In NeurlPS, 2018.
[8] Alexey Dosovitskiy. Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner. Mostafa Dehghani, Matthias Minderer, Georg Heigold. Sylvain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition at scale. In ICLR, 2020.
[9] Christoph Feichtenhofer, Haoqi Fan, Jitendra Malik, and Kaiming He. Slowfast networks for vidco recognition. In ICCV, 2019.
[10] Andreas Geiger, Philip Lenz, and Raquel Urtasun. Are we ready for autonomous driving? the kitti vision benchmark suite. In CVPR, 2012.
[11] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. ICCV, 2017.
[12] Ping Hu, Fabian Caba, Oliver Wang. Zhe Lin, Stan Selaroff, and Federico Perazzi. Temporally distributed networks for fast video semantic segmentation. In CVPR, 2020.
[13] Zhaojin Huang. Lichao Huang, Yongchao Gong, Chang Huang. and Xinggang Wang. Mask scoring r-cnn. In CVPR, 2019.
[14] Joakim Johnander, Martin Danelljan, Emii Brissman, Fahad Shahbaz Khan, and Michael Felsherg. generative appearance model for end-to-end video object segmentation. In CVPR, 2019.
[15] Lei Ke, Yu-Wing Tai, and Chi-Keung Tang. Deep occlusion-aware instance segmentation with overlapping bilayers. In CVPR, 2021.
[16] Lei Ke, Yu-Wing Tai, and Chi-Keung Tang. Occlusion-aware video object inpainting. In ICCV, 2021.
[17] Aleksandr Kim, Aljoša OSep, and Laura Leal- Taix'Taxx' e. Eagermot: 3d multi multi-object tracking via sensor fusion. In IEEE International Conference on Robotics and Automation (ICRA), 2021.
[18] Minghan Li. Shuai Li, Lida Li. and Lei Zhang. Spatial feature calibration and temporal fusion for effective
one-stage video instance segmentation. In CVPR, 2021.
[19] Xia Li, Zhisheng Zhong. Jianlong Wu, Yibo Yang. Zhouchen Lin, and Hong Liu. Expectation- maximizatiiinn attention networks for semantic segmentation. In ICCV, 2019.
[20] Yingwei Ii, Xiaojie Jin, Jieru Mei, Xiaochen Lian, Linjie Yang, Cihang Xie, Qihang Yu, Yuyin Zhou, Song Bai, and Alan Yuille. Neural architecture search for lightweight non-local networks. In CVPR, 2020.
[21] Chung-Ching Lin, Ying Hung, Rogerio Feris, and Linglin He. Video instance segmentation tracking with modified vae architecture. In CVPR, 2020.
[22] Dongfang Liu, Yiming Cui, Wenbo Tan, and Yingjie Chen. Sg-net: Spatial granularity network for one-stage video instance segmentation. In CVPR, 2021.
[23] Xiankai Lu, Wenguan Wang, Danelljan Martin. Tianfei Zhou, Jianbing Shen, and Van Gool Luc. Video object segmentation with episodic graph memory networks. In ECCV, 2020.
[24] Jonathon Luiten, Tobias Fischer, and Bastian Leibe. Track to reconstruet and reconstruct track. IEEE Robotics and Automation Letters, 183:11003-1810 2020.
[25] Tim Mcinhardt, Alexander Kirillov, Laura Leal-Taixe, and Christoph Feichtenhofer. Trackformer: Multi- object tracking with transformers. arviv preprint arXiv:2101.02700 2021.
[26] Anton Milan, Laura Leal-Taixé, Ian Reid, Stefan Roth, and Konrad Schindler. Mot16: benchmark for multi-object tracking. arXiv preprint 16Xiv:1603,00000 00831, 2016.
[27] Anton Milan, Laura Leal-Taixé, Konrad Schindler, and lan Reid. Joint tracking and segmentation of multiple targets. In CVPR. 2015.
[28] Scoung Wug Oh, Joon- Young Lee, Ning Xu, and Seon Joo Kim. Video object segmentation using time memory networks. In ICCV, 2019.

---

[29] Jiangmiao Pang, Linlu Qiu, Xia Li, Haofeng Chen. Qi Li. Trevor Darrell, and Fisher Yu. Quasi-dense similarity learning for multiple object tracking. In CVPR, 2021.
[30]
Jiyang Qi, Yan Gao. Yao Hu, Xinggang Wang. Xiaoyu Liu, Xiang Bai, Serge Belongie, Alan Yuille, Philipp Torr, and Song Bai. Occluded video instance segmentation. arXiv preprini urXi::2102.015500 2021. Styuan Qiao, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang-Chieh Chen. Vip-deeplab: Learning visual perception with depth-aware video panoptic segmentation. In CVPR, 2021.
[31]
[32] Hongje Scong. Junhyuk Hyun, and Funtai Kim. Kemeliized memory network for video object segmentation. In ECCV, 2020.
[33] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In NeurlPS,
2017.
[34] 7hi Tian, Chunhua Shen, Hao Chen, and Tong He. Fcos: Fully convolutional one-stage object detection.
In ICCV, 2019.
[35] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, F. ukasz Kaiser, and Illia Polosukhin. Attention all you need. In NewrlPS, 2017.
[36] Paul Voigtlaender, Yuning Chai, Florian Schroff, Hartwig Adam, Bastian Leibe, and I Liang-Chich Chen.
Feelvos: Fast end-to-end embedding learning for video object segmentation. CVPR, 2019.
[37] Paul Voigtlaender, Michael Krause, Aljosa Osep, Jonathon Luiten, Berin Balachandar Gnana Sekar, Andreas Geiger, and Bastian Leihe. Mots: Multi-object tracking and segmentation. In CVPR, 2019.
[38] Apoory Vyas, Angelos Katharopoulos, and François Fleuret. Fast transformers with clustered attention.
NeurIPS, 2020.
[39] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In CVPR, 2018.
[40] Xiaolong Wang and Abhinav Gupta. Videos as space-time region graphs. In ECCV, 2018.
[41] Yuqing Wang. Zhaoliang Xu. Xinlong Wang. Chunhua Shen, Baoshan Cheng, Hao Shen, and Huaxia Xia. End-to-end video instance segmentation with transformers. arXiv preprint arXiv:2011. 1.450v.., 2020. [42] Nicolai Wojke, Alex Bewley, and Dietrich Paulus. Simple online and realtime tracking with a deep association metric. In IEEE international conference on image processing (ICIP), 2017.
[43] Haozhe Xie, Hongxum Yao, Shangchen Zhou, Shengping Zhang, and Wenxiu Sun. Efficient regional memory network for video object segmentation. In CVPR, 2021.
[44] Zhenbo Xu, Wei Zhang, Xiao Tan, Wei Yang, Huan Huang, Shilei Wen, Errui Ding, and Liusheng Huang. Segment as points for efficient online multi-object tracking and segmentation. In Proceedings of the European Conference on Computer Vision (ECCV), 2020.
[45] Boyu Yang. Chang Liu, Bohao Li, Jianbin Jiao, and Qixiang Ye. Prototype mixture models for few-shot semantic segmentation. In ECCV, 2020.
[46] Linjie Yang. Yuchen Fan, and Ning Xu. Vidco instance segmentation. In ICCV, 2019.
[47] Linjie Yang. Yanran Wang, Xuehan Xiong, Jianchao Yang, and Aggelos K Katsaggelos. Efficient video object segmentation via network modulation. In CVPR, 2018.
[48] Shusheng Yang. Yuxin Fang. Xinggang Wang. Yu Li, Chen Fang, Ying Shan, Bin Feng, and Wenyu Liu. Crossover learning for fast online video instance segmentation. In ICCV, 2021.
[49] Zongxin Yang. Yunehao Wei. and Yi Yang. Collaborative video object segmentation by foreground- background integration. In ECCV, 2020.
[50] Fisher Yu, Haofeng Chen, Xin Wang, Wengi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell. Bdd100k: A diverse driving dataset for heterogeneous multitask learning. In CVPR, 2020.
[51] Chi Zhang, Guosheng Lin, Fayao Liu. Rui Yao, and Chunhua Shen. Canet: Class-agnostic segmentation networks with iterative refinement and attentive sho- learning. In CVPR, 2019.
12


Reviews:
[{"review_id": "iZLhj9boicg", "reviewer": "Reviewer_HvVc", "summary": "This paper provides a Prototypical Cross-Attention Networks (PCA) for Multiple Object Tracking and Segmentation (MOTS). Two prototypical cross-attention modules are adopted for frame-level and instance-level features to retrieve information from past frames. By applying prototypical cross-attention, computational cost has been reduced. Experiments on two datasets demonstrate the effectiveness of the proposed method.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n### Originality: \nThe prototypical cross attention using clustering is new for MOTS. It reduces computational complexity for obtaining spatial temporal information compared to spatial temporal attention.\n\n\n### Quality:\nThe method is technically sound. However,  many designs in the paper are not validated. \nFor instance, the impact of the number of cluster N is not validated. The impact of each module to the tracking performance is not clear.\n\n\n### Clarity:\nThe paper is badly written. Many crucial details are missing. In figure1, the aggregate feature $\\bar{y}_t$ is used for classification, detection, tracking, and segmentation. However, there are no descriptions in the paper to elaborate the processes on $\\bar{y}_t$. How to construct positive and negative instance prototypical?  Training details are also missing in the paper. \n\n### Significance: \nThe proposed method outperforms SOTA one-stage methods on two MOTS datasets.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. This paper proposes PCM to reduce computational cost for online tracking and segmentation. However, 15 fps is much slower than 28fps in [18]. Authors should report FLOPS for compared methods. \n\n2. I'm confused by Figure 1, 2 and 3.  The shapes of frame embedding in Figure 1, 3 are the same, but are different from Figure 2. \n  The frame embedding is passed to PCM in Figure 1 and is passed to the Multiple-level temporal aggregation module in Figure 2.  \nHowever, the frame embedding is passed to TSM for mask prediction in Figure 3. The TSM module is also not mentioned in the text. \n\n3. What is the number of mixtures in GMM (N) during training? What is the temporal length $t$ during training? Many important training details are missing. The impact of N is not validated. Impacts of modules should be summarized in a table.\n\n4. Instance-level prototypes only have two mixtures (foreground and background). Are all instances belonging to the foreground prototypical?  What do prototypes stand for? How to infer a tracking mask with $\\bar{y}_t$ and $\\bar{k}$?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 "}, "extra_text": {}}, {"review_id": "LfAImboR7MV", "reviewer": "Reviewer_NPPQ", "summary": "The paper focuses on making transformers for multi-object-tracking-and-segmentation (MOTS) more efficient, where typically all pixels from the past frames have to \"transform\" with all current pixels. The trick in the paper is to group past pixels into prototypes (clusters) and hence reduce complexity. \n\nThe authors claim contributions in:\n\n- Improve transformers's efficiency for dense segmentation by operating at a per cluster (prototype) level rather than per pixel for past frames.\n\n- Applied the method to MOTS.\n\n- Further improvement by introducing foreground and background prototypes.\n\n- Experiments and above SOTA performance.\n\nI agree with the novelty assessment. I am not an expert in MOTS, without looking up additional comparison, this work seems to do well on Berkeley deep drive (BDD) and Youtube-VIS, although some of the numbers in the paper do not agree with what are in original papers (see below).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am borderline on this paper, leaning acceptance, based on sufficient novelty and good experimental results compared to SOTA. My concerns are a bit in the ablation and the mismatch between cited SOTA numbers and what they are from papers.\n\nSufficient novelty: The novelty of grouping pixels into clusters and use them as unit for the transformer seems like a very simple idea to improve the efficiency. I was honestly quite surprised that I couldn't find a work that has done this before. Assuming that the idea is indeed new, it should be sufficient for this venue.\n\nSufficient experiments against SOTA: The authors performed experiments on both the BDD and the Youtube-VIS dataset and showed strong results against SOTA. My only comment is that the VisTR numbers quoted in this paper don't match those in the original publication (e.g. 40.1 AP). Please elaborate the difference.\n\nQuestions:\n\nAblation: The motivation of the work is to improve the efficiency by grouping pixels together. Is there any experiments showing how much accuracy we lose by doing this? If not feasible, how about trivial grouping such as a simple tiling of the input images?\n\nNits:\n- For equations, there shouldn't be a point after each equation.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since the model keeps all prototypes from all past frames, a limitation is that it won't scale to infinite time. However, a simple fix is to \"forget\" some prototypes after a while.\n\nYes on societal impact, no comment.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 - 3 hrs, didn't count exactly"}, "extra_text": {}}, {"review_id": "Bg0HgWJ4b7l", "reviewer": "Reviewer_TiXB", "summary": "This paper builds upon a mask propagation family of methods that leverage memory mechanism to decode current-frame segmentation mask(s) (assuming the first-frame mask is given, either specified via human or predicted by a network). In a nutshell, these methods will need to attend to all pixels stored in the memory (that effectively represents a spatiotemporal volume), leading to high computational cost (quadratic wrt. the image size). This paper proposes a very interesting alternative: instead of computing cross-attention maps between query and the spatio-temporal volume (memory), attending to WxHxT pixels, the memory will be clustered into a fixed (pre-defined) number of components, modeled as Gaussians. As a consequence, attention will be computed over cluster representatives (means), i.e., N-prototypes. This yields a significant reduction in the complexity (attending to N-prototypes instead of WxHxT pixels) and (as Tab. 5 shows) doesn’t have a negative impact on the final performance (works even slightly better). The experiments conducted on Youtube-VIS and BDD100k dataset confirm that the presented method is effective and outperforms the state-of-the-art, and design decisions are well-justified via well-designed ablation studies. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nPros\n\n--------------\n\n* This paper is well-written and motivated, technically sound, and presents a very nice solution to a relevant problem. Methods that leverage Spatio-temporal memory are highly competitive and very promising research direction in the field of tracking and segmentation, and the remedy for the memory issue proposed in this paper could lead to winder adaptation of this family of methods! \n* The paper presentation is (mostly) fine. Certain parts could be connected better and certain explanations could be refined (e.g., it should be explained sooner how the learned clustering will be utilized to reduce the complexity; also, 3.3.2 is a bit verbose), but I think that is doable within a few additional passes/iterations over the paper. \n* Experimental evaluation is convincing, even though the lack of experiments on the standard MOTS dataset (Voigtlander et al., CVPR'19) and VOS datasets (Perazzi et al., CVPR'16) is rather surprising. I especially appreciate the thorough ablation studies, clearly demonstrating how the performance improves with the size of the memory bank (wrt. the temporal dimension) and demonstrating that the prototypical cross-attention model does not hurt the performance. \n* This paper makes a big step towards the applicability of memory-based methods for tracking and segmentation-related tasks, and I am very excited about the prospects of that! \n\nCons\n\n--------------\n\n\n* While I am fairly convinced with the experimental evaluation (i.e., all claims are sufficiently supported experimentally), I was quite surprised to see that no experiments were conducted on the MOTS dataset- why? This is surprising, as this is the first MOTS dataset with a public test set containing a significantly larger number of entries compared to three baselines reported in Tab 2. If the model could not be trained due to a small amount of training data, it would be nice to discuss that. \n* Given that the proposed method tackles mask propagation through the volume, why is not this method evaluated on the video-object segmentation datasets (DAVIS, YouTube-VOS)?\n* Presentation-wise, there is a big jump between 3.1 and 3.2; while 3.1 nicely summarises issues with the prior memory-based methods, 3.2 jumps directly into clustering. I feel that a sentence or a paragraph that would provide the intuition on how the prototypes will be used to reduce the complexity would be well in place. \n* If I am not mistaken, this method needs to be applied independently to each mask (either given in the first frame of the clip or detected on the fly in case of MOTS). This should be made very very clear and preferably listed as a disadvantage of this method (correct me if I misunderstood this). \n* It should be made more clear what aspect of MOTS task this paper tackles precisely: i.e., only mask propagation and not detection.  \n\n\nAdditional questions:\n\n* Looking at the temporal window size (for memory), the performance did not saturate with T=32. Why didn’t you try bigger temporal windows?\n* What is N (#prototypes) in practice, and how was it determined? How does varying N impacts the performance? \n\n\nJustification\n\n--------------\n\nOverall I am excited about the contribution of this paper its potential impact on the community. I am certain that the community will also appreciate these findings. Given that this paper is informative, presents an interesting (and novel) solution to a relevant problem, and backs up all claims well experimentally, I think it should be accepted to NeurIPS proceedings. \n\n\nPost-rebuttal Comments and Justification\n\n--------------\n\nI would like to thank the authors for a good rebuttal, my doubts were addressed well. I also read comments from my colleagues and I see we have a consensus that this is a good paper that will be valuable to the community. \n\nI would suggest adding the number of prototypes ablation to the main paper (I see that my colleagues also agree on that). I still think the evaluation on MOTS dataset would make sense, the standard approach is to compare to vision-only based methods. I find a direct comparison to the first (and as simple as possible) TrackR-CNN baseline more meaningful compared to the BDD100k based discussion. \n\nOverall, I think this paper will open the door for a wider applicability of methods that explicitly leverage external memory to aid data association and keep my original rating.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors did address potential negative social impacts but could do a better job at addressing limitations (see my comments). ", "review_text": "", "extra_scores": {"ethical_concerns": "I don't see any ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "0CF-v5mrFKz", "reviewer": "Reviewer_9ARZ", "summary": "This paper tackles multiple object tracking and segmentation. The whole framework is based on previous cross attention methods, and the main selling point is to deal with the complexity of the attention computation by constructing prototypes in the feature space. In addition to frame-wise prototypes, instance prototypes are also computed to refine the segmentation. Good performance is shown on two major benchmarks Youtube-VIS and BDD100K. Also, a good trade-off between efficiency and accuracy is reported in Table 5. It is a marginal yet solid contribution, but there are still many issues that need to be clarified such that the message here can be accurately delivered.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "the key idea of this paper is to reduce the computational cost of attention-based tracking and segmentation by cross attention between the query feature and a set of prototype features. An additional procedure is to compute the attention within a specific instance. It is a natural extension of traditional cross-attention methods, and the novelty is a bit limited.\nHowever, the experiments, including both the comparison to the other methods and the ablation study, demonstrate good performance on two major datasets.\n\nthere are no major flaws in the proposed method given the goal is to reduce computation during the attention procedure.  Since the prototypes are averaged features, how does the proposed method achieve the balance between discriminability and robustness? for example a person wearing a white shirt and black pants, the average could be anything, how do you ensure that the pixel-wise feature in the current frame can attend to the right features? Moreover, there are many descriptions that are not clear, which makes it difficult to appreciate the details of the method. please check the following:\n\n- in eq. 4, the summation is over N values, which is equivalent to the number of prototypes. it is weird that the number of features to be clustered is equal to the number of clusters.\n- in eq. 5, the similarity is measured by the L2 distance between the feature and the prototypes, how much difference does it make if a cosine similarity is used here?\n- line 154, what do you mean by \"essentially aligns the condensed feature information in frame \\hat{t} with the current frame\"? it is a linear combination of the value features from time \\hat{t}, specifically, what information is been aligned here?\n- in eq. 7, why do you use dot product here instead of L2? any normalization of the features during dot product?\n- what does the subscript j mean in the notation K^+_tj in section 3.3.2? does it mean instance id?\n- line 175, how many prototypes do you have for the foreground and background? \n- line 178, for each object, how do you know which set of foreground and background features you need to attend?\n- line 179, how do you get the initial mask detection?\n- line 181, when you update the features, how do you select the background features?\n- line 167, why is this contrastive foreground and background representation? is there an explicit learning procedure that encourages the foreground feature and background to be different?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think so. there is a whole paragraph addressing the issues related to societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "four hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All four reviewers recommend acceptance of this paper. The final ratings are: 7, 7, 6, 7.

Overall, the reviewers appreciated the interesting take on reducing the computational cost of memory-based mask propagation methods by means of matching to a small set of prototypes. The cost-accuracy tradeoff is acknowledged as very strong. The ablations are informative and convincing.

However, several reviewers comment that the presentation and description of the method should be improved to do full justice to the approach. As noted by Reviewer TiXB, the ablations on the number of prototypes is highly relevant and should be added to the paper if at all possible.

Decision: Accept (Spotlight)