基于主方向模板的视频中角标广告检测算法

徐 聪， 杜秀华， 曹雪昭， 曹 俊

(1. 上海交通大学 自动化系 系统控制与信息处理教育部重点实验室，上海200240;2. 上海东方娱乐传媒集团 广告经营中心，上海200041)

0 引 言

电视节目中的角标广告是一种新颖的广告形式，它通过在视频内容的边缘位置播放特定的图标，以实现为企业或组织提供广告宣传的目的，图1 为某电视台包含角标广告的视频截图。角标广告形式多样，图标形状或不规则，或镂空等有不同的外形特点，对角标广告的检测是用图像处理和识别方法自动检测视频中角标广告的时长和位置。

图1 某电视台视频截图及角标广告

角标广告的检测问题比较新，但对角标的检测算法可借鉴基于内容的视频检索［1］(CBOR)的已有成果。CBOR 中的图像识别算法可分为基于全局特征的方法和基于局部特征的方法。基于全局特征的方法如利用距离分布直方图［2］或基于轮廓的距离变换［3］等实现图像的检索，但这些方法均因速度较慢、鲁棒性不强，或是缺乏准确性而难以用于实际的视频检索。而基于局部特征的算法，如SIFT［4-6］、SURF［7］，这类算法所基于的特征点与描述子通常很稳定，但是特征向量的提取以及匹配都非常依赖于局部区域像素的梯度方向，描述子方向的不准确会造成特征匹配的误差放大，而且检索的效率也依赖于特征点的数量。

模板匹配方法［8］一般使用全局特征，它的优点在于可方便添加不同的模板，定位过程比较简单。但是，由于模板遍历的计算复杂度较高，因此在视频检索中的应用受到了限制。Hinterstoisser 等提出了主方向模板(Dominant Orientation Template，DOT)算法，加快了模板特征的提取和匹配速度［9］，使模板匹配方法受到了新的关注。DOT 借鉴了HOG［10］算法，将目标图像分割为网格，定义“主梯度方向”对图像特征进行压缩，并对主梯度方向采用位编码法大幅度降低了特征提取和匹配的计算复杂度，在图像匹配的鲁棒性上也显示了较好的性能。但是DOT 也存在不少局限，它以搜索窗口的全局得分作为检索窗口是否存在目标图像的标准，对于存在镂空、不规则形状的图像，这种简单的处理方式会造成错检与漏检。本文针对角标图像的多样性的需求特点，以DOT 为基础，提出了一般角标的检测算法，在保证实时处理能力的前提下提高了检测率，达到了角标广告的检测要求。

1 基于主方向模板的角标检测算法

1.1 主方向模板算法

DOT 算法［9］是一种基于全局特征的模板匹配算法，该算法将目标图像分割为网格并采用主梯度方向作为特征。

(1)特征提取过程。该算法依次对每个网格的梯度进行统计，将网格内最大的k 个梯度所对应的方向量化到n0个方向域，并用一个n0+1 位整型保存。其中低n0位对应每一个方向域，若主梯度方向落入此域内则相应位置1;若网格内最大的k 个梯度都小于给定阈值时，则将最高位置1(表明网格过于平滑)。这种处理方式对图像的特征进行了充分的压缩，大幅度降低了特征提取与匹配的复杂度。

(2)算法的匹配过程。定义相似性度量函数(Similarity Measure Function)［9］如下，该函数具有良好的鲁棒性，并返回输入图像当前窗口模板与目标图像模板两者之间对应网格的匹配结果。

式中:δ(P)是二值函数，P 为真时返回1，为假时则返回0;O、I 分别代表目标图像(Object Image)和输入图像(Input Image);do(I，c +R)为返回的是输入图像I位于位置c 处的网格R 中值最大的梯度;DO(w(O，M)，R)为返回目标图像的网格R 中较大值梯度的集合;w(O，m)为使目标图像O 对小尺度平移鲁棒的处理;M 表示处理范围，大小为［－t/2，t/2］2。

目标检测过程中，对输入图像以对应目标图像大小的窗口进行遍历，并获取当前窗口的主方向模板，根据式(1)依次对当前窗口图像与目标图像的主方向模板的对应网格进行匹配，最终返回一个搜索窗口的全局得分并与给定阈值比较，以此作为评价该窗口是否存在检测目标的标准。分别记目标图像与窗口图像对应网格的主梯度方向值为L 和D，上述的匹配过程［9］可以概括为

1.2 角标图像检测算法的思路

对于一幅常规的待检测角标图像，通常由角标部分与背景部分组成，如图1 所示。设角标图像对应的主方向模板为T(O)m×n=(oij)m×n(1≤i≤m，1≤j≤n)，输入图像当前窗口的主方向模板为T(I)m×n=(iij)m×n。其中，oij代表第i 行、j 列的网格所表示的主梯度方向。根据“位与”原则，如果仅希望角标部分参与运算，那么只需要将背景部分的数据清零，而角标部分的数据保持不变即可，即:

此外，DOT 算法简单采用每个网格的贡献对搜索窗口的全局得分相同，这种方法简单易行但易混入错误匹配的窗口。对于角标图像而言，角标部分的边缘网格得分非常敏感，很容易受到频繁变换背景的干扰。为了抑制这种干扰，本文采用加权模板为每个网格分配得分权重，通过弱化角标部分边缘网格的得分从而在一定程度上降低其可能造成的误匹配。

1.3 角标图像检测算法

角标图像检测算法的实现过程可以用图2 的流程图表示。

图2 角标广告检测算法框架

具体算法描述如下，定义视频帧当前窗口的主方向模板为T (I)m×n，目标图像的主方向模板为T(O)m×n，匹 配 模 板 为 T (M)m×n，加 权 模 板 为G(M)m×n，窗口全局得分为Ws，匹配模板屏蔽网格数为b，匹配率

算法的处理步骤如下:

(1)根据目标图像初始化匹配模板T(M)m×n，其中待屏蔽网格值设为0，剩余网格值设为并按照T(M)m×n依次生成不同尺度下的T(M')m×n。

(2)根据T(M')m×n生成当前尺度下的加权模板G(M')m×n。G(M')m×n的初始化过程如下:

①对当前尺度下的匹配模板进行T(M')m×n4－N距离变换［11］，生成G(M)m×n。

③对G(M)m×n作截断阈值化处理:

④为保持变换后全局总得分不变，令g'(i，j)=kg(i，j)，其中，

(3)读入输入图像I 和目标图像O，按照提取两幅图像的主方向模板特征，得到T(I)m×n与T(O)m×n。

(4)将T(M)m×n分别与T(I)m×n、T(O)m×n作“与”操作后，后述两者再作“与”操作，并将返回的模板与加权模板相卷积，得到当前窗口的全局得分Ws。根据之前定义的匹配率公式可以得到两者的匹配率为:

其中

(5)设遍历输入图像后存在匹配率满足阈值的窗口，则标记对应窗口所在的位置，并读取下一帧图像并返回(3)。

1.4 算法复杂度分析

设输入图像大小为U ×V，目标图像大小为M ×N，网格大小为r×r。算法第(1)、(2)步的计算复杂度是O(MN)，而主要的计算量在第(3)～(5)步，第(3)步的计算复杂度为:

第(4)、(5)步的计算复杂度:

在本文大多数的实例测试中，目标图像大小MN＜104，该情况下算法计算复杂度正比于O(UV)，通过SSE2 指令集对数据并行处理后，能达到对目标图像的实时检测。

2 实例分析及讨论

本文对DOT 算法与本文提出的改进DOT 算法在CPU:Intel i5 处理器(2.4 GHz)、RAM:4 GB、Visual C+ +2008、OpenCV2.3 的环境下进行了实现。以某电视台的实际视频进行了大量的实验，这里列选了7 种角标广告的检测查准率如表1 所示，其中加权因子q=2;改进后算法的每帧平均运算时间为22.1 ms，原DOT 算法为18.2 ms。

表1 改进DOT、DOT 的查准率比较 %

表中的实验数据表明，改进算法的查准率始终大于原DOT 算法。当角标广告背景复杂时，改进算法的检测效果明显优于原DOT 算法，可以达到实际检测精确度要求。但是改进算法运算时间略有增加，这主要是由于改进算法引入了匹配模板、加权模板而增加了计算量，但改进后的算法仍然能够实现对目标图像的实时检测。

3 结 语

视频中的图像检测作为一个新兴的研究领域，正受到人们越来越多的关注。本文针对角标广告的检测问题，提出了一种新颖的基于主方向模板的角标广告检测算法。该算法以主方向模板为基础，利用反映角标形状的匹配模板和加权模板有效抑制了复杂背景的干扰。通过大量的实例运行表明了算法的适应性、准确性和实时性。本文算法为复杂图像的检测提供了一种解决方法，在相关应用领域具有一定的推广应用价值。

［1］ Christoph H Lampert. Detecting objects in large image collections and videos by efficient subimage retrieval［C］//Proceedings of IEEE International Conference on Computer Vision. Kyoto:IEEE，2009:987-994.

［2］ 郭 丽，孙兴华，黄元元，等.距离分布直方图及其在商标图案检索中的应用［J］. 中国图象图形学报(A 卷)，2002，7(10):1027-1031.GUO Li，SUN Xing-hua，HUANG Yuan-yuan，et al. Distance Distribution Histogram and its Application in Trademark Image Retrieval［J］. Journal of Image and Graphics，2002，7A(10):1027-1031.

［3］ Olson C F，Huttenlocher D P. Automatic target recognition by matching oriented edge pixels［J］. IEEE Transactions on Image Processing，1997，66(1):103-113.

［4］ Lowe D. Distinctive Image Features from Scale-Invariant Keypoints［J］. International Journal of Computer Vision，2004，60(2):91-110.

［5］ 林传力，赵宇明. 基于Sift 特征的商标检索算法［J］. 计算机工程，2008，34(23):275-277.LIN Chuan-li，ZHAO Yu-ming. Trademark Retrieval Algorithm Based on Sift Feature［J］. Computer Engineering，2008，34(23):275-277.

［6］ 孙 林，吴相林，周 莉，等. 对扭转鲁棒的SIFT 图像匹配在商标识别中的应用［J］. 计算机工程与设计，2011，32(4):1406-1410.SUN Lin，WU Xiang-lin，ZHOU Li，et al. Application of affine invariant SIFT matching for automatic logo recognition［J］. Computer Engineering and Design，2011，32(4):1406-1410.

［7］ Herbert Bay，Andreas Ess，Tinne Tuytelaars，et al. SURF:Speeded up Robust Features［J］. Computer Vision and Image Understanding，2008，110(3):346-359.

［8］ 洪朝群，朱建科，李 娜，等. 金字塔评分改进主方向模板匹配的实时目标检索［J］. 中国图像图形学报，2012，17(5):700-706.HONG Chao-qun，ZHU Jian-ke，LI Na，et al. Real-time object retrieval with dominant orientation template matching improved by pyramid scoring［J］. Journal of Image and Graphics，2012，17(5):700-706.

［9］ Hinterstoisser S，Lepetit V，Ilic S，et al. Dominant Orientation Temp-lates for Real-Time Detection of Texture-Less Object［C］//IEEE Conference on Computer Vision and Pattern Recognition. New York:IEEE，2010:2257-2264.

［10］ Dalal N，Triggs B. Histograms of Oriented Gradients for Human Detection［C］//International Conference on Computer Vision and Pattern Recognition. New York:IEEE，2005:886-893.

［11］ Borgefors G. Distance Transformation in digital images［J］.Computer Vision，Graph-ics，and Image Processing，1986，34(3):344-371.

［12］ Lampert C H，Blaschko H，Hofmann T. Efficient Subwindow Search:A Branch and Bound Framework for Object Localization［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31(12):2129-2142.

［13］ Lu C Y，Roh M C，Kang S Y，et al. Automatic logo transition detection in digital video contents［J］. Pattern Analysis and Applications，2012，15(2):175-187.

［14］ Arafat S Y，Husain S A，Niaz I A，et al. Logo detection and recognition in video stream［C］//2010 Fifth International Conference on Digital Information Management. Thunder Bay:IEEE，2010:163-168.

［15］ 卜 江，老松杨，白 亮，等. 一种体育视频中广告牌商标的实时识别算法［J］. 自动化学报，2011，37(4):418-426.BU Jiang，LAO Song-yang，BAI Liang，et al. A Real-time Billboard Trademark Recognition Algorithm in Sports Video［J］. Acta Automatica Sinica，2011，37(4):418-426.