(57)【特許請求の範囲】
【請求項１】
第１画像と第２画像とを比較する方法であって、
前記第１画像の複数の第１キーポイントと前記第２画像の複数の第２キーポイントとを識別するステップと、
各第１キーポイントを、対応する第２キーポイントと関連付けして、対応するキーポイントマッチを形成するステップと、
第１キーポイントの各ペアについて、それらの間の距離を計算して、対応する第１長さを得るステップと、
第２キーポイントの各ペアについて、それらの間の距離を計算して、対応する第２長さを得るステップと、
複数の距離比率を計算するステップであって、各距離比率は、それぞれ、第１長さと第２長さとの間での選択されたものと、第２長さと第１長さとの間での対応する選択されたものとの間での長さ比率に基づく、ステップと、
前記複数の距離比率の統計的分布を計算するステップと、
前記第１画像および前記第２画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成するステップと、
前記複数の距離比率の前記統計的分布と、前記モデル関数とを比較するステップと、
前記比較に基づいて、前記第１画像が、前記第２画像に描写されたオブジェクトのビューを含むかを評価するステップと
を含む方法。
【請求項２】
請求項１に記載の方法であって、
前記複数の距離比率の前記分布を、複数の順序付けられたビンを有するヒストグラムの形にするステップであって、各ビンは距離比率の値のそれぞれの間隔に対応するものであり、前記ヒストグラムは、各ビンに関して、前記それぞれの間隔内に含まれる値を有する分布の距離比率の対応する数を列挙する、ステップと、
各ビンに関して、前記ビンにわたっての前記モデル関数の積分に対応する、対応するモデル確率を生成するステップと
を更に含み、
前記複数の距離比率の分布と前記モデル関数とを比較する前記ステップは、前記ヒストグラムと前記モデル確率とを比較するステップを含む、
方法。
【請求項３】
請求項２に記載の方法であって、前記ヒストグラムと前記モデル確率とを比較する前記ステップは、ピアソンのカイ２乗検定を行うステップを含む、方法。
【請求項４】
請求項１から３の何れかに記載の方法であって、前記距離比率を計算する前記ステップは、前記長さ比率の対数の計算を提供する、方法。
【請求項５】
請求項２、請求項３、または、請求項２もしくは３に従属する場合の請求項４に記載の方法であって、誤ったキーポイントマッチの数を推定するステップを更に含み、誤ったキーポイントマッチは、前記第１画像と前記第２画像とに描写された同じオブジェクトの同じポイントに対応しない第１キーポイントと第２キーポイントとにより形成され、誤ったキーポイントマッチの数を推定する前記ステップは、
重みパラメータを初期値へと初期化するステップと、
以下のａ）およびｂ）のステップ、
ａ）前記重みパラメータを用いて前記モデル確率を重み付けするステップと、
ｂ）前記重みパラメータの値を増加させるステップと
を少なくとも１つの重み付けされたモデル確率の値が、前記モデル確率に対応する前記ビンにおいて前記ヒストグラムにより列挙されている距離比率の数に到達するまで反復するステップと、
前記重みパラメータがとる最新の値に基づいて、誤ったキーポイントマッチの数を求めるステップと
を含む、方法。
【請求項６】
請求項５に記載の方法であって、正しいキーポイントマッチの数を推定するステップを更に含み、正しいキーポイントマッチは、前記第１画像と前記第２画像とに描写された同じオブジェクトの同じポイントに対応する第１キーポイントと第２キーポイントとにより形成されるものであり、正しいキーポイントマッチの数を推定する前記ステップは、第１キーポイントマッチの数に、前記重みパラメータがとる前記最新の値を１から減算した値の平方根と等しい項を乗算したものに基づく、方法。
【請求項７】
請求項６に記載の方法であって、
マトリックスを計算するステップであって、前記マトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、前記キーポイントマッチのそれぞれのペアの前記距離比率を含む前記ビンのところで前記ヒストグラムがとる値と、前記ビンに対応する重み付けされた前記モデル確率との間の差に対応する値を有する、ステップと、
前記マトリックスの主な固有ベクトルを見つけるステップと、
前記主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別するステップと
を更に含む方法。
【請求項８】
請求項７に記載の方法であって、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別する前記ステップは、最も大きな絶対値を有する前記固有ベクトルの前記エレメントを識別するステップを含む、方法。
【請求項９】
第１画像と第２画像とを比較するための装置であって、
前記第１画像の複数の第１キーポイントと前記第２画像の複数の第２キーポイントとを識別するように構成された第１識別ユニットと、
各第１キーポイントと、対応する第２キーポイントとを関連付けて、対応するキーポイントマッチを形成するように構成された関連付けユニットと、
第１キーポイントの各ペアについて、それらの間の距離を計算して、対応する第１長さを得るように構成された第１計算ユニットと、
第２キーポイントの各ペアについて、それらの間の距離を計算して、対応する第２長さを得るように構成された第２計算ユニットと、
複数の距離比率を計算するように構成された第３計算ユニットであって、各距離比率は、それぞれ、第１長さと第２長さとの間での選択されたものと、第２長さと第１長さとの間での対応する選択されたものとの間での長さ比率に基づく、第３計算ユニットと、
前記複数の距離比率の統計的分布を計算するように構成された第４計算ユニットと、
前記第１画像および前記第２画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成するように構成された第１生成ユニットと、
前記複数の距離比率の前記統計的分布と前記モデル関数とを比較するように構成された第１比較ユニットと、
前記比較に基づいて、前記第１画像が、前記第２画像に描写されたオブジェクトのビューを含むかを評価するように構成された評価ユニットと
を含む装置。
【請求項１０】
請求項９に記載の装置であって、
前記複数の距離比率の分布を、複数の順序付けられたビンを有するヒストグラムの形に配置するように構成された配置手段であって、各ビンは距離比率の値のそれぞれの間隔に対応し、前記ヒストグラムは、各ビンに関して、前記それぞれの間隔内に含まれる値を有する前記分布の距離比率の対応する数を列挙する、配置手段と、
各ビンについて、前記ビンにわたっての前記モデル関数の積分に対応する、対応するモデル確率を生成するように構成された第２生成ユニットと
を更に含み、
前記第１比較ユニットは、前記ヒストグラムと前記モデル確率とを比較するように構成された第２比較ユニットを含む、
装置。
【請求項１１】
請求項１０に記載の装置であって、
誤ったキーポイントマッチの数を推定するように構成された第１推定ユニットを更に含み、誤ったキーポイントマッチは、前記第１画像と前記第２画像とに描写された同じオブジェクトの同じポイントに対応しない第１キーポイントと第２キーポイントとにより形成され、前記第１推定ユニットは、
重みパラメータを初期値へと初期化するように構成された初期化ユニットと、
重み付けユニットであって、以下のａ）およびｂ）の動作、
ａ）前記重みパラメータを用いて前記モデル確率に重み付けすること、および
ｂ）前記重みパラメータの値を増加させること
を、少なくとも１つの重み付けされたモデル確率の値が、前記モデル確率に対応する前記ビンにおいて前記ヒストグラムにより列挙されている距離比率の数に到達するまで反復するように構成された重み付けユニットと、
前記重みパラメータがとる最新の値に基づいて、誤ったキーポイントマッチの数を求めるように構成された決定ユニットと
を含む、装置。
【請求項１２】
請求項１１に記載の装置であって、
正しいキーポイントマッチの数を推定するように構成された第２推定ユニットを更に含み、正しいキーポイントマッチは、前記第１画像と前記第２画像とに描写された同じオブジェクトの同じポイントに対応する第１キーポイントと第２キーポイントとにより形成され、前記第２推定ユニットは、第１キーポイントマッチの数に、前記重みパラメータがとる最新の値を１から減算した値の平方根と等しい項を乗算したものに基づいて、正しいキーポイントマッチの数を推定するように構成された、装置。
【請求項１３】
請求項１２に記載の装置であって、
マトリックスを計算するように構成された第５計算ユニットであって、前記マトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、前記キーポイントマッチのそれぞれのペアの前記距離比率を含む前記ビンにおいて前記ヒストグラムがとる値と、前記ビンに対応する重み付けされた前記モデル確率との間の差に対応する値を有する、第５計算ユニットと、
前記マトリックスの主な固有ベクトルを見つけるように構成された発見ユニットと、
前記主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいキーポイントマッチと考えられるかを識別するように構成された第２識別ユニットと
を更に含む装置。
【請求項１４】
クエリ画像を受け取り、前記画像における対応する第１キーポイントを識別するように構成されたキーポイント検出ユニットと、
前記第１キーポイントのローカルのアスペクトを、対応する第１ローカル記述子を通じて記述するように構成された特徴計算ユニットと、
複数の参照画像を記憶する参照データベースであって、各参照画像に関して、対応する第２キーポイントと、前記第２キーポイントの対応する第２ローカル記述子とを更に記憶する参照データベースと、
少なくとも１グループの参照画像のうちの各参照画像に関して、前記第１ローカル記述子と前記参照画像の前記第２ローカル記述子とを比較するように構成された特徴マッチングユニットであって、前記第１キーポイントと前記参照画像の前記第２キーポイントとを関連付けて、対応するキーポイントマッチの組を生成するように構成された特徴マッチングユニットと、
前記特徴マッチングユニットにより行われた比較に基づいて参照図のサブセットを選択するように構成された選択ユニットと、
前記クエリ画像と前記サブセットの１つの参照画像とを含む各ペアに関して、正しいキーポイントマッチの数を計算するように構成された最適化ユニットであって、請求項１２または請求項１３に記載の装置を含む最適化ユニットと
を含むシステム。
【請求項１５】
請求項１４に記載のシステムであって、ビジュアル・サーチ・サーバと、ネットワークを通じて前記ビジュアル・サーチ・サーバへクエリ画像を供給するように構成された複数の端末とを更に含み、
前記ビジュアル・サーチ・サーバは、前記キーポイント検出ユニットと、前記特徴計算ユニットと、前記参照データベースと、前記特徴マッチングユニットと、前記選択ユニットと、前記最適化ユニットとを含む、
システム。
【請求項１６】
請求項１４に記載のシステムであって、ビジュアル・サーチ・サーバと、ネットワークを通じて前記ビジュアル・サーチ・サーバへクエリ画像を供給するように構成された複数の端末とを更に含み、
前記ビジュアル・サーチ・サーバは、前記参照データベースと、前記特徴マッチングユニットと、前記選択ユニットと、前記最適化ユニットとを含み、
各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットとを含む、
システム。
【請求項１７】
請求項１４に記載のシステムであって、ビジュアル・サーチ・サーバと、ネットワークを通じて前記ビジュアル・サーチ・サーバとデータを交換するように構成された複数の端末とを更に含み、
前記ビジュアル・サーチ・サーバは前記参照データベースを含み、
各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットと、それぞれの特徴マッチングユニットと、それぞれの選択ユニットと、それぞれの最適化ユニットと、それぞれのローカル・データベースとを含み、
各端末は、前記参照データベースに記憶されている第２キーポイントと前記第２キーポイントの対応する第２ローカル記述子とのそれぞれのセットを、前記ビジュアル・サーチ・サーバから受け取るように構成され、
前記端末の前記ローカル・データベースは、受け取った第２キーポイントと第２ローカル記述子との前記セットを記憶するように構成され、記憶された第２キーポイントと第２ローカル記述子との前記セットは、少なくとも１グループの参照画像のうちの前記参照画像に対応する、
システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像分析の分野に関する。
【背景技術】
【０００２】
画像分析の分野では、一般的な動作において、２つの画像の双方が同じシーンや同じオブジェクトの少なくとも一部を含む場合、２つの画像の間の関係を見つけるために、２つの画像の比較を行う。
【０００３】
多数のアプリケーションの中では、画像の比較は、マルチカメラ・システムに属するビデオ・カメラの校正のため、ビデオ撮影の２つのフレーム間で生じる運動を評価するため、および画像（例えば、ピクチャ）内の物を認識するために、最も重要である。後者のアプリケーションは、現在、重要性が増してきていると考えられる。その理由は、ビジュアル・サーチ・エンジンと呼ばれるもので用いられるように特定的に設計されたオブジェクト認識アルゴリズム、即ち、ピクチャから開始して、そのピクチャ内に描写されているオブジェクト（１または複数）を識別し、その識別されたオブジェクト（１または複数）と関連する情報を提供することができる自動サービスの、最近の発展に起因する。このタイプの既知のサービスの例は、Ｇｏｏｇｌｅ（登録商標）  Ｇｏｇｇｌｅｓ（グーグル・ゴーグル）、Ｎｏｋｉａ（登録商標）  Ｐｏｉｎｔ＆Ｆｉｎｄ（ノキア・ポイント・アンド・ファインド）、ｋｏｏａｂａ  Ｓｍａｒｔ  Ｖｉｓｕａｌｓ（クアバ・スマート・ビジュアルズ）を含む。オブジェクト認識アルゴリズムは、第１画像、即ち、認識対象のオブジェクトを描写しており、専門用語で「クエリ画像（query image、問合せ画像）」と呼ばれる第１画像と、それぞれが個々の既知のオブジェクトを描写している複数の参照画像（reference image）との比較を行えるようにする。これにより、クエリ画像に描写されたオブジェクトと参照画像に描写されたオブジェクトとの間での比較を可能とする。
【０００４】
参照画像は、典型的には、適切な参照データベースに配される。データベースに含まれる参照画像の数が多いほど、行われる比較動作の数が多くなる。幾つかの場合、参照データベースは、非常に大きくなる場合があり、オブジェクト認識プロセスの効率に関して悪影響を与える。例えば、オブジェクト認識をオンライン・ショッピングのシナリオにおいて用いる場合、それぞれの参照画像（例えば、ブック・カバーや、ＤＶＤやＣＤのカバーのピクチャ）がオンライン・ストアで販売されている物品に対応するので、参照画像の数は数百万の個体数を超え得る。更に、そのような大量のデータを効率的に管理するために、比較動作は、十分な処理能力のある処理ユニットにより行われるべきである。
【０００５】
この１０年、オブジェクト認識を行うために必要な時間を低減するための様々なアルゴリズムが提案されてきた。それらのアルゴリズムは、クエリ画像に描写されたオブジェクトを含む候補である参照画像の数を、大きく低減するものである。
【０００６】
２つの画像間での比較の動作を行うための非常に効率的な方法は、第１画像において、専門用語でキーポイントと呼ばれるポイントの組を選択し、次に、その１組のキーポイントのそれぞれを、第２画像における対応するキーポイントとマッチングする。第１画像における何れのポイントをキーポイントとすべきかの選択は、ポイント自体を囲む画像の範囲のローカルの特徴（local feature）を考慮して行われる。この点に関しては、２００４年のInternational Journal of computer visionにおけるDavid G. Loweによる「Distinctive image features from scale-invariant keypoints（スケール不変キーポイントからの区別される画像特徴）」を参照されたい。
【０００７】
第１画像のキーポイントと第２画像の対応するキーポイントとの双方が、同じオブジェクト（２つの画像の双方に描写されている）の同じポイントに対応するという意味において、第１画像のキーポイントと第２画像の対応するキーポイントとのマッチング（matching）が正しい場合、そのようなキーポイントのマッチ（match）を「インライア（inlier）」という。
【０００８】
逆に、第１画像のキーポイントと第２画像の対応するキーポイントとの双方が、同じオブジェクトの同じポイントに対応しないという意味において、第１画像のキーポイントと第２画像の対応するキーポイントとのマッチングが正しくない場合、そのようなキーポイントのマッチを「アウトライア（outlier）」という。
【０００９】
従って、信頼性のある結果を得るために、アウトライアとインライアを区別できる手順が、キーポイントのマッチが決定された後に好都合に行われる。
【００１０】
このタイプの手順の幾つかの例は、従来技術において既に知られている。
【００１１】
最もよく使用される手順は、１９８１年６月のCommunications of the ACMの２４（６）の第３８１−３９５ページにおけるMartin A. FischlerおよびRobert C. Bollesによる「Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography（ランダム・サンプル・コンセンサス：画像分析および自動地図作成に対するアプリケーションと適合するモデルのパラダイム）」に開示されているＲＡＮＳＡＣアルゴリズムを使用する。しかし、このアルゴリズムは、反復手法に基づくので、時間を浪費する。
【００１２】
２０１０年１０月のInternational Conference on Image ProcessingにおけるSam S. Tsai、Davide Chen、Gabriel Takacs、Vijay Chandrasekhar、Ramakrishna Vedantham、Radek Grzeszczuk、Bernd Girodによる「Fast geometric re-ranking for image-based retrieval（画像ベースの検索のための高速の幾何学的な再整列）」に開示されているアルゴリズムと、国際特許出願のＷＯ２００９／１３０４５１に開示されているアルゴリズムとは、変換、回転、およびスケーリングが行われてもキーポイントの距離の間の比率が不変であるという事実に基づく。更に、このタイプのアルゴリズムは、２０１０年８月のInternational Conference on Pattern Recognitionの第８４２−８４５ページのZhipeng Wu、Qianqian Xu、Shuqiang Jiang、Qingming Huang、Peng Cui、およびLiang Liによる「Adding Affine Invariant Geometric Constraint for Partial-Duplicate Image Retrieval（部分的複製画像検索のためのアファイン不変量幾何学制約の付加）」、および２０１０年の20th International Conference on Pattern Recognitionの第１８４４−１８４７ページにおける Daniel FleckおよびZoran Duricによる「Using Local Affine Invariants to Improve Image Matching（画像のマッチングを改善するためのローカル・アファイン不変量の使用）」に開示されている。
【００１３】
更に、ＵＳ  ２０１０／０１３５５２７  Ａ１は、キーポイント・ベースの比較と認識ベースの色比較とを含む画像認識アルゴリズムを開示する。そのアルゴリズムを用いてターゲット画像を識別する方法は、処理デバイスにおいて、ターゲット画像に関連するデータを含む入力を受けるステップと、画像データベースから画像を検索することと、その画像が受け入れられるまで又は拒否されるまで、その画像を候補画像として指定することとを含む検索ステップを行うステップと、処理デバイスを用いて、ターゲット画像および候補画像に対して画像認識アルゴリズムを実行し、画像認識アルゴリズム出力を得ることを含む画像認識ステップを行うステップと、画像認識アルゴリズム出力が予め選択された範囲内にあるとき、候補画像をターゲット画像として受け入れることと、画像認識アルゴリズム出力が予め選択された範囲内にないとき、候補画像を拒否し、検索ステップ、画像認識ステップ、および比較ステップを反復することとを含む比較ステップを行うステップとを含む。
【００１４】
ＵＳ  ２０１０／０１８３２２９  Ａ１は、画像のマッチングのための方法、システム、およびコンピュータ・プログラム製品について言及している。マッチングされる画像は、特徴ポイント（feature point）と、特徴ポイントと関連する特徴ベクトル（feature vector）および向きとにより表される。最初に、特徴ベクトルを用いて、推測される対応（putative correspondence）を決定する。推測される対応のサブセットが選択され、そのサブセットの位相同形が決定される。推測される対応の位相同形サブセットは、運動推定（motion  estimation）モデルを確立するために使用される。向き整合性テスト（orientation consistency test）が、推測される対応と、決定された対応する運動推定変換とに対して行われて、実行不可能な変換を避けるようにする。向き整合性テストを満足させるマッチに対して、被写域（coverage）テストが行われる。画像のうちの１つの画像の重要部分を包含していない候補のマッチングは、拒否される。複数の画像が全てのテストの要求を満足させる場合、マッチングが低減する順に、最終的なマッチ画像が提供される。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
出願人は、オブジェクト認識サービスを実現させるための上記の既知のアプローチが、幾つかの欠点の影響を受けることを発見した。特に、これらのアプローチは、反復する手順に基づいたり、大量のデータの処理を必要としたりするので、時間を浪費する。
【００１６】
出願人は、時間の浪費および大量のデータの処理に関して、これらのアプローチを改善することに関する問題に取り組んだ。
【００１７】
特に、出願人は、データ処理に関して信頼性があり、且つ時間の浪費に関して良好な能力を有する、画像を比較する方法を提供することに関する問題に取り組んだ。
【課題を解決するための手段】
【００１８】
出願人は、キーポイントの組が第１画像（クエリ画像）上に生成され、そのキーポイントの組が第２画像（参照画像）上に生成される対応するキーポイントの組と関連付けされて、対応するキーポイントマッチの組を形成するところから始めることにより、本発明に従った画像を比較する方法が、主段階と２つの後続のオプション段階とを含むことができることを発見した。
【００１９】
主段階は、キーポイントマッチを生成した後に適用されるものであり、キーポイントマッチの統計的な処理を提供し、それに従って、幾何学的整合性テスト（geometric consistency test）を通じて、クエリ画像と参照画像とが同じオブジェクトを描写しているようであるか否かについての評価を行う。より詳細には、誤ったマッチ（アウトライア）の統計的分布を表すモデル関数を生成後、適合度テストを行い、参照画像が、クエリ画像に存在するオブジェクトのビュー（view）を含んでいるかを決定する。
【００２０】
肯定的結果が得られた場合、方法は、参照画像に描写されているオブジェクトと、クエリ画像に描写されているオブジェクトとの間の実際の相似性のランク付けに使用されるスコアを計算することができる。
【００２１】
第２段階は、キーポイントマッチの全ての組の中で幾つのキーポイントマッチがインライアであるかを評価することを可能にする。
【００２２】
この段階は、ビジュアル・サーチ・アプリケーションにおける精度を向上させるように、好都合に行うことができる。
【００２３】
第３段階は、何れのキーポイントマッチがインライアであり、何れのキーポイントマッチがアウトライアであるかを、特に識別することを可能にする。
【００２４】
このような段階は、拡張現実（augmented reality）などのような幾つかの特定のアプリケーションにおいて、好都合に行うことができる。
【００２５】
より詳細には、本発明の１つの態様によると、本発明は、第１画像と第２画像とを比較する方法と関連する。方法は、第１画像の複数の第１キーポイントと第２画像の複数の第２キーポイントとを識別し、各第１キーポイントと、対応する第２キーポイントとを関連付けし、対応するキーポイントマッチを形成することを含む。第１キーポイントの各ペアに関して、方法は更に、それらの間の距離を計算して、対応する第１長さを得ることを含む。同様に、第２キーポイントの各ペアに関して、方法は、それらの間の距離を計算して、対応する第２長さを求めることを含む。方法は更に、複数の距離比率を計算することを含み、それぞれの距離比率は、第１長さと第２長さとの間での選択されたものと、第２長さと第１長さとの間での対応する選択されたものとの間での、それぞれの、長さ比率に基づく。方法は更に、複数の距離比率の統計的分布を計算することと、第１画像および第２画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成することとを含む。方法は、前記の複数の距離比率の統計的分布と、前記のモデル関数とを比較することと、前記の比較に基づいて、第１画像が、第２画像に描写されたオブジェクトのビューを含むかを評価することとを含む。
【００２６】
本発明の１つの実施形態に従うと、方法は、複数の距離比率の分布を、複数の順序付けられたビン（bin）を有するヒストグラムの形に配置することを含み、各ビンは距離比率値のそれぞれの間隔に対応する。ヒストグラムは、各ビンに関して、それぞれの間隔内に含まれる値を有する分布の距離比率の対応する数を列挙する。各ビンに関して、方法は更に、前記のビンにわたってのモデル関数の積分に対応する、対応するモデル確率を生成することを含む。前記の、複数の距離比率の分布と前記のモデル関数とを比較することは、ヒストグラムとモデル確率とを比較することを含む。
【００２７】
好適には、前記のヒストグラムとモデル確率とを比較することは、ピアソンのカイ２乗検定を行うことを含む。
【００２８】
好都合なことに、前記の距離比率を計算することは、長さ比率の対数を計算することを提供する。
【００２９】
本発明の１つの実施形態に従うと、方法は更に、誤ったキーポイントマッチの数を推定することを含む（誤ったキーポイントマッチは、第１画像と第２画像とに描写された同じオブジェクトの同じポイントに対応しない第１キーポイントと第２キーポイントとにより形成される）。前記の誤ったキーポイントマッチの数を推定することは、重みパラメータを初期値へと初期化することと、次のａ）およびｂ）を反復することと、即ち、ａ）重みパラメータを用いてモデル確率に重み付けすること、およびｂ）重みパラメータの値を増加させることを、少なくとも１つの重み付けされたモデル確率の値が、前記のモデル確率に対応するビンにおいてヒストグラムにより列挙されている距離比率の数に到達するまで反復することとを含む。方法は更に、重みパラメータがとる最新の値に基づいて、誤ったキーポイントマッチの数を求めることを含む。
【００３０】
本発明の１つの実施形態に従うと、方法は更に、正しいキーポイントマッチの数を推定することを含む（正しいキーポイントマッチは、第１画像と第２画像とに描写された同じオブジェクトの同じポイントに対応する第１キーポイントと第２キーポイントとにより形成される）。前記の正しいキーポイントマッチの数を推定することは、第１キーポイントマッチの数に、重みパラメータがとる最新の値を１から減算した値の平方根と等しい項を、乗算したものに基づく。
【００３１】
本発明の更なる実施形態に従うと、方法は更に、マトリックスを計算することを含み、そのマトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、キーポイントマッチのそれぞれのペアの距離比率を含むビンのところでヒストグラムがとる値と、前記のビンに対応する重み付けされたモデル確率（weighted model probability）との間の差に対応する値を有する。方法は更に、マトリックスの主な固有ベクトルを見つけることと、前記の主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別することとを含む。
【００３２】
前記の、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別することは、最も大きな絶対値を有する固有ベクトルのエレメントを識別することを含む。
【００３３】
本発明の１つの態様では、第１画像と第２画像とを比較するための装置を提供する。装置は、第１画像の複数の第１キーポイントと第２画像の複数の第２キーポイントとを識別するように構成される第１識別ユニットと、対応するキーポイントマッチを形成するために、各第１キーポイントと、対応する第２キーポイントとを関連付けように構成される関連付けユニットとを含む。第１計算ユニットは、第１キーポイントの各ペアに対して、それらの間の距離を計算して、対応する第１長さを得るように構成され、第２計算ユニットは、第２キーポイントの各ペアに対して、それらの間の距離を計算して、対応する第２長さを得るように構成される。装置は更に、複数の距離比率を計算するように構成された第３計算ユニットを含み、各距離比率は、それぞれ、第１長さと第２長さとの間での選択されたものと、第２長さと第１長さとの間での対応する選択されたものとの間での長さ比率に基づく。装置は更に、複数の距離比率の統計的分布を計算するように構成された第４計算ユニットと、第１画像および第２画像のキーポイントのランダムな選択に対応する更なる距離比率の統計的分布を表すモデル関数を生成するように構成された第１生成ユニットとを含む。装置は、前記の複数の距離比率の統計的分布と前記のモデル関数とを比較するように構成された第１比較ユニットと、前記の比較に基づいて、第１画像が、第２画像に描写されたオブジェクトのビューを含むかを評価するように構成される評価ユニットとを含む。
【００３４】
本発明の１つの実施形態に従うと、装置は更に、複数の距離比率の分布を、複数の順序付けられたビンを有するヒストグラムの形に配置するよう構成された配置手段（arranging means）を含み、各ビンは距離比率値のそれぞれの間隔に対応し。ヒストグラムは、各ビンに関して、それぞれの間隔内に含まれる値を有する分布の距離比率の対応する数を列挙する。装置は更に、各ビンに関して、前記のビンにわたってのモデル関数の積分に対応する、対応するモデル確率を生成するように構成された第２生成ユニットを含む。前記の第１比較ユニットは、ヒストグラムとモデル確率とを比較するように構成された第２比較ユニットを含む。
【００３５】
本発明の更なる実施形態に従うと、装置は、誤ったキーポイントマッチの数を推定するように構成される第１推定ユニットを含み、誤ったキーポイントマッチは、第１画像と第２画像とに描写された同じオブジェクトの同じポイントに対応しない第１キーポイントと第２キーポイントとにより形成される。第１推定ユニットは、重みパラメータを初期値へと初期化するように構成された初期化ユニットと、ａ）重みパラメータを用いてモデル確率を重み付けする操作と、ｂ）重みパラメータの値を増加させる操作とを、少なくとも１つの重み付けされたモデル確率の値が、前記のモデル確率に対応するビンにおいてヒストグラムにより列挙されている距離比率の数に到達するまで反復するように構成された重み付けユニットとを含む。装置は更に、重みパラメータがとる最新の値に基づいて、誤ったキーポイントマッチの数を求めるように構成された決定ユニットを含む。
【００３６】
好ましくは、装置は更に、正しいキーポイントマッチの数を推定するように構成された第２推定ユニットを含み、前記の第２推定ユニットは、第１キーポイントマッチの数に、重みパラメータがとる最新の値を１から減算した値の平方根と等しい項を乗算したものに基づいて、正しいキーポイントマッチの数を推定するように構成される。
【００３７】
本発明の更なる実施形態に従うと、装置は更に、マトリックスを計算するように構成された第５計算ユニットを含み、そのマトリックスの各エレメントは、キーポイントマッチのそれぞれのペアに対応し、且つ、キーポイントマッチのそれぞれのペアの距離比率を含むビンにおいてヒストグラムがとる値と、前記のビンに対応する重み付けされたモデル確率（weighted model probability）との間の差に対応する値を有する。装置は更に、マトリックスの主な固有ベクトルを見つけるように構成された発見ユニットと、前記の主な固有ベクトルに基づいて、何れのキーポイントマッチが最も正しいと考えられるキーポイントマッチであるかを識別するように構成された第２識別ユニットとを含む。
【００３８】
本発明の更なる態様では、クエリ画像を受け取り、前記の画像における対応する第１キーポイントを識別するように構成されたキーポイント検出ユニットと、前記の第１キーポイントのローカルのアスペクトを、対応する第１ローカル記述子を通じて記述するように構成された特徴計算ユニットとを含むシステムを提供する。システムは更に、複数の参照画像を記憶する参照データベースを含み、各参照画像に関して、参照データベースは更に、対応する第２キーポイントと、それら第２キーポイントの対応する第２ローカル記述子とを記憶する。システムは更に、少なくとも１グループの参照画像のうちの各参照画像に関して、第１ローカル記述子と前記の参照画像の第２ローカル記述子とを比較するように構成され、それに従って、第１キーポイントと前記の参照画像の第２キーポイントとを関連付けて、対応するキーポイントマッチの組を生成するように構成された特徴マッチングユニットを含む。システムは更に、特徴マッチングユニットにより行われた比較に基づいて参照図のサブセットを選択するように構成された選択ユニットと、クエリ画像とサブセットの参照画像とを含む各ペアに関して、正しいキーポイントマッチの数を計算するように構成された最適化ユニットとを含む。
【００３９】
本発明の１つの実施形態に従うと、システムは更に、ビジュアル・サーチ・サーバと、ネットワークを通じてビジュアル・サーチ・サーバとデータを交換するように構成された複数の端末とを含む。
【００４０】
本発明の１つの実施形態に従うと、ビジュアル・サーチ・サーバは、キーポイント検出ユニットと、特徴計算ユニットと、参照データベースと、特徴マッチングユニットと、選択ユニットと、最適化ユニットとを含む。
【００４１】
本発明の別の実施形態に従うと、ビジュアル・サーチ・サーバは、参照データベースと、特徴マッチングユニットと、選択ユニットと、最適化ユニットとを含み、各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットとを含む。
【００４２】
本発明の更に別の実施形態に従うと、ビジュアル・サーチ・サーバは参照データベースを含み、各端末は、それぞれのキーポイント検出ユニットと、それぞれの特徴計算ユニットと、それぞれの特徴マッチングユニットと、それぞれの選択ユニットと、それぞれの最適化ユニットと、それぞれのローカル・データベースとを含む。各端末は、参照データベースに記憶された、第２キーポイントと、第２キーポイントの対応する第２ローカル記述子とのそれぞれのセットを、ビジュアル・サーチ・サーバから受け取るように構成され、端末のローカル・データベースは、受け取った前記の第２キーポイントと第２ローカル記述子とのセットを記憶するように構成され、前記の記憶された第２キーポイントと第２ローカル記述子とのセットは、少なくとも１グループの参照画像のうちの参照画像に対応する。
【００４３】
本発明のこれらおよび他の特徴および利点は、例示であり制限を加えるためのものではない幾つかの実施形態についての以下の説明を、添付の図面と関連させて読むことにより、明らかになる。
【図面の簡単な説明】
【００４４】
【図１Ａ】図１Ａは、２つの画像のキーポイントが互いに関連付けされてキーポイントマッチを形成する例を示す。
【図１Ｂ】図１Ｂは、図１Ａの例を示すが、インライアのみが示されている。
【図１Ｃ】図１Ｃは、図１Ａの例に対応するＬＤＲヒストグラムを示す。
【図２】図２は、本発明の１つの実施形態に従ったアウトライア・モデル関数の形状を示す。
【図３Ａ】図３Ａ〜図３Ｆは、チューリッヒ・ビルディング・イメージ・データベースから取り出した画像のペアから生成されるＬＤＲヒストグラムの幾つかの例を示す。
【図３Ｂ】図３Ａ〜図３Ｆは、チューリッヒ・ビルディング・イメージ・データベースから取り出した画像のペアから生成されるＬＤＲヒストグラムの幾つかの例を示す。
【図３Ｃ】図３Ａ〜図３Ｆは、チューリッヒ・ビルディング・イメージ・データベースから取り出した画像のペアから生成されるＬＤＲヒストグラムの幾つかの例を示す。
【図３Ｄ】図３Ａ〜図３Ｆは、チューリッヒ・ビルディング・イメージ・データベースから取り出した画像のペアから生成されるＬＤＲヒストグラムの幾つかの例を示す。
【図３Ｅ】図３Ａ〜図３Ｆは、チューリッヒ・ビルディング・イメージ・データベースから取り出した画像のペアから生成されるＬＤＲヒストグラムの幾つかの例を示す。
【図３Ｆ】図３Ａ〜図３Ｆは、チューリッヒ・ビルディング・イメージ・データベースから取り出した画像のペアから生成されるＬＤＲヒストグラムの幾つかの例を示す。
【図４】図４は、クエリ画像と参照画像とが、同じ平面状オブジェクトを、大きく異なる角度から見て描写している例示的なケースを示す。
【図５Ａ】図５Ａと図５Ｂとは、２つの例示的なケースを示すものであり、大きくは異ならない角度から見られているほぼ平面状のオブジェクトが示されている。
【図５Ｂ】図５Ａと図５Ｂとは、２つの例示的なケースを示すものであり、大きくは異ならない角度から見られているほぼ平面状のオブジェクトが示されている。
【図６】図６は、本発明の１つの実施形態に従った、インライアの数を推定するためにモデル確率をスケーリングする例を示す。
【図７Ａ】図７Ａは、本発明の１つの実施形態に従った方法の第１段階の主なステップを示すフローチャートである。
【図７Ｂ】図７Ｂは、本発明の１つの実施形態に従った方法の第２段階の主なステップを示すフローチャートである。
【図７Ｃ】図７Ｃは、本発明の１つの実施形態に従った方法の第３段階の主なステップを示すフローチャートである。
【図８】図８は、可能なシナリオを概略的に示すものであり、このシナリオにおいて、本発明の１つの実施形態に従った方法を用いてビジュアル・サーチ・サービスを実現できる。
【図９Ａ】図９Ａは、本発明の１つの実施形態に従ったビジュアル・サーチ・サービスを実現するシステムを示す。
【図９Ｂ】図９Ｂは、本発明の別の実施形態に従ったビジュアル・サーチ・サービスを実現するシステムを示す。
【図９Ｃ】図９Ｃは、本発明の更に別の実施形態に従ったビジュアル・サーチ・サービスを実現するシステムを示す。
【図１０】図１０は、本発明の１つの実施形態に従った自動的ビデオ・カメラ校正方法の主なステップを示すフローチャートである。
【発明を実施するための形態】
【００４５】
既に述べたように、２つの画像の比較は、第１画像のキーポイントと第２画像の対応するキーポイントとのマッチングのために行われる。キーポイントマッチは、２つの画像の対応するキーポイントが、同じオブジェクト（２つの画像の双方に描写）の同じポイントに対応する場合に、正しい（インライアである）と言われ、逆に、キーポイントマッチは、２つのキーポイントが、同じオブジェクトの同じポイントに対応しない場合に、誤り（アウトライアである）と言われる。図１Ａに示す例では、各画像は同じオブジェクト（教会）のピクチャであり、それぞれのキーポイントマッチは、それぞれの実線で示されている。図１Ａの例示的ケースで示されているキーポイントマッチは、インライアとアウトライアとの双方を含んでいる。同じ例示的ケースにおいてアウトライアを除いたものを、図１Ｂに示している。
【００４６】
以下の説明において、新規な画像比較方法を提示する。ここで提案する方法は、クエリ画像または単にクエリと呼ばれる第１画像上で生成されたキーポイントの組と、参照画像と呼ばれる第２画像上で生成された対応するキーポイントの組とを関連付けて、対応するキーポイントマッチの組を形成するようにしたところから開始するものであり、主段階と２つの後続するオプション段階とを含む。
【００４７】
１）  主段階は、キーポイントマッチを生成した後に適用されるものであり、キーポイントマッチを統計的に処理し、それに従って、幾何学的整合性検査を通じて、クエリ画像と参照画像とが同じオブジェクトを描写しているようであるか否かについての評価を行う。より詳細には、誤ったマッチ（アウトライア）の確率的モデルを生成後、適合度テストを行い、参照画像が、クエリ画像に存在するオブジェクトのビューを含んでいるかを決定する。肯定的結果が得られた場合、方法は、参照画像に描写されているオブジェクトと、クエリ画像に描写されているオブジェクトとの間の実際の相似性のランク付けに使用されるスコアを計算することができる。
【００４８】
２）  第２段階（オプション）は、キーポイントマッチの全ての組の中で幾つのキーポイントマッチがインライアであるかを評価することを可能にする。この段階は、ビジュアル・サーチ・アプリケーションにおける精度を向上させるように、好都合に行うことができる。
【００４９】
３）  第３段階（これもオプション）は、何れのキーポイントマッチがインライアであり、何れのキーポイントマッチがアウトライアであるかを、特定的に識別することを可能にする。このような段階は、拡張現実などのような幾つかの特定のアプリケーションにおいて、好都合に行うことができる。
【００５０】
この説明のセクション１では、この方法で用いる特定の統計の特性と、ログ距離比率（log distance ratio）の概念とを紹介するが、これらの双方とも、誤ったマッチおよび正しいマッチと関連する。後続の３つのセクション（セクション２〜４）では、提案される方法の３つの段階の数学的および統計的な面について開示する。セクション５は、方法の３つの段階の主なステップを開示する。最後のセクション（セクション６）は、提案される方法の例示的な応用に関するものである。
【００５１】
セクション１  −距離の比率の統計
Ｎ個のマッチングされたキーポイントの組を考慮する。
【００５２】
(x1,y1),・・・(xi,yi),・・・(xN,yN)      （１）
上記の組において、ｘｉは、クエリ画像における第ｉのキーポイントの座標を含み、ｙｉは、参照画像におけるマッチングされるキーポイントの座標を含む。ペア（ｘｉ，ｙｉ）は、２つのキーポイントが正しくマッチングされている場合、インライアと呼ばれる。逆に、キーポイントが誤ってマッチングされている場合、ペアはアウトライアと呼ばれる。
【００５３】
提案される方法は、上記で引用したＴｓａｉその他による論文で提案されているログ距離比率（省略形ではＬＤＲ）と呼ばれるものを用いる。
【００５４】
【数１】
0005734460.tif 000002
【００５５】
キーポイントは別個である必要があり、従って、下記のような関係である。
ｘｉ≠ｘｊ，ｙｉ≠ｙｊ
また、ＬＤＲは、ｉ＝ｊの場合には定義されない。ＬＤＲは、長さの比率の関数であり、相似性に関しては不変である。対数演算子が存在しているので、クエリ画像が参照画像と交換される場合（ｘがｙになる場合、またはその逆の場合）、ＬＤＲは符号を逆にする。
【００５６】
Ｎ個のマッチングされたキーポイント（ｘｉ，ｙｉ）の組は、クエリ画像上のＮ個のキーポイントｘｉと参照画像上のＮ個の対応するキーポイントｙｉとを含むものであり、そのＮ個のマッチングされたキーポイントの組が与えられた場合、「ｎ＝Ｎ（Ｎ−１）／２」であるｎ個の別個のログ距離比率が存在する。そのようなログ距離比率の統計的分布は、対応するヒストグラムの形で表すことができ、それをここでは「ＬＤＲヒストグラム」という。ＬＤＲヒストグラムは、アレイ「ｈ＝［ｈ１・・・ｈｋ］Ｔ」により表すことができる。ｈは、Ｋ個の予め定めた間隔Ｔ１，・・・，ＴＫのそれぞれの間隔内に含まれる観察されたログ距離比率を計数しているときに生じる頻度のアレイであり、以下では、予め定めた間隔をビンと呼ぶ。例えば、ビン（bins、複数のビン）は、下記の例のように、幅が０．２であり、下の値が−２．５であり、上の値が２．５である２５の間隔とすることができる。
【００５７】
T1=[-2.5,-2.3>, T2=[-2.3,-2.1>, ・・・ T25=[2.3,2.5]
図１Ａの場合のＬＤＲヒストグラムの例は、図１Ｃに示している。
【００５８】
ＬＤＲの主な利点は、インライアのペアとアウトライアのペアとに対して異なる挙動を示すことである。多くの画像変換（インライアの挙動を決定する）に関して、ＬＤＲは、間隔に限定される。アウトライアに関しては、ＬＤＲは、そのような間隔の外へ延び、また、適合度検定に使用できる特有の確率密度関数を有する。
【００５９】
ＬＤＲは、２つの総称的なキーポイント・ペア、即ち、（ｘｉ，ｙｉ）と（ｘｊ，ｙｊ）の関数である。３つの状態が発生し得るが、それらは、双方のペアがアウトライアである状態と、双方がインライアである状態と、一方のペアがインライアであり他方のペアがアウトライアである状態とである。
【００６０】
１．１  双方のペアがアウトライアのときのＬＤＲ
マッチングプロセスは、画像中のシーンの幾何図形的配列の何れの知識によっても制限されない。なぜなら、そのような知識は、マッチングが行われる前には使用できないからである。たとえ２つの画像が同じオブジェクトを示す場合でも、誤ったマッチを妨げる機構はない。２つの画像が、同じまたは非常に似たオブジェクトを示さない場合、何れのマッチングも誤りであると考えられる。
【００６１】
たとえマッチングプロセスが決定性（deterministic、静的）であるとしても、誤ってマッチングされたキーポイントの位置は予測できない。一般に、アウトライアの幾何学パターンを発見するのは不可能であり、そのようなパターンを導き出せる優れた原理はない。従って、誤ったマッチングはランダム・プロセスとして考慮され、アウトライアの挙動は、アウトライア・モデル関数と呼ばれる適切な密度関数を通じてモデル化される。
【００６２】
「アウトライア・モデル関数の定義」。ＡおよびＢが矩形であるとする。ｘｉ，ｘｊ∈Ａおよびｙｉ，ｙｊ∈Ｂが、ランダムに描かれたポイントであり、確率変数（random variable）Ｘｉ，ＸｊおよびＹｉ，Ｙｊに対応するものとする。ランダムな変数ＣをＬＤＲとする。
【００６３】
Ｃ＝ｌｄｒ（Ｘｉ，Ｘｊ，Ｙｉ，Ｙｊ）
アウトライア・モデル関数は、Ｃに対する確率密度関数ｆｃ（ｃ）である。
【００６４】
アウトライア・モデル関数は、正規（normal）と一様（uniform）との２つのタイプのキーポイント分布に関して表すことができる。
【００６５】
「正規に分布されたキーポイント座標」。キーポイントが正規に分布しているという仮定は、アウトライア・モデル関数の定式化を簡単なものとし、これは実際のケースに対しての良い近似である。
【００６６】
クエリ画像のキーポイントは独立同分布（independent and identically distributed）（ｉ．ｉ．ｄ．）であると想定され、平均μおよび分散（１／２）Ｉを有し、正規に分布する確率変数Ｘとして挙動する。
【００６７】
【数２】
0005734460.tif 000003
【００６８】
座標は適切にスケーリングされ、それにより、キーポイントは画像全体に分布していると仮定される（分散は、水平方向および垂直方向において同じであることに留意されたい）。従って、２つのキーポイントの間の差は正規分布となる。
【００６９】
Ｘｉ−Ｘｊ〜  Ｎ（０，Ｉ）；  ｉ≠ｊ    （４）
参照画像のキーポイント｛Ｙｎ｝が｛Ｘｎ｝と同じ統計を有し、キーポイントＸｎがキーポイントＹｎとマッチングされると想定する。その場合、平方の距離比率（squared distance ratio）は、（２，２）の自由度のＦ分布を有する。
【００７０】
【数３】
0005734460.tif 000004
【００７１】
これは、例えば、Prentice-Hallの出版のR.J.LarsenおよびM.L.Marxによる「An introduction to Mathematical Statistics and its Applications（数学的統計およびその応用の概論）」１８９６年、第２版の第３３８ページに示されている。
【００７２】
確率密度関数Ｆ（２，２）は下記のとおりである。
【００７３】
【数４】
0005734460.tif 000005
【００７４】
上記の式では、簡素化のために、式（５）の確率変数「Ｒｉｊ２」をＳに置き換えている。ログ距離比率（平方の距離比率ではない）が考慮されているので、平方根および対数が確率変数「Ｓ＝Ｒｉｊ２」に適用される。更に、２つの画像のサイズの違いや２つの画像におけるキーポイントの広がりの違いを考慮に入れるために、関数は、２つの画像におけるキーポイントの標準偏差のプロポーション（proportion）に対応するパラメータａ、即ち、以下の式に示すパラメータａを確率変数に乗算することにより、そのようなケースに対しての拡張が行われる。
【００７５】
【数５】
0005734460.tif 000006
【００７６】
Ｆ（２，２）のｐ．ｆ．ｄ．に対するこれらの変更により、下記のアウトライア・モデル関数が導き出される。
【００７７】
「アウトライア・モデル関数」。２つの画像がランダムなキーポイント｛Ｘｎ｝および｛Ｙｎ｝を有するものとし、それら全てが二変量正規分布を有し、第１画像において分散σｘ２、第２画像において分散σｙ２を有するものとする。ａ２を分散のプロポーションとする。
【００７８】
【数６】
0005734460.tif 000007
【００７９】
出願人は、ログ距離比率が確率密度関数を有すると判断した。
【００８０】
【数７】
0005734460.tif 000008
【００８１】
式７のアウトライア・モデル関数は、提案する方法の基礎である。アウトライア・モデル関数の形は、図２に示されている。このアウトライア・モデル関数が矩形画像のアスペクト比を考慮しないことに、留意すべきである。なぜなら、水平の分散と垂直の分散とが同じと想定されているからである。
【００８２】
図３Ａ〜図３Ｆは幾つかの例を示し、それぞれが、チューリッヒ・ビルディング・イメージ・データベース（Zurich Building Image Database）（１００５の画像を含み、２０１のビルディングのそれぞれについての５つのビューを含む）からの画像の個々のペア（クエリ画像−参照画像）を示す。キーポイントは円で示し、ラインは、別の画像におけるマッチングされるキーポイントの位置を指す。それぞれの画像ペアに関して、ＬＤＲヒストグラムと、式７の定式化での、対応するアウトライア・モデル関数とが示されている。これらの画像は異なるビルディングを示すので、全てのキーポイントマッチをアウトライアと考える必要があることに、留意されたい。これらの例から、アウトライア・モデル関数は、全てのマッチがアウトライアであるときには常にＬＤＲヒストグラムにかなり近いものとなる、ということを観察することができる。
【００８３】
１．２  双方のペアがインライアのときのＬＤＲ
一般に、全てのキーポイントマッチがインライアである場合のＬＤＲヒストグラムは、アウトライアに対するＬＤＲヒストグラムと大きく異なることが多い。多数の実際的なケースにおいて、インライアのみに対してのＬＤＲヒストグラムは、アウトライアのみに対してのＬＤＲヒストグラムよりも狭い。即ち、インライアのみに対してのＬＤＲヒストグラムは、アウトライアのＬＤＲヒストグラムがゼロではない幾つかのビン（特に、横方向のビン）にわたって、ゼロとなる。
【００８４】
２つの画像における関連付けされたキーポイントｘｉおよびｙｉは、見られているオブジェクト上の同じポイントのマッピングを通じて関連するので、確率的モデリングを用いる代わりに、ＬＤＲヒストグラムの上界および下界を考慮することが好都合である。
【００８５】
ここで行われた研究は、３Ｄシーンにおける平面上のポイントに限定される。なぜなら、深さの変化が限定されたオブジェクトを認識することを、主に考えているからである。平面は、ビルディングや本や看板などのような、画像内の多くの対象となるオブジェクトの可視部分を近似したものとして表す。
【００８６】
平面上の部分にある２つの画像は、ホモグラフィ（homography）Ｈを通じて関連する。
【００８７】
【数８】
0005734460.tif 000009
【００８８】
ｙ＝ｈ／ｄ      （９）
上記の式において、ｘおよびｙは２つの画像における同じ点の投射の座標である。従って、同じ平面上のインライアのペアは、同じホモグラフィを通じて関連する。アファイン変換および一般的ホモグラフィに対してのＬＤＲヒストグラムの特徴を、ここで開示する。
【００８９】
「アファイン変換」。アファイン変換は、下記のようなホモグラフィの特別のケースである。
【００９０】
【数９】
0005734460.tif 000010
【００９１】
上記の式に関して、「ｙｎ＝Ｋｘｎ＋ｔ」である。
【００９２】
距離比率は、「２×２マトリックスＫ」の特異値（singular value）により与えられる間隔に制限される。
【００９３】
【数１０】
0005734460.tif 000011
【００９４】
この場合、ＬＤＲは下記の間隔にある。
【００９５】
ldr(xi,xj,yi,yj)∈[-lnσmax,-lnσmin]      （１０）
従って、ＬＤＲヒストグラムの非ゼロ部分の幅は、アファイン変換がオブジェクトを変形させる度合いに応じたものとなる。相似変換（similarity transformation）に関しては、２つの特異値は等しく、従って、ＬＤＲヒストグラムは、ゼロではないビンを１つのみ有する。アファイン変換により、長さが、最小限度として１／３まで縮められ、最大限度として２倍まで伸ばされる場合、２つの特異値は１／３と２とであり、ＬＤＲの非ゼロ値に対する間隔は下記のようになる。
【００９６】
【数１１】
0005734460.tif 000012
【００９７】
「ホモグラフィ」。ｘｉ、ｘｊとｙｉ、ｙｊとが、式８および式９のように、下記のホモグラフィを通じて関連するものとする。
【００９８】
【数１２】
0005734460.tif 000013
【００９９】
この場合、ＬＤＲも下記の間隔に制限される。
【０１００】
ldr(xi,xj,yi,yj)∈[-lnb,-lna]      （１１）
上記の式においてａは最大数であり、ｂは最小であり、下記のような関係である。
【０１０１】
【数１３】
0005734460.tif 000014
【０１０２】
ホモグラフィの最も実際的なケースでは、この間隔は、アウトライアに対するＬＤＲのヒストグラムに関しては、用いられる機構の性質に大きく影響されるので、狭いものとなる。ＳＩＦＴ（Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ）やＳＵＲＦ（Ｓｐｅｅｄｅｄ  Ｕｐ  Ｒｏｂｕｓｔ  Ｆｅｔｕｒｅｓ）のような機構は、相似変換に対しては不変であるが、アファイン変換に対してはそうではなく、特にホモグラフィに対してはそうではない。これは、遠近法的な歪みが強くて[-lnb,-lna]が理論的に広くなり得る場合に、極端なＬＤＲ値を生成し得るキーポイントは関連付けされないことを意味する。なぜなら、それらのキーポイントの特徴は、異なる記述子を有するからである。従って、正しく関連付けされたキーポイントに関するインライアのヒストグラムは、相対的に狭い間隔に留まることになるであろう。
【０１０３】
図４は、クエリ画像と参照画像とが、大きく異なる角度（この例では−７５度と０度）から見た同じ平面オブジェクト（矩形）を描写する例示的ケースを示す。図４の下部の図は、前記の画像ペアから計算されたアウトライア・モデル関数とＬＤＲヒストグラムとを示す。
【０１０４】
図５Ａおよび図５Ｂは、大きくは異ならない角度から見られているほぼ平面状のオブジェクト（ビルディングの面）が示された２つの例示的ケースを示す。図５Ａおよび図５Ｂの下部の図は、対応するＬＤＲヒストグラムとアウトライア・モデル関数とを示す。
【０１０５】
１．３  双方のタイプのペアのときのＬＤＲ
第３の代替例は、ペアｘｉ、ｙｉがインライアであり、ペアｘｊ、ｙｊがアウトライアである場合（または、その逆の場合）のためのものである。この場合も、１つの画像のキーポイントがランダムに分布していると仮定する。なぜなら、未知の画像に含まれるキーポイントの位置を制限する幾何学的なパターンや規則を前もって知ることができないからである。
【０１０６】
従って、それぞれのキーポイントは、式３のように、例えば、正規分布を用いて、確率変数により表すことができる。２つのキーポイントの間の差ベクトルは、式４における場合のようにモデル化される。なぜなら、１つはインライアとして取られ、別の１つはアウトライアとしてとられ、それらの間には相関が無いからである。
【０１０７】
しかし、式５のＦ分布は正確に維持できない。なぜなら、Ｆ分布の仮定とは異なって、分子と分母とは独立していないからである。インライアとアウトライアとのペアの場合のキーポイントは下記のようである。
【０１０８】
（xi,yi），（xj,π(xj)）
上記の式において、πは、１つの画像のインライアのキーポイントの、別の画像へのマッピングである（未知であるにもかかわらず）。この場合における平方の距離比率を表す確率変数は下記のとおりである。
【０１０９】
【数１４】
0005734460.tif 000015
【０１１０】
上記の式において、分子と分母とは明らかに独立していない。なぜなら、双方ともＸｊの関数だからである。式１３における変数の確率密度を見つけるのは非常に難しいが、ここで提案される方法を考慮するかぎり、見つける必要はないであろう。同じモデル確率、従って、式７のアウトライア・モデル関数を用いて、これら２つのケース（インライア／アウトライア・ペアではなく双方がインライアのペア）に対してのＬＤＲのヒストグラムを、僅かな誤差はあるがモデル化することが可能であることを、経験により仮定することができる。
【０１１１】
セクション２  −  マッチングされない画像の拒絶（提案される方法の第１段階）
ＬＤＲヒストグラムは、画像（クエリ画像）において見ることができるオブジェクトを識別するために用いることができる。従って、「識別（identification）」は、クエリ画像に描写されているオブジェクトのビューを含む参照画像を、参照コレクション（参照データベース）の参照画像の中から見つけることを意味する。提案される方法の第１段階は、クエリ画像と参照画像との間でのインライアのキーポイント・ペアを明確に検出することを必要とせずに、オブジェクトを識別することを可能にする。
【０１１２】
提案される方法の第１段階は幾何学的整合性テストであり、これは、以下の仮定
Ｈ０：参照画像はクエリに対応しない、
Ｈ１：参照画像はクエリに対応する
の間での二者択一を行うためのものである。
【０１１３】
Ｈ０の仮定は、物事の予期される状態を表すものであり、ほぼ全ての参照画像に、クエリにおけるオブジェクトのビューが含まれていないことが知られている。Ｈ０を拒絶してＨ１を受け入れるには（これは例外的イベントである）、或る程度の根拠が必要である。この根拠は、ＬＤＲヒストグラムとアウトライア・モデル関数との間の関係において見つけられる。そのヒストグラムがアウトライア・モデル関数に良く適合する場合、Ｈ０を受け入れ、そうでない場合はＨ１の仮定を受け入れる。
【０１１４】
そのような仮定をテストするために、提案される方法では、ピアソンのカイ２乗検定を行う（例えば、上記で引用したR.J.Larsenその他による文献の第４０２〜４０３ページを参照）。
【０１１５】
ピアソンの検定を適用する前に、「離散化アウトライア・モデル関数（discretized outlier model function）」の概念を紹介する。
【０１１６】
ビン、即ち、ＬＤＲヒストグラムを構成するために用いられるＬＤＲ値の間隔を、「ｋ＝１，・・・，Ｋ」であるＴｋで表すものとする。離散化アウトライア・モデル関数は、確率値をＫ個のビンのそれぞれに割り当てる。
【０１１７】
ｐ：｛１，・・・，Ｋ｝→［０，１］
第ｋのビンのそれぞれにおいて、値は、そのビンにわたってのアウトライア・モデル関数を積分したものと等しい。
【０１１８】
【数１５】
0005734460.tif 000016
【０１１９】
上記の式において、それぞれの値ｐ（ｋ）は、「モデル確率」と呼ばれる。表記を統一するために、モデル確率を、シーケンスｐｋのエレメントとして考慮する。
ｐｋ＝ｐ（ｋ）；  ｋ＝１，・・・，Ｋ
ピアソンのカイ２乗検定は、ＬＤＲヒストグラムと離散化アウトライア・モデル関数との間で行われる。
【０１２０】
「ピアソンの検定」。αレベルの重要度（significance）において、Ｈ１の仮定は、下記の場合に受け入れられる。
【０１２１】
【数１６】
0005734460.tif 000017
【０１２２】
上記の式において、「ｎ＝Ｎ（Ｎ−１）／２」であるｎは、ＬＤＲヒストグラムを構築するために用いた観測結果の合計数、即ち、キーポイントマッチ（ｘｉ，ｙｉ）、（ｘｊ，ｙｊ）のペアの数である。スレッショルド「χ１−α，Ｋ−１２」は、Ｋ−１の自由度でのカイ２乗検定の１００（１−α）パーセンタイルである。
【０１２３】
Ｈ１の仮定を受け入れるということは、参照画像が、クエリ画像内のオブジェクトを表す候補であることを意味する。スレッショルドを超えるマージンは、２つの画像の類似度の測定値として使用することができる。
【０１２４】
【数１７】
0005734460.tif 000018
【０１２５】
式１５を参照されたい。最大のρを有する参照画像（のインデックス）を、クエリ画像内のオブジェクトと同一のもの（identity）として選択することができる。
【０１２６】
１つより多くの参照画像が大きいρを有する場合、クエリ画像が、前記の参照画像の全てに存在する幾つかのオブジェクトを示すか、または、前記の参照画像が、非常に似たオブジェクトを描写するかの何れかである。この問題は、参照コレクションの知識を通じてや、手近な識別タスクを通じて、特定の解法を見つけることができる。
【０１２７】
αパラメータは、確率密度としてアウトライア・モデル関数をもつソースからＬＤＲヒストグラムを実際に生じさせた場合において、誤った参照画像を受け入れる確率である。
【０１２８】
セクション３  −  インライアの数の推定（提案される方法の第２段階）
関連付けされたキーポイントマッチの組において存在するインライアの数を知ることは、興味のあることである場合が多い。そのような数は、それ自体が有用であり得、また、セクション４で説明するように、アウトライアとインライアとを分離するために必要であり得る。
【０１２９】
この数は、ＬＤＲヒストグラムを用いて推定することができる。キーポイントマッチは２つの互いに素のカテゴリに分類されるので、ヒストグラムは、それぞれのカテゴリに対して１つのヒストグラム・コンポーネント（histogram component）と呼ばれる２つの項により形成される。インライアに対するヒストグラムとアウトライアに対するヒストグラムとは全く異なり、実際、その差異は、２つのコンポーネントを分離するためおよびそれらの相対的重みを表すために、有用である。
【０１３０】
先に説明したように、キーポイントマッチがアウトライアである場合、ヒストグラムはアウトライア・モデル関数のように見える。更には、ヒストグラムがアウトライア・モデル関数と似ている場合、ペアはアウトライアである。より一般的には、ヒストグラムを２つの項に分解でき、その１つの項がアウトライア・モデル関数のように見える場合、その項はアウトライアに起因するものである。この原理は、アウトライアの数を推測するため、更には、アウトライアを識別するために使用される。
【０１３１】
（ｘｉ，ｙｉ）と（ｘｊ，ｙｊ）との双方が正しく関連付けされている場合、キーポイントマッチのペアはインライアである。キーポイントマッチの一方または双方が誤って関連付けされている場合、キーポイントマッチのペアはアウトライアである。Ｐｉｎは、キーポイントマッチのペアがインライアのみを含む確率を示し、Ｐｏｕｔは、ペアのエレメントのうちの少なくとも１つがアウトライアである確率を示す。ｚを、キーポイントマッチのペアに対するＬＤＲの値とし、ｐ（ｚ｜ｉｎ）およびｐ（ｚ｜ｏｕｔ）は、条件付き確率密度（conditional probability density）を表すものとする。アウトライアに対する条件付き確率は、式７のアウトライア・モデル関数となると仮定される。
【０１３２】
ｐ（ｚ｜ｏｕｔ）＝ｆｚ（ｚ）
従って、全体の確率密度は下記の形を有する。
【０１３３】
ｐｚ（ｚ）＝Ｐｉｎ・ｐ（ｚ｜ｉｎ）＋Ｐｏｕｔ・ｆｚ（ｚ）      （１７）
この式は、ＬＤＲヒストグラムを２つの項に分解したもの対応する。
【０１３４】
ｈｋ＝ｄｋ＋ｇｋ；  ｋ＝１，・・・，Ｋ      （１８）
上記の式において、ｈｋはＬＤＲヒストグラムを表し、ｄｋはインライアに起因するコンポーネントであり、ｇｋはアウトライアに起因するコンポーネントである。インライアの数を推定する方法は、アウトライア・コンポーネントｇｋは予測される値に近いものである、という仮定に基づくものであり、以下の式が導きだされる。
【０１３５】
ｈｋ＝ｄｋ＋Ｅ（ｇｋ）＝ｄｋ＋ｎ・Ｐｏｕｔｐｋ      （１９）
上記の式において、モデル確率ｐｋは、第ｋのビンの間隔にわたってのアウトライア・モデル関数の積分であり、「ｎ＝Ｎ（Ｎ−１）／２」であるｎは、ＬＤＲヒストグラムを構築するために用いたキーポイントマッチのペアの数である。式１９には２つの未知の数量があり、それらはアウトライア確率Ｐｏｕｔと、インライア・コンポーネントｄｋとである。インライア・コンポーネントは負ではない必要があるので、式１９は下記のように書き換えることができる。
【０１３６】
ｈｋ−ｎ・Ｐｏｕｔｐｋ  ≧０      （２０）
上記のようにすると、式からインライア・コンポーネントが除かれる。ここでは、セクション１で説明したように、幾つかの間隔にわたってインライア・コンポーネントがゼロであると仮定しているので、それらの間隔にわたって、アウトライア・コンポーネントはヒストグラムの値と等しくなければならない。これは、式２０における差が、インデックスｋの幾つかのビンに関して下界０へ到達するように、アウトライア確率Ｐｏｕｔが十分に大きいものであるべきことを、意味する。従って、予め定めた値の小さい組においてアウトライア確率の可能な最大値を見つけるためのサーチが行われる。
【０１３７】
「アウトライア確率のサーチ」。ｋ＝１，・・・，Ｋであるｈｋが、ＬＤＲヒストグラムのビンを表すものとする。ｐｋがモデル確率を表し、ｎがヒストグラムの構築に使用されるキーポイントマッチのペアの数を表すものとする。「Ｂ＝｛β１，・・・，βＬ｝⊂［０，１］」を、Ｐｏｕｔの予め定めた適格な値の組とする。出願人は、キーポイントマッチのペアが少なくとも１つのアウトライアを含む確率の推定が、下記のようであると判断した。
【０１３８】
Ｐｏｕｔ＝ｍａｘ｛β：β∈Ｂ，ｈｋ≧ｎβｐｋ；ｋ＝１,・・・，Ｋ｝      （２１）
確率「１−Ｐｏｕｔ」は、全てのキーポイントマッチのペア（ｘｉ，ｙｉ）、（ｘｊ，ｙｊ）の中でのインライアの相対的な関数である。インライアのペア（ｘｉ，ｙｉ）の数を求めるためには、キーポイント・ペアの数Ｎと、キーポイントマッチのペアの数「ｎ＝Ｎ（Ｎ−１）／２」とが考慮されねばならない。なぜなら、ヒストグラムは全てのペア（ｘｉ，ｙｉ）、（ｘｊ，ｙｊ）を計数することにより作られるからである。なお、ここではｉ≦ｊである。インライアのペアの数がｍで表される場合、インライアからなるキーポイント・ペアの一対（keypoint pair couples）の端数（fraction）は下記のようになる。
【０１３９】
【数１８】
0005734460.tif 000019
【０１４０】
分布についての推定および仮定に基づくと、式２２の精度は低いものである。従って、ｍについての仮定の解が好ましい。
【０１４１】
従って、推定されるインライアのキーポイント・ペアの数は下記のようになる。
【０１４２】
【数１９】
0005734460.tif 000020
【０１４３】
図６は、モデル確率をスケーリングしてインライアの数を推定する例を示す。この例では、同じオブジェクト（家）が２つの画像に描写されている。下部の図は、ＬＤＲヒストグラムｈｋ（実線でプロット）と、推定されたアウトライアのヒストグラム（破線でプロット）とを示す。この場合、インライアの数は、キーポイントの総数の１／３であると推定された。
【０１４４】
セクション４  −  最もインライアでありそうなものの識別（提案される方法の第３段階）
先のステップが完了した後、インライアのヒストグラム・コンポーネントを決定するための全ての必要な数量が使用可能とされる（式１９を参照されたい）。
【０１４５】
ｄｋ＝ｈｋ−ｎ・Ｐｏｕｔｐｋ
このコンポーネントは、このセクションで示すように、インライアとアウトライアとを分離するために使用できる。
【０１４６】
キーポイントマッチの各ペアはログ距離比率の値に対応し、インライアのヒストグラム・コンポーネントは、その対がインライアを含む確率を表す。この情報は、パラメータとしてキーポイントのそれぞれのペアに対するバイナリ値をもつ尤度関数（likelihood function）を定式化するために使用される。１という値は、ペアがインライアであることを意味し、０はペアがアウトライアであることを意味する。インライアの所与の数を制約として用いる場合、この尤度関数を最大化するパラメータは、最もインライアでありそうなものの組を示す。
【０１４７】
Ｎをキーポイントマッチの数とし、ｕをＮエレメントのバイナリ・ベクトルとする。
【０１４８】
ｕ∈｛０，１｝Ｎ      （２４）
値１を持つエレメントは、対応するキーポイント・ペアがインライアであることを示し、値０を持つものはアウトライアであることを示す。前のセクションにおける手順のような手順は、インライアの数ｍの推定を行うので（式２２）、制約を加えることができる。
【０１４９】
【数２０】
0005734460.tif 000021
【０１５０】
式２のＬＤＲは、キーポイントマッチの各ペアについて知られている。
【０１５１】
ｚｉｊ＝ｌｄｒ（ｘｉ，ｘｊ，ｙｉ，ｙｊ）；ｉ≠ｊ      （２６）
理想的には、インライアに対しての条件付き確率密度を知っている場合、単に、インライアに対する全ての確率を加算することにより、尤度の値を、インライアの組の何れの仮定へも割り当てることができる。
【０１５２】
【数２１】
0005734460.tif 000022
【０１５３】
ｕはバイナリであるので、この合計を下記のように書き換えることができる。
【０１５４】
【数２２】
0005734460.tif 000023
【０１５５】
式２３および式２４の制約の下で式２７のＬを最大化するバイナリ・ベクトルｕは、最もインライアでありそうなｍ個のインライアの組を表す。
【０１５６】
式２７は、実際的なアルゴリズムを作るために変更する必要がある。インライアの確率密度ｐ（ｚ｜ｉｎ）についての閉じた形（closed form）が無い場合、それは式１９のインライアのヒストグラム・コンポーネントｄと置換される。この推移を理解するために、下記の量子化手段（quantizer）ｑを紹介するのが有益である。
【０１５７】
【数２３】
0005734460.tif 000024
【０１５８】
この量子化手段ｑは、値ｚに最も近いビン・センター（全てのビン・センターξ１，・・・，ξＫの中でのビン・センター（bin center））に対するインデックスを生成する。これは下記の近似を可能とする。
【０１５９】
【数２４】
0005734460.tif 000025
【０１６０】
下記の式は、この確率の近似値がＬＤＲヒストグラムのインライア・コンポーネントに対して予測される値に比例することを示す。
【０１６１】
【数２５】
0005734460.tif 000026
【０１６２】
上記の式において、比例定数は、キーポイントマッチのペアの総数であるｎと、一対における双方のペアがインライアである確率であるＰｉｎと、ビンの幅であるδとである。
【０１６３】
ここで、式２７における理想的な尤度関数を下記のものと置き換えることができる。
【０１６４】
【数２６】
0005734460.tif 000027
【０１６５】
上記の式において、式３１の定数ファクタは、Ｇ（ｕ）を最大化する解を動かさないので、省略されている。
【０１６６】
マトリックスの形では、上記の式は下記のようになる。
【０１６７】
Ｇ（ｕ）＝ｕＴＤｕ      （３３）
上記の式において、マトリックスＤは、エレメントｉ，ｊとして下記のものを有するインライアのヒストグラムからの値を含む。
【０１６８】
【数２７】
0005734460.tif 000028
【０１６９】
ここで、インライアの識別の問題を以下のように表すことができる。
【０１７０】
【数２８】
0005734460.tif 000029
【０１７１】
マトリックスＤが全ランクを有する場合、最適のものを計算するのは難しい。近似の解法への道筋は、IEEE Transactions on Image Processing、vol 19、２０１０年５月の第１３１９〜１３２６ページのA.Egozi、Y.Keller、およびH.Gutermanによる「Improving shape retrieval by spectral matching and met similarity（スペクトルマッチングおよび満たされた相似性による形状検索の改善）」に提供されており、ここでも、式３３に関するものと同様の問題に直面している。ここで、バイナリの最適化は簡単なものに置き換えられる。
【０１７２】
ｗＴＤｗ    を最大化する                  （３６）
ｗ∈ＲＮ，||ｗ||＝１    を条件とする。
【０１７３】
解は、Ｄの主な固有ベクトル（dominant eigenvector）（最大の固有値に対応する固有ベクトル）である。このベクトルのエレメントは、ゼロに近い場合または最大値に近い場合が多い（符号は選択されているので、最大値は正である）。従って、固有ベクトルｗは、下記の関係に従って、ｍ個の最大のエレメント（ｍは、式２２のインライアの推定された数）を取ることにより、バイナリ・ベクトルｕを得るために使用される。
【０１７４】
［ｗ＊，ｉ］＝ｓｏｒｔ（ｗ，’ｄｅｓｃｅｎｄ’）      （３７）
【０１７５】
【数２９】
0005734460.tif 000030
【０１７６】
上記の式において、「ｓｏｒｔ（ｗ，’ｄｅｓｃｅｎｄ’）」（ソート（ｗ，’降順’））は、Ｍａｔｌａｂ（ＭａｔｈＷｏｒｋｓによるもの）の関数であり、これは、アレイｗのエレメントを降順にソートして、対応する順序付けられたアレイｗ＊を生成する。関数「ｓｏｒｔ（ｗ，’ｄｅｓｃｅｎｄ’）」は、更なるアレイｉを生成し、そのエレメントは、アレイｗのエレメントのインデックスであり、アレイｗ＊の場合と同様に、順序付けられている。
【０１７７】
結果ｕは、インライアの組に良く近似したものであり、それは実際的な実験において証明できる。
【０１７８】
「高速固有ベクトル計算（fast eigenvector computation）」。推定したインライアは、Ｄの主な固有ベクトルのｍ個の最大エレメントに対応する。目的は、固有ベクトルの計算を、可能な限り、また幾らかは精度を犠牲にしてでも、高速に維持することである。主な固有ベクトルを見つける方法は当技術分野では知られている（例えば、The Society for Industrial and Applied Mathematics、１９９７年の、L.TredethenおよびD.Bauによる「Numerical Linear Algebra（数値的線形数学）」に開示されているパワー反復およびレイリー商反復（the power iteration and the Rayleigh quotient iteration）を参照）。
【０１７９】
双方の方法とも、反復法であり、主な固有ベクトルの最初の推測に依存するものであり、にわか仕立ての候補は中間コラム（mean column）であり、これは、Ｄのような負ではないエントリのマトリックスに対して近くなる。
【０１８０】
セクション５  −  方法の主なステップ
先に説明した方法の主なステップを図７Ａないし図７Ｃに示す。
【０１８１】
より詳細には、図７Ａは、本発明の１つの実施形態に従った方法の第１段階の主なステップを示すフローチャートである。既に説明したように、方法の第１段階は、第１画像と第２画像とが同じオブジェクトを描写しているか否かを評価するものである。
【０１８２】
画像のペアが比較されるところから、即ち、第１画像（クエリ画像）がＮ個のキーポイントｘｉを含み、第２画像（参照画像）がＮ個のキーポイントｙｉを含むところから開始するものと仮定している。クエリ画像上の各キーポイントｘｉは、参照画像上の対応するキーポイントｙｉと関連付けされて、個々のキーポイントマッチ（ｘｉ，ｙｉ）を定める。
【０１８３】
第１ステップは、相似性に関して不変である距離比率の関数を用いて、キーポイントマッチ（ｘｉ，ｙｉ）から距離比率のヒストグラムを生成する。例えば、式２を用いてキーポイントマッチ（ｘｉ，ｙｉ）からログ距離比率（ＬＤＲ）ヒストグラムが生成される（ブロック７０２）。
【０１８４】
次に、式２で定義されたログ距離比率（ＬＤＲ）関数を用いる場合には、第１ステップで使用される距離比率の関数と関連する確率密度関数、例えば、式７を用いて、対応するアウトライア・モデル関数が生成される（ブロック７０４）。
【０１８５】
次のステップは、以前に計算したアウトライア・モデル関数の離散化（discretize）を行うが（ブロック７０６）、このステップでは、例えば、式１４を、以前に計算したアウトライア・モデル関数に適用して、その離散化版を得る。
【０１８６】
次に、ピアソンの検定（式１５）を用いて、ＬＤＲヒストグラムを、離散化アウトライア・モデル関数と比較し、全てのキーポイントマッチがランダムであると考えられるか否かの評価を行う（ブロック７０８）。
【０１８７】
特に、ピアソンの検定の結果が、離散化アウトライア・モデル関数とのＬＤＲヒストグラムの良好な適合を伴う場合（ブロック７１０の出口側分岐Ｙ）、それは、キーポイントマッチの全てまたはほぼ全てがアウトライアであることを意味し、従って、参照画像は、クエリ画像に描写されている何れのオブジェクトも示さない。従って、方法は終了する。
【０１８８】
逆に、ピアソンの検定の結果が、ＬＤＲヒストグラムが離散化アウトライア・モデル関数と適合しないことを示す場合（ブロック７１０の出口側分岐Ｎ）、それは、キーポイントマッチの多くがインライアであり得ることを意味し、従って、参照画像は、おそらく、クエリ画像に描写されているオブジェクトを示す。このケースにおいて、望まれる場合には、方法は第２段階へ進む。
【０１８９】
図７Ｂは、本発明の１つの実施形態に従った方法の第２段階の主なステップを示すフローチャートである。この段階は、先に説明した「アウトライア確率のサーチ」に基づいて、キーポイントマッチの組のうちの何個のキーポイントマッチがインライアであるかを評価することを可能にする。
【０１９０】
第１ステップでは、式２１のファクタβを初期化する（ブロック７１２）。例えば、βをゼロに初期化する。
【０１９１】
ファクタβは、離散化アウトライア・モデル関数を重み付けするために使用され、ＬＤＲヒストグラムと比較されるようにする。このステップの目的は、式２１を通じてキーポイントマッチの所与の一対が少なくとも１つのアウトライアを含む確率を推定することである。より特定時には、各ｋに対してｎβｐｋが計算され（ブロック７１４）、項βが、以前にとった値へ所定数量を加算することにより更新されると（ブロック７１６）、以前に計算したｎβｐｋと対応するｈｋ（各ｋについて）との間での比較が行われる。
【０１９２】
各ｋについて、ｈｋが、以前に計算したｎβｐｋよりも高いという結果となった場合（ブロック７１８の出口側分岐Ｙ）、重み付けされた離散化アウトライア・モデル関数がＬＤＲヒストグラムよりも低いことを意味し、βの更新された値を用いてｎβｐｋの新たな計算が行われる（ブロック７１４へ戻る）。
【０１９３】
上記のようではなく、ｎβｐｋが、少なくとも１つのｋに関して、ｈｋへ到達した場合（ブロック７１８の出口側分岐Ｎ）、これは、重み付けされた離散化アウトライア・モデル関数の一部（特定的には、その横方向のテール）が、ＬＤＲヒストグラムの対応する部分に到達したまたはそれらを超越したことを意味する。従って、式２１に従い、キーポイントマッチのペアが少なくとも１つのアウトライアを含む確率Ｐｏｕｔは、βがとる最新の値と等しいと考えられる（ブロック７２０）。従って、キーポイントマッチのペアが少なくとも１つのインライアを含む推定される確率Ｐｉｎは、「１−Ｐｏｕｔ」と等しく設定される（ブロック７２２）。
【０１９４】
次に、インライアの数ｍは、式２３を用いて計算される（ブロック７２４）。
【０１９５】
この時点で、望まれる場合には、方法は第３段階へ進む。
【０１９６】
図７Ｃは、本発明の１つの実施形態に従った方法の第３段階の主なステップを示すフローチャートである。この段階は、何れのキーポイントマッチがインライアであるかと、何れのキーポイントマッチがアウトライアであるかを特定的に識別することを可能にするものであり、３６の最大化の問題を解く。
【０１９７】
第１ステップでは、３４の関係において示されるインライア・マトリックスＤを構築する（ブロック７２６）。
【０１９８】
次に、最大化の問題３６は、インライア・マトリックスＤの主な固有ベクトルｗを見つけるように解かれる（ブロック７２８）。
【０１９９】
最後に、インライアの組の近似値を、関係３７および３８における以前に見つけた固有ベクトルｗを用いて、計算する（ブロック７３０）。
【０２００】
このセクションで説明される方法のステップは、適切な処理ユニットにより行うことができ、それらの構造および機能は、それらに対して定められた特定の応用分野に応じたものとなる。例えば、それぞれの処理ユニットは、方法の１以上のステップを行うように特別に設計されたハードウェア・ユニットとすることができる。更には、方法のステップは、プログラマブルの機械（例えば、コンピュータ）により、対応する１組の命令による制御の下で、行うことができる。
【０２０１】
セクション６  −  方法の幾つかの例示的な応用
図８は、考えられ得るシナリオを概略的に示すものであり、本発明の１つの実施形態に従って、先に説明した方法を用いて、ビジュアル・サーチ・サービスを実施することができる。参照符号８００で示される図８のシナリオは、クライアント−サーバ構成に従って構築されるものであり、ビジュアル・サーチ・サーバ８１０は、複数の端末８２０と、外部ネットワーク８３０を通じてデータを交換するために、対話するように構成される。外部ネットワーク８３０は、ＭＡＮ、ＷＡＮ、ＶＰＮ、インターネット、電話網などである。各端末８２０は、パーソナル・コンピュータ、ノートブック、ラップトップ、パーソナル・デジタル・アシスタント、スマートフォン、またはデジタル画像を管理できる任意の電子デバイスとすることができる。
【０２０２】
図９Ａに示す本発明の１つの実施形態に従うと、ビジュアル・サーチ・サービスの全ての主な動作は、ビジュアル・サーチ・サーバ８１０により行われる。
【０２０３】
ピクチャに描写されているオブジェクトと関連する情報を要求する端末８２０のユーザは、そのピクチャ（クエリ画像となる）を、ネットワーク８３０を通じてビジュアル・サーチ・サーバ８１０へ送信する。
【０２０４】
ビジュアル・サーチ・サーバ８１０は、端末８２０との間でのデータの送信／受信のためにネットワーク８３０と対話するためのサーバ・インターフェース９０２を含む。サーバ・インターフェース９０２を通じて、ビジュアル・サーチ・サーバ８１０は、分析対象となるクエリ画像を受信する。
【０２０５】
クエリ画像は、そのクエリ画像に含まれるキーポイントを識別するように構成されたキーポイント検出ユニット９０４へ供給される。
【０２０６】
キーポイントが生成されると、そのローカルのアスペクト（aspect）が特徴計算ユニット（feature computation unit）９０６により記述される。この動作は、特徴計算ユニット９０６により、ＳＩＦＴ（Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ）やＳＵＲＦ（Ｓｐｅｅｄｅｄ  Ｕｐ  Ｒｏｂｕｓｔ  Ｆｅｔｕｒｅｓ）などのような既知のローカル記述子を用いて、行われる。
【０２０７】
ビジュアル・サーチ・サーバ８１０は更に特徴マッチングユニット（feature matching unit）９０８を含み、特徴マッチングユニット９０８は、画像認識に使用される参照画像を記憶する参照データベース９１０と結合される。クエリ画像から抽出されたローカル記述子と、参照データベースに記憶された参照画像のローカル記述子との比較は、特徴マッチングユニット９０８により、例えば、記述子間のユークリッド距離に基づく技術のような、既知の画像特徴比較技術を用いて、行われる。参照データベースのそれぞれの参照画像について、特徴マッチングユニット９０８は、対応するキーポイントマッチの組を含む、対応するリストを出力する。このリストは、クエリ画像に描写されたオブジェクトが何れの参照画像に描写された何れのオブジェクトにも対応しない場合、空であり得る。
【０２０８】
特徴マッチングユニット９０８により生成されたリストに基づいて、選択ユニット９１２は、最高数のキーポイントマッチをクエリ画像と共有する第１のｑ個の参照画像を選択する。これらの参照画像は、クエリ画像に描写されたオブジェクトを含む最適の候補であると想定されている。
【０２０９】
本発明の１つの実施形態に従うと、ビジュアル・サーチ・サーバ８１０は更に、先に説明した方法を実施するように構成される最適化ユニット９１４を含む。最適化ユニット９１４は、前記の方法を、選択ユニット９１２により選択されたｑ参照画像の組に対応するキーポイントマッチに適用する。クエリ画像と組の中の１つの参照画像とで構成される各ペアに関して、最適化ユニット９１４は、正しいキーポイントマッチ（インライア）の数を計算する。この計算は、方法の第１段階に従って行われ、好適には、方法の最初の２つの段階（即ち、図７Ａと図７Ｂとに示されたもの）に従って行われる。図７Ｃに示される方法の第３段階も行われる場合（例えば、クエリ画像に描写されているオブジェクトが参照画像に配されているかを示す指示を得ることが望まれる場合）、最適化ユニット９１４は、何れのキーポイントマッチがインライアと考えられるかを、特定的に識別することができる。クエリ画像の対応するキーポイントと正しくマッチングされたキーポイントを十分な数だけ含む、という結果が得られた組の中の参照画像は、少なくとも、クエリ画像に描写されたオブジェクトと同じオブジェクト（同じオブジェクトの一部）を含むものと考えられる。後者の参照画像は、次に、ビジュアル・サーチに要求の結果として、ネットワーク８３０を通じて端末へ送られるが、その場合において、数えられたインライアの数に基づいて順序付けすることができる。
【０２１０】
図９Ｂに示す本発明の別の実施形態に従うと、キーポイント検出ユニット９０４と特徴計算ユニット９０６とは、ビジュアル・サーチ・サーバ８１０に含まれるのではなく、端末８２０に含まれる。この場合、クエリ画像をビジュアル・サーチ・サーバ８１０へ送信するのではなく、それぞれの端末８２０は、クエリ画像からローカルで生成したローカル記述子を直接に送信することができる。
【０２１１】
先の実施形態と比較して、この解決法は、送信する必要のあるデータ（クエリ画像全体ではなくローカル記述子）の量が少ない。更に、この実施形態に従うと、ビジュアル・サーチ・サーバ８１０の計算負荷が低減され、ビジュアル・サーチ・サーバ８１０が、より多くの画像サーチの要求を同時に管理できるようになる。
【０２１２】
図９Ｃに示す本発明の更に別の実施形態に従うと、ビジュアル・サーチ・サービスの主な動作のほぼ全てが端末８２０により行われ、ビジュアル・サーチ・サーバ８１０は、単に、参照画像のキーポイントとローカル記述子とを記憶し、それらのものの選択されたサブセットを、端末のユーザから要求された特定のビジュアル・サーチに基づいて端末へ送信する。例えば、端末８２０が、ＧＰＳシステムを装備したスマートフォンであり、クエリ画像が、スマートフォンのカメラで撮られたピクチャである場合、ビジュアル・サーチ・サーバ８１０により送信するキーポイントとローカル記述子との選択は、端末８２０の実際の位置に基づくことができる。この解決法は、モニュメント認識サービスなどのような幾つかのビジュアル・サーチ・サービスにおいて好都合に用いることができる。
【０２１３】
画像比較動作を管理できるようにするために、端末８２０は、ローカル参照データベース９１６と更新ユニット９２０とを備え、更新ユニット９２０は、ビジュアル・サーチ・サーバ８１０により送信されたキーポイントおよびローカル記述子を受信するように適用され、従って、ローカル参照データベース９１６を更新する。なお、既に記憶されているキーポイントおよびローカル記述子を用いても十分であるので、画像の比較を行うとき毎にローカル参照データベース９１６の更新を必ず行う必要があるという訳ではいことを、理解すべきである。例えば、ローカル参照データベース９１６を、１日に１回のみ、ビジュアル・サーチ・サーバ８１０により更新することができる。
【０２１４】
先の実施形態と比較して、この解決法は、送信されるデータの量が大きく低減されるので、速い。従って、この解決法は、特に、拡張現実の応用に適する。
【０２１５】
提案される方法の更に可能な応用は、立体カメラ・システムに属するビデオ・カメラの自動校正である。校正の目的は、基礎的マトリックス（fundamental matrix）と呼ばれるもの、即ち、取得システム（acquisition system）の内在的および外来的なパラメータを記述するマトリックスの生成である。内在的パラメータはカメラの構成を記述し、外来的パラメータは空間内のカメラの位置を記述する。
【０２１６】
図１０の概略的なフローチャートに示すように、第１カメラ１００１は第１画像を取得し（ブロック１００４）、第１画像は、対応する第１キーポイントを識別するために処理される（ブロック１００６）。第１キーポイントが識別されると、そのローカルのアスペクトが、対応する第１ローカル記述子を通じて記述される（ブロック１００８）。同様に、第２カメラ１０１０は第２画像を取得し（ブロック１０１２）、第２画像は、対応する第２キーポイントを見つけるために処理される（ブロック１０１４）。次に、それらのキーポイントのローカルのアスペクトが、対応する第２ローカル記述子を通じて記述される（ブロック１０１６）。
【０２１７】
第１ローカル記述子と第２ローカル記述子とを比較することにより、第１画像と第２画像との間でのキーポイントマッチが生成される（ブロック１０１８）。次に、図７Ａ〜図７Ｃに示す方法の３つの段階を適用することにより、インライアであるキーポイントマッチが識別される（ブロック１０２０）。
【０２１８】
インライアが識別されると、基礎的マトリックスを推定するために反復する手順が行われ（ブロック１０２２）、それにより、新たなキーポイントマッチが見つけられる（ブロック２０１４）。これらの動作は、IEEE Transactions on pattern analysis and machine intelligence、Vol.19、No.6のR.Hartleyによる「In defense of the Eight-Point Algorithm（８ポイント・アルゴリズムを守る）」に記載された手順に続いて行うことができる。次に、新たなキーポイントマッチは、図７Ａ〜図７Ｃに示す方法の３つの段階により再び処理され、インライアが識別される（ブロック１０２６）。この手順（即ち、ブロック１０２２、１０２４、１０２６に対応する手順）は、インライアの数が安定するまで反復される。
【０２１９】
上記の記載では、本発明の幾つかの実施形態を詳細に呈示し説明したが、特許請求の範囲に定めた範囲から出ることなく、説明した実施形態に対して幾つかの変更を行うことができ、また、別の実施形態も可能である。
【０２２０】
例えば、ここでの説明では、ログ距離比率（ＬＤＲ）を参照しているが、ヒストグラムが、対数を用いない単純な距離比率などのような別の距離比率を用いて解釈される場合には、ログ距離比率の場合と類似の考え方を適用することができ、更には、ヒストグラムが、ログ距離比率の倍数や累乗を用いて解釈される場合にも、ログ距離比率の場合と類似の考え方を適用することができる。
【０２２１】
更に、距離比率の統計的分布をヒストグラムとは異なる表現で表すことに、何の妨げもない。その場合、ピアソンの検定は、選択された特定の表現と矛盾しない等価の検定に置き換えるべきである。
【０２２２】
更に、本発明の構成要素は、ヒストグラムのビンの幅が互いに異なっている場合でも、適用することができる。
【図１Ａ】
0005734460.tif 000031
【図１Ｂ】
0005734460.tif 000032
【図１Ｃ】
0005734460.tif 000033
【図２】
0005734460.tif 000034
【図３Ａ】
0005734460.tif 000035
【図３Ｂ】
0005734460.tif 000036
【図３Ｃ】
0005734460.tif 000037
【図３Ｄ】
0005734460.tif 000038
【図３Ｅ】
0005734460.tif 000039
【図３Ｆ】
0005734460.tif 000040
【図４】
0005734460.tif 000041
【図５Ａ】
0005734460.tif 000042
【図５Ｂ】
0005734460.tif 000043
【図６】
0005734460.tif 000044
【図７Ａ】
0005734460.tif 000045
【図７Ｂ】
0005734460.tif 000046
【図７Ｃ】
0005734460.tif 000047
【図８】
0005734460.tif 000048
【図９Ａ】
0005734460.tif 000049
【図９Ｂ】
0005734460.tif 000050
【図９Ｃ】
0005734460.tif 000051
【図１０】
0005734460.tif 000052