图像理解及目标检测的一种快速算法：Objectness Detection

图像理解及目标检测的一种快速算法：Objectness Detection

今晚是平安夜……没啥活动，想起来有快一月没有写博客了，最近实在是事情多，要开题了，一直科研和做实验作报告……写博客的时间就少了，最近看了不少论文，又get了很多新技能，分享一个出来哈哈~马上就元旦啦，祝大家新年快乐~

最近一直在研究图像显著性相关的算法，算是当前的一个研究热点吧，对于图像的理解上有着很大的帮助。上周的时候看到了程明明老师所做的相关的工作，非常受启发，并且在主页上也提供了代码供研究，工作非常的Solid，很敬佩。
这次我要分享的是他的一篇论文：
BING：Binarized Normed Gradient for Objectness Estimation at 300fps
发表在CVPR14是，非常好的文章，不过可能由于是会议，因此文章中的一些细节可能没有仔细的阐述，因此我把我的理解写在这里供大家参考一下，也希望能够得到指正！这篇文章主要是做Objectness检测的，和图像的显著性有着类似的特点，因此我也顺带研究了一下，扩展思路。

这篇文章提出的方法主要应用于快速检测图像中的Objectness区域，其亮点有：

1. 比以往提出的算法都要快很多，从题目上就可以看到，每秒钟达到300张图像（据文章所述，速度超过了TPAMI2012 2013，CVPR13的bestpaper）；
2. 用到了比较简单的特征，稳定，效果好。

Objectness的定义：

Measuring the objectness of image windows. Alexe, B., Deselares, T. and Ferrari, V. PAMI 2012. 是这样说的：
What is objectness?
The objectness measure acts as a class-generic object detector. It quantifies how likely it is for an image window to contain an object of any class, such as cars and dogs, as opposed to backgrounds, such as grass and water.
通俗的讲，就是通过一个窗口将物体框出来，并且这个窗口能够最大程度的包含其中的物体，无论这个物体是何物。
以往的检测方法是怎么做的呢：
通过滑动窗口的方法，一个个仔细判断，这样首先是效率上很低，其次是如果从仿生学的角度，人类也不是这样判断图像中是否有物体的。
这篇文章提出的方法抛弃了这种低效的方法，提出了一种通用的特征，在通过学习训练的方法通过特征对图像中的窗口进行筛选，并且为了提高运算速度，将特征进行二值化，并将其紧凑化表示，通过原子操作（位操作）来加速计算。

在阅读这个文献之前有几个问题需要理解：

1. 既然不采用滑动窗口法，那么通过什么方法来选取其中可能区域？
2. 作者采用的features是什么？如何通过二值化进行加速
3. 采用什么模型对数据进行训练，以及如何训练，训练什么参数
4. 通过什么公式来估算Objectness值？

文章的理解：

问题4：
这里先把估算Objectness的公式列出来


在这里W为我们要学习的模型，通过训练得出的一个参数；gl为提取的特征；l代表着位置等参数 ol即为估算的Objectness值；
问题1及问题2：
如何选择窗口：算法首先产生一系列不同大小的梯度图像出来，通过NMS（非极值抑制算法：这个算法我之前也没有接触过）选取出一系列的候选窗口（大小均为8*8）
为什么是这样？
首先先看下图：

可以看到算法采用的即窗口内8x8的梯度特征；关于这个特征，作者是这样解释的：
因为图像中的物体存在这一些闭合的边缘，因此其存在这一些显著的轮廓，可以通过梯度图像表现出来，其次呢，这个特征在resize到指定大小后比较稳定，从上图的图c中可以看出来。
关于8x8的窗口，作者应该是基于计算效率以及通过试验得到的参数吧。
那么新问题来了：如何对这个特征在算法上进行Speedup
这时候我们大概有个思路了，将提取好的特征通过上面的公式2、3进行计算，可以预想，这里的全都是矩阵，存在着大量的乘法，并且一旦窗口过多后，虽然算法简单，但是仍然会消耗大量的时间，因此作者对此做了改进。
改进方法： 首先对学习到的模型W进行离散化的逼近：

这个算法看着太眼熟了，应该在矩阵论里见过，这个过程有点像矩阵的分解，将其分解为几个单位矩阵类似的。总之通过这种方法将原来的存在这很多变量的矩阵变成了系数以及值仅有0，1的矩阵。这步也是为了后面做准备；
逼近后原来的公式1就可以变成上面那样简单的计算公式啦：（这里的一些细节可以参考原文）
下面更精彩了，离散化NG特征，也就是BING特征，这部分我在第一遍看时没理解，可能由于篇幅原因有些细节没有具体解释（嗯……也有可能是我没有理解到位。。。），今天又反复阅读和计算了下，才算有点理解，这里就把我的理解放上来（我还没仔细的看代码，如果后面看了发现有误我还会回来改的~欢迎指正！）：
首先文章的目的是将原有的特征离散化，在离散化之前我们首先要知道在梯度图中，每个位置的梯度值的变化范围是0~255，因此可以用8bit来表示，用公式来说就是：

那么原来的8x8的窗口，用位（bit）来表示就是（8x8）x8维了，可以想象成一个立方体，每一维都是由某一位上的值{0，1}组成的；在了解了这个后后面的就好理解了:
针对每一维，采用算法2（下图）进行逼近，因为8x8=64，因此可以用一个int64类型进行表示，同时呢，其每一行又可以用1byte表示，这就给原子操作（位操作）留下了可能：


通过上图可以直观的看到算法进行一些左移以及或操作是如何运算的原理，总之就是进行逼近后，原来的8x8的某一维就变成一个int64位的整型喽~
因此最终的NG的逼近公式就是：

就是上面的这个公式卡了我半天……。。。
那么公式4就变成下面这样了：

问题3
关键的地方说完了……这部分就比较好说了，采用的训练模型为线性支持向量机： 公式1中的w，采用的ground truth以及随机的背景进行训练 公式3中的两个参数，采用NMS选取到窗口以及最后的标注进行训练；

思路梳理

如果理解没错的话，那么算法的流程是大概如下的：

1. 首先进行参数训练；得到各种参数
2. 输入某图像；
3. 产生一系列不同大小的梯度图像；
4. 采用NMS算法，检测出一系列窗口大小8*8梯度图；
5. 对每个窗口的梯度图进行二值化逼近产生出BING features;
6. 通过公式6，公式3计算出objectness值;
7. 得到结果（因为待选窗口可能来自于不同大小的梯度图，根据其resize的比例将其还原至原图像）;

参考文献：

[1] BING: Binarized Normed Gradients for Objectness Estimation at 300fps. Ming-Ming Cheng, Ziming Zhang, Wen-Yan Lin, Philip Torr, IEEE CVPR, 2014.
[2] Measuring the objectness of image windows. Alexe, B., Deselares, T. and Ferrari, V. PAMI 2012.

写在最后

终于写完了，因为还没有读下源代码，因此可能回存在一些理解错误的地方，后面会继续的关注修改，也欢迎大家指正。
非常感谢程明明老师能够把这些东西贡献出来供大家学习，非常牛叉的工作，非常赞的精神！让我觉得有的时候一个好的算法不一定需要多么的复杂与高深，应该要针对问题进行解决，也许简单的方法就会起到很好的效果。
继续努力~！！

最后呢……我也不知道写这些个人的理解会不会产生一些侵权的问题呢？要是有什么问题请及时联系我呀……