一種新的冗余關鍵幀去除算法

解曉萌，黎紹發

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

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

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

圖1 基于內容的視頻檢索的流程

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

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

1 基于顏色和結構的冗余幀去除算法

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

1.1 圖像的灰度直方圖

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

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

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

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

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

1.2 圖像的輪廓

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

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

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

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

式中，N是坐標集C中坐標的個數。

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

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

1.3 冗余幀去除算法

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

下面給出算法的偽代碼：

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

2 實驗及討論

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

表1 實驗用視頻信息

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

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

表2 結合圖像顏色和圖像結構所得的實驗結果

表3 只用圖像顏色所得的實驗結果

表4 只用圖像結構所得的實驗結果

3 總結

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

[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] 張繼東，陳都.基于內容的視頻檢索技術[J].電視技術，2002，26（8）：17-19.

[3] 章毓晉.基于內容的視覺信息檢索[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.