目标检测算法综述

概述 Overview

在深度学习正式介入之前，传统的「目标检测」方法都是 区域选择、提取特征（颜色，纹理等）、分类回归 三部曲，这样就有两个难以解决的问题；其一是区域选择的策略效果差、时间复杂度高；其二是手工提取的特征鲁棒性较差。

云计算时代来临后，「目标检测」算法大家族主要划分为两大派系，一个是 R-CNN 系两刀流，另一个则是以 YOLO 为代表的一刀流派。下面分别解释一下 两刀流 和 一刀流。

两刀流 顾名思义，两刀解决问题：

1、生成可能区域（Region Proposal） & CNN 提取特征 2、放入分类器分类并修正位置

这一流派的算法都离不开 Region Proposal ，即是优点也是缺点，主要代表人物就是 R-CNN 系。

一刀流 顾名思义，一刀解决问题，直接对预测的目标物体进行回归。回归解决问题简单快速，但是太粗暴了，主要代表人物是 YOLO 和 SSD 。

无论 两刀流 还是 一刀流，他们都是在同一个天平下选取一个平衡点、或者选取一个极端——要么准，要么快。

两刀流的天平主要倾向准，一刀流的天平主要倾向快。

但最后万剑归宗，大家也找到了自己的平衡，平衡点的有略微的不同。

接下来我们花开两朵各表一支，一朵 两刀流 的前世今生，另一朵 一刀流 的发展历史。

一、两刀流 R-CNN

R-CNN 其实是一个很大的家族，自从 rbg 大神发表那篇论文，子孙无数、桃李满天下。在此，我们只探讨 R-CNN 直系亲属，他们的发展顺序如下：

R-CNN -> SPP Net -> Fast R-CNN -> Faster R-CNN -> Mask R-CNN

其实说句良心话，最佩服的并不是 rbg 大神，而是提出了 SPP Net 的以何恺明为主的作者们。他们在整个家族进化的过程中，一致暗埋了一条主线：充分榨干 feature maps 的价值。

1.1 R-CNN / 2013

论文：Rich feature hierarchies for accurate object detection and semantic segmentation

这篇论文，这个模型，是利用卷积神经网络来做「目标检测」的开山之作，其意义深远不言而喻。

1.1.1核心贡献

一、速度 传统的区域选择使用滑窗，每滑一个窗口检测一次，相邻窗口信息重叠高，检测速度慢。R-CNN 使用一个启发式方法（Selective search），先生成候选区域（使用选择性搜索）再检测，降低信息冗余程度，从而提高检测速度。

二、特征提取 传统的手工提取特征鲁棒性差，限于如颜色、纹理等 低层次（Low level）的特征。使用 CNN （卷积神经网络）提取特征，可以提取更高层面的抽象特征，从而提高特征的鲁棒性。

选择性搜索主要思想

论文：Selective Search for Object Recognition

组成目标物体通常有四个要素：变化尺度、颜色、结构（材质）、所占面积。选择性搜索会确定物体在图片中的这些特征，然后基于这些特征突出不同区域。下面是选择搜索的一个简单案例：

首先将一张图片作为输入：

之后，它会生成最初的sub-分割，将图片分成多个区域：
查看现有小区域，按照合并规则合并可能性最高的相邻两个区域，重复这种操作：

最后，生成最终的目标物体位置（Region of Interest）。

1.1.2 基本流程

我们首先取一个预训练卷积神经网络CNN。
根据需要检测的目标类别数量，训练CNN的最后一层。
将以下图片作为输入：

之后，我们会用上文中的选择性搜索得到感兴趣区域（大约1k~2k个）：

对这些区域重新改造，以让其符合CNN的输入尺寸要求，将这些区域输入到CNN中，并经过卷积网络：

对每个类别，我们都要训练一个二元SVM（判断物体是foreground or background，我们检测的目标是foreground）。CNN为每个区域提取特征，利用SVM将这些区域分成不同类别：

最后，我们训练一个线性回归模型（bounding box regression），为每个辨识到的物体生成更精确的边界框。：

bounding box regression原理

如图9所示绿色框为飞机的Ground Truth(GT)，红色为提取的foreground anchors，即便红色的框被分类器识别为飞机，但是由于红色的框定位不准，这张图相当于没有正确的检测出飞机。所以我们希望采用一种方法对红色的框进行微调，使得foreground anchors和GT更加接近。

对于窗口一般使用四维向量 [x,y,w,h] 表示，分别表示窗口的中心点坐标和宽高。对于下图，红色的框A代表原始的Foreground Anchors，绿色的框G代表目标的GT，我们的目标是寻找一种关系，使得输入原始的anchor A经过映射得到一个跟真实窗口G更接近的回归窗口G’，即：

给定：anchor$A = (A_x,A_y,A_w,A_h)$ 和$GT = [G_x,G_y,G_w,G_h]$
寻找一种变换F，使得：$F(A_x,A_y,A_w,A_h)=(G’_x,G’_y,G’_w,G’_h)$，其中$(G’_x,G’_y,G’_w,G’_h)\approx (G_x,G_y,G_w,G_h)$

那么经过何种变换F才能从图中的anchor A变为G’呢？比较简单的思路就是:

先做平移 $G'_x = A_w*d_x(A)+A_x$
\[G'_y = A_h*d_y(A)+A_y\]
再做缩放 $G'_w = A_w*exp(d_w(A))$
\[G'_h = A_h*exp(d_h(A))\]

观察上面4个公式发现，需要学习的是 $d_{x}(A),d_{y}(A),d_{w}(A),d_{h}(A)$这四个变换。当输入的anchor A与GT相差较小时，可以认为这种变换是一种线性变换，那么就可以用线性回归来建模对窗口进行微调（注意，只有当anchors A和GT比较接近时，才能使用线性回归模型，否则就是复杂的非线性问题了）。接下来的问题就是如何通过线性回归获得 $d_{x}(A),d_{y}(A),d_{w}(A),d_{h}(A)$ 了。线性回归就是给定输入的特征向量X, 学习一组参数W, 使得经过线性回归后的值跟真实值Y非常接近，即$Y=WX$。对于该问题，输入X是cnn feature map，定义为Φ；同时还有训练传入A与GT之间的变换量，即$(t_{x}, t_{y}, t_{w}, t_{h})$。输出是$d_{x}(A),d_{y}(A),d_{w}(A),d_{h}(A)$四个变换。那么目标函数可以表示为： $d_*(A)=W_*^T\cdot \phi(A)$

其中 $\phi(A)$ 是对应anchor的feature map组成的特征向量， $W_$ 是需要学习的参数， $d_(A)$是得到的预测值（表示 x，y，w，h，也就是每一个变换对应一个上述目标函数）。为了让预测值$d_(A)$与真实值$t_*$ 差距最小，设计损失函数：

\[\text{Loss}=\sum_{i}^{N}{(t_*^i-W_*^T\cdot \phi(A^i))^2}\]

函数优化目标为：

\[\hat{W}_*=\text{argmin}_{W_*}\sum_{i}^{n}(t_*^i- W_*^T\cdot \phi(A^i))^2+\lambda||W_*||^2\\]

需要说明，只有在GT与需要回归框位置比较接近时，才可近似认为上述线性变换成立。说完原理，对应于Faster RCNN原文，foreground anchor与ground truth之间的平移量 $(t_x, t_y)$与尺度因子 $(t_w, t_h)$如下：

\[t_x=(x-x_a)/w_a\ \ \ \ t_y=(x-y_a)/h_a\] \[t_w=\log(w/w_a)\ \ \ \ t_h=\log(h/h_a)\]

对于训练bouding box regression网络回归分支，输入是cnn feature Φ，监督信号是Anchor与GT的差距 $(t_x, t_y, t_w, t_h)$，即训练目标是：输入 Φ的情况下使网络输出与监督信号尽可能接近。那么当bouding box regression工作时，再输入Φ时，回归网络分支的输出就是每个Anchor的平移量和变换尺度 $(t_x, t_y, t_w, t_h)$，显然即可用来修正Anchor位置了。

这就是RCNN检测目标物体的方法。

1.1.3局限

训练一个RCNN模型非常昂贵，并且步骤较多：

根据选择性搜索，要对每张图片提取2000个单独区域；
用CNN提取每个区域的特征。假设我们有N张图片，那么CNN特征就是N*2000；
用RCNN进行目标检测的整个过程有三个模型：
- 用于特征提取的CNN
- 用于目标物体辨别的线性SVM分类器
- 调整边界框的回归模型。

这些过程合并在一起，会让RCNN的速度变慢，通常每个新图片需要40—50秒的时间进行预测，基本上无法处理大型数据集。

从结果上说，该方法将 PASCAL VOC 上的检测率从 35.1% 提升到 53.7% ，提高了好几个量级。虽然比传统方法好很多，但是从现在的眼光看，只能是初窥门径。

1.2 SPP Net / 2014

论文：Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition

R-CNN 提出后的一年，以何恺明、任少卿为首的团队提出了 SPP Net ，这才是真正摸到了卷积神经网络的脉络。也不奇怪，毕竟这些人鼓捣出了 ResNet 残差网络，对神经网络的理解是其他人没法比的。

1.2.1 核心贡献

解决了R-CNN的两个硬伤：

算力冗余先生成候选区域，再对区域进行卷积，这里有两个问题：其一是候选区域会有一定程度的重叠，对相同区域进行重复卷积；其二是每个区域进行新的卷积需要新的存储空间。

何恺明等人意识到这个可以优化，于是把先生成候选区域再卷积，变成了先卷积后生成区域。“简单地”改变顺序，不仅减少存储量而且加快了训练速度。
图片缩放

在R-CNN基本流程步骤5中，对搜索出的感兴趣区域重新改造，以让其符合CNN的输入尺寸要求时，无论是剪裁（Crop）还是缩放（Warp），在很大程度上会丢失图片原有的信息导致训练效果不好，如上图所示。直观的理解，把车剪裁成一个门，人看到这个门也不好判断整体是一辆车；把一座高塔缩放成一个胖胖的塔，人看到也没很大把握直接下结论。人都做不到，机器的难度就可想而知了。

ROI池化层

何恺明等人发现了这个问题，于是思索有什么办法能不对图片进行变形，将图片原汁原味地输入进去学习。

最后，他们发现问题的根源是 FC Layer（全连接层）需要确定输入维度，于是他们在输入全连接层前定义一个特殊的池化层，将输入的任意尺度 feature maps 组合成特定维度的输出，这个组合可以是不同大小的拼凑，如同拼凑七巧板般。这就是ROI池化层。

具体来说，

先将对应的feature map区域水平分为$pooled_w ×pooled_h$ 的网格；
对网格的每一份都进行max pooling处理。

这样处理后，即使大小不同的proposal输出结果都是 $pooled_w ×pooled_h$ 固定大小，实现了固定长度输出。

SPP Net 的出现是如同一道惊雷，不仅减少了计算冗余，更重要的是打破了固定尺寸输入这一束缚，让后来者享受到这一缕阳光。

1.3 Fast R-CNN / 2015

论文：Fast R-CNN

此时，我们的 rbg 大哥也按耐不住了——自己家的孩子，自己养大——于是憋出了一个大招 Fast R-CNN 。取这个名字的意思就是“儿子比爸爸强”，相对于原来的 Slow R-CNN，做了速度上的优化——就是快。

在这篇论文中，引用了 SPP Net 的工作，并且致谢其第一作者何恺明的慷慨解答。

1.3.1 核心贡献

想要减少RCNN算法的计算时间，可以用什么方法？我们可不可以在每张图片上只使用一次CNN即可得到全部的重点关注区域呢，而不是运行2000次。

RCNN的作者提出了一种想法，在每张照片上只运行一次CNN，然后找到一种方法在2000个区域中进行计算。在Fast RCNN中，我们将图片输入到CNN中，会相应地生成传统特征映射。利用这些映射，就能提取出感兴趣区域。之后，我们使用一个Rol池化层将所有提出的区域重新修正到合适的尺寸，以输入到完全连接的网络中。

简单地说，这一过程含有以下步骤：

输入图片。
输入到卷积网络中，它生成感兴趣区域。
利用Rol池化层对这些区域重新调整，将其输入到完全连接网络中。
在网络的顶层用softmax层输出类别。同样使用一个线性回归层，输出相对应的边界框。

所以，和RCNN所需要的三个模型不同，Fast RCNN只用了一个模型就同时实现了区域的特征提取、分类、边界框生成。

另外，原来的 R-CNN 是先对候选框区域进行分类，判断有没有物体，如果有则对 Bounding Box 进行精修 回归 。这是一个串联式的任务，那么势必没有并联的快，所以 rbg 就将原有结构改成并行——在分类的同时，对 Bbox 进行回归。

这一改变将 Bbox 和 Clf 的 loss 结合起来变成一个 Loss 一起训练，并吸纳了 SPP Net 的优点，最终不仅加快了预测的速度，而且提高了精度。

1.3.2 基本流程

首先，输入图像：
图像被传递到卷积网络中，返回感兴趣区域：
之后，在区域上应用Rol池化层，保证每个区域的尺寸相同：

这些区域被传递到一个完全连接的网络中进行分类，并用softmax和线性回归层同时返回边界框：

1.3.3 局限

但是即使这样，Fast RCNN也有某些局限性。它同样用的是选择性搜索作为寻找感兴趣区域的，这一过程通常较慢。与RCNN不同的是，Fast RCNN处理一张图片大约需要2秒。但是在大型真实数据集上，这种速度仍然不够理想。

1.4 Faster R-CNN / 2015

论文：Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks

众人拾柴火焰高，原来 SPP Net 的人马和 rbg 一起研究憋大招，在 rbg 和 何恺明 绽放完光芒后，任少卿 老哥发出了太阳般的光芒——RPN 的概念让人不得不服。

1.4.1 核心贡献

在 Faster R-CNN 前，我们生产候选区域都是用的一系列启发式算法，基于 Low Level 特征生成区域。这样就有两个问题：

第一个问题 是生成区域的靠谱程度随缘，而 两刀流 算法正是依靠生成区域的靠谱程度——生成大量无效区域则会造成算力的浪费、少生成区域则会漏检； 第二个问题 是生成候选区域的算法是在 CPU 上运行的，而我们的训练在 GPU 上面，跨结构交互必定会有损效率。

那么怎么解决这两个问题呢？

于是乎，任少卿等人提出了一个 Region Proposal Networks 的概念，利用神经网络自己学习去生成候选区域。

这种生成方法同时解决了上述的两个问题，神经网络可以学到更加高层、语义、抽象的特征，生成的候选区域的可靠程度大大提高；可以从上图看出 RPNs 和 RoI Pooling 共用前面的卷积神经网络——将 RPNs 嵌入原有网络，原有网络和 RPNs 一起预测，大大地减少了参数量和预测时间。

在 RPNs 中引入了 anchor 的概念，feature map 中每个滑窗位置都会生成 k 个 anchors，然后判断 anchor覆盖的图像是前景还是背景，同时回归 Bbox 的精细位置，预测的 Bbox 更加精确。

将 两刀流 的两刀并入同一个网络，这一操作足够载入史册了。

1.4.2 基本流程

Faster RCNN基本结构

Faster RCNN其实可以分为4个主要内容：

Conv layers。作为一种CNN网络目标检测方法，Faster RCNN首先使用一组基础的conv+relu+pooling层提取image的feature maps。该feature maps被共享用于后续RPN层和全连接层。
Region Proposal Networks。RPN网络用于生成region proposals。该层通过softmax判断anchors属于foreground或者background，再利用bounding box regression修正anchors获得精确的proposals。
Roi Pooling。该层收集输入的feature maps和proposals，综合这些信息后提取proposal feature maps，送入后续全连接层判定目标类别。
Classification。利用proposal feature maps计算proposal的类别，同时再次bounding box regression获得检测框最终的精确位置。

具体来说可看下图：VGG16模型中的faster_rcnn_test.pt的网络结构

可以清晰的看到该网络对于一副任意大小PxQ的图像，首先缩放至固定大小MxN，然后将MxN图像送入网络；而Conv layers中包含了13个conv层+13个relu层+4个pooling层；RPN网络首先经过3x3卷积，再分别生成foreground anchors与bounding box regression偏移量，然后计算出proposals；而Roi Pooling层则利用proposals从feature maps中提取proposal feature送入后续全连接和softmax网络作classification（即分类proposal到底是什么object）。

Conv layers

Conv layers包含了conv，pooling，relu三种层。如图2，Conv layers部分共有13个conv层，13个relu层，4个pooling层。这里有一个非常容易被忽略但是又无比重要的信息，在Conv layers中：

所有的conv层都是：keneral_size = 3,pad = 1,stride = 1
所有的pooling层都是：keneral_size = 2,pad = 0 ,stride = 2

为何重要？在Faster RCNN Conv layers中对所有的卷积都做了扩边处理（ pad=1，即填充一圈0），导致原图变为 (M+2)x(N+2)大小，再做3x3卷积后输出MxN 。正是这种设置，导致Conv layers中的conv层不改变输入和输出矩阵大小。如图3：

类似的是，Conv layers中的pooling层kernel_size=2，stride=2。这样每个经过pooling层的MxN矩阵，都会变为(M/2)x(N/2)大小。综上所述，在整个Conv layers中，conv和relu层不改变输入输出大小，只有pooling层使输出长宽都变为输入的1/2。那么，一个MxN大小的矩阵经过Conv layers固定变为(M/16)x(N/16)！这样Conv layers生成的featuure map中都可以和原图对应起来。

Region Proposal Networks(RPN)

经典的检测方法生成检测框都非常耗时，如OpenCV adaboost使用滑动窗口+图像金字塔生成检测框；或如R-CNN使用SS(Selective Search)方法生成检测框。而Faster RCNN则抛弃了传统的滑动窗口和SS方法，直接使用RPN生成检测框，这也是Faster R-CNN的巨大优势，能极大提升检测框的生成速度。

上图4展示了RPN网络的具体结构。可以看到RPN网络实际分为2条线：

一路用来判断候选框是前景还是背景，它先reshape成一维向量，softmax分类anchors获得foreground和background（检测目标是foreground），然后reshape恢复为二维feature map。故经过这一步之后，我们就可以舍弃背景anchors了。大部分的anchors都是属于背景，故这一步可以筛选掉很多无用的anchor，从而减少全连接层的计算量。对于经过了3x3的卷积后得到的256个feature map，先经过1x1的卷积，变换为18个feature map。然后reshape为一维向量，经过softmax判断是前景还是背景。此处reshape的唯一作用就是让数据可以进行softmax计算。然后输出识别得到的前景anchors。

下面一路用于计算对于anchors的bounding box regression偏移量，以获得精确的proposal（也就是确定候选框的位置）。

而最后的Proposal层则负责综合foreground anchors和bounding box regression偏移量获取proposals，同时剔除太小和超出边界的proposals。其实整个网络到了Proposal Layer这里，就完成了相当于目标定位的功能。

关于1x1卷积

如上图，输入有3个通道，同时有2个卷积核。对于每个卷积核，先在输入3个通道分别作卷积，再将3个通道结果加起来得到卷积输出。所以对于某个卷积层，无论输入图像有多少个通道，输出图像通道数总是等于卷积核数量！对多通道图像做1x1卷积，其实就是将输入图像于每个通道乘以卷积系数后加在一起，即相当于把原图像中本来各个独立的通道“联通”在了一起。

候选框（anchors）：

所谓anchors，实际上就是一组由rpn/generate_anchors.py生成的矩形。直接运行作者demo中的generate_anchors.py可以得到以下输出：

[[ -84.  -40.   99.   55.]
 [-176.  -88.  191.  103.]
 [-360. -184.  375.  199.]
 [ -56.  -56.   71.   71.]
 [-120. -120.  135.  135.]
 [-248. -248.  263.  263.]
 [ -36.  -80.   51.   95.]
 [ -80. -168.   95.  183.]
 [-168. -344.  183.  359.]]

其中每行的4个值$(x_1, y_1, x_2, y_2)$代表矩形左上和右下角点坐标。9个矩形共有3种形状，长宽比为大约为$width:height \in { 1:1,1:2,2:1 }$ 三种，如下图。实际上通过anchors就引入了检测中常用到的多尺度方法。

那么这9个anchors是做什么的呢？借用Faster RCNN论文中的原图，如图7，遍历Conv layers计算获得的feature maps，为每一个点都配备这9种anchors作为初始的检测框。这样做获得检测框很不准确，不用担心，后面还有2次bounding box regression可以修正检测框位置。

假设在conv5 feature map中每个点上有k个anchor（默认k=9），而每个anhcor要分foreground和background，所以每个点由256d feature转化为cls=2k scores；而每个anchor都有(x, y, w, h)对应4个偏移量，所以reg=4k coordinates。

补充一点，全部anchors拿去训练太多了，训练程序会在合适的anchors中随机选取128个postive anchors+128个negative anchors进行训练。

softmax判定foreground与background

一副MxN大小的矩阵送入Faster RCNN网络后，到RPN网络变为(M/16)x(N/16)，不妨设 W=M/16，H=N/16。在进入reshape与softmax之前，先做了1x1卷积，如图9：

图9 RPN中判定fg/bg网络结构

该1x1卷积的caffe prototxt定义如下：

layer {
  name: "rpn_cls_score"
  type: "Convolution"
  bottom: "rpn/output"
  top: "rpn_cls_score"
  convolution_param {
    num_output: 18   # 2(bg/fg) * 9(anchors)
    kernel_size: 1 pad: 0 stride: 1
  }
}

可以看到其num_output=18，也就是经过该卷积的输出图像为WxHx18大小。这也就刚好对应了feature maps每一个点都有9个anchors，同时每个anchors又有可能是foreground和background，所有这些信息都保存WxHx(9*2)大小的矩阵。为何这样做？后面接softmax分类获得foreground anchors，也就相当于初步提取了检测目标候选区域box（一般认为目标在foreground anchors中）。那么为何要在softmax前后都接一个reshape layer？其实只是为了便于softmax分类，至于具体原因这就要从caffe的实现形式说起了。在caffe基本数据结构blob中以如下形式保存数据：

blob=[batch_size, channel，height，width]

对应至上面的保存bg/fg anchors的矩阵，其在caffe blob中的存储形式为[1, 2x9, H, W]。而在softmax分类时需要进行fg/bg二分类，所以reshape layer会将其变为[1, 2, 9xH, W]大小，即单独“腾空”出来一个维度以便softmax分类，之后再reshape回复原状。贴一段caffe softmax_loss_layer.cpp的reshape函数的解释，非常精辟：

"Number of labels must match number of predictions; "
"e.g., if softmax axis == 1 and prediction shape is (N, C, H, W), "
"label count (number of labels) must be N*H*W, "
"with integer values in {0, 1, ..., C-1}.";

综上所述，RPN网络中利用anchors和softmax初步提取出foreground anchors作为候选区域。

对proposals进行bounding box regression

在了解bounding box regression后，再回头来看RPN网络第二条线路，如图。

先来看一看上图11中1x1卷积的caffe prototxt定义：

layer {
  name: "rpn_bbox_pred"
  type: "Convolution"
  bottom: "rpn/output"
  top: "rpn_bbox_pred"
  convolution_param {
    num_output: 36   # 4 * 9(anchors)
    kernel_size: 1 pad: 0 stride: 1
  }
}

可以看到其 num_output=36，即经过该卷积输出图像为WxHx36，在caffe blob存储为[1, 4x9, H, W]，这里相当于feature maps每个点都有9个anchors，每个anchors又都有4个用于回归的$[d_x(A),d_y(A).d_w(A),d_h(A)]$变换量。

Proposal Layer

Proposal Layer负责综合所有$[d_x(A),d_y(A).d_w(A),d_h(A)]$变换量和foreground anchors，计算出精准的proposal，送入后续RoI Pooling Layer。还是先来看看Proposal Layer的caffe prototxt定义：

layer {
  name: 'proposal'
  type: 'Python'
  bottom: 'rpn_cls_prob_reshape'
  bottom: 'rpn_bbox_pred'
  bottom: 'im_info'
  top: 'rois'
  python_param {
    module: 'rpn.proposal_layer'
    layer: 'ProposalLayer'
    param_str: "'feat_stride': 16"
  }
}

Proposal Layer有3个输入：fg/bg anchors分类器结果rpn_cls_prob_reshape，对应的bbox reg的$[d_x(A),d_y(A).d_w(A),d_h(A)]$变换量rpn_bbox_pred，以及im_info；另外还有参数feat_stride=16，这和图4是对应的。首先解释im_info。对于一副任意大小PxQ图像，传入Faster RCNN前首先reshape到固定MxN，im_info=[M, N, scale_factor]则保存了此次缩放的所有信息。然后经过Conv Layers，经过4次pooling变为WxH=(M/16)x(N/16)大小，其中feature_stride=16则保存了该信息，用于计算anchor偏移量。

图13

Proposal Layer forward（caffe layer的前传函数）按照以下顺序依次处理：

生成anchors，利用$[d_x(A),d_y(A).d_w(A),d_h(A)]$对所有的anchors做bbox regression回归（这里的anchors生成和训练时完全一致）
按照输入的foreground softmax scores由大到小排序anchors，提取前pre_nms_topN(e.g. 6000)个anchors，即提取修正位置后的foreground anchors。
限定超出图像边界的foreground anchors为图像边界（防止后续roi pooling时proposal超出图像边界）
剔除非常小（width<threshold or height<threshold）的foreground anchors
进行非极大值抑制 non maximum suppression
再次按照nms后的foreground softmax scores由大到小排序fg anchors，提取前post_nms_topN(e.g. 300)结果作为proposal输出。

之后输出$proposal=[x_1, y_1, x_2, y_2]$，注意，由于在第三步中将anchors映射回原图判断是否超出边界，所以这里输出的proposal是对应MxN输入图像尺度的，这点在后续网络中有用。另外我认为，严格意义上的检测应该到此就结束了，后续部分应该属于识别了~ RPN网络结构就介绍到这里，总结起来就是： 生成anchors -> softmax分类器提取foreground anchors -> bbox reg回归foreground anchors -> Proposal Layer生成proposals

Classification

Classification部分利用已经获得的proposal feature maps，通过full connect层与softmax计算每个proposal具体属于那个类别（如人，车，电视等），输出cls_prob概率向量；同时再次利用bounding box regression获得每个proposal的位置偏移量bbox_pred，用于回归更加精确的目标检测框。Classification部分网络结构如图16。

图16 Classification部分网络结构图

从PoI Pooling获取到7x7=49大小的proposal feature maps后，送入后续网络，可以看到做了如下2件事：

通过全连接和softmax对proposals进行分类，这实际上已经是识别的范畴了
再次对proposals进行bounding box regression，获取更高精度的rect box

二、一刀流 YOLO & SSD

一刀流的想法就比较暴力，给定一张图像，使用回归的方式输出这个目标的边框和类别。一刀流最核心的还是利用了分类器优秀的分类效果，首先给出一个大致的范围（最开始就是全图）进行分类，然后不断迭代这个范围直到一个精细的位置，如上图从蓝色的框框到红色的框框。

这就是一刀流回归的思想，这样做的优点就是快，但是会有许多漏检。

2.1 YOLO / 2015

论文：YOLO

2.1.1 核心贡献

YOLO将物体检测作为回归问题求解。基于一个单独的end-to-end网络，完成从原始图像的输入到物体位置和类别的输出。从网络设计上，YOLO与rcnn、fast rcnn及faster rcnn的区别如下：

YOLO训练和检测均是在一个单独网络中进行。YOLO没有显示地求取region proposal的过程。而rcnn/fast rcnn 采用分离的模块（独立于网络之外的selective search方法）求取候选框（可能会包含物体的矩形区域），训练过程因此也是分成多个模块进行。Faster rcnn使用RPN（region proposal network）卷积网络替代rcnn/fast rcnn的selective search模块，将RPN集成到fast rcnn检测网络中，得到一个统一的检测网络。尽管RPN与fast rcnn共享卷积层，但是在模型训练过程中，需要反复训练RPN网络和fast rcnn网络（注意这两个网络核心卷积层是参数共享的）。
YOLO将物体检测作为一个回归问题进行求解，输入图像经过一次inference，便能得到图像中所有物体的位置和其所属类别及相应的置信概率。而rcnn/fast rcnn/faster rcnn将检测结果分为两部分求解：物体类别（分类问题），物体位置即bounding box（回归问题）。

2.1.2基本流程

YOLO检测网络包括24个卷积层和2个全连接层，如下图所示。

preview

其中，卷积层用来提取图像特征，全连接层用来预测图像位置和类别概率值。

整体来看，Yolo算法采用一个单独的CNN模型实现end-to-end的目标检测，整个系统如下图所示：首先将输入图片resize到448x448，然后送入CNN网络，最后处理网络预测结果得到检测的目标。相比R-CNN算法，其是一个统一的框架，其速度更快，而且Yolo的训练过程也是end-to-end的。

具体来说，Yolo的CNN网络将输入的图片分割成 S×S 网格，然后每个单元格负责去检测那些中心点落在该格子内的目标，如图所示：

边界框置信度

可以看到狗这个目标的中心落在左下角一个单元格内，那么该单元格负责预测这个狗。每个单元格会预测 $B$个边界框（bounding box）以及边界框的置信度（confidence score）。所谓置信度其实包含两个方面，一是这个边界框含有目标的可能性大小，二是这个边界框的准确度。前者记为 $Pr(object)$ ，当该边界框是背景时（即不包含目标），此时 $Pr(object)=0$ 。而当该边界框包含目标时， $Pr(object)=1$。边界框的准确度可以用预测框与实际框（ground truth）的IOU（intersection over union，交并比）来表征，记为 $\text{IOU}^{truth}_{pred}$。因此置信度可以定义为： $Pr(object)*\text{IOU}^{truth}_{pred}$

边界框的大小与位置可以用4个值来表征：$ (x, y,w,h)$，其中 $(x,y)$ 是边界框的中心坐标，而 $w$和 $h$是边界框的宽与高。还有一点要注意，中心坐标的预测值 $(x,y)$ 是相对于每个单元格左上角坐标点的偏移值，并且单位是相对于单元格大小的，单元格的坐标定义如图6所示。而边界框的 $w$ 和 $h$ 预测值是相对于整个图片的宽与高的比例，这样就保证了边界框中心点不会超过单元格，但是框的边界可以超过单元格。4个元素的大小应该在 $[0,1]$ 范围。这样，每个边界框的预测值实际上包含5个元素： $(x,y,w,h,c)$，其中前4个表征边界框的大小与位置，而最后一个值是置信度。

类别置信度

还有分类问题，对于每一个单元格其还要给出预测出$N$个类别概率值，其表征的是由该单元格负责预测的边界框其目标属于各个类别的概率。但是这些概率值其实是在各个边界框置信度下的条件概率，即 $Pr(class_{i}|object)$ 。以此计算出各个边界框类别置信度（class-specific confidence scores）: $Pr(class_{i}|object)*Pr(object)*\text{IOU}^{truth}_{pred}=Pr(class_{i})*\text{IOU}^{truth}_{pred}$

边界框类别置信度表征的是该边界框中目标属于各个类别的可能性大小以及边界框匹配目标的好坏。一般会根据类别置信度来过滤网络的预测框。

总结一下，每个单元格需要预测 $B5+N$个值。如果将输入图片划分为 $S\times S$ 网格，那么最终预测值为 $SS(B5+N)$ 大小的张量。整个模型的预测值结构如下图所示。对于PASCAL VOC数据，其共有20个类别，如果使用 $S=7,B=2$ ，那么最终的预测结果就是 $7\times 7\times 30$大小的张量。

2.1.3网络训练

在训练之前，先在ImageNet上进行了预训练，其预训练的分类模型采用图8中前20个卷积层，然后添加一个average-pool层和全连接层。预训练之后，在预训练得到的20层卷积层之上加上随机初始化的4个卷积层和2个全连接层。整个网络的流程如下图所示：

损失函数：

其中，coordError、iouError和classError分别代表预测数据与标定数据之间的坐标误差、IOU误差和分类误差。

\[loss=\sum_{i=0}^{S^{2} }{coordError + iouError + classError}\]

YOLO对上式loss的计算进行了如下修正。

位置相关误差（坐标、IOU）与分类误差对网络loss的贡献值是不同的，因此YOLO在计算loss时，使用!$\lambda _{coord} =5$修正coordError
在计算IOU误差时，包含物体的格子与不包含物体的格子，二者的IOU误差对网络loss的贡献值是不同的。若采用相同的权值，那么不包含物体的格子的confidence值近似为0，变相放大了包含物体的格子的confidence误差在计算网络参数梯度时的影响。

可以这样理解，整个 YOLO 系统其实最有效的地方就是那些包含了目标中心点的网格它们所预测的 2 个 bbox，所以它们这 2 个 bbox 的位置信息就至关重要，所以它们的坐标就不允许它们变化剧烈，所以就需要添加一个系数放大它们的误差，进而达到惩罚的目的。而没有包含目标的网格，虽然它们也会预测 bbox，也会有 confidence 的预测，但基本等同于无效，所以可以看做它们对于整体的 Loss 而言，没有那么重要，因此要减弱它们对于 Loss 的影响，以防止它去干扰正常的包含了目标的那些 bbox 的 confidence 表现。

为解决这个问题，YOLO 使用$\lambda _{noobj} =0.5$修正iouError。（注：此处的包含是指存在一个物体，它的中心坐标落入到格子内）。
对于相等的误差值，大物体误差对检测的影响应小于小物体误差对检测的影响。这是因为，相同的位置偏差占大物体的比例远小于同等偏差占小物体的比例。比如预测一个小的 bbox，groundtruth 的 width 是 4，它预测是 3，那么它的误差是 1，再预测一个大的 bbox，groundtruth 的 width 是 100，预测值是 99，那么误差也是 1。很容易发现，进行小尺寸的 bbox 预测时，误差更敏感，所以 sum-sqaured error 手段需要改良。

YOLO将物体大小的信息项（w和h）进行求平方根来改进这个问题。还是用刚才的例子，小的 bbox width prediction = 3,groundtruth = 4，误差为 0.067。大的 bbox width prediction = 99,groundtruth = 100，误差为 0.0025。

综上，YOLO在训练过程中Loss计算如下式所示：

其中，$x,y,w,C,p$为网络预测值，$x,y,w,C,\widehat{p}$帽为标注值。$\Pi _{i}^{obj} $表示物体落入格子i中，$\Pi _{ij}^{obj} $和$\Pi _{ij}^{noobj}$ 分别表示物体落入与未落入格子i的第j个bounding box内。

注： YOLO方法模型训练依赖于物体识别标注数据，因此，对于非常规的物体形状或比例，YOLO的检测效果并不理想。 YOLO采用了多个下采样层，网络学到的物体特征并不精细，因此也会影响检测效果。 YOLO loss函数中，大物体IOU误差和小物体IOU误差对网络训练中loss贡献值接近（虽然采用求平方根方式，但没有根本解决问题）。因此，对于小物体，小的IOU误差也会对网络优化过程造成很大的影响，从而降低了物体检测的定位准确性。

2.1.4局限

虽然每个格子可以预测B个bounding box，但是最终只选择只选择IOU最高的bounding box作为物体检测输出，即每个格子最多只预测出一个物体。当物体占画面比例较小，如图像中包含畜群或鸟群时，每个格子包含多个物体，但却只能检测出其中一个。这是Yolo算法的一个缺点，在后来的改进版本中，Yolo9000是把类别概率预测值与边界框是绑定在一起的。

2.2 SSD / 2015

论文：SSD

SSD 就在 YOLO 的主意上添加了 Faster R-CNN 的 Anchor 概念，并融合不同卷积层的特征做出预测。

我们从上图就可以很明显的看出这是 YOLO 分治网络 和 Faster R-CNN Anchor 的融合，这就大大提高了对小物体的检测。这里作者做实验也提到和 Faster R-CNN 一样的结果，这个 Anchor 的数量和形状会对性能造成较大的影响。

除此之外，由于这个 Anchor 是规整形状的，但是有些物体的摆放位置是千奇百怪的，所以没有 数据增强 前的效果比增强后的效果差 7 个百分点。直观点理解，做轻微地角度扭曲让 Anchor 背后的神经元“看到”更多的信息。

还有一个重大的进步是结合了不同尺寸大小 Feature Maps 所提取的特征，然后进行预测。这是 FPN 网络提出前的第一次做 Feature Pyramid 的尝试，这个特征图金字塔结合了不同层的信息，从而结合了不同 尺寸 和 大小 的特征信息。

这个尝试就大大地提高了识别的精度，且高分辨率（尺寸大）的 Feature Map 中含有更多小物体的信息，也是因为这个原因 SSD 能够较好的识别小物体。

除此之外，和 YOLO 最大的区别是，SSD 没有接 FC 减少了大量的参数量、提高了速度。

小结 / 2018

回顾过去，从 YOLO 到 SSD ，人们兼收并蓄把不同思想融合起来。

YOLO 使用了分治思想，将输入图片分为 SxS 的网格，不同网格用性能优良的分类器去分类。 YOLO v1 也有和当年其它杰出的目标检测系统做对比，但在今天来看，这个并不十分重要，重要的是我们需要理解 YOLO 快的原因。

YOLO 就是一个撒渔网的捕鱼过程，一次性搞定所有的目标定位。
YOLO 快的原因在于比较粗的粒度将输入图片划分网格，然后做预测。

YOLO 的算法精髓都体现在它的 Loss 设计上及作者如何针对问题改进 Loss，这种思考问题的方式才是最值得我们学习的。

SSD 将 YOLO 和 Anchor 思想融合起来，并创新使用 Feature Pyramid 结构。

但是 Resize 输入，必定会损失许多的信息和一定的精度，这也许是一刀流快的原因。

无论如何，YOLO 和 SSD 这两篇论文都是让人不得不赞叹他们想法的精巧，让人受益良多。

三、总结 Summary

在「目标检测」中有两个指标：快（Fast） 和 准（Accurate）。

一刀流代表的是快，但是最后在快和准中找到了平衡，第一是快，第二是准。两刀流代表的是准，虽然没有那么快但是也有 6 FPS 可接受的程度，第一是准，第二是快。

两类算法都有其适用的范围，比如说实时快速动作捕捉，一刀流更胜一筹；复杂、多物体重叠，两刀流当仁不让。没有不好的算法，只有不合适的使用场景。

四、一些概念

1. IOU

IoU度量两个框之间的重叠。我们用它来测量我们预测的框与ground truth(真实物体边界)的重叠程度。在一些数据集中，我们预先定义了一个IoU阈值(比如0.5)来分类预测是真阳性还是假阳性。

2. mAP

相关概念

mAP: mean Average Precision, 即各类别AP的平均值

AP: PR曲线下面积，后文会详细讲解

PR曲线: Precision-Recall曲线

Precision: TP / (TP + FP) 在你认为的正样本中，有多大比例真的是正样本

Recall: TP / (TP + FN) 在真正的正样本中，有多少被你找到了

TP: IoU>0.5的检测框数量（同一Ground Truth只计算一次）

FP: IoU<=0.5的检测框，或者是检测到同一个GT的多余检测框的数量

FN: 没有检测到的GT的数量

明确问题: 大背景是object detection，我就以正在学的RetinaNet应用背景为例，识别出来的每一个框都有N+1个score，对应着N个class和1个background，我们会选score最高的那个作为最终的判断。

问题核心: 我们需要一个对于score的threshold, 为什么呢? 比如在一个bounding box里，我识别出来鸭子的score最高，可是他也只有0.1，那么他真的是鸭子吗？很可能他还是负样本。所以我们需要一个阈值，如果识别出了鸭子而且分数大于这个阈值才真的说他是正样本，否则他是负样本

那么threshold到底是怎么影响precision和recall的呢？我们还是用鸭子的例子

如果threshold太高， prediction非常严格，所以我们认为是鸭子的基本都是鸭子，precision就高了；但也因为筛选太严格，我们也放过了一些score比较低的鸭子，所以recall就低了
如果threshold太低，什么都会被当成鸭子， precision就会很低， recall就会很高

这样我们就明确了threshold确实对鸭子的precision和recall产生影响和变化的趋势，也就带来了思考， precision不是一个绝对的东西，而是相对threshold而改变的东西， recall同理，那么单个用precision来作为标准判断，就不合适。这是一场precision与recall之间的trade off，用一组固定值表述不够全面，因为我们根据不同的threshold，可以取到不同（也可能相同）的precision recall值。这样想的话对于每个threshold，我们都有（precision， recall）的pair，也就有了precision和recall之间的curve关系

有了这么一条precision-recall curve，他衡量着两个有价值的判断标准， precision和recall的关系，那么不如两个一起动态考虑，就有了鸭子这个class的Average Precision，即curve下的面积，他可以充分的表示在这个model中， precision和recall的总体优劣。

最后，我们计算每个class的Average Precision，就得到了mean Average Precision

非极大值抑制（NMS）：

RCNN会从一张图片中找出n个可能是物体的矩形框，然后为每个矩形框为做类别分类概率：

就像上面的图片一样，定位一个车辆，最后算法就找出了一堆的方框，我们需要判别哪些矩形框是没用的。非极大值抑制的方法是：先假设有6个矩形框，根据分类器的类别分类概率做排序，假设从小到大属于车辆的概率分别为A、B、C、D、E、F。

(1)从最大概率矩形框F开始，分别判断A~E与F的重叠度IOU是否大于某个设定的阈值;

(2)假设B、D与F的重叠度超过阈值，那么就扔掉B、D；并标记第一个矩形框F，是我们保留下来的。

(3)从剩下的矩形框A、C、E中，选择概率最大的E，然后判断E与A、C的重叠度，重叠度大于一定的阈值，那么就扔掉；并标记E是我们保留下来的第二个矩形框。

就这样一直重复，找到所有被保留下来的矩形框。

非极大值抑制（NMS）顾名思义就是抑制不是极大值的元素，搜索局部的极大值。这个局部代表的是一个邻域，邻域有两个参数可变，一是邻域的维数，二是邻域的大小。这里不讨论通用的NMS算法，而是用于在目标检测中用于提取分数最高的窗口的。例如在行人检测中，滑动窗口经提取特征，经分类器分类识别后，每个窗口都会得到一个分数。但是滑动窗口会导致很多窗口与其他窗口存在包含或者大部分交叉的情况。这时就需要用到NMS来选取那些邻域里分数最高（是行人的概率最大），并且抑制那些分数低的窗口。