画像から3次元データを復元する技術の調査　三次元座標の算出の原理　～ステレオカメラによる三角測量～


#もくじ
「画像から3次元データを復元する技術の調査　(1)概要」
https://qiita.com/akaiteto/items/caa8d64b1afd1fee7563

#このシリーズについて
カメラをつかって三次元情報を復元する技術について調査したことを
個人的な「勉強ノート」としてまとめる。
とくにＭＶＳの処理に関心があるので、最終的にはMVSの各手法を原理レベルで記載したい。
そのうち点群操作系のアルゴリズムも勉強したい。

#はじめに
「三次元座標の算出の原理」では、単眼カメラとステレオカメラを対比させながら、
実際にどのようにして画像から三次元座標を算出するかを記載する。

「三次元座標の算出の原理」で説明する方法は２つ。
１つ、ステレオカメラを使った三角測量による手法。
２つ、単眼カメラによる複数視点の画像を用いたエピポーラ幾何による手法。
これらの手法の原理について、できるかぎり導出の部分を省かずに記載する。
分量の問題で、このページではステレオカメラによる三角測量について記載する。

加えて、コンピュータービジョンにおける基本的な知識である
内部パラメータ、外部パラメータ、射影行列、ピンホールカメラモデルについても説明し、
また、高校数学レベルから大学レベルまでの数学に関する基本的な知識についてもできるだけ説明した。

よって、本来は数ページに分けるところを一気に書いてあり、
冗長な部分もあるのでご了承ください。（エピポーラ幾何はくそながいです・・・。）

#前提
![tri.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/6cf7dedb-aea2-0a40-fd0f-fb2d224e3e4b.png)
上図は、左と右、２つの視点から撮影された画像を図にしたものである。
$x_{L}$と$x_{R}$は同じ物体の同じ点を指していて、$X$はこれら２つの点が示す３次元座標である。
エピポーラ幾何と三角測量においては、$x_{L}$と$x_{R}$が既知である前提知識のもとで$X$の算出が行われる。

よって大前提として、2つの写真においてどのポイントが対応しているのかを把握していなければならない。
人間の目で見ればどこが同じであるかは明らかだが、計算機は計算してやらないとわからない。
![match.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/8fdb188c-7043-b911-ad92-0262ee35e8b3.png)

したがって、計算機では最初の初期処理として「特徴点抽出」「特徴点マッチング」を行い、
２つの画像から$x_{L}$と$x_{R}$のような対応付けられたポイントを抽出する。

上記の画像は抽出した特徴点をマッチングさせた例である。
以降では、「特徴点抽出」「特徴点マッチング」により対応するポイントが
既知であるという前提のもと、説明を行うものとする。

なお、特徴点抽出と特徴点マッチングについては筆者が必要になった際に
別のページに記載するかもしれないししないかもしれないのでそちらを参照してください。

#（１）三角測量（triangulation）
ステレオカメラでは三角測量を適用させることで三次元情報を計算する。
この項では、ステレオカメラによる三角測量とはどういった原理であるかを記載する。

##（１－０）基礎知識０　ピンホールカメラ

いざ説明。・・・・の前に、カメラに関する基本的な知識について記載する。

「前提」の項では、
「物体のポイント$X$」「画像の映る面$X_{R}$」「カメラの位置$O_{L}$」の順で並ぶように三角の図を示した。
しかしこの図の位置関係は実は現実では発生しえない図である。

小学生理科で学んだレンズの知識をまだ覚えている人は
カメラの図と聞くと以下のような図をイメージするだろう。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/b32ce34c-7947-e421-3c82-87146b417886.png)
いわゆるピンホールカメラ。ピンホールカメラはフィルタに映し出す像が上下に逆転し、レンズの後ろ側に像が発生する。
「物体のポイント$X$」「画像の映る面$X_{R}$」「カメラの位置$O_{L}$」ではなく、
「物体のポイント$X$」「カメラの位置$O_{L}$」「画像の映る面$X_{R}$」が本来現実で発生する位置関係なのである。

この図こそが物理的に正しい状態なのだが、どうにもこの図は直感的にわかりづらい。
よって画像処理の分野においては、分かりやすくするために、以下のように図を記載する場合がほとんどである。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/463dbdd0-ac58-6962-8d81-2606f249bebf.png)
青い三角と赤い三角が相似の関係であるため、図のように書いても差異は発生しない。
よって、前提の項では「物体のポイント」「カメラの位置」「画像の映る面」の順に記載したことに注意されたい。

以降ではカメラと画像面と被写体の関係は「物体のポイント」「カメラの位置」「画像の映る面」の順で記載するものとする。
https://www.slideshare.net/ShoheiMori/ss-64994150

キーワード：ピンホールカメラモデル  Pinhole Camera Model

##（１－１）前提
「三角測量を用いて画像から三次元座標を求める」
これがこの項における最大の目的である。
三角測量を利用するために必要なものとして、２つのカメラ、２枚の写真が最低限必要となる。
これらを図に表現したものが下記の図。さきほども提示したのと同じ図である。
![tri.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/6cf7dedb-aea2-0a40-fd0f-fb2d224e3e4b.png)

そしてこの図を上から俯瞰的に見てみる。
先ほどの図では水色の面（画像が映し出される面）の向きが異なっていたが、
以下の図では、２つのカメラの向きが平行であると仮定して、２つの画像の面を平行にして修正している点に注意したい。
![tri2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/d304ad45-1d86-c8a7-5308-a86bcc36c08c.png)

図の文字の意味は下記の通り。
$P$　・・・・・・　三次元座標。これを求めたい。
$Z$　・・・・・・　物体との距離。俗にいうデプス。
　　　　　　　　この図ではカメラとの距離ではなく、カメラ間を中心とした距離であることに注意。
$f$　・・・・・・　カメラの焦点距離。Exif情報より既知。
$O_{l}$と$O_{r}$　・・・　カメラの位置
$T$　・・・・・・　２つのカメラの間の距離。ステレオカメラであれば既知。
$p_{l}$と$p_{r}$　・・・　画像平面
$x_{l}$と$x_{r}$　・・・　今まで書いた$x_{L}$と$x_{R}$とはちょっと違う。（わかりにくくてすみません…）
　　　　　　　　それぞれ、$p_{l}$と$p_{r}$の左端からのピクセルの長さを指している。
　　　　　　　　このときの差$|x_{l} - x_{r}|$を「視差」と呼ぶ。
　　　　　　　　ステレオカメラであれば、２枚の画像をもっているので既知。

![sfm.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/ad4b01fe-6b1f-7209-2ced-611830f0c317.png)
ここではあえてカメラの向きを変えずに平行移動させた場合を考える。
上の図でいうと左の例である。
カメラを平行移動させただけなので、$p_{l}$と$p_{r}$の画像平面同士は三次元空間内において「平行」となる。
この平行な関係を利用して、幾何学的な方程式を導き出すのが三角測量のミソである。

また、一般的なステレオカメラも同様にカメラが平行の向きを向いているが実はこれには深い意味があるのである。
![mynteye_s_img.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/ff05e75e-0312-1714-6467-947168178d24.jpeg)


以降、詳しく見ていく。

【参考】
http://www.cs.toronto.edu/~fidler/slides/2015/CSC420/lecture12_hres.pdf

##（１－２）幾何学的条件　デプスの推定
![tri4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/cd7407fd-0a1e-ffd0-0de0-5912e1c3f392.png)
前提に記載した通り、カメラを平行移動させただけなので、
$p_{l}$と$p_{r}$の面は平行になる。加えて、カメラの向きを真正面に固定すれば、
$p_{l}$と$p_{r}$の面と、２つのカメラの位置を直線で結んだ$O_{l}$と$O_{r}$は平行になるはずである。

その前提に基づけば、図のように赤い△と青い△はスケールが異なるだけの同質の三角形となる。
ステレオカメラが平行にカメラを配置して、垂直にカメラの向きを揃える理由は
実はこの２つの三角形の関係を作り出すため。
これらの三角形は、小学生算数でいうところの「相似」の関係。
赤い△と青い△が同じであるなら、「底辺」と「高さ」の比率は赤い△と青い△で全く同じになるはず。
これを等式でもって表現してみる。

青い△の「底辺」は$T$、
青い△の「高さ」は$Z$

赤い△の「底辺」は$T-(視差)= T - (x_{l} - x_{r}) = T - x_{l} + x_{r} $、
赤い△の「高さ」は$Z-f$

底辺/高さの比率が同じであることより、以下の式が求まる。
$\frac{T}{Z} = \frac{T - x_{l} + x_{r}}{Z-f}$

この式を変形し、距離$Z$を求める式に変形させる。
$Z = \frac{f・T}{x_{l} - x_{r}}$

$x_{l} - x_{r}$は視差であるので、画像上のピクセルの値より計算できる。
$f$は焦点距離であるので、Exif情報かカメラの機種名さえわかれば問題ない。
$T$はステレオカメラであれば既知の情報である。

よって上式により距離$Z$、いわゆるデプスが求まる。


##（１－３）幾何学的条件　三次元座標の推定
デプス$Z$は求まった。この数値を可視化させたものがデプスマップと呼ばれるものである。
![images.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/581710/34e28899-36ee-a6dc-ee21-9a29283533a3.jpeg)

しかし今求めたいのは$P$の三次元座標。
$Z$がカメラの位置からの距離ならまだしも、2つのカメラの間からの距離というのはちょっと都合が悪い。
ちなみにOpenCVであれば、reprojectImageTo3Dという関数を使うと、
デプスと視差より三次元座標が求まるらしい。（この手のQAがいくつか海外サイトにあったので一応記載）

数式で表すなら相似の関係を用いれば容易である。
$x_{l}$と焦点距離$f$、$O_{l}$がなす三角形と、青い三角形の相似より、
（１－２）と同じように比率から等式をつくると以下のようになる。
$\frac{f}{Z} = \frac{x_{l}}{P}$

これを変形させると以下のようになる。
$P = \frac{1}{f}Zx_{l}$

上式は焦点距離、画像の座標、求めたデプスより三次元座標が求まることを指している。
厳密にいえば上式はx座標の算出である。ほかの軸についても同様に計算を行う。
余談だがこの式は内部パラメータの逆行列でもって表現することも可能である。
（内部パラメータ。初出のワードであるがエピポーラ幾何の説明の項で説明するので分からない人はスルー推奨）

さて、いろいろごちゃごちゃ書いたが、これにより三次元座標の推定が可能となる。
以上がステレオカメラによる三次元座標の推定方法である。

【参考】
http://www.cse.psu.edu/~rtc12/CSE486/lecture12.pdf