基于核矢量过滤的视频检索算法

摘要：视频检索是高维空间中的计算。针对高维计算量大的特点，提出了构造一个核矢量的算法，将高雏空间转换到低维空间，在低维空间逐维过滤不相似的数据集，缩小检索范围，提高检索速度。
关键词：核矢量子域过滤候选集

    为了有效地从视频媒体库中找到所需的信息，必须对视频信息进行有效的组织、索引，以提供快捷、方便的视觉检索。视频内容既包含与视频内容直接相关的视觉信息数据，也包括与视频不直接相关的数据(即内容无关的元数据)，如格式、作者名、日期和所有权等。其中，与视频内容直接相关的数据又分为两类：(1)内容相关的元数据，即与感觉因素相关的低层或中层特征的数据．如颜色、纹理、形状、空间联系和运动等；(2)描述与视觉信息所表示的含义相关的高层语义的内容描述元数据，即描述图像实体与客观实体的关系，如视觉符号和场景的时间、事件、感受和意图。
    由于与内容无关的数据不能有效地描述视频，而高层语义信息在直接理解上存在困难，因此目前主要利用视频内容的各种低、中层特征，或利用经过人工描述后量化的高层语义特征以及它们的组合构造描述视频的特征矢量。这样形成的特征矢量是高维矢量。在高维空间如何有效地建立索引，快速响应用户的检索要求是问题的关键。
    通常视频检索采用顺序扫描算法SSA(Sequent ScanAlgorithm)，但是当媒体库不断扩大时，影响了此算法的检索效率。因此常用树结构来构造高维索引，包括η参数优化树即η-树(η Parameter Optimal Tree)，高度平衡R-树(Height-balanced Tree)及其变种。分析表明，这些索引树结构在低维矢量空间是有效的，而当矢量空间超过一定的维数时，这些索引树结构比简单的顺序扫描还要差。
    本文提出一种示例视频检索的方法，首先根据每一类特征生成一个质心量，将多个质心量组合成一个核矢量，然后将模式集按核矢量的每一维过滤，生成一个较小候选集，在候选集内用SSA算法查找示例视频的相似近邻。

1 特征的提取
    建立索引结构首先要抽取特征，构造模式集，每一个模式由一个特征矢量描述。

1．1 中低层特征的选取
    在算法的实验系统中选择了颜色、纹理、形状等特征。颜色特征采用36色非均匀量化算法的HSV颜色模型。HSV模型能较好地反映人对色彩的感知和鉴别能力，比较适合基于色彩的相似比较。纹理特征采用粗糙度、对比度和方向性这三个值组成的分量来表示。形状特征主要通过矩来描述，计算速度快，比图像分割方法的鲁棒性好。

1.2 其他特征
    系统还可以进行扩展，如加入运动特征(同组人员正在寻求相关算法)及物体之间的空间关系。此外，还可以采用注释的形式形成高层语义特征，然后量化到系统中。

2 检索算法
2．1 生成核矢量
    生成核矢量的主要步骤描述如下。
     
2．2 生成算法的索引数据结构
    算法的主要思想可以描述如下。
    设模式集S中含有N个矢量，记为S={s1,s2，……sN}，模式si在F上的投影记为{SiF1,SiF2,……siFn}。
    将模式集在每个投影分量上划分成若干子域，并作如下定义：
    θmax为每个子域中允许的模式数。若某子域元素数多于此值，则分裂子域；θmin为每个子域中允许的模式数，若某子域元素数低于此值，合并相邻子域；Fimin为模式集在Fi上的值；Fimax为模式集在Fi上的值；ki为模式集在Fi上划分的子域数；niF1为模式集在Fi上投影的第i个子域的元素数。
    对模式集中的每个投影分量，寻找一组满足如下关系的值：

   
    算法实质上相当于把模式集按其在核矢量的每个投影分量进行过滤，除去一些与示例矢量不在同一个子域的模式，终形成一个候选集。这显然可以降低计算量。但是随着新模式的加入或删除，某些模式就要对原有子域的划分作出调整，即模式识别中常用的插入、分裂、删除以及合并过程。下面分别介绍这些算法。

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

    (1)计算SiFi所属的子域。

   
    (2)计算SiFi所插入的子域R1Fi的当前元素数niFi。
    (3)判断是否要分裂子域，如果niFi>θmax则执行分裂算法。

2．2．2 分裂
    当第i个子域的元素个数时，则要执行分裂算法。
    (1)对集合排序。
    (2)重新计算子域边界。

   

2．2．3 删除
    当从模式集中删除某个模式时。计算相应的RiFi中元素数niFi，判断是否要进行合并运算。如果niFi<θmin，则执行合并算法。

2．2．4 合并
   

2．3 检索过程
2．3．1 候选集的生成
    针对检索矢量在核矢量各分量上的过滤，对于每一模式在核矢量各维上的投影．若与检索矢量在同一子域中，将视为相似矢量归于候选集。这是一个迭代的过程，可以描述为：假设当前已进行到第i步，当前候选集为S={s1，s2，……sm}时，判断候选集在核矢量第i+1维上的投影是否与检索矢量在同一子域，若是则保留，否则从候选集中去除。

2．3．2 在候选集上运用SSA算法
    在上一步生成的候选集内根据相似度量函数Similarity(Si，Q)，针对阈值d，对于候选集中每一个模式，若Similarity(Si，Q）≤d，则Si属于终解集合。

3 评价
    实验系统采用VC6.0编程语言，SQL Server 2000为视频特征库，在Windows 2000 Server系统上测试，测试环境为CPUP4 2 400MHz，内存512MB。
    将此算法和R一树算法在相同的数据集上针对不同维数测试，两种算法的检索时间如图1所示。

    从图1可以看出，在低于50维时，R一树性能优于此算法，但当高于50维时，此算法计算时间的增长速度要低于R一树。
    针对由200例20类构成的视频库，分别对颜色、纹理、形状单类特征构成的视频特征矢量和三类特征的特征矢量组合起来作为视频特征矢量。从查全率和查准率方面对算法作分析，结果如表l所示。
    经过比较，该算法比SSA算法检索速度明显要快，但是单特征与组合特征的查准率与查全率均略低于SSA算法，这可以通过用户反馈来调整。
    算法的关键在于构造了一个较小的核矢量，简化了计算。但用它生成候选集时，只是排除不可能的模式，对模式包含的信息量造成的损失较小。而且在候选集中仍然采用相似性度量来确定终解。从表中可以看出算法还有待进一步改进，可
以引入相关反馈以提高查准率。