一種新的近重復(fù)監(jiān)控視頻檢測算法*

郭丁云，楊艷芳，朱俊俊，齊美彬

（1.合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥230009；2.合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院，安徽 合肥230009）

近年來，數(shù)字視頻應(yīng)用飛速發(fā)展，在視頻監(jiān)控領(lǐng)域，需要從成千上萬個攝像頭產(chǎn)生的海量視頻中找到含有用戶關(guān)心的線索的視頻，比如穿紅色衣服女子唱歌的視頻片段，檢索需要耗費大量的人力物力。因此，視頻檢索、視頻摘要以及視頻編解碼等應(yīng)用應(yīng)運而生，如何在海量監(jiān)控視頻數(shù)據(jù)中快速、準確地檢測到相同的視頻片段已成為多媒體內(nèi)容分析和視頻檢索中的一個重要課題。

傳統(tǒng)的近重復(fù)視頻檢測一般采用參考文獻[1]中描述的算法，即首先將視頻通過時間采樣或鏡頭邊界檢測算法檢測出多個子鏡頭，提取出各子鏡頭中的一個或多個關(guān)鍵幀圖像；然后使用某些高維特征向量（如顏色直方圖、局部二值模式（LBP）等）表示這些關(guān)鍵幀，作為視頻的全局簽名；最后通過某種相似性度量函數(shù)來計算兩個視頻的關(guān)鍵幀序列，以此來檢測兩個視頻是不是重復(fù)或近重復(fù)視頻。參考文獻[2]提出了一種基于全局簽名的視頻重復(fù)檢測算法，提出了一種稱為視頻直方圖的視頻簽名，用來表示視頻特征向量在特征空間的分布情況。參考文獻[3]介紹了一種結(jié)合時間-空間分布信息的時序特征和色彩范圍的視頻重復(fù)檢測算法。參考文獻[4]提出將視頻關(guān)鍵幀的全局特征與局部關(guān)鍵點結(jié)合起來檢測相似視頻，即采用分層的方法，通過比較視頻簽名過濾掉一些完全不相同的視頻，從而減少基于局部關(guān)鍵點的相似關(guān)鍵幀檢測的計算量，然后再用局部關(guān)鍵點檢測剩下的變化較大的視頻。這種以視頻內(nèi)容為視頻序列匹配依據(jù)的方法一般都是在所有關(guān)鍵幀圖像上直接提取全局顏色特征，再使用圖像匹配算法比較相似性，在大量關(guān)鍵幀圖像的特征匹配中不僅占用大量計算時間，而且會丟失視頻序列的時間一致性信息。

[4]啟發(fā)，本文在提取關(guān)鍵幀圖像的特征提取之前先在鏡頭層次提取出一種新的特征作為鏡頭的時序特征，再提取全局顏色特征和更精確的SURF局部特征進行檢測，最終得到與查詢視頻近重復(fù)的視頻，算法具體框架如圖1所示。

圖1 本文算法設(shè)計框架

1 近重復(fù)監(jiān)控視頻檢測算法

1.1 鏡頭邊界檢測

鏡頭邊界檢測是視頻索引和檢索的第一步，即找出視頻序列中發(fā)生鏡頭變換的位置，以進一步將視頻分成獨立的鏡頭片段。本文采用的是基于邊緣輪廓差值法來檢測鏡頭邊界的方法[5]，使用Canny邊緣檢測算子依次逐幀檢測出各圖像幀的邊緣，將消失的舊邊緣和增加的新邊緣的差異不連續(xù)值與相鄰幀的不連續(xù)值作比較，通過設(shè)置合適的閾值，可以達到一定的自適應(yīng)性，以滿足不同視頻的鏡頭邊界檢測。具體實現(xiàn)步驟如下：

（1）初始化讀入視頻的第1幀圖像，將圖像轉(zhuǎn)化為灰度圖像，以便使用Canny邊緣檢測算子檢測出其邊緣，統(tǒng)計其邊緣元素個數(shù)，并通過形態(tài)學(xué)操作得到該圖像的膨脹圖像，將得到的邊緣二進制圖像反色。

（2）按照讀入圖像幀的順序從第2幀開始直到視頻的最后一幀，使用步驟（1）中的方法將各圖像幀依次進行邊緣檢測，得到邊緣元素個數(shù)、膨脹圖像及反色邊緣二進制圖像。

（3）通過圖像幀的兩兩依次進行與操作并統(tǒng)計前一圖像幀消失的邊緣點數(shù)目和后一圖像幀新增的邊緣點數(shù)目，定義一個邊緣輪廓差值函數(shù)framedif來進行鏡頭邊界點的評價度量：

其中，i的值從2到最后一幀，pi-1是前一圖像幀的邊緣數(shù)，pi是后一圖像幀的邊緣數(shù)，out是前一圖像幀消失的邊緣點數(shù)目，in是后一圖像幀新增的邊緣點的數(shù)目。

（4）為達到一定的自適應(yīng)性以滿足不同視頻的鏡頭邊界檢測，本文選取的比較度量是后一幀的邊緣輪廓差值與前一幀的邊緣輪廓差值的比值ratiodif，即：

當ratiodif的值大于預(yù)先設(shè)置的閾值T時，就說明兩個圖像幀之間發(fā)生了鏡頭變化。

另外，考慮到有些監(jiān)控視頻中會有一些運動幅度變化很小的漸變視頻，其鏡頭邊界點非常不明顯，其后一幀的邊緣輪廓差值與前一幀的邊緣輪廓差值相差不大，這種情況下使用邊緣輪廓差值法將檢測不到符合大于閾值條件的鏡頭邊界點。為了增加實驗的廣泛適用性和準確性，對于使用邊緣輪廓差值法檢測不到鏡頭邊界點的情況，則只取其中間一幀作為鏡頭邊界點，將整個視頻分成兩個子鏡頭，然后再按照同樣的關(guān)鍵幀提取算法進行檢測。

1.2 關(guān)鍵幀圖像提取

視頻的匹配檢測歸根到底就是圖像的匹配檢測，本文采用的是基于幀差的歐式距離來提取各個子鏡頭中的關(guān)鍵幀，歐式距離越大，說明幀間的差異越大，越可能出現(xiàn)關(guān)鍵幀。幀差歐氏距離的表達式為：

首先逐幀計算出各圖像的幀差歐氏距離，即對第i+2幀圖像的灰度值與第i+1幀圖像的灰度值的差減去第i+1幀圖像的灰度值與第i幀圖像的灰度值的差的平方進行求和，對和值求算術(shù)平方根，然后計算這些幀差歐氏距離的極值以及極值點對應(yīng)的函數(shù)值，再計算各函數(shù)值的均值，極值點中函數(shù)值大于均值的點即為所要選取的關(guān)鍵幀圖像。

1.3 時序特征提取

視頻是由一系列連續(xù)記錄的幀圖像組成的，是一個二維圖像流序列，檢測出的子鏡頭也是按照時間順序排列的，因此每個子鏡頭中提取出的關(guān)鍵幀圖像也必然存在著很大的時間一致性。前面提到，對于兩個視頻序列的匹配，大多數(shù)學(xué)者都是直接對各子鏡頭中每個關(guān)鍵幀圖像提取全局或局部特征，在關(guān)鍵幀層次上進行兩兩比較，該方法在大規(guī)模視頻數(shù)據(jù)集查找所需視頻時，若對很多與查詢視頻明顯不相同的干擾視頻進行檢測，則會花費大量時間。

本文提出一種新的特征來表示鏡頭的時序特征，直接在關(guān)鍵幀所在的子鏡頭層次上進行比較，可在提取關(guān)鍵幀圖像的全局或局部特征之前，快速濾除與查詢視頻很不相同的無關(guān)視頻。具體做法如下：

（1）在基于視頻序列連續(xù)一致性的前提下，先計算查詢視頻與待查詢視頻中所有視頻每個關(guān)鍵幀文件夾中的幀圖像數(shù)目，按照在關(guān)鍵幀中的時間順序，將各個關(guān)鍵幀圖像分成9塊，計算其中間第5塊的顏色特征。

（2）將各個鏡頭中所有關(guān)鍵幀圖像第5塊的顏色特征組成一個行數(shù)為關(guān)鍵幀數(shù)目、列數(shù)為36的矩陣，即可用來表示每一個關(guān)鍵幀集合中的所有幀圖像在連續(xù)時間上的時序特征。

（3）將得到的查詢視頻的各關(guān)鍵幀子鏡頭的時序特征分別與待查詢視頻的所有關(guān)鍵幀子鏡頭的時序特征進行余弦相似度比較。

（4）將計算得到的比較值與事先設(shè)定的閾值進行比較，若存在大于這一閾值的時序特征，就取出待查詢視頻中滿足這一條件的關(guān)鍵幀子鏡頭，以進行進一步檢測；若沒有滿足條件的關(guān)鍵幀子鏡頭，則說明這個待查詢視頻與查詢視頻很不相同，可以將其濾除，從而避免了再進行視頻特征提取和兩兩特征匹配，大大節(jié)省檢測時間。

1.4 全局顏色特征提取

全局特征中顏色特征一般是顏色直方圖，能簡單描述一幅圖像中顏色的全局分布。在這里也簡單地提取出視頻關(guān)鍵幀圖像的36維的顏色直方圖來表示這些關(guān)鍵幀，作為視頻的全局顏色特征進行特征相似性比較。

1.5 SURF特征提取

局部特征描述圖像局部區(qū)域信息，計算容易，能抵抗局部遮擋，對視覺變換不敏感。常用的局部關(guān)鍵點檢測算子有Difference-of-Gaussian（DoG）算子、Harris-Affine算子等。最常用的局部關(guān)鍵點描述子有SIFT算子、PCA-SIFT算子、GLOH算子以及依賴于積分圖像的圖像卷積的SURF算子[6]。鑒于SURF算法對于圖像旋轉(zhuǎn)、平移、縮放和噪聲影響具有較好的魯棒性，而且計算速度比SIFT算法快很多，本文把SURF的這種優(yōu)勢應(yīng)用到下一步的局部特征提取中。

2 實驗結(jié)果與分析

本文的實驗是一個小范圍的驗證實驗，所使用的視頻來源于合肥工業(yè)大學(xué)計算機與信息學(xué)院DSP聯(lián)合實驗室各個小實驗室的監(jiān)控視頻。由于每次拍攝的監(jiān)控視頻一般時長為1 h～2 h，在驗證實驗中，重新構(gòu)造了實驗數(shù)據(jù)集，對于不同時間不同地點拍攝的各類視頻進行截取，分割成時長均約為1分30秒的視頻。通過混合不同時間、不同地點的視頻，構(gòu)造出每類包含20個這樣視頻的待查詢視頻集。在每類的20個視頻中，選取一個視頻為查詢視頻之后，其他的視頻中，一類是包含查詢視頻的近重復(fù)視頻，另一類是與查詢視頻不相同的視頻，下面對這些視頻進行驗證實驗。

本實驗所用的計算機配置為Intel（R）Core（TM）i3 2.93 GHz CPU，2 GB內(nèi)存，實驗平臺為Matlab 7.11.0（R2010b）。實驗所用的實驗評價標準為：（1）定性地分析使用這種算法的有效性和準確性；（2）大規(guī)模視頻集中進行拷貝檢測和近重復(fù)檢測常用的準確率和召回率。

實驗中對很多不同同源視頻的兩類都進行了驗證，限于文章篇幅，本文只對其中一類的實驗結(jié)果進行說明。選取的視頻如圖2所示，其中1.avi為預(yù)先假設(shè)的查詢視頻，2.avi視頻為選取的與查詢視頻在不同場景、不同主體人物下拍攝的監(jiān)控視頻，即看作無關(guān)的干擾視頻，這里該類視頻共有7個，剩下的如3.avi視頻為與查詢視頻重復(fù)或近重復(fù)的視頻，包含與查詢視頻有相同場景但主題人物不同和有不同場景但有相同主體人物動作的情況。這些視頻的幀率均為25 f/s，碼率均為46.1 Mb/s，畫面尺寸為320 pix×240 pix，包括1.avi在內(nèi)的這20個視頻中共有13個與查詢視頻重復(fù)或近重復(fù)的視頻，有7個不相同的視頻。

圖2 本文中選取的監(jiān)控視頻

在實驗中進行時序一致性特征和分塊顏色特征比較時，本文采取一般算法使用的直接將余弦值與事先設(shè)定的一個閾值相比較的度量方法。滿足條件的關(guān)鍵幀集合對應(yīng)的被查詢視頻有可能是要檢測出來的重復(fù)或近重復(fù)視頻，將再進行下一步更精確的檢測；而不滿足條件的即為與查詢視頻不相同的視頻，直接濾除掉，以減少后面的檢測量。但是在進行SURF特征的比較時，本文采用的是一種同時滿足兩個閾值的度量方法。每一對SURF特征相比較的余弦度量值的維數(shù)為Mi×Nj，其中Mi表示查詢視頻中一個鏡頭中第i個關(guān)鍵幀的局部關(guān)鍵點數(shù)目，Nj表示一個被查詢視頻對應(yīng)的一個鏡頭中第j個關(guān)鍵幀的局部關(guān)鍵點數(shù)目。當比較這個余弦值是否滿足近重復(fù)檢測的條件時，首先計算這個矩陣中的元素個數(shù)，即Mi×Nj個；再計算矩陣中大于第一個閾值T1的元素個數(shù)，記為M；然后比較M和Mi×Nj的比值是否大于第二個閾值T2。同時滿足這兩個閾值條件的關(guān)鍵幀集對應(yīng)的被查詢視頻就是最終得到的重復(fù)或近重復(fù)視頻。

本實驗中，當查詢視頻1.avi與20個待查詢視頻相比較時，通過每一步都可以濾除掉一部分視頻，并最終檢測出重復(fù)或近重復(fù)視頻。在進行時序一致性特征比較時，當閾值設(shè)置為0.985時，兩個完全不同場景、不同人物的視頻首先被濾除；在進行全局顏色特征比較時，當閾值設(shè)置為0.99時，濾除3個不同的視頻；最后，在進行SURF特征比較時，當設(shè)置閾值T1=0.6、閾值T2=0.7時，濾除1個視頻。實驗最終剩下14個視頻，其中13個重復(fù)或近重復(fù)視頻被全部檢測出來，7個不相同的視頻只濾除了6個，還有一個不相同的視頻沒有被濾除而和近重復(fù)視頻一起被誤檢出來。假設(shè)CAS_TF表示本文提出的使用了視頻鏡頭時序特征的方法，M_GLOF和M_HIER分別表示直接使用全局顏色特征和聯(lián)合全局特征與局部特征的分層方法，則使用這3種方法進行小范圍的視頻檢測的實驗結(jié)果比較如表1所示，其中p/q表示在q個待查詢視頻中返回p個重復(fù)或近重復(fù)視頻。

表1 實驗結(jié)果比較

由表1可見，3種方法達到了相同的召回率，即3種方法都檢測出了所要檢測的重復(fù)或近重復(fù)視頻，但是本文方法的準確率明顯高于前兩種方法。由于本文方法先在鏡頭層次使用了鏡頭的時序一致性特征，在進行每個關(guān)鍵幀圖像的特征提取之前進行比較，濾除了一部分不相同的視頻，減少了關(guān)鍵幀圖像層次上特征的直接比較。本文提出的代表時序特征的過程簡單，計算也比較容易，為后面進行全局特征和局部特征的比較縮小了范圍，減少了計算量，若應(yīng)用到大規(guī)模的視頻數(shù)據(jù)集中，會有力地減少耗時，提高檢測速度。

本文提出了在關(guān)鍵幀層次上進行特征提取和匹配之前，首先使用一種新的特征代表整個鏡頭隨時間變化的時序特征，預(yù)先濾除不同視頻，以減少與不相同視頻的比較，節(jié)省檢測時間，再聯(lián)合全局特征與局部特征進行一步步的拷貝檢測。通過對實驗室的監(jiān)控視頻進行驗證實驗，驗證了對于給定的查詢視頻，可以得到與該查詢視頻重復(fù)或近重復(fù)的關(guān)鍵幀鏡頭及相應(yīng)的關(guān)鍵幀，即準確檢測出與查詢視頻重復(fù)或近重復(fù)的視頻。本文方法有一定的有用性和準確性，尤其對于運動場景和景物變化較大的監(jiān)控視頻檢測效果更好。未來的研究工作主要有：將本方法應(yīng)用到大規(guī)模網(wǎng)絡(luò)視頻集的近重復(fù)檢測中，使用合適的索引結(jié)構(gòu)和檢索方案，與其他近重復(fù)檢測方法進行比較，以獲得更好的檢測效率和準確率；優(yōu)化閾值設(shè)置方案，以能夠自適應(yīng)地對不同內(nèi)容的查詢視頻進行特征比較，而不必每次設(shè)置不同的閾值。

參考文獻

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