最近傍探索（Nearest Neighbor Search）
ということで，なんだかんだ会社設立やその他もろもろが思った以上に大変で，，，ちょっと止まってたんですが，ひとまず小休止に入ったので引き続き SFM をやりたいと思います！
X. 最近傍探索とは．
まず，最近傍探索とは何ぞや？って話なんですが，Wikipedia の定義を見ると，
「距離空間における最も近い点を探す最適化問題の一種」
とあります．「距離空間」には「マンハッタン距離」とか「ユークリッド距離」とかいろいろとありますが，ここでは簡単のために「ユークリッド距離」前提としてエントリを進めていきます．で，これだけ見ても意味わからないので，まず簡単に一次元の例を考えてみたいと思います．
Brute Force Macher １次元データの最近傍探索
この問題は，「クエリ点（=4.2）にもっとも近い値を探索対象の中から探す．」ということになりますが，上記は力任せ方による解法です．このやり方だとクエリ点と探索対象点のすべての距離を計算して，距離が最も近いものを選択するという流れになります．このやり方では，比較対象点がn個存在する場合，探索回数が O(n) になります．なので，比較対象点が１億点あるときは1億回の比較が必要になります．
Binary Treeによる１次元データの最近傍探索
次に，Binary Tree を用いた最近傍探索になります．力任せ探索とは異なり，比較対象点が n 個存在する場合，探索回数が O(log n) のオーダになります．実際には数値のばらつき具合によりますが，うまく行けば比較対象点が１億点あるときは，約27回程度の比較になります．めちゃ減りましたね．上図では，ツリーの葉ノードが探索対象を表しており，四角のノードが分岐のための閾値を表しています．閾値は単純に当該ノード以下の探索対象の平均値を用いています．
で，今回のエントリでは，「点が１次元じゃなくて，高次元のユークリッド空間にある場合はどうやって探索すんの？」という話になります．高次元になったときでも力任せ探索は有効で，クエリ点に対して一番近い点を確実に見つけてくれます．ただ，時間がかかります．一方で， Binary Tree を高次元に適用しようとすると，ちょっと工夫が必要そうです．
X. SFMの処理フローと計算コスト．
で，過去に書いた SFM エントリのちょっとしたおさらいになるんですが，細かな処理を除くと SFM の大きな処理フローとは下記になります．
１．各写真から特徴点の抽出．
２．視点が似ている（＝同じようなものが被写体になっている）写真のペアを見つける．
【探索コスト大】全ての写真ペアを比較し，視点が似ているかチェック．
３．見つけた写真のペアに紐づく特徴点をマッチング．
【探索コスト大】ペアの全ての特徴点を比較して，最近傍ペアを推定する．
４．カメラの位置と点群を推定する．
で，２と３のところで探索の話が出てきます．２では写真ペア，３では特徴点ペアということで，ちょっと探索の内容は異なりますが，SFMの復元対象物体が大きくなるほどこの２と３にかかるコストが大きくなっていきます．奈良の大仏とかその位のスケールの構造物でも写真の枚数がある程度大きくなるはずなので，２と３を工夫しないと計算量が爆発します．今回のエントリでは，３の特徴点探索の話をします．
※ちなみに那覇の国際通りは1.6キロあるので，２と３を工夫するだけだとまだ不十分で，Hybrid SfM か，写真の時系列順序を使う方法を試したいと思ってます．
X. SIFTを用いた場合の SFM の特徴点マッチング．
今回は特徴点に SIFT を使おうと思っていますが， SIFT では画像中で見つかったキーポイントに一つづつに識別子（Descriptor）が付随しています．
つまり，生成したキーポイントの比較に識別子を使うことになるのですが，この識別子は上図にあるように128個のビンを持つヒストグラムになっています．つまり，「128次元のユークリッド空間内に存在する点の最近傍探索」になります．
X. 今回解剖した３つの手法．
一つ一つのエントリがそこそこの分量になりそうだったので，別のポストにします！書き終わったら順次リンクを貼っていきます．
Brute Force Matching
エントリを書き終わったらリンクしますm(_ _;)m
KD Tree Search
エントリを書き終わったらリンクしますm(_ _;)m
Cascade Hashing for 3D Search
エントリを書き終わったらリンクしますm(_ _;)m
X. ３つの手法による最近傍探索の計算時間．
計算時間を全く考慮に入れなければ Brute Force Matching で良いのですが，そういうわけにもいかないので，計算時間とマッチング精度のトレードオフを取ることになります．で，今回は実験を簡単にするために，同じ画像から抽出したキーポイントと識別子を比較しました．ただ，比較対象となる特徴点セットの中に必ず完全一致する特徴点が見つかります．これでは実際に SFM において使う用途と状況が異なってしまうので，探索対象データに少しずつノイズを混ぜていって，探索時間や精度がどう変化するか見てみました．
実験に用いた画像
取得できた特徴点数：2674
σ = 0 の場合の探索精度と時間
Brute Force Matcher ー＞ 処理時間：1.45s, 正解率：1.0
KDTree Matcher ー＞ 処理時間：0.0062s, 正解率：1.0
Cascading Hasher ー＞ 処理時間：0.129s, 正解率：1.0
σ = 4 の場合の探索精度と時間
Brute Force Matcher ー＞ 処理時間：1.45s, 正解率：1.0
KDTree Matcher ー＞ 処理時間：0.0062s, 正解率：0.9996
Cascading Hasher ー＞ 処理時間：0.129s, 正解率：0.9996
σ = 32 の場合の探索精度と時間
Brute Force Matcher ー＞ 処理時間：1.44s, 正解率：0.99
KDTree Matcher ー＞ 処理時間：0.0252s, 正解率：0.75
Cascading Hasher ー＞ 処理時間：0.1104s, 正解率：0.48
ということで，「ノイズが大きくなれば，KDTree Matcher の探索時間が大きくなり，Cascading Hasherのほうが性能がよくなります！！！」という結論に持って行きたかったんですが，どうやらそうならず（笑）ここはちょっと自分の理解不足な部分があるかもしれませんが，KDTree Matcher の性能が一番よい結果になりました．ただし，あくまでも同じ画像から生成した特徴点を比較しているので，この前提を変更するとひょっとすると結果が変わるかもしれません．
X. 実験に使ったコード
git clone して，下記のコマンドを実行すると上のテストが動きます．
sh build.sh ./build/nearest_neighbor_perf_test
X. 参考文献
KD-Trees に関連する論文．
An algorithm for Finding Best Matches in Logarithmic Expected Time.
Shape Indexing Using Approximate Nearest-Neighbor Search in High-Dimensional Spaces.
FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION.
Optimized KD-trees for fast image descriptor matching.
