視頻檢索中的關鍵幀提取方法研究

王紅霞，王 磊，晏杉杉

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

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

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

1 基于自定義k值聚類和內容分析的關鍵幀提取方法

1.1 概述

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

選取一個自定義k值。假設經過鏡頭分割之后的一個獨立鏡頭內有n幀(可對每一幀編號，為1，2，……,n)，而本文選取的自定義k值的取值為n/4

算法流程圖如圖1所示。

圖1 提取關鍵幀流程圖

算法具體步驟如下。

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

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

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

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

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

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

(7)算法結束，得到k個關鍵幀。

1.2 互信息量特征提取

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

(1)

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

(2)

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

(3)

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

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

(4)

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

隨機變量X和Y的平均互信息和聯合熵的關系可如式(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 統計直方圖

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

(7)

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

1.4 幀間相似度計算

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

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

(8)

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

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

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

(9)

式中C表示協方差矩陣。

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

(10)

式中Ci表示各個分量的方差。

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

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

(11)

式中：Q和I分別表示不同的顏色直方圖，A為顏色相似矩陣，A中的數據為對應下標顏色區間之間的相似度。

2 實驗結果與分析

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

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

圖2 基于視頻鏡頭邊界的關鍵幀

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

圖3 基于視頻視覺內容分析的關鍵幀

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

圖4 基于聚類的關鍵幀

利用本文方法提取的關鍵幀如圖5所示。

圖5 本文方法的關鍵幀

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

通過以上實驗，可以看出，文本方法可行，但依然需要進一步驗證其提取到的關鍵幀的準確性。通常，使用準確率和查全率兩個參數評價關鍵幀提取的效果[8]，如式(12)、式(13)所示。

(12)

(13)

選取一段稍長的視頻，使用以上方法提取關鍵幀，并與人工標注的關鍵幀進行對比。對于所選視頻，人工標注的關鍵幀數為8，檢測結果如表1所示。

表1 不同方法提取關鍵幀檢測結果

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

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

表2 算法處理時間比較

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

3 結束語

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