基于改進Census變換與最小生成樹的立體匹配算法?

于修成 宋 燕 李 航

（上海理工大學光電信息與計算機工程學院 上海 200093）

1 引言

立體匹配是計算機視覺的基礎和研究熱點之一，是通過尋找雙目或多目圖像中的對應點進而估計場景深度信息的過程，在機器人導航、虛擬現實 、以 及 三 維 重 構 等 領 域 得 到 廣 泛 應 用［1～2］。Scharstein［3］對當前現有立體匹配算法進行了分類研究，對諸多算法在性能上進行了詳細的分析對比，建立了較全面的測試體系。此外，Scharstein提供了相應的測試數據集以及比較方法，同時將立體匹配的過程大致分為四個階段：代價計算、代價聚合、視差計算/優化、視差強化等。

在代價計算中，常見代價計算方法是將像素差異的絕對值作為匹配代價。Pollard［4］等證明通過將圖像梯度信息引入到匹配代價計算中，可以增強匹配代價對幅度等失真的抗干擾能力；Zabin［5］等提出將非參數變換引入到代價計算中，可以顯著減少光照和噪聲等干擾的影響。Hirschmuller［6］等提出Census變換在光照失真的條件下具有很好的穩健性。但傳統Census變換依賴于中心像素灰度值大小，對噪聲比較敏感。通過代價計算得到的匹配代價存在較大的噪聲，將其作為視差選擇的標準會造成較大的誤匹配，因此需要將當前代價和其鄰域代價進行聚合。常見的代價聚合方法有盒子濾波、高斯濾波，此類濾波器實現簡單，但往往會模糊圖像深度邊界。Yoon［7］等使用雙邊濾波進行代價聚合，在保留深度邊界的同時增加了算法的復雜度。Rhemann［8］等將導向濾波引入代價聚合，使得聚合的效果和時間效率得以進一步提升。然而，以上聚合算法都是基于支持窗口內的聚合，忽略了窗口外的像素信息，因此通過此類算法得到的視差圖還有待進一步完善。Yang［9］等將圖像看作是一張無向圖，并對無向圖進行去除最大邊界處理得到最小生成樹，然后在最小生成樹上進行代價聚合。這樣的聚合方式將支持窗口擴展到整幅圖像，進一步提高了匹配的精度。在視差選擇和優化中，根據優化算法的不同可以將立體匹配算法分為局部立體匹配和全局立體匹配。局部匹配是選擇最小匹配代價對應的視差作為最終的視差，而全局算法則是建立一個全局能量函數，對函數進行求最優化即可得到最終的視差圖。在全局算法中，較為經典的算法包括動態規劃［10］、圖割法［11］、置信傳播［12］等。需要說明的是，通過以上方法得到的視差圖仍存在誤匹配，從而需對視差圖進一步強化如左右一致性檢驗、空洞填充、中值濾波等［13］。

通過以上分析，針對基于傳統Census變化計算匹配代價存在的問題，本文提出一種基于增強Census變換的多尺度立體匹配算法。在代價計算階段，首先將支持窗口內像素的加權平均值作為Census變換的參考值，該權重包含支持窗口內空間信息和像素差異信息，并為參考值增加一定的噪聲容限α，然后通過比較得到四個狀態的二進制表示。進而，在代價聚合階段，基于多尺度圖像采用最小生成樹算法進行代價聚合，從而綜合了圖像中所有像素信息。該方法使得立體匹配率進一步提高，并在噪聲情況下具有一定的穩健性。

2 算法描述

立體匹配算法由代價計算、代價聚合、視差選擇和視差強化等步驟組成，本文所提的算法也包含以上步驟。

2.1 匹配代價計算

傳統Census變換是將中心像素灰度值與支持窗口內所有像素進行比較生成匹配模板，然后進行非參數變換獲得比特串，最后用漢明距離計算匹配代價，該算法對中心像素的依賴性強，抗干擾能力差。Chang［14］等提出用支持窗口內所有像素的均值作為參考值的算法（MCT），該算法將鄰域像素信息融入參考值的計算，進一步提高了單像素匹配代價的可靠性，但不能很好地利用中心像素與鄰域像素之間的關系。文獻［15］提出用支持窗口內所有像素的加權平均灰度值作為參考值的算法（SWCT），其中權重由支持窗口內像素的空間信息決定，該算法進一步提高了Census算法的穩健性，但忽略了窗口內鄰域像素與中間像素的差異信息。

針對上述Census變換存在的問題，提出一種改進的Census變換來計算匹配代價，每一個Census變化的參考值由支持窗口內像素的加權平均后得到。具體地，用支持窗口去掃描圖像中的每一個像素，將窗口內像素的加權平均值作為Census變換參考值，其中權重由空間信息和支持窗口內像素差異共同決定。改進算法參考值計算公式與權重計算公式分別為

其中 p、q分別為支持窗口內中心像素和鄰域像素索引，Iwm為用于Census變換的參考值，Wpq為像素 p、q之間的權重，D=∑Wpq為歸一化常數，也為所有權重之和，N為支持窗口內所有像素，‖‖p-q為像素p、q之間的歐氏距離，rp為空間標準差，Ip、Iq為像素索引 p、q的像素值，rc為像素標準差?？紤]到噪聲的影響，為Census變換參考值增加一定的噪聲容限α，則利用Census變換計算該支持窗口的比特串公式為

其中

其中C（p，d）為像素點 p在視差為d時的匹配代價，d∈[0，dmax]。 Ham[x，y]為計算比特串 x和 y的漢明距離，Tcen為截斷閾值，λ為控制離群值參數。

由上述分析可見，傳統Census算法采用支持窗口中心像素作為參考值，然而改進Census算法采用支持窗口內像素的加權平均值作為參考值，并對其增加噪聲容限α。然后用四個狀態對其進行表示，改進Census算法的抗干擾能力比傳統Census強。此外，與SWCT算法采用基于窗口空間信息的加權平均值不同，改進算法采用基于窗口內空間信息和像素差異信息共同決定的加權平均值作為參考值，得到匹配率更高的視差圖。以上幾種方法得到的視差對比圖如圖1所示：由于Venus圖像包含豐富的顏色信息，SWCT變換僅僅使用空間信息來求解權重，因此得到的視差圖存在較多的誤匹配點，得到的視差圖比較粗糙，如圖1（c）所示。圖（d）為改進Census變換得到的視差圖，與（c）相比，視差圖平滑了許多，在視差不連續區域視差圖有明顯的改善（紅色方框內）。因此，改進Census匹配代價計算方法有較強的穩健性，其匹配效果更加精準。

圖1 SWCT與改進Census變換得到的視差圖

2.2 匹配代價聚合

2.1節定義了基于像素的原始匹配代價，但由于基于像素的匹配代價易受噪聲的影響，因此需要利用周圍像素的匹配代價進行代價聚合，提高視差的區分性。傳統代價聚合大都采用支持窗口進行聚合，最簡單的是盒子濾波?；谥С执翱诘拇鷥r聚合本質上只考慮了窗口內像素對中心像素的影響，窗口之外的像素影響徹底忽略。易見，此類算法匹配效果差，誤匹配率高。

基于最小生成樹的代價聚合將聚合窗口擴展到整幅圖像，使得匹配的精度進一步提高。和以往的成本聚合方法不同，最小生成樹算法首先將圖像I表示為連接的無向圖G（V，E），其中V是所有圖

其中 I（s）、I（r）為邊所連接的兩個節點 s和 r 的像素值。然后，通過kruskal算法或prim算法進行優化，尋找兩節點之間的最小連接，進而生成最小生成樹。最小生成樹中節點 p和q的距離是兩個節點之間的連接邊的權重之和，記為D（p，q），則 p、q之間相似度為像像素節點，E為連接節點的邊，其權重為

其中σ為調節相似度常數。因此，對于像素點 p，其聚合后的匹配代價為

在不同尺度下分別對匹配代價圖進行代價聚合，具體過程類似于文獻［16］，最終的聚合代價為

其中 A 為 （S+1）×（S+1）的系數矩陣；S 為下采樣層數；為第0層的匹配代價。

2.3 視差計算與強化

運用Winner-Takes-All（WTA）算法，選取對應匹配代價最小的視差作為最終的視差，從而得到視差圖。獲取視差的公式為

其中dfinal表示最小代價對應的最優視差；p為當前像素。

在視差強化階段，首先通過左右一致性來檢測匹配異常點，判斷公式為

其中dL、dR為左右初始視差圖，Th為視差閾值。不滿足以上公式的點視為異常點，否則為穩定點。異常點需要進行修正。具體地，對于異常點 pout，在水平方向上分別往左和往右各找到第一個穩定點 pinL和 pinR。將異常點 pout的視差值修正為 pinL和pinR中的較小值，計算公式如下：

3 實驗與結果分析

使用Middlebury2.0立體匹配評估測試平臺對所提算法進行評估，測試圖片包括2001，2003，2005，2006四個數據集中的 31組立體圖像對［17］。實驗環境為Visual studio 2013下C/C++編程環境，Windows 10，X64位系統，Intel Core i7處理器，內存為8GB。

為了驗證所提算法的實際性能，除特殊說明之外，文中所涉及到的視差圖都是未經過任何視差精化和后處理的初始視差圖；對比實驗中誤差設置為一個像素差，也就是算法所得到的視差圖與真實的視差圖之間的差距大于1個像素則將該點標記為誤匹配點。

3.1 匹配代價計算實驗

為驗證改進Census算法的有效性，選擇基于梯度變換（GRD）、傳統Census變換（CT）、基于平均值的Census變換（MCT）、基于加權平均的Census變換（SWCT）四種不同匹配代價方法和所提算法在Middlebury2.0中4組標準立體圖像進行實驗對比。通過非遮擋區域和所有區域的誤匹配率來測試算法的性能，如表1、2所示。

表中結果表明，所提匹配代價計算方法未經過視差強化時在非遮擋區域的平均誤匹配率為3.65%，所有區域的平均誤匹配率為10.11%，與其他代價算法相比，本文提出的算法具有較低的誤匹配率。

GRD、CT、SWCT與本文算法的視差圖如圖2所示，可以看出，本文算法的視差圖中紅色標記點（誤匹配點）明顯少于其他算法，在網格孔、邊界交界處尤為明顯；圖2（b）和2（c）中弱紋理區域的誤匹配點明顯少于圖2（a），說明基于Census變換的算法要比GRD在弱紋理處有較好的匹配效果；在邊緣視差不連續區域，圖2（a）的紅色誤匹配標記點明顯比2（b）和2（c）少，表明基于像素差異信息的GRD算法要比CT和SWCT算法在視差不連續區域有較好的匹配效果；圖2（d）為所提算法的視差圖，由于其采用基于空間和像素差異信息的改進Census變換，可以看出在弱紋理區域和視差不連續區域的誤匹配率明顯減少，表明所提算法的誤匹配率低、精度高。

圖2 不同匹配代價算法獲得的視差圖

3.2 抗干擾測試

為了測試所提算法的穩健性，選取4種傳統算法（GRD、CT、MCT和 SWCT）與本文算法進行比較。給4組標準立體圖像加入噪聲密度為3%的椒鹽噪聲，通過非遮擋區域的平均誤匹配率來測試匹配算法的性能，實驗結果與數據如圖3和表3所示。

噪聲實驗結果表明，在增加一定的噪聲后，本文算法均優于其他幾種匹配算法，因此本文算法對噪聲具有較好的穩健性。

表3 非遮擋區域在有噪聲情況下的誤匹配率

圖3 加入椒鹽噪聲后，CT與所提算法對比圖

3.3 27組數據集測試結果

為了進一步測試本文算法的總體性能，對Middlebury2.0平臺另外27組立體圖像對（M27）進行測試，通過非遮擋區域誤匹配率百分比來對比相關算法與所提算法的性能。實驗結果如表4所示，視差圖未經細化處理，誤差限制為1pixel。

表4表明，本文算法在27組立體圖像對的平均誤匹配率最低，僅為10.8%。在立體圖像對Lampshade2中最高誤匹配率為32.45%，本文算法僅為12.17%，誤匹配率降低了20.28%；在Midd2中，最高誤匹配率為50.66%，而本文算法僅為17.35%。實驗結果表明，本文算法進一步降低了誤匹配率，提高了匹配精度。

表4 非遮擋區域不同匹配代價計算方法誤匹配率（M27）

4 結語

提出了一種改進的局部立體匹配算法，用支持窗口的加權平均灰度值作為Census變換的參考值，其中權重由支持窗口內的空間和像素差異信息共同決定。該算法融合像素差異信息，更好地利用了圖像的紋理信息，使得匹配精度進一步提高。此外，該算法為Census參考值增加一定的噪聲容限，通過四種狀態得到比特串，從而使得匹配算法具有一定的抗干擾能力，增強了算法的穩健性。進而，利用最小生成樹算法分別在不同分辨率尺度下進行代價聚合，充分利用了圖像的細節信息，降低了圖像在視差不連續區域和弱紋理區域的誤匹配率。最后，運用實驗對本文算法與相關算法進行比較，結果表明本文算法的匹配精度要明顯優于其他算法，尤其是在視差不連續區域和弱紋理區域。在抗干擾測試中，所提算法也表現出較強的穩健性。需要說明的是，從誤差標記的視差圖中可以看出，本文算法在細節區域中的匹配精度還有待提高，這將是我們下一步的研究工作。