STAR-GNN: Spatial-Temporal Video Representation for Content-based Retrieval

We introduce the proposed STAR-GNN framework for video feature extraction. As illustrated in Figure 2, the training process of STAR-GNN can be described in four steps. First, for a video, we sample frames at a given rate and take the pre-trained backbone network to extract the raw frame feature map. Multi-scale regional features are then generated from the frame feature map. Second, each video is transformed into a regional graph with spatial-temporal links. Third, we train the graph neural network in the STAR-GNN framework with retrieval triplet loss or contrastive loss. Fourth, each regional graph is processed with the trained STAR-GNN using shared parameters. The feature for a video is represented as the average of all regional node representations in its regional graph. The rest of this section provides further details.

A video consists of frames with a temporal order, and each frame contains semantic contents appearing in various locations. A video is therefore a collection of inter-related temporal-spatial information in three dimensions. To integrate these aspects into a unified feature space, we construct an undirected/weighted graph $G(V,E)$ for each video, to model both the spatial and temporal domains.

First, we divide a single frame into multi-scale regions to model the local visual coherence and enable the modeling of regional relationships through time. Considering that the regions of interest among different frames may vary in size, we use $s$ different scales. These scales are applied on frame feature maps extracted by the backbone network to obtain region-level features with corresponding strides. Consequently, each frame is split into several regions, with each region corresponding to a node in the regional graph. And a frame $F_{i}$ will have $s$ types of regions which are represented by $R^{ki}_{j}$, in which $j$ stands for the region index and $k\in\{1,2,...,s\}$ is the scale index. See Figure 2 STEP 1.

Second, to take advantage of a video’s local temporal dynamics, we inter-connect all regional nodes at the same spatial location across all frames in a video to form a complete temporal sub-graph. The graph construction strategy of STAR-GNN is formally defined as (STEP 2 in Figure 2):

1. 1.

   Node formulation: Each region $R^{ki}_{j}$ ($k\in\{1,2,...,s\}$) is represented as a node in graph $G$. And the edge weight $w_{ij}$ between node $n_{i}$ and node $n_{j}$ is the cosine similarity of corresponding region features.

2. 2.

   Spatial Connectivity: Every pair of regions belonging to the same frame are connected, i.e. for a fixed $i=\hat{i}$, the sub-graph defined by the node set $\{R^{k\hat{i}}_{j}\}$ and the edges among them is a complete graph.

3. 3.

   Temporal Connectivity: Regions of the same scale and the same location are connected through different frames. Given $j=\hat{j}$, the sub-graph defined by the node set $\{R^{\hat{k}i}_{\hat{j}}\}$ and the edges among them is a complete graph.

The spatio-temporal graph constructed with the procedure described above has a few desirable properties for a GCN. Details are provided in the Analysis part.

We consider an undirected graph $G(V,E)$. When applied to feature representation learning for a graph, graph neural networks are designed to learn a transition function $f$ as well as an output function $g$. Such that:

$$H=f(H,X),$$

(1)

$$O=g(H,X_{N}),$$

(2)

where $X$ is all features, $H$ is the graph’s hidden states, $X_{N}$ denotes all the node features and $O$ denotes the final feature representation for all the graph nodes.

In this STAR-GNN frame work, instead of outputting all node representations, we use a global aggregation function to compress all these learned features into a single feature vector to represent the entire graph. That is, the graph neural networks in the STAR-GNN framework can be written as:

$$o=AGGREGATE(G_{\Theta}\star X).$$

(3)

Here, $G_{\Theta}$ is the GNN layer-wise operator and $AGGREGATE$ is the aggregate function which takes in a feature matrix for all the graph nodes and outputs a single feature vector.

In particular, the GNN layer-wise operator here can be replaced by any specific GNN implementation, such as the vanilla GCN layer [14] $H^{(l+1)}=\sigma(\hat{A}H^{(l)}W^{(l)})$, cluster GCN layer [16] $H^{(l)}=\sigma(\hat{A}H^{(l-1)}W_{a}^{(l-1)}+H^{(l-1)}W_{b}^{(l-1)})$ and so on. Here, $\hat{A}$ is a renormalized adjacency matrix, $W$ denotes a learnable parameters. Correspondingly, $AGGREGATE$ function can be replaced by different strategies such mean aggregation, max pooling aggregation and so on.

In order to train STAR-GNN, we use the GCN mini-batch training strategy. But instead of mini-batches of nodes from the same graph as in most of the literature [16, 18], we spilt the training video set into mini-batches with $B$ videos in each, and use the set of spatio-temporal feature graphs that correspond to the videos as the input signal to STAR-GNN. We then use triplet loss to update the model’s parameters at each iteration on a mini-batch, which is defined as:

$$\mathcal{J}=\sum_{i=1}^{B}\mathcal{L}(AG^{(i)},PG^{(i)},NG^{(i)}),$$

(4)

$\mathcal{L}$ can be a triplet loss or contrastive loss, $AG^{(i)}$ denotes the output graph features for an anchor video sample, $PG^{(i)}$ denotes that for a positive retrieval sample and $NG^{(i)}$ is that of a negative sample. Here we regard a labelled positive sample in the dataset for a given query $AG^{(i)}$ as $PG^{(i)}$, and a random sample outside the labelled positive sample sets as $NG^{(i)}$. The gradient is then updated for each mini-batch iteration:

$$\frac{1}{B}\sum_{i\in\mathcal{B}}\bigtriangledown\mathcal{L}(AG^{(i)},PG^{(i)},NG^{(i)}).$$

(5)

In the experiments, we compare the proposed method with six state-of-the-art content-based video retrieval methods, including MAC[3], RMAC[3], SPOC[4], 3D-shuffenetv2[22], DML[2], 3D-shuffenetv2(Supervised)[22] and RGB[23]. Among them, MAC, RMAC, and SPOC used VGG pre-trained on ImageNet as feature extractor, and 3D-shuffenetV2 used a 3D convolutional network pre-trained on video classification dataset Kinetics-600[24]. For DML and 3D-shuffenetV2(Supervised), we use the same training set with STAR-GNN. RGB is a attention-based deep metric learning model, which we use the data from the source paper. For STAR-GNN, CL denote Contrastive Loss and TL denote Triplet Loss. Comparative results for retrieval mAP on SVD and VCDB datasets are shown in Table 1. The top half of Table 1 includes the results for some previous methods while the lower half shows the methods using STAR-GNN framework. Additional Distraction stands for the number of distractor videos, which are randomly selected, unlabeled videos (apart from the positive samples and negative samples labelled) in test datasets. They drastically increase the volume of the candidate set and raise the difficulty significantly for retrieval. For each configuration, we use bold text to mark the best performing results.

From the Table 1, we can see that STAR-GNN outperform all other baselines under all distraction settings. On SVD, our method gives mAP=0.9329 without distractor, which is a 2.67% relative improvement compared to the current state-of-the-art supervised CBVR method, i.e., DML[2], and a 5.28% relative improvement when the number of distractor videos is 520,000. A similar trend was reported on VCDB dataset, STAR-GNN outperforms other baselines with a consistent margin (+0.0273 +0.0624) on VCDB. Importantly, with the size of the distraction set increasing, the mAP of all methods will decrease, but STAR-GNN decreases the least, which means STAR-GNN is significantly more stable to the feature representation of the videos. On SVD, with an increasing additional distraction set from 0 to 520K, the mAP of our proposed method are 92.78%, 88.12%, 85.97%, 85.28%, 82.34%, respectively. On VCDB, the mAP of our proposed method are 80.25%, 88.12%, 72.01%, 64.24%, 60.77%, respectively. All reported results show that STAR-GNN has significant benefit to content-based video retrieval.