運動からの構造

カメラが移動するフレームのシーケンスを見ると、脳はコンテンツの幾何学的構造を簡単に認識します。 ただし、コンピュータービジョンでは、これは些細な問題ではありません。 この記事では、この問題の可能な解決策を説明しようとします。

この記事を読む前に、 「立体視の基礎」という記事を注意深く読んでも問題はありません。

そのため、一連の2次元画像を3次元構造に変換するという課題に直面しています。 タスクは単純ではなく、単純化する必要があります。
まず、フレームが2つしかないとします。 それらをAおよびBとして示します。
次に、フレームAとBで互いに対応する有限のポイントセットを使用します。画像内のポイントは、 。 次に、フレームAとBのポイントは そして 。 点の各ペアは、3次元空間の点に対応します 。

次に、検索方法を決定する必要があります そして 。 これを行うには、最初のフレームで、コントラストが最も高いポイント（「特別な」ポイント（機能））を選択します。 これには 、 高速、またはその他のサーフィンを使用できます。 これらのポイントは 。 次に、同じsurfアルゴリズムまたは光 ストリームを使用して、2番目のフレームでこれらのポイントへの対応を見つける必要があります 。 そして、これらがポイントです 。

そして今、私たちはこの記事の中心的な質問に来ます：どのようにポイントから そして （ポイント対応、ポイント対応）空間内のポイントの座標とカメラの位置を取得しますか？ 最初に、画像に当たるポイントを把握する必要があります。 カメラの数学モデルを構築する必要があります。

投影カメラモデル

おそらく既に「ステレオビジョンの基礎」という記事を読んでいるため、この式はおなじみのはずです。
。
または、より完全に説明する場合：
。
ここで、Xは空間の3次元の点です。
xは、 均一な座標での画像内のポイントの座標です。 、つまり、通常の画像座標への変換は次のようになります。 。
空間内のポイントを画像座標に変換するプロセスは、式の2つのマトリックスによって実装される2つの段階に分割できます。

1. [R | t]-Rとtは、空間内のカメラの位置を表します。 この段階で、ポイントの座標はカメラのローカル座標に変換されます。 Rは3x3回転行列、tは3次元変位ベクトルです。これらは一緒に[R | t]遷移行列（3x4）を構成し、フレーム内のカメラの位置を決定します。 [R | t]-これは、3次元グラフィックスのビュー行列と同じです（4x4ではないサイズを考慮しない場合）。
   カメラの回転行列です -空間内のカメラの位置の3次元座標。 Rとtはカメラの外部パラメーターと呼ばれます。
2. Kはカメラ行列です。 ポイントのローカル座標は、均一な画像座標に変換されます。 f _x 、f _yはピクセル単位の焦点距離、c _x 、c _yはカメラの光学中心（通常は画像の中心の座標）です。 これらのパラメーターは、カメラの内部パラメーターと呼ばれます。

このモデルの重要な特性は、空間内の1つの直線上にあるポイントが、画像内の1つの直線上にあることです。
実際、説明されているモデルは非常に不正確な場合があります。 実際のカメラでは、直線が湾曲するため、レンズの歪みが発生します。 この歪みを歪みと呼びます。 これらの歪みを修正するさまざまなモデルがあります。 実装の一部を以下に示します。 このモデルのパラメーターは、カメラの内部パラメーターの概念にも含まれています。
歪みを考えると、式は複雑です。
ここで、D（X）は、画像点の均一な座標を取得し、画像内の通常の座標を返す関数です。 また、後で逆関数-InvD（ix）が必要になります。
カメラの内部パラメーターは事前に知っておく必要があります。 これらのパラメーターの明確化は別の問題であり、既に存在すると仮定します。

歪みの歪みは、可視ポイントの深さではなく、画像内の座標のみに依存します。 これは、カメラの外部パラメーターと空間内のポイントの座標を知らなくても、イメージを「修正」することができることを意味します（直線を配置する必要があります）。 次に、D関数なしでカメラモデルを使用できます。

左右に歪みがある画像は、レンズの歪みから「補正」された画像です。 ラインがまっすぐになったことがわかります。

ポイントの正規化

内部パラメーターを知っていること、画像内のポイントの座標もわかっていること、つまり[R | t]およびX _i （カメラの位置と空間内のポイント）を見つけることを意味することに同意しました。
私たちの式はすでに少し複雑なので、単純化する必要があります。 始めに、これをやってみましょう：

表現は公正なままです。 続ける：

示す （そして、歪みがなければ、 ） すべてのパラメータが既知であるため、nx _iは事前に計算できます。 行列Kがどのように見えるかを思い出すと、nx _z = 1であることがわかります。これは、さらなる計算に役立ちます。 その結果、式はより単純になります。


nx _iは、画像の正規化されたポイントです。

基本および必須行列

したがって、同じカメラから撮影した2つの画像があるとします。 カメラの位置と空間内のポイントの座標はわかりません。 最初のフレームに関する計算を導入することに同意します。 したがって、R ^A = I（Iは単位行列）、t ^A =（0、0、0）であることがわかります。 フレームBのカメラの位置は、Rとtで簡単に表されます（つまり、R ^B = R、t ^B = t）。 [R | t]は2番目のフレームの座標のマトリックスであり、フレームAからフレームBへのカメラの位置の変位のマトリックスでもあります。その結果、このようなシステムが得られます（歪みなし！）。

基本行列F（基本行列）を使用して、次の方程式を取得します。

また、Fのサイズは3x3であり、ランクは2でなければなりません。
基本行列Fから、必要なRとtを既に取得できます。 ただし、歪みはすべてを損なうため、フレーム間のポイントの依存関係は非線形になり、これは機能しなくなります。
しかし、正規化された点に進み、必須行列E（必須行列）を使用します。 すべてがほぼ同じですが、よりシンプルになります。
-必須マトリックスの方程式系;
-彼女のための方程式。
ここで、歪みを安全に考慮することができます。
基本行列と必須行列は次のように関連しています。

ここで、基本行列Fまたは必須行列Eのいずれかを見つけるタスクに直面します。これらの行列から、後でRお​​よびtを取得できます。

必須行列の計算（8ポイントアルゴリズム）

方程式に戻る：

同じ形式をこの形式で書き換えることができます（ そして ）：
、パラメータiは便宜上ここでは省略されていますが、各ポイントでこれが当てはまることを意味します。
ベクトルeと行列Mを導入します。


次に、方程式系全体を次のように表すことができます。

方程式の同次系を取得し、それを解いて、eからEを取得します。ここでの明らかな解決策はゼロベクトルですが、興味はありません。 解決するには最低8ポイントが必要です。

特異展開を使用した同次方程式のシステムを解く

特異分解は行列の分解であり、次の形式になります。
ここで、U、Vは直交行列、Wは対角行列です。 さらに、行列Wの対角要素を降順で配置するのが一般的です。 また、行列Wのランクは行列Mのランクです。また、Wは対角行列なので、そのランクは非ゼロの対角要素の数です。

そのため、次の形式の方程式が与えられました。
ここで、Mは既知の行列、eは検出されるベクトルです。

同じ行のゼロ対角要素Wに対応する行V ^Tは、行列Mのゼロ空間です。つまり、この場合、システムの線形独立解です。 そして、Wの要素は降順で配置されているため、行列Wの最後の要素を調べる必要があります。そして、解は最後の行です 。
8ポイントを使用して必須マトリックスを計算する場合、マトリックスWの最後の要素はゼロ-W ₉₉ = 0である必要がありますが、実際には、エラーの結果として、ゼロ以外の値があり、この値の大きさを使用してこのエラーの値を推定できます そうすることで、最高のソリューションを取得します。
それにもかかわらず、私たちが見つけた解決策は唯一のものではなく、さらに、無限に多くの解決策があります。 見つかった解に任意の係数を掛けても、解のままです。 したがって、係数s（任意の可能性があります）は方程式に隠されていました。
。
確かに、これらのソリューションはすべて線形に依存し、そのうちの1つだけが興味を持っています。
したがって、行列Eもスケーリングできます。 つまり、計算は均一な空間で実行され、結果として、スケーリング（つまり、係数s）に依存しません。
E ₃₃ = 1になるように、結果の行列Eをスケーリングする価値があるでしょう。

必須行列の計算（7ポイントアルゴリズム）

あなたは7ポイントで得ることができます。
7点しか取らない場合、Mは7x9行列になります。
式に戻る：

W-は以前と同様に9x9行列にもなりますが、W ₉₉はゼロになるだけでなく（計算エラーを考慮せずに）、W _88にもなります。 これは、方程式の線形に独立した2つの解があることを意味します。 。 それらから、2つの行列E ₁およびE ₂を取得します。 解決策は式です 。
基本マトリックスと同様に、必須マトリックスのランクは2でなければならず、サイズが3x3であるため、マトリックスの行列式は0- 。 だから 。 この方程式を書くと、1つまたは3つの解を持つ3次方程式が得られます 。 したがって、1つまたは3つの行列Eを取得します。
この方程式の解法を説明しません（この宿題を考えてみてください）。 極端な場合、 opencvの実装をすぐに見ることができます。

必須（基本）マトリックスの改良

この世界のすべてが不完全であるため、対処する必要があるエラーを常に受け​​取ります。 したがって、必須行列のランクは2でなければならず、したがって 。 ただし、実際にはそうではありません。
これが何で表現されているかを見るために、基本的なマトリックスを使用します。 エッセンシャルマトリックス/ファンダメンタルマトリックス-唯一の違いは、使用するポイント（正規化されたポイントまたは画像内のポイント）です。
フレームAのポイントから放出されたレイは、フレームBに直線として存在します（または、歪みによるものではありませんが、忘れてしまいます）。 行列FがフレームAおよびBの基本行列であると仮定します（ ）
次に、ポイントからビームを放した場合 、その後、フレームBで行lを取得します- 。 この線はエピポーラ線と呼ばれます。 ここで、ix、iyは画像内のポイントの座標です。 そして、均一な座標を持つ画像内のポイントに対して同じ条件- 。 ポイント したがって、この行にあります 。 ここから一般的な式が来ます- 。

この図は、正しい基本行列（ランクが2、右が画像）から取得されたエピポーラ線と、正しくない画像（左）の例を示しています。
正しい基本マトリックスを取得するには、特異展開のプロパティを使用して、マトリックスを指定されたランクに近似します。
。 理想的には、W ₃₃ （対角線の最後の要素）はゼロでなければなりません。 新しい行列W 'を導入します。これはWに等しく、要素W' ₃₃ = 0のみです。
次に修正されたバージョン： 。
エッセンシャルマトリックスにもまったく同じ原理が適用されます。

アルゴリズムの正規化バージョン

計算で得られるエラーを減らすために、ポイントは特定のビューに変換されます。 マトリックスT ^AとT ^Bが選択され、それぞれ独立して、独自のフレームで、ポイントの平均座標をポイント（0、0）にシフトし、中心までの平均距離が ：

そして、行列T ^A、Bの形式は次のとおりです。 ここで、cはフレームポイントの平均座標、sはスケール係数です。
その後、通常のように必須行列を計算します。 上記のように、明確にする必要があります。 結果の行列をE ^tとして示します。
結果の必須行列は 。
要約すると：
繰り返しますが、基本的なマトリックスを見つける必要がある場合、すべての原則が保持されます。

エンティティマトリックスからカメラの位置を取得する

行列Hを導入します。
必須行列で特異分解を使用します。
次に、次のソリューションを取得します。



どこで 、 -カメラ位置の座標。
カメラ自体のローカル座標でのカメラの位置が必要です。 。
4つのソリューションが登場します。 。
8ポイントアルゴリズムの場合、4つのソリューションから選択します。 7点アルゴリズムの場合、3つの必須行列が出てきますが、そのうち12の解が得られます。 1つだけを選択する必要があり、エラーが少なくなります。

縮退ケース

必須行列の計算に戻りましょう。 方程式がありました：

次に、特異分解を使用してそれを解決しました。

この方程式の解は、行列Wのランク、またはこの行列の対角にあるゼロの数に依存します（これは行列のランクを反映していることを覚えています）。 それは単にエラーを考慮しているだけです。この場合はゼロ、ゼロに十分近い数値を考慮します。
そのようなオプションがあります：

• ゼロはありません。 解決策はありません。おそらくエラーが大きすぎます。
• ゼロ。 1つの解決策、ポイントの数が8以上の場合。
• 2つのゼロ。 1つまたは3つのソリューション。 7つ以上のポイントが使用されました。
• 3つのゼロ。 次に、条件が真でなければなりません 。 これは、カメラがフレームからフレームへ移動せず、回転のみがあった場合、つまりt =（0、0、0）の場合に可能です。 または、すべてのポイントが1つの平面上にあります。 2番目のケースでは、これらの点の座標とカメラの位置を見つける機会がまだありますが、他の方法でもあります。

空間内の点の座標の計算

今、3つ以上のフレームがあるとしましょう-A、B、C、...
-カメラフレームA、B、C、...の位置
-正規化されたポイント
ポイントを見つける必要がある

このシステムを次のように想像してください。


マトリックス形式で：


特異展開を使用して、ベクトルを見つけます どれ （上記の方法による）。 それから 、ここでsは未知の係数です。 出てきます 。

評価機能

評価関数（コスト関数）は、結果を取得したり、信頼性を評価したり、他の結果と比較したりするために必要です。
モデルを取る：
-期待される結果。
-ポイントの実際の値。
したがって、i番目のポイントの2乗誤差は次のようになります。 。
実際には、いくつかのポイントは他のポイントよりも信頼性の高い結果をもたらします。 そして一般的には、明らかに間違ったものを提供する人もいます。 その結果、信頼できるポイントのみを一般的なポイントの配列から選択する必要が生じ、残りは単純に計算から除外されます。
「信頼できる」ポイントを選択する最も簡単な方法は、何らかの制限（5ピクセルなど）を選択し、この制限未満のエラーを与えるポイントのみを取得することです（ ） ポイントは両方のフレームでカメラの前になければならないことを考慮に入れなければならないことに注意する必要があります。
したがって、推定関数-信頼できるポイントの数を入力できます。 そして、比較するときは、より多くの「信頼できる」ポイントを与える結果を選択します。
そして、別のより微妙な関数を使用できます：
、ここでlimitは選択した制限（5ピクセル）です。
最適なオプションは、価値が低くなるオプションです。 ここで、将来の計算のために「信頼できない」ポイントを削除する必要があることは明らかです。

RANSACメソッド

1. エッセンシャルマトリックスを計算する場合、「信頼性のない」ポイントを破棄する必要があります。これらのポイントは計算に大きな誤差をもたらすためです。 RANSACアルゴリズムを使用して、適切なポイントのセットを決定できます。
   サイクルを指定された回数（たとえば、100、400）繰り返します。
   
   • 計算のためにポイントの最小セットをランダムに選択します（7つあります）。
   • このセットから必須行列を計算します（1つまたは3つの行列を取得できます）
   • 評価関数は、各行列の信頼性を計算します
2. 前のサイクルから、最適な結果が得られる必須マトリックスを選択します。
3. 得られた必須マトリックスでエラーを与える計算のポイントを選択します;エラーは与えられたしきい値より小さくなります;
4. 得られたポイントのセットから、最終的なエンティティマトリックスを計算します。

一般的なアルゴリズム

1. 最初のフレームで「特別な」点を見つける
2. 2つの画像間の対応点を決定します。
3. RANSACを使用して、これら2つの画像に対応する必須の（または基本的な）マトリックスを見つけます。
4. 1つまたは3つのソリューションがあり、そこから4または12の可能な行列[R | t]を取得します。 カメラを両方のフレームに配置し、可能なマトリックスごとに空間内のポイントの座標を計算します。 それらから、評価関数を使用して最適なものを選択します。

次は？

最初は、2つのフレームしかないという仮定から始めました。
フレームのシーケンスを使用するには、シーケンスをフレームの連続したペアに分割するだけです。 フレームのペアを処理して、あるフレームから別のフレームへのカメラオフセットを取得します。 これから、残りのフレームのカメラの位置の座標を取得できます。

主なもの-カメラの位置を受け取ったら、さまざまな方法で行動できます：

• コレスポンデンスポイントを使用して空間内のポイントの3次元座標を取得すると、ポイントのクラウドが生成され、3次元モデルに変換できます。
• 基本行列を使用して深度マップを計算します。
• 2つのフレームを使用して、空間内のポイントの計算された座標を使用してSLAMのマップを初期化すると、次のフレームで位置座標を取得するのが簡単かつ迅速になります。
• よく、別の

一般に、説明されているアルゴリズムだけでなく、さまざまな方法を使用して、さまざまな方法で行動できます。

文学

基本マトリックス 、 エッセンシャルマトリックス 、 8ポイントアルゴリズム -ウィキペディアの詳細
Hartley、Zisserman-Computer Visionの複数ビュージオメトリがこの記事のスポンサーです