一. 前言

你好，歡迎你打開這篇文章，這是我的系列立體匹配算法介紹文章中承上啟下的一篇，請(qǐng)看看我們現(xiàn)在走到了哪一步：

當(dāng)前進(jìn)度 今天，我將通過這一篇文章，填滿上圖箭頭指向的格子！ 下面我展示了一對(duì)雙目相機(jī)拍攝的原始圖像，已經(jīng)過了立體校正：

一對(duì)做過立體校正后的雙目圖像 而下面左圖是OpenCV的SGBM算法得到的視差圖，右邊則是通過我今天要介紹的算法處理后的視差圖?？戳怂鼈兒?，我想你應(yīng)該對(duì)什么叫做”化腐朽為神奇“有了深刻印象了吧。

左：SGBM算法結(jié)果 右：今日介紹的算法結(jié)果 那么如此神奇的效果，是如何做到的呢？ 在復(fù)雜的問題進(jìn)行空間轉(zhuǎn)換，變換為小規(guī)模的易解問題的思想：

化簡(jiǎn)問題的思路 今天我介紹的這篇文章，也是基于這種思想的——事實(shí)上這就是同一個(gè)作者Jon Barron，基于相同思想的進(jìn)一步研究，

Jon Barron文章介紹 這個(gè)算法我在后文中會(huì)簡(jiǎn)稱為FBS，它是我在立體匹配的研究和工程應(yīng)用中最喜歡的算法之一。這個(gè)算法相比我之前介紹的Fast Bilateral-Space Stereo有什么不同呢？ 上一篇文章所講的Fast Bilateral-Space Stereo，解決的是立體匹配問題——它將立體匹配當(dāng)成下面的全局匹配代價(jià)最小化問題進(jìn)行解決。

Fast Bilateral-Space Stereo算法思想總結(jié) 這個(gè)算法的優(yōu)點(diǎn)我們已經(jīng)講過了，在此不再贅述。然而它也有明顯的缺點(diǎn)。 首先是其匹配代價(jià)函數(shù)過于簡(jiǎn)單，上面公式中第二項(xiàng)是就是匹配代價(jià)項(xiàng)，也即是數(shù)據(jù)項(xiàng)。為了盡可能簡(jiǎn)單快速求解，作者采用了下面這樣非常簡(jiǎn)單的形式：

簡(jiǎn)化的立體匹配代價(jià)函數(shù) 圖示如下：

圖示這種簡(jiǎn)化問題的思路 然而，正是因?yàn)槠湫问椒浅：?jiǎn)單，因此效果也不夠好，很容易出現(xiàn)大大小小的錯(cuò)誤。 Fast Bilateral-Space Stereo算法的另外一個(gè)問題是，作者把上述代價(jià)映射到了雙邊空間，用一種叫做L-BFGS的方法進(jìn)行求解，這是Broyden,Fletcher,Goldfarb,Shanno這幾位數(shù)學(xué)家發(fā)明的優(yōu)化算法，他們名字的首字母組合就是BFGS。這是一種迭代式的求解方法，它的求解速度是比較慢的。

同時(shí)，F(xiàn)ast Bilateral-Space Stereo的求解方法也無法應(yīng)用到深度學(xué)習(xí)過程中，因?yàn)槠浯鷥r(jià)函數(shù)也無法求導(dǎo)進(jìn)行反向傳播。這一點(diǎn)我之后再談。 今天要講的FBS，則采用了特別不一樣的思想，如下圖所示。Fast Bilateral-Space Stereo的一大缺點(diǎn)就是采用了較低質(zhì)量的匹配函數(shù)，所以Fast Bilateral Solver（即所謂FBS）干脆不自己做匹配，而是允許其他算法算出一個(gè)初始的還不夠好的視差圖，然后再通過最優(yōu)化一個(gè)全局代價(jià)函數(shù)來優(yōu)化這個(gè)初始的視差圖，最終得到一個(gè)更好的結(jié)果：

FBS思想 在作者論文中開篇就用下面這幅圖來說明了這個(gè)思想：

利用FBS優(yōu)化視差圖 我一開始給大家呈現(xiàn)的關(guān)于貓貓的視差圖（下面右圖)，就是用FBS處理了SGBM算法的結(jié)果(左圖)后得到的，這也是我最喜歡的FBS的用法：

左：SGBM算法結(jié)果 右：FBS優(yōu)化左圖的結(jié)果 FBS的優(yōu)秀之處在于它不僅僅可以用于優(yōu)化初始的視差圖，還能做得更多，比如視差圖或深度圖圖的超分辨率重建。這里有一個(gè)低質(zhì)量的輸入視差圖y，以及一個(gè)參考圖像R，通過FBS可以得到高質(zhì)量的輸出圖像x，其中x相對(duì)于參考圖像R滿足雙邊平滑的特性，且其邊緣貼合參考圖像的邊緣，同時(shí)x還與輸入圖像y盡可能相似。

在圖像超分鐘應(yīng)用FBS 另外一個(gè)有趣的應(yīng)用是用戶引導(dǎo)的灰度圖像上色。這里也有低質(zhì)量的輸入圖像y，即用戶指定的最終色彩圖像的骨架，原始的灰度圖像則作為參考圖像。再指定一個(gè)置信度圖c，我們一樣通過FBS求解輸出彩色圖像x，并且要求x自身相對(duì)參考圖像來說是雙邊平滑的，同時(shí)還在高置信度的區(qū)域和用戶輸入y盡可能一致。

在圖像上色中應(yīng)用FBS 看出來了吧？FBS算法可以用于優(yōu)化任意的輸入圖像，只要給出了一個(gè)參考圖像和一個(gè)目標(biāo)圖像，它就會(huì)努力的讓輸出圖像既能夠按照參考圖像來雙邊平滑，又能夠非常接近目標(biāo)圖像，所以這是一種非常通用的算法。那么在下一節(jié)中，我們從原理上理解一下FBS算法。

二. FBS算法的應(yīng)用目標(biāo)和原理

2.1 FBS算法要解決的問題

用數(shù)學(xué)公式更加嚴(yán)謹(jǐn)?shù)恼f明一下FBS吧。我們的目標(biāo)是求解一個(gè)未知的圖像x，它本身相對(duì)于參考圖像R是雙邊平滑的(下式第1項(xiàng))，但在高置信度的區(qū)域又是和輸入的目標(biāo)圖像t又是非常接近的。

FBS試圖優(yōu)化的全局代價(jià)函數(shù) 剛才給過的這張圖，清晰的展示了上面公式的4張圖。左上圖為目標(biāo)圖像t，是由一個(gè)立體匹配算法得到的初始視差圖。而右上圖是輸出圖x，是經(jīng)過FBS優(yōu)化得到的結(jié)果。左下圖是置信度圖c，右下圖則是輸入的參考圖像R，上面公式中的W就是由輸入?yún)⒖紙D像R計(jì)算而來的。

FBS應(yīng)用到視差后處理優(yōu)化的示例

2.2 將問題轉(zhuǎn)換到雙邊空間

求解上述的最小化的問題非常復(fù)雜，于是我們沿用上一次講到的思想，將問題轉(zhuǎn)換到雙邊空間中去求解。不過，F(xiàn)BS和Fast Bilateral Stereo算法在雙邊空間中的表達(dá)式有關(guān)鍵的區(qū)別：

在雙邊空間中比較FBS及Fast Bilateral-Space算法 可以看到，F(xiàn)BS在雙邊空間中的求解非常簡(jiǎn)單，直接求解一個(gè)線性等式Ay=b即可，這是因?yàn)镕BS不再需要承擔(dān)做立體匹配的職責(zé)，它只需要保證優(yōu)化后的視差圖滿足雙邊平滑以及與初始視差圖盡可能相似即可。 當(dāng)在雙邊空間中求得了y，接下來就再用下面的公式把結(jié)果轉(zhuǎn)換為像素空間，就可以得到像素空間中的優(yōu)化后的視差圖了：

看起來是不是很簡(jiǎn)單？所以上面公式中最關(guān)鍵的就是要找出公式(6)中A和b及c的表達(dá)式，作者論文中已經(jīng)給出：

下面我們?cè)俳忉屢幌律厦鎺讉€(gè)公式中的各個(gè)變量：

公式變量解釋 當(dāng)構(gòu)造了上面提到的Ay = b這樣的等式之后，作者采用了一種叫做preconditioned conjugate gradient (PCG)的算法（帶先驗(yàn)條件的共軛梯度算法)來優(yōu)化它，并且在這個(gè)過程中還采用了級(jí)聯(lián)金字塔的思想。這個(gè)過程略去不表，咱們只需要知道，采用了這種方式之后，整個(gè)問題的構(gòu)建和優(yōu)化速度都比之前介紹的Fast Bilateral Stereo大大加快了：

FBS的優(yōu)化速度大大提升 在應(yīng)用到對(duì)初始視差圖進(jìn)行優(yōu)化的過程中，作者考慮到FBS的輸出結(jié)果對(duì)于給定的置信度圖和初始視差圖比較敏感，還采用了一種迭代式的求解形式， 這個(gè)過程中的公式推導(dǎo)比較復(fù)雜，限于篇幅所限，這里我就略過了推導(dǎo)的過程。但作者給出了粗糙版的Python實(shí)現(xiàn)，在OpenCV里面也有相應(yīng)的實(shí)現(xiàn)。我會(huì)在我的知識(shí)星球中，針對(duì)這兩份代碼做進(jìn)一步的解釋說明。

三. FBS的應(yīng)用效果

讓我先展示一些作者論文中的FBS的效果吧。首先我們看看一個(gè)當(dāng)時(shí)最優(yōu)秀的立體匹配算法MC-CNN的結(jié)果，這是第一代基于深度學(xué)習(xí)的立體匹配算法。下面是Middle Burry立體匹配數(shù)據(jù)集中的一幅圖，從下圖中看來，它在很多邊緣細(xì)節(jié)上還是出現(xiàn)了錯(cuò)誤和瑕疵：

MC-CNN算法結(jié)果 現(xiàn)在來看看經(jīng)過FBS處理優(yōu)化后的結(jié)果，我們看到從視覺上視差圖結(jié)果明顯好了一個(gè)檔次，MAE和RMSE也有所降低，雖然bad 1%這個(gè)指標(biāo)略有上漲。

用FBS優(yōu)化MC-CNN算法結(jié)果大大減少了錯(cuò)誤 下面是另外一張，很明顯MC-CNN出現(xiàn)了很多瑕疵，尤其是近距離處出現(xiàn)很多匹配錯(cuò)誤

下面是經(jīng)過FBS優(yōu)化后的結(jié)果，很明顯視覺效果好了不少，MAE和RMSE也少了很多！

用FBS優(yōu)化MC-CNN算法結(jié)果大大減少了錯(cuò)誤

四. 可導(dǎo)性與深度學(xué)習(xí)

作者還花了不少篇幅來講解將FBS作為一個(gè)“層”應(yīng)用到深度學(xué)習(xí)的過程中，這里我也提一提吧。以語義分割為例，我們?cè)O(shè)想中將FBS作為網(wǎng)絡(luò)的一個(gè)層加入到網(wǎng)絡(luò)的輸出部分，如下圖所示，其目的是優(yōu)化網(wǎng)絡(luò)輸出的分割掩模：

現(xiàn)在我們來看看現(xiàn)在比較常見的卷積神經(jīng)網(wǎng)絡(luò)優(yōu)化損失函數(shù)的過程，下面是這個(gè)過程的圖示：

深度學(xué)習(xí)用于優(yōu)化復(fù)雜的目標(biāo)函數(shù) 直接優(yōu)化上述函數(shù)是很困難的，所以實(shí)際中一般會(huì)采用小批量隨機(jī)梯度下降法來求解

梯度下降法要求損失函數(shù)可導(dǎo) 所以這里很關(guān)鍵的就是損失函數(shù)要能夠?qū)Ω鱾€(gè)待優(yōu)化參數(shù)求偏導(dǎo)數(shù)，要在反向傳播的過程中可導(dǎo)。如果我們把FBS作為網(wǎng)絡(luò)的一個(gè)層，應(yīng)用到網(wǎng)絡(luò)構(gòu)建的過程中，也會(huì)要求它可導(dǎo)。

在反向傳播中要求FBS可導(dǎo) 在FBS之前有很多全局能量?jī)?yōu)化的算法，都很難做到這一點(diǎn)。幸運(yùn)的是，作者證明了FBS是可以用于反向傳播的，我們把FBS看做下面這樣的函數(shù)

那么反向傳播需要求解它對(duì)于輸入的兩幅圖像的偏導(dǎo)數(shù)：

作者在論文中給出了兩個(gè)偏導(dǎo)數(shù)的公式：

作者給了一個(gè)例子，來說明引入了FBS到網(wǎng)絡(luò)中的好處，首先是用Deeplab進(jìn)行分割后的粗糙結(jié)果：

Deeplab語義分割結(jié)果 現(xiàn)在引入一個(gè)復(fù)雜的后處理算法DenseCRF, 可以得到下面的結(jié)果

DenseCRF優(yōu)化Deep Lab算法結(jié)果的展示 如果我們將DenseCRF替換為FBS加入到網(wǎng)絡(luò)中，可以看到效果相似，但速度是11倍快！

FBS優(yōu)化Deep Lab算法結(jié)果的展示

五. 總結(jié)

今天我為你介紹了Jon Barron的經(jīng)典算法Fast Bilateral Solver，可以說這是我最喜歡的算法之一。其中包含了很多深邃的思想。 首先是對(duì)很多問題中輸出圖像特性的敏銳觀察，并把這種觀察表達(dá)為了優(yōu)美的數(shù)學(xué)公式。這種思想，和我之前在文章50. 從暗通道先驗(yàn)去霧到海底圖像修復(fù)-三維重建輔助計(jì)算攝影中介紹的何凱明的“利用暗通道先驗(yàn)去霧”有異曲同工之妙。

輸出圖像的兩大特性 然后是作者將上述復(fù)雜的公式，轉(zhuǎn)換到了雙邊空間中，降低問題規(guī)模，用于快速求解，而在今天所說的FBS算法中，作者又將這種思想進(jìn)行了更深層次的應(yīng)用。

問題轉(zhuǎn)換求解空間 在求解問題的過程中，作者又高效的利用了級(jí)聯(lián)金字塔形式，并采用了一種特殊的共軛梯度法來求解，使得求解過程大大加速，并得到了更好的效果。講到這里不得不說作者的數(shù)學(xué)功底超級(jí)扎實(shí)，如果你看原文及作者的論文附件，一定會(huì)對(duì)文章中問題建立和問題優(yōu)化的細(xì)致分析過程擊節(jié)而嘆！當(dāng)然，讀懂這些分析過程還是很燒腦的，所以我準(zhǔn)備在我的知識(shí)星球中仔細(xì)的對(duì)應(yīng)著作者的代碼進(jìn)行分析和注解，感興趣的朋友可以加我“計(jì)算攝影學(xué)”公眾號(hào)，進(jìn)而了解星球的加入方法。 還有一點(diǎn)值得提的是, FBS在傳統(tǒng)算法和深度學(xué)習(xí)算法中都可應(yīng)用，可以說是連接過去和現(xiàn)在的橋梁，所以后面很多人寫文章來描述如何將Fast Bilateral Solver的思想應(yīng)用到深度學(xué)習(xí)算法中，感興趣的話你可以搜索一下。

反向傳播示例 不過，F(xiàn)BS也并非沒有缺陷。它最大的問題也就在于雙邊平滑權(quán)重是與輸入?yún)⒖紙D像高度相關(guān)上——這使得其最終效果很容易受到輸入?yún)⒖紙D像的影響，很容易在結(jié)果中引入輸入?yún)⒖紙D像本身的紋理。下圖中左下角是SGBM的結(jié)果，右下角是FBS處理后的結(jié)果。我們可以看到頭發(fā)部分的視差圖很明顯引入了原圖中美女頭發(fā)部分的紋理特征，這并非我們想要的結(jié)果。處理這樣的問題，需要我們?cè)趹?yīng)用FBS的過程中，仔細(xì)的調(diào)整各個(gè)參數(shù)和輸入的置信度圖，并且選擇性的應(yīng)用FBS在部分區(qū)域上，而不是一股腦用于全圖的所有像素上。

FBS容易引入?yún)⒖紙D像的紋理信息 總的來說，F(xiàn)BS是一種非常經(jīng)典和優(yōu)秀的通用圖像處理算法，當(dāng)它應(yīng)用到立體匹配的視差后處理時(shí)，能夠起到“化腐朽為神奇”的功效，非常值得學(xué)習(xí)！現(xiàn)在看看我們的進(jìn)度吧，我們終于完成了經(jīng)典視差優(yōu)化算法的學(xué)習(xí)，即將邁入立體匹配的現(xiàn)代算法——基于深度學(xué)習(xí)的立體匹配算法部分，驚不驚喜，期不期待 就讓我們拭目以待吧！

我們當(dāng)前的進(jìn)度

審核編輯 ：李倩