本文轉自徐飛翔的“立體視覺中的對極幾何——如何更好更快地尋找對應點 ”
版權聲明：本文為博主原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接和本聲明
什么是立體視覺立體視覺(Stereo Vision)是什么呢？我們可以這樣理解：立 體 視 覺 ( S t e r e o V i s i o n ) = 尋 找 相 關 性 ( C o r r e s p o n d e n c e s ) + 重 建 ( R e c o n s t r u c t i o n ) 立體視覺(Stereo Vision) = 尋找相關性(Correspondences) + 重建(Reconstruction)立體視覺(StereoVision)=尋找相關性(Correspondences)+重建(Reconstruction)
Correspondences: 給定一張圖片中的像素點，尋找其在另一張圖片中的對應點
。Reconstruction: 給定一組對應點對
，計算其在空間中對應點P的3D坐標。
Fig 1.1 立體視覺的尋找對應點和重建。那么，在本文中，其實我們要討論的內容就屬于如何去更好更快地尋找對應點。抱著這個問題，我們正式地開始討論對極幾何吧。
對極幾何假設我們現在有兩張從不同視角拍攝的，關于同一個物體的圖片，如Fig 2.1所示，最為樸素的想法就是從一個2D區域中去尋找對應點，這樣顯然我們的計算復雜度很高，而且還不一定精準，那么我們有沒有能夠改善這個算法的方案呢？我們能不能對對應點的可能搜索范圍進一步縮小呢？答案是可以的。
通過對極幾何的約束，我們可以把搜索空間限制在一個直線上，我們將這個直線稱之為對極線，顯然，這樣不僅提供了搜索的效率，還提高了搜索的精確度。如Fig 2.2所示。
Fig 2.2 通過對極幾何的約束，我們將搜索空間限制在了對極線上。這個對極幾何那么神奇，那到底是什么原理呢？且聽筆者慢慢道來。
對極約束為了簡單分析考慮，我們現在只是假設兩臺攝像機的情況，假設我們已經對攝像機進行了內外參數的標定[2]，也就是說，我們已經知道了攝像機的朝向以及彼此之間的距離，相對位置關系等，同時也知道了內參數，也就是焦距等等。那么我們假設現在這兩臺攝像機同時對某個現實物體點P PP進行成像，我們有幾何關系示意圖Fig 2.3。
Fig 2.3 對極幾何約束，其中P點是實體3D點，O和O'是焦點在Fig 2.3中，其中的是實體3D點，而O和
是兩個攝像機的焦點（對于焦點，讀者不妨看成是一個觀察者的視角，也就是你可以想象成你在O和
點觀察P點。），而成像平面
和
就是我們的成像面，其中面上的p 和
是實體點P的成像對應點，我們需要找的對應關系，其實就是
這樣的點對。
對于這兩個不同的相機坐標系，我們對于這兩個成像點有著不同的坐標系表達，讓我們分別以各自的焦點為原點，表達這兩個點，有：
對于Fig 2.3中的其他幾何元素，我們分別給予術語，以方便稱呼：
點e和點稱之為極點(epipole)線l 和
稱之為對極線(epipolar line)，其中l是點
的對極線，
是點p的對極線。焦點之間的連線
稱之為基線(Baseline)平面
稱之為對極面(epipolar plane)。具體的元素位置，我們還能參考圖Fig 2.4中的英語標注。
Fig 2.4 對極幾何的一些術語。
那么由圖Fig 2.3我們其實很容易發現，所謂的對極約束，指的就是，成像平面上的點p，其在
的對應點
必然在其對極線
上，這個關系可以由三者共面很容易看出來，其證明可參考[3]。也就是說，對于點p，如果我們要搜索其在另一個成像平面上的對應點，無需在整個平面上搜索，只需要在對極線上尋找即可了。如圖Fig 2.5所示，我們發現這個幾何關系其實是很直觀的。
再如圖Fig 2.6所示，這是個實際圖像的例子，我們發現我們剛才在幾何上的結論在實際中是成立的。
Fig 2.6 b和c上的對極線以及其對應點的位置。
同時，我們要注意到，我們的基線和成像平面的位置是不會改變的（假設不改變攝像機的相對位置的話），那么顯然，不管實體點P PP的位置在哪里，所有的對極線都是會經過極點的，如圖Fig 2.7所示,其中虛線表示不同的對極面，不管對極面是哪個，都是會經過基線的；相對應的，所有的對極線也是會經過極點的。
好的，那么我們以上就直覺上討論了對極約束，那么我們應該怎么用代數的方式去描述這個約束呢？畢竟只有用代數的方式表達，才能進行計算機的編程和實現。為了實現代數化，我們要引入所謂的本征矩陣。我們接下來討論這個。
本征矩陣還記得公式(2.1)中，我們曾經對兩個對應點p和進行了坐標表達嗎？假設我們現在知道了每臺攝像機的內部參數，并且圖像坐標已經歸一化[4,5]，這里所說的歸一化指的是假設存在一個焦距為1的面，如Fig 2.8所示，這里假設焦距為單位長度，是為了后面的分析方便而已，我們將會看到，當考慮實際焦距時，其處理略有不同。進行了歸一化之后，我們有：
其中是圖像點的單位坐標向量。
Fig 2.8 相機系統內的物理視網膜平面（也就是實際的成像平面）和歸一化成像平面（也就是焦距為1時的成像平面，是假想出來的平面，為了分析方便）。
OK， 不管怎么樣，我們繼續我們的討論。我們發現在Fig 2.3中，和
共面，我們用代數描述就是：
其中，×表示的是向量叉乘，我們知道空間向量叉乘表示求得其在右手坐標系中的正交向量，如圖Fig 2.9所示。
Fig 2.9 叉乘的幾何意義。而式子中的點積為0表示了垂直關系，因此式子(2.2)正確表達了我們的對極約束，我們接下來代入坐標。
考慮在中表示點p，通過坐標的平移和旋轉可以容易實現，見：
其中表示平移向量，
表示旋轉矩陣。那么反過來有：
令和
，我們有(2.4)的簡化形式：
令和
，我們有(2.4)的簡化形式：
考慮公式(2.2)，我們發現：
注意到，因為對于垂直關系而言，平移與否沒有影響，我們最終有式子：
其中，(2.7)第二行的公式表示在另一個成像平面表示
上的坐標，最后一行，我們把叉乘轉化成矩陣乘法操作[6]。對于一個
來說，其叉乘乘子的矩陣乘法形式為：
如果用? ，我們有：
我們把這里的稱之為本征矩陣(Essential matrix)。
我們發現，這里的旋轉矩陣其實是可以通過相機標定進行外參數估計得到的，同樣的，
也是如此。假設，我們現在已知了
上的點p，我們可以令
，我們知道這個是個常數向量。最終，公式(2.9)可以寫成：
我們發現(2.10)其實就是一個直線方程了，這個直線方程正是p 的對極線，我們需要搜索的對應點 正是在對極線上。
去掉歸一化坐標系的限制，引入基礎矩陣我們在本征矩陣那一節考慮的是歸一化的坐標系，那么如果在原始的圖像坐標系中，我們需要改寫成：
其中，是3 × 3 的標定矩陣，
是圖像點的單位坐標向量。那么我們有：
其中，矩陣稱之為基礎矩陣(Fundamental matrix)。
通常來說，無論是基礎矩陣還是本征矩陣都可以通過內外參數的標定來求得，特別地，通過足夠多的的圖像匹配計算，我們同樣可以無須采用標定圖像，也可以得到這兩個矩陣。
Reference
[1]. 電子科技大學自動化學院 楊路 老師 計算機視覺課程課件。
[2]. https://blog.csdn.net/LoseInVain/article/details/102632940
[3]. Hartley R, Zisserman A. Multiple View Geometry in Computer Vision[J]. Kybernetes, 2008, 30(9/10):1865 - 1872.
[4]. http://answers.opencv.org/question/83807/normalized-camera-image-coordinates/
[5]. http://answers.opencv.org/question/83807/normalized-camera-image-coordinates/
[6]. https://en.wikipedia.org/wiki/Cross_product