今回はDavid Loweが1999年に提案したSIFTについて話していきます。今更、SIFTなんて解説してもそこらにいっぱい解説あるんだからと思うかもしれませんが、まぁ、マッタリ行きましょうや。なお、SIFTには特許があるので使用時には気をつけて下さい。また、オープンソースの実装にOpenCVの他、OpenSIFTもあります。ところで、昔JAVAで作ったSIFTのプログラムが見当たりません。(T_T) あいつはどこ行ってしまったのか…。
Scale-Invariant
前回話したハリスのコーナー検出の手法には、回転不変性がありました。画像が回転しても特徴が変わらないよ、というものです。チョロッとだけ、アフィン変換不変や、スケール対応する改良があるよとだけ言いましたように、基本的にはその他の変形に対して不変な特徴ではありません。
特に困るのが、画像の大きさの違いを吸収できないことでした。へんてこな変換をされた画像から同じ特徴が出てこないというのはまだ許せます。何せ、人間の目から見ても見た目が全然違うわけですから。しかし、大きさが違うだけで結果が変わってしまうなんておかしいですよね。そこで、スケールに対して不変な特徴点や特徴量という物が必要になってくるのです。
さて、スケール不変な特徴を得るには、スケールに対して不変な物を探してこなくてはいけません。いったいどんな物がスケールの変化で変わらないのでしょうか？
スケールの変化が影響しない物の例
エッジなどの方向に関する情報。何らかの値の平均値や比率（＊計算範囲の影響を考慮は必要）
スケールの変化が影響する物の例
面積 周波数 分散（標本数が変化する為）
ふむ、では方向の情報が使えそうですね。しかし、方向情報というのは基本的に回転不変性がありません。この欠点を解決する簡単な方法は周囲から方向情報を集めてきて、周辺との相対的な情報を出す方法です。
そこで問題になるのは、どのぐらいの範囲から情報を持ってくるのかと言うこと。範囲はスケール不変量ではありません。
では、どうするのか？二つのアプローチがあります。まず一つ目が気にしない。最も単純な方法では、画像の大きさで決めてしまう方法です。各特徴点に対する考察はしません。ここで吸収できなかったスケール量は学習段階や検出手法で吸収します。HOGなどはこの方向性です。もう一つが、各特徴点に対して適切な範囲を計算する方法。今回解説するSIFTはこの方向性です。
LoGとDoG
面積の変化を吸収する為には何をするのが良いのでしょうか？手っ取り早い方法は、同じ形の物が、何倍に変化したか調べれば、その倍率を使って変化を吸収できますね。そういったスケール探索にSIFTはKoenderink(The structure of images)やLindeberg(Scale-space theory: A basic tool for analysing structures at different scales)らが報告しているガウスカーネルを用いる手法を利用します。（すみません、論文は読んだことないです。）
スケール探索の為に、ガウス関数g(x,y,σ)を画像に畳み込んでどうやったら面積に関する情報が得られるのでしょうか？そこで重要なのが周波数です。前にも書きましたが、画像の周波数は画像の大きさに対して反比例して変化します。大きくなれば低周波に、小さくなれば高周波に移行します。
ガウスフィルタ（ぼかしフィルタ）をつかうと、画像から高周波が取り除かれます。周波数をどのぐらい減らすことが出来るかどうかはガウス関数のσに依存します。低周波を消そうとするほど、大きなσが必要になります。（実空間でのガウスフィルタの大きさと、周波数空間でのガウスフィルタの大きさが反比例する為です。）σが大きくなれば、必要なフィルタの面積も大きくなります。ということは、このσでなんだか面積を代用できそうです。
どのようなσを面積の代わりに用いるべきなのかを考える為に、「ぼかし度合い」というものが定義できるとしましょう。これは、ぼかしたときにどのぐらいぼけているか（もしくはぼけていないか）を表現する値です。このぼかし度合いを、σの値を順に変えながら画像をぼかして計測すると、「σ-ぼかし度合いグラフ」が出来ます。このグラフの形は、画像の大きさの違いによってσ方向の倍率が違うだけで、凹凸などの見た目は同じグラフになるはずです。なぜなら、スケールの変化に対して、画像の周波数が反比例して変化するだけなのですから。
後は、このグラフから、面積に相当するσを持ってくれば良いのです。実際は何でも良いんですが、二つの大きさの異なる画像を比較すると言うことを考えると、σーぼかし度合いグラフにおいても比較しやすい点を選ぶのが自然です。そして、グラフの中でわかりやすい点は極大極小です。したがって、極値のσを面積に相当するスケール情報としましょう。
（画像の大きさが変わっても見た目は変わらない）
では、「ぼかし度合い」はどう定義すれば良いのでしょうか？いくらか考えることは出来ますが、画像を2階微分した物を考えます。
ガウス関数にラプラス作用素を作用させるので、LoG(Laplacian of Gaussian)と呼びます。微分した結果というのは変化度合いを表します。つまり、「ぼけてない度合い」を表す値と言うことですね。本当は画像面における平均曲率辺りの話なのですが、私はそんな概念よりも「ぼけてない度合い」と考える方が分かりやすいと思います。（詳しい人が読んだときに文句言われない為の回避(-_-) ）画像処理を勉強してて平均曲率がうんぬんという説明が出てきたら、「なんかの変化量」ぐらいに受け取っておけば問題ないですよ。（幾何を扱ってる場合を除く）
(1)
このLoGの出力をσが小さい方から順に取っていって、極大点になった値をスケール値としてあつかいます。
しかし、このLoGには問題があります。何か数学的な問題があるわけではないのですが、xy方向にフィルタを分解できないLoGは計算コストが高いです。かなり前に拡大縮小の話をしたときに、フィルタを分解できるか出来ないかでO(N2)とO(N)の計算コスト差がでると話をしました。あまり、LoGを計算したくないですね。そこで、以下の式を利用します。
こんなのどうやってうまいこと見つけてきたのか知りませんが、(x,y)方向に微分するのではなく、σ方向に微分をすることでLoGを出すことが出来ます。実際にσ方向に微分することは出来ませんので、ガウスカーネルを畳み込んだ画像の差分で近似します。
(2)
(2)式の左辺をDoG（Difference of Gaussian)と呼び、これをLoGの代わりに使います。DoGは単なるガウス関数なので、xy方向にフィルタを分解でき、計算が高速です。DoGとLoGの関係は
です。
DoG計算方法
なんかもー私が書きたかったことはLoGとDoG背景までなんで、後は正直面倒くさいんだけど。（日本語でわかりやすく解説してくれてるのってないんだよね。東工大の長橋教授が画像解析論で使ってるPDFがあるけど、めっちゃ読みにくいよ、あれ。なお、ここで公開されているプログラムは一部バグあったけど一読の価値あり。）
じゃーもー、後は適当で。こまけぇこたぁ、他のサイトや長橋教授のPDFを読んでよ。（投げやり）まぁ、HPを作るまでにゆっくり情報追加していくかな。
で、いくらDoGが分解できて高速と言っても、σが大きくなってくると、フィルタサイズが大きくなって遅くなってきます。それを何とかしようと言うことで、あるσから2倍の大きさまでσが大きくなったら、画像を半分に縮小します。周波数は画像が半分に縮小されると2倍に広がるので、ローパスに必要なσの値は半分ですむわけです。（TODO：処理のイメージはHP作るまでには作るよ！）
趣味で実装する程度で、実行速度を気にしてないならやらなくても問題ないってこっちゃ！
候補点を得る
候補点とスケールの探し方についてです。まず、先にも述べたように、候補となるスケールは極大もしくは極小となるσになります。前後のDoG画像の同じ位置と比較して値が極大、極小なら候補になります。ただ、2pxしか見ないのはさすがに視野が狭いので、3×3×3近傍を見て、極大か極小かを判断します。
（赤が現在注目している位置とスケール。水色が比較を行うデータ）
ただし、そのような点とスケールを見つけたと言っても、DoG値があまりに小さかったらほとんど信用性ありません。それ、ノイズの影響の可能性大ですよ。なので適当な閾値以下のDoG値の候補は無視します。
それでも、候補点ってのは多い物なので、さらに減らす為にもエッジ上の点は候補から削除します。前回のコーナー検出の時も話しましたが、輪郭上で重要なのは頂点で、ただのエッジはそこまで重要ではありません。ノイズの影響もありますし。
で、どうやってエッジか、エッジでないかを判断するかです。これも前回話したハリスのコーナー検出で実は説明しちゃってて、主曲率で判断できます。前回、主曲率の一方が大きく、一方が小さいのはコーナーを含まないって書きました。これを使います。つまり、二つの主曲率の比率が一定以上よりも大きかったらエッジと判断するのです。
今回の主曲率の出し方は、前回のよくわからんやり方と違ってDoG画像から作るヘッセ行列Hから求めます。ヘッセ行列の固有値は主曲率（の近似）になります。でも、やっぱ固有値求めるのは嫌なので、行列式とTraceから間接的に求めます。二つの固有値の内、大きい方の固有値をα、小さい方をβとすると、1以上の比率γを用いてα=γβと表せますから
となります。よって、を求めることで固有値を求めなくても、閾値として代用することが出来るわけですね。
回転不変性
疲れたのでそのうち書き足す。
