SIMD在點云濾波處理中的應用

柳紅凱　徐曉　郭浩

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

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

引言

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

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

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

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

區(qū)域生長（region growing）是指將成組的像素或區(qū)域發(fā)展成更大區(qū)域的過程。既是根據(jù)事先定義的準則將像素或者子區(qū)域聚合成更大的區(qū)域。基本方法是以“一組”種子開始，將與種子性質(zhì)相似（灰度級或顏色的特定范圍）的相鄰像素附加到生長區(qū)域的種子上。

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

1.1 區(qū)域增長法則

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

1.2 初始地面的生成

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

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

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

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

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

3 算法

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

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

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

4 實驗

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

5 結(jié)束語

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

參考文獻

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

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

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

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

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

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

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

[8]萬幼川，徐景中，賴旭東，等.基于多分辨率方向預測的LIDAR點云濾波方法[J].武漢大學學報（信息科學版），2007，32（11）：10-11.

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

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