SIMD在點(diǎn)云濾波處理中的應(yīng)用

柳紅凱　徐曉　郭浩

摘 要：為了進(jìn)一步提高.NET平臺(tái)數(shù)據(jù)處理能力，微軟新推出基于.NET平臺(tái)的新技術(shù)-SIMD。傳統(tǒng)濾波算法大都采用單指令單數(shù)據(jù)流對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行處理，然而由于三維激光掃描獲取的點(diǎn)云數(shù)據(jù)量極其龐大，單指令單數(shù)據(jù)的處理方式效率較低。文章在區(qū)域增長理論基礎(chǔ)上提出基于.NET平臺(tái)的單指令多數(shù)據(jù)流（SIMD）點(diǎn)云濾波處理新算法。該方法在對(duì)數(shù)據(jù)處理時(shí)通過一次指令同時(shí)進(jìn)行多個(gè)數(shù)據(jù)并行計(jì)算的方式達(dá)到提高效率的目的。通過對(duì)大量數(shù)據(jù)的運(yùn)算實(shí)例表明算法的高效性。

關(guān)鍵詞：.NET；SIMD；點(diǎn)云濾波；區(qū)域增長；單指令

引言

三維激光掃描技術(shù)（LIDAR）是繼GPS后又一新興的測(cè)量新技術(shù)，能夠在很短的時(shí)間內(nèi)獲得大量地形表面信息，這些LIDAR點(diǎn)云數(shù)據(jù)除了包括地面點(diǎn)外，還包括諸如汽車，房屋及植被等一些非地面信息。為了獲得真實(shí)的地面高程模型（DEM），需要將點(diǎn)云數(shù)據(jù)進(jìn)行濾波處理，將地面點(diǎn)和非地面點(diǎn)進(jìn)行分離，得到由地面點(diǎn)組成的DEM模型。

多年來，國內(nèi)外不少學(xué)者專注于點(diǎn)云的處理研究上[1-2]，并取得了不錯(cuò)的成果，具有代表性的有以下幾種濾波算法，如以內(nèi)插不規(guī)則三角形的算法[3]、基于形態(tài)學(xué)的算法[4-7]、基于多分辨率法[8]、基于坡度的算法、區(qū)域增長算法等，這些算法應(yīng)用到不同情況和不同地形條件下得到一些有價(jià)值的參考價(jià)值。區(qū)域增長算法由于適應(yīng)性廣，即使在復(fù)雜地形條件下也有強(qiáng)的適應(yīng)性，但是該方法是串行算法，當(dāng)目標(biāo)較大時(shí)，數(shù)據(jù)處理速度慢，因此在使用該方法時(shí)應(yīng)該盡量提高效率。

文章在區(qū)域增長算法的基礎(chǔ)上，提出融合SIMD技術(shù)，一次指令多個(gè)數(shù)據(jù)并行處理，使得大量點(diǎn)云數(shù)據(jù)時(shí)，極大的提高了效率。文章試驗(yàn)中，抽取大量的、不同數(shù)量的點(diǎn)云數(shù)據(jù)，通過計(jì)時(shí)對(duì)比，驗(yàn)證該理論算法的可行性和高效性。

1 區(qū)域增長濾波算法

區(qū)域生長（region growing）是指將成組的像素或區(qū)域發(fā)展成更大區(qū)域的過程。既是根據(jù)事先定義的準(zhǔn)則將像素或者子區(qū)域聚合成更大的區(qū)域?；痉椒ㄊ且浴耙唤M”種子開始，將與種子性質(zhì)相似（灰度級(jí)或顏色的特定范圍）的相鄰像素附加到生長區(qū)域的種子上。

這種算法的關(guān)鍵是一類元素總有一些相似的性質(zhì)，在點(diǎn)云數(shù)據(jù)濾波處理中就是為了分離地面點(diǎn)和非地面點(diǎn)，文章將數(shù)據(jù)元素的高程值作為同一性質(zhì)的集合用作數(shù)據(jù)分離度量。

1.1 區(qū)域增長法則

（1）選取圖像中的一點(diǎn)為種子點(diǎn)（種子點(diǎn)的選取需要具體情況具體分析）。（2）在種子點(diǎn)處進(jìn)行8鄰域或4鄰域擴(kuò)展（文章以8鄰域搜索），判定準(zhǔn)則是：如果考慮的像素與種子像素灰度值差的絕對(duì)值小于某個(gè)門限T，則將該像素包括進(jìn)種子像素所在的區(qū)域。（3）當(dāng)不再有像素滿足加入這個(gè)區(qū)域的準(zhǔn)則時(shí)，區(qū)域生長停止。

1.2 初始地面的生成

（1）確定格網(wǎng)尺寸L0。為了避免分割尺寸過大時(shí)數(shù)據(jù)的冗余和尺寸過小時(shí)格內(nèi)無點(diǎn)的情況，在對(duì)點(diǎn)云數(shù)據(jù)分割時(shí)一般將格網(wǎng)尺寸L0略大于點(diǎn)云的平均間隔L。（2）計(jì)算網(wǎng)格的平均高程。在只有一個(gè)點(diǎn)云數(shù)據(jù)的網(wǎng)格內(nèi)，將該點(diǎn)的高程值作為格網(wǎng)的高程值記錄下來；一個(gè)網(wǎng)格內(nèi)含有多個(gè)點(diǎn)時(shí)，以高程最小的點(diǎn)為基準(zhǔn)，將超過閾值的其他點(diǎn)刪除，最后記錄內(nèi)所有高程點(diǎn)的平均值；一個(gè)格網(wǎng)沒有點(diǎn)時(shí)，進(jìn)行8鄰域搜索選取最低點(diǎn)作為該格子的高程值。（3）生成地面模型。選擇合適種子點(diǎn)，按照生長準(zhǔn)則，不斷進(jìn)行8鄰域搜索和合并得到地面模型。區(qū)域增長算法是串行性質(zhì)的算法，區(qū)域增長算法就顯得效率較低，文章就是針對(duì)提高區(qū)域增長算法效率而引入多數(shù)據(jù)并行處理的新算法。

2 單指令多數(shù)據(jù)流（SIMD）

單指令多數(shù)據(jù)流（Single Instruction Multiple Data，簡(jiǎn)稱SIMD），能夠一次性獲得多個(gè)操作數(shù)，并把它們保存成一組指令集。以同步方式，在同一時(shí)間內(nèi)執(zhí)行同一條指令。

以乘法指令為例，單指令單數(shù)據(jù)流（SISD）的CPU對(duì)乘法指令譯碼后，先訪問內(nèi)存，取得第一個(gè)操作數(shù)；之后再一次訪問內(nèi)存，取得第二個(gè)操作數(shù)，隨后才能進(jìn)行求積運(yùn)算。而在SIMD中，CPU對(duì)乘法指令譯碼后，一次性獲得所有操作數(shù)進(jìn)行運(yùn)算，隨后進(jìn)行求積運(yùn)算。兩者技術(shù)區(qū)別代碼如下：

通過對(duì)比我們可以了解到這個(gè)特點(diǎn)使SIMD特別適合于大量點(diǎn)云數(shù)據(jù)的處理。SIMD是通過一次指令并行處理多個(gè)數(shù)據(jù)元素的方式處理數(shù)據(jù)，該方法在點(diǎn)云這種大數(shù)據(jù)量的處理中有獨(dú)特的優(yōu)勢(shì)。

3 算法

由于點(diǎn)云數(shù)據(jù)量極大，傳統(tǒng)單數(shù)據(jù)流算法較難提高效率，文章在區(qū)域增長思想的基礎(chǔ)上，結(jié)合了SIMD的編程技術(shù)，提高點(diǎn)云處理效率。

文章算法的基本思想如下：

（1）結(jié)合經(jīng)驗(yàn)對(duì)區(qū)域進(jìn)行塊劃分（block）。在進(jìn)行區(qū)域劃分時(shí)盡量保證分割區(qū)域的連續(xù)性。而格網(wǎng)尺寸的大小一般以最大建筑物的尺寸為參考。并且盡量將區(qū)域分成大小不同的規(guī)則形狀（如矩形，正方形等）。（2）將塊格網(wǎng)化。根據(jù)點(diǎn)的平面坐標(biāo)位置，將點(diǎn)云區(qū)域格網(wǎng)劃分，至于格網(wǎng)的大小以點(diǎn)云的密度為參考，一般保證每個(gè)小方格內(nèi)含有1、2個(gè)點(diǎn)即可。（3）選擇適當(dāng)?shù)姆N子點(diǎn)。遍歷塊中的點(diǎn)數(shù)據(jù)選擇高程值最小的點(diǎn)作為種子點(diǎn)數(shù)據(jù)。（4）以8鄰域法則進(jìn)行種子搜索。將鄰域點(diǎn)與種子點(diǎn)的高程值作比較，當(dāng)差值小于閾值時(shí)即為地面點(diǎn)且作為新的種子點(diǎn)，當(dāng)差值大于閾值時(shí)就以非地面點(diǎn)濾除。直到?jīng)]有符合條件的點(diǎn)數(shù)據(jù)時(shí)生長結(jié)束。在.NET Vector 數(shù)據(jù)處理時(shí)，首先利用Vector 泛型類中public static int Length { get； }只讀屬性獲得計(jì)算機(jī)cpu支持的位數(shù)，將搜索到的數(shù)據(jù)點(diǎn)的高程值（文章將高程值定義為float類型）壓入堆棧，然后對(duì)堆棧中的數(shù)據(jù)進(jìn)行并行處理（文章計(jì)算機(jī)設(shè)計(jì)成4數(shù)值并行處理）。

4 實(shí)驗(yàn)

文章選取大淑村掃描的1580645個(gè)點(diǎn)進(jìn)行對(duì)比計(jì)算，通過新算法與原算法進(jìn)行對(duì)比。為了驗(yàn)證新算法的高效性，文章選取傳統(tǒng)的區(qū)域增長算法與新算法對(duì)去除體外孤點(diǎn)進(jìn)行試驗(yàn)對(duì)比，通過計(jì)時(shí)對(duì)比兩者之間的差距。為了論證新算法的高效性，文章還通過錄入不同數(shù)量的點(diǎn)進(jìn)行比較，進(jìn)一步證明新算法的高效性。

5 結(jié)束語

文章算法是針對(duì)傳統(tǒng)算法對(duì)點(diǎn)云數(shù)據(jù)處理中效率性進(jìn)行討論，并對(duì)并行算法的關(guān)鍵技術(shù)做了詳細(xì)解釋。針對(duì)大量的、不同算法、不同數(shù)量的點(diǎn)云數(shù)據(jù)處理進(jìn)行計(jì)時(shí)對(duì)比試驗(yàn)，結(jié)果表明新改進(jìn)的算法確實(shí)可以將點(diǎn)云處理效率提高數(shù)倍。

參考文獻(xiàn)

[1]王勇.地面激光掃描數(shù)據(jù)濾波研究[D].鄭州：解放軍信息工程大學(xué)，2012.

[2]王金亮，陳聯(lián)君.激光雷達(dá)點(diǎn)云數(shù)據(jù)的濾波算法述評(píng)[J].遙感技術(shù)與應(yīng)用，2010，25（5）：632-638.

[3]李卉，李德仁，黃先鋒，等.一種漸進(jìn)加密三角網(wǎng)LIDAR點(diǎn)云濾波的改進(jìn)算法[J].測(cè)繪科學(xué)，2009，34（3）：39-40，216.

[4]張熠斌，隋立春，曲佳，等.基于數(shù)學(xué)形態(tài)學(xué)算法的機(jī)載LIDAR點(diǎn)云數(shù)據(jù)快速濾波[J].測(cè)繪通報(bào)，2009，5：16-18，65.

[5]李鵬程，王慧，劉志青，等.一種基于掃描線的數(shù)學(xué)形態(tài)學(xué)LIDAR點(diǎn)云濾波方法[J].測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2011，28（4）：274-277，282.

[6]張熠斌，隋立春，曲佳，等.基于數(shù)學(xué)形態(tài)學(xué)算法的機(jī)載LIDAR點(diǎn)云數(shù)據(jù)快速濾波[J].測(cè)繪通報(bào)，2009，5：16-18，65.

[7]孫美玲，李永樹，陳強(qiáng)，等.基于掃描線的漸進(jìn)式形態(tài)學(xué)機(jī)載LIDAR點(diǎn)云濾波[J].光電工程，2013，40（11）：71-75.

[8]萬幼川，徐景中，賴旭東，等.基于多分辨率方向預(yù)測(cè)的LIDAR點(diǎn)云濾波方法[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2007，32（11）：10-11.

[9]成曉倩，趙紅強(qiáng).基于區(qū)域生長的LIDAR點(diǎn)云數(shù)據(jù)濾波[J].國土資源遙感，2008，78（4）：6-8，21.

作者簡(jiǎn)介：柳紅凱（1989-），男，碩士研究生，主要從事地理三維激光點(diǎn)云數(shù)據(jù)處理方面研究。