基于數字簽名的高效視頻拷貝檢測算法研究

李小雨，王 琳，王輝淇

(1.國家新聞出版廣電總局廣播科學研究院，北京100866;2.北京郵電大學信息與通信工程學院，北京100876)

隨著互聯網技術的快速發展，視頻信息的傳播和獲取變得越來越便利。同時由于網絡所具有的共享性和開放性，致使數字視頻經常遭到惡意攻擊、非法侵犯版權和信息篡改。視頻拷貝檢測作為一種有效的視頻跟蹤和檢測技術，它能夠有效地檢測出視頻內容是否被篡改、被盜版，可以廣泛地應用于數字廣播電視的監控領域。在基于內容的視頻檢索(Content Based Video Retrieval，CBVR)領域已經廣泛展開了有效的視頻相似性度量和高效的視頻拷貝檢測(Video Copy Detection，VCD)算法研究。

視頻拷貝檢測包括兩方面的技術:特征提取和搜索方法。在過去的十年里，研究者們已經提出了大量的圖像和視頻特征提取算法，例如色矩［1］、DCT［2］、差分圖像的投影［3］和 SIFT［4］等。為了提高計算效率，降維法已普遍用于高維特征空間。典型統計模型有混合高斯模型［5］和ViSig模型［6］。然而，這些方法計算效率較低，針對海量的視頻數據效率并不高。

在大量的數據庫中建立一個高效的索引是視頻拷貝檢測的另一個關鍵問題。基于局部敏感的哈希索引算法(Locality Sensitive Hashing，LSH)［7］已經被廣泛用于高維空間近似最近鄰搜索。ViTris［8］算法可用于視頻摘要和構建最佳B+樹索引。金字塔技術［9］將D維的數據空間劃分為二維金字塔，然后將每個金字塔切分成幾個片段，每一個片段組成一個數據頁。現有的LSH技術，通常含有數百個哈希表，對于可擴展的分布式應用和快速查詢的大型數據庫都并不十分高效。

本文提出了一種新的基于視頻指紋的高效視頻拷貝檢測算法，該算法設計了一種簡單的基于時空域特征的視頻簽名。視頻剪輯間的相似度通過視頻簽名的距離來度量。根據聚類索引表(Clustering Index Table，CIT)設計了一種高效的搜索方法。實驗結果表明本文提出的算法應用于大量視頻數據庫場景中具有較好的效果，適用于數字廣播電視的監控領域。

1 基于時空域的視頻簽名

一般視頻簽名是基于圖像特征提取，考慮到計算效率，一些低層的特征例如顏色、紋理、邊緣通常被作為圖像簽名。文獻［10］中驗證了將YCbCr直方圖是一種有效的視頻簽名，它能夠為視頻拷貝檢測提供有用的信息。由于網絡中視頻總數量是飛速增長的，考慮到計算效率，數字簽名設計應盡可能的簡單。在本方案中，將YCbCr的平均值加權求和的結果作為圖像簽名S，如下式所示

式中:M和N分別是圖像的寬度和高度;Yij，Cbij和Crij分別表示圖像每一個像素的Y，Cb和Cr分量。實驗中所使用的測試序列都是4∶2∶0采樣格式，所以Cb和Cr分量尺寸只有Y分量的1/4。基于空間統計特性的平均值能夠提供圖像的例如顏色、亮度等重要信息。在圖像簽名中，設置權重是為了放大Y，Cb和Cr分量的差異。根據人類視覺特性，人們對于紅色最為敏感，因此Cr分量權重設置的最大。

在本方案中，采用兩個時空分布(Spatial Temporal Distribution，STD)統計特性作為視頻簽名——視頻序列的均值和方差，如下式所示

式中:Si是圖像簽名;L代表視頻序列總幀數。根據時空分布特征，復制的視頻通常具有相近的圖像簽名和時空變化。視頻的相似度與圖像幀的特征、鏡頭長度及其變化有關，根據人類視覺特性，拍攝時間對視頻相似度影響不大。基于圖像簽名的STD的統計特性可以表征視頻的相似性，可以用作視頻簽名。根據本文提出的方法計算出的圖像簽名在坐標軸上是相近的。因此，本文提出的方法是一種統計特征提取策略，能夠有效地用于視頻拷貝檢測。

2 視頻拷貝檢測

由于視頻簽名是基于STD的統計特性，相似度測量轉變為計算視頻簽名的距離。給定2個視頻序列v1和v2，它們的視頻簽名分別是(Vm1，Vd1)和(Vm2，Vd2)。這2個視頻的相似度定義如下

為了簡化相似度搜索，本文提出聚類索引表(Clustering Index Table，CIT)。索引表根據視頻簽名的數值除以10，具有近似視頻簽名的視頻剪輯存儲到同一張索引表中。CIT有5個屬性:視頻剪輯文件名、高度、寬度、均值Vm和方差Vd。視頻簽名Vm提供的是STD的普通統計特性，用于索引聚類;Vd表示視頻圖像幀的時空變化，用作距離度量的一部分。

對于視頻拷貝檢測，視頻可以分為兩類:在數據庫中的視頻和新視頻。對于前者，其視頻簽名已經計算過了。對于后者，需要計算其視頻簽名并添加到數據庫中。給出一個待查詢的視頻剪輯，先計算出其視頻簽名，然后再去相應的索引表中進行查詢。用這種方法，搜索引擎是在有界的范圍內處理每一個視頻剪輯，從而避免去搜索大量不相似的視頻，搜索效率可以得到較大的提升。由于拷貝的視頻剪輯是有限的，利用CIT搜索視頻剪輯滿足VCD要求。對于完整視頻拷貝檢測，搜索表的索引是由以下規則決定:如果余數小于5，并且q－1或者q+1存在，搜索索引為q－1和q。否則索引為q和q+1，表示如下

根據四舍五入原則找到最相近的視頻簽名，從而找到視頻復制源。圖1為本文提出的VCD算法流程圖和系統框架圖。在特征提取階段，根據圖像簽名計算在數據庫中的每一個視頻剪輯的視頻簽名。然后，根據視頻簽名聚類生成索引表，即CIT。在VCD系統中，搜索引擎在相應的CIT中處理每一個視頻剪輯，并且返回結果。

圖1 VCD算法流程圖和系統

3 實驗結果

本文采用MATLAB 7.14對算法進行仿真實驗。實驗過程中，所采用的計算機為Intel Core i5 2.80 GHz，內存為2.99 Gbyte。視頻數據庫中含有600個視頻剪輯。為了評價檢測的準確性，實驗過程中采用了查全率(Recall Rate，RR)和正確率(Precision Rate，PR)兩個指標，其定義分別為式(8)和式(9)。拷貝視頻剪輯是通過原視頻剪輯經過時空變換后產生的。在實驗中，使用的時空變換主要有:亮度增強，添加高斯噪聲，添加椒鹽噪聲，旋轉，縮放尺寸，翻轉，高斯模糊，幀裁剪。變換對比圖如圖2所示。

圖2 時空變換結果對比圖

實驗過程中，所采用的原始視頻尺寸為1 920×800。圖2b亮度增強3%;圖2c添加的高斯噪聲均值為0，方差為0.005;圖2d添加的椒鹽噪聲其噪聲密度為0.01;圖2e旋轉變換圍繞圖像中心旋轉2個像素;圖2f高斯模糊降析函數模板尺寸為7×7，標準差為5像素;圖2g視頻尺寸縮小為1 800×800;圖2h對視頻剪輯進行水平翻轉;圖2i剪切5%，裁剪后視頻剪輯尺寸為1 870×780。實驗結果如表1所示，該表中列出了上述8種變換類型下VCD的查全率和正確率。

表1 不同變化下VCD結果 %

根據表1實驗結果可以看出，經過不同的時空變換后，運用本文算法進行視頻拷貝檢測，其結果具有較高的查全率和正確率。圖3所示為隨著視頻剪輯數增加，VCD用時曲線。從圖中曲線可以看出，隨著視頻剪輯數的增加，VCD的用時增長并不是十分迅速。適用于大型數據庫中進行視頻拷貝檢測。

4 總結

本文提出了一種新的視頻拷貝檢測算法，該算法基于視頻剪輯的時空特征提取視頻簽名，通過計算視頻簽名的距離度量視頻剪輯之間的相似性。為視頻簽名數據庫建立聚類索引表，能夠提高搜索速度。實驗結果表明，本文算法對視頻拷貝檢測有較高的查全率和正確率。可以用于在大型數據庫中進行視頻拷貝檢測，適用于數字廣播電視的監控領域。

圖3 視頻剪輯數增加情況下的VCD用時曲線

［1］YANG X，TIAN Q，CHANG E C.A color fingerprint of video shot for content identification［EB/OL］.［2013－04－21］.http://www.deepdyve.com/lp/association－for－computing－machinery/a－color－fingerprint－ofvideo－shot－for－content－identification－bdtOObs0JB .

［2］ GROSX N A P.Detecting repeats for video structuring［J］.Multimedia Tools and Applications，2008(38):233－252.

［3］ CBAUER R R A.Content－based video signatures based on projections of difference images［C］//Proc.IEEE 9th Workshop on Multimedia Signal Processing.［S.l.］:IEEE Press，2007:341－344.

［4］ PHILBIN C J，ISARDM，ZISSERMAN A.Scalable near identical image and shot detection［C］//Proc.the6th ACM International Conference on Image and Video Retrieval.New York:ACM Press，2007:549－556.

［5］ VASCONCELOS N.On the complexity of probabilistic image retrieval［C］//Proc.Eighth IEEE Int＇l Conf.on Computer Vision.［S.l.］:IEEE Press，2001:400－407.

［6］ ZAKHOR SC.Efficient video similaritymeasurementwith video signature［J］.IEEE Trans.Circuits and Systems for Video Technology，2003(13):59－74.

［7］ LV Q，JOSEPHSONW，WANG Z，et al.Multi－probe LSH:efficient indexing for high－dimensional similarity search［EB/OL］.［2013－04－21］.http://www.03964.com/read/0c616a85e9a527573c344a77.html.

［8］ SHEN H，ZHOU BO.Towards effective indexing for very large video sequence database［EB/OL］.［2013－04－21］.http://portal.acm.org/citation.cfm?doid=1066157.1066240.

［9］ BERCHTOLD S C，KRIEGEL H P.The pyramid－technique:towards breaking the curse of dimensionality［EB/OL］.［2013－04－21］.http://dl.acm.org/citation.cfm?id=276318.

［10］ HT S，BCO，ZHOU X.Towards effective indexing for very large video sequence database［EB/OL］.［2013－04－21］.http://dl.acm.org/citation.cfm?doid=1066157.1066240.