樹(shù)木三維點(diǎn)云的枝葉分割方法

黃 亮 許文雅 譚 帥

(1. 江蘇省測(cè)繪工程院,江蘇 南京 210013; 2. 江陰市綠化技術(shù)監(jiān)督指導(dǎo)站, 江蘇 江陰 214400;3. 江陰市園林綠化管理所, 江蘇 江陰 214400)

0 引言

樹(shù)木在城市環(huán)境中是園林綠化的主要組成部分,在野外環(huán)境中是森林的基本構(gòu)成單元,在保護(hù)生態(tài)環(huán)境、改善人居環(huán)境、碳達(dá)峰及碳中和等方面具有不可替代的作用。建設(shè)工程多測(cè)合一中綠化測(cè)量、園林綠化調(diào)查、森林資源調(diào)查等都需要采集樹(shù)木信息,恢復(fù)樹(shù)木的三維結(jié)構(gòu)是樹(shù)木資源精細(xì)化管理、全生命周期管理的基礎(chǔ)工作。

傳統(tǒng)的單木測(cè)量方式主要是全野外采集,利用全球定位系統(tǒng)(Global Positioning System，GPS)接收機(jī)或者全站儀獲取樹(shù)木的位置和高度數(shù)據(jù),利用胸徑尺、卷尺獲取樹(shù)木的地徑、胸徑、蓬徑等數(shù)據(jù)[1]。傳統(tǒng)方法效率低、成本高、周期長(zhǎng)、精度差,且只能獲取有限的結(jié)構(gòu)參數(shù),無(wú)法滿(mǎn)足生物量統(tǒng)計(jì)、實(shí)景三維構(gòu)建等新需求。隨著遙感技術(shù)的不斷發(fā)展,地面三維激光掃描技術(shù)已經(jīng)可以獲取樹(shù)木的高密度、高精度三維點(diǎn)云,為樹(shù)木資源的三維模型構(gòu)建、立體監(jiān)測(cè)提供了技術(shù)途徑[2]。

利用點(diǎn)云重建樹(shù)木三維模型的方法大致分為兩類(lèi),即分割建模法和直接建模法[3]。分割建模法是先對(duì)樹(shù)木點(diǎn)云進(jìn)行枝葉分割,利用枝干點(diǎn)云構(gòu)建樹(shù)木骨架后建模。直接建模法是將采集得到的所有點(diǎn)云統(tǒng)一處理、建模,避開(kāi)了分割枝葉的步驟,模型注重整體視覺(jué)效果,但與真實(shí)枝干分布吻合度較差。顯然,分割建模法可以反映樹(shù)木更真實(shí)的形態(tài)結(jié)構(gòu)信息,而有效的枝葉點(diǎn)云分割是樹(shù)木分割建模法的前提和基礎(chǔ)。

文獻(xiàn)[4]利用鄰域點(diǎn)的主曲率方向相似性來(lái)區(qū)分有效樹(shù)枝點(diǎn)和噪聲,但算法針對(duì)的落葉樹(shù)的樹(shù)葉很少,具有一定的局限性。文獻(xiàn)[5]利用移動(dòng)圓柱體提取枝干骨架點(diǎn),對(duì)枝干細(xì)節(jié)模擬不夠。文獻(xiàn)[6]在利用移動(dòng)圓柱體提取枝干骨架點(diǎn)的基礎(chǔ)上，利用移動(dòng)圓柱主方向判斷點(diǎn)云密集區(qū)枝干的中心點(diǎn),優(yōu)點(diǎn)是枝條半徑精度較高,但后續(xù)重建的判斷條件比較復(fù)雜。文獻(xiàn)[7]分析局部鄰域的特征值,將線(xiàn)性的分布?xì)w類(lèi)為樹(shù)木的枝干,將平面分布?xì)w類(lèi)為樹(shù)葉,但較粗的主干往往不成線(xiàn)性,較小的樹(shù)葉疊加晃動(dòng)等因素在點(diǎn)云中也不表現(xiàn)為平面。文獻(xiàn)[8]利用半監(jiān)督的支持向量機(jī)(Support Vector Machine,SVM)分類(lèi)算法對(duì)櫻花樹(shù)和深山含笑樹(shù)的點(diǎn)云進(jìn)行枝葉分離,得到枝干點(diǎn)云數(shù)據(jù)。文獻(xiàn)[9]利用法向量分布、結(jié)構(gòu)張量與半監(jiān)督SVM結(jié)合,分割枝干、樹(shù)葉等多種點(diǎn)云。文獻(xiàn)[10]利用點(diǎn)特征向量組特性,結(jié)合一種半監(jiān)督SVM的方法,實(shí)現(xiàn)枝干、葉片的分類(lèi)。文獻(xiàn)[11]構(gòu)造特征訓(xùn)練分類(lèi)器將樹(shù)木點(diǎn)云分割為地面、樹(shù)干與枝葉。利用SVM或其他分類(lèi)器進(jìn)行分類(lèi),由于樹(shù)木種類(lèi)多、激光掃描儀的型號(hào)多、掃描方式差異大,需要頻繁采集和訓(xùn)練樣本,操作復(fù)雜,對(duì)用戶(hù)的要求較高。文獻(xiàn)[12]利用超體聚類(lèi)算法實(shí)現(xiàn)單木枝干和樹(shù)葉的分割,需要設(shè)置體素分辨率、種子分辨率、顏色權(quán)重、空間權(quán)重、法向量權(quán)重、相鄰體素法向量夾角閾值等參數(shù),且依賴(lài)顏色屬性,較為復(fù)雜。文獻(xiàn)[13]采用閾值法和隨機(jī)森林法進(jìn)行立木枝葉分離,活立木強(qiáng)度數(shù)據(jù)經(jīng)過(guò)校正可以得到枝葉分離的閾值,但面對(duì)混生樹(shù)木差異較大時(shí)適應(yīng)性較差。

為此,本文提出一種基于鄰域點(diǎn)分布規(guī)律的枝葉分割方法。首先對(duì)樹(shù)木點(diǎn)云構(gòu)建K維樹(shù)(KDimension-Tree，KD-Tree),搜索某激光點(diǎn)的R鄰域點(diǎn)集;接著對(duì)鄰域點(diǎn)集進(jìn)行主成分分析(Principal Component Analysis,PCA),獲取特征值和特征向量,利用特征值構(gòu)建鄰域點(diǎn)集的分布散亂度;然后將分布散亂度與閾值比較,區(qū)分枝干和葉片的候選點(diǎn);最后利用歐氏聚類(lèi)獲取可靠的枝干點(diǎn)。利用江陰大橋公園的樹(shù)木點(diǎn)云數(shù)據(jù)集進(jìn)行測(cè)試。結(jié)果表明：本文提出的樹(shù)木點(diǎn)云枝葉分離方法準(zhǔn)確率高、點(diǎn)云屬性要求低、簡(jiǎn)單易用,可應(yīng)用于多測(cè)合一綠化測(cè)量、城市綠地生物量統(tǒng)計(jì)、實(shí)景三維樹(shù)木模型構(gòu)建等領(lǐng)域。

1 數(shù)據(jù)獲取與預(yù)處理

1.1 掃描與配準(zhǔn)

本文使用Leica ScanStation C10、Leica ScanStation P40兩款三維激光掃描儀,架設(shè)自由站從多個(gè)角度對(duì)樹(shù)木進(jìn)行掃描,如圖1(a)所示。各站點(diǎn)云,首先人工選取同名點(diǎn)對(duì)計(jì)算旋轉(zhuǎn)和平移參數(shù),實(shí)現(xiàn)粗配準(zhǔn)。再利用迭代最近點(diǎn)(Iterative Closest Point,ICP)算法[14]實(shí)現(xiàn)自動(dòng)的精配準(zhǔn),配準(zhǔn)點(diǎn)云如圖1(b)所示。

圖1 掃描與配準(zhǔn)

1.2 移除噪聲

由于儀器本身、懸浮顆粒等原因,獲取的三維點(diǎn)云含有大量的噪聲,會(huì)影響法向量計(jì)算、主成分分析等算法的可靠性,使用統(tǒng)計(jì)離群點(diǎn)移除(Statistical Outlier Removal,SOR)濾波器[15]去除噪聲點(diǎn)。

1.3 點(diǎn)云重采樣

掃描儀的型號(hào)、掃描的距離、掃描的角度、掃描的分辨率等因素,都會(huì)影響樹(shù)木點(diǎn)云的密度。不均勻的點(diǎn)密度會(huì)降低算法的穩(wěn)定性,因此，利用體素化網(wǎng)格(VoxelGrid)方法進(jìn)行重采樣。將點(diǎn)云在空間中劃分為等邊長(zhǎng)的立方體,每個(gè)立方體就是一個(gè)體素,每個(gè)體素中包含的激光點(diǎn)只保留最靠近體素中心的那個(gè)點(diǎn)(圖2)。體素邊長(zhǎng)即重采樣后點(diǎn)云中相鄰點(diǎn)的平均間距。

圖2 移除噪聲和重采樣后的點(diǎn)云

1.4 地面濾波

激光掃描數(shù)據(jù)中含有大量的地面點(diǎn),不僅增加了點(diǎn)云處理的運(yùn)算量,也不利于后續(xù)單棵樹(shù)木的分割。因此,使用布料模擬濾波器(Cloth Simulation Filter,CSF)[16]加上少量的人工編輯將點(diǎn)云分為地面點(diǎn)、非地面點(diǎn),其中非地面點(diǎn)(圖3)包含了所有的樹(shù)木點(diǎn)云。

圖3 非地面點(diǎn)云

1.5 單木提取

由于樹(shù)冠重疊生長(zhǎng)等原因,非地面點(diǎn)中的樹(shù)木點(diǎn)云在空間上可能是粘連的,并不是按棵獨(dú)立分布的?？梢允褂米钚「罘指?mincut segment)[17]算法結(jié)合人工編輯,對(duì)非地面點(diǎn)實(shí)施精確的單木分割。在樹(shù)木點(diǎn)云之間粘連較少時(shí),可以單純使用人工編輯提取單木點(diǎn)云(圖4)。

圖4 單木點(diǎn)云

2 枝葉分離方法

2.1 搜索鄰域點(diǎn)集

已經(jīng)分割成單木的樹(shù)木點(diǎn)云構(gòu)建KD-Tree結(jié)構(gòu),實(shí)現(xiàn)點(diǎn)云的快速索引。遍歷樹(shù)木點(diǎn)云,第i個(gè)激光點(diǎn)Pi,以其為球心搜索半徑R內(nèi)的領(lǐng)域點(diǎn),構(gòu)成鄰域點(diǎn)集Ni。通過(guò)觀察發(fā)現(xiàn),樹(shù)的主干部分較粗,當(dāng)搜索半徑R小于樹(shù)徑時(shí),其鄰域點(diǎn)集Ni一般呈現(xiàn)為面狀分布;樹(shù)的枝干較細(xì),直徑一般小于搜索半徑R,其鄰域點(diǎn)集Ni一般呈現(xiàn)為線(xiàn)狀分布;不考慮葉片特別大的樹(shù)種,葉片尺寸一般小于搜索半徑R,再加上葉片堆疊和晃動(dòng)等因素,其鄰域點(diǎn)集Ni一般趨近各向同性分布。

2.2 散亂度計(jì)算

為了定量表達(dá)鄰域點(diǎn)集Ni的各向同性分布程度,構(gòu)建散亂度指標(biāo)S,如公式(1)所示。

(1)

S值越小則鄰域點(diǎn)集Ni的散亂度越高,越有可能是樹(shù)葉點(diǎn)。設(shè)定一個(gè)預(yù)定義的散亂度閾值ST,當(dāng)前點(diǎn)Pi的散亂度為Si,當(dāng)Si

2.3 歐式聚類(lèi)

對(duì)枝干候選點(diǎn)集Mbranch進(jìn)行歐式聚類(lèi),距離判斷準(zhǔn)則為歐氏距離。具體步驟：

(1)對(duì)于當(dāng)前點(diǎn)Pj,利用KD-Tree近鄰搜索算法,找到Pj的K個(gè)最近鄰點(diǎn),距離D小于設(shè)定閾值DT的聚類(lèi)到集合Q中。Pj標(biāo)記為已處理。

(2)對(duì)Q中未處理的其他點(diǎn),執(zhí)行(1)操作。

(3)如果Q中點(diǎn)的數(shù)量n不再增加,則當(dāng)前聚類(lèi)完成。計(jì)算Q的空間尺寸L(x,y,z),其中長(zhǎng)Lx,寬Ly,高Lz。

(4)如果n>nT且L(x,y,z)>L(x,y,z)T,則Pj保留為枝干點(diǎn),否則Pj放入Mleaf中。其中,nT為歐氏聚類(lèi)的點(diǎn)數(shù)量閾值,L(x,y,z)T為歐氏聚類(lèi)的尺寸閾值,兩個(gè)閾值都是預(yù)定義的。

(5)最終樹(shù)木點(diǎn)云分為枝干點(diǎn)集Mbranch和樹(shù)葉點(diǎn)集Mleaf,完成了枝葉分離。

3 實(shí)驗(yàn)與結(jié)論

實(shí)驗(yàn)點(diǎn)云數(shù)據(jù)使用Leica ScanStation C10和Leica ScanStation P40聯(lián)合三維激光掃描獲得,共計(jì)16站,地點(diǎn)位于江陰市大橋公園內(nèi)部。掃描站之間,先手動(dòng)選取4對(duì)以上同名點(diǎn)粗配準(zhǔn),若配準(zhǔn)誤差較大,再利用ICP算法精配準(zhǔn),最終所有站之間的配準(zhǔn)點(diǎn)位誤差均小于0.02 m。使用統(tǒng)計(jì)離群點(diǎn)移除(Statistical Outlier Removal，SOR)噪聲時(shí),參數(shù)采用默認(rèn)推薦值,即估計(jì)平均距離的鄰域點(diǎn)數(shù)設(shè)置為6,標(biāo)準(zhǔn)差設(shè)置為1.0,隨機(jī)噪聲去除的效果較好。點(diǎn)云基于VoxelGrid重采樣時(shí),體素的邊長(zhǎng)設(shè)置為0.01 m,獲得重采樣點(diǎn)云密度約為每立方厘米1個(gè)點(diǎn)。使用布料模擬濾波器(Cloth Simulation Filter，CSF)進(jìn)行地面濾波時(shí),布料的分辨率設(shè)置為1.0 m,最大迭代次數(shù)設(shè)置為500,點(diǎn)到布料的距離閾值設(shè)置為0.3 m,獲取了包含樹(shù)木的非地面點(diǎn)。非地面點(diǎn)在空間聚類(lèi)后依靠簡(jiǎn)單的人工編輯和標(biāo)記,實(shí)現(xiàn)了精確的單木分割。

實(shí)驗(yàn)點(diǎn)云數(shù)據(jù)經(jīng)過(guò)預(yù)處理后,得到37個(gè)單木點(diǎn)云,使用本文提出的方法進(jìn)行枝葉分割,散亂度閾值設(shè)置為0.8,歐氏聚類(lèi)時(shí)最小間距設(shè)置為0.02 m,最少聚類(lèi)點(diǎn)數(shù)10,最小聚類(lèi)尺寸0.20 m,枝葉分割的效果如表1所示。

表1 枝葉分割效果

目視判別點(diǎn)云中的樹(shù)木主干、一級(jí)枝干、次級(jí)枝干,認(rèn)為是真值。統(tǒng)計(jì)本文枝葉分割方法的運(yùn)算結(jié)果,經(jīng)計(jì)算可知,對(duì)于樹(shù)木主干可以全部精確分割,對(duì)于一級(jí)枝干的正確分割的比例為89.63%,對(duì)于次級(jí)枝干,正確分割的比例為72.72%,錯(cuò)誤分割的比例為17.29%。分割結(jié)果可以用于樹(shù)木骨架更精確地跟蹤。

表2 枝葉分割結(jié)果 單位：根

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有枝葉分割方法參數(shù)設(shè)置復(fù)雜、需要訓(xùn)練樣本、依賴(lài)顏色強(qiáng)度等不足,提出了一種新的基于鄰域點(diǎn)分布規(guī)律的枝葉分割方法。該方對(duì)鄰域點(diǎn)集進(jìn)行主成分分析,利用特征值計(jì)算鄰域點(diǎn)集的分布散亂度,進(jìn)而區(qū)分枝干和葉片的候選點(diǎn),對(duì)枝干候選點(diǎn)實(shí)施歐氏聚類(lèi)獲取可靠的枝干點(diǎn)。使用江陰大橋公園的樹(shù)木點(diǎn)云數(shù)據(jù)集進(jìn)行測(cè)試,結(jié)果表明，本文方法分割的準(zhǔn)確率高、簡(jiǎn)單易用,可應(yīng)用于多測(cè)合一綠化測(cè)量、城市綠地生物量統(tǒng)計(jì)、實(shí)景三維樹(shù)木模型構(gòu)建等領(lǐng)域。

本文方法的不足之處是當(dāng)樹(shù)木的葉片較大時(shí),容易被分割為次級(jí)枝干。接下來(lái)的研究,計(jì)劃先分割出主干,用主干中心線(xiàn)作為約束,雖然大樹(shù)葉也呈現(xiàn)面狀分布,但可以利用其距離主干較遠(yuǎn)的特點(diǎn)進(jìn)行排除。