(57)【要約】負例は画像内容検索におけるユーザのニーズをよく理解するために非常に有用な場合があるが、これは、何名かの著者により考察されている。本発明による画像内容検索法では、より効率的な画像検索を実行するために正例と負例との組合せに関係するいくつかの課題に取り組んでいる。明細書では、正例を使用して一般化を実行し、負例を使用して特殊化を実行する関連フィードバック方式について説明している。この方式では、正例と負例の両方を含むクエリが２つの一般的なステップで処理される。第１の一般的なステップでは、正例のみを考慮して、検索に関与する画像の集合をより均質な部分集合に還元する。次に、第２の一般的なステップでは、正例と負例の両方を考慮し、第１のステップで保持されている画像に働きかける。数学的には、関連フィードバックは正例および負例の内分散および間分散の最適化として定式化される。
2005535952.tif 000002
【特許請求の範囲】
【請求項１】
データベースファイルの集合からデータファイルを検索する内容検索法であって、
データファイルの正例および負例を用意し、前記正例は少なくとも１つの関連特徴を含むことと、
前記正例および負例のうちの少なくとも１つの例の中の少なくとも１つの弁別特徴を与え、前記正例と負例とを区別できるようにすることと、
データベースファイルの前記集合の中のデータベースファイル毎に、前記各データベースファイルと前記少なくとも１つの関連特徴を考慮した前記正例との類似性に基づき関連性スコアを計算することと、
データベースファイルの前記集合の中で類似性スコアが最高であるNb1個のファイルを含む関連ファイルのリストを作成し、前記Nb1は所定の数であることと、
関連ファイルの前記リスト内の関連ファイル毎に、前記各関連ファイルと前記少なくとも１つの弁別特徴を考慮した前記正例との類似性、および前記各関連ファイルと前記少なくとも１つの弁別特徴を考慮した前記負例との非類似性に基づき弁別スコアを計算することと、
関連ファイルの前記リストの中の弁別スコアが最高であるNb2個のファイルを選択し、前記Nb2は所定の数であることと
を含むことを特徴とする内容検索法。
【請求項２】
データベース画像の集合の中から画像を検索する内容検索法であって、
正例および負例の画像を用意し、前記正例画像は少なくとも１つの関連特徴を含むことと、
前記正例および負例のうちの少なくとも１つの例の中の少なくとも１つの弁別特徴を与え、前記正例画像と負例画像とを区別できるようにすることと、
データベース画像の前記集合の中のデータベース画像毎に、前記各データベース画像と前記少なくとも１つの関連特徴を考慮した前記正例画像との類似性に基づき関連性スコアを計算することと、
データベース画像の前記集合の中で関連性スコアが最高であるNb1個の画像を含む関連画像のリストを作成し、前記Nb1は所定の数であることと、
関連画像の前記リスト内の関連画像毎に、前記各関連画像と前記少なくとも１つの弁別特徴を考慮した前記正例画像との類似性、および前記各関連画像と前記少なくとも１つの弁別特徴を考慮した前記負例画像との非類似性に基づき弁別スコアを計算することと、
関連画像の前記リストの中の弁別スコアが最高であるNb2個の画像を選択し、前記Nb2は所定の数であることと
を含むことを特徴とする内容検索法。
【請求項３】
前記正例および負例のうち前記少なくとも１つは、複数の画像の重み付き平均であることを特徴とする請求項２に記載の方法。
【請求項４】
前記少なくとも１つの関連特徴は、数Iの関連特徴を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記正例画像は、各関連特徴Iに対するN1個の正例の重み付き平均
【数１】
2005535952.tif 000092
であることを特徴とする請求項４に記載の方法。
【請求項６】
【数２】
2005535952.tif 000093
は、以下の式により定義され、
【数３】
2005535952.tif 000094
πn1は前記正例nに対する関連度であることを特徴とする請求項５に記載の方法。
【請求項７】
前記少なくとも１つの弁別特徴は、数Iの弁別特徴を含み、前記負例画像は各関連特徴iに対するN2個の負例の重み付き平均
【数４】
2005535952.tif 000095
であり、
【数５】
2005535952.tif 000096
は、
【数６】
2005535952.tif 000097
により定義され、πn2は前記負例nに対する関連度であることを特徴とする請求項６に記載の方法。
【請求項８】
【数７】
2005535952.tif 000098
であり、ただし、
【数８】
2005535952.tif 000099
であることを特徴とする請求項７に記載の方法。
【請求項９】
【数９】
2005535952.tif 000100
および
【数１０】
2005535952.tif 000101
であることを特徴とする請求項８に記載の方法。
【請求項１０】
データベース画像、正例画像、負例画像の前記集合のそれぞれは、画像特徴の集合により表されることを特徴とする請求項２に記載の方法。
【請求項１１】
画像特徴の前記集合のそれぞれは、特徴ベクトルにより表されることを特徴とする請求項３に記載の方法。
【請求項１２】
関連性スコアを計算することは、前記正例画像と前記それぞれのデータベース画像との間の距離を計算することを含み、前記最高関連性スコアは、前記正例画像と前記それぞれのデータベース画像との間の前記距離のうちの最小の距離に対応することを特徴とする請求項１１に記載の方法。
【請求項１３】
前記少なくとも１つの関連特徴は、数Iの関連特徴を含み、前記正例画像は各関連特徴iに対するN1個の正例の重み付き平均
【数１１】
2005535952.tif 000102
であり、
【数１２】
2005535952.tif 000103
は、以下の式により定義され、
【数１３】
2005535952.tif 000104
πn1は前記正例nに対する関連度であり、
前記正例画像と特徴ベクトル
【数１４】
2005535952.tif 000105
により表される前記それぞれのデータベース画像との間の前記距離は、以下の式により定義され、
【数１５】
2005535952.tif 000106
uiは、前記i番目の特徴に割り当てられた前記大域的重みであり、Wiは、前記少なくとも１つの関連特徴のそれぞれの一般化された楕円距離Dおよび重み付き成分を定義することができる対称行列であり、uiおよびWiは、正例画像の分散Jpositive
【数１６】
2005535952.tif 000107
を最小にすることを特徴とする請求項１２に記載の方法。
【請求項１４】
弁別スコアを計算することは、前記負例画像と前記それぞれのデータベース画像との間の距離を計算することを含み、前記最高弁別スコアは、前記負例画像と前記それぞれのデータベース画像との間の前記距離のうちの最小の距離に対応することを特徴とする請求項１２に記載の方法。
【請求項１５】
前記少なくとも１つの関連特徴は、数Iの関連特徴を含み、前記正例画像は各関連特徴iに対するN1個の正例の重み付き平均
【数１７】
2005535952.tif 000108
であり、
【数１８】
2005535952.tif 000109
は、以下の式で定義され、
【数１９】
2005535952.tif 000110
πn1は前記正例nに対する関連度であり、
前記負例画像は各関連特徴iに対するN2個の負例の重み付き平均
【数２０】
2005535952.tif 000111
であり、
【数２１】
2005535952.tif 000112
は、以下の式により定義され、
【数２２】
2005535952.tif 000113
πn2は前記負例nに対する関連度であり、
前記正例画像と特徴ベクトル
【数２３】
2005535952.tif 000114
により表される前記それぞれのデータベース画像との間の前記距離から、前記負例画像と以下の式により定義される特徴ベクトル
【数２４】
2005535952.tif 000115
により表される前記それぞれのデータベース画像との前記距離を引く計算をし、
【数２５】
2005535952.tif 000116
uiは、前記i番目の関連特徴に割り当てられた前記大域的重みであり、Wiは、前記一般化された楕円距離Dを定義するために使用できる対称行列であり、uiおよびWiは、正例画像の内分散を最小にし、負例画像の内分散を最小にし、正例と負例との弁別を最大にすることを特徴とする請求項１４に記載の方法。
【請求項１６】
正例画像の前記内分散を最小にし、前記負例画像の前記内分散を最小にし、前記正例と前記負例との前記弁別を最大にすることは、
【数２６】
2005535952.tif 000117
としてA/Rを最小にすることにより実現され、
ただし、正例に対してはk=1、負例に対してはk=2であり、
【数２７】
2005535952.tif 000118
は、i番目の特徴に対するすべての正例および負例画像の重み付き平均であり、
【数２８】
2005535952.tif 000119
により定義されることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記正例および負例画像は、サンプル画像のリストの中から人手により選択されることを特徴とする請求項２に記載の方法。
【請求項１８】
データベースファイルの集合からデータファイルを検索する内容検索法であって、
データファイルの正例および負例を用意し、前記正例画像は少なくとも１つの関連特徴を含むことと、
データベースファイルの前記集合を前記複数のデータベースファイルの中から選択されたファイルの部分集合に制約し、ファイルの前記部分集合内の各ファイルは、前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて選択されることと、
前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて、また前記正例と負例との間の少なくとも１つの弁別特徴に基づく前記負例との非類似性に応じて、ファイルの前記部分集合内のファイルを検索し、それによって、前記データベースファイルの中から検索された前記ファイルは、前記正例とは類似性を持つが、前記負例とは非類似性を持つファイルに対応することと
を含むことを特徴とする内容検索法。
【請求項１９】
データベース画像の集合の中から画像を検索する内容検索法であって、
正例および負例の画像を用意し、前記正例画像は少なくとも１つの関連特徴を含むことと、
データベース画像の前記集合を前記複数のデータベース画像の中から選択された画像の部分集合に制約し、画像の前記部分集合内の各画像は、前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて選択されることと、
前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて、また前記正例と負例との間の少なくとも１つの弁別特徴に基づく前記負例との非類似性に応じて、画像の前記部分集合内の画像を検索し、それによって、前記データベース画像の中から検索された前記画像は、前記正例とは類似性を持つが、前記負例とは非類似性を持つ画像に対応することと
を含むことを特徴とする内容検索法。
【請求項２０】
データベース画像の集合の中から画像を検索する内容検索システムであって、
正例および負例の画像を用意する手段であって、前記正例画像は少なくとも１つの関連特徴を含む手段と、
前記正例および負例のうちの少なくとも１つの例の中の少なくとも１つの弁別特徴を与え、前記正例画像と負例画像とを区別できるようにする手段と、
データベース画像の前記集合の中のデータベース画像毎に、前記各データベース画像と前記少なくとも１つの関連特徴を考慮した前記正例画像との類似性に基づき関連性スコアを計算する手段と、
データベース画像の前記集合の中で類似性スコアが最高であるNb1個の画像を含む関連画像のリストを作成する手段であって、前記Nb1は所定の数である手段と、
関連画像の前記リスト内の関連画像毎に、前記各関連画像と前記少なくとも１つの弁別特徴を考慮した前記正例画像との類似性、および前記各関連画像と前記少なくとも１つの弁別特徴を考慮した前記負例画像との非類似性に基づき弁別スコアを計算する手段と、
関連画像の前記リストの中の弁別スコアが最高である前記Nb2個の画像を選択する手段であって、前記Nb2は所定の数である手段と
を備えることを特徴とする内容検索システム。
【請求項２１】
正例画像および負例画像を用意する前記手段は、サンプル画像を表示するグラフィカルユーザインターフェースを含むことを特徴とする請求項２０に記載のシステム。
【請求項２２】
前記グラフィカルユーザインターフェースは、それぞれの前記サンプル画像の関連度を指定するための手段を備えることを特徴とする請求項２０に記載のシステム。
【請求項２３】
前記グラフィカルユーザインターフェースは、前記検索された画像を表示するための手段を備えることを特徴とする請求項２２に記載のシステム。
【請求項２４】
データベース画像の集合の中から画像を検索する装置であって、
正例画像および負例画像を受け取るように適合されているインターフェースであって、前記正例画像は少なくとも１つの関連特徴を含むインターフェースと、
データベース画像の前記集合を前記複数のデータベース画像の中から選択された画像の部分集合に制約する動作が可能な制約コンポーネントであって、画像の前記部分集合内の前記画像は、前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて選択される制約コンポーネントと、
前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて、また前記正例と負例との間の少なくとも１つの弁別特徴に基づく前記負例との非類似性に応じて、画像の前記部分集合内の画像を検索する動作が可能な検索コンポーネントとを備え、
それによって、前記データベース画像の中から検索された前記画像は、前記正例とは類似性を持つが、前記負例とは非類似性を持つ画像に対応することを特徴とする装置。
【請求項２５】
前記制約コンポーネントおよび検索コンポーネントは、同じロジックデバイス内に実装されることを特徴とする請求項２４に記載の装置。
【請求項２６】
データベース画像の集合の中から画像を検索する画像内容検索ロジックを含むコンピュータ可読メモリであって、前記画像内容検索ロジックは、
正例画像および負例画像を受け取る動作が可能な画像受け入れロジックであって、前記正例画像は少なくとも１つの関連特徴を含むロジックと、
データベース画像の前記集合を前記複数のデータベース画像の中から選択された画像の部分集合に制約する動作が可能な制約ロジックであって、画像の前記部分集合内の前記画像は、前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて選択される制約ロジックと、
前記少なくとも１つの関連特徴に基づく前記正例との類似性に応じて、また前記正例と負例との間の少なくとも１つの弁別特徴に基づく前記負例との非類似性に応じて、画像の前記部分集合内の画像を検索する動作が可能な検索ロジックとを含み、
それによって、前記データベース画像の中から検索された前記画像は、前記正例とは類似性を持つが、前記負例とは非類似性を持つ画像に対応することを特徴とするコンピュータ可読メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータ検索に関する。より具体的には、本発明は、画像内容検索に関する。
【背景技術】
【０００２】
コンピュータ技術の進歩およびワールドワイドウェブの出現に伴い、デジタルデータが生成され、格納され、伝送され、分析され、アクセスされる量およびそれらのデータの複雑さが爆発的に増した。これらのデータは、テキスト、音声、画像、およびビデオなど様々な形態をとる。
【０００３】
例えば、利用可能なデジタル画像が増えてきたため、効率よく画像検索を行い、ユーザが妥当な時間内に必要な画像を見つけ出すのを手助けできるシステムの開発が必要になっている。これらの検索システムの一部では、色の特定の組合せの存在または特定の種類のイベントの描写などの画像の属性を使用している。このような属性は、画像の内容または周囲のテキストおよびデータから引き出すことができる。これにより、内容検索手法およびテキスト検索手法などの画像検索の様々な方式が導かれる。
【０００４】
いずれの場合も、画像検索システムが与えられたクエリの結果を返した場合に、ノイズとミスという２つの問題が発生することがよくある。ノイズは、ユーザが欲している画像に対応しない画像がシステムによって検索された場合に生じる。ミスとは、ユーザが欲している画像に対応する、検索されなかった画像の集まりのことである。これら２つの問題は、異なるレベルの欠陥に由来する。実際、それらの画像のいずれもがユーザの欲する画像に対応していないため、またはユーザが画像の特徴を明確に指示する際の画像内容に関する十分な知識を欠いているため、ユーザが利用可能な画像を使用して適切なクエリを定式化することは容易でない場合がある。また、ユーザのニーズおよび特異性を画像の特徴および類似性尺度に関して翻訳することが困難であることがわかっている。
【０００５】
より具体的には、画像内容検索の場合、クエリを定式化する数多くの方法を区別することができる。非特許文献１で説明されている、QBICなどの初期の頃のシステムは、ユーザ側で色、形、またはテクスチャなどの画像特徴を選択するよう求める。非特許文献２で説明されているBLOBWORLDなどの他のシステムでは、ユーザ側で特徴の組合せに対し重み付けを行う必要がある。
【０００６】
しかし、このような画像内容検索手法の欠点として、いくつかの理由から、特定のクエリに必要な特徴を直接指定することが一般的には困難であるという点が挙げられる。このような理由のうち第１のものは、すべてのユーザが与えられたクエリを定式化するために必要な画像に関する用語(例えば、コントラスト、テクスチャ、色)を理解しているわけではないことである。第２の理由は、ユーザがたとえ画像のスペシャリストであるとしても、自分が考えている画像を特徴の組合せに翻訳するのは容易なことではないということである。
【０００７】
他の方法として、「例示照会」として当業で知られているビジュアルインターフェースを暗黙のうちに介してユーザに特徴およびその対応する重みを指定させる方法がある。このプロセスを介して、ユーザは、クエリに関与する画像を選択し、探している画像との類似度に応じて重み付けすることができる。その後、より関連性のある画像を指定することによりクエリの結果を繰り返し精密化してゆくことができる。このプロセスは、当業では「関連フィードバック」(RF)と呼ばれ、非特許文献３において、すでに検索されているドキュメントの関連性に関するユーザによってフィードバックされた情報を使用して既存のクエリを自動調整するプロセスとして定義されている。
【０００８】
関連フィードバックは、複数の段階にわけてユーザ主観をモデル化するために使用される。まず、これは、ユーザの主観的な心の中にある理想的画像を識別するために適用できる。検索の各ステップで、ユーザは、クエリに関与する画像の集合を選択し、それぞれに関連度を割り当てるよう求められる。この情報は、ユーザが意図するクエリを表す分析方法を定義するために様々な方法で使用することができる。その後、理想的クエリを、非特許文献４で開示されているように、前回クエリとは無関係に定義することができる。これは、さらに、理想的クエリポイントが正例（positive example）に向かって進み、負例（negative example）から遠ざかる「クエリポイント移動法」の場合のように、前回クエリにも依存することがある。この最後の方法は、非特許文献５で説明されている。
【０００９】
また、関連フィードバックを使用すると、重要度(例えば、重み)をそれぞれの特徴に割り当てるか、または元の特徴空間をユーザのニーズおよび特異性に最もよく対応する新しい特徴空間に変換することにより、ユーザのニーズをうまくすくい取ることができる。そうするために、関連性のある画像の検索に役立つ特徴の重要度を強め、役立たない特徴の重要度を低くする。それぞれの特徴の重要度が決定された後、それらの結果を適用し、特定の現在クエリでユーザ意図する類似性にうまく対応する類似性尺度を定義する。
【００１０】
さらに、重みを特徴に属性として割り当てる操作を適用し、冗長な特徴または予測情報を殆どまたは全くもたらさない特徴を排除することにより特徴の部分集合を選択するプロセスとして、非特許文献６で定義されている特徴選択を実行することができる。実際、それぞれの特徴の重要度が決定された後に、十分重要である特徴のみを残すことにより特徴選択を実行することができ、その残りは排除される。いくつかの特徴を排除することにより、検索効率を高めることができるが、それは、低次元の特徴空間では、適切な類似性尺度を定義し、妥当な時間内に検索を実行し、効果的なインデキシング手法を適用することが比較的容易だからである(詳細については、非特許文献７を参照のこと)。
【００１１】
正例を使用する関連フィードバックは、当業では非常によく知られている。例えば、Ishikawaらは、画像同士を比較する二次形式の距離関数を定義している。Tは行列の転置を表すものとする、それぞれの画像がI次元特徴ベクトル
【００１２】
【数１】
2005535952.tif 000003
【００１３】
で表される、N個の画像からなるクエリを考え、さらにユーザがクエリに関与するそれぞれの画像に、探索される画像の類似度を表す関連度πnを関連付けるものと考えて、Ishikawaらは、２つパラメータ、つまり、クエリ画像と理想的クエリ式との間の大域的距離を表す、式(1)で与えられる量Dを最小にする、理想的クエリ
【００１４】
【数２】
2005535952.tif 000004
【００１５】
および楕円距離行列Wを計算している。
【００１６】
【数３】
2005535952.tif 000005
【００１７】
Ishikawaらによって提案されている方法の欠点は、負例をサポートしないという点である。
【００１８】
非特許文献８では、各画像は、実数ベクトルによりそれぞれ表される/特徴の集合に分解される方法を開示している。
【００１９】
【数４】
2005535952.tif 000006
【００２０】
は、n番目のクエリ画像のi番目の特徴ベクトルを表し、πnは、ユーザによってn番目の画像に割り当てられている関連度を表す。また、クエリはN個の画像からなると仮定されている。それぞれの特徴iについて、理想的クエリベクトル
【００２１】
【数５】
2005535952.tif 000007
【００２２】
、行列Wi、および式(2)で与えられるクエリ画像の大域的分散を最小にするスカラー重みuiが計算される。クエリ画像の分散を最小にするのは、集中している特徴、つまり、画像例同士が近い関係にある特徴を強めることが目的である。
【００２３】
【数６】
2005535952.tif 000008
【００２４】
非特許文献９で、Ruiら(3)は、負例画像に割り当てられている負の関連度を用いること以外は同様のモデルを使用することを提案している。このモデルの欠点は、負例の関連特徴を無視することになり、負例は正例と混同されるという点である。
【００２５】
多くの研究が関連フィードバックでのユーザインタラクションから学習する方法に重点的に取り組んでいた一方で、負例の関連性を喚起した研究はわずかしかなかったことに留意されたい。しかし、負例は、これを利用することでユーザは欲しない画像を決定し捨てることができるため、クエリの精密化に有用な場合がある。実際、Mullerらは、非特許文献１０で、正フィードバックのみを使用することにより、最初のフィードバックステップでのみ主要な改善を果たし、しかも、結果が連続的に改善されて行く正と負のフィードバックによる4つの最初のステップについて改善は顕著であることを示している。
【００２６】
負例を使用する関連フィードバックも、ノイズ(検索された望まれていない画像)を減らし、ミス(検索されなかった望まれている画像)を減らすためにも有用と考えられる。実際、与えられてクエリの結果が得られた後、ユーザは、正例画像を保持し、いくつかの望まれていない画像を負例として取り込むことによりクエリを充実させることができる。これは、負例の画像に似た画像は捨てられ、したがってノイズが減ることを意味する。それと同時に、捨てられた画像は、ユーザが欲しているものとさらによく似ているはずの他の画像で置き換えられる。したがって、ミスも減少する。さらに、ユーザは、最近検索した画像の中から、ユーザが必要とする画像に似た画像をさらに見つけ出して、新規クエリを定式化するためにそれらの画像を使用することができる。したがって、負例の使用は、ページゼロ問題と呼ばれる問題、つまり、検索を開始するためのよいクエリ画像を見つけるという問題を解決するのに役立つことであろう。ページゼロ問題を緩和すると、検索時間が短縮され、結果の精度も改善されることがわかっている(非特許文献７を参照)。また、負例を伴う関連フィードバックは、ユーザフィードバッククエリに対する応答として、システムが前回反復の場合とまったく同じ画像を返すときに有用であることにも留意されたい。ユーザがすでにシステムに対し可能なすべての正フィードバックを送っていると仮定すると、この状況から逃れる唯一の方法は、いくつかの画像を負フィードバックとして選択することである。
【００２７】
負例を伴う画像内容検索法の結果の解釈を考察すると、モデルの２つのカテゴリを区別できる。第１のカテゴリでは、正例画像はユーザによって選択されるが、負例画像は、ユーザによって選択されなかった画像の中から検索システムにより自動的に選択される。第２のカテゴリでは、正例画像と負例画像の両方がユーザによって選択される。
【００２８】
Mullerらは、この第１のカテゴリから画像内容検索法を説明している。初期クエリに関しては、非選択画像を負例として自動的に供給することにより充実させることを提案している。精密化のため、前回クエリの結果正例として得られた上位20の画像が選択される。負例としては、返却されない画像のうち4つが選択される。Muller法では、数回のフィードバックステップで精密化を行い、それぞれのステップでは、理想的クエリを正例へと進め、負例からは遠ざけることを目指す。より具体的には、これは、非特許文献１１で提案されている以下の公式を使って得られる。
【００２９】
【数７】
2005535952.tif 000009
【００３０】
ただし、Qは理想的クエリであり、n1およびn2は、それぞれクエリ内の正と負の画像の個数であり、RiおよびSiは、それぞれ正と負の画像の特徴であり、αおよびβは、正例と負例の相対的重み付けを決定する。一部のテキスト検索システムで使用される値α=0.65およびβ=0.35が使用される(Mullerらを参照のこと)。
【００３１】
システムでは自動的に負例画像を選択するので、第１のカテゴリからのシステムの欠点は、不適切な画像を使用した場合にクエリが破壊される可能性があるという点である。実際、システムが、正例としてむしろみなすべきいくつかの画像を負例として選択した場合、それらの画像の関連特徴は捨てられ、検索プロセスを誤らせることになる。
【００３２】
非特許文献１２では、第２のカテゴリからの負例を伴う画像内容検索法を開示している。より具体的には、画像検索にベイズモデルを提案しているということであり、これはデータベースが多数の画像クラスで構成されているという仮定に基づいて動作する。検索を実行すると、高いメンバーシップ確率を正例画像に割り当てる画像クラスはサポートされ、高いメンバーシップ確率を負例に割り当てる画像クラスはペナルティが課される。著者らは、正例および負例が同じ相対的重要度を持つと考えていることに留意されたい。Vasconcelosにより提案されている方法およびシステムの欠点は、選択のどのような種類の特徴重み付けをも実行しないという点である。実際、特徴の重要度は、ユーザ毎に、さらには同じユーザであってもその瞬間毎に異なるということはよく知られている。しかし、このシステムでは、すべての特徴が同じ重要度を持つとみなしている。
【００３３】
Picardらは非特許文献１３および非特許文献１４で、正例に類似した画像の集合を検索してから、負例に類似した画像の集合を検索し、最後にそれら２つの集合を操作してユーザに返すべき画像の集合を取得することを伴う方法を提案している。
【００３４】
より具体的には、Picardらは、データベース画像を色およびテクスチャなどの個別の特徴に応じて多数の階層木に編成する方法を教示している。ユーザがクエリをサブミットすると、各木を使用した比較が実行され、その結果として得られた集合が組み合わされるのであるが、そのために、最も効率よく正例を記述する画像集合を、それらの画像集合が負例もうまく記述しているというようなことはないという条件の下で、選択する。
【００３５】
Belkinらは、非特許文献１５で、負例に関係があろうとなかろうと正例の関連特徴は適切であると仮定するベイズ確率モデルを使用している。負例に対する解釈は、正例が出現する文脈は検索者の問題には不適切であるというものである。正例の関連特徴の(正の)重みを(負例内での出現に関係なく)高くし、正例内に出現しない負例の関連特徴を(負の重みで)強めることを提案している。
【００３６】
Belkinらは、負例を特徴レベルで考察している。同時に正例に似ているが、負例には似ていない画像を検索するのに役立つ特徴を識別し、強めようと試みている。しかし、負例にも出現する正例の重要な特徴を強めることで、後述のように、検索プロセスは誤った方向に進むことになる。
【００３７】
最終的に、Nastarらは、非特許文献１６および非特許文献１７で、ユーザが正例を選択する関連画像とユーザが負例を選択する非関連画像とで構成される画像データベースを考察している。確率モデルは、関連画像の分布を推定し、同時に、非関連画像の検索確率を最小にするために使用される。このようなモデルの欠点は、負例に対するその解釈、および負例画像と非関連画像との混同にある。現実のデータベースでは、ほとんどの画像は、一般に、与えられたクエリに無関係であるが、そのうちいくつかが、このクエリを破壊することなく負例として使用できる。
【００３８】
【非特許文献１】Flickerら「Query by image and video content.The QBIC system」、IEEE Computer Magazine、28:23〜32、1995年
【非特許文献２】Carsonら「A system for region-based image indexing and retrieval」、International Conference on Visual Information Systems、Amsterdam、1999年、509〜516頁
【非特許文献３】Ruiら「Content-based image retrieval with relevance feedback in MARS」IEEE International Conference on Image Processing、Santa Barbara、California、1997年、815〜818頁
【非特許文献４】Ishikawaら「Mindreader:Query databases through multiple examples」24th International Conference on Very Large Data Bases、New York、1998年、433〜438頁
【非特許文献５】Zhangら「Relevance Feedback in Content-Based Image Search」12th International Conference on New Information Technology (NIT) in Beijing、2001年5月
【非特許文献６】Kimら「Feature Selection in Unsupervised Learning via Evolutionary Search」6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-00)、San Diego、2000年、365〜369頁
【非特許文献７】Kherfiら「Web Image Search Engines:A Survey.Technical Report N°276」Universite de Sherbrooke、Canada、2001年12月
【非特許文献８】Ruiら(2)「Optimizing Learning in Image Retrieval」IEEE International Conference On Computer Vision and Pattern Recognition、Hilton Head、Sc、USA、2000年
【非特許文献９】Ruiら(3)「Efficient Indexing,Browsing and Retrieval of Image/Video Content」PhD thesis、Department of Computer Science、University of Illinois at Urbana-Champaign、1999年
【非特許文献１０】Mullerら「Strategies for Positive and Negative Relevance Feedback in Image Retrieval」Technical Report N° 00.01、Computer Vision Group、Computing Center、University of Geneva、2000年
【非特許文献１１】Rocchio「Relevance Feedback in Information Retrieval」SMART Retrieval System、Experiments in Automatic Document Processing、New Jersey、1971年、323〜323頁
【非特許文献１２】Vasconcelosら「Learning from User Feedback in Image Retrieval Systems」Neural Information Processing Systems 12、Denver、Colorado、1999年
【非特許文献１３】Picardら「Interactive Learning Using a Society of Models」IEEE Conference on Computer Vision and Pattern Recognition、San Francisco、1996年、447〜452頁
【非特許文献１４】Picardら「Modeling user subjectivity in image libraries」Technical Report No.382、MIT Media Lab Perceptual Computing、1996年
【非特許文献１５】Belkinら「Rutgers' TREC-6 interactive track experience」、6th Text Retrieval Conference、Gaitherburg、USA、1998年、597〜610頁
【非特許文献１６】Nastarら「Relevance Feedback and Category Search in Image Databases」IEEE International Conference on Multimedia Computing and Systems、Florence、Italy、1999年、512〜517頁
【非特許文献１７】Nastarら「Efficient Query Refinement for Image Retrieval」IEEE Conference on Computer Vision and Pattern Recognition、Santa Barbara、1998年、547〜552頁
【非特許文献１８】J.Li、J.Z.WangならびにG.Wiederhold「IRM:Integrated region matching for image retrieval」2000 ACM Multimedia Conference、San Jose、USA、2000年、147〜156頁
【非特許文献１９】J.Li、J.Z.WangならびにG.Wiederhold「SIMPLIcity:Semantics-sensitive Integrated Matching for Picture Libraries」IEEE Transactions on Pattern Analysis and Machine Intelligence、23 (9):947--963、2001年
【非特許文献２０】John R.Smith「Image Retrieval Evaluation」IEEE Workshop on Content-based Access of Image and Video Libraries、1998年
【非特許文献２１】Huangら「Image Indexing using Color Correlogram」IEEE Conference on Computer Vision and Pattern Recognition、1997年
【発明の開示】
【発明が解決しようとする課題】
【００３９】
そこで、本発明の目的は、正例と負例とを使用して画像内容検索機能を改善することである。
【課題を解決するための手段】
【００４０】
本発明によりデータベースファイルの集合からデータファイルを検索する内容検索法は、一般的に、ユーザが正例画像、負例画像、およびそれぞれの関連度を選択できる検索シナリオを定義することを目指している。これにより、まず、正例に基づいてデータセットの異種混合の不均一を低減し、その後、負例に基づいて結果を精密化することができる。
【００４１】
より具体的には、本発明の第１の態様により実現される、データファイルの集合からデータファイルを検索する内容検索法は、データファイルの正例および負例を用意することと、正例は少なくとも１つの関連特徴を含むことと、正例および負例のうちの少なくとも１つの例の中の少なくとも１つの弁別特徴を与え、正例と負例とを区別できるようにすることと、データベースファイルの集合の中のデータベースファイル毎に、各データベースファイルと少なくとも１つの関連特徴を考慮した正例との類似性に基づき関連性スコアを計算することと、データベースファイルの集合の中で類似性スコアが最高であるNb1個のファイルを含む関連ファイルのリストを作成することと、Nb1は所定の数であることと、関連ファイルのリスト内の関連ファイル毎に、各関連ファイルと少なくとも１つの弁別特徴を考慮した正例との類似性および各関連ファイルと少なくとも１つの識別特徴を考慮した負例との非類似性に基づき弁別スコアを計算することと、関連ファイルのリストの中の弁別スコアが最高であるNb2個のファイルを選択することと、Nb2は所定の数であることとを含む。
【００４２】
本発明の第２の態様により実現される、データベース画像の集合から画像を検索する内容検索法は、正例および負例の画像を用意することと、正例画像は少なくとも１つの関連特徴を含むことと、正例および負例のうちの少なくとも１つの例の中の少なくとも１つの弁別特徴を与え、正例画像と負例画像とを区別できるようにすることと、データベース画像の集合の中のデータベース画像毎に、各データベース画像と少なくとも１つの関連特徴を考慮した正例画像との類似性に基づき関連性スコアを計算することと、データベース画像の集合の中で関連性スコアが最高であるNb1個のファイルを含む関連画像のリストを作成することと、Nb1は所定の数であることと、関連画像のリスト内の関連画像毎に、各関連画像と少なくとも１つの弁別特徴を考慮した正例画像との類似性および各関連画像と少なくとも１つの識別特徴を考慮した負例画像との非類似性に基づき弁別スコアを計算することと、関連画像のリストの中の弁別スコアが最高であるNb2個の画像を選択することと、Nb2は所定の数であることとを含む。
【００４３】
本発明の第３の態様により実現される、データベース画像の集合から画像を検索する内容検索法は、正例および負例の画像を用意することと、正例画像は少なくとも１つの関連特徴を含むことと、データベース画像の集合を複数のデータベース画像の中から選択された画像の部分集合に制約することと、画像の部分集合内の画像は、少なくとも１つの関連特徴に基づく正例との類似性に応じて選択されることと、少なくとも１つの関連特徴に基づく正例との類似性に応じて、また正例と負例との間の少なくとも１つの弁別特徴に基づく負例との非類似性に応じて、画像の部分集合内の画像を検索することと、それによって、データベース画像の中から検索された画像は、正例とは類似性を持つが、負例とは非類似性を持つ画像に対応することとを含む。
【００４４】
本発明による画像内容検索法を採用すれば、理想的ポイントを識別しなくてもユーザが探している内容を類似性尺度に自動的にまとめられるため、理想的クエリの計算が不要になる。
【００４５】
本発明の第４の態様により実現される、データベース画像の集合から画像を検索する内容検索システムは、正例および負例の画像を用意する手段であって、正例画像は少なくとも１つの関連特徴を含む手段と、正例および負例のうちの少なくとも１つの例の中の少なくとも１つの弁別特徴を与え、正例画像と負例画像とを区別できるようにする手段と、データベース画像の集合の中のデータベース画像毎に、各データベース画像と少なくとも１つの関連特徴を考慮した正例画像との類似性に基づき関連性スコアを計算する手段と、データベース画像の集合の中で類似性スコアが最高であるNb1個の画像を含む関連画像のリストを作成する手段であって、Nb1は所定の数である手段と、関連画像のリスト内の関連画像毎に、各関連画像と少なくとも１つの弁別特徴を考慮した正例画像との類似性および各関連画像と少なくとも１つの識別特徴を考慮した負例画像との非類似性に基づき弁別スコアを計算する手段と、関連画像のリストの中の弁別スコアが最高であるNb2個の画像を選択する手段であって、Nb2は所定の数である手段とを備える。
【００４６】
本発明の第５の態様により実現される、データベース画像の集合から画像を検索する装置は、正例画像および負例画像を受け取るように適合されているインターフェースであって、正例画像は少なくとも１つの関連特徴を含むインターフェースと、データベース画像の集合を複数のデータベース画像の中から選択された画像の部分集合に制約する動作が可能な制約コンポーネントであって、画像の部分集合内の画像は、少なくとも１つの関連特徴に基づく正例との類似性に応じて選択されるコンポーネントと、少なくとも１つの関連特徴に基づく正例との類似性に応じて、また正例と負例との間の少なくとも１つの弁別特徴に基づく負例との非類似性に応じて、画像の部分集合内の画像を検索する動作が可能な検索コンポーネントとを備え、それによって、データベース画像の中から検索された画像は、正例とは類似性を持つが、負例とは非類似性を持つ画像に対応する。
【００４７】
最後に、本発明の第６の態様により実現される、データベース画像の集合から画像を検索する画像内容検索ロジックを格納するコンピュータ可読メモリにおいて、前記画像内容検索ロジックは、正例画像および負例画像を受け取る動作が可能な画像受け入れロジックであって、正例画像は少なくとも１つの関連特徴を含む画像受け入れロジックと、データベース画像の集合を複数のデータベース画像の中から選択された画像の部分集合に制約する動作が可能な制約ロジックであって、画像の部分集合内の画像は、少なくとも１つの関連特徴に基づく正例との類似性に応じて選択される制約ロジックと、少なくとも１つの関連特徴に基づく正例との類似性に応じて、また正例と負例との間の少なくとも１つの弁別特徴に基づく負例との非類似性に応じて、画像の部分集合内の画像を検索する動作が可能な検索ロジックとを格納し、それによって、データベース画像の中から検索された画像は、正例とは類似性を持つが、負例とは非類似性を持つ画像に対応する。
【００４８】
本発明の他の目的、利点、および特徴は、付属の図面のみを参照しつつ例を挙げて取りあげた好ましい実施形態の以下の非制約的説明を読むとさらに明らかになるであろう。
【発明を実施するための最良の形態】
【００４９】
本発明による画像内容検索法は、負例を使用する関連フィードバックを伴う。この負例は、特徴の観点から考慮され、ユーザによって与えられるクエリに応じてほとんどの弁別特徴を識別するために使用される。
【００５０】
本発明による画像内容検索法では、特性規則および弁別規則を含む決定規則を使用しており、これらについて簡単に説明することにする。集合の特性規則は、この集合の元のすべてまたはほとんどにより満たされる概念を特徴付ける主張である。例えば、特定の疾病の症状は、特徴規則により要約できる。弁別規則は、目標集合の概念をデータベースのそれ以外の部分から弁別する主張である。例えば、疾病を区別するには、弁別規則により、この疾病をそれ以外の疾病から弁別する症状を要約しなければならない。
【００５１】
本発明による画像内容検索法を適用する際に、正例および負例は、弁別できる、つまり、正例または負例またはその両方に関連するが、その値は正例と負例とでは同じでない、いくつかの関連特徴を持つと仮定する。言い換えると、正例の関連特徴は、類似の値を除外した負例の関連特徴と同じであるということである。そのような場合、曖昧なクエリができる。本発明による画像内容検索法を実装するシステムは、そのような場合を棄却し、新しい関連特徴を指定するようユーザに求め、ユーザが新しい関連特徴を指定できるようにプログラムされる。
【００５２】
上述の原理を実現するために、第１に関連特徴の識別により特性規則を正例画像から抽出することができる。検索プロセスでそのような特徴に対しより大きな重要度を与え、それらを強める画像を検索しなければならない。第２に、判別規則を正例と負例との差から抽出することができる。値が正例および負例に共通ではない関連特徴は、よい弁別要因であり、したがって、より大きな重要度を与え、逆に、共通の特徴はよい弁別要因ではないため、ペナルティを課さなければならない。しかし、このようにしてこの原理を適用すると、後述のように、正例および負例のいくつかの関連特徴を無視することにより、検索プロセスを誤らせる可能性がある。
【００５３】
上述で取り上げられている問題を解消する、本発明による画像内容検索法について詳しく説明する前に、関連特徴の概念を詳細に定義にしておく。与えられた特徴は、探索対象の画像の検索に役立つ場合に関連すると考えられる。これは、２つの要因に依存する。
【００５４】
第１に、関連性はクエリに関して考えることができる。クエリに関連する特徴は、クエリ画像の大半において顕著な特徴である。考察対象の特徴は、値がクエリ画像の中に集中している特徴であり、それにより、クエリとの関連性に従って、正例と負例とを正しく弁別する。
【００５５】
第２に、特徴の関連性は、データベースに関して考えることができる。与えられた特徴の値がデータベース画像の大半についてほとんど同じである場合、この特徴は、探索される画像とそれ以外の画像とを区別できないため関連性がないと考えられ、またその逆もいえる。このことを分かりやすくするために、それぞれの画像が円形のオブジェクトを含むが、オブジェクトの色は画像毎に異なるデータベースを考える。このようなデータベースでは、形状特徴は、望まれている画像と望まれていない画像とを区別できないため、検索には引っかからないが、色特徴は検索に引っかかる。つまり、データベースが均質であることの基準となる特徴は、検索に関連しないと考えられ、データベースが異種混成であることの基準となる特徴は、関連があると考えられる。
【００５６】
以下では、値が正例と負例の両方に共通である特徴を無視した結果を分析する。実際には、これはデータベースの性質に依存する。データベースがそのような特徴に関して均質である場合、データベースには関連しないためそれらを無視しても弊害をもたらさない。他方、データベースがそれらの特徴に関して異種混成である場合、それらを無視すると、システムは多くの望まれていない画像を検索し、多くの望まれている画像をミスすることになる。
【００５７】
上述のことから、共通の特徴は、任意のクエリに対して働く解を展開するものと考えなければならない。しかし、場合によっては、与えられた時点に、単独であると考えるべき十分な共通の特徴がなく、むしろ、他の特徴と合わせて考えなければならないこともある。
【００５８】
そこで、付属の図面の図１を参照すると、本発明の第１の実施例による画像内容検索法100が例示されている。
【００５９】
一般的にいって、方法100は、
102-データベース画像の集合を用意するステップと、
104-正例および負例の画像を用意するステップと、
106-データベース画像毎に、データベース画像と関連する特徴を考慮した正例との類似性に基づき関連性スコアを計算するステップと、
108-データベース画像の集合の中で関連性スコアが最高であるNb1個の画像を含む関連画像のリストを作成するステップと、
110-正例画像と負例画像とを区別できるようにする弁別特徴を用意するステップと、
112-関連画像のリスト内の関連画像毎に、各関連画像と弁別特徴を考慮した正例画像との類似性および関連画像と弁別特徴を考慮した負例画像との非類似性に基づき弁別スコアを計算するステップと、
114-関連画像のリストの中の弁別スコアが最高であるNb2個の画像を選択するステップとを実行する。
【００６０】
本発明による画像内容検索法を２つの一般的なステップを含むものとして説明することは有益であろう。以下では、参照番号を使用して方法100のステップを参照し、式を使用してさらに一般的なステップ、つまり第１の一般的ステップと第２の一般的ステップを参照することにする。
【００６１】
第１の一般的ステップでは、正例関連特徴に従って(およびそのため、共通特徴にも従って)より均質な部分集合に制約することにより検索に関与する画像の集合の異種混成を減らすことができる。この第１の一般的なステップでは、正例の関連特徴すべてを強める。正例との類似度に応じてデータベース画像をランク付けし、その後、Nb1を所定の数として、Nb1個の最上位ランクの画像のみを保持する。
【００６２】
第１の一般的なステップで保持されている画像のみが第２の一般的なステップで実行される精密化に関与し、そこで、弁別特徴、つまり、値が正例および負例に共通でない特徴を強める。この第２の一般的なステップでは、正例との類似性および負例との非類似性に応じて候補画像をランク付けし、ユーザにNb2(Nb2<Nb1)個の最上位ランクの画像のみを返す。したがって、共通特徴が第２の一般的なステップで無視されたとしても、第１の一般的なステップで考慮されているため検索が誤ることはない。以下で詳しく提示するように、本発明の方法を実装した検索システムを使用することにより、２つのステップで負例とともにクエリを処理することが重要であることを実験的に確認した。
【００６３】
図２は、２つの手法に対する精度-範囲の曲線を比較したもので、本発明による画像内容検索に基づく２つの一般的なステップで処理される負例クエリと従来技術からの方法により独自のステップ(正例および負例の両方が考慮され、データベース内のすべての画像が検索に関与する)で処理される負例クエリとを対比している。縦座標「Precision」は、検索された画像の関連度の平均値を表し、「scope」は、検索された画像の個数である。図１から、負例を含むクエリが１ステップで考慮されている場合、検索の精度は検索画像の個数とともにたちまち減少する。
【００６４】
方法100のステップ102〜114のそれぞれについて説明する前に、いくつかの特別な場合は、重要であり、言及しておく価値があるので、提案されている画像検索法も同様に機能することを示す。これらの場合は、すべての弁別特徴が正例のみ、または負例のみから得られる場合に出現する。実際、正例の関連特徴が負例の関連特徴に、共通の値とともに厳格に含まれる場合、一般的な第１のステップで、提案されている原理を適用することにより、正例の関連特徴(共通特徴と同じである)を強め、それに似た画像を保持する。その後、第２の一般的なステップで、負例関連特徴の残りを強め、それに近い画像を捨てる。他方、負例の関連特徴が正例の関連特徴に、共通の値とともに厳格に含まれる場合、一般的な第１のステップで、提案されている原理を適用することにより、正例の関連特徴(負例の特徴を含む)を強め、正例に似た画像を保持する。その後、第２の一般的なステップで、正例に関連するが、負例には関連しない特徴のみを強め、本質的にそれらの特徴に応じて画像のランク付けをやり直す。
【００６５】
以下では、画像内容検索法100により、ユーザが負例のみを使用してクエリを構成する方法について説明する。
【００６６】
第１に、与えられたクエリについて、非関連画像の個数は、通常、関連画像の個数よりもかなり多いことに注意されたい。つまり、だれかが欲していないものがわかっても、これは、ユーザが欲しないものについての十分な情報にならないということである。例えば、ユーザが正例を与えることなく自家用車の画像を負例として与えても、いったいユーザが探している画像がビルなのか、動物なのか、人なのか、またはその他の物なのかを知ることはできない。しかしながら、負例は場合によっては単独で使用することもでき、例えば、データベースにユーザが同意している画像のほかにユーザの文化では許容できない画像、例えば、誰かの裸体画像が含まれる場合に、例えば、データベースから部分集合を排除することができる。このような場合、ユーザは、まず、それらのうち一部を負例として使用して望まれていない画像を排除し、その後、データベースの残り部分に入るか、または検索することができる。検索方法に関しては、負例のみクエリは正例クエリとして考えられる、つまり、システムは最初に、負例に似ている画像を探索する。その結果得られた画像(ユーザが捨てたいと思っている画像)が検索された場合、システムはユーザに対し、それらの画像ではなくデータベースの残り部分を返す。
【００６７】
次に方法100のステップ102〜114のそれぞれについて詳しく説明する。
【００６８】
ステップ102において、ユーザが検索したい画像を含む可能性のある画像の集合のうち、データベース画像の集合がユーザに与えられるか、またはユーザによって与えられる。
【００６９】
その後、ステップ104において、正例画像および負例画像は、ユーザと方法100を実装するシステムとの間のインタラクションを通じてやり取りされる。もちろん、特定の特徴を備える画像を探している人は、そうする代わりに、手作業で例画像を選択することもできる。その場合、選択された画像は後でデジタル化される。
【００７０】
ユーザインタラクションでは、２つの主要な目的を達成することを目指している。第１に、クエリ画像とそれぞれの関連度とを組み合わせて、ユーザが探しているものを識別し、この情報を類似性尺度で統合できるようにすることである。第２に、クエリとの関連度と提供できる弁別能力に応じてそれぞれの所定の特徴およびその構成要素に重み付けをすることである。
【００７１】
図３は、異なる主題に関係する9つのサンプル画像を表示し、異なる特徴を強調するグラフィカルインターフェースを例示している。グラフィカルインターフェースは、クエリを定式化する前にユーザがデータベースから追加画像を選択できるようにプログラムされる。画像を例画像(またはクエリ画像)として選択するには、ユーザは「Select」ボタンをクリックする。システムは、ユーザが関連度を指定するためのダイアログボックスを表示する(図４を参照のこと)。図４に例示されているユーザインターフェースにより、人は選択された例画像を特徴付けることができる。
【００７２】
選択されたそれぞれの画像について、可能な関連度は以下のとおりである。
・Very similar:正例画像に対する関連度２に対応する。
・Similar:正例画像に対する関連度１に対応する。
・Doesn't matter:画像はクエリに関与しない。
・Different:負例画像に対する関連度１に対応する。
・Very different:負例画像に対する関連度２に対応する。
【００７３】
もちろん、それぞれの画像の関連性は、おおよその適合性により特徴付けることができる。
【００７４】
関連フィードバックの定式化について詳細に説明する前に、画像モデルおよび類似性尺度の一実施例について説明する。もちろん、他の画像モデルはその代わりに使用することもできる。
【００７５】
画像を表すために、Ruiらにより提案されている階層モデルを使用する。このモデルによれば、それぞれのイメージは、クエリ内にあるものもデータベース内にあるものも、I個の特徴の集合により表され、それぞれは多数の構成要素からなる実ベクトルである。この画像モデルでは、画像と画像特徴の両方を適切にモデル化し、計算時間を短縮できることがわかっている。この階層型２レベル画像モデルに応じて、各レベルの距離計量が選択される。特徴レベルでは、Ishikawaらのように、一般化されたユークリッド距離関数が選択される、
【００７６】
【数８】
2005535952.tif 000010
【００７７】
および
【００７８】
【数９】
2005535952.tif 000011
【００７９】
がそれぞれ画像x1およびx2のi番目の特徴ベクトルである場合、この特徴レベルでの距離は以下の式で表され、
【００８０】
【数１０】
2005535952.tif 000012
【００８１】
Wiは、一般化された楕円距離計量Diを定義するために使用できる対称行列である。
【００８２】
この距離計量を選択すると、各特徴の構成要素に重み付けするだけでなく、初期特徴空間をユーザのニーズおよび特異性をうまくモデル化する空間に変換することができる。２つの画像x1およびx2の間の大域的距離は、線形であり、以下の式により与えられる。
【００８３】
【数１１】
2005535952.tif 000013
【００８４】
ただし、uiは、i番目の特徴に割り当てられた大域的重みである。
【００８５】
データベースまたはクエリに含まれるそれぞれの画像は、以下のようにして、27個の特徴ベクトルからなる集合により表される。まず、画像内のすべてのピクセルを三次元(3D)HSI空間内の一点にマッピングする(図５を参照のこと)。この操作は、すべての三つ組み[H,S,I]について、値Hue=H、Saturation=S、およびIntensity=Iを持つピクセルの個数を計算することからなる。これにより、多くの空間を占有し、その値の大半について0となっている、3Dカラーヒストグラムが得られる。例えば、HSI値が0から255の範囲である画像だと、大半がどのピクセルにも対応しない2563個のセルを含むヒストグラムが得られる。
【００８６】
ヒストグラムのサイズを低減するため、3Dヒストグラムの点の空間再配分などの多数の解決策が考えられ、その際に、それぞれの出現頻度、つまり、ヒストグラム内の各点に対応するピクセルの個数を考慮する。しかし、方法100では最良の視覚的特徴を見つけることを目的としていないので、軸H、S、およびIをそれぞれ3つの等しい間隔に再分割することにより空間を分割する際に妥協を図る。これにより、図５に示されているように、33=27の部分空間が得られる。それぞれの部分空間は１つの特徴を含み、その対応するベクトルは以下のように計算される。部分空間は、23=8個の部分空間に細分される。それぞれの部分部分空間の要素の総和を計算し、その結果を特徴ベクトルの対応するセル内に格納する。
【００８７】
それとは別に、他のモデルを使用して画像を表すこともできる。
【００８８】
ステップ106で、データベース画像毎に、画像と関連特徴を考慮した正例画像との類似性に基づき関連性スコアを計算する。
【００８９】
ユーザがN1個の正例画像およびn=1,...,N1に対するそれぞれの関連度πn1からなるクエリのほかに、N2個の負例画像およびn=1,...,N2に対するそれぞれの関連度πn2を構成することを考える。(πn2はπnの二乗ではなく、2は負例を指示するインデックスであることに留意されたい。)
【００９０】
正例のみが、ステップ106で考慮されている。それぞれの関連特徴およびその構成要素は、正例との関連性に応じて強められる。これは、式(6)で与えられている、正例の大域的分散であるJpositiveを最小にする最適なパラメータuiおよびWiを代入することにより実行することができる。
【００９１】
【数１２】
2005535952.tif 000014
【００９２】
ただし、
【００９３】
【数１３】
2005535952.tif 000015
【００９４】
は、以下の式により与えられる、正例の重み付き平均である(図６を参照のこと)。
【００９５】
【数１４】
2005535952.tif 000016
【００９６】
本発明による画像検索法では、特徴空間内で正例画像同士が近いような特徴および特徴構成要素により大きな重みを付けることができる。形式張らずにいうと、クエリ画像の分散が与えられた軸に沿って高い場合、この軸上の値はユーザに受け入れられそうであり、したがってこの軸に低い重みを付けるべきであり、またその逆もいえる、というのが理由である。
【００９７】
ステップ108で、データベース画像は、各データベース画像と関連特徴を考慮した正例画像との類似性に基づく関連性スコアに応じて昇順でランク付けされる。
【００９８】
より具体的には、正例平均およびNb1個の最上位ランクの画像からの距離を計算し、次のステップのために保持する。この距離は、式(8)により与えられる。
【００９９】
【数１５】
2005535952.tif 000017
【０１００】
クエリに負例画像のみが含まれている場合、システムは最初に類似の手順で作業を進めるが、正例ではなく負例を考慮する。これは、システムでは負例画像の分散を最小にする理想的パラメータを計算し、負例平均からの距離に応じて昇順で画像をランク付けし、その後、ユーザに最後にランク付けされた画像を返すことを意味している。クエリが正例と負例の両方を含む場合、システムは、検索の２つのステップを実行する。第１のステップで使用されるパラメータ計算および距離関数は、正例のみのクエリの場合と同じである。
【０１０１】
第２の一般的なステップでは、正例画像と負例画像の両方が考慮され、精密化は第１の一般的なステップ、より具体的にはステップ108で、保持される画像に関係する。
【０１０２】
まず、クエリの大域的分散Jglobalは、正例画像および負例画像を含み、以下の式で定義される。
【０１０３】
【数１６】
2005535952.tif 000018
【０１０４】
ただし、正例に対してはk=1、負例に対してはk=2であり、式(10)で与えられる
【０１０５】
【数１７】
2005535952.tif 000019
【０１０６】
は、i番目の特徴に対するすべてのクエリ画像の重み付き平均である(図７を参照のこと)。
【０１０７】
【数１８】
2005535952.tif 000020
【０１０８】
非特許文献８では、負の関連度を負例画像に割り当て、式(9)の同じ式を最小にするパラメータを計算することを提案している。このような方式の結果は、本発明による画像内容検索法では採用されていないが、そのような方式と方法100で使用されている方式との違いを強調するために考慮される。式(9)において正例が負例と別に考慮される場合、以下の式になる。
【０１０９】
【数１９】
2005535952.tif 000021
【０１１０】
Ruiら(2)は、n=1,...,N1についてπn1>0と選択し、n=1,...,N2についてπn2<0と選択して、以下の式を得ている。
【０１１１】
【数２０】
2005535952.tif 000022
【０１１２】
ただし、
【０１１３】
【数２１】
2005535952.tif 000023
【０１１４】
は、πn2の絶対値を表す。式(12)は、大域的分散Jglobalは正例の分散を負例の分散から引いたものであることを示している。したがって、大域的分散を最小にすることにより、Ruiら(2)の文献で大域的クエリ平均q(これを画像と比較する)を正例に向かって移動し、負例から遠ざける場合でも、２つの問題が表面化する。
【０１１５】
まず、大域的分散を最小にすると、正例の分散が最小になるが、それは正例平均
【０１１６】
【数２２】
2005535952.tif 000024
【０１１７】
よりはむしろ大域的クエリ平均qに関係している。これでは、正例分散の最適な最小化は行われず、したがって、正例の関連特徴には、十分な重要度が与えられない。
【０１１８】
第２に、大域的分散を最小にすると、負例の分散が最大になる。これは、負例の関連特徴を無視することを意味している。したがって、その検索システムは、望まれていない画像を捨てることができない。これは、図８に例示されている。
【０１１９】
重みuiおよびWiは、うまく区別できるようにする正例または負例の関連特徴により大きな重要度を与えるため代入される。つまり、uiおよびWiを介して、重みが特徴に属性として与えられ、特徴空間は正例画像同士ができる限り近く、負例画像同士はできる限り近く、そして正例と負例とはできる限り隔たる新しい空間に変換される(図７を参照のこと)。これらの目標は、まず、式(9)の大域的分散公式で正例画像を負例画像から区別することにより数式に翻訳される。特徴i毎に、正例画像の重み付き平均
【０１２０】
【数２３】
2005535952.tif 000025
【０１２１】
はリコールされ、式(13)および(14)で負例画像の重み付き平均
【０１２２】
【数２４】
2005535952.tif 000026
【０１２３】
はそれぞれ定義される。
【０１２４】
【数２５】
2005535952.tif 000027
【０１２５】
【数２６】
2005535952.tif 000028
【０１２６】
および
【０１２７】
【数２７】
2005535952.tif 000029
【０１２８】
を式(9)に代入することにより、以下のように書き換えることができる。
【０１２９】
【数２８】
2005535952.tif 000030
【０１３０】
式(15)を展開すると以下の式が得られる。
【０１３１】
【数２９】
2005535952.tif 000031
【０１３２】
式(16)の第２および第３の部分が0であることは容易に示すことができる。例えば、第２の部分は以下のようになる。
【０１３３】
【数３０】
2005535952.tif 000032
【０１３４】
式(13)および(14)により、以下のようになるからである。
【０１３５】
【数３１】
2005535952.tif 000033
【０１３６】
したがって、式(17)は、以下のように書くことができる。
【０１３７】
【数３２】
2005535952.tif 000034
【０１３８】
第１項「A」は、正例の内部分散、つまり、正例画像同士がどれだけ近いかということに、負例の内部分散、つまり、負例画像同士がどれだけ近いかということを加えたものを表す。第２項「R」は、２つの集合からの距離、つまり、正例が負例からどれだけ隔たっているかを表す。
【０１３９】
これで、分散間「R」から分散内「A」を区別することにより、上記の目標を数学的問題にどのように定式化できるかが明らかになる。実際、分散内「A」を最小にし、分散間「R」を最大にするモデルパラメータ、つまり、uiおよびWiを計算したい。AとRのいくつかの組合せが可能である。
【０１４０】
R≠0と仮定して、比A/Rを最小にするパラメータを計算する。R=0の場合は、正例および負例は区別できず、クエリはあいまいである。そのような場合、クエリは棄却され、ユーザは新しいクエリの定式化を求められる。さらに、数値安定性問題を回避するために、２つの制約条件、
【０１４１】
【数３３】
2005535952.tif 000035
【０１４２】
およびすべてのi=1,...,Iについてdet(Wi)=1が導入される。ラグランジュ乗数法を使用することにより、最適なパラメータuiおよびWiで、式(18)により与えられる量Lを最小にしなければならない。
【０１４３】
【数３４】
2005535952.tif 000036
【０１４４】
ただし、
【０１４５】
【数３５】
2005535952.tif 000037
【０１４６】
および
【０１４７】
【数３６】
2005535952.tif 000038
【０１４８】
であり、
【０１４９】
【数３７】
2005535952.tif 000039
【０１５０】
は、正例関連度の総和を表す、つまり
【０１５１】
【数３８】
2005535952.tif 000040
【０１５２】
であり、
【０１５３】
【数３９】
2005535952.tif 000041
【０１５４】
は、負例関連度の総和を表す、つまり
【０１５５】
【数４０】
2005535952.tif 000042
【０１５６】
である。
【０１５７】
そこで最適なパラメータuiおよびWiを得るための最適化問題を解決することにする。
【０１５８】
まず、正例および負例の相対的重要度を決定する、つまり
【０１５９】
【数４１】
2005535952.tif 000043
【０１６０】
に関して
【０１６１】
【数４２】
2005535952.tif 000044
【０１６２】
であることに留意されたい。Mullerらによって説明されているようないくつかの画像検索システムでは、正例については0.65、負例については0.35である、特定のテキスト検索システムにより使用されている値を採用している。Vasconcelosらによって説明されているような他のシステムでは、正例および負例は同じ重要度を持つと仮定する。方法100では、後者の選択が採用されているが、それは、問題の導出をいくつか簡素化できるからである。さらに、ユーザによって与えられるすべての関連度は、
【０１６３】
【数４３】
2005535952.tif 000045
【０１６４】
となるように正規化される。
【０１６５】
Wiに対する最適解を得るために、Hiをi番目の特徴の次元、wirsをWiのrs番目の要素、つまりWi=[wirs]としてr,s=1,...,Hiについてwirsに関するLの偏微分をとると、以下の式が得られる。
【０１６６】
【数４４】
2005535952.tif 000046
【０１６７】
ただし、
【０１６８】
【数４５】
2005535952.tif 000047
【０１６９】
および
【０１７０】
【数４６】
2005535952.tif 000048
【０１７１】
【数４７】
2005535952.tif 000049
【０１７２】
を計算する前に、
【０１７３】
【数４８】
2005535952.tif 000050
【０１７４】
であることに留意すべきであるが、ただし、det(Wirs)は、det(Wi)の第r行と第s列を取り除いて得られたWiの第rs番目の小行列式である。したがって、以下の式が得られる。
【０１７５】
【数４９】
2005535952.tif 000051
【０１７６】
式(19)、(20)、および(21)を(18)に代入して、以下の式が得られる。
【０１７７】
【数５０】
2005535952.tif 000052
【０１７８】
次に、Wiの逆行列である行列Wi-1=[wirs-1]を考える(Wiは逆行列が存在すると仮定する)。各成分wirs-1の値を求めるために、行列逆演算の行列式法を使用して以下の式を得る。
【０１７９】
【数５１】
2005535952.tif 000053
【０１８０】
det(Wi)=1であることから、以下の式が得られる。
【０１８１】
【数５２】
2005535952.tif 000054
【０１８２】
式(26)で、det(Wirs)を式(25)からの値に置き換えて以下の式を得る。
【０１８３】
【数５３】
2005535952.tif 000055
【０１８４】
ただし、
【０１８５】
【数５４】
2005535952.tif 000056
【０１８６】
式(27)は、さらに、以下のように行列形式で書くこともできる。
【０１８７】
【数５５】
2005535952.tif 000057
【０１８８】
ただし、Ciは、以下のように表される行列[cirs]である。
【０１８９】
【数５６】
2005535952.tif 000058
【０１９０】
そこで、γの値は、未知のパラメータであるλと独立に計算される。式(28)は、以下のように書くことができる。
【０１９１】
【数５７】
2005535952.tif 000059
【０１９２】
ただし、det(Wi-1)=1なので、
【０１９３】
【数５８】
2005535952.tif 000060
【０１９４】
である。最後に、Wiに対する最適解が式(30)により与えられる。
【０１９５】
【数５９】
2005535952.tif 000061
【０１９６】
ただし、Ciの成分は、式(29)により与えられる。
【０１９７】
以下では、Wiの成分に対する正例および負例の分散の影響を考察する。まず、式(29)は、以下のように行列形式に書き直すことができる。
【０１９８】
【数６０】
2005535952.tif 000062
【０１９９】
ただし、Covaiは、以下のような、i番目の特徴に対する内共分散行列の総和、つまり、
【０２００】
【数６１】
2005535952.tif 000063
【０２０１】
であり、
【０２０２】
【数６２】
2005535952.tif 000064
【０２０３】
Covriは、以下のような、i番目の特徴に対する間共分散行列、つまり、
【０２０４】
【数６３】
2005535952.tif 000065
【０２０５】
であり、
【０２０６】
【数６４】
2005535952.tif 000066
【０２０７】
次に、式(31)を考察するが、ただし、「A」および「R」の値は、すべての特徴に関係しているので設定されている。内分散が間分散に相対的に高く、したがって、Covaiの要素がCovriの要素に相対的に重要である場合、式(31)により、Ciの成分の値は重要である。しかし、Wi=γCi-1(式(30))なので、wirsの値は小さく、したがって、i番目の特徴の成分は低い重みが与えられることになる。他方、内分散がi番目の特徴の間分散に相対的に低い場合、同様の論法により、この特徴の成分は高い重みが与えられることがわかる。Wiのこの挙動により、弁別特徴を他の特徴に対して強める目的が達成される。
【０２０８】
uiに関してLの偏微分をとると、uiの最適解が求められる。
【０２０９】
【数６５】
2005535952.tif 000067
【０２１０】
ただし、
【０２１１】
【数６６】
2005535952.tif 000068
【０２１２】
および
【０２１３】
【数６７】
2005535952.tif 000069
【０２１４】
式(33)および(34)を(32)に代入して、以下の式が得られる。
【０２１５】
【数６８】
2005535952.tif 000070
【０２１６】
式(35)の両辺にuiを掛けると、以下の式が得られる。
【０２１７】
【数６９】
2005535952.tif 000071
【０２１８】
ただし、
【０２１９】
【数７０】
2005535952.tif 000072
【０２２０】
次に、未知のパラメータλを取り除くために、uiと任意のujとの間のλとは無関係の関係を探す。まずλを、以下のように式(36)から直接計算することができる。
【０２２１】
【数７１】
2005535952.tif 000073
【０２２２】
次に、式(36)の総和をiについてとると、
【０２２３】
【数７２】
2005535952.tif 000074
【０２２４】
が得られるが、
【０２２５】
【数７３】
2005535952.tif 000075
【０２２６】
なので、
【０２２７】
【数７４】
2005535952.tif 000076
【０２２８】
となる。その結果、以下のようになる。
【０２２９】
【数７５】
2005535952.tif 000077
【０２３０】
式(32)および(33)は、すべての特徴iについて、以下の式が成り立つことを意味している。
【０２３１】
【数７６】
2005535952.tif 000078
【０２３２】
式(40)からf1u12=f2u22=...=fiui2=fIuI2となる。
【０２３３】
したがって、以下の式が得られる。
【０２３４】
【数７７】
2005535952.tif 000079
【０２３５】
最後に、uiの最適解を求めるために、式(40)の中のujを式(41)からの値で置き換えて、以下の式を求める。
【０２３６】
【数７８】
2005535952.tif 000080
【０２３７】
uiの最適解は、式(42)により与えられるが、ただし、fiは、式(37)により定義される。
【０２３８】
次に、正例および負例が各uiの値に及ぼす影響について考察する。まず、式(37)でfiを以下のように書くことができる。
fi=RFai-AFri                                                            (43)
ただし、
【０２３９】
【数７９】
2005535952.tif 000081
【０２４０】
および
【０２４１】
【数８０】
2005535952.tif 000082
【０２４２】
AおよびRは、すべての特徴に依存するため定数と仮定する。i番目の特徴について、内分散が間分散に相対的に高い場合、量Faiは量Friに関して重要度が高くなる。式(43)により、これにより、fiの値が大きくなる。さらに、式(42)は、fiが増大すると、uiが減少し、したがって、i番目の特徴は低い重みが与えられることを示している。逆に、i番目の特徴について、内分散が間分散に相対的に低い場合、同様の論法により、i番目の特徴は高い重みを与えられることがわかる。したがって、uiについて見つかった最適値は、他の特徴に対して関連する弁別特徴を強めるという目的を達成する。
【０２４３】
簡単にいうと、ステップ112への入力は、正例画像、負例画像、およびそれぞれの関連度からなる。ステップ112の部分的結果は、最適なパラメータWiおよびuiを含む。これらのパラメータは、それぞれ、式(30)および(42)に従って計算される。これらのパラメータを計算するには、それぞれ式(13)、(14)、(10)、(37)、(19)、および(20)に従って
【０２４４】
【数８１】
2005535952.tif 000083
【０２４５】
、A、およびRを計算する必要がある。このアルゴリズムは、Wiおよびuiの計算がAおよびRに依存し、AおよびRの計算がWiおよびuiに依存しているため反復的である。固定小数点法を使用して、Wiとuiの計算を実行する。初期化ステップが必要であり、そこで、以下の値を採用することにする。
【０２４６】
-  Wiは対角行列で初期化される。
【０２４７】
【数８２】
2005535952.tif 000084
【０２４８】
ただし、以下の式
【０２４９】
【数８３】
2005535952.tif 000085
【０２５０】
は、クエリ画像の全集合について計算されたi番目の特徴のr番目の成分の標準偏差である。
【０２５１】
-  パラメータuiは以下の式によって与えられるある種の分散により初期化される。
【０２５２】
【数８４】
2005535952.tif 000086
【０２５３】
ただし、
【０２５４】
【数８５】
2005535952.tif 000087
【０２５５】
Wiの計算では、行列Ciの逆行列を求める必要がある。しかし、(N1+N2)<Hiの場合、Ciは逆行列を持たない。Ishikawaらは、特異値分解(SVD)による手順で擬似逆行列を求めることを提案している。しかし、この解は、満足な結果を与えず、特に、Ruiらが指摘しているように(N1+N2)がHiよりかなり小さい場合にはそうであり、Ruiらは、特異行列の場合には、Wiを要素が標準偏差の逆数になっている対角行列で置き換えること、つまりr=sならば
【０２５６】
【数８６】
2005535952.tif 000088
【０２５７】
、そうでなければwirs=0とすることを提案している。
【０２５８】
ステップ112で、Wiは、要素が行列Ciの対角要素の逆数である対角行列、つまり
【０２５９】
【数８７】
2005535952.tif 000089
【０２６０】
で置き換えられるが、ただし、
【０２６１】
【数８８】
2005535952.tif 000090
【０２６２】
およびcissは、式(26)の中でr=sと置いて得られる。
【０２６３】
ステップ114で、ステップ108により得られる関連画像は、正例への近さと負例からの遠さに基づく弁別スコアによりランク付けされる。比較関数は、式(44)により与えられる。最後に、システムは、Nb2個の最上位ランクの画像をユーザに返す。
【０２６４】
【数８９】
2005535952.tif 000091
【０２６５】
［実験結果とパフォーマンス評価］
テストは、ペンシルベニア州立大学画像データベースの10000件の画像について実施されており、これについては、J.Li、J.Z.WangならびにG.Wiederholdにより、非特許文献１８および非特許文献１９で説明されている。このデータベースは、異なる特徴を強調し、異なる照明条件の下で撮影された、異なる主題に関係する画像を含む。画像毎に、特徴の集合が上述のように計算される。検索および精密化に関してテストが何回も実施された。正例および負例が容易には区別できない場合であっても、本発明による方法は、弁別特徴を識別し、その結果得られた画像をそれらの特徴に基づいてソートすることに成功した。
【０２６６】
図９は、正例のみによる検索例を示している。図１0は、正例と負例とによる検索例を示している。
【０２６７】
第１の実施例では、２つの画像が正例としてクエリに関与している。これらの画像は両方とも、青色の空の下で緑色の木が映っている(5095.ppmおよび5118.ppm)。図９は、上位9個の返される画像を示している。この２つのクエリ画像は最上位位置に返されることに留意されたい。また、空の下の木を含む画像はほかにもいくつかあるが、青色の空の下の緑色の木に止まっている茶色の鳥の3つの画像からなるノイズを含む(5523.ppm、5522.ppm、5521.ppm)。それと同時に、データベースには検索されていない空の下の木の他の画像(図には示されていない)が生まれているためミスはなかった。
【０２６８】
第２の実施例により、精密化が第１の実施例の結果に対し適用されている。したがって、正例と同じ画像(5095.ppmおよび5118.ppm)を使用しているが、空の下の木に止まっている鳥の画像は、負例として選択されている(図８の画像5521.ppm)。図９は、鳥の画像が捨てられ(ノイズ低減)、空の下の木の画像がさらに大きく検索される(ミス低減)ことを示している。
【０２６９】
［パフォーマンス評価］
提案されている関連フィードバック手法を評価するために、本発明による方法を実装する検索システムのパフォーマンス評価が実施された。評価は、正例のみの使用と正例および負例の両方の使用の比較に基づいている。画像検索に関して評価を実行する上で、グランドトルースの取得とパフォーマンス基準の定義という２つの主要な課題が現れている。グランドトルースについては、人間の被験者が用いられた、つまり後述のすべての経験に3人が参加した。John R.Smith が非特許文献２０で説明しているPrecision Pr and Recall Reが使用された。
【０２７０】
その最も単純な定義では、Precisionは、関連する検索済み画像の割合、つまり、すべての検索された画像の数に対する関連する検索された画像の個数であり、Recallは、検索される関連画像の割合、つまり、データベース内のすべての関連画像の数に対する検索された関連画像の個数である。Smithは、精度-リコール(precision-recall)曲線Pr=f(Re)を作成したが、この尺度は、Recallが一貫して低いため、画像検索の文脈ではあまり意味がないことが観察された。さらに、多くの場合、Recallを計算することは、特に画像データベースのサイズが大きい場合には困難であると考えられるが、それは、クエリ毎に、データベース全体の中の関連画像の個数がわかっている必要があるからである。Recallに関する問題としてはほかに、ユーザに返す画像の数の選択に大きく依存するという点があげられる。データベース内の関連画像の個数がユーザに返される画像の個数よりも多い場合、リコールはペナルティを課される。非特許文献２１で説明されているように、精度-範囲曲線Pr=f(Sc)である表現により富んだ曲線が使用されている。範囲Scは、ユーザに返される画像の個数であり、したがって、曲線Pr=f(Sc)は、ユーザに返される画像の個数の異なる値に対する精度を表す。これらのパフォーマンス基準は、当業でよく知られていると考えられるため、ここではさらに詳しく説明しない。
【０２７１】
２つの経験があり、それぞれ、われわれのモデルの与えられた態様を測定することを目指している。第１の経験では、検索された画像の関連度の、負例を使った改善を測定することを目指す。第２の経験では、画像の与えられたカテゴリを特定するために必要な反復回数の、負例を使った改善を測定することを目指す。
【０２７２】
［第１の経験］
上述のように、第１の経験の目標は、検索された画像の関連度の改善に負例がどの程度寄与しているかを測定することである。経験に参加している各被験者は、正例のみを使用してクエリを定式化し、検索されたそれぞれの画像に良さのスコアを与え、その後、負例を使用してそれらの結果を精密化し、検索されたそれぞれの画像に良さのスコアを与えるよう求められた。可能なスコアは、画像が良好である場合には2、許容できる場合は1、不良である場合は0である。それぞれの被験者は、毎回新規クエリを指定することにより経験を5回繰り返した。Precisionは、Pr=検索された画像の関連度の総和/検索された画像の個数として計算された。図１1は、正例による検索と負例による精密化の２つの場合の曲線Pr=f(Sc)の比較を例示している。
【０２７３】
経験の結果、平均して、負例が導入されたときには、精度の改善は約20%であることがわかる。実際には、改善はクエリ毎に異なり、それは、意味のある負例の選択およびデータベースの構成などの他の要因に左右されるからである。与えられたクエリについて、データベースに、大半が第１のステップで検索された関連画像が少し含まれている場合、負例またはその他の手法の導入によって、顕著な改善をもたらすことはできないであろう。
【０２７４】
［第２の経験］
第２の経験では、画像の与えられたカテゴリを特定するために必要な精密化反復回数の改善だけでなく、ページゼロ問題(検索を開始する際の良好な画像を見つけること)を解消する際の負例の役割を測定することを目指す。各被験者は、色に関して互いに比較的類似している画像の集合を見せられた。示されている画像はいずれも、被験者が初期クエリを定式化するために使用できる画像の集合内に現れていない。それぞれの被験者は、示されている画像のうちの少なくとも１つを正例のみを使って特定し、反復回数を数え、その後経験を、ただし正例と負例の両方を使用してやり直し、反復回数を数えるよう求められる。この経験は、4回繰り返され、その結果は図１2に示されている。S1、S2、およびS3は、それぞれ、実験に参加した3名の被験者を表している。PEは正例を意味し、NEは負例を意味する。表内の各エントリは、探索された画像を特定するために必要な反復回数を示す。
【０２７５】
正例と負例の両方を使用した場合、被験者はすべての経験で成功しているが、正例のみを使用した場合には、被験者の一部はいくつかの経験において探索された画像の特定に失敗していることがわかった。経験2.2および経験2.4では、少なくとも一人の被験者が、正例のみを使用して探索された画像を特定することができなかった。これは、与えられた反復で、検索されたすべての画像が望まれていないカテゴリに分類され、それらの画像を使用する次の反復のクエリの定式化により、同じカテゴリに属している画像が検索されるからである。ユーザは無限ループに陥る可能性があるが、正例のみを使ってこの状況を逃れることはできない。第２の観察結果から、負例を使用すると、反復回数が目立って減ることがわかる。成功した経験(2.1および2.3)の中の平均反復回数を計算すると、正例のみが使用された場合には5.83、正例と負例の両方が使用された場合には2.33となった。この経験から、ページゼロ問題を緩和する際の負例の役割が明らかになる。実際、探索された画像の少なくとも１つを取得した後、ユーザはそれを使用して、新しいクエリを定式化することができ、そのため、さらに多くの探している画像を検索することができる。
【０２７６】
本発明による画像内容検索法では、関連フィードバックを介して識別されることができるユーザのニーズおよび特異性を考慮することができる。正例のみの使用はユーザが探しているものを突き止めるのには必ずしも十分ではないことが示された。これは、特に、クエリに関与するすべての候補画像が不適切な文脈内に現れるか、またはユーザが探している特徴に加えて、ユーザが検索したくない特徴またはオブジェクトを含む場合に見られる。
【０２７７】
本発明のモデルは、画像検索に限られず、関連フィードバックによる任意の検索プロセスに適合させ、適用することができることに留意されたい。例えば、本発明による方法は、テキスト、音声、およびマルチメディアの検索などの検索のプロセスで使用することができる。
【０２７８】
本発明は、好ましい実施形態を使用してこれまでに説明したとおりであるが、本発明の精神および性質から逸脱することなく、修正することができる。
【図面の簡単な説明】
【０２７９】
【図１】本発明の例示されている一実施形態による画像内容検索法を説明する流れ図である。
【図２】図１の方法による２つのステップにおける負例および従来技術による１ステップにおける負例の２つの場合についての精度-範囲曲線を示すグラフである。
【図３】異なる主題に関係するサンプル画像を表示し、異なる特徴を強調するグラフィカルインターフェースのコンピュータのスクリーンショットである。
【図４】図１の方法による人が例画像を特徴付けることができるユーザインターフェースからのクエリ画面のコンピュータのスクリーンショットである。
【図５】HIS色空間の部分空間の集合への分解およびそれぞれの部分空間のヒストグラムの計算を例示する概略図である。
【図６】正の平均、負の平均、およびその結果のクエリ平均総計を例示するグラフである。
【図７】負例の関連特徴を無視することになる大域的分散を最小にすることを例示しているグラフである。
【図８】「従来技術」と書かれている、正例の分散、負例の最小化、および従来技術の方法による区別の低減を例示するグラフである。
【図９】図２の方法からの結果として得られる続くステップ106を例示するスクリーンショットである。
【図１０】図２の方法からの結果として得られる続くステップ112を例示するスクリーンショットである。
【図１１】正例による検索および負例による精密化に関する精度-範囲曲線を例示するグラフである。
【図１２】図２の方法による正例のみの使用および正例と負例の両方の使用の２つの場合における画像の与えられたカテゴリを特定するために必要な反復回数を示す表である。
【図１】
2005535952.tif 000120
【図２】
2005535952.tif 000121
【図３】
2005535952.tif 000122
【図４】
2005535952.tif 000123
【図５】
2005535952.tif 000124
【図６】
2005535952.tif 000125
【図７】
2005535952.tif 000126
【図８】
2005535952.tif 000127
【図９】
2005535952.tif 000128
【図１０】
2005535952.tif 000129
【図１１】
2005535952.tif 000130
【図１２】
2005535952.tif 000131
【国際調査報告】
2005535952.tif 000132
2005535952.tif 000133