Voronoi圖在無人機航空影像匹配中的應用

王海濤,張 丹,張 娜

(1. 中國地質大學(武漢)國家地理信息系統工程技術研究中心，湖北 武漢 430074； 2. 湖北省基礎地理信息中心(湖北省北斗衛星導航應用技術研究院)，湖北 武漢 430074)

Voronoi圖在無人機航空影像匹配中的應用

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

(1. 中國地質大學(武漢)國家地理信息系統工程技術研究中心，湖北 武漢 430074； 2. 湖北省基礎地理信息中心(湖北省北斗衛星導航應用技術研究院)，湖北 武漢 430074)

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

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

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

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

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

1 多視影像間匹配分析

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

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

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

基于局部特征不變算子的影像匹配首先是特征提取，這樣同名點就包含在已知的特征點集內，因此多視影像間匹配同名點是在已知特征點集內開展，那么特征點集內的同名點匹配過程有何特性，下面以具體實例來分析，如圖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圖與多視影像匹配

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

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

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

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

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

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

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

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

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

3.1 多視影像匹配流程

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

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

圖5 多視影像匹配流程

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

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

(1)

(2)

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

表1 點匹配策略表及要求

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

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

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

(3)

圖6 匹配雙向一致性

圖7 匹配唯一性

4 試驗分析

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

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

表2 樣例影像數據信息

圖8 匹配點重疊度分析

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

5 結 論

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

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

[2] 李德仁,袁修孝.誤差處理與可靠性理論[M].2版.武漢：武漢大學出版社,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圖的接縫線網絡生成方法[J]. 武漢大學學報(信息科學版), 2009, 34(5): 518-521.

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

[22] 李佳田,康順,李曉娟,等. 寬泛地理注記的投放模型[J]. 武漢大學學報(信息科學版), 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圖在無人機航空影像匹配中的應用[J].測繪通報，2017(11)：118-122.

10.13474/j.cnki.11-2246.2017.0360.

P23

A

0494-0911(2017)11-0118-05

2017-08-09

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

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