H.264压缩域中利用Biased-SVM检测镜头边界

游运喜，张恩迪，苟志坚

湖南大学物理与微电子科学学院，长沙 410082

H.264压缩域中利用Biased-SVM检测镜头边界

游运喜，张恩迪，苟志坚

湖南大学物理与微电子科学学院，长沙 410082

1 引言

为了从海量数字视频中快速获取感兴趣的信息，产生了基于内容的视频检索技术。镜头边界检测是视频检索技术的基础，镜头是摄像头一次连续拍摄的视频帧序列，代表时间或空间上连续的一组动作。前后镜头的切换产生了镜头边界，对于观察者来说，边界是由于视频内容发生了变化产生的[1]。按照镜头切换方式不同，镜头边界可分为突变和渐变两类，突变是指镜头切换在两个视频帧间完成，中间没有过渡；渐变是指镜头切换有一个平缓的过渡，完成切换常常需要十几或几十帧[2]。镜头边界检测方法可分为基于像素域的和基于压缩域的两类。基于像素域的方法可采用的特征信息全面，所以检测精度较高；基于压缩域的方法可以直接使用压缩域的特征，不需要完全解码，所以速度较快，但是对于不同压缩编码标准需要采用不同的算法。

H.264/AVC视频编码标准具有突出的压缩性能和良好的网络亲和性，越来越多的视频采用H.264编码标准[3]。H.264编码标准引入了许多新特性，如其采用了帧内预测，DC系数不再代表平均能量，使得原MPEG压缩域DC图方法不能直接适用于H.264压缩域[4]。关于如何在H.264压缩域检测镜头边界，近几年一些学者提出了许多方法。文献[5]用I帧中帧内宏块预测模式信息来检测发生在I帧的边界，利用帧内编码宏块数信息来检测发生在P帧和B帧的边界。文献[6]根据帧内宏块比率检测出候选边界帧，再定义了帧内预测模式8个方向的直方图来确定边界帧，对于防止闪光灯的干扰有好的效果。文献[3]统计相邻帧对应宏块的帧内预测模式差异或帧间预测模式差异来检测边界，并与文献[7]相比获得了更好的性能。上面三种方法都未涉及到渐变镜头的检测。文献[8]提出了利用运动矢量和预测残差的DC系数来检测边界的方法，表明了比没有采用运动矢量和DC系数的方法有更好的性能，但其中较多的阈值选择对于检测性能影响很大。还有，文献[4]对于GOP级的场景切换检测进行了研究，文献[9]对QCIF视频的场景切换检测进行了研究。近几年来，基于机器学习的方法也应用到了压缩域的镜头边界检测上，如文献[2]将SVM应用到了MPEG压缩域的镜头边界检测上，避免了阈值选择的问题，并取得了不错的性能。

基于以上研究基础，本文提出融合H.264压缩域多特征和采用Biased-SVM分类方法的镜头边界检测方法。先根据帧类型、帧内预测模式图差异、宏块类型等特征，利用Biased-SVM将视频帧分为突变帧和非突变帧；再根据P帧的帧内宏块比率和运动混乱度[10]等特征，将非突变帧分为渐变帧和非镜头边界帧；最后根据渐变帧一般延续十几帧以上的特点，对渐变帧进行修正。

2 H.264压缩域中镜头边界的特征

2.1 突变边界特征

H.264视频中一个编码图像由若干宏块组成，宏块可分为帧内预测编码宏块和帧间预测编码宏块两种。帧内宏块利用图像空间上的相似性进行预测编码，帧间宏块利用相邻帧之间的相似性进行预测编码。根据预测方向的不同，帧间宏块可分为前向预测宏块、后向预测宏块、双向预测宏块。I帧只有帧内预测宏块，P帧有帧内预测宏块和前向预测宏块，B帧有帧内预测宏块、前向预测宏块、后向预测宏块、双向预测宏块。

当出现突变镜头边界时，新镜头的第一帧，也即突变帧，与其前面帧的相似性很小，所以突变帧会主要采用帧内预测宏块或者后向预测宏块。同理，前一镜头的最后一帧会主要采用前向预测宏块或帧内宏块。

设itrar，frontr，backr，bidr分别为帧内预测宏块，前向预测宏块，后向预测宏块，双向预测宏块在一帧内所占比例。图1和图2所示为突变边界出现在视频帧序列中不同位置的情况。先看图1所示的三种情况，虚线箭头表示相应方向上的预测宏块比例减少：

（1）如图1（a），突变出现在I帧或P帧和B帧之间，此时B1帧的frontr会大幅减少，itrar和backr增加。

（2）如图1（b），突变出现在两个B帧之间，此时B2帧的backr大幅减少，而itrar和frontr增加；B3帧的frontr大幅减少，itrar和backr很大。

（3）如图1（c），突变发生在B帧和P帧或I帧之间，这样B4帧的backr少，itrar和frontr大，P帧的frontr也很少。

图1 突变出现在可以用宏块类型检测的位置

图2 突变出现在不能用宏块类型检测的位置

所以可以用itrar，frontr，backr和bidr特征，来检测出上面三种突变边界。

再看如图2所示的情况，如图2（a）所示，突变出现在P帧之后和I帧之前时，不能根据frontr和backr的减少来检测边界，因为P帧没有后向预测宏块，I帧只有帧内宏块；图2（b）所示，突变边界出现在IDR帧之前时，IDR帧（立即刷新帧）的出现打破了预测链，IDR帧和I帧同属于帧内编码帧，可以将其看成是特殊的I帧，不同的是，IDR帧之后的帧不会参考它之前的帧预测编码，反之，IDR帧之前的帧也不会参考它之后的帧预测编码，所以不能根据B5帧的后向预测宏块减少来检测突变边界。

H.264中帧内宏块有4×4子块和16×16块两种分割尺寸，第一种分割模式适合于多细节的图像区域，而后一种模式适合编码平坦的区域。所以I帧的宏块尺寸分割信息代表了其内容的细节。比较两个I帧的宏块分割模式分布情况，它们之间的内容变化可以被检测到，所以针对突变帧出现在I帧的情况，较多的文献采用直接比较两个I帧的分割模式差异[3-4，6]来检测边界。这种方法不可靠，因为两个I帧之间还有许多P帧和B帧，内容可能已经发生了很大的变化。文献[7]和文献[11]定义了帧内分割模式图（intra partitioning map），图从第一个I帧开始记录每帧的帧内宏块分割模式，后续帧中遇到帧内宏块，就将图内对应宏块的分割模式更新。然后将I帧的帧内分割情况与前一帧的帧内分割图的情况比较，将差异和阈值比较来判断是否发生了突变。采用这种方式的不足是，物体或摄像头的运动或导致误检测。

I帧中4×4亮度块有9种预测模式，16×16亮度块有4种预测模式，共有13种预测模式。不同的预测模式描述了不同的纹理结构，例如垂直预测模式适合编码具有垂直边缘的宏块。本文定义帧内预测模式图，根据I帧和其前一帧的帧内预测模式图的差异，来检测发生在I帧的突变边界。帧内预测模式图用矩阵M记录每帧的等效帧内预测模式：式（1）中amn为图像中4×4宏块的预测模式，16×16宏块可看成16个预测模式相同的4×4宏块。M从第一个I帧开始记录帧内预测模式，后续帧中遇到帧内宏块，就将M中对应宏块的预测模式更新。

用变量m（k=0，1，…，12，对应13种预测模式）表示

这样，可以根据I帧和其前一帧的Ω来检测发生在图2所示位置的突变边界。

综上所述，提取的突变边界的特征有：itrar，frontr，backr，bidr，Ω和帧类型ftype。

本文构造的特征Ω，利用矩阵M记录对应帧的等效帧内预测模式图，避免了要直接比较两个跨度大的I帧的缺点，同时采用比较两个相邻帧M的预测模式直方图的方式，而不是对应宏块进行比较，抗干扰性能提高。将Ω和其他几个特征融合在一起，也更有利于检测发生在P帧和B帧的突变。第i帧M中预测模式为k的4×4宏块数。计算前后帧M的预测模式直方图差异如式（2）。

2.2 渐变边界特征

渐变镜头边界会延续十几帧至上百帧，而P帧的间隔一般在5帧以内，典型的编码序列为IBBPBBP…，P帧间隔为2帧，所以选择先在P帧层检测渐变边界。当出现渐变边界时，连续多个P帧的帧内预测宏块比例itrar较大。如图3所示为anni005视频中第1 010号到1 130号P帧中itrar的变化情况，当渐变镜头边界出现时，连续P帧的itrar会呈现一个峰值区域。设置一个长度为N帧的滑动窗口，选取N=7，当前帧处于窗口的中心，可以根据这个窗口内P帧的itrar特征，来判定当前帧是否属于渐变帧。

图3 渐变过程中帧内宏块比例的变化

只根据帧内宏块比例一个特征来判断渐变，还不够准确，因为当视频内容中有物体运动或摄像头运动时也会造成帧内宏块数上升。文献[7]提出了将图像分割为前景和后景，再根据前景和后景的运动活性度来排除运动干扰的方法，但前后景分割的计算量大。渐变主要有淡入/淡出，慢转换和扫转换几类。淡入/淡出和慢转换的运动很小，全局一致性运动为零，扫转换整体向一个方向运动，具有运动的一致性[10]。文献[10]根据渐变运动的一致性特点，定义了运动混乱度来排除运动的干扰。用mchaosi表示第i帧的运动混乱度，mchaosi的计算如下：

其中MN为一帧中4×4子宏块数，mvxj和mvyj表示第j个4×4子宏块对应的运动矢量。

如图4所示为anni005视频中第1 550号到1 630号P帧中itrar和mchaos的变化情况，当mchaos很大时，即使出现了itrar峰值区域也不是渐变边界。

图4 渐变过程中运动混乱度的特征

所以要提取的渐变特征有连续N个P帧的itrar，mchaos。

本文选用前后连续N个P帧的itrar，mchaos作为渐变特征，避免了只采用连续几个P帧的帧内宏块比例作为特征的缺点。在避免物体或摄像头运动干扰的方法上，与文献[7]的方法比，mchaos的提取，比分割前后景和计算运动活性度的复杂度低很多。与文献[10]的差异在于，文献[10]将I帧的DC系数和mchaos结合来检测渐变，而DC系数提取的复杂度接近完全解码。

3 利用Biased-SVM检测镜头边界及修正

3.1 Biased-SVM

SVM（支持向量机）是根据统计学习理论中的结构风险最小化原理提出的机器学习方法，通过调节分类决策函数，构造最佳分类超平面，对有限样本分类问题具有独特优势，且具有较好的泛化能力。不平衡数据集是指数据集中某一类数据远小于其他类数据，如视频帧序列中属于镜头边界的帧数远少于不属于边界的帧数。在处理不平衡数据分类时，SVM方法遇到的主要问题是分类面会靠近少数类，从而容易错分少数类[12]。Biased-SVM模型[13]对于正负类样本数据采用不同的惩罚因子，来解决处理不平衡数据的分类问题。给定正类样本数据的惩罚因子为C+，负类样本数据的惩罚因子为C-，负类为多数样本数据，正类为少数样本数据。这样，SVM的目标函数变为式（6）[13]。

为求解式（6）的二次规划问题，可得到它的等价对偶问题如式（7）。当给定的多数类的惩罚因子小于少数类惩罚因子时，分类面就会靠近多类数据[12]。

关于参数C+和C-的设定，文献[14]提出了多数类与少数类惩罚因子的比例等于少数类与多数类样本的比例的方法。文献[13]对于惩罚因子C-和C+的选取进行了研究，提出了使用样例平均密度选取参数的方法。本文采用文献[14]的思想先确定C-和C+值的范围，再通过交叉验证对C-和C+进行遍历式的参数调优，直到正负类样例都取得最佳准确率。正负类准确率都取得最佳的评价标准的计算如式（8），这也是不平衡数据集研究中广泛采用的评价标准[13]。

式（8）中acc+和acc-分别为正类样本和负类样本的分类正确率。

3.2 镜头边界检测

首先构造特征矢量。根据上面描述的突变边界特征，从H.264视频帧中提取的突变边界的特征矢量为xcut=(itrar，frontr，backr，bidr，Ω，ftype)，考虑到每帧是否为镜头边界帧与其前后帧联系紧密，选用连续5帧的滑动窗口，窗口中心为当前帧，这样对于当前帧可以构造一个30维的突变特征矢量，如式（9），i为第i帧。根据渐变边界特征，提取的特征矢量为xgra=(itrar,mchaos)，同样建立长度为7帧的窗口，窗口中心为当前帧，对于当前帧构造一个14维的渐变特征矢量，式（10）为渐变边界的特征矢量。

然后，训练突变边界分类器SVM1和渐变边界分类器SVM2。选用典型的H.264视频段构成训练视频集，从这些训练视频的H.264码流中，提取出(，)构成样本集，来训练SVM得到分类突变帧的SVM1模型，=+1为突变边界帧，也即为正类样本，=-1为非突变边界帧，也即为负类样本，i=0，1，…，l，l为训练样本个数即帧数；提取出样本集(，)，训练SVM得到分类渐变帧的SVM2模型，=+1为渐变边界帧，=-1为非边界帧。具体训练SVM的样本选取及参数的设定在第4章给出。

最后用SVM1和SVM2分类出突变帧和渐变帧。图5所示为利用SVM检测镜头边界的过程。先从H.264视频帧提取突变边界特征，利用SVM1模型将视频帧分为突变帧或非突变帧；如果非突变帧为P帧，则提取渐变边界特征，利用SVM2将非突变帧分为渐变帧或非边界帧。

图5 利用SVM检测边界帧的过程

3.3 镜头边界修正

利用SVM模型分类得到的边界帧，需要修正以减少误捡和漏检，还有渐变边界帧是在P帧层检测的，得到的渐变帧不连续。修正步骤如下：

（1）在P帧层，如果前后两个渐变帧的间隔小于等于2帧，则将它们中间的间隔帧改为渐变帧，若中间的帧为突变帧则保持不变。

（2）在P帧层，在步骤（1）后，如果连续的渐变帧数小于等于2，则将这1或2帧渐变帧改为非边界帧。

（3）上面两步之后，将两个渐变帧之间的非P帧改为渐变帧，其中若有突变帧则保持不变。

（4）最后，若连续的渐变帧中间有突变帧，则保留突变帧，将这些连续的渐变帧改为非边界帧。

4 实验结果分析与对比

实验平台及数据介绍：实验的PC机配置为Pentium®双核，2.7 GHz，2.00 GB内存。SVM的实现是基于LIBSVM的C-SVM，核函数选择RBF核函数。为了测试所提算法的性能及方便与其他算法比较，选择了TRECVID-2001视频集中的部分视频进行实验。这个视频集中的视频是MPEG压缩格式的，进行实验前，先将选取的视频重新编码成H.264格式的。编码参数为：main profile，30 frame/s，I帧周期为60，帧序列结构为IBBPBBP…。

4.1 样本选取及参数设定

SVM训练的样本选取和参数设定：选取bor08，nad53，senses111三个视频段用做训练SVM模型用的视频集，其中bor08共有50 569帧，含有375个突变和153个渐变；nad53共有25 783帧，含有81个突变和77个渐变；senses111共有86 789帧，含有292个突变和16个渐变。

训练SVM1模型：选取RBF核函数参数g=1/d，d为特征维数，得g1=0.033。从三个视频段中提取得到三个样本集，每次选择一个样本集作为测试集，剩下的作为训练集，用K交叉验证法和网格法，寻找取得最佳a_mean时的惩罚因子用确定的最优参数g1，和，在三个样本集一起构成的训练集上训练SVM得到最终的SVM1模型。

4.2 算法检测性能

算法性能测试：为了与文献[15-16]进行比较，选取了视频集中的anni005，anni009，bor03三个视频作为测试视频，来测试所提算法的性能。常用查全率、准确率两个标准来评价镜头检测算法的性能。为了综合评价检测性能，还采用了式（13）定义的指标F。的问题。在图6中，与其他方法的综合指标F进行了对比，总体上有更好的性能。

表2 与其他算法性能的对比（%）

图6 与其他算法的综合指标F对比

其中，Nc为正确检测到的边界数；Nm为漏检的边界数；Nf为错误检测的边界数。

表1列出了测试视频的镜头边界信息和所提算法的检测性能信息。总体上突变边界的检测性能比渐变边界的性能高很多，anni009视频中含有较多的渐变镜头边界，其中部分渐变帧，尤其是具有明显光照变化的渐变边界帧被误检为突变帧，影响了突变边界的检测性能。bor03视频中渐变镜头所占比例很少，少数的误检在式（12）中也会得到较低的准确率，所以出现了一个很低的准确率。

表1 测试视频特征及本文算法检测性能

表2是与其他同类算法的检测性能对比表。表2中的查全率和准确率，是将突变和渐变放在一起计算得到的。文献[3]算法的数据是通过重复其算法计算得出的，文献[15]和文献[16]算法的数据是通过读取文献[15]中的结果图得到的。文献[3]算法的查全率高，但检测准确率低。与文献[15]和文献[16]算法对比，在含有较多渐变边界的视频anni005和anni009上比较，本文算法有更高的准确率，但由于镜头边界修正的第（4）步将一些渐变边界误判为突变边界，使得anni009上的查全率较低。文献[15]和文献[16]算法可以调节阈值的参数，所以适合检测突变边界较多的视频bor03，本文算法在bor03视频上的准确率低些。从上面的比较可以看出，本文算法在检测渐变边界方面有更好的性能，突变边界方面也有不错的性能，同时没有阈值选择

4.3 计算复杂度

所提算法的复杂度，包括特征矢量的提取和边界分类两个过程。itrar，frontr backr，bidr，ftype，mchaos的提取主要是判断语句和一些简单的统计运算，Ω的提取虽然用到了矩阵，但没有矩阵的乘除等复杂运算。所以特征提取过程的时间复杂度为O(l)，l为要处理的视频帧数，空间复杂度为O(1)。SVM分类的时间复杂度为O(l·nsv)，空间复杂度为O(nsv)，nsv为支持向量个数，SVM模型训练好之后，nsv是个常数。所以本文算法时间和空间复杂度分别为O(l·nsv)+O(l),O(nsv)+O(1)。在特征提取阶段，其他H.264压缩域的检测算法复杂度与本文区别不大，因为提取宏块类型，预测模式，运动矢量等信息的过程一样，只是由这些信息构成特征时不同算法有所不同。复杂度的区别在于，本文采用了SVM分类，而其他文献采用阈值或动态阈值来分类。文献[3]，文献[15]和文献[16]算法的时间和空间复杂度分别为O(l)+O(l),O(1)+O(1)。本文的复杂度高些。

由于特征的提取是在H.264/AVC的参考软件JM8.6的ldecod上实现的，ldecod的后续解码会影响本文算法的时间消耗统计，所以不能给出完整算法的时间消耗情况。这里给出SVM分类阶段的时间消耗情况：在anni005视频上实验，SVM分类时间消耗为9.51 s，在anni009上为7.78 s。而用JM8.6完全解码这两个视频消耗的时间分别为1 516.34 s和1 582.34 s。在特征提取阶段不需要进行运动补偿，反余弦变换等一些在解码过程中非常耗时的运算，所以耗时很小。可以得出的结论是，本文算法的时间消耗远小于完全解码的时间消耗。

5 结束语

本文将Biased-SVM应用到H.264压缩域检测镜头边界上，避免了阈值选择的问题，融合了帧类型、宏块类型、运动矢量、帧内预测模式和帧内宏块比率等多个特征，提高了检测性能。在TRECVID视频集上实验，与其他3个H.264压缩域的算法比较，所提算法的渐变边界检测性能明显较好，综合性能也更好。但是SVM模型的训练对于检测性能和泛化能力影响很大，所以需要进一步研究SVM模型的训练，参数的选择，以及更多类型渐变边界的检测。

[1]陈萍，李秀强，肖国强，等.基于视觉注意特征和SVM的镜头边界检测算法[J].计算机工程与应用，2010，46（7）：184-186.

[2]曹建荣，蔡安妮.压缩域中基于支持向量机的镜头边界检测算法[J].电子学报，2008，36（1）：203-208.

[3]夏定元，谢慧琳.一种在H.264/AVC压缩域中检测镜头边界的方法[J].中国图象图形学报，2009，14（12）：2595-2598.

[4]高宇，卓力，王素玉，等.一种基于H.264/AVC压缩域的GOP级视频场景转换检测算法[J].电子学报，2010，38（2）：382-386.

[5]Zeng W，Cao W.Shot change detection on H.264/AVC compressed video[C]//IEEE International Symposium Oil Circuits and Systems，2005：3459-3462.

[6]Hong B，Eom M.Scene change detection using edge direction based on intra prediction mode in H.264/AVC compression domain[C]//2006 IEEE Region 10 Conference，TENCON 2006，2006：1-4.

[7]Bruyne S D，Deursen D V，Cock J D，et al.A compresseddomain approach for shot boundary detection on H.264/AVC bit streams[J].Signal Processing：Image Communication，2008， 23（7）：473-489.

[8]Yu Z Y，Lin Z P.Scene change detection using motion vectors and DC components of prediction residual in H.264 compressed videos[C]//7th IEEE Conference on Industrial Electronics and Applications，2012：990-995.

[9]南哲万，阮秋琦.一种新的H.264视频场景切换检测算法[J].计算机工程与应用，2011，47（8）：1-3.

[10]龚声蓉，范益进，周翔.一种基于H.264/AVC码流的镜头边界检测方法[J].小型微型计算机系统，2007，28（4）：688-691.

[11]Bruyne S D，Cock J D，Poppe C，et al.Compressed-domain shot boundary detection for H.264/AVC using intra partitioning maps[C]//17th International Multimedia Modeling Conference，2011：29-39.

[12]王和勇，樊泓坤，姚正安.SMOTE和Biased-SVM相结合的不平衡数据分类方法[J].计算机科学，2008，35（5）：174-176.

[13]金鑫，李玉鑑.不平衡支持向量机的惩罚因子选择方法[J].计算机工程与应用，2011，47（33）：129-133.

[14]Akbani R，Kwek S，Japkowicz N.Applying support vector machines to imbalanced datasets[C]//15th European Conference on Machine Learning，2004：214-220.

[15]Feng J，Huang A A，Chen Y W.A novel scene change detection algorithm for H.264/AVC bitstreams[C]//Pacific-Asia Workshop on Computational Intelligence and Industrial Application，2008：712-716.

[16]Kim S M，Byun J W，Won C S.A scene change detection in H.264/AVC compression domain[C]//6th Pacific Rim Conference on Multimedia，2005：1072-1082.

YOU Yunxi,ZHANG Endi,GOU Zhijian

School of Physics and Microelectronics Science,Hunan University,Changsha 410082,China

In order to detect shot boundaries in H.264 bit streams,a shot boundary detection method using compressed domain features of H.264 and Biased-SVM（Biased Support Vector Machine）is proposed.The features about the abrupt shot changes and gradual shot changes are obtained by analyzing the information of frame type,macroblock type,motion vector,intra-prediction mode,etc.As the number of shot boundary frames is far fewer than the total number of video frames,proposed method chooses Biased-SVM to classify the frames into three classes,namely,the frames of abrupt change,gradual change and non-change.Experimental results on TRECVID video dataset indicate that the presented approach has better performance on shot boundary detection, compared with other method in H.264 compressed domain.

shot boundary detection;H.264 compressed domain;biased Support Vector Machine（SVM）

为了直接从H.264码流中检测镜头边界，提出了利用H.264压缩域多特征和Biased-SVM（不平衡支持向量机）分类算法的检测方法。分析帧类型、宏块类型、运动矢量、帧内预测模式等信息，以获得发生镜头突变和渐变的特征。针对镜头边界帧的数量远少于视频帧总数的特点，用Biased-SVM分类方法将视频帧分为突变帧、渐变帧和非镜头边界帧。在TRECVID视频集上的实验结果表明，与其他H.264压缩域的算法相比，该算法有更好的性能。

镜头边界检测；H.264压缩域；不平衡支持向量机

A

TP391.41

10.3778/j.issn.1002-8331.1307-0192

YOU Yunxi,ZHANG Endi,GOU Zhijian.Shot boundary detection using Biased-SVM in H.264 compressed domain. Computer Engineering and Applications,2013,49（24）：138-143.

国家科技支撑计划资助项目（No.2012BAD35B06）。

游运喜（1988—），男，硕士研究生，研究领域为数字图像处理；张恩迪（1964—），男，高级工程师，研究领域为信号处理；苟志坚（1986—），男，硕士研究生，研究领域为数字图像处理。E-mail：youyunxi@qq.com

2013-07-15

2013-08-29

1002-8331（2013）24-0138-06

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.003.html