基于改进Chamfer匹配的台标识别

胡星火，姚剑敏，林志贤，郭太良

(福州大学物理与信息工程学院，福州 350002)

1 概述

电视机视频中的台标是标识该电视台台名、节目取义的重要信息。台标识别是基于内容的视频图像分析、检索领域[1]的热门研究方向之一。台标正确识别的首要前提是台标的正确分类，目前大陆电视台台标主要分为3类：

(1)静态不透明台标，像湖南卫视、江苏卫视等大部分频道。

(2)静态半透明台标，以中央电视台为典型代表。

(3)极少数的动态台标，本文不考虑此类台标。

台标识别主要包括2个方面的内容：台标的检测，台标的特征的提取和识别。目前，国内外已有的技术多是基于视频流作帧间差[2]和视频流加权叠加求平均[3]方法来分割台标。该原理只对静态不透明台标成立，对半透明台标则不成立。另外，基于视频流的方法不能实现台标的实时检测识别。因此，本文提出一种基于改进Chamfer匹配的台标识别方法。

2 台标识别分析

台标识别的关键在于台标的检测分割，传统视频流法主要利用台标的时空不变性，即台标区域的像素值稳定不变，非台标区域像素值发生均匀或者非均匀变化。显然，该方法存在3个缺陷：(1)当背景长时间不变或变化很小时，将不能分割出台标或分割效果不理想。(2)由于半透明台标区域的像素值会随背景的变化而变化，因此对半透明台标识别效果不理想。(3)由于视频流中相邻帧图像相似性极高，一般至少每隔 30帧抽取一帧做帧间差[4]或加权叠加[5]时算法才有效，因此实时性差。

采用加权叠加平均法结合自适应阈值法[6]分割湖南卫视频道的一段视频，处理结果如图1所示。

从图1可以看出，叠加的帧数越多，分割效果越好，但实时性越差，这在实际中是无法忍受的。

另外，许多电视台在播放电影时，画面的上边沿会出现一个固定宽度的黑边，此时，基于视频流法无效。总的来说，视频流法依赖于背景的变化，而本文方法不依赖背景，可实现单帧图像识别。

3 本文方法原理

3.1 方法分析

当视频背景分布较均匀的时，Canny[7]算子提取的台标边缘效果较好，而实际情况多为背景复杂，用Canny算子检测出的台标边缘存在大量的背景干扰边缘。这种情况下，仅依靠台标边缘信息，匹配的效果较差，也就是说单纯使用形状特征，丢失边缘方向和颜色信息，容易误判。为克服背景边缘的干扰，本文采用融合台标边缘梯度方向和颜色分量的Chamfer匹配[8-9]。该方法克服了视频流作差或叠加时效性差的缺点，只需一帧包含台标的图像，即可准确的检测并识别出台标，本文台标识别方法框架如图2所示。其中，三角形为台标；圆形和正方形为假设的背景干扰边缘；δ为距离阈值；CGCM(Color Gradient Chamfer Matching)。与传统Chamfer匹配方法相比，本文方法鲁棒性更好，适应场所更广泛。

图2 台标识别方法框架

3.2 Chamfer匹配原理

本文方法的基础是传统Chamfer匹配方法，传统方法通过计算2个轮廓距离的方法，来度量它们的相似性。这种方法在目标发生小幅旋转、畸变以及非对称的情况下，仍能检测出目标物[10-11]，具有良好的鲁棒性，其基本计算公式如下：

其中，T={ti}为模板图像的边缘点集合；|T|表示集合T的点数；E={ej}为目标图像的边缘点集合；ti和 ej分别为T和E中的第i个、第j个边缘点；dT(T,E)为模板 T中的边缘点到图像 E中最近像素点的平均距离；T和E 2个边缘相似度越高，dT(T,E)的值将越小，当T和E是完全相同的边缘的话dT(T,E)=0。

而在实际情况当中，dT(T,E)都是通过E的边缘距离变换来计算的，E的距离变换公式如下：

那么dT(x)可以写成下面的形式：

其中，x为模板在目标图上的偏移量。

若直接按照式(3)计算，dT(x)时间复杂度非常高。为了计算简单，通常长采用所谓3-4法则[12-13]来近似欧氏距离用于计算，只需循环2次就可以完成距离变换的计算，大大加快计算速度，2次循环分别为：第1次是前向循环：从左至右，从上到下；第2次是反向循环：从右到左，从下到上；这样形成的距离值与真实的欧氏距离值最大误差是 8%。具体详细过程可以参考文献[12]。

3.3 本文匹配原理

广播电视画面复杂多变，且具有随机性，使用Canny算子提取台标边缘，通常不可避免会有背景边缘的干扰；再者由于传统Chamfer匹配方法自身的局限性，抗干扰能力较差，因此为了克服杂乱背景边缘的干扰，本文对Chamfer匹配方法进行了改进，引入边缘梯度方向θ和边缘颜色分量c。

其中，ti和ei分别为台标模板T和目标图像E中的边缘点；θ(ti)、θ(ei)边缘点梯度方向；c(ti)、c(ei)为边缘点颜色；α和β分别为边缘梯度方向和颜色的权重。引进方向分量α是为了克服非台标边缘的干扰；引进颜色分量β是为了区分形状相似、颜色相异的台标。

综合式(3)～式(8)得：

同理计算上面的式子也可以通过图像 E的距离变换来实现：

显然，台标匹配的位置越精确，Ci、Fi越小；反之越大。图3为CGCM计算原理。

图3 CGCM计算原理

模板T是由一序列边缘点构成的点集，因此，为了进一步加快计算速度、节约存储空间，本文使用RANSAC[13]算法对模板T的边缘点进行优化，滤去一些杂点。设优化前模板点集为T={ti}(i=1,2,…, N)，优化拟合后点集可以表示为Tr={li[si,ei]}，(i=1,2,…,M)，其中，M远小于N；li表示集合T的第i个子集；si、ei分别表示子集li的起点和终点，子集里的点都具有相同的梯度方向θi，经过优化拟合后的点集可以节约存储空间，显著提高计算速度。RANSAC算法拟合边缘图本质上是对边缘梯度方向进行量化。图 4为RANSAC算法拟合前后的模板边缘。

图4 RANSAC算法拟合前后的模板边缘

由此，式(10)最终可以改写为：

3.4 台标边缘梯度方向和颜色的提取

台标的形状和颜色是台标最直观的特征，现有的大部分台标都具有丰富的颜色和独特的形状。现有的形状描述法主要有2种，即基于边缘的形状和基于区域的形状，考虑到半透明台标颜色易受背景影响，因此，台标形状不宜采用基于区域的形状。通常，无论是不透明还是半透明台标，都会与背景形成鲜明的边缘，且边缘颜色比较稳定。一般情况下，台标总能与背景形成清晰可见的边缘，台标边缘检测的好坏直接影响到台标的检测识别；Canny算子是目前边缘检测方法中最好的，具有良好的信噪比和检测精度；因此，本文利用Canny算子提取边缘梯度方向θ和边缘颜色分量c，Canny算子提取的台标模板边缘如图5所示。

图5 Canny算子提取的台标模板边缘

关于边缘颜色特征提取的方法很多，常用的方法有颜色直方图、颜色统计矩、颜色信息熵等方法。在实际中，往往都是针对不同场所采用不同的方法。台标的边缘是与背景形成的，由于视频背景的随机变法特点以及视频噪声等，每次形成的台标边缘会有一些差异，因此对台标边缘颜色特征提取方法不宜过于精细，过于精细不仅计算复杂，且存储空间迅速膨胀，对噪声特别敏感。

基于以上因素考虑，本文采用常用的色度、饱和度、纯度(Hue Saturation Value, HSV)颜色空间对台标边缘分量c非均匀量化，具体量化过程参考文献[14]，不再赘述。

色度H量化分为8个相似区间：[316,20]，[21,40]，[41,75]，[76,155]，[156,190]，[191,270]，[271,295]，[296,315]；饱和度 S量化为 3个区间：[0,0.2]，[0.2,0.7]，[0.7,1]；对纯度V量化为2个区间：[0,0.2]，[0.2,1]。

3.5 台标识别

台标识别就是在台标边缘特征提取的基础上，所进行的特征匹配。其过程为：首先，建立标准的台标模板库，台标模板是通过软件和必要的手动修改完成的。台标的相似性度量是采用改进型的Chamfer匹配距离度量，类似于欧氏距离最小准则，本文称作CGCM 距离最短准则。dTr(Tr,E)(x(θ,c))越小，匹配度越高。本文采用多次识别的方法，即统计概率最大准则来提高识别精度。方法是对多帧进行台标识别，若某一台标被选的次数超过总识别次数的 60%(包含60%)，则认为该台标为最终识别的结果。

如图 6所示为复杂背景下本文方法和 Chamfer匹配方法仿真结果对比。

图6 复杂背景下2种方法的仿真结果对比

从图6可以看出，对于复杂背景下，由于丢失了颜色信息和边缘方向，因此传统Chamfer匹配方法会出现明显误判。

4 实验结果与分析

本文实验的硬件平台是Intel(R) Core(TM)2 Quad CPU Q83 00、华为公司的InfoLink C2510有线数字机顶盒、同三维公司的T650E视频采集卡、软件平台为Windows XP操作系统、微软VS2008、Open-CV2.0，台标库的台标数为77。

根据经验，大陆电视台标一般都在电视台的左上角，因此，为了节省搜索时间，每次只搜索视频画面左上角部分大小为(640/3)×(480/4)的部分，即占整个视频画面的 1/12大小。本文在识别时间和识别精度上做了折中，即对每个电视台识别10次，如果6次识别正确，即表示最终识别结果正确。实验方式为在线对每一个频道不间断测试 3 h，台标识别结果如图7所示，表1为部分频道在线测试结果。

图7 台标识别结果

表1 部分频道在线测试结果

本文方法实现了单帧识别，不依赖于连续变化的视频流，因此，基本满足实时检测识别，由表1可知，平均识别时间为801 ms，平均识别率为97.7%。

5 结束语

综合分析台标特征，本文提出一种基于改进Chamfer匹配的台标识别方法。该方法不依赖于背景视频的连续变化，能实现单帧图像的台标实时检测，具有较好的鲁棒性，能够满足国内主要电视台台标的识别。然而随着台标库中台标数量的增加，匹配时间会越来越长，且其还无法对动态台标进行识别，因此，今后将继续研究如何提高计算速度和匹配精度。

[1]胡振兴, 夏利民.基于视频片段的视频检索[J].中南大学学报: 自然科学版, 2010, 14(3): 1010-1014.

[2]史迎春, 周献中, 方鹏飞.综合利用形状和颜色特征的台标识别[J].人工智能与模式识别, 2005, 18(2): 216-222.

[3]Albiol A, Fulla M J, Albiol A, et al.Detection of TV Commercials[C]//Proc.of the IEEE International Conference on Acoustics Speech, and Signal Processing.Montreal, Canada: [s.n.], 2004.

[4]周献中, 史迎春, 王 韬.基于 HSV 颜色空间加权 Hu不变矩的台标识别[J].南京理工大学学报, 2005, 29(3):364-367.

[5]Chattopadhyay T, Aniruddha S, Arpan P, et al.Recognition of Channel Logos from Streamed Video for Value Added Services in Connected TV[C]//Proc.of IEEE International Conference on Consumer Electronics.Las Vegas, USA:[S.l.]: 2011.

[6]Ozay N, Sankur B.Automatic TV Logo Detection and Classification in Broadcast Videos[C]//Proc.of the 17th European Signal Processing Conference.Glasgow, UK:[s.n.], 2009.

[7]Canny J.A Computational Approach to Edge Detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(6): 236-241.

[8]Gavrila D M, Daimler A G.Multi-feature Hierarchical Template Matching Using Distance Transforms[C]//Proc.of IEEE International Conference on Pattern Recognition.Brisbane, Austrila: [s.n.], 1998.

[9]Borgefors G.Distance Transformations in Arbitrary Dimensions[J].Computer Vision, Graphics, and Image Processing, 1984, 27(3): 321-345.

[10]Shotton J, Blake A, Cipolla R.Multi-scale Categorical Object Recognition Using Contour Fragments[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008, 30(7): 1270-1281.

[11]Belongie S, Malik J, Puzicha J.Shape Matching and Object Recognition Using Shape Contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(4):509-522.

[12]管伟光, 马颂德.统一化的快速距离变换[J].计算机学报, 1995, 18(8): 625-635.

[13]Martin A F, Robert C B.Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Communications of the ACM, 1981, 24(6): 381-395.

[14]王向阳, 陈景伟, 于永健.一种基于彩色边缘综合特征的图像检索算法[J].人工智能与模式识别, 2010, 23(2):216-221.