JP3720573B2 - 画像検索装置及び方法 - Google Patents
画像検索装置及び方法 Download PDFInfo
- Publication number
- JP3720573B2 JP3720573B2 JP09013398A JP9013398A JP3720573B2 JP 3720573 B2 JP3720573 B2 JP 3720573B2 JP 09013398 A JP09013398 A JP 09013398A JP 9013398 A JP9013398 A JP 9013398A JP 3720573 B2 JP3720573 B2 JP 3720573B2
- Authority
- JP
- Japan
- Prior art keywords
- label
- image
- image data
- search
- matching
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Processing Or Creating Images (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、画像を検索する画像検索装置及び方法に関するものである。
【０００２】
【従来の技術】
従来より類似画像を検索するための種々の技術が提案されている。類似画像検索を自然画像について行うための、ある程度実用化されている技術では、色情報を画像特徴量として用いているものが多い。そして、その多くが、色情報に関するヒストグラムを取ることにより、ＲＧＢの割合や画像中に多く存在する色の組み合わせを用いて検索を行うものである。
【０００３】
【発明が解決しようとする課題】
しかしながら、上記の手法では、色の位置情報が失われてしまうためにその検索精度は必ずしも高くなかった。また、例えば特開平８−２４９３４９号には、画像を複数のブロックに分け夫々の特徴量（代表色）を用いたパターンマッチングが開示されている。しかしながら、この手法では、マッチングを行う２つの画像について各ブロック間の特徴量の距離を計算しなければならず、膨大な計算量が必要となってしまう。特に特徴量として代表色を用いると、ＲＧＢ３個のデータを扱わなければならず、更に計算が複雑なものとなる。また、特徴量そのものを用いて比較を行うので、比較の精度が高くなる反面、画像のアングルが変ったり、物体の位置が変ったりするだけで類似画像検索できなくなってしまうといった問題がある。すなわち、画像のアングルが変ったり、物体の位置が変ったり、あるいは撮影条件による画像特徴量のある程度の違い等を吸収するなど、ある程度の曖昧さを有しながらも適切に画像検索を行うという、いわゆるロバストな類似画像検索を行うことはできなかった。
【０００４】
従って、従来技術において自然画像を検索する場合には、画像にキーワードを付与しておき、このキーワードによって画像検索を行うことが普通であった。しかし、このキーワード付け作業は人手のかかる作業であり、更に、キーワード付けが行われていない画像に関しては、縮小画を提示してマニュアルにて選択するという作業が生じ、検索操作を煩雑なものとしていた。
【０００５】
本発明は上記の問題点に鑑みてなされたものであり、画像の特徴量の配置を考慮した高速な類似画像の検索を可能とする画像検索装置及び方法を提供することを目的とする。
【０００６】
また、本発明の他の目的は、画像の特徴量の配置を考慮した類似画像の検索を行うとともに、撮影条件の変動等による違いを吸収した類似画像検索を可能とする画像検索装置及び方法を提供することにある。
【０００７】
また、本発明の他の目的は、特徴量群を１つのラベルで表し、画像をラベル列もしくはラベル行列で表現して画像間の類似度を算出することにより類似度の計算量を減少させ、迅速な類似画像検索を可能とすることにある。
【０００８】
また、本発明の他の目的は、ラベル列もしくはラベル行列を適切に管理し、ラベルを用いた画像検索処理の処理速度を著しく向上することにある。
【０００９】
また、本発明の他の目的は、元画像と比較先画像の類似度をラベル列もしくはラベル行列の比較によって行う際に、ＤＰマッチングやファジー非決定性オートマトン等のラベル位置の前後の曖昧さを許す手法を適用し、より効果的な類似画像検索を可能とすることにある。
【００１０】
【課題を解決するための手段】
上記の目的を達成するための本発明の画像検索装置は以下の構成を備える。即ち、
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与する付与手段と、
前記付与手段で付与されたラベルを所定のブロック順序に基づいて並べることによりラベル列を生成する生成手段と、
前記生成手段で生成されたラベル列を前記画像データに対応付けて記憶する第１記憶手段と、
前記生成されたラベル列に基づいて、前記画像データをラベルをキーとして、ラベル毎に当該ラベルを含む画像データを示す画像ＩＤを登録するとともに、各画像データにおける当該ラベルの含有数を登録するインデックステーブルを記憶する第２記憶手段と、
検索元となる検索元画像データが与えられた場合、該検索元画像データに対応するラベル列を獲得し、前記インデックステーブルに登録されている画像ＩＤとラベルの含有数とに基づき、該獲得されたラベル列に類似する画像データ群を抽出する抽出手段と、
前記抽出手段で抽出された画像データ群のそれぞれについて、前記第１記憶手段に記憶されたラベル列に基づいて前記検索元画像データに対応する画像データの検索を行う検索手段とを備える。
【００１１】
また、本発明の他の形態によれば、上記画像検索装置に対応する画像検索方法、及び該画像検索方法を実現するための制御プログラムを格納する記憶媒体が提供される。
【００１２】
【発明の実施の形態】
以下、添付の図面を参照して本発明の好適な一実施形態を説明する。
【００１３】
［第１の実施形態］
図１は第１の実施形態による画像検索装置の制御構成を示すブロック図である。同図において、１０１はＣＰＵであり、本実施形態の画像検索装置における各種制御を実行する。１０２はＲＯＭであり、本装置の立ち上げ時に実行されるブートプログラムや各種データを格納する。１０３はＲＡＭであり、ＣＰＵ１０１が処理するための制御プログラムを格納するとともに、ＣＰＵ１０１が各種制御を実行する際の作業領域を提供する。１０４はキーボード、１０５はマウスであり、ユーザによる各種入力操作環境を提供する。
【００１４】
１０６は外部記憶装置であり、ハードディスクやフロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ等で構成される。１０７は表示器である。１０８はネットワークインターフェースであり、ネットワーク上の各機器との通信を可能とする。１０９はインターフェース、１１０は画像読み取りのためのスキャナである。また、１１１は上記の各構成を接続するバスである。なお、後述の各フローチャートに示される処理を実現する制御プログラムは、ＲＯＭ１０２に格納されていてもよいし、外部記憶装置１０６よりＲＡＭ１０３にロードされてもよい。
【００１５】
なお、上記の構成においてスキャナ１１０や外部記憶装置１０６はネットワーク上に配置されたもので代用してもよい。
【００１６】
図２は第１の実施形態の画像検索装置の機能構成を示すブロック図である。同図において、１１はユーザインターフェース部であり、表示器１０７、キーボード１０４及びマウス１０５を用いて、ユーザからの各種の操作入力を検出する。１２は画像入力部であり、スキャナ１１０による画像の読み取りを行う。１３は画像メモリであり、画像入力部１２によって得られたイメージデータをＲＡＭ１０３の所定の領域に格納する。１４は画像特徴量抽出部であり、画像メモリ１３に格納した画像について、後述の手順で特徴量を抽出する。１５は特徴量ラベル列化部であり、画像特徴量抽出部１４によって得られた特徴量に基づいてラベル列を生成する。１６はパターンマッチング部であり、指定された画像のラベル列と、画像蓄積部１７に蓄積されている画像のラベル列に基づいて、両者の類似度を算出し、類似画像を検索する。
【００１７】
１７は画像蓄積部であり、画像入力部１２等によって得られた画像データを蓄積する。図３は画像蓄積部１７における画像データの格納状態を説明する図である。各画像データ１１２には画像ＩＤ１１１が付与され、画像蓄積部１７にはこれらが対になって保持される。１８は画像管理データベース（以下、画像管理ＤＢ）であり、図８で示されるデータ形態で画像蓄積部１７に格納された画像データを管理する。また、１９はラベル列インデックスであり、図１０に示されるラベル成分インデックスファイルを格納する。なお、ラベル成分インデックスの利用については、図９のフローチャートにより後述する。
【００１８】
以上のような構成を備えた本実施形態の画像検索装置の動作例を以下に説明する。なお、以下の例では色に着目した画像特徴量として、赤（Ｒ）、緑（Ｇ）、青（Ｂ）の三色を採用し、３次元の色空間での処理を用いて説明する。
【００１９】
［画像の登録処理］
先ず画像登録の際に行う処理を説明する。図４は第１の実施形態による画像登録処理の手順を表すフローチャートである。まず、ステップＳ１１において、ユーザーインターフェース部１１を介したユーザの指示により、画像入力部１２を用いた画像を読み込み、画像メモリ１３に保持する。次に、ステップＳ１２において、この画像を複数のブロックに分割する。本実施形態では、画像を縦横の複数ブロックに分割する。図５は本実施形態による画像のブロック分割例を示す図である。同図に示されるように、本実施形態では、説明のため３×３の計９個のブロックに画像を分割するものとする。次にステップＳ１３において、分割された各ブロックの特徴量を算出し、得られた特徴量を次の手順でラベル化する。
【００２０】
なお、本実施形態で用いる３×３への分割はあくまで説明のためのものである。実際には、自然画であれば１０×１０以上の分割数とするのが好ましい。また、白の無地背景に商品が写っているような場合であれば、１３×１３以上の分割数とするのが好ましい。
【００２１】
図６は本実施形態による多次元特徴量空間を説明する図である。図６に示すように、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロック（色ブロック）、即ちセル（色セル）に分割し、夫々のセル（色セル）に対して通し番号でユニークなラベルを付与する。ここで、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロックに分けたのは微妙な特徴量（色）の違いを吸収するためである。
【００２２】
なお、多次元特徴量空間に関しては、画像特徴量をそのまま用いるものではなく各パラメータを平均と分散を実験によって求め規格化（正規化）した後、例えば、主成分分析等の直交変換を行い、意味のある次元にしたものを用いることが考えられる。なお、「意味のある次元」とは、主成分分析において、寄与率が大きな主成分軸で構成される次元である。
【００２３】
ステップＳ１３では、ステップＳ１２で得られた各分割ブロックに対して、定められた画像特徴量計算処理を行い、上記多次元特徴量空間上のどのセルに属するかを求め、対応するラベルを求める。この処理を全てのブロックに対して行う。すなわち、分割画像ブロックに対して、全ての画素がどの色セルに属するかの計算処理を行い、もっとも頻度の多い色セルのラベルをその分割画像ブロックのパラメータラベル（カラーラベル）として決定し、この処理を全てのブロックに対して行う。
【００２４】
以上のようにして各ブロックに対してパラメータラベルが付与されると、ステップＳ１４において、各ブロックに付与されたパラメータラベルを所定のブロック順序で並べることにより、パラメータラベル列（以下、ラベル列とする）が生成される。図７はラベル列を生成する際のブロック順序例を説明する図である。同図の分割画像ブロックの升にある数字に従って上記のパラメータラベルを並べ、ラベル列を作る。
【００２５】
ここで、図７の（ａ）では、分割ブロックを右上から左下方向への斜め方向へスキャンしている。これは、比較する画像のアングルの微妙な違い、ずれの影響を少なくするために類似検索対象物体に沿ってなるべく多く連続したラベル列を高い期待値で得るためである。この結果、後で述べるパターンマッチング部１６の作用とあいまって、上下左右のどちらのずれに対しても影響の少ないラベル列同士の比較が可能となる。
【００２６】
なお、本実施形態に適用可能なスキャンの方法としては、
・水平方向（左から右へのスキャンを上から下へ行う、左から右へのスキャンを下から上へ行う等、４通りのスキャン方法が考えられる）、
・垂直方向（上から下へのスキャンを左から右へ行う等、４通りのスキャン方法が考えられる）、
・斜め方向（四隅の各始点について２方向の斜めスキャンがあり、図７の（ａ）〜（ｃ）を含む８通りのスキャン方法がある）、
・ジグザグスキャン（ＪＰＥＧ等において採用されているスキャン方法であり、四隅の各始点について２通りのジグザグスキャンがあり、合計８通りのスキャンがある）、
等があげられる。本実施形態では以下の観点から採用すべきスキャン方法を決定する。すなわち、
（１）本実施形態ではラベル列同士の時系列的な比較であり、この順序に逆転が生じることは好ましくない。よって、すべての画像を所定のスキャン方法でスキャンしてラベル列化を行う必要がある。
（２）位置の近いブロックはラベル列中においても近くに位置することが望ましい。
（３）検索したい物体に引っ掛かるブロックのラベルが出来る限り早く現れ、且つ長く続くことがマッチングを行いやすくする。
（４）物体が動いたり、アングルが変わったりしても、ラベルの並びが極端に変わらないようにする。
という条件を満足するスキャン方法を採用する。特に、着目物体の多くが画像中央であることを仮定すると、着目物体を含むブロックが出来るだけスキャンの早いうちに現れ、長くその着目物体をスキャンする期待値が高い方法として、本実施形態では斜め方向のスキャンを採用している。なお、本実施形態では、図７の（ａ）のような右上から左下方向への斜めスキャンを採用するが、当然、図７の（ｂ）のような例や図７の（ｃ）の様なスキャン方法を採用してもよい。
【００２７】
続いてステップＳ１５において、以上のようにして得たラベル列や画像データを画像蓄積部１７、画像管理ＤＢ１８、ラベル列インデックス１９に格納する。すなわち、ステップＳ１１で読み込んだ画像データに対して画像ＩＤを取得し、これらをペアにして画像蓄積部１７に格納する。そして、当該画像ＩＤに対応付けて図８に示す画像管理ＤＢレコードを生成し、これを画像管理ＤＢ１８に登録する。
【００２８】
以上が画像登録時に行われる処理である。
【００２９】
［類似画像検索処理］
次に図９のフローチャートに従って類似画像検索の処理を説明する。図９は第１の実施形態による類似画像検索の処理手順を説明するフローチャートである。なお、第１の実施形態では、予め初期化時において、画像管理ＤＢのラベル系列から、既に登録されている画像のラベル列群を得て、各ラベル成分をキーとするラベル成分インデックスファイル（図１０）を生成し、ラベル列インデックス１９に格納しておく。なお、ここでいう初期化時とは、システムの立ち上げ時或いはアプリケーションの起動時のいずれでも良い。また、新規の画像登録があり、これを画像ＤＢに登録した場合にも、このラベル成分インデックスの生成を行う。図１０は、ラベル成分インデックスのデータ構成例を示す図である。図１０に示すように、ラベル成分インデックスには、各ラベル成分毎に、そのラベルを内部に持つラベル列へのアドレス群（列ＩＤ群）を有する。なお、このラベル成分インデックスファイルは画像の登録及び削除、変更を反映する必要が生じるまで、作成し直す必要はない。もちろん、毎回画像データの登録時にラベル成分インデックスを追記してゆく方法も存在する。この場合は、図４のステップＳ１５の後で、新たに登録された画像について上述した処理を行う。
【００３０】
図１０に示すラベル成分インデックスには、ラベル成分をキーとして、そのラベル成分を含む画像ＩＤとそれに含まれる当該ラベルの個数が格納されている。このようなインデックスを用いれば、検索元画像が有するラベル成分を含む画像データの画像ＩＤを直接的に抽出できる。なお、各キー毎に格納されている画像ＩＤを、ラベルの個数にしたがって昇順或いは降順にソートして登録しておけば、より処理速度を向上させることができる。
【００３１】
まず、ステップＳ２１において、ユーザーインターフェース部１１から類似検索元画像が指定されると、ステップＳ２２において、指定された類似検索元画像の画像ＩＤが取得され、更に画像管理ＤＢ１８から当該元画像のラベル列（本例ではカラーラベル列）が取得される。
【００３２】
次にステップＳ２３において、ラベル成分インデックスファイルを参照し、類似検索元画像のラベル列とある程度以上同一のラベルを含むラベル列群（ラベル系列インデックス中のラベル列）を取得する。これは登録した画像の全てのラベル列との比較を行うと処理が遅くなるので、予め似ているものに絞った後に、類似検索元画像のラベル列と一対一で比較するようにし、処理速度を改善するためである。なお、類似したラベル列とは、類似検索元画像のラベル列と所定数以上の同一もしくは類似のラベルを含むラベル列群をいう。ここで、類似のラベルとは後述の図１１のラベル間ペナルティの小さいラベル同士をいう。もちろん、処理が遅くなっても良ければ、登録した画像の全てのラベル列との比較を行い、精度の高い検索を行ってもよい（この場合、ステップＳ２３は省略される）。
【００３３】
なお、上述のラベル成分インデックスファイルを用いた画像の絞り込み方としては、次のような方法が考えられる。例えば、本例では９個のラベルからなるラベル列が用いられるが、このラベル列の中央部の３つのラベル（４番目から６番目のラベル）を含む画像を抽出する。一般に、画像の中央部に当該画像の特徴的な情報が存在するからである。
【００３４】
次に、ステップＳ２４において、ステップＳ２３で取得した各ラベル列と類似検索元画像のラベル列とを比較し、その類似度を算出する。そして、類似検索元画像のラベル列に最も近いラベル列から順にその類似度とともに検索結果として出力する。
【００３５】
ここで、ラベル列同士の類似比較（類似度の算出）を行う方法について述べる。
【００３６】
図１１はラベル列を比較し類似度を求める際に用いるラベル間のペナルティマトリックスの一例を示す図である。マトリクス中の値が小さい程類似していることになる。例えば、ラベル２とラベル６のペナルティは「７」である。また、同じラベル同士のペナルティは当然のことながら「０」となっている。本マトリクスの使用目的はラベルの類似に応じた距離判定を行うことにある。すなわち、本実施形態では、特徴量空間としてＲＧＢカラー空間を用いているので、色の類似に応じた距離判定が行えることになる。
【００３７】
例えば、検索元画像と検索対象画像のラベル列中のそれぞれ対応する位置のラベルの値から図１１のペナルティマトリクスを参照して距離を求め、ラベル列中の全ラベルについての距離の和を求めることで、両ラベル列間の距離を得る。例えば、図１２に示す例では、検索元画像のラベル列が「１１２３１３４４１」であり、検索対象画像のラベル列が「１１３２２４４５２」であるので、図１１のペナルティマトリクスを用いてＤＰマッチングを行うことにより、図１３に示されるように距離（最終解）が求まる。なお、この例では、傾斜制限として次の条件を用いている。すなわち、図１４において、格子点(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）を以下の漸化式によって求めている。
【００３８】
【数１】
【００３９】
以上のように、ラベル間のパターンマッチングの際に隣接するセル同士ではペナルティ（距離）を小さくし、遠いものには大きなペナルティを与えるために図１１に示すようなラベル間でのペナルティマトリックスを導入する。ステップＳ２４ではこのペナルティマトリックスを考慮し、ラベル列同士を比較するが、その際に、オートマトン等のラベルシーケンスを曖昧に比較できるマッチングを行うようにしてもよい。このような曖昧化の手法を用いることにより、余分なラベルの付加、ラベルの欠落や同じラベルの繰り返しに対しては低いペナルティが与えられとともに、ラベル間のペナルティには図１２のカラーラベル間のペナルティマトリックスを用いてラベル列同士の距離計算を行うことで、曖昧なパターンマッチングが行えるようになる。なお、オートマトンとしては、「特開平８−２４１３３５のファジー非決定性有限オートマトンを使用した曖昧な文字列検索方法およびシステム」に記載されている「ファジー非決定性有限オートマトン」を適用することができる。このオートマトンでは、各シンボル間の距離（ペナルティー）が多値でして出来、なお、比較するラベル位置を前後曖昧に移動することが出来、トータルの距離が最小（類似度が最大）となるようなラベル列の比較を実現するための手法として、上述のオートマトンの他に、音声認識等において用いられているＤＰマッチングがあり、この手法も本実施形態に好適に適用できるものである。
【００４０】
更に、上述の曖昧なパターンマッチングに加えて、図７の（ａ）〜（ｃ）のブロック順序の規則を併用することにより、比較する画像のアングルの微妙な違いやずれの影響を少なく、上下左右のどちらのずれに対しても影響の少ないカラーラベル列同士の比較を行うことが可能となる。すなわち、ＤＰマッチングやファジー非決定性オートマトンは、ラベル列の前後の曖昧さを許容するマッチングであり、画像の位置ずれの影響を吸収する性質を有する。また、アングルの違い等により物体の位置が変わり、ブロックによって切りとられる物体の位置が変わることにより、ブロックの色合いも微妙に異なることが予想されるが、この違いは上述のペナルティーマトリクスにより吸収されることになる。このように、ＤＰマッチング或いはファジーオートマトンによる曖昧さを許容するマッチングと、ペナルティーマトリクスによる特徴量の曖昧さの許容との相乗効果によって、上下左右のずれに対して影響の少ないマッチングを可能としている。更に、図７（ａ）〜（ｃ）のような斜めスキャンにより、物体の位置の変化によるラベル位置の変化が低減されるので、より効果的にマッチング時の物体のずれの影響を低減できる。
【００４１】
次に、ステップＳ２５において、画像管理ＤＢ１８を参照して、画像ＩＤ群の各画像ＩＤについてフルパスのファイル名を取得し、これをユーザに提示する。
【００４２】
以上のような処理により、画像のアングルが変ったり、物体の位置が変ったり、あるいは撮影条件が変わったりすることによって生じる、色のある程度の違い等を吸収するなど、ロバストな類似画像検索を高速に行うことが可能となる。
【００４３】
なお、ブロック化できない１つの画像に対して１つのパラメータを加味した類似検索の場合には、本発明で得られる類似度（ペナルティの総和を用いて作る）を１つの新たなる特徴量として、統計的な距離尺度に基づく検索を行うことも可能である。また、上記実施形態では、類似度が所定値を越える類似画像を検索結果として得るが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよいことはいうまでもない。
【００４４】
以上説明したように、第１の実施形態によれば、特徴量群（特徴量空間を分割して得られる特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル同士の類似度に基づく距離をペナルティーマトリクスによって与える。このため、２つの画像のブロック間の距離の計算量を大幅に減少させることができるとともに、類似した特徴量が同じラベルで表されることになるので、類似画像の検索を良好に行うことができる。
【００４５】
また、（１）ペナルティマトリクスによるラベル同士の距離概念を導入し、（２）ＤＰマッチングやファジー非決定性オートマトン等の、比較するラベル位置を前後曖昧に移動させることが出来、トータルの距離が最小（類似度が最大）となるようなラベル列の比較を実現する手法を導入する、ことにより、画像のアングルが多少変わっても検索することが可能となり、雰囲気の似ている画像を検索できるようになる。
【００４６】
更に上記実施形態によれば、インデックスデータベース（ラベル成分インデックス（図１０））を用いたことにより、画像検索が更に高速化する。
【００４７】
［第２の実施形態］
上記第１の実施形態では、特徴量を表すラベルを１次元に並べて、すなわちラベル列として類似画像検索を行った。第２の実施形態では、特徴量を表すラベルの２次元配置を考慮して、すなわちラベル行列を用いて類似画像検索を行う。なお、第２の実施形態による画像検索装置の制御構成は、第１の実施形態（図１）と同様であるのでここでは説明を省略する。
【００４８】
図１５は本実施形態の画像検索装置の機能構成を示すブロック図である。同図において、ユーザインターフェース部１１、画像入力部１２、画像メモリ１３、画像特徴量抽出部１４、画像蓄積部１７は第１の実施形態（図２）と同様の構成である。
【００４９】
１５ａは特徴量ラベル行列化部であり、画像特徴量抽出部１４によって得られた特徴量に基づいてラベル行列を生成する。１６ａはパターンマッチング部であり、指定された画像のラベル行列と、画像蓄積部１７に蓄積されている画像のラベル行列に対し、後述の２次元ＤＰマッチングを用いて類似度を算出する。１８ａは画像管理データベース（以下、画像管理ＤＢ）であり、図１６で示すデータ形態で画像蓄積部１７に格納された画像データを管理する。また、１９ａはラベル行列インデックスであり、図１０で示したラベル成分インデックスファイルを格納する。
【００５０】
以上のような構成を備えた第２の実施形態の画像検索装置の動作例を以下に説明する。なお、以下の例では色に着目した画像特徴量として、赤（Ｒ）、緑（Ｇ）、青（Ｂ）の三色を採用し、３次元の色空間での処理を用いて説明する。
【００５１】
［画像の登録処理］
図１７は第２の実施形態による画像登録処理の手順を示すフローチャートである。図１７において、ステップＳ１１〜Ｓ１３は第１の実施形態（図４）で説明した処理と同様である。
【００５２】
ステップＳ１１〜Ｓ１３の処理により、各ブロックに対してパラメータラベルが付与されると、ステップＳ１４ａにおいて、各ブロックに付与されたパラメータラベルを所定のブロック順序で並べることにより、パラメータラベル行列（以下、ラベル行列とする）が生成される。図１８はラベル行列を生成する際のブロック順序例を説明する図である。同図の分割画像ブロックの升にある数字に従って上記のパラメータラベルを並べ、ラベル行列を作る。なお、画像管理データベース１８ａやラベル行列インデックス１９ａにラベル行列を格納するに際しては、上述のように２次元的なラベル行列を所定の順序で１次元に並べたものを格納するが、本実施形態ではこのような１次元の形態のものもラベル行列と称することにする。
【００５３】
ここで、図１８の（ａ）では、分割ブロックを左から右へ水平方向へスキャンし、この水平方向のスキャンを上から下へ行う順序となっている。なお、本実施形態に適用可能なスキャンの方法としては、
・水平方向（図１８の（ａ）に示したように、左から右へのスキャンを上から下へ行うという順序の他に、図１８の（ｂ）〜（ｄ）に示すように、左から右へのスキャンを下から上へ行う等、４通りのスキャン方法がある）、
・垂直方向（上から下へのスキャンを左から右へ行う等、４通りのスキャン方法が考えられる）、
・図１８（ｅ）に示すように、偶数ラインと奇数ラインでスキャンを分ける。
【００５４】
なお、第２の実施形態では、図１８の（ａ）に示すスキャン方法を採用するが、上述した他のスキャン方法も適用可能である。
【００５５】
続いてステップＳ１５ａにおいて、以上のようにして得たラベル行列や画像データを画像蓄積部１７、画像管理ＤＢ１８ａ、ラベル行列インデックス１９ａに格納する。すなわち、ステップＳ１１で読み込んだ画像データに対して画像ＩＤを取得し、これらをペアにして画像蓄積部１７に格納する。そして、当該画像ＩＤに対応付けて図１６に示す画像管理ＤＢレコードを生成し、これを画像管理ＤＢ１８ａに登録する。
【００５６】
以上が画像登録時に行われる処理である。
【００５７】
［類似画像検索処理］
次に図１９のフローチャートに従って類似画像検索の処理を説明する。図１９は第２の実施形態による類似画像検索の処理手順を説明するフローチャートである。なお、本実施形態では、予め初期化時において、画像管理ＤＢのラベル系列から、既に登録されている画像のラベル行列群を得て、各ラベル成分をキーとするラベル成分インデックスファイルを生成し、ラベル行列インデックス１９ａに格納しておく。なお、ここでいう初期化時とは、システムの立ち上げ時或いはアプリケーションの起動時のいずれでも良い。また、新規の画像登録があり、これを画像ＤＢに登録した場合にも、このラベル成分インデックスの生成を行う。
【００５８】
本実施形態においても、第１の実施形態で説明したラベル成分インデックス（図１０）を用いる。すなわち、ラベル成分インデックスには、各ラベル成分毎に、そのラベルを内部に持つラベル行列へのアドレス群（列ＩＤ群）が登録される。なお、このラベル成分インデックスファイルは画像の登録及び削除、変更を反映する必要が生じるまで、作成し直す必要はない。もちろん、第１の実施形態で述べたように、毎回登録時にラベル成分インデックスを追記してゆく方法も存在する。
【００５９】
まず、ステップＳ２１において、ユーザーインターフェース部１１から類似検索元画像が指定されると、ステップＳ２２ａにおいて、指定された類似検索元画像の画像ＩＤが取得され、更に画像管理ＤＢ１８から当該元画像のラベル行列（本例ではカラーラベル行列）が取得される。
【００６０】
次にステップＳ２３ａにおいて、ラベル成分インデックスファイルを参照し、類似検索元画像のラベル行列とある程度以上同一のラベルを含むラベル行列群（ラベル系列インデックス中のラベル行列）を取得する。これは登録した画像の全てのラベル列との比較を行うと処理が遅くなるので、予め似ているものに絞った後に、類似検索元画像のラベル行列と一対一で比較するようにし、処理速度を改善するためである。なお、類似したラベル行列とは、類似検索元画像のラベル行列と所定数以上の同一もしくは類似のラベルを含むラベル行列群をいう。ここで、類似のラベルとは図１１で説明したラベル間ペナルティの小さいラベル同士をいう。もちろん、処理が遅くなっても良ければ、登録した画像の全てのラベル行列との比較を行い、精度の高い検索を行ってもよい（この場合、ステップＳ２３ａは省略される）。
【００６１】
次に、ステップＳ２４ａにおいて、ステップＳ２３ａで取得した各ラベル行列と類似検索元画像のラベル行列とを比較し、その類似度を算出する。そして、類似検索元画像のラベル行列に最も近いラベル行列から順にその類似度とともに検索結果として出力する。
【００６２】
ここで、ラベル行列同士の類似比較（類似度の算出）を行う方法について述べる。なお、以下では、ステップＳ２３ａで取得したラベル行列を類似比較先画像と称する。
【００６３】
また、第２の実施形態においてもラベル行列を比較して類似度を求める際には、第１の実施形態と同様にラベル間のペナルティマトリックス（図１１）を用いる。
【００６４】
ラベル間のパターンマッチングの際に隣接するセル同士ではペナルティ（距離）を小さくし、遠いものには大きなペナルティを与えるために図１２に示すようなラベル間でのペナルティマトリックスを導入する。ステップＳ２４ａではこのペナルティマトリックスを考慮し、ラベル行列同士を比較するが、第２の実施形態では、その際に以下に説明する２次元的なＤＰマッチング（以下、２次元ＤＰマッチングという）を使用する。
【００６５】
図２０は本実施形態による類似度算出処理を説明する図である。上述のステップＳ２２ａにおいて取得された類似検索元画像のラベル行列は、そのスキャン方法に従って図２０の（ｂ）のように並べることができる。また、ステップＳ２３ａにおいて抽出されたラベル行列群のうちの一つを類似検索元画像とすると、そのラベル行列は図２０（ａ）のように並べることができる。
【００６６】
まず、類似比較先画像の第１行目のラベル列「ａｂｃ」と、類似検索元画像の第１〜第３行目のラベル列（「１２３」、「４５６」、「７８９」）のそれぞれとの距離をＤＰマッチングによって求め、その距離が最少となるラベル列の類似検索元画像における行番号を類似ライン行列（図２０の（ｃ））の該当する位置に記憶する。また、得られた最小距離が所定の閾値よりも大きい場合には、どの行とも類似していないと判断し、類似ライン行列の該当する位置に「！」を記憶する。ＤＰマッチングの性質により、たとえば画像のアングルが水平方向へ多少変わっていたとしても、上記処理により類似する行（ライン）を検出可能である。以上の処理を、類似比較先画像の全ての行（「ｄｅｆ」「ｇｈｉ」）について行うことで、図２０の（ｃ）のような列方向の類似ライン行列が得られる。
【００６７】
図２０の（ｃ）では、「ａｂｃ」に類似した行が類似検索元画像に存在せず、「ｄｅｆ」に類似した行が類似検索元画像の第１行目、「ｇｈｉ」に類似した行が類似検索元画像の第２行目であったことを示している。以上のようにして得られた類似ライン行列と標準ライン行列（類似検索元画像の行の並びであり、本例では「１２３」となる）との類似度をＤＰマッチングを用いて算出し、これを当該類似検索元画像と当該類似比較先画像との類似度として出力する。なお、ＤＰマッチングでは、周知のように、比較するラベルシーケンスが最も類似距離が小さくなるように、比較するラベルシーケンスを伸縮（比較する相手を次に進めないで我慢する）させて比較するという処理を行う。また、何処まで伸縮（我慢）できるかを制約条件（整合窓の幅）で与えることも可能である。
【００６８】
図２１は第２の実施形態による、２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。上記図２０を参照して説明した処理を、図２１のフローチャートを参照して更に説明する。
【００６９】
まず、ステップＳ１０１において、類似比較先画像の行番号を表す変数ｉと、類似検索元画像の行番号を表す変数ｊを１に初期化し、ともに第１行目を示すように設定する。次に、ステップＳ１０２において、類似比較先画像の第ｉ行目のラベル列を取得する。例えば図２０の場合、ｉ＝１であれば「ａｂｃ」が取得される。そして、ステップＳ１０３において、類似検索元画像の第ｊ行目のラベル列を取得する。例えば、図２０において、ｊ＝１であれば、「１２３」が取得される。
【００７０】
次にステップＳ１０４では、上記ステップＳ１０２、Ｓ１０３で得られた２つのラベル列間の距離を、図１２で説明した色セルペナルティーマトリクスを用いて、ＤＰマッチングによって求める。そして、ステップＳ１０５において、ステップＳ１０４で得た距離が、第ｉ行目に関してそれまでに得られた距離の最小値であれば、当該行番号（ｊ）をライン行列要素ＬＩＮＥ［ｉ］に記憶する。
【００７１】
以上のステップＳ１０３からステップＳ１０５の処理を、類似検索元画像の全ての行について行う（ステップＳ１０６、Ｓ１０７）。以上のようにして、類似比較先画像の第ｉ行目のラベル列に対して、類似検索元画像に含まれる行のうち最も距離の近い行の番号がＬＩＮＥ［ｉ］に格納されることになる。
【００７２】
そして、ステップＳ１０８において、上記処理でられたＬＩＮＥ［ｉ］と所定の閾値（Ｔｈｒｅｓｈ）とを比較する。そして、ＬＩＮＥ［ｉ］がＴｈｒｅｓｈ以上であればステップＳ１０９へ進み、いずれの行とも類似していないことを表す「！」をＬＩＮＥ［ｉ］に格納する。
【００７３】
以上説明したステップＳ１０２からＳ１０８の処理を類似比較先画像の全ての行について実行する（ステップＳ１１０、Ｓ１１１）ことにより、ＬＩＮＥ［１］〜ＬＩＮＥ［ｉｍａｘ］が得られるので、これを類似ライン行列ＬＩＮＥ［］として出力する。
【００７４】
次に、ステップＳ１１３において、標準ライン行列「１２…ｉｍａｘ」と類似ライン行列ＬＩＮＥ［］とのＤＰマッチングを行い、両者の距離を算出する。なお、ここで、標準ライン行列とは、１から始まり、列方向に１ずつ増加する行列である。
【００７５】
ここで、標準ライン行列と類似ライン行列間のＤＰマッチングにおいて用いられるペナルティーについて説明する。列方向の類似ライン行列と標準ライン行列とのＤＰマッチングのペナルティーの設定としては２つの方法が考えられる。すなわち、動的なペナルティーと固定的なペナルティーの２つである。
【００７６】
動的なペナルティーとは、動的にライン番号間のペナルティーを設定するものであり、画像によってライン番号間のペナルティーは変化する。本実施形態では、類似検索元画像の自分自身の横（行）方向のラベル行列の距離を求め、これに基づいて各行間のペナルティーを求める。
【００７７】
図２２は第２の実施形態による動的なペナルティー値の設定手順を示すフローチャートである。ステップＳ１２１において、変数ｉを１に、変数ｊを２にそれぞれセットする。次に、ステップＳ１２２において、類似検索元画像の第ｉ行目のラベル列を取得し、ステップＳ１２３において、類似検索もと画像の第ｊ行目のラベル列を取得する。そして、ステップＳ１２４において、類似検索元画像の第ｉ行目のラベル列と第ｊ行目のラベル列とについて、色ペナルティーマトリクスを用いてＤＰマッチングを行い、距離を獲得する。ステップＳ１２５では、ステップＳ１２４で得たＤＰマッチングの距離を、類似検索元画像のｉ行目のラベル列とｊ行目のラベル列間のペナルティーとしてＬＩＮＥ[i][j]に記憶すると共に、、類似検索元画像のｊ行目のラベル列とｉ行目のラベル列間のペナルティーとしてＬＩＮＥ[j][i]に記憶する。
【００７８】
ステップＳ１２６によって、変数ｊの値がｊｍａｘとなるまで、ステップＳ１２３〜Ｓ１２５の処理が繰返される。この結果、第ｉ行目のラベル列について、ｉ＋１〜ｊｍａｘ行目の各ラベル列との間のペナルティー値が決定される。そして、ステップＳ１２８、Ｓ１２９、Ｓ１３０により、ステップＳ１２３〜Ｓ１２６の処理を変数ｉの値がｉｍａｘ−１となるまで繰返される。この結果、ＬＩＮＥ[i]「ｊ］には、ｉ＝ｊの対角成分を除く全てに、上記処理で決定されたペナルティー値が記憶されることになる。
【００７９】
次にステップＳ１３１では、上記処理で決定されていないＬＩＮＥ[i][j]の対角成分のペナルティーを決定する。この部分はｉ＝ｊであり、同一のラベル列であるから、その距離は０であり、従ってペナルティー０が記憶される。また、ステップＳ１３２では、「！」に関してペナルティーを決定する。すなわち、「！」に対するペナルティーは、ＬＩＮＥ[i][j]の全てのペナルティー値の中で、最大のペナルティー値よりもある程度大きな値を設定する。ただし、このペナルティー値を極端に大きくすると、曖昧にヒットする性質が損なわれてしまう。
【００８０】
以上のようにして類似検索元画像に関して計算されたラベル列間のペナルティーを用いて、上記ステップＳ１１３におけるＤＰマッチングを行い、類似度検索元画像と類似比較先画像の類似度を獲得する。
【００８１】
一方、固定的なペナルティーでは、ＤＰマッチングのペナルティーとして、ラベルが一致すればペナルティー「０」を、一致しない場合、もしくは「！」との比較であった場合にはある程度の大きさのペナルティーを与える。この場合は類似検索元画像によらず、常に同じペナルティーとなる。このような固定的なペナルティーを用いてステップＳ１１３の処理を実行し、類似度検索元画像と類似比較先画像の類似度を決定する。
【００８２】
以上説明したマッチング処理は次のような特徴を有する。もし、図２０の（ａ）と（ｂ）が極めて類似していれば、類似ライン行列は「１２３」となり、その距離は０となる。また、類似ライン行列が「！１２」や「２１２」であれば、類似検索元画像に対して類似比較先画像は下方向へずれたものである可能性があるし、類似ライン行列が「２３！」や「２３３」であれば類似検索元画像に対して類似比較先画像が上方向へずれたものである可能性がある。また、類似ライン行列が「１３！」や「！１３」であれば、類似検索元画像に対して類似比較先画像が縮小したものである可能性がある。同様に、類似比較先画像が類似検索元画像を拡大したようなものである場合も検出可能である。
【００８３】
上述のステップＳ１１３で説明したように、類似ライン行列と標準ライン行列との間でＤＰマッチングを行うことにより、垂直方向へのずれが効果的に吸収される。このため、上述したような、上方向や下方向へのずれ、拡大、縮小等に起因する類似検索元画像と類似比較先画像との相違が効果的に吸収され、良好な類似検索を行うことが可能となる。
【００８４】
すなわち、本実施形態の２次元ＤＰマッチングは、ラベル行列の各ラベル列における前後の曖昧さを許容するマッチングであり、画像の位置ずれの影響を吸収する性質を有する。また、アングルの違い等により物体の位置が変わり、ブロックによって切りとられる物体の位置が変わることにより、ブロックの色合いも微妙に異なることが予想されるが、この違いは上述のペナルティーマトリクスにより吸収されることになる。このように、本実施形態の２次元ＤＰマッチングによる曖昧さを許容するマッチングと、ペナルティーマトリクスによる特徴量の曖昧さの許容との相乗効果によって、上下左右拡大、縮小のずれに対しても影響の少ないマッチングを可能としている。
【００８５】
ただし、動的なペナルティーと固定的なペナルティーとでは、動的なペナルティーを用いる方が好ましい。例えば、一面麦畑の類似元検索画像があったとした場合、どのラインも似たようなラベル列となることが考えられる。一方、類似比較先画像にも一面麦畑の画像があったとした場合に、この画像の類似ライン行列には全て最初のライン番号１が入り、「１１１」となってしまう可能性がある。この場合、類似検索元画像のどのラインも似たような画像となっており、ライン番号間のペナルティーが極めて小さくなければ低い距離でのヒットはしない。しかしながら、動的なペナルティーを用いた場合は、ライン番号間のペナルティーが低くなり、類似度の高い結果を得ることができる。
【００８６】
一方、固定的なペナルティーを用いると、「１２３」と「１１１」ではペナルティー値が大きくなり、類似度が低くなってしまう。
【００８７】
ステップＳ２４ａでは、以上説明した類似度の算出処理をステップＳ２３ａで取得した全ラベル行列について行い、得られた類似度を高い順にソートして、ステップＳ２５ａへ進む。ステップＳ２５ａにおいて、画像管理ＤＢ１８ａを参照して、画像ＩＤ群の各画像ＩＤについてフルパスのファイル名を取得し、これをユーザに提示する。
【００８８】
以上のようにして、ＤＰマッチングを水平・鉛直方向、すなわち２次元に行うことにより、水平や鉛直方向、更に斜め方向に画像アングルが変わったり、物体が移動していても検索を行うことが可能である。また、ＤＰマッチングの時系列伸縮特性により、ズームアップ撮影画像やマクロ撮影画像をも検索することが可能となる。
【００８９】
なお、上記実施形態では、水平方向のブロック並びに対応するラベル列を用いて類似ライン行列を得たが、垂直方向のブロック並びに対応するラベル列を用いて類似ライン行列を得るようにすることも、上記と同様の手法で実現可能である。
【００９０】
以上説明したように、第２の実施形態によれば、特徴量群（特徴量空間を分割して得られる特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル同士の類似度に基づく距離を上述の２次元ＤＰマッチングとペナルティーマトリクスによって与える。このため、２つの画像のブロック間の距離の計算量を大幅に減少させることができるとともに、類似した特徴量が同じラベルで表されることになるので、類似画像の検索を良好に行うことができる。
【００９１】
また、（１）ペナルティマトリクスによるラベル同士の距離概念を導入し、（２）比較するラベル位置を前後曖昧に移動させることが出来、トータルの距離が最小（類似度が最大）となるようなラベル行列の比較を実現する上記２次元ＤＰマッチングを導入したことにより、画像のアングルが多少変わっても検索することが可能となり、雰囲気の似ている画像を検索できるようになる。
【００９２】
更に上記実施形態によれば、インデックスデータベース（ラベル成分インデックス）を用いたことにより、画像検索が更に高速化する。
【００９３】
すなわち、上記実施形態によれば、画像の特徴量の配置を考慮した類似画像の高速な検索が行われるとともに、撮影条件の変動等による違いを吸収した類似画像の検索が可能となり、従来難しかった画像のアングルが変ったり、物体の位置が変ったり、あるいは他の撮影条件が変動したりすることによる画像の特徴量のある程度の違いを吸収するなど、ロバストな類似画像検索を行うことが可能となる。
【００９４】
なお、上記各実施形態においては、自然画像検索を行う例を説明したが、本発明はＣＧやＣＡＤ等の人工的な画像の検索にも適応可能な技術であることは当業者には明らかである。
【００９５】
また、上記各実施形態では画像特徴量として色情報を選んだが、本発明はこれに限られるものではなく、その他の画像パラメータを画像分割ブロックごとに求めることで実施することも可能である。
【００９６】
また、上記各実施形態では１つの特徴量での認識の例を挙げたが、その他の特徴量での検索結果との論理演算を行うことにより、複数の特徴量からの高速な検索を行うことも可能である。
【００９７】
１つの画像に対して複数の画像特徴量を用いた検索を行う場合には、本発明で得られる類似度を１つの新たなる画像特徴量とみなし、複数のパラメータを用いた多変量解析を行い統計的な距離尺度を用いた検索を行うことも可能である。また、上記実施形態では、類似度が所定値を越える類似画像を検索結果として得るが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよいことはいうまでもない。
【００９８】
なお、曖昧度を指定することにより、ＤＰマッチングにおけるいわゆる整合窓の幅を変更することにより、検索の曖昧度を所望に設定可能とすることもできる。図２３はＤＰマッチングにおける整合窓を説明する図である。図２３において直線ＡはＪ＝Ｉ＋ｒで表され、直線ＢはＪ＝Ｉ−ｒで表される。整合窓の幅はｒの値を変更することで行える。したがって、キーボード１０４から曖昧度を指定することにより、このｒの値が変更されるように構成すれば、ユーザの所望の曖昧度（整合窓の幅）で類似度検索を行えるようになる。
【００９９】
なお、上記実施形態のような２次元ＤＰマッチングにおいては、水平方向のＤＰマッチングにおける整合窓の幅と、垂直方向のＤＰマッチングにおける整合窓の幅とを別々に設定できるようにしてもよい。或いは、両整合窓が異なる変化率で変化するように構成してもよい。このようにすれば、ユーザは、類似画像検索に際してよりきめ細かい曖昧さの設定を行えるようになる。例えば、図１８で示されたようなブロック順序を用いた場合において、検索元の画像中における注目物体の横方向への移動を許容したいような場合や、検索元の画像が横長画像であるような場合には、横方向への曖昧度を大きくするために水平方向のＤＰマッチングにおける整合窓の幅をより大きくすればよい。
【０１００】
なお、本発明は、例えばホストコンピュータ，インタフェイス機器，リーダ，プリンタなどの複数の機器から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機，ファクシミリ装置など）に適用してもよい。
【０１０１】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。
【０１０２】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０１０３】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピディスク，ハードディスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリカード，ＲＯＭなどを用いることができる。
【０１０４】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０５】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０６】
【発明の効果】
以上説明したように本発明によれば、画像の特徴量の配置を考慮した類似画像の検索が可能となる。
【０１０７】
また、本発明によれば、画像の特徴量の配置を考慮した類似画像の検索が行われるとともに、撮影条件の変動等による違いを吸収した類似画像の検索が可能となり、従来難しかった画像のアングルが変ったり、物体の位置が変ったり、あるいは他の撮影条件が変動したりすることによる画像の特徴量のある程度の違いを吸収するなど、ロバストな類似画像検索を行うことが可能となる。
【０１０８】
また、本発明によれば、特徴量ラベルに基づいて画像データを登録するインデックステーブルを導入することにより、類似度計算の対象とする画像データを効率よく絞り込むことが可能となり、類似検索の処理速度が著しく向上する。
【０１０９】
【図面の簡単な説明】
【図１】第１の実施形態による画像検索装置の制御構成を示すブロック図である。
【図２】第１の実施形態の画像検索装置の機能構成を示すブロック図である。
【図３】画像蓄積部１７における画像データの格納状態を説明する図である。
【図４】第１の実施形態による画像登録処理の手順を表すフローチャートである。
【図５】本実施形態による画像のブロック分割例を示す図である。
【図６】本実施形態による多次元特徴量空間を説明する図である。
【図７】ラベル列を生成する際のブロック順序例を説明する図である。
【図８】第１の実施形態における、画像管理データベースによる画像データの格納形態を説明する図である。
【図９】第１の実施形態による類似画像検索の処理手順を説明するフローチャートである。
【図１０】ラベル成分インデックスのデータ構成例を示す図である。
【図１１】ラベル列を比較し類似度を求める際に用いるラベル間のペナルティマトリックスの一例を示す図である。
【図１２】ＤＰマッチングによるラベル列間の距離の算出を説明する図である。
【図１３】ＤＰマッチングによるラベル列間の距離の算出を説明する図である。
【図１４】ＤＰマッチングによるラベル列間の距離の算出を説明する図である。
【図１５】本実施形態の画像検索装置の機能構成を示すブロック図である。
【図１６】第２の実施形態における、画像管理データベースによる画像データの格納形態を説明する図である。
【図１７】第２の実施形態による画像登録処理の手順を示すフローチャートである。
【図１８】ラベル行列を生成する際のブロック順序例を説明する図である。
【図１９】第２の実施形態による類似画像検索の処理手順を説明するフローチャートである。
【図２０】本実施形態による類似度算出処理を説明する図である。
【図２１】第２の実施形態による、２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。
【図２２】第２の実施形態による動的なペナルティー値の設定手順を示すフローチャートである。
【図２３】ＤＰマッチングにおける整合窓の調整を説明する図である。
【発明の属する技術分野】
本発明は、画像を検索する画像検索装置及び方法に関するものである。
【０００２】
【従来の技術】
従来より類似画像を検索するための種々の技術が提案されている。類似画像検索を自然画像について行うための、ある程度実用化されている技術では、色情報を画像特徴量として用いているものが多い。そして、その多くが、色情報に関するヒストグラムを取ることにより、ＲＧＢの割合や画像中に多く存在する色の組み合わせを用いて検索を行うものである。
【０００３】
【発明が解決しようとする課題】
しかしながら、上記の手法では、色の位置情報が失われてしまうためにその検索精度は必ずしも高くなかった。また、例えば特開平８−２４９３４９号には、画像を複数のブロックに分け夫々の特徴量（代表色）を用いたパターンマッチングが開示されている。しかしながら、この手法では、マッチングを行う２つの画像について各ブロック間の特徴量の距離を計算しなければならず、膨大な計算量が必要となってしまう。特に特徴量として代表色を用いると、ＲＧＢ３個のデータを扱わなければならず、更に計算が複雑なものとなる。また、特徴量そのものを用いて比較を行うので、比較の精度が高くなる反面、画像のアングルが変ったり、物体の位置が変ったりするだけで類似画像検索できなくなってしまうといった問題がある。すなわち、画像のアングルが変ったり、物体の位置が変ったり、あるいは撮影条件による画像特徴量のある程度の違い等を吸収するなど、ある程度の曖昧さを有しながらも適切に画像検索を行うという、いわゆるロバストな類似画像検索を行うことはできなかった。
【０００４】
従って、従来技術において自然画像を検索する場合には、画像にキーワードを付与しておき、このキーワードによって画像検索を行うことが普通であった。しかし、このキーワード付け作業は人手のかかる作業であり、更に、キーワード付けが行われていない画像に関しては、縮小画を提示してマニュアルにて選択するという作業が生じ、検索操作を煩雑なものとしていた。
【０００５】
本発明は上記の問題点に鑑みてなされたものであり、画像の特徴量の配置を考慮した高速な類似画像の検索を可能とする画像検索装置及び方法を提供することを目的とする。
【０００６】
また、本発明の他の目的は、画像の特徴量の配置を考慮した類似画像の検索を行うとともに、撮影条件の変動等による違いを吸収した類似画像検索を可能とする画像検索装置及び方法を提供することにある。
【０００７】
また、本発明の他の目的は、特徴量群を１つのラベルで表し、画像をラベル列もしくはラベル行列で表現して画像間の類似度を算出することにより類似度の計算量を減少させ、迅速な類似画像検索を可能とすることにある。
【０００８】
また、本発明の他の目的は、ラベル列もしくはラベル行列を適切に管理し、ラベルを用いた画像検索処理の処理速度を著しく向上することにある。
【０００９】
また、本発明の他の目的は、元画像と比較先画像の類似度をラベル列もしくはラベル行列の比較によって行う際に、ＤＰマッチングやファジー非決定性オートマトン等のラベル位置の前後の曖昧さを許す手法を適用し、より効果的な類似画像検索を可能とすることにある。
【００１０】
【課題を解決するための手段】
上記の目的を達成するための本発明の画像検索装置は以下の構成を備える。即ち、
画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与する付与手段と、
前記付与手段で付与されたラベルを所定のブロック順序に基づいて並べることによりラベル列を生成する生成手段と、
前記生成手段で生成されたラベル列を前記画像データに対応付けて記憶する第１記憶手段と、
前記生成されたラベル列に基づいて、前記画像データをラベルをキーとして、ラベル毎に当該ラベルを含む画像データを示す画像ＩＤを登録するとともに、各画像データにおける当該ラベルの含有数を登録するインデックステーブルを記憶する第２記憶手段と、
検索元となる検索元画像データが与えられた場合、該検索元画像データに対応するラベル列を獲得し、前記インデックステーブルに登録されている画像ＩＤとラベルの含有数とに基づき、該獲得されたラベル列に類似する画像データ群を抽出する抽出手段と、
前記抽出手段で抽出された画像データ群のそれぞれについて、前記第１記憶手段に記憶されたラベル列に基づいて前記検索元画像データに対応する画像データの検索を行う検索手段とを備える。
【００１１】
また、本発明の他の形態によれば、上記画像検索装置に対応する画像検索方法、及び該画像検索方法を実現するための制御プログラムを格納する記憶媒体が提供される。
【００１２】
【発明の実施の形態】
以下、添付の図面を参照して本発明の好適な一実施形態を説明する。
【００１３】
［第１の実施形態］
図１は第１の実施形態による画像検索装置の制御構成を示すブロック図である。同図において、１０１はＣＰＵであり、本実施形態の画像検索装置における各種制御を実行する。１０２はＲＯＭであり、本装置の立ち上げ時に実行されるブートプログラムや各種データを格納する。１０３はＲＡＭであり、ＣＰＵ１０１が処理するための制御プログラムを格納するとともに、ＣＰＵ１０１が各種制御を実行する際の作業領域を提供する。１０４はキーボード、１０５はマウスであり、ユーザによる各種入力操作環境を提供する。
【００１４】
１０６は外部記憶装置であり、ハードディスクやフロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ等で構成される。１０７は表示器である。１０８はネットワークインターフェースであり、ネットワーク上の各機器との通信を可能とする。１０９はインターフェース、１１０は画像読み取りのためのスキャナである。また、１１１は上記の各構成を接続するバスである。なお、後述の各フローチャートに示される処理を実現する制御プログラムは、ＲＯＭ１０２に格納されていてもよいし、外部記憶装置１０６よりＲＡＭ１０３にロードされてもよい。
【００１５】
なお、上記の構成においてスキャナ１１０や外部記憶装置１０６はネットワーク上に配置されたもので代用してもよい。
【００１６】
図２は第１の実施形態の画像検索装置の機能構成を示すブロック図である。同図において、１１はユーザインターフェース部であり、表示器１０７、キーボード１０４及びマウス１０５を用いて、ユーザからの各種の操作入力を検出する。１２は画像入力部であり、スキャナ１１０による画像の読み取りを行う。１３は画像メモリであり、画像入力部１２によって得られたイメージデータをＲＡＭ１０３の所定の領域に格納する。１４は画像特徴量抽出部であり、画像メモリ１３に格納した画像について、後述の手順で特徴量を抽出する。１５は特徴量ラベル列化部であり、画像特徴量抽出部１４によって得られた特徴量に基づいてラベル列を生成する。１６はパターンマッチング部であり、指定された画像のラベル列と、画像蓄積部１７に蓄積されている画像のラベル列に基づいて、両者の類似度を算出し、類似画像を検索する。
【００１７】
１７は画像蓄積部であり、画像入力部１２等によって得られた画像データを蓄積する。図３は画像蓄積部１７における画像データの格納状態を説明する図である。各画像データ１１２には画像ＩＤ１１１が付与され、画像蓄積部１７にはこれらが対になって保持される。１８は画像管理データベース（以下、画像管理ＤＢ）であり、図８で示されるデータ形態で画像蓄積部１７に格納された画像データを管理する。また、１９はラベル列インデックスであり、図１０に示されるラベル成分インデックスファイルを格納する。なお、ラベル成分インデックスの利用については、図９のフローチャートにより後述する。
【００１８】
以上のような構成を備えた本実施形態の画像検索装置の動作例を以下に説明する。なお、以下の例では色に着目した画像特徴量として、赤（Ｒ）、緑（Ｇ）、青（Ｂ）の三色を採用し、３次元の色空間での処理を用いて説明する。
【００１９】
［画像の登録処理］
先ず画像登録の際に行う処理を説明する。図４は第１の実施形態による画像登録処理の手順を表すフローチャートである。まず、ステップＳ１１において、ユーザーインターフェース部１１を介したユーザの指示により、画像入力部１２を用いた画像を読み込み、画像メモリ１３に保持する。次に、ステップＳ１２において、この画像を複数のブロックに分割する。本実施形態では、画像を縦横の複数ブロックに分割する。図５は本実施形態による画像のブロック分割例を示す図である。同図に示されるように、本実施形態では、説明のため３×３の計９個のブロックに画像を分割するものとする。次にステップＳ１３において、分割された各ブロックの特徴量を算出し、得られた特徴量を次の手順でラベル化する。
【００２０】
なお、本実施形態で用いる３×３への分割はあくまで説明のためのものである。実際には、自然画であれば１０×１０以上の分割数とするのが好ましい。また、白の無地背景に商品が写っているような場合であれば、１３×１３以上の分割数とするのが好ましい。
【００２１】
図６は本実施形態による多次元特徴量空間を説明する図である。図６に示すように、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロック（色ブロック）、即ちセル（色セル）に分割し、夫々のセル（色セル）に対して通し番号でユニークなラベルを付与する。ここで、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロックに分けたのは微妙な特徴量（色）の違いを吸収するためである。
【００２２】
なお、多次元特徴量空間に関しては、画像特徴量をそのまま用いるものではなく各パラメータを平均と分散を実験によって求め規格化（正規化）した後、例えば、主成分分析等の直交変換を行い、意味のある次元にしたものを用いることが考えられる。なお、「意味のある次元」とは、主成分分析において、寄与率が大きな主成分軸で構成される次元である。
【００２３】
ステップＳ１３では、ステップＳ１２で得られた各分割ブロックに対して、定められた画像特徴量計算処理を行い、上記多次元特徴量空間上のどのセルに属するかを求め、対応するラベルを求める。この処理を全てのブロックに対して行う。すなわち、分割画像ブロックに対して、全ての画素がどの色セルに属するかの計算処理を行い、もっとも頻度の多い色セルのラベルをその分割画像ブロックのパラメータラベル（カラーラベル）として決定し、この処理を全てのブロックに対して行う。
【００２４】
以上のようにして各ブロックに対してパラメータラベルが付与されると、ステップＳ１４において、各ブロックに付与されたパラメータラベルを所定のブロック順序で並べることにより、パラメータラベル列（以下、ラベル列とする）が生成される。図７はラベル列を生成する際のブロック順序例を説明する図である。同図の分割画像ブロックの升にある数字に従って上記のパラメータラベルを並べ、ラベル列を作る。
【００２５】
ここで、図７の（ａ）では、分割ブロックを右上から左下方向への斜め方向へスキャンしている。これは、比較する画像のアングルの微妙な違い、ずれの影響を少なくするために類似検索対象物体に沿ってなるべく多く連続したラベル列を高い期待値で得るためである。この結果、後で述べるパターンマッチング部１６の作用とあいまって、上下左右のどちらのずれに対しても影響の少ないラベル列同士の比較が可能となる。
【００２６】
なお、本実施形態に適用可能なスキャンの方法としては、
・水平方向（左から右へのスキャンを上から下へ行う、左から右へのスキャンを下から上へ行う等、４通りのスキャン方法が考えられる）、
・垂直方向（上から下へのスキャンを左から右へ行う等、４通りのスキャン方法が考えられる）、
・斜め方向（四隅の各始点について２方向の斜めスキャンがあり、図７の（ａ）〜（ｃ）を含む８通りのスキャン方法がある）、
・ジグザグスキャン（ＪＰＥＧ等において採用されているスキャン方法であり、四隅の各始点について２通りのジグザグスキャンがあり、合計８通りのスキャンがある）、
等があげられる。本実施形態では以下の観点から採用すべきスキャン方法を決定する。すなわち、
（１）本実施形態ではラベル列同士の時系列的な比較であり、この順序に逆転が生じることは好ましくない。よって、すべての画像を所定のスキャン方法でスキャンしてラベル列化を行う必要がある。
（２）位置の近いブロックはラベル列中においても近くに位置することが望ましい。
（３）検索したい物体に引っ掛かるブロックのラベルが出来る限り早く現れ、且つ長く続くことがマッチングを行いやすくする。
（４）物体が動いたり、アングルが変わったりしても、ラベルの並びが極端に変わらないようにする。
という条件を満足するスキャン方法を採用する。特に、着目物体の多くが画像中央であることを仮定すると、着目物体を含むブロックが出来るだけスキャンの早いうちに現れ、長くその着目物体をスキャンする期待値が高い方法として、本実施形態では斜め方向のスキャンを採用している。なお、本実施形態では、図７の（ａ）のような右上から左下方向への斜めスキャンを採用するが、当然、図７の（ｂ）のような例や図７の（ｃ）の様なスキャン方法を採用してもよい。
【００２７】
続いてステップＳ１５において、以上のようにして得たラベル列や画像データを画像蓄積部１７、画像管理ＤＢ１８、ラベル列インデックス１９に格納する。すなわち、ステップＳ１１で読み込んだ画像データに対して画像ＩＤを取得し、これらをペアにして画像蓄積部１７に格納する。そして、当該画像ＩＤに対応付けて図８に示す画像管理ＤＢレコードを生成し、これを画像管理ＤＢ１８に登録する。
【００２８】
以上が画像登録時に行われる処理である。
【００２９】
［類似画像検索処理］
次に図９のフローチャートに従って類似画像検索の処理を説明する。図９は第１の実施形態による類似画像検索の処理手順を説明するフローチャートである。なお、第１の実施形態では、予め初期化時において、画像管理ＤＢのラベル系列から、既に登録されている画像のラベル列群を得て、各ラベル成分をキーとするラベル成分インデックスファイル（図１０）を生成し、ラベル列インデックス１９に格納しておく。なお、ここでいう初期化時とは、システムの立ち上げ時或いはアプリケーションの起動時のいずれでも良い。また、新規の画像登録があり、これを画像ＤＢに登録した場合にも、このラベル成分インデックスの生成を行う。図１０は、ラベル成分インデックスのデータ構成例を示す図である。図１０に示すように、ラベル成分インデックスには、各ラベル成分毎に、そのラベルを内部に持つラベル列へのアドレス群（列ＩＤ群）を有する。なお、このラベル成分インデックスファイルは画像の登録及び削除、変更を反映する必要が生じるまで、作成し直す必要はない。もちろん、毎回画像データの登録時にラベル成分インデックスを追記してゆく方法も存在する。この場合は、図４のステップＳ１５の後で、新たに登録された画像について上述した処理を行う。
【００３０】
図１０に示すラベル成分インデックスには、ラベル成分をキーとして、そのラベル成分を含む画像ＩＤとそれに含まれる当該ラベルの個数が格納されている。このようなインデックスを用いれば、検索元画像が有するラベル成分を含む画像データの画像ＩＤを直接的に抽出できる。なお、各キー毎に格納されている画像ＩＤを、ラベルの個数にしたがって昇順或いは降順にソートして登録しておけば、より処理速度を向上させることができる。
【００３１】
まず、ステップＳ２１において、ユーザーインターフェース部１１から類似検索元画像が指定されると、ステップＳ２２において、指定された類似検索元画像の画像ＩＤが取得され、更に画像管理ＤＢ１８から当該元画像のラベル列（本例ではカラーラベル列）が取得される。
【００３２】
次にステップＳ２３において、ラベル成分インデックスファイルを参照し、類似検索元画像のラベル列とある程度以上同一のラベルを含むラベル列群（ラベル系列インデックス中のラベル列）を取得する。これは登録した画像の全てのラベル列との比較を行うと処理が遅くなるので、予め似ているものに絞った後に、類似検索元画像のラベル列と一対一で比較するようにし、処理速度を改善するためである。なお、類似したラベル列とは、類似検索元画像のラベル列と所定数以上の同一もしくは類似のラベルを含むラベル列群をいう。ここで、類似のラベルとは後述の図１１のラベル間ペナルティの小さいラベル同士をいう。もちろん、処理が遅くなっても良ければ、登録した画像の全てのラベル列との比較を行い、精度の高い検索を行ってもよい（この場合、ステップＳ２３は省略される）。
【００３３】
なお、上述のラベル成分インデックスファイルを用いた画像の絞り込み方としては、次のような方法が考えられる。例えば、本例では９個のラベルからなるラベル列が用いられるが、このラベル列の中央部の３つのラベル（４番目から６番目のラベル）を含む画像を抽出する。一般に、画像の中央部に当該画像の特徴的な情報が存在するからである。
【００３４】
次に、ステップＳ２４において、ステップＳ２３で取得した各ラベル列と類似検索元画像のラベル列とを比較し、その類似度を算出する。そして、類似検索元画像のラベル列に最も近いラベル列から順にその類似度とともに検索結果として出力する。
【００３５】
ここで、ラベル列同士の類似比較（類似度の算出）を行う方法について述べる。
【００３６】
図１１はラベル列を比較し類似度を求める際に用いるラベル間のペナルティマトリックスの一例を示す図である。マトリクス中の値が小さい程類似していることになる。例えば、ラベル２とラベル６のペナルティは「７」である。また、同じラベル同士のペナルティは当然のことながら「０」となっている。本マトリクスの使用目的はラベルの類似に応じた距離判定を行うことにある。すなわち、本実施形態では、特徴量空間としてＲＧＢカラー空間を用いているので、色の類似に応じた距離判定が行えることになる。
【００３７】
例えば、検索元画像と検索対象画像のラベル列中のそれぞれ対応する位置のラベルの値から図１１のペナルティマトリクスを参照して距離を求め、ラベル列中の全ラベルについての距離の和を求めることで、両ラベル列間の距離を得る。例えば、図１２に示す例では、検索元画像のラベル列が「１１２３１３４４１」であり、検索対象画像のラベル列が「１１３２２４４５２」であるので、図１１のペナルティマトリクスを用いてＤＰマッチングを行うことにより、図１３に示されるように距離（最終解）が求まる。なお、この例では、傾斜制限として次の条件を用いている。すなわち、図１４において、格子点(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）を以下の漸化式によって求めている。
【００３８】
【数１】
以上のように、ラベル間のパターンマッチングの際に隣接するセル同士ではペナルティ（距離）を小さくし、遠いものには大きなペナルティを与えるために図１１に示すようなラベル間でのペナルティマトリックスを導入する。ステップＳ２４ではこのペナルティマトリックスを考慮し、ラベル列同士を比較するが、その際に、オートマトン等のラベルシーケンスを曖昧に比較できるマッチングを行うようにしてもよい。このような曖昧化の手法を用いることにより、余分なラベルの付加、ラベルの欠落や同じラベルの繰り返しに対しては低いペナルティが与えられとともに、ラベル間のペナルティには図１２のカラーラベル間のペナルティマトリックスを用いてラベル列同士の距離計算を行うことで、曖昧なパターンマッチングが行えるようになる。なお、オートマトンとしては、「特開平８−２４１３３５のファジー非決定性有限オートマトンを使用した曖昧な文字列検索方法およびシステム」に記載されている「ファジー非決定性有限オートマトン」を適用することができる。このオートマトンでは、各シンボル間の距離（ペナルティー）が多値でして出来、なお、比較するラベル位置を前後曖昧に移動することが出来、トータルの距離が最小（類似度が最大）となるようなラベル列の比較を実現するための手法として、上述のオートマトンの他に、音声認識等において用いられているＤＰマッチングがあり、この手法も本実施形態に好適に適用できるものである。
【００４０】
更に、上述の曖昧なパターンマッチングに加えて、図７の（ａ）〜（ｃ）のブロック順序の規則を併用することにより、比較する画像のアングルの微妙な違いやずれの影響を少なく、上下左右のどちらのずれに対しても影響の少ないカラーラベル列同士の比較を行うことが可能となる。すなわち、ＤＰマッチングやファジー非決定性オートマトンは、ラベル列の前後の曖昧さを許容するマッチングであり、画像の位置ずれの影響を吸収する性質を有する。また、アングルの違い等により物体の位置が変わり、ブロックによって切りとられる物体の位置が変わることにより、ブロックの色合いも微妙に異なることが予想されるが、この違いは上述のペナルティーマトリクスにより吸収されることになる。このように、ＤＰマッチング或いはファジーオートマトンによる曖昧さを許容するマッチングと、ペナルティーマトリクスによる特徴量の曖昧さの許容との相乗効果によって、上下左右のずれに対して影響の少ないマッチングを可能としている。更に、図７（ａ）〜（ｃ）のような斜めスキャンにより、物体の位置の変化によるラベル位置の変化が低減されるので、より効果的にマッチング時の物体のずれの影響を低減できる。
【００４１】
次に、ステップＳ２５において、画像管理ＤＢ１８を参照して、画像ＩＤ群の各画像ＩＤについてフルパスのファイル名を取得し、これをユーザに提示する。
【００４２】
以上のような処理により、画像のアングルが変ったり、物体の位置が変ったり、あるいは撮影条件が変わったりすることによって生じる、色のある程度の違い等を吸収するなど、ロバストな類似画像検索を高速に行うことが可能となる。
【００４３】
なお、ブロック化できない１つの画像に対して１つのパラメータを加味した類似検索の場合には、本発明で得られる類似度（ペナルティの総和を用いて作る）を１つの新たなる特徴量として、統計的な距離尺度に基づく検索を行うことも可能である。また、上記実施形態では、類似度が所定値を越える類似画像を検索結果として得るが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよいことはいうまでもない。
【００４４】
以上説明したように、第１の実施形態によれば、特徴量群（特徴量空間を分割して得られる特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル同士の類似度に基づく距離をペナルティーマトリクスによって与える。このため、２つの画像のブロック間の距離の計算量を大幅に減少させることができるとともに、類似した特徴量が同じラベルで表されることになるので、類似画像の検索を良好に行うことができる。
【００４５】
また、（１）ペナルティマトリクスによるラベル同士の距離概念を導入し、（２）ＤＰマッチングやファジー非決定性オートマトン等の、比較するラベル位置を前後曖昧に移動させることが出来、トータルの距離が最小（類似度が最大）となるようなラベル列の比較を実現する手法を導入する、ことにより、画像のアングルが多少変わっても検索することが可能となり、雰囲気の似ている画像を検索できるようになる。
【００４６】
更に上記実施形態によれば、インデックスデータベース（ラベル成分インデックス（図１０））を用いたことにより、画像検索が更に高速化する。
【００４７】
［第２の実施形態］
上記第１の実施形態では、特徴量を表すラベルを１次元に並べて、すなわちラベル列として類似画像検索を行った。第２の実施形態では、特徴量を表すラベルの２次元配置を考慮して、すなわちラベル行列を用いて類似画像検索を行う。なお、第２の実施形態による画像検索装置の制御構成は、第１の実施形態（図１）と同様であるのでここでは説明を省略する。
【００４８】
図１５は本実施形態の画像検索装置の機能構成を示すブロック図である。同図において、ユーザインターフェース部１１、画像入力部１２、画像メモリ１３、画像特徴量抽出部１４、画像蓄積部１７は第１の実施形態（図２）と同様の構成である。
【００４９】
１５ａは特徴量ラベル行列化部であり、画像特徴量抽出部１４によって得られた特徴量に基づいてラベル行列を生成する。１６ａはパターンマッチング部であり、指定された画像のラベル行列と、画像蓄積部１７に蓄積されている画像のラベル行列に対し、後述の２次元ＤＰマッチングを用いて類似度を算出する。１８ａは画像管理データベース（以下、画像管理ＤＢ）であり、図１６で示すデータ形態で画像蓄積部１７に格納された画像データを管理する。また、１９ａはラベル行列インデックスであり、図１０で示したラベル成分インデックスファイルを格納する。
【００５０】
以上のような構成を備えた第２の実施形態の画像検索装置の動作例を以下に説明する。なお、以下の例では色に着目した画像特徴量として、赤（Ｒ）、緑（Ｇ）、青（Ｂ）の三色を採用し、３次元の色空間での処理を用いて説明する。
【００５１】
［画像の登録処理］
図１７は第２の実施形態による画像登録処理の手順を示すフローチャートである。図１７において、ステップＳ１１〜Ｓ１３は第１の実施形態（図４）で説明した処理と同様である。
【００５２】
ステップＳ１１〜Ｓ１３の処理により、各ブロックに対してパラメータラベルが付与されると、ステップＳ１４ａにおいて、各ブロックに付与されたパラメータラベルを所定のブロック順序で並べることにより、パラメータラベル行列（以下、ラベル行列とする）が生成される。図１８はラベル行列を生成する際のブロック順序例を説明する図である。同図の分割画像ブロックの升にある数字に従って上記のパラメータラベルを並べ、ラベル行列を作る。なお、画像管理データベース１８ａやラベル行列インデックス１９ａにラベル行列を格納するに際しては、上述のように２次元的なラベル行列を所定の順序で１次元に並べたものを格納するが、本実施形態ではこのような１次元の形態のものもラベル行列と称することにする。
【００５３】
ここで、図１８の（ａ）では、分割ブロックを左から右へ水平方向へスキャンし、この水平方向のスキャンを上から下へ行う順序となっている。なお、本実施形態に適用可能なスキャンの方法としては、
・水平方向（図１８の（ａ）に示したように、左から右へのスキャンを上から下へ行うという順序の他に、図１８の（ｂ）〜（ｄ）に示すように、左から右へのスキャンを下から上へ行う等、４通りのスキャン方法がある）、
・垂直方向（上から下へのスキャンを左から右へ行う等、４通りのスキャン方法が考えられる）、
・図１８（ｅ）に示すように、偶数ラインと奇数ラインでスキャンを分ける。
【００５４】
なお、第２の実施形態では、図１８の（ａ）に示すスキャン方法を採用するが、上述した他のスキャン方法も適用可能である。
【００５５】
続いてステップＳ１５ａにおいて、以上のようにして得たラベル行列や画像データを画像蓄積部１７、画像管理ＤＢ１８ａ、ラベル行列インデックス１９ａに格納する。すなわち、ステップＳ１１で読み込んだ画像データに対して画像ＩＤを取得し、これらをペアにして画像蓄積部１７に格納する。そして、当該画像ＩＤに対応付けて図１６に示す画像管理ＤＢレコードを生成し、これを画像管理ＤＢ１８ａに登録する。
【００５６】
以上が画像登録時に行われる処理である。
【００５７】
［類似画像検索処理］
次に図１９のフローチャートに従って類似画像検索の処理を説明する。図１９は第２の実施形態による類似画像検索の処理手順を説明するフローチャートである。なお、本実施形態では、予め初期化時において、画像管理ＤＢのラベル系列から、既に登録されている画像のラベル行列群を得て、各ラベル成分をキーとするラベル成分インデックスファイルを生成し、ラベル行列インデックス１９ａに格納しておく。なお、ここでいう初期化時とは、システムの立ち上げ時或いはアプリケーションの起動時のいずれでも良い。また、新規の画像登録があり、これを画像ＤＢに登録した場合にも、このラベル成分インデックスの生成を行う。
【００５８】
本実施形態においても、第１の実施形態で説明したラベル成分インデックス（図１０）を用いる。すなわち、ラベル成分インデックスには、各ラベル成分毎に、そのラベルを内部に持つラベル行列へのアドレス群（列ＩＤ群）が登録される。なお、このラベル成分インデックスファイルは画像の登録及び削除、変更を反映する必要が生じるまで、作成し直す必要はない。もちろん、第１の実施形態で述べたように、毎回登録時にラベル成分インデックスを追記してゆく方法も存在する。
【００５９】
まず、ステップＳ２１において、ユーザーインターフェース部１１から類似検索元画像が指定されると、ステップＳ２２ａにおいて、指定された類似検索元画像の画像ＩＤが取得され、更に画像管理ＤＢ１８から当該元画像のラベル行列（本例ではカラーラベル行列）が取得される。
【００６０】
次にステップＳ２３ａにおいて、ラベル成分インデックスファイルを参照し、類似検索元画像のラベル行列とある程度以上同一のラベルを含むラベル行列群（ラベル系列インデックス中のラベル行列）を取得する。これは登録した画像の全てのラベル列との比較を行うと処理が遅くなるので、予め似ているものに絞った後に、類似検索元画像のラベル行列と一対一で比較するようにし、処理速度を改善するためである。なお、類似したラベル行列とは、類似検索元画像のラベル行列と所定数以上の同一もしくは類似のラベルを含むラベル行列群をいう。ここで、類似のラベルとは図１１で説明したラベル間ペナルティの小さいラベル同士をいう。もちろん、処理が遅くなっても良ければ、登録した画像の全てのラベル行列との比較を行い、精度の高い検索を行ってもよい（この場合、ステップＳ２３ａは省略される）。
【００６１】
次に、ステップＳ２４ａにおいて、ステップＳ２３ａで取得した各ラベル行列と類似検索元画像のラベル行列とを比較し、その類似度を算出する。そして、類似検索元画像のラベル行列に最も近いラベル行列から順にその類似度とともに検索結果として出力する。
【００６２】
ここで、ラベル行列同士の類似比較（類似度の算出）を行う方法について述べる。なお、以下では、ステップＳ２３ａで取得したラベル行列を類似比較先画像と称する。
【００６３】
また、第２の実施形態においてもラベル行列を比較して類似度を求める際には、第１の実施形態と同様にラベル間のペナルティマトリックス（図１１）を用いる。
【００６４】
ラベル間のパターンマッチングの際に隣接するセル同士ではペナルティ（距離）を小さくし、遠いものには大きなペナルティを与えるために図１２に示すようなラベル間でのペナルティマトリックスを導入する。ステップＳ２４ａではこのペナルティマトリックスを考慮し、ラベル行列同士を比較するが、第２の実施形態では、その際に以下に説明する２次元的なＤＰマッチング（以下、２次元ＤＰマッチングという）を使用する。
【００６５】
図２０は本実施形態による類似度算出処理を説明する図である。上述のステップＳ２２ａにおいて取得された類似検索元画像のラベル行列は、そのスキャン方法に従って図２０の（ｂ）のように並べることができる。また、ステップＳ２３ａにおいて抽出されたラベル行列群のうちの一つを類似検索元画像とすると、そのラベル行列は図２０（ａ）のように並べることができる。
【００６６】
まず、類似比較先画像の第１行目のラベル列「ａｂｃ」と、類似検索元画像の第１〜第３行目のラベル列（「１２３」、「４５６」、「７８９」）のそれぞれとの距離をＤＰマッチングによって求め、その距離が最少となるラベル列の類似検索元画像における行番号を類似ライン行列（図２０の（ｃ））の該当する位置に記憶する。また、得られた最小距離が所定の閾値よりも大きい場合には、どの行とも類似していないと判断し、類似ライン行列の該当する位置に「！」を記憶する。ＤＰマッチングの性質により、たとえば画像のアングルが水平方向へ多少変わっていたとしても、上記処理により類似する行（ライン）を検出可能である。以上の処理を、類似比較先画像の全ての行（「ｄｅｆ」「ｇｈｉ」）について行うことで、図２０の（ｃ）のような列方向の類似ライン行列が得られる。
【００６７】
図２０の（ｃ）では、「ａｂｃ」に類似した行が類似検索元画像に存在せず、「ｄｅｆ」に類似した行が類似検索元画像の第１行目、「ｇｈｉ」に類似した行が類似検索元画像の第２行目であったことを示している。以上のようにして得られた類似ライン行列と標準ライン行列（類似検索元画像の行の並びであり、本例では「１２３」となる）との類似度をＤＰマッチングを用いて算出し、これを当該類似検索元画像と当該類似比較先画像との類似度として出力する。なお、ＤＰマッチングでは、周知のように、比較するラベルシーケンスが最も類似距離が小さくなるように、比較するラベルシーケンスを伸縮（比較する相手を次に進めないで我慢する）させて比較するという処理を行う。また、何処まで伸縮（我慢）できるかを制約条件（整合窓の幅）で与えることも可能である。
【００６８】
図２１は第２の実施形態による、２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。上記図２０を参照して説明した処理を、図２１のフローチャートを参照して更に説明する。
【００６９】
まず、ステップＳ１０１において、類似比較先画像の行番号を表す変数ｉと、類似検索元画像の行番号を表す変数ｊを１に初期化し、ともに第１行目を示すように設定する。次に、ステップＳ１０２において、類似比較先画像の第ｉ行目のラベル列を取得する。例えば図２０の場合、ｉ＝１であれば「ａｂｃ」が取得される。そして、ステップＳ１０３において、類似検索元画像の第ｊ行目のラベル列を取得する。例えば、図２０において、ｊ＝１であれば、「１２３」が取得される。
【００７０】
次にステップＳ１０４では、上記ステップＳ１０２、Ｓ１０３で得られた２つのラベル列間の距離を、図１２で説明した色セルペナルティーマトリクスを用いて、ＤＰマッチングによって求める。そして、ステップＳ１０５において、ステップＳ１０４で得た距離が、第ｉ行目に関してそれまでに得られた距離の最小値であれば、当該行番号（ｊ）をライン行列要素ＬＩＮＥ［ｉ］に記憶する。
【００７１】
以上のステップＳ１０３からステップＳ１０５の処理を、類似検索元画像の全ての行について行う（ステップＳ１０６、Ｓ１０７）。以上のようにして、類似比較先画像の第ｉ行目のラベル列に対して、類似検索元画像に含まれる行のうち最も距離の近い行の番号がＬＩＮＥ［ｉ］に格納されることになる。
【００７２】
そして、ステップＳ１０８において、上記処理でられたＬＩＮＥ［ｉ］と所定の閾値（Ｔｈｒｅｓｈ）とを比較する。そして、ＬＩＮＥ［ｉ］がＴｈｒｅｓｈ以上であればステップＳ１０９へ進み、いずれの行とも類似していないことを表す「！」をＬＩＮＥ［ｉ］に格納する。
【００７３】
以上説明したステップＳ１０２からＳ１０８の処理を類似比較先画像の全ての行について実行する（ステップＳ１１０、Ｓ１１１）ことにより、ＬＩＮＥ［１］〜ＬＩＮＥ［ｉｍａｘ］が得られるので、これを類似ライン行列ＬＩＮＥ［］として出力する。
【００７４】
次に、ステップＳ１１３において、標準ライン行列「１２…ｉｍａｘ」と類似ライン行列ＬＩＮＥ［］とのＤＰマッチングを行い、両者の距離を算出する。なお、ここで、標準ライン行列とは、１から始まり、列方向に１ずつ増加する行列である。
【００７５】
ここで、標準ライン行列と類似ライン行列間のＤＰマッチングにおいて用いられるペナルティーについて説明する。列方向の類似ライン行列と標準ライン行列とのＤＰマッチングのペナルティーの設定としては２つの方法が考えられる。すなわち、動的なペナルティーと固定的なペナルティーの２つである。
【００７６】
動的なペナルティーとは、動的にライン番号間のペナルティーを設定するものであり、画像によってライン番号間のペナルティーは変化する。本実施形態では、類似検索元画像の自分自身の横（行）方向のラベル行列の距離を求め、これに基づいて各行間のペナルティーを求める。
【００７７】
図２２は第２の実施形態による動的なペナルティー値の設定手順を示すフローチャートである。ステップＳ１２１において、変数ｉを１に、変数ｊを２にそれぞれセットする。次に、ステップＳ１２２において、類似検索元画像の第ｉ行目のラベル列を取得し、ステップＳ１２３において、類似検索もと画像の第ｊ行目のラベル列を取得する。そして、ステップＳ１２４において、類似検索元画像の第ｉ行目のラベル列と第ｊ行目のラベル列とについて、色ペナルティーマトリクスを用いてＤＰマッチングを行い、距離を獲得する。ステップＳ１２５では、ステップＳ１２４で得たＤＰマッチングの距離を、類似検索元画像のｉ行目のラベル列とｊ行目のラベル列間のペナルティーとしてＬＩＮＥ[i][j]に記憶すると共に、、類似検索元画像のｊ行目のラベル列とｉ行目のラベル列間のペナルティーとしてＬＩＮＥ[j][i]に記憶する。
【００７８】
ステップＳ１２６によって、変数ｊの値がｊｍａｘとなるまで、ステップＳ１２３〜Ｓ１２５の処理が繰返される。この結果、第ｉ行目のラベル列について、ｉ＋１〜ｊｍａｘ行目の各ラベル列との間のペナルティー値が決定される。そして、ステップＳ１２８、Ｓ１２９、Ｓ１３０により、ステップＳ１２３〜Ｓ１２６の処理を変数ｉの値がｉｍａｘ−１となるまで繰返される。この結果、ＬＩＮＥ[i]「ｊ］には、ｉ＝ｊの対角成分を除く全てに、上記処理で決定されたペナルティー値が記憶されることになる。
【００７９】
次にステップＳ１３１では、上記処理で決定されていないＬＩＮＥ[i][j]の対角成分のペナルティーを決定する。この部分はｉ＝ｊであり、同一のラベル列であるから、その距離は０であり、従ってペナルティー０が記憶される。また、ステップＳ１３２では、「！」に関してペナルティーを決定する。すなわち、「！」に対するペナルティーは、ＬＩＮＥ[i][j]の全てのペナルティー値の中で、最大のペナルティー値よりもある程度大きな値を設定する。ただし、このペナルティー値を極端に大きくすると、曖昧にヒットする性質が損なわれてしまう。
【００８０】
以上のようにして類似検索元画像に関して計算されたラベル列間のペナルティーを用いて、上記ステップＳ１１３におけるＤＰマッチングを行い、類似度検索元画像と類似比較先画像の類似度を獲得する。
【００８１】
一方、固定的なペナルティーでは、ＤＰマッチングのペナルティーとして、ラベルが一致すればペナルティー「０」を、一致しない場合、もしくは「！」との比較であった場合にはある程度の大きさのペナルティーを与える。この場合は類似検索元画像によらず、常に同じペナルティーとなる。このような固定的なペナルティーを用いてステップＳ１１３の処理を実行し、類似度検索元画像と類似比較先画像の類似度を決定する。
【００８２】
以上説明したマッチング処理は次のような特徴を有する。もし、図２０の（ａ）と（ｂ）が極めて類似していれば、類似ライン行列は「１２３」となり、その距離は０となる。また、類似ライン行列が「！１２」や「２１２」であれば、類似検索元画像に対して類似比較先画像は下方向へずれたものである可能性があるし、類似ライン行列が「２３！」や「２３３」であれば類似検索元画像に対して類似比較先画像が上方向へずれたものである可能性がある。また、類似ライン行列が「１３！」や「！１３」であれば、類似検索元画像に対して類似比較先画像が縮小したものである可能性がある。同様に、類似比較先画像が類似検索元画像を拡大したようなものである場合も検出可能である。
【００８３】
上述のステップＳ１１３で説明したように、類似ライン行列と標準ライン行列との間でＤＰマッチングを行うことにより、垂直方向へのずれが効果的に吸収される。このため、上述したような、上方向や下方向へのずれ、拡大、縮小等に起因する類似検索元画像と類似比較先画像との相違が効果的に吸収され、良好な類似検索を行うことが可能となる。
【００８４】
すなわち、本実施形態の２次元ＤＰマッチングは、ラベル行列の各ラベル列における前後の曖昧さを許容するマッチングであり、画像の位置ずれの影響を吸収する性質を有する。また、アングルの違い等により物体の位置が変わり、ブロックによって切りとられる物体の位置が変わることにより、ブロックの色合いも微妙に異なることが予想されるが、この違いは上述のペナルティーマトリクスにより吸収されることになる。このように、本実施形態の２次元ＤＰマッチングによる曖昧さを許容するマッチングと、ペナルティーマトリクスによる特徴量の曖昧さの許容との相乗効果によって、上下左右拡大、縮小のずれに対しても影響の少ないマッチングを可能としている。
【００８５】
ただし、動的なペナルティーと固定的なペナルティーとでは、動的なペナルティーを用いる方が好ましい。例えば、一面麦畑の類似元検索画像があったとした場合、どのラインも似たようなラベル列となることが考えられる。一方、類似比較先画像にも一面麦畑の画像があったとした場合に、この画像の類似ライン行列には全て最初のライン番号１が入り、「１１１」となってしまう可能性がある。この場合、類似検索元画像のどのラインも似たような画像となっており、ライン番号間のペナルティーが極めて小さくなければ低い距離でのヒットはしない。しかしながら、動的なペナルティーを用いた場合は、ライン番号間のペナルティーが低くなり、類似度の高い結果を得ることができる。
【００８６】
一方、固定的なペナルティーを用いると、「１２３」と「１１１」ではペナルティー値が大きくなり、類似度が低くなってしまう。
【００８７】
ステップＳ２４ａでは、以上説明した類似度の算出処理をステップＳ２３ａで取得した全ラベル行列について行い、得られた類似度を高い順にソートして、ステップＳ２５ａへ進む。ステップＳ２５ａにおいて、画像管理ＤＢ１８ａを参照して、画像ＩＤ群の各画像ＩＤについてフルパスのファイル名を取得し、これをユーザに提示する。
【００８８】
以上のようにして、ＤＰマッチングを水平・鉛直方向、すなわち２次元に行うことにより、水平や鉛直方向、更に斜め方向に画像アングルが変わったり、物体が移動していても検索を行うことが可能である。また、ＤＰマッチングの時系列伸縮特性により、ズームアップ撮影画像やマクロ撮影画像をも検索することが可能となる。
【００８９】
なお、上記実施形態では、水平方向のブロック並びに対応するラベル列を用いて類似ライン行列を得たが、垂直方向のブロック並びに対応するラベル列を用いて類似ライン行列を得るようにすることも、上記と同様の手法で実現可能である。
【００９０】
以上説明したように、第２の実施形態によれば、特徴量群（特徴量空間を分割して得られる特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル同士の類似度に基づく距離を上述の２次元ＤＰマッチングとペナルティーマトリクスによって与える。このため、２つの画像のブロック間の距離の計算量を大幅に減少させることができるとともに、類似した特徴量が同じラベルで表されることになるので、類似画像の検索を良好に行うことができる。
【００９１】
また、（１）ペナルティマトリクスによるラベル同士の距離概念を導入し、（２）比較するラベル位置を前後曖昧に移動させることが出来、トータルの距離が最小（類似度が最大）となるようなラベル行列の比較を実現する上記２次元ＤＰマッチングを導入したことにより、画像のアングルが多少変わっても検索することが可能となり、雰囲気の似ている画像を検索できるようになる。
【００９２】
更に上記実施形態によれば、インデックスデータベース（ラベル成分インデックス）を用いたことにより、画像検索が更に高速化する。
【００９３】
すなわち、上記実施形態によれば、画像の特徴量の配置を考慮した類似画像の高速な検索が行われるとともに、撮影条件の変動等による違いを吸収した類似画像の検索が可能となり、従来難しかった画像のアングルが変ったり、物体の位置が変ったり、あるいは他の撮影条件が変動したりすることによる画像の特徴量のある程度の違いを吸収するなど、ロバストな類似画像検索を行うことが可能となる。
【００９４】
なお、上記各実施形態においては、自然画像検索を行う例を説明したが、本発明はＣＧやＣＡＤ等の人工的な画像の検索にも適応可能な技術であることは当業者には明らかである。
【００９５】
また、上記各実施形態では画像特徴量として色情報を選んだが、本発明はこれに限られるものではなく、その他の画像パラメータを画像分割ブロックごとに求めることで実施することも可能である。
【００９６】
また、上記各実施形態では１つの特徴量での認識の例を挙げたが、その他の特徴量での検索結果との論理演算を行うことにより、複数の特徴量からの高速な検索を行うことも可能である。
【００９７】
１つの画像に対して複数の画像特徴量を用いた検索を行う場合には、本発明で得られる類似度を１つの新たなる画像特徴量とみなし、複数のパラメータを用いた多変量解析を行い統計的な距離尺度を用いた検索を行うことも可能である。また、上記実施形態では、類似度が所定値を越える類似画像を検索結果として得るが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよいことはいうまでもない。
【００９８】
なお、曖昧度を指定することにより、ＤＰマッチングにおけるいわゆる整合窓の幅を変更することにより、検索の曖昧度を所望に設定可能とすることもできる。図２３はＤＰマッチングにおける整合窓を説明する図である。図２３において直線ＡはＪ＝Ｉ＋ｒで表され、直線ＢはＪ＝Ｉ−ｒで表される。整合窓の幅はｒの値を変更することで行える。したがって、キーボード１０４から曖昧度を指定することにより、このｒの値が変更されるように構成すれば、ユーザの所望の曖昧度（整合窓の幅）で類似度検索を行えるようになる。
【００９９】
なお、上記実施形態のような２次元ＤＰマッチングにおいては、水平方向のＤＰマッチングにおける整合窓の幅と、垂直方向のＤＰマッチングにおける整合窓の幅とを別々に設定できるようにしてもよい。或いは、両整合窓が異なる変化率で変化するように構成してもよい。このようにすれば、ユーザは、類似画像検索に際してよりきめ細かい曖昧さの設定を行えるようになる。例えば、図１８で示されたようなブロック順序を用いた場合において、検索元の画像中における注目物体の横方向への移動を許容したいような場合や、検索元の画像が横長画像であるような場合には、横方向への曖昧度を大きくするために水平方向のＤＰマッチングにおける整合窓の幅をより大きくすればよい。
【０１００】
なお、本発明は、例えばホストコンピュータ，インタフェイス機器，リーダ，プリンタなどの複数の機器から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機，ファクシミリ装置など）に適用してもよい。
【０１０１】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。
【０１０２】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０１０３】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピディスク，ハードディスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリカード，ＲＯＭなどを用いることができる。
【０１０４】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０５】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０６】
【発明の効果】
以上説明したように本発明によれば、画像の特徴量の配置を考慮した類似画像の検索が可能となる。
【０１０７】
また、本発明によれば、画像の特徴量の配置を考慮した類似画像の検索が行われるとともに、撮影条件の変動等による違いを吸収した類似画像の検索が可能となり、従来難しかった画像のアングルが変ったり、物体の位置が変ったり、あるいは他の撮影条件が変動したりすることによる画像の特徴量のある程度の違いを吸収するなど、ロバストな類似画像検索を行うことが可能となる。
【０１０８】
また、本発明によれば、特徴量ラベルに基づいて画像データを登録するインデックステーブルを導入することにより、類似度計算の対象とする画像データを効率よく絞り込むことが可能となり、類似検索の処理速度が著しく向上する。
【０１０９】
【図面の簡単な説明】
【図１】第１の実施形態による画像検索装置の制御構成を示すブロック図である。
【図２】第１の実施形態の画像検索装置の機能構成を示すブロック図である。
【図３】画像蓄積部１７における画像データの格納状態を説明する図である。
【図４】第１の実施形態による画像登録処理の手順を表すフローチャートである。
【図５】本実施形態による画像のブロック分割例を示す図である。
【図６】本実施形態による多次元特徴量空間を説明する図である。
【図７】ラベル列を生成する際のブロック順序例を説明する図である。
【図８】第１の実施形態における、画像管理データベースによる画像データの格納形態を説明する図である。
【図９】第１の実施形態による類似画像検索の処理手順を説明するフローチャートである。
【図１０】ラベル成分インデックスのデータ構成例を示す図である。
【図１１】ラベル列を比較し類似度を求める際に用いるラベル間のペナルティマトリックスの一例を示す図である。
【図１２】ＤＰマッチングによるラベル列間の距離の算出を説明する図である。
【図１３】ＤＰマッチングによるラベル列間の距離の算出を説明する図である。
【図１４】ＤＰマッチングによるラベル列間の距離の算出を説明する図である。
【図１５】本実施形態の画像検索装置の機能構成を示すブロック図である。
【図１６】第２の実施形態における、画像管理データベースによる画像データの格納形態を説明する図である。
【図１７】第２の実施形態による画像登録処理の手順を示すフローチャートである。
【図１８】ラベル行列を生成する際のブロック順序例を説明する図である。
【図１９】第２の実施形態による類似画像検索の処理手順を説明するフローチャートである。
【図２０】本実施形態による類似度算出処理を説明する図である。
【図２１】第２の実施形態による、２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。
【図２２】第２の実施形態による動的なペナルティー値の設定手順を示すフローチャートである。
【図２３】ＤＰマッチングにおける整合窓の調整を説明する図である。
Claims (22)
- 画像データを複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与する付与手段と、
前記付与手段で付与されたラベルを所定のブロック順序に基づいて並べることによりラベル列を生成する生成手段と、
前記生成手段で生成されたラベル列を前記画像データに対応付けて記憶する第１記憶手段と、
前記生成されたラベル列に基づいて、前記画像データをラベルをキーとして、ラベル毎に当該ラベルを含む画像データを示す画像ＩＤを登録するとともに、各画像データにおける当該ラベルの含有数を登録するインデックステーブルを記憶する第２記憶手段と、
検索元となる検索元画像データが与えられた場合、該検索元画像データに対応するラベル列を獲得し、前記インデックステーブルに登録されている画像ＩＤとラベルの含有数とに基づき、該獲得されたラベル列に類似する画像データ群を抽出する抽出手段と、
前記抽出手段で抽出された画像データ群のそれぞれについて、前記第１記憶手段に記憶されたラベル列に基づいて前記検索元画像データに対応する画像データの検索を行う検索手段とを備えることを特徴とする画像検索装置。 - 前記インデックステーブルの各ラベル毎に登録される画像データは、当該ラベルの含有数に基づいてソートされている
ことを特徴とする請求項１に記載の画像検索装置。 - 前記ラベルは、多次元特徴量空間を複数のセルに分割して得られたセルの夫々に与えられる固有のラベルであり、
前記付与手段は、前記ブロックの夫々について特徴量を算出し、算出された特徴量が属するセルに付与されているラベルを当該ブロックに付与することを特徴とする請求項１に記載の画像検索装置。 - 前記複数のブロックは画像を縦横複数のブロックに分けて得られたものであり、前記生成手段で用いられるブロック順序は、該複数のブロックを斜め方向に走査する順序であることを特徴とする請求項１に記載の画像検索装置。
- 前記複数のブロックは画像を縦横複数のブロックに分けて得られたものであり、前記生成手段で用いられるブロック順序は、該複数のブロックを水平もしくは鉛直方向に走査する順序であることを特徴とする請求項１に記載の画像検索装置。
- 前記検索手段は、
前記検索元画像データのラベル列と前記抽出手段で抽出された画像データのラベル列との類似度を演算する演算手段と、
前記演算手段による類似度が所定値を越える画像データを検索結果として出力する出力手段とを備えることを特徴とする請求項１に記載の画像検索装置。 - 前記演算手段は、各ラベル値のペアについてペナルティ値を保持するペナルティテーブルを有し、前記検索元画像データのラベル列と前記抽出された画像データのラベル列とから得られる各ラベル値のペアについて該ペナルティテーブルを参照してペナルティ値を取得し、取得されたペナルティ値に基づいて類似度を算出することを特徴とする請求項６に記載の画像検索装置。
- 前記ラベルは、多次元特徴量空間を複数のセルに分割し、得られたセルの夫々に与えられる固有のラベルであり、
前記ペナルティ値は、２つのラベルが表すセル間の距離に基づいて設定される値であることを特徴とする請求項７に記載の画像検索装置。 - 前記演算手段は、検索元画像のラベル列と比較先画像のラベル列との類似度を演算するにおいて、更にラベルの過不足に対するペナルティ値を付与することを特徴とする請求項７に記載の画像検索装置。
- 前記演算手段は、前記ペナルティ値を用いてＤＰマッチングを行い、類似度を算出することを特徴とする請求項７に記載の画像検索装置。
- 前記抽出手段は、前記第１記憶手段に記憶されたラベル列のうちの、前記検索元画像データのラベル列に含まれるラベルと同一もしくは類似のラベルを所定数以上含むラベル列を前記インデックステーブルを参照して抽出することを特徴とする請求項１に記載の画像検索装置。
- 前記ラベル列が、２次元のラベル行列を表し、
前記検索手段が、
前記検索元画像データのラベル行列より抽出される行単位のラベル列と、前記抽出手段で抽出された画像データのラベル行列より抽出される行単位のラベル列とをＤＰマッチングによって対応づけて該抽出された画像データの行並びを得る第１マッチング手段と、
前記検索元画像データのラベル行列の行並びと、前記第１マッチング手段で得られた行並びとの類似度をＤＰマッチングによって求める第２マッチング手段とを備えることを特徴とする請求項１に記載の画像検索装置。 - 前記行単位のラベル列は、画像の水平方向に対応する並び、または、画像の垂直方向に対応する並びであることを特徴とする請求項１２に記載の画像検索装置。
- 前記第２マッチング手段によって得られた類似度が所定値を越える画像を検索結果として出力する出力手段を更に備えることを特徴とする請求項１２に記載の画像検索装置。
- 前記第１マッチング手段は、各ラベルのペアについてペナルティ値を保持するペナルティテーブルを有し、前記検索元画像のラベル列と前記比較先画像のラベル列との距離をＤＰマッチング手法を用いて算出するに際して該ペナルティテーブルを参照することを特徴とする請求項１２に記載の画像検索装置。
- 前記第２マッチング手段は、行並びにおける各行番号のペアについてペナルティ値を保持する行間ペナルティテーブルを有し、前記検索元画像の行並びと前記比較先画像の行並びの類似度をＤＰマッチング手法を用いて算出するに際して、該行間ペナルティテーブルを参照することを特徴とする請求項１２に記載の画像検索装置。
- 前記元画像データの行方向の各ラベル列の類似度に基づいて各行のペアに関するペナルティー値を決定し、これを前記行間ペナルティテーブルとして保持する保持手段を更に備えることを特徴とする請求項１６に記載の画像検索装置。
- 前記第１マッチング手段は、前記元画像データのラベル列と前記記憶手段に記憶されたラベル列との類似度を演算するにおいて、更にラベル比較の系列伸縮に伴うペナルティー及び制約を付与することを特徴とする請求項１２に記載の画像検索装置。
- 前記第１マッチング手段で使用するＤＰマッチングの整合窓の幅を設定する第１設定手段を更に備えることを特徴とする請求項１２に記載の画像検索装置。
- 前記第２マッチング手段で使用するＤＰマッチングの整合窓の幅を設定する第２設定手段を更に備えることを特徴とする請求項１２に記載の画像検索装置。
- 画像特徴量算出手段が、メモリに格納された画像データについて、画像を複数のブロックに分割し、各ブロックの画像データから各ブロックの特徴量を算出する算出工程と、
ラベル付与手段が、前記算出工程で算出された特徴量に応じて各ブロックにラベルを付与する付与工程と、
ラベル列生成手段が、前記付与工程で付与されたラベルを所定のブロック順序に基づいて並べることによりラベル列を生成する生成工程と、
第１記憶手段が、前記生成工程で生成されたラベル列を前記画像データに対応付けて画像管理記憶手段に記憶する第１記憶工程と、
第２記憶手段が、前記生成されたラベル列に基づいて、前記画像データをラベルをキーとして、ラベル毎に当該ラベルを含む画像データを示す画像ＩＤを登録するとともに、各画像データにおける当該ラベルの含有数を登録するインデックステーブルをラベル記憶手段に記憶する第２記憶工程と、
抽出手段が、検索元となる検索元画像データの指定に応じて、該検索元画像データに対応するラベル列を前記算出工程、前記付与工程及び前記生成工程により獲得し、前記インデックステーブルに登録されている画像ＩＤとラベルの含有数とに基づき、該獲得されたラベル列に類似する画像データ群を抽出する抽出工程と、
検索手段が、前記抽出工程で抽出された画像データ群のそれぞれについて、前記画像記憶手段に記憶されているラベル列に基づいて前記検索元画像データに対応する画像データを検索してその検索結果データを出力する検索工程とを備えることを特徴とする画像検索方法。 - コンピュータに類似画像検索処理を実行させるために、該コンピュータを、
メモリに格納された画像データについて、画像を複数のブロックに分割し、各ブロックの画像データから各ブロックの特徴量を算出し、算出された特徴量に応じて各ブロックにラベルを付与する付与手段と、
前記付与手段で付与されたラベルを所定のブロック順序に基づいて並べることによりラベル列を生成する生成手段と、
前記生成手段で生成されたラベル列と前記画像データの対応付けデータをメモリに記憶する第１記憶手段と、
前記生成されたラベル列に基づいて、前記画像データをラベルをキーとして、ラベル毎に当該ラベルを含む画像データを示す画像ＩＤを登録するとともに、各画像データにおける当該ラベルの含有数を登録するインデックステーブルをメモリに記憶する第２記憶手段と、
検索元となる検索元画像データの指定に応じて、該検索元画像データに対応するラベル列を獲得し、前記インデックステーブルに登録されている画像ＩＤとラベルの含有数とに基づき、該獲得されたラベル列に類似する画像データ群を抽出する抽出手段と、
前記抽出手段で抽出された画像データ群のそれぞれについて、前記対応付けデータに登録されているラベル列に基づいて前記検索元画像データに対応する画像データを検索してその検索結果データを出力する検索手段とを備える画像検索装置として機能させる制御プログラムを格納したことを特徴とする記憶媒体。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP09013398A JP3720573B2 (ja) | 1998-04-02 | 1998-04-02 | 画像検索装置及び方法 |
| US09/281,783 US6584223B1 (en) | 1998-04-02 | 1999-03-31 | Image search apparatus and method |
| DE69942901T DE69942901D1 (de) | 1998-04-02 | 1999-03-31 | Einrichtung und Verfahren zum Suchen von Bildern |
| EP99302566A EP0947937B1 (en) | 1998-04-02 | 1999-03-31 | Image search apparatus and method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP09013398A JP3720573B2 (ja) | 1998-04-02 | 1998-04-02 | 画像検索装置及び方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11288418A JPH11288418A (ja) | 1999-10-19 |
| JP3720573B2 true JP3720573B2 (ja) | 2005-11-30 |
Family
ID=13990018
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP09013398A Expired - Fee Related JP3720573B2 (ja) | 1998-04-02 | 1998-04-02 | 画像検索装置及び方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3720573B2 (ja) |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4610696B2 (ja) * | 2000-06-07 | 2011-01-12 | カシオ計算機株式会社 | 画像処理装置及び記録媒体 |
| JP2003109009A (ja) * | 2001-09-26 | 2003-04-11 | Communication Research Laboratory | 画像の類似性計測方法及び装置 |
| JP4235604B2 (ja) | 2004-11-22 | 2009-03-11 | キヤノン株式会社 | 画像処理装置、画像処理方法、ならびにプログラム |
| JP4968882B2 (ja) | 2005-06-03 | 2012-07-04 | キヤノン株式会社 | 画像検索装置、画像検索方法およびプログラム |
| JP4642697B2 (ja) | 2006-05-24 | 2011-03-02 | Ｎｅｃディスプレイソリューションズ株式会社 | 画像キャッシュメモリを有する画像表示装置 |
| JP4183012B2 (ja) * | 2007-04-16 | 2008-11-19 | カシオ計算機株式会社 | 画像処理装置および記録媒体 |
| JP5277499B2 (ja) * | 2007-05-16 | 2013-08-28 | 株式会社アテロソフト | 情報検索装置 |
| JP4820433B2 (ja) * | 2009-05-14 | 2011-11-24 | 日本電信電話株式会社 | 画像情報検索装置及びプログラム |
| KR102441902B1 (ko) * | 2021-12-10 | 2022-09-13 | 주식회사 이안에스아이티 | 시계열 3차원 시각화 데이터 생성 방법 및 장치 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3311077B2 (ja) * | 1993-05-06 | 2002-08-05 | 松下電器産業株式会社 | 画像検索装置 |
| JPH07160725A (ja) * | 1993-12-03 | 1995-06-23 | Toshiba Corp | 画像検索装置 |
| JP3727967B2 (ja) * | 1995-01-31 | 2005-12-21 | キヤノン株式会社 | 画像検索方法及びその装置 |
| JPH08137908A (ja) * | 1994-11-15 | 1996-05-31 | Canon Inc | 画像検索方法及び装置 |
| JP3199976B2 (ja) * | 1995-03-14 | 2001-08-20 | 正夫 坂内 | 画像データベース装置 |
-
1998
- 1998-04-02 JP JP09013398A patent/JP3720573B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH11288418A (ja) | 1999-10-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6584223B1 (en) | Image search apparatus and method | |
| EP0866409B1 (en) | Image retrieval apparatus and method | |
| Bai et al. | Learning-based efficient graph similarity computation via multi-scale convolutional set matching | |
| JP3754791B2 (ja) | 画像検索装置及び方法 | |
| JP3952592B2 (ja) | 画像検索装置及び方法 | |
| US6691126B1 (en) | Method and apparatus for locating multi-region objects in an image or video database | |
| US6564206B1 (en) | Information search apparatus and method, and storage medium | |
| US7961950B2 (en) | Image processing apparatus, method thereof, and its control method | |
| EP1634135B1 (en) | Systems and methods for source language word pattern matching | |
| EP1993064A2 (en) | Image processing apparatus and image retrieval method | |
| US5359671A (en) | Character-recognition systems and methods with means to measure endpoint features in character bit-maps | |
| CN109101981B (zh) | 一种街景场景下基于全局图像条纹码的回环检测方法 | |
| US5999653A (en) | Fast techniques for searching images using the Hausdorff distance | |
| JP4235604B2 (ja) | 画像処理装置、画像処理方法、ならびにプログラム | |
| JP2004522228A (ja) | ディジタル画像を表現し比較する方法 | |
| CN115145906A (zh) | 一种面向结构化数据的预处理和补全方法 | |
| JP3720573B2 (ja) | 画像検索装置及び方法 | |
| Wang et al. | Chinese document image retrieval system based on proportion of black pixel area in a character image | |
| JP3193658B2 (ja) | データ間結合ルール導出方法及び装置、及び直交凸領域切出方法及び装置 | |
| JP2000311246A (ja) | 類似画像表示方法及び類似画像表示処理プログラムを格納した記録媒体 | |
| JP3720538B2 (ja) | 画像検索装置及び方法 | |
| Schreck et al. | A new metaphor for projection-based visual analysis and data exploration | |
| JP2007079616A (ja) | 情報検索装置、情報検索装置の制御方法、及び制御プログラム | |
| KR102054211B1 (ko) | 이미지 쿼리 기반의 영상 검색 방법 및 시스템 | |
| Munarko et al. | HII: Histogram Inverted Index for Fast Images Retrieval. |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20041022 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20041221 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050307 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050428 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050822 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050908 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090916 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090916 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100916 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100916 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110916 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110916 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120916 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120916 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130916 Year of fee payment: 8 |
|
| LAPS | Cancellation because of no payment of annual fees |