一种基于体育比赛视频的相似视频片段检索方法

摘要

本发明涉及一种基于体育比赛视频的相似视频片段检索方法，通过离线部分对视频库中的所有视频进行预处理形成视频特征库，在线部分对查询片段进行视频结构化分析以及特征提取后在视频特征库中进行两轮不同粒度的检索。第一轮粗粒度的检索确定候选视频集，第二轮细粒度的检索确定相似片段在视频对象中的精确位置。并且，对所有的视频特征采用K-D tree进行组织以加速查询过程。最后综合考虑视觉、时序、干扰因子对相似度的影响，对相似片段进行相似度进行计算并排序。

说明书

技术领域

本发明涉及一种相似视频片段检索方法，属于计算机视觉技术领域。

背景技术

相似视频检索是基于内容视频检索（CBVR）领域近年来兴起的研究 热点。由于其应用广泛能为视频复制检测、视频语义标注等提供关键技术， 成为众多研究机构和学者关注的焦点。其中，对体育比赛视频进行自动检 索则具有很高的实用价值，研究成果既可以被专业人士用于对体育比赛中 的选手的技术动作与战术进行快速分析，从而提高体育训练效率和训练水 平，也可以被体育爱好者们用于对感兴趣的视频片段进行更加准确、方便、 快捷的检索，从而提高人们观赏体育比赛的便捷程度。相似视频检索是通 过选取合适的底层视觉特征，在视频的特征空间进行视频的相似度度量， 并在视频数据库中进行快速、准确的检索，从而得到检索结果。

目前在实际的应用中都是基于单轮检索，直接对视频库中的所有视频 进行相似度计算，但直接检索存在着一个很严重的问题：由于视频包含文 本、声音以及图像是一种复杂的没有结构的流数据，其特征维数高、蕴含 的数据量大、计算复杂，若对视频库进行直接处理必然造成检索时间过长， 难以满足实时查询的要求。并且针对视频特征一般维数较高、数据量大计 算复杂等问题，目前的相似片段检索方法中对于视频的特征的组织往往采 用一些常用的降维方法（如VA-File）避免“维度灾难”这一严峻问题。常 用的降维方法能在一定程度上降低时间复杂度，减少计算时间，但降维方 法是基于近似向量的原理会导致检索精度降低，并且一些常用的降维方法 都有其适用范围，而视频特征具有随机性难以满足要求。对于体育比赛视 频而言，尤其是某类型的体育比赛，其场景较为固定、简单，场地以及背 景信息变化较小，因此不必为体育视频提取高维的特征进行检索，只需提 取具有代表性的特征即可，例如颜色特征、亮度特征等。

发明内容

本发明的目的是提供一种基于体育比赛视频的相似片段检索方法。该 方法利用离线部分已经形成视频特征库，在线部分对查询片段进行视频结 构化分析以及特征提取后在视频特征库中的视频进行两轮不同粒度的检 索，并采用K-D tree组织视频特征得到相似片段。最后综合考虑视觉、时 序、干扰因子对相似度的影响，对相似片段进行相似度进行计算并排序。 该方法能有效地减少计算量、提高检索效率，实现了快速、准确的基于体 育比赛视频的相似片段检索。

为实现上述目的，本发明采用下述的技术方案。其特征在于包括以下 步骤：

步骤一：对视频库中的所有视频进行预处理，分别采用基于颜色相 似性的子片段分割方法和基于亮度差异性的子片段分割方法将每个视频 分割为若干视频子片段，对每个视频子片段提取其中的关键帧，对每一关 键帧提取颜色和亮度特征，组成视频特征库；

步骤二：对于步骤一中得到的所有特征采用K-D tree结构进行存储， 每一个特征都作为K-D tree中的一个节点，特征值大于该层分辨器值的特 征作为右子树，特征值小于等于该层分辨器值的特视作为左子树，视频特 征库中的所有特征构建成一棵K-D tree；

步骤三：对待查询视频片段分别采用基于颜色相似性的子片段分割方 法和基于亮度差异性的子片段分割方法法将其分割为若干视频子片段，对 每个视频子片段提取其中的关键帧，对每一关键帧提取颜色和亮度特征， 作为查询条件；

步骤四：首先，通过将查询条件与视频特征库中的特征进行对比找到 待查询视频片段中所有视频子片段的相似子片段集，对所得到的所有相似 子片段集求交集，并由所求交集确定候选视频集；其次，对候选视频集中 所有视频采用滑动子片段窗口进行相似片段的精确定位，采用如下公式 （1）计算滑动子片段窗口中的视频片段与待查询视频片段的匹配度m_qw， 匹配度小于给定阈值时，将所述窗口以一个视频子片段为步长向前移动； 直到匹配度大于所述给定阈值，此时所述窗口的前端为相似片段的起始位 置；

$m_{\mathrm{qw}}=\frac{{\mathrm{NV}}_{n_q}}{\mathrm{len}}---\left(1\right)$

其中表示待查询视频片段和滑动子片段窗口中一一对应的视频子片 段数目，len为滑动子片段窗口中视频子片段的总数目；

步骤五：根据步骤四中得到相似片段，按照如下相似度计算公式（2） 计算待查询视频片段与相似片段的相似度S(V_q,V_s)；

S(V_q,V_s)＝ω_v×f_v+ω_o×f_o+ω_i×f_i            (2)

其中f_v、f_o、f_i分别为视觉因子、顺序因子及干扰因子，ω_v、ω₀、ω_i分别 为视觉因子、顺序因子及干扰因子的权重值；

步骤六：根据上述计算得到的相似度，确定最终的相似视频。

本发明所提供的基于体育比赛视频的相似片段检索方法可以在保证检 索精度的同时有效地减少计算量、降低查询时间。有关的测试结果表明， 本方法对于体育比赛视频的相似片段检索具有较好的结果，其检索时间满 足实时的需求。

附图说明

图1基于体育比赛视频的相似片段检索方法的框架图。

图2基于体育比赛视频的相似片段检索方法的流程图。

图3基于体育比赛视频的相似片段检索方法效果图。

具体实施方式

前已述及，本发明通过离线部分形成视频特征库，在线部分对查询片 段进行视频结构化分析以及特征提取后在视频特征库中的视频进行两轮 不同力粒度的检索，并采用K-D tree组织视频特征得到相似片段。最后综 合考虑视觉、时序、干扰因子对相似度的影响，对相似片段进行相似度进 行计算并排序。

下面结合附图说明本发明的实现方式，图3中明确表示了本发明的过 程。首先，对查询视频进行分析；其次，相似片段的查询得到最终结果。

需要注意的是，以下仅是示例性的列举了本发明的一种实施方式：

步骤一：查询视频分析

由于视频是多媒体中比较复杂的一种媒体，它包含了声音、图像、文 本，是在时间上连续的一系列帧的集合，是一种没有结构的流数据，如果 不对其进行有效的组织管理就无法完成快速且高效的视频检索。本发明中 采用视频-子片段-关键帧的三层结构对视频片段进行表示。在有效的表示 视频片段后必须为其提取适合的底层特征进行后续的计算。本发明中，由 于针对特定类型的视频-体育比赛视频，我们仅选取颜色或亮度信息作为底 层特征，其具有简单、快速的特点，并且具有较好的鲁棒性和泛化性能。

步骤一的一种示例性实施步骤如下：

(1)子片段的分割

本方法中采用了两种不同的子片段分割方法：基于颜色相似性的子片 段分割方法与基于亮度差异的子片段分割算法。

基于颜色相似性的子片段分割的主要思想是计算视频流中的每一帧的 HSV颜色空间的颜色直方图作为该帧的特征向量，遍历视频流中的每一帧 与相邻帧之间的颜色差异，若颜色差异大于给定阈值，说明存在一个子片 段的分界点。这种方法是基于视频子片段内部颜色差异小，而不同的子片 段之间的颜色差异大，利用颜色的差异来区分子片段之间视觉特征的差 异，符合人的主观要求。某一类体育比赛视频一般颜色比较简单，不同的 颜色特征在一定程度上能对应不同的视频语义。因此，选取颜色特征来分 割视频是十分可行的。该方法将HSV空间量化成144个bin值，其中H 量化为16个区间、S和V都量化3个区间，并统计其颜色直方图后将其 归一化作为该视频帧的特征向量。帧差用公式(1)来计算。

$D=1-\frac{{\Sigma }_i\min (H_1\left(i\right),H_2\left(j\right))}{{\Sigma }_i\min \left(H_2\left(j\right)\right)}---\left(1\right)$

其中，H₁,H₂分别表示两帧基于HSV颜色空间的颜色直方图，利用其直方 图归一化的交表示其相似度，阈值dist的选取可以根据实验得到。

基于亮度差异的子片段分割方法采用包含空间信息的亮度排序方法 对视频流进行分割，将一个视频片段中具有相同亮度排序的相邻帧划分到 一个子片段中。该方法选取Lab颜色空间中L，即亮度信息作为视频帧的 视觉特征，将视频中的每一帧分为四个子块，统计每个子块的亮度值的总 和，并对这四个总和进行排序，若两帧的亮度值排序相同则将这两个视频 帧划入同一个子片段中，若不同则不划入同一个视频子片段中。

(2)关键帧提取

现阶段关键帧的选取原则“宁多勿少”同时，在代表特征不具体的情 况下，一般以去掉重复（或冗余）帧为原则。基于这一基本原则，不同的 提取算法可以选取不同的原则，建立适合自身情况的判定标准，有时针对 不同的视频事件，还可以选择不同的判定标准。就本方法而言，子片段不 同于以往的镜头，往往在子片段内部视觉内容变化较小，为了提高检索的 效率，减少计算复杂度，我们采取特定帧法来选取关键帧，选取每个子片 段的第一帧作为该子片段的关键帧。

(3)视觉特征提取

在进行完视频子片段分割完成后选取每个子片段的第一帧作为该子片 段的关键帧，视频片段以视频-子片段-关键帧结构表示。本方法中针对两 种不同的子片段分割方法-基于颜色差异子片段分割和基于亮度排序子片 段分割采用相同的特征作为子片段代表-关键帧的特征向量。对于基于颜色 相似性的子片段分割方法和基于亮度差异的子片段分割方法均采用关键 帧的颜色直方图作为一个视频子片段的特征向量。视频片段被分割成C个 子片段C＝{C₁,C₂,...,C_c}，其对应的HSV颜色直方图为 Hist＝{H₁,H₂,...,H_c}，本文采用非均匀量化，将每一个关键帧帧表示为 16×3×3共144Bin的HSV颜色直方图，其中H为16Bin，S和V分别为 3Bin。

(4)视频特征库的组织

由于视频片段被分割成若干子片段，并且以视频子片段作为视频查询 的单位，因此视频数据库就表示成了子片段的集合C＝{C₁,C₂,...,C_c}。提取 子片段关键帧的颜色直方图作为视频特征，就形成了大量特征向量组成的 视频特征数据库。由于子片段数量较多，其关键帧的数量也多，因此视频 特征数据库也将是规模巨大的，为了提高查询效率，就需要利用索引结构 对其进行组织和管理。

最常见的方法是采用高维索引结构VA-File来组织视频特征库。VA-file （Vector-Approximation file）是用于高维向量数据K-NN的索引方法，它 通过减少向量的存储空间来达到减少查询开销的目的，能够有效克服高维 索引结构中存在的“维数灾难”问题。本方法只针对体育比赛视频进行处 理，由于其场景较为单一，可以考虑只采用维数较低的简单特征即可。通 过大量的实验表明，采取维度较低的颜色特征或亮度特征就能得到较好的 检索结果。因此，面临的问题不是“维数灾难”问题而是子片段较多造成 关键帧较多，引起特征向量的数量较多。针对上述问题，本方法中采用 K-D tree对视频特征进行组织。

K-D tree（K-Dimension tree）又称为多维二进制搜索树，是对数据点在k维 空间在k维空间中划分的一种数据结构，其中k表示搜索空间的维数。K-D  tree树可以用来存储对象信息，其中每个对象包括k维，一般被应用于文 件的储存，数据库查找，网络的查找等领域。K-D tree成功地将二叉搜索 树推广到多维数据检索，本论文中用K-D tree来组织视频的特征向量，K 维空间中的一个点代表一个关键帧（即一个视频子片段）的特征向量。不 同于二叉搜索树，K-D tree的每个节点用K个关键字来做索引，其中每个 关键字都表示K维空间的一个维度值。

一棵K-D tree，或为空树，或为满足一下特征的二叉树：

（1）树中的每个节点P拥有K维向量V＝[V₁,V₂,…,V_k]，记为V(P)；

（2）树的每一层都有一个分辨器(discrimination)，1≤d1scrimination≤K， 表示节点P处应表示哪个分量，用discrimination(P)表示；

（3）树节点P指向左孩子和右孩子的指针分别用Left(P)和Right(p)表示。

（4）对于树中任意节点P，令i=discrimination(P)，都满足以下特征：对 于P左子树中的任意节点L，满足V_i(L)＜V_i(P)；对于P右子树中的 任意节点R，满足V_i(R)≥V_i(P)；同一层次的discrimination值相等， 第一层的discrimination值discrimination(1)＝1，第i层的 discrimination值discrimination(i)＝i，第K层的discrimination值 discrimination(K)＝K，第K+1层discrimination(K+1)＝1，如此循 环。

其具体做法是将特征库中的所有颜色特征根据K-D tree的构造方法构 建成为一棵K-D tree。K-D tree的每一个节点是代表一个关键帧的特征， 后续的查询计算中根据K-D tree检索算法进行快速地检索。

步骤二：相似片段的查询

本步骤主要是在视频特征库中进行两轮不同粒度的检索。第一轮粗粒 度的检索确定候选视频集，第二轮细粒度的检索确定相似片段在视频对象 中的精确位置。最后综合考虑视觉、时序、干扰因子对相似度的影响，对 相似片段进行相似度进行计算并排序。

步骤二的一个示例性实施步骤如下：

(1)子片段的相似度计算

为了提高检索的速度，本方法为每个视频子片段提取唯一的关键帧。 于是，视频子片段的相似度可以转化为关键帧的相似度，其具体定义为公 式(2)。

$\mathrm{CSim}(C_i,C_j)=\mathrm{FSim}(f_i,f_j)=\frac{{\Sigma }_{\mathrm{bin}}\min (H_i\left(\mathrm{bin}\right),H_j\left(\mathrm{bin}\right))}{{\Sigma }_{\mathrm{bin}}\min \left(H_j\left(\mathrm{bin}\right)\right)}---\left(2\right)$

其中，H_i、H_j分别为子片段C_i、C_j的关键帧f_i、f_j所对应的基于HSV颜色空 间的144bin的颜色直方图。

(2)候选视频集的确定

考虑到视频数据量大，处理要花费较长的时间，检索时间难以满足检 索的需求。本方法中首先对数据库中的视频进行筛选，去除不符合要求的 视频对象。如果查询片段的每个子片段都能在视频库中的某个视频对象中 查找到与其相似的子片段，则它们之间存在相似。基于这个原理筛选出不 存在相似视频子片段的视频对象，构造候选视频集。其具体做法是如下所 示。

输入：一个查询视频对象的子片段序列V_q＝{C_q1,C_q2,…,C_qn}，视频数 据库中的所有视频对象的子片段集Clip_i＝{C_d1,C_d2,…,C_dm},i＝1,…,n。

输出：候选视频集V_c={C_cl，C_c2，..．，C_cn]。

（1）初始化，输入查询视频对象的子片段序列V_q以及视频数据库中 的所有视频对象的子片段集 Clip_i={C_dl，C_d2，…，C_dm]，i=1，…，n。

（2）遍历查询视频对象的子片段序列，查找其在视频数据库中的所 有视频对象的子片段集的相似视频，构造相似子片段集 SClip_i={S_d1，S_d2，…，S_dm]，i=1，...，n。

（3）为相似子片段集中的每一个S_di，查找其对应的视频。于是，一 个相似子片段集SClip_i可以得到一个视频集S_ci。

（4）对查询视频对象所有子片段对应的S_ci求他们的交集，交集记为 候选视频集V_c={C_c1，C_c2，...，C_cn]。

候选视频集的确定过程计算简单，时间复杂度低，不会增加较多的额 外的开销，并且候选视频集的构造过程中能去除很大一部分与查询视频无 关的视频集，能减少处理得数据量，提高检索的效率。

(3)相似片段的精确定位

本方法中采用滑动子片段窗口进行相似片的精确定位。首先，定义匹 配度。其次计算滑动子片段窗口中的片段与查询片段的匹配度，并根据匹 配度的高低确定相似片段的位置。其具体做法如下述所示。

为了确定查询视频片段和滑动子片段窗中的视频片段的匹配度，过滤 伪相似的片段，从而得到与查询片段真正相似的片段，首先先介绍查询视 频片段的相似子片段集的定义。

相似子片段集。假定查询视频片段为V_q，当前滑动子片段窗中的子片 段集合为V_w，窗口的大小为len，对于查询片段V_q中的任一子片段C_qi定义 C_qi的相似子片段集为 S_i＝{C_wj∣CSim(C_qi,C_wj)＞a},i＝1,…,n_q,j＝n,n+1,n+2,…,n+ len-1， 则不相似子片段集为V_w-S_i。其中CSim(C_qi,C_wj)两个视频子片段的相似 度，α为视频子片段相似度的临界值，n为滑动窗口中第一个子片段的序号。

按照相似子片段集合中包含子片段数目从少到多的顺序排列相似子片 段集，如果存在多个相似子片段集包含的子片段数目相同，则可将序号小 的子片段的相似子片段集排在前面。相似子片段集排序后记为OS_i。

假设NV_i表示当前已经一一对应匹配的子片段数目，集合OI_i表示排在相 似子片段集OS_i前面的所有相似子片段集与OS_i的并集，则OS_i用公式(3)和 公式(4)计算。

其中|OS_i|表示OI_i所含子片段数目，n_q为查询视频中子片段的数目。

设集合NS_i表示已经被查询子片段匹配的相似子片段集合，即NS_i中的 子片段已经被匹配，不能再与后续的查询子片段匹配，则NS_i的公式计算为 公式(5)。

因此，NV_i的计算式为公式(6)。

其中，n_q为查询视频片段中的子片段数目。当τ_i＞0时，表明集合OI_i中仍 然有剩余的可匹配子片段，OS_i ∪ NS_i-1≠NS_i-1表明相似子片段集OS_i中有 可匹配的相似子片段与当前查询子片段匹配。τ_i＝0表明相似子片段集OI_i中的所有相似子片段已经与当前查询子片段之前的查询子片段匹配，不能 再与当前查询子片段匹配。

匹配度的计算。设查询片段为V_q，子片段数为n_q，当前滑动子片段窗 中的子片段集合为V_w，窗口的大小为len，对于的相似子片段集为S_i，

则视频片段V_q和V_w的匹配度的计算公式如公式(7)所示。

$m_{\mathrm{qw}}=\frac{{\mathrm{NV}}_{n_q}}{\mathrm{len}}---\left(7\right)$

其中表示查询视频和滑动窗口中一一对应的视频子片段数目。

相似片段精度定位的具体做法如下述所示。

输入：一个查询视频对象的子片段序列V_q={C_q1,C_q2,...,C_qn},候选视 频集V_c＝{C_c1,C_c2,...,C_cn}。

输出：n_s个相似视频片段，即相似片段集。

（1）初始化，输入查询视频子片段序列V_q，以及候选视频集子片段 序列V_c，设定滑动窗口的大小len＝1.5×n_q。

（2）如果候选视频集子片段序列为空，算法停止，否则转第（3）步。

（3）对于候选视频集子片段序列V_c中的每一个子片段C_ci，如果C_ci至 少与查询视频V_q中的一个子片段相似，则把C_ci记为M_cj，得到 一组相似子片段的集合MClip＝{M_c1,M_c2,…,M_cn}。

（4）计算匹配度m_qw。如果相似子片段集合MClip为空，算法停止， 否则在当前相似子片段M_cj,1≤j≤n的位置使用滑动子片段 窗口；计算查询视频片段V_q与滑动子片段窗中片段V_w的匹配 度m_qw，如果m_qw≥β转第（5）步，否则j＝j+1，转第（4） 步。

（5）以一个子片段的增量移动滑动子片段窗口，计算每个子片段窗 中视频片段V_w与查询视频片段V_q的匹配度m_qw。

（6）确定相似视频。滑动子片段窗口后移窗口长度个单位后，选取 匹配度大于等于β局部最大值中匹配度最大值所对应的序号 就是相似片段的起始位置，从此位置处开始取与滑动子片段窗 口子片段个数相等的后续若干个子片段作为相似片段。

j＝j+1，转至（4）。

其中，β的作用是选择使用滑动子片段窗口的子片段，只有当相似子片段 对应的子片段窗中片段与查询片段的匹配度大于β时才继续进行匹配度计 算，否则忽略该相似子片段M_cj，β的值可根据实验设定。

(4)相似度的排序

本方法中相似度的计算主要考虑包括视觉因子、时序因子以及干扰因 子对相似度的影响。

视觉因子的计算如下述所示。用MaxC_qs(i)表示查询片段V_q的某一个子 片段C_qi，与相似片段Vs中所有子片段的相似度最大值，V_q的子片段个数 为n_q，则其计算公式为(8)。

${\mathrm{MaxC}}_{\mathrm{qs}}\left(i\right)=\underset{1\le i\le n_q}{\max }(C_{\mathrm{qi}},C_{\mathrm{sj}})---\left(8\right)$

其中，C_sj为相似视频的某一子片段。

同理，用MaxC_sq(i)表示相似片段Vs的某一个子片段C_si，与查询片段V_q中所有子片段的相似度最大值，V_s的子片段个数为n_s，则其计算公式为(9)。

${\mathrm{MaxC}}_{\mathrm{sq}}\left(i\right)=\underset{1\le i\le n_s}{\max }(C_{\mathrm{si}},C_{\mathrm{qj}})---\left(9\right)$

其中，C_qj为查询片段V_q的某一子片段。

视觉因子定义如公式(10)所示。

$f_v=\frac{1}{2}(\overline{{\mathrm{MaxC}}_{\mathrm{qs}}}+\overline{{\mathrm{MaxC}}_{\mathrm{sq}}})---\left(10\right)$

顺序因子定义式为(11)所示。

$f_o=\frac{\mathrm{LCS}(i,j)}{n_q}---\left(11\right)$

其中n_q为查询视频的子片段个数，LCS(i,j)为查询片段与相似片段V_s的最 长公共子序列的长度。

干扰因子计算式为公式(12)。

$f_i=1-\frac{N_d}{n_q+n_s}---\left(12\right)$

其中n_q、n_s分别表示查询片段V_q与相似片段V_s中子片段的数量，N_d表示查 询片段V_q与相似片段V_s中找不到对应的相似子片段的子片段总个数。

综合考虑视觉因子、时序因子以及干扰因子对相似度的影响，定义查 询片段V_q与它的相似片段V_s的总体相似程度计算式为(13)。

S(V_q,V_s)＝ω_v×f_v+ω_o×f_o+ω_i×f_i(ω_v+ω_o+ω_i＝1)(13)

其中ω_v、ω_o、ω_i分别为视觉因子、顺序因子及干扰因子的权重值，该值可 以通过实验得出。本方法通过利用公式(13)，计算候选相似片段集中所有 候选视频片段与查询视频片段的总体相似度，并按照相似度高低得到最终 结果。

以上公开的仅为本发明的具体实例，根据本发明提供的思想，本领域 的技术人员能思及的变化，都应落入本发明的保护范围内。