基于块匹配运动估计的视频场景切换检测算法

段淑玉 陈艳

摘 要：提出一种应用于帧率提升系统的，根据内插帧各匹配块的均值SAD为检测依据的场景切换检测算法，解决场景切换时ME/MC算法因匹配失误产生严重块效应的问题.将当前内插帧的均值SADcurr与前面已生成的内插帧的均值SADpre相除，所得商与经验阈值进行比较，若大于经验阈值则判定发生场景切换；否则，没有场景切换.帧率提升系统根据判定结果选择不同的算法产生内插帧.实验结果表明；与传统的检测算法相比，本文算法在场景切换检测的准确率上有明显的提升.

关键词：场景切换检测；块匹配；运动估计；帧率提升

中图分类号：TP317.4 DOI：10.16375/j.cnki.cn45-1395/t.2018.04.015

0 引言

场景切换是视频中较为常见的特征，场景切换检测是数字视频后处理中的关键技术之一.在时域降噪、视频编码、基于运动估计运动补偿的帧率提升等应用中，准确检测场景切换对降噪效果、编码效率、内插帧质量等具有明显的改善作用.目前较为流行的场景切换检测算法主要有灰度分割法[1]、直方图分割法[2]、边缘分割法[3]、基于DCT系數的检测法[4]、基于运动矢量的检测法和基于宏块编码类型的检测法[5]等，其中应用最为广泛的属灰度分割法和直方图分割法.方宏俊等[6]在直方图和平均亮度检测法的基础上提出一种适配分辨率动态变化的低复杂度场景切换算法，在视频源分辨率发生变化时保持较低的错判率；刘辉等[7]将场景切换检测应用于HEVC码率控制中来提高视频编码质量.

基于ME/MC（Motion Estimation/Motion Compensation）的帧率提升算法利用相邻帧之间的运动相关性进行运动估计和运动补偿[8]，产生的内插帧质量完全取决于运动估计的准确性.当发生场景切换时，相邻帧之间的相关性下降，运动估计算法失效，因此产生的内插帧会出现严重的块效应，严重影响帧率提升效果.如图1所示，图1（c）为发生场景切换时生成的内插帧，该内插帧具有严重的块效应，将造成视频的抖动，严重影响观看效果.文献[9]将场景切换应用于自适应电影源模式检测算法中，并提出多级分块χ2直方图检测算法，但复杂度过高.文献[10]采用改进的直方图检测法用于无缝自适应数字视频后处理中，并且先进行场景切换检测，再做运动估计运动补偿的帧率转换.本文利用帧率提升系统中运动估计阶段（即ME）产生的匹配块SAD值，提出以内插帧最佳匹配块SAD值的均值为判决依据的场景切换检测算法，实验表明，该算法对各种场景切换具有较好的检测效果.

1 基于块匹配运动估计的视频场景切换检测算法描述

1.1 块匹配双向运动估计算法

运动估计算法是帧率提升系统的核心部分，其目的是根据帧间的运动信息得到帧内每一个像素点的运动位移（运动矢量），运动补偿产生的内插帧质量依赖于运动矢量的准确性.基于块的运动估计是最常用的搜索算法，双向运动估计方法能克服单向运动估计方法固有的重叠、空洞问题而被广泛使用，其示意图如图2所示.其中f（n-1）和f（n+1）为前后原始参考帧，fn为内插帧，Bn为内插帧中的待插块，B（n-1）和B（n+1）为搜索到的最佳匹配块，两者位移的一半即为Bn的运动矢量.搜索最佳匹配块时用的最多的匹配准则是SAD（Sum of Absolute Difference）准则.该准则只需做减法和加法运算，硬件实现简单，运算量小，计算公式如式（1）所示.其中，M和N为匹配块大小，fc（m，n）和fr（m，n）分别为前后参考帧.

[SAD（i，j）=m=1Mn=1Nfc（m，n）-fr（m+i，n+j）] （1）

如果前后参考帧之间发生了场景切换，则使用SAD匹配准则寻找最佳匹配块的算法失效，在搜索范围内找到的SAD值最小的匹配块，并不是真正的匹配块，此时SAD值将是一个较大的值.对于整个内插帧来说，所有待插块的运动估计都是失效的，每一个待插块的最佳匹配块的SAD值都很大，所有这些SAD值求和取平均，得到的均值SAD也很大.若未发生场景切换，最佳匹配块对应的SAD值将是一个较小值，在整个内插帧中，即使存在个别待插块匹配失误（即个别SAD值较大），但对所有SAD值求和取平均后，得到的均值SAD也较小.因此内插帧的均值SAD可作为衡量是否发生场景切换的参量.

1.2 视频场景切换检测算法及步骤

对相邻两帧图像做运动估计时，如果发生场景切换，则SAD匹配准则失效，在搜索范围内找到的最佳匹配块对应的最小SAD值也将是一个较大的值.因此，本文使用当前内插帧均值SAD作为场景切换检测的基础，均值SAD计算如下：

CurrSADavg （n）=[1M×N][i=1M][j=1N]SAD（i，j） （2）

其中，[M×N]为内插帧中待插块的个数，SAD（i，j）是第（i，j）个待插块的最佳匹配块SAD值.CurrSADavg （n）不能单独作为场景切换的判断依据，但没有发生切换的场景中匹配块搜索策略、搜索范围的大小、运动物体运动的快慢都会对CurrSADavg （n）的值产生影响.为消除这种影响，应将当前内插帧的均值SAD与前面已生成的内插帧均值SAD进行比较，若与已生成内插帧的均值SAD相比，当前内插帧的均值SAD发生突变，则可判定当前内插帧处于场景切换的两帧之间.

PreSADavg（n）= α×CurrSADavg（n）+（1-α）×PreSADavg （n-1） （3）

式（3）是一个计算所有内插帧的均值SAD的加权和的过程，PreSADavg（n）与前面各内插帧的均值SAD都有关，并且离当前内插帧越近，其均值SAD对PreSADavg（n）的影响也就越大.α是权重因子，表明的是与当前内插帧的距离对PreSADavg（n）的影响，α越大则表示距离近的内插帧的均值SAD影响越大.本文实验中设置α为0.5.视频序列第一帧内插帧以及场景切换后第一帧内插帧的PreSADavg（n）就等于CurrSADavg（n）.判断当前是否发生场景切换的依据K（n）为：

K（n）=[CurrSADavg （n）PreSADavg （n-1）] （4）

视频序列的第一帧内插帧对应的K（n）为1，场景切换发生后的第一帧内插帧的K（n）也为1.将K（n）与经验阈值Th进行比较，大于Th则表示当前发生场景切换.算法具体实现步骤如下：

Step 1 从视频流中获取用于产生内插帧的前后参考帧F（n）和F（n+1）；

Step 2 采用基于SAD块匹配的双向运动估计算法计算内插帧中每一待插块的运动矢量，记录下每一最佳匹配块的SAD值；

Step 3 当前内插帧的运动矢量搜索完毕，计算各匹配块的SAD的平均值CurrSADavg （n）；

Step 4 如果是第一帧内插帧，则K（1）=1，PreSADavg（1）=CurrSADavg（1），场景切换标记SceneChangeFlag=0，转Step 6；否则，转Step 5；

Step 5 判断SceneChangeFlag是否为1，如果为1，说明F（n-1）与F（n）之间发生了场景切换，F（n）与F（n-1）之间不可能再發生场景切换，所以置K（n）=1，PreSADavg重新被赋值，即PreSADavg（n）=CurrSADavg （n），并将切换标记SceneChangeFlag置回0；如果SceneChangeFlag为0，说明F（n-1）与F（n）之间没有发生场景切换，则K（n）=CurrSADavg （n）/ PreSADavg（n-1），并且更新PreSADavg（n）= α×CurrSADavg（n）+（1-α）×PreSADavg （n-1）；

Step 6 将K（n）与阈值Th比较，大于Th，则SceneChangeFlag=1，表示F（n）和F（n+1）之间发生了场景切换；

Step 7 如果SceneChangeFlag为1，无需进行运动补偿，内插帧直接复制F（n）即可；否则，采用运动补偿方法产生内插帧.

2 算法仿真结果及对比分析

2.1 仿真平台及实验步骤

在MATLAB R2016a上进行仿真实验，实验对象选择8段mp4格式的电视电影片段，帧速率为25帧/秒，分辨率为640 × 480.这8段电视电影片段特征不同，如表1所示.

实验步骤如下：

Step 1 将视频序列转换成帧图像，并将彩色的帧图像转换成灰度图像；

Step 2 为了提高切换的频率，在原始图像序列基础上剪辑掉一些未发生场景切换的中间帧，以减少实验时间；

Step 3 依次读取图像序列，采用双向运动估计方法及SAD值匹配准则进行内插帧的运动估计，再根据本文提出的场景切换检测算法判断前后帧之间是否发生场景切换；

Step 4 用像素绝对差值法和平均亮度统计法去检测相同的视频序列；

Step 5 将3种算法的检测结果进行对比分析，验证本文算法的优越性.

2.2 分场景的仿真实验

根据视频片段的特征，将视频序列分成2种场景进行实验，分别为普通场景和切换前后图像亮度变化较小场景.

1）普通场景

所谓普通场景即是场景发生切换时，前后两帧图像的内容、纹理结构和亮度发生明显改变.如图3所示.

设置阈值Th为3，权重因子[α]为0.5，3个测试序列的实验结果如图4所示.其中，横坐标为图像帧序号，纵坐标为式（4）中的K值，判断是否发生场景切换取决于K值与阈值的比较.

（a）《新闻》视频序列的K值

从图4中可以看出，在发生场景切换时，K发生突变，其值远远大于未发生场景切换时的值，故根据K值判断是否发生场景切换是可行的.

2）切换前后图像亮度变化较小场景

在一些球赛或是整体过暗或过亮的视频序列中，发生场景切换时，切换前后图像亮度没有明显变化，如图5所示.

实验中，设置阈值Th为2，[α]为0.5.其中，横坐标为图像帧序号，纵坐标为式（4）中的K值.

从图6、图7中可以看出，在过暗或亮度变化不大的视频序列中，发生场景切换时部分帧图像的K值并没有突变，因此误判率和漏检率会比普通场景的高，K的阈值Th选取更复杂.

2.3 仿真结果对比分析

选取错判率[Rf]和漏检率[Rm]作为场景切换算法的评价标准，漏检表示真实发生了场景切换但是没有被算法检测到的情况，误判是指实际没有发生场景切换却被算法判断为发生了切换的情况.其公式分别如下：

[Rm=NmNc+Nm] （5）

[Rf=NfNc+Nf] （6）

其中，[Nc]——正确检测出场景切换的次数，[Nm]——遗漏检测出场景切换的次数，[Nf]——错误判断了场景切换的次数.将本文算法与传统的用于数字图像视频后处理芯片中的场景切换检测算法如像素绝对差值法[11]、平均亮度统计法[12]和参考文献[6]提出的算法进行比较.比较结果如表2所示.

从表2中可以看出，像素绝对差值法的平均错判率达到0.238，漏检率是0.169；平均亮度统计法比前者略有优势，错判率和漏检率分别为0.232和0.116；参考文献[6]的错判率和漏检率较前两者都有较大改善，分别为0.160和0.043.本文算法的错判率和漏检率分别为0.047和0.098，较前两种算法，错判率提升幅度分别为80%和79%，漏检率提升幅度为42%和16%，尤其在过暗或亮度变化不大的场景下，本文算法优势明显.这是因为像素绝对插值法和平均亮度统计法是基于像素或每一帧图像内容的亮度变化来判断场景是否发生了切换，因此对一些场景切换但图像平均亮度并未发生变化，或者没有场景切换而有部分图像内容发生较大亮度变化的情况，存在较高的“漏检”和“错判”可能.文献[6]是对基于直方图分布统计法的优化算法，能有效解决场景切换前后亮度变化不大而可能漏检的问题，因此本文算法与之相比，漏检率略高，但错判率更低.

3 结论

本文提出的场景切换检测算法是应用于帧率提升系统的，根据运动估计阶段内插帧的最佳匹配块对应SAD值的均值作为检测依据的一种算法，该算法与两种传统的用于视频后处理芯片中的检测算法即像素绝对差值法、平均亮度统计法以及参考文献[6]的算法相比，在以错判率和漏检率表征的检测准确率上有了明显的提升.

参考文献

[1]LUO L J，ZOU C R，HE Z Y. A new algorithm on MPEG-2 target bit-number allocation at scene changes[J]. IEEE Transactions on Circuits and Systems for Video Technology，1997，7（5）：815-819.

[2]FERNANDO W A C，CANAGARARAJAH C N，BULL D R. Fade-in and fade-out detection in video sequences using histograms[C]// IEEE International Symposium on Circuits and Systems，2000.

[3]RAINER L. Reliable transition detection in videos：a survey and practitioner's guide[J]. International Journal of Image and Graphics，2001，1（3）：469-486.

[4]戴宁赟，朱光喜. 一种场景切换的码率控制方法[J].计算机应用，2007，27（S1）：369-371.

[5]PEI S C，CHOU Y Z. Efficient MPEG compressed video analysis using macroblock type information[J]. IEEE Transactions on Multimedia，1999，1（4）：321-333.

[6]方宏俊，宋利，杨小康. 适配分辨率动态变化的低复杂度视频场景切换检测方法[J].计算机科学，2017，44（2）：290-295.

[7]刘辉，刘立程，郝禄国，等. 一种场景切换下的HEVC码率控制算法[J].电视技术，2017，41（6）：1-5.

[8]段淑玉，徐奕奕，李春贵，等. 一种基于运动矢量时域递归的运动估计算法[J].广西科技大学学报，2015，26（2）：36-40.

[9]袁高阳. 自适应逐行电影源模式检测算法研究[D].西安：西安电子科技大学，2015.

[10]方宏俊. 适配智能电视分辨率动态变化的视频后处理技术研究[D].上海：上海交通大学，2015.

[11]史久根，许林，张超. 一种场景自适应的H.264帧层码率控制算法[J].计算机应用研究，2010，27（5）：1968-1969.

[12]王悦，薛永林. 基于场景切换的码率控制方法[J].电视技术，2009，33（12）：17-20.

Scene change detection algorithm based on block matching motion estimation

DUAN Shuyu， CHEN Yan

（School of Computer Science and Communication Engineering， Guangxi University of Science and Technology， Liuzhou 545006， China）

Abstract： This paper proposes a scene change detection algorithm based on the mean SAD of the interpolated frames matching blocks， which is used in frame rate up system. This algorithm is used to solve the serious block effect problems due to mismatch in ME/MC algorithm when the scene is changed. We divide the average of the current interpolated frame SADcurr by the average of the previously generated interpolated frames SADpre and compare the resulting quotient with the empirical threshold， if we find the quotient is greater than the threshold， it is determined that a scene change occurs； otherwise， there has no scene change. The frame rate up system uses different interpolating algorithms based on the comparison results. Compared with the traditional detection algorithms， the experimental results show that the proposed algorithm has a significant improvement in the accuracy of scene change detection.

Key words： scene change detection； block match； motion estimation； frame rate up

（學科编辑：黎 娅）