近年來，在許多領(lǐng)域中出現(xiàn)了多媒體視頻自動匹配和識別的需求,同時也出現(xiàn)了很多關(guān)于視頻處理的方法，涉及醫(yī)學(xué)、電視系統(tǒng)、交通監(jiān)管系統(tǒng)及網(wǎng)絡(luò)數(shù)據(jù)庫等領(lǐng)域。隨著網(wǎng)絡(luò)數(shù)據(jù)庫的興起與發(fā)展，視頻技術(shù)也迅速地普及到網(wǎng)絡(luò)中來,例如百度、優(yōu)酷以及美國的“YouTube”等在線視頻網(wǎng)站。用戶每天都可以通過互聯(lián)網(wǎng)上傳并共享數(shù)以萬計的網(wǎng)絡(luò)視頻[1]，由此引發(fā)了網(wǎng)絡(luò)視頻的大量重復(fù)和數(shù)據(jù)庫冗余的現(xiàn)象。如何準(zhǔn)確快速地匹配這些網(wǎng)絡(luò)視頻，打造一個無重復(fù)文本、無資源浪費的綠色網(wǎng)絡(luò)，對當(dāng)前的視頻匹配技術(shù)提出了迫切的要求。

    以往的視頻匹配多采用基于內(nèi)容的處理方式，計算量巨大。對于背景動態(tài)變化的場景，參考文獻(xiàn)[2]利用動態(tài)紋理的方法實現(xiàn)視頻的登記。該方法通過多角度共同解決這些含糊不清的模型參數(shù),并且用多個視頻序列轉(zhuǎn)換識別參數(shù),達(dá)到一個標(biāo)準(zhǔn)的形式，降低了在視頻登記時出現(xiàn)多個圖像配準(zhǔn)的問題,從而有效地解決了現(xiàn)有的圖像匹配技術(shù)。近年來，出現(xiàn)了利用視頻序列或者是視頻運動軌跡來實現(xiàn)的視頻匹配或識別。參考文獻(xiàn)[3]提出了一種利用視頻圖像之間的軌跡進(jìn)行比對的方法,利用視頻序列運動軌跡所得到的稀疏矩陣對視頻進(jìn)行的匹配。該方法屬于視頻匹配中一個新的領(lǐng)域，具有良好的實用性和精確度。
    參考文獻(xiàn)[4]提出一種基于多維縮放的算法，能從不同修改程度的視頻中得到一個具有魯棒性特征的序列。但是這個方法對底層特征有巨大改變的視頻存在一定的缺陷，同時也會產(chǎn)生一些誤差。本文提出一種基于鏡頭模型和多維縮放方法的視頻內(nèi)容描述框架以及匹配方法，該方法對于鏡頭數(shù)目較多或者切變較快的視頻具有魯棒性。采用可伸縮鏡頭算法TS（Telescopic Shot）模型來描述各個鏡頭與視頻處理算法的對應(yīng)關(guān)系，提高了多維縮放方法的準(zhǔn)確度及對這類視頻的匹配能力。
1 鏡頭檢測技術(shù)
      視頻由一序列鏡頭組成，而相鄰鏡頭的連接方式是切變和漸變[5]。參考文獻(xiàn)[6]減少計算量是根據(jù)視頻一個鏡頭中大部分都是鏡頭內(nèi)幀,且內(nèi)容變化小的特點，利用K（K=11）步長滑動窗口和自適應(yīng)閾值把大部分的鏡頭內(nèi)幀去掉，只在剩下的少數(shù)候選幀中進(jìn)行切變和漸變檢測。為了提高檢測精度，切變則利用步長為1的方法計算鏡頭幀距離，并對閃光進(jìn)行排除。漸變采用參考文獻(xiàn)[6]提到的迭代方法進(jìn)行檢測。
2 多維縮放算法
   多維縮放算法MDS（Multi-Dimensional Scaling）是一種針對多變量分析的降維方法,該方法找到了視頻序列在低維空間中的運動軌跡，其核心含義是當(dāng)視頻中距離矩陣改變很大時，低維空間兩點之間的距離改變量卻很小。而當(dāng)修改距離矩陣時，對于低維空間的改變影響不大，保證了得到序列的魯棒性。
3 TS模型描述
    對于鏡頭切換快、數(shù)量多的視頻，采用多維縮放方法會遇到一些小的誤差。盡管大多數(shù)誤差不足以影響視頻匹配的效果，但為了力求更加精確的配準(zhǔn)率，本文還是插入了鏡頭分割的流程。對于整個算法的實現(xiàn)，提出了一種基于TS模型的多維縮放算法的實現(xiàn)，TS基本模型如圖1所示。
    本文提出的可伸縮式鏡頭模型成功地解決了兩類問題：一是可以減小經(jīng)過視頻匹配得出的視頻散列值的誤差，使多維縮放方法的魯棒性更高；二是降低了計算復(fù)雜度。在視頻哈希序列匹配的前提下，只需對視頻的鏡頭數(shù)量進(jìn)行檢測，驗證視頻切變與漸變的個數(shù)是否一致，如果一致則證明此視頻和目標(biāo)視頻為同一視頻，即匹配成功。該過程無需對全部鏡頭都做降維等復(fù)雜處理，即可達(dá)到可伸縮性的目的，大大減少了計算時間和空間的復(fù)雜度。其中鏡頭模型設(shè)定的閾值可采用自適應(yīng)性閾值，以鏡頭和完整視頻幀的比率自動調(diào)節(jié)，一般最少進(jìn)行降維處理的鏡頭個數(shù)占完整視頻的二分之一。
    算法描述如下：
       Input
           Original video V
       Begin
              Shot-Boundary Detection
         For K=1：N
            For N=1： M//M為具體視頻的鏡頭數(shù)
　　　　　             MDS
　　　
4 基于TS模型的匹配算法的實現(xiàn)
4.1 特征提取
    底層特征選取的兩個主要需求是不變性和敏感性，即底層特征對圖片的旋轉(zhuǎn)和平移等變化具有不變性，而對視頻內(nèi)容變化具有敏感性。文中采用基于像素的亮度變化特征及運動補償特征計算幀圖像的距離，使鏡頭邊界檢測方法更高地獨立于運動。
 
    (2)將圖像分成n塊，對其中一塊在另一幅待比較圖像的n塊中找到亮度距離最小的一塊，將該最小亮度差值作為該塊的距離值，然后把n個距離值累加，即可得到兩幅圖像的距離。本文則對每幀視頻圖像進(jìn)行8×8分塊的離散余弦變換(DCT)，并在輸出的zigzag陣列中對DCT系數(shù)進(jìn)行標(biāo)記，選取最中間的40％的DCT系數(shù)取平均值，這樣既避免了采用片面的系數(shù)值達(dá)不到準(zhǔn)確反映視頻變化的要求，又可以把一些不穩(wěn)定的距離因素排除，實現(xiàn)魯棒性。
4.2 鏡頭分割
    采用參考文獻(xiàn)[6]中的鏡頭邊界檢測視頻中的漸變幀和切變幀。對于候選片段集S，根據(jù)切變的特點，利用本文提出的新的距離計算方法和自適應(yīng)閾值來判定是否是切變，及其所在的幀位置，并進(jìn)行一次閃光排除過程，以排除閃光造成的誤檢。
    對于鏡頭的伸縮式閾值P的設(shè)定，采用自適應(yīng)的閾值，因為不同的視頻鏡頭內(nèi)容構(gòu)架不同，所得到的結(jié)果也不同。采用自適應(yīng)鏡頭閾值，可有效地節(jié)省計算時間和空間，如表1所示。

4.3 多維縮放
    對于分割完成的鏡頭序列N0，N1,…,Nm,首先選取第一個鏡頭N0，此時不需要再對這個鏡頭進(jìn)行特征提取，可直接調(diào)用此前已經(jīng)保存的鏡頭內(nèi)的亮度距離矩陣dij，對其進(jìn)行降維處理,如下式：
 

4.4 伸縮鏡頭匹配
    對于已經(jīng)完成的n個鏡頭內(nèi)的哈希序列匹配，判定是否已經(jīng)決定匹配，即已經(jīng)匹配出目標(biāo)視頻。如果沒有，則繼續(xù)對第n＋1個鏡頭進(jìn)行縮放匹配，直到視頻完全匹配為止。再對其余各個鏡頭進(jìn)行數(shù)量匹配，并對完整視頻幀數(shù)進(jìn)行匹配。這兩個步驟的計算量相當(dāng)小，目的是確保在最短的時間內(nèi)確定目標(biāo)視頻與源視頻為同一視頻。
5 試驗結(jié)果與分析
     實驗中采用50個內(nèi)容完全不同的視頻來訓(xùn)練伸縮式鏡頭模型。視頻長度介于60~40 000幀之間，視頻格式為AVI、MPEG-1等。
     實驗證明，當(dāng)視頻的鏡頭切換比較頻繁時，本文所得結(jié)果優(yōu)于單純基于多維縮放算法所取得的結(jié)果。同等情況下，由于漸變式鏡頭切換內(nèi)容變化較少，而切變式鏡頭是瞬間變化背景內(nèi)容，因此切變率較高，參考文獻(xiàn)[4]得出的哈希序列誤差相對多于本文算法。由于各個鏡頭的幀數(shù)不同，平均值又不能很精確地描述哈希序列中的誤差和鏡頭之間的關(guān)系，因此本文摒棄普通幀，或是相對變化緩慢的幀，選取兩鏡頭的分界處屬于切變的兩幀視頻圖像。分析大量視頻得到的結(jié)果可以得出一個結(jié)論，即對于切變幀的哈希值，如果不做鏡頭處理，直接將下一個鏡頭的第一幀和本鏡頭的最后一幀做距離的運算，則很容易出現(xiàn)不穩(wěn)定的結(jié)果。而利用鏡頭算法可以將視頻切變引起的誤差減少到最小。
　    圖3給出了利用本文算法對三種格式的視頻匹配與參考文獻(xiàn)[4]方法得出的平均誤差的比較。其中，視頻簽名VS（Video Signature）、MPEG-1、AVI代表的是三種視頻格式，分別與TS模型相結(jié)合，在圖中表示為TS-VS、TS-M、TS-A。
    從圖中可以看出，本文方法所得到的視頻哈希序列的誤差比參考文獻(xiàn)[4]有所減少。當(dāng)鏡頭數(shù)很少的時候，誤差數(shù)相差不太明顯，但當(dāng)鏡頭數(shù)很多時，其中切變數(shù)對誤差的影響較大，漸變數(shù)對誤差的影響較小。因此，經(jīng)過鏡頭分割之后，在切變點的兩幀之間的誤差有所減少。本文做了大量的實驗，分別對帶有視頻數(shù)字簽名、壓縮的MPEG-1和AVI格式的視頻進(jìn)行了多次驗證，并對實驗結(jié)果進(jìn)行了平均化處理。結(jié)果發(fā)現(xiàn)，基于TS鏡頭模型算法的處理方式對三種格式的視頻均有大幅度改進(jìn)。
    TS鏡頭算法的計算量相對減小了很多，用本文方法丟棄的不必要的距離計算更多，同時也彌補了鏡頭分割參與到算法中的計算量，計算效率優(yōu)勢更明顯。同時，在視頻哈希值可匹配的情況下，將鏡頭調(diào)用閾值定為1/2，省去了1/2的視頻多維縮放處理的計算量。由于添加了鏡頭分割的算法，所以計算量高于參考文獻(xiàn)[4]計算量的1/2。
    圖4中列舉了各種算法需要的計算時間，其中MDS代表多維縮放算法所得出的運算時間，Shot cuts代表鏡頭分割算法，而TS-MDS則是本文TS模型和MDS相結(jié)合的算法。

    由圖4可以看出，各個算法的時間與視頻幀數(shù)和鏡頭數(shù)之間有著明顯的線性關(guān)系。由于運行環(huán)境不同，得出的計算時間不同，但是同種運行環(huán)境得到的結(jié)果相似。通過大量的實驗發(fā)現(xiàn)，鏡頭數(shù)越多的視頻，本文方法的優(yōu)越性就越明顯。通過比較，采用單鏡頭時，本文方法計算時間不如參考文獻(xiàn)[4]的MDS方法；而采用多鏡頭時,鏡頭分割和TS-MDS方法的計算時間總和比MDS有明顯提高。
    對于內(nèi)容變化緩慢的視頻，本文方法的檢測準(zhǔn)確度和返回率與MDS方法相當(dāng)，對于有較多鏡頭的視頻，或者說是切變較為快速的視頻來說，本文方法的配準(zhǔn)率高于參考文獻(xiàn)[4]所述方法。
    本文提出一種基于可伸縮式鏡頭模型的視頻匹配算法，通過視頻分割成鏡頭的方式，在匹配有效的前提下，省去部分鏡頭的距離矩陣等運算，在一定程度上減少了算法的計算量。通過避開切變前后幀的不穩(wěn)定差值，從而大大減小了切變引起的哈希值的誤差。文中的可伸縮式鏡頭模型（TS模型）是根據(jù)切變對視頻散列的影響而提出的，并通過大量實驗驗證，具有一定的通用性。
參考文獻(xiàn)
[1] ESMAEILI M M, FATOURECHI M, WARD R K. A robust and fast video copy detection system using content-based  fingerprinting[J].IEEE Transactions on Information Forensics and security, 2011，6(1):213-226.
[2] RAVICHANDRAN A, VIDAL R. Video registration using  dynamic Textures[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011，33(1):158-171.
[3] NUNZIATI W, SCLAROFF S,BIMBO A D. Matching trajectories between Video Sequences by Exploiting a Sparse  Projective Invariant Representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010，32(3):517-529.
[4] Nie Xiushan, Liu Ju, SUN J. Robust video hashing for identification based on MDS[R]. Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference,2010.
[5] 顧家玉,覃團(tuán)發(fā),陳慧婷.一種基于MPEG-7顏色特征和塊運動信息的關(guān)鍵幀提取方法[J]. 廣西大學(xué)學(xué)報:自然科學(xué)版, 2010,4(2):310-314.
[6] Qin Tuanfa, Gu Jiayu, Chen Huiting, et al. A  fast shotboundary detection based on K-Step slipped window[R].Proceedings of IC-NIDC 2010.