常虹，張明（上海海事大學(xué)信息工程學(xué)院，上?！?01306）

一種基于支持向量機(jī)的鏡頭邊界檢測(cè)算法

常虹，張明
（上海海事大學(xué)信息工程學(xué)院，上海201306）

以往鏡頭邊界檢測(cè)對(duì)閾值的依賴(lài)性很大，提出一種基于支持向量機(jī)的鏡頭邊界檢測(cè)算法來(lái)避免對(duì)鏡頭檢測(cè)閾值的依賴(lài)。該算法利用SVM對(duì)視頻數(shù)據(jù)進(jìn)行分析和處理，把從視頻像素幀中提取的特征數(shù)據(jù)作為支持向量機(jī)的輸入數(shù)據(jù)，從而把鏡頭邊界檢測(cè)問(wèn)題轉(zhuǎn)化成分類(lèi)問(wèn)題。有效地將鏡頭邊界檢測(cè)跟機(jī)器學(xué)習(xí)的方法結(jié)合起來(lái)，實(shí)驗(yàn)表明這種方法對(duì)鏡頭邊界檢測(cè)的切變檢測(cè)有很好的檢測(cè)效果。

視頻檢索；鏡頭邊界檢測(cè)；支持向量機(jī)

0　引言

鏡頭邊界檢測(cè)在研究基于內(nèi)容檢索、視頻數(shù)據(jù)庫(kù)及視頻處理和利用上具有十分重要的作用?，F(xiàn)有的視頻鏡頭邊界檢測(cè)算法大多是基于視頻幀間的內(nèi)容變化的。通常把具有較明顯的連續(xù)差異比較大的相鄰兩幀看作視頻鏡頭的邊界。鏡頭邊界分為突變和漸變。為了有效地分割鏡頭定義了連續(xù)兩幀圖像的相似性特征量。如果相鄰兩幀相似性較大，就認(rèn)為兩幀位于同一個(gè)鏡頭中，如果相鄰兩幀相似性很小，就認(rèn)為在這兩幀間發(fā)生了鏡頭突變。鏡頭檢測(cè)的整個(gè)過(guò)程可以分為3個(gè)階段［1］：（1）提取特征；（2）構(gòu)造幀間差值；（3）鏡頭邊界檢測(cè)。視頻鏡頭邊界檢測(cè)算法的分類(lèi)可以按照其使用的幀間差別特征進(jìn)行分類(lèi)，也可以按照算法的應(yīng)用對(duì)象進(jìn)行分類(lèi)。還有些算法按照視頻是否壓縮進(jìn)行分類(lèi)，大部分算法是用于像素域的視頻鏡頭檢測(cè)。像素域中的鏡頭邊界檢測(cè)方法主要有：基于像素塊比較的方法；基于像素比較的方法；全局直方圖比較的方法；基于模型分割等的方法。在鏡頭邊界檢測(cè)的方法中，早期主要采用固定閾值的方法［2］，但固定閾值的鏡頭邊界檢測(cè)對(duì)于閾值的設(shè)定過(guò)于敏感。除非選取恰當(dāng)?shù)膱D像特征計(jì)算出來(lái)的自適應(yīng)閾值。近些年，有許多機(jī)構(gòu)和研究者用機(jī)器學(xué)習(xí)的方法進(jìn)行鏡頭邊界檢測(cè)，如Lee等［3］人提出利用壓縮域中特征，并結(jié)合神經(jīng)網(wǎng)絡(luò)進(jìn)行鏡頭邊界檢測(cè)，取得不錯(cuò)的效果，AT&T利用像素域中提取的圖像特征，結(jié)合有限狀態(tài)機(jī)進(jìn)行鏡頭邊界檢測(cè)。因此，用機(jī)器學(xué)習(xí)的方法進(jìn)行鏡頭邊界檢測(cè)是目前的一種很具有研究?jī)r(jià)值的發(fā)展趨勢(shì)。

本文提出一種改進(jìn)的基于支持向量機(jī)的鏡頭邊界檢測(cè)算法。首先提取HSV顏色空間中的顏色直方圖和紋理特征算子組合成的特征算子作為特征數(shù)據(jù)，其后結(jié)合支持向量機(jī)進(jìn)行鏡頭邊界檢測(cè)。本文首先介紹了鏡頭檢測(cè)過(guò)程中用到的顏色空間轉(zhuǎn)換和幀間差值的計(jì)算方法，在此基礎(chǔ)上設(shè)計(jì)了基于支持向量機(jī)的鏡頭切變識(shí)別算法。最后給出TREVID 2007數(shù)據(jù)集上的測(cè)試結(jié)果。該算法的實(shí)驗(yàn)結(jié)果與TREVID 2007公布的評(píng)測(cè)結(jié)果進(jìn)行對(duì)比后，鏡頭邊界檢測(cè)準(zhǔn)確率有了明顯提高，試驗(yàn)結(jié)果表明了該算法的有效性。

1　顏色模型轉(zhuǎn)換和幀間差值的計(jì)算

1.1顏色模型轉(zhuǎn)換

HSV顏色模型

HSV顏色模型是色調(diào)（H，Hue）、飽和度（S，Saturation）、亮度（V，Value）三個(gè)英文單詞的首字母縮寫(xiě)［4］，這一點(diǎn)與RGB顏色空間模型類(lèi)似，然而HSV顏色模型與人類(lèi)視覺(jué)的特點(diǎn)更相符，其模型采用上述三個(gè)方面來(lái)描述現(xiàn)實(shí)世界中各種各樣的顏色。在一幅圖像中，色調(diào)代表圖像顏色的一個(gè)總體傾向，可以是各種各樣的顏色，包含紅色、綠色、藍(lán)色等；所謂飽和度，是指一幅圖像中圖像色彩的鮮艷程度；而亮度則是指圖像所具有顏色的明亮程度的反映。

由于HSV顏色模型具備有線(xiàn)性伸縮性的性質(zhì)，所以人們比較傾向于HSV顏色模型所描述的顏色［5］。然而在一般情況下，我們得到的圖像絕大部分都采用RGB顏色空間模型來(lái)進(jìn)行描述，由此需要把RGB顏色空間轉(zhuǎn)換成HSV顏色空間。在轉(zhuǎn)換公式中，r，g，b的取值是從0到255。h采用弧度制來(lái)進(jìn)行表示，其范圍為0度到360度，s，v的取值是0到1，h，s，v是通過(guò)非線(xiàn)性變換得到的如下：

1.2圖像特征提取

為了能有效進(jìn)行基于SVM的分類(lèi)，選取合適的分類(lèi)特征參數(shù)也是很重要的。目前，較普遍的使用方法是顏色直方圖，本文選用一種將每一幀的HSV顏色空間中的顏色直方圖和紋理特征因子組合而成的特征因子作為視覺(jué)特征。

（1）紋理特征

在對(duì)圖像幀處理的過(guò)程中，如果僅僅是以顏色特征作為特征提取的參數(shù)，對(duì)于種類(lèi)繁多的視頻資源來(lái)說(shuō)，顯得過(guò)于單一，所以，本文在原本的顏色特征的基礎(chǔ)上，引入紋理特征算子。

本文利用LBP［6］（局部二值模式）紋理特征描述算子來(lái)對(duì)幀圖像的紋理特征進(jìn)行處理。LBP描述算子具有的灰度不變和旋轉(zhuǎn)不變的性質(zhì)很巧妙的避免了由光照或閃光顯著改變而引起的實(shí)驗(yàn)結(jié)果的誤差。

LBP算子的主要思想是選取區(qū)域的中心像素并把它的灰度值設(shè)為閾值，然后，再對(duì)周?chē)鷪A形鄰域內(nèi)的像素進(jìn)行二值化處理，也就是將周?chē)霃綖镽的圓形鄰域內(nèi)的像素灰度值與閾值作比較，若像素值大于閾值則此鄰域的像素值為1，反之為0，由此可得一串二進(jìn)制的值，最后對(duì)不同位置的像素值進(jìn)行加權(quán)求和，就可以得到該區(qū)域的LBP值。表示半徑為R的圓形鄰域內(nèi)存在P個(gè)像素點(diǎn)。

圖1　基本的LBP算子計(jì)算示意圖

用公式可以表示為：

其中，P表示半徑為R的圓形鄰域內(nèi)存在P個(gè)像素點(diǎn)。bi為像素點(diǎn)的像素值，bc為中心點(diǎn)的像素值.。若bi-bc的值大于0，則s（x）的值為1，反之，s（x）值為0。

（2）顏色直方圖

本文研究過(guò)程中，必需對(duì)整個(gè)HSV顏色模型進(jìn)行量化，量化之后再進(jìn)行后續(xù)計(jì)算，以便有效降低計(jì)算量。本文選擇對(duì)HSV顏色空間進(jìn)行非等間隔的量化，分色調(diào)H為8份，飽和度S和亮度V為3份，采用的公式如下：

經(jīng)過(guò)量化之后，依據(jù)如下方法將H、S、V合成一個(gè)一維矢量，這樣就把HSV顏色空間劃分為72種顏色，然后就可以進(jìn)行特征提取了：

首先進(jìn)行顏色直方圖的提取，顏色直方圖反映了一幅圖像中像素顏色出現(xiàn)的概率，是一種概率統(tǒng)計(jì)，計(jì)算公式如下：

上式中，Wi（k）指的是第i幅圖像的第k種顏色集合出現(xiàn)的概率，Dk指的是第k種顏色集合，圖像中的像素點(diǎn)用M和N表示，即圖像有M行N列，表示了這幅圖像的大小。

1.3幀間差值計(jì)算

在鏡頭邊界檢測(cè)算法中，非常普遍的使用方法是顏色直方圖法，它是分別對(duì)兩幅相鄰的圖像進(jìn)行顏色直方圖提取，再對(duì)兩者的直方圖進(jìn)行歸一化，計(jì)算兩幅相鄰圖像的幀間差，換句話(huà)說(shuō)就是計(jì)算直方圖間的相似性，最后通過(guò)差值比較的方法來(lái)對(duì)鏡頭的邊界進(jìn)行判斷。

因?yàn)楸疚氖抢妙伾卣骱图y理特征共同來(lái)對(duì)幀圖像進(jìn)行描述［7］，所以，兩幀之間的相似度可以用二者差值來(lái)表示。在本文中，首先計(jì)算兩幀圖像之間的顏色直方圖的差值，再計(jì)算兩幀圖像之間的LBP紋理算子的差值，再將這兩個(gè)差值進(jìn)行加權(quán)計(jì)算，最后得到的總差值即可表示為兩幀之間的相似度，差值越大，則兩幀之間相似度越大，反之，相似度越小。

其中，I代表幀圖像，C代表幀圖像的顏色直方圖矢量值，V代表采用LBP紋理算子方法計(jì)算得到的紋理特征值，D（CC，Cc+1）和D（VC，Vc+1）則可以分別表示兩幀圖像的顏色特征及紋理特征的歸一化相似度，數(shù)值越大，說(shuō)明相似度越低，w1，w2分別代表顏色相似度以及紋理相似度的權(quán)重，且滿(mǎn)足權(quán)值關(guān)系：w1+w2=1，在本文的實(shí)驗(yàn)中，w1和w2均取值0.5。

在這里設(shè)相鄰兩幀顏色直方圖的結(jié)果分別為Cc和Cc+1，N為直方圖的Bin數(shù)，兩直方圖的相似性用D （CC，Cc+1）表示，幀間差的常見(jiàn)的計(jì)算方法如下：其中，Cc（k）在顏色直方圖里表示的是第k個(gè)Bin出現(xiàn)的頻率，D（CC，Cc+1）的值越大表示相似程度越高。

2　改進(jìn)的基于支持向量機(jī)的鏡頭邊界檢測(cè)算法

2.1幀間SVM原理

支持向量機(jī)（Support Vector Machine，簡(jiǎn)稱(chēng) SVM）［8］是一種機(jī)器學(xué)習(xí)的技術(shù)，它建立在統(tǒng)計(jì)學(xué)習(xí)理論中VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理的基礎(chǔ)之上，由Vapnik在20世紀(jì)90年代提。如今已應(yīng)用到科學(xué)研究的各個(gè)領(lǐng)域，如人臉識(shí)別、圖像分類(lèi)以及語(yǔ)音識(shí)別等。現(xiàn)實(shí)世界的分類(lèi)問(wèn)題一般可以分為線(xiàn)性可分問(wèn)題與線(xiàn)性不可分問(wèn)題，雖然SVM是由線(xiàn)性可分問(wèn)題發(fā)展而來(lái)的，但目前也可以較好地解決現(xiàn)行不可分問(wèn)題。

線(xiàn)性可分問(wèn)題就是說(shuō)可以用一條直線(xiàn)將樣本數(shù)據(jù)分隔成兩個(gè)不同的類(lèi)，而支持向量機(jī)的作用即在多條可分的平面中確定一個(gè)最優(yōu)的平面使得兩個(gè)分類(lèi)的間隔最大化。假設(shè)一個(gè)n維空間線(xiàn)性可分的樣本集為｛（xi，yi），i=1，2，…，n，x∈Rn，y∈｛-1，1｝｝，n維空間的線(xiàn)性判別函數(shù)為g（x）=wx+b，當(dāng)分類(lèi)超平面wx+b=0可以成功劃分樣本集，且兩類(lèi)樣本點(diǎn)距離分類(lèi)面的距離間隔最大時(shí)，此分類(lèi)超平面就是最優(yōu)超平面，距離最優(yōu)超平面最近且與其平行的樣本即為支持向量。

在支持向量機(jī)中，用來(lái)解決非線(xiàn)性可分問(wèn)題的主要思想是將非線(xiàn)性不可分問(wèn)題通過(guò)核函數(shù)映射到高維空間，使其在高維空間線(xiàn)性可分，然后在高維空間中尋找最優(yōu)超平面作數(shù)據(jù)分類(lèi)。常見(jiàn)的核函數(shù)有以下三種：

（1）多項(xiàng)式核函數(shù)（Poly）：

K（x，y）=（（x·y）+c）d，其中參數(shù)c取值未1。

徑向基核函數(shù)（RBF）：

（3）Sigmoid核函數(shù)：

K（x，y）=tan（v（x·y）+c），其中，v＞0，c＜0。

支持向量機(jī)劃分為輸入層、隱含層和輸出層。輸入層主要功能是接受數(shù)據(jù)，隱含層實(shí)現(xiàn)低維空間到高維空間的映射并且計(jì)算特征向量與支持向量的內(nèi)積，輸出層則負(fù)責(zé)提供分類(lèi)結(jié)果。

2.2改進(jìn)的算法描述

由于SVM對(duì)核函數(shù)類(lèi)型以及參數(shù)很敏感，所以構(gòu)造最優(yōu)參數(shù)的核函數(shù)才能保證SVM分類(lèi)器識(shí)別的準(zhǔn)確率。本文提出一種對(duì)相應(yīng)SVM進(jìn)行交叉對(duì)比訓(xùn)練的方法來(lái)得到最優(yōu)的參數(shù)C與r。算法描述如下：

（1）計(jì)算各鏡頭特征值的平均值以及利用滑動(dòng)窗口法計(jì)算各窗口的邊緣比率

假設(shè)一個(gè)鏡頭中有N幀｛f1，f2，f3，…，fn｝，利用公式（9）計(jì)算出相鄰兩幀之間的幀差序列K=｛K1，K2，K3，…，Kn-1｝。在針對(duì)各鏡頭幀差進(jìn)行計(jì)算后，需要計(jì)算各鏡頭特征值的平均值來(lái)代表鏡頭的特征值，這里，定義Kij為第j鏡頭的第i個(gè)幀差計(jì)算如下：

（2）通過(guò)上面公式（12）、（13）、（14）計(jì)算，構(gòu)造7維特征向量

（3）構(gòu)造SVM

首先將上述特征向量xi作為輸入變量輸入SVM，在對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行歸一化后，通過(guò)訓(xùn)練得到4×（4-1）/2個(gè)二元分類(lèi)的支持向量機(jī)，每一個(gè)訓(xùn)練集訓(xùn)練一個(gè)分類(lèi)器。然后對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行交叉對(duì)比訓(xùn)練，得到最優(yōu)的核函數(shù)參數(shù)。再利用得到的決策函數(shù)進(jìn)行投票，票數(shù)最多的鏡頭類(lèi)型即為測(cè)試鏡頭的類(lèi)型，最后實(shí)現(xiàn)視頻鏡頭的分類(lèi)。支持向量機(jī)核函數(shù)選用RBF函數(shù)：

（4）利用支持向量機(jī)的判別函數(shù)進(jìn)行突變鏡頭檢測(cè)

給定特征向量xi，則支持向量機(jī)的判別函數(shù)為：

式中sv是支持向量的個(gè)數(shù)，K（x，y）為核函數(shù)。

最后基于機(jī)器學(xué)習(xí)得到的模板進(jìn)行鏡頭邊界分類(lèi)，進(jìn)一步的工作是選取合適的特征矢量來(lái)描述不同的邊界。

3　實(shí)驗(yàn)結(jié)果及分析

3.1數(shù)據(jù)的來(lái)源

本文的數(shù)據(jù)集為T(mén)REVID 2007數(shù)據(jù)集。實(shí)驗(yàn)數(shù)據(jù)集分為測(cè)試集與訓(xùn)練集，通常比例為1∶4，這樣可以使建立模型在大量的訓(xùn)練集中得到完善，使得最后的實(shí)驗(yàn)結(jié)果更具有說(shuō)服力。

3.2評(píng)測(cè)標(biāo)準(zhǔn)

本文采用查全率以及查準(zhǔn)率的評(píng)價(jià)標(biāo)準(zhǔn)，其定義如下：

根據(jù)視頻內(nèi)容的不同選取體育、電影、廣告、紀(jì)錄片4種題材的視頻片段作為樣本進(jìn)行了大量的實(shí)驗(yàn)。說(shuō)明了本文的算法的有效性，實(shí)驗(yàn)結(jié)果如1與表2所示。

表1　本文方法實(shí)驗(yàn)結(jié)果

表2　TREVID 2007數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果

通過(guò)以上兩個(gè)表的實(shí)驗(yàn)結(jié)果我們知道，本文提出的基于SVM的方法對(duì)于視頻的鏡頭邊界檢測(cè)有著較高的查全率與查準(zhǔn)率。同文獻(xiàn)中方法進(jìn)行比較，本文提出的算法在避免漏檢和誤檢方面有很好地效果。

下圖是在Window 7系統(tǒng)下，采用MATLAB 2010b實(shí)現(xiàn)的其中一小段紀(jì)錄片運(yùn)用本文提出的基于支持向量機(jī)的鏡頭邊界檢測(cè)算法的結(jié)果，以及文獻(xiàn)中方法給出的結(jié)果對(duì)比圖如下：

圖1　本文方法的鏡頭檢測(cè)結(jié)果

從結(jié)果的對(duì)比中我們可以看出TREVID 2007數(shù)據(jù)集中的方法敏感性較強(qiáng)，把鏡頭內(nèi)物體的運(yùn)動(dòng)誤判為發(fā)生了鏡頭突變，導(dǎo)致提取的鏡頭出現(xiàn)重復(fù)，而本文提出的算法能夠有效地避免誤判，從而說(shuō)明本文算法的有效性，以及優(yōu)越性。

圖2　文獻(xiàn)中方法的鏡頭檢測(cè)結(jié)果

4　結(jié)語(yǔ)

本文提出了一種改進(jìn)的基于支持向量機(jī)的鏡頭邊界檢測(cè)算法，消除了鏡頭邊界檢測(cè)對(duì)閾值的依賴(lài)。它運(yùn)用機(jī)器學(xué)習(xí)中的支持向量機(jī)有效的實(shí)現(xiàn)利用SVM對(duì)視頻數(shù)據(jù)進(jìn)行分析和處理，從而把鏡頭邊界檢測(cè)問(wèn)題轉(zhuǎn)化成了分類(lèi)問(wèn)題。有效地實(shí)現(xiàn)鏡頭邊界檢測(cè)，實(shí)驗(yàn)表明這種方法對(duì)鏡頭邊界檢測(cè)的切變檢測(cè)有很好的檢測(cè)效果。

［1］巢娟，蔣興浩.基于雙重監(jiān)測(cè)模型的視頻鏡頭分割算法［J］.上海交通大學(xué)學(xué)報(bào)，2011∶1542-1546.

［2］文軍，謝毓湘，老松楊.足球比賽視頻中的精彩鏡頭分析方法［J］.計(jì)算機(jī)工程，2004∶159-161.

［3］Liu Z，Gibbon D，Zavesky E，et Al.AT&T Research at TRECVID2006［C］，2006.

［4］姜慧.網(wǎng)球視頻中場(chǎng)地廣告牌檢索關(guān)鍵技術(shù)的研究［D］.上海海事大學(xué)，2011.

［5］Geng Yuliang，Xu De，F(xiàn)eng Songhe.A Repid and Effective Method for Shot Boundary Detection［J］.Acta Electronica Sinica，2006，34 （12）∶2272-2277.

［6］王瑋，黃非非，李見(jiàn)為，馮海亮.使用多尺度LBP特征描述與人臉識(shí)別［D］.光學(xué)精密工程，2008∶697-704.

［7］陳建斌.圖像特征提取及其相似度的研究和實(shí)現(xiàn)［D］.西安電子科技大學(xué)，2012.

［8］鄧乃揚(yáng)，田英杰.數(shù)據(jù)挖掘中的新方法——支持向量機(jī)［M］.北京科學(xué)出版社，2004.

Video Retrieval；Shot Boundary Detection；Support Vector Machine

An Algorithm of Video Shot Boundary Detection Based on SVM

CHANG Hong，ZHANG Ming
（College of Information Engineering，Shanghai Maritime University，Shanghai201306）

Proposes an improved shot boundary detection algorithm based on Support Vector Machine，which is not dependent on the threshold.The algorithm makes use of SVM to analyze and process the video data，the feature extracted from the video frame is used as the input data of SVM，thus，the shot boundary detection problem is transformed into a classification problem.The shot boundary detection and machine learning effective combination，experimental results show that this method has a good effect on the mutation detection of shot boundary detection.

1007-1423（2016）20-0073-05

10.3969/j.issn.1007-1423.2016.20.015

常虹（1990-），女，江蘇徐州人，碩士研究生，研究方向?yàn)闄C(jī)器學(xué)習(xí)、自然語(yǔ)言處理、模式識(shí)別等

張明（1957-），男，博士，教授，研究方向?yàn)槎嗝襟w信息處理、分布式多媒體技術(shù)、多媒體數(shù)據(jù)庫(kù)、視覺(jué)信息檢索與分析、網(wǎng)絡(luò)信息安全、人工智能、航運(yùn)信息化技術(shù)等

2016-04-21

2016-07-10