吳明君，侯艷艷，李慶華

（1.棗莊學(xué)院信息科學(xué)與工程學(xué)院，山東棗莊 277160；2.齊魯工業(yè)大學(xué)電氣工程與自動(dòng)化學(xué)院，山東濟(jì)南 250353）

基于奇異值分解的視頻拷貝檢測(cè)研究

吳明君1，侯艷艷1，李慶華2

（1.棗莊學(xué)院信息科學(xué)與工程學(xué)院，山東棗莊 277160；2.齊魯工業(yè)大學(xué)電氣工程與自動(dòng)化學(xué)院，山東濟(jì)南 250353）

針對(duì)傳統(tǒng)的視頻拷貝檢測(cè)算法計(jì)算量大、對(duì)視頻變化敏感等問(wèn)題，提出一種新的視頻指紋算法來(lái)產(chǎn)生包含時(shí)空域信息的關(guān)鍵幀。采用奇異值分解的方法提取視頻關(guān)鍵幀的特征向量，對(duì)視頻特征序列進(jìn)行降維。改進(jìn)的視頻拷貝檢測(cè)算法對(duì)噪聲、幀平移、幀旋轉(zhuǎn)、丟幀等有很好的魯棒性。與以往的拷貝算法相比，提高了視頻拷貝檢測(cè)的查全率和準(zhǔn)確率，降低了誤碼率，與源視頻具有較高的匹配率。

視頻拷貝檢測(cè)；奇異值分解；特征提?。灰曨l指紋

吳明君，侯艷艷，李慶華.基于奇異值分解的視頻拷貝檢測(cè)研究［J］.河北科技大學(xué)學(xué)報(bào)，2014，35（2）：179-183.

WU Mingjun，HOU Yanyan，LI Qinghua.Study on singular value decomposition based video copy detection［J］.Journal of Hebei University of Science and Technology，2014，35（2）：179-183.

視頻信息的暴發(fā)性增長(zhǎng)使得網(wǎng)絡(luò)用戶可以共享更多的視頻，建立有效的視頻版權(quán)保護(hù)和檢測(cè)機(jī)制顯得尤為重要。視頻水印和視頻指紋算法可應(yīng)用于視頻拷貝檢測(cè)過(guò)程，視頻水印算法要求在視頻中嵌入額外的信息來(lái)降低視頻感知質(zhì)量，視頻擁有者很難在視頻發(fā)布前實(shí)現(xiàn)，在視頻拷貝檢測(cè)中有很大的局限性。視頻指紋算法主要提取具有魯棒性和區(qū)分性的特征信息，通過(guò)計(jì)算檢測(cè)視頻與原始視頻之間的特征距離來(lái)檢測(cè)視頻是否為拷貝。視頻指紋算法的研究仍然處于初步階段，許多研究者將圖像指紋算法應(yīng)用于視頻拷貝檢測(cè)，SUNIL等將視頻中的幀分成N×M的塊，提取每塊的梯度特征，所有塊的梯度特征組合成該幀特征信息［1］。LAW-TO等提出基于哈希點(diǎn)提取幀特征信息［2］，由于沒(méi)有考慮視頻幀的連續(xù)性，增加了產(chǎn)生的哈希函數(shù)維數(shù)，為了減少哈希函數(shù)的維數(shù)，許多學(xué)者提出基于關(guān)鍵幀的視頻指紋算法，將視頻分片，提取每片關(guān)鍵幀的高維特征量，通過(guò)哈希算法生成低維特征量，ROOVER等提出提取不同徑向區(qū)的像素方差作為特征量的算法［3］，缺點(diǎn)是對(duì)于關(guān)鍵幀衰減和噪聲敏感，調(diào)整關(guān)鍵幀將不利于視頻檢測(cè)的實(shí)現(xiàn)。COSKUN等提出提取視頻的時(shí)空域特征，將視頻序列看成三維矩陣，通過(guò)DCT變換提取視頻特征，在高斯噪聲、改變亮度、取反等幾何攻擊下保持了良好的性能，但計(jì)算復(fù)雜度較高［4］。

本文首先根據(jù)視頻的時(shí)空域特征將視頻分成片段，然后根據(jù)視頻片段內(nèi)的幀間相關(guān)性，將片段內(nèi)幀的組合構(gòu)成關(guān)鍵幀。最后對(duì)關(guān)鍵幀矩陣進(jìn)行奇異值分解，根據(jù)奇異值分布特點(diǎn)，選取前去10個(gè)奇異值構(gòu)成關(guān)鍵幀矩陣的特征量，通過(guò)與視頻庫(kù)匹配計(jì)算，完成拷貝檢測(cè)。實(shí)驗(yàn)證明改進(jìn)的視頻檢測(cè)算法比TOM算法［5］具有更高的查準(zhǔn)率和查全率。

1 基于奇異值分解的視頻拷貝檢測(cè)算法

1.1 視頻預(yù)處理

基于奇異值分解的視頻拷貝檢測(cè)算法分視頻預(yù)處理、片段劃分、關(guān)鍵幀選取、特征向量提取及匹配4步實(shí)現(xiàn)。

為了保證算法可以抵抗視頻縮放和幀率的變化，首先對(duì)視頻進(jìn)行預(yù)處理，預(yù)處理主要通過(guò)對(duì)視頻進(jìn)行時(shí)空域重采樣改變幀率和分辨率，統(tǒng)一幀率和幀大小，重采樣之前采用低通高斯濾波器對(duì)時(shí)空域處理以阻止量化噪聲［6］。重采樣后幀大小設(shè)為160×120，160×120適合 MPEG1，AVI，Real Video 512k，Real Video 28k等視頻格式，且在降低計(jì)算量的基礎(chǔ)上，可保證視頻的局部不變特性?；谙噜弾g的相似性，鏡頭內(nèi)部相鄰幀內(nèi)容上的差別非常小，幀率為12幀／s能基本保證視頻的連貫性［7］。

1.2 視頻片段劃分

視頻由一系列片段組成，片段內(nèi)的幀之間具有較強(qiáng)的時(shí)域相關(guān)性［8］。如果提取視頻序列每幀的特征值進(jìn)行檢測(cè)匹配，會(huì)造成特征信息冗余和增加計(jì)算復(fù)雜度，本文基于Bin-wise平均顏色直方圖對(duì)視頻進(jìn)行片段劃分，依次計(jì)算相鄰幀之間Bin-wise平均顏色直方圖的差值，遞歸分割視頻［9］。算法如下。

1）設(shè)視頻幀序列為F1，F(xiàn)2，…，F(xiàn)i，…，F(xiàn)n，i＝1，2，…，n。

2）計(jì)算Fi與后續(xù)幀F(xiàn)i＋1的特征距離di，di小于指定的相似度閾值β，則i＋1，返回2），繼續(xù)計(jì)算；di大于相似度閾值Y，則轉(zhuǎn)到3）計(jì)算，直到i＝n－1，停止計(jì)算。

3）將｛F1，F(xiàn)2，…，F(xiàn)i｝保存為視頻子片段，i＋1；返回2）計(jì)算。

視頻特征距離d利用直方圖交計(jì)算，視頻片段分割算法能夠有效地將視頻劃分成視頻片段集合，具有計(jì)算復(fù)雜度低、效率高的優(yōu)點(diǎn)。基于整個(gè)視頻進(jìn)行片段分割，分割效果不受鏡頭邊界檢測(cè)效果的負(fù)面影響，得到的視頻片段具有更好的內(nèi)部相似性和外部區(qū)分性［10］。

1.3 關(guān)鍵幀選取

考慮到視頻片段內(nèi)的幀間相關(guān)性，不是選用視頻片段某幀作為片段代表，而是將每個(gè)視頻片段中的幀加權(quán)平均得到關(guān)鍵幀，設(shè)lm，n，k為第k幀（m，n）象素的亮度值。為了避免不同格式視頻顏色特性發(fā)生變化，文中采用視頻幀的亮度部分作為視頻特征，指數(shù)函數(shù)對(duì)于關(guān)鍵幀的時(shí)域信息破壞較少，能更好地代表視頻的空域信息，具有較好的視覺(jué)效果［11］。關(guān)鍵幀對(duì)應(yīng)的象素計(jì)算：

1.4 特征向量提取及匹配

關(guān)鍵幀可以看成一個(gè)像素矩陣，視頻受到擾動(dòng)時(shí)，像素矩陣的奇異值不會(huì)發(fā)生劇烈變化，奇異值能體現(xiàn)視頻的代數(shù)特征，具有較好的穩(wěn)定性，本文采用奇異值分解的方法從像素矩陣中提取標(biāo)識(shí)視頻序列的特征向量［12］。

關(guān)鍵幀矩陣A＝M×N，對(duì)矩陣A∈Rm×n進(jìn)行奇異值分解，其中R表示實(shí)數(shù)域，則存在矩陣U和V滿足：

U是M×N階酉矩陣，V是M×N階酉矩陣，且滿足：

AAT的特征向量為A的左奇異向量；ATA的特征向量為A的右奇異向量，對(duì)應(yīng)的特征值都是A的奇異值的平方。

Σ為半正定對(duì)角矩陣：

Σ矩陣非對(duì)角線上的元素為0，λi為矩陣A的奇異值，r為矩陣A的秩，對(duì)角線上的元素為

λ1，λ2，…，λr－1，λr連同λr＋1，符合λi＝λl＝0（i＝1，2，…，r）按降序排列構(gòu)成視頻關(guān)鍵幀的特征向量，歸一化的奇異值對(duì)于視頻拷貝檢測(cè)具有很好的魯棒性，設(shè)σi為第i個(gè)特征量歸一化值：

特征向量維數(shù)選取對(duì)拷貝檢測(cè)有很大影響，特征向量維數(shù)太大會(huì)造成計(jì)算量增大，維數(shù)太小又很難實(shí)現(xiàn)對(duì)視頻的區(qū)分，設(shè)特征向量的維數(shù)為10。

視頻匹配過(guò)程將待測(cè)視頻與原始視頻庫(kù)的特征值進(jìn)行比較，σj，i為檢測(cè)視頻第j幀的第i個(gè)特征量，σ′j，i為 原始視頻第j幀的第i個(gè)特征量，L（Aj，A′j）為特征向量的距離函數(shù)：

d（A，A′）為待測(cè)視頻與原始視頻之間的距離，k為待測(cè)視頻片段個(gè)數(shù)，則

若待測(cè)視頻片段數(shù)k與原始視頻片段數(shù)差別較大時(shí)，采用滑動(dòng)窗方法來(lái)進(jìn)行匹配，以較短的視頻長(zhǎng)度為滑動(dòng)窗長(zhǎng)度［13］。

2 仿真實(shí)驗(yàn)及分析

為分析本文算法的性能，從視頻數(shù)據(jù)庫(kù)TRECVID的MUSCLE-VCD-2008數(shù)據(jù)集選取7個(gè)視頻序列，構(gòu)成待測(cè)視頻樣本。

視頻拷貝檢測(cè)將檢測(cè)出所有可能拷貝的幀或片段的檢測(cè)查全率（Recall）和查準(zhǔn)率（Precision）作為視頻拷貝檢測(cè)的指標(biāo)［14］。計(jì)算公式如下。

查全率＝有關(guān)聯(lián)的正確檢索結(jié)果／所有有關(guān)聯(lián)的結(jié)果；

查準(zhǔn)率＝有關(guān)聯(lián)的正確檢索結(jié)果／所有檢索到的結(jié)果。

視頻關(guān)鍵幀前幾個(gè)奇異值較大，剩下的奇異值一般較小，圖1為測(cè)試視頻和它們對(duì)應(yīng)的前10個(gè)歸一化奇異值，圖2為不同奇異值個(gè)數(shù)的查全率和查準(zhǔn)率。實(shí)驗(yàn)證明，奇異值個(gè)數(shù)為10時(shí)，視頻拷貝檢測(cè)算法能得到較好的性能和準(zhǔn)確率，當(dāng)奇異值的個(gè)數(shù)再增加對(duì)視頻拷貝檢測(cè)的性能提高不大，增加了系統(tǒng)復(fù)雜度。

本文選取20 min的7個(gè)視頻樣本進(jìn)行實(shí)驗(yàn)，相似度閾值β為0.13，wk＝γk中γ為0.65，表1為本

文算法與TOM算法和OM算法［15］的平均查全率與平均查準(zhǔn)率比較。

圖1 前10個(gè)歸一化奇異值對(duì)應(yīng)圖Fig.1 First 10 normalized singular value for test video

表1 不同視頻的查全率與查準(zhǔn)率Tab.1 Recall and precision for different video

圖2 不同奇異值個(gè)數(shù)下的查全率與查準(zhǔn)率Fig.2 Recall and precision for different number singular value

為了進(jìn)一步驗(yàn)證算法的精確性，從處理集合選取高斯白噪聲、幀平移、幀旋轉(zhuǎn)、模糊處理、丟幀、幀率改變等攻擊方法，對(duì)7個(gè)視頻進(jìn)行攻擊，計(jì)算誤碼率，并且驗(yàn)證是否能從原始視頻庫(kù)中檢測(cè)出攻擊視頻。誤碼率為2個(gè)序列不同碼字的數(shù)目與序列長(zhǎng)度的比值，閾值設(shè)為0.15，實(shí)驗(yàn)結(jié)果如表2所示，證明本算法具有較好的區(qū)分性和檢測(cè)精確度。

表2 視頻拷貝檢測(cè)結(jié)果Tab.2 Video copy detection results

3 結(jié) 語(yǔ)

提出一種基于奇異值分解的視頻拷貝檢測(cè)方法。該方法基于視頻幀相似性原理劃分視頻片段，在關(guān)鍵幀中嵌入片段時(shí)域信息，采用抗干擾能力強(qiáng)的歸一化奇異值算法計(jì)算特征向量，不再采用將視頻拷貝檢測(cè)轉(zhuǎn)化為幀匹配模式來(lái)處理問(wèn)題。實(shí)驗(yàn)表明本文提出的視頻拷貝檢測(cè)算法能有效保留視頻的時(shí)空域特征，較好地區(qū)分拷貝視頻與原始視頻，在保證視頻檢測(cè)準(zhǔn)確率的基礎(chǔ)上，降低檢測(cè)的誤碼率。

［1］ SUNIL L，YOO C D.Robust video fingerprinting for content-based video identification［J］.Circuits and Systems for Video Technology，2008，18（7）：983-988.

［2］ LAW-TO J，BUISSON O，GOUET-BRUNET V，et al.Robust voting algorithm based on labels of behavior for video copy detection［A］.14th Annual ACM International Conference on Multimedia［C］.New York：［s.n.］，2006.835-844.

［3］ de ROOVER C，de VLEESCHOUWER C，LEFEBVRE F，et al.Robust video hashing based on radial projections of key frames［J］.Signal Processing，2005，53（10）：4020-4037.

［4］ COSKUN B S，MEMON N.Spatiotemporal transform based video hashing［J］.Multimedia，2006，8（6）：1190-1208.

［5］ HUA Xiansheng，XIAN Chen，ZHANG Hongjiang.Robust video signature based on ordinal measure［A］.ICIP′04.2004 International Conference on Image Processing（Volume：1）［C］.［S.l.］：［s.n.］，2004.685-688.

［6］ TRUONG B T，VENKATESH S.VideoAbstraction：A system atic review and classification［J］.ACM Trans on Multimedia Computing，Communications and Applications，2007，3（1）：1-37.

［7］ YUAN Jinhui，WANG Huiyi，XIAO Lan，et al.A form al study of shot boundary detect ion［J］.IEEE Trans on Circuits and System for Video Technology，2007，17（2）：168-186.

［8］ 黃 敏，趙 艷，王?，帲?基于數(shù)字水印技術(shù)的電子簽章算法研究［J］.河北工業(yè)科技，2012，29（3）：149-154.

HUANG Min，ZHAO Yan，WANG Haiyao，et al.Electronic signature algorithm based on digital signature and digital watermarking technology［J］.Hebei Journal of Science and Technology，2012，29（3）：149-154.

［9］ 李春華，秦志英.一種基于 DCT的圖像灰度水印算法［J］.河北工業(yè)科技，2012，29（3）：334-337.

LI Chunhua，QIN Zhiying.A gray level image watermarking algorithm based on DCT［J］.Hebei Journal of Science and Technology，2012，29（3）：334-337.

［10］ ESMAEILI M M，F(xiàn)ATOURECHI M，WARD R K.A robust and fast video copy detection system using content-based fingerprinting［J］.Information Forensics and Security，2011，6（1）：213-226.

［11］ NIE Xiushan，LIU Ju，SUN Jiande.Robust video hashing for identification based on MDS［A］.2010 IEEE International Conference on Acoustics Speech and Signal Processing（ICASSP）［C］.Dallas：［s.n.］，2010.1834-1837.

［12］ NIE Xiushan，LIU Ju，SUN Jiande，et al.Robust video hashing based on double-layer embedding［J］.IEEE Signal Processing Letters，2011，18（5）：307-310.

［13］ TIAN Y，JIANG M，MOUL X，et al.A multimodal video copy detection approach with sequential pyramid matching［A］.IEEE International Conference on Image Processing［C］.Brussels：Belgium，2011.11-14.

［14］ WU Xiao，LI Jintao，TANG Sheng，et al.Video copy detection based on spatio-temporal trajectory behavior feature［J］.Journal of Computer Research and Development，2010，47：1871-1877.

［15］ KIM C，VASUDEY B.Spation temporal sequence matching for efficient video copy detection［J］.Circuits and Systems for Video Technology，2005，15（1）：127-132.

Study on singular value decomposition based video copy detection

WU Mingjun1，HOU Yanyan1，LI Qinghua2
（1.College of Information Science and Engineering，Zaozhuang College，Zaozhuang Shandong 277160，China；2.College of Electrical Information and Control Engineering，Qilu University of Technology，Jinan Shandong 250353，China）

According to the problems of heavy computation load and sensitivity to video variation in conventional video copy detection algorithms，a novel video fingerprinting algorithm is presented to produce the key frame that contains the time and spatial information.The singular value decomposition is used to extract feature vectors of key frames，and then to reduce the dimension of video feature sequence.The improved video copy detection algorithm has good robustness against noise，frame shifting，frame-rate conversion and frame lost，etc.Compared with previous copy algorithms，the video copy detection recall and precision are improved with high matching rate to the source video，while the error rate is reduced.

video copy detection；singular value decomposition；feature extraction；video fingerprinting

TP391

A

1008-1542（2014）02-0179-05

10.7535／hbkd.2014yx02012

2013-12-12；

2014-01-19；責(zé)任編輯：李 穆

國(guó)家自然科學(xué)基金（41204025）

吳明君（1958-），男，山東蓬萊人，教授，主要從事視頻圖像處理方面的研究。

E-mail：wmjnet＠uzz.edu.cn