Delaunay三角剖分下的視頻指紋算法

李曉雨,聶秀山,2,董 飛,尹義龍,2

1(山東財經大學 計算機科學與技術學院,濟南 250014)

2(山東大學 計算機科學與技術學院,濟南 250014)

3(山東師范大學 傳媒學院,濟南 250014)

1 引 言

近年來,隨著信息技術和通信技術的發展,手機、平板電腦等移動設備得以迅速普及,用戶可以隨時隨地的拍攝視頻,并將視頻上傳到互聯網,這就使得網絡上視頻的數量以幾何式的速度激增,在這種情況下,互聯網上經常出現盜用他人視頻、未經作者允許隨意再次上傳視頻等不道德、不合法的行為發生.因此,在面對這些海量視頻時,如何保護原作者版權,如何監管視頻非法拷貝,如何過濾重復視頻等一系列的問題成為亟待解決的難題.為解決這一系列的問題,研究者提出了視頻指紋這一概念.將視頻指紋類比于人的指紋,人的指紋可以唯一的代表一個人,并且可以通過指紋來追溯到特定的人,視頻指紋為視頻內容的標識,是從視頻內容中提取的視頻特征表示,可以唯一代表相應視頻內容.視頻服務管理機構可以通過視頻指紋來追溯某一特定視頻,也可以通過比對視頻指紋來判斷視頻內容是否相似,進而為解決視頻非法拷貝和重復視頻檢索提供技術支撐.因此,對視頻指紋技術的研究具有較大的應用價值.

自視頻指紋的概念提出以來,視頻指紋相關技術的研究取得了很多成果,現有的視頻指紋算法大體可分為三類:

第一類是基于空域的方法,這類方法主要以視頻中每一幀的空域屬性為基礎,使用亮度、灰度等魯棒性較好、復雜度較低的特征來生成視頻指紋.Oostveen[1]等學者將視頻幀分塊,以各亮度塊的偏微分特征作為視頻指紋.Lee[2]等學者將視頻幀分塊,而后計算每塊的亮度梯度生成視頻指紋.

第二類是基于時域的方法,這類方法主要使用視頻相鄰幀在時間上的關系來生成視頻指紋.Chen[3]提出了一種基于時域順序的視頻指紋方案,對視頻幀分塊,求每一塊的像素均值,并通過定義一個時域窗口,對窗口內每一幀相同位置的塊進行排序,從而構造視頻指紋.Radharkrishan[4]提出利用幀與幀之間亮度差分生成視頻指紋的方法.

第三類是基于變換域的方法,這類方法主要使用視頻幀在變換域中的屬性生成視頻指紋.Cosku[5]等通過三維離散余弦(3D-DCT)變換,將視頻變換到變換域,并利用頻率特征生成視頻指紋.其他研究者還提出了諸如基于奇異值分解[6]、極坐標傅里葉變換[7]等變換域技術生成視頻指紋的方法.

以上的三類方法都各有優劣.基于空域的視頻指紋算法所采用的空域特征在全局幾何變換，如旋轉、放射變換等情況下具有較好的魯棒性,且復雜度較低,但視頻的幀與幀之間順序排列、密切相關,當改變幀與幀之間的順序時就會出現較大的誤差,使視頻指紋性能大幅下降.基于時域的視頻指紋算法能夠體現視頻幀與幀之間的相互聯系,在對比度變化、添加噪聲等基于空域的視頻算法表現較弱的視頻攻擊下具有良好的魯棒性,但由此類方法生成的視頻指紋內部分量之間高度相關,對于局部信息非常敏感,一個分塊內容的改變可能導致視頻指紋的大幅變動,使得算法性能下降.基于變換域的視頻指紋算法所使用的的頻率特征能夠在旋轉、裁剪等幾何變換中保持穩定,具有良好的魯棒性,但由于此類方法使用的傅里葉變換、小波變換等變換域技術常具有較高的復雜性,對實際應用不利.隨著對視頻指紋相關技術研究的深入,研究者不再單一的使用某一種特征來生成視頻指紋,而是根據實際需求,結合不同類型的特征來生成性能更好的視頻指紋[8-10].Lee[11]等提出了一種將空間域與變換域結合的方法,該方法首先將視頻幀分塊,計算各塊梯度方向質心(CGO),然后根據雙對稱增強算法和濾波量化器生成視頻指紋.

一般來說,魯棒性是評價一個視頻指紋算法優劣的重要標準.在一定數量的視頻中識別出完全相同的、未加修改的視頻是比較容易的.但是,當視頻經歷了亮度、角度、分辨率等參數的變化,或是噪聲添加、旋轉、平移等操作,導致視頻在視覺上出現一定程度的改變后就難以準確的與原始視頻進行匹配.因此,視頻指紋在經歷以上的修改或攻擊后的魯棒性就變得非常重要.為增強視頻指紋的魯棒性,本文充分利用視頻的時空信息,從空域特征入手,再與時域特征相結合,進而生成視頻指紋.具體來說,在空域方面,對視頻幀進行分塊,將每一塊的灰度均值作為特征描述值.在時域方面,將順序排列的視頻幀的每一塊看做一個帶有時間序列標志的三維特征點,并對這些特征點的集合進行Delaunay三角剖分.三角剖分后形成一系列相關四面體,將這些四面體的特征值均值作為視頻指紋,使視頻指紋兼具空域性與時域性.同時由于Delaunay三角剖分具有較好的穩定性,使視頻指紋的魯棒性也得以加強.

本文的主要貢獻在于創新性的利用Delaunay三角剖分構建空間四面體,來挖掘視頻的時空特征,進而生成視頻指紋.Delaunay三角剖分在部分特征點遭受擾動的情況下,剖分后得到的四面體仍具有較好的穩定性,因此,本文算法與現有基于時空信息的視頻指紋算法相比,在充分利用視頻時空信息的同時,又具有較強的魯棒性.

2 Delaunay三角剖分下的視頻指紋算法

本文算法的框架圖如圖1所示,主要分為視頻預處理、特征點提取,Delaunay三角剖分和視頻指紋生成四個部分.首先對視頻進行預處理,然后對每一幀進行分塊處理,每一塊作為一個特征點,每一塊的灰度均值作為特征描述值,其次對特征點的集合進行Delaunay三角剖分,得到一個四面體集合,該集合內的四面體不僅包含了同一幀內特征點的相互關聯信息,還包含了不同幀之間特征點的相互關聯信息,最后把四面體四個頂點的灰度均值作為視頻指紋.

圖1 本文算法框架圖Fig.1 Algorithm frame

2.1 預處理

在生成視頻指紋的過程中,由于視頻的幀數、分辨率、幀頻率等原始數據參數的不同,可能會使得生成視頻指紋的長度、規格各不相同,會對視頻指紋之間的匹配產生影響,使檢測的準確率下降.為了避免這種影響,本文首先要對視頻進行預處理操作,使數據庫中視頻的物理參數在生成視頻指紋之前就相互統一.預處理并沒有改變視頻的內容,因此預處理在視頻指紋算法中有著廣泛的應用.本文在對視頻進行預處理時,首先對視頻片段進行均勻采樣,采樣標準為64幀,然后把采樣后的視頻幀分辨率統一設置為64×64.

2.2 特征點提取

特征點提取是從視頻中提取含有視頻幀重要特征的點,特征點對圖像畸變具有一定的魯棒性,在圖像、視頻匹配中被廣泛應用.

為提高算法效率,本文通過像素分塊的方式構造特征點,具體做法是:在空域上,對按照標準采樣、統一分辨率的視頻幀時間序列中的每一個視頻幀,按順序進行分塊處理,將每個視頻幀均等分塊,然后把每一塊看做一個特征點,特征點按行的順序依次排列,分塊及提取特征點的方式如圖2所示.按照此方法,對不同視頻提取的特征點個數相同.

圖2 特征點提取Fig.2 Extract feature points

得到視頻幀的特征點后,把每個特征點的坐標記為一個三維向量(x,y,z).x代表所在位置的行序號,y代表所在位置的列序號,z代表該特征點所屬的視頻幀在整個視頻幀時間序列中的序號,表示視頻幀的時間信息.集合B表示所有特征點的集合:B={B1,B2,…,Bn}.

例如,特征點B1的三維坐標為(1,1,1),則其表示視頻幀時間序列中第一幀的第一行、第一列的特征點.

然后計算每一個分塊的灰度平均值,并將其作為對應特征點的特征描述值,集合G表示特征值的集合:G={G1,G2,…,Gn}.

2.3 Delaunay三角剖分

通過視頻幀分塊獲取的特征點,其特征描述值僅包含對應分塊內的灰度信息,即空間信息,而包含時間信息的視頻特征點的坐標尚未得到利用.為了構造既包含空間信息又包含時間信息的視頻指紋,就需要利用視頻特征點的坐標.將特征點集合看作視頻空間中的散點集合,通過Delaunay三角剖分[12],建立視頻幀與幀之間的特征點的聯系,這種聯系能夠體現視頻的時間信息.

圖3 Delaunay三角剖分Fig.3 Delaunay triangulation

Delaunay三角剖分的目的在于將空間內有限的散點集合剖分成互不交叉的、形狀均勻的三角網格,如圖3所示.這就使得Delaunay三角剖分的結果具有兩個特點:一是對同一個散點集進行Delaunay三角剖分后得到的三角網格是唯一的;二是Delaunay三角剖分后形成的三角網格中的每一個三角形的最小角最大,即避免出現狹長的三角形.第一個特點能夠在視頻特征點之間建立唯一的相互聯系,不隨重新進行Delaunay三角剖分而改變相互聯系.第二個特點能在視頻特征點之間均勻地建立相互聯系,避免了在極遠點之間,即攜帶時間信息差異較大的點之間建立相互聯系.

圖4 特征點變動前后Delaunay三角剖分對比Fig.4 Contrast of Delaunay triangulation with feature point changing

同時,Delaunay三角剖分具有較強的魯棒性.對于一個已知的散點集來說,當改變一個點或部分點的位置之后再次進行Delaunay三角剖分時,除了包含發生變動點的三角網格產生變化外,其他的三角網格保持不變,如圖4 所示.視頻易受噪聲、對比度、旋轉等多種因素影響,使部分特征點發生變化,Delaunay三角剖分較強的魯棒性可以將部分特征點變動引起的整體變動降低,這是這一技術被應用于視頻指紋生成的主要原因.

以上特性對于三維的散點集來說同樣成立.進行三維的Delaunay三角剖分后得到的三角網格,構成了空間中均勻的四面體,如圖5所示.因此,對本文提取的、攜帶時間信息的三維特征點坐標集合進行Delaunay三角剖分,得到一系列互不交叉、形狀均勻的四面體.四面體把視頻幀內和幀間的特征點通過四面體的邊相互連接起來,一個四面體由視頻幀的幀內和幀間特征點共同確定.因此,在一個四面體上,幀內和幀間的關聯關系都得到了充分的體現,空域和時域上的信息都得到了有效的表達.

圖5 三維Delaunay三角剖分Fig.5 3-D Delaunay triangulation

2.4 視頻指紋生成

視頻指紋是從視頻中提取的、能夠標識視頻內容,并唯一代表視頻的標志.本文希望通過Delaunay三角剖分后得到的一系列既包含時間信息又包含空間信息的空間四面體,來生成兼具時域特征與空域特征的視頻指紋.

構成四面體的特征點的特征值為G,四面體的特征值由構成一個四面體的四個特征點的特征值決定,則四面體的特征值定義如下:

(1)

集合T表示Delaunay三角剖分后的所有四面體的特征值,集合T即為視頻指紋.

3 實驗結果與分析

3.1 實驗設定及評價標準

本實驗所用視頻來源于公開視頻數據庫CC_WEB_VIDEO (vireo.cs.cityu.edu.hk/ webvideo),該數據庫包含體育、新聞、動畫等不同類型的視頻,視頻時長在20秒到20分鐘之間.在此數據庫的基礎上,對數據庫中視頻分別進行旋轉變換、仿射變換、對比度變換、添加圖標變換、添加噪聲變換,以及綜合使用添加圖標、仿射變換和改變對比度這三種視頻變換方法進行組合變換,從而使一個視頻衍生出6種變換后的視頻,各種攻擊變化的效果圖如圖6所示.

本文采用漏報概率和誤報概率構成的受試者工作特征曲線(ROC曲線)作為評價標準.漏報概率為未能檢測出的真實拷貝個數和總拷貝個數的比值.誤報概率為檢測出的虛假拷貝個數與檢測出的拷貝個數的比值.

設總拷貝個數為S,未檢測出的真實拷貝個數為N,則漏報概率定義如下:

(2)

設檢測出的拷貝個數為R,檢測出的虛假拷貝個數為F,則誤報概率定義如下:

(3)

為驗證本文算法的魯棒性,將本文提出的算法與近年來較為流行的梯度方向質心(CGO)算法[13]、近似低秩張量(LRTA)算法[14]進行比較,本文實驗共分為6組:

第一組實驗是對原始視頻進行旋轉變換,設定旋轉參數為視頻幀逆時針旋轉10度.主要目的是為了檢驗在旋轉攻擊下,算法的魯棒性.

圖6 視頻幀攻擊效果Fig.6 Effect of video frame attack

圖7 實驗結果Fig.7 Experimental result

第二組實驗是對原始視頻進行仿射變換,設仿射變換矩陣為[1 0.1 0;0.1 1 0;0 0 1].主要目的是為了檢驗在仿射變換攻擊下算法的魯棒性.

第三組實驗是對原始視頻進行對比度變換,設定對比度變換參數為([0.2,0.9],[0,1]),即對比度在0.2以下和對比度0.9以上的值被去除,剩余的值映射到0-1之間.主要目的是為了檢驗在對比度攻擊下算法的魯棒性.

第四組實驗是對原始視頻添加分辨率為20×20的圖標.主要目的是為了檢驗在添加圖標攻擊下算法的魯棒性.

第五組實驗是對原始視頻添加均值為0、方差為0.005的高斯噪聲,主要目的是為了檢驗在噪聲攻擊下算法的魯棒性.

第六組實驗是對原始視頻進行包括對比度、添加圖標、仿射變換在內的組合變換.對比度變換參數為([0.2,0.9],[0,1]),添加圖標的分辨率為20×20,仿射變換矩陣為[1 0.1 0;0.1 1 0;0 0 1].主要目的是為了檢驗在組合攻擊下算法的魯棒性.

3.2 實驗結果與分析

依次進行上述6組實驗,并把變換后視頻與原始視頻的視頻指紋進行匹配,繪制ROC曲線.ROC曲線縱坐標表示漏報概率,橫坐標表示誤報概率.結果如圖7所示.

根據這6組實驗的結果可以看出,在旋轉變換、仿射變換、對比度變換、添加圖標這四種視頻攻擊下,本文提出算法的ROC曲線位于CGO和LRTA算法的左下方如圖7(a)-圖7(d),說明在以上四種攻擊下,其性能都優于CGO和LRTA算法;在噪聲攻擊下,本文算法的ROC曲線在LRTA算法的左下方,CGO算法的右上方,但距離較小如圖7(e),說明漏報概率、誤報概率這兩個評價指標優于LRTA算法,弱于CGO算法,但差距較小,這是因為本文算法基于視頻幀的灰度特征生成視頻指紋,添加噪聲后對灰度特征影響較大,使算法性能下降,弱于CGO算法;在組合攻擊下,本文算法的ROC曲線位于CGO和LRTA算法的左下方如圖7(f),說明在綜合攻擊下本文算法性能優于CGO算法和LRTA算法.綜上所述,本文算法具有較好的魯棒性.

4 結 論

為綜合利用視頻的空域和時域信息,增強視頻指紋的魯棒性,本文提出了一種Delaunay三角剖分下的視頻指紋算法,該算法對視頻幀分塊后提取的特征點進行Delaunay三角剖分,以每一個剖分所得的四面體為單位計算其對應特征值,生成包含空域與時域信息的視頻指紋.實驗證明,該算法具有良好的魯棒性.

Delaunay三角剖分后得到的四面體具有良好的穩定性,該四面體不僅體現了同一幀內特征點的聯系,還包含了幀與幀之間在時域上的信息,因此本文提出的算法既具有較好的視頻內容代表性又具有較好的魯棒性.但是當視頻的幀數較多時,Delaunay三角剖分得到的四面體的數目較多,從而增加了算法的計算復雜度,因此,本文下一步的工作將重點研究如何從眾多的四面體中優選出具有代表性的四面體,在不降低算法魯棒性能的前提下減小計算的復雜度.

：

[1] Oostveen,Kalker,Haitsma,et al.Feature extraction and a database straregy for video fingerprinting [C].Proc of Recent Advancein Visual Information Systems,Springer-Verlag,2002:117-128.

[2] Lee,Yoo C D,et al.Video fingerprinting based on centrodis of gradient orientations [C].Proc of Int.Conf.Acoust.Speech and Siganl Processing(ICCASSP),IEEE,2006:401-404.

[3] Chen L.Stentiford F W M.Video sequence matching based on temporal ordinal measurement [J].Pattern Recognition Letters,2008,29(13):1824-1831.

[4] Radhakrishnan R,Bauer C.Content-baesd video signatures based on projections of difference images[C].Proc of IEEE 9th Workshop on Mulitimedia Signal Processing,IEEE Xplore,2007:341-344.

[5] Coskun B,Bulent S,Nasir M.Spatio-temporal transform based video hashing [J].IEEE Trans on Multi-Media,2006,8(6):1190-1208.

[6] Zoran M,Zoran V.Robustness of SVD watermarks in video sequences encoded with H.264/AVC[C].International Conference on Environmental Science and Technology,2014.

[7] Urvoy M,Goudia D,Autrusseau F.Perceptual DFT watermarking with improved detection and robustness to geometrical distortions[J].IEEE Transactions on Information Forensics & Security,2014,9(7):1108-1119.

[8] Douze M,Jegou H,Schmid C.An image-based approach to video copy detection with spatio-temporal post-filtering [J].IEEE Transactions on Multimedia,2010,12(4):257- 266.

[9] Liu W,Mei T,Zhang Y.Instant mobile video search with layered audio-video indexing and progressive transmission[J].IEEE Transactions on Multimedia,2014,16(8):2242-2255.

[10] Roopalakshmi R,Reddy G R M,A.Novel approach to video copy detection using audio fingerprints and PCA [J].Procedia Computer Science,2011,5:149-156.

[11] Sunil L,Yoo C D,et al.Robust video fingerprinting based on symmetric pairwise boosting [J].Circuits and Systems gor Video Technology,2009,19(9):1379-1388.

[12] Jeandaniel B,Ramsay D,Arijit G.The stability of delaunay triangulations [J].International Journalof Computational Geometry & Applications,2015,23 (04n05):303-333.

[13] Aldahoud A,Singhai R,Kumar P,et al.Video fingerprinting using AED of CGO based signatures[C].IEEE International Conference on Computer Science and Automation Engineering,IEEE,2012:292-295.

[14] Li M,Monga V.Desynchronization resilient video fingerprinting via randomized,low-rank tensor approximations[C].IEEE,International Workshop on Multimedia Signal Processing,IEEE,2011:1-6.

[15] Liu Zhao-qing.Research on several key technologies of image sensing Hash [D].Harbin:Harbin University of Technology,2013.

[16] Caroli M,Teillaud M.Delaunay triangulations of point sets in closed euclidean d-manifolds [J].Annual Symposium on Computational Geometry,2011,6(1):274-282.

[17] Wu B,Krishnan S S,Zhang N,et al.Compact and robust video fingerprinting using sparse represented features[C].IEEE International Conference on Multimedia and Expo.IEEE,2016:1-6.

[18] Yang G,Chen N,Jiang Q.A robust hashing algorithm based on SURF for video copy detection [J].Computers & Security,2012,31(1):33-39.

[19] Wang R B,Chen H,Yao J L,et al.Video copy detection based on temporal contextual hashing[C].IEEE Second International Conference on Multimedia Big Data,IEEE,2016:223-228.

[20] Lee H K,Kim J.Extended temporal ordinal measurement using spatially normalized mean for video copy detection [J].Etri Journal,2010,32(3):490-492.

[21] Qingzhen M A,Wang Y,Zeng Y,et al.Hashing-based image copy detection[J].Ship Electronic Engineering,2014,34(9):96-99.

[22] Dash S,Kramer R M D,O′Dwyer L M,et al.A robust video copy detection system using TIRIDCT fingerprints and DWT statistical features [J].International Journal of Computer Applications,2012,51(6):29-34.

[23] Li M,Monga V.Compact video fingerprinting via structural graphical models[J].IEEE Transactions on Information Forensics & Security,2013,8(11):1709-1721.

[24] Bhogle M P,Chhangani A.Content based copy detection using TIRI-DCT method [J].International Journal of Engineering Sciences & Research Technology,2014,3(7):449-454.

附中文參考文獻：

[15] 劉兆慶.圖像感知哈希若干關鍵技術研究[D].哈爾濱:哈爾濱工業大學,2013.