一種樹葉點云的逼真建模方法

趙艷妮，郭華磊

（1.陜西職業技術學院計算機科學系，西安　710100；2.西安理工大學計算機科學與工程學院，西安　710048；3.西安通信學院信息服務系，西安　710106）

一種樹葉點云的逼真建模方法

趙艷妮1，2，郭華磊3

（1.陜西職業技術學院計算機科學系，西安710100；2.西安理工大學計算機科學與工程學院，西安710048；3.西安通信學院信息服務系，西安710106）

針對點云建模細節和逼真性不足的問題，提出一種基于樹葉點云的逼真建模方法。首先，預處理樹葉點云數據，然后，結合樹葉點云數據映射的二維圖像，提取樹葉的邊界點和葉脈點，在保留樹葉點云數據邊界點和葉脈點的基礎上精簡樹葉原始點云，接著，對精簡后的樹葉點云數據進行Delaunay三角網格化，最后，基于網格模型對樹葉點云數據進行逼真的顏色紋理映射。實驗結果表明，該方法能夠快速準確地重構出逼真的樹葉模型。

點云；樹葉；數據精簡；紋理映射

陜西省科技廳自然科學基金（No.2014JM8354）、陜西省教育廳重點實驗室科技項目（No.13JS083）

0　引言

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

在逼真程度和細節特征方面，上述樹葉建模方法都存在不足。為此，本文以樹葉點云并結合圖像為基礎，以梧桐樹葉和楊樹葉為研究對象，深入研究了樹葉的逼真建模，結合三維點云數據和成熟的二維圖像特征提取技術，實現樹葉點云數據邊界點和葉脈點的提取，構建逼真的樹葉模型。

1　樹葉點云的簡化

TOPCON的GLS-1500三維激光掃描儀測距精度為4mm/150m，掃描的樹葉點云數據規模有幾萬、幾十萬。采用過多的數據建模，不但消耗大量的計算機資源，而且過于密集的點云數據直接影響模型的光滑性。為了使重建后的樹葉模型邊緣平滑且細節豐富，點云數據精簡過程中最大程度保留邊界點和葉脈點［7］。基本原理：先嚴格按照優先序列對數據進行簡化，直到剩余點數達到預先指定的點個數；最后將精簡的結果和前面提取的葉脈點及邊界點進行合并［8］。具體算法如下：

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

（4）將精簡后的點集和葉脈點及邊界點進行合并；

（5）算法結束。

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

圖2　精簡楊樹樹葉點云數據

表1　對比兩種算法所保留的邊界點

2　葉脈點和邊界點的求取

利用樹葉的葉脈可以探索樹木間的遺傳關系、重構樹葉模型等。激光樹葉點云數據包含樹葉的三維空間信息，但缺少樹葉的紋理信息［9］。樹葉的二維圖像雖然沒有三維空間信息，但包含樹葉的紋理信息，并且特征識別和提取算法相對成熟。結合點云數據和二維圖像各自優勢，利用二維圖像特征提取技術完成點云數據邊界點和葉脈點的提取［10］。

本文采用TOPCON GLS-1500三維激光掃描儀采集樹葉的三維坐標信息和二維圖像信息。結合三維點云數據和二維圖像優點，提出一種二維數字圖像輔助三維激光點云特征提取算法，基本原理如下：將點云數據投影到二維圖像，采用成熟的圖像處理算法提取出相關特征，根據映射關系，計算圖像相關特征在點云數據中的對應點集［11］。具體過程如下：

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

（2）將三維樹葉點云數據投影為二維樹葉圖像。假設點云數據有N個點，將點云數據投影到XOZ平面，二維圖像高度為height，寬度為width。設根據公式（1）、（2）計算點云數據（xi，yi，zi）投影到二維圖像的相應坐標（h，w）：

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

若以上兩個誤差滿足公式（5），則點（xi，yi，zi）為邊界點或葉脈點；

（4）算法結束。

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

圖3　提取梧桐樹葉的葉脈點和邊界點

圖4　提取楊樹樹葉的葉脈點和邊界點

圖3實驗結果表明本文算法能夠把樹葉的邊界點和葉脈點從樹葉點云數據中準確高效提取。由于二維黑白圖像和誤差閾值直接影響提取結果，為了驗證本文算法的準確率，對比手工標記的樹葉邊界點和本文算法提取的邊界點，準確率如表2所示。

表2　準確率

3　紋理映射

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

3.1Bowyer-Watson三角網格化

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

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

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

（3）對新形成的局部三角形進行優化，結果存儲在Delaunay三角形鏈表中；

（4）重復執行步驟（2），直到所有散點插入到三角形鏈表；

（5）算法結束。

圖5為采用Bowyer-Watson算法三角網格化精簡后的點云數據的實驗結果。圖5（a）為網格化精簡后的梧桐樹葉的實驗結果，（b）為網格化精簡后的楊樹樹葉的實驗結果。

圖5　三角網格化點云數據

3.2逼真紋理映射

紋理映射本質上是將紋理圖像的坐標和三角網格的坐標建立一種對映射關系［14］。本文首先將點云數據映射到樹葉圖像上，即將樹葉圖像作為紋理圖像。然后通過映射關系計算點云集中所有點的紋理坐標［15］。具體步驟如下：

（1）初始化。設網格模型有N個頂點，頂點坐標為（xi，yi，zi）。設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）計算坐標為（xi，yi，zi）點的紋理坐標u，v，如公式（6）和公式（7）所示：

（3）根據步驟（2）計算的紋理坐標，對樹葉點云進行紋理映射；

（4）算法結束。

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

圖6　紋理映射后的樹葉

4　結語

本文提出了一種樹葉點云的逼真建模方法，首先樹葉點云數據進行精簡，使用Bowyer-Watson算法三角網格化精簡的點云數據，并建立紋理圖像坐標和網格模型頂點坐標的映射關系，然后根據映射關系計算所有頂點的紋理坐標，最后利用紋理映射實現逼真建模。實驗驗證了本文方法較好從樹葉原始點云數據中提取邊界點和葉脈點，重構的樹葉模型細節豐富，邊緣光滑。

［1］Rodkaew Y，Lursinsap C，Fujimoto 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，Falcao A J，Fernandes 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－），女，陜西藍田人，講師，博士研究生，研究方向為虛擬現實、模式識別等

2016-06-14

2016-09-05

郭華磊（1981－），男，河南泌陽人，碩士，講師，研究方向為圖像處理