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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Stefano Mattoccia, Stereo Vision: Algorithms and Applications, 2012

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