Temporal Context Aggregation for Video Retrieval with Contrastive Learning

We address the problem of video representation learning for Near-Duplicate Video Retrieval (NDVR), Fine-grained Incident Video Retrieval (FIVR), and Event Video Retrieval (EVR) tasks. In our setting, the dataset is two-split: the core and distractor. The core subset contains pair-wise labels describing which two videos are similar (near duplicate, complementary scene, same event, etc.). And the distractor subset contain large quantities of negative samples to make the retrieval task more challenging.

We only consider the RGB data of the videos. Given raw pixels ($\mathbf{x}_{r}\in\mathbb{R}^{m\times n\times f}$), a video is encoded into a sequence of frame-level descriptors ($\mathbf{x}_{f}\in\mathbb{R}^{d\times f}$) or a compact video-level descriptor ($\mathbf{x}_{v}\in\mathbb{R}^{d}$). Take the similarity function as $\text{sim}(\cdot,\cdot)$, the similarity of two video descriptors $\mathbf{x}_{1},\mathbf{x}_{2}$ can be denoted as $\text{sim}(\mathbf{x}_{1},\mathbf{x}_{2})$. Given these, our task is to optimize the embedding function $f(\cdot)$, such that $\text{sim}\left(f\left(\mathbf{x}_{1}\right),f\left(\mathbf{x}_{2}\right)\right)$ is maximized if $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are similar videos, and minimized otherwise. The embedding function $f(\cdot)$ typically takes a video-level descriptor $\mathbf{x}\in\mathbb{R}^{d}$ and returns an embedding $f(\mathbf{x})\in\mathbb{R}^{k}$, in which $k\ll d$. However, in our setting, $f(\cdot)$ is a temporal context aggregation modeling module, thus frame-level descriptors $\mathbf{x}\in\mathbb{R}^{d\times f}$ are taken as input, and the output can be either aggregated video-level descriptor ($f(\mathbf{x})\in\mathbb{R}^{d}$) or refined frame-level descriptors ($f(\mathbf{x})\in\mathbb{R}^{d\times f}$).

According to the results reported in  [31] (Table 2), we select iMAC [14] and modified $\text{L}_{3}$-iMAC [31] (called $\text{L}_{3}$-iRMAC) as our benchmark frame-level feature extraction methods. Given a pre-trained CNN network with $K$ convolutional layers, $K$ feature maps $\mathcal{M}^{k}\in\mathbb{R}^{n_{d}^{k}\times n_{d}^{k}\times c^{k}}(k=1,\dots,K)$ are generated, where $n_{d}^{k}\times n_{d}^{k}$ is the dimension of each feature map of the $k^{\text{th}}$ layer, and $c^{k}$ is the total number of channels.

For iMAC feature, the maximum value of every channel of each layer is extracted to generate $K$ feature maps $\mathcal{M}^{k}\in\mathbb{R}^{c^{k}}$, as formulated in Eq. 1:

$$v^{k}(i)=\max\mathcal{M}^{k}(\cdot,\cdot,i),\quad i=1,2,\dots,c^{k}\,,$$

(1)

where $v^{k}$ is a $c^{k}$-dimensional vector that is derived from max pooling on each channel of the feature map $\mathcal{M}^{k}$.

Max pooling with different kernel size and stride are applied to every channel of different layers to generate $K$ feature maps $\mathcal{M}^{k}\in\mathbb{R}^{3\times 3\times c^{k}}$ in the original $\text{L}_{3}$-iMAC feature. Unlike its setting, we then follow the tradition of R-MAC [56] to sum the $3\times 3$ feature maps together, then apply $\ell_{2}$-normalization on each channel to form a feature map $\mathcal{M}^{k}\in\mathbb{R}^{c^{k}}$. This presents a trade-off between the preservation of fine-trained spatial information and low feature dimensionality (equal to iMAC), we denote this approach as $\text{L}_{3}$-iRMAC.

For both iMAC and $\text{L}_{3}$-iRMAC, all layer vectors are concatenated to a single descriptor after extraction, then PCA is applied to perform whitening and dimensionality reduction following the common practice [23, 31], finally $\ell_{2}$-normalization is applied on each channel, resulting in a compact frame-level descriptor $\mathbf{x}\in\mathbb{R}^{d\times f}$.

We adopt the Transformer [57] model for temporal context aggregation. Following the setting of [13, 64], only the encoder structure of the Transformer is used. With the parameter matrices written as $W^{Q},W^{K},W^{V}$, the entire video descriptor $\mathbf{x}\in\mathbb{R}^{d\times f}$ is first encoded into Query $Q$, Key $K$ and Value $V$ by three different linear transformations: $Q=\mathbf{x}^{\top}W^{Q}$, $K=\mathbf{x}^{\top}W^{K}$ and $V=\mathbf{x}^{\top}W^{V}$. This is further calculated by the self-attention layer as:

$$\text{Attention}(Q,K,V)=\text{softmax}\left(\frac{QK^{\top}}{\sqrt{d}}\right)V\,.$$

(2)

The result is then taken to the LayerNorm layer [2] and Feed Forward Layer [57] to get the output of the Transformer encoder, i.e., $f_{\text{Transformer}}(\mathbf{x})\in\mathbb{R}^{d\times f}$. The multi-head attention mechanism is also used.

With the help of the self-attention mechanism, Transformer is effective at modeling long-term dependencies within the frame sequence. Although the encoded feature keeps the same shape as the input, the contextual information within a longer range of each frame-level descriptor is incorporated. Apart from the frame-level descriptor, by simply averaging the encoded frame-level video descriptors along the time axis, we can also get the compact video-level representation $\overline{f}(\mathbf{x})\in\mathbb{R}^{d}$.

If we denote $\mathbf{w}_{a},\mathbf{w}_{p},\mathbf{w}_{n}^{j}(j=1,2,\dots,N-1)$ as the video-level representation before applying normalization of the anchor, positive, negative examples, we get the similarity scores by: $s_{p}=\left.\mathbf{w}_{a}^{\top}\mathbf{w}_{p}\middle/\left(\left\|\mathbf{w}_{a}\right\|\left\|\mathbf{w}_{p}\right\|\right)\right.$ and $s_{n}^{j}=\left.\mathbf{w}_{a}^{\top}\mathbf{w}_{n}^{j}\middle/\left(\left\|\mathbf{w}_{a}\right\|\left\|\mathbf{w}_{n}^{j}\right\|\right)\right.$. Then the InfoNCE [40] loss is written as:

$$\mathcal{L}_{\text{nce}}=-\log\frac{\exp\left(s_{p}/\tau\right)}{\exp\left(s_{p}\right)+\sum_{j=1}^{N-1}\exp\left(s_{n}^{j}/\tau\right)}\,,$$

(3)

where $\tau$ is a temperature hyper-parameter [63]. To utilize more negative samples for better performance, we borrow the idea of the memory bank from [63]. For each batch, we take one positive pair from the core dataset and randomly sample $n$ negative samples from the distractors, then the compact video-level descriptors are generated with a shared encoder. The negative samples of all batches and all GPUs are concatenated together to form the memory bank. We compare the similarity of the anchor sample against the positive sample and all negatives in the memory bank, resulting in $1$ $s_{p}$ and $kn$ $s_{n}$. Then the loss can be calculated in a classification manner. The momentum mechanism [17] is not adopted as we did not see any improvement in experiments. Besides the InfoNCE loss, the recent proposed Circle Loss [53] is also considered:

$$\mathcal{L}_{\text{circle}}=-\log\frac{\exp(\gamma\alpha_{p}(s_{p}-\Delta_{p}))}{\exp(\gamma\alpha_{p}(s_{p}-\Delta_{p}))+\sum\limits_{j=1}^{N-1}\exp(\gamma\alpha_{n}^{j}(s_{n}^{j}-\Delta_{n}))}$$

(4)

where $\gamma$ is the scale factor(equivalent with the parameter $\tau$ in Eq. 3), and $m$ is the relaxation margin. $\alpha_{p}=\left[1+m-s_{p}\right]_{+},\alpha_{n}^{j}=\left[s_{n}^{j}+m\right]_{+},\Delta_{p}=1-m,\Delta_{n}=m$. Compared with the InfoNCE loss, the Circle loss optimizes $s_{p}$ and $s_{n}$ separately with adaptive penalty strength and adds within-class and between-class margins.

In the recent work of Khosla et al. [28], the proposed batch contrastive loss is proved to focus on the hard positives and negatives automatically with the help of feature normalization by conducting gradient analysis, we further reveal that this is the common property of Softmax loss and its variants when combined with feature normalization. For simplicity, we analyze the gradients of Softmax loss, the origin of both InfoNCE loss and Circle loss:

$$\mathcal{L}_{\text{softmax}}=-\log\frac{\exp\left(s_{p}\right)}{\exp\left(s_{p}\right)+\sum_{j=1}^{n-1}\exp\left(s_{n}^{j}\right)}\,,$$

(5)

the notation is as aforementioned. Here we show that easy negatives contribute the gradient weakly while hard negatives contribute greater. With the notations declared in Section 3.4, we denote the normalized video-level representation as $\mathbf{z}_{*}=\left.\mathbf{w}_{*}\middle/\left\|\mathbf{w}_{*}\right\|\right.$, then the gradients of Eq. 5 with respect to $\mathbf{w}_{a}$ is:

		$\displaystyle\frac{\partial\mathcal{L}_{\text{softmax}}}{\partial\mathbf{w}_{a}}=\frac{\partial\mathbf{z}_{a}}{\partial\mathbf{w}_{a}}\cdot\frac{\partial\mathcal{L}_{\text{softmax}}}{\partial\mathbf{z}_{a}}$		(6)
		$\displaystyle=\frac{1}{\left\|\mathbf{w}_{a}\right\|}\left(\mathbf{I}-\mathbf{z}_{a}\mathbf{z}_{a}^{\top}\right)\left[\left(\sigma(\mathbf{s})_{p}-1\right)\mathbf{z}_{p}+\sum_{j=1}^{N-1}\sigma(\mathbf{s})_{n}^{j}\mathbf{z}_{n}^{j}\right]$
		$\displaystyle\propto\overbrace{(1-\sigma(\mathbf{s})_{p})[(\mathbf{z}_{a}^{\top}\mathbf{z}_{p})\mathbf{z}_{a}-\mathbf{z}_{p}]}^{\text{positive}}+\underbrace{\sum_{j=1}^{N-1}\sigma(\mathbf{s})_{n}^{j}[\mathbf{z}_{n}^{j}-(\mathbf{z}_{a}^{\top}\mathbf{z}_{n}^{j})\mathbf{z}_{a}]}_{\text{negatives}}\,,$

where $\sigma(\mathbf{s})_{p}=\left.\exp\left(s_{p}\right)\middle/\left[\exp\left(s_{p}\right)+\sum_{j=1}^{N-1}\exp\left(s_{n}^{j}\right)\right]\right.$, and $\sigma(\mathbf{s})_{n}^{j}=\left.\exp\left(s_{n}^{j}\right)\middle/\left[\exp\left(s_{p}\right)+\sum_{j=1}^{N-1}\exp\left(s_{n}^{j}\right)\right]\right.$ following the common notation of the softmax function. For an easy negative, the similarity between it and the anchor is close to -1, thus $\mathbf{z}_{a}^{\top}\mathbf{z}_{n}^{j}\approx-1$, and therefore

$$\sigma(\mathbf{s})_{n}^{j}\left\|\left(\mathbf{z}_{n}^{j}-\left(\mathbf{z}_{a}^{\top}\mathbf{z}_{n}^{j}\right)\mathbf{z}_{a}\right)\right\|=\sigma(\mathbf{s})_{n}^{j}\sqrt{1-\left(\mathbf{z}_{a}^{\top}\mathbf{z}_{n}^{j}\right)^{2}}\approx 0\,.$$

(7)

And for a hard negative, $\mathbf{z}_{a}^{\top}\mathbf{z}_{n}^{j}\approx 0$¹¹1This represents the majority of hard negatives, and if the similarity is close to 1, it is too hard and may cause the model to collapse, or due to wrong annotation., and $\sigma(\mathbf{s})_{n}^{j}$ is moderate, thus the above equation is greater than 0, and its contribution to the gradient of the loss function is greater. Former research only explained it intuitively that features with shorter amplitudes often represent categories that are more difficult to distinguish, and applying feature normalization would divide harder examples with a smaller value (the amplitude), thus getting relatively larger gradients [58], however, we prove this property for the first time by conducting gradient analysis. The derivation process of Eq. 3 and Eq. 4 are alike. Comparing with the commonly used Triplet loss in video retrieval tasks [33, 31] which requires computationally expensive hard negative mining, the proposed method based on contrastive learning takes advantage of the nature of softmax-based loss when combined with feature normalization to perform hard negative mining automatically, and use the memory bank mechanism to increase the capacity of negative samples, which greatly improves the training efficiency and effect.

To save the computation and memory cost, at the training stage, all feature aggregation models are trained with the output as $\ell_{2}$-normalized video-level descriptors ($f(\mathbf{x})\in\mathbb{R}^{d}$), thus the similarity between video pairs is simply calculated by dot product. Besides, for the sequence aggregation models, refined frame-level video descriptors ($f(\mathbf{x})\in\mathbb{R}^{d\times f}$) can also be easily extracted before applying average pooling along the time axis. Following the setting in [31], at the evaluation stage, we also use chamfer similarity to calculate the similarity between two frame-level video descriptors. Denote the representation of two videos as $\mathbf{x}=[x_{0},x_{1},\dots,x_{n-1}]^{\top}$, $\mathbf{y}=[y_{0},y_{1},\dots,y_{m-1}]^{\top}$, where $x_{i},y_{j}\in\mathbb{R}^{d}$, the chamfer similarity between them is:

$$\text{sim}_{f}(\mathbf{x},\mathbf{y})=\frac{1}{n}\sum_{i=0}^{n-1}\max_{j}{x_{i}y_{j}^{\top}}\,,$$

(8)

and the symmetric version:

$$\text{sim}_{sym}(\mathbf{x},\mathbf{y})=\left.\left(\text{sim}_{f}(\mathbf{x},\mathbf{y})+\text{sim}_{f}(\mathbf{y},\mathbf{x})\right)\middle/2\right.\,.$$

(9)

Note that this approach (chamfer similarity) seems to be inconsistent with the training target (cosine similarity), where the frame-level video descriptors are averaged into a compact representation and the similarity is calculated with dot product. However, the similarity calculation process of the compact video descriptors can be written as:

	$\displaystyle\text{sim}_{cos}(\mathbf{x},\mathbf{y})$	$\displaystyle=\left(\frac{1}{n}\sum_{i=0}^{n-1}x_{i}\right)\left(\frac{1}{m}\sum_{j=0}^{m-1}y_{j}\right)^{\top}$		(10)
		$\displaystyle=\frac{1}{n}\sum_{i=0}^{n-1}\frac{1}{m}\sum_{j=0}^{m-1}x_{i}y_{j}^{\top}\,.$

Therefore, given frame-level features, chamfer similarity averages the maximum value of each row of the video-video similarity matrix, while cosine similarity averages the mean value of each row. It is obvious that $\text{sim}_{cos}(\mathbf{x},\mathbf{y})\leq\text{sim}_{f}(\mathbf{x},\mathbf{y})$, therefore, by optimizing the cosine similarity, we are optimizing the lower-bound of the chamfer similarity. As only the compact video-level feature is required, both time and space complexity are greatly reduced as cosine similarity is much computational efficient.

We evaluate the proposed approach on three video retrieval tasks, namely Near-Duplicate Video Retrieval (NDVR), Fine-grained Incident Video Retrieval (FIVR), and Event Video Retrieval (EVR). In all cases, we report the mean Average Precision (mAP).

Training Dataset. We leverage the VCDB [25] dataset as the training dataset. The core dataset of VCDB has 528 query videos and 6,139 positive pairs, and the distractor dataset has 100,000 distractor videos, of which we successfully downloaded 99,181 of them.

Evaluation Dataset. For models trained on the VCDB dataset, we test them on the CC_WEB_VIDEO [61] dataset for NDVR task, FIVR-200K for FIVR task and EVVE [45] for EVR task. For a quick comparison of the different variants, the FIVR-5K dataset as in [31] is also used. The CC_WEB_VIDEO dataset contains 24 query videos and 13,129 labeled videos; The FIVR-200K dataset includes 225,960 videos and 100 queries, it consists of three different fine-grained video retrieval tasks: (1) Duplicate Scene Video Retrieval, (2) Complementary Scene Video Retrieval and (3) Incident Scene Video Retrieval; The EVVE dataset is designed for the EVR task, it consists of 2,375 videos and 620 queries.

Implementation Details. For feature extraction, we extract one frame per second for all videos. For all retrieval tasks, we extract the frame-level features following the scheme in Section 3.2. The intermediate features are all extracted from the output of four residual blocks of ResNet-50 [18]. PCA trained on 997,090 randomly sampled frame-level descriptors from VCDB is applied to both iMAC and $\text{L}_{3}$-iRMAC features to perform whitening and reduce its dimension from 3840 to 1024. Finally, $\ell_{2}$-normalization is applied.

For the Transformer model, it is implemented with one single layer, eight attention heads, dropout_rate set to 0.5, and the dimension of the feed-forward layer set to 2048.

During training, all videos are padded to 64 frames (if longer, a random segment with a length of 64 is extracted), and the full video is used in the evaluation stage. Adam [29] is adopted as the optimizer, with the initial learning rate set to $10^{-5}$, and cosine annealing learning rate scheduler [37] is used. The model is trained with batch size 64 for 40 epochs, and $16\times 64$ negative samples sampled from the distractors are sent to the memory bank each batch, with a single device with four Tesla-V100-SXM2-32GB GPUs, the size of the memory bank is equal to 4096. The code is implemented with PyTorch [41], and distributed training is implemented with Horovod [47].

Models for Temporal Context Aggregation. In Table 7, we compare the Transformer with prior temporal context aggregation approaches, i.e., NetVLAD [1], LSTM [20] and GRU [8]. All models are trained on VCDB dataset with iMAC feature and evaluated on all three tasks of FIVR-5K, and dot product is used for similarity calculation for both train and evaluation. The classic recurrent models (LSTM, GRU) do not show advantage against NetVLAD. However, with the help of self-attention mechanism, the Transformer model demonstrate excellent performance gain in almost all tasks, indicating its strong ability of long-term temporal dependency modeling.

Frame Feature Representation. We evaluate the iMAC and $\text{L}_{3}$-iRMAC feature on the FIVR-200K dataset with cosine similarity, as shown in Table 7. With more local spatial information leveraged, $\text{L}_{3}$-iRMAC show consistent improvement against iMAC.

Loss function for contrastive learning. We present the comparison of loss functions for contrastive learning in Table 7. The InfoNCE loss show notable inferiority compared with Circle with default parameters $\tau=0.07,\gamma=256,m=0.25$. By adjusting the sensitive temperature parameter $\tau$ (set to $1/256$, equivalent with $\gamma=256$ in Circle loss), it still shows around 0.5% less mAP.

Size of the Memory Bank. In Table 7, we present the comparison of different sizes of the memory bank. It is observed that a larger memory bank convey consistent performance gain, indicating the efficiency of utilizing large quantities of negative samples. Besides, we compare our approach against the commonly used triplet based approach with hard negative mining [33] (without bank). The training process of the triplet-based scheme is extremely time-consuming (5 epochs, 5 hours on 32 GPUs), yet still show around 10% lower mAP compared with the baseline (40 epochs, 15 minutes on 4 GPUs), indicating that compared with learning from hard negatives, to utilize a large number of randomly sampled negative samples is not only more efficient, but also more effective.

Momentum Parameter. In Table 7, we present the ablation on momentum parameter of the modified MoCo [17]-like approach, where a large queue is maintained to store the negative samples and the weight of the model is updated in a moving averaged manner. We experimented with different momentum ranging from 0.1 to 0.999 (with queue length set to 65536), but none of them show better performance than the baseline approach as reported in Table 7, we argue that the momentum mechanism is a compromise for larger memory. as the memory bank is big enough in our case, the momentum mechanism is not needed.

Similarity Measure. We evaluate the video-level features with cosine similarity, and frame-level features following the setting of ViSiL [31], i.e., chamfer similarity, symmetric chamfer similarity, and chamfer similarity with similarity comparator (the weights are kept as provided by the authors). Table 7 presents the results on FIVR-5K dataset. Interestingly, the frame-level similarity calculation approach outperforms the video-level approach by a large margin, indicating that frame-level comparison is important for fine-grained similarity calculation between videos. Besides, the comparator network does not show as good results as reported, we argue that this may be due to the bias between features.

Next, we only consider the Transformer model trained with $\text{L}_{3}$-iRMAC feature and Circle loss in the following experiments, denoted as TCA (Temporal Context Encoding for Video Retrieval). With different similarity measures, all four approaches are denoted as $\text{TCA}_{c}$ (cosine), $\text{TCA}_{f}$ (chamfer), $\text{TCA}_{sym}$ (symmetric-chamfer), $\text{TCA}_{v}$ (video comparator) for simplicity.

A more comprehensive comparison on performance is given in Fig. 2. The proposed approach achieves the best trade-off between performance and efficiency with both video-level and frame-level features against state-of-the-art methods. When compared with $\text{ViSiL}_{v}$, we show competitive results with about 22x faster inference time. Interestingly, our method slightly outperforms $\text{ViSiL}_{v}$ in ISVR task, indicating that by conducting temporal context aggregation, our model might show an advantage in extracting semantic information.

We demonstrate the distribution of video-level features on a randomly sampled subset of FIVR-5K with t-SNE [39] in Fig. 6. Compared with DML, the clusters formed by relevant videos in the refined feature space obtained by our approach are more compact, and the distractors are better separated; To better understand the effect of the self-attention mechanism, we visualize the average attention weight (response) of three example videos in Fig. 5. The self-attention mechanism helps expand the vision of the model from separate frames or clips to almost the whole video, and conveys better modeling of long-range semantic dependencies within the video. As a result, informative frames describing key moments of the event get higher response, and the redundant frames are suppressed.