「画像の認識･理解シンポジウム(MIRU2004)」2004 年 7 月 ËÈÁÊ 総当たり照合と同一の精度を保証する類似部分画像検索昭悟Ý 木村川西隆仁Ý 邦夫Ý 柏野 Ý 日本電信電話株式会社，ÆÌÌ コミュニケーション科学基礎研究所¸ 厚木市 ¹Ñ Ð あらまし × ØÓ¸ Û Ò × ¸ ÙÒ Ó Ý Ý º ÖÐºÒØØº Óº Ô 本稿では，膨大な数の画像の中から目的とする画像に類似する部分画像を画像から抽出した特徴間の類似度に基づいて検出する，類似部分画像検索のための基本的な枠組を提案する．高速な検索を実現するためには，ある種のインデックス構造を導入することが必要となる．しかし，上記部分画像検索においては，データベース中の各画像から膨大な量の部分領域を抽出してインデックス構造に投入する必要があるため，インデックスの保持に必要な記憶容量が膨大になるという問題点があった．提案法では，データベース中の画像について，部分領域を間引いて抽出することにより，インデックスサイズを大幅に削減する．このとき，部分領域の抽出間隔を適切に設定することにより，総当たり照合と全く同一の検索結果を理論的に保証することが可能である． ÓÒØ ÒØ¹ キーワード ËÈÁÊ × Ñ Ö ØÖ Ú Ð，部分画像検索，部分領域，マージン Ë Ñ Ð Ö ØÝ¹ × Ô ÖØ Ð Ñ Ö ØÖ Ú Ð Ù Ö ÒØ ÙÖ Ý × Ü Ù×Ø Ú Ñ Ø Ò × ØÓ ÃÁÅÍÊ Ý¸ Ì Ý ØÓ Ã Ï ÆÁËÀÁÝ ¸ Ò ÃÙÒ Ó Ã ËÀÁÆÇÝ ÆÌÌ ÓÑÑÙÒ Ø ÓÒ Ë Ò Ä ÓÖ ØÓÖ ×¸ ÆÌÌ ÓÖÔÓÖ Ø ÓÒ¸ ÅÓÖ ÒÓ× ØÓ Ï Ñ Ý ¿¹½¸ Ø×Ù ¹× ¸ Ã Ò Û ¸ ¾ ¿¹¼½ ¸ Â Ô Ò ¹Ñ Ð Ý × ØÓ¸ Û Ò × ¸ ÙÒ Ó Ý º ÖÐºÒØØº Óº Ô ×ØÖ Ø Ñ Ò × Ñ × ×ØÓÖ Ï ÔÖÓÔÓ× × ÓÒ ×Ô ÖÓÑ ÓÖ Ò Ø Û Ð Ø ÔÖ ÓÖ Ø Ã Ý ÛÓÖ × × Ò Û Ö Ñ ÛÓÖ ¬Ò Ü × Ñ ×Ø Ò Ù ØÓ Ø Ø Ð Ö ×ÙÖ º ÒÙÑ ÓÒ×Ø ÒØ ×Ô ÐÐÝ Ù Ö ÒØ Ò Ø ÓÒØ ÒØ¹ Ñ × Ñ ÓÖ ÕÙ × Ñ Ò Ò Ò ÙÖ Ø ×Ù Ñ Ô ÖØ Ð × Ñ Ð Ö Ø × Ö Ó ÔÓÖØ ÓÒ× Ó Ò º Ì ÙÖ Ò¸ Ø Ý × Ü Ö ØÖ Ú Ð¸ Ô ÖØ Ð Ñ Ö ØÖ Ú Ð Ø ÖÓÙ ÔÖÓÔÓ× Ñ ×º Ì Ò Ö ÐÐÝ Ö ÕÙ Ö × ÔÖÓÔÓ× Ñ Ø Ó Ù×Ø Ú Ñ Ø Ù Ò Ö Ñ Ø Ó ØÐÝ Ö Ù Ø ÒÙÑ Ù ÑÓÙÒØ Ó ÜØÖ Ø× ÔÓÖØ ÓÒ× ×Þ Ó Ò Ü × Ò º Ö ØÖ Ú Ð¸ Ñ Ø Ò Ö ÓÒ¸ Ñ Ö Ò の特定の物体に注目して検索を行う手法，Î ×Ù ÐË ½º まえがき Ö Ó Ã ¿ などに代表される，物体の大まかな形状や配置を与えて検索をディジタルカメラの普及，記憶媒体の低価格化・大容量化，大容量ネットワークの普及などにより，容易に大量のディジタル画像を取得し保存する環境が整ってきている．そのため，大行う方法 ¿ が知られている．さらに近年，画像の部分領域間の類似性に基づいて画像全体の類似性を判断する Ö ÔÔÖÓ が提案されている ¸ ÓÒ¹ × ．部分的な領域に注目する量の画像から所望の画像を高速に探し出す高速画像検索技術がことで，画像全体を一律に扱う手法に比べ，より頑健な画像検強く求められている．索が可能となると考えられる．このようなアプローチでは，画画像検索における主要なアプローチとして， ÓÒØ ÒØ¹ Ñ Ö ØÖ Ú Ð ´ ÁÊµ が広く用いられている． × ÁÊ では，キーワードに基づく検索とは異なり，各画像から色・物体形状・像中から部分領域を効率的に切り出す方法が重要になる．画像中から個別物体と考えられる領域を抽出することにより，取り出す部分領域を絞り込む方法が数多く提案されているが ∼ テクスチャなど自動的に取得可能な特徴を抽出し，特徴同士の，それらの多くは特定の応用に限定することによって個別物類似度に基づいて，ユーザから与えられたクエリ画像に類似す体の検出精度を高めており，汎用目的には必ずしも十分な精度 ÁÊ の代表的な例を与えてはいない．多様な検索要求に対応するためには，物体 Ø ¾ になど代表される，画像中抽出を陽に行わず，画像中の任意の部分領域での照合結果を統る画像を画像データベースから検出する．としては，É Á ½ や ÜË Ⅱ－400 database D mx matching window W query Q Di wx my qy margin=1 wy qx images extracting extracting indexes query image images creating image database pruning features f Q(W ) features f D(W ) 図½ 部分画像検索 re-matching results 図¾ 合することによって，画像の類似性を検出する手法がより有効 ËÈÁÊ の概要であると考えられる．しかし，このようなアプローチでは，各 ´ µ ´Ü 画像から膨大な量の部分領域を抽出しなければならない．その Ý µ を抽出する．ブロックは縦横 ½ ピクセルずつずため，照合計算が膨大になるだけでなく，インデックスの保持らしながら抽出される．ブロック特徴として，様々な種類の特に必要な記憶容量が膨大になるという問題点も生じる．徴を用いることができ，例えば，そこで，本稿では，Ö ÓÒ¹ × ÔÔÖÓ ÁÊ 実による現のための要素技術として，膨大な数の画像 ´データベースµ Ì， Ì，ウェーブレット，色ヒストグラムなどを用いることができる．次に，大きさが Û Ü ¢ Û Ý ピクセルの照合窓 ´Ï µ ´Ü Ý Ï を各画像に配置し，照合の中から目的とする画像 ´クエリµ と類似する部分画像を検索窓から部分領域する基本的な枠組 ËÈÁÊ ら切り出した部分領域を照合領域と呼ぶ．照合窓は，あらゆる ´ËÔ Ö× ¹ Ò Ü¹ × È ÖØ Ð ÁÑ Ê ØÖ Ú Ðµ を提案する ´図 ½µ．すなわち，ËÈÁÊ のタスクは， É との距離が予め定められた閾値である検索閾値を ´Ü Ý µ を，データベース下回る部分画像 ½ の中クエリ Å から検出することである ´式 ´½µµ． ´ Ü Ý µ Éµ ここで，位置 ´ ´ 全ての箇所に配置されることはなく，縦方向に Ñ 横方向に Ñ Ñ ´ Ý Ü ピクセル，ピクセルの間隔で配置される．照合窓の配置間隔 Ü ´Ï µ ´Ü Ý µ を取り出す．照合特徴は，照合領域内にブロックを重複も隙間もなく配置して抽出し ´½µ Ü Ýµ は，データベース中のある画像 Ñ Ý µ を，以下，マージンと呼ぶ．続いて，照合領域に対応する特徴である照合特徴 ´ µ を切り出す．以下，照合窓かたブロック特徴の集合体である．簡単のため，照合領域の大きにおいて， Ü Ýµ にある部分画像を指す．本稿で提案する ËÈÁÊ Û Û さ´ Ü Ýµ は，ブロックの大きさ ´ Ü Ýµ の倍数であるとする．のそして，検索を高速に実行するために，各照合特徴に対してイ基本的なアイディアは，時系列信号の高速照合検索法であるンデキシングを行う．特徴同様，様々な種類のインデックス構 Ù ÐÅ Ø ½¼ 及び Ò Ö ÐÅ Ø ½½ のインデキシング手法造を用いることができ，例えば，Ê£ ¹ØÖ ½¾ や ËÊ¹ÌÖ ½¿ を ¾ 次元 ´画像信号µ に拡張したものである．すなわち，デーなどの空間インデックス手法や，ベクトル量子化に基づくインタベース中の各画像からはある一定間隔で部分領域を間引いてデックス手法であるグローバル枝刈り法 ½ 抽出し，逆にクエリからは間引きを行なわずに部分領域を抽出ができる．する．これにより，総当たり照合と全く同一の検索結果を理論的に保証したまま，すなわち，クエリとの距離が検索閾値を下回る部分画像を見落とすことなく，インデックスの保持に必要な記憶容量を大幅に削減することが可能となる．ここまでの手順は，クエリを必要としないので，事前処理として予め実行しておくことが可能である．クエリが与えられると，まず，クエリからブロックを取り出し，ブロック特徴を抽出する．次に，クエリに照合窓本稿の構成は以下の通りである．まず，¾º 節で提案法である ËÈÁÊ などを用いることてて，照合特徴 ´Ï µ ´ÜÉ Ý Éµ É Ï を当を抽出する．クエリにおいては，の概要を述べる．次に，¿º 節でインデックスを用いたデータベースとは異なり，照合窓を縦横 ½ ピクセルずつずらし候補領域の絞り込みについて具体的に説明する． º 節では，特ながら配置し，照合特徴を抽出する．続いて，クエリから抽出徴照合を高速化する手法について述べる． º 節で提案法の効果した照合特徴と類似する可能性のある照合特徴である検索候補を実験で示し， º 節を結びとする．を，インデックスを用いて抽出する．詳細については，¿º 節に ¾º 概て説明する．抽出された各検索候補について，対応するデータ Ü Ý 要ベース中の画像内の位置 ´ 図 ¾ に，ËÈÁÊ の概要を示す．まず，データベースの各画像 µ に，クエリと同じ大きさの窓を配置する．そして，照合特徴作成時と同様にして，ブロッから，大きさが Ü ¢ Ý ピクセルのブロックを切り出し，各ブロックからブロック特徴 Ⅱ－401 クを窓内に重複も隙間もなく配置して窓内のブロック特徴の集合体を抽出する．クエリ É と部分画像 ´Ü Ýµ との距離は，上記特徴の集合体同士の距離によって定義し，以下の式にしたした照合特徴の与え方として，¾ 通りの方法が考えられる．第がって計算する． ½ の方法として，クエリから抽出した全ての照合領域を個別に与え，独立に検索候補を抽出する．第 ¾ の方法として，クエリ Ü Ý µ Éµ ´Ü Ý µ ´ ´ ÕÜ Ü ½ ÕÝ Ý ¡ É ½ 出し，代表特徴を与えることで検索候補を抽出する．まず，照 ´ µ ´Ü · ¼ ¼ から抽出した照合特徴からそれらの代表となる代表特徴を取り Ü Ý· Ýµ ´ µ´ É 合特徴から代表特徴 Ýµ Ü の距離の最大値 Ñ Ü ´Ü Ý µ ´¾µ ここで， É はクエリ全体から抽出したブロック特徴の集合体 Ü Ýµ はクエリと同じ大きさの窓をデータベース中の画像における位置 ´Ü Ý µ に配置して抽出したブロック特徴の集合体， ´ µ ´Ü Ý µ は位置 ´Ü Ý µ にあるブロック特徴であ ´ であり，を取り出し，各照合特徴と代表特徴と É る．式 ´¾µ はすなわち，対応する位置にあるブロック特徴同士 ´Ï µ ´Ü É É Ýµ ´ µ を計算する．そして，代表特徴をインデックスに与え，代表特徴と類似する検索候補を抽出する．このとき，選択閾値は，各照合特徴との距離の最大値の分だけ大きくする．すなわち， ´Ï µ ´Ü Ý ´Ï µ µ · É ´ µ を満たす照合特徴を，検索候補として抽出する．第 ¾ の方法での距離を加算したものを全体の距離とすることを意味する．ブは，マージンが大きくなったときにロック特徴同士の距離は，様々な尺度を用いることが可能でああるため， Ð× り，例えば，ユークリッド距離，マンハッタン距離，内積，正とができない場合がある．この問題を回避するために，代表特規化相互相関などを用いることができる．式 ´¾µ で計算された徴を複数用いてを下回ったとき，部分画像距離が検索閾値 Ü Ýµ を検索結 ´ 果として出力する． Ð× ×Ñ ×× Ð を生じさせないことが必要である． Ð× ×¹ Ñ Ñ µ，照合領域の大きさ ´Û Û µ 及びクエリの大きさ ´Õ Õ µ は，以 Ñ ×× Ð が生じないことを保証するために，マージン ´ Ü Ý Ü Ü Ý ×Ñ ×× Ð が生じてしまう． Ð× Û Ü Ü · Ñ Ü Õ Û Ý Ý · Ñ ´¿µ Ý 像のいかなる場所に配置したとしても，少なくとも ½ つの照合領域が含まれている必要があることを意味する． Æ は，クエリと同じ大きさの窓をデータベース中の画像の任意位置に配置したときの，窓内に存在する重なりのない照合領域の最小数であり，以下のように与えられる． Æ Æ 検索候補としてインデックスから抽出される照合特徴は，クエリにおける各照合特徴 ´Ï µ ´ÜÉ られた値である選択閾値を下回る照合特徴である．すなわち， É 以下の式を満たす照合特徴 µ Ý Éµ ´Ï µ ´Ü ´Ï µ ´ÜÉ É との距離が，予め定め Ý µ が取り出される． Ý Éµ ´ µ 照合特徴同士の距離は，式 ´¾µ と同様にして，以下のようにして計算する． ´Ï µ ´Ü Ü Ý Ñ Ü ½ Æ Ñ Ü ½ ÛÜ Ü ½ ¼ Õ ´ µ Ü Õ ·½ Û Ñ Ñ Ò´ Ý Üµ Ü ·½ Û Ñ Ñ Ò´ Ýµ Ý ½ ´½¼µ ½ ´½½µ Ð× ×Ñ ×× Ð を生じさせないための必要条件であることを保証するものである．［補題 ½ ］ Ü Ý µ Éµ であれば， ´ µ ´Ü Ý ·Ü Ý ·Ý µ を満たす ´Ü Ý µ が存在する．もし ´ ´ ´Ï µ ´Ü É É É Ï É É Éµ É 補題 ½ は，文献 ½½ の Ì ÓÖ Ñ ½ と同様にして示される．想定されるクエリの最小サイズが既知であると仮定したとき， Ý ÛÝ Ý Æ ¡Æ 以下の補題は，条件 ´ µ がについて，説明する． Ý ´ µ ここで， Ý 本節では，インデックスを用いた検索候補の絞り込みの詳細を用いて以下 Æ Ü ¿º 検索候補の絞り込み Ð× のように与えられる． Ý 条件 ´¿µ は，クエリと同じ大きさの窓を，データベース中の画 ´Ï µ ´Ü Ð ÖÑ を減少 ×Ñ ×× Ð を生じさせないために選択閾値が満たすべき必要条件は，検索閾値下が必要条件となる．ある． Õ を小さくする方法も考えられる．選択閾値を小さく設定することによって， Ð× させることができるが，過度に小さく設定すると，逆に総当たり照合と同一の探索結果を保証するためには，少なくともの値が大きくなる傾向が Ð ÖÑ が増加し，十分に検索候補を絞り込むこ ½ ¼ µ ´Ï µ ´ÜÉ Ý ´ µ ´Ü · ´ µ ´ÜÉ · É É インデックスサイズを小さくためには，条件 ´¿µ を満たした上 Éµ でマージンをできる限り大きく取ることになるが，そのために照合窓の大きさを小さくしなければならない．照合窓の大きさ Ü Ý · Ýµ Ü Ý · Ýµ が小さくなると，条件 ´ µ を満たすために選択閾値を相対的に大きく設定しなければならず， Ð× É ´ µ インデックスから検索候補を抽出するとき，クエリから作成 Ⅱ－402 Ð ÖÑ が増加してしまう．すなわち，照合窓の大きさとマージンとは ØÖ あり，要求に応じて適切に設定する必要がある． ¹Ó« の関係に bx Image D matching window W wx by wy block 図 matching region feature extraction 8 0 4 0 0 0 1 3 1 8 0 0 0 2 3 7 1 1 2 0 0 original features p 3 0 0 5 2 2 2 2 2 ÕÜ Ü Ü Ý ½ ÕÝ Ý ½ ¼ Ý ¼ ¡ µ É Ü ´ Ü ´ · Ü Ý · Ýµ ÜÉ ´ Ý µµ Ü ´½¿µ blockwise VQ codebook for blockwise VQ (set of typical block patterns) 式 ´½¾µ´½¿µ に基づいて照合計算を行うと，照合特徴をブロッ 1 3 ク特徴の集合体として照合計算を行った場合と同一の検索結果 2 1 を保証することはできない．しかし，多数の ÎÉ 符号の集合体として表現されるので，実用上の検索精度が低下する可能性は feature f D 図¿ ´ クエリの例小さい．照合特徴の構成方法 º 実 º 特徴照合の高速化験 º½ 実験条件前節までに解説した手法により，インデックスを用いて検索提案法の効果を検証するために，½¼¼¼ 枚の画像中から特定の精度を保証したまま検索候補を絞り込むことが可能となった．部分画像を検索する実験を行った．実験に用いた計算機のしかし，特徴が極めて高次元であるため，いわゆる「次元の呪は ÁÒØ Ð い」と呼ばれる現象によりインデックスを用いた検索候補の絞 ÓÒ ¾º ÀÞ，メモリは ¾ ÈÍ とした．本実験では，データベース画像として，È ÒÒ×ÝÐÚ Ò ¸ ½ ËØ Ø り込みによる効果が著しく低下する，特徴照合に要する計算量 ÍÒ Ú Ö× ØÝ から配布された実画像データセットが非常に大きくなるなどの問題点が生じる．そこで本節では，た．このデータセットには ½¼¼¼ 枚の画像が ÂÈ 照合特徴の構成を工夫することにより，特徴空間の次元を仮想トで収録されており，各画像のサイズは ¿ 的に削減し，特徴照合を高速化する手法を説明する．ている．データベース中の任意の画像から， ¼ ¢ ¼ ピクセル概要を図 ¿ に示す．最初に，ブロック特徴に関して，その典 ¢¾ を用いフォーマッで統一されの部分画像を ½¼ 枚切り出し，これをクエリ画像として用いた．型的なパターンを予め学習しておく．具体的には，ブロック特ブロックの大きさは ¢ ピクセルとし，各ブロックに Ì Ì 係数ベクトルをブロック特徴として用いた．徴についてベクトル量子化の符号帳を作成する．次に，画像中を施し，そのの各ブロック特徴を，先に作成した符号帳を用いてベクトル量各ブロック特徴を，符号語数 ½¾ のベクトル量子化符号帳を用子化する．そして，ブロック特徴の代わりに，ベクトル量子化いて量子化し，ÎÉ 符号の集合を照合特徴とした．照合領域の符号 ´ÎÉ 符号µ を照合特徴の各要素として用いる．すなわち，大きさは照合特徴は ÎÉ 符号の集合体として表現される．て照合窓を配置し，各照合特徴にインデックスを付与した．イ照合特徴間の距離は，式 ´¾µ に代わって，以下の式で計算さ ¢ ンデックスは，ベクトル量子化に基づく特徴分類であるグローバル枝刈り法 ½ れる． ´Ï µ ´Ü ÛÜ Ü ½ Ý ÛÝ Ý ¼ µ ´Ï µ ´ÜÉ ½ ¼ Ü Ü Ýµ 及び · Ü ÜÉ ´ ここで， Ü ´ Éµ ´ Ü ´ · É を用いて付与した．グローバル枝刈り法において，特徴分類の数に相当するクラスタ数を ½¼¾ とした． Ý É ピクセルとし，別途定めたマージンにしたがっ º ¾ インデックスサイズ Ü Ü まず，マージンを変化させたときのインデックスサイズの変 Ý Ý É · Ýµ · Ý µµ 化について調べた．マージンは縦横同じ値を用いた．結果を図に示す．マージンが増加するにともなって，抽出するべき照 ´½¾µ Ü Ýµ は，各画像の位置 ´Ü Ýµ に ÜÉ ´ あるブロックに対応する ÎÉ 符号である．ÎÉ 符号間の距離は合領域が Ç´Ñ¾ µ で減少するので，インデックスサイズも同様のオーダで減少している． º¿ 検索時間前もって計算しておき，テーブルとして保持しておくことが可続いて，マージンを変化させたときの検索時間の変化につい能である．照合計算は，このテーブルを逐次参照することにて調べた．検索時間は，クエリが与えられてから検索結果を出よって行うことができ，極めて少ない処理で実行できる．同様力するまでに要する時間であり，クエリが与えられてから照合にして，検索候補を絞り込んだ後の詳細照合を，以下のように計算を行うまでの時間である事前処理時間と，照合計算に要すして行う．る時間である照合時間との和によって与えられる．インデック Ⅱ－403 ル変化，照明変動，回転などの変動をある程度吸収することが 1.E+09 可能であると考えられる．今後は，特徴，距離尺度，インデッ 123Mbyte クス構造などの検討を詳細に行うことによって，より高速かつ file size [byte] 1.E+08 より高精度な類似部分画像検索の実現を目指す．文 1.E+07 ½ 1.E+06 480Kbyte ¾ 1.E+05 1 4 8 12 16 margins 図 ¿ マージンに対するインデックスサイズの変化 8.0 time for matching calculations time for pre-processing time for calculations [s] 7.0 6.0 5.0 4.0 3.0 2.0 1.0 0.0 1 4 8 12 16 margins 図マージンに対する検索時間の変化スを用いて検索候補を絞り込んだ後の特徴照合において，現在の照合箇所における類似度に基づいて周辺箇所の照合をスキップする手法であるスキッピングテンプレートマッチング法 ½ ¸ ½ 図を用いたº 検索閾値は ½¼¼ とした． ½¼ に結果を示す．照合時間はマージンを変化させた場合でもほぼ一定であるが，事前処理時間がマージンの増加にしたがって若干増加しているため，検索時間はマージンの増加にと ½½ もなって若干増加している．事前処理時間は，検索候補の絞り込みに要する時間が大半である．よって，検索候補の絞り込み方法，及びそれと深く関連するインデックス構造をより詳細に ½¾ 検討することにより，検索時間のさらなる短縮が期待される．インデックスを用いずに検索を行なった場合，検索時間は ½½ ½¿ 秒であった． ½ º むすび本稿では，Ö ÁÑ ÓÒ¹ × ÔÔÖÓ に基づく ÓÒØ ÒØ¹ × Ê ØÖ Ú Ð 実現のための要素技術として，膨大な画像データベースの中から目的とするクエリ画像に類似する部分画像を検出するための基本的な枠組を提案した．提案法では，ある一 ½ ½ 定間隔をおいて間引いて抽出した部分領域に対してのみインデックスを付与することでインデックスサイズを大幅に削減し， ½ クエリ画像からあらゆる全ての部分領域を抽出して検索を行うことにより，総当たり照合と全く同一の検索結果を出力することを保証することができる．提案法は，様々な特徴や距離尺度を用いることが可能であるので，それらの工夫により，スケー Ⅱ－404 ½ 献 Åº Ð Ö Ø Ðº ÉÙ ÖÝ Ý Ñ Ò Ú Ó ÓÒØ ÒØ Ì É Á ×Ý×Ø Ñ ¸ Á ÓÑÔÙØ Ö¸ ÎÓÐº¾ ¸ ÆÓº ¸ ÔÔº¾¿¹¿¾¸ ½ º Ãº ÃÙ× Ñ ¸ Àº Ñ ¸ Ëº ÃÓÒ³Ý Ò Åº Ñ ÑÙÖÓ ÜË Ø À ÐÝ ÙÖ Ø Ó Ø × Ñ Ö ØÖ Ú Ð ×Ý×Ø Ñ Ò Ò Ý Ö ÙÒ ÒØ Ó Ø ÜØÖ Ø ÓÒ ¸ ÈÖÓ º Ó Ï ¹ ÁÒ ÓÖÑ ÒØ ÓÒ Å Ò Ñ ÒØ¸ ÔÔº¿¿½¹¿ ¿¸ ¾¼¼¼º Âº Êº ËÑ Ø Ò Ëº º Ò Î ×Ù ÐË Ã ÙÐÐÝ ÙØÓ¹ Ñ Ø ÓÒØ ÒØ¹ × Ñ ÕÙ ÖÝ ×Ý×Ø Ñ ¸ ÈÖÓ º Ó Å ÅÙÐØ Ñ ¸ ÔÔº ¹ ¿¸ ½ º º Æ Ø× Ú¸ Êº Ê ×ØÓ Ò Ãº Ë Ñ Ï ÄÊÍË × Ñ Ð Ö¹ ØÝ Ö ØÖ Ú Ð Ð ÓÖ Ø Ñ ÓÖ Ñ Ø × × ¸ Á ÌÖ Ò×º ÃÒÓÛÐ Ò Ø Ò Ò Ö Ò ¸ ÎÓÐº½ ¸ ÆÓº¿¸ ÔÔº¿¼½¹¿½ ¸ ¾¼¼ º ºÃÑ Ò º ÙÒ È ÖØ Ð × Ñ Ð Ö ØÝ × Ö Ò Ò Ð Ö Ñ Ø × × ¸ Ã ÁËÌ Ë Ì Ò Ð Ê ÔÓÖØ¸ Ë¹ÌÊ¹ ¾¼¼½¹½ ¸ ¾¼¼½º º Ö×ÓÒ¸ Åº Ì ÓÑ ×¸ Ëº ÐÓÒ ¸ Âº Åº À ÐÐ ÖËØ Ò Ò Âº Å Ð ÐÓ ÛÓÖÐ ×Ý×Ø Ñ ÓÖ Ö ÓÒ¹ × Ñ Ò Ü Ò Ò Ö ØÖ Ú Ð ¸ ÈÖÓ º Ó ÁÒØ ÖÒ Ø ÓÒ Ð ÓÒ Ö Ò ÓÒ Î ×ÙÐ ÁÒ ÓÖÑ Ø ÓÒ ËÝ×Ø Ñ×¸ ÔÔº ¼ ¹ ½ ¸ ½ º Ïº º Å Ò º Ëº Å Ò ÙÒ Ø Æ ÌÊ ØÓÓÐ ÓÜ ÓÖ Ò Ú ØÒ Ð Ö Ñ Ø × × ¸ ÈÖÓ º Ó Á ÁÈ¸ ÎÓÐº½¸ ÔÔº ¹ ½¸ ½ º Åº ×¸ º Åº Ê × Ñ Ò Ò º Åº Ö Ô Ö Ç ÍË Ë Ö Ò ÓÖ ÑÙÐØ ¹ ÓÐÓÖ Ó Ø× Ò Ú Ö× Ñ Ø × ¸ ÈÖÓ º Ó ÎÈÊ¸ ÔÔº ¹ ½¸ ½ º Âº º Ï Ò ¸ Âº Ä Ò º Ï Ö ÓÐ ËÁÅÈÄÁ ØÝ Ë Ñ ÒØ ×¹× Ò× Ø Ú ÒØ Ö Ø Ñ Ø Ò ÓÖ Ô ØÙÖ Ð ¹ Ö Ö × ¸ Á ÌÖ Ò×º È ØØ ÖÒ Ò ÐÝ× × Ò Å Ò ÁÒ¹ Ø ÐÐ Ò ¸ ÎÓÐº¾¿¸ ÆÓº ¸ ÔÔº ¹ ¿¸ ¾¼¼½º º ÅÓÓÒ¸ Ãº Ï Ò Ò Ïº ÄÓ Ù Ð ØÝ¹ × ×Ù × ¹ ÕÙ Ò Ñ Ø Ò Ò Ø Ñ ¹× Ö × Ø × × ¸ ÈÖÓ º Ó Á ¸ ÔÔº¾ ¿¹¾ ¾¸ ¾¼¼½º º ÅÓÓÒ¸ Ãº Ï Ò Ò Ïº À Ò Ò Ö ÐÅ Ø ×Ù ¹ × ÕÙ Ò Ñ Ø Ò Ñ Ø Ó Ò Ø Ñ ¹× Ö × Ø × × × ÓÒ Ò Ö Ð Þ Û Ò ÓÛ× ¸ ÈÖÓ º Ó Å ËÁ ÅÇ ¸ ÔÔº¿ ¾¹ ¿ ¿¸ ¾¼¼¾º Æº Ñ Ò¸ Àº Èº ÃÖ Ð¸ Ê¸ Ë Ò Ö Ò º Ë Ö Ì Ê£ ¹Ø Ò Æ ÒØ Ò ÖÓ Ù×Ø ×× Ñ Ø Ó ÓÖ ÔÓ ÒØ× Ò Ö Ø Ò Ð × ¸ ÈÖÓ º Ó Å ËÁ ÅÇ ¸ ÔÔº¿¾¾¹ ¿¿½¸ ½ ¼º 片山，佐藤 ËÊ¹ÌÖ ：高次元点データに対する最近接探索のためのインデックス構造の提案 ¸ 信学論 ¹Á¸ ÎÓÐº Â ¼¹ ¹Á¸ ÆÓº ¸ ÔÔº ¼¿¹ ½ ¸ Ù º ½ º º Ã ÑÙÖ ¸ Ãº Ã × ÒÓ¸ Ìº ÃÙÖÓÞÙÑ Ò Àº ÅÙÖ × Î ÖÝ ÕÙ Ù Ó × Ö Ò ÒØÖÓ Ù Ò ÐÓ Ð ÔÖÙÒ Ò ØÓ Ø Ì Ñ ¹× Ö × Ø Ú Ë Ö ¸ ÈÖÓ º Ó Á ËËÈ¸ ÎÓÐº¿¸ ÔÔº½ ¾ ¹½ ¿¾¸ ¾¼¼½º Ì ×Ø Ñ Ø × Ù× Ò ËÁÅÈÄÁ ØÝ Ô Ô Ö ¸ ØØÔ »»Û Ò º ×ØºÔ×Ùº Ù»ÁÅ »º Ìº Ã Û Ò × ¸ Ìº ÃÙÖÓÞÙÑ ¸ Ãº Ã × ÒÓ Ò Ëº Ì Ë ÔÔ Ò Ø ÑÔÐ Ø Ñ Ø Ò Ù Ö ÒØ Ò × Ñ ÙÖ Ý × Ü Ù×Ø Ú × Ö ¸ ÈÖÓ º Ó Á ÈÊ¸ ÔÔº¾¼ ¹¾½¾¸ ¾¼¼¿º 川西，黒住，柏野，高木サブテンプレート間距離を用いた適応的スキップによる高速テンプレートマッチング法−スキッピングテンプレートマッチング法− ¸ 画像の認識・理解シンポジウム予稿集¸ ¾¼¼ º º Ö× Ó Ò Êº Åº ÃÐÙÛ Ö ÓÑÔÖ ×× ÓÒº Ö Ý Î Ñ ØÓÖ ÕÙ ÒØ Þ Ø ÓÒ ´½ ¾µ Ò × Ò Ð