*SIFT とは 　特徴的な輝度分布を持つ部位（以降，単に”特徴”と表記）を画像から検出し，それを対応付けるためのアルゴリズムの１つです．画像のサイズや角度が異なる条件においても，特徴を対応付けることができます(Lowe[1])． 　図１は，SIFTによる特徴検出とその対応付け結果を示します． [img:zf5k] {{small:図１　SIFTによる特徴検出とその対応付け結果}} {{small:緑の円は特徴の位置とサイズ，青緑の線は対応付けた特徴を表す}} {{small:[1]D. Lowe, "Distinctive image features from scale-invariant keypoints" International Journal of Computer Vision, 60, 2 2004. [link:https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf] }} *サンプルコード (C++) ライブラリ：[link:simplesp] サンプルコード：simplesp/sample/sp/sift Lennaの画像から特徴の対応付けを行います．また，その対応関係から画像のホモグラフィを計算します． *アルゴリズム 　ここでは，SIFTの処理の手順を説明します．処理は，次の２つの段階に分かれます． １．Detection　画像から特徴の位置とサイズを検出する． ２．Descripstion　特徴の周囲の輝度分布から，特徴量を抽出する． また，通常はこの後，処理２で計算した特徴量を手掛かりに特徴の対応付けを行います． **Detection 位置とサイズを検出 　SIFTでは，Blobと呼ばれる水玉模様のような特徴に注目します．この特徴は，輝度値が２次元的に凸の分布（山形或いは谷型）になっています．この分布の傾向を手掛かりに，位置とサイズを検出します． ***ラプラシアンフィルタの性質 　検出方法を説明する上で，まずはラプラシアンフィルタの性質について説明します．ラプラシアンフィルタは画像の2階偏微分を計算します．この計算は，輝度値が凸の分布になっている位置で強い応答を示します．つまり，特徴のある位置で強い応答が期待できます． 　ただし，期待する応答を得るには，特徴のサイズに合わせたフィルタが必要です．大きな特徴に小さなフィルタを適応しても，期待する応答は得られません．そこで，サイズを変えた複数のフィルタを使う方法を考えます． ***複数のフィルタを使った特徴検出 　所定の増加率{$k$}でサイズを変えたフィルタを使い，畳み込みを行います．図２はその処理の模式図を表します． [img:5cpv] {{small:サイズを変えた複数のフィルタを使った畳み込み演算}} 　この処理の結果，位置とサイズの空間に関するフィルタの応答マップ{$R(x,y,s)$}が得られます．ここで，{$s$}は使用したフィルタのサイズを表します．このマップから強い応答を見つけることで，特徴の位置とサイズを検出することができます． 　しかし，サイズの大きいフィルタを使う都合から，計算コストが問題になります．仮に{$k=1.3$}と置くと4段目のフィルタのサイズは約2倍になります（フィルタは2次元ですので，計算量は2倍の2乗で約４倍になります）．通常それ以上のサイズも考えて計算を行うため，応答マップの計算コストは膨大になります． 　この問題に対し，次に示すDoGと呼ばれる方法は，ガウシアンフィルタの組み合わせによってラプラシアンフィルタを近似することで，計算を効率化します． ***DoG(Difference-of-Gaussian)による計算の効率化 　ここでは，ラプラシアンフィルタをガウシアンフィルタの組み合わせで近似できる理屈を説明します．まず，フィルタの元になるガウス関数とその２階偏微分（ラプラシアン）は，式（１）と（２）で定義します． {$$G(x, y, \sigma)=\frac{1}{2\pi\sigma^2}\exp(-\frac{x^2 + y^2}{2\sigma^2}) \tag{1}$$} {$$L(x, y, \sigma)=\nabla^2 G(x, y, \sigma)=-\frac{x^2 + y^2-2\sigma^2}{2\pi\sigma^6}\exp(-\frac{x^2 + y^2}{2\sigma^2}) \tag{2}$$} ここで，式（１）を{$\sigma$}で偏微分すると式（３）が得られます（この式は，物理学の分野では拡散方程式と呼ばれています）． {$$\frac{\partial G(x, y, \sigma)}{\partial \sigma} = \sigma\nabla^2 G(x, y, \sigma) \tag{3}$$} 一方，式（１）を{$\sigma$}で偏微分した値は，式（４）で近似計算することもできます． {$$\frac{\partial G(x, y, \sigma)}{\partial \sigma} \simeq \frac{G(x, y, k\sigma) - G(x, y, \sigma)}{k\sigma - \sigma} \tag{4}$$} 次に，式（３）と（４）から，式（５）が得られます． {$$\nabla^2 G(x, y, \sigma) \simeq \frac{G(x, y, k\sigma) - G(x, y, \sigma)}{k\sigma^2 - \sigma^2} \tag{4}$$} この式から，左辺のラプラシアンは，右辺のガウス関数の差分（と係数）で近似できます． 　以上の理屈から，ラプラシアンフィルタはガウシアンフィルタの差分で近似できることが分かります．ただし，この時点では利用するフィルタが変わっただけで，そのサイズは変化していません．フィルタのサイズを小さく抑えるには，ガウシアンフィルタの重ね掛けのテクニックを利用します．つまり，{$ G(x,y,k\sigma) \ast I $}を素直に計算するのではなく，{$G(x,y,k\sigma) \ast I = G(x,y,a_1) \ast (G(x,y,\sigma) \ast I)$}と置き換えて計算します．これにより，サイズの大きい{$G(x,y,k\sigma)$}を使わずに計算を進めることができます．なお，{$a_i$}は代わりに利用するフィルタのサイズで，{$ a_i^2 =  (k^i\sigma)^2 - (k^{i-1}\sigma)^2 $}という関係があります．{{small:ただし，{$a_i$}は{$k^i\sigma$}に比べると小さな値ですが，それでも段階的に大きくはなります}} 　図３は，以上に説明したDoGの模式図を表します． [img:y17d] {{small:DoGの模式図}} ***画像ピラミッドの利用 　ガウシアンフィルタの重ね掛けにより，使用するフィルタのサイズを小さく抑えることができます．しかし，その方法であっても段階が進むにつれフィルタのサイズは徐々に大きくなります．また，フィルタのサイズが大きくなると，畳み込み計算の際に，画像の端からはみ出る部分が発生し適切に応答が計算できなくなります． 　これらの問題の対策として，画像ピラミッドを利用した階層的な計算を行います．画像ピラミッドとは，画像を{$\frac{1}{2}$}，{$\frac{1}{4}$}，...とダウンサンプリングしたセットのことです．画像の解像度を落とした階層的な計算により，できるだけ大きなフィルタを使わずに済ませます． 　画像ピラミッドを利用した計算について具体的に説明します． 　まず，入力画像{$I_1$}について，元のフィルタサイズの2倍に相当する段階{$ G(x,y,2\sigma) $}まで，DoGによる計算を進めます．つまり，{$ L(x,y,\sigma) \ast I_1 $}から{$ L(x,y,2\sigma) \ast I_1 $}までの応答マップを計算します．次に，画像をダウンサンプリングさせます．ここで，元の入力画像{$I_1$}をダウンサンプリングした画像を{$I_2$}と置きます．{$I_2$}に対してガウシアンフィルタを適応した結果{$G(x,y,\sigma) \ast I_2$}は，{$G(x,y,2\sigma) \ast I_1$}をダウンサンプリングすることで得られます．この{$G(x,y,\sigma) \ast I_2$}をスタート地点にして，{$I_1$}と同様にDoGの計算を行います．ここでは，使用するフィルタのサイズ{$a_i$}は同じですが，画像のサイズが小さくなっているので，相対的に大きな特徴に注目していることになります．この操作により，大きな特徴の検出にかかる計算コストを抑えることができます． ***極値の検出 　画像ピラミッドの各階層から計算した応答マップ{$R(x,y,s)$}を参考に，特徴の位置とサイズを検出します．ここで，マップ中の各座標{$(x,y,s)$}の値が周囲3x3マスの中で最も強くかつ閾値以上である場合，特徴として検出します．この時，注目する座標{$(x,y,s)$}が特徴の位置とサイズを表します． **Descripstion 特徴量を抽出 　SIFTでは，注目する特徴の位置とサイズに基づいて，画像から128次元のベクトルを抽出し，それを特徴量にします．そこではまず，特徴の角度を決めます．その角度を基準に特徴量を抽出することで，特徴の回転に寄らず同じ特徴量を得られるようにします． ***角度の推定 　特徴の角度は，特徴のサイズから所定の範囲を決め，その範囲内の各部の輝度勾配を参考にして計算します．具体的には，範囲内の各部の輝度勾配の角度をヒストグラムにして，閾値以上の頻度でピークとなる角度を推定します． ***特徴量の抽出 　特徴のサイズから所定の範囲を決め，4x4のブロックに分割します．各ブロックについて8方向の勾配の強度を算出し，合計して128次元のベクトルとして算出します．