基于动态滑动窗口和折半查找的镜头检测算法

明 巍,鹿秀丽（.湖北师范学院数学与统计学院；.黄石市中心医院信息部，湖北 黄石 43500）

基于动态滑动窗口和折半查找的镜头检测算法

明 巍1,鹿秀丽2
（1.湖北师范学院数学与统计学院；2.黄石市中心医院信息部，湖北 黄石 435002）

摘 要：针对视频数据处理的数据量比较大的问题，提出了一种基于动动窗口和折半查找的镜头检测算法，实验结果表明，相对传统的计算相邻两帧差值的镜头检测算法，算法的检测效果很好，算法复杂度低，易于实现。

关键词：滑动窗口；折半查找；镜头检测；HSV颜色直方图

1　引言

镜头（shot）是视频的基本物理单元，它由一个摄像机拍摄得到的连续若干帧组成[1]。镜头检测是基于内容的视频检索的重要内容和关键步骤，直接关系到视频检索的效率。

镜头的转换方式主要有两大类[1]：切变（突变）和渐变。镜头切变检测的方法主要有[1-3]：像素对比较方法、模板比较方法、似然比较方法、直方图比较方法、滑动窗口法等。镜头渐变的特点是两个镜头之间的切换过程是逐渐完成的，从一个镜头变化到另一个镜头经常延续十几或者几十帧。目前镜头渐变检测的方法主要有[4]：双阈值方法、基于模型的方法等。

传统计算相邻两帧之间的差值进行镜头检测的算法将耗费大量的时间在每一帧信息的提取和计算相邻两帧之间的差值上。通过对视频特征数据的分析，同一镜头中两帧之间的差值相差较小，不同镜头中两帧的差值相差较大，而且同一镜头中的帧数比较多。根据视频的这一特点，提出了动态滑动窗口和折半查找对镜头检测的算法。

2　两帧差值的计算

两帧差值的计算需要利用视频HSV颜色直方图的特征来计算视频中任意两帧之间的差值。设视频帧序列集合为， HSV颜色分割采用HSV(12×5×5)制，即H分量等分为12块，S、V分量各自等分为5块，HSV颜色空间的直方图定义为式（1）：表示视频帧序列集合中的第m帧，Hi、Si、Vi分别表示第i像素点的H、S、V值，其中Hj、Sj、Vj表示第j像素点的H、S、V值，L为每一帧图像像素点的个数,

3　自动选取阈值的方法

对于任一视频数据，任意选取连续的k帧作相邻两帧之间的帧间差值，可以得到一个由k-1个差值所构成的集合。通过帧间差值的分析，得到集合中明显比两边差值大很多的特征差值。在这些特征差值中得到最大差值maxdistance和最小差值mindistance，定义镜头检测阈值：

4　动态滑动窗口和折半查找

由以上的公式（1）和公式（2）可知，提取每一帧的HSV颜色直方图信息和计算两帧之间的差值所需要的时间在整个镜头检测算法中所占的时间的比例是比较大的。传统计算相邻两帧之间的差值进行镜头检测的算法将耗费大量的时间在每一帧信息的提取和计算相邻两帧之间的差值上。根据视频同一镜头中两帧之间的相似性，可以推断同一镜头中两帧的差值和不同镜头中两帧的差值有显著的差异。又根据视频同一镜头中包含的帧数一般比较大的特点，提出了动态滑动窗口和折半查找对镜头检测的算法。

5　实验及结果分析

对镜头边界检测结果的评价方法一般使用查全率和查准率这两个参数，它们的定义如下：

查全率和查准率越高，说明算法的效果越好。本文在采用查全率和查准率作为视频镜头检测算法的衡量标准的基础上，从算法的时间复杂度方面将本文的算法与传统计算相邻两帧之间的差值进行镜头检测的算法进行比较。

本实验在Visual C++6.0环境中进行，建立包括体育，电影，广告，纪录片在内的实验视频库，总帧数是5867帧，帧速率为25帧/秒，视频被转化为320×240标准尺寸。

本文算法的结果与文献中的算法进行对比，查准率相差不大。本文算法的误检主要原因在于对于镜头切换较快的视频，误检会增多，查准率会下降。但是从算法效率来看，本文的算法不需要计算每相邻两帧的差值，算法效率大大提高。

参考文献：

[1]章毓晋.基于内容的视觉信息检索[M].北京:科学出版社,2003.

[2]钱刚，曾贵华．典型视频镜头分割方法的比较[J].计算机工程与应用，2004(32):5l-55．

[3]肖治民，林坤辉，周昌乐.基于HSV颜色空间的视频镜头检测[J].厦门大学学报（自然科学版），2008,47(05):665-668

[4]原野，宋擒豹，沈钧毅.一个自动阈值选择的镜头检测算法[J].小型微型计算机系统.2004,25(07):1337-1340.