(57)【要約】【課題】  蓄積画像から、目的画像に類似した部分画像を検索する際、検索処理にかかる時間を短縮する部分画像検索システム及び方法並びにプログラムを提供する。【解決手段】  本部分画像検索システム装置は、見本特徴及び見本特徴間距離を準備し、蓄積部分領域特徴に索引を付し、目的部分領域特徴に類似する蓄積部分領域特徴を、索引により検索候補特徴を抽出し、検索候補特徴と目的部分領域特徴との距離を、検索候補特徴及び目的部分領域特徴の組合せに対応した見本特徴間距離で計算し、類似する部分画像の蓄積画像群の存在を判定し、目的画像と類似する部分画像が存在すると判定された蓄積画像中で、蓄積特徴に対し、目的画像と同一の照合窓を設定し、目的特徴との特徴距離を上記見本特徴間距離から計算し、目的画像と類似する部分画像の蓄積画像群中の当該箇所における存在の有無を判定する。【選択図】    図１
2006011622.tif 000002
【特許請求の範囲】
【請求項１】
データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索方法であり、
部分画像を検出するとき、見本となる典型的な特徴パターンを有する見本特徴を複数種類作成する見本特徴作成過程と、
該見本特徴各々の間の距離である見本特徴間距離を演算する見本特徴間距離計算過程と、
蓄積画像群の各画像から複数の小領域を選択し、各小領域における画像の特徴である蓄積特徴を抽出する蓄積特徴抽出過程と、
該蓄積特徴と前記見本特徴とを比較し、各蓄積特徴に対して前記見本特徴に対応する符号を割り当てる蓄積特徴量子化過程と、
該符号の集合に対して、所定の大きさの注目窓を所定の間隔にて配置して、各注目窓内の符号の集合である蓄積部分領域特徴を抽出する蓄積部分領域特徴抽出過程と、
前記蓄積部分領域特徴に索引を付与する索引付与過程と、
目的画像から複数の小領域を選択し、この小領域各々の特徴を目的特徴として抽出する目的特徴抽出過程と、
該目的特徴と、前記見本特徴とを比較することにより、前記目的特徴に対して、見本特徴に対応する符号を割り当てる目的特徴量子化過程と、
前記目的特徴量子化過程で求められた符号の集合に予め定められた所定の大きさの注目窓を設定し、この注目窓をずらしながら各注目窓内の符号の集合である目的部分領域特徴を抽出する目的部分領域特徴抽出過程と、
前記索引により、目的部分領域特徴の集合に類似する蓄積部分領域特徴を抽出する索引検索過程と、
前記索引検索過程において導かれた蓄積部分領域特徴と前記目的部分領域特徴抽出過程で導かれた目的部分領域特徴との距離を、前記見本特徴間距離に基づいて演算する特徴照合過程と、
前記距離に基づいて、目的画像に類似する部分画像が、蓄積画像群中の当該箇所に存在する可能性の有無の判定を行う照合結果判定過程と、
前記照合結果判定過程において目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴の符号に目的画像と同一の大きさの照合窓を設定し、該照合窓内の符号の集合と、前記目的特徴の符号の集合との特徴距離を前記見本特徴間距離に基づいて演算する特徴再照合過程と、
前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する照合結果再判定過程と、
前記照合結果再判定過程において、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択過程と、
前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定過程と、
前記検索候補特徴の集合の中から、次の照合すべき検索候補特徴を指定する次検索候補特徴選定過程と
を有することを特徴とする部分画像検索方法。
【請求項２】
前記照合結果再判定過程において、前記特徴距離と、該特徴距離に対応する閾値である検索閾値とが比較され、
前記目的画像と類似する部分画像が前記蓄積画像中の当該箇所に存在するか否かが判定され、
前記索引検索過程において、前記目的部分領域特徴抽出過程から導かれたいずれかの目的部分領域特徴との距離が、前記検索閾値から決定される選択閾値を下回る蓄積部分領域特徴を、前記索引を用いて抽出し、
前記照合結果判定過程において、
前記距離と、前記選択閾値とが比較され、前記目的画像と類似する部分画像が前記蓄積画像中の当該箇所に存在する可能性の有無が判定される
ことを特徴とする請求項１に記載の部分画像検索方法。
【請求項３】
前記検索結果候補選択過程において、
前記照合結果再判定過程にて、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を、前記特徴再照合過程で算出された距離の小さい順に、予め定められた数量だけ選択して検索結果候補とし、
該検索結果候補から、前記特徴距離に基づいて、ある検索結果候補を検出し、その距離値から新たな検索閾値を設定する検索閾値更新過程を備えたことを特徴とする請求項２に記載の部分画像検索方法。
【請求項４】
前記索引検索過程において、
前記索引に対して、前記目的部分領域特徴抽出過程で導かれた全ての目的部分領域特徴を用い、検索結果候補を抽出することを特徴とする請求項１から請求項３のいずれかに記載の部分画像検索方法。
【請求項５】
前記目的部分領域特徴を分類し、この各分類を代表する部分領域特徴である代表特徴を抽出する目的代表特徴抽出過程を備え、
前記索引検索過程において、前記目的部分領域特徴の代わりに、前記代表特徴を用いることを特徴とする請求項１から請求項３のいずれかに記載の部分画像検索方法。
【請求項６】
前記次目的部分領域特徴選定過程において、
前記特徴照合過程で照合を行った蓄積部分領域特徴との距離が前記選択閾値を超えることが検出された、前記目的部分領域特徴抽出過程にて抽出された目的部分領域特徴を、次に照合すべき部分領域特徴として指定せずに、照合を省略することを特徴とする請求項１から請求項５のいずれかに記載の部分画像検索方法。
【請求項７】
前記目的部分領域特徴の集合において、各目的部分領域特徴間の距離を計算する目的部分領域間距離計算過程と、
前記距離値及び部分領域間距離とを用い、特徴照合過程において照合を行った蓄積部分領域と、前記目的部分領域特徴抽出過程で導かれた各目的部分領域特徴との距離の下限値を計算する周辺距離下限値計算過程と
を備え、
前記次目的部分領域特徴選定過程において、前記距離下限値及び選択閾値とを比較し、距離下限値が選択閾値を下回る蓄積信号中の箇所を、次に照合すべき箇所として指定する
ことを特徴とする請求項６に記載の部分画像検索方法。
【請求項８】
前記特徴照合過程及び前記特徴再照合過程において、
部分領域特徴特徴間の距離を、前記見本特徴間距離に基づいて算出された各小領域間の距離各々を加算した積算値とすることを特徴とする請求項１から請求項７のいずれかに記載の部分画像検索方法。
【請求項９】
前記見本特徴作成過程において、
予め用意された所定の学習信号にて、典型的に出現する特徴パターンを学習することにより見本特徴を生成することを特徴とする請求項１から請求項８のいずれかに記載の部分画像検索方法。
【請求項１０】
前記見本特徴作成過程において、
クラスタリングアルゴリズムを用い、典型的に出現する特徴パターンを学習することを特徴とする請求項９に記載の部分画像検索方法。
【請求項１１】
前記蓄積特徴量子化過程において、
前記蓄積特徴に対して、該蓄積特徴との距離が最も小さい見本特徴に対応する符号を割り当て、
前記目的特徴量子化過程において、
前記目的特徴に対して、該目的特徴との距離が最も小さい見本特徴に対応する符号を割り当てる
ことを特徴とする請求項１から請求項１０のいずれかに記載の部分画像検索方法。
【請求項１２】
前記蓄積特徴量子化過程において、
前記蓄積特徴に対して、該蓄積特徴との距離が、予め定められた割当閾値以下にて最も小さい見本特徴に対応する符号を割り当て、該当する見本特徴が存在しない場合、いずれの見本特徴にも対応しない他の符号を割り当て、
前記目的特徴量子化過程において、
前記目的特徴に対して、該目的特徴との距離が予め定められた割当閾値以下にて最も小さい見本特徴に対応する符号を割り当て、該当する見本特徴が存在しない場合、いずれの見本特徴にも対応しない他の符号を割り当てる
ことを特徴とする請求項１から請求項１０のいずれかに記載の部分画像検索方法。
【請求項１３】
前記見本特徴各々について、該見本特徴に割り当てられる可能性のある前記蓄積特徴抽出過程及び前記目的特徴抽出過程で導かれる特徴が存在し得る範囲である特徴存在範囲を導く特徴存在範囲確定過程を備え、
前記見本特徴間距離計算過程において、
前記特徴存在範囲を用い、各々の見本特徴間の距離を演算することを特徴とする請求項１から請求項１２のいずれかに記載の部分画像検索方法。
【請求項１４】
前記見本特徴間距離計算過程において、
前記特徴存在範囲に基づいて、見本特徴各々に対応する前記特徴存在範囲の間の最大距離、または前記特徴存在範囲の間の最小距離、あるいはその双方を計算し、それらを新たに見本特徴間の距離とすることを特徴とする請求項１３に記載の部分画像検索方法。
【請求項１５】
データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索装置であり、
部分画像を検出するとき、見本となる典型的な特徴パターンを有する見本特徴を複数種類作成する見本特徴作成部と、
該見本特徴各々の間の距離である見本特徴間距離を演算する見本特徴間距離計算部と、
蓄積画像群の各画像から複数の小領域を選択し、各小領域における画像の特徴である蓄積特徴を抽出する蓄積特徴抽出部と、
該蓄積特徴と前記見本特徴とを比較し、各蓄積特徴に対して前記見本特徴に対応する符号を割り当てる蓄積特徴量子化部と、
該符号の集合に対して、所定の大きさの注目窓を所定の間隔にて配置して、各注目窓内の符号の集合である蓄積部分領域特徴を抽出する蓄積部分領域特徴抽出部と、
前記蓄積部分領域特徴に索引を付与する索引付与部と、
目的画像から複数の小領域を選択し、この小領域各々の特徴を目的特徴として抽出する目的特徴抽出部と、
該目的特徴と、前記見本特徴とを比較することにより、前記目的特徴に対して、見本特徴に対応する符号を割り当てる目的特徴量子化部と、
前記目的特徴量子化部が求めた符号の集合に予め定められた所定の大きさの注目窓を設定し、この注目窓をずらしながら各注目窓内の符号の集合である目的部分領域特徴を抽出する目的部分領域特徴抽出部と、
前記索引により、目的部分領域特徴の集合に類似する蓄積部分領域特徴を抽出する索引検索部と、
前記索引検索部が導いた蓄積部分領域特徴と、前記目的部分領域特徴抽出部が導いた目的部分領域特徴との距離を、前記見本特徴間距離に基づいて演算する特徴照合部と、
前記距離に基づいて、目的画像に類似する部分画像が、蓄積画像群中の当該箇所に存在する可能性の有無の判定を行う照合結果判定部と、
前記照合結果判定部により目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴の符号に目的画像と同一の大きさの照合窓を設定し、該照合窓内の符号の集合と、前記目的特徴の符号の集合との特徴距離を前記見本特徴間距離に基づいて演算する特徴再照合部と、
前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する照合結果再判定部と、
前記照合結果再判定部により目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択部と、
前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定部と、
前記検索候補特徴の集合の中から、次の照合すべき検索候補特徴を指定する次検索候補特徴選定部と
を有することを特徴とする部分画像検索システム。
【請求項１６】
データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索処理をコンピュータに実行させるプログラムであり、
部分画像を検出するとき、見本となる典型的な特徴パターンを有する見本特徴を複数種類作成する見本特徴作成処理と、
該見本特徴各々の間の距離である見本特徴間距離を演算する見本特徴間距離計算処理と、
蓄積画像群の各画像から複数の小領域を選択し、各小領域における画像の特徴である蓄積特徴を抽出する蓄積特徴抽出処理と、
該蓄積特徴と前記見本特徴とを比較し、各蓄積特徴に対して前記見本特徴に対応する符号を割り当てる蓄積特徴量子化処理と、
該符号の集合に対して、所定の大きさの注目窓を所定の間隔にて配置して、各注目窓内の符号の集合である蓄積部分領域特徴を抽出する蓄積部分領域特徴抽出処理と、
前記蓄積部分領域特徴に索引を付与する索引付与処理と、
目的画像から複数の小領域を選択し、この小領域各々の特徴を目的特徴として抽出する目的特徴抽出処理と、
該目的特徴と、前記見本特徴とを比較することにより、前記目的特徴に対して、見本特徴に対応する符号を割り当てる目的特徴量子化過程と、
前記目的特徴量子化処理で求められた符号の集合に予め定められた所定の大きさの注目窓を設定し、この注目窓をずらしながら各注目窓内の符号の集合である目的部分領域特徴を抽出する目的部分領域特徴抽出処理と、
前記索引により、目的部分領域特徴の集合に類似する蓄積部分領域特徴を抽出する索引検索処理と、
前記索引検索処理において導かれた蓄積部分領域特徴と前記目的部分領域特徴抽出過程で導かれた目的部分領域特徴との距離を、前記見本特徴間距離に基づいて演算する特徴照合処理と、
前記距離に基づいて、目的画像に類似する部分画像が、蓄積画像群中の当該箇所に存在する可能性の有無の判定を行う照合結果判定処理と、
前記照合結果判定処理において目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴の符号に目的画像と同一の大きさの照合窓を設定し、該照合窓内の符号の集合と、前記目的特徴の符号の集合との特徴距離を前記見本特徴間距離に基づいて演算する特徴再照合処理と、
前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する照合結果再判定処理と、
前記照合結果再判定処理において、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択処理と、
前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定処理と、
記検索候補特徴の集合の中から、次の照合すべき検索候補特徴を指定する次検索候補特徴選定処理と
を有する部分画像検索処理をコンピュータに実行させるプログラム。
【請求項１７】
請求項１６に記載の部分画像検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、蓄積された複数の画像から、与えられた画像と類似した部分画像を含む画像及びその部分画像が含まれている位置を同定するのに適した部分画像検索システム及び方法並びにプログラムに関する。
【背景技術】
【０００２】
デジタルカメラの普及や記録媒体の大容量化・低価格化、さらに大容量ネットワークの普及により、容易に大容量のデジタル画像を取得して保存する環境が整ってきている。
そのため、大量の画像から所望の画像を高速に探し出す高速画像検索技術が必要となってきており、特に画像の部分検索は、検索したい画像が蓄積されている画像の一部分であるため、比較の処理が多くなり、さらに高速性が要求される。
この部分画像検索技術は、膨大な画像データベースの中から、高速に目的の画像をその一部分として含む画像を検索する画像検出技術に用いられる。
【０００３】
例えば、画像データベースに蓄積された画像の中から、特定人物の顔が撮影されている画像を検出してユーザに提示したり、特定の物体や建造物などが撮影されている画像を含まれるホームページを検索したりする検索技術に用いられる。
従来、上記部分画像検索方法に関しては、見本となる検索したい画像と類似した画像の場所の探索を、より大きなサイズの画像の中から漏れなく正確に、高速に実行するための高速部分画像検出方法として、画像を小領域に分割して抽出した特徴をベクトル量子化し、その結果に基づいて、信号全体から照合のための特徴であるヒストグラムを作成する高速信号照合方法が知られている（例えば、特許文献１及び２参照）。
【特許文献１】特開平０７−２６２３７３号公報
【特許文献２】特許第３０６５３１４号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述した従来の部分画像検出方法にあっては、小領域の特徴をベクトル量子化し、その量子化結果からヒストグラムを作成して、比較のためのデータ量を低減しているが、比較演算するデータ量から考えると、データ量の削減が十分ではなく、ヒストグラムによる比較においても計算時間が非常に長く必要となるため、蓄積画像における部分画像の探索の時間を大幅に低減できないという欠点がある。
また、従来の部分画像検出方法にあっては、画像の特徴をベクトル量子化したものを、ヒストグラムに変換してしまうため、照合の際に部分画像内における目的画像の位置関係を正確に考慮することができないという欠点がある。
本発明は、このような事情に鑑みてなされたもので、目的画像と、蓄積画像における目的画像に類似した部分画像との類似を判定する際に、比較するデータ量を低減させ、検索処理にかかる時間を短縮し、かつ照合の際に部分画像内における目的画像の位置関係を、正確に検出する部分画像検索システム及び方法並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の部分画像検索方法は、データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索方法であり、部分画像を検出するとき、見本となる典型的な特徴パターンを有する見本特徴を複数種類作成する見本特徴作成過程と、該見本特徴各々の間の距離である見本特徴間距離を演算する見本特徴間距離計算過程と、蓄積画像群の各画像から複数の少領域を選択し、各小領域における画像の特徴である蓄積特徴を抽出する蓄積特徴抽出過程と、該蓄積特徴と前記見本特徴とを比較し、各蓄積特徴に対して前記見本特徴に対応する符号を割り当てる蓄積特徴量子化過程と、該符号の集合に対して、所定の大きさの注目窓を所定の間隔にて配置して、各注目窓内の符号の集合である蓄積部分領域特徴を抽出する蓄積部分領域特徴抽出過程と、前記蓄積部分領域特徴に索引を付与する索引付与過程と、目的画像から複数の小領域を選択し、この小領域各々の特徴を目的特徴として抽出する目的特徴抽出過程と、該目的特徴と、前記見本特徴とを比較することにより、前記目的特徴に対して、見本特徴に対応する符号を割り当てる目的特徴量子化過程と、前記目的特徴量子化過程で求められた符号の集合に予め定められた所定の大きさの注目窓を設定し、この注目窓をずらしながら各注目窓内の符号の集合である目的部分領域特徴を抽出する目的部分領域特徴抽出過程と、前記索引により、目的部分領域特徴の集合に類似する蓄積部分領域特徴を抽出する索引検索過程と、前記索引検索過程において導かれた蓄積部分領域特徴と前記目的部分領域特徴抽出過程で導かれた目的部分領域特徴との距離を、前記見本特徴間距離に基づいて演算する特徴照合過程と、前記距離に基づいて、目的画像に類似する部分画像が、蓄積画像群中の当該箇所に存在する可能性の有無の判定を行う照合結果判定過程と、前記照合結果判定過程において目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴の符号に目的画像と同一の大きさの照合窓を設定し、該照合窓内の符号の集合と、前記目的特徴の符号の集合との特徴距離を前記見本特徴間距離に基づいて演算する特徴再照合過程と、前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定す
る照合結果再判定過程と、前記照合結果再判定過程において、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択過程と、前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定過程と、記検索候補特徴の集合の中から、次の照合すべき検索候補特徴を指定する次検索候補特徴選定過程とを有することを特徴とする。
【発明の効果】
【０００６】
以上説明したように、本発明によれば、画像の特徴の典型的なパターンである見本特徴の集合を準備し、この見本特徴各々の間の距離を予め計算しておき、目的特徴及び蓄積特徴おのおのに対応する見本特徴を選択して、照合時にこの見本特徴の距離を用いることにより、照合に於ける距離の演算を行わないようにし、かつ照合のための特徴を符号列で表現することにより、従来例に比較して照合処理を高速化することができる。
また、本発明によれば、照合のための特徴を、ヒストグラムを用いた量子化処理を行わなわずに、特徴に対して符号を付して表現することにより、画像内の位置関係を保持することができる。
【発明を実施するための最良の形態】
【０００７】
＜第１の実施例＞
以下、本発明の第１の実施例による部分画像検索装置を図面を参照して説明する。図１は上記第１の実施例の部分画像検索装置の一構成例を示すブロック図である。
この図において、本実施例の部分画像検索システムは、見本特徴作成部１と、見本特徴間距離計算部２と、蓄積特徴抽出部３と、蓄積特徴量子化部４と、蓄積部分領域特徴抽出部５と、索引付与部６と、目的特徴抽出部７と、目的特徴量子化部８と、目的部分領域特徴抽出部９と、索引検索部１０と、特徴照合部１１と、照合結果判定部１２と、特徴再照合部１３と、照合結果再判定部１４と、検索結果候補選択部ｌ５と、次目的部分領域特徴選定定部１６と、次検索候補特徴選定部１７とを有しており、目的画像、すなわち参照している検索したい画像と、データベース等に蓄積されている蓄積画像群、すなわち検索される被検索画像である蓄積画像の集合を入力とし、上記目的画像と類似する部分画像が含まれている蓄積画像内の箇所を出力する。
【０００８】
見本特徴作成部１は、画像を検索する際に用いるため、画像の特徴において、見本となる典型的な特徴パターンである見本特徴を、複数の画像パターンに対応して作成する。
見本特徴間距離計算部２は、上述した各見本特徴間の距離である見本特徴間距離を計算する。また、見本特徴間距離計算部２は、データベースにおいて、上記見本特徴間距離を、各見本特徴の組合せに対応して記憶させても良い。
上記見本特徴間距離は、ユークリッド距離，マンハッタン距離，内積，正規化相互相関などを用いることが出来る。
蓄積特徴抽出部３は、蓄積画像群の画像各々において、所定の大きさの小領域を設定して、この小領域単位に画像を切り出し、この複数の小領域の画像各々の特徴を、蓄積特徴として抽出する。
【０００９】
蓄積特徴量子化部４は、上記蓄積特徴抽出部３の出力する蓄積特徴について、上記見本特徴作成部１から出力される各見本特徴と比較し、この蓄積特徴に近似する見本特徴に対応する所定の符号を割り当てる。
蓄積部分領域特徴抽出部５は、上記蓄積特徴抽出部３から出力された符号の集合に対し、予め定められた所定の大きさの注目窓を、予め定められた所定の間隔で設定し（所定の間隔でずらし）、各注目窓内に含まれる上記符号の集合である蓄積部分領域特徴を抽出する。
索引付与部６は、上記蓄積部分領域特徴抽出部５から出力される各蓄積部分領域特徴を、各々ベクトル量子化し、ベクトル量子化の符号語を、標識のための索引として付与する。
【００１０】
目的特徴抽出部７は、目的画像において、所定の大きさの小領域を設定して、この小領域単位に画像を切り出し、この複数の小領域の画像各々の特徴を、目的特徴として抽出する。
目的特徴量子化部８は、上記目的特徴抽出部７の出力する目的特徴について、上記見本特徴作成部１から出力される各見本特徴と比較し、この蓄積特徴に近似する見本特徴に対応する所定の符号を割り当てる。
目的部分領域特徴抽出部９は、上記目的特徴抽出部４から出力された符号の集合に対し、予め定められた所定の大きさの注目窓を、予め定められた所定の間隔で設定し（所定の間隔でずらし）、各注目窓内に含まれる上記符号の集合である目的部分領域特徴を抽出する。
【００１１】
索引検索部１０は、上記索引付与部６から出力される索引を用いて、上記目的部分領域特徴抽出部９から出力される目的部分領域特徴の集合に対して、類似する蓄積部分領域特徴の抽出を行う。
特徴照合部１１は、上記索引検索部１０の抽出した蓄積部分領域特徴と、目的部分領域特徴抽出部９の抽出した目的部分領域特徴との距離を、各々の符号に対応する見本特徴の組合せにより、上記データベースから対応する見本特徴間距離を抽出することにより演算する。
照合結果判定部１２は、上記特徴照合部１１の演算した距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在する可能性があるか否かの判定を行う。
【００１２】
特徴再照合部１３は、上記照合結果判定部１２により、目的画像と類似する部分蓄像が存在する可能性があると判定した場合、判定された蓄積画像における箇所において、蓄積特徴抽出部３の抽出した蓄積特徴に対し、目的画像と同じ大きさの照合窓を設定して、この照合窓内に含まれる符号の集合と、前記蓄積特徴量子化部４から出力された符号の集合との特徴距離を、特徴照合部１１と同様に前記見本特徴間距離に基づいて演算する。
照合結果再判定部１４は、上記照合結果判定部１３において用いられた距離に基づいて、目的画像と類似する部分画像が、蓄積画像群中の当該箇所に存在するか否かの判定を行う。
【００１３】
検索結果候補選択部１５は、上記照合結果再判定部１４において目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を、詳細な類似性の検討を行う検索結果候補とする。
次目的部分領域特徴選定部１６は、上記目的部分領域特徴抽出部９において抽出された目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴の指定を行う。
次検索候補特徴選定部１７は、上記索引検索部１０から検索結果として出力された蓄積部分領域特徴の集合の中から、次に照合すべき蓄積部分領域の指定を行う。
【００１４】
次に、図１及び図２を参照して、上述した部分画像検索装置の動作を説明する。図２は、図１の第１の実施例による部分画像検索システムの一動作例を具体的に示すフローチャートである。
見本特徴作成部１は、学習信号（画像）を読み込み（ステップＳ１）、この学習信号から見本特徴を抽出しても良いし、後に述べるように学習信号を読み込まずに、蓄積画像から見本特徴を抽出するための画像を選択して、見本特徴を抽出してもよい。
学習信号としては、複数の画像、例えば、１０００枚の画像群など、十分に学習可能な多数の画像を用いるのが好ましい。ここで、見本特徴作成部１は、クラスタリングアルゴリズムを用いて、典型的に出現する特徴パターンの学習を行う。
また、これ以降の処理において、見本特徴の抽出に対して、学習信号を用いない場合、学習信号を読み込む必要、すなわち、ステップＳ１の処理を行う必要はない。
【００１５】
次に、見本特徴作成部１は、入力した学習信号の画像から、後に述べる蓄積特徴抽出部３と同様の処理により、この画像を識別できる特徴を抽出する。
ここで、学習信号の画像から抽出した特徴を、以下、学習特徴と呼ぶ。
また、学習信号を用いない場合、このステップＳ２の処理を行わない。
そして、見本特徴作成部１は、以降の処理に用いる典型的な画像の特徴パターンである見本特徴の抽出を行う（ステップＳ２）。
このとき、見本特徴作成部１は、学習信号を用いない場合、見本特徴の抽出処理として、予め定められた確率分布、例えば、多次元ガウス分布に従って見本特徴をランダムに発生させることにより行う。
【００１６】
本実施例の場合は、上述したように見本特徴作成部１に見本特徴を発生させ、学習信号を用いずに見本特徴を作成している。
また、他の実施例として、学習特徴をベクトルとして、そのベクトルに対してベクトル量子化を行いて分類して（クラスタリングを行い）、見本特徴の抽出を行う様にしても良い。例えば、ベクトル量子化の符号の語数が１０２４個で有れば、学習特徴を１０２４の集合（以下、クラスタと呼ぶ）のいずれか一つのクラスタに分類することができる。
ここで、各クラスタに所属する学習特徴の重心となる特徴を、見本特徴とする。
そして、見本特徴作成部１は、上述のいずれかの方法により生成した見本特徴の集合を出力する。
【００１７】
次に、見本特徴間距離計算部２は、上記見本特徴の集合を読み込む（必要に応じて、特徴存在範囲確定部２２の出力する、見本特徴に対応した特徴存在範囲を読み込む）。
そして、見本特徴間距離計算部２は、見本特徴の集合において、全ての見本特徴の組合せを選択し、この組合せ毎に見本特徴間の距離である見本特徴間距離の演算を行う。
このとき、見本特徴間距離計算部２は、上記見本特徴間距離として、例えば、見本特徴ベクトル間の自乗誤差を計算し、見本特徴間距離とする（ステップＳ３）。
他の実施例として、見本特徴に対応した特徴存在範囲を用いて見本特徴間距離を定義することもできる。
例えば、特徴存在範囲を見本特徴を中心とした特徴ベクトル空間内の超球で表現した場合、特徴存在範囲間の最小距離及び最大距離を、見本特徴ベクトル間の距離（自乗誤差）ｄ(ｆi，ｆj)と対応する特徴存在範囲の半径ｒi及びｒjを用い、以下の（１）式及び（２）式を用いて計算できる。
【００１８】
【数１】
2006011622.tif 000003
【００１９】
【数２】
2006011622.tif 000004
【００２０】
上記（１）式で求まる特徴存在範囲間の最小距離ｄmin、または（２）式で求まる特徴存在範囲間の最大距離ｄmax、もしくはその両方（最小距離及び最大距離）を、見本特徴間距離として定義する。
これにより、見本特徴間距離計算部２は、全見本特徴の組合せ毎に、見本特徴間距離の集合を出力する（データベース等に記憶させることも可能である）。
【００２１】
次に、蓄積特徴抽出部３は、初めに、蓄積画像群を、図示しないデータベースから読み込む（ステップＳ４）。
そして、蓄積特徴抽出部３は、読み込んだ蓄積画像群の各画像から、例えば、「８×８」ピクセル程度の大きさの小領域を、縦方向及び横方向に１ピクセルずつずらしながら、画像を切り出し、各小領域に含まれる画像の特徴の抽出を行う（ステップＳ５）。
ここで、画像の特徴の抽出方法として、例えば、各小領域のＲＧＢ値をそのまま用いる。
例えば、蓄積画像の大きさが「３８４×２５６」ピクセルであるとき、「８×８×３＝１９２」次元の特徴ベクトルが、１画像あたり、「(３８４−８＋１)×(２５６−８＋１)＝９３８７３」個得られる。
【００２２】
他の実施例として、蓄積特徴抽出部３は、各小領域のＲＧＢ値各々に対して、２次元ＤＣＴ（デジタルコサイン変換)を施し、その係数ベクトルを特徴とすることもできる。
ここで、例えば、蓄積画像の大きさが「３８４×２５６」ピクセルであるとすると、「８×８×３＝１９２」次元の特徴ベタトルが、１画像あたり、「(３８４−８＋１)×(２５６−８＋１)＝９３８７３」個得られる。
蓄積特徴抽出部３は、上述したいずれかの方法により、蓄積画像から抽出された特徴である蓄積特徴の集合を出力する．
【００２３】
次に、蓄積特徴量子化部４は、見本特徴作成部１から出力された見本特徴の集合と、蓄積特徴抽出部３から出力された蓄積特徴の集合とを読み込む。
そして、蓄積特徴量子化部４は、各蓄積特徴毎に、見本特徴の集合の各見本特徴と照合し、蓄積特徴量各々に対して、見本特徴に対応した符号を１つ割り当てる。
このとき、蓄積特徴量子化部４は、蓄積特徴と各見本特徴との距離、例えば自乗誤差を計算し、最も距離が近い見本特徴に対応した符号をこの蓄積特徴に割り当てる（ステップＳ６）。
例えば、１０２４個の見本特徴を準備した場合、各見本特徴毎に１から１０２４までの番号をそれぞれ割り当て、その番号を符号とする。
【００２４】
他の実施形態として、蓄積特徴量子化部４は、蓄積特徴と各見本特徴との距離を計算し、最も距離が近い見本特徴との距離が予め定められた閾値である割当閾値を下回る場合、その見本特徴に対応した符号を割り当て、距離が割当閾値を上回る場合、どの見本特徴にも対応しない別の符号、例えば、上述した例においては、 １０２５等の番号を符号として割り当てる構成としてもよい。
そして、蓄積特徴量子化部４は、上述した方法のいずれかを用い、各蓄積特徴から抽出した符号列の集合を出力する。
【００２５】
次に、蓄積部分領域特徴抽出部５は、蓄積特徴量子化部４から、符号列の集合を読み込み、蓄積画像のある１つの箇所に、予め定められた所定の大きさの第１注目窓を設定する。
例えば、この第１注目窓は、大きさが６４×６４ピクセルであり、初期状態として蓄積画像の左上の角に配置される。
そして、蓄積部分領域特徴抽出部５は、設定された上記第１注目窓内に含まれる符号の集合を抽出し、抽出した符号を順に並べてベクトルとしたものを照合のための特徴として用い、以下、この特徴を蓄積部分領域特徴とする（ステップＳ７）。
ここで、符号の集合の抽出方法として、例えば、第１注目窓内に、重複することも隙間も存在しない状態に、上記小領域を配置して、この各小領域毎に対応する符号を抽出する。
このとき、「(６４／８)×(６４／８)×３＝６４」次元の特徴のベクトル、すなわち蓄積部分領域特徴を１つ得る。
【００２６】
上記第１注目窓は、各蓄積画像内において、予め定められた所定の間隔により、複数設定され、各注目窓内の部分領域から蓄積部分領域特徴を抽出する。
すなわち、第１注目窓（横ωxピクセル×縦ωyピクセル）は、各蓄積画像内において、縦及び横方向に、上記所定の間隔（各注目窓の同一の辺同士の間隔であり、例えば左辺同士、上辺同士の間隔として、横方向にｍxピクセル，縦方向にｍyピクセル）で順次ずらして配置されている。
【００２７】
例えば、第１注目窓を縦横それぞれ１６ピクセルの間隔で配置し、蓄積画像の大きさが「３８４×２５６」ピクセルであるとすると、第１注目窓が「６４×６４」ピクセルであるために１画像あたり、「２１×１３＝２７３」個の第１注目窓が設定されることになる。
また、第１注目窓の配置間隔を、以下マージンと呼ぶことにする。
そして、蓄積部分領域特徴抽出部５は、上記第１注目窓毎に得られた蓄積部分領域特徴の集合を出力する。
【００２８】
次に、索引付与部６は、蓄積部分領域特徴抽出部５の抽出した蓄積部分領域特徴の集合を読み込み、この読み込んだ各部分領域特徴に対して、検索を容易にするための索引を付与する。
このとき、索引付与部６は、必要に応じて、見本特徴作成部１から出力される見本特徴の集合と、見本特徴間距離計算部２から出力される見本特徴間距離を読み込む。
ここで、索引付与部６は、部分領域特徴を構成する符号列に対して、索引を付与する（ステップＳ８）。
例えば、予め作成された部分領域特徴である蓄積代表特徴の集合を用いて、各部分領域特徴を構成する符号列を量子化し、量子化の符号語を索引とする。
すなわち、上記方法について簡単に説明すると、はじめに、索引付与部６は、蓄積部分領域特徴の集合を読み込む。
【００２９】
次に、索引付与部６は、各部分領域特徴（符号列）のクラスタリングを行う。すなわち、部分領域特徴間の距離を、後述する特徴照合部１１と同様に計算することとし、上記蓄積代表特徴の集合から、蓄積部分領域特徴との距離が最も小さくなる蓄積代表特徴を選び出し、該蓄積代表特徴に対応する符号である代表特徴番号を出力することによって行われる。
そして、索引付与部６は、索引として、各部分領域特徴に対応する代表特徴番号を出力する。
他の実施例として、例えば、読み込んだ見本特徴の集合を用いて、部分領域特徴を構成する各符号を、対応する見本特徴ベクトルに展開し、それらを連結したベクトルに対して索引を付与する。
【００３０】
例えば、「信号検出方法、信号検出装置、記録媒体及びプログラム」(特開２００２−２３６４９６)記載の実施例のように、予め作成されたベクトル量子化符号帳を用いて、各部分領域画像の特徴ベクトルをベクトル量子化し、ベクトル量子化の符号語を索引とする。
すなわち、上記方法について簡単に説明すると、はじめに、索引付与部６は、蓄積部分領域特徴の符号列を展開したベクトルである展開ベクトルの集合を読み込む。
次に、索引付与部６は、各展開ベクトルのクラスタリングを行う。このクラスタリングは、例えば、各展開ベクトルを、ベクトル量子化を用いて符号化することによって行う。
例えば、ベクトル量子化の符号語数が１０２４個であれば、展開ベクトルは１０２４個のクラスタのいずれかに分類されることになる。
【００３１】
ここで、ベクトル量子化は、例えば、自乗誤差を距離関数として用い、クラスタ重心との距離が他のどのクラスタ重心との距離よりも小さくなるクラスタに展開ベクトルを所属させ、クラスタに対応する符号語を出力することによって行われる。
このクラスタは、例えば、クラスタ作成のために予め容易された、展開ベクトルと同じ次元数のベクトルである学習ベクトルを用いて予め作成しておく。
すなわち、クラスタは、それに所属する学習ベクトルとクラスタ重心との距離の総和が最小になるように、かつそのクラスタに所属する学習ベクトルについて、所属するクラスタのクラスタ重心との距離が、他のどのクラスタ重心との距離よりも小さくなるように構成される。
そして、索引付与部６は、索引として、各展開ベクトルに対応する、ベクトル量子化の符号語を出力する。
【００３２】
また、別の実施形態として、例えば、Ｒ＊-Ｔｒｅｅ（「The R＊-Tree: an efficient and robust access method for points and rectangles」，(N.Beckman他１名，Proc. of ACM SIGMOD Conference，pp.322-331，1990))やＳＲ-Ｔｒｅｅ（「SR-Tree: 高次元データに対する最近接探索のためのインデックス構造の提案」（片山紀生 他１名，電子情報通信学会論文誌D-I，Vol.J80-D-I，No.8，pp.703-717，1997年８月))など、多次元インデックスと総称される手法を用いて、特徴の存在する多次元空間内で特徴を包含する領域を階層的に作成し、最下層の領域と特徴とを対応付けることにより索引を付与することも可能である。
【００３３】
特徴を包含する領域は、例えば、Ｒ＊-Ｔｒｅｅであれば、３次元空間における直方体に相当する超直方体、ＳＲ-Ｔｒｅｅであれば、超直方体と、３次元空間における球に相当する超球との重なりとなる。
そして、索引付与部６は、上述のように求められた、各部分領域特徴に対する索引を出力する（ステップＳ８）。
【００３４】
次に、目的特徴抽出部７は、目的画像を読み込むが（ステップＳ９）、この目的画像の大きさは、例えば、マージンと第１注目窓の大ききとの和（合計）以上に設定すると、完全に蓄積画像の特徴の抽出を行う範囲を包含するために、検索漏れを生じることがない。
そして、目的特徴抽出部７は、小領域を縦方向及び横方向に１ピクセルずつずらしながら目的画像を切り出し、各小領域に含まれる画像の特徴の抽出を、上記蓄積特徴抽出部３と同様の手法で行い、目的画像から抽出された特徴である目的特徴の集合を出力する（ステップＳ１０）。
【００３５】
次に、目的特徴量子化部８は、見本特徴作成部１から出力される見本特徴の集合と、目的特徴抽出部７から出力される目的特徴の集合を読み込み、各目標特徴毎に見本特徴の集合の各見本特徴と照合し、目標特徴各々に対して見本特徴に対応した符号を１つ割り当てる。ここで、目的特徴量子化部８が符号を割り当てる手順は、蓄積特徴量子化部４と同様である。  
そして、目的特徴量子化部８は、目的特徴の集合の各目的特徴から抽出した符号列の集合を出力する（ステップＳ１１）。
【００３６】
次に、目的部分領域特徴抽出部９は、目的特徴量子化部８の抽出した符号列の集合を読み込み、この目的画像のある１つの箇所に、蓄積部分領域特徴抽出部５で用いた注目窓と同様の大きさ（縦×横）の注目窓、すなわち、第１注目窓を用い、この第１注目窓内に含まれる符号の集合を抽出する。
そして、目的部分領域特徴抽出部９は、上記蓄積部分領域特徴抽出部５と同様の抽出方法を用いて、目的画像のある１つの箇所から抽出した符号を順に並べて、ベクトルとしたものを照合に用いる特徴とし、この特徴を目的部分領域特徴の集合として出力する。（ステップＳ１２）。
【００３７】
ここで、目的部分領域特徴抽出部９は、蓄積部分領域特徴抽出部２における特徴抽出の場合と異なり、上記第１注目窓を、目的画像内に重複することもなく、かつ隙間もない状態に設定し、それらを１ピクセルずつずらしながら、各位置において上記目的部分領域特徴の抽出を行う。
このとき、第１抽出窓は、例えば、少なくともマージンの大きさの分だけずらせば、検索漏れを生じさせることがない。
例えば、目的画像の大きさが「８０×８０」ピクセル、第１注目窓の大きさが「６４×６４」ピクセル、マージンが「１６×１６」ピクセルであるとき、目的画像内に重複することもなく、かつ隙間もない状態に設定できる第１注目窓の数が１つなので、目的画像全体において、「１６×１６＝２５６」個の第１注目窓が設定される。
そして、目的部分領域特徴抽出部９は、上述した処理により抽出した、目的部分領域特徴の集合を出力する。
【００３８】
次に、索引検索部１０は、索引付与部６から出力される索引と、目的部分領域特徴抽出部９から出力される目的部分領域特徴の集合とを読み込む。
そして、目的代表特徴抽出部１９において、目的部分領域特徴から目的代表特徴を抽出する処理を行った場合、索引検索部１０は、目的部分領域特徴の集合の代わりに、目的代表特徴抽出部１９から出力される目的代表特徴の集合を読み込む。
目的代表特徴抽出部１９は、後述する他の実施形態において詳細に説明する。
また、必要に応じて、索引検索部１０は、目的部分領域間距離計算部１６から出力される目的部分領域間距離を読み込む構成もある。
また、検索閾値更新部１８が検索閾値及び選択閾値を更新する処理を行った場合、索引検索部１０は更新された選択閾値を読み込む。この検索閾値更新部１８については後述する他の実施形態において、詳細に説明する。
【００３９】
そして、索引検索部１０は、読み込んだ索引を用い、目的部分領域特徴の集合に類似する蓄積部分領域特徴を、検索候補特徴として抽出する（ステップＳ１３）。
このとき、索引検索部１０は、目的部分領域特徴の集合内におけるいずれかの目的部分領域特徴に対し、該部分領域特徴との距離ｄtが、予め定められた閾値である選択閾値θ２を下回るような（以下となるような）蓄積部分領域特徴を、索引から抽出する。
索引検索部１０は、部分領域特徴間の距離を特徴照合部１１と同様の処理により計算する（特徴照合部１１の構成については後述）。
上記選択閾値θ２は後述するパラメータから自動的に決定される値であり、また、この選択閾値の決定方法は後述する。
【００４０】
また、別の実施例として、目的部分領域特徴の集合の代わりに、目的部分領域特徴から代表的な特徴を目的代表特徴として抽出し、この目的代表特徴の集合を用いて、集合内のいずれかの目的代表特徴との距離ｄtが選択閾値θ２を下回る蓄積部分領域特徴を、上記索引から抽出する構成とすることも可能である（後述）。
さらに、別の実施例として、目的部分領域間距離を用い、各目的代表特徴との距離ｄtを、該目的代表特徴に対応する目的部分領域間距離の最大値分だけ小さくし、この距離ｄtの値が選択閾値θ２を下回る蓄積部分領域特徴を索引から抽出する構成とすることも可能である（後述）。
【００４１】
ここで上述した、ある１つの目的部分領域特徴あるいは目的代表特徴との距離が選択閾値を下回る蓄積部分領域特徴を索引から抽出する抽出方法について説明する。
この抽出方法は、上記索引付与部３において用いられた索引の種類によって異なり、上記索引に対応する特許明細書記載の方法あるいは非特許文献記載の方法と同様にして実施することができる。
例えば、上記蓄積代表特徴を用いた量子化によって索引を付与した場合、及び「信号検出方法、信号検出装置、記録媒体及びプログラム」(特開２００２−２３６４９６)に記載の方法を用いて索引を付与した場合、以下のようにして所望の蓄積部分領域特徴を抽出することができる。
【００４２】
はじめに、索引検索部１０は、目的部分領域特徴あるいは目的代表特徴と、索引付与部３で作成された索引（クラスタ）、及び選択閾値θ２を読み込む。
以下では、簡単のため、目的代表特徴ではなく、本実施例で採用した構成において目的部分領域特徴を読み込んだものとして説明する。目的代表特徴を読み込んだ場合でも、全く同様に行うことができる。
そして、索引検索部１０は、読み込んだ目的部分領域特徴と、各クラスタ重心との距離を計算する。
続いて、索引検索部１０は、計算された距離ｄtに基づいて、目的部分領域特徴との距離が選択閾値θ２を下回る蓄積部分領域特徴を含む可能性のあるクラスタを選択する。
【００４３】
上述したクラスタを選択する原理を以下に説明する。
図４は、点Ｑ，Ｃ1，Ｃ2の３点が乗るような平面であり、特徴ベクトルが配置される特徴空間を切り出した様子を示している。
ここで、点Ｑは目的部分領域特徴、Ｃ1は部分領域特徴Ｑが所属しているクラスタのクラスタ重心、Ｃ2は他のクラスタのクラスタ重心を表しており、距離ｄQ1，ｄQ2，ｄ12はそれぞれ、点Ｑと点Ｃ1との距離、点Ｑと点Ｃ2との距離、点Ｃ1と点Ｃ2との距離を示している。
【００４４】
ここで、目的部分領域特徴の座標である点Ｑからの距離ｄtが選択閾値θ２以内である蓄積部分領域特徴を抽出しなければならないとすると、点Ｑを中心とする半径θ２の超球（図４においては半径ｄθの円）の内部にある蓄積部分領域特徴がそれに該当する。
そして、点Ｑを中心とする超球の半径が図４におけるｄθより大きくなったとき、点Ｃ2に対応するクラスタに所属する蓄積部分領域特徴の中に、所望の蓄積部分領域特徴が含まれている可能性がある。
そこで、選択閾値θ２が図４におけるｄθより大きくなったとき、そのクラスタを選択する。
ｄθは、以下の（５）式から（４）式を用いて求められる。
【００４５】
【数３】
2006011622.tif 000005
【００４６】
上記（３）式より、
【００４７】
【数４】
2006011622.tif 000006
【００４８】
が求められる。
最終的に、索引検索部１０は、以下の（５）式が成り立つとき、点Ｃ2に対応するクラスタを選択し、そのクラスタに所属する蓄積部分領域特徴を全て抽出する。
そして、この手順を、目的部分領域特徴Ｑが所属するクラスタを除く全てのクラスタに対して行い、抽出された蓄積部分領域特徴を、検索候補特徴として出力する。
【００４９】
【数５】
2006011622.tif 000007
【００５０】
次に、特徴照合部１１は、目的部分領域特徴抽出部９から出力される目的部分領域特徴の集合と、索引検索部１０から出力される検索候補特徴の集合を読み込む。
そして、特徴照合部１１は、次目的部分領域特徴選定部１６により、次に照合すべき目的部分領域特徴が指定されている場合、該目的部分領域特徴を読み込む。この次目的部分領域特徴選定部１６は、本実施形態において後述する。
【００５１】
また、特徴照合部１１は、次検索候補特徴選定部１７から、次に照合すべき検索候補特徴が指定されている場合、該検索候補特徴を読み込む。この次検索候補特徴選定部１７は、本実施形態において後述する。
次に、特徴照合部１１は、次目的部分領域特徴選定部１６から読み込んだ目的部分領域特徴と、次検索候補特徴選定部１７から読み込んだ検索候補特徴の集合との照合を行う。
そして、特徴照合部１１は、目的部分領域特徴と検索候補特徴との距離を、見本特徴間距離を用いて計算する。
例えば、特徴照合部１１は、目的部分領域特徴及び検索候補特徴が単一の符号で構成されている場合、検索候補特徴及び目的部分領域特徴との間の距離を符号間の距離として求め、読み込まれた見本特徴間距離そのものを距離として出力する。
【００５２】
また、特徴照合部１１は、目的部分領域特徴及び検索候補特徴が符号列で構成されている場合、例えば、符号列の対応する要素である符号同士の距離として、各符号同士の組合せに対応した見本特徴間距離を入力し、要素同士の見本特徴間距離を積算することにより、検索候補特徴及び目的部分領域特徴の間の距離として出力する。
そして、特徴照合部１１は、見本特徴の集合において、いずれの見本特徴にも対応しない符号が検出された場合、例えば、符号間の距離を「０」とする。
また、他の実施例として、特徴照合部１１は、見本特徴の集合において、いずれの見本特徴にも対応しない符号が検出された場合、符号間の距離を十分大きな値、例えば、全ての見本特徴間距離の中での最大値に設定するよう構成してもよい。
【００５３】
ここで、特徴照合部１１は、指定された目的部分領域特徴がなければ、初期目的部分領域特徴として、例えば、目的画像の左上角の位置に対応する目的部分領域特徴を指定し、上記検索候補特徴と照合処理を行う（ステップＳ１４）。
また、特徴照合部１１は、指定された検索候補特徴がなければ、初期の検索候補特徴として、例えば、任意に選択した検索候補特徴を指定し、上記目的部分領域特徴と照合する。
そして、特徴照合部１１は、照合計算（検索候補特徴と目的部分領域特徴との間の距離の演算）の結果として、照合した検索候補特徴と目的部分領域特徴との距離値ｄ(ω)を出力する。
【００５４】
次に、照合結果判定部１２は、特徴照合部１１から出力される距離値ｄ(ω)を読み込み、目的画像と類似する部分画像が、現在の照合箇所に存在する可能性があるか否かの判定、すなわち、該距離値ｄ(ω)と、前記選択閾値θ２との比較を行う。
そして、照合結果判定部１２は、距離値ｄ(ω)が選択閾値θ２を以下となったとき、目的画像と類似する部分画像が現在の照合箇所に存在する可能性があると判定し、蓄積部分領域特徴を照合箇所として出力し、一方、距離値ｄ(ω)が選択閾値θ２を超えているとき、目的画像と類似する部分画像が現在の照合箇所に存在する可能性がないと判定し、処理をステップＳ１４へ進める（ステップＳ１５）。
【００５５】
次に、特徴再照合部１３は、見本特徴間距離計算部２から出力される見本特徴間距離、蓄積特徴量子化部４から出力される符号の集合である蓄積特徴の集合と、目的特徴量子化部８から出力される符号の集合である目的特徴の集合と、照合結果判定部１２から出力される照合箇所とを読み込む。
そして、特徴再照合部１３は、読み込んだ蓄積画像に、目的画像と同じ大きさ（縦×横）の注目窓である第２注目窓を設定する。
【００５６】
ここで、特徴再照合部１３は、第２注目窓の配置箇所を、照合結果判定部１２から出力された照合箇所に対応して決定する。
すなわち、特徴再照合部１３は、図５の概念図に示すように、第２注目窓の配置箇所に対する蓄積部分領域の相対的な位置が、目的画像における目的部分領域の相対的な位置と同一になるように、つまり、照合箇所における蓄積部分領域と目的部分領域とが重なる位置に、上記第２注目窓を配置する。
【００５７】
このとき、特徴再照合部１３は、蓄積部分領域特徴部５と同様な処理を行い、蓄積部分領域と目的部分領域との符号の集合の抽出を行う。
次に、特徴再照合部１３は、第２注目窓内において抽出した、蓄積特徴の符号の集合と、目的特徴の符号の集合との照合を行う。
ここで、特徴再照合部１３は、例えば、特徴照合部１１と同様の計算処理により、第２注目窓内の蓄積特徴と目的特徴との距離値ｄの演算を行う。
そして、特徴再照合部９は、照合計算結果である距離値ｄを出力する（ステップＳ１６）。
【００５８】
次に、照合結果再判定部１４は、特徴再照合部１３から出力される距離値ｄを読み込み、目的画像と類似する部分画像が現在の照合箇所に存在する可能性があるか否かの判定、すなわち、該距離値ｄと、前記検索閾値θとの比較を行う。
このとき、照合結果再判定部１４は、距離値ｄが検索閾値θ以下であるとき、目的画像と類似する部分画像が現在の照合箇所に存在すると判定し、蓄積画像における該照合箇所を検出箇所として、この検出箇所の位置及び判定結果（存在したことを示す情報）を出力し、一方、距離値ｄが検索閾値θを超えたとき、目的画像と類似する部分画像が現在の照合箇所に存在しないと判定し、処理をステップＳ１９へ進める（ステップＳ１７）。
【００５９】
上記選択閾値θ２は、前記検索閾値θから決定され、以下に示す（６）式に示すように、選択閾値θ２を設定すると、検索漏れを生じることがない。
【００６０】
【数６】
2006011622.tif 000008
【００６１】
上記（６）式において、Ｎは第１注目窓を重複も隙間もなく蓄積画像中に配置したと仮定したとき、任意位置に配置された第２照合窓に含まれる第１照合窓の最少数であり、以下に示す（７）〜（９）式により与えられる。
【００６２】
【数７】
2006011622.tif 000009
【００６３】
【数８】
2006011622.tif 000010
【００６４】
【数９】
2006011622.tif 000011
【００６５】
ここで、（８）式におけるＮxは横方向の第１の照合窓の数であり、（９）式におけるＮyは縦方向の第１の照合窓の数である。
ただし、（ｑx、ｑy）は目的画像の大きさ、すなわち、第２注目窓の大きさであり、（ωx，ωy）は第１注目窓の大きさである。
次に、検索結果候補選択部１５は、照合結果再判定部１４から出力される検出箇所（位置情報を含む）と、特徴再照合部１３から出力される距離値ｄを読み込む。
【００６６】
次に、検索結果候補選択部１５は、上記検出箇所と、この検出箇所における距離値ｄとを、検索結果候補として登録する。
検索結果候補選択部１５は、例えば、距離値の大小にかかわらず、読み込んだ検出箇所と距離値ｄとの組を全て登録する。
また、検索結果候補選択部１５は、他の実施形態として、検索結果候補が予め定められた数量以下になるように登録する構成とすることも可能である。
【００６７】
すなわち、検索結果候補選択部１５は、検索結果候補を該数量までは無条件に検出箇所と距離値の組を登録し、該数量を超過する場合、例えば、すでに読み込まれた検索結果候補の中における最大距離値ｄmaxと、以降読み込んだ距離値ｄとを比較し、読み込んだ距離値ｄが最大距離値ｄmaxを下回る場合、最大距離値ｄmaxに対応する候補を削除し、新たに読み込んだ検出箇所と距離値ｄの組とを候補として登録する。
このように、検索結果候補選択部１５は、蓄積画像から上述した方法により検索結果候補を出力する（ステップＳ１８）。
【００６８】
次に、次目的部分領域特徴選定部１６は、目的部分領域特徴抽出部９から出力される目的部分領域特徴の集合を読み込み、必要に応じて、特徴照合部１１から出力される距離値ｄ(ω)，検索閾値更新部１８から出力される選択閾値θ２，及び周辺距離下限値計算部２１から出力される周辺距離下限値を読み込む。
上記検索閾値更新部１８及び周辺距離下限値計算部２１は、他の実施例において後述する。
そして、次目的部分領域特徴選定部１６は、次に照合すべき目的部分領域特徴の選択、すなわち次に照合する目的部分領域特徴の有無の検出を行い、照合箇所がないことを検出すると処理をステップＳ２０へ進め、一方、照合箇所があることを検出すると、次に照合する目的部分領域特徴を選択して、処理をステップＳ１４へ進める（ステップＳ１９）。
【００６９】
このとき、次目的部分領域特徴選定部１６は、例えば、現在注目している蓄積部分領域特徴に対して、照合が終了していない目的部分領域特徴があるか否かを判定して、終了していない目的部分領域特徴があれば、この中から任意の目的部分領域特徴を１つ選択し、全ての目的部分領域特徴の照合が終了している場合、次の、蓄積部分領域特徴に注目を変更するため、処理をステップＳ２０へ進める。
また、別の実施形態として、次目的部分領域特徴選定部１６は、上記周辺距離下限値を読み込んだ場合、この距離下限値が、読み込んだ選択閾値θ２を上回る目的部分領域特徴との照合を省略し、この距離下限値が選択閾値θ２以下の目的部分領域特徴から任意に１つ選択する構成とすることも可能である。
そして、次目的部分領域特徴選定部１６は、終了していない目的部分領域特徴があれば、照合箇所が選択された目的部分領域特徴と、この目的部分特徴に対応する目的画像内の位置を出力する。
【００７０】
次に、次検索候補特徴選定部１７は、索引検索部１０から出力される蓄積部分領域特徴の集合を読み込み、次に照合すべき検索候補特徴を選択、すなわち次に照合する検索候補特徴の有無の検出を行い、照合する検索候補特徴がないことを検出すると処理を終了させ、一方、照合する検索候補特徴があることを検出すると、次に照合すべき検索候補特徴を選択して、処理をステップＳ１４へ進める（ステップＳ２０）。
このとき、次検索候補特徴選定部１７は、例えば、照合する検索候補特徴があることを検出すると、照合が終了していない検索候補特徴から任意に１つ選択する。
これにより、次検索候補特徴選定部１７は、選択された検索候補特徴を、特徴照合部１１に対して出力する。
【００７１】
＜第２の実施例＞（請求項３に対応）
図６は、請求項３に記載の方法を適用した第２の実施例による部分画像検索システムの構成例を示すブロック図である。
第２の実施例の部分画像検索システムは、請求項１に記載の方法を適用した第１の実施例による部分画像検索システムと同様な構成であり、異なる構成として、図６に示すように、検索閾値更新部１８を追加して設け、任意の目的画像、すなわち見本となる検索したい画像と、蓄積画像群、すなわち検索される複数の画像である蓄積画像の集合を入力とし、目的画像と類似する画像が含まれている部分画像の蓄積画像内における箇所を出力する。
【００７２】
上記検索閾値更新部１８は、上記検索結果候補選択部１５から出力された検索結果候補から、上記特徴再照合部１３から出力された距離値に基づいて、所定の距離内にある候補を検出し、この検出した候補の距離値に基づいて新たに検索閾値θを設定する。
次に、上述した見本特徴作成部１から検索閾値更新部１８における部分画像の検出処理を、図７を用いて具体的に説明する。ここで、図７は、図６に示す部分画像検索装置の動作例を示すフローチャートである。
【００７３】
図７のフローチャートは、図２に示す第１の実施例のフローチャートに対して、ステップＳ１３の「検索結果の候補選択」の処理の次に、ステップＳ１６の「検索閾値更新」の処理が追加されたのみで、他の処理については同様であるため、このステップＳ１６の処理の説明のみを行う。
検索閾値更新部１８は、検索結果候補選択部１５から出力される検索結果候補を読み込み、この読み込んだ検索結果候補の中から、距離値が最大の検索結果候補を選び出し、選択した検索結果候補の距離値が検索閾値θ以下であるか否かの判定を行い、この距離値が検索閾値θ以下であることを検出した場合、検索閾値θをその距離値と同じ値に更新する。
そして、検索閾値更新部１８は、（５）式に基づいて検索閾値θから選択閾値θ２を計算し、更新した検索閾値θとともに出力する（ステップＳ２１）。これ以降は、この更新された検索閾値θ及び選択閾値θ２が照合結果の判定に用いられる。
【００７４】
＜第３の実施例＞（請求項５に対応）
図８は、請求項５に記載の方法を適用した第３の実施例による部分画像検索システムの構成例を示すブロック図である。
この第３の実施例による部分画像検索システムは、第２の実施例と同様の構成であり、異なる構成として、第２の実施例の部分画像検索システムに対して、目的代表特徴抽出部１９を加えたものであり、目的画像、すなわち見本となる検索したい画像と、蓄積画像群、すなわち検索される画像である蓄積画像の集合とを入力し、目的画像と類似する画像が含まれてた部分画像の、上記蓄積画像内における箇所を検索し、検索結果を出力する。
この目的代表特徴抽出部１９は、上記目的部分領域特徴抽出部９から出力された目的部分領域特徴の集合における目的部分領域集合を分類（クラスタリング）して、各目的部分領域特徴に共通する特徴としての目的代表特徴を抽出する。
【００７５】
次に、上述した見本特徴作成部１から目的代表特徴抽出部１９における部分画像の検出処理を、図９を用いて具体的に説明する。ここで、図９は、図８に示す部分画像検索システムの動作例を示すフローチャートである。
図９のフローチャートは、図７に示す第２の実施例のフローチャートに対して、ステップＳ１２の「目的部分領域特徴の抽出」の処理の次に、ステップＳ２２の「目的代表特徴の抽出」の処理が追加されたのみで、他の処理については同様であるため、このステップＳ２２の処理の説明のみを行う。
【００７６】
目的代表特徴抽出部１９は、目的部分領域特徴抽出部９から出力される目的部分領域特徴の集合を読み込み、これら複数の目的部分領域特徴に対してクラスタリング処理を行う。
このとき、目的代表特徴抽出部１９は、例えば、クラスタを１つだけ用意し（共通の特徴ベクトルを抽出する）、上記集合における全ての目的部分領域特徴をそのクラスタに所属させる（１つの目的代表特徴を出力することになる）。
また、目的代表特徴抽出部１９は、別の実施例として、読み込んだ目的部分領域特徴の数だけクラスタを用意し、これら各クラスタに１つずつ目的部分領域特徴を割り当てる構成とすることもできる（目的代表特徴の集合を出力することになる）。
【００７７】
さらに、目的代表特徴抽出部１９は、別の実施例として、目的部分領域特徴に対応する目的画像中の位置を、読み込んだ全ての目的部分領域特徴について抽出し、その存在範囲を格子状に区切り、各格子をクラスタと対応させる構成とすることも可能である。
また、さらに、目的代表特徴抽出部１９は、別の実施例として、同一クラスタ内の目的部分領域特徴同士の距離の最大値が、予め定められた閾値である分類閾値を上回らないように、クラスタを併合することも可能である。
【００７８】
このとき、目的代表特徴抽出部１９は、クラスタの初期状態として、例えば、読み込んだ目的部分領域特徴の数だけ用意したクラスタに１つずつ目的部分領域を割り当てたものを用いる。
次に、目的代表特徴抽出部１９は、上記各クラスタから、該クラスタを代表する部分領域特徴である代表特徴を抽出する。目的代表特徴抽出部１９は、例えば、クラスタ内の任意に選択した１つの目的部分領域特徴を代表特徴とする。
【００７９】
また、目的代表特徴抽出部１９は、別の実施例として、ある特定位置に対応する目的部分領域特徴を代表特徴とすることもできる。
この特定位置とは、例えば、目的画像の左上角の位置などである。
さらに、目的代表特徴抽出部１９は、別の実施例として、クラスタ内の目的部分領域特徴の重心にある目的部分特徴を代表特徴とする構成とすることもできる。
そして、目的代表特徴抽出部１９は、上述した第３の実施例における各実施例により求めた、代表特徴あるいはその集合を出力する（ステップＳ２２）。
次のステップＳ１３において、索引検索部１０は、上記目的代表特徴を用いて、蓄積画像の索引との照合処理を行う。
【００８０】
＜第４の実施例＞（請求項７に対応）
図１０は、請求項７に記載の方法を適用した第４の実施例による部分画像検索システムの構成例を示すブロック図である。
この第４の実施例による部分画像検索システムは、第３の実施例と同様な構成であり、異なる構成として、第３の実施例の部分画像検索システムに対して、目的部分領域間距離計算部２０と、周辺距離下限値計算部２１とを加えたものであり、目的画像、すなわち見本となる検索したい画像と、蓄積画像群、すなわち検索される画像である蓄積画像の集合とを入力し、目的画像と類似する画像が含まれてた部分画像の、上記蓄積画像内における箇所を検索し、検索結果を出力する。
【００８１】
上記目的部分領域間距離計算部２０は、上記目的部分領域特徴抽出部９から出力された目的部分領域特徴について、部分領域特徴同士の距離である距離を計算する。
また、目的代表特徴抽出部１５がある場合には、目的部分領域特徴と、それに対応する目的代表特徴との距離を計算する。
上記周辺距離下限値計算部２１は、特徴照合部１１から出力された距離値と、目的部分領域間距離計算部２０から出力された部分領域間距離の数値とを用い、特徴照合部１１で照合を行った検索候補特徴と、上記目的部分領域特徴抽出部９から出力された各目的部分領域特徴との距離の下限値を計算する。
【００８２】
次に、上述した見本特徴作成部１から周辺距離下限値計算部２１における部分画像の検出処理を、図１１を用いて具体的に説明する。ここで、図１１は、図１０に示す部分画像検索システムの動作例を示すフローチャートである。
図１１のフローチャートは、図９に示す第３の実施例のフローチャートに対して、ステップＳ２２の「目的代表特徴の抽出」の処理の次に、ステップＳ２３の「目的部分領域間距離の演算」の処理が追加され、また、ステップＳ２１の「検索閾値の更新」の処理の次に、ステップＳ２４の「周辺距離下限値の演算」の処理が追加されたのみで、他の処理については同様であるため、このステップＳ２３及びステップＳ２４の処理の説明のみを行う。
【００８３】
目的部分領域間距離計算部２０は、目的部分領域特徴抽出部９から出力される目的部分領域特徴の集合を読み込み、各目的部分領域特徴同士の距離を計算する。
そして、目的部分領域間距離計算部２０は、例えば、全ての目的部分領域特徴の組に対して距離計算を行う。
また、別の実施例として、目的代表特徴抽出部１９が設けられている場合には、さらにこの目的代表特徴抽出部１９から出力される目的代表特徴の集合を読み込み、各目的部分領域特徴と、それに対応する目的部分領域特徴との距離を計算することも可能である。
上述したように、目的部分領域間距離計算部２０は、目的部分領域特徴同士の距離、あるいは目的部分領域特徴と目的代表特徴との距離を出力する。
上述した距離を用いて、ステップＳ８において、索引による検索が行われる。
【００８４】
次に、周辺距離下限値計算部２１は、特徴照合部１１から出力される距離値と、目的部分領域間距離計算部２０から出力される部分領域間距離とを読み込む。
そして、周辺距離下限値計算部２１は、読み込んだ距離値と部分領域間距離とから、蓄積部分領域特徴と各目的部分領域特徴との距離下限値を計算する。
このとき、周辺距離下限値計算部２１は、蓄積部分領域特徴ｆＤ（Ｗ）と、目的部分領域特徴ｆＱ２（Ｗ）との距離の下限値ｄ(ｆＤ（Ｗ），ｆＱ２（Ｗ）)は、三角不等式に基づいて、以下の（１０）式により求められる。，
【００８５】
【数１０】
2006011622.tif 000012
【００８６】
上記（１０）式において、ｄ(ｆＤ（Ｗ），ｆＱ１（Ｗ）)は特徴照合部１１から読み込んだ距離値であり、ｄ(ｆＱ１（Ｗ），ｆＱ２（Ｗ）)は読み込んだ目的部分領域間距離である。
上述したように、周辺距離下限値計算部２１は、蓄積部分領域特徴と、目的部分領域特徴との距離の下限値である周辺距離下限値を出力する。
そして、次のステップＳ１９において、次目的部分領域特徴選定部１６は、上記周辺距離下限値を入力し、この距離下限値が、読み込んだ選択閾値θ２を上回る目的部分領域特徴との照合を省略し、この距離下限値が選択閾値θ２以下の目的部分領域特徴から任意に１つ選択する。
【００８７】
＜第５の実施例＞（請求項１３に対応）
図１２は、請求項１３に記載の方法を適用した第５の実施例による部分画像検索システムの構成例を示すブロック図である。
この第５の実施例による部分画像検索システムは、第４の実施例と同様な構成であり、異なる構成として、第４の実施例の部分画像検索システムに対して、特徴存在範囲確定部２２を加えたものであり、目的画像、すなわち見本となる検索したい画像と、蓄積画像群、すなわち検索される画像である蓄積画像の集合とを入力し、目的画像と類似する画像が含まれてた部分画像の、上記蓄積画像内における箇所を検索し、検索結果を出力する。
上記特徴存在範囲確定部２２は、上記見本特徴作成部１から出力される各見本特徴について、この見本特徴に割り当てられる可能性のある上記蓄積特徴抽出部３及び目的特徴抽出部７から出力される各々の画像の特徴（蓄積特徴，目的特徴）が存在し得る範囲である特徴存在範囲を計算する。
【００８８】
次に、上述した見本特徴作成部１から特徴存在範囲確定部２２における部分画像の検出処理を、図１３を用いて具体的に説明する。ここで、図１３は、図１２に示す部分画像検索システムの動作例を示すフローチャートである。                 
図１３のフローチャートは、図１１に示す第４の実施例のフローチャートに対して、ステップＳ２の「見本特徴の作成」とステップＳ３の「見本特徴間距離の計算」のと処理の間に、ステップＳ２５の「特徴存在範囲の確定」の処理が追加されたのみで、他の処理については同様であるため、このステップＳ２５の処理の説明のみを行う。
【００８９】
特徴存在範囲確定部２２は、見本特徴作成部１から出力される見本特徴の集合を読み込み、この集合の各見本特徴に割り当てられる蓄積特徴及び目的特徴が存在する可能性のある特徴空間内の範囲である特徴存在範囲を、上記各々の見本特徴に対して設定する。
このとき、特徴存在範囲確定部２２は、例えば、蓄積特徴量子化部４及び目的特徴量子化部８において、割当閾値以下で最も距離の近い見本特徴に対して割り当てを行う場合、見本特徴を中心として、半径が割当閾値に等しい超球を特徴存在範囲として設定する（ステップＳ２５）。
【００９０】
また、特徴存在範囲確定部２２は、別の実施例として、蓄積特徴量子化部４及び索引付与部６において、最も距離の近い見本特徴に対して割り当てを行う場合、見本特徴を中心として、半径が見本特徴間の距離の最大値の半分に等しい超球を特徴存在範囲として設定するように構成されても良い。
上述したように、特徴存在範囲確定部２２は、上述した方法のいずれかで求めた特徴存在範囲の集合を出力する。
上述した特徴存在範囲を用いて、ステップＳ３において、見本特徴間の距離が計算される。
【００９１】
＜実験＞
本発明を適用した装置の動作例を以下に示す。
ここで、蓄積画像群として、大きさ３８４×２５６ピクセルの画像１０００枚を用い、目的画像として、大きさ８０×８０ピクセルの画像１０枚を、上記蓄積画像群中の任意の箇所から切り出して用いた。
また、部分領域は大きさを６４×６４ピクセルとし、マージンを縦方向及び横方向共に１６ピクセルと設定して、部分画像の切り出しを行った。
すなわち、蓄積画像１枚あたりの部分領域の数は２７３個であり、目的画像の部分領域の数は２８９個である。
【００９２】
蓄積画像及び目的画像の特徴、すなわち蓄積特徴及び目的特徴としては、大きさ８×８ピクセルの小領域におけるＲＧＢ値を用いたため、部分領域特徴の次元は１９２次元となっている。
代表特徴は、学習信号を用いてベクトル量子化の符号帳を作成することによって、６４個生成し、学習信号として蓄積画像群から１０枚の画像を選択して取り出して用いた。
索引付与部６及び索引検索部１０は、「信号検出方法、信号検出装置、記録媒体及びプログラム」（特開2002-236496)記載の実施例のように、ベクトル量子化に基づく索引付与と索引検索と実施し、クラスタ数を１２８とした。
また、距離尺度は自乗誤差を用い、検索閾値は２０００とした。
【００９３】
本発明の効果を確認するため、本発明を適用した場合と、適用しない場合とにおける検索所要時間の比較を行った。
本実験の結果は、図１４の表に示すように、従来例（適用しない）においては検索時間として「８.３７秒」であったが、本発明（適用した）においては検索時間として「３.１７秒」となった。
上記図１４からわかるように、見本特徴を用いることにより、予め見本特徴間距離を求めておくことができるので、後の蓄積特徴及び目的特徴間の距離の演算が、上記見本特徴間距離を用いることにより大幅に低減することができるので、検索時間を短縮することが可能となる。
【００９４】
なお、図１における部分画像検索装置の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、部分画像の検索処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００９５】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００９６】
【図１】本発明の第１の実施例による部分画像検索システムの構成例を示すブロック図である。
【図２】図１の部分画像検索システムの動作例を示すフローチャートである。
【図３】蓄積画像において部分画像を設定する際に、配置のマージンについて説明する概念図である。
【図４】索引検索部６がクラスタを選択するときの原理を説明する概念図である。
【図５】蓄積画像における照合窓の設定を説明する概念図である。
【図６】本発明の第２の実施例による部分画像検索システムの構成例を示すブロック図である。
【図７】図６の部分画像検索システムの動作例を示すフローチャートである。
【図８】本発明の第３の実施例による部分画像検索システムの構成例を示すブロック図である。
【図９】図８の部分画像検索システムの動作例を示すフローチャートである。
【図１０】本発明の第４の実施例による部分画像検索システムの構成例を示すブロック図である。
【図１１】図１０の部分画像検索システムの動作例を示すフローチャートである。
【図１２】本発明の第５の実施例による部分画像検索システムの構成例を示すブロック図である。
【図１３】図１２の部分画像検索システムの動作例を示すフローチャートである。
【図１４】画像を検索する際の、従来例と本発明との検索所要時間の比較を示す表である。
【符号の説明】
【００９７】
１…見本特徴作成部        ２…見本特徴間距離計算部  ３…蓄積特徴抽出部          ４…蓄積特徴量子化部      ５…蓄積部分領域特徴抽出部    ６…索引付与部
７…目的特徴抽出部        ８…目的特徴量子化部    ９…目的部分領域特徴抽出部
１０…索引検索部          １１…特徴照合部          １２…照合結果判定部        １３…特徴再照合部        １４…照合結果再判定部    １５…検索結果候補選択部
１６…次目的部分領域特徴選定部    １７…次検索候補特徴選定部  １８…検索閾値更新部
１９…目的代表特徴抽出部  ２０…目的部分領域間距離計算部
２１…周辺距離下限値計算部  ２２…特徴存在範囲確定部
【図１】
2006011622.tif 000013
【図２】
2006011622.tif 000014
【図３】
2006011622.tif 000015
【図４】
2006011622.tif 000016
【図５】
2006011622.tif 000017
【図６】
2006011622.tif 000018
【図７】
2006011622.tif 000019
【図８】
2006011622.tif 000020
【図９】
2006011622.tif 000021
【図１０】
2006011622.tif 000022
【図１１】
2006011622.tif 000023
【図１２】
2006011622.tif 000024
【図１３】
2006011622.tif 000025
【図１４】
2006011622.tif 000026