陳 晨，詹永照

(江蘇大學(xué) 計算機科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013)

0 引言

隨著信息技術(shù)的高速發(fā)展與信息量的激增，產(chǎn)生了數(shù)據(jù)挖掘技術(shù)(KDD)[1]。視頻數(shù)據(jù)挖掘是計算機視覺領(lǐng)域的研究熱點之一，在視頻檢索[2]、視頻點播、智能監(jiān)控等領(lǐng)域應(yīng)用廣泛。視頻復(fù)雜動作場景概念分析是視頻復(fù)雜事件分析中的一個重要內(nèi)容，用視頻動作語義概念間的關(guān)聯(lián)關(guān)系分析高層次視頻復(fù)雜動作場景概念或視頻復(fù)雜事件概念[3-4]，能更加合理地刻畫視頻復(fù)雜動作場景概念或視頻復(fù)雜事件概念的內(nèi)在本質(zhì)，有助于提高分析的準確性。

然而在應(yīng)用過程中，由于視頻信息龐大、視頻底層特征與高層語義概念之間存在語義鴻溝(Semantic Gap)[5-6]等問題，增加了視頻挖掘的復(fù)雜性。目前的視頻動作語義概念檢測分析方法可大致分為3類[7]：

(1)基于預(yù)定義動作語義概念模型的動作語義概念檢測分析。Sadlier[7]主要基于運動視頻動作語義概念特點建立動作語義概念檢測器，通過與SVM結(jié)合，生成模型以推斷動作語義概念的發(fā)生；Ye等[8]提出動作語義概念網(wǎng)(EventNet)建立視頻動作語義概念庫，從而對視頻動作語義概念進行檢測。該方法的主要特點是采用預(yù)定義的規(guī)則或限制條件等構(gòu)建動作語義概念模型，由于其需要相關(guān)環(huán)境的先驗知識，用于特定情況下的動作語義概念檢測，而不能處理新的動作語義概念，因而具有很大的局限性。

(2)基于訓(xùn)練數(shù)據(jù)學(xué)習(xí)動作語義概念模型的動作語義概念檢測分析[10]。采用隱Markov模型或動態(tài)貝葉斯網(wǎng)絡(luò)等[11-12]方法分析各關(guān)鍵幀特征值之間的關(guān)系，并挖掘各鏡頭之間的關(guān)聯(lián)，進而檢測出一些典型的動作語義概念。M Chakroun等[13]采用神經(jīng)網(wǎng)絡(luò)模型對視頻特征(HOG/HOF)進行約簡，并支持向量機增量模型，對每一個動作語義概念狀態(tài)進行建模，檢測視頻動作語義概念。

(3)基于聚類分析的動作語義概念檢測分析。該方法樣本標簽是未知的，主要用于異常動作語義概念檢測。在特殊空間下，正常動作語義概念與異常動作語義概念可以采用K-means聚類算法[14]與K-近鄰法進行區(qū)分。

以上幾類視頻動作語義概念檢測方法對于基本低層視覺特征難以做到準確描述，但對于高層語義特征描述的視頻，視頻中感興趣動作語義概念之間的關(guān)系沒有直接體現(xiàn)視頻動作語義概念之間的關(guān)系。本文提出基于Aproiri[15-16]算法視頻動作語義概念關(guān)聯(lián)關(guān)系的視頻動作場景檢測，以挖掘視頻中動作語義概念的關(guān)聯(lián)性。首先在不同的視頻場景下，挖掘出訓(xùn)練視頻動作語義概念之間的頻繁模式，得出動作語義概念之間的強關(guān)聯(lián)規(guī)則；然后通過挖掘出的強關(guān)聯(lián)規(guī)則，構(gòu)造關(guān)聯(lián)規(guī)則庫；最后通過對比關(guān)聯(lián)規(guī)則庫，檢測出相關(guān)聯(lián)動作語義概念隸屬的視頻類別。

1 相關(guān)研究工作

面對海量數(shù)據(jù)，從中發(fā)現(xiàn)有用信息或知識是具有挑戰(zhàn)性的課題，數(shù)據(jù)挖掘即是為了滿足這一要求而發(fā)展起來的。本文研究的Aproiri算法是由Agrawal與Srikant[17]于1994年首次提出的布爾關(guān)聯(lián)規(guī)則挖掘算法。典型例子為購物籃分析，商場通過發(fā)現(xiàn)顧客放入他們“購物籃”中商品之間的關(guān)聯(lián)，分析顧客購物習(xí)慣。“那些90%購買面包的客戶也會購買牛奶”，其直觀意義是需要考慮用戶偏好，而這些信息即是人們想要挖掘的知識。

目前,關(guān)聯(lián)規(guī)則應(yīng)用于視頻檢測的研究還比較少。Lin等[18]提出基于Semantic的視頻關(guān)聯(lián)語義關(guān)聯(lián)框架方法，應(yīng)用多重對應(yīng)分析(MCA)將特征與類投影到一個新的主成份空間中，并發(fā)現(xiàn)特征值對與類之間的相關(guān)性，取得了較好的分類檢測效果；Yuya Matsuo等[19]采用關(guān)聯(lián)規(guī)則反映視頻編輯模式；Z等[20]探索視頻中基于鏡頭的關(guān)聯(lián)規(guī)則。上述算法都是利用不同視角對視頻進行挖掘檢測，而視頻本身作為非結(jié)構(gòu)化數(shù)據(jù)，由多種文件融合而成，與傳統(tǒng)事務(wù)關(guān)聯(lián)存在很大差異。視頻層次結(jié)構(gòu)從小到大分別為：關(guān)鍵幀、鏡頭、場景及整個視頻。因此，本文從不同層次對視頻數(shù)據(jù)進行挖掘。

2 基于動作關(guān)聯(lián)關(guān)系的視頻動作場景檢測方法

2.1 基于Aproiri的視頻動作語義概念關(guān)聯(lián)規(guī)則挖掘

2.1.1 基本概念定義

定義1 項集(Itemsets)：視頻預(yù)處理結(jié)構(gòu)，即視頻的動作語義概念集，用相應(yīng)符號ζ表示，如ζ={I1,I2,…,Im}是項的集合,與其相關(guān)的數(shù)據(jù)E是數(shù)據(jù)庫事務(wù)集合，每一個事務(wù)T是一個非空項集，T是E的子集。

定義2 K項集(K-Itemset):包含K個項的集合，是所有K項關(guān)聯(lián)的集合，每一個元素都是K項關(guān)聯(lián)。

表1 頻繁項集K

定義3 支持度(support):M、N都為項集，其中support是E中包含M∪N(集合M和集合N的并)的百分比。其數(shù)學(xué)表達式為：

support(M?N)=P(MUN)

(1)

定義4 頻繁項集：如果項集I的支持度滿足預(yù)先定義的最小支持度閾值(MST),則I被稱為頻繁項集。

定義5 置信度(Confidence)：如果項集I的支持度滿足規(guī)則M?N,該規(guī)則在事務(wù)集E中擁有置信度(MCT)，其數(shù)學(xué)表達式為：

confidence(M?N)=P(N|M)

(2)

定義6 關(guān)聯(lián)規(guī)則是形如M?N的蘊涵式，其中M為關(guān)聯(lián)規(guī)則的先導(dǎo)，N為后繼。關(guān)聯(lián)規(guī)則是M與N在E中同時出現(xiàn)的情況所占的百分比，即同時出現(xiàn)的概率。在E中已經(jīng)出現(xiàn)M的情況下N也出現(xiàn)的概率，稱為M、N滿足最小支持度(MST)與最小置信度(MCT)的強關(guān)聯(lián)規(guī)則。

2.2.1 算法基本思路及步驟

算法基本思路流程有以下3個步驟，如圖1所示。

圖1 視頻動作語義概念關(guān)聯(lián)規(guī)則挖掘

先對視頻中的基本動作語義概念進行序列化語義概念標注獲取，設(shè)基本動作語義概念有N類，則每個時刻都有N個動作語義概念標注信息，對相應(yīng)場景的每個視頻中T時刻出現(xiàn)的基本動作語義概念進行歸一化處理，成為一個N維基本動作語義概念的向量，再采用Apriori算法挖掘視頻動作語義概念的關(guān)聯(lián)規(guī)則，最后生成該場景的動作概念關(guān)聯(lián)規(guī)則集。

視頻動作語義概念關(guān)聯(lián)規(guī)則挖掘算法描述如下：

input：traindatasets E (訓(xùn)練數(shù)據(jù)動作語義概念事務(wù)集)。

MST:最小支持度閾值。

MCT：最小置信度,使用逐層迭代的方法。

output：L、E中的頻繁項集frequent_itemsets。

Video_rule

{

//產(chǎn)生頻繁項集

{

E1=Find_Video_frequent_1_itemsets(E,MST)

for(k=2;E1-1≠?;k++){

Ck=aproiori_gen(Lk-1)// 連接與剪枝

{

掃描動作語義概念數(shù)據(jù)庫中的每一個事務(wù)e∈E

Ce=subset(Ck,e) //得到e的子集作為候選集

For each candidatec∈Ce

count++ //進行計數(shù)

}

count>=MST//對于Ck的計數(shù), 滿足最小支持度(MST)

}

E1=∪kLk//得到視頻動作語義概念項集

}

//生成關(guān)聯(lián)規(guī)則

If frequent_itemsets El,{

s?El且s≠φ//產(chǎn)生El的所有非空子集s

for each s{

printf rules?(El-s) //生成規(guī)則

}

}

}

連接與剪枝：連接與剪枝算法aproiori_gen分為兩個步驟,先連接后剪枝，在得到K項集之前先得到K-1項集。步驟如下：

aproiori_gen

{ //連接：

for each 事務(wù)項集l1∈Lk-1

for each 事務(wù)項集l2∈Lk-1

if(項集LK-1是可連接的，之前的K-2項相同)

l1∞l2// l1與l2是可連接的

//候選集剪枝

if has_infrequent_subset(c, Lk-1)// 判斷是否為非頻繁項集

delete c; //剪枝

elsec∪Ck

將c添加到Ck中

}

非頻繁項集判斷:

has_infrequent_subset(c:K項候選集，Lk-1為K-1項集)

{

for each c的K-1項子集

如果都不屬于Lk-1，返回頻繁項集

否則，返回非頻繁項集

}

2.2 視頻復(fù)雜動作語義概念檢測分類

將各類視頻復(fù)雜動作語義概念中的動作語義概念關(guān)聯(lián)規(guī)則集挖掘出來后，根據(jù)所產(chǎn)生的強關(guān)聯(lián)規(guī)則，對訓(xùn)練集的視頻動作語義概念進行檢測分類，但需合理定義復(fù)雜動作語義概念檢測分類準則。

本文考慮到各種規(guī)則在各類動作語義概念中，不同支持度對視頻分類貢獻不同，將待測視頻中所有符合規(guī)則的置信度相加，除以動作語義概念規(guī)則集中所有規(guī)則的置信度，作為該類視頻動作語義概念的檢測分類依據(jù)。設(shè)視頻動作場景有M類，則計算待測視頻為第i類場景的得分scorei，其計算公式如下：

(3)

當分別計算出待檢測視頻動作場景符合視頻動作場景M類的得分后，對于待檢測視頻動作場景類別L，可由下式進行計算：

(4)

即計算其對應(yīng)的所有視頻動作語義場景類別得分，取得分最大的類別作為待測視頻動作場景的最終類別。

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)庫

本文首先采用動作識別數(shù)據(jù)庫Charades daily human activities Data Set[21]，該數(shù)據(jù)庫包含15類室內(nèi)復(fù)雜動作語義概念：Basement、Bathroom、Bedroom、Closet、Dining room、Entryway、Garage、Laundry room、Living room、Kitchen、Home Office、Hallway、Stairs、Recreation room、Pantry、Other。本實驗選取其中5類復(fù)雜動作語義概念：Bedroom、Bathroom、Kitchen、Living room、Home Office，總共4 336段視頻。在該視頻庫數(shù)據(jù)集中，對視頻中出現(xiàn)的動作語義概念進行序列標注，總共157個動作，并對視頻進行標準化。即對每個視頻截取50s片段，然后對每段視頻中動作語義概念的出現(xiàn)次數(shù)進行檢測，最后將視頻中每個動作語義概念出現(xiàn)的時間及共同出現(xiàn)的動作語義概念，作為最終的實驗輸入數(shù)據(jù)。

3.2 實驗設(shè)計支持度與置信度參數(shù)選擇

由于采用關(guān)聯(lián)規(guī)則的匹配程度進行動作語義場景檢測，各類場景的關(guān)聯(lián)規(guī)則集大小對檢測準確率有著重要影響，故需考慮支持度、置信度參數(shù)的變化，從而挖掘出相應(yīng)場景的關(guān)聯(lián)規(guī)則集，并選擇檢測準確率最高的參數(shù)作為該類場景挖掘的支持度與置信度參數(shù)，以保證挖據(jù)的規(guī)則集可以有效表達與檢測該類場景。因此，對視頻中5類復(fù)雜動作場景進行關(guān)聯(lián)規(guī)則挖掘，其中MST取值范圍為[0.02，0.09]，MCT取值范圍為[0.20，0.60]，然后對挖掘出的規(guī)則數(shù)與用相關(guān)規(guī)則進行場景檢測分類的準確率進行分析。

在Bedroom場景中挖掘出的規(guī)則數(shù)與用規(guī)則集進行語義場景檢測的準確率如表2、表3所示。由表3可以看出，在該語義場景下選取的最佳參數(shù)MST=0.05，MCT=0.40。

表2 Bedroom在不同MST與MCT下的規(guī)則數(shù)

表3 Bedroom在不同MST與MCT下的檢測準確率 單位：%

在Bathroom場景中挖掘出的規(guī)則數(shù)與用規(guī)則集進行語義場景檢測的準確率如表4、表5所示。由表5可以看出，在該語義場景下選取的最佳參數(shù)MST=0.04，MCT=0.60。

表4 Bathroom在不同MST與MCT下的規(guī)則數(shù)

在Kitchen場景中挖掘出的規(guī)則數(shù)與用規(guī)則集進行語義場景檢測的準確率如表6、表7所示。由表7可以看出，在該場景下選取的最佳參數(shù)MST=0.05，MCT=0.50。

在Living_room場景中挖掘出的規(guī)則數(shù)與用規(guī)則集進行語義場景檢測的準確率如表8、表9所示。由表9可以看出，在該場景下選取的最佳參數(shù)MST=0.06，MCT=0.50。

表5 Bathroom在不同MST與MCT下的檢測準確率 單位：%

表6 Kitchen在不同MST與MCT下的規(guī)則數(shù)

表7 Kitchen在不同MST與MCT下的檢測準確率 單位：%

表8 Living_room在不同MST與MCT下的規(guī)則數(shù)

在Home_Office場景中挖掘出的規(guī)則數(shù)與用規(guī)則集進行檢測的準確率如表10、表11所示。由表11可以看出，在該場景下選取的最佳參數(shù)MST=0.06，MCT=0.60。

表9 Living_room在不同MST與MCT下的檢測準確率 單位：%

表10 Home_Office在不同MST與MCT下的規(guī)則數(shù)

表11 Home_Office在不同MST與MCT下的檢測準確率 單位：%

以上結(jié)果可以看出5類視頻在不同參數(shù)下的表現(xiàn)情況，參數(shù)選取不同時，檢測性能也有較大差異。各個復(fù)雜場景挖掘的關(guān)聯(lián)規(guī)則數(shù)目對場景檢測分類準確率有一定影響，若MST>0.07，實驗中獲得關(guān)聯(lián)規(guī)則的數(shù)目偏少，過濾掉了大多數(shù)規(guī)則，會導(dǎo)致計算準確率偏低；若MST<0.03，MCT<0.30，挖掘出的關(guān)聯(lián)規(guī)則中則存在大量置信度較小的規(guī)則，降低了視頻語義場景檢測準確率。

3.3 實驗對比分析

為了驗證本文方法的有效性，在相同訓(xùn)練集與測試集下，將本文方法與SVM方法進行實驗對比分析。采用5倍交叉[22]實驗得出分類準確率，每次交叉實驗選取各類視頻場景訓(xùn)練集與測試集之比為8∶2。由5類場景的檢測準確率對比(見表12)可以看出，本文方法對5類場景的檢測準確率均高于SVM方法，并且對各類場景的檢測準確率更加均衡，其平均準確率比SVM高1.19%。

實驗結(jié)果表明，基于動作語義概念關(guān)聯(lián)規(guī)則表達復(fù)雜動作場景是有效的，采用場景的動作語義關(guān)聯(lián)規(guī)則集進行動作場景檢測分類，有利于提高復(fù)雜動作場景檢測準確率。

表12 視頻語義場景檢測準確率 單位：%

4 結(jié)語

針對視頻監(jiān)控多個動作語義概念形成的視頻場景或復(fù)雜事件檢測分類問題，本文提出一種基于基本動作語義概念關(guān)聯(lián)的視頻復(fù)雜動作場景檢測方法。該方法對相應(yīng)視頻場景中的所有動作語義概念采用Aproiri算法進行關(guān)聯(lián)規(guī)則挖掘，將挖掘得到的動作語義概念關(guān)聯(lián)規(guī)則作為視頻復(fù)雜動作場景檢測分類依據(jù)，并對測試視頻中符合相應(yīng)場景類別的關(guān)聯(lián)規(guī)則情形進行場景檢測分類。實驗結(jié)果表明，該方法可以挖掘出視頻中動作之間的關(guān)聯(lián)關(guān)系，并快速、有效地實現(xiàn)對視頻復(fù)雜動作場景概念的檢測分類。下一步工作還需要引入動作間的時序關(guān)系并對其進行挖掘，從而進一步提高視頻復(fù)雜動作場景的檢測分類準確率。