解曉萌，黎紹發(fā)

（華南理工大學 計算機科學與工程學院，廣東 廣州 510006）

隨著互聯(lián)網(wǎng)技術的發(fā)展，尤其是近幾年視頻網(wǎng)站的興起，越來越多的人上網(wǎng)查找和觀看自己所喜歡的視頻。視頻的種類也越來越多，從新聞、娛樂到廣告和教育，網(wǎng)絡視頻所展示的信息已涉及到社會的方方面面。與此同時，網(wǎng)絡視頻的數(shù)量極其龐大，且每天都有源源不斷的新的視頻信息被發(fā)布到網(wǎng)絡中去，這就使得如何高效、快速查找出用戶所需要的視頻信息成為一個重要的研究課題，越來越多的工作者投入大量精力做視頻檢索方面的研究。

和基于關鍵字的視頻檢索方法不同，基于內(nèi)容的視頻檢索方法主要是通過分析源視頻的內(nèi)容信息來查找相關視頻，已被認為是將來視頻檢索研究的方向，具有很好的前景?；趦?nèi)容的視頻檢索流程圖如圖1所示。

圖1 基于內(nèi)容的視頻檢索的流程

本文研究的重點在于關鍵幀提取，下面就現(xiàn)有的主要的關鍵幀提取技術做一下簡單介紹。第1類是基于鏡頭的方法，這類方法的基本思想是選取鏡頭中的特定幀作為關鍵幀，最簡單的是選取第一幀作為關鍵幀[1]，這類方法中比較經(jīng)典的算法有幀平均法和直方圖平均法[2]。這類方法的優(yōu)點是思路比較簡單，易于編程實現(xiàn)，容易選取到視頻圖像中具有一般代表意義的幀；缺點是該種方法無法處理運動強度較高的鏡頭。第2類是基于內(nèi)容分析的方法，該類方法主要依賴于信息統(tǒng)計論的觀點，認為相關性較小的幀圖像比相類似的圖像攜帶更多的信息[3-4]。當選取關鍵幀時，應該選取最不相關的幾幀作為關鍵幀。該類方法的最主要的問題是計算量大，且所選取的幀不一定具有代表意義。第3類是基于運動分析的方法，該類方法以光流分析算法[5]和MPEG-7描述符算法[6]為代表。光流分析算法由Wolf等人提出，它通過光流分析技術來計算鏡頭中的運動量，并把運動量為局部極小值的幀作為關鍵幀。該幀反映視頻信息的靜止，通常對應視頻中的重要信息。MPEG-7描述符算法使用了兩個MPEG-7描述符，分別使用行為強度和行為空間分布來做關鍵幀的提取。該類方法的主要問題也是計算量大，時間效率低，所選取的關鍵幀也不一定準確。第4類是基于聚類的方法，主要研究如何找出鏡頭間的關系。該方法是將內(nèi)容上有關系的鏡頭結(jié)合起來，以描述視頻節(jié)目中有意義的事件或活動。有些學者也稱該方法為場景轉(zhuǎn)換、情節(jié)分割、鏡頭聚集等[3，7]。第5類是基于壓縮視頻流提取的方法。文獻[8]提出了通過檢測MPEG壓縮視頻流中已有的離散余弦變換（DCT）的DC系數(shù)和運動矢量（MV）來提取關鍵幀的方法。該方法與其他基于原始視頻流的關鍵幀提取算法不同，它直接在編碼后的視頻流上識別關鍵幀，從而節(jié)省不必要的解壓縮計算。

以上介紹了當前一些主流的關鍵幀提取方法，但這些算法都會面對一個同樣的問題，即冗余關鍵幀的存在，其原因是不同的鏡頭所提取出的關鍵幀相似。所以，在視頻關鍵幀提取系統(tǒng)中，對所提取出的關鍵幀做去冗余處理是非常有必要的。

1 基于顏色和結(jié)構(gòu)的冗余幀去除算法

本文所提出的方法通過圖像的灰度直方圖（顏色）和圖像的輪廓（結(jié)構(gòu)）來對兩張圖像做比較，找出冗余的關鍵幀。下面對圖像的灰度直方圖和圖像的輪廓作介紹。

1.1 圖像的灰度直方圖

在一幅灰度圖像中，像素的取值范圍從0～255，把像素的取值作為橫坐標，把一幅圖像中取某一像素值的像素的個數(shù)與總像素個數(shù)的比值作為縱坐標畫一幅圖，即為圖像的灰度直方圖（見圖2）。

式中：k代表像素點的取值；nk代表取k值的像素點的個數(shù)；N代表圖像中所有像素的個數(shù)。

通過求圖像的灰度直方圖，可以將一幅圖像轉(zhuǎn)換為一個256維的列向量I=[i0,i1,…，i255]T。下面介紹如何用圖像的灰度直方圖來比較兩幅圖像，假設兩幅圖像的灰度直方圖為P，Q，兩幅圖片的差別為D，則

式中，D表示兩幅圖像顏色上的差別。可以簡單的給D設一個閾值a來判斷兩幅圖像是否相似，如果兩幅圖像相似，它們的顏色差別會小于a,否則兩幅圖像的顏色差別會大于a。但這樣做會出現(xiàn)一個問題，如圖3所示。

圖3a、3b兩幅圖像是水平翻轉(zhuǎn)所得，它們本質(zhì)上是不同的圖像，但是它們卻有相同的灰度直方圖，兩幅圖像的灰度直方圖的差別為零。所以，單從應用圖像的底層顏色信息來比較圖像無法克服這一問題，下面將介紹用圖像的輪廓來比較圖像。

1.2 圖像的輪廓

圖像的輪廓即圖像的邊緣，本文中用Canny邊緣檢測來提取圖像的邊緣。Canny邊緣檢測器是高斯函數(shù)的一階導數(shù)，是對信噪比與定位之乘積的最優(yōu)化逼近算子[1]。Canny認為好的邊緣檢測應該具有3個特點：1）錯標非邊緣點和漏標真實邊緣點的概率比較低；2）檢測出的邊緣點盡量接近真實邊緣中心；3）具有單值邊緣響應。

圖4是某一幅圖像應用Canny邊緣提取法所提取出的輪廓圖。圖像的輪廓表示的是圖像的結(jié)構(gòu)信息，下面介紹如何用圖像的輪廓來比較兩幅圖像。

圖像的輪廓圖（圖4b）只包含兩種像素點，白色和黑色。把黑色看成背景，白色的像素看成背景上的點，每一個白像素點都有一個坐標（用該像素點所在的列數(shù)作為橫坐標，以其所在的行數(shù)作為縱坐標），可以得到一個坐標的集合

式中n為所有白像素點的個數(shù)。得到坐標集C后，用其來擬合一條直線（見圖5），所用的方法是最小二乘法，假設所要似合的直線為y=a+bx，則

式中，N是坐標集C中坐標的個數(shù)。

假設有兩幅圖像，通過提取輪廓和直線擬合后得到兩條直線y=a1+b1x和y=a2+b2x，則兩條線的夾角為

用兩幅圖像所擬合的直線的夾角來判斷兩幅圖像是否相似，如果小于某一閾值，則認為相似；否則，認為不相似。

1.3 冗余幀去除算法

首先定義幾個函數(shù)，hist_similar（a，b）是通過上方介紹的通過直方圖求得的圖像a和b的差異值，edge_similar（a，b）是求得a和b兩張圖像擬合直線的夾角，則判斷兩張圖像是否相同的函數(shù)similar（a，b）定義為

下面給出算法的偽代碼：

算法中拿關鍵幀集中的某一幀同該幀后的所有的幀用similar函數(shù)進行比較，如果相同，則刪除掉該重復幀。因為similar函數(shù)需要同時滿足兩個條件（灰度直方圖比較相同和擬合直線比較相同）才認為兩幅圖像相同，這樣會大大減少誤刪的發(fā)生。

2 實驗及討論

實驗機器是CPU為Intel CoreTM2 Duo 2.33 GHz、內(nèi)存為2 Gbyte的臺式機。實驗中所需的參數(shù)設定為α=0.3，β=5。實驗中所用的視頻是從優(yōu)酷視頻網(wǎng)下載所得，題材包括了娛樂、動畫、電影、運動和新聞。運用文獻[3]的方法來提取關鍵幀，結(jié)果列于表1中。

表1 實驗用視頻信息

下面介紹兩個衡量標準，錯正率FP和錯負率FN。

從表2～表4實驗結(jié)果可以看出，結(jié)合了圖像顏色和圖像結(jié)構(gòu)的冗余幀去除算法比單純的只使用圖像顏色或者是圖像結(jié)構(gòu)的算法在準確率上有了很大的提高，結(jié)果證明本論文提出的方法對冗余幀去除這一問題得到了很好地解決。

表2 結(jié)合圖像顏色和圖像結(jié)構(gòu)所得的實驗結(jié)果

表3 只用圖像顏色所得的實驗結(jié)果

表4 只用圖像結(jié)構(gòu)所得的實驗結(jié)果

3 總結(jié)

關鍵幀提取在基于內(nèi)容的視頻檢索研究中是重要的一步，當下的關鍵幀提取算法當中都會存在冗余關鍵幀的問題，冗余關鍵幀不但不能提供信息量，而且需要存儲空間和處理時間，本文提出了結(jié)合圖像像素顏色和圖像結(jié)構(gòu)的冗余幀去除算法，實驗證明結(jié)合后的方法較單獨使用的方法性能有很大的提高，證明了本文提出的方法是有效的。但本文的算法也存在不足，對不同種類的視頻的效果存在差異，這也是接下來工作的內(nèi)容。

[1]SHAHRARAY B，GIBBON D C.Automatic generation of pictorial transcripts of video programs[EB/OL].[2012-01-01].http://dx.doi.org/10.1117/12.206078.

[2] 張繼東，陳都.基于內(nèi)容的視頻檢索技術[J].電視技術，2002，26（8）：17-19.

[3] 章毓晉.基于內(nèi)容的視覺信息檢索[J].北京：科學出版社，2003.

[4] 王新舸，羅志強.代表幀及其提取方法[J].電視技術，2010，35（10）：26-28.

[5] WOLF W.Key Frame selection by motion analysis[C]//Proc.ICASSP 96.[S.L.]:IEEE Press，1996：1228-1231.

[6]NARASIMHA R,SAVAKIS A，RAO R M，et al.Key frame extraction using MPEG-7motion descriptors[EB/OL].[2012-01-10].http://www.ce.rit.edu/～savakis/papers/Asilomar03_Narasimha_Savakis_Rao_deQueiroz.pdf.

[7] 鐘玉琢，向哲，沈洪.流媒體和視頻服務器[M].北京：清華大學出版社，2003.

[8] 鐘玉琢，王琪，趙黎，等.MPEG-2運動圖像壓縮編碼國際標準及MPEG的新進展[S].北京：清華大學出版社，2002.