Antoine Yang

Antoine Miech

Josef Sivic

Ivan Laptev

Cordelia Schmid

TubeDETR: Spatio-Temporal Video Grounding with Transformers

We consider the problem of localizing a spatio-temporal tube in a video corresponding to a given text query. This is a challenging task that requires the joint and efficient modeling of temporal, spatial and multi-modal interactions. To address this task, we propose TubeDETR, a transformerbased architecture inspired by the recent success of such models for text-conditioned object detection. Our model notably includes: (i) an efficient video and text encoder that models spatial multi-modal interactions over sparsely sampled frames and (ii) a space-time decoder that jointly performs spatio-temporal localization. We demonstrate the advantage of our proposed components through an extensive ablation study. We also evaluate our full approach on the spatio-temporal video grounding task and demonstrate improvements over the state of the art on the challenging VidSTG and HC-STVG benchmarks.

Introduction

Grounding natural language in visual content is a fundamental skill to build powerful and explainable vision and language models. In particular, understanding the association of language with spatial regions and temporal boundaries in videos is particularly important to analyze and improve multi-modal video models. This goes beyond associating a global visual representation with a textual representation [START_REF] Miech | End-to-end learning of visual representations from uncurated instructional videos[END_REF]62], as it requires to reason about detailed spatiotemporal visual representations and their association with natural language, as illustrated in Figure 1.

Spatio-temporal video grounding, recently introduced in [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF], is an interesting and challenging task that lies at the intersection of visual grounding [START_REF] Hu | Natural language object retrieval[END_REF][START_REF] Varun K Nagaraja | Modeling context between objects for referring expression understanding[END_REF][START_REF] Balajee Vasudevan | Object referring in videos with language and human gaze[END_REF] and temporal localization [START_REF] Chen | Temporally grounding natural sentence in video[END_REF][START_REF] Gao | TALL: Temporal activity localization via language query[END_REF][START_REF] Lisa | Localizing moments in video with natural language[END_REF]. Given an untrimmed video and a textual description of an object, spatio-temporal video grounding aims at localizing a spatio-temporal tube (i.e., a sequence of bounding boxes) for the target object described by the input text. This task is particularly challenging as videos are highly diverse and often present challenging scenarios where different entities have similar appearance or perform similar actions within one scene.

The success of attention-based models in natural language processing [START_REF] Devlin | BERT: Pre-training of deep bidirectional transformers for language understanding[END_REF][START_REF] Vaswani | Attention is all you need[END_REF] has recently inspired approaches to integrate transformers into computer vision tasks, such as image classification [22], object detection [START_REF] Carion | End-to-end object detection with transformers[END_REF], semantic segmentation [START_REF] Liu | Swin transformer: Hierarchical vision transformer using shifted windows[END_REF] or action recognition [3,7,[START_REF] Patrick | Keeping your eye on the ball: Trajectory attention in video transformers[END_REF][START_REF] Zhang | VidTr: Video transformer without convolutions[END_REF]. Notably, with DETR [START_REF] Carion | End-to-end object detection with transformers[END_REF], transformers have shown competitive performance on object detection while removing the need of multiple hand-designed components encoding a prior knowledge about this task. More recently, MDETR [START_REF] Kamath | MDETR -modulated detection for end-to-end multi-modal understanding[END_REF] has extended this framework for various text-conditioned object detection tasks in the image domain, such as phrase grounding, referring expression comprehension and segmentation.

Inspired by these works, and the fact that attentionbased architectures are an intuitive choice for modelling multi-modal and spatio-temporal contextual relationships in videos, we develop a transformer encoder-decoder model for spatio-temporal video grounding, as illustrated in Figure 2. While existing approaches for this task rely on preextracted object proposals [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF], tube proposals [START_REF] Tang | Human-centric spatio-temporal video grounding with visual transformers[END_REF] or upsampling layers [START_REF] Su | STVGBert: A visuallinguistic transformer based framework for spatio-temporal video grounding[END_REF], our architecture simply reasons about abstractions called time queries to jointly perform temporal localization and visual grounding. Our framework enables to use the same representations for both subtasks in order to learn powerful contextualized representations. 1 More specifically, our architecture includes key components to jointly model temporal, spatial and multi-modal interactions. Our video-text encoder efficiently encodes spatial and multi-modal interactions by computing these interactions over sparsely sampled frames, and separately recovers temporally local information with a lightweight fast branch. Our space-time decoder models temporal interactions with temporal self-attention layers, and spatial and multi-modal interactions with time-aligned cross-attention layers. Spatio-temporal video grounding is then tackled with multiple heads on top of the decoder outputs, which predict the object boxes and temporal start and end probabilities. We conduct various ablation studies, where we notably show the benefit of our video-text encoder in terms of performance-memory trade-off, and the efficiency of our space-time decoder in terms of spatio-temporal grounding results. Finally, we show that our method significantly improves over state-of-the-art methods on two benchmarks, VidSTG [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF] and HC-STVG [START_REF] Tang | Human-centric spatio-temporal video grounding with visual transformers[END_REF]. In summary, our contributions are three-fold: (i) We propose a novel architecture for spatio-temporal video grounding that performs this task with a space-time transformer decoder. (ii) We propose a dual-stream encoder that efficiently encodes spatial and multi-modal interactions, based on a slow multi-modal stream and a lightweight fast visual stream. (iii) We conduct comprehensive experiments on two benchmarks, VidSTG and HC-STVG, showing the effectiveness of our framework for the spatio-temporal video grounding task. Our approach, referred to as TubeDETR, outperforms all state-of-the-art methods by a large margin. Code and trained models are publicly available at [1].

Related Work

Spatio-temporal video grounding. Visual grounding consists in spatially localizing an object given a referring expression, and has been an active area of research both in the image domain [START_REF] Deng | Visual grounding via accumulated attention[END_REF]32,[START_REF] Hu | Natural language object retrieval[END_REF][START_REF] Liu | Relationaware instance refinement for weakly supervised visual grounding[END_REF][START_REF] Varun K Nagaraja | Modeling context between objects for referring expression understanding[END_REF][START_REF] Wang | Improving weakly supervised visual grounding by contrastive knowledge distillation[END_REF]83,[START_REF] Yu | A joint speaker-listener-reinforcer model for referring expressions[END_REF][START_REF] Zhang | Grounding referring expressions in images by variational context[END_REF][START_REF] Zhuang | Parallel attention: A unified framework for visual object discovery through dialogs and queries[END_REF] and the video domain [START_REF] De-An | Finding" it": Weaklysupervised reference-aware visual grounding in instructional videos[END_REF]66,[START_REF] Balajee Vasudevan | Object referring in videos with language and human gaze[END_REF]. A standard paradigm consists in using pre-extracted object proposals [START_REF] Liu | Referring expression generation and comprehension via attributes[END_REF][START_REF] Liu | Improving referring expression grounding with cross-modal attention-guided erasing[END_REF]78,[START_REF] Yamaguchi | Spatio-temporal person retrieval via natural language queries[END_REF][START_REF] Yang | Cross-modal relationship inference for grounding referring expressions[END_REF]87,[START_REF] Yu | MAttNet: Modular attention network for referring expression comprehension[END_REF], while some recent works [START_REF] Deng | TransVG: End-to-end visual grounding with transformers[END_REF][START_REF] Huang | Look before you leap: Learning landmark features for one-stage visual grounding[END_REF][START_REF] Kamath | MDETR -modulated detection for end-to-end multi-modal understanding[END_REF][START_REF] Liao | A real-time cross-modality correlation filtering method for referring expression comprehension[END_REF][START_REF] Luo | Multi-task collaborative network for joint referring expression comprehension and segmentation[END_REF][START_REF] Yang | Improving one-stage visual grounding by recursive sub-query construction[END_REF][START_REF] Yang | A fast and accurate onestage approach to visual grounding[END_REF] have proposed one-stage approaches which do not rely on such proposals. Our work follows the one-stage framework of MDETR [START_REF] Kamath | MDETR -modulated detection for end-to-end multi-modal understanding[END_REF], but extends it to spatio-temporal video grounding with temporal localization losses (see Equation 1), slow-fast encoding (see Figure 3), and space-time decoding (see Figure 4).

A separate line of work focuses on temporally localizing moments in a video given a natural language query [START_REF] Chen | Temporally grounding natural sentence in video[END_REF][START_REF] Chen | Localizing natural language in videos[END_REF][START_REF] Chen | Semantic proposal for activity localization in videos via sentence query[END_REF][START_REF] Gao | TALL: Temporal activity localization via language query[END_REF][START_REF] He | Read, watch, and move: Reinforcement learning for temporally grounding natural language descriptions in videos[END_REF][START_REF] Lisa | Localizing moments in video with natural language[END_REF][START_REF] Lisa | Localizing moments in video with temporal language[END_REF][START_REF] Lin | Weakly-supervised video moment retrieval via semantic completion network[END_REF][START_REF] Chowdhury Mithun | Weakly supervised video moment retrieval from text queries[END_REF][START_REF] Rodriguez | Proposal-free temporal moment localization of a natural-language query in video using guided attention[END_REF][START_REF] Wang | Temporally grounding language queries in videos by contextual boundary-aware prediction[END_REF][START_REF] Wang | Languagedriven temporal activity localization: A semantic matching reinforcement learning model[END_REF][START_REF] Yuan | To find where you talk: Temporal sentence localization in video with attention based location regression[END_REF][START_REF] Zeng | Dense regression network for video grounding[END_REF][START_REF] Zhang | MAN: Moment alignment network for natural language moment retrieval via iterative graph adjustment[END_REF][START_REF] Zhang | Span-based localizing network for natural language video localization[END_REF][START_REF] Zhang | Learning 2d temporal adjacent networks for moment localization with natural language[END_REF][START_REF] Zhang | Cross-modal interaction networks for query-based moment retrieval in videos[END_REF]. These works build architectures that reason about time but do not preserve spatial information. Spatio-temporal video grounding lies at the intersection of temporal localization and visual grounding. While some approaches [START_REF] Chen | Weakly-supervised spatio-temporally grounding natural sentence in video[END_REF][START_REF] Tang | Human-centric spatio-temporal video grounding with visual transformers[END_REF][START_REF] Yamaguchi | Spatio-temporal person retrieval via natural language queries[END_REF] rely on pre-extracted tube proposals, or object proposals [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF], our method does not require any pre-extracted proposals. A recent work [START_REF] Su | STVGBert: A visuallinguistic transformer based framework for spatio-temporal video grounding[END_REF] proposes STVGBert, a onestage approach that extends the VilBERT model [START_REF] Lu | ViL-BERT: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks[END_REF] pretrained on Conceptual Captions [START_REF] Sharma | Conceptual Captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning[END_REF] to this task. STVG-Bert uses deconvolutions to perform visual grounding, and symmetrically models temporal and spatial interactions. In contrast, our architecture performs visual grounding with a transformer decoder, and separately reasons about the temporal and spatial dimensions.

Temporal modeling for video understanding. The rise of powerful models for image understanding such as ViT [22] or DETR [START_REF] Carion | End-to-end object detection with transformers[END_REF] has fostered research extending these models to the video domain [3,7,[START_REF] He | End-to-end video object detection with spatial-temporal transformers[END_REF]41,[START_REF] Patrick | Keeping your eye on the ball: Trajectory attention in video transformers[END_REF][START_REF] Zhang | VidTr: Video transformer without convolutions[END_REF]. In particular, Lei et al. [41] propose an architecture that views moment retrieval as a direct set prediction problem, but is unsuitable to visual grounding as it does not preserve spatial information. He et al. [START_REF] He | End-to-end video object detection with spatial-temporal transformers[END_REF] extend the DETR framework to videos, and propose an architecture built with sequentially added modules on top of Deformable DETR [START_REF] Zhu | Deformable DETR: Deformable transformers for end-to-end object detection[END_REF], while ours is built on inner modifications of a pretrained encoder and decoder and also reasons about language. Our dual-branch encoder is also related to SlowFast networks [23,[START_REF] Xiao | Audiovisual slowfast networks for video recognition[END_REF] which combine fast and slow video streams. In contrast, in our case, both streams operate on features extracted from the same backbone, and our dual-stream architecture is motivated by the computational complexity related to multi-modal modeling.

Vision and language. Transformer-based architectures have become ubiquitous in various vision and language tasks [START_REF] Chen | History aware multimodal transformer for vision-and-language navigation[END_REF]14,17,[START_REF] Desai | VirTex: Learning visual representations from textual annotations[END_REF]36,[START_REF] Kim | ViLT: Visionand-language transformer without convolution or region supervision[END_REF][START_REF] Li | Unicoder-VL: A universal encoder for vision and language by cross-modal pre-training[END_REF][START_REF] Bain | Frozen in time: A joint video and image encoder for end-to-end retrieval[END_REF][START_REF] Lu | ViL-BERT: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks[END_REF][START_REF] Lu | 12-in-1: Multi-task vision and language representation learning[END_REF][START_REF] Su | VL-BERT: Pre-training of generic visual-linguistic representations[END_REF][START_REF] Tan | LXMERT: Learning crossmodality encoder representations from transformers[END_REF][START_REF] Zhou | Unified vision-language pre-training for image captioning and VQA[END_REF]. Most video-text transformers rely either on pre-extracted object features [START_REF] Zhu | ActBERT: Learning global-local video-text representations[END_REF], or spatially pooled features [START_REF] Gabeur | Multi-modal transformer for video retrieval[END_REF][START_REF] Ging | COOT: Cooperative hierarchical transformer for video-text representation learning[END_REF][START_REF] Li | HERO: Hierarchical encoder for video+language omni-representation pre-training[END_REF]70,[START_REF] Yang | Just ask: Learning to answer questions from millions of narrated videos[END_REF][START_REF] Zhou | End-to-end dense video captioning with masked transformer[END_REF], which do not preserve detailed spatial information. In contrast, our architecture is designed to preserve spatial information to perform visual grounding. Some recent works propose transformer-based architectures reasoning on videos and text that do preserve spatial information [2,5,[START_REF] Lei | Less is more: Clipbert for video-and-language learning via sparse sampling[END_REF][START_REF] Zellers | MERLOT: Multimodal neural script knowledge models[END_REF]. However, these works typically aim to learn global video representations to tackle video-level prediction tasks, while we focus on learning detailed framelevel representations to address a dense prediction task requiring spatial and temporal localization.

Method

We first give an overview of our model in Section 3.1. Next, we describe in detail the two main components of our model, the video-text encoder (Section 3.2) and the spacetime decoder (Section 3.3). Then in Section 3.4 we explain the loss used to train our model. Finally in Section 3.5 we present how we initialize our model weights.

Overview

Our objective is, given a video and a language query, to output a spatio-temporal tube, i.e. a sequence of bounding boxes with temporal boundaries, grounding the language query in the video. This is challenging as it requires modelling long-range spatial and temporal interactions between the language query and the video where the video may have hundreds of frames represented by tens of thousands spatiotemporal video features. Hence efficiency is a major challenge. To address this issue we design an encoder-decoder architecture, illustrated in Figure 2, that enables accurate yet efficient modelling of video-language spatial and temporal interactions across the entire video. In particular, our two-stream video-text encoder (Section 3.2) models videolanguage interactions only over short clips of about one second but allows for detailed spatial localization. Our spacetime decoder (Section 3.3) then models long-range temporal interaction over the entire video to produce a temporally consistent output and accurate predictions of the start and end times of the output spatio-temporal tube.

Video-Text Encoder

Our encoder is illustrated in Figure 3 and described next. Its objective is to model spatial and multi-modal interactions between the language query and the video to accurately spatially ground the query in each frame. To achieve this, we leverage the ability of the self-attention layers to jointly model spatial and visual-linguistic interactions [36,[START_REF] Kamath | MDETR -modulated detection for end-to-end multi-modal understanding[END_REF][START_REF] Lei | Less is more: Clipbert for video-and-language learning via sparse sampling[END_REF]. However, computing self-attention between visual features and textual features for every frame is computationally expensive. For this reason, we propose to compute spatial and multi-modal interactions only for every k-th frame. We denote the resulting stream as slow multi-modal branch. We use a separate lightweight fast visualonly branch that preserves the original frame rate and allows us to recover some of the high frequency spatio-temporal details lost by the sparse sampling in the slow branch.

Formally, our encoder takes as input a set of 2D flattened image features x 0 (v) ∈ R T ×HW ×d from the visual backbone for all T frames of the input video together with a set of L text features y 0 (s) ∈ R L×d extracted by the text encoder from the query sentence, and outputs a set of videotext features F (v, s) ∈ R T ×(HW +L)×d , one for each frame. Next we give the details of the Slow and Fast branches, and the final feature aggregation module. Slow multi-modal branch. The goal of this branch (see top of Figure 3) is to model interactions between visual and textual representations. This branch first samples features from one frame for a short clip of k consecutive frames. A typical clip length is one second, i.e. k = 5 with a standard frame rate of 5 frames per second [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF]. Formally, the resulting feature map is written as x p ∈ R M ×HW ×d where M = ⌈ T k ⌉ is the number of clips, k is the length of the clip and T is the length of the entire video. We then concatenate, for each clip m, its visual features x p m with text features y 0 (s) and forward it to a N-layer transformer encoder. The outputs are contextualized visual-text representations h p (v, s) ∈ R M ×(HW +L)×d , which effectively combine information from the input video v and the query sentence s. Fast visual-only branch. The previously explained temporal sparse sampling scheme reduces significantly the memory requirements of the video-text encoder but results in a loss of spatio-temporal details which are important for spatio-temporal video grounding. To alleviate this issue, we introduce module f (see bottom of Figure 3) which operates on 2D flattened image features for all frames. For- Then it computes multi-modal interactions between the sampled features x p m and text features y0 using a transformer encoder. The temporal sampling reduces the number of video features in order to efficiently compute the attentionbased interactions. Bottom: lightweight "Fast visual-only" branch f processes features from all frames but without any attention layers for increased efficiency. Features from both branches are then combined in module g into the final set of per-frame features F (v, s).

mally, given feature map x 0 (v), this module outputs visual features f (v) ∈ R T ×HW ×d . This fast branch preserves the spatial and temporal resolution of the features but is computationally light as it does not compute any multi-modal or spatial interactions. For additional efficiency, at training time, this branch does not back-propagate gradients to the visual backbone. Furthermore, we show in Section 4.2 that it is able, when combined with the temporally sparse features obtained from the slow branch, to recover some of the temporal information lost during the temporal sampling. Slow-Fast feature aggregation. We now describe the slow and fast branches aggregation module (see Figure 3, right), which fuses information from both branches and outputs final video-text features. To match the temporal dimension of the output from the fast branch f (v), the output of the slow multi-modal branch h p (v, s) is temporally replicated k times for each clip resulting in videotext encodings h(v, s) ∈ R T ×(HW +L)×d . These encodings are a concatenation of text-contextualized visual encodings h v (v, s) ∈ R T ×HW ×d and visually-contextualized textual encodings h s (v, s) ∈ R T ×L×d . The text-contextualized visual encodings h v (v, s) are combined with the outputs of the fast branch with an additional aggregation module g and a residual connection, resulting in aggregated visual encodings

F v (v, s) = g(h v (v, s), f (v)) + h v (v, s).
The final output of our video-text encoder is obtained by concatenating these aggregated visual encodings with the visually-contextualized textual encodings i.e.

F (v, s) = [F v (v, s), h s (v, s)] ∈ R T ×(HW +L)×d .
In detail, the module g is implemented as a sum followed by a linear layer, i.e. g(

h v (v, s), f (v)) = Linear(h v (v, s) + f (v)).

Space-Time Decoder

Our decoder is illustrated in Figure 4 and detailed next. Its objective is to model the temporal interactions within the entire video of T frames and decode the multi-modal features from the encoder into a temporally coherent output tube with accurate start and end times. This is achieved by an efficient decoder architecture that alternates (i) temporal self-attention layers, which model temporal interactions across the entire video, with (ii) time-aligned cross attention layers, which efficiently incorporate the video-text features for individual frames obtained from the encoder. In detail, the decoder operates on T positional encodings {q t } T t=1 , one per frame, referred to as time queries. The initial encoding of each time query is obtained by summing a learnt object encoding common to all frames, and a frozen sinusoidal time encoding. The decoder also takes as input T × (HW + L) video-language embeddings F (v, s) output from the video-text encoder. The decoder is a succession of N decoder blocks. Each block is composed of temporal self-attention, time-aligned cross-attention, and feed-forward layers, interleaved with normalization [START_REF] Lei Ba | Layer normalization[END_REF], as shown in Figure 4. The decoder outputs refined time queries {Q t } T t=1 , which are contextualized across all frames in the video together with video-text features produced by the encoder. The refined time queries are then jointly used for outputting the spatio-temporal video tube that grounds the input sentence in the video. The individual layers are described in detail next. Temporal self-attention. The T input time queries q t attend to each other using the temporal self-attention layer. This layer is in each of the N blocks of the decoder and is responsible for modelling the long-range temporal interactions in the entire video. This is possible because of the relatively low complexity of this layer, which does not depend on the spatial resolution of the input video. Time-aligned cross-attention. Allowing each time query to cross-attend to all T × (HW + L) video-text features can be highly computationally expensive due to the large number of video frames T and a large spatial resolution HW of the video features. Instead, in our cross-attention module, each time query q t only cross-attends to its temporally corresponding multi-modal features F (v, s)[t] at frame t. Note that with our time-aligned cross-attention formulation, the time encoding and the temporal self-attention layers are all the more important, as they are responsible for the temporal modelling across the entire video. Without them, our decoder would be decoding each frame independently. Their importance is ablated in Section 4.2.

{𝑄 ! } !"# $ … MLPs + 𝑏 # τ % ! τ & ! + 𝑏 ! ! τ % " ! τ & " ! + 𝑏 ! " τ % " " τ & " " + 𝑏 $ τ % # τ & # { / 𝑏 ! } !" ' ! $ ' ! % Predicted spatio-
Prediction heads. The output of the decoder is a set of refined time queries {Q t } T t=1 . They are jointly used for visual grounding and temporal localization to simultaneously obtain predictions for all frames of the video. In detail, normalized coordinates of all bounding boxes (2D center and size) b ∈ [0, 1] T ×4 are predicted with a 3-layer MLP. Probabilities of the start and the end of the output video tube, τs ∈ [0, 1] T and τe ∈ [0, 1] T , respectively, are predicted with 2-layer MLPs. At inference time, the start and end times of the output tube, ts and te , are computed by choosing the maximum of the joint start and end probability distribution (τ s , τe ) ∈ [0, 1] T ×T with invalid combinations where te ≤ ts masked out. The predicted spatiotemporal tube { bt } te t= ts is composed from bounding boxes bt predicted within the chosen start and end times ts and te .

Training loss

The input training data is in the form of a set of videos, where each video is annotated with a query sentence s and the corresponding video tube b composed of a set of bounding boxes and corresponding start and end times, t s and t e . Inspired by [START_REF] Rodriguez | Proposal-free temporal moment localization of a natural-language query in video using guided attention[END_REF], we construct a target start (respectively end) distribution τ s ∈ [0, 1] T (respectively τ e ) which follows a quantized Gaussian centered at t s ∈ [0, T -1] (respectively t e ) with standard deviation 1. We train our architecture with a linear combination of four losses

L = λ L1 L L1 ( b, b) + λ gIoU L gIoU ( b, b) +λ KL L KL (τ s , τe , τ s , τ e ) + λ att L att (A) (1)
where b ∈ [0, 1] 4(te-ts+1) denotes the normalized ground truth box coordinates and b the predicted bounding boxes and A ∈ [0, 1] T ×T denotes the temporal self-attention matrix. Finally, different λ • are scalar weights of the individual losses. L L1 is a L 1 loss on bounding box coordinates. L gIoU is a generalized "intersection over union" (IoU) loss [63] on the bounding boxes. Both L 1 and L gIoU are used for spatial grounding. L KL (τ s , τe , τ s , τ e ) is the Kullback-Leibler divergence loss measuring the distance between the predicted and the target start distribution as well as the distance between the predicted and the target end distribution [START_REF] Rodriguez | Proposal-free temporal moment localization of a natural-language query in video using guided attention[END_REF]. L att (A) is a guided attention loss [START_REF] Rodriguez | Proposal-free temporal moment localization of a natural-language query in video using guided attention[END_REF] that encourages weights corresponding to time queries outside of the temporal boundaries to be lower than the weights inside these boundaries. L KL and L att (A) are both used for temporal grounding. Losses are computed at each layer of the decoder following [START_REF] Carion | End-to-end object detection with transformers[END_REF].

Weight initialization

We initialize our architecture with weights from MDETR [START_REF] Kamath | MDETR -modulated detection for end-to-end multi-modal understanding[END_REF] pretrained on Flickr30k [START_REF] Bryan A Plummer | Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models[END_REF], MS COCO [START_REF] Chen | Microsoft COCO captions: Data collection and evaluation server[END_REF] and Visual Genome [START_REF] Krishna | Visual Genome: Connecting language and vision using crowdsourced dense image annotations[END_REF]. In detail, weights of our videotext encoder are initialized from the MDETR multi-modal encoder, except for the fast and aggregation modules. We also use the weights from the MDETR single-image multiobject decoder to initialize our multi-frame single-object space-time decoder, except for the temporal localization head. We show the benefit of this initialization notably by comparing it to an ImageNet initialization, i.e. using a visual backbone pretrained on ImageNet with a randomly initialized transformer, in Section 4.2. We also evaluate a MDETR-equivalent baseline in Section 4.2.

Experiments

This section demonstrates the effectiveness of our architecture and compares our method to the state of the art. We first introduce the datasets, evaluation metrics and imple-mentation details in Section 4.1. We then present ablation studies in Section 4.2. The comparison to the state of the art in spatio-temporal video grounding is given in Section 4.3. Finally, we show qualitative results in Section 4.4.

Experimental setup

Datasets. We evaluate our approach on the VidSTG [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF] and HC-STVG [START_REF] Tang | Human-centric spatio-temporal video grounding with visual transformers[END_REF] datasets. Both are annotated with spatio-temporal tubes corresponding to text queries. Vid-STG consists of 99,943 sentence descriptions with 44,808 declarative sentences and 55,135 interrogative sentences describing 79 types of objects appearing in 10,303 different videos. The dataset is divided into training, validation and test subsets with 80,684, 8,956 and 10,303 distinct sentences respectively, and 5,436, 602 and 732 distinct videos respectively. HC-STVG consists of videos in multi-person scenes, each annotated with one sentence referring to a person. For ablation, we use the second improved version of the dataset HC-STVG2.0 which is divided into training and validation subsets with 10,131 and 2,000 video-sentence pairs, respectively. The test set is not publicly available at the time of writing. To compare with prior work, we use the first version of the dataset HC-STVG1 which is divided into training and test subsets with 4,500 and 1,160 videosentence pairs, respectively. Evaluation metrics. We follow [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF] and define vIoU as vIoU = 1 |Su| t∈Si IoU ( bt , b t ) where S u (respectively S i ) is the set of frames in the union (respectively intersection) between the ground truth (GT) and the predicted timestamps. bt (respectively b t ) are the predicted (respectively GT) boxes at time t. To evaluate spatio-temporal video grounding, we use m vIoU , which is the average of vIoU . We also use vIoU @R, the proportion of samples for which vIoU > R. To isolate the evaluation of temporal localization, we use m tIoU which is the average of temporal IoU between the GT start and end and the predicted start and end. Likewise, to evaluate spatial grounding only, we use m sIoU , which is computed by using the GT start and end times. For ablations we report results averaged over all samples. More detailed ablation results presented separately for declarative and interrogative sentences in VidSTG are reported in Appendix Section C. We also report peak GPU memory usage during training (Mem.) to measure the memory footprint of alternative models. Implementation details. The visual backbone is ResNet-101 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF], the text encoder is RoBERTa [50] and the fast module f is a linear layer. Following [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF], we sample 5 frames per second for videos, and for videos with more than 200 sampled frames we uniformly sample 200 frames. We use hyper-parameters T = 200, N = 6, d = 256, λ L1 = 5, λ giou = 2, λ KL = 10 and λ att = 1. We train our networks for 10, 20 and 40 epochs on VidSTG, HC-STVG2.0 and HC-STVG1, respectively. The final model is selected based

Ablation studies

In this section, we ablate the hyper-parameters of our model and evaluate alternative design choices of the encoder and decoder. Unless stated otherwise, we use spatial frame resolution of 224 pixels and temporal stride k = 5. Space-time decoder. We first ablate the design choices of the proposed space-time decoder. We compare our full decoder model with variants without time encoding, without temporal self-attention and without both. The variant without both corresponds to a space-only decoder, similar to MDETR [START_REF] Kamath | MDETR -modulated detection for end-to-end multi-modal understanding[END_REF] applied independently to every frame. Table 1 shows that there is a substantial improvement over the space-only decoder when using both time encoding and temporal self-attention (+17.9% on vIoU @0.3 between rows 1 and 4). The gain comes mostly from the temporal localization (+22.0% on m tIoU ), while the spatial grounding moderately increases (+0.7% in m sIoU ). Furthermore, we can observe that the time encoding brings most of the gain (+13.4% on vIoU @0.3 between rows 1 and 3). Finally, the temporal self-attention results in an additional improvement (+4.5% on vIoU @0.3 between rows 3 and 4) over using time encoding only. Initialization. We now ablate the importance of initializing our model with pretrained MDETR [START_REF] Kamath | MDETR -modulated detection for end-to-end multi-modal understanding[END_REF] weights. In Table 2, we compare this initialization to ImageNet initialization, and a variant that does not transfer the spatial self-attention weights from MDETR decoder to the temporal self-attention in our space-time decoder. At pretraining time, this self-attention was used to model spatial relationships between different objects in the same image, while the temporal self-attention in our decoder models temporal relationships between the same object in different frames of a video. We find that pretraining is highly beneficial (+8.1% on vIoU @0.3 between rows 1 and 3), especially 3a) and the HC-STVG2.0 validation set (right, Table 3b).

Method

Pretraining Data

VidSTG HC-STVG1 Declarative Sentences

Interrogative Sentences m tIoU m vIoU vIoU@0.3 vIoU@0.5 m tIoU m vIoU vIoU@0.3 vIoU@0.5 m vIoU vIoU@0.3 vIoU@0.5 1. STGRN [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF] Visual Genome for the spatial grounding performance (+9.2% on m sIoU ). Additionally, we observe the benefit of using the spatial self-attention weights from the MDETR decoder to initialize the temporal self-attention in our decoder (+3.3% on vIoU @0.3 between rows 2 and 3). Impact of spatial resolution and temporal stride k. In this section, we analyze the impact of the frame resolution and the temporal stride k. In Table 3, we show that increasing the resolution is an important factor of performance for spatio-temporal video grounding, on both the VidSTG and HC-STVG2.0 datasets (see rows 2 and 4). However, it also results in significantly higher memory usage (16.2GB vs 23.7GB). As a consequence, the variant using temporal stride k = 1 is challenging to train on VidSTG with a resolution higher than 224 on a Tesla V100 32GB GPU. At a fixed 224 resolution, increasing the temporal stride k to 2 or 5 reduces the peak memory usage by 7.7GB or 12.1GB, respectively (see row 1 vs 2 or 3, respectively). Our proposed video-text encoder enables us to train on higher resolutions at a given memory usage. This leads to a better performance-memory trade-off (rows 4, 5, 6, 8) than the baseline variant with temporal stride k = 1 (row 1). In particular, the best spatio-temporal video grounding results (m vIoU and vIoU @R) over the two datasets are obtained with temporal stride k = 4 and resolution 352 (row 6). We note that as the resolution increases, performance gains obtained by its further increase are expected to be lower as they are limited by the original video resolution. For instance, the average video pixel height in VidSTG and HCSTVG2.0 is 440 and 490 pixels, respectively. Impact of the fast branch. Finally, we validate the importance of our fast branch by comparing, for the best variant, temporal stride k = 4 and resolution 352, our slow-fast video-text encoder to a slow-only variant that corresponds to f = 0 and g = 0. In this case the video-text features are the slow video-text features. By comparing rows 6 and 7 in Table 3, our fast branch significantly improves the spatiotemporal video grounding performance (+2.1% vIoU @0.3 on VidSTG and +2.9% vIoU @0.3 on HC-STVG2.0) with low computational memory overhead. This shows that the fast branch recovers useful spatio-temporal details lost by the temporal sampling operation in the slow branch. We further ablate the design of the fast and aggregation modules f and g in Appendix Section D.

Comparison to the state of the art

In this section, we compare our approach to state-of-theart methods in spatio-temporal video grounding. We report results for the model achieving the best validation results in the previous ablation studies, i.e., our space-time decoder with time encoding and temporal self-attention, temporal stride k = 4 and resolution 352. The focus of our work is on the spatio-temporal video grounding metrics (m vIoU and vIoU @R). As shown in Table 4, only using ImageNet to initialize the visual backbone (row 4), our TubeDETR performs competitively despite using less annotations. Furthermore, if we use MDETR initialization (row 5), our Tube-DETR outperforms by a large margin all previous methods (rows 1, 2 and 3) on both datasets. STGRN [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF] achieves similar m tIoU (measuring only temporal localization), but it defines a handcrafted set of possible window widths to tackle temporal localization, while we consider all possible windows, i.e. any starting frame i and ending frame j with i < j. These results demonstrate the excellent performance of our architecture for spatio-temporal video grounding.

Qualitative examples

We show qualitative examples of our predictions on the VidSTG test set in Figure 5. These examples show that our model is able to predict meaningful and accurate spatiotemporal tubes associated with the input text queries. In particular, in the first example, our model correctly detects the temporal moment corresponding to the cat biting the adult. In the second example, our model localizes the spatio-temporal tube corresponding to a man quickly grabbing a very small sports ball and in the third example it is able to localize the skis under the adult while skiing. However, as shown in the last example, it may fail to understand fine details in the query and the video. Note that the balloon and the ball are visually and semantically similar. A careful analysis is required to understand the difference. Furthermore, we provide visualizations of the different attention mechanisms of TubeDETR in Appendix Section A.

Conclusion

We have proposed TubeDETR, a novel transformerbased architecture for spatio-temporal video grounding. TubeDETR tackles this task with a space-time transformer decoder combined with a video-text encoder that efficiently encodes spatial and multi-modal interactions. We have demonstrated the effectiveness of our space-time decoder, and the benefits of our video-text encoder in terms of performance-memory trade-off. Finally, our approach outperforms state-of-the-art methods on two benchmarks, Vid-STG and HC-STVG. Future work could extend our spacetime decoder to detect multiple objects per frame or multiple events per video. Investigating more efficient alternatives to self-attention, such as the ones studied for natural language [START_REF] Beltagy | Longformer: The long-document transformer[END_REF][START_REF] Choromanski | Rethinking attention with performers[END_REF][START_REF] Kitaev | Reformer: The efficient transformer[END_REF][START_REF] Tay | Long range arena: A benchmark for efficient transformers[END_REF][START_REF] Wang | Linformer: Self-attention with linear complexity[END_REF][START_REF] Wu | Lite transformer with long-short range attention[END_REF][START_REF] Zaheer | Big bird: Transformers for longer sequences[END_REF], is another promising direction for future research.

of IDRIS under the allocation 2021-AD011011670R1 made by GENCI. The work was funded by a Google gift, the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute), the Louis Vuitton ENS Chair on Artificial Intelligence, the European Regional Development Fund under project IMPACT (reg. no. CZ.02.1.01/0.0/0.0/15 003/0000468). We thank S. Chen and J. Chen for helpful discussions and O. Bounou and P.-L. Guhur for proofreading.

A. Visualization of space, time and language attention patterns in the decoder

This section illustrates attention mechanisms of our space-time decoder over space, language and time for the spatio-temporal video grounding example presented in Figure 7. For this example the time-aligned cross-attention for the visual modality is also shown in Figure 7. We note that spatially, attention at each timestep is particularly focused on humans that are receiving the sports ball and gesturing. Additionally, the time-aligned cross-attention for the textual modality is illustrated in Figure 6. We observe that the words adult and grabs are the most attended overall, and that attention weights on the different words (e.g. sports and ball) vary over time. ts and te in Figure 6 denote the predicted start and end times of the output tube. Next, the temporal self-attention is illustrated in Figure 8. We notice long-range temporal interactions: a certain number of time queries attend to various temporally distant time queries, e.g. time queries located around the start of the video between the eighth and sixteenth frames.

B. Additional implementation details

In our transformer, the number of heads is 8 and the hidden dimension of the feed-forward layers is 2048. We set the initial learning rates to 1e -5 for the visual backbone, and 5e -5 for the rest of the network. The learning rate follows a linear schedule with warm-up for the text encoder and the learning rate is constant for the rest of the network. We use the AdamW optimizer [START_REF] Loshchilov | Decoupled weight decay regularization[END_REF] and weight-decay 1e -4 . Video data augmentation includes spatial random resizing, spatial random cropping preserving box annotations, and temporal random cropping preserving the annotated time interval. Dropout [START_REF] Srivastava | Dropout: A simple way to prevent neural networks from overfitting[END_REF] with probability 0.1 is applied in our transformer layers, and dropout with probability 0.5 is applied in the temporal localization head. We use exponential moving average with a decay rate of 0.9998, and an effective batch size of 16 videos. For temporal stride k = 1 the fast and aggregation modules in the encoder are not active, as their goal is to recover local spatial and temporal information when k > 1.

C. Detailed ablation results

In this section, we provide detailed results split by sentence type (declarative, interrogative) on the VidSTG dataset for the ablation studies presented in Section 4.2. (GB) m tIoU m vIoU vIoU@0.3 vIoU@0.5 m sIoU m tIoU m vIoU vIoU@0.3 vIoU@0.5 m sIoU Space-time decoder. We first provide detailed results for the ablation on our space-time decoder. The analysis is similar for both declarative and interrogative sentences. In detail, Table 5 shows that there is a substantial improvement over the space-only decoder when using both time encoding and temporal self-attention (+18.3% on vIoU @0.3 for declarative sentences and +17.5% on vIoU @0.3 for interrogative sentences between rows 1 and 4). The gain comes mostly from the temporal localization (+22.0% on m tIoU for declarative sentences and +22.1% on m tIoU for interrogative sentences), while the spatial grounding moderately increases (+0.9% in m sIoU for declarative sentences and +0.5% in m sIoU for interrogative sentences). Furthermore, we can observe that the time encoding brings most of the gain (+14.0% on vIoU @0.3 for declarative sentences and +12.9% on vIoU @0.3 for interrogatives sentences between rows 1 and 3). Finally, the temporal self-attention results in an additional improvement (+4.3% on vIoU @0.3 for declarative sentences and +4.6% on vIoU @0.3 for interrogative sentences between rows 3 and 4) over using time encoding only.

Initialization. We now provide detailed results for the ablation on our weight initialization. The analysis is similar for both declarative and interrogative sentences. In detail, Table 6 shows that pretraining is highly beneficial for spatio-temporal video grounding (+9.4% on vIoU @0.3 for declarative sentences and +6.9% on vIoU @0.3 for interrogative sentences between rows 1 and 3). The gain mainly comes from the spatial grounding performance (+11.7% on m sIoU for declarative sentences and +7.1% on m sIoU for interrogative sentences). Additionally, we observe the benefit of using the spatial self-attention weights from the MDETR decoder to initialize the temporal self-attention in our decoder (+3.2% on vIoU @0.3 for declarative sentences and +3.3% on vIoU @0.3 for interrogative sentences between rows 2 and 3).

Impact of spatial resolution and temporal stride k. In this section, we provide detailed results on the VidSTG dataset for the ablation on the impact of the spatial frame resolution and the temporal stride k. The analysis is similar for both declarative and interrogative sentences. In detail, Table 7 shows that increasing the resolution is an important factor of performance for spatio-temporal video grounding (see rows 2 and 4). Our proposed video-text encoder enables us to train on higher resolutions at a given memory usage. This leads to a better performance-memory tradeoff (rows 4, 5, 6, 8) compared to the baseline variant with temporal stride k = 1 (row 1). In particular, the best spatiotemporal video grounding results (m vIoU and vIoU @R) are obtained with temporal stride k = 4 and resolution 352 (row 6).

Impact of the fast branch. Finally, we provide detailed results on the VidSTG dataset for the ablation on the importance of our fast branch where we compare, for the best variant, temporal stride k = 4 and resolution 352, our slowfast video-text encoder to a slow-only variant. The analysis is similar for both declarative and interrogative sentences. By comparing rows 6 and 7 in Table 7, our fast branch significantly improves the spatio-temporal video grounding performance (+2.2% vIoU @0.3 for declarative sentences and +1.9% vIoU @0.3 for interrogative sentences) with low computational memory overhead. This shows that the fast branch recovers useful spatio-temporal details lost by the temporal sampling operation in the slow branch.

Figure 1 .

 1 Figure 1. Spatio-temporal video grounding requires reasoning about space, time, and language.

Figure 2 .

 2 Figure 2. TubeDETR model overview. All input video frames vt and the sentence s are first processed with a Visual Backbone and a Text Encoder. The resulting text and video features y0(s) and x0(v) are then jointly encoded with a Video-Text Encoder that computes spatial and multi-modal interactions for M short clips of k frames (about 1 second). The resulting video-text features F (v, s) are then decoded into the output spatio-temporal tube b using a Space-Time Decoder that jointly reasons about time, space and text over the entire video.

Figure 3 .

 3 Figure3. Video-Text Encoder takes as input a set of 2D flattened image features x0(v) together with a set of text features y0(s) from the query sentence, and outputs a set of video-text features F (v, s), one for each frame. Top: the Slow multi-modal branch first samples video features x p m , one from every k frames. Then it computes multi-modal interactions between the sampled features x p m and text features y0 using a transformer encoder. The temporal sampling reduces the number of video features in order to efficiently compute the attentionbased interactions. Bottom: lightweight "Fast visual-only" branch f processes features from all frames but without any attention layers for increased efficiency. Features from both branches are then combined in module g into the final set of per-frame features F (v, s).

Figure 4 .

 4 Figure 4. Space-Time Decoder. The decoder is composed of N repeated blocks. In each block, time queries qt successively attend to each other via temporal self-attention and to their respective time-aligned video-text features F (v, s) via time-aligned cross-attention. The cross-attention mask (bottom) indicates the non-zero weights (white) between the input HW + L video-language features for each of the T input frames (x-axis) and T time queries (y-axis). The cross-attention mask ensures that each time query qt only cross-attends to video-text features F (v, s) at the corresponding frame t, which significantly increases efficiency of the decoder and enables decoding entire videos of T frames. The temporal modelling over the entire length of the video is ensured by the temporal self-attention layers.

Query:Figure 5 .

 5 Figure 5. Qualitative examples of spatio-temporal tubes predicted by our model (light yellow), compared with ground truth (light green), on the VidSTG test set. The first three examples illustrate successful predictions of our method. In the last example the method confuses the small sports ball in the background with a balloon.

Figure 6 .

 6 Figure 6. Time-aligned cross-attention visualization (textual modality). Visualization of the attention weights between the time query (y-axis) and its time-aligned visually-contextualized text features (x-axis) at different times in our space-time decoder. These attention weights are averaged across all 8 heads and all 6 layers, and renormalized by the maximum weight at each timestep (i.e. each row) for the purpose of visualization. Lighter colors correspond to higher attention weights (see the colorbar on the right).

Query:Figure 7 .

 7 Figure 7. Time-aligned cross-attention visualization (visual modality). Top rows: Input frames with the predicted (yellow) and ground truth (green) spatio-temporal tubes overlaid. Bottom rows: Visualization of the attention weights between the time query and its timealigned text-contextualized visual features at different times in our space-time decoder. These attention weights are averaged across all 8 heads and all 6 layers, and renormalized by the maximum weight at each timestep for the purpose of visualization. Attention at each timestep is particularly focused on humans that are receiving the sports ball and gesturing.

Figure 8 .

 8 Figure 8. Temporal self-attention visualization. Visualization of the attention weights between the different time queries in our spacetime decoder. The column t corresponds to the weights of the different time queries for the time query at time t. These attention weights are averaged across all 8 heads and all 6 layers, and renormalized by the maximum weight at each timestep (i.e. each column) for the purpose of visualization. ts and te denote the predicted start and end times of the output tube. Lighter colors correspond to higher attention weights (see the colorbar on the right).

Table 1 .

 1 Effect of the time encoding and the temporal selfattention in our space-time decoder on the VidSTG validation set.

		Time Encoding	Self Attention	m tIoU m vIoU	vIoU @0.3	vIoU @0.5	m sIoU
	1.	✗		-	23.9	12.2 15.3 6.1	47.0
	2.	✗		Temporal 25.2	13.0 16.9 6.5	47.3
	3.	✓		-	41.7	21.3 28.7 17.4 46.5
	4.	✓		Temporal 45.9	24.3 33.2 22.0 47.7
		Pre-Training	Decoder Self-Attention Transfer	m tIoU m vIoU	vIoU @0.3	vIoU @0.5	m sIoU
	1.	✗		✗		42.8	18.8 25.1 15.6 38.5
	2.	✓		✗		43.8	22.4 29.9 19.1 46.5
	3.	✓		Temporal		45.9	24.3 33.2 22.0 47.7

Table 2 .

 2 Effect of the weight initialization for our model on the VidSTG validation set.on the best spatio-temporal video grounding performance on the validation set. For the largest dataset VidSTG, the optimization takes 2 days on 16 Tesla V100 GPUs. Further details are included in Appendix Section B.

Table 3 .

 3 Comparison of performance-memory trade-off with various temporal strides k, spatial resolutions (Res.), with or without the fast branch in our video-text encoder, on the VidSTG validation set (left, Table

									(b) HC-STVG2.0
	Temp. Stride	m tIoU m vIoU vIoU@0.3 vIoU@0.5 m sIoU	Mem. (GB)	Fast Res.	Temp. Stride	m tIoU m vIoU vIoU@0.3 vIoU@0.5 m sIoU	Mem. (GB)
	1. -224 1	46.5 25.2	34.1	23.0	49.1 23.9	1. -224 1	52.8 35.0	55.3	28.3	63.9 14.3
	2. ✓ 224 2	46.0 25.0	34.3	22.9	49.0 16.2	2. ✓ 224 2	53.7 35.8	56.7	29.6	64.3 10.2
	3. ✓ 224 5	45.9 24.3	33.2	22.0	47.7 11.8	3. ✓ 224 5	53.2 35.0	54.5	29.0	63.2 8.0
	4. ✓ 288 2	46.4 25.9	35.0	23.9	50.5 23.7	4. ✓ 288 2	53.9 36.4	58.1	30.7	65.4 13.9
	5. ✓ 320 3	46.4 25.9	35.7	23.7	50.7 23.6	5. ✓ 320 3	53.6 36.2	57.5	30.4	65.2 13.8
	6. ✓ 352 4	46.9 26.2	36.1	24.1	50.7 24.4	6. ✓ 352 4	53.9 36.4	58.8	30.6	64.9 14.3
	7. ✗ 352 4	46.6 24.8	34.0	21.6	48.3 18.1	7. ✗ 352 4	53.1 34.7	55.9	27.4	63.0 11.3
	8. ✓ 384 5	46.8 26.0	35.5	24.0	50.4 26.1	8. ✓ 384 5	53.6 36.3	57.5	30.4	65.3 15.2

Table 4 .

 4 Comparison to the state of the art on the VidSTG test set and the HC-STVG1 test set.

			48.5	19.8	25.8	14.6	47.0	18.3	21.1	12.8	-	-	-
	2. STGVT [72]	Visual Genome + Conceptual Captions	-	21.6	29.8	18.9	-	-	-	-	18.2	26.8	9.5
	3. STVGBert [68]	ImageNet + Visual Genome + Conceptual Captions	-	24.0	30.9	18.4	-	22.5	26.0	16.0	20.4	29.4	11.3
	4. TubeDETR (Ours)	ImageNet	43.1	22.0	29.7	18.1	42.3	19.6	26.1	14.9	21.2	31.6	12.2
	5. TubeDETR (Ours)	ImageNet + Visual Genome + Flickr + COCO	48.1	30.4	42.5	28.2	46.9	25.7	35.7	23.2	32.4	49.8	23.5

Table 6 .

 6 Effect of the weight initialization for our model on the VidSTG validation set.

	Time	Self	Declarative Sentences	Interrogative Sentences
	Encoding	Attention	m tIoU m vIoU	vIoU @0.3	vIoU @0.5	m sIoU m tIoU m vIoU	vIoU @0.3	vIoU @0.5	m sIoU

Table 7 .

 7 Comparison of performance-memory trade-off with various temporal strides k, frame spatial resolutions (Res.), with or without the fast branch in our video-text encoder, on the VidSTG validation set.

	1. -224 1	46.9 27.6	37.7	25.7	54.2 46.1 23.3	31.3	20.8	44.9 23.9
	2. ✓ 224 2	46.6 27.4	38.0	25.7	54.3 45.5 23.0	31.3	20.7	44.7 16.2
	3. ✓ 224 5	46.4 26.6	36.1	24.7	52.8 45.6 22.5	30.8	19.8	43.6 11.8
	4. ✓ 288 2	47.0 28.2	38.3	26.3	55.7 46.0 24.1	32.4	22.0	46.3 23.7
	5. ✓ 320 3	46.9 28.3	39.2	26.4	56.0 45.9 24.0	32.8	21.5	46.4 23.6
	6. ✓ 352 4	47.2 28.7	39.6	27.1	56.4 46.6 24.2	33.2	21.7	46.2 24.4
	7. ✗ 352 4	47.1 27.1	37.4	24.1	53.7 46.2 22.9	31.3	19.6	44.0 18.1
	8. ✓ 384 5	47.4 28.4	38.9	27.0	55.3 46.4 24.0	32.8	21.7	45.6 26.1

Czech Institute of Informatics, Robotics and Cybernetics at the Czech Technical University in Prague.

Acknowledgements. This work was granted access to the HPC resources

Appendix

In this Appendix, we present additional visualizations of the different attention mechanisms in our space-time decoder in Section A. Section B provides additional implementation details. We then give detailed results for ablations in Section 4.2 on the VidSTG dataset [START_REF] Zhang | Where does it exist: Spatio-temporal video grounding for multi-form sentences[END_REF] split by sentence type in Section C. Next we present an ablation of our fast and aggregation modules in Section D. Finally we discuss broader impact in Section E.

D. Additional Experiments

In this section, we provide additional ablation studies. As in the ablations presented Section 4.2, unless stated otherwise, we use spatial frame resolution of 224 pixels and temporal stride k = 5. Design of the modules. Here we further ablate the fast and aggregation modules f and g used in our dual-branch encoder. We report results in Table 8. The comparison between our slow-fast design (row 6) and the slow-only variant (row 2) is discussed in Section 4.2. Likewise, we compare our slow-fast design to a fast-only variant (row 1). The fast-only variant does not use the slow multi-modal branch, in which case the videotext features are the fast visual-only features concatenated with the text features. As shown in Table 8, our slow-fast design outperforms the fast-only variant, showing the importance of the slow multi-modal branch. We further compare the design of our fast and aggregation modules f and g (row 6) to other alternatives: row 3, a variant with the same primitives f and g but with f operating on features pooled over the spatial dimension; row 4, a variant which uses the same fast module f but a gating aggregation module

where σ is the sigmoid function; row 5, a variant that uses the same aggregation module g but a fast temporal transformer module f , which models temporal interactions between spatiallydetailed features. As shown in Table 8, our design outperforms row 3, showing that preserving spatial information for each frame is crucial for the effectiveness of the fast branch. Additionally, our design slightly improves over row 4, indicating that further forcing the network to use the slow branch is not helpful. Finally, our design slightly improves over row 5, suggesting that additional modeling of temporal interactions in our encoder is not necessarily helpful.

E. Broader Impact

This work is a contribution to spatio-temporal video grounding and its potential positive or negative impacts depend on the application. Such models may be used for video surveillance and hence lead to questionable use. On the other hand, we believe that such methods could improve ex-plainability of vision and language models which may help to understand some of their biases. This work also ablates memory usage when learning such models and thus could help promote development of lighter models with a reduced impact on the environment.


Raheleh Biglari

Joost Mertens

Joachim Denil

Towards Real-time Adaptive Approximation

Keywords: cyber physical systems, real-time, uncertainty, adaptation, abstraction

Cyber-physical systems (CPS) are real-time systems that operate in dynamic and non-deterministic environments. Models are often used for control and prediction, however do not reason on the trade-off between real-time constraints and uncertainty. This paper presents a conceptual model to reason on adaptive approximation in such systems. Furthermore, we envision a framework to allow the adaptivity of models, balancing between uncertainty and the real-time behavior of the system.

I. INTRODUCTION

Cyber-physical systems (CPS) are engineered systems that have tight integration between the cyber part (computation and networking) and its physical components [START_REF] Lee | Cyber physical systems: Design challenges[END_REF]. Examples include but are not limited to industry 4.0, automotive, and aerospace. Engineered systems have a goal to achieve in the context of the system, e.g. an autonomous vehicle needs to pilot the environment while not harming anyone. To achieve this goal, multiple decision models are needed and combined. For example, an autonomous vehicle has low-level control to accelerate and brake, tactical decision-making models for path planning, and strategic models to decide which roads to avoid, e.g., as an accident occurred. All of these decision models implement some form of (feedback) control.

Cyber-physical systems of systems are CPS that exhibit the features of a system of systems (SoS). They are large and spatially distributed, have distributed control, and autonomic behavior where parts of the SoS can join or leave the system [START_REF] Engell | Cyber physical sos-definition and core research and development areas[END_REF]. As such it is a system composed from different CPS where each part of the system contributes to the overall goal of the CPSoS. The engineering of such a CPSoS has to address the complex situations and, environments of the system, which is characterized by ambiguity, high uncertainty and emergence [START_REF] Sousa-Poza | System of systems engineering: an emerging multidiscipline[END_REF]. CPSoS have to allow for collaborative decision making and, as such, need to be aware of the state of the other constituents of the system [START_REF] Engell | Cyber physical sos-definition and core research and development areas[END_REF].

CPS and CPSoS operate in a very dynamic environment where lots of uncertainty is present [START_REF] Zhang | Understanding uncertainty in cyber-physical systems: a conceptual model[END_REF]. Uncertainty points to the lack of information that is available about the system or its environment. An autonomous vehicle might have uncertainties about its own position in the system and about the direction and velocities of other vehicles and road users. Cyber-physical Raheleh Biglari is funded by the BOF fund at the University of Antwerp. Joost Mertens is funded by the Research Foundation -Flanders (FWO) through strategic basic research grant 1SD3421N. systems are also real-time systems which means that the time at which a decision is made is as important as the decision itself. This means that during design time, the system is analyzed to ensure that all the deadlines of the control components are met in the worst-case.

One way to deal with the contradiction of better performance and reduced cost in CPS is to allow adaptivity at runtime and to change the underlying decision and estimation models such that they are sufficient for computing the control actions but at the same time computationally less intensive. Techniques that abstract or approximate models are commonly available in the literature, e.g., surrogate modeling [START_REF] Caughlin | Summary of model abstraction techniques[END_REF].

In this short paper, we look at different dimensions of the problem to allow for such a run-time adaptation of the underlying control and decision models with more abstract and approximate models. The rest of the paper is organized as follows: section II introduces our running example, section III describes the challenges in our work. We also present use case evaluation results. In section IV we describe our strategy to dealing with the challenges. We provide related works in section V and section VI presents our conclusion and discusses future directions.

II. RUNNING EXAMPLE

We use a lane change control algorithm to show the challenges of introducing adaptive abstraction and approximation in a real-time context. While we do not aim precisely at this class of control algorithms, lane changing allows for visual and intuitive reasoning over the problem space.

Lane changing algorithms control the lateral direction of the vehicle. The scenario throughout this paper is shown in Figure 1. The ego car (in dark blue) tries to change the lane in between two other cars. The velocity and acceleration vectors of the two cars is shown as vectors v 1 ,v 2 , a 1 and a 2 . The front car is lightly decelerating while the back car is lightly accelerating. Multiple algorithms have been proposed in the literature to solve such lane changing problems, e.g. [START_REF] Bevly | Lane change and merge maneuvers for connected and automated vehicles: A survey[END_REF]. In the context of this paper, we use a Simulink provided model to simulate the lane changing behavior. Figure 2 shows the high-level architecture of the lane changing algorithm. The algorithm uses Frenet Coordinate System, which represents the position of the car on the road more intuitively than traditional (x, y) coordinates.This algorithm also uses a prediction step to predict the trajectories of the different actors. Afterward, path planning takes care of finding a good path in the world. Finally, a model-predictive controller steers the vehicle over the planned path.

In the rest of the paper, we focus on the prediction step of the other vehicles. The prediction step simulates a trajectory relative to the ego car for each vehicle in the environment. The component receives information on the lateral and longitudinal position, velocity, and acceleration of the vehicles. In the default case, the prediction step uses a constant velocity model to predict the vehicle's position at multiple time-steps in a three-second window:s(t) = v * t + s 0 (with s the relative distance to the ego-car, v the relative speed to the ego vehicle, and s 0 the initial distance). However, we can imagine much more detailed models that also take the vehicle's acceleration into account or even more detailed models that simulate the complex decision-making in each of the vehicles.

III. CHALLENGES

Using a model of a car performing a lane change such as the scenario in Section II, we elaborate on identified challenges. The model is simulated with Simulink.

A. Model Prediction Uncertainty

Each of the different models has a different amount of predictive power. As such, more detailed models typically have lesser prediction uncertainty. Figure 3 depicts the prediction of the scenario with two different models over three time-steps. The top control bar is the uncertain position of the cars using a constant velocity model. The lower control bar shows the uncertain position using a constant acceleration model.

To reason over using different alternative models, we need to map the prediction uncertainty of all the different models. Two types of uncertainty are typically present in modeling and simulation: aleatoric and epistemic uncertainty. Aleatory uncertainty is known as stochastic uncertainty and is due to probabilistic variability. Epistemic uncertainty is the uncertainty that occurs because of the lack of knowledge [START_REF] Oberkampf | Verification and validation in scientific computing[END_REF].

With the simulation model, we demonstrate how the constant velocity and constant acceleration models have different predictive power. Figure 4 shows the velocity profile of car 2 and the L2-norm (Euclidean distance) between 4 predictions and the true location of that car. The number behind each prediction tells us how many steps (of 0.1s) in the future this prediction is. The simulation includes uncertainty on the sensor inputs of the ego vehicle, which results in slightly jagged error traces. The velocity profile shows that the car accelerates to 22 m/s. Afterward, it holds a constant velocity. We observe that under acceleration, the constant velocity model has a continuous error that only diminishes as the vehicle approaches constant velocity. The constant acceleration model performs better when conditions are constant, that is, positive, negative, or 0 acceleration, and shows the largest error when the predictions cross transitions in acceleration. Such transitions can be seen at t = 0s, where the initial acceleration measurement is 0, yet the car is already accelerating at 0.8m/s 2 , and at t = 2.4s, when the car stops accelerating. Under constant velocity, both models perform equally. From the results, we can say that the constant acceleration model has better predictive power, given the generally smaller errors.

B. Dynamic Environment

The environment in which systems operate is dynamic. Cars enter and leave the operating environment of the system. Some highways have more lanes than others. Even more, not all of the actors within the environment are of the same type. In a traffic environment, we have pedestrians, bicycles, cars, trucks, and buses that all behave differently. The prediction component of the lane change algorithm has to set up this dynamic environment each time and select the most appropriate models to include.

C. Real-time Constraints

Often our cyber-physical systems are also real-time systems. This means that the time at which the computation result is available is as important as that result itself. During the design of such systems, care is taken that the computations are finished before the expiry of the deadline of the computation. Different analytical techniques are available to check that this is correct. However, in the dynamic environment described above, this is difficult. How many cars, pedestrians, and bicycles are in the system's environment is unknown at design time. However, we still need a prediction of the behavior of each of these actors in the example within a certain time-span.

With the simulation model, we can demonstrate the impact computations can have on the number of predictions. Figure 5 shows the experimental cumulative distribution function of the profiled execution times of the state predictor the constant velocity and acceleration models. 400 simulations were run for each model. Although profiling a Simulink model does not yield real-time results, it does allow us to relatively compare the computational burden of its blocks, We observe that, on average, the constant acceleration model requires 22.74% more computation time than the constant velocity model. This implies that for predicting 4 other cars with constant acceleration, 5 cars with constant velocity could be computed.

IV. APPROACH

This section details our approach to handle these challenges. In the first part of this section, we look at a conceptual manner on reasoning over substitutability of models. We look at the effect of approximating a model with a surrogate model and how it impacts a decision making algorithm. The conceptual framework is used as the foundation for a framework that allows for the run-time adaptation of a system where models can be swapped by more approximate models based on the context of the system and the available library of models.

A. Language Engineering Framework

To reason on the challenges, we propose an adapted version of the conceptual framework proposed by Barroca, Kuhne and Vangheluwe [START_REF] Barroca | Integrating language and ontology engineering[END_REF]. The conceptual framework in Figure 6 integrates ontological and language engineering. We extended the framework with two different models with different approximations, and the layer of the decision-making algorithms. The linguistic level starts with a simulation model. The simulation model has semantics (denoted by [[.]]), which results in a simulation behavior trace. However, the trace might not be the quantity of interest of the decision-making algorithm or for reasoning over the logical behavior of the system. A function f () (e.g. integrating the signal) transforms the trace into some quantity of interest, here called the prediction value. A logical property is on the ontological level where it gets a real-world meaning, e.g. will the two cars collide? The logical property is a Boolean value; either the cars collide, or they do not collide. Another function g() is used to transform between the quantity of interest and the logical property. Decision algorithms typically work directly with the prediction value but implicitly encode the transform within its algorithm. We, therefore, show the direct link between the logical property and the decision-making model.

The framework is analog for a model that is approximated. It reasons on the same logical property, however, using a more approximate model introduces uncertainty. This means that the function g () should give the same answer as the original model, except with more uncertainty. If the uncertainty is within bounds, the original model can be substituted with the more approximate one. This bound is defined by some metric, which is the tolerance to this change in the logical property (and hence later in the decision that was made by the decision-making model). The tolerance depends on a number of factors. In our lane changing example, the tolerance is based on (a) the goal model: do I actually want to change lanes, or do I want to stay in the same lane? When staying in the same lane, the cars on other lanes are maybe less important. (b) the context or environment of the system: is the car close-by (less tolerance) or far away (more tolerance) (c) the decision-making model itself: is the algorithm itself more or less tolerant to uncertainties?

B. Adaptive abstraction and approximation for real-time systems

Based on the insights provided by the conceptual framework, we propose an architecture for adaptive abstraction and approximation for real-time systems. The architecture is shown in Figure 7. The high-level architecture is based on the MAPE-K architecture [START_REF] Kephart | The vision of autonomic computing[END_REF]. MAPE-K is a high-level control loop for self-adaptive systems. The managed system is, in our case, the embedded system running the control application for lane changing. The MAPE-K loop starts with a Monitor-phase where the necessary (processed) sensor data, the current goal function and the decision-maker are communicated to the adaptation mechanism. Here some processing occurs to allow for easier Analysis. The analysis phase starts by updating a model tree. This model tree contains, in the ordered branches, all realworld objects that are passed by the sensor data. In the running example, we only have two objects: the two cars. It uses the (processed) sensor data to add or remove objects from the model tree incrementally. The Model Selection activity updates or selects the different models for each object in the model tree. The update is based on the goal, context and decision model, the quantified tolerances, and the available models with uncertainty quantification. The combination of these Knowledge items result in a set of rules to decide if a certain model can or cannot be used in this specific instance. Furthermore, the tree is also ordered with the most important objects in the first branches, and the most appropriate model in the first branch. In our case, the acceleration model is placed before the constant velocity model. If another car was present at a larger distance, the constant vehicle model would be first, and an empty model second branch. Using the accelerated model would not make sense as the tolerance for the decision-maker is high. The empty model is present, as the non-computing of the model reduces the execution time significantly but reduces the performance of the system. Finally, real-time constraints are imposed on top of the model tree to prune infeasible solutions. After the analysis phase, a set of feasible solutions is left. Based on this set of solutions, the co-simulation scheme is adapted and a master is generated that enables execution of the simulation. Note that each cosimulation unit contains the different possible models (possibly an empty model) for fast adaptation. Finally, in Execute, the scheduler in the Managed system is updated.

The scheduler itself is an adaptive mixed-criticality scheduler based on [START_REF] Guan | A design that incorporates adaptive reservation into mixed-criticality systems[END_REF]. This allows for responsiveness to overload conditions and imperfections in the execution time measurement of each co-simulation unit.

C. Discussion

This paper shows how to deal with the trade-off between uncertainty and real-time behaviour using models at different approximation levels. Consider if the number of cars increases in a scenario, the ECU will not have sufficient time to compute a prediction of all the different models.

The proposed conceptual model solves the dynamic environment where you cannot reason over real-time behaviour as worst-case bounds or where fallbacks in the decision logic are necessary. This solution needs computation of the MAPE-K loop and switching of models.

In this research, we address Tolerance Quantification. We need to be able to evaluate the tolerance of the decision making algorithm, since it is one of the model selection criteria. Offline experiments are needed to see how a decision making algorithm responds to uncertainty. In the example, it is the tolerance to the uncertain distance and velocity vector that must be quantified.

V. RELATED WORK

In previous work [START_REF] Bosmans | Towards evaluating emergent behavior of the internet of things using large scale simulation techniques (wip)[END_REF]- [START_REF] Bosmans | Adaptivity in multi-level traffic simulation using experimental frames[END_REF], we worked on the adaptivity of large scale simulations with surrogates. However, none of these techniques use a quantification of tolerance or reason over the real-time behaviour of the system.

The two most related techniques to our defined methods are mixed criticality systems and the imprecise computation model. Most of the complex embedded systems like automotive and avionic industries are mixed criticality systems. These systems deal with task-priority scheduling regarding execution time [START_REF] Burns | Mixed criticality systems-a review[END_REF]. The imprecise computation is also a technique to deal with transient overload and improve real-time fault tolerance. This approach ensures that all critical tasks never miss their deadlines [START_REF] Liu | Imprecise computations[END_REF]. Both techniques do not take the uncertainty of the models into account but allow for adaptation based on real-time citeria.

VI. CONCLUSION AND FUTURE WORK

In this paper, we presented a conceptual model for reasoning on adaptive approximation in a dynamic environment. We used a Simulink model for the simulation of the lane change control algorithm as a visual and tangible use case. Guided by it, we identify 3 main challenges faced for real-time adaptive approximation: model prediction uncertainty, dynamicness of environments and real-time constraints. To handle those challenges, we envisioned an integrated framework for adaptive approximation in CPS that balances the uncertainty and real-time behavior of the system. In the future, we aim to implement the framework with a supporting architecture, methods, and techniques to reason over the use of self-adaptive approximations and abstractions at runtime. We also want to create an appropriate modeling language and supporting techniques to find better runtime deployment solutions.

Fig. 1 .

 1 Fig. 1. Lane changing scenario.

Fig. 2 .

 2 Fig. 2. Causal Block Diagram of the Lane Change Algorithm

Fig. 3 .

 3 Fig. 3. Prediction of the car position on three time steps within the time window, relative to the leading car. On each car, the prediction uncertainty of two different models is shown, one solid, one dashed.

Fig. 4 .

 4 Fig. 4. Car 2's velocity profile, compared with the L2 errors made by the constant velocity and acceleration prediction models.

Fig. 5 .

 5 Fig. 5. Experimental CDF of the profiled execution times of both models.

Fig. 6 .

 6 Fig. 6. Conceptual framework.

Fig. 7 .

 7 Fig. 7. Real-time Adaptive Abstraction and Approximation Architecture