曾華+王耀民

摘要：圖片的互信息量特征包含顏色和空間信息，能很好地反映視頻的幀間相似度，但互信息量計算量大，用于視頻關鍵幀提取時間復雜度大。針對動畫視頻大量存在背景固定鏡頭，提出一種改進的互信息量關鍵幀提取算法。實驗結果表明，算法在基本保持與互信息量特征提取結果相同的情況下，能有效降低關鍵幀提取的時間復雜度。

關鍵詞：基于內容；動畫視頻；關鍵幀提??；互信息量； 時間復雜度

中圖分類號：TP37 文獻標識碼：A 文章編號：1009-3044（2016）13-0220-03

Abstract： The mutual information feature contains the image color and spatial information， can well reflect the similarity between video frames， but mutual information calculation for content-based video key frame extraction is computation-intensive and time-consuming.. According to a fixed background animation video camera， this paper proposes an improved mutual information algorithm to extract key frames. The experimental results show that the algorithm can effectively reduce the time complexity of key frame extraction in the same condition， which is the same as the feature extraction of mutual information.

Key words： content-based； animation video； key frame extraction； mutual information； Time complexity

3 階段關鍵幀提取

基于內容的視頻檢測技術中，視頻包含大量的視頻幀，以一個90分鐘電影為例，假設每秒包含25幀，則視頻總共由135000幀組成，所以處理時間長是一個比較突出的問題。文章提出一種先利用非均勻分塊法將視頻幀進行非均勻分塊，將目標與背景進行分離，再利用視頻背景與內容相結合的兩階段關鍵幀提取方法動畫視頻關鍵幀。

3.1 圖像非均勻分塊

傳統(tǒng)視頻關鍵幀提取，可以考慮對視頻人物對象提取后根據(jù)視頻人物內容進行關鍵幀提取。動畫視頻在制作上與傳統(tǒng)的視頻有很大的不同，導致動畫視頻有著自身明顯的特點。例如，在動畫視頻中，目標物體的運動速率比一般的視頻要快，而且為了突出效果，視頻一般比較注重動作、表情的夸張表現(xiàn)。這些夸張的手法使得目標提取算法效果較差，可行性不高。

傳統(tǒng)的視頻多數(shù)是錄制編輯而成的，而動畫視頻往往是先設計出動畫人物的動作，在研究過程中發(fā)現(xiàn)相當數(shù)量的動畫視頻鏡頭的背景是相對固定的很多包含復雜動作的鏡頭其背景相對來說保持很高的相似性，甚至是一個固定的靜態(tài)圖像背景。實驗對目前主流的迪士尼動畫、日本動畫、國產動畫三類動畫視頻進行鏡頭類型統(tǒng)計。

從統(tǒng)計表可以看到，選取的動畫視頻中有超過半數(shù)的鏡頭是以靜態(tài)圖片為背景，這是動畫視頻的一個重要特征。根據(jù)動畫視頻這一特點文章提出相對簡單可行的動畫人物與背景分離方法，即將視頻幀進行非均勻圖像分塊，從而圖像幀分成目標對象區(qū)域與背景區(qū)域。圖像的分塊方法如下圖所示：

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

3.2 第一階段關鍵幀提取

針對動畫視頻大量存在靜態(tài)背景的特點，提出先對視頻幀進行圖像分塊，然后通過計算背景區(qū)域的特征距離，對同一場景內大量高度相似的視頻幀進行篩選。

第一階段的關鍵幀提取主要是提取備選關鍵幀，算法計算復雜度是主要考量因素。上面提到的圖像非均勻分塊方法將背景分成三個不同的區(qū)域，背景區(qū)域2和背景區(qū)域4容易受臺標、視頻字幕或者其他因素的影響，實驗選取背景區(qū)域3為代表進行特征距離計算。

特征距離的選取，第一階段候選關鍵幀提取選取像素差作為特征距離，簡單易實現(xiàn)。實驗研究發(fā)現(xiàn)R、G、B三個分量像素差高度相似，在實驗中計算幀間像素差時以R分量進行計算。下面是R分量的像素特征距離與處理后的幀間互信息量特征距離的對比示意圖。

從圖3可以看到，背景特征距離中大多數(shù)鏡頭分界明顯，為了避免丟失關鍵信息，閾值設置應相對嚴格。通過設置嚴格閾值進行第一階段的備選關鍵幀提取可以過濾大量高度相似的視頻幀，降低視頻幀數(shù)量。

第一階段備選關鍵幀提取算法描述：

第一階段算法步驟完成，得到視頻候選關鍵幀序列。

3.3 基于互信息量特征的關鍵幀二次提取

第一階段對原始視頻幀進行篩選得到候選關鍵幀序列后，需要在候選關鍵幀集合進行第二階段關鍵幀提取，得到最后的關鍵幀。根據(jù)概率關系式，圖像互信息量的計算可演化成：

互信息量作為圖像相似度，能較好地反映圖像的相關度，同時對光照變化不敏感。

參考3.2中的算法步驟，候選關鍵幀集合的第一幀作為關鍵幀，并作為當前關鍵幀，選取集合下一幀，根據(jù)公式（5）計算與當前關鍵幀的互信息量，如果小于設定的閾值，說明幀間差異大，就將其加入最終關鍵幀集合，并更新當前關鍵幀；否則繼續(xù)提取集合中其他關鍵幀進行檢測，直到候選關鍵幀中的幀處理完畢，得到最終的關鍵幀集合。

4 實驗結果分析

文章提出的算法主要目的是提高互信息為幀間特征的視頻關鍵幀提取算法時間效率。實驗選取5個不同類型動畫視頻實驗對象，其中國內動畫視頻1個，日本動畫視頻1個，美國迪士尼動畫視頻3個，視頻片斷平均幀數(shù)超過2000幀。其中算法1是互信息量關鍵幀提取算法，算法2為文章提出的改進算法，關鍵幀提取結果如下：

實驗數(shù)據(jù)表明，文章提出的算法對上述視頻關鍵幀提取結果與單一使用互信息量為特征距離的提取結果鏡頭覆蓋率稍差，但程序的時間復雜度大大降低，消耗的時間僅為算法1的18.61%。同時實驗結果表明，提出的算法關鍵幀提取冗除較少，下圖是其中《蠟筆小新》視頻片斷中的一個鏡頭提取關鍵幀結果對比：

5 結束語

文章針對互信息量計算量大的問題和動畫視頻大量存在鏡頭固定的特點，提出了一種先對視頻幀進行簡單可行的圖像非均勻分塊方法將目標與背景分離，選取計算復雜度低而且嚴格的特征描述對視頻幀進行備選關鍵幀提取，最后利用互信息量進行關鍵幀二次提取。實驗結果表明算法在基本保證與傳統(tǒng)互信息量的提取相同的鏡頭覆蓋率下，大大降低了時間復雜度。算法不足之處是對于并非靜態(tài)背景視頻較差，時間復雜度大大提高，是今后需要改進的。

參考文獻：

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

[2] 曾華，楊漢輝. 一種兩階段的關鍵幀提取方法[J].計算機與現(xiàn)代化，2011（6）.

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

[4] 徐丹. 基于內容的視頻檢索系統(tǒng)研究[D] . 武漢理工大學， 2006.

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

[6] 孔娟， 田麗. 基于互信息量的視頻關鍵幀提取算法[J]. 安陽工學院學報，2010年04期

[7] 徐建華.圖像處理與分析[M] .北京：科學出版社，1992.

[8] F Maes， A Collignon et al. Multimodality Image Registration by Maximization of Mutual Information[J]. IEEETrans. On Med. Imaging，1997，16（2）：189-198.