基于語義相關的視頻關鍵幀提取算法

王俊玲，盧新明

山東科技大學 計算機科學與工程學院，山東 青島 266500

隨著多媒體信息的發展，視頻成為人們獲取信息的重要途徑，面對海量的視頻，如何從視頻中提取關鍵部分，提高人們看視頻的效率已經成為人們所關注的問題。視頻摘要技術正是解決這一問題的關鍵，在視頻摘要技術中的核心部分就是關鍵幀的提取。關鍵幀的提取可以分為以下六類：

（1）基于抽樣的關鍵幀提取

基于抽樣的方法是通過隨機抽取或在規定的時間間隔內隨機抽取視頻幀。這種方法實現起來最為簡單，但存在一定的弊端，在大多數情況下，用隨機抽取的方式得到的關鍵幀都不能準確地代表視頻的主要信息，有時還會抽到相似的關鍵幀，存在極大的冗余和信息缺失現象，導致視頻提取效果不佳[1]。

（2）基于顏色特征的關鍵幀提取

基于顏色特征的方法是將視頻的首幀作為關鍵幀，將后面的幀依次和前面的幀進行顏色特征比較，如果發生了較大的變化，則認為該幀為關鍵幀，以此得到后續的一系列關鍵幀。該方法針對相鄰幀進行比較，不相鄰幀之間無法進行比較，對于視頻整體關鍵幀的提取造成一定的冗余。

（3）基于運動分析的關鍵幀提取

比較普遍的運動分析算法是將視頻片段中的運動信息根據光流分析計算出來，并提取關鍵幀。如果視頻中某個動作出現停頓，即提取為關鍵幀，針對不同結構的鏡頭，可視情況決定提取關鍵幀的數量。但它的缺點也十分突出，由于需要計算運動量選擇局部極小點，這一過程十分復雜，會消耗大量時間，并且由此得到的關鍵幀不一定能夠準確描述視頻內容[2-3]。

（4）基于鏡頭邊界的關鍵幀提取

Nagasak 等人[4]提出了基于鏡頭邊界的關鍵幀提取[5]算法，主要是通過鏡頭內容的變化，利用算法將視頻以鏡頭為單位分割并提取關鍵幀。這種方法需要將輸入的視頻分段，分別提取第一幀、中間幀、最后一幀作為該片段的關鍵幀。由于每個鏡頭內的內容幾乎沒有變化，而不同鏡頭間存在差異，因此提取出的關鍵幀數量相對穩定。與抽樣方法相比，鏡頭分割算法考慮了內容信息，在鏡頭內容變動較小、動作不劇烈的視頻中十分適用。當鏡頭內容變化復雜，或者強烈運動時，由于不能夠完全表達鏡頭內的全部內容，有時會丟失視頻的重要部分。

（5）基于視頻內容的關鍵幀提取

基于視頻內容的關鍵幀提取算法[6-11]是目前使用最廣的方法，其基本思想是在每個內容中設定第一幀為對比關鍵幀，根據顏色、形狀、紋理等視覺特征將對比關鍵幀與下一視頻幀進行相似度比較，當相似度小于設定的閾值時，將該視頻幀加入關鍵幀集合，并將該幀作為對比關鍵幀，以此類推，直到檢測完該內容為止。該方法提取出來的關鍵幀較多地保留了原視頻的內容，與基于鏡頭邊界的方法進行比較，更加注重視頻內容的變化。缺點是閾值選取影響關鍵幀提取的質量，且該算法計算量大，對于內容復雜、變換頻繁的視頻，效果不佳。

（6）基于聚類的關鍵幀提取

基于聚類的關鍵幀提取算法[12-15]充分考慮了鏡頭內以及鏡頭間的相關性，將相似的視頻幀分為一簇，滿足簇內相似度大，簇間相似度小的原則，依次從每簇中選取一幀作為關鍵幀。該方法解決了不同鏡頭之間可能存在相似視頻幀的情況，減少了信息冗余。缺點是聚類數目和聚類中心需要提前設定，在對視頻內容不了解的情況下，提前設定聚類數目和中心是非常困難的，且運算時間較長。

由于傳統的關鍵幀提取算法單純地提取底層信息，存在大量信息缺失、冗余現象突出等問題，本文提出了一種基于語義的視頻關鍵幀提取算法，該算法可以減少信息的缺失和降低關鍵幀的冗余。

本文算法流程：

（1）把視頻分成n幀，聚成n個類。

（2）利用感知哈希算法對n個類進行相似性度量。將相似的幀合并成一類形成k類(k＜n)，同一類內的視頻幀是相似的，類與類之間的視頻幀是不相似的。

（3）從每個類中提取一幀作為關鍵幀，如果一個類中幀的數目太少，則這個類不具有代表性，可以直接與相鄰的幀合并，得到層次聚類的初始化結果。

（4）得到的關鍵幀可能會存在冗余現象，再使用語義相關算法對其進一步處理，得到最后的關鍵幀。

1 視頻關鍵幀初步提取

1.1 感知哈希算法判斷圖像相似度

感知哈希算法通過將一幅圖像轉化成固定長度的字符串（指紋）[16]，通過計算圖像間漢明距離(H)判斷其相似性。

本文利用均值哈希算法進行計算，步驟如下：

（1）將圖像尺寸縮小為8×8大小。

（2）將縮小后的圖像進行灰度化處理。

（3）計算圖像像素的平均值（將大于均值的記為1，小于均值的記為0）。

（4）生成哈希值，得到一個64位的0，1序列，即為哈希指紋。

生成哈希指紋后對比兩幅圖像的哈希指紋，計算它們之間的漢明距離(H)，相同位置的值相同，距離不變，不相同距離加1，通常情況下，如果漢明距離(H)小于10，則認為兩幅圖像是相似的，漢明距離大于10，則認為兩幅圖像不相似，由此：

通過圖1 可以看出，（a）和（b）相似，漢明距離為6，（a）和（c）不相似，漢明距離為26。由此可以看出哈希指紋越接近，相似度就越高。

圖1 哈希指紋提取

1.2 計算圖像信息熵

信息熵的概念由Shannon[17]提出來的，用來度量信息的不確定性。一幅圖像可以看成一個二維的離散信號，用信息熵可以衡量圖像中包含信息量的多少，也可稱之為圖像熵[18]。對于一幅灰度級為L(1＜L ＜256)，大小為M×N的灰度級圖像I，用f(x,y)表示圖像中坐標為(x,y)的像素灰度值，則f(x,y)的取值范圍是[0,L-1]。令fi為圖像中灰度級為i的個數，則灰度級i出現的概率為：

根據信息熵的定義，二維圖像的信息熵可定義為：

此時，一幅圖像中含有多少信息量就可以用圖像熵來衡量。如圖2所示，信息量越多，圖像熵越大，信息量越少，圖像熵越小。

圖2 計算圖像信息熵

1.3 視頻關鍵幀的初步提取

首先將視頻分成n幀，聚成n個類，然后通過計算漢明距離對n個類進行合并，得到k個類(k＜n)，最后計算每個類中圖像的信息熵，取熵值最大的圖像為該類視頻的關鍵幀。

由圖3可以看出，n/k=12 時，分類的準確率能達到最大值，本文取得k值為n/12。

圖3 k 值隨分類準確率的變化曲線

2 語義相關算法提取視頻關鍵幀

2.1 SIFT特征提取算法

尺度不變特征變換[19-21]（Scale Invariant Feature Transform，SIFT）是由加拿大教授Lowe 于1999 年提出的，用來描述影像中局部性特征，其優點是對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩定性，可以在海量特征數據庫中進行快速、準確的匹配。

SIFT算法實現流程圖如圖4所示。

SIFT特征提取算法的實現過程如下：

步驟1尺度空間極值點檢測。

將一個變化尺度的高斯函數G(x,y,σ) 與原圖像I(x,y)的卷積定義為一個圖像的尺度空間，并將其設為L(x,y,σ)。

其中，*表示卷積運算。高斯函數表示為：

公式中的m、n代表高斯模板的維度；函數坐標中，(x,y)代表圖像的像素位置；σ則表示尺度空間因子，值越小表示圖像被平滑得越少，相應的尺度也就越小。為了在尺度空間中有效地檢測到穩定關鍵點的位置，使用高斯差分算子（Difference of Gaussian，DOG）進行極值檢測。

在尺度空間中，需要檢測出穩定關鍵點的位置，極值檢測提供了有效的檢測方法。這里使用高斯差分算子進行極值檢測。

使用該公式得到的關鍵點是由DOG空間的局部極值點組成的。通過對同一組內各DOG相鄰兩層圖像之間進行比較，從而完成對于關鍵點的初步探查。其中每一個像素點，都要與它上下左右所有的相鄰點比較，觀察其圖像域與尺度域的相鄰點大小，才能找到該DOG函數的極值點。

步驟2特征點定位。

離散空間的極值點，可以通過上述的高斯差分算子方法進行檢測。如果需要精確確定關鍵點的位置和尺度，就需要用到擬合三維二次函數。由于DOG 算子會產生較強的邊緣響應，這種方法不但能夠去除不穩定的邊緣響應點，也去除了低對比度的關鍵點，從而增強了匹配穩定性，提高了抗噪聲能力。

步驟3關鍵點的方向確定。

為了保持描述符具有旋轉不變性，利用圖像的局部特征，給每一個關鍵點分配一個基準方向，使用圖像梯度求取局部結構的穩定方向。這種方法需要采集像素的梯度和方向分布特征，將DOG檢測中得到的關鍵點，在其所在的高斯圖像3σ鄰域窗口內將兩種數值采集出來。梯度的模值和方向如下：

圖4 SIFT算法實現流程圖

通過以上步驟，已經找出了關鍵點，以每一個關鍵點為圓心，1.5σ為半徑的圓內，對關鍵點進行梯度計算。完成相關計算后，使用基于梯度直方圖的統計方法，以直方圖的形式，統計鄰域內像素的梯度和方向。梯度直方圖將360°每10°分成一個柱（bins），共分為36個柱，每個柱都代表自己的方向和數值。如圖5 所示，直方圖中的峰值代表關鍵點的主方向（為簡化，圖中只畫了8個方向的直方圖）。

圖5 直方圖表示

在方向梯度直方圖中，峰值代表在該特征點處鄰域梯度的方向，直方圖中的最大值就作為該關鍵點的主方向。為了增強匹配的效果，只保留峰值大于主方向峰值80%的方向作為該關鍵點的輔方向。

步驟4關鍵點描述。

特征描述子的生成，是對關鍵點當前尺度周圍區域的梯度進行統計得出的。以關鍵點為圓心，將其鄰域旋轉θ，從而使得旋轉具有不變性。旋轉后得到的圖像，再次將關鍵點作為中心，并將其分割成16×16的均勻區域，組合形成共計16個4×4的子窗口，然后利用高斯模糊增加距離關鍵點較近區域的權重，同時減小距離關鍵點位置較遠的區域權重。

如圖6，在每個4×4的區域內，分別對0，45，90，135，180，225，270，315 這8 個方向的梯度進行累加，最后用4×4×8共計128維特征向量表示特征描述子。

圖6 特征描述子

經過以上一系列操作后，將去除了尺度、旋轉變化影響的SIFT特征描述子，再進行進一步的歸一化處理，以減少光照的影響。最后按特征點的尺度對特征描述向量進行排序，生成SIFT特征描述向量。

2.2 BOF算法

BOF（Bag of Feature）是用于圖像和視頻檢索的算法，源自于BOW（Bag of Words）算法。BOW是文本分類中的一種，通過抓取一段文本的關鍵詞，根據關鍵詞出現的頻率確定這段文本的中心思想。BOF 算法正是運用這種思想，不同的是BOF 抽取的關鍵詞是圖像的關鍵特征。

算法步驟：

（1）視頻單詞提取：首先用SIFT算法提取圖像庫中所有的圖像特征，生成圖像庫中每一幅圖的特征點及描述符。

（2）視覺詞典的構建：用k-means 算法對圖像庫中的特征點進行聚類，得到視覺詞典。

（3）針對輸入特征集，根據視覺詞典進行量化。

（4）圖像表示：統計每張圖像在每個聚類中的特征的個數，每張圖片可以由一個分布直方圖表示，每個圖像都可以由基本詞匯表示。

（5）根據直方圖構造特征到圖像的倒排表，通過倒排表快速索引相關圖像。

（6）根據索引結果進行直方圖匹配。

3 實驗與分析

本文在Intel i5，2.20 GHz CPU，4 GB內存，Windows10（64位）環境下python平臺上實現該算法。

3.1 實驗1

本文選取VSUMM[22]提供的YouTube數據集進行實驗。YouTube數據集中共包括50個不同的視頻，所有視頻采用FLV和AVI多媒體標準格式，顯示分辨率為352×240，視頻的時長在1～10 min 不等，視頻主要有廣告視頻、商業視頻、新聞節目、電視節目、卡通視頻。該數據集還提供了50 名用戶手動提取的關鍵幀，方便了研究者做對比實驗。本文從該數據集的每一類中隨機抽取視頻進行實驗，實驗視頻信息如表1 所示。圖7 和圖8是在YouTube數據集選取視頻v71進行人工摘要與本文算法摘要進行對比實驗的結果。

表1 實驗信息表

從圖7 和圖8 的實驗結果中可以得知，本文算法提取的關鍵幀數量比人工提取的關鍵幀數量少，且冗余少，涵蓋的視頻內容豐富，能較好地表現視頻的完整信息。本文采用準確率（Accuracy Rate，AR）與誤差率（Error Rate，ER）對算法進行評價，其計算公式為：

圖7 人工提取關鍵幀

圖8 本文算法提取關鍵幀

其中，nu為用戶提供的視頻關鍵幀數量，nm為視頻關鍵幀提取算法生成的視頻關鍵幀與用戶提供的視頻關鍵幀相匹配的幀數，nmˉ為視頻關鍵幀提取算法生成的視頻關鍵幀與用戶提供的視頻關鍵幀不相匹配的幀數。表2 為本文算法與VSUMM 算法準確率和誤差率的比較。

表2 本文算法與VSUMM算法準確率與誤差率

通過繪制直方圖更直觀地對比兩種算法的準確率和誤差率，圖9和圖10分別為準確率比較和誤差率比較。通過比較可以看出，本文算法比VSUMM算法略好。

圖9 準確率直方圖比較

圖10 誤差率直方圖比較

選譯v14進行實驗，采用本文算法與VSUMM算法分別提取關鍵幀，結果如圖11～圖13 所示。可以得出本文算法比VSUMM 算法能更好地表達視頻內容，且冗余較少。

圖11 VSUMM提取關鍵幀

圖12 本文算法提取關鍵幀

圖13 用戶提取關鍵幀

3.2 實驗2

采用OVP數據集[23]進行實驗。該數據集有50個視頻，包含多種類型的視頻，視頻時長1～4 min 不等，采用統一多媒體標準格式MPEG-1，視頻分辨率為352×240像素，以每秒29 幀的速度播放，每個視頻都有來自5 個不同用戶的人工視頻關鍵幀提取。為了進一步評價本文提出的算法，以數據集人工提取關鍵幀作為結果對比評價的基礎，采用兩種評價指標對實驗結果進行分析：

（1）用漏檢率和錯誤率進行對比分析；

（2）用精度（Precision Rate，PR）、召回率（Recall Rate，RR）、F-Measure（F）進行對比分析。

漏檢率指未檢測出的關鍵幀所占的比率，漏檢率越低，說明檢測出的關鍵幀越能代表視頻的完整性；錯誤率指檢測出的關鍵幀中提取錯誤的關鍵幀所占的比率，錯誤率越低，說明該算法準確率越高。將本文算法與DT[24]、STIMO[25]進行比較。公式如下：

其中，RM表示漏檢率，RF表示錯誤率，Nm表示未檢測出的關鍵幀數目，Nc表示檢測出的關鍵幀與人工檢測出的關鍵幀正確匹配的數目，Nj表示檢測出錯誤的關鍵幀數目。由表3可以看出，本文算法的漏檢率有所降低，錯誤率高于 STIMO 算法，但比 DT 和 VSUMM 算法有所提高。

精度（PR）是指提取的視頻關鍵幀中選中正確關鍵幀的能力（正確關鍵幀是指用戶摘要中所具有的關鍵幀）。召回率（RR）是指生成的視頻關鍵幀中符合用戶要求的性能。F-Measure（F）是精度與召回率的均衡指標，是對視頻關鍵幀質量的總體評估。計算公式如下：

表3 不同算法提取的關鍵幀漏檢率和錯誤率

式中，nm表示視頻關鍵幀提取算法創建的視頻關鍵幀與用戶提取關鍵幀相匹配的數量；na表示視頻關鍵幀提取算法創建的總幀數；nu表示用戶提取的關鍵幀總幀數。

通過表4對比結果可以看出，本文算法的精度高于其他算法，而且視頻關鍵幀的質量也比較好。

表4 計算不同算法精度、召回率、F-Measure

4 結束語

本文提出了一種基于語義相關的視頻關鍵幀提取算法。該算法首先使用層次聚類算法對視頻關鍵幀進行初步提取，然后結合語義相關算法對初步提取的關鍵幀進行直方圖對比，去掉冗余幀，確定視頻的關鍵幀。計算各種評價指標來衡量本文算法，通過與其他算法進行比較可以看出本文算法性能略好一點，但是仍然存在誤檢和漏檢的問題。由此需要進一步分析，改革特征的提取方法，降低漏檢率和誤檢率。