基于视频片段的视频检索

胡振兴，夏利民

 (中南大学 信息科学与工程学院，湖南 长沙，410075)

摘　要：为提高视频检索的查询效率，提出一种基于视频片段的视频检索方法。该方法利用相邻帧之间的HIS(Hue, Saturation, Intensity)颜色信息特征将视频流分割成子片段，并采用高维索引结构Vector-Approximation Trie (VA-Trie)来组织视频子片段，然后，利用空间和纹理特征定义视频片段的相似度模型，在此基础上采用基于限定性滑动窗口的高效视频检索算法进行视频片段检索。研究结果表明：与其他检索方法相比，该方法能有效地提高视频检索的查全率和查询率，适合用于运动视频检索。

关键词：视频片段检索；高维索引结构；k近邻查询；相似度度量；空间和纹理特征

中图分类号：TP391          文献标志码：A         文章编号：1672-7207(2010)03-1009-06

Video retrieval based on video clip

HU Zhen-xing, XIA Li-min

 (School of Information Science and Engineering, Central South University, Changsha 410075, China)

Abstract: A video retrieval method based on video clip was presented to enhance the retrieval efficiency. The video stream was segmented into segments by HSI (Hue, Saturation, Intensity) color information between neighboring frames, and the high-dimensional index structure Vector-Approximation Trie (VA-Trie) was adopted to organize the segments. The new similarity model was defined using spatial and texture features, which can fully take into account the temporal order among video segments. Furthermore, the new query algorithm was used for video retrieval based on restricted sliding window to improve the retrieval accuracy. Experimental results indicate that the proposed approach can improve the recall ratio and precision ratio effectively, and suits the retrieval of sports videos.

Key words: video clip retrieval; high-dimensional index structure; k-nearest neighbor query; similarity measure; spatial and texture features

视频是在时间上连续的一系列帧的集合，是集图像、声音和文本为一体的综合性媒体信息。随着数字化视频数据量的迅速增加，传统耗时的浏览方式已远不能满足人们对视频内容访问和查询的需求。人们越来越希望能在海量视频库中快速找到自己感兴趣的视频片段，因此，为视频建立有效的索引结构，实现快速有效的查询已成为视频研究领域的一个重要课题。经过多年的研究，在视频片段检索方面产生了众多算法，这些算法一般从视频片段相似度度量方面进行研究^[1-4]，而在视频数据库建模和构造方面研究较少。镜头或片段的查询仍局限于对视频数据库的顺序扫描上，由于视频数据库的规模巨大，这种顺序扫描的查询方法势必导致查询效率低。Zhuang等^[5]在视频数据库中引入了ViSig(video signature)的概念，用多种方法对原始视频数据进行映射，并用映射后得到的规模较小的ViSig来表示视频数据，以达到提高查询速度的目的，但是他们在评价视频片段相似度时没有考虑视频片段中各帧之间的时间顺序，影响了查询精度。Ngo等^[6]提出了一种介于镜头和帧之间的数据表示形式，并以此为基本单位进行相似视频片段的查询。虽然该方法通过聚类在一定程度上提高了查询效率，但其查询精度受k-means聚类效果的影响很大，并且当候选视频片段中包含过多子片段时，相似度计算将占用大量查询时间，严重影响查询效率。本文作者提出了一种基于视频片段的视频检索方法。该方法利用相邻帧之间的HSI的颜色信息特征将视频流分割成子片段，再提取子片段特征并建立索引结构，通过高维索引结构VA-Trie 组织视频数据库，采用改进的基于空间和纹理特征的相似度模型来度量视频片段之间的相似性，最后通过基于限定性滑动窗口的高效视频检索算法进行视频片段检索。

1  基于VA-Trie的视频数据库的组织

由于视频数据是在时间上连续的帧的集合并且是非结构化的，因此很难对其进行快速有效的检索。本文作者提出的视频检索方法首先将原始视频流分割成内容上相似的子片段，然后采用高维索引结构VA-Trie来组织这些子片段。

1.1  视频子片段分割

现有的视频片段查询主要包含2种查询方式：以镜头为查询单位^[7]和以帧为查询单位。由于镜头运动和物体运动造成镜头中包含过多的内容变化，若以镜头为查询单位，则会较大地降低查询精度；而以帧为查询单位，虽然提高了查询精度，但由于视频片段中帧的数目过多会造成相似度的计算量过大，因而会降低查询效率。为此，在提出的视频片段检索方法中，将视频分割成子片段，在子片段的基础上对视频片段进行查询。子片段是介于帧和镜头之间的有序帧序列，子片段内的各帧在内容上十分相似而且保持了其在视频数据库^[8]中的时序关系。

本文作者提出一种基于HSI颜色信息的方法对视频流进行分割。该方法取HSI颜色信息中的色调H、饱和度S和亮度信息I。作为分割的特征。分割方法如下：

(1) 首先获取图像的RGB(Red, Green, Blue)颜色空间，再从RGB颜色空间转换成HSI颜色空间，转换公式见文献[9]；

(2) 将视频中的每一帧分割成大小为16×16的子区域；

(3) 分别计算每一帧小区域中所有像素点的H, S和I的和，假设视频流共有n帧，由于每一个小区域中的像素点总数不一定相等，因此，用M表示所有小区域中像素点总数最小值，则计算第i帧颜色信息值的方法如下：

其中，1≤i≤n; 1≤j≤p; 1≤k≤m; p为每帧图像小区域的块数；H_i,j，S_{i, j}和I_{i, j}分别表示第i帧中第j个小区域的H，S和I分量的和；H_{i, j­, k}，S_{i, j, k}和I_{i, j, k}分别表示第i帧中第j个小区域的第k个像素点的H，S和I分量。

(4) 分别计算这些得到的H, S和I的平均值，计算方法如下：

其中：H_{i, j, av}, S_{i, j, av}和I_{i, j, av}(1≤j≤256)分别表示第i帧中第j个小区域的H, S和I分量的平均值。

(5) 将第i帧中这3p个平均值相加，计算方法   如下：

(6) 计算每一帧与下一相邻帧的帧间差，若此帧间差比预先设定的阈值a小，则说明这2帧之间差异不大，将其分配到同一个子片段中，反之，则不属于同一个子片段。

图1给出了1个基于HSI颜色信息的视频分割例子，阈值a=100(阈值a是在实验中根据HSI特性来确定的，可由用户改动)，3个子片段是从1段连续的视频流中分割出来的。从图1可以清晰地分辨出羽毛球运动员接球时姿态的变化。另外，这种基于HSI的颜色信息的方法可以有效地去除一些噪音如全局闪光灯对视频分割的影响。而且，对于重放和不同帧率的问题，本文作者提出的分割方法也十分有效，它可以将相邻的表示相似内容的多帧分割成1个子片段，因此，能够有效地检索不同长度的视频。

1.2  用VA-Trie组织视频数据库

由于视频流被分割成子片段，因此，视频数据库就表示成子片段的集合。接下来用高维索引结构VA-Trie^[10]来组织和管理这些子片段。VA-Trie分为2层：上层是由VA-Trie的内部节点组成的Trie层；下层是由叶子节点组成的VA层。叶子节点中保存着所有近似矢量数据，并以磁盘页形式存储。图2所示为VA-Trie的结构示意图。

2  视频片段的相似度度量

在视频片段检索^[11-12]中，相似度定义是非常重要的部分，直接影响查询的准确率。尽管已经提出了一些相似度模型^[13]，但是由于相似视频定义复杂，所以，仍未产生一种公认的较好的相似度度量。

根据运动视频相似性的特点，Chen等^[14]提出一种新的相似度定义的方法，该方法是将视频片段的相似度分成片段、子片段2个层次来考虑。相似度定义充分考虑了视频片段对应子片段之间的相似度，但是，没有考虑视频中相应视频片段的时序关系，本文作者对此进行改进，在相似度度量中加入时序因子，充分考虑利用视频片段中子片段的时序关系来表达相似视频片段之间的关系。

假设1个视频子片段中有1个颜色对象C_i的像素点集s={(x₁, y₁), …, (x_n, y_n)}，进行如下定义。

(1) 密度分布为：

 (2) 紧密度分布为：

 (3) 离散度为：

图1  子片段分割示例

Fig.1  Example of segment

图2  VA-Trie的结构示意图

Fig.2  Structure of VA-Trie

为了定义第4个特征，将视频子片段分割成相同大小为16×16^[14]的p块。若这些块包含一些s的子集，则认为这个块是活跃的。假设在视频子片段中活跃块的数目为q，定义活跃块的比率为：

视频子片段的空间特征被计算之后，分别取这些值的平均值。用，，和表示视频子片段中的1个颜色对象C_i的平均特征值。1个视频片段中的2个颜色对象C_i和C_j的空间分布的差异定义为：

使用Canny边缘检测器对子片段中大小为16×16^[14]的p块进行边缘检测，若块中的边缘点数目大于设定的阈值(设置为30^[14])，则认为这块是有纹理的。然后，计算每一个视频子片段的纹理块的比率和在1个片段中的平均值。2个子片段中的纹理相似性由2个平均值的最小值确定。

令A，B分别表示子片段S₁和S₂中的所有颜色对象，给定颜色对象对应在B中满足＜ε的相似性颜色对象，其中，表示u和v在HSV(Hue, Saturation, Value)颜色空间中的欧氏距离；ε为阈值(设置为3)。因此，称(u, v)为1个相似性颜色对。设，子片段S₁和S₂的平均直方图分别为和，则子片段S₁和S₂之间的相似性为：

a和b是参数，设a=10和b=-5 ^[14]。

给定2个视频片段G₁={S₁₁, S₁₂, …, S_1m}和G₂={S₂₁, S₂₂, …, S_2n}，它们分别包含m个和n个子片段。则视频片段G₁和G₂之间的相似度计算式为：

然后取匹配子片段的相似度值的平均值为视频片段的相似度，这样，就保证了视频片段在视频流中的时序顺序。

3　视频片段检索

视频片段检索算法主要分成2个部分：相似子片段查询和相似视频片段查询。

3.1  相似子片段查询

首先，针对给定的待查视频片段，采用子片段分割算法把它分割成m个子片段，每个子片段用子片段内各帧的HSV颜色直方图的平均值表示。然后，在已经建好的视频索引结构VA-Trie上进行k近邻查询。由于不是每个子片段都有k个相似子片段，为了进一步提高查询精度，设置一个相似度阈值来滤除相似度值较低的子片段，形成近似子片段文件。

3.2  相似视频片段查询

在得到查询片段的相似子片段之后，接下来就是构造候选的相似视频片段并计算相似度，得到最终的查询结果。采用限定性滑动窗口^[15]方法构造候选视频片段，它与普通的滑动窗口不同，滑动窗口每次滑动的距离由下一个相似子片段的位置决定。滑动窗口的长度为待查视频片段长度的函数，即a×L_q(L_q为待查视频片段的长度，实验中a为2.0)。限定性滑动窗口每次滑动到下一个相似子片段上就取出滑动窗口中的内容作为候选视频片段。采用这种方法构造候选视频片段不但可以保证找到所有当前相似度度量值比较高的视频片段，而且由于不必扫描视频数据库所有的子片段，因而能提高查询速度。

相似视频片段的查询包含2步：查询和精化。在查询阶段，主要是构造候选视频片段，计算候选视频片段与待查视频片段的相似度，得到相似度最大的k个视频片段作为候选相似视频片段。为进一步提高查询精度，加入精化步骤，算法主要包含2部分：一是去除相似视频片段尾部不属于相似子片段的子片段并重新计算相似度；二是对于包含相同子片段的相似视频只保留相似度最大的作为查询结果。

4　实验与分析

4.1  实验结果

为了验证算法的有效性，在配置Windows XP，P4-2.8 G CPU，512 M RAM的PC机上对约200 min    (300 456帧)的运动视频数据库进行实验。该视频数据库囊括了羽毛球、足球、篮球、排球、体操、游泳、跳水和网球等项目共11段运动视频，能够较好地验证所提出的算法对运动视频检测的有效性。由于相似度阈值与视频类型的关系十分密切，因此很难给所有不同类型的视频设定统一的相似度阈值。为了避免相似度阈值的定义对查询结果产生不利的影响，在提出的算法中，无论是子片段的查询还是相似视频片段的查询均采用k近邻查询。经过反复实验设置k值如表1所示。实验中的查询片段是从视频数据库中提取的，包含羽毛球、体操、网球和篮球各一个视频片段。实验结果如表1所示。从表1可以看出：采用提出的视频检索方法可以得到平均查全率为94%，准确率为85%，而查询时间平均为6.865 s。

实验中，取k=80，羽毛球的部分查询结果如图3所示，其中：序列1、序列2和序列3与查询片段的相似度依次降低。由于作者提出的相似度度量充分考虑了视频片段之间的视觉相似性和子片段的时序关系，因此，查询结果与人的主观感觉较为符合。另外，从图3也可以看出：查询结果可以很好地表现出运动细节的相似性，查询的结果中序列1即为查询后的片段，也就是说序列1跟查询片段的相似度最高，序列 2和序列3的视频片段在运动细节上都与查询片段极为相似，几乎为相同的打球动作。实验中采用的相似度度量不仅考虑了视频片段可视特征的相似性，而且考虑了子片段之间的时序关系，因而查询结果比较符合人的主观判断，相似度值越大视频片段的相似程度也越高。

表1  相似视频片段检索结果

Table 1　Result of similar video clip retrieval

4.2　性能比较

为了充分验证算法的有效性，作者按照文献[3]和文献[6]中的方法，并采用相同的实验数据进行对比实验。实验从查全率、准确率和查询效率3个方面对3个算法的性能进行比较，实验结果如表2所示。本文作者提出的方法得到了平均94%的查全率和85%的准确率，与文献[3]中提出的方法相比，查全率提高了2%，准确率提高了29%；与文献[6]提出的方法相比，所提出的方法查全率提高了19%，准确率提高了23%。另外，实验还从查询效率方面对以上3个算法进行比较，实验结果如表2所示。从表2可知：所提出的算法的查询效率远高于文献[3]和文献[6]中算法的查询效率。

图3  羽毛球的视频片段查询部分结果

Fig.3  Badminton query clip and query results

表2  查全率、准确率和查询时间比较

Table 2  Comparison of recall, precision and query time

本文作者所提出的算法主要从数据压缩和优化查询2个方面提高了查询效率。在视频数据库组织方面，视频数据通过2步进行压缩。首先，将视频流分割成子片段，并且用子片段中所有帧的平均颜色直方图描述每一个子片段。由于子片段的数目远少于帧的数目，因此，视频数据被压缩成一个较小的数据集合。然后，在视频片段查询阶段，通过采用限定性滑动窗口构造候选项集的方法减少了需要访问的子片段的数目，因而提高了查询效率。

5　结论

(1) 利用相邻帧之间的HSI颜色信息特征来进行视频分割，有效地显示出图片中目标的位置变化，对于运动的细节查询非常有效。

(2) 采用高维索引结构VA-Trie组织视频数据库，有效克服普通高维索引结构中存在的“维数灾难”问题，提高了查询效率。同时，采用VA-Trie的顺序存储方式使得大型视频数据库更新十分容易。

(3) 对已有的相似度模型进行了改进，加入了时序因子，从视觉和时序关系2个方面定义视频相似性，对运动视频的查询十分有效。

参考文献：

[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] 谢东, 吴敏. 基于范围语义的非一致性数据库聚集查询[J]. 中南大学学报: 自然科学版, 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] 顾波, 邱道尹, 梁祥州. 基于彩色转换的水果分类系统设计[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] 董道国, 刘振中, 薛向阳. VA-Trie: 一种用于近似k近邻查询的高维索引结构[J]. 计算机研究与发展, 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 approximate k nearest neighbor query[J]. Journal of Computer Research and Development, 2005, 42(12): 2213-2218.

[11] 赵亚琴, 周献中, 何新. 利用等价关系理论进行视频片段检索的方法[J]. 中国图像图形学报, 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] 彭宇新, 董庆杰. 一种通过视频片段进行视频检索的方法[J]. 软件学报, 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] 张静, 路红, 薛向阳. 基于索引结构的高效运动视频检索[J]. 计算机研究与发展, 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.

收稿日期：2009-06-15；修回日期：2009-08-10

基金项目：国家自然科学基金资助项目(79816101)

通信作者：夏利民(1963-)，男，湖南攸县人，教授，博士生导师，从事数字图像处理及模式识别等研究；电话：13974961656；E-mail: xlm@mail.csu.edu.cn

(编辑 刘华森)