時(shí)間規(guī)整耦合線性判別分析的動(dòng)作識(shí)別算法

方云錄，苗 茹

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

0 引 言

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

雖然DTW在序列分析中應(yīng)用廣泛，但在多序列分類時(shí)存在一些局限性。例如：由于動(dòng)態(tài)規(guī)劃是一種簡(jiǎn)單的確定性方法，所得到的解對(duì)于包含時(shí)間結(jié)構(gòu)內(nèi)變化大的序列數(shù)據(jù)可能不是最優(yōu)的。其次，DTW沒有消除或忽略影響分類結(jié)果的無關(guān)變化的內(nèi)在機(jī)制。例如，在語音數(shù)據(jù)中，視頻數(shù)據(jù)或揚(yáng)聲器中的光照條件的變化會(huì)顯著地降低DTW的分類方法的性能，對(duì)這些不良影響較敏感。

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

1 動(dòng)態(tài)時(shí)間歸模式

動(dòng)態(tài)時(shí)間歸(DTW)的思想是將測(cè)試時(shí)序和參考時(shí)序數(shù)據(jù)伸長(zhǎng)或縮短，使其長(zhǎng)度相同，再通過Euclidean距離測(cè)量?jī)蓚€(gè)時(shí)序間的距離[8]。通過對(duì)長(zhǎng)度不一的時(shí)序完成非線性規(guī)整，尋找兩者間的最優(yōu)對(duì)應(yīng)位置。隨后，測(cè)量對(duì)應(yīng)位置的Euclidean距離，得到曲線的相似性。該技術(shù)在計(jì)算機(jī)視覺、語音識(shí)別、數(shù)據(jù)挖掘等具有較強(qiáng)的生命力[9]。

設(shè)兩個(gè)時(shí)序?yàn)锳、B，其對(duì)應(yīng)長(zhǎng)度為n、m，表示如下

(1)

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

(2)

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

(3)

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

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

(4)

最佳規(guī)整路線p*可根據(jù)函數(shù)獲得

(5)

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

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

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

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

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

(6)

2 本文動(dòng)作識(shí)別算法

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

圖1 本文算法流程

2.1 TE特征提取

為了處理時(shí)間結(jié)構(gòu)突變問題，利用TE特征來表示時(shí)間結(jié)構(gòu)的局部和全局信息。其中全局信息適應(yīng)總體時(shí)間結(jié)構(gòu)；局部信息處理時(shí)間結(jié)構(gòu)的片斷。

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

(7)

其中，t(·)表示圖像的原始順序。n為構(gòu)造TE特征所選擇的圖像個(gè)數(shù)，對(duì)應(yīng)于識(shí)別所需的有效幀的數(shù)目。

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

(8)

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

圖2 隨機(jī)選擇TE特征概率

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

(9)

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

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

2.2 相似性度量

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

根據(jù)2.1節(jié)描述，將隨機(jī)選擇過程重復(fù)R次，可得到s1,s2,…,sR。隨后，得到一個(gè)相關(guān)矩陣A，對(duì)應(yīng)于TE特征向量集，定義如下

(10)

通過計(jì)算A的特征向量[φ1,φ2,…,φN]，利用PCA構(gòu)造N維子空間。從一個(gè)序列中得到的TE特征集含有各種可能的規(guī)整模式，每種模式都對(duì)應(yīng)一個(gè)假設(shè)，因此，由TE特征集生成的子空間稱為序列假設(shè)子空間。通過子空間表示TE特征集的一個(gè)優(yōu)點(diǎn)是可以處理多個(gè)序列。在屬于同一類的多個(gè)參考序列的情況下，可在一個(gè)假設(shè)子空間中表示它們的特征集。因此，對(duì)未知序列的識(shí)別效率更高，因?yàn)椴恍枰獙⑽粗蛄信c屬于同一類的每個(gè)參考序列進(jìn)行比較。

接下來，對(duì)兩個(gè)子空間之間的相似性計(jì)算?；谡齽t角的相似度量也被稱為互子空間法，是一種廣泛應(yīng)用于3D目標(biāo)識(shí)別技術(shù)[13]。設(shè)類別c的N維參考子序列為ζc,υ為M維的輸入子空間。第一次的正則角θ1計(jì)算如下

(11)

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

(12)

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

Hi,j=Hi-1,j+1

(13)

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

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

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

這些差異表明，Hankel矩陣比RTW矩陣需要一個(gè)較長(zhǎng)的序列和一個(gè)更大的訓(xùn)練序列來生成豐富的時(shí)空運(yùn)動(dòng)詞典。此外，Hankel矩陣只能包含關(guān)于運(yùn)動(dòng)的有限全局時(shí)間信息，全局程度取決于Hankel塊的大小。

為了說明Hankel矩陣的優(yōu)勢(shì)，設(shè)SA={1,2,…,20},SB={20,19,…,1}為兩種不同動(dòng)態(tài)學(xué)的反向單變量序列數(shù)據(jù)。SI為與SA相似的含有噪聲的輸入序列，如圖4所示。

圖4 不同矩陣的性能對(duì)比

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

圖5 不同結(jié)構(gòu)下的相似度比較

2.3 線性判別分析分類器

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

(14)

(15)

其中，ui為第i類樣本均值；u為整體樣本均值；ni為第i類樣本數(shù)量；xk為第k個(gè)樣本。

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

(16)

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

通過對(duì)Fisher判別函數(shù)最優(yōu)化，尋找一組最優(yōu)判別矢量形成的投射矩陣W，定義如下

(17)

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

LDA的步驟如下：

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

(2)選擇判別方法。根據(jù)樣本的不同特點(diǎn)，選擇不同的判別分析手段。對(duì)訓(xùn)練樣本定義判別方程，并給出假設(shè)檢驗(yàn)。

(3)訓(xùn)練樣本考核。將樣本訓(xùn)練所有目標(biāo)的屬性代入到建立的判別方程，進(jìn)行類別判斷。測(cè)量訓(xùn)練樣本的判別誤差，衡量判別方程的性能。

(4)測(cè)試樣本考核。當(dāng)訓(xùn)練目標(biāo)的判別誤差較小時(shí)，將測(cè)試目標(biāo)的屬性輸入到判別方程，得出測(cè)試目標(biāo)的判別誤差值。

3 實(shí)驗(yàn)與分析

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

3.1 數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)集與方法

圖6 KTH數(shù)據(jù)庫(kù)

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

圖7 Hollywood數(shù)據(jù)集

3.2 實(shí)驗(yàn)結(jié)果

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

表2 KTH數(shù)據(jù)集的混淆矩陣

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

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

表3 Hollywood數(shù)據(jù)集混淆矩陣

圖8 不同算法的識(shí)別精度對(duì)比

表4為在KTH與Hollywood數(shù)據(jù)集中統(tǒng)計(jì)的不同算法的時(shí)間成本。根據(jù)表4中得知，在KTH與Hollywood數(shù)據(jù)集中的平均時(shí)間為41.12 s、65.87 s，運(yùn)算時(shí)間少于其它3種算法，具有明顯的優(yōu)勢(shì)。主要是因?yàn)榛谧涌臻g，避免了所有可能TE特征之間的窮舉匹配，消除和減少無相關(guān)特征的不良影響，從而提高分類效率。

表4 算法運(yùn)行時(shí)間對(duì)比

4 結(jié)束語

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

通過在KTH與Hollywood數(shù)據(jù)集上進(jìn)行算法測(cè)試，實(shí)驗(yàn)結(jié)果表明了提出的動(dòng)作識(shí)別算法能夠有效對(duì)各動(dòng)作理解與分類，提高了識(shí)別率與算法效率，在兩個(gè)數(shù)據(jù)集中的識(shí)別準(zhǔn)確率均在90%以上，且時(shí)耗最短，分別為41.12 s、65.87 s。