(57)【特許請求の範囲】
【請求項１】
１つの画像を少なくとも２つ以上の異なる階層レベルを有する画像グリッド構造に分割する段階と、
前記各階層レベルの画像グリッドに対して、前記画像グリッドの高さ及び幅に比例する分解度を有するセルに階層的に細分化する段階と、
前記各セルに対して、そのセルを代表する領域代表カラー及びその領域代表カラーの類似度を表す信頼度情報を割り当てる段階と
を含むことを特徴とする多重レベル画像データ生成方法。
【請求項２】
１つの画像が少なくとも２つの異なる階層レベルを有する画像グリッドに表現される画像のデータ構造を利用した画像検索方法において、
それぞれが異なる複数の階層レベルに分割された参照画像と検索対象画像に含まれる各セルをマッチングさせて、空間的なカラーフィーチャーを有する２つのカラーポイント間の領域代表カラー値の類似度の差に従って参照画像と検索対象画像の２つの画像間のカラー類似度を決定し、決定したカラー類似度に基づき参照画像と検索対象画像に含まれる各セルの類似度を求め、このセル類似度に基づいて画像を検索することを特徴とする画像検索方法。
【請求項３】
前記２つの画像間のカラー類似度は、２つの画像グリッドをマッチングさせ、それら画像間の空間的カラーフィーチャーに従って交差させながら算出されることを特徴とする請求項２に記載の画像検索方法。
【請求項４】
前記２つの画像間のカラー類似度は、各セルの領域代表カラー値をマッチングして領域代表カラー値が同一のセルの領域を検索することで算出されることを特徴とする請求項２に記載の画像検索方法。
【請求項５】
前記２つの画像に含まれた各セルのセル類似度は、対象画像の２つのセル間の領域代表カラーの類似度を表すカラー類似度（Ｃｏｌｏｒ＿Ｓｉｍ）に第１加重値を乗じた後、その値に前記カラー類似度（Ｃｏｌｏｒ＿Ｓｉｍ）に前記２つのセル間の信頼度の類似の程度を表す類似度（Ｉ）と、第２加重値とを乗じた値を加算し、前記カラー類似度を正規化した値であることを特徴とする請求項２又は請求項３に記載の画像検索方法。
【請求項６】
前記２つの画像間のカラー類似度は、比較対象される２つの画像グリッドの同じ階層レベルをマッチングさせてその類似度を算出する場合、２つのセル間の相互対応する縦横比の差に当たる移動量で、横と縦に移動しながら算出された類似度を加算した全体値であることを特徴とする請求項２又は請求項３に記載の画像検索方法。
【請求項７】
前記２つの画像間のカラー類似度は、前記２つの画像の異なる各階層レベルをマッチングさせてその類似度を算出する場合、前記各階層レベルに含まれた２つのセル間の相互対応する縦横比の差に当たる移動量で、横と縦に移動しながら算出された類似度を加算した全体値であることを特徴とする請求項２又は請求項３に記載の画像検索方法。
【請求項８】
前記２つの画像間のカラー類似度は、カラー領域を比較して算出する場合、前記２つの画像の同じ階層レベルでの同様な位置と異なる位置とをそれぞれ比較して算出されることを特徴とする請求項２に記載の画像検索方法。
【請求項９】
前記２つの画像にそれぞれ含まれる２つの画像グリッド間のカラー類似度は、カラー領域を比較して算出する場合、前記２つの画像グリッドの異なる階層レベルでの同様な位置と異なる位置とをそれぞれ比較して算出されることを特徴とする請求項２に記載の画像検索方法。
【発明の詳細な説明】
【０００１】
技術分野
本発明は、画像グリッドデータ構造及びそれを利用した画像検索方法に係るもので、詳しくは、スチール画像の空間的なカラーフィーチャーを異なる階層的なグリッドとして表現する多重レベル画像グリッドデータ構造、及びその多重レベル画像グリッドデータ構造を利用して画像を検索する画像検索方法に関するものである。
【０００２】
背景技術
従来の画像検索方法においては、カラー、形状及びテクスチャなどのフィーチャーを一つのレベルの画像グリッドデータ構造に表現し、該一つのレベル画像グリッドデータ構造を利用して、同様な構造の他の画像データ間の類似度を検索して当該の画像を検索していた。
【０００３】
このとき、検索しようとする画像の特性に従って、各フィーチャーの重要度が異なり、一つのフィーチャーであっても、従来の画像グリッドデータ構造における各セルに対する重要度が異なる。例えば、カラーヒストグラムを利用して画像検索を行う場合、そのカラーヒストグラムがｎ次元として構成されていると、ｎ次元を構成する各個別要素毎にその加重値がそれぞれ異なることもある。
【０００４】
従って、一つのレベルの画像グリッドデータ構造を用いる従来の画像検索方法においては、フィーチャー間の重要度が前記グリッドによって表現されている。しかし、それぞれのフィーチャーの各要素毎の重要度はほとんど考慮されていない。これを補うための画像検索方法として、予め各個別的フィーチャーの各要素毎に平均的な重要度を計算する方法が利用されている。
【０００５】
然るに、このような従来の画像検索方法においては、参照画像や参照対象の画像の特性に従って、各個別的なフィーチャーの要素毎の平均的重要度が様々であるので、画像を正確に検索ことが難しいという不都合な点があった。
さらに、従来の画像グリッドデータ構造においては、何れも一つのレベルとして構成されているため、従来の画像検索方法により画像に含まれた対象を正確に検索し難いという不都合な点があった。
【０００６】
発明の開示
そこで、本発明は、このような従来の問題点に鑑みてなされたもので、その目的は、一つの画像に含まれたフィーチャーが多重レベル画像グリッドとして表され、それらの各レベルが異なるレベルの階層的構造のセルとして表され、それら各セルは、領域代表カラー及びその代表カラー値の類似度を示す信頼度で表されるデータ構造を提供することにある。
【０００７】
かつ、本発明の他の目的は、参照対象画像の異なる多重レベル画像グリッドに対して、二つの画像グリッドの同じレベルのセルの間のマッチングと異なるレベルのセル間のマッチングと、カラー類似度抽出を実行するカラー領域のマッチングとを行って、画像を検索する画像検索方法を提供することにある。
【０００８】
このような目的を達成するため、本発明に係る多重レベル画像データ構造においては、一つの画像の空間的カラーフィーチャーに対し、二つ以上の異なるレベルの階層的画像グリッド構造を生成する。
上述した目的を達成する本発明に係る多重レベル画像データ構造を利用した画像検索方法においては、異なる階層的画像グリッドレベルに分割された参照画像の空間的なカラーフィーチャーのカラー類似度と、参照対象画像のカラー類似度とをマッチングさせて、ユーザからの内容に基づく照会に合わせて所望の画像を検索する。
以下、本発明の実施の形状について図面を用いて説明する。
【０００９】
発明を遂行するベストモード
本発明は、多重レベル画像グリッドデータ構造とそれを利用して画像を検索する方法に関する。まず、多重レベル画像グリッドデータ構造を生成する方法について説明する。
【００１０】
一つの画像に対し、画像が正四角形画像である場合、縦横比を均等に分け、正四角形画像でない場合、当該の画像の高さと幅の縦横比に基づいてその一方の側辺を均等に分けた後、他方側辺を一方の側辺の均等単位に分ける。即ち、縦横比が均等な正四角形画像は、縦横比を均等単位で分け、かつ、縦横比の異なる直四角形画像は、一方側（例えば、長さの長い辺）を均等に分け、一方の側辺の均等な単位で他方側（例えば、長さの短い辺）を分ける。
【００１１】
従って、このように生成される一つの画像データ構造は、空間的カラーフィーチャーを異なるレベルの階層的グリッドにそれぞれ分割することで多重レベル画像グリッド（Ｍｕｌｔｉ−ｌｅｖｅｌ ｉｍａｇｅ ｇｒｉｄ）構造になる。
【００１２】
このとき、各画像グリッドは、異なるレベルの階層的な構造になっているため、各レベルの分解度を階層的に細分化し、各グリッドのセルは、その領域を代表するカラー（ＲＲＣ：Ｒｅｇｉｏｎａｌ  Ｒｅｐｒｅｓｅｎｔａｔｉｖｅ  Ｃｏｌｏｒ）及びその代表カラーの正確な精度を示す信頼度（Ｓ：Ｒｅｌｉａｂｉｌｉｔｙ  Ｓｃｏｒｅ）として表される。
【００１３】
図１は、本発明に係る多重レベル画像グリッドデータ構造の実施形態で、３−レベル画像グリッドデータ構造を示した図面である。図示されたように、一つの画像が、１次レベル、２次レベル及び３次レベルの画像グリッドレベルに分割されている。
【００１４】
ここで、前記３−レベル画像グリッドデータ構造の分解度は、各レベル毎にそれぞれ等分された程度に従って、１次レベルの画像が最も低く、２次レベルの画像が中間程度で、３次レベルの画像が前記１、２次画像グリッドより相対的に高い。
【００１５】
前記１次レベル画像グリッドは、縦（Ｍ）と横（Ｎ）とに比例するＭ１×Ｎ１個の地域セル（ｌｏｃａｌ ｃｅｌｌ）を含む画像領域に分割される。各セルは、それぞれの領域を代表する領域代表カラー（ＲＲＣ）と、その代表カラー値の精度を示す信頼度（Ｓ）として表される。
【００１６】
一方、２次レベル画像のグリッドや３次レベル画像のグリッドも各分割程度に従って、Ｍ２×Ｎ２とＭ３×Ｎ３個の地域セルを含む画像領域に分割され、かつ、それぞれのセルは、領域代表カラー（ＲＲＣ）と信頼度（Ｓ）を持っている。
【００１７】
例えば、１次レベル画像のグリッドの最大の縦長さ（Ｍ１）と横長さ（Ｎ１）がそれぞれ８（全てのグリッド数は、６４（＝８×８）になる）であるとすると、２次レベル画像のグリッドの最大の縦長さ（Ｍ２）と横長さ（Ｎ２）は、それぞれ１６（全てのグリッド数は１６×１６）の地域セルになり、３次レベル画像のグリッドの最大の横長さ（Ｍ３）と縦長さ（Ｎ３）は、それぞれ３２（全てのグリッド数は、３２×３２）の地域セルになる。
【００１８】
図示されたように、３次レベル画像グリッドの任意のセル（Ｃｅｌｌ（ｉ，ｊ））は、その領域代表カラーと信頼度（Ｃ３ｉｊ、Ｓ３ｉｊ）として表される。
【００１９】
このとき、各画像レベル（１次レベル、２次レベル及び３次レベル）の最小分割は、画像に含まれた所定のオブジェクトの位置をより一層正確に表すために、画像の縦横比に基づいて行われる。即ち、長い辺を基準としたとき、長い辺を均等分割した後、短い辺を前記長い辺の均等単位で分けて分割する。
【００２０】
画像グリッドを生成する他の方法として、処理速度の向上及び画像に含まれたオブジェクトの概略的な位置情報のみを考慮して、各グリッドの縦横の長さを同様にすることができる。
【００２１】
このような多重レベル画像グリッドデータ構造を利用して画像を検索する方法について以下説明する。
【００２２】
このとき、前記多重レベル画像グリッドに分割された異なる画像は、その領域を代表する領域代表カラー（ＲＲＣ）と、その代表カラーの精度を示す信頼度（Ｓ）ととして表されるため、それぞれの領域代表カラーと信頼度とをマッチングさせ、ユーザからの内容に基づいた照会に従ってセルの類似度を算出して画像検索を行う。
【００２３】
先ず、多重レベル画像グリッドデータ構造を利用して、二つの画像間のカラー類似度を、各レベルの画像グリッドに含まれたセルと各セルを代表する領域代表カラー（ＲＲＣ）とをお互いに比較して算出する。即ち、セル（Ｃ１）とセル（Ｃ２）間の領域代表カラー値の類似度を表すカラー類似度（Ｃｏｌｏｒ＿Ｓｉｍ（ＲＲＣ＿Ｃ１、ＲＲＣ＿Ｃ２））を利用して二つのセル間のカラー類似度を求める。
【００２４】
そして、カラー類似度（Ｃｏｌｏｒ＿Ｓｉｍ（ＲＲＣ＿Ｃ１、ＲＲＣ＿Ｃ２））に第１加重値（α）を乗じた後、カラー類似度（Ｃｏｌｏｒ＿Ｓｉｍ（ＲＲＣ＿Ｃ１、ＲＲＣ＿Ｃ２））に第２加重値（β）と二つのセル間の信頼度の類似度（Ｉ）とを掛けた乗算値を、カラー類似度（Ｃｏｌｏｒ＿Ｓｉｍ（ＲＲＣ＿Ｃ１、ＲＲＣ＿Ｃ２））と第１加重値（α）との乗算値に加算し、その結果値を第１加重値（α）と第２加重値（β）との和で除算じて正規化すると、二つのセル（Ｃ１，Ｃ２）間のセル類似度（Ｃｅｌｌ＿Ｓｉｍ（Ｃ１、Ｃ２）が求められる。これをまとめて表すと次式のようになる。
【００２５】
【数１】
0003541011.tif 000002
ここで、二つのセル間の信頼度（Ｓ１，Ｓ２）の類似の程度を表す類似度（Ｉ）は、Ｉ＝１−｜Ｓ１−Ｓ２｜により求められる。
【００２６】
従って、二つの異なる多重レベル画像グリッド間のセル類似度は、多重レベル画像のような各レベルと、異なる各レベルとを比較して算出し、これに基づいて前記画像間のフィーチャーを検索する。
【００２７】
図２は、本発明に係る多重レベル画像グリッドデータ構造を利用した画像検索の実施形態を示した図面で、３−レベル画像グリッドデータ構造を有する二つの画像（Ｉ１、Ｉ２）のグリッド間の類似度に基づいて画像の検索を実施する方法を示した。
【００２８】
図示されたように、二つの画像（Ｉ１、Ｉ２）は、それぞれ１次レベル画像のグリッド（Ｇ１＿１ｓｔ、Ｇ２＿１ｓｔ）、２次レベル画像のグリッド（Ｇ１＿２ｎｄ、Ｇ２＿２ｎｄ）及び３次レベル画像のグリッド（Ｇ１＿３ｎｄ、Ｇ２＿３ｎｄ）を有する。
【００２９】
そして、双方の画像（Ｉ１、Ｉ２）に含まれた各グリッドレベル間の類似度（Ｇｒｉｄ＿Ｓｉｍ  （Ｇ１、Ｇ２））は、各レベルをお互いに比較して計算するが、式にまとめて表すと次のようである。
【００３０】
【数２】
0003541011.tif 000003
【００３１】
ここで、ｗ１〜ｗ９は、代表的なカラー類似度に対する加重値を表し、Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｅｘａｃｔは、二つの画像（Ｉ１、Ｉ２）に対する同じ画像グリッドレベル間の類似度を表し、Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｉｎｔｅｒは、二つの画像（Ｉ１、Ｉ２）に対する異なる画像グリッドレベル間の類似度を表す。
【００３２】
即ち、二つの異なる画像（Ｉ１、Ｉ２）に含まれる同じ画像グリッドレベル間の類似度（Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｅｘａｃｔ）は、図３に示したように、同じレベルの各画像グリッドを比較して算出され、かつ、二つの異なる画像（Ｉ１、Ｉ２）に含まれる異なる画像グリッドレベル間の類似度（Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｉｎｔｅｒ）は、図４に示したように、異なるレベルの各画像グリッドを比較して算出される。
【００３３】
これを、図５（Ａ）及び５（Ｂ）を参照してより詳しく説明する。
二つの異なる画像の同じレベルに対し、対応する二つのセルの類似を全て加え合わせた後、その値に横比と縦比との差だけ横側と縦側に移動させながらそれぞれの二つのセルの類似度を合計すると、最終的に二つのセルの類似度が求められる。
【００３４】
このとき、二つの画像グリッド間のマッチング数は、二つの画像の特定レベルの横と縦それぞれの差の絶対値にそれぞれ１を足した後、それらをお互いに乗じてマッチング数を計算する。
【００３５】
例えば、図５（Ａ）に示したように、画像（Ｉ１）の横と縦とのグリッド数をＭ×Ｎとし、画像（Ｉ２）の横と縦とのグリッド数をＯ×Ｐとすると、二つの画像グリッド間の全体マッチング数は、（｜Ｍ−Ｏ｜＋１）×（｜Ｎ−Ｐ｜＋１）になる。
【００３６】
かつ、同じグリッドレベル（Ｍａｘ（Ｍ，Ｎ）＝Ｍａｘ（Ｏ，Ｐ））間のお互いに対応する二つのセルの類似度は、二つの画像グリッドの横縦比に従ってそれぞれ移動させて、二つの画像グリッドをマッチングさせながら算出する。
【００３７】
このような二つの画像（Ｉ１、Ｉ２）の同じレベル間の類似度、（Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｅｘａｃｔ）は、次式（３−１，３−２）により求められる。
【数３】
0003541011.tif 000004
【００３８】
【数４】
0003541011.tif 000005
は、同じレベル間の類似度（Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｅｘａｃｔ）をマッチングさせるとき、対応する二つのセルの縦側と横側とのマッチング和を表す。
【００３９】
対応する二つのセルの類似度（Ｓｉｍ＿ｏｆ＿ｃｏｒｒｅｓ＿ｔｗｏ＿ｃｅｌｌｓ）は、横側と縦側との比（Ｍ：Ｎ、Ｏ：Ｐ）に基づき、次式（４−１）〜（４−４）によって計算される。
【００４０】
【数５】
0003541011.tif 000006
【００４１】
ここで、上記式（４−１）は、ＰがＮより小さく、ＭがＯより小さいとき適用し、式（４−２）はグリッド（Ｇ１）の長さＮがグリッド（Ｇ２）の長さＰより短く、グリッド（Ｇ２）の幅Ｏがグリッド（Ｇ１）の幅Ｍより短いとき適用する。さらに、式（４−３）はグリッド（Ｇ２）の垂直長さＰがグリッド（Ｇ１）のＮより短く、グリッド（Ｇ１）の水平長さＭがグリッド（Ｇ２）のＯより短いとき適用し、式（４−４）はＧ１のＮがＧ２のＰより短く、ＭがＯより短いときに適用する。
【００４２】
このとき、第１レベルの画像グリッド（Ｇ１）の長さと、第２レベルの画像グリッド（Ｇ２）の長さとの差（｜Ｍ−Ｏ｜、｜Ｎ−Ｐ｜）に対する移動量（ｉ，ｊ）をそれぞれセル座標（ｘ、ｙ）に加算し、それら各開始点（ｉ，ｊ，ｘ，ｙ）を０にする。
【００４３】
一方、異なる二つの画像（Ｉ１、Ｉ２）の異なる画像グリッドレベル（Ｍａｘ（Ｍ，Ｎ）≠Ｍａｘ（Ｏ，Ｐ））間の類似度（Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｉｎｔｅｒ）は、異なる二つの画像グリッドレベルを比較して算出するが、このときは前記した同じ画像グリッドレベル類似度（Ｓｉｍ＿ｏｆ＿ｔｈｅ＿Ｅｘａｃｔ）を算出する過程と同様に行われる。
【００４４】
更に、異なる画像グリッドレベル間の画像グリッドマッチング数は、その縦横比（Ｍ：Ｎ、Ｏ：Ｐ）を考慮し、（｜Ｍ−Ｏ｜＋１）×（｜Ｎ−Ｐ｜＋１）によって算出される。
【００４５】
一方、カラー領域マッチング（Ｃｏｌｏｒ  Ｒｅｇｉｏｎ  Ｍａｔｃｈｉｎｇ）は、多重レベル画像グリッドのうち、代表カラー値の同様な領域を検出する方法として、同じ大きさのグリッドレベル（Ｅｘａｃｔ ｓｃａｌｅ ｍａｔｃｈｉｎｇ）から相対的な位置（Ｒｅｌａｔｉｖｅ Ｐｏｓｉｔｉｏｎ）と変位位置（Ｔｒａｎｓｌａｔｉｏｎ Ｐｏｓｉｔｉｏｎ）からカラー類似度を検出する方法と、異なる大きさの画像グリッドレベル（Ｉｎｔｅｒ−ｓｃａｌｅ  ｍａｔｃｈｉｎｇ）の相対的な位置と、異なる位置からカラー類似度を検出する方法とがある。
即ち、前記同じ画像グリッドレベル（Ｅｘａｃｔ ｓｃａｌ ｅｍａｔｃｈｉｎｇ）間のカラー領域マッチングは、参照対象画像のうち同じレベルのカラー領域を検出する方法として、比較対象の各画像の同じ画像グリッドレベルの相対的位置とマッチングさせてそのカラー領域の類似度を算出し、かつ、比較対象画像の同じレベルの変位位置とマッチングさせてそのカラー領域の類似度を算出する。
【００４６】
一方、異なる画像グリッドレベル間のカラー領域マッチングは、参照対象画像のうち異なるレベルのカラー領域を検出する方法で行われ、比較対象画像の異なる画像グリッドレベルのうち、同じレベルを有するカラー領域の類似度を算出する。
【００４７】
異なる画像グリッドレベルのカラー領域をマッチングする方法としては、比較対象画像の異なる画像グリッドレベルの同様な位置とマッチングさせ、そのカラー領域の類似度を算出し、かつ、参照対象画像の異なるレベルの変位位置とマッチングさせてそのカラー領域の類似度を算出する。
【００４８】
【発明の効果】
以上説明したように、本発明に係る多重レベルの画像グリッドデータ構造とそれを利用した画像検索方法においては、一つの画像グリッドデータ構造を多重レベルの画像グリッド構造に分割し、多重レベルグリッド構造を利用し、内容に基づく画像検索の際、ユーザの主観的な照会に効率よく応答し、特定条件下での画像検索を迅速かつ正確に行い得るという効果がある。
【図面の簡単な説明】
【図１】本発明に係る多重レベル画像グリッドデータ構造の実施形態として、３−レベル画像グリッドデータ構造を示した図面である。
【図２】本発明に係る多重レベル画像グリッドデータ構造を利用した画像検索方法の実施形態として、３−レベル画像グリッドデータ構造のレベル間のフィーチャーマッチングを具現する構成を示した図面である。
【図３】本発明に係る多重レベル画像グリッドデータ構造を利用した画像検索方法の他の実施形態として、３−レベル画像グリッドデータ構造の同じレベル間のフィーチャーマッチングを実施する構成を示した図面である。
【図４】本発明に係る多重レベル画像グリッドデータ構造を利用した画像検索方法の又他の実施形態として、３−レベル画像グリッドデータ構造の異なるレベル間のフィーチャーマッチングを実施する構成を示した図面である。
【図５】（Ａ）（Ｂ）、本発明に係る多重レベル画像グリッドデータ構造を利用した画像検索方法の他の実施形態を示した図面で、（Ａ）は、二つの同じ画像グリッドデータ構造を示し、（Ｂ）は、二つの画像グリッドデータ構造間のフィーチャーのマッチングを実施する過程を示す。
【図１】
0003541011.tif 000007
【図２】
0003541011.tif 000008
【図３】
0003541011.tif 000009
【図４】
0003541011.tif 000010
【図５】
0003541011.tif 000011