(57)【要約】【課題】複数の条件を同時に満たす要素を検索する場合であっても目的の要素を高速に検索することができるようにする。【解決手段】  入力ベクトル３３４が入力されると、最初に、最近傍ベクトル候補の初期値として無限遠の点が設定され、その入力ベクトル３３４の特徴量１の類似ペア群の検索３３５が特徴量１の３６次元ベクトルマップに対して行われる。そして、このような特徴量１の類似ペア群の検索３３５の検索結果として得られた特徴量１の類似ペア群が初期値３３６として利用され、特徴量２の類似ペア群の検索３３７が行われる。本発明は、画像処理装置に適用することができる。【選択図】図３２
2006190192.tif 000002
【特許請求の範囲】
【請求項１】
検索対象となる特徴ベクトル群の中から複数の評価基準で入力ベクトルに対する近傍ベクトルを検索する検索処理を行う情報処理装置であって、
各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索手段と、
前記近傍ベクトル検索手段により実行された各検索処理により得られた前記近傍ベクトルを、次の評価基準による検索処理における前記近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定手段と、
前記近傍ベクトル検索手段の全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記近傍ベクトル候補設定手段は、前記近傍ベクトル検索手段が実行する１つ目の評価基準による検索処理における前記近傍ベクトルの候補の初期値を、前記入力ベクトルから無限遠に位置する仮想ベクトルに設定する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記近傍ベクトルの更新を管理する変化フラグの状態を確認する変化フラグ確認手段をさらに備え、
前記近傍ベクトル設定手段は、前記変化フラグ確認手段による確認結果に基づいて、前記近傍ベクトル検索手段の全ての評価基準による検索処理が完了後に前記変化フラグが立っていない前記近傍ベクトルを複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
検索対象となる特徴ベクトル群が複数存在する場合、
前記近傍ベクトル検索手段は、前記特徴ベクトル群毎に、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行い、
前記近傍ベクトル候補設定手段は、各検索処理により得られた前記近傍ベクトルを、次の評価基準による検索処理における前記近傍ベクトルの候補の初期値に設定し、
前記近傍ベクトル設定手段は、前記特徴ベクトル群毎に、複数の評価基準における入力ベクトルに対する近傍ベクトルを設定する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項５】
検索対象となる特徴ベクトル群の中から複数の評価基準で入力ベクトルに対する近傍ベクトルを検索する検索処理を行う情報処理装置の情報処理方法であって、
各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索ステップと、
前記近傍ベクトル検索ステップの処理により実行された各検索処理により得られた前記近傍ベクトルを、次の評価基準による検索処理における前記近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定ステップと、
前記近傍ベクトル検索ステップの処理における全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定ステップと
を含むことを特徴とする情報処理方法。
【請求項６】
検索対象となる特徴ベクトル群の中から複数の評価基準で入力ベクトルに対する近傍ベクトルを検索する検索処理をコンピュータに行わせるプログラムにおいて、
各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索ステップと、
前記近傍ベクトル検索ステップの処理により実行された各検索処理により得られた前記近傍ベクトルを、次の評価基準による検索処理における前記近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定ステップと、
前記近傍ベクトル検索ステップの処理における全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および方法、並びにプログラムに関し、特に、複数の評価基準に基づいて検索を行う場合であっても、目的の要素を高速に検索することができるようにする情報処理装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来、あるn次元入力ベクトルが与えられたときに、n次元ベクトル群の集合の中から、入力ベクトルに近い最近傍ベクトルを見つけることは、Nearest Neighbor探索問題といわれ、数多くの高速探索方式が提案されている。
【０００３】
例えば、ベクトル量子化における最適ベクトル探索方法として、Ｎ個のセントロイドベクトルｖ（ｉ）のうち、所定のセントロイドベクトルを注目ベクトルｖ1とするとき、注目ベクトルｖ1とセントロイドベクトルｖ（ｉ）との距離のうち、Ｎ／ｋ番目に注目ベクトルｖ1に近い距離を、注目ベクトルの半径距離ＤRとし、入力ベクトルｕと注目ベクトルｖ1との距離Ｄ1と、半径距離ＤRの１／２の値ＤR／２とを比較し、その比較結果に対応して、最適ベクトルを探索する範囲を決定する方法がある（例えば、特許文献１参照）。
【０００４】
また、このような探索方法は、画像認識処理等における特徴ベクトルの探索にも利用される。特徴ベクトルとは画像の特徴パラメータを組み合わせベクトル化したものである。処理対象の画像の特徴ベクトルと、予め用意されたモデル画像の特徴ベクトルとが比較されることにより、処理対象の画像とモデル画像の関係が特定される。このように特徴ベクトルを用いた画像認識処理は、視点変化や明度変化に強い認識を行うことができる。
【０００５】
【特許文献１】特許３２７３５８１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、以上のような方法においては、検索対象と比較する特徴の種類が複数の場合、各特徴について個別に検索を行い、最終的に全ての特徴に対して条件を満たす要素を特定するので、明らかに不要な要素に対しても検索処理を行うことになり、検索処理の効率が悪く、処理が遅くなってしまうという課題があった。
【０００７】
本発明はこのような状況に鑑みてなされたものであり、複数の条件を満たす入力ベクトルの近傍ベクトルを高速に検索することができるようにするものである。
【課題を解決するための手段】
【０００８】
本発明の情報処理装置は、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索手段と、近傍ベクトル検索手段により実行された各検索処理により得られた近傍ベクトルを、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定手段と、近傍ベクトル検索手段の全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定手段とを備えることを特徴とする。
【０００９】
前記近傍ベクトル候補設定手段は、近傍ベクトル検索手段が実行する１つ目の評価基準による検索処理における近傍ベクトルの候補の初期値を、入力ベクトルから無限遠に位置する仮想ベクトルに設定するようにすることができる。
【００１０】
前記近傍ベクトルの更新を管理する変化フラグの状態を確認する変化フラグ確認手段をさらに備え、近傍ベクトル設定手段は、変化フラグ確認手段による確認結果に基づいて、近傍ベクトル検索手段の全ての評価基準による検索処理が完了後に変化フラグが立っていない近傍ベクトルを複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定するようにすることができる。
【００１１】
検索対象となる特徴ベクトル群が複数存在する場合、近傍ベクトル検索手段は、特徴ベクトル群毎に、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行い、近傍ベクトル候補設定手段は、各検索処理により得られた近傍ベクトルを、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定し、近傍ベクトル設定手段は、特徴ベクトル群毎に、複数の評価基準における入力ベクトルに対する近傍ベクトルを設定するようにすることができる。
【００１２】
本発明の情報処理方法は、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索ステップと、近傍ベクトル検索ステップの処理により実行された各検索処理により得られた近傍ベクトルを、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定ステップと、近傍ベクトル検索ステップの処理における全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定ステップとを含むことを特徴とする。
【００１３】
本発明のプログラムは、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索ステップと、近傍ベクトル検索ステップの処理により実行された各検索処理により得られた近傍ベクトルを、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定ステップと、近傍ベクトル検索ステップの処理における全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定ステップとを含むことを特徴とする。
【００１４】
本発明の情報処理装置および方法、並びにプログラムにおいては、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理が順次行われ、その各検索処理により得られた近傍ベクトルが、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定され、このように順次実行される全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルが、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定される。
【発明の効果】
【００１５】
本発明によれば、複数の条件を同時に満たす要素を検索する場合であっても目的の要素を高速に検索することができる。
【発明を実施するための最良の形態】
【００１６】
以下に本発明の実施の形態を説明するが、本明細書に記載の発明と、発明の実施の形態との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする実施の形態が本明細書に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、発明に対応するものとして、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その発明に対応するものではないことを意味するものではない。逆に、実施の形態が発明に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その発明以外の発明には対応しないものであることを意味するものでもない。
【００１７】
さらに、この記載は、本明細書に記載されている発明の全てを意味するものではない。換言すれば、この記載は、本明細書に記載されている発明であって、この出願では請求されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定するものではない。
【００１８】
本発明においては、検索対象となる特徴ベクトル群の中から複数の評価基準で入力ベクトルに対する近傍ベクトルを検索する検索処理を行う情報処理装置（例えば、図３３の画像処理装置）が提供される。この情報処理装置では、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索手段（例えば、図３５の近傍ベクトル検索部）と、近傍ベクトル検索手段により実行された各検索処理により得られた近傍ベクトルを、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定手段（例えば、図３５の特徴別近傍ベクトル候補設定部）と、近傍ベクトル検索手段の全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定手段（例えば、図３５の近傍ベクトル設定部）とを備える。
【００１９】
前記近傍ベクトル候補設定手段（例えば、図３５の初期化処理部）は、近傍ベクトル検索手段が実行する１つ目の評価基準による検索処理における近傍ベクトルの候補の初期値を、入力ベクトルから無限遠に位置する仮想ベクトルに設定する（例えば、図３７のステップＳ２４１）ようにすることができる。
【００２０】
前記近傍ベクトルの更新を管理する変化フラグの状態を確認する変化フラグ確認手段（例えば、図３５の変化フラグ確認部）をさらに備え、近傍ベクトル設定手段は、変化フラグ確認手段による確認結果に基づいて、近傍ベクトル検索手段の全ての評価基準による検索処理が完了後に変化フラグが立っていない近傍ベクトルを複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する（例えば、図３７のステップＳ２５０）ようにすることができる。
【００２１】
検索対象となる特徴ベクトル群が複数存在する場合（例えば、図２の特徴ベクトルグループ群）、近傍ベクトル検索手段は、特徴ベクトル群毎に、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行い、近傍ベクトル候補設定手段は、各検索処理により得られた近傍ベクトルを、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定し、近傍ベクトル設定手段は、特徴ベクトル群毎に、複数の評価基準における入力ベクトルに対する近傍ベクトルを設定するようにする（例えば、図３７のステップＳ２５１）ことができる。
【００２２】
本発明においては、検索対象となる特徴ベクトル群の中から複数の評価基準で入力ベクトルに対する近傍ベクトルを検索する検索処理を行う情報処理装置（例えば、図３３の画像処理装置）の情報処理方法が提供される。この情報処理方法においては、各評価基準による入力ベクトルに対する近傍ベクトルの検索処理を順次行う近傍ベクトル検索ステップ（例えば、図３７のステップＳ２４３およびステップＳ２４５）と、近傍ベクトル検索ステップの処理により実行された各検索処理により得られた近傍ベクトルを、次の評価基準による検索処理における近傍ベクトルの候補の初期値に設定する近傍ベクトル候補設定ステップ（例えば、図３７のステップＳ２４４）と、近傍ベクトル検索ステップの処理における全ての評価基準による検索処理において近傍ベクトルとして検索された特徴ベクトルを、複数の評価基準における入力ベクトルに対する近傍ベクトルとして設定する近傍ベクトル設定ステップ（例えば、図３７のステップＳ２５０）とを含む。
【００２３】
本発明のプログラムにおいても、各ステップが対応する実施の形態（但し一例）は、本発明の情報処理方法と同様である。
【００２４】
以下、本発明の実施の形態について図を参照して説明する。
【００２５】
図１は、本発明を適用した特徴量比較装置の構成例を示す図である。
【００２６】
図１に示される特徴量比較装置１０は、画像や音声等の対象となる情報の特徴を示すパラメータ等をベクトル化した特徴ベクトルを認識するための装置であり、入力された特徴ベクトルである入力ベクトルをモデルとなるベクトル群と比較し、入力ベクトルに最も近いベクトル（最近傍ベクトル）をベクトルの集合毎に検索し、その最近傍ベクトル群を出力する装置である。特徴量比較装置１０は、図１に示されるように、ベクトル情報記憶部１１、共通代表点設定部１２、共通代表点情報記憶部１３、近傍テーブル群作成部１４、近傍テーブル群記憶部１５、および最近傍ベクトル群検索部１６を有している。
【００２７】
ベクトル情報記憶部１１は、例えばハードディスクや半導体メモリ等の記憶媒体を有しており、モデルとなる特徴ベクトルに関する情報であるベクトル情報を予め記憶する。特徴ベクトルはモデル毎に集合として扱われ、ベクトル情報記憶部１１は、特徴ベクトルの集合を複数記憶する。つまり、ベクトル情報記憶部１１は、複数のモデルの特徴ベクトルを記憶し、必要に応じて、その特徴ベクトルを、共通代表点設定部１２、近傍テーブル群作成部１４、および最近傍ベクトル群検索部１６に供給する。
【００２８】
共通代表点設定部１２は、ベクトル情報記憶部１１より特徴ベクトルを取得し、各集合（モデル）に共通の代表点（共通代表点）を設定する。共通代表点は、各集合（モデル）の特徴ベクトルの分布の特徴を示す情報であり、全てまたは一部の特徴ベクトルを代表する点（ベクトル）である。つまり、共通代表点は、ベクトル情報記憶部１１に記憶されている複数の集合を１つの集合としたときの、その集合の要素の分布の特徴を示す点（新たな要素）である。換言すると、共通代表点の集合は、ベクトル情報記憶部１１に記憶されている各集合の特徴を平均化した集合（各集合間の要素の分布の違いを吸収した集合）である。
【００２９】
この共通代表点の数は任意であり例えばユーザに設定されたり予め決められていたりする。ただし、特徴ベクトルを代表するという性質から、共通代表点の数は、全特徴ベクトルの数より少ないことが望ましく、さらに、各集合（モデル）の特徴ベクトルの数よりも少ないのが望ましい。共通代表点設定部１２は、このように設定された数の共通代表点を、全てのまたは一部の特徴ベクトルに基づいて設定する。共通代表点の設定方法の詳細は後述する。共通代表点設定部１２は、設定した共通代表点の情報（共通代表点情報）を共通代表点情報記憶部１３に供給し、記憶させる。
【００３０】
共通代表点情報記憶部１３は、例えばハードディスクや半導体メモリ等の記憶媒体を有しており、共通代表点設定部１２より供給された共通代表点情報を記憶する。共通代表点情報記憶部１３は、その共通代表点情報を、必要に応じて、近傍テーブル群作成部１４および最近傍ベクトル群検索部１６に供給する。
【００３１】
近傍テーブル群作成部１４は、ベクトル情報記憶部１１よりベクトル情報を取得し、さらに、共通代表点情報記憶部１３より共通代表点情報を取得すると、それらに基づいて、集合（モデル）毎に、各共通代表点の近傍に位置する特徴ベクトルの一覧である近傍テーブルを作成する。近傍テーブルは、後述するように、各共通代表点の近傍に位置する特徴ベクトルをリストアップしたテーブル情報であり、各集合（モデル）に作成される。つまり、共通代表点（群）は全集合（モデル）の特徴ベクトルを代表する点（群）であり、近傍テーブルは、各集合とその共通代表点との関係を示すテーブル情報である。近傍テーブルの作成方法の詳細や、近傍テーブルを利用する方法については後述する。近傍テーブル群作成部１４は、このような近傍テーブルを集合（モデル）毎に作成すると、その近傍テーブル群を近傍テーブル群記憶部１５に供給して記憶させる。
【００３２】
近傍テーブル群記憶部１５は、例えばハードディスクや半導体メモリ等の記憶媒体を有しており、近傍テーブル群作成部１４より供給された近傍テーブル群を記憶する。近傍テーブル群記憶部１５は、その近傍テーブル群を、必要に応じて、最近傍ベクトル群検索部１６に供給する。
【００３３】
最近傍ベクトル群検索部１６は、特徴量比較装置１０の外部より入力された特徴ベクトルである入力ベクトルを取得すると、ベクトル情報記憶部１１より取得したベクトル情報、共通代表点情報記憶部１３より取得した共通代表点情報、および近傍テーブル群記憶部１５より取得した近傍テーブル群を必要に応じて利用し、それらに基づいて入力ベクトルに最も近い最近傍ベクトルを集合（モデル）毎に検索する。最近傍ベクトル群検索部１６は、そのようにして検索された最近傍ベクトル群を特徴量比較装置１０の外部に比較結果として出力する。
【００３４】
次に、図２乃至図５を参照して、この特徴量比較装置１０による特徴量の比較方法について詳細に説明する。
【００３５】
特徴量比較装置１０は、入力ベクトルの特徴量をモデルの特徴ベクトルと比較する前に、まず、図２に示されるように、共通代表点を設定し、近傍テーブルを生成する。
【００３６】
ベクトル情報記憶部１１（図１）には、図２に示されるように、複数のモデル（集合）からなる、検索対象ベクトルグループ群２１が記憶されている。検索対象ベクトルグループ群は、Ｍ個の検索対象ベクトルグループ（すなわち、集合（モデル））２１−１乃至２１−Ｍにより構成される。各グループは特徴ベクトル２２の集合である。
【００３７】
共通代表点設定部１２（図１）は、この検索対象ベクトルグループ群２１を統一し、その１つの集合２３からなる特徴ベクトル群を形成すると、その集合２３の要素となる特徴ベクトル群を代表する（特徴ベクトル群の分布の様子を示す）代表点、すなわち、全集合（全モデル）に共通の代表点である共通代表点２４をＲ個設定する。
【００３８】
近傍テーブル群作成部１４（図１）は、共通代表点情報記憶部１３（図１）を介して、この共通代表点２４に関する情報を取得すると、ベクトル情報記憶部１１より取得したベクトル情報に基づいて、集合毎に近傍テーブル２５−１乃至２５−Ｍを作成し、近傍テーブル群記憶部１５に記憶させる。
【００３９】
この近傍テーブルは、例えば図３のように構成される。近傍テーブルにリストアップする各共通代表点の近傍ベクトルの数は任意であり、ユーザにより指定された数であってもよいし、予め定められた数であってもよいが、共通代表点の近傍の特徴ベクトルを示すという近傍テーブルの性質上、各集合の特徴ベクトルの数より少ないことが望ましい。
【００４０】
各近傍テーブルには、図３に示されるように、Ｒ個の共通代表点のそれぞれについて、Ｋ個の近傍ベクトルの識別情報と、その近傍ベクトルの共通代表点からの距離の２分の１の値が近い順に登録されている。
【００４１】
例えば、近傍テーブル２５−１には、共通代表点１の近傍ベクトルとして、最も近い特徴ベクトルの識別情報が「Ｎｏ．３」であり、その特徴ベクトルと共通代表点１との距離の２分の１の値が「０．２９」であり、２番目に近い特徴ベクトルの識別情報が「Ｎｏ．８」であり、その特徴ベクトルと共通代表点１との距離の２分の１の値が「０．３２」であり、３番目に近い特徴ベクトルの識別情報が「Ｎｏ．９」であり、その特徴ベクトルと共通代表点１との距離の２分の１の値が「０．４２」であり、４番目に近い特徴ベクトルの識別情報が「Ｎｏ．２」であり、その特徴ベクトルと共通代表点１との距離の２分の１の値が「０．４６」であり、５番目に近い特徴ベクトルの識別情報が「Ｎｏ．５」であり、その特徴ベクトルと共通代表点１との距離の２分の１の値が「０．５１」であることが示されている。同様に、近傍テーブル２５−１には、共通代表点２乃至共通代表点Ｒのそれぞれについて近傍ベクトルが近い順に５番目（Ｋ番目）まで登録されている。
【００４２】
近傍テーブル群作成部１４は、このような近傍テーブルを特徴ベクトルの集合（モデル）毎にＭ個作成する。
【００４３】
この近傍テーブルは、入力ベクトルの近傍ベクトルを検索する際に、検索対象とする特徴ベクトルの絞り込みに利用される。
【００４４】
最近傍ベクトル群検索部１６は、図４に示されるように、処理対象の情報２６の特徴を各モデルの特徴と比較するために、情報２６の特徴ベクトルである入力ベクトル２７に近似する最近傍ベクトルを、検索対象ベクトルグループ群２１の各グループの特徴ベクトル２２から検索する。つまり、最近傍ベクトル群検索部１６は、まず、集合検索対象ベクトルグループ２１−１について入力ベクトル２７の最近傍ベクトル２８−１を検索し、次に、集合検索対象ベクトルグループ２１−２について入力ベクトル２７の最近傍ベクトル２８−２を検索する。最近傍ベクトル群検索部１６は、集合検索対象ベクトルグループ２１−３乃至２１−Ｍについても同様に入力ベクトル２７の最近傍ベクトルをそれぞれ検索する。そして、最近傍ベクトル群検索部１６は、このように検索された最近傍ベクトル群を処理対象の情報２６とモデルとの比較結果として出力する。
【００４５】
この最近傍ベクトルの検索の際に、最近傍ベクトル群検索部１６は、図３の近傍テーブル群を利用することにより、その検索範囲を削減し、高速に最近傍ベクトル群を検索する。つまり、最近傍ベクトル群検索部１６は、まず、入力ベクトル２７と共通代表点との距離を算出する。次に、最近傍ベクトル群検索部１６は、その距離を、近傍テーブルにおける、近傍ベクトルと共通代表点との距離の２分の１と比較する。入力ベクトル２７と共通代表点との距離の方が短い場合、最近傍ベクトル群検索部１６は、入力ベクトル２７の最近傍ベクトルを、近傍テーブルに登録された共通代表点の近傍ベクトル群（共通代表点も含む）の中から検索し、その他の特徴ベクトルについては検索範囲外として検索しない。逆に、入力ベクトル２７と共通代表点との距離の方が遠い場合、最近傍ベクトル群検索部１６は、入力ベクトル２７の最近傍ベクトルを、その集合の全ての特徴ベクトルの中から検索する。
【００４６】
図５を参照してその範囲設定の原理を説明する。入力ベクトルｖ、共通代表点ｒ、および、近傍テーブルに登録されているこの共通代表点ｒから最も遠い（すなわち、共通代表点ｒからＫ番目に近い）近傍ベクトルｋが図５に示されるような位置関係であるとする。円３１は、共通代表点ｒと近傍ベクトルｋとの距離Ｄを示し、円３２は、その距離Ｄの２分の１（Ｄ／２）を示している。
【００４７】
共通代表点ｒを基準に考えると、入力ベクトルｖの最近傍ベクトルが入力ベクトルから最も離れた場合、その最近傍ベクトルは、共通代表点ｒとなる。つまり、図５の点線の円で示されるように、入力ベクトルｖの最近傍ベクトルが共通代表点ｒより遠い位置に存在することはない（最近傍ベクトルは必ず点線の円内に位置する）。
【００４８】
従って、入力ベクトルｖが円３２の内側に存在する場合、すなわち、入力ベクトルｖと共通代表点ｒとの距離ｄが近傍ベクトルｋと共通代表点ｒとの距離Ｄの２分の１より短い（ｄ＜Ｄ／２）場合、点線の円が円３１の外にはみ出すことはない。つまり、この場合、入力ベクトルｖの最近傍ベクトルは、必ず、共通代表点の近傍ベクトルｋより近い位置に存在する。
【００４９】
以上のような原理に基づいて、最近傍ベクトル群検索部１６は、入力ベクトル２７と各共通代表点との距離を算出し、近傍テーブルに登録されている、その共通代表点から最も遠い近傍ベクトルの、共通代表点との距離の２分の１の値と、算出した距離を比較する。そして、最近傍ベクトル群検索部１６は、このような処理を各共通代表点について行い、入力ベクトルと共通代表点との距離の方が短くなる共通代表点が存在する場合、その共通代表点の近傍ベクトルの中から入力ベクトルの最近傍ベクトルを検索する。そして、どの共通代表点に対しても入力ベクトルと共通代表点との距離の方が短くなる共通代表点が存在しなかった場合のみ、最近傍ベクトル群検索部１６は、検索対象ベクトルグループ内の全ての特徴ベクトルを検索対象とし、それらの中から最近傍ベクトルを検索する。
【００５０】
最近傍ベクトル群検索部１６は、このような検索を検索対象ベクトルグループ（モデル）毎に行い、比較結果として最近傍ベクトル群を出力する。このようにすることにより、特徴量比較装置１０は、明らかに最近傍ベクトルとはならない不要な特徴ベクトルを検索対象から除外することができるので、目的の要素を高速に検索することができる。また、共通代表点設定部１２が全検索対象ベクトルグループ（モデル）に共通の共通代表点を設定し、最近傍ベクトル群検索部１６が、その共通代表点を基準として最近傍ベクトルを検索することにより、特徴量比較装置１０は、検索対象ベクトルグループが複数存在する場合であっても、各検索対象ベクトルグループから最近傍ベクトルを高速に検索することができる。つまり、特徴量比較装置１０は、検索対象の集合が複数存在する場合であっても、各集合から目的の要素を高速に検索することができる。
【００５１】
次に、図１の特徴量比較装置１０の各部の詳細な構成について説明する。
【００５２】
図６は、共通代表点設定部１２の詳細な構成例を示す図である。図６において、共通代表点設定部１２は、共通代表点目標数設定部４１、ベクトルグループ統一部４２、重心算出部４３、共通代表点設定部４４、共通代表点数判定部４５、共通代表点分割部４６、メンバベクトル割り当て部４７、および共通代表点記憶制御部４８を有している。
【００５３】
共通代表点目標数設定部４１は、例えばユーザ入力等に基づいて共通代表点目標数の設定を行い、その情報を共通代表点数判定部４５に供給する。この共通代表点目標数は例えば２のｎ乗（ｎは整数）に設定される。また、共通代表点目標数は、ユーザ等に指示された値であってもよいし、予め定められた値であってもよい。
【００５４】
ベクトルグループ統一部４２は、ベクトル情報記憶部１１よりベクトル情報を取得すると、その情報に基づいて、ベクトル情報記憶部１１が記憶している全てのベクトルグループを統一し、全てのベクトルを含む１つのベクトルグループを作成する。そしてベクトルグループ統一部４２は、その情報を重心算出部４３に供給する。
【００５５】
重心算出部４３は、ベクトルグループ統一部４２より供給されるベクトル情報、またはメンバベクトル割り当て部４７より供給されるベクトル情報に基づいて、ベクトルグループ毎にベクトル群の重心（ベクトルの分布の重心位置）を算出する。例えば、ベクトルグループ統一部４２より供給されたベクトル情報においては、ベクトルグループは１つに統一されているので、そのベクトル情報に基づいて重心位置を算出する場合、重心算出部４３は、全てのベクトル群の重心を算出する。また、メンバベクトル割り当て部４７より供給されるベクトル情報に基づいて重心位置を算出する場合、重心算出部４３は、メンバベクトル割り当て部４７によって同じ共通代表点に割り当てられたメンバベクトル群を１つのベクトルグループとし、そのベクトルグループ毎に重心位置を算出する。重心算出部４３は、算出した重心に関する情報を共通代表点設定部４４に供給する。
【００５６】
共通代表点設定部４４は、重心算出部４３より供給された重心位置を共通代表点に設定し、その情報を共通代表点数判定部４５およびメンバベクトル割り当て部４７に供給する。
【００５７】
共通代表点数判定部４５は、共通代表点設定部４４より供給された設定結果を取得するか、または、メンバベクトル割り当て部４７より割り当て結果を取得すると、その設定結果または割り当て結果における共通代表点の数が共通代表点目標数設定部４１より供給された共通代表点目標数より少ないか否かを判定し、その判定結果に基づいて、共通代表点の情報を共通代表点分割部４６または共通代表点記憶制御部４８に供給する。
【００５８】
共通代表点分割部４６は、共通代表点数判定部４５より共通代表点に関する情報を取得すると、各共通代表点を２つに分割し、それらを元の位置から互いに離れるように所定の向きにに微小量ずらす。例えば、共通代表点分割部４６は、２つに分割した点の一方の位置をｘ軸の正方向に微小量ずらし、他方の位置をｘ軸の負方向にずらす。なお、この２点位置の補正の方向は互いに逆向きであればどのような方向であっても良い。つまり、共通代表点分割部４６は、共通代表点の数を分割して位置補正することにより、共通代表点の数を２倍に増やす。共通代表点分割部４６は、この分割して位置補正した共通代表点の情報をメンバベクトル割り当て部４７に供給する。
【００５９】
メンバベクトル割り当て部４７は、共通代表点分割部４６より供給される共通代表点に関する情報、すなわち、共通代表点分割部４６において分割され、その数が２倍になった共通代表点に関する情報を取得すると、それらの各共通代表点にメンバベクトルを割り当て、その割り当て結果を重心算出部４３に供給するとともに、共通代表点数判定部４５にその共通代表点の数に関する情報を供給する。
【００６０】
また、メンバベクトル割り当て部４７は、共通代表点設定部４４より供給される共通代表点の設定結果を取得すると、その設定結果に基づいて、設定された各共通代表点に対してメンバベクトルの割り当てを行い、その割り当て結果を重心算出部４３に供給するとともに、共通代表点の数に関する情報を供給する。
【００６１】
共通代表点記憶制御部４８は、共通代表点数判定部４５より供給される共通代表点に関する情報を共通代表点情報記憶部１３に供給し、記憶させる。
【００６２】
図７は、図１の近傍テーブル群作成部１４の詳細な構成例を示すブロック図である。
【００６３】
図７において、近傍テーブル群作成部１４は、初期化処理部６１、近傍テーブル群作成制御部６２、近傍テーブル作成部６３、および近傍テーブル記憶制御部６４を有している。
【００６４】
初期化処理部６１は、ベクトル情報記憶部１１よりベクトル情報を取得し、共通代表点情報記憶部１３より共通代表点情報を取得すると、近傍テーブル群の作成に必要な変数を初期値に設定する等の初期化処理を行う。
【００６５】
近傍テーブル群作成制御部６２は、近傍テーブル群の作成に関する制御処理を行う。近傍テーブル作成部６３は、近傍テーブルの作成に関する処理を行う。近傍テーブル記憶制御部６４は、近傍テーブル群記憶部１５を制御し、作成された近傍テーブルを記憶させる。
【００６６】
図８は、図７の近傍テーブル作成部６３の詳細な構成例を示すブロック図である。図８において、近傍テーブル作成部１４は、近傍テーブル群作成制御部８１、距離情報作成部８２、距離情報ソート部８３、距離情報抽出部８４、およびレコード保持部８５を有している。
【００６７】
近傍テーブル作成制御部８１は、近傍テーブルの作成に関する制御処理を行う。距離情報作成部８２は、近傍テーブルに用いられる距離情報の作成に関する処理を行う。距離情報ソート部８３は、距離情報作成部８２が作成した各距離情報を、その値の小さい順（距離の短い順）に整列（ソート）させる。距離情報抽出部８４は、そのソートされた距離情報の内、距離の短いほうから所定の数の距離情報を抽出する。レコード保持部８５は、その抽出された距離情報を近傍テーブルのレコードとして保持し、その情報を近傍テーブル作成制御部８１に返す。
【００６８】
図９は、図８の距離情報作成部８２の詳細な構成例を示すブロック図である。図９において、距離情報作成部８２は、距離情報作成制御部１０１、距離算出部１０２、１／２乗算部１０３、および距離情報保持部１０４を有している。
【００６９】
距離情報作成制御部１０１は、距離情報の作成に関する制御処理を行う。距離算出部１０２は、処理対象に指定されている共通代表点とメンバベクトルとの距離を算出する。１／２乗算部１０３は、算出された共通代表点とメンバベクトルとの距離に１／２を乗算する。距離情報保持部１０４は、その共通代表点とメンバベクトルとの距離の１／２の値を距離情報として保持し、その情報を距離情報作成制御部１０１に返す。
【００７０】
図１０は、図１の最近傍ベクトル群検索部１６の詳細な構成例を示すブロック図である。図１０において最近傍ベクトル群検索部１６は、初期化処理部１２１、最近傍ベクトル群検索制御部１２２、および最近傍ベクトル検索部１２３を有しており、ベクトル情報記憶部１１に記憶されているモデルから入力ベクトルの最近傍ベクトル群を検索する。
【００７１】
初期化処理部１２１は、入力ベクトルを取得すると、ベクトル情報記憶部１１よりベクトル情報を取得し、共通代表点情報記憶部１３より共通代表点情報を取得し、近傍テーブル群記憶部１５より近傍テーブル群を取得し、入力ベクトルの最近傍ベクトル群の検索に必要な変数を初期値に設定する等の初期化処理を行う。
【００７２】
最近傍ベクトル群検索制御部１２２は、入力ベクトルの最近傍ベクトル群の検索に関する制御処理を行う。最近傍ベクトル検索部１２３は、最近傍ベクトル群検索制御部１２２に制御され、ベクトルグループ毎に入力ベクトルの最近傍ベクトルを検索し、その検索結果を最近傍ベクトル群検索制御部１２２に返す。
【００７３】
図１１は、図１０の最近傍ベクトル検索部１２３の詳細な構成例を示すブロック図である。図１１において、最近傍ベクトル検索部１２３は、初期化処理部１４１、最近傍ベクトル検索制御部１５２、距離算出部１４３、距離比較部１４４、テーブル内検索部１４５、最近傍ベクトル設定部１４６、およびグループ内全体検索部１４７を有しており、モデル（ベクトルグループ）毎の最近傍ベクトルの検索処理を行う。
【００７４】
初期化処理部１４１は、入力ベクトルの最近傍ベクトルの検索に必要な変数を初期値に設定する等の初期化処理を行う。最近傍ベクトル検索制御部１４２は、処理対象のベクトルグループにおける入力ベクトルの最近傍ベクトルの検索に関する制御処理を行う。
【００７５】
距離算出部１４３は、入力ベクトルと処理対象の共通代表点との距離を算出する。距離比較部１４４は、算出された入力ベクトルと処理対象の共通代表点との距離を、近傍テーブルの距離情報と比較し、その比較結果に応じてテーブル内検索部１４５に最近傍ベクトルの検索処理を実行させる。
【００７６】
テーブル内検索部１４５は、近傍テーブルに登録されているメンバベクトルの中から入力ベクトルの最近傍ベクトルを検索し、その検索結果を最近傍ベクトル設定部１４６に供給する。
【００７７】
最近傍ベクトル設定部１４６は、テーブル内検索部１４５またはグループ内全体検索部１４７により検索されたメンバベクトルを入力ベクトルの最近傍ベクトルとして設定し、その設定結果を最近傍ベクトル検索制御部１４２に返す。
【００７８】
グループ内全体検索部１４７は、最近傍ベクトル検索制御部１４２によって全ての共通代表点の近傍ベクトルの中に入力ベクトルの最近傍ベクトルが存在しないと判定された場合、処理対象のベクトルグループ内の全てのメンバベクトルの中から入力ベクトルの最近傍ベクトルを検索し、その検索結果を最近傍ベクトル設定部１４６に供給する。
【００７９】
図１２は、図１１のテーブル内検索部１４５の詳細な構成例を示すブロック図である。図１２においてテーブル内検索部１４５は、初期化処理部１６１、テーブル内検索制御部１６２、距離算出部１６３、更新制御部１６４、およびデータ保持部１６５を有しており、近傍テーブルに登録されているメンバベクトルに対する最近傍ベクトルの検索（最近傍ベクトルのテーブル内検索）を行う。
【００８０】
初期化処理部１６１は、最近傍ベクトルのテーブル内検索に必要な変数を初期値に設定する等の初期化処理を行う。例えば、初期化処理部１６１は、最近傍ベクトルの候補であるＶkeepを入力ベクトルからの距離が無限遠の仮想点を設定し、入力ベクトルからの距離Ｄkeepを無限遠に設定する。また、初期化処理部１６１は、変数ｋの値を初期値（例えば「０」）に設定する。テーブル内検索制御部１６２は、最近傍ベクトルのテーブル内検索に関する制御処理を行う。距離算出部１６３は、入力ベクトルと、近傍テーブルに登録されているメンバベクトルとの距離を算出する。更新制御部１６４は、その算出された入力ベクトルとメンバベクトルとの距離に基づいてデータ保持部１６５が保持しているデータの更新を制御する。また、更新制御部１６４は、その制御結果をテーブル内検索制御部１６２に返す。データ保持部１６５は、入力ベクトルに最も近いベクトル（最近傍ベクトルの候補）に関するデータ（例えば、ＶkeepおよびＤkeep）を保持する。
【００８１】
図１３は、図１１のグループ内全体検索部１４７の詳細な構成例を示すブロック図である。図１３においてグループ内全体検索部１４７は、初期化処理部１８１、グループ内全体検索制御部１８２、距離算出部１８３、および更新制御部１８４、およびデータ保持部１８５を有しており、ベクトルグループの全てのメンバベクトルに対する最近傍ベクトルの検索（最近傍ベクトルのグループ内全体検索）を行う。
【００８２】
初期化処理部１８１は、最近傍ベクトルのグループ内全体検索に必要な変数を初期値に設定する等の初期化処理を行う。例えば、初期化処理部１８１は、最近傍ベクトルの候補であるＶkeepを入力ベクトルからの距離が無限遠の仮想点を設定し、入力ベクトルからの距離Ｄkeepを無限遠に設定する。また、初期化処理部１８１は、変数ｉの値を初期値（例えば「０」）に設定する。グループ内全体検索制御部１８２は、最近傍ベクトルのグループ内全体検索に関する制御処理を行う。距離算出部１８３は、入力ベクトルと、ベクトルグループ内のメンバベクトルとの距離を算出する。更新制御部１８４は、その算出された入力ベクトルとメンバベクトルとの距離に基づいてデータ保持部１８５が保持しているデータの更新を制御する。また、更新制御部１８４は、その制御結果をグループ内全体検索制御部１８２に返す。データ保持部１８５は、入力ベクトルに最も近いベクトル（最近傍ベクトルの候補）に関するデータ（例えば、ＶkeepおよびＤkeep）を保持する。
【００８３】
次に、以上のような構成の特徴量比較装置１０により実行される各処理の流れについて説明する。
【００８４】
最初に、特徴量比較装置１０は、共通代表点設定部１２（図１）によってベクトル情報保持部１１が保持しているベクトル情報に基づいて、各ベクトルグループ（モデル）に共通な代表点群を設定する。この共通代表点設定処理の流れを図１４のフローチャートを参照して説明する。
【００８５】
共通代表点設定処理が開始されると、ステップＳ１において、共通代表点目標数設定部４１（図６）は、入力された目標数（例えば、２のｎ乗（ｎは整数））に基づいて、共通代表点の目標数の変数NumReqを設定し、その値を共通代表点数判定部４５に供給する。
【００８６】
ステップＳ２において、ベクトルグループ統一部４２は、ベクトル情報記憶部１１よりベクトル情報を取得し、そのベクトル情報に基づいて、ベクトル情報記憶部１１に記憶されているベクトルグループの全グループを統一し、各グループの全部または一部のメンバベクトルからなる１つのグループを生成する。つまり、ベクトルグループ統一部４２は、各グループの全てのメンバベクトル、若しくは、各グループより任意の方法で抽出した一部のメンバベクトルを１つのグループとして再構成する。このグループの統一にメンバベクトルの全てを用いるかまたは一部のメンバベクトルを用いるかは毎回任意の方法で決定するようにしてもよいし、予め定められていてもよい。
【００８７】
グループが統一されると、重心算出部４３は、ステップＳ３において、そのグループが統一されたベクトル情報をベクトルグループ統一部４２より取得すると、その情報に基づいて、メンバベクトルの重心点（各メンバベクトルをそれぞれ質点とし、各質点にはたらく重力の合力の作用点）を算出し、その算出結果を共通代表点設定部４４に供給する。
【００８８】
共通代表点設定部４４は、ステップＳ４においてその重心点を共通代表点として設定し、共通代表点の数を示す変数GpNumの値を「１」に設定し、その設定結果を共通代表点数判定部４５に供給する。共通代表点数判定部４５は、ステップＳ５において、共通代表点の数GpNumの値が目標数NumReqの値より小さいか否かを判定する。
【００８９】
共通代表点の数GpNumの値が目標数NumReqの値より小さいと判定した場合、すなわち、目標数分の共通代表点を設定していない（設定した共通代表点の数が目標値に達していない）と判定した場合、共通代表点数判定部４５は、その共通代表点の情報を共通代表点分割部４６に供給し、処理をステップＳ６に進める。
【００９０】
ステップＳ６において、共通代表点分割部４６は、供給された共通代表点の情報に基づいて、各共通代表点を２つに分割し、位置を補正する。そして、共通代表点分割部４６は、ステップＳ７において、共通代表点の数GpNumの値を２倍にし、その共通代表点の情報をメンバベクトル割り当て部４７に供給する。
【００９１】
メンバベクトル割り当て部４７は、ステップＳ８において、各メンバベクトルを共通代表点に割り当て、ステップＳ９において、各メンバベクトルが属する共通代表点が全て前回と同じであるか否か、すなわち、各共通代表点が前回の割り当て時と同じであり、かつ、その各共通代表点に前回の割り当て時と同じメンバベクトルが割り当てられたか否かを判定する。
【００９２】
各メンバベクトルが属する共通代表点が全て前回と同じでないと判定した場合、すなわち、前回の割り当て時と、共通代表点が異なるか、若しくは、各共通代表点に割り当てられたメンバベクトルが異なると判定した場合、メンバベクトル割り当て部４７は、その判定結果を重心算出部４３に供給し、処理をステップＳ１０に進める。
【００９３】
ステップＳ１０において、重心算出部４３は同じ共通代表点に属するメンバベクトル同士の重心点を算出し、共通代表点設定部４４はその重心点を新たな共通代表点とする。つまり、重心算出部４３は、１つの共通代表点に割り当てられたメンバベクトル群を１つのグループとし、そのグループ毎に重心点を算出する。共通代表点設定部４４は、その算出された重心点をそれぞれ共通代表点とし、その処理結果をメンバベクトル割り当て部４７に供給し、処理をステップＳ８に戻し、それ以降の処理を繰り返す。メンバベクトル割り当て部４７は、供給された共通代表点の情報に基づいて、再度、各共通代表点に対するメンバベクトルの割り当てを行う。
【００９４】
つまり、メンバベクトル割り当て部４７、重心算出部４３、および共通代表点設定部４４は、メンバベクトル割り当て部４７がステップＳ９において、各メンバベクトルが属する共通代表点が全て前回と同じであると判定するまで、ステップＳ８乃至ステップＳ１０の処理を繰り返す。
【００９５】
ステップＳ９において、各メンバベクトルが属する共通代表点が全て前回と同じであると判定した場合、メンバベクトル割り当て部４７は、その判定結果を共通代表点数判定部４５に供給し、処理をステップＳ５に戻し、それ以降の処理を実行させる。
【００９６】
すなわち、共通代表点数判定部４５、共通代表点分割部４６、メンバベクトル割り当て部４７、重心算出部４３、および共通代表点設定部４４は、共通代表点数判定部４５がステップＳ５において、共通代表点の数GpNumの値が目標数NumReqの値より小さくないと判定するまで、ステップＳ５乃至ステップＳ１０の処理を繰り返す。
【００９７】
そして、ステップＳ５において、共通代表点の数GpNumの値が目標数NumReqの値より小さくないと判定した場合、すなわち、目標数分の共通代表点を設定した（設定した共通代表点の数が目標値に達した）と判定した場合、共通代表点数判定部４５は、その共通代表点の情報を共通代表点記憶制御部４８に供給し、処理をステップＳ１１に進める。
【００９８】
共通代表点記憶制御部４８は、ステップＳ１１において、その共通代表点の情報を、共通代表点情報記憶部１３に供給して記憶させる。共通代表点情報記憶部１３は、その供給された共通代表点の情報を記憶する。
【００９９】
共通代表点記憶制御部４８は、ステップＳ１１の処理を終了すると、共通代表点設定処理を終了する。
【０１００】
以上のように、共通代表点設定部１２が共通代表点設定処理を行い、重心点を用いて共通代表点をＲ個設定することにより、特徴量比較装置１０は、検索対象のベクトル集合（モデル）が複数存在する場合であっても、各集合（モデル）の近傍テーブルを容易に作成し、さらに、その近傍テーブルを用いて各集合（モデル）に対する入力ベクトルの近傍ベクトルを高速に検索することができる。
【０１０１】
以上のようにしてＲ個の共通代表点を設定した特徴量比較装置１０は、各ベクトルグループ（モデル）について、その各共通代表点の近傍ベクトルに関するテーブル情報である近傍テーブルをベクトルグループの数（Ｍ個）だけ作成する（Ｍ個の近傍テーブルからなる近傍テーブル群を作成する）。近傍テーブル群作成部１４（図１）は、共通代表点情報記憶部１３に記憶されている共通代表点の情報と、ベクトル情報記憶部１１に記憶されているベクトル情報に基づいて、近傍テーブル群作成処理を実行する。図１５のフローチャートを参照してその近傍テーブル群作成処理の流れについて説明する。
【０１０２】
近傍テーブル群作成処理が開始されると、近傍テーブル群作成部１４の初期化処理部６１（図７）は、ステップＳ３１において、処理対象のベクトルグループを示す変数ｊ（０≦ｊ≦Ｍ−１）の値、処理対象の共通代表点を示す変数ｈ（０≦ｈ≦Ｒ−１）の値、および処理対象のメンバベクトルを示す変数ｉ（０≦ｉ≦Ｎ−１）の値をそれぞれ初期値（例えば「０」）に設定する等の初期化処理を行う。なお、Ｍ、Ｒ、およびＮはそれぞれ任意の自然数である。
【０１０３】
ステップＳ３２において、近傍テーブル群作成制御部６２は、Ｍ個全てのベクトルグループについて近傍テーブルを作成したか否かを判定し、まだ近傍テーブルを未作成のベクトルグループが存在すると判定した場合、その判定結果を近傍テーブル作成部６３に供給し、処理をステップＳ３３に進める。ステップＳ３３において、近傍テーブル作成部６３は、ベクトルグループＳ（ｊ）の近傍テーブルを作成する。この近傍テーブルの作成処理の詳細については後述する。
【０１０４】
近傍テーブルを作成すると近傍テーブル作成部６３は、その作成した近傍テーブルを近傍テーブル記憶制御部６４に供給し、処理をステップＳ３４に進める。
【０１０５】
ステップＳ３４において近傍テーブル記憶制御部６４は、その作成した近傍テーブルを取得すると、それを近傍テーブル群記憶部１５に供給し、既に記憶されている他のベクトルグループの近傍テーブルにより構成される近傍テーブル群（１つまたは複数の近傍テーブル）に追加するように記憶させる。近傍テーブル群記憶部１５は、その制御に基づいて、供給された近傍テーブルを既に記憶している近傍テーブル群に追加するように記憶する。なお、近傍テーブル群記憶部１５が１つも近傍テーブルを記憶しておらず、供給された近傍テーブルが１つ目の近傍テーブルの場合、近傍テーブル群記憶部１５は、その供給された近傍テーブルを新たな近傍テーブル群として記憶する。
【０１０６】
ステップＳ３４の処理を終了すると近傍テーブル記憶制御部６４は、処理結果を近傍テーブル群作成制御部６２に返す。近傍テーブル群作成制御部６２は、ステップＳ３５において変数ｊの値に「＋１」を加算し、近傍テーブルを作成する処理対象ベクトルグループを変更する。
【０１０７】
以上のように、近傍テーブル群作成制御部６２、近傍テーブル作成部６３、および近傍テーブル記憶制御部６４は、近傍テーブル群作成制御部６２がステップＳ３２において全てのベクトルグループの近傍テーブルを作成した（Ｍ個の近傍テーブルを作成した）と判定するまで、ステップＳ３２乃至ステップＳ３５の処理を繰り返す。そして、ステップＳ３２において全てのベクトルグループの近傍テーブルを作成したと判定した場合、近傍テーブル群作成制御部６２は、近傍テーブル群作成処理を終了する。
【０１０８】
このように近傍テーブル群作成処理を実行することにより近傍テーブル群作成処理部１４は、各ベクトルグループについて近傍テーブルを作成する（Ｍ個の近傍テーブルからなる近傍テーブル群を作成する）ことができる。その際、各ベクトルグループに共通の共通代表点を用いることにより、近傍テーブル群作成処理部１４は、検索対象のベクトル集合（ベクトルグループ）が複数存在する場合であっても、それぞれの近傍テーブルを高速に作成することができる。また、この近傍テーブル群を入力ベクトルの最近傍ベクトルの検索に用いることにより、特徴量比較装置１０は、検索対象のベクトル集合が複数存在する場合であっても、各集合から入力ベクトルの近傍ベクトルを高速に検索することができる。
【０１０９】
次に、図１５のステップＳ３３において、近傍テーブル作成部６３（図７）が実行する近傍テーブル作成処理の流れの詳細について図１６のフローチャートを参照して説明する。
【０１１０】
近傍テーブル作成処理が開始されると、近傍テーブル作成部６３の近傍テーブル作成制御部８１（図８）は、ステップＳ５１において、Ｒ個全ての共通代表点のレコードを作成したか否かを判定する。近傍テーブルは、図３を参照して説明したように、各共通代表点に対応するレコードにより構成される。近傍テーブル作成制御部８１は、その共通代表点の近傍ベクトルが全て（Ｋ個（Ｋは任意の自然数））求められ、Ｒ個のレコードの作成が完了し、近傍テーブルが完成したか否かを判定する。まだレコードを作成していない（近傍テーブルを求めていない）共通代表点が存在し、全ての共通代表点のレコードを作成していないと判定した場合、近傍テーブル作成制御部８１は、処理をステップＳ５２に進める。
【０１１１】
ステップＳ５２において、距離情報作成部８２は、処理対象の共通代表点Ｃ（ｈ）と各ベクトルＶｍ（処理対象のベクトルグループのメンバベクトルのそれぞれ）との距離情報（共通代表点Ｃ（ｈ）とメンバベクトルＶｍとの距離の２分の１）を作成する。この距離情報の作成処理の詳細は後述する。距離情報作成部８２は、距離情報を作成するとそれを距離情報ソート部８３に供給し、処理をステップＳ５３に進める。ステップＳ５３において、距離情報ソート部８３は、作成した距離情報を距離が短い順（値の小さい順）にソートし、そのソート結果を距離情報抽出部８４に供給する。距離情報抽出部８４は、ステップＳ５４において距離の短い方からＫ個分の距離情報を抽出し、その抽出した距離情報をレコード保持部８５に供給する。
【０１１２】
レコード保持部８５は、ステップＳ５５において、この距離情報抽出部８４が抽出した距離情報群を、現在処理対象とされているグループＳ（ｊ）の近傍テーブルに、共通代表点Ｃ（ｈ）のレコードとして追加するように保持する。すなわち、レコード保持部８５は、距離情報抽出部８４より供給された距離情報群を近傍テーブルのレコードとして保持する。
【０１１３】
レコード保持部８５は、その処理結果を近傍テーブル作成制御部８１に返す。近傍テーブル作成制御部８１は、ステップＳ５６において変数ｈの値に「＋１」を加算し、処理対象共通代表点を変更し、処理をステップＳ５１に戻し、それ以降の処理を繰り返す。
【０１１４】
つまり、近傍テーブル作成制御部８１、距離情報作成部８２、距離情報ソート部８３、距離情報抽出部８４、およびレコード保持部８５は、ステップＳ５１において近傍テーブル作成制御部８１が全ての共通代表点のレコードを作成したと判定するまで、ステップＳ５１乃至ステップＳ５６の処理を繰り返す。
【０１１５】
そして、ステップＳ５１において、全ての共通代表点のレコードが作成され、処理対象のベクトルグループについて近傍テーブルが作成されたと判定した場合、近傍テーブル作成制御部８１は、近傍テーブル作成処理を終了し、レコード保持部８５が保持しているレコード群を近傍テーブルとして近傍テーブル記憶制御部６４（図７）に供給させ、処理を図１５のステップＳ３３に戻し、ステップＳ３４以降の処理を実行させる。
【０１１６】
次に、図１６のステップＳ５２において、距離情報作成部８２（図８）が実行する距離情報作成処理の流れの詳細について図１７のフローチャートを参照して説明する。
【０１１７】
距離情報作成処理が開始されると、距離情報作成部８２の距離情報作成制御部１０１（図９）は、ステップＳ７１において、現在処理対象とされる共通代表点Ｃ（ｈ）について、現在処理対象とされるベクトルグループＳ（ｊ）内のＮ個全てのメンバベクトルＶｍ（ｉ，ｊ）の距離情報を作成したか否かを判定する。まだ距離情報を作成していないメンバベクトルＶｍ（ｉ，ｊ）が存在し、Ｒ個全ての共通代表点のレコードを作成していないと判定した場合、距離情報作成制御部１０１は、処理をステップＳ７２に進める。
【０１１８】
距離算出部１０２は、ステップＳ７２において、現在処理対象とされている共通代表点Ｃ（ｈ）とメンバベクトルＶｍ（ｉ，ｊ）との距離を算出する。例えば、共通代表点Ｃ（ｈ）およびメンバベクトルＶｍ（ｉ，ｊ）が１つの平面上に存在し、ｘ座標およびｙ座標でその位置が示される場合、共通代表点Ｃ（ｈ）の座標を（ｘ１，ｙ１）とし、メンバベクトルＶｍ（ｉ，ｊ）の座標を（ｘ２，ｙ２）とすると、共通代表点Ｃ（ｈ）とメンバベクトルＶｍ（ｉ，ｊ）との距離Ｄcm（ｈ，ｉ，ｊ）は以下の式（１）により示される。
【０１１９】
Ｄcm＝√（ｘ１−ｘ２）2＋（ｙ１−ｙ２）2      ・・・（１）
【０１２０】
すなわち、距離Ｄcmは各座標の差の２乗の総和の平方根で示される。距離算出部１０２は、このように距離を算出するとそれを１／２乗算部１０３に供給する。１／２乗算部１３は、ステップＳ７３において、その算出された距離に１／２を乗算し、Ｄcm／２を算出し、その乗算結果を距離情報保持部１０４に供給する。
【０１２１】
距離情報保持部１０４は、ステップＳ７４において、その乗算結果をメンバベクトルＶｍ（ｉ，ｊ）の距離情報として保持し、その処理結果を距離情報作成制御部１０１に返す。距離情報作成制御部１０１は、ステップＳ７５において、処理対象のメンバベクトルＶｍを示す変数ｉの値に「＋１」を加算し、処理対象メンバベクトルを変更する。処理対象メンバベクトルを変更すると距離情報作成制御部１０１は、処理をステップＳ７１に戻し、新たな処理対象メンバベクトルについて、それ以降の処理を繰り返す。
【０１２２】
つまり、距離情報作成制御部１０１、距離算出部１０２、１／２乗算部１０３、および距離情報保持部１０４は、ステップＳ７１において距離情報作成制御部１０１が全てのメンバベクトルの距離情報を作成したと判定するまでステップＳ７１乃至ステップＳ７５の処理を繰り返す。
【０１２３】
そして、ステップＳ７１において、現在処理対象とされる共通代表点Ｃ（ｈ）について、現在処理対象とされるベクトルグループＳ（ｊ）内のＮ個全てのメンバベクトルＶｍ（ｉ，ｊ）の距離情報を作成したと判定した場合、距離情報作成制御部１０１は、距離情報作成処理を終了し、距離情報保持部１０４が保持している距離情報を距離情報ソート部８３（図８）に供給させ、図１６のステップＳ５２に処理を戻し、ステップＳ５３以降の処理を実行させる。
【０１２４】
図１の特徴量比較装置１０の最近傍ベクトル群検索部１６は、近傍テーブル群記憶部１５に記憶されている近傍テーブル群、共通代表点情報記憶部１３に記憶されている共通代表点の情報、およびベクトル情報記憶部１１に記憶されているベクトル情報に基づいて、入力ベクトルに対する最近傍ベクトルをベクトルグループ（モデル）毎に検索し、それらを最近傍ベクトル群として出力する。この最近傍ベクトル群検索処理の流れを図１８のフローチャートを参照して説明する。入力ベクトルが入力され、最近傍ベクトル群検索処理が開始されると、最近傍ベクトル群検索部１６の初期化処理部１２１は、ステップＳ９１において、ベクトル情報記憶部１１よりベクトル情報を取得し、共通代表点情報記憶部１３より共通代表点の情報を取得し、近傍テーブル群記憶部１５より近傍テーブル群を取得し、さらに、処理対象のベクトルグループを示す変数ｊの値、処理対象の共通代表点を示す変数ｈの値、並びに、処理対象のメンバベクトルを示す変数ｉおよび変数ｋの値をそれぞれ初期値（例えば「０」）に設定する等の初期化処理を行う。
【０１２５】
最近傍ベクトル群検索制御部１２２は、ステップＳ９２において、Ｍ個全てのベクトルグループ（モデル）について入力ベクトルの最近傍ベクトルを検索したか否かを判定し、未処理のベクトルグループが存在すると判定した場合、その判定結果を最近傍ベクトル検索部１２３に供給し、処理をステップＳ９３に進める。ステップＳ９３において、最近傍ベクトル検索部１２３は、処理対象のベクトルグループについて入力ベクトルの最近傍ベクトルを検索する処理を実行する。この最近傍ベクトル検索処理の詳細については後述する。最近傍ベクトル検索部１２３は、最近傍ベクトルを検索するとその検索結果を最近傍ベクトル群検索制御部１２２に供給し、処理をステップＳ９４に進める。ステップＳ９４において、最近傍ベクトル群検索制御部１２２は、変数ｊの値に「＋１」を加算し、処理対象ベクトルグループを変更し、処理をステップＳ９１に戻し、新たな処理対象ベクトルグループについてそれ以降の処理を繰り返す。
【０１２６】
すなわち、最近傍ベクトル群検索制御部１２２および最近傍ベクトル検索部１２３は、ステップＳ９２において最近傍ベクトル群検索制御部１２２がＭ個全てのベクトルグループについて最近傍ベクトルを検索したと判定するまでステップＳ９２乃至ステップＳ９４の処理を繰り返す。
【０１２７】
そして、ステップＳ９２において、全てのベクトルグループについて入力ベクトルの最近傍ベクトルを検索し、全ての最近傍ベクトル群が得られたと判定した場合、最近傍ベクトル群検索制御部１２２は、最近傍ベクトル群を出力し、最近傍ベクトル群検索処理を終了する。
【０１２８】
このように最近傍ベクトル群検索部１６が入力ベクトルの最近傍ベクトルを各ベクトルグループ（モデル）に対して検索し、最近傍ベクトル群を出力することにより、特徴量比較装置１０は、複数のモデルが存在する場合であっても、容易に各モデルの特徴と入力情報の特徴を比較することができる。
【０１２９】
次に、図１８のステップＳ９３において、最近傍ベクトル検索部１２３（図１０）が実行する最近傍ベクトル検索処理の流れの詳細について図１９のフローチャートを参照して説明する。
【０１３０】
最近傍ベクトル検索処理が開始されると、最近傍ベクトル検索部１２３の初期化処理部１４１（図１１）は、ステップＳ１１１において、処理対象の共通代表点を示す変数ｈの値、並びに処理対象のメンバベクトルを示す変数ｉおよび変数ｋの値をそれぞれ初期値（例えば「０」）に設定する等の初期化処理を行う。
【０１３１】
ステップＳ１１２において、最近傍ベクトル検索制御部１４２は、Ｒ個全ての共通代表点Ｃ（ｈ）について最近傍ベクトルの存在判定を行ったか否かを判定する。全ての共通代表点Ｃ（ｈ）について最近傍ベクトルの存在判定を行っていない、すなわち、未処理の共通代表点が存在すると判定した場合、最近傍ベクトル検索制御部１４２は、その判定結果を距離算出部１４３に供給し、処理をステップＳ１１３に進める。
【０１３２】
ステップＳ１１３において、距離算出部１４３は、入力ベクトルＶinと共通代表点Ｃ（ｈ）との距離Ｄinc（ｈ）を算出し、その算出結果を距離比較部１４４に供給する。距離算出部１４３は、上述した式（１）、すなわち、共通代表点とメンバベクトルとの距離の場合と同様に、各座標の差の２乗の総和の平方根を算出する。
【０１３３】
距離比較部１４４は、ステップＳ１１４において、距離Ｄinc（ｈ）を、近傍テーブルの共通代表点Ｃ（ｈ）のレコードの距離情報の最大値と比較し、ステップＳ１１５において距離Ｄinc（ｈ）の方が短いか否かを判定する。そして距離Ｄinc（ｈ）よりも近傍テーブルの共通代表点Ｃ（ｈ）のレコードの距離情報の最大値の方が短いと判定した場合、距離比較部１４４は、その比較結果を最近傍ベクトル検索制御部１４２に返し、処理をステップＳ１１６に進める。
【０１３４】
ステップＳ１１６において、最近傍ベクトル検索制御部１４２は、変数ｈの値に「＋１」を加算し、処理対象共通代表点Ｃ（ｈ）を変更し、処理をステップＳ１１２に戻し、新たな共通代表点Ｃ（ｈ）についてステップＳ１１２以降の処理を実行する。
【０１３５】
つまり、最近傍ベクトル検索制御部１４２、距離算出部１４３、および距離比較部１４４は、ステップＳ１１２において最近傍ベクトル検索制御部１４２が全ての共通代表点Ｃ（ｈ）について最近傍ベクトルの存在判定を行ったと判定するか、ステップＳ１１５において距離比較部１４４が距離Ｄinc（ｈ）の方が近傍テーブルの共通代表点Ｃ（ｈ）のレコードの距離情報の最大値よりも短いと判定するまで、ステップＳ１１２乃至ステップＳ１１６の処理を繰り返す。
【０１３６】
そして、ステップＳ１１５において、距離Ｄinc（ｈ）の方が近傍テーブルの共通代表点Ｃ（ｈ）のレコードの距離情報の最大値よりも短いと判定した場合、距離比較部１４４は、その判定結果をテーブル内検索部１４５に供給し、処理をステップＳ１１７に進める。ステップＳ１１７において、テーブル内検索部１４５は、処置対象の近傍テーブル内において入力ベクトルに最も近いベクトルを検索する。すなわち、テーブル内検索部１４５は、入力ベクトルの最近傍ベクトルの検索範囲を近傍テーブルに登録された近傍ベクトルに限定し、それらの近傍ベクトルの中から最近傍ベクトルを検索する。この最近傍ベクトルのテーブル内検索処理の流れの詳細については後述する。
【０１３７】
テーブル内検索部１４５は、ステップＳ１１７の処理を終了すると、検索結果を最近傍ベクトル設定部１４６に供給する。最近傍ベクトル１４６は、ステップＳ１１８において、その検索結果として供給された、テーブル内検索部１４５により検索されたベクトルを最近傍ベクトルに設定し、その最近傍ベクトルを最近傍ベクトル群検索制御部１２２に供給し、最近傍ベクトル検索処理を終了して処理を図１８のステップＳ９３に戻し、ステップＳ９４以降の処理を実行させる。
【０１３８】
つまり、近傍テーブルにおいて、入力ベクトルとの距離が、そのレコードの距離情報の最大値（距離の２分の１）よりも短くなる共通代表点が存在する場合、テーブル内検索部１４５は、その共通代表点の近傍ベクトル（近傍テーブルに登録されたメンバベクトル）の中から入力ベクトルの最近傍ベクトルを検索する。
【０１３９】
また、ステップＳ１１２において、全ての共通代表点Ｃ（ｈ）について最近傍ベクトルの存在判定を行ったと判定した場合、すなわち、近傍テーブルにおいて、入力ベクトルとの距離が、そのレコードの距離情報の最大値（距離の２分の１）よりも短くなる共通代表点が存在しない場合、最近傍ベクトル検索制御部１４２は、その判定結果をグループ内全体検索部１４７に供給し、処理をステップＳ１１９に進める。
【０１４０】
ステップＳ１１９において、グループ内全体検索部１４７は、グループ内の全てのメンバベクトルから入力ベクトルに最も近いベクトル（最近傍ベクトル）を検索する。そして、グループ内全体検索部１４７は、その検索結果を最近傍ベクトル設定部１４６に供給し、処理をステップＳ１１８に戻し、それ以降の処理を実行させる。
【０１４１】
この場合、最近傍ベクトル設定部１４６は、ステップＳ１１８において、その検索結果として供給された、グループ内全体検索部１４７により検索されたメンバベクトルを最近傍ベクトルに設定し、その最近傍ベクトルを最近傍ベクトル群検索制御部１２２に供給し、最近傍ベクトル検索処理を終了して処理を図１８のステップＳ９３に戻し、ステップＳ９４以降の処理を実行させる。
【０１４２】
以上のように、最近傍ベクトル検索部１２３は、入力ベクトルと共通代表点との距離に応じて最近傍ベクトルの検索範囲を近傍ベクトル内か若しくはベクトルグループ全体に設定し、その検索範囲で検索処理を行う。このようにすることにより、入力ベクトルが共通代表点のいずれかに近い場合、具体的には、入力ベクトルと共通代表点との距離が、近傍テーブルのその共通代表点のレコードに登録されている距離情報（共通代表点と近傍ベクトルとの距離の２分の１）の最大値より短くなる共通代表点が存在する場合、最近傍ベクトル検索部１２３は、最近傍ベクトルの検索範囲をその共通代表点の近傍ベクトルに限定することができるので、不要な候補（明らかに最近傍ベクトルとならないメンバベクトル）を検索範囲より除去し、最近傍ベクトルを高速に検索することができる。
【０１４３】
また、上述したように処理を行うことにより、ベクトルグループの全てのメンバベクトルを検索範囲とする必要があるグループのみベクトルグループ全体に対して検索処理を行い、明らかに不要なメンバベクトルが存在するベクトルグループに対しては、近傍ベクトル内に対する検索処理に切り替えることができる。つまり、最近傍ベクトル検索部１２３は、検索対象のベクトル集合が複数存在する場合であっても、検索の精度を低下させることなく、各集合から入力ベクトルの近傍ベクトルを高速に検索することができるようにするものである。
【０１４４】
次に、図１９のステップＳ１１７において、テーブル内検索部１４５（図１１）が実行するテーブル内検索処理の流れの詳細について図２０のフローチャートを参照して説明する。
【０１４５】
最初に、テーブル内検索処理が開始されると、テーブル内検索部１４５の初期化処理部１６１（図１２）は、ステップＳ１３１において、処理対象の近傍ベクトルを示す変数ｋの値をそれぞれ初期値（例えば「０」）に設定したり、データ保持部１６５が保持する最近傍ベクトルの候補Ｖkeepを入力ベクトルから無限遠の仮想点に設定したり、その最近傍ベクトルの候補Ｖkeepの入力ベクトルからの距離Ｄkeepを無限遠に設定したりする等の初期化処理を行う。
【０１４６】
テーブル内検索制御部１６２は、ステップＳ１３２において、レコードに含まれるＫ個全ての近傍ベクトルＶt（ｋ）（０≦ｋ≦Ｋ−１）について検索したか否かを判定する。未処理の近傍ベクトルＶt（ｋ）が存在すると判定した場合、テーブル内検索制御部１６２は、判定結果を距離算出部１６３に供給し、処理をステップＳ１３３に進める。
【０１４７】
ステップＳ１３３において、距離算出部１６３は、入力ベクトルＶinと処理対象の近傍ベクトルＶt（ｋ）との距離Ｄint（ｋ）を算出し、算出結果を更新制御部１６４に供給し、処理をステップＳ１３４に進める。
【０１４８】
ステップＳ１３４において更新制御部１６４は、距離Ｄint（ｋ）が、入力ベクトルＶinと最近傍ベクトル候補Ｖkeepとの距離Ｄkeepより短いか否かを判定する。距離Ｄint（ｋ）が、距離Ｄkeepより短いと判定した場合、更新制御部１６４は、処理対象の近傍ベクトルＶt（ｋ）と距離Ｄint（ｋ）の情報をデータ保持部１６５に供給し、ステップＳ１３５に処理を進める。ステップＳ１３５において、データ保持部１６５は、保持している最近傍ベクトルの候補Ｖkeepとその入力ベクトルからの距離Ｄkeepの情報を、供給された近傍ベクトルＶt（ｋ）と距離Ｄint（ｋ）の情報を用いて更新する。
【０１４９】
更新制御部１６４は、その制御結果をテーブル内検索制御部１６２に返し、処理をステップＳ１３６に進める。また、ステップＳ１３４において距離Ｄint（ｋ）が、入力ベクトルＶinと保持しているベクトルＶkeepとの距離Ｄkeepより長いと判定した場合、更新制御部１６４は、ステップＳ１３５の処理を省略し、その制御結果をテーブル内検索制御部１６２に返し、ステップＳ１３６に処理を進める。
【０１５０】
ステップＳ１３６において、テーブル内検索制御部１６２は、変数ｋの値に「＋１」を加算し、処理対象近傍ベクトルＶt（ｋ）を変更し、処理をステップＳ１３２に戻し、新たな処理対象近傍ベクトルＶt（ｋ）について、それ以降の処理を繰り返す。
【０１５１】
すなわち、テーブル内検索制御部１６２、距離算出部１６３、更新制御部１６４、およびデータ保持部１６５は、テーブル内検索制御部１６２がステップＳ１３２においてレコードに含まれる全ての近傍ベクトルＶt（ｋ）について検索したと判定するまでステップＳ１３２乃至ステップＳ１３６の処理を繰り返す。
【０１５２】
そして、ステプＳ１３２において、レコードに含まれる全ての近傍ベクトルＶt（ｋ）について検索したと判定した場合、テーブル内検索制御部１６２は、データ保持部１６５が保持している最近傍ベクトルの候補Ｖkeepおよびその入力ベクトルからの距離Ｄkeepの情報を検索結果として最近傍ベクトル設定部１４６に供給させ、テーブル内検索処理を終了し、図１９のステップＳ１１７に処理を戻し、ステップＳ１１８以降の処理を実行させる。
【０１５３】
次に、図１９のステップＳ１１９において、グループ内全体検索部１４７（図１１）が実行するグループ内全体検索処理の流れの詳細について図２１のフローチャートを参照して説明する。
【０１５４】
最初に、グループ内全体検索処理が開始されると、グループ内全体検索部１４７の初期化処理部１８１（図１３）は、ステップＳ１５１において、処理対象のメンバベクトルを示す変数ｉの値をそれぞれ初期値（例えば「０」）に設定したり、データ保持部１８５が保持する最近傍ベクトルの候補Ｖkeepを入力ベクトルから無限遠の仮想点に設定したり、その最近傍ベクトルの候補Ｖkeepの入力ベクトルからの距離Ｄkeepを無限遠に設定したりする等の初期化処理を行う。
【０１５５】
ステップＳ１５２において、グループ内全体検索制御部１８２は、グループに含まれるＮ個全てのメンバベクトルＶm（ｉ，ｊ）について処理を行ったか否かを判定する。未処理のメンバベクトルＶm（ｉ，ｊ）が存在すると判定した場合、グループ内全体検索制御部１８２は、判定結果を距離算出部１８３に供給し、処理をステップＳ１５３に進める。
【０１５６】
ステップＳ１５３において、距離算出部１８３は、入力ベクトルＶinと処理対象のメンバベクトルＶm（ｉ，ｊ）との距離Ｄint（ｉ）を算出し、算出結果を更新制御部１８４に供給し、処理をステップＳ１５４に進める。
【０１５７】
ステップＳ１５４において更新制御部１８４は、距離Ｄint（ｉ）が、入力ベクトルＶinと最近傍ベクトルの候補Ｖkeepとの距離Ｄkeepより短いか否かを判定する。距離Ｄint（ｉ）が、距離Ｄkeepより短いと判定した場合、更新制御部１８４は、処理対象のメンバベクトルＶm（ｉ，ｊ）と距離Ｄint（ｉ）の情報をデータ保持部１８５に供給し、ステップＳ１５５に処理を進める。ステップＳ１５５において、データ保持部１８５は、保持している最近傍ベクトルの候補Ｖkeepと、その入力ベクトルからの距離Ｄkeepの情報を、供給されたメンバベクトルＶm（ｉ，ｊ）と距離Ｄint（ｉ）の情報を用いて更新する。
【０１５８】
更新制御部１８４は、その制御結果をグループ内全体検索制御部１８２に返し、処理をステップＳ１５６に進める。また、ステップＳ１５４において距離Ｄint（ｉ）が、入力ベクトルＶinと保持している最近傍ベクトルＶkeepとその入力ベクトルからの距離Ｄkeepより長いと判定した場合、更新制御部１８４は、ステップＳ１５５の処理を省略し、その制御結果をテーブル内検索制御部１８２に返し、ステップＳ１５６に処理を進める。
【０１５９】
ステップＳ１５６において、テーブル内検索制御部１６２は、変数ｉの値に「＋１」を加算し、処理対象メンバベクトルＶm（ｉ，ｊ）を変更し、処理をステップＳ１５２に戻し、新たな処理対象メンバベクトルＶm（ｉ，ｊ）について、それ以降の処理を繰り返す。
【０１６０】
すなわち、テーブル内検索制御部１６２、距離算出部１６３、更新制御部１６４、およびデータ保持部１６５は、テーブル内検索制御部１６２がステップＳ１３２においてレコードに含まれるＮ個全てのメンバベクトルＶm（ｉ，ｊ）（０≦ｉ≦Ｎ−１）について検索したと判定するまでステップＳ１５２乃至ステップＳ１５６の処理を繰り返す。
【０１６１】
そして、ステップＳ１５２において、ベクトルグループに含まれるＮ個のメンバベクトルＶm（ｉ，ｊ）について全て検索したと判定した場合、グループ内全体検索制御部１８２は、データ保持部１８５が保持している最近傍ベクトルＶkeepおよびその入力ベクトルからの距離Ｄkeepの情報を検索結果として最近傍ベクトル設定部１４６に供給させ、グループ内全体検索処理を終了し、図１９のステップＳ１１９に処理を戻し、ステップＳ１１８以降の処理を実行させる。
【０１６２】
以上のように、図１の特徴量比較装置１０は、各ベクトルグループ（モデル）に共通の代表点を算出し、その共通代表点を用いて近傍テーブルを作成し、それらを用いて入力ベクトルの最近傍ベクトルの検索を行うので、検索対象のベクトル集合が複数存在する場合であっても、各集合から入力ベクトルの近傍ベクトルを高速に検索することができるようにするものである。つまり、特徴量比較装置１０は、検索対象の集合が複数存在する場合であっても、各集合から目的の要素を高速に検索することができる。
【０１６３】
なお、以上において、各パラメータの定数Ｎ、Ｍ、Ｒ、およびＫ等は、互いの大小関係に矛盾が生じない限り任意の自然数であり、ユーザにより指定された値であっても良いし、予め定められた値であってもよい。
【０１６４】
また、本発明は、最近傍ベクトルを検索する入力ベクトルや検索対象のメンバベクトル（モデル）がどのようなベクトル情報であってももちろんよく、さらに、例えばベクトル情報以外の検索にも適用することができる。例えば、集合の中から目的の要素を検索する検索処理であればどのような検索処理であっても本発明を適用することができる。
【０１６５】
また、図１においては、特徴量比較装置１０として説明したが、本発明は複数の装置により構成されるシステムにも適用することができ、例えば、図１の特徴量比較装置１０の各部が互いに異なる装置として構成されるようにしてもよい。図２２は、本発明を適用した特徴量比較システムの構成例を示す図である。
【０１６６】
図２２において、特徴量比較システム２００は、記憶装置２１１、共通代表点設定装置２１２、近傍テーブル群作成装置２１４、および最近傍ベクトル群検索装置２１６を有しており、図１の特徴量比較装置１０と同様の処理を行う。
【０１６７】
記憶装置２１１は、ベクトル情報記憶部１１、共通代表点情報記憶部１３、および近傍テーブル群記憶部１５を内蔵しており、上述した各種の情報をそれぞれの記憶部において記憶する。
【０１６８】
共通代表点設定装置２１２は図１の共通代表点設定部１２に対応し、近傍テーブル群作成装置２１４は図１の近傍テーブル群作成部１４に対応し、最近傍ベクトル群検索装置２１６は図１の最近傍ベクトル群検索部１６に対応し、それぞれ同様の処理を行う。従って、これらの説明については省略する。
【０１６９】
つまり、このように複数の装置により構成される特徴量比較システム２００の場合であっても、図１の特徴量比較装置１０の場合と同様に、本発明を適用することができる。すなわち、特徴量比較システム２００は、検索対象の集合が複数存在する場合であっても、各集合から目的の要素を高速に検索することができる。
【０１７０】
また、図１の特徴量比較装置１０は、他の装置の一部として構成されるようにしてもよい。例えば、特徴量比較装置１０が、画像認識処理等を行う画像処理装置の一部として構成されるようにしてもよい。
【０１７１】
図２３は、本発明を適用した画像処理装置の構成例を示すブロック図である。図２３において、画像処理装置２３０は、入力画像の特徴をベクトル化し、その特徴ベクトルをモデル画像の特徴ベクトルと比較することにより、それらの画像に共通する（または近似する）特徴を検出することにより、入力画像を認識する装置である。
【０１７２】
図２３において画像処理部２３０は、学習部２３１および認識部２３２により構成される。学習部２３１は、モデル画像の特徴ベクトルをモデル辞書として登録する処理を行う処理部であり、特徴点抽出部２４１、特徴量抽出部２４２、およびモデル辞書登録部２４３を有している。
【０１７３】
特徴点抽出部２４１は、モデル画像から予め定められた所定の特徴点を抽出し、それを特徴量抽出部２４２に供給する。特徴量抽出部２４２は、特徴点抽出部２４１において抽出された特徴点の特徴量を抽出し、それを特徴ベクトルとしてモデル辞書登録部２４３に登録する。
【０１７４】
認識部２３２は、入力画像が入力されると、その特徴ベクトルを抽出し、それをモデル画像の特徴ベクトルと比較し、モデルと一致する（近似する）部分を判定する処理部であり、特徴点抽出部２４４、特徴量抽出部２４５、特徴量比較部２４６、およびモデル検出判定部２４７を有している。
【０１７５】
特徴点抽出部２４４は、入力画像から予め定められた所定の特徴点を抽出し、それを特徴量抽出部２４５に供給する。特徴量抽出部２４５は、特徴点抽出部２４４において抽出された特徴点の特徴量を抽出し、それを特徴量比較部２４６に供給する。特徴量比較部２４６は、図１の特徴量比較装置１０と同様の構成を有しており、図１の特徴量比較装置１０と同様の処理を実行することにより、モデル辞書登録部２４３に登録されているモデル画像の特徴ベクトルと入力画像の特徴ベクトルとを比較し、その比較結果をモデル検出判定部２４７に供給する。モデル検出判定部２４７は、この比較結果に基づいて入力画像の特徴をモデル画像において検出できたか否かを判定し、その判定結果を認識処理結果として装置外部に出力する。
【０１７６】
このように、図１の特徴量比較装置１０を特徴量比較部２４６とし、画像処理装置２３０の特徴ベクトルの比較処理に用いるようにするようにしてもよい。この場合も特徴量比較部２４６は上述した特徴量比較装置１０における各処理と同様の処理を実行する。
【０１７７】
さらに、このとき、特徴量比較装置１０の各部（図１）と同様の処理部が特徴量比較部２４６以外として構成されるようにしてもよい。図２４は、図２３の画像処理装置２３０の他の構成例を示すブロック図である。
【０１７８】
図２４の場合、画像処理装置２５０は、図２３の画像処理装置２３０と同様に、学習部２５１および認識部２５２を有している。学習部２５１は、学習部２３１のモデル辞書登録部２４３の代わりに、モデル辞書登録部２６３、共通代表点設定部１２、および近傍テーブル群作成部１４を有している。モデル辞書登録部２６３は、モデル辞書登録部２４３の機能の他に、ベクトル情報記憶部１１、共通代表点情報記憶部１３、および近傍テーブル郡記憶部１５を有している。
【０１７９】
また、認識部２５２は、認識部２３２の特徴量比較部２４６の代わりに最近傍ベクトル群検索部１６を有している。
【０１８０】
つまり、図２３の画像処理装置２３０の場合、図１の特徴量比較装置１０に対応する特徴量比較部２４６は認識部２３２が有しており、図２４の画像処理装置２５０の場合、認識部２５２は、図１の特徴量比較装置１０の最近傍ベクトル群検索部１６のみを有し、図１の特徴量比較装置１０のそれ以外の構成（ベクトル情報記憶部１１、共通代表点設定部１２、共通代表点情報記憶部１３、近傍テーブル群作成部１４、および近傍テーブル郡記憶部１５）は学習部２５１が有している。
【０１８１】
このように、特徴量比較装置１０の各部は、実質的にそれらの処理内容等が変化しない限り（特徴量比較装置１０に対応するように構成されている限り）、どのように画像処理装置２３０に構成されるようにしてもよい。
【０１８２】
また、以上において説明した本発明の特徴量比較の構成を、他の技術と組み合わせるようにしてもよい。例えば、メンバベクトル群の処理をさらに容易にするために、主成分分析を利用した座標変換処理を上述した特徴量比較処理に適用するようにしてもよい。
【０１８３】
図２５は、特徴量比較装置の他の構成例を示すブロック図である。図２５の特徴量比較装置２８０は、図１の特徴量比較装置１０による特徴量比較処理に対して、主成分分析を利用した座標変換処理を適用するようにしたものであり、ベクトル情報記憶部１１、メンバベクトル座標変換部２８１、入力ベクトル座標変換部２８２、最近傍ベクトル群座標変換部２８３、変換座標ベクトル情報記憶部２９１、変換座標共通代表点設定部２９２、変換座標共通代表点情報記憶部２９３、変換座標近傍テーブル群作成部２９４、変換座標近傍テーブル群記憶部２９５、および変換座標最近傍ベクトル群検索部２９６を有している。
【０１８４】
メンバベクトル座標変換部２８１は、ベクトル情報記憶部１１に記憶されているベクトル情報に基づいて後述するように主成分分析を行い、各メンバベクトルの座標を変換する。メンバベクトル座標変換部２８１は、この座標変換された、変換座標上のベクトル情報（変換座標ベクトル情報）を変換座標ベクトル情報記憶部２９１に供給し、記憶させる。また、メンバベクトル座標変換部２８１は、主成分分析結果に関する情報を入力ベクトル座標変換部２８２に供給する。
【０１８５】
入力ベクトル座標変換部２８２は、メンバベクトル座標変換部２８１より供給された主成分分析結果に関する情報に基づいて、入力ベクトルに対してメンバベクトル座標変換部２８１と同様の座標変換処理を行い、その座標変換された変換座標上の入力ベクトル（変換座標入力ベクトル）を変換座標最近傍ベクトル群検索部２９６に供給する。また、入力ベクトル座標変換部２８２は、主成分分析結果に関する情報を最近傍ベクトル群座標変換部２８３に供給する。
【０１８６】
最近傍ベクトル群座標変換部２８３は、変換座標最近傍ベクトル群検索部２９６より供給される変換座標上の最近傍ベクトル群（変換座標最近傍ベクトル群）を取得すると、入力ベクトル座標変換部２８２より供給される主成分分析結果に関する情報に基づいて、その取得した変換座標最近傍ベクトル群に対して入力ベクトル座標変換部２８２に対応する座標変換処理を行い、変換座標最近傍ベクトル群を元の座標系（ベクトル情報記憶部１１に記憶されているベクトル情報の座標系）に変換し、その元の座標系の最近傍ベクトル群を特徴量比較装置２８０の外部に出力する。
【０１８７】
変換座標ベクトル情報記憶部２９１、変換座標共通代表点設定部２９２、変換座標共通代表点情報記憶部２９３、変換座標近傍テーブル群作成部２９４、変換座標近傍テーブル群記憶部２９５、および変換座標最近傍ベクトル群検索部２９６は、それぞれ、図１のベクトル情報記憶部１１、共通代表点設定部１２、共通代表点情報記憶部１３、近傍テーブル群作成部１４、近傍テーブル群１５、および最近傍ベクトル群検索部１６に対応しており、変換座標上において処理を行う以外これらと同様の処理を行う。従って、その説明は省略する。
【０１８８】
次に、図２６を参照し、主成分分析を用いた座標変換について説明する。図２６Ａは、ベクトルグループ２１−１における特徴ベクトル２２（メンバベクトル）の分布の例を示している。図２６Ａに示されるようにベクトルグループ２１−１の特徴ベクトル２２がｘ座標およびｙ座標で示される平面上に分布しているとする。この特徴ベクトル２２は例えば画像情報等の所定の特徴を示すベクトルであるため、この特徴ベクトル２２の分布は均一にならず、所定の偏りが生じる可能性が大きい。例えば、特徴点として画像のエッジ部分が抽出されるようにすると場合、各特徴ベクトル２２にはエッジ部分の特徴が含まれる。つまり、どの特徴ベクトル２２にも同一または近似する特徴が含まれるため、それらの特徴ベクトル２２の分布にも偏りが生じる。
【０１８９】
従って、特徴ベクトル２２の分布には、各特徴ベクトル２２が最も広範囲に分布する方向（すなわち、分布への寄与率が最も高い方向）が存在する。この寄与率が最も高い方向を主成分と称する。
【０１９０】
図２５の特徴量比較装置２８０は、メンバベクトルの分布からこの主成分を分析し、図２６Ｂに示されるように、その主成分を軸とする座標にメンバベクトルの座標を変換する。
【０１９１】
つまり、特徴量比較装置２８０は、図２６Ａに示されるようにｘ座標およびｙ座標で示される座標系に分布されている特徴ベクトル２２の座標を、特徴ベクトル２２の主成分であるｘ’座標およびｘ’座標に垂直なｙ’座標で示される座標系に変換する。図２６Ｂは、座標変換後の特徴ベクトル２２の分布を示している。
【０１９２】
この座標変換により、図２６Ａに示されるように、ｘ座標方向に範囲ａ、ｙ座標方向に範囲ｂと、互いにほぼ同程度であった特徴ベクトル２２の分布が、図２６Ｂに示されるように、ｘ’座標方向にａ’、ｙ’座標方向にｂ’に変化する（ａ’≫ｂ’）。つまり、特徴ベクトル２２の分布は座標変換によりｘ’座標方向に偏ることになる。
【０１９３】
このように主成分分析を行って座標変換することにより、特徴量比較装置２８０は、例えば、図２７に示されるように、メンバベクトルの分布に対して寄与率の低い方向の分布を省略し、次元圧縮することができる。例えば、図２７Ａのようにｘ’軸方向にほぼ直列に分布する特徴ベクトル２２群がベクトルグループ２１−１のメンバベクトルである場合、この特徴ベクトル２２を図２７Ｂのように座標変換すると、特徴ベクトル２２が主成分であるｘ’座標方向にのみ分布し、ｘ’座標に垂直なｙ’座標方向にはほとんど分布していないことがわかる。このような場合、特徴量比較装置２８０は、分布への寄与率が主成分に対して圧倒的に小さいｙ’軸方向への分布を省略し、全ての特徴ベクトル２２がｘ’軸上（１次元上）に存在するものとする。つまり、この場合、特徴量比較装置２８０は、特徴ベクトル２２の分布を２次元上から１次元上に次元圧縮している。このように特徴ベクトルの分布を次元圧縮することにより、特徴量比較装置２８０は、例えばベクトル間の距離演算等において、演算式の次数を削減することができ、演算量を低減させることができる。つまり、特徴量比較装置２８０は、このような次元圧縮することにより、入力ベクトルの最近傍ベクトルの検索処理の負荷を低減させ、高速に処理することができる。
【０１９４】
また、次元圧縮以外にも、特徴量比較装置２８０は、このように主成分分析を行って座標変換することにより、例えば、図２８に示されるように、寄与率の偏りを利用して最近傍ベクトルの検索を高速に行うことができる。
【０１９５】
最近傍ベクトルの検索においては、上述したように、特徴量比較装置２８０は、検索範囲内の各メンバベクトルに対して入力ベクトルまでの距離を１つずつ算出していき、最もその距離が短いものを最近棒ベクトルとする。具体的には、特徴量比較装置２８０は、最初に、最近傍ベクトル候補Ｖkeepの初期値として入力ベクトルからの距離Ｄkeepが無限遠の点を保持する。そして、特徴量比較装置２８０は、検索範囲内の全てのメンバベクトルと入力ベクトルとの距離を１つずつ算出し、その算出された距離が保持している距離Ｄkeepより短い場合、最近傍ベクトル候補Ｖkeepとその入力ベクトルからの距離Ｄkeepを更新する。特徴量比較装置２８０は、このような処理を繰り返し、最終的に保持されていた候補（全てのメンバベクトルを処理した後に保持されていた候補）Ｖkeepを最近傍ベクトルに設定する。
【０１９６】
つまり、図２８Ａに示されるようなベクトルグループ２１において、入力ベクトル２７に対して特徴ベクトル２２Ａが最近傍ベクトルの候補Ｖkeepとして保持されている場合、特徴量比較装置２８０は、まず特徴ベクトル２２Ｂと入力ベクトル２７との距離を算出し、それを特徴ベクトル２２Ａと入力ベクトル２７との距離と比較する。特徴ベクトル２２Ａの方が入力ベクトル２７に近い場合、特徴量比較装置２８０は、次に、特徴ベクトル２２Ｃと入力ベクトル２７との距離を算出し、それを特徴ベクトル２２Ａと入力ベクトル２７との距離と比較する。同様に特徴ベクトル２２Ａの方が入力ベクトル２７に近いとすると、特徴量比較装置２８０は、次に、特徴ベクトル２２Ｄと入力ベクトル２７との距離を算出し、それを特徴ベクトル２２Ａと入力ベクトル２７との距離と比較する。このように特徴量比較装置２８０は、特徴ベクトルと入力ベクトルとの距離を１つずつ算出し、それを現在の最近傍ベクトルの候補と入力ベクトルとの距離と比較する。そして新たに入力ベクトルから最も近いメンバベクトルが検索されれば、特徴量比較装置２８０は、そのメンバベクトルを新たな最近傍ベクトルの候補に設定し、その情報を保持する。
【０１９７】
このとき算出されるベクトル間の距離は、式（１）で示されるように、２点の各座標成分の差の２乗の総和の平方根で示される。この各座標成分の差の２乗は必ず正の値であるので、２つの距離の差の絶対値（どちらの特徴ベクトルが入力ベクトルに近いか）は、この正の値の総和で決定される。つまり、例えば、ある２点間の距離を算出してその大きさをある基準距離と比較する場合、その２点のある座標成分の差の２乗が基準距離の２乗より大きい場合、その２点間の距離は、必ず基準距離より長くなる。
【０１９８】
従って、メンバベクトルと入力ベクトルとの距離を算出する際に、寄与率の高い成分の差の２乗（値が比較的大きい項）から順に算出して加算し、その加算の度に、最近傍ベクトルの候補Ｖkeepの入力ベクトルからの距離Ｄkeepの２乗と比較することにより、特徴量比較装置２８０は、加算結果が距離Ｄkeepの２乗を越えた時点で（寄与率の低い成分の差の２乗（値が比較的小さい項）を加算しなくても）、そのメンバベクトルは最近傍ベクトルの候補とはなりえないので、そのメンバベクトルに対する距離演算を中止し、次のメンバベクトルに対する距離演算に移行することができる。
【０１９９】
換言すると、特徴量比較装置２８０は、メンバベクトルと入力ベクトルとの距離を算出する際に、寄与率の高い順に、２点の座標の各成分の差の２乗を加算していくようにすると、その加算結果は図２８Ｂに示される曲線のようになる。つまり、このように特徴ベクトル２２の分布に成分ごとに偏りを持たせるようにし、上述したように加算を行うことにより、特徴量比較装置２８０は、早い次元の段階において保持している最近傍ベクトルの候補の距離（Ｄkeep）の値を越える可能性を高くすることができ、演算を省略することができる可能性が高くなる。
【０２００】
従って、成分の差の２乗を加算する度にその加算結果と保持している距離（Ｄkeep）の値とを比較するようにすることにより、特徴量比較装置２８０は、距離演算の演算量を削減し、効率良く最近傍ベクトルを検索することができるので、入力ベクトルの最近傍ベクトルを高速に検索することができる。
【０２０１】
次に、図２５の特徴量比較装置２８０の詳細な構成例を説明する。図２９は、図２５のメンバベクトル座標変換部２８１の詳細な構成例を示すブロック図である。図２９において、メンバベクトル座標変換部２８１は、ベクトルグループ統一部３１１、主成分分析部３１２、座標変換部３１３、次元圧縮部３１４、および変換座標ベクトル情報記憶制御部３１５を有している。
【０２０２】
ベクトルグループ統一部３１１は、ベクトル情報記憶部１１より取得したベクトル情報に基づいて、ベクトルグループを統一し、１つのベクトルグループを生成し、その情報を主成分分析部３１２に供給する。
【０２０３】
主成分分析部３１２は、メンバベクトルの分布の主成分分析を行い、その分析結果を座標変換部３１３に供給する。座標変換部３１３は、供給された分析結果に基づいて主成分を座標軸とする座標系に各メンバベクトルを座標変換し、その変換結果を次元圧縮部３１４に供給する。次元圧縮部３１４は、必要に応じて変換座標上のメンバベクトルの分布を次元圧縮し、その処理結果を変換座標ベクトル情報記憶制御部３１５に供給する。変換座標ベクトル情報記憶制御部３１５は、供給された変換座標上のメンバベクトルのベクトル情報である変換座標ベクトル情報を変換座標ベクトル情報記憶部２９１に供給し、記憶させる。
【０２０４】
次に、この特徴量比較装置２８０により実行される特徴量比較処理の流れを図３０のフローチャートを参照して説明する。
【０２０５】
特徴量比較処理が開始されると、メンバベクトル座標変換部２８１は、ステップＳ１７１において、ベクトル情報記憶部１１より供給されたベクトル情報に基づいて全メンバベクトルの分布の主成分を分析し、その分析結果に基づいて各メンバベクトルを座標変換する。このメンバベクトル座標変換処理の詳細については後述する。
【０２０６】
ステップＳ１７２において、変換座標共通代表点設定部２９２は、変換座標ベクトル情報記憶部２９１より変換座標ベクトル情報を取得すると、その変換座標上のベクトル情報に基づいて変換座標上の共通代表点（変換座標共通代表点）を設定する。なお、この変換座標共通代表点設定処理は、変換座標上であること以外は、図１４のフローチャートを参照して説明した共通代表点設定処理と同様であるのでその詳細な説明を省略する。
【０２０７】
ステップＳ１７３において、変換座標近傍テーブル群作成部２９４は、変換座標ベクトル情報記憶部２９１より取得した変換座標上のベクトル情報、および、変換座標共通代表点情報記憶部２９３より取得した変換座標上の共通代表点に基づいて変換座標上の近傍テーブル群（変換座標近傍テーブル群）を作成する。なお、この変換座標近傍テーブル群作成処理は、変換座標上であること以外は、図１５のフローチャートを参照して説明した近傍テーブル群作成処理と同様であるのでその詳細な説明を省略する。
【０２０８】
入力ベクトル座標変換部２８２は、ステップＳ１７４において、入力ベクトルが入力されたか否かを判定し、入力されたと判定した場合、ステップＳ１７５において、メンバベクトル座標変換部２８１より供給された主成分分析結果に関する情報に基づいて、入力ベクトルの座標を変換し、その変換座標上の入力ベクトル（変換座標入力ベクトル）を変換座標最近傍ベクトル群検索部２９６に供給する。
【０２０９】
変換座標最近傍ベクトル検索部２９６は、ステップＳ１７６において、その変換座標上において、供給された変換座標入力ベクトルの最近傍ベクトル群（変換座標最近傍ベクトル群）を検索する。この変換座標最近傍ベクトル検索処理は、変換座標上であること以外は、図１８のフローチャートを参照して説明した最近傍ベクトル群検索処理と同様であるのでその詳細な説明を省略する。変換座標最近傍ベクトル群を検索した変換座標最近傍ベクトル検索部２９６は、それを最近傍ベクトル群座標変換部２８３に供給し、処理をステップＳ１７７に進める。
【０２１０】
ステップＳ１７７において、最近傍ベクトル群座標変換部２８３は、入力ベクトル座標変換部２８２より供給された主成分分析結果に関する情報に基づいて、各変換座標最近傍ベクトルの座標を元の座標系に変換する。最近傍ベクトル群座標変換部２８３は、その変換後の最近傍ベクトル群（元の座標系の最近傍ベクトル群）を特徴量比較結果として特徴量比較装置２８０の外部に出力し、処理をステップＳ１７８に進める。
【０２１１】
また、ステップＳ１７４において入力ベクトルが入力されていないと判定した場合、入力ベクトル座標変換部２８２は、処理をステップＳ１７８に進める。そして、ステップＳ１７８において、最近傍ベクトル群座標変換部２８３は、特徴量比較処理を終了するか否かを判定し、終了しないと判定した場合、処理をステップＳ１７４に戻し、それ以降の処理を繰り返す。
【０２１２】
なお、ステップＳ１７８において、例えばユーザの指示等に基づいて特徴量比較処理を終了すると判定した場合、最近傍ベクトル群座標変換部２８３は、特徴量比較処理を終了する。
【０２１３】
次に、図３０のステップＳ１７１において実行されるメンバベクトル座標変換処理の流れの詳細について図３１のフローチャートを参照して説明する。
【０２１４】
メンバベクトル座標変換処理が開始されるとメンバベクトル座標変換部２８１のベクトルグループ統一部３１１（図２９）は、ステップＳ１９１において、ベクトル情報記憶部１１より供給されたベクトル情報に基づいて、全ベクトルグループを統一し、各ベクトルグループの全部または一部のメンバベクトルからなる１つのベクトルグループを生成し、その情報を主成分分析部３１２に供給し、処理をステップＳ１９２に進める。
【０２１５】
ステップＳ１９２において、主成分分析部３１２は、全メンバベクトルの主成分分析を行い、その分析結果を座標変換部３１３に供給し、処理をステップＳ１９３に進める。ステップＳ１９３において、座標変換部３１３は、その分析結果に基づいて全メンバベクトルの座標を変換し、その変換結果を次元圧縮部３１４に供給し、処理をステップＳ１９４に進める。ステップＳ１９４において、次元圧縮部３１４は、例えばユーザ指示等に基づいて、供給された変換座標メンバベクトルに対して次元圧縮を行うか否かを判定し、行うと判定した場合、ステップＳ１９５に処理を進め、変換座標メンバベクトルの分布に対する寄与率の低い次元（座標）から次元圧縮処理を行い、変換座標メンバベクトルの分布を所望の次元数に次元圧縮する。ステップＳ１９５の処理が終了すると、次元圧縮部３１４は、その処理結果を変換座標ベクトル情報記憶制御部３１５に供給し、処理をステップＳ１９６に進める。
【０２１６】
また、ステップＳ１９４において、次元圧縮を行わないと判定した場合、次元圧縮部３１４は、ステップＳ１９５の処理を省略し、次元圧縮処理を行わずに、変換座標メンバベクトルのベクトル情報をそのまま変換座標ベクトル情報記憶制御部３１５に供給し、処理をステップＳ１９６に進める。
【０２１７】
ステップＳ１９６において、変換座標ベクトル情報記憶制御部３１５は、供給された変換座標ベクトル情報を変換座標ベクトル情報記憶部２９１（図２５）に供給し、記憶させる。変換座標ベクトル情報記憶部２９１は、変換座標ベクトル情報記憶制御部３１５より供給された変換座標ベクトル情報を記憶する。
【０２１８】
ステップＳ１９６の処理を終了すると変換座標ベクトル情報記憶制御部３１５は、メンバベクトル座標変換処理を終了し、処理を図３０のステップＳ１７１に戻し、それ以降の処理を実行させる。
【０２１９】
以上のように、メンバベクトルの分布の主成分を分析し、その分析結果に基づいて各ベクトルの座標変換を行い、特徴量の比較をその変換座標上において行うことにより、特徴量比較装置２８０は、より高速に、各集合から入力ベクトルの近傍ベクトルを検索することができる。つまり、特徴量比較装置２８０は、検索対象の集合が複数存在する場合であっても、各集合から目的の要素をより高速に検索することができる。
【０２２０】
なお、以上においては、１種類の特徴ベクトルの比較処理について説明したが、比較する特徴ベクトルの種類（ベクトルを構成する座標成分の種類）はいくつであってもよく、複数であっても良い。つまり、互いに異なる空間に存在する複数の特徴ベクトルをそれぞれ同じモデルと比較するようにしてもよい。また、比較する特徴ベクトルの種類が複数の場合、各特徴ベクトルの次元数が互いに異なっていてもよい。
【０２２１】
ただし、その場合、単に上述したような比較処理を特徴ベクトル毎に行うようにしても良いが、１種類目の特徴ベクトルの比較処理結果を次に比較する特徴ベクトルの比較処理に利用するようにし、特徴量比較装置が検索処理をより高速に行うことができるようにしてもよい。
【０２２２】
図３２は、複数種類の特徴ベクトルを比較する場合の処理の流れの例を説明する模式図である。
【０２２３】
図３２においては、１つのモデル辞書３３１（最上段）に記憶されているモデル毎に特徴量（モデル特徴量３３２）が抽出され（上から２段目）、そのモデル特徴量３３２の種類毎にベクトルマップが構築される（上から３段目）。図３２においては、特徴量１の３６次元ベクトルマップ構築３３３−１（上から３段目左側）と特徴量２の１８次元ベクトルマップ構築３３３−２（上から３段目右側）が行われる。そして、入力ベクトル３３４（最下段左側）が入力されると、その入力ベクトル３３４の特徴量１の類似ペア群の検索３３５が特徴量１の３６次元ベクトルマップに対して行われ（上から４段目左側）る。
【０２２４】
特徴量１の３６次元ベクトルマップは、例えば、上述したような共通代表点と近傍テーブルを用いて構築されたものであり、その場合、特徴量１の類似ペア群の検索３３５は、例えば図１乃至図２１を参照して上述した最近傍ベクトル検索処理と同様の方法で行われる。つまり、この特徴量１の類似ペア群の検索３３５においては最近傍ベクトル候補の初期値として無限遠の点が設定され、検索範囲内の全てのメンバベクトルと入力ベクトルとの距離が１つずつ算出され、入力ベクトルから最も近いメンバベクトルが検索される度に最近傍ベクトルの候補がそのメンバベクトルに更新される。このような検索処理を繰り返し、ベクトルグループ内の最近傍ベクトルが求められる。
【０２２５】
そして、このような特徴量１の類似ペア群の検索３３５の検索結果として得られた特徴量１の類似ペア群が初期値３３６として利用され（上から４段目中央）、特徴量２の類似ペア群の検索３３７が行われる（上から４段目右側）。このような手順で検索処理が行われることにより、特徴量２の類似ペア群の検索３３７の検索結果が特徴量１および特徴量２の両方における入力ベクトルの近傍ベクトル３３８（２種類の特徴量において入力ベクトルと近似するベクトル）となる。
【０２２６】
特徴量１の類似ペア群の検索３３５のように無限遠の点から検索を行う場合、全てのメンバベクトルが最近傍ベクトルの候補となり得ることになる。従って、このような検索の場合、特徴量比較装置による最近傍ベクトル検索における演算量が比較的多くなってしまう。これに対して、特徴量２の類似ペア群の検索３３７のように、所定の点から検索を行う場合、特徴量比較装置は、明らかに最近傍ベクトルとはならない遠点（所定の点より遠い点）についての演算を省略することができる。
【０２２７】
図３２においては、特徴量比較装置は、特徴量１と特徴量２の両方において入力ベクトルの近傍ベクトルとなるメンバベクトルを検索するので、特徴量１の類似ペア群の検索３３５において近傍ベクトルとならないメンバベクトルを特徴量２の類似ペア群の検索３３７において検索対象とする必要がない。従って、上述したように、特徴量１の類似ペア群の検索３３５における検索結果を特徴量２の類似ペア群の検索３３７の初期値とすることにより、特徴量比較装置は、特徴量２の類似ペア群の検索３３７における演算量を削減することができる。
【０２２８】
さらに、このように特徴量を比較することにより、特徴量比較装置は、特徴量１の類似ペア検索と特徴量２の類似ペア検索を互いに独立して行い、それらの検索結果を改めて比較し、両方を満たすペアを抽出するという複雑な処理を必要とせずに、特徴量１の類似ペア群の検索３３５および特徴量２の類似ペア群の検索３３７を行うのみで特徴量１および特徴量２の両方における入力ベクトルの近傍ベクトル３３８を検索することができ、全体の演算量も削減することができる。
【０２２９】
すなわち、このような検索を行うことにより特徴量比較装置は、例えば、特徴ベクトルを利用した画像認識等において、複数の評価基準で最近傍となる、入力ベクトルに対する最近傍ベクトルを検出する際、複数の評価基準での近傍探索を順列に行い、前段の近傍計算による最近傍ベクトルより近い近傍ベクトルが検出された時点で、複数の評価基準で最近傍となる最近傍ベクトルが存在しないことが確定するので、近傍探索を中断することにより、複数の条件を満たす入力ベクトルの近傍ベクトル（複数の評価基準で最近傍探索）を高速に検索することができる。つまり、この特徴量比較装置は、複数の条件を満たす目的の要素を集合の中から高速に検索することができる。
【０２３０】
以下において、このような特徴量比較方法を適用した装置の例について説明する。
【０２３１】
図３３は、本発明を適用した画像処理装置の他の構成例を説明する図である。
【０２３２】
図３３において、画像処理装置３５０は、学習部３５１および認識部３５２を有している。学習部３５１は、特徴量の比較対象となるモデル画像の特徴を予め準備する処理部であり、複数種類特徴点抽出部３６１、複数種類特徴量抽出部３６２、およびモデル辞書登録部３６３を有している。
【０２３３】
複数種類特徴点抽出部３６１は、入力されたモデル画像から複数種類の特徴点を抽出し、それらとモデル画像を複数種類特徴量抽出部３６２に供給する。なお、複数種類特徴点抽出部３６１は、モデル画像から抽出する特徴点の種類が複数であること以外（例えば、各特徴点の抽出方法等について）は図２３の特徴点抽出部２４１と同様であるのでその詳細の説明は省略する。
【０２３４】
複数種類特徴量抽出部３６２は、複数種類特徴点抽出部３６１において抽出された各特徴点の特徴量をモデル画像より抽出し、モデル特徴量としてモデル辞書登録部３６３に供給する。なお、複数種類特徴量抽出部３６２は、モデル画像から特徴量を抽出する特徴点の種類が複数であること以外（例えば、各特徴点の特徴量の抽出方法等について）は図２３の特徴量抽出部２４２と同様であるのでその詳細の説明は省略する。
【０２３５】
モデル辞書登録部３６３は、複数種類特徴量抽出部３６２より供給されたモデル特徴量群３３２をモデル辞書に登録して保持する。また、モデル辞書登録部３６３は、必要に応じてそのモデル特徴量群３３２を認識部３５２の複数種類特徴量比較部３６６に供給する。なお、モデル辞書登録部３６３は、保持するモデル特徴量の種類が複数であること以外（例えば、各モデル特徴量の保持方法等について）は図２３のモデル辞書登録部２４３と同様であるのでその詳細の説明は省略する。
【０２３６】
認識部３５２は、入力された入力画像の特徴ベクトルを、以上のような学習部３５１においてモデル辞書に登録されたモデル画像の特徴ベクトルと比較することにより、入力画像を認識する処理部であり、特徴点抽出部３６４、特徴量抽出部３６５、複数種類特徴量比較部３６６、およびモデル検出判定部３６７を有している。
【０２３７】
特徴点抽出部３６４は、入力された入力画像より所定の特徴点を抽出し、その特徴点および入力画像を特徴量抽出部３６５に供給する。特徴点抽出部３６４は、図２３の特徴点抽出部２４４と基本的に同様の構成であり同様の処理を行うのでその詳細な説明を省略する。
【０２３８】
特徴量抽出部３６５は、特徴点抽出部３６４において抽出された特徴点の特徴量を抽出し、その特徴量に関する情報を複数種類特徴量比較部３６６に供給する。特徴量抽出部３６５は、図２３の特徴量抽出部２４５と基本的に同様の構成であり同様の処理を行うのでその詳細な説明を省略する。
【０２３９】
複数種類特徴量比較部３６６は、特徴量抽出部３６５より供給された入力画像の特徴量に基づいて入力画像の特徴ベクトル（入力ベクトル）をモデル辞書登録部３６３が保持しているモデル特徴量群３３２と比較し、複数種類の特徴点の全てについて入力ベクトルの近傍ベクトルとなるメンバベクトルを検索することにより、入力画像の特徴とモデル画像の特徴とを比較し、その比較結果をモデル検出判定部３６７に供給する。複数種類特徴量比較部３６６の詳細については後述する。
【０２４０】
モデル検出判定部３６７は、複数種類特徴量比較部３６６における比較結果に基づいて、入力画像よりモデル画像の特徴を検出したか否かを判定する。モデル検出判定部３６７は、図２３のモデル検出判定部２４７と基本的に同様の構成であり同様の処理を行うのでその詳細な説明を省略する。
【０２４１】
図３４は、図３３の複数種類特徴量比較部３６６の詳細な構成例を示すブロック図である。
【０２４２】
図３３において、複数種類特徴量比較部３６６は、特徴量情報取得部３８１、ベクトル情報記憶部３９１、共通代表点設定部３９２、共通代表点情報記憶部３９３、近傍テーブル群作成部３９４、近傍テーブル群記憶部３９５、および近傍ベクトル群検索部３９６を有している。
【０２４３】
特徴量情報取得部３８１は、比較対象となる特徴点の種類を特定する特徴量情報を外部（例えばユーザ入力等）より取得し、それを必要に応じて共通代表点設定部３９２、近傍テーブル群作成部３９４、および近傍ベクトル群検索部３９６に供給する。
【０２４４】
ベクトル情報記憶部３９１、共通代表点設定部３９２、共通代表点情報記憶部３９３、近傍テーブル群作成部３９４、および近傍テーブル群記憶部３９５は、複数種類の特徴ベクトルのそれぞれに対して処理を行うこと以外は、それぞれ、図１のベクトル情報記憶部１１、共通代表点設定部１２、共通代表点情報記憶部１３、近傍テーブル群作成部１４、および近傍テーブル群記憶部１５に対応し、同様の処理を行う。従って、これらの詳細についての説明は省略する。
【０２４５】
近傍ベクトル群検索部３９６は、ベクトル情報記憶部３９１より取得したベクトル情報、共通代表点情報記憶部３９３より取得した共通代表点情報、および近傍テーブル群記憶部３９５より取得した近傍テーブル群に基づいて、入力された入力ベクトル群に対する近傍ベクトル群を検索する。そして、近傍ベクトル群検索部３９６は、その検索結果である近傍ベクトル群をモデル検出判定部３６７（図３３）に供給する。
【０２４６】
図３５は、図３６の近傍ベクトル群検索部３９６の詳細な構成例を示すブロック図である。図３６において、近傍ベクトル群検索部３９６は、初期化処理部４１１、近傍ベクトル群検索制御部４１２、近傍ベクトル検索部４１３、特徴別近傍ベクトル候補設定部４１４、変化フラグ確認部４１５、および近傍ベクトル設定部４１６を有している。
【０２４７】
初期化処理部４１１は、近傍ベクトル群の検索に必要な変数を初期値に設定する等の初期化処理を行う。例えば、初期化処理部４１１は、１つの入力ベクトルに対応する近傍ベクトルである特徴別近傍ベクトルの候補である特徴別近傍ベクトル候補を初期化したり、変数ｊ（０≦ｊ≦Ｍ−１）を初期値（例えば、「０」）に設定したり、特徴別近傍ベクトル候補の変化フラグを初期化したりする。変化フラグについては後述する。
【０２４８】
近傍ベクトル群検索制御部４１２は、検索対象として設定された特徴の全種類について条件を満たす近傍ベクトル群の検索に関する制御処理を行う。近傍ベクトル検索部４１３は、入力された各入力ベクトルについて特徴別近傍ベクトルの検索を行う。このとき、近傍ベクトル検索部４１３は、図１乃至図２１を参照して説明したように、入力ベクトルとモデルのメンバベクトルとの距離を１つずつ算出し、特徴別近傍ベクトルの候補より短い距離のメンバベクトルが検索された場合、特徴別近傍ベクトルの候補の情報を更新し、そのメンバベクトルを新たな特徴別近傍ベクトルの候補とする。近傍ベクトル検索部４１３は、以上のような処理を繰り返し、最終的に保持されている特徴別近傍ベクトルの候補を特徴別近傍ベクトル（検索結果）とする。
【０２４９】
特徴別近傍ベクトル候補設定部４１４は、近傍ベクトル検索部４１３による前回の検索結果（特徴別近傍ベクトル）を、次の検索における特徴別近傍ベクトル候補の初期値に設定する。特徴別近傍ベクトル検索部４１４は、その特徴別近傍ベクトル候補を用いて新たな入力ベクトルに対する特徴別近傍ベクトル検索を行う。
【０２５０】
また、近傍ベクトル検索部４１３は、特徴別近傍ベクトルの検索においてその候補が更新された場合、その更新を示す変化フラグを立てる。近傍ベクトル候補設定部４１４は、この変化フラグの情報を変化フラグ確認部４１５に供給する。
【０２５１】
変化フラグ確認部４１５は、供給された各変化フラグの状態を確認し、その確認結果を近傍ベクトル群検索制御部４１２に供給する。変化フラグは、近傍ベクトル候補が変化したことを示すフラグであり、候補毎に設けられている。つまり、変化フラグが立っている候補は、少なくとも１度は更新された候補であることを示す。
【０２５２】
近傍ベクトル群検索制御部４１２は、この確認結果に基づいて、近傍ベクトル群の検索処理を制御する。例えば、不変の特徴別近傍ベクトル候補が存在しなくなった時点で、近傍ベクトル群検索制御部４１２は近傍ベクトル群の検索処理を終了し、各部を制御して、次のベクトルグループについての検索処理に移行させる。また、例えば、近傍ベクトル検索部４１３が全ての入力ベクトルについて特徴別近傍ベクトルの検索を終了させたときに、変化フラグが立っていない不変の特徴別近傍ベクトル候補が存在する場合、その特徴別近傍ベクトル（候補）を近傍ベクトル設定部４１６に供給する。
【０２５３】
近傍ベクトル設定部４１６は、近傍ベクトル群検索制御部４１２に制御されて、不変であった特徴別近傍ベクトル（候補）を近傍ベクトル（群）として設定する。
【０２５４】
次にこのような画像処理装置３５０（図３３）の複数種類特徴量比較部３６６（図３４）により実行される複数種類特徴量比較処理の流れを図３６のフローチャートを参照して説明する。
【０２５５】
複数種類特徴量比較処理が開始されると、複数種類特徴量比較部３６６の特徴量情報取得部３８１は、ステップＳ２１１において、モデル辞書登録部３６３やユーザ入力等より比較する特徴量（特徴ベクトル）に関する情報を取得する。特徴量情報取得部３８１は、取得したその情報を共通代表点設定部３９２および近傍テーブル群作成部３９４に供給し、処理をステップＳ２１２に進める。
【０２５６】
ステップＳ２１２において共通代表点設定部３９２は、ベクトル情報記憶部３９１より取得したベクトル情報（モデル辞書登録部３６３より供給されベクトル情報記憶部３９１に記憶されていたベクトル情報）に基づいて、特徴量の種類毎に（特徴ベクトルの種類毎に）共通代表点を設定する。共通代表点設定部３９２は、その共通代表点を設定すると、それを共通代表点情報記憶部３９３に供給し、記憶させ、処理をステップＳ２１３に進める。
【０２５７】
ステップＳ２１３において、近傍テーブル群作成部３９４は、ベクトル情報記憶部３９１より取得したベクトル情報（モデル辞書登録部３６３より供給されベクトル情報記憶部３９１に記憶されていたベクトル情報）、および共通代表点情報記憶部３９３より取得した共通代表点情報（ステップＳ２１２の処理により設定された共通代表点）に基づいて、特徴量の種類毎に（特徴ベクトルの種類毎に）近傍テーブルを作成する。近傍テーブル群作成部３９４は、その近傍テーブルを作成すると、それを近傍テーブル群記憶部３９５に供給し、記憶させ、処理をステップＳ２１４に進める。
【０２５８】
ステップＳ２１４において、近傍ベクトル群検索部３９６は、ベクトル情報記憶部３９１より取得したベクトル情報（モデル辞書登録部３６３より供給されベクトル情報記憶部３９１に記憶されていたベクトル情報）、共通代表点情報記憶部３９３より取得した共通代表点情報（ステップＳ２１２の処理により設定された共通代表点）、および近傍テーブル群記憶部３９５より取得した近傍テーブル群に基づいて、入力された入力ベクトル群に対応する近傍ベクトル群を検索する。この近傍ベクトル群検索処理の詳細については後述する。近傍ベクトル群検索部３９６は、近傍ベクトル群を検索すると、その近傍ベクトル群を検索結果として、モデル検出判定部３６７（図３３）に供給し、複数種類特徴量比較処理を終了する。
【０２５９】
次に、図３６のステップＳ２１４において実行される近傍ベクトル群検索処理の流れについて図３７のフローチャートを参照して説明する。
【０２６０】
近傍ベクトル群検索処理が開始されると、近傍ベクトル群検索部３９６の初期化処理部４１１は、ステップＳ２４１において初期化処理を行い、特徴別近傍ベクトル候補を初期値として無限遠の点に設定したり、変化フラグの設定を初期化したり、処理対象のベクトルグループを示す変数ｊの値を初期値（例えば「０」）に設定したりする。初期化処理が終了すると初期化処理部４１１は、その処理結果を近傍ベクトル群検索制御部４１２に供給し、処理をステップＳ２４２に進める。
【０２６１】
ステップＳ２４２において、近傍ベクトル群検索制御部４１２は、全てのベクトルグループについて入力ベクトル群の近傍ベクトル群を検索したか否かを判定し、未検索のベクトルグループが存在すると判定した場合、その判定結果を近傍ベクトル検索部４１３に供給し、処理をステップＳ２４３に進める。
【０２６２】
ステップＳ２４３において、近傍ベクトル検索部４１３は、１つ目の入力ベクトルについて、特徴別近傍ベクトルを検索する。この特徴別近傍ベクトルの検索方法は、どのような方法であってもよく、例えば、図１９のフローチャートを参照して説明した最近傍ベクトル検索処理のような方法であっても良い。また、検索されるベクトルの数は１つでも良いし、複数であってももちろんよい。特徴別近傍のベクトルを検索すると、近傍ベクトル検索部４１３は、その検索結果を近傍ベクトル候補設定部４１４に供給し、処理をステップＳ２４４に進める。
【０２６３】
近傍ベクトル候補設定部４１４は、ステップＳ２４４において、検索されたベクトルを次の検索における特徴別近傍ベクトル候補の初期値として設定し、その情報を近傍ベクトル検索部４１３に供給し、処理をステップＳ２４５に進める。
【０２６４】
ステップＳ２４５において、近傍ベクトル検索部４１３は、次の入力ベクトルについて特徴別近傍ベクトルを検索する。この検索において、近傍ベクトル検索部４１３は、特徴別近傍ベクトル候補より近いベクトルが検索された場合、特徴別近傍ベクトル候補を更新し、その検索されたベクトルを特徴別近傍ベクトル候補とし、その特徴別近傍ベクトル候補に対応する変化フラグを立てる。検索が終了すると、近傍ベクトル検索部４１３は、最終的な特徴別近傍ベクトル候補を特徴別近傍ベクトルとして特徴別近傍ベクトル候補設定部４１４に供給する。また、近傍ベクトル検索部４１３は、変化フラグの情報も特徴別近傍ベクトル候補設定部４１４に供給する。
【０２６５】
ステップＳ２４６において、特徴別近傍ベクトル候補設定部４１４は、ステップＳ２４４の場合と同様に、今回検索されたベクトルをさらに次の検索における特徴別近傍ベクトル候補の初期値として設定する。このとき変化フラグの値はそのままにする。特徴別近傍ベクトル候補設定部４１４は、さらに、その情報を近傍ベクトル検索部４１３に供給するとともに、各特徴別近傍ベクトル候補の変化フラグの情報を変化フラグ確認部４１５に供給し、処理をステップＳ２４７に進める。
【０２６６】
ステップＳ２４７において、変化フラグ確認部４１５は、供給された特徴別近傍ベクトル候補の変化フラグの状態を確認し、その確認結果を近傍ベクトル群検索制御部４１２に供給し、ステップＳ２４８に処理を進める。
【０２６７】
近傍ベクトル群検索制御部４１２は、ステップＳ２４８において、確認結果に基づいて、不変の特徴別近傍ベクトル候補が存在するか否かを判定する。不変の特徴別近傍ベクトル候補が存在すると判定した場合、近傍ベクトル群検索制御部４１２は、処理をステップＳ２４９に進め、入力された入力ベクトル群の全ての入力ベクトルについて特徴別近傍ベクトルを検索したか否かを判定する。
【０２６８】
入力された入力ベクトル群に未処理の入力ベクトルが存在すると判定した場合、近傍ベクトル群検索制御部４１２は、その判定結果を近傍ベクトル検索部４１３に供給するとともに、処理をステップＳ２４５に戻し、次の入力ベクトルに対する処理を実行させる。つまり、近傍ベクトル群検索制御部４１２、近傍ベクトル検索部４１３、特徴別近傍ベクトル候補設定部４１４、および変化フラグ確認部４１５は、近傍ベクトル群検索制御部４１２が、ステップＳ２４８において不変の特徴別近傍ベクトル候補が存在しないと判定するか、ステップＳ２４９において入力された入力ベクトル群の全ての入力ベクトルについて特徴別近傍ベクトルを検索したと判定するまで、ステップＳ２４５乃至ステップＳ２４９の処理を繰り返す。
【０２６９】
そして、ステップＳ２４９において、入力された入力ベクトル群の全ての入力ベクトルについて特徴別近傍ベクトルを検索したと判定した場合、近傍ベクトル群検索制御部４１２は、特徴ベクトル近傍ベクトルを近傍ベクトル設定部４１６に供給し、処理をステップＳ２５０に供給する。
【０２７０】
ステップＳ２５０において、近傍ベクトル設定部４１６は、供給された特徴ベクトル近傍ベクトルの内、不変の特徴別近傍ベクトルを入力ベクトル群の近傍ベクトル群に設定する。設定が終了すると、近傍ベクトル設定部４１６は、その近傍ベクトル群をモデル検出判定部３６７（図３３）に供給し、処理の終了を近傍ベクトル群検索制御部４１２に通知し、処理をステップＳ２５１に進める。
【０２７１】
また、ステップＳ２４８において、全ての特徴別近傍ベクトル候補の変化フラグが立っており、不変の特徴別近傍ベクトル候補が存在しないと判定した場合、近傍ベクトル群検索制御部４１２は、そのベクトルグループには全ての入力ベクトルに対して近傍に位置するベクトルが存在しないと判定し（そのベクトルグループにおいて所望の近傍ベクトル群が得られないと判定し）、そのベクトルグループにおける近傍ベクトル群の検索を終了し、処理をステップＳ２５１に進める。
【０２７２】
ステップＳ２５１において、近傍ベクトル群検索制御部４１２は、変数ｊの値に「＋１」を加算し、処理対象ベクトルグループを変更する。また、近傍ベクトル群検索制御部４１２は、ステップＳ２５２において、特徴別近傍ベクトル候補を初期化し、無限遠の仮想点に設定し、処理をステップＳ２４２に戻し、それ以降の処理を繰り返す。
【０２７３】
つまり、近傍ベクトル群検索制御部４１２、近傍ベクトル検索部４１３、特徴別近傍ベクトル候補設定部４１４、および変化フラグ確認部４１５は、近傍ベクトル群検索制御部４１２がステップＳ２４２において全てのベクトルグループにおいて近傍ベクトル群を検索したと判定するまで、ステップＳ２４２乃至ステップＳ２５２の処理を繰り返す。
【０２７４】
そして、ステップＳ２４２において全てのベクトルグループにおいて近傍ベクトル群を検索したと判定した場合、近傍ベクトル群検索制御部４１２は、近傍ベクトル群検索処理を終了し、処理を図３６のステップＳ２１４に処理を戻し、さらに複数種類特徴量比較処理を終了させる。
【０２７５】
以上のように、複数種類の特徴ベクトルの検索において、１つの特徴ベクトルの検索結果を他の特徴ベクトルの検索に利用することにより、近傍ベクトル検索部３９６は、不要な演算量を削減することができ、より高速に入力ベクトル群の近傍ベクトル群を検索することができる。つまり、近傍ベクトル検索部３９６は、検索対象のベクトル集合が複数存在し、さらに、複数種類の入力ベクトルからなる入力ベクトル群を検索対象のベクトル集合と比較する場合であっても、各ベクトル集合から入力ベクトル群の近傍ベクトル群を高速に検索することができる。
【０２７６】
従って、画像処理装置３５０は、検索対象のベクトル集合が複数存在し、さらに、複数種類の入力ベクトルからなる入力ベクトル群を検索対象のベクトル集合と比較する場合であっても、各ベクトル集合から入力ベクトル群の近傍ベクトル群を高速に検索することができる。つまり、画像処理装置３５０は、検索対象の集合が複数存在し、さらに、複数種類の要素を検索する場合であっても、各集合から目的の要素群を高速に検索することができる。
【０２７７】
なお、以上においては、検索対象のベクトルグループ（モデル）が複数存在する場合について説明したが、図３２乃至図３７を参照して説明した、検索対象と比較する特徴の種類が複数の場合の検索方法は、検索対象のベクトルグループ（モデル）が１つの場合であっても適用することができる。つまり、この１つの特徴ベクトルの検索結果を他の特徴ベクトルの検索に利用する検索方法は、比較する特徴の種類（入力ベクトルの種類）が複数であればよく、モデルとなるベクトルグループの数には依存しない。
【０２７８】
従って、画像処理装置３５０は、検索対象と複数種類の特徴を比較する場合、互いに種類が異なる入力ベクトルからなる入力ベクトル群の近傍ベクトル群を高速に検索することができる。つまり、画像処理装置３５０は、検索対象と複数種類の特徴を比較する場合であっても、目的の要素群を検索対象の集合から高速に求めることができる。
【０２７９】
なお、以上において説明した各装置は、例えば上述した処理部単位で分割された複数の装置により構成されるようにしてもよい。もちろん、分割単位はどのような単位であってもよく処理部単位以外の単位であってもよい。また、複数の装置として説明したものを１つの装置として構成するようにしてもよい。また、上述していない機能を上述した装置にさらに組み合わせるようにしてもよい。また、矛盾や不具合等が生じない限り、上述した機能（処理部）の一部を省略するようにしてもよい。さらに、ある処理部において実行するように説明した処理を他の処理部において実行するようにしてもよい。
【０２８０】
また、本発明を適用した検索処理方法は、画像認識処理以外にも適用可能であり、例えば、音声データやテキストデータ等の画像データ以外のデータに対する情報処理に利用することもできる。
【０２８１】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、図１の特徴量比較装置１０、図２２の特徴量比較システム２００の各装置、図２３の画像処理装置２３０、図２４の画像処理装置２５０、図２５の特徴量比較装置２８０、および図３３の画像処理装置３５０は、図３８に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【０２８２】
図３８において、パーソナルコンピュータ５００のCPU（Central Processing Unit）５０１は、ROM（Read Only Memory）５０２に記憶されているプログラム、または記憶部５１３からRAM（Random Access Memory）５０３にロードされたプログラムに従って各種の処理を実行する。RAM５０３にはまた、CPU５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０２８３】
CPU５０１、ROM５０２、およびRAM５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インタフェース５１０も接続されている。
【０２８４】
入出力インタフェース５１０には、キーボード、マウスなどよりなる入力部５１１、CRT（Cathode Ray Tube）、LCD（Liquid Crystal Display）などよりなるディスプレイ、並びにスピーカなどよりなる出力部５１２、ハードディスクなどより構成される記憶部５１３、モデムなどより構成される通信部５１４が接続されている。通信部５１４は、インターネットを含むネットワークを介しての通信処理を行う。
【０２８５】
入出力インタフェース５１０にはまた、必要に応じてドライブ５１５が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア５２１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５１３にインストールされる。
【０２８６】
上述した一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【０２８７】
この記録媒体は、例えば、図３８に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（ＭＤ（Mini-Disk）（登録商標）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア５２１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM５０２や、記憶部５１３に含まれるハードディスクなどで構成される。
【０２８８】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０２８９】
また、本明細書において、システムとは、複数のデバイス（装置）により構成される装置全体を表すものである。
【図面の簡単な説明】
【０２９０】
【図１】本発明を適用した特徴量比較装置の構成例を示すブロック図である。
【図２】近傍テーブル群作成の様子を説明する図である。
【図３】近傍テーブル群の構成例を示す図である。
【図４】最近傍ベクトルの検索の様子を説明する図である。
【図５】検索範囲の絞り込みの例を説明する図である。
【図６】図１の共通代表点設定部の詳細な構成例を示すブロック図である。
【図７】図１の近傍テーブル群作成部の詳細な構成例を示すブロック図である。
【図８】図７の近傍テーブル作成部の詳細な構成例を示すブロック図である。
【図９】図８の距離情報作成部の詳細な構成例を示すブロック図である。
【図１０】図１の最近傍ベクトル群検索部の詳細な構成例を示すブロック図である。
【図１１】図１０の最近傍ベクトル検索部の詳細な構成例を示すブロック図である。
【図１２】図１１のテーブル内検索部の詳細な構成例を示すブロック図である。
【図１３】図１１のグループ内全体検索部の詳細な構成例を示すブロック図である。
【図１４】共通代表点設定処理の例を説明するフローチャートである。
【図１５】近傍テーブル群作成処理の例を説明するフローチャートである。
【図１６】近傍テーブル作成処理の例を説明するフローチャートである。
【図１７】距離情報作成処理の例を説明するフローチャートである。
【図１８】最近傍ベクトル群検索処理の例を説明するフローチャートである。
【図１９】最近傍ベクトル検索処理の例を説明するフローチャートである。
【図２０】テーブル内検索処理の例を説明するフローチャートである。
【図２１】グループ内全体検索処理の例を説明するフローチャートである。
【図２２】本発明を適用した特徴量比較システムの構成例を示すブロック図である。
【図２３】本発明を適用した画像処理装置の構成例を示すブロック図である。
【図２４】本発明を適用した画像処理装置の他の構成例を示すブロック図である。
【図２５】本発明を適用した特徴量比較装置の他の構成例を示すブロック図である。
【図２６】座標変換の様子を説明する模式図である。
【図２７】次元圧縮の様子を説明する模式図である。
【図２８】ベクトル間距離の比較の様子を説明する図である。
【図２９】図２５のメンバベクトル座標変換部の詳細な構成例を示すブロック図である。
【図３０】特徴量比較処理を説明するフローチャートである。
【図３１】メンバベクトル座標変換処理を説明するフローチャートである。
【図３２】近傍ベクトル群を検索する様子を説明する図である。
【図３３】本発明を適用した画像処理装置のさらに他の構成例を示すブロック図である。
【図３４】図３３の複数種類特徴量比較部の詳細な構成例を示すブロック図である。
【図３５】図３４の近傍ベクトル群検索部の詳細な構成例を示すブロック図である。
【図３６】複数種類特徴量比較処理を説明するフローチャートである。
【図３７】近傍ベクトル群検索処理を説明するフローチャートである。
【図３８】本発明を適用したパーソナルコンピュータの構成例を示す図である。
【符号の説明】
【０２９１】
１０  特徴量装置，  １１  ベクトル情報記憶部，  １２  共通代表点設定部，  １３  共通代表点情報記憶部，  １４  近傍テーブル群作成部，  １５  近傍テーブル群記憶部，  １６  最近傍ベクトル群検索部，  ４１  共通代表点目標数設定部，  ４２  ベクトルグループ統一部，  ４３  重心算出部，  ４４  共通代表点設定部，  ４５  共通代表点数判定部，  ４６  共通代表点分割部，  ４７  メンバベクトル割り当て部，  ４８  共通代表点記憶制御部，  ６１  初期化処理部，  ６２  近傍テーブル群作成制御部，  ６３  近傍テーブル作成部，  ６４  近傍テーブル記憶制御部，  ８１  近傍テーブル作成制御部，  ８２  距離情報作成部，  ８３  距離情報ソート部，  ８４  距離情報抽出部，  ８５  レコード保持部，  １０１  距離情報作成制御部，  １０２  距離算出部，  １０３  １／２乗算部，  １０４  距離情報保持部，  １２１  初期化処理部，  １２２  最近傍ベクトル群検索制御部，  １２３  最近傍ベクトル検索部，  １４１  初期化処理部，  １４２  最近傍ベクトル検索制御部，  １４３  距離算出部，  １４４  距離比較部，  １４５  テーブル内検索部，  １４６  最近傍ベクトル設定部，  １４７  グループ内全体検索部，  １６１  初期化処理部，  １６２  テーブル内検索制御部，  １６３  距離算出部，  １６４  更新制御部，  １６５  データ保持部，  １８１  初期化処理部，  １８２  グループ内全体検索制御部，  １８３  距離算出部，  １８４  更新制御部，  １８５  データ保持部，  ２００  特徴量比較システム，  ２３０  画像処理装置，  ２４６  特徴量比較部，  ２５０  画像処理装置，  ２６３  モデル辞書登録部，  ２８０  特徴量比較装置，  ２８１  メンバベクトル座標変換部，  ２８２  入力ベクトル座標変換部，  ２８３  最近傍ベクトル座標変換部，  ３１１  ベクトルグループ統一部，  ３１２  主成分分析部，  ３１３  座標変換部，  ３１４  次元圧縮部，  ３１５  変換座標ベクトル情報記憶制御部，  ３５０  画像処理装置，  ３６６  複数種類特徴量比較部，  ３８１  特徴量情報取得部，  ４１１  初期化処理部，  ４１２  近傍ベクトル群検索制御部，  ４１３  近傍ベクトル検索部，  ４１４  特徴別近傍ベクトル候補設定部，  ４１５  変化フラグ確認部，  ４１６  近傍ベクトル設定部，  ５００  パーソナルコンピュータ
【図１】
2006190192.tif 000003
【図２】
2006190192.tif 000004
【図３】
2006190192.tif 000005
【図４】
2006190192.tif 000006
【図５】
2006190192.tif 000007
【図６】
2006190192.tif 000008
【図７】
2006190192.tif 000009
【図８】
2006190192.tif 000010
【図９】
2006190192.tif 000011
【図１０】
2006190192.tif 000012
【図１１】
2006190192.tif 000013
【図１２】
2006190192.tif 000014
【図１３】
2006190192.tif 000015
【図１４】
2006190192.tif 000016
【図１５】
2006190192.tif 000017
【図１６】
2006190192.tif 000018
【図１７】
2006190192.tif 000019
【図１８】
2006190192.tif 000020
【図１９】
2006190192.tif 000021
【図２０】
2006190192.tif 000022
【図２１】
2006190192.tif 000023
【図２２】
2006190192.tif 000024
【図２３】
2006190192.tif 000025
【図２４】
2006190192.tif 000026
【図２５】
2006190192.tif 000027
【図２６】
2006190192.tif 000028
【図２７】
2006190192.tif 000029
【図２８】
2006190192.tif 000030
【図２９】
2006190192.tif 000031
【図３０】
2006190192.tif 000032
【図３１】
2006190192.tif 000033
【図３２】
2006190192.tif 000034
【図３３】
2006190192.tif 000035
【図３４】
2006190192.tif 000036
【図３５】
2006190192.tif 000037
【図３６】
2006190192.tif 000038
【図３７】
2006190192.tif 000039
【図３８】
2006190192.tif 000040