基于ＢＰ神經網絡的視頻鏡頭突變檢測算法
2008-12-31 00:00:00王讓定李雪芳
計算機應用研究 2008年11期
（寧波大學 信息科學與工程學院， 浙江 寧波315211）
摘要：對于數字視頻鏡頭突變切換的檢測，一般有模板匹配法、直方圖法等基本算法，但這些算法都需要確定閾值，并在實際檢測中通常達不到較高的檢測精度。提出了一種新的基于BP神經網絡的視頻鏡頭突變檢測算法，該算法選取模板匹配二次差分和直方圖二次差分作為特征，利用神經網絡的自組織、自學習能力實現鏡頭突變檢測，然后以閃光檢測來提高檢測的可靠性。實驗結果表明，該算法能夠有效地檢測視頻的鏡頭突變，無須設定閾值，具有計算簡單、易于實現的優點。
關鍵詞：鏡頭分割；突變檢測；BP網絡；閃光檢測
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2008)11-3480-03
Video abrupt shot change detection algorithm based on BP network
WANG Rang-ding，LI Xue-fang
(College of Information Science Engineering， Ningbo University， Ningbo Zhejiang 315211， China)
Abstract:There are some basic algorithms， including the template-matching algorithm， the histogram algorithm， etc， used to detect abrupt shot change in digital video， but they all need to fix on threshold and can’t always attain high precision in practical detecting.This paper proposed a new BP neural network based video abrupt shot change detection algorithm.It selected template-matching twice-difference and histogram twice-difference as characters， utilized the neural network’s ability of self-organization and self-learning to actualize abrupt shot change detection， then performed the flashlight detection to improve the detecting reliability. Experimental results show that this method achieves satisfying precision and recall of detecting shot boundaries compared with the conventional schemes， at the same time， it don’t need threshold and easy to implement.
Key words:shot segmentation; abrupt change detection; BP network; flashlight detection
0引言
隨著多媒體時代的到來，視頻已日益成為人們生活中不可或缺的信息載體，相關的視頻處理研究也越來越多。鏡頭分割是視頻處理的第一步，是隨后的高層內容分析、分類、索引和查詢的基礎。鏡頭分割的準確性將直接影響到后續處理的效果。因此，視頻鏡頭分割技術一開始就得到了廣泛的重視，它在基于內容的視頻分析和檢索中有著最長的研究歷史和最豐富的研究成果[1]。然而直到今天，鏡頭分割的技術還很不成熟，仍然沒有在各種情況下都能表現出良好性能的算法，因而研究穩健可靠的實用鏡頭分割方法是目前主要的研究方向。
鏡頭是視頻的基本物理單元，由一個攝像機連續拍攝的、時間上連續的若干幀圖像組成，代表了一個連續的動作。鏡頭之間的變換包括突變（切變）和漸變兩種。突變是指一個鏡頭不采用任何編輯效果直接變換到另一個鏡頭；漸變是指一個鏡頭通過某種編輯手段，如淡入、淡出、疊化等，緩慢地變換到另一個鏡頭[2，3]。突變切換由于處理簡潔，在實際的數字視頻中被大量采用。突變切換的檢測是鏡頭分割首先要解決的問題，它在鏡頭切換檢測中占據著極其重要的地位。
鏡頭分割分為壓縮域和非壓縮域兩種，本文的算法是在非壓縮域進行的。非壓縮域鏡頭分割技術先將視頻解壓縮，再對解壓縮后的視頻進行分析處理。一般鏡頭內部前后幀畫面內容基本相近；在鏡頭邊界處，前后幀內容差別較大。要檢測視頻鏡頭邊界，首先需要選取特征以描述視頻內容的不連續性，鏡頭邊界檢測方法就是通過比較相鄰兩幀的差異來尋找這些變化的規律，即幀間差算法。已經提出的幀間差算法很多，如模板匹配法、直方圖法、基于塊的方法、基于邊緣的方法、基于運動矢量的方法等但在現有條件下，還沒有發現一種性能明顯優越的方法。直方圖法和模板匹配法因其算法簡單、運算量小、在實際檢測中尚能達到較好的性能而在實際的視頻檢索系統中被較多地采用。
1典型的鏡頭突變檢測算法
11基于像素比較的方法
基于像素比較的方法又稱為模板匹配的方法，該方法是計算相鄰兩幀各個對應像素之間的絕對差值[4]。對于彩色視頻，其第m幀視頻幀和第n幀的對應像素之間的平均絕對差值定義為
D(Im，In)=M-1i=0N-1j=0{|Im(i，j;r)-In(i，j;r)|+|Im(i，j;g)-In(i，j;g)|+|Im(i，j;b)-In(i，j;b)|}/（M×N×3）(1)
其中：Im(i，j;*)為第m幀圖像(i， j)位置的像素值，In(i， j;*)為第n幀的相應值；r、g、b分別表示該像素點的紅、綠和藍色分量值；M、N為幀的寬度和高度。如果D(Im，In)大于一個預定義的閾值，則認為發生了鏡頭突變。由于該方法嚴格地局限于像素的空間位置，它對噪聲和鏡頭或物體運動十分敏感。為了減少物體運動的影響，Zhang等人[5]提出了在對幀進行像素比較之前，先用3×3均值濾波器對幀像素進行平滑的方法。
12基于直方圖比較的方法
另一種常用的方法是利用幀的直方圖作為特征，其主要思想是：認為一個鏡頭內的連續幀包含有相近的全局視覺性質，這表現在它們的直方圖之間的差異要小于鏡頭邊界兩邊兩幀的直方圖間的差異。其基本原理是將顏色空間分為一個個離散的顏色小區間，然后計算落入每個小區間的像素數目。在RGB彩色空間中，一幀圖像的直方圖可以表示成三個獨立的1-D分布或者一個3-D分布，三個1-D直方圖法由于儲量小和計算成本低而得到了普遍的重視。表示直方圖差異的方法有直方圖幀差法、 χ2檢驗直方圖差法、直方圖最小幀差法、平均彩色法等。其中直方圖最小幀差法性能最好[6]。
設顏色區間分為K個區間，hkm(*)、hkn(*)分別表示視頻第m幀和第n幀中落入第k個顏色區間的像素數目。采用三個獨立的1-D分布的直方圖最小幀差法定義為
H(Im，In)=1-Kk=1{min(hkm(r)，hkn(r))+min(hkm(g)，hkn(g))+min(hkm(b))，hkn(b))}/（M×N×3）(2)
如果H(Im，In)大于一個閾值，則認為發生了鏡頭突變。由于直方圖只注重全局分布，此特征對局部物體運動不敏感，但當鏡頭內存在全局運動時，直方圖會發生較大變化。另外，當兩幀圖像有完全不同的結構，但其直方圖卻很接近，這時就會發生漏檢。
目前，鏡頭突變的檢測基本上是基于閾值的方法，主要有全局閾值法[7，8]、局部自適應閾值法[9，10]和基于聚類的方法[11]等。這些鏡頭檢測方法共同的缺陷是無法適應各種不同的情況，對一段視頻有效的閾值對另一段視頻可能會失效。長的視頻序列在每一個時間段的內容變化特性并不相同，對于幀—幀差異的度量不存在一個統一的尺度，因此它們的閾值選取都較為困難。本文的算法是利用BP神經網絡的自組織、自學習和自適應能力來實現鏡頭突變檢測，該算法無須設定任何閾值，具有計算簡單、易于實現的優點，算法能夠有效地檢測各種類型視頻的鏡頭突變，實際應用中價值較大。
2BP算法檢測鏡頭突變
21BP網絡結構的確定和輸入參數的選擇
BP網絡是一種誤差反傳的神經網絡，典型的BP模型有一個輸入層、一個輸出層和至少一個隱含層。理論上，隱含層的層數沒有限制，但常用的是一層或二層。本文的算法確定為三層的BP網絡，分別為輸入層、隱含層和輸出層。
輸入層用于輸入樣本的特征值，每一個輸入節點對應樣本一個特征。本算法中需求出兩個特征作為輸入數據。隱含層用于對輸入模式的特征進行提取，并將提取出來的特征傳遞給輸出層，輸出層對輸入模式的類別作最后的判別。根據輸入層節點和訓練樣本的個數，隱含層節點數確定為三個。由于這是兩類的問題，輸出層只需一個節點就夠了。期望輸出值為1或0，1代表突變幀，0代表非突變幀。
特征是BP網絡模式識別的依據，選取較好的特征可以減弱鏡頭內局部和全局運動的影響并盡可能最大表現鏡頭轉換處的視覺內容的不連續性。特征參數的選擇直接關系著BP網絡的模式分類的優劣。
視頻運動包括攝像機鏡頭的運動和視頻內物體的運動，視頻運動會在各種幀間差算法中產生出幀間差，從而影響對鏡頭突變切換的檢測。文獻[7]指出，如果對模板匹配法以及直方圖法等基本幀間差算法計算得到的幀間差再作一次差分（即二次差分法），在發生視頻運動的視頻幀位置將只得到很小的差分值；而在發生鏡頭突變切換的位置，這個差分值則仍將保持與原來的幀間差值相近的數值。這樣，通過作這樣的一次差分處理，就很大地降低了視頻運動對鏡頭切換檢測的影響。
由式(1)計算出相鄰兩幀的對應像素之間的平均絕對差值d(m)=D(Im，Im-1)再作一次差分。令f(m)=d(m)-d(m-1)，為了滿足BP算法對輸入數據的要求，設f1(m)=f(m)/100；類似地，由式(2)計算出相鄰兩幀的直方圖最小幀差法t(m)=H(Im，Im-1)，再作一次差分，得到f2(m)=t(m)-t(m-1)。將f1(m)、f2(m)作為BP網絡的輸入參數。
圖1、2分別是用模板匹配法、直方圖法對球類比賽(視頻1)的第100~400幀視頻段所計算的幀間差特性曲線圖和二次差分特性曲線圖。圖中，s(m)=d(m)/100。從圖中可以看出，模板匹配法對視頻運動較敏感，而直方圖法則能抑制視頻運動的影響。通過二次差分，由視頻運動產生的幀間差被大幅度消除，而由鏡頭切換造成的幀間差則基本保持原來的幅度，從而達到優于現有幀間差算法的性能。
22BP網絡學習與模式分類
BP網絡是一種學習機，要實現分類的目的首先得讓它學習，即用一些學習樣本來訓練它。神經網絡通過樣本的訓練，不斷地改變自己，不僅可以處理各種變化的信息，而且在處理信息的同時，其自身也在不斷地變化，因而具有很強的自組織、自學習能力。設com(m)=f1(m)+2f2(m)，對待測視頻中的連續的n幀，求出其com值，并按此進行排序。在前e名中隨機地取p個幀作為突變幀，期望輸出值為1；在后f名中隨機地取q個幀作為非突變幀，期望輸出值為0，組成p+q個訓練樣本。本實驗中，p=q=5，即共有10個學習樣本。
BP網絡的學習過程由正向和反向傳播兩部分組成。在正向傳播過程中，每一層神經元的狀態只影響下一層神經元， 根據輸入值，先計算隱含層各個神經元的輸出值，然后計算出輸出層的輸出值。如果輸出層不能得到期望輸出，即實際輸出值與期望輸出值之間有誤差，那么轉入反向傳播過程，網絡便將誤差由輸出層向輸入層的方向逐層反向傳播并逐層修正相應的權值。如此反復學習，直到誤差達到所希望的要求，網絡的學習過程就結束了。
BP網絡學習結束后，神經元之間的連接強度就固定下來了，這時就可以進行模式分類了。將f1(m)、f2(m)輸入神經網絡，BP網絡會計算出相應的輸出值a，則可判別視頻幀m的類別，即
a≥0.6突變幀
0.4＜a＜0.6不確定幀
a≤0.4非突變幀
3閃光檢測
很多視頻節目（如新聞節目、體育節目等）常常會有突然的閃光出現。一般情況下，閃光持續時間很短，但亮度變化卻很大，二次差分法無法消除閃光的影響。在無閃光時，文獻[7]的像素點匹配二次差分法能夠實現對鏡頭突變切換的較準確的檢測，但如果有閃光頻繁出現，就會出現較多的誤檢現象；而且該算法還需要確定閾值，這限制了它在實際中的應用。目前比較常用的突變檢測算法在閃光出現時都會判別為突變位置，從而導致誤檢。因而，通過上述BP算法確定準突變位置后，再次對準突變位置進行閃光檢測尤其重要，可以有效降低誤檢現象。圖3給出了球類比賽（視頻a）中的一個例子。
一般來說，一次閃光的影響為鏡頭內一幀或連續的幾幀。上例中，第2237幀為閃光位置，在幀間差特征圖中出現了連續的雙峰現象，模板匹配法與直方圖法一般都會把第2237幀和2238幀都誤檢為突變幀。若用二次差分值做參數，則只有第2237幀被誤檢為突變幀。
設p為待測的準突變幀，則在p前后各取一幀fore與back，本實驗中， p-4≤fore≤p-1，
p+1≤back≤p+3。求出fore幀與back幀的差異值diff1=D(Ifore，Iback)/100和diff2=D(Ifore，Iback)，將diff1、diff2輸入學習后的BP網絡，計算出輸出值d。若d≤0.4，則表示這兩幀的相似度大，它們屬于同一鏡頭，兩幀之間不存在鏡頭突變，p是閃光位置；否則，就認為p是真正的突變位置。
4實驗結果
對鏡頭邊界檢測結果的評價方法一般使用查全率和查準率這兩個參數，定義為
查全率（recall）=hit/(hit+miss)
精確率（precision）=hit/(hit+1)
其中：hit代表正確檢測出的突變個數；miss代表漏檢的突變個數；1代表誤檢的突變個數。
為了驗證本文算法的有效性，選取了三類典型的視頻作為實驗視頻樣本，它們分別是球類比賽（視頻a 320×240）、新聞聯播節目（視頻b 320×240）和影視羅曼史（視頻c 352×288），均是24位真彩色。幾個分割出的視頻鏡頭如圖4所示，表1~3分別列出了五種檢測算法對
視頻a中含有121幀的閃光幀和較多的全局運動幀，視頻b無閃光幀，視頻c含有29幀閃光幀，因此直接幀間差算法與二次差分法對視頻a的檢測效果最差，對視頻b的檢測效果最好；本文的算法運用了閃光檢測，大大提高了檢測的可靠性。從實驗結果可知，對于模板匹配和直方圖比較的兩種檢測算法，其二次差分法的性能均優于其直接的幀間差算法，而本文的算法綜合利用了模板匹配二次差分和直方圖二次差分這兩個特征參數，達到了最佳的檢測性能。前四種算法的閾值選取很困難，經過反復實驗后才確定了合適的閾值，每種方法對這三段視頻的閾值都不同，共有12個閾值。其中模板匹配幀間算法采用的閾值分別為0.43、0.28、0.52。本文的算法無須確定閾值，只要BP網絡結構確定。網絡初始化后，便統一地應用于這三段視頻，簡單而有效。
5結束語
許多視頻鏡頭分割方法都用到了閾值，而閾值的選定是很困難的，通常只是靠經驗與實驗來確定。本文的算法無須設定任何閾值，綜合利用了模板匹配二次差分和直方圖二次差分這兩個特征參數，用BP神經網絡來實現視頻鏡頭突變檢測，然后以閃光檢測來提高檢測的可靠性。與其他算法相比，該算法具有計算簡單、易于實現的優點，且檢測的查全率和精確率較高，實際應用中價值較大。但是算法沒有引入漸變檢測，這是今后要進一步研究的課題。
參考文獻：
［1］
HANJALIC A.Shot-boundary detection: unraveled and resolved[J].IEEE Circuits and Systems for Video Technology，2002，12(2):90-105.
[2]章毓晉，劉雨.基于內容的視覺信息檢索[M].北京:科學出版社，2003.
[3]張洪德，劉雨.一種改進的視頻切變檢測方法[J].電視技術，2002，2(10):14-16.
[4]KIKUKAWA T，KAWAFUCHI S.Development of an automatic summary editing system for the audio visual resources[J].Trans on Electronics and Information，1992，75-A(2):204-212.
[5]ZHANG H J，CHIEN Y L，SMOLIAR S W.Video parsing and browsing using compressed data[J]. Multimedia Tools and Applications，1995，1(1):89-113.
[6]GARGI U，KASTURI R，STRYER S H.Performance characterization of video-shot-change detection methods[J].IEEE Trans on Circuits and Systems for Vodeo Technology，2000，10(1):1-13.
[7]劉謙雷， 楊綠溪， 鄒采榮.用于視頻鏡頭突變切換檢測的二次差分法和像素點匹配二次差分法[J].中國圖象圖形學報，2003，8(2):161-168.
[8]CERNEKOVA Z，KOTROPOULOS C，PITAS I.Video shot segmentation using singular value decomposition[C]//Proc of International Conference on Multimedia and Expo.Washington DC:IEEE Computer Society，2003:301-302.
[9]YU Jun，SRINATH M D.An efficient method for scene cut detection[J].Pattern Recognition Letter，2001，22(13):1379-1391.
[10]BOCCIGNONE G，CHIANESE A，MOSCATO V，et al.Foveated shot detection for video segmentation[J].IEEE Trans on Circuits and Systems Video Technology，2005，15(3):365-377.
[11]潘磊，吳小俊，尤媛媛.基于聚類的視頻鏡頭分割和關鍵幀提取[J]. 紅外與激光工程，2005，34(3):341-344.
