画像グループの表現方法、画像グループの記述子、画像グループの探索方法、コンピュータ読み取り可能な記憶媒体およびコンピュータシステム
【課題】 画像グループの表現方法および装置を提供する。
【解決手段】 本方法では、画像グループについて、色ドメインにおいてクラスタリングを行い、得られるクラスタの重心を支配的な色の値（１つまたは複数）とする。この支配的な色の値（１つまたは複数）について、画像グループをその支配的な色の値（１つまたは複数）に関して表す、支配的な色表現を導出する。色表現の成分は、色分布の分散、色の影響を示す重み、支配的な色の数、支配的な色に対応する画素の空間均一性を含む。
【解決手段】 本方法では、画像グループについて、色ドメインにおいてクラスタリングを行い、得られるクラスタの重心を支配的な色の値（１つまたは複数）とする。この支配的な色の値（１つまたは複数）について、画像グループをその支配的な色の値（１つまたは複数）に関して表す、支配的な色表現を導出する。色表現の成分は、色分布の分散、色の影響を示す重み、支配的な色の数、支配的な色に対応する画素の空間均一性を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像グループを特に色に関して表現する方法および装置に関し、また画像の探索および取り出しに関する。
【背景技術】
【０００２】
画像中に現れる色等の視覚的特徴を用いて画像を表現するための様々な技法が既知である。例えば既知の一技法では、各画素に色の値を割り当て、いくつかの色の値の範囲に対してビン（bin）を設定し、画像中の、それぞれの範囲の色の値を有する画素数をカウントすることによりカラーヒストグラムを導出する。次にこのカラーヒストグラムを画像表現として用いる。別の既知の技法では、画像中の１つまたは複数の支配的な色（dominant colour）を特定し、この支配的な色を用いて画像を表現する。
【０００３】
本発明は特に画像グループに関連する。これらの画像グループは例えば、ビデオの画像（フレームまたはフィールド）シーケンス、または任意の情報源からの、何らかの方法で関連付けられた任意の画像グループである可能性がある。例えば画像グループは、ビデオ中の１シーンまたは１ショットに関連する可能性がある。そのような画像グループの当該技術分野における用語はＧｒｏｕｐＯｆＦｒａｍｅｓ（フレームグループ）／ＧｒｏｕｐＯｆＰｉｃｔｕｒｅｓ（ピクチャグループ）である。以下ではこの用語をＧｏＦＧｏＰと呼ぶ。本明細書中において、画像という用語は、グループ中のフレーム／ピクチャを説明するために、ビデオフレームまたはフィールドであるか静止画であるかに関係なく用いられる。また、画像および画像領域という用語は、文脈から明らかである場合を除いて置き換え可能である。
【０００４】
画像グループを表現するための一手法は、その画像グループから１枚の画像を選択し、その１枚の画像をグループ全体の代表として扱うことである。次にその１枚の画像を、１枚の画像を表現するための既知の技法を用いて表現する。この１枚の画像は例えば、シーケンス中に現れる最初または最後の画像とするか、または画像グループを解析して、そのグループにおいて何らかの方法で特にそのグループを関心の視覚的特徴に関して表現している１枚の画像を特定してもよい。
【０００５】
別の手法は、その画像グループを集約する（aggregate）ことである。既存のＭＰＥＧ−７ Ｖｉｓｕａｌ Ｓｔａｎｄａｒｄ（ISO/IEC 15938-3）は、ビデオセグメントまたはグループのピクチャの色を、ＧｏＦＧｏＰ色記述子を用いて記述することを可能にする。これに関しては例えば、Manjunath、SalembierおよびSikora編「ＭＰＥＧ−７ Ｍｕｌｔｉｍｅｄｉａコンテント記述インタフェース入門（Introduction to MPEG-7 Multimedia content description interface）」（ISBN 0-471-48678-7）という本の第１３．５節に詳細に記載されている。３つの画像グループ集約技法、すなわち平均、中央値および共通集合（intersection）が記載されている。
【０００６】
各技法において、上述のようにグループ中の各画像についてカラーヒストグラムを導出する。平均技法では、カラーヒストグラムを積算し（accumulate）、次に積算した各ビンの値をＮで割って（ここでＮはグループ中の画像数）、平均ヒストグラムを作成する。中央値技法では、各ビンの値について、そのグループのヒストグラムの値を昇順／降順に並べ、それぞれのビンに中央値を割り当てる。共通集合ヒストグラムは、各ビンについて、そのグループのヒストグラムからその最小値をとることによって得られる。言い換えれば、共通集合ヒストグラムは、全ての画像に現れる特定の色または色の範囲（ビンに対応）の画素数を表す。
【０００７】
それぞれの場合に、集約したヒストグラム（平均、中央値または共通集合）を次に、スケーラブルな色記述子（Scalable Color Descriptor）（上記の本の第１３．４節を参照）を用いて表現する。これは、ハール（Haar）変換に基づく符号化方式をカラーヒストグラムの値に適用することを伴う。
【０００８】
Tong LinおよびHong-Jiang Zhang著「ショットの分類によるビデオシーンの自動抽出（Automatic video scene extraction by shot grouping）」という論文は、ショットをシーンに分類することに関する。１ショットを形成するフレームグループを解析して、各フレーム中の支配的な色のオブジェクトを決め、次にそのフレームグループを通して存在し続ける支配的な色のオブジェクトを決める。これにより、１ショットの支配的な色のヒストグラムが作成される。異なるショットの支配的な色のヒストグラムを比較する。２ショット間の相関性が高い場合、それらのショットを１シーンに分類する。
【発明の概要】
【課題を解決するための手段】
【０００９】
本発明の態様を添付の特許請求の範囲に記載する。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施形態によるシステムのブロック図である。
【図２Ａ】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図２Ｂ】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図３】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図４】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図５】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図６】画像を合成してスーパー画像を形成する図である。
【発明を実施するための形態】
【００１１】
本発明の一実施形態を添付図面を参照して説明する。
【００１２】
図１には、本発明の一実施形態によるシステムが示される。このシステムは、システムの動作を制御するための、メモリとプロセッサを少なくとも含むコンピュータのような制御ユニット１２と、画像およびテキストを含む出力を表示するために、制御ユニット１２に接続されるモニタのような表示ユニット１４と、制御ユニット１２に命令を入力するためのマウスのようなポインティングデバイス１６とを含む。また本システムは、デジタル形式の複数の画像グループを格納する画像データベース１８と、画像データベース１８に格納される各画像グループのために、以下にさらに詳細に記載される記述子情報を格納する記述子データベース２０とを含む。この例において、各画像グループはビデオシーケンスの１ショットに対応する。ビデオシーケンスをショットに分割する既知の技法には様々なものがあるが、ここでは詳述しない。本発明は任意の画像グループまたは画像領域（画像内の領域を含む）に適用することができる。画像はグループ単位で格納されるか、あるいは例えば、どの画像が同じグループに属すかを示す識別子があってもよい。
【００１３】
画像データベース１８および記述子データベース２０はそれぞれ制御ユニット１２に接続される。またそのシステムは、制御ユニット１２の制御下にあるコンピュータプログラムであり、記述子データベース２０に関連して動作するサーチエンジン２２も含む。
【００１４】
この実施形態では、システム要素は画像ライブラリのような１つのサイトに設けられ、システムの構成要素は永続的にリンクされる。
【００１５】
記述子データベース２０は、画像データベース内に格納される全ての画像の記述子、さらに画像データベース内の全画像グループの記述子を格納する。画像記述子およびグループ記述子は後述のように導出される。
【００１６】
各画像には、それぞれの画像を画像の支配的な色（単数または複数）に関して表現する画像記述子が関連付けられている。この実施形態では、画像記述子は実質的に、本発明者らの同時係属中出願ＷＯ００／６７２０３（この内容は参照により本明細書中に援用される）に記載されるように導出される。
【００１７】
画像記述子の導出の概要を以下に記載する。各画像は複数の画素を有し、各画素にはＲＧＢのような関連する色空間における色の値が関連付けられる。
【００１８】
色の値とそれに対応する画素は、支配的な色およびどの色がそれぞれの支配的な色に対応するかを決めるために色ドメインにおいてクラスタリングされる。これは、上記のＭＰＥＧ−７の本の第１３．３．１節に記載されているように、一般化ロイドアルゴリズムのような適切なクラスタリングアルゴリズムを用いて行われる。
【００１９】
クラスタリング手順から得られるクラスタの重心を支配的な色の値として用い、それぞれのクラスタを形成する画素のセットを、後述のようなさらなるフィールド（重みおよび色分散）の計算のために格納する。
【００２０】
あるいは支配的な色は、ＷＯ００／６７２０３に記載されるようなヒストグラム手法を用いて導出することもできる。
【００２１】
その場合、画像のカラーヒストグラムは、関連する色空間における所定数の色の値または色の値の範囲を選択し、画像中の、各色の値または関連する範囲の値を有する画素数をカウントすることによって導出される。
【００２２】
ヒストグラムは通常１つまたは複数のピークを有し、それらのピーク（またはそのうちで最も高い所定数のピークのような部分集合）を支配的な色として選択し、色の値／画素を色ドメインにおいて支配的な色に関してクラスタリングする。
【００２３】
色の値をクラスタリングしたら、支配的な各色について色分散値を求め、支配的な各色について、その支配的な色を中心とするそれぞれのクラスタの色の値の分散を表す。支配的な色は、関連するクラスタにおける色分布の平均値として考えることができる。
【００２４】
分散の計算は、次式を用いて表すことができる。
【００２５】
【数１】
【００２６】
ここで、ｊは色成分の添字であり（index）、ｍｊは支配的な色のｊ番目の成分であり、ｐｋｊはｋ番目の画素値のｊ番目の成分であり、総和は検討中の支配的な色に対応するＮ個の画素にわたって行う。
【００２７】
記述子は支配的な各色の重み値も含み、これは画像内での支配的な各色の相対的な重要度の尺度である。この例において重みは、支配的な色の値に対応するクラスタ内の画素数の、画像の総画素数に対する比である。この重みはパーセントで表すことができる。
【００２８】
支配的な色の値とそのそれぞれの分散および重みを結合して画像の色記述子を形成する。この記述子は、支配的な色の数を示す次数（degree）ｎのような他の成分を有してもよい。記述子はまた共分散値Ｃｉｊを含んでもよく、ここでｉおよびｊは、支配的な色およびクラスタの各々について関連する色空間における色成分ならびに分散値を表す。
【００２９】
各画像の色記述子は記述子データベースに格納される。
【００３０】
支配的な色記述子は画像を表すヒストグラムと同じではないことに留意することが重要である。支配的な色記述子は、初期の処理ステップにおいて決定しておくことができる画像中の支配的な色の値を含む。画像のヒストグラム表現は支配的な色を含むが、支配的な色は特定されていない。支配的な色記述子は、支配的な色または支配的な各色に対する色分布の分散に対応する値のような他の値も含む可能性があるが、ヒストグラム表現は分散または他のそのような値を計算するかまたは求めることを伴わない。支配的な色記述子の他の成分には例えば、画像中の支配的な色の影響を示す重み、画像中の支配的な色数、および画像中の支配的な色に対応する画素の空間均一性が含まれる可能性がある。
【００３１】
第１の実施形態において、画像グループのグループ記述子は以下のように導出される。
【００３２】
画像グループの各画像の画像記述子を記述子データベースから取り出す。次に画像記述子を結合してグループ記述子を形成する。
【００３３】
グループ記述子は画像記述子（支配的な色、分散、重み等）と同様の形式を有する。好ましくは、グループ記述子における支配的な色数は１〜８である。しかしながら、支配的な色数は無限であるか、あるいは所定の最大値を設定することができる。画像記述子における支配的な色数もまた無限であるか、あるいは所定の最大値により制限することができる。画像記述子の最大値とグループ記述子の最大値は同じである必要はなく、例えば画像記述子の支配的な色数がグループ記述子より多くてもよい。
【００３４】
この例では、１つのグループに２枚の画像があり、２つのそれぞれの画像記述子を以下のように結合する。
【００３５】
大まかに言えば、画像記述子は、色空間におけるクラスタの近接度（proximity）に基づいて画像中のクラスタをマージすることによって結合される。
【００３６】
図２Ａおよび図２Ｂは２枚の画像の色空間における抽象的なクラスタ表現である。図２Ａは第１の画像を表し、図２Ｂは第２の画像を表す。それぞれの場合に、円はそれぞれの支配的な色のクラスタを表す。簡略化のために、色空間を２次元で示すが、色空間は通常３次元である。また、クラスタは色空間における円に必ずしも対応する必要はなく、簡略化のためにそのように示されており、円はクラスタの重みを示すものではない。以下では、図２Ａおよび図２Ｂに示すような表現（すなわち支配的な色とそれぞれのクラスタに関する表現）をクラスタ記述子として説明する。
【００３７】
図２Ａおよび図２Ｂの２つのクラスタ記述子を結合して、クラスタのスーパー記述子（super-descriptor）を形成する。これを図３に示す。
【００３８】
次に、色空間における適切な距離測定を用いて、スーパー記述子における（上記で定義したような）各クラスタペア間の距離を求める。この例において、距離は色空間におけるユークリッド距離である。
【００３９】
この例において、第１の画像には２つの支配的な色と２つのクラスタがあり、第２の画像には３つの支配的な色と３つのクラスタがあり、それぞれに１〜５の番号を付けた。支配的な各色は、図２ないし図５において×印で示すＲＧＢ色空間の点に対応する。クラスタペア間の距離は３−ＤのＲＧＢ空間におけるクラスタの重心間の距離である。第１および第２の画像における支配的な色の各ペア間の距離を、この例では同じ画像のクラスタを含めて計算する。距離の測定値が最も小さい支配的な色のペアを選択する。
【００４０】
次に、その２つの支配的な色に対応するクラスタをマージする。
【００４１】
この例では図３に示すように、最も近い２つのクラスタはクラスタ１および３であり、これらを以下のようにマージする。
【００４２】
マージしたクラスタの支配的または代表的な色の値は２つのクラスタの支配的な色の加重平均であり、ここで重みは上記で定義した通りである。したがって、２つの支配的な色ｍ１、ｍ２とそれぞれの重みＷ１およびＷ２について、マージした支配的な色ｍは次の値を有する。
ｍ＝ｗ１ｍ１＋ｗ２ｍ２
ここで、ｗ１、ｗ２は相対的な重みであり、それぞれＷ１／Ｗ１＋Ｗ２およびＷ２／Ｗ１＋Ｗ２である。
【００４３】
マージした２つのクラスタの分散を用いて、マージしたクラスタの分散も計算する。この例では、各色成分を個別に扱い、マージしたクラスタの分散は２つのガウス分布の加重平均であると仮定する。この結果、マージしたクラスタの分散について次式が得られる。
σ２＝ｗ１σ１２＋ｗ２σ２２＋ｗ１ｗ２（ｍ１−ｍ２）２
ここで、σ１２、σ２２は成分クラスタの分散であり、ｍ１、ｍ２はそれらの平均であり、ｗ１、ｗ２は上記で定義したような相対的な重みである。
【００４４】
マージしたクラスタの重みＷはＷ１＋Ｗ２である。
【００４５】
マージしたクラスタは新たなクラスタとして扱い、重み、平均および分散は上記で説明した通りである。
【００４６】
これは図４に示されており、クラスタ１および３はマージされて新たなクラスタ６を形成している。
【００４７】
次にマージするステップをもう１度反復する。１度目の反復でマージした２つのクラスタ１および３はさらなる検討から除外し、図４に示すようにマージしたクラスタ６に置き換える。
【００４８】
次に、上記で略述したように、マージしたクラスタ６を含めて色空間において最も近いクラスタペアを特定しそれらをマージすることによって、マージするステップを繰り返す。
【００４９】
この例において、２度目の反復では、クラスタ２および４が最も近いクラスタペアである。これらをマージして新たなクラスタ７を作成し、クラスタ２および４の支配的な色、重みおよび分散から、上に記載したように支配的な色、重みおよび分散を導出する。図５に示すようにマージしたクラスタ７でクラスタ２および４を置き換える。
【００５０】
所定の条件を満たすまでマージの反復を繰り返す。例えば所定の条件として、残るクラスタ数の合計（第１および第２の画像における、マージされたクラスタと残っている元のクラスタの合計）が所定数になるまでマージを続けることとすることができる。あるいは所定の条件は、残りのクラスタの各ペア間の距離が所定の値よりも大きくなるまでマージを続けることとすることができる。あるいは本方法は所定回数の反復を含んでもよい。所定の条件のうち２つ以上を組み合わせてもよい。
【００５１】
この例では、所定数（３つ）のクラスタが残るまでマージを繰り返す。
【００５２】
上記の例では、マージしたクラスタをさらなる反復において検討する。しかしながら、マージしたクラスタはさらなる反復から除外してもよい。また上記の例において、クラスタを同一画像内の他のクラスタとマージすることもできるが、別法においてクラスタは、１回目の反復および／または任意の以後の反復において別の画像に現れるクラスタのみとマージしてもよい。これにより距離の測定回数が減る。
【００５３】
クラスタに関して説明したが、マージは、記述子すなわち支配的な色、分散および重みの値に対して行い、必ずしもクラスタ自体を解析する必要はないことが理解される。
【００５４】
反復が終了したら、残っているクラスタを用いてグループ記述子を形成する。より具体的には、最終的なクラスタの各々について、代表的または支配的な色、それぞれの分散、およびそれぞれの重みがある。これらを、最終的なクラスタ数を示す次数ｍとともに結合してグループ記述子を形成する。このグループ記述子は、色空間、または表現に用いられる色量子化の指示のような他の因子を含んでいてもよい。グループ記述子はＧｏＦＧｏＰの支配的な色記述子である。
【００５５】
上記の例では、画像グループには２枚の画像しかない。しかしながら本方法は、３枚以上の画像を含むグループにも適用することができる。上記のようにグループ中の各画像のクラスタ記述子を全て結合してスーパー記述子を形成することもできる。あるいは、画像グループをサブグループ、例えば連続するかまたは連続しない２枚組または３枚組のグループに結合して、サブグループの記述子を同様の方法で結合してもよい。
【００５６】
１つのグループに多数の画像がある場合、上記の方法は多数のクラスタならびに多数のクラスタ間距離の計算を伴う可能性がある。
【００５７】
上記に鑑みて、上記方法の変形は、ビデオショットまたはコレクション中の画像のほとんどは非常に類似しており、対応する記述子も類似するという事実を考慮する。これはほとんどのクラスタが、精度をそれほど損なうことなくフレーム毎にマージできることを意味する。
【００５８】
より詳細には、この変形は、画像グループの画像を連続して考慮する。上述の例のように、画像記述子は既に導出されて記述子データベースに格納されている。画像グループの第１および第２の画像のクラスタ記述子を取り出す。次に、画像ペアの各クラスタ間の距離を求める。クラスタペア間の距離が所定の閾値未満となるものがあれば、そのクラスタペアをマージする。画像ペアのマージしたクラスタと任意の残りのクラスタを上記で説明したようにスーパー記述子に集める。次に、次の画像のクラスタ記述子を取り出し、同様にして最初の２枚の画像のスーパー記述子とマージする。すなわち、近いクラスタをマージして新たなスーパー記述子を形成する。全ての画像のクラスタ記述子を検討したら、結果として得られるスーパー記述子を、最初の例に記載したように全ての残りのクラスタを用いてマージする。
【００５９】
上記説明では、クラスタ記述子は既に導出していた。別法として、画像を取り出すかまたは供給し、クラスタをマージする前に画像から記述子を導出してもよい。
【００６０】
上述の第１の実施形態において、ＧｏＦＧｏＰの記述子は、グループ中の各画像の記述子を集約することによって導出する。
【００６１】
第２の実施形態では、画像を画像または画素ドメインにおいて集約し、次に集約した画像から支配的な色記述子を導出してＧｏＦＧｏＰの支配的な色記述子を作成する。したがって図６に示すように、グループ中にＮ枚のｍ×ｍの画素を含む画像８がある場合、スーパー画像９は（Ｎ×ｍ）×ｍの画素配列とみなすことができる。
【００６２】
第１の実施形態と対照的に、第２の実施形態は各画像の画像記述子を用いず、画像を直接操作する。
【００６３】
画像を集約した後、第１の実施形態に関して上述した技法を用いてスーパー画像から支配的な色記述子を導出する。
【００６４】
第２の実施形態の利点は、抽出プロセスの精度が落ちないことである。しかしながら、全ての画像を検討する際には大量の複雑性、特にメモリが必要となる可能性がある。この複雑性の問題を克服するために、画像を時間的かつ／または空間的にサブサンプリングしてもよい。
【００６５】
上記において、画像を画像または画素ドメインで集約し、次に集約した画像から支配的な色記述子を導出してＧｏＦＧｏＰの支配的な色記述子を作成する。あるいは、各画像を色ドメインにおいて（例えば各画像のヒストグラムの形態で）集約し、集約したヒストグラムから支配的な色記述子を導出することもできる。例えば、各画像のカラーヒストグラムは導出するか、メモリから取り出すことができる。次に、カラーヒストグラム同士を加算することにより結合し、スーパー画像のヒストグラムを形成する。このヒストグラムは、スーパー画像を形成する画像の数により正規化することができる。最後に、第１の実施形態に関して上述した技法を用いて、スーパー画像のヒストグラムから支配的な色記述子を導出する。言い換えれば、スーパー画像のヒストグラムのピーク（支配的な色）、ならびにそれぞれの分散および重みを選択する。
【００６６】
支配的な色記述子を導出する前に画像を集約するための他の技法を用いてもよい。例えば、各画像のヒストグラム同士を加算する代わりに、画像グループの平均、中央値または共通集合を計算してもよい。次に結果として得られた平均、中央値または共通集合ヒストグラムから支配的な色のグループ記述子を導出する。
【００６７】
画像／画素ドメインおよび色／ヒストグラムドメインにおける集約に当てはまる第２の実施形態の変形では、後述のように画像グループを時間的にサブサンプリングしてもよい。この例において、各画像のクラスタ記述子を導出するかまたは取り出す。ＧｏＦＧｏＰ記述子を導出する際にグループ中のどの画像を用いるかをクラスタ記述子の類似度に基づいて決定する。
【００６８】
画像グループのシーケンスの１番目の画像が最初のスーパー画像を形成する。それ以後の画像は、ある画像とスーパー画像（最初は１番目の画像）に加えた最後の画像とのクラスタ記述子間の類似度が所定の決定条件を満たすまで廃棄する。ある画像がこの条件を満たす場合、これをスーパー画像に加える。次に、所定の条件が再び満たされるまでグループ中のそれ以後の画像をスーパー画像に加えた最後の画像と比較することを同様に行い、グループ中の全画像を検討し終えるまで続ける。次に結果として得られたスーパー画像から支配的な色記述子を導出する。
【００６９】
画像の類似度の１つの可能な決定基準は、本発明者らの同時係属中の出願ＷＯ００／６７２０３に記載されるような、それぞれの支配的な色記述子間のマッチング関数の値であるか、あるいは上記のＭＰＥＧ−７の本に記載されるようなマッチング関数を用いる。別の基準は、上述の「オンライン」マージの結果とすることもできる。この場合の「決定基準」は、全てのクラスタが既存の記述子にマージされた場合に満たされる。全ての画像について支配的な色を抽出することを避ける別の手法は、粗なカラーヒストグラムを計算し、ヒストグラムマッチング関数の値を基準として用いることであろう。
【００７０】
これらの基準は両方とも、さらなるパラメータ（第１の場合にはそれ未満ではマッチング関数の値が小さいとみなされる閾値、第２の場合にはマージ閾値）を指定することを必要とする。メモリに制限がある場合に特に当てはまる代替的な手法は、閾値を採用して、集めた画像数が指定された限界を超えないようにすることであろう。
【００７１】
第３の実施形態は、画像グループの支配的な色記述子のグループからＧｏＦＧｏＰの支配的な色記述子を導出する。より具体的には、画像グループについて、それぞれの支配的な色記述子を記述子データベースから取り出す（既に導出されていない場合には導出する）。
【００７２】
支配的な各色記述子について、その記述子とグループの残りの記述子それぞれの間の距離を測定する。この結果、各記述子について距離測定値のセットが生じ、これらを加算して各記述子の全体的な距離測定値を得る。全体的な距離測定値が最も小さい記述子を代表的な記述子として選択し、ＧｏＦＧｏＰの支配的な色記述子として扱う。
【００７３】
代表的な記述子を選択する、好ましくはグループ中の画像の画像記述子の少なくとも一部に関するテストまたは比較を伴う他の方法を用いることもできる。別の例として、これは、記述子全体について行った場合、ＭＰＥＧ−７において規定されるような歪尺度に基づいて行ってもよい。
【００７４】
非常に近い記述子を事前に拒絶して計算を減らすことも可能である。
【００７５】
上記ではＧｏＦＧｏＰ記述子、特にＧｏＦＧｏＰの支配的な色記述子を導出するための様々な方法を記載した。
【００７６】
ＧｏＦＧｏＰ記述子には、画像グループの探索および取り出しにおけるような様々な用途がある。例えばユーザは、入力画像または画像グループに対応する画像グループを探索したい場合がある。
【００７７】
探索方法の概要を以下に記載する。
【００７８】
図１を参照すると、ユーザが、スキャナやデジタルカメラのような適切な手段を用いて、あるいはコンピュータが表示する様々な画像から問い合わせ画像を選択することによって、あるいは任意のそのような画像の領域を選択することによって問い合わせ画像を入力する。上述のように画像の支配的な色記述子を導出する。次に問い合わせの支配的な色記述子を、記述子データベースに格納されたＧｏＦＧｏＰの支配的な色記述子の各々と比較する。ＧｏＦＧｏＰの支配的な色記述子は１枚の画像の支配的な色記述子と同じ形式であるので、マッチングは例えば、ＷＯ００／６７２０３に記載されるようなマッチング関数またはそれと同様のもの、あるいは上記のＭＰＥＧ−７の本の第１３．３．２節に記載されるようなマッチング関数を用いて行うことができる。問い合わせ記述子は任意選択で、データベースに格納されている可能性のある１枚の画像の記述子と比較してもよい。
【００７９】
マッチング関数の結果を順番に並べて、マッチング関数が最も近い一致を示す画像グループを取り出す。最も近い一致の１つまたは複数の画像を表示してもよい。
【００８０】
問い合わせを行う他の方法を用いることもできる。問い合わせは、画像グループを選択し、そのグループについて上述のようなＧｏＦＧｏＰ記述子を抽出することによって行うことができる。このグループは、例えばフレームの範囲を選択することによって明示的に、あるいは例えばビデオ中のキーフレームを選択することによって暗示的に選択することができ、この場合は適切なアルゴリズムを用いてキーフレームを含む「ショット」を導出する。
【００８１】
本発明によるシステムは例えば、画像ライブラリ内に設けることができる。別法では、そのデータベースは、システムの制御ユニットから遠隔に配置されており、電話線のような一時的なリンクによって、あるいはインターネットのようなネットワークによって制御ユニットに接続される場合がある。画像および記述子データベースは例えば、永久記憶装置内に、あるいはＣＤ−ＲＯＭまたはＤＶＤのようなポータブルデータ記憶媒体上に設けられる場合がある。
【００８２】
本発明の１実施形態として上述したシステムはコンピュータシステムの形態である。このコンピュータシステムは、本発明の１実施形態による方法を実行する適切なプログラムを用いてプログラムされている標準的なコンピュータであってよい。プログラムは、固定または永久記憶装置または取り外し可能な記憶手段を含む任意の適切な記憶媒体に格納されることができる。システムは、例えば特定のチップを含む特定のハードウェアおよび／またはソフトウェアを用いて変更することができる。本発明は、特定のハードウェアおよび／またはソフトウェアを含む特別に適応させた装置において実施することもできる。
【００８３】
上記の説明では、色表現を赤、緑および青の色成分に関して説明した。当然ながら、色相、彩度および明度、またはＹＵＶ座標系、あるいは任意の色空間における色成分のサブセット、例えばＨＳＩの色相と彩度のみを用いた表現等の他の表現を用いることもできる。
【００８４】
上述した本発明の実施形態は、画像および画像グループについて導出した記述子を用いる。しかしながら、画像記述子は画像の領域に関するものであってもよく、ＧｏＦＧｏＰ記述子も同様に画像の領域に基づくものであってよい。領域は長方形のブロックであるか、あるいは異なる形状およびサイズの領域を用いることもできる。別法では、記述子は、オブジェクト、例えば車、家または人に対応する画像の領域について導出してもよい。いずれの場合にも、記述子は画像の全てあるいはその一部のみについて導出される場合がある。また、画像領域グループを形成する画像中の複数の領域に上記方法を適用することによって、ＧｏＦＧｏＰグループ記述子を１枚の画像について導出することもできる。
【００８５】
探索手順では、ユーザは単純な色の問い合わせを入力するかまたは画像ブロックを選択する代わりに、例えばポインティングデバイスを用いて、例えば画像のある領域を囲むことによりその領域を記述することができ、すると制御ユニットは、その領域の記述子を導出して、それを上述と同様の方法で探索に用いる。また、探索を開始するために画像データベースに既に格納されている画像を用いる代わりに、例えば、画像スキャナまたはデジタルカメラを用いて画像をシステムに入力することもできる。そのような状況で探索を行うために、ここでもシステムがまず、画像または画像領域の記述子を自動的に、あるいはユーザが決定した通りに導出する。
【００８６】
本発明の適切な態様はハードウェアまたはソフトウェアを用いて実施することができる。
【００８７】
上記の実施形態では、代表的な各色のクラスタ分布をガウス関数を用いて近似し、それらの関数の平均、分散および共分散を記述子の値に用いた。しかしながら他の関数またはパラメータを用いて、例えば正弦または余弦のような基底関数を用い、これらの関数に基づく記述子を用いて、成分の分布を近似することもできる。
【符号の説明】
【００８８】
１〜７ クラスタ、８（１）〜８（ｎ） 画像、９ スーパー画像、１２ 制御ユニット、１４ 表示ユニット、１６ ポインティングデバイス、１８ 画像データベース、２０ 記述子データベース、２２ サーチエンジン。
【技術分野】
【０００１】
本発明は、画像グループを特に色に関して表現する方法および装置に関し、また画像の探索および取り出しに関する。
【背景技術】
【０００２】
画像中に現れる色等の視覚的特徴を用いて画像を表現するための様々な技法が既知である。例えば既知の一技法では、各画素に色の値を割り当て、いくつかの色の値の範囲に対してビン（bin）を設定し、画像中の、それぞれの範囲の色の値を有する画素数をカウントすることによりカラーヒストグラムを導出する。次にこのカラーヒストグラムを画像表現として用いる。別の既知の技法では、画像中の１つまたは複数の支配的な色（dominant colour）を特定し、この支配的な色を用いて画像を表現する。
【０００３】
本発明は特に画像グループに関連する。これらの画像グループは例えば、ビデオの画像（フレームまたはフィールド）シーケンス、または任意の情報源からの、何らかの方法で関連付けられた任意の画像グループである可能性がある。例えば画像グループは、ビデオ中の１シーンまたは１ショットに関連する可能性がある。そのような画像グループの当該技術分野における用語はＧｒｏｕｐＯｆＦｒａｍｅｓ（フレームグループ）／ＧｒｏｕｐＯｆＰｉｃｔｕｒｅｓ（ピクチャグループ）である。以下ではこの用語をＧｏＦＧｏＰと呼ぶ。本明細書中において、画像という用語は、グループ中のフレーム／ピクチャを説明するために、ビデオフレームまたはフィールドであるか静止画であるかに関係なく用いられる。また、画像および画像領域という用語は、文脈から明らかである場合を除いて置き換え可能である。
【０００４】
画像グループを表現するための一手法は、その画像グループから１枚の画像を選択し、その１枚の画像をグループ全体の代表として扱うことである。次にその１枚の画像を、１枚の画像を表現するための既知の技法を用いて表現する。この１枚の画像は例えば、シーケンス中に現れる最初または最後の画像とするか、または画像グループを解析して、そのグループにおいて何らかの方法で特にそのグループを関心の視覚的特徴に関して表現している１枚の画像を特定してもよい。
【０００５】
別の手法は、その画像グループを集約する（aggregate）ことである。既存のＭＰＥＧ−７ Ｖｉｓｕａｌ Ｓｔａｎｄａｒｄ（ISO/IEC 15938-3）は、ビデオセグメントまたはグループのピクチャの色を、ＧｏＦＧｏＰ色記述子を用いて記述することを可能にする。これに関しては例えば、Manjunath、SalembierおよびSikora編「ＭＰＥＧ−７ Ｍｕｌｔｉｍｅｄｉａコンテント記述インタフェース入門（Introduction to MPEG-7 Multimedia content description interface）」（ISBN 0-471-48678-7）という本の第１３．５節に詳細に記載されている。３つの画像グループ集約技法、すなわち平均、中央値および共通集合（intersection）が記載されている。
【０００６】
各技法において、上述のようにグループ中の各画像についてカラーヒストグラムを導出する。平均技法では、カラーヒストグラムを積算し（accumulate）、次に積算した各ビンの値をＮで割って（ここでＮはグループ中の画像数）、平均ヒストグラムを作成する。中央値技法では、各ビンの値について、そのグループのヒストグラムの値を昇順／降順に並べ、それぞれのビンに中央値を割り当てる。共通集合ヒストグラムは、各ビンについて、そのグループのヒストグラムからその最小値をとることによって得られる。言い換えれば、共通集合ヒストグラムは、全ての画像に現れる特定の色または色の範囲（ビンに対応）の画素数を表す。
【０００７】
それぞれの場合に、集約したヒストグラム（平均、中央値または共通集合）を次に、スケーラブルな色記述子（Scalable Color Descriptor）（上記の本の第１３．４節を参照）を用いて表現する。これは、ハール（Haar）変換に基づく符号化方式をカラーヒストグラムの値に適用することを伴う。
【０００８】
Tong LinおよびHong-Jiang Zhang著「ショットの分類によるビデオシーンの自動抽出（Automatic video scene extraction by shot grouping）」という論文は、ショットをシーンに分類することに関する。１ショットを形成するフレームグループを解析して、各フレーム中の支配的な色のオブジェクトを決め、次にそのフレームグループを通して存在し続ける支配的な色のオブジェクトを決める。これにより、１ショットの支配的な色のヒストグラムが作成される。異なるショットの支配的な色のヒストグラムを比較する。２ショット間の相関性が高い場合、それらのショットを１シーンに分類する。
【発明の概要】
【課題を解決するための手段】
【０００９】
本発明の態様を添付の特許請求の範囲に記載する。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施形態によるシステムのブロック図である。
【図２Ａ】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図２Ｂ】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図３】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図４】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図５】本発明の一実施形態による画像記述子のマージ方法を示すグラフである。
【図６】画像を合成してスーパー画像を形成する図である。
【発明を実施するための形態】
【００１１】
本発明の一実施形態を添付図面を参照して説明する。
【００１２】
図１には、本発明の一実施形態によるシステムが示される。このシステムは、システムの動作を制御するための、メモリとプロセッサを少なくとも含むコンピュータのような制御ユニット１２と、画像およびテキストを含む出力を表示するために、制御ユニット１２に接続されるモニタのような表示ユニット１４と、制御ユニット１２に命令を入力するためのマウスのようなポインティングデバイス１６とを含む。また本システムは、デジタル形式の複数の画像グループを格納する画像データベース１８と、画像データベース１８に格納される各画像グループのために、以下にさらに詳細に記載される記述子情報を格納する記述子データベース２０とを含む。この例において、各画像グループはビデオシーケンスの１ショットに対応する。ビデオシーケンスをショットに分割する既知の技法には様々なものがあるが、ここでは詳述しない。本発明は任意の画像グループまたは画像領域（画像内の領域を含む）に適用することができる。画像はグループ単位で格納されるか、あるいは例えば、どの画像が同じグループに属すかを示す識別子があってもよい。
【００１３】
画像データベース１８および記述子データベース２０はそれぞれ制御ユニット１２に接続される。またそのシステムは、制御ユニット１２の制御下にあるコンピュータプログラムであり、記述子データベース２０に関連して動作するサーチエンジン２２も含む。
【００１４】
この実施形態では、システム要素は画像ライブラリのような１つのサイトに設けられ、システムの構成要素は永続的にリンクされる。
【００１５】
記述子データベース２０は、画像データベース内に格納される全ての画像の記述子、さらに画像データベース内の全画像グループの記述子を格納する。画像記述子およびグループ記述子は後述のように導出される。
【００１６】
各画像には、それぞれの画像を画像の支配的な色（単数または複数）に関して表現する画像記述子が関連付けられている。この実施形態では、画像記述子は実質的に、本発明者らの同時係属中出願ＷＯ００／６７２０３（この内容は参照により本明細書中に援用される）に記載されるように導出される。
【００１７】
画像記述子の導出の概要を以下に記載する。各画像は複数の画素を有し、各画素にはＲＧＢのような関連する色空間における色の値が関連付けられる。
【００１８】
色の値とそれに対応する画素は、支配的な色およびどの色がそれぞれの支配的な色に対応するかを決めるために色ドメインにおいてクラスタリングされる。これは、上記のＭＰＥＧ−７の本の第１３．３．１節に記載されているように、一般化ロイドアルゴリズムのような適切なクラスタリングアルゴリズムを用いて行われる。
【００１９】
クラスタリング手順から得られるクラスタの重心を支配的な色の値として用い、それぞれのクラスタを形成する画素のセットを、後述のようなさらなるフィールド（重みおよび色分散）の計算のために格納する。
【００２０】
あるいは支配的な色は、ＷＯ００／６７２０３に記載されるようなヒストグラム手法を用いて導出することもできる。
【００２１】
その場合、画像のカラーヒストグラムは、関連する色空間における所定数の色の値または色の値の範囲を選択し、画像中の、各色の値または関連する範囲の値を有する画素数をカウントすることによって導出される。
【００２２】
ヒストグラムは通常１つまたは複数のピークを有し、それらのピーク（またはそのうちで最も高い所定数のピークのような部分集合）を支配的な色として選択し、色の値／画素を色ドメインにおいて支配的な色に関してクラスタリングする。
【００２３】
色の値をクラスタリングしたら、支配的な各色について色分散値を求め、支配的な各色について、その支配的な色を中心とするそれぞれのクラスタの色の値の分散を表す。支配的な色は、関連するクラスタにおける色分布の平均値として考えることができる。
【００２４】
分散の計算は、次式を用いて表すことができる。
【００２５】
【数１】
【００２６】
ここで、ｊは色成分の添字であり（index）、ｍｊは支配的な色のｊ番目の成分であり、ｐｋｊはｋ番目の画素値のｊ番目の成分であり、総和は検討中の支配的な色に対応するＮ個の画素にわたって行う。
【００２７】
記述子は支配的な各色の重み値も含み、これは画像内での支配的な各色の相対的な重要度の尺度である。この例において重みは、支配的な色の値に対応するクラスタ内の画素数の、画像の総画素数に対する比である。この重みはパーセントで表すことができる。
【００２８】
支配的な色の値とそのそれぞれの分散および重みを結合して画像の色記述子を形成する。この記述子は、支配的な色の数を示す次数（degree）ｎのような他の成分を有してもよい。記述子はまた共分散値Ｃｉｊを含んでもよく、ここでｉおよびｊは、支配的な色およびクラスタの各々について関連する色空間における色成分ならびに分散値を表す。
【００２９】
各画像の色記述子は記述子データベースに格納される。
【００３０】
支配的な色記述子は画像を表すヒストグラムと同じではないことに留意することが重要である。支配的な色記述子は、初期の処理ステップにおいて決定しておくことができる画像中の支配的な色の値を含む。画像のヒストグラム表現は支配的な色を含むが、支配的な色は特定されていない。支配的な色記述子は、支配的な色または支配的な各色に対する色分布の分散に対応する値のような他の値も含む可能性があるが、ヒストグラム表現は分散または他のそのような値を計算するかまたは求めることを伴わない。支配的な色記述子の他の成分には例えば、画像中の支配的な色の影響を示す重み、画像中の支配的な色数、および画像中の支配的な色に対応する画素の空間均一性が含まれる可能性がある。
【００３１】
第１の実施形態において、画像グループのグループ記述子は以下のように導出される。
【００３２】
画像グループの各画像の画像記述子を記述子データベースから取り出す。次に画像記述子を結合してグループ記述子を形成する。
【００３３】
グループ記述子は画像記述子（支配的な色、分散、重み等）と同様の形式を有する。好ましくは、グループ記述子における支配的な色数は１〜８である。しかしながら、支配的な色数は無限であるか、あるいは所定の最大値を設定することができる。画像記述子における支配的な色数もまた無限であるか、あるいは所定の最大値により制限することができる。画像記述子の最大値とグループ記述子の最大値は同じである必要はなく、例えば画像記述子の支配的な色数がグループ記述子より多くてもよい。
【００３４】
この例では、１つのグループに２枚の画像があり、２つのそれぞれの画像記述子を以下のように結合する。
【００３５】
大まかに言えば、画像記述子は、色空間におけるクラスタの近接度（proximity）に基づいて画像中のクラスタをマージすることによって結合される。
【００３６】
図２Ａおよび図２Ｂは２枚の画像の色空間における抽象的なクラスタ表現である。図２Ａは第１の画像を表し、図２Ｂは第２の画像を表す。それぞれの場合に、円はそれぞれの支配的な色のクラスタを表す。簡略化のために、色空間を２次元で示すが、色空間は通常３次元である。また、クラスタは色空間における円に必ずしも対応する必要はなく、簡略化のためにそのように示されており、円はクラスタの重みを示すものではない。以下では、図２Ａおよび図２Ｂに示すような表現（すなわち支配的な色とそれぞれのクラスタに関する表現）をクラスタ記述子として説明する。
【００３７】
図２Ａおよび図２Ｂの２つのクラスタ記述子を結合して、クラスタのスーパー記述子（super-descriptor）を形成する。これを図３に示す。
【００３８】
次に、色空間における適切な距離測定を用いて、スーパー記述子における（上記で定義したような）各クラスタペア間の距離を求める。この例において、距離は色空間におけるユークリッド距離である。
【００３９】
この例において、第１の画像には２つの支配的な色と２つのクラスタがあり、第２の画像には３つの支配的な色と３つのクラスタがあり、それぞれに１〜５の番号を付けた。支配的な各色は、図２ないし図５において×印で示すＲＧＢ色空間の点に対応する。クラスタペア間の距離は３−ＤのＲＧＢ空間におけるクラスタの重心間の距離である。第１および第２の画像における支配的な色の各ペア間の距離を、この例では同じ画像のクラスタを含めて計算する。距離の測定値が最も小さい支配的な色のペアを選択する。
【００４０】
次に、その２つの支配的な色に対応するクラスタをマージする。
【００４１】
この例では図３に示すように、最も近い２つのクラスタはクラスタ１および３であり、これらを以下のようにマージする。
【００４２】
マージしたクラスタの支配的または代表的な色の値は２つのクラスタの支配的な色の加重平均であり、ここで重みは上記で定義した通りである。したがって、２つの支配的な色ｍ１、ｍ２とそれぞれの重みＷ１およびＷ２について、マージした支配的な色ｍは次の値を有する。
ｍ＝ｗ１ｍ１＋ｗ２ｍ２
ここで、ｗ１、ｗ２は相対的な重みであり、それぞれＷ１／Ｗ１＋Ｗ２およびＷ２／Ｗ１＋Ｗ２である。
【００４３】
マージした２つのクラスタの分散を用いて、マージしたクラスタの分散も計算する。この例では、各色成分を個別に扱い、マージしたクラスタの分散は２つのガウス分布の加重平均であると仮定する。この結果、マージしたクラスタの分散について次式が得られる。
σ２＝ｗ１σ１２＋ｗ２σ２２＋ｗ１ｗ２（ｍ１−ｍ２）２
ここで、σ１２、σ２２は成分クラスタの分散であり、ｍ１、ｍ２はそれらの平均であり、ｗ１、ｗ２は上記で定義したような相対的な重みである。
【００４４】
マージしたクラスタの重みＷはＷ１＋Ｗ２である。
【００４５】
マージしたクラスタは新たなクラスタとして扱い、重み、平均および分散は上記で説明した通りである。
【００４６】
これは図４に示されており、クラスタ１および３はマージされて新たなクラスタ６を形成している。
【００４７】
次にマージするステップをもう１度反復する。１度目の反復でマージした２つのクラスタ１および３はさらなる検討から除外し、図４に示すようにマージしたクラスタ６に置き換える。
【００４８】
次に、上記で略述したように、マージしたクラスタ６を含めて色空間において最も近いクラスタペアを特定しそれらをマージすることによって、マージするステップを繰り返す。
【００４９】
この例において、２度目の反復では、クラスタ２および４が最も近いクラスタペアである。これらをマージして新たなクラスタ７を作成し、クラスタ２および４の支配的な色、重みおよび分散から、上に記載したように支配的な色、重みおよび分散を導出する。図５に示すようにマージしたクラスタ７でクラスタ２および４を置き換える。
【００５０】
所定の条件を満たすまでマージの反復を繰り返す。例えば所定の条件として、残るクラスタ数の合計（第１および第２の画像における、マージされたクラスタと残っている元のクラスタの合計）が所定数になるまでマージを続けることとすることができる。あるいは所定の条件は、残りのクラスタの各ペア間の距離が所定の値よりも大きくなるまでマージを続けることとすることができる。あるいは本方法は所定回数の反復を含んでもよい。所定の条件のうち２つ以上を組み合わせてもよい。
【００５１】
この例では、所定数（３つ）のクラスタが残るまでマージを繰り返す。
【００５２】
上記の例では、マージしたクラスタをさらなる反復において検討する。しかしながら、マージしたクラスタはさらなる反復から除外してもよい。また上記の例において、クラスタを同一画像内の他のクラスタとマージすることもできるが、別法においてクラスタは、１回目の反復および／または任意の以後の反復において別の画像に現れるクラスタのみとマージしてもよい。これにより距離の測定回数が減る。
【００５３】
クラスタに関して説明したが、マージは、記述子すなわち支配的な色、分散および重みの値に対して行い、必ずしもクラスタ自体を解析する必要はないことが理解される。
【００５４】
反復が終了したら、残っているクラスタを用いてグループ記述子を形成する。より具体的には、最終的なクラスタの各々について、代表的または支配的な色、それぞれの分散、およびそれぞれの重みがある。これらを、最終的なクラスタ数を示す次数ｍとともに結合してグループ記述子を形成する。このグループ記述子は、色空間、または表現に用いられる色量子化の指示のような他の因子を含んでいてもよい。グループ記述子はＧｏＦＧｏＰの支配的な色記述子である。
【００５５】
上記の例では、画像グループには２枚の画像しかない。しかしながら本方法は、３枚以上の画像を含むグループにも適用することができる。上記のようにグループ中の各画像のクラスタ記述子を全て結合してスーパー記述子を形成することもできる。あるいは、画像グループをサブグループ、例えば連続するかまたは連続しない２枚組または３枚組のグループに結合して、サブグループの記述子を同様の方法で結合してもよい。
【００５６】
１つのグループに多数の画像がある場合、上記の方法は多数のクラスタならびに多数のクラスタ間距離の計算を伴う可能性がある。
【００５７】
上記に鑑みて、上記方法の変形は、ビデオショットまたはコレクション中の画像のほとんどは非常に類似しており、対応する記述子も類似するという事実を考慮する。これはほとんどのクラスタが、精度をそれほど損なうことなくフレーム毎にマージできることを意味する。
【００５８】
より詳細には、この変形は、画像グループの画像を連続して考慮する。上述の例のように、画像記述子は既に導出されて記述子データベースに格納されている。画像グループの第１および第２の画像のクラスタ記述子を取り出す。次に、画像ペアの各クラスタ間の距離を求める。クラスタペア間の距離が所定の閾値未満となるものがあれば、そのクラスタペアをマージする。画像ペアのマージしたクラスタと任意の残りのクラスタを上記で説明したようにスーパー記述子に集める。次に、次の画像のクラスタ記述子を取り出し、同様にして最初の２枚の画像のスーパー記述子とマージする。すなわち、近いクラスタをマージして新たなスーパー記述子を形成する。全ての画像のクラスタ記述子を検討したら、結果として得られるスーパー記述子を、最初の例に記載したように全ての残りのクラスタを用いてマージする。
【００５９】
上記説明では、クラスタ記述子は既に導出していた。別法として、画像を取り出すかまたは供給し、クラスタをマージする前に画像から記述子を導出してもよい。
【００６０】
上述の第１の実施形態において、ＧｏＦＧｏＰの記述子は、グループ中の各画像の記述子を集約することによって導出する。
【００６１】
第２の実施形態では、画像を画像または画素ドメインにおいて集約し、次に集約した画像から支配的な色記述子を導出してＧｏＦＧｏＰの支配的な色記述子を作成する。したがって図６に示すように、グループ中にＮ枚のｍ×ｍの画素を含む画像８がある場合、スーパー画像９は（Ｎ×ｍ）×ｍの画素配列とみなすことができる。
【００６２】
第１の実施形態と対照的に、第２の実施形態は各画像の画像記述子を用いず、画像を直接操作する。
【００６３】
画像を集約した後、第１の実施形態に関して上述した技法を用いてスーパー画像から支配的な色記述子を導出する。
【００６４】
第２の実施形態の利点は、抽出プロセスの精度が落ちないことである。しかしながら、全ての画像を検討する際には大量の複雑性、特にメモリが必要となる可能性がある。この複雑性の問題を克服するために、画像を時間的かつ／または空間的にサブサンプリングしてもよい。
【００６５】
上記において、画像を画像または画素ドメインで集約し、次に集約した画像から支配的な色記述子を導出してＧｏＦＧｏＰの支配的な色記述子を作成する。あるいは、各画像を色ドメインにおいて（例えば各画像のヒストグラムの形態で）集約し、集約したヒストグラムから支配的な色記述子を導出することもできる。例えば、各画像のカラーヒストグラムは導出するか、メモリから取り出すことができる。次に、カラーヒストグラム同士を加算することにより結合し、スーパー画像のヒストグラムを形成する。このヒストグラムは、スーパー画像を形成する画像の数により正規化することができる。最後に、第１の実施形態に関して上述した技法を用いて、スーパー画像のヒストグラムから支配的な色記述子を導出する。言い換えれば、スーパー画像のヒストグラムのピーク（支配的な色）、ならびにそれぞれの分散および重みを選択する。
【００６６】
支配的な色記述子を導出する前に画像を集約するための他の技法を用いてもよい。例えば、各画像のヒストグラム同士を加算する代わりに、画像グループの平均、中央値または共通集合を計算してもよい。次に結果として得られた平均、中央値または共通集合ヒストグラムから支配的な色のグループ記述子を導出する。
【００６７】
画像／画素ドメインおよび色／ヒストグラムドメインにおける集約に当てはまる第２の実施形態の変形では、後述のように画像グループを時間的にサブサンプリングしてもよい。この例において、各画像のクラスタ記述子を導出するかまたは取り出す。ＧｏＦＧｏＰ記述子を導出する際にグループ中のどの画像を用いるかをクラスタ記述子の類似度に基づいて決定する。
【００６８】
画像グループのシーケンスの１番目の画像が最初のスーパー画像を形成する。それ以後の画像は、ある画像とスーパー画像（最初は１番目の画像）に加えた最後の画像とのクラスタ記述子間の類似度が所定の決定条件を満たすまで廃棄する。ある画像がこの条件を満たす場合、これをスーパー画像に加える。次に、所定の条件が再び満たされるまでグループ中のそれ以後の画像をスーパー画像に加えた最後の画像と比較することを同様に行い、グループ中の全画像を検討し終えるまで続ける。次に結果として得られたスーパー画像から支配的な色記述子を導出する。
【００６９】
画像の類似度の１つの可能な決定基準は、本発明者らの同時係属中の出願ＷＯ００／６７２０３に記載されるような、それぞれの支配的な色記述子間のマッチング関数の値であるか、あるいは上記のＭＰＥＧ−７の本に記載されるようなマッチング関数を用いる。別の基準は、上述の「オンライン」マージの結果とすることもできる。この場合の「決定基準」は、全てのクラスタが既存の記述子にマージされた場合に満たされる。全ての画像について支配的な色を抽出することを避ける別の手法は、粗なカラーヒストグラムを計算し、ヒストグラムマッチング関数の値を基準として用いることであろう。
【００７０】
これらの基準は両方とも、さらなるパラメータ（第１の場合にはそれ未満ではマッチング関数の値が小さいとみなされる閾値、第２の場合にはマージ閾値）を指定することを必要とする。メモリに制限がある場合に特に当てはまる代替的な手法は、閾値を採用して、集めた画像数が指定された限界を超えないようにすることであろう。
【００７１】
第３の実施形態は、画像グループの支配的な色記述子のグループからＧｏＦＧｏＰの支配的な色記述子を導出する。より具体的には、画像グループについて、それぞれの支配的な色記述子を記述子データベースから取り出す（既に導出されていない場合には導出する）。
【００７２】
支配的な各色記述子について、その記述子とグループの残りの記述子それぞれの間の距離を測定する。この結果、各記述子について距離測定値のセットが生じ、これらを加算して各記述子の全体的な距離測定値を得る。全体的な距離測定値が最も小さい記述子を代表的な記述子として選択し、ＧｏＦＧｏＰの支配的な色記述子として扱う。
【００７３】
代表的な記述子を選択する、好ましくはグループ中の画像の画像記述子の少なくとも一部に関するテストまたは比較を伴う他の方法を用いることもできる。別の例として、これは、記述子全体について行った場合、ＭＰＥＧ−７において規定されるような歪尺度に基づいて行ってもよい。
【００７４】
非常に近い記述子を事前に拒絶して計算を減らすことも可能である。
【００７５】
上記ではＧｏＦＧｏＰ記述子、特にＧｏＦＧｏＰの支配的な色記述子を導出するための様々な方法を記載した。
【００７６】
ＧｏＦＧｏＰ記述子には、画像グループの探索および取り出しにおけるような様々な用途がある。例えばユーザは、入力画像または画像グループに対応する画像グループを探索したい場合がある。
【００７７】
探索方法の概要を以下に記載する。
【００７８】
図１を参照すると、ユーザが、スキャナやデジタルカメラのような適切な手段を用いて、あるいはコンピュータが表示する様々な画像から問い合わせ画像を選択することによって、あるいは任意のそのような画像の領域を選択することによって問い合わせ画像を入力する。上述のように画像の支配的な色記述子を導出する。次に問い合わせの支配的な色記述子を、記述子データベースに格納されたＧｏＦＧｏＰの支配的な色記述子の各々と比較する。ＧｏＦＧｏＰの支配的な色記述子は１枚の画像の支配的な色記述子と同じ形式であるので、マッチングは例えば、ＷＯ００／６７２０３に記載されるようなマッチング関数またはそれと同様のもの、あるいは上記のＭＰＥＧ−７の本の第１３．３．２節に記載されるようなマッチング関数を用いて行うことができる。問い合わせ記述子は任意選択で、データベースに格納されている可能性のある１枚の画像の記述子と比較してもよい。
【００７９】
マッチング関数の結果を順番に並べて、マッチング関数が最も近い一致を示す画像グループを取り出す。最も近い一致の１つまたは複数の画像を表示してもよい。
【００８０】
問い合わせを行う他の方法を用いることもできる。問い合わせは、画像グループを選択し、そのグループについて上述のようなＧｏＦＧｏＰ記述子を抽出することによって行うことができる。このグループは、例えばフレームの範囲を選択することによって明示的に、あるいは例えばビデオ中のキーフレームを選択することによって暗示的に選択することができ、この場合は適切なアルゴリズムを用いてキーフレームを含む「ショット」を導出する。
【００８１】
本発明によるシステムは例えば、画像ライブラリ内に設けることができる。別法では、そのデータベースは、システムの制御ユニットから遠隔に配置されており、電話線のような一時的なリンクによって、あるいはインターネットのようなネットワークによって制御ユニットに接続される場合がある。画像および記述子データベースは例えば、永久記憶装置内に、あるいはＣＤ−ＲＯＭまたはＤＶＤのようなポータブルデータ記憶媒体上に設けられる場合がある。
【００８２】
本発明の１実施形態として上述したシステムはコンピュータシステムの形態である。このコンピュータシステムは、本発明の１実施形態による方法を実行する適切なプログラムを用いてプログラムされている標準的なコンピュータであってよい。プログラムは、固定または永久記憶装置または取り外し可能な記憶手段を含む任意の適切な記憶媒体に格納されることができる。システムは、例えば特定のチップを含む特定のハードウェアおよび／またはソフトウェアを用いて変更することができる。本発明は、特定のハードウェアおよび／またはソフトウェアを含む特別に適応させた装置において実施することもできる。
【００８３】
上記の説明では、色表現を赤、緑および青の色成分に関して説明した。当然ながら、色相、彩度および明度、またはＹＵＶ座標系、あるいは任意の色空間における色成分のサブセット、例えばＨＳＩの色相と彩度のみを用いた表現等の他の表現を用いることもできる。
【００８４】
上述した本発明の実施形態は、画像および画像グループについて導出した記述子を用いる。しかしながら、画像記述子は画像の領域に関するものであってもよく、ＧｏＦＧｏＰ記述子も同様に画像の領域に基づくものであってよい。領域は長方形のブロックであるか、あるいは異なる形状およびサイズの領域を用いることもできる。別法では、記述子は、オブジェクト、例えば車、家または人に対応する画像の領域について導出してもよい。いずれの場合にも、記述子は画像の全てあるいはその一部のみについて導出される場合がある。また、画像領域グループを形成する画像中の複数の領域に上記方法を適用することによって、ＧｏＦＧｏＰグループ記述子を１枚の画像について導出することもできる。
【００８５】
探索手順では、ユーザは単純な色の問い合わせを入力するかまたは画像ブロックを選択する代わりに、例えばポインティングデバイスを用いて、例えば画像のある領域を囲むことによりその領域を記述することができ、すると制御ユニットは、その領域の記述子を導出して、それを上述と同様の方法で探索に用いる。また、探索を開始するために画像データベースに既に格納されている画像を用いる代わりに、例えば、画像スキャナまたはデジタルカメラを用いて画像をシステムに入力することもできる。そのような状況で探索を行うために、ここでもシステムがまず、画像または画像領域の記述子を自動的に、あるいはユーザが決定した通りに導出する。
【００８６】
本発明の適切な態様はハードウェアまたはソフトウェアを用いて実施することができる。
【００８７】
上記の実施形態では、代表的な各色のクラスタ分布をガウス関数を用いて近似し、それらの関数の平均、分散および共分散を記述子の値に用いた。しかしながら他の関数またはパラメータを用いて、例えば正弦または余弦のような基底関数を用い、これらの関数に基づく記述子を用いて、成分の分布を近似することもできる。
【符号の説明】
【００８８】
１〜７ クラスタ、８（１）〜８（ｎ） 画像、９ スーパー画像、１２ 制御ユニット、１４ 表示ユニット、１６ ポインティングデバイス、１８ 画像データベース、２０ 記述子データベース、２２ サーチエンジン。
【特許請求の範囲】
【請求項１】
画像グループについて、１つまたは複数の支配的な色の値を求めることと、
前記画像グループを、１つまたは複数の前記支配的な色の値に関して表す、支配的な色表現を導出することと
を含み、
前記画像グループ中の画像の少なくともいくつかが、前記画像の１つまたは複数の支配的な色の値に関して、それぞれの支配的な色表現で表され、
前記支配的な色表現の各々は、１つまたは複数の成分を有し、
前記１つまたは複数の成分は、
少なくとも１つの支配的な色の値を含み、
さらに任意選択的に、支配的な各色の値に関して、
前記支配的な色の値に対する、前記画像の色分布の分散を示す分散と、
前記画像中の前記支配的な色の影響を示す重みと、
前記画像中の支配的な色の数と、
前記画像中の前記支配的な色に対応する画素の空間均一性と
を含み、
前記方法は、前記支配的な色表現のうち複数を結合すること、または、前記支配的な色表現のうちの１つを前記グループの代表として選択することを含み、
前記支配的な色の値、分散および重みの１つまたは複数が結合される
画像グループの表現方法。
【請求項２】
色空間における支配的な色の近接度を基に、前記表現の１つまたは複数の成分を結合することを含む、請求項１に記載の画像グループの表現方法。
【請求項３】
前記結合することは、前記支配的な色の値、分散および重みの加重平均を計算することを含む、請求項１に記載の画像グループの表現方法。
【請求項４】
第１段階において、前記支配的な色それぞれの間の距離が所定の閾値未満であるといった、所定の条件を満たす成分を結合することと、
第２段階において、他の成分を結合することと
を含む、請求項２に記載の画像グループの表現方法。
【請求項５】
複数の画像を画像／画素または色空間／ヒストグラムドメインにおいて結合すること、または、前記画像グループのうちの１枚の画像を前記グループの代表として選択することと、
前記結合または選択された画像中の、１つまたは複数の支配的な色の値を求めることであって、それによって、前記画像グループの支配的な色表現を、前記結合または選択された画像の１つまたは複数の支配的な色の値に関して導出する、求めることと
を含む、請求項１に記載の画像グループの表現方法。
【請求項６】
前記支配的な色表現は、
１つまたは複数の成分であって、
前記結合または選択した画像の少なくとも１つの支配的な色の値を含み、
さらに任意選択的に、支配的な各色の値に関して、
前記支配的な色の値に対する色分布の分散を示す分散と、
前記結合または選択した画像中の、前記支配的な色の影響を示す重みと、
前記支配的な色の数と、
前記結合または選択した画像中の、前記支配的な色に対応する画素の空間均一性とを含む、１つまたは複数の成分
を有する、請求項５に記載の画像グループの表現方法。
【請求項７】
前記画像を結合するステップは、複数の画像の総和、平均、中央値または共通集合を計算することを含む、請求項５に記載の画像グループの表現方法。
【請求項８】
前記画像グループを、時間的または空間的にサブサンプリングすることを含む、請求項１に記載の画像グループの表現方法。
【請求項９】
画像が、前記グループ中の他の画像に対する類似度に応じて除外または包含される、請求項８に記載の画像グループの表現方法。
【請求項１０】
前記サブサンプリングすることは、請求項４の各ステップを含む、請求項８に記載の画像グループの表現方法。
【請求項１１】
前記代表的な画像または支配的な色表現の選択は、前記グループ中の少なくとも１つの他の画像または表現を含む、比較またはテストを含む、請求項１に記載の画像グループの表現方法。
【請求項１２】
前記グループ中の、または前記グループに関する、全ての他の画像または全ての他の表現に最も近い画像または表現が選択される、請求項１１に記載の画像グループの表現方法。
【請求項１３】
請求項１に記載の方法によって導出される、画像グループの記述子。
【請求項１４】
マッチング手順を用いて、問い合わせの支配的な色記述子を、請求項１３に記載の複数の記述子と比較することと、
前記マッチング手順が最も近い一致を示す１つまたは複数の画像グループを選択することと
を含む、画像グループの探索方法。
【請求項１５】
請求項１に記載の方法を用いて、問い合わせの支配的な色記述子を導出することと、
前記問い合わせの支配的な色記述子を、請求項１に記載の方法を用いて導出された他の記述子のそれぞれと比較することと
を含む、請求項１４に記載の方法。
【請求項１６】
請求項１または１４に記載の方法を実行する手段を備える装置。
【請求項１７】
請求項１または１４に記載の方法を実施するための、コンピュータが実行可能な処理ステップを格納するコンピュータ読み取り可能な記憶媒体。
【請求項１８】
請求項１または１４に記載の方法に従って動作するようにプログラムされたコンピュータシステム。
【請求項１９】
画像グループの表現方法。
【請求項１】
画像グループについて、１つまたは複数の支配的な色の値を求めることと、
前記画像グループを、１つまたは複数の前記支配的な色の値に関して表す、支配的な色表現を導出することと
を含み、
前記画像グループ中の画像の少なくともいくつかが、前記画像の１つまたは複数の支配的な色の値に関して、それぞれの支配的な色表現で表され、
前記支配的な色表現の各々は、１つまたは複数の成分を有し、
前記１つまたは複数の成分は、
少なくとも１つの支配的な色の値を含み、
さらに任意選択的に、支配的な各色の値に関して、
前記支配的な色の値に対する、前記画像の色分布の分散を示す分散と、
前記画像中の前記支配的な色の影響を示す重みと、
前記画像中の支配的な色の数と、
前記画像中の前記支配的な色に対応する画素の空間均一性と
を含み、
前記方法は、前記支配的な色表現のうち複数を結合すること、または、前記支配的な色表現のうちの１つを前記グループの代表として選択することを含み、
前記支配的な色の値、分散および重みの１つまたは複数が結合される
画像グループの表現方法。
【請求項２】
色空間における支配的な色の近接度を基に、前記表現の１つまたは複数の成分を結合することを含む、請求項１に記載の画像グループの表現方法。
【請求項３】
前記結合することは、前記支配的な色の値、分散および重みの加重平均を計算することを含む、請求項１に記載の画像グループの表現方法。
【請求項４】
第１段階において、前記支配的な色それぞれの間の距離が所定の閾値未満であるといった、所定の条件を満たす成分を結合することと、
第２段階において、他の成分を結合することと
を含む、請求項２に記載の画像グループの表現方法。
【請求項５】
複数の画像を画像／画素または色空間／ヒストグラムドメインにおいて結合すること、または、前記画像グループのうちの１枚の画像を前記グループの代表として選択することと、
前記結合または選択された画像中の、１つまたは複数の支配的な色の値を求めることであって、それによって、前記画像グループの支配的な色表現を、前記結合または選択された画像の１つまたは複数の支配的な色の値に関して導出する、求めることと
を含む、請求項１に記載の画像グループの表現方法。
【請求項６】
前記支配的な色表現は、
１つまたは複数の成分であって、
前記結合または選択した画像の少なくとも１つの支配的な色の値を含み、
さらに任意選択的に、支配的な各色の値に関して、
前記支配的な色の値に対する色分布の分散を示す分散と、
前記結合または選択した画像中の、前記支配的な色の影響を示す重みと、
前記支配的な色の数と、
前記結合または選択した画像中の、前記支配的な色に対応する画素の空間均一性とを含む、１つまたは複数の成分
を有する、請求項５に記載の画像グループの表現方法。
【請求項７】
前記画像を結合するステップは、複数の画像の総和、平均、中央値または共通集合を計算することを含む、請求項５に記載の画像グループの表現方法。
【請求項８】
前記画像グループを、時間的または空間的にサブサンプリングすることを含む、請求項１に記載の画像グループの表現方法。
【請求項９】
画像が、前記グループ中の他の画像に対する類似度に応じて除外または包含される、請求項８に記載の画像グループの表現方法。
【請求項１０】
前記サブサンプリングすることは、請求項４の各ステップを含む、請求項８に記載の画像グループの表現方法。
【請求項１１】
前記代表的な画像または支配的な色表現の選択は、前記グループ中の少なくとも１つの他の画像または表現を含む、比較またはテストを含む、請求項１に記載の画像グループの表現方法。
【請求項１２】
前記グループ中の、または前記グループに関する、全ての他の画像または全ての他の表現に最も近い画像または表現が選択される、請求項１１に記載の画像グループの表現方法。
【請求項１３】
請求項１に記載の方法によって導出される、画像グループの記述子。
【請求項１４】
マッチング手順を用いて、問い合わせの支配的な色記述子を、請求項１３に記載の複数の記述子と比較することと、
前記マッチング手順が最も近い一致を示す１つまたは複数の画像グループを選択することと
を含む、画像グループの探索方法。
【請求項１５】
請求項１に記載の方法を用いて、問い合わせの支配的な色記述子を導出することと、
前記問い合わせの支配的な色記述子を、請求項１に記載の方法を用いて導出された他の記述子のそれぞれと比較することと
を含む、請求項１４に記載の方法。
【請求項１６】
請求項１または１４に記載の方法を実行する手段を備える装置。
【請求項１７】
請求項１または１４に記載の方法を実施するための、コンピュータが実行可能な処理ステップを格納するコンピュータ読み取り可能な記憶媒体。
【請求項１８】
請求項１または１４に記載の方法に従って動作するようにプログラムされたコンピュータシステム。
【請求項１９】
画像グループの表現方法。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−２２５１７２（Ｐ２０１０−２２５１７２Ａ）
【公開日】平成２２年１０月７日（２０１０．１０．７）
【国際特許分類】
【出願番号】特願２０１０−１３１０９２（Ｐ２０１０−１３１０９２）
【出願日】平成２２年６月８日（２０１０．６．８）
【分割の表示】特願２００４−１９８４０３（Ｐ２００４−１９８４０３）の分割
【原出願日】平成１６年７月５日（２００４．７．５）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
【公開日】平成２２年１０月７日（２０１０．１０．７）
【国際特許分類】
【出願日】平成２２年６月８日（２０１０．６．８）
【分割の表示】特願２００４−１９８４０３（Ｐ２００４−１９８４０３）の分割
【原出願日】平成１６年７月５日（２００４．７．５）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
[ Back to top ]