李　楓， 趙　巖，王世剛， 陳賀新

(吉林大學 通信工程學院，吉林 長春 130012)

?

結(jié)合SIFT算法的視頻場景突變檢測

李楓， 趙巖*，王世剛， 陳賀新

(吉林大學 通信工程學院，吉林 長春 130012)

摘要：視頻場景變化檢測對于視頻的標注以及語義檢索具有非常重要的作用。本文提出了一種結(jié)合SIFT(Scale Invariant Feature Transformation)特征點提取的場景變化檢測算法。首先利用SIFT 算法分別提取出視頻前后幀的特征點并分別統(tǒng)計其數(shù)量，然后對視頻前后幀進行圖像匹配，統(tǒng)計匹配上的特征點數(shù)量，最后將該幀的匹配特征點數(shù)量與該幀前一幀的特征點數(shù)量做比值，從而通過該比值判斷場景變化情況。實驗結(jié)果表明，視頻場景突變檢測率平均可以達到95.79%。本算法可以在視頻幀進行圖像匹配的過程中對場景的變化情況進行判斷，因此該算法不僅應(yīng)用范圍較廣，還可以保證場景變化檢測的精度，仿真結(jié)果證明了算法的有效性。

關(guān)鍵詞:SIFT；特征點匹配；場景變化檢測

1引言

圖像和視頻作為信息的載體之一，已經(jīng)融入到了人們的生活之中。場景變化檢測算法在關(guān)鍵幀檢索、視頻檢索、視頻編碼以及碼率控制等方面具有廣泛的應(yīng)用，因此研究場景變化檢測算法對視頻技術(shù)的進一步發(fā)展有很大幫助。

目前常見的場景突變檢測算法有像素比較法、直方圖比較法、基于邊緣的方法和基于運動矢量的方法等[1-5]。像素比較法比較簡單，但是對物體運動和噪聲比較敏感；直方圖比較法忽略了圖像中的位置信息；基于邊緣的方法和基于運動矢量的方法能夠獲得較好的檢測效果，但是計算量較大。隨著研究的深入，一些算法有了更加精準的檢測結(jié)果。例如，Vlachos[6]曾經(jīng)提出利用相位相關(guān)性進行場景突變檢測的方法。Yumi Eom[7]等人提出了在HEVC的編碼碼流中利用幀特征對超高清(UHD)視頻進行場景變化檢測，解決了傳統(tǒng)場景變化檢測方法無法面對UHD視頻數(shù)據(jù)量大的問題。Soongi Hong[8]等人為解決傳統(tǒng)算法在面對不同視頻時閾值選擇單一的問題上提出了先提取視頻直方圖，而后通過對數(shù)正態(tài)分布和參數(shù)模型估計的方法，實現(xiàn)了自適應(yīng)閾值的視頻場景變化檢測。不過一些算法因為計算量過大，同時沒有明顯提高檢測性能而沒有得到普及和應(yīng)用。例如，文獻[9]利用壓縮域結(jié)合神經(jīng)網(wǎng)絡(luò)進行邊界檢測，當場景中出現(xiàn)光強變化以及鏡頭移動等情況時，這種基于神經(jīng)網(wǎng)絡(luò)的場景變化檢測算法頑健性仍然不足。文獻[10]提出一種基于ORB(面向快速和短暫旋轉(zhuǎn))的場景變化檢測算法，不過，該算法中的閾值與視頻類型或者鏡頭轉(zhuǎn)換方式有關(guān)，需要在實際應(yīng)用中根據(jù)具體數(shù)據(jù)進行調(diào)整。

針對以上問題，如何在視頻中高效準確的判斷場景變化成為本文研究的重點內(nèi)容。故本文提出了一種結(jié)合SIFT特征點匹配算法的場景突變檢測算法。

2本文算法

SIFT算法自David Lowe于1999年提出后，由于其在物體識別、圖像拼接、機器人地圖感知與導航、影像追蹤等領(lǐng)域的廣泛應(yīng)用而備受人們的關(guān)注[11-16]。SIFT算法具有尺度不變性、旋轉(zhuǎn)不變性，同時對于仿射變化，噪音以及光照變化具有很好的穩(wěn)定性，因此經(jīng)過了十幾年的發(fā)展依然是一種經(jīng)典的特征提取算法。

SIFT算法主要有以下幾個特點：(1)獨特性，信息量豐富，可以在特征數(shù)據(jù)庫中進行快速、準確的匹配；(2)多量性，即使少數(shù)的幾個對象也可以提取數(shù)量較多的SIFT特征向量；(3)高速性，經(jīng)典的SIFT匹配算法經(jīng)過降低維度、改變灰度級等方法處理之后甚至可以達到實時的要求；(4)可擴展性，可以很方便地與其他形式的特征向量進行聯(lián)合。因此本文將其作為圖像匹配和識別的基礎(chǔ)，根據(jù)SIFT算法的這些特點進行視頻場景突變檢測。

圖1　本文算法流程圖Fig.1　Flow chart of the algorithm proposed in this paper

本文算法流程圖見圖1?；赟IFT特征點提取的場景突變檢測算法主要分為3個部分：(1)SIFT算法提取特征點；(2)基于SIFT算法的圖像匹配；(3)視頻場景變化檢測。

2.1　SIFT算法提取特征點

SIFT算法的本質(zhì)是在不同的尺度空間上尋找特征點并計算出特征點的方向。Lowe將SIFT算法主要分為4個步驟：

(1)尺度空間極值檢測：首先對圖像實現(xiàn)高斯模糊并通過降采樣建立高斯金字塔，利用高斯金字塔表示尺度空間，然后每一個像素點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。以確保在尺度空間和二維圖像空間都檢測到極值點。

(2)關(guān)鍵點的位置確定：尺度空間極值檢測得到的是離散空間的關(guān)鍵點，為了得到穩(wěn)健的特征點，必須對尺度空間高斯差分(DOG)函數(shù)進行擬合，同時去除由于DOG算子的邊緣響應(yīng)而產(chǎn)生的邊緣點。

(3)關(guān)鍵點的方向確定：計算關(guān)鍵點的圖像梯度，并用直方圖統(tǒng)計鄰域內(nèi)像素的梯度和方向，梯度直方圖將0~360°的方向范圍分為36個柱，其中每柱10°。直方圖的峰值方向代表了關(guān)鍵點的主方向。

(4)關(guān)鍵點描述：對于每一個關(guān)鍵點，擁有3個信息：位置、尺度以及方向。特征點描述的目的是用一個具有獨特性的特征向量把特征點描述出來。Lowe建議描述子使用在關(guān)鍵點尺度空間內(nèi)4×4的窗口中計算的8個方向的梯度信息，共4×4×8=128維向量表征。

2.2　基于SIFT算法的圖像匹配

在SIFT算法的實際應(yīng)用過程中，SIFT 特征點的匹配是最重要的步驟之一。SIFT特征點使用在關(guān)鍵點尺度空間內(nèi)4×4的窗口中計算的8個方向的梯度信息，共4×4×8=128維向量表征，因此SIFT特征點的匹配問題就可以轉(zhuǎn)化為在128維空間中特征向量的最近鄰搜索問題。由于特征描述子是一個128維向量，因此任意向量的距離定義都可以作為特征點的距離，比較常用的有Euclid距離和協(xié)方差和反余弦函數(shù)計算出的距離。由于Euclid距離計算量較大，會影響場景變化檢測的計算速度，因此本文采用協(xié)方差和反余弦函數(shù)計算，如式(1)：

(1)

計算輸入圖像的每個特征點與匹配圖像中所有特征點的距離后將其按照從小到大的順序排列得到距離向量d。計算最近距離d(1)與次近距離d(2)的比值，即d(1)/d(2)，如果該比值小于閥值，則認為匹配，否則認為不匹配。

2.3　視頻場景變化檢測

SIFT特征匹配具有顯著性，也就是說特征點在與其匹配的圖像中進行SIFT特征點搜索時，正確匹配的概率非常高，故本文將其作為圖像匹配和識別的基礎(chǔ)，利用SIFT匹配算法的這個特點進行視頻的場景突變檢測。

將圖像中相鄰兩幀即當前幀與前一幀利用SIFT算法進行特征點匹配，兩幀匹配后得到的特征點數(shù)量記為b。為了通過相鄰兩幀的匹配率來反映視頻場景突變的情況，將特征點匹配數(shù)量b與前一幀的特征點數(shù)量an-1作比值，當其滿足式(2)時，認定當前幀發(fā)生了場景突變，經(jīng)實驗驗證α取0.3。

(2)

式中，n表示當前幀，n-1表示前一幀，an-1表示前一幀特征點數(shù)量，b表示當前幀與前一幀利用SIFT算法進行特征點匹配后得到的匹配特征點數(shù)量。

3實驗結(jié)果

3.1　算法驗證

本程序是在VS2013+OpenCV2.4.10開發(fā)

圖2　無場景突變舉例(115、116幀)Fig.2　Examples of no scene mutation change(the 115th and 116th frames)

圖3　場景突變舉例(114、115幀)Fig.3　Examples of scene mutation change(the 114th and 115th frames)

環(huán)境下實現(xiàn)，主要包括SIFT特征點提取、特征點匹配與場景變化檢測的判斷三個部分，實驗過程結(jié)果見圖2與圖3。

本文截取了實驗視頻中114、115、116三幀，其中114與115幀發(fā)生了場景突變，115與116幀無場景突變，具體實驗數(shù)據(jù)見表1。通過實驗可以看出當相鄰兩幀沒有發(fā)生場景突變的時候，其相鄰兩幀的相似性高，匹配率大，如圖2所示；當相鄰兩幀發(fā)生了場景突變的時候，由于相鄰兩幀的場景完全變化，基本沒有相似性，匹配率也隨之大大降低，如圖3所示。因此可通過SIFT特征點匹配算法實現(xiàn)場景突變檢測。

表1　實驗數(shù)據(jù)舉例

3.2　SIFT特征點提取實時性驗證

由于視頻的場景突變檢測算法在實際的應(yīng)用當中實時性指標較為重要，因此本文通過視頻片段驗證SIFT算法在特征點提取方面是否可以達到實時性的要求。

表2　SIFT特征點提取耗時統(tǒng)計

從表2可以看出，對于場景較復雜的動畫，其1 922幀的特征點提取時間為72.717 6 s，平均1 s可以提取26.431 0 frames。人眼能識別的最低幀數(shù)是24 frames/s，就是說畫面每秒鐘變換24次以上人眼就會覺得連貫，低于24 frames/s就會覺得有停頓感。常見的電視等播放器可以達到25 frames/s，本實驗中可以達到26 frames/s左右，因此基本可以達到SIFT特征點實時提取的要求。

3.3　視頻場景突變檢測算法實驗數(shù)據(jù)

為了驗證本文算法的有效性，本文挑選使用了不同視頻片段作為實驗數(shù)據(jù)，包括新聞、電影與動畫等，均為AVI格式視頻。實驗數(shù)據(jù)中場景突變點信息如表3所示。

表3　視頻中場景突變點

評價檢測算法最常用的是查全率和查準率，標準檢測算法的有效性指標定義如下：

(3)

(4)

式中，Nm，Nf，Nc分別為漏檢數(shù)、誤檢數(shù)、正確檢測數(shù)。在場景突變檢測中，查全率用來證明這個場景變化檢測算法在實際應(yīng)用中的有效性，虛檢率用來說明當達到一定檢全率時所要付出的代價。

視頻場景突變檢測的實驗結(jié)果如表4所示。實驗結(jié)果中平均查全率為95.79%，平均查準率為94.45%。查準率略低于查全率，這是由于視頻中的人工編輯多而復雜，場景內(nèi)出現(xiàn)大范圍的突然的運動變化，從而容易造成的誤判。

表4　本算法實驗結(jié)果

3.4　本算法與其他算法比較

文獻[17]中提出針對二維視頻編碼的運動幀差圖像的多測度聯(lián)合場景突變檢測算法，對視頻ishop，本文與文獻[17]比較結(jié)果見表5。視頻ishop是一段場景變化較多的MV視頻，總共有2 752幀，其中場景突變總數(shù)為53個。從表5可以看出，本文算法的查全率比文獻[17]高3.78%，查準率比文獻[17]高4.88%。

表5　視頻ishop的比較結(jié)果

文獻[18]在信息論的基礎(chǔ)上，提出了一種結(jié)合信息論和運動信息的鏡頭檢測算法，通過視頻探索《北極熊》與文獻[18]比較結(jié)果見表6所示，視頻探索《北極熊》是一段紀錄片，總共有39 687 frames，其中場景突變共有127個。本文算法的查全率比其高1.58%，查準率比其高0.83%。由于此視頻段中北極場景較多，白雪皚皚的背景下特征點提取受到一定的限制，故本文算法與文獻[18]比較后提高較少。

表6　視頻探索《北極熊》的比較結(jié)果

4結(jié)論

本文提出了一種基于SIFT特征點匹配的場景突變檢測算法。通過SIFT特征點提取與特征點匹配算法相結(jié)合，實現(xiàn)了視頻的場景突變檢測。本算法可以在視頻幀進行圖像匹配的過程中對場景的變化情況進行判斷，同時SIFT特征點提取可以滿足實時性的要求，因此該算法不僅應(yīng)用范圍較廣，還可以保證場景突變檢測的精度，視頻場景突變檢測平均查全率為95.79%，平均查準率為94.45%，表明了該算法在視頻場景突變檢測中的有效性。

參考文獻：

[1]鄒曉燕.基于H.264壓縮域的視頻檢索研究[D].山東:山東大學,2011.

ZOU X Y. Video retrieval based H.264 compressed domain[D]. Shandong:Shandong University,2011.(in Chinese)

[2]薛立勤,張秀娟.基于運動分析的視頻檢索方法[J].計算機工程與應(yīng)用,2008,44(25):152-154.

XUE L Q,ZHANG X J. Video retrieval method based on motion analysis[J].ComputerEngineeringandApplications,2008,44(25):152-154.(in Chinese)

[3]朱耀麟，李倩.視頻檢索常用的鏡頭分割方法的研究[J].電視技術(shù)，2014，38(3):178-181.

ZHU Y L,LI Q .Survey of used methods for partitioning video into shots in video indexing[J].IdeoEngineering，2014，38(3):178-181.(in Chinese)

[4]魏瑋，劉靜,王丹丹.視頻鏡頭分割方法綜述[J].計算機系統(tǒng)應(yīng)用,2013,22(1):5-8.

WEI W,LIU J,WANG D D. Survey of methods for partitioning video into shots in video[J].ComputerSystem&Applications,2013,22(1):5-8.(in Chinese)

[5]劉艷紅.視頻鏡頭分割算法綜述[J].科技創(chuàng)新與應(yīng)用,2014(16):49-50.

LIU Y H. Survey of methods for partitioning video into shots in video[J].ScientificandTechnologicalInnovationandApplication,2014(16):49-50.(in Chinese)

[6]VLACHOS T. Cut detection in video sequences using phase correlation[J].IEEESignalProcessingLetters,2000,7(7):173-175.

[7]EOM Y,PARK S,YOO S,etal..AnanalysisofSceneChangeDetection[M]. Anaheim,California,USA: International Conference on Semantic Computing,2015:470-474.

[8]HONG S,CHO B,CHOE Y.AdaptiveThresholdingforSceneChangeDetection[M]. Berlin:International Conference on Consumer Electronics,2013:75-78.

[9]LEE M H,YOO H W,JANG D S. Video scene change detection using neural network:improved ART2[J].ExpertSystemswithApplications,2006,31(1):13-25.

[10]唐劍琪,謝林江,袁慶生,等.基于ORB的鏡頭邊界檢測算法[J].通信學報,2013,34(11):184-190.

TANG J Q,XIE L J,YUAN Q SH,etal.. ORB-based shot boundary detection algorithm[J].Communications,2013,34(11):184-190.(in Chinese)

[11]吳偉交.基于SIFT特征點的圖像匹配算法[D].武漢:華中科技大學,2013.

WU W J. Image matching algorithm based on SIFT feature points[D]. Wuhan:Huazhong University of Science and Technology,2013.(in Chinese)

[12]許佳佳.結(jié)合Harris與SIFT算子的圖像快速配準算法[J].中國光學,2015,8(4):574-581.

XU J J. Fast image registration method based on Harris and SIFT algorithm[J].ChineseOptics,2015,8(4):574-581.(in Chinese)

[13]高文,朱明,賀柏根,等.目標跟蹤技術(shù)綜述[J].中國光學,2014,7(3):365-375.

GAO W,ZHU M,HE B G,etal.. Overview of target tracking technology[J].ChineseOptics,2014,7(3):365-375.(in Chinese)

[14]聶海濤,龍科慧,馬軍,等.采用改進尺度不變特征變換在多變背景下實現(xiàn)快速目標識別[J].光學 精密工程,2015,23(8):2349-2356.

NIE H T,LONG K H,MA J,etal.. Fast object recognition under multiple varying background using improved SIFT method[J].Opt.PrecisionEng.,2015,23(8):2349-2356.(in Chinese)

[15]王睿,朱正丹.融合全局-顏色信息的尺度不變特征變換[J].光學 精密工程,2015,23(1):295-301.

WANG R,ZHU ZH D. SIFT matching with color invariant characteristics and global context[J].Opt.PrecisionEng.,2015,23(1):295-301.(in Chinese)

[16]劉志文,劉定生,劉鵬.應(yīng)用尺度不變特征變換的多源遙感影像特征點匹配[J].光學 精密工程,2013,21(8):2146-2153.

LIU ZH W,LIU D SH,LIU P. SIFT feature matching algorithm of multi-source remote image[J].Opt.PrecisionEng.,2013,21(8):2146-2153.(in Chinese)

[17]馬彥卓,常義林,楊海濤.應(yīng)用于視頻編碼的實時多測度聯(lián)合突變場景切換檢測算法[J].光子學報,2010,39(6):1058-1063.

MA Y ZH，CHANG Y L，YANG H T. Used in video coding mutations in real-time multi measure joint scene change detection algorithm[J].ActaPhotonicaSinica,2010,39(6):1058-1063.(in Chinese)

[18]易璨.基于信息熵和運動信息的視頻鏡頭檢測[D].湘潭:湘潭大學,2006.

YI C. Shot detection based on information entropy and motion information[D]. Xiangtan:Xiangtan University,2006.(in Chinese)

李楓(1990—)，女，黑龍江佳木斯人，碩士研究生，主要從事場景變化檢測方面的研究。E-mail:1006407131@qq.com

趙巖(1971—)，女，吉林遼源人，教授，博士生導師，2003年于吉林大學獲得博士學位，主要從事圖像與視頻編碼、立體視頻處理方面的研究。E-mail:zhao_y@jlu.edu.cn

《發(fā) 光 學 報》

—EI核心期刊 (物理學類； 無線電電子學、 電信技術(shù)類)

《發(fā)光學報》是中國物理學會發(fā)光分會與中國科學院長春光學精密機械與物理研究所共同主辦的中國物理學會發(fā)光分會的學術(shù)會刊。 該刊是以發(fā)光學、 凝聚態(tài)物質(zhì)中的激發(fā)過程為專業(yè)方向的綜合性學術(shù)刊物。

《發(fā)光學報》于1980年創(chuàng)刊， 曾于1992年， 1996年， 2000年和2004年連續(xù)四次被《中文核心期刊要目總覽》評為“物理學類核心期刊”， 并于2000年同時被評為“無線電電子學、 電信技術(shù)類核心期刊”。2000年獲中國科學院優(yōu)秀期刊二等獎。 現(xiàn)已被《中國學術(shù)期刊(光盤版)》、 《中國期刊網(wǎng)》和“萬方數(shù)據(jù)資源系統(tǒng)”等列為源期刊。 英國《科學文摘》(SA)自1999年； 美國《化學文摘》(CA)和俄羅斯《文摘雜志》(AJ)自2000年； 美國《劍橋科學文摘社網(wǎng)站》自2002年； 日本《科技文獻速報》(CBST， JICST)自2003年已定期收錄檢索該刊論文； 2008年被荷蘭“Elsevier Bibliographic Databases”確定為源期刊; 2010年被美國“EI”確定為源期刊。2001年在國家科技部組織的“中國期刊方陣”的評定中， 《發(fā)光學報》被評為“雙效期刊”。2002年獲中國科學院2001～2002年度科學出版基金“擇重”資助。2004年被選入《中國知識資源總庫·中國科技精品庫》。本刊內(nèi)容豐富、 信息量大，主要反映本學科專業(yè)領(lǐng)域的科研和技術(shù)成就， 及時報道國內(nèi)外的學術(shù)動態(tài)， 開展學術(shù)討論和交流， 為提高我國該學科的學術(shù)水平服務(wù)。

《發(fā)光學報》自2011年改為月刊， A4開本， 144頁， 國內(nèi)外公開發(fā)行。 國內(nèi)定價： 40元， 全年480元， 全國各地郵局均可訂閱。 《發(fā)光學報》歡迎廣大作者、 讀者廣為利用， 踴躍投稿。

地址： 長春市東南湖大路3888號

《發(fā)光學報》編輯部

郵編： 130033

電話： (0431)86176862， 84613407

E-mail: fgxbt@126.com

國內(nèi)統(tǒng)一刊號： CN 22-1116/O4

國際標準刊號： ISSN 1000-7032

國內(nèi)郵發(fā)代號： 12-312

國外發(fā)行代號： 4863BM

http://www.fgxb.org

Video scene mutation change detection

combined with SIFT algorithm

LI Feng, ZHAO Yan*, WANG Shi-gang, CHEN He-xin

(CollegeofCommunicationEngineering,JilinUniversity,Changchun130012,China)

*Correspondingauthor,E-mail:zhao_y@jlu.edu.cn

Abstract:Video scene change detection has a very important role for video annotation and semantic search. This paper proposes a scene mutation change detection algorithm combined with SIFT(Scale Invariant Feature Transformation) feature point extraction. Firstly, the feature points of two adjacent video frames are extracted respectively using SIFT algorithm and the number of them is counted respectively. Then image matching of the two adjacent frames of the video is performed and the number of matching feature points is counted. Finally, the ratio between the number of matching feature points of the current frame and the number of matching feature points of its previous frame is calculated, so as to judge the scene change by this ratio. The average scene mutation change detection rate in the experimental results can reach 95.79%. The proposed algorithm can judge scene change during image matching. Therefore, the algorithm can not only be applied widely, but also guarantee the accuracy of scene change detection. Experimental results show the effectiveness of the proposed algorithm.

Key words:SIFT;feature point matching;scene change detection

作者簡介：

中圖分類號：TN919.8

文獻標識碼:A

doi:10.3788/CO.20160901.0074