iDT算法是行为识别领域中非常经典的一种算法，在深度学习应用于该领域前也是效果最好的算法。由INRIA的IEAR实验室于2013年发表于ICCV。目前基于深度学习的行为识别算法效果已经超过了iDT算法，但与iDT的结果做ensemble总还是能获得一些提升。所以这几年好多论文的最优效果都是“Our method+iDT”的形式。
此前由于项目原因，对iDT算法进行了很多研究和实验，故此处对其核心思路与一些实施的细节进行总结，方便后续回顾，也希望能够在此过程中获得一些新的启发。
介绍的内容主要包含两篇文章的内容，分别是”Dense Trajectories and Motion Boundary Descriptors for Action Recognition”和”Action Recognition with Improved Trajectories”。这两篇都是H. Wang的文章，前者要更早一些，介绍了DT（Dense Trajectories）算法。后者则在前者的基础上进行了改进（improved），主要是引入了对背景光流的消除方法，使得特征更集中于对人的运动的描述。两者的框架大致相同，本文先对DT算法进行介绍，再介绍iDT算法的改进之处。
iDT的代码可以在其个人主页上下到，也可以点击此处下载。
对iDT特征进行FV编码的代码可以在dtfv 下载。
更新了iDT算法的代码解析，见iDT算法用法与代码解析
密集轨迹算法(DT算法)
算法基本框架
如图所示即为算法的基本框架，包括密集采样特征点，特征点轨迹跟踪和基于轨迹的特征提取几个部分。后续的特征编码和分类过程则没有在图中画出。
密集采样
DT方法通过网格划分的方式在图片的多个尺度上分别密集采样特征点。在多个空间尺度上采样能保证采样的特征点覆盖了所有空间位置和尺度，通常8个空间尺度已经非常足够了，若图像很大，可以适当增加。后续的特征提取也是在各个尺度上分别进行的。特征点采样的间隔（即网格的大小）W通常取W=5。
下一步的目标即在时间序列上跟踪这些特征点，但在缺乏变化的区域（比如一块白色墙壁中间的点）中跟踪特征点是无法实现的。因此在进行跟踪前要先去除一些特征点。此处的方法是计算每个像素点自相关矩阵的特征值，并设置阈值去除低于阈值的特征点。阈值由下式决定：
式中(λ1i,λ2i)是图像I中像素点i的特征值。0.001为实验确定的一个比较合适的值。下图即为密集采样的一个示例效果图片。
轨迹与轨迹描述子(trajectories)
设上一步中密集采样到的某个特征点的坐标为Pt=(xt,yt),则我们可以用下式来计算该特征点在下一帧图像中的位置。
式中ωt=(ut,vt)为密集光流场，是由It和It+1计算得到的，u和v分别代表光流的水平和垂直分量。而M则代表中值滤波器，尺寸为3*3。故该式子是通过计算特征点邻域内的光流中指来得到特征点的运动方向的。
某个特征点在连续的L帧图像上的位置即构成了一段轨迹(Pt,Pt+1,...,Pt+L),后续的特征提取即沿着各个轨迹进行。由于特征点的跟踪存在漂移现象，故长时间的跟踪是不可靠的，所以每L帧要重新密集采样一次特征点，重新进行跟踪。在DT/iDT算法中，选取L=15。
此外，轨迹本身也可以构成轨迹形状特征描述子。对于一个长度为L的轨迹，其形状可以用(ΔPt,...,ΔPt+L−1)来描述，其中位移矢量ΔPt=(Pt+1−Pt)=(xt+1−xt,yt+1−yt)。在进行正则化后就可以得到轨迹特征描述子了。正则化方式为：
故最终得到的轨迹特征为15*2=30维向量。
运动/结构描述子(HOF,HOG,MBH)
除了轨迹形状特征，我们还需要更有力的特征来描述光流，DT/iDT中使用了HOF,HOG和MBH三种特征。此前我写了一篇博客对这几种特征进行了介绍。
首先对这几种特征提取的通用部分进行介绍。沿着某个特征点的长度为L的轨迹，在每帧图像上取特征点周围的大小为N×N的区域，则构成了一个时间-空间体（volume），如算法基本框架图的右半部分所示。对于这个时间-空间体，在进行一次网格划分，空间上每个方向上分为nσ份，时间上则均匀选取nτ份。故在时间-空间体*分出nσ×nσ×nτ份区域用作特征提取。在DT/iDT中，取N=32,nσ=2,nτ=3,接下来对各个特征的提取细节进行介绍。
- HOG特征:HOG特征计算的是灰度图像梯度的直方图。直方图的bin数目取为8。故HOG特征的长度为96（2*2*3*8）。
- HOF特征:HOF计算的是光流（包括方向和幅度信息）的直方图。直方图的bin数目取为8+1，前8个bin于HOG相同，额外的一个bin用于统计光流幅度小于某个阈值的像素。故HOF的特征长度为108（2*2*3*9）。
- MBH特征:MBH计算的是光流图像梯度的直方图，也可以理解为在光流图像上计算的HOG特征。由于光流图像包括x方向和y方向，故分别计算MBHx和MBHy。MBH总的特征长度为192（2*96）。
在计算完后，还需要进行特征的归一化，DT算法中对HOG,HOF和MBH均使用L2范数归一化。
特征编码—Bag of Features
对于一段视频，存在着大量的轨迹，每段轨迹都对应着一组特征（trajectory,HOG,HOF,MBH），因此需要对这些特征组进行编码，得到一个定长的编码特征来进行最后的视频分类。
DT算法中使用Bag of Features方法进行特征的编码，Bag of Features方法的介绍见这篇博文——Bag of Features(BOF)图像检索算法,这篇博文也是转载的，但无奈原文地址已经打不开了。在训练码书时，DT算法随机选取了100000组特征进行训练。码书的大小则设置为4000。
在训练完码书后，对每个视频的特征组进行编码，就可以得到视频对应的特征。
分类-SVM
在得到视频对应的特征后，DT算法采用SVM（RBF−χ2核）分类器进行分类，采用one-against-rest策略训练多类分类器。
提升的密集轨迹算法（iDT算法）
iDT算法的基本框架和DT算法相同，主要改进在于对光流图像的优化，特征正则化方式的改进以及特征编码方式的改进。这几处改进使得算法的效果有了巨大的提升，在UCF50数据集上的准确率从84.5%提高到了91.2%，在HMDB51数据集上的准确率从46.6%提高到了57.2%。下面分别对几处改进进行进行介绍。
相机运动估计
首先是最重要的一处改进，通过估计相机运动估计来消除背景上的光流以及轨迹。首先看DT算法中在没消除背景干扰时的轨迹分布。
可以看出，由于相机在运动，所以背景上也有很多轨迹，人的轨迹也受到相机运动的很大影响。而这些信息与要识别的动作关系是不大的，属于干扰信息。因此就希望能够识别并消除这些轨迹。而实际上轨迹的运动也是通过计算光流信息进行计算的，因此需要通过估计相机运动，来消除背景区域的光流。
由于相邻两帧图像之间变化比较小，iDT算法假设相邻的两帧图像之间的关系可以用一个投影变换矩阵来描述，即后一帧图像是前一帧图像通过投影变换得到的。因此，估计相机运动的问题就变成了利用前后帧图像计算投影变换矩阵的问题。
为了准确得估计投影变换，iDT算法中采用了两种方法来获得匹配点对。分别为SURF特征以及光流特征。在获得匹配的点对后，就可以利用RANSAC算法估计投影变换矩阵了。具体操作为：记t时刻和t+1时刻的灰度图像分别为It和It+1,用两张图像计算得到投影变换矩阵H（It+1=H×It）。然后用H的逆对It+1进行变换（warp），即Iwarpt+1=H−1×It+1。Iwarpt+1代表假设不存在相机运动时t+1时刻的图像。用It和Iwarpt+1就可以计算得到优化过的光流。
此处可以注意到很大的一个问题，那就是图像中人的动作可能比较显著，人身上的匹配点对会使得投影矩阵的估计不准确。因此iDT算法中使用一个huaman detector检测人的位置框，并去除该框中的匹配点对。从而使得人的运动不影响投影矩阵的估计。iDT中使用的是当时效果最好的human detector，其文章为”Weakly supervised learning of interactions between humans and objects”。而现在物体检测领域已经完全被深度学习攻陷了，比较好的方法包括faster-rcnn,ssd等算法。其中ssd的速度很快，效果也不错，推荐使用。
综合以上的改进算法，可以得到如上效果图。图像左侧两列图是不使用human detector的效果，右边两列图是使用human detector时的效果。可以看出加入human detector对效果的提升非常巨大。最下面一列则是比较失败的情况，按照文章中的分析，原因主要包括两点：1）运动模糊；2）人物占图像比例高时相机运动估计不准。
从光流中消除相机运动带来的影响主要有两点好处：
1. 运动描述子（主要指HOF和MBH）能更准确的描述动作，用单一描述子的分类准确率比起DT中有很大的提高
2. 由于轨迹也是利用光流进行运算的，因此，可以通过设置阈值，消除优化后的光流中位移矢量的幅值小于阈值的轨迹。
特征归一化方式
在iDT算法中，对于HOF,HOG和MBH特征采取了与DT算法（L2范数归一化）不同的方式——L1正则化后再对特征的每个维度开平方。这样做能够给最后的分类准确率带来大概0.5%的提升。
特征编码—Fisher Vector
特征编码阶段iDT算法不再使用Bag of Features方法，而是使用效果更好的Fisher Vector编码，其具体编码方式见我之前写的博文：机器学习笔记：Fisher Vector基本原理与用法。Fisher Vector同样也是先用大量特征训练码书，再用码书对特征进行编码。在iDT中使用的Fisher Vector的各个参数为：
- 用于训练的特征长度：trajectory+HOF+HOG+MBH=30+96+108+192=426维
- 用于训练的特征个数：从训练集中随机采样了256000个
- PCA降维比例：2，即维度除以2，降维后特征长度为213。先降维，后编码
- Fisher Vector中高斯聚类的个数K：K=256
故编码后得到的特征维数为2KD个，即109056维。在编码后iDT同样也使用了SVM进行分类。在实际的实验中，推荐使用liblinear，速度比较快。
总结与讨论
iDT算法作为深度学习之前最好的行为识别算法，有着优良的效果和很好的鲁棒性。其中有很多非常值得借鉴的思路，比如相机运动引起的背景光流的消除，比如沿着轨迹提取特征的思路。CVPR2015中的”Action Recognition with Trajectory-Pooled Deep-Convolutional Descriptors”的思路就是沿着轨迹利用CNN提取特征，取得了进一步的效果提升。由于iDT还公开了源码，里面对算法的实现思路非常清晰，所以后续可能还会写一篇iDT的代码分析。