(57)【要約】【課題】  画像特徴量に基づいて類似画像を検索をする場合において、画像特徴量の位置情報を考慮しつつ、当該位置情報にある程度の違いがあった場合でも、高精度かつ高速に検索できるようにすることを目的とする。【解決手段】  異なる画像データの類似度を算出する画像処理装置であって、該異なる画像データをそれぞれ複数のブロックに分割し、該ブロックごとに取得された該各画像データの特徴量に基づいて、それぞれの特徴量行列を生成する第１の生成手段と、該生成された特徴量行列を構成する各特徴列間の距離をＤＰマッチングを用いて算出する算出手段と、該算出された特徴列間の距離を２次元に配列することでラインペナルティマトリックスを生成する第２の生成手段とを備え、前記異なる画像データの類似度を、該ラインペナルティマトリックスを用いてＤＰマッチングにより算出することを特徴とする。【選択図】  図１６
2006146715.tif 000002
【特許請求の範囲】
【請求項１】
画像データ間の類似度を算出する画像処理装置であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成手段と、
前記第１の生成手段を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴量列と、前記第１の生成手段を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴量列である第２の特徴量列との距離を、ＤＰマッチングにより算出するマッチング手段と、
前記マッチング手段により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴量列の並びと前記第２の特徴量列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成手段と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記第２の生成手段により生成された２次元配列を用いて、ＤＰマッチングにより算出することを特徴とする画像処理装置。
【請求項２】
画像データ間の類似度を算出する画像処理装置であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成手段と、
前記第１の生成手段を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴量列と、前記第１の生成手段を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴量列である第２の特徴量列との距離を、ＤＰマッチングにより算出するマッチング手段と、
前記マッチング手段により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴量列の並びと前記第２の特徴量列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成手段と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記第２の生成手段により生成された２次元配列を構成する前記ラインペナルティのうち、所定の直線近傍に位置する該ラインペナルティの和算値に基づいて算出することを特徴とする画像処理装置。
【請求項３】
画像データ間の類似度を算出する画像処理装置であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成手段と、
前記第１の生成手段を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴量列と、前記第１の生成手段を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴量列である第２の特徴量列との距離を、ＤＰマッチングにより算出するマッチング手段と、
前記マッチング手段により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴量列の並びと前記第２の特徴量列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成手段と、
前記第２の生成手段により生成された前記２次元配列を用いて類似度を求める際に、前記２次元配列上に所定の規則に基づき経路を生成する第３の生成手段と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記第３の生成手段により生成された２次元配列の経路に基づき算出することを特徴とする画像処理装置。
【請求項４】
画像データ間の類似度を算出する画像処理装置であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成手段と、
前記第１の生成手段を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴量列と、前記第１の生成手段を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴量列である第２の特徴量列との距離を、ＤＰマッチングにより算出するマッチング手段と、
前記マッチング手段により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴量列の並びと前記第２の特徴量列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成手段と、
前記第２の生成手段により生成された前記２次元配列を用いて類似度を求める際に、前記２次元配列上に所定の規則に基づき複数の経路を生成する第３の生成手段と、
前記第３の生成手段により生成された複数の経路のそれぞれの経路に基づく距離を演算する演算手段と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記演算手段により生成されたそれぞれの距離に基づき算出することを特徴とする画像処理装置。
【請求項５】
前記算出された類似度が、所定の値を超えていた場合に、前記第２の画像データを検索結果として出力する出力手段を更に備えることを特徴とする請求項１乃至４のいずれかに記載の画像処理装置。
【請求項６】
画像データ間の類似度を算出する画像処理方法であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成工程と、
前記第１の生成工程を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴列と、前記第１の生成工程を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴列である第２の特徴列との距離を、ＤＰマッチングにより算出するマッチング工程と、
前記マッチング工程により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴列の並びと前記第２の特徴列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成工程と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記第２の生成工程により生成された２次元配列を用いて、ＤＰマッチングにより算出することを特徴とする画像処理方法。
【請求項７】
画像データ間の類似度を算出する画像処理方法であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成工程と、
前記第１の生成工程を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴列と、前記第１の生成工程を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴列である第２の特徴列との距離を、ＤＰマッチングにより算出するマッチング工程と、
前記マッチング工程により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴列の並びと前記第２の特徴列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成工程と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記第２の生成工程により生成された２次元配列を構成する前記ラインペナルティのうち、予め定められた直線近傍に位置する該ラインペナルティの和算値に基づいて算出することを特徴とする画像処理方法。
【請求項８】
画像データ間の類似度を算出する画像処理方法であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成工程と、
前記第１の生成工程を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴量列と、前記第１の生成工程を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴量列である第２の特徴量列との距離を、ＤＰマッチングにより算出するマッチング工程と、
前記マッチング工程により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴量列の並びと前記第２の特徴量列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成工程と、
前記第２の生成工程により生成された前記２次元配列を用いて類似度を求める際に、前記２次元配列上に所定の規則に基づき経路を生成する第３の生成工程と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記第３の生成工程により生成された２次元配列の経路に基づき算出することを特徴とする画像処理方法。
【請求項９】
画像データ間の類似度を算出する画像処理方法であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成工程と、
前記第１の生成工程を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴量列と、前記第１の生成工程を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴量列である第２の特徴量列との距離を、ＤＰマッチングにより算出するマッチング工程と、
前記マッチング工程により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴量列の並びと前記第２の特徴量列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成工程と、
前記第２の生成工程により生成された前記２次元配列を用いて類似度を求める際に、前記２次元配列上に所定の規則に基づき経路を生成する第３の生成工程と、
前記第３の生成工程により生成された複数の経路のそれぞれの経路に基づく距離を演算する演算工程と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記演算工程により生成されたそれぞれの距離に基づき算出することを特徴とする画像処理方法。
【請求項１０】
前記算出された類似度が、所定の値を超えていた場合に、前記第２の画像データを検索結果として出力する出力工程を更に備えることを特徴とする請求項６乃至１０のいずれかに記載の画像処理方法。
【請求項１１】
請求項６乃至１０のいずれかに記載の画像処理方法をコンピュータによって実現させるための制御プログラムを格納した記憶媒体。
【請求項１２】
請求項６乃至１０のいずれかに記載の画像処理方法をコンピュータによって実現させるための制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を検索するための画像処理技術に関するものである。
【背景技術】
【０００２】
従来より類似画像を検索するための種々の技術が提案されている。最も一般的な例としては、画像にキーワードを付与しておき、このキーワードに基づいて画像検索を行う方式が挙げられる。しかし、当該方式の場合、高い精度で類似画像を検索できるという利点がある反面、ユーザがキーワードの付加作業を行わなければならず、更に、キーワードが付加されていない画像に関しては、縮小画として提示されたものを、ユーザがマニュアルにて選択しなければならないなど、ユーザにとって利便性が悪いという問題があった。このため、ユーザの利便性向上の観点より、画像から画像特徴量を自動的に抽出し、当該画像特徴量を用いて類似画像を検索する技術が求められてきた。
【０００３】
画像から画像特徴量を抽出し、該抽出された画像特徴量を用いて類似画像を検索する方式としては、これまでは、色情報を画像特徴量として用いる方式が主流であった。そして、かかる方式の多くが、色情報に関するヒストグラムを取ることにより算出されるＲＧＢの割合や画像中に多く存在する色の組み合わせといった画像特徴量を用いて検索するものであった。しかしながら、このような方式による類似画像検索の場合、色の位置情報が失われることとなるため、高い検索精度は望めないという問題があった。
【０００４】
そこで、最近では、例えば特開平８−２４９３４９号公報に示すように、画像を複数のブロックに分けそれぞれの画像特徴量（代表色）を用いてパターンマッチングを行うことで、色の位置情報を利用して類似画像を検索する方式が提案されてきている。
【０００５】
さらに、特開平１１−２８８４１８号公報では、画像特徴量の配置を考慮した類似画像の検索方法として、行単位のマッチングのみを行って類似行並びを特定し、その類似行並びを再使用して行毎のマッチングを行うことで、類似度を算出する方式が提案されている。
【特許文献１】特開平８−２４９３４９号公報
【特許文献２】特開平１１−２８８４１８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記特許文献１に開示された類似画像検索の場合、マッチングを行う２つの画像について各ブロックごとに画像特徴量の距離を計算しなければならず、計算量が膨大となってしまうという問題がある。特に画像特徴量として代表色を用いた場合には、ＲＧＢ３個のデータを扱わなければならず、更に計算が複雑なものとなってしまう。
【０００７】
また、画像から抽出された画像特徴量そのものを用いて比較を行うので、比較の精度が高いという利点がある反面、画像のアングルが変わったり、物体の位置が変わったりするだけで類似画像検索できなくなってしまうことから、いわゆる「自然画像」等を対象とした類似画像検索には不適であるといった問題もある。
【０００８】
一方、上記特許文献２に開示された類似画像検索の場合、行毎のマッチングを行わずに類似行並びを特定するため、上記特許文献１に比して計算量を削減することができるものの、上記特許文献１と同様、いわゆる「自然画像」を対象とした場合、類似行並びが正しく特定されない場合があり、その結果、類似度の精度も低下してしまうといった問題があった。またこの方式では、類似行並びが正しく特定されなかった場合には、元画像と比較先画像の位置的関係を正しく抽出することができないという問題もあった。
【０００９】
このような背景のもと、画像のアングルが変わったり、物体の位置が変わったり、あるいは撮影条件が変わることによって画像特徴量にある程度の違いが生じた場合であっても、それらを吸収可能な程度に曖昧さを有しながら類似画像検索を行うことが可能な、いわゆるロバストな類似画像検索の実現が望まれている。
【００１０】
本発明は上記課題に鑑みてなされたものであり、画像特徴量に基づいて類似画像を検索をする場合において、画像特徴量の位置情報を考慮しつつ、当該位置情報にある程度の違いがあった場合でも、高精度かつ高速に検索できるようにすることを目的とする。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために本発明に係る画像処理装置は以下のような構成を備える。即ち、
画像データ間の類似度を算出する画像処理装置であって、
画像データを複数のブロックに分割し、該ブロックごとに取得された画像データの画像特徴量を所定の順序で並べることにより、特徴量行列を生成する第１の生成手段と、
前記第１の生成手段を用いて生成された第１の画像データの特徴量行列を構成する行単位の特徴量列である第１の特徴量列と、前記第１の生成手段を用いて生成された第２の画像データの特徴量行列を構成する行単位の特徴量列である第２の特徴量列との距離を、ＤＰマッチングにより算出するマッチング手段と、
前記マッチング手段により算出された各行ごとの距離をラインペナルティとして、前記第１の特徴量列の並びと前記第２の特徴量列の並びとに対応づけて２次元に配列することで２次元配列を生成する第２の生成手段と、を備え、
前記第１の画像データと前記第２の画像データの類似度を、前記第２の生成手段により生成された２次元配列を用いて、ＤＰマッチングにより算出することを特徴とする。
【発明の効果】
【００１２】
本発明によれば、画像特徴量に基づいて類似画像を検索をする場合において、画像特徴量の位置情報を考慮しつつ、当該位置情報にある程度の違いがあった場合でも、高精度かつ高速に検索できるようになる。
【発明を実施するための最良の形態】
【００１３】
以下、必要に応じて添付図面を参照しながら本発明の実施形態を詳細に説明する。
【００１４】
＜第１の実施形態＞
図１は本発明の各実施形態に共通する画像処理装置の制御構成を示すブロック図である。同図において、１０１はＣＰＵであり、後述する各種制御処理を実行する。１０２はＲＯＭであり、本画像処理装置の立ち上げ時に実行されるブートプログラムや各種データを格納する。１０３はＲＡＭであり、ＣＰＵ１０１が処理するための制御プログラムを格納するとともに、ＣＰＵ１０１が各種制御処理を実行する際の作業領域を提供する。１０４はキーボード、１０５はマウスであり、ユーザによる各種入力操作環境を提供する。
【００１５】
１０６は外部記憶装置であり、ハードディスクやフロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ等で構成される。１０７は表示器であり、処理の内容や処理結果をユーザに伝える。１０８はネットワークインターフェースであり、ネットワーク上の各機種（不図示）との通信を可能とする。１０９はインターフェース（Ｉ／Ｆ）、１１０は画像読み取りのためのスキャナである。また、１１１は上記各構成を接続するバスである。なお、上記の構成のうち、スキャナ１１０や外部記憶装置１０６はネットワーク上に配置されたもので代用してもよい。
【００１６】
図２は本発明の各実施形態に共通する画像処理装置の機能構成を示すブロック図である。同図において、２０１はユーザインターフェース部であり、表示器１０７、キーボード１０４及びマウス１０５を介して、ユーザからの各種の操作入力を検出する。２０２は画像入力部であり、スキャナ１１０による画像の読み取りを行う。２０３は画像メモリであり、画像入力部２０２によって得られた画像データをＲＡＭ１０３の所定の領域に格納する。２０４は画像特徴量抽出部であり、画像メモリ２０３に格納した画像について、後述の手順で画像特徴量を抽出する。
【００１７】
２０５は特徴量ラベル行列化部であり、画像特徴量抽出部２０４によって得られた画像特徴量に基づいてラベル行列（特徴量行列）を生成する。２０６はパターンマッチング部であり、指定された画像のラベル行列と、画像蓄積部２０７に蓄積されている画像のラベル行列に対し、後述の２次元ＤＰマッチングを用いて類似度を算出する。
【００１８】
２０７は画像蓄積部であり、画像入力部２０２等によって得られた画像データを蓄積する。図３は画像蓄積部２０７における画像データの格納状態を説明する図である。各画像データ３０２には画像ＩＤ３０１が付与され、画像蓄積部２０７ではこれらが対になって保持される。
【００１９】
２０８は画像管理データベース（以下、画像管理ＤＢ）であり、図４に示されるデータ形態で画像蓄積部２０７に格納された画像データを管理する。また、２０９はラベル行列インデックスであり、図５に示されるラベル成分インデックスファイルを格納する。なお、ラベル成分インデックス２０９の利用については、図１０のフローチャートを用いて後述する。
【００２０】
以上のような構成を備えた本実施形態にかかる画像処理装置の動作例を以下に説明する。なお、以下の例では色に着目した画像特徴量として、赤（Ｒ）、緑（Ｇ）、青（Ｂ）の三色を利用するとともに、３次元の色空間での処理を前提として説明する。ただし、言うまでも無いことであるが、Ｌ＊ａ＊ｂ表色系等の色空間で処理を行ったり、３次元以外の色空間で処理を行ったりしてもかまわない。
【００２１】
〔画像の登録処理〕
まず、画像登録の際に行う処理について説明する。図６は画像登録処理の手順を表すフローチャートである。同図に示すように、ユーザインターフェース部２０１を介してユーザが入力した指示に基づいて、ステップＳ６０１では、画像入力部２０２が画像を読み込み、当該画像を画像メモリ２０３に保持する。
【００２２】
次に、ステップＳ６０２において、当該画像を複数のブロックに分割する。本実施形態では、画像を縦横のブロックに分割する。図７は本実施形態における画像のブロック分割の一例を示す図である。同図に示されるように、本実施形態では、３×３の計９個のブロックに画像を分割するものとする。なお、本実施形態のような３×３への分割はあくまで説明の便宜上の理由によるものであり、実際には、自然画像であれば１０×１０以上の分割数とするのが好ましい。また、白の無地背景に商品が写っているような画像の場合であれば、１３×１３以上の分割数とするのが好ましい。
【００２３】
次にステップＳ６０３において、分割された各ブロックの画像特徴量（パラメータラベル）を算出する。
【００２４】
図８は分割された各ブロックについて画像特徴量を算出する際に用いられる多次元特徴量空間を説明するための図である。図８に示すように、多次元特徴量空間（ＲＧＢカラー空間）は複数のセル（色セル）に分割され、それぞれのセル（色セル）に対して通し番号でユニークなラベルが付与されている。
【００２５】
そして、分割された各ブロックにおける色成分（Ｒ、Ｇ、Ｂ）が当該多次元特徴量空間において、どのセルに属するかによって、当該ブロックの画像特徴量（パラメータラベル）が求められることとなる。
【００２６】
具体的には、分割された各ブロックに対して、すべての画素がどの色セルに属するかの計算処理を行い、もっとも頻度の多い色セルのラベルをその分割画像ブロックのパラメータラベル（「カラーラベル」）として決定する。この処理はすべてのブロックに対して行われる。
【００２７】
なお、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロックに分けたのは微妙な特徴量（色）の違いを吸収するためである。
【００２８】
また、多次元特徴量空間を用いて、画像特徴量を算出するに際しては、各色成分（Ｒ、Ｇ、Ｂ）のそれぞれの平均値と分散値とを実験によって求め規格化（正規化）した後、例えば、主成分分析等の直行変換を行い、意味のある次元にしたデータを用いるものとする。ここで、「意味のある次元」とは、主成分分析において、寄与率が大きな主成分軸で構成される次元である。
【００２９】
以上のようにして各ブロックに対してパラメータラベルが付与されると、ステップＳ６０４では、各ブロックに付与されたパラメータラベルを所定のブロック順序で並べることにより、パラメータラベル行列（以下、「ラベル行列」とする）が生成される。
【００３０】
図９はラベル行列を生成する際のブロック順序列を説明する図である。同図の分割画像ブロックのマスにある数字に従って上記のパラメータラベルを並べ、ラベル行列を生成する。なお、画像管理ＤＢ２０８やラベル行列インデックス２０９にラベル行列を格納するに際しては、上述のように２次元的なラベル行列を所定の順序で１次元に並べたものを格納するが、本実施形態ではこのような１次元の形態のものもラベル行列と称することにする。
【００３１】
ここで、図９の（ａ）では、分割画像ブロックを左から右へ水平方向へスキャンし、この水平方向のスキャンを上から下へ行う順序となっている。なお、本実施形態に適用可能なスキャンの方法としては、
・水平方向（図９の（ａ）に示したように、左から右へのスキャンを上から下へ行うという順序の他に、図９の（ｂ）〜（ｄ）に示すように、左から右へのスキャンを下から上へ行う等、４通りのスキャン方法が考えられる）、
・垂直方向（上から下へのスキャンを左から右へ行う等、４通りのスキャン方法が考えられる）、
・図９の（ｅ）に示すように、偶数ラインと奇数ラインでスキャンを分ける、
等があげられる。
【００３２】
なお、本実施形態では、図９の（ａ）のような左上から右下方向への斜めスキャンを採用するが、上述した他のスキャン方法も適用可能である。
【００３３】
続いてステップＳ６０５では、以上のようにして得られたラベル行列や画像データを画像蓄積部２０７、画像管理ＤＢ２０８、ラベル行列インデックス２０９に格納する。すなわち、ステップＳ６０１で読み込んだ画像データに対して画像ＩＤを取得し、これらをペアにして画像蓄積部２０７に格納する。そして、当該画像ＩＤに対応付けて図４に示す画像管理ＤＢレコードを生成し、これを画像管理ＤＢ２０８に登録する。以上で画像登録処理が終了する。
【００３４】
［類似画像検索処理］
○ラベル成分インデックスファイルについて
次に類似画像検索処理について説明する。はじめに類似画像検索処理にて用いられるラベル成分インデックスファイルについて説明する。
【００３５】
なお、本実施形態では、予め初期化時において、ラベル行列インデックス２０９から、既に登録されている画像のラベル行列群を得て、各ラベル成分をキーとするラベル成分インデックスファイル（図５の５０１、５０２、５０３・・・等）を生成し、ラベル行列インデックス２０９に格納しておくものとする。なお、ここでいう初期化時とは、システムの立ち上げ時或いはアプリケーションの起動時のいずれでも良い。また、新規の画像登録があり、これを画像ＤＢに登録した場合にも、このラベル成分インデックス２０９の生成を行う。
【００３６】
図５は、ラベル行列インデックス２０９のデータ構成例を示す図である。図５に示すように、ラベル行列インデックス２０９は複数のラベル成分インデックスファイル（５０１、５０２、５０３・・・等）から構成され、各ラベル成分インデックスファイルは、各ラベル成分毎に、そのラベル成分を内部に持つラベル行列へのアドレス群（列ＩＤ群）を有する。なお、このラベル成分インデックスファイルは画像の登録及び削除、変更を反映する必要が生じるまで、作成し直す必要はない。もちろん、毎回画像データの登録時にラベル行列インデックス２０９に追記してゆくようにしてもよい。この場合は、図６のステップＳ６０５の後で、新たに登録された画像について上述した処理を行うこととなる。
【００３７】
図５に示すラベル成分インデックスファイルには、ラベル成分をキーとして、そのラベル成分を含む画像ＩＤとそれに含まれる当該ラベル成分の個数が格納されている。このようなインデックスを用いれば、類似検索元画像が有するラベル成分を含む画像データの画像ＩＤを直接的に抽出できる。なお、各キー毎に格納されている画像ＩＤを、ラベル成分の個数にしたがって昇順或いは降順にソートして登録しておけば、より処理速度を向上させることができる。
【００３８】
○類似画像検索処理の流れ
次に図１０を用いて類似画像検索処理について説明する。図１０は本実施形態にかかる画像処理装置における類似画像検索処理の処理手順を説明するフローチャートである。まず、ステップＳ１００１において、ユーザインターフェース部２０１から「類似検索元画像」が指定されると、ステップＳ１００２において、当該指定された類似検索元画像の画像ＩＤ３０１が取得され、更に画像管理ＤＢ２０８から当該類似検索元画像のラベル行列（ここではカラーラベル行列）が取得される。
【００３９】
次にステップＳ１００３において、ラベル成分インデックスファイルを参照し、類似検索元画像のラベル行列とある程度以上同一のラベルを含むラベル行列群（複数のラベル成分インデックスファイルのラベル行列）を取得する。これは登録した画像の全てのラベル行列との比較を行うと処理が遅くなることに鑑みて、予め似ているもの（類似検索元画像のラベル行列と所定数以上の同一のラベルを含むラベル行列群）に絞った後に、類似検索元画像のラベル行列と一対一で比較するようにし、処理速度を改善するためである。もちろん、処理が遅くなっても良ければ、登録した画像の全てのラベル成分インデックスファイルのラベル行列との比較を行い、精度の高い検索を行ってもよい（この場合、ステップＳ１００３は省略される）。
【００４０】
次に、ステップＳ１００４において、ステップＳ１００３で取得した各ラベル行列と類似検索元画像のラベル行列とを比較し、その類似度を算出する。そして、類似検索元画像のラベル行列に最も近いラベル行列から順にその類似度とともに検索結果として出力する。
【００４１】
ステップＳ１００５では、画像管理ＤＢ２０８を参照して、画像ＩＤ群の各画像ＩＤについてフルパスのファイル名を取得し、これをユーザに提示する。
【００４２】
○類似度の算出処理に用いるペナルティマトリックスについて
ここで、ラベル行列同士の類似比較（類似度の算出）を行う際に用いるペナルティマトリックスについて述べる。なお、以下では、ステップＳ１００３で取得したラベル行列を「類似比較先画像」と称する。
【００４３】
図１１はラベル行列を比較し類似度を求める際に用いるラベル間の「ペナルティマトリックス」の一例を示す図である。ペナルティマトリクス中の値（ペナルティ）が小さい程、類似していることになる。例えば、ラベル２とラベル６のペナルティは「７」である。また、同じラベル同士のペナルティは当然のことながら「０」となっている。当該ペナルティマトリクスの使用目的はラベルの類似に応じた距離判定を行うことにある。すなわち、本実施形態では、多次元特徴量空間としてＲＧＢカラー空間を用いているので、色の類似に応じた距離判定が行えることになる。
【００４４】
例えば、類似検索元画像と類似比較先画像のラベル行列中のラベル成分についてそれぞれ対応する位置のラベル成分から図１１のペナルティマトリクスを参照して距離を求め、ラベル行列中の全ラベル成分についての距離の和を求めることで、両ラベル行列間の距離を得る。
【００４５】
例えば、図１２に示す例では、類似検索元画像のラベル行列が「１１２３１３４４１」であり、類似比較先画像のラベル行列が「１１３２２４４５２」であるので、図１１のペナルティマトリクスを用いてＤＰマッチングを行うことにより、図１３に示されるように距離（最終解）を求めることができる。
【００４６】
図１３は、図１１のペナルティマトリックスを用いてＤＰマッチングを行うことにより、類似検索元画像のラベル行列と類似比較先画像のラベル行列との距離を算出する様子を示した図である。ここで、図１３について簡単に説明する。
【００４７】
同図において、横軸には、類似検索元画像の各ラベル成分が配され、縦軸には、類似比較先画像の各ラベル成分が配されている。
【００４８】
類似検索元画像の各ラベル成分と、類似比較先画像の各ラベル成分との交点に記載された数値は、ペナルティの和算値である。例えば、類似検索元画像のラベル成分のうち、第１番目のラベル成分は「１」であり、類似比較先画像のラベル成分のうち、第１番目のラベル成分は「１」であるため、その交点には、ペナルティとして「０」が記述されている（１３０１参照）。
【００４９】
同様に、類似検索元画像の第１番目のラベル成分「１」と、類似比較先画像の第２番目のラベル成分「１」との交点には、「１」と「１」のペナルティである「０」を、先ほどのペナルティ「０」（１３０１）に和算して得られた「０」が記述されている（１３０２参照）。さらに、類似検索元画像の第１番目のラベル成分「１」と、類似比較先画像の第３番目のラベル成分「３」との交点には、「１」と「３」のペナルティである「１」を、先ほどのペナルティ「０」（１３０２）に和算して得られた「１」が記述されている（１３０３参照）。順次、類似検索元画像の第１番目のラベル成分と、類似比較先画像の各ラベル成分との値が記述される。その後の各交点の値は、縦又は横の先行する値の小さい値を用いて、同様に各交点の値を求め記述される。
【００５０】
図１３を用いて類似検索元画像のラベル行列と類似比較先画像のラベル行列との距離を算出するにあたっては、図１３の左下（類似検索元画像の第１番目のラベル成分と、類似比較先画像の第１番目のラベル成分との交点）を始点、図１３の右上（類似検索元画像の第９番目のラベル成分と、類似比較先画像の第９番目のラベル成分との交点）を終点とし、始点から終点に至る各交点のペナルティを求めていくことで、最終解を求めることができる（図１３の例では、最終解は８となる）。なお、始点から終点に至るまでの経路（Ａ）は、最終解が最小となるように選択される（図１３の例では、ペナルティの和算値が０→０→１→１→２→２→４→５→５→５→６→８となる経路が、最終解が８となる経路である）。
【００５１】
なお、経路を選択するにあたっては、傾斜制限として次の条件を用いている。すなわち、図１４において、交点（ｉ−１，ｊ）、（ｉ−１，ｊ−１）、（ｉ，ｊ−１）上のペナルティをそれぞれｇ（ｉ−１，ｊ）、ｇ（ｉ−１，ｊ−１）、ｇ（ｉ，ｊ−１）とし、交点（ｉ，ｊ）上のペナルティをｄ（ｉ，ｊ）とした場合に、交点（ｉ，ｊ）上のペナルティｇ（ｉ，ｊ）を数式１の漸化式によって求めている。
【００５２】
【数１】
2006146715.tif 000003
【００５３】
このように、本実施形態にかかる画像処理装置では、ラベル行列間のパターンマッチングの際に隣接するラベル同士ではペナルティ（距離）を小さくし、遠いものには大きなペナルティを与えるために図１１に示すようなラベル間でのペナルティマトリックスを導入する。
【００５４】
○類似度算出処理の概要
上記ステップＳ１００４ではこのペナルティマトリックスを考慮し、ラベル行列同士を比較するが、本実施形態では、その際に以下に説明する２次元的なＤＰマッチング（以下、２次元ＤＰマッチングという）を使用する。
【００５５】
図１５及び図１６は本実施形態にかかる画像処理装置における類似度算出処理を説明する図である。上述のステップＳ１００２において取得された類似検索元画像のラベル行列は、そのスキャン方法に従って図１５の（ａ）のように並べることができる。また、ステップＳ１００３において抽出されたラベル行列群のうちの一つを類似比較先画像とすると、そのラベル行列は図１５（ｂ）のように並べることができる。
【００５６】
まず、類似検索元画像の第１行目のラベル列（特徴列）「ＡＢＣＤＥ」と、類似比較先画像の第１行目のラベル列「ａｂｃｄｅ」とのラベル行列間の距離をＤＰマッチングによって求め、ラインペナルティマトリクス（２次元配列。図１５の（ｃ）参照）の該当する位置にラインペナルティとして記憶する。以上の処理を、類似検索元画像のすべての行（「ＡＢＣＤＥ」「ＦＧＨＩＪ」「ＫＬＭＮＯ」「ＰＱＲＳＴ」「ＵＶＷＸＹ」）と類似比較先画像のすべての行（「ａｂｃｄｅ」「ｆｇｈｉｊ」「ｋｌｍｎｏ」「ｐｑｒｓｔ」「ｕｖｗｘｙ」）との組み合わせについて行うことで、図１５の（ｃ）のようなラインペナルティマトリクスが得られる。
【００５７】
図１５の（ｃ）では、「ＡＢＣＤＥ」と「ａｂｃｄｅ」のラインペナルティが５０、「ＡＢＣＤＥ」と「ｆｇｈｉｊ」のラインペナルティが４５、等々であったことを示している。
【００５８】
次に、ラインペナルティマトリクスをライン行列間のペナルティとして図１６のように並べ、類似度をＤＰマッチングを用いて算出し、これを当該類似検索元画像と当該類似比較先画像との類似度として出力する。なお、ＤＰマッチングでは、周知のように、比較するラベルシーケンスが最も類似距離が小さくなるように、比較するラベルシーケンスを伸縮（比較する相手を次に進めないで我慢する）させて比較するという処理を行う（図１６の例では、最終解は１７０となり、ラインペナルティの和算値が５０→９５→１００→１１０→１２５→１４５→１７０となる経路を通る）。なお、何処まで伸縮（我慢）できるかを制約条件（整合窓の幅）で与えることも可能である。
【００５９】
○類似度算出処理の流れ
図１７は本実施形態にかかる画像処理装置における、２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。上記図１５及び図１６を参照して説明した処理を、図１７のフローチャートに従って更に詳細に説明する。
【００６０】
まず、ステップＳ１７０１において、類似比較先画像の行番号を表す変数ｉと、類似検索元画像の行番号を表す変数ｊを１に初期化し、ともに第１行目を示すように設定する。
【００６１】
次に、ステップＳ１７０２において、類似比較先画像の第ｉ行目のラベル列を取得する。例えば図１５の場合、ｉ＝１であれば「ａｂｃｄｅ」が取得される。そして、ステップＳ１７０３において、類似検索元画像の第ｊ行目のラベル列を取得する。例えば、図１５において、ｊ＝１であれば、「ＡＢＣＤＥ」が取得される。
【００６２】
次にステップＳ１７０４では、上記ステップＳ１７０２、Ｓ１７０３で得られた２つのラベル列間の距離（ラインペナルティ）を、図１１で説明した色セルペナルティマトリクスを用いて、ＤＰマッチングによって求める。ステップＳ１７０５では、ステップＳ１７０４で得られたラインペナルティをラインペナルティマトリクスに記憶する。
【００６３】
ステップＳ１７０３からステップＳ１７０５の処理を、類似検索元画像のすべての行について行う（ステップＳ１７０６、Ｓ１７０７）。さらにステップＳ１７０３からステップＳ１７０７の処理を、類似比較先画像のすべての行について行う（ステップＳ１７０８、Ｓ１７０９）。このようにして、類似検索元画像と類似比較先画像のそれぞれのラベル行間の距離がラベルペナルティとしてラインペナルティマトリクスに格納される。
【００６４】
最後に、ラインペナルティマトリクスを用いて、類似比較先画像の標準ライン行列「１２・・・ｉｍａｘ」と類似検索元画像の標準ライン行列「１２・・・ｊｍａｘ」との２次元ＤＰマッチングを行い、両者の類似度を算出する（ステップＳ１７１０）。なお、ここで、標準ライン行列とは、１から始まり、列方向に１ずつ増加する行列である。以上で類似度算出処理が終了する。
【００６５】
［画像間のずれ等の検出］
なお、上記ステップＳ１７０４及びステップＳ１７１０において、ＤＰマッチングを行ったときの経路を求めることができる。具体的には図１４および数式１の漸化式において、交点（ｉ，ｊ）上のペナルティｇ（ｉ，ｊ）を求める際、ｇ（ｉ−１，ｊ）、ｇ（ｉ−１，ｊ−１）、ｇ（ｉ，ｊ−１）のうちどのペナルティを使用したかを記憶しておき、最終解決定後、経路を遡ることにより、図１３のＡで描かれた経路を求めることができる。
【００６６】
そしてステップＳ１７０４において、ＤＰマッチングを行ったときの経路により、類似検索元画像と類似比較先画像の左右方向のずれ、拡縮の検出が可能である。例えば、ステップＳ１７０４において、ＤＰマッチングを行ったときの経路を求めた結果、図１８の（ａ）のようになった場合は、類似検索元画像と類似比較先画像との間に左右のずれはほとんど無い可能性がある。
【００６７】
また、図１８の（ｂ）のように経路の傾きは図１８の（ａ）とほとんど同じで経路が左上方向に偏っている場合は、類似検索元画像に対して類似比較先画像は右方向へずれたものである可能性があるし、逆に図１８の（ｃ）のようになった場合は、類似検索元画像に対して類似比較先画像は左方向へずれたものである可能性がある。
【００６８】
また、図１８の（ｄ）のように傾きが急になった場合は、類似検索元画像に対して類似比較先画像は左右方向に拡大されたものである可能性があるし、逆に図１８の（ｅ）のように傾きが緩やかになった場合は、類似検索元画像に対して類似比較先画像は左右方向に縮小されたものである可能性がある。
【００６９】
また、これらが複合されて、図１８の（ｆ）のように傾きが急になって左側に偏った場合は、類似比較先画像は類似検索元画像の左側が拡大されたものである可能性があるし、図１８の（ｇ）のように傾きが緩やかになって上側に偏った場合は、類似検索元画像は類似比較先画像の右側に縮小されたものである可能性がある。
【００７０】
ステップＳ１７０４の単体の結果は行ごとの特徴であり、複数行の傾向を総合することにより、類似検索元画像に対する類似比較先画像の傾きの検出が可能である。例えば、第１行目が図１８の（ａ）のようになっていて、第２行目、第３行目と下の行に移っていくにつれて経路が図１８の（ｂ）のようになっていった場合は、類似検索元画像に対して類似比較先画像は左斜めに傾いた状態である可能性がある。
【００７１】
ステップＳ１７１０において、ＤＰマッチングを行ったときの経路によっても、類似検索元画像と類似比較先画像の上下方向のずれ、拡縮の検出が可能である。例えば、ステップＳ１７１０において、ＤＰマッチングを行ったときの経路を求めた結果、図１８の（ａ）のようになった場合は、類似検索元画像と類似比較先画像との間に左右のずれはほとんど無い可能性がある。
【００７２】
また、図１８の（ｂ）のように経路の傾きは図１８の（ａ）とほとんど同じで経路が左上方向に偏っている場合は、類似検索元画像に対して類似比較先画像は下方向へずれたものである可能性があるし、逆に図１８の（ｃ）のようになった場合は、類似検索元画像に対して類似比較先画像は上方向へずれたものである可能性がある。
【００７３】
また、図１８の（ｄ）のように傾きが急になった場合は、類似検索元画像に対して類似比較先画像は上下方向に拡大されたものである可能性があるし、逆に図１８の（ｅ）のように傾きが緩やかになった場合は、類似検索元画像に対して類似比較先画像は上下方向に縮小されたものである可能性がある。
【００７４】
また、これらが複合されて、図１８の（ｆ）のように傾きが急になって左側に偏った場合は、類似比較先画像は類似検索元画像の上側が拡大されたものである可能性があるし、図１８の（ｇ）のように傾きが緩やかになって上側に偏った場合は、類似検索元画像は類似比較先画像の下側に縮小されたものである可能性がある。
【００７５】
更にステップＳ１７０４の複数行の結果とステップＳ１７１０の結果を総合することにより、類似比較先画像と類似検索元画像の画像データ間の特徴を検出することも可能である。
【００７６】
以上のようにして、ＤＰマッチングを水平・鉛直方向、すなわち２次元に行うことにより、水平や鉛直方向、更に斜め方向に画像アングルが変わったり、物体が移動していたりした場合でも画像検索を行うことが可能となる。また、ＤＰマッチングの時系列伸縮特性により、ズームアップ撮影画像やマクロ撮影画像を検索することも可能となる。
【００７７】
なお、本実施形態では、水平方向のブロック並びに対応するラベル列を用いて類似ライン行列を得たが、垂直方向のブロック並びに対応するラベル列を用いて類似ライン行列を得る場合も、上記と同様の手法で実現可能である。
【００７８】
また、本実施形態では、画像特徴量をラベル表現して類似画像検索を行っているが、画像特徴量をラベル化せずに類似画像検索を行う方法も上記の方法より容易に推測できる。
【００７９】
以上の説明から明らかなように、本実施形態にかかる画像処理装置では、画像特徴量群（特徴量空間を分割して得られる画像特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル列同士の距離を上述のＤＰマッチングとペナルティマトリクスとによって求める。これにより、２つの画像のブロック間の距離を算出する際の計算量を大幅に減少させることができるとともに、類似した画像特徴量が同じラベルで表されることになるので、類似画像の検索を良好に行うことができる。
【００８０】
また、（１）ラインペナルティマトリクスによるラベル列同士の距離概念を導入し、（２）比較するラベル位置を前後曖昧に移動させたうえで、トータルの距離が最小（類似度が最大）となるようなラベル行列の比較を実現する上記２次元ＤＰマッチングを導入したことにより、画像のアングルが多少変わっても類似画像検索を行うことが可能となり、雰囲気の似ている画像の検索が可能となる。
【００８１】
更に本実施形態にかかる画像処理装置では、インデックスデータベース（ラベル行列インデックス）を用いたことにより、類似画像検索を更に高速化させることが可能となった。
【００８２】
すなわち、本実施形態にかかる画像処理装置によれば、画像特徴量の配置を考慮して類似画像の高速な検索が行われるとともに、撮影条件の変動等による違いを吸収した類似画像の検索が可能となる（アングルが変った画像や物体の位置が変った画像、あるいは他の撮影条件が変動した画像等、従来、類似画像検索が難しかった画像について、画像特徴量のある程度の違いを吸収することにより、ロバストな類似画像検索を行うことが可能となる）。
【００８３】
＜第２の実施形態＞
上記第１の実施形態においては、自然画像を検索する場合を想定して説明したが、本発明は自然画像に限られるものではなく、ＣＧやＣＡＤ等の人工的な画像の検索にも適応可能であることはいうまでもない。
【００８４】
また、上記第１の実施形態では画像特徴量として色情報を選んだが、本発明はこれに限られるものではなく、その他の画像特徴量を分割画像ブロックごとに求めることで実施することも可能である。
【００８５】
また、上記第１の実施形態では１つの画像特徴量を用いて類似画像検索を行う場合について説明したが、本発明はこれに限られるものではなく、その他の画像特徴量を用いて類似画像検索を行った検索結果との論理演算を行うことにより、複数の画像特徴量からの高速な類似画像検索を実現することも可能である。
【００８６】
なお、１つの画像に対して複数の画像特徴量を用いて類似画像検索を行う場合には、上記第１の実施形態で得られる類似度を１つの新たなる画像特徴量とみなし、複数のパラメータを用いた多変量解析を行い統計的な距離尺度を用いて類似画像検索を行うようにしてもよい。また、上記第１の実施形態では、類似度が所定値を越える類似画像を検索結果として出力するが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよい。
【００８７】
さらに、曖昧度を指定することにより、ＤＰマッチングにおけるいわゆる整合窓の幅を変更することにより、検索の曖昧度を所望に設定できるようにしてもよい。図１９はＤＰマッチングにおける整合窓を説明する図である。図１９において直線ＡはＪ＝Ｉ＋ｒで表され、直線ＢはＪ＝Ｉ−ｒで表される。整合窓の幅はｒの値を変更することで変更することができる。したがって、キーボード１０４から曖昧度を指定することにより、このｒの値が変更されるように構成すれば、ユーザの所望の曖昧度（整合窓の幅）で類似度検索を行うことができる。
【００８８】
なお、上記第１の実施形態のような２次元ＤＰマッチングにあっては、水平方向のＤＰマッチングにおける整合窓の幅と、垂直方向のＤＰマッチングにおける整合窓の幅とを別々に設定できるようにしてもよい。或いは、両整合窓が異なる変化率で変化するように構成してもよい。このようにすれば、ユーザは、類似画像検索に際してよりきめ細かい曖昧さの設定を行えるようになる。例えば、図９に示されたようなブロック順序を用いた場合において、類似検索元画像中における注目物体の横方向への移動を許容したいような場合や、類似検索元画像が横長画像であるような場合には、横方向への曖昧度を大きくするために水平方向のＤＰマッチングにおける整合窓の幅をより大きくすればよい。
【００８９】
＜第３の実施形態＞
上記第１、第２の実施形態では、類似度の算出にあたり、２次元ＤＰマッチングを採用することとしたが、本発明はこれに限られず、変形予測に基づく複数の経路の中から最小となる距離を選択することで類似度を算出するようにしてもよい。以下に詳細を説明する。
【００９０】
［画像検索処理］
○類似度算出の流れ
図２０は本実施形態にかかる画像処理装置における類似度算出の手順を説明するフローチャートである。上記図１５及び図１６を参照しつつ、図２０のフローチャートを用いて類似度算出処理について説明する。
【００９１】
まず、ステップＳ２００１において、類似比較先画像の行番号を表す変数ｉと、類似検索元画像の行番号を表す変数ｊを１に初期化し、ともに第１行目を示すように設定する。次に、ステップＳ２００２において、類似比較先画像の第ｉ行目のラベル列を取得する。例えば図１５の場合、ｉ＝１であれば「ａｂｃｄｅ」が取得される。そして、ステップＳ２１０３において、類似検索元画像の第ｊ行目のラベル列を取得する。例えば、図１５において、ｊ＝１であれば、「ＡＢＣＤＥ」が取得される。
【００９２】
次にステップＳ２００４では、上記ステップＳ２００２、Ｓ２００３で得られた２つのラベル列間の距離（ラインペナルティ）を、図１１で説明したペナルティマトリクスを用いて、ＤＰマッチングによって求める。ステップＳ２００５では、ステップＳ２００４で得られたラインペナルティをラインペナルティマトリクスに記憶する。
【００９３】
以上のステップＳ２００３からステップＳ２００５の処理を、類似検索元画像のすべての行について行う（ステップＳ２００６、Ｓ２００７）。さらにステップＳ２００３からステップＳ２００７の処理を、類似比較先画像のすべての行について行う（ステップＳ２００８、Ｓ２００９）。以上のようにして、類似検索元画像と類似比較先画像のそれぞれのラベル行間の距離がラインペナルティとしてラインペナルティマトリクスに格納される。
【００９４】
次に、ステップＳ２０１０において、変形予測に基づく複数の経路での類似度を求め、それらの最小値を出力する。なお、変形予測に基づく複数の経路とは、予め定められた各直線（図２１の直線参照）をいい、該経路での類似度とは、該各直線近傍に位置する該ラインペナルティ（図２１の網点部分参照）を足し合わせ、それぞれにおいて算出された平均値をいう。
【００９５】
［画像間のずれ等の検出］
なお、上記第１の実施形態と同様、上記ステップＳ２００４において、ＤＰマッチングを行ったときの経路を求めることができる。具体的には図１４および数式１の漸化式において、交点（ｉ，ｊ）上のペナルティｇ（ｉ，ｊ）を求める際、ｇ（ｉ−１，ｊ）、ｇ（ｉ−１，ｊ−１）、ｇ（ｉ，ｊ−１）のうちどのペナルティを使用したかを記憶しておき、最終解決定後、経路を遡ることにより、図１３のＡで描かれた経路を求めることができる。
【００９６】
そしてステップＳ２００４において、ＤＰマッチングを行ったときの経路により、類似検索元画像と類似比較先画像の左右方向のずれ、拡縮の検出が可能である。例えば、ステップＳ２００４において、ＤＰマッチングを行ったときの経路を求めた結果、図１８の（ａ）のようになった場合は、類似検索元画像と類似比較先画像との間に左右のずれはほとんど無い可能性がある。
【００９７】
また、図１８の（ｂ）のように経路の傾きは図１８の（ａ）とほとんど同じで経路が左上方向に偏っている場合は、類似検索元画像に対して類似比較先画像は右方向へずれたものである可能性があるし、逆に図１８の（ｃ）のようになった場合は、類似検索元画像に対して類似比較先画像は左方向へずれたものである可能性がある。
【００９８】
また、図１８の（ｄ）のように傾きが急になった場合は、類似検索元画像に対して類似比較先画像は左右方向に拡大されたものである可能性があるし、逆に図１８の（ｅ）のように傾きが緩やかになった場合は、類似検索元画像に対して類似比較先画像は左右方向に縮小されたものである可能性がある。
【００９９】
また、これらが複合されて、図１８の（ｆ）のように傾きが急になって左側に偏った場合は、類似比較先画像は類似検索元画像の左側が拡大されたものである可能性があるし、図１８の（ｇ）のように傾きが緩やかになって上側に偏った場合は、類似検索元画像は類似比較先画像の右側に縮小されたものである可能性がある。
【０１００】
ステップＳ２１０４の単体の結果は行ごとの特徴であり、複数行の傾向を総合することにより、類似検索元画像に対する類似比較先画像の傾きの検出が可能である。例えば、第１行目が図１８の（ａ）のようになっていて、第２行目、第３行目と下の行に移っていくにつれて経路が図１８の（ｂ）のようになっていった場合は、類似検索元画像に対して類似比較先画像は左斜めに傾いた状態である可能性がある。
【０１０１】
ステップＳ２０１０において、類似度が算出されたときに使用された経路によっても、類似検索元画像と類似比較先画像の上下方向のずれ、拡縮の検出が可能である。例えば、ステップＳ２０１０において、使用された経路が図２１の（ａ）のようになっている場合は、類似検索元画像と類似比較先画像との間に左右のずれはほとんど無い可能性がある。
【０１０２】
また、図２１の（ｂ）のように経路の傾きは図２１の（ａ）とほとんど同じで経路が左上方向に偏っている場合は、類似検索元画像に対して類似比較先画像は下方向へずれたものである可能性があるし、逆に図２１の（ｃ）のようになっている場合は、類似検索元画像に対して類似比較先画像は上方向へずれたものである可能性がある。
【０１０３】
また、図２１の（ｄ）のように傾きが急になっている場合は、類似検索元画像に対して類似比較先画像は上下方向に拡大されたものである可能性があるし、逆に図２１の（ｅ）のように傾きが緩やかになっている場合は、類似検索元画像に対して類似比較先画像は上下方向に縮小されたものである可能性がある。
【０１０４】
また、これらが複合されて、図２１の（ｆ）のように傾きが急になって左側に偏っている場合は、類似比較先画像は類似検索元画像の上側が拡大されたものである可能性があるし、図２１の（ｇ）のように傾きが緩やかになって上側に偏っている場合は、類似検索元画像は類似比較先画像の下側に縮小されたものである可能性がある。
【０１０５】
更にステップＳ２００４の複数行の結果とステップＳ２０１０の結果を総合することにより、類似比較先画像と類似検索元画像の画像データ間の特徴を検出することが可能である。
【０１０６】
以上のようにして、ＤＰマッチングを水平方向に、変形予測に基づく経路を仮定したマッチングを垂直方向に、すなわち２次元にマッチングを行うことにより、水平や鉛直方向、更に斜め方向に画像アングルが変わったり、物体が移動していても検索を行うことが可能である。また、ＤＰマッチングもしくは変形予測に基づく経路を仮定したマッチングの時系列伸縮特性により、ズームアップ撮影画像やマクロ撮影画像をも検索することが可能となる。
【０１０７】
なお、本実施形態では、水平方向のブロック並びに対応するラベル列を用いて類似ライン行列を得たが、垂直方向のブロック並びに対応するラベル列を用いて類似ライン行列を得る場合についても、上記と同様の手法で実現可能である。
【０１０８】
また、本実施形態では、画像特徴量をラベル表現して類似画像検索を行っているが、画像特徴量をラベル化せずに類似画像検索を行う方法も上記の方法より容易に推測できる。
【０１０９】
以上説明したように、本実施形態にかかる画像処理装置では、画像特徴量群（特徴量空間を分割して得られる画像特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル列同士の距離を上述のＤＰマッチングとペナルティーマトリクスとによって求める。これにより、２つの画像のブロック間の距離を算出する際の計算量を大幅に減少させることができるとともに、類似した画像特徴量が同じラベルで表されることになるので、類似画像の検索を良好に行うことができる。
【０１１０】
さらに、（１）ラインペナルティマトリクスによるラベル列同士の距離概念を導入し、（２）比較するラベル位置を前後曖昧に移動させたうえで、変形予測に基づく複数の経路の中からトータルの距離が最小（類似度が最大）となるような経路を選択することにより、画像のアングルが多少変わっても検索することが可能となり、雰囲気の似ている画像の検索が可能となる。
【０１１１】
更に本実施形態にかかる画像処理装置では、インデックスデータベース（ラベル行列インデックス）を用いたことにより、類似画像検索が更に高速化する。
【０１１２】
すなわち、本実施形態にかかる画像処理装置によれば、画像特徴量の配置を考慮した類似画像の高速な検索が行われるとともに、撮影条件の変動等による違いを吸収した類似画像の検索が可能となる（アングルが変った画像や物体の位置が変った画像、あるいは他の撮影条件が変動した画像等、従来、類似画像検索が難しかった画像について、画像特徴量のある程度の違いを吸収することにより、ロバストな類似画像検索を行うことが可能となる。
【０１１３】
＜第４の実施形態＞
上記第３の実施形態においては、自然画像を検索する場合を想定して説明したが、本発明は自然画像に限られるものではなく、ＣＧやＣＡＤ等の人工的な画像の検索にも適応可能であることはいうまでもない。
【０１１４】
また、上記第１の実施形態では画像特徴量として色情報を選んだが、本発明はこれに限られるものではなく、その他の画像特徴量を分割画像ブロックごとに求めることで実施することも可能である。
【０１１５】
また、上記第３の実施形態では１つの画像特徴量を用いて類似画像検索を行う場合について説明したが、本発明はこれに限られるものではなく、その他の画像特徴量を用いて類似画像検索を行った検索結果との論理演算を行うことにより、複数の画像特徴量からの高速な類似画像検索を実現することも可能である。
【０１１６】
なお、１つの画像に対して複数の画像特徴量を用いて類似画像検索を行う場合には、上記第３の実施形態で得られる類似度を１つの新たなる画像特徴量とみなし、複数のパラメータを用いた多変量解析を行い統計的な距離尺度を用いて類似画像検索を行うようにしてもよい。また、上記第１の実施形態では、類似度が所定値を越える類似画像を検索結果として出力するが、類似度の高い画像から順に前もって指定された個数の画像を検索結果として出力するようにしてもよい。
【０１１７】
さらに、曖昧度を指定することにより、ＤＰマッチングにおけるいわゆる整合窓の幅を変更することにより、検索の曖昧度を所望に設定できるようにしてもよい。図１９はＤＰマッチングにおける整合窓を説明する図である。図１９において直線ＡはＪ＝Ｉ＋ｒで表され、直線ＢはＪ＝Ｉ−ｒで表される。整合窓の幅はｒの値を変更することで変更することができる。したがって、キーボード１０４から曖昧度を指定することにより、このｒの値が変更されるように構成すれば、ユーザの所望の曖昧度（整合窓の幅）で類似度検索を行うことができる。
【０１１８】
同様に、変形予測に基づく経路作成の幅を変更することにより、検索の曖昧度を所望に設定可能とすることもできる。図２２は経路作成の幅を説明する図である。図２２において直線ＡはＪ＝Ｉ＋ｒで表され、直線ＢはＪ＝Ｉ−ｒで表される。経路作成の幅はｒの値を変更することで行える。図２２の直線Ｃ、直線Ｄ、直線Ｅのように、直線Ａと直線Ｂの間で変形予測に基づいて経路が作成される。したがって、キーボード１０４から曖昧度を指定することにより、このｒの値が変更されるように構成すれば、ユーザの所望の曖昧度（経路作成の幅）で類似度検索を行えるようになる。
【０１１９】
なお、上記第３の実施形態のような類似度検索にあっては、水平方向のＤＰマッチングにおける整合窓の幅と、垂直方向の変形予測に基づく経路仮定のマッチングにおける経路作成の幅とを別々に設定できるようにしてもよい。或いは、両幅が異なる変化率で変化するように構成してもよい。このようにすれば、ユーザは、類似画像検索に際してよりきめ細かい曖昧さの設定を行えるようになる。例えば、図９に示されたようなブロック順序を用いた場合において、検索元の画像中における注目物体の横方向への移動を許容したいような場合や、検索元の画像が横長画像であるような場合には、横方向への曖昧度を大きくするために水平方向のマッチングにおける経路作成の幅をより大きくすればよい。
【０１２０】
＜他の実施形態＞
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用してもよい。
【０１２１】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。
【０１２２】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０１２３】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピ（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【０１２４】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１２５】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１２６】
【図１】本発明の各実施形態に共通する画像処理装置の制御構成を示すブロック図である。
【図２】本発明の各実施形態に共通する画像処理装置の機能構成を示すブロック図である。
【図３】画像蓄積部における画像データの格納状態を説明する図である。
【図４】画像管理ＤＢによる画像データの格納形態を説明する図である。
【図５】ラベル成分インデックスのデータ構成例を示す図である。
【図６】画像登録処理の手順を説明するフローチャートである。
【図７】画像のブロック分割の一例を示す図である。
【図８】多次元特徴量空間を説明するための図である。
【図９】ラベル行列を生成する際のブロック順序列を説明する図である。
【図１０】類似画像検索処理の手順を説明するフローチャートである。
【図１１】ラベル列を比較し類似度を求める際に用いるラベル間のペナルティマトリクスの一例を示す図である。
【図１２】類似検索元画像のラベル行列と類似比較先画像のラベル行列の一例を示す図である。
【図１３】ＤＰマッチングによるラベル列間の距離の算出を説明する図である。
【図１４】ＤＰマッチングによる経路選択を説明するための図である。
【図１５】類似度算出処理を説明する図である。
【図１６】類似度算出処理を説明する図である。
【図１７】２次元ＤＰマッチングによる類似度算出の手順を説明するフローチャートである。
【図１８】２次元ＤＰマッチングの経路例を説明する図である。
【図１９】ＤＰマッチングにおける整合窓の調整を説明する図である。
【図２０】類似度算出の手順を説明するフローチャートである。
【図２１】変形予測に基づく複数の経路例を説明する図である。
【図２２】変形予測に基づく経路作成の幅を説明する図である。
【図１】
2006146715.tif 000004
【図２】
2006146715.tif 000005
【図３】
2006146715.tif 000006
【図４】
2006146715.tif 000007
【図５】
2006146715.tif 000008
【図６】
2006146715.tif 000009
【図７】
2006146715.tif 000010
【図８】
2006146715.tif 000011
【図９】
2006146715.tif 000012
【図１０】
2006146715.tif 000013
【図１１】
2006146715.tif 000014
【図１２】
2006146715.tif 000015
【図１３】
2006146715.tif 000016
【図１４】
2006146715.tif 000017
【図１５】
2006146715.tif 000018
【図１６】
2006146715.tif 000019
【図１７】
2006146715.tif 000020
【図１８】
2006146715.tif 000021
【図１９】
2006146715.tif 000022
【図２０】
2006146715.tif 000023
【図２２】
2006146715.tif 000024
【図２１】
2006146715.tif 000025