摘" 要: 在對點云數(shù)據(jù)進行采集時,由于激光雷達設備和拍攝高度等因素導致點云質量存在差異,將影響后續(xù)重建結果。針對輸入點云質量不高或拓撲結構不完整的問題,文中采用一種基于骨架的方法提取樹木的原始骨架,通過最短路徑算法構建一個最小生成樹(MST),通過模糊熵迭代方法去除冗余部分簡化原始骨架。利用基于優(yōu)化的擬合圓柱體序列進行重建,以近似模擬樹枝的幾何形狀。實驗結果表明,在點云數(shù)量非常有限的情況下,該方法的單木重建精度也可以達到85%左右。而在點云數(shù)量較多的情況下,重建精度可提高至90%左右,且能夠處理不同形狀和結構的樹木,對樹木主干以及具有高密度點云的矮樹具有良好的重建效果。
關鍵詞: 激光雷達; 樹木骨架; MST; 模糊熵迭代; 擬合圓柱體序列; 重建精度
中圖分類號: TN958.98?34" " " " " " " " " " " " "文獻標識碼: A" " " " " " " " " " " "文章編號: 1004?373X(2025)07?0139?07
Fuzzy entropy based reconstruction method for single tree skeleton
ZHAO Yonghui1, YAN Peiyu1, GU Juntao2, LI Zhen1, PENG Xunhui1, LI Chao1, LIU Shuyu1
(1. College of Computer and Control Engineering, Northeast Forestry University, Harbin 150040, China;
2. Heilongjiang Cyberspace Research Centre, Harbin 150090, China)
Abstract: During the acquisition of point cloud data, the point cloud quality varies due to factors such as LiDAR equipment and shooting height, which will affect the results of subsequent reconstruction. In view of the poor quality or incomplete topology of the input point clouds, this paper adopts a skeleton?based method to extract the original skeleton of the tree, constructs a minimum spanning tree (MST) with the shortest path algorithm, and removes the redundant parts by the fuzzy entropy iterative method, so as to simplify the original skeleton. Reconstruction is carried out with an optimization?based sequence of fitted cylinders to approximate the geometry of simulated tree branches. The experimental results show that the accuracy of single tree reconstruction can reach about 85% even in the case of a very limited number of point clouds. In the case of a larger number of point clouds, however, its reconstruction accuracy can be increased to about 90%, and it can deal with trees of different shapes and structures, and the reconstruction results are good for tree trunks, as well as dwarf trees with high?density point clouds.
Keywords: LiDAR; tree skeleton; MST; fuzzy entropy iteration; fitted cylinder sequence; reconstruction accuracy
0" 引" 言
激光雷達能快速、準確、廣泛地獲取三維空間信息,從不同角度生成不同分辨率的點云,取代多種測量儀器來獲取單木的胸徑、樹高和樹冠等結構參數(shù),生成不同質量的點云,點云對一些重建方法影響較大,導致拓撲結構不完整[1?2]。樹木拓撲結構的重建方法大致分為兩類:基于分割和基于骨架。基于分割的方法先將樹點云分成小的子集,再將它們連接起來形成樹木結構,但這種方法對輸入數(shù)據(jù)質量高度依賴;而基于骨架的方法是通過原始輸入點云直接提取骨架。文獻[3]提出基于動態(tài)圓柱擬合的方法對單木骨架進行提取。文獻[4]采用基于點云骨架的建模思路,使用廣義圓柱體構建模型,獲得清晰的拓撲結構。文獻[5]依據(jù)基于骨架的方法對枝干進行重建,冠層特征點能較好地表達數(shù)目冠層輪廓的凹凸特性。文獻[6]計算點云上的最小生成樹(MST)獲得初始樹骨架,并應用多種全局優(yōu)化技術細化分支結構。文獻[7]使用基于K?means聚類方法提取樹枝的拓撲結構,但過于依賴輸入數(shù)據(jù)的質量,導致魯棒性較差。文獻[8]通過計算最小生成樹獲取樹木骨架,從整體角度保證優(yōu)良建模效果,重建后樹木模型富有真實感。
針對重建精度不高或拓撲結構不完整的問題,本文提出一種基于骨架的方法:采用最小生成樹(MST)算法,通過點云準確地提取輸入初始樹骨架。迭代簡化原始樹木骨架后進行柱體擬合,針對不同輸入質量點云進行合理建模,點云數(shù)量較少的情況下,重建精度可以達到85%左右。點云密集處可以更好地反映枝干情況,即有更好的建模效果,因此數(shù)量較多的精度大約可以達到90%左右。
1" 研究方法
研究區(qū)域位于東北林業(yè)大學,地理坐標為東經(jīng)126°37′15″,北緯45°43′10″,位處哈爾濱市南崗區(qū)和香坊區(qū)的交界處,該區(qū)屬于溫帶大陸性季風氣候,擁有多種溫、熱、冷杉類植物,主要研究的樹種有椴樹和楓樹等。LiDAR數(shù)據(jù)采集于2023年10月,采集數(shù)據(jù)使用的雷達參數(shù)如表1所示。
輸入的單木點云數(shù)據(jù)包含噪聲和離群值等干擾,離群值是指在一份數(shù)據(jù)中,與其他觀察值具有明顯不同特征的值,離群值非主干點,并不會影響主要分支結構,但噪聲會對分支產(chǎn)生一定的影響,所以二者都需要被刪除。本文先對骨架初始化處理,依靠主要枝干提高骨架質量;對提取的骨架進行模糊熵迭代,消除噪聲和離群值,并簡化得到一個輕量級的樹木骨架;最后通過一系列的圓柱體擬合輸入點近似模擬幾何形狀的分支。采用非線性最小二乘法獲得準確的樹干半徑,從主干幾何學導出后續(xù)分支半徑。本文技術路線如圖1所示。
1.1" 骨架區(qū)域提取
考慮到彼此十分接近的兩個點很可能來自于同一個分支,將輸入點云應用三角剖分法構造一個MST圖表示初始樹骨架,最有效的方法是在剖分圖中找到邊之間的最小生成樹[9]。使用歐幾里得定義對所有邊進行加權,依據(jù)最短路徑算法從三角剖分圖中計算MST,表示單棵樹木的初始骨架。
圖2顯示通過最短路徑計算在輸入點上提取的初始骨架。在大多數(shù)情況下用MST表示原始樹木骨架結構,如圖2a)所示。然而也存在一些特殊情況(見圖2b)),即獨立的MST無法準確表示樹骨架。有些樹木短且寬,導致點云和分支較為分散,這種情況會以水平方式計算MST,而并非正常的緊湊垂直生長方式。利用樹木主要枝干上的點可以解決這一問題,這樣能更好地提取骨架從而生成壓縮分支。有些部位的點密度經(jīng)常突然變化,例如分叉或分支尖端附近,而單個分支內的點密度則相對穩(wěn)定,依靠這個性質可以通過判斷該部位的點密度是否穩(wěn)定區(qū)分主分支點和尖端,利用均值漂移算法[10]集中識別主要分支點。
對識別后的點云數(shù)據(jù)進行Pyelastix配準,對待測點云的最近點進行計算分組,多次迭代刪除冗余部分,將點云數(shù)據(jù)的前后坐標進行配準,得到簡化后配準的樹木骨架點云,如圖3所示。其中,圖3a)和圖3b)是單棵樹木點云的前后配準視角圖,圖3c)是配準后的結果。
1.2" 骨架簡化
1.2.1" 邊界提取
在描述一個物體時,它的形狀由它的邊界決定,但由于邊界很容易丟失,因此需要對邊界單獨提取。通常情況下,點云數(shù)據(jù)是三維立體的,但由于人們自身的高度和拍攝角度常常把三維的信息變成二維,所以本文方法采取以長和寬為主要研究方向來保留邊界,這樣就不會影響算法的效率,在1.2.2節(jié)中曲率為向導時,高度信息并未丟失,提取到的邊界圖如圖4b)所示,具體步驟如圖5所示。
1.2.2" 模糊熵迭代
為在不丟失細節(jié)點云的條件下精簡骨架,就需要對具有不同特征的數(shù)據(jù)點進行刪減或保留。首先估計所有數(shù)據(jù)點的曲率(見圖6),如果該數(shù)據(jù)點附近的相關點到切平線較遠,則該點處的曲率值較大,相反,距離較近,則該點曲率值較小。
需要保留曲率較大的數(shù)據(jù)點來表達簡化后模型的細節(jié)特征,適當保留曲率較小的數(shù)據(jù)點來保證模型的視覺效果。定義模糊熵這個名詞來反映一個數(shù)據(jù)集的模糊程度,如果該數(shù)據(jù)集模糊程度大,則熵值也偏大,如果模糊程度小,則熵值也很小[11]。針對一個數(shù)據(jù)集來說,模糊程度的含義是某一點的曲率特征通過對某類特征的隸屬程度表達。輸入點云提取的原始樹木骨架中通常含有多余點,這些點對骨架形狀的影響很小,將它們刪除進一步簡化樹木骨架。簡化主要分為以下步驟進行:首先對輸入數(shù)據(jù)進行邊界提?。挥嬎闼悬c的曲率,并分組計算該組中點的個數(shù)和曲率平均值;構造曲率小組模糊集;計算最小模糊熵決定最佳劃分閾值;迭代進行比例稀釋,大于閾值進行模糊熵操作,小于閾值則保留。
把[C=[Cur(x,y, z)]]定義為無邊界三維點云模型,[X={Xur,min,…,Xur,max}]表示無邊界數(shù)據(jù)點分組后的平均曲率,[Xur,min]代表最小平均曲率值組,[Xur,max]代表最大平均曲率值組,坐標[(x,y, z)]處的曲率用[C=[Cur(x,y, z)]∈X]表示,[μc[Cur(x,y, z)]]代表數(shù)據(jù)點[(x,y, z)]在[C]中具有某種特性的隸屬度函數(shù)。若用模糊集合表示模型,則有:[C={Cur(x,y, z), μc[Cur(x,y, z)]}],其中,[μc[Cur(x,y, z)]∈[0,1]]。
將最大和最小曲率差值的1%定義為模糊集曲率分組閾值[t],分組[x∈X]出現(xiàn)次數(shù)用[h(x)]表示,目標和背景的均值分別為[μ0]和[μ1]。
[μ0=x=Cur,mintx?h(x)x=Cur,minth(x)] (1)
[μ1=x=t+1Cur,maxx?h(x)x=t+1Cur,maxh(x)] (2)
定義[A[Cur(x,y, z);t, μ0, μ1]]為隸屬函數(shù),其表達式為:
[A[Cur(x,y, z);t, μ0, μ1]=" " 11+Cur(x,y, z)-μ0 k," " "Cur(x,y, z)lt;t11+Cur(x,y, z)-μ1 k," " "Cur(x,y, z)≥t] (3)
式中[k]為常數(shù),目的是讓隸屬函數(shù)處于0.5~1之間。由隸屬函數(shù)定義知,某點處鄰域的隸屬程度越大,則該處的值越大,也就說明該鄰域越清晰,便于分割,即模糊熵越小。所以曲率分組閾值選用最小模糊熵。傳統(tǒng)方法對于給定三維模型[C]的對數(shù)型模糊熵可表示為式(4)、式(5)。其中[n]為輸入點云的個數(shù),[μc(x)]表示隸屬函數(shù)值。將輸入點云經(jīng)過模糊熵迭代后得到的簡化骨架圖如圖4所示。
[e(c)=1nln2x∈X[μc(x)]h(x)] (4)
[M[μc(x)]=-μc(x)ln[μc(x)]-[1-μc(x)]ln[1-μc(x)]] (5)
1.3" 分支匹配
為了準確模擬樹枝的幾何形狀,本文選取圓柱擬合的方法,因為在數(shù)據(jù)集中有孔隙和噪聲的情況下表示樹枝的幾何形狀時,圓柱體模型也有很好的魯棒性。相比于復曲線擬合方法,該模型在計算上更容易且迅速。
一般情況下,密度最大的支撐點存在于樹木根部附近。利用基于優(yōu)化的方法可以獲得準確的分支幾何形狀,步驟如下:分割并識別位于軀干部分內的相鄰點(見圖7);使用暴力搜索方法或kd?tree查詢加速分割速度;接下來,根據(jù)相應的主干點擬合一個圓柱體,其本質是典型的非線性最小二乘法問題,可以使用馬夸特算法(Levenberg)解決[12]。將參數(shù)定義(見圖8)為:輸入點的位置[H];圓柱體的軸向矢量[z]、端點在軸上的位置[Hz]、圓柱體半徑[r];目標函數(shù)為從點到分支圓柱的距離[d]的平方和。
[d=i=1ndis Hi] (6)
式中[dis Hi]表示從[Hi]到分支圓柱表面的距離。
正態(tài)最小二乘法對數(shù)據(jù)噪聲和異常值非常敏感。因此,通過不斷地進行非線性最小二乘法過程提高解的質量,并在第二次迭代期間為每個點引入權重,特定點的權重定義如下:
[Pi=1-dis Hi dismax] (7)
式中:[dis Hi]表示從初始計算獲得的當前第[i]點到圓柱體之間的距離;[dismax]是所有點到圓柱體的最大距離。通過這種方式,將所有點權重歸一化到[0,1]的范圍。目標函數(shù)相應地表示為:
[F=i=1nPi?dis Hi] (8)
lt;E:\2025年第7期\2025年第7期\Image\25t8.tifgt;
圖8" 圓柱擬合問題中的參數(shù)和目標
一般小的樹枝在接近樹冠和樹枝尖端時噪聲變得較大,圓柱體無法精確擬合。為了解決該問題,采用異速生長規(guī)則對其余樹枝進行合理估計。分支邊半徑與其權重成正比,權重定義為其兩個頂點的子樹長度的平均值。使用式(9)計算剩余分支邊緣的半徑。
[rei=rtwi wt] (9)
式中:[rei]是第[i]個分支邊緣的半徑;[rt]是通過圓柱擬合獲得的樹干半徑;[wi]是特定第[i]個分支邊緣的權重。
1.4" 最小二乘擬合圓獲取初始半徑
設點集[x]是由以[A(1)]為起點、[A(2)]為終點的骨架得到的,點集[x]的外接立方體中心為[c]。設旋轉矩陣[R]滿足:
[(0,0,1)T=R?A(2)-A(1)A(2)-A(1)2] (10)
將[x]平移至其外接立方體中心為坐標原點后旋轉,得到[x'],則[x']滿足:
[x′=Up∈X{R(p-c)}] (11)
[x′]中的點向[xOy]平面投影,得到[x′xOy]點集。將[X2+Y2+Dx+Ey+F=0]記作擬合后的圓的方程,用[xi]和[yi]分別表示點集[x′xOy]中第[i]個點的橫坐標與縱坐標,[n]為[x′xOy]中點的數(shù)量,且:
[r1=nx2i-xi2r2=nxiyi-xiyir3=nx3i+nxiy2i-x2i+y2ixir4=ny2i-yi2r5=nx2iyi+ny3i-x2i+y2iyi] (12)
由最小二乘法的原理易知:
[D=r2r5-r3r4r1r4-r22E=r1r5-r2r3r22-r1r4F=-x2i+y2i+Dxi+Eyin] (13)
公式(13)中[D]、[E]、[F]均為參數(shù),即擬合得到的圓的圓心坐標為[-D2,-E2],半徑為[D2+E2-4F22]。
2" 結果與分析
2.1" 實驗建模結果分析
本文實驗的目的是重建不同種類、大小和分支結構的樹木。圖9通過對5組不同的數(shù)據(jù)進行重建,將5組真實RGB圖像和重建后的骨架進行對比,實驗結果表明采用基于骨架的方法能夠處理不同形狀和結構的樹木。
分別對點云數(shù)量適中的高樹、矮樹、點云數(shù)量龐大的高樹、矮樹和點云質量較差的樹木進行重建,圖9結果顯示,點云數(shù)量適中的樹木重建效果一般,當輸入點云的質量較高時有很好的重建效果,但當輸入點云質量較差時,依然可以輸出合理的三維模型。
2.2" 重建精度
對于任意一段骨架線,其頂點為[A(1)],終點為[A(2)],中點處的半徑為[r],首先構造三維空間中[xOy]平面上的剖面點集[S]:
[S=i=0n-1rcos2πin,rsin2πin,0T] (14)
計算旋轉矩陣[R]滿足:
[A(2)-A(1)A(2)-A(1)2=R(0,0,1)T] (15)
則通過中點剖面的點集為[S′]。
[S′=p∈SRp+12(A(2)-A(1))] (16)
通過計算輸入點和生成的分支模型之間的平均距離量化建模結果的幾何精度[13],表2給出重建精度和標準偏差。對比5組實驗數(shù)據(jù)可知,通常具有較高點云密度的矮樹會有更準確的建模結果,此外,形狀不規(guī)則的樹木或生長緊湊的樹木也能實現(xiàn)較高精度的重建。
標準偏差的求解方法:先尋找距離點云中最近的三角面頂點,依據(jù)式(17)計算歐氏距離dis;計算完成后尋找頂點周圍的面,以頂點為圓心,最小單位為半徑畫圓,再對圓進行等邊三角形外切處理找到周圍的面;計算中心點到各個面的平均距離作為標準偏差的數(shù)值(取整),利用式(18)計算得出。
[dis=x1-x22+y1-y22+z1-z22] (17)
[Dis=Ax1+By1+Cz1A2+B2+C2] (18)
通過表2和圖9可以得出,位于主分支內的點在構建模型時通常更加準確地被構建,而分支尖端附近的點通常具有高誤差值。這表明本文方法可以生成輸入樹的高精度主支結構(依靠基于非最小二乘的分支擬合),但分支末端附近點云密度很小,這些小特征無法完全重建。
2.3" 實驗對比分析
將本文所用的建模方法與公開訪問的其他建模方法進行比較,例如TreeQSM方法[14?15]以及SimpleTree[16]。TreeQSM方法和傳統(tǒng)樹木建模方法相比,更加關注枝干幾何參數(shù)的定量提取,和本文所使用的方法類似,但TreeQSM的效果不夠平滑,在點云數(shù)據(jù)質量較差的情況下有部分枝干脫離主干,產(chǎn)生傾斜,重建精度達到87%左右。而PypeTree精度較差,只能將原始樹木的枝干粗略地重建出來,視覺效果較差,重建精度大概只有80%。此外,將本文的方法與PointNet和改進的PointNet++方法進行對比發(fā)現(xiàn),后兩種方法的重建精度較高,但對于小細節(jié)的處理并不是很完善,重建精度達到90%左右。SimpleTree方法簡單地重建樹木枝干的基本構架,并沒有針對胸徑大小進行相應的處理,重建精度達到85%以上。本文方法改進以上方法的不足,能更好地擬合單木骨架的頂點和邊緣并進行重建,重建結果平滑且合理,重建精度可達90%以上,具有較好的重建結果。對比結果如表3和圖10所示。
3" 結" 論
本文針對精度不高或拓撲結構不完整問題,增加樹木骨架重建時對主分支點的中心化,能夠大大提高生成樹枝結構的真實度,利用基于優(yōu)化的圓柱體擬合序列準確地重建樹枝的幾何形狀,重建精度可達90%以上,即便是點云數(shù)量有限的情況下,重建精度也可達85%以上。實驗結果表明,該方法具有魯棒性,在處理各種類型和大小的樹木時,只要點云能表現(xiàn)出分支結構,就可以生成高質量的樹木模型。在未來的重建場景應用中,可以對樹木進行自動分割,一旦實現(xiàn)將應用到更多的場景,還可以采用自由曲面擬合的方式替代圓柱體擬合,進一步提升重建精度。
注:本文通訊作者為劉淑玉。
參考文獻
[1] ZHANG W M, WAN P, WANG T J, et al. A novel approach for the detection of standing tree stems from plot?level terrestrial laser scanning data [J]. Remote sensing, 2019, 11(2): 211.
[2] 杜建麗,陳動,張振鑫,等.建筑點云幾何模型重建方法研究進展[J].遙感學報,2019,23(3):374?391.
[3] 黃志鑫,邢濤,邢艷秋,等.基于動態(tài)圓柱擬合的背包激光雷達單木骨架曲線提取[J].中南林業(yè)科技大學學報,2021,41(12):68?76.
[4] 徐亦凡.基于地基激光雷達的單木可視化模擬研究[D].南京:南京林業(yè)大學,2022.
[5] 張浩.基于點云數(shù)據(jù)的樹木三維幾何模型自動重建[D].福州:福州大學,2017.
[6] 陳動,張振鑫,王臻,等.骨架優(yōu)化下的地面激光樹木點云重建方法[J].地球信息科學學報,2019,21(2):236?248.
[7] 黃曉輝,王成,熊李艷,等.一種集成簇內和簇間距離的加權k?means聚類方法[J].計算機學報,2019,42(12):2836?2848.
[8] 張安珍,李建中.不確定圖最小生成樹算法[J].智能計算機與應用,2019,9(6):1?5.
[9] 李國森,閆李,朱小培,等.基于最小生成樹的粒子群優(yōu)化算法[J].計算機工程與設計,2022,43(7):1972?1980.
[10] 王忠民,段娜,范琳.融合YOLO檢測與均值漂移的目標跟蹤算法[J].計算機工程與應用,2019,55(10):186?192.
[11] 劉玉敏,朱峰,靳琳琳.基于概率猶豫模糊熵的多屬性決策方法[J].控制與決策,2019,34(4):861?870.
[12] 姜玉鑫,孫建鋒,侯培培,等.基于Levenberg?Marquardt算法的旋轉雙棱鏡指向偏差修正[J].中國激光,2023,50(6):97?105.
[13] GUO J W, XU S B, YAN D M, et al. Realistic procedural plant modeling from multiple view images [J]. IEEE transactions on visualization and computer graphics, 2020, 26(2): 1372?1384.
[14] 范光鵬.基于激光雷達點云的樹木定量結構模型研究[D].北京:北京林業(yè)大學,2021.
[15] 吳毓涵,汪沛,李雅新,等.基于實際和模型樹木的TreeQSM建模估計樹木參數(shù)性能分析[J].中國激光,2023,50(22):165?174.
[16] 王立鵬,張佳鵬,張智,等.基于深度學習的移動機器人語義SLAM方法研究[J].哈爾濱工程大學學報,2024,45(2):306?313.
[17] 林文杰.基于最小生成樹的高分辨率遙感影像層次化分割方法研究[J].測繪學報,2022,51(2):316.
作者簡介:趙永輝(1979—),男,黑龍江依蘭人,碩士研究生,工程師,研究方向為物聯(lián)網(wǎng)與人工智能。
顏培鈺(2000—),男,黑龍江哈爾濱人,碩士研究生,研究方向為物聯(lián)網(wǎng)與人工智能。
谷俊濤(1979—),男,黑龍江哈爾濱人,博士研究生,黑龍江省網(wǎng)絡空間研究中心主任,研究方向為遙感數(shù)據(jù)處理。
李" 振(1998—),男,山東濰坊人,碩士研究生,研究方向為物聯(lián)網(wǎng)與人工智能。
彭勛輝(2000—),男,江西撫州人,碩士研究生,研究方向為物聯(lián)網(wǎng)與人工智能。
李" 超(1982—),女,山西太原人,博士研究生,教授,研究方向為人工智能、通信與信號處理。
劉淑玉(1979—),女,山東煙臺人,碩士研究生,研究方向為通信與信號處理。
收稿日期:2024?06?17" " " " " "修回日期:2024?07?10
基金項目:黑龍江省自然科學基金(LH2023F003);黑龍江省杰出青年項目基金(JQ2023F002)