劉　陽， 羅安平

(沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院， 沈陽 110870)

視頻分析方法的研究作為視頻語義領(lǐng)域的一個(gè)重要分支在學(xué)術(shù)和商用兩個(gè)方面得到了廣泛關(guān)注.不僅因?yàn)槠鋼碛芯薮蟮纳虡I(yè)價(jià)值，也因?yàn)槠渖婕暗叫盘柼幚怼⑷斯ぶ悄堋⒂?jì)算機(jī)視覺、模式識別、人機(jī)交互及數(shù)據(jù)庫等諸多學(xué)科領(lǐng)域，具有重要的理論意義.視頻分析實(shí)際上就是通過提取特定的特征來檢測目標(biāo)事件，并以檢測出的目標(biāo)事件為基礎(chǔ)進(jìn)行分析得到用戶需要的信息[1].

事件檢測就是將用戶感興趣的視頻段從一個(gè)完整的、擁有大量信息的視頻中提取出來[2].最開始的事件檢測方法是通過人工來進(jìn)行目標(biāo)事件的檢測和提取，也就是專業(yè)人士根據(jù)自己的工作經(jīng)驗(yàn)利用純手工的方式，將目標(biāo)事件從完整的視頻中檢測和提取出來.但是當(dāng)今社會(huì)是一個(gè)信息爆炸的社會(huì)，視頻數(shù)據(jù)每天都在高速地增長著，這種方式非常耗費(fèi)人力資源，同時(shí)可靠性很差，容易出錯(cuò)，所以如何對視頻中的目標(biāo)事件進(jìn)行快速且準(zhǔn)確的自動(dòng)檢測成為了本文研究的重點(diǎn).

1　事件檢測過程

本文以足球比賽視頻中的進(jìn)球事件為例，介紹了一種機(jī)器學(xué)習(xí)和人工規(guī)則相結(jié)合的事件檢測方法，其流程圖如圖1所示，具體步驟如下：

1) 將訓(xùn)練樣本視頻段和完整的足球比賽視頻進(jìn)行鏡頭分割，得到訓(xùn)練樣本鏡頭序列和比賽視頻鏡頭序列；

2) 結(jié)合人工規(guī)則和傳統(tǒng)經(jīng)典算法對分割好的鏡頭進(jìn)行語義標(biāo)注；

3) 通過特殊鏡頭定位將疑似目標(biāo)事件的語義鏡頭序列提取出來，本文以進(jìn)球事件為例，通過檢測球門鏡頭初步提取疑似進(jìn)球事件的語義鏡頭序列；

4) 利用訓(xùn)練樣本鏡頭序列計(jì)算隱馬爾科夫模型的初始參數(shù)，建立進(jìn)球事件的隱馬爾科夫模型；

5) 通過前向算法計(jì)算訓(xùn)練樣本鏡頭序列的概率，用來確定判斷的閾值；

6) 計(jì)算該模型下產(chǎn)生這些語義鏡頭序列的概率，并根據(jù)判斷閾值檢測出測試數(shù)據(jù)中的進(jìn)球事件.

圖1　事件檢測流程圖Fig.1　Flow chart of event detection

2　鏡頭分割與語義標(biāo)注

視頻是由連續(xù)圖像幀構(gòu)成的，而當(dāng)一系列保持較高相似性和連續(xù)性的幀組合在一起就形成了鏡頭，因此，足球視頻可以看作是由一系列語義鏡頭組成的.而事件則是一系列按照一定規(guī)律排列的語義鏡頭序列.

若要得到語義鏡頭，首先需要將視頻進(jìn)行鏡頭分割并提取關(guān)鍵幀，再通過對關(guān)鍵幀的處理得到特征值[3]，從而對鏡頭進(jìn)行語義標(biāo)注.本文選取了Twin Comparison算法進(jìn)行鏡頭分割，該算法是一個(gè)能夠識別突變和漸變的雙閾值算法.算法考慮了漸變過程中幀與幀之間的累積差異，并進(jìn)行了兩次視頻掃描，一次使用較高的閾值來檢測突變，另一次使用較低的閾值來檢測潛在的漸變.鏡頭分割完成后就可以按一定規(guī)律進(jìn)行關(guān)鍵幀提取，需要注意的是：關(guān)鍵幀必須是能夠反映鏡頭內(nèi)容的[4]，文中將鏡頭的中間幀作為關(guān)鍵幀.

本文通過提取特征值并結(jié)合決策樹來對鏡頭進(jìn)行分類和語義標(biāo)注.在決策樹的第一層首先區(qū)分的是重放鏡頭和非重放鏡頭，提取重放鏡頭的步驟如下：

1) 利用Logo鏡頭幀間差的特征提取可能的Logo.

2) 利用這些提取的Logo生成一個(gè)相對標(biāo)準(zhǔn)的模板.

3) 利用Logo模板將所有的Logo檢測出來.

4) 按順序兩個(gè)Logo鏡頭之間的鏡頭就是重放鏡頭.決策樹的第2層則是通過顏色直方圖來判斷場地面積，以此將非重放鏡頭分為場內(nèi)鏡頭和場外鏡頭；第3層通過計(jì)算人臉比例提取場內(nèi)鏡頭中的特寫鏡頭；第4層通過計(jì)算場地和球員面積比例將剩下的場內(nèi)鏡頭分為遠(yuǎn)鏡頭和中鏡頭.決策樹流程圖如圖2所示.

圖2　決策樹流程圖Fig.2　Flow chart of decision tree

3　基于球門檢測的進(jìn)球事件定位

從一個(gè)完整的足球比賽視頻中檢測出進(jìn)球事件，首先需要從比賽視頻中提取可能的語義鏡頭序列.當(dāng)發(fā)生進(jìn)球事件時(shí)，最先出現(xiàn)的一定是禁區(qū)附近的區(qū)域，這通常包含了清晰的球門遠(yuǎn)鏡頭或中鏡頭，進(jìn)球完成后，通常會(huì)出現(xiàn)運(yùn)動(dòng)員、教練員或者裁判員的一些特寫鏡頭，最后會(huì)出現(xiàn)進(jìn)球的重放鏡頭，因此，提取可能為進(jìn)球事件的語義鏡頭序列步驟如下：

1) 從分割好的鏡頭中提取關(guān)鍵幀.

2) 對關(guān)鍵幀圖像進(jìn)行robert算子提取邊緣檢測(檢測結(jié)果如圖3所示).

圖3　邊緣檢測Fig.3　Edge detection

3) 利用霍夫變換平行線檢測將兩條相鄰的平行線合并為一條直線(霍夫變換檢測結(jié)果如圖4所示).

圖4　霍夫變換檢測結(jié)果Fig.4　Detection result of Hough transform

4) 在步驟3)得到的線段中選取兩根豎直最長的線段作為候選球門柱.

5) 利用啟發(fā)規(guī)則判斷步驟4)中的候選門柱是否為球門，啟發(fā)規(guī)則如下：

① 判斷兩根球門柱的長度，如果都不在一個(gè)范圍內(nèi)則不是球門，這個(gè)范圍由圖片的分辨率決定，如本文的范圍是15～200個(gè)像素；

② 判斷兩根球門柱之間的距離，如果不在一定范圍內(nèi)則不是球門，本文的范圍是20～260個(gè)像素；

③ 判斷兩根球門柱之間的長度差，如果不在一定范圍內(nèi)則不是球門，本文的范圍是0～20個(gè)像素；

④ 判斷兩根球門柱之間的距離和最長球門柱之間的比值，若不在0.5～3.5的范圍內(nèi)則不是球門；

⑤ 兩個(gè)球門柱構(gòu)成的最小矩形的中心位置應(yīng)處在一定的區(qū)域內(nèi)，其中心點(diǎn)的縱坐標(biāo)應(yīng)在一定范圍內(nèi)，如果不符合則認(rèn)為不是球門，本文的范圍是20～340個(gè)像素.

6) 找到包含球門的鏡頭后，以該語義鏡頭為開始，在語義鏡頭序列中尋找重放鏡頭.根據(jù)實(shí)際情況確定尋找的最大長度，如本文尋找長度為10，即如果開始鏡頭與重放鏡頭之間超過10個(gè)鏡頭，則繼續(xù)尋找下一個(gè)包含球門的鏡頭；反之，該鏡頭序列為候選進(jìn)球事件序列.

圖5則是通過上述方法提取的可能為進(jìn)球事件的語義鏡頭序列關(guān)鍵幀.在取得可能的進(jìn)球事件語義鏡頭序列后，則需要采用隱馬爾科夫模型(hidden Markov models，HMM)來做進(jìn)一步的判斷.

圖5　疑似進(jìn)球事件序列Fig.5　Suspected scoring event sequence

4　基于HMM進(jìn)球事件檢測

HMM可以被看作是一個(gè)關(guān)于進(jìn)球事件的語義鏡頭序列模型，這個(gè)序列可以通過“隨機(jī)行走”產(chǎn)生[5]，即從初始位置W0出發(fā)，通過狀態(tài)轉(zhuǎn)移矩陣A選擇一個(gè)可能的狀態(tài)θ1，并到達(dá)W1.如果W1的狀態(tài)為θ1，則根據(jù)觀察值狀態(tài)矩陣選擇一個(gè)該狀態(tài)下可能的語義鏡頭O1，然后再根據(jù)狀態(tài)矩陣轉(zhuǎn)移到下一個(gè)狀態(tài).通過模型中的狀態(tài)(θ1，θ2，…，θN)產(chǎn)生一系列的語義鏡頭(O1，O2，…，ON)，則狀態(tài)序列產(chǎn)生的語義鏡頭序列的概率便是評判該序列是否為進(jìn)球事件語義鏡頭序列的標(biāo)準(zhǔn).而語義鏡頭序列概率需要使用向前算法來計(jì)算[6]，其定義為

γm(i)=P(O1，O2，…，Om，qm=θi|λ)

(1)

式中：m為鏡頭序列的鏡頭數(shù)；qm為第m個(gè)鏡頭的狀態(tài)；λ為模型狀態(tài).因此一個(gè)語義鏡頭序列的概率為

(2)

對于與模型相符合的序列，HMM能以較大的概率產(chǎn)生序列；與模型不符合的序列，則產(chǎn)生序列的概率會(huì)較小[7].實(shí)踐中一般采用Baum-Welch算法使模型產(chǎn)生更合適的事件語義鏡頭序列，但該算法易收斂于局部最優(yōu)，本文設(shè)計(jì)了一種遺傳算法來訓(xùn)練HMM，從訓(xùn)練樣本中自動(dòng)獲得模型參數(shù).

5　基于Baum-Welch算法的HMM

Baum-Welch算法[8]描述為：給定訓(xùn)練序列語義鏡頭O和模型狀態(tài)λ，定義ξt(i，j)為馬爾可夫鏈在t時(shí)刻處于狀態(tài)θi，t+1時(shí)刻處于狀態(tài)θj的概率[9-10]，即

(3)

式中：αt(i)和βt+1(j)分別為t、t+1時(shí)刻處于狀態(tài)θi條件下產(chǎn)生序列O的概率；aij為狀態(tài)轉(zhuǎn)移矩陣中的對應(yīng)元素；bj(Ot+1)為觀測符號矩陣中的對應(yīng)元素.則t時(shí)刻馬爾可夫鏈處于狀態(tài)θi的概率為

(4)

(5)

6　結(jié)合遺傳算法的HMM

遺傳算法是模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，將可能的解編碼成一個(gè)染色體，并不斷用適應(yīng)度函數(shù)去計(jì)算每條染色體的適應(yīng)值，從中選取最優(yōu)解.

在HMM的參數(shù)π、a和b中，b的選取最為重要，因?yàn)棣袨槌跏紶顟B(tài)量，對模型影響并不是很大，而a為狀態(tài)轉(zhuǎn)移量，由于本文應(yīng)用的HMM中狀態(tài)僅有三個(gè)，且應(yīng)用了從左向右的諾爾馬夫鏈，所以a的選取對模型影響也不是十分明顯.只要通過遺傳算法訓(xùn)練出最優(yōu)的初值b就可以明顯提高HMM的模型性能，使其能夠在盡量少的訓(xùn)練樣本下得到性能最優(yōu)的模型.

6.1　編碼方案

初值b中每個(gè)元素的取值范圍為[0，1]，為了保證精度，本文選取長度為64的二進(jìn)制數(shù)來表示該參數(shù)，它能產(chǎn)生264種不同的編碼.

6.2　適應(yīng)度函數(shù)

適應(yīng)度函數(shù)為判斷每條染色體優(yōu)劣的函數(shù)，訓(xùn)練模型為了能更好地描述代表進(jìn)球事件的語義鏡頭序列，定義染色體優(yōu)劣的評判標(biāo)準(zhǔn)為：在該模型下一個(gè)代表進(jìn)球事件的語義鏡頭序列概率越大越好.適應(yīng)度用各組訓(xùn)練樣本的對數(shù)似然函數(shù)來表示，即

f(λ)=ln(P(Ok|λ))

(6)

6.3　遺傳算子選擇

本文采用了基于適應(yīng)值比例的賭輪盤選擇方法，這種方法可以想象成向劃分好扇區(qū)的輪盤里扔色子，事先生成一組滿足均勻分布的隨機(jī)數(shù)，代表n次擲色子或者n個(gè)色子一起扔，輪盤不動(dòng)，色子所在區(qū)域?yàn)檫x擇結(jié)果，也就是要選擇的染色體.

6.4　終止準(zhǔn)則

常用的終止準(zhǔn)則是預(yù)先設(shè)置最大進(jìn)化的代數(shù)或預(yù)先設(shè)置一個(gè)適應(yīng)度改善的閾值.對于前一種準(zhǔn)則，在進(jìn)化代數(shù)到達(dá)預(yù)置值時(shí)進(jìn)化終止；而后一種準(zhǔn)則是在適應(yīng)度改善低于該閾值時(shí)進(jìn)化停止.本文采用了兩種準(zhǔn)則相結(jié)合的方法，同時(shí)設(shè)置閾值和最大進(jìn)化代數(shù)，在達(dá)到最大迭代數(shù)之前如果達(dá)到閾值，則進(jìn)化結(jié)束.

6.5　訓(xùn)練算法

首先通過對訓(xùn)練樣本的觀察和統(tǒng)計(jì)得到幾組初始參數(shù)，然后將這幾組參數(shù)中的b進(jìn)行編碼，形成種群，通過適應(yīng)度函數(shù)計(jì)算種群中所有染色體的適應(yīng)度，并利用賭輪盤方法選擇染色體，對選擇出的染色體進(jìn)行交叉和變異操作，將形成的子代代替父代放入種群中，重復(fù)以上操作直到達(dá)到終止準(zhǔn)則為止.

7　實(shí)驗(yàn)與結(jié)論

實(shí)驗(yàn)視頻選自2016年英超聯(lián)賽多個(gè)場次的比賽.實(shí)驗(yàn)視頻分為兩部分，一部分作為訓(xùn)練視頻片段，分為4組，分別包含10、20、30、50個(gè)進(jìn)球視頻片段；另一部分作為測試視頻片段，含有30個(gè)進(jìn)球視頻片段和20個(gè)非進(jìn)球視頻片段.實(shí)驗(yàn)通過對測試樣本的識別準(zhǔn)確率來判斷模型的性能.

識別率的比較結(jié)果如表1所示，由表1中可以看出，在訓(xùn)練樣本增加的時(shí)候，本文所提算法的識別率增加速度要遠(yuǎn)高于Baum-Welch算法，因此可以得出，改進(jìn)算法能夠有效避免局部最優(yōu)解.

表1　識別率比較Tab.1　Comparison in recognition rate

本文還做了適應(yīng)性測試以證明本方法的有效性.選取了歐冠和西甲等各個(gè)聯(lián)賽的完整視頻作為測試數(shù)據(jù)進(jìn)行進(jìn)球事件的檢測，適應(yīng)性測試結(jié)果如表2所示.由表2可見，本文提出的事件檢測方法能夠比較準(zhǔn)確地實(shí)現(xiàn)足球視頻中進(jìn)球事件的檢測.

表2　適應(yīng)性測試Tab.2　Adaptability test

綜上所述，本文所提出的基于人工規(guī)則和機(jī)器學(xué)習(xí)相結(jié)合的事件檢測算法可以有效地在不影響準(zhǔn)確率的情況下節(jié)約時(shí)間成本，提高了HMM訓(xùn)練算法在訓(xùn)練樣本相對較少情況下的查全率和查準(zhǔn)率.本算法流程還存在不足之處，如機(jī)器學(xué)習(xí)算法有待改進(jìn).尋求更加詳細(xì)和全面的鏡頭語義標(biāo)注方法，進(jìn)一步提高機(jī)器學(xué)習(xí)算法對目標(biāo)事件的識別能力是今后的研究重點(diǎn).