基于树形检测器的多标志识别

0 引言
自动的电视台标检测和识别已经在多媒体领域获得非常高的关注度。如今，多数的手机都具备了摄像头功能，所以人们可以随心所欲地拍摄各种事物，然后利用各种算法去分析处理获得的图像。本文中，展示一个系统一利用手机内置摄像头帮助人们识别电视频道信息。日常观看的电视频道就有几十个不同的台标，所以可以把这个问题看作是一个多类检测问题，而单类的检测即识别，最终就实现了多类识别。
对于单类检测问题，Viola和Jones给出了state-of-the-art算法。他们先训练了一系列节点分类器去检测图像里的每一个子窗口，只有那些能够通过所有节点分类器的子窗口图像才被认为是正样本。吴将Voila的工作简单地拓展到了多视角人脸检测上，为每个独立的人脸视角训练了一个不同的 cascade结构，并且并行地运用它们进行检测。但是当正样本的类型数量增加时，这个方案所花费的检测时间也是线性增长的，而这个代价是我们无法负担的。Torrobla提出了一种新的boosting框架，命名为jointboosting。他将N类分类问题转化为N-1个两类分类问题，然后自动地共享相同的弱分类器。尽管它的检测器可以共享特征，但是当检测目标时，它仍然需要计算全部特征，所以它并不是一个快速检测框架。
近些年来，树形检测器被引入了多视角人脸检测应用中。许多研究者更加偏爱于这种树形结构，例如，Fleuret和Geman的scalar tree，Li等人的金字塔结构，还有Huang chang的广度优先搜索树。在他们的工作里，Huang的工作最有新意，他提出来一种新的输出一个布尔矢量的boosting算法，取名为vector boosting。由于它具有良好的性能，本文选用它作为分叉树的部分。有别于多视角人脸的并行结构，经验证明直接构建一个由粗到精的树是比较困难的。故此，本文设计了一种根据不同组合的误报率来构建分叉树的方法。详细的方案会在1．3中阐述。
本文的其他部分是这样组织的：在1．1小节中，本文介绍所采用的特征集，然后简要地描述下普通cascade结构和soft cascade结构。在实验过程中，作者测试了本文算法的精确度和检测所需的平均特征数。

1 检测器框架
在实验中，本文采用了一架摄像机来拍摄电视节目的全屏幕图像。考虑到此方法的通用性，不假设关于台标位置的先验信息(尽管台标通常会出现在屏幕的上部)。为了可以检测出台标，本文先使用了一个分类器对大量的不同尺度和位置的子窗口进行扫描。因为多数的子窗
口都是背景，而背景的轮廓特征不明显，所以可以将任务分割成两个部分：首先是尽可能早的拒判掉非台标的子窗口，然后是区别每个台标属于哪个频道。接下来描述下算法的第一部分。

1．1 通用检测器
Viola在他的人脸检测中成功地运用了adaboost结构和由haar特征构成的弱分类器。OpenCV也给出了该算法的代码。许多目标检测的问题也经常用到Viola的检测框架，有时也只是用别的特征集替换了haar特征。
如图2所示，电视台标的主要属性就是它的轮廓特征。在行人检测中，基于梯度方向直方图(HOG)的特征是一种描述轮廓的十分有效的特征。这个特征的缺点是它的输出是一个矢量，所以需要用一个基于支持向量机的弱分类器，但是它要花费大量的计算时间。文献提出了一个EHOG特征，它只输出一个值，并可以很容易地被Adaboost算法使用。

因此在本文的台标检测器中，使用了EHOG特征。对于一副训练图像，计算一个块Rb里的梯度直方图，然后在n个方向分别统计梯度幅度的总和。


n是HOG特征的维数(在中，n=9)，本文中设置为6。
然后，本文使用了中定义的主方向梯度D概念，D是上述区间集的一个子集，即，并计算对应D方向的EHOG特征：

为了快速地计算特征，本文也应用了积分直方图方法。
本文采用了EHOG特征和gentle adaboost训练了一个普通cascade结构，然后在所有桩分类器中收集全部的弱分类器，并用校正算法重新排序它们，得到一个新的"soft cascade"检测器。


本文定义为前t个弱分类器的响应值的和。运用了校正算法后，可以得到一个迹数组trace=(r1，r2，…，rN)。当对一个样本x做决策时，加上每一个弱分类器的响应值ht(x)，然后就将ht(x)和rt进行比较，如果低于，就立刻拒绝该样本。Soft cascade结构的性能要优于Viola的Cascade，在获得相当的检测性能时，它需要较少的特征数。这些将会在后面的实验中展示。
第一层的普通检测器可以拒判大量的背景图像，却还不能区别不同类的台标。为了做进一步处理，仍需要一个可以解决多类别分类问题的算法结构。
1．2 分叉树
在Huang的工作里，他构建了一棵由粗到精标注了人脸的不同视角的树。分叉树上的每个节点分类器采用了矢量boosting算法训练得到，依靠假设输出空间的矢量化来解决多类问题。举例说明，在一个节点分类器上，有四个可能的输出矢量((0，O)，(0，1)，(1，0)，(1，1))：(0，0)代表着该样本的检测将终止于当前节点。(0，1)，(1，0)，(1，1)代表着该样本将会通过哪个孩子节点。
在文献中，相邻的视角在分叉树里的距离也很近。全部15个不同视角是根据旋转角度平分成15份得到的。由于在本文的多台标检测中没有关于某两个台标是近邻的先验知识，所以不能依靠经验来构建一棵由粗到精的分叉树。例如，当面对图2中的6类台标时，在分叉树的根节点上，不知道该如何将它们划分成两个子节点。如果将明显不同的台标放在同一个节点里，训练算法将会耗费更多的特征才能获得一个相对较好的分类。基于这样的想法，作者认为一个较好的划分应该是在固定的迭代次数上利用矢量boosting训练得到一个更好的分类结果。
假设有N类正样本集，在第一层分叉节点上，就有2N-1-1种组合数可以将一个包含N类的集合划分成两个正样本子集。
如果盲目地寻找一个合适的树，总的时间复杂度会是log(N)*2N，这是无法实现的。为了解决这个问题，以下本文将引入一个贪婪搜索算法。
在一个二维矢量boosting算法里，正样本数据被标示为(O，1)或者(1，0)，负样本数据被标示为(-1，-1)。本文用{S1，S2，…，SN}来表示所有的数据，那么左边子节点的数据集就是，右边子节点的数据集就是，这里Dleft和Dright是(1，2，…，N)的子集。
本文设置检测率为O．995，迭代次数为10。误报率被用来评估算法性能。在矢量boosting算法中，判决准则如下：


对于本文的6类台标数据集，将给出节点划分的算法流程，这里一个二进制串001001表示一种划分模式，0代表进入左子节点，1代表进入右子节点。
算法1划分节点集合的贪婪搜索算法
输入：{S1，S2，…，SN}
输出：划分模式p
初始化p：p={00，…，0}；
初始化一个包含比特串的空列表；

外层循环i=1:N-1