论文名称：Selective Search for Object Recognition

论文地址：Selective Search

论文代码：Selective Search代码

# Selective Search算法流程 Algorithm1:Selective Search Input:(color)image Output:Set of object location hypotheses L 1.生成初始区域集R 2.初始化相似集合S为空集 3、foreach (ri,rj) do #计算区域内每个相邻区域的相似度      计算s(ri,rj)      把s(ri,rj)合并到S 4、while S不等于空集 do  #将S集合中相似度最高的区域合并为一个区域      取出S集合中相似度最高的s(ri,ji)      对ri，ji合并成rt      把rt加入到S中      删除S集合中和ri有关的子集      删除S集合中和rj有关的子集      计算新集合与所有集合的相似性 5.跳转到步骤4，直到S为空 

# 生成初始区域集R的方法 Algorithm2.区域分割算法 Input:有n个节点和m条边图G Output:一系列区域集R 1、 根据权重值非递减排序 2、 最初的分割记录为S(0)，即每个节点属于一个区域 3、 按以下方式S(q-1)构造S(q)：第q条边连接的两个节点是vi和vj，如果在S(q-1)中vi和vj属于两个区域，第q条边的权重小于两个区域的内间距，则合并两个区域。否则令S(q) = S(q-1)。否则令S(q) = S(q-1)。 4、 从q=1到q=m，重复步骤2 5、 返回S（m）即所需分割区域的集合 

1.区域内间距求法:

MST对应区域最小生成树，即区域内间距对应最小生成树中权值最大的边对应权值。

2.区域间距求法:

也就是说，在所有属于两个区域和有边链接的点对中，找到权值最小的对方的权值为区域间距（如果两个区域的点没有边缘连接，则定义间距为无限大）

3.判断两个集合能否合并的方法

上述公式三是否可以合并两个区域？true表示不合并(即区域间距远大于区域间距)，fasle表示可以合并 。

4.最小生成树

见博客https://blog.csdn.net/qq_35644234/article/details/59106779讲解

5.计算区域相似度

①颜色相似度：计算每个通道的颜色直方图，然后取每个对应的bins直方图的最小值。这样，两个区域合并后的直方图也很容易计算直接通过直方图的大小加权区域的大小，然后除以总区域的大小。将颜色空间转换为HSV，以下是每个通道bins=25计算直方图，使每个区域的颜色直方图为25*3=75个区间。

②纹理相似性：计算方法与颜色距离几乎相同，我们计算每个区域的快速度sift其中方向数为8、3个通道，每个通道bins为10，对于每幅图像得到240维的纹理直方图。

③尺寸相似性：优先合并小区域。如果只通过颜色和纹理特征合并，合并区域很容易不断吞并周围区域。因此，多尺度只应用于局部，而不是全球多尺度。因此，我们给小区域更多的权重，以确保图像的每个位置都是多尺度的合并。

④区域适宜性相似性：不仅要考虑各区域特征的一致性，区域一致性也很重要，一致性是指合并区域应尽可能标准化，不能合并悬崖区域，明显不符合常识，反映区域外矩形重叠面积较大。因此，该区域的适当相似性被定义为：

⑤通过各种相似性，通过各种策略获得region proposal，当然，最简单的方法是加权：

⑥参数始化多样性，我们基于图的图像分割得到初始区域，而这个初始区域对于最终的影响是很大的，因此我们通过多种参数初始化图像分割，也算是扩充了多样性。

6、给区域打分

​ 通过上述的步骤我们能够得到很多很多的区域，但是显然不是每个区域作为目标的可能性都是相同的，因此我们需要衡量这个可能性，这样就可以根据我们的需要筛选region proposal个数。

​ 本文做法是给予最先合并的图片块较大的权重，比如最后一块完整图像权重为1，倒数第二次合并的区域权重为2以此类推。但是当我们策略很多，多样性很多的时候这个权重就会有太多的重合了，因为不好排序。本文做法是给他们乘以一个随机数，然后对于相同的区域多次出现的就做权重叠加，毕竟多个方法都说你是目标，也是有理由的。这样就得到了所有区域的目标分数，也就可以根据自己的需要选择需要多少个区域了。

论文名称：Edge Boxes: Locating Object Proposals from Edges

论文链接：EdgeBoxes

论文源码：EdgeBoxes实现

selective search与edgeboxes的调包实现

①对于一张image，计算每一个pixel的edge response，在论文中使用Structured Edge Detector来判断物体的边界。然后使用NMS去整理edge，得到最后较为稳定的object edges。

②计算edge groups 和 affinity：直观的来说，笔直的边界具有较高的affinity，而曲率较高的边界的affinity较低。给定一个bbox，根据bbox内部含有的edge的affinity的最大值来判断bbox的boundary。给定一个edges group的几个，计算两两相邻groups之间的affinity。如果两个groups之间均值夹角接近于groups的方向，则说明这两个edge groups有着较高的affinity。

③计算bounding box的score：从上面得到了edges groups集合S和他们的affinity，可以计算每一个candidate bounding box的object proposal score。首先计算在group Si 中的所有edges p的mp值的和，为mi，在group Si中计算si是否完全包含在b中的连续值wb(xi) ，介于[0,1]。

使用一种高效的算法，去计算每一个Sb。上面的公式可以求出edges group Si 与bounding box中含有最高的affinity的一些path。在上面的公式计算下，很多的pairwise都是0。下面可以计算score：

其中 b w b_w bw​和 b n b_n bn​代表box的width 和height。k值为1.5，作用是对大windows会有更多的edges进行偏置调节。同时发现box中央的edges会比靠近box边界的edges的作用更小。所以在这里对位于box中央的bin做一个调整处理。定义box的center的指标是：bin的width和height是整个box的一半，即 b w 2 \frac{b_w}{2} 2bw​​, b n 2 \frac{b_n}{2} 2bn​​。

④查找策略：使用sliding window search 在一个image上进行位置，尺度和纵横比上的查找bbox，在含有一个object的区域，可能会产生更多的bounding boxes和更密集地聚集。利用IoU去筛选，提炼最终合并bounding box。然后最后是对得到的bounding boxes进行NMS，得到最终的sorted boxes。

论文名称：《Rich feature hierarchies for accurate object detection and semantic segmentation》

论文链接：R-CNN

摘要：在过去几年中，在标准PASCAL VOC数据集上目标检测性能保持稳定。性能最好的方法是复杂的集成系统，通常将多个低级图像特征与高级上下文相结合。在本文中，我们提出了一种简单且可扩展的检测算法，与之前在VOC 2012上获得的53.3%的平均精度相比，平均精度（mAP）提高了30%以上。我们的方法结合了两个关键观点：（1）一个可以将高容量CNN应用于自下而上的region proposal，以便定位和分割对象；（2）当有label的训练数据稀缺时，这时就用到了监督预训练作为辅助任务，然后进行特定区域的微调，就可以显著提高性能。由于我们将区域提议与CNN相结合，我们将此方法称为R-CNN：具有CNN特征的区域。我们还将R-CNN与OverFeat进行了比较，OverFeat是最近提出的一种基于类似CNN结构的滑动窗口检测器。我们发现，在200类别的ILSVRC2013检测数据集上，R-CNN的表现远优于OverFeat。

关注的两个问题：①用深度网络定位目标②用小量的标注数据训练一个高容量模型。

解决CNN定位问题：使用区域识别范式操作。具体操作为：测试时在输入图片上产生2000个类别独立的region proposal，用CNN从每个proposal上提取固定长度的向量，然后用特定类别的线性SVM对每个region进行分类。用仿射图像变形去计算来自每个region proposal的固定大小CNN输入。

解决标注数据缺失问题：在大型辅助数据集ImageNet上进行监督预训练，在小数据集VOC上进行迁移学习微调操作。（传统方法为先进行无监督预训练再进行有监督微调操作）

R-CNN结构图：

R-CNN包括三个模块：RP生成模块，特征提取模块，分类模块。

①RP生成模块：生成类别独立的region proposal模块，使用选择性搜索方法。

选择性搜索方法：首先通过类似聚类方法在图像中找到初始的分割区域（颜色、纹理、大小、形状、相似度比较相似的区域），然后对这些区域进行加权合并产生不同层次的2000个候选框。

②特征提取模块：用大型CNN(AlexNet)从每个region提取固定长度的特征向量的模块。

候选框缩放原则：使用非等比例缩放（不保留长宽比）且连带邻近像素的方法（dilate proposal），连带的像素作者使用P=16，多出来的像素全部填为此图的像素平均值，喂到CNN之前每个像素都要做去均值操作。下图最右边的两张图表示本文使用的缩放原则。

③分类模块：使用特定类别的线性SVM分类器。

为什么用SVM分类而不用softmax？

答：微调时正负样本的选择策略是与GT的IOU最大且IOU大于0.5的候选框为正样本（与GT有偏离，精确定位性能差），其余候选框为负样本；而训练各类别SVM分类器时GT框为正样本（精确定位性能好），与GT的IOU小于0.3的候选框为该类负样本（用到难例挖掘），忽略与GT的IOU大于0.3的候选框。 ​ 选择sotfmax之后正负样本的选择策略要跟着微调时的策略来，因此造成性能没有SVM分类那么好。

整个过程描述：将输入图像用选择性搜索方法生成2000个候选框，将每个候选框都强制缩放为227×227大小的RGB图像，然后将每一张RGB图像逐一输入同一个CNN中提取出一个4096维度的特征向量，最后用线性SVM对这个向量进行分类，在分类的同时还进行了BBox的回归操作。

总结：该设计是一个由上而下产业链的设计，不是端到端的设计，这使得流程中只要有一个地方出差错整体性能将会跟着下降。而且这种设计很耗时，主要耗费都在2000张RGB图像逐一输入到CNN中得到特征向量的计算上。

R-CNN缺点：①训练是个多阶段的流水线过程（首先在目标proposal上对卷积网络进行微调，然后让SVM适应卷积网络输出的特征，最后需要学习BBox回归） ​ ②训练非常耗费时间和空间 ​ ③检测速度非常慢（测试阶段）

改进点：①提取候选框：EdgeBoxes、RPN网络 ②共享卷积运算：SPPNet、Fast R-CNN ③兼容任意尺寸图像：SPP、ROI Pooling ④预设长宽比：Anchor ⑤网络结构：端到端 ⑥融合各层特征：FPN

论文名称：《Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition》

论文地址：SPPNet

论文源码：SPPNet实现

摘要：现有CNN需要一个固定大小的输入图像。这一要求是“人为的”，可能会降低任意大小/比例的图像或子图像的识别精度。在这项工作中，我们为网络配备了另一种**池化策略“空间金字塔池化”**以消除上述要求。这种新的网络结构称为SPP网络，它可以生成固定长度的表示，而不管图像大小/比例如何。金字塔池化对于目标变形也鲁棒。有了这些优势，SPP网络总体上改进了所有基于CNN的图像分类方法。在ImageNet 2012数据集上，我们证明了SPP net提高了各种CNN架构的准确性，尽管它们的设计不同。在Pascal VOC 2007和Caltech101数据集上，SPP net使用单个完整图像表示，无需微调，即可获得最先进的分类结果。 SPP网络的功能在目标检测中也很重要。使用SPP网络，我们只从整个图像中计算一次特征映射，然后在任意区域（子图像）中汇集特征，生成用于训练检测器的固定长度表示。该方法避免了重复计算卷积特征。在处理测试图像时，我们的方法比R-CNN方法快24-102倍，同时在Pascal VOC 2007上实现了更好或类似的精度。 在2014年ImageNet大规模视觉识别挑战赛（ILSVRC）中，我们的方法在所有38个团队中的目标检测和图像分类排名分别为#2和#3。

问题：CNN需要固定大小的输入图像（卷积层其实不需要固定尺寸的输入图也能产生任意尺寸大小的特征图，但是FC层则需要固定大小的输入）。

方案：提出空间金字塔池化层，在卷积层最后一层加SPP层，该层可以池化特征产生固定大小的输出。

SPP优点：①不论输入图像大小可产生固定带小的输出； ②使用多级空间池化核，多级池化对目标变形具有鲁棒性； ③由于输入尺寸较灵活，SPP可以池化在不同尺度上提取到的特征。

对R-CNN的改进点： ①让卷积层在整张输入图像中只运行一次（而不是像R-CNN中在整张图像中提取到2000多个候选框再强制扭曲为227×227大小的2000张图像最后逐图像输入CNN中让CNN运行2000多次），然后让SPPnet在特征图上提取特征。 ②用到EdgeBoxes的快速提案法，整张图的处理速度更快了。

SPP是一种自适应的max-pooling方法

思路：根据输入特征图的大小和期望输出特征图的大小来确定池化框的size和stride，如假设输入为C×M×M的特征图，期望SPP输出C×N×N的特征图，则SPP的池化框大小为 c e i l ( M N ) ceil(\frac{M}{N}) ceil(NM​)，其中ceil为向上取整操作；滑动stride为 f l o o r ( M N ) floor(\frac{M}{N}) floor(NM​)，其中floor为向下取整操作。

• 池化框数量的确定：SPP输出C×N×N的特征图，则bin数量为N×N。如下图最左边的SPP欲输出4×4大小的特征图，则bin数量为16（可以理解为将原来的特征图分为16份，在每一份上做最大池化操作）。

• 维度数确定 ：等于最后一层卷积层的卷积核个数。例如下图为256维。

• L-level SPP：L个输出尺寸不同的SPP形成的金字塔网络。一般将每个SPP的输出进行flatten，然后再concatenate，最后输入到FC或softmax。例如下图为3-level SPP。

上图操作可以可视化为下面的图：

注意：最右边有一个覆盖全图的池化框，这其实是全局池化操作。

全局池化：可以做全局平均池化和全局最大池化

优点：①减少模型尺寸、参数量；②防止过拟合现象

总结：此篇论文对R-CNN最大的改进点在于特征提取阶段：将整张待检测的图片输入CNN中，进行一次性特征提取，得到feature maps，然后在feature maps中找到各个候选框的区域，再对各个候选框采用金字塔空间池化，提取出固定长度的特征向量。R-CNN的做法是：将每个候选框逐个输入到CNN中提取出4096维向量。因为SPP-Net只需要对整张图片进行一次特征提取，速度会大大提升。

SPPnet缺点：①训练过程仍是个多阶段的流水线； ​ ②微调算法不能更新SPP层之前的卷积层，因此（固定的卷积层）限制了非常深的网络的准确性。

改进点：①改为单阶段训练； ​ ②使得算法可以更新网络所有层。

整个训练和测试流程见这篇博客的部分三：https://blog.csdn.net/weixin_45422462/article/details/108412656

对SPP层的定义：

import math
def spatial_pyramid_pool(self, previous_conv, num_sample, previous_conv_size, out_pool_size):
    ''' previous_conv: a tensor vector of previous convolution layer num_sample: an int number of image in the batch(这里等于1) previous_conv_size: size of featrue map in previous convolution layer out_pool_size: expected output size of max pooling layer returns: a tensor vector with shape [1 x n] is the concentration of multi-level pooling '''    
    for i in range(len(out_pool_size)):
        h_siz = int(math.ceil(previous_conv_size[0] / out_pool_size[i]))
        w_siz = int(math.ceil(previous_conv_size[1] / out_pool_size[i]))
        
        h_str = int(math.floor(previous_conv_size[0] / out_pool_size[i]))
        w_str = int(math.floor(previous_conv_size[1] / out_pool_size[i]))
        
        h_pad = (h_siz*out_pool_size[i] - previous_conv_size[0] + 1)/2
        w_pad = (w_siz*out_pool_size[i] - previous_conv_size[1] + 1)/2
        
        maxpool = nn.MaxPool2d((h_wid, w_wid), stride=(h_wid, w_wid), padding=(h_pad, w_pad))
        x = maxpool(previous_conv)
        if(i == 0):
            spp = x.view(num_sample,-1)
            # print("spp size:",spp.size())
        else:
            # print("size:",spp.size())
            spp = torch.cat((spp,x.view(num_sample,-1)), 1) #concat操作
    return spp

带有SPP层的CNN网络：

import torch
import torch.nn as nn
from torch.nn import init
import functools
from torch.autograd import Variable
import numpy as np
import torch.nn.functional as F
from spp_layer import spatial_pyramid_pool
class SPP_NET(nn.Module):
    ''' A CNN model which adds spp layer so that we can input multi-size tensor '''
    def __init__(self, opt, input_nc, ndf=64,  gpu_ids=[]):
        super(SPP_NET, self).__init__()
        self.gpu_ids = gpu_ids
        self.output_num = [4,2,1]
        
        self.conv1 = nn.Conv2d(input_nc, ndf, 4, 2, 1, bias=False)
        
        self.conv2 = nn.Conv2d(ndf, ndf * 2, 4, 1, 1, bias=False)
        self.BN1 = nn.BatchNorm2d(ndf * 2)

        self.conv3 = nn.Conv2d(ndf * 2, ndf * 4, 4, 1, 1, bias=False)
        self.BN2 = nn.BatchNorm2d(ndf * 4)

        self.conv4 = nn.Conv2d(ndf * 4, ndf * 8, 4, 1, 1, bias=False)
        self.BN3 = nn.BatchNorm2d(ndf * 8)

        self.conv5 = nn.Conv2d(ndf * 8, 64, 4, 1, 0, bias=False)
        self.fc1 = nn.Linear(10752,4096)
        self.fc2 = nn.Linear(4096,1000)

    def forward(self,x):
        x = self.conv1(x)
        x = self.LReLU1(x)

        x = self.conv2(x)
        x = F.leaky_relu(self.BN1(x))

        x = self.conv3(x)
        x = F.leaky_relu(self.BN2(x))
        
        x = self.conv4(x)
        x = F.leaky_relu(self.BN3(x))
        
        x = self.conv5(x)
        spp = spatial_pyramid_pool(x,1,[int(x.size(2)),int(x.size(3))],self.output_num)

        fc1 = self.fc1(spp)
        fc2 = self.fc2(fc1)
        s = nn.Sigmoid()
        output = s(fc2)
        
        return output

论文名称：《fast R-CNN 》

论文链接：Fast R-CNN

源码(fast-RCNN实践)：Fast R-CNN实现

摘要：本文提出了一种基于区域卷积网络的快速目标检测方法（Fast R-CNN）。Fast R-CNN基于之前的工作，使用深度卷积网络对目标proposal进行有效分类。与之前的工作相比，Fast R-CNN采用了多项创新技术来提高训练和测试速度，同时也提高了检测精度。Fast R-CNN比R-CNN快9倍，在测试时快213倍，在PASCAL VOC 2012上得到了更高的mAP。与SPPnet相比，Fast R-CNN训练VGG16的速度快3倍，测试速度快10倍也更准确。

问题：解决目标检测定位的复杂性的时候牺牲了速度、准确性和简化度。

解决措施：提出单阶段训练算法，使之可以联合学习对目标proposal分类和优化空间位置这两个动作。最终结果可以训练非常深的检测网络，如VGG。

Fast R-CNN算法的优点：

• ①较R-CNN和SPPnet更高的mAP；
• ②单阶段训练，用多任务损失；
• ③训练可以更新网络所有层；
• ④特征计算不需要耗费磁盘空间存储。

过程分解： ①输入整张图像经过两个分支，一个分支将图像送入到卷积网络中得到特征图，另一个分支通过selective search方法提取region proposal；两路分支都是整个Fast RCNN的输入； ②将region proposal映射到CNN的最后一层卷积特征图上； ③对于每个region proposal，ROI池化层使每个RoI生成固定尺寸的特征图； ④每个特征向量输入到一系列FC层中，这些层最终分支为两个同级输出层：一个层对K个目标类加上一个“背景”类生成softmax概率估计，另一层为K个对象类中的每一类输出四个实数，即边框回归偏移量。每组4个值代表了K类中的其中一类的精确边框位置的编码。

ROI池化层：用最大池化将内含感兴趣区域的特征图转换为小的固定尺寸为H×W大小的特征图（H，W是相互独立的）。本文中ROI池化层是个卷积特征图中的矩形窗，每个ROI都由四元组 ( r , c , h , w ) (r,c,h,w) (r,c,h,w)定义，其中 ( r , c ) (r,c) (r,c)代表左顶部， ( h , w ) (h,w) (h,w)代表高和宽。这些坐标都是对应原图像的，而不是输出的特征图的，因此还需要把原图像的坐标系映射到特征图上！

ROI池化层过程：将h×w的region proposal用尺寸为h/H，w/W的子窗分割为H×W大小的网格然后将region proposal映射到最后一个卷积层输出的特征图，最后计算每个网格里的最大值作为该网格的输出。其中池化操作在每个特征图通道中都是独立的。ROI层其实是one-level SPP层的一种特殊情况。

ROI池化过程：

①输入的固定大小的feature map

②region proposal 投影之后位置(左上角,右下角坐标)：(0,3),(7,8）

③将其划分成（2×2）个sections（因为输出大小为2*2）,我们可以得到：

④对