一种基于音频匹配的广告检测算法

赵花婷，王明敏，2

(1.复旦大学计算机科学技术学院，上海 201203;2.东方有线网络有限公司，上海 201203)

0 引言

随着数字电视的日益普及和大众欣赏水平的提高，观众对数字电视的内容提出了越来越高的要求［1］。这其中，要求减少甚至彻底去除广告的呼声最为强烈。另一方面，国家对直播类电视节目中的广告播放也有一定的限制，如广电总局规定在电视剧中不得插播广告。为满足用户诉求，改善用户观看体验，执行国家政策，数字电视运营机构需要对直播和回看的电视节目中的广告进行排查。然而，目前大多采用人工标注的方式来排查电视节目中的广告，在电视台数量和节目都极大繁荣的现在，人工排查需要耗费相当大的人力和时间。因此，如何高效、自动地在电视节目中检测广告成为一个热门的、迫切需要解决的问题，具有很大的现实意义和应用价值。

1 研究现状

目前，主流广告检测算法大致分为2类［2］。一类方法基于一段特定的广告会在多个时段、多个电视频道中重复出现这一事实，将已知的广告视频段通过镜头切割等手段提取关键帧，并提取一些图像特征作为广告特征，再利用比较图像特征的方法来检测节目视频中的广告，这类方法被称为视频拷贝检测［3］。除了仅能在广告样本库内检测广告这一局限之外，这类方法对存储量的要求也比较大，对每个广告样本都需要提取并保存若干幅关键帧图像，有的方法还需要对这些图像进一步提取高达数百维的特征，以提高检测的准确率。随着广告库中广告数量的增加，存储量也随之急剧增加。

另一类方法是基于机器学习［4］的方法，挑选一批有代表性的广告样本，从中定义一些能够代表广告特征的特征集，然后训练这些特征集得到分类器并以之来对视频进行分类。然而，这些方法对训练集的依赖性很强，采用不同样本进行训练所得的分类器的差别比较大。随着广告拍摄手法的多样化，特别是近年来出现的一些类似电视剧片段的广告，这类方法面临越来越大的困难。

也有人提出了将音频和视频相结合的广告检测方法［5］，通过提取广告视频的最具代表性的帧(通常是最后一帧)来分割广告段和非广告段，避开了对广告区间的搜索。这种方法本质上仍然是基于视频的机器学习的方法，不同之处仅在于通过检测广告的静音段来辅助定位广告的边界，在处理复杂背景条件的广告时仍然力不从心。

本文借鉴视频拷贝检测的思路，结合音频检索的相关技术，提出一种基于音频的检索方法，在保证查准率和查全率的基础上，大幅度降低了对存储的需求。

2 基于声谱图的音频匹配

本文通过音频拷贝检测即音频匹配算法实现广告检测。目前，借由计算机视觉方法来解决音频识别问题已经成为音频领域的一个重要研究方向。本文采用文献［6］的基于计算机视觉的音乐识别算法进行音频拷贝检测。

本文将音频匹配问题转化为图像检索问题:(1)将音频数据转化为声谱图，并进一步提取局部特征描述子;(2)以局部特征描述子构造标准哈希索引，为查询片段快速检索候选的音频序列;(3)使用随机抽样一致性算法，将查询片段对每个候选序列进行时域上的对齐，根据对齐后的似然概率对该片段进行非广告或广告的标记。

2.1 音频图像化

为使图像化的音频数据兼具局部特性与鲁棒性，算法使用短时傅里叶变换(STFT)［7］将音频数据转化为声谱图。该声谱图表示了33个频域带宽上包含的能量，并在大小为0.372 s的滑动窗口上每11.6 ms测量一帧。

图像化后的数据可应用计算机视觉技术提取图像特征，构建音频特征库，用于实时的检索匹配。

2.2 局部特征描述子

直接利用声谱图进行匹配，结果不精确且效率低，因此提取局部特征描述子，使得特征同样兼具局部特性与鲁棒性。Viola与Jones提出的目标检测框架中的Haar特征能够满足以上要求［8-9］。根据Haar特征的可控参数，针对本文的可选滤波器约25000个，仅需从中筛选出M(=32)个参与特征提取。

为筛选滤波器，采用不对称成对Boosting算法，其中训练样本是成对的特征向量，训练过程对正负样本使用不对称的迭代操作。为此定义分类器为H(x1，x2)→y={－1，1}，x1、x2表示 2 段声音的声谱图，当x1、x2同源时y=1，反之 y= －1。分类器H 由M组弱分类器hm(x1，x2)及可信度cm组成。hm(x1，x2)由一组滤波器fm及阈值tm组成:

假设有特征x从分布D中随机抽取，有fm及tm，使得P(fm(x)＜tm)=p，0≤p≤1。若从D中独立随机抽取两段不匹配的特征x1、x2，则有:

当采样空间足够大时，至少一半的负样本将被错误地标记为匹配。参考文献［10］得到非对称成对Boosting算法，其中只有错配的正样本才会更新权重，并且正负样本权重之和分别被归一化到0.5。所有M个弱分类器hm(x1，x2)的线性组合得到最终的强分类器H(x1，x2)。显然H(x1，x2)并不用于最终系统结果，其功能是挑选出M个最优滤波器。

由此每帧滑动窗口可根据M组fm及对应的tm，计算出一个M比特的局部特征描述子。

2.3 检索音频匹配

在检索阶段，对查询片段的每个特征描述子，在音频特征库中都进行相似性最近邻搜索［11］。由于该特征描述子出人意料地精确，本文直接使用标准哈希算法［12］进行检索。为了能够容忍一定程度的噪声，使用汉明距离［13］为2以内的特征描述子作为候选匹配。

当所有的候选匹配被找到，要将测试片段与候选序列对齐。为此，本文采用文献［14］中的随机抽样一致性算法RANSAC［15］。实验表明，RANSAC在500次迭代之内收敛。

形式上，现有n个特征描述子组成的特征向量xr=，...)，为其与数据库中某音频片段特征向量)的相似度建模:

其中xr－o表示xo和xr按位取异或得到的向量。yi取1则来自某个音频源文件;若值为0则来自于遮挡。在训练阶段，使用EM算法［16］自动标记出数据的yi。

每给定一个查询音频片段，提取xr，根据式(2)在数据库中查找满足最大P(xr|xo)的xo，最后为了平衡正确率和召回率，根据阈值T来判断查询片段是否来自音频库:

由贝叶斯公式得，P(xr|xo)等价于后验概率P(xo|xr)。

3 基于音频匹配的广告检测算法

将音频匹配算法应用到广告检测中，首先构建广告音频样本库，从原始广告样本中抽取出音频数据，转换为声谱图，进而计算其局部描述子，组成广告音频库。

3.1 构建音频拷贝检测样本库

图1 从广告片段构建声谱图与特征描述子

如图1所示，根据第2节中的算法描述，对广告视频语料库进行如下处理:

(1)抽取广告视频流的音频信号。本文的广告视频流以MPEG2-TS格式传输。MPEG2-TS是一种传输和存储包含音频、图像与通信协议各种数据的标准格式，可以直接以FFMPEG标准方法提取出其音频分量，以wav格式保存。该音频数据为原始的1D的音频振幅信息。

(2)对音频数据进行短时傅里叶变换得到时频域的声谱图。这是将音频数据的频率信息图形化表示的形式。在0.372 s的滑动窗口上提取33个带宽上的频率信息，并绘制时域上的频率密度。短时傅里叶变换可写作:

其中w(t)是窗函数，x(t)是原始的音频数据信号。X(t，ω)是 w(t－ τ)x(τ)的傅里叶变换。随着 t的改变，窗函数在时间轴上滑动。经过w(t－τ)x(τ)后，信号只留下了窗函数截取的部分做最后的傅里叶转换。经此得到时频域图形如图1中的声谱图。

(3)提取声谱图的局部特征描述子。使用计算机视觉方法，对声谱图提取Haar特征。其中按2.2节算法已经预先得到M组fm及对应的tm。Haar特征并不作用于像素上，而是作用于矩形区域上，这可以使用积分图快速计算。在一个已知位置大小的Haar特征矩形框内求和，计算方法如下:B表示黑色区域，W表示白色区域;图2(a)中两个矩形区域的和为W－B的值;图2(d)的和为W－(B1+B2);图2(c)的和为W1+W2－(B1+B2)。

图2 Haar特征举例

将加和的结果与Haar特征对应的阈值tm做比较，得到一个比特，大于tm值为1，反之则为0;共有M个特征fm，组成一个M比特的局部特征描述子。特征描述子组成广告音频特征库，以描述子为键值建立标准哈希表，用于后续检索。

3.2 检测过程

对给定的待测音频序列，先取［0，m］s和［m，2m］s两段音频，按照2.3节算法描述分别为这2段音频在广告音频库中寻找匹配，进而根据匹配结果将音频识别为广告段或非广告段。如果2段音频的识别结果不同，则按照3.5节的方法，确定分界点K0(若2段音频的识别结果相同，则K0=2m)。然后，从分界点处继续向后取2段长度为m s的音频进行匹配与识别，…，以此类推，直至序列的末尾。在本文中，m设为3 s，这是通过大量实验得出的能保证音频匹配算法稳定的最小时长。

3.3 检索候选匹配

在线检索阶段，对实时视频流以3.1节中相同的处理方式得到特征描述子，在已建好的哈希表中进行相似性最近邻检索。这样每个测试特征描述子都可找出若干候选匹配。为从候选匹配中筛选最佳匹配，这里使用RANSAC算法。

RANSAC算法具体操作如下:(1)已知在线检索片段的特征描述子序列;(2)在候选匹配集合上迭代地做以下操作:①随机选取一个候选匹配;②根据已选匹配，将所有检索片段的特征描述子序列与候选序列一一对齐，依式(2)计算似然概率得分;③得分最高者且满足式(3)的候选为最终匹配结果。经过RANSAC后未成功找到匹配，则该序列标记为非广告片段，否则标记为广告片段。

由于是对音频流建模，在非同源音频仍然相似的情况下，会造成误判。因此，需要对音频匹配的结果进行平滑分析，才能得出最终结果。

3.4 结果平滑

广告序列中不会夹杂非广告序列;广告序列具有特定的长度如5 s、10 s、30 s;电视节目往往时间较长且连续。基于以上事实，可以对广告检测结果进一步平滑修正。

平滑规则如下:(1)若广告序列长度低于T1，则标记为非广告序列;(2)若非广告序列长度低于T2，则标记为广告序列。经测试，当阈值T1和T2均设为3.5 s时即可将查全率结果修正到满足实际需要。

3.5 确定分界点

假设有2段相邻的长度均为 m的音频 Ai和Ai+1，如果它们同时被识别为广告段或者非广告段，则视它们中间不存在分界点。反之，则之间存在分界点。设 Ai和Ai+1对应的时刻区间分别为［Tj，Tj+m］、［Tj+m，Tj+2m］，先将 Ai+1向前移动 1 s(即取［Tj+m－1，Tj+2m－1］段)进行检测，如果检测结果和 Ai一致，则分界点在 Tj+2m－1，否则继续向前移动1 s，…，以此类推，直至Ai和Ai+1重合，此时分界点为Tj+m。确定分界点过程中，每次平移1 s是基于以下事实:电视节目的分界点位于整数秒附近。这个事实是通过检查大量的真实广告数据得出的，也就是说几乎没有长度是7.3 s或者10.5 s的广告，因此移动1 s不会导致分界点的错判，文献［5］给出的静默帧出现的位置在整数秒附近，也证明了这一点。

4 仿真实验结果及分析

本文实验基于私有数据集。数据集共包含广告7441条，平均时长大约为14 s，这些广告构成了本文的广告视频库。

图3 音频匹配检测结果

单纯使用音频拷贝检测算法进行广告检测，如图3所示，容易造成漏判和误判。因此，直接引用音频拷贝检测不能满足实际需求。

图4 平滑检测结果

使用音频拷贝检测算法进行广告检测，并使用3.4节的优化后，明显减少错判率，如图4所示。

图5 加入短时间静默段检测结果

利用广告序列与非广告序列切换时往往有一段时间的静默这一特性，将静默帧前后的序列经过投票方式进行统计，前后段落中含有的非广告序列投票高，则该短时段落为非广告序列，反之为广告序列。图5中查全率明显提高。

图6 与参考文献方法对比

图 6 为 Duan Ling-Yu［17］、Hua Xian-Sheng［4］、音视频结合广告检测算法［5］与本文算法的性能对比图。由于视频拷贝算法需处理的信息量过大，为提高性能往往需要舍弃大量的图像信息，必然导致精度的下降。本文采用的算法，使用计算机视觉算法实现音频拷贝检测，信息内容稳定而数据量较少，可以在保证精度的前提下提高运算效率，与同类算法相比有明显的优势。

以上所有的测试结果均基于单帧的检测结果，即11.6 ms的单个特征描述子的检测结果;实际中由于广告和非广告序列具有时间上的连续性，结合3.3节与3.4节的方法，将广告序列平滑至视频段落的检测上，可以将检测结果的查全率提高到95%以上。这与文献［5］以及文献［4，17］中的算法相比都有长足的进步。

为满足商业需要(广告误判为非广告后果非常严重)，广告拷贝检测应保证查全率尽量逼近100%，这样才有可能通过加入人为干预，使最终的查准率和查全率均达到100%，才具有可靠的商业价值。

5 结束语

本文提出了一种基于音频匹配的广告检测算法，利用广告片段的音频特性，构建广告音频特征库。使用音频拷贝检测算法解决广告检测问题，使用计算机视觉方法解决音频拷贝检测问题。提取广告的音频信息，使用STFT获得声谱图，通过非对称成对Boosting方法获得滤波器及阈值集合，对声谱图加窗编码，以编码后的特征描述子集合作为广告特征库，并以此进行检索匹配。该方法的优点是:(1)充分利用了音频特性在广告片段中的稳定性、广告与非广告之间有静默片段、广告具有标志性音乐等，检测结果高效而准确，大幅提高其商业价值;(2)音频特征描述子相比视频特征能更有效减少数据库的存储空间;(3)音频特征可以在音频库中以常数级时间检索到候选，可以满足实时性的要求。对于如何提高音频检测的准确性，以及如何采取更合理的策略处理包含较长静默段的广告，将是进一步研究的课题。

［1］Lienhart R，Kuhmunch C，Effelsberg W.On the detection and recognition of television commercials［C］//Proceedings of the 1997 IEEE International Conference on Multimedia Computing and Systems.Ottawa，Canada，1997:509-516.

［2］Ke Y，Sukthankar R，Huston L.Efficient near-duplicate detection and sub-image retrieval［C］//Proceedings of the 2004 ACM International Conference on Multimedia.New York，USA，2004:869-876.

［3］Sadlier D A，Marlov S，O’Connor N E，et al.Automatic TV advertisement detection from MPEG bitstream［C］//Proceedings of the 1st International Workshop on Pattern Recognition in Information Systems.Setubal，Portugal，2001:14-25.

［4］Hua X S，Lu L，Zhang H J.Robust learning-based TV commercial detection［C］//Proceedings of the 2005 IEEE International Conference on Multimedia and Expo.2005:149-152.

［5］丁汝一，杨宁，董道国.音视频相结合的广告检测算法［J］.计算机工程与应用，2012，48(22):184-188.

［6］Ke Y，Hoiem D，Sukthankar R.Computer vision for music identification［C］//Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2005:597-604.

［7］Jurado F，Saenz J R.Comparison between discrete STFT and wavelets for the analysis of power quality events［J］.Electric Power Systems Research，2002，62(3):183-190.

［8］Jones M，Viola P.Face Recognition Using Boosted Local Features［R］.Technical Report MERL-TR-2003-25，Mitsubishi Electric Research Laboratories，2003.

［9］Viola P，Jones M.Rapid object detection using a boosted cascade of simple features［C］//Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2001，1:511-518.

［10］Schapire R E，Singer Y.Improved boosting algorithms using confidence-rated predictions［J］.Machine Learning，1999，37(3):297-336.

［11］Indyk P，Motwani R.Approximate nearest neighbors:Towards removing the curse of dimensionality［C］//Proceedings of the 30th Annual ACM Symposium on Theory of Computing.1998:604-613.

［12］Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing［C］//Proceedings of the 25th International Conference on Very Large Data Bases.1999:518-529.

［13］Bhattacharryya D K，Nandi S.An efficient class of SECDED-AUED codes［C］//Proceedings of the 1997 International Symposium on Parallel Architectures，Algorithms and Networks.1997:410-416.

［14］Lowe D G.Object recognition from local scale-invariant features［C］//Proceedings of the 7th IEEE International Conference on Computer Vision.1999，2:1150-1157.

［15］Fischler M A，Bolles R C.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.

［16］McLachlan G，Krishnan T.The EM Algorithm and Extensions［M］.Wiley-Interscience，1997.

［17］Duan L Y，Wang J，Zheng Y，et al.Segmentation，categorization，and identification of commercials from TV streams using multimodal analysis［C］//Proceedings of the 14th Annual ACM International Conference on Multimedia.2006:201-210.