Intro
object detection 主要解决的问题是图像中目标的what and where。以2014年为分水岭，2014年主要为传统方法，2014年后主要是基于deep learning的方法。面临的主要问题是不同视角，不同光照条件，类内差异，小目标（目标的尺度和旋转变化），精确的目标定位，密集和遮挡条件下如何处理，以及如何加快速度等问题。目标检测延伸出如实例分割，人车检测，跟踪等多个领域。当下，目标检测领域已经完全进入了Anchor-free时代。
传统方法
1. VJ detectors
普遍的方法是滑动窗遍历所有可能的区域，Scale每个区域查看是否存在目标。Viola和Jones两位大牛发表了经典的《Rapid Object Detection using a Boosted Cascade of Simple Features》和《Robust Real-Time Face Detection》，在AdaBoost算法的基础上，使用Haar-like小波特征和积分图方法进行人脸检测，他俩不是最早使用提出小波特征的，但是他们设计了针对人脸检测更有效的特征，并对AdaBoost训练出的强分类器进行级联。
Haar-like特征：
基础的Haar-like特征在2002年的《A general framework for object detection》提出，它定义了四个基本特征结构，如下A，B，C，D所示，可以将它们理解成为一个窗口（与卷积核类似），这个窗口将在图像中做步长为1的滑动，最终遍历整个图像。在基本的四个haar特征基础上，文章《An extended set of Haar-like features for rapid object detection》对其做了扩展，将原来的4个扩展为14个。这些扩展特征主要增加了旋转性，能够提取到更丰富的边缘信息。
Haar-like特征提取过程就是利用下面定义的窗口在图像中滑动，滑动到一个位置的时候，将窗口覆盖住的区域中的白色位置对应的像素值的和减去黑色位置对应的像素值的和，得到的一个数值就是haar特征中一个维度。 当一次遍历结束后，窗口根据原图像的尺寸将在宽度或长度上成比例的放大，再重复之前遍历的步骤，直到放大到最后一个比例后结束。
Adaboost：
集成方法已经十分常见，其目标是结合多个估计器来解决一个共同的问题，这里不多赘述。Adaboost 首先选择一个决策树桩，然后当决策树桩不正确的时候，提高权重，当分类正确的时候，降低权重，这种迭代方式会让集成中每个新的分类器优先训练那些标记错误的情况，结果是模型以通过那些高权重的数据点作为目标处理进而得到调整，最后，这些树桩合并得到最终的分类器。
积分图：
积分图本质是一个加速器，它是Haar分类器能够实时检测人脸的保证。Haar-like分类器的训练和检测过程，无论是训练还是检测，每遇到一个图片样本，每遇到一个子窗口图像，我们都面临着如何计算当前子图像特征值的问题，一个Haar-like特征在一个窗口中怎样排列能够更好的体现人脸的特征，这是未知的，所以才要训练，而训练之前我们只能通过排列组合穷举所有这样的特征，仅以最基本四个特征为例，在一个24×24size的窗口中任意排列至少可以产生数以10万计的特征，对这些特征求值的计算量是非常大的。而积分图就是只遍历一次图像就可以求出图像中所有区域像素和的快速算法，大大的提高了图像特征值计算的效率。
积分图是一个二维矩形的查找表，与原始图像具有一样的尺寸。积分图的每一个元素是原始图像在对应位置左上角所有像素的和。这就使得在任意位置计算任意尺寸的矩形的像素和时，只需要进行四次查表：
2. HOG detector
HOG+SVM 经典中的经典
其属于传统的特征加分类器的目标检测方法。HOG算子Histogram of Oriented Gradients (HOG) 特征描述子，其和Sift，surf，ORB等相似均为局部描述算子。它通过计算和统计图像局部区域的梯度方向直方图来构成特征。与sift的比较可见 https://www.zhihu.com/question/45833619
颜色空间归一化—>梯度计算—>梯度方向直方图—>重叠块直方图归一化—>HOG特征
颜色归一化: 灰度与Gamma矫正（ 在图像照度不均匀的情况下，可以通过Gamma校正，将图像整体亮度提高或降低。在实际中可以采用两种不同的方式进行Gamma标准化，平方根、对数法。）
例如下面的平方根方法
梯度计算：经过颜色空间归一化后的图像，使用梯度算子求取其梯度及梯度方向，分别在水平和垂直方向进行计算。
梯度方向直方图：将图像划分成若干个cells（单元），8x8=64个像素为一个cell，相邻的cell之间不重叠。在每个cell内统计梯度方向直方图，将所有梯度方向划分为9个bin（即9维特征向量），作为直方图的横轴，角度范围所对应的梯度值累加值作为直方图纵轴，每个bin的角度范围如下。Z2对应着两部分，一部分是20∘20∘到40∘40∘，另一部分是200∘200∘到220∘220∘。
如图所示，可以分成9个bin分别对应一定的角度范围，这9个bins即为直方图的横轴，而这些角度范围内所对应的梯度的累加值为直方图的纵轴。最后我们可以得到每个cell的梯度方向直方图。
重叠块直方图归一化：一个block由若干个cell组成，通常以R-HOG为例，一个block含9个cell，以九字格的形式存在。相邻block之间都有重叠的cell，目的就是利用相邻信息，引入各个block之间的关系。
相关的参数设置可以是，每图片大小为512*512，一个cell大小是8*8=64个pixel，block的大小为64∗4=256个像素，有时图片大小不一定正好是其整数倍，所以还要调整图片的大小，缩放到其整数倍，以分离出整数个block。使用R-HOG，则共有(512/8−1)×(512/8−1)=63×63=3969个block。对于每个cell，其提取出的HOG特征向量有9个bins，即9维特征向量。则每个block有4×9=364×9=36维特征向量。那么，整幅图像共有36×3969=14288436×3969=142884维HOG特征向量。
到这里已经得到了整幅图像的HOG特征向量了，使用一系列样本提取得到的HOG特征向量送入SVM分类器训练，寻找最优超平面进行分类。在实际应用中，往往是从一幅图片中取出若干个小窗口进行特征提取，这样子可以得到有目标的窗口作为正样本，和没有目标的窗口作为负样本。将正负样本送入SVM训练，识别时也是取一个相同大小的滑动窗口，使用训练好的SVM来判断滑动窗口是否包含目标
3. DPM deformable part-based model可形变部件模型
传统方法的巅峰，DPM最初是HOG检测器的扩展，也是先计算梯度方向直方图，然后用SVM训练得到物体的梯度模型。有了这样的模板就可以直接用来分类了，简单理解就是模型和目标匹配。DPM随后被 R. Girshick做了一系列的改进。DPM的主要思想是分而治之，训练被看作是学习分解一个物体，结果可以看作是对目标不同部分检测的集合。它将目标对象建模成几个部件的组合。比如它将人类视为头部/身体/手/腿的组合。尽管看起来DPM非常简单，但是将这种intuition转化为数学模型（SVM，convex optimization，坐标下降法，梯度下降法）是十分tricky的。这其中涉及了很多的优化/训练方法。但是深度学习技术火了之后，DPM似乎消失了光芒。如果可视化深度学习每一层的特征，可以看到深度学习似乎也在学习这些部件（人的头/手/脚）的特征，但是深度学习训练起来比较简单。而DPM则加入较多的启发式规则，变得复杂。
For example, the problem of detecting a “car” can be considered as the detection of its window, body, and wheels.（aka star model）接着 R. Girshick 将其扩展到“混合模型”，以便在更显着的变化下处理现实世界中的物体。
典型的DPM检测器由一个root filter和多个part filter 组成，基于DPM的弱监督学习无需手动指定part filter(size，location)，而是将part filters的所有配置作为latent variables 潜在变量自动学习。R. Girshick进一步将此过程作为multi-instance learning的一个特例，并应用了其他一些重要技术，如“hard negative mining”，“BBX回归”和“context priming”等。提高检测精度。为了加快检测速度，Girshick开发了一种技术，用于将检测模型“编译”成更快的检测模型，实现级联结构，加速超过10倍而不牺牲任何精度。尽管今天的探测器在探测精度方面远远超过DPM，但其中许多仍深受其宝贵见解的影响，例如“hard negative mining”，“BBX回归”和“context priming”等。
HHOG+linear SVM中，我们根据图像计算出HOG pyramid，然后学习一个权重filter，然后计算这两个矩阵的内积，就会得到一个分数，我们再训练得出分数阀值就可以检测人类。但是在现实生活中，物体是有很多变化的，包括人的各种动作/车的各种形状/不同的视角和光照等等。而DPM则是一个更好的表示模型，上面这些变化对DPM影响不大。以检测一个人为例。它将人类表示成头/手/大腿/小腿等部件。每个部件的位置不是固定的，也就是说可以形变的。其中root filter是关注整个人的，part filter是关注身体几个部件的。而deformation model则是考虑不同形变带来的惩罚，也就是说你的手不能离身体太远，否则就会扣分。而且每个部件和主体的相对位置是比较稳定的，头部在上方，手部在中间，腿在下边。
DPM算法主要公式
混和模型：
因为视角不同，将会导致不同的形状（比如人的正面和侧面）。就好像盲人摸象一样。那么就需要多训练几个DPM，最后组成一个mixture model，这样才能准确识别到目标物体。
基本原理：
一个DPM模型包括一个root filter Fo和 n个部件模型 （Fi，Vi，di） ，其中Fi表示第i个部件的filter， Vi表示第i个部件跟root filter的相对位置， di表示第i个部件的形变参数（用来定义不同位置的形变代价。 那么DPM可以用一个得分函数来描述：
其中第一项是每个filter跟feature vector的点乘，用来判断像不像人。第二项是形变系数点乘形变特征，用来确定形变代价，b是偏置值，用于混合模型的多个component的比较。 那么对于一个假定的位置z，其对应的分数可以记为：
其中， β是未知参数，这是模型需要通过训练学习得到的。而 是已知量,包括HOG特征和形变特征，可以通过计算得到。
Part2会首先介绍DPM的训练方法，接着主要介绍各类网络的优缺点和tips。
Reference：
1. Object Detection in 20 Years: A Survey https://arxiv.org/abs/1905.050552.
2. https://www.cnblogs.com/ello/archive/2012/04/28/2475419.html
3. Computer Vision:Algorithms and Applications Richard Szeliski
4. https://zh.wikipedia.org/wiki/%E5%93%88%E5%B0%94%E7%89%B9%E5%BE%81
5. https://blog.csdn.net/hujingshuang/article/details/47337707
6 https://dataxujing.github.io/CNN-paper2/#/
7. https://blog.csdn.net/ttransposition/article/details/12966521
