"コンピュータによって、場面の複数の画像間で対応する点を特定するための方法であって、該方法は、コンピュータにより実行される以下の各ステップ、即ち、各画像内の特徴点をさまざまな解像度で特定するステップであって、前記点を表す画像内の位置は、前記点を中心とする第1の所定のサイズの近傍領域内のピクセルに起因する少なくとも1つの属性で定義され、前記点を中心とする第2の所定のサイズの近傍領域内のピクセルに起因する少なくとも1つの属性に基づく一意の向きを割り当てられる、ステップと、前記特徴点のそれぞれについて、画像の位置、向き、スケールの変化、および前記点の位置と向きを定義するためのピクセルの輝度の変化に対して不変の形で各点を特徴付ける記述子を生成するステップと、前記画像間で一致する記述子を検出するステップと、異なる画像中に現れる一致する記述子の各集合に関連付けられた前記特徴点を対応する点として指定するステップとを備えることを特徴とする方法。各画像内の特徴点を特定する前記ステップは、画像ごとに、画像解像度ピラミッドを構成するステップと、前記ピラミッドのレベルごとに、コーナー特徴を代表する考察対象の画像内の位置を特定するステップと、各コーナー特徴の前記向きを特定するステップと、各コーナー特徴の前記特定された位置を個別の特徴点として指定するステップと、各コーナー特徴の前記特定された向きを前記特徴に関連付けられた前記特徴点に割り当てるステップとを備えることを特徴とする請求項1に記載の方法。コーナー特徴を代表する考察対象の画像内の位置を特定する前記ステップは、各コーナー特徴の位置を特定するステップであって、前記コーナー特徴は前記位置を中心とする所定の最小近傍半径のピクセル近傍の局所的な最大値であるコーナー強度を示しており、所定の最小強度しきい値を超えるステップと、前記近傍半径を所定の整数値だけ増分し、前記前に特定された位置でコーナー強度が現在考察対象であるピクセル近傍でも依然として局所的な最大値であり、依然として前記所定の最小強度しきい値を超えている位置を特定するステップと、前記特定された位置の数が所定の最大値を超えない範囲で増分と第2の特定のステップを繰り返すステップと、残っている特定された位置のそれぞれを個別のコーナー特徴の代表として指定するステップとを備えることを特徴とする請求項2に記載の方法。各コーナー特徴の前記特定された位置を個別の特徴点として指定する前記ステップは、考察の対象となる前記特定された位置を中心とする所定のサイズの局所的な近傍に適合する2次元の正方形2Dquadraticの面で最大強度を示す位置を個々の特徴点の位置として指定するステップを備えることを特徴とする請求項2に記載の方法。各コーナー特徴の前記向きを特定するステップは、ぼかし勾配brurredgradientのアプローチを使用して各コーナー特徴の向きを特定するステップを備えることを特徴とする請求項2に記載の方法。各コーナー特徴はハリスのコーナーであることを特徴とする請求項2に記載の方法。前記特徴点のそれぞれについて記述子を生成する前記ステップは、考察対象である前記特徴点の位置を中心とし、前記特徴点と同じ向きの所定のサイズpxpの記述子領域を確立するステップと、前記記述子領域から前記領域内のピクセル輝度値の双線形補間を使用してピクセルあたり1回のサンプリングになるようにサンプリングした前記記述子領域より小さい所定のサイズdxdの記述子ベクトルを構成するステップと、前記記述子ベクトルを標準化するステップと、前記記述子ベクトルに対してハールのウェーブレット変換を実行して変換ベクトルを生成するステップとを備えることを特徴とする請求項1に記載の方法。前記画像間で一致する記述子を検出するステップは、前記変換された記述子ベクトルを、特徴空間内の所定の数の近傍領域とマッチングするステップを備えることを特徴とする請求項7に記載の方法。前記変換された記述子ベクトルをマッチングする前記ステップは、各変換された記述子ベクトルの所定の数n個のウェーブレット係数から3次元ハッシュテーブルを生成してn係数ベクトルのハッシュテーブルを構成するステップと、前記ハッシュテーブルのビンのそれぞれについて、考察対象の前記ビン内で検出される個々のn係数ベクトル間の距離を計算するステップと、n係数ベクトルのそれぞれについて、前記同じビン内にあるが前記考察対象のベクトルと同じ前記画像には関連付けられていない前記計算された距離に基づいてその所定の数の近傍領域を特定し、一致ベクトル候補の集合を構成するステップと、前記一致ベクトル候補の集合のそれぞれに属する前記ベクトルに関連付けられた前記特徴点を、前記関連の画像内で前記場面の前記同じ要素を表す対応する点として指定するステップとを備えることを特徴とする請求項8に記載の方法。前記ハッシュテーブルは次元あたり10個のビンを備えており、各ビンは半分の領域が重複することと、前記所定の数n個のウェーブレット係数は3係数ベクトルのハッシュテーブルを構成する最初の3つの非ゼロ係数を備えることを特徴とする請求項9に記載の方法。一致ベクトル候補の集合のそれぞれに属する前記ベクトル関連付けられた前記特徴点を対応する点として指定する前記ステップは、一致ベクトル候補ベクトルのそれぞれについて、関連の特徴点が同じベクトル集合に属する別の3係数ベクトルに関連付けられた別の画像内の特徴点に実際には対応しない一致ベクトル候補として前記3係数ベクトルを考察対象から除外するステップと、一致ベクトル候補の各集合内に残っている前記3係数ベクトルのそれぞれについて、前記ベクトルに関連付けられた前記特徴点を前記関連の画像内の対応する点として指定するステップとを備えることを特徴とする請求項9に記載の方法。一致ベクトルの集合のそれぞれについて、関連の特徴点が前記同じベクトル集合に属する別の前記3係数ベクトルに関連付けられた別の画像内の特徴点に実際に対応しない一致ベクトル候補として前記3係数ベクトルを考察対象から除去する前記ステップは、考察対象である一致ベクトルの集合のアウトライアの距離を計算するステップと、任意の前記一致ベクトルについて計算した前記距離が前記アウトライアの距離の65を超えるかどうかを判断するステップと、一致ベクトルの距離が前記アウトライアの距離の65を超えると判断した場合は、必ず前記ベクトルに対応する点として関連付けられた前記特徴点を除外するステップとを備えることを特徴とする請求項11に記載の方法。一致ベクトルの集合のそれぞれについて、関連の特徴点が前記同じベクトル集合に属する別の前記3係数ベクトルに関連付けられた別の画像内の特徴点に実際に対応しない一致ベクトル候補として3係数ベクトルを考察対象から除去する前記ステップは、幾何学的アウトライア除去手順を実行するステップと、アウトライアであると判断された対応する点として任意のベクトルに関連付けられた特徴点を除外するステップとを備えることを特徴とする請求項11に記載の方法。前記変換された記述子ベクトルをマッチングする前記ステップは、変換された記述子ベクトルのそれぞれについて最初の3つの非ゼロウェーブレット係数から3次元ハッシュテーブルを生成して3係数ベクトルのハッシュテーブルを構成するステップと、前記ハッシュテーブルの各ビンについて、考察対象の前記ビン内で検出される3係数ベクトルのそれぞれの間の前記距離を計算するステップと、3係数ベクトルのそれぞれについて、考察対象の前記ベクトルに関連付けられた前記画像を除く各画像に個々に関連付けられた前記同じビン内で検出される前記近傍領域を、前記計算された距離に基づいて画像ごとの所定の数まで特定し、一致ベクトル候補の集合を構成するステップと、一致ベクトル候補の集合のそれぞれに属する前記ベクトルに関連付けられた前記特徴点を、前記関連の画像内で前記場面の前記同じ要素を表す対応する点として指定するステップとを備えることを特徴とする請求項8に記載の方法。前記ハッシュテーブルは次元あたり10個のビンを備えており、さらに各ビンは半分の重複領域を備えることを特徴とする請求項14に記載の方法。前記第1と第2の所定のサイズの近傍が同じサイズであることを特徴とする請求項1に記載の方法。場面の複数の画像間で対応する点を特定するシステムであって、汎用コンピューティングデバイスと、前記コンピューティングデバイスで実行可能なプログラムモジュールを備えるコンピュータプログラムであって、前記コンピューティングデバイスは前記コンピュータプログラムの前記プログラムモジュールによって指示されて、各特徴点をピクセルの所定の属性によって構成されるパターンに基づいて割り当てられる位置と向きによって定義して、各画像内の対応する点の候補を表す特徴点を特定し、前記特徴点のそれぞれについて、画像の位置、向き、スケールの変化、および前記点の位置と向きを定義するためのピクセルのバイアスとゲインの変化に対して不変である形で各点を特徴付ける記述子を生成し、前記画像間で一致する記述子を検出し、異なる画像中に現れる一致する記述子の集合に関連付けられた前記特徴点を対応する点として指定するコンピュータプログラムとを備えることを特徴とするシステム。前記特徴点のそれぞれについて記述子を生成する前記プログラムモジュールは、特徴点ごとに、a前記特徴点の位置を中心とし、前記特徴点と同じ向きの所定のサイズpxpの記述子領域を確立するサブモジュールと、b前記記述子領域から前記領域内の輝度値に関する双線形補間のサンプリングを使用して、より小さい所定のサイズdxdの記述子ベクトルを構成するサブモジュールと、c前記記述子ベクトルをバイアスとゲインに関して標準化するサブモジュールと、d前記標準化された記述子ベクトルに対してハールのウェーブレット変換を適用して前記考察対象の特徴点の前記記述子を構成するサブモジュールとを備えることを特徴とする請求項17に記載のシステム。前記画像間で一致する記述子を検出する前記プログラムモジュールは、e各特徴点の最初の3つの非ゼロウェーブレット係数から3次元ハッシュテーブルを生成するサブモジュールと、f前記ハッシュテーブルのビンごとに、各記述子間の距離を計算するサブモジュールと、gまだ選択されていない記述子を選択するサブモジュールと、h前記同じビン内にあるが前記選択された記述子と前記同じ画像には関連付けられていない所定の数の前記選択された記述子の近傍領域を特定するサブモジュールと、i前記選択された記述子とその近傍領域のアウトライアの距離を計算するサブモジュールと、j前記選択された記述子とその近傍領域のそれぞれとの前記計算された距離は前記アウトライアの距離の65未満かどうかを個々に判断するサブモジュールと、k前記選択された記述子とその近傍領域の1つとの前記計算された距離は前記アウトライアの距離の65未満である場合は、必ず前記近傍領域の記述子を前記選択された記述子に関する一致記述子として指定するサブモジュールと、l幾何学ベースのアウトライア除去手順を実行し、前記選択された記述子に一致するとして指定された記述子に対応する任意の特徴点は、前記選択された記述子の前記特徴点の位置に対応しないかどうかを判断するサブモジュールと、m前記選択された記述子に一致するとして指定された任意の記述子が前記選択された記述子の特徴点の位置に対応しない場合に一致記述子から除外するサブモジュールと、n残っているすべての記述子について処理が完了するまで、サブモジュールgからmを繰り返すサブモジュールとを備えることを特徴とする請求項18に記載のシステム。前記画像間で一致する記述子を検出する前記プログラムモジュールは、e各特徴点記述子の最初の3つの非ゼロウェーブレット係数から3次元ハッシュテーブルを生成するサブモジュールと、f前記ハッシュテーブルのビンごとに、各記述子間の距離を計算するサブモジュールと、gまだ選択されていない記述子を選択するサブモジュールと、h前記同じビン内にあるが前記選択された記述子と同じ画像には関連付けられていない所定の数の前記選択された記述子の近傍領域を特定するサブモジュールと、i前記選択された記述子とその近傍領域のアウトライアの距離を計算するサブモジュールと、j前記選択された記述子とその近傍領域のそれぞれとの前記計算された距離は前記アウトライアの距離の65未満かどうかを個々に判断するサブモジュールと、k前記選択された記述子とその近傍領域の1つとの前記計算された距離は前記アウトライアの距離の65未満である場合は、必ず近傍領域記述子を前記選択された記述子に関する一致記述子として指定するサブモジュールと、l残っているすべての記述子について処理が完了するまで、サブモジュールgからkを繰り返すサブモジュールとを備えることを特徴とする請求項18に記載のシステム。前記画像間で一致する記述子を検出する前記プログラムモジュールは、e各特徴点の最初の3つの非ゼロウェーブレット係数から3次元ハッシュテーブルを生成するサブモジュールと、f前記ハッシュテーブルのビンごとに、各記述子間の距離を計算するサブモジュールと、gまだ選択されていない記述子を選択するサブモジュールと、h前記同じビン内にあるが前記選択された記述子と同じ画像に関連付けられていない所定の数の前記選択された記述子の近傍領域を特定するサブモジュールと、i幾何学ベースのアウトライア除去手順を実行し、前記近傍領域記述子に対応するどの特徴点が前記選択された記述子の特徴点の位置に対応するかを判断するサブモジュールと、j前記近傍領域記述子に対応する前記特徴点の位置に対応すると判断した場合にのみ、近傍領域記述子を前記選択された記述子に関する一致記述子として指定するサブモジュールと、k残っているすべての記述子についての処理が完了するまで、サブモジュールgからjを繰り返すサブモジュールとを備えることを特徴とする請求項18に記載のシステム。コンピュータに、場面の複数の画像間で対応する点を特定するために各ステップを実行させるためのコンピュータ可読命令を格納するコンピュータ可読媒体であって、前記各ステップは、各画像内の対応する点の候補を表す特徴点を特定する操作であって、各特徴点は前記位置を中心とする近傍内のピクセルに関する所定の属性で構成される一意のパターンで特定できる画像内の位置に対応するステップと、各特徴点に位置を割り当てる操作であって、前記位置は前記位置を中心とする近傍内のピクセルに関する所定の属性で構成される一意のパターンから抽出されるステップと、前記特徴点のそれぞれについて、画像の位置、向き、スケールの変化、および前記点の前記位置と向きを定義するためのピクセルのバイアスとゲインの変化に対して、不変の形で記述子を生成するステップと、前記画像間で一致する記述子を検出するステップと、異なる画像中に現れる前記一致する記述子の集合に関連付けられた前記特徴点を、一致する点として指定するステップとから成ることを特徴とするコンピュータ可読媒体。一般に、特徴点の抽出と記述子のマッチングは2つの基本的なステップと見なされており、特徴点の繰り返し精度repeatability[17]と記述子のパフォーマンス[13]に関するさまざまな技術を評価する場合に何らかの進展が見られた。また、動きの構造structurefrommotion[19]とパノラマイメージングpanoramicimaging[6]のコンテキストにおけるマルチビューマッチングへの強制的な適用もある。しかし、今日までこうした手順で特徴を迅速に検出し、場面の部分的に重複する多くの画像間の相関性を検出する機能を提供するものはない。本明細書の以上と以下の各節の説明で、角括弧内の数字は関連のさまざまな文献の参照を示していることに留意されたい。たとえば、こうした参照は参考文献[1]または単に[1]で表される。複数の参考文献を表す場合は、たとえば[2、3]のように複数の数字を角括弧で囲む。個々の数字に対応する出版物が記載された参考文献のリストは、以下の実施形態の節DetailedDescriptionsectionの終わりに示している。本発明は、不変の特徴の新しいクラスに基づいて場面の複数の画像間で対応する点を特定するシステムおよびプロセスを対象とする。本システムおよびプロセスは、特徴を迅速に抽出し、場面の部分的に重複する多くの画像間の相関性を検出する機能を備えている。本技術は、画像ステッチimagestitchingやビデオ安定化videostabilizationのための画像相関性の検出にきわめて有効である。また、ビデオの特徴追跡や複数画像からの3次元モデルの構築などの一般的なマルチ画像の相関性にも拡張できる。より詳細には、本システムおよびプロセスには、まずさまざまな解像度の各画像において特徴点を特定する操作が含まれる。特徴点は、その画像内の位置がその点を中心とするあらかじめ指定されたサイズのピクセル近傍内のピクセルに起因する少なくとも1つの属性で定義される点である。さらに、個々の特徴点はその点を中心とするピクセル近傍内のピクセルに起因する少なくとも1つの属性点の位置の定義に使用した属性と同じでもよいし、別の属性でもよいに基づいて一意の向きを割り当てることができる点である。この第2の近傍は、点の位置の定義に使用したものと同じサイズの近傍でもよいし、別のサイズの近傍でもよい。特徴点が特定されると、特徴点ごとに記述子が確立する。この記述子は、画像の位置、向き、スケールの変化に対しても、この点を中心とする領域内のピクセルの輝度intensityに対しても、実質的に不変である形で各点を特徴付ける。次に、画像間で実質的に一致する記述子の集合が特定される。異なる画像中に現れる、一致する記述子の集合に関連付けられた特徴点は、対応する点すなわち、場面の同一の要素を表す点として指定される。画像ごとに特徴点を特定する操作に関して、この操作はまず画像の解像度のピラミッドを作成することで実行できる。ピラミッドの各レベルで、コーナー特徴を代表する画像内の位置を特定する。たとえば、本システムおよびプロセスの試験済みの実施形態では、いわゆるハリスのコーナー特徴を採用した。コーナー特徴の位置を特定する1つの方法は、その位置を中心とした所定の最小近傍半径のピクセル近傍内で局所的に最大のコーナー強度cornerstrengthを示し、所定の最小強度の閾値を超えるコーナーの位置を特徴ごとに特定することである。特定されたコーナー位置の総数が所定の最大値を超える場合は、近傍半径を所定の整数値だけ増分し、前回特定された各位置のコーナー強度が現在考察中のピクセル近傍でも依然として局所的な最大値をとるかどうか、さらに依然として最小強度の閾値を超えるかどうかを判断する。両方の条件を満たさない場合は、コーナーの位置が考察の対象から外される。すべてのコーナーの位置についての再検討が完了すると、総数が最大許容値を超えているかどうかをもう一度判断する。超えている場合は、半径を増分して前述の手順をもう一度繰り返す。コーナーの位置の数が最大許容数以内になるまでこの繰り返しのプロセスを継続する。この時点で、残っている特定された位置は別のコーナー特徴を代表する点として指定される。残っているコーナー特徴の位置については、それぞれ考察の対象となる特定された位置を中心とする所定のサイズの局所的な近傍に適合する2次元の正方形2Dquadraticの面で最大強度を示す位置を特徴に割り当てることで、各特徴の位置を調整できる。残っているコーナー特徴には向きも割り当てられる。本システムおよびプロセスの試験済みの実施形態において、この操作はぼかし勾配brurredgradientのアプローチを使用して実行される。最終的に、残っているコーナー特徴のそれぞれについて特定された位置は、該当するコーナー特徴に関して計算された向きの個別の特徴点として指定される。各特徴点の記述子を生成する操作に関して、この操作を実行するためには、まず考察対象の特徴点の位置を中心とする特徴点と同じ向きの所定のサイズpxpの記述子領域を確立する。次に、記述子領域より小さい所定のサイズdxdの記述子ベクトルが構成され、この領域内のピクセルの輝度に関する双線形補間を使用して領域のサンプリングが行われる。ただし、適切なピラミッドレベルからサンプリングすることで、エイリアシングを回避する。これで、記述子ベクトルがゲインとバイアスに関して標準化され、標準化された記述子ベクトルに対してハールHaarのウェーブレットの変換が行われ、変換ベクトルが生成される。画像間で実質的に一致する記述子を検出する操作に関して、一般にこの操作は変換された各記述子ベクトルを特徴空間featurespace内の所定の数の近傍領域とマッチングすることで実行される。このタスクを実行する1つの方法は、まず変換された個々の記述子ベクトルの最初の3つの非ゼロウェーブレット係数から3次元ハッシュテーブルを作成することである。次に、ハッシュテーブルの各ビンbinについて、ビン内で検出される3係数ベクトルthree-coefficientvector間の距離を計算する。3係数ベクトルのそれぞれが順に選択され、計算した距離に基づいて、同じビンに含まれるが選択されたベクトルと同じ画像には関連付けられていないその所定の数の近傍領域が特定される。これで、一致ベクトル候補potentiallymatchingvectorsの集合が構成される。こうした各集合内のベクトルに関連付けられた特徴点は、画像間で対応する点として指定される。本マッチング手順の試験済みの実施形態において、ハッシュテーブルは次元あたり10個のビンを備え、各ビンの範囲は半分が重複するように構成されている。各ベクトルの所定の数の近傍領域を特定する代わりに、一致ベクトル候補の集合を構成せずに、考察中のベクトルに関連付けられた画像以外の各画像に関連付けられた同じビン内にある近傍領域を画像ごとに所定の最大数まで特定してもよいことに留意されたい。一致ベクトル候補の各集合に含まれるベクトルに関連付けられた特徴点を対応する点として指定する操作において、誤って特定された一致を除去できる。このためには、一般に3係数ベクトルに関連付けられた特徴点が実際に同じベクトル集合内の別の3係数ベクトルに関連付けられた特徴点に対応しない場合は、一致ベクトルの候補としての考察対象からその3係数ベクトルを除外する必要がある。この操作はさまざまな方法で実行できる。1つの方法では、一致ベクトルの集合ごとに、まず集合のアウトライアoutlierの距離を計算し、次にこの集合内の任意の一致ベクトルについて計算した距離がアウトライアの距離の約65を超えるかどうかを判断する。一致ベクトルの距離がアウトライアの距離の約65を超えることがわかった場合は、対応する画像点としての考察からこれを除外する。この除去戦略は、アウトライアの距離に基づく拘束条件outlierdistanceconstraintを使用したアウトライア除去outlierrejectionと呼ばれる。誤った一致ベクトルを集合から除去する別の方法は、標準の幾何学的アウトライア除去手順を実行し、アウトライアであることが判明したベクトルに対応する点として関連付けられた特徴点を除去することである。本質的に、この幾何学的アウトライア除去手順には、2つの画像間ですべての点が最もよく一致する変換を検出する操作と、変換したときに所定の許容範囲内に対応しない点を除去する操作が含まれる。前述の除去技法の両方を採用することもできる。たとえば、本システムおよびプロセスの試験済みの実施形態においては、まずアウトライアの距離に基づく拘束条件を使用した除去戦略が採用され、続いて幾何学的アウトライア除去手順が採用された。以上に説明した効果に加えて、本発明のその他の利点は、以下の実施形態に関する説明と添付の図面を関連付けて参照することで明らかになるであろう。本発明の特定の機能、態様、および利点は、以下の実施形態の説明、前述の請求項、および添付の図面に関連して理解が深まるであろう。以下に示す本発明の好ましい実施形態の説明では、本明細書の要素となる添付の図面を参照する。こうした図面には、本発明を実施できる特定の実施形態が例として示されている。本発明の範囲を逸脱しない限り、他の実施形態を利用できること、および構造上の変更を適用できることは言うまでもない。1.0コンピューティング環境本発明の好ましい実施形態について説明する前に、本発明を実装できる適切なコンピューティング環境の簡単かつ一般的に説明する。図1は、適切なコンピューティングシステム環境100を示している。コンピューティングシステム環境100は適切なコンピューティング環境の1つの例にすぎず、本発明の使い方または機能の範囲に関するいかなる制限を示すものでもない。また、コンピューティング環境100は、例示的なオペレーティング環境100に示すコンポーネントの1つまたは組合わせに関して、依存性も要件もないものとする。本発明は、他のさまざまな汎用または専用のコンピューティングシステム環境または構成にも適用できる。本発明の使用に適した周知のコンピューティングシステム、環境、および/または構成の例には、パーソナルコンピュータ、サーバーコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家庭用電子機器、ネットワークPC、ミニコンピュータ、メインフレームコンピュータ、前述の任意のシステムまたはデバイスを含む分散コンピューティング環境などが含まれるが、これらに限定はされない。本発明は、プログラムモジュールのようにコンピュータで実行可能な命令をコンピュータで実行する一般的なコンテキストで説明できる。一般に、プログラムモジュールには、特定のタスクを実行したり、特定の抽象データ型を実装したりするルーチン、プログラム、オブジェクト、コンポーネント、データ構造などがある。本発明は、通信ネットワークを介してリンクするリモート処理装置でタスクを実行する分散コンピューティング環境でも実施できる。分散コンピューティング環境では、メモリ記憶装置を含むローカルとリモートの両方のコンピュータ記憶媒体にプログラムモジュールを格納できる。図1を参照すると、本発明を実施する例示的なシステムに、コンピュータ110の形で汎用コンピューティングデバイスが配置されている。コンピュータ110のコンポーネントには、処理装置120、システムメモリ130、さまざまなシステムコンポーネントシステムメモリや処理装置120などを接続するシステムバス121が含まれるが、それらに限定はされない。システムバス121は、さまざまなバスアーキテクチャの任意の1つを使用したメモリバスまたはメモリコントローラ、周辺バス、ローカルバスを含む各種バス構造のいずれでもよい。こうしたアーキテクチャには、例として、ISAIndustryStandardArchitectureバス、MCAMicroChannelArchitectureバス、EISAEnhancedISAバス、VESAVideoElectronicsStandardsAssociationローカルバス、PCIPeripheralComponentInterconnectバスメザニンMezzanineバスとも呼ばれるが含まれるが、これらに限定はされない。コンピュータ110は、通常はさまざまなコンピュータ可読媒体を備えている。コンピュータ可読媒体は、コンピュータ110からアクセスできる任意の使用可能な媒体でよい。揮発性と不揮発性の両方、および取り外し可能と不可能の両方の媒体が含まれる。例として、コンピュータ可読媒体にはコンピュータ記憶媒体および通信媒体を含めてもよいが、これらに限定はされない。コンピュータ記憶媒体には、コンピュータ可読の命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を記憶する任意の方法または技術で組み込まれた、揮発性と不揮発性の両方、および取り外し可能と不可能の両方の媒体が含まれる。コンピュータ記憶媒体には、RAM、ROM、EEPROM、フラッシュメモリなどのメモリ技術、CDROM、デジタル多用途ディスクDVD:digitalversatilediskなどの光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスクなどの磁気記憶装置、または必要な情報を格納でき、コンピュータ110からアクセスできる他の任意の媒体が含まれるが、これらに限定はされない。通信媒体は、搬送波やその他の搬送メカニズムのような変調データ信号に含まれるコンピュータ可読の命令、データ構造、プログラムモジュール、またはその他のデータなどを具体化したものであり、任意の情報伝達媒体を含む。変調データ信号という用語は、信号内の情報を符号化するように、1つまたは複数の特徴を設定または変更された信号を意味する。例として、通信媒体には、有線ネットワーク、直接ワイヤ接続などの有線媒体と、音、RF、赤外線などの無線媒体が含まれるが、これらに限定はされない。上記の任意の組合わせも、コンピュータ可読媒体の範囲内に含まれるものとする。システムメモリ130には、読み取り専用メモリROM:readonlymemory131やランダムアクセスメモリRAM:randomaccessmemory132のように揮発性および/または不揮発性メモリという形をとるコンピュータ記憶媒体が含まれる。起動時などにコンピュータ110内のエレメント間の情報転送を支援する基本ルーチンを含む基本入出力システム133BIOS:basicinput/outputsystemは、通常はROM131に格納される。RAM132には、通常はプロセッシングユニット520から直ちにアクセスできる、かつ/またはプロセッシングユニット120で現在操作しているデータおよび/またはプログラムモジュールが格納される。例として、図1にはオペレーティングシステム134、アプリケーションプログラム135、その他のプログラムモジュール136、およびプログラムデータ137が示すが、これには限定されない。コンピュータ110には、その他の取り外し可能/不可能、揮発性/不揮発性のコンピュータ記憶媒体を含めてもよい。単に例として、図1に取り外し不可能な不揮発性の磁気媒体の読み出しまたは書き込みを行うハードディスクドライブ141、取り外し可能な不揮発性の磁気ディスク152の読み出しまたは書き込みを行う磁気ディスクドライブ151、CDROMや他の光媒体のような取り外し可能な不揮発性の光ディスク156の読み出しまたは書き込みを行う光ディスクドライブ155を示す。例示的なオペレーティング環境で使用できる上記以外の取り外し可能/不可能、揮発性/不揮発性のコンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートRAM、ソリッドステートROMなどが含まれるが、それらに限定はされない。ハードディスクドライブ141は、通常はインターフェース140などの取り外し不可能なメモリインターフェースを介してシステムバス121に接続し、磁気ディスクドライブ151と光ディスクドライブ155は、通常はインターフェース150などの取り外し可能なメモリインターフェースを介してシステムバス121に接続する。図1に示す前述のドライブとこれに対応するコンピュータ記憶媒体には、コンピュータ可読の命令、データ構造、プログラムモジュールなど、コンピュータ110のデータを格納できる。たとえば、図1を参照すると、ハードディスクドライブ141にオペレーティングシステム144、アプリケーションプログラム145、その他のプログラムモジュール146、およびプログラムデータ147が格納されている。ただし、こうしたコンポーネントは、オペレーティングシステム134、アプリケーションプログラム135、その他のプログラムモジュール136、およびプログラムデータ137と同じでもよいし、異なっていてもよい。ここでは、オペレーティングシステム144、アプリケーションプログラム145、その他のプログラムモジュール146、およびプログラムデータ147には異なる番号を付けて、少なくとも別の複製であることを示している。ユーザーは、キーボード162やポインティングデバイス161などの入力装置一般に、マウス、トラックボール、またはタッチパッドと呼ばれるを使用してコンピュータ110にコマンドや情報を入力できる。他の入力装置図示せずには、マイクロフォン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどを含めてもよい。これらの入力装置および他の入力装置は、多くの場合にシステムバス121に接続されたユーザー入力インターフェース160を介して処理装置120に接続するが、パラレルポート、ゲームポート、USBuniversalserialbusのような他のインターフェースやバス構造によって接続してもよい。モニタ191または他のタイプの表示装置も、ビデオインターフェース190のようなインターフェースを介してシステムバス121に接続される。さらに、コンピュータには出力インターフェース195を介してスピーカー197やプリンタ196など、モニタ以外の出力周辺装置を接続できる。本発明において特に重要であるが、一連の画像193をキャプチャできるカメラ192デジタル/電子的スチールstillカメラまたはビデオカメラ、またはフィルムスキャナ/フォトスキャナfilm/photographicscannerを、パーソナルコンピュータ110の入力装置として備えていてもよい。さらに、パーソナルコンピュータ110の入力装置として1台のカメラが図示されているが、複数台のカメラを備えていてもよい。1台または複数台のカメラの画像193は、適切なカメラインターフェース194を介してコンピュータ110に入力される。このインターフェース194はシステムバス121に接続され、それによって画像をRAM132またはコンピュータ110に関連付けられた他のデータ記憶装置のいずれかにルーティングでき、格納できる。ただし、画像データは前述のコンピュータ可読媒体のいずれかからコンピュータ110に入力することもでき、カメラ192を使用する必要はない。コンピュータ110は、リモートコンピュータ180のような1台または複数台のリモートコンピュータへの論理接続を使用してネットワーク環境で動作できる。リモートコンピュータ180は、パーソナルコンピュータ、サーバー、ルータ、ネットワークPC、ピアデバイス、または他の一般のネットワークノードでよい。通常は、コンピュータ110に関連して上で説明したエレメントの多くまたはすべてが含まれるが、図1にはメモリ記憶装置181のみを示す。図1に示す論理接続には、ローカルエリアネットワークLAN:localareanetwork171とワイドエリアネットワークWAN:wideareanetwork173が含まれるが、他のネットワークを含めてもよい。このようなネットワーキング環境は、職場、企業規模のコンピュータネットワーク、イントラネット、およびインターネットではごく一般的である。LANネットワーキング環境で使用した場合、コンピュータ110はLAN171にネットワークインターフェースまたはアダプタ170を介して接続する。WANネットワーキング環境で使用する場合、コンピュータ110は一般にインターネットなどのWAN173を介して通信を確立するためのモデム172またはその他の手段を備えている。モデム172内蔵または外付けは、ユーザー入力インターフェース160または他の適切なメカニズムを使用してシステムバス121に接続できる。ネットワーク環境では、コンピュータ110またはその一部に関連して記述したプログラムモジュールをリモートメモリ記憶装置に格納できる。例として、図1にメモリデバイス181に格納されたリモートアプリケーションプログラム185を示すが、これには限定されない。図示されたネットワーク接続が例示的なものであり、コンピュータ間の通信リンクを確立する他の手段を使用してもよいことは言うまでもない。2.0マルチ画像特徴マッチングのシステムおよびプロセス例示的な動作環境について説明してきたが、本実施形態の節では、この後に本発明を実施するプログラムモジュールについて説明する。一般に、本発明によるシステムおよびプロセスには、場面を構成する複数の画像間で対応する点を特定する操作が含まれる。通常、これは図2のハイレベルhigh-level流れ図に示すように、以下のプロセス操作によって実現する。まず、画像ごとにさまざまな解像度で特徴点が特定されるプロセス操作200。特徴点は、画像内の位置がその点を中心とするあらかじめ指定されたサイズのピクセル近傍内のピクセルに起因するattributable少なくとも1つの属性で定義される点である。さらに、個々の特徴点はその点を中心とするピクセル近傍内のピクセルに起因する少なくとも1つの属性点の位置の定義に使用した属性と同じでもよいし、別の属性でもよいに基づいて一意の向きを割り当てることのできる点である。この第2の近傍は、点の位置の定義に使用したものと同じ所定のサイズの近傍でもよいし、別のサイズの近傍でもよい。特徴点が特定されると、プロセス操作202で特徴点ごとに記述子が確立する。この記述子は、画像の位置、向き、スケールの変化に対しても、この点の位置と向きを定義するためのピクセルの輝度の変化に対しても、実質的に不変である形で各点を特徴付ける。次に、画像間で実質的に一致する記述子の集合が特定されるプロセス操作204。最終的に、プロセス操作206で、一致する記述子の集合に関連付けられた、異なる画像中に現れる特徴点は、対応する点つまり、場面の同じ要素を表す点として指定される。まず、前述の特徴記述子で表される不変の特徴の新しいクラス一般に、輝度値のバイアス/ゲイン標準化パッチbias/gainnormalizedpatchofintensityvaluesであるについて説明し、続いて特徴マッチングスキーマについて説明する。2.1マルチスケール指向Multi-ScaleOrientedの特徴マルチスケールの有向特徴は、4つの幾何学的なパラメータと2つの光度測定のパラメータによって特徴付けられる。幾何学的なパラメータは、t1、t2、θ、l、すなわち画像内の領域またはパッチの中心の位置x、y、向き、スケールである。光度測定のパラメータは、α、β、すなわちパッチのゲインとバイアスである。こうした表現が指定されると、パッチのマッチングを行う6パラメータのシンプルなモデルが採用され、正しい一致と誤った一致に関するノイズ統計が分析される。これで、特徴ごとのアウトライアの距離に基づくシンプルな一致検証手順が得られる。より詳細には、対応する画像パッチ間の変換は次のように表される。I’x’=αIxβe1ただし、x’=Axt、である。エラーeはイメージングのノイズとモデリングのエラーを表す。特徴の中心の位置x、yは、この変換が適切に定義されたwelldefined点、すなわちIxの自動相関autocorrelationがピークに達している点に一致すると考えられる。こうした点の候補は、特徴点と呼ばれる。特徴を比較するために、原則的に2つの画像の位置同士の変換パラメータの最尤推定値を計算できる。ガウスのノイズGaussiannoiseを想定すると、非線形最小二乗問題を解くことでこの操作を繰り返し実行できる。ただし、効率を上げるために、各特徴を前述のモデルの不変要素で特徴付け、2つの特徴間のモデルパラメータに関する閉じた形の近似を使用してもよい。エラーeに関する統計を使用して、一致が正しいか誤りかを検証できる。2.1.1特徴点画像内には位置と向きの両方で特徴付けできる多くの点が存在するが[17]、本システムおよびプロセスの試験済みの実施形態について選択した特徴点は、いわゆるハリスのコーナーに関連付けられる。こうしたハリスのコーナーに一致する特徴点は、次のようにして検出される。入力画像Ix,yのそれぞれについて、低レベルのP0x,y=Ix,yと、以下のように高レベルのスムージングと二段抽出subsamplingの操作に関連するによって画像ピラミッドが構成される。lはピラミッドのレベル、gσx,yは標準偏差σのガウスカーネルを表す。二段抽出率subsamplingrates=2とピラミッドスムージングσp=1.0は、このピラミッド構成手順の試験済みの実施形態に適切に採用されている。ただし、一般にはsとして約1.1から3.0までの値を使用し、σpとして約0.55から1.5までの値を使用する。特徴点は、ピラミッドの各レベルから抽出される。レベル1と位置x,yのハリス行列Harrismatrixは、次のようにスムージングされた勾配gradientsの外積である。ただし、∇σは以下のようにスケールσでの空間微分spatialderivativeである。∇σfx,y∇fx,ygσx,y4試験済みの実施形態において、積分integrationスケールはσi=1.5に設定され、微分スケールσd=1.0に設定された。以下のコーナー検出関数が使用された。これは、Hの固有値λ1、λ2の調和平均である。試験済みの実施形態において、特徴点は、コーナー強度fHMx,yが局所領域中の極大値となり、その値が閾値10.0を超える所に位置すると仮定した。ただし、一般にはσiとして約0.5から2.5までの値を使用でき、σdとして約0.5から2.5までの値を使用できる。閾値は0以上の任意の値でよいことに留意されたい。前述の周囲の近傍のサイズについて簡単に説明する。前述の特徴点検出関数選択の理由は、Hと局所相関関数との関係によって理解できる。画像Ixに関して、1次テーラー展開Taylorexpansionによって以下の局所的な自動相関が得られる。特徴点は、自動相関関数のピークに位置する。これは、すべての単位ベクトルuについてeuが大きいことを意味する。つまり、Hの両方の固有値が大きいという要件と同等である。特徴点の位置を検出するには、調和平均関数harmonicmeanfunction以外のコーナー検出関数も使用できることに留意されたい。たとえば、いわゆるハリスの関数すなわち、fH=λ1λ2-0.04λ1λ22=detH-0.04trH2とShi-Tomasiの関数すなわち、fST=minλ1,λ2を代用してもよい。図3では、調和平均の特徴点検出関数のアイソコンターisocontourと、その他の関数のアイソコンターとを比較している。すべての検出関数において、2つの固有値が大きいことが要求される。予備試験Preliminaryexperimentsにより、3つの検出機能のそれぞれは概ね同じ性能を示すので、ほとんど同様に利用できることがわかっている。2.1.1.1適応非極大抑制AdaptiveNon-MaximalSuppression計算上の問題により、画像ごとに固定数の特徴点を生成するのが望ましい。画像内で空間的に適切に分散する特徴点を選択するために、適応非極大抑制の戦略を利用できる。より詳細には、特徴点はコーナー強度fHMに基づいて抑制され、半径rピクセルの近傍内で最大のもののみが保持される。画像からほぼ一定数nipの特徴点を抽出するために、非極大抑制半径rを検索できる。試験済みの実施形態において、初期値r=rinit=4.0を使用する。ただし、これはほぼ1から15までの範囲である。ここで、各画像からnipを超えない特徴点が抽出されるような連続する整数値がrの最大値として検索される。試験済みの実施形態ではnip=500である。ただし、一般にこの値は画像のサイズと状態natureによって、最小で約10から最大で数千に及ぶ。前述の方法で特徴点を空間的に分散すると、最大のコーナー強度に基づいて選択するのとは対照的に、画像の一致の脱落が少なくなる。2.1.1.2サブピクセルの精度2次元の正方形を局所的な近傍内のコーナー強度関数に適合させ、その最大値を検出することで、特徴点をサブピクセルの精度で配置し、よりよい結果を得ることができる。より詳細に記述すると以下のようになる。ただし、xは位置x,yを表し、fx=fHMxはコーナー強度の測定値である。試験済みの実施形態では、3x3の近傍が使用された。以下のように、ピクセルの相違を使用して3x3の近傍から微分が計算される。したがって、サブピクセル位置のコンポーネントxとyは次のように計算される。繰り返し精度は、変換された位置がある許容値まで正しい特徴点の割合として定義できる。前述の手順を使用してサブピクセルの局所化を行った場合と行わない場合の特徴点の繰り返し精度を図4に示す。サブピクセルの局所化によって繰り返し精度は約5向上することに注目されたい。2.1.2向き各特徴点には向きθがある。ただし、向きベクトルは次に示すスムージングされた局所的な勾配から得られる。試験済みの実施形態で使用した向きの積分スケールは、σo=4.5である。動きのフィールドmotionfieldulx,yが画像全体でスムーズに変化し、向きの評価が特徴点位置のエラーに左右されないようにするために、大きな微分スケールが望ましい。ただし、一般に向きの積分スケールは約2.0から7.0までである。本システムおよびプロセスの試験済みの実施形態では、ぼかし局所勾配blurredlocalgradientのアプローチを使用して個々の特徴点の向きを確定したが、その他の方法を利用してもよい。たとえば、向きを測定する方法には行列Hの勾配ヒストグラムまたは固有ベクトルの最大値を使用する方法がある。2.1.3記述子ベクトル向きのある特徴点x,y,l,θのそれぞれについて、記述子領域は検出スケールでatthedetectionscaleサイズpxpピクセルのベクトルのパッチである。パッチは、中心がx,y、向きが角度θである。このpxpの記述子領域から、サイズdxdピクセルの記述子ベクトルが構成される。試験済みの実施形態ではp=40、d=8である。ただし、一般にpは画像サイズの約0.1から10であり、dはつり合いのとれる値である。図6に山の場面を示す。ここでは、ピークの頂上にある特徴点に関連付けられた記述子領域が白いボックスで示されている。特徴点の位置をボックスの中心の白いドットで示しており、特徴点から伸びる線でこの点に割り当てられた向きを示している。図7は、図6の記述子領域から構成される8x8の記述子を示す図である。特徴点と向きを表すラインは、この図でも白で示されている。サンプリング時のエイリアシング/ブラーリングを回避するために、記述子はピラミッドレベルでサンプリングされる。これは、概ねピクセルあたり1回のサンプリングになる。これを実行する1つの方法は、検出スケールを超えるレベルlsのレベルから記述子をサンプリングすることである。記述子ベクトルは、双線形補間を使用してサンプリングされる。たとえば、試験済みの実施形態ではp=40、d=8、s=2であるが、ls=2レベルから記述子をサンプリングする。ただし、特徴点はレベルlで検出されたと仮定する。これで、から記述子をサンプリングすることになる。ただし、代わりにp’l1x,yただし、すなわちブラーリングはするがダウンサンプリングdownsamplingはしないからサンプリングする別の手順を使用すると、よりよい結果を得られる。さらに、小さなゲインでも、からのサンプリングによって作成される。2.1.3.1標準化次に、記述子ベクトルは以下のように平均が0で標準偏差が1になるように標準化される。di=d’i-μ/σ12ただし、d’i、i∈{1...d2}は記述子ベクトルの要素であり、、である。これで、特徴はアフィン変換に対して強度バイアスとゲインが不変になる。2.1.3.2ハールのウェーブレット変換Wavelet.Transform最後に、dxdの記述子ベクトルdi上でハールの変換が実行され、ウェーブレット係数ciを含むd2次元の記述子ベクトルを構成する。ハールのウェーブレットの直交性属性により、距離が維持される以下。したがって、2乗和の差の意味で近傍領域は変更されない。ただし、この後でshortly説明するインデックス戦略には、最初の3つの非ゼロウェーブレット係数c1、c2、c3が使用される。2.1.4記述子生成プロセスの概要特徴点を定義するハリスのコーナー特徴と、各特徴の向きを確定するぼかし局所勾配のアプローチを使用した本システムおよびプロセスの実施形態に従って特徴点ごとに記述子を生成する技術に関する以上の説明は、図5A~Cのプロセス流れ図に要約される。このプロセスは、画像内の特徴点を特定する操作で開始される。より詳細には、画像ごとに画像解像度のピラミッドを構成するプロセス操作500。次に、まだ選択されていないピラミッドレベルを選択しプロセス操作502、選択したレベルで個々のハリスのコーナーの位置を特定するプロセス操作504。次に、まだ選択されていないハリスのコーナーの1つを選択しプロセス操作506、コーナーの位置を表す特徴点を中心とした所定の最小近傍半径のピクセル近傍内で、選択したコーナーのコーナー強度が局所的な最大値かどうかを判断するプロセス操作508。選択したコーナーのコーナー強度が局所的な最大値の場合は、さらにこのコーナー強度が所定の最小強度閾値を超えるかどうかを判断するプロセス操作510。その場合は、選択したコーナーをコーナーの候補として指定しプロセス操作512、他のコーナーある場合について考察する。一方、コーナー強度が局所的な最大値でない場合、またはコーナー強度が所定の最小強度閾値を超えないことが確認された場合は、選択したコーナーを考察の対象から除外し、他のコーナーある場合について考察する。このように、いずれの場合も次の操作では考察対象としてまだ選択されていないコーナーがあるかどうかを判断するプロセス操作514。考察するコーナーが残っている場合は、前述のプロセスをプロセス操作506から繰り返す。それ以外の場合、プロセスはプロセス操作516に進み、ここで最後に使用した近傍半径を所定の整数値だけ増分するたとえば1ずつ。ここで、コーナーの候補のそれぞれについて、前述のスクリーニング手順を繰り返す。具体的には、まだ選択されていないコーナーの候補を選択しプロセス操作518、そのコーナー強度が現在の近傍半径の値で定義されるピクセル近傍内の局所的な最大値かどうかを判断するプロセス操作520。選択したコーナー候補のコーナー強度が局所的な最大値の場合は、さらにそれが所定の最小強度閾値を超えるかどうかを判断するプロセス操作522。その場合は、選択したコーナーを引き続きコーナーの候補として指定しプロセス操作524、他のコーナーある場合について考察する。一方、コーナー強度が局所的な最大値でない場合、またはコーナー強度が所定の最小強度閾値を超えないことが確認された場合は、選択したコーナー候補を考察の対象から除外し、他のコーナー候補ある場合について考察する。このように、いずれの場合も次の操作では考察対象としてまだ選択されていないコーナー候補があるかどうかを判断するプロセス操作526。考察するコーナーが残っている場合は、前述のプロセスの一部がプロセス操作518から繰り返される。考察するコーナーが残っていない場合は、次に引き続きコーナー候補として指定されているコーナーの数がまだ所定の最大許容値を超えるかどうかを判断するプロセス操作528。コーナー候補の最大許容値を超える場合は、コーナー候補の数が最大許容値以下になるまで、必要に応じてプロセス操作516から528を繰り返す。許容数のコーナー候補が残ると、プロセスは残っているコーナー候補のそれぞれの位置を定義する点を考察対象の画像の特徴点として指定する操作に進むプロセス操作530。次に、まだ選択されていない特徴点を選択しプロセス操作532、その位置を調整する。より詳細には、プロセス操作534で特徴点の位置を、選択した点を中心とする所定のサイズの局所的な近傍に適合する2次元の正方形2Dquadraticの面で最大強度を示す位置として指定する。選択した特徴点の調整された位置が確定した場合は、この点の向きを指定するプロセス操作536。前述のように、本発明の試験済みの実施形態において、この操作はぼかし勾配brurredgradientのアプローチを使用して実施している。次に、選択した特徴点の位置と向きを使用して、この点の記述子ベクトルを生成する。この操作を実行するためには、まず特徴点の位置を中心とする特徴点と同じ向きを向いた所定のサイズpxpの記述子領域またはパッチを確立するプロセス操作538。ここで、前述のように、強度の値をサンプリングする双線形補間を使用して記述子領域から所定のサイズdxdの小規模な記述子ベクトルが構成されるプロセス操作540。次に、この記述子ベクトルを標準化しプロセス操作542、ハールのウェーブレット変換を実行するプロセス操作544。変換された記述子ベクトルは、選択した特徴点の記述子を表す。ここで、まずまだ選択されていないコーナー候補が残っているかどうかを判断し、他の特徴点についてこのプロセスを実行するプロセス操作546。ある場合は、すべての特徴点が関連の変換コンポーネントされた記述子ベクトルを備えるまで、必要に応じてプロセス操作532から546を繰り返す。最後に、まずまだ選択されていないピラミッドレベルが残っているかどうかを判断し、画像ピラミッドの他のすべての解像度レベルについて記述子生成プロセスを繰り返すプロセス操作548。残っている場合は、必要に応じてプロセス操作502から548を繰り返す。完了すると、画像ピラミッド各レベルの特徴点のそれぞれについて、変換された記述子ベクトルが関連付けられている。前述のようにして特定された特徴点の向きを計算し、変換された記述子ベクトルを生成する代わりに、別のアプローチとして、バッチ方式ですべての特徴点を特定し、その向きを指定し、変換された記述子ベクトルを生成することもできる。2.2特徴マッチング場面の画像の集合に属するn個すべての画像から抽出されたマルチスケールの有向パッチが与えられた場合に、特徴マッチングの目標はすべての画像間で幾何学的に一貫した一致を検出することである。このタスクを実行するには、まず特徴マッチングの確率モデルを開発する。このモデルから、特徴の一致を検証するためのシンプルな拘束条件が得られる。これはアウトライアの距離に基づく拘束条件と呼ばれる。さらに、アウトライアの距離に基づく拘束条件と同時に、またはその代わりとして幾何学的拘束条件を適用してアウトライアを除去し、画像の一致を検出することもできる。2.2.1特徴マッチングのための確率モデルトレーニングデータから正しい一致と誤った一致のエラーの分布peimageを計算し、これを使用して特定の特徴の一致が正しいか誤りかを確率的に判断できることが理想的である。ただし、画像ベースのエラー、eimage=|I’x’-αIxβ|14は、特徴の一致が正しいか誤りかを判断するための評価基準metricとして適切ではない。実際に、|eimage|の値は正しい一致の場合と誤った一致の場合とで区別がない場合が多いので、一致が正しいか誤りかを判断するための閾値をとして|eimage|を指定できないことがわかっている。コントラストcontrastの変化によるパッチの近傍領域の一致に関連するエラーも問題である。正しい一致のエラーと誤った一致のエラーとの間には常に明らかな差があり、エラーのスケールは著しく変動することがわかっている。特に、コントラストの高いパッチではエラーが大きく、コントラストの低いパッチではエラーが小さい。したがって、コントラストの低いパッチが含まれる場合は、正しい一致と誤った一致の区別が難しくなる。考えられるソリューションの1つは、コントラストに関してパッチを標準化することである。これは、特徴空間におけるエラーの計算以下と同等である。efeatureの分布は正しい一致と誤った一致でより異なっているが、明らかな閾値はない。したがって、一致のエラーのサイズは単に比較する問題ではないと思われる。高周波数コンテンツhighfrequencycontentも重要であると考えられている。たとえば、勾配の大きな特徴は位置決め不良によるエラーが大きい。ただし、個々の特徴ベースでは、正しい一致と誤った一致に対応する特徴距離の二峰性分布が存在することがわかっている。実際に、誤った一致のクエリqueryからの距離はほとんど一定であると思われる。この現象は、シェル属性shellpropertyとして知られる高次元空間の属性に関連付けられると考えられる。高次元では、超球の体積volumeofahypersphereのほとんどは外側のシェルに集中している。つまり、ガウス分布のような一般的な分布では、確率質量probabilitymassのほとんどは外側のシェルに位置する。d次元超立方体内に一様に分布する点の集合について考察する。中心から距離rの範囲内にある点の数は、空間の境界に達するまでrdで増大し、境界に達すると急速に減少する。dが増大すると、ほとんどすべての点が特定のクエリ点から同じ距離にある、つまりクエリから一定の距離にある薄いシェル内に存在することになる。ただし、この距離の値は空間内のクエリ点の位置によって変わることに留意されたい。たとえば、端に近い点は中心の点より距離が大きい。Loweが提案するように[11]、第1の近傍領域1-NNの距離に基づく閾値は信頼できないが、第1の近傍領域の距離と第2の近傍領域の距離の比e1-NN/e2-NNは、一致が正しいかどうかを判断するための適切な評価基準である。マルチ画像マッチングの場合は、複数の正しい一致が存在する可能性があるので、代わりに比ei/eoutlierが検査される。ただし、eiは考察する一致の距離、eoutlierはアウトライアの距離である。特徴あたり最大k個の一致i∈{1...k}が存在すること、およびアウトライアの距離が近傍領域k1からknoの平均の距離として計算されることが仮定される。ベイズBayesの決定規則decisionruleを使用して一致を次のように分類できる。Pcorrecte/eoutlier>Pincorreete/eoutlier16これで、次の場合に特徴の正しい一致が区分されることになる。e<0.65xeoutlier17これはアウトライアの距離に基づく拘束条件と呼ばれる。最適なeoutlierの計算方法に関する問題が残る。σ’xefeature=eimageなので、アウトライアの距離を基準とする相対的な距離は特徴空間内では画像ベースの距離と同じである。したがって、特徴空間画像の距離を比較し、アウトライアの距離に基づく拘束条件を適用するだけでよく、ペアごとにα、βを計算する必要がないという利点がある。2.2.2アウトライア除去を使用した特徴マッチング特徴マッチング手順は、事前に計算された記述子ベクトルのそれぞれへの近傍領域の高速近似で開始される。こうした近傍領域ベクトルは、画像間で一致する点の候補を表している。次に、本特徴マッチング技術の試験済みの実施形態では、2段階のアプローチを使用して誤った一致を除去する。具体的には、前述のアウトライアの距離に基づく拘束条件を使用して誤った一致点を除去する非幾何学的なアウトライア除去技術を使用する。最終的に、標準の幾何学的アウトライア除去技術を使用して、まだ誤った一致点が残っている場合はさらにこれを除去する。ただし、前述のように、要求される精度や本特徴マッチング技術を採用するシステムの処理上の制限によっては、こうしたアウトライア除去技術のいずれかを省略してもよい。2.2.2.1ウェーブレットインデックスを使用した高速近似近傍領域FastApproximateNearestNeighborsすべての画像から特徴を抽出し、それぞれを特徴空間内のk個の近似近傍領域にマッチングする。高速近似近傍領域の計算は、ハッシュテーブルを使用して特徴にインデックス付けすることで実行される。ハッシュテーブルは3次元であり、各次元は最初の3つの非ゼロウェーブレット係数c1、c2、c3に対応する。こうした値は、パッチのの推定値である。試験済みの実施形態ではk=4であり、ハッシュテーブルは次元あたりb=10個のビンを備えている各次元の平均からの標準偏差±nσ=3を対象とする。ビンは半分が重複しているので、ビンの幅のの範囲内のデータは一致することが保証される。真の近傍領域は3つの次元のいずれかの外側に存在する可能性があるただし、確率は低いので、これらは近似近傍領域である。個々の記述子ベクトルをビン内のすべての特徴とマッチングし、k個の近似近傍領域を選択する。ここで、次に説明するように、アウトライアの距離に基づく拘束条件を使用して正しい一致が検証され、アウトライアが除去される。特徴間の距離を使用して近傍領域を決定することに留意されたい。試験済みの実施形態において、こうした距離は64次元の特徴ベクトルの二乗差の和で求められる。2.2.2.2アウトライアの距離に基づく拘束条件を使用したアウトライア除去誤った一致はほとんどすべてについてクエリ点からの距離アウトライアの距離がほぼ同等であるが、正しい一致はイメージングと検出のノイズによってのみ異なるので、前述のシェル属性をアウトライア除去戦略の基準として利用できる。アウトライアの距離を推定する1つの方法として、各画像の2-NN距離の平均値または最小値に一致させることが考えられる。計算したアウトライアの距離から、アウトライアの距離に基づく拘束条件を使用して誤った一致の数を削減できる。より詳細には、考察対象ベクトルの近傍領域の1つとして検出されたベクトルの考察対象ベクトルからの距離がアウトライアの距離の65以内にある場合は、このベクトルは一致点に関連付けられていると見なされる。ベクトルの距離がアウトライアの距離の約65を超える場合、このベクトルに対応する点は一致点とは見なされない。2.2.2.3幾何学的拘束条件を使用したアウトライア除去アウトライアの距離に基づく拘束条件を使用して一致の候補が調整された場合は、一致に関する幾何学的拘束条件を使用して一致をさらに調整することができる。基本的に、このためには、残っている一致点が場面の画像に実際に対応するかどうかを標準的な方法で判断する操作が必要である。画像が1つの点から取得され、場面が静的な場合は、パノラマ式の運動モデルpanoramicmotionmodelホモグラフィーhomographyが適している。画像が移動カメラから取得され、場面が静的な場合は、完全な3次元運動モデルfull3Dmotionmodel基本行列fundamentalmatrixが適している。複数のオブジェクトまたは移動するオブジェクトを扱うより複雑な運動モデルを開発してもよい。自動パノラマステッチでは、[6]に示すようにパノラマ式の運動モデルと確率モデルによるマッチングを選択するのが適切である。1つの画像内の点が場面の同じ要素を表す別の画像内の点と実際に一致しないと判断した場合は、この点が一致点の集合から除去される。2.2.3特徴マッチングプロセスの概要3次元ハッシュテーブルと少なくとも一部はアウトライアの距離に基づく拘束条件に基づくアウトライア除去とを使用した本システムおよびプロセスの実施形態に従って、場面の一連の画像間で対応する点を特定する特徴マッチング技術に関する以上の説明は、図11のプロセス流れ図に要約される。このプロセスは、変換された記述子ベクトルのそれぞれを、特徴空間におけるその所定の数の近傍領域とマッチングする操作で開始される。より詳細には、変換された個々の記述子ベクトルの最初の3つの非ゼロウェーブレット係数から3次元ハッシュテーブルを生成するプロセス操作1100。前述のように、本特徴マッチング手順の試験済みの実施形態において、ハッシュテーブルは次元あたり10個のビンを備えており、各ビンの範囲は半分が重複する。ここで、ハッシュテーブルの各ビン内にある3係数ベクトル間の距離を計算するプロセス操作1102。次に、記述子ベクトルのそれぞれについて、こうした距離を使用して、考察対象のベクトルと同じ画像内にはないが同じビンに含まれるその所定の数の近傍領域を特定するプロセス操作1104a。ここで、特徴マッチング技術の別の実施形態では、次の操作1104bをプロセス操作1104aで置き換えていることに注目する。すなわち、記述子ベクトルのそれぞれについて、その他の各画像から同じビン内の近傍領域を所定の最大数まで特定する。操作1104aと1104bが交換可能であることは、図11の破線のボックスで示されている。各記述子ベクトルの近傍領域が特定された場合は、まだ選択されていないベクトルを選択するプロセス操作1106。これで、関連の特徴点が選択したベクトルに関連する特徴点に実際に対応しない選択したベクトルの近傍領域記述子ベクトルは考察の対象から外される。より詳細には、本特徴マッチング技術の試験済みの実施形態において、この操作は前述のように2段階で実行される。第1段階プロセス操作1108は、アウトライアの距離に基づく拘束条件を使用したアウトライア除去と呼ばれており、対応しない可能性の高い点を除去する迅速な手順である。第2段階プロセス操作1110は、アウトライアの距離に基づく拘束条件を使用したアウトライア除去と呼ばれており、対応しない可能性の高い点を除去する迅速な手順である。ただし、第1段階で多くの誤った一致が除去されると、第2段階の処理の必要性は最小になる。本質的に、第2段階の幾何学ベースのアウトライア除去手順では、2つの画像間ですべての点の最適なマッチングを行う変換を検出する操作と、変換したときに特定の許容範囲内に対応しない点を除去する操作が実行される。図8Aと8Bは、アウトライア除去プロセスの効果valueの例を示している。2つの図は、共通する部分のある2つの山の場面を示しており、アウトライア除去プロセスを実行する前に特定された画像間の対応する位置を白いドットで示している587個の一致。図9Aおよび9Bは、図8Aおよび8Bと同じ画像を示しており、それぞれ、アウトライアの距離に基づく拘束条件を使用したアウトライア除去技法を適用した後である。ここで242個のアウトライアが除去され、345個の一致が残っている。図10Aおよび10Bは、図9Aおよび9Bと同じ画像を示しており、それぞれ幾何学ベースのアウトライア除去技法を適用した後である。さらに34のアウトライアが特定されて除去され、最終的に画像間で合計311個の対応する点が残っている。本特徴マッチング技術の特定の適用において、第1段階のアウトライア除去手順で十分に正しい結果が得られる場合は、必要に応じて第2段階を省略してもよい。逆に、処理コストが問題でない場合は、第2段階の幾何学ベースのアウトライア除去手順を単独で使用し、第1段階を省略してもよい。第1のアウトライア除去手順に関して、試験済みの実施形態ではこのためにまず選択した記述子ベクトルとその近傍領域との距離を計算する操作を実行し、次に選択した記述子ベクトルとそのいずれかの近傍領域との距離がアウトライアの距離の約65以上であるかどうかを判断する操作を実行する。近傍領域ベクトルから選択されたベクトルまでの距離がアウトライアの距離の約65以上であると判断した場合は、必ず選択されたベクトルに関連付けられた特徴点を表す考察の対象からこれを除外する。アウトライア除去手順が完了すると、選択したベクトルの近傍領域として特定された記述子ベクトルに関連付けられており、考察の対象から外されていない特徴点のそれぞれは、選択されたベクトルに関連付けられた特徴点に対応する点として指定されるプロセス操作1112。次に、その他の記述子ベクトルのそれぞれについて前述のプロセスを実行し、まずまだ選択されていないベクトルが残っているかどうかを判断し、その他の画像内の対応する点を特定するプロセス操作1114。残っている場合は、すべてのベクトルが処理されるまで、必要に応じてプロセス操作1106から1114を繰り返す。すべてのベクトルが選択され、処理されると、手順は終了する。3.0参考文献"