基于關鍵幀多特征融合的視頻拷貝檢測

張興忠,李 皓,張三義

(太原理工大學 計算機科學與技術學院,太原 030024)

基于關鍵幀多特征融合的視頻拷貝檢測

張興忠,李 皓,張三義

(太原理工大學 計算機科學與技術學院,太原 030024)

針對視頻拷貝檢測中檢索速度問題,提出一種基于關鍵幀多特征融合的類局部敏感哈希索引方法,將存在拷貝片段的視頻映射到同一個哈希桶中,減少檢索的范圍,達到提高檢索速度的目的。該算法首先對視頻進行鏡頭分割提取關鍵幀,為了提高檢測精度,分別提取了灰度序全局特征、基于關鍵點的希爾伯特特征、ORB(Oriented FAST and Rotated BRIEF)局部特征,綜合利用全局特征和局部特征兩者各自的優勢;然后根據視頻關鍵幀序列建立了類局部敏感哈希索引,利用建立好的索引獲得拷貝檢測結果。實驗結果表明,該方法在保證檢測精度的同時,速度上也有很大提升,具有重要的應用價值。

視頻拷貝檢測;關鍵幀;ORB;類局部敏感哈希;關鍵點希爾伯特

隨著信息化社會的高速發展,多媒體尤其是圖像和視頻已經滲透到了我們的日常生活中,如何對圖像、視頻進行版權保護成為了一項重要的研究課題,本文研究視頻版權保護中,如何在保證高檢測精度的前提下實現快速視頻拷貝檢測。

視頻拷貝檢測技術可以用于檢測視頻是否存在拷貝或者重復片段,是數字視頻版權保護的關鍵支撐技術。一般地,視頻拷貝檢測技術是從提取視頻幀的內容來實現拷貝檢測,通過比較視頻幀內容的相似程度來判斷兩個視頻是否被篡改。

目前基于內容的視頻拷貝檢測技術[1-2]是基于視頻幀特征的方法來實現。全局特征檢索方法[1]可以實現快速的拷貝檢測且檢索效果不錯,但是對于復雜性的拷貝效果差。局部特征檢索方法[2]可以檢測出多種拷貝,但是由于局部特征存在特征描述點較多的問題,匹配速度慢。

筆者提出一種基于關鍵幀多特征融合的視頻索引方法。該方法分別提取了灰度序全局特征、基于關鍵點的希爾伯特特征和ORB局部特征,綜合利用他們各自的特點,同時借鑒局部敏感哈希的思想,將相似的視頻即存在拷貝視頻片段的視頻放到同一個哈希桶中,減少檢索的范圍,從而達到在保證檢索精度的同時,實現快速檢索的目的。

1 相關研究

基于內容的視頻拷貝檢測技術主要包括基于哈希的方法、基于視覺詞袋的方法以及降維方法。局部敏感哈希(Local Sensitive Hashing, LSH)算法[3]是一種有效的近似相似性查詢技術,通過哈希函數把相似的視頻映射到同一個哈希桶中,可以有效減少檢索范圍并加快檢索。文獻[4]引用了局部敏感哈希的方法用于網絡視頻重復檢測,加快了檢索速度?；谝曈X詞袋(Bag of Words)[5]的方法通過k-means聚類的方法統計視頻關鍵幀庫中出現的所有特征,相近的特征歸為一類,將聚類中心作為詞袋。利用視覺詞袋量化視頻關鍵幀特征,采用詞頻或直方圖來表示圖像。除此之外,還有一些降維方法,如文獻[6-7]提出采用流行學習中的局部線性嵌入降維的方法降低視頻關鍵幀特征的維度來加快檢索速度。

2 視頻關鍵幀及其特征提取

視頻關鍵幀提取采用基于鏡頭的關鍵幀提取策略,采用的是文獻[9]中基于相鄰幀的灰度直方圖的方法來提取關鍵幀,在此基礎上添加了去重操作來保證關鍵幀的精確性。本節主要介紹本文所采用的三種視頻關鍵幀特征的提取技術。

2.1 空間灰度序特征

空間灰度序特征是一種具有排序性質的全局特征。其提取過程首先將視頻幀圖像分割為n×n個等同的圖像塊,文中n取3;然后分別計算各圖像塊的灰度平均值;最后對求得的各個圖像塊的灰度平均值進行排序,得到的排序編碼作為該視頻幀圖像的灰度序特征。

2.2 基于關鍵點的希爾伯特特征

希爾伯特曲線(Hilbert Curve)是由德國數學家David Hilbert在1891年提出,它是一種十分神奇的曲線,該曲線是一種能填充滿一個平面正方形的分形曲線,其特點是將一個平面正方形平均劃分為n×n的均勻小分塊,每個分塊是一個小正方形,從正方形四個角的任意一個小分塊開始,勾畫一條曲線充滿平面正方形的每個正方形小分塊,如圖1所示是一個劃分為4×4均勻小分塊的希爾伯特曲線示意圖。

圖1 基于關鍵點的希爾伯特特征

將希爾伯特曲線引入到視頻關鍵幀的特征提取中,把視頻關鍵幀均勻劃分,勾勒一條希爾伯特曲線填充滿整個視頻關鍵幀的每個小分塊,就可以得到一個視頻關鍵幀的希爾伯特全局特征。

局部特征提取的視頻關鍵幀的局部關鍵點位置均為可標識該視頻關鍵幀的關鍵像素點,它們可以有效地代表該視頻關鍵幀。兼顧局部關鍵點的重要性和希爾伯特曲線的全局完整性筆者提出了基于關鍵點的希爾伯特特征。

基于關鍵點的希爾伯特特征的提取流程如下所示:

1) 利用ORB特征提取策略獲取視頻關鍵幀的局部關鍵點位置;

2) 將視頻關鍵幀劃分為4×4均勻大小的塊,統計各分塊中局部關鍵點的個數和對應的灰度值,并計算出各分塊的平均灰度值,如圖1中所示計算左圖視頻關鍵幀的平均灰度值為右圖所示;

3) 對各個分塊的平均灰度值采用希爾伯特曲線進行串聯,如圖1中右圖的正方形所示,從左下角小正方形分塊開始,用一條不間斷且能通過所有均勻小正方形分塊的曲線連接起來;

4) 勾畫出希爾伯特曲線后,視頻關鍵幀的希爾伯特特征采用平均灰度值可以表示為一個16位的序列,以圖1為例該視頻關鍵幀形成的16位的平均灰度值序列則表示為{186,0,78,182,0,0,133,129,110,120,0,0,0,171,0,121},對該灰度值序列采用如下策略轉換為二值特征序列。記平均灰度值序列為a[i],0≤i<16,將新生成的二值特征序列記為b[j],0≤j<15,那么序列b的計算過程如式(1)所示,

(1)

得到最終的15位的二值希爾伯特特征為100 100 110 100 010。

2.3 ORB特征

ORB特征是對二值特征描述符BRIEF的改進,它克服了BRIEF特征不具備旋轉不變性和對噪音敏感的缺陷。ORB特征提取過程如下。

1) 快速關鍵點提取。首先采用FAST-9方法檢測視頻幀的關鍵點,然后采用Harris角檢測方法來對FAST關鍵點進行排序,選取排序最高的n個關鍵點;提取視頻幀的尺度金字塔,并對金字塔的每層提取FAST特征;最后定位強度質心。

2) 基于旋轉的BRIEF(rBRIEF)。BRIEF是從視頻幀塊的一系列二值強度測試集中構建二值特征描述符。對于一個平滑的圖像塊p,一個二值測試τ定義如公式(2)所示:

(2)

式中:p(x)是在點x處的p的強度。

ORB特征采用貪婪搜索法從所有可能的二值測試集中尋找既有高變化性(平均值接近0.5)又不相關的特征,直至獲得256個測試集。這個算法得到一組不相關的平均值接近0.5的測試集結果,這個結果叫做基于旋轉的BRIEF,簡稱rBRIEF。

3 基于關鍵幀多特征融合的視頻拷貝檢測

3.1 類局部敏感哈希索引的建立

類局部敏感哈希索引的示意圖如圖2所示。初始時哈希桶大小為空,每一個哈希桶有一個代表視頻,即該哈希桶中存儲的是該代表視頻的拷貝視頻。每個哈希桶內部包含n個拷貝視頻集,數目n是代表視頻的關鍵幀序列數目,每個視頻關鍵幀的視頻集合是由存在該視頻關鍵幀的拷貝片段或重復片段的視頻集組成。

圖2 類局部敏感哈希索引

類局部敏感哈希索引的建立流程圖如圖3所示,建立過程如下:

1) 輸入一個視頻,如果哈希桶為空,則將該視頻放入哈希桶1,并將該視頻作為哈希桶的代表視頻,建立該視頻關鍵幀序列的拷貝視頻集合;如果哈希桶不為空,則轉入步驟2進行處理;

2) 將輸入視頻遍歷每個哈希桶,計算與每個哈希桶代表視頻的相似度,如果與某哈希桶代表視頻相似,則采用基于公共視頻幀序列[9]的方法,計算出相似的視頻關鍵幀序列,放入對應的視頻關鍵幀的拷貝視頻集中;

3) 如果輸入視頻未執行,則繼續執行步驟1和2,直到所有視頻遍歷完畢;

4) 所有視頻遍歷完成后,還需要進行整合處理。因為一些哈希桶代表視頻的拷貝視頻集僅有一個視頻,說明屬于特例,不存在該視頻的拷貝,在此處的處理方法是將哈希桶中僅有一個視頻的哈希桶整合為一個哈希桶,剩下的哈希桶保持不變。

圖3 索引建立流程圖

3.2 檢索流程

輸入一個查詢視頻,遍歷哈希桶計算與每一個哈希桶代表視頻的相似度,如果與某代表視頻相似,則說明該哈希桶中存在查詢視頻的拷貝視頻,采用基于公共視頻幀的方法計算出代表視頻中存在拷貝片段的關鍵幀序列,融合公共視頻關鍵幀對應的拷貝視頻集,添加到視頻拷貝結果集合。繼續遍歷哈希桶直至遍歷完畢,將每個哈希桶的結果去重求并集得到最終的視頻拷貝檢測結果。

4 實驗結果及分析

本文實驗均在3.4 GHz, 4G內存,Windows 7操作系統下用C++語言實現,采用OpenCV2.4.8標準庫。數據集選取自CC_WEB_VIDEO[10]數據集,選用8組視頻進行測試,每組視頻均存在各種拷貝。

用準確率、召回率和檢索時間作為評測指標。

1) 準確率Precision的計算公式如式(3)所示,

Precision=QC/PResult .

(3)

式中:QC表示檢索結果中包含的正確的檢索結果數;PResult表示檢索結果數目。

2)召回率Recall的計算公式如式(4)所示,

Recall=QC/RResult .

(4)

式中:QC表示檢索結果中正確的檢索結果數;RResult表示檢索集中總共的準確結果數。

3) 檢索時間。完成一次檢索消耗的時間即從開始檢索到檢索結束耗費的時間。

圖4 召回率比較

為了驗證本文提出的方法的有效性,與文獻[1]中灰度序的方法和bag-of-words檢索方法(下面簡述為BOW-300)進行了比較。采用k-means聚類算法,字典數目選為300,匹配采用基于動態規劃方法。圖4、圖5和表1為采用三種方法對召回率、準確率和檢索時間比較。

圖5 準確率比較

從圖4召回率的結果可以看出,文獻[1]灰度序方法和BOW-300的召回率可以保持很高的水平,多組實驗結果均為100%,比本文的方法要好,但是從圖5準確率的結果來看,雖然灰度序的方法和BOW-300的方法召回率很高,但是準確率很低,并不如本文的方法。準確率和召回率是兩個折衷的評判標準,兩者均保持較高水平,檢索結果才更有說服力,本文的方法在召回率和準確率兩個指標上表現均穩定,保證了較高的檢索精度。

從表1的結果來看,本文的方法與文獻[1]灰度序全局特征的方法相比慢了點,這是由于灰度序是一種全局特征方法,特征維度低,故而檢索速度快,但是文獻[1]灰度序方法犧牲了精度,BOW-300的方法時間耗費較長是由于雖然通過聚類方法減少了特征維數,但是相似度的計算和匹配過程仍然耗費了很多時間。本文的方法平均檢索時間相對其他兩種方法是一個折衷的提升,由于采用了基于關鍵幀多特征融合的拷貝檢測算法,以哈希桶為檢索單元,在保證檢索精度的同時,縮小檢索范圍,檢索時間獲得較大提升。

表1 檢索時間的比較 s

5 結論

本文提出的基于關鍵幀多特征融合的視頻拷貝檢測方法即利用灰度序、基于關鍵點的希爾伯特特征和ORB特征建立的類局部敏感哈希索引,在保證高召回率和準確率的同時,在檢索時間上獲得了較大提升。今后的研究考慮為一種魯棒的視頻關鍵幀特征建立快速的索引方法,快速有效地檢測到多種拷貝攻擊;另一條思路圍繞時空特征,發掘出一種魯棒的時空特征來表示視頻片段,依此來檢索視頻拷貝片段。

[1] Hua X S,Chen X,Zhang H J.Robust video signature based on ordinal measure[C]∥Image Processing,2004. ICIP′04.2004 International Conference on.IEEE,2004,1:685-688.

[2] Ates T K,Esen E,Saracoglu A,et al.Content based video copy detection with local descriptors[C]∥Signal Processing and Communications Applications Conference (SIU),2010 IEEE 18th.IEEE,2010:49-52.

[3] Lv Q,Josephson W,Wang Z,et al.Multi-probe LSH:efficient indexing for high-dimensional similarity search[C]∥Proceedings of the 33rd international conference on Very large data bases.VLDB Endowment,2007:950-961.

[4] 王洪峰,劉辛.基于位置敏感哈希的網絡視頻重復檢測[J].計算機應用研究,2012,29(5):1954-1958.

[5] Nowak E,Jurie F,Triggs B.Sampling strategies for bag-of-features image classification[M]∥Computer Vision-ECCV 2006.Springer Berlin Heidelberg,2006:490-503.

[6] 聶秀山,劉琚,孫建德,等.基于局部線性嵌入的視頻拷貝檢測方法[J].電子與信息學報,2011,33(5):1030-1034.

[7] 聶秀山.基于魯棒哈希的視頻拷貝檢測技術研究[D].山東大學,2011.

[8] Rublee E,Rabaud V,Konolige K.et al.ORB:an efficient alternative to SIFT or SURF[C].2011,International Conference on Computer Vision(ICCV),2564-2571.

[9] 張三義,張興忠,郝曉燕.基于ORB和灰度序特征的視頻拷貝檢測[J].計算機應用研究,2014,31(10):3113-3116.

[10] Xiao Wu,Alexander G.Hauptmann and chong-wah ngo practical elimination of near-duplicates from web video search[C].ACM International Conference on Multimedia (ACM MM’07),Augsburg, Germany,Sep.2007:218-227.

(編輯：朱 倩)

Video Copy Detection Based on Key Frame Multi-feature Fusion

ZHANG Xingzhong,LI Hao,ZHANG Sanyi

(CollegeofComputerScienceandTechnology,TaiyuanUniversityofTechnology,Taiyuan030024,China)

Retrieval speed is an important issue in video copy detection. This paper proposed a fast video copy detection method, which uses a local sensitive hashing index to achive fast retrieval by mapping videos with similar clips into the same buckets, and combines multi-features of key frames to achieve high accuracy. To improve retrieval accuracy, the method extracts key frames by using shot segmentation techniques, and then obtains the Hilbert feature based on key points, ordinal measure feature and ORB (Oriented FAST and Rotated BRIEF) feature from key frames. This allows the method make full use of both local features and global features. The hash index is built by hash the combined features. Experimental results show that this proposed method not only achieves high precision and recall rate, but also has high spead.

video copy detection;key-frames;oriented FAST and Rotated BRIEF (ORB);local sensitive hashing;hilbert feature based on key points

1007-9432(2015)05-0566-05

2015-05-13

國家科技支撐項目子課題:(2012BAH04F02-2)；教育部歸國留學人員科研啟動基金(2010-1174)；人社部留學人員科技活動項目(2011-508)；山西省國際科技合作計劃基金資助項目：中美、中加合作云計算環境下網站系統架構和數據庫系統建模技術研究(2012081034-2)

張興忠(1964-)，男，山西汾陽人，副教授，主要研究方向為嵌入式系統、軟件工程、模式識別等，(E-mail)1659898176@qq.com

TP391.41

A

10.16355/j.cnki.issn1007-9432tyut.2015.05.017