挖掘視頻層次結構，改善視頻管理

摘 要：為了實現視頻層次結構挖掘，提出了一個有效的視頻鏡頭分割算法和一種鏡頭相似性度量方法，然后根據鏡頭顏色、紋理和語義相似性采用場景邊界探測算法構造視頻場景。實驗結果表明，這些算法是可行的。

關鍵詞：視頻層次結構；視頻結構挖掘；場景邊界檢測

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

文章編號：1001-3695(2007)06-0155-03

0 引言

隨著多媒體技術的快速發展產生了大量的視頻數據。近年來為了有效地管理視頻數據，視頻挖掘已經引起了許多研究者的興趣［1－4］，采用各種數據挖掘方法探索視頻數據中的知識和模式。視頻能記錄、保留空間和時間上的各種信息，其內容豐富，是文本、圖像、語音等媒體綜合而成的數據流。其中蘊涵著大量潛在價值的信息和知識。視頻挖掘就是從大量視頻集中，發現有效的、新穎的、有價值的、可理解的模式，即知識，得出事件的趨向和關聯，為用戶提供問題求解層次的輔助能力。

視頻挖掘的成功主要歸功于數據挖掘算法的完善和視頻數據管理的迫切需求。這些視頻挖掘可以粗略地分為三類［1］：①特殊模式挖掘，挖掘視頻中的特殊模式和重要場景；②視頻聚類和分類，將視頻分成不同的類型；③視頻關聯規則挖掘，如視頻編輯規則之間的關聯規則［2］和視頻單元之間的關聯規則［3］。

實際上除了這三種類型的視頻挖掘外，還有一類視頻挖掘，那就是視頻結構挖掘［4］，挖掘視頻基本層次結構，以及探索隱藏于基本結構之中的結構語法和結構語義。通過數據挖掘發現的基本結構、鏡頭語法、場景語法等，表征視頻的結構語法模式；通過抽取的特征類關聯規則和時間相關的事件關聯規則，表現視頻包含的結構語義。這些視頻結構知識可以用于視頻數據庫的組織與管理、基于內容的個性視頻推薦、基于結構語法和語義的視頻摘要等視頻數據的處理當中。

視頻是非結構化的數據流，最基本的物理單元是視頻幀，最高層的結構單元就是視頻節目本身。但是從視頻節目的內容組織來看，它還是有結構可循的，一般認為視頻節目具有如圖1所示的層次結構［5］。

幀是一幅靜態圖像，是組成視頻的最小邏輯單元，將時間上連續的幀序列按等間隔連續播放，便形成動態視頻。鏡頭是一臺攝像機從開機到關機連續拍攝的幀序列，描繪一個事件或一個場面的一部分，不具有或具有較弱的語義信息，強調構成幀的視覺內容相似性，通常用一個或多個關鍵幀（代表幀）來表現鏡頭。場景是語義相關的連續鏡頭，可以是相同對象的不同角度、不同技法拍攝，也可以是具有相同主題和事件的鏡頭組合，強調語義的相關性。視頻節目包含一個完整的事件或故事，作為最高層的視頻內容結構，它包括視頻的組成關系以及對視頻的摘要、語義和一般性描述等。

如何利用數據挖掘的方法將視頻的層次結構重構出來，對于建立視頻數據庫，支持各種視頻應用是非常重要的。視頻層次結構挖掘的基本框架是，首先對視頻流進行鏡頭分割，得到視頻鏡頭和提取關鍵幀；提取鏡頭（或關鍵幀）靜態和動態特征，計算鏡頭相似性，由鏡頭構造視頻場景，實現視頻層次結構挖掘。

本文采用HSV顏色空間不等間隔量化，根據幀間顏色直方圖差分提出了一個有效的鏡頭分割算法；根據鏡頭的顏色、紋理和語義相似性，采用場景邊界探測（Scene Change Detection，SCD)算法構造視頻場景，完成視頻層次結構挖掘。

1 鏡頭分割

從視頻的層次結構來看，鏡頭是基本的結構單元，將視頻分割成鏡頭是尋求視頻結構的第一步，也是非常關鍵的一步。它是場景探測的基礎。鏡頭分割效果的好壞，直接影響到后續的結構化挖掘過程。鏡頭是攝像機連續拍攝的一段畫面。由于攝像機的連續拍攝，鏡頭內部相連和相近的視頻幀間特征相近，變化很小；而在鏡頭轉換處，視頻幀特性往往發生明顯的改變。這為鏡頭邊界的檢測提供了依據。根據轉換處編輯特性的不同，鏡頭間的變換可分為突變和漸變兩種類型。代表性的鏡頭分割方法包括像素匹配法、顏色或灰度直方圖的比較法、邊緣變化率法以及上述方法的結合。顏色直方圖因其簡單高效而廣泛使用，但直接用RGB空間顏色進行計算，直方圖矢量的維數會非常多，占用大量存儲空間、耗時多，而且RGB空間顏色直方圖不能很好地滿足人的感知特征。因此本文使用HSV空間，采用文獻[6]中的方法對HSV顏色進行不等間隔量化，然后在此基礎上提出了一種有效的自適應雙閾值鏡頭分割算法。

1.1 顏色量化

按照以上的量化級，根據式(2)將三個顏色分量合成為一維特征矢量。

1.2 鏡頭分割算法及關鍵幀提取

假定一個鏡頭內幀間顏色直方圖差分服從N(μ， σ2)的正態分布。其中μ是鏡頭中幀間差分均值，σ是幀間差分標準差，由統計學中的“68-95-99.7規則”可以認為：

在鏡頭探測過程中，閾值選取是一個非常關鍵的問題。一般來講，對于一段視頻，選用全局閾值進行鏡頭探測是不太準確的。因為實驗表明閾值的設定與鏡頭內視頻的內容有很大的關系，一個閾值可能對于某段視頻有效，而對于另一段內容不同的視頻就不太合適。對于長視頻文件更是如此，因此自適應的閾值選取尤為重要，它將使整個視頻的鏡頭探測結果更加準確有效。

本文的自適應雙閾值鏡頭探測算法如下：在探測當前幀前選用一個滑動窗口，包括M幀（試驗中取M＝30），計算這M幀的幀間顏色差分平均值μ和標準差σ，用μ±Tσ來計算閾值。當閾值確定后，采用文獻[7]中的雙閾值鏡頭探測算法進行鏡頭分割，一般來說低閾值取T為2或3，高閾值取T為5或6。同時用標準差σ衡量閾值的有效性，如果方差σ比較小，表明窗口內的幀相對比較平滑，適合作閾值標準；反之，如果方差σ很大，表明此滑動窗口內的視頻內容有較大的變化，則不適合作為閾值標準，仍根據以前的μ和σ計算閾值。

當鏡頭分割完成后，為了簡化計算，用鏡頭的中間幀作為關鍵幀。

2 鏡頭的相似性度量

除了在進行鏡頭分割時提取的顏色特征外，以鏡頭為基本結構單元進一步提取鏡頭關鍵幀的同構紋理和鏡頭的語義信息，由顏色、紋理、語義計算鏡頭的相似性，同時考慮視頻的時基特性來構造視頻場景。

2.1 顏色相似性度量

2.2 紋理相似性度量

紋理是幀圖像中一個重要而又難以描述的特性。很多圖像在局部區域內可能呈現出不規則性，而在整體上表現出某種規律性，習慣上將圖像中這種局部不規則的、而宏觀有規律的特性稱之為紋理。紋理特征主要有粗糙性、方向性和對比度等，紋理作為物體的一個重要特征，是圖像媒體的一條重要信息線索。

同構紋理描述子(Homogeneous Texture Descriptor，HTD)［8］基于人類視覺系統，對視覺信號的反映轉換成頻域中的一個有限頻道，通過Gabor濾波器加強頻域在不同頻道的能量，通過頻道的平均能量和能量標準差來反映圖像的紋理特征。具體方法是將頻率平面按方向和半徑分割成30個頻道，頻道在角度上是以30°等量分割為六個方向，而半徑則以二分之一為底等比分割為五個半徑，然后計算在每個頻道中的平均能量和標準差，將其記錄在描述子中：

2.3 語義信息相似性度量

語義信息對鏡頭的相似性匹配有著很重要的作用，用一列關鍵詞來描述鏡頭的語義信息。關鍵詞的提取原則：主要選擇實詞作為關鍵詞，如名詞、動詞、形容詞等。其中名詞比其他詞更能代表語義信息，過濾掉虛詞，如連詞、介詞等。

2.4 鏡頭多特征相似性

根據前面定義的鏡頭相似性度量，shoti和shotj是鏡頭序列中的兩個鏡頭，則它們之間的多特征相似性定義為

對于一段長視頻，可能包含很多鏡頭，而時間相距越遠，屬于同一個場景的可能性越小。因此算法不應將相距很遠的鏡頭聚集在一起。為了避免這種情況出現，引入時間約束機制，定義時間系數為

3 基于鏡頭的場景邊界檢測

根據上述定義的鏡頭相似性度量，采用基于分裂和合并力量競爭［9］的視頻場景邊界探測方法，將一系列連續的鏡頭歸納為一個場景結構。每個鏡頭受到兩種力的作用。一種力是來自前后兩個方向的分裂力，如果這兩個方向的分裂力的比值較大，那么這個鏡頭很可能處在一個新場景的邊界上；另一種力是合并力，它阻止當前鏡頭被單方向的分裂力所吸引。一種簡單的閾值算法用于檢測場景邊界。

基本思路是：對于每一個鏡頭shoti，根據它和前后鏡頭的相似性定義四個量：

4 實驗結果和結論

對鏡頭分割算法使用五段視頻序列進行了測試。其中兩段為實時采集的電視視頻（TV1和TV2），其余為電影視頻片段。為了保證算法的有效性，對電影視頻作了適當的挑選。其中Mov1為愛情片，Mov2為喜劇片，Mov3為功夫片。所有測試視頻中，共有15 620幀，突變171個，漸變48個。其中TV1和Mov2沒有漸變。

在進行鏡頭分割時，由μ+5σ確定突變閾值，μ+3σ確定漸變潛在的起始幀。一旦確定了這個幀，就用它與后續幀進行比較，用累積差分來取代幀間差分。這個累積差分必須是單調的，應該不斷加大，直至這個單調過程中止。這時，將累積差值與μ+5σ閾值進行比較。如果超過了這個閾值，就可以認為這個累積差值單調增的序列對應的就是一個漸變。

回調率較差，主要是因為快節奏電影的內容通常比較復雜，變化較快，其鏡頭比慢節奏電影更難識別。

表1 鏡頭分割實驗結果

場景邊界探測中，對三段長度約為15 min的視頻進行實驗。參數設定為T1=0.6，T2=0.7，T3=0.2。測試結果與肉眼觀測的場景進行比較，結果如表2所示。從表中可以看出，平均性能為回調率0.906和查準率0.935，結果比較滿意。

為了有效地組織、瀏覽和檢索視頻數據，從視頻序列中抽取鏡頭層和場景層結構信息是非常重要的。本文基于HSV顏色空間提出了一種自適應雙閾值鏡頭探測算法，并利用鏡頭顏色、紋理和語義相似性，采用場景邊界探測算法進行視頻場景分割，完成視頻場景結構構造，充分考慮了視頻的時基特性和場景的語義特性。實驗結果表明，算法的效果理想。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。