一種快速動畫鏡頭檢測算法

曾華+鄭勝前++何文廣

摘要：互信息量特征包含顏色和空間信息很好地反映視頻幀間相似度。互信息量計算量大，用于視頻鏡頭檢測時間復(fù)雜度大。針對動畫視頻大量存在背景固定鏡頭的情況，提出先運用背景特征進(jìn)行鏡頭篩選，再利用互信息量進(jìn)行最終確認(rèn)的兩階段的鏡頭檢測方法。實驗結(jié)果表明，算法在基本保持與互信息量特征提取結(jié)果相同的情況下，可有效降低視頻鏡頭檢測時間復(fù)雜度。

關(guān)鍵詞：基于內(nèi)容；動畫視頻；鏡頭檢測；互信息量；聯(lián)合直方圖

中圖分類號：TP37 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）14-0174-03

A Fast Animation Video Shot Detection Algorithm

ZENG Hua， ZHENG Sheng-qian，HE Wen-guang

（School of Information Engineering， Guangdong Medical College， Dongguan 523808，China）

Abstract： The color and spatial information of mutual information can reflect the similarity between video frames. The feature of mutual information can be used in video shot detection， but there is a large amount of computation. There is a large amount of background fixed scenes in the animation video， the paper proposes to use the background feature to screen the shot， and then use the mutual information to confirm the shot detection method. Experimental results show that the algorithm can effectively reduce the time complexity of video shot detection in the same condition， which is the same as mutual information feature extraction algorithm.

Key words： content-based； animation video； shot detection； mutual information； co-histogram

隨著數(shù)字多媒體技術(shù)與計算機網(wǎng)絡(luò)技術(shù)快速發(fā)展，移動設(shè)備的不斷更新，大量的視頻信息已廣泛地應(yīng)用于各個領(lǐng)域，數(shù)字多媒體與網(wǎng)絡(luò)技術(shù)快速發(fā)展，互聯(lián)網(wǎng)線上線下的數(shù)字視頻資源不斷地增長，人們所接觸的視頻也越來越多，面對周圍海量的視頻信息，如何快速有效地對視頻資源進(jìn)行準(zhǔn)確描述，方便用戶高效地進(jìn)行視頻檢索與瀏覽，成為了迫切的需求，基于內(nèi)容的視頻檢索技術(shù)因此正是基于這種需求而出現(xiàn)的。

動畫視頻可根據(jù)其特點分成不同的類型，比如一些全部由現(xiàn)代CG技術(shù)制作出來的新的動畫類電影；還有一些主要在于強調(diào)其寓意，而制作手法簡單所以其畫面也非常簡單；還有一些是非常受歡迎的以美國迪斯尼為主的動畫片。其中迪斯尼這一類動畫片受歡迎，而且制作出來的動畫視頻有著其鮮明的特點：題材吸引人，而且制作手法比較大膽夸張，其中以《貓和老鼠》和《米老鼠與唐老鴨》等等為代表。動畫視頻中往往因含有大量的目標(biāo)物體快速運動且不規(guī)則、表情大膽夸張，其中第三類的動畫視頻尤其明顯，而現(xiàn)有的主要的視頻分析處理方法主要都是針對普通的電影電視、體育、新聞等視頻的，而正如前面所說，動畫視頻從其創(chuàng)作到制作整個過程都有著它自身鮮明的特點，而且正因為這些獨特的特點，使得現(xiàn)有的視頻鏡頭邊界檢測算法對動畫視頻往往不能取得良好效果。

圖片互信息量包含了圖片間的顏色和空間特征信息，能較好地反映圖片間差別，在基于內(nèi)容的視頻檢索中作為視頻的幀間特征能較好地反映視頻內(nèi)容的變化，但其計算復(fù)雜度高。動畫存在大量背景相似的鏡頭，鏡頭邊界只占極小部分，通過背景可以篩選大量非鏡頭邊界的視頻幀。文章根據(jù)動畫視頻背景相對固定的特高提出一種快速有效的互信息量鏡頭切變檢測方法。

1 現(xiàn)有基于內(nèi)容鏡頭檢測技術(shù)

自上世紀(jì)九十年代基于內(nèi)容的視頻檢索研究興起以來，國內(nèi)外學(xué)者提出了很多視頻鏡頭檢測的算法，其中包括了很多傳統(tǒng)的經(jīng)典算法。（1）模版匹配法，是一種最直接的基于兩幅視頻幀的灰度圖對應(yīng)點像素值差的絕對值的方法。（2）基于直方圖的方法，這是一種較為簡單的基于統(tǒng)計的方法，方法利用圖像的整體特征，因此受鏡頭和目標(biāo)運動的影響較小。直方圖法通常還可以將視頻幀的各個像素的灰度、亮度或顏色均勻分成K等級，再對每個等級統(tǒng)計像素數(shù)目構(gòu)成直方圖進(jìn)行比較。（3）基于分塊匹配法，與前面提到的相鄰圖像上逐點像素比較法不同，基于塊匹配的方法先將每一幀圖像劃分成K塊，連續(xù)幀之間的相似性通過比較對應(yīng)的塊來進(jìn)行估計。這種方法主要利用局部特征來抑制圖像噪聲和攝像機及物體運動干擾。對于像素值較為相似，而場景不同的鏡頭邊界，可能會出現(xiàn)漏判的情況。若塊匹配法可以較好地與其他方法相結(jié)合，往往可以達(dá)到較高的檢測率。（4）基于圖像邊緣信息方法，Ramin Zabih與Justin Mille等人提出了一種基于圖像邊緣信息的鏡頭檢測方法。

此外不少學(xué)者研究運用視頻基本運動信息進(jìn)行鏡頭檢測，同時也有相關(guān)壓縮域的鏡頭檢測方法研究。

2 非均勻分塊方法

視頻鏡頭檢測與關(guān)鍵幀提取技術(shù)主要包括兩個方面，基于文字描述和基于內(nèi)容兩大類。其中基于內(nèi)容的視頻檢測技術(shù)是針對視頻內(nèi)容進(jìn)行的檢測，可以避免因文字描述不當(dāng)所導(dǎo)致的檢索錯誤。而由于每個視頻為了達(dá)到流暢視頻效果，往往要求每秒至少包含25個視頻幀，所以包含大量的相似視頻幀，這導(dǎo)致基于內(nèi)容的鏡頭檢測和關(guān)鍵幀提取存在處理時間長的突出問題。文章提出了一種非均勻分塊法將視頻幀進(jìn)行非均勻分塊，用簡單可行的方法先將目標(biāo)與背景進(jìn)行分離，再利用視頻背景與內(nèi)容相結(jié)合的兩階段鏡頭檢測算法進(jìn)行鏡頭檢測。

動畫視頻在制作上與傳統(tǒng)的視頻有很大的不同，導(dǎo)致動畫視頻有著自身明顯的特點。例如，動畫視頻中的目標(biāo)對象的運動速率比傳統(tǒng)視頻要快，同時動畫視頻為了突出視覺效果，視頻往往更加注重目標(biāo)動作、表情的夸張表現(xiàn)方法。

動畫視頻往往是先設(shè)計出動畫人物的動作，而傳統(tǒng)的視頻多數(shù)是錄制編輯而成，研究發(fā)現(xiàn)：相當(dāng)數(shù)量的動畫視頻鏡頭的背景是相對固定的，很多鏡頭目標(biāo)復(fù)雜動作，但背景卻是相對有較高的相似性，甚至存在大量鏡頭背景為一個固定的靜態(tài)圖像。實驗對目前主流的國內(nèi)外動畫視頻進(jìn)行鏡頭類型統(tǒng)計，實驗通過統(tǒng)計發(fā)現(xiàn)：動畫視頻有超過50%的鏡頭是以靜態(tài)圖片為背景，說明背景相對固定是動畫視頻的重要特征。根據(jù)動畫視頻這一特點文章提出一種簡單有效的動畫人物與背景分離方法，即將視頻幀進(jìn)行非均勻圖像分塊，將圖像幀分成目標(biāo)區(qū)域與背景區(qū)域。圖像的非均勻分塊方法如圖1所示：

從上面的示意圖可以看出：文章給出的圖像分塊法可以有效將視頻幀人物對象和背景進(jìn)行分離，且方法簡單易實現(xiàn)。

3 第一階段候選鏡頭邊界檢測

第一階段：候選鏡頭邊界檢測。第一階段針對動畫視頻大量存在靜態(tài)背景的特點，提出先對視頻幀進(jìn)行圖像分塊，然后通過計算背景區(qū)域的聯(lián)合直方圖特征距離，對同一場景內(nèi)大量高度相似的非鏡頭邊界視頻幀進(jìn)行篩選。

3.1 聯(lián)合直方圖特征距離

像素值p在大小為M*N的圖像f（x，y）中出現(xiàn)的概率定義為：

[Hf（p）=1MNy=1Mx=1Nδ（f（x，y），p）] （1）

式（1）中，[δ（f，p）]是克羅內(nèi)克函數(shù)：

[δ（f，p）=10if（f=p）if（f≠p）] （2）

如此可見，對于給定的大小為M*N的兩幅圖像f（x，y）、g（x，y），它們之間對應(yīng)的像素值對（p，q）聯(lián)合概率的定義為：

[H（p，q）=1MNy=1Mx=1Nδ（f（x，y），p）?δ（g（x，y），q）] （3）

由式（3）可知，對可能的像素值對（p，q）求其聯(lián)合概率[H（p，q）]的值，即可以計算出兩幅圖像f（x，y）和g（x，y）之間的聯(lián)合直方圖。而圖像間的聯(lián)合直方圖對稱性可以很好的描述兩幅圖像的相似性：對于相同的兩幅圖片，它們之間的聯(lián)合直方圖關(guān)于對角線嚴(yán)格對稱，即對角線上才有取值；而如果兩幅圖像非常相似，聯(lián)合直方圖相應(yīng)展現(xiàn)出非常高的對稱性；只有當(dāng)兩幅圖像存在很大的差別時，計算所得的聯(lián)合直方圖取值區(qū)域會變得很大，而且關(guān)于對角線對稱性差。綜上，求兩幅圖像的聯(lián)合直方圖，通過聯(lián)合直方圖對稱性即可判定圖像的相似程度。下面是聯(lián)合直方圖對稱性定義：

[symmetry=αpH2（p，p）+p，qβH（p，q）H（q，p）αpH2（p，p）+p，qβH2（p，q）] （4）

其中[α]是對角線上的權(quán)值，為小于1的常量；[β=（p-q）n]是遠(yuǎn)離對角線元素的權(quán)重， n是整數(shù)。在實驗中為了可以突出圖像間聯(lián)合直方圖差異，上式中 [α]應(yīng)賦較小值，而β賦較大值。實驗給[α]取值1/8，n取值2。

3.2 第一階段鏡頭檢測方法

第一階段的候選鏡頭檢測主要通過計算圖像分塊后的背景區(qū)域來獲取，幀間特征選取聯(lián)合直方圖。第一階段候選鏡頭檢測的算法主要步驟描述：

Step1：計算幀間背景區(qū)域聯(lián)合直方圖特征距離，得到視頻聯(lián)合直方圖幀間差特征向量[D=（d1，d2，…，dN）]，設(shè)置N=5，作為用于鏡頭漸變檢測容忍度；

Step2：對于當(dāng)前視頻幀i的幀間特征距離[di]，若[di]>[Thigh]，說明視頻幀i可能是候選的鏡頭切變，轉(zhuǎn)step3；若[Tlow]<[di]<[Thigh]，說明視頻幀i可能是候選漸變，轉(zhuǎn)step5；

Step3：閃光干擾檢測：計算[Diffi-1，i+1]，若[Diffi-1，i+1]<[Thigh]，判定為誤檢；否則計算[Diffi-1，i+3]，如果[Diffi-1，i+3]<[Thigh]，判定為誤檢，否則轉(zhuǎn)step4進(jìn)行切變判定；

Step4：切變檢測：以要檢測的幀為中心設(shè)定長度為21雙側(cè)滑動窗口[W]，若同時候滿足以下兩個條件：[di=max（W）]，[di>5*avg]，其中[avg]是[W]窗口中除當(dāng)前幀間特征距離外的特征距離平均值，判定為候選切變。i=i+1，轉(zhuǎn)step2；

Step5：漸變檢測：標(biāo)記當(dāng)前幀為可能的漸變開始幀，j=i+1，繼續(xù)向后進(jìn)行檢測，若同時滿足[dj] >[Tlow]和[Diffi，j>Diffi，j-1]，則N=N-1； j=j+1，直到N=0或者[Diffi，jThigh]，判定為鏡頭漸變，鏡頭漸變開始幀是i幀，漸變結(jié)束幀是j幀，令i=j，轉(zhuǎn)step2；否則判定視頻幀i不是鏡頭漸變，i=i+1轉(zhuǎn)step2；

Step6：算法結(jié)束，得到第一階段的候選切變和漸變集合。

4 第二階段鏡頭檢測

在1995年Viola和Collignon分別獨立提出了利用互信息量作為圖像之間的相似性測試，隨后圖像的互信息量相似性測試在應(yīng)用上取得巨大的成功。對于兩幅圖像A和B，它們之間的互信息量的定義為：

（8）

其中PA，PB，PAB分別為A， B的概率分布和聯(lián)合概率分布。從式（5）互信息量定義可知：I（A， B）值越大說明A，B越相似；I（A， B）的值越小說明A，B越不相關(guān)。

在兩階段的鏡頭檢測方法中，第二階段對第一階段選取的鏡頭進(jìn)行二次確認(rèn)，選取互信息量描述幀間相似性，對第一階段的切變邊界進(jìn)行窗口為21幀重新互信息量特征，參照3.2中step4進(jìn)行切變判斷；對漸變邊界，參照3.2中step5進(jìn)行漸變判斷。

通過對候選鏡頭重新確認(rèn)，得到視頻最終的鏡頭邊界集合。

5 實驗結(jié)果分析

針對本文提出的鏡頭分割方法，我們分別選取了幾段動畫視頻片斷進(jìn)行測試，為了使檢測結(jié)果更加有普遍性，實驗選取了國外動畫及國產(chǎn)動畫做實驗，其中國外動畫中人物動作幅度大，一般的特征描述方法所得的鏡頭分割效果誤檢率比較高；而片斷三和片斷四是兩個國內(nèi)動畫，其視頻內(nèi)容相對簡單，人物動作小，誤檢率較低，一般算法均可達(dá)到較高的查準(zhǔn)率。實驗中主要和基于像素的鏡頭檢測算法和互信息量的檢測算法比較。其中算法1為基于像素的檢測算法，算法2為互信息量的檢測算法。

實驗數(shù)據(jù)表明，對于實驗選取的視頻片斷，三種算法的查全率相同，互信息量算法和文章提出的算法較基于像素的方法查準(zhǔn)率高；運行時間，基于像素檢測算法較快，沒有加入比較，本文算法是互信息量檢測算法的31.25%，在查全率與查準(zhǔn)率保持不變的基礎(chǔ)上有效地降低了時間復(fù)雜度。

6 結(jié)束語

針對互信息量計算量大的問題和動畫視頻大量存在鏡頭固定的特點，文章提出先對視頻幀進(jìn)行簡單可行的圖像非均勻分塊，將目標(biāo)與背景分離，先選取計算復(fù)雜度相對較低的聯(lián)合直方圖對背景區(qū)域進(jìn)行候選鏡頭檢測，再利用互信息量特征進(jìn)行最終鏡頭邊界確認(rèn)。實驗結(jié)果表明，文章算法較為有效地降低了時間復(fù)雜度。

參考文獻(xiàn)：

[1] 曾華， 王耀民， 何文廣. 動畫視頻鏡頭檢測方法[J]. 電腦知識與技術(shù)， 2012（17）.

[2] Pengwei Hao， Ying Chen. Co-Histogram and Its Application in Video Analysis. In Proceedings of IEEE International Conference on Multimedia and Expo（ICME），Taiwan， 2004，195-203

[3] Mai K，Miller J，Zabih R.A robust method for detectingcuts and dissolves in video sequences. Proceedings of ACM Multimedia . 1995

[4] 陶志勇.一種基于顏色直方圖的圖像檢索方法[J].科學(xué)技術(shù)與工程，2007（24）.

[5] 岡薩雷斯. 數(shù)字圖像處理[M].北京：電子工業(yè)出版社，2005.

[6] 孔娟，田麗. 基于互信息量的視頻關(guān)鍵幀提取算法[J].安陽工學(xué)院學(xué)報，2010（4）.

[7] 方勇，戚飛虎，冉鑫. 基于窗幀差的鏡頭邊界系數(shù)模型及其應(yīng)用[J]. 電子學(xué)報， 2005，34（5）：810-816.