写在前面
在深度学习出现之前，传统的目标检测方法大概分为区域选择（滑窗）、特征提取（SIFT、HOG等）、分类器（SVM、Adaboost等）三个部分，其主要问题有两方面：一方面滑窗选择策略没有针对性、时间复杂度高，窗口冗余；另一方面手工设计的特征鲁棒性较差。自深度学习出现之后，目标检测取得了巨大的突破，最瞩目的两个方向有：1 以RCNN为代表的基于Region Proposal的深度学习目标检测算法（RCNN，SPP-NET，Fast-RCNN，Faster-RCNN等）；2 以YOLO为代表的基于回归方法的深度学习目标检测算法（YOLO，SSD等）。本篇对基于Region Proposal的深度学习目标检测算法进行介绍，后续再对基于回归方法的深度学习目标检测方法进行介绍。
RCNN
流程框图
算法特点
1 使用Selective Search提取Proposes，然后利用CNN等识别技术进行分类。
2 使用识别库进行预训练，而后用检测库调优参数。
3 使用SVM代替了CNN网络中最后的Softmax，同时用CNN输出的4096维向量进行Bounding Box回归。
4 流程前两个步骤（候选区域提取+特征提取）与待检测类别无关，可以在不同类之间共用；同时检测多类时，需要倍增的只有后两步骤（判别+精修），都是简单的线性运算，速度很快。
存在问题
1 训练分为多个阶段，步骤繁琐: 微调网络+训练SVM+训练边框回归器。
2 训练耗时，占用磁盘空间大：5000张图像产生几百G的特征文件。
3 速度慢: 使用GPU, VGG16模型处理一张图像需要47s。
SPP-NET
流程框图
算法特点
1 通过Spatial Pyramid Pooling解决了深度网络固定输入层尺寸的这个限制，使得网络可以享受不限制输入尺寸带来的好处。
2 解决了RCNN速度慢的问题，不需要对每个Proposal（2000个左右）进行Wrap或Crop输入CNN提取Feature Map，只需要对整图提一次Feature Map，然后将Proposal区域映射到卷积特征层得到全链接层的输入特征。
几个要点
一、ROI的在特征图上的对应的特征区域的维度不满足全连接层的输入要求怎么办?
作者使用Spatial Pyramid Pooling解决了该问题。如下图所示，假设原图输入是224x224，对于conv5出来后的输出是13x13x256的，可以理解成有256个这样的Filter，每个Filter对应一张13x13的Reponse Map。如果像上图那样将Reponse Map分成1x1（金字塔底座），2x2（金字塔中间），4x4（金字塔顶座）三张子图，分别做Max Pooling后，出来的特征就是（16+4+1）x256 维度。如果原图的输入不是224x224，出来的特征依然是（16+4+1）x256维度。这样就实现了不管图像尺寸如何池化n的输出永远是 （16+4+1）x256 维度。
二、原始图像的ROI如何映射到特征图（一系列卷积层的最后输出）
要搞定这个问题，需要首先清楚感受野等概念和计算方法。下面从感受野、感受野上面的坐标映射及原始图像的ROI如何映射三方面阐述。
1 感受野
① 概念
在卷积神经网络中，感受野的定义是卷积神经网络每一层输出的特征图（Feature Map）上的像素点在原始图像上映射的区域大小。
② 如何计算
output field size = ( input field size - kernel size + 2*padding ) / stride + 1
其中output field size 是卷积层的输出，input field size 是卷积层的输入，反过来卷积层的输入（也即前一层的感受野） = ？答案必然是：
input field size = （output field size - 1）* stride - 2*padding + kernel size
#Python
#卷积层输出大小和感受野大小的计算
net_struct = {'alexnet': {'net':[[11,4,0],[3,2,0],[5,1,2],[3,2,0],[3,1,1],[3,1,1],[3,1,1],[3,2,0]],
'name':['conv1','pool1','conv2','pool2','conv3','conv4','conv5','pool5']},
'vgg16': {'net':[[3,1,1],[3,1,1],[2,2,0],[3,1,1],[3,1,1],[2,2,0],[3,1,1],[3,1,1],[3,1,1],
[2,2,0],[3,1,1],[3,1,1],[3,1,1],[2,2,0],[3,1,1],[3,1,1],[3,1,1],[2,2,0]],
'name':['conv1_1','conv1_2','pool1','conv2_1','conv2_2','pool2','conv3_1','conv3_2',
'conv3_3', 'pool3','conv4_1','conv4_2','conv4_3','pool4','conv5_1','conv5_2','conv5_3','pool5']},
'zf-5':{'net': [[7,2,3],[3,2,1],[5,2,2],[3,2,1],[3,1,1],[3,1,1],[3,1,1]],
'name': ['conv1','pool1','conv2','pool2','conv3','conv4','conv5']}}
imsize = 224
def outFromIn(isz, net, layernum):#从前向后算输出维度
totstride = 1
insize = isz
for layer in range(layernum):
fsize, stride, pad = net[layer]
outsize = (insize - fsize + 2*pad) / stride + 1
insize = outsize
totstride = totstride * stride
return outsize, totstride
def inFromOut(net, layernum):#从后向前算感受野 返回该层元素在原始图片中的感受野
RF = 1
for layer in reversed(range(layernum)):
fsize, stride, pad = net[layer]
RF = ((RF -1)* stride) + fsize #计算感受野大小时，忽略了图像边缘的影响，即不考虑padding的大小
return RF
if __name__ == '__main__':
print "layer output sizes given image = %dx%d" % (imsize, imsize)
for net in net_struct.keys():
print '************net structrue name is %s**************'% net
for i in range(len(net_struct[net]['net'])):
p = outFromIn(imsize,net_struct[net]['net'], i+1)
rf = inFromOut(net_struct[net]['net'], i+1)
print "Layer Name = %s, Output size = %3d, Stride = % 3d, RF size = %3d" % (net_struct[net]['name'][i], p[0], p[1], rf)
运行结果如下。从运行结果可以看出论文中ZF-5网络感受野大小为139是什么得到的了。
2 感受野上的坐标映射
① 计算公式
对于Convolution/Pooling Layer:
$$p_i=s_i \cdot p_{i+1}+[(k_i-1)/2-padding]$$
对于Neuronlayer（ReLU/Sigmoid/...）:
$$p_i=p_{i+1}$$
其中$p_i$为第$i$层感受野上的坐标，$s_i$为Stride的大小，$k_i$为感受野的大小。
② 例子
上面是计算任意一个Layer输入输出的坐标映射关系，如果是计算任意Feature Map之间的关系，只需要用简单的组合就可以得到，下图是一个简单的例子:
③ 简化版本
何凯明在SPP-NET中使用的是简化版本，将2小节公式中的Padding都设为$\left \lfloor k_i/2 \right \rfloor$，公式可进一步简化为：$p_i=s_i \cdot p_{i+1}$
3 原始图像的ROI如何映射
SPP-NET是把原始ROI的左上角和右下角 映射到Feature Map上的两个对应点。 有了Feature Map上的两队角点就确定了对应的Feature Map 区域（下图中橙色）。
左上角取$x'=\left \lfloor x/S \right \rfloor+1, y'=\left \lfloor y/S \right \rfloor+1$；右下角的点取$x'=\left \lceil x/S \right \rceil-1, y'=\left \lceil y/S \right \rceil-1$。其中S为坐标映射的简化计算版本，即$S=\prod_{0}^{i}s_i$。
Fast-RCNN
流程框图
算法特点
1 Fast-RCNN直接使用Softmax替代了RCNN中SVM进行分类，同时在网络中加入了多任务函数边框回归，实现了端到端的训练（除SS Region Proposal阶段）。
2 借鉴SPP-NET，提出了一个ROI层。ROI Pooling Layer实际上是SPP-NET的一个精简版，SPP-NET对每个Proposal使用了不同大小的金字塔映射，而ROI Pooling Layer只需要下采样到一个7x7的特征图。对于VGG16网络conv5_3有512个特征图，这样所有Region Proposal对应了一个7*7*512维度的特征向量作为全连接层的输入。
3 使用了不同于SPP-NET的训练方式，训练时，把同张图片的Prososals作为一批进行学习，而Proposals的坐标直接映射到conv5层上，这样相当于一张图片的所有训练样本只卷积了一次。
4 论文在回归问题上并没有用很常见的2范数作为回归，而是使用所谓的鲁棒L1范数作为损失函数。
5 论文将比较大的全链接层用SVD分解了一下使得检测的时候更加迅速。
几个要点
一、联合训练
联合训练（Joint Training）指如何将分类和边框回归联合到一起在CNN阶段训练，主要难点是损失函数的设计。Fast-RCNN中，有两个输出层：第一个是针对每个ROI区域的分类概率预测，$p=(p_0, p_1, \cdots, p_K)$；第二个则是针对每个ROI区域坐标的偏移优化，$t^k = (t^k_x, t^k_y, t^k_w, t^k_h)$，$0 \le k \le K$是多类检测的类别序号。每个训练ROI都对应着真实类别$u$和边框回归目标$v=(v_x,v_y,v_w,v_h)$，对于类别$u$预测边框为$t^u=(t_x^u,t_y^u,t_w^u,t_h^u)$，使用多任务损失$L$来定义ROI上分类和边框回归的损失：
$$L(p,u,t^u,v)=L_{cls}(p,u)+\lambda [u \ge 1]L_{loc}(t^u,v)$$
其中$L_{cls}(p,u)=-\log p_u$表示真实类别的log损失，当$u \ge 1$时，$[u \ge 1]$的值为1，否则为0。下面将重点介绍多任务损失中的边框回归部分（对应坐标偏移优化部分）。
二、边框回归
假设对于类别$u$，在图片中标注的真实坐标和对应的预测值理论上两者越接近越好，相应的损失函数为：
$$L_{loc}(t^u, v) = \sum_{i \in {x, y, w, h}} \text{smooth}_{L_1}(t_i^u- v_i)$$
其中
$$\text{smooth}_{L_1}(x) = \left \{ \begin{aligned} & 0.5x^2 & |x| \le 1 \\ &|x|-0.5 & \text{otherwise}\end{aligned} \right.$$
Fast-RCNN在上面用到的鲁棒$L_1$函数对外点比RCNN和SPP-NET中用的$L_2$函数更为鲁棒，该函数在$(-1, 1)$之间为二次函数，其他区域为线性函数，函数直观图如下图所示。
存在问题
使用Selective Search提取Region Proposals，没有实现真正意义上的端对端，操作也十分耗时。
Faster-RCNN
流程框图
算法特点
1 提出了Region Proposal Network（RPN），将Proposal阶段和CNN分类融到了一起，实现了一个完全的End-To-End的CNN目标检测模型。RPN可以快速提取高质量的Proposal，不仅加快了目标检测速度，还提高了目标检测性能。
2 将Fast-RCNN和RPN放在同一个网络结构中训练，共享网络参数。
几个要点
一、Region Proposal Network
Region Proposal Network（RPN）的核心思想是使用卷积神经网络直接产生Region Proposal，使用的方法本质上就是滑动窗口。RPN的设计比较巧妙，RPN只需在最后的卷积层上滑动一遍，借助Anchor机制和边框回归可以得到多尺度多长宽比的Region Proposal。下图是RPN的网络结构图。
在ZF网络模型下，给定输入图像（假设分辨率为600*1000），经过卷积操作得到最后一层的卷积特征图（大小约为40*60）。在这个特征图上使用3*3的卷积核（滑动窗口）与特征图进行卷积，最后一层卷积层共有256个Feature Map，那么这个3*3的区域卷积后可以获得一个256维的特征向量，后边接Cls Layer和Reg Layer分别用于分类和边框回归（跟Fast RCNN类似，只不过这里的类别只有目标和背景两个类别）。3*3滑窗对应的每个特征区域同时预测输入图像3种尺度（128,256,512），3种长宽比（1:1,1:2,2:1）的Region Proposal，这种映射的机制称为Anchor。所以对于这个40*60的Feature Map，总共有约20000（40*60*9）个Anchor，也就是预测20000个Region Proposal。下图是51*39个Anchor中心，以及9种Anchor示例。
这样设计的好处是什么？虽然现在也是用的滑动窗口策略，但是，滑动窗口操作是在卷积层特征图上进行的，维度较原始图像降低了16*16倍（16如何得到的可参见前文）；多尺度采用了9种Anchor，对应了三种尺度和三种长宽比，加上后边接了边框回归，所以即便是这9种Anchor外的窗口也能得到一个跟目标比较接近的Region Proposal。
二、RPN的损失函数
损失函数定义为：
$$L({p_i}{t_i}) = \frac{1}{N_{cls}} \sum_i L_{cls}(p_i, p_i^*) +\lambda \frac{1}{N_{reg}} \sum_i p_i^* L_{reg}(t_i, t_i^*)$$
其中$i$表示一次Mini-Batch中Anchor的索引，$p_i$是Anchor $i$是否是一个物体，$L_{reg}$即为上面提到的$\text{smooth}_{L_1}(x)$函数，$N_{cls}$和$N_{reg}$是两个归一化项，分别表示Mini-Batch的大小和Anchor位置的数目。
三、网络的训练
如果是分别训练两种不同任务的网络模型，即使它们的结构、参数完全一致，但各自的卷积层内的卷积核也会向着不同的方向改变，导致无法共享网络权重，Faster-RCNN提出了三种可能的方式：
1 Alternating Training：此方法其实就是一个不断迭代的训练过程，既然分别训练RPN和Fast-RCNN可能让网络朝不同的方向收敛，那么我们可以先独立训练RPN，然后用这个RPN的网络权重对Fast-RCNN网络进行初始化，并且用之前RPN输出Proposal作为此时Fast-RCNN的输入，之后不断迭代这个过程，即循环训练RPN、Fast-RCNN。
2 Approximate Joint Training：这里与前一种方法不同，不再是串行训练RPN和Fast-RCNN，而是尝试把二者融入到一个网络内，具体融合的网络结构如下图所示，可以看到，Proposals是由中间的RPN层输出的，而不是从网络外部得到。需要注意的一点，名字中的"Approximate"是因为“This solution ignores the derivative w.r.t. the proposal boxes' coordinates that are also network responses”，也就是说，反向传播阶段RPN产生的Cls Score能够获得梯度用以更新参数，但是Proposal的坐标预测则直接把梯度舍弃了，这个设置可以使Backward时该网络层能得到一个解析解（Closed Results），并且相对于Alternating Traing减少了25-50%的训练时间。
3 Non-approximate Training：上面的Approximate Joint Training把Proposal的坐标预测梯度直接舍弃，所以被称作Approximate，那么理论上如果不舍弃是不是能更好的提升RPN部分网络的性能呢？作者把这种训练方式称为“ Non-approximate Joint Training”，但是此方法只是一笔带过，表示“This is a nontrivial problem and a solution can be given by an “RoI warping” layer as developed in [15], which is beyond the scope of this paper”。
作者没有用上面提到的三种可能方法，而是使用了4-Step Alternating Training，具体步骤如下。
1 用ImageNet模型初始化，独立训练一个RPN网络；
2 仍然用ImageNet模型初始化，但是使用上一步RPN网络产生的Proposal作为输入，训练一个Fast-RCNN网络，至此，两个网络每一层的参数完全不共享；
3 使用第二步的Fast-RCNN网络参数初始化一个新的RPN网络，但是把RPN、Fast-RCNN共享的那些卷积层的Learning Rate设置为0，也就是不更新，仅仅更新RPN特有的那些网络层，重新训练，此时，两个网络已经共享了所有公共的卷积层；
4 仍然固定共享的那些网络层，把Fast-RCNN特有的网络层也加入进来，形成一个Unified Network，继续训练，Fine Tune Fast-RCNN特有的网络层，此时，该网络已经实现我们设想的目标，即网络内部预测Proposal并实现检测的功能。
上述步骤图示如下。
小结
至此，介绍完了以RCNN为代表的基于Region Proposal的深度学习目标检测算法（RCNN，SPP-NET，Fast-RCNN，Faster-RCNN），主要介绍了算法的核心思想和要点难点，代码可以从GitHub得到，更多实现细节可以阅读原论文和代码。接下来会写另一篇文章来介绍以YOLO为代表的基于回归方法的深度学习目标检测算法（YOLO，SSD）。
参考文献
[1] RCNN:"Rich feature hierarchies for accurate object detection and semantic segmentation"
[2] SPP-NET:"Spatial pyramid pooling in deep convolutional networks for visual recognition"
[3] Fast-RCNN:"Fast R-CNN"
[4] Faster-RCNN:"Faster R-CNN: Towards real-time object detection with region proposal networks"
[5] RCNN, Fast-RCNN, Faster-RCNN的一些事
[7] 原始图片中的ROI如何映射到到Feature Map
[8] Fast R-CNN
[10] Faster R-CNN
[11] 基于深度学习的目标检测研究进展
