(57)【特許請求の範囲】
【請求項１】
画像中の個々の領域に対する情報を記述した画像記述情報を参照情報として、検索指定された画像と類似する画像を含む画像データを検索する画像検索装置であって、
前記画像中の個々の領域のそれぞれと、検索が指定された検索画像とに応じて前記個々の領域より前記検索画像に含まれる単一領域を検出する単一領域処理手段と、
前記単一領域のそれぞれとの組み合わせと前記検索画像とに応じて前記検索画像に含まれる前記単一領域を複合した複合領域を求める複合領域処理手段と、
前記複合領域と前記検索画像との類似度を求める類似度検出手段と、
前記類似度検出手段により求められた類似度に応じて画像データを検索する検索手段と、
を有することを特徴とする画像検索装置。
【請求項２】
前記単一領域処理手段は、前記個々の領域のそれぞれと、前記検索画像との色情報の差と、前記検索画像の形状情報に応じて対応する前記単一領域を判定することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記単一領域処理手段は、前記個々の領域のそれぞれと、前記検索画像が所定の位置関係にあるか否かにより前記単一領域を判定することを特徴とする請求項１に記載の画像検索装置。
【請求項４】
前記複合領域処理手段は、前記個々の領域のそれぞれと、前記検索画像とが所定の位置関係にある範囲を示す幾何パラメータ領域の交差領域に基づいて複合領域を判定することを特徴とする請求項１に記載の画像検索装置。
【請求項５】
検索指定された検索画像と類似する画像を含む画像データを画像ファイルから検索する画像検索装置における画像検索方法であって、
検索が指示された検索画像を検索画像メモリに記憶する工程と、
前記画像ファイルに記憶された画像中の個々の領域の位置、形状及び色情報に関する情報を記述した記述ファイルを参照して、前記画像中の個々の領域が前記検索画像メモリに記憶された前記検索画像に含まれるか否かを判定する判定工程と、
前記判定工程で検索画像に含まれると判定された領域の記述情報と、前記画像に対する前記検索画像の移動可能領域を単一領域メモリに記憶する工程と、
前記記述情報と前記移動可能領域とに基づいて、前記単一領域メモリに記憶された各領域が同時に前記検索画像に内包される条件を満たすと判定された場合に前記領域を複合した複合領域を求めて複合領域メモリに記憶する工程と、
前記複合領域メモリに記憶された前記複合領域と前記検索画像との類似度を計算する計算工程と、
前記計算工程で計算された前記類似度に応じて前記検索画像を含む画像データを検索する工程と、
を有することを特徴とする画像検索方法。
【請求項６】
前記判定工程で検索画像に含まれると判定された領域は、前記領域の色情報と前記検索画像の色情報との差が所定値よりも小さく、かつ前記個々の領域のそれぞれの形状が前記検索画像の形状よりも小さい領域であることを特徴とする請求項５に記載の画像検索方法。
【請求項７】
前記判定工程で検索画像に含まれると判定された領域は、更に前記領域と前記検索画像が所定の位置関係にあると判定された領域であることを特徴とする請求項６に記載の画像検索方法。
【請求項８】
前記複合領域は、前記領域のそれぞれと前記複合領域の平行移動量を軸とする幾何パラメータ空間での移動可能領域の交差領域を計算し、当該交差領域が前記検索画像内に存在する場合に複合領域であると判定されることを特徴とする請求項５に記載の画像検索方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、例えば画像データベース或は画像ファイルシステム等において、画像もしくは図形を指定して、それに類似する画像データを検索する画像検索方法及びその装置に関するものである。
【０００２】
【従来の技術】
従来より、画像ファイル形式で記憶された複数の画像の中から所望の画像を検索する画像検索方法として、以下に示すような手法が用いられてきた。
（１）検索対象となる画像が入力されると、その画像と、画像ファイルに記憶されている画像データと順次重ね合わせていき、検索画像と画像ファイルの各画像との間の画素の差の総和を求め、その最小値を検索画像と画像ファイルの画像データとの差とする、いわゆるテンプレートマッチング法を用い、この差が所定以下の画像データを類似画像として選び出す方法（テンプレートマッチング方の詳細は、画像処理の教科書、例えば、コンピュータ画像処理入門、総研出版，５．６  マッチング，ｐｐ．１４８−１５２）がある。
（２）画像ファイルに記憶されている画像データを、予め幾つかの性質の一様な領域に区分けし、それぞれの画像領域を記述したデータと、検索画像もしくは検索図形との対応を面積・２次モーメントなどの類似度を用いて計算し、この類似度が大きいものを類似画像として選択する方法（例えば、概略画像を用いた画像検索：平田恭二，原良憲，情報処理学会研究会資料，ＤＥ９２−２）等があった。
【０００３】
【発明が解決しようとする課題】
しかしながら上記従来例（１）では、検索対象の画像データに対して指定された画像を移動させ、その移動毎に対応する画素数の差を計算しなければならないため検索処理に多くの時間を要していた。また、検索に際して指示された画像を画像データの２次元の領域内で十分に微小な距離毎に移動させて比較しないと正確な検索結果が得られないことから、非常に多量の計算時間を要するという問題があった。
【０００４】
また、上記従来例（２）では、検索される画像ファイルの画像データの一領域が、検索対象として指示された画像にそのまま１対１に対応していないと、正しく検索できないという問題があった。
【０００５】
ここで、自動的に画像データを複数の領域に分割する、いわゆる領域分割手法においては、しばしば人間が一つの領域と認識している対象エリアが複数の部分に分けて抽出されるため、このような制限は実用上の大きな問題となっていた。
【０００６】
本発明は上記従来例に鑑みてなされたもので、画像データ中の検索領域が複数の領域に分割されて抽出された場合にも効率的に画像データを検索できる画像検索方法及びその装置を提供することを目的とする。
【０００７】
また本発明の目的は、一つの領域として認識される画像データの領域に即して分割した画像データに基づいて画像を検索できる画像検索方法及びその装置を提供することにある。
【０００８】
また本発明の他の目的は、画像の類似度の計算に要する時間を短縮して、効率良く画像を検索できる画像検索方法及びその装置を提供することにある。
【０００９】
【課題を解決するための手段】
上記目的を達成するために本発明の画像検索装置は以下のような構成を備える。即ち、
画像中の個々の領域に対する情報を記述した画像記述情報を参照情報として、検索指定された画像と類似する画像を含む画像データを検索する画像検索装置であって、前記画像中の個々の領域のそれぞれと、検索が指定された検索画像とに応じて前記個々の領域より前記検索画像に含まれる単一領域を検出する単一領域処理手段と、前記単一領域のそれぞれとの組み合わせと前記検索画像とに応じて前記検索画像に含まれる前記単一領域を複合した複合領域を求める複合領域処理手段と、前記複合領域と前記検索画像との類似度を求める類似度検出手段と、前記類似度検出手段により求められた類似度に応じて画像データを検索する検索手段とを有する。
【００１０】
上記目的を達成するために本発明の画像検索方法は以下のような工程を備える。即ち、  検索指定された検索画像と類似する画像を含む画像データを画像ファイルから検索する画像検索装置における画像検索方法であって、
検索が指示された検索画像を検索画像メモリに記憶する工程と、
前記画像ファイルに記憶された画像中の個々の領域の位置、形状及び色情報に関する情報を記述した記述ファイルを参照して、前記画像中の個々の領域が前記検索画像メモリに記憶された前記検索画像に含まれるか否かを判定する判定工程と、
前記判定工程で検索画像に含まれると判定された領域の記述情報と、前記画像に対する前記検索画像の移動可能領域を単一領域メモリに記憶する工程と、
前記記述情報と前記移動可能領域とに基づいて、前記単一領域メモリに記憶された各領域が同時に前記検索画像に内包される条件を満たすと判定された場合に前記領域を複合した複合領域を求めて複合領域メモリに記憶する工程と、
前記複合領域メモリに記憶された前記複合領域と前記検索画像との類似度を計算する計算工程と、
前記計算工程で計算された前記類似度に応じて前記検索画像を含む画像データを検索する工程とを有することを特徴とする。
【００１１】
【作用】
以上の構成において、画像中の個々の領域のそれぞれと、検索が指定された検索画像とに応じて前記個々の領域より検索画像に含まれる単一領域を検出し、その単一領域のそれぞれとの組み合わせと検索画像とに応じて、その検索画像に含まれる単一領域を複合した複合領域を求める。そして、この複合領域とその検索画像との類似度を求め、求められた類似度に応じて画像データを検索するように動作する。
【００１２】
【実施例】
以下、添付図面を参照して本発明の好適な実施例を詳細に説明する。
【００１３】
図１は本発明の一実施例の画像検索装置における処理の流れを機能的に示すブロック図である。
【００１４】
図１において、１００は検索したい画像（以下、検索画像）を示し、この検索が指示された検索画像１００は、検索画像メモリ１０１に記憶される。１０２は単一領域処理部で、各画像データの内容を、その画像データの特徴を用いて記述した記述ファイル１１０を参照し、各画像データに含まれる個々の領域が、検索画像に含まれるかどうかを判定し、含まれる場合には、その画像データのその領域の記述情報と、検索画像の移動可能領域の情報とを、単一領域メモリ１０３に追加する。１０４は複合領域処理部で、複合領域に対して、それを構成する全ての領域が同時に検索画像に内包されるといった条件を満たすかどうかを判定し、内包される場合に、その領域の記述情報と、検索画像の移動可能領域の情報とを複合領域メモリ１０５に追加する。
【００１５】
１０６は最大値選択部で、複合領域処理部１０４により複合領域メモリ１０５に格納された複合領域と検索画像との類似度を計算し、この類似度の値の最大値を、それぞれの画像領域に対する類似度として選択する。１０７は順序化部で、それぞれの画像領域に対する検索画像の類似度を入力し、その類似度の大きい方からＫ個分の画像データを選択する。１０９は画像データアクセス部で、順序化部１０７で選択された画像データを、画像ファイル１０９にアクセスして読み出す。１１１は、こうして検索された画像を表示する表示部である。
【００１６】
単一領域処理部１０２は、ユーザである検索者から与えられた検索画像（図形も含む）が格納された検索画像メモリ１０１と、画像ファイル１０９に記憶された画像データ中の個々の領域の面積や境界点座標列などが記述された画像記述ファイル１１０を参照し、画像記述ファイル１１０の個々の領域に対して、その領域が検索画像に含まれるという条件の下に移動可能な領域である移動可能領域を計算し、その領域が検索画像に含まれるという条件を満たすか否かを判定すると共に、含まれる場合には、その領域の記述情報と、検索画像の移動可能領域の情報とを単一領域メモリ１０３に追加する。
【００１７】
複合領域処理部１０４は、検索画像メモリ１０１の内容（検索画像）と、単一領域メモリ１０３内の領域情報と、複合領域メモリ１０５内の複合領域情報とを入力とし、単一領域を組み合わせた複合領域及び複合領域と単一領域を組み合わせた複合領域を生成し、それらの複合領域が検索画像に含まれるという条件を満たすか否かを判定すると共に、その領域が検索画像に含まれる場合に、複合領域の記述情報と検索画像の移動可能領域の情報とを複合領域メモリ１０５に追加する。
【００１８】
最大値選択部１０６は、複合領域処理部１０４により選択された、複合領域が検索画像に含まれるという条件を満足する複合領域メモリ１０５内の複合領域に対して、その複合領域と検索画像との類似度を計算し、一枚分の画像データに含まれる全ての領域に対する類似度の最大値を選択し、これをその画像データに対する類似度として出力する。
【００１９】
順序化部１０７は、最大値選択部１０６より得られる各々の画像データに対する類似度を入力し、類似度の大きい順よりｋ個分の画像データをソーティングしつつ選択する。データアクセス部１０８は、順序化部１０７の内部メモリに格納されているソーティングされた各画像データの類似度情報を用い、類似度の大きい方から、対応する画像データを画像ファイル１０９より複数枚分読み出して表示部（ディスプレイ）１１１に表示する。
【００２０】
図２は、本実施例の画像検索装置における画面の表示例を示す図である。
【００２１】
図２において、２０１はユーザが検索したい画像（検索画像）を書き込む図形入力ウィンドウである。２０２は、ユーザが検索画像の種類などを指定する条件入力ウィンドウである。２０３は、検索した結果の画像を、例えば類似度の順に表示する検索結果表示ウィンドウである。２０４はカラーパレットで、ユーザが検索画像に与える色情報を選択するのに使用される。２０５は付属情報表示ウィンドウで、検索結果である画像に付属する付属情報を表示する。
【００２２】
以上の構成において、ユーザは条件入力ウィンドウ２０２に検索したい画像データ（検索画像）の種類などを指定して入力すると共に、その検索したい画像データ中にある部分画像を模した図形を図形入力ウィンドウ２０１に入力し、その図形の色をカラーパレット２０４を用いて指定する。
【００２３】
こうして指定された画像検索条件に基づいて画像データの検索を行った結果、検索された結果を示す画像データが検索結果表示ウィンドウ２０３に表示されると共に、その検索結果の画像に付随する情報が付属情報表示ウィンドウ２０５に表示される。
【００２４】
図３は、本発明の第１実施例の画像検索処理を説明する図であり、図１に示す単一領域処理部１０２を実現する処理を示す機能構成図である。
【００２５】
図４は、検索画像の一例を表した図である。ここでは検索画像は、多角形の図形であり、検索画像情報は、例えば指定された図形の頂点列、図形の縦横幅、図形の面積、色情報などで構成されている。また、領域記述情報の単位となる領域は、画像ファイル１０９に記憶されている検索対象の画像データに対して当該分野の技術者に知られている領域分割処理を適用することにより得られる。このような領域分割処理は、例えば、富永昌冶：「カラー画像の色分類と分割」、情報処理学会論文誌，Ｖｏｌ．３１，Ｎｏ．１１，ｐｐ．１５８９−１５９８，１９９０，Ｎｏｖ．に示されている。
【００２６】
図５は、検索対象である画像データの領域分割結果の一例を模式的に表した図である。ここで領域記述情報は、各領域に対して（領域の輪郭点列、領域の起点、領域の縦横幅、領域の面積、領域の平均色情報など）を含んでいる。
【００２７】
図３の３０１は色情報判定部、３０２はサイズ情報判定部、３０３は移動可能領域計算部、３０４は領域情報判定部である。
【００２８】
入力された検索画像と、検索対象となる画像データの領域記述情報とに基づいて色情報判定部３０１が両者の色情報の差を計算し、その差が前もって決められた閾値よりも大きければ不一致（検索画像の一部にならない）と判断して検索対象画像より除外する。この色情報の差は、検索画像の色を（Ｒ，Ｇ，Ｂ）、画像データの領域の色を（ｒ，ｇ，ｂ）とした時、以下のように計算できる。
【００２９】
Ｄ＝｜Ｒ−ｒ｜＋｜Ｇ−ｇ｜＋｜Ｂ−ｂ｜
次に、サイズ情報判定部３０２が両者の縦幅・横幅を比較し、例えば図５に示す分割された各領域の縦もしくは横幅が検索画像の縦・横幅よりも大きければ不一致（検索画像の一部にならない）と判断して検索対象より除外する。
【００３０】
色情報判定部３０１及びサイズ情報判定部３０２で不一致と判定されなかった場合には、移動可能領域計算部３０３が、検索対象画像の領域記述情報の個々の領域に対して、検索画像に、その領域が含まれる平行移動範囲を示す移動可能領域を計算する。そして領域情報判定部３０４が、この計算された移動可能領域が空領域か否かを判定し、移動可能領域が空である場合には不一致と判断して、その画像データを検索対象より除外する。このようにして、検索画像の内部に含まれ得る領域のみが検索対象画像として選択される。
【００３１】
図６は、図３の移動可能領域計算部３０３における、移動可能領域の境界となる境界線の検出処理を示した流れ図である。
【００３２】
まずステップＳ１で、最大値を“−９９９９９９９”に設定し、線分Ｆの式をＦ＝ａj×ｘ＋ｂj×ｙに設定する。次にステップＳ２に進み、検索画像の頂点列Ｑj（ｊは各頂点に対応するインデックス）より、隣り合う頂点座標ＱjとＱj+1とを結ぶ稜線Ｅjの方程式
ａj×ｘ＋ｂj×ｙ＋ｃj＝０
を求め、各領域の境界点列Ｐi（ｉは各点に対応するインデックス）に対して、稜線Ｅjの方程式の係数（ａj，ｂj）と境界点Ｐiの座標（Ｘi，Ｙi）から
Ｆ＝ａj×Ｘi＋ｂj×Ｙi
を計算する（ステップＳ３）。次にステップＳ４に進み、一つの領域の境界点列に対するＦの最大値ＦMAX(j)を計算する（尚、検索画像の頂点列の順序は、時計回り方向に並ぶ必要があるため、頂点列が反時計回り方向の場合には、前もって逆順に並べ直す）。この最大値がそれまでに求めた値よりも大きい時はステップＳ５で最大値を更新する。ステップＳ６では、全ての境界点Ｐに対する処理が終了したかを調べ、終了していない時はステップＳ７に進み、インデックスｉを＋１してステップＳ２に戻る。
【００３３】
このようにして、領域境界点列Ｐiの全ての点を含む境界線ａj×ｘ＋ｂj×ｙ−ＦMAX(j)＝０を規定するＦMAX(j)が求められるとステップＳ８で、そのＦMAXを登録し、ステップＳ９で、検索画像の頂点列から構成される全ての稜線Ｅjに対してこの処理が実施されたかを調べ、そうでない時はステップＳ１０でインデックスｊを＋１してステップＳ１に戻ることにより、全ての境界線を求める。
【００３４】
図７は、図６のフローチャートで示された処理結果を説明するための模式図である。ここでは、検索画像（図４）を平行移動した際に、図の中央にある領域７００が、その検索画像内に含まれる限界が矢印で示されている。これら矢印の先が指示している直線を方程式で表したのが
ａj×ｘ＋ｂj×ｙ−ＦMAX(j)＝０
である。
【００３５】
そして、図７における画像中の領域７００に対して、領域７００の境界点列Ｐi＝（Ｘi，Ｙi）は
ａj×Ｘi＋ｂj×Ｙi＜＝ＦMAX(j)
を満足し、Ｘ及びＹ方向の平行移動量（ｄｘ，ｄｙ）を軸とする幾何パラメータ空間を考えた時、各稜線に対応する方程式は、
ａj×（ｘ−ｄｘ）＋ｂj×（ｙ−ｄｙ）＋ｃj＝０より
ａj×Ｘi＋ｂj×Ｙi−ＦMAX(j)＜＝ａj×（Ｘi−ｄｘ）＋ｂj×（Ｙi−ｄｙ）＋ｃjとなり、（ｄｘ，ｄｙ）は以下の条件を満足することが必要となる。
【００３６】
ａj×ｄｘ＋ｂj×ｄｙ−（ｃj＋ＦMAX(j)）＜＝０
これから、（ｄｘ，ｄｙ）空間における境界線
ａj×ｄｘ＋ｂj×ｄｙ−（ｃj＋ＦMAX(j)）＝０
を描くことで、検索画像の全ての稜線に対する条件を満足する（ｄｘ，ｄｙ）の存在範囲は、例えば、図８のように得られる。また検索画像の全ての稜線に対する条件を満足する点（ｄｘ，ｄｙ）の存在範囲が空である場合には、検索対象の画像データのその領域は検索画像内に入りきらないと判断される。
【００３７】
図９は、図３の領域情報判定部３０４における、移動可能領域が空領域か否かの判定処理を示すフローチャートである。
【００３８】
ステップＳ２１では、（ｄｘ，ｄｙ）空間における境界線間の交差点の位置を計算し、ステップＳ２２では、それらの交差点の中に、検索画像の全ての稜線に対する条件を満足する内部交差点があるか否かを判定する。そして、境界線間の交差点の何れかが、検索画像の全ての稜線に対する条件を満足すれば、移動可能領域は空でないと判定する。尚ここで、境界線間の交差点の位置は、２つの境界線の方程式に対して、連立方程式の解法を用いて計算する。
【００３９】
図１０は、図９のステップＳ２２における、内部交差点の有無を判定する処理の流れを示すフローチャートである。
【００４０】
ステップＳ３１で、境界線間の交差点Ｐi＝（Ｘi，Ｙi）をセットし、その設定された交差点Ｐiに対して、境界線Ｂj：ａj×ｄｘ＋ｂj×ｄｙ−（ｃj×ＦMAX(j)）＝０に対する条件
ａj×Ｘi＋ｂj×Ｙi＜＝ｃj＋ＦMAX(j)
が満足されるかを、順に全ての境界線に対して判定し（ステップＳ３３）、ステップＳ３４で全ての境界線に対する処理が終了したかを調べ、全ての境界線に対して満足した場合には、内部交差点有りと判定して処理を終了する。一方、満足しない条件がある場合には次の交差点を対象として、上記判定を繰り返す。
【００４１】
また、ステップＳ３６で全ての交差点に対する判定処理を終了したかを判断し、全ての交差点を判定しても内部交差点有りと判定されない場合は、内部交差点なしと判定して処理を終了する。
【００４２】
このような判定を行った結果、単一領域メモリ１０３の中には、例えば、図１１に模式的に示すようないくつかの領域が挿入されることになる。
【００４３】
図１２は、図１の複合領域処理部１０４における複合領域の生成と処理の流れを示すフローチャートである。この処理は、単一領域メモリ１０３の中の領域情報を組み合わせた複合領域を生成し、複合領域メモリ１０５に挿入するものである。
【００４４】
システムはまずステップＳ４１で、複合領域として、単一領域メモリ１０３内の全ての領域を複合領域メモリ１０５に設定する。次いでステップＳ４２に進み、単一領域メモリ１０３の単一領域ｉを順に選択する。続いてステップＳ４３で、選択した単一領域ｉと複合領域メモリ１０５の複合領域（複写された単一領域も含む）との組み合わせにより生成される複合領域を一時的に格納するテンポラリメモリをクリアする。
【００４５】
そしてステップＳ４４に進み、複合領域メモリ１０５の複合領域ｊ（複写された単一領域も含む）を順に選択する。ステップＳ４５では、その選択した複合領域ｊを構成する単一領域の中に選択した単一領域ｉがあるかどうかを調べ、無い場合はステップＳ４６に進み、これらの組み合わせによる複合領域ｋを生成する。そしてステップＳ４７に進み、この複合領域ｋが検索画像内に含まれるか否かを判定する。含まれるならばステップＳ４８に進み、その複合領域ｋをテンポラリメモリに追加する。これをステップＳ４９で、複合領域メモリ１０５の全ての複合領域に対して行うまで、インデックスｊをインクリメントしながら前述の処理を実行する。
【００４６】
こうしてステップＳ４９で、全ての複合領域に対する処理が終了したならばステップＳ５１に進み、テンポラリメモリ内の複合領域を複合領域メモリ１０５に追加し、ステップＳ５２で、単一領域内の全ての領域に対する処理が完了するまで、ステップＳ５３で、インデックスｉをインクリメントしながら以上の処理を繰り返す。
【００４７】
図１３は、個々の複合領域ｋが検索画像内に含まれるか否かの判定処理を行う複合領域処理部１０４の機能構成を示す機能ブロック図である。
【００４８】
まず、サイズ情報判定部１３０１が、複合領域のサイズ情報を判定する。複合領域ｋの面積は、それに含まれる単一領域ｉおよび複合領域ｊの面積の和であり、その複合領域ｋの起点およびその縦横幅は、それぞれの領域の起点、および起点と縦横幅から計算される終点の中での最小値を起点とし、最大値との差として縦横幅を計算する。
【００４９】
このように計算された複合領域ｋの面積が、検索画像の面積よりも大きいか、あるいは複合領域ｋの縦幅もしくは横幅が、検索画像の縦幅・横幅よりも大きいならば、これらは検索画像に含まれ得ないとして除外する。
【００５０】
次いで、複合領域ｋを構成する単一領域ｉと複合領域ｊが同時に、検索画像内に存在するか否かを判定するために、交差領域計算部１０３２が、単一領域ｉおよび複合領域ｊの平行移動量（ｄｘ，ｄｙ）を軸とする幾何パラメータ空間での移動可能領域の交差領域を計算し、領域情報判定部１３０３が、この交差領域が空であるか否かを判定する。
【００５１】
前述したように、（ｄｘ，ｄｙ）空間での移動可能領域は以下の条件から得られる。
【００５２】
ａj×ｄｘ＋ｂj×ｄｙ−（ｃj＋ＦMAX(j)）＜＝０
よって、同一の稜線に対応するそれぞれの領域の境界線に対するＦMAX(j)の値のうち、小さい方を選択することで交差領域が規定される。
【００５３】
領域が空であるか否かは、単一領域に対する移動可能領域の場合と同様であり、図９および図１０に示された移動可能領域の判定および内部交差点の有無判定の動作で判定される。
【００５４】
図１４は複合領域の一例を示した図であり、図１５は図７と対になる、もう一方の領域の境界線を示す図、図１６は図８と対になる（ｄｘ，ｄｙ）空間における移動可能領域を示している。
【００５５】
図１２および図１３に示した前述の複合領域の生成処理の流れにより、図１４に示す複合領域が同時に、図４に示す検索画像内に存在する領域として、図１７が得られる。このように複合領域の判定を進めることにより、図１８に示すような複合領域をも得る事ができる。
【００５６】
図１の最大値選択部１０６は、１枚の画像から上述の複合領域処理部１０４で検出された全ての複合領域に対して類似度を計算し、その最大値を求める。
【００５７】
ここで類似度は以下のように計算される。
【００５８】
類似度＝１−｜複合領域の面積−検索画像の面積｜／検索画像の面積
最大値選択部１０６は得られた最大値をその画像に対する類似度として順序化部１０７に送る。順序化部１０７は、最大値選択部１０６より得られる各々の画像に対する類似度を入力とし、類似度の大きい順にｋ個のデータをソーティングしつつ選択する。
【００５９】
データアクセス部１０８は、順序化部１０７の内部メモリに格納されているソーティングされた画像の類似度情報を用い、類似度の大きい方から画像ファイル１０９を複数枚読み出してディスプレイ１１１に表示する。
【００６０】
［第２実施例］
第２実施例は、検索画像の大きさが変動し得る場合に対応する。以下にまず、原理を説明する。
【００６１】
この第２実施例では、検索画像に対して、大きさの拡大率をｓｃａｌｅ（１未満の時縮小）とし、原点を中心に拡大した場合、全ての点Ｐ（ｘ，ｙ）は、点Ｑ（ｓｃａｌｅ×ｘ，ｓｃａｌｅ×ｙ）に移動する。点Ｐ0Ｐを通る直線の方程式が、
ａj×ｘ＋ｂj×ｙ＋ｃj＝０
ただし、ａj＝ｙ0−ｙ，
ｂj＝ｘ−ｘ0
ｃj＝ｘ0×ｙ−ｘ×ｙ0
とすると、これを拡大した点Ｑ0Ｑを通る直線の式は、
ａk×ｘ＋ｂk×ｙ＋ｃk＝０
ただし、ａk＝ｓｃａｌｅ×ａj
ｂk＝ｓｃａｌｅ×ｂj
ｃk＝ｓｃａｌｅ×ｓｃａｌｅ×ｃj
これは、直線の式としては、拡大前と平行になる。よって、同じ領域の境界列に対して最大値ＦMAXを与える点も同じである。即ち、
ＦMAX(k)＝ａk×Ｘ＋ｂk×Ｙ＝ｓｃａｌｅ×（ａj×Ｘ＋ｂj×Ｙ）
＝ｓｃａｌｅ×ＦMAX(j)
包合条件を与える式
ａk×ｄｘ＋ｂk×ｄｙ−（ｃk＋ＦMAX(k)）＜＝０
をｓｃａｌｅで割ると、
ａj×ｄｘ＋ｂj×ｄｙ−（ｓｃａｌｅ×ｃj＋ＦMAX）＜＝０
であり、これは（ｄｘ，ｄｙ，ｓｃａｌｅ）空間を考えた時の平面の片側を構成する。
【００６２】
同様に他の稜線も平行となり、存在可能なパラメータ領域は、これらの平面群に含まれる多面体（実際には片側が無限）となる。
【００６３】
従って、この多面体の交差領域を得ることにより、複数の領域が同一の拡大率で同時に、検索画像内に存在し得るか否かが判定できる。
【００６４】
図１９は、上記の原理を実現する複合領域処理部１０４の実施形態を示すフローチャートである。
【００６５】
ａj×ｄｘ＋ｂj×ｄｙ−（ｓｃａｌｅ×ｃj＋ＦMAX）＜＝０
検索画像の全ての稜線ｊに対してａj，ｂj，ｃjが前述のように計算され、図４の動作でＦMAXが得られる。
【００６６】
平行でない３つの境界面の交点として、全ての交差点Ｐ＝（ｄｘi，ｄｙi）を計算し、これが各条件式を満たすか否かを判定する。３つの境界面の交点は、（ｉ，ｊ，ｋ）を検索画像の稜線の数より小さい異なる３つの整数とした時、次の連立方程式を良く知られている連立方程式の解法により解くことで計算する。
【００６７】
ａi×ｄｘ＋ｂi×ｄｙ−（ｓｃａｌｅ×ｃi＋ＦMAX(i)）＝０
ａj×ｄｘ＋ｂj×ｄｙ−（ｓｃａｌｅ×ｃj＋ＦMAX(j)）＝０
ａk×ｄｘ＋ｂk×ｄｙ−（ｓｃａｌｅ×ｃk＋ＦMAX(k)）＝０
また、条件式の満足は、以下の式により判定できる。
【００６８】
（ａj×ｄｘj＋ｂj×ｄｙj−ＦMAX）／ｃj＜＝ｓｃａｌｅ  ｉｆ  ｃj＞０
（ａj×ｄｘj＋ｂj×ｄｙj−ＦMAX）／ｃj＜＝ｓｃａｌｅ  ｉｆ  ｃj＜０
ここでｓｃａｌｅを無限に大きくできるならば、任意の形状の領域を含めるようになるので、実用的には、変動可能なｓｃａｌｅの範囲を“１．２”以下といったように定め、この範囲内に内部交差点があるか否かの判定を行う。即ち、
（ａj×ｄｘ＋ｂj×ｄｙ−ＦMAX）／ｃj＜＝１．２  ｉｆ  ｃj＞０
（ａj×ｄｘ＋ｂj×ｄｙ−ＦMAX）／ｃj＜＝１．２  ｉｆ  ｃj＜０
これにより、大きさが変動する場合にも適切な対応を得ることができる。
【００６９】
［第３実施例］
本発明の第３の実施例は、検索画像が複数の色の異なる領域から構成される場合に対応する。
【００７０】
検索画像を構成するそれぞれのパターンは以下の情報を持つ（検索画像の頂点列、その画像の縦横幅、面積、色情報）。この場合には、図３に示した単一領域処理部１０２の動作を以下に説明するように変更する。
【００７１】
図２０は第３実施例での単一領域処理部１０２の処理部の構成を示した図である。
【００７２】
入力された検索画像内の個々のパターン情報と領域情報の組み合わせに対して、図３に相当する処理手順を適用し、条件を満足する全ての場合に、領域の記述情報と検索画像の移動可能領域の情報を単一領域メモリ１０３に追加する。この後、前述した複合領域の処理部およびそれ以降の各部を構成することで、複数のパターンを用いて検索画像による検索を行うことができる。
【００７３】
また、画像の一部が検索画像として与えられた場合、その検索画像を領域分割し、各々の境界線を多角形近似して複数の色の異なる領域を作成することで複数の画像パターン（図形パターン）を生成できる。この結果、上述の部分を用いて、画像の一部が検索画像として与えられた場合にも、その検画像パターンを含む画像データの検索が可能となる。
【００７４】
尚、本発明は、複数の機器から構成されるシステムに適用しても、１つの機器から成る装置に適用しても良い。また、本発明はシステム或は装置に本発明を実施するプログラムを供給することによって達成される場合にも適用できる。
【００７５】
以上説明したように本実施例によれば、単一の領域に対する処理と共に、複数の領域の複合した複合領域に対する処理を行うことにより、複数の領域に分かれて抽出された対象を正しく検索できる効果がある。
【００７６】
また、各領域と検索画像とが特定の位相関係にある移動可能領域を求め、この移動可能領域の交差領域の有無を判定することにより、効率的に判定が行なえるという効果がある。
【００７７】
【発明の効果】
以上説明したように本発明によれば、画像データを複数の領域に分割して抽出した対象画像に基づいて効率的に画像データを検索できる効果がある。
【００７８】
また本発明によれば、一つの領域として認識される画像データの領域に即して分割した画像データに基づいて画像を検索できる効果がある。
【００７９】
また本発明によれば、画像の類似度の計算に要する時間を短縮して、効率良く画像を検索できる効果がある。
【００８０】
【図面の簡単な説明】
【図１】本発明の一実施例の画像検索装置の機能構成を示す機能ブロック図である。
【図２】本実施例の画像検索装置の一例を示す図である。
【図３】本発明の第１実施例における単一領域処理部の構成を示す機能ブロック図である。
【図４】本実施例における検索画像の一例を模式的に表した図である。
【図５】検索対象となる画像データの領域分割の結果の一例を模式的に表した図である。
【図６】本実施例の移動可能領域計算部における境界線の検出処理を示したフローチャートである。
【図７】図６の境界線検出処理により検出された境界線を説明するための模式図である。
【図８】幾何パラメータ空間における単一領域の移動可能領域の一例を示した図である。
【図９】本実施例の領域情報判定部における移動可能領域の判定処理を示すフローチャートである。
【図１０】図９の移動可能領域の判定処理における内部交差点の有無の判定処理を示すフローチャートである。
【図１１】本実施例において、単一領域メモリの中に挿入された複合領域を模式的に示した図である。
【図１２】複合領域処理部における複合領域の生成と処理の流れを示すフローチャートである。
【図１３】第１実施例の複合領域処理部において個々の複合領域に対する領域情報判定部の構成を示す機能ブロック図である。
【図１４】本実施例における複合領域の一例を模式的に示した図である。
【図１５】境界線検出処理により検出された領域の境界線を示した図である。
【図１６】幾何パラメータ空間における単一領域の移動可能領域の一例を示した図である。
【図１７】幾何パラメータ空間における複合領域の移動可能領域の一例を示した図である。
【図１８】本実施例により得られた複合領域の一例を模式的に示す図である。
【図１９】第２実施例における内部交差点の有無判定処理を示すフローチャートである。
【図２０】第３実施例における単一領域処理部の機能構成を示ス機能ブロック図である。
【符号の説明】
１００  検索画像
１０１  検索画像メモリ
１０２  単一領域処理部
１０３  単一領域メモリ
１０４  複合領域処理部
１０５  複合領域メモリ
１０６  最大値選択部
１０７  順序化部
１０９  画像ファイル
１１０  記述ファイル
１１１  ディスプレイ
３０１  単一領域処理部の色情報判定部
３０２  単一領域処理部のサイズ情報判定部
３０３  単一領域処理部の移動可能領域計算部
３０４  単一領域処理部の領域情報判定部
１３０１  複合領域処理部のサイズ情報判定部
１３０２  複合領域処理部の交差領域計算部
１３０３  複合領域処理部の領域情報判定部
【図１】
0003647075.tif 000002
【図２】
0003647075.tif 000003
【図３】
0003647075.tif 000004
【図４】
0003647075.tif 000005
【図５】
0003647075.tif 000006
【図６】
0003647075.tif 000007
【図７】
0003647075.tif 000008
【図８】
0003647075.tif 000009
【図９】
0003647075.tif 000010
【図１０】
0003647075.tif 000011
【図１１】
0003647075.tif 000012
【図１２】
0003647075.tif 000013
【図１３】
0003647075.tif 000014
【図１４】
0003647075.tif 000015
【図１５】
0003647075.tif 000016
【図１６】
0003647075.tif 000017
【図１７】
0003647075.tif 000018
【図１８】
0003647075.tif 000019
【図１９】
0003647075.tif 000020
【図２０】
0003647075.tif 000021