一种新的维吾尔文字幕关键帧提取方法

闫 轲，哈力旦·阿布都热依木，李敏强

（新疆大学 电气工程学院，新疆 乌鲁木齐 830047）

随着多媒体和互联网技术的迅速发展，视频已经成为获取信息资源的主要形式之一.人们希望像文本一样能对视频进行浏览、查询、处理等，能够通过快速浏览找出自己感兴趣的内容.但是从海量的视频中快速找到有效的信息并不容易，因为视频具有数据量大、结构复杂、内容丰富的特点.如何实现视频的有效处理和管理、多媒体图像快速有效检索浏览［1］是当前视频处理领域需要解决的问题.

关键帧是能够代表视频主要内容的视频帧图像，用户只需要浏览关键帧序列就可以了解视频的主要内容，所以关键帧的提取是视频检索的重要环节，提取的效果直接影响视频检索系统的性能.近年来，经过人们不断研究和完善，视频关键帧提取的方法越来越多.文献［2］使用预采样方法来减少处理的数据量，提取图像的局部二值模式（local binary pattern，简称LBP）特征；然后对两帧图像进行相似度分析，获取聚类数目，使用K－均值算法聚类；最后使用“重要度”函数评测，从“重要”聚类中选取关键帧.文献［3］利用基于八叉树结构的色彩量化算法提取图像主色彩特征，通过计算颜色特征的相似度实现镜头边界检测，采用K－均值算法对提取出的代表帧序列进行聚类，再提取出指定数目的关键帧.文献［4］在计算帧图像相似度时，给不同的块赋予不同权值，通过计算自适应阈值对视频进行初次聚类，并计算类间距离，进行二次聚类得到最终类别，从每个最终类中选取关键帧.文献［5］先通过映射不变特征排除一些相似关键帧，后利用局部二值模式和颜色特征匹配来对两帧图像进行比较，去除相似关键帧.另外还有基于支持向量机（SVM）的关键帧提取方法［6］等.

上述关键帧提取方法大都存在计算量大、提取结果冗余量大等情况，此外，大多数方法都是对视频画面的整体变化提出的，针对视频中含字幕的帧图像的提取并没有合适的具体方法.为了有利于以维吾尔文为内容的视频信息在互联网上的检索和获取，加快维吾尔文信息的传播，作者提出一种基于多尺度Harris角点检测和拟合直线的方法，结合维吾尔文字的笔划特点［7］对视频中维吾尔文字幕进行关键帧提取［8］.

1 基于多尺度Harris角点的字幕关键帧提取

1.1 Harris角点检测

Harris角点检测算法是在 Moravec算法［9］的基础上，由Harris等于1988年提出的一种基于信号点特征的提取算法［10］.

Moravec角点检测算法的思想是：在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化值超过设定的阈值时，就将窗口中心的像素点提取为角点.定义任意方向上自相关值E（u，v）为一组正方形区域中图像灰度变化，设像素点（x，y）的灰度为f（x，y），则像素点从（x，y）移动到（x＋u，y＋v）的灰度变化可表示为

其中：（u，v）的取值为：（1，0），（1，1），（0，1），（－1，1），（－1，0），（－1，－1），（0，－1），（1，－1）.可以看出，Moravec角点检测算法有几个明显的缺陷：1）灰度的计算并不是各向同性的，只考虑到离散的8个45°角的方向；2）未对噪声进行抑制，故响应函数会有噪声；3）只考虑了E的最小值，故对边缘响应较敏感.针对Moravec算法存在的问题，Harris在此基础上，利用微分运算和自相关矩阵来检测角点.（1）式的泰勒展开式为

假定M是2×2的对称矩阵，表达式如下

其中：fx，fy分别是图像沿x和y方向上的梯度值.设λ1、λ2是M的两个特征值，可以通过特征值来判断图像中的平坦区域、角点和边缘.3种类型的λ1、λ2数值大小如下：

（1）平坦区域：λ1和λ2的值均比较小；

（2）边缘区域：λ1和λ2中一个值较小，另一个值较大；

（3）角点：λ1和λ2的值均比较大.

为了提取角点，Harris构造如下表达式

其中：Det（·）表示对矩阵求行列式；Trace（·）表示对矩阵求迹；k为常系数，经验值为0.04～0.06.当R绝对值很小时，表示平坦区域；R是负值且绝对值较大时，表示边缘区域；R值很大时，表示角点.

Harris角点检测是一种经典的角点检测方法，但是其存在一定的缺陷，如只能在单一尺度下检测角点、对噪声比较敏感、容易漏掉真实角点等。多尺度Harris角点检测［11］中的多尺度参数检测算子，能够检测出图像灰度的粗略变化，对噪声具有较强的抑制，因此作者拟采用多尺度Harris角点检测方法，以剔除伪角点、提高角点的定位准确度。

1.2 维吾尔文字幕关键帧初步提取

视频图像的文字一般分为两种：一种是视频图像内容自身含有的文字，如车牌号、标语，称为场景字幕；另一种是人工合成到视频图像中的文字，如新闻标题、台词，称为人工字幕.该文主要检测人工字幕.图1为第60帧原图及多尺度Harris角点检测图.

多尺度Harris算法是一种有效的角点检测算法，计算时只用到灰度的一阶差分以及滤波，不必手工设置每一尺度下的阈值，对图像旋转、灰度变化、噪声影响和视点变换不敏感，结合维吾尔文字的笔划特征（点、环、弯钩等），对维吾尔文字幕区域提取的角点均匀合理，具有高密度、高准确率的特点，突出了字幕区域，为维吾尔文字幕关键帧的提取奠定了良好的基础.

假设从一段视频得到的帧序列为F，表示为｛f1，f2，…，fn｝，n为视频帧的总数，基于多尺度Harris角点的字幕关键帧提取步骤如下：

1）利用公式（4）中的R值判断出每帧图像的角点区域，并统计每帧图像的角点个数和二值化（背景为黑色，字幕为白色）以后的白色像素点个数，设S（fi）和C（fi）分别表示第i帧图像的角点个数和白色像素点个数.

2）设定阈值T1，如果S（fi）和S（fi＋1）均大于T1，且C（fi）＞C（fi＋1），则将编号为fi的帧保存至文件夹pic中，否则，将帧编号为fi＋1的帧保存至文件夹pic中.

3）取i＝i＋1，若i＜＝n－1，转至步骤2），否则结束提取，此时文件夹pic中存放的即为初步提取的含字幕关键帧.

经此过程提取出的关键帧存在一定的冗余，还需要进一步去除冗余.

2 利用拟合直线消除冗余的关键帧

图像的轮廓即图像的边缘，常用的边缘检测算子有：Roberts、Sobel、Prewitt以及Canny算子等.Canny算子是依次进行高斯滤波、求每个像素梯度、对梯度进行非最大值抑制、计算边缘强度和对边缘图像做滞后阈值化处理，来完成边缘提取的.Prewitt算子是在图像空间利用两个方向模板（分别用于检测水平边缘和垂直边缘）与图像进行邻卷积来完成边缘提取的.

以第235帧图像为例，图2a为Canny算子边缘图，毛刺较多，会干扰该实验结果的准确性；相比之下，Prewitt算子边缘图2b，虽然检测出的边缘并不是完全连通的，但是毛刺较少，有利于该实验的进行.故该文采用Prewitt算子来提取图像的边缘.

初步提取得到的关键帧虽然能够很好地反映视频的主要内容，但存在一定的冗余，这里需要采用最小二乘法来拟合［12］.

图像的轮廓图只包含两种像素点：白色和黑色（把黑色作为背景，白色的像素看成背景上的点）.每一个白像素点都有一个坐标（用该像素点所在的列数作为横坐标，以其所在的行数作为纵坐标），这样可得到一个坐标集C，即

其中：n为所有白像素点的个数.得到坐标集C后，假设所要拟合的直线为y＝ax＋b，则

其中：N是坐标集C中坐标的个数.设有两幅图像，通过提取轮廓和直线拟合得到的两条直线为：y＝a1x＋b1和y＝a2x＋b2.两条线的夹角为

根据最小二乘法拟合直线的原理，结合维吾尔文字的特点，可得到拟合直线的结果.用两幅帧图像的拟合直线夹角来判断两幅帧图像是否相似，如果夹角小于阈值T2，则认为相似；否则，认为不相似.

3 实验结果分析

实验在Matlab7.0环境下进行.下面以《功夫熊猫2》中一段长度为16s的视频为例，总共244帧，其中含有维吾尔文字幕的帧有211帧，含字幕的关键帧有6帧，采用该文方法的提取结果如下：

（1）实验中选取阈值T1为40，图3为基于多尺度Harris角点检测的字幕关键帧初步提取结果.

（2）实验中选取阈值T2为0.04，图4为关键帧去冗余后的结果.

从《功夫熊猫2》视频段的实验数据可以看出，通过多尺度Harris角点检测初步提取的8帧（见图3）字幕关键帧，漏检数为0，误检数为2，经过拟合直线去冗余后，得到了6帧（见图4）准确含有维吾尔文字幕的关键帧，结果比较理想.

为了进一步验证该方法的有效性，选取不同类型的视频，含有不同的维吾尔文字.表1、2分别是用文献［3］提出的图像主色彩方法和文献［5］提出的LBP和颜色匹配法提取的维吾尔文字幕关键帧的实验数据.表3是用该文提出的多尺度Harris角点检测和最小二乘法提取的维吾尔文字幕关键帧的实验数据.图5、6分别是以上3种方法的查全率和查准率的对比图.

表1 文献［3］方法的实验数据Tab.1 The experimental data of methods in Ref.［3］

表2 文献［5］方法的实验数据Tab.2 The experimental data of methods in Ref.［5］

表3 该文方法的实验数据Tab.3 The experimental data of method in this paper

从表1～3的实验数据可以看出，该文方法的提取结果中误检帧数以及电影和MTV类的视频中的漏检帧数均低于文献［3］和文献［5］方法的提取结果.由图5、6可知：虽然该文方法对新闻类视频的查全率较其他两种方法略低，但是其电影和MTV视频的查全率及所有类型的查准率较其他两种方法都高，因此综合起来看将多尺度Harris角点检测与拟合直线结合的方法，运用到视频维吾尔文字幕关键帧的提取中，不失为一种有效的方法.

4 结束语

Harris算法是目前使用较多的角点检测方法，但是其容易漏掉真实角点，对噪声敏感.作者结合维吾尔文字的笔划特点，提出基于多尺度Harris角点检测方法对维吾尔文字幕关键帧进行初步提取.由于目前的关键帧提取方法当中都存在冗余的问题，所以要利用拟合直线的方法对初步提取的关键帧进行去冗余处理，实验表明该方法在保证查全率的同时，还降低了提取结果的误检帧数，计算快速简单，提取结果准确率高，具有良好的适应性.作者对维吾尔文字幕关键帧的提取为后期维吾尔文字定位、切分、识别以及不良文本过滤等研究奠定了一定的基础.

［1］雷少帅.基于内容的视频检索关键技术研究［D］.太原：太原理工大学电气与动力工程学院，2012.

［2］张芯，谢毓湘，栾悉道.一种基于局部二值模式的关键帧提取方法［J］.计算机与现代化，2013，2013（11）：8－12.

［3］王松，韩永国，吴亚东，等.基于图像主色彩的视频关键帧提取方法［J］.计算机应用，2013，33（9）：2631－2635.

［4］刘晓楠.基于内容二次聚类的关键帧提取算法［J］.计算机与数字工程，2010，38（7）：26－29.

［5］Wang Y，Hou Z，Chang R，et al.Near－duplicate keyframe identification based on color and affine invariant features［C］／／Image Processing（ICIP），19th IEEE International Conference on IEEE，2012：2361－2364.

［6］Li P，Guo Y，Sun H.Multi－keyframe abstraction from videos［C］／／Image Processing（ICIP），18th IEEE International Conference on IEEE，2011：2473－2476.

［7］艾力，居麦，哈力旦，等.视频图像中维吾尔文字的识别研究［J］.计算机工程与应用，2012，47（36）：190－192.

［8］张鲁建，哈力旦，黄浩.基于基线的视频维吾尔文字幕帧提取研究［J］.传感器与微系统，2013，32（4）：65－68.

［9］Moravec H P.Towards automatic visual obstacle avoidance［C］／／Proceeding of the 5th International Joint Conference on Artificial Intelligence，Cambridge，MA，USA，1977：584－590.

［10］Harris C，Stephens M.A combined corner and edge detector［C］／／Proceedings of the 4th Alvey Vision Conference，1988：147－151.

［11］杜振龙，杨凡，李晓丽，等.基于多尺度 Harris角点的图像文字检测［J］.计算机工程与设计，2012，33（9）：3522－3525.

［12］解晓萌，黎绍发.一种新的冗余关键帧去除算法［J］.电视技术，2012，36（S1）：53－56.