最近知ったのですが、OpenCVにもいつの間にか多視点三角測量(Multi view triangulation)が実装されていたんですね。
ということで今回は、OpenCVのcv::sfm::triangulatePointsでも使われている、古典的なMulti view triangulationのアルゴリズムについて解説してみます。triangulatePointsはこの書籍のアルゴリズムを実装してます。この本は昔ながらの有用な3次元系のアルゴリズムを網羅しているため、英語が苦にならない人にはお勧めです。
Multi view triangulationとは
複数の画像の特徴点の対応付けと透視投影変換行列から、その特徴点の3次元座標を求めるのがMulti view triangulationです。すなわち、下記の式を満たす世界座標点\(\boldsymbol{X}_w=[X_w, Y_w, Z_w, 1]^T\)を見つけるわけです。
実際には諸々誤差の影響ですべての画像でこの式をぴったり満たす世界座標点は見つからないので、なるべく満たしそうな世界座標点を線形的に見つけてやります。基本的な考え方としては下図のように、再投影誤差(画像座標点と世界座標点を画像に投影した点の距離)が最小になるような世界座標点が、求めたい3次元点だろうという考えです。
Multi view triangulationのアルゴリズム
では実際に世界座標点の導出法について説明していきます。まず、上の透視投影変換の式を展開するとこのようになります。
表記を簡単にするために、透視投影変換行列の各行を\(\boldsymbol{p}_{1}^{T}, \boldsymbol{p}_{2}^{T}, \boldsymbol{p}_{3}^{T}\)とおきます。
すると先ほどの式はこうなりますね。
ここで、(3)’を(1)’と(2)’に代入して\(s\)を消して整理してやります。
特徴点の対応付けは複数枚の画像でわかっているはずですので、実際にはこの式は画像数分成り立ちます。
これを行列式で表すと
という風になります。実際は\([X_w, Y_w, Z_w, 1]^T\)を定数倍してもこの式は成り立つため、スケールの要素を加味して、
とおいてやります。\(S[X_w, Y_w, Z_w ,1]^{T}=[X’_w, Y’_w, Z’_w, S]^T\)とおいたわけですね。
さて、あとはこの行列の最小特異値に対応する特異値ベクトルを求めることで、一番それらしい\([X’_w, Y’_w, Z’_w, S]^T\)が求まります。最後に、スケール要素を削除して\([X_w, Y_w, Z_w]=[X’_{w}/S, Y’_{w}/S, Z’_{w}/S]^T\)としてやります。これで、特徴点の対応付けから世界座標点を求めることができました。
コメント