基于改進(jìn)凸包算法的樹冠輪廓點(diǎn)提取與體積計(jì)算

董亞涵，李永強(qiáng)，李鵬鵬，呂亞磊

(河南理工大學(xué) 測繪與國土信息工程學(xué)院，河南 焦作 454003)

樹木作為城市景觀中的組成部分，具有重要的生態(tài)和環(huán)境服務(wù)功能，樹冠是樹木進(jìn)行光合作用的主要場所，對人類的生活具有重要意義[1,2]。作為樹木變化最頻繁的部分，樹冠的體積是進(jìn)行樹木生長檢測和生物量計(jì)算研究的重要測量因子，因此樹冠體積的測量必須滿足一定精度。對于樹冠的信息采集，傳統(tǒng)方法主要使用圍尺、測高儀、測距儀、全站儀等測量儀器對樹冠冠幅、樹冠高進(jìn)行測量，但由于傳統(tǒng)方法采集的數(shù)據(jù)不完整，精度不高并不足以對其進(jìn)行深入分析，而三維激光掃描儀可以高效率、高精度地獲取樹冠表面的三維點(diǎn)云數(shù)據(jù)[3-8]。

對于使用點(diǎn)云數(shù)據(jù)計(jì)算樹冠體積，常規(guī)方法是從點(diǎn)云數(shù)據(jù)中提取樹冠的冠幅、冠高等信息，再將樹冠近似為規(guī)則幾何體，按規(guī)則幾何體的體積計(jì)算公式進(jìn)行估算樹冠體積。但由于樹冠結(jié)構(gòu)復(fù)雜且不對稱，這種方法計(jì)算樹冠體積易造成較大誤差，并不符合精度要求。為此眾多學(xué)者提出了改進(jìn)方法，如熊妮娜等將樹冠等間距分成多個部分，并將各個部分近似為規(guī)則臺體，對臺體進(jìn)行體積計(jì)算并累加得到樹冠體積[9]。韋雪花提出體元模擬法，將樹冠點(diǎn)放入體元并設(shè)置體元邊長閾值，通過計(jì)算有效體元數(shù)計(jì)算樹冠體積，經(jīng)實(shí)驗(yàn)證明，當(dāng)選擇的體元邊長為1 cm 時，計(jì)算出的樹冠體積最接近真值[10]，但未考慮到由于樹冠遮擋而形成的偽空隙，使用體元模擬法計(jì)算的樹冠體積往往偏小。樊仲謀利用樹冠表面三角網(wǎng)配合立體格網(wǎng)計(jì)算樹冠體積[11]。鞏垠熙等人提出改進(jìn)的Delaunay算法計(jì)算樹冠體積[12]。徐偉恒等人通過將樹冠等距分層并對每層樹冠點(diǎn)云進(jìn)行投影，再對投影后的點(diǎn)云使用Graham掃描線算法構(gòu)建凸包多邊形[13]，通過多邊形構(gòu)建臺體從而得出樹冠體積。樹冠體積計(jì)算的最大問題在于如何精確提取出樹冠邊緣，并且除掉樹冠邊緣與樹冠間的空隙，傳統(tǒng)的凸包算法對提取樹冠邊緣的精度有限，并且是對分層后的樹冠進(jìn)行整體凸包構(gòu)建，難以有效地將樹冠邊緣與樹冠間空隙提取出來，本文提出一種改進(jìn)的凸包算法—迭代漸進(jìn)的凸包算法，使樹冠的提取精度更接近與真實(shí)值。

1 迭代漸進(jìn)的凸包算法

凸包(Convex Hull)作為計(jì)算機(jī)圖形學(xué)中的重要概念，已被廣泛應(yīng)用于圖像處理、設(shè)計(jì)自動化、模式識別和運(yùn)籌學(xué)等領(lǐng)域之中。在一個實(shí)數(shù)向量空間V中，對于給定集合X，所有包含X的凸集的交集S被稱為X的凸包，常用的凸包算法包括窮舉法、分治法、JARVIS步進(jìn)法、Graham掃描線算法、局部凸包算法等[14-19]。由于樹冠邊緣不規(guī)則且樹冠內(nèi)孔隙較多，傳統(tǒng)凸包算法無法有效排除樹冠空隙，為解決傳統(tǒng)凸包算法在提取樹冠輪廓點(diǎn)中的不足，本文對傳統(tǒng)方法構(gòu)建的樹冠凸包進(jìn)行了改進(jìn)，發(fā)展了迭代漸進(jìn)的凸包算法，算法描述如下：

1)將樹冠點(diǎn)云自下而上等間距分層，并將每一層點(diǎn)云儲存成一個獨(dú)立單元，分層間距為0.2 m；

2)對分層后的點(diǎn)云進(jìn)行z軸投影；

3)對每層點(diǎn)云使用傳統(tǒng)凸包算法對其進(jìn)行外層凸包構(gòu)建，本文中選擇的凸包算法為局部凸包算法；

4)設(shè)置邊長閾值Llimit，對建立的凸包輪廓以每條大于邊長閾值Llimit的邊為直徑作圓形區(qū)域，選取圓內(nèi)的點(diǎn)為疑似邊界點(diǎn)，尋找疑似邊界點(diǎn)中與直徑端點(diǎn)組成最大角的點(diǎn)作為新邊界點(diǎn)，從而有效地收縮樹冠邊界，剔除邊界空隙；

5)重復(fù)步驟4)進(jìn)行各條邊的運(yùn)算，直至所有邊長都小于邊長閾值Llimit，或者以該邊為直徑的圓內(nèi)沒有點(diǎn)，停止迭代計(jì)算。

圖1為迭代漸進(jìn)的凸包算法運(yùn)算過程，其中(b)為使用傳統(tǒng)凸包算法建立的外包圍輪廓，并以一條邊為直徑構(gòu)建圓，(c)選取圓內(nèi)黃色的點(diǎn)作為疑似邊界點(diǎn)，(d)選擇與直徑兩端點(diǎn)構(gòu)成最大角的點(diǎn)作為新的邊界點(diǎn)。根據(jù)三維激光掃描儀采集點(diǎn)云的間隔，本文設(shè)置邊長閾值為0.1 m 。

2 樹冠體積計(jì)算

樹冠體積計(jì)算具體步驟如下：

1)對樹冠點(diǎn)進(jìn)行按高程分層，使用PCL點(diǎn)云庫中的歐式聚類算法對分層樹冠進(jìn)行聚類；

2)使用迭代漸近的凸包算法對聚類后的樹冠點(diǎn)提取外輪廓并連接選取的輪廓點(diǎn)構(gòu)成不規(guī)則多邊形；

3)使用格林公式對建立的多邊形進(jìn)行面積計(jì)算。

(1)

式中：S為切片面積，m為單片樹冠凸包的總點(diǎn)數(shù)，xi為i點(diǎn)的x坐標(biāo)，yi為i點(diǎn)的y坐標(biāo)，xi+1為i+1點(diǎn)的x坐標(biāo)，yi+1為i+1點(diǎn)的y坐標(biāo)。若樹冠分塊，則S為各塊樹冠面積之和。

圖2為單株樹使用迭代漸進(jìn)的凸包算法提取輪廓點(diǎn)并構(gòu)建多邊形的結(jié)果：(c)(d)(e)為使用迭代漸近的凸包算法對分層點(diǎn)云進(jìn)行輪廓提取，并通過輪廓點(diǎn)構(gòu)建不規(guī)則多邊形。

4)將相鄰的兩切片構(gòu)建為多邊形不規(guī)則臺體，通過臺體計(jì)算式計(jì)算單塊臺體體積并累加，累加結(jié)果即為樹冠體積。

圖1 迭代漸進(jìn)的凸包算法

圖2 樹冠輪廓點(diǎn)提取并構(gòu)建多邊形

(2)

式中：V為樹冠體積，n為切片層數(shù)，Si為第i層切片多邊形面積，Si+1為第i+1層切片多邊形面積，h為分層距離[3]。

3 試驗(yàn)分析

為檢驗(yàn)上述算法計(jì)算出樹冠體積的正確性，選取河南理工大學(xué)校園內(nèi)行道樹為實(shí)驗(yàn)數(shù)據(jù)，樹木種類包括女貞樹、柳樹等，使用RIEGL VZ-1000型地面三維激光儀對測區(qū)樹木進(jìn)行點(diǎn)云數(shù)據(jù)采集，掃描方式為重復(fù)掃描，平均點(diǎn)云密度為3 cm。為獲取完整的樹種點(diǎn)云，對每一目標(biāo)樹種，均設(shè)立3個掃描站，三站位置盡量成120°，以確保樹種點(diǎn)云的完整性。數(shù)據(jù)壓縮，點(diǎn)云去噪以及配準(zhǔn)拼接等工作均是在配套軟件RiscanPro中完成。

從實(shí)驗(yàn)數(shù)據(jù)中選取出樹冠形態(tài)具有代表性的25株樹為樣本，對樣本進(jìn)行樹冠外輪廓提取與樹冠體積計(jì)算，選擇3種常用且具有代表性的計(jì)算樹冠體積的方法：幾何體模型法、體元模擬法、以及文獻(xiàn)[13]中使用Graham掃描線法對樹冠進(jìn)行構(gòu)建凸包并計(jì)算樹冠體積的方法，與本文所述方法進(jìn)行對比，由于樹冠的真實(shí)體積無法獲取，采用人工交互的方法，人為選取外輪廓點(diǎn)，并通過外輪廓點(diǎn)構(gòu)建多邊形以及進(jìn)行樹冠體積計(jì)算，將得到的樹冠體積作為測量參照值，人工提取雖然并非絕對真值，但由于三維激光掃描儀數(shù)據(jù)獲取精度高，點(diǎn)云密集，人工干預(yù)可信程度高，可以作為參考的基準(zhǔn)。同時將三種提取樹冠外輪廓點(diǎn)的方法置于同一視圖中，結(jié)果如圖3所示。使用迭代漸進(jìn)的凸包算法自動構(gòu)建的樹冠輪廓與人工提取的樹冠輪廓相似度較高。人工提取雖然能夠更為精確的提取樹冠輪廓，并有效忽略樹冠離散點(diǎn)的影響，但人工提取工作量大，提取過程繁瑣，工作效率低，不適用于城市中樹木的批量處理。

圖3 3種樹冠外輪廓提取方法對比

將5種方法計(jì)算出的樹冠體積進(jìn)行統(tǒng)計(jì)，結(jié)果如表1所示，其中C1為樹冠冠幅，V1，V2為使用幾何模型法，體元模擬法計(jì)算出的樹冠體積，V3，V4為使用Graham掃描線法與迭代漸進(jìn)的凸包算法構(gòu)建樹冠凸包后計(jì)算出的樹冠體積，V5為人工交互方式計(jì)算出的樹冠體積。

表1 樹冠體積計(jì)算

續(xù)表1

對表1中樹冠體積數(shù)據(jù)進(jìn)行詳細(xì)分析，將V5作為樹冠的測量參照值，分別計(jì)算V5與V1-V4的均方根誤差與相關(guān)性，結(jié)果如表2所示。V4(RMSE=2.342)與V5相關(guān)系數(shù)r=0.988，說明兩組數(shù)據(jù)高度相關(guān)。

表2 V5與V1-V4均方根誤差及相關(guān)系數(shù)對比

將V1～V5放置于同一折線圖(圖4)中，實(shí)驗(yàn)數(shù)據(jù)表明，除使用幾何體模擬法V1(RMSE=47.563)計(jì)算結(jié)果明顯偏大外，另外4種方法計(jì)算出的樹冠體積相差較小，且V4(RMSE=2.342)結(jié)果基本位于V2(RMSE=5.046)，V3(RMSE=6.892)之間，使用幾何體模擬法計(jì)算樹冠體積的方法，只是將樹冠模擬為規(guī)則幾何體，而沒有考慮樹冠形態(tài)的復(fù)雜性與樹冠空隙，因此計(jì)算結(jié)果偏大且具有較大誤差，體元模擬法計(jì)算樹冠體積V2，忽略樹冠相互遮擋形成的偽空隙，在對樹冠邊緣格網(wǎng)進(jìn)行處理后，導(dǎo)致體元模擬法計(jì)算出的樹冠體積偏小，使用Graham掃描線法V3計(jì)算樹冠體積，由于未能有效剔除樹冠邊緣與內(nèi)部空隙，導(dǎo)致V3計(jì)算出的樹冠體積偏大，使用迭代漸進(jìn)的凸包算法有效地減小了樹冠邊緣與內(nèi)部空隙對樹冠體積的影響，因此V4更接近于樹冠體積的真實(shí)值V5。

圖4 5種樹冠體積計(jì)算方法結(jié)果對比

4 結(jié) 論

三維激光掃描系統(tǒng)通過多個方向依次對目標(biāo)樹進(jìn)行掃描，得到的樹冠點(diǎn)云數(shù)據(jù)完整且最接近于樹冠真實(shí)形態(tài)，通過對樹冠進(jìn)行0.2 m的等距分層并聚類，使用改進(jìn)的凸包算法—迭代漸進(jìn)的凸包算法對樹冠進(jìn)行外輪廓點(diǎn)的提取，將提取出的輪廓點(diǎn)構(gòu)建為不規(guī)則多邊形，使用格林公式計(jì)算每一層多邊形面積，并結(jié)合臺體計(jì)算公式最終得到樹冠體積。

以25株形態(tài)、體積差別較大的樹株作為實(shí)驗(yàn)對象，由于樹冠體積真值無法獲取，采用人工交互的方式，人為選取輪廓點(diǎn)，使用選取出的輪廓點(diǎn)計(jì)算樹冠體積，并以此作為樹冠參照對本文算法進(jìn)行驗(yàn)證，同時將本文方法計(jì)算出的樹冠體積與幾何體模型法、體元模擬法、Graham掃描線法計(jì)算的樹冠體積進(jìn)行對比與分析，結(jié)果表明，使用迭代漸進(jìn)的凸包算法計(jì)算出的樹冠體積(VV4)與幾何體模型法(V1)、體元模擬法(V2V)以及Graham掃描線法(VV3)計(jì)算出的樹冠體積結(jié)果相比，與樹冠體積參照值(V5)更為相近，相關(guān)性更高，并且V4繪制出的體積折線圖基本位于V2和V3V之間，也從側(cè)面說明本文所述方法所計(jì)算出的樹冠體積更接近于樹冠真實(shí)值。

使用傳統(tǒng)測量方法獲取樹冠的精確信息非常困難，三維激光掃描系統(tǒng)提供了便捷、快速、準(zhǔn)確獲取樹冠表面三維信息的方法，使用迭代漸進(jìn)的凸包算法對樹冠點(diǎn)云進(jìn)行外輪廓提取，不僅能夠?qū)涔隗w積進(jìn)行精細(xì)的計(jì)算，也為樹冠的信息提取與精細(xì)自動建模工作提供了基礎(chǔ)。本文所述算法更為精確的提取出了樹冠的外輪廓點(diǎn)，有效彌補(bǔ)了傳統(tǒng)凸包算法應(yīng)用在樹冠外輪廓提取中的不足。

[1] 林樹森. 城市增長與城市發(fā)展[J]. 城市規(guī)劃，2011(11): 11-18.

[2] 林樹森. 城市道路交通長期規(guī)劃應(yīng)突出人居環(huán)境理念[J]. 城市與區(qū)域規(guī)劃研究，2015(3): 120-131.

[3] 李楊，李秀峰. 基于點(diǎn)云數(shù)據(jù)的樹木骨架線提取研究[J]. 科技創(chuàng)新與生產(chǎn)力，2017(6)：53-55.

[4] 管西鵬. 樹木三維點(diǎn)云數(shù)據(jù)分析與建模技術(shù)研究[D].長沙：中南林業(yè)科技大學(xué),2015.

[5] 李宏星，歐陽玉華.基于三維激光掃描點(diǎn)云的樹冠面積快速精準(zhǔn)計(jì)算方法[J].綠色科技，2015(6):72-74.

[6] 梁子瑜.基于TLS點(diǎn)云數(shù)據(jù)的林分調(diào)查因子測定及收獲估計(jì)[D].南京：南京林業(yè)大學(xué)，2015.

[7] 王祺，胡洪，吳艷蘭，等. 基于點(diǎn)云數(shù)據(jù)的樹冠體積自動求算方法[J]. 西北林學(xué)院學(xué)報(bào),2017,32(2):242-246.

[8] 臧克. 基于Riegl三維激光掃描儀掃描數(shù)據(jù)的初步研究[J]. 首都師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，28(1)：77-82.

[9] 熊妮娜，王佳，羅旭，等. 一種基于三維激光掃描系統(tǒng)測量樹冠體積方法的研究——以油松為例[J]. 北京林業(yè)大學(xué)學(xué)報(bào)，2007(增2)：61-65.

[10] 韋雪花，王永國，鄭君，等. 基于三維激光掃描點(diǎn)云的樹冠體積計(jì)算方法[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2013(7): 235-240.

[11] 樊仲謀，馮仲科，鄭君，等. 基于立方體格網(wǎng)法的樹冠體積計(jì)算與預(yù)估模型建立[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015(3)：320-327.

[12] 鞏垠熙，何誠，馮仲科，等. 基于改進(jìn)Delaunay算法的樹冠三維重構(gòu)單木因子提取[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2013(2): 192-199.

[13] 徐偉恒，馮仲科，蘇志芳，等. 一種基于三維激光點(diǎn)云數(shù)據(jù)的單木樹冠投影面積和樹冠體積自動提取算法[J]. 光譜學(xué)與光譜分析，2014(2): 465-471.

[14] 張飛，謝步瀛，閆星宇，等. 改進(jìn)的三維點(diǎn)集凸包求取算法[J]. 計(jì)算機(jī)輔助工程，2009, 18(1): 78-82.

[15] 黃俊杰，羅周全，秦亞光，等. 復(fù)雜采空區(qū)三維散亂點(diǎn)建模技術(shù)研究及應(yīng)用[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，37(12)：1784-1788.

[16] 吳文周，李利番，王結(jié)臣. 平面點(diǎn)集凸包Graham算法的改進(jìn)[J]. 測繪科學(xué)，2010(6): 123-125.

[17] 蔣聯(lián)源. 凸殼算法及其應(yīng)用研究[D]. 南京：廣西師范大學(xué)，2007.

[18] 李必棟，閆浩文，王中輝，等. 坐標(biāo)排序的離散點(diǎn)凸包生成算法[J].測繪科學(xué)，2017，42(2):14-17.

[19] 黃先鋒，程曉光，張帆，等. 基于邊長比約束的離散點(diǎn)準(zhǔn)確邊界追蹤算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2009(6): 688-691.