趙杰雪，豐洪才，楊 琳

(武漢輕工大學 數(shù)學與計算機學院，湖北 武漢 430023)

?

基于遺傳算法的多模態(tài)視頻場景分割算法

趙杰雪，豐洪才，楊 琳

(武漢輕工大學 數(shù)學與計算機學院，湖北 武漢 430023)

視頻場景分割可縮短檢索時間，提高檢索的準確度，已成為視頻領(lǐng)域的研究熱點之一。為了實現(xiàn)快速、準確的視頻場景分割，提出了一種基于遺傳算法的多模態(tài)視頻場景分割算法，根據(jù)多模態(tài)特征融合的思想提取視頻關(guān)鍵幀中不同模態(tài)的物理特征，對鏡頭間同種模態(tài)數(shù)據(jù)的相似度和不同模態(tài)數(shù)據(jù)的相關(guān)度進行融合，并計算出不同鏡頭之間的相似度，構(gòu)造鏡頭相似度矩陣，利用遺傳算法實現(xiàn)視頻場景的分割。實驗數(shù)據(jù)驗證了該算法對視頻場景有較好的分割效果，查全率和查準率分別達到86.9%和87.7%，F(xiàn)值達到87.3%。

場景分割;多模態(tài);遺傳算法;相似度融合;鏡頭相似度矩陣

視頻場景分割是視頻檢索中關(guān)鍵性的一步，可縮短檢索時間、提高檢索的準確度，已成為視頻領(lǐng)域的研究熱點之一。國內(nèi)外學者進行了大量視頻場景分割方法的研究，取得了一定程度上的突破。如文獻[1]提出的基于幀熵和SURF(speeded up robust features)特征的滑動窗場景檢測方法，該方法簡單、效率高，對電影視頻分割效果較好，但其只采用視覺特征，忽視了視頻多種模態(tài)數(shù)據(jù)之間存在互補關(guān)系，因此對于動畫等一些視頻內(nèi)容高強度變化的視頻效果不佳，不具有通用性。此外，還有一些場景分割方法雖然利用了多種模態(tài)特征融合的思想，但是只針對某一特定類型的視頻，如新聞視頻[2]、體育視頻[3]、電影視頻[4]等，該方法分割準確度較高，但通用性較差，且需要特定領(lǐng)域的先驗知識。

遺傳算法是全局優(yōu)化算法，其計算花費時間少、魯棒性高、可擴展性強，且具有較好的收斂性。因此針對文獻[1]中場景分割算法通用性低、局限性強的問題，筆者結(jié)合多模態(tài)特征融合的思想將遺傳算法應(yīng)用到視頻場景分割的領(lǐng)域當中，提出了一種基于遺傳算法的多模態(tài)視頻場景分割算法，首先對視頻的3種底層特征進行提取，并度量鏡頭間的相似度，構(gòu)造出鏡頭相似度矩陣；然后結(jié)合遺傳算法實現(xiàn)視頻場景的分割，并對過分割視頻場景進行合并。實驗驗證了該算法對視頻場景有較好的分割效果，查全率和查準率分別達到86.9%和87.7%，F(xiàn)值達到87.3%。

1 底層特征提取和鏡頭相似度度量

1.1 圖像特征向量

筆者采用文獻[5]中對視頻底層特征提取的方法，分別提取出圖像特征向量H、音頻特征向量A及文本特征向量T。鏡頭關(guān)鍵幀的圖像特征向量H的表達式如式(1)所示：

H=(h0,h1,h2,…,h71)

(1)

1.2 音頻特征向量

一個鏡頭包含一段音頻序列，該鏡頭的音頻特征向量A的表達式如式(2)所示：

A=(En,Zn,C1,C2,…,C12)

(2)

式中：En為短時平均能量；Zn為過零率ZCR；Cτ為MFCC系數(shù)，τ=1,2,…,12。

1.3 文本特征向量

一個鏡頭的文本特征向量T為：

T=(ω1(d),ω2(d),…,ωk(d),…,ωn(d))

(3)

式中：n為視頻中關(guān)鍵詞的總數(shù)；ωk(d)為詞條tk在文檔d中所占權(quán)重。

1.4 鏡頭間同種模態(tài)相似度計算

(1)采用直方圖相交法計算鏡頭Shoti與鏡頭Shotj圖像特征之間的相似度。

(4)

(2)利用歐氏距離計算鏡頭Shoti與鏡頭Shotj音頻特征之間的相似度。

SimA(i,j)=

(5)

(3)利用余弦距離計算鏡頭Shoti與鏡頭Shotj文本特征之間的相似度。

(6)

由式(4)～式(6)可得鏡頭Shoti與鏡頭Shotj之間同種模態(tài)數(shù)據(jù)的相似度Sim′(i,j)為：

Sim′(i,j)=ωHSimH(i,j)+ωASimA(i,j)+ωTSimT(i,j)

(7)

其中，ωH、ωA、ωT分別為鏡頭間圖像、音頻、文本相似度分量的權(quán)重。

1.5 鏡頭間不同模態(tài)相關(guān)度計算

利用張鴻等[6]提出的典型相關(guān)性分析法計算鏡頭Shoti與鏡頭Shotj不同模態(tài)之間的相關(guān)度，分別得到圖像與音頻特征之間的相關(guān)度ρH,A(i,j)、音頻與文本特征之間的相關(guān)度ρA,T(i,j)及圖像與文本特征之間的相關(guān)度ρH,T(i,j)：

(8)

(9)

(10)

由式(8)～式(10)得出鏡頭Shoti與鏡頭Shotj之間不同模態(tài)數(shù)據(jù)的相關(guān)度Cor′(i,j)：

Cor′(i,j)=ωH,AρH,A(i,j)+ωA,TρA,T(i,j)+ωH,TρH,T(i,j)

(11)

其中，ωH,A、ωA,T、ωH,T分別為圖像與音頻、音頻與文本、圖像與文本相關(guān)度分量的權(quán)重。

1.6 相似度與相關(guān)度融合

將鏡頭間同種模態(tài)數(shù)據(jù)的相似度Sim′(i,j)與不同模態(tài)數(shù)據(jù)的相關(guān)度Cor′(i,j)進行加性融合得到鏡頭Shoti與鏡頭Shotj之間的相似度Cor(i,j)，如式(12)所示。

Cor(i,j)=ωSimSim′(i,j)+ωCorCor′(i,j)

(12)

其中，ωSim、ωCor分別為同種模態(tài)數(shù)據(jù)的相似度與不同模態(tài)數(shù)據(jù)的相關(guān)度所占權(quán)重。

1.7 鏡頭相似度矩陣

在用遺傳算法[7]進行場景分割之前需先計算鏡頭相似度矩陣(shotsimilaritymatrix,SSM)。為了提高迭代效率，一段一段地進行檢測，每一段為100個鏡頭。這樣SSM就是一個100×100的對稱矩陣，其值全部初始化為-1，然后根據(jù)式(12)計算出不同鏡頭之間的相似度，并將其保存在矩陣SSM中，如式(13)所示。

(13)

其中，元素SSMi, j表示鏡頭Shoti與Shotj之間的相似度值Cor(i,j)(i≠j),其值滿足以下特性：0≤Cor(i,j)<1，Cor(i,j)=Cor(j,i)。

2 遺傳算法在場景分割中的應(yīng)用

假設(shè)得到的鏡頭分割結(jié)果為：Shot1,Shot2,…,ShotL，其中L為鏡頭總數(shù)，因為每100個鏡頭作為一段進行檢測，所以L應(yīng)滿足條件：L≤100。

2.1 個體編碼方案

一段視頻中連續(xù)L個鏡頭的集合稱之為一個個體。根據(jù)鏡頭相似度矩陣SSM采用二進制編碼方式對個體進行編碼(I1,I2,…,Ii,…,IL-1)，Ii∈{0,1}。個體編碼與鏡頭序列的對應(yīng)關(guān)系如圖1所示。

圖1 個體編碼與鏡頭序列對應(yīng)圖

Ii∈{0,1}為個體中的一個基因，Ii=0表示鏡頭Shoti和Shoti+1屬于同一個場景；Ii=1表示鏡頭Shoti和Shoti+1不屬于同一個場景。根據(jù)鏡頭相似度矩陣SSM得出個體編碼的依據(jù)為：如果SSMi,i+1<給定閾值Th(根據(jù)多次試驗的經(jīng)驗，筆者取Th=0.6)，說明鏡頭Shoti和Shoti+1很有可能不屬于同一個場景，就令I(lǐng)i=1；否則，令I(lǐng)i=0。于是，個體的編碼就是場景劃分的表示。

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

適應(yīng)度函數(shù)[8]是用于評估個體優(yōu)劣的指標。筆者以打分的形式衡量個體的適應(yīng)度，個體得分越高，意味著適應(yīng)度越高，個體越優(yōu)，所劃分的場景正確率越高。適應(yīng)度函數(shù)定義如下：

(14)

2.3 交叉

采用單點交叉的方法，種群中的個體隨機配對，配成對的兩個個體以交叉概率Pc相互交換基因，交叉位置M隨機產(chǎn)生。經(jīng)過多次試驗，取Pc=0.8，交叉過程如下所示：

交叉前：

PA(I1,I2,…，IM-1，IM，IM+1，…,IL-1)

PB(I′1,I′2,…，I′M-1，I′M，I′M+1，…,I′L-1)

交叉后：

Pnew1(I1,I2,…，IM-1，IM，I′M+1，…,I′L-1)

Pnew2(I′1,I′2,…，I′M-1，I′M，IM+1，…,IL-1)

2.4 變異

變異算子采用基本位變異，即隨機選取一個基因以變異概率Pm對其進行取反操作，變異位置M是隨機產(chǎn)生的，將IM取反變異成1-IM。經(jīng)過多次試驗，取Pm=0.1，變異過程如下所示：

變異前：

Pnew(I1,I2,…，IM-1，IM，IM+1，…,IL-1)

變異后：

Pnew(I1,I2,…，IM-1，1-IM，IM+1，…,IL-1)

2.5 選擇

選擇操作采用輪盤賭選擇法[9-10]與最優(yōu)保存策略[11]相結(jié)合的方式，具體操作步驟如下：

(1)用輪盤賭選擇法從當前種群中選擇兩個個體直接復制到下一代種群，其余個體經(jīng)過交叉和變異操作之后產(chǎn)生相同數(shù)量的新個體，新個體與之前選出來的兩個個體一起構(gòu)成新的種群。

(2)從步驟(1)產(chǎn)生的新種群之中找到適應(yīng)度最高和最低的個體。

(3)將新種群中最高的適應(yīng)度與截止到目前最高的適應(yīng)度作比較，若前者大于后者，將前者所對應(yīng)的個體作為截止到目前適應(yīng)度最高的個體；否則，用截止到目前適應(yīng)度最高的個體替換新種群中適應(yīng)度最低的個體。

3 視頻場景分割

根據(jù)鏡頭相似度矩陣得到個體的初始編碼，稱為I(1)，而I(1)不一定就是正確劃分場景的個體，因此由個體I(1)經(jīng)過變異、交叉操作得到16個個體的初始種群，利用遺傳算法不斷迭代，產(chǎn)生更多新個體，向著最優(yōu)解方向進化直至達到終止代數(shù)，找到適應(yīng)度最高的個體，根據(jù)該個體的編碼確定場景邊界。

3.1 算法描述

利用遺傳算法進行視頻場景分割的具體實施步驟如下：

輸入：根據(jù)鏡頭相似度矩陣SSM得到個體初始編碼I(1):(I1,I2,…,IL-1)。

輸出：場景邊界scene[L][2]。

變量說明：sceneCount表示場景計數(shù)器，用于記錄場景的個數(shù)；scene[L][2]用于記錄場景的邊界；scene[k][0]記錄的是場景k+1開始的鏡頭編號；scene[k][1]記錄的是場景k+1終止的鏡頭編號(0≤k

(1)將個體I(1)按照上述變異方法，取Pm=1變異得到新個體I(2)。

(2)將I(1)，I(2)按照上述交叉方法，交叉得到兩個新個體I(3)，I(4)，由I(1)，I(2)，I(3)，I(4)交叉得到4個新個體I(5)，I(6)，I(7)，I(8)，再由I(1)，I(2)，…，I(8)這8個個體交叉得到8個新個體I(9)，I(10)，…，I(16)，并將I(1)，I(2)，…，I(16)這16個個體作為初始種群。

(3)按照式(14)算得種群中每一個個體的適應(yīng)度值。

(4)判斷當前迭代次數(shù)是否達到50次(根據(jù)多次試驗，算法在迭代到40次時接近收斂，因此將終止迭代數(shù)定為50代)，若未達到50次，則按照上述選擇方法產(chǎn)生下一代種群，并返回至步驟(3)；否則，輸出當前代中適應(yīng)度最高的個體。

(5)初始化。將sceneCount初始化為0，scene[sceneCount][0]初始化為1，i初始化為1。

(6)針對由步驟(4)中得到的適應(yīng)度最高個體的編碼，若i=L-1，則跳轉(zhuǎn)至步驟(8)；否則判斷Ii是否等于1，若Ii=1，說明鏡頭Shoti是該場景的結(jié)束鏡頭，將i寫入數(shù)組scene[sceneCount][1]，sceneCount自增，將i+1作為下一個場景的起始鏡頭寫入scene[sceneCount][0]。

(7)令i=i+1，進行下一個基因的判斷，返回至步驟(6)。

(8)將最后一個鏡頭L寫入scene[sceneCount][1]，sceneCount=sceneCount+1，場景分割完畢，算法結(jié)束。

3.2 過分割處理

通過參閱多篇文獻，得知一個真正場景包括的鏡頭數(shù)應(yīng)當不小于3個[12]。若經(jīng)上述演化之后存在鏡頭數(shù)小于3的場景，則屬于過分割，應(yīng)對其進行合并。筆者定義兩個鏡頭類CA，CB之間的相似度為：

(15)

其中，i和j分別代表鏡頭Shoti和鏡頭Shotj。將經(jīng)過演化之后得出的場景都作為鏡頭類，找出過分割的場景，根據(jù)式(15)計算出該鏡頭類與前、后鏡頭類之間的相似度，與相似度較大的那個鏡頭類進行合并，直到?jīng)]有過分割的場景為止。

4 實驗結(jié)果分析

為了檢驗筆者算法，選擇4種不同種類的視頻片段進行測試，分別是CCTV新聞聯(lián)播(記為NNB)、電影《阿凡達》片段(記為Avatar)、動畫《貓和老鼠：綠野仙蹤》片段(記為TAJ)及NBA籃球比賽片段(記為NBA)。由于場景的劃分沒有統(tǒng)一的標準，不同的人分割結(jié)果可能不同，因此實驗中通過多人商討共同確定實驗素材中場景的分割點即起始邊界，以保證場景劃分的正確性。實驗素材涵蓋了所有類型的場景，具有一定的代表性，總時長約135′51″，共195 535幀，1 266個鏡頭，107個場景，視頻片段詳細信息如表1所示。

表1 視頻片段詳細信息

使用查全率(Recall)、查準率(Precision)及綜合度量指標F檢測算法的性能，定義如下：

(16)

(17)

(18)

式中：nc為檢測正確的場景個數(shù)；nm為檢測時漏掉的場景個數(shù)；nf為檢測錯誤的場景個數(shù)。

將筆者算法與文獻[1]算法進行比較，進而說明筆者算法性能的優(yōu)劣。實驗結(jié)果如表2所示。

表2 筆者算法與文獻[1]算法結(jié)果對比

從表2中可以看出，在不同類型的視頻中，筆者算法的查全率和查準率總的來說較文獻[1]的算法均有明顯提高，綜合度量指標F值也相對較高。實驗中所選取的4種不同類型的視頻片段均取得了不錯的效果，其中分割最好的是新聞視頻，F(xiàn)值高達98.0%，查全率和查準率分別比文獻[1]的算法提高了9.1%、13.5%；體育視頻和電影的場景分割效果比新聞視頻要差一些，F(xiàn)值分別為92.7%和86.6%；分割效果最差的是動畫，F(xiàn)值為75.0%,比文獻[1]提高了12.4%。可見，筆者算法與文獻[1]的算法相比，場景分割的效果更好，且具有一定的通用性。

5 結(jié)論

筆者通過對視頻多模態(tài)底層特征的提取，將同種模態(tài)數(shù)據(jù)的相似度和不同模態(tài)數(shù)據(jù)的相關(guān)度融合得出鏡頭間的相似度，利用遺傳算法實現(xiàn)了對視頻場景的快速分割，并且對過分割的場景做了相應(yīng)的合并處理，取得了較好的實驗效果。多模態(tài)特征的融合對縮減“語義鴻溝”的作用非同小可，遺傳算法的引入使得分割準確度更高、通用性更強。

[1] BABER J, AFZULPURKAR N, SATOH S. A framework for video segmentation using global and local features[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2013, 27(5):13550071-135500729.

[2] 劉嘉琦,封化民,閆建鵬.基于多模態(tài)特征融合的新聞故事單元分割[J].計算機工程,2012,38(24):161-165.

[3] 華漫.基于語義的體育視頻場景分割方法[J].計算機工程,2010,36(15):206-207.

[4] 郭小川,劉明杰,王婧璐,等.基于頻繁鏡頭集合的視頻場景分割方法[J].計算機應(yīng)用與軟件,2011,28(6):116-120.

[5] 楊亭,豐洪才,金凱,等.基于多模態(tài)融合和競爭力的視頻場景分割算法[J].武漢理工大學學報(信息與管理工程版),2014,36(6):759-763.

[6] 張鴻,吳飛,莊越挺,等.一種基于內(nèi)容相關(guān)性的跨媒體檢索方法[J].計算機學報,2008,31(5):820-826.

[7] YANG H, YI J, ZHAO J, et al. Extreme learning machine based genetic algorithm and its application in power system economic dispatch[J]. Neurocomputing, 2013,102(15):154-162.

[8] NGOC T A, HIRAMATSU K, HARADA M. Optimizing the rule curves of multi-use reservoir operation using a genetic algorithm with a penalty strategy[J]. Paddy and Water Environment, 2014,12(1):125-137.

[9] GUPTA N, SHEKHAR R, KALRA P K. Congestion management based roulette wheel simulation for optimal capacity selection:probabilistic transmission expansion planning[J]. International Journal of Electrical Power and Energy Systems, 2012,43(1):1259-1266.

[10] HWANG S F, HSU Y C, CHEN Y. A genetic algorithm for the optimization of fiber angles in composite laminates[J]. Journal of Mechanical Science and Technology, 2014,28(8):3163-3169.

[11] 田景文,孔垂超,高美娟.一種車輛路徑規(guī)劃的改進混合算法[J].計算機工程與應(yīng)用,2014,50(14):58-63.

[12] 印勇,王旭軍.基于主色跟蹤和質(zhì)心運動的視頻場景分割[J].計算機應(yīng)用研究,2010,27(4):1563-1565.

ZHAO Jiexue:Postgraduate; School of Mathematics and Computer Science, Wuhan Polytechnic University, Wuhan 430023, China.

[編輯：王志全]

GA-based Multimodal Video Scene Segmentation Algorithm

ZHAOJiexue,FENGHongcai,YANGLin

Video segmentation based on scene can not only shorten the time of search but also improve the accuracy of retrieval. It has become one of the hot researches in the video field. In order to cut apart video scenes rapidly and accurately, a multimodal segmentation algorithm under genetic algorithm was presented. In light of the idea of different features fusion, it extracted physical characteristics of different modes from video key frame, integrated the similarity of same modal data and correlation of different modal data among shots to get the similarity, and the shot similarity matrix was constructed. The genetic algorithm was used to complete segmenting video scenes. The experiments suggest that the proposed method can segment video scenes effectively; recall rate and precision can reach 86.9% and 87.7%; the F value is up to 87.3%.

scene segmentation; multimodal; genetic algorithm; similarity fusion; shot similarity matrix

2015-07-01.

趙杰雪(1993-)，女，安徽亳州人，武漢輕工大學數(shù)學與計算機學院碩士研究生.

湖北省自然科學基金資助項目(2009Chb008, 2010CDB06603)；湖北省教育廳重點科研計劃資金資助項目(D20101703).

2095-3852(2015)06-0841-05

A

TP391

10.3963/j.issn.2095-3852.2015.06.039