ハミング距離
ハミング距離とは、桁数が同じ2つの2進数を比較して、異なっている桁の個数として定義される。例えば、1111111と1010101とのハミング距離は3である。
別の言い方をすれば、ハミング距離はある文字列を別の文字列に変形する際に必要な置換回数を計測したものである。1ビットのエラーが起こるということは、n次元2進空間の中で2進数の位置が距離＝1だけ動くということに相当する。
画像解析において、特徴量がバイナリコードで表されるような特徴点同士の類似度は、ハミング距離によって計算できる。ハミング距離は、他の距離（角度やサイズを特徴量としたときの類似度計算：コサイン距離，ベクトル間角度，ユークリッド距離など）に比べてメモリ効率が良く、最近傍探索の速度も向上できるという利点がある。
https://www.denso.co.jp/ja/aboutdenso/technology/dtr/v18/files/11.pdf
http://news.mynavi.jp/column/architecture/262/
決定木
決定木とは、木構造をした決定を行うためのグラフのこと。
節点と枝、端点の葉への経路によって表される。
決定木は「質問」を繰り返すことでそのデータがどのグループに属するかを決定するものであり、よい決定木とは、答えによってデータがよく分類されるものと言うことができる。反対にデータの分類が最終的に半々になってしまうような決定木は、悪い決定木と言える。
与えられたデータから適切な決定木を作成することを「決定木の学習」という。
http://www.sist.ac.jp/~kanakubo/research/reasoning_kr/decision_tree.html
FAST（Features from Accelerated Segment Test）
画像中のコーナーを高速に検出する方法として提案された。
注目画素pの周辺の円周上の決まった16画素を観測し、輝度がしきい値以上のピクセルが連続してn個以上になる点を特徴点とする。ここで全ての画素を調べるのには時間がかかるので、円周上の画素から観測する画素を選び、次に参照する画素を選択して輝度を比較していく「決定木」を構成して、コーナーであることを「学習」させていく。
コーナー検出の高速化のために決定木アルゴリズムを用いている。決定木アルゴリズムでは、コーナー画像と非コーナー画像を入力し、次に参照する画素を2段目、その次に参照する画素を3段目におく。それぞれ輝度値の比較結果によって「brighter」「similar」「darker」の3本の枝があり、末端ノードにおいてコーナーか非コーナーかを判定する。判定でYESとなった場合、末端に至る経路は「YES」になる経路として重みが加算される。
（円周上の画素をどのような順番で観測していくのだろうか？決定木の良し悪しは観測の順番にも左右されるように思われる。）
SURF（Speeded Up Robust Features）
SIFTによる特徴量抽出アプローチの改良版。精度はSIFTに劣るが高速マッチングが可能。
スケール・回転不変な特徴点検出方法として、SIFTやSURFがある。SIFTはDoG画像生成や勾配ヒストグラム生成の計算コストが高く、SURFは積分画像を利用することにより10倍の高速化を実現した。
SURFでは曲率が極大値をとる点を抽出するために、Gaussianの2階微分Lxx, Lyy, Lxyから構成されるヘッセ行列の行列式det(H)を計算した。しかし、ガウシアンの2次微分は計算コストが高い。
なのでこれをBOXフィルタにより近似する。
Hessian Detector⇒Fast-Hessian Detector
実際の計算では上記のフィルタをかけた上で足し合わせるわけだが、それを全画素について実行するのは計算回数が大きくなってしまうので、積分画像を用いる。
積分画像は、例えば点(x,y)における画素値を(0,0)から(x,y)を囲む矩形内の画素値の和とするものである。これを計算しておくと、画像内の任意の矩形の画素値の和を求めるときに、4回程度の和と差のみで表すことができ、高速に計算ができるため利用できる。
またSURFではGaussianフィルタのサイズを徐々に大きくしていくが、それに伴い処理時間も増えてしまう。しかし積分画像を用いると、矩形サイズによらず定数時間で積分値を求めることができるため高速になる。
SIFT（Scale-Invariant Feature Transform）
SIFTは、スケール不変性・回転不変性・ノイズおよび照明変化への不変性をもつ特徴点および特徴量検出方法である。
LoGオペレータ
SIFTを説明するために、まずLoGオペレータを紹介する。
前回のHarrisコーナー検出法は、コーナー部分のみしか注目しないため、それがどの程度の大きさをもつのかが分からず、スケール不変性がなかった。コーナーがどのような大きさをもつか、という適当な「スケール値」を求める方法のひとつが、以下に示すLoGオペレータを用いる方法である。
LoGオペレータは、Gussianのxおよびyに関する2階微分を足し合わせたもの（ラプラシアン：Ixx + Iyy）で、その関数型を見ると中心にピークがあり、その周辺で一度凹んだ関数型になっている。画像に対してLoGオペレータをかけると、エッジが輝度値の大きい（または小さい）部分として検出できる。ただしこのままでは、ノイズを拾いやすい・エッジとの区別がつかない、という問題点があり、後述するようにコントラストや主曲率による特徴点の絞込みをSIFTでは行っている。
コーナーのスケール情報を得る方法のひとつに、Gaussianの分散値σを変化させてLoGオペレータをかけた画像同士の差分をとる方法がある。σを徐々に変化させて差分をとると、あるσでLoGオペレータの計算結果が極大値をとる場合がある。これは画像を分散値σの程度でぼかしたときに「見えなく」なってしまうコーナーがあると解釈でき、「σのスケール値をもつ特徴量」としてスケール情報を抽出できる。
DoGオペレータ
LoGは計算コストがかかるという問題がある。それはexpに含まれるx^2+y^2を計算するため、xとyを独立に計算できないためである。そのため、それを解消したDoG（Difference-of-Gaussian）オペレータが提案された。
DoGはGaussianのラプラシアンを計算する代わりに、分散値σを変えたときの差分画像を計算する。拡散方程式によってラプラシアンがσの微分で近似できることが示せ、差分画像の輝度分布から高速に特徴点を検出することができる。
ヘッセ行列
SIFTはこのDoGの極大値として特徴点を求めているが、この方法ではDoG値が小さい点や、エッジとコーナーとの区別できないため、SIFTではさらに主曲率による絞込みを行う。曲率は輝度の変位に関する2階微分で表されるが、それを2次元平面の曲率に一般化したものがヘッセ行列（Hessian）である。
ヘッセ行列の固有値をλ1, λ2とすると、画像上のエッジはλ1が大きくλ2が小さい点として検出され、コーナーはλ1とλ2がともに大きくなる点として検出される。このような点を求める方法としてHarrisオペレータと同様のものを考えると、Tr(H)^2/det(H)を計算してこれが大きい点を抽出することでコーナーを検出できる。第1固有値と第2固有値の比率をγとしてλ1=γλ2とすると、γがしきい値よりも大きい点を特徴点の候補として絞り込む。
また2階微分の極大値を求めるときに、3次元パラボラ（放物面）フィッティングを行い頂点をサブピクセル精度で求めて精度を上げている。
DoG出力値が小さい場合、ノイズの影響を受けやすいため特徴点候補から削除する。DoG値はコントラストが低い領域では小さくなるため、このような点を削除する。
オリエンテーションを求めて規格化
さらに検出された特徴点を比較する要素である特徴量のひとつとして、オリエンテーションを求める。オリエンテーションは特徴点における方向を表し、求められたオリエンテーションで向きの正規化を行うことで、回転不変な特徴量を計算することができる。
オリエンテーションの計算方法は、以下のようになっている
- まず各画素においてHaar型フィルタ（x方向とy方向の1階微分を計算）を用いて、比率または差の自乗和から「勾配方向θ」と「勾配強度m(u,v)」を求める
- 勾配方向は輝度勾配の大きくなる方向をヒストグラムのしきい値以上の点として求め、それが複数ある場合は複数の方向を勾配方向として割り当てる
