一種支持不同時間尺度的視頻相似性匹配算法

(北京工業大學電子信息與控制工程學院 電子工程系， 北京 100124)

摘 要：針對不同時間尺度視頻間的匹配問題，如人為再編輯（快進、慢放等）視頻與原始視頻間的匹配以及不同幀率視頻間的檢索等，提出了一種基于動態時間規劃的最優匹配算法。在子片段的基礎上進行視頻相似性匹配，通過極小化兩段視頻的整體距離建立視頻之間的子片段對應關系，引入搜索門限值，將全局搜索轉變為在門限區域內的局部搜索，保持視頻內部各子片段之間的時序關系并能處理非線性偏移。該算法能夠成功地匹配不同時間尺度的相似視頻，并能實現海量視頻的快速檢索。實驗結果證明了該算法比傳統的基于視覺相似性的視頻片段檢索算法更快速有效。

關鍵詞：基于內容的視頻檢索；時間尺度；子片段；動態規劃；最優匹配

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2009)01036903

Video similarity matching algorithm supporting for different time scales

DENG Zhipin，JIA Kebin

(Dept. of Electronic Engineering， School of Electronic Information Control Engineering， Beijing University of Technology， Beijing 100124， China)

Abstract:Based on the analysis of video retrieval issues among different time scales， such as retrieval between reedit video (speed forward or slowmotion) or original video and different frame rate (PAL or NTSC) videos，this paper proposed a novel dynamic time warping (DTW) optimal matching algorithm. This algorithm established subsegment correspondences by minimizing global differences between them， introduced search bound to change the whole searching to local searching， keeped temporal order of subsegments and could successfully matching similar videos which had different time scale. Experimental results show that the algorithm is more efficient and robust than the traditional similarity matching algorithm based on visual similarity.

Key words:content based video retrieval; time scales; subsegments; dynamic time warping (DTW); optimal matching

0 引言

隨著網絡信息交互技術的發展和視頻制作技術的普及，視頻數據庫中很多相似的視頻片段并不具有相同的長度，因此，不同時間尺度視頻間的匹配檢索問題日益突出，如人為再編輯（快進、慢放等）視頻與原始視頻間的匹配，不同幀率（PAL 或NTSC）視頻間的檢索等。視頻相似性檢索要求能夠檢索到經過后期編輯增加或刪除某些圖像幀所產生的包含快慢鏡頭的視頻片段。

當前基于樣例的視頻檢索技術多以鏡頭或幀為數據單元，進行視頻特征數據庫的組織管理和查詢[1~3]，降低了查詢精度或是造成視頻片段相似度計算量過大，很難達到快速查找的目的，并且不能有效地解決不同時間尺度視頻的檢索問題。一些算法采用幀匹配方法以得到視頻片段之間較好的相似度關系[4，5]，雖然這種方法可以在一定程度上解決不同時間尺度相似視頻片段的匹配問題，但并沒有充分利用視頻在時間域中的相關性。此外，代表幀的選取較為困難，嚴重影響了算法的查準率和查全率。文獻[6]利用高維索引結構組織視頻特征數據庫，并采用順序掃描特征庫和逐幀匹配的方法構造候選視頻片段。但是由于視頻特征數據庫的規模巨大，這種通過順序掃描整個特征庫并逐幀比對計算相似性距離，得到每個可能的匹配對的方法勢必產生大量的數據訪問時間和相似度計算時間，從而不可避免地導致查詢效率低下，并且在視頻片段檢索中，兩段在內容上相似的視頻片段時間尺度可能不一致，對于查詢這樣的視頻片段，該方法將無能為力。文獻[7]中提出利用順序掃描和滑動窗口的方法構造候選視頻片段，通過構造大量的候選視頻片段保證了較高的查全率，但其相似度定義完全放棄視頻片段內各鏡頭相似度值的差異和鏡頭的時序關系，只考慮相似鏡頭的個數，因此查詢準確率不高。

鑒于此，通過分析不同時間尺度視頻產生的原因，本文提出了一種新的基于動態時間規劃的最優匹配算法。首先借用介于鏡頭與幀之間的數據表示形式——子片段[8]的概念，作為視頻最小的數據單元，并以此進行相似視頻片段的查詢。在相似性匹配方面，通過極小化兩段視頻的整體距離建立視頻之間的子片段對應關系，引入搜索門限值，將全局搜索轉變為在門限區域內的局部搜索，保持視頻內部各子片段之間的時序關系并能處理非線性偏移。該算法能夠成功匹配不同時間尺度的相似視頻，并能實現海量視頻數據庫的快速檢索。 

視頻片段檢索流程如圖1所示。首先視頻特征組織模塊對視頻數據庫中的所有視頻片段進行子片段的分割，提取各個子片段的特征，并且建立索引以備后期查詢。用戶通過輸入查詢樣例，由查詢樣例分析模塊對樣例視頻進行子片段分割，并且提取特征來與視頻數據庫中的視頻特征進行子片段匹配，進而視頻片段查詢算法會實現樣例視頻和數據庫中的待查詢視頻之間的相似性匹配，最后返回查詢結果。

1 子片段分割

子片段是介于幀與鏡頭之間的有序幀序列，子片段內的各幀在內容上十分相似而且保持了其在視頻數據庫中的時序關系。以子片段為基本的查詢單位進行相似視頻片段查詢不僅提高了查詢速度而且還盡可能地保證了查詢精度。

子片段分割算法示意如下：首先將視頻中的每一幀分割成2×2的子塊，計算每一子塊的平均亮度值，并對這些值進行排序，如圖2所示；然后用排序矩陣值作為分割特征，將亮度排序相同的相鄰幀分到一個子片段中。

圖3給出了一個子片段分割的例子。假設幀i的四個子塊的亮度排序特征值為{1， 3， 4， 2}，第i+1幀和第i+2幀的亮度排序特征值也為{1， 3， 4， 2}，則它們屬于同一個子片段。由于幀i+3四個子塊所有的亮度排序特征值為{2， 4， 1，3}，與第i+2幀的亮度排序特征值不同，不屬于同一個子片段。

這種基于亮度排序的子片段分割算法，將一個鏡頭中具有相同亮度排序的相鄰幀分配到一個子片段中。由于子片段長度由亮度排序一致的幀的個數決定，可以有效處理不同時間尺度的問題。

2一種基于動態時間規劃的最優匹配算法

傳統的基于視覺相似性的視頻相似性檢索算法雖然能夠在一定程度上解決了不同時間尺度視頻間的匹配問題。但是要對查詢樣例視頻的每個子片段均在待匹配視頻子片段中找到與其最相似的片段，是一種全局搜索方法。當查詢視頻片段中包含過多子片段時，相似度計算將占用大量查詢時間，嚴重影響查詢效率。因此，結合不同時間尺度視頻間的匹配問題，本文提出一種新的基于DTW的最優匹配算法， 動態時間規劃(dynamic time warping，DTW)[9]是一種在語音處理中廣泛應用的模板匹配算法，它是動態規劃算法的一類變種。DTW算法使用遞歸的方法計算兩個長度不同的模板之間的相似程度，用失真距離表示，并找到滿足兩序列距離最小的兩序列各點的對應關系，如圖4所示。將查詢片段T的各個子片段n=1～N在一個二維直角坐標系中的橫軸上標出，將候選片段R的各個子片段m=1～M在縱軸上標出。通過這些表示子片段序號的整數坐標畫出縱橫線即形成網絡，網格中的每一個交叉點（n，m）對應兩個子片段關鍵幀的相似性距離。該算法的目的是在參考序列R與測試序列T之間找到一條優化的時間校準匹配路徑，使得該路徑上各點的距離和最小。 

本文提出的這種新的基于DTW的最優匹配算法，如圖5所示。在子片段的基礎上進行視頻片段的查詢，并且通過引入搜索范圍門限值來提高算法的速度，將全局搜索轉變為在門限區域內搜索，能夠有效地解決不同時間尺度的視頻相似性匹配問題。

具體來說，對兩個視頻片段A和B，假定其中分別包含M和N個子片段。可以首先計算A序列和B序列中任意兩個子片段對的相似性距離，即計算dist(i， j)（i=1，…，M；j=i，…，N），將得到一個M×N的差值矩陣D，矩陣D中第i行和第j列的元素記做D(i， j)=dist(i， j)。當|i-j|≤T時，計算查詢片段的第i個子片段與候選片段的第j個子片段的相似度距離。根據視頻內各個子片段之間的相關性關系，假設在兩條斜對角線之外的區域，認為查詢片段與候選片段沒有匹配的子片段，如圖6所示。相當于設計了一個搜索窗口，將當前查詢子片段與對應候選子片段相鄰幾個子片段作比較，計算相似性距離，不僅加快了算法的速度，還能夠有效解決不同時間尺度視頻間匹配問題。

D(i， j)=dist(i， j)if|i-j|≤T

∞if|i-j|＞T(1)

其中：dist(i， j)是子片段i與j之間的相似性距離；T的取值在第3章中給出。

在這個差值矩陣的基礎上，采用對稱算法通過循環計算差值來得到最優比對結果，如式(2)所示。

E(i， j)=D(i， j)+min(E(i-1， j)E(i-1， j-1)，E(i-1， j-2)) (2)

其中：矩陣E表示查詢片段和候選片段的極小化距離；E(i， j)表示查詢片段A的子片段i和候選片段B的子片段j之間的累加距離。E(i， j)的最小可能累加值同時在(i-1， j)，(i-1， j-1)，(i-1， j-2)三種不同可能中選擇。

基于改進的DTW的最優匹配算法的基本步驟如下：

a)計算兩組視頻對應子片段的相似度距離，得到兩序列的差值矩陣；

b)循環計算序列間的最短距離，得到累加距離和；

c)在可能的匹配結果中選擇最小值；

d)最后回溯得到路徑，驗證視頻是否匹配。

筆者通過檢測最小匹配值，即當計算得到的最終結果D(M，N)小于給定的閾值時，再用DTW算法反向跟蹤得到對應最終結果的匹配路徑，匹配路徑是一組子片段匹配對的序列。

3 實驗結果及分析

為了驗證算法的有效性，本文將視頻片段分別進行快進和慢放處理，得到內容一致但時間尺度不同的視頻片段，先用基于亮度排序的子片段分割算法進行子片段分割，得到如圖6所示的結果。圖中三行數據分別為原始視頻Vq（共343幀）、快進片段Vf（共230幀）、慢放片段Vs（共456幀）的子片段分割結果。

用Vq作為查詢樣例，分別用傳統的基于視覺相似性的片段檢索算法和本文提出的這種新的基于DTW的最優匹配算法在數據庫中進行檢索，得到圖7的查詢結果。其中圖7(a)是用傳統基于視覺相似性的片段檢索算法檢索查詢得到的樣例視頻Vq本身、快進片段Vf和慢放片段Vs，sim(Vq，Vf)=0783 5，sim(Vq，Vs)=0.784 7；(b)是采用基于DTW的最優匹配算法檢索得到的結果，搜索窗口長度T設為6，前兩行為檢索到的快進片段，sim(Vq，Vf)=0.811 8，其回溯路徑如圖8(a）所示，后兩行是檢索到的慢放片段，sim(Vq，Vs)=0836 1，其回溯路徑如圖8(b)所示。

從實驗結果可以看出，傳統的基于視覺相似性的片段檢索算法雖然能夠在一定程度上避免不同時間尺度視頻的匹配問題，但是得到的查詢結果中包含多個重復的子片段，不能達到最優匹配效果。而采用本文提出的基于DTW的最優匹配算法檢索得到的視頻片段與查詢樣例視頻相似度更高，可以在樣例視頻和待匹配視頻子片段中找到與其最相似的匹配對，使兩段視頻間的相似度值最大，達到最優匹配的目的。

4 結束語

本文針對不同時間尺度視頻間的相似性匹配問題，結合子片段的概念，先用基于亮度排序的子片段分割算法將視頻片段分割成保持時序關系的子片段，然后在子片段的基礎上進行視頻片段的相似性匹配。針對傳統的基于視覺相似性的視頻片段檢索算法的不足，本文提出了一種新的基于DTW的最優匹配算法，通過引入搜索范圍門限值來將全局搜索轉變為在門限區域內進行搜索，不僅提高了查詢速度而且還盡可能地保證了查詢精度，有效解決了不同時間尺度相似視頻片段的查詢問題。

參考文獻：

［1］

KASTURI R，JAIN R.Dynamic vision，computer vision:principles[M].Washington DC:IEEE Computer Society Press，1991:460480.

［2］LEE C F，CHANG C C.A breadth first oriented symbolic picture representation for spatial match retrieval[J].Journal of Systems and Software，2000，52(1):1123.

［3］TAN Y P，KULKARNI S R，RAMADGE P J.A framework for measuring video similarity and its application to video query by example[C]//Proc of IEEE International Conference on Image Processing.1999:10110.

［4］SHAN M K，LEE S Y.Contentbased video retrieval based on similarity of frame sequence[C]//Proc of MultiMedia Database Management Systems Workshop.1998:9097.

［5］PARK S，CHO J S，HYUN K H.Indexing technique for similarity matching in large video databases[C]//Proc of the SPIE Conference on Storage and Retrieval for Media Databases.2002.

［6］LIU F J，DONG D G，XUE X Y，et al.A fast video clip retrieval algorithm based on VAFile[C]//Proc of SPIE Electronic Imaging 2004:Storage and Retrieval for Media Database.2004:167176.

［7］CHEN L P，CHUA T S.A match and tiling approach to contentbased video retrieval[C]//Proc ofIEEE International Conference on Multimedia and Expo.2001:301304.

［8］LIAN N X，TAN Y P，CHAN K L.Efficient video retrieval using shot clustering and alignment[C]//Proc of the 4th International Conference on Information， Communications Signal Processing and the 4th PacificRim Conference on Multimedia.2003:18011805.

［9］MYERS C S，RABINER L R.A comparative study of several dynamic timewarping algorithms for connected word recognition[J].The Bell System Technical Journal，1981，60(7):13891409.