一種新的基于ＲＳ理論的壓縮域鏡頭分割算法

（1. 蘭州理工大學 電氣工程與信息工程學院，蘭州730050; 2. 蘭州工業高等專科學校，蘭州 730050; 3. 西北師范大學 數學與信息科學學院，蘭州730070）

摘 要：針對傳統的非壓縮域鏡頭分割算法數據多、運算量大和效率低的缺點，提出了一種基于RS理論的壓縮域鏡頭分割算法。該算法首先根據MPEG壓縮標準，從視頻流中提取DCT系數；然后經預處理得到每一幀的DC系數；最后依DC系數建立鏡頭分割信息系統模型，通過RS理論的劃分與屬性約簡得到視頻鏡頭。實驗結果表明，該算法相對傳統非壓縮域算法運算量和數據量大大減少，算法效率明顯提高。

關鍵詞：鏡頭; 鏡頭分割; RS; I幀;壓縮域

中圖分類號：TP391文獻標志碼：A

文章編號：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

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

1 RS理論基本原理

1.1 分辨關系及等價類

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

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

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

顯然IND（P）也是等價關系[9]。不可分辨關系將所有對象分成不同等價類。

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

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

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

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

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

1.3 分辨矩陣

設S＝（U，A）為一信息系統，S的分辨矩陣M定義為一個n階對稱矩陣，其i行、j列的元素定義為

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

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

1.4 約簡與核

定義3 設QP，若Q是獨立的，且IND（Q）＝IND（P），則稱Q是等價關系族P的一個約簡。P中所有不可省關系的集合稱為等價關系族P的核，記為CORE（P）[9]。

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

由MPEG國際標準可知，I幀是MPEG壓縮域中的基礎幀，是視頻信息的主要攜帶者，其信息以DCT系數的形式存在，基于RS理論的鏡頭分割算法就是對DCT系數進行相關處理的基礎上進行數學模型的建立，依據分割模型進行分割。

2.1 I幀與DCT系數抽取

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

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

2.2 對DCT預處理產生DC系數

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

2.3 依DC系數建立信息系統

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

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

根據1.1節中關于等價類與不可分辨關系的理論:

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

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

相鄰兩幀中用DC系數進行分割的數學模型構造如下：

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

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

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

3 實驗與分析

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

同時算法在閾值為0.271時對五種類型的視頻進行了分割實驗。實驗結果如表4所示。

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

視頻類型總幀數系統分割鏡頭數目測分割鏡頭數虛檢鏡頭數漏檢鏡頭數總體評價

體育1127520滿意

動畫174131401滿意

風景317231850基本滿意

故事126131210滿意

新聞153141733基本滿意

本文采用漏檢率、虛檢率、查全率和準確率作為測量指標，分別定義為

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

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

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

準確率=正確的切換數/（正確切換數+錯檢數）×100%(8)

以上指標的統計數據如表5所示。

表5 四種指標對比表

類型漏檢率/%虛檢率/%檢全率/%準確率/%

體育04010071

動畫709392

風景02710078

故事0810092

新聞17178282

同理，對同一鏡頭DC系數與不同鏡頭DC系數進行了對比分析，結果如圖4所示。

4 結束語

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

參考文獻：

［1］

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

[2]王一拙，石峰.基于自動鏡頭分割的視頻壓縮編碼算法[J].計算機輔助設計與圖形學學報，2005， 17(7):1620-1624.

[3]譚楓.鏡頭邊界檢測及關鍵幀提取[D].哈爾濱:哈爾濱工程大學，2006.

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

[5]方勇，戚飛虎. 一種新的視頻鏡頭邊界檢測及關鍵幀提取方法[J]. 華南理工大學學報，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]張文修，仇國芳.基于粗糙集的不確定決策 [M].北京：清華大學出版社，2005.

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