基于球哈希和改進的灰度差算法的視頻拷貝檢測

李　皓　張興忠

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

?

基于球哈希和改進的灰度差算法的視頻拷貝檢測

李皓張興忠

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

摘要針對大規模的視頻版權保護中檢索準確率低和檢索速度慢的問題，提出一種基于球哈希和改進的灰度差算法的視頻拷貝檢測方法。首先，對傳統的灰度差提取關鍵幀的算法進行改進，提出利用灰度差與灰度差累積量相結合的方法提取關鍵幀，減少了提取關鍵幀時產生的累積誤差，提高視頻檢索的準確率；然后，提取關鍵幀的SIFT特征，并且利用著名的球哈希算法對SIFT特征建立索引，把128維的高維浮點向量變為二值索引,提高檢索速度。實驗結果表明該方法不僅提高了視頻檢索的準確率和檢索速度，而且保證了較高的查全率。

關鍵詞版權保護視頻拷貝檢測灰度差SIFT特征球哈希

0引言

隨著互聯網的普及，以及各種壓縮技術和大容量存儲技術的不斷出現，使得視頻的傳播、制作、存儲越來越容易，視頻網站服務日漸成熟[1]。大量影視作品在未經授權的情況下通過視頻服務網站在網絡上進行傳播，對著作權所有人的權利造成了直接的損害。這種行為導致電影票房的下降和電視收視率的降低，以及音像制品銷量的下降。為保護著作權人的合法權益，減少侵權行為的發生，視頻版權保護技術的研究的重要性日益凸顯并成為目前研究的熱點。

視頻版權保護面臨的主要挑戰之一是視頻數量大。例如，全球著名視頻網站YouTube每天平均上傳6000多個視頻(平均每秒上傳0.7個)。上傳視頻的平均長度是5分鐘，每天上傳視頻的總長度約為5000個小時。如果要對近10年的視頻進行版權保護，需要用每天上傳的5000個小時的視頻和過去10年中4.38億個小時的視頻比較。除此之外，視頻的剪切、旋轉、轉換編碼格式等視頻拷貝攻擊也增加了視頻版權保護的難度。

本文提出了一個基于內容的視頻拷貝檢測方法。目的是通過把上傳的文件和已存文件進行對比，檢測出侵權視頻。為了提高檢測的準確率和檢測速度，提出基于灰度差與灰度差累積量相結合的方法提取關鍵幀，并且利用球哈希算法為關鍵幀的SIFT特征建立二值索引的視頻拷貝檢測方法。

1相關工作

近年來，眾多學者投身于視頻版權保護技術的研究。數字水印技術[2]和基于內容的視頻拷貝檢測技術[3]是目前視頻版權保護具有代表性的兩種方法。數字水印技術需在視頻發布之前嵌入水印進行保護，嵌入在視頻中的數字水印容易被破壞而失去版權保護功能，因此將數字水印應用到實際中還存在一定的局限性。相反，基于內容的視頻拷貝檢測技術直接從視頻內容本身提取特征，無需嵌入任何信息，與數字水印技術相比更具實用價值。

基于內容的視頻拷貝檢測技術中的一個關鍵問題是如何提取視頻關鍵幀[4]，高效地分割視頻的關鍵幀是精確檢索視頻的基礎。傳統的視頻關鍵幀提取方法有：基于邊緣檢測的方法、基于直方圖的分割方法和基于灰度差的方法。這些方法在提取關鍵幀時都是以提取前一關鍵幀為基準來提取下一關鍵幀，在提取關鍵幀時會產生嚴重的累積誤差，影響視頻檢索的準確率。本文對傳統的基于灰度差的方法進行改進，提出了基于灰度差與灰度差累積量相結合的方法提取視頻關鍵幀。

在提取視頻關鍵幀后提取關鍵幀特征。文獻[5]提出LSH-MPEG方法，在該方法中MPEG圖像特征被用來檢測拷貝視頻，但是MPEG特征對于顏色退化等攻擊魯棒性較差，通常作為一種基準特征使用，本文在實驗部分也與該方法進行比較。Liu N[6]于2010年提取關鍵幀的空間灰度序特征來檢測拷貝視頻，實驗表明該特征對于各種輕微拷貝攻擊(如顏色變化、重編碼、分辨率變化等)有較好的魯棒性。文獻[7]采用運動向量特征作為視頻關鍵幀特征，特征提取時間長，不適用于大規模的視頻版權保護。雖然全局特征的提取和相似度匹配速度較快，但是匹配的能力不足，影響了視頻查找的準確率。為了提高視頻檢索的準確率，我們采用經典的SIFT局部特征，并在其基礎上進行改進。

在查詢大型數據庫時建立索引來加快檢索速度是基于內容的視頻拷貝檢測的另一個關鍵技術。本文采用球哈希算法為SIFT特征建立索引，球哈希是一種二值哈希算法。與傳統的樹形結構索引相比，二值哈希算法具有數據結構更加緊湊、占用內存小、實用性高的優點。

目前，二值哈希算法主要分為數據獨立的哈希算法和數據依賴的哈希算法兩大類。在數據獨立的哈希算法中，哈希函數的選擇和輸入的數據是無關的。局部敏感哈希LSH(Locality-Sensitive Hashing)[8]是被廣泛應用的一種數據獨立哈希算法。最近，數據依賴哈希算法被廣泛研究，該類算法由于考慮到數據分布特點，因此可以選擇出更好的哈希函數。數據依賴哈希算法包括譜哈希算法[9]，半自動哈希算法[10]，聯合優化算法[11]，迭代量化方法[12]等。

上面提到的所有的哈希算法都是基于超平面把數據點劃分成兩個不同的集合來計算相應的二進制編碼。與上面提到的方法不同，球哈希算法是通過超球面來劃分數據點集合的，實驗表明球哈希算法具有更快地檢索速度。本文利用球哈希算法把相似的高維數SIFT特征點映射到相似的二值索引，通過查找近似的二值索引就可以有效地查詢相似的數據點。

2基于球哈希和改進的灰度差算法的視頻拷貝檢測

基于視頻內容的版權保護技術的基本處理流程包括：關鍵幀提取、特征提取、建立索引、關鍵幀匹配[13]四個關鍵步驟。基于改進的灰度差關鍵幀提取算法和球哈希索引的視頻拷貝檢測框架如圖1所示。

圖1　基于球哈希和改進的灰度差算法的視頻拷貝檢測框架

2.1視頻關鍵幀提取

傳統的灰度差關鍵幀提取方法，在實際使用時會產生累積誤差，為提高視頻檢索的準確率對原始的灰度差關鍵幀提取算法進行改進，提出灰度差與灰度差累積量相結合的方法提取關鍵幀。

圖像灰度差計算公式：

(1)

式中Ht(j)表示直方圖中灰度j的像素點數0≤j≤255,下標t表示第t個幀。

灰度差累積量計算公式：

(2)

式中k表示視頻幀積累的個數。式(2)是k個式1的和。

關鍵幀必須滿足兩個判定條件：一是當前幀與前一關鍵幀之間的灰度差大于設定的閾值1；二是當前幀與前一關鍵幀之間的累積量C大于設定的閾值2。該方法可以有效地減小由原始的灰度差方法在提取關鍵幀時帶來的誤差，提高視頻檢測的準確度。

2.2SIFT特征提取

在視頻關鍵幀提取后，提取關鍵幀的SIFT特征。SIFT由David Lowe在1999年提出[14]，是近十年來影響較大的一種特征描述方式。SIFT特征是圖像的局部特征，其對尺度、視角、光照、旋轉等多種嚴重的變換具有很好的魯棒性。此外，SIFT特征還具有多量性、高速性和可擴展性。SIFT算法大致分為五個步驟：

1) 構建尺度空間一個圖像的尺度空間L(x,y,σ)定義為一個尺度變化的高斯函數G(x,y,σ)與原圖像I(x,y)的卷積。

L(x,y,σ)=G(x,y,σ)*I(x,y)

(3)

其中*表示卷積運算，G(x,y,σ)是尺度可變的高斯函數，公式如下：

(4)

式中(x,y)是空間坐標，σ大小決定圖像的平滑程度，大σ對應粗糙尺度(低分辨率)，反之對應精細尺度(高分辨率)。

2) 空間極值點檢測利用高斯差分函數DOG算子(Difference of Gaussian)進行極值檢測，高斯差分函數如下：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)

=L(x,y,kσ)-L(x,y,σ)

(5)

為尋找DOG函數的極值點，每一個像素點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。

3) 精確定位特征點的位置通過擬和三維二次函數以精確確定關鍵點的位置和尺度(達到亞像素精度)，去除低對比度的關鍵點和不穩定的邊緣響應點，以增強匹配穩定性、提高抗噪聲能力。

4) 確定方向根據圖像的局部梯度方向，給每個關鍵點分配方向。

5) 關鍵點特征描述通過以上步驟，每個關鍵點擁有三個信息：位置、尺度以及方向。給每個關鍵點建立一個128維的浮點數向量描述符。

2.3球哈希

為提高視頻的檢索速度，利用球哈希算法為關鍵幀的SIFT描述符建立索引。球哈希算法的定義如下：X={x1,…,xn}，xi∈RD為D維空間中的n個數據點的集合，利用c個球哈希函數把集合X映射到一個二進制空間{-1,+1}c中，其中c表示二進制編碼的長度。

每個球哈希函數定義為：

其中pk表示圓心，tk表示圓的半徑，d(·,·)表示RD中兩個點的歐式距離。每個哈希函數的值表示點x是否在以pk為球心，tk為半徑的球面內。當點x在球面內時，函數值為+1，否則，函數值為-1。

2.3.1球哈希函數的獨立性

在哈希算法中，保證數據點對每個哈希函數的均衡分布和各個哈希函數的相互獨立性是非常重要的，因為滿足這兩個屬性不僅可以實現數據點對不同二進制編碼的均衡分布，而且可以提高查詢速度[15]和查詢結果的準確率[16]。為了使球哈希函數滿足這兩個屬性必須滿足以下兩個條件：

首先，每個哈希函數的值為+1或-1的概率是相等的且均為0.5，即每個哈希函數滿足如下關系：

(6)

其次，保證任意兩個哈希函數之間是相互獨立的，定義vk代表事件hi(x)=+1。當且僅當Pr[Vi∩Vj]=Pr[Vi]∩Pr[Vj]時，事件vi和vj是相互獨立的。如果每個數據點對每一個二進制位的分布是均衡的(滿足式(6))，那么任意兩個獨立的二進制位滿足式(7)：

Pr[hi(x)=+1,hj(x)=+1]=Pr[hi(x)=+1]∩

(7)

2.3.2迭代優化

為了計算各個哈希函數的中心點pk和半徑tk， 提出一個迭代的過程。通過該迭代過程得到c個哈希函數，使得這些哈希函數同時滿足式(6)和式(7)。

該迭代過程分為兩步：首先，從點集X抽取一個子集S={s1,s2,…,sm}，并且在點集S中隨機選取c(c=256)個數據點作為c個哈希函數中心點的初始值。

然后，重新修改哈希函數的中心點pk和半徑tk，迭代過程中，用到兩個變量，分別為oi和oi,j，定義如下：

oi=|{sk|hi(sk)=+1,1≤k≤m}|

oi,j=|{sk|hi(sk)=+1,hj(sk)=+1,1≤k≤m}|

其中1≤i,j≤c,oi表示第i個哈希函數在點集S中值為+1的個數；oi,j表示點集S中使第i個哈希函數和第j個哈希函數的值同時為+1的點的個數。

算法1迭代優化算法:

輸入：采樣點集合S={s1,s2,…,sm}，容錯率εm和εs，哈希函數數目c；

輸出：圓心的位置p1,…,pc，每個哈希函數的半徑t1,…,tc。

從點集S中隨機選取c個數據點來初始化圓心p1,…,pc；

計算任意兩個哈希函數的oi,j的值。

repeat

for i = 1 to c - 1 do

for j = i + 1 to c do

fj←i=-fi←j

end for

end for

for i = 1 to c do

pi=pi+fi

end for

2.3.3哈希索引的距離計算公式

大部分基于超平面的二值哈希算法是用漢明距離來計算兩個二進制編碼的距離的，漢明距離是計算兩個二進制編碼異或后1的個數。這種測量距離的方法計算出了兩個點所跨越的超平面的個數，但是，漢明距離不能很好地表示封閉球面的性質。為了充分利用球哈希函數的特性，提出一個球哈希距離計算公式：

(8)

式中bi,bj是由球哈希函數計算得到的兩個二進制編碼， ⊕是異或運算符，|bi⊕bj|表示兩個二進制編碼中不同二進制位的個數，∧是位與運算符， |bi∧bj|表示兩個二進制編碼中同為+1的位的個數。分母表示在同一個球面內的位數，分子表示不在同一個球面內的位數，分數值越大表示兩個二進制編碼的距離越遠。

3實驗及結果分析

實驗環境：本文實驗在Intel Core i7-3770 3.40 GHz，8 G內存，采用OpenCV標準庫，在Windows Server 2008下用C++語言實現。

3.1實驗數據

實驗數據為CC_WEB_VIDEO[17]，CC_WEB_VIDEO是大規模網絡視頻數據集，該數據庫由香港城市大學和卡內基梅隆大學合作收集而來。該視頻集包括從YouTube, Google和Yahoo視頻分享網站采集得到的24組查詢視頻，平均每組查詢視頻的冗余量為27%，共12 790個視頻。

相似視頻主要分為格式變化和內容改變兩大類：格式變化包括：視頻格式改變(flv, mv, avi, mpg, mp4等視頻格式)、幀率變化、分辨率的改變；內容改變包括：光度變化(顏色改變或亮度改變)、視頻編輯變化(插入標題或插入logo)、內容修改(增加與內容不相關的幀)。

3.2評價指標

與一般的檢索類似，CC_WEB_VIDEO數據集上的評價指標主要包括：準確率、查全率、檢索時間，具體指標定義如下：

(9)

(10)

式中Ni表示檢索第i個視頻返回的視頻片段集，Mi表示目標視頻集中與第i個查詢視頻相似的視頻片段集。式(9)中的Pi表示第i個查詢視頻的準確率，式(10)中的Ri表示第i個查詢視頻的查全率。檢索時間指完成一次檢索需要的時間。

3.3實驗結果及分析

為檢測基于球哈希和改進的灰度差算法的視頻拷貝檢測的性能，實驗中用本文的方法(Special-Gray方法)和沒有建立索引的SIFT方法(SIFT方法)和文獻[5]中基于LSH索引和MPEG特征的方法(LSH-MEPG方法)進行比較，選取了24個查詢視頻，用查全率、準確率和檢索時間三項指標進行評估。基于SIFT方法、基于LSH-MPEG方法和Special-Gray方法的比較結果如圖2、圖3、表1所示。

圖2　查全率比較

圖3　準確率比較

LSH-MEPG方法SIFT方法Special-Gray方法16.7364.45.5

從圖2可以看出這三種方法中LSH-MPEG方法的查全率最高，SIFT方法和Special-Gray方法的召回率略低于LSH-MPEG的方法，但是基本保持在80%以上。該實驗結果表明本文的Special-Gray方法有較高的查全率。

但是，從圖3中可以看到三種方法中本文Special-Gray方法準確率最高。可以看出SIFT方法比LSH-MPEG方法有較高的準確率，這是由于MPEG特征對顏色退化等攻擊魯棒性較差，而SIFT特征比MPEG特征信息量豐富，獨特性好，而匹配精度高。本文的Special-Gray方法的準確率比SIFT方法高，這是因為該方法不僅提取了關鍵幀的SIFT特征，而且采用了灰度差和灰度差累積量相結合的方法提取關鍵幀，減少了幀間累積誤差，進一步提高了視頻檢索的準確率。

由表1可看出Special-Gray方法的平均檢索速度最快，與沒有索引的SIFT方法相比檢索時間縮短了10倍，與采用局部敏感哈希算法的LSH-MPEG方法相比檢索時間縮短了3倍。這是由于在Special-Gray方法中為SIFT特征建立了球哈希索引，把128維的浮點數向量變成了256維的二值向量，提高了檢索速度。

綜上所述，與其它兩種方法相比，LSH-MPEG具有方法檢索速度快和召回率高的特點，但是準確率低，不具有實用性。SIFT方法檢索時間太長，影響了檢索效率。Special-Gray方法在較高的準確率和較快的檢索速度的前提下，保持了較高的查全率，在視頻拷貝檢測方面更具實用價值。

4結語

本文對傳統灰度差關鍵幀提取算法進行了改進，提出了灰度差和灰度差累積量相結合的方法提取關鍵幀，提高了提取關鍵幀的準確率，并且利用球哈希算法對SIFT特征建立索引，把高維浮點向量變為二值向量，提高了檢索速度。今后的研究方向是在此基礎上進一步提高視頻的檢索的查全率，增強視頻檢索的實用性。

參考文獻

[1] 王光文. 論視頻網站UGC經營者的版權侵權注意義務[J]. 國際新聞界, 2012, 34(3): 28-34.

[2] 聶廷遠, 賈蕭, 萬勝偉, 等. 多重加密的數字水印生成方法[J]. 計算機工程與設計, 2013, 34(9): 3054-3057.

[3] 劉紅, 文朝暉, 王曄. 基于內容的視頻拷貝檢測研究[J]. 計算機工程, 2010, 36(7): 227-229.

[4] 陳青華, 程恭, 謝曉方, 等. 一種改進的自適應關鍵幀提取方法[J]. 兵工自動化, 2011, 30(9): 90-92.

[5] Murabayashi N, Yoshida K. Copied video detection with MPEG-7 video signature and multiple direct-mapped cache[C]//Hybrid Intelligent Systems (HIS), 2011 11th International Conference on. IEEE, 2011: 190-195.

[6] Liu N, Zhao Y, Zhu Z. Commercial recognition in TV streams using coarse-to-fine matching strategy[M]//Advances in Multimedia Information Processing-PCM 2010. Springer Berlin Heidelberg, 2010: 296-307.

[7] Schoeffmann K, Boeszoermenyi L. Video sequence identification in TV broadcasts[M]//Advances in Multimedia Modeling. Springer Berlin Heidelberg, 2011: 129-139.

[8] 林朝暉, 于俊清, 何云峰, 等. 高維分布式局部敏感哈希索引方法[J]. 計算機科學與探索, 2013, 7(9): 811-818.

[9] Weiss Y, Torralba A, Fergus R. Spectral hashing[C]//Advances in neural information processing systems. 2009: 1753-1760.

[10] Wang J, Kumar S, Chang S F. Semi-supervised hashing for scalable image retrieval[C]//Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010: 3424-3431.

[11] He J, Radhakrishnan R, Chang S F, et al. Compact hashing with joint optimization of search accuracy and time[C]//Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on. IEEE, 2011: 753-760.

[12] Gong Y, Lazebnik S. Iterative quantization: A procrustean approach to learning binary codes[C]//Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on. IEEE, 2011: 817-824.

[13] Li J, Liang Y, Zhang B. Video copy detection based on spatiotemporal fusion model[J]. Tsinghua Science and Technology, 2012, 17(1): 51-59.

[14] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[15] He J, Radhakrishnan R, Chang S F, et al. Compact hashing with joint optimization of search accuracy and time[C]//Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on. IEEE, 2011: 753-760.

[16] Joly A, Buisson O. Random maximum margin hashing[C]//Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on. IEEE, 2011: 873-880.

[17] Shang L, Yang L, Wang F, et al. Real-time large scale near-duplicate web video retrieval[C]//Proceedings of the International Conference on Multimedia. ACM, 2010: 531-540.

VIDEO COPY DETECTION BASED ON SPHERICAL HASHING AND IMPROVED GRAY DIFFERENCE ALGORITHM

Li HaoZhang Xingzhong

(CollegeofComputerScienceandTechnology,TaiyuanUniversityofTechnology,Taiyuan030024,Shanxi,China)

AbstractFor the problem of low retrieval accuracy and slow retrieval speed in large-scale video copyright protection, we proposed a video copy detection method, it is based on spherical Hashing and improved gray difference algorithm. First, we improved the traditional algorithm of extracting key frames based on gray difference, proposed a method to extract key frames which combines the gray difference with gray difference accumulation, thus reduced the cumulative errors when extracting key frames, as well as improved the accuracy of video retrieval. Secondly, we extracted the SIFT feature of key frames and used the famous spherical Hashing algorithm to establish hashing index for SIFT feature, and converted the 128 high-dimensional floating-point vectors to binary hashing indexes, therefore improved retrieval speed. Experimental results showed that this method not only improved video retrieval accuracy and retrieval speed, but also ensured a higher recall rate.

KeywordsCopyright protectionVideo copy detectionGray differenceSIFT featureSpherical Hashing

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.01.046

收稿日期：2014-07-03。國家科技支撐項目子課題(2012BAH0 4F02-2)；山西省國際科技合作項目(2012081034-2)；人社部留學人員科技活動項目(2011-508)。李皓，碩士生，主研領域：計算機視覺，圖像處理，模式識別。張興忠，副教授。