HOG（描述子）

參考博客
HOG+SVM在行人檢測中獲得巨大成功
HOG的主要思想是圖片的局部特征可以被梯度或邊緣的方向密度分布很好地表達兆沙。
方向梯度直方圖提取流程：
0、預處理：灰度化（將圖像看做一個x,y,z（灰度）的三維圖像），采用Gamma校正法對輸入圖像進行顏色空間的標準化（歸一化）；目的是調節(jié)圖像的對比度再姑，降低圖像局部的陰影和光照變化所造成的影響，同時可以抑制噪音的干擾找御；
1元镀、把窗口劃分成若干個塊(blocks)
2绍填、將每個塊劃分為若干個元胞(cells)
3、統(tǒng)計每個元胞內部的梯度方向直方圖栖疑，并以此為該元胞的特征向量
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內部的梯度直方圖
5击敌、組合每個block內的所有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）缝其，把一個塊內的特征向量聯(lián)起來得到36維的特征向量，用塊對樣本圖像進行掃描徘六，掃描步長為一個單元内边。最后將所有塊的特征串聯(lián)起來，就得到了人體的特征待锈。例如漠其，對于64*128的圖像而言，每16*16的像素組成一個cell竿音，每2*2個cell組成一個塊和屎，因為每個cell有9個特征，所以每個塊內有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的窗口內的，其生成過程為：以9個像素中的中心像素為閾值盛杰，其周圍的8個像素中比它大的設置為1挽荡，比它小的設置為0，并以此8位二進制數(shù)表示LBP特征饶唤，LBP特征的最終表示要轉化為10進制數(shù)徐伐。
改進后的LBP

• 1贯钩、圓形LBP：為了改進原始LBP的主要缺陷——窗口大小不能隨這不同尺寸和頻率的紋理特征動態(tài)變化募狂，Ojala等人將3*3的鄰域擴展到半徑為R的任意領域，從而產生半徑為R的圓形領域內基于P個采樣點的LBP算子角雷。
• 2祸穷、LBP旋轉不變模式：原始的LBP定義保證了LBP算子的灰度不變性但并不能保證其旋轉不變性，為克服此缺陷勺三，Maenpaa等人通過不斷旋轉圓形鄰域并在不同方向的領域計算原始LBP雷滚，取所有LBP的最小值來實現(xiàn)LBP算子的旋轉不變性
• 3、LBP的等價模式：如果用原始LBP的定義吗坚，那么在p個采樣點的LBP算子中祈远，產生的LBP將有種呆万，這不僅僅會降低紋理識別、分類的效果(可能是由于對高頻噪聲過擬合造成的)车份，而且對信息存取也是不利的谋减，將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表示鄰域集內的采樣點數(shù)袒炉，這使得特征向量的維數(shù)更少，并且可以減少高頻噪聲帶來的影響樊零。

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

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

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

Haar-like特征（描述子）

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

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

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

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

積分圖的計算
采用動態(tài)規(guī)劃算法計算積分圖
積分圖能夠在多種尺度下析二，使用相同的時間（常數(shù)時間）來計算不同的特征，因此大大提高了檢測速度。
Harr-like矩形特征擴展
Lienhart R.等對Haar-like矩形特征庫進行了擴展叶摄，加入了角的矩形特征属韧，擴展后的特征大致有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算子會產生較強的邊緣響應)來增強匹配穩(wěn)定性瘪校、提高抗噪聲能力澄暮。

  • 關鍵點精確定位：
    離散空間的極值點并不是真正的極值點名段，下圖顯示了二維函數(shù)離散空間得到的極值點與連續(xù)空間極值點的差別。利用已知的離散空間點插值得到的連續(xù)空間極值點的方法叫做子像素插值泣懊。
    

    
    子像素插值的原理：利用DoG函數(shù)在尺度空間的的Taylor展開式——插值函數(shù)進行插值伸辟，1)求高斯差分尺度空間中任意離散極值點處的泰勒展開式，并舍棄二階以后的所有項馍刮，2)求該泰勒展開式的極值點()，表示相對插值中心的偏移量卡啰，當它的任一維度(x, y, σ)大于0.5静稻，則可以認為插值的中心已經(jīng)偏移到了臨近點上，此時應該改變當前極值點的位置匈辱，并在新的位置反復插值直到收斂姊扔。同時，在此過程中獲取特征點的精確位置(原位置加上擬合的偏移量)以及尺度(σ)梅誓。

    迭代過程中也有可能超出所設定的迭代次數(shù)或者超出圖像邊界的范圍恰梢，此時這樣的點應該刪除，在Lowe中進行了5次迭代梗掰。另外嵌言，過小的點易受噪聲的干擾而變得不穩(wěn)定，所以將 小于某個經(jīng)驗值(Lowe論文中使用0.03及穗，Rob Hess等人實現(xiàn)時使用0.04/S)的極值點刪除摧茴。

  • 消除邊緣響應：
    一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率埂陆。DOG算子會產生較強的邊緣響應苛白，需要剔除不穩(wěn)定的邊緣響應點。獲取特征點處的Hessian矩陣焚虱，主曲率通過一個2x2 的Hessian矩陣H求出（D的主曲率和H的特征值成正比）：
    
    假設H的特征值為α和β（α购裙、β代表x和y方向的梯度）且α>β。令α=rβ則有：
    
    
    其中Tr(H)求取H的對角元素和鹃栽；Det(H)為求H的行列式值躏率。
    
    則公式(r+1)^2/r的值在兩個特征值相等時最小，隨著兩個特征值差別的增大而增大民鼓。值越大薇芝，說明兩個特征值的比值越大，即在某一個方向的梯度值越大丰嘉，而在另一個方向的梯度值越小夯到，而邊緣恰恰就是這種情況。所以為了剔除邊緣響應點饮亏，需要讓該比值小于一定的閾值耍贾，因此阅爽，為了檢測主曲率是否在某域值r下，只需檢測:
    
    OpenCV建議r = 10

  3逼争、關鍵點方向匹配
  為了使描述符具有旋轉不變性优床，需要利用圖像的局部特征為每個關鍵點匹配一個方向劝赔，下面是通過使用圖像的梯度的方法實現(xiàn)的

  • 梯度直方圖的生成
  • 特征點主方向的確定：
    在該特征點領域的方向梯度直方圖中誓焦，峰值方向就表示該關鍵點的主方向，為了增強匹配的魯棒性着帽，可以將值大于峰值 * 80%的方向作為該關鍵點的輔助方向杂伟，這樣對于有多個峰值(主方向或輔助方向)的關鍵點鄰域，將會在相同的空間位置產生多個空間位置相同但是方向不同的關鍵點(實際編程實現(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ū)域如下：
      
      
      其中

    • 坐標軸旋轉至主方向(確保旋轉不變性)

      
      

    • 生成梯度直方圖
      將鄰域內的采樣點分配到對應的子區(qū)域內够吩，將子區(qū)域內的梯度值分配到8個方向上，計算其權值丈氓。

      
      

    • 三線性插值
      三線性插值：x_線周循、y_線强法、角度_線(8個值)

      
      
      
      

      采樣點在子區(qū)域中的下標(x'',y'')(圖中藍色窗口內紅色點)線性插值，計算其對每個種子點的貢獻湾笛。如圖中的紅色點饮怯，落在第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的則保持不變)。然后再進行一次歸一化處理诵盼，提高特征的鑒別性惠豺。

  • 描述子生成過程