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

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

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

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

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

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

我們來看看解決上述困難的基本思路：

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

剛才計算同名點匹配代價時采用的是單個像素點的絕對值的差異，這樣很容易受到噪聲的干擾。規(guī)避方法有兩類：

• 換用更魯棒的單像素的代價函數(shù)
• 采用鄰域支持窗來計算整體代價

我們一個個講。

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

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

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

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

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

• 亞像素插值：我們上面計算的視差值都是離散的整數(shù)值，但實際場景物體存在連續(xù)變化的視差，我們希望得到以浮點數(shù)表示的更精細的視差值。一般來說，會采用某種二次的拋物線插值法，得到連續(xù)的視差值，計算量也比較低，結(jié)果也不錯。

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

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

Stefano Mattoccia, Stereo Vision: Algorithms and Applications, 2012

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