一種新的冗余關(guān)鍵幀去除算法

解曉萌，黎紹發(fā)

（華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006）

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

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

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

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

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

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

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

1.1 圖像的灰度直方圖

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

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

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

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

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

1.2 圖像的輪廓

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

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

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

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

式中，N是坐標(biāo)集C中坐標(biāo)的個(gè)數(shù)。

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

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

1.3 冗余幀去除算法

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

下面給出算法的偽代碼：

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

2 實(shí)驗(yàn)及討論

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

表1 實(shí)驗(yàn)用視頻信息

下面介紹兩個(gè)衡量標(biāo)準(zhǔn)，錯(cuò)正率FP和錯(cuò)負(fù)率FN。

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

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

表3 只用圖像顏色所得的實(shí)驗(yàn)結(jié)果

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

3 總結(jié)

關(guān)鍵幀提取在基于內(nèi)容的視頻檢索研究中是重要的一步，當(dāng)下的關(guān)鍵幀提取算法當(dāng)中都會(huì)存在冗余關(guān)鍵幀的問(wèn)題，冗余關(guān)鍵幀不但不能提供信息量，而且需要存儲(chǔ)空間和處理時(shí)間，本文提出了結(jié)合圖像像素顏色和圖像結(jié)構(gòu)的冗余幀去除算法，實(shí)驗(yàn)證明結(jié)合后的方法較單獨(dú)使用的方法性能有很大的提高，證明了本文提出的方法是有效的。但本文的算法也存在不足，對(duì)不同種類的視頻的效果存在差異，這也是接下來(lái)工作的內(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)容的視頻檢索技術(shù)[J].電視技術(shù)，2002，26（8）：17-19.

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

[4] 王新舸，羅志強(qiáng).代表幀及其提取方法[J].電視技術(shù)，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] 鐘玉琢，向哲，沈洪.流媒體和視頻服務(wù)器[M].北京：清華大學(xué)出版社，2003.

[8] 鐘玉琢，王琪，趙黎，等.MPEG-2運(yùn)動(dòng)圖像壓縮編碼國(guó)際標(biāo)準(zhǔn)及MPEG的新進(jìn)展[S].北京：清華大學(xué)出版社，2002.