目次

HOG特徴量

画像認識における特徴量の1つで、2005年に発表されてから、人や車両などを検出するのに一定の精度が認められている。

ピクセルを、いくつか(8×8程度)まとめて「セル」を作る。また、セルをいくつか(2×2~4×4程度)まとめて「ブロック」を作る。

「ピクセル毎の輝度の変化の方向と強さ」を「セル単位でヒストグラム化」した後「ブロック単位で正規化」する。

画像からの人体・車両検出には、この特徴量をSVM(Support Vector Machine)で分類する手法がメジャーであった。

近年は、流行のディープラーニングを応用したCNN(Convolutional Neural Network)(参考: Convolutional Neural Networkとは何なのか - Qiita)を用いた手法が出てきており、人気が取って代わられている感があるが、考え方は知っておいて損は無いので、メモ。

ただし、HOGにしろCNNにしろ、教師あり学習なので、まともに精度を出すには数千個レベルのの正解データの作成が必要となる。ツールはあっても、ここで頓挫するケースは多い。

特徴

Pythonでの実装

Pythonでは、主に2つのパッケージに実装が存在する。違いはよくわからないが、デフォルト値や、細かな計算方法の差異で僅かに結果が異なるらしい。

執筆時点で、scikit-imageは0.13.10.14devがあるが、hogに関して与えるパラメータに変更が生じている。

基本的なところは変わっていないが、結果の画像イメージを得るvisualisevisualizeに微妙に変わってたり、0.13までは画像を2次元のグレースケールで与えないといけなかったところ、0.14devではmultichannel=TrueでRGBの3次元配列で与えても良くなったりとしている。

scikit-imageでの実装

こちらはpythonで書かれているため順を追って見ていきやすい。(0.13.1準拠)

Parameters概要
image M行N列のnumpy.ndarray
画像の輝度を表す2次元配列
orientations9輝度方向をヒストグラム化する際のbins数
180°を20°づつということで9がよく使われる
pixels_per_cell(8,8)1セルにおけるピクセル数
cells_per_block(3,3)1ブロックにおけるセル数
block_norm'L2-Hys'ブロックを正規化する時のメソッド
【機械学習】LPノルムってなんだっけ? - Qiita
visualiseTrueこれの右側のような、結果を直感的に理解しやすい画像を生成して一緒に返す
transform_sqrtTrue正規化する時にルートを取る?効果はよくわかっていない
feature_vectorTrue返す前に配列を1次元化する

結果の解釈が難しいので、何をやっているか順を追ってみていく。まず、超簡単な4x4pxの輝度情報があるとする。pixels_per_cell=(2,2), cells_per_block=(2,2)とする。

     |      2x2 px   = 1 cell
  1 2 4 7   2x2 cell = 1 block
__4 7 1 2__ 
  4 4 7 7   ←16 px
  2 2 1 1      4 cell
     |         1 block

まず、x,yについてnumpyでgradientを取る。端の処理をどうするかはいろいろあると思うが、scikit-imageではnp.gradient()を用いて「端であれば隣との差分、それ以外なら両端の差分/2」としている。

gx                  gy
 1.  1.5  2.5  3.    3.   5.  -3.  -5.
 3. -1.5 -2.5  1.    1.5  1.   1.5  0.
 0.  1.5  1.5  0.   -1.  -2.5  0.  -0.5
 0. -0.5 -0.5  0.   -2.  -2.  -6.  -6.
 ↑
 (2-1) (4-1)/2 (7-2)/2 (7-4)
 (7-4) (1-4)/2 (2-7)/2 (2-1)
 (4-4) (7-4)/2 (7-4)/2 (7-7)
 (2-2) (1-2)/2 (1-2)/2 (1-1)

ここから、各セルの輝度勾配と強さを算出する。勾配はarctan, 強さはnormを用いる。

勾配(arctan(gy/gx)、単位: degrees)
[[  71.56505118   73.30075577  -50.19442891  -59.03624347]
 [  26.56505118  146.30993247  149.03624347    0.        ]
 [ -90.          -59.03624347    0.          -90.        ]
 [ -90.         -104.03624347  -94.76364169  -90.        ]]
↓
勾配を20°毎に分類(負なら+180°し、20で割る)
[[3 3 6 6]
 [1 7 7 0]
 [4 6 0 4]
 [4 3 4 4]]

勾配強さ(√(gx^2+gy^2) / 4)4で割っているのはセルのピクセル数で正規化?
[[ 0.79056942  1.30503831  0.97628121  1.45773797]
 [ 0.83852549  0.45069391  0.72886899  0.25      ]
 [ 0.25        0.72886899  0.375       0.125     ]
 [ 0.5         0.5153882   1.50519932  1.5       ]]

9個に分類した勾配方向別に、勾配強さで重みを付けて、2×2のセル毎に、ヒストグラムに加算していく。

orientation_histogram
[[[ 0.          0.83852547  0.          2.09560776  0.          0.          0.    0.45069391  0.        ]
  [ 0.25        0.          0.          0.          0.          0.    2.43401909  0.72886896  0.        ]]
 [[ 0.          0.          0.          0.51538819  0.75        0.    0.72886896  0.          0.        ]
  [ 0.375       0.          0.          0.          3.13019943  0.          0.    0.          0.        ]]]

例えば、orientation_histogram[0][0]の9個の数字

[ 0.  0.83852547  0.  2.09560776  0.  0.  0.  0.45069391  0.]

は、元の画像の左上の2×2のセル

元配列      勾配方向   勾配強さ
[[1  2]     [[3  3]    [[0.79  1.31]
 [4  7]]     [1  7]]    [0.84  0.45]]

について、各勾配のindexに勾配強さを加算したものとなっている。つまり、0で初期化された要素数9の配列hを用意して、h[3]+=0.79, h[3]+=1.31, h[1]+=0.84, h[7]+=0.45とした結果となっている。

これをブロック毎に正規化していく。これにより、明るさが変化した時の影響が均される。

ブロックは、pixels_per_cellごとにスライドしていくので、正規化はx,yのそれぞれで(セル数 - 1ブロック内のセル数 + 1)回行われる。これをnx, ny回とすると、この処理の結果は、[nx, ny, cells_per_block_x, cells_per_block_y, orientation]の配列となる。この例では、[1,1,2,2,9] となる。

[[[[[ 0.          0.03627755  0.          0.04159976  0.          0.          0.      0.0194986   0.        ]
    [ 0.01081588  0.          0.          0.          0.          0.      0.04159976  0.03153343  0.        ]]
   [[ 0.          0.          0.          0.0222975   0.03244763  0.      0.03153343  0.          0.        ]
    [ 0.01622381  0.          0.          0.          0.04159976  0.          0.      0.          0.        ]]]]]

例が4×4の小さな配列だったので、ブロックでの正規化回数が1回になってしまったが、本来はこれを移動させながら何回も行う。同じセルでも、属するブロックが異なるとその回数分、正規化される。

正規化については、メソッドによって異なる。

L2-Hysの根拠論文: ijcv04.pdf p.16

However, non-linear illumination changes can also occur due to camera saturation or due to illumination changes that affect 3D surfaces with differing orientations by different amounts.These effects can cause a large change in relative magnitudes for some gradients, but are less likely to affect the gradient orientations.Therefore, we reduce the influence of large gradient magnitudes by thresholding the values in the unit feature vector to each be no larger than 0.2, and then renormalizing to unit length.This means that matching the magnitudes for large gradients is no longer as important, and that the distribution of orientations has greater emphasis.The value of 0.2 was determined experimentally using images containing differing illuminations for the same 3D objects.
しかしながら、カメラの飽和により、または異なる量の異なる向きの3D表面に影響を及ぼす照明変化のために、非線形照明変化も起こり得る。これらの影響は、いくつかの勾配の相対的な大きさの大きな変化を引き起こすことがあるが、勾配の方向に影響を与える可能性は低い。したがって、単位特徴ベクトルの値をそれぞれ0.2以下に閾値処理し、次に単位長に再正規化することにより、大きな勾配の影響を低減する。これは、大きな勾配の大きさを一致させることはもはや重要ではなく、方向の分布がより重視されることを意味する。0.2の値は、同じ3D物体に対する異なる照度を含む画像を用いて実験的に決定された。

最後にこれを1次元化したのが、結果として返る。これを特徴量ベクトルとして利用する。

AdaBoost

上記の通り、HOG特徴量はベクトルの要素数が結構膨大になる。

当然その中には分類に役立つものと、あまり役立たないものがある。これを、検出率を上げるためにいい感じにチューニングする手法をBoostingといい、その中の1つにAdaBoostがある。

FIXME