陳 晨，詹永照

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

2.1.1 基本概念定義

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

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

表1 頻繁項(xiàng)集K

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

support(M?N)=P(MUN)

(1)

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

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

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

(2)

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

2.2.1 算法基本思路及步驟

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

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

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

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

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

MST:最小支持度閾值。

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

output：L、E中的頻繁項(xiàng)集frequent_itemsets。

Video_rule

{

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

{

E1=Find_Video_frequent_1_itemsets(E,MST)

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

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

{

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

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

For each candidatec∈Ce

count++ //進(jìn)行計(jì)數(shù)

}

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

}

E1=∪kLk//得到視頻動(dòng)作語義概念項(xiàng)集

}

//生成關(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分為兩個(gè)步驟,先連接后剪枝，在得到K項(xiàng)集之前先得到K-1項(xiàng)集。步驟如下：

aproiori_gen

{ //連接：

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

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

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

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

//候選集剪枝

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

delete c; //剪枝

elsec∪Ck

將c添加到Ck中

}

非頻繁項(xiàng)集判斷:

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

{

for each c的K-1項(xiàng)子集

如果都不屬于Lk-1，返回頻繁項(xiàng)集

否則，返回非頻繁項(xiàng)集

}

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

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

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

(3)

當(dāng)分別計(jì)算出待檢測視頻動(dòng)作場景符合視頻動(dòng)作場景M類的得分后，對于待檢測視頻動(dòng)作場景類別L，可由下式進(jìn)行計(jì)算：

(4)

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)庫

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

3.2 實(shí)驗(yàn)設(shè)計(jì)支持度與置信度參數(shù)選擇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)對比分析

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

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

表12 視頻語義場景檢測準(zhǔn)確率 單位：%

4 結(jié)語

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