基于改進(jìn)鏡頭邊界檢測(cè)算法的視頻檢索系統(tǒng)

鄒曉燕，殷 建

（山東大學(xué)威海分校 信息工程學(xué)院，威海 264209）

隨著多媒體技術(shù)和互聯(lián)網(wǎng)技術(shù)的發(fā)展，多媒體信息已逐漸成為信息處理領(lǐng)域中越來越重要的信息媒體形式。面對(duì)越來越龐大的網(wǎng)絡(luò)多媒體信息，要找到自己所需信息并非易事，而準(zhǔn)確地找到自己所需的信息則更是難上加難。為了便于人們快捷準(zhǔn)確地訪問多媒體信息，研究人員在過去的十幾年里已經(jīng)開展了大量的研究工作，主要集中在兩個(gè)方面：基于關(guān)鍵字的檢索和基于內(nèi)容的檢索。在基于文本的圖像檢索（Text-based Image Ret r ieval）中采用關(guān)鍵字標(biāo)識(shí)符方法描述信息線索，然后在索引時(shí)對(duì)標(biāo)簽進(jìn)行檢索。這樣一來對(duì)圖像的查詢變成了基于標(biāo)簽的查詢。這種傳統(tǒng)的方法雖然簡(jiǎn)單，但特定的標(biāo)簽只適合特定的查詢要求，并且沒有統(tǒng)一標(biāo)準(zhǔn)。此外這種方法不適用于大規(guī)模的數(shù)據(jù)集合。為了解決這個(gè)問題，基于內(nèi)容的視頻檢索受到了人們廣泛的關(guān)注。基于內(nèi)容的視頻檢索，就是由計(jì)算機(jī)來對(duì)視頻內(nèi)容進(jìn)行自動(dòng)分析，用戶可以通過提交樣例數(shù)據(jù)或者描述信息查找自己想要的視頻數(shù)據(jù)。

在基于內(nèi)容的檢索技術(shù)中，視頻結(jié)構(gòu)的基本單元是鏡頭。鏡頭定義為攝像機(jī)一次不間斷的拍攝。因此同一鏡頭內(nèi)的內(nèi)容具有一致性?；趦?nèi)容的視頻檢索的第一步工作就是從視頻流中找到鏡頭變換的邊界，從而對(duì)視頻流進(jìn)行切分以得到一個(gè)個(gè)的鏡頭，其效果的優(yōu)劣直接影響到視頻特征的提取、更高層結(jié)構(gòu)的描述以及視頻的瀏覽和檢索，因此，鏡頭分割在基于內(nèi)容的視頻檢索中有著重要的地位。鏡頭的變換是指兩個(gè)鏡頭之間的切換，從大類上分，可以分為突變和漸變兩大類。傳統(tǒng)的鏡頭分割算法對(duì)于鏡頭內(nèi)部閃光的誤檢率過高，或者不能同時(shí)檢測(cè)到鏡頭的突變和漸變。而本文提出的改進(jìn)的算法，即自適應(yīng)滑窗的雙閾值鏡頭檢測(cè)算法，可以很好地對(duì)兩種鏡頭轉(zhuǎn)變方式進(jìn)行識(shí)別，并且可以使鏡頭內(nèi)部閃光的誤檢率大大下降。

1 特征選擇

在視頻邊界檢測(cè)技術(shù)中，可以使用的視頻特性包括顏色、紋理、運(yùn)動(dòng)向量等。選取其中的一種則對(duì)視頻的描述不夠精確，檢索也容易出現(xiàn)大的誤差，選取過多的特性則會(huì)在數(shù)量級(jí)上加大計(jì)算量，極大地降低計(jì)算速度，因此，本文中我們選取顏色直方圖和紋理直方圖作為特征，一方面可以對(duì)全局顏色信息進(jìn)行描述，另一方面可以對(duì)圖像的局部紋理進(jìn)行刻畫。

1.1 HSV顏色空間

選取HSV顏色空間對(duì)顏色進(jìn)行H、S和V3個(gè)分量上的劃分，它符合人眼對(duì)顏色的識(shí)別模式。在這3個(gè)分量中，H是最重要的，因此劃分的時(shí)候，采取非等量化分，使用7∶2∶2的模型，從而得到一個(gè)28維顏色直方圖。

1.2 紋理譜描述子

本文使用紋理譜描述子來描述紋理。對(duì)于圖像中的每一個(gè)像素，使用一個(gè)3×3的矩陣I來描述它的紋理模式，I的計(jì)算公式如式（1）：

為了降低計(jì)算難度，將矩陣I映射成一個(gè)[0,255]之間的值T，公式如式（2）：

其中，G 為變換系數(shù)矩陣。

這樣，可以將3×3的區(qū)域紋理模式轉(zhuǎn)化到[0,255]之間的一個(gè)值。具有視覺一致性的多種紋理模式將分類成為同一種紋理模式，這樣紋理直方圖的維度就降低很多，為后續(xù)的計(jì)算節(jié)省了不少資源而精確度上卻沒有較大的損失。視覺一致性定義： 對(duì)于任意兩個(gè)紋理模式A和B，如果通過旋轉(zhuǎn)（0°，90°，180°或360°），翻轉(zhuǎn)（水平，垂直，主對(duì)角線或副對(duì)角線）等變換，A可以轉(zhuǎn)換為B，則認(rèn)為A和B 具有視覺一致性，劃分為同一紋理模式類。最終，可以得到51種紋理模式類。

1.3 二維聯(lián)合直方圖

使用顏色和紋理兩種特征，可以得到28×51維的二維聯(lián)合直方圖。設(shè)隨機(jī)變量C代表顏色分量，隨機(jī)變量T代表紋理分量，則Pi,j=P(C=ci,T=tj)代表聯(lián)合分布公式。通過該公式即可得到聯(lián)合分布直方圖。單一特征直方圖可以通過二維聯(lián)合直方圖的邊緣分布得到。對(duì)于兩個(gè)二維分布直方圖Hx和Hy，其相似度可以用兩個(gè)直方圖的交來表示，公式如式（4）：

而兩個(gè)直方圖的距離，也就是幀間差，可以用1－Inner(Hx, Hy)來表示。

2 傳統(tǒng)滑動(dòng)窗口鏡頭邊界檢測(cè)算法

定義一個(gè)長(zhǎng)度為2R+1的窗口，使要檢測(cè)的幀位于次窗口的正中。計(jì)算前后兩幀的幀間差差值，設(shè)Di為待檢測(cè)幀的幀間差差值，則當(dāng)Di滿足下列條件時(shí)認(rèn)為待檢測(cè)幀處為突變位置：

（1）Di是2R+1窗口中的最大值。

（2）設(shè)窗口中的第2大幀間差為D2，且Di＞k·D2。

傳統(tǒng)的滑動(dòng)窗口法主要用于鏡頭突變的檢測(cè)。它可以有效的減少因全局閾值選取不當(dāng)而造成的漏檢。但是由于其判斷準(zhǔn)則較為簡(jiǎn)單，會(huì)造成較大的漏檢和誤檢。

3 傳統(tǒng)雙閾值鏡頭邊界檢測(cè)算法

傳統(tǒng)的雙閾值法是一種經(jīng)典的通用鏡頭檢測(cè)方法，可以檢測(cè)出突變鏡頭和漸變鏡頭。根據(jù)前面滑動(dòng)窗口算法對(duì)突變鏡頭檢測(cè)的介紹，當(dāng)前后兩幀的幀間差超過閾值時(shí)，則認(rèn)為此處有一個(gè)突變，可將此方法推廣到漸變檢測(cè)中。幀間差在漸變處要比在鏡頭內(nèi)部高，但比在突變處要低很多。為此，需要設(shè)置高低兩個(gè)閾值TH和TL。順序考察幀間差，如果超過了TH，就認(rèn)為是檢測(cè)到一個(gè)突變。如果沒有超過TH，但超過了TL，就認(rèn)為檢測(cè)到了一個(gè)可能的漸變起始幀，并繼續(xù)向后檢測(cè)，如果仍超過TL，則將幀間差累加，直至幀間差低于TL。若此時(shí)累計(jì)的幀間差超過了TH，則認(rèn)為是檢測(cè)到漸變的結(jié)束幀，否則認(rèn)為剛才那些超過TL的幀間差是由于其他原因（如光照變化和運(yùn)動(dòng)等）造成的，不是漸變。這個(gè)過程如圖1。

圖1 雙閾值法鏡頭檢測(cè)示意圖

4 改進(jìn)的基于滑動(dòng)窗口和雙閾值的鏡頭邊界檢測(cè)算法

傳統(tǒng)的雙閾值算法可以同時(shí)檢測(cè)突變和漸變，具有算法簡(jiǎn)單，計(jì)算量小等優(yōu)點(diǎn)。但是其檢測(cè)效果依賴于閾值的設(shè)定。本文通過統(tǒng)計(jì)當(dāng)前窗口內(nèi)的平均幀間差，從而動(dòng)態(tài)設(shè)定閾值，提高了算法的靈活性和適應(yīng)性。具體算法如下：

（1）輸入：高閾值因子FH，低閾值因子FL，初始窗口寬度w， 二次檢測(cè)長(zhǎng)度l，幀間差計(jì)算函數(shù)fradif(i,j)，整個(gè)視頻的幀間差序列FraDif={d1, d2, …, dn}。

（2）輸出： 鏡頭邊界序列n1, n2, …, nm。

。對(duì)于每個(gè)幀間差di做如下判斷：

（1） 如果di>TH，則說明可能發(fā)生了突變。以當(dāng)前幀為中心，取長(zhǎng)度大小為l的窗口，計(jì)算該窗口幀間差序列的均。

（2）如果diTL，則假定出現(xiàn)漸變，設(shè)置漸變標(biāo)志。記錄下當(dāng)前幀位置作為候選鏡頭邊界，并開始累計(jì)幀間差FraDiffSum。

（3）如果diTH，則說明漸變可能發(fā)生，需進(jìn)一步檢測(cè)。假定漸變發(fā)生，設(shè)漸變開始幀為s t ar t，漸變結(jié)束幀為end，計(jì)算。如果，則認(rèn)為發(fā)生了漸變，并記錄當(dāng)前漸變位置。否則認(rèn)為沒有發(fā)生漸變，取消漸變標(biāo)記并清零FraDiffSum。

如果判斷發(fā)生了鏡頭切換，則需要重新設(shè)定窗口并計(jì)算幀間差平均值：。如果沒有發(fā)生鏡頭變化，設(shè)當(dāng)前鏡頭開始位置為start，取w=max(w,i－start)，調(diào)整閾值。根據(jù)設(shè)定高閾值，設(shè)定低閾值。

在算法的最后，所有幀處理完畢后，輸出鏡頭邊界序列n1, n2, …, nm。

改進(jìn)的算法主要是改變了自適應(yīng)閾值TH和TL的確定方式。在算法中，設(shè)定窗口寬度w小于一個(gè)鏡頭長(zhǎng)度（可設(shè)定為視頻的fps值）。這樣每一個(gè)鏡頭的閾值由該鏡頭內(nèi)的幀間差動(dòng)態(tài)確定。不同的鏡頭，其內(nèi)部的活動(dòng)度不一樣，活動(dòng)度與平均幀間差、閾值成正比。由鏡頭本身確定的平均幀間差和閾值才能夠正確地檢測(cè)出鏡頭的變化。另外在檢測(cè)出鏡頭邊界后，需要提取鏡頭的前后l幀進(jìn)行鏡頭邊界的確認(rèn)。這樣能夠有效地避免因?yàn)殚W光等原因造成的誤檢。

5 實(shí)驗(yàn)與討論

5.1 鏡頭邊界檢測(cè)算法的評(píng)價(jià)標(biāo)準(zhǔn)

綜合考慮正確檢測(cè)數(shù)、漏檢數(shù)和誤檢數(shù)，檢測(cè)一個(gè)鏡頭邊界檢測(cè)算法是否有效。

5.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中，共選取了2段視頻片段，16 402幀，合計(jì)突變鏡頭52個(gè)，漸變鏡頭13個(gè)。分別采用傳統(tǒng)滑動(dòng)窗口鏡頭檢測(cè)算法(A)、傳統(tǒng)雙閾值鏡頭邊界檢測(cè)算法(B)和本文提出的改進(jìn)算法(C)進(jìn)行了突變鏡頭的檢測(cè)并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行比較，如表1。

表1 算法運(yùn)行結(jié)果比較表

由表1可見，傳統(tǒng)滑動(dòng)窗口鏡頭檢測(cè)算法的漏檢誤檢現(xiàn)象比較嚴(yán)重。傳統(tǒng)雙閾值鏡頭邊界檢測(cè)算法效果要好于傳統(tǒng)滑動(dòng)窗口鏡頭檢測(cè)算法，相比之下，本文提出的改進(jìn)算法能夠較好地避免漏檢和誤檢。由于本算法對(duì)檢測(cè)到的鏡頭邊界進(jìn)行了第2次驗(yàn)證，因此可以有效避免由閃光造成的誤檢。

5.3 使用改進(jìn)算法實(shí)現(xiàn)的視頻檢索系統(tǒng)

本文使用Visual C#和SQL2000實(shí)現(xiàn)了一個(gè)基于本文提出算法的視頻分割檢索系統(tǒng)。系統(tǒng)分為視頻分割部分和視頻檢索部分。首先對(duì)視頻進(jìn)行分割，同時(shí)在視頻中抓取要查找的圖像，然后讓系統(tǒng)動(dòng)態(tài)查找與該幅圖像相似度最高的關(guān)鍵楨圖像。根據(jù)實(shí)驗(yàn)結(jié)果可知，該改進(jìn)算法快速有效。

6 結(jié)束語

通過使用顏色紋理等特征并對(duì)視頻采用本文提出的方法進(jìn)行鏡頭檢測(cè)，實(shí)驗(yàn)結(jié)果表明，本文提出的算法較之傳統(tǒng)算法在精確度和效率上有了較大的改進(jìn)。

[1]肖莎莉，周昌國(guó)，唐岳霖. 基于DirectShow的鏡頭邊界檢測(cè)系統(tǒng)[J]. 重慶大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2006，29（1）.

[2]孫季豐，李穎雄. 視頻鏡頭自動(dòng)分割的若干方法[J]. 華南理工大學(xué)學(xué)報(bào)， 2003，31（8）.

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