摘要：視頻檢索是高維空間中的計(jì)算。針對(duì)高維計(jì)算量大的特點(diǎn)，提出了構(gòu)造一個(gè)核矢量的算法，將高雛空間轉(zhuǎn)換到低維空間，在低維空間逐維過(guò)濾不相似的數(shù)據(jù)集，縮小檢索范圍，提高檢索速度。
關(guān)鍵詞：核矢量子域過(guò)濾候選集

    為了有效地從視頻媒體庫(kù)中找到所需的信息，必須對(duì)視頻信息進(jìn)行有效的組織、索引，以提供快捷、方便的視覺(jué)檢索。視頻內(nèi)容既包含與視頻內(nèi)容直接相關(guān)的視覺(jué)信息數(shù)據(jù)，也包括與視頻不直接相關(guān)的數(shù)據(jù)(即內(nèi)容無(wú)關(guān)的元數(shù)據(jù))，如格式、作者名、日期和所有權(quán)等。其中，與視頻內(nèi)容直接相關(guān)的數(shù)據(jù)又分為兩類(lèi)：(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)用戶(hù)的檢索要求是問(wèn)題的關(guān)鍵。
    通常視頻檢索采用順序掃描算法SSA(Sequent ScanAlgorithm)，但是當(dāng)媒體庫(kù)不斷擴(kuò)大時(shí)，影響了此算法的檢索效率。因此常用樹(shù)結(jié)構(gòu)來(lái)構(gòu)造高維索引，包括η參數(shù)優(yōu)化樹(shù)即η-樹(shù)(η Parameter Optimal Tree)，高度平衡R-樹(shù)(Height-balanced Tree)及其變種。分析表明，這些索引樹(shù)結(jié)構(gòu)在低維矢量空間是有效的，而當(dāng)矢量空間超過(guò)一定的維數(shù)時(shí)，這些索引樹(shù)結(jié)構(gòu)比簡(jiǎn)單的順序掃描還要差。
    本文提出一種示例視頻檢索的方法，首先根據(jù)每一類(lèi)特征生成一個(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色非均勻量化算法的HSV顏色模型。HSV模型能較好地反映人對(duì)色彩的感知和鑒別能力，比較適合基于色彩的相似比較。紋理特征采用粗糙度、對(duì)比度和方向性這三個(gè)值組成的分量來(lái)表示。形狀特征主要通過(guò)矩來(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)
    算法的主要思想可以描述如下。
    設(shè)模式集S中含有N個(gè)矢量，記為S={s1,s2，……sN}，模式si在F上的投影記為{SiF1,SiF2,……siFn}。
    將模式集在每個(gè)投影分量上劃分成若干子域，并作如下定義：
    θmax為每個(gè)子域中允許的模式數(shù)。若某子域元素?cái)?shù)多于此值，則分裂子域；θmin為每個(gè)子域中允許的模式數(shù)，若某子域元素?cái)?shù)低于此值，合并相鄰子域；Fimin為模式集在Fi上的值；Fimax為模式集在Fi上的值；ki為模式集在Fi上劃分的子域數(shù)；niF1為模式集在Fi上投影的第i個(gè)子域的元素?cái)?shù)。
    對(duì)模式集中的每個(gè)投影分量，尋找一組滿(mǎn)足如下關(guān)系的值：

   
    算法實(shí)質(zhì)上相當(dāng)于把模式集按其在核矢量的每個(gè)投影分量進(jìn)行過(guò)濾，除去一些與示例矢量不在同一個(gè)子域的模式，終形成一個(gè)候選集。這顯然可以降低計(jì)算量。但是隨著新模式的加入或刪除，某些模式就要對(duì)原有子域的劃分作出調(diào)整，即模式識(shí)別中常用的插入、分裂、刪除以及合并過(guò)程。下面分別介紹這些算法。

2．2．1 插入
    以新模式si在Fi上投影分量的插入為例，算法的步驟如下：

    (1)計(jì)算SiFi所屬的子域。

   
    (2)計(jì)算SiFi所插入的子域R1Fi的當(dāng)前元素?cái)?shù)niFi。
    (3)判斷是否要分裂子域，如果niFi>θmax則執(zhí)行分裂算法。

2．2．2 分裂
    當(dāng)?shù)趇個(gè)子域的元素個(gè)數(shù)時(shí)，則要執(zhí)行分裂算法。
    (1)對(duì)集合排序。
    (2)重新計(jì)算子域邊界。

   

2．2．3 刪除
    當(dāng)從模式集中刪除某個(gè)模式時(shí)。計(jì)算相應(yīng)的RiFi中元素?cái)?shù)niFi，判斷是否要進(jìn)行合并運(yùn)算。如果niFi<θmin，則執(zhí)行合并算法。

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ǔ)言，SQL Server 2000為視頻特征庫(kù)，在Windows 2000 Server系統(tǒng)上測(cè)試，測(cè)試環(huán)境為CPUP4 2 400MHz，內(nèi)存512MB。
    將此算法和R一樹(shù)算法在相同的數(shù)據(jù)集上針對(duì)不同維數(shù)測(cè)試，兩種算法的檢索時(shí)間如圖1所示。

    從圖1可以看出，在低于50維時(shí)，R一樹(shù)性能優(yōu)于此算法，但當(dāng)高于50維時(shí)，此算法計(jì)算時(shí)間的增長(zhǎng)速度要低于R一樹(shù)。
    針對(duì)由200例20類(lèi)構(gòu)成的視頻庫(kù)，分別對(duì)顏色、紋理、形狀單類(lèi)特征構(gòu)成的視頻特征矢量和三類(lèi)特征的特征矢量組合起來(lái)作為視頻特征矢量。從查全率和查準(zhǔn)率方面對(duì)算法作分析，結(jié)果如表l所示。
    經(jīng)過(guò)比較，該算法比SSA算法檢索速度明顯要快，但是單特征與組合特征的查準(zhǔn)率與查全率均略低于SSA算法，這可以通過(guò)用戶(hù)反饋來(lái)調(diào)整。
    算法的關(guān)鍵在于構(gòu)造了一個(gè)較小的核矢量，簡(jiǎn)化了計(jì)算。但用它生成候選集時(shí)，只是排除不可能的模式，對(duì)模式包含的信息量造成的損失較小。而且在候選集中仍然采用相似性度量來(lái)確定終解。從表中可以看出算法還有待進(jìn)一步改進(jìn)，可
以引入相關(guān)反饋以提高查準(zhǔn)率。