王紅霞，王 磊，晏杉杉

(沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110159)

隨著互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展，日益增長的視頻信息充斥在互聯(lián)網(wǎng)中，大量以視頻為主體的信息交流形式不斷涌現(xiàn)，如何從海量的視頻中進(jìn)行高效準(zhǔn)確的檢索成為當(dāng)下亟待解決的問題。關(guān)鍵幀提取作為視頻檢索極為關(guān)鍵的一步，是本文研究的重點(diǎn)。因此，如何從完整視頻中提取到能代表主要信息的幀是首先要解決的問題。

文獻(xiàn)[1]提出了基于鏡頭邊界的關(guān)鍵幀提取算法，假設(shè)鏡頭內(nèi)的變化較小，取鏡頭的首幀和尾幀作為關(guān)鍵幀，但存在由于鏡頭內(nèi)容變化較大僅僅采用首幀和尾幀不能充分表達(dá)視頻內(nèi)容而導(dǎo)致信息遺漏的問題；文獻(xiàn)[2]提出了基于內(nèi)容分析的關(guān)鍵幀提取方法，把顏色、形狀和紋理等視覺特征變化明顯的幀作為關(guān)鍵幀，但存在由于鏡頭中物體過快從而導(dǎo)致選取過多冗余幀的不足；文獻(xiàn)[3]提出了基于聚類的關(guān)鍵幀提取方法，確定聚類中心，將最接近聚類中心的幀作為關(guān)鍵幀，但往往存在算法復(fù)雜度過高而導(dǎo)致運(yùn)算時(shí)間較長且聚類中心和數(shù)目難以確定的不足。通過針對(duì)已有算法特性深入分析并取長補(bǔ)短，本文提出了基于自定義k值聚類和內(nèi)容分析的關(guān)鍵幀提取方法，該方法提取的關(guān)鍵幀不僅可最具代表性且關(guān)鍵幀數(shù)量能很好把握又不產(chǎn)生冗余。

1 基于自定義k值聚類和內(nèi)容分析的關(guān)鍵幀提取方法

1.1 概述

聚類方法是常見的一種關(guān)鍵幀提取方法，該方法主要是把鏡頭內(nèi)的幀按照相似度進(jìn)行分類，相似度越高，劃分到同一類的可能性越大，而不同類之間的相似度差異比較大，最后提取同類中的能代表這類主要內(nèi)容的一幀作為這類的關(guān)鍵幀，最終得到的k個(gè)關(guān)鍵幀則為這個(gè)鏡頭的關(guān)鍵幀。本文通過對(duì)聚類算法的深入研究，提出了基于自定義k值聚類和內(nèi)容分析的關(guān)鍵幀提取方法，對(duì)已有的聚類算法進(jìn)行了改進(jìn)，并融合了內(nèi)容分析方法，使得提取的關(guān)鍵幀相比于傳統(tǒng)方法無論在數(shù)目合理性還是內(nèi)容代表性上都有較大的提升。

選取一個(gè)自定義k值。假設(shè)經(jīng)過鏡頭分割之后的一個(gè)獨(dú)立鏡頭內(nèi)有n幀(可對(duì)每一幀編號(hào)，為1，2，……,n)，而本文選取的自定義k值的取值為n/4

算法流程圖如圖1所示。

圖1 提取關(guān)鍵幀流程圖

算法具體步驟如下。

(1)啟動(dòng)算法，為每個(gè)鏡頭的幀序列進(jìn)行編號(hào)，用fi(i=1，2，…，n)表示。確定k值大小，選取前k幀，將f1幀到fk幀的每一幀單獨(dú)作為一個(gè)類，且為各自所在類的中心，形成k個(gè)聚類。

(2)計(jì)算前k幀中兩兩幀之間的互信息量，把互信息量最大的兩幀聚類為一類，因此聚類數(shù)目減1，此時(shí)的聚類為k-1個(gè)。

(3)依次加入第m幀，m=k+1，k+2，……，n-1，n。如果m=k+1，k+2，……，n-1，執(zhí)行第4步；否則，執(zhí)行第5步。

(4)加入一幀，作為單獨(dú)的一個(gè)聚類，且為這個(gè)聚類的中心，與之前的k-1個(gè)聚類形成k個(gè)聚類。循環(huán)第2步和第3步。

(5)加入最后一幀，根據(jù)基于鏡頭邊界的關(guān)鍵幀提取算法，將最后一幀作為關(guān)鍵幀，且為單獨(dú)一類，得到k個(gè)聚類。

(6)對(duì)于得到的k個(gè)聚類，針對(duì)每一個(gè)聚類中的所有圖像幀，根據(jù)基于視頻內(nèi)容分析的關(guān)鍵幀提取算法，得到每一幀的統(tǒng)計(jì)直方圖后求平均值，把聚類中最接近平均值的一幀作為關(guān)鍵幀。

(7)算法結(jié)束，得到k個(gè)關(guān)鍵幀。

1.2 互信息量特征提取

互信息量作為圖像配準(zhǔn)的一個(gè)準(zhǔn)則，通常用來測量并統(tǒng)計(jì)兩個(gè)隨機(jī)變量相關(guān)性[5]。假設(shè)X是一個(gè)離散型的隨機(jī)變量，其n個(gè)取值分別為a1、a2、……、an。各個(gè)取值出現(xiàn)的概率分別為p1=p(a1)、p2=p(a2)、……、pn=p(an)，其中各個(gè)取值的概率和為1，如式(1)所示。

(1)

隨機(jī)變量X的取值是有限個(gè)或可列無限多個(gè)，一般情況下沒有固定的函數(shù)式可以表示，但存在一個(gè)概率分布的函數(shù)f(p1，p2，……，pn)，在滿足連續(xù)性、等概率時(shí)為單調(diào)函數(shù)和可加性三個(gè)條件時(shí)，函數(shù)形式是確定的，如式(2)所示。

(2)

通常把式(2)稱為熵，用Hs表示，其可對(duì)隨機(jī)變量的不確定程度進(jìn)行度量，用式(3)表示。

(3)

若設(shè)定圖像A和B，其互信息量MI可定義式(4)所示。

MI(A,B)=Hs(A)+Hs(B)-Hs(A,B)

(4)

式中：Hs(A)和Hs(B)分別為圖像A和B的熵；Hs(A，B)為二者的聯(lián)合熵。

隨機(jī)變量X和Y的平均互信息和聯(lián)合熵的關(guān)系可如式(5)所示。

I(X,Y)=Hs(X)+Hs(Y)-Hs(XY)

(5)

式中Hs(X)和Hs(Y)分別為X、Y的邊界熵。

平均互信息可通過其信息量和條件熵來定義，如式(6)所示。

I(X,Y)=Hs(X)+Hs(X|Y)

(6)

1.3 統(tǒng)計(jì)直方圖

直方圖是計(jì)算相鄰兩幀圖像中對(duì)應(yīng)像素位置變化的平均值[6]，并將相鄰幀間的差值定義為

(7)

式中：Ik(x,y)和Ik+1(x,y)分別表示第k幀和第k+1幀在(x,y)處的亮度值；M和N分別表示該幀的高度和亮度。

1.4 幀間相似度計(jì)算

圖像幀之間的相似度匹配是視頻檢索的關(guān)鍵性技術(shù)，相似度匹配的好壞直接影響最后的檢索結(jié)果。常用的幀間相似度計(jì)算方法有歐式距離、馬氏距離和二次式距離三種[7]。

歐式距離是空間中兩點(diǎn)之間的真實(shí)距離，如果該特征向量正交無關(guān)且各個(gè)分量之間權(quán)值相同，即可使用歐式距離計(jì)算幀間相似度。A和B兩個(gè)特征向量之間的歐式距離如式(8)所示。

(8)

式中：m表示特征向量的維度；n可以取1或2。在本文，計(jì)算幀間相似度時(shí)，采用的是這種方式。

馬氏距離適用于特征向量的各個(gè)分量之間權(quán)值不同或分量之間有相關(guān)性的情況，如式(9)所示。

D=(A-B)iC-1(A-B)

(9)

式中C表示協(xié)方差矩陣。

如果各個(gè)分量之間沒有相關(guān)性，如式(10)所示。

(10)

式中Ci表示各個(gè)分量的方差。

二次式距離則根據(jù)不同顏色間的相似程度計(jì)算相似度，如式(11)所示。

D=(Q-I)iA(Q-I)

(11)

式中：Q和I分別表示不同的顏色直方圖，A為顏色相似矩陣，A中的數(shù)據(jù)為對(duì)應(yīng)下標(biāo)顏色區(qū)間之間的相似度。

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

為更加形象的對(duì)比本文方法與其它不同方法提取關(guān)鍵幀的效果，選取一段AVI格式的且分辨率為544×960的較短視頻，分別使用基于鏡頭邊界的關(guān)鍵幀提取方法、基于內(nèi)容分析的關(guān)鍵幀提取方法、基于聚類的關(guān)鍵幀提取方法以及本文方法提取關(guān)鍵幀做對(duì)比。

基于鏡頭邊界的關(guān)鍵幀提取方法，這種方法最簡單，直接選取該鏡頭內(nèi)部的第一幀、最后一幀和中間的那一幀作為關(guān)鍵幀，如圖2所示。

圖2 基于視頻鏡頭邊界的關(guān)鍵幀

基于視頻視覺內(nèi)容分析的關(guān)鍵幀提取方法，先把第一幀選為關(guān)鍵幀，對(duì)于其后面的幀，都以這一幀為參考。在計(jì)算得到后面各幀的特征信息之后，都需要與第一個(gè)關(guān)鍵幀進(jìn)行做差比較。如果，計(jì)算到某一幀的時(shí)候，所得的差值大于事先設(shè)定好的閾值，則把這一幀加入關(guān)鍵幀序列。以此類推，直到視頻幀序列的最后一幀為止，如圖3所示。

圖3 基于視頻視覺內(nèi)容分析的關(guān)鍵幀

基于聚類的關(guān)鍵幀提取方法，首先，確定初始的聚類中心；然后，通過判斷每幀圖像與這個(gè)聚類中心的距離來確定是否歸為該類。將這個(gè)距離與預(yù)設(shè)閾值比較，可有兩種結(jié)果，一種是小于閾值，當(dāng)前幀歸為該類，另一種是大于閾值，當(dāng)前幀作為新的聚類中心。將鏡頭中的所有幀全部進(jìn)行分類后，分別計(jì)算每幀與其所在那類聚類中心的差值，選取差值最小的幀作為關(guān)鍵幀如圖4所示。

圖4 基于聚類的關(guān)鍵幀

利用本文方法提取的關(guān)鍵幀如圖5所示。

圖5 本文方法的關(guān)鍵幀

由以上結(jié)果可知，不同方法得出的關(guān)鍵幀及數(shù)目的確存在差異，但本文方法，在數(shù)量上適中，且每一幅關(guān)鍵幀圖像存在明顯差異，能較好的表示這段視頻的關(guān)鍵內(nèi)容。對(duì)于視頻中關(guān)鍵信息，即大熊貓動(dòng)作的變化展示的非常清晰，且不冗余，效果十分明顯。

通過以上實(shí)驗(yàn)，可以看出，文本方法可行，但依然需要進(jìn)一步驗(yàn)證其提取到的關(guān)鍵幀的準(zhǔn)確性。通常，使用準(zhǔn)確率和查全率兩個(gè)參數(shù)評(píng)價(jià)關(guān)鍵幀提取的效果[8]，如式(12)、式(13)所示。

(12)

(13)

選取一段稍長的視頻，使用以上方法提取關(guān)鍵幀，并與人工標(biāo)注的關(guān)鍵幀進(jìn)行對(duì)比。對(duì)于所選視頻，人工標(biāo)注的關(guān)鍵幀數(shù)為8，檢測結(jié)果如表1所示。

表1 不同方法提取關(guān)鍵幀檢測結(jié)果

從準(zhǔn)確率和查全率來看，本文方法取得了較高的準(zhǔn)確率和查全率，結(jié)果顯示本文方法相比其他方法，在提取關(guān)鍵幀方面更有效。

本文進(jìn)一步比較了四種方法的運(yùn)行效率，選取3段上述格式視頻進(jìn)行測試，三種方法各自的幀處理平均時(shí)間如表2所示。

表2 算法處理時(shí)間比較

由表2可知基于鏡頭邊界的方法耗時(shí)最少，原因在于該方法選取首幀和尾幀作為關(guān)鍵幀，只需要很小的計(jì)算量。但是該方法選取關(guān)鍵幀不夠靈活，極容易造成信息遺漏?；趦?nèi)容分析的方法根據(jù)視覺特征的變化選取關(guān)鍵幀，該方法選取的關(guān)鍵幀雖然相對(duì)基于鏡頭邊界的方法效果有所提高，但面對(duì)運(yùn)動(dòng)較快的視頻目標(biāo)容易產(chǎn)生大量冗余，大大降低了運(yùn)行效率?；诰垲惖年P(guān)鍵幀提取方法由于算法的復(fù)雜度較高，在處理時(shí)間上比基于內(nèi)容分析的方法還要高些。本文的基于自定義k值聚類和內(nèi)容分析的關(guān)鍵幀提取方法，在保證提取的關(guān)鍵幀代表性的前提下解決了基于內(nèi)容分析方法的冗余幀問題，在運(yùn)行效率上要高于基于內(nèi)容分析方法和基于聚類方法。雖然本文方法相比于基于鏡頭邊界方法耗時(shí)略高，但對(duì)原視頻內(nèi)容的表達(dá)更為準(zhǔn)確，且耗時(shí)在相同數(shù)量級(jí)，滿足工程要求。

3 結(jié)束語

本文提出的基于自定義k值聚類和內(nèi)容分析的關(guān)鍵幀提取方法，能很容易的提取出視頻中具有代表性的關(guān)鍵幀，這些關(guān)鍵幀不但內(nèi)容明確，而且數(shù)量上也不冗余，同時(shí)，彌補(bǔ)了其它方法對(duì)于內(nèi)容變化較多或物體運(yùn)動(dòng)較快所導(dǎo)致的數(shù)量冗余和無法展示主要信息的不足，對(duì)后續(xù)的關(guān)鍵幀提取方法研究有一定的借鑒作用。