一文詳解三維重建中的立體匹配

來(lái)源丨計算攝影學(xué) 通過(guò)立體校正算法，可以把雙攝圖像對校正到標準形態(tài)，使得兩幅圖像的對極線(xiàn)水平對齊，就好像是我們創(chuàng )造了兩個(gè)內參相同的虛擬相機，它們指向同一個(gè)方向進(jìn)行拍攝原來(lái)的場(chǎng)景，得到兩幅新的圖像。
當做到這一點(diǎn)后，就可以很方便的在水平方向搜索一個(gè)圖像上的一點(diǎn)在另外一個(gè)圖像上的對應點(diǎn)。如下圖所示，左圖上的一點(diǎn)p在右圖上的對應點(diǎn)是p'，接下來(lái)就很方便的進(jìn)行三角測距，確定物點(diǎn)P的物距了。物距Z的計算公式可以很容易通過(guò)相似三角形得出：這里面, X_R-X_T叫做視差，而b是兩個(gè)相機光心的距離, f是焦距。這樣，求取空間點(diǎn)和相機之間距離的關(guān)鍵就變成了求取其投影點(diǎn)視差了。而整個(gè)圖像上所有點(diǎn)的視差構成了一幅圖像，這個(gè)圖像叫做視差圖，如下所示：而通過(guò)校正后的一對圖像獲取到視差圖的過(guò)程，叫做立體匹配，它有點(diǎn)像玩連連看的游戲：給計算機一對輸入圖像，指定左圖上的某個(gè)點(diǎn)，要求算法在右圖上找到它對應的投影點(diǎn)，然后將兩個(gè)點(diǎn)的橫坐標相減得到該點(diǎn)的視差。今天我就來(lái)好好聊聊立體匹配。我最喜歡的關(guān)于立體匹配算法的基礎教學(xué)課件是意大利Bologna大學(xué)的Stefano Mattoccia教授在2012年編寫(xiě)的"Stereo vision: algorithms and applications"（當時(shí)他還在佛羅倫薩大學(xué)）。這份講義涵蓋了立體匹配的諸多基礎知識，據我了解很多人也是通過(guò)這份文檔入門(mén)的。由于內容過(guò)于豐富，讀者自己閱讀時(shí)可能會(huì )理不清其中的邏輯關(guān)系，或丟失掉一些細節信息。我希望結合自己的理解，對這份講義加以導讀，幫助你更快的入門(mén)。

先來(lái)看看下面兩幅經(jīng)過(guò)立體校正的圖像，一幅稱(chēng)為Reference圖像(R)，一幅稱(chēng)為T(mén)arget圖像(T)?，F在希望求取兩幅圖像的視差圖，正如我上面所說(shuō)，這是一個(gè)讓計算機做連連看游戲的過(guò)程——給定R圖上一點(diǎn)，我們在T圖的同一行上搜索和R圖點(diǎn)匹配的同名點(diǎn)。這時(shí)，我們會(huì )將水平搜索約束在一個(gè)范圍內[0,  ]，如下圖所示現在的問(wèn)題是，如何判斷最匹配的點(diǎn)呢？一般來(lái)說(shuō)，我們會(huì )定義某種匹配代價(jià)，用來(lái)衡量?jì)蓚€(gè)像素的相似程度。那么匹配代價(jià)最低的那個(gè)像素，就會(huì )被選為同名點(diǎn)。最基本的匹配代價(jià)就是兩個(gè)像素的像素值的絕對差（我們可以暫且把圖像當做是單通道的灰度圖像），那么匹配代價(jià)就是：如果最小視差為0，候選的視差值d的值域范圍是從0到dmax的整數，那么可視化一下所有的匹配代價(jià)如下圖所示：從所有的候選像素中挑選匹配代價(jià)最低的作為最終的同名點(diǎn)，這個(gè)策略被稱(chēng)為Winner Takes All (WTA)，所謂的贏(yíng)者通吃那么，按照這種方法算出的視差圖如何呢？我們看看下面的結果，并和Groundtruth做下對比：肉眼判斷視差圖是否有錯誤可以通過(guò)下面幾個(gè)準則來(lái)觀(guān)察：

• 視差是近大遠小的，表現到視差圖上則是近亮遠暗
• 同一個(gè)物距的物體表面的視差亮度是一致的
• 在物體的邊緣，如果物距發(fā)生了突變，那么視差圖上也應該有突變的邊緣
• 物距漸變時(shí)，視差圖上也是平滑變化的

很明顯，相比理想結果，這種方法的得到的視差圖充滿(mǎn)了噪聲，很多地方可以肉眼可見(jiàn)明顯的錯誤。我們上面這種簡(jiǎn)單的立體匹配算法很明顯是不足的。接下來(lái)，我會(huì )先談?wù)劻Ⅲw匹配的困難之處，再分析一下解決這些困難的方法。

在講義中，Stefano教授提到的困難之處包括了：在實(shí)際場(chǎng)景中，可以同時(shí)包含了以上多種困難之處，難怪立體匹配如此困難，上面那種簡(jiǎn)單的方法無(wú)法奏效。那么該如何應對這些問(wèn)題呢？

我們來(lái)看看解決上述困難的基本思路：

立體匹配的困難最終的反映為搜索同名點(diǎn)失敗上，如果是因為兩幅圖像的亮度、噪聲不一致，一般會(huì )先對圖像做預處理，使得兩幅圖像的整體質(zhì)量區域一致。這里面典型的方法有（這里括號中提到的參考文獻都是原講義的參考文獻，讀者可以自行查閱）

剛才計算同名點(diǎn)匹配代價(jià)時(shí)采用的是單個(gè)像素點(diǎn)的絕對值的差異，這樣很容易受到噪聲的干擾。規避方法有兩類(lèi)：

• 換用更魯棒的單像素的代價(jià)函數
• 采用鄰域支持窗來(lái)計算整體代價(jià)

我們一個(gè)個(gè)講。

1. 換用更魯棒的單像素的代價(jià)函數

這一類(lèi)方法依然是利用左右圖像上單一的像素點(diǎn)進(jìn)行代價(jià)計算。人們設計了很多不同的代價(jià)函數計算方式，分別都有自己的優(yōu)缺點(diǎn)，這里列出如下：像素差異絕對值 Absolute Differences平方差 Squared Differences上面兩種代價(jià)函數都容易受到噪聲的干擾，于是就有了更加魯棒的函數，比如：截斷絕對差 Truncated Absolute Differences (TAD）將絕對差限制在<=T的范圍內，避免噪聲引起過(guò)大的代價(jià)。這是一種簡(jiǎn)單的策略，其實(shí)并不比上面兩種好多少，因為T(mén)很難確定還有更復雜的，通過(guò)某種對圖像內容不敏感的方式來(lái)確定兩個(gè)像素的不相似度，比如Birchfield and Tomasi [27]中提到的方法。它考慮了當前像素，以及其旁邊的兩個(gè)像素。總之，僅僅考慮單個(gè)像素，還是很難得到好的結果。更好的方式是通過(guò)計算所關(guān)注的像素點(diǎn)的鄰域的整體情況，來(lái)提升信噪比，減少噪聲的影響。我們把這個(gè)鄰域范圍稱(chēng)為“支持窗(Support Window)”，通過(guò)支持窗內所有像素來(lái)計算一個(gè)匹配代價(jià)值。采用鄰域支持窗來(lái)計算整體代價(jià)這種策略就是把單個(gè)像素的計算轉換為一個(gè)支持窗內的整體計算了，比如：像素絕對差值和 Sum of Absolute differences (SAD)像素差值平方和Sum of Squared differences (SSD)截斷絕對差值和 Sum of truncated absolute differences (STAD)除了這些簡(jiǎn)單的代價(jià)函數，還有更多方法，比如利用兩個(gè)圖像的互相關(guān)信息的，利用圖像梯度域信息的，或是利用一些非參數方法的，等等。你可以參考原講義，找到參考文獻來(lái)閱讀。總之，我們可以為R中的每個(gè)像素點(diǎn)和選定的T中的像素點(diǎn)計算一個(gè)代價(jià)，并且這個(gè)代價(jià)還具有很高的區分度。如前所述，我們是在一個(gè)范圍[dmin, dmax]中搜索匹配點(diǎn)，因此對任何一個(gè)R中的像素點(diǎn)，可以算出dmax - dmin + 1種代價(jià)值。如果圖像的寬高分別為W和H，那么我們總共會(huì )得到W x H x (dmax - dmin + 1）種代價(jià)值。所有這些代價(jià)值可以存儲到一個(gè)立方體中，這就是所謂的代價(jià)立方體，如下所示：

通過(guò)支持窗計算代價(jià)已經(jīng)對圖像的噪聲、光照不一致等等提升了一定的魯棒性，但依然有很多問(wèn)題遺留下來(lái)。我用一個(gè)基本的例子加以說(shuō)明。讓我們用一個(gè)改進(jìn)的流程來(lái)處理之前給出的一對圖像：計算一個(gè)簡(jiǎn)單固定尺寸方形支持窗內的截斷絕對差值和STAD，然后用WTA策略計算視差。看看上面的結果，比起最基礎的方案，視差圖似乎平滑了很多，沒(méi)有了大片的噪聲。但是很多局部是錯誤的，比如說(shuō)燈罩邊緣變得凹凸不平，背景出現異常的亮區，右上角也出現了異常的噪聲，燈架斷開(kāi)，等等。固定支持窗，英文是Fixed Window，簡(jiǎn)稱(chēng)FW。上述結果不夠理想，是因為FW策略違背了一些基礎假設。我們一一列舉一下：1. FW假設支持窗是正對相機的平面，支持窗內的所有點(diǎn)的視差是一致的，這顯然和實(shí)際情況不一樣。比如下面場(chǎng)景標注的支持窗，就顯然不是正對相機的平面：這里人頭部分是帶弧度的，而下圖的平面應該是傾斜的。2. 支持窗忽略了窗口內深度不連續，甚至有突變的情況，而強行把窗口內的視差值加權平均到一起。這就會(huì )導致產(chǎn)生的視差圖內出現大量的物體邊緣錯誤。如下圖所示：理想情況下，支持窗應該只包含同一深度的像素點(diǎn)，像下面一樣。我后面會(huì )給出一些進(jìn)行這些努力的方法。然而，現實(shí)情況是由于固定方形窗口的優(yōu)點(diǎn)，很多算法還是采用了它。于是為了避免上面這種包含過(guò)多不同視差像素在同一個(gè)支持窗的現象，就需要適當的減小窗口的大小。但這又和我們一開(kāi)始用支持窗來(lái)去除視差圖中的噪聲，提升信噪比的初衷違背了——于是，就需要根據實(shí)際場(chǎng)景的要求，經(jīng)驗性的調整支持窗的大小，這顯然不是一件容易的事情。3. 當場(chǎng)景中有大面積的重復紋理、無(wú)紋理的部分時(shí)，小尺寸的支持窗無(wú)法解決同名點(diǎn)計算錯誤的問(wèn)題，這種情況下可能出現很多候選像素點(diǎn)的代價(jià)值都一樣，難以區分的情況。比較好的策略是在這些區域用盡可能大的支持窗，來(lái)提升信噪比和像素之間的區分度。而這又和上面希望減小支持窗大小避免深度不連續影響相矛盾——顯然一個(gè)單一尺寸的支持窗無(wú)法應對兩種情況。很明顯，當完成3.2節所說(shuō)的代價(jià)計算得到代價(jià)立方體后，由于計算過(guò)程中的上述問(wèn)題，代價(jià)立方體中肯定有許多的噪聲和錯誤。下面右圖是另外一個(gè)場(chǎng)景，你應該也能觀(guān)察到其視差圖中的錯誤。盡管固定支持窗有這樣那樣的缺點(diǎn)，但它理解和實(shí)現都很容易，且非常便于并行化，在現代處理器上也比較容易做到實(shí)時(shí)運行，非常容易采用FPGA這樣的硬件進(jìn)行實(shí)現，性?xún)r(jià)比很足！所以很多傳統算法的代價(jià)計算這一步都是采用固定大小支持窗來(lái)完成的。而要繼續提升最終算法的效果，還得靠后續的步驟。這里主要有兩大類(lèi)思路，也就是局部聚合思路，和全局優(yōu)化思路。

局部聚合思路是通過(guò)對代價(jià)立方體中同一視差的代價(jià)進(jìn)行某種程度的聚合，來(lái)減少或消除錯誤代價(jià)的影響，這一步就是所謂的代價(jià)聚合(Cost Aggregation)。比如下面左圖，同一個(gè)視差的窗口我們會(huì )擴大并將代價(jià)立方體中相應的代價(jià)聚合在一起。而下面右圖則說(shuō)明在聚合過(guò)程中要避免混合不同視差的像素。Stefano Mattoccia教授的講義中介紹了各種各樣代價(jià)聚合方法，它們一般來(lái)說(shuō)是通過(guò)調整支持窗的位置、形狀、窗內各像素的權重等等來(lái)完成聚合的。我會(huì )在下一篇文章中為你導讀講義中提到的各種各樣的局部代價(jià)聚合方法?？傊?，通過(guò)局部的代價(jià)聚合，有可能得到非常不錯的效果，比如下圖中所示的一個(gè)利用了局部一致性的方案，相比FW的效果得到了很大的提升。3.3.2 視差優(yōu)化(Disparity Optimization)而全局優(yōu)化思路，則是希望尋找到每個(gè)像素的最優(yōu)視差結果，使得全局的、整體的匹配代價(jià)最小，這一步被稱(chēng)為視差優(yōu)化(Disparity Optimization)。于是這個(gè)過(guò)程就變成了一個(gè)最優(yōu)化某個(gè)能量函數的過(guò)程，該函數通常寫(xiě)成如下的形式：等號右邊第1項是數據項，用于約束全局代價(jià)最小化。但是代價(jià)立方體中通常含有噪聲和錯誤，直接最小化求得的結果也會(huì )有很多問(wèn)題，所以還需要第2項平滑項。這一項一般用于給出某些額外的約束條件，比如通常假設整個(gè)圖像的視差是平滑變化的。這樣視差的大變化只會(huì )在場(chǎng)景內視差邊緣處產(chǎn)生，一般也和圖像內物體邊緣高度相關(guān)。對上述能量函數的最優(yōu)化過(guò)程是一個(gè)非常困難的問(wèn)題，所以一般會(huì )有一些近似求解方法，比如講義中提到的：還有就是用將全局能量函數的最優(yōu)化轉換為針對圖像中的子部分的最優(yōu)化，比如約束到某些掃描線(xiàn)方向上的最優(yōu)化，然后利用動(dòng)態(tài)規劃或掃描線(xiàn)優(yōu)化等方式去求解。關(guān)于視差優(yōu)化，我也會(huì )在后面專(zhuān)門(mén)的文章中再闡述細節。但至少當時(shí)，全局法的效果確實(shí)比起很多局部法要好，我們看下面這些例子，就很清楚了：

前面介紹的步驟最終將輸出一張視差圖，然而正如你已經(jīng)看到的，即便是在上面那些受約束的場(chǎng)景，得到的視差圖依然不是完美的，還是有很多錯誤。因此，還需要一個(gè)后處理的步驟，來(lái)消除其中的錯誤，得到更準確的視差圖，這一步被Stefano教授稱(chēng)為Disparity Refinement。我感覺(jué)Disparity Refinement比較容易和全局法的Disparity Optimization在字面上混淆，因此就翻譯做視差后處理吧，如下圖所示。這一步需要解決哪些問(wèn)題呢？這包括了：

• 亞像素插值：我們上面計算的視差值都是離散的整數值，但實(shí)際場(chǎng)景物體存在連續變化的視差，我們希望得到以浮點(diǎn)數表示的更精細的視差值。一般來(lái)說(shuō)，會(huì )采用某種二次的拋物線(xiàn)插值法，得到連續的視差值，計算量也比較低，結果也不錯。

噪聲和錯誤消除：有時(shí)候會(huì )簡(jiǎn)單采用圖像濾波的技術(shù)來(lái)處理視差圖，也能得到不錯的結果。從簡(jiǎn)單的中值濾波，到復雜的雙邊濾波都有人嘗試。我會(huì )在之后的文章專(zhuān)門(mén)介紹一種強大的濾波類(lèi)的處理方法。另外一個(gè)重要的技巧是雙向匹配，這種方法分別以雙目圖像中左圖和右圖作為參考圖像R計算兩個(gè)視差圖（缺點(diǎn)：增加了計算量)。然后它認為一對匹配點(diǎn)的視差值是互反的，也就是說(shuō)一對正確匹配點(diǎn)的視差值會(huì )非常接近。如果不滿(mǎn)足這個(gè)條件那么對應的視差值應該就是錯誤的。比如下面紅色點(diǎn)的視差就計算錯誤了，而綠色點(diǎn)則是正確的。關(guān)于視差后處理，可談的內容也挺多的，考慮到篇幅限制，這里就先不深入了，之后的文章再補上吧?？傊?，通過(guò)組合前面的步驟，我們就可以得到最終的視差圖了。

今天這一篇文章是我要寫(xiě)的關(guān)于立體匹配的文章的第1篇，主要是對Stefano Mattoccia教授的講義的一個(gè)導讀。主要為你介紹了立體匹配的一些基本概念和步驟。在接下來(lái)的幾篇文章中，我還是會(huì )繼續導讀這份講義，主要展開(kāi)講解代價(jià)聚合、視差優(yōu)化，以及視差后處理。當這些部分都搞清楚后，我就會(huì )再介紹一些經(jīng)典的算法，包括傳統的局部法、全局法、半全局法，以及基于深度學(xué)習的某些方法。希望整個(gè)內容能有機的連成一片。當然，畢竟這是一個(gè)2012~2013年間的講義，很多后來(lái)的優(yōu)秀方法都沒(méi)有包含在內。比如我現在團隊所開(kāi)發(fā)的方法，已經(jīng)能在非常非常挑戰的場(chǎng)景下得到非常非常精細的結果了，這是以前這些方法無(wú)法想象的。但Stefano教授提到的這些本質(zhì)性的挑戰和優(yōu)化思想，依然在指引著(zhù)后來(lái)的研究者。我在之后也會(huì )介紹今年CVPR中我們的一篇文章，看看我們是如何把傳統視覺(jué)方法和深度學(xué)習方法結合起來(lái)，用到匹配中的。

Stefano Mattoccia, Stereo Vision: Algorithms and Applications, 2012

本文僅做學(xué)術(shù)分享，如有侵權，請聯(lián)系刪文。