基于改进镜头边界检测算法的视频检索系统

邹晓燕，殷 建

（山东大学威海分校 信息工程学院，威海 264209）

随着多媒体技术和互联网技术的发展，多媒体信息已逐渐成为信息处理领域中越来越重要的信息媒体形式。面对越来越庞大的网络多媒体信息，要找到自己所需信息并非易事，而准确地找到自己所需的信息则更是难上加难。为了便于人们快捷准确地访问多媒体信息，研究人员在过去的十几年里已经开展了大量的研究工作，主要集中在两个方面：基于关键字的检索和基于内容的检索。在基于文本的图像检索（Text-based Image Ret r ieval）中采用关键字标识符方法描述信息线索，然后在索引时对标签进行检索。这样一来对图像的查询变成了基于标签的查询。这种传统的方法虽然简单，但特定的标签只适合特定的查询要求，并且没有统一标准。此外这种方法不适用于大规模的数据集合。为了解决这个问题，基于内容的视频检索受到了人们广泛的关注。基于内容的视频检索，就是由计算机来对视频内容进行自动分析，用户可以通过提交样例数据或者描述信息查找自己想要的视频数据。

在基于内容的检索技术中，视频结构的基本单元是镜头。镜头定义为摄像机一次不间断的拍摄。因此同一镜头内的内容具有一致性。基于内容的视频检索的第一步工作就是从视频流中找到镜头变换的边界，从而对视频流进行切分以得到一个个的镜头，其效果的优劣直接影响到视频特征的提取、更高层结构的描述以及视频的浏览和检索，因此，镜头分割在基于内容的视频检索中有着重要的地位。镜头的变换是指两个镜头之间的切换，从大类上分，可以分为突变和渐变两大类。传统的镜头分割算法对于镜头内部闪光的误检率过高，或者不能同时检测到镜头的突变和渐变。而本文提出的改进的算法，即自适应滑窗的双阈值镜头检测算法，可以很好地对两种镜头转变方式进行识别，并且可以使镜头内部闪光的误检率大大下降。

1 特征选择

在视频边界检测技术中，可以使用的视频特性包括颜色、纹理、运动向量等。选取其中的一种则对视频的描述不够精确，检索也容易出现大的误差，选取过多的特性则会在数量级上加大计算量，极大地降低计算速度，因此，本文中我们选取颜色直方图和纹理直方图作为特征，一方面可以对全局颜色信息进行描述，另一方面可以对图像的局部纹理进行刻画。

1.1 HSV颜色空间

选取HSV颜色空间对颜色进行H、S和V3个分量上的划分，它符合人眼对颜色的识别模式。在这3个分量中，H是最重要的，因此划分的时候，采取非等量化分，使用7∶2∶2的模型，从而得到一个28维颜色直方图。

1.2 纹理谱描述子

本文使用纹理谱描述子来描述纹理。对于图像中的每一个像素，使用一个3×3的矩阵I来描述它的纹理模式，I的计算公式如式（1）：

为了降低计算难度，将矩阵I映射成一个[0,255]之间的值T，公式如式（2）：

其中，G 为变换系数矩阵。

这样，可以将3×3的区域纹理模式转化到[0,255]之间的一个值。具有视觉一致性的多种纹理模式将分类成为同一种纹理模式，这样纹理直方图的维度就降低很多，为后续的计算节省了不少资源而精确度上却没有较大的损失。视觉一致性定义： 对于任意两个纹理模式A和B，如果通过旋转（0°，90°，180°或360°），翻转（水平，垂直，主对角线或副对角线）等变换，A可以转换为B，则认为A和B 具有视觉一致性，划分为同一纹理模式类。最终，可以得到51种纹理模式类。

1.3 二维联合直方图

使用颜色和纹理两种特征，可以得到28×51维的二维联合直方图。设随机变量C代表颜色分量，随机变量T代表纹理分量，则Pi,j=P(C=ci,T=tj)代表联合分布公式。通过该公式即可得到联合分布直方图。单一特征直方图可以通过二维联合直方图的边缘分布得到。对于两个二维分布直方图Hx和Hy，其相似度可以用两个直方图的交来表示，公式如式（4）：

而两个直方图的距离，也就是帧间差，可以用1－Inner(Hx, Hy)来表示。

2 传统滑动窗口镜头边界检测算法

定义一个长度为2R+1的窗口，使要检测的帧位于次窗口的正中。计算前后两帧的帧间差差值，设Di为待检测帧的帧间差差值，则当Di满足下列条件时认为待检测帧处为突变位置：

（1）Di是2R+1窗口中的最大值。

（2）设窗口中的第2大帧间差为D2，且Di＞k·D2。

传统的滑动窗口法主要用于镜头突变的检测。它可以有效的减少因全局阈值选取不当而造成的漏检。但是由于其判断准则较为简单，会造成较大的漏检和误检。

3 传统双阈值镜头边界检测算法

传统的双阈值法是一种经典的通用镜头检测方法，可以检测出突变镜头和渐变镜头。根据前面滑动窗口算法对突变镜头检测的介绍，当前后两帧的帧间差超过阈值时，则认为此处有一个突变，可将此方法推广到渐变检测中。帧间差在渐变处要比在镜头内部高，但比在突变处要低很多。为此，需要设置高低两个阈值TH和TL。顺序考察帧间差，如果超过了TH，就认为是检测到一个突变。如果没有超过TH，但超过了TL，就认为检测到了一个可能的渐变起始帧，并继续向后检测，如果仍超过TL，则将帧间差累加，直至帧间差低于TL。若此时累计的帧间差超过了TH，则认为是检测到渐变的结束帧，否则认为刚才那些超过TL的帧间差是由于其他原因（如光照变化和运动等）造成的，不是渐变。这个过程如图1。

图1 双阈值法镜头检测示意图

4 改进的基于滑动窗口和双阈值的镜头边界检测算法

传统的双阈值算法可以同时检测突变和渐变，具有算法简单，计算量小等优点。但是其检测效果依赖于阈值的设定。本文通过统计当前窗口内的平均帧间差，从而动态设定阈值，提高了算法的灵活性和适应性。具体算法如下：

（1）输入：高阈值因子FH，低阈值因子FL，初始窗口宽度w， 二次检测长度l，帧间差计算函数fradif(i,j)，整个视频的帧间差序列FraDif={d1, d2, …, dn}。

（2）输出： 镜头边界序列n1, n2, …, nm。

。对于每个帧间差di做如下判断：

（1） 如果di>TH，则说明可能发生了突变。以当前帧为中心，取长度大小为l的窗口，计算该窗口帧间差序列的均。

（2）如果diTL，则假定出现渐变，设置渐变标志。记录下当前帧位置作为候选镜头边界，并开始累计帧间差FraDiffSum。

（3）如果diTH，则说明渐变可能发生，需进一步检测。假定渐变发生，设渐变开始帧为s t ar t，渐变结束帧为end，计算。如果，则认为发生了渐变，并记录当前渐变位置。否则认为没有发生渐变，取消渐变标记并清零FraDiffSum。

如果判断发生了镜头切换，则需要重新设定窗口并计算帧间差平均值：。如果没有发生镜头变化，设当前镜头开始位置为start，取w=max(w,i－start)，调整阈值。根据设定高阈值，设定低阈值。

在算法的最后，所有帧处理完毕后，输出镜头边界序列n1, n2, …, nm。

改进的算法主要是改变了自适应阈值TH和TL的确定方式。在算法中，设定窗口宽度w小于一个镜头长度（可设定为视频的fps值）。这样每一个镜头的阈值由该镜头内的帧间差动态确定。不同的镜头，其内部的活动度不一样，活动度与平均帧间差、阈值成正比。由镜头本身确定的平均帧间差和阈值才能够正确地检测出镜头的变化。另外在检测出镜头边界后，需要提取镜头的前后l帧进行镜头边界的确认。这样能够有效地避免因为闪光等原因造成的误检。

5 实验与讨论

5.1 镜头边界检测算法的评价标准

综合考虑正确检测数、漏检数和误检数，检测一个镜头边界检测算法是否有效。

5.2 实验结果

实验中，共选取了2段视频片段，16 402帧，合计突变镜头52个，渐变镜头13个。分别采用传统滑动窗口镜头检测算法(A)、传统双阈值镜头边界检测算法(B)和本文提出的改进算法(C)进行了突变镜头的检测并对实验结果进行比较，如表1。

表1 算法运行结果比较表

由表1可见，传统滑动窗口镜头检测算法的漏检误检现象比较严重。传统双阈值镜头边界检测算法效果要好于传统滑动窗口镜头检测算法，相比之下，本文提出的改进算法能够较好地避免漏检和误检。由于本算法对检测到的镜头边界进行了第2次验证，因此可以有效避免由闪光造成的误检。

5.3 使用改进算法实现的视频检索系统

本文使用Visual C#和SQL2000实现了一个基于本文提出算法的视频分割检索系统。系统分为视频分割部分和视频检索部分。首先对视频进行分割，同时在视频中抓取要查找的图像，然后让系统动态查找与该幅图像相似度最高的关键桢图像。根据实验结果可知，该改进算法快速有效。

6 结束语

通过使用颜色纹理等特征并对视频采用本文提出的方法进行镜头检测，实验结果表明，本文提出的算法较之传统算法在精确度和效率上有了较大的改进。

[1]肖莎莉，周昌国，唐岳霖. 基于DirectShow的镜头边界检测系统[J]. 重庆大学学报（自然科学版）， 2006，29（1）.

[2]孙季丰，李颖雄. 视频镜头自动分割的若干方法[J]. 华南理工大学学报， 2003，31（8）.

[3]刘政凯，汤晓鸥. 视频检索中镜头分割方法综述[J]. 计算机工程与应用，2002，38（23）.