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

一種基于支持向量機的鏡頭邊界檢測算法

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

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

視頻檢索；鏡頭邊界檢測；支持向量機

0　引言

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

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

1　顏色模型轉換和幀間差值的計算

1.1顏色模型轉換

HSV顏色模型

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

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

1.2圖像特征提取

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

（1）紋理特征

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

本文利用LBP［6］（局部二值模式）紋理特征描述算子來對幀圖像的紋理特征進行處理。LBP描述算子具有的灰度不變和旋轉不變的性質很巧妙的避免了由光照或閃光顯著改變而引起的實驗結果的誤差。

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

圖1　基本的LBP算子計算示意圖

用公式可以表示為：

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

（2）顏色直方圖

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

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

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

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

1.3幀間差值計算

在鏡頭邊界檢測算法中，非常普遍的使用方法是顏色直方圖法，它是分別對兩幅相鄰的圖像進行顏色直方圖提取，再對兩者的直方圖進行歸一化，計算兩幅相鄰圖像的幀間差，換句話說就是計算直方圖間的相似性，最后通過差值比較的方法來對鏡頭的邊界進行判斷。

因為本文是利用顏色特征和紋理特征共同來對幀圖像進行描述［7］，所以，兩幀之間的相似度可以用二者差值來表示。在本文中，首先計算兩幀圖像之間的顏色直方圖的差值，再計算兩幀圖像之間的LBP紋理算子的差值，再將這兩個差值進行加權計算，最后得到的總差值即可表示為兩幀之間的相似度，差值越大，則兩幀之間相似度越大，反之，相似度越小。

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

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

2　改進的基于支持向量機的鏡頭邊界檢測算法

2.1幀間SVM原理

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

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

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

（1）多項式核函數(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。

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

2.2改進的算法描述

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

（1）計算各鏡頭特征值的平均值以及利用滑動窗口法計算各窗口的邊緣比率

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

（2）通過上面公式（12）、（13）、（14）計算，構造7維特征向量

（3）構造SVM

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

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

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

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

最后基于機器學習得到的模板進行鏡頭邊界分類，進一步的工作是選取合適的特征矢量來描述不同的邊界。

3　實驗結果及分析

3.1數(shù)據(jù)的來源

本文的數(shù)據(jù)集為TREVID 2007數(shù)據(jù)集。實驗數(shù)據(jù)集分為測試集與訓練集，通常比例為1∶4，這樣可以使建立模型在大量的訓練集中得到完善，使得最后的實驗結果更具有說服力。

3.2評測標準

本文采用查全率以及查準率的評價標準，其定義如下：

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

表1　本文方法實驗結果

表2　TREVID 2007數(shù)據(jù)集中的實驗結果

通過以上兩個表的實驗結果我們知道，本文提出的基于SVM的方法對于視頻的鏡頭邊界檢測有著較高的查全率與查準率。同文獻中方法進行比較，本文提出的算法在避免漏檢和誤檢方面有很好地效果。

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

圖1　本文方法的鏡頭檢測結果

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

圖2　文獻中方法的鏡頭檢測結果

4　結語

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

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

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

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

［4］姜慧.網球視頻中場地廣告牌檢索關鍵技術的研究［D］.上海海事大學，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］王瑋，黃非非，李見為，馮海亮.使用多尺度LBP特征描述與人臉識別［D］.光學精密工程，2008∶697-704.

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

［8］鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法——支持向量機［M］.北京科學出版社，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-），女，江蘇徐州人，碩士研究生，研究方向為機器學習、自然語言處理、模式識別等

張明（1957-），男，博士，教授，研究方向為多媒體信息處理、分布式多媒體技術、多媒體數(shù)據(jù)庫、視覺信息檢索與分析、網絡信息安全、人工智能、航運信息化技術等

2016-04-21

2016-07-10