目标检测是计算机视觉领域里的一个重要分支，其本质内容是：What objects are where？ 它同时作为一个基础任务为领域内一些更复杂的问题（如实例分割、图片文本识别、目标跟踪等）提供支持。从应用的角度来看，目标检测可以划分为两大类：通用目标检测和检测应用。通用目标检测主要是探索在统一的算法框架下检测不同类型目标的方法，类似于人类的视觉感知；检测应用则侧重于实际场景，例如行人检测、人脸检测和文本检测等。
Map
目标检测领域从1999年发展至今已过了大约20个年头。这期间相关的算法模型发展路线如下图所示（摘自原论文）：
本文以此为依据按照发展历程记录各个算法的关键贡献。
Traditional Detection Methods
在发展前期，该领域内的算法主要以传统算法为准，即需要自己去设计相关特征供机器学习。
Viola-Jones Detectors
2001年，P.Viola和M.Jones发表了经典的目标检测算法（Viola-Jones Detector）。该算法是在Adaboost的基础上使用类Haar特征作为输入进行检测，同时使用滑窗的方式来判断某一区域是否有目标。滑窗的引入增加了大量的计算负担，为此作者采用了几种方法对算法进行了加速：
- Integral image：Haar特征考虑的是某一特定位置相邻的矩形区域，把每个矩形区域的像素相加然后再相减（example）。为了计算Haar-like特征，需要对矩形区域的所有像素求和，一个图像所能形成的矩形区域有大有小，如果每个矩形区域都用遍历所有像素再求和的运算方法。积分图就是对于图像中的任何一点，该点的积分图像值等于位于该点左上角的所有像素之和，公式如下：
\[ I(x,y) = \sum_{x'< x}\sum_{y' < y}f(x',y') \]
积分图中存在如下关系：
\[ I(x,y) = f(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1) \]
以上\(I\)表示积分图，\(f\)表示原图像。通过积分图，可以计算图像上任意矩形区域的像素和：
\[ S_{abcd} = I(d)-I(b)-I(c)+I(a) \]
- Feature selection：图像提取出来的Haar特征是比较多的，作者假设这些特征中只有一小部分是有用的，并使用了Adaboost进行了特征筛选，通过减少特征数目来减轻运算负担。
- Detection cascades：为了进一步降低计算量，作者没有使用传统的Adaboost分类器，而是使用多个小型Adaboost级联，同时一旦在某一级分类器中检测出不是目标，则立即停止该区域的检测。
HOG Detectors
2005年，N.Dalal和B.Triggs提出了HOG（Histogram of Oriented Gradients）特征提取算法，它通过计算和统计图像局部区域的梯度方向直方图来构成特征。这么做是因为图像中局部目标的表象和形状能够被梯度或边缘的方向密度分布很好地描述。具体是对灰度图像进行分块，在计算各块中各像素点的梯度或边缘方向直方图，最后组合这些直方图构成特征。
上图展示了一个典型的HOG检测器执行的具体步骤。这里使用Gamma矫正目的是调节图像的对比度，降低图像局部的阴影和光照变化所造成的影响，同时可以抑制噪音的干扰。由于局部光照的变化以及前景背景对比度的变化，使得梯度强度的变化范围非常大。这就需要对梯度强度做归一化，归一化能够进一步地对光照、阴影和边缘进行压缩。作者通过联合几个cell的特征来进行归一化操作。
Deformable Part-based Model (DPM)
2008年，P.Felzenszwalb提出了可变组件模型（Deformable Part Model），\(v_i\)即一种基于组件的检测算法，是HOG检测器的一种扩展。一个典型的DPM模型包括一个根滤波器和一些组件滤波器，其中根滤波器覆盖了整个目标，而组件滤波器是覆盖目标某一部分的高分辨率模板。对于一个目标，该模型在形式上将其定义为一个元组：\((F_0,P_0,P_1,...,P_n,b)\)，\(F_0\)为根滤波器，\(P_i\)为第\(i\)个部件的模型， 是表示偏差值。每一个部件模型用一个三元组表示\((F_I, v_i, d_i)\)，\(F_i\)是第\(i\)个部件的模型，是一个二维向量，指定第\(i\)个滤波器的锚点位置（改位置为未发生形变的标准位置）相对于根的坐标，\(d_i\)是一个四维向量，指定了一个二次函数的参数，此二次函数表示部件的每一个可能位置相对于锚点位置的偏移代价。
上图是根模型、组件模型和组件偏移代价的可视化图。这里以行人为例，其中左边的图片是根模型，它比较粗略地表示了一个直立行人；中间图片是组件模型，各组件模型为矩形框内的部分，分辨率为根模型的两倍，这样可以获得更好的效果；右边图片则是组件模型的偏离损失，越亮的区域表示偏离损失代价越大，组件模型的标准位置的偏离损失为0。为了降低模型的复杂度，根模型和组件模型都是轴对称的。
DPM采用了传统的滑动窗口检测方式，通过构建尺度金字塔在各个尺度搜索。下图为某一尺度下的行人检测流程，即行人模型的匹配过程。 某一位置与根模型或组件模型的响应得分，为该模型与以该位置为锚点（即左上角坐标）的子窗口区域内的特征的内积。也可以将模型看作一个滤波算子，响应得分为特征与待匹配模型的相似程度，越相似则得分越高。左侧为根模型的检测流程，滤波后的图中，越亮的区域代表响应得分越高。右侧为各组件模型的检测过程。首先，将特征图像与模型进行匹配得到滤波后的图像。然后，进行响应变换。响应变换是以锚点为参考位置，综合组件模型与特征的匹配程度和组件模型相对标准位置的偏离损失，得到的最优的组件模型位置和响应得分。
Deep Larning Detection Methods
自从2012年Alex神经网络在Imagenet上获得SOTA的成绩，神经网络开始被人重视，这里介绍几种关键算法。
RCNN
2014年，R.Girshick等人发表了RCNN，首次将神经网络模型引入目标检测领域。RCNN通过selective search从原图中获得大量的候选框，对于每个候选框使用卷积神经网络获取图像特征，之后对该图像特征调用线性SVM分类器进行分类，最后即可得到图像中目标的类别和位置大小。
整体上模型可分为三部分：
- 生成与类别无关的候选区域
- 用来从每一个候选区域中提取固定长度特征向量的卷积网络
- 一组线性SVM分类器
SPPNet
对于RCNN，它需要将每个候选区域缩放到固定尺寸，然后对每个区域提取卷积特征。这两步操作带来了一些性能瓶颈。为了解决这些瓶颈问题，2014年，K.He等人提出了SPPNet模型。作者在特征提取网络最后的全连接层前添加了一个池化层来对任意输入产生固定的输出，以此来解决RCNN中需要固定尺寸的候选区域输入问题。模型还借助了空间金字塔的思路，即将一副图像划分为不同尺度的块，对每一块提取特征最后拼接在一起。
下图展示了SPPNet和RCNN在处理不同尺寸的输入图像的差别。RCNN会通过裁剪或缩放来获取固定大小的图片，再传入卷积神经网络进行计算。SPPNet则通过先经过卷积网络提取特征，再由池化层获得固定大小的特征向量作为全连接层的输入。最重要的一点是每幅图片只需要提取一次特征。
空间金字塔池化层，其主要目的是对于任意尺寸的输入产生固定大小的输出。思路是对于任意大小的feature map首先分成16、4、1个块，然后在每个块上做最大池化操作，池化后的特征拼接得到一个固定维度的输出。以满足全连接层的需要。
Fast RCNN
和RCNN一样，SPPNet也需要训练CNN提取特征，然后训练SVM分类这些特征。需要巨大的存储空间，并且分开训练也很复杂。2015年，R.Girshick推出了Fast RCNN模型，他将检测器和框回归器统一在一个框架内，方便进行统一训练。它将整个图像和一组候选框都作为输入，模型首先用一组卷积层和最大池化层对整张图像进行特征提取，再在提取出的特征图上，针对每一个候选框用RoI pooling提取出一个固定长度的特征向量，之后送入全连接层，最终分成两个分支分别进行目标识别和边界框回归。虽然和RCNN和SPPNet相比，Fast RCNN有着很大的提升，但是该模型还是使用selective search生成候选框，这是该模型的主要速度瓶颈。
Faster RCNN
对于RCNN、SPPNet以及Fast RCNN采用的都是selective search来获得目标候选框，这部分的操作拖慢了整个模型的运行速度。2015年，S.Ren等人提出了Faster RCNN，这是首个端到端的、运行速度接近实时的深度学习目标检测模型。主要贡献是提出了RPN层。通过RPN层可以快速的生成候选区域，同时也引入了锚框来框选候选区域。大致结构如下，其中红框表示RPN层（图片摘自网络）
Faster RCNN抛弃了传统的通过滑动窗口和selective search来生成候选框的做法，直接使用RPN生成检测框，这也是Faster RCNN的巨大优势，能极大提升检测框的生成速度，也是从这里，目标检测引入了Anchor来作为目标候选框。
Anchor的生成主要由长宽比和缩放尺度这两个参数决定的。例如右图是Faster RCNN在三个长宽比（ratios=[0.5, 1.0, 2.0]）和三个缩放尺度（scales=[8, 16, 32]）下生成的九个锚框。
锚框是分布在特征图的每一个像素点上的，即锚框的中心位置为特征图像素点的位置。最后生成的锚框会布满整个特征图，并且同一像素点下的各个锚框尺度并不一样，所以实际上通过锚框就引入了检测中常用到的多尺度方法。
大致计算方式如下：
\[ \begin{cases} w\times h = s \\ \frac{w}{h} = ratio \end{cases} \Rightarrow \begin{cases} h = \sqrt{\frac{s}{ratio}} \\ w = ratio\cdot h = \sqrt{s\cdot ratio} \end{cases} \]
进一步可以得到
\[ \begin{cases} h = \sqrt{\frac{s}{ratio}\cdot scale} \\ w = ratio\cdot h = \sqrt{s\cdot ratio \cdot scale} \end{cases} \]
一张特征图生成锚框大致如下图（摘自网络）：
对于RPN层，下图是RPN网络的具体结构。可以看到RPN网络实际分为2条线，上面一条通过softmax分类anchors获得positive和negative分类，下面一条用于计算对于anchors的bounding box 回归偏移量，以获得精确的proposal。而最后的Proposal层则负责综合positive anchors和对应bounding box regression偏移量获取proposals，同时剔除太小和超出边界的proposals。其实整个网络到了Proposal Layer这里，就完成了相当于目标定位的功能。
RPN大致流程：
生成anchors -> softmax分类器提取positvie anchors -> bbox reg回归positive anchors -> Proposal Layer生成proposals
Feature Pyramid Networks (FPN)
在2017年，T.-Y.Lin等人在Faster RCNN的基础上提出了FPN。之前的神经网络目标检测模型都是只提取了最顶层输出的特征进行检测，而卷积网络较深层的功能有利于类别识别，但它不利于目标的定位。FPN包含了一种具有横向连接的自顶向下的网络结构，可用于构建各种规模的高级语义。后续提出的各种网络中，基本上都包含了这种结构。
在FPN自顶向下的结构中，网络层之间的详细操作如下：
You Only Look Once (YOLO)
2015年，R.Joseph提出了首个深度学习目标检测领域的单阶段模型YOLO。该模型将图片划分为\(S\times S\)个网格，如果有目标对象的中心落在某个网格内，则该网格负责预测该对象。每个网格都会预测\(B\)个边界框以及这些框的置信度，这里置信度是指该框里是否有对象和做出这个判断的把握：\(Pr(Object)*IOU^{truth}_{pred}\)。如果没有对象在框内，则\(Pr(Object)\)为0,否则使用预测框和真实框之间的\(IOU\)作为其置信度数值。
作者将目标检测的流程统一为单个神经网络。该神经网络采用整个图像信息在预测目标的bounding boxes的同时识别目标的类别，实现端到端实时目标检测任务。每个bounding boxes预测五个变量：x、y、w、h、conf，其中前四个是坐标变量，其中x、y为框的中心，w、h则表示宽和长。这里注意中心坐标是相对网格大小的，而长宽是相对整张图像的，conf表示预测框与正类框的IOU。
后面作者也吸取了其它网络模型的特点，对YOLO进行了改进推出了YOLO2和YOLO3。
Single Shot MultiBox Detector (SSD)
与YOLO一样，SSD是一个单阶段检测模型，在2015年由W.Liu等人提出。SSD主要特点是使用了多尺度检测结构。与FPN类似，SSD从不同的卷积层抽取特征图进行检测。由于不同层的感受野大小不一样，所以采取这种方式可以顾及到不同尺寸的目标。SSD还使用了卷积层替换全连接层进行最后的分类回归操作。
RetinaNet
虽然单阶段模型的运行速度要快于二阶段模型，但精度普遍偏低。2017年，T.-Y.Lin等人提出了RetinaNet。作者认为造成单阶段模型精度低的原因是正负样本的极度不均衡，并为此设计出了focal loss损失函数来重新平衡正负样本，这也是RetinaNet的主要贡献点。
最后推出的损失函数为：
\[ loss = -\alpha(1-p_t)^\gamma * log(p_t) \]
其中\(\alpha\)和\(\gamma\)都为超参数。作者在自己的模型上实验显示\(\alpha=0.25\)，\(\gamma=2\)时效果最好。该函数仅在计算分类损失时用到。
CornerNet
最后这个方法虽然不在作者的路线图里，但我个人觉得无锚框这个思想还是挺有意思的，就加了进来。在单阶段的目标检测网络中，基本上都使用了Anchor-box的方法，但这种方法需要大量的anchor，这导致了正负样本不平衡，降低训练效率，同时anchor的设置引入了许多超参数（如：数量、大小、长宽比），增加了网络设计的难度。2018年，Hei Law发表了CornerNet，通过检测目标框的角点来获得目标的位置，这样就无需设置anchor这一步骤。大致结构如下：
其中的特征提取网络主要为Hourglass。Hourglass结构是Newell等人在2016年提出的，主要通过重复自底向上和自顶向下同时联合中间结果，在人体姿态估计中可以很好地利用身体不同部位的空间关系。大致如下图：
corner pooling用于定位目标的顶点。为了更好地适应corner的检测，在目标检测的任务中，目标的角点往往在目标之外，所以角点的检测不能根据局部的特征，而是应该对该点所在行的所有特征与列的所有特征进行扫描。下图以左上角为例。
这里注意对各行各列求池化是有方向的，如下图以黑色箭头的方向进行行或列的最大池化：
Datasets
Pascal VOC
在早期的计算机视觉（2005年到2012年）中，VOC是一个非常重要的开源数据集，其中用于目标检测任务最多的是VOC07和VOC12这两部分。VOC07大致有5k训练图片，包含有12k+标注目标；VOC12有11k的训练图片，包含27k+的标注目标，两者都是对日常生活中常见的20类物品进行标注。
ILSVRC
该数据集（2010年到2017年）包含有200个类别，总的图片数量要比VOC丰富得多，例如ILSVRC-14包含有517k图片数量、534k标注目标。
MS-COCO
2015年起发展到现在的COCO数据集是当前目标检测领域最具挑战性的数据集，它的类别数没有ILSVRC的多，但标注目标远多于ILSVRC。在MS-COCO-17数据集上一共有164k图片，包含80个类别的897k标注目标。
Open Images
2018年开始的Open Images检测挑战赛公布的数据集比起COCO数据集的规模更大。对于目标检测任务，Open Images包含有1910k图片，600个种类的15440k标注目标。
Metrics
准确率与召回率的计算：
| 实际为正类 | 实际为负类 | |
|---|---|---|
| 预测为正类 | TP | FP |
| 预测为负类 | FN | TN |
准确率（Precision）：预测为正类的样本中，真正类所占的比例。
\[ P = \frac{TP}{FP+TP} \]
召回率（Recall）：在真正类样本中，被预测为正类所占的比例。
\[ R = \frac{TP}{FN+TP} \]
在早期，通用的目标检测评估指标是单图虚检（FPPI)，即平均每张图片中能正确检索到的目标数目：
\[ FPPI = \frac{FP}{N} \]
VOC2007引入了AP值。AP值是在不同召回率下准确率的平均值。这定义是针对于单类的，对于多类，通过mAP（各类AP的平均）来评估。
在目标检测中，判断某个框是否正确可以通过计算该框与真实框的重合度（IOU），与设置的重合度阈值比较来得出。
\[ IOU(A,B) = \frac{A\cap B}{A\cup B} \]
这样通过设置不同的IOU阈值可以改变评估标准的严厉程度。2014年后，MS-COCO数据集的评估标准将AP值定义为IOU阈值在0.5到0.95下的AP平均值。
下图列举了各类检测算法的精度：
Challenge
Lightweight object detection: 目标检测算法的总体性能和人眼还是有一定的差距的，在速度上的差距更加明显。所以轻量化的模型设计是一个重要的研究方向；
Detection meets AutoML: 现今的检测模型越来越复杂，同时也依赖于人们的经验。网络结构搜索可以很大程度上减少人们参与模型结构设计的程度，这方面目前已经有模型实现了，例如Efficientdet，在未来也会是一个发展方向；
Weakly supervised detection: 从数据集的发展，我们可以看出检测模型对于数据量的要求是十分巨大的，而数据集的标注十分消耗人力和时间，而且不同人的标注会有一些偏差。所以怎样实现弱监督目标检测是一个重要问题；
Detection in videos: 如何在视频中进行目标检测也是检测领域一个重要的问题。通常的办法是对视频的每一帧都进行检测，但这样做忽略了视频帧与帧之间的关联信息。挖掘视频中空间与时间上的关联对于视频上的目标检测是非常重要的
致谢
本文主要参考了以下文章，更详细的内容建议看原论文：Object Detection in 20 Years: A Survey
Rapid object detection using a boosted cascade of simple features
A discriminatively trained, multiscale, deformable part model
Rich feature hierarchies for accurate object detection and semantic segmentation
Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition
Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks