葉雯　云挺

（1信息化建設(shè)與管理辦公室，南京工程學(xué)院，江蘇　南京　211167）

（2信息科學(xué)技術(shù)學(xué)院，南京林業(yè)大學(xué)，江蘇　南京　210037）

活立木樹(shù)干點(diǎn)云數(shù)據(jù)特征提取

葉雯1云挺2

（1信息化建設(shè)與管理辦公室，南京工程學(xué)院，江蘇南京211167）

（2信息科學(xué)技術(shù)學(xué)院，南京林業(yè)大學(xué)，江蘇南京210037）

活立木樹(shù)干點(diǎn)云數(shù)據(jù)非常龐雜散亂，其三維重建的關(guān)鍵是局部拓?fù)浣Y(jié)構(gòu)及特征提取的快速實(shí)現(xiàn)。利用對(duì)K近鄰一般搜索算法進(jìn)行精簡(jiǎn)獲得的拓?fù)湫畔?，結(jié)合運(yùn)用特征提取的相關(guān)算法，采取逐步逼近的方法提取樹(shù)干特征點(diǎn)，為實(shí)現(xiàn)活立木點(diǎn)云數(shù)據(jù)模型化作了初步探討。

點(diǎn)云數(shù)據(jù)活立木特征提取

1　引言

林業(yè)樹(shù)木的監(jiān)測(cè)和精細(xì)識(shí)別一直是個(gè)難題，隨著計(jì)算機(jī)技術(shù)、數(shù)字圖像處理技術(shù)和信息技術(shù)的發(fā)展以及智能機(jī)的研發(fā)應(yīng)用，為解決這一難題找到了突破口。利用掃描得到的點(diǎn)云數(shù)據(jù)進(jìn)行三維重建，進(jìn)而獲取林木生物學(xué)特征參數(shù)及三維模型的技術(shù)在林木生產(chǎn)、果樹(shù)栽培、園林綠化等多方面引起了人們廣泛的關(guān)注。

Xu等人［1］提出了基于非稠密的點(diǎn)云數(shù)據(jù)獲取樹(shù)木主骨架，再結(jié)合圖形學(xué)模擬算法構(gòu)建逼真度高的分枝和方向感強(qiáng)的葉片。Thies［2］和Binney［3］針對(duì)激光點(diǎn)云數(shù)據(jù)采用鏈表結(jié)構(gòu)的空間連續(xù)重疊的圓柱體來(lái)擬合樹(shù)木主枝干，對(duì)樹(shù)木胸徑、樹(shù)高、尖削度和傾斜度等參數(shù)進(jìn)行了估計(jì)，得到枝干連接位置、角度、半徑和長(zhǎng)度等信息并和真實(shí)數(shù)據(jù)進(jìn)行比較；Wezyk等［4］提出采用體素法與管道擬合法相結(jié)合處理點(diǎn)云數(shù)據(jù)，根據(jù)樹(shù)干截面點(diǎn)云數(shù)據(jù)的凸殼（convex hull）來(lái)計(jì)算胸徑等指標(biāo)。Tansey等［5］采用最小二乘的形狀匹配法以及霍夫變換法對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)在林分密度較大林地內(nèi)的活立木材積和樹(shù)高測(cè)量并不成功。R.Mech and P.Prusinkiewicz用某種數(shù)學(xué)模型模擬樹(shù)木的生長(zhǎng)或形態(tài)特性，通過(guò)少量的參數(shù)產(chǎn)生復(fù)雜的樹(shù)結(jié)構(gòu)，他們認(rèn)為不同種類的樹(shù)木可能需要使用不同的數(shù)學(xué)模型［6］。

倪小軍等［7］基于已有的算法，提出了一種新的特征保留的點(diǎn)云自適應(yīng)精簡(jiǎn)算法，該算法首先最大程度地保留了模型特征，其次對(duì)于特征不明顯的點(diǎn)進(jìn)行了有效的自適應(yīng)精簡(jiǎn)，解決了某些算法中模型由于精簡(jiǎn)帶來(lái)空洞或者簡(jiǎn)化率太差的問(wèn)題，而且避免了基于曲率精簡(jiǎn)算法中時(shí)間消耗長(zhǎng)的不足；他們甚至認(rèn)為該算法能夠適應(yīng)不同表面形狀的點(diǎn)云模型。

本文的研究對(duì)象是速生的楊樹(shù)活立木中軸部分，包括主干和中軸部分的枝條葉片，簡(jiǎn)稱樹(shù)干。楊樹(shù)活立木枝葉分生散亂隨意，主干幾何形狀也極不規(guī)整，由激光掃描儀得到的樹(shù)干實(shí)測(cè)數(shù)據(jù)非常龐雜散亂。點(diǎn)云數(shù)據(jù)三維重建的難點(diǎn)是對(duì)海量測(cè)量數(shù)據(jù)進(jìn)行精簡(jiǎn)，精簡(jiǎn)的關(guān)鍵是快速獲得其局部特征的拓?fù)浣Y(jié)構(gòu)并實(shí)現(xiàn)特征提取，而其算法的效率尤為重要。因此為了提高海量測(cè)量數(shù)據(jù)處理算法的效率，分別運(yùn)用鄰域彎曲度和曲率估計(jì)值提取點(diǎn)云數(shù)據(jù)的特征點(diǎn)，為實(shí)現(xiàn)活立木點(diǎn)云數(shù)據(jù)模型化進(jìn)行了初步探討。

2　點(diǎn)云數(shù)據(jù)的特征提取

本文初始數(shù)據(jù)來(lái)源于Cyclone激光掃描儀掃描人工楊樹(shù)單木得到的實(shí)測(cè)數(shù)據(jù)。本文首先根據(jù)點(diǎn)云數(shù)據(jù)集合C的范圍，對(duì)整個(gè)點(diǎn)云集合進(jìn)行劃分，得到多個(gè)幾何大小相同的子立方柵格，再利用記錄的子立方柵格內(nèi)點(diǎn)云的信息對(duì)每個(gè)點(diǎn)云進(jìn)行K近鄰搜索，從而獲取到整個(gè)活立木樹(shù)干點(diǎn)云數(shù)據(jù)的局部拓?fù)湫畔ⅲ?］。通過(guò)得到的局部拓?fù)湫畔?，?duì)整個(gè)點(diǎn)云模型進(jìn)行特征提取，這樣既完整保存實(shí)物模型的整體輪廓，而且能夠最大限度地保證模型局部區(qū)域特征［9］。

本文首先對(duì)數(shù)據(jù)點(diǎn)pi的K個(gè)鄰居點(diǎn)集合P進(jìn)行協(xié)方差分析［10］，得到其鄰域協(xié)方差矩陣：

式中Zi為半正定的三階對(duì)稱矩陣，其中是集合P的重心：

2.1局部區(qū)域彎曲度計(jì)算

點(diǎn)的鄰域彎曲度，它能夠近似表示該點(diǎn)附近的彎曲程度和特征明顯度，它不需要進(jìn)行復(fù)雜的曲率計(jì)算。處于特征明顯地段的點(diǎn)的鄰域彎曲度大，相反處于特征不明顯，不尖銳的地方的點(diǎn)的鄰域彎曲度小。

其中<，>為向量之間的點(diǎn)積符號(hào)，‖‖為求向量模長(zhǎng)符號(hào)［7］。

根據(jù)公式（11）的計(jì)算結(jié)果，選取彎曲度大的點(diǎn)作為特征點(diǎn)，即可以實(shí)現(xiàn)點(diǎn)云模型的特征提取。

具體的特征保留的點(diǎn)云自適應(yīng)精簡(jiǎn)算法步驟如下：

（1）根據(jù)K近鄰，求出每個(gè)點(diǎn)的鄰域彎曲度值k（pi），并根據(jù)每個(gè)點(diǎn)的k（pi）值，依次將點(diǎn)分別歸類到4個(gè)點(diǎn)集，然后根據(jù)所在區(qū)間將其分別標(biāo)記為S1、S2、S3、S4。

（3）遍歷點(diǎn)云進(jìn)行精簡(jiǎn)。

（4）對(duì)處理后的點(diǎn)云，僅僅讀取“保留”狀態(tài)的點(diǎn)，刪除所有“刪除”狀態(tài)的點(diǎn)。

2.2局部區(qū)域曲率估計(jì)

曲面的曲率信息是曲面特征識(shí)別的重要依據(jù)，曲率大小反映模型表面的凸凹程度。在點(diǎn)云數(shù)據(jù)模型中，曲率信息被廣泛用于數(shù)據(jù)分割和簡(jiǎn)化等處理中。

根據(jù)法向ni估計(jì)曲率Hi：

通過(guò)公式（3）計(jì)算得到的曲率作為點(diǎn)云模型的法向，將整個(gè)模型中的尖銳部分，即曲率比較大的點(diǎn)提取出來(lái)，即可以實(shí)現(xiàn)點(diǎn)云模型的特征提取。

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

本文的實(shí)驗(yàn)平臺(tái)是Microsoft visual studio 2005，在結(jié)合OpenGL的基礎(chǔ)上，又嵌入了OpenCV技術(shù)。運(yùn)算過(guò)程中，利用其中的庫(kù)函數(shù)和函數(shù)類來(lái)求解矩陣，快捷地得到了矩陣Zi的三個(gè)特征值λ1，λ2，λ3及其對(duì)應(yīng)的單位特征向量e1，e2，e3，用于求解鄰域彎曲度及曲率，其中假定λ1為三個(gè)特征值中最小值。這樣根據(jù)彎曲度計(jì)算結(jié)果和曲率估計(jì)值即可分別實(shí)現(xiàn)點(diǎn)云模型的特征提取。其中，求取彎曲度以及估計(jì)曲率的鄰域協(xié)方差矩陣Zi的部分偽代碼如下：

立木點(diǎn)云數(shù)據(jù)的截?cái)嗥我约罢w柵格見(jiàn)圖1。

圖1　截?cái)嗥我约罢w柵格

圖2為原始點(diǎn)云，圖3為用文獻(xiàn)［7］提供的算法通過(guò)計(jì)算彎曲度獲得的特征提取效果圖。

圖2　楊樹(shù)三維點(diǎn)云數(shù)據(jù)片段888_correct原圖

圖3　楊樹(shù)三維點(diǎn)云數(shù)據(jù)片段888_correct基于彎曲度的特征提取

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

本文研究對(duì)象楊樹(shù)活立木點(diǎn)云數(shù)據(jù)非常龐雜散亂?；盍⒛救S重建的難點(diǎn)是對(duì)龐雜散亂的點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)，精簡(jiǎn)的關(guān)鍵是快速獲取其局部特征的拓?fù)浣Y(jié)構(gòu)并實(shí)現(xiàn)特征提取，而其算法的效率尤為重要。因此為了提高模型化算法的效率，本文在保證一定精準(zhǔn)度的前提下，對(duì)K近鄰一般搜索算法進(jìn)行了有效精簡(jiǎn)，快速地獲取了點(diǎn)云數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，大大節(jié)省了運(yùn)算時(shí)間，從而提高了點(diǎn)云數(shù)據(jù)處理的算法效率。本文利用快速獲得的拓?fù)湫畔ⅲY(jié)合運(yùn)用點(diǎn)云數(shù)據(jù)特征提取的相關(guān)算法，分別獲得鄰域彎曲度和曲率估計(jì)值后，重點(diǎn)使用逐步逼近的方法對(duì)點(diǎn)云數(shù)據(jù)的特征點(diǎn)提取過(guò)程作了有效簡(jiǎn)化，為實(shí)現(xiàn)活立木點(diǎn)云數(shù)據(jù)模型化進(jìn)行了初步探討。

［1］XU H，GOSSETT N，CHEN B.Knowledge and heuristic based modeling of laser-scanned trees［J］.ACM Transactions on Graphics，2007，26（04）：303-308.

［2］THIES M，PFEIFER N，WINTERHALDER D，et al. Three-dimensional reconstruction of stems for assessment of taper sweep and lean based on laser scanning of standing trees ［J］.Scandinavian Journal of Forest Research，2004，19（6）：571-581.

［4］WEZYK P，KOZIOL K，GLISTA M，et al.Terrestrial laser scanning versus traditional forest inventory.First results from the Polish forests［C］//Proceedings of the ISPRS Workshop ‘Laser Scanning，2007：12-14.

［5］TANSEY K，SELMES N，ANSTEE A，et al.Estimating tree and stand variables in a Corsican Pine woodland from terrestrial laser scanner data［J］.International Journal of Remote Sensing，2009，30（19）：5195-5209.

［7］倪小軍，姜曉峰，葛亮.特征保留的點(diǎn)云數(shù)據(jù)自適應(yīng)精簡(jiǎn)算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28（8）：38-39.

［8］葉雯，云挺，業(yè)寧.基于點(diǎn)云數(shù)據(jù)的立木樹(shù)干局部曲面擬合及拓?fù)浣Y(jié)構(gòu)［J］.山東大學(xué)學(xué)報(bào)（工學(xué)版），2013，43（2）：42-47.

［9］王麗輝，袁保宗.三維散亂點(diǎn)云模型的特征點(diǎn)檢測(cè)［J］.信號(hào)處理，2011，27（6）：932-938.

［10］HOPPE H，DEROSE T，DUCHAMPT T，et al.Surface Reconstruction from Unorganized Points［C］// SIGGRAPH'92 conference proceedings.Addison-Wesley：ACM SIGGRAPH，1992：71-78.

Point Cloud Data Feature Extraction for the Standing Timber Trunk

YE Wen，YUN Ting
（1 Information construction and management office，Nanjing Institute of Technology，Nanjing，JiangSu 211167 China）
（2 School of Information Science&Technology，Nanjing Forestry University，Nanjing，JiangSu 210037 China）

The point cloud data of Standing timber trunk is numerous and jumbled.It is the key point for 3D Reconstruction to obtain local topology structure fastly and achieve feature extraction.For data modeling，this paper applies topology information obtained by K-Nearest Neighbours Searching，combined with the use of feature extraction algorithms，take gradually approaching the trunk feature points extraction，for the realization of stumpage point cloud data model turned into the preliminary discussion.

point cloud data，standing timber，feature extraction

TP3-05

A

1008-1739（2015）11-61-3

定稿日期：2015-05-12

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)資助項(xiàng)目(2011CB707904);國(guó)家自然科學(xué)基金資助項(xiàng)目(30671639);江蘇省自然科學(xué)基金資助項(xiàng)目(BK2009393);南京林業(yè)大學(xué)高學(xué)歷人才基金資助項(xiàng)目(163070052)