距離計算を行わない最近傍探索アルゴリズム : Grafting Trees(テーマセッション,大規模データベースとパターン認識)
スポンサーリンク
概要
- 論文の詳細を見る
本報告では、K-D木を用いた最近傍探索アルゴリズムにおけるPriority Searchを識別問題としてとらえ、距離計算を行わない最近傍探索アルゴリズムを提案する。K-D木を用いた最近傍探索では、1)木探索によって暫定最近傍解を求め、2)A*アルゴリズムによる真の最近傍の探索が行われる。このうち、2)のA*アルゴリズムによる最近傍の探索に処理時間の大半が費やされてしまう。この傾向は、格納されているデータ分布の次元数が上昇するにつれて顕著になる。本報告では、木探索でたどり着いた葉ノードに対応する空間のBOX分割を考え、そのBOX内のどこにクエリが存在するかにより、Pnority Searchで見つかる最近傍は決まっていることに着目し、BOX毎に識別器を用意して、距離計算なしで最近傍探索を行う方法を提案する。具体的には、K-D木の葉の部分に決定木を継ぎ足したGrafting Treesというデータ構造を用いた最近傍探索アルゴリズムを提案する。Grafting Treesでは、データ分布の次元数が上昇するにつれて決定木の構造が深くなってしまうという問題が起きるため、登録したデータを母点とするVoronoi境界付近では、木探索の代わりに距離計算を行うHybrid Grafting Treesについても提案する。実験では、D. MountらのANNライブラリとGrafting Treesの速度比較を行い、ANNよりも高速であることを示す。
- 2013-02-14
著者
関連論文
- 文書表裏面スキャン画像の輝度値分布変換による裏写り除去法 (ヒューマン情報処理)
- B+木を用いた補助記憶装置上での近似最近傍探索(テーマ関連セッション6,コンピュータビジョンとパターン認識のための学習理論)
- B+木を用いた補助記憶装置上での近似最近傍探索(テーマ関連セッション6)
- 劣化の影響を受けにくい画像間相違度に関する研究 (情報論的学習理論と機械学習)
- 第10回コンピュータビジョン国際会議ICCV2005報告(会議報告)
- 第10回コンピュータビジョン国際会議ICCV2005報告(会議参加報告,CVのためのパターン認識・学習理論の新展開)
- 一般分布に対するPrincipal Component Hashing(一般セッション11)
- 一般分布に対するPrincipal Component Hashing(一般セッション4,三次元画像,多視点画像)
- 自己参照に基づくパターン欠陥検査法(一般セッション7,コンピュータビジョンとパターン認識のための学習理論)
- 自己参照に基づくパターン欠陥検査法(一般セッション7)
- 誤差による変動幅を考慮した決定木に関する研究(テーマ関連セッション6,コンピュータビジョンとパターン認識のための学習理論)
- 誤差による変動幅を考慮した決定木に関する研究(テーマ関連セッション6)
- 複数カメラを用いたCONDENSATIONのための隠れに対して頑健な重み統合法
- データベースに基づくサーバサイド迷惑メール検出システム(セキュリティ技術, インターネットアーキテクチャ技術論文)
- 飽和画像からの色復元 : 1,2色飽和の場合(一般セッション1,コンピュータビジョンとパターン認識のための学習理論)
- 2次元主成分分析を用いたMahalanobis距離最小化による高次元線形写像計算法:2D-M3(テーマ関連セッション5,コンピュータビジョンとパターン認識のための学習理論)
- 線形弁別特徴変換に関する研究(テーマ関連セッション5,コンピュータビジョンとパターン認識のための学習理論)
- 飽和画像からの色復元 : 1,2色飽和の場合(一般セッション1)
- 2次元主成分分析を用いたMahalanobis距離最小化による高次元線形写像計算法:2D-M3(テーマ関連セッション5)
- 動的色境界の提案と道路標識追跡・認識への応用(一般セッション8)
- 動的色境界の提案と道路標識追跡・認識への応用(一般セッション3,三次元画像,多視点画像)
- 事例を用いた弁別性マップの構築とその応用 : 弁別性マップを用いたステレオトラッキング(一般セッション1)
- 空間分割を用いた識別と非線形写像の学習 : (2)データ空間の再帰的分割に基づく非線形写像学習 : 回帰木の今昔
- 非線形写像学習のための PaLM-Tree の提案
- 情報量基準に基づく区分的関数あてはめによる写像学習(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 識別器選択のための入力空間分割法に関する検討(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 回帰木を用いた非線形写像の学習と識別問題への応用(テーマ関連/オーガナイズドセッション(2))
- 回帰木を用いた非線形写像の学習と識別問題への応用(オーガナイズドセッション(2))(CVのためのパターン認識・学習理論の新展開)
- ステレオカメラによる色ターゲットの3次元位置計測(卒論セッション)
- ロボットの身体と環境との相互作用に基づく地図作成法(卒論セッション)
- 高次元空間における近似最近傍探索技術の進歩とその展望(大規模画像データ処理)
- 特集「大規模画像データ処理」にあたって
- 一般分布に対するPrincipal Component Hashing(一般セッション4,三次元画像,多視点画像)
- 線形弁別特徴変換に関する研究(テーマ関連セッション5)
- 装着型カメラを用いた頭部位置・姿勢の計測法
- 劣化の影響を受けにくい画像間相違度に関する研究
- ユーザの選好を反映した特徴変換(一般,顔・人物・ジェスチャ・行動)
- 文書表裏面スキャン画像の輝度値分布変換による裏写り除去法(一般,顔・人物・ジェスチャ・行動)
- 文書表裏面スキャン画像の輝度値分布変換による裏写り除去法(一般,顔・人物・ジェスチャ・行動)
- 劣化の影響を受けにくい画像間相違度に関する研究(一般,顔・人物・ジェスチャ・行動)
- 劣化の影響を受けにくい画像間相違度に関する研究(一般,顔・人物・ジェスチャ・行動)
- 劣化の影響を受けにくい画像間相違度に関する研究 (パターン認識・メディア理解)
- Mahalanobis距離最小化による高次元線形写像計算法:M3(パターン認識と学習,第12回画像の認識・理解シンポジウム推薦論文,画像の認識・理解論文)
- SIFT特徴量の拡張と対称性平面物体検出への応用(幾何学的解析,第12回画像の認識・理解シンポジウム推薦論文,画像の認識・理解論文)
- 対称SIFT特徴量を用いた対称性平面物体検出(一般セッション4)
- 対称SIFT特徴量を用いた対称性平面物体検出(一般セッション4,CV/PR技術のVRへの応用)
- ユーザの選好を反映した特徴変換(一般,顔・人物・ジェスチャ・行動)
- マスメイルデータベースとそれを用いたマスメイル検出システム
- 動的色境界の提案と道路標識追跡・認識への応用(一般セッション3,三次元画像,多視点画像)
- Chamfer Matchingを利用した有向NFTGとその応用(テーマ関連セッション3)
- Chamfer Matchihgを利用した有向NFTGとその応用(テーマセッション(3),CVのためのパターン認識・学習理論の新展開)
- 離散最適化によるDenoisingのFPGA上での実時間実装法(一般,顔・人物・ジェスチャ・行動)
- 離散最適化によるDenoisingのFPGA上での実時間実装法(一般,顔・人物・ジェスチャ・行動)
- コンテンツに基づくマスメイルフィルタリング(光ネットワーク構成技術,インターネット関連技術,及び一般)
- コンテンツに基づくマスメイルフィルタリング(光ネットワーク構成技術,インターネット関連技術,及び一般)
- コンテンツに基づくマスメイルフィルタリング(光ネットワーク構成技術,インターネット関連技術,及び一般)
- ステレオカメラを用いた顔検出の高速化(一般セッション3)
- ステレオカメラを用いた顔検出の高速化(一般セッション3,CV/PR技術のVRへの応用)
- 特集「安心・安全のためのCV」の発行に寄せて(安心・安全のためのCV)
- 特集「安心・安全のためのCV」の発行に寄せて
- 二分探索型Belief Propagationの多次元拡張による領域分割
- Whiteningと線形予測を用いた人為的操作を伴うプラントの異常検出(一般,顔・人物・ジェスチャ・行動)
- FPGAを用いたSURFの実時間計算法(一般,顔・人物・ジェスチャ・行動)
- Whiteningと線形予測を用いた人為的操作を伴うプラントの異常検出(一般,顔・人物・ジェスチャ・行動)
- FPGAを用いたSURFの実時間計算法(一般,顔・人物・ジェスチャ・行動)
- Gaussian Processesを用いたプラントの異常及びその予兆の検出 (マルチメディア・仮想環境基礎)
- Gaussian Processesを用いたプラントの異常及びその予兆の検出 (パターン認識・メディア理解)
- 背景変化の共起性に基づく背景差分
- 複数カメラを用いたCONDENSATIONによる複数人物頭部の実時間検出・追跡(一般セッション11)
- 複数カメラを用いたCONDENSATIONによる複数人物頭部の実時間検出・追跡(一般セッション(5),CVのためのパターン認識・学習理論の新展開)
- 制約付きEMアルゴリズムによる対象個数推定(一般セッション5)
- 制約付きEMアルゴリズムによる対象個数推定(一般セッション5,CV/PR技術のVRへの応用)
- インテグラルイメージを用いた主成分木による画像の最近傍探索の高速化(一般セッション(3),ユビキタス情報社会と複合現実感のためのパターン認識・メディア理解)
- インテグラルイメージを用いた主成分木による画像の最近傍探索の高速化
- 自動視線推定のためのアイモデルの個人適応法(一般セッション(2),ユビキタス情報社会と複合現実感のためのパターン認識・メディア理解)
- 連続特徴空間における決定木構築法と顔検出への応用(テーマ関連セッション4)
- 事例ベース対象追跡・認識のための近さ優先探索グラフの対話的構築アルゴリズム(テーマ関連セッション3)
- 効率的な距離計算戦略による高次元最近傍探索の高速化(テーマ関連セッション2)
- 空間分割と直交変換の統合による高次元最近傍探索の高速化(テーマ関連セッション2)
- 連続特徴空間における決定木構築法と顔検出への応用(テーマセッション(4)CVのためのパターン認識・学習理論の新展開)
- 事例ベース対象追跡・認識のための近さ優先探索グラフの対話的構築アルゴリズム(テーマセッション(3),CVのためのパターン認識・学習理論の新展開)
- 効率的な距離計算戦略による高次元最近傍探索の高速化(テーマセッション(2),CVのためのパターン認識・学習理論の新展開)
- 空間分割と直交変換の統合による高次元最近傍探索の高速化(テーマセッション(2),CVのためのパターン認識・学習理論の新展開)
- ハッシュを用いた最大類似度探索法に関する研究(一般セッション6)
- ハッシュを用いた最大類似度探索法に関する研究(一般セッション6,CV/PR技術のVRへの応用)
- 特集「CVにおけるパターン認識・学習理論の新展開」の発行に寄せて(CVにおけるパターン認識・学習理論の新展開)
- 最近傍探索・識別技術と画像理解(機械学習による自然言語処理・言語処理を利用したメディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 最近傍探索・識別技術と画像理解(機械学習による自然言語処理・言語処理を利用したメディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 4分木表現を用いた画像の高速最近傍識別(卒論セッション)
- 画像の4分木表現に対する最近傍識別(PRMU&NCテーマセッション(1) : 認識と学習)(認識と学習,模倣学習)
- 画像の4分木表現に対する最近傍識別(PRMU&NCテーマセッション(1) : 認識と学習)(認識と学習,模倣学習)
- 色競合における適応的事例収集法(卒論セッション)
- オプティカルフローの無相関化によるエゴモーション解析(一般セッション1)
- オプティカルフローの無相関化によるエゴモーション解析(一般セッション(1),CVのためのパターン認識・学習理論の新展開)
- K-D Decision Treeとその応用 : 最近傍識別器の高速化と省メモリ化(パターン認識基礎, 画像の認識・理解論文)
- 最近傍識別器を用いた背景差分と色検出の統合(一般セッション(2))
- K-D Decision Tree最近傍識別器の高速化(テーマセッション(3))(データマイニングとパターン認識・メディア理解)
- 回帰木を用いた識別器のモールディングによる文字認識の高速化(一般セッション,パターン認識とメディア理解のフロンティアとグランドチャレンジ)
- 情報量基準に基づく区分的関数あてはめによる写像学習(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
- 識別器選択のための入力空間分割法に関する検討(学習理論とパターン認識メディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)