python之CSF算法的示例分析

這篇文章給大家分享的是有關python之CSF算法的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

1. 引言

機載LiDAR可以獲取快速、低成本地獲取大區域的高精度地形測量值。為了獲取高精度的地形數據（厘米級），對機載LiDAR點云數據進行“濾波”是一個非常重要的步驟。因此近二十年來，國內外學者提出了眾多有效的自動濾波算法，大大降低了人力成本，提高了點云數據的應用效率。在博客：“點云地面點濾波(Progressive Morphological Filter)算法介紹（PCL庫）”與“點云地面點濾波-progressive TIN densification(PTD)算法介紹”中分別對兩種常用濾波器進行了介紹。
以往的眾多算法濾波效果容易受到地形特征的影響（通常在復雜場景及陡峭地形區域濾波效果較差）且常常需要用戶對數據有較為豐富的先驗知識來進行設置濾波器中的各種參數。
為了解決這些問題，張吳明教授等人在2015年第三屆全國激光雷達大會提出的“布料”濾波算法，本篇博客對其進行了簡要介紹。

2. 基本思想

傳統的濾波算法大多是考慮在坡度、高程變化之間的不同來進行區分地物點與地面點，而布料”濾波算法從一個完全新的思路來進行濾波，首先把點云進行翻轉，然后假設有一塊布料受到重力從上方落下，則最終落下的布料就可以代表當前地形。如下圖所示，可以幫助我們進行理解。

下方的藍色圖形代表原始測量值，對其進行翻轉，紅色虛線代表布料，可以反映地形的起伏。

3. CSF算法實現步驟

3.1 “布料”模擬

首先，定義了一個基本公式：

式中，X代表“布料”中的粒子在 t 時刻的位置，Fext(X,t)代表外部驅動因素（重力，碰撞等），Fint(X,t)代表內部驅動因素（粒子間的內部聯系）。

即可以總結為“布料”粒子的位置受到Fext(X,t)與Fint(X,t)兩方面因素的影響。

隨后如下圖所示，通過四個狀態對“布料”粒子的移動過程進行說明。

（a）為初始狀態，假設一個虛擬的布放在翻轉的LiDAR測量值上方。黑色點為LiDAR測量值，深紅色點為可移動粒子。
（b）計算重力影響下對粒子產生的位移，由此一些粒子可能會出現在地面的下方。淺紅色點為粒子的舊位置。
（c）相交檢查，檢查粒子新位置是否到達地面，如果已經到達地面則設置為不可移動。藍色點代表粒子不可移動
（d）考慮“布料”的內部驅動，對現有的“可移動”粒子，根據鄰近粒子所產生的“力”來進行移動新的位置。（如上圖小房子處的可移動粒子）

3.2 外部/內部因素驅動

如3.1節中所述，粒子的位置移動包括外部/內部兩方面的驅動因素，首先假設只有外部因素Fext(X,t)，并設置內部因素Fint(X,t)為0，可以得到以下公式：

式中，m為粒子的重量，通常設置為1，△t 為時間步長。且由于G是一個常數，所以上式非常容易計算，只要給定一個△t 就可以計算出下一次迭代粒子所在的新位置。

為了約束粒子在反轉表面空白區域的反轉問題，作者又考慮了使用內部因素Fint(X,t) 。任意選取兩個相鄰的粒子，如果兩個粒子都是 可移動 的，則令二者往相反的方向移動同樣的距離；如果一個是不可移動的，則移動另一個；如果兩者具有相同的高度，則不進行移動。
位移量可以通過下式進行計算：

式中，d為粒子的位移量；當粒子可移動時，b等于1，不可移動時b等于0；pi為p0的相鄰粒子，n是把點進行標準化到垂直方向上的單位向量（0，0，1）T。

移動過程如下圖所示：

同時還引入了一個新的參數rigidness, RI，用來描述粒子的移動次數，RI為1時，則移動一次，且移動的距離是兩個粒子之間高差的1/2；RI為2時，則移動兩次，且移動3/4。類似的，RI為3時，移動三次，移動距離為兩個粒子高差的7/8。RI的值越大，則“布料”就越硬，一般來說，平地需要設置RI的值較大，陡坡、山區需要設置的RI值較小。

3.3 具體實現

綜上所述，布料模擬的簡要步驟可以總結如下：
1）通過第三方軟件去除原始LiDAR點云數據中的“孤立點”。
2）反轉LiDAR點云。
3）初始布料格網，這時用戶需要設置格網的大小（grid resolution, GR）。初始“布料”的位置通常在最高點的上方。
4）把所有LiDAR點與格網粒子投影到同一個水平面，并找到每一個粒子的最近鄰點（corresponding point, cp），記錄其投影前的高程（intersection height value, IHV）
5）對于每一個可移動的格網“粒子”，計算其受到重力影響產生的位移，并與當前粒子對應cp點的IHV進行比較，如果粒子的高度低于或者等于IHV，則把粒子的高度設置為IHV并設置為不可移動點。
6）對于每個格網“粒子”，計算其受到內部驅動因素影響所產生的的位移。
7）重復上述5）、6）步驟，直到所有粒子的最大高承諾變化足夠小或者迭代次數到達用戶的預先設置值，則停止模擬過程。
8）計算LiDAR點云與格網粒子之間的高度差異。
9）區分地面點與非地面點，如果LiDAR點與模擬粒子之間的距離小于預先設置的閾值hcc，則認為其是地面點，反之則認為其為非地面點。

3.4 后處理

上述方法處理過后對于平坦區域可以取得較好的效果，但是對于“陡坡”區域仍然會產生較大的誤差，因為“布料”會由于其粒子間的內部約束而落在地面測量值的上方。如下圖所示：

為了消除這些誤差，可以通過一個后處理方法來解決。在每一個“可移動”粒子的四個鄰接點中找到“不可移動”粒子，然后比較“最近鄰點”之間的高程差，如果高程差值小于閾值hcp，則把“可移動”粒子移動到地面，并設置為不可移動。
例如，上圖中的D點，找到了一個不可移動的粒子A，然后比較C,B之間的高程差值（對于D點、A點之間的最近鄰點CP）。如果高程差值小于閾值hcp則待判斷點D就被移動到C點，且被設置為不可移動。重復上述操作，直到所有的“可移動”粒子被正確處理。
如果逐行掃描“粒子”來進行實現此后處理操作，結果可能會受到特定掃描方向的影響。因此，作者采用了先建立一個“強連接元素集”（strongly connected components, SCC）包含一個關聯的可移動粒子集。

如上圖所示，每個SCC中包括兩種粒子，第一種是至少包含一個近鄰“不可移動”粒子（上圖中的黃色點M1），第二種是近鄰點中不包含“不可移動”粒子（上圖中的紅色點M2）。執行過程中使用外部的黃色點為“初始種子點”，通過“廣度優先”的方式逐步向內遍歷SCC。如上圖中的從1-18點，實現了從邊緣逐步向內部靠近處理過程，而不受掃描方向的影響。

感謝各位的閱讀！關于“python之CSF算法的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！