方向梯度直方图

方向梯度直方图（英语：Histogram of oriented gradient，简称HOG）是应用在计算机视觉和图像处理领域，用于目标检测（英语：Object detection）的特征描述器。这项技术是用来计算局部图像梯度的方向讯息的统计值。这种方法跟边缘方向直方图（edge orientation histograms）、尺度不变特征变换（scale-invariant feature transform descriptors）以及形状上下文方法（英语：Shape context）（ shape contexts）有很多相似之处，但与它们的不同点是：HOG描述器是在一个网格密集的大小统一的细胞单元（dense grid of uniformly spaced cells）上计算，而且为了提高性能，还采用了重叠的局部对比度归一化（overlapping local contrast normalization）技术。

其作者Navneet Dalal和Bill Triggs是法国国家计算机技术和控制研究所（INRIA）的研究员，他们在2005年的CVPR上首先发表了描述方向梯度直方图的论文。在这篇论文里，他们主要是将这种方法应用在静态图像中的行人检测上，但在后来，他们也将其应用在影片中的行人检测，以及静态图像中的车辆和常见动物的检测。

HOG描述器最重要的思想是：在一副图像中，局部目标的表象和形状（appearance and shape）能够被梯度或边缘的方向密度分布很好地描述。具体的实现方法是：首先将图像分成小的连通区域，我们把它叫细胞单元。然后采集细胞单元中各像素点的梯度的或边缘的方向直方图。最后把这些直方图组合起来就可以构成特征描述器。为了提高性能，我们还可以把这些局部直方图在图像的更大的范围内（我们把它叫区间或block）进行对比度归一化（contrast-normalized），所采用的方法是：先计算各直方图在这个区间（block）中的密度，然后根据这个密度对区间中的各个细胞单元做归一化。通过这个归一化后，能对光照变化和阴影获得更好的效果。

与其他的特征描述方法相比，HOG描述器有很多优点。首先，由于HOG方法是在图像的局部细胞单元上操作，所以它对图像几何的（geometric）和光学的（photometric）形变都能保持很好的不变性，这两种形变只会出现在更大的空间领域上。其次，作者通过实验发现，在粗的空域抽样（coarse spatial sampling）、精细的方向抽样（fine orientation sampling）以及较强的局部光学归一化（strong local photometric normalization）等条件下，只要行人大体上能够保持直立的姿势，就容许行人有一些细微的肢体动作，这些细微的动作可以被忽略而不影响检测效果。综上所述，HOG方法是特别适合于做图像中的行人检测的。

许多特征检测的第一步都是要进行图像的预处理，如归一化颜色值和gamma值，但如Dalal和Triggs指出的那样，HOG描述子可以省略这个步骤，因为它其中的描述子归一化处理能达到同样的效果。图像预处理对最终效果的贡献微薄。所以第一步就是计算梯度值。最通常用的方法就是简单的应用一个一维的离散的梯度模版分别应用在水平和垂直方向上去。可以使用如下的卷积核进行卷积：

Dalal和Triggs也测试了其他更加复杂的卷积核，例如3x3的Sobel卷积核(索贝尔算子)和斜角卷积核，但是这些卷积核在行人检测的实验中表现的都很差。他们还用高斯模糊进行预处理，但是在实际运用中没有模糊反而会更好。

计算的第二步是建立分块直方图。每个块内的每个像素对方向直方图进行投票。每个块的形状可以是矩形或圆形的，方向直方图的方向取值可以是0-180度或者0-360度，这取决于梯度是否有正负。Dalal和Triggs发现在人的检测实验中，把方向分为9个通道效果最好。至于投票的权重，可以是梯度的幅度本身或者是它的函数。在实际测试中，梯度幅度本身通常产生最好的结果。其它可选的方案是采用幅度的平方或开方，或者幅度的裁剪版本。

为了要解释光照和对比的改变，梯度强度必须要局部地归一化，这需要把方格集结成更大、在空间上连结的区块。HOG描述器是归一化方格直方图的元件的向量，这直方图由所有区块的区域而来。这些区块通常会重叠，意味着每个方格不只一次影响了最后的描述器。两个主要的区块几何存在着：一个是矩形的R-HOG区块，另一个是圆形的C-HOG区块。R-HOG区块一般来说是多个方格子组成的，由三个参数表示：每个区块有多少方格、每个方格有几个像素、以及每个方格直方图有多少频道。在Dalal和Triggs的人检测实验中，发现最优的参数为6x6像素大小的单元，每个单元块为3x3像素，同时直方图是9通道。作者还发现，在对直方图做处理之前，给每个区间加一个高斯空域窗口是非常必要的，因为这样可以降低边缘的周围像素点的权重。R-HOG跟SIFT描述器看起来很相似，但他们的不同之处是：R-HOG是在单一尺度下、密集的网格内、没有对方向排序的情况下被计算出来；而SIFT描述器是在多尺度下、稀疏的图像关键点上、对方向排序的情况下被计算出来。补充一点，R-HOG是各区间被组合起来用于对空域信息进行编码，而SIFT的各描述器是单独使用的。

C-HOG区间（blocks）有两种不同的形式，它们的区别在于：一个的中心细胞是完整的，一个的中心细胞是被分割的。作者发现C-HOG的这两种形式都能取得相同的效果。C-HOG区间可以用四个参数来表征：角度盒子的个数、半径盒子个数、中心盒子的半径、半径的伸展因子。通过实验，对于行人检测，最佳的参数设置为：4个角度盒子、2个半径盒子、中心盒子半径为4个像素、伸展因子为2。前面提到过，对于R-HOG，中间加一个高斯空域窗口是非常有必要的，但对于C-HOG，这显得没有必要。C-HOG看起来很像基于形状上下文（英语：Shape context）的方法，但不同之处是：C-HOG的区间中包含的细胞单元有多个方向通道，而基于形状上下文的方法仅仅只用到了一个单一的边缘存在数。

Dalal和Triggs采用了四种不同的方法对区间进行归一化，并对结果进行了比较。引入 ${\displaystyle v}$ 阶范数，这里的 ${\displaystyle k=1,2}$。用 ${\displaystyle e}$ 表示一个很小的常数。这时，归一化因子可以表示如下：

还有第四种归一化方式：L2-Hys，它可以通过先进行L2-norm，对结果进行截短（clipping），然后再重新归一化得到。作者发现：采用L2-Hys, L2-norm, 和 L1-sqrt方式所取得的效果是一样的，L1-norm稍微表现出一点点不可靠性。但是对于没有被归一化的数据来说，这四种方法都表现出来显著的改进。

最后一步就是把提取的HOG特征输入到SVM分类器中，寻找一个最优超平面作为决策函数。作者采用的方法是：使用免费的SVMLight软件包加上HOG分类器来寻找测试图像中的行人。