基于強相似點檢測快速雙目立體匹配算法

馬龍，孫銘澤，黃超，裴昕，周航，張鴻燕

中國民航大學中歐航空工程師學院，天津300300

基于強相似點檢測快速雙目立體匹配算法

馬龍，孫銘澤，黃超，裴昕，周航，張鴻燕

中國民航大學中歐航空工程師學院，天津300300

1 引言

近年來實時準確地獲取移動機器人工作空間的三維信息成為機器人視覺導航、障礙物檢測與環境地圖構建中的一個研究熱點，其匹配速度對于視覺導航，特別是在障礙物檢測技術的實際應用中起著重要的作用[1]。

立體匹配作為計算機視覺的一個重要方向，是通過多視點圖像還原出物體深度信息的主要手段[2]。目前，根據匹配不同的基元，立體匹配主要分為特征點匹配與區域特征匹配[3]。兩者各具優勢與不足。其中Andrej Satnik等人[4]通過將不同特征描述方法進行比對，并優化了立體匹配方法，但基于特征點的立體匹配方法仍然難以得到稠密的視差圖[5]。而根據文獻[6]，基于基元的立體匹配方法根據最優化理論方法的不同，分為全局與局部立體匹配方法。全局匹配方法是指通過構造全局能量函數，并通過該函數得到全局最優解的方法得到最優視差，其包括圖割（graph cuts）[7]、信念傳播（belief propagation）[8]等。雖然全局方法能夠得到精度很好的結果，但受限于復雜的建模過程，需要大量計算時間，即使較快的情況下也需要幾十秒的計算時間。從文獻[9]可以看出，雖然近年來全局方法得到進一步發展，但其速度仍然難以滿足實時性要求。局部匹配方法[10]通過采用固定形狀和大小的支撐窗口計算匹配代價，再將其聚合得到視差，根據不同的匹配代價函數，其包括灰度匹配灰度絕對值和（Sum of Absolute Differences）[11]、灰度平方差和（Sum of squared Differences）[12]、自適應權重（Adapt Weight）[10]與歸一化互相關（Normalized Cross Correlation）[13]等局部方法。雖然相比于全局方法在精度上有所犧牲，但是在速度上卻有較大提高。由于SAD代價函數計算簡單，近年來在機器人導航、障礙物檢測等實時立體匹配的領域內得到了廣泛應用[14]。

基于以上問題，本文提出了一種基于強相似點的快速雙目立體匹配算法。首先對采集圖像進行對極化處理；其次，將圖像進行灰度轉化，并選取與待匹配點相似高的點作為強相似點，在強相似點的集合內計算最優視差；最后將得到整個視差圖進行視差修正與濾波，保證視差的精度，得到最終視差。利用標準數據集與實際室內場景進行了實驗驗證，驗證了本文算法的有效性。

2 雙目視覺系統

如圖1所示，雙目立體視覺成像的模型一般為兩個并排放置的攝像頭。其中Ol與Or分別為左右相機光心，兩個光心之間距離為T,P為真實空間中一點，它成像在左右兩相機的坐標分別為Pl(xl,yl)和Pr(xr,yr)。

圖1 雙目視覺模型

若兩相機嚴格水平并排放置，則目標的深度與在兩圖像上的視差成反比，視差定義為d=xl-xr。根據三角相似原理，深度為：

然而實際情況下兩相機很難做到嚴格平行放置，所以需要在進行立體匹配前對圖像進行極線校正，進行極線校正之后的圖像不但易于計算目標深度，還減少了立體匹配的計算量，提高了系統速度。圖片校正后結果如圖2。

圖2 極線校正結果

從圖2中可以看出，經過極線校正后，左圖像上任一點在右圖像上的匹配點一定在同一條水平線上。除此之外，校正會將相機畸變的影響進行消除，從而造成了如左圖上方的黑區出現。

3 算法原理

3.1 強相似點定義

在許多研究中，關于基于特征點的視差求解一直難以得出稠密視差，而基于局部窗口的求解方式需要在整個搜索空間上進行計算，導致計算量較大[10]。強相似點指的是與待匹配點相似度強的點，并且在該待匹配點對應的視差搜索空間內。為了進一步加快速度，本文直接通過待匹配點與其對應視差搜索范圍內的點的灰度值差的絕對值作為相似度評價函數。當兩點灰度值小于閾值時，即定義為強相似點。如式（2）所示，其中fL(x,y)與fR(x,y)分別表示點(x,y)在左右圖的灰度值，δ表示設定閾值。

若在該點對應的匹配區域內不存在強相似點，則以每次增加定量增大閾值δ，直至出現強相似點或者到達迭代上限。其中最大迭代次數為5次，定量增量為初始閾值的20%。隨著增量幅度的增大，強相似點與原點的相似度越低，會導致匹配效果下降，但與此同時由于能夠提取到更多的強相似點因而能夠減少立體匹配中相似度函數的計算量，減少運算時間。若到達最大迭代次數依然沒能出現強相似點，則將所有在匹配區域內的點都作為該點的強相似點，也就是正常計算所得待匹配的點。與傳統的特征點不同，強相似點的計算更加簡單，而且計算區域也明顯小于特征點提取。因此與特征點提取相比，其計算量更小，且計算速度更快。

雖然在不同場景情況下光照強度不同，但是由于雙目相機間距較小，左右相機采集圖像差異較小，導致不同場景下對選取相同閾值的匹配效果影響有限。同時閾值的選取更多是考慮到匹配的效果與速度，并通過實驗結果與分析，閾值取10的情況能夠在不同場景下均具有較好的適應性。

3.2 基于強相似點的快速匹配

本文通過局部匹配窗口的方式進行視差求解，相比較于全局匹配局部匹配具有速度快的優勢，同時能生成特征點匹配方式不具備的稠密視差圖。如圖3所示，區域匹配通常為以左圖像中待匹配點p為中心，選擇一個區域，以此區域中的灰度信息來表征該匹配點的性征，同時在右圖像中以任意一個對應的待匹配的點q為中心選取同樣大小的區域，對兩個區域的相似測度進行計算，此時若相似測度函數能夠取得極值，兩個區域就被稱為相互匹配。

圖3 局部匹配窗口

雖然SAD減少計算量的同時會對匹配的質量造成影響，但是其在速度上的提高要遠遠優于SSD與ASW。因此為了簡化計算量，增加算法速度，從而滿足整個算法在實時性上的性能，本文選取了Sum of Absolute Differences（SAD）匹配代價作為相似測度函數，其計算公式如下所示：

其中IL(X,Y)為左圖像在(X,Y)位置上的灰度值，同理IR(X,Y)為右圖像該點的灰度值。本文算法僅對待匹配點的強相似點的區域進行相似測度計算，并取其中數值最小的點進行計算得出視差。由于大部分的待匹配點的強相似點的數量要遠小于視差搜索范圍，因此減少了相似測度函數的計算區域，而立體匹配中大部分的時間是用來進行區域匹配的相似度函數計算，因此本方法能夠有效地減少視差的計算時間。

3.3 視差修正與濾波

在得到基于強相似點的立體匹配結果之后，算法又通過遮擋點檢測與平滑濾波進一步修正視差結果，使得在速度得到提高的同時，保證了匹配的精度。

遮擋點檢測就是以右圖像參考點為基準，在左圖像中搜索匹配點，則其在左圖像上得到的匹配點應該與右圖像參考點一致。設d(i,j)和d′(i,j)分別為從右向左和從左向右匹配計算得到的視差，對于計算出的匹配點應當滿足：

不滿足則不是匹配點，即為遮擋點。在經過左右遮擋點檢測得到遮擋點位置之后，需要對遮擋點進行過濾。對于遮擋點p，分別找到p點左方向與右方向的第一個非遮擋點，即為pl與pr。即點p的視差值為：

在進行遮擋點檢測與處理之后，算法還對圖像進行平滑濾波，去除遮擋過濾可能產生的水平條紋。濾波前后圖像如圖4、圖5所示。在圖中可以看到，圖片右區域的橫線減少，同時屋頂區域也得到了改善。最后通過與數據集標準視差圖對比，得出平滑濾波會將誤差再降低1%左右。

圖4 平滑濾波前視差圖

圖5 平滑濾波后視差圖

4 實驗結果與分析

4.1 Middlebury數據集結果及分析

為了驗證本文算法的性能，在實驗中使用來自Middlebury大學立體視覺網站的圖像集和實驗室室內實際環境的立體圖像進行測試和對比分析。實驗所用計算機配置：實驗環境為Inter?CoreTMi7-4500U CPU 1.80 GHz，Windows 7 64位操作系統，算法程序在Visual Studio 2013環境設計完成。

其中標準數據集實驗中分別采用SAD匹配算法、Sum of Squared Differences（SSD）匹配算法、ASW匹配算法和本文算法進行實驗比較驗證。其中Adapt Size Weight（ASW）算法精度較高，用于進行準確度的對比。而本文算法中閾值δ設定為10，SAD窗口選擇為7。方便起見本文圖像只給出Teddy數據集中右圖像實驗圖像結果。Teddy數據集實驗結果如圖6所示。其中圖6（a）～6（d）分別表示原始SAD、SSD、ASW與本文方法的匹配代價計算結果，而圖6（e）與6（f）則表示標準視差與原始圖像用來比較匹配結果的好壞。

從圖6（a）和圖6（d）可看出，本文算法相對于SAD區域算法，計算得到視差精度較高，較好地解決了遮擋區域的視差問題，不但精確地再現了布偶、玩具房子與畫布的輪廓，還對輪廓邊緣區域得到了比較可信的結果。但是由圖6（c）和圖6（d）可知，本文算法仍然存在一些匹配效果欠佳的區域，主要原因是在屋頂區域的紋理信息不夠豐富，而在物體邊緣處本文算法依然要由優于ASW算法。對于不同數據集精度比較如表1所示。

表1 本文算法與其他算法誤差率比較%

表1中分別表示了不同數據集下每種算法計算出視差圖的誤差率（百分比）。從表1和圖6不難看出，與SAD、SSD相比，本文匹配效果得到改善，與ASW算法相比精度接近在某些情況下，甚至性能優于ASW算法。

圖6 Teddy數據集實驗結果

而在表2中可以看出，SAD雖然精度較低，但是具有明顯的速度優勢，與速度較快的SSD方法相比，SAD精度相差2%左右，速度卻提高2倍，而與精度較高的ASW方法相比，雖然精度相差5%，但是在速度上SAD提高超過100倍。本文算法與傳統SAD算法相比，速度提高約為三倍，因此能夠滿足在對速度要求高的實時匹配場景下的應用。

表2 本文算法與其他算法運算時間比較s

4.2 室內環境實驗結果及分析

本文還在是室內環境下進行實測。在實驗過程中，通過自主設計的雙目視覺平臺作為實驗平臺。該雙目攝像頭的設計與應用目標為安裝在室內無人機上，向無人機平臺提供視覺數據，進而計算獲取深度等信息。

圖7 室內實驗結果

首先采集一組圖像進行極線校正，再將校正后圖像通過本文算法進行立體匹配，其中閾值為大小為10，最高迭代次數為5，最后得出視差結果。實驗中首先將本文方法與常在實時雙目系統使用的優化SAD進行比對。雖然與本文方法都選取相同的SAD匹配代價函數進行匹配代價計算，但對比算法為了滿足實時性的要求而犧牲了匹配的質量，本文則通過強匹配點進行匹配精度的增強，并通過遮擋點的檢測與處理進一步優化了匹配的質量。因此從圖7（c）與圖7（d）的對比中可以看出，本文算法相比較于優化SAD算法，本文獲得的視差圖更加完整，而且細節的還原也更高。同時如圖7（e）～圖7（j）所示，本文還將系統在室內環境下不同場景進行了實驗，其中不同場景具有不同光照強度與光照分布情況，實驗結果表明本文方法能夠在室內環境下滿足立體匹配質量與環境適應性上的要求。

同時由于雙目視覺平臺采集圖像的分辨率為640×480，比標準數據集的分辨率更低，也因此具有更快的計算速度，但是由于實物圖具有對圖像的校正，去畸變等處理，導致整體時間略有增加，依然可控制在0.9 s左右，能夠滿足旋翼飛行器的實時性要求。

5 結束語

本文提出了一種基于強相似點的快速匹配算法。在不損壞精確度的情況下，大大增加了匹配的速度，提高了匹配效率。加速與遮擋點處理，保證了系統的檢測的速度與準確性。實驗表明，所述算法相比于速度較快的SAD算法，能夠提高近三倍匹配速度，同時精度提高3%。又通過實驗驗證了本文算法的實際價值，為立體匹配算法在視覺導航、障礙物檢測等方面的應用奠定了良好基礎。

[1] 王軍華，李丁，劉盛鵬.基于改進RANSAC的消防機器人雙目障礙檢測[J].計算機工程與應用，2017，53（2）：236-240.

[2] Watanabe Y，Calise A，Johnson E.Vision-based obstacle avoidance for UAVs[C]//AIAA Guidance，Navigation and Control Conference and Exhibit.South Carolina：American Institute of Aeronautics and Astronautics Press，2007：20-23.

[3] Hirschmuller H.Stereo processing by semiglobal matching and mutual information[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2008，30（2）：328-341.

[4] Satnik A，Hudec R，Kamencay P，et al.A comparison of key-point descriptors for the stereo matching algorithm[C]//Radioelektronika，2016：292-295.

[5] 賀利樂，路二偉，李趙興，等.基于ORB算子的快速立體匹配算法[J].計算機工程與應用，2017，53（1）：190-194.

[6] Hong G S，Kim B G.A local stereo matching algorithm based on weighted guided image filtering for improving the generation of depth range images[J].Displays，2017，49：80-87.

[7] Rother C，Kolmogorov V，Blake A.GrabCut：Interactive foreground extraction using iterated graph cuts[J].ACM Transactions on Graphics，2004，23（3）：309-314.

[8] Sun J，Shum H Y，Zheng N N.Stereo matching using belief propagation[C]//European Conference on Computer Vision.Berlin Heidelberg：Springer，2002：510-524.

[9] Cao G，Peng H.Graph cut stereo matching based on region consistency[J].Journal of Northwestern Polytechnical University，2017，35（1）：160-163.

[10] Huang D.Improved Yoon stereo matching algorithm based on adaptive weight[J].Journal of Electronic Measurement&Instrument，2010，24（7）：632-637.

[11] Tabssum T，Charles P，Patil A V.Evaluation of disparity map computed using local stereo parametric and nonparametric methods[C]//International Conference on Automatic Control and Dynamic Optimization Techniques，2017：104-109.

[12] Song Y.A computational optimization method of the SSD and NCC algorithms of the stereo matching[J].Computer Engineering&Applications，2006，42（2）：42-44.

[13] Chen D，Ardabilian M，Wang X，et al.An improved nonlocalcostaggregationmethodforstereomatching based on color and boundary cue[C]//IEEE International Conference on Multimedia and Expo，2013：1-6.

[14] Zhu S，Gao R，Li Z.Stereo matching algorithm with guided filter and modified dynamic programming[J].Multimedia Tools&Applications，2017，76：1-18.

MA Long,SUN Mingze,HUANG Chao,et al.Fast binocular stereo matching algorithm based on strong similarity detection.Computer Engineering andApplications,2018,54（6）：193-197.

MALong,SUN Mingze,HUANG Chao,PEI Xin,ZHOU Hang,ZHANG Hongyan

Sino-European Institute ofAviation Engineering,CivilAviation University of China,Tianjin 300300,China

Stereo matching is an important branch of binocular vision,which can reduce the three-dimensional information through the depth map,but because of its huge amount of computation,real-time is difficult to be guaranteed.In this paper,a fast stereo matching algorithm based on strong similarity is proposed.Firstly,the binocular image is processed by the pole,so that the matching region is fixed on the same horizontal line,and the matching region is reduced.Secondly,the image is gray,and the points in the search range which are close to the gray value of the matching points are defined as strong similarities.The matching cost of the strong similarity points is calculated and the optimal parallax is obtained.Point for normal parallax calculation,the final parallax correction and filtering,get the final parallax.The results show that the proposed method can improve the accuracy of SAD by 70%without compromising the accuracy rate,which provides a good foundation for the practical application of stereo matching algorithm.In the visual navigation,obstacle detection also has a good application prospects.

binocular vision;epipolar rectification;stereo matching;strong similarities;matching cost

立體匹配是雙目視覺的一個重要分支領域，能夠通過深度圖還原出三維信息，但由于其計算量龐大，實時性難以得到保障。為此，提出了一種基于強相似點的快速立體匹配算法。首先，將雙目圖像通過對極處理，使匹配區域固定在同一水平線上，減少匹配區域；其次，對圖像進行灰度轉化，并將搜索范圍內與待匹配點灰度值接近的點定義為強相似點，對強相似點所在塊進行匹配代價計算，并得出該點最優視差，對不存在強相似點的待匹配點進行正常視差計算；最后將進行視差修正與濾波，得到最終視差圖。經Middlebury算法測試平臺的提供數據進行驗證，結果表明在不損失精確率的前提下，該方法相對于SAD速度提高70%左右，為立體匹配算法的實際應用奠定了良好基礎，在視覺導航、障礙物檢測方面也有著良好的應用前景。

雙目視覺；極線校正；立體匹配；強相似點；相似代價

2017-08-25

2017-10-13

1002-8331（2018）06-0193-05

A

TP242.6；TP301.6

10.3778/j.issn.1002-8331.1708-0313

國家自然科學基金委員會與中國民用航空局聯合資助（No.U1633101）；中央高校基本科研業務費中國民航大學專項（No.3122015Z003）。

馬龍（1983—），男，博士，講師，主要從事精密測量，光學無損檢測和導航信息融合等方面的研究，E-mail：malong9904@aliyun.com；孫銘澤（1993—），男，碩士研究生，主要從事雙目視覺與導航方面的研究。