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

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

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

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

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

　由表1可見(jiàn)，3種方法達(dá)到了相同的召回率，即3種方法都檢測(cè)出了所要檢測(cè)的重復(fù)或近重復(fù)視頻，但是本文方法的準(zhǔn)確率明顯高于前兩種方法。由于本文方法先在鏡頭層次使用了鏡頭的時(shí)序一致性特征，在進(jìn)行每個(gè)關(guān)鍵幀圖像的特征提取之前進(jìn)行比較，濾除了一部分不相同的視頻，減少了關(guān)鍵幀圖像層次上特征的直接比較。本文提出的代表時(shí)序特征的過(guò)程簡(jiǎn)單，計(jì)算也比較容易，為后面進(jìn)行全局特征和局部特征的比較縮小了范圍，減少了計(jì)算量，若應(yīng)用到大規(guī)模的視頻數(shù)據(jù)集中，會(huì)有力地減少耗時(shí)，提高檢測(cè)速度。
　本文提出了在關(guān)鍵幀層次上進(jìn)行特征提取和匹配之前，首先使用一種新的特征代表整個(gè)鏡頭隨時(shí)間變化的時(shí)序特征，預(yù)先濾除不同視頻，以減少與不相同視頻的比較，節(jié)省檢測(cè)時(shí)間，再聯(lián)合全局特征與局部特征進(jìn)行一步步的拷貝檢測(cè)。通過(guò)對(duì)實(shí)驗(yàn)室的監(jiān)控視頻進(jìn)行驗(yàn)證實(shí)驗(yàn)，驗(yàn)證了對(duì)于給定的查詢視頻，可以得到與該查詢視頻重復(fù)或近重復(fù)的關(guān)鍵幀鏡頭及相應(yīng)的關(guān)鍵幀，即準(zhǔn)確檢測(cè)出與查詢視頻重復(fù)或近重復(fù)的視頻。本文方法有一定的有用性和準(zhǔn)確性，尤其對(duì)于運(yùn)動(dòng)場(chǎng)景和景物變化較大的監(jiān)控視頻檢測(cè)效果更好。未來(lái)的研究工作主要有：將本方法應(yīng)用到大規(guī)模網(wǎng)絡(luò)視頻集的近重復(fù)檢測(cè)中，使用合適的索引結(jié)構(gòu)和檢索方案，與其他近重復(fù)檢測(cè)方法進(jìn)行比較，以獲得更好的檢測(cè)效率和準(zhǔn)確率；優(yōu)化閾值設(shè)置方案，以能夠自適應(yīng)地對(duì)不同內(nèi)容的查詢視頻進(jìn)行特征比較，而不必每次設(shè)置不同的閾值。
參考文獻(xiàn)
[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.