基于降采樣聚類的雙目圖像測距算法研究

李先真，張大波

(遼寧大學 信息學院，遼寧 沈陽110036)

0 引言

據國家統(tǒng)計局分析，中國民用汽車保有量已經突破兩億，智能交通和輔助駕駛技術已經成為目前的研究熱門，而測距是輔助駕駛技術的重要研究分支.現(xiàn)有的測距技術有很多，如：視覺測距、超聲波測距、激光測距、紅外線測距等.與其他測距技術相比，雙目視覺測距具有實現(xiàn)簡單、成本低廉、魯棒性強、獲取信息量大，抗干擾能力強等優(yōu)點，因此成為近年來的熱門研究方向.

雙目視覺測距一般情況按如下步驟進行：攝像機標定、圖像獲取、圖像預處理、立體匹配、獲取視差圖.其中立體匹配的準確度將直接影響視差圖的精確程度，因此成為視覺測距算法中的核心研究課題.自20世紀70年代M IT的Marr提出了完整的雙目視覺體系框架[1]起，立體匹配算法開始系統(tǒng)而高速的發(fā)展.目前的立體匹配算法主要分為兩類：全局立體匹配算法和局部立體匹配算法.

全局立體匹配算法通過運用圖像整體特征，建立全局能量函數(shù)，通過求能量函數(shù)的最小值來尋找最優(yōu)視差值.全局立體匹配算法準確性較高，但是由于圖像一般數(shù)據量較大所以全局算法效率較低.文獻[2]提出了一種基于的動態(tài)規(guī)劃立體匹配算法，減少了全局算法的復雜度并減輕了傳統(tǒng)動態(tài)規(guī)劃算法導致的視差圖條紋現(xiàn)象；文獻[3]提出了一種基于圖像分割的立體匹配算法，可以獲得較為平滑的視差圖；文獻[4]提出了一種基于置信度傳播的立體匹配算法，降低了硬件實現(xiàn)的復雜度.文獻[5]為了提高全局算法的效率將全局算法與局部算法融合，提出了一種基于半全局的立體匹配算法，取得了較好地效果.

局部立體匹配算法是通過局部特征對應或窗口對應的方法來計算匹配代價，通過代價聚合來求出最優(yōu)視差值.由于局部立體匹配算法一般只考慮圖像的局部信息，算法的效率較高，但是在弱紋理或者深度間斷區(qū)域會出現(xiàn)誤匹配現(xiàn)象.文獻[6-7]通過窗口內像素點的顏色特征來計算匹配代價，對光照變化有較好地魯棒性，但是在弱紋理區(qū)域效果不理想；文獻[8-9]通過SIFT算法對圖像的sift描述子進行匹配來計算最優(yōu)視差值，可以較好地保存圖像的幾何特征.

立體匹配算法的速度和精確度的平衡是本文研究的重點，本文提出了一種基于降采樣Census算法的局部立體匹配算法，通過縮小圖像尺寸的方式在盡可能保留視差特征的基礎上極大的提高算法運算速度.適合在對速度要求高，場景空間較大，對細節(jié)測量要求較低的情況下使用，如交通圖像、無人機航拍圖像等.獲取視差圖之后可以通過進一步對尺度縮小的圖像進行處理以提高匹配的準確的，同時不會對效率產生過高的影響，

1 基本原理

雙目視覺體系通過左右攝像機所拍攝圖像中同名像素點(代表相同實際物體的像素點)之間的視差來計算深度.測量原理如圖1所示：

圖1 雙目測距原理示意圖

在理想情況下，兩個攝像機主光軸平行，且成像平面于同一平面上.實際物體P與光心所在距離為Z，l為鏡頭平面即是攝像機成像坐標的XoY面，焦距為f，兩光心之間距離為T，則根據相似性原理有[10]：

其中d＝x1+x2，即左右圖像中同名像素點的視差.因此只要找到圖像中的同名像素點，并求出起視差，即可計算出Z，即物體與攝像機之間距離的值.

因此，雙目視覺測距核心就是立體匹配，立體匹配具體可分為四步：代價計算、代價聚合，視差優(yōu)化、獲取視差圖.本文提出了一種基于降采樣Census算法的局部立體匹配算法，并在代價聚合中采用WTA算法的同時使用Meanshift算法將視差聚類，以獲得更加準確平滑的視差圖.

圖2 算法流程

1.1 降采樣Census算法

通常局部立體匹配算法，受到窗口大小和局部噪聲的影響，在弱紋理區(qū)域和噪聲區(qū)域無匹配現(xiàn)象較為嚴重.常用的窗口對應代價計算算法有：灰度差絕對值之和SAD，灰度差平方之和SSAD、Census算法、歸一化互相關等.

Census算法：傳統(tǒng)Census算法是一種典型的通過窗口內顏色特征來計算匹配代價的算法，Census算法不關心具體灰度值，只考慮窗口內灰度值之間的關系，因此對光照變化不敏感.Census算法首先使用窗口遍歷左右圖像，對每個像素進行編碼，形成Census串.如圖3，A為當前像素點(常用窗口中心點)的灰度值，Ai為A的鄰域窗口q內像素點的灰度值.其中

圖3 Census算法實例

然后通過計算串之間的漢明距離來計算匹配代價，即：

distance＝⊕(Cenl?Cenr)

其中，?代表按位相減，⊕代表按位相加，Cenl和Cenr代表左右圖像的Census串.

傳統(tǒng)Census對光照變化不敏感，匹配較為準確.然而，由于Census算法需要對圖像每一個像素點進行一次編碼，而且為了保證匹配精度掃描窗口不宜過小，導致Census算法速度較慢.因此本文提出了一種基于降采樣[11]的Census算法，可以較好提升算法的運算速度.

使用窗口q(w×w)遍歷圖像，遍歷步長為w，按照Census算法的規(guī)則形成Census串.Census串矩陣計算方法如下

Cen(i，j)＝? ?λ[A(ih，jk)，avg]

其中?代表按位連接，avg代表窗口內像素點灰度平均值，使用窗口內像素點灰度平均值來代替?zhèn)鹘y(tǒng)Census算法中窗口中心的點，以減弱噪聲點的影響[13].

圖4 左圖為傳統(tǒng)Census算法右圖為降采樣Census算法

根據Census算法的原理，編碼過程與代價計算過程獨立，同時編碼對每一個像素點(像素區(qū)域塊)獨立，因此可以通過多線程和邊緣計算的思想進一步提高算法運算速度.本文實驗中是將兩幅圖像的編碼過程并行進行，同時在施加極線約束之后，認為左右匹配點都在極線上，因此獲得一行編碼便可立即進行立體匹配.如此可以將運算速度繼續(xù)提高.但不足之處在于由于匹配代價只在極線上計算，會導致橫條紋現(xiàn)象.

1.2 代價聚合

在代價計算之后，需要確定最佳視差.在全局立體匹配方法中，視差選擇能量函數(shù)取最小時的視差值，因此不需要進行代價聚合.局部立體匹配方法，通常只考慮局部特征，容易受到噪聲和誤匹配影響，單個像素點的視差實用性不高，需要通過代價聚合進一步優(yōu)化視差.

本文使用貪心算法，來進行初步代價聚合.貪心算法選擇匹配代價最小時的視差，同時增加了噪聲容限以減少誤匹配率.其優(yōu)點是實現(xiàn)簡單，計算速度快，但是缺點是局部算法固有的缺點導致精確度下降，對噪聲點處理能力較弱[14].考慮到視差圖像在同一物體內的連續(xù)性和不同物體之間存在較大灰度差，本文使用聚類算法對初步匹配代價進一步處理.

考慮到由于視差圖灰度變化的不確定性，無法提前確定聚類中心，本文使用Meanshift算法來進行聚類[15].Meanshift算法是一個迭代的過程，其核心步驟是不斷更新Meanshift向量：

其中G(x)是一個單位核函數(shù)，w(xi)≥0是一個賦給采樣點xi的權重，本文中取其最簡單的形式，即

算法步驟：

(1)開始迭代，給定初始聚類中心，n為迭代次數(shù)，初值為0，m為聚類中心序號，初值為1，容限誤差為ε，令

(2)計算mh()，把mh()賦值給.

(3)如果‖mh()-‖≥ε，迭代次數(shù)加一，n＝n+1，返回(2).

(4)即為第m個聚類中心，圖像中像素點灰度為f(x)，如果‖f()-f(x)‖＜δ，則將該點標記為m，并令f(x)＝f().

(5)如果圖中還有未標記點，令m＝m+1，從圖像中未標記的像素點中給定新的初始聚類中心，令n＝0，返回(2).

(6)結束迭代.

圖5 左圖為聚類聚類之前效果右圖為聚類后效果

圖5即為初始代價聚合結果，和聚類之后的結果.雖然Meanshift聚類算法較為復雜，但是由于降采樣導致視差圖尺寸極大縮小，聚類算法耗時被大大降低到可以接受的地步.

2 實驗

本文實驗使用使用用來自KITTI數(shù)據庫的實際道路圖像(375×1 250)進行實驗.電腦處理器是i5-7 300 HQ，顯卡是英偉達GTX1050Ti，實驗平臺是MATLAB.Census算法和SAD算法的消耗時間是通過MATLAB單線程操作運行時長獲得的.本文算法的耗時是通過MATLAB單線程并行操作來模擬多線程所消耗的時間.以下表格是幾種常見立體匹配算法效果的對比和時間復雜度分析.公認的立體匹配精確度指標是誤匹配率，其計算公式如下：

其中dc(x，y)是通過匹配計算所得視差，dT(x，y)是真實視差值，δ是允許誤差閾值，N是圖像素總數(shù)，即計算誤差點占全圖點的比例.這里采用無效點(dc(x，y)＝0)和奇異點(在四個方向上dc+1(x，y)-dc(x，y)＞δ)和誤匹配點(｜dc(x，y)-dT(x，y)｜＞δ)作為誤差點來計算誤匹配率.

表1 三種算法匹配精確度和時間復雜度對比

表中算法時間復雜度以比較操作為基準操作，其中M×N代表圖像尺寸，d代表檢索距離.

圖6是使用用來自KITTI數(shù)據庫的實際道路圖像(375×1 250)進行實驗.圖6(a)是使用SAD立體匹配算法獲得的視差圖，圖6(b)是使用Census算法獲得的視差圖，圖6(c)是使用本文算法獲得的視差圖.圖6(d)是原始圖像.每種算法隨機選取三幅圖像作為代表展示實驗效果.

圖6 三種算法使用K ITTI數(shù)據庫圖像匹配效果及原圖

表2 三種算法使用K ITTI數(shù)據庫圖像匹配效果

圖7所示的是三種算法在不同尺度圖像上的運行時間.橫坐標為圖像尺寸(單位：像素像素)，縱坐標為運行時間(單位：s).從圖表中可以看出本文算法在時間效率上遠遠高于其他兩種傳統(tǒng)算法.

圖7 三種算法時間隨圖像尺度變化圖(單位：秒)

3 結論

綜上所述，基于降采樣的Census算法可以極大的提高傳統(tǒng)算法的運算速度，并同時可以提高后續(xù)處理的速度，同時保證一定的的匹配準確率.但是由于圖像尺寸縮小會導致細節(jié)的丟失，因此本算法適用于尺寸較大的空間測距，例如交通道路圖像，而且由于視差圖尺寸較小導致平滑處理對邊緣影響較大，破壞了邊緣的連續(xù)化.后續(xù)將對算法進一步優(yōu)化，尋找更好保持細節(jié)和邊緣的算法.