蒙彼利埃大学2博士学校I2S信息科学与信息学P H D T H E S I S获得...的称号理学博士蒙彼利埃大学的专长：计算机科学捍卫查克里特·普卢克萨卡恩从三维激光扫描仪数据重建植物虚拟植物团队，UMR AGAP，CIRAD/INRIA/INRA定于2012陪审团：审稿人/主席：BernardMOURRAIN-INRIA审稿人：FrédéricBet-INRA顾问：ChristopheGO dI n-INRIA共同顾问：FrédéricBOUDON- CIRAD检查员：GerardSUBSOL-CNRS杰拉尔丁·莫里- INPT邀请人：Pierre-EricLAURI-INRA摘要虚拟植物模型可以在视觉上逼真的计算机图形应用。然而，在生物学和农学的背景下，获取真实植物的精确模型仍然是一项繁琐且耗时的任务，并且是构建植物发育定量模型的主要瓶颈近来，3D激光扫描仪已经使得能够获取3D图像，在该3D图像上，每个像素具有与扫描仪和对象的精确定位的表面之间的距离相对应的关联深度然而，植物通常是一组不连续的表面模糊地分布在一定体积的植被。经典的几何重建对于这种特殊类型的几何体是失败的在这篇论文中，我们提出了一种方法来重建虚拟模型的植物从激光扫描现实世界的植被。使用激光扫描仪测量工厂可以产生不同精度水平的数据点集通常在树干和主枝的表面上密集，但仅稀疏地覆盖细枝。该方法的核心是根据点集的局部密度迭代生成植物的骨架结构。这是由于局部自适应的方法结合了收缩阶段和局部点跟踪算法的数据的精度水平此外，我们还开发了一个定量评估程序，将我们的重建与真实植物的专业结构进行为此，我们首先探索树图之间的编辑距离的使用。或者，我们将比较形式化为分配问题，以找到两个结构之间的最佳匹配并量化它们的差异。简历在信息图表中，植物的虚拟模型是最真实的视觉模型。然而，在生物学和Récement，des scanners laser 3D permettent d'acquérir des images 3D avecpour chaque pixel une profondeur correspondant à la distance entre le scanner etla surface de l'objet visé.同时，一个工厂是一个整体重要的小表面上lesquelles les方法分类重建échouent。在此，我们提出了一种方法来恢复激光扫描部分的虚拟设备。测量植物与一个扫描仪激光产品的données与精密的niveaux。主要分支表面上的扫描一般是密集的，但可以从分支点处获得。我们的方法是根据点的密度分布对植物的结构进行迭 代 。 Pour cela ， une methode localement adaptative a été décampée quicombine une phase de contraction et un algorithme de suivi de points.Nous présentons également une procédure为了这个目的，我们探索了利用树木生长的一个距离最后，我们形成了一个问题，以确定两种结构之间的最佳外观，并对这些结构进行定量分析确认首先，我要感谢我的第一位博士生导师，Christophe Godin。他在这一过程中的指导和支持是宝贵的。接下来我要感谢弗雷德里克·布东，他接管了监督的任务，更重要的是，帮助这项工作成为可能。他的热情和科学知识一直是这篇论文背后的巨大动力和推动力这项工作极大地得益于他的思想和建议。在此，我向论文委员会的各位委员表示衷心的感谢。感谢Bernard Bastrain和Frédéric Barret对本论文的草稿提出了许多有见地的评论，并感谢他们的可用性。感谢Gerard Subsol，Geraldine Morin和Pierre-Eric Lauri对我们在防守方面的建设性意见和讨论我还要感谢Pascal Ferraro和Jean-Beptiste Durand，他们帮助设计和实现了本文中开发的几个算法。此外，我要感谢Eero Nikinmaa和Eric Casella，他们在测试设备和数据方面给予了很大的帮助。非常感谢虚拟工厂团队的所有同事。他们总是创造一个非常友好和友好的气氛。特别感谢Yassin Refahi的帮助。我还要感谢泰国Kasetsart大学和国家计算机科学与控制研究所（INRIA）对我的慷慨资助最后，我还要感谢我生命中最重要的人，我的妻子和儿子，他们一直在那里支持我，无条件地支持我。内容摘要i简历三鸣谢v介绍11测量并将形状表示为点31.1测量技术.....................................................................................................................31.1.1触觉接触方法.........................................................................................41.1.2非接触式方法.........................................................................................41.23D激光扫描仪.................................................................................................... 91.2.1范围确定...............................................................................................111.2.2坐标系和变换.......................................................................................121.2.3积分注册...............................................................................................131.3点基元................................................................................................................171.3.1邻里.......................................................................................................171.3.2点法线...................................................................................................181.4点数据结构........................................................................................................1.4.1基于.......................................................................................................网格191.4.2八叉树...................................................................................................1.4.3K-D树....................................................................................................201.5点集....................................................................................................................的一般重建方法211.5.1表面重建...............................................................................................211.5.2骨骼重建...............................................................................................232 植物结构表示312.1全球代表情况....................................................................................................312.1.1基于包络的表示......................................................................................... 312.1.2基于分区的代表性..................................................................................... 362.2 详细介绍............................................................................................................372.2.1空间表示...............................................................................................382.2.2 Topologicalrepresentations拓扑表示.....................................................392.2.3 几何表示...............................................................................................443植物模型55的获取与重建方法综述3.1三维数字化........................................................................................................553.1.1接触数字化...........................................................................................553.1.2非接触式数字化...................................................................................573.2 从草图中............................................................................................................建模植物结构583.3 基于图像的植物建模........................................................................................613.3.1图像分割...............................................................................................623.3.2 重建.......................................................................................................623.4 基于3D点.......................................................................................................... 重建植物模型644激光扫描仪71的植物建模流程4.1植物材料............................................................................................................714.2 预处理................................................................................................................754.3 点模式................................................................................................................754.4 重建管道............................................................................................................764.5 点的特性描述....................................................................................................784.5.1局部邻域图...........................................................................................784.5.2 点局部密度...........................................................................................794.5.3 点局部方向...........................................................................................804.6 收缩....................................................................................................................点824.7 骨骼重建............................................................................................................844.7.1点跟踪算法...........................................................................................844.7.2 通过聚集点方向确定分支方向...........................................................874.8 表面重建............................................................................................................894.8.1直径.......................................................................................................估计894.8.2 表面.......................................................................................................的重建904.9 重建....................................................................................................................的结果905重建模型955.1全球比较方法....................................................................................................5.1.1建筑植物特性评估...............................................................................955.1.2辐射冠层特性评估...............................................................................5.2 结构比较方法....................................................................................................975.3 工厂建筑............................................................................................................之间的距离测量985.3.1编辑操作...............................................................................................985.3.2 编辑映射...............................................................................................995.4 工厂建筑............................................................................................................的比较995.4.1使骨架结构............................................................................................... 化1005.4.2 局部成本函数.....................................................................................1015.4.3 第一批结果.........................................................................................1025.5基于几何标准..................................................................................................的工厂比较1035.6 评估..................................................................................................................结果106摘要109参考书目111介绍在过去的十年中，植物建模在计算机图形学和相关领域变得流行它不仅是图形工业中虚拟自然景物的主要元素，也为科学家研究复杂的植物三维结构提供了新的机遇。了解植物的几何形状是研究植物与环境（光、病虫害传播等）相互作用的关键因素这些关键优势促使研究人员设计数字化方法来生成准确的虚拟植物模型。然而，大多数实际测量方法是手工的，并且非常耗时。这是植物发育定量模型重建中的一个重要问题随着激光扫描的最新进展，直接捕获植物的3D数据已经成为可能。这样的捕获产生表示植物的表面积的点云原始输出是相机在植物表面看到的点的空间坐标（x，y，z）的集合。因此，大多数应用需要从捕获的点云重建完整的植物几何形状虽然在大多数应用中是成功的，例如用于捕获考古文物或城市几何形状，但由于植物的多尺度性质，该技术在应用于植物时不能实现可接受的事实上，植物看起来是一组不连续的不同大小的表面，模糊地分布在一个体积中，其中发生多个遮挡。最小的分支通常会以非常低的点密度被捕获，这增加了模糊性，并使它们可能被错误地连接到结构的其他部分因此，标准方法不能用于植物采集。本论文的目标是首先研究一种获取现有植物几何形状同时也为定量评价所生成重建图像的有效性和准确性提供了工具在这项工作的背景下，一个软件工作流程重建三维植物结构和评估它已经开发出来。这些工具使人们能够忠实地重建激光扫描观察到的真实植物结构。此外，他们允许验证重建模型对专家重建。文档组织本文的结构安排如下：• 第1章介绍了不同的技术开发的数字化形状。重点介绍了激光技术。由于这些工具产生对测量对象的表面进行采样的点，因此已经开发了许多方法来处理这些点并重新生成对象的虚拟模型因此，本章将介绍和讨论重建的经典方法• 第2介绍了文献中使用的不同植物表示法一种基于沟通水平的代表性分类，复杂性，是作为一个指导画布的文献综述。特别是，我们提出了多尺度树图，用于表示在不同的尺度，我们在我们的重建和评估过程中使用的植物的结构• 第三章介绍了植物虚拟模型生成的不同技术。它们可以大致分为手动测量技术、基于草图、基于图像或基于点。• 第4介绍了我们从激光扫描仪数据重建管道我们提出了一种局部自适应的方法，结合了收缩阶段和局部点跟踪算法，从激光数据中检索形状的骨架的数据的精度的• 第5章描述了我们的方法来定量评估重建的模型。我们设计了一种方法来比较重建的树模型与专家重建。考虑了结构和几何标准。这样的方法使得有可能评估我们的重建算法的准确性。2内容第一章测量和表示形状为点近年来，基于点的几何体作为一种替代的表面表示方法，无论是用于高效渲染还是用于高度复杂的3D模型的灵活几何体处理，都受到了越来越多的关注[KobbeltBotsch 2004]。点曲面由3D空间中的点的集合组成，每个点代表一个小的表面区域。类似的数据集是在过去获得的各种方法，如距离成像，声纳和摄影测量系统。随着技术速度的提高在大多数情况下，3D采集设备产生对象的离散样本，即，点样本的集合。根据采集技术的不同，每个点样本还带有许多属性，例如颜色或材质特性。作用于基于点的表面的建模算法通常是非常有效的，这是由于每个点样本都存储几何形状（例如，位置）以及外观信息（例如，颜色）。因此，大多数建模操作可以通过仅局部改变点样本来执行[Adams 2006]。在本章中，我们将展示点获取和表示在处理3D对象时是有益的我们在1.1节中介绍了主要的数据采集技术。在第1.2节中，我们更精确地介绍了激光扫描技术，可以创建点云的几何样本上的物体的表面在1.3节中，我们描述了基本的点处理算法。第二节一点四最后，我们总结了1.5节中从点集进行一般重构的各种工作。1.1测量技术重建真实世界物体的第一步是进行数据采集，这直接影响模型的准确性。数据采集系统受物理因素的限制，只能从物体表面采集数据。有许多不同的方法来捕捉物体的表面。这些方法可分为两种：触觉接触式和非接触式（如图1.1所示）。在非接触方法中，使用光、声或磁场，而对于接触方法，通过使用机械探针直接接触表面1.1.测量技术5图1.1：数据捕获方法。[Várady et al. 一九九七年]1.1.1触觉接触方法触觉方法作为一种接触方法，通过机械探针接触物体表面来确定物体的空间坐标，并生成表面上数据点的三维坐标有许多不同的机器人设备用于检测物体，但对于凹面不是很有效可能最流行的方法是使用坐标测量机（CMM）。这些机器提供了准确的测量结果，并被广泛接受为工具，从对象捕捉大多数坐标测量机类似于配备触摸探头而不是机器人夹具的机器人[Spyridi Requicha 1990]。这些机器可以编程为沿着表面的路径并以高精度捕获已经提出了几项使用CMM的工作：Sahoo和Menq [Sahoo Menq 1991]使用CMM系统来感测复杂的雕塑表面，Lin等人[Linet al. 2005]使用这种方法来重建人工连接的CAD模型，以满足他们的定制需求等。然而，坐标测量机不适合测量大量的点，因为这些机器的主要限制是数据采集速度慢它们必须与每个采样点的零件表面进行物理接触。如果零件是由不能触摸的软材料制成的，它们也可以使零件表面变形[Wolf等人， 2000年，Lee等人2001年]。此外，这些机器非常昂贵和复杂。因此，考虑采用非接触方法进行数据采集。1.1.2非接触方法与接触式设备相比，非接触式方法可以在短时间内获取大量数据，成本低，精度适中，并且在存在的情况下具有鲁棒性4第1章测量并将形状表示为点环境光源的情况[Park Chang 2009]。一个与使用非接触式测量方法密切相关的早期例子是所谓的Jacob Bar，见图1.2。这种测量是基于截距定理，它涉及三角形线段之间的比率 这种仪器可以确定与物体的距离（如果其横向尺寸已知）或其尺寸（如果距离已知）[Schwenke et al.2002年]。图1.2：用于确定距离和横向尺寸的雅各布杆（14世纪）[Schwenke et al.2002年]。后来，计算能力的快速增长，光电二极管和CCD传感器（摄像机），可以将光强度转换为电信号已经开发出来，以执行数据采集。 对于光学方法，Javis [Jarvis1983]和Schwenke et al. [Schwenke et al. 2002]介绍了用于数据采集的不同方法。可归纳如下。这里讨论了五种重要的光学方法：三角测量、测距、干涉测量、结构照明和图像分析。三角测量使用物体的位置和光源与探测器之间的角度来推断位置。光源装置，例如，投影仪、激光扫描仪在物体上发射光或激光点，并利用传感器来寻找出现在传感器中的这种点物体表面上的一点可以由三角关系确定。检测器上的点的位置是传感器和物体表面之间的距离的函数。在图1.3中，假设所有的几何参数都是已知的，从基线到物体的距离可以计算如下：d=b sinαsinβsin（α+β）（一、一）三角剖分法已在多个领域得到应用例如，6第1章测量并将形状表示为点用于支持制造业中的计算机辅助质量控制过程[Wolf et al. 2000年]。三角测量的主要局限性是表面的光学特性，例如，非常光滑的表面由于不充分的散射和反射光而无法测量。图1.3：三角测量原理。测距方法不同于三角测量方法，因为光束探测器通常感测返回光，并以其信号的时间和相移来表征它在这一系列方法中，可以找到3D激光扫描仪，用于收集有关物体形状和可能外观（即颜色）的数据到物体表面的距离的估计在第1.2.1节中描述。该系统有助于实现高质量的数据和快速扫描。此外，它们能够长距离运行因此，这些扫描仪适合测量大型物体。测距方法的缺点它只能在干燥的天气条件下使用：雨滴或雾会导致不需要的点和激光束的折射。在第1.2节中，将给出关于3D激光扫描仪的干涉测量法[Macgovern Wyant 1971]方法使用干涉图案根据波长测量距离大多数干涉仪使用光或其它形式电磁波。这可以实现准确的结果，因为可见光具有数百纳米量级的波长，而大多数光学方法都在厘米到米的范围内[Várady等人。 1997年]。原则上，来自光源的光束将被分成两束。这些光束中的每一束，一束探测物体的光束和一束参考光束，将沿着不同的路径行进，直到它们在到达探测器之前重新组合，见图1.4。每个光束传播距离的差异产生了初始波之间的干涉图样路径长度的物理变化在两个光束之间产生相位差，该相位差可用于估计距离。如今，干涉测量是天文学、纤维光学和生物分子相互作用领域的重要研究技术。然而，用于干涉测量的装置相当复杂和昂贵。此外，所研究对象的尺寸受到客观视场的大小的限制，并且较大的变形导致形成不可区分的干涉结构。1.1.测量技术7图1.4：两束相干光束在传播不同距离后重新组合，得到理想的干涉波长测定。结构化照明涉及将光图案（通常是网格或水平条）投射到物体上，并使用相机捕获表面反射的结果图案的图像，见图1.5。使用LCD投影仪或扫描激光器将光投射到物体上摄像机观察图案的变形，并使用算法来计算图案中每个点的距离，类似于三角测量方法。这种方法的优点是它的速度。不是一次扫描一个点，而是可以一次扫描多个点或整个视场，但确定数据位置的分析可能相当复杂。此外，许多工作必须通过熟练用户的直觉手动完成Will和Pennington [Will Pennington1972]使用投影到物体表面的网格来确定点的位置。最近，Park和Chang [ParkChang 2009]提出了一种从多次扫描中识别缺失区域的程序这种方法试图定位额外的扫描方向来填充缺失区域。立体图像分析使用从水平移位的两个类似相机获得的两个图像来确定场景中对象的深度[Goshtasby 1989]。如果在两个相机的两个图像中可获得相同的物点，则物点被约束为沿着空间中的两条已知射线，并且因此必须位于它们的交点处（例如，见图1.6中的点P1和P2）。为了使用一对图像确定物体上点的三维位置，如果两个视图的相机的相对位置和方向已知，则可以通过简单的三角测量来计算这些位置，如图1.6该方法最重要和最耗时的任务是两个图像的配准，即对应点的识别。对于声学测量系统，声纳用于确定源和目标之间的距离该距离是在已知声速的情况下确定的，类似于从光速的时间估计距离（参见等式1.2）。这项技术被用来寻找和识别水中的物体例如，Giannitrapani8第1章测量并将形状表示为点图1.5：多条条纹中的一条所示的三角测量原理图1.6：立体三角测量的位置测量
