陳占軍 王耀武 龔詠喜

(哈爾濱工業(yè)大學(xué)(深圳)建筑學(xué)院 廣東 深圳 518055)(哈爾濱工業(yè)大學(xué)(深圳)深圳市城市規(guī)劃與決策仿真重點(diǎn)實(shí)驗(yàn)室 廣東 深圳 518055)

0 引 言

圖像特征匹配是計(jì)算機(jī)視覺領(lǐng)域的一個(gè)重要研究方向，對(duì)于立體視覺[1-2]、三維重建[3-4]、物體識(shí)別[5]以及圖像配準(zhǔn)[6]等研究和應(yīng)用都具有重要意義。從圖像匹配技術(shù)的發(fā)展過程來看，由于應(yīng)用領(lǐng)域和具體圖像的特點(diǎn)和技術(shù)要求的不同，因此，不存在一種圖像匹配算法能解決所有匹配問題。對(duì)于一些室外的建筑物場景的圖像來說，由于建筑本身的表面紋理是單一而重復(fù)的，會(huì)導(dǎo)致匹配多義性即錯(cuò)誤匹配問題；由于不同視角差的建筑物圖像的基線較寬，會(huì)帶來圖像畸變和深度不連續(xù)問題。因此，上述問題給圖像匹配提出了新的要求和挑戰(zhàn)。我們需要在傳統(tǒng)的圖像匹配算法基礎(chǔ)上加以改進(jìn)，減少匹配錯(cuò)誤率并得到數(shù)量更多、更準(zhǔn)確的特征匹配點(diǎn)。

傳統(tǒng)的特征提取和匹配算法，如SIFT[7]，Hessian-Affine[8]、Harris角點(diǎn)[9]、MSER[10]等匹配方法在建筑物圖像上只能提取和得到數(shù)量較少的正確特征匹配點(diǎn)即稀疏匹配，通過這些稀疏匹配結(jié)果，可以恢復(fù)攝像機(jī)的相機(jī)姿態(tài)，但遠(yuǎn)遠(yuǎn)不夠恢復(fù)出建筑物完整的、全視角的三維空間結(jié)構(gòu)。為了重建較準(zhǔn)確且視覺效果較好的建筑物的三維結(jié)構(gòu)，需要得到稠密匹配，至少是準(zhǔn)稠密匹配結(jié)果。

稠密匹配算法[11]先獲取稀疏的初始種子匹配，再用結(jié)構(gòu)化方法、體元方法以及跨尺度圖像濾波方法[12]等計(jì)算出稠密視差圖和立體匹配，獲得數(shù)量巨大的稠密匹配結(jié)果。這種方法的局限是計(jì)算復(fù)雜度高且對(duì)硬件要求也較高，有些算法要求圖像是短基線或者先經(jīng)過校正。

準(zhǔn)稠密匹配方法[13]先通過尺度不變的Harris角點(diǎn)獲取初始種子匹配點(diǎn)，再通過一定的匹配擴(kuò)散規(guī)則如余弦距離測度和最優(yōu)最先擴(kuò)散策略，獲取數(shù)量較多且分布較均勻的匹配點(diǎn)。其中匹配擴(kuò)散這一步是計(jì)算機(jī)視覺的一個(gè)重要問題和關(guān)鍵環(huán)節(jié)，其正確性、數(shù)量及魯棒性直接影響到圖像的其他處理，如三維重建和圖像配準(zhǔn)的效果。準(zhǔn)稠密匹配既克服了稀疏匹配方法的匹配點(diǎn)數(shù)量不足，又克服了稠密匹配方法的效率低及對(duì)運(yùn)算條件要求高的缺點(diǎn)，是適用性比較廣的一種匹配方法。

最有代表性的準(zhǔn)稠密匹配方法是由Maxime L和Quan L[14-15]提出的。該算法過程是：先獲取初始種子匹配點(diǎn)，通過局部和全局幾何約束，采用ZNCC[14]為匹配點(diǎn)打分，每次取出最優(yōu)的種子匹配點(diǎn)，在其鄰域窗口內(nèi)進(jìn)行擴(kuò)散來獲取更多新匹配點(diǎn)，最終得到準(zhǔn)稠密匹配結(jié)果。Kannala等[16]提出了針對(duì)寬基線圖像的匹配擴(kuò)散方法：檢測特征點(diǎn)并進(jìn)行匹配得到初始種子匹配點(diǎn)后，針對(duì)每對(duì)種子匹配點(diǎn)的鄰域窗口，用一個(gè)仿射變換來近似，計(jì)算仿射變換矩陣，利用該矩陣對(duì)鄰域窗口進(jìn)行規(guī)范化，通過ZNCC確定種子匹配點(diǎn)的優(yōu)先序列，再依次在種子點(diǎn)周圍擴(kuò)散獲取新的匹配點(diǎn)。

上述準(zhǔn)稠密匹配方法可以應(yīng)用于部分基線較寬的圖像，但是應(yīng)用于室外建筑物場景圖像的匹配擴(kuò)散時(shí)卻不能取得較好效果。Megyesi等[17]提出的匹配擴(kuò)散算法應(yīng)用到了表面紋理是豐富且分段光滑的圖像，具體如下：在種子匹配點(diǎn)的仿射矩陣參數(shù)基礎(chǔ)上，進(jìn)行小幅度范圍搜索來確定新的匹配點(diǎn)的最佳仿射矩陣，通過這種擴(kuò)散方法獲取數(shù)量更多的準(zhǔn)稠密匹配。該算法的應(yīng)用限制在于：要求原始圖像是紋理豐富的，且需要將原始圖像對(duì)的極線預(yù)先校正為水平方向。而校正工作應(yīng)用到大多數(shù)寬基線圖像來說是比較復(fù)雜的，所以，該方法也不適應(yīng)于寬基線的表面紋理單一的建筑物場景圖像。

通過上述常用特征檢測算法、特征點(diǎn)匹配算法、稠密匹配算法以及典型的準(zhǔn)稠密匹配算法的介紹和分析來看，紋理重復(fù)且單一的建筑物圖像匹配擴(kuò)散的關(guān)鍵在于應(yīng)用更佳的匹配度量準(zhǔn)則來減少匹配多義性即模糊匹配問題。本文在上述匹配擴(kuò)散算法框架基礎(chǔ)上加以改進(jìn)，加入了自適應(yīng)支持加權(quán)準(zhǔn)則作為匹配度量準(zhǔn)則，提出了適用于建筑物圖像的匹配擴(kuò)散算法：

(1) 加入了自適應(yīng)支持加權(quán)準(zhǔn)則即Adaptive Support Weight[18](以下簡稱ASW)作為匹配擴(kuò)散的度量準(zhǔn)則。對(duì)于初始種子匹配點(diǎn)和擴(kuò)散后獲得的新匹配點(diǎn)都應(yīng)用ASW分?jǐn)?shù)進(jìn)行打分，并結(jié)合應(yīng)用仿射傳遞思想進(jìn)行擴(kuò)散匹配，以此確定新的匹配點(diǎn)的準(zhǔn)確位置，從而減少由于匹配多義性而導(dǎo)致的錯(cuò)誤匹配數(shù)。

(2) 對(duì)于建筑物圖像具有較好的適用性，匹配前，不需要對(duì)輸入圖像做預(yù)處理，也不需要預(yù)先計(jì)算攝像機(jī)的參數(shù)和獲取姿態(tài)。

1 建筑物圖像的匹配擴(kuò)散算法框架

1.1 算法框架

先獲取兩幅建筑物圖像的初始種子匹配點(diǎn)，一般來說，得到的初始種子匹配點(diǎn)的數(shù)量比較少，需要運(yùn)用一定的匹配約束和擴(kuò)散規(guī)則在每隊(duì)種子匹配點(diǎn)鄰域內(nèi)擴(kuò)散，搜索和確定新的匹配點(diǎn)，以此獲取準(zhǔn)稠密匹配點(diǎn)。算法流程如下：

步驟1提取圖像SIFT特征點(diǎn)，獲得圖像的初始匹配。

步驟2利用8點(diǎn)算法和RANSAC[19]計(jì)算圖像之間基本矩陣F，剔除外點(diǎn)得到較準(zhǔn)確的SIFT匹配作為種子匹配點(diǎn)。

步驟3計(jì)算每一個(gè)種子匹配點(diǎn)的ASW分?jǐn)?shù)，根據(jù)ASW分?jǐn)?shù)對(duì)種子點(diǎn)進(jìn)行排序組成集合L，每次從L取出ASW分?jǐn)?shù)最小的種子點(diǎn)進(jìn)行擴(kuò)散操作。

步驟4對(duì)當(dāng)前種子點(diǎn)圖像鄰域進(jìn)行基于仿射變換的幾何規(guī)范化，對(duì)于鄰域內(nèi)部的點(diǎn)，重新計(jì)算仿射變換和ASW分?jǐn)?shù)，選擇ASW最小的匹配點(diǎn)，將ASW分?jǐn)?shù)小于一定閾值V并且滿足極線約束的匹配點(diǎn)插入集合L中。轉(zhuǎn)步驟3，直到L為空集。

步驟5將獲取的匹配點(diǎn)進(jìn)行重采樣，得到分布較均勻的準(zhǔn)稠密匹配點(diǎn)。

步驟6利用8點(diǎn)算法和RANSAC再次計(jì)算基本矩陣F并剔除錯(cuò)誤匹配，得到準(zhǔn)稠密匹配結(jié)果。

1.2 鄰域窗口幾何規(guī)范化

種子匹配點(diǎn)的信息除了包括匹配點(diǎn)的二維坐標(biāo)(i,j)和(i′,j′)之外，還包括其所在鄰域窗口對(duì)應(yīng)的仿射矩陣A。應(yīng)用ASW度量準(zhǔn)則進(jìn)行打分并排序可以在很大程度上減少匹配錯(cuò)誤數(shù)量。計(jì)算ASW分?jǐn)?shù)時(shí)，當(dāng)前種子匹配點(diǎn)的鄰域窗口都需要先進(jìn)行幾何規(guī)范化操作(見圖1)，其步驟如下：

圖1 鄰域窗口幾何規(guī)范化過程

(1) 以左邊圖像當(dāng)前匹配點(diǎn)為中心沿極線方向提取一個(gè)大小為(2W+1)×(2W+1)方形區(qū)域。

(2) 對(duì)方形鄰域進(jìn)行仿射變換A，得到右邊圖像上對(duì)應(yīng)方塊區(qū)域。

(3) 對(duì)左右圖像中方形鄰域進(jìn)行雙線性插值變換成(4W+1)×(4W+1)大小。

(4) 將插值后的窗口重新采樣為(2W+1)×(2W+1)大小窗口。

由于寬基線建筑物圖像透視變換嚴(yán)重，若沿著水平方向選取鄰域窗口可能導(dǎo)致擴(kuò)散失敗。因此，通常在左邊圖像中，沿著當(dāng)前種子匹配點(diǎn)的極線方向選取方形小塊，通過仿射變換得到右邊圖像的對(duì)應(yīng)窗口。由此，計(jì)算候選匹配點(diǎn)的ASW分?jǐn)?shù)時(shí)，所使用到的當(dāng)前種子匹配點(diǎn)對(duì)的鄰域窗口區(qū)域內(nèi)包含了相同的內(nèi)容，因此計(jì)算得到的ASW分?jǐn)?shù)更加準(zhǔn)確，減少擴(kuò)散后的錯(cuò)誤匹配。

在計(jì)算種子匹配點(diǎn)和擴(kuò)散時(shí)搜索到的候選匹配點(diǎn)的ASW分?jǐn)?shù)時(shí)，分別選擇了不同大小的窗口來進(jìn)行計(jì)算。由于初始種子匹配點(diǎn)是識(shí)別度較高的特征點(diǎn)，對(duì)于表面紋理不太豐富的建筑物圖像來說，初始種子匹配點(diǎn)可選擇稍大的窗口(如15×15)來計(jì)算其ASW分?jǐn)?shù)值，再進(jìn)行排序，確定初始種子匹配點(diǎn)的準(zhǔn)確性排序；對(duì)于擴(kuò)散搜索到的候選匹配點(diǎn)，則選擇較小的窗口(如7×7)，在該窗口內(nèi)計(jì)算其ASW分?jǐn)?shù)，確保搜索到的候選匹配點(diǎn)所在窗口不超出種子匹配點(diǎn)的窗口范圍。

此外，計(jì)算候選匹配點(diǎn)的ASW分?jǐn)?shù)使用的匹配度量準(zhǔn)則結(jié)合了像素的顏色信息和幾何距離信息，運(yùn)用各像素的顏色支持權(quán)重和幾何距離支持權(quán)重的差異，通過ASW匹配代價(jià)函數(shù)來計(jì)算ASW匹配分?jǐn)?shù)。

1.3 仿射傳遞

算法的步驟4中采用了仿射傳遞思想。在一般的匹配擴(kuò)散算法中如文獻(xiàn)[17]和文獻(xiàn)[20]都應(yīng)用到了仿射傳遞，其過程如下：在進(jìn)行匹配擴(kuò)散時(shí)，以種子匹配點(diǎn)為中心，沿著極線選取鄰域窗口，利用初始種子匹配點(diǎn)的仿射矩陣，將該矩陣的三個(gè)參數(shù)進(jìn)行微小變化而搜索，最終得到新匹配點(diǎn)的最佳仿射矩陣，由此也獲得了新匹配點(diǎn)的最佳鄰域窗口。當(dāng)匹配擴(kuò)散到達(dá)邊界或角落時(shí)，擴(kuò)散搜索到的新候選匹配點(diǎn)的深度或顏色信息發(fā)生突變，仿射矩陣的各參數(shù)突變，即仿射矩陣的各參數(shù)無法在小幅度范圍內(nèi)搜索變化得到新的仿射矩陣，因此仿射傳遞將停止，當(dāng)前種子點(diǎn)的擴(kuò)散終止。本文使用的仿射傳遞同時(shí)結(jié)合ASW分?jǐn)?shù)匹配度量準(zhǔn)則，以此使每次搜索計(jì)算得到的仿射矩陣是最佳的，提高了算法的準(zhǔn)確性。

2 自適應(yīng)支持加權(quán)匹配度量準(zhǔn)則ASW

圖像的匹配多義性即對(duì)于左邊圖像中給定像素，由于右邊圖像存在多個(gè)像素的顏色和結(jié)構(gòu)等信息很相似，因此無法確定該特征點(diǎn)唯一對(duì)應(yīng)的精確匹配點(diǎn)。一般的匹配約束條件或匹配打分如灰度相似性約束ZNCC和置信度約束等都無法解決上述匹配模糊問題。本節(jié)將詳細(xì)介紹第1節(jié)算法中的步驟3，闡述ASW匹配度量準(zhǔn)則原理及ASW分?jǐn)?shù)計(jì)算過程。

ASW是在固定窗口下用權(quán)重自適應(yīng)變化計(jì)算其匹配代價(jià)函數(shù)值即ASW分?jǐn)?shù)來度量兩個(gè)像素點(diǎn)的匹配程度，其思想是綜合考慮左右圖像對(duì)應(yīng)參考支持窗口內(nèi)像素的支持權(quán)重，結(jié)合初始匹配代價(jià)進(jìn)行加權(quán)求和，得到對(duì)應(yīng)像素對(duì)的ASW分?jǐn)?shù)。對(duì)于落到同一窗口內(nèi)的候選匹配點(diǎn)，ASW分?jǐn)?shù)決定了其匹配代價(jià)和匹配程度，因此分析ASW分?jǐn)?shù)從很大程度上可以減少誤匹配。

通過上面的分析可知，計(jì)算ASW分?jǐn)?shù)須要結(jié)合顏色支持權(quán)重和距離支持權(quán)重。像素和像素之間的支持權(quán)重表達(dá)式如下：

w(i,j)=f(Δcij,Δdij)

(1)

Δcij和Δdij分別表示像素i和像素j的顏色差值和歐式幾何距離。

將f(Δcij,Δdij)分開來計(jì)算：

f(Δcij,Δdij)=f(Δcij)·f(Δdij)

(2)

f(Δcij)為顏色權(quán)重，f(Δdij)為距離權(quán)重，其表達(dá)式分別如下：

(3)

(4)

式中：Δcij是在CIELab顏色空間上對(duì)像素i的顏色值ci=[Li,ai,bi]和像素j的顏色值cj=[Lj,aj,bj]進(jìn)行差值計(jì)算得到的，rc是顏色差值閾值，由窗口內(nèi)的實(shí)際顏色信息來決定，rp是距離差值閾值，由支持窗口的大小來決定。CIELab是CIE的一個(gè)顏色系統(tǒng)，Li、ai、bi表示CIELab顏色值ci的三個(gè)坐標(biāo)。相較于RGB顏色空間來說，CIELab顏色空間更接近于人的視覺感知系統(tǒng)。

綜合上面四個(gè)表達(dá)式，得到w(i,j)的最終表達(dá)式為：

(5)

在左邊圖像I中取以i為中心的鄰域窗口Ni，在右邊圖像I′中取以i′為中心的對(duì)應(yīng)鄰域窗口Ni′，結(jié)合Ni和Ni′的支持權(quán)重w(i,j)、w(i′,j′)，對(duì)初始匹配代價(jià)e(j,j′)加權(quán)求和，獲得ASW匹配分?jǐn)?shù)E(i,i′)：

(6)

(7)

式中：Ni和Ni′是幾何規(guī)范化的(2W+1)×(2W+1)窗口，e(j,j′)為初始匹配代價(jià)，Y為顏色差值閾值。

綜上可知，ASW應(yīng)用左邊圖像和右邊圖像對(duì)應(yīng)的像素對(duì)其各自窗口中心像素的顏色支持權(quán)重和距離支持權(quán)重來計(jì)算其匹配代價(jià)值。在通常小范圍局部窗口區(qū)域內(nèi)，像素的顏色變化一般是連續(xù)的，其深度信息也相同或相近。反之，在顏色變化不連續(xù)和深度有突變的邊界上，像素與中心點(diǎn)的顏色差值很大，計(jì)算得到的ASW分?jǐn)?shù)都較大，其值也大于閾值V，對(duì)于這種候選匹配點(diǎn)不滿足入選種子匹配隊(duì)列的條件，當(dāng)前種子匹配點(diǎn)的擴(kuò)散和仿射傳遞也將終止。因此，利用ASW分?jǐn)?shù)作為匹配度量準(zhǔn)則，結(jié)合仿射傳遞，可以使邊界上的匹配更加準(zhǔn)確。

3 實(shí)驗(yàn)結(jié)果和分析

圖2、圖3、圖4是三個(gè)實(shí)際場景的建筑物圖像對(duì)的匹配擴(kuò)散結(jié)果，通過原始圖像對(duì)、初始種子點(diǎn)匹配、準(zhǔn)稠密匹配以及部分三維重建來呈現(xiàn)效果。算法程序用C++代碼實(shí)現(xiàn)，程序在普通的PC機(jī)平臺(tái)上運(yùn)行。實(shí)驗(yàn)中的主要參數(shù)設(shè)置如下：式(3)中rc取6；式(4)中rp取7.5；式(6)中，Ni和Ni′為15×15大小窗口；式(7)中Y取21；算法步驟4的閾值V取24。

(a) 原始圖像對(duì)

(b) 種子SIFT匹配結(jié)果

(c) 準(zhǔn)稠密擴(kuò)散匹配結(jié)果圖2 Merton College校園建筑樓圖像的準(zhǔn)稠密匹配

(a) 原始圖像對(duì)

(b) 種子SIFT匹配結(jié)果

(c) 準(zhǔn)稠密擴(kuò)散匹配結(jié)果

(d) 場景三維重建結(jié)果：紋理貼圖、三維點(diǎn)云圖3 山西應(yīng)縣木塔準(zhǔn)稠密匹配結(jié)果和三維重建結(jié)果

(a) 原始圖像對(duì)

(b) 種子匹配結(jié)果

(c) 準(zhǔn)稠密擴(kuò)散匹配結(jié)果

(d) 三維重建結(jié)果圖4 聞一多雕像圖像的準(zhǔn)稠密匹配結(jié)果

首先，圖2是通過本文算法針對(duì)Merton College校園建筑樓圖像得到的準(zhǔn)稠密匹配結(jié)果。原始圖像分辨率1 024×768，初始種子匹配點(diǎn)數(shù)目1 736對(duì)，擴(kuò)散后得到5 514對(duì)最終準(zhǔn)稠密匹配點(diǎn)。經(jīng)過擴(kuò)散后得到403 805對(duì)稠密匹配點(diǎn)，耗時(shí)1 062 s，平均匹配用時(shí)2.63 ms。由圖2可見，初始圖像的視角變化比較大，而由初始種子匹配擴(kuò)散得到的準(zhǔn)稠密匹配結(jié)果數(shù)量較多、準(zhǔn)確而且分布較均勻，并且絕大部分邊界上的匹配結(jié)果都是正確的。

圖3是針對(duì)山西應(yīng)縣木塔的圖像對(duì)，使用本文算法得到的準(zhǔn)稠密匹配結(jié)果。為了驗(yàn)證本文算法的合理性，將準(zhǔn)稠密匹配結(jié)果結(jié)合三維重建算法，得到了三維重建結(jié)果包括紋理貼圖和三維點(diǎn)云。原始圖像對(duì)的分辨率為1 440×1 920，初始種子匹配點(diǎn)獲取了3 874對(duì)，通過匹配擴(kuò)散后，最終獲得16 584對(duì)準(zhǔn)稠密匹配。

此外，我們還將本文算法應(yīng)用到同樣是紋理單一且重復(fù)的視角變化較大的雕塑圖像上進(jìn)行實(shí)驗(yàn)。圖4是針對(duì)清華大學(xué)校園內(nèi)的聞一多雕像不同角度拍攝的圖像得到的準(zhǔn)稠密匹配及三維重建結(jié)果。所使用的原始圖像對(duì)的分別率為1 000×1 504，獲得的初始種子點(diǎn)數(shù)為368，經(jīng)過匹配擴(kuò)散后最終得到5 329對(duì)準(zhǔn)稠密匹配結(jié)果。

將本文算法與文獻(xiàn)[16]算法都應(yīng)用到清華大學(xué)某建筑樓圖像進(jìn)行匹配擴(kuò)散對(duì)比，得到如圖5所示結(jié)果。圖5(a)和(b)為文獻(xiàn)[16]算法結(jié)果：從68對(duì)初始種子點(diǎn)進(jìn)行匹配擴(kuò)散，最終得到2 041對(duì)準(zhǔn)稠密匹配結(jié)果；圖5(c)和(d)為本文算法結(jié)果：從82對(duì)初始種子點(diǎn)經(jīng)過匹配擴(kuò)散后，最終得到3 101對(duì)準(zhǔn)稠密匹配結(jié)果。

(a) 文獻(xiàn)[16]算法種子匹配結(jié)果

(b) 文獻(xiàn)[16]算法準(zhǔn)稠密擴(kuò)散匹配結(jié)果

(c) 本文算法種子匹配結(jié)果

(d) 本文算法準(zhǔn)稠密擴(kuò)散匹配結(jié)果圖5 本文算法與文獻(xiàn)[16]算法匹配擴(kuò)散比較

為了體現(xiàn)本文算法及文獻(xiàn)[16]算法的運(yùn)行結(jié)果和效率，將上述圖2至圖5實(shí)驗(yàn)的匹配結(jié)果和運(yùn)行時(shí)間總結(jié)于表1。

表1 實(shí)驗(yàn)2至實(shí)驗(yàn)5數(shù)據(jù)

結(jié)合圖5和表1結(jié)果：綜合最終準(zhǔn)稠密擴(kuò)散匹配點(diǎn)數(shù)、匹配點(diǎn)分布以及運(yùn)算效果來看，本文算法都要略優(yōu)于文獻(xiàn)[16]算法結(jié)果。

4 結(jié) 語

本文運(yùn)用自適應(yīng)支持加權(quán)準(zhǔn)則研究了適用于紋理單一而重復(fù)的建筑物場景圖像的匹配擴(kuò)散算法。實(shí)驗(yàn)結(jié)果表明，本文算法取得了效果比較好的匹配擴(kuò)散結(jié)果。本文算法適用性廣，不需要對(duì)原始圖像進(jìn)行預(yù)先校正，攝像機(jī)的內(nèi)參數(shù)矩陣和外參數(shù)矩陣也無需預(yù)先標(biāo)定，整個(gè)匹配擴(kuò)散的計(jì)算過程都是自動(dòng)的。

下一步的研究工作將針對(duì)初始公共種子匹配點(diǎn)數(shù)量少的問題，提高多幅圖像之間的準(zhǔn)稠密匹配擴(kuò)散質(zhì)量和效果。