HOG特征（Histogram of Gradient）学习总结

最近在做的项目有用到HOG+SVM这一方面的知识，参考相关论文和网上一些博文在此对HOG特征进行下总结。

参考资料：
HOG的经典论文：Dalal N, Triggs B. Histograms of oriented gradients for human detection[C]//Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on. IEEE, 2005, 1: 886-893.(2016:Google Citation: 14046)
下载链接：https://hal.inria.fr/file/index/docid/548512/filename/hog_cvpr2005.pdf
较为详细的博士论文：Dalal N. Finding people in images and videos[D]. Institut National Polytechnique de Grenoble-INPG, 2006.(Google Citation: 337)
下载链接：https://tel.archives-ouvertes.fr/tel-00390303/document

其他论文：
P. Felzenszwalb, D. McAllester, D. Ramaman. A Discriminatively Trained, Multiscale, Deformable Part Model. Proceedings of the IEEE CVPR 2008.

P. Felzenszwalb, R. Girshick, D. McAllester, D. Ramanan. Object Detection with Discriminatively Trained Part Based Models. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, No. 9, September 2010

采用级联结构对HOG检测进行加速：Zhu Q, Yeh M C, Cheng K T, et al. Fast human detection using a cascade of histograms of oriented gradients[C]//Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on. IEEE, 2006, 2: 1491-1498.(Google Citation: 1270)

关于HOG特征的三线性插值论文:
[Wang, 2009] X. Wang, X. Han, and S. Yan. A HOG-LBP human de­tec­tor with par­tial oc­clu­sion han­dling [A]. In Proc. of ICCV[C], 2009.(Google Citation: 965)
[Pang, 2011] Y. Pang, Y. Yuan, X. Li, et al. Efficient HOG human detection [J]. Signal Processing, 2011, 91: 773-781.(Google Citation: 105)

比较好的博文：
http://blog.sina.com.cn/s/blog_60e6e3d50101bkpn.html
http://blog.csdn.net/icvpr/article/details/8454527
对经典文章的翻译：http://blog.csdn.net/masibuaa/article/details/14056807
从理论到OpenCV实现：http://blog.csdn.net/zhazhiqiang/article/details/21047207
重新解读HoG 和PHoG (pyramid HoG)：http://blog.csdn.net/cheng1988shu/article/details/8332795

行人数据集：INRIA Person dataset
Download：http://pascal.inrialpes.fr/data/human/

概述

CVPR2005这篇文章中，HOG是用来做行人检测的。作者研究了行人检测的特征集问题，局部归一化的HOG描述子相比于现存的特征集(包括小波)有更好的表现。相比于边缘方向直方图(Edge Orientation Histograms)、SIFT描述子、形状上下文(Shape Contexts)，HOG是在网格密集的大小统一的细胞单元(dense grid of uniformly spaced cells)上进行计算，而且为了提高性能，还采用了重叠的局部对比度归一化(overlapping local contrast normalizations)。作者用行人检测(行人是大部分可见的并且基本上是直立的)进行测试，为了保证速度和简洁性，使用线性SVM作为分类器。

作者在文中提到他们的非正式实验表明，即使截止到05年最好的基于特征点的方法，在行人检测方面比本论文的方法的错检率也要高上至少1-2个数量级，主要是因为这些基于特征点的检测器不能可靠地检测行人结构。HOG有个优点，提取的边缘和梯度特征能很好的抓住局部形状的特点，且因是对图像做了Gamma校正和采用cell方式进行梯度方向量化，在局部进行提取，所以对几何和光学变化都有很好的不变性，变换或旋转对于足够小的区域影响很小。对于行人检测，在粗糙空域采样(coarse spatial sampling)、精细方向采样(fine orientation sampling)和强局部灰度归一化(strong local photometric normalization)这些条件下，只要行人大体上能够保持直立的姿势，就容许有一些细微的肢体动作，这些细微的动作可以被忽略而不影响检测效果。综上，HOG特征很适合于做图像中的人体检测。

1 Overview of the Method

HOG方法是基于对稠密网格中归一化的局部方向梯度直方图的计算。此方法的基本观点是：局部目标的外表和形状可以被局部梯度或边缘方向的分布很好的描述，即使我们不知道对应的梯度和边缘的位置。在实际操作中，将图像分为小的元胞(cells)，在每个元胞内累加计算出一维的梯度方向(或边缘方向)直方图。为了对光照和阴影有更好的不变性，需要对直方图进行对比度归一化，这可以通过将元胞组成更大的块(blocks)并归一化块内的所有元胞来实现。归一化的块描述符就叫作HOG描述子。将检测窗口中的所有块的HOG描述子组合起来就形成了最终的特征向量，然后使用SVM分类器进行行人检测。如上图描述了特征提取和目标检测流程。检测窗口划分为重叠的块，对这些块计算HOG描述子，形成的特征向量放到线性SVM中进行目标/非目标的二分类。检测窗口在整个图像的所有位置和尺度上进行扫描，并对输出的金字塔进行非极大值抑制来检测目标。

2 Gamma/Colour Normalization

标准化gamma空间和颜色空间。为了减少光照因素的影响，首先需要将整个图像进行规范化（归一化）。在图像的纹理强度中，局部的表层曝光贡献的比重较大，所以，这种压缩处理能够有效地降低图像局部的阴影和光照变化。

f(I)=Iγ

gamma<1在高灰度值区域内，动态范围变小，图像对比度降低，图像整体灰度值变大，显得亮一些；gamma>1在低灰度值区域内，动态范围变小，图像对比度降低，图像整体灰度值变小，变得暗淡。

作者在他的博士论文里有提到，对于涉及大量的类内颜色变化，如猫，狗和马等动物，没标准化的RGB图效果更好，而牛，羊的图做gamma颜色校正后效果更好。是否用gamma校正得分析具体的训练集情况。

3 Image Smoothing

对于灰度图像，一般为了去除噪点，所以会先利用离散高斯平滑模板进行平滑：高斯函数在不同平滑的尺度下进行对灰度图像进行平滑操作。Dalal等实验表明moving from σ=0 to σ=2 reduces the recall rate from 89% to 80% at 10−4 FPPW，即不做高斯平滑人体检测效果最佳，使得漏检率缩小了约一倍。不做平滑操作，可能原因：HOG特征是基于边缘的，平滑会降低边缘信息的对比度，从而减少图像中的有用信息。

4 Gradient Computation

式中 Gx(x,y),Gy(x,y) 分别表示输入图像在像素点(x,y)处的水平方向梯度和垂直方向梯度。则 G(x,y),α(x,y) 分别为像素点(x,y)的梯度幅值和梯度方向。Dalal等人利用许多一阶微分模板进行求梯度近似值，但在实验中表明模板[-1,0,1]效果最好。

首先用[-1,0,1]梯度算子对原图像做卷积运算，得到水平方向（以向右为正方向）的梯度分量，然后用[1,0,-1]T梯度算子对原图像做卷积运算，得到竖直方向（以向上为正方向）的梯度分量。然后再用以上公式计算该像素点的梯度大小和方向。

%matlab code
hx = [-1,0,1];hy = -hx';
gradscalx = imfilter(double(img),hx);
gradscaly = imfilter(double(img),hy);

5 Spatial / Orientation Binning

这一步骤的目的是为局部图像区域提供一个指示函数量化梯度方向的同时能够保持对图像中人体对象的姿势和外观的弱敏感性。
将图像分成若干个“单元格cell”，例如每个cell为8 ∗ 8的像素大小。假设采用9个bin的直方图来统计这8 ∗ 8个像素的梯度信息，即将cell的梯度方向0～180度（或0～360度，考虑了正负，signed）分成9个方向块。如下图所示：如果这个像素的梯度方向是20-40度，直方图第2个bin即的计数就加1，这样，对cell内每个像素用梯度方向在直方图中进行加权投影，将其映射到对应的角度范围块内，就可以得到这个cell的梯度方向直方图了，就是该cell对应的9维特征向量（因为有9个bin）。这边的加权投影所用的权值为当前点的梯度幅值。例如说：某个像素的梯度方向是在，其梯度幅值是4，那么直方图第2个bin的计数就不是加1了，而是加4。这样就得到关于梯度方向的一个加权直方图。

采用梯度幅值量级本身得到的检测效果最佳，而使用二值的边缘权值表示会严重降低效果。采用梯度幅值作为权重，可以使那些比较明显的边缘的方向信息对特征表达影响增大，这样比较合理，因为HOG特征主要就是依靠这些边缘纹理。

根据Dalal等人的实验，在行人目标检测中，在无符号方向角度范围并将其平均分成9份（bins）能取得最好的效果，当bin的数目继续增大效果改变不明显，故一般在人体目标检测中使用bin数目为9范围0~180度的度量方式。

6 Tri-linear interpolation

在计算每个cell的梯度直方图时，可以用三线性插值来提高计算速率。对于每个cell里的点，我们认为都是一个三维向量 (x,y,θ) ,如下图所示某一待处理像素点它位于block中的C0单元中， 利用该点与四个cell中的中心像素点 （图中4个圆点， (x1,y1),...,(x4,y4) ） 的距离计算权值， 将待处理像素点的梯度幅值分别加权累加到C0、C1、 C2、 C3中相应的直方图上，与θ相邻的两个bin上（θ1，θ2）。


参见上图，以(x,y,θ)对cell0的梯度直方图即h(x1,y1,θ1)的加权投影为例，三线性插值公式如下：

这样不断累加更新得到最终的 h(x1,y1,θ1),...,h(x4,y4,θ4) ，就是我们所要4个cell的梯度直方图。

7 Normalization and Descriptor Blocks

由于局部光照的变化以及前景-背景对比度的变化，使得梯度强度的变化范围非常大。这就需要对梯度强度做归一化。归一化能够进一步地对光照、阴影和边缘进行压缩，使特征向量空间对光照，阴影和边缘变化具有鲁棒性。本文的做法是：把各个细胞单元组合成大的、空间上连通的区域（blocks）。这样，一个block内所有cell的特征向量串联起来便得到该block的HOG特征。这些区间是互有重叠的，这就意味着：每一个单元格的特征会以不同的结果多次出现在最后的特征向量中。归一化之后的块描述符（向量）就称之为HOG描述符。

通常使用的HOG结构大致有三种：矩形HOG（简称为R-HOG），圆形HOG和中心环绕HOG。它们的单位都是Block（即块）。Dalal的试验证明矩形HOG和圆形HOG的检测效果基本一致，而环绕形HOG效果相对差一些。

如上图，一般一个块（Block）都由若干单元（Cell）组成，一个单元都有如干个像素点组成。
假设行人检测的参数设置是：2×2 cell/block、8×8像素/cell、9个直方图通道（9 bins），一个块的特征向量长度为：2×2×9。

对block块内的HOG特征向量进行归一化。一般采用的归一化函数有以下四种：

在人体检测系统中进行HOG计算时一般使用L2-norm，Dalal的文章也验证了对于人体检测系统使用L2-norm的时候效果最好。

8 Classifier

计算一个样本的HOG特征维度，例如：
detection window:64×128; 8×8 pixels/cell; bin=9;2×2cells/block; blockstride=1cell;
block number:15×7=105;Length of HOG feature vector: 2×2×9×15×7=3780
最后就是把这么一个3780维的特征向量输入给SVM做训练分类。

9 Visualizing Object Detection Features

关于HOG特征可视化的程序如下：

基于OpenCV的C++程序，效果图如下，通过该程序可以帮助理解HOG特征。
下载链接：http://download.csdn.net/detail/u011285477/9472067

用MATLAB实现的HOG特征可视化代码，视觉效果不错。

下载链接：http://web.mit.edu/vondrick/ihog/index.html#code。
相关资料：Vondrick C, Khosla A, Malisiewicz T, et al. Hoggles: Visualizing object detection features[C]//Proceedings of the IEEE International Conference on Computer Vision. 2013: 1-8.(Google Citation: 98)

10 Multi-Scale Object Localisation

上图右上角是对SVM分类结果的置信度做个映射得到检测评分。检测过程就是用固定大小的窗口对多个尺度的图像进行滑窗检测，将多个尺度计算得到的矩形框都还原成原图尺寸，再进行非极大值抑制(NMS,Non-maximum Suppression)处理。在物体检测非极大值抑制应用十分广泛，主要目的是为了消除多余的框，找到最佳的检测框的位置，大致思想如下图所示。

11 Conclusions

HOG的优点：
- 核心思想是所检测的局部物体外形能够被梯度或边缘方向的分布所描述，HOG能较好地捕捉局部形状信息，对几何和光学变化都有很好的不变性；
- HOG是在密集采样的图像块中求取的，在计算得到的HOG特征向量中隐含了该块与检测窗口之间的空间位置关系。

矩形HOG和SIFT有些相似的地方，关于SIFT具体看这篇博文SIFT特征提取分析

HOG的缺陷：
- 很难处理遮挡问题，人体姿势动作幅度过大或物体方向改变也不易检测（这个问题后来在DPM中采用可变形部件模型的方法得到了改善）；
- 跟SIFT相比，HOG没有选取主方向，也没有旋转梯度方向直方图，因而本身不具有旋转不变性（较大的方向变化），其旋转不变性是通过采用不同旋转方向的训练样本来实现的；
- 跟SIFT相比，HOG本身不具有尺度不变性，其尺度不变性是通过缩放检测窗口图像的大小来实现的；
- 此外，由于梯度的性质，HOG对噪点相当敏感，在实际应用中，在Block和Cell划分之后，对于得到各个像区域中，有时候还会做一次高斯平滑去除噪点。