| 講演名 | 2006-03-16 効率的な距離計算戦略による高次元最近傍探索の高速化(テーマセッション(2),CVのためのパターン認識・学習理論の新展開) 武本 浩二, 加藤 丈和, 和田 俊和, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文では,高次元空間での最近傍探索の高速化について検討する.従来の最近傍探索の高速化手法には,最近傍候補の絞り込みと,距離計算の打ち切りとがある.前者は,高次元空間ではほとんど全探索になってしまい,後者は,次元数が高い場合でも,高速化が可能である.本手法では,さらに,より効率的な距離計算の打ち切りを行うために,基底を寄与率の順にソートする直交変換と,入力パターンとの距離を計算する最近傍候補の並び換えを行う.顔画像データベースを用いた実験では,従来手法よりも提案手法が高速であることを確認した. |
| 抄録(英) | In this paper, we propose an accelerated Nearest Neighbor (NN) search algorithm in high dimensional space. The methods proposed so far can be classified into two types: 1) NN candidate narrowing and 2) pruning of distance computation. In high dimensional space over 30D, while NN candidate narrowing becomes brute force search, the latter method, pruning of distance computation is still effective for acceleration. For realizing more efficient NN search in high dimensional space, we integrate these two methods. As well, orthogonal expansion of patterns ordered by contribution ratio is incorporated for efficient pruning, because the distance computation starting from the most contributed component provides good approximation of the true distance. We confirmed through extensive experiments that our method is faster than existing methods. |
| キーワード(和) | |
| キーワード(英) | |
| 資料番号 | PRMU2005-240 |
| 発行日 |
| 研究会情報 | |
| 研究会 | PRMU |
|---|---|
| 開催期間 | 2006/3/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Pattern Recognition and Media Understanding (PRMU) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 効率的な距離計算戦略による高次元最近傍探索の高速化(テーマセッション(2),CVのためのパターン認識・学習理論の新展開) |
| サブタイトル（和） | |
| タイトル（英） | An Accelerated High Dimensional Nearest Neighbor Search based on An Efficient Distance Computational Strategy |
| サブタイトル（和） | |
| キーワード(1)（和/英） | |
| 第 1 著者 氏名（和/英） | 武本 浩二 / Koji Takemoto |
| 第 1 著者 所属（和/英） | 和歌山大学大学院 システム工学研究科 Graduate School of System Engineering, Wakayama University |
| 第 2 著者 氏名（和/英） | 加藤 丈和 / Takekazu Kato |
| 第 2 著者 所属（和/英） | 和歌山大学大学院 システム工学研究科 Graduate School of System Engineering, Wakayama University |
| 第 3 著者 氏名（和/英） | 和田 俊和 / Toshikazu Wada |
| 第 3 著者 所属（和/英） | 和歌山大学大学院 システム工学研究科 Graduate School of System Engineering, Wakayama University |
| 発表年月日 | 2006-03-16 |
| 資料番号 | PRMU2005-240 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 673 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |