基于改進的種子點擴展自適應立體匹配算法

李鵬格　戴本祁

(華東理工大學信息科學與工程學院　上海 200237)

?

基于改進的種子點擴展自適應立體匹配算法

李鵬格戴本祁

(華東理工大學信息科學與工程學院上海 200237)

由于在圖像中不同區域的紋理密集程度不同，因此使用固定窗口大小的算法無法兼顧紋理不同的區域，并且在視差不連續區域的匹配精度較低。針對該問題，提出一種自適應窗口和自適應權重相結合的算法，并且采用種子點擴展的方法。首先，通過交叉自適應窗口法，區分出連續點和孤立點，對于不同的分類點采用不同的處理方法。其次，針對每一個像素點，利用改進的自適應權重方法進行匹配。最后，提出一種新的種子點擴展的視差優化方法，對初始視差圖進行精細化。實驗結果表明，視差圖中紋理密集區域和視差不連續區域的誤匹配現象得到改善。該算法可以有效地處理圖像中紋理分布不均的問題，提高了在視差不連續區域內匹配精度。

交叉自適應窗口自適應權重孤立點種子點

0　引　言

立體匹配是通過二維圖像進行三維重構的一個重要環節。立體匹配的目的就是為要從一對左右圖像得到一幅精準的視差圖，但是由于左右視圖中的遮擋問題、光照問題、基線偏移問題等使得在圖像處理的過程中加大了提取視差的難度。根據立體匹配算法的處理范圍不同可以分為全局算法和局部算法，全局算法在長期以來都有著在精度方面的優勢。然而在運算速度方面卻是不盡人意，因此不適于對時間要求比較苛刻的大多數工業環境中的實時處理系統。在局部算法方面，在研究學者們的不斷努力下，該算法在精度上逐漸提高，并且目前一些局部算法的精度已經可以達到全局算法的水平。

局部立體匹配算法包括區域匹配和特征匹配算法[1]。區域匹配算法就是以各個像素點為中心構建或設定相應的一個支撐窗口，利用像素間的顏色約束和距離約束等約束條件，在一定的視差范圍內進行匹配。主要有固定窗口法、滑動窗口法、多窗口法、自適應窗口法、自適應權重AW(Adaptive-Weight)法[2-4]、基于Rank變換的匹配算法[5,6]等。

目前，使用較多并且效果較好的是自適應權重法[2]及其改進算法，它是由Yoon等提出的。對每一個像素點分配一個固定窗口，計算窗口內的各個像素與中心像素間的顏色距離和空間距離，將二者的距離權重相結合，得到整個窗口內各個像素與中心像素的權重，然后結合像素初始距離計算匹配代價，利用WTA(Winner-Takes-All)方法得到密集視差圖。然而，由于其利用固定窗的方法使得該方法存在一些固有的缺陷，如在稀疏紋理區域和視差不連續區域的匹配精度低。

為此，后來的研究者基于該方法提出了一些改進算法，如Tombari等[7]提出在分割區域的權重為1，其他區域的權重為AW算法中聯合權重，這種方法使得在稀疏紋理區域的匹配精度得到有效的提高。Hosni等[8]利用通透性的原理，提出測地距離立體匹配的方法，將除去那些與中心像素不連續卻擁有較高權值的像素的影響，在紋理稀疏區域更好地提高了匹配精度。但是由于Hosni等采用通透性原理，在高紋理的區域內像素的連續區域通常較小，導致其匹配區域減小而出現誤匹配的現象。

為提高在紋理程度不同的區域的兼顧性，本文提出一種基于改進的交叉自適應增長的圖像分割方法，并在各個分割區域內，利用各個像素與中心像素之間的空間距離和色度距離來確定其不同的相關權值。該算法有效地提高了整體圖像的匹配精度，并且針對視差圖中易出現誤匹配的孤立像素點，提出一種改進的種子點擴展算法，即根據鄰近視差有效種子點[9]擴展的方法，使視差精度進一步得到提高。

1　自適應匹配算法

在局部立體匹配算法中，為了得到精確的匹配結果，選擇一個合適的窗口是很重要的。原則上來說，這個窗口應該包括所有具有相同視差的相鄰的像素點，但是每個像素的視差值是不可預知的。由于在鄰近區域內具有相似的色度的像素點一般都是在同一視差區域內，因此假設在一定閾值內的鄰近像素點有相同的視差，即視差相似性假設。

本文算法流程如圖1所示。圖1中自適應匹配階段，首先利用改進的自適應交叉分割算法，得到各個左右圖中各個像素點的分割區域，并記錄像素點為孤立點或者連續點；其次計算各個分割區域內的像素點對中心點的權重；最后得到聯合匹配代價。

圖1　本文匹配算法框圖

1.1交叉自適應分割

(1)

式中pi=(xp-i,yp)，L是設定的臂長搜索范圍。δ(p,pi)是像素p1和p2之間顏色相似度的測量函數如下[10]：

(2)

式中Ic是顏色通道c上的強度值，τ是設定的限定相似度程度的閾值，文獻[10]中取20。由此可以得到點p的上下左右的臂長，即可得到點p的分割區域。

該分割算法中利用p點的垂直擴展臂，進行水平方向的擴展，可以得到p點的分割區域，但是這樣只考慮了圖像的水平方向的通透性，忽略了垂直方向的通透性，降低了匹配的精度。由于該算法利用圖像的通透性，在低紋理區域可以得到較高的匹配精度，但是在高紋理區域，由于每個像素點的分割區域都較小，致使出現較高的誤匹配現象，為此本文提出了解決該問題的方法。

對文獻[8]中提出的交叉自適應分割方法進行補充和改進，不僅考慮到圖像水平方向上的通透性，也利用圖像垂直方向上的通透性。利用式(1)搜索到像素點p的上下左右臂長，再分別以p點上下臂和左右臂上的像素點作為基準點，分別進行左右和上下的擴展，兩者結合一起可得到像素點p的支撐窗口W。如圖2所示：其中(a)是以p點的垂直方向臂長上的像素點作為基準點，進行水平方向的擴展；(b)是以p點的水平方向臂長上的像素點作為基準點，進行垂直方向的擴展；(c)是聯合(a)、(b)分割區域后的p點的支撐區域。這樣擴展可以充分利用像素之間的相似性，得到更大的分割窗口，并且能包含所有與中心像素相似的像素點，實驗證明也更加合理有效。

圖2　支撐區域擴展圖

1.2自適應權重算法

在一幅圖像中，除了邊緣點之外，每一個像素點與其周圍的像素點都有一定的相似性，并且隨著像素距離的邊遠，其相似度通常情況下也在逐漸變小。根據顏色約束和距離約束條件，Yoon和Kweon提出了自適應權重的算法。

在該算法中其像素距離fg(p,q)的計算是通過下面公式[2]得到的：

(3)

其中，Δgpq為任意像素點p、q點之間的歐氏距離，μg為聯合權重中像素距離的權重。

由于其使用指數函數，其不足點在于，對于在低紋理區域的像素點，中心像素點與周圍的鄰近像素點具有較高的相似性。但是該函數下降速度快，只有在3×3鄰域內的像素才具有較大的權重值，雖然有顏色權值作為補充，該算法在低紋理或無紋理區域匹配精度依然較低。

式(3)無法充分滿足顏色相似的像素點要分配相同的權重的要求。本文利用下面公式[11]進行改進，可以滿足在一定的范圍內具有較高顏色相似性的像素點分配相同的權重的要求。

fg(p,q)=((1+exp(-a(Δipq+b)))-1-

(1+exp(-a(Δipq-b)))-1)×

((1+exp(-a(Δjpq+b)))-1-

(1+exp(-a(Δjpq-b)))-1)

(4)

式中，參數a可以設置像素距離的權值函數的下降速度，a越大下降速度越快；參數b可以改變函數的中心區域權值變化緩慢的區域塊，b越大中心區域越大；Δipq、Δjpq分別表示像素點(p,q)的水平和垂直坐標距離。

1.3代價聚合

在代價聚合階段，結合自適應分割算法和自適應權重算法計算匹配代價。在自適應分割時得到的分割區域內，利用自適應權重算法，可以排除那些與中心像素點不在同一紋理區域內的像素點，并且擴大在低紋理區域像素點的分割區域。因此，可以提高低紋理區域的匹配精度，其聚合匹配代價如下式：

(5)

其中fs(p,q)、fs(pd,qd)分別是左圖和右圖中p和pd點的支撐窗口；Spq為d在Rd范圍內搜索時左右支撐窗口的聯合窗口；Ns為聯合窗口的大小，即窗口內的像素數目；w(p,q)、w(pd,qd)分別為p和pd對應的支撐窗口內的權重；e(q,qd)為p和pd的支撐窗口內對應像素點的初始匹配代價值。

在Rd={dmin,…,dmax}范圍內，進行視差搜索，利用WTA算法[2]得到最優視差：

(6)

2　視差優化

2.1種子點選取

如本文算法圖1所示，在得到初始視差圖后，對視差圖進行優化。首先，在初始視差圖中選出準確度高的種子點[9]；然后，將孤立點，也就是由于支撐窗口小而可能引起誤匹配的像素點，標記出來，在其支撐窗口內搜索到與其鄰近的種子點，將種子點的視差值賦給該孤立點。

種子點的選取條件如下：

(1)DL(i,j)=DR(i,j-(DL(i,j)))

(2)C((i,j),DL(i,j))×γ

式中，DL(i,j)表示左視差圖中(i,j)點的視差值，DR(i,j-(DL(i,j)))表示對應于(i,j)點的視差值在右圖中的視差值，C((i,j)、DL(i,j))表示左視差圖中(i,j)點視差值為DL(i,j)時的代價值。條件(1)要求種子點的視差值滿足左右一致性(Left-Rightcheck,LRC)，條件(2)確保該點的可信度，設定的閾值γ可以改變種子點的可信度，本文中選取γ=1.1，γ越大，種子點的可信度越高，但是種子點數也會相應的減少。

2.2孤立點標記及優化

在自適應分割時，若得到像素點p(i,j)的支撐窗口內的像素點總數小于θ，或者其半邊界小于θ/2，則標記P點為孤立點。根據產生孤立點的條件不同，可分為左邊界孤立點、右邊界孤立點和全孤立點。此時，對于每一個孤立點進行視差優化。

對于全孤立點，在其支撐區域內，所包含的所有種子點的視差值的均值即為P點的視差值；對于左邊界孤立點，即該孤立點的左邊靠近邊界，根據視差相似性假設，即假設該點的視差與在其右邊的像素點的視差相似，則在其支撐區域內，選取其右半部分的種子點的視差值的均值作為其視差值；同理，對右邊界孤立點，選取其左半部分的種子點的視差值的均值作為其視差值。表示為：

(7)

其中，Np為p點的支撐區域，qA表示在p支撐區域內的種子點，d(p)表示p像素點的視差值，Sp表示p點的分割區域，Sp-left、Sp-right分別表示p點的分割區域內的左右半部分。

由于這些孤立點雖然其分割區域較小，但是其初始視差值不一定就不準確，因此，在視差優化階段，從得到的孤立點圖中除去那些本身是種子點的孤立點，只對非種子點的孤立點進行視差優化。然而由于部分遮擋點被誤認為是種子點的情況會出現較大的誤匹配率，因此，根據左右一致性檢測，通過左右視差圖得到遮擋點圖，對其中遮擋點而非孤立點的像素點進行視差優化，直接取其11×11窗口內的種子點均值。

3　實驗結果

實驗測試中使用Middlebury數據庫[12]中的標準圖像進行測試，實驗中各個參數的設置如表1所示。

表1　參數對照表

其中，θ閾值的選取是根據L值得大小，即窗口的大小。當L=19時，窗口的大小為39×39，其中包含的像素點數為1521個，當某個像素點的分割區域內像素點個數少于整個窗口的大約三分之一時，標記為孤立點。當閾值過小時，孤立點過少，無法有效地優化誤匹配點的視差；反之，孤立點過多，使一些非誤匹配點的視差被更改，反而降低了匹配率。

3.1種子點擴展實驗結果

在圖3中，下圖的兩列分別為Tsukuba圖和Cones圖，第一行為得到的種子點圖，高亮度部分為種子點，黑色點為非種子點；第二行為待優化的孤立點圖，通過2.2節部分的方法得到孤立點圖，將其中視差值滿足種子點要求的點去除，再將根據左右視差圖得到的遮擋圖部分考慮進去，可得到該孤立點圖，高亮度區域表示孤立點；第三行為初始左視差圖，第四行為種子點擴展后的左視差圖。

從圖3(a)、(b)中可以看出種子點一般出現在紋理稀疏并且視差連續的區域，而孤立點主要出現在紋理密集區域，包括視差不連續區域。

對比圖3(a)、(b)，本文的孤立點選取方法可以提取出圖像中的誤匹配點；對比圖3(c)、(d)，本文提出的種子點擴展方法可以有效地消除孤立點的誤匹配現象。從圖中用橢圓形標記出來的區域可以看出，在Tsukuba圖中的臺燈左側的前景腫大現象得到優化，并且在頭像的左上方的白色區域被消除；在Cones圖像中效果明顯，各個模型的左邊黑塊大幅減少。

圖3　種子點擴展過程

3.2實驗結果對比分析

根據表1參數對文獻2以及本文的算法進行測試，結果如圖4所示。其中各列的圖依次為Tsukuba、Teddy、Cones和Venus。由圖中結果可以看出，除去遮擋區域的少量誤匹配現象，改進的算法在其他區域整體均有所提高。

在圖4(b)中使用自適應權重的算法，在圖4(c)圖中利用自適應分割的方法。由于其在使用自適應分割時，最大臂長的設置與圖4(b)中的固定窗口的相等，因此在視差不連續區域使得匹配窗口小于圖4(b)中相應的匹配窗口，匹配結果提高不明顯。但是在該過程中可以得到種子點和孤立點，再考慮到視差優化階段的種子點擴展，可得到圖4(d)，即本文算法，可以看出通過優化使得匹配效果得到較大提高。

對比圖4(b)、(c)，在(b)的結果中Tsukuba圖中的背景區域中出現被橢圓形標記的白塊，以及在Teddy圖中的用橢圓形標記的區域，也都在加上自適應分割窗口之后，得到有效的改善。對比圖4(b)、(d)，在文獻[2]的結果中，Venus圖中有出現用橢圓形標記的白色區域，在Cones圖中出現用橢圓形標記的黑色區域，都在改進算法中被消除。

圖4　立體匹配原圖及視差結果圖

在Tsukuba圖和Venus圖中的標記區域出現在低紋理區域，在只考慮權重的情況下，由于附近視差的相似性，導致出現誤差。但在考慮自適應分割和種子點擴展之后可以彌補這種誤差。在Teddy圖和Cones圖中的標記區域出現在紋理不連續區域，在該區域利用孤立點的特性進行擴展，可以消除大量誤匹配的像素點。

在實驗結果圖4中可以看出文獻[2]的Venus中的背景邊緣線模糊不清。但在本文的算法結果中邊界明顯，這是由于在邊緣附近的像素點易出現誤匹配現象，并且誤匹配的視差值都是由于背景引起的，而本文提出的種子點擴展法，可以有效提高邊緣附近像素點的匹配精度。然而在Teddy圖的處理上出現了誤匹配塊現象，無法消除，主要是由于該區域紋理太過相近，而在進行圖像分割時，是有最大窗口限制的分割，致使該區域出現誤匹配。

圖4的(c)、(d)實驗得出的非遮擋區域錯誤率(nonocc)、總體錯誤率(all)和視差不連續區域錯誤率數據(disc)如表2所示。在文獻[10]中只是利用自適應分割的水平方向擴展進行立體匹配，因此當圖像中含有大量垂直邊界的時候，無法保證匹配的準確性，而在本文算法中同時考慮到垂直方向上的擴展，可以使匹配率得到提高。不僅如此，本文還結合種子點擴展的方法，將像素點分類為孤立點和連續點，利用種子點對孤立點進行水平方向擴展，進行視差優化，使匹配率進一步得到提高。

表2　算法結果的誤匹配率比較(error>1)

根據表2對誤匹配率的分析，文獻[10]的總平均誤匹配率為7.60%，本文算法的總平均誤匹配率為6.72%，減小了0.88%。實驗結果也顯示在Tsukuba、Venus和Teddy圖中的誤匹配率都有所改善，分別減少了0.35%、0.07%、0.65%，并且由于在Cones圖中的孤立點大部分為左右邊界點，因此Cones圖的誤匹配率提高最為明顯，分別為1.68%、4.15%、1.48%。因此，本文算法可以降低立體匹配過程中的誤匹配率，尤其在水平不連續區域內，可以大幅提高匹配率。

4　結　語

本文在交叉分割和自適應權重的立體匹配算法的基礎上，提出一種改進的分割算法和自適應權重算法。通過實驗表明，該方法有效地解決了自適應權重算法中在視差不連續區域匹配精度低的問題。雖然在計算效率上比較文獻[2]有所降低，但是通過并行計算的方法依然可以大大提高計算速度。本文在視差優化階段提出種子點擴展的算法，實驗結果顯示，在紋理密集區域匹配精度得到了顯著的提高，彌補了文獻[2]在該區域內匹配精度低的問題。

但是本文也存在一些有待提高的地方，如在Teddy圖的實驗數據中，all和disc區域的誤匹配率優化較小，究其原因，是本文算法在進行孤立點的選取時只標記其左右的邊界特性。而Teddy圖里面又含有較大部分的上下邊界點，如圖中的煙囪部分，因此可以通過考慮其上下邊界特性，使其匹配精度進一步提高。

[1]YangL,WangR,GeP,etal.Researchonarea-matchingalgorithmbasedonfeature-matchingconstraints[C]//2009FifthInternationalConferenceonNaturalComputation,Tianjin,August14-16,2009,Piscataway:IEEEPress,2009:208-213.

[2]YoonKJ,KweonIS.Adaptivesupport-weightapproachforcorrespondencesearch[J].IEEETransactionsOnPatternAnalysisandMachineIntelligence,2006,28(4):650-656.

[3]ChengF,ZhangH,YuanD,etal.Stereomatchingbyusingtheglobaledgeconstraint[J].Neurocomputing,2014,131(7):217-226.

[4]HuW,ZhangK,SunL,etal.Virtualsupportwindowforadaptive-weightstereomatching[C]//VisualCommunicationsandImageProcessing,2011IEEE,2011:1-4.

[5]IrijantiE,NayanMY,YusoffMZ.Localstereomatchingalgorithm:Usingsmall-colorcensusandsparseadaptivesupportweight[C]//NationalPostgraduateConference,KualaLumpur,September19-20,2011.Piscataway:IEEEPress,2011:1-5.

[6] 郭龍源,盧阿麗,楊靜宇.非參量變換在彩色圖像立體匹配中的應用研究[J].計算機科學,2008,35(11):217-219.

[7]TombariF,Mattoccia1S,StefanoLD.Segmentation-basedadaptivesupportforaccuratestereocorrespondence[C]//ProceedingsofAdvancesinImageandVideoTechnology,SecondPacificRimSymposium,Santiago,December17-19,2007.Berlin:Springer,2007:427-438.

[8]HosniA,BleyerM,GelautzM,etal.Localstereomatchingusinggeodesicsupportweights[C]//ImageProcessing,2009 16thIEEEInternationalConference,Cairo,November7-10,2009.Piscataway:IEEEPress,2009:2069-2072.

[9]SunX,MeiX,JiaoS,etal.Stereomatchingwithreliabledisparitypropagation[C]//3DImaging,Modeling,Processing,VisualizationandTransmission,2011InternationalConference,Hangzhou,May16-19,2011.Piscataway:IEEEPress,2011:132-139.

[10]ZhangK,LuJ,LafruitG.Cross-basedlocalstereomatchingusingorthogonalintegralimages[J].IEEETransactionsOnCircuitsandSystemsForVideoTechnology,2009,19(7):1073-1079.

[11] 王富治,黃大貴.改進的YOON自適應加權立體匹配算法[J].電子測量與儀器學報,2010,24(7):632-637.

[12]ScharsteinD,SzeliskiR.Ataxonomyandevaluationofdensetwo-framestereocorrespondencealgorithms[J].InternationalJournalofComputerVision,2002,47(1-3):7-42.

ADAPTIVESTEREOMATCHINGALGORITHMBASEDONIMPROVEDSEEDPOINTSEXPANSION

LiPenggeDaiBenqi

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Sincetheimageindifferentregionshasdifferenttextureintensity,thereforethealgorithmusingasize-fixedwindowcan’ttakeintoaccounttheregionswithdifferenttextures,anditsmatchingprecisionislowindisparitydiscontinuitiesregions.Tosolvetheseproblems,inthispaperweproposeanewalgorithmwhichcombinesadaptivewindowandadaptiveweight,andusesthemeansofseedpointexpansion.First,wedistinguishtheconsecutivepointsandisolatedpointswithcross-adaptivewindowmethod,andusedifferentprocessingapproachesfordifferentclassificationpoints.Secondly,foreachpixelpointweusetheimprovedadaptiveweightmethodtomatchit.Finally,wepresentanewdisparityoptimisationapproachofseedpointsexpansiontorefinetherawdisparitymap.Experimentalresultsshowthatthephenomenonofmismatchingthetextureintensityregionanddisparitydiscontinuitiesregionindisparitymaphasbeenimproved.Thealgorithmcaneffectivelyprocesstheproblemofuneventexturedistributioninimage,andraisethematchingprecisionindisparitydiscontinuitiesregion.

Cross-adaptivewindowAdaptiveweightIsolatedpointSeedpoint

2014-09-06。李鵬格，碩士生，主研領域：立體匹配。戴本祁，副教授。

TP391

ADOI:10.3969/j.issn.1000-386x.2016.03.050