(57)【要約】      （修正有）【課題】第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を決定するためのカメラ姿勢推定方法を提供する。【解決手段】第１の位置で捕捉された第１の画像と第２の位置で捕捉された第２の画像とから特徴を抽出することと、抽出された特徴が、場所、スケール情報、および記述子を備え、該記述子が、第１の画像からの特徴を第２の画像からの特徴にマッチングさせることができる情報を備え、一致した特徴を生成するために第１の画像と第２の画像との間で特徴をマッチングさせ、一致した特徴の深度比をスケール情報から決定し、該深度比が、ｎ個の一致した特徴を選択することと、一致した特徴のうちの少なくとも１つが深度比と場所の両方により選択される、スケール情報から導出された深度比をもつ選択された一致した特徴を使用して、第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を計算することとを備える。【選択図】図３
2019021291.tif 000002
【特許請求の範囲】
【請求項１】
第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を決定するためのカメラ姿勢推定方法であって、
第１の位置で捕捉された第１の画像と第２の位置で捕捉された第２の画像とから特徴を抽出することと、ここにおいて、前記抽出された特徴が、場所、スケール情報、および記述子を備え、前記記述子が、前記第１の画像からの特徴を前記第２の画像からの特徴にマッチングさせることができる情報を備える、
前記第１の画像と前記第２の画像との間で特徴をマッチングさせ、一致した特徴を生成することと、
一致した特徴の深度比を前記スケール情報から決定することと、ここにおいて、前記深度比が、前記第２の位置からの一致した特徴の深度に対する前記第１の位置からの一致した特徴の深度の比である、
ｎ個の一致した特徴を選択することと、ここにおいて、前記一致した特徴のうちの少なくとも１つが前記深度比および前記場所の両方により選択される、
前記スケール情報から導出された前記深度比をもつ前記選択された一致した特徴を使用して、前記第１のカメラ姿勢と前記第２のカメラ姿勢との間の前記平行移動および前記回転を計算することと
を備える、方法。
【請求項２】
前記一致した特徴を選択することが、ｎ個の一致した特徴を選択することを備え、ここにおいて、ｎは４以下の整数であり、前記ｎ個の一致した特徴のうちのｍ個が、前記深度比と前記場所の両方により選択され、ｐ個の特徴が、前記深度比ではなく場所情報により選択され、ｍおよびｐは、関係式２ｍ＋ｐ＝５を満たす整数である、請求項１に記載の方法。
【請求項３】
ｍ＝１およびｐ＝３である、請求項２に記載の方法。
【請求項４】
ｍ＝２およびｐ＝１である、請求項２に記載の方法。
【請求項５】
前記深度比に関連する情報が、スケール比から導出される、請求項１に記載の方法。
【請求項６】
前記深度比が、前記特徴から直接抽出される、請求項１に記載の方法。
【請求項７】
ロバスト推定器を使用してモデルを改良することをさらに備える、ここにおいて、モデルパラメータが、前記第１のカメラ位置と前記第２のカメラ位置との間の前記計算された平行移動および回転である、請求項１に記載の方法。
【請求項８】
前記ロバスト推定器を使用することが、
前記モデルパラメータを最良モデルの最良モデルパラメータとして設定することと、
前記最良モデルの適合度を評価することと、
ｎ個の一致した特徴の新しいセットを選択し、新しいモデルパラメータを計算して、新しいモデルを生成することと、
前記新しいモデルの適合度を評価することと、
前記新しいモデルの前記適合度が前記最良モデルの前記適合度よりも良好である場合に、前記新しいモデルパラメータで前記最良モデルパラメータを更新することと、
ｎ個の一致した特徴の新しいセットを選択して新しいモデルを生成することと、前記新しいモデルの前記適合度を評価することと、前記新しいモデルの前記適合度が前記最良モデルの前記適合度よりも良好である場合に、前記新しいモデルパラメータで前記最良モデルパラメータを更新することとのプロセスを、停止基準が達せられるまで連続的に繰り返すことと
を備える、
請求項７に記載の方法。
【請求項９】
前記適合度が、インライアの数を計算することによって評価される、請求項８に記載の方法。
【請求項１０】
前記一致した特徴の深度比に関連する前記情報に誤差があることが仮定され、
前記モデルの前記適合度を評価することが、前記特徴から得られた前記深度比、正の誤差値をもつ前記深度比、および負の誤差値をもつ前記深度比に対する前記モデルの前記適合度を評価することを備え、
前記方法が、
前記特徴から得られた前記深度比、正の誤差値をもつ前記深度比、および負の誤差値をもつ前記深度比から選択された３つの値のうちのどれが最良の適合度を生じたかに依存して、前記これらの３つの値のうちの１つにより前記深度比を更新することと、
新しい誤差値を設定することと、ここにおいて、前記新しい誤差値が現在の誤差値を２で割ったものである、
前記新しい誤差値を使用して前記モデルの前記適合度を評価することと
をさらに備える、
請求項８に記載の方法。
【請求項１１】
前記インライアの数が、深度と場所の両方に対して計算される、請求項９に記載の方法。
【請求項１２】
より良好なモデルを見つけ出す可能性が閾値を下回るとき、前記停止基準が設定される、請求項８に記載の方法。
【請求項１３】
前記第１の画像が第１のカメラによって捕捉され、前記第２の画像が第２のカメラによって捕捉され、前記第１のカメラと前記第２のカメラとが異なる、請求項１に記載の方法。
【請求項１４】
前記第１の画像および前記第２の画像がビデオカメラによって捕捉される、請求項１に記載の方法。
【請求項１５】
前記ビデオカメラが移動車両に備えられる、請求項１４に記載の方法。
【請求項１６】
前記車両の軌跡が、前記第１のカメラ姿勢と前記第２のカメラ姿勢との間の前記計算された平行移動および回転から決定される、請求項１５に記載の方法。
【請求項１７】
ビデオカメラを使用してＳＬＡＭ（ｓｉｍｕｌｔａｎｅｏｕｓ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ｍａｐｐｉｎｇ）を実行する方法であって、前記ビデオカメラの姿勢が請求項１に記載の方法を使用して推定される、方法。
【請求項１８】
物体の３Ｄモデルを決定する方法であって、
移動カメラを使用して前記物体の複数の画像を捕捉することと、
前記物体の点群を発生することと、ここにおいて、前記点群が前記カメラの姿勢を使用して三角測量から決定される、
を備え、
前記カメラの前記姿勢が、請求項１に記載の前記方法によって推定される、方法。
【請求項１９】
第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を決定するためのカメラ姿勢推定装置であって、
前記装置がプロセッサを備え、前記プロセッサが、
第１の位置で捕捉された第１の画像と第２の位置で捕捉された第２の画像とから特徴を抽出し、ここにおいて、前記抽出された特徴が、場所、スケール情報、および記述子を備え、前記記述子が、前記第１の画像からの特徴を前記第２の画像からの特徴にマッチングさせることができる情報を備える、
前記第１の画像と前記第２の画像との間の特徴をマッチングさせ、一致した特徴を生成し、
前記一致した特徴の深度比を前記スケール情報から決定し、ここにおいて、前記深度比が、前記第２の位置からの一致した特徴の深度に対する前記第１の位置からの一致した特徴の深度の比である、
ｎ個の一致した特徴を選択し、ここで、前記一致した特徴のうちの少なくとも１つが前記深度比と前記場所の両方により選択される、
前記スケール情報から導出された深度比をもつ前記選択された一致した特徴を使用して、前記第１のカメラ姿勢と前記第２のカメラ姿勢との間の前記平行移動および前記回転を計算する
ように構成される、
カメラ姿勢推定装置。
【請求項２０】
請求項１に記載の前記方法をコンピュータに実行させるように構成されたコンピュータ可読コードを備える非一時的キャリア媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で説明される実施形態は、一般に、コンピュータビジョンの分野に関する。
【背景技術】
【０００２】
相対姿勢推定は何世紀にもわたって研究されており、最初は写真で、後にはコンピュータビジョンコミュニティで研究されている。それにもかかわらず、ストラクチャフロムモーションおよびＳＬＡＭ（ｓｉｍｕｌｔａｎｅｏｕｓ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ｍａｐｐｉｎｇ）における多くの最新技術用途との基本的な関連により、研究が近年常に発展している。相対姿勢の中心課題は、２つのカメラ姿勢の間の動きを推定し、環境の３Ｄ再構築ならびにカメラオドメトリを明らかにすることである。
【０００３】
古典的手法は、多数のビューの点対応（point correspondence）の場所と、それらの姿勢回復との関係とを研究している。未知の固有較正の場合には、基礎行列を回復するために８点アルゴリズムまたは７点アルゴリズムが最も頻繁に利用され、６点アルゴリズムは未知の焦点距離に対して使用される。較正済みカメラでは、５点アルゴリズムが最も好適である。
【図面の簡単な説明】
【０００４】
【図１（ａ）】カメラを有する自動車の概略図。
【図１（ｂ）】軌跡を決定するためおよび３Ｄモデルを決定するためのステップを示す基本的フロー図。
【図２】一実施形態による、方法を実行するために使用され得る装置の概略図。
【図３】一実施形態による方法を示すフロー図。
【図４】図４（ａ）は、特徴抽出を説明するために使用される２つの画像を示す。図４（ｂ）は、標準３Ｄ点三角測量の図。図４（ｃ）は、図４（ｂ）の深度比の使用を示す図。図４（ｄ）は、図４（ｂ）の構成から未知数の数を減少させるために深度比をどのように使用できるかを示す図。
【図５】ＲＡＮＳＡＣフレームワークが利用される一実施形態による方法を示すフロー図。
【図６】スケール誤差が修正される、図５のフロー図の変形を示すフロー図。
【図７（ａ）】スケール誤差を修正するプロセスをより詳細に示すフロー図。
【図７（ｂ）】スケール誤差を修正するプロセスをより詳細に示すフロー図。
【図８】カメラ位置およびカメラパラメータを示す図。
【図９（ａ）】場所測定の際にノイズがある場合の基本行列に対して得られた誤差を示す図。
【図９（ｂ）】場所測定の際にノイズがある場合の平行移動に対して得られた誤差を示す図。
【図９（ｃ）】場所測定の際にノイズがある場合の回転に対して得られた誤差を示す図。
【図１０（ａ）】場所測定の際にノイズがある場合の基本行列に対して得られた誤差を示す図。
【図１０（ｂ）】場所測定の際にノイズがある場合の平行移動に対して得られた誤差を示す図。
【図１０（ｃ）】場所測定の際にノイズがある場合の回転に対して得られた誤差を示す図。
【図１１（ａ）】２＋１アルゴリズムについて、２つのスケール比に対する基本行列の誤差へのスケール効果を示す図。
【図１１（ｂ）】２＋１アルゴリズムについて、２つのスケール比に対するエピポーラ制約の平均誤差へのスケール効果を示す図。
【図１１（ｃ）】図１１（ａ）のデータの中央スライスを示す図。
【図１１（ｄ）】図１１（ｂ）のデータの中央スライスを示す図。
【図１１（ｅ）】１＋３アルゴリズムについて、スケール比に対する基本行列の誤差へのスケール効果を示す図。
【図１１（ｆ）】１＋３アルゴリズムについて、スケール比に対するエピポーラ制約の平均誤差へのスケール効果を示す図。
【図１２】スケールインライアと場所インライアの比が示されている６対の画像を示す図。各対の画像はスケールダイバージェンス（scale divergence）の関連するヒストグラムとともに示される。
【図１３】図１２の対の画像の各々に対する場所ベースインライア比を示すヒストグラム。
【発明を実施するための形態】
【０００５】
一実施形態において、第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を決定するためのカメラ姿勢推定方法が提供され、
この方法は、
第１の位置で捕捉された第１の画像と第２の位置で捕捉された第２の画像とから特徴を抽出することと、抽出された特徴は、場所、スケール情報、および記述子を備える、記述子は、第１の画像からの特徴を第２の画像からの特徴にマッチングさせることができる情報を備える、
一致した特徴を生成するために第１の画像と第２の画像との間で特徴をマッチングさせることと、
一致した特徴の深度比をスケール情報から決定することと、ここにおいて、深度比は、第１の位置からの一致した特徴の深度と第２の位置からの一致した特徴の深度の比である、
ｎ個の一致した特徴を選択することと、ここで、一致した特徴のうちの少なくとも１つが深度比と場所の両方により選択される、
スケール情報から導出された深度比をもつ選択された一致した特徴を使用して、第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を計算することとを備える。
【０００６】
特徴検出器は、コーナー、テクスチャ、または独特の外観をもつ領域などの画像データ中の関心点を見つけ出す。特徴検出器は、別の視点から同様の検出を再現することができる。例示の特徴検出器は、Ｆａｓｔ、Ｈａｒｒｉｓ  Ｃｏｒｎｅｒs、ガウス差分を含む。これらの各々は、通常、画像のスケール空間ピラミッドに適用され、その結果、スケールを提供するか、または深度センサを利用してスケールを直接推定する。したがって、特徴検出器は、場所とスケール情報とを与えることができる。
【０００７】
特徴記述子が特徴の外見を記述するために使用され、その結果、それは、第２の画像の特徴と比較することができる。ＳＩＦＴ、ＳＵＲＦ、およびＯＲＢは、ほとんどビュー方向依存性がない既知の記述子である。
【０００８】
深度情報を使用することによって、場所のみを備える５点を使用する代わりに、それらの点のうちの１つまたは複数から深度情報が使用される場合、少ない数の点を使用することが可能である。上述の方法は、特徴検出の間に導出されたスケール情報から深度を導出する。特徴検出器は、位置ｘ、ｙおよびスケールｓを抽出する。この情報は、場所ｘ、ｙにおける既定のサイズ*ｓの長方形を定義するために使用することができる。長方形は、特徴記述子を実行するために使用される。
【０００９】
一般に、５点を使用する姿勢推定の間、場所または座標情報のみが使用される。特徴検出の間に抽出されたスケール情報は廃棄される。
【００１０】
したがって、一実施形態では、一致した特徴を選択することは、ｎ個の一致した特徴を選択することを備え、ここで、ｎは４以下の整数であり、前記ｎ個の一致した特徴のうちのｍ個は、深度比と場所とに関連する両方の情報により選択され、ｐ個の特徴が、深度比に関連する情報ではなく場所情報により選択され、ｍおよびｐは、関係式２ｍ＋ｐ＝５を満たす整数である。
【００１１】
深度比に関連する情報はスケール比とすることができ、または深度比自体が特徴から直接抽出され得る。本明細書の全体にわたって、深度比とスケール比とは交換可能に使用される。
【００１２】
実際には、特徴が一致するとき、誤差があることがある。したがって、一実施形態では、平行移動および回転の多数の推定が得られ、最良の推定が選択される。このタイプのデータはアウトライアの傾向があるので、ロバスト推定フレームワークが使用され得る。それゆえに、一実施形態では、この方法は、ロバスト推定器を使用してモデルを改良することをさらに備える、ここにおいて、モデルパラメータは、第１のカメラ位置と第２のカメラ位置との間の計算された平行移動および回転である。
【００１３】
可能な推定フレームワークは、
モデルパラメータを最良モデルの最良モデルパラメータとして設定することと、
最良モデルの適合度を評価することと、
新しいモデルを生成するために、ｎ個の一致した特徴の新しいセットを選択し、新しいモデルパラメータを計算することと、
新しいモデルの適合度を評価することと、
新しいモデルの適合度が最良モデルの適合度よりも良好である場合新しいモデルパラメータで最良モデルパラメータを更新することと、
新しいモデルを生成するために、ｎ個の一致した特徴の新しいセットを選択すること、新しいモデルの適合度を評価すること、および新しいモデルの適合度が最良モデルの適合度よりも良好である場合新しいモデルパラメータで最良モデルパラメータを更新することのプロセスを、停止基準が達せられるまで連続的に繰り返すことと
を備えることができる。
【００１４】
さらなる実施形態では、ランダムサンプルコンセンサス（ＲＡＮＳＡＣ）タイプフレームワークが使用される。ここで、適合度は、インライアの数を計算することによって評価され、一致した特徴の各セットがランダムに選択される。
【００１５】
一実施形態では、インライアの数は、深度と場所の両方に対して計算される。
【００１６】
停止基準は、いくつかの方法で決定され得る。一実施形態では、固定数の反復がある場合があり、またはより良好なモデルを見いだす可能性が閾値を下回ったときプロセスが停止される場合がある。
【００１７】
高解像度画像では、特徴検出器は、場所に関してかなり信頼性が高い。残念ながら、スケールの推定は、安定性が低く、スケール空間ピラミッドで使用されるステップサイズまたは深度センサの品質に依存する。
【００１８】
さらなる実施形態では、一致した特徴の深度比に関連する情報に誤差があることが仮定され、
ここにおいて、モデルの適合度を評価することが、特徴から得られた深度比、正の誤差値をもつ深度比、および負の誤差値をもつ深度比に対するモデルの適合度を評価することを備え、
この方法は、
特徴から得られた深度比、正の誤差値をもつ深度比、および負の誤差値をもつ深度比から選択された３つの値のうちのどれが最良の適合度を生成したかに応じて、これらの３つの値のうちの１つにより深度比を更新することと、
新しい誤差値を設定することと、新しい誤差値が現在の誤差値を２で割ったものである、
新しい誤差値を使用してモデルの適合度を評価することと
をさらに備える。
【００１９】
上述の方法は、
１．スケールおよび対応の場所による相対姿勢推定
ａ．ＳＬＡＭ（ｓｉｍｕｌｔａｎｅｏｕｓ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ｍａｐｐｉｎｇ）
ｂ．３Ｄモデル発生
２．信号入力に対するオドメトリ推定
ａ．単眼カメラからのスケール比
ｂ．ステレオカメラまたはＲＧＢ−Ｄカメラからの深度比
３．自動運転＋ドライバ支援システム
ａ．車両の軌跡の高速推定
ｂ．車両の３Ｄ位置および３Ｄ方位の推定
のために使用され得る。
【００２０】
一実施形態では、第１の画像は第１のカメラによって捕捉され、第２の画像は第２のカメラによって捕捉され、第１のカメラと第２のカメラとは異なる。各カメラはそれ自体の較正行列を有するので、この方法は２つの異なるカメラに対処することができる。
【００２１】
しかしながら、多くの実施形態では、同じカメラが使用されることになる。カメラはビデオカメラとすることができ、異なる画像は異なるフレームに対応する。そのようなカメラは、移動車両、例えば、自動車、トラック、ロボット、ドローン、家電製品などに備えることができる。
【００２２】
車両の軌跡は、第１のカメラ姿勢と第２のカメラ姿勢との間の計算された平行移動および回転から決定される。
【００２３】
カメラ姿勢を推定する方法は、カメラの位置をいわゆるＳＬＡＭ（ｓｉｍｕｌｔａｎｅｏｕｓ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ｍａｐｐｉｎｇ）システム（ＳＬＡＭ）で決定するために使用され得る。
【００２４】
上述の方法は、さらに、物体の３Ｄモデルを決定するために使用され得、この方法は、
移動カメラを使用して物体の複数の画像を捕捉することと、
物体の点群を発生することと、点群はカメラの姿勢を使用して三角測量から決定される、
を備え、
ここにおいて、カメラの姿勢は上述の方法によって推定される。
【００２５】
さらなる実施形態において、第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を決定するためのカメラ姿勢推定装置が提供され、
この装置はプロセッサを備え、プロセッサは、
第１の位置で捕捉された第１の画像と第２の位置で捕捉された第２の画像とから特徴を抽出し、抽出された特徴は、場所、スケール情報、および記述子を備える、記述子は、第１の画像からの特徴を第２の画像からの特徴にマッチングさせることができる情報を備える、
一致した特徴を生成するために第１の画像と第２の画像との間の特徴をマッチングさせ、
一致した特徴の深度比をスケール情報から決定し、ここにおいて、深度比は、第１の位置からの一致した特徴の深度と第２の位置からの一致した特徴の深度の比である、
ｎ個の一致した特徴を選択し、ここで、一致した特徴のうちの少なくとも１つが深度比と場所の両方により選択される、
スケール情報から導出された深度比をもつ選択された一致した特徴を使用して、第１のカメラ姿勢と第２のカメラ姿勢との間の平行移動および回転を計算する
ように構成される。
【００２６】
実施形態によるいくつかの方法はソフトウェアで実施され得るので、いくつかの実施形態は、汎用コンピュータに供給されるコンピュータコードを任意の好適なキャリア媒体に含む。キャリア媒体は、フロッピー（登録商標）ディスク、ＣＤ  ＲＯＭ、磁気デバイス、もしくはプログラマブルメモリデバイスなどの任意の記憶媒体、または任意の信号、例えば、電気信号、光信号、もしくはマイクロ波信号などの任意の一時的媒体を含むことができる。
【００２７】
図１（ａ）は、自動車５０の動きを示す。自動車はカメラを備えている。自動車の動きに伴い、カメラは異なる位置から画像を捕捉する。
【００２８】
自動運転の分野において、またはさらに駐車支援のために、車両は環境内でそれ自体の場所を特定できる必要がある。例えば、自動車が道路に沿って前進できるためには、自動車は、道路の画像を捕らえ、道路に対する自動車の位置を決定できる必要がある。
【００２９】
図１（ａ）において、一例として、自動車は、位置５１において第１の画像（画像１）および位置５３において第２の画像（画像２）を捕らえる。両方の画像は特徴点５５を捕捉する。次いで、特徴点が２つの画像の間で一致され得、第１の位置から第２の位置までのカメラの姿勢が決定され得る。
【００３０】
図１（ｂ）はフロー図を示す。画像１および画像２が上述のように捕捉される。上述のように、特徴検出器は、通常、画像のスケール空間ピラミッドに適用される。特徴が抽出される。次に、特徴マッチング（突き合せ）が行われる。
【００３１】
上述したように、ひとたび特徴が一致したならば、カメラの相対姿勢を推定することが可能である。これにより、自動車の場所、自動車の軌跡などが分かる。これは、さらに、オドメトリで使用され得る。
【００３２】
上述のシステムは、さらに、３Ｄモデルを生成するために使用され得る。ひとたびカメラの姿勢が分かれば、カメラによって捕捉された画像から、三角測量を使用して３Ｄモデルを構築することが可能である。
【００３３】
図２は、システム分析ユニット２０の可能な基本構造を示す。分析ユニット２０は、プログラム２５を実行するプロセッサ２３を備える。分析ユニット１３は記憶装置２７をさらに備える。記憶装置２７は、カメラから受け取ったデータを分析するためにプログラム２５によって使用されるデータを記憶する。
【００３４】
分析ユニット２０は、入力モジュール３１と出力モジュール３３とをさらに備える。入力モジュール３１はカメラ入力部３５に接続される。カメラ入力部３５はカメラ（図示せず）からのカメラデータを受け取る。カメラ入力部３５は、単に、カメラからデータを直接受け取ることができ、または代替として、カメラ入力部３５は、外部記憶媒体またはネットワークからカメラデータを受け取ることができる。
【００３５】
一実施形態では、ディスプレイ３７が出力モジュール３３に接続される。ディスプレイ３７は、カメラ入力部３５で受け取られたカメラデータから発生された捕捉３Ｄ画像を表示するために使用され得る。ディスプレイ２７の代わりに、出力モジュール３３は、ファイルに、またはインターネットなどを介して出力することができる。
【００３６】
図３は、カメラ姿勢の推定を得るステップを示す基本的フロー図である。ステップＳ１０１において、２Ｄ画像が、移動カメラによって捕捉される。そのような画像の一例が図４（ａ）に示される。
【００３７】
次に、ステップＳ１０３において、特徴が２つの画像から抽出される。図４（ａ）の２つの図を見ると、左上の窓が、特徴を抽出する一例として使用されている。
【００３８】
既知のアルゴリズムが、特徴を抽出するために使用され得る。抽出された特徴がスケールを含んでいる場合には、任意の特徴抽出アルゴリズムが使用され得る。一般に、特徴抽出器は、構造のコーナーまたは他の際立った特徴を識別することになる。
【００３９】
次に、ステップＳ１０５において、特徴がマッチングされる。２つのビュー中のＮ個の一致点は、それぞれ同次ベクトルｘi＝［ｘi  ｙi  １］Tおよび
【数１】
2019021291.tif 000003
によって表される。各フレームの３Ｄ座標系における対応する３Ｄ点は、ｄiｘiまたは
【数２】
2019021291.tif 000004
によって見いだされ、ここで、ｄiおよび
【数３】
2019021291.tif 000005
は、関連するビューから観察される点の深度を表す。
【００４０】
画像間の相対姿勢が回転
【数４】
2019021291.tif 000006
および平行移動
【数５】
2019021291.tif 000007
によって表される場合、一般性を失うことなく、内部較正行列Ｋが同一であると仮定することができる。
【００４１】
したがって、エピポーラ制約は、
【数６】
2019021291.tif 000008
で与えられ、ここで、ｔと任意のベクトル
【数７】
2019021291.tif 000009
との間の外積は、［ｔ］×ａ＝ｔ×ａで表される。上記のように、記述子はスケールも抽出する。２つのビューからの対応
【数８】
2019021291.tif 000010
の深度ｄiと深度
【数９】
2019021291.tif 000011
との間の比
【数１０】
2019021291.tif 000012
から、平行移動
【数１１】
2019021291.tif 000013
の方向が、回転Ｒによって、
【数１２】
2019021291.tif 000014
として決定されることが確認され得る。上述のことが、図４（ｂ）から図４（ｄ）に図によって示されている。それゆえに、１つの既知の対応（ｘ，ｘ’，ｓ）を用いて、（１）を、
【数１３】
2019021291.tif 000015
として、
【数１４】
2019021291.tif 000016
に対する等式ａTｂ＝ｂTａ、ａT（ｂｘｃ）＝ｂT（ｃｘａ）、およびＲ（ａｘｂ）＝ＲａｘＲｂを使用して書き直すことが可能である。（３）を等式
【数１５】
2019021291.tif 000017
として書き直すことは背後の直観を明らかにし、すべてのエピポーラ平面は、平行移動ｔ、言い換えるとベクトル（ｘ’−ｓＲｘ）を含まなければならないことに留意されたい。さらに、（３）は、深度比をもつすべての対応
【数１６】
2019021291.tif 000018
が、
【数１７】
2019021291.tif 000019
を満たすことを必要とし、ここで、
【数１８】
2019021291.tif 000020
である。したがって、（４）は、エピポーラ制約を（３）を介して強制するだけでなく、三角形の正弦法則が有効であることも保証する。上述の式（３）および式（４）は、以下で説明するような最小ソルバを提案するために利用される。
【００４２】
ＳＩＦＴ、ＯＲＢなどの上記の記述子は、いわゆるスケール空間ピラミッドマッチングに依存する。具体的には、これらの方法は、本質的に、場所情報に加えて、一致した特徴の間のスケール差を提供する。ステップＳ１０９において、スケール情報が、深度情報を導出するために抽出されることになる。
【００４３】
画像平面上の既知のスケール比は、深度比に緊密に関連づけられる。実際、スケール比は同次座標空間における深度比の逆数であり、
【数１９】
2019021291.tif 000021
である。スケール、言い換えると深度値の間のこの比は、以下では
【数２０】
2019021291.tif 000022
として表すことがある。
【００４４】
正確には、スケールを考慮して相対姿勢問題を解く２つの最小セットがある。カメラの間の移行を表す未知数は、全体で、回転に対して３つおよび平行移動に対して３つ（スケールは回復できないので１つ減）の５つである。
【００４５】
一致する画素の２Ｄ場所は１つのエピポーラ制約を提供する。スケールが追加として与えられる場合、上述の式４の正弦法則がやはり有効でなければならない。これからは、２つの可能な最小ソルバがあり、（ａ）スケールをもつ１つの点およびスケールをもたない３つの点（１×２＋３×１＝５）、ならびに（ｂ）スケールをもつ２つの点およびスケールをもたない１つの点（２×２＋１×１＝５）である。
【００４６】
最初に、３＋１点アルゴリズムを調べる。ステップＳ１０７において、４つの（ｎ個の）一致点が２つの画像ビューにおいて選択され、これらのうちの１つ（ｍ個）はスケールおよび場所
【数２１】
2019021291.tif 000023
をもち、３つは場所
【数２２】
2019021291.tif 000024
のみをもつ。これらから、回転Ｒおよび平行移動ｔが導出される。上述の式（２）および式（４）を使用して、以下の連立方程式を表すことが可能である。
【数２３】
2019021291.tif 000025
【数２４】
2019021291.tif 000026
【００４７】
上述の式（７）は、ｔに無関係であり、したがって、回転に対する３つの未知数をもつ３つの方程式の系を形成することが分かる。次いで、これは、１＋３点アルゴリズムと呼ばれる第１の最小ソルバのコアとして使用される。次いで、ｔの長さは回復できないので、平行移動ｔは上述の式（２）を介して見いだされる。
【００４８】
回転は、四元数ｑ＝ｑa＋ｑbｉ＋ｑcｊ＋ｑdｋとして表され、ここで、
【数２５】
2019021291.tif 000027
である。次いで、式（７）は、式（８）を考慮して展開することができ、
【数２６】
2019021291.tif 000028
である。
【００４９】
ｑは単位長であるので、
【数２７】
2019021291.tif 000029
を置き換え、（８ａ）の右項を並べ換えて、
【数２８】
2019021291.tif 000030
となることが可能である。最後に、未知数の数は、
【数２９】
2019021291.tif 000031
でｑをスケーリングすることによって減らされ、二次形式
【数３０】
2019021291.tif 000032
を形成することができる。１８０度の回転に関連するｑa＝０の縮退の場合がある。しかしながら、これは、実際のデータではほとんど見られない。さらに、ｑa＞０が強制されるので、回転行列Ｒごとに１つの解のみが存在する。ｑおよび−ｑは同じ回転を包含していることに留意されたい。
【００５０】
したがって、上述の式（７）は、今では、簡単な二次形式の３つの式、すなわち、
【数３１】
2019021291.tif 000033
で表され得、ここで、未知数のベクトルは
【数３２】
2019021291.tif 000034
に対応し、Ａi、ｂi、およびｃiは既知の観察値である。回転を同次四元数として用いて、最小ソルバはグレブナー基底アルゴリズムを介して導出され得る。上述の方法は、８つの解をもつ８次１変数多項式に分解する。根は、スツルムシーケンスを介してまたはより確実には固有値分解を介して効率的に見いだされ得る。最後に、式（３）は最小解として十分であるが、単純な応用は、トレースおよび単項式の６０％の増加をもたらす。その結果、変更された式のセットは、ステップＳ１１１においてＲおよびｔの推定値を見いだすのに必要な計算ステップが少ないので、数値的に安定したソルバを生成する。
【００５１】
上述の３＋１ソルバの代替として、２＋１ソルバを使用することも可能である。ここで、ステップＳ１０７において、ｎ＝３およびｍ＝２である。したがって、３つの点対応、すなわち、
【数３３】
2019021291.tif 000035
、
【数３４】
2019021291.tif 000036
、および
【数３５】
2019021291.tif 000037
があり、そのうちの２つは既知のスケールを有する。上述の式（２）、（３）、および（４）を使用して、以下の連立方程式が導出され、
【数３６】
2019021291.tif 000038
【数３７】
2019021291.tif 000039
【数３８】
2019021291.tif 000040
ここで、式（１１）は、式（４）を式（２）の比例する平行移動の同値性と組み合わせている。上述の１＋３点アルゴリズムと同様に、回転Ｒのみを解くべき系は（１１）および（１２）によって与えられ、それは３つの独立した式から構成される。式（１１）は、最初に、まずそれを
【数３９】
2019021291.tif 000041
に並べ換え、次いで、式（９）に類似して１組の３つの同値な二次式を構成することによって簡単化される。グレブナー基底を用いて解く場合、４つの解をもつ４次１変数多項式を得ることが可能である。再び、根は、Ｒを与えるためにスツルムシーケンスまたは固有値分解を介して見いだすことができる。次いで、平行移動ｔが、ステップＳ１１１においてＲから導出され得る。
【００５２】
上述の方法は、回転Ｒと平行移動ｔとを直接計算する。それゆえに、キラリティが自動的に強制される。しかしながら、１＋３および２＋１点アルゴリズムは、縮退を有する。点が同じエピポーラ平面にある場合、式は、独立ではなく、縮退をもたらす。さらに、回転が同次四元数として表されるとき、回転角１８０度を伴うカメラの動きはサポートされない。しかしながら、両方の事例は、実際の画像ではほとんど経験しない。
【００５３】
図３のフロー図を参照して説明された方法は、カメラの姿勢、具体的にはＲおよびｔの推定をもたらす。しかしながら、特徴の検出およびマッチングには誤差が存在することがあるので、さらなる実施形態において、図３を参照して説明されたＲおよびｔの推定値が改良される方法が提供される。これらの方法のうちの１つは、ＲＡＮＳＡＣ推定フレームワークを使用するものである。
【００５４】
ＲＡＮＳＡＣは、最小ソルバを利用するロバスト推定フレームワークである。点対応からの相対姿勢推定の場合には、例えば、カメラ姿勢を決定する場合、最小セットが、前提を見いだすためにランダムに選択され、次いで、前提が残りのデータサンプルで試験される。この例では、まず、２つのクラスセットアップが考慮され、次いで、不安定なスケールを使用して、最小ソルバをＲＡＮＳＡＣフレームワークに統合する。
【００５５】
上述の最小ソルバは、２つのクラスのサンプル点、具体的には、スケールをもつ点対応／一致の場所と、スケールをもたない点対応／一致の場所とを有する。それゆえに、ＲＡＮＳＡＣの古典的な停止基準は、２つのインライアタイプを反映するように変更され、それぞれ、１＋３点アルゴリズムおよび２＋１点アルゴリズムに対して
【数４０】
2019021291.tif 000042
である。Ｋは、ｒlおよびｒsが、それぞれ、場所と、スケールをもつ場所とに対してインライアを選択する可能性を表すという仮定の下で、確率ｐまでインライアセットが選択されたことを保証するために必要とされる反復の数である。レートはインライア試験に基づく。一般に、サンプソン距離は、試験する場所のエピポーラ制約の誤差を推定するために利用され、
【数４１】
2019021291.tif 000043
であり、ここで、Ｋ1およびＫ2は、それぞれ第１のビューおよび第２のビューの較正行列であり、（ａ）2ｉは、ベクトルａのｉ番目の要素の２乗を計算し、δlは場所インライア閾値である。今では、インライア試験がスケールに対して設定され得る。式４を使用し、ならびにｘおよびｘ'がエピポーラ平面上にあるという仮定の下で、外積の法線ベクトルが共有されるので、
【数４２】
2019021291.tif 000044
を書くことが可能である。式１６の最終項は、画像ドメインからのスケールが、以下では
【数４３】
2019021291.tif 000045
によって表されることになる、Ｒおよびｔによって示唆される予想スケールと異なることがあるという観察から生じる。特に、スケール誤差εsは、ｓを
【数４４】
2019021291.tif 000046
にマッチングさせるのに必要とされる変化として定義され、その結果、差は、
【数４５】
2019021291.tif 000047
によって与えられる。最後に、式１５の場所制約ならびに式１６のスケール試験を小さい誤差δlおよびδsまで満たす対応をスケールインライアとして定義することが可能である。閾値δsの大きさは容易に設定され得、スケール空間ピラミッドのステップサイズに関連するパラメータの考慮事項は容易に設定され得ることに留意されたい。
【００５６】
高解像度画像では、特徴検出器は、場所に関してかなり信頼性が高い。
残念ながら、スケールの推定は、安定性が低く、スケール空間ピラミッドで使用されるステップサイズに依存する。例えば、ＳＩＦＴにおいて、スケールは、最初に、ベーススケールσ0＝１．６およびステップサイズσs＝１を用いて
【数４６】
2019021291.tif 000048
で離散化され、次いで、連続値に補間される。その結果、ソルバに影響を与えることがある誤差が間違って導入される。
【００５７】
スケールにおける誤差の修正を目的とする効率的な二分探索が提案されている。特に、相対姿勢問題は、元の観察値のまわりで得られた多数のスケールを用いて反復して解決される。ｓi、ｓi（１＋ε）、およびｓi（１−ε）に対する解から始めて、ｓiに対する最善選択をもつスケールが更新され、変動を半分
【数４７】
2019021291.tif 000049
にして、このプロセスを続ける。二分が機能するには、誤差の減少とともに性能尺度の単調な減少が必要とされることが強調されるべきである。場所インライア比が性能尺度として利用される。
【００５８】
最後に、二分探索が利用されるとき、相対姿勢問題ではより多くの解を計算することが必要とされることに留意されたい。様々なスケールのスコアリングは計算上最も大きいコストであるが、対照的にソルバは高速である。したがって、プリエンプティブ法およびランタイム性能の向上のための早期救済が実行される。図５は、最小ソルバとして図３からの解を使用するＲＡＮＳＡＣ法のフロー図を示す。
【００５９】
さらに、擬似コードが、１＋３点アルゴリズムについて以下に列記される。２＋１アルゴリズムと異なっている箇所では、その擬似コードは｛｝に入れられている。
【００６０】
入力：Ｎ点対応
【数４８】
2019021291.tif 000050
較正行列Ｋ1およびＫ2、インライアセット選択の所望の確率ｐ。
【００６１】
出力：ビュー間の推定された回転Ｒおよび平行移動ｔ。
【００６２】
１：最良のレート
【数４９】
2019021291.tif 000051
、姿勢
【数５０】
2019021291.tif 000052
、
【数５１】
2019021291.tif 000053
、およびカウントｋ←０を初期化する
２：ｒｅｐｅａｔ
３：  １＋３：
【数５２】
2019021291.tif 000054
、
【数５３】
2019021291.tif 000055
、
【数５４】
2019021291.tif 000056
、および
【数５５】
2019021291.tif 000057
を
【数５６】
2019021291.tif 000058
からランダムに選択する
｛２＋１点アルゴリズムの場合：
【数５７】
2019021291.tif 000059
、
【数５８】
2019021291.tif 000060
、および
【数５９】
2019021291.tif 000061
を
【数６０】
2019021291.tif 000062
からランダムに選択する｝
４：  スケール変動を初期化する
【数６１】
2019021291.tif 000063
５：  ｗｈｉｌｅ  ε  ＞  １０-3  ｄｏ
６：    １＋３：スケールｓa、ｓa±εをもつ選択されたタプルに対してＲj、ｔjを見つけ出す
｛２＋１アルゴリズムの場合：スケールｓa、ｓa±ε、ｓb、ｓb±εをもつ選択されたタプルに対してＲj、ｔjを見つけ出す｝
７：    ｆｏｒ  ａｌｌ  Ｒj，  ｔj  ｄｏ
８：      １＋３：インライアレートｒsおよびｒlを計算する、および
【数６２】
2019021291.tif 000064
を設定する。
｛２＋１アルゴリズムの場合：インライアレートｒsおよびｒlを計算する、および
【数６３】
2019021291.tif 000065
を設定する｝
９：      ｉｆ
【数６４】
2019021291.tif 000066
ｔｈｅｎ
１０：        最良の結果
【数６５】
2019021291.tif 000067
、
【数６６】
2019021291.tif 000068
を更新する、および
【数６７】
2019021291.tif 000069
を見つけ出す
１１：      ｅｎｄ  ｉｆ
１２：    ｅｎｄ  ｆｏｒ
１３：    ｉｆ
【数６８】
2019021291.tif 000070
未満の最大投影改善  ｔｈｅｎ
１４：      ブレーク
１５：    ｅｎｄ  ｉｆ
１６：    １＋３：最良のスケールを選択する、およびｓaを更新する、および
【数６９】
2019021291.tif 000071
｛２＋１アルゴリズムの場合：最良のスケールを選択する、およびｓa、ｓbを更新する、および
【数７０】
2019021291.tif 000072
｝
１７：  ｅｎｄ  ｗｈｉｌｅ
１８：  ｋ＝ｋ＋１
１９：ｕｎｔｉｌ  ｋ≧Ｋ
【００６３】
ステップＳ１５１において、一致する特徴が２つの画像から抽出される。問題を簡単にするために、ここでは１＋３点アルゴリズムが使用されると仮定する。２＋１点アルゴリズムに適応させる方法への変形は後で説明する。
【００６４】
次に、ステップＳ１５３において、１＋３点アルゴリズムでは、４つの一致点のグループが、上述の擬似コードのライン３に示したように、ランダムに選択される。それに続いて、Ｒおよび次いでｔが、ランダムに選択されたタプルに対してステップＳ１５５において計算される。Ｒおよびｔは、図３に関連して説明されたように計算される。ランダムに選ばれたタプルのセットに対して多数の解が存在することになる（最大４つまたは８つの解）。インデクスｊは、解のインデキシングを示すために使用される。
【００６５】
図５のフロー図は、上述の擬似コードのそれから簡単化した解を調べ、図５のフロー図では、スケールに対する修正はない。スケールの修正は、図６のフロー図を参照して説明する。
【００６６】
ステップＳ１６３において、ループが開始され、アルゴリズムは、インライアのレートがすべてのｊに対して計算されたかどうかを調べる。
【００６７】
計算されていない場合、インライアのレートが、ステップＳ１５５において計算されたＲjおよびｔjに対して計算される。場所に関するインライアのレートｒl、およびスケールに関するインライアのレートｒsが、上述のように式１５および式１６を使用して計算される。
【００６８】
インライアの総合レートｒは、１＋３アルゴリズムでは
【数７１】
2019021291.tif 000073
から計算される。これが計算された最低レートである場合、これは最良の結果
【数７２】
2019021291.tif 000074
として設定される。さらに、
【数７３】
2019021291.tif 000075
、
【数７４】
2019021291.tif 000076
、および
【数７５】
2019021291.tif 000077
が、ステップＳ１６１において設定される。次に、Ｊがインクリメントされ、ループはステップＳ１６３に戻り、次いで、インライアのレートが、ステップＳ１５７において同じグループの一組に関する次の解に対して計算される。
【００６９】
ステップＳ１５９において、インライアの最低レートが現在のｊに対して計算されていない場合、方法は、ステップＳ１６３に戻り、カウンタｊをインクリメントするが、結果を更新しない。
【００７０】
インライアレートが、すべてのｊ、すなわち、現在選択されているタプルに対するすべての解に対して計算されるまで、このループは続く。
【００７１】
インライアレートがすべてのｊに対して計算された後、方法はステップＳ１６５に進み、停止基準が達せられたかどうかが決定される。停止基準は、式１４を参照して説明されている。停止基準が達せられていない場合、４つの一致点の新しいグループがステップＳ１５３において選択されるべきであることを示すために、インデクスケースが１だけインクリメントされる。次いで、方法は、上述のように続く。
【００７２】
停止基準が達せられた後、結果が出力される。結果は、カメラの姿勢を与える。これは、カメラ位置の簡単な出力とすることができる。次いで、出力は、さらに、移動物体の位置および／または姿勢が決定される必要があるＳＬＡＭシステムまたは他のシステムの一部として使用され得る。
【００７３】
上述で説明したように、特徴検出器は場所に関して信頼できる。しかしながら、スケールの推定は、安定性が低く、スケール空間ピラミッドで使用されるステップサイズに依存する。図６のフロー図はこれを考慮に入れている。
【００７４】
不必要な繰り返しを避けるために、同様の参照番号は、同様の特徴を示すために使用される。図６において、図５からのステップＳ１５５はステップＳ１５４で置き換えられている。ステップＳ１５５において、Ｒjおよびｔjが、ステップＳ１５３において選択されたタプルに対して計算された。これは、ステップＳ１５４においても生じる。しかしながら、これらの値は、測定されたスケールに対して計算されるが、ｓa、ｓa±εとして表される誤差をもつスケールに対しても計算される。これは、記述子中の測定されたスケールが、通常、いくつかのステップ状の値から選択された値であるということなので、上述の理由により行われる。しかしながら、実際には、スケールは、これらのステップの２つの間に入ることがある。それゆえに、このプロセスが行われ、誤差がスケールに適用され、モデルはこの誤差を組み込んだスケールで実行される。この誤差を組み込んだスケールがより良好な結果をもたらした場合、誤差をもつスケールが次の反復で使用される。反復ごとに、あり得る誤差が減少して、この方法は、最も適切なスケールを目指して進むことができる。
【００７５】
図７は、スケール改良ステップＳ１５４をより詳細に示す。ステップＳ１１５１において、Ｒおよび次いでｔが、ランダムに選択されたタプルに対して計算される。次いで、ステップＳ１１５３において、ループが終了したかどうか、およびインライアのレートがすべてのｊに対して計算されたかどうかが調べられる。そうでない場合、インライアのレートが、ステップＳ１１５５においてｊに対して計算される。次いで、ステップＳ１１５７において、これがインライアの最低レートであるかどうかが調べられる。そうでない場合、インデクスｊはインクリメントし、ループはステップＳ１１５３に戻る。インライアの新しい最低レートが計算された場合、結果はステップＳ１１５９において更新され、ｊはループ中にインクリメントされ、ステップＳ１１５３に戻る。
【００７６】
ステップＳ１１５３において、ループが終了し、すべてのｊに対するインライアが計算された場合、方法はステップＳ１１６１に進む。ここで、誤差εがスケールから減じられる。次いで、上述のものと同様のプロセスが実行される。インデクスｊはリセットされる。まず、ステップＳ１１６３において、ループが終了されるべきかどうかを調べる。次に、ステップＳ１１６５において、インライアのレートが計算される。上述と同じように、ステップＳ１１６７において、インライアの最新のレートが、インライアの以前にセーブしたレートよりも低い場合、結果がステップＳ１１６９において更新され、インデクスがインクリメントされて、Ｓ１１６３に折り返す。一番最近に計算されたインライアレートが最低でない場合、結果は更新されず、システムは再びステップＳ１１６３に折り返す。
【００７７】
ステップ１１６３において、すべての解が検査されたと決定された場合、方法はステップＳ１１７１に進み、インデクスがリセットされ、誤差εがスケールに加えられる。次いで、上述のものと同様のプロセスが実行される。まず、ステップＳ１１７３において、ループが終了されるべきかどうかを調べる。次に、ステップＳ１１７５において、インライアのレートが計算される。上述と同じように、ステップＳ１１７７において、インライアの最新のレートが、インライアの以前にセーブしたレートよりも低い場合、結果はステップＳ１１７９において更新され、インデクスがインクリメントされて、Ｓ１１７３に折り返す。一番最近に計算されたインライアレートが最低でない場合、結果は更新されず、システムは再びステップＳ１１７３に折り返す。
【００７８】
ステップＳ１１７３において、すべての解が試験されたと決定された場合、方法はステップＳ１１８１に進む。ここで、誤差が閾値未満であるかどうかが調べられる。そうでない場合、最良のスケール測定値が、ステップＳ１１８３においてスケール管理ｓaとして設定され、誤差が半分にされる。次いで、プロセスはステップＳ１１６１に折り返し、ステップＳ１１６１からステップＳ１１８１までが、半分にされた誤差を用いて繰り返される。ステップは、誤差が閾値を下回るまで誤差が減らされて連続的に繰り返される。
【００７９】
一例では、以下の擬似コードが使用され得る。
【００８０】
１）ｓ＿ａに対して解｛Ｒj，ｔj｝を計算する（ｊ＝０に設定する）
２）現在のｊに対してＲjおよびｔjが存在するか？
ａ．Ｙｅｓ：続ける
ｂ．Ｎｏ：５に行く
３）インライア比を計算する
４）最低の現在のインライアレートか？
ａ．Ｎｏ：ｊ＋１、および２に行く
ｂ．Ｙｅｓ：今のところｓaを最良のスケールとしてセーブする（レート、解などを記憶する）、および４．ａを行う
５）ｓa＋ｅに対してＲjおよびｔjを計算する（ｊ＝０に設定する）
６）現在のｊに対してＲjおよびｔjが存在するか？
ａ．Ｙｅｓ：続ける
ｂ．Ｎｏ：９に行く
７）インライア比を計算する
８）最低の現在のインライアレートか？
ａ．Ｎｏ：ｊ＋１、および６に行く
ｂ．Ｙｅｓ：今のところｓ＿ａ＋ｅを最良のスケールとしてセーブする（インライアレート、解などを記憶する）、および８．ａを行う
９）ｓa−ｅに対してＲjおよびｔjを計算する（ｊ＝０に設定する）
１０）現在のｊに対してＲjおよびｔjが存在するか？
ａ．Ｙｅｓ：続ける
ｂ．Ｎｏ：１４に行く
１１）インライア比を計算する
１２）最低の現在のインライアレートか？
ａ．Ｎｏ：ｊ＋１、および１０に行く
ｂ．Ｙｅｓ：今のところｓ＿ａ−ｅを最良のスケールとしてセーブする（レート、解などを記憶する）、および１２．ａを行う
１３）ｅ＜閾値か？
ａ．Ｎｏ：最良のスケールとなるようにｓ＿ａを更新し、半分のｅ、および５からループする
ｂ．Ｙｅｓ：続ける
１４）最低の総合インライアレートか？
ａ．Ｙｅｓ：記憶されたレートおよび解から結果および停止基準を更新する
ｂ．Ｎｏ：続ける
１５）Ｓ１６５
【００８１】
上述は、１＋３点アルゴリズムに関連して説明された。しかしながら、上述は、一致した特徴の異なる選択を使用して、２＋１点アルゴリズムに容易に適応され得、ここで、「２」はスケールをもち、「１」はスケールをもたないように選択される。さらに、Ｒおよびｔの計算は、上述のように、式６から式９とは対照的に式１０から式１３に関連する。さらに、停止基準は、式１４に示された第２の変形の通りに変更される。
【００８２】
２＋１点アルゴリズムでは、２つのスケール比があり、これらの両方は誤差εによって変更され、両方は、上述の擬似コードの第１の例のライン３およびライン１６に関連して説明されたように最適化されることに留意されたい。
【００８３】
上述の方法から得られる結果を実証するために、合成データモデルが使用される。既知のノイズを用いてこの方法を評価するために、２つのビューセットアップが、図８に示すように使用される。図８において、２つのカメラの各カメラ２０１は、焦点距離１と、ベースライン０．１およびせいぜい４５°の回転によるランダムな動きとにより選ばれる。点は、１と１．５との間の深度値でサンプリングされる。
【００８４】
追加として、ノイズが、以下では、場所観測および深度比観測に導入される。評価は、３つの誤差測度に基づき、
【数７６】
2019021291.tif 000078
【数７７】
2019021291.tif 000079
【数７８】
2019021291.tif 000080
であり、ここで、ｉは、解のセットをインデクス付けする。式（１７）における真の基本行列
【数７９】
2019021291.tif 000081
と推定された基本行列Ｅiとの間のフロベニウスノルムが、全体的なシステム性能を試験するために使用される。式（１８）および式（１９）における真の平行移動ベクトル
【数８０】
2019021291.tif 000082
と推定ｔiとの間の角度誤差、または真の回転行列
【数８１】
2019021291.tif 000083
および推定Ｒiが、より詳細な分析のために利用される。
【００８５】
図９（ａ）、図９（ｂ）、および図９（ｃ）は、場所測定にノイズがある場合のそれぞれ基本行列、平行移動、および回転に対して得られた誤差を示す。正規分布ノイズが、ＣＩＦ画像（解像度３５２ｐｘ×２４０ｐｘ）によって観察される画素の大きさの標準偏差として表される、画像平面の点に誘導される。１＋３点アルゴリズムおよび２＋１点アルゴリズム（以下では１＋３ｐｔおよび２＋１ｐｔで表される）が、場所のみを考慮する５点アルゴリズム（５ｐｔで表される）と比較される。Ｅ誤差は、５ｐｔに対して±Ｅiをサポートするように変更される。全部で、３点、４点、または５点の１００００ランダム事例がモデルを使用して発生される。
【００８６】
１＋３ｐｔは全部で４つの場所のみを必要とするが、ノイズに対して最も脆弱であり、しかも５ｐｔに匹敵する。２＋１ｐｔは、導出された基本行列が２つの正確なスケール測定によってサポートされるので、両方の他の手法よりも著しく良好に動作する。
【００８７】
ノイズの多いスケールで１＋３ｐｔおよび２＋１ｐｔを精密に調べることによって、図１０（ａ）、図１０（ｂ）、および図１０（ｃ）は、それぞれ、基本行列、平行移動、および回転に対する異なるノイズレベル（ＳＩＦＴのデフォルトのステップサイズの１００分の１の分散を伴う１のまわりでのガンマ分布としてモデル化された）の１００００事例の平均性能を示す。
【００８８】
再度、２＋１ｐｔは１＋３ｐｔ設定より性能が優れており、回転がとりわけ改善されている。式（１１）において、２つのスケールは、回転が平行移動をサポートし、それにより、誤った結果の機会を減少させることを保証しなければならないことに留意されたい。実際、スケールの誤差が大きい場合、２＋１ｐｔは、多くの場合、ノイズに対していくらかの頑健性を示す実際に価値のある解をほとんど生成しないかまたはさらに全く生成しないことが見いだされた。
【００８９】
図１１は、Ｅ誤差へのスケール効果を示す。図１１（ａ）は、２＋１アルゴリズムについて、両方のスケール比に対するＥ誤差へのスケール効果を別々に示し、図１１（ｂ）は、１００００インライアに対するエピポーラ制約への平均誤差を示す。図１１（ｃ）および図１１（ｄ）は、それぞれ、図１１（ａ）および図１１（ｂ）のデータの中央スライスを示す。図１１（ｅ）および図１１（ｆ）は、１＋３点アルゴリズムに対する対応するデータを示す。両方の方法は、事実上、ノイズの増加とともに単調に増加する。上述のデータは、１００００試行から得られた。
【００９０】
図１１は、誤差の増加に伴うスケールのノイズを系統的に詳細にモデル化している。１＋３ｐｔと２＋１ｐｔの両方は、事実上、ノイズレベルが大きくなるとともに単調に増加していることに留意されたい。この挙動は、上述のように二分探索アルゴリズムにおいて利用される。真の基本行列は実際のデータでは不明であるが、Ｅ誤差の近似は、インライア比、または代替としてエピポーラ制約における平均誤差を推定することによって与えられる。
【００９１】
次に、上述の方法は、図１２に示すように様々な難易度の６つの実際の画像対で試験される。まず、ＳＩＦＴ特徴一致（SIFT feature match）が抽出される。次に、ＲＡＮＳＡＣ（＝０．９９、δ＝１ｐｘ、δ＝０．１を用いて）が実行され、評価は上述のように場所インライア基準に基づく。比較は、提案する方法と５点アルゴリズムとの間で行われる。ＲＡＮＳＡＣはランダム選択プロセスに基づくので、すべてのアルゴリズムが１０００回実行され、平均が報告される。
【００９２】
５ｐｔ、１＋３ｐｔ、および２＋１ｐｔのインライア比が、図１３において比較されている。スケール修正なしの性能は、１＋３ｐｔおよび２＋１ｐｔでは著しく低下している。図：ｒａｎｓａｃは、追加として、１＋３*および２＋１*で表された、二分改良（ｓｅｃ：二分）による１＋３ｐｔおよび２＋１ｐｔの結果を示す。
【００９３】
全体的に、これらは５ｐｔと同様に動作し、２＋１*は、ｐ２、ｐ３、ｐ４、およびｐ５において最も高いインライア比に達し、１＋３*は、ｐ１およびｐ６において最良の性能を有する。図：画像は、２＋１*の視覚的な例を示す。画像対ｐ１は、限定的なスケール変化と、比較的簡単なカメラ構成とを有する。画像ｐ２、ｐ３、ｐ４、およびｐ５は、低減した場所依存性を得るので、スケールから利益を得る。スケール利用のための挑戦的な設定はｐ６であり、その理由は、投影がパッチの楕円の面積を一貫して減少させ、それにより、不正確なスケール比がもたらされるからである。これは、さらに、２＋１*によって推定されるような必要とされるスケール
【数８２】
2019021291.tif 000084
を用いた
【数８３】
2019021291.tif 000085
によって与えられ、ｐ６の結果から離れて１のまわりの正規分布であるスケールのダイバージェンスにおいて明らかである。
【００９４】
最後に、全体的に、１＋３*および２＋１*は、ＲＡＮＳＡＣによって必要とされる反復で著しく改善するが、しかしながら、単純に、二分探索ではより多くの解が調査されることに留意されたい。それゆえに、信頼性の低いスケールでは、早期救済およびプリエンプティブ評価が必須である。
【００９５】
２つの較正済み画像の間の相対姿勢を推定する効率的な最小ソルバが提示される。提案する方法は、スケール空間ピラミッドを用いたスケール不変特徴検出器（ＳＩＦＴ）によって本質的に与えられる特徴一致の既知のスケール比を利用する。スケールを使用しているので、必要とされる特徴の数。
【００９６】
既知のスケール比を用いた相対姿勢の２つの解が上述で提示されている。特に、ＳＩＦＴなどの記述子はスケール空間ピラミッドを利用するので、画像平面上のパッチのスケールが本質的に与えられることに留意されたい。上述の方法は、スケールと深度との間の接続を使用し、姿勢と深度比とを関連づける幾何学的制約を導出する。全部で、場所およびスケール対応に対する２つの可能な最小セット、すなわち、１つの既知のスケールとともに４つの特徴一致を利用する１＋３点アルゴリズムと、２つの既知のスケールを用いて３つの一致から相対姿勢を推定する２＋１点アルゴリズムとがある。
【００９７】
次いで、最小ソルバが、ランダムサンプリングコンセンサス（ＲＡＮＳＡＣ）を使用する最終推定フレームワークにおいて使用される。上述の方法は、
１．スケール（または深度）比を相対姿勢に関連づける幾何学的観察を導出する。
【００９８】
２．スケール空間特徴検出を利用し、姿勢に対する２つの新しい最小ソルバを導出する。
【００９９】
３．信頼性の低いスケールでは１＋３および２＋１点アルゴリズムをＲＡＮＳＡＣに埋め込む。
【０１００】
上述の方法において、スケールと深度との間の相互関係が使用される。上述の方法において、２つのソルバは、各々、２つの可能な最小セットのうちの１つに関連して導出される。１＋３点アルゴリズムは、１つの既知のスケールを用いて４つの特徴一致から相対姿勢を推定し、一方、２＋１点アルゴリズムは、２つの既知のスケールを用いて３つの特徴一致から相対姿勢を計算する。提案する方法は、２つのインライアクラスによりＲＡＮＳＡＣに埋め込まれ、信頼性の低いスケールでは効率的なＲＡＮＳＡＣ変形を提示する。
【０１０１】
上述の方法は、スケール空間ピラミッドを用いてスケール不変特徴検出器（例えば、ＳＩＦＴ、ＯＲＢ特徴）によって容易に与えられる特徴一致の既知のスケール比を利用する。
【０１０２】
上述の方法はスケールを使用するので、必要とされる特徴一致の数が減少し、その結果、必要なインライアが少ない。１＋３点アルゴリズムは、１つの既知のスケールを用いて４つの特徴一致から相対姿勢を推定し、一方、２＋１点アルゴリズムは、２つの既知のスケールを用いて３つの特徴一致から相対姿勢を計算する。
【０１０３】
最後に、この方法は、２つのインライアクラスによるＲＡＮＳＡＣに適用可能である。信頼性の低いスケールを取り扱うために、効率的なＲＡＮＳＡＣ変形が提示される。
【０１０４】
上述の方法は、単に、画像と画像の間の対応を利用し、１つまたは２つの対応は追加のスケール比情報を運ぶ。さらに、上述の方法は、相対姿勢について正確に解明する。
【０１０５】
上述の方法において、１＋３点アルゴリズムは４つのインライアのみを必要とし、８つまでの解を生成し、一方、２＋１点アルゴリズムは４つまでの解のみを生成する。それゆえに、信頼できる特徴対応のセットを選ぶことは比較的容易であり、正しい解をフィルタ処理するために計算はほとんど必要とされない。
【０１０６】
上述の方法は、相対姿勢の推定を可能にし、追加のハードウェアが必要とされず、ビュー間のいかなるカメラの動きも可能である。必要とされる特徴対応の数を減少させるために、容易に入手できるスケールが利用される。
【０１０７】
特定の実施形態が説明されたが、これらの実施形態は単なる例として提示されており、本発明の範囲を限定するようには意図されていない。確かに、本明細書で説明した新規の方法および装置は、様々な他の形態で具現され得、さらに、本明細書で説明された方法および装置の形態における様々な省略、置換、および変更が、本発明の趣旨から逸脱することなくなされ得る。添付の特許請求の範囲およびその均等物は、本発明の範囲および趣旨内にあるそのような形態の変形を包含するように意図される。
【図１（ａ）】
2019021291.tif 000086
【図１（ｂ）】
2019021291.tif 000087
【図２】
2019021291.tif 000088
【図３】
2019021291.tif 000089
【図４】
2019021291.tif 000090
【図５】
2019021291.tif 000091
【図６】
2019021291.tif 000092
【図７（ａ）】
2019021291.tif 000093
【図７（ｂ）】
2019021291.tif 000094
【図８】
2019021291.tif 000095
【図９（ａ）】
2019021291.tif 000096
【図９（ｂ）】
2019021291.tif 000097
【図９（ｃ）】
2019021291.tif 000098
【図１０（ａ）】
2019021291.tif 000099
【図１０（ｂ）】
2019021291.tif 000100
【図１０（ｃ）】
2019021291.tif 000101
【図１１（ａ）】
2019021291.tif 000102
【図１１（ｂ）】
2019021291.tif 000103
【図１１（ｃ）】
2019021291.tif 000104
【図１１（ｄ）】
2019021291.tif 000105
【図１１（ｅ）】
2019021291.tif 000106
【図１１（ｆ）】
2019021291.tif 000107
【図１２】
2019021291.tif 000108
【図１３】
2019021291.tif 000109
【外国語明細書】
2019021291000001.pdf