查看“︁方向梯度直方图”︁的源代码

{{FeatureDetectionCompVisNavbox}}
'''方向梯度直方图'''（'''{{lang-en|Histogram of oriented gradient}}'''，簡稱'''HOG'''）是应用在[[计算机视觉]]和[[图像处理]]领域，用于{{Link-en|目标检测|Object detection}}的特征描述器。這項技術是用来計算局部圖像梯度的方向訊息的统计值。这种方法跟[[边缘方向直方图]]（edge orientation histograms）、[[尺度不变特征变换]]（scale-invariant feature transform descriptors）以及{{Link-en|形状上下文方法|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方法是特别适合于做图像中的行人检测的。<ref>{{cite web |url= http://www.acemedia.org/aceMedia/files/document/wp7/2005/cvpr05-inria.pdf |title= Histograms of Oriented Gradients for Human Detection, pg. 2 |deadurl= yes |archiveurl= https://web.archive.org/web/20110408220331/http://www.acemedia.org/aceMedia/files/document/wp7/2005/cvpr05-inria.pdf |archivedate= 2011-04-08 }}</ref>

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

: <math>[-1, 0, 1]\text{ and }[-1, 0, 1]^T.\,</math>

Dalal和Triggs也测试了其他更加复杂的卷积核，例如3x3的Sobel卷积核([[索貝爾算子]])和斜角卷积核，但是这些卷积核在行人检测的实验中表现的都很差。他们还用[[高斯模糊]]进行预处理，但是在实际运用中没有模糊反而会更好。 <ref>{{cite web |url= http://www.acemedia.org/aceMedia/files/document/wp7/2005/cvpr05-inria.pdf |title= Histograms of Oriented Gradients for Human Detection, pg. 4 |deadurl= yes |archiveurl= https://web.archive.org/web/20110408220331/http://www.acemedia.org/aceMedia/files/document/wp7/2005/cvpr05-inria.pdf |archivedate= 2011-04-08 }}</ref>

=== 直方图统计的方向单元划分（Orientation binning） ===
计算的第二步是建立分块直方图。每个块内的每个像素对方向直方图进行投票。每个块的形状可以是矩形或圆形的，方向直方图的方向取值可以是0-180度或者0-360度，这取决于梯度是否有正負。Dalal和Triggs发现在人的检测实验中，把方向分为9个通道效果最好。至于投票的权重，可以是梯度的幅度本身或者是它的函数。在实际测试中，梯度幅度本身通常产生最好的结果。其它可选的方案是采用幅度的平方或开方，或者幅度的裁剪版本。<ref>{{cite web |url=http://www.acemedia.org/aceMedia/files/document/wp7/2005/cvpr05-inria.pdf |title=Histograms of Oriented Gradients for Human Detection, pg. 5 |deadurl=yes |archiveurl=https://web.archive.org/web/20110408220331/http://www.acemedia.org/aceMedia/files/document/wp7/2005/cvpr05-inria.pdf |archivedate=2011-04-08 }}</ref>

=== 描述器區塊 ===
為了要解釋光照和對比的改變，梯度強度必須要局部地歸一化，這需要把方格集結成更大、在空間上連結的區塊。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看起来很像基于{{Link-en|形状上下文|Shape context}}的方法，但不同之处是：C-HOG的区间中包含的细胞单元有多个方向通道，而基于形状上下文的方法仅仅只用到了一个单一的边缘存在数。<ref name="#1">{{cite web |url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf |title=Histograms of Oriented Gradients for Human Detection, pg. 6 |accessdate=2015-03-19 |archive-date=2013-01-25 |archive-url=https://www.webcitation.org/6DvoEMDXQ?url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf |dead-url=no }}</ref>

=== 区间归一化 ===
Dalal和Triggs采用了四种不同的方法对区间进行归一化，并对结果进行了比较。引入 <math>v</math>表示一个还没有被归一化的向量，它包含了给定区间（block）的所有直方图信息。<math>\|v\|_k</math> 表示 <math>v</math> 的 ''k'' 阶范数，这里的 <math>k={1,2}</math>。用 <math>e</math> 表示一个很小的常数。这时，归一化因子可以表示如下：

: L2-norm: <math>f = {v \over \sqrt{\|v\|^2_2+e^2}}</math>

: L2-hys: L2-norm followed by clipping (limiting the maximum values of v to 0.2) and renormalizing, as in <ref>D. G. Lowe. [http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf Distinctive image features from scale-invariant keypoints.] {{Wayback|url=http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf |date=20150208033057 }} IJCV, 60(2):91–110, 2004.</ref>

: L1-norm: <math>f = {v \over (\|v\|_1+e)}</math>

: L1-sqrt: <math>f = \sqrt{v \over (\|v\|_1+e)}</math>

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

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

== 測試 ==

== 進一步的發展 ==

== 參見 ==
* [[角檢測]]
* [[特徵提取]]
* [[尺度不變特徵轉換]]

== 參考資料 ==
{{reflist}}

== 外部連結 ==
* http://www.cs.cmu.edu/~yke/pcasift/ {{Wayback|url=http://www.cs.cmu.edu/~yke/pcasift/ |date=20100701050050 }} - Code for PCA-SIFT Object Detection
* http://lear.inrialpes.fr/software/ {{Wayback|url=http://lear.inrialpes.fr/software/ |date=20090919120210 }} - Software Toolkit for HOG Object Detection (Research Team homepage)
* https://web.archive.org/web/20100502032344/http://www.navneetdalal.com/software - Software Toolkit for HOG Object Detection (Navneet Dalal homepage)
* https://web.archive.org/web/20100505083112/http://pascal.inrialpes.fr/data/human/ - INRIA Human Image Dataset
* http://cbcl.mit.edu/software-datasets/PedestrianData.html {{Wayback|url=http://cbcl.mit.edu/software-datasets/PedestrianData.html |date=20080428224624 }} - MIT Pedestrian Image Dataset

[[Category:計算機視覺]]