基于布模擬算法與三角形插值的稀疏點云處理方法

郝耀庭，楊 保，張鵬飛，王麗媛

(1.河南理工大學 測繪與國土信息工程學院，河南 焦作 454000；2.河南四維遠見信息技術有限公司，河南 鄭州 450000)

點云分割是在二維圖像分割受到局限的情況下，研究者將數據維度從二維提升到三維，從根本上解決二維圖像在空間位置上的局限性。在二維圖像分割中，國內外許多研究者都提出了用于深度學習的算法[1]，點云分割與分類模型的效果也與訓練樣本的質量息息相關，在Wang[2]等人提出的DGCNN網絡模型中，設計了一個用于提取中心點的特征以及此點與鄰域點的邊緣向量的邊緣卷積操作，在這部分操作中，點云的稠密程度影響較大，總體的分割效果與點云的點數呈現線性關系，點云點數越多，分割效果越好。點云數據密度較大時，會存在大量的數據冗余，造成計算量大、效率低、顯示不便等一系列問題，由此陳佩奇等[3]針對城區(qū)LiDAR點云數據提出了自適應采樣的抽稀算法。對于稀疏點云的插值，康帥[4]以冷龍嶺斷裂上一處典型地貌點云為例，對比了最鄰近法、距離反比法、不規(guī)則三角網法、樣條函數法、克里金法等5種插值方法，實驗結果表明：不規(guī)則三角網插值法結果最優(yōu)，可以較好地還原野外真實場景。

對于室外復雜場景，先對點云進行濾波處理分為地面點和非地面點，再對兩部分點云進行分別插值。點云濾波是LiDAR點云數據處理過程中的重要環(huán)節(jié)之一，常用于點云去噪、分離地面點與非地面點等。傳統(tǒng)的常見點云濾波方法一般有直通濾波、體素濾波、統(tǒng)計濾波、條件濾波、半徑濾波。直通濾波是對具有一定空間分布特征的點云數據進行處理，適用于處理x、y方向具有一定范圍但z方向分布較廣的這類點云的離群點。體素濾波通過體素網格去除噪音點以及離群點，可對點云進行降采樣，同時可以使點云本身的幾何結構不被破壞。統(tǒng)計濾波是定義某一部分區(qū)域的點云密度閾值，小于閾值的部分點云無效。條件濾波即設定一個或多個條件對點云進行過濾，符合設定的條件即保留。半徑濾波與統(tǒng)計濾波類似，同樣是區(qū)域性的濾波，但是濾波方式有差別，是以某點為中心畫一個圓并計算落在該圓中的數量，當數量大于閾值的時候保留該點，小于閾值則剔除該點，圓的半徑與閾值均要人工指定。目前，國內外研究者提出了大量的點云濾波算法，基本分為基于形態(tài)學的濾波算法[5-6]、自適應不規(guī)則三角網濾波[7]、基于多尺度濾波。

1 點云數據與算法原理

1.1 布模擬算法

2003年，張建忠[8]等人通過對布匹動力學的物理模型簡化，提出了一種快速有效的布模擬算法(Cloth Simulation Filtering，CSF)，其可以模擬布料在真實場景中的狀態(tài)。2016年，張吳明[9]等人將布模擬算法的思想應用于點云濾波中。應用于機載LiDAR點云的布模擬點云濾波算法的主要原理是將點云反轉之后，設定格網分辨率和迭代次數，生成一個該分辨率下迭代多次的彈性格網來模擬布匹落在地面上的狀態(tài)，再設定一個閾值，通過點云與彈性格網的歐式距離來分離地面點與非地面點，見圖1、圖2。

布模擬算法包含3個參數，分別為格網分辨率、迭代次數、分類閾值。格網分辨率是指覆蓋地形的格網大小，設置的分辨率越大，模擬的彈性格網越粗糙。迭代次數是指地形模擬的最大迭代次數。分類閾值是根據點與地形模擬彈性格網的距離，將點云分為地面點與非地面點兩部分的閾值。

1.2 三角形內部線性插值

已知三角形的3個頂點坐標P1、P2、P3，三角形內部一點P與3個頂點連線將三角形分為3個面積分別為V1、V2、V3的小三角形，大三角形面積為V，如圖3所示。

P點坐標P=u×P1+v×P2+w×P3，其中，u=V1/V，v=V2/V，w=V3/V，u+v+w=1，由此可以得出三角形內任意一點的坐標。

由于大面積三角形需要的插值點過多，所以總體采用隨機插值的方法，先在(0,1)范圍內隨機得到兩個數字c,d，則令

u=min(c,d)

(1)

v=|c-d|

(2)

w=1-max(c,d) (3)

這樣的隨機取值方法可以確保在對大面積三角形進行插值的時候不會出現插值點聚集在一起的現象，使插值結果更加均勻。

2 實驗流程及結果分析

2.1 實驗條件

操作系統(tǒng)：Windows10；軟件環(huán)境：Python3.5；點云顯示軟件：CloudCompare；點云數據：ModelNet10數據集，鄭州市高新技術開發(fā)區(qū)一處機載LiDAR實測點云。

2.2 實驗數據

論文中所使用的模型點云數據為ModelNet10點云數據集，該數據集共有662種目標分類，127 915個CAD模型以及10類標記過方向的數據。點云數據為off格式，包含點數量、面數量、邊數量、點信息、面信息。室外點云數據使用鄭州市高新技術開發(fā)區(qū)一塊實測點云，點云數據為las格式。

原始點云數據包含13 147 331個點，點云密度較大，如圖4所示。對點云進行隨機降采樣，降采樣后生成的點云包含893 871個點，使用降采樣后的點云作為實驗對象，如圖5所示。

圖4 原始點云

圖5 降采樣后的稀疏點云

2.3 實驗流程

ModelNet10數據集的點云數據格式為off格式，包含了a個點信息和b個面信息。首先，讀取點云數據，每一條點信息都包含了該點的x、y、z坐標，每一條面信息都包含了面的邊數以及各個頂點的點號，點號從0開始，到最后一個點結束。利用三角網中三角面的權重來確定增加的點數，先計算三角形的邊長l1、l2、l3，點P1與P2之間的距離D采用歐式距離，公式為：

(4)

再用海倫公式計算面積，公式為：

(5)

(6)

其中，S為面積，p為半周長。

第i個三角形插值點的數量通過當前三角形的面積Si與三角網總面積的比值n來確定，公式為：

(7)

由于ModelNet10數據提取的三角網存在兩邊較長一邊較短的三角形，為了保證這類細長型三角網的插值，通過判定周長總和與最短邊長比m，

(8)

對于室外點云數據先對其進行布模擬濾波處理，對點云進行多層次不同分類閾值的布模擬濾波并進行整合，解決單次固定分類閾值下的濾波導致的部分分類錯誤問題。

2.4 實驗結果分析

2.4.1 ModelNet10數據插值

對一個椅子的點云進行插值，由于點云數據直接包含了三角網的面狀屬性信息，直接將數據分為點云數據和三角網模型，再對三角網進行插值。

通過對比插值前后的點云，當k=1時，點數從2 382增加到6 050個，當k=2時，點數從2 382增加到8 581個，如圖6所示。通過視覺上直觀的對比，k=1時，點云插值的結果已經非常理想，足夠作為深度學習網絡模型來進行訓練學習的樣本。

圖6 插值前后點云以及三角網

2.4.2 室外實測點云插值

對鄭州市高新技術開發(fā)區(qū)一處機載LiDAR實測點云進行實驗，實驗數據與ModeNet10數據集不同，為las格式數據，先對las數據進行解析提取點云的點信息，進行隨機降采樣之后對點云進行布模擬濾波處理來分離地面點和非地面點。格網分辨率設置為0.5，迭代次數為500，進行單次濾波作為對比，將分類閾值分別設置為0.5～3.5，以0.5為間隔的分類閾值進行布模擬濾波，濾波后地面點和非地面點的點數見表1。

表1 單次不同分類閾值下濾波結果

分類閾值為0.5、2.0、3.5時的濾波結果分別見圖7、圖8、圖9。由表1可以看出，隨著分類閾值的增加，地面點數的增速呈遞減趨勢。分類閾值為0.5時，很大一部分地面點都被錯誤分類到非地面點。分類閾值為2.0時大部分地面點都正確分類到地面點，只有一小部分依然被錯誤分類。分類閾值為3.5時，更多的矮建筑物被分類到地面點。所以，選取分類閾值為2.0時的濾波結果進行下一步的插值。

圖7 分類閾值為0.5時的分類結果

圖8 分類閾值為2.0時的分類結果

圖9 分類閾值為3.5時的分類結果

對首次濾波的結果(見圖10)再次進行更大分類閾值下的濾波，對地面點與非地面點分別進行更高分類閾值的濾波之后并整合，結果如圖11所示，兩種方法的分類結果對比見表2。

圖10 單次固定分類閾值的分類結果

圖11 多次不同分類閾值整合的分類結果

表2 不同方法結果對比

與單次單分類閾值情況下的濾波相比，多次不用分類閾值整合的分類結果更加精確。單次濾波的分類結果中有部分矮建筑被錯誤分類到地面點，也有部分街道上的點云被分類到非地面點，使用多次不同分類閾值并進行整合的方法可以很大程度地降低類似的分類錯誤，提高分類精度，準確性更好。對最終分離的地面點和非地面點分別生成三角網，再對三角網進行插值，插值結果如圖12所示。

圖12 插值后的地面點與非地面點

通過插值前后對比，地面點由617 391個增加為1 019 494個，非地面點由276 480個增加為536 911個，插值效果理想。在保證增加了點云細節(jié)的情況下，不使深度學習模型對點云進行分割分類的計算量過于巨大。

3 結論

論文設計實現了一種基于布模擬算法和三角形內部線性插值的快速高效點云插值方法。利用三角網中三角形面積權重與三角形邊長總和與最短邊的比值來確定插值點數量，并在三角形面內進行隨機均勻線性插值，在ModelNet10數據集上插值效果理想。對于室外場景，插值效果受點云濾波處理的影響，布模擬算法可以很好地貼合地面點，但單次固定分類閾值下的分類會導致有一部分高度比較低的地物和面積比較大的矮建筑被分類到地面點，造成分離錯誤。論文提出的方法通過對室外點云進行多次不同分類閾值濾波，整合所得到的分類結果很大程度地降低了單次固定濾波造成的分類錯誤，只有極少部分的地物分類錯誤。地物點的顏色信息一般與地面點有一定差異，可以從這個角度出發(fā)對布模擬算法做進一步的研究和改進。