从单张树木图像快速构建真实感树木模型的方法

摘要

本发明公开了一种从单张树木图像快速构建真实感树木模型的方法，属于计算机图形学领域，用于解决从单张真实树木图像中快速重建出树木的三维几何模型和二维纹理贴图这一问题。该方法包括以下步骤：首先在树木图像上标记出树木大致树冠轮廓和主树干中心线；其次采用主动轮廓方法求解精确树冠轮廓、主树干轮廓和树木前景图像；再次使用粒子仿真方法计算树冠轮廓内部的二维树枝形状；然后将树枝形状从二维平面变换到三维空间；接着扫描三维树枝形状构建树木三维几何模型；最后合成枝干纹理贴图和树叶纹理贴图。本发明提供的树木建模方法建模操作简单、建模速度快，在景观设计、动漫创作、游戏开发、影视制作等领域具有较高的实用价值。

说明书

技术领域

本发明专利涉及计算机图形学领域，特别是涉及一种从单张树木图像快速 构建真实感树木模型的方法。

背景技术

树木能有效增强虚拟场景的真实感维度。然而，由于自然界的树木种类繁 多、形态万千、结构复杂，构建真实感的三维树木模型具有很大困难。目前， 针对树木的建模方法主要包括四类。

第一类是基于交互的建模方法。用户使用通用的三维建模软件完全手动的 构建树木的每个细节，例如使用Autodesk公司的3DS MAX软件。该建模方法的 控制精度较高，但建模工作量较大。有一些建模方法通过提供内置的树木模型， 例如IDV公司的SpeedTree软件，用户通过交互修改已有树木模型的参数得到 期望的树木模型。该建模方法速度得到了很大提升，但要求用户对建模参数具 有一定的理解和掌握，并且构建与真实树木图像相似的树木模型比较困难。

第二类是基于规则的建模方法。由于植物生长符合一定生物学规则和模式， 因此有许多研究者提出通过设计和使用规则来模拟树木的生长，并据此构建其 三维模型，参见Ijiri，T.，Owada，S.，Okabe，M.，Igarashi，T.2005.Floral  diagrams and inflorescences：interactive flower modeling using botanical  structural constraints.ACM Transactions on Graphics 24，3，720-726.。 虽然这类方法可以得到较为自然和真实的树木模型，但用户在设计和使用规则 以及指定规则定参数时，需要比专业的背景和经验，在构建比较复杂的树木模 型时，则需要使用大量规则。

第三类是基于草图的建模方法。这类方法首先让用户勾勒出树木树冠、枝 干、树叶等形状的草图，然后对草图进行分析、理解和推导，生成树木模型， 参见Okabe，M.，Owada，S.，Igarashi，T.2005.Interactive design of  botanical trees using freehand sketches and example based editing. Computer Graphics Forum 24，3，487-496.。这类方法所需要的建模交互量 一般较大，并且对于普通用户，一般难以绘制出比较合理的树木草图。

第四类是基于图像的建模方法。一些研究者通过沿树木周围拍摄多张图像， 然后利用计算机视觉从运动恢复结构等算法，计算得到树木表面的三维点云， 并根据这些点云进一步计算树木枝干和树叶的三维网格模型，参见Quan，L.， Tan，P.，Zeng，G.，Yuan，L.，Wang，J.，Kang，S.B.2006.Image-based plant  modeling.SIGGRAPH 2006，599-604.和Tan，P.，Zeng，G.，Wang，J.，Kang， S.B.，Quan，L.2007.Image-based tree modeling.SIGGRAPH 2007，87-93.。 这类建模方法构建的树木模型的细节比较真实，并且和真实树木具有较大相似 度，但构建时间比较长、用户交互工作量也比较大。

上述树木建模方法，都存在建模时间长、建模交互量大、建模操作复杂等 缺点。随着人们对虚拟现实需求的增长和虚拟现实应用的增多，对其开发周期 的要求也在不断提高。因此研发建模成本低、建模交互少、建模速度快的快速 树木建模技术十分必要。

发明内容

本发明克服了现有技术中的缺点，提供了一种从单张树木图像快速构建真 实感树木模型的方法，结合主动轮廓方法、粒子仿真方法、纹理合成方法，可 从单张树木图像中快速重建出树木的三维几何模型和二维纹理贴图，降低了树 木的模型建模成本、建模交互工作量和建模时间，可应用于景观设计、园林设 计、动漫创作、游戏开发、影视制作等领域。

本发明的技术方案包括以下六个步骤：

1)在树木图像上标记树木大致树冠轮廓和主树干中心线

拍摄一张树木图像，在树木图像上用多边形标记出树木大致树冠轮廓，用 直线段标记出树木大致主树干中心线；

2)求解精确树冠轮廓、主树干轮廓和树木前景图像

采用主动轮廓方法，分别从树木大致树冠轮廓和主树干轮廓出发，通过局 部最小化由连续能量、曲率能量和梯度能量加权求和组成的能量函数，求解精 确的树冠轮廓和主树干轮廓，并提取出精确的树木前景图像；

3)计算树冠轮廓内部的二维树枝形状

对精确树冠轮廓顶点进行重采样和平滑处理，然后在树冠轮廓顶点等距放 置粒子，根据主树干引力、树冠轮廓排斥力和粒子间相互引力，采用粒子仿真 方法不断更新粒子位置，直到所有粒子都死亡，合并粒子运动轨迹，得到树冠 轮廓内部的二维树枝形状；

4)将树枝形状从二维平面变换到三维空间

然后根据最大分叉原则，采用贪心算法，从下至上逐段处理每段二维树枝 形状，根据二维树枝形状在树木图像平面上的位置以及已经处理的二维树枝形 状的数量，将树枝形状从二维平面上旋转到三维空间中，处理完成所有二维树 枝形状后，得到树木的三维树枝形状；

5)扫描三维树枝形状构建树木的三维几何模型

从三维树枝形状的根节点出发，从下至上扫描每段三维树枝形状，逐段生 成枝干表面的三维几何模型，根据运动轨迹所包含粒子的数量计算树枝形状的 半径，在树枝形状内部，采用结合下一段树枝形状的方法计算几何模型顶点采 样点平面，在树枝形状分叉处，采用结合分叉处两段树枝形状的方法计算几何 模型顶点采样点平面；

6)根据树木前景图像合成树木二维纹理贴图

根据主树干轮廓内的树木前景图像像素，采用基于样例的逐像素纹理合成 方法生成枝干纹理贴图，并根据树冠轮廓内的树木前景图像像素，采用高斯模 型分析方法合成树叶纹理贴图，得到具有真实感的树木二维纹理贴图。

本发明与背景技术相比，具有的有益的效果是：

本发明结合主动轮廓、粒子仿真、纹理合成等技术，能根据单张树木图像 快速重建出与其相似的具有真实感的树木三维几何模型和二维纹理贴图，有效 地克服了现有方法建模成本高、建模交互量大、建模时间长的缺点，可满足景 观设计、动漫创作、电子游戏等领域中快速构建感树木模型的需求。

附图说明

图1是本发明方法的技术方案流程图。

图2是基于粒子仿真的二维树枝形状构建流程图。

具体实施方式

在实施本发明一种从单张树木图像快速构建真实感树木模型的方法时，具 体步骤如下：

第一步，拍摄一张树木图像并标记出树木的大致树冠轮廓和主树干中心线。

使用普通数码相机拍摄一张树木图像，拍摄时数码相机需正对树木，并完 整地拍摄到树木的树冠和主树干图像，树木图像分辨率应不低于1024个像素宽 和1024个像素高。在树木图像上标记出树木的大致树冠轮廓和主树干中心线。 树冠轮廓用多边形表示，标记为C＝{c₀，c₁，...，c_n-1}，其中c_i表示多边形的顶点， 其值为树木图像中的像素位置，n表示树冠轮廓顶点的数量。主树干用直线段表 示，标记为T＝{t₀，t₁，...，t_m-1}，其中t_i表示直线段上的顶点，其值也为树木图像 中的像素位置，m表示主树干顶点的数量。

第二步，求解精确的树冠轮廓、主树干轮廓和树木前景图像。

采用主动轮廓方法求解精确的树冠轮廓。树冠轮廓顶点初始位置设置为第 一步中标记的位置，通过局部最小化一个能量函数对树冠轮廓顶点位置不断更 新，直到得到精确的树冠轮廓。在每次迭代时，首先计算每个顶点c_i处3x3邻 域内8个相邻顶点处的能量函数值，然后将该顶点移动到具有最小能量函数值 的相邻顶点处。能量函数E_i由该顶点处的连续能量Ec、曲率能量Ev和梯度能量 Eg加权求和得到，计算公式如下：

E_i＝αEc(c_i)+βEv(c_i)+γEg(c_i)

其中α、β、γ为加权因子，分别取1.2、1.0、1.2。

Ec(c_i)为顶点c_i处的连续能量，计算公式如下：

Ec(c_i)＝d²+|cn_k-c′_i|²

其中d为当前所有顶点和在上一次迭代前所有对应顶点的距离的平均值， cn_k为顶点c_i处3x3邻域内的相邻顶点，k＝{0，1，...，7}，c′_i为顶点c_i在上一次迭代 前的位置，|cn_k-c′_i|为顶点cn_k到顶点c′_i之间的距离。

Ev(c_i)为顶点c_i处的曲率能量，计算公式如下：

Ev(c_i)＝|c′_k-1-2cn_k+c′_k+1|²

其中c′_k-1和c′_k+1分别是在上一次迭代前，顶点cn_k沿轮廓顶点列表的前一个 顶点和后一个顶点。

Eg(c_i)为顶点c_i处的梯度能量，计算公式如下：

$\mathrm{Eg}\left(c_i\right)=\frac{g_{\min }-g}{g_{\max }-g_{\min }}$

其中g为顶点c_i处图像梯度的幅值，g_min和g_max分别为顶点c_i处3x3邻域内 相邻顶点的最大的和最小的图像梯度的幅值。

从树冠轮廓顶点的初始位置出发，迭代20次以上可得到精确的树冠轮廓。 在计算精确的主树干轮廓时，先将主树干直线段上位于起始顶点和终止顶点之 间的顶点复制一次，并插入到终止顶点之后，得到主树干轮廓的初始位置，然 后从该初始位置出发，同样采用主动轮廓方法求得精确的主树干轮廓。精确树 冠轮廓和主树干轮廓内的图像像素共同构成树木前景图像。

第三步，计算支撑树冠轮廓内部的二维树枝形状。

首先对第二步求得的精确树冠轮廓顶点进行重采样和平滑处理。重采样时， 遍历一遍树冠轮廓顶点列表，并计算相邻两个顶点之间的距离，如果其距离大 于10个像素，则从起始顶点出发，沿终止顶点方向每隔5个像素增加一个新的 轮廓顶点，如果其距离小于5个像素，则删除终止顶点。对树冠轮廓进行平滑 处理时，也遍历一边树冠轮廓顶点列表，将每个顶点位置更新为其前后各n个 顶点位置的平均值，n取值为3，计算公式如下：

$c_1=\frac{1}{2n+1}\underset{k=i-n}{\overset{k=i+n}{\Sigma }}{c}_k$

重采样和平滑处理完所有树冠轮廓顶点后，得到平滑的树冠轮廓，标记为 C^s。使用粒子仿真方法求解树冠轮廓内部的二维树枝形状。先根据树木外形规 模确定粒子总数，对于小型树木，粒子总数确定为500-1500个，对于大型树木， 粒子总数确定为1500-3000个。再沿树冠轮廓C^s等间距地放置粒子，树冠轮廓 顶点的坐标作为粒子的初始位置。开始对粒子进行仿真，每次仿真流程执行粒 子位置更新、相邻粒子合并、粒子死亡判断三个操作，直到所有粒子都死亡则 仿真结束。当仿真结束时，将粒子的运动轨迹合并，并且以二叉树数据结构存 储，得到树冠轮廓内部的二维树枝形状，二维树枝形状构建流程参见图2。

粒子位置更新方法参照牛顿第二定律，根据粒子所受合外力和粒子质量计 算粒子的加速度，并由粒子的加速度更新粒子的速度和位移，计算公式如下：

$a=\frac{F}{m}$

v＝v₀+at

$s=v_{0}t+\frac{1}{2}{\mathrm{at}}^2$

其中F表示粒子所受合外力，m表示粒子质量，a表示粒子的加速度，v₀表示粒子的初始速度，v表示粒子的速度，t表示仿真步长。所有粒子的初始速 度和初始加速度均设定为0，初始质量设定为0.1，仿真步长设定为0.01。粒子 所受合外力由主树干引力、树冠轮廓排斥力和粒子间相互引力加权求和得到， 计算公式如下：

F＝αF_t+βF_c+γF_a

其中α、β、γ为加权系数，分别取0.8、0.4、0.1；F_t为主树干引力，引导 粒子向主树干运动，通过计算从当前粒子位置到主树干顶部位置的向量得到；F_c为树冠轮廓排斥力，引导粒子在树冠轮廓内运动，通过计算从最近的树冠轮廓 顶点位置到当前粒子位置的向量得到；F_a为粒子间的相互引力，引导粒子朝相 邻粒子运动和合并，令m_i为当前粒子质量，m_k为距离其最近的粒子质量，d_ik为 两个粒子位置之间的距离，其计算公式如下：

$F_a=\frac{m_i{m}_k}{d_{\mathrm{ik}}^2}$

执行相邻粒子合并时，对于每个粒子P_i，找到距离其最近的粒子P_n，如果 粒子P_i与P_n之间的距离小于2个像素，则将粒子P_n合并到P_i中，并将粒子P_i的 质量更新为粒子P_i与P_n的质量之和，然后设置粒子P_n为死亡状态。执行粒子死 亡判断时，计算粒子当前位置到主树干顶部位置的距离，如果该距离小于2个 像素，则粒子死亡。

第四步，将树枝形状从二维平面变换到三维空间。

根据最大分叉原则，采用贪心算法，将树枝形状从二维平面变换到三维空 间，得到三维树枝形状。首先定义树木的三维空间坐标系，主树干根部为坐标 系原点，朝左为正X轴，朝上为正Y轴，朝前为正Z轴。XZ平面为地平面， 标记为P_G。XY平面为二维树枝形状所在平面，也是树木图像所在平面，标记为 P_T。此时，二维树枝形状在地平面上的投影全部位于X轴上。

首先将平面P_T沿与正X轴夹角的大小划分为I_A(45度～135度)、I_B(135 度～225度)、I_C(225度～315度)、I_D(315度～45度)四个区间，将地平面 P_G也沿与正X轴夹角的大小划分成G_A、G_B、G_C、G_D四个区间，分别与I_A、 I_B、I_C、I_D一一对应。从主树干根部向上遍历每一段二维树枝形状，每段二维 树枝形状的起始顶点V_B和终止顶点V_E之确定一条直线，根据该直线与X轴夹 角的小大，判断其在平面P_T上所属的区间，标记为I_K，计算对应的三维树枝形 状在平面P_G上所属的区间，标记为G_K，计算公式如下：

其中N(I_K)，I_K＝{I_A，I_B，I_C，I_D}表示区间I_K内分配的二维树枝形状数量。

然后计算向量V_B V_E和Z轴的叉积，标记为R，固定起始顶点V_B不动，将 二维树枝形状沿R轴旋转，直到V_B V_E在地平面P_G上的投影位于G_K区间边界和 已分配三维树枝形状投影之间最大夹角的角平分线，得到三维树枝形状。

第五步，扫描三维树枝形状构建树木的三维几何模型。

从第四步中得到的三维树枝形状的根节点出发，由下至上进行扫描，逐段 生成枝干表面的三维几何模型。粒子仿真时，粒子采用两两合并的方式并以二 叉树数据结构保存树枝形状，每个二叉树节点为一段树枝形状，其中包含以直 线段方式存储的粒子的运动轨迹、粒子合并时生成的二叉树子节点和父节点的 对象指针、以及树枝半径。

树枝半径r计算公式如下：

$r=\omega \sqrt{n}$

其中n为经过该段树枝的粒子总数，ω为树枝半径控制系数，设置为1.2。 在扫描三维树枝形状时，按以下两种方式生成枝干表面的三维几何模型：

(1)当扫描树枝形状内部时，令当前扫描的直线段为L_i，其起始顶点和终 止顶点分别为V_i和V_i+1，下一次扫描直线段为L_i+1，两个直线段的方向向量分别 为N_i和N_i+1，根据法向量(N_i+N_i+1)和顶点V_i+1计算得到平面P_i，在平面P_i上 以V_i+1为圆心、R_i+1为半径的圆周上均匀间隔采样16个顶点，将这些顶点分别 与上一次扫描采样得到的16个顶点一一连接，得到该段树枝的三维几何模型。 对于三维树枝形状的根节点，直接在地平面上进行采样。

(2)当扫描树枝形状分叉处时，令分叉处的直线段分别为L_i、L_m和L_n， 其中L_m和L_n所属树枝为L_i所属树枝的子节点，三个直线段的方向向量分别为 N_i、N_m和N_n，根据向量N_i和L_i的起始顶点V_i计算平面P_i，根据向量N_m和L_m的终止顶点V_m+1计算平面P_m，根据向量N_n和L_n的终止顶点V_n+1计算平面P_n。 然后使用方式(1)中的采样方法分别对平面P_i、P_m和P_n进行顶点采样，然后将 P_m的16个采样顶点与P_i的16个采样顶点一一连接，同样也将P_n的16个采样顶 点与P_i的16个采样顶点一一连接，得到树枝形状分叉处的三维几何模型。

第六步，根据树木前景图像合成树木二维纹理贴图。

树木二维纹理贴图由枝干纹理贴图和树叶纹理贴图组成。首先根据第二步 中得到的精确主树干轮廓内的树木前景像素，采用基于样例的逐像素纹理合成 方法，构建枝干纹理贴图。在主树干轮廓内，沿水平方向以8个像素为一组， 将树木前景像素组拷贝到分辨率为512x512大小的枝干纹理贴图的像素区域中， 直到铺满第一行和第二行像素区域。按从上到下、从左到右的扫描线顺序，从 主树干轮廓内的树木前景像素中，选择最佳像素填充到枝干纹理贴图的空白像 素区域。最佳像素定义为与待填充像素邻域最相似的像素点，通过搜索主树干 轮廓内的树木前景像素区域，找到一个像素点，其3x3邻域和待填充像素3x3 邻域的像素颜色差的绝对值之和最小。

再根据树冠轮廓内的树木前景像素颜色合成树叶纹理贴图。构建10个三通 道颜色的高斯模型，高斯模型的初始均值和初始方差均设置为0。按扫描线顺序 扫描树冠轮廓内的树木前景像素，判断当前像素颜色是否命中某个高斯模型， 即其颜色是否位于该高斯模型均值±2.5倍方差范围内，若命中则更新该高斯模 型的计数器。取命中次数最多的高斯模型作为树叶纹理贴图的颜色。最后将树 叶纹理贴图以布告板方式放置到树枝处，以一个50x50x50分辨率的三维网格划 分树木三维几何模型空间，并扫描每段树枝，将其所在的三维网格单元投影到 树木图像平面，计算投影区域内像素的平均灰度值。如果平均灰度值小于128， 则不放置树叶纹理贴图布告板，否则就放置树叶纹理贴图布告板。结合第五步 构建的树木三维几何模型，得到最终的三维真实感树木模型。