（1. 蘭州理工大學(xué) 電氣工程與信息工程學(xué)院，蘭州730050; 2. 蘭州工業(yè)高等?？茖W(xué)校，蘭州 730050; 3. 西北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，蘭州730070）

摘 要：針對(duì)傳統(tǒng)的非壓縮域鏡頭分割算法數(shù)據(jù)多、運(yùn)算量大和效率低的缺點(diǎn)，提出了一種基于RS理論的壓縮域鏡頭分割算法。該算法首先根據(jù)MPEG壓縮標(biāo)準(zhǔn)，從視頻流中提取DCT系數(shù)；然后經(jīng)預(yù)處理得到每一幀的DC系數(shù)；最后依DC系數(shù)建立鏡頭分割信息系統(tǒng)模型，通過(guò)RS理論的劃分與屬性約簡(jiǎn)得到視頻鏡頭。實(shí)驗(yàn)結(jié)果表明，該算法相對(duì)傳統(tǒng)非壓縮域算法運(yùn)算量和數(shù)據(jù)量大大減少，算法效率明顯提高。

關(guān)鍵詞：鏡頭; 鏡頭分割; RS; I幀;壓縮域

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1588-03

Novel compressed-domain shot segment alogrithm based on RS theory

LI Xiang-wei1，2， LI Zhan-ming1， ZHANG Ming-xin3， ZHANG Guo-quan1， WEI Zhe1

(1. College of Electrical Engineering Information Engineering， Lanzhou University of Technology， Lanzhou730050， China;2. Lanzhou Polytechnic College， Lanzhou730050， China; 3. College of Mathematics Information Science， Northwest Normal University， Lanzhou730070， China)

Abstract:Aimed at overcoming the amount of computing and low efficient of traditional shot segment methods in noncompressed-domain.The paper presented a new compressed-domain shot segment algorithm based on RS theory. The method extracted DCT coefficients from the video stream according to MPEG standard firstly. And then got the DC coefficients after the preprocessing. At last，constructed the information system using DC coefficients and got shot segment model. Experimental results show that the alogrithm reduced the amount of computing and data obviously， the efficiency is increased dramaticly.

Key words：shot; shot segment; RS; I frame; compressed-domain

隨著數(shù)字視頻的大量出現(xiàn)，如何對(duì)非結(jié)構(gòu)化視頻數(shù)據(jù)進(jìn)行組織、表達(dá)、管理、查詢和檢索成為目前的迫切需求。而基于內(nèi)容的視頻瀏覽和檢索則是解決這一問(wèn)題的有效方法。其中的鏡頭分割則是這一問(wèn)題的基礎(chǔ)與關(guān)鍵。文獻(xiàn)[1]對(duì)目前常用的鏡頭分割方法進(jìn)行了總結(jié)，詳細(xì)分析了灰度分割法、邊緣分割法、彩色直方圖分割法、MPEG的視頻分割方法、塊匹配鏡頭分割方法、統(tǒng)計(jì)判決鏡頭分割方法、基于聚類的鏡頭分割方法、鏡頭漸變的檢測(cè)等。文獻(xiàn)[2] 提出了一種基于對(duì)分查找的鏡頭分割算法，此算法通過(guò)對(duì)分查找的策略形成二叉樹(shù)，同時(shí)通過(guò)廣度優(yōu)先搜索尋找分割點(diǎn)，能夠較好地實(shí)現(xiàn)鏡頭的分割。文獻(xiàn)[3]提出了一種改進(jìn)的鏡頭分割算法，即基于傳統(tǒng)方法的閾值自適應(yīng)鏡頭邊界檢測(cè)方法，此方法結(jié)合多種鏡頭檢測(cè)的優(yōu)點(diǎn)，揚(yáng)長(zhǎng)避短，在一定程度上提高了鏡頭分割的效率。以上算法在理論上均可行，而在實(shí)踐中，所有視頻幾乎全部以壓縮的形式儲(chǔ)存與傳輸，因此，以上方法需要壓縮、計(jì)算、解壓和再計(jì)算的復(fù)雜過(guò)程，故效率并不理想，特別是隨著待處理視頻數(shù)據(jù)的急劇增加，算法的效率和實(shí)時(shí)性急劇下降。文獻(xiàn)[4]提出了一種基于壓縮域的視頻摘要研究方法，為研究基于內(nèi)容的視頻檢索提供了思路。但距真正的基于壓縮域的視頻檢索仍有距離。文獻(xiàn)[5~8]分別討論了基于關(guān)鍵幀、基于對(duì)象、基于前景和背景的鏡頭分割技術(shù)，各種方法有其自身的優(yōu)點(diǎn)，但均存在數(shù)據(jù)量大和分割方法主觀性強(qiáng)等不足之處。本文是在深入分析研究MPEG視頻幀結(jié)構(gòu)及相關(guān)理論的基礎(chǔ)上，得出I幀是視頻流的基礎(chǔ)幀，壓縮時(shí)采用幀內(nèi)壓縮，即消除了空間上的冗余性，又保留了視頻幀圖像的主要信息。I幀采用DCT變換（DCT變換后的系數(shù)是反映每一幀視頻的惟一標(biāo)志），因此，可以直接對(duì)DCT系數(shù)進(jìn)行分析而達(dá)到分析每一幀視頻的目的。本文基于RS的壓縮域鏡頭分割算法就是在對(duì)壓縮域DCT系數(shù)進(jìn)行預(yù)處理后建立DC的信息系統(tǒng)，然后依RS的劃分與約簡(jiǎn)理論進(jìn)行鏡頭分割。

1 RS理論基本原理

1.1 分辨關(guān)系及等價(jià)類

定義1 如果任意兩個(gè)對(duì)象xi、xj對(duì)所有條件屬性其值相等，則稱其為不可分辨對(duì)象。

定義2 令R為等價(jià)關(guān)系族，設(shè)PR，且P≠，則P中所有等價(jià)關(guān)系的交集稱為P上的不可分辨關(guān)系，記為ind（P）即有

[x]ind(P)=IR∈P[x]R(1)

顯然IND（P）也是等價(jià)關(guān)系[9]。不可分辨關(guān)系將所有對(duì)象分成不同等價(jià)類。

1.2 集合的上近似與下近似

粗糙集理論的不確定性是建立在上、下近似的概念之上。令XU是一個(gè)集合，R是定義在U上的等價(jià)關(guān)系，則

R-X=Y{Y∈U/R｜YX}(2)

RX=Y{Y∈U/R｜Y∩X≠}(3)

分別稱為X的R下近似與R上近似集[9]。

1.3 分辨矩陣

設(shè)S＝（U，A）為一信息系統(tǒng)，S的分辨矩陣M定義為一個(gè)n階對(duì)稱矩陣，其i行、j列的元素定義為

mi，j ={a∈A｜f(xi，a)≠f(xj，a)};i，j=1，…，n

即mij是能夠區(qū)別對(duì)象xi和xj的所有屬性的集合[9]。

1.4 約簡(jiǎn)與核

定義3 設(shè)QP，若Q是獨(dú)立的，且IND（Q）＝IND（P），則稱Q是等價(jià)關(guān)系族P的一個(gè)約簡(jiǎn)。P中所有不可省關(guān)系的集合稱為等價(jià)關(guān)系族P的核，記為CORE（P）[9]。

2 基于RS理論的壓縮域鏡頭分割算法

由MPEG國(guó)際標(biāo)準(zhǔn)可知，I幀是MPEG壓縮域中的基礎(chǔ)幀，是視頻信息的主要攜帶者，其信息以DCT系數(shù)的形式存在，基于RS理論的鏡頭分割算法就是對(duì)DCT系數(shù)進(jìn)行相關(guān)處理的基礎(chǔ)上進(jìn)行數(shù)學(xué)模型的建立，依據(jù)分割模型進(jìn)行分割。

2.1 I幀與DCT系數(shù)抽取

由MPEG視頻壓縮國(guó)際標(biāo)準(zhǔn)可知，視頻在傳輸與存儲(chǔ)時(shí)均為壓縮形式，而在壓縮域視頻表現(xiàn)為三種類型的幀，分別為I幀、P幀和B幀。I幀為主要信息攜帶者，其表現(xiàn)為DCT系數(shù)。其壓縮過(guò)程如圖1 所示。DCT系數(shù)又分為直流系數(shù)(DC)和交流系數(shù)(AC)，直流系數(shù)又是DCT系數(shù)的主要成分。在壓縮域中可直接得到視頻幀的DCT系數(shù)。

圖2和3是以壓縮形式存儲(chǔ)的兩個(gè)視頻幀。表1是圖3處理后抽取的部分DCT系數(shù)。

2.2 對(duì)DCT預(yù)處理產(chǎn)生DC系數(shù)

對(duì)DCT系數(shù)進(jìn)行預(yù)處理可得到DC系數(shù)（直流系數(shù)或稱之為低頻系數(shù)），表2為表1預(yù)處理后得到的DC系數(shù)。依據(jù)DCT變換理論，DC系數(shù)是I幀圖像的主要信息攜帶者，代表了I幀圖像的平均亮度信息，因?yàn)閷?duì)于鏡頭的分割一方面有誤差所允許的范圍；另一方面，在人眼視覺(jué)范圍內(nèi)，有一部分信息是不敏感的，因此由DC系數(shù)提供的信息足以進(jìn)行鏡頭分割[10]。

2.3 依DC系數(shù)建立信息系統(tǒng)

以每一視頻幀為行，以每一幀的DC系數(shù)為列，可得到一段視頻的DC信息系統(tǒng)，每一視頻幀可視為元素，每一DC系數(shù)可視為每一幀的屬性。表3為基于DC系數(shù)的信息系統(tǒng)。

2.4 依RS理論及閾值分割模型劃分鏡頭

根據(jù)1.1節(jié)中關(guān)于等價(jià)類與不可分辨關(guān)系的理論:

若PR，且P≠，則∩P為一個(gè)等價(jià)關(guān)系，稱為P的不可分辨關(guān)系，記為ind(P);U為感興趣的視頻幀組成的有限集合，子集XU稱為U中的一個(gè)概念，R是U上的一個(gè)等價(jià)關(guān)系或劃分。

在DC信息系統(tǒng)中，對(duì)相鄰兩幀的DC系數(shù)平均差值與給定閾值進(jìn)行比較。如果大于閾值，則鏡頭分割；如果小于閾值，則分到同一鏡頭，接著比較下兩幀。

相鄰兩幀中用DC系數(shù)進(jìn)行分割的數(shù)學(xué)模型構(gòu)造如下：

D(li，l)=1/1 024[∑1 0241｜c(diǎn)(li，k)-c(li+1，k｜)/

max(c(li，k)，c(li+1，k))](4)

其中：li，Ii+1代表第i和 i+1 個(gè)I幀；c(li，k)與c(li+1，k)為相鄰兩幀k塊的DC系數(shù)。稱式(4)為相鄰兩幀的差異度。其閾值由大量實(shí)驗(yàn)和經(jīng)驗(yàn)得出，本算法中確定為0.271。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證算法的有效性，選取了自己建立的視頻數(shù)據(jù)庫(kù)進(jìn)行測(cè)試，數(shù)據(jù)庫(kù)大小為3 GB，分別有動(dòng)畫、體育、故事、新聞和風(fēng)景五種不同類型的MPEG視頻。而且對(duì)每種不同的視頻均以人的視覺(jué)特征為基礎(chǔ)進(jìn)行手工鏡頭分割，作為算法分析的參考對(duì)象。分割算法用Java語(yǔ)言實(shí)現(xiàn)，其他部分功能用MATLAB2007實(shí)現(xiàn)。經(jīng)過(guò)大量的實(shí)驗(yàn)與目測(cè)鏡頭相比較，得到給定閾值為0.271，即平均差值大于0.271則進(jìn)行鏡頭分割；否則，繼續(xù)比較下兩幀。

同時(shí)算法在閾值為0.271時(shí)對(duì)五種類型的視頻進(jìn)行了分割實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表4所示。

表4 五種類型的視頻鏡頭分割結(jié)果

視頻類型總幀數(shù)系統(tǒng)分割鏡頭數(shù)目測(cè)分割鏡頭數(shù)虛檢鏡頭數(shù)漏檢鏡頭數(shù)總體評(píng)價(jià)

體育1127520滿意

動(dòng)畫174131401滿意

風(fēng)景317231850基本滿意

故事126131210滿意

新聞153141733基本滿意

本文采用漏檢率、虛檢率、查全率和準(zhǔn)確率作為測(cè)量指標(biāo)，分別定義為

漏檢率=漏檢的鏡頭數(shù)/實(shí)際存在的機(jī)頭切換數(shù)×100%(5)

虛檢率=虛檢的鏡頭切換數(shù)/全部檢測(cè)到的鏡頭切換數(shù)×100%(6)

檢全率=正確切換數(shù)/（正確切換數(shù)+漏檢數(shù)）×100%(7)

準(zhǔn)確率=正確的切換數(shù)/（正確切換數(shù)+錯(cuò)檢數(shù)）×100%(8)

以上指標(biāo)的統(tǒng)計(jì)數(shù)據(jù)如表5所示。

表5 四種指標(biāo)對(duì)比表

類型漏檢率/%虛檢率/%檢全率/%準(zhǔn)確率/%

體育04010071

動(dòng)畫709392

風(fēng)景02710078

故事0810092

新聞17178282

同理，對(duì)同一鏡頭DC系數(shù)與不同鏡頭DC系數(shù)進(jìn)行了對(duì)比分析，結(jié)果如圖4所示。

4 結(jié)束語(yǔ)

視頻信息處理是當(dāng)前研究的熱點(diǎn)，鏡頭分割是這一技術(shù)的基礎(chǔ)與關(guān)鍵。當(dāng)前的鏡頭分割算法均在直接非壓縮域上進(jìn)行，即對(duì)原視頻先進(jìn)行解壓后進(jìn)行，因此算法的數(shù)據(jù)量和運(yùn)算量很大，實(shí)時(shí)性和效率也受到影響。本文提出的算法直接在壓縮域進(jìn)行；同時(shí)，RS理論可以在不需要任何先驗(yàn)知識(shí)的前提下對(duì)數(shù)據(jù)元素進(jìn)行劃分，即提高了算法科學(xué)性與有效性。

參考文獻(xiàn)：

［1］

劉政凱，湯曉鷗.視頻檢索中的鏡頭分割方法綜述[J].計(jì)算機(jī)工程與應(yīng)用，2002，(23):84-87.

[2]王一拙，石峰.基于自動(dòng)鏡頭分割的視頻壓縮編碼算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005， 17(7):1620-1624.

[3]譚楓.鏡頭邊界檢測(cè)及關(guān)鍵幀提取[D].哈爾濱:哈爾濱工程大學(xué)，2006.

[4]李曉光，沈蘭蓀.壓縮域視頻內(nèi)容分析與摘要提取技術(shù)[J]. 測(cè)控技術(shù)，2006， 25(5):17-19.

[5]方勇，戚飛虎. 一種新的視頻鏡頭邊界檢測(cè)及關(guān)鍵幀提取方法[J]. 華南理工大學(xué)學(xué)報(bào)，2004， 32(11):18-21.

[6]MONEY A G， AGIUS H. Video summarisation: aconceptual framework and survey of the state of the art[J]. Journal of Visual Image Representation， 2007， 19(2):121-143.

[7]Lei Bang-jun， Xun Li-Qun， Real-time outdoor video surveillance with robust foreground extraction and object tracking via multi-state traqnsition management[J]. Pattern Recognition Letters， 2006， 27(15):1816-1825.

[8]CHEN Liang-hua， LAI Yu-chun， LIAO H Y M. Movie scene segmentation using background information[J]. Pattern Recognition， 2008，41(3):1056-1065.

[9]張文修，仇國(guó)芳.基于粗糙集的不確定決策 [M].北京：清華大學(xué)出版社，2005.

[10]李向偉，李戰(zhàn)明，張明新.基于RS理論的鏡頭分割預(yù)處理算法 [J].蘭州理工大學(xué)學(xué)報(bào)，2008， 34(3):1-4.