時間規整耦合線性判別分析的動作識別算法

方云錄，苗 茹

(河南大學 民生學院，河南 開封 475000)

0 引 言

近年來，眾多學者對動作識別[1-3]開展了深入的研究，得到了一些動作識別算法。例如傅穎等[4]提出了基于DTW的動作識別算法。徐向藝等[5]提出了一種DTW優化直方圖動態捕獲動作識別算法。但是基于DTW算法中時間結構變化較大，對光照變化敏感。Wang等[6]基于密集采樣的基礎上，提出了一種有效的基于密集軌跡特征。其利用光流場密集采樣的興趣點捕抓曲線，分別計算曲線位移向量與其曲線子時空塊的3個組成直方圖為動作特征。但在復雜的環境中，由于經常受到光照變化、晃動或者遮擋等影響，使其對動作特征提取難度增大，降低了算法性能。邵延華等[7]定義了一種特征融合的動作識別方案。其主要通過背景差分對顯著區檢測，并提取顯著區的剪影直方圖與光流直方圖，再通過的融合技術形成新的特征，最后，利用SVM進行分類學習。該方法能較好對行為動作完成識別判斷。但是該算法提取的特征會受到數據本身的噪聲干擾，動作類別中存在語義鴻溝。

雖然DTW在序列分析中應用廣泛，但在多序列分類時存在一些局限性。例如：由于動態規劃是一種簡單的確定性方法，所得到的解對于包含時間結構內變化大的序列數據可能不是最優的。其次，DTW沒有消除或忽略影響分類結果的無關變化的內在機制。例如，在語音數據中，視頻數據或揚聲器中的光照條件的變化會顯著地降低DTW的分類方法的性能，對這些不良影響較敏感。

為了解決這些問題，本文提出了一種基于隨機時間規整與線性判別分析的動作識別算法。通過對DTW進行了改進，構造了隨機時間規整(RTW)機制。與動態規劃來尋找最相似的規整模式不同，RTW是逐步生成一組規整的時間模式，稱為時間彈性(TE)特征。通過反復隨機抽樣子序列，保留原始時間順序。利用這種策略，可確保TE特征集包含足夠的高概率判別幀，并聯合PCA與線性判別分析技術，對序列進行分類學習，完成動作識別，最后，測試了所提動作識別算法的魯棒性與精度。

1 動態時間歸模式

動態時間歸(DTW)的思想是將測試時序和參考時序數據伸長或縮短，使其長度相同，再通過Euclidean距離測量兩個時序間的距離[8]。通過對長度不一的時序完成非線性規整，尋找兩者間的最優對應位置。隨后，測量對應位置的Euclidean距離，得到曲線的相似性。該技術在計算機視覺、語音識別、數據挖掘等具有較強的生命力[9]。

設兩個時序為A、B，其對應長度為n、m，表示如下

(1)

為使時序A、B非線性對齊，根據時序A、B的距離建立一個代價矩陣C=[c(i,j)]，矩陣中的元素為ai、bj之間的距離，表示為

(2)

為尋找兩個時序最優匹配，從矩陣中搜索一個路線，使時序A、B的累積距離最小。對于計算C的過程，如果n=m，直接計算時序A、B的距離。如果n≠m，需要進行對齊操作。A、B間的規整路線p的累積代價方程設為cp(A,B)，定義為

(3)

其中，規整路線，l∈[1,L],p為A、B的映射序列。A、B間的最佳規整路線p*為累加代價方程取最小值的路線。因此，DTW度量表示為

DTW=cp*(A,B)=min{cp(A,B)}

(4)

最佳規整路線p*可根據函數獲得

(5)

(1)邊界條件：從p1=(1,1)開始，到pk=(n,m)終結。

(2)連續性：設pk-1=(a′,b′)，那么下個點pk=(a,b)符合a-a′≤1,b-b′≤1。表示無法越過某點來匹配，只允許與自己相鄰點對齊。確保A、B的所有坐標出現在p中。

(3)單調性：給定pk-1=(a′,b′)，下個點pk=(a,b)，需符合0≤a-a′,0≤b-b′。路線p無法返回。

通過一個累加距離，將矩陣中的所有元素得到的距離相加，獲得了最后的總距離，即時序A、B的相似度，定義為

γ(i,j)=d(ai,bi)+min{γ(i,-1,j-1),γ(i-1,j),γ(i,j-1)}

(6)

2 本文動作識別算法

本文提出的算法包含了測試階段和訓練階段。分別通過計算測試與訓練階段的TE特征，然后利用PCA將得到的TE特征變換為子空間，再測量參考子空間與測試子空間的正則角，根據正則角的大小來衡量相似性。最后，根據LDA進行分類學習，完成動作識別過程，整個過程如圖1所示。在圖1中，R為TE特征向量的數量，Kc為類別c中圖像序列的數量。

圖1 本文算法流程

2.1 TE特征提取

為了處理時間結構突變問題，利用TE特征來表示時間結構的局部和全局信息。其中全局信息適應總體時間結構；局部信息處理時間結構的片斷。

y1,y2,…,yn={x1,x2,…,xN},t(y1)<…

(7)

其中，t(·)表示圖像的原始順序。n為構造TE特征所選擇的圖像個數，對應于識別所需的有效幀的數目。

在統計過程，t(y1)為在s中選定的n個圖像的最小圖像順序，t(yn)為最大的順序。令t(yj)為TE特征的第j個順序統計，通過以上描述，t(yj)=k的概率可定義為

(8)

當n=5,N=10時，t(yj)的概率質量函數(j=1,2,…,n)如圖2所示。圖2描述了提取TE特征的統計機制，能適用于整個序列而不只是約束于局部鄰域。位于運動邊緣附近最有可能被選作TE特征的開始和結束塊。這表明TE特征能夠收集時間信息的局部時間結構和全局結構。

圖2 隨機選擇TE特征概率

對于包含r幀范圍的TE特征的概率P(t(yn)-t(y1)=r),r=n-1,…,N-1為

(9)

圖3顯示了從一個包含10個運動圖像中產生的n=5個TE特征的幀范圍的概率分布。例如，TE特性包含1,2,3,4,5和2,3,5,9,10有序的圖像，其幀范圍分別為4和8。

圖3 不同幀范圍的概率分布

2.2 相似性度量

通過重復隨機抽樣，確保TE特征集包含足夠的高概率判別幀。然而，由于TE特征具有隨機性，集合中并非所有選定的特性都包含判別信息。為了降低冗余度，對于TE特征集，引入主成分分析(principal component analysis，PCA)法生成子空間[11,12]。

根據2.1節描述，將隨機選擇過程重復R次，可得到s1,s2,…,sR。隨后，得到一個相關矩陣A，對應于TE特征向量集，定義如下

(10)

通過計算A的特征向量[φ1,φ2,…,φN]，利用PCA構造N維子空間。從一個序列中得到的TE特征集含有各種可能的規整模式，每種模式都對應一個假設，因此，由TE特征集生成的子空間稱為序列假設子空間。通過子空間表示TE特征集的一個優點是可以處理多個序列。在屬于同一類的多個參考序列的情況下，可在一個假設子空間中表示它們的特征集。因此，對未知序列的識別效率更高，因為不需要將未知序列與屬于同一類的每個參考序列進行比較。

接下來，對兩個子空間之間的相似性計算。基于正則角的相似度量也被稱為互子空間法，是一種廣泛應用于3D目標識別技術[13]。設類別c的N維參考子序列為ζc,υ為M維的輸入子空間。第一次的正則角θ1計算如下

(11)

因此，可通過正則角cosθi的余弦來表示兩個假設子空間的相似性。第一個正則角θ1對應于兩組TE特征集之間最大的典型相關關系，可作為兩個對應的子空間中兩個最相似的規整模式之間的距離。第二個正則角θ2對應于兩組TE特征之間的第二大正則相關，依次同理。只有第一個正則角的使用可能會導致不穩定的識別性能，在DTW方法中，只考慮最相似的規整模式。這表明需要多個正則角來考慮子空間中所有可能的規整模式，從而實現更穩定的性能。因此，本文利用所有正則角的平均相似性作為最終相似性

(12)

在RTW操作過程中，將TE特征構建一個矩陣，形成Hankel矩陣[14]。Hankel矩陣H被定義為一個矩陣，矩陣中其它所有元素都與其左下角相鄰位置的元素相等

Hi,j=Hi-1,j+1

(13)

其中，i,j分別表示矩陣的行和列。

首先，Hankel方法中的最大特征數為i+n-1，但是，RTW的最大特征維數為N。

其次，Hankel矩陣的元素是通過式(13)生成。而在RTW中，TE功能是通過隨機抽樣產生的。

這些差異表明，Hankel矩陣比RTW矩陣需要一個較長的序列和一個更大的訓練序列來生成豐富的時空運動詞典。此外，Hankel矩陣只能包含關于運動的有限全局時間信息，全局程度取決于Hankel塊的大小。

為了說明Hankel矩陣的優勢，設SA={1,2,…,20},SB={20,19,…,1}為兩種不同動態學的反向單變量序列數據。SI為與SA相似的含有噪聲的輸入序列，如圖4所示。

圖4 不同矩陣的性能對比

因此，由TE特征集生成的子空間包含比Hankel矩陣更豐富的信息，子空間表示也適用于捕捉嵌入在TE特征集中的信息。在本文算法中，利用Hankel表示和TE特征集SA、SB、SI來生成子空間，隨機抽樣的RTW數設置為1000。圖5為利用PCA的99%累積能量比確定子空間維數時的相似度值。從圖5中得到，當利用Hankel時，SA和SI、SB和SI得到的相似值基本相同。主要是跨越SA和SB軌跡的滿秩子空間彼此重疊。在RTW的隨機化中，SI與SA更相似。

圖5 不同結構下的相似度比較

2.3 線性判別分析分類器

線性判別分析(LDA)是一種簡單、有效的模式辨別算法[15]。LDA的主要是從高維特征中挑選出辨別力最強的低維特征，選出的特征能使同類的數據簇類一起。對于不同種類的數據分別聚集，從而選擇訓練特征與測試特征最相似的對象，以達到抽取分類信息和壓縮特征空間維數的效果。設Rn空間中m個數據x1,x2,…,xm,x為一個n行的矩陣。設有c個類別，數據中的類內、類間散布矩陣為Sw與Sb，表示為

(14)

(15)

其中，ui為第i類樣本均值；u為整體樣本均值；ni為第i類樣本數量；xk為第k個樣本。

LDA作為一個分類算法，希望其類間耦合度低，類內的耦合度高。即Sw的值要小，而Sb的值要大，這樣分類的效果最佳。對此，引入Fisher判別函數J

(16)

其中，ψ為一個n維列向量。Fisher判別通過選擇使J(ψ)中最大的ψ為投射方向，投射后數據間的具有最大Sb和最小Sw。

通過對Fisher判別函數最優化，尋找一組最優判別矢量形成的投射矩陣W，定義如下

(17)

為了保證Sw的非奇異性，通過PCA進行降維處理，消除冗余信息。

LDA的步驟如下：

(1)樣本收集。收集含有不同類型的樣本c個，將樣本分為訓練、測試兩類。

(2)選擇判別方法。根據樣本的不同特點，選擇不同的判別分析手段。對訓練樣本定義判別方程，并給出假設檢驗。

(3)訓練樣本考核。將樣本訓練所有目標的屬性代入到建立的判別方程，進行類別判斷。測量訓練樣本的判別誤差，衡量判別方程的性能。

(4)測試樣本考核。當訓練目標的判別誤差較小時，將測試目標的屬性輸入到判別方程，得出測試目標的判別誤差值。

3 實驗與分析

為評估提出算法的性能，在兩個公開的數據庫：KTH數據集與Hollywood數據集，通過在KTH與Hollywood中進行實驗與統計分析。實驗環境為：Core I5,3.50 GHz CPU,4 GB運行RAM，32位的Win7系統。借助MATLAB7.0進行仿真分析。為了突出本文技術的優異性，將文獻[5]、文獻[6]、文獻[7]作為對照組，定義為A、B、C算法。本文采用的數據集與方法見表1。經過多次實驗，參數設定如下：最短序列長度為36，最長序列長度為120；參考自空間維度范圍為[1,60]，輸入子空間維度范圍為[1,50]；R=30。

3.1 數據集

KTH數據集[16]：是由瑞典皇家理工學院建立的動作識別數據集,KTH包括：走路(Walking)、慢跑(Jogging)、跑步(Running)、拳擊(Boxing)、揮手(Hand waving)和拍手(Hand clapping)6個常見的動作類型，其通過25個人在4種不同的簡單場景中完成。如圖6所示。

表1 實驗數據集與方法

圖6 KTH數據庫

Hollywood數據集[17]主要由10個場景中的12種不同動作組成的3669個動作序列。這12個類別分別為：Answer phone、Drive car、Eat、Fight person、Getout car、Hand Shake、Hug Person、Kiss、Run、Sit Down、Sit Up、Stand Up。其從69個Hollywood影視中獲取形成的。在Hollywood包含了各種不同的情緒、服飾、運動，并且會有相機運動、光照變化、遮擋、背景等干擾，較接近于真實生活。因此，對于Hollywood中的動作識別具有一定難度。Hollywood數據集如圖7所示。

圖7 Hollywood數據集

3.2 實驗結果

表2顯示了在KTH數據集中的混淆矩陣。從表2中可看出，本文方法在KTH中對大部分動作具有良好的識別效果，能夠各動作完成識別。如“Hand clapping”的識別率高達1。“Wave”的識別率為0.98，主要是“Hand clapping”、“Wave”動作與其它5種行為較明顯。此外，“Walk”動作識別率最低，為0.91，其主要易被誤識別為“Run”動作。

表2 KTH數據集的混淆矩陣

表3為在Hollywood數據集中得到的混淆矩陣。從表3中得出，在Hollywood中，對大部分動作具有較高的識別率。對“Hug Person”、“Kiss”、“Fight person ”的識別率高達1。但有些動作的識別率不高，如“Getout car”識別率為0.85，“Drive car”、“Run”、“Sit Up”識別率為0.90。其中“Getout car”易被誤識為“Drive car”動作。主要一些動作的相似度較高，從不同的視角或者受到環境的影響，導致了誤識別的產生。

圖8為在KTH與Hollywood數據集中，利用3個常見算法和本文算法得到的平均識別精度。從圖8中看出，在KTH中的識別率高于Hollywood。相對A、B、C算法，提出的方法在KTH與Hollywood數據集中取得良好表現。主要是本文算法通過RTW反復隨機抽樣提取序列數據的TE特征，保證了TE特征包含足夠的高概率判別幀。然后，根據提取的TE特征形成了低維子空間表示，計算兩個子空間的正則角表示兩個圖像序列之間的相似性。再引入LDA進行分析學習，根據參考序列與測試序列的相似性分類器判別，降低了信息冗余和噪聲干擾。而A算法中基于DTW算法容易導致時間結構變化較大，算法性能不穩定。B算法中密集軌跡特征，在復雜的環境中，由于經常受到光照變化。C算法采用了特征融合與SVM分類學習技術，由于噪聲的影響，容易會出現語義鴻溝。

表3 Hollywood數據集混淆矩陣

圖8 不同算法的識別精度對比

表4為在KTH與Hollywood數據集中統計的不同算法的時間成本。根據表4中得知，在KTH與Hollywood數據集中的平均時間為41.12 s、65.87 s，運算時間少于其它3種算法，具有明顯的優勢。主要是因為基于子空間，避免了所有可能TE特征之間的窮舉匹配，消除和減少無相關特征的不良影響，從而提高分類效率。

表4 算法運行時間對比

4 結束語

為了能夠在復雜環境下對各種動作進行準確快速識別，本文定義了一種RTWE耦合線性判別分析的動作識別算法。針對DTW在動作識別中的不足，對其予以改進，通過對圖像序列隨機抽樣，提取序列TE特征，保證了TE特征包含足夠的高概率判別幀。為了減少了冗余度，引入PCA將TE特征變換為子空間，避免了所有可能TE特征之間的窮舉匹配。測量兩個子空間之間的正則角，根據得到的正則角表示兩個圖像序列之間的相似性。為了完成動作的分類學習，借助線性判別分析LDA進行對圖像序列特征進行分析學習。

通過在KTH與Hollywood數據集上進行算法測試，實驗結果表明了提出的動作識別算法能夠有效對各動作理解與分類，提高了識別率與算法效率，在兩個數據集中的識別準確率均在90%以上，且時耗最短，分別為41.12 s、65.87 s。