著者

香川 椋平 和田 俊和

雑誌

研究報告コンピュータビジョンとイメージメディア(CVIM) (ISSN:21888701)

巻号頁・発行日

vol.2016-CVIM-203, no.24, pp.1-6, 2016-08-29

---

最近傍探索は,類似画像検索や,BoF 特徴ベクトルの生成,画像間の特徴の対応付けなど,多岐にわたって用いられている.手法としては Hash 型,木探索型,森探索,グラフ探索,など様々な手法があり,問題としては,1- 最近傍探索,k- 最近傍探索,Radius 探索,などがある.近年では格納データの分布の次元が上昇することによって探索速度が低下するという問題を回避するために,近似最近傍探索がよく使われている.これに対し,本稿では,クエリ側の分布を利用した検索の高速化問題を提案する.これを 「学習型最近傍探索問題」 と呼ぶことにする.この分布は逐次与えられるクエリ自身から学習することもできるため,近似最近傍探索と近似のない最近傍探索を並列動作させればオンライン学習もできる.本稿では,その一歩として,クエリに基づいて k-d tree を再構築し,木探索のみで最近傍探索を行う高速化手法を提案する.学習した k-d tree を用いた最近傍探索時間と精度の比較を行い,その活用法を論じる.