HOG（描述子）

參考博客
HOG+SVM在行人檢測中獲得巨大成功
HOG的主要思想是圖片的局部特征可以被梯度或邊緣的方向密度分布很好地表達。
方向梯度直方圖提取流程：
0、預處理：灰度化（將圖像看做一個x,y,z（灰度）的三維圖像），采用Gamma校正法對輸入圖像進行顏色空間的標準化（歸一化）；目的是調(diào)節(jié)圖像的對比度，降低圖像局部的陰影和光照變化所造成的影響，同時可以抑制噪音的干擾；
1、把窗口劃分成若干個塊(blocks)
2、將每個塊劃分為若干個元胞(cells)
3、統(tǒng)計每個元胞內(nèi)部的梯度方向直方圖，并以此為該元胞的特征向量
4、把每個元胞的特征向量相連作為一個塊的特征向量
5、將每個塊的特征向量相連最為該窗口的特征向量

注：以上步驟1、2為粗的空域抽樣，步驟4、5為精細的方向抽樣。4、5步驟特征向量的組合并不是簡單的相連，為了提高性能采用較強的局部光學歸一化，具體方法是：先計算各直方圖在這個區(qū)間（block）中的密度，然后根據(jù)這個密度對區(qū)間中的各個細胞單元做歸一化。通過這個歸一化后，能對光照變化和陰影獲得更好的效果。

gamma校正的原因：在圖像的紋理強度中局部的表層曝光貢獻的比重較大，所以，這種壓縮處理能夠有效地降低圖像局部的陰影和光照變化。因為顏色信息作用不大，通常先轉化為灰度圖；

優(yōu)點
由于HOG是在圖像的局部方格單元上操作，所以它對圖像幾何的和光學的形變都能保持很好的不變性，這兩種形變只會出現(xiàn)在更大的空間領域上。其次，在粗的空域抽樣、精細的方向抽樣以及較強的局部光學歸一化等條件下，只要行人大體上能夠保持直立的姿勢，可以容許行人有一些細微的肢體動作，這些細微的動作可以被忽略而不影響檢測效果。因此HOG特征是特別適合于做圖像中的人體檢測的。
下面是HOG結合svm做行人檢測的流程圖：
1、輸入圖片
2、進行歸一化和Gamma校正
3、計算圖像的梯度圖
4、統(tǒng)計每個cell內(nèi)部的梯度直方圖
5、組合每個block內(nèi)的所有cell的特征描述子
6、連接所有block的特征描述子，組成當前檢測窗口的特征描述子
7、收集所有檢測窗口的特征描述子
8、利用線性SVM進行分類
9、輸出有人/無人
blocks有兩個主要的幾何形狀——矩形區(qū)間（R-HOG）和環(huán)形區(qū)間（C-HOG）。R-HOG區(qū)間大體上是一些方形的格子，它可以有三個參數(shù)來表征：每個區(qū)間中細胞單元的數(shù)目、每個細胞單元中像素點的數(shù)目、每個細胞的直方圖通道數(shù)目。
例如：行人檢測的最佳參數(shù)設置是：3×3細胞/區(qū)間、6×6像素/細胞、9個直方圖通道。則一塊的特征數(shù)為：339；

總結一個圖像的HOG特征維度：
Dalal提出的Hog特征提取的過程：把樣本圖像分割為若干個像素的單元（cell），把梯度方向平均劃分為9個區(qū)間（bin），在每個單元里面對所有像素的梯度方向在各個方向區(qū)間進行直方圖統(tǒng)計，得到一個9維的特征向量，每相鄰的4個單元構成一個塊（block），把一個塊內(nèi)的特征向量聯(lián)起來得到36維的特征向量，用塊對樣本圖像進行掃描，掃描步長為一個單元。最后將所有塊的特征串聯(lián)起來，就得到了人體的特征。例如，對于64*128的圖像而言，每16*16的像素組成一個cell，每2*2個cell組成一個塊，因為每個cell有9個特征，所以每個塊內(nèi)有4*9=36個特征，以8個像素為步長，那么，水平方向將有7個掃描窗口，垂直方向將有15個掃描窗口。也就是說，64*128的圖片，總共有36*7*15=3780個特征。

DPM（描述子）

參考博客
DPM對HOG做了改進，具體如下：
1、DPM改進后的HOG特征取消了原HOG中的塊(Block)，只保留了單元（Cell）
2、歸一化時，是直接將當前單元與其周圍的4個單元（Cell）所組成的一個區(qū)域歸一化，所以效果和原HOG特征非常類似。
3、計算梯度方向時可以計算有符號（0-360°）或無符號（0-180°）的梯度方向，有些目標適合使用有符號的梯度方向，而有些目標適合使用無符號的梯度，作為一種通用的目標檢測方法，DPM與原HOG不同，采用了有符號梯度和無符號梯度相結合的策略。
4、對于無符號梯度：為了降低特征向量的維度，F(xiàn)elzenszwalb采用了一種近似的PCA降維效果。具體來說，將36維向量看成6*6的矩陣，對每一行，每一列求和得到13維特征，基本上能達到HOG特征36維的檢測效果。
5、對于有符號梯度：對18個有符號梯度方向求和得到18維向量
6、綜上所述，DPM特征為31維的特征向量（13維+8維）

LBP(Local Binary Pattern)（描述子）

參考博客
LBP是一個用來描述圖像矩紋理特征的特征描述子，它最明顯的有點就是具有旋轉不變性和灰度不變性。
原始局部二值模式特征：最原始的LBP是定義在一個3*3的窗口內(nèi)的，其生成過程為：以9個像素中的中心像素為閾值，其周圍的8個像素中比它大的設置為1，比它小的設置為0，并以此8位二進制數(shù)表示LBP特征，LBP特征的最終表示要轉化為10進制數(shù)。
改進后的LBP

1、圓形LBP：為了改進原始LBP的主要缺陷——窗口大小不能隨這不同尺寸和頻率的紋理特征動態(tài)變化，Ojala等人將3*3的鄰域擴展到半徑為R的任意領域，從而產(chǎn)生半徑為R的圓形領域內(nèi)基于P個采樣點的LBP算子。
2、LBP旋轉不變模式：原始的LBP定義保證了LBP算子的灰度不變性但并不能保證其旋轉不變性，為克服此缺陷，Maenpaa等人通過不斷旋轉圓形鄰域并在不同方向的領域計算原始LBP，取所有LBP的最小值來實現(xiàn)LBP算子的旋轉不變性
3、LBP的等價模式：如果用原始LBP的定義，那么在p個采樣點的LBP算子中，產(chǎn)生的LBP將有 $2^p$ 種，這不僅僅會降低紋理識別、分類的效果(可能是由于對高頻噪聲過擬合造成的)，而且對信息存取也是不利的，將LBP算子用于紋理分類或人臉識別時，常采用LBP模式的統(tǒng)計直方圖來表達圖像的信息，而較多的模式種類將使得數(shù)據(jù)量過大，且直方圖過于稀疏。
為了解決以上問題，Ojala提出了一種等價模式(Uniform Pattern)來對LBP算子進行降維，他們認為，絕大多數(shù)LBP最多只包含兩次0 1或1 0跳變，他們把這些多數(shù)模式稱為等價模式：當某個LBP所對應的循環(huán)二進制數(shù)從0到1或從1到0最多有兩次跳變時，該LBP所對應的二進制就稱為一個等價模式類。不是等價模式的其他模式稱為混合模式
通過這樣的改進，二進制模式的種類大大減少，而不會丟失任何信息。模式數(shù)量由原來的2P種減少為 P ( P-1)+2種，其中P表示鄰域集內(nèi)的采樣點數(shù)，這使得特征向量的維數(shù)更少，并且可以減少高頻噪聲帶來的影響。

LBP用于圖像處理的原理分析
LBP特征提取完畢后會每個像素點都會得到了個LBP編碼，即一幅圖片的原始LBP特征圖譜依然是一幅圖片，如果直接用其判斷兩幅圖的相似程度的話，可能會因為圖像位置沒有對準而造成去真錯誤，所以LBP的應用中，如：紋理分類，人臉分析等，一般都采用LBP特征圖譜的統(tǒng)計直方圖作為特征向量進行分類。
具體的講，研究發(fā)現(xiàn)可以將一幅圖片分為若干的blocks，然后在一個block內(nèi)統(tǒng)計LBP特征，形成該block的LBP直方圖作為該block的特征向量，整個圖片用來分類的特征向量就是這些blocks特征向量歸一化后連接的結果。之后利用相似性度量算法即可判斷兩幅圖片的相似性。

下面的這個步驟不一定是對的

首先將檢測窗口劃分為16×16的小區(qū)域（cell）；
對于每個cell中的一個像素，將相鄰的8個像素的灰度值與其進行比較，若周圍像素值大于中心像素值，則該像素點的位置被標記為1，否則為0。這樣，3*3鄰域內(nèi)的8個點經(jīng)比較可產(chǎn)生8位二進制數(shù)，即得到該窗口中心像素點的LBP值；
然后計算每個cell的直方圖，即每個數(shù)字（假定是十進制數(shù)LBP值）出現(xiàn)的頻率；然后對該直方圖進行歸一化處理。
最后將得到的每個cell的統(tǒng)計直方圖進行連接成為一個特征向量，也就是整幅圖的LBP紋理特征向量；
然后便可利用SVM或者其他機器學習算法進行分類了。

Haar-like特征（描述子）

參考博客
Haar-like最早由Papageorgiou等人用于人臉識別，Viola和Jones在此基礎上使用了3種類別共四種形式的特征，如下圖所示：

上圖中共有(A，C）、B、D三種特征，即水平、垂直、對角三種特征，所以haar-like特征描述子也就只能描述水平、垂直、對角這三種方向的邊緣或線段，三種特征模板的特征值計算如下：

A：sum(白) - sum(黑)
C：sum(白) - 2 * sum(黑)
A：sum(白) - sum(黑)
A：sum(白) - sum(黑)

Haar特征值反映了圖像的灰度變化情況。例如：臉部的一些特征能由矩形特征簡單的描述，如：眼睛要比臉頰顏色要深，鼻梁兩側比鼻梁顏色要深，嘴巴比周圍顏色要深等。
以上提到的特征模板成為特征原型，特征原型經(jīng)過在圖像上平移、伸縮得到的特征成為矩形特征，其值為特征值，矩形特征值是矩形模版類別、矩形位置和矩形大小這三個因素的函數(shù)，因此隨著這三個自變量的變化會產(chǎn)生非常多的矩形特征(數(shù)萬、數(shù)十萬)，所以這里就會有如下兩個問題：

矩形特征的計算問題(可以通過積分圖來解決)
分類時有效特征的選擇問題(可以通過AdaBoost分類器實現(xiàn))

積分圖的計算
采用動態(tài)規(guī)劃算法計算積分圖
積分圖能夠在多種尺度下，使用相同的時間（常數(shù)時間）來計算不同的特征，因此大大提高了檢測速度。
Harr-like矩形特征擴展
Lienhart R.等對Haar-like矩形特征庫進行了擴展，加入了 $45^o$ 角的矩形特征，擴展后的特征大致有4種類型：邊緣特征、線特征環(huán)、中心環(huán)繞特征和對角線特征，如下如所示：

SIFT(Scale-invariant feature transform)——特征點檢測+描述子

參考博客
SIFT即尺度不變特征轉換，它是一種捕獲影像局部特征的算法，這些特征往往是影像空間尺度的某極值點，SIFT提取器位置、尺度、旋轉不變量，常見的特征如：角點、邊緣點、暗區(qū)的亮點、亮區(qū)的暗點等，這些特征的穩(wěn)定性非常好，對于光線、噪聲、些微視角改變的容忍度相當高，在現(xiàn)今的電腦硬件速度下和小型的特征數(shù)據(jù)庫條件下，辨識速度可接近即時運算。SIFT特征的信息量大，適合在海量數(shù)據(jù)庫中快速準確匹配。
SIFT的應用范圍包括：物體辨識、機器人地圖感知與導航、影像縫合、3D模型建立、手勢辨識、影像追蹤和動作比對。
SIFT算法流程圖

圖解1：圖像金字塔
圖解2：圖像卷積
圖解3：空間極值點(關鍵點)的檢測
1、極值點的初步檢測是在高斯差分(DOG)金字塔中進行的，具體來說，就是待檢測點要域高斯差分金字塔中每組圖像的圖像域和尺度域中的所有相鄰像素進行比較，如下圖所示：

2、關鍵點定位
1中檢測的關鍵點是空間離散的，下面我們通過擬合三維二次函數(shù)來精確定位關鍵點的位置和尺度，同時去除低對比度關鍵點和不穩(wěn)定的邊緣響應點(DOG算子會產(chǎn)生較強的邊緣響應)來增強匹配穩(wěn)定性、提高抗噪聲能力。
- 關鍵點精確定位：
  離散空間的極值點并不是真正的極值點，下圖顯示了二維函數(shù)離散空間得到的極值點與連續(xù)空間極值點的差別。利用已知的離散空間點插值得到的連續(xù)空間極值點的方法叫做子像素插值。
  
  子像素插值的原理：利用DoG函數(shù)在尺度空間的的Taylor展開式——插值函數(shù)進行插值，1)求高斯差分尺度空間中任意離散極值點處的泰勒展開式，并舍棄二階以后的所有項，2)求該泰勒展開式的極值點( $\hat{X}，D(\hat{X})$ )， $\hat{X}$ 表示相對插值中心的偏移量，當它的任一維度(x, y, σ)大于0.5，則可以認為插值的中心已經(jīng)偏移到了臨近點上，此時應該改變當前極值點的位置，并在新的位置反復插值直到收斂。同時，在此過程中獲取特征點的精確位置(原位置加上擬合的偏移量)以及尺度(σ)。
  
  迭代過程中也有可能超出所設定的迭代次數(shù)或者超出圖像邊界的范圍，此時這樣的點應該刪除，在Lowe中進行了5次迭代。另外，過小的點易受噪聲的干擾而變得不穩(wěn)定，所以將小于某個經(jīng)驗值(Lowe論文中使用0.03，Rob Hess等人實現(xiàn)時使用0.04/S)的極值點刪除。
- 消除邊緣響應：
  一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。DOG算子會產(chǎn)生較強的邊緣響應，需要剔除不穩(wěn)定的邊緣響應點。獲取特征點處的Hessian矩陣，主曲率通過一個2x2 的Hessian矩陣H求出（D的主曲率和H的特征值成正比）：
  $H = \begin{bmatrix} D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{bmatrix}$
  假設H的特征值為α和β（α、β代表x和y方向的梯度）且α>β。令α=rβ則有：
  $Tr(H) = D_{xx} + D{yy} = α + β$
  $Det(H) = D_{xx}D{yy} - D_{xy}^2 = αβ$
  其中Tr(H)求取H的對角元素和；Det(H)為求H的行列式值。
  $\frac{Tr(H)^2}{Det(H)}=\frac{(r + 1)^2}{r}$
  則公式(r+1)^2/r的值在兩個特征值相等時最小，隨著兩個特征值差別的增大而增大。值越大，說明兩個特征值的比值越大，即在某一個方向的梯度值越大，而在另一個方向的梯度值越小，而邊緣恰恰就是這種情況。所以為了剔除邊緣響應點，需要讓該比值小于一定的閾值，因此，為了檢測主曲率是否在某域值r下，只需檢測:
  $\frac{Tr(H)^2}{Det(H)}<\frac{(r + 1)^2}{r}$
  OpenCV建議r = 10
3、關鍵點方向匹配
為了使描述符具有旋轉不變性，需要利用圖像的局部特征為每個關鍵點匹配一個方向，下面是通過使用圖像的梯度的方法實現(xiàn)的
- 梯度直方圖的生成
- 特征點主方向的確定：
  在該特征點領域的方向梯度直方圖中，峰值方向就表示該關鍵點的主方向，為了增強匹配的魯棒性，可以將值大于峰值 * 80%的方向作為該關鍵點的輔助方向，這樣對于有多個峰值(主方向或輔助方向)的關鍵點鄰域，將會在相同的空間位置產(chǎn)生多個空間位置相同但是方向不同的關鍵點(實際編程實現(xiàn)中，就是把該關鍵點復制成多份關鍵點，并將方向值分別賦給這些復制后的關鍵點)。以上操作將會使15%的關鍵點被賦予多個方向，但是可以明顯地提高關鍵點匹配的穩(wěn)定性，此處需要注意的是：離散的梯度方向直方圖要進行插值擬合處理，來求得更精確的方向角度值。
  具體過程

經(jīng)過以上步驟我們就找到了關鍵點的三個信息：位置、所在尺度、方向，由此可以生成SIFT特征。

圖解4：特征點描述符
特征點描述符創(chuàng)建的前提是：已經(jīng)檢測到了圖片中的關鍵點(位置、所在尺度、方向)，要求是：其不隨光照、視角、圖片縮放等變化而變化，而且有較高的區(qū)分度。
- 特征描述子的生成過程
  - 確定計算描述子所需的區(qū)域
    將關鍵點的鄰域劃分為d*d(Love建議d = 4)個子區(qū)域，每個子區(qū)域作為一個種子點，每個種子點8個方向，**考慮到實際計算時，需要采用三線性插值，所需圖像窗口邊長為3x3xσ_oct x(d+1) **，再考慮旋轉因素，所以實際計算時的區(qū)域如下：
    
    其中 $r = \frac{3\sigma\_oct*\sqrt{2}*(d + 1)}{2}$
  - 坐標軸旋轉至主方向(確保旋轉不變性)
  - 生成梯度直方圖
    將鄰域內(nèi)的采樣點分配到對應的子區(qū)域內(nèi)，將子區(qū)域內(nèi)的梯度值分配到8個方向上，計算其權值。
  - 三線性插值
    三線性插值：x_線、y_線、角度_線(8個值)
    
    采樣點在子區(qū)域中的下標(x'',y'')(圖中藍色窗口內(nèi)紅色點)線性插值，計算其對每個種子點的貢獻。如圖中的紅色點，落在第0行和第1行之間，對這兩行都有貢獻。對第0行第3列種子點的貢獻因子為dr，對第1行第3列的貢獻因子為1-dr，同理，對鄰近兩列的貢獻因子為dc和1-dc，對鄰近兩個方向的貢獻因子為do和1-do。則最終累加在每個方向上的梯度大小為：
    
    其中k，m，n為0（像素點超出了對要插值區(qū)間的四個鄰近子區(qū)間所在范圍）或為1（像素點處在對要插值區(qū)間的四個鄰近子區(qū)間之一所在范圍）。
  - 特征描述子
    如上統(tǒng)計的448=128個梯度信息即為該關鍵點的特征向量。
    特征向量形成后，為了去除光照變化的影響，需要對它們進行歸一化處理，對于圖像灰度值整體漂移，圖像各點的梯度是鄰域像素相減得到，所以也能去除。得到的描述子向量為H=(h1,h2,.......,h128)，歸一化后的特征向量為L=(L1,L2,......,L128)，則
  - 特征描述子的門限化
    非線性光照，相機飽和度變化對造成某些方向的梯度值過大，而對方向的影響微弱。因此設置門限值(向量歸一化后，一般取0.2)截斷較大的梯度值(大于0.2的則就令它等于0.2，小于0.2的則保持不變)。然后再進行一次歸一化處理，提高特征的鑒別性。
- 描述子生成過程