改進Census 立體匹配算法研究綜述

宋培玉，王 森

（華東交通大學理學院，江西 南昌 330013）

立體匹配技術可以獲得圖像的深度信息，近年來受到了廣泛的關注。 雙目立體匹配的基本原理即模擬人的雙眼，從兩個視點觀察同一場景獲得兩幅視圖，根據(jù)兩幅視圖的像素點構建相似三角形計算兩幅視圖的視差獲取深度信息。 自20世紀80 年代Marr 首次提出完整的機器視覺理論框架[1]。 曾文獻等[2]對立體匹配算法進行了總結，描述了立體匹配算法的基本原理及立體匹配算法的分類。 陳華等[3]描述了立體匹配算法的基本步驟及各個立體匹配算法定性和定量的對比。 曹之樂等[4]總結了立體匹配算法的優(yōu)缺點并對算法進行了深入的討論和研究。 陳炎等[5]將立體匹配算法基于深度學習和人工特征進行了總結。 趙晨園等[6]分析了全局、半全局、局部、深度學習立體匹配算法的現(xiàn)狀及不同算法的效果。 立體匹配技術不僅在醫(yī)療診斷、三維重建領域具有廣泛的應用，而且可以準確、快速的識別障礙物信息，找出最優(yōu)路徑[7]。 但是，快速地得到圖像的準確信息與立體匹配算法密切相關[8]。 全局立體匹配算法雖然可以得到較為精確的深度圖，但是由于硬件設備要求高，計算復雜、實時性較差，一般采用局部立體匹配算法。 局部立體匹配算法主要是基于非參數(shù)變換和灰度相關性進行匹配。 常見的局部代價及算法包括灰度絕對值算法AD（absolute differences）、歸一化互相關NCC（normalized cross correlation）[9]、去均值歸一化互相關ZNCC（zero mean normalized cross correlation）[10]、 互信息MI（mutual information）、梯度法。AD 算法在計算匹配代價時對弱紋理區(qū)域誤差較大； 同時NCC 算法在計算弱紋理區(qū)域和重復紋理區(qū)域時， 由于方差和均值變化不明顯會導致誤匹配； 基于梯度計算代價值在梯度不連續(xù)區(qū)域精度有所提高， 但對于光照的改變不敏感會導致誤差較大。 基于灰度變換算法求視差圖時， 由于噪聲的影響使得到的視差圖不平滑， 因此在實際應用中常使用由Ramin Zabih 和John Woodfill 等[11]提出的基于非參數(shù)的Census立體匹配算法。

本文根據(jù)Census 立體匹配算法的原理，分析算法存在的局限性；根據(jù)算法的局限性歸納算法的改進方向，并對各個改進算法對比；最后討論Census算法的發(fā)展趨勢。

1 Census 立體匹配算法描述

1.1 Census 立體匹配算法原理

Census 立體匹配算法的基本原理是建立以參考像素點為中心的窗口，以此窗口為濾波器，一一遍歷匹配圖像。 利用窗口內中心像素的灰度值和鄰域像素的灰度值的大小關系將原本的鄰域像素灰度值轉化為二進制字符，整個濾波器使得鄰域像素形成二進制字符串，比較兩個字符串的漢明距離即為參考像素點與匹配像素點之間的匹配代價值。Census 立體匹配算法是在立體匹配的算法中引入了非參數(shù)變換的思想[12]。 Census 代價計算過程原理簡單，不需要大量的計算，運行速度快[13]，同時Census 變換一定程度上抑制了噪聲和光照不均勻造成的誤差。 但是，由于立體匹配是一個“病態(tài)”問題，使得算法總存在一定的局限性。

1.2 Census 立體匹配算法局限性

根據(jù)Census 立體匹配算法的變換過程， 可將Census 立體匹配算法的局限性歸納：

1） Census 變換過程中先確立一個固定的窗口，這個固定的窗口在視差不連續(xù)區(qū)域會帶來一些無用點，影響視差圖的精度。

2） Census 在變換過程中是鄰域像素灰度值和中心像素點的灰度值進行大小的比較，一旦中心像素點發(fā)生突變，會使得匹配結果產生極大的誤差。

3） 在Census 變換過程中只利用了鄰域像素的灰度信息，使得鄰域像素的紋理、顏色、距離等信息大量丟失，造成誤匹配。

4） 在Census 變換過程中只考慮中心像素和鄰域像素的關系，忽視了鄰域像素和鄰域像素之間的關系，影響視差圖精度。

In Figure 1: λ is the traveling wave wavelength, mm; 2a is the contact area length, mm; hm is the thickness of the friction material layer, mm; Wz is the vertical amplitude of the traveling wave, mm. The traveling wave equation of the stator surface can be written as follows

2 改進的Census 立體匹配算法

為了增強Census 立體匹配算法的性能，近年來提出了許多Census 立體匹配的改進方法。 以下將Census 的改進方法分類歸納。

2.1 基于變換窗口的Census 立體匹配算法改進

Census 代價計算中如何選擇合適的窗口是一個難題[14]。窗口過大可能導致視差不連續(xù)，產生大量“無用點”， 窗口過小造成無法區(qū)分圖像紋理信息，產生誤匹配。傳統(tǒng)的Census 立體匹配算法計算代價函數(shù)時，選定固定的窗口去尋找匹配像素點，當遇到視差不連續(xù)區(qū)域時，窗口內的像素灰度值變化較大，可能會造成誤匹配。 基于可變窗口對傳統(tǒng)Census 立體匹配算法優(yōu)化，優(yōu)化思路分為2 種：①改變窗口的形狀，在視差不連續(xù)區(qū)域根據(jù)梯度算子[15]計算出邊緣，從而確定窗口大小，使其保持在視差連續(xù)區(qū)域，去除了視差不連續(xù)區(qū)域的“無用點”；②通過對窗口內的像素點賦予權值，減少視差不連續(xù)區(qū)域的誤差，從而降低“無用點”對代價值的影響。

匹配窗口不一定都是n*n 的正方形窗口，也可選擇長寬不等的矩形窗口， 降低視差不連續(xù)區(qū)域“無用點”帶來的誤匹配。 張麗君[16]的實驗結果發(fā)現(xiàn)采用長比寬短的形狀在豎直邊緣深度不連續(xù)區(qū)域可得到較高精度的視差圖，采用長比寬長的形狀在水平視差不連續(xù)區(qū)域可得到較高精度視差圖。 雷磊等[17]采用高斯模板確定代價計算的窗口，把窗口內的像素坐標帶入高斯函數(shù)中確定各個鄰域像素點的權值，從而降低“無用點”帶來的誤差。黃超等[18]通過窗口內像素灰度的平均值調節(jié)窗口形狀，設置最大窗口值和閾值來確定最佳的窗口，一定程度上也可以減少誤匹配。

2.2 基于中心像素灰度值的Census 立體匹配算法改進

大多數(shù)Census 立體匹配算法的改進都是基于中心像素點的改進。在代價計算過程中Census 立體匹配算法過度依賴中心像素點的灰度值，使得Census 立體匹配算法產生的視差圖精度較低。 為了防止中心像素點突變造成的誤匹配，可從以下思路優(yōu)化：以窗口內像素點灰度的平均值代替中心像素點的灰度值，理論上可以減少中心像素突變產生的誤差；利用窗口內像素點之間的信息，判斷中心像素點是否發(fā)生突變。

Ma[19]，Chang[20]，劉建國等[21]為改善中心像素點突變造成的誤匹配，利用鄰域像素平均值代替中心像素灰度值，此方法在一定程度上提高了初始代價值的可靠性。 理論上也可選擇中心像素點鄰近的四鄰域或八鄰域像素點的灰度值的平均值[22]來代替中心像素點的灰度值；劉爽等[23]將窗口內的灰度值進行排序，去除最大值和最小值之后求取均值，再進行比較，相比于用窗口內的所有像素平均值可靠性更高；黃彬等[24]利用正態(tài)分布為窗口內像素點的距離設置不同的權重即格式塔原理[25-26]，設定一個閾值判斷中心像素點是否突變，這樣大大降低了噪聲對視差圖的影響，使得初始視差圖中的噪聲點明顯減少。

2.3 基于鄰域像素其他信息的Census 立體匹配算法改進

鄰域像素的灰度平均值雖然一定程度上可以降低誤匹配，但未能充分利用各個鄰域像素與參考像素之間的其他特征關系。 為了防止鄰域信息的大量丟失可以利用窗口內鄰域像素的距離、 顏色、紋理、梯度等信息對中心像素點的灰度值進行控制。

梁海波等[27]在Census 代價計算過程中加入了局部紋理反差加權項[28]描述圖像的方向性，用鄰域像素平均值和局部紋理反差項代替中心像素點灰度值， 此方法增加了二進制字符串的排列方法，減少了誤匹配；侯華等[29]利用色補理論即兩個像素的灰度值為窗口內的最大值和最小值，則這兩個像素顏色互為補色，來改變中心像素灰度值，使得在代價計算過程中加入了鄰域像素的顏色信息，同時在中心像素發(fā)生突變時也不會影響視差圖的精度，提高了代價匹配的抗干擾性。 徐源等[30]將Census 立體匹配算法代價計算過程中的灰度值比較改成了中心像素點和鄰域像素點之間的梯度比較，進而計算漢明距離，一定程度上減少了對中心像素點的過度依賴，時間復雜度相對較低，同時精度有所提高。

2.4 基于二進制字符串的Census 立體匹配算法改進

在不改變中心像素點灰度值的情況下，為了提高傳統(tǒng)Census 立體匹配算法精度， 改進的Census立體匹配算法可從弱化中心像素點為唯一決定性角度出發(fā)，利用鄰域像素之間的信息對中心像素點進行約束， 降低中心像素點發(fā)生突變時產生的誤差。 改進的思路大致分為兩類：在鄰域像素灰度值和中心像素比較之后，再把鄰域像素灰度值和像素平均值進行比較，或者鄰域像素和鄰域像素進行比較，增加編碼長度，降低誤匹配率；引入控制噪聲的變量，使鄰域像素灰度值與其比較，也可以增加編碼長度，從而降低誤匹配率。

2.5 基于代價聚合的Census 立體匹配算法改進

對于Census 立體匹配算法得到的視差圖精度不足等問題，也可進一步利用其他信息即代價聚合方法對視差圖進行優(yōu)化， 得到精度較高的視差圖。大致可以分為3 個方向進行代價聚合：充分利用鄰域像素顏色、距離、插值等信息進行優(yōu)化；使用濾波的方法增加視差不連續(xù)區(qū)域的精度，使圖像邊緣保持平滑； 利用跨尺度的方法提高圖像的分辨率，提高匹配代價的精度。

Woodfill 等[34]通過相近像素具有相似的顏色對中心像素進行優(yōu)化；楊淑云[35]在代價聚合階段利用四路徑插值的方法優(yōu)化鄰域像素灰度值， 從而提高代價值精度；Yoon 等[36]利用了雙邊濾波以及He 等[37]采用引導濾波的方法對圖像邊緣信息進行優(yōu)化，提高了邊緣像素的匹配代價值的精度；Zhang 等[4]將多尺度的優(yōu)化方法加入到代價聚合中，利用人眼由遠到近的觀察方式將圖像分成不同的分辨率，大大提高了信息的利用率。

2.6 基于融合算法的Census 立體匹配算法改進

根據(jù)Census 立體匹配算法計算代價函數(shù)所導致的視差圖精度不足的問題， 許多研究者提出了Census 算法與其他局部立體匹配算法融合來計算代價函數(shù)。 其思想就是用其它局部算法來彌補Census 計算代價函數(shù)過程中的缺點，從而降低誤匹配率，提高視差圖精度。 可以和梯度算法融合降低視差不連續(xù)區(qū)域的誤匹配；和灰度差融合降低重復紋理區(qū)域的誤匹配；和權重或者改進的灰度、梯度進行融合。

Mei[38]提出了一種很經典的AD（灰度差絕對值）和Census 的融合算法，實驗結果表明，這兩種算法的融合大大提高了在弱紋理和重復紋理區(qū)域的視差精度；蕭紅等[39]將傳統(tǒng)的Census 算法和梯度算法融合， 相比于傳統(tǒng)的Census 算法誤匹配率大大降低；鄒進貴等[40]將自適應權重的SAD 算法和Census融合，實驗結果表明融合的Census 算法在時間復雜度不增加的情況下誤匹配率大大降低，同時對亮度差異也有一定的抗干擾性，3 種算法的匹配代價融合也可以提高算法的精度。

3 改進Census 立體匹配算法對比分析

3.1 立體匹配算法優(yōu)缺點對比分析

表1 基于變換窗口的Census 改進算法對比Tab.1 Comparison of Census improved algorithms based on transform window

表2 基于鄰域像素平均化中心像素點Census 的改進算法對比Tab.2 Comparison of improved algorithm based on neighborhood pixel averaging center pixel census

表3 基于鄰域像素其他信息Census 的改進算法對比Tab.3 Comparison of improved Census algorithm based on other information of neighborhood pixels

表4 基于弱化中心像素點為唯一決定性因素Census 的改進算法對比Tab.4 Comparison of improved Census algorithm based on weakening center pixel as the only decisive factor

表5 基于代價聚合的Census 改進算法對比Tab.5 Comparison of improved Census algorithm based on cost aggregation

表6 基于融合算法的Census 改進算法對比Tab.6 Comparison of improved Census algorithm based on fusion algorithm

表7 各類改進Census 算法對比Tab.7 Comparison of various improved Census algorithms

3.2 立體匹配算法效果圖對比分析

算法是在Visual Studio 2019 軟件平臺上使用C++操作實現(xiàn)的， 采用集數(shù)據(jù)集Middlebury 上的Cones 圖像對算法進行驗證[41]，實驗環(huán)境為Windows10，X64 系統(tǒng)，Intel Core i5-7200U，主頻為2.50 GHz。部分改進后的Census 立體匹配算法效果圖如圖1 所示。

圖1 Census 算法效果圖Fig.1 Effect of census algorithm

改進的算法一定程度上提高了視差圖的精度，不同的改進算法在弱紋理，重復紋理等區(qū)域都有一定程度的視差精度的改善。 但在視差不連續(xù)區(qū)域的匹配精度效果仍然不太理想， 有待改進。 以上改進的Census 立體匹配算法中還存在大量的噪聲點，因此在實際應用中往往根據(jù)Scharstein D[42]的視差計算步驟對改進后的視差圖進行視差優(yōu)化以達到需要精度。

改進算法匹配代價時間對比如表8 所示。

表8 改進Census 算法效果圖的時間對比Tab.8 Time comparison of the improved Census algorithm effect diagram

改進算法效果圖精度越高相對的時間復雜度越高。

4 Census 立體匹配算法的應用和發(fā)展趨勢

雙目匹配是計算機視覺中一直以來存在的問題之一，雙目匹配是一個“病態(tài)”問題，已有近40 年的實踐和研究。 多年來，立體匹配算法從全局算法到局部算法以及像素級的各種轉變?yōu)檫B續(xù)優(yōu)化和離散優(yōu)化。因為Census 局部立體匹配算法相對來說原理簡單、運行速度快、匹配精度較高和抗干擾性強，使得Census 算法在重建實時交互性三維場景得到廣泛應用，是獲取三維場景結構信息的研究熱點之一；在FPGA 上最常用的就是Census 算法[43]，它結構簡單，易于并行化，生成的視差圖精度高并且在滿足實時性的要求下可提高特定區(qū)域的匹配精度[44]；對于弱紋理場景和光照不一致場景也能得到較為精確的視差圖；同時基于Census 立體匹配算法可用于醫(yī)學上外科手術導航、無人車駕駛的路線規(guī)劃及目標勘測，都可快速地找到立體相對的匹配[45]。 但是Census 立體匹配算法也存在一定的局限性，因此改進的Census 立體匹配算法可以使得尋找的立體匹配像對的精度更高。

立體匹配算法的實施要考慮諸多因素，并要以計算的穩(wěn)定性和復雜度等總體性指標來衡量算法的有效性和可行性。因此對于研究Census 立體匹配算法應從系統(tǒng)的角度來分析，未來的發(fā)展趨勢也要在以下幾方面有所側重：

1） Census 立體匹配算法和其它方法的有效融合。 由于立體匹配是一個“病態(tài)”問題，每一種算法在不同的場景都有各自的優(yōu)缺點。 Census 立體匹配算法是基于局部特征進行的立體匹配，缺乏全局信息，因此可將Census 立體匹配算法融合到全局立體匹配算法框架中進行整體改進。

2） 提高Census 立體匹配算法在特征缺乏、紋理重復、遮擋和不連續(xù)區(qū)域的視差圖精度。 由于場景中存在噪聲、紋理重復、無紋理以及視差不連續(xù)等不可抗的因素， 導致匹配過程中容易產生誤差。得到特定區(qū)域的高精度視差圖是Census 立體匹配算法未來的發(fā)展趨勢。

3） 建立實時的、穩(wěn)定的、實用的Census 立體匹配算法[46]。在提高算法的匹配精度的同時，時間復雜度也是必須要考慮的一個因素。 目前大多數(shù)算法都是基于精度的提高對Census 算法進行的改進，因此在確保精度的條件下，減少Census 立體匹配算法代價計算過程中的時間復雜度是未來的發(fā)展趨勢，使得Census 立體匹配算法在實時計算中得到廣泛的應用。

4） Census 立體匹配算法和深度學習算法結合。人工智能算法越來越多的應用于解決立體匹配問題。 最近機器學習的興起和深度學習的迅速普及增強了立體匹配新的發(fā)展趨勢和應用，這在幾年前是不可想象的。 有趣的是，這兩個世界之間的關系是雙向的。 機器學習，尤其是深度學習，推動了立體匹配技術的發(fā)展，而立體匹配技術本身又開創(chuàng)了新的方法。 它們提供了各類求解復雜系統(tǒng)優(yōu)化問題的通用框架，可以此為基礎建立智能化Census 立體匹配算法。

5 結束語

Census 立體匹配算法相對來說匹配精度較高，抗干擾性較強，但是還是具有一定的缺陷。 本文主要綜述了Census 立體匹配算法的缺陷， 歸納了Census 立體匹配算法的改進方向以及對各個改進的算法進行了對比，分析了它們的優(yōu)缺點、各個改進算法的效果圖以及時間復雜度。 雖然立體匹配算法的研究已經經過了很多年，但是Census 立體匹配算法無論是在理論上還是實際應用方面都有一定的局限性。對于Census 立體匹配算法未來主要考慮它的精度和時間復雜度的進一步優(yōu)化。 在提高算法匹配精度的同時，時間復雜度也是必須要考慮的一個因素。