计算机视觉研究院专栏
作者:Edison_G
今天带来的这篇推送,估计您有读过或试验过,但是为了让更多的科研学者知道这么“牛”的内容知识,接下来就开始说说今天的主题——1000000类的快速精确检测。
1
前景概要
今天带来的这篇推送,估计您有读过或试验过,但是为了让更多的科研学者知道这么“牛”的内容知识,接下来就开始说说今天的主题——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算法的计算过程如下:
改进算法计算过程如下:
事先计算得到C*P个filter对应的hash值
计算多尺度的边缘强度和边缘方向图像;
对所有窗口进行遍历,对于每个窗口,计算其高斯加权HOG直方图特征,计算特征对应的hash值,分别计算HOG特征hash值和C类P个filter的hash值的hamming距离;
将具有局部最大响应的窗口作为候选,得到可能的物体中心的分布累积,综合得到最终的物体检测结果。
对比可以看到,由于改进算法中,计算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内存,推测主要应该是查找表对应的内存。
2
新框架
3
实验
从表中可以看出,只有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,从数据上看是很理想,但是距离实用性还有很长的距离。
4
启发
这个思路,对于基本操作为点积(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距离的近似比较大,未必会有好的结果。
联系客服