轉發請注明出處：http://blog.csdn.net/wzmsltw/article/details/53023363
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。
下一步的目标即在時間序列上跟蹤這些特征點，但在缺乏變化的區域（比如一塊白色牆壁中間的點）中跟蹤特征點是無法實作的。是以在進行跟蹤前要先去除一些特征點。此處的方法是計算每個像素點自相關矩陣的特征值，并設定門檻值去除低于門檻值的特征點。門檻值由下式決定：
T=0.001×maxi∈Imin(λ1i,λ2i)
式中 (λ1i,λ2i) 是圖像I中像素點i的特征值。0.001為實驗确定的一個比較合适的值。下圖即為密集采樣的一個示例效果圖檔。
軌迹與軌迹描述子(trajectories)
設上一步中密集采樣到的某個特征點的坐标為 Pt=(xt,yt) ,則我們可以用下式來計算該特征點在下一幀圖像中的位置。
Pt+1=(xt+1,yt+1)=(xt,yt)+(M∗ωt)|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) 。在進行正則化後就可以得到軌迹特征描述子了。正則化方式為：
T=(ΔPt,...,ΔPt+L−1)∑t+L−1j=t||ΔPj||
故最終得到的軌迹特征為15*2=30維向量。
運動/結構描述子(HOF,HOG,MBH)
除了軌迹形狀特征，我們還需要更有力的特征來描述光流，DT/iDT中使用了HOF,HOG和MBH三種特征。此前我寫了HOG,HOF與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）。其中，MBH是作者借鑒他人的工作，第一次将這個特征用到動作識别的領域。
在計算完後，還需要進行特征的歸一化，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的代碼分析。