(57)【特許請求の範囲】
【請求項１】
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与し、付与されたラベルを所定のブロック順序で並べることによりラベル行列を生成する第１生成手段と、
前記第１生成手段で生成されたラベル行列を前記画像データに対応付けて記憶する記憶手段と、
前記生成されたラベル行列より部分ラベル行列を抽出し、抽出された部分ラベル行列をキーとして画像データを検索可能なテーブルを保持する保持手段と、
検索元の画像データから部分ラベル行列を抽出し、前記テーブルを用いて類似画像を検索する第１検索手段と、
前記第１検索手段で検索された各類似画像を比較先画像として、前記記憶手段から得られた比較先画像のラベル行列と、前記検索元の画像データから得られるラベル行列との間でラベル間距離に基づくマッチング処理を行って類似度を獲得し、獲得した類似度に基づいて検索結果を得る第２検索手段と、
画像の一部を構成する部分画像が検索元の画像として指定された場合、該部分画像を表す部分画像データが含まれるブロックに関して前記特徴量に応じたラベルを付与し、他のブロックに関してはラベルとの間の距離がゼロであることを示すラベルを付与することで検索元の画像のラベル行列を生成する第２生成手段と、
前記部分画像の画像データが含まれるブロックに関して付与されたラベルに基づいて部分ラベル行列を生成する第３生成手段とを備え、
前記第１及び第２検索手段は、前記第２生成手段及び前記第３生成手段によって生成されたラベル行列と部分ラベル行列を用いて画像の検索を行うことを特徴とする画像検索装置。
【請求項２】
前記テーブルには、各部分ラベル行列をキーとして、当該部分ラベル行列を含む画像データの識別子と各画像データによる当該部分ラベル行列の含有数が登録されることを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記ラベルは、多次元特徴量空間を複数のセルに分割して得られたセルの夫々に与えられる固有のラベルであり、前記生成手段は、前記ブロックの夫々について特徴量を算出し、算出された特徴量が属するセルに付与されているラベルを当該ブロックに付与することを特徴とする請求項１に記載の画像検索装置。
【請求項４】
画像中の所望の部分画像を指定する指定手段と、
前記指定手段で指定された部分画像に対応する部分画像データを抽出してこれを前記第２生成手段に提供する抽出手段とを更に備えることを特徴とする請求項１に記載の画像検索装置。
【請求項５】
所望の着目物体を表す画像データを指定する指定手段と、
前記指定手段で指定された画像データを所定の背景を有する画像に合成して検索元の画像を生成し、これを前記第２生成手段に提供する合成手段とを更に備えることを特徴とする請求項１に記載の画像検索装置。
【請求項６】
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与し、付与されたラベルを所定のブロック順序で並べることによりラベル行列を生成する第１生成手段と、
前記第１生成手段で生成されたラベル行列を前記画像データに対応付けて記憶する記憶手段と、
前記生成されたラベル行列より部分ラベル行列を抽出し、抽出された部分ラベル行列をキーとして画像データを検索可能なテーブルを保持する保持手段と、
検索元の画像データから部分ラベル行列を抽出し、前記テーブルを用いて類似画像を検索する第１検索手段と、
前記第１検索手段で検索された各類似画像を比較先画像として、前記記憶手段から得られた比較先画像のラベル行列と、前記検索元の画像データから得られるラベル行列との間でラベル間距離に基づくマッチング処理を行って類似度を獲得し、獲得した類似度に基づいて検索結果を得る第２検索手段とを備え、
前記ラベル行列は２次元のラベル行列を表し、
前記第２検索手段が、
前記検索元の画像データのラベル行列より抽出される行単位のラベル列と、前記第１検索手段で得られた比較先画像データのラベル行列より抽出される行単位のラベル列とをＤＰマッチングによって対応づけることによって該比較先画像データの行並びを得る第１マッチング手段と、
前記元画像データのラベル行列の行並びと、前記第１マッチング手段で得られた行並びとの類似度をＤＰマッチングによって求める第２マッチング手段とを含むことを特徴とする画像検索装置。
【請求項７】
前記第１マッチング手段は、各ラベルのペアについてペナルティ値を保持するペナルティテーブルを有し、前記検索元画像のラベル列と前記比較先画像のラベル列との距離をＤＰマッチング手法を用いて算出するに際して該ペナルティテーブルを参照する
ことを特徴とする請求項６に記載の画像検索装置。
【請求項８】
前記第２マッチング手段は、行並びにおける各行番号のペアについてペナルティ値を保持する行間ペナルティテーブルを有し、前記検索元画像の行並びと前記比較先画像の行並びの類似度をＤＰマッチング手法を用いて算出するに際して、該行間ペナルティテーブルを参照する
ことを特徴とする請求項６に記載の画像検索装置。
【請求項９】
前記元画像データの行方向の各ラベル列の類似度に基づいて各行のペアに関するペナルティー値を決定し、これを前記行間ペナルティテーブルとして保持する保持手段を更に備える
ことを特徴とする請求項８に記載の画像検索装置。
【請求項１０】
前記第１マッチング手段で使用するＤＰマッチングの整合窓の幅を設定する第１設定手段を更に備える
ことを特徴とする請求項６に記載の画像検索装置。
【請求項１１】
前記第２マッチング手段で使用するＤＰマッチングの整合窓の幅を設定する第２設定手段を更に備える
ことを特徴とする請求項６に記載の画像検索装置。
【請求項１２】
前記第１検索手段は、検索元の画像データから、前記保持手段と同じ手法を用いて部分ラベル行列を抽出し、該部分ラベル行列を所定の含有数の範囲で含む画像を前記テーブルを用いて検索する
ことを特徴とする請求項１乃至１１のいずれか１項に記載の画像検索装置。
【請求項１３】
前記含有数の範囲を、前記検索元の画像データから抽出された部分ラベル行列の、該検索元の画像データが含む個数に基づいて設定する設定手段を更に備える
ことを特徴とする請求項１２に記載の画像検索装置。
【請求項１４】
前記設定手段は、前記検索元の画像データが含む個数と指定された曖昧度に基づいて前記含有数の範囲を決定する
ことを特徴とする請求項１３に記載の画像検索装置。
【請求項１５】
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与し、付与されたラベルを所定のブロック順序で並べることによりラベル行列を生成する第１生成工程と、
前記第１生成工程で生成されたラベル行列を前記画像データに対応付けて記憶装置に記憶する記憶工程と、
前記生成されたラベル行列より部分ラベル行列を抽出し、抽出された部分ラベル行列をキーとして画像データを検索可能なテーブルを保持する保持工程と、
検索元の画像データから部分ラベル行列を抽出し、前記テーブルを用いて類似画像を検索する第１検索工程と、
前記第１検索工程で検索された各類似画像を比較先画像として、前記記憶装置より得られた比較先画像のラベル行列と、前記検索元の画像データから得られるラベル行列との間でラベル間距離に基づくマッチング処理を行って類似度を獲得し、獲得した類似度に基づいて検索結果を得る第２検索工程と、
画像の一部を構成する部分画像が検索元の画像として指定された場合、該部分画像を表す部分画像データが含まれるブロックに関して前記特徴量に応じたラベルを付与し、他のブロックに関してはラベルとの間の距離がゼロであることを示すラベルを付与することで検索元の画像のラベル行列を生成する第２生成工程と、
前記部分画像の画像データが含まれるブロックに関して付与されたラベルに基づいて部分ラベル行列を生成する第３生成工程とを備え、
前記第１及び第２検索工程は、前記第２生成工程及び前記第３生成工程によって生成されたラベル行列と部分ラベル行列を用いて画像の検索を行うことを特徴とする画像検索方法。
【請求項１６】
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与し、付与されたラベルを所定のブロック順序で並べることによりラベル行列を生成する第１生成工程と、
前記第１生成手段で生成されたラベル行列を前記画像データに対応付けて記憶装置に記憶する記憶工程と、
前記生成されたラベル行列より部分ラベル行列を抽出し、抽出された部分ラベル行列をキーとして画像データを検索可能なテーブルを保持する保持工程と、
検索元の画像データから部分ラベル行列を抽出し、前記テーブルを用いて類似画像を検索する第１検索工程と、
前記第１検索工程で検索された各類似画像を比較先画像として、前記記憶装置から得られた比較先画像のラベル行列と、前記検索元の画像データから得られるラベル行列との間でラベル間距離に基づくマッチング処理を行って類似度を獲得し、獲得した類似度に基づいて検索結果を得る第２検索工程とを備え、
前記ラベル行列は２次元のラベル行列を表し、
前記第２検索工程が、
前記検索元の画像データのラベル行列より抽出される行単位のラベル列と、前記第１検索手段で得られた比較先画像データのラベル行列より抽出される行単位のラベル列とをＤＰマッチングによって対応づけることによって該比較先画像データの行並びを得る第１マッチング工程と、
前記元画像データのラベル行列の行並びと、前記第１マッチング手段で得られた行並びとの類似度をＤＰマッチングによって求める第２マッチング工程とを含むことを特徴とする画像検索方法。
【請求項１７】
請求項１５又は１６に記載の画像検索方法をコンピュータに実行させる制御プログラムを格納したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像を検索する画像検索装置及び方法に関するものである。
【０００２】
【従来の技術】
従来より類似画像を検索するための種々の技術が提案されている。類似画像検索を自然画像について行うための、ある程度実用化されている技術では、色情報を画像特徴量として用いているものが多い。そして、その多くが、色情報に関するヒストグラムを取ることにより、ＲＧＢの割合や画像中に多く存在する色の組み合わせを用いて検索を行うものである。
【０００３】
しかしながら、上記の手法では、色の位置情報が失われてしまうためにその検索精度は必ずしも高くなかった。また、例えば特開平８−２４９３４９号には、画像を複数のブロックに分け夫々の特徴量（代表色）を用いたパターンマッチングが開示されている。しかしながら、この手法では、マッチングを行う２つの画像について各ブロック間の特徴量の距離を計算しなければならず、膨大な計算量が必要となってしまう。特に特徴量として代表色を用いると、ＲＧＢ３個のデータを扱わなければならず、更に計算が複雑なものとなる。また、特徴量そのものを用いて比較を行うので、比較の精度が高くなる反面、画像のアングルが変ったり、物体の位置が変ったりするだけで類似画像検索できなくなってしまうといった問題がある。すなわち、画像のアングルが変ったり、物体の位置が変ったり、あるいは撮影条件による画像特徴量のある程度の違い等を吸収するなど、ある程度の曖昧さを有しながらも適切に画像検索を行うという、いわゆるロバストな類似画像検索を行うことはできなかった。
【０００４】
また、画像中のある物体（一部分）に着目して検索を行いたいような場合には、その物体以外の画像（背景画像）が異なると検索不可能となってしまう等、不都合な場合があった。
【０００５】
【発明が解決しようとする課題】
一般的な画像検索システムとして、自然画像を検索する場合に、画像にキーワードを付与しておき、このキーワードによって画像検索を行うことが知られている。しかし、このキーワード付け作業は人手のかかる作業であり、更に、キーワード付けが行われていない画像に関しては、縮小画を提示してマニュアルにて選択するという作業が生じ、検索操作を煩雑なものとしていた。
【０００６】
本発明は上記の問題点に鑑みてなされたものであり、画像の特徴量の配置を考慮した高速な類似画像の検索を可能とする画像検索装置及び方法を提供することを目的とする。
【０００７】
また、本発明の他の目的は、画像の特徴量の配置を考慮した類似画像の検索を行うとともに、撮影条件の変動等による違いを吸収した類似画像検索を可能とする画像検索装置及び方法を提供することにある。
【０００８】
また、本発明の他の目的は、特徴量群を１つのラベルで表し、画像をラベル行列で表現して画像間の類似度を算出することにより類似度の計算量を減少させ、迅速な類似画像検索を可能とすることにある。
【０００９】
また、本発明の他の目的は、ラベル行列を適切に管理し、ラベルを用いた画像検索処理の処理速度を著しく向上することにある。
【００１０】
また、本発明の他の目的は、元画像と比較先画像の類似度をラベル列もしくはラベル行列の比較によって行う際に、ＤＰマッチングやファジー非決定性オートマトン等のラベル位置の前後の曖昧さを許す手法を適用し、より効果的な類似画像検索を可能とすることにある。
【００１１】
また、本発明の他の目的は、画像中のある物体（一部分）に着目した類似画像検索を可能とすることにある。
【００１２】
【課題を解決するための手段】
上記の目的を達成するための本発明の一態様による画像検索装置は、例えば以下の構成を備える。すなわち、
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与し、付与されたラベルを所定のブロック順序で並べることによりラベル行列を生成する第１生成手段と、
前記第１生成手段で生成されたラベル行列を前記画像データに対応付けて記憶する記憶手段と、
前記生成されたラベル行列より部分ラベル行列を抽出し、抽出された部分ラベル行列をキーとして画像データを検索可能なテーブルを保持する保持手段と、
検索元の画像データから部分ラベル行列を抽出し、前記テーブルを用いて類似画像を検索する第１検索手段と、
前記第１検索手段で検索された各類似画像を比較先画像として、前記記憶手段から得られた比較先画像のラベル行列と、前記検索元の画像データから得られるラベル行列との間でラベル間距離に基づくマッチング処理を行って類似度を獲得し、獲得した類似度に基づいて検索結果を得る第２検索手段と、
画像の一部を構成する部分画像が検索元の画像として指定された場合、該部分画像を表す部分画像データが含まれるブロックに関して前記特徴量に応じたラベルを付与し、他のブロックに関してはラベルとの間の距離がゼロであることを示すラベルを付与することで検索元の画像のラベル行列を生成する第２生成手段と、
前記部分画像の画像データが含まれるブロックに関して付与されたラベルに基づいて部分ラベル行列を生成する第３生成手段とを備え、
前記第１及び第２検索手段は、前記第２生成手段及び前記第３生成手段によって生成されたラベル行列と部分ラベル行列を用いて画像の検索を行う。
【００１３】
又、上記の目的を達成するための本発明の他の態様による画像検索装置は、以下の公正を備える。すなわち、
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与し、付与されたラベルを所定のブロック順序で並べることによりラベル行列を生成する第１生成手段と、
前記第１生成手段で生成されたラベル行列を前記画像データに対応付けて記憶する記憶手段と、
前記生成されたラベル行列より部分ラベル行列を抽出し、抽出された部分ラベル行列をキーとして画像データを検索可能なテーブルを保持する保持手段と、
検索元の画像データから部分ラベル行列を抽出し、前記テーブルを用いて類似画像を検索する第１検索手段と、
前記第１検索手段で検索された各類似画像を比較先画像として、前記記憶手段から得られた比較先画像のラベル行列と、前記検索元の画像データから得られるラベル行列との間でラベル間距離に基づくマッチング処理を行って類似度を獲得し、獲得した類似度に基づいて検索結果を得る第２検索手段とを備え、
前記ラベル行列は２次元のラベル行列を表し、
前記第２検索手段が、
前記検索元の画像データのラベル行列より抽出される行単位のラベル列と、前記第１検索手段で得られた比較先画像データのラベル行列より抽出される行単位のラベル列とをＤＰマッチングによって対応づけることによって該比較先画像データの行並びを得る第１マッチング手段と、
前記元画像データのラベル行列の行並びと、前記第１マッチング手段で得られた行並びとの類似度をＤＰマッチングによって求める第２マッチング手段とを含む。
【００１５】
【発明の実施の形態】
以下、添付の図面を参照して本発明の好適な実施形態を説明する。
【００１６】
図１は本実施形態による画像検索装置の制御構成を示すブロック図である。同図において、１０１はＣＰＵであり、本実施形態の画像検索装置における各種制御を実行する。１０２はＲＯＭであり、本装置の立ち上げ時に実行されるブートプログラムや各種データを格納する。１０３はＲＡＭであり、ＣＰＵ１０１が処理するための制御プログラムを格納するとともに、ＣＰＵ１０１が各種制御を実行する際の作業領域を提供する。１０４はキーボード、１０５はマウスであり、ユーザによる各種入力操作環境を提供する。
【００１７】
１０６は外部記憶装置であり、ハードディスクやフロッピーディスク、ＣＤ−ＲＯＭ等で構成される。１０７はネットワークインターフェースであり、ネットワーク上の各機器との通信を可能とする。１０９はインターフェース、１１０は画像読み取りのためのスキャナである。また、１１１は上記の各構成を接続するバスである。なお、後述の各フローチャートに示される処理を実現する制御プログラムは、ＲＯＭ１０２に格納されていてもよいし、外部記憶装置１０６よりＲＡＭ１０３にロードされてもよい。
【００１８】
なお、上記の構成においてスキャナ１１０や外部記憶装置１０６はネットワーク上に配置されたもので代用してもよい。
【００１９】
図２は本実施形態の画像検索装置の機能構成を示すブロック図である。同図において、１１はユーザインターフェース部であり、表示器１０７、キーボード１０４及びマウス１０５を用いて、ユーザからの各種の操作入力を検出する。１２は画像入力部であり、スキャナ１１０による画像の読み取りを行う。１３は画像メモリであり、画像入力部１２によって得られたイメージデータをＲＡＭ１０３の所定の領域に格納する。１４は画像特徴量抽出部であり、画像メモリ１３に格納した画像について、後述の手順で特徴量を抽出する。１５は特徴量ラベル行列化部であり、画像特徴量抽出部１４によって得られた特徴量に基づいてラベル行列を生成する。１６はパターンマッチング部であり、指定された画像のラベル行列と、画像蓄積部１７に蓄積されている画像のラベル行列との間の類似度を算出し、類似画像を検索する。１７は画像蓄積部であり、画像入力部１２等によって得られた画像データを蓄積する。
【００２０】
１８は画像管理データベース（以下、画像管理ＤＢ）であり、図３で示されるデータ形態で画像蓄積部１７に格納された画像データを管理する。また、１９はラベル成分インデックスであり、図４に示されるラベル成分インデックスファイルを格納する。なお、ラベル成分インデックスの利用については、図９のフローチャートにより後述する。
【００２１】
以上のような構成を備えた本実施形態の画像検索装置の動作例を以下に説明する。なお、以下の例では色に着目した画像特徴量として、赤（Ｒ）、緑（Ｇ）、青（Ｂ）の三色を採用し、３次元の色空間での処理を用いて説明する。
【００２２】
［画像の登録処理］
先ず画像登録の際に行う処理を説明する。図５は本実施形態による画像登録処理の手順を表すフローチャートである。まず、ステップＳ１１において、ユーザーインターフェース部１１を介したユーザの指示により、画像入力部１２を用いて画像を読み込み、画像メモリ１３に保持する。次に、ステップＳ１２において、この画像を複数のブロックに分割する。本実施形態では、画像を縦横の複数ブロックに分割する。図６は本実施形態による画像のブロック分割例を示す図である。同図に示されるように、本実施形態では、説明のため３×３の計９個のブロックに画像を分割するものとする。次にステップＳ１３において、分割された各ブロックの特徴量を算出し、得られた特徴量を次の手順でラベル化する。
【００２３】
なお、本実施形態で用いる３×３への分割はあくまで説明のためのものである。実際には、自然画であれば１０×１０以上の分割数とするのが好ましい。また、白の無地背景に商品が写っているような場合であれば、１３×１３以上の分割数とするのが好ましい。
【００２４】
図７は本実施形態による多次元特徴量空間を説明する図である。図６に示すように、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロック（色ブロック）、即ちセル（色セル）に分割し、夫々のセル（色セル）に対して通し番号でユニークなラベルを付与する。ここで、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロックに分けたのは微妙な特徴量（色）の違いを吸収するためである。
【００２５】
なお、多次元特徴量空間に関しては、画像特徴量をそのまま用いるものではなく各パラメータを平均と分散を実験によって求め規格化（正規化）した後、例えば、主成分分析等の直交変換を行い、意味のある次元にしたものを用いることが考えられる。なお、「意味のある次元」とは、主成分分析において、寄与率が大きな主成分軸で構成される次元である。
【００２６】
ステップＳ１３では、ステップＳ１２で得られた各分割ブロックに対して、定められた画像特徴量計算処理を行い、上記多次元特徴量空間上のどのセルに属するかを求め、対応するラベルを求める。この処理を全てのブロックに対して行う。すなわち、分割画像ブロックに対して、全ての画素がどの色セルに属するかの計算処理を行い、もっとも頻度の多い色セルのラベルをその分割画像ブロックのパラメータラベル（カラーラベル）として決定し、この処理を全てのブロックに対して行う。
【００２７】
以上のようにして各ブロックに対してパラメータラベルが付与されると、ステップＳ１４において、各ブロックに付与されたパラメータラベルを所定のブロック順序で並べることにより、パラメータラベル行列（以下、ラベル行列とする）が生成される。
【００２８】
図８はラベル列を生成する際のブロック順序例を説明する図である。同図の分割画像ブロックの升にある数字に従って上記のパラメータラベルを並べ、ラベル列を作る。なお、画像管理データベース１８やラベル成分インデックス１９にラベル行列を格納するに際しては、上述のように２次元的なラベル行列を所定の順序で１次元に並べたものを格納するが、本実施形態ではこのような１次元の形態のものもラベル行列と称することにする。
【００２９】
ここで、図８の（ａ）では、分割ブロックを左から右へ水平方向へスキャンし、この水平方向のスキャンを上から下へ行う順序となっている。なお、本実施形態に適用可能なスキャンの方法としては、
・水平方向（図８の（ａ）に示したように、左から右へのスキャンを上から下へ行うという順序の他に、図８の（ｂ）〜（ｄ）に示すように、左から右へのスキャンを下から上へ行う等、４通りのスキャン方法がある）、
・垂直方向（上から下へのスキャンを左から右へ行う等、４通りのスキャン方法が考えられる）、
・図８（ｅ）に示すように、偶数ラインと奇数ラインでスキャンを分ける。
【００３０】
なお、本実施形態では、図８の（ａ）に示すスキャン方法を採用するが、上述した他のスキャン方法も適用可能であることは明らかであろう。
【００３１】
続いてステップＳ１５において、以上のようにして得たラベル列や画像データを画像蓄積部１７、画像管理ＤＢ１８に反映する。すなわち、ステップＳ１１で読み込んだ画像データに対して画像ＩＤを取得し、これらをペアにして画像蓄積部１７に格納する。また、当該画像ＩＤに対応付けて図３に示した画像管理ＤＢレコードを生成し、これを画像管理ＤＢ１８に登録する。
【００３２】
そして、ステップＳ１６において、当該画像のラベル行列から部分ラベル行列を獲得し、図４に示すようなラベル成分インデックスファイルを更新する。ラベル成分インデックスファイルは、部分ラベル行列（単独のラベルを含む）を検索キーとし、画像ＩＤ群と各画像に含まれる部分ラベル行列の個数を納めるレコードを格納したものである。このラベル成分インデックスによれば、部分ラベル行列（単独のラベルを含む）を与えることにより、当該部分ラベル行列を持つ画像ＩＤ群と、各画像の当該部分ラベル行列（単独のラベルを含む）の含有数が高速に得られる。なお、画像登録時の段階では未加工のレベルで情報を格納しておく。また、ラベル行列を構成するすべてのラベルをラベル成分インデックスに登録する。例えば、ラベルのヒストグラム情報を得て、出現するラベルの全てがラベル成分インデックスに反映されるようにする。例えば、単独のラベルが登録されたラベル成分インデックスを用いた場合は、ヒストグラム情報に現れる全てのラベルをキーとするデータレコードを更新することになる。
【００３３】
なお、画像の登録処理において異は、後述のドント・ケアー・ラベルは用いられない。すなわち、ラベル成分インデックスには、ドント・ケアー・ラベルは登録されない。以上が画像登録時に行われる処理である。
【００３４】
［画像の検索処理］
次に、図９及び図１０のフローチャートに従って、本実施形態による類似画像検索処理を説明する。検索処理はおおきく分けて画像全体の類似画像検索であるか、あるいは物体に着目した検索であるかにより処理が異なってくる。以下、順を追って説明する。
【００３５】
図９は、本実施形態による画像検索の手順を説明するフローチャートである。まず、ステップＳ２１において、当該検索が画像全体の類似画像検索であるか、所望の物体（或いは部分領域）に着目した検索であるかを指定する。検索方法が指定されるとステップＳ２２において、指定された検索方法に適合したラベル行列と特徴部分ラベル行列が取得される。このステップＳ２２では、指定された検索方法に応じて処理が異なる。以下、図１０のフローチャートを参照してステップＳ２２における処理の手順を詳細に説明する。
【００３６】
図１０は本実施形態による、特徴部分ラベル行列の抽出手順を説明するフローチャートである。
【００３７】
まず、ステップＳ４１において、指定された検索方法を判定する。指定された検索方法が「画像全体の類似検索」であった場合は、ステップＳ４２へ進む。ステップＳ４２では、検索者が画像全体の類似検索を行いたい画像を選択する。すなわち、類似検索元画像を指定する。ステップＳ４３では、指定された類似検索元画像に対応するラベル行列を画像ＤＢ１８より獲得する。そして、ステップＳ４４において、特徴部分ラベル行列を取得する。
【００３８】
なお、特徴部分ラベル行列の求め方に関しては、経験・実験による学習や統計的な手法など、実現手段は様々存在するものであり、ここでは特に限定されるものではない。一例を挙げると、このラベル行列を例えばヒストグラム解析を行うことにより特徴的な部分ラベル行列（単一ラベルも含む）を求める。
【００３９】
一方、ステップＳ４１において、着目物体の類似検索が指定されたと判定された場合は、ステップＳ４５へ進み、検索元となる着目物体の画像を決定する。着目物体の決定方法としては、例えば以下の方法が挙げられる。
【００４０】
（１）画像中の着目物体をポインティングデバイスで指示し、画像処理により着目物体を背景画像から分離し、背景画像を取り除くことで着目物体画像を作成する。一例を挙げると、ユーザーが指定した座標からエッジや色の変化具合を考慮して着目物体を抽出する既存の画像処理技術を用いる。この場合、着目物体の抽出内容に、誤りがあれば、抽出輪郭線をポインティングデバイスで補正することで、正確な着目物体の抽出が行える。
【００４１】
（２）物体画像ライブラリから着目物体画像を選択する。物体画像ライブラリに関して一例を挙げれば、予めキーワード検索が可能な物体画像を自らのシステムにインストールしておく方法や、あるいはインターネット等のネットワークを介してサーバーにキーワードで物体画像を検索して物体画像を入手する方法が考えられる。
【００４２】
（３）描画ソフトを用いて着目物体の画像を描いたり、（１）或いは（２）で得られた着目物体画像の色を変更してこれを着目物体画像とする。
【００４３】
次に、ステップＳ４６へ進み、上記抽出した着目物体画像を、その大きさや位置、方向を考慮して画像フレームに貼り付け、類似検索元画像を作成する。そして、ステップＳ４７において、当該類似検索元画像をブロック分割し、上記（１）〜（３）のいずれかの手法によって得た着目物体画像を含む分割ブロックの部分のみに関して、登録のときと同様な画像特徴抽出処理（例えば、代表色抽出）を行いラベル化する。更に、ステップＳ４８では、着目物体画像を含まない分割ブロックに対して、どのラベルともペナルティーが０のドント・ケアー・ラベル（don't care label）を付与し、類似検索元画像のラベル行列を生成する。
【００４４】
なお、上記の（１）から（３）の手法によって得られる画像において、着目物体画像の占める面積と背景領域の面積との比に応じて画像の分割方法を変えるようにしてもよい。例えば、着目物体画像の面積が所定の割合以下であって場合は、当該着目物体画像に外接するような矩形領域について所定数の分割ブロックを得て、ラベル割り当てを行う。また、着目物体画像の面積が所定の割合を越えていれば、上述の画像フレームについて分割ブロックを得るようにする。
【００４５】
そして、ステップＳ４９では、ステップＳ４８で得られた類似検索元画像のラベル行列よりドント・ケアー・ラベルを除いた各ラベルに対して、上述のようなヒストグラム処理を行い、特徴部分ラベル行列を取得する。例えば、この着目物体を含む画像分割ブロック群のみから得たラベル行列にヒストグラム解析を施すことにより特徴的な部分ラベル列を取得する。なお、ヒストグラム解析においては、色の事前の存在確率や色空間上での飽和などを考慮した重み付けヒストグラム処理を行ってもよい。また、着目物体による類似検索においても、特徴的な部分ラベル行列は複数個の存在を可能とする。
【００４６】
以上のようにして、検索方法に適合した類似検索元画像のラベル行列と特徴部分ラベル行列が取得されると、処理は図９のステップＳ２３へ進む。ステップＳ２３では、ラベル成分インデックス１９ステップＳ２２で得られた特徴部分ラベル行列の含有数の上限値及び下限値を決定する。この上限値及び下限値で決まる含有数の範囲は、ラベル成分インデックス１９を用いて行われるマッチング処理対象画像の絞り込み（プリサーチ）に用いられる。
【００４７】
特徴的な部分ラベル行列の含有数の上限下限の決定手法に関しては経験・実験による学習や統計的な手法など手段はさまざま存在し、ここでは特に限定は行わない。一例を挙げると、検索元画像に取得された特徴部分ラベル行列が含まれる個数ｎ0に対する割合で指定を行う。例えば、値が１以上の曖昧度fuzziness（大きいほど曖昧な検索を行う）を導入し、上限は曖昧度に比例したｎ0×fuzzinessとし、下限は反比例したｎ0÷fuzzinessとする。
【００４８】
このように、拡大縮小した画像を検索したい場合や、多少異なった画像をも検索したい場合の曖昧さの度合いに応じた曖昧度fuzzinessを与え、プリサーチの曖昧さを調節することが可能となる。
【００４９】
次に、ステップＳ２４において、ラベル成分インデックスファイルを参照して、ステップＳ２３で決定した上限値および下限値の範囲内の個数の特徴部分ラベル行列を含む画像ＩＤ群を求める。ラベル成分インデックスは図４に示したように部分ラベル行列をキーとして、当該部分ラベル行列を含む画像の画像ＩＤとその含有数が登録されている。従って、ステップＳ４４或いはステップＳ４９で得られる特徴部分ラベル行列を用いて検索が行え、当該特徴部分ラベル行列を所望の含有数範囲で含む画像ＩＤを容易、かつ高速に得ることができる。
【００５０】
部分特徴ラベル行列を用いて取得される画像ＩＤの数が、所定の目標数以下となるまで絞り込みを行う。例えば、ヒストグラム上位のものから順に選ばれた特徴部分ラベル列を用いて上記の手法により順次画像ＩＤ群を取得し、順次取得される画像ＩＤ群の論理積を取って目標数の画像ＩＤに絞り込んでいく。なお、ヒストグラム解析では、色の事前の存在確率や色空間上での飽和などを考慮した重み付けヒストグラム処理を行ってもよい。また、特徴的な部分ラベル行列は複数個存在してもよい。
【００５１】
次に、ある程度以上同一のラベルを含むラベル行列群と類似検索元の画像のラベル行列とを比較し、類似検索したい画像のラベル行列に近いラベル行列群を類似度とともに検索結果として出力する。
【００５２】
検索者が類似検索を行いたい画像を選択すると画像管理ＤＢからこれに対応するカラーラベル行列を得て、インデックスファイルから既に登録している画像のカラーラベル行列群を得て、これとの比較により、類似検索したい画像のカラーラベル行列に近いカラーラベル行列群を類似度とともに検索結果として出力する。
【００５３】
上記のステップＳ２４における処理は、登録してある全ての画像についてラベル行列間のマッチング（比較）を行うと処理が遅くなるので、予め似ているものを抽出し、抽出された画像について類似検索元画像のラベル行列との比較を行うためである。もちろん、処理が遅くなってもよければ、登録した画像の全てのラベル行列との比較を行うようにして、精度の高い検索を行ってもよい。
【００５４】
次に、ステップＳ２５において、検索元画像のラベル行列と、ステップＳ２４で取得された画像のラベル行列との間でパターンマッチングを行う。すなわち、ある程度以上共通なラベルを持った画像のラベル行列と類似検索元画像のラベル行列とを、ラベル間ペナルティーマトリックスを考慮したマッチング処理を行って比較する。ペナルティーマトリックスについては図１１により後述する。この比較の結果得られるペナルティー値（ラベル間の距離）に基づいて類似度を決定する。本実施形態では、ラベル行列におけるラベルの２次元的配置を考慮した２次元ＤＰマッチングを用いる。なお、２次元ＤＰマッチングについては後述する。
【００５５】
ステップＳ２６では、ステップＳ２５におけるマッチング処理の結果として得られた類似度が所定のしきい値以上であるかどうかを判断する。類似度が所定のしきい値以上であれば、ステップＳ２７へ進み、当該画像ＩＤを検索結果に登録するとともに、類似度の大きい順にソートする。一方、ステップＳ２６において類似度が所定のしきい値に達していないと判定された場合は、ステップＳ２７をスキップし、検索結果から除外する。ステップＳ２８では、ステップＳ２４で取得された全ての画像について上記ステップＳ２５からＳ２７の処理を終えたかどうかを判断し、未処理の画像があればステップＳ２５へ戻り、全画像について処理を終えていればステップＳ２９へ進む。
【００５６】
ステップＳ２９では、画像管理データベース１８を参照して、検索結果として類似度の大きい順に登録された画像ＩＤに対応するフルパスのファイル名を得て、これをユーザに提示する。
【００５７】
［２次元ＤＰマッチング］
次にラベル行列同士の類似比較を行うための２次元ＤＰマッチングについて述べる。
【００５８】
図１１はラベル列を比較し類似度を求める際に用いるラベル間のペナルティマトリックスの一例を示す図である。マトリクス中の値が小さい程類似していることになる。すなわち、カラーラベル間のパターンマッチングに際して、隣接する色セル同士ではペナルティー（距離）を小さくし、遠いものには大きなペナルティーを与えるものである。例えば、ラベル２とラベル６のペナルティは「７」である。また、同じラベル同士のペナルティは当然のことながら「０」となっている。本マトリクスの使用目的はラベルの類似に応じた距離判定を行うことにある。すなわち、本実施形態では、特徴量空間としてＲＧＢカラー空間を用いているので、色の類似に応じた距離判定が行えることになる。但し、ドント・ケアー・ラベルに関しては全てのラベルに対しペネルティーが０と定義する。
【００５９】
例えば、図１２に示す例では、検索元画像のラベル列が「１１２３１３４４１」であり、検索対象画像のラベル列が「１１３２２４４５２」である。このような一次元のラベル列のＤＰマッチング、すなわち一次元のＤＰマッチングは一般によく知られたものである。すなわち、図１２のラベル列に関して、図１１のペナルティマトリクスを用いてＤＰマッチングを行うと、図１３に示されるように両ラベル列間の距離（最終解）が求まる。なお、この例では、傾斜制限として次の条件を用いている。すなわち、図１４において、格子点(i-1,j),(i-1,j-1),(i,j-1)上のコストをそれぞれg(i-1,j), g(i-1,j-1), g(i,j-1)とし、格子点（i,j）上のペナルティをd(i,j)とした場合に、格子点（i,j）上のコストg（i,j）を以下の漸化式によって求めている。
【００６０】
【数１】
0003952592.tif 000002
【００６１】
なお、ラベル列同士の比較においては、オートマトン等のラベルシーケンスを曖昧に比較できるマッチングを行うようにしてもよい。このような曖昧化の手法を用いることにより、余分なラベルの付加、ラベルの欠落や同じラベルの繰り返しに対しては低いペナルティが与えられとともに、ラベル間のペナルティには図１２のカラーラベル間のペナルティマトリックスを用いてラベル列同士の距離計算を行うことで、曖昧なパターンマッチングが行えるようになる。なお、オートマトンとしては、「特開平８−２４１３３５のファジー非決定性有限オートマトンを使用した曖昧な文字列検索方法およびシステム」に記載されている「ファジー非決定性有限オートマトン」を適用することができる。
【００６２】
本実施形態では、上記の一次元ＤＰマッチングを２次元に拡張した２次元ＤＰマッチングを用いてラベル行列同士の類似比較（類似度の算出）を行う。以下、２次元ＤＰマッチングを説明する。
【００６３】
図１５は本実施形態による類似度算出処理を説明する図である。上述のステップＳ２２（ステップＳ４３、Ｓ４８）において取得された類似検索元画像のラベル行列は、そのスキャン方法に従って図１５の（ｂ）のように並べることができる。また、ステップＳ２４において抽出された画像ＩＤのラベル行列群のうちの一つを類似比較先画像とすると、そのラベル行列は図１５の（ａ）のように並べることができる。
【００６４】
まず、類似比較先画像の第１行目のラベル列「ａｂｃ」と、類似検索元画像の第１〜第３行目のラベル列（「１２３」、「４５６」、「７８９」）のそれぞれとの距離をＤＰマッチングによって求め、その距離が最少となるラベル列の類似検索元画像における行番号を類似ライン行列（図１５の（ｃ））の該当する位置に記憶する。また、得られた最小距離が所定の閾値よりも大きい場合には、どの行とも類似していないと判断し、類似ライン行列の該当する位置に「！」を記憶する。ＤＰマッチングの性質により、たとえば画像のアングルが水平方向へ多少変わっていたとしても、上記処理により類似する行（ライン）を検出可能である。以上の処理を、類似比較先画像の全ての行（「ｄｅｆ」「ｇｈｉ」）について行うことで、図１５の（ｃ）のような列方向の類似ライン行列が得られる。なお、この処理において、類似検索元画像中のドント・ケアー・ラベルのみからなる列（ドント・ケアー・ラベル列）に関しては処理を行わない。これは、ドント・ケアー・ラベルのみからなる列は類似比較先画像の全ての列と距離がゼロとなってしまうからである。
【００６５】
図１５の（ｃ）では、「ａｂｃ」に類似した行が類似検索元画像に存在せず、「ｄｅｆ」に類似した行が類似検索元画像の第１行目、「ｇｈｉ」に類似した行が類似検索元画像の第２行目であったことを示している。以上のようにして得られた類似ライン行列と標準ライン行列（類似検索元画像の行の並びであり、本例では「１２３」となる）との類似度をＤＰマッチングを用いて算出し、これを当該類似検索元画像と当該類似比較先画像との類似度として出力する。なお、ＤＰマッチングでは、周知のように、比較するラベルシーケンスが最も類似距離が小さくなるように、比較するラベルシーケンスを伸縮（比較する相手を次に進めないで我慢する）させて比較するという処理を行う。また、何処まで伸縮（我慢）できるかを制約条件（整合窓の幅）で与えることも可能である。
【００６６】
図１６は本実施形態による２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。上記図１５を参照して説明した処理を、図１６のフローチャートを参照して更に説明する。
【００６７】
まず、ステップＳ１０１において、類似比較先画像の行番号を表す変数ｉと、類似検索元画像の行番号を表す変数ｊを１に初期化し、ともに第１行目を示すように設定する。次に、ステップＳ１０２において、類似比較先画像の第ｉ行目のラベル列を取得する。例えば図１５の場合、ｉ＝１であれば「ａｂｃ」が取得される。そして、ステップＳ１０３において、類似検索元画像の第ｊ行目のラベル列を取得する。例えば、図１５において、ｊ＝１であれば、「１２３」が取得される。ステップＳ１０３ａでは、ステップＳ１０３で取得されたラベル列がドント・ケアー・ラベル列か否かを判断し、ドント・ケアー・ラベル列であればステップＳ１０６へ、そうでなければステップＳ１０４へそれぞれ進む。
【００６８】
次にステップＳ１０４では、上記ステップＳ１０２、Ｓ１０３で得られた２つのラベル列間の距離を、図１１で説明した色セルペナルティーマトリクスを用いて、ＤＰマッチングによって求める。そして、ステップＳ１０５において、ステップＳ１０４で得た距離が、第ｉ行目に関してそれまでに得られた距離の最小値であれば、当該行番号（ｊ）をライン行列要素ＬＩＮＥ［ｉ］に記憶する。
【００６９】
以上のステップＳ１０３からステップＳ１０５の処理を、類似検索元画像の全ての行について行う（ステップＳ１０６、Ｓ１０７）。以上のようにして、類似比較先画像の第ｉ行目のラベル列に対して、類似検索元画像に含まれる行のうち最も距離の近い行の番号がＬＩＮＥ［ｉ］に格納されることになる。
【００７０】
そして、ステップＳ１０８において、上記処理でられたＬＩＮＥ［ｉ］と所定の閾値（Ｔｈｒｅｓｈ）とを比較する。そして、ＬＩＮＥ［ｉ］がＴｈｒｅｓｈ以上であればステップＳ１０８へ進み、いずれの行とも類似していないことを表す「！」をＬＩＮＥ［ｉ］に格納する。
【００７１】
以上説明したステップＳ１０２からＳ１０８の処理を類似比較先画像の全ての行について実行する（ステップＳ１１０、Ｓ１１１）ことにより、ＬＩＮＥ［１］〜ＬＩＮＥ［ｉｍａｘ］が得られるので、これを類似ライン行列ＬＩＮＥ［］として出力する。
【００７２】
次に、ステップＳ１１３において、標準ライン行列「１２…ｉｍａｘ」と類似ライン行列ＬＩＮＥ［］とのＤＰマッチングを行い、両者の距離を算出する。なお、ここで、標準ライン行列とは、１から始まり、列方向に１ずつ増加する行列である。
【００７３】
ここで、標準ライン行列と類似ライン行列間のＤＰマッチングにおいて用いられるペナルティーについて説明する。列方向の類似ライン行列と標準ライン行列とのＤＰマッチングのペナルティーの設定としては２つの方法が考えられる。すなわち、動的なペナルティーと固定的なペナルティーの２つである。
【００７４】
動的なペナルティーとは、動的にライン番号間のペナルティーを設定するものであり、画像によってライン番号間のペナルティーは変化する。本実施形態では、類似検索元画像の自分自身の横（行）方向のラベル行列の距離を求め、これに基づいて各行間のペナルティーを求める。
【００７５】
図１７は本実施形態による動的なペナルティー値の設定手順を示すフローチャートである。ステップＳ１２１において、変数ｉを１に、変数ｊを２にそれぞれセットする。次に、ステップＳ１２２において、類似検索元画像の第ｉ行目のラベル列を取得し、ステップＳ１２３において、類似検索もと画像の第ｊ行目のラベル列を取得する。そして、ステップＳ１２４において、類似検索元画像の第ｉ行目のラベル列と第ｊ行目のラベル列とについて、色ペナルティーマトリクスを用いてＤＰマッチングを行い、距離を獲得する。ステップＳ１２５では、ステップＳ１２４で得たＤＰマッチングの距離を、類似検索元画像のｉ行目のラベル列とｊ行目のラベル列間のペナルティーとしてＬＩＮＥ[i][j]に記憶すると共に、、類似検索元画像のｊ行目のラベル列とｉ行目のラベル列間のペナルティーとしてＬＩＮＥ[j][i]に記憶する。
【００７６】
ステップＳ１２６によって、変数ｊの値がｊｍａｘとなるまで、ステップＳ１２３〜Ｓ１２５の処理が繰返される。この結果、第ｉ行目のラベル列について、ｉ＋１〜ｊｍａｘ行目の各ラベル列との間のペナルティー値が決定される。そして、ステップＳ１２８、Ｓ１２９、Ｓ１３０により、ステップＳ１２３〜Ｓ１２６の処理を変数ｉの値がｉｍａｘ−１となるまで繰返される。この結果、ＬＩＮＥ[i]「ｊ］には、ｉ＝ｊの対角成分を除く全てに、上記処理で決定されたペナルティー値が記憶されることになる。
【００７７】
次にステップＳ１３１では、上記処理で決定されていないＬＩＮＥ[i][j]の対角成分のペナルティーを決定する。この部分はｉ＝ｊであり、同一のラベル列であるから、その距離は０であり、従ってペナルティー０が記憶される。また、ステップＳ１３２では、「！」に関してペナルティーを決定する。すなわち、「！」に対するペナルティーは、ＬＩＮＥ[i][j]の全てのペナルティー値の中で、最大のペナルティー値よりもある程度大きな値を設定する。ただし、このペナルティー値を極端に大きくすると、曖昧にヒットする性質が損なわれてしまう。
【００７８】
以上のようにして類似検索元画像に関して計算されたラベル列間のペナルティーを用いて、上記ステップＳ１１３におけるＤＰマッチングを行い、類似度検索元画像と類似比較先画像の類似度を獲得する。
【００７９】
一方、固定的なペナルティーでは、ＤＰマッチングのペナルティーとして、ラベルが一致すればペナルティー「０」を、一致しない場合、もしくは「！」との比較であった場合にはある程度の大きさのペナルティーを与える。この場合は類似検索元画像によらず、常に同じペナルティーとなる。このような固定的なペナルティーを用いてステップＳ１１３の処理を実行し、類似度検索元画像と類似比較先画像の類似度を決定する。
【００８０】
以上説明したマッチング処理は次のような特徴を有する。もし、図１５の（ａ）と（ｂ）が極めて類似していれば、類似ライン行列は「１２３」となり、その距離は０となる。また、類似ライン行列が「！１２」や「２１２」であれば、類似検索元画像に対して類似比較先画像は下方向へずれたものである可能性があるし、類似ライン行列が「２３！」や「２３３」であれば類似検索元画像に対して類似比較先画像が上方向へずれたものである可能性がある。また、類似ライン行列が「１３！」や「！１３」であれば、類似検索元画像に対して類似比較先画像が縮小したものである可能性がある。同様に、類似比較先画像が類似検索元画像を拡大したようなものである場合も検出可能である。
【００８１】
上述のステップＳ１１３で説明したように、類似ライン行列と標準ライン行列との間でＤＰマッチングを行うことにより、垂直方向へのずれが効果的に吸収される。このため、上述したような、上方向や下方向へのずれ、拡大、縮小等に起因する類似検索元画像と類似比較先画像との相違が効果的に吸収され、良好な類似検索を行うことが可能となる。
【００８２】
すなわち、本実施形態の２次元ＤＰマッチングは、ラベル行列の各ラベル列における前後の曖昧さを許容するマッチングであり、画像の位置ずれの影響を吸収する性質を有する。また、アングルの違い等により物体の位置が変わり、ブロックによって切りとられる物体の位置が変わることにより、ブロックの色合いも微妙に異なることが予想されるが、この違いは上述のペナルティーマトリクスにより吸収されることになる。このように、本実施形態の２次元ＤＰマッチングによる曖昧さを許容するマッチングと、ペナルティーマトリクスによる特徴量の曖昧さの許容との相乗効果によって、上下左右拡大、縮小のずれに対しても影響の少ないマッチングを可能としている。
【００８３】
ただし、動的なペナルティーと固定的なペナルティーとでは、動的なペナルティーを用いる方が好ましい。例えば、一面麦畑の類似元検索画像があったとした場合、どのラインも似たようなラベル列となることが考えられる。一方、類似比較先画像にも一面麦畑の画像があったとした場合に、この画像の類似ライン行列には全て最初のライン番号１が入り、「１１１」となってしまう可能性がある。この場合、類似検索元画像のどのラインも似たような画像となっており、ライン番号間のペナルティーが極めて小さくなければ低い距離でのヒットはしない。しかしながら、動的なペナルティーを用いた場合は、ライン番号間のペナルティーが低くなり、類似度の高い結果を得ることができる。
【００８４】
一方、固定的なペナルティーを用いると、「１２３」と「１１１」ではペナルティー値が大きくなり、類似度が低くなってしまう。
【００８５】
以上のようにして、ＤＰマッチングを水平・鉛直方向、すなわち２次元に行うことにより、水平や鉛直方向、更に斜め方向に画像アングルが変わったり、物体が移動していても検索を行うことが可能である。また、ＤＰマッチングの時系列伸縮特性により、ズームアップ撮影画像やマクロ撮影画像をも検索することが可能となる。
【００８６】
なお、上記実施形態では、水平方向のブロック並びに対応するラベル列を用いて類似ライン行列を得たが、垂直方向のブロック並びに対応するラベル列を用いて類似ライン行列を得るようにすることも、上記と同様の手法で実現可能である。
【００８７】
以上説明したように、本実施形態によれば、特徴量群（特徴量空間を分割して得られる特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル同士の類似度に基づく距離を上述の２次元ＤＰマッチングとペナルティーマトリクスによって与える。このため、２つの画像のブロック間の距離の計算量を大幅に減少させることができるとともに、類似した特徴量が同じラベルで表されることになるので、類似画像の検索を良好に行うことができる。
【００８８】
また、（１）ペナルティマトリクスによるラベル同士の距離概念を導入し、（２）比較するラベル位置を前後曖昧に移動させることが出来、トータルの距離が最小（類似度が最大）となるようなラベル行列の比較を実現する上記２次元ＤＰマッチングを導入したことにより、画像のアングルが多少変わっても検索することが可能となり、雰囲気の似ている画像を検索できるようになる。
【００８９】
更に上記実施形態によれば、インデックスデータベース（ラベル成分インデックス）を用いたことにより、画像検索が更に高速化する。
【００９０】
すなわち、上記実施形態によれば、画像の特徴量の配置を考慮した類似画像の高速な検索が行われるとともに、撮影条件の変動等による違いを吸収した類似画像の検索が可能となり、従来難しかった画像のアングルが変ったり、物体の位置が変ったり、あるいは他の撮影条件が変動したりすることによる画像の特徴量のある程度の違いを吸収するなど、ロバストな類似画像検索を行うことが可能となる。
【００９１】
なお、上記各実施形態においては、自然画像検索を行う例を説明したが、本発明はＣＧやＣＡＤ等の人工的な画像の検索にも適応可能な技術であることは当業者には明らかである。
【００９２】
また、上記各実施形態では画像特徴量として色情報を選んだが、本発明はこれに限られるものではなく、その他の画像パラメータを画像分割ブロックごとに求めることで実施することも可能である。
【００９３】
また、上記実施形態では１つの特徴量での認識の例を挙げたが、その他の特徴量での検索結果との論理演算を行うことにより、複数の特徴量からの高速な検索を行うことも可能である。
【００９４】
１つの画像に対して複数の画像特徴量を用いた検索を行う場合には、本発明で得られる類似度を１つの新たなる画像特徴量とみなし、複数のパラメータを用いた多変量解析を行い統計的な距離尺度を用いた検索を行うことも可能である。また、上記実施形態では、類似度が所定値を越える類似画像を検索結果として得るが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよいことはいうまでもない。
【００９５】
なお、曖昧度を指定することにより、ＤＰマッチングにおけるいわゆる整合窓の幅を変更することにより、検索の曖昧度を所望に設定可能とすることもできる。図１８はＤＰマッチングにおける整合窓を説明する図である。図１８において直線ＡはＪ＝Ｉ＋ｒで表され、直線ＢはＪ＝Ｉ−ｒで表される。整合窓の幅はｒの値を変更することで行える。したがって、キーボード１０４から曖昧度を指定することにより、このｒの値が変更されるように構成すれば、ユーザの所望の曖昧度（整合窓の幅）で類似度検索を行えるようになる。
【００９６】
なお、上記実施形態のような２次元ＤＰマッチングにおいては、水平方向のＤＰマッチングにおける整合窓の幅と、垂直方向のＤＰマッチングにおける整合窓の幅とを別々に設定できるようにしてもよい。或いは、両整合窓が異なる変化率で変化するように構成してもよい。このようにすれば、ユーザは、類似画像検索に際してよりきめ細かい曖昧さの設定を行えるようになる。例えば、図８で示されたようなブロック順序を用いた場合において、検索元の画像中における注目物体の横方向への移動を許容したいような場合や、検索元の画像が横長画像であるような場合には、横方向への曖昧度を大きくするために水平方向のＤＰマッチングにおける整合窓の幅をより大きくすればよい。
【００９７】
なお、ブロック化できない１つの画像に対して１つのパラメータを加味した類似検索の場合には、本発明で得られる類似度（ペナルティの総和を用いて作る）を１つの新たなる特徴量として、統計的な距離尺度に基づく検索を行うことも可能である。また、上記実施形態では、類似度が所定値を越える類似画像を検索結果として得るが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよいことはいうまでもない。
【００９８】
更に、ＤＰマッチング処理の代わりにファジー非決定性オートマトン等の、比較するラベル位置を前後曖昧に移動させることが出来、トータルの距離が最小（類似度が最大）となるようなラベル列の比較を実現する手法を導入することも可能であり、これにより画像のアングルが多少変わっても検索することが可能となり、雰囲気の似ている画像を検索できるようになる。
【００９９】
更に上記実施形態によれば、インデックスデータベース（ラベル成分インデックス（図４））を用いたことにより、画像検索が更に高速化する。
【０１００】
以上のように、本実施形態によれば、キーワードの付いていない画像を検索するのに好適な画像検索装置、方法が提供される。
【０１０１】
画像認識技術への壁が厚い現在、自分の欲しい画像に近い縮小画を見つけ、その画像に類似する画像を検索する手段を提供する事により、縮小画提示、類似画像検索を繰り返す事により、高い確率で検索者の欲しい画像を得る手段が考えられる。
【０１０２】
その際、本方式では、従来難しかった画像のアングルが変わったり、物体の位置が変わったり、或いは撮影条件による画像特徴量のある程度の違い等を吸収するなどロバストな類似画像検索を高速に行うことが可能となる。また、従来の類似画像検索の弱点であった背景による検索の影響を受けない、着目物体を重視した検索も可能となった。
【０１０３】
なお、本発明は、複数の機器（例えばホストコンピュータ，インタフェイス機器，リーダ，プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機，ファクシミリ装置など）に適用してもよい。
【０１０４】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。
【０１０５】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０１０６】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピディスク，ハードディスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリカード，ＲＯＭなどを用いることができる。
【０１０７】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０８】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０９】
【発明の効果】
以上説明したように、本発明によれば、画像の特徴量の配置を考慮した高速な類似画像の検索が可能となる。
【０１１０】
また、本発明によれば、画像の特徴量の配置を考慮した類似画像の検索を行うとともに撮影条件の変動等による違いを吸収した類似画像検索が可能となる。
【０１１１】
また、本発明によれば、特徴量群を１つのラベルで表し、画像をラベル行列で表現して画像間の類似度を算出することにより類似度の計算量を減少させるので、迅速な類似画像検索が可能となる。
【０１１２】
また、本発明によれば、ラベル行列を適切に管理し、ラベルを用いた画像検索処理の処理速度が著しく向上する。
【０１１３】
また、本発明によれば、元画像と比較先画像の類似度をラベル列もしくはラベル行列の比較によって行う際に、ＤＰマッチングやファジー非決定性オートマトン等のラベル位置の前後の曖昧さを許す手法を適用し、より効果的な類似画像検索が可能となる。
【０１１４】
また、本発明によれば、画像中のある物体（一部分）に着目した類似画像検索が可能となる。
【０１１５】
【図面の簡単な説明】
【図１】本実施形態による画像検索装置の制御構成を示すブロック図である。
【図２】本実施形態の画像検索装置の機能構成を示すブロック図である。
【図３】画像管理データベースのデータ構成例を示す図である。
【図４】ラベル成分インデックスのデータ構成例を示す図である。
【図５】本実施形態による画像登録処理の手順を表すフローチャートである。
【図６】本実施形態による画像のブロック分割例を示す図である。
【図７】本実施形態による多次元特徴量空間を説明する図である。
【図８】ラベル列を生成する際のブロック順序例を説明する図である。
【図９】本実施形態による画像検索の手順を説明するフローチャートである。
【図１０】本実施形態による、特徴部分ラベル行列の抽出手順を説明するフローチャートである。
【図１１】ラベル列を比較し類似度を求める際に用いるラベル間のペナルティマトリックスの一例を示す図である。
【図１２】類似検索元画像のラベル列と類似検索先画像のラベル列の一例を示す図である。
【図１３】一次元のＤＰマッチングを説明する図である。
【図１４】ＤＰマッチングの傾斜制限を説明する図である。
【図１５】本実施形態による類似度算出処理を説明する図である。
【図１６】本実施形態による２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。
【図１７】本実施形態による動的なペナルティー値の設定手順を示すフローチャートである。
【図１８】ＤＰマッチングにおける整合窓を説明する図である。
【図１】
0003952592.tif 000003
【図２】
0003952592.tif 000004
【図３】
0003952592.tif 000005
【図４】
0003952592.tif 000006
【図５】
0003952592.tif 000007
【図６】
0003952592.tif 000008
【図７】
0003952592.tif 000009
【図８】
0003952592.tif 000010
【図９】
0003952592.tif 000011
【図１０】
0003952592.tif 000012
【図１１】
0003952592.tif 000013
【図１２】
0003952592.tif 000014
【図１３】
0003952592.tif 000015
【図１４】
0003952592.tif 000016
【図１５】
0003952592.tif 000017
【図１６】
0003952592.tif 000018
【図１７】
0003952592.tif 000019
【図１８】
0003952592.tif 000020