平原地區機載激光雷達數據的抽稀算法分析

，，， ，

(1. 中科遙感科技集團有限公司, 天津 300384； 2. 國家測繪地理信息局重慶測繪院, 重慶 401120； 3. 吉林省航測遙感院, 吉林 長春 130051)

機載激光雷達(LiDAR)是獲取高精度地形數據的新型測量手段，可以快速獲取大面積高密度、高精度的三維點云數據，LiDAR數據擁有的高精度和高密度使其在生成地貌數據方面的應用得到飛速的發展和廣泛的應用，可用于數字高程模型制作、城市三維建模、災害環境監測等方面[1-3]。然而，高密度的數據導致數據量的大幅增加，幾千米的航帶，其點云量就達數千萬[4]，給等值線生成帶來了諸多不便，在等值線生成過程中，并無需全部表達所獲取的數據信息，僅需表達相應地貌特征所需要的數據點信息[5]，符合相應的地形地貌精度要求，特別是在地勢較平坦的平原地區。

在實際情況中，采樣地形的LiDAR數據越密集，生成的精度越高、等值線越逼真，但是在《機載激光雷達數據獲取技術規范》中沒有將地形類型和采樣密度相匹配，只規定點云數據的最大點間距不能大于1/2 DEM格網間距，若按此要求執行，在平原地區獲取的點云數據會存在大量的冗余數據。有的地區兼顧大比例尺測繪需要，按照1∶2000要求獲取點云數據制作等值線， 如此標準分幅的圖幅數據量更大，對設備的要求更高，需要超高性能設備才能完成生產作業。同時由地面點云數據生成的等值線往往呈鋸齒狀，有許多獨立的閉合環和曲折轉彎，在平原地區尤為突出；點云數據的平均坡度值也異常的高，平原地區的地面TIN模型也是如此，給平原地區生產等值線造成很大的困難[6]。

由于機載激光雷達數據的水平采樣距離相對于垂直方向精度較低，因此激光雷達存在很多噪點，要獲得鋸齒較少的等值線和更合理的坡度，必須去除點云數據中的噪點，同時還要最大可能地保留真實信息。因此，如何根據地形類別及特征要素對地形數據抽稀，獲得合理的、適于等值線生成的點云地形數據集，具有重要意義[7]。點云數據抽稀的主要目的是優化采樣密度和數據精度，以此得到符合要求的高精度DEM和等值線。在海量的點云數據中，如何能夠把地形要素特征點保留下來，剔除冗余的噪聲點，提高等值線生產效率和數據質量，是當前面臨的重要問題[8]。

本文通過對幾種抽稀算法的對比分析，結合平原地區激光點云的生產應用，總結出最優的、能夠滿足實際需求的抽稀算法，解決點云生產中的關鍵問題，提升生產效率，從而有利于點云數據的推廣和應用。

1 LiDAR數據抽稀算法

目前國內外關于LiDAR數據抽稀的算法按照其核心原理主要有系統抽稀、格網抽稀、TIN抽稀、坡度抽稀等算法。

1.1 系統抽稀

系統抽稀是按照固定間隔對數據點隨機抽稀。對于一個大樣本N，首先確定抽樣間隔，比如每10個點作為一個抽樣間隔，然后在這10個樣本點中隨機選擇一個樣本數據點。這種數據抽稀算法主要優勢是處理速度快，可以用來做快速顯示和縮略圖，適合于分析數據覆蓋范圍，制作區域快視圖；但是沒有顧及地形地貌特征信息[9]，如在TerraScan軟件中數據抽稀就采用該方法調用點云數據。

1.2 格網抽稀

格網抽稀是利用輸入的采樣間隔構建虛擬格網，然后按照處理規則只保留虛擬格網內一個點云數據點(規則如最低值、均值或最高值等)。其中虛擬格網的大小要依據數據點的密度和數據成果要求來設定，如果數據點的密度達到每平方米幾個點，則可以設定格網大小為1 m或更小。這種算法比較簡單高效，但無法顧及點云數據的地形地貌特征信息，這將在一定程度上降低數據的精度。隨著壓縮程度的增加，特征點被刪除的可能性也會增加，會丟失許多關鍵點數據。這種方法一般只應用于對精度要求較低的工程項目，或者對點云數據初步抽稀[10]。

1.3 TIN抽稀

TIN抽稀算法的原理是利用點云數據建立不規則三角網模型，分析判斷相鄰面的法線來確定點云點剔除還是保留。在平坦區域上點云數據點構成的三角網包含信息量最少，三角形構成面的法線向量趨近于平行，即法線向量的夾角越小地貌特征越一致，利用三角網的這個性質可以實現對點云數據的抽稀。該算法能夠較好地保留地形特征點，但是在判斷一點是否剔除時，需查找包含該點的三角面，在判斷不同三角面之間的夾角時，在一定程度上會降低數據處理的速度[11-13]。

1.4 坡度抽稀

首先利用點云數據構建TIN，在生成的TIN數據點中讀入第一個數據點，查找該點相鄰的三角形，計算每個三角面的坡度，求得這些三角面的平均坡度，依此確定坡度抽稀閾值，并求得最大坡度和最小坡度之差，即最大坡度差，通過最大坡度差與坡度抽稀閾值進行比較確定此點是否為特征地形點。該算法能夠較好地保留地形特征點，但坡度閾值確定時存在一定的不確定性，尤其是確定數據坡度臨界值時存在較大不確定性，會在一定程度上影響點云數據質量和數據處理速度[14]。

2 基于約束TIN節點的抽稀法

以上幾種算法中,系統抽稀和格網抽稀算法不能很好地保留地形特征信息,在一定程度上會降低點云數據精度。而基于TIN的抽稀算法和坡度抽稀算法,對于不同的地形采用動態閾值,能取得顯著的效果,也能更好地保留地形特征點，但是也難以得到理想的抽稀結果。

2.1 約束TIN節點

為了實現對平原地區點云數據的抽稀,本文提出基于約束TIN節點的抽稀算法。采用點云數據和特征數據構建TIN，利用約束條件判斷某個點云數據是否保留，通過剔除該點再構建TIN，判斷其點位置的內插值與源值的差值是否小于相應地形的容差，如果滿足要求就剔除該點，否則保留該點；在數據處理過程中特征數據始終參與構TIN，新構TIN網不能穿越特征要素，約束數據保證關鍵地形特征精度[15]。

由于地形地貌復雜多變，在一幅圖內也會變化多樣,按照坡度不同，可將地形分成平原、丘陵、山地及高山地，根據地形類別的中誤差要求設置不同地貌的抽稀容差，詳見表1，每類地形的容差按照1/3的中誤差進行取值，這樣既能更好地抽稀，又能保證數據精度。

表1 地形高程中誤差和容差分類

數學模型算法如下：

(1) 讀入所有點，生成TIN，依據地形類別確定容差值。

(2) 在TIN中讀入TIN網中第一個點P，找到與P點相關的三角形的節點，如圖1所示。

(3) 利用找到的節點重新構TIN，并提取P點在新TIN中的線性內插值P′。

(4) 計算P′與P的高程差值，與容差值對比，大于容差值保留，小于容差值則剔除，如圖2所示。

(5) 繼續遍歷所有TIN網中的點云數據，直到判斷完成為止。

(6) 判斷涉及遞歸運算，同時要考慮特征約束線的三角網。

特征約束線是對地形要素進行強制約束，點云構TIN不能跨越特征線，但是必須與特征線構成網，即點云與約束線相鄰的點必須一起構成三角網。圖3(a)是原始TIN數據，圖3(b)是在抽稀中未考慮約束要素，圖3(c)是經過本文方法抽稀后的TIN數據，在特征線位置處會出現錯誤，在后期補上約束線也會損失跨越特征線的點信息。

2.2 約束TIN節點算法的優化

在采用約束TIN節點算法時，每個點云的取舍均按照約束值判斷，但是存在剔除后在原TIN的內部插值高程變形超過約束值數倍的情況，內部變形如圖4所示，圖4(a)粗線網是原始點云的點構網，圖4(b)細線網是抽稀后點云的點構網，圖4(c)是二者的疊加圖，圖4(a)圓點處的點云(高程值：129.749 m)被抽稀掉，在圖4(b)圓點處內插值為129.586 m，兩次點值較差為0.163 m，然而在圖4(a)、(b)中三角形處，高程值分別是129.828 m和128.877 m，較差為0.951 m，超過附近點限差的5倍。

為了解決上述問題，在點云點的抽稀過程中，通過增加虛擬格網約束點的方式保證點云數據抽稀的精度，確定點云剔除還是保留，算法流程如圖5所示。虛擬格網間距的設置根據成果精度要求確定，在刪減過程中動態計算原值和新內差值的較差，超限則放入保留點數據集，如圖2所示，圖中黑點即為虛擬格網點。

為了提高運算速度，在剔除過程中只刪減三角形，不作增加處理；在第一次處理完成后，利用保留的點重新優化構建三角網，對剔除的點進行二次判斷，確認是否剔除；如果超限則補回到保留點中，并增加三角網，這樣既能保證處理精度，又能提高運算效率[16-17]。

3 抽稀方法應用分析

3.1 試驗區介紹

為了滿足實際生產的需要，選取任務區的部分激光點云數據進行試驗測試。試驗測區為地勢整體平緩，主要分為松遼河間過渡帶風沙覆蓋的平原、風沙覆蓋的傾斜平原、松嫩鹽漬化發育的低平原和松嫩湖沼漫布的低平原，地貌破碎復雜，鹽堿地貌隨處可見，屬于平原地區，試驗參數按照平原執行。試驗數據的點云間距約1.2 m，測區總面積5500 km2，典型地貌如圖6所示。

3.2 精度評估分析方法

(1) 為了更好地分析驗證各種抽稀算法，分別對系統抽稀、格網抽稀和TIN抽稀作基本分析，對坡度抽稀算法和約束TIN節點抽稀法進行重點分析。

(2) 采用ArcGIS 10.1軟件平臺完成數據成果測試、分析；數據樣本為隨機抽取的一幅具有水域特征線的數據，1∶1萬原始點云中地面點數據為5 346 712個點。

(3) 所使用的LiDAR點云是經過質檢部門驗收合格的點云數據， 使用分類好的點云數據作為基準數據，利用基準數據的地面點構建TIN，然后按照2 m格網間距線性內插生成DEM數據，行列數為(1851,2001)，總共點數為3 703 851個，全部為分析檢測點，以此為標準值完成抽稀精度評定。

(4) 采用各種方法抽稀后的點云數據集構TIN，然后按照相同范圍、相同格網間距、相同采樣方法內插生成新的DEM數據。

(5) 利用柵格數據計算工具，使用標準DEM數據與各類抽稀方法生成的新DEM數據作差，生成差值柵格數據，如圖7所示。

(6) 利用柵格分類工具，對新的柵格數據按照5類進行統計分析，分類統計內容見表2，使用差值結果直接統計分析，不采用標準差和中誤差公式計算分析。

表2 分類統計

3.3 試驗精度分析

3.3.1 系統抽稀

系統抽稀是不確定性抽稀，按抽稀后的保留點數計算，分別保留到85%、75%、50%和43%的程度計算分析，也就是抽稀掉15%、25%、50%和57%。表3顯示了保留點密度與標準段數據精度的關系。

表3 系統抽稀保留率與數據精度的關系

在試驗數據保留率84.2%的測試中，最大偏差點分別為-1.569 85和1.945 12；保留率74.5%的測試中最大偏差點分別為-1.572 85和1.963 4；保留率50.5%的測試中最大偏差點分別為-1.579 67和1.752 27；保留率43.2%的測試中最大偏差點分別為-1.779 61和1.952 12；從表3中可以看出保留率越小兩端所占比例越高，分布在-0.2～0.20 m區間比例越小，整體效果較差。

3.3.2 格網抽稀

分別保留85%、75%、50%和40%的程度計算分析。在試驗數據保留率85.9%的測試中最大偏差點分別為-1.150 25和0.949 936；保留率72.6%的測試中最大偏差點分別為-1.671 38和1.351 34；保留率50.1%的測試中最大偏差點分別為-1.910 63和2.120 69；保留率41.5%的測試中最大偏差點分別為-2.010 64和2.530 65；從表4中50%以上保留率在高精精度范圍內的點最多。

表4 格網抽稀保留率與數據精度的關系

3.3.3 TIN抽稀

分別保留55%、42%、35%和16%的程度計算分析。在數據試驗中保留率55.7%的測試中最大偏差點分別為-0.950 24和0.849 936；保留率42.1%的測試中最大偏差點分別為-0.971 051和0.982 042；保留率35.6%的測試中最大偏差點分別為-1.271 06和1.152 04；保留率15.8%的測試中最大偏差點分別為-1.510 64和1.630 65；從表5中35%以上保留率在高精精度范圍內的點最多。

表5 TIN抽稀保留率與數據精度的關系

3.3.4 坡度抽稀算法

試驗經原始數據抽稀后，保留65%、50%、41%和25%的程度，保留率和高程比率分布見表6。

在數據試驗中保留率65.0%的測試中最大偏差點分別為-1.132 31和0.947 453；保留率50.2%的測試中最大偏差點分別為-1.347 01和1.252 32；保留率40.9%的測試中最大偏差點分別為-1.645 52和1.368 91；保留率25.1%的測試中最大偏差點分別為-2.110 03和1.941 36；從表6中41%以上保留率在高精精度范圍內的點最多。

表6 坡度抽稀算法保留率與數據精度的關系

3.3.5 約束TIN節點抽稀法

試驗經原始數據抽稀后，分別抽稀保留65%、50%、41%和25%的程度，保留率和高程比率分布見表7。在數據試驗中保留率65.1%的測試中最大偏差點分別為-0.312 37和0.287 413；保留率50.3%的測試中最大偏差點分別為-0.327 61和0.310 02；保留率41.3%的測試中最大偏差點分別為-0.347 05和0.332 32；保留率25.3%的測試中最大偏差點分別為-0.349 01和0.341 27；從表7中可以看出保留率在41%以上，精度分布最好。

表7 約束TIN節點抽稀法保留率與數據精度的關系

3.4 抽稀方法比較

通過試驗各種抽稀方法，結果表明無論數據抽稀到何種程度,都會有一些高程信息會丟失,抽稀的目標是最大限度地降低數據的密度而損失最小的精度。采用一種合適的抽稀方法可以使試驗區域的數據在保留率達到41%時,其高程內插精度仍能好于20 cm，高程中誤差能控制幾厘米內[18]。

為了能夠更好地說明各種抽稀算法對基礎點云精度的影響,將以上5種抽稀算法的保留率與-0.2～0.20 m的精度匯集到一個圖中,如圖8所示。

4 約束TIN節點抽稀算法的建立與應用

4.1 抽稀法的應用

采用約束TIN節點抽稀算法完成某試驗測區5500 km2的機載雷達數據制作DEM和等值線，作業單元為1∶10 000標準分幅數據，單幅數據量大的達到10 GB、小的也有0.4 GB，數據抽稀完后一般在0.5 GB左右，這樣標準配置計算機都能滿足滿幅作業，避免了拆分再合并的復雜工作。

本文項目成果要求制作DEM和等值線，在生產過程中考慮到生產精度和運算速度等因素，充分分析各種算法的優缺點，采用組合抽稀方式進行數據處理，首先采用高效的格網最低點抽稀算法完成概略抽稀，網格抽稀間距為0.75 m，每幅圖的數據量大約為1.2 GB；然后采用約束TIN節點抽稀算法完成精細化抽稀，高程限差設置為0.10 m，處理完成后每幅數據量為0.4 GB大小，保留率為34%，壓縮率為66%。數據生產完成后進行外業實地符合性高程精度檢查，見表8，利用數據分別生成2 m×2 m和5 m×5 m格網間距的DEM，利用外業檢測數據計算中誤差，2 m×2 m的精度都優于5 m×5 m的精度，中誤差都優于0.20 m；5 m×5 m格網間距的DEM精度最大為0.20 m，圖幅都優于0.20 m，最好精度達到0.08 m。

表8 外業實地符合性高程中誤差

4.2 抽稀算法探討

基于原始點云數據生成的三角網和等值線均有坡度值大、抖動和氣泡比較多的特點，無意義的噪聲數據也較多，單獨幾個點就會有等值線反映出來；點云數據經過兩種方法抽稀后生成的DEM數據和等值線數據噪聲明顯減少，效果對比如圖9所示。

因此，各種抽稀算法和優化約束TIN節點抽稀法的組合應用能達到事半功倍的理想效果。

5 結 語

本文提出了約束TIN節點抽稀法，其既能很好地保留局部地形特征，又能保證整體的地貌特征；既能實現點云數據超強壓縮，又能保證它的高精度。本文算法優勢在于引入高度差約束，并充分利用TIN構網優勢，補充虛擬格網控制精度優化算法，組合傳統算法并能深化應用，尤其在平原地區地貌數據生產項目中的應用，充分體現了算法的高壓縮、高去噪特點。

本文算法解決了點云冗余數據的剔除，提高了計算速度和工作效率，讓處理大數據量點云數據變為可能，解決了逐塊處理的痛點，實現了整幅完整作業，同時實現了點云噪聲和高植被點云自動濾波，消除了DEM和等值線數據中的噪聲。

本文算法經過大范圍制作DEM和等值線數據的實際應用，充分驗證了算法的實用性和可行性。點云數據抽稀或去噪是生產各種測繪產品的必經階段，高度精準抽稀為點云數據制作DEM和等值線產品奠定了良好的數據基礎，為全國性推廣點云數據制作DEM和等值線提出可行性方法[19]。

今后，將在平原測區的生產實踐基礎上進一步完善驗證丘陵地、山地的各種參數和算法，然后再展開地形地貌的平滑算法，為基于激光雷達數據制作高質量的等值線提供更優的解決方案。