摘  要： 設計了一種使用視頻鏡頭時序特征來實現級聯式檢測近重復視頻的算法。首先在進行關鍵幀特征提取之前，直接在鏡頭層次上提取時序特征，初步濾除完全不相同的視頻，然后對剩下的視頻幀提取全局顏色特征和SURF特征進行逐步檢測，最終獲得與查詢視頻近重復的視頻。對實驗室的監控視頻進行小范圍的驗證實驗，實驗結果表明，該算法與不用時序特征的方法相比有一定的有效性和準確性。
關鍵詞： 監控視頻；近重復檢測；時序特征；全局顏色特征；SURF

　近年來，數字視頻應用飛速發展，在視頻監控領域，需要從成千上萬個攝像頭產生的海量視頻中找到含有用戶關心的線索的視頻，比如穿紅色衣服女子唱歌的視頻片段，檢索需要耗費大量的人力物力。因此，視頻檢索、視頻摘要以及視頻編解碼等應用應運而生，如何在海量監控視頻數據中快速、準確地檢測到相同的視頻片段已成為多媒體內容分析和視頻檢索中的一個重要課題。
　傳統的近重復視頻檢測一般采用參考文獻[1]中描述的算法，即首先將視頻通過時間采樣或鏡頭邊界檢測算法檢測出多個子鏡頭，提取出各子鏡頭中的一個或多個關鍵幀圖像；然后使用某些高維特征向量（如顏色直方圖、局部二值模式（LBP）等）表示這些關鍵幀，作為視頻的全局簽名；最后通過某種相似性度量函數來計算兩個視頻的關鍵幀序列，以此來檢測兩個視頻是不是重復或近重復視頻。參考文獻[2]提出了一種基于全局簽名的視頻重復檢測算法，提出了一種稱為視頻直方圖的視頻簽名，用來表示視頻特征向量在特征空間的分布情況。參考文獻[3]介紹了一種結合時間-空間分布信息的時序特征和色彩范圍的視頻重復檢測算法。參考文獻[4]提出將視頻關鍵幀的全局特征與局部關鍵點結合起來檢測相似視頻，即采用分層的方法，通過比較視頻簽名過濾掉一些完全不相同的視頻，從而減少基于局部關鍵點的相似關鍵幀檢測的計算量，然后再用局部關鍵點檢測剩下的變化較大的視頻。這種以視頻內容為視頻序列匹配依據的方法一般都是在所有關鍵幀圖像上直接提取全局顏色特征，再使用圖像匹配算法比較相似性，在大量關鍵幀圖像的特征匹配中不僅占用大量計算時間，而且會丟失視頻序列的時間一致性信息。
　受參考文獻[4]啟發，本文在提取關鍵幀圖像的特征提取之前先在鏡頭層次提取出一種新的特征作為鏡頭的時序特征，再提取全局顏色特征和更精確的SURF局部特征進行檢測，最終得到與查詢視頻近重復的視頻，算法具體框架如圖1所示。

1 近重復監控視頻檢測算法
1.1 鏡頭邊界檢測
　鏡頭邊界檢測是視頻索引和檢索的第一步，即找出視頻序列中發生鏡頭變換的位置，以進一步將視頻分成獨立的鏡頭片段。本文采用的是基于邊緣輪廓差值法來檢測鏡頭邊界的方法[5]，使用Canny邊緣檢測算子依次逐幀檢測出各圖像幀的邊緣，將消失的舊邊緣和增加的新邊緣的差異不連續值與相鄰幀的不連續值作比較，通過設置合適的閾值，可以達到一定的自適應性，以滿足不同視頻的鏡頭邊界檢測。具體實現步驟如下：
　（1）初始化讀入視頻的第1幀圖像，將圖像轉化為灰度圖像，以便使用Canny邊緣檢測算子檢測出其邊緣，統計其邊緣元素個數，并通過形態學操作得到該圖像的膨脹圖像，將得到的邊緣二進制圖像反色。
　（2）按照讀入圖像幀的順序從第2幀開始直到視頻的最后一幀，使用步驟（1）中的方法將各圖像幀依次進行邊緣檢測，得到邊緣元素個數、膨脹圖像及反色邊緣二進制圖像。
　（3）通過圖像幀的兩兩依次進行與操作并統計前一圖像幀消失的邊緣點數目和后一圖像幀新增的邊緣點數目，定義一個邊緣輪廓差值函數framedif來進行鏡頭邊界點的評價度量：
　　
　其中，i的值從2到最后一幀，pi-1是前一圖像幀的邊緣數，pi是后一圖像幀的邊緣數，out是前一圖像幀消失的邊緣點數目，in是后一圖像幀新增的邊緣點的數目。
　（4）為達到一定的自適應性以滿足不同視頻的鏡頭邊界檢測，本文選取的比較度量是后一幀的邊緣輪廓差值與前一幀的邊緣輪廓差值的比值ratiodif，即：

　首先逐幀計算出各圖像的幀差歐氏距離，即對第i+2幀圖像的灰度值與第i+1幀圖像的灰度值的差減去第i+1幀圖像的灰度值與第i幀圖像的灰度值的差的平方進行求和，對和值求算術平方根，然后計算這些幀差歐氏距離的極值以及極值點對應的函數值，再計算各函數值的均值，極值點中函數值大于均值的點即為所要選取的關鍵幀圖像。
1.3 時序特征提取
　視頻是由一系列連續記錄的幀圖像組成的，是一個二維圖像流序列，檢測出的子鏡頭也是按照時間順序排列的，因此每個子鏡頭中提取出的關鍵幀圖像也必然存在著很大的時間一致性。前面提到，對于兩個視頻序列的匹配，大多數學者都是直接對各子鏡頭中每個關鍵幀圖像提取全局或局部特征，在關鍵幀層次上進行兩兩比較，該方法在大規模視頻數據集查找所需視頻時，若對很多與查詢視頻明顯不相同的干擾視頻進行檢測，則會花費大量時間。
　本文提出一種新的特征來表示鏡頭的時序特征，直接在關鍵幀所在的子鏡頭層次上進行比較，可在提取關鍵幀圖像的全局或局部特征之前，快速濾除與查詢視頻很不相同的無關視頻。具體做法如下：
　（1）在基于視頻序列連續一致性的前提下，先計算查詢視頻與待查詢視頻中所有視頻每個關鍵幀文件夾中的幀圖像數目，按照在關鍵幀中的時間順序，將各個關鍵幀圖像分成9塊，計算其中間第5塊的顏色特征。
　（2）將各個鏡頭中所有關鍵幀圖像第5塊的顏色特征組成一個行數為關鍵幀數目、列數為36的矩陣，即可用來表示每一個關鍵幀集合中的所有幀圖像在連續時間上的時序特征。
　（3）將得到的查詢視頻的各關鍵幀子鏡頭的時序特征分別與待查詢視頻的所有關鍵幀子鏡頭的時序特征進行余弦相似度比較。
　（4）將計算得到的比較值與事先設定的閾值進行比較，若存在大于這一閾值的時序特征，就取出待查詢視頻中滿足這一條件的關鍵幀子鏡頭，以進行進一步檢測；若沒有滿足條件的關鍵幀子鏡頭，則說明這個待查詢視頻與查詢視頻很不相同，可以將其濾除，從而避免了再進行視頻特征提取和兩兩特征匹配，大大節省檢測時間。
1.4 全局顏色特征提取
　全局特征中顏色特征一般是顏色直方圖，能簡單描述一幅圖像中顏色的全局分布。在這里也簡單地提取出視頻關鍵幀圖像的36維的顏色直方圖來表示這些關鍵幀，作為視頻的全局顏色特征進行特征相似性比較。
1.5 SURF特征提取
　局部特征描述圖像局部區域信息，計算容易，能抵抗局部遮擋，對視覺變換不敏感。常用的局部關鍵點檢測算子有Difference-of-Gaussian（DoG）算子、Harris-Affine算子等。最常用的局部關鍵點描述子有SIFT算子、PCA-SIFT算子、GLOH算子以及依賴于積分圖像的圖像卷積的SURF算子[6]。鑒于SURF算法對于圖像旋轉、平移、縮放和噪聲影響具有較好的魯棒性，而且計算速度比SIFT算法快很多，本文把SURF的這種優勢應用到下一步的局部特征提取中。
2 實驗結果與分析
　本文的實驗是一個小范圍的驗證實驗，所使用的視頻來源于合肥工業大學計算機與信息學院DSP聯合實驗室各個小實驗室的監控視頻。由于每次拍攝的監控視頻一般時長為1 h~2 h，在驗證實驗中，重新構造了實驗數據集，對于不同時間不同地點拍攝的各類視頻進行截取，分割成時長均約為1分30秒的視頻。通過混合不同時間、不同地點的視頻，構造出每類包含20個這樣視頻的待查詢視頻集。在每類的20個視頻中，選取一個視頻為查詢視頻之后，其他的視頻中，一類是包含查詢視頻的近重復視頻，另一類是與查詢視頻不相同的視頻，下面對這些視頻進行驗證實驗。
　本實驗所用的計算機配置為Intel（R）Core（TM）i3 2.93 GHz CPU，2 GB內存，實驗平臺為Matlab 7.11.0（R2010b）。實驗所用的實驗評價標準為：（1）定性地分析使用這種算法的有效性和準確性；（2）大規模視頻集中進行拷貝檢測和近重復檢測常用的準確率和召回率。
　實驗中對很多不同同源視頻的兩類都進行了驗證，限于文章篇幅，本文只對其中一類的實驗結果進行說明。選取的視頻如圖2所示，其中1.avi為預先假設的查詢視頻，2.avi視頻為選取的與查詢視頻在不同場景、不同主體人物下拍攝的監控視頻，即看作無關的干擾視頻，這里該類視頻共有7個，剩下的如3.avi視頻為與查詢視頻重復或近重復的視頻，包含與查詢視頻有相同場景但主題人物不同和有不同場景但有相同主體人物動作的情況。這些視頻的幀率均為25 f/s，碼率均為46.1 Mb/s，畫面尺寸為320 pix×240 pix，包括1.avi在內的這20個視頻中共有13個與查詢視頻重復或近重復的視頻，有7個不相同的視頻。

　在實驗中進行時序一致性特征和分塊顏色特征比較時，本文采取一般算法使用的直接將余弦值與事先設定的一個閾值相比較的度量方法。滿足條件的關鍵幀集合對應的被查詢視頻有可能是要檢測出來的重復或近重復視頻，將再進行下一步更精確的檢測；而不滿足條件的即為與查詢視頻不相同的視頻，直接濾除掉，以減少后面的檢測量。但是在進行SURF特征的比較時，本文采用的是一種同時滿足兩個閾值的度量方法。每一對SURF特征相比較的余弦度量值的維數為Mi×Nj，其中Mi表示查詢視頻中一個鏡頭中第i個關鍵幀的局部關鍵點數目，Nj表示一個被查詢視頻對應的一個鏡頭中第j個關鍵幀的局部關鍵點數目。當比較這個余弦值是否滿足近重復檢測的條件時，首先計算這個矩陣中的元素個數，即Mi×Nj個；再計算矩陣中大于第一個閾值T1的元素個數，記為M；然后比較M和Mi×Nj的比值是否大于第二個閾值T2。同時滿足這兩個閾值條件的關鍵幀集對應的被查詢視頻就是最終得到的重復或近重復視頻。
　本實驗中，當查詢視頻1.avi與20個待查詢視頻相比較時，通過每一步都可以濾除掉一部分視頻，并最終檢測出重復或近重復視頻。在進行時序一致性特征比較時，當閾值設置為0.985時，兩個完全不同場景、不同人物的視頻首先被濾除；在進行全局顏色特征比較時，當閾值設置為0.99時，濾除3個不同的視頻；最后，在進行SURF特征比較時，當設置閾值T1=0.6、閾值T2=0.7時，濾除1個視頻。實驗最終剩下14個視頻，其中13個重復或近重復視頻被全部檢測出來，7個不相同的視頻只濾除了6個，還有一個不相同的視頻沒有被濾除而和近重復視頻一起被誤檢出來。假設CAS_TF表示本文提出的使用了視頻鏡頭時序特征的方法，M_GLOF和M_HIER分別表示直接使用全局顏色特征和聯合全局特征與局部特征的分層方法，則使用這3種方法進行小范圍的視頻檢測的實驗結果比較如表1所示，其中p/q表示在q個待查詢視頻中返回p個重復或近重復視頻。

　由表1可見，3種方法達到了相同的召回率，即3種方法都檢測出了所要檢測的重復或近重復視頻，但是本文方法的準確率明顯高于前兩種方法。由于本文方法先在鏡頭層次使用了鏡頭的時序一致性特征，在進行每個關鍵幀圖像的特征提取之前進行比較，濾除了一部分不相同的視頻，減少了關鍵幀圖像層次上特征的直接比較。本文提出的代表時序特征的過程簡單，計算也比較容易，為后面進行全局特征和局部特征的比較縮小了范圍，減少了計算量，若應用到大規模的視頻數據集中，會有力地減少耗時，提高檢測速度。
　本文提出了在關鍵幀層次上進行特征提取和匹配之前，首先使用一種新的特征代表整個鏡頭隨時間變化的時序特征，預先濾除不同視頻，以減少與不相同視頻的比較，節省檢測時間，再聯合全局特征與局部特征進行一步步的拷貝檢測。通過對實驗室的監控視頻進行驗證實驗，驗證了對于給定的查詢視頻，可以得到與該查詢視頻重復或近重復的關鍵幀鏡頭及相應的關鍵幀，即準確檢測出與查詢視頻重復或近重復的視頻。本文方法有一定的有用性和準確性，尤其對于運動場景和景物變化較大的監控視頻檢測效果更好。未來的研究工作主要有：將本方法應用到大規模網絡視頻集的近重復檢測中，使用合適的索引結構和檢索方案，與其他近重復檢測方法進行比較，以獲得更好的檢測效率和準確率；優化閾值設置方案，以能夠自適應地對不同內容的查詢視頻進行特征比較，而不必每次設置不同的閾值。
參考文獻
[1] Shang L F， Yang L J， Wang F， et al. Real-time large scale near-duplicate web video retrieval[C]. Proceedings of ACM International Conference on Multimedia （MM）， 2010： 531-540.  
[2] Lu L， Wei L， Xian S H， et al. Video histogram： a novel signature for efficient Web video duplicate detection[J]. Lecture Notes in Computer Science， 2007： 94-103.  
[3] Yuan J， Duan L Y， RANGANATH S， et al. Fast and robust short video clip search for copy detection[C]. Proceedings of Pacific-Rim Conference on Multimedia （PCM） ， 2004： 479-488.
[4] Wu X， NGO C W， ALEXANDER G H， et al. Real-time near-duplicate elimination for Web video search with content and context[C]. IEEE Transactions on Multimedia， 2009， 11（2）： 196-207.
[5] LIENHART R. Comparison of automatic shot boundary detection algorithms[C]. SPIE， 1999， 3656：290-301.
[6]  BAY H， TUYTELAARS T，  VAN G L. SURF： speeded up robust features[J]. Computer Vision and Image Understanding， 2008， 110（3）： 346-359.