"第1画像と第2画像とを比較する方法であって、第1画像の複数の第1キーポイントと第2画像の複数の第2キーポイントとを識別するステップと、各第1キーポイントを、対応する第2キーポイントと関連付けして、対応するキーポイントマッチを形成するステップと、第1キーポイントの各ペアについて、それらの間の距離を計算して、対応する第1長さを得るステップと、第2キーポイントの各ペアについて、それらの間の距離を計算して、対応する第2長さを得るステップと、複数の距離比率を計算するステップであって、各距離比率は、それぞれ、第1長さと第2長さとの間での選択されたものと、第2長さと第1長さとの間での対応する選択されたものとの間での長さ比率に基づく、ステップと、前記複数の距離比率の統計的分布を計算するステップと、前記第1画像および前記第2画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成するステップと、前記複数の距離比率の前記統計的分布と、前記モデル関数とを比較するステップと、前記比較に基づいて、前記第1画像が、前記第2画像に描写されたオブジェクトのビューを含むかを評価するステップとを含む方法。請求項1に記載の方法であって、前記複数の距離比率の前記分布を、複数の順序付けられたビンを有するヒストグラムの形にするステップであって、各ビンは距離比率の値のそれぞれの間隔に対応するものであり、前記ヒストグラムは、各ビンに関して、前記それぞれの間隔内に含まれる値を有する分布の距離比率の対応する数を列挙する、ステップと、各ビンに関して、前記ビンにわたっての前記モデル関数の積分に対応する、対応するモデル確率を生成するステップとを更に含み、前記複数の距離比率の分布と前記モデル関数とを比較する前記ステップは、前記ヒストグラムと前記モデル確率とを比較するステップを含む、方法。請求項2に記載の方法であって、前記ヒストグラムと前記モデル確率とを比較する前記ステップは、ピアソンのカイ2乗検定を行うステップを含む、方法。請求項1から3の何れかに記載の方法であって、前記距離比率を計算する前記ステップは、前記長さ比率の対数の計算を提供する、方法。請求項2から4の何れかに記載の方法であって、誤ったキーポイントマッチの数を推定するステップを更に含み、誤ったキーポイントマッチは、前記第1画像と前記第2画像とに描写された同じオブジェクトの同じポイントに対応しない第1キーポイントと第2キーポイントとにより形成され、誤ったキーポイントマッチの数を推定する前記ステップは、重みパラメータを初期値へと初期化するステップと、以下のaおよびbのステップ、a前記重みパラメータを用いて前記モデル確率を重み付けするステップと、b前記重みパラメータの値を増加させるステップとを少なくとも1つの重み付けされたモデル確率の値が、前記モデル確率に対応する前記ビンにおいて前記ヒストグラムにより列挙されている距離比率の数に到達するまで反復するステップと、前記重みパラメータがとる最新の値に基づいて、誤ったキーポイントマッチの数を求めるステップとを含む、方法。請求項5に記載の方法であって、正しいキーポイントマッチの数を推定するステップを更に含み、正しいキーポイントマッチは、前記第1画像と前記第2画像とに描写された同じオブジェクトの同じポイントに対応する第1キーポイントと第2キーポイントとにより形成されるものであり、正しいキーポイントマッチの数を推定する前記ステップは、第1キーポイントマッチの数に、前記重みパラメータがとる前記最新の値を1から減算した値の平方根と等しい項を乗算したものに基づく、方法。請求項6に記載の方法であって、マトリックスを計算するステップであって、前記マトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、前記キーポイントマッチのそれぞれのペアの前記距離比率を含む前記ビンのところで前記ヒストグラムがとる値と、前記ビンに対応する重み付けされた前記モデル確率との間の差に対応する値を有する、ステップと、前記マトリックスの主な固有ベクトルを見つけるステップと、前記主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別するステップとを更に含む方法。請求項7に記載の方法であって、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別する前記ステップは、最も大きな絶対値を有する前記固有ベクトルの前記エレメントを識別するステップを含む、方法。第1画像と第2画像とを比較するための装置であって、前記第1画像の複数の第1キーポイントと前記第2画像の複数の第2キーポイントとを識別するように構成された第1識別ユニットと、各第1キーポイントと、対応する第2キーポイントとを関連付けて、対応するキーポイントマッチを形成するように構成された関連付けユニットと、第1キーポイントの各ペアについて、それらの間の距離を計算して、対応する第1長さを得るように構成された第1計算ユニットと、第2キーポイントの各ペアについて、それらの間の距離を計算して、対応する第2長さを得るように構成された第2計算ユニットと、複数の距離比率を計算するように構成された第3計算ユニットであって、各距離比率は、それぞれ、第1長さと第2長さとの間での選択されたものと、第2長さと第1長さとの間での対応する選択されたものとの間での長さ比率に基づく、第3計算ユニットと、前記複数の距離比率の統計的分布を計算するように構成された第4計算ユニットと、前記第1画像および前記第2画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成するように構成された第1生成ユニットと、前記複数の距離比率の前記統計的分布と前記モデル関数とを比較するように構成された第1比較ユニットと、前記比較に基づいて、前記第1画像が、前記第2画像に描写されたオブジェクトのビューを含むかを評価するように構成された評価ユニットとを含む装置。請求項9に記載の装置であって、前記複数の距離比率の分布を、複数の順序付けられたビンを有するヒストグラムの形に配置するように構成された配置手段であって、各ビンは距離比率の値のそれぞれの間隔に対応し、前記ヒストグラムは、各ビンに関して、前記それぞれの間隔内に含まれる値を有する前記分布の距離比率の対応する数を列挙する、配置手段と、各ビンについて、前記ビンにわたっての前記モデル関数の積分に対応する、対応するモデル確率を生成するように構成された第2生成ユニットとを更に含み、前記第1比較ユニットは、前記ヒストグラムと前記モデル確率とを比較するように構成された第2比較ユニットを含む、装置。請求項10に記載の装置であって、誤ったキーポイントマッチの数を推定するように構成された第1推定ユニットを更に含み、誤ったキーポイントマッチは、前記第1画像と前記第2画像とに描写された同じオブジェクトの同じポイントに対応しない第1キーポイントと第2キーポイントとにより形成され、前記第1推定ユニットは、重みパラメータを初期値へと初期化するように構成された初期化ユニットと、重み付けユニットであって、以下のaおよびbの動作、a前記重みパラメータを用いて前記モデル確率に重み付けすること、およびb前記重みパラメータの値を増加させることを、少なくとも1つの重み付けされたモデル確率の値が、前記モデル確率に対応する前記ビンにおいて前記ヒストグラムにより列挙されている距離比率の数に到達するまで反復するように構成された重み付けユニットと、前記重みパラメータがとる前記最新の値に基づいて、誤ったキーポイントマッチの数を求めるように構成された決定ユニットとを含む、装置。請求項11に記載の装置であって、正しいキーポイントマッチの数を推定するように構成された第2推定ユニットを更に含み、正しいキーポイントマッチは、前記第1画像と前記第2画像とに描写された同じオブジェクトの同じポイントに対応する第1キーポイントと第2キーポイントとにより形成され、前記第2推定ユニットは、第1キーポイントマッチの数に、前記重みパラメータがとる最新の値を1から減算した値の平方根と等しい項を乗算したものに基づいて、正しいキーポイントマッチの数を推定するように構成された、装置。請求項12に記載の装置であって、マトリックスを計算するように構成された第5計算ユニットであって、前記マトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、前記キーポイントマッチのそれぞれのペアの前記距離比率を含む前記ビンにおいて前記ヒストグラムがとる値と、前記ビンに対応する重み付けされた前記モデル確率との間の差に対応する値を有する、第5計算ユニットと、前記マトリックスの主な固有ベクトルを見つけるように構成された発見ユニットと、前記主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいキーポイントマッチと考えられるかを識別するように構成された第2識別ユニットとを更に含む装置。クエリ画像を受け取り、前記画像における対応する第1キーポイントを識別するように構成されたキーポイント検出ユニットと、前記第1キーポイントのローカルのアスペクトを、対応する第1ローカル記述子を通じて記述するように構成された特徴計算ユニットと、複数の参照画像を記憶する参照データベースであって、各参照画像に関して、対応する第2キーポイントと、前記第2キーポイントの対応する第2ローカル記述子とを更に記憶する参照データベースと、少なくとも1グループの参照画像のうちの各参照画像に関して、前記第1ローカル記述子と前記参照画像の前記第2ローカル記述子とを比較するように構成された特徴マッチングユニットであって、前記第1キーポイントと前記参照画像の前記第2キーポイントとを関連付けて、対応するキーポイントマッチの組を生成するように構成された特徴マッチングユニットと、前記特徴マッチングユニットにより行われた比較に基づいて参照図のサブセットを選択するように構成された選択ユニットと、前記クエリ画像と前記サブセットの1つの参照画像とを含む各ペアに関して、正しいキーポイントマッチの数を計算するように構成された最適化ユニットであって、請求項12または請求項13に記載の装置を含む最適化ユニットとを含むシステム。請求項14に記載のシステムであって、ビジュアルサーチサーバと、ネットワークを通じて前記ビジュアルサーチサーバへクエリ画像を供給するように構成された複数の端末とを更に含み、前記ビジュアルサーチサーバは、前記キーポイント検出ユニットと、前記特徴計算ユニットと、前記参照データベースと、前記特徴マッチングユニットと、前記選択ユニットと、前記最適化ユニットとを含む、システム。請求項14に記載のシステムであって、ビジュアルサーチサーバと、ネットワークを通じて前記ビジュアルサーチサーバへクエリ画像を供給するように構成された複数の端末とを更に含み、前記ビジュアルサーチサーバは、前記参照データベースと、前記特徴マッチングユニットと、前記選択ユニットと、前記最適化ユニットとを含み、各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットとを含む、システム。請求項14に記載のシステムであって、ビジュアルサーチサーバと、ネットワークを通じて前記ビジュアルサーチサーバとデータを交換するように構成された複数の端末とを更に含み、前記ビジュアルサーチサーバは前記参照データベースを含み、各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットと、それぞれの特徴マッチングユニットと、それぞれの選択ユニットと、それぞれの最適化ユニットと、それぞれのローカルデータベースとを含み、各端末は、前記参照データベースに記憶されている第2キーポイントと前記第2キーポイントの対応する第2ローカル記述子とのそれぞれのセットを、前記ビジュアルサーチサーバから受け取るように構成され、前記端末の前記ローカルデータベースは、受け取った第2キーポイントと第2ローカル記述子との前記セットを記憶するように構成され、記憶された第2キーポイントと第2ローカル記述子との前記セットは、少なくとも1グループの参照画像のうちの前記参照画像に対応する、システム。出願人は、オブジェクト認識サービスを実現させるための上記の既知のアプローチが、幾つかの欠点の影響を受けることを発見した。特に、これらのアプローチは、反復する手順に基づいたり、大量のデータの処理を必要としたりするので、時間を浪費する。出願人は、時間の浪費および大量のデータの処理に関して、これらのアプローチを改善することに関する問題に取り組んだ。特に、出願人は、データ処理に関して信頼性があり、且つ時間の浪費に関して良好な能力を有する、画像を比較する方法を提供することに関する問題に取り組んだ。出願人は、キーポイントの組が第1画像クエリ画像上に生成され、そのキーポイントの組が第2画像参照画像上に生成される対応するキーポイントの組と関連付けされて、対応するキーポイントマッチの組を形成するところから始めることにより、本発明に従った画像を比較する方法が、主段階と2つの後続のオプション段階とを含むことができることを発見した。主段階は、キーポイントマッチを生成した後に適用されるものであり、キーポイントマッチの統計的な処理を提供し、それに従って、幾何学的整合性テストgeometricconsistencytestを通じて、クエリ画像と参照画像とが同じオブジェクトを描写しているようであるか否かについての評価を行う。より詳細には、誤ったマッチアウトライアの統計的分布を表すモデル関数を生成後、適合度テストを行い、参照画像が、クエリ画像に存在するオブジェクトのビューviewを含んでいるかを決定する。肯定的結果が得られた場合、方法は、参照画像に描写されているオブジェクトと、クエリ画像に描写されているオブジェクトとの間の実際の相似性のランク付けに使用されるスコアを計算することができる。第2段階は、キーポイントマッチの全ての組の中で幾つのキーポイントマッチがインライアであるかを評価することを可能にする。この段階は、ビジュアルサーチアプリケーションにおける精度を向上させるように、好都合に行うことができる。第3段階は、何れのキーポイントマッチがインライアであり、何れのキーポイントマッチがアウトライアであるかを、特に識別することを可能にする。このような段階は、拡張現実augmentedrealityなどのような幾つかの特定のアプリケーションにおいて、好都合に行うことができる。より詳細には、本発明の1つの態様によると、本発明は、第1画像と第2画像とを比較する方法と関連する。方法は、第1画像の複数の第1キーポイントと第2画像の複数の第2キーポイントとを識別し、各第1キーポイントと、対応する第2キーポイントとを関連付けし、対応するキーポイントマッチを形成することを含む。第1キーポイントの各ペアに関して、方法は更に、それらの間の距離を計算して、対応する第1長さを得ることを含む。同様に、第2キーポイントの各ペアに関して、方法は、それらの間の距離を計算して、対応する第2長さを求めることを含む。方法は更に、複数の距離比率を計算することを含み、それぞれの距離比率は、第1長さと第2長さとの間での選択されたものと、第2長さと第1長さとの間での対応する選択されたものとの間での、それぞれの、長さ比率に基づく。方法は更に、複数の距離比率の統計的分布を計算することと、第1画像および第2画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成することとを含む。方法は、前記の複数の距離比率の統計的分布と、前記のモデル関数とを比較することと、前記の比較に基づいて、第1画像が、第2画像に描写されたオブジェクトのビューを含むかを評価することとを含む。本発明の1つの実施形態に従うと、方法は、複数の距離比率の分布を、複数の順序付けられたビンbinを有するヒストグラムの形に配置することを含み、各ビンは距離比率値のそれぞれの間隔に対応する。ヒストグラムは、各ビンに関して、それぞれの間隔内に含まれる値を有する分布の距離比率の対応する数を列挙する。各ビンに関して、方法は更に、前記のビンにわたってのモデル関数の積分に対応する、対応するモデル確率を生成することを含む。前記の、複数の距離比率の分布と前記のモデル関数とを比較することは、ヒストグラムとモデル確率とを比較することを含む。好適には、前記のヒストグラムとモデル確率とを比較することは、ピアソンのカイ2乗検定を行うことを含む。好都合なことに、前記の距離比率を計算することは、長さ比率の対数を計算することを提供する。本発明の1つの実施形態に従うと、方法は更に、誤ったキーポイントマッチの数を推定することを含む誤ったキーポイントマッチは、第1画像と第2画像とに描写された同じオブジェクトの同じポイントに対応しない第1キーポイントと第2キーポイントとにより形成される。前記の誤ったキーポイントマッチの数を推定することは、重みパラメータを初期値へと初期化することと、次のaおよびbを反復することと、即ち、a重みパラメータを用いてモデル確率に重み付けすること、およびb重みパラメータの値を増加させることを、少なくとも1つの重み付けされたモデル確率の値が、前記のモデル確率に対応するビンにおいてヒストグラムにより列挙されている距離比率の数に到達するまで反復することとを含む。方法は更に、重みパラメータがとる最新の値に基づいて、誤ったキーポイントマッチの数を求めることを含む。本発明の1つの実施形態に従うと、方法は更に、正しいキーポイントマッチの数を推定することを含む正しいキーポイントマッチは、第1画像と第2画像とに描写された同じオブジェクトの同じポイントに対応する第1キーポイントと第2キーポイントとにより形成される。前記の正しいキーポイントマッチの数を推定することは、第1キーポイントマッチの数に、重みパラメータがとる最新の値を1から減算した値の平方根と等しい項を、乗算したものに基づく。本発明の更なる実施形態に従うと、方法は更に、マトリックスを計算することを含み、そのマトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、キーポイントマッチのそれぞれのペアの距離比率を含むビンのところでヒストグラムがとる値と、前記のビンに対応する重み付けされたモデル確率weightedmodelprobabilityとの間の差に対応する値を有する。方法は更に、マトリックスの主な固有ベクトルを見つけることと、前記の主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別することとを含む。前記の、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別することは、最も大きな絶対値を有する固有ベクトルのエレメントを識別することを含む。本発明の1つの態様では、第1画像と第2画像とを比較するための装置を提供する。装置は、第1画像の複数の第1キーポイントと第2画像の複数の第2キーポイントとを識別するように構成される第1識別ユニットと、対応するキーポイントマッチを形成するために、各第1キーポイントと、対応する第2キーポイントとを関連付けように構成される関連付けユニットとを含む。第1計算ユニットは、第1キーポイントの各ペアに対して、それらの間の距離を計算して、対応する第1長さを得るように構成され、第2計算ユニットは、第2キーポイントの各ペアに対して、それらの間の距離を計算して、対応する第2長さを得るように構成される。装置は更に、複数の距離比率を計算するように構成された第3計算ユニットを含み、各距離比率は、それぞれ、第1長さと第2長さとの間での選択されたものと、第2長さと第1長さとの間での対応する選択されたものとの間での長さ比率に基づく。装置は更に、複数の距離比率の統計的分布を計算するように構成された第4計算ユニットと、第1画像および第2画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成するように構成された第1生成ユニットとを含む。装置は、前記の複数の距離比率の統計的分布と前記のモデル関数とを比較するように構成された第1比較ユニットと、前記の比較に基づいて、第1画像が、第2画像に描写されたオブジェクトのビューを含むかを評価するように構成される評価ユニットとを含む。本発明の1つの実施形態に従うと、装置は更に、複数の距離比率の分布を、複数の順序付けられたビンを有するヒストグラムの形に配置するよう構成された配置手段arrangingmeansを含み、各ビンは距離比率値のそれぞれの間隔に対応し。ヒストグラムは、各ビンに関して、それぞれの間隔内に含まれる値を有する分布の距離比率の対応する数を列挙する。装置は更に、各ビンに関して、前記のビンにわたってのモデル関数の積分に対応する、対応するモデル確率を生成するように構成された第2生成ユニットを含む。前記の第1比較ユニットは、ヒストグラムとモデル確率とを比較するように構成された第2比較ユニットを含む。本発明の更なる実施形態に従うと、装置は、誤ったキーポイントマッチの数を推定するように構成される第1推定ユニットを含み、誤ったキーポイントマッチは、第1画像と第2画像とに描写された同じオブジェクトの同じポイントに対応しない第1キーポイントと第2キーポイントとにより形成される。第1推定ユニットは、重みパラメータを初期値へと初期化するように構成された初期化ユニットと、a重みパラメータを用いてモデル確率を重み付けする操作と、b重みパラメータの値を増加させる操作とを、少なくとも1つの重み付けされたモデル確率の値が、前記のモデル確率に対応するビンにおいてヒストグラムにより列挙されている距離比率の数に到達するまで反復するように構成された重み付けユニットとを含む。装置は更に、重みパラメータがとる最新の値に基づいて、誤ったキーポイントマッチの数を求めるように構成された決定ユニットを含む。好ましくは、装置は更に、正しいキーポイントマッチの数を推定するように構成された第2推定ユニットを含み、前記の第2推定ユニットは、第1キーポイントマッチの数に、重みパラメータがとる最新の値を1から減算した値の平方根と等しい項を乗算したものに基づいて、正しいキーポイントマッチの数を推定するように構成される。本発明の更なる実施形態に従うと、装置は更に、マトリックスを計算するように構成された第5計算ユニットを含み、そのマトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、キーポイントマッチのそれぞれのペアの距離比率を含むビンにおいてヒストグラムがとる値と、前記のビンに対応する重み付けされたモデル確率weightedmodelprobabilityとの間の差に対応する値を有する。装置は更に、マトリックスの主な固有ベクトルを見つけるように構成された発見ユニットと、前記の主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別するように構成された第2識別ユニットとを含む。本発明の更なる態様では、クエリ画像を受け取り、前記の画像における対応する第1キーポイントを識別するように構成されたキーポイント検出ユニットと、前記の第1キーポイントのローカルのアスペクトを、対応する第1ローカル記述子を通じて記述するように構成された特徴計算ユニットとを含むシステムを提供する。システムは更に、複数の参照画像を記憶する参照データベースを含み、各参照画像に関して、参照データベースは更に、対応する第2キーポイントと、それら第2キーポイントの対応する第2ローカル記述子とを記憶する。システムは更に、少なくとも1グループの参照画像のうちの各参照画像に関して、第1ローカル記述子と前記の参照画像の第2ローカル記述子とを比較するように構成され、それに従って、第1キーポイントと前記の参照画像の第2キーポイントとを関連付けて、対応するキーポイントマッチの組を生成するように構成された特徴マッチングユニットを含む。システムは更に、特徴マッチングユニットにより行われた比較に基づいて参照図のサブセットを選択するように構成された選択ユニットと、クエリ画像とサブセットの参照画像とを含む各ペアに関して、正しいキーポイントマッチの数を計算するように構成された最適化ユニットとを含む。本発明の1つの実施形態に従うと、システムは更に、ビジュアルサーチサーバと、ネットワークを通じてビジュアルサーチサーバとデータを交換するように構成された複数の端末とを含む。本発明の1つの実施形態に従うと、ビジュアルサーチサーバは、キーポイント検出ユニットと、特徴計算ユニットと、参照データベースと、特徴マッチングユニットと、選択ユニットと、最適化ユニットとを含む。本発明の別の実施形態に従うと、ビジュアルサーチサーバは、参照データベースと、特徴マッチングユニットと、選択ユニットと、最適化ユニットとを含み、各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットとを含む。本発明の更に別の実施形態に従うと、ビジュアルサーチサーバは参照データベースを含み、各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットと、それぞれの特徴マッチングユニットと、それぞれの選択ユニットと、それぞれの最適化ユニットと、それぞれのローカルデータベースとを含む。各端末は、参照データベースに記憶された、第2キーポイントと、第2キーポイントの対応する第2ローカル記述子とのそれぞれのセットを、ビジュアルサーチサーバから受け取るように構成され、端末のローカルデータベースは、受け取った前記の第2キーポイントと第2ローカル記述子とのセットを記憶するように構成され、前記の記憶された第2キーポイントと第2ローカル記述子とのセットは、少なくとも1グループの参照画像のうちの参照画像に対応する。本発明のこれらおよび他の特徴および利点は、例示であり制限を加えるためのものではない幾つかの実施形態についての以下の説明を、添付の図面と関連させて読むことにより、明らかになる。既に述べたように、2つの画像の比較は、第1画像のキーポイントと第2画像の対応するキーポイントとのマッチングのために行われる。キーポイントマッチは、2つの画像の対応するキーポイントが、同じオブジェクト2つの画像の双方に描写の同じポイントに対応する場合に、正しいインライアであると言われ、逆に、キーポイントマッチは、2つのキーポイントが、同じオブジェクトの同じポイントに対応しない場合に、誤りアウトライアであると言われる。図1Aに示す例では、各画像は同じオブジェクト教会のピクチャであり、それぞれのキーポイントマッチは、それぞれの実線で示されている。図1Aの例示的ケースで示されているキーポイントマッチは、インライアとアウトライアとの双方を含んでいる。同じ例示的ケースにおいてアウトライアを除いたものを、図1Bに示している。以下の説明において、新規な画像比較方法を提示する。ここで提案する方法は、クエリ画像または単にクエリと呼ばれる第1画像上で生成されたキーポイントの組と、参照画像と呼ばれる第2画像上で生成された対応するキーポイントの組とを関連付けて、対応するキーポイントマッチの組を形成するようにしたところから開始するものであり、主段階と2つの後続するオプション段階とを含む。1主段階は、キーポイントマッチを生成した後に適用されるものであり、キーポイントマッチを統計的に処理し、それに従って、幾何学的整合性検査を通じて、クエリ画像と参照画像とが同じオブジェクトを描写しているようであるか否かについての評価を行う。より詳細には、誤ったマッチアウトライアの確率的モデルを生成後、適合度テストを行い、参照画像が、クエリ画像に存在するオブジェクトのビューを含んでいるかを決定する。肯定的結果が得られた場合、方法は、参照画像に描写されているオブジェクトと、クエリ画像に描写されているオブジェクトとの間の実際の相似性のランク付けに使用されるスコアを計算することができる。2第2段階オプションは、キーポイントマッチの全ての組の中で幾つのキーポイントマッチがインライアであるかを評価することを可能にする。この段階は、ビジュアルサーチアプリケーションにおける精度を向上させるように、好都合に行うことができる。3第3段階これもオプションは、何れのキーポイントマッチがインライアであり、何れのキーポイントマッチがアウトライアであるかを、特定的に識別することを可能にする。このような段階は、拡張現実などのような幾つかの特定のアプリケーションにおいて、好都合に行うことができる。この説明のセクション1では、この方法で用いる特定の統計の特性と、ログ距離比率logdistanceratioの概念とを紹介するが、これらの双方とも、誤ったマッチおよび正しいマッチと関連する。後続の3つのセクションセクション2~4では、提案される方法の3つの段階の数学的および統計的な面について開示する。セクション5は、方法の3つの段階の主なステップを開示する。最後のセクションセクション6は、提案される方法の例示的な応用に関するものである。セクション1-距離の比率の統計N個のマッチングされたキーポイントの組を考慮する。1上記の組において、xiは、クエリ画像における第iのキーポイントの座標を含み、yiは、参照画像におけるマッチングされるキーポイントの座標を含む。ペアxi,yiは、2つのキーポイントが正しくマッチングされている場合、インライアと呼ばれる。逆に、キーポイントが誤ってマッチングされている場合、ペアはアウトライアと呼ばれる。提案される方法は、上記で引用したTsaiその他による論文で提案されているログ距離比率省略形ではLDRと呼ばれるものを用いる。キーポイントは別個である必要があり、従って、下記のような関係である。xi≠xj,yi≠yjまた、LDRは、i=jの場合には定義されない。LDRは、長さの比率の関数であり、相似性に関しては不変である。対数演算子が存在しているので、クエリ画像が参照画像と交換される場合xがyになる場合、またはその逆の場合、LDRは符号を逆にする。N個のマッチングされたキーポイントxi,yiの組は、クエリ画像上のN個のキーポイントxiと参照画像上のN個の対応するキーポイントyiとを含むものであり、そのN個のマッチングされたキーポイントの組が与えられた場合、n=NN-1/2であるn個の別個のログ距離比率が存在する。そのようなログ距離比率の統計的分布は、対応するヒストグラムの形で表すことができ、それをここではLDRヒストグラムという。LDRヒストグラムは、アレイh=[h1hk]Tにより表すことができる。hは、K個の予め定めた間隔T1,,TKのそれぞれの間隔内に含まれる観察されたログ距離比率を計数しているときに生じる頻度のアレイであり、以下では、予め定めた間隔をビンと呼ぶ。例えば、ビンbins、複数のビンは、下記の例のように、幅が0.2であり、下の値が-2.5であり、上の値が2.5である25の間隔とすることができる。T12523T22321T252325図1Aの場合のLDRヒストグラムの例は、図1Cに示している。LDRの主な利点は、インライアのペアとアウトライアのペアとに対して異なる挙動を示すことである。多くの画像変換インライアの挙動を決定するに関して、LDRは、間隔に限定される。アウトライアに関しては、LDRは、そのような間隔の外へ延び、また、適合度検定に使用できる特有の確率密度関数を有する。LDRは、2つの総称的なキーポイントペア、即ち、xi,yiとxj,yjの関数である。3つの状態が発生し得るが、それらは、双方のペアがアウトライアである状態と、双方がインライアである状態と、一方のペアがインライアであり他方のペアがアウトライアである状態とである。1.1双方のペアがアウトライアのときのLDRマッチングプロセスは、画像中のシーンの幾何図形的配列の何れの知識によっても制限されない。なぜなら、そのような知識は、マッチングが行われる前には使用できないからである。たとえ2つの画像が同じオブジェクトを示す場合でも、誤ったマッチを妨げる機構はない。2つの画像が、同じまたは非常に似たオブジェクトを示さない場合、何れのマッチングも誤りであると考えられる。たとえマッチングプロセスが決定性deterministic、静的であるとしても、誤ってマッチングされたキーポイントの位置は予測できない。一般に、アウトライアの幾何学パターンを発見するのは不可能であり、そのようなパターンを導き出せる優れた原理はない。従って、誤ったマッチングはランダムプロセスとして考慮され、アウトライアの挙動は、アウトライアモデル関数と呼ばれる適切な密度関数を通じてモデル化される。アウトライアモデル関数の定義。AおよびBが矩形であるとする。xi,xj∈Aおよびyi,yj∈Bが、ランダムに描かれたポイントであり、確率変数randomvariableXi,XjおよびYi,Yjに対応するものとする。ランダムな変数CをLDRとする。C=ldrXi,Xj,Yi,Yjアウトライアモデル関数は、Cに対する確率密度関数fccである。アウトライアモデル関数は、正規normalと一様uniformとの2つのタイプのキーポイント分布に関して表すことができる。正規に分布されたキーポイント座標。キーポイントが正規に分布しているという仮定は、アウトライアモデル関数の定式化を簡単なものとし、これは実際のケースに対しての良い近似である。クエリ画像のキーポイントは独立同分布independentandidenticallydistributedi.i.d.であると想定され、平均μおよび分散1/2Iを有し、正規に分布する確率変数Xとして挙動する。座標は適切にスケーリングされ、それにより、キーポイントは画像全体に分布していると仮定される分散は、水平方向および垂直方向において同じであることに留意されたい。従って、2つのキーポイントの間の差は正規分布となる。Xi-Xj~N0,I;i≠j4参照画像のキーポイント{Yn}が{Xn}と同じ統計を有し、キーポイントXnがキーポイントYnとマッチングされると想定する。その場合、平方の距離比率squareddistanceratioは、2,2の自由度のF分布を有する。これは、例えば、PrenticeHallの出版のRJLarsenおよびMLMarxによるAnintroductiontoMathematicalStatisticsanditsApplications数学的統計およびその応用の概論1896年、第2版の第338ページに示されている。確率密度関数F2,2は下記のとおりである。上記の式では、簡素化のために、式5の確率変数Rij2をSに置き換えている。ログ距離比率平方の距離比率ではないが考慮されているので、平方根および対数が確率変数S=Rij2に適用される。更に、2つの画像のサイズの違いや2つの画像におけるキーポイントの広がりの違いを考慮に入れるために、関数は、2つの画像におけるキーポイントの標準偏差のプロポーションproportionに対応するパラメータa、即ち、以下の式に示すパラメータaを確率変数に乗算することにより、そのようなケースに対しての拡張が行われる。F2,2のp.f.d.に対するこれらの変更により、下記のアウトライアモデル関数が導き出される。アウトライアモデル関数。2つの画像がランダムなキーポイント{Xn}および{Yn}を有するものとし、それら全てが二変量正規分布を有し、第1画像において分散σx2、第2画像において分散σy2を有するものとする。a2を分散のプロポーションとする。出願人は、ログ距離比率が確率密度関数を有すると判断した。式7のアウトライアモデル関数は、提案する方法の基礎である。アウトライアモデル関数の形は、図2に示されている。このアウトライアモデル関数が矩形画像のアスペクト比を考慮しないことに、留意すべきである。なぜなら、水平の分散と垂直の分散とが同じと想定されているからである。図3A~図3Fは幾つかの例を示し、それぞれが、チューリッヒビルディングイメージデータベースZurichBuildingImageDatabase1005の画像を含み、201のビルディングのそれぞれについての5つのビューを含むからの画像の個々のペアクエリ画像-参照画像を示す。キーポイントは円で示し、ラインは、別の画像におけるマッチングされるキーポイントの位置を指す。それぞれの画像ペアに関して、LDRヒストグラムと、式7の定式化での、対応するアウトライアモデル関数とが示されている。これらの画像は異なるビルディングを示すので、全てのキーポイントマッチをアウトライアと考える必要があることに、留意されたい。これらの例から、アウトライアモデル関数は、全てのマッチがアウトライアであるときには常にLDRヒストグラムにかなり近いものとなる、ということを観察することができる。1.2双方のペアがインライアのときのLDR一般に、全てのキーポイントマッチがインライアである場合のLDRヒストグラムは、アウトライアに対するLDRヒストグラムと大きく異なることが多い。多数の実際的なケースにおいて、インライアのみに対してのLDRヒストグラムは、アウトライアのみに対してのLDRヒストグラムよりも狭い。即ち、インライアのみに対してのLDRヒストグラムは、アウトライアのLDRヒストグラムがゼロではない幾つかのビン特に、横方向のビンにわたって、ゼロとなる。2つの画像における関連付けされたキーポイントxiおよびyiは、見られているオブジェクト上の同じポイントのマッピングを通じて関連するので、確率的モデリングを用いる代わりに、LDRヒストグラムの上界および下界を考慮することが好都合である。ここで行われた研究は、3Dシーンにおける平面上のポイントに限定される。なぜなら、深さの変化が限定されたオブジェクトを認識することを、主に考えているからである。平面は、ビルディングや本や看板などのような、画像内の多くの対象となるオブジェクトの可視部分を近似したものとして表す。平面上の部分にある2つの画像は、ホモグラフィhomographyHを通じて関連する。y=h/d9上記の式において、xおよびyは2つの画像における同じ点の投射の座標である。従って、同じ平面上のインライアのペアは、同じホモグラフィを通じて関連する。アファイン変換および一般的ホモグラフィに対してのLDRヒストグラムの特徴を、ここで開示する。アファイン変換。アファイン変換は、下記のようなホモグラフィの特別のケースである。上記の式に関して、yn=Kxntである。距離比率は、2×2マトリックスKの特異値singularvalueにより与えられる間隔に制限される。この場合、LDRは下記の間隔にある。ldr∈lnσmaxlnσmin10従って、LDRヒストグラムの非ゼロ部分の幅は、アファイン変換がオブジェクトを変形させる度合いに応じたものとなる。相似変換similaritytransformationに関しては、2つの特異値は等しく、従って、LDRヒストグラムは、ゼロではないビンを1つのみ有する。アファイン変換により、長さが、最小限度として1/3まで縮められ、最大限度として2倍まで伸ばされる場合、2つの特異値は1/3と2とであり、LDRの非ゼロ値に対する間隔は下記のようになる。ホモグラフィ。xi、xjとyi、yjとが、式8および式9のように、下記のホモグラフィを通じて関連するものとする。この場合、LDRも下記の間隔に制限される。ldr∈lnblna11上記の式においてaは最大数であり、bは最小であり、下記のような関係である。ホモグラフィの最も実際的なケースでは、この間隔は、アウトライアに対するLDRのヒストグラムに関しては、用いられる機構の性質に大きく影響されるので、狭いものとなる。SIFTScale-InvariantFeatureTransformやSURFSpeededUpRobustFeturesのような機構は、相似変換に対しては不変であるが、アファイン変換に対してはそうではなく、特にホモグラフィに対してはそうではない。これは、遠近法的な歪みが強くてlnblnaが理論的に広くなり得る場合に、極端なLDR値を生成し得るキーポイントは関連付けされないことを意味する。なぜなら、それらのキーポイントの特徴は、異なる記述子を有するからである。従って、正しく関連付けされたキーポイントに関するインライアのヒストグラムは、相対的に狭い間隔に留まることになるであろう。図4は、クエリ画像と参照画像とが、大きく異なる角度この例では-75度と0度から見た同じ平面オブジェクト矩形を描写する例示的ケースを示す。図4の下部の図は、前記の画像ペアから計算されたアウトライアモデル関数とLDRヒストグラムとを示す。図5Aおよび図5Bは、大きくは異ならない角度から見られているほぼ平面状のオブジェクトビルディングの面が示された2つの例示的ケースを示す。図5Aおよび図5Bの下部の図は、対応するLDRヒストグラムとアウトライアモデル関数とを示す。1.3双方のタイプのペアのときのLDR第3の代替例は、ペアxi、yiがインライアであり、ペアxj、yjがアウトライアである場合または、その逆の場合のためのものである。この場合も、1つの画像のキーポイントがランダムに分布していると仮定する。なぜなら、未知の画像に含まれるキーポイントの位置を制限する幾何学的なパターンや規則を前もって知ることができないからである。従って、それぞれのキーポイントは、式3のように、例えば、正規分布を用いて、確率変数により表すことができる。2つのキーポイントの間の差ベクトルは、式4における場合のようにモデル化される。なぜなら、1つはインライアとして取られ、別の1つはアウトライアとしてとられ、それらの間には相関が無いからである。しかし、式5のF分布は正確に維持できない。なぜなら、F分布の仮定とは異なって、分子と分母とは独立していないからである。インライアとアウトライアとのペアの場合のキーポイントは下記のようである。xiyi,xjπ上記の式において、πは、1つの画像のインライアのキーポイントの、別の画像へのマッピングである未知であるにもかかわらず。この場合における平方の距離比率を表す確率変数は下記のとおりである。上記の式において、分子と分母とは明らかに独立していない。なぜなら、双方ともXjの関数だからである。式13における変数の確率密度を見つけるのは非常に難しいが、ここで提案される方法を考慮するかぎり、見つける必要はないであろう。同じモデル確率、従って、式7のアウトライアモデル関数を用いて、これら2つのケースインライア/アウトライアペアではなく双方がインライアのペアに対してのLDRのヒストグラムを、僅かな誤差はあるがモデル化することが可能であることを、経験により仮定することができる。セクション2-マッチングされない画像の拒絶提案される方法の第1段階LDRヒストグラムは、画像クエリ画像において見ることができるオブジェクトを識別するために用いることができる。従って、識別identificationは、クエリ画像に描写されているオブジェクトのビューを含む参照画像を、参照コレクション参照データベースの参照画像の中から見つけることを意味する。提案される方法の第1段階は、クエリ画像と参照画像との間でのインライアのキーポイントペアを明確に検出することを必要とせずに、オブジェクトを識別することを可能にする。提案される方法の第1段階は幾何学的整合性テストであり、これは、以下の仮定H0:参照画像はクエリに対応しない、H1:参照画像はクエリに対応するの間での二者択一を行うためのものである。H0の仮定は、物事の予期される状態を表すものであり、ほぼ全ての参照画像に、クエリにおけるオブジェクトのビューが含まれていないことが知られている。H0を拒絶してH1を受け入れるにはこれは例外的イベントである、或る程度の根拠が必要である。この根拠は、LDRヒストグラムとアウトライアモデル関数との間の関係において見つけられる。そのヒストグラムがアウトライアモデル関数に良く適合する場合、H0を受け入れ、そうでない場合はH1の仮定を受け入れる。そのような仮定をテストするために、提案される方法では、ピアソンのカイ2乗検定を行う例えば、上記で引用したRJLarsenその他による文献の第402~403ページを参照。ピアソンの検定を適用する前に、離散化アウトライアモデル関数discretizedoutliermodelfunctionの概念を紹介する。ビン、即ち、LDRヒストグラムを構成するために用いられるLDR値の間隔を、k=1,,KであるTkで表すものとする。離散化アウトライアモデル関数は、確率値をK個のビンのそれぞれに割り当てる。p:{1,,K}→[0,1]第kのビンのそれぞれにおいて、値は、そのビンにわたってのアウトライアモデル関数を積分したものと等しい。上記の式において、それぞれの値pkは、モデル確率と呼ばれる。表記を統一するために、モデル確率を、シーケンスpkのエレメントとして考慮する。pk=pk;k=1,,Kピアソンのカイ2乗検定は、LDRヒストグラムと離散化アウトライアモデル関数との間で行われる。ピアソンの検定。αレベルの重要度significanceにおいて、H1の仮定は、下記の場合に受け入れられる。上記の式において、n=NN-1/2であるnは、LDRヒストグラムを構築するために用いた観測結果の合計数、即ち、キーポイントマッチxi,yi、xj,yjのペアの数である。スレッショルドχ1-α,K-12は、K-1の自由度でのカイ2乗検定の1001-αパーセンタイルである。H1の仮定を受け入れるということは、参照画像が、クエリ画像内のオブジェクトを表す候補であることを意味する。スレッショルドを超えるマージンは、2つの画像の類似度の測定値として使用することができる。式15を参照されたい。最大のρを有する参照画像のインデックスを、クエリ画像内のオブジェクトと同一のものidentityとして選択することができる。1つより多くの参照画像が大きいρを有する場合、クエリ画像が、前記の参照画像の全てに存在する幾つかのオブジェクトを示すか、または、前記の参照画像が、非常に似たオブジェクトを描写するかの何れかである。この問題は、参照コレクションの知識を通じてや、手近な識別タスクを通じて、特定の解法を見つけることができる。αパラメータは、確率密度としてアウトライアモデル関数をもつソースからLDRヒストグラムを実際に生じさせた場合において、誤った参照画像を受け入れる確率である。セクション3-インライアの数の推定提案される方法の第2段階関連付けされたキーポイントマッチの組において存在するインライアの数を知ることは、興味のあることである場合が多い。そのような数は、それ自体が有用であり得、また、セクション4で説明するように、アウトライアとインライアとを分離するために必要であり得る。この数は、LDRヒストグラムを用いて推定することができる。キーポイントマッチは2つの互いに素のカテゴリに分類されるので、ヒストグラムは、それぞれのカテゴリに対して1つのヒストグラムコンポーネントhistogramcomponentと呼ばれる2つの項により形成される。インライアに対するヒストグラムとアウトライアに対するヒストグラムとは全く異なり、実際、その差異は、2つのコンポーネントを分離するためおよびそれらの相対的重みを表すために、有用である。先に説明したように、キーポイントマッチがアウトライアである場合、ヒストグラムはアウトライアモデル関数のように見える。更には、ヒストグラムがアウトライアモデル関数と似ている場合、ペアはアウトライアである。より一般的には、ヒストグラムを2つの項に分解でき、その1つの項がアウトライアモデル関数のように見える場合、その項はアウトライアに起因するものである。この原理は、アウトライアの数を推測するため、更には、アウトライアを識別するために使用される。xi,yiとxj,yjとの双方が正しく関連付けされている場合、キーポイントマッチのペアはインライアである。キーポイントマッチの一方または双方が誤って関連付けされている場合、キーポイントマッチのペアはアウトライアである。Pinは、キーポイントマッチのペアがインライアのみを含む確率を示し、Poutは、ペアのエレメントのうちの少なくとも1つがアウトライアである確率を示す。zを、キーポイントマッチのペアに対するLDRの値とし、pz|inおよびpz|outは、条件付き確率密度conditionalprobabilitydensityを表すものとする。アウトライアに対する条件付き確率は、式7のアウトライアモデル関数となると仮定される。pz|out=fzz従って、全体の確率密度は下記の形を有する。pzz=Pinpz|inPoutfzz17この式は、LDRヒストグラムを2つの項に分解したもの対応する。hk=dkgk;k=1,,K18上記の式において、hkはLDRヒストグラムを表し、dkはインライアに起因するコンポーネントであり、gkはアウトライアに起因するコンポーネントである。インライアの数を推定する方法は、アウトライアコンポーネントgkは予測される値に近いものである、という仮定に基づくものであり、以下の式が導きだされる。hk=dkEgk=dknPoutpk19上記の式において、モデル確率pkは、第kのビンの間隔にわたってのアウトライアモデル関数の積分であり、n=NN-1/2であるnは、LDRヒストグラムを構築するために用いたキーポイントマッチのペアの数である。式19には2つの未知の数量があり、それらはアウトライア確率Poutと、インライアコンポーネントdkとである。インライアコンポーネントは負ではない必要があるので、式19は下記のように書き換えることができる。hk-nPoutpk≧020上記のようにすると、式からインライアコンポーネントが除かれる。ここでは、セクション1で説明したように、幾つかの間隔にわたってインライアコンポーネントがゼロであると仮定しているので、それらの間隔にわたって、アウトライアコンポーネントはヒストグラムの値と等しくなければならない。これは、式20における差が、インデックスkの幾つかのビンに関して下界0へ到達するように、アウトライア確率Poutが十分に大きいものであるべきことを、意味する。従って、予め定めた値の小さい組においてアウトライア確率の可能な最大値を見つけるためのサーチが行われる。アウトライア確率のサーチ。k=1,,Kであるhkが、LDRヒストグラムのビンを表すものとする。pkがモデル確率を表し、nがヒストグラムの構築に使用されるキーポイントマッチのペアの数を表すものとする。B={β1,,βL}⊂[0,1]を、Poutの予め定めた適格な値の組とする。出願人は、キーポイントマッチのペアが少なくとも1つのアウトライアを含む確率の推定が、下記のようであると判断した。Pout=max{β:β∈B,hk≧nβpk;k=1,K}21確率1-Poutは、全てのキーポイントマッチのペアxi,yi、xj,yjの中でのインライアの相対的な関数である。インライアのペアxi,yiの数を求めるためには、キーポイントペアの数Nと、キーポイントマッチのペアの数n=NN-1/2とが考慮されねばならない。なぜなら、ヒストグラムは全てのペアxi,yi、xj,yjを計数することにより作られるからである。なお、ここではi≦jである。インライアのペアの数がmで表される場合、インライアからなるキーポイントペアの一対keypointpaircouplesの端数fractionは下記のようになる。分布についての推定および仮定に基づくと、式22の精度は低いものである。従って、mについての仮定の解が好ましい。従って、推定されるインライアのキーポイントペアの数は下記のようになる。図6は、モデル確率をスケーリングしてインライアの数を推定する例を示す。この例では、同じオブジェクト家が2つの画像に描写されている。下部の図は、LDRヒストグラムhk実線でプロットと、推定されたアウトライアのヒストグラム破線でプロットとを示す。この場合、インライアの数は、キーポイントの総数の1/3であると推定された。セクション4-最もインライアでありそうなものの識別提案される方法の第3段階先のステップが完了した後、インライアのヒストグラムコンポーネントを決定するための全ての必要な数量が使用可能とされる式19を参照されたい。dk=hk-nPoutpkこのコンポーネントは、このセクションで示すように、インライアとアウトライアとを分離するために使用できる。キーポイントマッチの各ペアはログ距離比率の値に対応し、インライアのヒストグラムコンポーネントは、その対がインライアを含む確率を表す。この情報は、パラメータとしてキーポイントのそれぞれのペアに対するバイナリ値をもつ尤度関数likelihoodfunctionを定式化するために使用される。1という値は、ペアがインライアであることを意味し、0はペアがアウトライアであることを意味する。インライアの所与の数を制約として用いる場合、この尤度関数を最大化するパラメータは、最もインライアでありそうなものの組を示す。Nをキーポイントマッチの数とし、uをNエレメントのバイナリベクトルとする。u∈{0,1}N24値1を持つエレメントは、対応するキーポイントペアがインライアであることを示し、値0を持つものはアウトライアであることを示す。前のセクションにおける手順のような手順は、インライアの数mの推定を行うので式22、制約を加えることができる。式2のLDRは、キーポイントマッチの各ペアについて知られている。zij=ldrxi,xj,yi,yj;i≠j26理想的には、インライアに対しての条件付き確率密度を知っている場合、単に、インライアに対する全ての確率を加算することにより、尤度の値を、インライアの組の何れの仮定へも割り当てることができる。uはバイナリであるので、この合計を下記のように書き換えることができる。式23および式24の制約の下で式27のLを最大化するバイナリベクトルuは、最もインライアでありそうなm個のインライアの組を表す。式27は、実際的なアルゴリズムを作るために変更する必要がある。インライアの確率密度pz|inについての閉じた形closedformが無い場合、それは式19のインライアのヒストグラムコンポーネントdと置換される。この推移を理解するために、下記の量子化手段quantizerqを紹介するのが有益である。この量子化手段qは、値zに最も近いビンセンター全てのビンセンターξ1,,ξKの中でのビンセンターbincenterに対するインデックスを生成する。これは下記の近似を可能とする。下記の式は、この確率の近似値がLDRヒストグラムのインライアコンポーネントに対して予測される値に比例することを示す。上記の式において、比例定数は、キーポイントマッチのペアの総数であるnと、一対における双方のペアがインライアである確率であるPinと、ビンの幅であるδとである。ここで、式27における理想的な尤度関数を下記のものと置き換えることができる。上記の式において、式31の定数ファクタは、Guを最大化する解を動かさないので、省略されている。マトリックスの形では、上記の式は下記のようになる。Gu=uTDu33上記の式において、マトリックスDは、エレメントi,jとして下記のものを有するインライアのヒストグラムからの値を含む。ここで、インライアの識別の問題を以下のように表すことができる。マトリックスDが全ランクを有する場合、最適のものを計算するのは難しい。近似の解法への道筋は、IEEETransactionsonImageProcessing、vol19、2010年5月の第1319~1326ページのAEgozi、YKeller、およびHGutermanによるImprovingshaperetrievalbyspectralmatchingandmetsimilarityスペクトルマッチングおよび満たされた相似性による形状検索の改善に提供されており、ここでも、式33に関するものと同様の問題に直面している。ここで、バイナリの最適化は簡単なものに置き換えられる。wTDwを最大化する36w∈RN,w=1を条件とする。解は、Dの主な固有ベクトルdominanteigenvector最大の固有値に対応する固有ベクトルである。このベクトルのエレメントは、ゼロに近い場合または最大値に近い場合が多い符号は選択されているので、最大値は正である。従って、固有ベクトルwは、下記の関係に従って、m個の最大のエレメントmは、式22のインライアの推定された数を取ることにより、バイナリベクトルuを得るために使用される。[w,i]=sortw,’descend’37上記の式において、sortw,’descend’ソートw,’降順’は、MatlabMathWorksによるものの関数であり、これは、アレイwのエレメントを降順にソートして、対応する順序付けられたアレイwを生成する。関数sortw,’descend’は、更なるアレイiを生成し、そのエレメントは、アレイwのエレメントのインデックスであり、アレイwの場合と同様に、順序付けられている。結果uは、インライアの組に良く近似したものであり、それは実際的な実験において証明できる。高速固有ベクトル計算fasteigenvectorcomputation。推定したインライアは、Dの主な固有ベクトルのm個の最大エレメントに対応する。目的は、固有ベクトルの計算を、可能な限り、また幾らかは精度を犠牲にしてでも、高速に維持することである。主な固有ベクトルを見つける方法は当技術分野では知られている例えば、TheSocietyforIndustrialandAppliedMathematics、1997年の、LTredethenおよびDBauによるNumericalLinearAlgebra数値的線形数学に開示されているパワー反復およびレイリー商反復thepoweriterationandtheRayleighquotientiterationを参照。双方の方法とも、反復法であり、主な固有ベクトルの最初の推測に依存するものであり、にわか仕立ての候補は中間コラムmeancolumnであり、これは、Dのような負ではないエントリのマトリックスに対して近くなる。セクション5-方法の主なステップ先に説明した方法の主なステップを図7Aないし図7Cに示す。より詳細には、図7Aは、本発明の1つの実施形態に従った方法の第1段階の主なステップを示すフローチャートである。既に説明したように、方法の第1段階は、第1画像と第2画像とが同じオブジェクトを描写しているか否かを評価するものである。画像のペアが比較されるところから、即ち、第1画像クエリ画像がN個のキーポイントxiを含み、第2画像参照画像がN個のキーポイントyiを含むところから開始するものと仮定している。クエリ画像上の各キーポイントxiは、参照画像上の対応するキーポイントyiと関連付けされて、個々のキーポイントマッチxi,yiを定める。第1ステップは、相似性に関して不変である距離比率の関数を用いて、キーポイントマッチxi,yiから距離比率のヒストグラムを生成する。例えば、式2を用いてキーポイントマッチxi,yiからログ距離比率LDRヒストグラムが生成されるブロック702。次に、式2で定義されたログ距離比率LDR関数を用いる場合には、第1ステップで使用される距離比率の関数と関連する確率密度関数、例えば、式7を用いて、対応するアウトライアモデル関数が生成されるブロック704。次のステップは、以前に計算したアウトライアモデル関数の離散化discretizeを行うがブロック706、このステップでは、例えば、式14を、以前に計算したアウトライアモデル関数に適用して、その離散化版を得る。次に、ピアソンの検定式15を用いて、LDRヒストグラムを、離散化アウトライアモデル関数と比較し、全てのキーポイントマッチがランダムであると考えられるか否かの評価を行うブロック708。特に、ピアソンの検定の結果が、離散化アウトライアモデル関数とのLDRヒストグラムの良好な適合を伴う場合ブロック710の出口側分岐Y、それは、キーポイントマッチの全てまたはほぼ全てがアウトライアであることを意味し、従って、参照画像は、クエリ画像に描写されている何れのオブジェクトも示さない。従って、方法は終了する。逆に、ピアソンの検定の結果が、LDRヒストグラムが離散化アウトライアモデル関数と適合しないことを示す場合ブロック710の出口側分岐N、それは、キーポイントマッチの多くがインライアであり得ることを意味し、従って、参照画像は、おそらく、クエリ画像に描写されているオブジェクトを示す。このケースにおいて、望まれる場合には、方法は第2段階へ進む。図7Bは、本発明の1つの実施形態に従った方法の第2段階の主なステップを示すフローチャートである。この段階は、先に説明したアウトライア確率のサーチに基づいて、キーポイントマッチの組のうちの何個のキーポイントマッチがインライアであるかを評価することを可能にする。第1ステップでは、式21のファクタβを初期化するブロック712。例えば、βをゼロに初期化する。ファクタβは、離散化アウトライアモデル関数を重み付けするために使用され、LDRヒストグラムと比較されるようにする。このステップの目的は、式21を通じてキーポイントマッチの所与の一対が少なくとも1つのアウトライアを含む確率を推定することである。より特定時には、各kに対してnβpkが計算されブロック714、項βが、以前にとった値へ所定数量を加算することにより更新されるとブロック716、以前に計算したnβpkと対応するhk各kについてとの間での比較が行われる。各kについて、hkが、以前に計算したnβpkよりも高いという結果となった場合ブロック718の出口側分岐Y、重み付けされた離散化アウトライアモデル関数がLDRヒストグラムよりも低いことを意味し、βの更新された値を用いてnβpkの新たな計算が行われるブロック714へ戻る。上記のようではなく、nβpkが、少なくとも1つのkに関して、hkへ到達した場合ブロック718の出口側分岐N、これは、重み付けされた離散化アウトライアモデル関数の一部特定的には、その横方向のテールが、LDRヒストグラムの対応する部分に到達したまたはそれらを超越したことを意味する。従って、式21に従い、キーポイントマッチのペアが少なくとも1つのアウトライアを含む確率Poutは、βがとる最新の値と等しいと考えられるブロック720。従って、キーポイントマッチのペアが少なくとも1つのインライアを含む推定される確率Pinは、1-Poutと等しく設定されるブロック722。次に、インライアの数mは、式23を用いて計算されるブロック724。この時点で、望まれる場合には、方法は第3段階へ進む。図7Cは、本発明の1つの実施形態に従った方法の第3段階の主なステップを示すフローチャートである。この段階は、何れのキーポイントマッチがインライアであるかと、何れのキーポイントマッチがアウトライアであるかを特定的に識別することを可能にするものであり、36の最大化の問題を解く。第1ステップでは、34の関係において示されるインライアマトリックスDを構築するブロック726。次に、最大化の問題36は、インライアマトリックスDの主な固有ベクトルwを見つけるように解かれるブロック728。最後に、インライアの組の近似値を、関係37および38における以前に見つけた固有ベクトルwを用いて、計算するブロック730。このセクションで説明される方法のステップは、適切な処理ユニットにより行うことができ、それらの構造および機能は、それらに対して定められた特定の応用分野に応じたものとなる。例えば、それぞれの処理ユニットは、方法の1以上のステップを行うように特別に設計されたハードウェアユニットとすることができる。更には、方法のステップは、プログラマブルの機械例えば、コンピュータにより、対応する1組の命令による制御の下で、行うことができる。セクション6-方法の幾つかの例示的な応用図8は、考えられ得るシナリオを概略的に示すものであり、本発明の1つの実施形態に従って、先に説明した方法を用いて、ビジュアルサーチサービスを実施することができる。参照符号800で示される図8のシナリオは、クライアント-サーバ構成に従って構築されるものであり、ビジュアルサーチサーバ810は、複数の端末820と、外部ネットワーク830を通じてデータを交換するために、対話するように構成される。外部ネットワーク830は、MAN、WAN、VPN、インターネット、電話網などである。各端末820は、パーソナルコンピュータ、ノートブック、ラップトップ、パーソナルデジタルアシスタント、スマートフォン、またはデジタル画像を管理できる任意の電子デバイスとすることができる。図9Aに示す本発明の1つの実施形態に従うと、ビジュアルサーチサービスの全ての主な動作は、ビジュアルサーチサーバ810により行われる。ピクチャに描写されているオブジェクトと関連する情報を要求する端末820のユーザは、そのピクチャクエリ画像となるを、ネットワーク830を通じてビジュアルサーチサーバ810へ送信する。ビジュアルサーチサーバ810は、端末820との間でのデータの送信/受信のためにネットワーク830と対話するためのサーバインターフェース902を含む。サーバインターフェース902を通じて、ビジュアルサーチサーバ810は、分析対象となるクエリ画像を受信する。クエリ画像は、そのクエリ画像に含まれるキーポイントを識別するように構成されたキーポイント検出ユニット904へ供給される。キーポイントが生成されると、そのローカルのアスペクトaspectが特徴計算ユニットfeaturecomputationunit906により記述される。この動作は、特徴計算ユニット906により、SIFTScale-InvariantFeatureTransformやSURFSpeededUpRobustFeturesなどのような既知のローカル記述子を用いて、行われる。ビジュアルサーチサーバ810は更に特徴マッチングユニットfeaturematchingunit908を含み、特徴マッチングユニット908は、画像認識に使用される参照画像を記憶する参照データベース910と結合される。クエリ画像から抽出されたローカル記述子と、参照データベースに記憶された参照画像のローカル記述子との比較は、特徴マッチングユニット908により、例えば、記述子間のユークリッド距離に基づく技術のような、既知の画像特徴比較技術を用いて、行われる。参照データベースのそれぞれの参照画像について、特徴マッチングユニット908は、対応するキーポイントマッチの組を含む、対応するリストを出力する。このリストは、クエリ画像に描写されたオブジェクトが何れの参照画像に描写された何れのオブジェクトにも対応しない場合、空であり得る。特徴マッチングユニット908により生成されたリストに基づいて、選択ユニット912は、最高数のキーポイントマッチをクエリ画像と共有する第1のq個の参照画像を選択する。これらの参照画像は、クエリ画像に描写されたオブジェクトを含む最適の候補であると想定されている。本発明の1つの実施形態に従うと、ビジュアルサーチサーバ810は更に、先に説明した方法を実施するように構成される最適化ユニット914を含む。最適化ユニット914は、前記の方法を、選択ユニット912により選択されたq参照画像の組に対応するキーポイントマッチに適用する。クエリ画像と組の中の1つの参照画像とで構成される各ペアに関して、最適化ユニット914は、正しいキーポイントマッチインライアの数を計算する。この計算は、方法の第1段階に従って行われ、好適には、方法の最初の2つの段階即ち、図7Aと図7Bとに示されたものに従って行われる。図7Cに示される方法の第3段階も行われる場合例えば、クエリ画像に描写されているオブジェクトが参照画像に配されているかを示す指示を得ることが望まれる場合、最適化ユニット914は、何れのキーポイントマッチがインライアと考えられるかを、特定的に識別することができる。クエリ画像の対応するキーポイントと正しくマッチングされたキーポイントを十分な数だけ含む、という結果が得られた組の中の参照画像は、少なくとも、クエリ画像に描写されたオブジェクトと同じオブジェクト同じオブジェクトの一部を含むものと考えられる。後者の参照画像は、次に、ビジュアルサーチに要求の結果として、ネットワーク830を通じて端末へ送られるが、その場合において、数えられたインライアの数に基づいて順序付けすることができる。図9Bに示す本発明の別の実施形態に従うと、キーポイント検出ユニット904と特徴計算ユニット906とは、ビジュアルサーチサーバ810に含まれるのではなく、端末820に含まれる。この場合、クエリ画像をビジュアルサーチサーバ810へ送信するのではなく、それぞれの端末820は、クエリ画像からローカルで生成したローカル記述子を直接に送信することができる。先の実施形態と比較して、この解決法は、送信する必要のあるデータクエリ画像全体ではなくローカル記述子の量が少ない。更に、この実施形態に従うと、ビジュアルサーチサーバ810の計算負荷が低減され、ビジュアルサーチサーバ810が、より多くの画像サーチの要求を同時に管理できるようになる。図9Cに示す本発明の更に別の実施形態に従うと、ビジュアルサーチサービスの主な動作のほぼ全てが端末820により行われ、ビジュアルサーチサーバ810は、単に、参照画像のキーポイントとローカル記述子とを記憶し、それらのものの選択されたサブセットを、端末のユーザから要求された特定のビジュアルサーチに基づいて端末へ送信する。例えば、端末820が、GPSシステムを装備したスマートフォンであり、クエリ画像が、スマートフォンのカメラで撮られたピクチャである場合、ビジュアルサーチサーバ810により送信するキーポイントとローカル記述子との選択は、端末820の実際の位置に基づくことができる。この解決法は、モニュメント認識サービスなどのような幾つかのビジュアルサーチサービスにおいて好都合に用いることができる。画像比較動作を管理できるようにするために、端末820は、ローカル参照データベース916と更新ユニット920とを備え、更新ユニット920は、ビジュアルサーチサーバ810により送信されたキーポイントおよびローカル記述子を受信するように適用され、従って、ローカル参照データベース916を更新する。なお、既に記憶されているキーポイントおよびローカル記述子を用いても十分であるので、画像の比較を行うとき毎にローカル参照データベース916の更新を必ず行う必要があるという訳ではいことを、理解すべきである。例えば、ローカル参照データベース916を、1日に1回のみ、ビジュアルサーチサーバ810により更新することができる。先の実施形態と比較して、この解決法は、送信されるデータの量が大きく低減されるので、速い。従って、この解決法は、特に、拡張現実の応用に適する。提案される方法の更に可能な応用は、立体カメラシステムに属するビデオカメラの自動校正である。校正の目的は、基礎的マトリックスfundamentalmatrixと呼ばれるもの、即ち、取得システムacquisitionsystemの内在的および外来的なパラメータを記述するマトリックスの生成である。内在的パラメータはカメラの構成を記述し、外来的パラメータは空間内のカメラの位置を記述する。図10の概略的なフローチャートに示すように、第1カメラ1001は第1画像を取得しブロック1004、第1画像は、対応する第1キーポイントを識別するために処理されるブロック1006。第1キーポイントが識別されると、そのローカルのアスペクトが、対応する第1ローカル記述子を通じて記述されるブロック1008。同様に、第2カメラ1010は第2画像を取得しブロック1012、第2画像は、対応する第2キーポイントを見つけるために処理されるブロック1014。次に、それらのキーポイントのローカルのアスペクトが、対応する第2ローカル記述子を通じて記述されるブロック1016。第1ローカル記述子と第2ローカル記述子とを比較することにより、第1画像と第2画像との間でのキーポイントマッチが生成されるブロック1018。次に、図7A~図7Cに示す方法の3つの段階を適用することにより、インライアであるキーポイントマッチが識別されるブロック1020。インライアが識別されると、基礎的マトリックスを推定するために反復する手順が行われブロック1022、それにより、新たなキーポイントマッチが見つけられるブロック2014。これらの動作は、IEEETransactionsonpatternanalysisandmachineintelligence、Vol19、No6のRHartleyによるIndefenseoftheEightPointAlgorithm8ポイントアルゴリズムを守るに記載された手順に続いて行うことができる。次に、新たなキーポイントマッチは、図7A~図7Cに示す方法の3つの段階により再び処理され、インライアが識別されるブロック1026。この手順即ち、ブロック1022、1024、1026に対応する手順は、インライアの数が安定するまで反復される。上記の記載では、本発明の幾つかの実施形態を詳細に呈示し説明したが、特許請求の範囲に定めた範囲から出ることなく、説明した実施形態に対して幾つかの変更を行うことができ、また、別の実施形態も可能である。例えば、ここでの説明では、ログ距離比率LDRを参照しているが、ヒストグラムが、対数を用いない単純な距離比率などのような別の距離比率を用いて解釈される場合には、ログ距離比率の場合と類似の考え方を適用することができ、更には、ヒストグラムが、ログ距離比率の倍数や累乗を用いて解釈される場合にも、ログ距離比率の場合と類似の考え方を適用することができる。更に、距離比率の統計的分布をヒストグラムとは異なる表現で表すことに、何の妨げもない。その場合、ピアソンの検定は、選択された特定の表現と矛盾しない等価の検定に置き換えるべきである。更に、本発明の構成要素は、ヒストグラムのビンの幅が互いに異なっている場合でも、適用することができる。"