基于視頻片段的視頻檢索

胡振興，夏利民

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410075)

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

1 基于VA-Trie的視頻數(shù)據(jù)庫(kù)的組織

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

1.1 視頻子片段分割

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

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

(1)首先獲取圖像的RGB(Red, Green, Blue)顏色空間，再?gòu)腞GB顏色空間轉(zhuǎn)換成HSI顏色空間，轉(zhuǎn)換公式見(jiàn)文獻(xiàn)[9]；

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

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

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

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

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

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

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

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

1.2 用VA-Trie組織視頻數(shù)據(jù)庫(kù)

由于視頻流被分割成子片段，因此，視頻數(shù)據(jù)庫(kù)就表示成子片段的集合。接下來(lái)用高維索引結(jié)構(gòu)VA-Trie[10]來(lái)組織和管理這些子片段。VA-Trie分為 2層：上層是由VA-Trie的內(nèi)部節(jié)點(diǎn)組成的Trie層；下層是由葉子節(jié)點(diǎn)組成的VA層。葉子節(jié)點(diǎn)中保存著所有近似矢量數(shù)據(jù)，并以磁盤(pán)頁(yè)形式存儲(chǔ)。圖2所示為VA-Trie的結(jié)構(gòu)示意圖。

2 視頻片段的相似度度量

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

根據(jù)運(yùn)動(dòng)視頻相似性的特點(diǎn)，Chen等[14]提出一種新的相似度定義的方法，該方法是將視頻片段的相似度分成片段、子片段2個(gè)層次來(lái)考慮。相似度定義充分考慮了視頻片段對(duì)應(yīng)子片段之間的相似度，但是，沒(méi)有考慮視頻中相應(yīng)視頻片段的時(shí)序關(guān)系，本文作者對(duì)此進(jìn)行改進(jìn)，在相似度度量中加入時(shí)序因子，充分考慮利用視頻片段中子片段的時(shí)序關(guān)系來(lái)表達(dá)相似視頻片段之間的關(guān)系。

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

(1)密度分布為：

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

(2)緊密度分布為：

其中：m是在s中4連接都有像素點(diǎn)的像素點(diǎn)總數(shù)。

(3)離散度為：

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

圖2 VA-Trie的結(jié)構(gòu)示意圖Fig.2 Structure of VA-Trie

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

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

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

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

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

a和b是參數(shù)，設(shè)a=10和b=-5[14]。

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

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

3 視頻片段檢索

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

3.1 相似子片段查詢

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

3.2 相似視頻片段查詢

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)結(jié)果

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

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

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

4.2 性能比較

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

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

表2 查全率、準(zhǔn)確率和查詢時(shí)間比較Table 2 Comparison of recall, precision and query time

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

5 結(jié)論

(1)利用相鄰幀之間的HSI顏色信息特征來(lái)進(jìn)行視頻分割，有效地顯示出圖片中目標(biāo)的位置變化，對(duì)于運(yùn)動(dòng)的細(xì)節(jié)查詢非常有效。

(2)采用高維索引結(jié)構(gòu)VA-Trie組織視頻數(shù)據(jù)庫(kù)，有效克服普通高維索引結(jié)構(gòu)中存在的“維數(shù)災(zāi)難”問(wèn)題，提高了查詢效率。同時(shí)，采用VA-Trie的順序存儲(chǔ)方式使得大型視頻數(shù)據(jù)庫(kù)更新十分容易。

(3)對(duì)已有的相似度模型進(jìn)行了改進(jìn)，加入了時(shí)序因子，從視覺(jué)和時(shí)序關(guān)系2個(gè)方面定義視頻相似性，對(duì)運(yùn)動(dòng)視頻的查詢十分有效。

[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] 謝東, 吳敏. 基于范圍語(yǔ)義的非一致性數(shù)據(jù)庫(kù)聚集查詢[J].中南大學(xué)學(xué)報(bào): 自然科學(xué)版, 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] 顧波, 邱道尹, 梁祥州. 基于彩色轉(zhuǎn)換的水果分類系統(tǒng)設(shè)計(jì)[J]. 農(nóng)機(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] 董道國(guó), 劉振中, 薛向陽(yáng). VA-Trie: 一種用于近似k近鄰查詢的高維索引結(jié)構(gòu)[J]. 計(jì)算機(jī)研究與發(fā)展, 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] 趙亞琴, 周獻(xiàn)中, 何新. 利用等價(jià)關(guān)系理論進(jìn)行視頻片段檢索的方法[J]. 中國(guó)圖像圖形學(xué)報(bào), 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] 彭宇新, 董慶杰. 一種通過(guò)視頻片段進(jìn)行視頻檢索的方法[J].軟件學(xué)報(bào), 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] 張靜, 路紅, 薛向陽(yáng). 基于索引結(jié)構(gòu)的高效運(yùn)動(dòng)視頻檢索[J].計(jì)算機(jī)研究與發(fā)展, 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.