在单机上快速、精确的100000类别的检测

今天带来的这篇推送，估计您有读过或试验过，但是为了让更多的科研学者知道这么“牛”的内容知识，接下来就开始说说今天的主题——1000000类的快速精确检测。

注：内容选于dengyafeng的博客

今天的主题最引起关注的是“1000000类”，比Base Line快了将近2000倍。但是任何一个好的东西都会有美中不足之处，之后我们在讨论其缺陷。

今天说的这个模型主要优势在于速度快，具体就是对于多类检测问题，检测速度可以做到和类别数目无关。

对于包含C类的物体检测而言，一个基本的框架是，训练C个分类器，对于每个候选位置，用每个分类器都判定一遍，然后做后处理融合。这样的坏处就是速度太慢，处理速度和物体类别成反比。

今天说讲的内容参考的Base Line算法是DPM模型，就是每个物体的模型由多个part（假定P个）的模型组成，每个part的模型可以看作是一个filter和该位置特征的点积（整体上可以看作是一个convolution过程），然后根据可能的part候选的位置约束确定物体的位置。在实际中，最耗时的是convolution过程，每个物体分类器的filter（对应weight）都需要和候选位置的特征进行一次点积处理，假定候选窗口数目为W个，候选窗口的feature dimension是M维，则运算复杂度为W*C*P*M。

今天讲的内容工作者利用了之前的一个工作结果，可以将两个向量的点积（其实点积和cos距离有非常强的关联，如果预先对参与cos距离运算的两个向量进行模的归一化处理，则归一化后两向量的cos距离和点积是相同的）相似度转化为两个hash值的hamming距离。

距离将feature转换为lsh hash的过程如下（得到的hash是LSH hash，也是WTA hash）：假定共M维feature，设K为保留的中间元素数目设定一个重排数组（随机得到，个数为M，元素为0-M-1，每个元素的序号表示临时feature对应原始feature中的序号），从而将原始feature转变为一个临时feature，取临时featue的前K维，组成最终的新feature，则新feature中最大元素序号（新feature中）为k，将k表示为一个log(K)位的二进制数字串继续设定共N个重排数组（随机得到），则得到共N*log(K)位的二进制串，按照最前面的重排数组对应的串放在最低位的原则，得到一个hash值（N*log(K)位整数）。

对应的，两个feature之间的点积转化为两个对应hash之间的hamming距离。

直观上看，由于如此得到的数字只和数字之间的相互大小有关，且每次保留最大的序号的信息，因此，对于数字的扰动非常鲁棒。因此，得到的两个hash值之间的hamming距离所对应的相似度对于特征值的变化更加鲁棒，是更有效的表示。

（到底是否是这样，无从得知，其他信息请参考J. Yagnik, D. Strelow, D. A. Ross, and R.-s. Lin. The powe of comparative reasoning. In IEEE International Conference on Computer Vision, 2011.）

由于计算两个hash之间的hamming距离非常快速（还可以查表），因此最耗时的部分在计算每个窗口的feature以及计算hash值上，这个运算和类别数目无关。

上述可以用于点积衡量相似度的特征，可以是各种各样的特征，在物体检测里面最常用的要数HOG特征了。

下面以HOG特征为例，说明Base Line 算法和本文提出的改进之间计算时间的对比：

Base Line算法的计算过程如下：

1. 计算多尺度的边缘强度和边缘方向图像；
2. 对所有窗口进行遍历，对于每个窗口，计算其高斯加权HOG直方图特征，分别计算HOG特征和C类P个filter的点积；
3. 将具有局部最大响应的窗口作为候选，得到可能的物体中心的分布累积，综合得到最终的物体检测结果。

改进算法计算过程如下：

事先计算得到C*P个filter对应的hash值

1. 计算多尺度的边缘强度和边缘方向图像；
2. 对所有窗口进行遍历，对于每个窗口，计算其高斯加权HOG直方图特征，计算特征对应的hash值，分别计算HOG特征hash值和C类P个filter的hash值的hamming距离；
3. 将具有局部最大响应的窗口作为候选，得到可能的物体中心的分布累积，综合得到最终的物体检测结果。

对比可以看到，由于改进算法中，计算hamming距离的部分非常快，可以忽略，因此，最终得到的多类检测器的运算量和类别数目无关。

进一步，为了快速运算，可以将上述的hamming距离计算转换为查表运算，为了当累积相似度高于阈值时无需继续计算，将hash值划分为多个不同部分（这样每个表也比较小）。

将N*log(K) bit的hash分为N/M组(band)，每组是一个M*log(K) bit的整数，对于每个类别每个part的filter（训练模型），对应N/M组查找表（查找表的序号为当前窗口feature在该band上的hash值，查找表记录的值为该featurehash值和模型hash值的相似度），从而避免了hamming距离计算过程。每个filter取到的N/M组查找表的值的累积和为对应的点积值（相似度）。对N/M组累积和计算，当计算发现相似度大于阈值时，则放弃后面的运算，直接对预估物体位置分布进行累积。

则最终得到物体位置分布累积最大的位置为检测得到的物体位置。

提出的框架中还有一点值得讨论的地方在于，100000类数据都是搜索引擎爬取的，没有经过人工标定，所以结果存在一定不准确的地方。但是定性上看，这样做确实快了很多。

当然，相对Base Line算法，提出的算法在精度上还是降低一些的（见论文voc 2007的对比结果,mAP由0.26->0.24）。而耗费的20G内存，推测主要应该是查找表对应的内存。

文章的基本框架：

实验：

表1 hash-based算法与Base Line算法准确率比较

从表中可以看出，只有3个表现的比较好，其余的都表现一般甚至比Base Line更差。

mAP随hash数量变化的情况

可以看出：

• 随着hash数量增加，mAP随之提高，但是到某一数量的时候趋于饱和，该实验证明了达到了16的时候，效果最好；
• 当K=16时，在5KB/filter，mAP到达饱和，所有当有1000000类时，每类10个filters，则需要5G内存；
• 在5秒每张图像的条件下，与Base Linr相比，加速将近增加了20倍。

表2 相同内存情况下，执行速度与准确率的关系

三种不同执行时间下，检测目标数量和mAP的关系

从图中可以看出：

• 关系曲线呈指数变化趋势；
• 大概三分之一的样本集的准确率为0.20;
• 大概五分之一的样本集的准确率为0.30。

t=8时，检测准确率最高的6中物体

在PASCAL VOC2007数据集中，内存给定，不同执行时间下，增加目标类，准确率的变化情况。

从上图可以看出：执行速度越快，准确率越低。随着类数增加，准确率迅速下降，这是由于哈希冲突或者哈希表的信息量达到饱和，值得注意的是红色曲线，mAP下降最少，说明当增加计算时间后，hashing-base检测器检测大数据量级的目标类是可行的。

之前有提及框架的缺点，现在说说其缺点所在：

因为是在单机上进行类别检测，所以速度不是很理想，单机处理一张图像的速度需要20s，而且1000000类的mAP是0.16，从数据上看是很理想，但是距离实用性还有很长的距离。

启发：

• 这个思路，对于基本操作为点积（x*y）运算的，都可以加速，这个操作非常常见，比如线性SVM，COS距离，以及神经网络和LR里面的WX等等，都可以使用。一个比较容易想到的是可以应用于multi-model检测框架中（比如多类别物体检测，多姿态人脸/汽车检测等等）；
• 对于多模型检测，速度是一个非常重要的方面，一般的思路就是在提高单个模型速度（feature和分类器计算速度）的情况下，增加特征共用（LAB feature image, vector boosting），其实，最理想的特征共用是deep learning模型（只在最后一层不同，其它层都是共用的，每个隐节点可以看作是feature，所有类别共用feature，只在输出层时，计算一个wh+b项，是非常理想的特征共用），只可惜单个deep learning模型太慢，当遍历多个检测候选窗口时，最终的速度现在看太慢了。

补充：其实这个方法可能用于加速神经网络模型（当然包括deep learning），难点在于点积变为hash距离的近似比较大，未必会有好的结果。