SURF算法和RANSAC算法相结合的台标检测与识别

吴月凤，何小海，张 峰，滕奇志

(四川大学电子信息学院，四川成都 610064)

电视台的台标［1］是确定电视台的台名、节目取义的重要信息，是区分不同电视台唯一标志。为了声明视频的所有权，往往会在播放的视频中加入台标。若用人工来识别则工作量很繁重。目前主要存在基于颜色直方图［2］和普通Hu不变矩［3］两类台标自动检测与识别［4］。

近年来，基于特征点的匹配方法越来越被广泛的运用，SIFT［5－6］(Scale Invariant Feature Transform)是由 D.G.Lowe在1999年提出来的，之后Y.Ke对其算法进行改进，提出了 PAC － SIFT。Herbert Bay 在 SURF［7－8］(Speeded Up Robust Feature)中利用Integral和Hessian矩阵对其进行加速。

直接用SURF算法得到的匹配点对数，会出现很多错误的匹配，直接影响着匹配结果。本文融合了SURF算法与RANSAC［9］算法的各自优点，提出了只对感兴趣区域利用SURF提取特征，对得到的特征点对用RANSAC进行分类。首先需要用SURF算法创建一个台标特征点库。第二步得到视频中感兴趣的区域，即台标可能出现的位置，同样用SURF算法提取它的特征点。第三步将视频帧中提取的特征点与库中提取的特征点进行预匹配。最后通过RANSAC算法将错误匹配的特征点去掉，得到最终的匹配结果，计算出匹配率并进行排序，得到最大的结果与设定的阈值进行比较，从而识别出视频中的台标。

1 SURF匹配

为了保证旋转不变性和尺度不变性，SURF提取的特征信息由矩阵Hessian得到的极值点，同时还增加了一个包含主方向的特征描述符。

1.1 SURF特征提取

为提高运算速度，利用积分方式实现图像卷积。积分图像定义如下:设X=(x，y)表示图像I(X)中某一像素点，则积分图像IΣ(X)是由点X=(x，y)与原点为对角顶点组成的矩形框内的所有像素点之和，即

因为在积分时只需要遍历一次原始图像即可，计算积分图像时它的运算非常小。假如矩形由A、B、C和D四个顶点构成，则矩形的窗口内的总灰度为Σ=A－B C+D。

给定图像I中的一个点X=(x，y)，Hessian矩阵H(x，σ)在x处尺度为σ的定义如下

式中:参数ω是一个调节参数，用于平衡Hessian行列式表达式，计算如下

由H矩阵的特征值得到判别式的值，在判定结果的基础上将所有的点进行分类，根据判别式取值判断是否是极值点。然后将低于预先设定极值的取值丢弃，实现特征点精确定位，通过增加极值以减少特征点数，最后留下最强的特征点。

1.2 特征点的匹配

当计算得到所需要的特征点之后，计算出该点的主方向，然后提取特征描述符，找出图像中与之对应特征点的位置。只有确定图像之间特征点的关系，才能完成对后续两幅图像的关系进行判断。特征点是否匹配成功是用特征描述符之间的相似度来判别的。

设n1，n2为图像Q，T的特征数，Qi(i=1，2，…，n1)为查询图像的任意特征点，Ti(j=1，2，…，n2)为目标图像的任意特征点，则定义Qi与Ti之间的相似度为

根据式(5)，把查询图像的Qi与目标图像中的所有特征点计算一遍，如果单纯地取它们之间的最小值作为两个特征点匹配的依据，则会出现错误匹配。因此对视频帧中台标的某一特征点，在台标库中找出和它欧氏距离最近的两个特征点，d1表示两者之间的最近距离，d2表示两者之间的次近距离，为了消除背景或遮挡带来的干扰而产生的无对应关系的特征点，Lowe提出用d1和d2相比较的方法，匹配准则是当d1＜a×d2时(其中a为比例系数，取值范围在0～1)，若满足匹配准则即可认为该点对成功配对。显然，当a越小，匹配成功的点对越少，但相对更加稳定;当a越大，则错误匹配的几率就有可能增加。

1.3 计算感兴趣的区域

不同于其他类型的图像，国内的电视台标一般置于4个角附近的矩形区域［11］内，基于台标这一特殊位置的特点，本文提出了先获得视频帧中感兴趣区域。为了提高算法的鲁棒性，假设台标在感兴趣区域中的偏移量为δ个像素，即台标的左上角位置位于(xi－δ，yi－δ)和(xi+δ，yi+δ)的矩形区域内。本文的感兴趣区域采用式(6)表示

对待测试图像的感兴趣区域［11］为

式中:ROIi表示第i个待识别图像的感兴趣区域;MIN表示最小值;MAX表示最大值。只对感兴趣区域提取特征点很大程度上提高了识别的速度。

2 RANSAC算法

RANSAC［12－13］(Random Sample Consensus)算法是基于一组包含异常数据的样本数据集，通过迭代方式估计数学模型的参数，得到有效样本数据的算法。它于1981年由Fischler和Bolles最先提出。RANSAC基本思想是先任意取两个特征点画一条直线，用事先确定的误差计算直线包含的点数，包含在直线上的点称为内点，根据所谓的内点重新得出一条直线，不断重复直到内点数不再变化，最后得出RANSAC算法的拟合结果。

3 判决准则

3.1 匹配点对的过滤

本文对SURF算法所得到的匹配点对进行排序，得到匹配最多的特征点对可能是视频帧中的台标，所以需要设定对应的判决标准。在用SURF进行特征点配对时，根据1.2节中设定的系数a来判断点对是否匹配成功。本文在实验中遇到多个特征点对应一个特征点的情况(如图1所示)，如果没有进行透视转换关系，下文中提到的匹配率有可能大于1，这对于正确的台标匹配是不合理的。

因此单纯地将SURF提取的特征点进行匹配得到的对数作为台标的排序是不合理的，所以很有必要使用RANSAC随机抽样方法来计算预匹配点对之间的透视变换关系。为提高匹配的正确率，首先必须实现台标的正确定位。因此本文首先用SURF提取台标的特征点与台标库中的台标特征点进行预匹配，然后进行透视变换去除错误的点对，滤除后的点对作为它的最终匹配点对数，将点对进行排序得到最多对数，计算出匹配率再与设定的阈值比较，最后得出它的识别结果。

图1 点对过滤效果图(截图)

3.2 匹配率

对于台标的特征点参差不一的情况，无法通过设定对数阈值来判断是否匹配成功，所以可以用一个比值来表达相同的含义，于是引入了匹配率。本文定义匹配率T为

式中:C表示经过RANSAC算法后得到的匹配成功最多的对数;Stemp表示在待识别台标中提取的特征点数;T表示台标中匹配成功最多的对数与待测台标特征点数的比值。

4 算法的流程描述

本文算法的流程图如图2所示。首先从视频中获取一帧图像，然后计算感兴趣区域并只对感兴趣区域提取SURF特征，与台标库提取的SURF特征预匹配，再用RANSAC算法过滤匹配点对，接下来对匹配成功的点对数进行排序，得到匹配最多的对数，计算出它的匹配率，最后将得算出的匹配率与设定好的阈值比较大小，识别出视频帧中的台标是否存在于台标库中。

图2 实验流程图

5 实验结果与分析

本文在实验中首先选择一些背景干扰比较少的电视台的台标提取特征信息。然后提取一些包含台标和不包含台标的视频帧，将它们一部分存档一部分不存档。实验中的测试目标包括CCTV2、CCTV4、CCTV7、安徽卫视、河南卫视、东南卫视、兵团卫视、甘肃卫视、西藏卫视、云南卫视、湖北卫视等25个电视台标，每个台标的视频提取20帧作为样本。实验采用C++与OPENCV库相结合的方式进行台标的检测与识别。测试机器为双核酷睿i3，主频2.1 GHz。

表1为实验中用透视变换关系与不用透视变换关系得到的统计识别率情况。经过多次实验得到当设定的最近距离与次近距离的比例因子a为0.6、匹配率的阈值T为0.13时识别率最高。识别率的统计方法为

表1 实验中台标识别结果

匹配率T是台标识别的判断标准，它的大小会直接影响着台标识别的结果。据实验统计，匹配率T的值对正确识别率的影响关系如图3所示，可以看出当T=0.13左右时，识别的正确率最高。

图3 T值对识别结果的影响

图4为部分实验结果，其中图4a～图4e为正确识别出的台标，图4f为台标库中未存档的台标，图4g、图4h为未识别出。

图4 部分台标匹配的结果(截图)

由表2知，将本文使用的识别方法与常用的模板匹配的方法进行比较，可以看出对于透明的台标，本文使用的方法比模板匹配的识别率要高。另外用本文的方法可以保证旋转不变和尺度不变的优点。而模板匹配则没有这个优点。

本文只提取感兴趣区域的特征点以提高识别速度。为更充分说明这点，本文分别在使用ROI与不使用ROI的情况下，统计了部分台标在识别过程所消耗的时间，表3是两种情况下每个台标与一个视频帧匹配所消耗的时间。先计算感兴趣区域，在很大程度上减少了台标识别所用时间。

表2 本文算法与模板匹配算法识别结果的对比

表3 部分台标识别所消耗的时间 ms

6 结论

本文提出一种基于SURF算法与RANSAC算法相结合的台标检测与识别，首先对视频帧中感兴趣区域用SURF算法提取特征点，并与台标库中的特征点进行预匹配，再利用RANSAC算法对匹配的特征点对过滤，得到最后的匹配点对。实验取得了令人满意的正确率，较好地实现了视频帧中的台标检测与识别。实验表明本文算法对标在识别率以及识别速度上都取得了很好的效果。

:

［1］张重德.电视信号自动检测与报警系统［D］.合肥:合肥工业大学，2008.

［2］秦剑鹏，符茂胜，涂铮铮，等.基于颜色直方图变化率的视频镜头检测［J］. 计算机应用与软件，2011，28(4):17－20.

［3］王振海.融合HU不变矩和SIFT特征的商标检索［J］.计算机工程与应用，2012，48(1):187－190.

［4］YAN W，WANG J，MOHAN S.Automatic video logo detection and removal［J］.Multi－media System，2005，10(5):379.

［5］郭振成，梁凤梅.一种改进的SIFT特征点匹配算法［J］.电视技术，2014，38(1):23－25.

［6］YANG Z，GUO B.Image mosaic based on SIFT［C］//Proc.International Conference on Intelligent Information Hiding and Multimedia Signal Processing.［S.l.］:IEEE Press，2008:1422－1425.

［7］BAY H，ESS A，TUYTELAARS T，et al.Surf:speed up robust feature［EB/OL］.［2014－02－02］.http://www.vision.ee.ethz.ch/～ surf/.

［8］张鹏雁，赵耀，朱振峰.基于商标匹配的视频广告识别［J］.信号处理，2012，28(8):1083－1089.

［9］LUO C，JAMES H.Robust geolocation estimation using adaptive RANSAC algorithm［J］.IEEE Geosci.Remote Sens.Lett. ，2010，9(3):3862－3865.

［10］LOWE D.Object recognition from local scale－invariant features［C］//Proc.the 7th IEEE International Conference on Computer Vision.［S.l.］:IEEE Press，1999:1150－1157.

［11］侯胜伟，何小海，滕奇志.台标的自动检测与识别［J］.四川大学学报:自然科学版，2013，50(3):521－526.

［12］LIU K，JIE Q，YANG R.Block matching algorithm based on RANSAC algorithm［C］//Proc.IASP 2010.［S.l.］:IEEE Press，2010:223－227.

［13］MARTIN A，ROBERT C.Random sample consensus:a paradigm for modelfitting with applications to image analysis and automated cartography［J］.Communications of the ACM，1981，24(6):381－395.