Paper: https://arxiv.org/abs/1806.01810 (ECCV 2018)
Author: Xiaolong Wang, Abhinav Gupta (CMU)

0. 引言

GNN最近在深度学习领域受到了广泛关注，其具有解决深度学习无法解决的因果推理和可解释性的问题，可以说是一个比较有前景的方向。今天来分享一篇ECCV2018的paper，结合图网络来做视频分类。视频和图像属于非结构化的数据，如何构建一个合理的graph是需要考虑的问题，本文通过物体检测算法来获取graph中的节点，再计算节点之间的关联性，进而构建整个graph。

1. Intro

人类如何识别一个动作，比如打开一本书。

我们认为有2个重要的线索：对时序上形状的变化进行建模，以及对人与物体之间的关系进行建模。
本文提出将视频表示成时空域的region的graph，用于捕获上述信息。graph中的node是指视频的不同帧所检测到的物体proposals，这些node以两种关系进行连接：（1）是否具有一定的相似性（2）在时间和空间位置上是否相关。

2. Overview

如图2所示，我们的模型输入为视频序列，将其通过3D CNN得到一个 $T\times H \times W \times d$T×H×W×d 大小的feature map。除了提取视频的特征外，我们通过RPN获取T帧的每一帧上物体的bbox，然后通过ROIAlign得到每个物体 $7 \times 7 \times d$7×7×d 大小的feature map再maxpool得到d维的feature vector，作为每个物体的特征。这样假设有N个bbox，我们最后就有 $N \times d$N×d 维的物体特征。

然后我们构建一个graph，包含N个node，对应上述的N个物体proposal。在这个graph上共有2种relation：similarity relation和spatial-temporal relation，简单起见我们将整个图分成两个子图，子图包含相同的节点但不同的relation。
我们使用GCN来对图的特征进行训练，GCN的输出维度也是N*d，和输入维度保持一致。然后通过avg pooling得到d维的feature，同时除了GCN的feature，我们将视频的feature（ $T\times H \times W \times d$T×H×W×d 维）也做avg pooling得到同样d维的特征，两个特征concat送入到最后的fc进行视频分类。

3. Graph Representations in Videos

3.1 Video Representation

视频的特征表示分为整个视频的特征和提取的物体框的特征两个部分。
整个视频的特征。 每个视频平均采样32帧，送入到3D ConvNet中进行特征提取，表1是我们用的3D-resnet-50的结构，网络的输入是 $32 \times 224 \times 224$32×224×224，输出res5的feature map为 $16\times 14 \times 14$16×14×14。

RPN。 提取物体框采用的算法是RPN，每隔一帧（原来32帧，取16帧）提取object proposals，注意这些proposal是不知道物体类别的。RPN通过MSCOCO训练，RPN和I3D之间没有参数共享。为了得到这些物体的特征，将16帧RGB图片上的bbox映射到最终的 $16\times 14 \times 14$16×14×14 大小的feature map上，然后通过ROIAlign得到每个框最后的特征。ROIAlign为每个框生成 $7 \times 7 \times d$7×7×d 大小的feature，经过max-pool得到d维的特征。

3.2 Similarity Graph

我们通过计算物体特征之间的相似度来构建相似度图。在这个图中，我们将语义上相互关联的object pairs联系起来。具体地，我们会得到一个高置信度的edge当两个物体组成的对是以下情况：

1. 他们是相同物体在不同帧的不同状态
2. 他们和动作识别有很大相关性

similarity edges在任意两个物体之间进行计算，其表达式为：

其中$\phi$ϕ和$\phi'$ϕ′表示对原始特征的两种不同的变换，我们有$\phi(x)=wx$ϕ(x)=wx和$\phi(x)=w'x$ϕ(x)=w′x，$w$w和$w'$w′都是 $d\times d$d×d 维的权重，能够通过反向传播进行学习。加上$w$w和$w'$w′这两个变换权重，使得我们不仅可以学习同一个物体在不同帧所处不同状态之间的关系，也可以学习不同物体之间的关联性。
通过计算相似度矩阵后，我们对每一行进行归一化，使得和特定的某个proposal i相关的所有边的加和为1，本文使用softmax进行归一化，即：

3.3 Spatial-Temporal Graph

虽然similarity graph能够捕获任意两个物体框的长距离的依赖，但是它没有捕获物体间spatial的关系以及物体状态改变的顺序。为了能够得到物体间的空间和时间的关系，我们提出spatial-temporal graph，即时间空间位置上比较临近的物体相连起来。
给定一个t帧上的物体框，我们计算t+1时刻所有物体框和它之间的IoU，将t时刻的物体i和t+1时刻的物体j之间的IoU记为$\sigma_{ij}$σij​，如果$\sigma_{ij}>0$σij​>0，则将物体i和j通过一个有向的边 $i\rightarrow j$i→j相连接，这条边的值即为$\sigma_{ij}$σij​，最后，将与同一个物体i相连的所有边的值进行归一化：

$G^{front}$Gfront表示从前一时刻t指向后一时刻t+1的graph，同样的方法构建t+1时刻到t时刻的graph $G^{back}$Gback。

4. Convolutions on Graphs

一层graph conv的表达式如下：

G表示上述提到的临域graph中的一种（$G^{sim}$Gsim，$G^{front}$Gfront，$G^{back}$Gback），其维度为$N \times N$N×N，X是各node所表示的物体的feature，维度为 $N \times d$N×d，W是这一层的权重，本文中大小为$d \times d$d×d，则输出Z的维度为$N \times d$N×d。
graph conv可以被堆叠到多个层，每层后我们使用两种非线性函数，包括Layer Norm和ReLU。
多个graph可以通过下式进行加和，但作者发现效果并不理想。

原因在于similarity graph有参数可学，其他两个没有，直接加和会使得参数优化困难。因此把整个graph分成了2个分支，分别进行L层的conv后，最终的feature加和在一起，得到 $N \times d$N×d 的维度。

5. Experiments

训练。 backbone的resnet50先在imagenet上训练，然后inflat成I3D，后在Kinetics上进行训练。整个网络以32帧作为输入，spatial的维度$224 \times 224$224×224，是将原视频resize到短边[256,320]，然后random crop得到的。
由于res5的输出feature map的channel维度是2048，为了进一步减少GCN的参数量，作者另外加了一个 $1 \times 1 \times 1$1×1×1 的conv层将其维度减小，最终d=512。
baseline I3D是用4卡GPU训练的，batchsize=8。注意在训练时我们固定所有BN的参数。我们的模型总共训练100K iter，前90K iter采用lr=0.00125，后10K iter的lr=0.000125，dropout用在最后的global pooling层，dropout=0.3.
GCN的层数=3，前两层随机初始化，最后一层初始化为0。为了将I3D和GCN一起训练，我们实行stage-wise training。首先finetune I3D模型，然后在最后的conv feature基础上进行ROIAlign和GCN。我们固定I3D然后以相同的lr策略训练GCN，然后再一起训练I3D和GCN 30K iter，lr=0.000125。
和数据集有关的设置。 对于Charades和Something-something数据集采用不同的loss function，对Charades，采用binary sigmoid loss来解决多 label，对Something-something，用softmax loss。我们也在这两个数据集上提取了不同数量的proposal，Charades的场景更加杂乱所以每帧提取50个proposal，Something-something比较单一提取10个proposal。
推理。 使用全卷积的推理方式，每个视频的短边resize到256，在测试时对charades使用10 clips，对something-something使用2 clips（这是根据两个数据集的平均视频长度得到的），不同clips的score通过max pooling最终聚合到一起。

5.1 Experiments on Charades

5.2 Experiments on Something-Something