一种基于支持向量机的镜头边界检测算法

常虹，张明（上海海事大学信息工程学院，上海　201306）

一种基于支持向量机的镜头边界检测算法

常虹，张明
（上海海事大学信息工程学院，上海201306）

以往镜头边界检测对阈值的依赖性很大，提出一种基于支持向量机的镜头边界检测算法来避免对镜头检测阈值的依赖。该算法利用SVM对视频数据进行分析和处理，把从视频像素帧中提取的特征数据作为支持向量机的输入数据，从而把镜头边界检测问题转化成分类问题。有效地将镜头边界检测跟机器学习的方法结合起来，实验表明这种方法对镜头边界检测的切变检测有很好的检测效果。

视频检索；镜头边界检测；支持向量机

0　引言

镜头边界检测在研究基于内容检索、视频数据库及视频处理和利用上具有十分重要的作用。现有的视频镜头边界检测算法大多是基于视频帧间的内容变化的。通常把具有较明显的连续差异比较大的相邻两帧看作视频镜头的边界。镜头边界分为突变和渐变。为了有效地分割镜头定义了连续两帧图像的相似性特征量。如果相邻两帧相似性较大，就认为两帧位于同一个镜头中，如果相邻两帧相似性很小，就认为在这两帧间发生了镜头突变。镜头检测的整个过程可以分为3个阶段［1］：（1）提取特征；（2）构造帧间差值；（3）镜头边界检测。视频镜头边界检测算法的分类可以按照其使用的帧间差别特征进行分类，也可以按照算法的应用对象进行分类。还有些算法按照视频是否压缩进行分类，大部分算法是用于像素域的视频镜头检测。像素域中的镜头边界检测方法主要有：基于像素块比较的方法；基于像素比较的方法；全局直方图比较的方法；基于模型分割等的方法。在镜头边界检测的方法中，早期主要采用固定阈值的方法［2］，但固定阈值的镜头边界检测对于阈值的设定过于敏感。除非选取恰当的图像特征计算出来的自适应阈值。近些年，有许多机构和研究者用机器学习的方法进行镜头边界检测，如Lee等［3］人提出利用压缩域中特征，并结合神经网络进行镜头边界检测，取得不错的效果，AT&T利用像素域中提取的图像特征，结合有限状态机进行镜头边界检测。因此，用机器学习的方法进行镜头边界检测是目前的一种很具有研究价值的发展趋势。

本文提出一种改进的基于支持向量机的镜头边界检测算法。首先提取HSV颜色空间中的颜色直方图和纹理特征算子组合成的特征算子作为特征数据，其后结合支持向量机进行镜头边界检测。本文首先介绍了镜头检测过程中用到的颜色空间转换和帧间差值的计算方法，在此基础上设计了基于支持向量机的镜头切变识别算法。最后给出TREVID 2007数据集上的测试结果。该算法的实验结果与TREVID 2007公布的评测结果进行对比后，镜头边界检测准确率有了明显提高，试验结果表明了该算法的有效性。

1　颜色模型转换和帧间差值的计算

1.1颜色模型转换

HSV颜色模型

HSV颜色模型是色调（H，Hue）、饱和度（S，Saturation）、亮度（V，Value）三个英文单词的首字母缩写［4］，这一点与RGB颜色空间模型类似，然而HSV颜色模型与人类视觉的特点更相符，其模型采用上述三个方面来描述现实世界中各种各样的颜色。在一幅图像中，色调代表图像颜色的一个总体倾向，可以是各种各样的颜色，包含红色、绿色、蓝色等；所谓饱和度，是指一幅图像中图像色彩的鲜艳程度；而亮度则是指图像所具有颜色的明亮程度的反映。

由于HSV颜色模型具备有线性伸缩性的性质，所以人们比较倾向于HSV颜色模型所描述的颜色［5］。然而在一般情况下，我们得到的图像绝大部分都采用RGB颜色空间模型来进行描述，由此需要把RGB颜色空间转换成HSV颜色空间。在转换公式中，r，g，b的取值是从0到255。h采用弧度制来进行表示，其范围为0度到360度，s，v的取值是0到1，h，s，v是通过非线性变换得到的如下：

1.2图像特征提取

为了能有效进行基于SVM的分类，选取合适的分类特征参数也是很重要的。目前，较普遍的使用方法是颜色直方图，本文选用一种将每一帧的HSV颜色空间中的颜色直方图和纹理特征因子组合而成的特征因子作为视觉特征。

（1）纹理特征

在对图像帧处理的过程中，如果仅仅是以颜色特征作为特征提取的参数，对于种类繁多的视频资源来说，显得过于单一，所以，本文在原本的颜色特征的基础上，引入纹理特征算子。

本文利用LBP［6］（局部二值模式）纹理特征描述算子来对帧图像的纹理特征进行处理。LBP描述算子具有的灰度不变和旋转不变的性质很巧妙的避免了由光照或闪光显著改变而引起的实验结果的误差。

LBP算子的主要思想是选取区域的中心像素并把它的灰度值设为阈值，然后，再对周围圆形邻域内的像素进行二值化处理，也就是将周围半径为R的圆形邻域内的像素灰度值与阈值作比较，若像素值大于阈值则此邻域的像素值为1，反之为0，由此可得一串二进制的值，最后对不同位置的像素值进行加权求和，就可以得到该区域的LBP值。表示半径为R的圆形邻域内存在P个像素点。

图1　基本的LBP算子计算示意图

用公式可以表示为：

其中，P表示半径为R的圆形邻域内存在P个像素点。bi为像素点的像素值，bc为中心点的像素值.。若bi-bc的值大于0，则s（x）的值为1，反之，s（x）值为0。

（2）颜色直方图

本文研究过程中，必需对整个HSV颜色模型进行量化，量化之后再进行后续计算，以便有效降低计算量。本文选择对HSV颜色空间进行非等间隔的量化，分色调H为8份，饱和度S和亮度V为3份，采用的公式如下：

经过量化之后，依据如下方法将H、S、V合成一个一维矢量，这样就把HSV颜色空间划分为72种颜色，然后就可以进行特征提取了：

首先进行颜色直方图的提取，颜色直方图反映了一幅图像中像素颜色出现的概率，是一种概率统计，计算公式如下：

上式中，Wi（k）指的是第i幅图像的第k种颜色集合出现的概率，Dk指的是第k种颜色集合，图像中的像素点用M和N表示，即图像有M行N列，表示了这幅图像的大小。

1.3帧间差值计算

在镜头边界检测算法中，非常普遍的使用方法是颜色直方图法，它是分别对两幅相邻的图像进行颜色直方图提取，再对两者的直方图进行归一化，计算两幅相邻图像的帧间差，换句话说就是计算直方图间的相似性，最后通过差值比较的方法来对镜头的边界进行判断。

因为本文是利用颜色特征和纹理特征共同来对帧图像进行描述［7］，所以，两帧之间的相似度可以用二者差值来表示。在本文中，首先计算两帧图像之间的颜色直方图的差值，再计算两帧图像之间的LBP纹理算子的差值，再将这两个差值进行加权计算，最后得到的总差值即可表示为两帧之间的相似度，差值越大，则两帧之间相似度越大，反之，相似度越小。

其中，I代表帧图像，C代表帧图像的颜色直方图矢量值，V代表采用LBP纹理算子方法计算得到的纹理特征值，D（CC，Cc+1）和D（VC，Vc+1）则可以分别表示两帧图像的颜色特征及纹理特征的归一化相似度，数值越大，说明相似度越低，w1，w2分别代表颜色相似度以及纹理相似度的权重，且满足权值关系：w1+w2=1，在本文的实验中，w1和w2均取值0.5。

在这里设相邻两帧颜色直方图的结果分别为Cc和Cc+1，N为直方图的Bin数，两直方图的相似性用D （CC，Cc+1）表示，帧间差的常见的计算方法如下：其中，Cc（k）在颜色直方图里表示的是第k个Bin出现的频率，D（CC，Cc+1）的值越大表示相似程度越高。

2　改进的基于支持向量机的镜头边界检测算法

2.1帧间SVM原理

支持向量机（Support Vector Machine，简称 SVM）［8］是一种机器学习的技术，它建立在统计学习理论中VC维理论和结构风险最小原理的基础之上，由Vapnik在20世纪90年代提。如今已应用到科学研究的各个领域，如人脸识别、图像分类以及语音识别等。现实世界的分类问题一般可以分为线性可分问题与线性不可分问题，虽然SVM是由线性可分问题发展而来的，但目前也可以较好地解决现行不可分问题。

线性可分问题就是说可以用一条直线将样本数据分隔成两个不同的类，而支持向量机的作用即在多条可分的平面中确定一个最优的平面使得两个分类的间隔最大化。假设一个n维空间线性可分的样本集为｛（xi，yi），i=1，2，…，n，x∈Rn，y∈｛-1，1｝｝，n维空间的线性判别函数为g（x）=wx+b，当分类超平面wx+b=0可以成功划分样本集，且两类样本点距离分类面的距离间隔最大时，此分类超平面就是最优超平面，距离最优超平面最近且与其平行的样本即为支持向量。

在支持向量机中，用来解决非线性可分问题的主要思想是将非线性不可分问题通过核函数映射到高维空间，使其在高维空间线性可分，然后在高维空间中寻找最优超平面作数据分类。常见的核函数有以下三种：

（1）多项式核函数（Poly）：

K（x，y）=（（x·y）+c）d，其中参数c取值未1。

径向基核函数（RBF）：

（3）Sigmoid核函数：

K（x，y）=tan（v（x·y）+c），其中，v＞0，c＜0。

支持向量机划分为输入层、隐含层和输出层。输入层主要功能是接受数据，隐含层实现低维空间到高维空间的映射并且计算特征向量与支持向量的内积，输出层则负责提供分类结果。

2.2改进的算法描述

由于SVM对核函数类型以及参数很敏感，所以构造最优参数的核函数才能保证SVM分类器识别的准确率。本文提出一种对相应SVM进行交叉对比训练的方法来得到最优的参数C与r。算法描述如下：

（1）计算各镜头特征值的平均值以及利用滑动窗口法计算各窗口的边缘比率

假设一个镜头中有N帧｛f1，f2，f3，…，fn｝，利用公式（9）计算出相邻两帧之间的帧差序列K=｛K1，K2，K3，…，Kn-1｝。在针对各镜头帧差进行计算后，需要计算各镜头特征值的平均值来代表镜头的特征值，这里，定义Kij为第j镜头的第i个帧差计算如下：

（2）通过上面公式（12）、（13）、（14）计算，构造7维特征向量

（3）构造SVM

首先将上述特征向量xi作为输入变量输入SVM，在对训练数据进行归一化后，通过训练得到4×（4-1）/2个二元分类的支持向量机，每一个训练集训练一个分类器。然后对训练数据集进行交叉对比训练，得到最优的核函数参数。再利用得到的决策函数进行投票，票数最多的镜头类型即为测试镜头的类型，最后实现视频镜头的分类。支持向量机核函数选用RBF函数：

（4）利用支持向量机的判别函数进行突变镜头检测

给定特征向量xi，则支持向量机的判别函数为：

式中sv是支持向量的个数，K（x，y）为核函数。

最后基于机器学习得到的模板进行镜头边界分类，进一步的工作是选取合适的特征矢量来描述不同的边界。

3　实验结果及分析

3.1数据的来源

本文的数据集为TREVID 2007数据集。实验数据集分为测试集与训练集，通常比例为1∶4，这样可以使建立模型在大量的训练集中得到完善，使得最后的实验结果更具有说服力。

3.2评测标准

本文采用查全率以及查准率的评价标准，其定义如下：

根据视频内容的不同选取体育、电影、广告、纪录片4种题材的视频片段作为样本进行了大量的实验。说明了本文的算法的有效性，实验结果如1与表2所示。

表1　本文方法实验结果

表2　TREVID 2007数据集中的实验结果

通过以上两个表的实验结果我们知道，本文提出的基于SVM的方法对于视频的镜头边界检测有着较高的查全率与查准率。同文献中方法进行比较，本文提出的算法在避免漏检和误检方面有很好地效果。

下图是在Window 7系统下，采用MATLAB 2010b实现的其中一小段纪录片运用本文提出的基于支持向量机的镜头边界检测算法的结果，以及文献中方法给出的结果对比图如下：

图1　本文方法的镜头检测结果

从结果的对比中我们可以看出TREVID 2007数据集中的方法敏感性较强，把镜头内物体的运动误判为发生了镜头突变，导致提取的镜头出现重复，而本文提出的算法能够有效地避免误判，从而说明本文算法的有效性，以及优越性。

图2　文献中方法的镜头检测结果

4　结语

本文提出了一种改进的基于支持向量机的镜头边界检测算法，消除了镜头边界检测对阈值的依赖。它运用机器学习中的支持向量机有效的实现利用SVM对视频数据进行分析和处理，从而把镜头边界检测问题转化成了分类问题。有效地实现镜头边界检测，实验表明这种方法对镜头边界检测的切变检测有很好的检测效果。

［1］巢娟，蒋兴浩.基于双重监测模型的视频镜头分割算法［J］.上海交通大学学报，2011∶1542-1546.

［2］文军，谢毓湘，老松杨.足球比赛视频中的精彩镜头分析方法［J］.计算机工程，2004∶159-161.

［3］Liu Z，Gibbon D，Zavesky E，et Al.AT&T Research at TRECVID2006［C］，2006.

［4］姜慧.网球视频中场地广告牌检索关键技术的研究［D］.上海海事大学，2011.

［5］Geng Yuliang，Xu De，Feng Songhe.A Repid and Effective Method for Shot Boundary Detection［J］.Acta Electronica Sinica，2006，34 （12）∶2272-2277.

［6］王玮，黄非非，李见为，冯海亮.使用多尺度LBP特征描述与人脸识别［D］.光学精密工程，2008∶697-704.

［7］陈建斌.图像特征提取及其相似度的研究和实现［D］.西安电子科技大学，2012.

［8］邓乃扬，田英杰.数据挖掘中的新方法——支持向量机［M］.北京科学出版社，2004.

Video Retrieval；Shot Boundary Detection；Support Vector Machine

An Algorithm of Video Shot Boundary Detection Based on SVM

CHANG Hong，ZHANG Ming
（College of Information Engineering，Shanghai Maritime University，Shanghai201306）

Proposes an improved shot boundary detection algorithm based on Support Vector Machine，which is not dependent on the threshold.The algorithm makes use of SVM to analyze and process the video data，the feature extracted from the video frame is used as the input data of SVM，thus，the shot boundary detection problem is transformed into a classification problem.The shot boundary detection and machine learning effective combination，experimental results show that this method has a good effect on the mutation detection of shot boundary detection.

1007-1423（2016）20-0073-05

10.3969/j.issn.1007-1423.2016.20.015

常虹（1990-），女，江苏徐州人，硕士研究生，研究方向为机器学习、自然语言处理、模式识别等

张明（1957-），男，博士，教授，研究方向为多媒体信息处理、分布式多媒体技术、多媒体数据库、视觉信息检索与分析、网络信息安全、人工智能、航运信息化技术等

2016-04-21

2016-07-10