趙杰雪，豐洪才，楊 琳

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

?

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

趙杰雪，豐洪才，楊 琳

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

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

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

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

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

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

1.1 圖像特征向量

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

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

(1)

1.2 音頻特征向量

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

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

(2)

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

1.3 文本特征向量

一個(gè)鏡頭的文本特征向量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)相似度計(jì)算

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

(4)

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

SimA(i,j)=

(5)

(3)利用余弦距離計(jì)算鏡頭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)度計(jì)算

利用張鴻等[6]提出的典型相關(guān)性分析法計(jì)算鏡頭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)進(jìn)行加性融合得到鏡頭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]進(jìn)行場(chǎng)景分割之前需先計(jì)算鏡頭相似度矩陣(shotsimilaritymatrix,SSM)。為了提高迭代效率，一段一段地進(jìn)行檢測(cè)，每一段為100個(gè)鏡頭。這樣SSM就是一個(gè)100×100的對(duì)稱矩陣，其值全部初始化為-1，然后根據(jù)式(12)計(jì)算出不同鏡頭之間的相似度，并將其保存在矩陣SSM中，如式(13)所示。

(13)

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

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

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

2.1 個(gè)體編碼方案

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

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

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

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

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

(14)

2.3 交叉

采用單點(diǎn)交叉的方法，種群中的個(gè)體隨機(jī)配對(duì)，配成對(duì)的兩個(gè)個(gè)體以交叉概率Pc相互交換基因，交叉位置M隨機(jī)產(chǎn)生。經(jīng)過多次試驗(yàn)，取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 變異

變異算子采用基本位變異，即隨機(jī)選取一個(gè)基因以變異概率Pm對(duì)其進(jìn)行取反操作，變異位置M是隨機(jī)產(chǎn)生的，將IM取反變異成1-IM。經(jīng)過多次試驗(yàn)，取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)用輪盤賭選擇法從當(dāng)前種群中選擇兩個(gè)個(gè)體直接復(fù)制到下一代種群，其余個(gè)體經(jīng)過交叉和變異操作之后產(chǎn)生相同數(shù)量的新個(gè)體，新個(gè)體與之前選出來的兩個(gè)個(gè)體一起構(gòu)成新的種群。

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

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

3 視頻場(chǎng)景分割

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

3.1 算法描述

利用遺傳算法進(jìn)行視頻場(chǎng)景分割的具體實(shí)施步驟如下：

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

輸出：場(chǎng)景邊界scene[L][2]。

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

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

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

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

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

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

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

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

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

3.2 過分割處理

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

(15)

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

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

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

表1 視頻片段詳細(xì)信息

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

(16)

(17)

(18)

式中：nc為檢測(cè)正確的場(chǎng)景個(gè)數(shù)；nm為檢測(cè)時(shí)漏掉的場(chǎng)景個(gè)數(shù)；nf為檢測(cè)錯(cuò)誤的場(chǎng)景個(gè)數(shù)。

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

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

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

5 結(jié)論

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

[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].計(jì)算機(jī)工程,2012,38(24):161-165.

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

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

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

[6] 張鴻,吳飛,莊越挺,等.一種基于內(nèi)容相關(guān)性的跨媒體檢索方法[J].計(jì)算機(jī)學(xué)報(bào),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ìn)混合算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(14):58-63.

[12] 印勇,王旭軍.基于主色跟蹤和質(zhì)心運(yùn)動(dòng)的視頻場(chǎng)景分割[J].計(jì)算機(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-)，女，安徽亳州人，武漢輕工大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院碩士研究生.

湖北省自然科學(xué)基金資助項(xiàng)目(2009Chb008, 2010CDB06603)；湖北省教育廳重點(diǎn)科研計(jì)劃資金資助項(xiàng)目(D20101703).

2095-3852(2015)06-0841-05

A

TP391

10.3963/j.issn.2095-3852.2015.06.039