吳明君，侯艷艷，李慶華

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

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

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

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

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

視頻拷貝檢測；奇異值分解；特征提取；視頻指紋

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

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

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

1.1 視頻預(yù)處理

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

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

1.2 視頻片段劃分

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

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

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

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

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

1.3 關(guān)鍵幀選取

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

1.4 特征向量提取及匹配

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

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

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

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

Σ為半正定對角矩陣：

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

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

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

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

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

若待測視頻片段數(shù)k與原始視頻片段數(shù)差別較大時，采用滑動窗方法來進行匹配，以較短的視頻長度為滑動窗長度［13］。

2 仿真實驗及分析

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

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

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

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

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

本文選取20 min的7個視頻樣本進行實驗，相似度閾值β為0.13，wk＝γk中γ為0.65，表1為本

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

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

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

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

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

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

3 結(jié) 語

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

［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é)任編輯：李 穆

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

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

E-mail：wmjnet＠uzz.edu.cn