賀 亮， 劉 榮， 呂開(kāi)云

(東華理工大學(xué)測(cè)繪工程學(xué)院，江西撫州 344000)

一種基于種子生長(zhǎng)的匹配算法

賀 亮， 劉 榮， 呂開(kāi)云

(東華理工大學(xué)測(cè)繪工程學(xué)院，江西撫州 344000)

立體匹配是三維重建的重要組成部分，被廣泛用于數(shù)字城市、虛擬現(xiàn)實(shí)等領(lǐng)域中。提出了一種基于種子生長(zhǎng)的匹配點(diǎn)擴(kuò)散算法。首先用SIFT算法提取圖像間對(duì)應(yīng)的特征點(diǎn)并將其做為種子點(diǎn)，對(duì)種子點(diǎn)在其領(lǐng)域范圍進(jìn)行區(qū)域傳播匹配。接著將生長(zhǎng)得到稠密匹配點(diǎn)經(jīng)重采樣轉(zhuǎn)換為準(zhǔn)稠密匹配點(diǎn)。最后再用對(duì)稱對(duì)極點(diǎn)距離法去除誤匹配得到整幅圖像上均勻分布的精確匹配點(diǎn)對(duì)。實(shí)驗(yàn)表明，改進(jìn)的算法對(duì)于表面結(jié)構(gòu)重復(fù)性高、未校正的圖像均適用并能得到較好結(jié)果。

SIFT算法;區(qū)域傳播;極線校正;準(zhǔn)稠密匹配

立體匹配是三維重建的關(guān)鍵技術(shù)之一，通過(guò)恢復(fù)立體像對(duì)所對(duì)應(yīng)匹配點(diǎn)的空間三維坐標(biāo)及三維網(wǎng)格連接和紋理映射可以完成三維物體可見(jiàn)表面的幾何結(jié)構(gòu)(張祖勛等，1997)。隨著三維重建在數(shù)字地球、數(shù)字城市和虛擬現(xiàn)實(shí)等領(lǐng)域應(yīng)用的發(fā)展，立體匹配技術(shù)也越來(lái)越受到廣大研究人員的關(guān)注。然而，圖像對(duì)應(yīng)點(diǎn)自動(dòng)匹配的密度及精度間并沒(méi)有得到很好的解決。

立體匹配的算法研究分為全局算法和局域算法兩大類(lèi)(陳鷹，2003)。全局算法主要是通過(guò)優(yōu)化某一視差函數(shù)來(lái)完成，如傅立葉變換的方法。該算法的不足之處是計(jì)算時(shí)間較長(zhǎng)，難以滿足實(shí)時(shí)重建的要求。局域算法又可分為基于特征的匹配算法和基于像素的匹配算法?；谔卣鞯钠ヅ淠軌蛲ㄟ^(guò)Harris，SIFT，MSER等匹配方法準(zhǔn)確提取圖像的特征，降低了時(shí)間和空間復(fù)雜度，但只能得到少數(shù)的匹配基元，遠(yuǎn)遠(yuǎn)無(wú)法滿足三維物體精準(zhǔn)可視化的要求?；谙袼氐钠ヅ浞椒▌t是對(duì)每一個(gè)像素都計(jì)算一次匹配，雖然能得到稠密的匹配點(diǎn)集，但十分耗時(shí)且可靠性不高。

針對(duì)上述各匹配方法存在的缺陷，有研究人員提出了種子生長(zhǎng)的匹配方法(Ottog et al.，1989)。稠密匹配的各種方法也孕育而出。本文根據(jù)稠密匹配的原理，簡(jiǎn)化了Lhuillier等(2005)中的算法，提出了一種新的稠密匹配方法，先使用SIFT算法提取出可靠性較高的特征匹配點(diǎn)做為種子點(diǎn)，接著使用Best－First原則從匹配點(diǎn)集中找出最可靠的點(diǎn)對(duì)，對(duì)其進(jìn)行區(qū)域傳播稠密匹配得到稠密的匹配點(diǎn)集?？紤]到所有匹配點(diǎn)是用于三維重建的，在得到的點(diǎn)集中使用重采樣的方法得到均勻分布的準(zhǔn)稠密點(diǎn)，最后再用對(duì)稱對(duì)極點(diǎn)距離法消除誤匹配，通過(guò)三維網(wǎng)格的建立及紋理映射，得到滿足視覺(jué)要求的三維物體重建。

1 SIFT特征基元的提取與匹配

點(diǎn)特征是影像最基本的特征，常被用于圖像的配準(zhǔn)與匹配，目標(biāo)描述與識(shí)別和立體像對(duì)3D建模等眾多領(lǐng)域(官云蘭等，2007)。SIFT特征(Scaleinvariant feature transform，尺度不變特征轉(zhuǎn)換)是一種電腦視覺(jué)的算法用來(lái)偵測(cè)與描述影像中的局部性特征，它在空間尺度中尋找極值點(diǎn)，并提取出其位置、尺度、旋轉(zhuǎn)不變量，此算法由Lowe(2005)提出。此方法是將圖像分為各個(gè)子區(qū)域來(lái)計(jì)算其位置和方向的三維直方圖，然后使用直方圖法得到描述子，即使在圖像形變的情況下仍能保持很好的穩(wěn)定性(賈永紅，2003)。優(yōu)于常規(guī)的利用灰度相關(guān)性作依據(jù)的匹配方法。所以采用SIFT用于初始點(diǎn)的匹配提取。

根據(jù)SIFT算法提取出特征向量的灰度相似性作為兩幅圖像匹配點(diǎn)的相似性判別量，使用ZNCC(歸一化零均值互相關(guān)系數(shù))來(lái)建立初始匹配。ZNCC定義如下:

式中 Δ=(Δx，Δy)T為對(duì)應(yīng)點(diǎn)X=(x，y)T的偏移量，ˉI(x)和ˉI'(x)分別為兩幅圖像中以x為中心的窗口內(nèi)所有像素灰度的平均值。ZNCC的取值范圍為－1～1，值越大則表示對(duì)應(yīng)點(diǎn)的相似程度越高。本文中的相關(guān)性窗口取值為7，將ZNCC＞0.8的點(diǎn)對(duì)做為種子點(diǎn)。

2 匹配點(diǎn)擴(kuò)散算法

本文中的匹配點(diǎn)擴(kuò)散算法流程圖由圖1來(lái)表示。

圖1 擴(kuò)散算法流程圖Fig.1 The flow chart of propagation algorithm

下面介紹每個(gè)步驟的詳細(xì)操作:

Step1。將已得到的種子點(diǎn)按ZNCC值從大到小的順序排一個(gè)隊(duì)列，從隊(duì)列頂端取出可靠性最高的一對(duì)種子點(diǎn)(Xi，X'i)，并將其在種子隊(duì)列中刪除。使用Best－First(最優(yōu)最先)的策略，即每次都由最可靠的種子點(diǎn)來(lái)擴(kuò)散出相應(yīng)匹配點(diǎn)，保證了擴(kuò)散出來(lái)的匹配點(diǎn)的精確度，從一定程度上達(dá)到了全局優(yōu)化的效果。種子點(diǎn)的領(lǐng)域定義為:

種子點(diǎn)的領(lǐng)域可被表示為(2N+1)×(2N+1)的像素集，其中N為領(lǐng)域的半徑，一般取值為2。

Step2。由以下四個(gè)約束條件在種子點(diǎn)的領(lǐng)域里擴(kuò)散出滿足條件的匹配點(diǎn)。

(1)離散二維視差梯度約束。根據(jù)物體表面一般都存在平滑性得出臨近的點(diǎn)需滿足一定的視差要求，滿足其要求的匹配點(diǎn)定義為

其中ε為視差梯度的閾值，可取值為1。

(2)灰度相似性約束。匹配點(diǎn)要求灰度的相似性達(dá)到一定程度，文中要求匹配點(diǎn)的ZNCC值必須大于0.5。

(3)置信度約束。置信度約束使得匹配點(diǎn)的擴(kuò)散能沿著邊緣擴(kuò)散而不擴(kuò)散到灰度過(guò)于一致的區(qū)域，本文中的置信度定義為:

在圖像灰度歸一化的情況下，文中設(shè)定擴(kuò)散只在滿足＞0.01的條件下進(jìn)行。相似的置信度約束還有Moravec算子(Moravec，1977)。

(4)唯一性約束。根據(jù)像對(duì)匹配點(diǎn)需滿足一一對(duì)應(yīng)的原則，當(dāng)Xi或X'i在對(duì)應(yīng)的圖像上已存在匹配點(diǎn)，則不再對(duì)該點(diǎn)進(jìn)行擴(kuò)散匹配。

將通過(guò)Step2得到的匹配點(diǎn)放入種子點(diǎn)隊(duì)列slist中，重復(fù)Step1和Step2，直至種子隊(duì)列中不再存在種子點(diǎn)。所有的匹配點(diǎn)便組成了稠密匹配點(diǎn)集。

Step3。由于本文中立體匹配的目的是為了三維重建，所以只需要準(zhǔn)稠密匹配點(diǎn)集即可，通過(guò)重采樣，可以得到均勻分布的更加準(zhǔn)確可靠的匹配點(diǎn)。將第一幅圖像分割成8×8的小方格區(qū)域，在方格區(qū)域內(nèi)的稠密點(diǎn)集使用Ransac方法估算與其對(duì)應(yīng)第二幅圖像中小區(qū)域的仿射矩陣H，由此保證了仿射矩陣不會(huì)受到一些誤匹配點(diǎn)的影響。計(jì)算第一幅圖像個(gè)小方格區(qū)域的中心點(diǎn)坐標(biāo)C，計(jì)算得到在另一幅圖像中對(duì)應(yīng)的中心點(diǎn)H*C。如果小方格區(qū)域中存在初始種子點(diǎn)，用同樣方法得到對(duì)應(yīng)點(diǎn)(圖2)。將這一步中得到的所有點(diǎn)放入集合，組成準(zhǔn)稠密匹配點(diǎn)集。由于最后得到的準(zhǔn)稠密匹配點(diǎn)是各個(gè)區(qū)域的中心點(diǎn)通過(guò)相應(yīng)的仿射轉(zhuǎn)換得到的，所以即使初始種子點(diǎn)因紋理重復(fù)等原因匹配錯(cuò)誤，對(duì)得到準(zhǔn)稠密匹配點(diǎn)影響也有限。

圖2 重采樣示意圖Fig.2 The resample of square grid

Step4。使用Ransac方法用8點(diǎn)法迭代計(jì)算出立體像對(duì)間的基本矩陣F。計(jì)算過(guò)程中使用對(duì)稱對(duì)極點(diǎn)距離法來(lái)去除不滿足條件的外點(diǎn)(鄭碧娜等，2009)。通過(guò)設(shè)定閾值，可以除去此前因紋理重復(fù)或各種原因產(chǎn)生的不滿足要求的匹配點(diǎn)，保留下來(lái)的匹配點(diǎn)均在一定精度以內(nèi)，大大提高匹配點(diǎn)的準(zhǔn)確度。

其中F為計(jì)算得到的基本矩陣;(FXi表示矢量FXi的第j個(gè)元素的平方。文中要求S＜1.0，即表明只保留下誤差值在1個(gè)像素距離以內(nèi)的匹配點(diǎn)。

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

采用文中提到的擴(kuò)散算法，對(duì)兩組圖像(一組為校正圖像，另一組為未校正圖像)做了擴(kuò)散及重采樣的實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)為Matlab2008a，算法的主要參數(shù)設(shè)置為:ZNCC領(lǐng)域半徑為2，擴(kuò)散要求匹配點(diǎn)ZNCC＞0.5，視差梯度閾值取1，置信度取值0.01。

3.1 校正圖像

如圖3所示，圖3a，圖3b分別表示原始圖像的左圖和右圖，圖3c表示了左右兩圖的視差圖，是由經(jīng)Step1，Step2循環(huán)得到的稠密匹配點(diǎn)(共得到115 261對(duì)匹配點(diǎn))對(duì)列坐標(biāo)相減得到，視差圖中個(gè)像素的灰度信息表示了物體距離的遠(yuǎn)近信息，灰度越大表示距離越近。從視差圖上可以直觀的了解到經(jīng)由Step1，Step2循環(huán)得到的稠密匹配點(diǎn)對(duì)是比較準(zhǔn)確的。圖3d則是經(jīng)過(guò)重采樣和核線約束后得到的準(zhǔn)稠密匹配點(diǎn)(共2 000對(duì)匹配點(diǎn))。

3.2 未校正圖像

如圖4所示，同樣在未校正像對(duì)上運(yùn)用了該算法，圖4a，圖4b分別表示原始圖像的左圖和右圖，由于未校正圖像無(wú)法通過(guò)匹配點(diǎn)列坐標(biāo)相減得到視差圖，為了直觀地表達(dá)經(jīng)由Step1，Step2循環(huán)得到的稠密匹配點(diǎn)對(duì)(共198 716對(duì)匹配點(diǎn))的準(zhǔn)確性，采用了另一種方法來(lái)表示，如果圖4a中一點(diǎn)與圖4b中一點(diǎn)匹配，則將點(diǎn)的灰度復(fù)制到結(jié)果圖像點(diǎn)的位置。圖4c為得到的匹配效果圖(黑色部分為未匹配區(qū)域)，它可以直觀的表達(dá)稠密匹配的效果，圖中可以看出本文中的算法在存在結(jié)構(gòu)重復(fù)性較高的區(qū)域也取得了精確的結(jié)果。圖4d為最后得到的準(zhǔn)稠密匹配圖(共5 094對(duì)匹配點(diǎn))。

4 結(jié)論

從以上對(duì)校正圖像和未校正圖像的實(shí)驗(yàn)中可以看出，本文提到的立體匹配擴(kuò)散算法對(duì)于表面結(jié)構(gòu)性重復(fù)高、未校正的圖像均適用并能得到較好結(jié)果。先使用SIFT算子結(jié)合ZNCC提取出初始的種子點(diǎn)，經(jīng)由區(qū)域擴(kuò)散和重采樣后得到稠密的匹配點(diǎn)集，從實(shí)驗(yàn)中可得出這些稠密匹配點(diǎn)已具有較高精度，接著通過(guò)重采樣和核線約束得到對(duì)于整幅圖像均勻分布的更加準(zhǔn)確的準(zhǔn)稠密匹配點(diǎn)，在提高精度的同時(shí)也合理減少了三維重建時(shí)的數(shù)據(jù)量?；謴?fù)這些準(zhǔn)稠密匹配點(diǎn)的三維坐標(biāo)、建立三維網(wǎng)格及紋理映射之后，就可以得到逼真的可視三維模型。

陳鷹.2003.遙感影像的數(shù)字?jǐn)z影測(cè)量［M］.上海:同濟(jì)大學(xué)出版社.

官云蘭，張紅軍，劉向美.2007.點(diǎn)特征提取算法探討［J］.東華理工學(xué)院學(xué)報(bào)，30(1):42－46.

賈永紅.2003.數(shù)字圖像處理［M］.武漢:武漢大學(xué)出版社.

張祖勛，張劍清.1997.數(shù)字?jǐn)z影測(cè)量學(xué)［M］.武漢:武漢大學(xué)出版社.

鄭碧娜，江澤濤，吳敏.2009.一種基于立體像對(duì)稠密匹配的三維重建方法［J］.中國(guó)體視學(xué)與圖像分析，14(2):187－191.

Moravec H P.1977.Towards automatic visual obstacle avoidance［C］.In Proceedings of the 5th International Joint Conference on Artificial Intelligence，Cambridge，Massachusetts，USA，584.

Lhuillier M，Quan L.2005.A quasi－dense approach to surface reconstruction from uncalibrated images［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，27(3):418－433.

Lowe D G.2005.Distinctive Image Features from Scale－Invariant Points［J］.International Journal of Computer Vision，60(2):91－110.

Ottog P，Chaut K W.1989.A“region－growing”algorithm for matching of terrain images［J］.Image and Vision Computing，7(2):83－94.

An Algorithm for Image Match Propagation

HE Liang， LIU Rong， Lü Kai－yun
(Faculty of Geomatics，East China Institute of Technology，F(xiàn)uzhou，JX 344000，China)

Stereo matching，an important part of 3D reconstruction，is widely used in digital cities，virtual reality.An improved match propagation algorithm is proposed.Firstly，the feature points are extracted and matched by SIFT algorithm.Then，the seed points are matched propagation in the neighborhood.Secondly，these dense correspondences are resampled to quasi－dense correspondences.Finally，the mismatched points and outliers are eliminated with epipolar constraint.Results show that this algorithm can be utilized for images with similar structure and without correction，and presents good performance.

SIFT algorithm;propagation;epipolar correction;quasi－dense matching

P232

A

1674－3504(2011)04－0379－05

賀亮，劉榮，呂開(kāi)云.2011.一種基于種子生長(zhǎng)的匹配算法［J］.東華理工大學(xué)學(xué)報(bào):自然科學(xué)版，34(4):379－383.He Liang，Liu Rong，Lü Kai－yun.2011.An algorithm for image match propagation［J］.Journal of East China Institute of Technology(Natural Science)，34(4):379－383.

10.3969/j.issn.1674－3504.2011.04.012

2011－09－06; 責(zé)任編輯:吳志猛

江西省自然科學(xué)基金(2009GQS0001)

賀 亮(1986—)，男，碩士研究生，攝影測(cè)量與遙感專(zhuān)業(yè)。Email:hl_chn@163.com