欒鑒

安徽省地質(zhì)測繪技術(shù)院 安徽 合肥 230022

引言

隨著科技進步，測繪工作中應(yīng)用的工具和技術(shù)越來越先進，測繪數(shù)據(jù)呈現(xiàn)出爆發(fā)式發(fā)展，通過并行技術(shù)對測繪數(shù)據(jù)處理成為現(xiàn)階段研究重要方向。并行技術(shù)的應(yīng)用可以實現(xiàn)大規(guī)模的計算工作，通過將計算任務(wù)分解為多個小任務(wù)，由不同處理器進行同時處理，快速提高測繪數(shù)據(jù)的處理速度，大幅縮短測繪數(shù)據(jù)計算時間，提高測繪工作的生產(chǎn)效率。

1 MPI并行技術(shù)

MPI作為常見并行編程環(huán)境，在石油開采、測繪學(xué)、生物醫(yī)學(xué)、核工業(yè)、空氣動力學(xué)等領(lǐng)域中廣泛使用。MPI是信息傳遞接口標準，包括多個信息傳遞函數(shù)組合而成的函數(shù)庫，提供JAVA、C++、Fortran等專用接口。MPI吸收了P4、PVM、Express等消息傳遞的優(yōu)勢，具有較強的可移植性，可以在各類計算機中應(yīng)用。同時具有良好的拓展性，可以大規(guī)模并行，提供異步通信功能，為MPI發(fā)展奠定了良好的基礎(chǔ)[1]。在測繪工作中使用地理測繪技術(shù)、遙感影像測量技術(shù)以及激光點云技術(shù)等獲取數(shù)據(jù)，并使用對應(yīng)的算法進行計算解析，獲取目標數(shù)據(jù)。但由于算法耗時長，計算效率較低，通過MPI并行技術(shù)的使用有利于加快計算效率，縮短計算耗時，更有利于提高信息傳遞和數(shù)據(jù)共享的效率，為測繪工作的開展提供有力支持。

2 測繪數(shù)據(jù)處理中MPI并行技術(shù)的應(yīng)用

2.1 并行ICP算法

在測繪工作中廣泛使用激光點云技術(shù)進行測繪，對點云配準主要采取ICP算法進行，但由于ICP算法實時性差、計算量大，需要使用ICP進行多幅點云配準，浪費較多時間。因此將MPI并行技術(shù)和ICP算法相結(jié)合，提高配準速度。ICP算法配準是對兩幅點云配準前搜索點云中最近的匹配點，通過搜索最近點對，計算參考點云中任一點到目標點云的距離，通過對比選擇最近一點作為對應(yīng)點。最近點的算法計算量較大，電數(shù)多時耗時更長。使用MPI進行多幅點云并行配準，從而有效縮短耗時。點云配準耗時原因在于獲取相鄰變換矩陣，充分利用MPI計算相鄰變換矩陣，再行交換，最終獲取全局變換矩陣。如下圖所示為并行匹配七幅點云。其中P1/P2/P3表示并行進程1/2/3，Ii代表點云，每個進程先讀取點云數(shù)據(jù)，并行進程能獲得相鄰變換矩陣Ti-（i+1），Ii代表分局變換矩陣，即和第1幅點云變換矩陣。在進程分局變換矩陣后，進程要對最末各分局變換矩陣聚合廣播。每個進程通過共享獲得全局變換矩陣。每個進程獲得的全局變換矩陣將對應(yīng)點云坐標變換至源點云坐標系之下，最終實現(xiàn)并行輸出。

圖1 并行匹配多幅點云

由于點云PCD文件存儲包括二進制和文本兩種，文本類型點云數(shù)據(jù)耗時長，用MPI并行讀取可以縮短耗時。讀取80幅文本類型PCD文件，耗時200.35s，由于進程數(shù)增加，耗時會隨之減少，在進程數(shù)為16時，耗時達到最低值19.25s。當進程數(shù)逐漸增加，加速比降低。二進制點云數(shù)據(jù)進行讀取，速度更快，80幅點云數(shù)據(jù)讀取耗時只需要1s左右[2]。點云配準為了更準確控制配準過程，取消各項迭代終止閾值，迭代次數(shù)設(shè)定30次。不管迭代結(jié)果，次數(shù)達到30次即停止。如下表所示，在串行配準中進程數(shù)增加，耗時逐漸減少，直至達到進程數(shù)16，達到耗時最小值和加速比最大值。當進程數(shù)進一步增加時，耗時也會逐漸增加。由于服務(wù)器有16個核，借助于超線程技術(shù)對CPU進行拓展。當進程數(shù)達到16和32時，并行效率接近。隨著進程數(shù)的增加，由于進程之間出現(xiàn)競爭資源的關(guān)系，造成加速比降低。服務(wù)器計算資源十分有限，進程數(shù)的增加均分計算資源，造成相對效率的持續(xù)降低。因此要根據(jù)計算機核數(shù)選擇配準最優(yōu)進程，避免進程數(shù)超過CPU數(shù)量。

表1 點云并行配準分析

2.2 并行球諧綜合法計算

根據(jù)地球重力模型對大地水準面、重力異常、擾動位以及垂線偏差等進行計算均使用球諧綜合法。由于計算量大使用地球重力場模型對格網(wǎng)重力場元進行計算，計算過程耗時長。任何一個質(zhì)點都受到重力作用，重力位W計算公式為：

式中，W為重力位，V為引力位，Q為離心力位。

但由于地球內(nèi)部密度不均勻，表面不規(guī)則，重力位只是理想狀態(tài)下，正常重力位（）和真實重力位存在擾動位（T）差距，計算公式為：

正常重力位是按照橢球重力位參考計算，按照球諧函數(shù)，引力位可以通過下式計算：

式中，r， ， 表示地心向徑、余緯、經(jīng)度；GM表示地心引力常數(shù)；n和m表示階和次；Snm和Cnm表示規(guī)格化引力位系數(shù)；Cn0x表示正常引力位系數(shù)；R表示橢球長半徑；Pnm（cos）表示締合勒讓德函數(shù)。

為了讓計算效率得到提高，先對地球重力場元計算公式進行求解，引入數(shù)組避免傳統(tǒng)算法重復(fù)計算的問題。MPI并行技術(shù)可以并行計算大規(guī)模重力場元的計算。進行格網(wǎng)重力場元計算時采取逐緯度計算，重力場元的緯度帶保持獨立關(guān)系，數(shù)據(jù)并行模式將緯度帶作為基本單元。MPI并行技術(shù)可以對格網(wǎng)進行分解，形成多個緯度帶，緯度帶分配給多個進程計算[3]。由于緯度帶獨立運行，計算過程中不需要通信。計算結(jié)束后可以將進程結(jié)果收集至根進程，通信開銷相對較小，可選擇主從模式并行，方便于管理。分解格網(wǎng)可以選擇維度循環(huán)分解以及維度分塊分解，維度分塊分解由每個進程負責對緯度帶的處理，維度循環(huán)分解，由進程連續(xù)負責多個緯度帶。MPI數(shù)據(jù)收集按照進程號進行收集，先將進程存放至數(shù)組中，逐個存在進程數(shù)據(jù)。使用維度分塊的分解模式直接輸出收集結(jié)果。根據(jù)維度循環(huán)分解模式對結(jié)果的收集需要變換順序才能輸出，運算量更大，因此建議選擇維度分塊分解模式。

2.3 并行SIFT算法

SIFT作為一種精度高的算法，在圖像配準中廣泛使用，由于SIFT算法較為復(fù)雜，耗時較多，實時性差，要想讓SIFT配準速度加快，使用MPI并行技術(shù)予以處理。SIFT算法包括圖像采樣、高斯平滑濾波、高斯差分金字塔等步驟，各個步驟之間并行難度較大。SIFT算法處理數(shù)據(jù)是將圖像分塊處理，每塊作為獨立塊搜索特征點，最終集合匹配所有特征點。在數(shù)據(jù)并行中，除了收集分塊特征點外，每個步驟可以單獨完成進程，不需要通信，大幅減少通信開銷。同時還要考慮圖像大小和硬件條件，選擇最合適的進程數(shù)量，快速完成圖像配準。SIFT算法并行數(shù)據(jù)方便于編程，通信需求少，并行程度更高。將圖像分為九塊，每塊對應(yīng)著進程1～9處理，最后收集特征向量，完成特征向量提取。為了減少圖像邊緣對于特征提取產(chǎn)生的影響，每個進程都可以經(jīng)過平均分塊，高和寬均可以增加適當寬度，作為重疊分割。由于SIFT算法特殊，圖像分割后，提取特征因素較多，包括特征點剔除、分塊大小等因素，因此重疊分割寬度并不具備明確標準。剔除邊緣特征點即設(shè)定閾值，剔除圖像邊緣特征。提取特征向量后需要匹配圖像特征向量，將圖像分為四塊，分別將各圖像進程提取的特征向量收集到進程內(nèi)。由進程獨立對特征向量匹配，最后得到匹配特征向量。提取特征向量采取并行方式，匹配特征向量采取串行方式。在特征向量不多的情況下，特征樹串行匹配可以滿足用戶需要[4]。但特征向量較多時，特征樹串行匹配將耗費較多時間。各個進程完成特征提取后，將特征收集并發(fā)送至進程，每個進程需要建立圖像特征點，將圖像特征樹的點和進程提到圖像特征匹配，將進程獲得的分塊特征點收集至進程中，匹配和提取并行。

SIFT算法和MPI并行配準主要經(jīng)過圖像分塊、封裝特征、發(fā)送特征以及拆封特征幾個部分。對圖像分塊后提取圖像的特征量，形成特征描述子。進程可以獲得特征點的坐標，將其轉(zhuǎn)換至原圖坐標系。由于MPI采取通信，各進程提取特征量按照順序封裝數(shù)組，再通信。各進程對應(yīng)特征向量封裝數(shù)組后，發(fā)送給其他進程。由于提取特征量不同，發(fā)送特征量前需要先發(fā)送個數(shù)，根據(jù)特征個數(shù)預(yù)留儲存空間。特征向量發(fā)送至指定進程中，函數(shù)將特征向量發(fā)送至給所有進程，收集完畢后進行拆封，按照順序保存至對應(yīng)結(jié)構(gòu)中。其中圖像分塊會對匹配特征點產(chǎn)生影響，將特征匹配點通過圖形方式表示數(shù)據(jù)，特征匹配點隨著分塊數(shù)量增多而減少。由于不同進程對應(yīng)圖像特征數(shù)量不同，進程特征匹配耗時也明顯不同，總耗時是由匹配最大值決定。將匹配最大值衡量匹配效率。在進程數(shù)為16時，耗時最低，加速比達到最大值。當進程數(shù)為4時，特征匹配和耗時減少最明顯。隨著進程數(shù)增加，耗時逐漸增加。進程數(shù)越多分攤了特征樹搜索任務(wù)，充分建構(gòu)特征樹。隨著進程數(shù)增加，各進程占用資源減少，耗時增加。耗時增加也影響到特征樹匹配的效率。因此按照PCU個數(shù)進行并行進程數(shù)量的確定，可達到最低耗時，雖然特征樹并行匹配耗費更多通信資源，但匹配速度得到明顯提升。

4 結(jié)束語

綜上所述，測繪工作處理測繪工具時應(yīng)用MPI并行技術(shù)，能夠充分利用計算機資源并行處理多進程，大幅提高數(shù)據(jù)處理效率。主要體現(xiàn)在格網(wǎng)重力場元測繪數(shù)據(jù)、攝影遙感影像數(shù)據(jù)、激光點云數(shù)據(jù)的處理上，通過和SIFT算法、ICP算法以及球諧綜合法的并行計算，有效縮短計算耗時，提高數(shù)據(jù)處理效率，為測繪工作提供支持。