一种树叶点云的逼真建模方法

赵艳妮，郭华磊

（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－），男，河南泌阳人，硕士，讲师，研究方向为图像处理