李小雨，王 琳，王輝淇

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

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

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

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

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

1 基于時(shí)空域的視頻簽名

一般視頻簽名是基于圖像特征提取，考慮到計(jì)算效率，一些低層的特征例如顏色、紋理、邊緣通常被作為圖像簽名。文獻(xiàn)［10］中驗(yàn)證了將YCbCr直方圖是一種有效的視頻簽名，它能夠?yàn)橐曨l拷貝檢測(cè)提供有用的信息。由于網(wǎng)絡(luò)中視頻總數(shù)量是飛速增長(zhǎng)的，考慮到計(jì)算效率，數(shù)字簽名設(shè)計(jì)應(yīng)盡可能的簡(jiǎn)單。在本方案中，將YCbCr的平均值加權(quán)求和的結(jié)果作為圖像簽名S，如下式所示

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

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

式中:Si是圖像簽名;L代表視頻序列總幀數(shù)。根據(jù)時(shí)空分布特征，復(fù)制的視頻通常具有相近的圖像簽名和時(shí)空變化。視頻的相似度與圖像幀的特征、鏡頭長(zhǎng)度及其變化有關(guān)，根據(jù)人類視覺特性，拍攝時(shí)間對(duì)視頻相似度影響不大?；趫D像簽名的STD的統(tǒng)計(jì)特性可以表征視頻的相似性，可以用作視頻簽名。根據(jù)本文提出的方法計(jì)算出的圖像簽名在坐標(biāo)軸上是相近的。因此，本文提出的方法是一種統(tǒng)計(jì)特征提取策略，能夠有效地用于視頻拷貝檢測(cè)。

2 視頻拷貝檢測(cè)

由于視頻簽名是基于STD的統(tǒng)計(jì)特性，相似度測(cè)量轉(zhuǎn)變?yōu)橛?jì)算視頻簽名的距離。給定2個(gè)視頻序列v1和v2，它們的視頻簽名分別是(Vm1，Vd1)和(Vm2，Vd2)。這2個(gè)視頻的相似度定義如下

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

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

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

圖1 VCD算法流程圖和系統(tǒng)

3 實(shí)驗(yàn)結(jié)果

本文采用MATLAB 7.14對(duì)算法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)過程中，所采用的計(jì)算機(jī)為Intel Core i5 2.80 GHz，內(nèi)存為2.99 Gbyte。視頻數(shù)據(jù)庫(kù)中含有600個(gè)視頻剪輯。為了評(píng)價(jià)檢測(cè)的準(zhǔn)確性，實(shí)驗(yàn)過程中采用了查全率(Recall Rate，RR)和正確率(Precision Rate，PR)兩個(gè)指標(biāo)，其定義分別為式(8)和式(9)?？截愐曨l剪輯是通過原視頻剪輯經(jīng)過時(shí)空變換后產(chǎn)生的。在實(shí)驗(yàn)中，使用的時(shí)空變換主要有:亮度增強(qiáng)，添加高斯噪聲，添加椒鹽噪聲，旋轉(zhuǎn)，縮放尺寸，翻轉(zhuǎn)，高斯模糊，幀裁剪。變換對(duì)比圖如圖2所示。

圖2 時(shí)空變換結(jié)果對(duì)比圖

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

表1 不同變化下VCD結(jié)果 %

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

4 總結(jié)

本文提出了一種新的視頻拷貝檢測(cè)算法，該算法基于視頻剪輯的時(shí)空特征提取視頻簽名，通過計(jì)算視頻簽名的距離度量視頻剪輯之間的相似性。為視頻簽名數(shù)據(jù)庫(kù)建立聚類索引表，能夠提高搜索速度。實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)視頻拷貝檢測(cè)有較高的查全率和正確率?？梢杂糜谠诖笮蛿?shù)據(jù)庫(kù)中進(jìn)行視頻拷貝檢測(cè)，適用于數(shù)字廣播電視的監(jiān)控領(lǐng)域。

圖3 視頻剪輯數(shù)增加情況下的VCD用時(shí)曲線

［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.