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

鄒亞未，劉玉紅

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

一、引 言

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

四、試驗與結(jié)果分析

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

表1 試驗數(shù)據(jù)列表

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

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

表3 參與平差連接點統(tǒng)計情況

圖1 img006和img007影像匹配結(jié)果局部效果圖

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

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

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

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

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

五、結(jié)束語

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

參考文獻：

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

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

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

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

[5] 紀松.多視匹配策略與優(yōu)化方法研究[D].鄭州:信息工程大學(xué),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.多核程序設(shè)計技術(shù)——通過軟件多線程提升性能[M].北京：電子工業(yè)出版社，2007.

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