基于空间金字塔的镜头检测

1.北京信息科技大学 中文信息处理研究中心，北京 100101

2.北京拓尔思信息技术股份有限公司，北京 100101

1.北京信息科技大学 中文信息处理研究中心，北京 100101

2.北京拓尔思信息技术股份有限公司，北京 100101

1 引言

视频是一种非结构化、大信息量的数据，基于文本检索的传统方法人力财力耗费巨大，并且视频内容受个体主观因素影响较大，因而基于内容的视频检索（Content Based Video Retrieve，CBVR）成为研究热点。镜头检测是将随时间变化的图像流分割出内容不同的一个个镜头，是CBVR的基础，直接影响到检索结果的准确性。镜头检测（即镜头的边界检测），通过比较视频帧的帧间差异，寻找镜头的边界变化。

对镜头进行检测，首先要解决的问题是何为一个镜头。一个镜头是由一个摄像机连续拍摄得到的时间上连续的若干帧图组成[1]。

2 相关研究

镜头检测，是根据视频中图像的内容特征差异来区分，不同的镜头其图像视觉内容也不同，从而其图像特征也会不同。因此，镜头检测的效果很重要一部分是依赖于特征的选择，在选择检测特征时需注意：（1）应该体现出帧间的视觉差异；（2）对摄像机、物体运动有一定的鲁棒性；（3）能有效克服或消除光照变化对检测结果的影响。

文献[2]采用直方图变换率HCR（Histogram Change Ratio）法，其对单一的使用直方图的方法进行了改进，仍然没有考虑像素的位置信息，其效果也是有限的。文献[3]将小波与神经网络结合进直方图的方法，其运算量太大，对性能的限制大。文献[4]使用了SVM进行镜头检测，其也是用了HSV的颜色统计特征，也没有用像素的位置信息特征；并且其需要对视频进行抽样取足够大的训练集进行训练，确定分类的标准，通用性需要进一步考证，其实验结果显示对平移或运动较易误检。文献[5]虽然考虑了像素特征，同时也考虑了像素位置信息，使用的是金字塔的思想，但是其使用的颜色直方图的算法与人类的视觉感知不相符，而且其位置信息考虑过多，得到的效果不是很理想。所以本文提出了空间金字塔与直方图结合的改进方法，既考虑像素的视觉信息又考虑像素的空间信息，相较于以上文献在查全率和查准率上都有很大的提高。

3 空间金字塔

3.1 分块空间金字塔

空间金字塔是一种考虑图像的全局像素信息的方法。文献[5]使用的是如图1所示的空间金字塔方法。

图1 空间金字塔及各层量化信息

从图1可以看出，随着层数的增加，分的小块越来越多、越来越细，考虑的位置信息越来越多，相对地，每一块的像素信息直方图的划分会越来越粗糙。算法如下：

图像 f(x，y)在单个维度上像素所属块的位置确定为：

其中a表示行和列分的块数（本文中要求行和列分的块数相同），width和height表示图像的宽和高。每个像素点对应的块编号为：

其中l表示每个块所要提取的特征向量的维数，bin∈[0，a2-1]。最后得到这一层的特征向量为：

其中H[bin+1]表示每个块的图像内容特征的特征向量，i表示特征向量的下标索引。

较低的级的位置信息较少，可以去掉单个抖动和噪声的干扰，越往级数高的层像素的位置信息考虑得越多，从而可以识别出相邻的重复帧。

3.2 采样空间金字塔

一种多尺度的的金字塔方法，通过计算不同分辨率的图像信息来获得图像的多尺度表达，如图2所示。

其思想是，对于一幅N×M的图像，在行和列两个方向上对其进行1∶2的亚采样，可构成原图像的一幅(N/2)× (M/2)的缩略图。将亚采样重复进行，随着层数的增加，每一层的图像是下一层图像的宽和高的一半，就得到构成金字塔的各层图像[6]。

在亚采样过程中，可使用C(↓2)表示亚采样算子，则帧图像每一层的单个采样用下式表示：

图2 亚采样金字塔

公式表明第k+1层的亚采样图像可由第k层的亚采样图像计算得出，其中符号“↓”后的数字表示亚采样率，C是卷积模板，表示压缩算子。

亚采样可能会丢失一部分细节信息，图像的质量不能保证。实际应用时，在采样的过程中也可同步加入图像的平滑，例如各种低通滤波器，像均值滤波器或高斯滤波器等。但是，镜头检测不关注图像的细节信息，只要有足够的信息可以将不同镜头分开即可，所以本文不进行平滑运算，只取亚采样操作，所构成的金字塔是亚采样金字塔。

4 镜头检测

4.1 特征选择

现在的视频多以彩色为主，颜色又是图像的一种非常重要的视觉特征，并且颜色特征以其定义明确、抽取容易，已经在图像检索应用中证明非常有效，所以本文采用颜色特征作为帧图像的底层特征。HSV模型与人对颜色的感知接近，本文将HSV空间等间隔量化为8×4×4=128级，作为只含像素信息不含像素位置信息的直方图特征。

本文使用均匀量化对HSV的三个分量进行量化。H(Hue)色调平均分为8个区间，从0°开始每45°划分一个区间，分别对应的量化编码为0到7。S（Saturation）饱和度与V（Value）亮度均分为4个区间，分别为[0，0.25]，（0.25，0.5），（0.5，0.75），（0.75，1]，对应于量化编码为0到3。将HSV合成一维特征矢量是：G=16H+4S+V，其中G∈[0，127]。组成一个128维特征向量，再将特征向量进行归一化处理。

4.2 空间信息选择

根据前面的分析，空间金字塔可看成图像中像素位置信息的一种表现形式，亚采样表现的是空间中单个像素点之间的位置关系，块分割表现的是像素的集合的位置关系。所以本文将两种金字塔结合起来使用。经过大量实验观察出，像素的空间位置信息是不可少的，否则其查准率到达一定程度后总是无法提向更高。但是如果考虑过多的位置信息，会受到小的物体运动的影响，其查全率就会急速地下降。

首先，将原帧图像进行两次亚采样运算，分别得到Level 1和level 2两层的图像信息。接着将得到的Level 1的图像均分成四块，如图1中的第二层所示。最后得到Level 2和Level 1的四个块，及得到一个全局位置信息和四个局部位置信息，总共五个块的信息。

4.3 镜头检测

同一个镜头内的各帧图像的内容大致相似，不同镜头内的图像内容也存在比较大的不同。图像的内容相似度，根据其特征向量的相似度度量。根据像素的位置信息选择，再提取颜色信息，整个图像的特征提取过程如图3所示。

图3 直方图特征提取过程图

直方图匹配的算法很多，本文使用既简单又容易理解的直方图相交的方法计算相似度。镜头检测的总体算法步骤为：

步骤1将原图像帧Fi进行第一次降采样操作，得到图像Fi1。

步骤2根据分块空间金字塔的算法，将Fi1的行与列各区二等分，总共分成大小相等的四块像素区域，分别提取每一块的HSV特征，得到整幅图像的特征向量。

步骤3将图像Fi2进行一次亚采样，得到图像Fi2，计算此图像的hsv特征。

步骤4将以上步骤计算得到的两个特征向量级联，得到该帧总的特征向量。

步骤5使用直方图相交算法计算帧间的相似度，大于阈值的认为是出现新的镜头，并提取作为关键帧。

5 实验

5.1 实验数据

本文采用信息检索的通用评价方法，即使用查全率和查准率对镜头检测进行评价，查全率（Recall）和查准率（Precision）分别表示为：

其中，Nc表示正确检测到的镜头数，Nm表示漏检的镜头数，Ne表示检测到的错误的镜头数。

本文对多种视频类型进行测试实验，视频多是从文献[7]处下载，各个视频的信息如表1所示。

表1 所用视频信息

5.2 对比实验

表2 实验比较的部分数据

直方图变化率HCR是文献[2]提出的方法，文献[5]中使用IOO三个变量表示其特征，所用本文中用IOO表示文献[5]的方法，本文是使用的直方图空间金字塔HSP（Histogram Space Pyramid）方法，所以用HSP表示本文方法，实验结果如表2所示。表中所用到的符号说明：No.表示视频序号，T表示阈值，R表示查全率，P表示查准率，N表示检测出的镜头总数，Nc表示正确检测到的场景数。

从图4中的实验结果可以推出，本文的方法与HCR方法相比，虽然查全率没有HCR方法高，但是查准率却比HCR的方法高很多。与IOO方法相比，查准率没有IOO方法高，但是查准率却比IOO方法高。HCR的准确率比较低的原因是，HCR根据的是视频帧边缘的改变率，对于图像帧的像素位置信息考虑不足，将颜色直方图分布相近，而内容不同的镜头帧给丢失了。IOO方法的查全率比较差的原因是，其特征直方图虽然也是根据像素颜色特征提出，但是与人的时间感知不太贴合，容易造成漏检，而且其考虑像素的位置信息过多，对于运动比较敏感，将很多相同的镜头判定为不同的镜头，所以造成较多的漏检。

图4 各视频的实验结果对比图

对于视频检测来说，查全率高而查准率低的方法，检测出相同的镜头比较多，即冗余信息比较多，数据库中冗余信息就会很多；而查准率高而查全率低的方法，检测出的镜头会比较少，会丢失很多重要的镜头，对于视频检索的高层语义构建不能提供足够的信息。所以本文的方法是很有优势的，在阈值调整到比较合适的值时，可以使查全率和查准率都相对比较高，例如对于电影视频查全率和查准率都可以在90%以上。

文献[8]是使用小波变换算出视频帧的颜色特征和纹理特征，再根据相邻帧的颜色特征互信息与纹理特征的信息熵差计算相似度。虽然颜色特征体现的是像素的信息，纹理特征体现一定的像素位置信息，但是小波变换的计算复杂度太高，在实际中的应用有限。文献[9]是使用小波分析与统计量综合的方法，对于小的运动误检严重，而且同样的计算量很大，不实用。文献[10]是使用SIFT特征进行镜头的检查，虽然SIFT特征在匹配过程中效果还可以，但是其运行速度是让人难以接受的，一个普通的1小时视频，处理大概要2天以上，无法实现web实时服务的要求。

综合考虑，本文的优点是：（1）既考虑像素信息，又考虑了像素的位置信息；（2）既考虑了像素位置的全局特性，又考虑了其局部特性；（3）对视频中物体的运动有好的鲁棒性；（4）均衡考虑了查全率与查准率两个属性；（5）算法简单直观，有较高的实用价值。

6 总结与展望

本文方法对颜色直方图的方法进行了改进，将空间金字塔与HSV颜色直方图结合。有实验结果得出，在取合适的阈值的时候，其综合检索效果比HCR和IOO方法好一些。从实验结果可以分析出，查全率与查准率之间会存在一个权衡，根本原因在于图像的像素信息与像素的位置信息之间存在一定的取舍关系，考虑的位置信息过多虽然可以提高查准率，但是可能会造成漏检情况比较严重。所以，对于位置信息的考量可以作为今后研究的重点。

[1]章毓晋.基于内容的视觉信息检索[M].北京：科学出版社，2003：221-223.

[2]秦剑鹏，符茂胜，涂铮铮，等.基于颜色直方图变化率的视频镜头检测[J].计算机应用与软件，2011，28（4）：17-20.

[3]周顺勇.基于小波神经网络的镜头检测[D].成都：电子科技大学，2009.

[4]卢悦.基于内容的视频镜头检测与分类研究[D].山东：山东师范大学，2010.

[5]Chum O，Philbin J，Isard M，et al.Scalable near identical image and shot detection[C]//Proceedings of the 6th ACM International Conference on Image and Video Retrieval.New York， USA：ACM，2007：549-556.

[6]章毓晋.图像工程（上册）图像处理[M].北京：清华大学出版社，2006.

[7]The open video project[EB/OL].[2011-07-11].http：//www.openvideo.org/.

[8]李玉峰，赵政.基于特征信息的镜头检测研究[J].计算机工程与应用，2009，45（6）：168-169.

[9]叶军，吴菲，李建良.基于综合相似度的二次差分法在镜头检测中的应用[J].计算机工程与科学，2008，30（3）.

[10]刘根涛.基于内容的视频结构分析[D].北京：北京邮电大学，2010.

基于空间金字塔的镜头检测

都云程1，2，任绍美1，王 涛1，2，吕学强1，2

DU Yuncheng1，2,REN Shaomei1,WANG Tao1，2,LV Xueqiang1，2

1.Chinese Information Processing Research Center,Beijing Information Science and Technology University,Beijing 100101,China
2.Beijing TRS Information Technology Co.,Ltd.,Beijing 100101,China

In this paper,it proposes a new method,which takes into account both pixels’information and its location,combining the HSV histogram and the spatial pyramid of pixels to detect shots.A sub-sampling image,which is the first layer of the sub-sampling pyramid,is evenly split to four blocks.It is to extract color features from the four blocks respectively.Making another sub-sampling is to get a second layer image,and it extracts the color feature.It is to connect five vectors to be this frame image’s color feature,and calculate the similarity of adjacent frames.This algorithm considers not only the pixel information, but also the location information both of the global and local ones.Experimental results show that this method gives a better balance about recall and precision rates.

spatial pyramid;sub-sampling;blocking;histogram

提出一种HSV颜色直方图与像素的位置空间金字塔结合的方法，该方法既考虑像素的信息，又考虑了像素的位置信息，来进行视频镜头分割。将图像进行一次亚采样，对得到的第一层亚采样图像进行均匀的四分割；对得到的四块小区域分别计算其颜色直方图，获得四个特征向量；将第一层亚采样的图像再进行一次亚采样，得到第二层亚采样图像，并计算其颜色特征向量；将五个特征向量级联，作为图像帧的特征，并计算相邻两个帧的相似度。该算法不仅考虑了像素信息，还考虑了像素位置信息，而且考虑的是全局位置信息和局部位置信息。实验结果显示，该方法较好地权衡了查全率和查准率。

空间金字塔；亚采样；分块；直方图

A

TP37

10.3778/j.issn.1002-8331.1111-0146

DU Yuncheng,REN Shaomei,WANG Tao,et al.Shot detection based on spatial pyramid.Computer Engineering and Applications,2013,49（11）：187-190.

国家自然科学基金（No.60872133）；北京市自然科学基金（No.4092015）；北京市教委科技发展计划项目（No.KM201110772021）；国家科技支撑计划课题（No.2011BAH11B03）。

都云程（1967—），男，高级工程师，主要研究领域为中文信息处理、信息检索与Web应用；任绍美（1986—），女，硕士在读。E-mail：renshaomei2008@126.com

2011-11-09

2012-01-17

1002-8331（2013）11-0187-04

CNKI出版日期：2012-04-25 http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1721.068.html