基于改進凸包算法的樹冠輪廓點提取與體積計算

董亞涵，李永強，李鵬鵬，呂亞磊

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

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

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

1 迭代漸進的凸包算法

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

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

2)對分層后的點云進行z軸投影；

3)對每層點云使用傳統凸包算法對其進行外層凸包構建，本文中選擇的凸包算法為局部凸包算法；

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

5)重復步驟4)進行各條邊的運算，直至所有邊長都小于邊長閾值Llimit，或者以該邊為直徑的圓內沒有點，停止迭代計算。

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

2 樹冠體積計算

樹冠體積計算具體步驟如下：

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

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

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

(1)

式中：S為切片面積，m為單片樹冠凸包的總點數，xi為i點的x坐標，yi為i點的y坐標，xi+1為i+1點的x坐標，yi+1為i+1點的y坐標。若樹冠分塊，則S為各塊樹冠面積之和。

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

4)將相鄰的兩切片構建為多邊形不規則臺體，通過臺體計算式計算單塊臺體體積并累加，累加結果即為樹冠體積。

圖1 迭代漸進的凸包算法

圖2 樹冠輪廓點提取并構建多邊形

(2)

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

3 試驗分析

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

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

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

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

表1 樹冠體積計算

續表1

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

表2 V5與V1-V4均方根誤差及相關系數對比

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

圖4 5種樹冠體積計算方法結果對比

4 結 論

三維激光掃描系統通過多個方向依次對目標樹進行掃描，得到的樹冠點云數據完整且最接近于樹冠真實形態，通過對樹冠進行0.2 m的等距分層并聚類，使用改進的凸包算法—迭代漸進的凸包算法對樹冠進行外輪廓點的提取，將提取出的輪廓點構建為不規則多邊形，使用格林公式計算每一層多邊形面積，并結合臺體計算公式最終得到樹冠體積。

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

使用傳統測量方法獲取樹冠的精確信息非常困難，三維激光掃描系統提供了便捷、快速、準確獲取樹冠表面三維信息的方法，使用迭代漸進的凸包算法對樹冠點云進行外輪廓提取，不僅能夠對樹冠體積進行精細的計算，也為樹冠的信息提取與精細自動建模工作提供了基礎。本文所述算法更為精確的提取出了樹冠的外輪廓點，有效彌補了傳統凸包算法應用在樹冠外輪廓提取中的不足。

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

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

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

[4] 管西鵬. 樹木三維點云數據分析與建模技術研究[D].長沙：中南林業科技大學,2015.

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

[6] 梁子瑜.基于TLS點云數據的林分調查因子測定及收獲估計[D].南京：南京林業大學，2015.

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

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

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

[10] 韋雪花，王永國，鄭君，等. 基于三維激光掃描點云的樹冠體積計算方法[J]. 農業機械學報，2013(7): 235-240.

[11] 樊仲謀，馮仲科，鄭君，等. 基于立方體格網法的樹冠體積計算與預估模型建立[J]. 農業機械學報，2015(3)：320-327.

[12] 鞏垠熙，何誠，馮仲科，等. 基于改進Delaunay算法的樹冠三維重構單木因子提取[J]. 農業機械學報，2013(2): 192-199.

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

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

[15] 黃俊杰，羅周全，秦亞光，等. 復雜采空區三維散亂點建模技術研究及應用[J]. 東北大學學報(自然科學版)，2016，37(12)：1784-1788.

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

[17] 蔣聯源. 凸殼算法及其應用研究[D]. 南京：廣西師范大學，2007.

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

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