*kd-tree とは 　多次元空間を分割して作るデータ構造で，類似するデータを高速に探索したいときに利用されます．コンピュータビジョンに限らず，データの探索を行う様々な場面に適応できます． {{small:wikipedia [link:https://ja.wikipedia.org/wiki/Kd木] }} *サンプルコード (C++) ライブラリ：[link:simplesp] サンプルコード：simplesp/sample/sp/kdtree ２次元の点群を対象とした最近傍探索を，全探索とkd-treeのそれぞれの方法で計算します． *問題設定 　N次元のデータ群に対して，指定したデータの最近傍(nearest neighbour)を探索したいとします．図１は２次元の点群に対して，指定した点（赤点）の最近傍の点を探索した結果を表します． [img:qrzv] {{small:図１ ２次元の点の最近傍探索}} 　もっとも簡単な探索方法は，全ての点と比較して最も距離の近い点を探す方法です．この方法は全探索，或いは力任せ探索(brute force search)と呼ばれています．図１の例では，１０点候補があるので，距離の計算も１０回行う必要があります．点群の数が少ない条件や，最近傍探索を実施する点（赤点）が少ない条件では，この方法でもさほど計算コストはかかりません． 　しかし，点群の数が多く，最近傍探索を実施する点（赤点）も多い場合，計算コストは非常に大きくなります．kd-treeでは，２分木のデータ構造を利用した効果的な探索を行うことで，この計算コストを抑えることができます． 　 *アルゴリズム 　ここでは，kd-treeのアルゴリズムについて説明します．まず，kd-tree では，元々の点群を2分木の構造に変換します．2分木は点群を2つに分けるような構造で，もっとも簡単な例を図２に示します． [img:dzs5] {{small:図２}} 　図２では，ある閾値{$t$}に基づいて点群をクラス０とクラス１に分割しています．このように分けておくと，指定した点が閾値{$t$}より大きいか小さいかを見てクラスを選ぶことで，探索候補の点数を大幅に減らすことができます．ここで，閾値{$t$}の設定は，用途にもよるのですができるだけ均等な点数で分割できた方が都合が良いです．偏りが大きいと，探索候補の点数を減らすことができる期待値が悪くなります．とは言え，理想的な閾値を選ぶのにも計算コストはかかるので，ランダムや簡単な計算だけで選ぶ場合も多いようです． [img:k1yv] {{small:図３}} 　点群の数が多いと１回の分割だけでは，探索候補を十分減らすことができないので，図３に示す様に，段階的に分割を行います．なお，探索の効率を上げるため，分割の段階ごとに分ける次元の軸を変える方法が一般的です．