基于SIFT的寬基線立體影像密集匹配

楊化超,姚國(guó)標(biāo),王永波

1.國(guó)土環(huán)境與災(zāi)害監(jiān)測(cè)國(guó)家測(cè)繪局重點(diǎn)實(shí)驗(yàn)室,江蘇 徐州 221116;2.中國(guó)礦業(yè)大學(xué) 環(huán)境與測(cè)繪學(xué)院,江蘇 徐州221116

基于SIFT的寬基線立體影像密集匹配

楊化超1,2,姚國(guó)標(biāo)2,王永波1,2

1.國(guó)土環(huán)境與災(zāi)害監(jiān)測(cè)國(guó)家測(cè)繪局重點(diǎn)實(shí)驗(yàn)室,江蘇 徐州 221116;2.中國(guó)礦業(yè)大學(xué) 環(huán)境與測(cè)繪學(xué)院,江蘇 徐州221116

提出基于對(duì)極幾何和單應(yīng)映射雙重約束及SIFT特征的寬基線立體影像多階段準(zhǔn)密集匹配算法。算法包括三個(gè)階段:①基于特征點(diǎn)的空間分布和信息熵選取一定數(shù)量的最優(yōu)SIFT特征點(diǎn)集并進(jìn)行最小二乘初始稀疏匹配及立體像對(duì)的基本矩陣和單應(yīng)矩陣估計(jì);②對(duì)于其余特征,利用同名核線傾斜角及SIFT特征的尺度信息對(duì)匹配窗口的仿射變換參數(shù)進(jìn)行迭代優(yōu)化及變形改正、提取仿射不變SIFT特征描述符,并基于雙重約束信息及歐氏距離測(cè)度進(jìn)行匹配;③考慮寬基線立體影像較低的特征提取重復(fù)率,對(duì)第②步左右影像中未能成功匹配的特征點(diǎn),基于雙向搜索策略,采用基于盒濾波加速計(jì)算的SSD測(cè)度在變形改正后的雙重約束區(qū)域中進(jìn)行匹配,并對(duì)匹配結(jié)果進(jìn)行加權(quán)最小二乘擬合定位。實(shí)際的寬基線立體影像試驗(yàn)結(jié)果證明了算法的有效性,可為后續(xù)的三維重建提供較為可靠的密集或準(zhǔn)密集匹配點(diǎn)。

尺度不變特征變換;準(zhǔn)密集匹配;仿射不變;單應(yīng)映射

1 前 言

三維重建,即從二維圖像恢復(fù)三維物體可見(jiàn)表面的幾何結(jié)構(gòu)的過(guò)程,一直是數(shù)字?jǐn)z影測(cè)量與計(jì)算機(jī)視覺(jué)的重要研究?jī)?nèi)容。其主要涉及影像匹配得到同名像點(diǎn)及在物方空間對(duì)表面進(jìn)行三維重建兩大核心技術(shù)[1]。目前的三維重建技術(shù)已相對(duì)較為成熟,因而問(wèn)題的關(guān)鍵在于如何快速得到稠密或至少是準(zhǔn)稠密(quasi-dense)的匹配點(diǎn)。為此,數(shù)字?jǐn)z影測(cè)量與計(jì)算機(jī)視覺(jué)領(lǐng)域的廣大研究人員對(duì)立體影像匹配問(wèn)題進(jìn)行了大量的科學(xué)研究,出現(xiàn)了許多具有較高參考價(jià)值的理論研究成果[1-11]。然而目前大多數(shù)性能較優(yōu)的同名點(diǎn)密集匹配算法多是針對(duì)短基線攝影條件的[1-5],即匹配時(shí)多直接在影像上取矩形窗口,采用基于區(qū)域(area-based)的或基于特征(feature-based)的匹配方法完成相似性判斷。而對(duì)于存在較大幾何變形的寬基線影像而言,此種直接匹配方法的可靠性將大為降低?，F(xiàn)有的寬基線立體匹配研究的基本思路是:利用仿射變換近似圖像局部區(qū)域之間的對(duì)應(yīng)關(guān)系并進(jìn)行仿射變形改正,然后在幾何變形改正后的鄰域上完成相似性判斷并進(jìn)行迭代匹配傳播(match propagation)。此外,在匹配傳播前,還需首先獲得若干初始稀疏匹配。如:文獻(xiàn)[6]選用 Hessian-Affine[7]、文獻(xiàn)[8]則綜合選用Hessian-Affine及MSER[7]實(shí)現(xiàn)初始稀疏種子匹配并基于二階梯度矩及主方位估計(jì)來(lái)恢復(fù)其對(duì)應(yīng)鄰域的仿射關(guān)系;而在匹配傳播階段,上述算法均在初始種子匹配估計(jì)得到的核線幾何約束下來(lái)更新新匹配點(diǎn)對(duì)應(yīng)鄰域的仿射關(guān)系并進(jìn)行幾何變形改正,然后在視差梯度、置信度等約束下,采用基于NCC(normalized cross correlation)測(cè)度的區(qū)域匹配及全局“最優(yōu)最先”(best first)的策略進(jìn)行逐像素(pixel-to-pixel)的匹配傳播。所不同的是,文獻(xiàn)[6]使用一種代表局部形狀的二階強(qiáng)度矩、而文獻(xiàn)[8]則通過(guò)鄰域3參數(shù)仿射參數(shù)傳遞的方式來(lái)獲得新匹配點(diǎn)對(duì)應(yīng)鄰域的仿射關(guān)系。文獻(xiàn)[9]的方法則通過(guò)人工選取特征點(diǎn)對(duì)整幅圖像進(jìn)行校正,以簡(jiǎn)化匹配傳播點(diǎn)對(duì)應(yīng)鄰域仿射參數(shù)的求取,但卻使得算法的實(shí)用性受到限制。文獻(xiàn)[10]和[11]分別研究了基于 Harris和尺度不變特征變換(scale invariant feature transformation, SIFT)算法的寬基線立體影像最小二乘匹配算法。上述算法總體上存在著計(jì)算復(fù)雜度高且可靠性不足的缺陷。如計(jì)算機(jī)視覺(jué)界的準(zhǔn)密集匹配方法多采用仿射不變區(qū)域特征的重心作為稀疏匹配點(diǎn),精度無(wú)法保障,而以此估計(jì)的核線也是粗略的,對(duì)后續(xù)匹配傳播的約束缺乏精確性。此外,該類方法中基于逐像素的匹配傳播策略計(jì)算復(fù)雜度較高。而基于Harris和SIFT特征點(diǎn)的最小二乘匹配方法涉及較多的平差迭代參數(shù),計(jì)算復(fù)雜度亦較高且難以獲得可靠的密集匹配點(diǎn)。

SIFT算法主要包括尺度空間極值點(diǎn)檢測(cè)、特征點(diǎn)主方位確定、特征描述符生成及特征匹配四個(gè)主要步驟[12]。SIFT特征是圖像的局部特征,具有多量性、獨(dú)特性(distinctiveness)好和信息量豐富的特點(diǎn),且其對(duì)旋轉(zhuǎn)、尺度縮放、亮度變換保持不變性,對(duì)視點(diǎn)變化、仿射變換、圖像噪聲等也保持一定程度的不變性。SIFT算法的上述特點(diǎn)使得其在寬基線立體影像匹配中得到了廣泛應(yīng)用的研究和應(yīng)用。然而:①SIFT特征描述符不具完全的仿射不變性;②寬基線立體影像特征提取的重復(fù)率(repeatability rate)較低。上述兩個(gè)因素極大地影響了SIFT特征匹配的數(shù)量和準(zhǔn)確率,難以獲得可靠的密集匹配,不利于后續(xù)的三維重建。綜合考慮上述因素,并充分利用SIFT特征檢測(cè)結(jié)果的多量性特點(diǎn),提出基于對(duì)極幾何和單應(yīng)映射雙重約束及SIFT特征的寬基線立體影像多階段密集匹配算法,并選取實(shí)際的寬基線立體影像對(duì)算法進(jìn)行試驗(yàn)。

2 算 法

算法整體流程如圖1所示,主要包括如下三個(gè)階段:①基于空間分布和信息熵優(yōu)選部分較優(yōu)的SIFT特征點(diǎn)并進(jìn)行最小二乘初始稀疏匹配及基本矩陣和單應(yīng)矩陣估計(jì)[13-14];②對(duì)于其余特征,利用同名核線傾斜角及SIFT特征的尺度信息對(duì)匹配窗口進(jìn)行仿射迭代優(yōu)化及改正、提取仿射不變SIFT特征描述符,并基于雙重約束信息及歐氏距離測(cè)度進(jìn)行匹配;③考慮到寬基線立體影像較低的特征提取重復(fù)率,對(duì)未能成功匹配的特征點(diǎn),采用基于鄰域參數(shù)自適應(yīng)傳播及基于盒濾波(box filter)[15]快速計(jì)算的 SSD(sum of squared difference)測(cè)度[10]進(jìn)行雙向約束搜索匹配,并對(duì)匹配結(jié)果進(jìn)行加權(quán)最小二乘曲面擬合定位。算法各階段的匹配策略和方法詳細(xì)介紹如下。

2.1 第一階段匹配

SIFT特征點(diǎn)包含三類信息:位置(x)、所處尺度(σ)和方向(θ)。如圖2,十字絲代表特征點(diǎn)所處位置,圓的半徑代表其所處尺度,而矩形虛線框代表SIFT特征描述符的提取窗口,箭頭代表方位。不失一般性,現(xiàn)假設(shè) m1(xm1,σm1,θm1)和m2(xm2,σm2,θm2)為立體像對(duì) I1、I2中檢測(cè)到的一對(duì)同名SIFT特征點(diǎn)。并設(shè)σm1≥σm2,s=(σm1/ σm2),θ=(θm1-θm2)。以同名特征點(diǎn) m1、m2為坐標(biāo)原點(diǎn)的兩個(gè)相關(guān)窗口記為W1、W2,大小為(2w+ 1)×(2w+1)。記 m2的鄰域窗口坐標(biāo) x=[x y]T∈[-w w],x2= [x2y2]T為 x按式(2)進(jìn)行仿射變換后的坐標(biāo)。則W1、W2窗口表達(dá)為

上式中的A可用式(2)表達(dá)。

圖1 算法流程Fig.1 Flow chart of the proposed algorithm

圖2 SIFT特征檢測(cè)與描述示意圖Fig.2 Illustrated figure of SIFT detection and description

式中,sx、sy為x、y兩個(gè)方向上的縮放因子;δ為特征點(diǎn)相關(guān)窗口相對(duì)旋轉(zhuǎn)角度。由于 m1和 m2為同名像點(diǎn),有如下關(guān)系式成立

式中,h0、h1為影像窗口之間的線性灰度畸變參數(shù);n1(x2,y2)、n2(x,y)為影像的隨機(jī)噪聲。上式線性化后可得最小二乘匹配的誤差方程式,誤差方程式及其各項(xiàng)系數(shù)以及求解過(guò)程詳見(jiàn)文獻(xiàn)[16]。

最小二乘影像匹配需要良好的待求參數(shù)初始值,基于SIFT特征的尺度和方位信息,并考慮到方位確定的誤差(由SIFT算法的特征點(diǎn)方向確定的計(jì)算過(guò)程可知,特征點(diǎn)方向確定本身存在較大的偏差,一般在15°以內(nèi)),待求參數(shù)初始值按下式確定

考慮到計(jì)算速度及基本矩陣 F和單應(yīng)矩陣H估計(jì)的可靠性,算法通過(guò)多層次空間分布約束和尺度空間信息熵度量來(lái)優(yōu)選部分SIFT特征進(jìn)行最小二乘匹配[11]。最小二乘匹配結(jié)束后,利用高精度的稀疏匹配結(jié)果采用隨機(jī)采樣一致性算法來(lái)計(jì)算 F和 H[13]并記錄該階段匹配特征點(diǎn)間的比例因子s和最優(yōu)的k值kopm,以用于后續(xù)兩個(gè)匹配階段的尺度參數(shù)傳遞。

2.2 第二階段匹配

為提高計(jì)算速度,第二階段采用忽略平移向量的4參數(shù)仿射變換模型。

如圖3,m1和m2的同名核線方程分別記為

易得同名核線的傾斜角分別為

圖3 匹配窗口仿射變形改正Fig.3 Affine rectified for matching window

圖3中以m2為中心的矩形窗口W2首先旋轉(zhuǎn)α-β角度得到窗口區(qū)域U2,則此時(shí)以m1為中心的鄰域窗口U1與U2間僅存尺度變換關(guān)系。進(jìn)一步考慮尺度變形因素,則圖3和式(1)中的A表達(dá)為

第一階段匹配已獲得了較為精確的核線幾何關(guān)系,因此,在第二階段匹配時(shí)將核線的傾斜角視作定值。由此,式(4)僅需尺度變形因子sx、sy需要確定。在變形改正后的窗口中提取SIFT特征描述符并基于歐氏距離計(jì)算相似性測(cè)度,選擇相似性測(cè)度最小者對(duì)應(yīng)的k值即可按式(4)和式(5)確定最優(yōu)仿射參數(shù)并同時(shí)確定匹配點(diǎn)。記錄該階段匹配特征點(diǎn)間的比例因子 s和最優(yōu)的 k值kopm,以用于第三階段匹配時(shí)的尺度參數(shù)傳遞。

2.3 第三階段匹配

第二階段未能正確匹配的SIFT特征,多數(shù)是由于寬基線立體影像較低的特征提取重復(fù)率引起的。有鑒于此,算法對(duì)第二階段未能正確匹配的特征點(diǎn)進(jìn)行雙向約束匹配,并采用如下策略和方法:

(1)鄰域窗口尺度參數(shù)自適應(yīng)迭代優(yōu)化。雙向匹配是以立體像對(duì)中其中一張影像中檢測(cè)的特征點(diǎn)為基礎(chǔ),而在另一張影像中基于多信息約束進(jìn)行窮舉搜索匹配,因而式(4)中的s無(wú)法根據(jù)SIFT特征的尺度信息直接確定?？紤]到上述兩個(gè)階段的匹配已經(jīng)獲得了一定數(shù)量的匹配點(diǎn),因而,尺度參數(shù)可根據(jù)已匹配點(diǎn)間的尺度信息確定。采用如下自適應(yīng)策略:首先找到與待匹配點(diǎn)距離最近的已匹配點(diǎn),設(shè)最近距離為D,給定閾值DT,如D大于DT,則需首先按式(6)定義的SSD匹配測(cè)度優(yōu)化式(4)中的尺度比例因子s;繼而再優(yōu)化sy;如D小于DT,則直接按式(4)優(yōu)化sy,且在優(yōu)化sy時(shí),僅需在已匹配特征點(diǎn)的 kopm的較小鄰域內(nèi)進(jìn)行。上述自適應(yīng)策略保證了鄰域尺度參數(shù)傳遞的速度和準(zhǔn)確性。

(2)基于盒濾波技術(shù)快速計(jì)算的SSD匹配。第三階段匹配需在約束的鄰域范圍內(nèi)進(jìn)行窮舉搜索,匹配運(yùn)算較為耗時(shí)。為此,算法采用如下策略:現(xiàn)假設(shè)右影像 I2中的特征點(diǎn) m2在左影像 I1中的核線為l1,雙重約束搜索區(qū)域?yàn)閳D4中右圖陰影部分(記為Ω1),首先對(duì)Ω1的中心m按上述第(1)步的方法進(jìn)行仿射參數(shù)優(yōu)化,根據(jù)優(yōu)化結(jié)果對(duì)Ω1進(jìn)行幾何變形改正,在改正后的鄰域Ω2中采用基于盒濾波快速計(jì)算的SSD匹配測(cè)度進(jìn)行相似性搜索。采用盒濾波技術(shù)在計(jì)算窗口匹配代價(jià)時(shí)充分利用了前一個(gè)像素的累積結(jié)果,消除了冗余計(jì)算,其計(jì)算一個(gè)后續(xù)窗口的差異和,只需計(jì)算4個(gè)點(diǎn)。

圖4 雙重約束區(qū)域仿射變形改正Fig.4 Affine rectified for dual constraint region

如僅基于核線幾何約束,則可沿核線兩側(cè)鄰域進(jìn)行分段校正,再采用快速的SSD匹配算法。

(3)匹配點(diǎn)加權(quán)擬合定位。在匹配點(diǎn)的3×3鄰域窗口內(nèi),依匹配測(cè)度進(jìn)行加權(quán)多項(xiàng)式擬合,以其極值點(diǎn)的位置作為最佳匹配點(diǎn)。考慮如下多項(xiàng)式

式中,f(x,y)=1/CSSD(x,y)。為突出窗口中心像素的重要性,對(duì)窗口各像素采用高斯距離加權(quán),即

采用最小二乘法擬合二次多項(xiàng)式后,極大值點(diǎn)的位置(xmax,ymax)可按下式求出

3 試驗(yàn)與分析

3.1 試驗(yàn)數(shù)據(jù)及評(píng)價(jià)指標(biāo)

選取實(shí)際的具有不同紋理類型的兩寬基線立體影像序列,分別是 Graffiti Sequences和 Wall Sequences(http:∥www.robots.ox.ac.uk/～vgg/data/data-aff.html)的前4幅影像(分別記作img1、img2、img3及img4)。Graffiti和Wall序列立體影像間存在不同程度的仿射變形。各序列影像之間的單應(yīng)矩陣 H0已知。利用已知的單應(yīng)矩陣按式(10)將待匹配影像投影到參考影像,以投影誤差作為同名點(diǎn)匹配定位精度的評(píng)價(jià)指標(biāo),并對(duì)其設(shè)一閾值ε0,如投影誤差小于ε0,則認(rèn)為該對(duì)點(diǎn)是匹配的。以下的試驗(yàn)中取ε0=3.0像素。

3.2 試驗(yàn)結(jié)果與分析

在 Microsoft XP操作系統(tǒng)下基于 Visual C++6.0及OpenCV(開(kāi)放計(jì)算機(jī)視覺(jué)函數(shù)庫(kù))集成開(kāi)發(fā)環(huán)境編寫(xiě)了算法試驗(yàn)程序。相關(guān)試驗(yàn)結(jié)果如下:①圖5和圖6分別給出了兩立體影像序列中各像對(duì)各階段基于雙重幾何約束時(shí)及僅基于核線幾何約束時(shí)的正確匹配對(duì)數(shù)(第一階段未施加約束);②表1列出了兩影像序列中視點(diǎn)變化為40°的img1-img4立體像對(duì)各階段的正確匹配/總匹配數(shù)量(n1/n2)和匹配正確率(p%);③表2給出了兩立體影像序列中各像對(duì)LSM-SIFT算法與本文算法的匹配定位誤差(e= [ε ε]/n ,ε按式(10)計(jì)算,n為總匹配點(diǎn)數(shù)量)對(duì)比;④圖7和圖8分別給出了兩影像序列中img1-img4立體像對(duì)的最終匹配結(jié)果圖及文獻(xiàn)[11]LSM-SIFT算法的匹配結(jié)果,圖7(a)和圖8(a)的局部放大圖中(相對(duì)圖像原始分辨率放大2倍)紅色標(biāo)記點(diǎn)為本文算法第一階段的匹配點(diǎn),白色為第二階段的匹配點(diǎn),而綠色和黃色點(diǎn)分別為第三階段中從左至右和從右至左的匹配點(diǎn)。經(jīng)檢驗(yàn),圖7(a)局部放大圖中除藍(lán)色圓標(biāo)出的點(diǎn)外,其余的白色點(diǎn)和紅色點(diǎn)是LSM-SIFT算法的匹配點(diǎn);而圖8(a)局部放大圖中的白色點(diǎn)和紅色點(diǎn)均是LSM-SIFT算法的匹配點(diǎn)。

圖5 兩立體影像序列中各像對(duì)各階段基于雙重幾何約束時(shí)的正確匹配點(diǎn)數(shù)量Fig.5 Correct matching number of each stage for every pairs from two stereo image sequences with dual geometric constraints

圖6 兩立體影像序列中各像對(duì)各階段僅基于核線幾何約束時(shí)的正確匹配點(diǎn)數(shù)量Fig.6 Correct matching number of each stage for every pairs from two stereo image sequences with epipolar constraint only

表1 兩立體影像序列中img1-img4像對(duì)各階段的匹配結(jié)果Tab.1 Matching results of each stage for img1-img4 pairs from two stereo image sequences

表2 兩序列立體影像各像對(duì)不同算法的匹配定位誤差對(duì)比Tab.2 Comparison of matching errors using different algorithms for each pairs from two stereo image sequences 像素

圖7 Graffiti Sequences(img1-img4)的匹配結(jié)果Fig.7 Matching results for Graffiti Sequences(img1-img4)

圖8 Wall Sequences(img1-img4)的匹配結(jié)果Fig.8 Matching results for Wall Sequences(img1-img4)

綜合上述試驗(yàn)結(jié)果,分析如下:

(1)充分顧及寬基線立體影像特征提取的重復(fù)率,通過(guò)第三階段的雙向匹配策略可顯著提高匹配點(diǎn)的數(shù)量。如對(duì)存在較大仿射變形的Graffiti和Wall Sequences中的img1-img4立體像對(duì),通過(guò)第三階段的匹配,使匹配點(diǎn)的數(shù)量分別增加了1 452和2 816個(gè)(表 1及圖 5)。又如,圖 5(b)Wall Sequences中的立體像對(duì)img1-img2(視點(diǎn)變化為20°),左右影像初始檢測(cè)的特征點(diǎn)數(shù)分別為5 361個(gè)和6 419個(gè),但最終正確匹配點(diǎn)的數(shù)量為8 446個(gè)。由此可見(jiàn),本文算法使得寬基線立體影像的匹配性能不再受特征提取重復(fù)率的限制,使SIFT的冗余特征變得不再“冗余”,并可利用其獲得較好的密集或準(zhǔn)密集匹配結(jié)果。

(2)文獻(xiàn)[11]業(yè)已證明,LSM-SIFT算法在正確匹配點(diǎn)的數(shù)量和匹配定位精度方面優(yōu)于現(xiàn)有的基于 SIFT的特征匹配方法。但圖7(b)和圖8(b)表明,該方法難以獲得密集匹配,尤其是對(duì)具有大量結(jié)構(gòu)和紋理信息的 Graffiti立體影像對(duì),主要原因在于LSM-SIFT算法對(duì)寬基線立體影像特征點(diǎn)較大的提取和定位誤差較為敏感。如圖7(a)局部放大圖中藍(lán)色圓標(biāo)出的一對(duì)點(diǎn),其定位誤差為2.43像素,則LSM-SIFT算法未能取得成功匹配。本文算法除第一階段外,第二階段采用了對(duì)特征點(diǎn)定位誤差具有一定抗差性的SIFT特征匹配方法,第三階段匹配則充分考慮了寬基線立體影像較低的特征提取重復(fù)率的影響而采用雙向雙重約束搜索策略,從而顯著提高了匹配點(diǎn)的數(shù)量。此外,雖然本文方法的匹配定位精度同LSM-SIFT算法相比有較大差距(表2),但對(duì)于匹配難度較大的寬基線立體影像及大多數(shù)3維重建任務(wù)而言,匹配點(diǎn)的數(shù)量要比匹配精度重要得多。另一方面,基于NCC的LSM-SIFT算法迭代運(yùn)算涉及的平差參數(shù)較多,而且,由于寬基線立體影像變形較大,平差參數(shù)的初始值難以精確給定,導(dǎo)致迭代收斂時(shí)間較慢。而本文方法僅僅優(yōu)選部分特征點(diǎn)進(jìn)行最小二乘匹配(第一階段),而在第二、第三階段分別采用運(yùn)算速度較快的SIFT特征描述符和快速的SSD算法,試驗(yàn)結(jié)果表明本文方法的匹配時(shí)間要低于LSM-SIFT算法。如圖7(a)和圖7(b)的匹配耗時(shí)分別為118.7 s和147.6 s。

(3)對(duì)比圖5和圖6可知,如僅基于核線幾何約束,匹配點(diǎn)的數(shù)量會(huì)有較大幅度的下降。如Graffiti和 Wall Sequences中視點(diǎn)變化為40°的img1-img4立體像對(duì)基于雙重約束和僅基于核線約束的總匹配點(diǎn)數(shù)量分別為(1 762,1 087)和(3 515,2 235)。但從匹配點(diǎn)的絕對(duì)數(shù)量來(lái)看,仍可獲得密集至少是準(zhǔn)密集的匹配點(diǎn)(限于篇幅,匹配結(jié)果圖像不再給出)。

4 結(jié) 論

本文充分利用SIFT特征檢測(cè)結(jié)果的密集性特點(diǎn),并同時(shí)考慮到寬基線立體影像的仿射幾何變形、匹配約束條件及最終匹配點(diǎn)的數(shù)量要求,有針對(duì)性地將密集匹配算法劃分為三個(gè)階段,并對(duì)三個(gè)不同的匹配階段采用不同的匹配策略和方法,以提高匹配的準(zhǔn)確性和計(jì)算速度。試驗(yàn)結(jié)果表明本文算法可顯著提高匹配點(diǎn)的數(shù)量和匹配準(zhǔn)確率,獲得較為可靠的密集匹配點(diǎn),有利于后續(xù)的攝影測(cè)量三維重建。需要指出的是,全局單應(yīng)約束僅適合平面或近平面場(chǎng)景。因此下一步的研究重點(diǎn)是借助仿射不變區(qū)域特征(如Harris-Affine及MSER等)對(duì)非平面場(chǎng)景進(jìn)行單應(yīng)面估計(jì)和劃分,在多個(gè)單應(yīng)面內(nèi)采用本文算法進(jìn)行匹配,而對(duì)于非單應(yīng)面內(nèi)的點(diǎn),則采用核線幾何約束及拓?fù)鋷缀侮P(guān)系進(jìn)行匹配,通過(guò)上述策略擴(kuò)展本文算法的適用范圍。

[1] YUAN Xiuxiao,MING Yang.A Novel Method of Multiimage Matching Using Image and Space Synthesis Information[J].Acta Geodaetica et Cartographica Sinica,2009,38 (3):216-222.(袁修孝,明洋.一種綜合利用像方和物方信息的多影像匹配方法[J].測(cè)繪學(xué)報(bào),2009,38(3):216-222.)

[2] ZHU Qing,WU Bo,ZHAO Jie.Propagation Strategies for Stereo Image Matching Based on the Dynamic Triangle Constraint[J]. ISPRS Journal ofPhotogrammetry & Remote Sensing,2007,62(4):295-308.

[3] HUA Shungang,ZENG Lingyi.Dense Matching Algorithm Based on Corner Detection[J].Computer Engineering and Design,2007,28(5):1092-1095.(華順剛,曾令宜.一種基于角點(diǎn)檢測(cè)的圖像密集匹配算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(5):1092-1095.)

[4] TANG Liang,WU Chengke,CHEN Zezhi.Image Dense MatchingBasedon Region Growth with Adaptive Window[J]. Pattern Recognition Letters,2002,23(10):1169-1178.

[5] L HUILLIER M,QUAN L.A Quasi-dense Approach to Surface Reconstruction from Uncalibrated Images[J]. IEEE Transactions on Pattern Analysisand Machine Intelligence,2005,27(3):418-433.

[6] KANNALA J,BRANDT S.Quasi-dense Wide Baseline Matching Using Match Propagation[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis:IEEE,2007.

[7] MIKOLAJCZYK K,TU YTELAARS T,SCHMID C.A Comparison of Affine Region Detectors[J].International Journal of Computer Vision,2005,60(1):163-186.

[8] XU Zhenhui,ZHANG Feng,SUN Fengmei,et al.Quasidense Matching by Neighborhood Transfer for Fish-eye Images[J].Acta Automatica Sinica,2009,35(9):1159-1167. (許振輝,張峰,孫鳳梅,等.基于鄰域傳遞的魚(yú)眼圖像的準(zhǔn)稠密匹配[J].自動(dòng)化學(xué)報(bào),2009,35(9):1159-1167.)

[9] MEGYESI Z,KOS G,CHETVERIKOV D.Surface Normal Aided Dense Reconstruction from Images[C]∥Proceedings of Computer Vision Winter Workshop.Telc: [s.n.],2006.

[10] DENG Baosong,SONG Hanchen,YANG Bing.Feature Point Matching Based on Affine Iterative Model[J]. Journal of Image and Graphic,2007,12(4):678-683.(鄧寶松,宋漢辰,楊冰.基于仿射迭代模型的特征點(diǎn)匹配算法[J].中國(guó)圖象圖形學(xué)報(bào),2007,12(4):678-683.)

[11] YAN G Huachao,ZHAN G Shubi,ZHAN G Qiuzhao. LeastSquaresMatching Methods forWide Base-line Stereo Images Based on SIFT Features[J].Acta Geodaetica et Cartographica Sinica,2010,39(2):187-194.(楊化超,張書(shū)畢,張秋昭.基于SIFT的寬基線立體影像最小二乘匹配方法[J].測(cè)繪學(xué)報(bào),2010,39(2):187-194.)

[12] LOWE D.Distinctive Image Features from Scale-invariant Keypoints[J].International Journal of Computer Vision, 2004,60(2):91-110.

[13] LIANG Dong,TONG Qiang,QU Lei,et al.Algorithm for Images Matching Based on Epipolar and Homography Constraints[J].Journal of System Simulation,2006,18(1): 44-46.(梁棟,童強(qiáng),屈磊,等.一種基于極幾何和單應(yīng)約束的圖像匹配算法[J].系統(tǒng)仿真學(xué)報(bào),2006,18(1): 44-46.)

[14] HARTLEY R I,ZISSERMAN A.Multiple View Geometry in Computer Vision[M].Cambridge:Cambridge University Press,2003.

[15] WANG Xin,MA Yan,YANG Jian,et al.Implementation and Improvement ofArea-based Stereo Matching Algorithm[J].Optics and Precision Engineering,2008, 16(10):2002-2008.(王昕,馬巖,楊劍,等.區(qū)域立體匹配算法的實(shí)現(xiàn)與改進(jìn)[J].光學(xué)精密工程,2008,16(10): 2002-2008.)

[16] ZHANGJianqing,PAN Li,WANG Shugen.The Photogrammetry[M].Wuhan:Wuhan University Press,2003. (張劍清,潘勵(lì),王樹(shù)根.攝影測(cè)量學(xué)[M].武漢:武漢大學(xué)出版社,2003.)

Dense Matching for Wide Base-line Stereo Images Based on SIFT

Y ANG Huachao1,2,Y AO Guobiao2,WANG Yongbo1,2
1.Key Laboratory for Land Environment&Disaster Monitoring of SBSM,Xuzhou 221116,China;2.School of Environmental& Spatial Informatics,China University of Mining&Technology,Xuzhou 221116,China

A novel multi-stage quasi-dense matching algorithm for wide base-line stereo images is introduced based on SIFT and dual constraints of epipolar geometry and homographic mapping.The proposed algorithm includes following three stages:①The optimal SIFTfeatures with good spatial distribution and large information content are first selected,and matched by using the least squares matching method,then the fundamental and homographic matrix can be estimated by using these initial sparse correspondences with higher precision;②For the other SIFT features,the affine transformation parameters between matching windows are iteratively optimized by using the slope angle of correspondent epipolar lines and scale information of SIFT features,and affine invariant feature descriptors are extracted from the corrected matching windows,then correspondences can be determined by Euclid distance and dual constraint information;③Considering the lower repeatability rate of feature detection for wide base-line stereo images,for the unmatched points extracted from left and right images of stereo pairs,matching can be carried out by adopting two-way search strategy from left to right image or from right to left image based on the rapid SSD similarity cost function and affine rectified dual constraints region,and the least squares curve surface fitting weighted by Gaussian-distance algorithm is adopted to improve the precision of matching results. Test results using practical wide base-line image pairs indicate the proposed algorithm is effective and can provide reliable dense or quasi-dense matching points for subsequent 3D reconstruction.

scale invariant feature transformation;quasi-dense matching;affine invariant;homographic mapping

Y ANG Huachao(1977—),male,Post PhD, associate professor,majors in digital photogrammetry and remote sensing images processing.

1001-1595(2011)05-0537-07

P237

A

國(guó)家自然科學(xué)基金(41001312;41001297;61072094)

(責(zé)任編輯:雷秀麗)

2010-10-11

2011-01-17

楊化超(1977—),男,博士后,副教授,主要研究方向?yàn)閿?shù)字?jǐn)z影測(cè)量、遙感圖像處理。

E-mail:yanghc3344@yahoo.com.cn