(57)【要約】  クエリキーワードにより表される指定されるビジュアルオブジェクトカテゴリに対するデータベースから抽出される画像の関連性を決定する方法であって、ビジュアルオブジェクトカテゴリの特徴とそれらの間の空間的関係を規定するモデルを学習し、データベースから抽出される画像セットと格納されているモデルとを比較し、モデルとの対応関係に基づき各画像に関する尤度値を計算することから構成される方法。
2007531136.tif 000002
【特許請求の範囲】
【請求項１】
指定されたビジュアルオブジェクトカテゴリに対するデータベースから抽出された画像セットの関連性を決定する装置であって、
ビジュアルオブジェクトカテゴリを該ビジュアルオブジェクトカテゴリの特徴と該特徴間の空間的関係とを規定するモデルに変換する手段と、
前記モデルを格納する手段と、
前記データベースの検索中に特定される画像セットと前記格納されているモデルとを比較し、前記モデルとの対応関係に基づき各画像に関する尤度値を計算する手段と、
を有することを特徴とする装置。
【請求項２】
請求項１記載の装置であって、
前記画像とモデルとを比較する手段は、前記画像の特徴を特定し、前記画像の最大尤度記述を決定するため、前記特徴のパラメータの確率密度を推定する手段を有することを特徴とする装置。
【請求項３】
請求項１又は２記載の装置であって、さらに、前記画像を各自の尤度値の順序によりランク付けする手段、及び／又は前記指定されたビジュアルオブジェクトカテゴリに対応するさらなる画像を抽出する手段を有することを特徴とする装置。
【請求項４】
請求項１乃至３何れか一項記載の装置であって、
前記特徴は、オブジェクトの少なくとも２つのタイプの部分を有することを特徴とする装置。
【請求項５】
請求項４記載の装置であって、
前記タイプは、ピクセルパッチ、カーブセグメント、コーナー及びテクスチャを含むことを特徴とする装置。
【請求項６】
請求項１乃至５何れか一項記載の装置であって、
各特徴は１以上のパラメータにより表され、
前記パラメータは、前記特徴の様相及び／又はジオメトリ、前記特徴の前記モデルに対するスケール、及び前記特徴のオクルージョン確率を含む、
ことを特徴とする装置。
【請求項７】
請求項６記載の装置であって、
前記パラメータは、確率密度関数によりモデル化されることを特徴とする装置。
【請求項８】
請求項１乃至７何れか一項記載の装置であって、
前記画像セットは、データベース検索中に取得されることを特徴とする装置。
【請求項９】
請求項１乃至８何れか一項記載の装置であって、さらに、
前記画像セットのサブセットを選択し、前記画像サブセットから前記モデルを生成する手段を有することを特徴とする装置。
【請求項１０】
請求項９記載の装置であって、
前記画像サブセットは、ユーザにより選択可能であることを特徴とする装置。
【請求項１１】
請求項１乃至８何れか一項記載の装置であって、
前記画像セットの画像の実質的にすべてが、前記モデルを生成するのに利用されることを特徴とする装置。
【請求項１２】
請求項１乃至１１何れか一項記載の装置であって、
各々が特徴タイプの１つ又は組み合わせを有する少なくとも２つのモデルが、前記画像セットに関して生成されることを特徴とする装置。
【請求項１３】
請求項１２記載の装置であって、さらに、
前記比較する手段により利用するため、前記少なくとも２つのモデルの１つを選択する手段を有することを特徴とする装置。
【請求項１４】
請求項１３記載の装置であって、
前記選択する手段は、各モデルに関する差分的ランク付け指標を計算し、最大のランク付け指標を有するモデルを選択するよう構成されることを特徴とする装置。
【請求項１５】
指定されたビジュアルオブジェクトカテゴリに対するデータベースから抽出された画像セットの関連性を決定する方法であって、
ビジュアルオブジェクトカテゴリを該ビジュアルオブジェクトカテゴリの特徴と該特徴間の空間的関係とを規定するモデルに変換するステップと、
前記モデルを格納するステップと、
前記データベースから抽出される画像セットと前記格納されているモデルとを比較し、前記モデルとの対応関係に基づき各画像に関する尤度値を計算するステップと、
を有することを特徴とする方法。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
本発明は、画像を有するデータベースからビジュアルオブジェクトカテゴリを抽出する方法及び装置に関し、より詳細には、インターネットサーチエンジンなどを利用して、ユーザによって指定されるビジュアルオブジェクトカテゴリに対応する関連する画像を検索及び抽出する改良された方法及び装置に関する。
【０００２】
単に１以上のキーワードをサーチエンジンに入力し、それに応答いて、数百及びときには数千の関連する画像がユーザによる選択のための検索結果により返される画像用のワールド・ワイド・ウェブの検索を行うことは、比較的簡単である。しかしながら、これらの結果により返される画像のすべてが必ずしも検索に特に関連しているとは限らない。実際、返される画像の多くは全く無関係である可能性もある。
【０００３】
テキストベースインターネット検索では、最も関連のある返されたアイテム（すなわち、入力されたキーワードを正確に含むもの）が特定され、他のウェブページの各ウェブページとの既存のリンク数に基づく数値に従ってランク付けされる。この結果、ユーザに最も関連する可能性のある結果が、検索結果の最初の数ページにリストされる。
【０００４】
しかしながら、画像ベース検索の場合、最も関連性のある可能性の高い結果は、検索結果の最初の数ページで返される可能性は低く、代わりに関連性のない画像と均等に混合されている可能性が高い。これは、現在のインターネット検索技術が、画像コンテンツでなく単語に基づくものであり、結果において返される画像が画像のファイル名又はウェブページ上の当該画像の近傍に出現するテキストにおいて入力されたキーワードを含み、その結果がその後にテキストベース検索を参照して上述のようにランク付けされるためである。この方法は、ワールド・ワイド・ウェブ上で利用可能な数百万のものから関連する画像を迅速に収集するのに大変効果的であるが、最終的な結果は、ユーザがその後に興味のある画像を見つけるため数十、数百又は数千もの結果エントリを検索する必要があるという意味で完全とはほど遠いものである。
【０００５】
ここで、我々は改良された構成を考案した。
【０００６】
本発明によると、指定されたビジュアルオブジェクトカテゴリに関してデータベースから抽出された画像の関連性を決定する装置であって、ビジュアルオブジェクトカテゴリを当該ビジュアルオブジェクトカテゴリの特徴とそれらの間の空間的関係を規定するモデルに変換する手段を有する装置が提供される。
【０００７】
当該モデルを格納する手段が設けられてもよい。本発明の一実施例では、データベースから抽出される画像セットを格納されているモデルと比較し、当該モデルとそれの対応関係に基づき各画像に関する尤度値を計算する手段が設けられる。さらに、各尤度値の順序により画像をランク付けし、及び／又は指定されたビジュアルオブジェクトカテゴリに対応するさらなる画像を抽出する手段が設けられてもよい。
【０００８】
また本発明によると、指定されたビジュアルオブジェクトに関してデータベースから抽出される画像の関連性を決定する方法であって、ビジュアルオブジェクトカテゴリを当該ビジュアルオブジェクトカテゴリの特徴とそれらの間の空間的関係を規定するモデルに変換するステップを有する方法が提供される。本方法はさらに、当該モデルを格納するステップを有するようにしてもよい。本発明の一実施例では、本方法はさらに、データベースから抽出される画像セットと格納されているモデルとを比較するステップと、当該モデルとのそれの対応関係に基づき各画像に関する尤度値を計算するステップとを有するかもしれない。好ましくは、本方法は、各自の尤度値の順序により画像をランク付けするステップ、及び／又は指定されたビジュアルオブジェクトカテゴリに対応するさらなる画像を検出するステップを有する。
【０００９】
何れかのイベントにおいて、この画像セットはサーチエンジンなどを利用してデータベースの検索中にデータベースから抽出されてもよいということが理解されるであろう。
【００１０】
これらの特徴は、効果的には少なくとも２つのタイプを有し、これらのカテゴリは、ピクセルパッチ（ｐｉｘｅｌ  ｐａｔｃｈ）、カーブセグメント（ｃｕｒｖｅ  ｓｅｇｍｅｎｔ）、コーナー（ｃｏｒｎｅｒ）及びテクスチャ（ｔｅｘｔｕｒｅ）を含むかもしれない。好適な実施例では、各部分は、それの様相及び／又はジオメトリ、モデルに対するそれのスケール及びそれのオクルージョン確率（ｏｃｃｌｕｓｉｏｎ  ｐｒｏｂａｂｉｌｉｔｙ）の１以上により表され、これらのパラメータは、ガウス確率関数などの確率密度関数によりモデル化されるかもしれない。
【００１１】
画像をモデルと比較するステップは、好ましくは、画像の特徴を識別し、上述した確率密度を用いて当該特徴を評価するステップを有する。
【００１２】
本方法は、データベース検索中に抽出される画像のサブセットを選択し、当該画像サブセットからモデルを生成するステップを有するかもしれない。あるいは、データベース検索中に抽出される画像の実質的にすべてが、モデルを生成するのに利用されてもよい。何れのケースでも、少なくとも２つのモデルが、他の特徴も考えられるが、データベース検索中などに抽出される画像セット、すなわち、パッチ及びカーブなどに関して生成されるかもしれない。あるいは、より好ましくは、特徴の組み合わせから構成される異質なモデルが生成されてもよい。何れのイベントでも、本方法は、好ましくは、比較のために利用されるモデルの性質又はタイプを選択するステップと、特定の画像セットに関してランク付けするステップとを有する。
【００１３】
一実施例では、選択するステップは、各モデルに関して差分的なランク付け指標を計算し、最大となる差分ランク付け指標を有するモデルを選択することにより実行されるかもしれない。
【００１４】
本発明の上記及び他の特徴は、ここで説明された実施例を参照して明らかにされる。
【００１５】
本発明は、サーチエンジンのパフォーマンスを向上させることがないとしても、画像ベースインターネット検索に関する上述の問題点が、検索により返される画像間の「ビジュアルコンシスタンシ（ｖｉｓｕａｌ  ｃｏｎｓｉｓｔｅｎｃｙ）」を測定し、当該コンシスタンシに基づきそれらを再ランク付けし、これにより、検索結果の最初の数エントリ内におけるユーザに返された関連する画像の比率を増大させることにより軽減されるかもしれない。このコンセプトは、検索要求に関する画像が典型的には視覚的に類似する一方、検索要求に関係しない画像が典型的には互いに異なっているように見えるという仮定に基づくものである。
【００１６】
「ビジュアルコンシスタンシ」の測定方法の問題は、確率的モデリング及びロウバストな統計量の１つとして本発明の以下の実施例においてアプローチされている。ここで使用されるアルゴリズムは、所望されない（非カテゴリ）画像が拒絶可能であり、又は少なくとも返された画像が当該共通性との類似性に従ってランク付け可能であるように、返された画像セットにおける共通のビジュアル要素をロウバストに学習する。より正確には、要求されたカテゴリにクラス内の変形を収容可能なビジュアルオブジェクトモデルが学習される。これは極めて困難なビジュアルタスクであるということは当業者に理解されるであろう。ライティング及び視点の変更（スケール、短縮）及び部分的オクルージョンなど、画像からの学習には視覚的困難さがあるだけでなく、オブジェクトは返された画像のサブセットに実際に存在するかもしれず、このサブセット（及びそれのサイズさえ）は知られていない。
【００１７】
図１及び図２を参照するに、本発明のこれら一例となる実施例の装置及び方法は、コンステレーションモデル（ｃｏｎｓｔｅｌｌａｔｉｏｎ  ｍｏｄｅｌ）の拡張を利用し、クラッタ（ｃｌｕｔｔｅｒ）を含む画像からオブジェクトカテゴリを学習するよう構成され、これにより、少なくとも人間による介入に対する要求を最小限にする。
【００１８】
オブジェクト又はコンステレーションモデルは、各部分がある様相を有し、オクルード可能又は不可であるオブジェクト上に空間的に構成されるいくつかの部分から構成される。このケースにおける部分とは、例えば、画像要素（ピクセル）のパッチ又はカーブセグメントであるかもしれない。何れの場合でも、部分は、それの固有の記述（様相又はジオメトリ）、モデルに対するそれのスケール及びそれのオクルージョン確率によって表される。オブジェクトの形状（又はモデル全体の形状）は、部分相互の位置により表される。モデル全体は、部分記述、スケールモデル形状及びオクルージョンが、これのケースではガウスである確率密度関数によってすべてモデル化されるという意味で、生成的及び確率的なものである。
【００１９】
オブジェクトカテゴリを学習するプロセスは、まず特徴スケールにより特徴を検出し、その後にモデルがトレーニングデータの最大尤度記述を与えるように、これらの特徴から上記密度のパラメータを推定することである。
【００２０】
この実施例では、モデルは、Ｐ個の部分から構成され、パラメータυにより特定される。位置Ｘ、スケールＳ及び記述ＤによりＮ個の検出された特徴が与えられると、画像がオブジェクトを有する尤度は、以下の式を有すると仮定される。
【００２１】
【数１】
2007531136.tif 000003
ただし、この和は部分の特徴への割当てｈ上で行われる。典型的には、モデルは５〜７の部分を有し、画像内には４０個までの特徴が存在するであろう。
【００２２】
同様に、非オブジェクトバックグラウンド画像がパラメータυｂｇによる同一形式の尤度によりモデル化することができることが仮定される。ある画像がオブジェクトを有するか否かに関する決定は、
【００２３】
【数２】
2007531136.tif 000004
の尤度レシオによって決定される。
【００２４】
適合及び認識段階の両方において、当該モデルはスケール不変である。当該モデルの完全な詳細及びＥＭアルゴリズムを利用したトレーニングデータへのそれの適合は、Ｒ．Ｆｅｒｇｕｓ，Ｐ．Ｐｅｒｏｎａ及びＡ．Ｚｉｓｓｅｒｍａｎによる“Ｏｂｊｅｃｔ  Ｃｌａｓｓ  Ｒｅｃｏｇｎｉｔｉｏｎ  ｂｙ  Ｕｎｓｕｐｅｒｖｉｓｅｄ  Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｌｅａｒｎｉｎｇ”（Ｐｒｏｃ．ＣＶＰＲ，２００３）により与えられ、実質的に同一の表現及び推定方法が、本発明の以下の実施例において使用される。
【００２５】
既存の認識アプローチは、それらからモデルが学習する画像パッチ、テクスチャ領域又はＨａｒｒウェーブレットなどの１つのタイプの特徴に基づきモデルを学習する。しかしながら、オブジェクトの異なる視覚的性質は、当該アプローチが限定的なものであることを意味する。ワインボトルなどのいくつかのオブジェクトについては、オブジェクトのエッセンスが、ピクセルのパッチではなくジオメトリック情報（すなわち、輪郭）によりはるかに良好にキャプチャされ、もちろん、人間の顔など多くのオブジェクトについてその反対も真である。この結果、フレキシブルな視覚認識システムについて、複数の特徴タイプを有する必要がある。上述したコンステレーションモデルのフレキシブルな性質は、各部分の記述密度が独立であるため、それぞれが異なるタイプの特徴を利用可能であるという事実の観点でこれを可能にする。
【００２６】
以下の説明では、図３を参照して、より多くのもの（コーナー、テクスチャなど）が容易に追加可能であるが、２つのタイプの特徴のみが考慮される。これらのタイプの第１のものはピクセルの領域から構成され、第２のものはカーブセグメントから構成される。これらのタイプの特徴は、第１のものがオブジェクトの様相を表し、他方がオブジェクトジオメトリを表すという意味で補完的であることが理解される。
【００２７】
Ｔ．Ｋａｄｉｒ及びＭ．Ｂｒａｄｙによる“Ｓｃａｌｅ，Ｓａｌｉｅｎｃｙ  ａｎｄ  Ｉｍａｇｅ  Ｄｅｓｃｒｉｐｔｉｏｎ”（ＩＪＣＶ，４５（２）：８３−１０５，２００１）により記述されるような関心オペレータが、位置とスケールの両方に対して顕著な領域を検出するのに利用されるかもしれない。それは、グレイレベルヒストグラム及び領域全体のエントロピーの指標に基づく。オペレータは、位置（円の中心）とスケール（円の半径）の両方が決定されるように、円の領域セットを検出する。オペレータは、主として画像の回転及びスケール変更に対して不変である。従って例えば、画像が２倍のサイズにされる場合、対応する領域セットが検出されるであろう（２倍のスケールにより）。
【００２８】
カーブセグメントを決定するため、エッジポイントの大変ローカルな空間構成を考慮するだけでなく、例えば、Ｊ．Ｆ．Ｃａｎｎｙによる“Ａ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｅｄｇｅ  Ｄｅｔｅｃｔｉｏｎ”（ＩＥＥＥ  ＰＡＭＩ，８（６）：６７９−６９８，１９８６）により記載されるエッジオペレータなどによって、拡張されたエッジチェーンが利用可能である。その後、このチェーンはバイタンジェントポイント（ｂｉｔａｎｇｅｎｔ  ｐｏｉｎｔ）、すなわち、ある直線が曲線と２つの接点を有する点の間のセグメントにセグメント化される。この分解は、ここでは２つの輪ようにより利用される。第１には、バイタンジェンシ（ｂｉｔａｎｇｅｎｃｙ）はプロジェクティブ（ｐｒｏｊｅｃｔｉｖｅ）な変換と共変（ｃｏｖａｒｉａｎｔ）である。これは、近傍の平面曲線について、セグメント化が視点について不変であり、同一又は類似するオブジェクトが異なるスケール及び向きによりイメージングされる場合に重要な要件となることを意味する。第２には、バイローカル（ｂｉ−ｌｏｃａｌ）性質を利用して曲線をセグメント化することによって、不完全なエッジデータではあるが、興味深いセグメントがコンシスタントに検出可能となる。Ｃ．Ｒｏｔｈｗｅｌｌ、Ａ．Ｚｉｓｓｅｒｍａｎ、Ｄ．Ｆｏｒｓｙｔｈ及びＪ．Ｍｕｎｄｙによる“Ｐｌａｎａｒ  Ｏｂｊｅｃｔ  Ｒｅｃｏｇｎｉｔｉｏｎ  Ｕｓｉｎｇ  Ｐｒｏｊｅｃｔｉｖｅ  Ｓｈａｐｅ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ”（ＩＪＣＶ，１６（２），１９９５）により記載される方法を利用して、バイタンジェントポイントが各チェーン上に検出される。バイタンジェントポイントの各ペアは、チェーンのサブセクションである曲線を規定しているため、チェーンの曲線セクションへの分解には複数のものがあるかもしれない。実際、多数のカーブセグメントが直線（ノイズに対する閾値の範囲内で）であり、これらは曲線よりもはるかに有用性が低いという点から破棄される。さらに、チェーン全体がまた利用され、これにより、凸な曲線部分が維持される。
【００２９】
従って、上述した特徴検出装置は、各画像内の関心のあるパッチ及びカーブを提供する。それらを本発明のモデルに利用するため、Ｄ＝［Ａ，Ｇ］についてそれらの性質をパラメータ化する必要がある。ただし、Ａは画像内の領域の様相であり、Ｇは画像内のカーブの形状である。
【００３０】
領域が特定されると、それらは画像からクロップ処理（ｃｒｏｐ）され、より小さなピクセルパッチに再スケーリングされる。各パッチは、所定次元のスペースに存在する。モデルの様相密度が当該スペースに存在する必要があるため、その識別力を維持しながら、各パッチの次元をどうにかして低減することが実用的な観点から必要である。これは、主成分解析（ＰＣＡ）を利用した本発明の当該実施例により達成される。学習段階では、すべての画像からのパッチが収集され、それらに対してＰＣＡが実行される。そのとき、各パッチの様相は、第１の所定の数ｋの主成分の範囲内の座標ベクトルであり、Ａを与える。これは、部分毎に適度な個数のパラメータを使用しながら、元のパッチの良好な再構成をもたらす。
【００３１】
各カーブは、それが原点からスタートし、点（１，０）でエンドとなるように、類似性変換を利用した基準位置に変換される。カーブの中心がｘ軸の下方にある場合、それはｘ軸と直線ｙ＝０．５の双方において反転し、これにより、エッジオーダリングとは独立に同一のカーブが取得される。この基準位置のカーブのｙの値は、（０，０）と（１，０）との間で等しい間隔のいくつかのｘインターバルにおいてサンプリングされる。モデルは向き不変でないため、カーブの元の向きは、各カーブのベクトルに連結され、他のベクトルが与えられる。画像内のすべてのカーブからのベクトルを合成することにより、Ｇが与えられる。
【００３２】
以下において、画像収集の一例となる実現形態と、上述のアルゴリズムを適用する際の主要なステップ（すなわち、特徴検出、モデル学習及びランク付け）が、より詳細に説明される。
【００３３】
与えられたキーワードについて、Ｇｏｏｇｌｅ（登録商標）などのサーチエンジンを使用した画像検索が、画像セットをダウンロードするのに利用さ可能であり、ダウンロードした画像のインテグリティがチェックされる。さらに、主軸上の１００〜６００のピクセルの適度なサイズの領域外のものは破棄される。典型的な画像検索は、４５０〜７００の利用可能な画像の領域により返される可能性があり、当該処理を自動化するためのスクリプトが利用可能である。アルゴリズムを評価するため、返された画像は３つのタイプに分割することができる。
・良好な画像、すなわち、様々な視点、スケーリング及び向きが可能であるが、主要なオクルージョンを欠いたキーワードカテゴリの良好な例
・中間的な画像、すなわち、ある方法ではキーワードカテゴリに関連するが、良好な画像より品質の低い画像  それらは、拡張的なオクルージョン、実質的な画像ノイズを有するか、カテゴリの風刺又は漫画であるか、あるいは他のいくつかの欠点があるかもしれない。
・ジャンク画像、すなわち、キーワードカテゴリに全く関係しない画像
この特定のケースでは、各画像がグレイスケールに変換され（カラー情報は本発明の実施例に適用される他のモデルにおいて利用されるかもしれないが、カラー情報は上述したモデルでは使用されず、本発明はこれに関して限定されないため）、関心領域及びカーブはが画像内に識別される。これは、学習又は認識に利用されるＸ、Ｄ及びＳを生成する。各画像からの最も高い顕著性を有する所定数の領域が使用される。
【００３４】
学習プロセスは、２つの形式、すなわち、教師なし学習（図６）と限定的監視の１つをとる。供しない学習では、モデルは、データセットのすべての画像を利用して学習される。当該処理には、人間による介入は必要でない。限定的監視による学習では、関連性フィードバックを利用した他のアプローチが利用され、これにより、ユーザは求められる画像に近接したデータセットからの１０又はその程度の画像を選択し、モデルはこれら選択された画像を利用して学習される。
【００３５】
何れのアプローチでも、学習タスクは、上述したモデルのパラメータθを推定する形式をとる。その目的は、選択されたトレーニング画像（１０又はデータセット全体）からデータＸ、Ｄ及びＳを最も良く説明する、すなわち、尤度
【００３６】
【数３】
2007531136.tif 000005
を最大化するパラメータθMLを求めることである。このモデルは、上述したＲ．Ｆｅｒｇｕｓらによる参考文献によって説明されるようなＥＭアルゴリズムを利用して学習される。
【００３７】
学習モデルが与えられると、ある画像内のすべての仮説が評価され、これは当該画像の尤度レシオを決定する。その後、この尤度レシオが、データセットのすべての画像をランク付けするのに利用される。
【００３８】
各画像セットについて、様々なモデルが学習可能であり、各モデルは様々な特徴タイプ（パッチ、カーブなど）から構成され、どれがユーザに提供される最終的なランク付けを与えるべきか決定されねばならない。本発明の実施例により、これは、「ジャンク」画像（指定された視覚的オブジェクトカテゴリに全く関係のない画像）から全体的に構成される第２の画像セットを利用することにより行われる。これらは、例えば、「事物」をサーチエンジンの画像検索機能にタイプすることにより収集されるかもしれない。従って、ここではａ）ランク付けされる画像セット（ジャンク画像と良好な画像の組み合わせから構成される）と、ｂ）ジャンクデータセットの２つの画像セット又はデータセットが存在する。本発明の当該実施例によると、各モデルは、双方のデータセットから画像の尤度を評価し、差分的ランク付け指標が、例えば、２つのデータセット間のＲＯＣカーブ下のエリアを観察することによってそれらの間で計算される。最も大きな差分的ランク付け指標を与えるモデルが、ユーザに提供される最終的なランク付けを与えるのに選択される。
【００３９】
この一例となるアプローチの背後にある論拠は、以下の通りである。差分的ランク付け指標を観察することによって、双方のデータセットのジャンク画像の寄与が相殺され、良好な画像のみの指標が与えられるように、ジャンクデータセットｂ）のジャンク画像の統計量が、ランク付けされるデータセットａ）のジャンク画像のものと同一であることが仮定することが可能である。それらのランク付けが高いほど、モデルはより良好になるべきである。
【００４０】
ここで処理される状況に適合したモデルは、有効なデータ（良好な画像）だけでなく、モデルによって適合不可能な異常値（中間的な画像及びジャンク画像）を含むデータセットからモデルを学習しようとする意味で、ロウバストな統計量のエリアに直面したモデルと等価である。この結果、ロウバストな適合アルゴリズムであるＲＡＮＳＡＣが、本発明の要求に適応化されるかもしれない。モデルをトレーニングするのに十分な画像セット（このケースでは、１０）が、データベース検索中に抽出される画像からランダムにサンプリングされる。その後、このモデルは、上述した差分的ランク付け指標により残りの画像に対してスコアリングされる。このサンプリング処理は、正常値（良好な画像）から全体的に構成されるサンプルセットの良好な可能性を保証するのに十分な回数だけ繰り返される。
【００４１】
多数の関連のない画像を含む（５０％まで、そしてそれ以上）トレーニングセットからの学習が可能なあるカテゴリのモデルが示され、本発明が従来のインターネットサーチエンジンによって返されるデータセットのタイプを処理することを可能にするのはこの能力である。さらに本発明では、２つの実施例に関して上述されるように、そのアルゴリズムのみがそれの入力として画像を要求し、従って、本発明の方法及び装置は、既存の何れのサーチエンジンに関して利用可能である。さらに、本発明が関連する画像を抽出／ランク付けするためのそれの能力においてスケール不変であるということを重要な効果として有することは、当業者により理解されるであろう。
【００４２】
本発明の２つの特定の実施例が説明された。第１には、ユーザは、図１に示されるように、具体例（すなわち、関連性フィードバック又は教師付き学習のシンプルな形式）を要求する小さな割合の画像を選択するのに限られた時間（２０〜３０秒）しか費やさないよう求められ、第２には、図２に示されるように、学習におけるユーザの介入が要求されない。
【００４３】
そのアルゴリズムのスピードは、実際的に大きな重要性を有する、すなわち、ウェブ利用研究は、ユーザがウェブページがロードされるのに数秒しか待つことが許容されないことを示している。以下で与えられるタイミングは、３ＧＨｚマシーンに対するものである。
【００４４】
インターネットサーチエンジンアプリケーションの場合には、カテゴリキーワードの大きなセットが、最も共通して検索された画像カテゴリ（既存のサーチエンジンが容易に編集可能な情報）を選択することにより自動的に取得することが可能である。
【００４５】
教師なしの学習のケースでは、このカテゴリキーワードセットに対するユーザ入力が要求されないため、すべてがオフラインに予め計算可能である。従って、そのアルゴリズムに対する時間ペナルティはない。オフライン計算にはある時間がかかるかもしれないが（おそらく、ＲＡＮＳＡＣアプローチにより学習されるモデル数に応じて数日間でさえ）、それは一度実行されればよい。
【００４６】
教師付き学習のケースでは、状況はより困難である。ユーザがいくつかの画像を選択すると、複数のモデル（特徴タイプの異なる組み合わせに対応する）が学習される必要があり、その後、これらのモデルは数秒間のうちにデータセット全体（〜１０００画像）について実行される必要がある。これを可能にするため、以下の手段が行われる。
（ｉ）データセットのすべての画像から特徴をオフラインに抽出し、それらを格納する。これは、１回だけ行われればよい。
（ｉｉ）異なるモデルをパラレルに学習する。
（ｉｉｉ）データセット全体について異なるモデルをパラレルに実行する。
【００４７】
これらの手段は、スピードのボトルネックが、モデルがどの程度迅速に学習可能であるか、そしてそれが画像を評価するのにどの程度迅速に利用可能であるかに依存することを意味する。現在の最適化されていない展開形態では、処理全体に約１分を要するが、専門的なグレード符号化及び最適化により、これは数秒まで低減することが可能である。
【００４８】
再び、カテゴリキーワードの選択（上記（ｉ）について必要とされる）は、最も共通して検索されるカテゴリを選択することにより自動選択可能である。
【００４９】
上述した実施例は本発明を限定するものでなく、説明するものであり、当業者は添付した請求項により規定されるような本発明の範囲から逸脱することなく、他の多数の実施例を構成可能であるということに留意すべきである。請求項では、括弧内に置かれる参照符号は、請求項を限定するものとして解釈されるものではない。「有する」という用語は、請求項又は明細書全体に列挙された以外の要素又はステップの存在を排除するものではない。要素の単数形による表現は、そのような要素が複数存在することを排除するものでなく、その逆も然りである。本発明は、複数の要素を有するハードウェアと、適切にプログラムされたコンピュータにより実現可能である。複数の手段を列挙した装置クレームでは、これらの手段のいくつかは、１つの同一のハードウェアアイテムにより実現可能である。ある手段が互いに異なる従属クレームにより記載されているという事実は、これらの手段の組み合わせが効果的に利用可能でないことを示すものではない。
【図面の簡単な説明】
【００５０】
【図１】図１は、本発明の第１実施例による方法の主要なステップを示す概略的なブロック図である。
【図２】図２は、本発明の第２実施例による方法の主要なコンポーネントを示す概略的なブロック図である。
【図３】図３は、図１又は図２の方法に利用されるパッチ特徴抽出方法の主要なステップを示す概略的なブロック図である。
【図４】図４は、図１又は図２の方法に利用されるカーブ特徴抽出方法の主要なステップを示す概略的なブロック図である。
【図５】図５は、図１の方法に使用される教師付きのケースにおけるモデル学習方法の主要なステップを示す概略的なブロック図である。
【図６】図６は、図２の方法に利用される教師なしのケースによるモデル学習方法の主要なステップを示す概略的なブロック図である（注意：矩形はプロセスを示し、平行四辺形はデータを示す）。
【図１】
2007531136.tif 000006
【図２】
2007531136.tif 000007
【図３】
2007531136.tif 000008
【図４】
2007531136.tif 000009
【図５】
2007531136.tif 000010
【図６】
2007531136.tif 000011
【国際調査報告】
2007531136.tif 000012
2007531136.tif 000013
2007531136.tif 000014