趙艷妮，郭華磊

（1.陜西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)系，西安　710100；2.西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，西安　710048；3.西安通信學(xué)院信息服務(wù)系，西安　710106）

一種樹葉點(diǎn)云的逼真建模方法

趙艷妮1，2，郭華磊3

（1.陜西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)系，西安710100；2.西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，西安710048；3.西安通信學(xué)院信息服務(wù)系，西安710106）

針對點(diǎn)云建模細(xì)節(jié)和逼真性不足的問題，提出一種基于樹葉點(diǎn)云的逼真建模方法。首先，預(yù)處理樹葉點(diǎn)云數(shù)據(jù)，然后，結(jié)合樹葉點(diǎn)云數(shù)據(jù)映射的二維圖像，提取樹葉的邊界點(diǎn)和葉脈點(diǎn)，在保留樹葉點(diǎn)云數(shù)據(jù)邊界點(diǎn)和葉脈點(diǎn)的基礎(chǔ)上精簡樹葉原始點(diǎn)云，接著，對精簡后的樹葉點(diǎn)云數(shù)據(jù)進(jìn)行Delaunay三角網(wǎng)格化，最后，基于網(wǎng)格模型對樹葉點(diǎn)云數(shù)據(jù)進(jìn)行逼真的顏色紋理映射。實(shí)驗(yàn)結(jié)果表明，該方法能夠快速準(zhǔn)確地重構(gòu)出逼真的樹葉模型。

點(diǎn)云；樹葉；數(shù)據(jù)精簡；紋理映射

陜西省科技廳自然科學(xué)基金（No.2014JM8354）、陜西省教育廳重點(diǎn)實(shí)驗(yàn)室科技項(xiàng)目（No.13JS083）

0　引言

樹木的樹葉擁有不同的紋理和形態(tài)，同一片樹葉隨著季節(jié)和周圍氣候的變化，樹葉的紋理和形態(tài)存在差異。準(zhǔn)確、合理地重構(gòu)樹葉模型是虛擬現(xiàn)實(shí)領(lǐng)域近幾年研究的熱點(diǎn)之一。Rodkawe等［1］結(jié)合L系統(tǒng)和遺傳算法，重構(gòu)了樹葉的幾何模型；Mundermann等［2］利用樹葉二維圖像，提取樹葉輪廓，計(jì)算樹葉骨架等方法對樹葉進(jìn)行建模；El-Latif［3］利用B-樣條曲線原理構(gòu)造樹葉模型；Lei Wang等［4］利用雙三次Bezier曲面實(shí)現(xiàn)樹葉的建模。Shizeng G等［5］去除樹葉點(diǎn)云數(shù)據(jù)噪聲，對數(shù)據(jù)進(jìn)行網(wǎng)格化處理，并進(jìn)行平滑、優(yōu)化等處理，最終構(gòu)建樹葉的網(wǎng)格模型；Milenkovi M等［6］方法根據(jù)樹葉點(diǎn)云數(shù)據(jù)擬合出一個(gè)回歸平面，隨后將數(shù)據(jù)垂直投影到該平面并且提取樹葉邊界點(diǎn)，最后根據(jù)邊界點(diǎn)擬合橢圓來代表樹葉。

在逼真程度和細(xì)節(jié)特征方面，上述樹葉建模方法都存在不足。為此，本文以樹葉點(diǎn)云并結(jié)合圖像為基礎(chǔ)，以梧桐樹葉和楊樹葉為研究對象，深入研究了樹葉的逼真建模，結(jié)合三維點(diǎn)云數(shù)據(jù)和成熟的二維圖像特征提取技術(shù)，實(shí)現(xiàn)樹葉點(diǎn)云數(shù)據(jù)邊界點(diǎn)和葉脈點(diǎn)的提取，構(gòu)建逼真的樹葉模型。

1　樹葉點(diǎn)云的簡化

TOPCON的GLS-1500三維激光掃描儀測距精度為4mm/150m，掃描的樹葉點(diǎn)云數(shù)據(jù)規(guī)模有幾萬、幾十萬。采用過多的數(shù)據(jù)建模，不但消耗大量的計(jì)算機(jī)資源，而且過于密集的點(diǎn)云數(shù)據(jù)直接影響模型的光滑性。為了使重建后的樹葉模型邊緣平滑且細(xì)節(jié)豐富，點(diǎn)云數(shù)據(jù)精簡過程中最大程度保留邊界點(diǎn)和葉脈點(diǎn)［7］?；驹恚合葒?yán)格按照優(yōu)先序列對數(shù)據(jù)進(jìn)行簡化，直到剩余點(diǎn)數(shù)達(dá)到預(yù)先指定的點(diǎn)個(gè)數(shù)；最后將精簡的結(jié)果和前面提取的葉脈點(diǎn)及邊界點(diǎn)進(jìn)行合并［8］。具體算法如下：

（3）對于點(diǎn)Pi，若del_mark［i］為true，則繼續(xù)；否則查找點(diǎn)Pi的K個(gè)鄰接點(diǎn)中第一個(gè)未被標(biāo)記為true的點(diǎn)，并計(jì)算點(diǎn)Pi和該鄰接點(diǎn)距離，設(shè)其為dist；若dist＜min_dist并且該點(diǎn)既不是葉脈點(diǎn)又不是邊界點(diǎn)，則dist=min_dist，并采用變量temp_index記錄該鄰接點(diǎn)的索引。查找所有原始點(diǎn)云數(shù)據(jù)未被刪除的鄰接點(diǎn)中距離最近的點(diǎn)，置且轉(zhuǎn)到步驟（2）；

（4）將精簡后的點(diǎn)集和葉脈點(diǎn)及邊界點(diǎn)進(jìn)行合并；

（5）算法結(jié)束。

采用該算法的實(shí)驗(yàn)結(jié)果如圖1和圖2所示，圖1（a）是梧桐樹葉原始點(diǎn)云數(shù)據(jù)，圖2（a）是楊樹樹葉原始點(diǎn)云數(shù)據(jù)，圖1（b）和圖2（b）分別是梧桐樹葉和楊樹樹葉采用本文算法精簡掉3/4的點(diǎn)后的實(shí)驗(yàn)結(jié)果。表1保留邊界點(diǎn)的個(gè)數(shù)。表1表明本文的方法能更好地保留了樹葉的邊界點(diǎn)和葉脈點(diǎn)。

圖2　精簡楊樹樹葉點(diǎn)云數(shù)據(jù)

表1　對比兩種算法所保留的邊界點(diǎn)

2　葉脈點(diǎn)和邊界點(diǎn)的求取

利用樹葉的葉脈可以探索樹木間的遺傳關(guān)系、重構(gòu)樹葉模型等。激光樹葉點(diǎn)云數(shù)據(jù)包含樹葉的三維空間信息，但缺少樹葉的紋理信息［9］。樹葉的二維圖像雖然沒有三維空間信息，但包含樹葉的紋理信息，并且特征識別和提取算法相對成熟。結(jié)合點(diǎn)云數(shù)據(jù)和二維圖像各自優(yōu)勢，利用二維圖像特征提取技術(shù)完成點(diǎn)云數(shù)據(jù)邊界點(diǎn)和葉脈點(diǎn)的提?。?0］。

本文采用TOPCON GLS-1500三維激光掃描儀采集樹葉的三維坐標(biāo)信息和二維圖像信息。結(jié)合三維點(diǎn)云數(shù)據(jù)和二維圖像優(yōu)點(diǎn)，提出一種二維數(shù)字圖像輔助三維激光點(diǎn)云特征提取算法，基本原理如下：將點(diǎn)云數(shù)據(jù)投影到二維圖像，采用成熟的圖像處理算法提取出相關(guān)特征，根據(jù)映射關(guān)系，計(jì)算圖像相關(guān)特征在點(diǎn)云數(shù)據(jù)中的對應(yīng)點(diǎn)集［11］。具體過程如下：

（1）樹葉邊界和葉脈特征提取。首先采用中值濾波對樹葉圖像進(jìn)行降噪處理，接著采用雙邊濾波增強(qiáng)樹葉邊緣信息，然后使用Sobel算子提取樹葉的邊界和葉脈，最后采用二值化的方法對樹葉圖像進(jìn)行黑白處理。

（2）將三維樹葉點(diǎn)云數(shù)據(jù)投影為二維樹葉圖像。假設(shè)點(diǎn)云數(shù)據(jù)有N個(gè)點(diǎn)，將點(diǎn)云數(shù)據(jù)投影到XOZ平面，二維圖像高度為height，寬度為width。設(shè)根據(jù)公式（1）、（2）計(jì)算點(diǎn)云數(shù)據(jù)（xi，yi，zi）投影到二維圖像的相應(yīng)坐標(biāo)（h，w）：

（3）利用二維圖像特征求解點(diǎn)云數(shù)據(jù)相關(guān)特征點(diǎn)集。設(shè)X軸方向最大誤差x_delta=預(yù)先給定值，Z軸方向最大誤預(yù)先給定值。（h,w）處像素灰度值表示為其中從左到右，從上到下遍歷二維投影圖像，若（h，w）處像素的灰度值則計(jì)算（h，w）處像素映射的點(diǎn)云數(shù)據(jù)（xi，yi，zi）：

若以上兩個(gè)誤差滿足公式（5），則點(diǎn)（xi，yi，zi）為邊界點(diǎn)或葉脈點(diǎn)；

（4）算法結(jié)束。

采用本文算法提取梧桐、楊樹樹葉的葉脈點(diǎn)和邊界點(diǎn)，結(jié)果如圖3和圖4所示。圖3（a）為梧桐葉原始圖像，圖4（a）為楊樹葉原始圖像，圖3（b）為梧桐葉原始點(diǎn)云數(shù)據(jù)，圖4（b）為楊樹葉原始點(diǎn)云數(shù)據(jù)，圖3（c）為將點(diǎn)云數(shù)據(jù)圖3（b）投影到原始圖像圖3（a）的實(shí)驗(yàn)結(jié)果，圖4（c）為將點(diǎn)云數(shù)據(jù)圖4（b）投影到原始圖像圖4（a）的實(shí)驗(yàn)結(jié)果，圖3（d）和圖4（d）是二值化圖像，圖3（e）和圖4（e）是允許誤差都為0.005時(shí)求取的葉脈點(diǎn)和邊界點(diǎn)，圖3（f）和圖4（f）是允許誤差都為0.006時(shí)求取的葉脈點(diǎn)和邊界點(diǎn)。

圖3　提取梧桐樹葉的葉脈點(diǎn)和邊界點(diǎn)

圖4　提取楊樹樹葉的葉脈點(diǎn)和邊界點(diǎn)

圖3實(shí)驗(yàn)結(jié)果表明本文算法能夠把樹葉的邊界點(diǎn)和葉脈點(diǎn)從樹葉點(diǎn)云數(shù)據(jù)中準(zhǔn)確高效提取。由于二維黑白圖像和誤差閾值直接影響提取結(jié)果，為了驗(yàn)證本文算法的準(zhǔn)確率，對比手工標(biāo)記的樹葉邊界點(diǎn)和本文算法提取的邊界點(diǎn)，準(zhǔn)確率如表2所示。

表2　準(zhǔn)確率

3　紋理映射

紋理映射不需要過多考慮物體的細(xì)節(jié)即可生成極具真實(shí)感的物體，主要有兩類：幾何紋理映射、顏色紋理映射。本文采用顏色紋理映射來實(shí)現(xiàn)樹葉真實(shí)感繪制。

3.1Bowyer-Watson三角網(wǎng)格化

三角網(wǎng)格模型形狀簡單，方便存儲、分析和繪制，能夠表述具有復(fù)雜拓?fù)涞男误w，而且可以根據(jù)實(shí)際需要任意精度的逼近物體表面，成為曲面重建的重要描述方式［12］。本文采用Bowyer-Watson算法［10］實(shí)現(xiàn)樹葉點(diǎn)云數(shù)據(jù)的三角網(wǎng)格化，并手動(dòng)刪除冗余。具體步驟如下：

（1）新建一個(gè)包含所有樹葉點(diǎn)云散點(diǎn)的三角形，并存儲在三角形鏈表中；

（2）將散點(diǎn)依次插入到三角形，并在三角形鏈表中查找外切圓包含當(dāng)前插入散點(diǎn)的三角形，刪除該三角形的公共邊，并將該三角形全部頂點(diǎn)和當(dāng)前插入散點(diǎn)連接，形成新的三角形［13］。在鏈表中刪除已經(jīng)消失的三角形并將新形成的三角形插入到鏈表中；

（3）對新形成的局部三角形進(jìn)行優(yōu)化，結(jié)果存儲在Delaunay三角形鏈表中；

（4）重復(fù)執(zhí)行步驟（2），直到所有散點(diǎn)插入到三角形鏈表；

（5）算法結(jié)束。

圖5為采用Bowyer-Watson算法三角網(wǎng)格化精簡后的點(diǎn)云數(shù)據(jù)的實(shí)驗(yàn)結(jié)果。圖5（a）為網(wǎng)格化精簡后的梧桐樹葉的實(shí)驗(yàn)結(jié)果，（b）為網(wǎng)格化精簡后的楊樹樹葉的實(shí)驗(yàn)結(jié)果。

圖5　三角網(wǎng)格化點(diǎn)云數(shù)據(jù)

3.2逼真紋理映射

紋理映射本質(zhì)上是將紋理圖像的坐標(biāo)和三角網(wǎng)格的坐標(biāo)建立一種對映射關(guān)系［14］。本文首先將點(diǎn)云數(shù)據(jù)映射到樹葉圖像上，即將樹葉圖像作為紋理圖像。然后通過映射關(guān)系計(jì)算點(diǎn)云集中所有點(diǎn)的紋理坐標(biāo)［15］。具體步驟如下：

（1）初始化。設(shè)網(wǎng)格模型有N個(gè)頂點(diǎn)，頂點(diǎn)坐標(biāo)為（xi，yi，zi）。設(shè)max_x=max｛xi|0≤i≤N｝，min_x=min｛xi|0≤i≤N｝，max_z=max｛zi|0≤i≤N｝，min_z=min｛zi|0≤i≤N｝；

（2）計(jì)算坐標(biāo)為（xi，yi，zi）點(diǎn)的紋理坐標(biāo)u，v，如公式（6）和公式（7）所示：

（3）根據(jù)步驟（2）計(jì)算的紋理坐標(biāo)，對樹葉點(diǎn)云進(jìn)行紋理映射；

（4）算法結(jié)束。

如圖6所示，由于較好保留了葉脈點(diǎn)和邊界點(diǎn)，重構(gòu)模型邊緣光滑清晰，紋理映射效果逼真。

圖6　紋理映射后的樹葉

4　結(jié)語

本文提出了一種樹葉點(diǎn)云的逼真建模方法，首先樹葉點(diǎn)云數(shù)據(jù)進(jìn)行精簡，使用Bowyer-Watson算法三角網(wǎng)格化精簡的點(diǎn)云數(shù)據(jù)，并建立紋理圖像坐標(biāo)和網(wǎng)格模型頂點(diǎn)坐標(biāo)的映射關(guān)系，然后根據(jù)映射關(guān)系計(jì)算所有頂點(diǎn)的紋理坐標(biāo)，最后利用紋理映射實(shí)現(xiàn)逼真建模。實(shí)驗(yàn)驗(yàn)證了本文方法較好從樹葉原始點(diǎn)云數(shù)據(jù)中提取邊界點(diǎn)和葉脈點(diǎn)，重構(gòu)的樹葉模型細(xì)節(jié)豐富，邊緣光滑。

［1］Rodkaew Y，Lursinsap C，F(xiàn)ujimoto T，et al.Modeling Leaf Shapes Using L-Systems and Genetic Algorithms［C］.International Conference NICOGRAPH.2002：73-78.

［2］Mundermann L，MacMurchy P，Pivovarov J，et al.Modeling Lobed Leaves［C］.Computer Graphics International，2003.Proceedings.IEEE，2003：60-65

［3］El-Latif A，Mohamed Y.A New Model for the Structure of Leaves［J］.Journal of Software，2011，6（4）：670-677.

［4］Wang L，Lu L，Jiang N.A Study of Leaf Modeling Technology based on Morphological Features［J］.Mathematical and Computer Mod-elling，2011，54（3）：1107-1114.

［5］Shizeng G，Huaiqing Z，Min L，et al.Application Analysis of Laser Scanning Technology in Trees Measurement［C］.Computer Science and Automation Engineering（CSAE），2012 IEEE International Conference on.IEEE，2012，2：692-696.

［6］Milenkovi M，Eysn L，Hollaus M，et al.Modeling the Tree Branch Structure at Very High Resolution［C］.SilviLaser 2012，the 12th International Conferencr on LiDAR Applications for assessing Forest Ecosystems Freiburg，Canada，2012：1-8.

［7］Huang H，Wu S，Cohen-Or D，et al.L1-Medial Skeleton of Ooint Cloud［J］.ACM Trans.Graph.，2013，32（4）：1-8.

［8］Zhou Q Y，Neumann U.Complete Residential Urban Area Reconstruction from Dense Aerial LiDAR Point Clouds［J］.Graphical Models，2013，75（3）：118-125.

［9］Burgess R，F(xiàn)alcao A J，F(xiàn)ernandes T，et al.Selection of Large-Scale 3D Point Cloud Data Using Gesture Recognition［M］.Technological Innovation for Cloud-Based Engineering Systems.Springer International Publishing，2015：188-195.

［10］Morell V，Orts S，Cazorla M，et al.Geometric 3D point cloud compression［J］.Pattern Recognition Letters，2014，50：55-62.

［11］Paulus S，Schumann H，Kuhlmann H，et al.High-Precision Laser Scanning System for Capturing 3D Plant Architecture and Analysing Growth of Cereal Plants［J］.Biosystems Engineering，2014，121：1-11.

［12］Ramaswamy A K，Monsuez B，Tapus A.Solution Space Modeling for Robotic Systems［J］.Journal for Software Engineering Robotics（JOSER），2014，5（1）：89-96.

［13］Kaasalainen S，Krooks A，Liski J，et al.Change Detection of Tree Biomass with Terrestrial Laser Scanning and Quantitative Structure Modelling［J］.Remote Sensing，2014，6（5）：3906-3922.

［14］Li W，Guo Q，Jakubowski M K，et al.A New Method for Segmenting Individual Trees from the Lidar Point Cloud［J］.Photogrammetric Engineering&Remote Sensing，2012，78（1）：75-84.

［15］Xing Z Q，Deng K Z，Xue J Q.Initial Registration for Point Cloud Based on K-Nearest Neighbor Search［J］.Science of Surveying and Mapping，2013，38（2）：93-95.

A Leaves Realistic Modeling Approach Based on Point Cloud

ZHAO Yan-ni1，2，GUO Hua-lei3
（1.Department of Computer Science，Shannxi Vocational&Technical College，Xi'an 710100；2.School of Computer Science and Engineering，Xi'an University of Technology，Xi'an 710048；
3.Department of Information Service，Xi'an Communications Institute，Xi'an 710106）

In view of the problem of the lack of detail and fidelity of point cloud modeling，proposes a method that based on point cloud leaves photorealistic rendering.Firstly，preprocesses leaves point cloud data，then，combined with the two-dimensional image of the leaves point cloud data is mapped，leaves the boundary points and veins point extraction，while retaining leaves little cloud data boundary points and veins point based on streamlined leaves the original point cloud.Then，Delaunay triangulation of streamlined leaves point cloud data.Finally，the leaves of point cloud data of vivid color texture mapping based on mesh model.Experimental results show that the method can quickly and accurately reconstruct the realistic leaf model.

Point Cloud；Leaves；Data Reduction；Texture Mapping

1007-1423（2016）26-0052-05DOI：10.3969/j.issn.1007-1423.2016.26.013

趙艷妮（1982－），女，陜西藍(lán)田人，講師，博士研究生，研究方向?yàn)樘摂M現(xiàn)實(shí)、模式識別等

2016-06-14

2016-09-05

郭華磊（1981－），男，河南泌陽人，碩士，講師，研究方向?yàn)閳D像處理