在单机上快速、精确的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距离的近似比较大,未必会有好的结果。


原文发布于微信公众号 - 计算机视觉战队(ComputerVisionGzq)

原文发表时间:2017-11-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏宏伦工作室

深度有趣 | 04 图像风格迁移

图像风格迁移是指,将一幅内容图的内容,和一幅或多幅风格图的风格融合在一起,从而生成一些有意思的图片

26160
来自专栏PaddlePaddle

【结构化语义模型】深度结构化语义模型

导语 PaddlePaddle提供了丰富的运算单元,帮助大家以模块化的方式构建起千变万化的深度学习模型来解决不同的应用问题。这里,我们针对常见的机器学习任务,提...

55780
来自专栏机器人网

图解机器学习(清晰的路线图)

每当提到机器学习,大家总是被其中的各种各样的算法和方法搞晕,觉得无从下手。确实,机器学习的各种套路确实不少,但是如果掌握了正确的路径和方法,其实还是有迹可循的,...

58390
来自专栏AI科技评论

干货 | 攻击AI模型之FGSM算法

本文将为您揭开白盒攻击中鼎鼎大名的FGSM(Fast Gradient Sign Method)算法的神秘面纱!

81320
来自专栏人工智能LeadAI

零基础入门深度学习 | 第三章:神经网络和反向传播算法

无论即将到来的是大数据时代还是人工智能时代,亦或是传统行业使用人工智能在云上处理大数据的时代,作为一个有理想有追求的程序员,不懂深度学习这个超热的技术,会不会感...

516120
来自专栏人工智能LeadAI

数据预处理 | 机器学习之特征工程

作者:苏小保(jacksu) 华为工程师 擅长分布式系统、大数据、机器学习。github地址:https://github.com/jacksu 通过特征提取,...

43790
来自专栏企鹅号快讯

常用的像素操作算法:Resize、Flip、Rotate

Resize 图像缩放是把原图像按照目标尺寸放大或者缩小,是图像处理的一种。 图像缩放有多种算法。最为简单的是最临近插值算法,它是根据原图像和目标图像的尺寸,计...

468100
来自专栏null的专栏

论文阅读——利用Binary Hash Codes的深度图像检索

这篇文章是阅读《Deep Learning of Binary Hash Codes for Fast Image Retrieval》后的总结,该文章提出了...

44740
来自专栏Ldpe2G的个人博客

Mxnet 实现图片快速风格化

论文链接:Perceptual Losses for Real-Time Style Transfer and Super-Resolution

18570
来自专栏机器学习和数学

[高大上的DL]经典网络模型总结之AlexNet篇

为了不让大家以为我这两天没学习的假象(shi shi),决定今天一定要更新一下了! 之前基本把卷积神经网络的内容过了一遍,还差一...

44180

扫码关注云+社区

领取腾讯云代金券