python 點雲地面點濾波-progressive TIN densification(PTD)算法介紹

Posted on by

本篇博客參考：
1）DEM generation from laser scanner data using adaptive TIN models
2）Filtering airborne LiDAR data by embedding smoothness-constrained segmentation in progressive TIN densification

文章名中有超鏈接，若不方便下載，則可以在此：資源鏈接進行下載。

1.引言

1.1什麼是地面點濾波？

機載激光雷達(airborne light detection and ranging)/機載激光掃描(ALS, airborne laser scanning)在過去20多年的時間裡迅速發展，其相對於傳統攝影測量影像及INSAR(幹涉合成孔徑雷達)可以直接記錄從地物或地表返回的密集、離散、細節豐富、精確的三維點雲。如何對這些不規則點雲進行處理應用是我們要解決的問題，其中一個重要的處理步驟就是：地面點濾波(ground filterring)，簡而言之就是“在無序、不規則的三維離散點雲中找到哪些是由地表返回的，哪些是由地物返回的。”

註：關於地面點濾波的概念我們要與孤立點(outlier)濾波區分開，孤立點濾波可以理解為圖像中的去噪，去除數據測量過程中受到飛鳥、多路徑效應所產生的遠低於/高於其他數據的點。

1.2地面點濾波的相關方法

眾多學者已經提出瞭各種類型的濾波算法來從ALS三維點雲中自動提取地面點，根據濾波器的概念可以分為以下四類：

  • slope-based
  • block-minimum
  • surface-based
  • clustering/segmentation algorithm

基於面的地面點濾波方法的核心步驟是創建一個最接近裸露地表的表面，其使用瞭更多的context(上下文，環境、背景)信息，所以一般可以取得比其他濾波方法更好的濾波效果。此外，根據創建表面的方法又可以把surface-based類型濾波器分為以下三個子類：

  • Morphology-based filters
  • Iterative-interpolation-based filters
  • Progressive-densification-based filters

其中Morphology-based filters使用不同尺寸大小的窗口形態學操作(opening/geodesic)來去除不同大小的地物，但是這類方法需要假設地形的坡度是一個常數。以及面臨著一個巨大的挑戰是在窗口大小變化的時候怎麼保持地形特征不變；Iterative-interpolation-based filters是通過整個點雲數據集來逐步接近地表，首先通過一個粗糙的表面來計算點雲到表面的殘差，通常來說地物點會有正的差值，地面點會有負的差值。這種方法最大的挑戰是當精度一定的條件下怎麼來提高算法的效率；Progressive-densification-based filters與上一種方法類似，也是漸進地把每個點逐步的分類為地面點，然而此方法不需要進行插值。本篇博客中所介紹的PTD(progressive TIN densification)就是屬於surface-based類型中的一種Progressive-densification-based filters。

2.PTD具體介紹

PTD是Axelsson在2000年左右提出的一種經典濾波方法，在工程應用（TerraScan）及科學社區中得到瞭廣泛的應用。主要可以通過以下五個步驟進行實現：

2.1去除孤立點

如引言中1.1所述，去除孤立點類似於圖像中的去噪操作。outliers是測量數據集中的那些遠高於/低於地表的點，這中情況常常會導致濾波算法出現錯誤（例如，PTD算法中假設格網中的最低點為地面點，從而導致錯誤）。可以通過下述三個簡單步驟來去除孤立點，當然除此之外還有其他很多更加優秀的方法。

  • 對所有數據的高程進行統計，建立一個高程分佈的直方圖，通過觀察高程分佈來確定高程閾值，從而消除分佈中最低和最高的小“尾巴”。
  • 通過每個點與周圍點之間的最小高程差來進行搜尋仍然存在的孤立點（這裡使用一個2D的KD樹來進行組織查詢每個點的近鄰點）。
  • 手工校正孤立點自動去除過程中所產生的錯誤。

 2.2參數說明

在PTD算法中有以下6個參數進行預先設置：

1）最大建築尺寸m：m是一個長度閾值，此閾值被用來定義格網的大小，隨後算法可以處理建築物尺寸小於此閾值的建築物。
2）最大地形角度t：t是一個坡度閾值，決定瞭通過什麼方式（是否進行設置鏡像點）去判斷未分類點的類別。如果未分類點所在三角面的坡度大於t則應該通過一個鏡像點來進行判斷，反之則直接判斷。（後續在2.4中也會再進行詳細介紹）。
3）最大角度θ：θ是三角面與待分類點和最近的三角網頂點之間連線之間的最大角度。如果一個未分類點對應的角度大於θ則被標記為地物點，否則設置為地面點。
4）最大距離d：d是當前迭代中從待判斷點到三角面之間的最大距離，類似的，如果一個未分類點對應的最大距離大於d則被標記為地物點，否則設置為地面點。
5）最小邊長l：l是構建TIN模型中所有三角形最長邊（平面投影）的最小閾值。當三角形中的所有邊都小於l時，則停止在三角網中加入地面點（註意l是在平面中計算的）。因此，此參數可以避免引起地面模型中過高的點密度，以及降低內存的使用。
6）最大邊長l’：*l’是構建TIN模型中所有三角形最短邊（平面投影）的最大閾值，當三角形中的所有邊都小於l’*被用於停止處理處理三角形。因此，此參數用於稀疏地面點，以及降低內存的使用。

2.3選擇種子點並構建TIN模型

對給定的點雲數據集定義一個特定的“bounding box”並固定左上角坐標(xtopleft, ytopleft)右下角坐標(xbottomright, ybottomright)，寬度w，以及高度h。然後通過上述定義的變量通過以下公式把整個數據區域劃分成nRow行，nColumn列，尺寸大小為m的格網。

在這裡插入圖片描述

其中m，為最大建築尺寸，ceil(x)函數代表向上取整，即找到不小於x的最小整數。

根據整個數據集劃分為格網之後，每個網格中的最低點被設置為“種子點”（初始地面點）。除此之外，“bounding box”的四個角點也被設置為“種子點”（其高程值等同於距離最近的種子點高程），如下圖所示：

在這裡插入圖片描述

註：把“bounding box”的四個角點也被設置為“種子點”是為瞭保證所有點都處於TIN模型內部。

隨後，根據選擇好的種子點來構建初始TIN模型來表示初始地表，剩餘的點被默認標記為地物。

2.4迭代加密TIN模型

在每次迭代過程中通過預先設置的閾值參數，來對“潛在點(potential point)”進行逐點判斷。詳細步驟如下所述：
1）確定潛在點(potential point)的所在位置PPotential(xp,yp,zp)，找到其所在的三角形Ttriangle，即PPotential在三角形內部或邊緣上或者在頂點上。
2）計算三角平面的坡度Striangle，如果Striangle小於預先設置的最大地形角度t，則進行第3)步，若大於則進行第4)步。
3）如下圖所示，計算的兩個參數，包括：三角面Ttriangle與待分類點PPotential和最近的三角網頂點之間連線之間的角度，表示為Aangle，以及待分類點PPotential和三角面Ttriangle之間的距離，表示為Ddistance。如果PPotential所對應的上述兩個參數Aangle小於最大角度θ，Ddistance小於最大距離d則認為待分類點PPotential是地面點，否則認為是地物點。隨後，進行下一個點的判斷。

在這裡插入圖片描述

4）如果三角平面的坡度Striangle大於預先設置的最大地形角度t則需要設置PPotential的鏡像點。先找到PPotential所在三角形

Ttriangle中高程值最大的頂點Pvertex(xv,yv,zv)，然後通過下式計算PPotential的鏡像點：

在這裡插入圖片描述

其中(xmirror,ymirror,zmirror)是所求鏡像點的三維坐標。

在這裡插入圖片描述

接著對鏡像點使用步驟3）的方式來進行計算Aangle與Ddistance兩個參數進行判斷，來決定PPotential的類別。
5）在結束每次迭代之後，新檢測出的地面點通過下述步驟加入TIN模型中。

  • 確定Pground(xg,yg,zg)的坐標，找到其所在的三角形T’triangle。
  • 計算三角形T’triangle的所有邊在水平投影中的長度，如果任意邊的長度都大於l加入當前地面點Pground到TIN模型中，並進行刷新。否則，進行判斷下一個新檢測的地面點。
  • 重復上述迭代，直到不再有點被加入到地面點集中。

上述五個步驟就是PTD算法的主要實現方法瞭，PTD算法已經被廣泛應用在各種類型的景觀（地形）中，且取得不錯的效果。但是需要註意的是，雖然在算法中采用瞭設置“鏡像點”的方式來避免出現cutting-off的問題（斷裂線分佈區域），其還是對陡峭地形非常敏感。

到此這篇關於python 點雲地面點濾波-progressive TIN densification(PTD)算法介紹的文章就介紹到這瞭,更多相關python PTD點雲地面點濾波內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：