基于擴(kuò)展雙權(quán)重聚合的實(shí)時(shí)立體匹配

茆 看，靜大海

（河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 211110）

基于擴(kuò)展雙權(quán)重聚合的實(shí)時(shí)立體匹配

茆 看，靜大海

（河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 211110）

基于在保證實(shí)時(shí)性的前提下提高匹配精確度的目的，本文采用了一種基于擴(kuò)展雙權(quán)重聚合的實(shí)時(shí)立體匹配方法。擴(kuò)展雙權(quán)重聚合是基于以下2個(gè)新的想法。第一，擴(kuò)展雙權(quán)重聚合越過顏色邊界連接相似區(qū)域，對(duì)于一個(gè)給定的像素給予一個(gè)很大的支持區(qū)域。第二，它不包括支持區(qū)域中的預(yù)估異常值，從而制作一個(gè)高質(zhì)量的支持區(qū)域。通過實(shí)驗(yàn)將擴(kuò)展雙權(quán)重聚合的實(shí)時(shí)立體匹配方法和其他實(shí)時(shí)立體匹配方法的精確性相比較。實(shí)驗(yàn)結(jié)果表明，所提出的立體匹配方法顯示了一個(gè)平均5.10%的壞像素率，是這些實(shí)時(shí)立體匹配方法中精確度最高的。

立體匹配；雙權(quán)重聚合；遠(yuǎn)程連接聚合；異常排除聚合

立體匹配是對(duì)給定的一對(duì)立體圖像計(jì)算視差圖的過程。目前許多立體匹配的應(yīng)用程序需要實(shí)時(shí)處理，但事實(shí)上立體匹配需要經(jīng)歷大規(guī)模的計(jì)算。幸運(yùn)的是，無論硬件還是軟件方面并行處理技術(shù)已經(jīng)非常先進(jìn)。因此，在最近幾年實(shí)時(shí)立體匹配的方法被廣泛研究。

立體匹配可以分為兩種類型[1]：全局和局部方法。全局方法[2-3]通過一個(gè)能量函數(shù)來表示需要解決的立體匹配問題，然后通過使能量函數(shù)最小化來找到最優(yōu)的解決方案[4]。局部方法[5-6]計(jì)算每個(gè)像素的異同，然后確定每個(gè)像素的最優(yōu)視差。局部方法本質(zhì)上是容易計(jì)算和適當(dāng)并行化的。因此，大多數(shù)最近的實(shí)時(shí)立體匹配的方法都采用的是局部方法。一般情況下，局部立體匹配方法包括以下4個(gè)步驟[7]：代價(jià)計(jì)算，代價(jià)聚合，視差計(jì)算，視差精化。

文中，提出了一種高精度的實(shí)時(shí)立體匹配方法。為了實(shí)現(xiàn)該方法，采用了容易計(jì)算的雙權(quán)重，聚合步驟中刪除現(xiàn)有雙權(quán)重方法的連通性約束。然而在現(xiàn)有的雙權(quán)重方法中所有雙權(quán)重應(yīng)都需要與中心像素相關(guān)聯(lián)。該方法會(huì)導(dǎo)致聚合變得復(fù)雜但擁有高精度性。

1 傳統(tǒng)聚合方法

聚合步驟對(duì)局部立體匹配方法的性能的精度和運(yùn)算速度方面有顯著影響。根據(jù)權(quán)重類型，將聚合方法分為2類：雙權(quán)重聚合和真值權(quán)重聚合。雖然雙權(quán)重聚合一般精度不高，但它的計(jì)算復(fù)雜度較低。相反的，高精度的實(shí)時(shí)值權(quán)重聚合也有較高計(jì)算復(fù)雜度。

1.1 雙權(quán)重聚合

最初，在聚合步驟中使用一個(gè)固定大小的正方形窗口，使窗口中的所有代價(jià)平均。然而，隨著窗口大小的增加邊緣區(qū)域變得更加模糊，隨著窗口尺寸減小平滑區(qū)域的錯(cuò)誤隨之增加。

為了克服一個(gè)固定大小的窗口帶來的缺點(diǎn)，提出可變窗口和多窗口。一個(gè)可變窗口分配一個(gè)正方形窗口尺寸能夠自適應(yīng)每個(gè)像素的代價(jià)函數(shù)和方差。多窗口方法將一個(gè)固定大小的窗口分為子窗口，然后選擇一些子窗口作為支持區(qū)域，即這些像素將被聚合。

為了克服矩形支持區(qū)域這一局限性，提出了更加靈活的多邊形區(qū)域。從中心像素向四向量或八向量的每個(gè)方向上的移動(dòng)，直到遇到一個(gè)與中心像素顏色差異很大的像素。多邊形支持區(qū)域是通過連接的所有頂點(diǎn)而生成的。

最近提出的雙權(quán)重聚合使用一個(gè)基于交叉的支持區(qū)域，由其分配像素單元的雙權(quán)重[8]。用“基于交叉”這個(gè)詞是因?yàn)槊總€(gè)像素都有一個(gè)十字形元素。為了生成每個(gè)像素的元素，沿著4個(gè)方向擴(kuò)展直到遇到一個(gè)顏色差異很大的像素作為中心像素。支持區(qū)域是通過收集水平穿過垂直交叉的中心像素從而動(dòng)態(tài)合成的，如圖1所示。這樣使得分配雙權(quán)重的形狀更適合于每個(gè)像素，從而增加精確度。

圖1 基于交叉支持區(qū)域的示意圖

現(xiàn)有的雙權(quán)重聚合都有連通性約束，因?yàn)樵跈?quán)重分配時(shí)，所有像素應(yīng)與中心像素相關(guān)聯(lián)。這個(gè)約束是能夠快速運(yùn)算速度的關(guān)鍵原因。然而，連通性約束也是精度較差的原因之一。由于連通性約束，有很多不屬于聚合目標(biāo)的像素。

1.2 實(shí)值權(quán)重聚合

一種自適應(yīng)權(quán)重算法[9-10]根據(jù)比較中心像素的色差和空間距離給支持窗口中所有像素分配權(quán)重。自適應(yīng)權(quán)重算法的基本假設(shè)是，與中心像素比只有較小的顏色和空間距離的像素視為與中心像素有相同的差距。自適應(yīng)權(quán)重算法的準(zhǔn)確性有很大的改善，但需要大量的計(jì)算。

許多各樣的自適應(yīng)權(quán)重算法需要考慮有效的計(jì)算方法?？焖匐p邊立體（FBS）通過為每個(gè)子窗口設(shè)置統(tǒng)一的重量降低了計(jì)算復(fù)雜度，從O（W2）降低到O（W2/），W是一個(gè)聚集窗口的大小。雙通聚合[11]是利用水平聚集隨后垂直聚集，同時(shí)代替二維聚合。可以將聚合的計(jì)算復(fù)雜度降低到O（W）。此外，指數(shù)逐步自適應(yīng)權(quán)重（ESAW）將目標(biāo)的數(shù)量呈指數(shù)增加的代價(jià)分層結(jié)合，從而降低計(jì)算復(fù)雜度到O(logW)[12]。然而，F(xiàn)BS，雙通聚合，ESAW都帶來不可避免的降低了它們的近似精度。真值權(quán)重聚合通常比雙權(quán)重聚合更準(zhǔn)確，因?yàn)檎嬷禉?quán)重聚合是不受連通性約束的。

2 基于擴(kuò)展雙權(quán)重聚合的立體匹配方法

所提出的方法包括以下4個(gè)步驟：代價(jià)計(jì)算，代價(jià)聚合，視差計(jì)算，視差精化。整體框圖如圖2所示。所提出的方法的主要改進(jìn)點(diǎn)是它的聚合步驟，聚合步驟在精度和計(jì)算復(fù)雜度起著重要作用。

圖2 該立體匹配方法的整體框圖

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

SAD和HD是兩個(gè)被廣泛使用的用來構(gòu)建綜合代價(jià)。將SAD和HD合并使用比分開單獨(dú)使用它們效果更好[13]。然而，在結(jié)合兩者之前，它們應(yīng)該被截?cái)嘁员苊獯鷥r(jià)過大忽略掉聚合步驟的其他代價(jià)。此外，異常檢測(cè)，聚合步驟中最重要的一個(gè)方面，取決于代價(jià)比例。因此，兩者的代價(jià)應(yīng)該被截?cái)啵顾鼈儺a(chǎn)生的影響有限。最后，綜合代價(jià)為兩個(gè)代價(jià)的截?cái)嗫偤停?/p>

τSAD和τHD分別代表SAD和HD的截?cái)嘀甸撝担聵?biāo)init表示初始代價(jià)，用來區(qū)分它和聚合代價(jià)。

2.2 代價(jià)聚合

代價(jià)聚合步驟結(jié)合像素的代價(jià)，像素代價(jià)期望有相同差值從而提高匹配的精度?，F(xiàn)有的雙權(quán)重聚合都具有連通性約束，因?yàn)樗邢袼氐碾p權(quán)重分配都要與中心像素相聯(lián)系。然而，這種約束是得到一個(gè)準(zhǔn)確視差圖的一個(gè)主要障礙，因?yàn)樗璧K了雙權(quán)重的靈活分配。與現(xiàn)有的雙權(quán)重聚合相比通過移除連通性約束的該聚合方法提供了更高的精度。此擴(kuò)展雙權(quán)重聚合主要有兩種方法：遠(yuǎn)程連接聚合和異常排除聚合。遠(yuǎn)程連接聚合將聚合目標(biāo)擴(kuò)展到顏色邊界的外部，異常排除聚合主要是刪除異常值的雙權(quán)重。使用這些方法可以克服雙權(quán)重聚合相對(duì)較低的精確度，同時(shí)可以保持其快速的運(yùn)算速度。

2.2.1 遠(yuǎn)程連接聚合

雙權(quán)重聚合根據(jù)顏色的相似性和空間約束來確定支持區(qū)域。我們希望同一個(gè)對(duì)象中的像素都能有相似的顏色。然而，在真實(shí)場(chǎng)景中，同一個(gè)對(duì)象中的許多像素顏色區(qū)別較大，盡管人們不能識(shí)別出來。當(dāng)然，這些像素可以通過降低顏色相似的邊界線的閾值來包含進(jìn)支持區(qū)域中，但它可能會(huì)導(dǎo)致過度聚合而產(chǎn)生一個(gè)模糊的視差圖。遠(yuǎn)程連接聚合方法要合理地?cái)U(kuò)展支持區(qū)域，而不是通過放寬的顏色閾值引起過度聚合。

現(xiàn)有的基于交叉的聚合方法中支持區(qū)域設(shè)置為每個(gè)像素的預(yù)定義窗口大小為。如果像素滿足與中心像素顏色相似性和連通性這兩個(gè)條件，雙權(quán)重將分配給每個(gè)像素的4個(gè)方向，aggr_pts定義來表示雙權(quán)重分配像素端點(diǎn)如下：

下標(biāo)E表示正確方向，W是聚合窗口的大小，τcolor是顏色閾值。其他3個(gè)方向aggr_pts計(jì)算方法與它本身方向計(jì)算方式相同。函數(shù)diff定義如下：

為了降低計(jì)算復(fù)雜度，在水平聚集后進(jìn)行垂直聚集，因此，聚合步驟的計(jì)算復(fù)雜度變成O（W）。因?yàn)轭伾吔?，很多顏色相似的像素都不能分配到雙權(quán)重，如圖3（a）。如果它們屬于聚合目標(biāo)，錯(cuò)誤率將會(huì)降低。

遠(yuǎn)程連接聚合設(shè)置雙權(quán)重時(shí)可以越過顏色邊界。如果它們顏色類似中心像素，不管連通性如何雙權(quán)重分配給每個(gè)像素在4個(gè)方向上。要做到這一點(diǎn)，aggr_pts要擴(kuò)展到三維數(shù)據(jù)，定義如下：

aggr_ptE（x，y，1）的定義同（2）式。其他3個(gè)方向aggr_pts計(jì)算方法與它們自己方向計(jì)算方式相同。所提出的方法也是先水平聚集再垂直聚集以保持計(jì)算復(fù)雜度為O（W）。運(yùn)算過程通過圖3（b）以圖形方式描述。當(dāng)比較圖3（a）和圖3（b）時(shí)，很明顯可以看出遠(yuǎn)程連接聚合方法能夠更合理分配更多雙權(quán)重。

圖3 雙權(quán)重分配圖形化描述

黑點(diǎn)顯示的是中心像素，而由黑體線包圍的封閉區(qū)域則是聚集的目標(biāo)像素。

2.2.2 異常排除聚合

一個(gè)視差圖的精確度一般是可以通過聚合步驟來提高，因?yàn)樵谄渚奂繕?biāo)中大多數(shù)的像素都有一個(gè)明顯正確的代價(jià)。然而，一些像素的聚合目標(biāo)組成一個(gè)顯然錯(cuò)誤的代價(jià)，導(dǎo)致一個(gè)不一樣的錯(cuò)誤分配。在所提出的方法中，錯(cuò)誤的代價(jià)在聚合之前就已被排除。

排除異常聚合的關(guān)鍵是異常值檢測(cè)的準(zhǔn)確性。因此，各種異常值檢測(cè)方法都應(yīng)進(jìn)行測(cè)試，以找到一個(gè)理想的異常值檢測(cè)法。在本文中，是通過結(jié)合左右一致性檢測(cè)（LRC）和平均峰值比（APKR）來找出異常值的。

LRC是最廣泛使用的異常值檢測(cè)法。如果某一點(diǎn)在左、右視差圖中的差異不一致，則該點(diǎn)是一個(gè)離群點(diǎn)，如下面所示：

dispL和dispR分別代表左，右視差圖。LRC的基本思想是任意一點(diǎn)的視差都必須是唯一的。

APKR是最近提出的立體置信度，它在發(fā)現(xiàn)異常值上顯示出了最佳性能[14]。它被定義為一個(gè)像素的二次最低代價(jià)和最小代價(jià)的比。APKR不僅考慮原始峰率還要考慮周圍像素代價(jià)分布的一致性，如下所示：

其中d1和d2分別對(duì)應(yīng)中心像素最小代價(jià)和二次最低代價(jià)視差，WAPKR是APKR的參考窗口。值得注意的是，APKR不是簡單的平均峰值比。如果一個(gè)像素的APKR值比預(yù)定閾值低，這個(gè)像素將被視為一個(gè)異常點(diǎn)。

異常值可以被分為兩類，一類是遮擋一類是不匹配。遮擋發(fā)生在由于立體相機(jī)拍攝的不同景象時(shí)背景被前景對(duì)象隱藏時(shí)。不匹配發(fā)生在立體匹配方法出現(xiàn)錯(cuò)誤導(dǎo)致一個(gè)錯(cuò)誤的預(yù)估視差。LRC專門用來找遮擋區(qū)域因?yàn)樗饕米笥乙暡顖D的差異。另一方面，APKR主要是搜索不匹配地區(qū)因?yàn)椴黄ヅ湎袼氐拇鷥r(jià)分配通常與周圍像素不一致。因此，我們盡量結(jié)合LRC和APKR來加強(qiáng)兩項(xiàng)指標(biāo)的強(qiáng)度，如下：

其中τL和τH分別代表閾值。即使LRC確定一個(gè)像素為非離群，當(dāng)APKR值太小時(shí)像素仍可能是異常值，因此，APKR的τL就是用來過濾這種異常值的。

刪除雙權(quán)重的異常值之后雙權(quán)重將稀疏分布。因此很難有效地計(jì)算聚合步驟。但是，利用離群圖和聚合過濾代價(jià)，我們可以很容易通過過濾總代價(jià)的方法解決這個(gè)問題。

2.3 視差計(jì)算

正如前面提到的，代價(jià)與像素之間的相似性成反比。因此，將最小代價(jià)看作是視差是合理。在該方法中，計(jì)算視差采用贏者全勝策略，如下：

2.4 視差精化

視差通過3個(gè)階段進(jìn)行優(yōu)化：異常檢測(cè)，異常校正和中值濾波。異常值檢測(cè)是利用異常排除聚合的相同的標(biāo)準(zhǔn)篩選的；然而，LRC和APKR是在聚合步驟后從聚合代價(jià)中重新計(jì)算的。

對(duì)于一個(gè)異常值的校正，是通過對(duì)每個(gè)異常像素向左右兩個(gè)方向搜索最近的非離群像素點(diǎn)。異常值的視差就被具有更相似的顏色的像素視差替換掉。這是因?yàn)榫哂邢嗨频念伾南袼乜赡苡兄嗤囊暡?。之后，使用垂直中值濾波處理異常值，以消除因異常值校正而產(chǎn)生的水平劃痕類型的錯(cuò)誤。最后，利用平方中值濾波對(duì)整個(gè)視差圖進(jìn)行平滑處理。

3 實(shí)驗(yàn)結(jié)果

通過比較4種不同的情況下，對(duì)兩種方法在精確度方面的影響進(jìn)行了評(píng)價(jià)：方法0：直接連接聚合不用任何方法；方法1：遠(yuǎn)程連接聚合；方法2：異常排除聚合和直接連接聚合；方法3：擴(kuò)展雙權(quán)重聚合（遠(yuǎn)程連接聚合和異常排除聚合兩者相結(jié)合）。后續(xù)處理步驟也在實(shí)驗(yàn)中進(jìn)行。實(shí)驗(yàn)結(jié)果見表1。每種方法都明顯地降低了錯(cuò)誤率。當(dāng)這兩種方法都應(yīng)用時(shí)我們得到了最好的結(jié)果。因?yàn)檫@兩種方法是以一種互補(bǔ)的方式進(jìn)行的。方法1從顏色邊界的外部包含進(jìn)了更多的聚合目標(biāo)，而方法2排除了現(xiàn)有聚合目標(biāo)中的錯(cuò)誤代價(jià)。

表1 各種聚合方法的精度比較

表2顯示了所提出的立體匹配方法和其他實(shí)時(shí)立體匹配方法的精確性。HEBF，RTAdaptWgt，F(xiàn)astBilateral，RealtimeBFV，ESAW and RT-ColorAW[15]被用作檢測(cè)方法。精確度是通過預(yù)估壞像素的平均百分比，它的絕對(duì)視差錯(cuò)誤是大于1的。對(duì)于每一個(gè)圖像，壞像素率是對(duì)無遮擋的（NOCC），全部的（all），和不連續(xù)（disc）區(qū)域進(jìn)行評(píng)估，然后取平均值。

表2 各種聚合方法的精度比較

所提出的方法顯示了一個(gè)平均5.10%個(gè)壞像素率，是這些實(shí)時(shí)立體匹配方法中精確度最高的。設(shè)置，τSAD=30，τHD=40，ω=2，產(chǎn)生初始代價(jià)，采用遠(yuǎn)程連接聚合的顏色閾值為 13，采用結(jié)合LRC和 APKR相結(jié)合的異常排除聚合設(shè)置為，τH=1.35，τL= 1.05。最后，最后一步的中值濾波在3*3大小的窗口中進(jìn)行。圖4中提供了本文結(jié)果與參考圖像和標(biāo)準(zhǔn)視差圖。

圖4 本文結(jié)果與參考圖像和標(biāo)準(zhǔn)視差圖

4 結(jié) 論

在本文中，提出了一個(gè)新的使用擴(kuò)展的雙權(quán)重聚合的實(shí)時(shí)立體匹配方法。它有兩個(gè)主要的方法來實(shí)現(xiàn)高精度：遠(yuǎn)程連接聚合設(shè)置雙權(quán)重越過顏色邊界和異常排除聚合在聚合之前重置異常值的雙權(quán)重。該立體匹配方法克服現(xiàn)有的雙權(quán)重聚合方法的連通性約束，表現(xiàn)出非常精確的結(jié)果，同時(shí)可以通過GPU采用CUDA平臺(tái)實(shí)現(xiàn)，提供快速的運(yùn)行速度。

[1]馬頌德，張友正.計(jì)算機(jī)視覺[M].北京:北京科學(xué)出版社,1998.

[2]Saygili Gorkem,van der Maaten Laurens,Hendriks Emile A.Feature-based stereo matching using graph-cuts[C]//Conference on Asian Society of Cardiovascular Imaging,Hong Kong,2011:14-15.

[3]KlausA,SormannM,KarnerK.Segment-based stereo matching using belief propagation and a selfadapting dissimilarity measure[C]//The 18th International Conference on Pattern Recognition, Hong Kong,2006:15-18.

[4]Sharstein D,Szeliski R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J].International Journal on Computer Vision,2002,47(1-3):7-42.

[5]Yoon K J,Kweon S.Adaptivesupport-weight approach for correspondence search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(4):650-656.

[6]Humenberger M,Zinner C,Weber M,et al.A fast stereo matching algorithm suitable for embedded real-time systems[J].Computer Vision and Image Understanding,2010,114(11):1180-1202.

[7]Einecke N,Eggert J.A two-stage correlation method for stereoscopic depth estimation[C]//International Conference on Digital Image Computing: Techniquesand Applications,Sydney,New South Wales,2010:227-234.

[8]Zhang K,Lu J,Lafruit G.Cross-based local stereo matching using orthogonal integral images[J].IEEE Trans.Circuits Syst.Video Technol，2009，19（7）:1073-1079.

[9]Yoon K J,Kweon I S.Adaptive support-weight approach for correspondence search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(4):650-656.

[10]Rhemann C,Hosni A,Bleyer M,et al.Fast costvolume filtering for visual correspondence and beyond[C]//2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR),2011: 3017-3024.

[11]Zhang K,Lu J,Yang Q,et al.Van Gool,Real-time and accurate stereo:a scalable approach with bitwise fast voting on CUDA [J].IEEE Trans. Circuits Syst.Video Technol,2011,21(7):867-878.

[12]Yu W,Chen T,Franchetti F,et al.High performance stereo vision designed for massively data parallel platforms[J]IEEE Trans.Circuits Syst.Video Technol.2010,20(11):1509-1519.

[13]Sun X,Mei X,Jiao S,et al.Stereo matching with reliabledisparitypropagation [J].International Conference on 3D Imaging,Modeling,Processing, Visualization and Transmission,2011:132-139.

[14]Kim S,Yoo D,Kim Y H.Stereo confidence metrics using the costs of surrounding pixels[J].Interna’tional Conference on Digital Signal Processing, 2014:98-103.

[15]Chang X,Zhou Z,Wang L,et al.Real-time accurate stereo matching using modified two-pass aggregation and winner-take-all guided dynamic programming[J].International Conference on 3D Imaging, Modeling,Processing,Visualization and Transmission,2011:73-79.

Real-time stereo matching based on extended binary weighted aggregation

MAO Kan，JING Da-hai
（Computer and Information Institute，Hohai University，Nanjing 211110，China）

In order to ensure the accuracy of real-time to improve the matching accuracy，this paper puts forward a real-time stereo matching method based on extended binary weighted aggregation.The extended binary weighted aggregation is based on the following two new ideas.First，the extended binary weighted aggregation connects distant regions over color boundaries to make them one large support region for a given pixel.Second，it excludes outliers in the support region to make a high quality support region.The extended binary weighted aggregation and other real-time stereo matching methods are compared by the experiment. Experimental results show that，the proposed stereo matching method shows an average of 5.10%of the bad pixel rate，it is the highest accuracy of these all existing real-time stereo matching methods.

stereo matching；binary weighted aggregation；remotely connected aggregation；outlierexcluded aggregation

TN91

：A

：1674－6236（2017）06-0160-05

2016-03-07稿件編號(hào)：201603070

茆 看（1992—），男，江蘇鹽城人，碩士研究生。研究方向：圖像信息處理。