王海濤,張 丹,張 娜

(1. 中國地質(zhì)大學(xué)(武漢)國家地理信息系統(tǒng)工程技術(shù)研究中心，湖北 武漢 430074； 2. 湖北省基礎(chǔ)地理信息中心(湖北省北斗衛(wèi)星導(dǎo)航應(yīng)用技術(shù)研究院)，湖北 武漢 430074)

Voronoi圖在無人機航空影像匹配中的應(yīng)用

王海濤1,2,張 丹2,張 娜2

(1. 中國地質(zhì)大學(xué)(武漢)國家地理信息系統(tǒng)工程技術(shù)研究中心，湖北 武漢 430074； 2. 湖北省基礎(chǔ)地理信息中心(湖北省北斗衛(wèi)星導(dǎo)航應(yīng)用技術(shù)研究院)，湖北 武漢 430074)

提出了顧及無人機航空影像地面覆蓋范圍的影像空間位置Voronoi圖的生成方法，利用基于局部特征不變算子在多視影像匹配過程的可傳遞特性，使用影像的Voronoi圖鄰域關(guān)系開展多視影像的匹配，既保證了多視影像間匹配點的重疊度，又提高了多視影像間的匹配速度。

無人機航空攝影；多視影像匹配；Voronoi圖

無人機航空攝影是快速獲取地理空間數(shù)據(jù)的一種重要手段[1]，多使用導(dǎo)航型GNSS技術(shù)攜帶小面幅數(shù)碼相機對地觀測，獲取的影像數(shù)量也較多。無人機航空攝影后處理的首要工作是影像間同名點匹配，考慮影像關(guān)系計算的可靠性[2-3]，需要在多視影像間匹配具有多度重疊的同名點。隨著無人機航空攝影的廣泛應(yīng)用，對其后處理的實時性要求越來越高，多視影像間同名點的快速匹配需要考慮兩個方面：①兩幅影像間的快速匹配；②多視影像間匹配策略的優(yōu)化。

對于兩幅影像間的匹配，從無人機航空影像的特點來看，匹配算法要適應(yīng)：①影像旋轉(zhuǎn)；②仿射變形；③尺度差異；④色彩差異；⑤投影變形等。該方面的算法在David Lowe提出的SIFT(scale-invariant feature transform)[4]算法的基礎(chǔ)上不斷改進，形成了基于局部特征不變算子[4-12]算法來處理影像間不同形變的匹配。兩幅影像間基于特征匹配的速度優(yōu)可從：①特征描述改進[13]；②特征降維[8-9]；③匹配搜索策略優(yōu)化[14]；④特征內(nèi)在關(guān)系分析[15-16]等方面來實現(xiàn)。

基于局部特征不變算子影像匹配首先是特征點提取，這樣同名點就包含在已知的特征點集內(nèi)，因此多視影像間匹配同名點是在已知特征點集內(nèi)開展的，那么已知特征點集內(nèi)的同名點匹配過程有何特性呢？經(jīng)分析，多視影像間特征點集內(nèi)的同名點匹配具有“可傳遞性”，這樣可通過建立多視影像間的鄰域關(guān)系來提高匹配速度。無人機航空攝影同時獲取影像中心點位置信息，可以利用這一信息建立多視影像的鄰域關(guān)系，Voronoi圖是按照最鄰近原則對目標(biāo)的一種空間剖分[17-19]，被廣泛應(yīng)用于幾何信息的相關(guān)領(lǐng)域[20-22]。本文使用影像空間位置信息生成影像間Voronoi圖，并以此構(gòu)建多視影像的鄰域關(guān)系，利用特征點集內(nèi)同名點匹配具有可傳遞的特性來提高多視影像間的匹配速度。

1 多視影像間匹配分析

從無人機影像變形來考慮，匹配算法要適應(yīng)影像間的仿射變形、色彩差異等，SIFT[4]算法是一種有效的算法，該算法首先提取特征點，通過統(tǒng)計特征點的梯度直方圖來確定特征點主方向，并以主方向?qū)μ卣鼽c生成128維矢量特征(如圖1所示)。從影像關(guān)系計算的可靠性來考慮[2-3]，需要在多視影像間匹配多度重疊的同名點，即每張影像與鄰域內(nèi)有重疊的影像進行匹配(如圖2所示)，隨著影像的重疊度的增大，每張影像與其有重疊的影像數(shù)量也在增多，后處理的計算量也大大增加。

圖1 SIFT算法特征提取與描述

圖2 無人機多視影像重疊關(guān)系(隨著影像間重疊的增大，每張影像需要匹配的鄰域影像也在增多)

基于局部特征不變算子的影像匹配首先是特征提取，這樣同名點就包含在已知的特征點集內(nèi)，因此多視影像間匹配同名點是在已知特征點集內(nèi)開展，那么特征點集內(nèi)的同名點匹配過程有何特性，下面以具體實例來分析，如圖3所示，地面點P在影像3615、3614、3562、3561上成像點為Pi(i=1～4)，如影像3615上的點P1與影像3614上的點P2匹配成功，影像3614上的點P2與影像3562上的點P3匹配成功，這樣影像3615與影像3562不需要匹配，影像3615上的點P1即可傳遞到影像3562上的點P3，此時點P已有3度重疊，點P的匹配還可以在影像3615的其他鄰域影像(如影像3561)間傳遞。

2 Voronoi圖與多視影像匹配

無人機航空攝影同時獲取影像中心點坐標(biāo)，影像間具有明確的空間關(guān)系，可借助影像的空間位置關(guān)系及特征點集匹配的“可傳遞性”實現(xiàn)多視影像間的快速匹配。Voronoi圖是按照最鄰近原則對目標(biāo)的一種空間剖分[18-19]，已被廣泛應(yīng)用于幾何信息的相關(guān)領(lǐng)域[20-22]，在此利用影像空間位置生成的Voronoi圖來實現(xiàn)多視影像匹配的優(yōu)化調(diào)度。

圖3 無人機多視覺影像匹配分析

圖4(a)所示為使用某區(qū)域無人機航空影像中心點坐標(biāo)生成的Voronoi圖，借助Voronoi圖可給出每張影(如影像E)與其他影像的鄰域關(guān)系，即有公共邊的影像作為其鄰域影像，這樣借助特征點匹配的可傳遞性，多視影像間匹配僅需要每張影像與其Voronoi圖領(lǐng)域影像匹配即可實現(xiàn)快速匹配。

直接使用影像中心點坐標(biāo)生成影像的Voronoi圖存在一些問題，如圖4(a)所示，影像A與影像B間沒有重疊，但是具有公共邊，這樣B也被列入影像A的鄰域影像，同樣影像C和影像D也存在同樣問題。需要對Voronoi圖生成算法加以改進，本文采用增加輔助點的方式來實現(xiàn)，方法如下(如圖4(b)所示)：

(1) 輔助候選點計算：以影像中心點坐標(biāo)建立輔助正方形，輔助正方形的四個角點作為輔助的候選點。

(2) 輔助點選?。簩γ繌堄跋竦?個候選點，判別是否在其他影像輔助正方形的覆蓋范圍內(nèi)，如不在選取為輔助點。

圖4(c)所示為使用增加輔助點生成的影像領(lǐng)域關(guān)系的Voronoi圖，這樣計算影像鄰域關(guān)系更加合理。

圖4 無人機航空影像Voronoi圖生成

3 多視影像間匹配工作的開展

3.1 多視影像匹配流程

由第1節(jié)分析可知，使用SIFT特征點集在多視影像間匹配，同名點匹配具有“可傳遞性”，利用這一特性并結(jié)合影像間的Voronoi圖關(guān)系可以提高多視影像間匹配速度，如圖4(c)所示，影像G僅需要與影像H、K、M、N匹配即可，不需要與其有重疊度的所有影像(圖4(c)圓圈范圍內(nèi)的影像)匹配。

如圖4(c)所示，影像G的鄰域包括影像H，影像H的鄰域包括影像G，這樣影像G與影像H僅需要匹配一次，當(dāng)影像G與影像H匹配完成后將匹配結(jié)果保存，當(dāng)影像H與影像G匹配時，直接使用已記錄的結(jié)果即可?？紤]利用多核并行計算的開展，在影像匹配前建立影像關(guān)系表(以影像G、H為例，當(dāng)影像G的關(guān)系中有影像H時，影像H的關(guān)系表中不需要包含影像G)。由本節(jié)分析可知，利用影像Voronoi圖關(guān)系開展多視影像匹配，考慮影像匹配的雙向性及多核心并行計算的開展，本文的影像匹配流程如圖5所示。

圖5 多視影像匹配流程

3.2 多視影間匹配的可靠性處理

設(shè)影像特征點的SIFT描述子(歸一化的128位描述子)為H=(h1,h2,…,h128)，則兩幅影像間點i、j的相似度可采用歐氏距離來計算

(1)

(2)

除采用距離比值方法量判斷特征點之外，本文還采用核線約束[17]、雙向一致性、匹配唯一性原則來提高匹配的可靠性，具體要求見表1。

表1 點匹配策略表及要求

圖6中，Ai、Bj為左右影像特征點，如點A1與B1滿足雙向一致性要求，但如點A3對應(yīng)目標(biāo)點B4，B4對應(yīng)目標(biāo)點A4，不滿足雙向一致性要求。圖7中，Ai、Bj為左右影像特征點，如點A1僅有一個同名點B1滿足唯一性要求；如點A3對應(yīng)兩個目標(biāo)點B4、B5，因此A3不滿足唯一性要求。

對于核線約束，采用同名點計算本征矩陣F的方式實現(xiàn)，設(shè)左右影像同名點Al、Ar的坐標(biāo)為xl、xr，則xlFxr=0，通過已知點同名點計算F并剔除錯誤點。

多視影像在匹配的“傳遞”過程中仍然有錯誤存在，SIFT點描述子H，對其相似度可采用歐氏距離，也可使用相關(guān)系數(shù)計算(式3)，對多視影像匹配的多度同名點計算相關(guān)系數(shù)進一步加以驗證(在此取C≥0.85)。

(3)

圖6 匹配雙向一致性

圖7 匹配唯一性

4 試驗分析

傳統(tǒng)多視影像匹配是對每張影像在一定半徑內(nèi)搜索與其有重疊的影像匹配(在此稱為半徑搜索匹配，簡稱R-匹配)，本文利用影像Voronoi圖鄰域方式開展多視影像匹配(在此稱為V圖鄰域匹配，簡稱V-匹配)。

從多視影像匹配的可靠性要求來考慮，R-匹配可有效保證影像點匹配的多度重疊，針對V-匹配是否可保證影像點匹配的多度重疊的問題，本文選取3組樣例數(shù)據(jù)(見表2)來驗證匹配效率和特征點的重疊度，結(jié)果如圖8和表3所示。試驗表明，R-匹配與V-匹配同名點的重疊度相當(dāng)，但是后者可以大幅度提高匹配速度，匹配效率的加速比與影像的重疊度有關(guān)，加速比隨著影像間的重疊度增大而增大。

表2 樣例影像數(shù)據(jù)信息

圖8 匹配點重疊度分析

匹配時間/sR-匹配V-匹配加速比220278.152701419.2320907727.14

5 結(jié) 論

從無人機航空影像的特點來看，匹配算法要適應(yīng)：①影像旋轉(zhuǎn)；②仿射變形；③尺度差異；④色彩差異；⑤投影變形；⑥視點變化等?；诰植刻卣鞑蛔兯阕拥挠跋衿ヅ涫且环N有效的方法，該方法提取的特征點在多視影像間的同名點匹配過程具有“可傳遞性”，利用這一特性，使用影像空間位置信息生產(chǎn)顧及影像覆蓋范圍的Voronoi圖，并構(gòu)建了影像的鄰域關(guān)系，這樣構(gòu)建的影像鄰域關(guān)系更加合理，然后利用影像Voronoi圖鄰域關(guān)系開展多視影像間匹配，既保證了匹配同名點重疊度，又提高了多視影像間的匹配效率。

[1] 李德仁,李明. 無人機遙感系統(tǒng)的研究進展與應(yīng)用前景[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2014, 39(5): 505-513.

[2] 李德仁,袁修孝.誤差處理與可靠性理論[M].2版.武漢：武漢大學(xué)出版社,2012.

[3] HARTLEY R, ZISSERMAN A. Multiple View Geometry in Computer Vision[M].Cambridge: Cambridge University Press,2004.

[4] LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints[J].Internation Journal of Computer Vision,2004,60(2):91-110.

[5] HERBERT Bay, ANDREAS Ess, TINNE Tuytelaars, et al. SURF: Speeded Up Robust Features[J]. Computer Vision and Image Understanding, 2006,110(3): 404-417.

[6] YAN K, SUKTHANKAR R. PCA-SIFT:A More Distinctive Representation for Local Image Descriptors[J].IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004,2(2): 506-513.

[7] MIKOLAJCZYK K, SCHMID C. A Performance Evaluation of Local Descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10):1615-1630.

[8] WANG Zhenhua, FAN Bin, WU Fuchao. Local Intensity Order Pattern for Feature Description[J]. International Conference on Computer Vision, 2011,23(5):603-610.

[9] ABDELHAKIM A E, FARAG A A. CSIFT: A SIFT Descriptor with Color Invariant Characteristics[C]∥2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006). New York, NY, USA: IEEE, 2006.

[10] MIKOLAJCZYK K, TUYTELAARS T, SCHMID C, et al. A Comparison of Affine Region Detectors[J]. International Journal of Computer Vision,2005,65(1-2): 43-72.

[11] MIKOLAJCZYK K, SCHMID C. Scale & Affine Invariant Interest Point Detectors[J]. International Journal of Computer Vision,2004,60(1):63-86.

[12] MOREL J M, YU G, ASIFT: A New Framework for Fully Affine Invariant Image Comparison[J]. SIAM Journal on Imaging Sciences, 2010, 2(2)：438-469.

[13] OJALA T, PIETIKINEN M, MAENPT. Multiresolution Gray-scale and Rotation Invariant Texture Classification with Local Binary Patterns[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(7):971-987.

[14] MIKOLAJCZY K, MATAS J G. Improving Descriptors for Fast Tree Matching by Optimal Linear Projection[C]∥IEEE International Conference on Computer Vision. [S.l.]: IEEE, 2007.

[15] GRABNER M, GRABNER H, BISCHOF H. Fast Appro-ximated SIFT[C]∥Asian Conference on Computer Vision. Hyderabad, India:[s.n.], 2006: 918-927.

[17] HAN J H,PARK J S. Contour Matching Using Epipolar Geometry[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2000,22(4):358-370.

[18] AURENHAMMER F. Voronoi Diagram: A Survey of a Fundamental Geometric Data Structure[J]. ACM Computing Surveys,1991,23(3):345-405.

[19] GOLD C M. The Meaning of ‘Neighbour’[C]. Lecture Notes in Computing Science. Berlin:Springer-verlag,1992: 200-235.

[20] 潘俊，王密，李德仁. 基于顧及重疊的面Voronoi圖的接縫線網(wǎng)絡(luò)生成方法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2009, 34(5): 518-521.

[21] 喬朝飛，趙仁亮，陳軍,等. 基于Voronoi內(nèi)鄰近的等高線樹生成法 [J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2005, 30(9): 801-804.

[22] 李佳田,康順,李曉娟,等. 寬泛地理注記的投放模型[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2015, 40(1): 20-25.

ApplicationofVoronoiDiagraminUAVAerialImageMatching

WANG Haitao1,2,ZHANG Dan2,ZHANG Na2

(1. National Engineering Research Center for Geographic Information System, Wuhan 430074, China; 2. Hubei Geomatics Information Center(Hubei Institute of BeiDou Satellite Navigation Applied Technology)， Wuhan 430074,China)

A method of generating Voronoi diagram of the spatial location of UAV aerial images is presented in this paper. This method takes the ground coverage of images into account. A matching algorithm based on local invariant features, which is transferable during the matching procedure between multi-view images, combined with Voronoi diagram of images is used to improve the matching speed and the degree of overlapping of corresponding points between multi-view images.

UAV aerial photography;multView image matching;voronoi diagram

王海濤,張丹,張娜.Voronoi圖在無人機航空影像匹配中的應(yīng)用[J].測繪通報，2017(11)：118-122.

10.13474/j.cnki.11-2246.2017.0360.

P23

A

0494-0911(2017)11-0118-05

2017-08-09

國家高科技研究發(fā)展計劃863(2013AA122104)；測繪地理信息公益性行業(yè)科研專項(201512012)

王海濤(1976—)，男，博士生，高級工程師，主要研究方向為攝影測量與計算機視覺。E-mail:306550757@qq.com