摘 要： 視頻檢索" title="視頻檢索">視頻檢索是高維空間中的計(jì)算。針對(duì)高維計(jì)算量大的特點(diǎn)，提出了構(gòu)造一個(gè)核矢量的算法，將高維空間轉(zhuǎn)換到低維空間，在低維空間逐維過(guò)濾不相似的數(shù)據(jù)集，縮小檢索范圍，提高檢索速度。
關(guān)鍵詞： 核矢量 子域 過(guò)濾 候選集
為了有效地從視頻媒體庫(kù)中找到所需的信息，必須對(duì)視頻信息進(jìn)行有效的組織、索引，以提供快捷、方便的視覺(jué)檢索。視頻內(nèi)容" title="視頻內(nèi)容">視頻內(nèi)容既包含與視頻內(nèi)容直接相關(guān)的視覺(jué)信息數(shù)據(jù)，也包括與視頻不直接相關(guān)的數(shù)據(jù)(即內(nèi)容無(wú)關(guān)的元數(shù)據(jù)" title="元數(shù)據(jù)">元數(shù)據(jù))，如格式、作者名、日期和所有權(quán)等。其中，與視頻內(nèi)容直接相關(guān)的數(shù)據(jù)又分為兩類：(1)內(nèi)容相關(guān)的元數(shù)據(jù)，即與感覺(jué)因素相關(guān)的低層或中層特征的數(shù)據(jù)，如顏色、紋理、形狀、空間聯(lián)系和運(yùn)動(dòng)等；(2)描述與視覺(jué)信息所表示的含義相關(guān)的高層語(yǔ)義的內(nèi)容描述元數(shù)據(jù)，即描述圖像實(shí)體與客觀實(shí)體的關(guān)系，如視覺(jué)符號(hào)和場(chǎng)景的時(shí)間、事件、感受和意圖。
由于與內(nèi)容無(wú)關(guān)的數(shù)據(jù)不能有效地描述視頻，而高層語(yǔ)義信息在直接理解上存在困難，因此目前主要利用視頻內(nèi)容的各種低、中層特征，或利用經(jīng)過(guò)人工描述后量化的高層語(yǔ)義特征以及它們的組合構(gòu)造描述視頻的特征矢量。這樣形成的特征矢量是高維矢量。在高維空間如何有效地建立索引，快速響應(yīng)用戶的檢索要求是問(wèn)題的關(guān)鍵。
通常視頻檢索采用順序掃描算法SSA(Sequent Scan Algorithm)[1]，但是當(dāng)媒體庫(kù)不斷擴(kuò)大時(shí)，影響了此算法的檢索效率。因此常用樹結(jié)構(gòu)來(lái)構(gòu)造高維索引，包括η參數(shù)優(yōu)化樹即η-樹(η Parameter Optimal Tree)[2]，高度平衡R-樹(Height-balanced Tree)[3]及其變種。分析表明，這些索引樹結(jié)構(gòu)在低維矢量空間是有效的，而當(dāng)矢量空間超過(guò)一定的維數(shù)時(shí)，這些索引樹結(jié)構(gòu)比簡(jiǎn)單的順序掃描還要差。
本文提出一種示例視頻檢索的方法，首先根據(jù)每一類特征生成一個(gè)質(zhì)心量，將多個(gè)質(zhì)心量組合成一個(gè)核矢量，然后將模式集按核矢量的每一維過(guò)濾，生成一個(gè)較小候選集，在候選集內(nèi)用SSA算法查找示例視頻的相似近鄰。
1 特征的提取
建立索引結(jié)構(gòu)首先要抽取特征，構(gòu)造模式集，每一個(gè)模式由一個(gè)特征矢量描述。
1.1 中低層特征的選取
在算法的實(shí)驗(yàn)系統(tǒng)中選擇了顏色、紋理、形狀等特征。顏色特征采用36色非均勻量化算法[4]的HSV顏色模型。HSV模型能較好地反映人對(duì)色彩的感知和鑒別能力，比較適合基于色彩的相似比較。紋理特征采用粗糙度、對(duì)比度和方向性[5]這三個(gè)值組成的分量來(lái)表示。形狀特征主要通過(guò)矩[6]來(lái)描述，計(jì)算速度快，比圖像分割方法的魯棒性好。
1.2 其他特征
系統(tǒng)還可以進(jìn)行擴(kuò)展，如加入運(yùn)動(dòng)特征(同組人員正在尋求相關(guān)算法)及物體之間的空間關(guān)系。此外，還可以采用注釋的形式形成高層語(yǔ)義特征，然后量化到系統(tǒng)中。
2 檢索算法
2.1 生成核矢量
生成核矢量的主要步驟描述如下。
2.2 生成算法的索引數(shù)據(jù)結(jié)構(gòu)
算法的主要思想可以描述如下。
對(duì)模式集中的每個(gè)投影分量，尋找一組滿足如下關(guān)系的值：
算法實(shí)質(zhì)上相當(dāng)于把模式集按其在核矢量的每個(gè)投影分量進(jìn)行過(guò)濾，除去一些與示例矢量不在同一個(gè)子域的模式，最終形成一個(gè)候選集。這顯然可以降低計(jì)算量。但是隨著新模式的加入或刪除，某些模式就要對(duì)原有子域的劃分作出調(diào)整，即模式識(shí)別中常用的插入、分裂、刪除以及合并過(guò)程。下面分別介紹這些算法。
2.2.1 插入
以新模式si在Fi上投影分量的插入為例，算法的步驟如下：
2.2.2 分裂
2.2.3 刪除
2.2.4 合并
2.3 檢索過(guò)程
2.3.1 候選集的生成
針對(duì)檢索矢量在核矢量各分量上的過(guò)濾，對(duì)于每一模式在核矢量各維上的投影，若與檢索矢量在同一子域中，將視為相似矢量歸于候選集。這是一個(gè)迭代的過(guò)程，可以描述為：假設(shè)當(dāng)前已進(jìn)行到第i步，當(dāng)前候選集為S={S1，S2，……Sm}時(shí)，判斷候選集在核矢量第i+1維上的投影是否與檢索矢量在同一子域，若是則保留，否則從候選集中去除。
2.3.2 在候選集上運(yùn)用SSA算法
在上一步生成的候選集內(nèi)根據(jù)相似度量函數(shù)Similarity(Si，Q)，針對(duì)閾值d，對(duì)于候選集中每一個(gè)模式，若Similarity(Si，Q)≤d，則Si屬于最終解集合。
3 評(píng)價(jià)
實(shí)驗(yàn)系統(tǒng)采用VC6.0編程語(yǔ)言" title="編程語(yǔ)言">編程語(yǔ)言，SQL Server 2000為視頻特征庫(kù)，在Windows 2000 Server系統(tǒng)上測(cè)試，測(cè)試環(huán)境" title="測(cè)試環(huán)境">測(cè)試環(huán)境為CPUP4 2 400MHz，內(nèi)存512MB。
將此算法和R-樹算法在相同的數(shù)據(jù)集上針對(duì)不同維數(shù)測(cè)試，兩種算法的檢索時(shí)間如圖1所示。
從圖1可以看出，在低于50維時(shí)，R-樹性能優(yōu)于此算法，但當(dāng)高于50維時(shí)，此算法計(jì)算時(shí)間的增長(zhǎng)速度要低于R-樹。
針對(duì)由200例20類構(gòu)成的視頻庫(kù)，分別對(duì)顏色、紋理、形狀單類特征構(gòu)成的視頻特征矢量和三類特征的特征矢量組合起來(lái)作為視頻特征矢量。從查全率和查準(zhǔn)率方面對(duì)算法作分析，結(jié)果如表1所示。
經(jīng)過(guò)比較，該算法比SSA算法檢索速度明顯要快，但是單特征與組合特征的查準(zhǔn)率與查全率均略低于SSA算法，這可以通過(guò)用戶反饋來(lái)調(diào)整。
算法的關(guān)鍵在于構(gòu)造了一個(gè)較小的核矢量，簡(jiǎn)化了計(jì)算。但用它生成候選集時(shí)，只是排除不可能的模式，對(duì)模式包含的信息量造成的損失較小。而且在候選集中仍然采用相似性度量來(lái)確定最終解。從表中可以看出算法還有待進(jìn)一步改進(jìn)，可以引入相關(guān)反饋以提高查準(zhǔn)率。
參考文獻(xiàn)
1 Wu Y，Zhuang Y T，Pan Y H.Video similarity measurement.Journal of Computer-aided Design & Computer Graphics，2001；13(3)：284～288
2 Feng Y C，Cao G，Cao Z S.A multidimensional index structure for fast similatiry retrieval.Journal of Software，2002；13(8)：1678～1685
3 Guttman A.R-Trees：A dynamic index structure for spatial searching.In：Proceedings of the ACM SIGMOD international conference on management of data，1984：47～54
4 Zhang L.A CBIR method based on color-spatial reature.IEEE regin10 annual international conference 1999，CheJu，Korea，1999：166～169
5 谷口慶治.數(shù)字圖像處理.北京：科學(xué)出版社，2002：95～96