对目前常见的快速目标检测模型进行分析。部分模型将融入在14年三月发布的eagleeye的语法树目标检测模型中，敬请期待。
众所周知sliding window策略是目标检测中的基本检测方式，我们需要遍历图像中的每个点以及以该点为起始点的不同大小的矩形窗口，然后依靠所采用的评分方式对检索窗口进行估分，从而判断当前检测位置是否是目标。我们可以清楚的看到，这样的遍历空间是巨大的，不可能实际在应用中使用。因而需要采用一定的简化策略。下面的方法就是讨论如何降低检索空间的方案。
为了降低检索空间，将图像分割信息引入，使其作为检索的预测位置（Segmentation as Selective Search for Object Recognition）。下面来简要分析一下如何引入这些分割信息的。
这种想法是基于这样的假设，检测目标一定会存在于某一个分割区域当中。基于这样的假设，对图像分割的要求就很高了，不能将检测目标分割到若干区域当中，又不能将分割容忍度过度放大，导致单一分割区域过大，从而无法实现精确的目标检测与定位。作者采用hierarchy segmentation algorithm,从而保证在某个分辨率层上的分割中，目标物体存在于一个紧致分割区域当中。对于图像分割的问题已经描述清楚，现在需要说说如何进行模型训练问题。为了清楚的说明，请看下面的结构图：
（1）训练数据的产生
在训练数据上，标注出目标区域，如上图中绿色高亮区域的奶牛，将这些标注区域作为正样本。使用hierarchy segmentation algorihtm产生目标假设区域（也就是若干个分割区域）。可以作为假设区域的限制是，分割区域的外接矩形和目标标注区域的重叠度在20%~50%之间，并且和其他的负样本不能有超过70%的重叠。我们将这些假设区域作为负样本。在有了正样本和负样本后，便需要进行特征提取，固然这里特征提取有多种方式，作者采用的是SIFT + bag of words。OK， 现在可以ＳＶＭ模型训练了。
（2）迭代训练
采用迭代训练方式，在每次训练完成之后，挑选出false positives样本，并将其加入到训练样本中，其实这便是增加了困难样本数。使用其进行模型训练，直到收敛（精度不在产生变化）。
注意：这种训练方式似乎没有boost的方式有效。
评论：这种想法的优势主要在于引入分割信息，并将其作为目标假设区域，从而只对这些假设区域进行目标检测。这样的处理方式极大地降低了检索空间。
Christoph H.Lampert 提出的efficient sub window search 从另一个角度加速检测效率。作者提出Branch-and-Bound Search， 其主要思想便是不应该浪费大量的时间来评估大多数的候选检测区域的quality function（分类器响应），而是应该直接检索那些可能含有最大分数的区域，忽略其它的可能区域。那么如何来实现这样的杰出想法呢？
下面首先描述一下其主要的实现策略。迭代地切分参数空间（图像中所有可能的矩形区域）到离散的子区域，并且同时保持这些子区域拥有最大的质量分数上届。
下面我们详细描述并给出算法框图
首先对矩形使用top,
bottom, left 和
right坐标值进行标示。使用坐标区间的形式来表示区域的不确定性
，其中
。也就是用其表示一组矩形集。
对于每个矩形集合，我们计算一个在这个集合中quality function(分类函数)在所有矩形区域上能够取得的最大分数，并将其作为上届。当发现一个仅仅含有一个矩形的矩形集合时，并且其quality function分数至少要和所有其他的候选区域的分数上届一样好，那么ESS算法终止。这就保证了一个全局最大分数被发现。
ESS以一种最佳方式在那些候选集合上进行检索，其总是检索那些看起来有最大quality bound（分类响应分数）的区域。然后，候选集合沿着那个最大的坐标区间分割成两半，形成了两个较小的候选子集。如果那个最有希望的候选子集仅仅有一个矩形区域，那么算法停止，这个矩形区域就是目标区域。见下面的伪代码：
这时有人会说，如果一副图中存在多个目标怎么办呢？一个一个检索，找到一个目标区域后，将其清空，然后寻找第二个。
接下来有人会问了，这个quality bounding function如何可以快速估计啊？如果估计太复杂的化怎么用啊？没错我们接下来，进一步瞧瞧quality function 以及 quality bounding function。
作者给出了quality bounding function的两条特性：
其中是quality function，
是quality bounding function，
表示矩形集合，
表示矩形。
下面我们举一个简单的例子，来看看如何将这种想法应用在实际情况当中，以及瞧瞧如何设置quanlity funciton和 quality bouding function。
在举例子之前我们应该清楚地认识到quality function 以及 quality bounding function 必须能够快速计算。
使用bag of words 进行 non-rigid 目标检测
使用SIFT对来抽取局部图像的描述子，然后进行bag of words 表示，从而产生矩形区域的直方图特征。所使用的分类器是线性SVM。注意，这个特征直方图，其实是由矩形区域中每个特征描述所属的word构造而成。
决策函数是，其中
表示点积操作，
是训练样本的直方图特征，
和
是权向量（weight）和偏执（bias）。接下来我们会产生一个重要的变形，将决策函数写成在矩形区域内的每个特征点的贡献（
）形式
其中表示的矩形区域中的特征点
所属的那个word的索引，
表示在矩形区域内的特征点的个数。
这种形式就允许我们首先产生一副响应分数积分图，然后便可以快速计算任何矩形区域的quality funciton 值。
好了，现在我们需要构建quality bounding function了。首先我们对quality function 进行分解，，其中
表示正训练样本的贡献（注意
的表达形式），
表示负训练样本的贡献（注意的表达形式）。其次，用
表示在矩形集合中最大的矩形，
表示矩形集合中最小的矩形。那么quality bounding function 则表示为
哈哈，至此我们构建出来了。
至此，我们从如何降低检索空间（使用分割信息提供线索）和 如何加速检索（其实也依靠了特殊决策函数和特征抽取的贡献）两个方面进行目标检测的加速。接下来，我们看看如何从决策函数的角度来加快计算呢。
我们应该知道，目标检测时，除了需要遍历的检索空间大外，对每个检索位置处的分数评估过程也是极度耗时的，尤其在分类模型极度复杂的时候，如DPM模型。接下来，我们看看有什么策略呢？
在Sparselet Models for Efficient Multiclass Object Detection中，作者提出了稀疏模型。接下来让我们仔细瞧瞧，这是怎么回事？
我们结合上面这张算法流程描述图来说明算法是如何工作的。事先说一下，这篇论文是针对的DPM目标检测模型进行分析的。由于DPM中需要有大量的filter 与 特征图像金字塔进行卷积，然后计算每一点的分数，那么这里作者的想法是降低计算卷积的代价。作者提出，将filter稀疏化处理。稀疏化的方式是这样的：
我们想要发现一组fitler dictionary ，用其在某受限条件下来估计part filters
，从而有如下的优化方程
其中称为activation vector。
现在，如何进行卷积计算呢？
哈哈，可以使用图像特征金字塔和filter dictionary 进行卷积，然后使用一系列activation vector 来重构出图像特征金字塔与相应的 part filter 卷积的结果。
我们需要说明一下，这样的构造方式在多类识别时应该较为有效，因为所有的filter共用一套filter dictionary。因而，可以实现快速计算卷积的目的。
Star Cascade 模型
不可否认Cascade模型已经成为了加速的标配策略
（待续）eagleeye 支持
From Coarse To Fine 模型
这个不错的想法来自于A coarse-to-fine approach for fast deformable object detection。这个目标检测算法是针对于DP（变形部分模型） 模型进行加速的，加速的核心思想是降低检索空间。如何实现的呢？ 从标题上我们可以想到，这必然是建立一个层级模型，从低分辨率到高分辨率。接下来，我们仔细看看如何进行建模并且加速的。
最低分辨率level r = 0 对应于树的root。这是一个维度为w * h的ＨＯＧfilter 。在第二分辨率层 level r = 1， HOG特征分辨率加倍，以至于每个part filter 的维度依然是w * h。特别地，对于root filter 所检测过的位置，需要进行一个 m * m大小的邻域最大值寻找，只有是最大值的位置，才会进行接下来的计算。对于保留下来的每个位置，在下一层的parts 依然要在 m * m邻域内检索，来探索deformations。
由于对partial occlusion，blurring 或者其他噪声敏感，引入lateral connection（这就是上图中得红色点划线）。这其实类似于额外的集合约束。这种约束致使siblings 的运动保持一致性并且提高了模型的健壮性。接下来，我们用数学式子进行进一步的描述。
在root level， 仅仅有一个filter （w * h * 31）。然后将其分成四个子部分，并且HOG 特征分辨率加倍，从而导致了四个 w * h filter，其分别对应四个子部分。这个过程不断的重复，直到达到指定层深。
让表示是P 个part的位置。每个
在一个离散的位置集合
（HOG cells）中变化。给定一副图像，构型
的分数计算公式如下：
其中是parent-child 边（蓝色连接线），
是lateral connection（红色点划线），
是模型参数。
衡量在位置
处的图像的appearance 与 i-th
part 之间的兼容性。这用下式给出：
其中右侧第一项是特征描述，第二项是对应的模型参数。惩罚当前part的
与其对应的parent
之间的偏移。这是一个二次代价函数：
其中
惩罚sibling-to-sibling 变形，其由下式给出：
我们应该注意，除了二次变形代价之外，可能的构型还需要受到一些其他的限制，称之为parent-child 限制（ ）
至此，模型已经建立完成，接下来的任务就是如何记性分数推断了。采用动态规划方法。
参考文献
1 Koen E.A. van de Sande Segmentation as Selective Search for Object Recognition
2. Christoph H.Lampert Beyond Sliding Windows: Object Localization by Efficient Subwindow Search
3. Christoph H.Lampert Efficient subwindow search: a branch and bound framework for object localization
4. Hyun Oh Song. Sparselet Models for Efficient Multi-Class Object Detection
5. Pedro F.Felzenszwalb Cascade Object Detection with Deformable Part Models
6. Jianguo Li, Yimin Zhang Learning SURF Cascade for Fast and Accurate Object Detection
7. Fast Accurate Detection of 100,000 Object Classes on A Single Machine
8. Marco Pedersoli A coarse-to-fine approach for fast deformable object detection