(57)【要約】【課題】従来の類似度算出方法は乗算を含むため計算負荷が大きく大規模な画像データベースで画像検索をリアルタイムで提供することは困難であった。色情報を用いた類似判定では、精度が低く誤検出が多いという問題があった。【解決手段】質問画像を特徴付ける、画像の局所的特徴を含む第１の特徴パラメータ群を算出するパラメータ算出手段１１５、類似度を算出する類似度算出手段１２０、質問画像と被検索画像が同一・類似か否かを判定する判定手段１２５、被検索画像およびこれらを特徴付ける第２の特徴パラメータ群を格納する画像データベース１３０を含む画像検索システム１００を提供する。【選択図】        図１
2004318365.tif 000002
【特許請求の範囲】
【請求項１】
複数の被検索画像を含む画像データベースから所望の質問画像を検索する画像検索システムであって、
フラクタルブロック符号化技法を用いて、前記質問画像から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、前記質問画像を特徴付ける第１の特徴パラメータ群を算出するパラメータ算出手段と、
複数の被検索画像、および、これらに関連付けられた複数の第２の特徴パラメータ群を格納する画像データベースであって、前記第２の特徴パラメータ群が、フラクタルブロック符号化技法を用いて、前記複数の被検索画像の各々から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、予め算出されたこれら複数の被検索画像の各々を特徴付けるような前記第２の特徴パラメータ群である、画像データベースと、
前記第１の特徴パラメータ群と、前記第２の特徴パラメータ群とに基づき、前記質問画像に対する前記被検索画像の各々の類似度を算出する類似度算出手段と、
を含む画像検索システム。
【請求項２】
請求項１に記載の画像検索システムにおいて、
前記第１および第２の特徴パラメータ群は、
前記アフィンパラメータのうちの位置パラメータのみを含む、
ことを特徴とする画像検索システム。
【請求項３】
請求項１または２に記載の画像検索システムにおいて、
前記位置パラメータは、前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックに関連する、
ことを特徴とする画像検索システム。
【請求項４】
請求項１〜３のいずれか１項に記載の画像検索システムにおいて、
前記パラメータ算出手段は、
前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックを選択し、他方、重なり合いを許して前記質問画像から複数のドメインブロックを切り出し、これらを縮小アフィン変換して複数の縮小ドメインブロックを得て、前記選択された上位複数ブロックの各々を近似する縮小ドメインブロックをそれぞれ求め、求めたこれら複数の縮小ドメインブロックの位置パラメータのみを含むような、前記質問画像を特徴付ける第１の特徴パラメータ群を算出する手段を含み、
前記第２の特徴パラメータ群は、
前記フラクタルブロック符号化技法を用いて、前記被検索画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、
高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックを選定し、さらに、前記被検索画像から重なり合いを許して複数のドメインブロックを切り出し、これらを縮小アフィン変換して複数の縮小ドメインブロックを得て、前記上位複数ブロックを近似する縮小ドメインブロックをそれぞれ求め、この求めた複数の縮小ドメインブロックの位置パラメータのみを含むような、予め算出されたこれら複数の被検索画像の各々を特徴付ける、
ことを特徴とする画像検索システム。
【請求項５】
請求項１〜４のいずれか１項に記載の画像検索システムにおいて、
前記類似度算出手段は、前記第１の特徴パラメータ群の各成分と前記第２の特徴パラメータ群の各成分との差を二乗したものに基づき、前記類似度を算出する、
ことを特徴とする画像検索システム。
【請求項６】
請求項１〜４のいずれか１項に記載の画像検索システムにおいて、
前記類似度算出手段は、前記第１の特徴パラメータ群の各成分と前記第２の特徴パラメータ群の各成分とが同一か否かによって２進符号化したものに基づき、前記類似度を算出する、
ことを特徴とする画像検索システム。
【請求項７】
請求項１〜６のいずれか１項に記載の画像検索システムにおいて、
前記類似度が高い上位複数画像を前記画像データベースから読み出しユーザにネットワークを介して送信する手段、および／または、前記類似度が高い上位複数画像を前記画像データベースから読み出し表示装置に表示する手段、を含む
ことを特徴とする画像検索システム。
【請求項８】
請求項１〜６のいずれか１項に記載の画像検索システムにおいて、
前記複数の被検索画像から、所定の閾値と前記複数の非検索画像の類似度の各々とを比較して、前記質問画像に一致或いは類似するものを判定する判定手段、をも含むこと特徴とする画像検索システム。
【請求項９】
請求項８に記載の画像検索システムにおいて、
一致或いは類似するものと判定された画像を前記画像データベースから読み出しユーザにネットワークを介して送信する手段、および／または、一致或いは類似するものと判定された画像を前記画像データベースから読み出し表示装置に表示する手段、を含む
ことを特徴とする画像検索システム。
【請求項１０】
複数の被検索画像を含む画像データベースから所望の画像を検索する画像検索方法であって、
フラクタルブロック符号化技法を用いて、前記質問画像から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、前記質問画像を特徴付ける第１の特徴パラメータ群を算出するパラメータ算出ステップと、
複数の被検索画像、および、これらに関連付けられた複数の第２の特徴パラメータ群を格納する画像データベースに予め格納する格納ステップであって、前記第２の特徴パラメータ群が、フラクタルブロック符号化技法を用いて、前記複数の被検索画像の各々から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、これら複数の被検索画像の各々を特徴付けるような前記第２の特徴パラメータ群である、格納ステップと、
前記第１の特徴パラメータ群と、前記画像データベースに格納されている前記第２の特徴パラメータ群とに基づき、前記質問画像に対する前記被検索画像の各々の類似度を演算手段を用いて算出する類似度算出ステップ、
を含むことを特徴とする画像検索方法。
【請求項１１】
請求項１０に記載の画像検索方法において、
前記第１および第２の特徴パラメータ群が、
前記アフィンパラメータのうちの位置パラメータのみを含み、
前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックに基づき前記位置パラメータを求めるステップ、
をも含むことを特徴とする画像検索方法。
【請求項１２】
複数の被検索画像を含む画像データベースから所望の画像を検索する画像検索方法をコンピュータに実行させるためのプログラムであって、
前記方法は、
フラクタルブロック符号化技法を用いて、質問画像から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、前記質問画像を特徴付ける第１の特徴パラメータ群を算出するパラメータ算出ステップと、
複数の被検索画像、および、これらに関連付けられた複数の第２の特徴パラメータ群を格納する画像データベースに予め格納する格納ステップであって、前記第２の特徴パラメータ群が、フラクタルブロック符号化技法を用いて、前記複数の被検索画像の各々から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、これら複数の被検索画像の各々を特徴付けるような前記第２の特徴パラメータ群である、格納ステップと、
前記第１の特徴パラメータ群と、前記画像データベースに格納されている前記第２の特徴パラメータ群とに基づき、前記質問画像に対する前記被検索画像の各々の類似度を算出する類似度算出ステップと、
を含むことを特徴とするプログラム。
【請求項１３】
請求項１２に記載のプログラムにおいて、
前記第１および第２の特徴パラメータ群が、
前記アフィンパラメータのうちの位置パラメータのみを含み、
前記方法は、
前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックに基づき前記位置パラメータを求めるステップ、をも含む、
ことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像検索システム、画像検索方法およびそのプログラムに関するものである。
【０００２】
【従来の技術】
インターネットの普及や記憶装置の大容量化などに伴って、所望の類似画像を大量の画像を格納した大規模な画像データベースからネットワークを介して検索する需要が高まっており、類似画像を検出する各種手法が提案されている。それらが提案する画像の類似度の算出手段は、計算負荷が高い「乗算」が含まれて定義されているものがあり、このような乗算を含む算出手段は高速処理の障害となり得る。特に、データベースのさらなる大規模化が見込まれるため、乗算を含むアルゴリズムでは、応答性が悪化してユーザにリアルタイムで検索結果を提供することは一層困難となる。
【０００３】
また、乗算を必要としない手法も提案されているが、それらは主に色情報（ＲＧＢまたはＣＭＹＫなどの各成分の割合やヒストグラム）を利用して類似画像を検出しているため、視覚的には類似していない画像であっても類似画像と判定するような誤検出が生じる。このような、誤検出を取り除くためにはユーザの労力が必要となり、大量の画像を含むデータベースを検索対象とする場合には、色情報に基づく技術を利用することは困難である。従って、高い検索精度、および、計算量の低減化の両者を満足する検索尺度（即ち、画像の類似度）はいまだ存在していないと言える。
【０００４】
画像検索を実現する直接的技術ではないが、従来技術としてＪａｃｑｕｉｎが提案した画像を符号化する技術「フラクタルブロック符号化（非特許文献１、２、３を参照されたい。）」がある。これらは、画像内における部分的な自己相似性を有するフラクタル図形で近似することによって画像を符号化（圧縮）する技法であるが、これらに基づき類似度を算出する手法は提案されていない。
【非特許文献１】
Ａ．Ｅ．Ｊａｃｑｕｉｎ，  ”Ｉｍａｇｅ  Ｃｏｄｉｎｇ  Ｂａｓｅｄ  ｏｎ  ａ  Ｆｒａｃｔａｌ  Ｔｈｅｏｒｙ  ｏｆ  Ｉｔｅｒａｔｅｄ  Ｃｏｎｓｔｒａｃｔｉｖｅ  Ｉｍａｇｅ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ”，  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  ＩＰ  Ｖｏｌ．ＩＰ−１  Ｎｏ．１  ｐｐ．１８−３０  （Ｊａｎ．１９９２）
【非特許文献２】
Ａ．Ｅ．Ｊａｃｑｕｉｎ，  ”Ｆｒａｃｔａｌ  Ｉｍａｇｅ  Ｃｏｄｉｎｇ  ：  Ａ  Ｒｅｖｉｅｗ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  Ｖｏｌ．８１  Ｎｏ．１０  ｐｐ．１４５１−１４６５  （Ｏｃｔ．１９９３）
【非特許文献３】
Ｍ．Ｆ．Ｂａｒｎｓｌｅｙ  ａｎｄ  Ｌ．Ｐ．Ｈｕｒｄ，  ”Ｆｒａｃｔａｌ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ”，  ＡＫ  ＰＥＴＥＲＳ  （１９９２）
【０００５】
【発明が解決しようとする課題】
上述したように、従来の類似度算出方法は、乗算を含むため計算負荷が大きく大規模な画像データベースで画像検索をリアルタイムで提供することは困難であった。また、色情報を用いた類似度判定では、精度が低く誤検出が多いという問題があった。
従って、本発明の目的は、フラクタルブロック符号化技法を利用して上述した諸課題を解決し、高速かつ高精度の画像検索技法を提供することである。より詳細には、フラクタルブロック符号化技法を発展させた、本発明者が提案する２−ＤファンクショナルＡＲモデル（これについては後で詳述する。）を用いて高速かつ高精度の画像検索技法を提供することである。
【０００６】
【課題を解決するための手段】
本発明による画像検索システムは、
複数（大量）の被検索画像を含む画像データベースから所望の質問画像を検索する画像検索システムであって、
ユーザにユーザが所望する検索対象の質問画像を入力するよう、またはネットワークを介して送信するよう促す入力要求手段（オプション）と、
検索対象の質問画像を受信する受信手段（オプション）と、
前記質問画像を被検索画像と同じ画素サイズおよび階調（例えば２５６×２５６画素、２５５階調のサムネイル画像）に変換する変換する変換手段（オプション）と、
フラクタルブロック符号化技法を用いて、前記質問画像から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、前記質問画像を特徴付ける第１の特徴パラメータ群を算出するパラメータ算出手段と、
複数の被検索画像、および、これらに関連付けられた複数の第２の特徴パラメータ群を格納する画像データベースであって、前記第２の特徴パラメータ群が、フラクタルブロック符号化技法を用いて、前記複数の被検索画像の各々から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、予め算出されたこれら複数の被検索画像の各々を特徴付けるような前記第２の特徴パラメータ群である、画像データベースと、
前記第１の特徴パラメータ群と、前記第２の特徴パラメータ群とに基づき、前記質問画像に対する前記被検索画像の各々の類似度を算出する類似度算出手段と、
を含むものである。
本発明によれば、画像の局所的特徴を表す上述したような第１および第２の特徴パラメータ群のみを使用して類似度を算出することにより、従来技法よりも計算負荷を軽減し、高精度な画像データベース検索を可能とする。また、本発明では、種々のアフィンパラメータを利用しており極めて厳密に画像の類似度を算出するため、極めて高い精度で画像が類似・一致するのかを判定することが可能となる。即ち、本発明は画像の完全一致か否かを判定するような用途に適している。しかしながら、本構成では、扱うパラメータがアフィンパラメータを全て含むため、上記のごとく極めて高精度に類似・一致するのか否かを判定可能であるが、その反面、後述する本発明の別構成よりパラメータ量が多いため計算コストが若干多くかかり、曖昧検索などで大まかな検索結果の閲覧を所望するような用途には向かない。この点について後述する別構成の発明で対処可能である。
また、本発明は、フラクタルブロック符号化を利用しているため、フラクタルブロック符号化の性質から、質問画像や被検索画像が何らかの画像処理ソフトによって処理されたり、電子透かしが埋め込まれるなどの改竄処理を施されたり、或いは、様々なノイズを含んだりして画質が劣化・変化していても、高精度に画像の同一性や類似性を判定することを可能にする。
【０００７】
また、本発明による画像検索システムは、
前記第１および第２の特徴パラメータ群は、
前記アフィンパラメータのうちの位置パラメータのみを含む、
ことを特徴とする。
本発明によれば、精度をほとんど損なうことなく、「前段落の発明」よりもパラメータを限定しているため、計算コストを大幅に軽減して高速な画像データベース検索を可能とする。
【０００８】
また、本発明による画像検索システムは、
前記位置パラメータは、前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し（分割）、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックに関連する、
ことを特徴とする。
本発明によれば、輝度値の分散が大きいものなど「局所的特徴がより大きなデータ」のみに限定することによって、精度をほとんど損なわずに、計算コストを低減でき、さらに高速な画像データベース検索を可能とする。
【０００９】
また、本発明による画像検索システムは、
前記パラメータ算出手段は、
前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し（分割し）、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックを選択し、他方、重なり合いを許して前記質問画像から複数のドメインブロックを切り出し、これらを縮小アフィン変換して複数の縮小ドメインブロックを得て、前記選択された上位複数ブロックの各々を（最も良く）近似する縮小ドメインブロックをそれぞれ求め、求めたこれら複数の縮小ドメインブロックの位置パラメータ（例えば当該ブロックの左上の頂点の座標）のみを含むような、前記質問画像を特徴付ける第１の特徴パラメータ群を算出する手段を含み、
前記第２の特徴パラメータ群は、
前記フラクタルブロック符号化技法を用いて、前記被検索画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックを選定し、さらに、前記被検索画像から重なり合いを許して複数のドメインブロックを切り出し、これらを縮小アフィン変換して複数の縮小ドメインブロックを得て、前記上位複数ブロックを（最も良く）近似する縮小ドメインブロックをそれぞれ求め、この求めた複数の縮小ドメインブロックの位置パラメータのみを含むような、予め算出されたこれら複数の被検索画像の各々を特徴付ける、ことを特徴とする。
本発明によれば、上記のごとく「画像の局所的特徴」を効果的に特徴付けるような輝度値の分散の大きい、或いは高周波成分の多い、或いは近傍画素との相関が低い「複数のレンジブロック」や「複数の縮小ドメインブロック」を利用することによって計算コストを大幅に軽減し、精度をほとんど損なわずに、より高速な画像データベース検索を可能とする。また、本発明は、「画像の局所的特徴」を効果的に特徴付けるようなブロックに基づくパラメータを利用しているため、改竄処理、ノイズ、画質劣化・変化などに堅牢な類似度の算出が可能となり、より高精度に画像の同一性や類似性を判定することを可能にする。換言すれば、本構成は、厳密な画像の同一性を判定するよりは、多少ノイズが入ったような画像同士であっても、検索漏れにならずに類似画像として抽出するような用途に適する。
【００１０】
また、本発明による画像検索システムは、
前記類似度算出手段は、前記第１の特徴パラメータ群の各成分と前記第２の特徴パラメータ群の各成分との差を二乗したもの（例えばこれらの総和）に基づき、前記類似度を算出する、
ことを特徴とする。
本発明によれば、画像の局所的特徴を表す特徴パラメータ群の各成分同士の差を二乗し総和を求めるといった簡易な計算手法で類似度を求めることができ、高精度かつ高速な画像データベース検索を可能とする。
【００１１】
また、本発明による画像検索システムは、
前記類似度算出手段が、前記第１の特徴パラメータ群の各成分と、前記複数の第２の特徴パラメータ群の各々（即ち、個々の画像の特徴パラメータ群）の各成分とが同一か否かによって２進符号化（例えば、同一の場合は１とし、否の場合は０とする）したものの総和に基づき、前記類似度を算出する、
ことを特徴とする。
本発明によれば、乗算を含まないため計算コストを顕著に低減させることができ、大規模の大量の被検索画像から検索する場合であっても高速かつ精度良く所望の画像、或いはこれに類似する画像をリアルタイムで検出することが可能となる。
【００１２】
また、本発明による画像検索システムは、
前記類似度が高い上位複数画像（例えば、類似度の上位１０個の原画データ或いはサムネイル画像データ）を前記画像データベースから読み出しユーザにネットワークを介して送信する手段、および／または、前記類似度が高い上位複数画像を前記画像データベースから読み出し表示装置に表示する手段、を含む
ことを特徴とする。
本発明によれば、ユーザは、類似度の高い複数の画像を容易かつ簡便に閲覧することが可能となり、検索システムの操作性が顕著に向上する。
【００１３】
また、本発明による画像検索システムは、
前記複数の被検索画像から、所定の閾値と前記複数の非検索画像の類似度の各々とを比較して、前記質問画像に一致或いは類似するものを判定（選出）する判定手段、
をも含むこと特徴とする。
これは、類似度の定義によって異なるが、例えば、類似度が０に近いほど類似するという定義の場合は、所定の閾値未満のものを一致或いは類似するものと判定し、類似度が１（１００％）に近いほど類似するという定義の場合は、所定の閾値よりも大きなものを一致或いは類似するものと判定する。
【００１４】
また、本発明による画像検索システムは、
一致或いは類似するものと判定された画像を前記画像データベースから読み出しユーザにネットワークを介して送信する手段、および／または、一致或いは類似するものと判定された画像を前記画像データベースから読み出し表示装置に表示する手段、を含む
ことを特徴とする。
【００１５】
上述したように本発明の解決手段をシステム（装置）として説明してきたが、本発明はこれらに実質的に相当する方法、プログラム、プログラムを記録した記憶媒体としても実現され得るものであり、本発明の範囲にはこれらも包含されるものと理解されたい。
例えば、本発明による複数（大量）の被検索画像を含む画像データベースから所望の画像を検索する画像検索方法は、
ユーザにユーザが所望する検索対象の質問画像を入力するよう、またはネットワークを介して送信するよう促す入力要求ステップ（オプション）と、
検索対象の質問画像を受信する受信ステップ（オプション）と、
前記質問画像を被検索画像と同じ画素サイズおよび階調（例えば２５６×２５６画素、２５５階調のサムネイル画像）に変換する変換する変換手段（オプション）と、
フラクタルブロック符号化技法を用いて、前記質問画像から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、前記質問画像を特徴付ける第１の特徴パラメータ群を算出するパラメータ算出ステップと、
複数の被検索画像、および、これらに関連付けられた複数の第２の特徴パラメータ群を格納する画像データベースに予め格納する格納ステップであって、前記第２の特徴パラメータ群が、フラクタルブロック符号化技法を用いて、前記複数の被検索画像の各々から演算手段を用いて算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、これら複数の被検索画像の各々を特徴付けるような前記第２の特徴パラメータ群である、格納ステップと、
前記第１の特徴パラメータ群と、前記画像データベースに格納されている前記第２の特徴パラメータ群とに基づき、前記質問画像に対する前記被検索画像の各々の類似度を、演算手段を用いて算出する類似度算出ステップと、
を含むものである。
【００１６】
また、本発明による画像検索方法は、
前記第１および第２の特徴パラメータ群が、
前記アフィンパラメータのうちの位置パラメータのみを含み、
前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックに基づき前記位置パラメータを求めるステップ、
をも含むことを特徴とする。
【００１７】
例えば、本発明によるプログラムは、
複数（大量）の被検索画像を含む画像データベースから所望の画像を検索する画像検索方法をコンピュータに実行させるためのプログラムであって、
前記方法は、
ユーザにユーザが所望する検索対象の質問画像を入力するよう、またはネットワークを介して送信するよう促す入力要求ステップ（オプション）と、
検索対象の質問画像を受信する受信ステップ（オプション）と、
前記質問画像を被検索画像と同じ画素サイズおよび階調（例えば２５６×２５６画素、２５５階調のサムネイル画像）に変換する変換する変換手段（オプション）と、
フラクタルブロック符号化技法を用いて、前記質問画像から算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、前記質問画像を特徴付ける第１の特徴パラメータ群を算出するパラメータ算出ステップと、
複数の被検索画像、および、これらに関連付けられた複数の第２の特徴パラメータ群を画像データベース（記憶装置）に予め格納する格納ステップであって、前記第２の特徴パラメータ群が、フラクタルブロック符号化技法を用いて、前記複数の被検索画像の各々から演算手段を用いて算出したＩＦＳパラメータに含まれるアフィンパラメータを含む、これら複数の被検索画像の各々を特徴付けるような前記第２の特徴パラメータ群である、格納ステップと、
前記第１の特徴パラメータ群と、前記画像データベースに格納されている前記第２の特徴パラメータ群とに基づき、前記質問画像に対する前記被検索画像の各々の類似度を演算手段を用いて算出する類似度算出ステップと、
を含むことを特徴とするプログラム。
【００１８】
また、本発明によるプログラムは、
前記第１および第２の特徴パラメータ群が、
前記アフィンパラメータのうちの位置パラメータのみを含み、
前記方法は、
前記フラクタルブロック符号化技法を用いて、前記質問画像から相互に重なり合わない複数のレンジブロックを切り出し、これらレンジブロックのうち、高周波成分が多い上位複数ブロック、近傍画素との相関が低い上位複数ブロック、或いは、輝度値の分散の大きい上位複数ブロック、の少なくとも１つの上位複数ブロックに基づき前記位置パラメータを求めるステップ、をも含む、
ことを特徴とする。
【００１９】
【発明の実施の形態】
以下、諸図面を参照しつつ本発明の実施態様を詳細に説明する。
図１は、本発明による画像検索システムの一例を示すブロック図である。図に示すように、画像検索システム１００は、ユーザに所望する質問画像の入力を促す入力要求手段１０５、入力された質問画像を受信する受信手段１１０、第１の特徴パラメータ群を算出するパラメータ算出手段１１５、類似度を算出する類似度算出手段１２０、質問画像と被検索画像が同一・類似か否かを判定する判定手段１２５、被検索画像およびこれらを特徴付ける第２の特徴パラメータ群を格納する画像データベース１３０、一致或いは類似するものと判定された画像をユーザに送信する送信手段１３５、検索結果を表示する表示手段１４０を含むものである。本システム１００は、直接的にローカルのユーザＰＣ１６０に接続され、さらに、ネットワーク１５０を介してリモートの多数のユーザＰＣ１６０にも接続されている。ユーザはこれらのユーザＰＣ１６０を用いて本システム１００にアクセスし、所望の画像に一致或いは類似する画像を検索・抽出することが可能である。データ容量、計算コスト、著作権上の観点から画像データベース１３０に格納される非検索画像は画素および階調を劣化させたサムネイル画像を用いることが好適であるが、もちろんオリジナル画像を格納すること可能である。本システム１００で得た検索結果に満足し、検索結果の非検索画像のオリジナル画像の入手をユーザが所望する場合は、本システム１００は、原画像を含む第２のオリジナル画像データベースから当該画像を取り出して、有料でユーザに提供することも可能である。
【００２０】
図２は、本発明による画像検索方法の一例を示すフローチャートである。図に示すように、本方法は、ユーザに質問画像の入力を要求し（Ｓ１００）、ユーザから送信・入力された質問画像を受信する（Ｓ１１０）。次に質問画像から当該画像の局所的特徴を表す第１の特徴パラメータ群（行列）を算出する（Ｓ１２０）。そして、第１の特徴パラメータ群と、データベースに格納された予め算出してある第２の特徴パラメータ群とに基づき、当該質問画像に対する被検索画像の類似度をそれぞれ算出する（Ｓ１３０）。類似度が上位数個の画像を画像データベースから取り出し表示装置に表示する（Ｓ１４０）。
【００２１】
図３は、第１の特徴パラメータ群を算出する手順（図２で示したステップＳ１２０に相当する）を詳細に説明するフローチャートである。図に示すように、質問画像を重なり合いを許さずに分割しレンジブロックを得る（Ｓ２００）。分割したレンジブロックのうち、輝度値の分散の大きい上位Ｌ個のブロックを選択する（Ｓ２１０）。次に、質問画像を重なり合いを許して分割しドメインブロックを得る（Ｓ２２０）。選択した輝度値の分散の大きいレンジブロックを近似するドメインブロックを求めるために、各ドメインブロックを縮小アフィン変換して縮小ドメインブロックを得る（Ｓ２３０）。縮小アフィン変換ドメインブロックのうち、前記の輝度値の分散の大きいレンジブロックを近似する上位Ｎ個のブロックを求め、これらのブロックの座標を位置パラメータとする（Ｓ２４０）。
【００２２】
２−ＤファンクショナルＡＲモデル
本発明によるシステムや方法などは、本発明者が新たに提案する画像識別のための２−ＤファンクショナルＡＲモデルに基づくものであるがこのモデルについて詳細に説明する。
はじめに、画像ｘおよび白色ノイズ画像ｕの輝度値を、それぞれｘ（ｉ，ｊ）、ｕ（ｉ，ｊ）とする。ここでｉ＝０，…，Ｌ、ｊ＝０，…，Ｍとする。画像ｘを相互に重なり合わないＮ×Ｎ画素のブロックに分割し、［Ｌ／Ｎ］×［Ｍ／Ｎ］個（ここでは便宜上”［  ］”を用いたが、これは小数点以下切り捨て、即ち整数化の処理を意図する。）の参照ブロック（即ちレンジブロック）ＸＲｉ，ｊを得る。ここでｉ，ｊは当該ブロックの左上の頂点のｘ，ｙ座標をそれぞれ表す。白色ノイズ画像ｕについても同様にブロックに分割し、［Ｌ／Ｎ］×［Ｍ／Ｎ］個のブロックＵｉｊを得る。
【００２３】
さらに、画像ｘを相互に重なり合いを許してαＮ×αＮ画素（α∈｛１，２，…，ｍｉｎ（［Ｌ／Ｎ］，［Ｍ／Ｎ］）｝）のブロックを切り出し（分割）、（Ｌ−αＮ＋１）×（Ｍ−αＮ＋１）個のドメインブロックＸＤｉ，ｊ（便宜上、このような表記を用いたが、正確にはＤはＸの上付き文字、ｉ，ｊはＸの下付き文字であることを意図する。以降、同様の表記がある場合も同じことを意図する）を得る。このようなブロック分割において、２−ＤファンクショナルＡＲモデルは下式のように定義される。
【数１】
2004318365.tif 000003
ここで、
【数２】
2004318365.tif 000004
である。ドメインブロックＸＤｉ，ｊにおける画素（ｋ，ｌ）が輝度値
【数３】
2004318365.tif 000005
を持ち、ドメインブロック
【数４】
2004318365.tif 000006
における画素（ｋ，ｌ）が輝度値
【数５】
2004318365.tif 000007
を持つとき、関数Ｆｓ，ｔは下式のようにＸＤｉ，ｊをＸＤ’ｉ，ｊに変換する。
【００２４】
【数６】
2004318365.tif 000008
ここで、
【数７】
2004318365.tif 000009
（ｘ’＝１，…，Ｎ；ｙ’＝１，…，Ｎ）であり、
【数８】
2004318365.tif 000010
ここで、θｓ，ｔ（∈｛０，π／２，π，３π／２［ｒａｄ］｝）は回転角、λｓ，ｔ∈｛１，−１｝、ｅおよびｆはその他のパラメータによって自動的に設定される座標オフセット、θｓ，ｔおよびｏｓ，ｔはアフィン変換のパラメータである。θｓ，ｔ、λｓ，ｔ、θｓ，ｔおよびｏｓ，ｔを２−ＤファンクショナルＡＲパラメータと称する。
【００２５】
式（４）および式（５）で定義される関数Ｆｓ，ｔは、画像符号化（「Ｆｒａｃｔａｌ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ」Ｍｉｃｈａｅｌ  Ｂａｒｎｓｌｅｙ，  ａｎｄ  Ｌｙｍａｎ  Ｈｕｒｄ  ＡＫ  Ｐｅｔｅｒｓ，  １９９３）のためのグローバルＩＦＳ技法（Ａ．  Ｅ．  Ｊａｃｑｕｉｎ，  Ｉｍａｇｅ  ｃｏｄｉｎｇ  ｂａｓｅｄ  ｏｎ  ａ  ｆｒａｃｔａｌ  ｔｈｅｏｒｙ  ｏｆ  ｉｔｅｒａｔｅｄ  ｃｏｎｔｒａｃｔｉｖｅ  ｉｍａｇｅ  ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，  １  （１）  （Ｊａｎｕａｒｙ  １９９２）  １８−３０））に似ている。この提案したモデルにはいかなる関数も選び得るが、その１つとしてグローバルＩＦＳの定式化を用いることが考えられる。その理由は、グローバルＩＦＳ法に基づくＦｓ，ｔの採用は、画像に対する自己相似性を非常に良く表し得るからであり、この自己相似性の表現（即ち、繰り返し写像による表現）が、このモデルにおける自己回帰スキームに適応するからである。
【００２６】
２−ＤファンクショナルＡＲモデルのパラメータの計算
与えられた画像がｘである場合、このモデルのパラメータは下式を最小化することによって計算される。
【数９】
2004318365.tif 000011
（ｉ＝０，Ｎ，２Ｎ，…，Ｎ［Ｌ／Ｎ］，ｊ＝０，Ｎ，２Ｎ，…，Ｎ［Ｍ／Ｎ］）である。
【００２７】
【数１０】
2004318365.tif 000012
ここで、
【数１１】
2004318365.tif 000013
である。
【００２８】
上記の最小化によって最適な２−ＤファンクショナルＡＲパラメータを得ることができる。しかしながら上述した諸式ではまだ計算量も多く、特に最適なθやλを決定するためにはサーチアルゴリズムを必要とする。そこで計算負荷を軽減するために、式（１）のモデル定義を以下のように簡単化する。
【数１２】
2004318365.tif 000014
は下式を満足させる。
【数１３】
2004318365.tif 000015
ここでｓ＝１，…，ＬＭ、ｔ＝１，…，ＬＭである。
図４は、この簡単化した２−ＤファンクショナルＡＲ（自己回帰）モデルを表すブロック線図である。この簡単化は画像識別の性能を低下させることなく、計算コストの低減を実現することが可能である。図において、ｚ−ｓｘ、ｚ−ｔｙはｘ、ｙ軸のシフトオペレータであり、これらはｚ−ｓｘｚ−ｔｙＤｉ，ｊ＝Ｄｉ−ｓ，ｊ−ｔで機能する。なお、図に示すように、クリッピングに関しては左上のブロックと記載したが、これは一例であり他のブロックであっても良い。
【００２９】
２−ＤファンクショナルＡＲモデルに基づく画像識別
検索対象の画像として質問画像ｘ（ｉ，ｊ）が与えられた場合、これの２−ＤファンクショナルＡＲパラメータは、前述の諸式で計算され得る。本発明は、この２−ＤファンクショナルＡＲモデルを利用して、類似度を算出することによって、画像データベース内に格納されている画像が質問画像ｘと同一或いは類似であるのか否かを識別することを可能にする。
【００３０】
（ｉ）画像識別評価値（類似度）Ｅ１
画像データベースに格納されている被検索画像をｇとすると、その輝度値は、ｇ（ｉ，ｊ）（ｉ＝１，…，Ｌ；ｊ＝１，…，Ｍ）である。ここで、
【数１４】
2004318365.tif 000016
は、下記のように、質問画像ｘの２−ＤファンクショナルＡＲパラメータを適用することによって計算される。
【数１５】
2004318365.tif 000017
（ｉ＝０，Ｎ，２Ｎ，…，Ｎ［Ｌ／Ｎ］，ｊ＝０，Ｎ，２Ｎ，…，Ｎ［Ｍ／Ｎ］）である。
【数１６】
2004318365.tif 000018
【００３１】
【数１７】
2004318365.tif 000019
は質問画像ｘから計算される２−ＤファンクショナルＡＲモデルによって決定さる。この識別評価値（類似度）は、下式のように定義され得る。
【数１８】
2004318365.tif 000020
この評価値において、Ｅ１＝０の場合（即ち、各成分同士の誤差が無い場合）は、ｇは質問画像ｘと同一であると評価される。Ｅ１＜ＣＴＨ（例えばこの閾値ＣＴＨ＝０．２と設定する。）である場合は、ｇは質問画像ｘと類似であると評価される。ここでＣＴＨは予め定義された閾値である。
【００３２】
画像検索の用途ではＥ１のために
【数１９】
2004318365.tif 000021
を計算しなければならないが、画像データベースが巨大であれば計算量が問題と成るケースも考えられるが、その場合は、後述するＥ２を用いることが好適である。
【００３３】
（ｉｉ）画像識別評価値（類似度）Ｅ２
画像データベースに格納されている各画像を２−ＤファンクショナルＡＲモデルパラメータを事前に計算する場合を考える。画像識別のための計算コストは、下式を用いることによって低減され得る。
【数２０】
2004318365.tif 000022
ここで
【数２１】
2004318365.tif 000023
は検索対象の質問画像ｘから計算されるパラメータ（即ち第１のパラメータ群）であり、
【数２２】
2004318365.tif 000024
は画像データべース内の画像ｇ（被検索画像）から計算されるパラメータ（即ち第２のパラメータ群）であり、関数Ｉ（ｘ）は下式のように２進符号化の形式で定義される。
【数２３】
2004318365.tif 000025
【００３４】
このような画像識別においては、Ｅ２＝（Ｌ−Ｎ）×（Ｍ−Ｎ）である場合に被検索画像ｇは質問画像ｘと同一であると評価即ち判定される。また、Ｅ２＞ＣＴＨである場合は、被検索画像ｇは質問画像ｘと類似であると評価される。この評価値（類似度）の計算式には何ら乗算を含まないため、計算コストを顕著に低減することが可能である。
【００３５】
本発明による画像検索システム、方法、プログラムの効果を確認するために以下の評価実験を行った。
まず、２４個のオリジナル画像（２５６×２５６画素、２５５階調、人物、動物、植物、地形、風景、景色、船、橋、月面、円や三角などのパターン図形、グラフィック図形、ＤＴＰ印刷物、ＣＧ図形など）を用意し、個々の各画像に対して、メディアンフィルタやスムージングフィルタによるスムージング処理、ＪＰＥＧ圧縮、シャープニングフィルタによるシャープニング処理、或いは、ランダムな幾何学的歪みを施す処理をかけ、１オリジナル画像あたり１８個の処理済み画像を得た。従って、２４×１８＝４３２個の非検索画像を画像データベースに格納した。質問画像にはそれぞれのオリジナル画像を用いた。また、オリジナル画像は元々は画素がより大きなものであり、データ量を軽減化するためにそれらをサムネイル化したものである。
【００３６】
また、類似度の計算式を下式のように修正した。
【数２４】
2004318365.tif 000026
ここでＲは質問画像を分割した全ての参照ブロックのうち、１番〜１０番目に輝度値の分散が高いブロックを含むものである。なお、ここでは１０個のブロックに限定したが、この数を増加すればより高精度な類似度判定が可能になるがデータを増加させた分だけ計算コストがかかる。従って、この数は十分な精度が得られ、かつ、精度を損なわない数に、実験結果などを勘案して設定することが望ましい。
【数２５】
2004318365.tif 000027
は式（１１）の（ｓｉ，ｊ，ｔｉ，ｊ）に対応する。
【数２６】
2004318365.tif 000028
はｋ番目に最も小さい
【数２７】
2004318365.tif 000029
から成る。また、２−ＤファンクショナルＡＲモデルは、Ｎ＝１６、α＝２を用いて実現する。各ドメインブロックは１６画素未満で重ね合わせた状態で切り出す。計算量を低減するためにλおよびθは０および１に固定する。
【００３７】
実験に用いた演算手段ＣＰＵは、一般的なＰＣに搭載されているインテル社のペンティアム（登録商標）ＩＩの４５０ＭＨｚであるが、１つの質問画像を用いて４３２個の被検索画像に対して検索処理（類似度の計算処理）をするときに約２０ｍｓを要した。実験結果は、非常に良好であり、ほとんど場合、質問画像に由来する被検索画像の類似度（評価値Ｅ’２）は１００％近くあり、それ以外の画像に対しては２０％未満の類似度であった。
【００３８】
図５は、本実験で得られた類似度（評価値）の計算結果の一例を示すグラフである。図に示すように、質問画像（この場合は航空機から移した地形写真）に由来する被検索画像（この場合は画像番号１〜１８）の類似度（評価値Ｅ’２）は１００％であり、それ以外の画像に対してはほとんどが２０％未満の類似度であった。
従って、本発明によるシステムは非常に高精度かつ高速に所望の画像を検索して、大量の画像データベースから類似或いは一致する画像を取り出すことが可能である。
【００３９】
本明細書では、様々な実施態様で本発明の原理を説明してきたが、本発明は上述した実施例に限定されず幾多の変形および修正を施すことが可能であり、これら変形および修正されたものも本発明に含まれることを理解されたい。
例えば、実施例では、ＰＣというプラットホーム上で本発明を実現させたが、本発明は、ワークステーション、メーンフレームなどでも実現可能である。また、本実施例では、輝度値の分散の高いブロックの位置パラメータに基づき画像の局所的特徴を特徴付けたが、その他に高周波成分の多いブロックなどを用いることも可能であり、さらには位置パラメータ以外のアフィンパラメータをも利用し得ることに留意されたい。
さらに、本発明の様々な構成を組み合わせて検索を段階的に実施することも可能である。例えば、最初に、計算負荷が軽い位置パラメータのみを含む特徴パラメータ群を用いて類似度を算出して、類似候補の画像を絞り込み、その後、この類似候補の画像のみに対して、計算負荷が大きな全てのアフィンパラメータを用いて類似度を算出してより厳密・高精度な検索を行うことも可能である。このような構成を取れば、最初の絞り込みで候補画像を少数に限定できるため、高精度を保持しつつ、高速な検索サービスを提供することが可能である。
【図面の簡単な説明】
【図１】本発明による画像検索システムの一例を示すブロック図である。
【図２】本発明による画像検索方法の一例を示すフローチャートである。
【図３】第１の特徴パラメータ群を算出する手順を詳細に説明するフローチャートである。
【図４】この簡単化した２−ＤファンクショナルＡＲ（自己回帰）モデルを表すブロック線図である。
【図５】本実験で得られた類似度（評価値）の計算結果の一例を示すグラフである。
【符号の説明】
１００  画像検索システム
１０５  入力要求手段
１１０  受信手段
１１５  パラメータ算出手段
１２０  類似度算出手段
１２５  判定手段
１３０  画像データベース
１３５  送信手段
１４０  表示手段
【図１】
2004318365.tif 000030
【図２】
2004318365.tif 000031
【図３】
2004318365.tif 000032
【図４】
2004318365.tif 000033
【図５】
2004318365.tif 000034