王俊玲，盧新明

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

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

（1）基于抽樣的關(guān)鍵幀提取

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

（2）基于顏色特征的關(guān)鍵幀提取

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

（3）基于運動分析的關(guān)鍵幀提取

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

（4）基于鏡頭邊界的關(guān)鍵幀提取

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

（5）基于視頻內(nèi)容的關(guān)鍵幀提取

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

（6）基于聚類的關(guān)鍵幀提取

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

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

本文算法流程：

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

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

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

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

1 視頻關(guān)鍵幀初步提取

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

感知哈希算法通過將一幅圖像轉(zhuǎn)化成固定長度的字符串（指紋）[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的個數(shù)，則灰度級i出現(xiàn)的概率為：

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

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

圖2 計算圖像信息熵

1.3 視頻關(guān)鍵幀的初步提取

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

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

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

2 語義相關(guān)算法提取視頻關(guān)鍵幀

2.1 SIFT特征提取算法

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

SIFT算法實現(xiàn)流程圖如圖4所示。

SIFT特征提取算法的實現(xiàn)過程如下：

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

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

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

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

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

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

步驟2特征點定位。

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

步驟3關(guān)鍵點的方向確定。

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

圖4 SIFT算法實現(xiàn)流程圖

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

圖5 直方圖表示

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

步驟4關(guān)鍵點描述。

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

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

圖6 特征描述子

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

2.2 BOF算法

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

算法步驟：

（1）視頻單詞提?。菏紫扔肧IFT算法提取圖像庫中所有的圖像特征，生成圖像庫中每一幅圖的特征點及描述符。

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

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

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

（5）根據(jù)直方圖構(gòu)造特征到圖像的倒排表，通過倒排表快速索引相關(guān)圖像。

（6）根據(jù)索引結(jié)果進行直方圖匹配。

3 實驗與分析

本文在Intel i5，2.20 GHz CPU，4 GB內(nèi)存，Windows10（64位）環(huán)境下python平臺上實現(xiàn)該算法。

3.1 實驗1

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

表1 實驗信息表

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

圖7 人工提取關(guān)鍵幀

圖8 本文算法提取關(guān)鍵幀

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

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

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

圖9 準確率直方圖比較

圖10 誤差率直方圖比較

選譯v14進行實驗，采用本文算法與VSUMM算法分別提取關(guān)鍵幀，結(jié)果如圖11～圖13 所示?？梢缘贸霰疚乃惴ū萔SUMM 算法能更好地表達視頻內(nèi)容，且冗余較少。

圖11 VSUMM提取關(guān)鍵幀

圖12 本文算法提取關(guān)鍵幀

圖13 用戶提取關(guān)鍵幀

3.2 實驗2

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

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

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

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

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

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

表3 不同算法提取的關(guān)鍵幀漏檢率和錯誤率

式中，nm表示視頻關(guān)鍵幀提取算法創(chuàng)建的視頻關(guān)鍵幀與用戶提取關(guān)鍵幀相匹配的數(shù)量；na表示視頻關(guān)鍵幀提取算法創(chuàng)建的總幀數(shù)；nu表示用戶提取的關(guān)鍵幀總幀數(shù)。

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

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

4 結(jié)束語

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