低空無人機影像匹配像對的提取方法

任超鋒，彭曉東

(1. 長安大學 地質(zhì)工程與測繪學院，陜西 西安 710054;2. 長安大學 西部礦產(chǎn)資源與地質(zhì)工程教育部重點實驗室，陜西 西安 710054)

在傳感器技術高速發(fā)展的信息化測繪時代，利用無人機(unmanned aerial vehicle，UAV)低空遙感平臺快速地獲取地表數(shù)據(jù)成為研究的熱點[1]。目前，除了搭載單鏡頭相機進行垂直航空攝影外，機載傾斜多相機系統(tǒng)的發(fā)展也已成為城市三維重建的主要數(shù)據(jù)源。由于無人機影像像幅較小，相機數(shù)量多，導致測區(qū)內(nèi)的航片數(shù)量劇增。因此，一種通用且快速的無人機影像匹配算法，成為制約低空無人機影像數(shù)據(jù)生產(chǎn)的關鍵步驟之一。

總體上可將無人機影像匹配分為三步：第一步，選擇待匹配像對，提取各影像特征點；第二步，對當前像對進行粗匹配，獲取初始同名點對；第三步，對當前像對進行精匹配，剔除同名點對中的誤配點。

針對第一步，brute-force search是最穩(wěn)定、最可靠的待匹配像對選擇方法，它采用窮舉法判定數(shù)據(jù)集內(nèi)所有可能存在的像對，也稱為盲匹配，但該方法效率太低，不具有可操作性。文獻[2-4]利用傾斜相機的檢校參數(shù)及定位定向系統(tǒng) (Positioning and Orientation System，POS系統(tǒng)) 數(shù)據(jù)，計算各個子相機的粗略外方位元素，利用平均高計算每張影像在“水平面”的腳印范圍，進而確定相鄰影像是否重疊。文獻[5]則是利用下視影像進行空三獲取精確外方位元素后，進而擴展至各個子相機，獲取其相應外方位元素。上述幾種方法的核心環(huán)節(jié)是采用地面平均高方式計算每張影像的腳印圖，進而判定像對是否具有重疊區(qū)。然而，受地形起伏及飛行平臺穩(wěn)定性等綜合因素影響，采用這類方法往往會遺漏一定數(shù)量的待匹配像對，使后續(xù)的自動空中三角測量存在嚴重隱患。此外，傾斜相機設計參數(shù)及測區(qū)先驗知識也不宜獲得，進一步降低該類方法的適用性。當選擇一對影像作為待匹配像對后，需分別對其進行特征點提取。文獻[2]對比常用的SIFT[6],ASIFT[7],AIF[3]等3種特征提取算子。其區(qū)別在于是否根據(jù)相機的設計參數(shù)，將“傾斜”影像糾正為近似“水平”影像，然后在“水平”影像上提取SIFT特征，之后再根據(jù)子相機相對關系將特征點反算回原始影像。采用這類方法，可有效提高特征點數(shù)量，改善匹配效果，但直接在原始影像上提取SIFT特征，理論更嚴密，且試驗結(jié)果表明，直接在原始影像上提取特征點，其數(shù)量及分布也可滿足精度需求。

針對粗匹配階段，文獻[8]提出一種利用GPU進行雙向窮舉法進行同名點粗匹配，但該方法耗時隨特征點數(shù)量的提升呈指數(shù)增長。文獻[9]根據(jù)多維空間最臨近搜索方法，獲取當前特征點的同名像點，但需要首先創(chuàng)建特征空間搜索索引，兩種方法各有適用范圍。最后，利用隨機一致性約束算法[10](Random Sample Consensus, RANSAC)剔除同名點粗差，完成同名像點匹配。

鑒于此，本文設計一種通用的無人機影像匹配算法，從選擇待匹配像對入手，以影像的初始空間位置關系為依據(jù)，完成部分像對的影像匹配。之后，根據(jù)同名點列表跟蹤連接點，利用連接點信息對遺漏的像對進行自動識別，同時構建CPU與GPU混合模式，以提高影像粗匹配效率。最后選取常規(guī)無人機影像與傾斜影像進行對比試驗，以證實本文方法的適應性和高效性。

1 無人機影像快速匹配流程

本文提出的無人機影像快速匹配算法流程，如圖1所示。

圖1 無人機影像快速匹配算法流程圖

1)導入POS信息中的影像位置信息，計算當前第i張影像與之后所有影像投影中心之間的空間距離，并按照降序排列；

2)以第i張影像為左影像，以降序影像集合為右影像，順次構成待匹配像對；

3)對當前選擇的像對進行粗匹配與精匹配，獲取其同名點列表；

4)判定當前匹配過程中，是否已經(jīng)超過最大搜索深度；

5)利用兩兩匹配結(jié)果，跟蹤測區(qū)內(nèi)連接點關系；

6)根據(jù)連接點結(jié)構信息，搜索遺漏的待匹配像對；

7)完成遺漏像對影像匹配，并輸出匹配結(jié)果。

2 無人機影像快速匹配算法

2.1 選擇待匹配像對

由于無人機影像有效覆蓋范圍小、數(shù)量龐大，且影像間的重疊關系隨著地形、地貌的變化而變化，因此以最小的計算量，穩(wěn)健、可靠的選擇待匹配像對是影響匹配算法效率的關鍵環(huán)節(jié)?？臻g距離上越近的影像具有重疊區(qū)的可能性越高，因此本文首先根據(jù)影像初始POS信息中的X,Y,Z坐標，計算當前影像與其后所有影像的歐式空間距離，然后按照距離關系進行降序排列，之后，依次完成當前影像與排序影像之間的影像匹配。

如圖2所示，假設測區(qū)包含n張影像，影像i為當前選擇的左影像，影像jk,k∈[0,7]為影像i之后的待選右影像。對所有jk影像按照距離進行降序排列，結(jié)果為(j2

圖2 待匹配像對選擇方法

2.2 像對同名點匹配

當確定一組像對后，分別提取其SIFT特征及特征向量，并利用特征向量的距離比值作為同名像點的相似性判定測度，獲取像對的初始同名點列表，之后利用RANSAC剔除誤配點。其中，獲取初始同名點列表總體上可分為兩種：窮舉法、構建索引法。

窮舉法依次完成左影像至右影像特征向量之間的距離對比，若左、右影像中特征向量數(shù)目均為N，則該算法的時間復雜度為O(N2)。為了進一步提高該算法效率，本文利用GPU對窮舉法匹配進行并行加速。

構建索引法首先利用K-D樹建立右影像特征向量的空間索引，再計算特性向量之間的距離比值。該算法耗時主要包含兩部分，構建索引和計算距離比值，其時間復雜度為O(N+N)。窮舉法耗時隨著特征數(shù)量增加呈指數(shù)增加，前者適合特征點數(shù)量較少情況，后者適合特征點數(shù)量較多情況。本文采用窮舉法與構建索引法相組合的方法完成同名點的初始匹配，并分別以GPU粗匹配與CPU粗匹配進行標識，其算法流程如圖3所示。

圖3 像對同名點匹配流程

2.3 識別遺漏待匹配像對

先驗知識的不確定性會造成測區(qū)內(nèi)遺漏一定數(shù)量的待匹配像對。根據(jù)連接點的結(jié)構信息，自動識別遺漏的待匹配像對。首先，按照文獻[12]中數(shù)據(jù)結(jié)構算法，獲得的同名點列表中跟蹤搜索連接點。在同一連接點內(nèi)，按照排列計算方式，任意選擇兩幅影像構成待匹配像對。若該像對從未匹配過，則該像對為遺漏待匹配像對。

如圖4中所示，假設測區(qū)內(nèi)的4張影像A，B，C，D已完成兩兩匹配。即AB，BC，CD像對同名點列表已知。之后進行連接點跟蹤獲得4度連接點P，該連接點在影像A，B，C，D上的像點坐標依次為pa，pb，pc，pd。從連接點的結(jié)構信息中可知，A，B，C，D影像對同一地面點P均有成像，即同一連接點內(nèi)所有影像之間均具有重疊度，因此，從該連接點內(nèi)任意提取兩張影像即可構成待匹配像對。如圖4所示，AC，AD，BD為遺漏的待匹配像對。

圖4 識別遺漏待匹配像對

按照圖4所示方法，依次對所有連接點進行識別，獲取所有遺漏像對信息，按照2.2節(jié)方法完成剩余像對的匹配工作。

3 試驗與分析

3.1 試驗數(shù)據(jù)

為了驗證本文算法的有效性，試驗選取典型的3種相機數(shù)據(jù)：單相機、雙相機、五相機影像數(shù)據(jù)。其中單相機為索尼ILCE-5100拍攝的下視影像。雙相機由2臺索尼ILCE-QX1相機組成，構成一左、一后排列，采集數(shù)據(jù)時按照航線往返飛行，模擬出傾斜四相機影像。五相機由5臺索尼ILCE-5100相機組成，1臺采集下視數(shù)據(jù)，4臺分別采集前、后、左、右傾斜影像數(shù)據(jù)。試驗數(shù)據(jù)的相關屬性描述見表1。硬件平臺為Windows7 64位操作系統(tǒng)、處理器為i7-4910MQ、主頻2.9 GHz、顯卡為英偉達Quadro K2100M 2G獨立顯存、內(nèi)存32 GB。本文匹配算法基于VC++ 2015、CUDA8.0進行開發(fā)。

表1 試驗數(shù)據(jù)影像描述

3.2 試驗過程與分析

3.2.1 影像分塊大小對SIFT特征提取效率的影響

當獲取原始影像后，首先依次提取影像的SIFT特征。文獻[6]提出一種GPU并行加速的SIFT特征提取算子SiftGPU，提升SIFT特征算子的計算效率。然而由于顯卡存儲資源有限，SiftGPU算子無法直接對原始影像進行處理。本文采用分塊提取的策略，將原始影像劃分為規(guī)則格網(wǎng)，依次提取格網(wǎng)內(nèi)影像的SIFT特征，之后將所有SIFT特征進行合并。為了能將影像劃分為整數(shù)格網(wǎng)，格網(wǎng)寬度設置為2的倍數(shù)。以100張索尼ILCE-5100影像為例，統(tǒng)計不同格網(wǎng)大小時SIFT特征提取的總耗時(包含影像讀取)，按平均值計算其單張影像耗時如表2所示。

表2 不同格網(wǎng)大小時影像SIFT特征提取時間

從表2可知，格網(wǎng)越大單張影像的SIFT特征提取效率越高，其主要原因在于格網(wǎng)劃分太小單次提取SIFT特征無法充分發(fā)揮顯卡的運算能力。因此在顯存允許前提下，SIFT特征提取時格網(wǎng)越大越好?；诒?影像尺度信息及表2結(jié)果，本文算法將所有原始無人機影像劃分4塊分塊子影像提取SIFT特征。

3.2.2 特征點數(shù)量對粗匹配效率的影響

由SIFT算法原理可知，SIFT特征點是在差分高斯差分金字塔影像中進行提取，最終獲得的特征點也分布于不同的高斯差分金字塔影像中。通常，一張普通無人機影像可提取數(shù)萬個特征點，對于大部分應用而言數(shù)據(jù)量過大，因此實際使用中會根據(jù)具體的應用需求對特征點進行取舍。SiftGPU在高斯差分金字塔影像中采用從上往下的方式，分層保留提取的特征點，直至滿足用戶設置的特征點數(shù)量。

當獲取像對SIFT特征點之后，即可按照GPU并行、或者CPU索引兩種方式進行像對粗匹配。為了評價特征點數(shù)量對粗匹配效率的影響，本文依次設置保留2 000、4 000、6 000、8 000、10 000個特征點，從雙相機影像中提取200組(400張)影像，按照圖3所示流程，分別統(tǒng)計兩種粗匹配方式的耗時，如圖5所示。

從圖5中可知，當特征點數(shù)量逐漸增加時，GPU并行方式耗時急劇增高，而CPU索引方式耗時與特征點數(shù)量成線性比例關系，且兩種方式的特征點閾值約為7 000個。

3.2.3 算法可靠性對比分析

驗證本文匹配方法的可靠性，分別采用盲匹配、腳印圖和本文方法對表1所示的3種數(shù)據(jù)進行匹配，分別統(tǒng)計待匹配像對數(shù)量、最終匹配成功的像對數(shù)量、并計算其相應的可靠度。本文將待匹配像對完成匹配后，獲得的同名點數(shù)量不小于16對時認定為具有重疊區(qū)的像對，結(jié)果如表3所示。

由于盲匹配是將測區(qū)所有影像進行兩兩匹配，可靠性最高，其結(jié)果可作為測區(qū)數(shù)據(jù)的真實情況進行對比分析，因此其可靠度為100%。其它兩種方法的最終匹配結(jié)果與盲匹配的結(jié)果進行比值，計算其相應的可靠度。由表3可知，按照腳印圖方法選擇待匹配像對時會有少量遺漏像對，其原因主要在于該算法對輸入的POS數(shù)據(jù)、地形參數(shù)、及相機設計信息高度相關，而這些數(shù)據(jù)的不準確性導致遺漏了一定數(shù)量的待匹配像對。與腳印圖算法相比，本文算法的可靠性均得到提升。其中，單相機數(shù)據(jù)提升2.4%，雙相機數(shù)據(jù)提升5.3%，五相機數(shù)據(jù)提示24.3%。可靠度提升的原因在于本文算法選擇的待匹配像對數(shù)量較多，同時無效匹配也相應減少，且相機鏡頭數(shù)量越多，可靠度提示幅度越大。此外，括號內(nèi)為自動識別的遺漏待匹配像對，可見本文的識別遺漏像對算法有效，進一步提升算法的可靠度。

圖5 不同特征點數(shù)量的粗匹配耗時

單相機雙相機五相機盲匹配腳印圖本文方法盲匹配腳印圖本文方法盲匹配腳印圖本文方法待匹像對/個108 34516 85524 042499 50078 93162 96424 042323 111411 080最終像對/個8 5188 3128 518(775)22 39917 41518 600(1 397)41 51430 50840 583(3 905)可靠度/%10097.610010077.783.010073.597.8

3.2.4 算法效率對比分析

為了評價本文算法的效率，提取SIFT特征時將特征點數(shù)量設置為2 000個，分別統(tǒng)計特征提取、粗匹配、精匹配階段的耗時，結(jié)果如表4所示。

表4 3種匹配方法分階段耗時 s

分析表4可知，特征提取階段用時比較固定，主要與影像數(shù)量相關，精匹配環(huán)節(jié)所占時間也非常少，匹配算法中耗時最多的為粗匹配過程，因此，決定無人機影像匹配算法效率的關鍵環(huán)節(jié)在于，是否能夠高效選出真正具有重疊度的待匹配像對。本文算法總體耗時與腳印圖算法相比略有增加，其中單相機耗時增加19.6%，五相機耗時增加16.4%。由于雙相機為一種特殊類型相機，同一站點的4張傾斜影像通過往返飛行而得，造成同一組影像之間空間姿態(tài)的不確定性增大，因此利用POS數(shù)據(jù)計算所得腳印圖精度也更低。而本文算法不考慮影像的空間姿態(tài)，得到的待匹配像對總體數(shù)量上少于腳印圖算法，所以總體耗時減少了16.2%。

4 結(jié)束語

本文針對低空無人機影像的自動匹配算法進行研究，試驗選取典型的3種影像數(shù)據(jù)，結(jié)果表明：

1)本文算法具有較高的適用性。不需要相機、地形、航攝等參數(shù)即可自動完成無人機影像匹配。

2) 本文算法具有較高的可靠性。與腳印圖算法相比，單相機數(shù)據(jù)提升2.4%，雙相機數(shù)據(jù)提升5.3%，五相機數(shù)據(jù)提示24.3%。

3)本文算法效率適當。與腳印圖算法相比，單相機耗時增加19.6%，五相機耗時增加16.4%，雙相機耗時減少16.2%。