画像特徴量

特徴量

SIFT

Scale Invariant Feature Transformの略。2004年発表。Difference of Gaussian (DoG)の極値を探すことでエッジ点を検出。回転、拡大縮小、限定アフィン変換に対して頑強だが、計算コストがかかる。

SURF

Speed Up Robust Featureの略。2008年発表。回転、拡大縮小に対して頑強だが、アフィン変換に対して弱い。SIFTと比べると高速。

KAZE

2012年発表。回転、拡大縮小、限定アフィン変換に対して頑強。

AKAZE

Accelerated-KAZE。2013年発表。回転、拡大縮小、限定アフィン変換に対して頑強。

BRIEF

Binary Robust Independent Elementary Featuresの略。 特徴点の記述に使われ、検出には使えない。

ORB

Oriented FAST and Rotated BRIEF の略。2013年発表。回転、拡大縮小、限定アフィン変換に対して頑強。

BRISK

Binary Robust Invariant Scalable Keypointsの略。2011年発表。

FAST

Features from Accelerated Segment Testの略。

Harris

コーナー検出。1988年

http://www.bmva.org/bmvc/1988/avc-88-023.pdf

参考

ieeexplore.ieee.org

Harrisコーナー検出。

u, vを適当な変位とする。画像上のある点 Pがコーナーであるかを判定するために、点 P周りのみ0でない値を持つ窓関数 w_{P}(x, y)を用いて

\begin{eqnarray} E_{P} &\equiv& \sum_{x, y} w_{P}(x, y) \left[ I(x+u, y+v) - I(x, y) \right]^{2} \\ \end{eqnarray}

を使い、この値が大きい点 Pでコーナーと判定する。

f:id:salpik:20220403224050p:plain
窓関数のイメージ

E_{P}を変形すると

\begin{eqnarray} E_{P} &=& \sum_{x, y} w_{P}(x, y) \left[ \frac{\partial I}{\partial x} u + \frac{\partial I}{\partial y} v \right]^{2} \\ &=& (u, v) \sum_{x, y} w_{P}(x, y) \left( \begin{array}{cc} (\frac{\partial I}{\partial x})^{2} & \frac{\partial I}{\partial x} \frac{\partial I}{\partial y} \\ \frac{\partial I}{\partial x} \frac{\partial I}{\partial y} & (\frac{\partial I}{\partial y})^{2} \\ \end{array} \right) \left( \begin{array}{c} u \\ v \end{array} \right) \\ &\equiv& (u, v) M \left( \begin{array}{c} u \\ v \end{array} \right) \end{eqnarray}

となる。ここで行列 Mを M = P^{-1}\Sigma Pと対角化したとすると

\begin{eqnarray} E_{P} &=& (u, v) P^{-1}\Sigma P \left( \begin{array}{c} u \\ v \end{array} \right) \\ &=& \left[ P \left( \begin{array}{c} u \\ v \end{array} \right) \right]^{-1} \Sigma \left[ P \left( \begin{array}{c} u \\ v \end{array} \right) \right] \end{eqnarray}

と変形できる。これは、 \left( \begin{array}{c} u^{'} \ v^{'} \end{array} \right) \equiv P\left( \begin{array}{c} u \ v \end{array} \right)という新しい直行軸 u^{'}, v^{'}を取ったときに、それぞれの方向にどれだけ変化するかを表しており、その変化係数がそれぞれの固有値である。。新しい直行軸は変化の主成分を表しているため、以下のことが言える。

  • 第1、第2固有値のどちらも大きい：頂点である
  • 第1固有値のみ大きく、第2固有値は小さい：辺である
  • 第1、第2固有値のどちらも小さい：辺でも頂点でもない

具体例

コーナーの場合

窓関数領域において、 x方向と y方向がそれぞれ独立に大きな微分 \frac{\partial I}{\partial x}、 \frac{\partial I}{\partial y}を取るとする。そうすると (\frac{\partial I}{\partial x})^{2}や (\frac{\partial I}{\partial y})^{2}は大きな値をとるが \frac{\partial I}{\partial x}\frac{\partial I}{\partial y}はある程度互いに独立になり0に近い値になるので、行列 Mは対角行列に近くなり、固有ベクトルの方向も x軸と y軸に平行になる。

f:id:salpik:20220403224921p:plain
行列 Mの計算例

辺の場合

例えばx軸に平行な辺の場合、 |\frac{\partial I}{\partial y}| >> |\frac{\partial I}{\partial x}|である。 (\frac{\partial I}{\partial y})^{2}は (\frac{\partial I}{\partial x})^{2}と比べると大きくなり、 \frac{\partial I}{\partial x} \frac{\partial I}{\partial y}は互いにキャンセルして0に近くなる。 (\frac{\partial I}{\partial x})^{2}も小さい値であるが常に2乗で足していっているので \frac{\partial I}{\partial x} \frac{\partial I}{\partial y}の項よりは大きくなると思うと、やはり行列 Mは対角行列となり、第1固有値は |\frac{\partial I}{\partial y}|で固有ベクトルが[tex: y軸方向、第2固有値は |\frac{\partial I}{\partial x}|で固有ベクトルが[tex: x軸方向となる。

f:id:salpik:20220403225318p:plain
固有ベクトルの方向とその大きさのイメージ

参考

labs.eecs.tottori-u.ac.jp

SIFT

画像ピラミッド

画像ピラミッドとは、重み関数 w(m, n)を定義し、この重みに基づいて圧縮した画像をピラミッドのように並べたものである。元の画像のサイズを N\times Mとし、 G_{0}(x, y)\ (0 \le x \lt N, 0 \le y \lt M)とすると、下から i\ (i=0, 1, 2, \dots)層目のピラミッドの画像は \frac{N}{2^{i}} \times \frac{M}{2^{i}}であり、

\begin{eqnarray} G_{i+1}(x, y) = \sum_{m, n} w(m, n) G_{i}(2x+m, 2y+n) \end{eqnarray}

と表される。重み関数としてはガウシアンなどが使われる。またこのように画像サイズを圧縮することをOctaveと呼ぶ

f:id:salpik:20220327221720p:plain
画像ピラミッドのイメージ

参考

medium.com

labs.eecs.tottori-u.ac.jp

画像フィルターと微分の関係

画像の微分はフィルターをかけることと同値である。

1階微分

例えば I(x, y)のピクセルにおいて xと y方向の微分を考える。

\begin{eqnarray} I(x+1, y) &\sim& I(x, y) + I_{x}(x, y) \\ I(x-1, y) &\sim& I(x, y) - I_{x}(x, y) \\ \end{eqnarray}

となるから、

\begin{eqnarray} I_{x}(x, y) = I(x+1, y) - I(x-1, y) \end{eqnarray}

となるから、これは (-1\ 0\ 1)というフィルターを適用したのと同等である。

2階微分

\begin{eqnarray} I(x+1, y) &\sim& I(x, y) + I_{x}(x, y) + \frac{1}{2}I_{xx}(x, y) \\ I(x-1, y) &\sim& I(x, y) - I_{x}(x, y) + \frac{1}{2}I_{xx}(x, y) \\ \end{eqnarray}

となるから、

\begin{eqnarray} I_{xx}(x, y) = I(x-1, y) -2 I(x, y) + I(x+1, y) \end{eqnarray}

となり、 (1\ -2\ 1)というフィルターを適用したのと同等である。2次元に拡張すれば、2階微分の和であるラプラシアンは

\begin{eqnarray} \Delta \equiv I_{xx} + I_{yy} = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \\ \end{array} \right) \end{eqnarray}

というフィルターとなる。

エッジとラプラシアンの関係

エッジ位置というのは2階微分が0でありかつ1階微分の絶対値が大きいところとして定義できる。したがってラプラシアン \Delta \equiv I_{xx}+I_{yy}のフィルタをかけこの値の絶対値が小さいところをエッジ点とすればよい。

f:id:salpik:20220327224519p:plain
エッジ位置と1階微分、2階微分の関係（点線がエッジ位置）

参考

https://www.cse.psu.edu/~rtc12/CSE486/lecture11.pdf

LoGとDoGの関係

まず、ガウシアンフィルターのラプラシアンは、ガウシアンのラプラシアンのフィルターになる。すなわち、 G(x, y; \sigma)をガウシアンフィルタ

\begin{eqnarray} G(x, y; \sigma) \equiv \frac{1}{2\pi \sigma^{2}} \exp(-\frac{x^{2}+y^{2}}{2\sigma^{2}}) \end{eqnarray}

とし、ピクセルの値を I(x, y)とすると、

\begin{eqnarray} \Delta [ G(x, y; \sigma) \otimes I(x, y) ] = [ \Delta G(x, y; \sigma) ] \otimes I(x, y) \end{eqnarray}

となる。

証明

\begin{eqnarray} \Delta [ G(x, y; \sigma) \otimes I(x, y) ] &=& (\frac{\partial^{2}}{\partial x^{2}} + \frac{\partial^{2}}{\partial y^{2}}) \sum_{X, Y} G(x-X, y-Y)I(X, Y) \\ &=& \sum_{X, Y} [ (\frac{\partial^{2}}{\partial x^{2}} + \frac{\partial^{2}}{\partial y^{2}})G(x-X, y-Y) ] I(X, Y) \\ &=& [ \Delta G(x, y, \sigma) ] \otimes I(x, y) \end{eqnarray}

1次元の場合は、

\begin{eqnarray} G(x; \sigma) = \frac{1}{2\pi \sigma^{2}} \exp(-\frac{x^{2}}{2\sigma^{2}}) \end{eqnarray}

となるので、

\begin{eqnarray} \frac{\partial G(x; \sigma)}{\partial x} &=& \frac{1}{2\pi \sigma^{2}} (-\frac{x}{\sigma^{2}})\exp(-\frac{x^{2}}{2\sigma^{2}}) \\ \frac{\partial^{2} G(x; \sigma)}{\partial x^{2}} &=& \frac{1}{2\pi \sigma^{2}} \left(-\frac{1}{\sigma^{2}} \right) \left(1-\frac{x^{2}}{\sigma^{2}}\right) \exp(-\frac{x^{2}}{2\sigma^{2}}) \end{eqnarray}

f:id:salpik:20220327231349p:plain
ガウシアンの1階微分、2階微分

一方、異なる標準偏差のガウシアンを引き算すると、ガウシアンの2階微分の形に近くなる。

f:id:salpik:20220327232930p:plain
ガウシアンの引き算
これが、LoG(Laplacian of Gaussian filter)をDoG(Difference of Gaussian filter)で近似するということである。すなわち、 \sigmaの異なるガウシアンフィルターを使って同じ画像サイズの画像をいくつか生成し、その差分をとることでラプラシアンフィルターの近似を得て、その絶対値が小さいところとしてエッジを検出する。また、その時に、1)同じ \sigmaのフィルターをかけた画像内での周辺8ピクセルおよび2)前後の \sigmaのフィルターをかけた画像内での周辺および自分の位置9ピクセルを使って、異なる \sigmaのフィルターをかけた画像においてもエッジとなっているかを確認したのち正式な特徴点として登録される。

f:id:salpik:20220327235213p:plain
赤い対象ピクセルが特徴点として登録するか判断する時にチェックされる周辺ピクセル

参考

https://www.cse.psu.edu/~rtc12/CSE486/lecture11.pdf

Descriptorの計算

特徴点の周辺を 4 \times 4=16領域に分割し、各領域ごとに 45^\circごとに合計8方向の特徴ベクトルを用意する。したがってSIFTの1つの特徴点は合計128次元のベクトルである。