改進(jìn)的互信息量動(dòng)畫(huà)視頻關(guān)鍵幀提取算法

曾華+王耀民

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

關(guān)鍵詞：基于內(nèi)容；動(dòng)畫(huà)視頻；關(guān)鍵幀提取；互信息量； 時(shí)間復(fù)雜度

中圖分類(lèi)號(hào)：TP37 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 階段關(guān)鍵幀提取

基于內(nèi)容的視頻檢測(cè)技術(shù)中，視頻包含大量的視頻幀，以一個(gè)90分鐘電影為例，假設(shè)每秒包含25幀，則視頻總共由135000幀組成，所以處理時(shí)間長(zhǎng)是一個(gè)比較突出的問(wèn)題。文章提出一種先利用非均勻分塊法將視頻幀進(jìn)行非均勻分塊，將目標(biāo)與背景進(jìn)行分離，再利用視頻背景與內(nèi)容相結(jié)合的兩階段關(guān)鍵幀提取方法動(dòng)畫(huà)視頻關(guān)鍵幀。

3.1 圖像非均勻分塊

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

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

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

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

3.2 第一階段關(guān)鍵幀提取

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

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

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

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

第一階段備選關(guān)鍵幀提取算法描述：

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

3.3 基于互信息量特征的關(guān)鍵幀二次提取

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

互信息量作為圖像相似度，能較好地反映圖像的相關(guān)度，同時(shí)對(duì)光照變化不敏感。

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

4 實(shí)驗(yàn)結(jié)果分析

文章提出的算法主要目的是提高互信息為幀間特征的視頻關(guān)鍵幀提取算法時(shí)間效率。實(shí)驗(yàn)選取5個(gè)不同類(lèi)型動(dòng)畫(huà)視頻實(shí)驗(yàn)對(duì)象，其中國(guó)內(nèi)動(dòng)畫(huà)視頻1個(gè)，日本動(dòng)畫(huà)視頻1個(gè)，美國(guó)迪士尼動(dòng)畫(huà)視頻3個(gè)，視頻片斷平均幀數(shù)超過(guò)2000幀。其中算法1是互信息量關(guān)鍵幀提取算法，算法2為文章提出的改進(jìn)算法，關(guān)鍵幀提取結(jié)果如下：

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

[2] 曾華，楊漢輝. 一種兩階段的關(guān)鍵幀提取方法[J].計(jì)算機(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] 徐丹. 基于內(nèi)容的視頻檢索系統(tǒng)研究[D] . 武漢理工大學(xué)， 2006.

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

[6] 孔娟， 田麗. 基于互信息量的視頻關(guān)鍵幀提取算法[J]. 安陽(yáng)工學(xué)院學(xué)報(bào)，2010年04期

[7] 徐建華.圖像處理與分析[M] .北京：科學(xué)出版社，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.