"画像を蓄積する画像蓄積手段と、前記画像の近似データを前記画像と対応付けて蓄積する近似データ蓄積手段と、検索対象に類似する近似データを前記近似データ蓄積手段に蓄積された近似データから検索する近似空間検索手段と、前記近似空間検索手段の検索結果に対応する前記画像蓄積手段に蓄積された画像と検索対象との類似度を計算する手段とを備え、前記近似データ蓄積手段に蓄積する前記近似データは、前記画像蓄積手段に蓄積された前記画像同士の関係を保持する様に生成されることを特徴とする画像検索装置。前記近似データ蓄積手段に蓄積されたデータ量は、近似データに対応する画像を蓄積した画像蓄積手段のデータ量より少なく、近似データ蓄積手段は画像蓄積手段に比べ高速アクセス可能であることを特徴とする請求項1に記載の画像検索装置。画像検索装置におけるデータ蓄積装置であって、画像を蓄積する画像蓄積手段と、前記画像を近似した近似データを前記画像蓄積手段に蓄積された画像と対応付けて蓄積する近似データ蓄積手段とを備え、前記近似データ蓄積手段に蓄積されるデータ量は、近似データに対応する画像を蓄積した画像蓄積手段に蓄積されるデータ量より少なく、前記近似データ蓄積手段は前記画像蓄積手段に比べ高速アクセス可能な記憶媒体であり、前記近似データ蓄積手段に蓄積する前記近似データは、前記画像蓄積手段に蓄積された前記画像同士の関係を保持する様に生成されることを特徴とするデータ蓄積装置。請求項3記載のデータ蓄積装置を備えた画像検索装置を用いて、プログラムされたコンピュータにより画像を検索する方法であって、検索対象と類似する近似データを前記近似データ蓄積手段に蓄積された近似データから検索するステップと、検索結果に対応する画像を画像蓄積手段から求めるステップと、検索対象と前記画像蓄積手段から求めた検索結果の画像との類似度を計算するステップとを有する画像検索方法。しかしながら、従来の木構造にする方法では、多次元特徴データの次元数が多くなると、隣接空間が指数関数的に増え、多次元特徴データをクラスタリングするのに膨大な時間を要する。さらに、検索時には、隣接空間も含め近傍検索を行なうため、登録同様、膨大な時間を要する。また、特許文献1に記載の技術においては、射影による次元縮退には限度がある。また、その対策として、目鼻口等の重要度の高い部分のみを使用して類似度計算をする方法も記載されているが、個人の特徴がどこに現れるのかは千差万別で、精度を維持したまま次元を縮退するには限界がある。本発明は、前記従来の事情に鑑みてなされたもので、顔色等の多次元特徴データが高次元で大量に存在する場合でも、ユーザの望む画像を効率よく適切に検索可能な画像検索装置および画像検索方法を実現することを目的とする。本発明の画像検索装置は、画像を蓄積する画像蓄積手段と、前記画像の近似データを前記画像と対応付けて蓄積する近似データ蓄積手段と、検索対象に類似する近似データを前記近似データ蓄積手段に蓄積された近似データから検索する近似空間検索手段と、前記近似空間検索手段の検索結果に対応する前記画像蓄積手段に蓄積された画像と検索対象との類似度を計算する手段とを備え、前記近似データ蓄積手段に蓄積する前記近似データは、前記画像蓄積手段に蓄積された前記画像同士の関係を保持する様に生成されることを特徴とする。また、本発明の画像検索装置は、前記近似データ蓄積手段に蓄積されたデータ量は、近似データに対応する画像を蓄積した画像蓄積手段のデータ量より少なく、近似データ蓄積手段は画像蓄積手段に比べ高速アクセス可能であることを特徴とする。また、本発明のデータ蓄積装置は、画像検索装置におけるデータ蓄積装置であって、画像を蓄積する画像蓄積手段と、前記画像を近似した近似データを前記画像蓄積手段に蓄積された画像と対応付けて蓄積する近似データ蓄積手段とを備え、前記近似データ蓄積手段に蓄積されるデータ量は、近似データに対応する画像を蓄積した画像蓄積手段に蓄積されるデータ量より少なく、前記近似データ蓄積手段は前記画像蓄積手段に比べ高速アクセス可能な記憶媒体であり、前記近似データ蓄積手段に蓄積する前記近似データは、前記画像蓄積手段に蓄積された前記画像同士の関係を保持する様に生成されることを特徴とする。また、本発明の画像検索方法は、前記データ蓄積装置を備えた画像検索装置を用いて、プログラムされたコンピュータにより画像を検索する方法であって、検索対象と類似する近似データを前記近似データ蓄積手段に蓄積された近似データから検索するステップと、検索結果に対応する画像を画像蓄積手段から求めるステップと、検索対象と前記画像蓄積手段から求めた検索結果の画像との類似度を計算するステップとを有することを特徴とする。本発明によれば、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みができるため、次元数が高次元になった時でもユーザの望む画像を効率よく検索することができる。以下、本発明の実施の形態について、図面を参照しながら説明する。実施の形態1図1は、本発明の実施の形態1における画像検索装置の構成図である。図1において、11は、人物を撮影するカメラ、12は、指定された検索条件に該当する人物を含む画像を検索する検索サーバ、13は、検索サーバ12に対して検索条件を指定して検索を実行させるための検索端末である。101は、カメラ11で撮影した画像から、顔色形状などの人物を識別するための多次元特徴データを抽出する多次元特徴データ生成手段、102は、多次元特徴データ生成手段101で抽出した多次元特徴データの次元を縮退して近似データを生成する次元縮退手段、103は、次元縮退手段102で生成した近似データと次元縮退前の多次元特徴データと対応付けて、それぞれ近似特徴データ群103aと実特徴データ群103bとして蓄積する近似データ蓄積手段、104は、少なくとも、検索対象人物の多次元特徴データを識別する識別子を検索キーとして受信する検索要求受信手段、105は、検索端末13で指定された検索条件に基づいて、検索要求受信手段104で受信した検索キーに対応する近似データと近似データ蓄積手段103で蓄積した複数の近似データのそれぞれとの距離計算を行ない、計算結果の距離順すなわち類似度順に並べる近似空間検索手段、106は、近似空間検索手段105で得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定する実空間最終ランク付け手段である。実空間最終ランク付け手段106で決定された最終順位は、検索結果として出力される。多次元特徴データ生成手段101で抽出する人物特徴データは、画像から切出した移動体の画像データであり、或いは、形状色大きさ、動きなどにより移動体を特定する情報であり、或いは、顔の目鼻口の形状や位置などを特定する情報である。これらの特徴情報の抽出分類方法は広く知られており、例えば、特開2001268657号公報、及び、画像の処理と認識に厳密に記されている。これらの既存技術を利用して生成した顔服装色等の人物特徴データは、人物を特定するために複数の要素から構成されている。例えば、顔特徴データは、全体の顔つきを把握するための要素群、目鼻口等の特定部品の形状を把握するための要素群の合計:数百~数千次元から構成される。図2は、次元縮退手段102の処理手順を示したもので、以下その動作について説明する。<ステップ201>入力された多次元特徴データに対して、値を全て絶対値にして、値の大きいものから順にソートする。入力される多次元特徴データは、2-aのように、顔全体部品単位の主成分を持つ顔特徴データや、人物の服装の色分布をRGBHSV等の色空間ヒストグラムとして表わしたデータや、さらに、人物が写っている領域を切出して周波数に変換したデータなどで、横軸の各要素の要素番号値の集合が、ステップ201の多次元特徴データの入力として与えられる。また、ソート後は2-bのように絶対値が大きいものから順に並べられ、横軸の各要素は、ソート前の要素番号、値として生成される。<ステップ202>指定された次元で、多次元特徴データを分離次元をカットする。分離後、指定次元R以内の要素は、R1データとしてソート前の要素番号値の系列として出力され、また、指定次元Rより大きい部分は、R2データとして、代表値VR2内の符号ビット列として生成される2-c。なお、R2データの代表値Vは、R2データの絶対値での平均値、或いは、R2データの絶対値の最大値が用いられる。また、符号ビット列は、R2のN番目の要素の値が正ならビット値=1、負ならビット値=0として、R2の要素数分の符号が分かるビット列として生成される。<ステップ203>ステップ202で生成したR1及びR2データを近似データ蓄積手段103の近似特徴データ群103aへ格納する。また、ステップ201で入力されたソート前ベクトルデータを実特徴データ群103bへ格納する。このようにしてインデクスを生成する。なお、近似特徴データ群103aは、次元を縮退したデータ群であるため、高速アクセス可能なメモリ上に配置するようにしてもよい。図3は、近似空間検索手段105及び実空間最終ランク付け手段106の処理手順を示したもので、以下その動作について説明する。<ステップ301>検索要求受信手段104で受信した検索キーに対応する近似データ3-aと近似データ蓄積手段103で蓄積した複数の近似データ3-bとの近似距離計算を行ない、近似データ蓄積手段103で蓄積した複数の近似データを近似距離の小さい順に並べる。近似距離計算は、3-cに示すように、ソート前の全ての次元に対して、1各次元が、3-a,3-bのR1に含まれれば、R1にある値を用いて距離計算を行なう。2各次元が、3-a,3-bのR2に片方含まれれば、R2に含まれるものに対しては、R2の代表値Vと符号ビットから近似値を算出し、それを用いて距離計算を行なう。といった処理を行なう。<ステップ302>ステップ301で距離の小さい順に並べた上位M件に対して、検索要求受信手段104で受信した検索キーとの実距離計算を行ない、3-dのように実距離の小さい順に上位K件を抽出し結果として返す。実距離は、実特徴データ群103bに格納したソート前ベクトルデータから計算する。図3の処理は、近似距離の小さい順に並べた上位M件に対して、実空間上で最終順位付けを行なうものだが、上位M件に絞込んだ時点で検索漏れを起こす可能性がある。図4は、近似空間上での絞込みによる検索漏れを0にするための実空間最終ランク付け手段108の処理手順を示したもので、以下その動作について説明する。<ステップ401>近似空間検索手段105で生成した、検索キーとの近似距離のリストを取得する。リストは、近似距離の小さいものから順に格納されているものとする。<ステップ402>近似距離リストから、近似距離の小さいデータを取得する。取得した時点で、近似距離リストから該当データを削除する。<ステップ403>ステップ402で取得したデータと検索キーに対応するデータとの実距離を計算する。<ステップ404>ステップ402で取得したデータを実距離リストへ追加する。リストは、実距離の小さいものから順に格納されるようにする。<ステップ405>実距離リストの上位K件の全ての距離が、近似距離リスト内の最小距離より小さいか判定する。Yesの場合、ステップ406へ、Noの場合、ステップ402へ移行する。<ステップ406>実距離リストの上位K件を実空間最終ランク付け手段106の検索結果として出力する。図5を用いて、図3と図4の処理手順による検索結果の違いについて述べる。5-aは、検索キーとデータA~Hとの近似距離及び実距離の例を示したものである。5-aに対して、図3のフローで検索した場合、5-bに示すようにデータGが検索漏れを起こしてしまう。これに対し、図4のフローで検索した場合は5-cに示すようにデータGの検索漏れを起こすことはない。図3と図4のどちらの検索処理を採用するかは、近似距離と実距離の関係により異なる。例えば、全てのデータに対して近似距離≒実距離となる場合は、近似によって検索順位が大きく入替わる可能性がないため、検索漏れを防ぎつつ高速処理が可能な図4が適している。一方、近似距離実距離となる場合は、図4の処理では全データに対する検索が結局発生して処理が遅くなるため、ある程度検索漏れを抑えつつ高速に検索できる図3の処理が適している。以上のように、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みを行なうことで、次元数が高次元になった時でも演算量を抑えて、ユーザの望む画像を効率よく検索することができる。また、画像毎に、人物の特徴を強く表わす成分と平均的な成分に分離して次元を縮退することで、予め目鼻口等の重要度が高いと想定した成分のみを使用して次元を縮退する場合と比較して、重要度が高くないと想定した成分に特徴が大きく現れる人物の画像が登録されている場合でも、該当人物画像の検索を柔軟にかつ適切に行なうことができる。さらに、図4のような検索処理を導入する事により、近似空間上で検索結果を絞込む過程における検索漏れを0にすることができる。なお、次元縮退方法として、成分値の並替えによって人物の特徴を強く表わす成分と平均的な成分に分離する方法について述べたが、Haar等に代表されるウェーブレット変換を用いて、低周波に相当する平均的な成分からR2データを生成し、高周波に相当する平均との差分成分からR1データを生成するようにしてもよい。この場合、R1R2データを構成する要素番号が入力する多次元特徴データに依存せず固定されるため、近似空間検索手段105での演算量を削減できるという効果が得られる。また、多次元特徴データ間の差異が平均的な成分に強く出る場合には、前述のウェーブレット変換後の低周波に相当する平均的な成分をR1データ、高周波に相当する平均との差分成分をR2データに変更することで対応可能である。実施の形態2実施の形態2では、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる画像検索装置について述べる。本発明の実施の形態2で述べる構成は実施の形態1とほぼ同じであるため、ここでは、追加となる再検索時の絞込み操作の処理手順のみ記載し、他は省略する。図6は、近似空間検索手段105で得られた検索結果が実空間最終ランク付け手段106の最終ランク付けでどの程度変更が生じたかを示す次元縮退による歪み率を結果表示し、ユーザが次元縮退による歪み率を参照しながら、近似空間検索手段105で利用する次元数と絞込む件数を再検索条件として設定する例を示したものである。6-aは、検索対象者の検索キーと時刻場所の検索範囲を最初に指定する初期検索条件指定画面、6-bは、次元縮退による歪み率も併せて検索結果を表示する検索結果表示画面、6-cは、3通りの再検索の方法1利用次元数の調整、2近似範囲の調整、3上記12の調整は行なわずに次のK件を出力するから次の検索条件をユーザが指定する再検索条件指定画面であり、6-bと6-cの操作は繰返し行なわれる。図7を用いて、次元縮退による歪み率の算出例について述べる。7-aは、図1に示すような構成で検索を行なった場合に生じる検索漏れの例を表わしている。7-bは、検索漏れが起きた時の、近似空間検索手段105と実空間最終ランク付け手段106で得られた検索結果の違いを表わしている。7-bにおいて、近似空間での絞込みの閾値である上位M件のM値を大きくすれば検索漏れの確率は小さくなるが、ユーザがどの程度M値を大きくすれば良いのか判断がつかない。そこで、次元縮退の歪み率として、a近似空間で得られる上位K件が最終順位付け上位K件に含まれる比率、或いは、b最終順位付け上位K件のデータに対して、最終順位の総和/2/近時空間での順位の総和の順位比率、を用いることで、ユーザに次元縮退による歪みがどの程度発生しているのかを伝えることができる。なお、上記abの値が小さいほど歪みは大きくなる。次に、次元縮退の歪み率を参照してユーザが再検索条件を指定する操作について詳細に説明する。再検索条件の指定には、6-cに示したように、1利用次元数の調整、2近似範囲の調整、3次のK件を出力する、の3パターン存在する。1の利用次元数とは、近似空間検索手段105で使用するR1データの要素数であり、R1データの要素数を増やすことで次元縮退の歪み率を小さくすることができる。なお、利用次元数の調整が行なわれた時に、近似空間検索手段105でR1データの要素数を変更して再検索処理ができるように、図8に示すような複数のカット次元に対応したデータ構造を予め生成しておく。データ構造は、複数のカット次元毎に生成する必要はなく、8-bのように、R1データの要素数が大きいカット次元にあわせて用意しておくことで対応可能である。2の近似範囲の調整は、近似空間で絞込む範囲を調整するためのもので、次元縮退の歪み率が大きいときでも、M値を大きくする事で検索漏れを防ぐことができる。3の次のK件は、次元縮退の歪み率が小さい或いは次元縮退の歪み率が大きいが、12による調整が難しいとユーザが判断した時に使用される。以上のように、ユーザが次元縮退による歪み率を参照して、近似空間検索手段で利用する次元数と絞込む件数を調整していくことで、近似空間上で検索結果を絞込む過程における検索漏れを抑制した再検索操作を実現することができる。なお、再検索条件指定手段が、実空間最終ランク付け手段で出力した次元縮退による歪み率を参照して自動的に検索条件を再指定する構成としてもよい。この構成により、より効率的に画像を検索できる。実施の形態3実施の形態3では、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる、実施の形態2とは別の画像検索装置について述べる。本発明の実施の形態3で述べる構成は実施の形態1とほぼ同じであるため、ここでは、追加となる再検索時の絞込み操作の処理手順のみ記載し、他は省略する。図9は、検索結果に対してユーザが正解または不正解を指定すると、近似空間検索手段105にて、正解と指定した近似データで使用している要素番号の重み付けを強く、また、誤りと指定した近似データで使用している要素番号の重み付けを弱くして、近似空間内での距離計算を再度行なう例を示したものである。9-bのように、人物の特徴を強く表わす要素番号は検索結果毎に異なるため、ユーザが正解不正解と指定した結果から、正解を導出する要素番号と不正解を除去する要素番号をそれぞれ抽出して重み付けを行なうことで、検索漏れを抑制した再検索処理を実現する事ができる。なお、重み付けとは、図3の3-cの各次元の距離計算において、距離計算結果に重み係数を付与することである。また、図10は、検索結果に対してユーザが不正解と指定すると、不正解と指定したデータが実空間最終ランク付け手段106で出力されないように、近似空間検索手段105で利用する次元数と絞込む件数を自動調整する例を示したものである。10―bにおいて、ユーザがデータH/E=不正解と指定した場合は、最終順位付けでデータH/Eより距離の小さい要素が出てくるまで、近似空間での絞込みの閾値である上位M件のM値を大きく、或いは利用する次元数を増やして処理を行なう。以上のように、検索結果に対して、画像毎に、ユーザが正解不正解を指定して、再検索時の近似距離計算パラメータを自動調整していくことで、近似空間上で検索結果を絞込む過程における検索漏れを抑制した再検索操作を実現することができる。以上のように、本発明の各実施形態にかかる画像検索装置および画像検索方法は、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みを行なうことで、次元数が高次元になった時でも演算量を抑えて、ユーザの望む画像を効率よく適切に検索することができるという効果を有し、複数カメラを対象にした万引き犯迷子落し物者の全行動把握を行なう監視用途に加えて、旅行運動会等の個人で撮影したコンテンツ静止画動画に対する閲覧検索編集の用途等にも応用することができる。"