基于分块直方图帧差变化率的镜头分割算法研究

陈逸韬，宫宁生，王淑敏

（南京工业大学 计算机科学与技术学院，江苏 南京 211816）

基于分块直方图帧差变化率的镜头分割算法研究

陈逸韬，宫宁生，王淑敏

（南京工业大学 计算机科学与技术学院，江苏 南京 211816）

在介绍了目前主流的镜头分割算法后，文章提出一种基于分块直方图帧差变化率的镜头分割算法。该算法主要分为两部分：突变检测和渐变检测。首先利用图像的HSV分块直方图特征计算相邻帧帧差，将其与自适应的突变阈值比较从而确定突变镜头的位置。然后利用突变分割得到的视频段进行镜头渐变的检测。对每一个视频段利用相邻帧帧差变化率的规律来判定渐变位置。实验结果表明，该方法具有较高的准确率，并且易于实现。

HSV色彩模型；分块直方图；镜头突变；镜头渐变；帧差变化率

随着互联网和多媒体技术的蓬勃发展，越来越多的多媒体内容涌入到人们的日常生活当中来。面对网络上涌现出越来越多的视频，依靠传统的人工标定整理的方式已经无法满足时代的需求。于是基于内容的视频检索孕育而生，而镜头分割就是关键的第一步，也是后续视频高层内容分析的基础。现在已经有很多成熟的视频分割研究成果［1］。镜头的分割方法有两大类，一种是基于压缩域的，另一种是基于非压缩域的。基于压缩域的镜头检测方法主要有Yeo和Liu提出的一种利用MPEG压缩视频的DC（离散余弦）序列进行镜头边界检测的方法。基于非压缩域的镜头检测方法主要有［2-3］：基于图像像素的方法、基于图像直方图的方法和基于运动边缘的方法等。

本文提出一种基于分块直方图帧差变化率的自适应镜头分割方法，它的实现思路是：充分利用HSV符合人眼视觉特征的特性，使用该色彩空间的分块直方图来表示一帧图像。利用自适应的阈值先对整个视频进行突变的镜头分割，然后再在任意两个突变镜头之间根据帧差变化率进行渐变检测。

1　图像特征和差异性度量

1.1 视频帧图像的特征表达

本文选取基于HSV色彩空间的分块直方图作为帧图像的描述特征参与到边界检测中来。HSV是一种符合人眼视觉特征的彩色模型。其中H代表色调（Hue），S代表饱和度（Saturation），V代表明度或亮度（Value）。

当选定了HSV空间模型直方图来表示视频帧图像的颜色特征后，出于存储效率的考虑，还要进行非等间隔量化。这里采用论文［4］的量化方法。方法是将H分量量化成8份，S 和V分别分成3份。因为人眼对H分量的感知比其它两个分量更细致一些，因此量化的份数也更多一些。这样这个直方图矢量的分量个数就减少为8×3×3=72个了。

考虑到一般的直方图难以反映图像的空间位置信息，因此本文采用分块的直方图方法，文［5］考虑的不同区块的重要性不同，采用了类似高斯加权的方式，但是却是采用了简单平均的分块方式，如图1（a）所示。文［6］使用了一种改进的分块策略—黄金分割比分块策略。如图1（b）所示。此方法将图像的长宽分别按照3∶5∶3类黄金的比例进行分割。这种方案相较第一种能更好地突出图像的主要内容，并且能有效地降低图像周边的影响。本文在参考了上述的方法后提出了一种新的改进的直方图分块策略。如图1（c）所示。采用这种方法的原因是视频中的人物关系，以及各种事物的呈现都是横向结构的，经过研究也发现，在视频中（尤其是电影），人物往往会占满纵向空间，而基本不会占满横向空间。因此图像的上下分块不需要分那么多，而左右的分割要尽可能扩大中间的区域，从而容纳更多有用的信息。

图1　不同的直方图分块策略（图像内的数字为权值）

1.2 帧间差异性度量

比较两个直方图之间的差异，其实就是定义一种合适的距离度量方式来计算两个直方图的距离。这里设定两个直方图的距离为：

由于一帧图像被分为了若干块，且每块被赋予了不同的权值，因此两帧图像的差值为：

其中为加权系数，就是某个分块直方图的差值。就是m，n两帧的差值。

2 镜头分割算法详述

2.1 镜头突变的检测

镜头的突变切换是突然的，切换前的最后一帧和切换后的第一帧之间是没有过渡帧的。所以从人眼视觉的直观感受上看画面出现了一个明显的跳变，实际原因就是视频中运动物体的运动轨迹出现了断裂，失去了连续性。所以从理论上来说切变的前后两帧中的画面内容应该相差很大，它们的直方图差异也会比较明显，实验观察的确如此，如图2所示。

图2　突变变换

是相邻两帧 的差值（见公式3），公式左边代表从该镜头第一帧到当前帧的前一帧的所有相邻帧间差的和。需要的是帧间差平均值：

则镜头突变检测的自适应阈值为：

突变检测的方式为，用当前帧跟前一帧得到的帧差与这个阈值比较，如果大于这个阈值则判定为镜头突变的位置。这里需要考虑系数a的选取，根据大量实验结果表明，在本论文的数量级空间下，绝大部分突变位置的帧差是当前平均帧差（）的20倍以上，也就是说当前帧的帧差值如果大于平均值的20倍基本就可以确定为突变帧。

2.2 镜头渐变的检测

在完成了突变镜头的检测后，一个完整的视频就被分割成了若干小视频段，视频段的两端就是镜头的突变帧。下面就是要在这些视频段里找寻镜头渐变帧的位置。如图3所示，这是发生了镜头渐变切换的视频段的帧差直方图。

图3　含有渐变变换的帧差

图3（a）中椭圆圈住的部分就是镜头渐变发生的区域。箭头指出在镜头发生渐变变换时相邻帧差的变化趋势。从图中可以看出渐变部分呈现出一个凸包的形状，整体上从左往右看变化趋势是先递增再递减。其中图3（a）是包含一个渐变镜头的情况，图3（b）是包含多个渐变镜头的情形。由此本文提出一种根据帧差值变化率来检测镜头渐变的方法。

首先对算法中用到的变量进行说明：设某一个小视频段的长度为L（帧），将其分割成M子段，每个子段取等长设为K（帧）（一般取5到8即可），则M=L/K。设Li为第i子段帧差代表值（i = 1， … ，M），inum， dnum分别为子段的L值连续增加和递减的个数。W为判断是否还属于一个渐变镜头的判定阈值，设为一个渐变镜头帧数的一半，由大量实验测试得出，一般镜头的渐变变换都要持续3秒以上也就是接近80帧，所以这里设W的值为35/K。w为发生连续递增和递减之间的子段间隔。具体流程如下：

（1）令i=1， w= 0。inum=0， dnum=0。

（2）若i > M，则转（6），否则将第i子段中的K帧按照其帧差值排序，找出中位数和求取帧差平均值，分别记为Mid 和Mean。若Mid > Mean，则Li= Mean，若Mean≥Mid，则Li= Mid。若inum≥3转（5），否则转（3）。

（3）若i为1，则转（2），否则转（4）。

（4）若Li＞Li-1，inum=inum+1，i=i+1，转（2）。

若Li≤Li-1：

a.若inum＜3，inum=0，i=i+1，转（2）。

b.若inum≥3，dnum=1，i=i+1，转（2）。

（5）若Li＜Li-1，dnum=dnum+1，w=w+1，i=i+1，转（2）。

若Li≥Li-1：

a.若dnum≥3，则确定一个渐变区域，设第i子段中的最后一帧为分割帧。inum=dnum=w=0，i=i+1，转（2）。

b.若dnum＜3，若w≥W，则inum=dnum=w =0，i=i+1，转（2）。否则dnum=0，w=w+1，i=i+1，转（2）。

（6）若dnum≥3，则说明镜头渐变结束之后紧接着发生了镜头的突变切换，因此这时就可以用已经检测出的突变帧作为镜头的分割处，转（7）。

（7）算法结束。

整个算法的核心思路是：只要出现连续3段的L值递增的情况就认为一个可能的渐变开始，然后在设定的宽度内出现连续三段L值递减的情况就判定该算法该算法为一个渐变区域。

3　实验结果分析

作为对论文算法有效性的检验，随机选取4部电影的片段进行检验，并且跟文献［8］中的方法作了比较。该论文提出一种基于亮度直方图帧差的自适应镜头分割算法，用亮度直方图作为图像帧的特征向量，并且采用双阈值。将相邻两帧的亮度直方图帧差跟自适应的双阈值比较，如果大于大的阈值则进入突变检测模块，如果介于两个阈值之间，则进入渐变检测模块，在渐变模块中采用了基于帧间差方差的方法检测渐变。

这里采用论文中常用的评估指标查全率和查准率来评价对比两种算法，如表1所示。

表1　实验结果对比

01视频段里全部是突变镜头，且整段视频相对比较平和，因此两种算法的准确率都非常之高。03和04两端视频里包含了数量较多的渐变镜头，且镜头突变间的画面变化较为激烈，因此两种算法的查全率和查准率都有所下降，但是实验表明本文算法仍然优于对比算法。尤其在镜头渐变检测中的误检率要小于对比方法。

4　结语

文中提出用HSV彩色模型做出的直方图作为视频帧图像的量化表达，充分利用了HSV模型符合人眼直观视觉感受的特性，并且利用分块直方图的方法有效克服了一般直方图会丢失图像空间位置信息的弊端，再通过加权的方式，突出一幅图像不同位置重要性的不同，从而能更好地区分视频帧之间的差异。在镜头分割过程中，本文采用先做突变分割再做渐变分割的策略，利用突变检测分割好的视频段进行镜头的渐变检测，忽略掉一些间隔较短的视频，对符合要求的视频段采用帧差变化率的方法来检测。实验结果表明该方法具有较高的准确率和实用性。

［1］朱耀麟，李倩.视频检索常用的镜头分割方法的研究［J］.电视技术，2014（3）：178-181.

［2］陶明明，周源华.一种基于亮度帧差的自适应镜头边界检测算法［J］.电视技术，2004（12）：62-65.

［3］刘政凯，汤晓鸥.视频检索中镜头分割方法综述［J］.计算机工程与应用，2002（23）：84-87.

［4］彭波，李弼程.一种因果的突变镜头检测方法［J］.计算机工程与应用，2004（5）：91-92，114.

［5］ZHONG Y，KARU K，JAIN A K.Locating text in complex color images［J］.Analysis and Recognition，1995（1）：146-149.

［6］周艺华，曹元大，张洪欣.一种基于二次帧差的突变镜头检测方法［J］.计算机工程与应用，2005（6）：22-25.

［7］汪翔，罗斌，翟素兰，等.基于颜色空间的自适应阈值镜头分割算法［J］.计算机技术与发展，2012（9）：37-40.

［8］印勇，侯海珍.基于直方图帧差的自适应镜头分割算法［J］.计算机工程与应用，2010（9）：186-189.

A Shot Segmentation Algorithm Based on Partitioned Histogram Change Rate of Frame Difference

Chen Yitao， Gong Ningsheng， Wang Shumin
（ College of Computer Science and Technology， Nanjing Technical University， Nanjing 211816， China）

After introducing the current mainstream video shot segmentation algorithms， an adaptive shot segmentation algorithm based on partitioned histogram change rate of frame difference is proposed. The algorithm is mainly divided into two parts： abrupt change detection and gradual change detection. Firstly using the HSV partitioned histogram to calculate the frame difference of adjacent frames. Compare it with the adaptive threshold of abrupt change， and then determine the position of the abrupt change shot. Then using video segments， which is from abrupt change cut， to detect the gradual changes of video shot. Using regular pattern of neighbor frame difference change rate to determine the position of gradual change. Experimental results show that the method in this paper has high accuracy， and it is easy to implement.

HSV color model； partitioned histogram； abrupt change shot； gradual change shot； change rate of frame difference

陈逸韬（1989— ），男，江苏南京，硕士；研究方向：图像处理。

项目名称：国家重点基础研究发展计划项目；项目编号：2005CB321901。项目名称：软件开发环境国家重点开放实验室开放课题；项目编号：BUAA-SKLSDE-09KF-03。