王競雪 張 晶 張 雪

(1. 遼寧工程技術大學測繪與地理科學學院, 遼寧阜新 123000;2. 西南交通大學地球科學與環(huán)境工程學院, 四川成都 611756)

1 引言

隨著數(shù)碼相機的普及使得近景影像的獲取十分便捷，因此，基于近景影像的三維重建也成為攝影測量和計算機視覺領域研究的熱門話題，其中關鍵核心問題即影像匹配[1-3]。現(xiàn)有點匹配算法，如SIFT[4]、ASIFT[5]、SURF[6]等算法已經(jīng)非常成熟，可獲取可靠的同名點。但這些方法得到的結果往往是稀疏的匹配點集，難以勝任高精細三維建模的需求，故基于影像的密集匹配變得十分必要的。目前常用的方法是基于靜態(tài)區(qū)域約束的密集匹配。該類方法將影像劃分成多個獨立區(qū)域并結合多種約束條件完成匹配。文獻[7- 8]利用N個種子點和Voronoi方法將圖像劃分成N個區(qū)域，利用SSD等約束完成區(qū)域內(nèi)像素點的匹配、文獻[9-10]利用稀疏匹配結果進行Delaunay三角網(wǎng)的構建，在同名三角網(wǎng)的區(qū)域里進行匹配、文獻[11]利用Markov網(wǎng)絡作為區(qū)域約束引導匹配傳播，用貝葉斯置信度傳播算法完成網(wǎng)格中逐像素的匹配。該類方法約束區(qū)域大小是固定的，不能隨著匹配點的增加而動態(tài)更新約束范圍，不能有效利用過程數(shù)據(jù)，約束較為固定。另一種是漸進傳播約束的密集匹配，常用的漸進三角網(wǎng)傳播策略，文獻[12]提出一種自適應三角形約束的影像可靠匹配方法，與上述固定區(qū)域約束相比，該方法提出了一種動態(tài)更新三角形的匹配傳播策略，將匹配過程中產(chǎn)生新的同名點不斷插入到初始三角網(wǎng)中，時時更新優(yōu)化三角形用于進一步約束后續(xù)點匹配。但該方法利用三角網(wǎng)內(nèi)已有的特征點進行匹配，本質(zhì)上仍屬于稀疏匹配范疇，且時時更新三角網(wǎng)算法較為復雜，計算量大。文獻[13]提出一種近景影像三角網(wǎng)內(nèi)插點密集匹配方法，該方法認為理想狀態(tài)下，同名三角形的重心即為同名點，后續(xù)再經(jīng)過彩色信息相似性約束和極線約束進行篩選。該方法對于視差變化小的近景影像，或者視頻序列影像效果較為理想，對于視差變化較大的近景影像難以適用。針對上述問題，本文提出一種簡單有效的迭代三角網(wǎng)約束的近景影像密集匹配算法。該方法以初始同名點構建的Delaunay三角網(wǎng)作為匹配基礎，以左影像三角形重心作為匹配基元，綜合多重約束確定右影像上的同名點。迭代過程中整體構網(wǎng)，以三角形面積為間接約束，以是否有新的同名點產(chǎn)生為直接約束作為迭代停止的條件，取得較好的密集匹配結果。

2 算法原理

本文首先利用SIFT算法對左、右影像進行匹配，并采用RANSAC方法對匹配結果進行錯誤剔除，得到初始同名點。利用初始同名點構建左、右影像上同名Delaunay三角網(wǎng)，通過目視檢測同名三角網(wǎng)的一致性進一步剔除誤匹配點，確保初始同名三角網(wǎng)的正確性；然后依次以左影像上三角形重心作為匹配基元加密匹配，匹配過程中綜合利用同名三角形區(qū)域約束、核線約束確定右影像匹配候選點集，利用灰度相關約束確定最終同名點；對于上述過程未匹配到同名點的重心點，在確定同名三角形相似度的條件下，通過仿射變換和重心約束確定同名點；最后結合已有同名點及新匹配得到的同名點，整體構建Delaunay三角網(wǎng)，迭代匹配，直到新構建的三角網(wǎng)內(nèi)所有三角形面積都小于一定閾值為止，迭代停止。

2.1 左、右影像上同名三角網(wǎng)的構建

利用初始同名點構建左、右影像上同名三角網(wǎng)是本文算法加密匹配的基礎。利用初始稀疏點建立的三角網(wǎng)中的三角形要盡量達到角度和邊長接近正三角形，理論證明，Delaunay三角網(wǎng)是有限點集中的、且唯一存在的局部等角三角網(wǎng)。因此本文選擇Delaunay三角網(wǎng)作為初始網(wǎng)型。在以三角網(wǎng)作為區(qū)域約束的匹配傳播中，應確保左、右影像上同名三角網(wǎng)的關系是一一對應的，即兩張影像上同名三角網(wǎng)內(nèi)同名三角形的順序要一致，同名三角形的頂點對應關系要一致。本文以左影像作為基準，對左影像上的初始同名點嚴格按照Delaunay準則構建初始三角網(wǎng)，依次得到每個三角形的頂點索引。對應右影像上，則根據(jù)左影像上三角形的頂點索引及其對應的右影像上的同名點直接構建對應的同名三角網(wǎng)。

2.2 同名三角形約束下的重心點匹配

2.2.1匹配基礎

研究以同名三角形作為匹配基礎，以三角形重心點作為密集匹配基元，匹配過程中涉及三角形重心、面積、以及三角形相似性等基本理論，因此，首先對上述基礎理論進行簡單介紹。

(1)三角形重心

三角形的重心點是三條邊中線的交點，其點位必然在三角形內(nèi)。假定某一三角形頂點坐標分別為A(xA,yA)、B(xB,yB)、C(xC,yC)，其重心點P坐標為：

(1)

(2)三角形面積

三角形面積S可利用海倫公式求得：

(2)

其中l(wèi)=(l1+l2+l3)/3，l1、l2、l3分別為三角形三邊的邊長。

(3)三角形相似性

(3)

當T△=1時，認為兩三角形完全相似。

2.2.2多重條件約束下重心點匹配

對左影像上任一三角形的重心點P，如圖1(a)所示，將其作為匹配基元進行匹配，確定其在右影像上的同名點的具體過程如下：

假定理想狀態(tài)下，根據(jù)同名點一定位于同名三角形內(nèi)的原理，首先將候選點搜索范圍定位于右影像上對應的同名三角形內(nèi)。

然后根據(jù)同名點必定位于同名核線上這一原理，根據(jù)文獻[16]中基于共面條件的核線求解方法計算左影像重心點P在右影像上的核線，進一步將候選點的搜索范圍限定到同名三角形內(nèi)的同名核線上，如圖1(b)所示，減小了搜索范圍，提高了算法的運行效率。

圖1 同名三角形和核線約束匹配候選點

依次遍歷同名三角形內(nèi)同名核線段上的候選點，利用灰度相似性約束確定最終的同名點；該過程根據(jù)公式(4)分別計算左影像上重心點P與右影像上所有候選之間的灰度相關系數(shù)ρ[17]，選取相關系數(shù)最大且大于一定閾值Tρ的候選點作為P點的同名點。實驗過程中相關系數(shù)閾值Tρ=0.75。

(4)

2.3 迭代三角網(wǎng)約束密集匹配

2.3.1具體步驟

迭代三角網(wǎng)約束密集匹配算法實現(xiàn)整體流程如圖2所示，具體步驟如下：

圖2 迭代三角網(wǎng)密集匹配流程圖

步驟1利用已有同名點構建同名Delaunay三角網(wǎng)。

步驟2依次遍歷左影像上三角網(wǎng)中所有三角形，對每一個三角形按照步驟3進行處理，然后轉到步驟5。

步驟3判斷三角形面積是否大于給定的閾值TS？如果大于，計算三角形重心并按照2.2.2所述原理對其進行匹配，得到新的匹配點。對于相關系數(shù)不滿足閾值未匹配到同名點的重心點，進行步驟4。

步驟4判斷左、右影像上同名三角形的相似性，如果相似性大于一定閾值Ti，首先根據(jù)左、右影像上同名三角形對應的三個頂點坐標和六參數(shù)仿射變換公式(5)計算仿射變換參數(shù)[18]：

x′=a0+a1x+a2y

y′=b0+b1x+b2y

(5)

其中，a0、a1、a2、b0、b1、b2表示仿射變換的六參數(shù)，x和y表示左影像上三角形頂點坐標，x′和y′表示右影像上同名三角形對應的頂點坐標。然后根據(jù)求得的參數(shù)和公式(5)，將左影像上的重心點映射至右影像上，將其作為左影像上三角形重心點的同名點。

步驟5判斷是否有新增的匹配點？是，轉到步驟1；否，則停止迭代。圖3分別為局部影像的初始三角網(wǎng)、迭代兩次之后的中間三角網(wǎng)、以及最終的三角網(wǎng)，從中可以看出三角網(wǎng)逐步加密的效果。

2.3.2迭代停止條件

本文同時選取三角形面積和同名點數(shù)目作為迭代停止條件。條件一：理想狀態(tài)下，三角網(wǎng)中每個三角形面積都小于閾值，迭代停止；條件二：在實際匹配過程中，如果存在任一三角形重心點未匹配成功，會導致該三角形的面積永遠大于閾值，條件一約束失敗，會反復循環(huán)迭代匹配。因此匹配過程中，在三角形面積約束迭代的基礎上，同時增加了同名點數(shù)目作為迭代停止條件，通過判斷當前匹配是否有新的同名點增加作為迭代終止條件。滿足上述任一條件，停止迭代。且條件一滿足，條件二同時滿足，反之條件二滿足，條件一未必滿足。假定K為新增同名點數(shù)目，初始值為1，具體程序實現(xiàn)如下：

⑴K=1；

⑵ whileK

⑶ if三角網(wǎng)內(nèi)每個三角形面積

⑷K=0；迭代停止；

⑸ else

⑹ 大于面積閾值的三角形重心依次進行匹配；

⑺ if有新匹配點產(chǎn)生

⑻K=1；繼續(xù)迭代；

⑼ else

(10)K=0；停止迭代；

(11) end

(12) end

(13) end

3 實驗結果及分析

3.1 本文算法密集匹配結果

實驗在3.30GHz Intel Core i5- 4590 CPU、4G內(nèi)存的電腦上進行，采用MATLAB2016a平臺完成算法實現(xiàn)。實驗影像來自網(wǎng)上公開的影像庫數(shù)據(jù)，從中選取三組不同類型的近景影像對作為實驗數(shù)據(jù)，分別如圖4(a)、圖4(b)、圖4(c)所示。三組影像大小分別為680像素×850像素、600像素×800像素和512像素×768像素。其中，圖4(a)所示立體像對

圖3 三角網(wǎng)約束匹配傳播

之間存在較大的旋轉變化，且紋理較豐富；圖4(b)所示建筑物立體像對存在一定的尺度變化，且紋理較為單一；圖4(c)所示立體像對存在視角變化，影像上存在重復紋理。本文首先采用SIFT匹配算法對圖4所示三組影像對進行匹配實驗，并采用RANSAC方法對匹配結果進行檢核，剔除錯誤的匹配，得到初始可靠的同名點。然后利用初始可靠同名點構建Delaunay三角網(wǎng)，得到左、右影像上初始同名三角網(wǎng)，作為后續(xù)密集匹配的基礎。三組影像初始同名三角網(wǎng)構建分別如圖5(a)、圖5(b)、圖5(c)所示。從中可以看出，初始三角網(wǎng)基本覆蓋立體像對重疊區(qū)域或基本覆蓋建筑物主體部分。但由于初始同名點數(shù)目較少，初始三角網(wǎng)較為稀疏，且形狀不規(guī)則，存在部分狹長三角形。通過本文迭代三角網(wǎng)約束加密匹配后，得到最終同名三角網(wǎng)分別如圖6(a)、圖6(b)、圖6(c)所示，對應的同名點分別如圖7(a)、圖7(b)、圖7(c)所示，鑒于文章篇幅，僅對TS=50的結果圖進行顯示。從中可以看出，經(jīng)過本文算法密集匹配后，初始三角網(wǎng)得到了加密，優(yōu)化，且同名點均勻分布。

圖5 初始三角網(wǎng)

圖6 TS=50密集匹配后生成的三角網(wǎng)

圖7 TS=50密集匹配得到的同名點

圖8為面積閾值TS分別取50、40、30、20條件下三組實驗影像密集匹配結果統(tǒng)計圖，分別從同名點數(shù)目、三角網(wǎng)數(shù)目、迭代循環(huán)次數(shù)、運行時間四個方面進行統(tǒng)計。從中可以看出，①相比較初始SIFT匹配結果，密集匹配后同名點及三角網(wǎng)數(shù)目大幅度增多；②對于每組實驗影像，隨著面積閾值的減小，同名點數(shù)目、三角網(wǎng)數(shù)目、運行時間逐次遞增，其中圖4(a)同名點數(shù)目增加幅度最大，TS=20時同名點數(shù)目從初始1614增加到23575，提高了13倍，大大提高了匹配點的數(shù)量；③隨著面積閾值的遞減，初始循環(huán)次數(shù)無規(guī)律可言，這是由于本文算法迭代過程中對同名點整體構網(wǎng)，部分三角形具備不固定性，而當?shù)螖?shù)開始遞增時，說明網(wǎng)型開始趨于規(guī)整；④運行時間上，圖4(b)影像所用時間最少，圖4(a)影像所用時間最長，這與影像大小、同名點的數(shù)目與迭代的次數(shù)均相關，整體可以看出，本文算法具有較高的運算效率。

圖8 不同面積閾值條件下密集匹配結果統(tǒng)計

圖9為不同面積閾值條件下三組實驗影像匹配正確率統(tǒng)計圖，實驗過程中結合RANSAC方法與目視判斷對匹配結果進行錯誤判讀。從中可以看出，圖4(a)影像匹配正確率高于圖4(b)、圖4(c)影像，這主要是由于后兩組影像存在尺度變化、紋理單一且重復等問題。此外，隨著面積閾值的減小，匹配的正確率隨之降低，原因在于本文算法利用三角網(wǎng)作為匹配傳播和區(qū)域約束的載體，因此隨著面積閾值的減小，迭代次數(shù)的增加，產(chǎn)生的錯誤傳播及累積現(xiàn)象。后續(xù)可以通過對上一次匹配結果進行錯誤剔除再進行下一次迭代匹配，減少錯誤傳播，提高匹配正確率。

圖9 不同面積閾值條件下密集匹配正確率

綜上所述，本文算法對存在旋轉、尺度變化、視角變化、重復紋理的近景影像，都能取得可靠的密集匹配結果，具有較好的適應性。較傳統(tǒng)的稀疏匹配，密集匹配結果能更好地反映近景影像場景的細節(jié)信息，可為后續(xù)基于影像的高精度三維建模提供較好的基礎數(shù)據(jù)。

3.2 不同算法對比分析

為了進一步驗證本文算法的有效性，本文還實現(xiàn)了文獻[13]中的密集匹配方法。文獻[13]同樣采用三角網(wǎng)內(nèi)插點漸進匹配方法，與本文算法不同的是，該算法假定左、右影像上同名三角形的重心點即為同名點，在此基礎上，通過多波段灰度相關和極限約束進行驗證，剔除非同名點。實驗過程中涉及與本文相同的數(shù)據(jù)或參數(shù)，如初始同名點、相關窗口大小、相關系數(shù)閾值等設置均與本文相同。針對圖4中三組實驗影像，文獻[13]密集匹配結果統(tǒng)計如表1所示。根據(jù)同名點數(shù)目及后續(xù)運行速度，匹配過程中人工設置迭代次數(shù)，在迭代次數(shù)少于本文算法的情況下，運行時間、同名點數(shù)目及其對應三角網(wǎng)的數(shù)目均多于本文算法。但是從圖10密集匹配得到的同名三角網(wǎng)來看，部分同名點簇團狀分布，均勻性差，這是由于一些面積較大的同名三角形重心未滿足約束條件，匹配失敗，而面積較小的三角網(wǎng)則不斷的漸進匹配。進而可以驗證本文算法增加虛擬同名點的必要性及結合面積和同名點作為約束迭代終止條件的優(yōu)越性。

表1 文獻[13]密集匹配結果統(tǒng)計

圖10 文獻[13]密集匹配得到的同名三角網(wǎng)

4 結論

針對傳統(tǒng)稀疏匹配難以滿足高精度三維建模需要，本文提出一種簡單有效的迭代三角網(wǎng)約束的近景影像密集匹配算法。該方法利用SIFT匹配獲取初始同名點構建初始Delaunay三角網(wǎng)，將其作為匹配基礎。以三角形重心作為匹配基元進行加密匹配，匹配過程中綜合利用多重約束條件確定最終同名點。每次迭代匹配過程中，依次遍歷三角網(wǎng)中所有的三角形進行匹配，將新產(chǎn)生的同名點和初始同名點整體進行構網(wǎng)。迭代過程中，以三角形面積為間接約束，以是否有新的同名點產(chǎn)生為直接約束作為迭代停止的條件。針對不同類型的近景影像對進行匹配實驗，驗證了本文算法對存在旋轉、尺度變化、視角變化、重復紋理的近景影像都具有較好的適應性，均能取得可靠的密集匹配結果，為后續(xù)精細的三維建模提供有利的基礎數(shù)據(jù)。

但該類基于同名三角形約束的影像匹配算法對于景深變化較大、且視角變化較大的復雜地物的近景影像的適用性有待進一步驗證，后續(xù)將針對該類型的影像數(shù)據(jù)進行針對性研究。

[1] 耿英楠.立體匹配技術的研究[D].長春:吉林大學,2014.

Geng Yingnan.Research on Stereo Matching Algorithms[D]. Changchun: Jilin University,2014.(in Chinese)

[2] Marr D, Poggio T. A Computational Theory of Human Stereo Vision[J]. Readings in Cognitive Science, 1988, 204(1156):534-547.

[3] Mayhew J E W, Frisby J P. Psychophysical and Computational Studies Towards a Theory of Human Stereopsis[J]. Artificial Intelligence,1981, 17(1):349-385.

[4] Lowe D G.Distinctive Image Features form Scale-in-variant Keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.

[5] Morel J M, Guo Y. ASIFT:A New Framework for Fully Affine Invariant Comparison[J]. Siam Journal on Imaging Science,2009,2(2):438- 469.

[6] Herbert B, Andreas E. SURF: Speeded Up Robust Features[J]. Computer Vision and Image Understanding,2008,110(3): 346-359.

[7] Aurenhammer F, Voronoi Diagrams-A Survey of A Fundamental Geometric Data Structure[J]. ACM Computing Surveys,1991,23(3):345- 405.

[8] Tang L, Tsui H T, Wu C K. Dense Stereo Matching Based on Propagation With a Voronoi Diagram[C]∥Proceedings of India Conference on Computer Vision, Graphics and Image ProcessingⅢ, 2002: 230-240.

[9] Tsai V J D. Delaunay Triangulation in TIN Creation: An Overview and a Linear-time Algorithm[J]. International Journal of Geographical Information Science,1993,7(6):501-524.

[10] 李文龍.SURF算法和Delaunay三角網(wǎng)算法相結合的遙感圖像匹配技術的研究與實現(xiàn)[D].上海:華東理工大學,2013.

Li Wenlong. SURF Algorithm and Delaunay Triangulation Algorithm Combining Remote Sensing Image Matching Technology Research and Implementation[D]. Shanghai: East China Institute of Technology,2013.(in Chinese)

[11] Sun J, Zheng N N, Shum H Y. Stereo Matching Using Belief Propagation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(7):787- 800.

[12] 朱慶,吳波,趙杰.基于自適應三角形約束的可靠影像匹配方法[J].計算機學報,2005,28(10):1734-1739.

Zhu Qing,Wu Bo,Zhao Jie. A Reliable Image Matching Method Based on Self-adaptive Triangle Constraint[J].Chinese Journal of Computers,2005,28(10):1734-1739.(in Chinese)

[13] 朱紅,宋偉東,楊冬,等. 近景影像三角網(wǎng)內(nèi)插點密集匹配方法[J].測繪科學,2016,41(4):19-23.

Zhu Hong,Song Weidong,Yang Dong,et al. Dense Matching Method of Inserting Point into the Delaunay Triangulation for Close-range Image[J].Science of Surveying and Maping, 2016,41(4):19-23.(in Chinese)

[14] 竇慧麗.基于Delaunay三角剖分的指紋匹配算法[D].長春:吉林大學,2004.

Dou Huili. Fingerprint Matching Algorithm Based on Delaunay Triangulation[D]. Changchun: Jilin University,2004.(in Chinese)

[15] 吳波.自適應三角形約束下的立體影像可靠匹配方法[D].武漢:武漢大學,2006.

Wu Bo. A Reliable Stereo Image Matching Method Based on the Self-adaptive Triangle Constraint[D]. Wuhan: Wuhan University, 2006.(in Chinese)

[16] 來春風.數(shù)字近景影像稠密匹配方法研究[D].南京:南京師范大學,2012.

Lai Chunfeng.A Dissertation Submitted in Partial Fulfillment of the Requirements For the Degree of Master of Science[D]. Nanjing: Nanjing Normal University,2012.(in Chinese)

[17] 王競雪,宋偉東,韓丹,等. 邊緣視差連續(xù)性約束的航空影像特征線匹配算法[J].信號處理,2015,31(3):364-371.

Wang Jingxue,Song Weidong,Han Dan,et al.Feature Line Matching Algorithm for Aerial Image based on Continuity Constraint of Edge Parallax[J].Journal of Signal Processing,2015,31(3):364-371.(in Chinese)

[18] 朱紅,宋偉東,譚海,等. Delaunay三角網(wǎng)優(yōu)化下的小面元遙感影像配準算法[J].信號處理,2016,32(9):1032-1038.

Zhu Hong,Song Weidong,Tan Hai,et al. A Tiny Facet Primitive Remote Sensing Image registration Algorithm Based on Optimized Delaunay Triangulation[J].Journal of Signal Processing,2016,32(9):1032-1038.(in Chinese)