.. _epipolar_geometry:


エピポーラ幾何
*********************


目的
========
このチュートリアルでは

    * 多視点幾何の基礎を学びます．
    * エピポール(epopole)，エピポーラ線(epopolar line)，エピポーラ高速(epipolar constraint)などについて学びます．
    

基本概念
=================

ピンホールカメラを使って撮影した画像は重要な情報(各画素の距離)を失っています．3次元空間を2次元画像に写像したことによって各画素に対応する点とカメラ間の距離が分からなくなってしまうとも言えます．そのため，ピンホールカメラを使って距離情報を計算できるのかというのは重要な疑問です．この問い対する答えは，「複数台のカメラを使えば可能」です．2台のカメラを使うことをステレオ視(stereo vision)と呼びますが，実は私たち人間の目の働きと同じように動作します．早速OpenCVが提供する技術を見ていきましょう．

(この分野に関しては，Gary Bradskyが書いた *Learning OpenCV* に多くの情報が載っています．)

距離画像の話を扱う前に多視点幾何の基本概念を理解しましょう．ここではエピポーラ幾何を扱います．以下の画像は，あるシーンを2台のカメラで撮影したシーンを描いています．

    .. image:: images/epipolar.jpg
        :alt: Epipolar geometry
        :align: center
        

もし左のカメラのみを使った場合，私たちは点 :math:`x` に対応する3次元点の3次元位置が分かりません．なｓぜなら，カメラの工学中心と点 :math:`x` を結ぶ直線 :math:`OX` 上の点であれば，どのような点でも点 :math:`x` に写像するからです．しかし，右のカメラで撮影した画像も考慮すると，直線 :math:`OX` 上の別の点は 右側の画像上で異なる点に写像されます．これより，2枚の画像があれば3次元点を正しく三角測量できることが分かります．これが多視点幾何における3次元計測のアイディアです．

直線 :math:`OX` 上の異なる点を右側カメラの画像平面上に投影すると，別の直線が形成されます(直線 :math:`l'` とします)．この直線は 点 :math:`x` の**エピポーラ線(epiline)** と呼びます．右側画像上で点 :math:`x` を検出するためには，エピポーラ線上を探索すればよい事を意味します．対応点はこの直線上のどこかにあるべきです．言い換えると，対応点の探索は右側画像中を全探索する必要は無く，エピポーラ線上を探索すればよいので処理速度と精度の向上につながります．この現象を **エピポーラ高速(Epipolar Constraint)** と呼びます．同様に，あらゆる点に対してエピポーラ線を描くことができます．3次元点 :math:`X` と両光学中心 :math:`O` ， :math:`O'` が形成する平面 :math:`XOO'` は **エピポーラ平面(Epipolar Plane)** と呼ばれます．

上記の構成から，右側のカメラの光学中心 :math:`O'` を左側画像へ写像したものが :math:`e` になると分かります．この点を **エピ極(epipole)** と呼びます．エピ極はカメラの光学中心を通る直線と画像平面の交点になります．同様に :math:`e'` は左側カメラに対応するエピ極です．場合によって(カメラの位置関係によって)エピ極が画像上に写らないこともありますが，その場合はエピ極は対応するであろう点は画像の外に位置する(つまり，カメラはお互いが視野角に入っていない)ことになります．

全てのエピポーラ線はエピ極を通過します．つまりエピ極の位置を見つけるためには大量のエピポーラ線を探し，それらの交点を見つければよいことになります．

ここではエピポーラ線の検出とエピ極の検出を取り扱います．これらの検出には **基礎行列(Fundamental Matrix ) (F)** と **基本行列(Essential Matrix) (E)** の二つの要素が必要になります．基本行列（Essential Matrix)は左側カメラに対する右側カメラの相対的な位置・姿勢の情報を含んでいます．以下の画像を見てください(画像は以下から転載: Learning OpenCV by Gary Bradsky):

    .. image:: images/essential_matrix.jpg
        :alt: Essential Matrix
        :align: center 
 
しかし，できれば画素単位での計測が好ましいですよね？基礎行列(Fundamental Matrix)は基本行列の持つ情報に加え，両カメラの内部パラメータの情報も含みます．そのため，二台のカメラの関係を画素単位で表せることになります．(もしステレオ画像の併行化を行い点の座標を焦点距離の長さで割れば， :math:`F=E` が成り立ちます)．簡単に言うと，基礎行列Fは画像中のある点を別の画像中の線(エピポーラ線)に写像する行列です．基礎行列の計算には少なくとも8組の対応点が必要になります(8点アルゴリズムを使えば)が，それ以上の数の対応点を使いRANSACによるロバスト推定を行った方が結果がロバストになります．

実装(コード)
=================

基礎行列を計算するためには2枚の画像間で出来るだけ多くの対応点対を見つける必要があります．ここではSIFT特徴量とFLANNに基づくマッチングを使って対応点対の検出を行います．
::

    import cv2
    import numpy as np
    from matplotlib import pyplot as plt

    img1 = cv2.imread('myleft.jpg',0)  #queryimage # left image
    img2 = cv2.imread('myright.jpg',0) #trainimage # right image
     
    sift = cv2.SIFT()
     
    # SIFTを使った特徴点検出と特徴量の計算
    kp1, des1 = sift.detectAndCompute(img1,None)
    kp2, des2 = sift.detectAndCompute(img2,None)
     
    # 対応点探索のためのFLANNのパラメータ設定
    FLANN_INDEX_KDTREE = 0
    index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
    search_params = dict(checks=50)

	# 対応点検出
    flann = cv2.FlannBasedMatcher(index_params,search_params)
    matches = flann.knnMatch(des1,des2,k=2)
     
    good = []
    pts1 = []
    pts2 = []
     
    # Loweの論文に記載されている特徴量の類似度の比に基づくマッチングの評価
    for i,(m,n) in enumerate(matches):
        if m.distance < 0.8*n.distance:
            good.append(m)
            pts2.append(kp2[m.trainIdx].pt)
            pts1.append(kp1[m.queryIdx].pt)
            

この段階で両画像から取得した対応点対のリストを保持しています．次に，これらの対応点群から **cv2.findFundamentalMat** 関数を使って基礎行列を計算します．ここでは第3引数に ``cv2.FM_LMEDS`` を指定し，ロバスト推定を行っています．
::

    pts1 = np.int32(pts1)
    pts2 = np.int32(pts2)
    F, mask = cv2.findFundamentalMat(pts1,pts2,cv2.FM_LMEDS)
     
    # 外れ値を取り除きます
    pts1 = pts1[mask.ravel()==1]
    pts2 = pts2[mask.ravel()==1]
    

次にエピポーラ線を計算します．1枚目の画像上の点に対応するエピポーラ線は2枚目の画像上に表示されます．ここでは正しい画像を選ぶ必要があります．複数のエピポーラ線を配列として保持しているので，これらの画像上にエピポーラ線を描画する関数を作成します．
::

    def drawlines(img1,img2,lines,pts1,pts2):
        ''' img1 - img2上の点に対応するエピポーラ線を描画する画像
            lines - 対応するエピポーラ線 '''
        r,c = img1.shape
        img1 = cv2.cvtColor(img1,cv2.COLOR_GRAY2BGR)
        img2 = cv2.cvtColor(img2,cv2.COLOR_GRAY2BGR)
        for r,pt1,pt2 in zip(lines,pts1,pts2):
            color = tuple(np.random.randint(0,255,3).tolist())
            x0,y0 = map(int, [0, -r[2]/r[1] ])
            x1,y1 = map(int, [c, -(r[2]+r[0]*c)/r[1] ])
            img1 = cv2.line(img1, (x0,y0), (x1,y1), color,1)
            img1 = cv2.circle(img1,tuple(pt1),5,color,-1)
            img2 = cv2.circle(img2,tuple(pt2),5,color,-1)
        return img1,img2
        

これで両画像上にエピポーラ線を描けるようになります．
::

    # 右画像(二番目の画像)中の点に対応するエピポーラ線の計算
    # 計算したエピポーラ線を左画像に描画
    lines1 = cv2.computeCorrespondEpilines(pts2.reshape(-1,1,2), 2,F)
    lines1 = lines1.reshape(-1,3)
    img5,img6 = drawlines(img1,img2,lines1,pts1,pts2)
     
    # 左画像(一番目の画像)中の点に対応するエピポーラ線の計算
    # 計算したエピポーラ線を右画像に描画
    lines2 = cv2.computeCorrespondEpilines(pts1.reshape(-1,1,2), 1,F)
    lines2 = lines2.reshape(-1,3)
    img3,img4 = drawlines(img2,img1,lines2,pts2,pts1)

	# 結果の表示
    plt.subplot(121),plt.imshow(img5)
    plt.subplot(122),plt.imshow(img3)
    plt.show()
    

以下に結果画像を示します:

    .. image:: images/epiresult.jpg
        :alt: Epilines
        :align: center 
        

左画像中の全てのエピポーラ線が画像の外側(右)の一点で交差している事が分かります．この交点がエピ極です．

より良い結果を得るためには解像度の良い画像を撮影したり，3次元的に分布している対応点を使って基礎行列を計算する必要があります．


補足資料
==========================


課題
=============

#. 重要なトピックの一つとしてカメラの前進運動が挙げられます．前進運動をするカメラによって撮影された2枚の画像のエピポールは，エピポーラ線が一点で交差するため同じ位置に観測されます．詳しくは ` この資料<http://answers.opencv.org/question/17912/location-of-epipole/>`_ を参照してください．

#. 基礎行列の推定はマッチングの精度(外れ値など)に対して敏感です．全対応点が同一平面上に乗っている時，精度が悪くなってしまいます．詳しくは `この資料 <http://answers.opencv.org/question/18125/epilines-not-correct/>`_ を参照してください．