【このテーマでは、きちんと記事にまとめる暇のない、速報的なメモ書きを掲載します。】
Multi-View Triangulationとは、多数の画像間でマッチングされた点の、各画像への投影位置（各画像上での座標）から、その点の3次元座標を求めることです。
日本語に訳せば、「多視点三角測量」でしょうか。言うまでもなく、SfMに必須の処理の1つです。
Multi-View Triangulationの標準的なアルゴリズムは「再投影誤差の2乗和の最小化」だとされてきました（1)のp.13）が、Metashapeなどが多数の検証点の座標を瞬時に求めてくれるのを見るにつけ、より速い近似解法が使われている香りがします。
私には難解な文献も多く、例によって長らく勉強を怠っていましたが、今回、Multi-View Triangulationのアルゴリズムを平易に分類してくれている最新文献2)を見つけましたので、これを読みつつ理解したことをメモしていきます。論文2)に記載されていることと、私の解釈が混ざっていますので、ご注意願います。
A. Linear Method （線形解法）
タイポイントの同次座標をXで表すと、共線条件を右辺＝0の形で書き表したものを、投影の数だけ連立してAX = 0の形にまとめることが出来ます（1)のp.13にも登場）。この連立方程式の最小二乗解つまりは||AX|| = 0を満たすようなXを、特異値分解か固有値分解を使って求める方法です。
この古典的な方法は、数値的最適化が不要という美点がある一方で、再投影誤差の小さい解を求めるわけではなく、||AX||に幾何学的な意味が見いだせないという欠点があります。1)でも、Cの方法の初期値を与えるための方法として位置付けられています。
対策として、各方程式に重みをつけた方法 (Iterative-Eigen method)もあるようですが、それはまだ勉強していないため省略します。
C. L2 Triangulation Method （L2ノルム最小化法；都合によりBより先に置きます）
冒頭で標準的な方法として挙げた「再投影誤差の2乗和の最小化」です。最急こう配法、ニュートン法、LM (Levenberg-Marquardt) 法などの数値的最適化アルゴリズムを、再投影誤差の2乗和に適用します。
1)では"Gold Standard"とされているほか、私も理解しやすく、研究で使ってきました。なぜなら、バンドル調整と目的関数が同じ（再投影誤差2乗和）であり、「バンドル調整でカメラパラメータを固定した場合」と考えることができるためです。
しかし、局所最適解に陥りやすい（本当の最適解を見つけにくい）という欠点があります。画像がたったの2枚の場合でも、局所最適解に陥る場合がある（最適化空間に多峰性がある）そうです。
D. L∞ Triangulation Method（L∞ノルム最小化法）
Cの方法の欠点（局所最適解に陥りやすい）を克服するために編み出さた方法のようです。
なぜかは未勉強ですが、L∞ノルムを使うと最適化空間が準凸関数になるとか。
L∞ノルムとは、「絶対値が最大の要素の絶対値」を評価することにあたります。
一口に「L2ノルムの代わりにL∞ノルムを使う」と言っても、
- 1画像に関する再投影誤差を評価する際に、u, v成分（横・縦成分）の2乗和ではなく、絶対値が大きい方の絶対値を使うのか
- 多画像に関する再投影誤差の統計量として、2乗和ではなく、再投影誤差の絶対値が最大の画像における絶対値を評価するのか
B. Midpoint Method （中点法）
最後にもってきましたが、文献2)の分類Bは、全視線への距離の二乗和が最小となるような点を求める方法です。
私も論文5)で、名前も知らないまま、見かけの点を求めるために使用していました。
画像上ではなく3次元空間上での距離の和の最小化です。
高速である一方で、視線の向きが平行に近い場合は誤差が大きすぎるという欠点があるようです（※）。
※ 文献2)には"when the camera is parallel"と表記されていましたが、カメラの光軸の向きが平行な場合ではなく、目標点（座標を推定する対象の点）をみる視線が互いに平行に近い場合と解釈しました。光軸の向きは関係ないと思われるためです。しかし視線が平行に近い場合とは、2視点で喩えれば基線長が短い場合ですから、何をしても誤差は大きいのではないかと思います。このあたりは別途要勉強／検討です。