基于改進自適應權重的三邊濾波立體匹配算法

潘衛華，杜 旭

華北電力大學 計算機系，河北 保定 071000

1 引言

雙目立體視覺賦予了計算機類似人類視覺的能力，左右兩臺平行放置的攝像機模擬人類的兩個眼睛，通過改變攝像機位置，從各個角度采集拍攝場景的二維信息[1]。由于攝像機參數已知，可通過公式計算得到攝像機與拍攝位置的距離，從而進一步得到拍攝場景的深度信息[2]。雙目立體匹配是計算機視覺中的重要分支，廣泛用于三維重建、自動駕駛、機器人導航與避障等領域，因此提高雙目立體匹配算法的匹配精確度和運行速度具有重要的意義[3]。

根據獲取視差圖方式的不同，雙目立體匹配算法分為全局立體匹配算法和局部立體匹配算法[4]。全局立體匹配算法指在整個圖像集或者某個子集內尋求能量函數的極小值，從而得到雙目立體匹配的視差圖（Disparity Map），該算法匹配精度較高，但是得到準確匹配結果的同時也帶來了巨大的計算復雜度，從而大大降低了匹配速度[5]。局部立體匹配算法是通過匹配代價函數計算某一窗口相鄰兩個像素之間的相似性得到匹配代價，對代價進行聚合，最后，通過勝者為王（WTA）優化方案進行視差優化，得到最終視差圖[6]。局部立體匹配方法的復雜度為O(NWD),N、W、D分別是圖像大小、窗口大小和視差范圍，相比全局立體匹配算法，局部算法的匹配速度有了大幅度提高，但是匹配結果略有遜色。

近年來，許多學者提出了一系列雙目立體匹配改進算法。Einecke 等[7]提出了一種基于標準互相關函數的局部立體匹配算法，該算法提高了立體匹配的準確率，但是圖像邊緣處的匹配效果不佳。龔文彪等[8]提出了一種基于顏色內相關的自適應權重方法，很大程度上消除了光照差異對匹配精度的影響，但是匹配速度沒有得到很好的提高。Yoon 等[9]根據色彩相似性和幾何距離確定權重，提出了一種自適應支持權重（ASW）算法，降低了匹配復雜度，但無法有效解決邊緣匹配模糊性問題。全局匹配算法[10-11]通過添加幾何方向向量約束，建立斜面匹配模型，有效解決了傾斜平面匹配模糊的問題，但是很大程度上增加了匹配復雜度，增加了運算時間。基于雙邊濾波器的自適應權重立體匹配算法[12-13]取得了與全局算法相當的匹配結果，但在視差不同、顏色相似處的匹配效果不佳。

針對以上問題，本文通過引入邊界強度項，分別從顏色特征和距離特征兩方面測量兩個像素之間視差不連續性的強度，邊界線索在文獻[14]中用于構造更忠實的樹，來改進基于最小生成樹（MST）的代價聚合方法[15]，對傳統的雙邊濾波自適應權重算法進行改進，提出一種三邊濾波自適應權重匹配方法，在有效提高匹配精度的同時，通過遞歸實現，滿足了雙目立體匹配實時性的要求[16]。在Middlebury 基準測試集上的實驗結果驗證了引入的邊界強度項的有效性。

2 雙邊濾波立體匹配

2.1 雙目立體匹配原理

典型的雙目立體視覺系統可由圖1表示，兩臺平行放置的攝像機從不同視角捕獲相同的場景，得到攝像機的左右視圖。

圖1 雙目立體視覺示意圖

其中，P點為三維世界中的物理點，在左右攝像機上的成像點分別為pl和pr,f為焦距，根據三角測量原理可得：

點P距離拍攝點的距離（深度）D為：

其中，d=dl-dr稱為視差（Disparity）。

雙目立體匹配過程可由圖2表示，局部立體匹配算法的處理過程包括匹配代價計算，代價聚合，視差優化和視差細化，局部立體匹配算法的準確性和效率性都高度依賴于代價聚合步驟。

圖2 雙目立體視覺系統流程

2.2 雙邊濾波自適應權重

自適應權重（ASW）算法屬于局部立體匹配的新技術，而基于雙邊濾波器的ASW 方法實現了出色的性能。ASW方法的關鍵思想是估計支持窗口內每個像素的單個權重，然后匯總加權代價。在基于雙邊濾波器（BF）的權重函數中，權重與該像素和中心像素之間的顏色相似性和空間距離成正比[17]。因此，執行代價聚合等同于使用具有邊緣保留屬性的BF來過濾代價量。雙邊濾波權重函數遵循顏色規則和空間規則。

（1）顏色規則：如果兩個像素具有相似的顏色，則它們更可能位于相同的視差范圍，因此權重應該很高。顏色相似性定義為：

其中，q是以像素p為中心的支撐窗口內的像素。參數λc為調整顏色相似性項。顏色距離ΔCpq表示p和q的顏色之間的歐幾里德距離：

（2）空間規則：如果兩個像素在空間上接近，則它們更可能位于相同的視差范圍，因此權重應該高。空間距離項定義為：

其中，參數λd為調整空間距離項，空間距離ΔDpq表示p和q的坐標(x,y)之間的歐幾里德距離：

然后，將這兩個項組合作為最終的BF權重函數：

3 改進算法

所提出的基于三邊濾波（TF）的ASW方法包括以下五個步驟：（1）預處理；（2）匹配代價計算；（3）匹配代價聚合；（4）視差優化；（5）視差細化。在這個流程中，提出了TF權重函數及其在代價聚合步驟中的遞歸實現。這五個步驟如圖3所示。

圖3 TF的ASW方法步驟示意圖

（1）預處理：為了去除孤立的像素，應用標準中值濾波（3×3窗口）來預處理輸入的原始圖像。

（2）匹配代價計算：文獻[18]提出顏色和梯度的截斷絕對差異匹配代價函數，來計算兩個像素之間的匹配代價。一對候選點之間的原始匹配代價Cd(p)為：

其中，d是視差，?x是x方向的導數；ε平衡顏色和導數項；τ1和τ2是截斷值，以減少被遮擋像素的影響。

（3）代價聚合：ASW方法用于在支持窗口內聚合原始匹配代價，使用不對稱策略來計算權重掩模，在視差為處的像素p的聚合代價為：

其中，ωp表示以像素p為中心的支持窗口，q是ωp中的支持像素。

（4）視差優化：采用常用的勝者為王優化策略從一組候選集中選擇最佳視差D(p)：

（5）視差細化：在最后一步中，通過左右一致性檢查，選擇穩定、有效的像素，對生成的視差圖D(?)進行后處理以消除誤匹配并處理遮擋區域的匹配問題。穩定像素應通過一致性檢查，并且有效像素應滿足D(?)＞0，否則在每個視差水平d處的每個像素p的新匹配代價被重新計算：

然后，對該新匹配代價執行聚合步驟以獲得新的聚合代價，其后是視差優化步驟以生成最終視差圖。

3.1 三邊濾波（TF）權重

顏色規則和空間規則可以解決大多數深度模糊問題，但無法為位于不同視差的兩個附近像素分配準確的權重，因此，本節提出邊界規則，引入一個新的邊界強度項We來解決模糊性問題，即如果兩個鄰近像素之間存在邊界，則它們不太可能位于相同的視差，因此權重應該更低。

其中，參數λe為調整邊界強度項，邊界強度距離ΔEpq是使用局部能量模型計算的[19]。具體地，圖像的局部能量為不同取向上的能量組合，給定圖像I，像素p處的局部能量表示為：

其中，*表示卷積運算符，奇數相位濾波器Fθ,odd和偶數相位濾波器Fθ,even是方向θ處的一對正交濾波器，其通過文獻[20]中使用的偏移高斯函數的差來計算局部能量對邊界具有最大響應。偶數相位濾波器Fθ,even定位邊界的位置，像素p的相位定義為：

其中，θmax是給出最大響應的方向：

對于兩個相鄰像素i和j，它們的邊界強度ΔE(i,j)的距離表示為：

對于任意兩個像素p和q，可以定義連接它們的線。假設在該連接線上有N個像素，那么它們的邊界強度是：

其中m和m+1 代表兩個相鄰像素。

如果兩個像素之間沒有邊界，則邊界強度項等于1，邊界越強，邊界強度項越小。然后，將提出的邊界強度項與先前的顏色相似性項和空間距離項組合，形成TF權重函數Wtf(p,q)：

3.2 三邊遞歸濾波

由于上文所提出的TF權重函數的實現非常耗時并且不能真正滿足實時性的要求。因此，在本節提出一種遞歸三邊濾波（RTF）權重函數，它受到雙邊遞歸濾波RBF的啟發，以提高其計算效率。

設x表示階數為n的遞歸系統的1-D輸入，y表示輸出。一般遞歸系統為：

根據上述通式，一階遞歸濾波器的輸出可以簡化為：

因此1-D BF可以聚合為：

其中，x表示2-D 圖像的掃描線，q是該掃描線上的像素。在BF 權重函數的遞歸實現中，顏色相似性被重新定義為：

其中，i和i+1 表示兩個相鄰像素。空間距離項被重新定義為：

然后可以通過水平和垂直執行上述1-D 遞歸實現來計算最終的2-D雙邊濾波結果。

3.1節提出的TF權重函數由兩部分組成，BF部分和增加的邊界強度部分。這兩個部分可以分別計算然后加起來。讓x表示掃描線，然后像素q處的x的1-D TF值是：

BF 部分的遞歸實現在式（21）已給出，將邊界強度項重新定義為：

顏色相似項和空間距離項與RBF 權重函數中定義的相同，使用新的邊界強度項，由數學歸納法可得：

在提出的三邊遞歸濾波權重函數中，使用四對正交濾波器來檢測邊界，這些濾波器是預先計算的并且是所有測試圖像的常數。卷積運算可分為三個步驟：（1）離散傅里葉變換（DFT）；（2）乘法；（3）逆DFT（iDFT）。DFT和iDFT 的計算復雜度是O(NlbN)，其中N表示圖像大小。因此，邊界檢測的計算復雜度是O(NlbN)。然后，單獨執行雙邊濾波部分和邊界強度的遞歸實現，計算復雜度均為O(N)，因此，除了邊界檢測之外，三邊濾波的遞歸實現的計算復雜度是O(N)，其獨立于支持窗口大小。

4 實驗結果與分析

4.1 匹配精度分析

實驗使用 3.4 GHz、Inter Core i7 CPU 和 8 GB 內存的高性能計算機，搭建VS2015+OPencv3.0.0 開發平臺，使用C++編程實現。

實驗樣本來自于Middlebury測試集的Tsukuba（384×288，最大深度為16）、Teddy（450×375，最大深度為59）、Venus（433×383，最大深度為19）以及Cones（450×375，最大深度為59）四組雙目視覺圖像對。

4.1.1 實驗1

共進行三次實驗，對RTF算法和其他雙目立體匹配算法進行比較。在第一個實驗中，為了更好地比較每種方法的代價聚合步驟，選擇了匹配代價計算，代價聚合和Winner-Take-Al（lWTA）優化步驟運行，而不受預處理和后處理的影響。原始視差圖由WTA優化策略直接傳遞，因此沒有進行如中值濾波等任何后處理操作。匹配代價計算步驟的參數設置為相同的值，即{θ,τ1,τ2}={0.1，6，1}。對于代價聚合參數，為每種方法測試了20多個參數設置并選擇了最佳參數，從而保證圖像集上的平均誤差最小，其中RTF：{λe,λc,λd}={0.08,0.7,0.04},RBF：{λc,λd}={0.4,0.06},TF：{λe,λc,λd,r}={0.06,0.08,0.02,0.06,17}，BF：{λc,λd,r}={30,7,17}。誤差閾值設定為1，為了更好地觀察由每種方法計算的原始視差圖，在圖4 中，將誤差像素標記為紅色，用藍色框標記了顏色相似但視差不同的像素所在區域，從實驗結果可以看出，三邊濾波比雙邊濾波在顏色相似但視差不同的區域誤匹配點更少，匹配結果更精確，證明了邊界強度項的有效性。

4.1.2 實驗2

實驗2 中，為了測試所提算法的穩健性，為圖像集添加了密度為3%的椒鹽噪聲，如圖5（b）所示，通過比較RTF與RBF非遮擋區域的平均誤匹配率，來驗證增加的邊界強度的有效性，實驗結果的視覺比較和定量比較圖5和表1所示。

圖4 顏色相似視差不同區域邊緣分布圖

圖5 添加噪聲匹配圖

表1 添加噪聲的誤匹配率 %

定量比較表明，RTF比RBF在處理噪聲方面表現良好，其平均錯誤率為4.48%，低于RBF12.90%的誤匹配率，因為這是基于局部能量邊緣檢測，孤立的嘈雜的椒鹽像素對邊界項沒有影響，因此本文算法對噪聲具有較好的穩健性。

4.1.3 實驗3

通過實驗1 和實驗2，驗證了三邊濾波比雙邊濾波的精度高，在顏色相似但視差不同的區域效果尤其明顯，在實驗3中，將三邊遞歸濾波自適應權重（RTF）算法的匹配結果與雙邊濾波自適應權重算法（BF）、三邊濾波自適應權重算法（TF）、雙邊遞歸濾波自適應權重算法（RBF）以及遞歸邊緣感知濾波算法（REAF）算法進行比較，圖6 列舉了五種雙目立體匹配算法在Middlebury樣本上的匹配結果。

通過視差圖可見，本文提出的邊界強度項是有效的，在顏色相似但視差不同的像素點的匹配效果優于其他算法，此外，由于在RTF算法中，引導圖像表示為無向圖G=(V,E)，頂點V是所有圖像像素，而邊緣E是相鄰像素之間的所有邊緣。所有像素通過四連接網格連接，每個像素的加權代價首先水平聚合（從左到右，然后從右到左），然后垂直聚合（從上到下，然后從下到上）。這導致每個像素的代價通過四連接的網格路徑傳播到其他像素，很好地保證圖像邊緣處的平滑連續性。

根據Middlebury Web 的方法計算并比較上述雙目立體匹配算法得到的視差圖的誤碼率，比較結果如圖7～圖11 所示，從圖中可以看出本文所提的邊界強度項是有效的，通過比較可以觀察到RTF（TF）在平均誤差方面以及在大多數立體圖像對中比RBF（BF）匹配結果更優，RTF 產生較少的誤差像素，在平均錯誤率方面優于其他方法，并且在大多數列中顯示出更好的準確度，尤其是在表示深度不連續附近的區域（圖6 中的白色區域）名為disc的列中，表現更加突出。

圖6 不同算法視差圖比較

圖7 Tsukuba數據集的誤碼率

圖8 Venus數據集的誤碼率

圖9 Teddy數據集的誤碼率

圖10 Cones數據集的誤碼率

圖11 平均誤碼率

4.2 效率評估

通過比較Middlebury基準提供的四個標準，計算評估以上每種方法的代價聚合步驟運行時間，可得統計圖，如圖12、圖13。

圖12 遞歸算法運行時間

圖13 非遞歸算法運行時間

由圖12、圖13 可知，遞歸代價聚合方法RTF、RBF和REAF 算法運行速度遠遠快于非遞歸的雙邊濾波BF和三邊濾波TF 算法，在第3 章中分析了RTF 的計算復雜度為O(N)，RBF 和REAF 算法的復雜度也為O(N)，算法復雜度與支持窗口大小無關。因此，采用遞歸濾波方法進行代價聚合非常有效。另一方面，RTF比RBF耗時多，是因為與RBF 相比，RTF 需要邊界檢測操作。邊界檢測的平均執行時間約為90 ms，且RTF 包括增加了邊界強度項的運算，因此，基于RTF 的代價聚合比基于RBF的代價聚合速度慢，但是在匹配精度上有了很大的提高。具體而言，RTF、RBF 中的代價聚合需要四次掃描，即兩次水平掃描和兩次垂直掃描，而非遞歸的代價聚合需要兩次完全掃描，即從葉到根然后從根到葉，這樣大大增加了運行時間，降低了匹配速度，遞歸實現顯著提高了計算效率。TF、BF 的計算復雜度取決于支持窗口大小，這兩種方法非常慢，從圖12 和圖13 中，可以觀察到 RTF、RBF 比 TF、BF 快將近 100 倍，這證明了遞歸實現的高效性。

5 結束語

通過閱讀文獻資料，研究發現雙邊濾波自適應權重算法不能有效地解決由視差不同但顏色相似的像素引起的模糊匹配問題。因此，本文提出了一種三邊濾波代價聚合方法，通過引入邊界強度項來擴展雙邊濾波，在該三邊濾波代價聚合方法的基礎上，進一步提出了三邊遞歸濾波自適應權重代價聚合方法，從理論角度和實際運行時間角度分析了其計算復雜度，實驗結果顯示該方法相較其他立體匹配方法匹配結果更精確，運算速度更快，證明了邊界強度項的有效性和遞歸實現的高效性。