基于SURF和SIFT特征的視頻鏡頭分割算法

張昊骕，朱曉龍，胡新洲，任洪娥,2*

(1. 東北林業(yè)大學(xué) 信息與計算機工程學(xué)院，黑龍江 哈爾濱 150040；2. 黑龍江省林業(yè)智能裝備工程研究中心，黑龍江 哈爾濱 150040)

1 引 言

視頻鏡頭分割是視頻處理中的第一步，它的任務(wù)是準確找出鏡頭之間的邊界，這對視頻的后續(xù)處理如關(guān)鍵幀提取等起著至關(guān)重要的作用。視頻鏡頭邊界主要分為兩種[1]，一種是切變鏡頭，指的是前一個鏡頭直接切入到下一個鏡頭，鏡頭之間變化明顯，也比較容易檢測。另一種是漸變鏡頭，指的是前一個鏡頭通過幾幀甚至幾十幀緩慢過度到下一個鏡頭，鏡頭之間變化緩慢，檢測比較困難。近些年來，為了解決鏡頭邊界檢測的問題，很多種用于鏡頭邊界檢測的方法被提出，并取得了顯著效果。Kikukawa等[2]提出了像素幀差法，它采用前后相鄰兩幀的對應(yīng)像素的色度并比較其差值來查找鏡頭邊界。Zhang等[3]提出了直方圖幀差法，采用度量臨近幀之間直方圖的差異來查找鏡頭的邊界。楊瑞琴等[4]提取Hu不變矩特征進行初檢選出候選邊界，然后利用三維顏色直方圖進行復(fù)檢。于俊清等[5]通過構(gòu)造回放因子特征來改進情感激勵模型從而實現(xiàn)了鏡頭邊界檢測。李小琛等[6]利用SIFT特征融合CSIFT顏色不變量特征進行鏡頭邊界檢測，有效地彌補了SIFT算法丟失色彩信息的缺陷。蔡軼珩等[7]提出一種融合了色彩特征和改進的SURF特征的鏡頭分割算法，通過減少匹配點數(shù)量，加快了算法運算速度，通過使用自適應(yīng)閾值，以及融入顏色特征等方式，提高了算法準確率。除此之外，還有很多類似的方法。簡而言之，這些方法從不同的角度實現(xiàn)了對鏡頭識別分割這一過程。然而，在上述算法中，有些算法僅僅利用了全局特征，雖然速度較快但是準確率較差。有些算法雖然融合了局部特征和全局特征，但是融合方式不緊密導(dǎo)致可能會出現(xiàn)漏檢。

SIFT特征是一種經(jīng)典的特征點提取描述算法。并且它已被大量應(yīng)用于圖像、視頻分析等領(lǐng)域中，它具有對尺度變換、旋轉(zhuǎn)變換、仿射變換、視角變換、噪聲的不變性等諸多優(yōu)點，然而由于其特征點提取過程比較復(fù)雜，導(dǎo)致效率低下，不適用于數(shù)據(jù)量大和具有實時性要求的場合，而且由于算法使用灰度圖像進行特征點的檢測，缺乏圖像色彩信息，所以對于視頻檢測來說容易造成誤檢。

相比之下，SURF特征比SIFT特征的速度快很多，并且對亮度等變化不太敏感。所以，本文針對以上文獻中存在的高效性與準確性不平衡的問題，從SIFT特征效率較低的特點入手，提出了基于SURF和SIFT特征的鏡頭分割技術(shù)。首先判斷兩幀的顏色特征距離，如果大于設(shè)定的自適應(yīng)閾值，則加入候選幀，否則提取出SURF特征并與顏色特征進行特征融合，然后使用滑動窗口技術(shù)計算當前幀與后續(xù)幀的特征距離并使用閾值篩選出候選切變鏡頭和漸變鏡頭。最后采用SIFT特征用來進行復(fù)選，從而去掉誤檢鏡頭。

2 基于多特征融合的鏡頭分割算法

由于SIFT特征效率低下，顯然不能直接使用SIFT進行鏡頭分割，所以在鏡頭邊界幀初選階段我們引入SURF特征來替代SIFT特征以實現(xiàn)高效分割。

2.1 SURF特征點提取

SURF特征即加速穩(wěn)健特征，是一種局部特征點的提取和描述算法[8]，它基于SIFT特征并改良了其特征點提取和描述方式，所以SURF也具有SIFT特征的對尺度、旋轉(zhuǎn)等不變性的特性，而且SURF由于采用了Harr小波特征和積分圖像的方法，運行效率相較SIFT有了大幅度的提升。

SURF特征點的提取過程如下：

(1)假設(shè)圖像用函數(shù)f(x,y)來表示。首先利用黑塞矩陣獲取特征點，則圖像中相應(yīng)點的黑塞矩陣為：

(1)

從而有判別式：

(2)

經(jīng)過高斯濾波的對應(yīng)矩陣為：

(3)

在計算黑塞矩陣之前，應(yīng)該使用二階標準高斯函數(shù)進行濾波，這是因為它可以使求得的特征點具備尺度無關(guān)特性。用I(x,y)代替點(x,y)，L(x,t)為高斯函數(shù)G(t)在點(x,y)處卷積的結(jié)果：

L(x,t)=G(t)·I(x,y)，

(4)

其中，高斯核G(t)為：

(5)

為了加快計算速度，SURF算法改變了以往先進行高斯濾波，然后求二階導(dǎo)數(shù)，進而求取黑塞矩陣的方式，轉(zhuǎn)而采用了盒式濾波來近似高斯濾波。設(shè)在經(jīng)過盒式濾波之后，用Pxx、Pyy、Pxy來代表Lxx、Lyy、Lxy，所以有判別式：

det(H)=PxxPyy-(0.9Pxy)2，

(6)

其中，0.9為經(jīng)驗值。根據(jù)判定結(jié)果的符號,若det(H)>0,則此點為極值點。

(2)生成尺度空間，如圖1所示。

圖1 尺度空間的建立Fig.1 Building of a scale space

在SURF特征中，圖像尺度是不變的，通過對圖像進行不同尺度的盒式濾波來生成尺度空間的每一層。

(3)利用非最大抑制來定位特征點，如圖2所示。

圖2 定位特征點Fig.2 Location feature points

經(jīng)過黑塞矩陣處理過的每個特征點與相鄰的26個點進行大小比較，如果最大或最小，則保留下來做備選點。然后，采用3維線性插值法進一步得到亞像素級的特征點，同時也去掉一些較弱或錯誤的特征點，通過控制極值大小來控制特征點數(shù)量，最終僅留下一些較強的特征點。

(4)為特征點選取主方向，如圖3所示。

圖3 選取特征點主方向Fig.3 Selection of the main direction of feature points

SURF特征統(tǒng)計了以特征點為中心，在固定半徑大小的圓形區(qū)域內(nèi)以一定間隔轉(zhuǎn)動的扇形內(nèi)全部點的Harr小波特征，并將取得最大值的扇形方向設(shè)定為主方向。這樣，通過計算每一個特征點，得到每一個特征點的主方向。

(5)構(gòu)成特征點的描述算子，如圖4所示。在特征點鄰域選取一個矩形框并將其分成4×4個子區(qū)域，然后統(tǒng)計每個區(qū)域中共25個像素的Haar小波特征來得到描述子。

圖4 構(gòu)成特征點描述子Fig.4 Constitution of the descriptor of feature points

2.2 改進的SURF特征匹配及特征融合算法

特征點匹配一般采用FLANN算法。FLANN算法基于KD樹，可以根據(jù)數(shù)據(jù)集的分布特點，來推薦索引類型和檢索參數(shù)[9]。該算法首先根據(jù)得到的特征點，計算圖像中某一特征點x與另一圖像中特征點y的歐式距離，接著采用歐式距離比值法進行匹配[10]，最后篩選經(jīng)過配對的特征點，僅保留符合要求的點。

為了提升SURF特征的準確性，本文改進了特征點的匹配方式。傳統(tǒng)的匹配方式通常為使用固定閾值或者設(shè)定閾值為最小匹配距離Dmin的N倍來進行匹配，但是，如果使用固定閾值將可能無法滿足不同類型視頻匹配的要求，如果設(shè)定閾值為最小匹配距離的N倍，在某些情況下，最小匹配距離可能為0，而其他匹配點的匹配距離可能并不為0，從而導(dǎo)致誤檢。為解決這個問題，使用最大匹配距離Dmax和顏色特征距離Dc并采用線性結(jié)合權(quán)重的自適應(yīng)閾值的方法，如式7所示。

Dt=ρ·D+(1-ρ)·Dc，

(7)

其中：Dc為顏色特征距離，D為特征點距離，Dt為融合后的距離。

對于兩幅圖像而言，式(7)中融合了相同的顏色特征信息，只有D是可變的，因此經(jīng)過融合后的最大距離Dtmax與最小距離Dtmin的比值應(yīng)該與Dmax和Dmin的比值相等。設(shè)Dtmin=ρ·Dmin+(1-ρ)·Dc，所以有式(8):

(8)

令Dmax/Dmin=M，設(shè)優(yōu)秀匹配點閾值Dm為融合后最大距離Dtmax的K倍(K∈(0,1))，如式(9)所示。

Dm=K·(ρ·Dmax+(1-ρ)·M·Dc).

(9)

經(jīng)過大量實驗證明，在SURF檢測器閾值為3 000，K值為0.4時，這種方法尤其對切變鏡頭有較高的匹配率。在本文中的SIFT特征匹配方式也是按照相似的方式進行的。

對于特征融合算法，傳統(tǒng)的特征融合方式包括串行融合和并行融合兩種[11]。串行融合是指新的特征向量是由兩組特征向量通過串行連接成的。其優(yōu)點是構(gòu)造方法簡單，幾乎不需要進行運算，缺點是特征向量γ的維數(shù)可能急劇增加。并行融合是利用復(fù)向量，將特征向量在復(fù)向量空間進行融合。如果兩個向量維數(shù)不同，則通過補0來對齊。其優(yōu)點是對比串行融合方式，有效地降低了特征向量的維數(shù)，缺點是計算量可能較大。

為了盡可能減小計算量，避免維度劇烈增加，本文采用式7的方式通過賦予每種特征的特征向量之間的距離以相應(yīng)的權(quán)重，再求其和進而表示特征融合后兩圖之間的距離。通過此公式融入FLANN匹配算法來獲得優(yōu)秀的匹配點，實驗證明，權(quán)重ρ在取值為0.6時準確率最高。

2.3 改進的顏色特征的檢測算法

SURF特征是一種局部特征，它反映了圖像的部份像素間的關(guān)系，然而僅僅使用局部特征還不能對圖像精確地描述。全局特征可以表達出整張圖像的信息，而且它的速度比局部特征要快，所以為了增加速度和準確性，本文使用了全局特征及全局特征融合局部特征的方式進行鏡頭檢測。

顏色直方圖是一種常用的全局特征，主要因為其算法簡單，對匹配圖像的旋轉(zhuǎn)、變形、模糊變換具有不變性的優(yōu)勢，并且對噪聲、鏡頭位置、分辨率等也并不敏感，所以在圖像、視頻處理系統(tǒng)中被廣泛應(yīng)用。而在這其中HSV空間是直方圖最常用的顏色空間，它包含色相H、飽和度S和亮度V3個分量，同時，它也是最適合人類的視覺系統(tǒng)。

計算顏色直方圖首先需要量化顏色。顏色量化即是將顏色空間分為若干區(qū)間(bin)，然后計算處于每個區(qū)間的像素個數(shù)即可得到顏色直方圖。

為了減少計算復(fù)雜度，首先將直方圖分為64個bin，H范圍為(0,44),(45,89),(90,134),(135,179),S范圍為(0,63),(64,127),(128,191),(191,255),V范圍為(0,63),(64,127),(128,191),(191,255)，并將其歸一化，即將每個bin值除以圖像像素數(shù)量。最后得到顏色特征向量：

(10)

其中:S為圖像像素數(shù)量，Mn代表bin元素數(shù)量。

為了后續(xù)的特征融合階段，本文中使用歐式距離作為HSV直方圖的距離對比方式：

(11)

這里M,N是兩幀圖像的HSV顏色直方圖Mi、Ni是顏色直方圖第i個bin的元素個數(shù)。

算法主要是通過比較前后兩幀顏色直方圖距離與某一閾值的大小來尋找鏡頭邊界。傳統(tǒng)的判別方法使用固定閾值，然而固定閾值對于不同類型的視頻來說閾值設(shè)定不盡相同，且需要大量的實驗來確定，很容易發(fā)生漏檢、誤檢現(xiàn)象，所以本文通過使用自適應(yīng)閾值來判斷切變鏡頭。對于漸變鏡頭，其變化過程多樣，單一顏色特征檢測漸變鏡頭較難判定，容易造成誤檢。所以并未采用單一顏色特征來判定漸變鏡頭。本節(jié)算法過程為：

首先提取視頻的相鄰兩幀圖像，然后分別把這兩幀圖像從RGB空間轉(zhuǎn)換成HSV空間并將進行顏色量化，接著分別計算這兩幀圖像的HSV直方圖，最后計算它們的顏色特征距離，如果顏色距離大于自適應(yīng)閾值T，則判定切變鏡頭。根據(jù)實驗得到的經(jīng)驗，對于一般情形，前后兩幀的信息具有一定連續(xù)性，顏色變化程度較小，所以相應(yīng)顏色特征距離不會超過其與零向量的歐式距離。所以，將自適應(yīng)閾值選擇為兩幀中第一幀的顏色特征向量與零向量歐氏距離的0.8倍(式(12))。經(jīng)過實驗檢驗，本節(jié)算法對檢測切變鏡頭有較高的準確性。

(12)

2.4 基于顏色和SURF特征的鏡頭分割算法

本節(jié)算法過程為：首先提取顏色特征，使用上述基于顏色特征的檢測算法判斷當前幀是否為切變鏡頭，如果是則進入下一幀，否則提取SURF特征，然后將改進的融合模式用于特征融合，并篩選優(yōu)秀的匹配點，接著計算相鄰兩幀之間的匹配度，如果幀間匹配度小于閾值T1，則將其判定為切變鏡頭。如果匹配度大于閾值T2，則判定為無變化。如果匹配度處于T1與T2之間，則有可能存在漸變鏡頭。針對切變和漸變兩種鏡頭邊界的差別，我們使用了滑動窗口的檢測手段。維持一個窗口，設(shè)定它的最初大小w為0，它的起始位置為當前幀c，并不斷向右側(cè)拓展，并不斷比較幀F(xiàn)c和Fc-w的匹配度，如果兩幀匹配度小于閾值T1，那么將其認定為漸變鏡頭，并加入候選幀，然后恢復(fù)最初設(shè)定。若在此窗口擴展中檢測到相鄰兩幀存在切變鏡頭或無變化，則直接初始化設(shè)定。重復(fù)如此過程，直到檢測完所有幀。經(jīng)過大量實驗，確定閾值T1=0.3，T2=0.8時準確率最高。算法流程如圖5所示。

通過應(yīng)用信息化科學(xué)技術(shù)可以實現(xiàn)土木工程設(shè)計和管理的優(yōu)化，充分將建筑美學(xué)表達出來，實現(xiàn)土木管理的精細化。隨著各項新的技術(shù)、設(shè)備逐漸研發(fā)，新的管理模式以及應(yīng)用平臺的更新，土木工程建設(shè)如果不能做到與時俱進勢必會被社會淘汰，只有不斷將適應(yīng)現(xiàn)代化社會發(fā)展的需求，逐步提升管理水平，才能促進土木工程施工建設(shè)可持續(xù)發(fā)展。

圖5 基于顏色特征和SURF特征的鏡頭分割算法流程圖Fig.5 Flowchart of shot segmentation algorithm based on color feature and SURF feature

2.5 SIFT特征匹配

雖然顏色特征結(jié)合SURF特征可以滿足要求，但是根據(jù)Juan等人對SURF和SIFT等特征的實驗比較來看，SIFT特征可以獲得數(shù)量更多的特征點，而且SURF特征對于尺度和旋轉(zhuǎn)變換等方面相比檢測效果略差[12]，綜合來看SIFT特征的檢測效果要強于SURF特征，此外，在漸變鏡頭檢測中由于滑動窗口未限定尺寸，有可能產(chǎn)生誤檢，為了提高算法準確性，我們通過構(gòu)造SIFT特征來去除一些由于尺度、旋轉(zhuǎn)等方面誤檢的候選幀，如圖6所示。

圖6 鏡頭放大造成的誤檢Fig.6 Misdetection caused by lens enlargement

SIFT特征的全稱是尺度不變的特征變換[13], 它具有許多優(yōu)點，例如對旋轉(zhuǎn)、尺度、視角變化、仿射、噪聲等變換的不變性。SIFT特征與SURF特征的主要區(qū)別在于：

(1)SIFT是在高斯差分圖像金字塔中對每一層圖像進行高斯濾波求取圖像差來求取特征點。

(2)SIFT算法通過計算梯度直方圖，然后查找其最大方向或大于80%處的最大bin方向來確定相應(yīng)特征點的主方向。

(3)在確定特征描述子方面，SIFT算法采用了在16×16的鄰域內(nèi)分成4×4的區(qū)域，每個區(qū)域取8個方向，即特征向量維數(shù)=4×4×8=128維。

SIFT特征復(fù)選的算法如下：對候選幀首先計算其前一幀和后一幀的SIFT距離，如果匹配度小于閾值T3，則判定為切變鏡頭，反之計算其前后4幀的SIFT距離，如果匹配度小于閾值T4，則判定為漸變鏡頭，若匹配度大于T4，則說明既不是切變鏡頭也不是漸變鏡頭，去除即可。經(jīng)過大量實驗，確定閾值T3=0.3，T4=0.5時準確率最高。

3 實驗流程和結(jié)果對比評價

3.1 實驗環(huán)境

本實驗硬件環(huán)境是CPU為Intel Core I7 6700，內(nèi)存為4 GB，軟件環(huán)境是操作系統(tǒng)為Windows 10 64位，編程環(huán)境為Visual Studio.NET 2015、OpenCV 2.4.13。測試視頻數(shù)量為70個，分辨率均為320×240，碼率均為326 kb/s。

3.2 實驗數(shù)據(jù)

3.3 實驗流程

本文算法實施流程如下：

(1)讀取視頻文件。

(2)讀取成功進入下一步，失敗則退出。

(3)讀取下一幀，計算其HSV顏色特征，通過是否大于自適應(yīng)閾值判斷是否為切變鏡頭，若是，則將此幀加入候選幀，直接進入下一幀，否則進入下一步。

(4)結(jié)合SURF特征與HSV顏色特征，通過設(shè)定滑動窗口來判斷此幀是否為切變鏡頭或漸變鏡頭，如果是，則加入候選幀。然后回到第二步。

(5)使用SIFT特征，通過對其前后幀及前后四幀的特征距離進行判斷，篩選候選幀，剔除偽漸變鏡頭和偽切變鏡頭。

(6)保存并輸出分割結(jié)果。

3.4 實驗結(jié)果及評價

本文使用查準率和查全率作為評價指標,如式(13)、式(14)所示。

(13)

(14)

將視頻數(shù)據(jù)通過圖5算法流程進行分割，將得到的視頻幀內(nèi)容及幀數(shù)輸出，與該視頻數(shù)據(jù)人工標注幀對比，并計算其查準率和查全率，進而得到本文算法的綜合指標。本節(jié)選取了幾個視頻片段在本文算法下的部份分割結(jié)果：

視頻1長度為59 s，總幀數(shù)為1 798幀。視頻2長度為7 min 43 s，總幀數(shù)為13 888幀。由于篇幅有限，僅選部份結(jié)果進行展示。視頻片段1和視頻片段2的鏡頭分割輸出結(jié)果如圖7、8所示。

(a) 切變鏡頭輸出結(jié)果(a) Output of shear shot

(b) 漸變鏡頭輸出結(jié)果(b) Output of gradual shot圖7 視頻片段1輸出結(jié)果Fig.7 Output of shot segmentation in video clip 1

(a) 切變鏡頭輸出結(jié)果(a) Output of shear shot

(b) 漸變鏡頭輸出結(jié)果(b) Output of gradual shot圖8 視頻片段2輸出結(jié)果Fig.8 Output of shot segmentation in video clip 2

本文算法與其他算法的精準度比較如表1所示。

由圖7、圖8可以看出，算法能夠?qū)η凶冪R頭和漸變鏡頭進行有效的識別，為了說明本文算法的優(yōu)勢，我們通過使用70個視頻數(shù)據(jù)測試本文算法與其它幾種單一特征算法或文章中提到的一些算法進行比對,通過比較其平均查準率和平均查全率，顯示了本文的方法無論在查準率還是查全率上都要稍高于其他算法。另外，通過和單一特征算法的單幀平均運行時間比較表明，融合后的特征比單一特征更為均衡，兼顧性能和準確性。

表1 本文算法與其他算法的精準度比較Tab.1 Comparion of the accuracy of the proposed algorithm with that of other algorithms

本文算法與其他算法的平均單幀運行時間比較如表2所示。

表2 本文算法與其他算法的平均單幀運行時間比較

Tab.2 Comparison of the average simgle frame run time between the proposed algorithm and other algorithms

算法單幀平均運行時間/sSIFT1.46SURF0.14HSV直方圖0.05本文算法0.26

4 結(jié) 論

本文實現(xiàn)了一種基于SURF和SIFT特征的視頻鏡頭分割算法.通過在初選階段引入顏色和SURF特征并進行了特征融合，精巧地解決了SIFT特征效率不高的難題，同時增加了算法的準確性。在復(fù)選階段使用SIFT進行篩選，又利用了SIFT特征的優(yōu)勢，進一步加強了算法的準確性。該算法有效地結(jié)合了局部特征和全局特征，可以精準快速地識別鏡頭邊界，對切變鏡頭的查全率達到95%，查準率達到93%，對漸變鏡頭的檢測查全率達到90%，查準率達到76%，并且平均單幀運行時間為0.26s。實驗結(jié)果表明，通過特征融合，融合后的特征同時具備了兩種特征的優(yōu)點，而彌補了相應(yīng)的缺點，起到了揚長補短的作用。此外，對于算法中SURF、SIFT特征檢測器的閾值以及兩幀匹配度的判定閾值均為實驗所得的固定閾值，可以通過加入無監(jiān)督學(xué)習(xí)來進一步優(yōu)化。