一. ADCensus背景介紹

到目前為止，我通過(guò)解讀Stefano Mattoccia教授的經(jīng)典講義，介紹了立體匹配算法的全貌。然后介紹了幾個(gè)經(jīng)典的立體匹配算法的評(píng)價(jià)指標(biāo)和數(shù)據(jù)集。下一步我將介紹經(jīng)典的立體匹配算法，并展示它們?cè)趯?shí)際中的應(yīng)用。 先來(lái)看看你現(xiàn)在讀到哪里了吧：

經(jīng)典立體匹配算法局部法和全局法的總體流程，如下圖所示：

事實(shí)上，有一些算法的流程比較混合——比如今天我將介紹的一個(gè)經(jīng)典立體匹配算法，它總體來(lái)說(shuō)是局部法的流程，但其中也有少量模塊在進(jìn)行視差優(yōu)化的過(guò)程。 這個(gè)方法很多人簡(jiǎn)稱為ADCensus，是三星先進(jìn)技術(shù)研究院中國(guó)實(shí)驗(yàn)室以及中科院自動(dòng)化所的一群學(xué)者的成果，文章發(fā)表于2011年：

我用下圖總結(jié)這篇文章的完整流程，我們可以利用Stefano Mattoccia教授給出的流程來(lái)對(duì)比理解ADCensus。

這個(gè)算法我個(gè)人非常喜歡，因?yàn)樗牧鞒谭浅Ｒ?guī)范，而且易于理解。簡(jiǎn)直就像學(xué)習(xí)了Stefano Mattoccia教授的講義后，將各個(gè)標(biāo)準(zhǔn)組件用當(dāng)時(shí)各種優(yōu)秀的算法實(shí)現(xiàn)并串聯(lián)起來(lái)的作品，可以說(shuō)上面圖中每一個(gè)組件都有當(dāng)時(shí)已經(jīng)發(fā)表的論文做基礎(chǔ)。但作者也并非簡(jiǎn)單的搞了一個(gè)縫合怪出來(lái)， 而是把許多組件都做了創(chuàng)造性的優(yōu)化。比如把AD和Census兩種特征融合在一起計(jì)算代價(jià)，并優(yōu)化了基于十字架的代價(jià)聚合算法，同時(shí)組合使用了一系列的視差優(yōu)化的后處理算法。而且，作者還在文章中描述了算法的CUDA實(shí)現(xiàn)，使得這個(gè)算法可以高效的在硬件上運(yùn)行。 每一年計(jì)算機(jī)視覺(jué)領(lǐng)域都有大量的研究成果，但其中能夠?qū)嵱没恼娴牟欢?，而ADCensus就是其中之一。據(jù)我了解，很多硬件實(shí)現(xiàn)的立體匹配算法受到了ADCensus的啟發(fā)。比如OAK相機(jī)，這是一個(gè)由OpenCV基金會(huì)發(fā)起的成功的眾籌產(chǎn)品，可以實(shí)時(shí)計(jì)算深度圖，完成一系列復(fù)雜的功能。

它們推出了多款產(chǎn)品，我手上有下面這一款：

這個(gè)相機(jī)內(nèi)部集成的立體匹配算法，就是基于ADCensus的思想實(shí)現(xiàn)的，我們可以在這里查到相應(yīng)的介紹，如下圖所示，當(dāng)然這里為了效率在原始的算法上做了必要的裁剪和調(diào)整。

另外，Intel公司的著名產(chǎn)品Intel Realsense D400后的系列RGBD相機(jī)也借鑒了本文作者提出的立體匹配算法，特別是其中代價(jià)計(jì)算部分，在Census特征基礎(chǔ)上疊加AD這樣的特征，就是從ADCensus方法中借鑒的方法。 如果你查看2017年CVPR的下面這篇關(guān)于Intel RealSense的論文，你會(huì)看到對(duì)此的清晰描述

總之，一群中國(guó)學(xué)者，在2011年左右搞出了一種非常實(shí)用化的立體匹配算法，在很多領(lǐng)域都得到了應(yīng)用，非常值得欽佩！

二. 效果展示

我在github上找到了一個(gè)比較原汁原味的算法實(shí)現(xiàn)：https://github.com/DLuensch/StereoVision-ADCensus，我們來(lái)看看效果吧。 先來(lái)看兩對(duì)MiddleBurry中的經(jīng)典圖像，左上和左下是校正后的圖像，右邊是算法默認(rèn)參數(shù)生成的視差圖，看起來(lái)還不錯(cuò)：

再看看這把椅子吧，看起來(lái)對(duì)這種復(fù)雜的場(chǎng)景稍微差點(diǎn)意思，需要仔細(xì)的調(diào)優(yōu)參數(shù)才行（我?guī)缀跤玫氖悄J(rèn)參數(shù)）：

來(lái)試試摩托車，盡管還遺留了一些空洞，整個(gè)畫(huà)面的深度圖還是被正確恢復(fù)出來(lái)了，總的來(lái)說(shuō)，效果還是令人滿意的

再看看在MPI Sintel數(shù)據(jù)集上的效果，這個(gè)數(shù)據(jù)集的具體介紹請(qǐng)見(jiàn)76. 三維重建11-立體匹配7，解析合成數(shù)據(jù)集和工具，可以看到前景效果總體來(lái)說(shuō)不錯(cuò)，背景似乎都為0，看起來(lái)是因?yàn)樘h(yuǎn)了的原因？

然后我們請(qǐng)出我的御用模特Sunny妹來(lái)試試，看起來(lái)默認(rèn)參數(shù)在這種場(chǎng)景下有很多錯(cuò)誤，需要仔細(xì)調(diào)參才能得到更好的結(jié)果。我們待會(huì)會(huì)仔細(xì)分析下ADCensu算法的各個(gè)步驟和相關(guān)參數(shù)：

三. 原理簡(jiǎn)介

3.1 代價(jià)計(jì)算

立體匹配算法總體理解中說(shuō)過(guò)代價(jià)計(jì)算的過(guò)程類似于連連看的過(guò)程：

最簡(jiǎn)單的代價(jià)就是左右圖中相應(yīng)像素的亮度絕對(duì)差，這種代價(jià)被稱為AD：

然而，這種代價(jià)在圖像中的平坦區(qū)域（亮度值都差不多）很顯然會(huì)得到錯(cuò)誤的結(jié)果。此時(shí)顯然應(yīng)該使用別的特征來(lái)計(jì)算代價(jià)。Cencus就是一種很好的特征，它衡量了局部區(qū)域中像素亮度的排序，這是一種結(jié)構(gòu)信息。這就使得它很好的避免了左右圖像素亮度差異、噪聲、重復(fù)紋理等因素帶來(lái)的錯(cuò)誤。 不過(guò)，僅使用Census特征的話，在圖像中重復(fù)結(jié)構(gòu)的區(qū)域，也會(huì)得到錯(cuò)誤的結(jié)果。這時(shí)候顏色或亮度特征則可以加以輔助。所以ADCensus的作者創(chuàng)造了一種很不錯(cuò)的融合亮度差異和結(jié)構(gòu)差異的方法，如下面公式所述。這里前一部分是基于Census的代價(jià)，后一部分是AD代價(jià)，所以這個(gè)算法才被很多人稱為ADCensus：

這里面，為了讓兩部分代價(jià)歸一化到[0,1]之間，作者采用了下面這個(gè)歸一化函數(shù)，它能很方便的將輸入的原始代價(jià)轉(zhuǎn)換為[0,1]之間的值，而這里的λ則用于設(shè)置代價(jià)的權(quán)重：

我們通過(guò)作者給出的下圖可以很容易的看到混合兩種代價(jià)帶來(lái)的好處：

這時(shí)候，直接利用AD-Census計(jì)算固定窗口的代價(jià)，然后用WTA得到視差圖，如下圖所示。我們可以看到這里有大量的噪聲和空洞區(qū)域。這是很容易理解的，所以才需要下一節(jié)所述的代價(jià)聚合過(guò)程：

3.2 代價(jià)聚合

ADCensus所用的代價(jià)聚合方法很有意思。在我的文章71. 三維重建6-立體匹配2，立體匹配中的代價(jià)聚合中，我提到了代價(jià)聚合的假設(shè)：

空間上接近的像素，其視差值也是接近的，于是代價(jià)值也是接近的

像素值接近的像素，其視差值也是接近的，于是代價(jià)值也是接近的

左右兩張圖的相鄰像素，在關(guān)鍵信息上具有局部相似性

我們還看到了各種各樣的聚合方式，有一類方式就是用可變形狀的支持窗來(lái)進(jìn)行聚合的——ADCensus的方法就屬于這種。當(dāng)要確定某個(gè)像素點(diǎn)p的支持窗時(shí)，它是通過(guò)尋找上下左右四個(gè)"臂"，在這四個(gè)臂的包裹下構(gòu)成了其支持窗。確切說(shuō)，首先找到p的上下臂，也就是在空間和像素值兩個(gè)維度上都盡可能接近p的兩端像素。這樣就構(gòu)成了一個(gè)包含在p內(nèi)的垂直的像素線段。在這條線段上的任何一個(gè)點(diǎn)q，我們都確定其左右臂，得到水平的遠(yuǎn)端像素。這樣，所有q點(diǎn)的左右臂的遠(yuǎn)端像素就形成了一個(gè)包絡(luò)，其中就是p點(diǎn)的支持窗。

有了支持窗后，就比較容易聚合了，先在水平方向聚合，將水平方向的代價(jià)值加到一起。然后在垂直方向聚合，得到總的代價(jià)：

事實(shí)上，ADCensus中為了讓結(jié)果更好，進(jìn)行了4次交替方向的聚合。即先水平再垂直，這是第1次。第二次相反，先垂直，再水平。然后再進(jìn)行2次交替的聚合。最終四次的代價(jià)整合到一起，成為最后聚合后的代價(jià)值。 那么，如何得到上面所說(shuō)的p點(diǎn)的四個(gè)臂呢？這似乎是得到支持窗的關(guān)鍵。我們以獲得p的左臂為例來(lái)說(shuō)明:

所以很顯然，這里面的幾個(gè)參數(shù)L1, L2等參數(shù)τ2 都很重要?？傊?，通過(guò)這一步代價(jià)聚合后，我們能夠得到更加平滑的視差圖，如下圖所示：

3.3 掃描線優(yōu)化

在文章72. 三維重建7-立體匹配3，立體匹配算法中的視差優(yōu)化中，我們看到了一種掃描線優(yōu)化的方法。ADCensus也采用了這種方法，通過(guò)聚合后的代價(jià)優(yōu)化得到視差圖。在這篇文章中我已經(jīng)詳細(xì)闡述了方法，這里只說(shuō)說(shuō)不同之處。在原始的掃描線優(yōu)化方法中，一共是8個(gè)方向。而ADCensus為了提高計(jì)算速度，只采用了其中的0、1、2、3這幾個(gè)水平和垂直的掃描線：

通過(guò)這一步，能得到更加準(zhǔn)確的視差圖，如下圖所示。相比上面代價(jià)聚合后的結(jié)果，這里明顯噪聲小了很多:

3.4 視差后處理

接下來(lái)就是視差后處理了，這里是我覺(jué)得這個(gè)算法的可圈可點(diǎn)之處。作者幾乎把我在73. 三維重建8-立體匹配4，利用視差后處理完善結(jié)果中提到的視差后處理方法都用上了，形成了一個(gè)復(fù)雜的管線，如下圖所示。我會(huì)在后面對(duì)這種方式進(jìn)行評(píng)價(jià)，但讓我們先跟著作者的脈絡(luò)往下學(xué)習(xí)吧。

3.4.1 錯(cuò)誤檢測(cè)和區(qū)分

首先需要通過(guò)左右一致性檢查判斷哪些像素是錯(cuò)誤的：

然后，通過(guò)一個(gè)簡(jiǎn)單的法則來(lái)區(qū)分到底是因?yàn)檎趽鯇?dǎo)致的錯(cuò)誤，還是因?yàn)殄e(cuò)誤匹配導(dǎo)致的錯(cuò)誤。遮擋像素?zé)o論調(diào)整d為多少，都無(wú)法通過(guò)左右一致性檢測(cè)。而錯(cuò)誤匹配則可以通過(guò)調(diào)整d，得到滿足左右一致性檢查的新視差值。

接下來(lái)，就可以分別對(duì)遮擋和錯(cuò)誤匹配進(jìn)行處理了。

3.4.2 區(qū)域投票

首先進(jìn)行區(qū)域投票。在錯(cuò)誤像素點(diǎn)p的支持窗內(nèi)，對(duì)所有正確計(jì)算視差的像素(即通過(guò)了左右一致性檢測(cè))的視差值建立一個(gè)直方圖。如果這個(gè)支持窗中穩(wěn)定視差值足夠多，并且直方圖中占比最大的視差值的占比大于某個(gè)閾值，我們就把p點(diǎn)的視差值更新為最大占比的視差值：

這里面，Sp代表支持窗中正確視差值的個(gè)數(shù)，Hp(d*p)代表直方圖中占比最大的視差值的數(shù)量

3.4.3 分情況插值

前面我們區(qū)分了遮擋像素和錯(cuò)誤匹配的像素，現(xiàn)在分情況進(jìn)行插值。

首先對(duì)于錯(cuò)誤像素，我們尋找16個(gè)方向上的最相似的正確匹配的像素。

接下來(lái)，如果當(dāng)前像素在3.4.1節(jié)中被劃分為了遮擋像素，那么就從這些正確像素中挑選最小的視差，用于填充當(dāng)前像素的視差值，也就是說(shuō)假設(shè)遮擋像素屬于背景。

而如果當(dāng)前像素是錯(cuò)誤匹配的像素，那么就從這些正確點(diǎn)中挑選與當(dāng)前像素顏色維度最相似的那一個(gè)，用其視差填充當(dāng)前像素。

現(xiàn)在再來(lái)看看結(jié)果，很明顯大量的錯(cuò)誤像素被成功插值了。不過(guò)也可以看到，部分遮擋像素還是未填充視差值，這是因?yàn)樵谄?6個(gè)方向都找不到滿足條件的正確像素，這里主要是因?yàn)橛?個(gè)參數(shù)限制了在一個(gè)方向上的最大搜索像素。如果增加這個(gè)參數(shù)的值，應(yīng)該可以使得更多的像素得到填充。

3.4.4 修正邊緣處的視差值

考慮到物體邊緣的視差值不穩(wěn)定，容易出錯(cuò)，因此作者還加入了一個(gè)步驟，對(duì)邊緣處的視差值進(jìn)行微調(diào)。具體來(lái)說(shuō)，先檢測(cè)到所有的邊緣，接著對(duì)邊緣上的像素p，我們判斷其在邊緣兩側(cè)的兩個(gè)相鄰像素p1或p2的代價(jià)是否小于p點(diǎn)的代價(jià)。如果確實(shí)如此，那么就用p1和p2中代價(jià)最小的那個(gè)像素的視差值來(lái)替換p點(diǎn)的視差值。 不過(guò)對(duì)于當(dāng)前這對(duì)圖像，似乎邊緣調(diào)整帶來(lái)的變化很小，肉眼幾乎分不出來(lái)。當(dāng)然，這是可以理解的，因?yàn)檫@只是“微調(diào)”

3.4.5 亞像素增強(qiáng)和濾波

調(diào)整完邊緣后，作者采用了我在文章73. 三維重建8-立體匹配4，利用視差后處理完善結(jié)果中提到的亞像素增強(qiáng)，將整數(shù)型的視差值插值為了浮點(diǎn)數(shù)型的視差值

然后，對(duì)最后的視差圖做了1個(gè)3x3的中值濾波，去除微小的噪聲，這就得到了最終的視差圖：

我把整個(gè)過(guò)程做成一個(gè)視頻，可以看得更清楚些：

四. 算法討論

正如我在文章開(kāi)篇所說(shuō)，我挺喜歡ADCensus這個(gè)算法的。因?yàn)樗怯梢粋€(gè)又一個(gè)非常容易理解的子部件組合而成的。這種結(jié)構(gòu)也使得實(shí)現(xiàn)起來(lái)很容易，而且還可以根據(jù)工程需要?jiǎng)h除或者替換其中的子部件。 比如，在文章開(kāi)篇我們看到的OAK Camera的流程，通過(guò)官方的流程圖可以看出跟原版ADCensus很相似，用了Census特征，掃描線優(yōu)化，左右一致性檢測(cè)后的插值，還增加了更多的濾波器。似乎裁減掉了區(qū)域投票、邊緣調(diào)整等步驟：

從效果上看，OAK Camera僅通過(guò)單通道的雙目圖像，就已經(jīng)能實(shí)時(shí)得到不錯(cuò)的結(jié)果，這進(jìn)一步證明了類ADCensus算法的有效性：

而且，作者還專門(mén)闡釋了在硬件上優(yōu)化實(shí)現(xiàn)的方案，包括代價(jià)計(jì)算，代價(jià)聚合，掃描線優(yōu)化等在內(nèi)的步驟都可以用硬件來(lái)并行計(jì)算。在作者的論文中，通過(guò)硬件加速，算法執(zhí)行速度提升了最高140倍！OAK Camera應(yīng)該也是借鑒了其中的思想，所以能實(shí)時(shí)計(jì)算得到視差圖。 然而，硬幣總有兩面，由多個(gè)子部件來(lái)構(gòu)成一個(gè)完整的算法管線，也會(huì)帶來(lái)新的問(wèn)題。由于每個(gè)部件都有自己的參數(shù)，這就導(dǎo)致要將算法調(diào)整到最佳狀態(tài)非常困難，因?yàn)閰?shù)數(shù)量太多了，而且各個(gè)部件之間有強(qiáng)相關(guān)關(guān)系，調(diào)整前一個(gè)步驟的參數(shù)，可能會(huì)影響到后一個(gè)步驟，這就使得調(diào)整參數(shù)更加復(fù)雜。而且，在不同的數(shù)據(jù)集上，參數(shù)的值顯然不相同，所以導(dǎo)致這個(gè)算法的泛化性很成問(wèn)題。 前面的開(kāi)源實(shí)現(xiàn)https://github.com/DLuensch/StereoVision-ADCensus， 里面，就定義了眾多參數(shù)：

前面我們Sunny妹的圖片，采用MiddleBurry數(shù)據(jù)集上調(diào)出的默認(rèn)參數(shù)時(shí)就存在很多區(qū)域的錯(cuò)誤。很顯然，此時(shí)應(yīng)該在這種場(chǎng)景下對(duì)參數(shù)進(jìn)行精調(diào)才行。

比如在OAK-Camera上調(diào)整參數(shù)后，可以得到這個(gè)結(jié)果，明顯的錯(cuò)誤像素少了許多：

用多個(gè)子部件組成算法管線，還存在性能優(yōu)化的問(wèn)題。因?yàn)槟悴坏貌粌?yōu)化每一個(gè)部件的性能，才能得到一個(gè)高性能的算法——這對(duì)立體匹配通常非常重要。

五. 總結(jié)

今天，我為你介紹了一個(gè)經(jīng)典的立體匹配算法ADCensus，其流程非常規(guī)整。它很容易理解，很容易實(shí)現(xiàn)，并且被許多知名的硬件設(shè)備所借鑒，比如OpenCV官方推出的OAK Camera，以及Intel Realsense。 它的作者是一群中國(guó)學(xué)者，嗯，好感度++ 它遵循的范式是用一堆容易理解的子模塊構(gòu)成整個(gè)算法，似乎咱普通人也能想得到這種思想：

ADCensus算法也有自己的缺點(diǎn)：參數(shù)眾多、難以調(diào)整、泛化性不夠高。模塊眾多，優(yōu)化復(fù)雜，很吃經(jīng)驗(yàn)。 那么，有沒(méi)有更好的方式呢？這也是我后面的文章中會(huì)講述的，讓我們拭目以待吧。

六. 參考資料

1.X. Mei etc.，On building an accurate stereo matching system on graphics hardware2.OAK-Camera：https://store.opencv.ai/products/oak-d3.Leonid Keselman etc.Intel RealSense Stereoscopic Depth Cameras4.開(kāi)源實(shí)現(xiàn)：https://github.com/DLuensch/StereoVision-ADCensus

審核編輯 ：李倩