关于目标检测的那些事儿（1） —— 二十年发展史 ^_^
目标检测是当前计算机视觉和机器学习领域的研究热点。从Viola-Jones Detector、DPM等冷兵器时代的智慧到当今RCNN、YOLO等深度学习土壤孕育下的GPU暴力美学，整个目标检测的发展可谓是计算机视觉领域的一部浓缩史。
简要概括下从1994到至今一共二十余年间目标检测的发展历程。
先看一张图：。。。。。。。
一、基于经典手工特征的目标检测算法（冷兵器时代的智慧）
早期的目标检测算法大多是基于手工特征所构建的。由于在深度学习诞生之前缺乏有效的图像特征表达方法，人们不得不尽其所能设计更加多元化的检测算法以弥补手工特征表达能力上的缺陷。同时，由于计算资源的缺乏，人们不得不同时寻找更加精巧的计算方法对模型进行加速。
【代表算法1】Viola-Jones 检测器
2001年Paul Viola和MichaelJones在CVPR上发表了一篇跨时代意义的文章，后人将文章中的人脸检测算法称之为Viola-Jones（VJ）检测器。VJ检测器在17年前极为有限的计算资源下第一次实现了人脸的实时检测，速度是同期检测算法的几十甚至上百倍，极大程度地推动了人脸检测应用商业化的进程。VJ检测器的思想深刻地影响了目标检测领域至少10年的发展。
VJ检测器采用了最传统也是最保守的目标检测手段——滑动窗口检测，即在图像中的每一个尺度和每一个像素位置进行遍历，逐一判断当前窗口是否为人脸目标。这种思路看似简单，实则计算开销巨大。VJ人脸检测之所以器能够在有限的计算资源下实现实时检测，其中有三个关键要素：多尺度Haar特征的快速计算，有效的特征选择算法以及高效的多阶段处理策略。
在多尺度Harr特征快速计算方面，VJ检测器使用积分图对特征提取进行加速。积分图可以使特征计算量与窗口的尺寸无关，同时也避免了处理多尺度问题时建图像金字塔这一耗时的过程。
在特征选择算法方面，与传统意义上的手工特征不同的是，VJ检测器中使用的Harr特征并非是人为事先设计好的。VJ检测器使用了过完备的随机Haar特征，并通过Adaboost算法从一个巨大的特征池（约180k维）中进行特征选择，选取出对于人脸检测最有用的极少数几种特征从而降低不必要的计算开销。
在多阶段处理方面，作者提出了级联决策结构，并将其形象地称之为“瀑布”（Cascades）。整个检测器由多级Adaboost决策器组成，每一级决策器又由若干个弱分类决策桩（Decision Stump）组成。瀑布的核心思想是将较少的计算资源分配在背景窗口，而将较多的计算资源分配在目标窗口：如果某一级决策器将当前窗口判定为背景，则无需后续决策就可继续开始下一个窗口的判断。
【代表算法2】HOG行人检测器
HOG特征最早是为解决行人检测问题所提出。HOG特征可以认为是在梯度方向直方图特征基础上的又一次重要改进，是所有基于梯度特征的目标检测器的基础。HOG检测器是沿用了最原始的多尺度金字塔+滑窗的思路进行检测。为了检测不同大小的目标，通常会固定检测器窗口的大小，并逐次对图像进行缩放构建多尺度图像金字塔。为了兼顾速度和性能，HOG检测器采用的分类器通常为线性分类器[3]或级联决策分类器[7]等。
在图像的特征提取过程中，最重要的两个概念是不变性（包括平移不变性、旋转不变性、尺度不变性以及光照不变性等）和区分性（特征的表达能力）。为了兼顾二者的特点，HOG特征采用了如下的策略：将图像所在区域划分为不同的细胞单元（Cell），并在每个细胞内统计梯度方向直方图信息。除此之外，为了进一步增强其光照不变性以及非线性表达能力，HOG特征还首次引入了区块（Block）的概念，将相邻的Cell归并为一个Block，并在Block内对Cell特征进行局部归一化。
【代表算法3】可变形部件模型
可变形部件模型（Deformable Part based Model，DPM）是基于经典手工特征的检测算法发展的顶峰，连续获得VOC07、08、09三年的检测冠军。DPM最早由芝加哥大学的P. Felzenszwalb等人提出，后由其博士生R.Girshick改进。2010年，P.Felzenszwalb和R. Girshick被VOC授予“终身成就奖”。DPM的主要思想可简单理解为将传统目标检测算法中对目标整体的检测问题拆分并转化为对模型各个部件的检测问题，然后将各个部件的检测结果进行聚合得到最终的检测结果，即“从整体到部分，再从部分到整体”的一个过程。例如，对汽车目标的检测问题可以在DPM的思想下分解为分别对车窗、车轮、车身等部件的检测问题，对行人的检测问题也可以类似地被分解为对人头、四肢、躯干等部件的检测问题。
在模型结构方面，DPM可视为HOG检测器在其结构上进行了拓展。整个DPM检测器由基滤波器（Root-filter）和一系列部件滤波器（Part-filter）构成。这一部分工作由Felzenszwalb等人在07年提出，并称其为星型模型（Star-model）。后来Girshick又在星型模型的基础上进一步将其拓展为混合模型（Mixture Model），用于解决真实世界中三维物体不同视角下的检测问题。
在模型优化方面，由于DPM模型在训练过程中并未要求详细标注出各个部件的位置，所以采用了一种弱监督学习的策略。由于部件滤波器可以视为模型中的隐含变量，故Girshick进一步将其转化为隐含变量结构SVM的优化问题，并结合难样本挖掘和随机梯度优化策略对该问题进行求解。
在模型加速方面，Girshick还曾将DPM中的线性SVM分类器“编译”为一系列的级联决策桩（Decision Stump）分类器，在不牺牲精度的前提下，将DPM加速了10倍。值得一提的是，这种加速策略本质上是借鉴了VJ检测器快速检测人脸的技术思路。
在算法的后处理方面，DPM算法采用包围框回归和上下文信息集成这两个方法进一步提升检测准确率。其中，包围框回归的主要作用是将检测得到的基滤波器以及部件滤波器所对应的包围框进行整合并利用线性最小二乘回归来得到最终精确的包围框坐标。上下文信息集成的作用在于利用全局信息对检测结果进行重新调整。从本质上来讲，上下文信息反映了各个类别的目标在图像中的联合先验概率密度分布，即哪些类别的目标可能同时出现，哪些类别的目标则不太可能同时出现。
虽然近几年基于深度学习的检测模型从精度上已远远超越了DPM，但DPM中的很多思想直到今天依然重要，例如混合模型、难样本挖掘、包围框回归、上下文信息的利用等。时至今日，这些方法还都深深影响着目标检测领域的发展。
二、基于深度学习的目标检测算法（gpu下的暴力美学）
1、基于Object Proposals的检测算法
Girshick曾提到：“在过去的几年中（2011-2013），目标检测算法的发展几乎是停滞的，人们大多在低层特征表达基础上构建复杂的模型以及更加复杂的多模型集成来缓慢地提升检测精度”。既然深度卷积网络能够学习到非常鲁棒且具有表达能力的特征表示，那么为何不将其引入目标检测流程中用来提取特征呢？当卷积神经网络在2012年ImageNet分类任务中取得了巨大成功后，Girshick等人抓住了机会打破僵局，于2014年率先提出了区域卷积网络目标检测框架（Regionswith CNN features，R-CNN）。自此目标检测领域开始以前所未有的速度发展。
随着卷积神经网络层数的不断加深，网络的抽象能力、抗平移能力和抗尺度变化能力越来越强。对于图像分类任务来说这诚然是一件好事，然而对于检测任务来说却带来了另一个问题：目标包围框精准的位置越来越难以获得。由此便出现了一个矛盾：如果想让检测算法获得更强的平移不变性和尺度不变性，那就必须一定程度地牺牲特征在目标包围框位置和尺度变化上的敏感性，即协变性；相反，如果想要获得更精确的目标包围框定位结果，就必须在平移不变性和尺度不变性上做一些妥协。所以，如果想要将卷积网络有效应用于目标检测问题中，关键是如何有效解决深度网络的平移/尺度不变性和目标检测问题中平移/尺度协变性要求的矛盾。这迫使人们不得不放弃基于特征图+滑动窗口这一套检测方案，从而将关注点转向寻找更加定位精准的目标候选框检测（Object Proposal Detection）算法上来。
在过去的几年里，伴随着深度学习目标检测算法的发展，有非常多的Object ProposalDetection算法被提出，例如Selective Search、Edge Boxes、BING等等。需要注意的是，基于Object Proposal并非是深度学习检测算法的专属，早在传统的手工特征时期，Uijlings等人就尝试过使用Selective Search + 词袋（Bag of Words）特征进行目标检测。
【代表算法1】Regions with CNN Features (R-CNN)
R-CNN使用了一种非常简单的检测策略，首先在图像中提取Object Proposals，接下来把每个Proposal缩放到相同的大小后使用在ImageNet上训练好的Alexnet网络[19]提取特征，最后再使用SVM分类器进行虚警排除和类别判断。R-CNN在VOC07数据集上取得了惊艳的效果，mAP由33.7%（DPM-v5）提升至58.5%。虽然R-CNN取得了很大的进步，但其缺陷也很明显：首先，其训练是多阶段的，较为繁琐和耗时；其次，由于在高密度的候选区域上反复进行特征提取，其检测速度很慢（GPU下每张图40秒，640×480像素）。后来Kaiming He等人提出了SPPNet，很好地解决这个问题。
【代表算法2】Spatial Pyramid Pooling Networks (SPPNet)
Kaiming He等人在2014年提出了SPPNet，用来解决CNN网络提取特征时要求输入图像尺寸固定的问题。与传统的CNN网络模型相比，其创新点是，在卷积层和全连接层之间添加了一个空间金字塔池化（Spatial Pyramid Pooling, SPP）层。SPPNet可做到不经过候选区域的缩放操作就能实现任意大小、任意长宽比区域的特征提取。在不损失精度的前提下，SPPNet是R-CNN的检测速度的38倍。SPPNet有效解决了候选区域计算冗余的问题，但是依然存在一些缺陷：首先，其训练是仍然是多阶段的；其次，SPPNet在微调网络时，只对其全连接层进行了微调，影响了特征的准确性。后续提出的Fast R-CNN检测器进一步地解决了这些问题。
【代表算法3】Fast-RCNN
2015年，Girshick等人在R-CNN和SPPNet的基础上又提出了FastR-CNN检测器。Fast-RCNN最大的特点在于实现了一种多任务学习方式，实现了在网络微调的同时，对目标分类和包围框回归的同步训练，且训练速度是R-CNN的9倍，检测速度是R-CNN的200倍。在VOC2007数据集上，Fast-RCNN将mAP由RCNN的58.5%提升至70.0%。Fast-RCNN成功地结合了R-CNN和SPPNet两者的优点，但还是需要事先使用外部算法来提取目标后选框，不能够实现端到端的处理。那能不能将候选区域检测这一操作同样也交给网络去做呢？后来的Faster R-CNN解决了这个问题。
【代表算法4】Faster-RCNN
同样是在2015年，在Fast-RCNN被提出后不久，Shaoqing Ren、Kaiming He以及Girshick等人又很快提出了Faster-RCNN算法。Faster-RCNN是第一个真正意义上的端到端的深度学习检测算法，也是第一个准实时（17帧/秒，640×480像素）的深度学习目标检测算法。Faster-RCNN在VOC07上在此将mAP由70.0%提升至78.8%。Faster-RCNN最大的创新点在于设计了候选区域生成网络（RegionProposal Network，RPN），并在其中设计了“多参考窗口”的机制，将Selective Search或Edge Boxes等外部Objectproposal检测算法融合到同一个深度网络中实现。从R-CNN到Fast RCNN再到Faster-RCNN，候选区域生成，特征提取，候选目标确认和包围框坐标回归逐渐被统一到同一个网络框架之中。检测精度由R-CNN的58.8%提升至Faster-RCNN的78.8%，检测速度也由每帧几十秒提升至准实时检测速度。
【代表算法5】Feature Pyramid Networks
在2017年，Tsung-Yi Lin、Piotr Dollar、Ross Girshick和Kaiming He等人又在Faster RCNN的基础上提出了Feature Pyramid Networks（FPN）检测算法。原有的目标检测算法通常都是只采用顶层特征做检测，原因是网络顶层特征的语义信息比较丰富。然而，虽顶层特征的语义信息丰富，但其中的目标位置信息却比较粗略，不利于目标包围框的准确定位；相反，虽然底层特征的语义信息比较少，但其中目标的位置信息却非常准确。因此，FPN的主要思想就是在网络前馈结束后，又将网络中最顶层的特征图像逐层地反馈并与前层的特征图进行融合，在此基础上，再从网络中不同深度的位置引出多个检测端口对其中的不同尺度的目标进行检测。由于网络在前馈过程中天然形成了金字塔形状的特征图，所以FPN对小目标以及尺度分布较大的目标具有天然的检测优势。FPN选择在比VOC规模和难度更大的MSCOCO数据集上进行了测试，取得了当时最佳的检测效果。
2、基于一体化卷积网络的检测算法
最近两年基于深度学习的目标检测算法的发展有两条主线，第一条是基于Object Proposal的检测主线，这条主线基本是按照R-CNN >> SPPNet >> Fast-RCNN >> Faster-RCNN >> FPN发展的；另一条是最近一年提出的一体化卷积网络的检测主线，这条主线基本是按照YOLO >> SSD >> Retina-Net发展的。在第二条主线中，人们抛弃了传统的粗检测+精检测的检测流程，经过单次检测即可直接得到最终的检测结果，因此有着更快的检测速度。
一体化卷积网络检测算法最早可以追溯到上世纪九十年代]，当时Yann Lecun等人将其命名为“空间位移神经网络（Space Displacement Neural Network）”。最近两年，一体化卷积网络检测算法受到了更多人的关注，在未来也会有更大的发展空间。下面将分别对这条主线下的YOLO、SSD、Retina-Net三种典型算法进行介绍。
【代表算法1】You Only Look Once (YOLO)
YOLO是第一个一体化卷积网络检测算法，由Joseph和Girshick等人在2015年提出。该算法最大的优势是速度快，彻底解决了基于深度学习速度上的痛点。该算法的增强版本在GPU上速度为45帧/秒，快速版本速度为155帧/秒（640×480像素）。YOLO是“You Only LookOnce”的缩写，从算法的名字就能够看出来作者彻底放弃了Proposal这一概念，直接将整张图像作为网络的输入，并仅通过一次前向传播直接得到目标包围框的位置和目标的类别。YOLO虽然有着非常快的检测速度，但其精度与Faster-RCNN相比有所下降，尤其是小目标检测效果较差，其定位的准确度也稍有不足。这主要是由于YOLO没有采用类似FasterRCNN中的“多参考窗口”的机制处理多尺度窗口问题。后来提出的SSD算法改善了这些问题。
【代表算法2】Single Shot MultiBox Detector (SSD)
SSD[28]算法由Wei Liu等人于2015年提出。SSD算法吸收了YOLO速度快和RPN定位精准的优点，采用了RPN中的多参考窗口技术，并进一步提出在多个分辨率的特征图上进行检测。SSD在VOC07上取得了接近Faster-RCNN的准确率（mAP=72%），同时保持了极快的检测速度（58帧/秒，640×480像素）。SSD与Faster-RCNN中不同之处有两点：首先，SSD是在多个尺度下的特征图上设置多个参考窗口进行后选框的检测，而Faster-RCNN仅仅是在一个尺度上进行处理；其次，Faster-RCNN是先利用提取目标后选框，然后再在后选框基础上利用检测网络和ROI Pooling进行后续判断，SSD则直接分别在多个尺度的特征图上进行多尺度检测和包围框坐标回归。此外，SSD在训练过程中，还采用了难样本挖掘操作来对图像中难样本进行聚焦。
【代表算法3】Retina-Net
一直以来，虽然基于一体化卷积网络的检测模型的检测速度都明显快于基于Object Proposals的检测算法，其检测精度却一直略逊于后者。Tsung-Yi Lin、 Priya Goyal、Ross Girshick以及Kaiming He等人对其背后的原因进行了研究，并与2017年提出了Retina-Net检测模型。Tsung-Yi Lin等人认为图像中极为不均衡的目标-背景数据分布才是导致一体化卷积网络检测精度较低的主要原因。Retina-Net对传统的交叉熵损失函数进行修正，提出了“聚焦损失函数（Focal Loss）”。通过降低网络训练过程中简单背景样本的学习权重，Retina-Net可以做到对难样本的“聚焦”和对网络学习能力的重新分配，从而使一体化卷积网络检测模型的检测速度和精度全面超越基于Object Proposals的检测模型。事实上，SSD中的难样本挖掘操作也与Focal Loss有着类似思想和效果。