基于多核CPU的無人機影像連接點并行匹配方法

鄒亞未，劉玉紅

(1. 東華理工大學 測繪工程學院，江西 撫州 344000； 2. 中國測繪科學研究院，北京 100830)

一、引 言

近年來，無人機低空平臺因其具有機動靈活、響應快、使用成本低、維護操作簡單等技術特點，成為低空攝影測量與遙感研究領域的熱點[1]。影像連接點匹配是無人機影像攝影測量處理中的核心問題之一，由于匹配算法自身的復雜性，消耗的計算資源多、運行速度慢，在大規模無人機影像處理中該問題表現得更為突出。針對無人機影像匹配問題，文獻[1—3]介紹了基于SIFT算法的無人機影像匹配方法，但是由于SIFT算子計算速度慢，單純利用該方法不能獲得較高的匹配效率。近年來出現的并行處理技術為大幅提高處理效率提供了有效的解決方案，主要為“高性能集群并行處理技術”和“大規模分布式處理技術”，典型的商業系統有Pixel Factory、INPHO’s Photogrammetric System、PCI Geomatics公司的Geo-Imaging Accelerator(GXL)等。但是這些系統所依賴的硬件平臺成本昂貴、軟件開發過程復雜，無法滿足某些領域對處理平臺小型化、移動化的要求[4-5]。

由于無人機影像具有重疊度不規則、像幅較小、像片數量多、傾角過大且傾斜方向沒有規律等缺點，導致其匹配存在一定困難。在保證匹配算法可靠、穩定的前提下，為提高無人機影像匹配的效率，引入了多核處理器并行處理的思想，提出了一種基于幾何約束條件的影像連接點匹配方法，多組試驗表明了該方法的高效性。

二、基于幾何約束的無人機影像連接點匹配方法

1. 基于SURF特征的影像初匹配

SIFT算子是計算機視覺和攝影測量領域非常著名的算子，由于其具有抗旋轉、尺度不變等特性，在多個領域有著廣泛應用。但SIFT算法也存在檢測和匹配速度慢、對視角變化較敏感等缺點。2006年提出的SURF(speeded up robust feature)算法[6],除在可重復性、魯棒性方面優于現有方法外，還能夠獲得較快的計算速度，因此在圖像配準、圖像拼接、檢索等領域有著更大的應用價值。盡管SURF特征匹配有著上述優良特性，但是該算法本身是在基準影像上和搜索影像上同時提取特征點，然后進行特征描述和匹配。這就產生了兩個問題：一是影像特征點匹配是全局遍歷計算搜索，相對于其他常見灰度相關算法，特征描述和匹配花費了大量時間，效率不高；二是由于低空影像像幅小，SURF算法在匹配多度連接點(3度以上)時因為重疊區域提取的特征點不同而導致匹配穩定性不高。然而，在大區域、多像幅的低空遙感數據處理中，匹配速度的快慢非常關鍵，直接影響著處理效率，更多的多度連接點有利于低空影像的區域網平差，因此單純地直接利用SURF算法并不能滿足低空遙感影像匹配處理的要求。

有鑒于此，在利用SURF特征匹配抗旋轉、尺度不變等特性的同時，能夠提高匹配效率則是比較理想的結果。該方法在進行匹配的兩張影像的金字塔頂層，首先進行SURF特征匹配，這樣大大降低了計算量，縮小了搜索范圍，提高了匹配速度；然后利用基于多項式的隨機采樣法(RANSAC)進行粗差剔除，該方法能夠較好地剔除較大粗差點；最后把匹配結果映射到影像底層，利用匹配點對建立起兩張影像的像方空間仿射變換關系。該匹配建立的影像間像方關系，大大縮小了后續影像精匹配的搜索范圍，提高了匹配速度。

2. 幾何約束條件的影像連接點匹配思路

在基準影像與搜索影像建立起仿射變換關系后，利用仿射變換系數可以將搜索影像窗口糾正采樣到基準影像的像方空間坐標系下，使基準影像和搜索影像的共軛實體在像方空間上一致，即兩者不存在旋轉、幾何變形和尺度變化，之后就可以直接進行相關系數的匹配。首先在基準影像上提取一定個數的特征點，并把特征點的位置映射到影像金字塔的各層；其次在影像金字塔頂層，通過兩者的仿射變換關系，把特征點對應在搜索影像的匹配窗口采樣糾正到基準影像上；然后在基準影像的像方空間坐標系下，進行相關系數匹配，保留匹配成功的點對，同時對匹配結果進行多項式迭代剔除粗差，并把最終解算的多項式系數作為基準影像與搜索影像間新的仿射變換關系；最后進行下層影像匹配，迭代直至底層影像，并進行最小二乘匹配，提高匹配精度。

三、基于多核CPU的并行匹配算法設計

在無人機影像數據處理中，很多算法在每張影像上完成相同的計算處理，并且在處理任務之間不需要進行數據交互，算法本身具有天然的可并行性。采用單幅影像作為處理任務的基本單元，以該幅影像與其滿足重疊范圍要求的一組相鄰影像間的多組匹配作為一個匹配單元，那么在特征提取和匹配的環節上，每張影像完成相同的計算處理，任務之間不需要進行數據交換，是獨立的執行單元。針對無人機影像連接點匹配算法的并行化設計，有以下兩個關鍵點：

1) 匹配單元的確定。根據每張影像對應的POS數據記錄，易知該影像攝影時刻攝站的位置和姿態，即影像的外方位元素；同時相機的焦距，地面的概略高程是已知的，把影像4個角點的像坐標，代入共線條件方程的物方模型，如式(1)所示，可獲得影像4個角點的地理坐標，如此，可獲得每張影像的地理范圍；然后對每張影像的地理范圍和其他影像范圍求交并且計算兩者的重疊度，把滿足航行、旁向重疊度要求的影像記作該影像的鄰接影像；遍歷所有影像，得到了每張影像所對應的鄰接影像，把影像與其鄰接的多張影像的匹配任務作為一個匹配單元。之所以這樣設計而沒有選擇兩張影像間的匹配作為匹配單元，是因為根據影像連接點匹配的流程，在更高的任務級并行的層次上，單元之間沒有數據交換和沖突，是獨立的，最終形成了和影像數目相同個數的匹配單元。

(1)

2) 任務并行執行的策略。在匹配單元確定以后，匹配任務的數量也就確定了。本文根據CPU處理核的數量對匹配任務進行劃分和并行計算，具體方法如下：首先獲取CPU處理核的個數，然后開辟相同個數的處理線程，并將各線程指定到相應的CPU處理核上，各線程按順序選擇匹配單元并同時執行匹配任務，當其中任意線程匹配任務執行完畢后，則選擇下一匹配單元執行任務，直至所有匹配任務完成。

為了測試匹配算法的并行性能，通過并行加速比與并行效率來評價[8]，具體定義如下

(2)

式中，參數p表示CPU處理器的數目或者并行線程的數目；T1為串行程序運行的時間；Tp為并行處理時間；Sp為并行加速比，其理論值為p；Ep為并行效率，其理論值為1。

四、試驗與結果分析

為了驗證上述方法的有效性，選取了兩個并行計算試驗平臺和兩套無人固定翼飛機航拍數據。數據1的基本情況為：平均航高為430 m，共7個航帶397張影像，影像大小5616像素×3744像素，影像的航向重疊度為70%～80%，旁向重疊度為30%～40%，測區主要為城區人工建筑物。數據2為山西柳林地區無人機航拍影像，平均航高360 m，影像大小7360像素×4912像素，影像分辨率為0.05 m，共4個航帶，32張影像，該航拍影像像幅較大，分辨率高。試驗數據的詳細情況見表1。試驗平臺的硬件配置情況見表2，其中試驗平臺2包含了普通硬盤和固態硬盤。

表1 試驗數據列表

表2 試驗平臺硬件配置列表

為了驗證該匹配方法的可靠性及適應性，在試驗平臺1上，選取數據1、數據2進行多核并行匹配試驗。圖1為數據1中編號為img006和img007的兩張影像匹配結果的局部效果圖，圖2為數據2中上、下兩個航帶影像匹配的6度連接點。為了便于統計和分析，文中只對參與區域網平差的連接點進行了統計，數據1選取匹配的連接點總數為14 742個。其中，三度以上連接點5034個，經區域網平差共剔除了26個粗差點，整體平差的單位權中誤差為0.87像元；數據2選取匹配的連接點個數為1127個，其中，三度以上連接點409個，經區域網平差剔除了2個粗差點，整體平差的單位權中誤差為0.51像元；兩套數據區域網平差兩套數據試驗的具體情況見表3。從表3可知，該方法匹配正確率在99.8%以上，匹配可靠性高。

表3 參與平差連接點統計情況

圖1 img006和img007影像匹配結果局部效果圖

為了分析利用CPU處理核的數量變化對匹配效率的影響，利用數據2，在兩個試驗平臺上，進行了三組匹配試驗，其中在試驗平臺2上，針對匹配的原始影像數據在普通硬盤和固態硬盤兩種情況，分別進行了試驗。根據匹配算法利用不同數量的CPU處理核，得到統計分析結果如圖2、表4和表5所示。其中表4和圖2(a)給出了在試驗平臺1上，無人機影像連接點匹配算法利用1～4核并行處理條件下的處理時間、加速比和并行效率；表5和圖2(b)給出了在試驗平臺2上，匹配的原始影像數據在普通硬盤和固態硬盤兩種情況下，無人機影像連接點匹配算法利用1～8核并行處理條件下的處理時間、加速比和并行效率。

圖2 匹配的6度連接點效果圖

表5 CPU處理核數變化條件下的連接點并行匹配處理結果表(平臺2)

從表4和圖3(a)可知，在試驗1平臺上，在利用4個處理核時，影像匹配算法的加速比達到3.92，并行效率達到了98.3%；加速比與處理核的個數成近線性的關系；從表4和圖3(b)可知，在試驗平臺2上，原始影像數據在普通硬盤上時，當匹配利用的處理核個數在1～5個時，加速比與處理核的個數成近線性的關系，并行效率也在97%以上；而當匹配利用的處理核個數在6～8個時，加速比分別為5.22、5.37、5.38，即加速比變化不大，并行效率也迅速下降。原始影像數據在固態硬盤上時，加速比與處理核的個數一直成近線性的關系，當利用8個處理核時，加速比達到了7.41，并行效率仍在92%以上。從分析來看，原始影像數據在普通硬盤上，當利用處理核個數在5個以上時，匹配過程中的影像數據讀寫操作，已受限于硬盤的讀寫速度，使得加速比增加量變小；而在固態硬盤上，硬盤的讀寫速度對多核并行匹配影響較小。試驗表明，該并行算法能夠充分利用已有的計算資源，大幅提高處理效率，尤其是在高配置的硬件環境上，其加速效果更加明顯。

圖3 CPU處理核變化條件下的加速比和CPU并行效率圖

五、結束語

影像連接點匹配是無人機遙感影像幾何處理的一個關鍵步驟，高效的匹配算法對于無人機影像數據快速應急服務具有重要意義。本文提出的匹配方法具備了多核并行處理的高效率、SURF特征匹配的抗旋轉、尺度不變，相關系數匹配可靠性高，最小二乘匹配高精度等多種方法的優良特性，有著較大的應用潛力和價值。如何把多核并行處理的思想引入到無人機影像幾何處理的全過程，是下一步的研究重點。

參考文獻：

[1] 胡慶武,艾明耀,殷萬玲,等.大旋角無人機影像全自動拼接方法研究[J].計算機工程,2012,38(15)：152-155.

[2] 柯濤,張永軍. SIFT特征算子在低空遙感影像全自動匹配中的應用[J].測繪科學, 2012, 34(4): 23-26.

[3] 索效榮,齊苑辰.基于SIFT算法的無人機航空遙感影像匹配[J] .測繪科學, 2012,37(1):89-91.

[4] 李勁澎,龔志輝,張婷.無人機影像SIFT特征匹配的集群并行處理方法[J].測繪科學技術學報,2012,26(6):440 -444.

[5] 紀松.多視匹配策略與優化方法研究[D].鄭州:信息工程大學,2012.

[6] BAY H, ESS A， TUYTELAARS T, et al. SURF: Speeded up Robust Features[C]∥Proceedings of the 9th European Conference on Computer Vision.[S.l.]:ECCV,2006: 404-417.

[7] AKHTER S,ROBERT J.多核程序設計技術——通過軟件多線程提升性能[M].北京：電子工業出版社，2007.

[8] 鄒賢才，李建成，汪海洪，等．OpenMP并行計算在衛星重力數據處理中的應用[J]．測繪學報，2010，39(6)：636-641．