方向梯度直方圖

方向梯度直方圖（英語：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方法是特別適合於做圖像中的行人檢測的。^[1]

算法實現

梯度計算

許多特徵檢測的第一步都是要進行圖像的預處理，如歸一化顏色值和gamma值，但如Dalal和Triggs指出的那樣，HOG描述子可以省略這個步驟，因為它其中的描述子歸一化處理能達到同樣的效果。圖像預處理對最終效果的貢獻微薄。所以第一步就是計算梯度值。最通常用的方法就是簡單的應用一個一維的離散的梯度模版分別應用在水平和垂直方向上去。可以使用如下的卷積核進行卷積：

[-1,0,1]{\text{ and }}[-1,0,1]^{T}.\,

Dalal和Triggs也測試了其他更加複雜的卷積核，例如3x3的Sobel卷積核(索貝爾算子)和斜角卷積核，但是這些卷積核在行人檢測的實驗中表現的都很差。他們還用高斯模糊進行預處理，但是在實際運用中沒有模糊反而會更好。 ^[2]

直方圖統計的方向單元劃分（Orientation binning）

計算的第二步是建立分塊直方圖。每個塊內的每個像素對方向直方圖進行投票。每個塊的形狀可以是矩形或圓形的，方向直方圖的方向取值可以是0-180度或者0-360度，這取決於梯度是否有正負。Dalal和Triggs發現在人的檢測實驗中，把方向分為9個通道效果最好。至於投票的權重，可以是梯度的幅度本身或者是它的函數。在實際測試中，梯度幅度本身通常產生最好的結果。其它可選的方案是採用幅度的平方或開方，或者幅度的裁剪版本。^[3]

描述器區塊

為了要解釋光照和對比的改變，梯度強度必須要局部地歸一化，這需要把方格集結成更大、在空間上連結的區塊。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的區間中包含的細胞單元有多個方向通道，而基於形狀上下文的方法僅僅只用到了一個單一的邊緣存在數。^[4]

區間歸一化

Dalal和Triggs採用了四種不同的方法對區間進行歸一化，並對結果進行了比較。引入 $v$ 表示一個還沒有被歸一化的向量，它包含了給定區間（block）的所有直方圖信息。 $\|v\|_{k}$ 表示 $v$ 的 k 階範數，這裡的 $k={1,2}$ 。用 $e$ 表示一個很小的常數。這時，歸一化因子可以表示如下：

L2-norm:

f={v \over {\sqrt {\|v\|_{2}^{2}+e^{2}}}}

L2-hys: L2-norm followed by clipping (limiting the maximum values of v to 0.2) and renormalizing, as in ^[5]

L1-norm:

f={v \over (\|v\|_{1}+e)}

L1-sqrt:

f={\sqrt {v \over (\|v\|_{1}+e)}}

還有第四種歸一化方式：L2-Hys，它可以通過先進行L2-norm，對結果進行截短（clipping），然後再重新歸一化得到。作者發現：採用L2-Hys, L2-norm, 和 L1-sqrt方式所取得的效果是一樣的，L1-norm稍微表現出一點點不可靠性。但是對於沒有被歸一化的數據來說，這四種方法都表現出來顯著的改進。^[4]

SVM分類器

最後一步就是把提取的HOG特徵輸入到SVM分類器中，尋找一個最優超平面作為決策函數。作者採用的方法是：使用免費的SVMLight軟體包加上HOG分類器來尋找測試圖像中的行人。

測試

進一步的發展

參見

參考資料

^ Histograms of Oriented Gradients for Human Detection, pg. 2 (PDF). （原始內容 (PDF)存檔於2011-04-08）.
^ Histograms of Oriented Gradients for Human Detection, pg. 4 (PDF). （原始內容 (PDF)存檔於2011-04-08）.
^ Histograms of Oriented Gradients for Human Detection, pg. 5 (PDF). （原始內容 (PDF)存檔於2011-04-08）.
^ ^4.0 ^4.1 Histograms of Oriented Gradients for Human Detection, pg. 6 (PDF). [2015-03-19]. （原始內容存檔 (PDF)於2013-01-25）.
^ D. G. Lowe. Distinctive image features from scale-invariant keypoints. （頁面存檔備份，存於網際網路檔案館） IJCV, 60(2):91–110, 2004.

外部連結

http://www.cs.cmu.edu/~yke/pcasift/ （頁面存檔備份，存於網際網路檔案館） - Code for PCA-SIFT Object Detection
http://lear.inrialpes.fr/software/ （頁面存檔備份，存於網際網路檔案館） - 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 （頁面存檔備份，存於網際網路檔案館） - MIT Pedestrian Image Dataset

[1] Histograms of Oriented Gradients for Human Detection, pg. 2 (PDF). （原始內容 (PDF)存檔於2011-04-08）.

[2] Histograms of Oriented Gradients for Human Detection, pg. 4 (PDF). （原始內容 (PDF)存檔於2011-04-08）.

[3] Histograms of Oriented Gradients for Human Detection, pg. 5 (PDF). （原始內容 (PDF)存檔於2011-04-08）.

[#1-4] 4.0 ^4.1 Histograms of Oriented Gradients for Human Detection, pg. 6 (PDF). [2015-03-19]. （原始內容存檔 (PDF)於2013-01-25）.

[5] D. G. Lowe. Distinctive image features from scale-invariant keypoints. （頁面存檔備份，存於網際網路檔案館） IJCV, 60(2):91–110, 2004.

[1]

[2]

[3]

[4]

[5]