文献

J-GLOBAL ID：201302216170262961   整理番号：13A0028708

Hamming空間における高速な近似最近傍探索アルゴリズム

A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space

著者 (3件)： ESMAEILI Mani Malek (Univ. British Columbia, BC, CAN) ,  WARD Rabab Kreidieh (Univ. British Columbia, BC, CAN) ,  FATOURECHI Mehrdad (Univ. British Columbia, BC, CAN)
資料名： IEEE Transactions on Pattern Analysis and Machine Intelligence  (IEEE Transactions on Pattern Analysis and Machine Intelligence)
巻： 34  号： 12  ページ： 2481-2488  発行年： 2012年12月 
JST資料番号： B0519B  ISSN： 0162-8828  CODEN： ITPIDJ  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 著者らは以前にマルチメディア信号に対する最近傍(NN)探索のための説明的で,ロバストな特徴ベクトル(フィンガープリント)の抽出について検討した。本論文では,Hamming空間に着目してバイナリフィンガープリントに対するマッチング過程を対象に,高速で高精度なNN探索アルゴリズムを提案した。既存法として局所性鋭敏型ハッシュ(LSH)が多用され,その改良法も多く研究されているが速度と精度の双方の観点でオリジナルを上回る手法は提案されていない。また,それらは最近傍距離が大きくなると失敗する確率が増大するので,誤りのあるハッシュベクトルを考慮してLSHと比べてかなり小さく,正確な最近傍候補リストを生成する誤差重み付けハッシュ(EWH)を提案した。EWHはLSHと同様にフィンガープリントからインデックステーブルを作成する前処理を行うが,インデックステーブルから候補を検索する方法に新規性があり,大きな最近傍距離に対する探索時間を抑えて探索性能を維持できる。1000本以上の映像からなるフィンガープリントデータベースに適用したところ,LSHと同等のエラー率で最大8倍高速になった。また,約8000万画像からなるデータベースではLSHの10倍の精度で2.5倍高速であった。

シソーラス用語： *特徴抽出 ,  *最適化問題 ,  パターンマッチング ,  ハッシング ,  確率モデル ,  重みづけ ,  指紋 ,  インデクシング【計算機】 ,  探索問題 ,  性能評価 ,  映像 ,  *画像データベース ,  誤り率 ,  高速化 ,  評価試験
準シソーラス用語： *最近傍問題 ,  フィンガープリント

分類 (3件)： パターン認識  (JE07000S) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (3件)： 近似 ,  近傍探索 ,  アルゴリズム