(57)【要約】【課題】  索引の情報量を低減し、索引の保持に必要な記憶容量を削減し、かつ検索漏れが生じない部分画像検索システム及び方法並びにプログラムを提供する。【解決手段】  本発明の部分画像検索装置は、蓄積画像群から、類似した部分画像を含む位置を検出するものであり、蓄積部分領域特徴各々に索引を付し、目的部分領域特徴に類似する蓄積部分領域特徴を、上記索引を用いて検索候補特徴として抽出し、検索候補特徴と目的部分領域特徴との距離を計算し、距離に基づいて類似する部分画像が蓄積画像群中に存在するか否かを判定し、照合結果判定部にて、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所において、蓄積特徴に対し、目的画像と同一の大きさの照合窓を設定し、目的特徴との特徴距離を計算し、特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する。【選択図】    図１
2005352990.tif 000002
【特許請求の範囲】
【請求項１】
データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索方法であり、
前記蓄積画像群の各画像の特徴である蓄積特徴を抽出する蓄積特徴抽出過程と、
所定の大きさの注目窓を所定の間隔でずらしつつ、各位置における注目窓内の特徴を、蓄積部分領域特徴として抽出する蓄積部分領域特徴抽出過程と、
前記蓄積部分領域特徴各々を標識する索引を付与する索引付与過程と、
前記目的画像の特徴である目的特徴を抽出する目的特徴抽出過程と、
該目的特徴において、所定の大きさの注目窓を設定し、該注目窓をずらしつつ、各位置における注目窓内の特徴を、目的部分領域特徴として抽出する目的部分領域特徴抽出過程と、
前記目的部分領域特徴の集合に類似する蓄積部分領域特徴を、前記索引を用いて検索候補特徴として抽出する索引検索過程と、
該検索候補特徴と前記目的部分領域特徴との距離を計算する特徴照合過程と、
前記距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在する可能性があるか否かを判定する照合結果判定過程と、
前記照合結果判定過程にて、目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴に対し、目的画像と同一の大きさの照合窓を設定し、前記目的特徴との特徴距離を計算する特徴再照合過程と、
前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する照合結果再判定過程と、
前記照合結果再判定過程にて、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択過程と、
前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定過程と、
前記検索候補特徴の集合の中から、次に照合すべき検索候補特徴を指定する次検索候補特徴選定過程と
を備えることを特徴とする部分画像検索方法。
【請求項２】
前記照合結果再判定過程において、前記特徴距離と、該特徴距離に対応する閾値である検索閾値とが比較され、
前記目的画像と類似する部分画像が前記蓄積画像中の当該箇所に存在するか否かが判定され、
前記索引探索過程において、前記目的部分領域特徴抽出過程から導かれたいずれかの目的部分領域特徴との距離が、前記検索閾値から決定される選択閾値を下回る蓄積部分領域特徴を、前記索引を用いて抽出し、前記照合結果判定過程において、前記距離と、前記選択閾値とが比較され、前記目的画像と類似する部分画像が前記蓄積画像中の当該箇所に存在する可能性の有無が判定されることを特徴とする請求項１に記載の部分画像検索方法。
【請求項３】
前記検索結果候補選択過程において、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所が、前記特徴距離の小さい順に、予め定められた数量だけ選択されて検索結果候補とされ、
該検索結果候補から、前記特徴距離に基づいてある候補を検出し、該候補の距離値を新たに検索閾値として設定する検索閾値更新過程と
を備えることを特徴とする請求項２に記載の部分画像検索方法。
【請求項４】
前記索引検索過程において、前記目的部分領域特徴抽出過程により導かれた全ての目的部分領域特徴を用い、検索候補特徴が抽出されることを特徴とする請求項１から請求項３のいずれかに記載の部分画像検索方法。
【請求項５】
前記目的部分領域特徴を分類し、各分類を代表する部分領域特徴である代表特徴を抽出する目的代表特徴抽出過程と
を備え、
前記索引検索過程において、前記目的部分領域特徴に替え、前記目的代表特徴抽出過程により導かれた代表特徴を用いることを特徴とする請求項１から請求項３のいずれかに記載の部分画像検索方法。
【請求項６】
前記次目的部分領域特徴選定過程において、蓄積部分領域特徴との距離が前記選択閾値を超えることが検出された、前記目的部分領域特徴抽出過程にて抽出された目的部分領域特徴を、次に照合すべき部分領域特徴として指定せずに照合を省略することを特徴とする、請求項１から請求項５のいずれかに記載の部分画像検索方法。
【請求項７】
前記目的部分領域特徴各々の部分距離を計算する目的部分領域間距離計算過程と、
前記距離と前記部分距離とを用い、前記特徴照合過程で照合を行った蓄積部分領域と、前記目的部分領域特徴抽出過程にて抽出された各目的部分領域特徴との距離の距離下限値を計算する周辺距離下限値計算過程と
を備え、
前記次目的部分領域特徴選定過程において、前記距離下限値と、前記選択閾値とを比較し、距離下限値が選択閾値を下回る目的部分領域特徴の箇所を、次に照合すべき部分領域として指定することを特徴とする請求項６に記載の部分画像検索方法。
【請求項８】
データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索装置であり、
前記蓄積画像群の各画像の特徴である蓄積特徴を抽出する蓄積特徴抽出部と、
所定の大きさの注目窓を所定の間隔でずらしつつ、各位置における注目窓内の特徴を、蓄積部分領域特徴として抽出する蓄積部分領域特徴抽出部と、
前記蓄積部分領域特徴各々を標識する索引を付与する索引付与部と、
前記目的画像の特徴である目的特徴を抽出する目的特徴抽出部と、
該目的特徴において、所定の大きさの注目窓を設定し、該注目窓をずらしつつ、各位置における注目窓内の特徴を、目的部分領域特徴として抽出する目的部分領域特徴抽出部と、
前記目的部分領域特徴の集合に類似する蓄積部分領域特徴を、前記索引を用いて検索候補特徴として抽出する索引検索部と、
該検索候補特徴と前記目的部分領域特徴との距離を計算する特徴照合過程と、
前記距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在する可能性があるか否かを判定する照合結果判定部と、
前記照合結果判定過程にて、目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴に対し、目的画像と同一の大きさの照合窓を設定し、前記目的特徴との特徴距離を計算する特徴再照合部と、
前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する照合結果再判定部と、
前記照合結果再判定過程にて、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択部と、
前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定部と、
前記蓄積部分領域特徴の集合の中から、次に照合すべき蓄積部分領域を指定する次検索候補特徴選定部と
を有することを特徴とする部分画像検索装置。
【請求項９】
データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索処理をコンピュータに実行させるプログラムであり、
前記蓄積画像群の各画像の特徴である蓄積特徴を抽出する蓄積特徴抽出処理と、
所定の大きさの注目窓を所定の間隔でずらしつつ、各位置における注目窓内の特徴を、蓄積部分領域特徴として抽出する蓄積部分領域特徴抽出処理と、
前記蓄積部分領域特徴各々を標識する索引を付与する索引付与処理と、
前記目的画像の特徴である目的特徴を抽出する目的特徴抽出処理と、
該目的特徴において、所定の大きさの注目窓を設定し、該注目窓をずらしつつ、各位置における注目窓内の特徴を、目的部分領域特徴として抽出する目的部分領域特徴抽出処理５と、
前記目的部分領域特徴の集合に類似する蓄積部分領域特徴を、前記索引を用いて検索候補特徴として抽出する索引検索処理と、
該検索候補特徴と前記目的部分領域特徴との距離を計算する特徴照合処理と、
前記距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在する可能性があるか否かを判定する照合結果判定処理と、
前記照合結果判定過程にて、目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴に対し、目的画像と同一の大きさの照合窓を設定し、前記目的特徴との特徴距離を計算する特徴再照合処理と、
前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する照合結果再判定処理と、
前記照合結果再判定過程にて、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択処理と、
前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定処理と、
前記蓄積部分領域特徴の集合の中から、次に照合すべき蓄積部分領域を指定する次検索候補特徴選定処理と
を有する部分画像検索の処理をコンピュータに実行させるプログラム。
【請求項１０】
請求項９に記載の部分画像検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、蓄積された複数の画像から、与えられた画像と類似した部分画像を含む画像及びその部分画像が含まれている位置を同定するのに適した部分画像検索システム及び方法並びにプログラムに関する。
【背景技術】
【０００２】
デジタルカメラの普及や記録媒体の大容量化・低価格化、さらに大容量ネットワークの普及により、容易に大容量のデジタル画像を取得して保存する環境が整ってきている。
そのため、大量の画像から所望の画像を高速に探し出す高速画像検索技術が必要となってきており、特に画像の部分検索は、検索したい画像が蓄積されている画像の一部分であるため、比較の処理が多くなり、さらに高速性が要求される。
この部分画像検索技術は、膨大な画像データベースの中から、高速に目的の画像をその一部分として含む画像を検索する画像検出技術に用いられる。
【０００３】
例えば、画像データベースに蓄積された画像の中から、特定人物の顔が撮影されている画像を検出してユーザに提示したり、特定の物体や建造物などが撮影されている画像を含まれるホームページを検索したりする検索技術に用いられる。
従来、上記部分画像検索方法に関しては、見本となる検索したい画像と類似した画像の場所をより大きなサイズの画像の中から漏れなく正確に探し出す高速部分画像検出方法が、物体検出装置（例えば、特許文献１参照）や、高速テンプレート照合法（例えば、非特許文献１参照）等として知られている。
【０００４】
しかし、上述した方法においては、目的画像との類似性によらず、全ての画像の全ての部分領域に対して照合検索を行うため、多数の無駄な照合処理が発生してしまい、検索を高速化できないという欠点がある。
そのため、部分画像の検索を高速化する方法として、容易に画像の検索を行うため、各画像に予め索引をつけておくことが考えられる。
しかし、各画像から位置的にあり得る全ての部分画像を抽出した場合、その画像数が膨大となり、これら画像の全てに索引を付与すると、索引保持に必要となる記憶容量が膨大になるという問題点がある。
【０００５】
これに対し、従来、上記問題点を解決する方法として、部分画像をクラスタリングすることによって、索引を付与する部分画像の数を削減する部分画像検出方法（例えば、非特許文献２参照）が知られている．
【特許文献１】特開平０９−３３０４０４号公報
【非特許文献１】「目的画像の部分領域間の残差情報を利用した高速テンプレート照合法」、川西隆仁，et al、情報科学技術フォーラム講演論文集、LI-008，2003年９月
【非特許文献２】「ＷＡＬＲＵＳ：A similarity retrieval algorithm for image databases」、A. Natsev，et al、ＩＥＥＥ Transactions on Knowledge and Data Engineering，Vol.16，No-3，2004年３月
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した非特許文献２に示す部分画像をクラスタリングする部分画像検出方法にあっては、特許文献１及び非特許文献１に対して部分画像の数を減少させることができるが、容量削減の観点において部分画像の数の削減が十分ではなく、索引の保持に必要となる記憶容量が膨大になるという問題点が解消されていない。
また、上記非特許文献２の方法においては、部分画像のクラスタリングに要する計算時間が非常に長く必要となるため、索引を付与するために必要な時間が膨大になるという欠点がある。
本発明は、このような事情に鑑みてなされたもので、索引の情報量を低減し、索引の保持に必要な記憶容量を削減し、かつ検索漏れが生じない部分画像検索システム及び方法並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の部分画像検索方法は、データベースに登録されている蓄積画像群から、検索対象の目的画像に類似した部分画像を含む画像及び該画像における部分画像の位置を検出する部分画像検索方法であり、前記蓄積画像群の各画像の特徴である蓄積特徴を抽出する蓄積特徴抽出過程と、所定の大きさの注目窓を所定の間隔でずらしつつ、各位置における注目窓内の特徴を、蓄積部分領域特徴として抽出する蓄積部分領域特徴抽出過程と、前記蓄積部分領域特徴各々を標識する索引を付与する索引付与過程と、前記目的画像の特徴である目的特徴を抽出する目的特徴抽出過程と、該目的特徴において、所定の大きさの注目窓を設定し、該注目窓をずらしつつ、各位置における注目窓内の特徴を、目的部分領域特徴として抽出する目的部分領域特徴抽出過程と、前記目的部分領域特徴の集合に類似する蓄積部分領域特徴を、前記索引を用いて検索候補特徴として抽出する索引検索過程と、該検索候補特徴と前記目的部分領域特徴との距離を計算する特徴照合過程と、前記距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在する可能性があるか否かを判定する照合結果判定過程と、前記照合結果判定過程にて、目的画像と類似する部分画像が存在する可能性があると判定された蓄積画像中の箇所において、前記蓄積特徴に対し、目的画像と同一の大きさの照合窓を設定し、前記目的特徴との特徴距離を計算する特徴再照合過程と、前記特徴距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在するか否かを判定する照合結果再判定過程と、前記照合結果再判定過程にて、目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を検索結果候補とする検索結果候補選択過程と、前記目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴を指定する次目的部分領域特徴選定過程と、前記蓄積部分領域特徴の集合の中から、次に照合すべき蓄積部分領域を指定する次検索候補特徴選定過程とを備えることを特徴とする。
【発明の効果】
【０００８】
以上説明したように、本発明によれば、蓄積画像群の各画像において、部分領域より狭い所定の間隔毎に、部分領域を間引いて抽出して索引を付与することにより、ピクセル単位に画像全体にずらしながら、蓄積された画像群の各画像に対し、部分画像を抽出して索引を付与する非特許文献２などの公知の方法に比較し、索引付与に要する時問を増加させることなく、索引の保持に必要な記憶容量を削減し、かつ、目的画像に対して、画像全体に渡り、間隔を有さずに全ての部分領域を抽出するため、蓄積画像の検索処理において検索漏れを生じさせないことを保証できるという効果が得られる。
【発明を実施するための最良の形態】
【０００９】
＜第１の実施例＞
以下、本発明の第１の実施例による部分画像検索装置を図面を参照して説明する。図１は上記第１の実施例の部分画像検索装置の一構成例を示すブロック図である。
この図において、本実施例の部分画像検索装置は、蓄積特徴抽出部１と、蓄積部分領域特徴抽出部２と、索引付与部３と、目的特徴抽出部４と、目的部分領域特徴抽出部５と、索引検索部６と、特徴照合部７と、照合結果判定部８と、特徴再照合部９と、照合結果再判定部１０、検索結果候補選択部ｌｌと、次目的部分領域特徴選定部１２と、次検索候補特徴選定部１３とを有しており、目的画像、すなわち参照している検索したい画像と、データベース等に蓄積されている蓄積画像群、すなわち検索される被検索画像である蓄積画像の集合を入力とし、上記目的画像と類似する部分画像が含まれている蓄積画像内の箇所を出力する。
【００１０】
蓄積特徴抽出部１は、蓄積画像群の各画像から、画像を表現する蓄積特徴を、画像全体、または所定の画素数からなるブロック単位に抽出する。
蓄積部分領域特徴抽出部２は、上記蓄積特徴抽出部１から出力された特徴に対し、予め定められた所定の大きさの注目窓を、予め定められた所定の間隔で設定し（所定の間隔でずらし）、各注目窓内の特徴である蓄積部分領域特徴を抽出する。
索引付与部３は、上記蓄積部分領域特徴抽出部２から出力される各蓄積部分領域特徴を、各々ベクトル量子化し、ベクトル量子化の符号語を、標識のための索引として付与する。
【００１１】
目的特徴抽出部４は、目的画像から画像を表現する目的特徴を抽出する。
目的部分領域特徴抽出部５は、上記目的特徴抽出部４が抽出した目的特徴に対して、予め定められた所定の大きさの注目窓を設定し、この注目窓を１ピクセルずつずらしながら、各注目窓内の特徴である目的部分領域特徴の抽出を行う。
索引検索部６は、上記索引付与部３から出力きれる索引を用いて、上記目的部分領域特徴抽出部５の抽出した目的部分領域特徴の集合から、類似する蓄積部分領域特徴の抽出を行う。
【００１２】
特徴照合部７は、上記索引検索部６の抽出した蓄積部分領域特徴と、目的部分領域特徴抽出部５の抽出した目的部分領域特徴との距離を計算する。
この距離は、ユークリッド距離，マンハッタン距離，内積，正規化相互相関などを用いることが出来る。
照合結果判定部８は、上記特徴照合部７の演算した距離に基づいて、目的画像と類似する部分画像が蓄積画像群中の当該箇所に存在する可能性があるか否かの判定を行う。
【００１３】
特徴再照合部９は、上記照合結果判定部８が目的画像と類似する部分蓄像が存在する可能性があると判定した場合、判定された蓄積画像における箇所において、蓄積特徴抽出部１の抽出した蓄積特徴に対し、目的画像と同じ大きさの照合窓を設定して、目的特徴抽出部４から出力された目的特徴との特徴距離を計算する。この特徴距離も上記距離と同様に各種の定義を用いることができる。
照合結果再判定部１０は、上記照合結果判定部８において用いられた距離に基づいて、目的画像と類似する部分画像が、蓄積画像群中の当該箇所に存在するか否かの判定を行う。
【００１４】
検索結果候補選択部１１は、上記照合結果再判定部１０において目的画像と類似する部分画像が存在すると判定された蓄積画像中の箇所を、詳細な類似性の検討を行う検索結果候補とする。
次目的部分領域特徴選定部１２は、上記目的部分領域特徴抽出部５において抽出された目的部分領域特徴の集合の中から、次に照合すべき目的部分領域特徴の指定を行う。
次検索候補特徴選定部１３は、上記索引検索部６から検索結果として出力された蓄積部分領域特徴の集合の中から、次に照合すべき蓄積部分領域の指定を行う。
【００１５】
次に、図１及び図２を参照して、上述した部分画像検索装置の動作を説明する。図２は、図１の第１の実施例による部分画像検索装置の一動作例を具体的に示すフローチャートである。
蓄積特徴抽出部１は、初めに、蓄積画像群を、図示しないデータベースから読み込む（ステップＳ１）。
次に、蓄積特徴抽出部１は、入力した蓄積画像群の各画像から、画像の特徴である蓄積特徴を抽出する（ステップＳ２）。
【００１６】
例えば、ＲＧＢ画素値をそのまま用いて、蓄積画像の大きさが「３８４×２５６」ピクセルであるとすると、「３８４×２５６×３＝２９４９１２」個の数値で構成される蓄積特徴（多次元ベクトルからなる特徴ベクトル）が各蓄積画像ごとに、すなわち、１画像あたり１つ得られる。ここで、上記「３８４×２５６」に乗ぜられている「３」はＲＧＢの色数である。
【００１７】
また、他の実施例として、例えば、画像から８×８ピクセル程度の大きさの小領域（ブロック）を用い、縦及び横方向に順次１ピクセルずつ、この小領域をずらしながら、各小領域の範囲内での蓄積特徴を抽出し、各小領域のＲＧＢ各々の平均値を計算することにより得ることができる。
すなわち、蓄積画像の大きさが「３８４×２５６」ピクセルであるとすると、「(３８４−８＋１)×(２５６−８＋１)×３＝２８１６１９」個の数値で構成される特徴が、各蓄積画像ごとに、すなわち、１画像あたり１つ得られる。
【００１８】
さらに、他の実施例として、例えば、蓄積画像から８×８ピクセル程度の大きさの小領域を、縦及び横方向に１ピクセルずつずらしながら、各小領域に含まれるピクセルのＲＧＢ各々に対して、２次元ＤＣＴ(デジタルコサイン変換)を行い、その係数ベクトルを蓄積特徴とすることもできる。
すなわち、蓄積画像の大きさが「３８４×２５６」ピクセルであるとすると、８×８×３＝１９２次元の特徴ベクトルが、１画像あたりに、「(３８４−８＋１)×(２５６−８＋１)＝９３８７３」個、算出される。
この場合、蓄積特徴抽出部１は、蓄積画像から抽出された特徴である蓄積特徴の集合を出力することになる。
【００１９】
次に、蓄積部分領域特徴抽出部２は、蓄積特徴抽出部１から、蓄積特徴の集合を読み込み、蓄積画像のある１つの箇所に、予め定められた所定の大きさの第１注目窓を設定する。
例えば、この第１注目窓は、大きさが６４×６４ピクセルであり、初期状態として蓄積画像の左上の角に配置される。。
そして、蓄積部分領域特徴抽出部２は、設定された上記第１注目窓内に含まれる部分領域の画像の特徴である蓄積部分領域特徴を抽出する。
例えば、この蓄積部分領域特徴各々は、ＲＧＢ画素値をそのまま用いて、「６４×６４×３＝１２２８８次元の特徴ベクトルを１つ得ることになる。
【００２０】
また、他の実施形態においては、例えば、蓄積部分領域特徴として、小領域内のＲＧＢ面素値の平均を演算し、得られた平均値を用い、上記第１注目窓内に、重複することも隙間もな存在しない状態に、上記小領域を配置して、この各小領域に対応する特徴を抽出して、「(６４／８)×(６４／８)×３＝１９２」次元の特徴のベクトルを１つ得るようにすることも可能である。
さらに、他の実施形態においては、例えば、蓄積部分領域特徴として、小領域内の２次元ＤＣＴ係数ベクトルを用い、上記第１注目窓内に重複することも隙問も存在しない状態に、上記小領域を配置して、この各小領域に対応する特徴を抽出し、「８×８×３＝１９２」次元の特徴ベクトルを、「(６４／８)×(６４／８)＝６４」個、もしくは、全ての次元の特徴ベクトルを１つにまとめて、「１９２×６４＝１２２８８」次元の特徴ベクトルを１つ得ることもできる。
【００２１】
第１注目窓は、各蓄積画像内において、予め定められた所定の間隔により、複数設定され、各注目窓内の部分領域から蓄積部分領域特徴を抽出する（ステップＳ３）。
すなわち、第１注目窓（横ωxピクセル×縦ωyピクセル）は、各蓄積画像内において、縦及び横方向に、上記所定の間隔（各注目窓の同一の辺同士の間隔であり、例えば左辺同士、上辺同士の間隔として、横方向にｍxピクセル，縦方向にｍyピクセル）で順次ずらして配置されており、各々が重なり合う状態となっており、連続する第１の窓同士は、図３に示すように、所定の間隔を除いて重なることとなる。
【００２２】
例えば、第１注目窓を縦横それぞれ１６ピクセルの間隔で配置し、蓄積画像の大きさが「３８４×２５６」ピクセルであるとすると、第１注目窓が「６４×６４」ピクセルであるために１画像あたり、「２１×１３＝２７３」個の第１注目窓が設定されることになる。
また、第１注目窓の配置問隔を、以下マージンと呼ぶことにする。このマージンは、例えば、第１注目窓の大きさ以下に設定すると、必ず第１注目窓が重なって配置されることになり、検索漏れを生じることがなくなる。
そして、蓄積部分領域特徴抽出部２は、上記第１注目窓毎に得られた蓄積部分領域特徴の集合を出力する。
【００２３】
次に、索引付与部３は、蓄積部分領域特徴抽出部２の抽出した蓄積部分領域特徴の集合を読み込み、この読み込んだ各部分領域特徴に対して、検索を容易にするための索引を付与する。
例えば、「信号検出方法、信号検出装置、記録媒体及びプログラム」(特開２００２−２３６４９６)記載の実施例のように、予め作成されたベクトル量子化符号帳を用いて、各部分領域画像の特徴ベクトルをベクトル量子化し、ベクトル量子化の符号語を索引とする。
【００２４】
すなわち、上記方法について簡単に説明すると、はじめに、索引付与部３は、蓄積部分領域特徴の集合を読み込む。
次に、索引付与部３は、各蓄積部分領域特徴のクラスタリングを行う。このクラスタリングは、例えば、各蓄積部分領域特徴をベクトルと考えて、そのベクトルを、ベクトル量子化を用いて符号化することによって行う。
例えば、ベクトル量子化の符号語数が１０２４個であれば、部分領域特徴は１０２４個のクラスタのいずれかに分類されることになる。
【００２５】
ここで、ベクトル量子化は、例えば、自乗誤差を距離関数として用い、クラスタ重心との距離が他のどのクラスタ重心との距離よりも小さくなるクラスタに部分領域特徴を所属させ、クラスタに対応する符号語を出力することによって行われる。
このクラスタは、例えば、クラスタ作成のために予め用意された、部分領域特徴と同じ次元数の特徴である学習特徴を用いて予め作成しておく。
すなわち、クラスタは、それに所属する学習特徴とクラスタ重心との距離の総和が最小になるように、かつそのクラスタに所属する学習特徴について、所属するクラスタのクラスタ重心との距離が、他のどのクラスタ重心との距離よりも小さくなるように構成される。
そして、索引付与部３は、索引として、各部分領域特徴に対応する、ベクトル量子化の符号語を出力する（ステップＳ４）。
【００２６】
また、別の実施形態として、例えば、Ｒ＊-Ｔｒｅｅ（「The R＊-Tree: an efficient and rbust 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に対応するクラスタに所属する蓄積部分領域特徴の中に、所望の蓄積部分領域特徴が含まれている可能性がある。
そこで、選択閾値θ２が図４におけるｄθより大きくなったとき、そのクラスタを選択する。ｄθは、以下の（１）式，（２）式を用いて求められる。
【００３７】
【数１】
2005352990.tif 000003
【００３８】
上記（１）式より、
【００３９】
【数２】
2005352990.tif 000004
【００４０】
が求められる。
最終的に、索引検索部６は、以下の（３）式が成り立つとき、点Ｃ2に対応するクラスタを選択し、そのクラスタに所属する蓄積部分領域特徴を全て抽出する。
そして、この手順を、目的部分領域特徴Ｑが所属するクラスタを除く全てのクラスタに対して行い、抽出された蓄積部分領域特徴を、検索候補特徴として出力する。
【００４１】
【数３】
2005352990.tif 000005
【００４２】
次に、特徴照合部７は、目的部分領域特徴抽出部５から出力される目的部分領域特徴の集合と、索引検索部６から出力される検索候補特徴の集合を読み込む。
そして、特徴照合部７は、次目的部分領域特徴選定部１２により、次に照合すべき目的部分領域特徴が指定されている場合、該目的部分領域特徴を読み込む。この次目的部分領域特徴選定部１２は、本実施形態において後述する。
【００４３】
また、特徴照合部７は、次検索候補特徴選定部１３から、次に照合すべき検索候補特徴が指定されている場合、該検索候補特徴を読み込む。この次検索候補特徴選定部１３は、本実施形態において後述する。
次に、特徴照合部７は、次目的部分領域特徴選定部１２から読み込んだ目的部分領域特徴と、次検索候補特徴選定部１３から読み込んだ検索候補特徴の集合との照合を行う。
このとき、特徴照合部７は、上記目的部分領域特徴と検索候補特徴との距離、例えば、自乗誤差の演算を行う。
【００４４】
ここで、特徴照合部７は、指定された目的部分領域特徴がなければ、初期目的部分領域特徴として、例えば、目的画像の左上角の位置に対応する目的部分領域特徴を指定し、上記検索候補特徴と照合処理を行う（ステップＳ９）。
また、特徴照合部７は、指定された検索候補特徴がなければ、初期の検索候補特徴として、例えば、任意に選択した検索候補特徴を指定し、上記目的部分領域特徴と照合する。
そして、特徴照合部７は、照合計算（検索候補特徴と目的部分領域特徴との間の距離の演算）の結果として、照合した検索候補特徴と目的部分領域特徴との距離値ｄ(ω)を出力する。
【００４５】
次に、照合結果判定部１２は、特徴照合部７から出力される距離値ｄ(ω)を読み込み、目的画像と類似する部分画像が、現在の照合箇所に存在する可能性があるか否かの判定、すなわち、該距離値ｄ(ω)と、前記選択閾値θ２との比較を行う。
そして、照合結果判定部８は、距離値ｄ(ω)が選択閾値θ２を以下となったとき、目的画像と類似する部分画像が現在の照合箇所に存在する可能性があると判定し、蓄積部分領域特徴を照合箇所として出力し、一方、距離値ｄ(ω)が選択閾値θ２を超えているとき、目的画像と類似する部分画像が現在の照合箇所に存在する可能性がないと判定し、処理をステップＳ１４へ進める（ステップＳ１０）。
【００４６】
次に、特徴再照合部９は、蓄積特徴抽出部１から出力される蓄積特徴の集合と、目的特徴抽出部４から出力される目的特徴の集合と、照合結果判定部８から出力される照合箇所とを読み込む。
そして、特徴再照合部９は、読み込んだ蓄積特徴に、目的画像と同じ大きさ（縦×横）の注目窓である第２注目窓を設定する。
【００４７】
ここで、特徴再照合部９は、第２注目窓の配置箇所を、照合結果判定部８から出力された照合箇所に対応して決定する。
すなわち、特徴再照合部９は、図５の概念図に示すように、第２注目窓の配置箇所に対する蓄積部分領域の相対的な位置が、目的画像における目的部分領域の相対的な位置と同一になるように、つまり、照合箇所における蓄積部分領域と目的部分領域とが重なる位置に、上記第２注目窓を配置する。
【００４８】
次に、特徴再照合部９は、第２注目窓内における蓄積特徴と目的特徴との照合を行う。
ここで、特徴再照合部９は、例えば、第２注目窓内の蓄積特徴と目的特徴との距離値ｄ、例えば、自乗誤差を計算する。
そして、特徴再照合部９は、照合計算結果である距離値ｄを出力する（ステップＳ１１）。
【００４９】
次に、照合結果再判定部１４は、特徴再照合部１３から出力される距離値ｄを読み込み、目的画像と類似する部分画像が現在の照合箇所に存在する可能性があるか否かの判定、すなわち、該距離値ｄと、前記予め定められた閾値である検索閾値θとの比較を行う。
このとき、照合結果再判定部１０は、距離値ｄが検索閾値θ以下であるとき、目的画像と類似する部分画像が現在の照合箇所に存在すると判定し、蓄積画像における該照合箇所を検出箇所として、この検出箇所の位置及び判定結果（存在したことを示す情報）を出力し、一方、距離値ｄが検索閾値θを超えたとき、目的画像と類似する部分画像が現在の照合箇所に存在しないと判定し、処理をステップＳ１４へ進める（ステップＳ１２）。
【００５０】
上記選択閾値θ２は、前記検索閾値θから決定され、以下に示す（４）式に示すように、選択閾値θ２を設定すると、検索漏れを生じることがない。
【００５１】
【数４】
2005352990.tif 000006
【００５２】
上記（４）式において、Ｎは第１注目窓を重複も隙問もなく蓄積画像中に配置したと仮定したとき、任意位置に配置された第２照合窓に含まれる第１照合窓の最小数であり、以下に示す（５）〜（７）式により与えられる。
【００５３】
【数５】
2005352990.tif 000007
【００５４】
【数６】
2005352990.tif 000008
【００５５】
【数７】
2005352990.tif 000009
【００５６】
ここで、（６）式におけるＮxは横方向の第１の照合窓の数であり、（７）式におけるＮyは縦方向の第１の照合窓の数である。
ただし、（ｑx、ｑy）は目的画像の大きさ、すなわち、第２注目窓の大きさであり、（ωx，ωy）は第１注目窓の大きさである。
次に、検索結果候補選択部１１は、照合結果再判定部１０から出力される検出箇所と、特徴再照合部９から出力される距離値ｄを読み込む。
【００５７】
次に、検索結果候補選択部１１は、上記検出箇所と、この検出箇所における距離値ｄとを、検索結果候補として登録する。
検索結果候補選択部１１は、例えば、距離値の大小にかかわらず、読み込んだ検出箇所と距離値ｄとの組を全て登録する。
また、検索結果候補選択部１１は、他の実施形態として、検索結果候補が予め定められた数量以下になるように登録する構成とすることも可能である。
【００５８】
すなわち、検索結果候補選択部１１は、検索結果候補を該数量までは無条件に検出箇所と距離値との組を登録し、該数量を超過する場合、例えば、すでに読み込まれた検索結果候補の中における最大距離値ｄmaxと、以降読み込んだ距離値ｄとを比較し、読み込んだ距離値ｄが最大距離値ｄmaxを下回る場合、最大距離値ｄmaxに対応する候補を削除し、新たに読み込んだ検出箇所と距離値ｄの組とを候補として登録する。
このように、検索結果候補選択部１１は、蓄積画像から上述した方法により検索結果候補を出力する（ステップＳ１３）。
【００５９】
次に、次目的部分領域特徴選定部１２は、目的部分領域特徴抽出部５から出力される目的部分領域特徴の集合を読み込み、必要に応じて、特徴照合部７から出力される距離値ｄ(ω)，検索閾値更新部１４から出力される選択閾値θ２，及び周辺距離下限値計算部１７から出力される周辺距離下限値を読み込む。
上記検索閾値更新部１４及び周辺距離下限値計算部１７は、他の実施例において後述する。
そして、次目的部分領域特徴選定部１２は、次に照合する目的部分領域特徴の有無の検出を行い、照合箇所がないことを検出すると処理をステップＳ１５へ進め、一方、照合箇所があることを検出すると、次に照合する目的部分領域特徴を選択して、処理をステップＳ９へ進める（ステップＳ１４）。
【００６０】
このとき、次目的部分領域特徴選定部１２は、例えば、現在注目している蓄積部分領域特徴に対して、照合が終了していない目的部分領域特徴があるか否かを判定して、終了していない目的部分領域特徴があれば、この中から任意の目的部分領域特徴を１つ選択し、全ての目的部分領域特徴の照合が終了している場合、次の、蓄積部分領域特徴に注目を変更するため、処理をステップＳ１５へ進める。
また、別の実施形態として、次目的部分領域特徴選定部１２は、上記周辺距離下限値を読み込んだ場合、この距離下限値が、読み込んだ選択閾値θ２上回る目的部分領域特徴との照合を省略し、この距離下限値が選択閾値θ２以下の目的部分領域特徴から任意に１つ選択する構成とすることも可能である。
そして、次目的部分領域特徴選定部１２は、終了していない目的部分領域特徴があれば、照合箇所が選択された目的部分領域特徴と、この目的部分特徴に対応する目的画像内の位置を出力する。
【００６１】
次に、次検索候補特徴選定部１３は、索引検索部６から出力される検索候補特徴の集合を読み込み、次に照合すべき検索候補特徴を選択、すなわち次に照合する検索候補特徴の有無の検出を行い、照合する検索候補特徴がないことを検出すると処理を終了させ、一方、照合する検索候補特徴があることを検出すると、次に照合すべき検索候補特徴を選択して、処理をステップＳ９へ進める（ステップＳ１５）。
このとき、次検索候補特徴選定部１３は、例えば、照合する検索候補特徴があることを検出すると、照合が終了していない検索候補特徴から任意に１つ選択する。
これにより、次検索候補特徴選定部１３は、選択された検索候補特徴を、特徴照合部７に対して出力する。
【００６２】
＜第２の実施例＞（請求項３に対応）
図６は、請求項３に記載の方法を適用した第２の実施例による部分画像検索装置の構成例を示すブロック図である。
第２の実施例の部分画像検索装置は、請求項１に記載の方法を適用した第１の実施例による部分画像検索装置に加え、さらに、図６に示すように、検索閾値更新部１４を設け、任意の目的画像、すなわち見本となる検索したい画像と、蓄積画像群、すなわち検索される複数の画像である蓄積画像の集合を入力とし、目的画像と類似する画像が含まれている部分画像の蓄積画像内における箇所を出力する。
【００６３】
上記検索閾値更新部１４は、上記検索結果候補選択部１１から出力された検索結果候補から、上記特徴再照合部９から出力された距離値に基づいて、所定の距離内にある候補を検出し、この検出した候補の距離値に基づいて新たに検索閾値θを設定する。
次に、上述した蓄積特徴抽出部１から検索閾値更新部１４における部分画像の検出処理を、図７を用いて具体的に説明する。ここで、図７は、図６に示す部分画像検索装置の動作例を示すフローチャートである。
【００６４】
図７のフローチャートは、図２に示す第１の実施例のフローチャートに対して、ステップＳ１３の「検索結果の候補選択」の処理の次に、ステップＳ１６の「検索閾値更新」の処理が追加されたのみで、他の処理については同様であるため、このステップＳ１６の処理の説明のみを行う。
検索閾値更新部１４は、検索結果候補選択部１１から出力される検索結果候補を読み込み、この読み込んだ検索結果候補の中から、距離値が最大の検索結果候補を選び出し、選択した検索結果候補の距離値が検索閾値θ以下であるか否かの判定を行い、この距離値が探索結果閾値θ以下であることを検出した場合、検索閾値θをその距離値と同じ値に更新する。
そして、（４）式に基づいて検索閾値θから選択閾値θ２を計算し、更新した検索閾値θと共に出力する（ステップＳ１４）。
これ以降は、この更新された検索閾値θ及び選択閾値θ２が照合結果の判定に用いられる。
【００６５】
＜第３の実施例＞（請求項５に対応）
図８は、請求項５に記載の方法を適用した第３の実施例による部分画像検索装置の構成例を示すブロック図である。
この第３の実施例による部分画像検索装置は、第１及び第２の実施例の部分画像検索装置に対して、目的代表特徴抽出部１５を加えたものであり、目的画像、すなわち見本となる検索したい画像と、蓄積画像群、すなわち検索される画像である蓄積画像の集合とを入力し、目的画像と類似する画像が含まれてた部分画像の、上記蓄積画像内における箇所を検索し、検索結果を出力する。
この目的代表特徴抽出部１５は、上記目的部分領域特徴抽出部５から出力された目的部分領域特徴の集合の中から、各目的部分領域特徴に共通する特徴としての目的代表特徴を抽出する。
【００６６】
次に、上述した蓄積特徴抽出部１から目的代表特徴抽出部１５における部分画像の検出処理を、図９を用いて具体的に説明する。ここで、図９は、図８に示す部分画像検索装置の動作例を示すフローチャートである。
図９のフローチャートは、図７に示す第２の実施例のフローチャートに対して、ステップＳ７の「目的部分領域の抽出」の処理の次に、ステップＳ１７の「目的代表特徴の抽出」の処理が追加されたのみで、他の処理については同様であるため、このステップＳ１７の処理の説明のみを行う。
【００６７】
目的代表特徴抽出部１５は、目的部分領域特徴抽出部５から出力される目的部分領域特徴の集合を読み込み、これら複数の目的部分領域特徴に対してクラスタリング処理を行う。
このとき、目的代表特徴抽出部１５は、例えば、クラスタを１つだけ用意し（共通の特徴ベクトルを抽出する）、上記集合における全ての目的部分領域特徴をそのクラスタに所属させる（１つの目的代表特徴を出力することになる）。
【００６８】
さらに、目的代表特徴抽出部１５は、別の実施例として、目的部分領域特徴に対応する目的画像中の位置を、読み込んだ全ての目的部分領域特徴について抽出し、その存在範囲を格子状に区切り、各格子をクラスタと対応させる構成とすることも可能である。
また、さらに、目的代表特徴抽出部１５は、別の実施例として、同一クラスタ内の目的部分領域特徴同士の距離の最大値が、予め定められた閾値である分類閾値を上回らないように、クラスタを併合することも可能である。
【００６９】
このとき、目的代表特徴抽出部１５は、クラスタの初期状態として、例えば、読み込んだ目的部分領域特徴の数だけ用意したクラスタに１つずつ目的部分領域を割り当てたものを用いる。
次に、目的代表特徴抽出部１５は、上記各クラスタから、該クラスタを代表する部分領域特徴である代表特徴を抽出する。目的代表特徴抽出部１５は、例えば、クラスタ内の任意に選択した１つの目的部分領域特徴を代表特徴とする。
【００７０】
また、目的代表特徴抽出部１５は、別の実施例として、ある特定位置に対応する目的部分領域特徴を代表特徴とすることもできる。
この特定位置とは、例えば、目的画像の左上角の位置などである。
さらに、目的代表特徴抽出部１５は、別の実施例として、クラスタ内の目的部分領域特徴の重心にある目的部分特徴を代表特徴とする構成とすることもできる。
そして、目的代表特徴抽出部１５は、上述した第３の実施例における各実施例により求めた、代表特徴あるいはその集合を出力する。
次のステップＳ８において、索引検索部６は、上記目的代表特徴を用いて、蓄積画像の索引との照合処理を行う。
【００７１】
＜第４の実施例＞（請求項７に対応）
図１０は、請求項６に記載の方法を適用した第４の実施例による部分画像検索装置の構成例を示すブロック図である。
この第４の実施例による部分画像検索装置は、第１、第２、第３の実施例の部分画像検索装置に対して、目的部分領域間距離計算部１６と、周辺距離下限値計算部１７とを加えたものであり、目的画像、すなわち見本となる検索したい画像と、蓄積画像群、すなわち検索される画像である蓄積画像の集合とを入力し、目的画像と類似する画像が含まれてた部分画像の、上記蓄積画像内における箇所を検索し、検索結果を出力する。
【００７２】
上記目的部分領域間距離計算部１６は、上記目的部分領域特徴抽出部５から出力された目的部分領域特徴について、部分領域特徴同士の距離を計算する。
そして、目的代表特徴抽出部１５が設けられている場合は、目的部分領域特徴と、それに対応する目的代表特徴との距離を計算する。
上記周辺距離下限値計算部１７は、特徴照合部７から出力された距離値と、目的部分領域間距離計算部１６から出力された距離値とを用い、特徴照合部７で照合を行った検索候補特徴と、上記目的部分領域特徴抽出部５から出力された各目的部分領域特徴との距離を演算して、この演算結果から下限値を抽出する。
【００７３】
次に、上述した蓄積特徴抽出部１から周辺距離下限値計算部１７における部分画像の検出処理を、図１１を用いて具体的に説明する。ここで、図１１は、図１０に示す部分画像検索装置の動作例を示すフローチャートである。
図１１のフローチャートは、図９に示す第３の実施例のフローチャートに対して、ステップＳ１７の「目的代表特徴の抽出」の処理の次に、ステップＳ１８の「目的部分領域間距離の演算」の処理が追加され、また、ステップＳ１６の「検索閾値の更新」の処理の次に、ステップＳ１９の「周辺距離下限値の演算」の処理が追加されたのみで、他の処理については同様であるため、このステップＳ１８及びステップＳ１９の処理の説明のみを行う。
【００７４】
目的部分領域間距離計算部１６は、目的部分領域特徴抽出部５から出力される目的部分領域特徴の集合を読み込み、各目的部分領域特徴同士の距離を計算する。
そして、目的部分領域間距離計算部１６は、例えば、全ての目的部分領域特徴の組に対して距離計算を行う。ここで、距離尺度としては、例えば、自乗誤差を用いる。
また、別の実施例として、目的代表特徴抽出部１５が設けられている場合には、さらにこの目的代表特徴抽出部１５から出力される目的代表特徴の集合を読み込み、各目的部分領域特徴と、それに対応する目的部分領域特徴との距離を計算することも可能である。
上述したように、目的部分領域間距離計算部１６は、目的部分領域特徴同士の距離、あるいは目的部分領域特徴と目的代表特徴との距離を出力する。
上述した距離を用いて、ステップＳ８において、索引による検索が行われる。
【００７５】
次に、周辺距離下限値計算部１７は、特徴照合部７から出力される距離値と、目的部分領域間距離計算部１６から出力される部分領域間距離とを読み込む。
そして、周辺距離下限値計算部１７は、読み込んだ距離値と部分領域問距離とから、蓄積部分領域特徴と各目的部分領域特徴との距離下限値を計算する。
このとき、周辺距離下限値計算部１７は、蓄積部分領域特徴ｆＤ（Ｗ）と、目的部分領域特徴ｆＱ２（Ｗ）との距離の下限値ｄ(ｆＤ（Ｗ），ｆＱ２（Ｗ）)は、三角不等式に基づいて、以下の（８）式により求められる。，
【００７６】
【数８】
2005352990.tif 000010
【００７７】
上記（８）式において、ｄ(ｆＤ（Ｗ），ｆＱ１（Ｗ）)は特徴照合部７から読み込んだ距離値であり、ｄ(ｆＱ１（Ｗ），ｆＱ２（Ｗ）)は読み込んだ目的部分領域間距離である。
上述したように、周辺距離下限値計算部１７は、蓄積部分領域特徴と、目的部分領域特徴との距離の下限値である周辺距離下限値を出力する。
そして、次のステップＳ１４において、次目的部分領域特徴選定部１２は、上記周辺距離下限値を入力し、この距離下限値が、読み込んだ選択閾値θ２を上回る目的部分領域特徴との照合を省略し、この距離下限値が選択閾値θ２以下の目的部分領域特徴から任意に１つ選択する。
【００７８】
＜実験＞
本発明を適用した装置の動作例を以下に示す。
ここで、蓄積画像群として、大きさ384 × 256 ピクセルの画像１０００枚を用い、目的画像として、大きさ８０×８０ピクセルの画像１０枚を、上記蓄積画像群中の任意の箇所から切り出して用いた。
また、部分領域は大きさを６４×６４ピクセルとし、マージンを縦方向及び横方向共に１６ピクセルと設定して、部分画像の切り出しを行った。
すなわち、蓄積画像１枚あたりの部分領域の数は２７３個であり、目的画像の部分領域の数は２５６個である。
【００７９】
画像の特徴としては、大きさ８×８ピクセルの小領域におけるＲＧＢの平均値を用いたため、部分領域特徴の次元は１９２次元となっている。
索引付与部３及び索引検索部６は、「信号検出方法、信号検出装置、記録媒体及びプログラム」（特開2002-236496)記載の実施例のように、ベクトル量子化に基づく索引付与と索引検索と実施し、クラスタ数を１０２４とした。
また、距離尺度は自乗誤差を用い、検索閾値は１０００とした。
【００８０】
本発明の効果を確認するため、まず、マージンを変化させたときの、索引保持に必要な記憶容量の変化を検討した。
マージンは縦方向及び横方向共に同じ値とした。
本実験の結果を図１２に示す。この図において、グラフの横軸はマージンを表し、グラフの縦軸は索引付与に必要な記憶容量をバイト単位で示している。
上記図１２からわかるように、マージンの増加にともなって、索引付与に必要な記憶容量が大幅に削減されている。
【００８１】
例えば、マージンが１６のとき、記憶容量は２.０５メガバイトであり、マージンが１のとき、すなわち、あらゆる全ての部分領域に索引を付与するときに１２４メガバイトであり、マージンを１６取った場合が１である場合に比べて、記憶容量が約１／６０にまで削減されている。
【００８２】
次に、マージンを変化させたときにおける、検索所要時間（実線）の変化を検討した。
マージンは上述した実験と同様に縦方向及び横方向共に同じ値とした。
本実験の結果を図１３に示す。この図において、グラフの横軸はマージンを表し、グラフの縦軸は検索所要時間を秒単位で示している。
上記図１３からわかるように、マージンが１２のときに最も検索所要時間が短くなり、５.１２秒であり、マージンが１のとき１０.４９秒であり、もっとも検索時間が長くなった。この図において、破線は検索所要時間に含まれる検索を行う前の前処理の時間を示している。
【００８３】
なお、図１，６，８，１０における部分画像検索装置の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、部分画像の検索処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００８４】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００８５】
【図１】本発明の第１の実施例による部分画像検索装置の構成例を示すブロック図である。
【図２】図１の部分画像検索装置の動作例を示すフローチャートである。
【図３】蓄積画像において部分画像を設定する際に、配置のマージンについて説明する概念図である。
【図４】索引検索部６がクラスタを選択するときの原理を説明する概念図である。
【図５】蓄積画像における照合窓の設定を説明する概念図である。
【図６】本発明の第２の実施例による部分画像検索装置の構成例を示すブロック図である。
【図７】図６の部分画像検索装置の動作例を示すフローチャートである。
【図８】本発明の第３の実施例による部分画像検索装置の構成例を示すブロック図である。
【図９】図８の部分画像検索装置の動作例を示すフローチャートである。
【図１０】本発明の第４の実施例による部分画像検索装置の構成例を示すブロック図である。
【図１１】図１０の部分画像検索装置の動作例を示すフローチャートである。
【図１２】画像を検索する際の、部分領域を設定する場合のマージンと、索引付与に必要な記憶容量のバイト数との関係を示すグラフである。
【図１３】画像を検索する際の、部分領域を設定する場合のマージンと、検索所要時間との関係を示すグラフである。
【符号の説明】
【００８６】
１…蓄積特徴抽出部        ２…蓄積部分領域特徴抽出部  ３…索引付与部
４…目的特徴抽出部        ５…目的部分領域特徴抽出部  ６…索引検索部
７…特徴照合部            ８…照合結果判定部          ９…特徴再照合部
１０…照合結果再判定部      １１…検索結果候補選択部
１２…次目的部分領域特徴選定部      １３…次検索候補特徴選定部
１４…検索閾値更新部                １５…目的代表特徴抽出部
１６…目的部分領域間距離計算部      １７…周辺距離下限値計算部
【図１】
2005352990.tif 000011
【図２】
2005352990.tif 000012
【図３】
2005352990.tif 000013
【図４】
2005352990.tif 000014
【図５】
2005352990.tif 000015
【図６】
2005352990.tif 000016
【図７】
2005352990.tif 000017
【図８】
2005352990.tif 000018
【図９】
2005352990.tif 000019
【図１０】
2005352990.tif 000020
【図１１】
2005352990.tif 000021
【図１２】
2005352990.tif 000022
【図１３】
2005352990.tif 000023