基于視頻片段的視頻檢索

胡振興，夏利民

(中南大學 信息科學與工程學院，湖南 長沙，410075)

視頻是在時間上連續的一系列幀的集合，是集圖像、聲音和文本為一體的綜合性媒體信息。隨著數字化視頻數據量的迅速增加，傳統耗時的瀏覽方式已遠不能滿足人們對視頻內容訪問和查詢的需求。人們越來越希望能在海量視頻庫中快速找到自己感興趣的視頻片段，因此，為視頻建立有效的索引結構，實現快速有效的查詢已成為視頻研究領域的一個重要課題。經過多年的研究，在視頻片段檢索方面產生了眾多算法，這些算法一般從視頻片段相似度度量方面進行研究[1-4]，而在視頻數據庫建模和構造方面研究較少。鏡頭或片段的查詢仍局限于對視頻數據庫的順序掃描上，由于視頻數據庫的規模巨大，這種順序掃描的查詢方法勢必導致查詢效率低。Zhuang等[5]在視頻數據庫中引入了ViSig(video signature)的概念，用多種方法對原始視頻數據進行映射，并用映射后得到的規模較小的ViSig來表示視頻數據，以達到提高查詢速度的目的，但是他們在評價視頻片段相似度時沒有考慮視頻片段中各幀之間的時間順序，影響了查詢精度。Ngo等[6]提出了一種介于鏡頭和幀之間的數據表示形式，并以此為基本單位進行相似視頻片段的查詢。雖然該方法通過聚類在一定程度上提高了查詢效率，但其查詢精度受k-means聚類效果的影響很大，并且當候選視頻片段中包含過多子片段時，相似度計算將占用大量查詢時間，嚴重影響查詢效率。本文作者提出了一種基于視頻片段的視頻檢索方法。該方法利用相鄰幀之間的HSI的顏色信息特征將視頻流分割成子片段，再提取子片段特征并建立索引結構，通過高維索引結構VA-Trie 組織視頻數據庫，采用改進的基于空間和紋理特征的相似度模型來度量視頻片段之間的相似性，最后通過基于限定性滑動窗口的高效視頻檢索算法進行視頻片段檢索。

1 基于VA-Trie的視頻數據庫的組織

由于視頻數據是在時間上連續的幀的集合并且是非結構化的，因此很難對其進行快速有效的檢索。本文作者提出的視頻檢索方法首先將原始視頻流分割成內容上相似的子片段，然后采用高維索引結構VA-Trie來組織這些子片段。

1.1 視頻子片段分割

現有的視頻片段查詢主要包含2種查詢方式：以鏡頭為查詢單位[7]和以幀為查詢單位。由于鏡頭運動和物體運動造成鏡頭中包含過多的內容變化，若以鏡頭為查詢單位，則會較大地降低查詢精度；而以幀為查詢單位，雖然提高了查詢精度，但由于視頻片段中幀的數目過多會造成相似度的計算量過大，因而會降低查詢效率。為此，在提出的視頻片段檢索方法中，將視頻分割成子片段，在子片段的基礎上對視頻片段進行查詢。子片段是介于幀和鏡頭之間的有序幀序列，子片段內的各幀在內容上十分相似而且保持了其在視頻數據庫[8]中的時序關系。

本文作者提出一種基于HSI顏色信息的方法對視頻流進行分割。該方法取HSI顏色信息中的色調H、飽和度S和亮度信息I。作為分割的特征。分割方法如下：

(1)首先獲取圖像的RGB(Red, Green, Blue)顏色空間，再從RGB顏色空間轉換成HSI顏色空間，轉換公式見文獻[9]；

(2)將視頻中的每一幀分割成大小為16×16的子區域；

(3)分別計算每一幀小區域中所有像素點的H,S和I的和，假設視頻流共有n幀，由于每一個小區域中的像素點總數不一定相等，因此，用M表示所有小區域中像素點總數最小值，則計算第i幀顏色信息值的方法如下：

其中，1≤i≤n; 1≤j≤p; 1≤k≤m;p為每幀圖像小區域的塊數；Hi,j，Si,j和Ii,j分別表示第i幀中第j個小區域的H，S和I分量的和；Hi,j,k，Si,j,k和Ii,j,k分別表示第i幀中第j個小區域的第k個像素點的H，S和I分量。

(4)分別計算這些得到的H,S和I的平均值，計算方法如下：

其中：Hi,j,av,Si,j,av和Ii,j,av(1≤j≤256)分別表示第i幀中第j個小區域的H,S和I分量的平均值。

(5)將第i幀中這 3p個平均值相加，計算方法如下：

(6)計算每一幀與下一相鄰幀的幀間差，若此幀間差比預先設定的閾值a小，則說明這2幀之間差異不大，將其分配到同一個子片段中，反之，則不屬于同一個子片段。

圖1給出了1個基于HSI顏色信息的視頻分割例子，閾值a=100(閾值a是在實驗中根據HSI特性來確定的，可由用戶改動)，3個子片段是從1段連續的視頻流中分割出來的。從圖1可以清晰地分辨出羽毛球運動員接球時姿態的變化。另外，這種基于HSI的顏色信息的方法可以有效地去除一些噪音如全局閃光燈對視頻分割的影響。而且，對于重放和不同幀率的問題，本文作者提出的分割方法也十分有效，它可以將相鄰的表示相似內容的多幀分割成1個子片段，因此，能夠有效地檢索不同長度的視頻。

1.2 用VA-Trie組織視頻數據庫

由于視頻流被分割成子片段，因此，視頻數據庫就表示成子片段的集合。接下來用高維索引結構VA-Trie[10]來組織和管理這些子片段。VA-Trie分為 2層：上層是由VA-Trie的內部節點組成的Trie層；下層是由葉子節點組成的VA層。葉子節點中保存著所有近似矢量數據，并以磁盤頁形式存儲。圖2所示為VA-Trie的結構示意圖。

2 視頻片段的相似度度量

在視頻片段檢索[11-12]中，相似度定義是非常重要的部分，直接影響查詢的準確率。盡管已經提出了一些相似度模型[13]，但是由于相似視頻定義復雜，所以，仍未產生一種公認的較好的相似度度量。

根據運動視頻相似性的特點，Chen等[14]提出一種新的相似度定義的方法，該方法是將視頻片段的相似度分成片段、子片段2個層次來考慮。相似度定義充分考慮了視頻片段對應子片段之間的相似度，但是，沒有考慮視頻中相應視頻片段的時序關系，本文作者對此進行改進，在相似度度量中加入時序因子，充分考慮利用視頻片段中子片段的時序關系來表達相似視頻片段之間的關系。

假設1個視頻子片段中有1個顏色對象Ci的像素點集s={(x1,y1), …, (xn,yn)}，進行如下定義。

(1)密度分布為：

其中：k是視頻子片段的像素總數。

(2)緊密度分布為：

其中：m是在s中4連接都有像素點的像素點總數。

(3)離散度為：

圖1 子片段分割示例Fig.1 Example of segment

圖2 VA-Trie的結構示意圖Fig.2 Structure of VA-Trie

為了定義第4個特征，將視頻子片段分割成相同大小為16×16[14]的p塊。若這些塊包含一些s的子集，則認為這個塊是活躍的。假設在視頻子片段中活躍塊的數目為q，定義活躍塊的比率為：

視頻子片段的空間特征被計算之后，分別取這些值的平均值。用表示視頻子片段中的1個顏色對象Ci的平均特征值。1個視頻片段中的2個顏色對象Ci和Cj的空間分布的差異定義為：

使用 Canny邊緣檢測器對子片段中大小為 16×16[14]的p塊進行邊緣檢測，若塊中的邊緣點數目大于設定的閾值(設置為30[14])，則認為這塊是有紋理的。然后，計算每一個視頻子片段的紋理塊的比率和在 1個片段中的平均值。2個子片段中的紋理相似性由 2個平均值的最小值確定。

令A，B分別表示子片段S1和S2中的所有顏色對象，給定顏色對象u∈A對應在B中滿足的相似性顏色對象v∈ε，其中，表示u和v在HSV(Hue, Saturation, Value)顏色空間中的歐氏距離；ε為閾值(設置為3)。因此，稱(u,v)為1個相似性顏色對。設，子片段S1和S2的平均直方圖分別為則子片段S1和S2之間的相似性為：

其中：k為子片段的像素總數；t1和t2分別為子片段S1和S2的紋理塊的平均比率；wt和W為權重函數，權重函數W為Sigmoid函數，

a和b是參數，設a=10和b=-5[14]。

給定 2個視頻片段G1={S11,S12, …,S1m}和G2={S21,S22, …,S2n}，它們分別包含m個和n個子片段。則視頻片段G1和G2之間的相似度計算式為：

其中：Sim(S1i,S2j)表示視頻片段(S1i,S2j)中第i幀和(S1i,S2j)中第j幀的相似度，充分考慮子片段之間的視覺相似性；δ為歸一化參數，在實驗中，δ=0.6Lq(Lq為查詢片段的長度)[15]；用于降低位置上不對應的子片段的相似度權重，然后取匹配子片段的相似度值的平均值為視頻片段的相似度，這樣，就保證了視頻片段在視頻流中的時序順序。

3 視頻片段檢索

視頻片段檢索算法主要分成2個部分：相似子片段查詢和相似視頻片段查詢。

3.1 相似子片段查詢

首先，針對給定的待查視頻片段，采用子片段分割算法把它分割成m個子片段，每個子片段用子片段內各幀的HSV顏色直方圖的平均值表示。然后，在已經建好的視頻索引結構VA-Trie上進行k近鄰查詢。由于不是每個子片段都有k個相似子片段，為了進一步提高查詢精度，設置一個相似度閾值來濾除相似度值較低的子片段，形成近似子片段文件。

3.2 相似視頻片段查詢

在得到查詢片段的相似子片段之后，接下來就是構造候選的相似視頻片段并計算相似度，得到最終的查詢結果。采用限定性滑動窗口[15]方法構造候選視頻片段，它與普通的滑動窗口不同，滑動窗口每次滑動的距離由下一個相似子片段的位置決定。滑動窗口的長度為待查視頻片段長度的函數，即a×Lq(Lq為待查視頻片段的長度，實驗中a為2.0)。限定性滑動窗口每次滑動到下一個相似子片段上就取出滑動窗口中的內容作為候選視頻片段。采用這種方法構造候選視頻片段不但可以保證找到所有當前相似度度量值比較高的視頻片段，而且由于不必掃描視頻數據庫所有的子片段，因而能提高查詢速度。

相似視頻片段的查詢包含2步：查詢和精化。在查詢階段，主要是構造候選視頻片段，計算候選視頻片段與待查視頻片段的相似度，得到相似度最大的k個視頻片段作為候選相似視頻片段。為進一步提高查詢精度，加入精化步驟，算法主要包含2部分：一是去除相似視頻片段尾部不屬于相似子片段的子片段并重新計算相似度；二是對于包含相同子片段的相似視頻只保留相似度最大的作為查詢結果。

4 實驗與分析

4.1 實驗結果

為了驗證算法的有效性，在配置 Windows XP，P4-2.8 G CPU，512 M RAM的PC機上對約200 min(300 456幀)的運動視頻數據庫進行實驗。該視頻數據庫囊括了羽毛球、足球、籃球、排球、體操、游泳、跳水和網球等項目共11段運動視頻，能夠較好地驗證所提出的算法對運動視頻檢測的有效性。由于相似度閾值與視頻類型的關系十分密切，因此很難給所有不同類型的視頻設定統一的相似度閾值。為了避免相似度閾值的定義對查詢結果產生不利的影響，在提出的算法中，無論是子片段的查詢還是相似視頻片段的查詢均采用k近鄰查詢。經過反復實驗設置k值如表1所示。實驗中的查詢片段是從視頻數據庫中提取的，包含羽毛球、體操、網球和籃球各一個視頻片段。實驗結果如表1所示。從表1可以看出：采用提出的視頻檢索方法可以得到平均查全率為 94%，準確率為85%，而查詢時間平均為6.865 s。

實驗中，取k=80，羽毛球的部分查詢結果如圖3所示，其中：序列1、序列2和序列3與查詢片段的相似度依次降低。由于作者提出的相似度度量充分考慮了視頻片段之間的視覺相似性和子片段的時序關系，因此，查詢結果與人的主觀感覺較為符合。另外，從圖3也可以看出：查詢結果可以很好地表現出運動細節的相似性，查詢的結果中序列1即為查詢后的片段，也就是說序列1跟查詢片段的相似度最高，序列 2和序列 3的視頻片段在運動細節上都與查詢片段極為相似，幾乎為相同的打球動作。實驗中采用的相似度度量不僅考慮了視頻片段可視特征的相似性，而且考慮了子片段之間的時序關系，因而查詢結果比較符合人的主觀判斷，相似度值越大視頻片段的相似程度也越高。

表1 相似視頻片段檢索結果Table 1 Result of similar video clip retrieval

4.2 性能比較

為了充分驗證算法的有效性，作者按照文獻[3]和文獻[6]中的方法，并采用相同的實驗數據進行對比實驗。實驗從查全率、準確率和查詢效率3個方面對3個算法的性能進行比較，實驗結果如表2所示。本文作者提出的方法得到了平均94%的查全率和85%的準確率，與文獻[3]中提出的方法相比，查全率提高了2%，準確率提高了29%；與文獻[6]提出的方法相比，所提出的方法查全率提高了19%，準確率提高了23%。另外，實驗還從查詢效率方面對以上3個算法進行比較，實驗結果如表2所示。從表2可知：所提出的算法的查詢效率遠高于文獻[3]和文獻[6]中算法的查詢效率。

圖3 羽毛球的視頻片段查詢部分結果Fig.3 Badminton query clip and query results

表2 查全率、準確率和查詢時間比較Table 2 Comparison of recall, precision and query time

本文作者所提出的算法主要從數據壓縮和優化查詢2個方面提高了查詢效率。在視頻數據庫組織方面，視頻數據通過2步進行壓縮。首先，將視頻流分割成子片段，并且用子片段中所有幀的平均顏色直方圖描述每一個子片段。由于子片段的數目遠少于幀的數目，因此，視頻數據被壓縮成一個較小的數據集合。然后，在視頻片段查詢階段，通過采用限定性滑動窗口構造候選項集的方法減少了需要訪問的子片段的數目，因而提高了查詢效率。

5 結論

(1)利用相鄰幀之間的HSI顏色信息特征來進行視頻分割，有效地顯示出圖片中目標的位置變化，對于運動的細節查詢非常有效。

(2)采用高維索引結構VA-Trie組織視頻數據庫，有效克服普通高維索引結構中存在的“維數災難”問題，提高了查詢效率。同時，采用VA-Trie的順序存儲方式使得大型視頻數據庫更新十分容易。

(3)對已有的相似度模型進行了改進，加入了時序因子，從視覺和時序關系2個方面定義視頻相似性，對運動視頻的查詢十分有效。

[1] Lin T, Zhang H J, Feng J F, et al. Shot content analysis for video retrieval applications[J]. Journal of Software, 2002, 13(8):1577-1585.

[2] Zhao L, Qi W, Li Z Q, et al. Content-based retrieval of video shot using the improved neatest feature line method[J]. Journal of Software, 2002, 13(4): 586-590.

[3] Ngo C W, Pong T C, Zhang H J. On clustering and retrieval of video shots through temporal slices analysis[J]. IEEE Transactions on Multimedia, 2002, 4(4): 446-459.

[4] Jain A K, Vailaya A, Wei X. Query by video clip[J]. ACM Multimedia Systems, 1999, 7(5): 369-384.

[5] Zhuang Y T, Liu X M, Wu Y, et al. A new approach to retrieve video by example video clip[J]. Chinese Journal of Computers,2000, 23(3): 300-305.

[6] Ngo C W, Pong T C, Chin R T. Video partitioning by temporal slice coherency[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2001, 11(8): 941-953.

[7] Hanjalic A, Lagendijk R L, Biemond J. Automated high-level movie segmentation for advanced video-retrieval systems[J].IEEE Transactions on Circuits and Systems for Video Technology, 1999, 9(4): 580-588.

[8] 謝東, 吳敏. 基于范圍語義的非一致性數據庫聚集查詢[J].中南大學學報: 自然科學版, 2008, 39(4): 810-815.XIE Dong, WU Min. Aggregation queries based on range semantics in inconsistent databases[J]. Journal of Central South University: Science and Technology, 2008, 39(4): 810-815.

[9] 顧波, 邱道尹, 梁祥州. 基于彩色轉換的水果分類系統設計[J]. 農機化研究, 2007, 5(5): 105-107.GU Bo, QIU Dao-yin, LIANG Xiang-zhou. The fruit system base on the color image transformation[J]. Farm Machinery Research, 2007, 5(5): 105-107.

[10] 董道國, 劉振中, 薛向陽. VA-Trie: 一種用于近似k近鄰查詢的高維索引結構[J]. 計算機研究與發展, 2005, 42(12):2213-2218.DONG Dao-guo, LIU Zhen-zhong, XUE Xiang-yang. VA-Trie:A new and efficient high dimensional index structure for approximateknearest neighbor query[J]. Journal of Computer Research and Development, 2005, 42(12): 2213-2218.

[11] 趙亞琴, 周獻中, 何新. 利用等價關系理論進行視頻片段檢索的方法[J]. 中國圖像圖形學報, 2007, 12(1): 127-134.ZHAO Ya-qin, ZHOU Xian-zhong, HE Xin. An efficient method for video clip retrieval using equivalence relation theory[J].Journal of Image and Graphics, 2007, 12(1): 127-134.

[12] 彭宇新, 董慶杰. 一種通過視頻片段進行視頻檢索的方法[J].軟件學報, 2003, 14(8): 1409-1417.PENG Yu-xin, DONG Qing-jie. An approach for video retrieval by video clip[J]. Journal of Software, 2003, 14(8): 1409-1417.

[13] Cheung S S, Zakhor A. Efficient video similarity measurement with video signature[J]. IEEE Trans on Circuits and Systems for Video Technology, 2003, 13(1): 59-74.

[14] CHEN Liang-hua, CHIN Kuo-hao, LIAO Hong-yuan.An integrated approach to video retrieval[C]//Proc 19th Australasian Database Conference(ADC 2008). Wollongong: Australian Comuter Society, Inc., 2008: 49-56.

[15] 張靜, 路紅, 薛向陽. 基于索引結構的高效運動視頻檢索[J].計算機研究與發展, 2006, 43(11): 1953-1958.ZHANG Jing, LU Hong, XUE Xiang-yang. Efficient sports video retrieval based on index structure[J]. Journal of Computer Research and Development, 2006, 43(11): 1953-1958.