基于自適應權重的立體匹配優化算法

文 斌，朱 晗

（三峽大學電氣與新能源學院，湖北宜昌 443000）

0 概述

立體匹配是指通過雙攝像頭中的二維場景，利用視差匹配獲取三維場景的深度信息，被廣泛地應用于移動機器人技術、3D 建模技術、航空航天［1］等領域，是雙目立體視覺的重點和難點，立體匹配的精確度決定了立體視覺的最終效果。因此，研究更加高效、精確的立體匹配算法具有重要意義。

目前，立體匹配主要分為全局匹配和局部匹配兩大類［2-3］，文獻［4］根據雙目立體匹配算法的特點進行歸納總結，將立體匹配算法分為匹配代價計算、代價聚合、視差計算和視差優化4 個部分。全局匹配是利用圖像的全局約束信息構建全局能量函數，通過優化算法使得全局能量函數最小從而構建稠密視差圖。雖然全局匹配精確度較高，但是全局匹配存在運算復雜、能量函數不易構建等問題。而對于局部匹配，由于其運算速度快、算法的復雜度低、能量函數易構建等優勢，因此更加受到研究人員的青睞。

局部立體匹配主要是通過局部像素的代價聚合實現的，具有代表性的傳統的代價聚合算法有SAD［5］、SSD［6］和NCC 歸一化［7］匹配算法。SAD 和SSD 匹配算法計算量小、運算速度快，但是該算法的匹配準確度完全依賴于中心點的灰度值，并且由于其代價聚合是等價聚合，易受到低紋理區域以及視差不連續區域的干擾，產生大片的誤匹配區域和視差空洞。NCC 歸一化算法可以有效地降低光照對匹配的影響，但傳統的NCC 算法運行較慢，且其匹配率對于SAD 算法而言沒有優勢。

BM 匹配算法是基于字符串搜索規則和SAD 匹配算法的代價聚合實現的，采用壞字符與好后綴的原則進行匹配［8］，相對于SAD 算法，低紋理區域的匹配有了一定的完善，但對于復雜環境的視差不連續區域的匹配依舊存在較大缺陷。

立體匹配的核心思想是將特定區域內的多個像素點的相互聯系歸一化到一個能量函數的框架之下，將立體匹配的最優匹配問題轉換成能量函數最小化問題。為構建更好的能量函數，提高匹配精度，國內外學者對立體匹配進行了研究。文獻［9］提出了自適應權重的立體匹配算法，將自適應的概念引入到代價聚合中，根據Lab 顏色空間的相似性和歐式空間距離的接近性自定義代價權重，結合雙邊濾波器，表現出了較好的性能。文獻［10］介紹了一種新穎的基于三邊濾波器的ASW 方法，該方法使用了RGB 顏色空間的相似性，并將匹配代價改為灰度差異值和X方向上梯度差異值之和。文獻［11］融合權重的思想，實現灰度、漢明距離、梯度三者代價的非等比例聚合，在聚合代價前加入濾波權重，以期降低立體匹配代價體積濾波計算成本。文獻［12］將基于灰度空間的自適應權重算法與Census 變化融合，提高算法在實際場景的穩健性。文獻［13］將權重系數的Lab 空間顏色相似性改為RGB 顏色空間相似性，以滿足機器人平臺實際應用中廣泛使用的攝像機模式。

本文提出一種基于自適應權重的立體匹配優化算法，該算法基于自適應權重算法的核心框架，并保留了Lab 空間顏色的相似性和歐式空間距離的接近性。為使得自適應權重算法能與其他處理算法有良好的兼容性，對初始匹配代價進行修改，將RGB 顏色空間差異與高斯差分圖像差異進行聚合來設置截斷閾值，并選擇邊緣約束對遮擋部分進行視差同化。此外，為并保證自適應權重算法運行時不受窗口大小的影響，提出基于高斯差分圖像判斷的自適應窗口算法，以保證匹配算法的最優性能。

1 自適應權重的匹配算法

1.1 ASW 算法

自適應支撐權重（Adaptive Support Weight，ASW）立體匹配算法一種經典局部匹配算法，該算法是在SAD算法的基礎上進行的改進，修改了SAD 匹配算法的匹配代價并增加了自適應權重。因此，與SAD 匹配算法不同，ASW 算法在代價聚合時是根據格式塔理論，并不是簡單地將窗口內所有像素的匹配代價等價聚合，其核心思想是為窗口內每一個像素分配一個合適的權重，計算單個像素的權重，然后進行加權匯總代價。根據格式塔理論的接近性與相似性原理，距離越小，分配的權重越大，顏色越相似，其分配的權重也會更大。假設q是以p像素點為中心的窗口內的任意一點，其空間的接近性定義為：

其中，λd為距離差異系數，ΔDpq為p和q在歐式空間中的距離：

其顏色的相似性定義為：

其中，λc為顏色差異系數，ΔCpq為p和q在Lab 顏色空間中的距離：

那么，p和q之間的權重定義為：

則匹配代價E(p，)的計算公式為：

其中，是在視差范圍內，像素點p、q匹配的被搜索圖像中的像素點，Np是以p點為中心的窗口，e(q，)表示q點與點之間的初始匹配代價，Ic表示像素點所在顏色空間的色度值，c屬于RGB 顏色空間分量，T是截斷閾值。

1.2 ASW 改進算法

針對立體匹配中低紋理區域和視差不連續區域，ASW 算法的匹配效果表現一般。本文通過改進ASW 算法來優化低紋理區域和視差不連續區域的匹配。

低紋理區域和視差不連續區域的匹配問題普遍存在于立體匹配中，低紋理區域的誤匹配易造成視差空洞，視差不連續區域的誤匹配問題很容易造成忽略圖像細節區域。因此，本文算法從初始匹配代價上著手改進，在求RGB 顏色空間分量差分和的基礎上加入高斯差分圖的差分值：

其中，A為RGB 顏色空間分量差分權重，B為高斯差分圖差分權重，本文取A=0.1，B=0.1。ΔDOGq為像素點q和的高斯差分圖像差分的絕對值：

假設是一對待匹配點，則DOGq、DOGq分別為參考圖像和搜索圖像的高斯差分圖像［14-15］。

1.3 自適應窗口

低紋理區域的匹配問題一直是立體匹配中的難點。低紋理區域的匹配窗口選擇過小，就無法得到更多的特征像素點，難以準確匹配，紋理豐富的區域匹配窗口選擇過大，易造成前景膨脹效應和匹配計算復雜度過高。針對上述問題，文獻［16］提出了通過測算局部灰度和視差變化來選取適當窗口的方法，但該方法效率低下，對視差初值的要求較高。文獻［17］針對文獻［16］中存在的問題，提出一種僅利用灰度信息確定窗口的方法，該方法解決了文獻［16］中效率低下、初值敏感的問題，但該方法的計算量仍不能滿足實際需求。文獻［18］采用灰度信息的自適應窗口算法，根據窗口內像素灰度值的平均值選擇窗口，但其算法的主要作用是用于降低運算時間，圖像的誤匹配率沒有降低，反而略有升高。

本文提出的自適應窗口的優化匹配算法主要解決低紋理區域的匹配及降低誤匹配率，而在時間上不做過多要求。該方法的原理是基于圖像特征在尺度空間［15，19］的“模糊”特性。所謂尺度空間的“模糊”特性，是假設從不同的距離觀察一個物體，物體上的特征并不會因為觀察距離的遠近而在視角中消失，只是特征變模糊，而稍弱的特征則會因為過度模糊并不能被人們所捕捉，相當于“消失“。在圖像處理中，通過不同尺度的高斯函數“觀察”圖像，不同強度的特征點受到尺度空間變化的影響也就較小。因此，根據式（10）計算高斯差分圖像：

其中，I(x，y) 為圖像的灰度值，Gσ1(x，y) 和Gσ2(x，y) 分別為σ為σ1 和σ2 時的高斯函數，*為卷積符號，g1(x，y)和g2(x，y)分別為濾波后的灰度圖像。

σ1、σ2 分別取0.1 和255 時的高斯函數圖如圖1所示。

圖1 二維高斯函數圖Fig.1 Two-dimensional Gaussian function diagram

對標準圖像的高斯差分處理結果如圖2 所示。

圖2 高斯差分圖像Fig.2 Gaussian difference images

以圖2（a）Tsukuba 圖像為例可以明顯看出，圖中右上角以及臺燈、桌子等低紋理區域在高斯差分圖像中的像素點的像素值很低，而書架、攝像機等紋理豐富區域在高斯差分圖像中像素點的像素值較大。因此，根據式（11）、式（12）可以很明顯地區分出區域的紋理豐富程度，對于低紋理區域：

其中，D(x，y)為圖像DOG(x，y) 的二值化圖像，TD為閾值，統計大小為K×K窗口內大于閾值TD的像素點個數，若個數小于ε，則為低紋理區域，選擇較大窗口。

基于高斯差分圖像的自適應窗口算法實現簡單，算法復雜度較低，能夠直觀地判斷區域的紋理豐富性。

2 視差計算

2.1 WTA 算法

采用勝者為王（Winner-Takers-All，WTA）［20］算法計算最優視差，假設視差范圍是0～n，E0，E1，…，En是在視差范圍內搜索到的像素點的匹配代價，取匹配代價最小值Eσ(σ∈[0，n])所在的點作為待匹配點的最優匹配點，則該點的視差為σ。

WTA 算法示意圖如圖3 所示。

圖3 WTA 算法示意圖Fig.3 Schematic diagram of WTA algorithm

2.2 遮擋區域的優化

在得到初始視差圖后，仍存在一些遮擋區域的誤匹配點。應用左右一致性原則，找到遮擋區域的誤匹配點。

其中，點是p點的匹配點，d(x，y)為p點所在圖像的視差圖，dp為p點的視差值，為點的視差值。如果兩點的視差差分小于等于T，則認為是正確匹配點；如果兩點的視差差分大于T，則是誤匹配點。

在得到遮擋區域的誤匹配點后，再利用鄰點法，以誤匹配點為中心對4 個方向進行搜尋，找出距離誤匹配點最近的正確匹配點，將最近的正確匹配點的視差值作為遮擋點的視差值。

其中，df為誤匹配點的視差值，da、db、dl、dr和da-d、db-d、dl-d、dr-d分別為上下左右方向上的最近正確視差點的視差值以及最近像素距離。

3 基于邊緣約束的視差聚類

對遮擋區域的誤匹配點優化完成以后，視差圖中在低紋理區域以及光線過亮區域仍存在大量的誤匹配點，并且這些區域還存在視差空洞的問題。針對上述情況，本文引入邊緣作為約束條件，分區域對邊緣約束內的視差點進行聚類處理，減小誤匹配點的誤差，消除視差空洞。主要步驟如下：1）將邊緣圖像加入到視差圖中；2）將邊緣作為約束條件，對視差在橫縱方向上進行處理；3）清除邊緣；4）圖像濾波；5）迭代優化。

3.1 邊緣算子的選取

本文引入圖像邊緣對視差圖進行邊緣約束，選取的是Canny 算子［21］，原因如下：1）Canny 算子在圖像預處理階段使用高斯濾波平滑圖像，有效地去除了噪聲，降低了偽邊緣的識別；2）Canny 算子使用非極大值抑制技術，通過尋找像素點的局部最大值，對非極大值的像素點進行抑制，有效地剔除了大部分非邊緣像素點；3）采用滯后閾值法，設置高閾值DH與低閾值DL，有效地去除了大部分噪聲。

針對Canny 算子高斯濾波以及高低閾值設置，可以根據取主去次的原則，即保留主要的邊緣區域，省略掉一些不重要的邊緣，圖像的整體大概輪廓保留即可。

在得到參考圖像的邊緣圖像后，將邊緣圖像與視差圖進行相加得到新的圖像，本文將該圖像稱之為視差邊緣圖像。

3.2 邊緣約束視差聚類

針對邊緣約束區域內存在的誤匹配點和視差空洞，分別從橫、縱兩個方向對視差點進行處理。對橫軸方向上的處理如下：

在式（16）～式（19）中，先求得橫軸方向上相鄰邊緣點約束的非邊緣視差點的視差值之和sumX0，x0表示左邊緣點所在的橫坐標的值，countP表示相鄰邊緣點約束的非邊緣視差點個數，dg(x，y)表示視差邊緣圖像，值255 表示邊緣上的點的像素值，然后再根據統計的點，求得橫軸方向上相鄰邊緣點約束的非邊緣視差點視差的平均值davgX0，count表示相鄰邊緣點約束的非邊緣視差點以及非視差空洞點的個數。

但上述方法在計算平均視差值時包含了一些離群點，這些點往往是一個視差值遠小于正常值的誤匹配點，導致該方向上整體視差值減小。運用式（20）消除離群點，得到正確視差：

其中，sumX表示橫軸方向上非異常視差點的視差值之和，當視差圖中的某點dg(x，y)與先前求得的視差平均值davgX0的絕對差大于φ時，認為dg(x，y)是離群點，不統計該點的像素值，countQ表示相鄰邊緣點約束的非離群點以及非視差空洞點的個數，davgX表示剔除離群點后橫軸方向上視差的平均值。運用上述方法，遍歷整幅視差邊緣圖像。

同理，對于縱軸方向上的處理方法，參考橫軸方向上的處理方法，遍歷整幅圖像。

完成上述操作后，優化后的視差中還留有邊緣，應用式（22）、式（23）進行消除邊緣：

其中，g(x，y)為邊緣圖像閾值分割后的二值圖像，dg(x，y)為消去邊緣后的視差邊緣圖像。將閾值分割后的邊緣圖像與得到的初始視差圖進行與運算，得到被邊緣所覆蓋視差點的視差圖，再將該圖像與消去邊緣的視差邊緣圖像相加，復原視差圖d(x，y)。

由于同一邊緣區域內的視差幾乎是相同的，應用上述邊緣約束視差的方法，有效地修正了視差圖中的誤匹配點以及視差空洞。

3.3 存在問題及解決方法

上述方法存在以下3 個問題：1）橫向和縱向的單獨處理會出現類似于動態規則算法的水平條紋；2）被邊緣覆蓋重現的視差點存在壞點；3）由于d(x，y)是由邊緣約束處理而來，因此視差圖中存在明顯的邊緣特征，一些同處于背景區域的物體，由于邊緣約束的存在，使得不同物體之間的視差值存在微小差異。

針對上述問題，本文引入中值濾波消除條紋和部分壞點。而對于視差圖中存在明顯邊緣特征的問題，本文提出基于視差圖邊緣約束的迭代聚類算法。

迭代聚類算法的核心在于邊緣更新與迭代精度，假設d0(x，y)為初始視差圖，取視差圖d0(x，y)的邊緣作為新的約束條件，重復3.2 節的步驟得到一次迭代下的視差圖d1(x，y)；取視差圖d1(x，y) 的邊緣更新約束條件，重復3.2 節。

假設第n次迭代后的視差圖為dn(x，y)，該視差圖的誤匹配率為Edn，若視差圖的誤匹配率滿足：

則表明第n次的迭代結果滿足要求，ξ為允許的最大精度。

迭代前后對比如圖4 所示。從圖4 可以看出，一些帶有邊緣特征的區域和視差壞點被消除。

圖4 迭代前后視差對比Fig.4 Parallax comparison before and after iteration

4 實驗結果與分析

實驗使用的計算機操作系統為Win10 專業版，處理器為AMD Ryzen 5 2600X，主頻為3.6 GHz，內存為16 GB，顯卡為Nvidia GeForce GT 730（2 GB）。基于軟件VS2013 和Opencv2.4.11 函數庫進行仿真實驗。實驗所用標準圖片均來源于國際公認的Middlebury［22-23］數據集。其中，Tsukuba 圖像主要測試算法前向平行平面的匹配效果，Venus主要測試對不同斜面的匹配效果，Teddy 測試的是復雜場景下算法的魯棒性，Cones 測試的是算法的整體性能。

將所得到的視差圖與理想視差圖進行比較，逐一判斷像素點是否為正確的匹配點，得到視差圖的誤匹配率為：

其中，N為總的像素點個數，dc(x，y) 為計算得到的視差圖，dT(x，y)為真實視差圖，δ為誤差閾值。

4.1 實驗1

為體現本文算法相對于其他匹配算法在匹配中的優勢，本文選擇在大小為7 的固定匹配窗口下，分別用SAD 算法、BM 算法、傳統ASW 算法以及本文提出算法匹配代價改進的ASW 算法（Improved ASW），對Tsukuba、Venus、Teddy、Cones 4 幅標準圖像進行匹配，并逐一比較，匹配結果如圖5 所示。其中，從左到右依次為原圖、SAD、BM、Traditional ASW 和Improved ASW。各算法誤匹配率如表1 所示。

圖5 不同算法的匹配結果Fig.5 Matching results of different algorithms

表1 各算法誤匹配率Table 1 Mismatch rate of each algorithm %

從表1 的數據可以看出，Tsukuba 圖像由于其場景的復雜性，匹配效果最差，各算法都沒有取得很好的匹配效果，SAD 算法與BM 算法對右上角的低紋理區域都沒有很好地進行處理，產生了大量的誤匹配點。另外，BM 算法在臺燈燈桿的視差不連續區域匹配效果很差。針對上述兩種情況，傳統ASW 算法克服了視差不連續區域的匹配問題，誤匹配率相對于前兩種算法而言，分別下降了7.07%和21.73%，但是對低紋理區域的誤匹配并沒有做到很好的抑制，而改進的ASW 算法則將兩者都進行優化，相對于傳統的ASW 算法誤匹配率下降了1.26%。

Venus 圖像的場景比較簡單，低紋理區域也較少，各算法的誤匹配率都相對較低，傳統的ASW 算法對斜面的適應性不是很強，改進后的ASW 算法克服了這一問題，極大地提升了算法對斜面的適應性，使得誤匹配率下降了近一半，僅有17.17%。

Teddy 與Cones 圖像的視差范圍都比較大，SAD算法不適合處理視差范圍較大的匹配，因此，該算法的誤匹配率較高。與傳統的ASW 算法相比，改進的ASW 算法優化了視差圖中存在的大量噪聲點與少量的視差空洞，提升了性能，降低了誤匹配率。

4.2 實驗2

為體現本文算法對ASW 算法改進的有效性，選擇了在大小為7 的匹配窗口下，代價改進的ASW 算法（Improved ASW）、代價改進+自適應窗口的ASW 算法（Improved ASW+Adaptive W）、代價改進+邊緣約束與迭代聚類的ASW 算法（Improved ASW+edge）、代價改進+邊緣約束與迭代聚類+自適應窗口的ASW 算法（Improved ASW+edge+Adaptive W）對Tsukuba、Venus、Teddy、Cones 4 幅標準圖像進行匹配，并逐一比較。實驗得到的匹配結果如圖6 所示，從上到下依次為Improved ASW、Improved ASW+Adaptive W、Improved ASW+edge 和Improved ASW+edge+adaptive W。各改進算法誤匹配率如表2 所示。

圖6 改進算法的實驗結果Fig.6 Experimental results of improved algorithm

表2 各改進算法的誤匹配率Table 2 Mismatch rate of each improved algorithm %

從表2 的數據可以看出，自適應窗口算法無論是對于色彩多變，還是背景光照強度不一的復雜場景都有一定的提升作用，從Teddy 圖像的匹配結果可以看出，與僅改進匹配代價算法的視差圖相比，視差圖中的空洞區域明顯減小，這表明自適應窗口的ASW 算法優化了該低紋理區域的匹配。基于邊緣約束的視差聚類算法以及基于視差圖邊緣約束的迭代聚類算法表現出了較好的性能，基于邊緣約束的視差聚類算法消除了視差圖中大部分的視差空洞以及異常點，提升了視差圖的整體可靠性。迭代聚類算法從Tsukuba 圖像與其他圖像誤匹配率的對比中可以看出（Tsukuba 圖像經過5 次迭代，其他圖像僅經過1 次迭代），經過多次迭代的視差圖，其誤匹配率的降低量明顯要低于其他圖像，表明了迭代聚類算法的適用性。

與文獻［12-13］進行比較，文獻［12］中Tsukuba圖像的視差圖在視差不連續區域出現了大量的誤匹配點，圖片中的物體失去了應有的邊緣特征，邊緣變形嚴重，得到的視差圖效果極差。文獻［13］中視差圖的情況與其大致相同，并且在低紋理區域還存在一些視差空洞。在Teddy 圖像的視差圖中，文獻［12］在小熊左下部分的低紋理區域出現小片的視差空洞。而文獻［13］中的圖像則表現相對良好，在Cones 圖像中，文獻［13］的視差圖較為標準，文獻［12］的視差圖在圓錐尖峰處，筆筒上部出現少量誤匹配的條紋區域。針對上述研究視差圖中所存在的問題，本文的改進算法都對這些問題有了很好的解決方案，體現了算法較好的魯棒性。

各算法及改進算法平均誤匹配率如圖7 所示。

圖7 各算法及改進算法平均誤匹配率Fig.7 Average mismatch rate of each algorithm and its improvement algorithm

綜上所述，本文算法無論是在算法的魯棒性還是整體性能上，都取得了一定程度上的提升。與SAD算法相比，誤匹配率整體上下降了36.19%，相對于BM算法和傳統的ASW 算法，整體上分別下降了18.03%和15.05%，表明了本文改進算法的正確性。

4.3 實驗3

為體現本文中所提算法對低紋理區域匹配的有效性，以標準圖像Teddy為例，選取一塊具有代表性的低紋理區域，驗證算法對低紋理區域的匹配具有提升作用，其匹配結果對比如圖8所示。

圖8 不同改進算法的低紋理區域匹配實驗結果Fig.8 Experimental results of low-texture regions matching of different improved algorithms

從圖8 可以看出，選取的標記區域是一塊具有代表性的低紋理區域，在實驗中選取不同算法對該區域進行匹配，匹配效果如表3 所示。

表3 低紋理區域匹配效果分析Table 3 Analysis of matching effect of low-texture regions

結合圖8 和表3 可以看出，匹配代價的優化、自適應窗口算法以及基于邊緣約束的迭代聚類算法都對低紋理區域的匹配效果有著提升作用。其中，基于邊緣約束的迭代聚類算法效果最為明顯，使低紋理區域的匹配效果得到顯著提高。

4.4 實驗4

在本文提出的自適應權重立體匹配算法中，分為以下3 個計算步驟：1）匹配代價計算；2）視差計算；3）邊緣約束與視差聚類。假設N表示圖像大小，代表全體像素，那么匹配代價計算的復雜度為O(N)，視差計算WTA 算法的復雜度為O（1），因此，獲得基本視差圖的算法復雜度為O(N)=O(N)×O(1)。邊緣約束與視差聚類屬于視差圖的后處理部分，獨立運行于視差計算部分，其算法復雜度為O(N)，因此，本文所提算法總的復雜度為O(N)。各標準圖像的算法運行時間如表4所示。

表4 算法運行時間Table 4 Algorithms running timemin

本文算法基于傳統的自適應權重立體匹配算法進行修改，雖然效率略低于傳統算法，但是立體匹配的誤匹配率明顯降低，算法運行時間略微增加，主要是計算匹配代價時加入高斯差分以及后面的處理過程。

5 結束語

本文在傳統自適應權重匹配算法的基礎上，提出一種新的立體匹配優化算法。通過修改初始匹配代價，將高斯差分信息引入到代價匹配中，并加入邊緣約束和視差邊緣約束迭代聚類以及基于高斯差分圖的自適應窗口算法，修補視差空洞與誤匹配點。實驗結果表明，該算法能夠有效改善傳統局部匹配算法不能較好地處理低紋理區域和視差不連續區域的匹配問題。下一步將使用GPU 對算法進行并行運算，加快程序的運行速度，滿足實時性需求，并采用卷積神經網絡，結合本文匹配代價的改進方法優化損失函數，利用訓練好的網絡模型，加快視差圖的生成速度與復雜環境的處理能力。