視頻鏡頭分割算法綜述

劉艷紅

摘 要：視頻鏡頭分割作為視頻處理的第一步和關(guān)鍵幀提取的基礎(chǔ)，一直受到研究者的關(guān)注和重視，近二十年來已經(jīng)提出了大量的算法。文章首先對幾種典型的視頻鏡頭分割算法做了綜述，比較了它們之間的優(yōu)缺點，然后又介紹了兩種新的視頻鏡頭分割算法，最后對視頻鏡頭分割算法研究做了展望。

關(guān)鍵詞：鏡頭分割；視頻檢索；直方圖

1 引言

隨著科學技術(shù)的發(fā)展，視頻等多媒體格式的信息數(shù)據(jù)越來越豐富。面對龐大的視頻信息，如何建立一個簡便、快速、精確的視頻檢索系統(tǒng)就成為近年來的一個熱門課題[1]。對視頻檢索系統(tǒng)的研究具有十分重要的應(yīng)用意義。例如，電視新聞時時刻刻都在產(chǎn)生大量視頻數(shù)據(jù)的電視節(jié)目，這些節(jié)目又劃分為軍事、政治、娛樂、體育等。通過對各個節(jié)目進行分類、歸納、整理，建立對應(yīng)的視頻檢索系統(tǒng)，將會為人們的使用提供很大方便[2]。又如，近年來，足球作為一項全球性的運動，被越來越多的人們所關(guān)注，但由于各方面的原因，人們無法觀看完整的賽事，因此足球視頻精彩鏡頭的研究也具有很重要的現(xiàn)實意義，而這也同樣離不開視頻檢索系統(tǒng)[3]。

視頻鏡頭分割作為視頻檢索的第一步，也是隨后關(guān)鍵幀提取的基礎(chǔ)，它的準確與否直接影響到后續(xù)的處理效果。因此，對視頻鏡頭分割的研究就顯得尤為重要。

文章首先就現(xiàn)有的視頻鏡頭分割算法進行了分類，并總結(jié)了各個算法的優(yōu)缺點，接著介紹了兩種改進了的視頻鏡頭分割算法，最后對視頻鏡頭分割算法研究做了展望。

2 視頻鏡頭分割的典型算法

視頻鏡頭分割算法的研究已經(jīng)開展了很多年了，許多學者提出了各自的方案，對視頻鏡頭分割做了很多有益的研究和探討。各種視頻鏡頭分割算法各有所長，從不同的角度來提高視頻鏡頭邊緣的檢測效率。視頻鏡頭分割總體來說分為：像素比較法、直方圖比較法、邊緣比較法、塊匹配法[4]。下面就這幾種典型的視頻鏡頭分割算法做一個詳細的分析和比較。

2.1 像素比較法

當視頻從一個鏡頭切換到另一個鏡頭的時候，相鄰圖像幀的對應(yīng)像素的差值會發(fā)生很大的變化，當這個差值大于設(shè)定好的某一閾值時，我們就說鏡頭發(fā)生了轉(zhuǎn)變，這就是像素比較法的基本原理[5]。

像素比較法的幀間差定義為：

其中k與k+1是連續(xù)的兩個視頻幀，M、N分別是圖像幀的寬度和高度，Pk（i，j）是第k幀在像素點（i，j）的像素值。當D（k，k+1）大于設(shè)定閾值時說明第k幀和第k+1幀之間產(chǎn)生了鏡頭切換，即為鏡頭的邊界。

經(jīng)過分析，影響圖像的像素變化主要因素有：攝像機的運動、視頻對象的運動、閃光燈以及變焦等。另外，當發(fā)生漸變時，過渡效果對像素變化的影響也會比較嚴重[6]。

總的來說，像素比較法的原理簡單、便于實現(xiàn)，但是若單純的利用它來進行鏡頭分割的話效果是不太理想的。

2.2 直方圖比較法

直方圖比較法是比較相鄰兩幀圖像的直方圖差值，從而來進行鏡頭邊界的檢測，這種方法的考量是依據(jù)圖像幀的全局特征。

直方圖比較法通常是將每一幀圖像的亮度、灰度、顏色劃分為N個等級，統(tǒng)計每個等級中各個像素點的個數(shù)，繪制成直方圖。設(shè)圖像幀的總像素為M，灰度級為N，具有k級灰度的像素有fk個，它出現(xiàn)的頻率為

其中，設(shè)顏色區(qū)間分為N個，fi，k是第i幀中第k個顏色區(qū)間的像素個數(shù)。

因為同一個鏡頭中相鄰幀間的直方圖差異不是很大，而不同鏡頭之間的相鄰幀間的直方圖差異較大，因此通過比較相鄰幀之間的直方圖差異就可以實現(xiàn)視頻鏡頭的分割[7]。

大體上來說，直方圖比較法具有有效的抗干擾能力，并且計算復(fù)雜度低，實現(xiàn)簡單，效率高，鏡頭分割效果較好，但是直方圖不能反映圖像的空間特性，若出現(xiàn)兩幅具有不同結(jié)構(gòu)卻有相同顏色的直方圖時，就會造成誤檢。

2.3 邊緣比較法

邊緣比較法是利用圖像的邊緣特征來實現(xiàn)視頻鏡頭的分割。當鏡頭發(fā)生變化時，整個畫面的內(nèi)容發(fā)生了變化，因此對應(yīng)的圖像邊緣也發(fā)生了變化，邊緣比較法就是利用舊邊緣的消失和新邊緣的出現(xiàn)來實現(xiàn)視頻鏡頭的分割[8]。

具體原理是，設(shè)定一個閾值T，檢測第i幀與第i+1幀中最近邊緣的距離大于給定閾值T的邊緣像素數(shù)目的百分比（din），第i+1幀中與第i幀中最近邊緣的距離大于給定閾值T的邊緣像素數(shù)目的百分比（dout），計算第i幀與第i+1幀的幀間差（diff）：

diff=max（din，dout） 公式4

如果幀間差（diff）大于設(shè)定的閾值T1，則認為此處發(fā)生了視頻鏡頭的切換。

邊緣比較法對視頻鏡頭分割的檢測準確度相對來說比較高，但是計算過于繁瑣且數(shù)據(jù)量比較大，而且當邊緣不明顯時，檢測效果不理想。

2.4 塊匹配法

塊匹配法是將每幀圖像分割成若干個小塊，然后在比較相應(yīng)塊的相似程度來確定鏡頭的邊界，若相鄰幀對應(yīng)的不相似塊數(shù)比較多，則認為出現(xiàn)了視頻鏡頭的分割[9]。

把圖像分成m個小塊，小塊內(nèi)比較的閾值T1，相似塊數(shù)的閾值為T2，第i幀和第i+1幀對應(yīng)塊的相似比例？姿k計算方法如下：

其中，？滋k，i、？滋k，i+1分別是第i幀和第i+1幀中第m塊的像素平均值，？滓k，i、？滓k，i+1是第i幀和第i+1幀中第m塊的像素標準差。如果塊的相似比例？姿k大于閾值T1，則認為這兩個塊不相同。累計并記錄不同的塊數(shù)n，如果n大于閾值T2，則認為發(fā)生鏡頭切換。

塊匹配法與像素比較法相比降低了小塊內(nèi)噪聲的影響，但是因為分成了多個塊增加了計算量，給計算帶來了不便。

3 改進的視頻鏡頭分割算法

通過介紹典型的視頻鏡頭邊緣檢測算法，可以發(fā)現(xiàn)，鏡頭邊緣檢測算法的實質(zhì)就是：如何找到一種良好的視頻圖像特征，判斷相鄰圖像幀之間的特征是否發(fā)生了劇烈變化，從而來完成視頻鏡頭邊緣的檢測，實現(xiàn)鏡頭分割[10]?？紤]到典型算法都有優(yōu)缺點，如果能設(shè)計一種算法，去掉它們的缺點、綜合它們的優(yōu)點的話就可以大大提高視頻鏡頭分割的效率。下面就兩個改進了的視頻鏡頭分割算法進行簡單介紹。

3.1 基于顏色空間的自適應(yīng)閾值鏡頭分割算法

YUV顏色空間是一種最常用的顏色空間，不論是非壓縮視頻還是壓縮視頻都可以直接獲取。其中“Y”表示明亮度（Luminance或Luma），也就是灰階值；而“U”和“V”表示的則是色度（Chrominance或Chroma），作用是描述影像色彩及飽和度，用于指定像素的顏色。YUV顏色空間可以通過公式由RGB顏色空間得到。由于視頻內(nèi)容具有連續(xù)性，所以即便不在一個鏡頭內(nèi)的相鄰幀它們的色度分量U、V相差也不會很大，但是亮度分量Y會隨著鏡頭的切換發(fā)生變化，因而可以用亮度分量Y作為判斷鏡頭是否突變的主要依據(jù)。在YUV顏色空間中，Y和U、V分量是可以分離的，這樣就減少了大量的運算量[11]。

算法的具體思路是，首先要對相鄰幀幀差值進行計算。在統(tǒng)計直方圖時，會使視頻幀原有的像素點位置信息丟失，從而很難反應(yīng)視頻的空間信息。為了解決這個問題，采用了分塊直方圖?？紤]到一般視頻的內(nèi)容主要集中在視頻幀中心，而底部或頂部通常是廣告或字幕的變化，因此將視頻幀沿垂直和水平方向分別分割為3：5：3。

計算出相鄰幀對應(yīng)子塊的直方圖差值：

Minus_framei=|Y_valuek+1-Y_valuek| 公式6

這里的Y_valuek為當前幀子塊的Y分量直方圖，Y_valuek+1為下一幀對應(yīng)子塊Y分量的直方圖。根據(jù)每塊的重要程度，設(shè)置不同的權(quán)值，根據(jù)設(shè)定的加權(quán)矩陣W，得到相鄰兩幀之間的亮度分量Y的直方圖差值：

然后獲取自適應(yīng)閾值。由于處于同一鏡頭內(nèi)的相鄰兩幀在內(nèi)容上基本一致，因此它們之間的直方圖差值比較小。當發(fā)生鏡頭突變時，亮度分量Y的直方圖幀差值變化明顯要比同一鏡頭內(nèi)所有幀的平均幀差值大很多[12]，所以可以利用這個原理作為檢測鏡頭是否發(fā)生突變轉(zhuǎn)換的依據(jù)。鏡頭漸變是通過亮度的不斷變化來實現(xiàn)的，表現(xiàn)為在連續(xù)多幀內(nèi)相鄰幀差值變化較大，可以利用此點來檢測鏡頭是否發(fā)生漸變轉(zhuǎn)換。經(jīng)過大量的實驗對比，來確定閾值。

最后進行判斷，如果幀差值大于突變自適應(yīng)閾值，轉(zhuǎn)入突變檢測模塊；如果幀差值處于突變閾值和漸變閾值之間的話，轉(zhuǎn)入漸變幀檢測模塊；如果當前幀不是本段視頻最后一幀的話，檢測下一幀，直到結(jié)束。

通過查全率和查準率可以看出算法檢測效果比較好。采用YUV顏色空間，方便于亮度分量的提取，分塊上采用了不均勻分塊并且運用不同的權(quán)值，計算各個幀的直方圖亮度分量Y 的值，在閾值的計算中體現(xiàn)了自適應(yīng)性，但是計算復(fù)雜度比較高，并且當視頻出現(xiàn)閃光燈效果時，會出現(xiàn)誤檢。

為了解決這個問題，通過觀察，發(fā)現(xiàn)閃光燈前后的幀間差一般相差不大，而當發(fā)生鏡頭突變時，突變前后的幀間差都比較大。因此可以通過計算隔幀圖像的相關(guān)性來區(qū)分閃光燈和鏡頭突變。

當檢測出某幀可能發(fā)生鏡頭突變時，計算在該位置的前N幀和后N+1幀的幀間差d（fi-N，fi+N+1），將其與該幀的相鄰幀間差d（fi，fi+1）進行對比。如果二者的比值接近1，則表示位置i發(fā)生鏡頭突變，否則為閃光燈影響。因為閃光燈可能持續(xù)數(shù)幀，因此可以增加步長N來計算幀間差，使得相隔2N+1幀后恰好跳過閃光持續(xù)的幀[13]。

我們可以看出，此算法雖然整體是按照直方圖比較法來實現(xiàn)的，但為了提高算法的效率，在進行直方圖比較時增加了分塊思想，使得算法的檢測精準度有了大大提高。并且在閾值的設(shè)定上，采用了自適應(yīng)閾值提取法，使得算法更智能化。

3.2 基于HCR的視頻鏡頭分割

目前提出的很多鏡頭分割算法，對于鏡頭突變的檢測基本上都能達到預(yù)期效果，但是對于鏡頭漸變的檢測效果不是很理想。一些分割算法如運動估計、光流分析、運動建模等，雖然分割效果好，但是計算復(fù)雜，這些在實際運用中不是很方便[14]。因此提出了基于HCR的視頻鏡頭分割算法，該算法的具體步驟為：

首先，將RGB顏色空間轉(zhuǎn)換到HSV顏色空間，按L=4×H+S計算該幀的HS值，用Hcur、Hshot分別代表當前幀HS直方圖和當前鏡頭HS直方圖。得出當前幀Hcur直方圖，且Hshot=Hcur，并將當前鏡頭內(nèi)已有幀數(shù)len賦初值為1；計算下一幀的Hcur，并根據(jù)公式

更新鏡頭特征Hshot；否則，作為候選鏡頭邊界。此時需要進一步判斷當前鏡頭內(nèi)的視頻幀數(shù)len是否大于閾值T2；如果len>T2則認為檢測到鏡頭邊界，記錄當前盡頭結(jié)束位置并進行下一幀的檢測，直到視頻結(jié)束。

通過分析我們可以得出，此算法的物理意義就是當前檢測鏡頭內(nèi)所有幀的顏色直方圖的平均值，用當前幀的顏色直方圖值和鏡頭的顏色直方圖的平均值計算出HCR，不再以相鄰幀或者非相鄰幀之間距離作為邊界檢測的依據(jù)，而是用HS直方圖作為當前幀和當前鏡頭的特征，具有一定的合理性和準確性，但是在視頻較為復(fù)雜的時候，會出現(xiàn)一定的誤檢和漏檢，誤檢的原因是在漸變過程中會有過渡，閾值的設(shè)定不好把控，漏檢的原因是因為只用一種顏色信息造成的。

4 總結(jié)及展望

雖然對視頻鏡頭分割算法的研究已經(jīng)有很多年了，但總的來說能得到大家一致認同的算法卻仍然沒有。因此，我們在分析解決具體問題的時候就應(yīng)該選擇合適的算法。例如在進行新聞或體育類視頻的鏡頭檢索時，考慮到此類視頻的切換方式大多是突變，我們就可以選擇針對鏡頭突變檢測效果比較好的算法；而在一些MV和電影的視頻中，鏡頭漸變的切換方式運用的比較多，這個時候，我們應(yīng)該選擇側(cè)重于檢測鏡頭漸變的算法。

通過總結(jié)以前的視頻鏡頭分割算法，發(fā)現(xiàn)對視頻鏡頭的突變檢測的研究相對來說比較成熟，并且效果也比較好，但是對漸變的檢測效果就不盡如人意，所以對視頻鏡頭漸變的檢測將仍然是研究的重點。并且隨著三網(wǎng)融合的發(fā)展，作為視頻檢索的基礎(chǔ)技術(shù)之一的視頻鏡頭分割將成為一項重要的技術(shù)[15]。

參考文獻

[1]錢剛，曾貴華.典型視頻鏡頭分割方法的比較[J].計算機工程與應(yīng)用，2004，32.

[2]劉嘉琦，封化民.基于多模態(tài)特征融合的新聞故事單元分割[J].計算機工程，2012，12.

[3]段富，朱偉.視頻存儲中一種改進的鏡頭分割算法[J].微機計算機信息，2009，25（73）.

[4]Tsamoura E，Mezaris V，Kompatsiaris I.Gradual transition detection using color coherence and other criteria in a video shot meta-segementation framework.IEEE，2008：45-49.

[5]Jorge S，Narayanan，Shrikanth S.Discriminative Wavelet Packet Filter Bank Selection for Pattern Recognition[J].IEEE Transactions on Signal Processing，2009，57（5）：1796-1810.

[6]丁洪麗，陳懷新.基于累積直方圖的視頻鏡頭邊界檢測方法[J].電訊技術(shù)，2008，48（3）.

[7]Ercelebi E，Koc S.Lifting-based wavelet domain adaptive Wiener filter for image enhancement[J].IEEE proceedings.Vision，image and signal processing，2006，153（1）：31-36.

[8]秦劍鵬，符茂勝.基于顏色直方圖變化率的視頻鏡頭檢測[J].計算機應(yīng)用與軟件.2011，4.

[9]Lefever S，incent V.Efficient and robust shot change detecion[J].Springer，207，2（1）：23-34.

[10]Brechet L，Lucas M F，Doncarli C，et al.Compression of Biomedical Signals With Mother Wavelet Optimization and Bese-Basis Wavelet Packet Seletion[J].IEEE Transactions on Biomedical Engineering，2007，54（12）：2186-2192.

[11]潘磊，吳小俊.基于聚類的視頻鏡頭分割和關(guān)鍵幀提取[J].紅外與激光工程，2005，34（3）.

[12]汪翔，羅斌.基于顏色空間的自適應(yīng)閾值鏡頭分割算法[J].計算機技術(shù)與發(fā)展.2012，9.

[13]田玉民，吳自力.基于幀間聯(lián)合直方圖幀差的鏡頭邊界檢測算法[J].計算機應(yīng)用，2008，21（10）.

[14]巢娟，孫琰鋒.基于雙重檢測模型的視頻鏡頭分割算法[J].上海交通大學學報，2011，10.

[15]張玉珍，楊明.基于運動補償和自適應(yīng)雙閾值的鏡頭分割[J].計算機科學，2010，9.