一种采用手绘草图的三维人体多姿态建模方法

摘要

本发明提出了采用手绘草图的三维人体多姿态建模方法，包括：显式绘制人体特征草图，在给定的三维人体姿态模型下，将观察视角和人体姿态调整为与人体草图一致，并根据人体姿态模型网格点与人体关节点之间的位置关系对该人体模型加权；在该观察视角和人体姿态下，对人体姿态模型进行投影并提取轮廓线、暗示性轮廓线、谷线和脊线等特征投影线集合，将人体草图笔画线与特征投影线组合进行匹配，并根据草图笔画线与特征投影线组合的几何关系构建隐马尔科夫模型，将草图笔画点与三维模型网格点对应并计算对应点的位移参数；在对应三维模型网格点位移参数的约束下，通过均值坐标编码形变算法对人体网格模型进行形变，得到最终的三维人体网格模型。

说明书

技术领域

本发明涉及一种三维图像数据处理领域，特别是一种采用手绘草图的三维人体多姿态建模方法。

背景技术

三维人物建模技术是三维建模研究的重要问题之一，在游戏、动画及电影等领域有着广泛的应用,寻找一种简单有效地构建三维人体网格模型的方法，成为计算机图形学领域的重要课题。

目前的虚拟人物构建方法大多为真实感方法，主要分为创建，重构，插值三个类别，典型方法如文献1 Wilhelms J,Van Gelder A.Anatomically based modeling,In:Proceedings of SIGGRAPH’97,ACM SIGGRAPH;1997.p.173-80，该方法主要根据人体生理结构创建层次化物理模型，并通过模拟各层次物理性质驱动其运动，达到模拟仿真人体运动的目的。该类方法能够生成极为逼真的人体模型，但由于交互方式复杂，用户需要熟悉三维操作环境并具有专业的建模技能；同时，方法所需的人体生理学数据往往需要专业的数据采集设备，因此难以被普通用户所使用。为此，有研究者提出了非真实感人体建模方法，该类方法主要面向概念设计阶段，通过降低人体模型的真实程度以增强建模方法的交互性；其中，由于草绘交互方式符合传统的人体设计模式，能够较好地支持用户表达创作意图，因此近年来成为人体建模研究的热点之一。

根据特征映射机制及模型生成方法的不同，现有的草绘人体建模方法主要分为直接构造、参数化模板构造及模型形变三种类型。直接构造方法典型如文献2 Igarashi T,Matsuoka S,Tanaka H.Teddy:a sketching interface for 3D freeform design.In:Proceedingsof SIGGRAPH‘99,ACM SIGGRAPH;1999.p.409-16提出的基于草绘轮廓的自由形体模型生成方法，用户分别绘制人体各部分轮廓线并膨胀生成相应部分的网格模型，最后混合各部分网格得到完整人体模型。由于网格膨胀机制所能表现的三维形状极为有限，因此该方法所生成的肢体模型难以表现人体细节特征。参数化模板构造方法典型如文献3 Chen Mao,Sheng Feng Qin,David Wright,ChenMao,Sheng Feng Qin andDavidWright,Asketch-based approachto human body modelling,Computers & Graphics(2009)提出的基于截面模板的草绘人体建模方法，用户分层次绘制人体骨架线及外轮廓线，并通过解析骨架特征及外轮廓特征得到模板形变参数直接构造得到结果模型。但是，构建参数化人体模板需要用户进行大量交互，且结果模型的表现能力取决于人体模板的复杂性，一般只能表现手腿躯干部分的大致外形，而难以表现关节肌肉等复杂形状特征。模型形变方法典型如文献4 Vladislav Kraevoy,Alla Sheffer,and Michiel vande Panne.Contourbased Modeling Using Deformable 3D Templates.Tech Report,2007.提出的基于均值编码坐标的形变方法，该方法允许用户绘制人体模型在某一确定视角下的轮廓线，通过HMM方法将投影轮廓线与三维模型网格点进行对应，最后通过均值编码坐标方法对该人体模型进行形变得到结果模型。但是该方法只能够绘制人体外部轮廓线，且由于所匹配的网格点仅依赖于观察视角，因此无法保证笔画匹配过程的合理性；同时，由于未考虑人体模型的结构特性，因此模型形变时无法保证满足人体模型的局部细节特征。

概括起来，手绘草图是三维人体网格模型创建的有效方式，但已有基于单幅草图的三维人体网格模型创建方法对于用户的绘制内容和所能表现的人体特征均有很大的限制，如：直接构造方法和模型形变方法仅允许用户绘制人体外轮廓，且所匹配的三维特征点仅依赖于观察视角，因此无法保证特征映射过程的合理性，参数化模板构造方法虽然允许用户绘制骨架线以体现人体模型的姿态，但是仍然不允许用户绘制人体特征笔画；直接构造方法生成的人体为膨胀体模型，因此难以表现人体细节特征，参数化模板构造方法所生成的人体模型，其表现能力取决于人体模板的复杂性，一般只能表现手腿躯干部分的大致外形，而难以表现关节肌肉等复杂形状特征，模型形变方法虽然能够保持网格模型的几何特征，但由于没有考虑人体结构特征而无法在形变幅度较大的情况下满足人体生理学约束。显然，现有的单视图草绘人体建模方法难以满足用户较自由地进行形体设计的需要，如何捕捉用户绘制过程中体现的人体特征，并将这些特征合理地映射到三维模型网格特征点，同时如何在模型形变的过程中满足人体结构特征的约束也是手绘草图交互创建三维人体网格模型面临的重要课题。

发明内容

发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种采用手绘草图的三维人体多姿态建模方法。

为了解决上述技术问题，本发明公开了一种采用手绘草图的三维人体多姿态建模方法，包括以下步骤：

步骤一，模型预处理：用户绘制人体特征草图S，并调整给定的三维人体姿态模型M_o的观察视角和人体姿态，使三维人体姿态模型M_o的观察视角和人体姿态与人体特征草图S一致；根据用户在三维人体姿态模型M_o上标定的人体关节点位置，并对三维模型网格点进行加权；

步骤二，笔画匹配：在步骤一中调整后的观察视角和人体姿态下，对三维人体姿态模型M_o进行投影得到特征投影线集合S_F，特征投影线集合S_F包括一组特征投影线；

对每一条草图笔画线s_i计算对应的候选特征投影线集合S_FC，并在特征投影线集合S_FC中，遍历查找所有可能与草图笔画线s_i匹配的特征投影线组合，计算各特征投影线组合的组合代价集合C_Si，并得到对应的特征投影线组合集合S_FSi；计算草图笔画线s_i与特征投影线组合集合S_FSi中各特征投影线组合的相似度，选择相似度最高的特征投影线组合S_Si与草图笔画线s_i进行匹配，1≤i≤n；

对所述匹配的草图笔画线s_i和特征投影线组合S_Si建立隐马尔科夫模型，将草图笔画线s_i的草图笔画点与特征投影线组合S_Si中的特征投影线点进行匹配，并计算特征投影线点所对应的三维模型网格点在绘制平面的位移参数P_DSi，所有特征投影线点对应的三维模型网格点位移参数构成三维人体姿态模型M_o的特征点位移集合P_D；

步骤三，在三维人体姿态模型M_o的特征点位移集合P_D的约束下，对三维人体姿态模型M_o进行形变，得到最终的三维人体网格模型，从而实现三维人体多姿态建模。

本发明中，优选地，步骤一中，包括以下步骤：

用户显式绘制人体特征草图S={s₁,s₂,...,s_n}，对人体特征草图S中的草图笔画线s_i进行笔画分割，将所有草图笔画线识别为直线和椭圆两类图元；

所述三维人体姿态模型记为M_o(δ,α₀)，并以三维人体网格模型的形式显示给用户；用户根据人体特征草图S，调整三维人体姿态模型的观察视角，使该三维人体姿态模型M_o与人体特征草图S的投影视角一致，在三维人体姿态模型M_o(δ,α₀)上标定人体关节点位置；通过移动各人体关节点的位置调整人体姿态参数δ和根关节点坐标α，使移动后的三维人体姿态模型与人体特征草图S所绘制的人体姿态一致，移动后的人体姿态参数为δ′，根关节点坐标为α₀′，将所得到的三维人体姿态模型M_o(δ′,α₀′)作为模型形变的模板；

在三维人体姿态模型M_o(δ′,α₀′)上标记人体关节点位置，并对每个三维模型网格点v_a计算其到最近人体关节点的距离D_i，根据此距离D_i对三维模型网格点v_a进行加权。

本发明中，优选地，步骤二中，对三维人体姿态模型M_o(δ′,α₀′)计算以下几何特征并投影：

计算各三维人体姿态模型M_o(δ′,α₀′)中三维模型网格点的法向量与视向量的内积，并将内积小于阈值的三维模型网格点作为轮廓特征点，该阈值一般设为0.1-0.2(候选特征点的数量随着阈值的增大而增加)；计算各三维模型网格点处的曲率半径K_r以及K_r在w方向的方向导数D_w(K_r)，将K_r=0且D_w(K_r)>0的网格点作为暗示性轮廓点；计算三维人体网格模型M_o(δ′,α₀′)主曲率的局部极值点；

将上述轮廓特征点、暗示性轮廓点、以及主曲率局部极值点投影到绘制平面生成对应的投影点集，采用基于深度连续性的轮廓跟踪算法将上述投影点集连接为特征投影线，并根据各草图笔画线s_i的闭包矩形覆盖范围，在所述特征投影线集合中寻找各草图笔画线s_i对应的候选特征投影线集合S_FC；

在候选匹配特征投影线集合S_FC中，计算两两特征投影线之间的距离ε；

在候选匹配特征投影线集合S_FC中，遍历查找所有特征投影线组合集合S_FSi，并计算特征投影线组合集合S_FSi中各种组合形式的组合代价集合C_Si，组合代价集合C_Si中包括一组特征投影线组合代价；

计算草图笔画线s_i与特征投影线组合集合S_FSi中每个特征投影线组合S_Fj的形状相似度Sim_Si-SFj，1≤j≤n，根据形状相似度Sim_Si-SFj和组合代价集合C_Si中的对应特征投影线组合代价C_SFj，计算草图笔画线s_i与特征投影线组合S_Fj的相似度η_Si-SFj，并将相似度η_Si-SFj最大的特征投影线组合S_Fj与草图笔画线s_i进行对应；即根据人体草图笔画线s_i的闭包矩形覆盖范围，在上述特征投影线集合S_F中寻找候选匹配特征投影线集合S_FC；在候选匹配特征投影线集合S_FC中，根据任意两条特征投影线l₁和l₂之间的相邻点的二维距离d_l1l2、二维方向差异f_l1l2以及遮挡度量c_l1l2，综合计算两两特征投影线l₁和l₂之间的距离ε；然后，在候选匹配投影线集合S_FC中，遍历查找可能的特征投影线组合集合S_FSi，并计算S_FSi中各种组合形式的组合代价集合C_Si；最后，计算人体草图笔画线s_i与每个特征投影线组合S_Fj的形状相似度Sim_Si-SFj，根据形状相似度Sim_Si-SFj和特征投影线组合代价C_SFj，计算人体草图笔画线s_i与特征投影线组合S_Fj的相似度η_Si-SFj，并将相似度η_Si-SFj最大的特征投影线组合S_Fj与草图笔画线s_i进行对应；

根据上述相似度最大的草图笔画线s_i和特征投影线组合S_Fj，将草图笔画线s_i的草图笔画点作为观察状态，将特征投影线组合S_Fj的特征投影线点作为隐藏状态，根据三维模型网格点和对应特征投影线点之间的距离D_P及法向量差异D_N计算转移概率，根据三维模型网格点和对应特征投影线点之间的连续性度量D_C计算消除概率，并建立隐马尔科夫模型；将草图笔画点作为输入，计算概率最大的隐藏状态序列，作为对应特征投影线特征点的序列，实现草图笔画点与特征投影线特征点的匹配；

在上述匹配结果的基础上，计算特征投影线点所对应的三维模型网格点在绘制平面的位移参数P_DSi，所有特征投影线点对应的三维模型网格点位移参数构成三维人体姿态模型M_o的特征点位移集合P_D。

本发明中，优选地，步骤三中，包括以下步骤：

对三维人体姿态模型M_o(δ′,α₀′)进行均值坐标编码，即对每个三维模型网格点v_a，根据其邻接点坐标计算得到三维模型网格点v_a处的法向量n_a，及三维模型网格点坐标在该法向量方向投影的平均长度d_a；根据三维模型网格点v_a的周围顶点在该三维模型网格点v_a的投影平面上的投影长度，计算各三维模型网格点的权重w_ab以及各边夹角的余弦值cos_ab；根据均值坐标编码对所有三维模型网格点v_a的坐标进行编码，得到三维模型网格点v_a的均值编码坐标V_a；

在步骤二所计算得到的三维模型网格点在绘制平面的位移参数的约束下，对加权后的三维人体姿态模型M_o(δ′,α₀′)求解得到形变后的三维人体网格模型M_R(δ′,α₀′)，从而完成三维人体多姿态建模。

本发明中，优选地，所述的特征投影线l₁和特征投影线l₂两两之间的距离ε定义为：

$>ϵ=\frac{f_{l1/l2}}{d_{l1/l2}·c_{l1l2}}$>

其中，f_l1l2为两个特征投影线的二维方向差异，c_l1l2为两个特征投影线的遮挡度量，d_l1l2为两个特征投影线相邻点的二维距离；各变量的计算公式定义如下：

$>f_{l1l2}=\frac{{\gamma }_1-{\gamma }_2}{2\pi },$>$>c_{l1l2}=\frac{l_s}{l_l·l},$>$>d_{l1l2}=\underset{p_a\in l_1,p_b\in l_2}{\min }\left|\right|p_a-p_b\left|\right|,$>

其中，γ₁和γ₂分别为两条特征投影线与绘制平面上的x轴(水平)和y轴(竖直)的夹角(x轴与y轴为绘制平面内互相垂直的任意直线，对计算结果没有影响)，l为被遮挡特征线的长度，l_s为遮挡线较短部分的长度，l_l为遮挡线较长部分的长度，p_a为特征投影线l₁上的任意点，p_b为特征投影线l₂上的任意点。

本发明中，优选地，所述的特征投影线组合S_Fj可表示为如下形式：

S_Fj={l₀,l₁,...,l_n1|l_i∈S_F},S_Fj∈F_can

其中，l₀,l₁,...,l_n1为候选匹配特征投影线集合S_F中的一组首尾相连的特征投影线。则特征投影线组合S_Fj的组合代价C_SFj定义为：

$>C_{\mathrm{SFj}}={ϵ}_{l_0-l_1}+{ϵ}_{l_{m-1}-l_m}+\underset{t=1}{\overset{m-1}{\Sigma }}{w}_t\times ({ϵ}_{l_{t-1}-l_t}+{ϵ}_{l_t-l_{t+1}})$>

其中，为特征投影线l_k-1和特征投影线l_k两两之间的距离，k=1,2,...t...,m，w_t为特征投影线l_t在特征投影线组合S_Fj中的权重，该权重w_t定义为：

w_t=L_t/L_all

其中，L_t为特征投影线l_t的长度，L_all为特征投影线组合S_Fj中所有成员投影线的总长度。

本发明中，优选地，所述的均值坐标编码及形变方法，包含以下步骤：

对三维人体姿态模型M_o进行均值坐标编码，将各三维模型网格点坐标v_a表示为：

$>v_a=\underset{(a,b)\in E}{\Sigma }{w}_{\mathrm{ab}}(v_b+|\left|N_a\underset{(a,b)\in E}{\Sigma }{w}_{\mathrm{at}}(v_t-v_b)\right|\left|{\cos }_{\mathrm{ab}}{n}_a\right),N_a=I^3-n_a{n}_a^T,$>

其中，(a,b)∈E表示网格点v_a和v_b是相邻的，其中E为三维人体姿态模型M_o的边集，w_ab为相邻三维模型网格点v_a和v_b之间边的权重，cos_ab为边(a,b)边a和边b相邻夹角的余弦值，n_a为各三维模型网格点的均值编码法向量，v_a为当前计算三维模型网格点的坐标，v_t为与v_a相邻的三维模型网格点，I³为三阶单位矩阵。各变量值定义为：

$>w_{\mathrm{ab}}=\frac{\tan ({\gamma }_{\mathrm{ab}}/2)+\tan ({\delta }_{\mathrm{ab}}/2)}{l_{\mathrm{ab}}},$>$>{\mathrm{ct}}_{\mathrm{ab}}=\frac{(v_a-v_b)·n}{\left|\right|v_a-v_b\left|\right|},$>$>{\cos }_{\mathrm{ab}}=\frac{{\mathrm{ct}}_{\mathrm{ab}}}{\sqrt{1-c_{\mathrm{ab}}^2}},$>

$>n_a=\frac{\underset{t=1}{\overset{m}{\Sigma }}(v_{\mathrm{bt}+1}-l)\times (v_{\mathrm{bt}}-l)}{\left|\right|\underset{t=1}{\overset{m}{\Sigma }}(v_{\mathrm{bt}+1}-l)\times (v_{\mathrm{bt}}-l)\left|\right|},$>$>l=\frac{1}{m}\underset{(a,b)\in E}{\Sigma }{v}_b,$>

其中，在法向量垂直的投影平面上，三维网格点v_a与v_b的投影分别为v_a′和v_b′，则γ_ab与δ_ab表示投影边(v_a′,v_b′)与相邻投影边的夹角，l_ab表示投影边(v_a′,v_b′)的长度，m为与三维网格点v_a相邻接的三维网格点数量，三维网格点v_a的所有相邻网格点按照逆时针顺序标记为{v_b1,v_b2,...,v_bm}。

最后，在上述约束条件下，求解如下的最小二乘问题，可得到更新后的人体模型网格点坐标集合V′：

$>\arg \underset{V^{\prime }}{\min }G\left(V^{\prime }\right)=\frac{1}{2}\underset{v_a\in V}{\Sigma }{q}_a{(v_a-F(v_b,n_a\left(v_b\right)))}^2,$>

其中，目标函数G(V′)计算形变过程中三维模型网格点集V′的均值编码坐标差异度，q_a为根据关节点位置计算得到的三维模型网格点v_a的权重，F_a(v_b,n_a(v_b))为根据相邻网格点v_b坐标计算得到的三维模型网格点v_a的均值编码坐标。

有益效果：本发明具有以下优点：1、采用二维线特征投影表示三维人体模型特征，便于用户使用草绘方式对人体模型进行编辑；2、采用隐马尔科夫模型实现二维草绘笔画与二维线特征投影的形状匹配，能够在笔画-特征线匹配过程中充分利用人体模型的三维形状特征，使匹配结果更符合用户交互的意图；3、将关节子空间形变方法与均值编码形变方法相结合，使方法的形变过程能够保持三维人体模型的关节特性，增强了建模结果的真实感。

附图说明

下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。

图1是本发明的流程图。

图2a和图2b是均值坐标编码计算中各参数的示意图。

图3a、图3b、图3c是本发明的实施例示意图。

具体实施方式

本发明提出了一种采用手绘草图的三维人体多姿态建模方法，允许用户通过绘制的人体特征草图直接构建三维人体数字模型。其实施主要涉及模型预处理、笔画匹配以及模型形变三大关键技术，其处理流程如图1所示。用户显式绘制人体特征草图，在模型预处理部分，用户在三维空间中对系统给定的三维人体姿态模型进行调整，使其观察视角和人体姿态与所绘制人体特征草图相一致的；笔画匹配部分，首先在给定的观察视角和人体姿态下，对上述三维人体姿态模型进行投影并提取轮廓线、暗示性轮廓线、网格模型的谷线和脊线等特征投影线集合，然后根据用户绘制草图笔画的闭包矩形计算候选特征投影线集合，并根据特征投影线间的距离差异、方向差异以及遮挡差异计算特征投影线两两之间的距离，并针对候选特征投影线集合中每一种可能的组合形式计算其组合代价，最后，根据上述组合代价以及曲线的形状相似度度量综合计算草绘笔画线与特征投影线组合的相似度，根据最相似的特征投影线组合与草绘笔画线之间的关系建立隐马尔科夫模型，将人体草图笔画点与特征线投影点进行匹配，并计算三维人体姿态模型对应三维模型网格点在绘制平面的位移参数；在模型形变部分，首先由用户在三维人体姿态模型的正视图下标定该人体模型的关节点位置，然后根据人体网格模型的各三维模型网格点到相应关节点的距离，计算该三维模型网格点的形变权重，然后，根据各三维模型网格点邻接点坐标计算其法向量和邻接点在该法向量方向的投影平均值，计算各邻接边的权重以及各边夹角的余弦值，并根据均值坐标编码公式对三维人体姿态模型的各三维模型网格点坐标进行编码，最后，在三维模型网格点位移参数的约束下，对加权后的三维人体姿态模型求解一个最小二乘问题，即可得到形变后的三维人体网格模型。下面分别介绍各部分的主要实施方式。

1.模型预处理

模型预处理的计算包括关节点标定加权和姿态调整两个步骤。

1.1关节点标定加权

本发明中，为了使模型形变过程符合人体关节点约束，因此首先需要对三维人体姿态模型进行加权，通过在三维人体姿态模型M_o(δ′,α₀′)的正视图下标定该人体模型的关节点位置，并对三维人体姿态模型M_o(δ′,α₀′)的每个顶点v_a计算其到最近人体关节点的距离D_a，即可计算各三维模型网格点的权重，其算法流程如下：

步骤1：用户在三维人体姿态模型M_o(δ′,α₀′)的正视图下，标定该人体模型的关节点位置{C₀,C₁,...,C_n}；

步骤2：对三维人体姿态模型M_o(δ′,α₀′)，计算各关节点的距离值下限

$>d_a=\lambda ·\underset{v\in \mathrm{surf}}{\min }\left|\right|v-C_a\left|\right|;$>

步骤3：对三维人体姿态模型M_o(δ′,α₀′)的任一网格点p，按照下式计算该点对于关节点C_a的权重q_a：

$>\left(\begin{array}{cc}{q}_a=\frac{d_a}{\left|\right|p-C_a\left|\right|}& \left|\right|p-C_a\left|\right|<d_a\\ q_a=1& \mathrm{otherwise}\end{array}\right)$>

步骤4：重复步骤2~步骤3，计算网格点p对于各关节点的权重序列{q₀,q₁,...,q_n}，将作为该点权重。

1.2姿态调整

用户绘制人体特征草图S，并调整给定的三维人体姿态模型M_o的观察视角和人体姿态，使三维人体姿态模型M_o的观察视角和人体姿态与人体特征草图S一致，其流程如下：

步骤1：用户绘制人体特征草图S={s₁,s₂,...,s_n}，s₁,s₂,...,s_n表示由草图笔画点构成的各条人体笔画线，1≤i≤n，n为人体特征草图中的笔画数；

步骤2：三维人体姿态模型记为M_o(δ,α₀)，并以三维人体网格模型的形式显示给用户，该模型采用骨架-人体轮廓曲面双层模型，通过调整姿态参数δ和位移参数α进行控制；

步骤3：根据所绘制的人体特征草图S，用户分别在xyz三个方向上调整人体姿态模型M_o的关节点位置，使得到的三维人体姿态与草图中的人体姿态一致，记录此时人体姿态参数为δ′和位移参数α′；

步骤4：用户在三维环境中旋转观察视角，使其与草图中的观察视角一致，记录此时的观察视向量v_view；

步骤5：将该观察视角及人体姿态下的三维人体姿态模型记为M_o(δ′,α₀′)。

2.笔画匹配

本发明中，用户通过绘制人体特征线笔画来控制人体姿态模型进行形变，从而得到新的人体模型；因此，在给定的观察视角和人体姿态下，必须将用户绘制的人体特征笔画线与三维人体姿态模型的特征线进行匹配，并通过对应网格特征点的位移参数约束其后的模型形变过程。笔画匹配通过人体特征投影、特征组合代价计算以及特征点匹配三个步骤完成。

2.1人体特征投影

根据三维人体姿态模型M_o(δ′,α₀′)的几何特性，从网格模型中提取人体特征投影线作为用户编辑人体特征的绘制和形变依据，本发明中，将人体特征线分为轮廓特征线、暗示性轮廓线、谷线和脊线三类分别进行投影计算。

轮廓特征线，即在投影视图下区分人体模型区域与背景的轮廓线，其特征点的法向量与用户的观察的视向量接近于垂直，可通过计算各点法向量与视向量之间的内积进行判断，其算法流程如下：

步骤1：由当前观察视角得到当前观察的视向量，记为v_view；

步骤2：对三维人体姿态模型M_o(δ′,α₀′)中的某一个网格点v_a，计算该点处三维网格模型的法向量n_a；

步骤3：计算视向量v_view与该网格点法向量n_a的内积p_a＝v_view·n_a；

步骤4：若内积|p_a|<η_C，则将网格点v_a加入轮廓线特征点集合V_C，其中轮廓判断阈值η_C的取值为0.1~0.2左右，此处取值为0.2；

步骤5：重复步骤2~步骤4，直到三维人体姿态模型M_o(δ′,α₀′)中的所有网格点均已被计算；

步骤6：将邻近的轮廓特征点相连，组成若干轮廓线，将其在视平面上的投影线集合记为轮廓投影线集合F_C。

暗示性轮廓线，即当前视角下并非轮廓线，但当视角变化的时候会成为轮廓的特征线，该类特征线可通过计算三维模型网格点处的半径曲率K_r以及K_r在w方向的方向导数D_w(K_r)进行判断，其算法流程如下：

步骤1：对三维人体姿态模型M_o(δ′,α₀′)中的某一个网格点v_a，计算该点处的主曲率k₁(v_a)和k₂(v_a)，计算方法见文献5 Taubin,G.1995.Estimating the tensor of curvatureof a surface from a polyhedral approximation.In ICCV’95,902–907.；

步骤2：计算网格点v_a处，w方向与k₁(v_a)的主方向的夹角φ；

步骤3：计算网格点v_a处的半径曲率k_r(v_a)=k₁(v_a)cos²φ+k₂(v_a)sin²φ；

步骤4：计算k_r(v_a)在w方向的方向导数D_w(k_r)；

步骤5：若方向导数D_w(k_r)>0，则将网格点v_a加入暗示性轮廓点集合V_SC；

步骤6：重复步骤1~步骤5，直到三维人体姿态模型M_o(δ′,α₀′)中的所有网格点均已被计算；

步骤7：将邻近的暗示性轮廓特征点相连，组成若干暗示性轮廓线，将其在视平面上的投影线集合记为暗示性轮廓投影线集合F_SC。

谷线和脊线，即人体网格模型表面曲率的局部极值点，其计算方法根据文献6 Judd,T.,Durand,F.,Adelson,E.2007.Apparent Ridges for Line Drawing.ACM Trans.Graph.26,3,Article 19,July 2007,7pages所述进行计算，得到视平面上的谷线集合F_V和脊线集合F_R。

最后，需要对所得特征投影线集合进行消隐，即将当前观察视角下不可见的特征投影点进行剪除，可利用OpenGL的深度缓存来判断每个特征点是否可见，其计算流程如下：

步骤1：对特征投影线集合F_C、F_SC、F_V和F_R中的某个特征点p，得到其OpenGL窗口深度d(p)；

步骤2：将该特征点的深度值记为dep(p)=p^Z；

步骤3：若d(p)=dep(p)，则将特征点p保留，否则，从特征投影线集合中将特征点p删除；

步骤4：重复步骤1~步骤3，直到特征投影线集合F_C、F_SC、F_V和F_R中的所有特征点均已被计算。

2.2特征组合代价计算

本发明在提取三维人体姿态模型M_o(δ′,α₀′)特征投影线的基础上，根据用户绘制的草图特征笔画s_i在上述特征投影线集合F_C、F_SC、F_V和F_R中，寻找所有可能与草图特征笔画s_i相匹配的特征投影线组合S_FSi，并根据特征投影线间的几何关系计算各组合形式的组合代价集合C_Si。计算特征组合代价集合C_Si包括候选特征线集合计算、特征投影线组合查找以及特征投影线组合代价计算三个步骤。

1)候选特征线集合计算：根据用户绘制的草图特征笔画s_i，计算该笔画的闭包矩形，并将该闭包矩形所覆盖区域内的所有特征投影线作为候选匹配特征投影线，其算法流程如下：

步骤1：对某草图特征笔画s_i，计算其采样点在x方向的最大值right和最小值left，以及在y方向的最大值bottom和最小值top；

步骤2：计算该草图特征笔画s_i的闭包矩形

步骤3：对特征投影线集合F_C、F_SC、F_V和F_R中的某条特征投影线l_i，若l_i与重叠，则将该特征投影线l_i加入候选匹配特征投影线集合S_FC；

步骤4：重复步骤3，直到特征投影线集合F_C、F_SC、F_V和F_R中的所有特征投影线均已被计算。

2)特征投影线组合查找：根据三维人体姿态模型M_o(δ′,α₀′)提取的特征线投影通常是不连续的若干特征线的集合，为了找到可能与用户绘制的草图特征笔画匹配的特征组合，需要在候选匹配特征投影线集合S_FC中遍历查找所有可能的特征投影线组合，其算法流程如下：

步骤1：对候选匹配特征投影线集合S_FC中每条特征投影线l_i，记其两个端点分别为p_2i和p_2i，计算其端点的邻接特征线条数n_2i和n_2i+1；

步骤2：对任意端点p_i，若n_i=0，则将其加入起始端点集合P_o；

步骤3：对于起始端点集合P_o中的每个端点集合P_i，将其所在特征线l加入新的特征线组合S_Fj；

步骤4：对特征线l的另一个端点p，将通过该点与特征线l邻接的特征线l′加入特征线组合S_Fj；

步骤5：重复步骤3~步骤4，直到当前特征线的另一个端点p′也在起始端点集合P_o中，将特征线组合S_Fj加入候选匹配特征投影线组合集合S_FSi中；

步骤6：重复步骤2~步骤5，直到起始端点集合P_o中的所有端点均已被计算。

3)特征投影线组合代价计算：候选匹配特征投影线组合集合S_FSi中的各种特征投影线组合并不都是合理的，或者说其合理程度是不同的，本发明中采用特征投影线组合代价C_SFj来表征对应特征投影线组合S_Fj的合理程度，并将此组合代价用于草图笔画与特征投影线组合的匹配过程中。特征投影线组合代价计算通过特征投影线距离计算和特征组合代价计算两个步骤完成。

a)特征投影线距离计算：特征投影线距离表示两条特征投影线相互进行组合时所需要的组合代价，分为距离差异、方向差异和遮挡差异3个部分分别进行计算，其计算流程如下：

步骤1：对候选匹配特征投影线集合S_FC中的任意两条特征投影线，将其记为l_i和l_j；

步骤2：遍历该两条特征投影线l_i和l_j的所有特征点，计算其距离差异

$>d_{l1l2}=\underset{p_a\in l_1,p_b\in l_2}{\min }\left|\right|p_a-p_b\left|\right|;$>

步骤3：在绘制平面上，计算特征投影线l_i与x轴的夹角γ₁，特征投影线l_j与x轴的夹角γ₂，并计算其方向差异

步骤4：检测两条特征投影线l_i和l_j是否存在T型相交点，若不存在，则记遮挡差异c_l1l2=0；

步骤5：计算被遮挡特征线长度l，在遮挡特征线中，计算较长分段的长度为l_l，较短分段的长度为l_s；

步骤6：计算该两条特征投影线l_i和l_j的遮挡差异为

步骤7：计算该两条特征投影线l_i和l_j的距离为

步骤8：重复步骤1~步骤7，直到候选匹配特征投影线集合S_FC中的任意两条特征线之间均已被计算。

b)特征组合代价计算：对候选匹配特征投影线组合集合S_FSi中的每组特征投影线组合S_Fj，计算其通过所有成员特征投影线S_Fj={l₁,l₂,...,l_m}进行组合时所产生的综合组合代价C_SFj，其算法流程如下：

步骤1：在候选匹配特征投影线组合集合S_FSi中，选择任一特征投影线组合，记为S_Fj；

步骤2：对特征投影线组合S_Fj，计算其成员特征投影线的总长度

步骤3：对任一特征投影线，计算其组合代价权重w_t=L_t/L_all，其中L_t为该特征投影线的长度；

步骤4：计算该特征投影线的组合代价C_t-SFj=0.5×w_t×(ε_t~(t-1)+ε_t~(t+1))，其中ε_t~(t-1)为特征投影线l_t与l_t-1之间的距离；

步骤5：重复步骤3~步骤4，直到特征投影线组合S_Fj中的所有特征投影线均已被计算；

步骤6：计算特征投影线组合F_j的组合代价

步骤7：重复步骤1~步骤6，直到候选匹配特征投影线组合集合S_FSi中的所有特征投影线组合均已被计算。

2.3特征点匹配

本发明中，用户绘制的草图人体特征笔画可根据形状相似性及对应特征投影线组合的组合代价进行匹配，并通过建立对应草图笔画和特征投影线组合的隐马尔科夫(HMM)模型将对应的草图笔画点与网格模型特征点进行对应。特征点匹配过程通过草图笔画~特征投影线相似度计算以及草图笔画点~网格模型特征点对应两个步骤完成。

1)草图笔画~特征投影线相似度计算：在其候选匹配特征投影线组合集合S_FSi中，根据形状相似度d(s_i,S_Fj)与对应特征投影线组合S_Fj的组合代价C_SFj，可计算得到该特征投影线组合S_Fj与草图笔画s_i的相似度Sim_Si-SFj。本发明中，使用点集之间的Hausdorff距离表征两条曲线之间的形状相似度，其算法流程如下：

步骤1：对草图笔画s_i中的任意点p_a，计算特征投影线组合S_Fj到该点的最近距离

$>d_{\mathrm{pa}}=\underset{p_b\in S_{\mathrm{Fj}}}{\mathrm{mim}}d(p_a,p_b);$>

步骤2：重复步骤1，直到草图笔画s_i中的所有点均已被计算，并计算有向Hausdorff距离$>\overrightarrow{d}(s_i,S_{\mathrm{Fj}})=\underset{p_a\in s_i}{\max }\underset{p_b\in S_{\mathrm{Fj}}}{\min }d(p_a,p_b);$>

步骤3：如上所述计算反方向Hausdorff距离$>\overrightarrow{d}(S_{\mathrm{Fj}},s_i)=\underset{p_a\in S_{\mathrm{Fj}}}{\max }\underset{p_b\in s_i}{\min }d(p_a,p_b);$>

步骤4：计算该草图笔画s_i与特征投影线组合S_Fj的形状相似度度量

$>d(s_i,S_{\mathrm{Fj}})=\max \{\overrightarrow{d}(s_i,S_{\mathrm{Fj}}),\overrightarrow{d}(S_{\mathrm{Fj}},s_i)\};$>

步骤5：计算该草图笔画s_i与特征投影线组合S_Fj的相似度Sim_Si-SFj=d(s_i,S_Fj)×C_SFj；

步骤6：重复步骤1~步骤5，直到候选匹配特征投影线组合集合S_FSi中的所有特征投影线组合均已被计算；

2)草图笔画点~网格模型特征点对应：为计算对应网格特征点的位移参数，需要将用户绘制的草图人体特征笔画采样点与三维人体姿态模型的网格特征点进行对应，本发明中，按照文献7 Vladislav Kraevoy,Alla Sheffer,and Michiel van de Panne.Contourbased Modeling Using Deformable 3D Templates.Tech Report,2007所述方法，根据草图笔画与匹配的特征投影线组合之间的几何关系建立HMM模型，并通过Viterbi算法求解草图笔画点与网格模型特征点之间的对应关系，其算法流程如下：

步骤1：从草图笔画s_i的候选匹配特征投影线组合集合S_FSi中选择相似度最高的特征投影线组合S_Fj；

步骤2：将草图笔画点s_i={p₀,p₁,...,p_n}作为观察状态，特征投影线的特征点S_Fj={v₀,v₁,...,v_m}作为隐藏状态；

步骤3：对任意草图笔画点p和特征投影线特征点v，计算二维距离d_p=(p^x-v^x)²+(p^y-v^y)²，以及法向量差异d_N=n^p·n^v；

步骤4：计算草图笔画点连续性度量d_C=||v_i-v_i-1||²/||p_i-p_i-1||²；

步骤5：计算HMM模型的转移概率以及消除概率$>P\left(p_j\right|v_i)=e^{-\frac{1}{2}{\left(\frac{d_p}{{\sigma }_p}\right)}^2}{e}^{-\frac{1}{2}{\left(\frac{d_{N-1}}{{\sigma }_N}\right)}^2;}$>

步骤6：根据文献8 RABINER,L.R.1989.A tutorial on hidden Markov models andselected applications inspeech recognition.Proceedings of the IEEE 77,2,257-286.所述方法，采用Viterbi算法计算该HMM模型最有可能的隐藏状态序列，作为草图笔画点的对应序列；

步骤7：根据草图笔画点和特征投影线特征点的对应关系，计算网格特征点的位移参数P_D={v_a=v_def|v_a∈M_o(θ′,α₀′)}。

3.模型形变

本发明中，用户在三维人体姿态模型的正视图下标定该人体模型的关节点位置，根据三维人体网格模型网格点与人体关节点之间的相对位置对该人体网格模型进行加权；然后，在对应三维模型的三维模型网格点位移参数的约束下，通过均值编码网格形变算法对人体网格模型进行形变，得到最终的三维人体网格模型。模型形变过程通过人体模型加权以及人体模型形变两个步骤完成。

3.1人体模型形变

本发明中，如文献9 Kraevoy V.,Sheffer A.Mean-value geometry encoding.International Journal of Shape Modeling 12,1,2007所述的均值编码方法对三维人体姿态模型M_o(δ′,α₀′)进行形变。人体模型形变通过均值坐标编码以及网格形变坐标求解两个步骤完成。

1)均值坐标编码：对三维人体网格模型M_o(δ′,α₀′)进行均值坐标编码，其计算流程如下：

对三维人体网格模型M_o(δ′,α₀′)进行均值坐标编码，即对每个三维模型网格点v_a，根据其邻接点坐标计算得到三维模型网格点v_i处的法向量n_i，及各点坐标在该法向量方向投影的平均值d_a；根据顶点v_a的周围顶点在该点v_a的投影平面上的投影长度，计算各点的权重w_ab以及各边夹角的余弦值cos_ab，这两个值在形变过程中保持不变；最后，根据均值坐标编码公式对该顶点v_a的坐标进行编码，得到v_a的均值编码坐标V_a。

步骤1：对每个三维模型网格点v_a，计算其邻接网格点的平均坐标

步骤2：基于三维模型网格点v_a的邻接网格点坐标，按照下式计算其均值编码法向量：

$>n_a=\frac{\underset{t=1}{\overset{m}{\Sigma }}(v_{\mathrm{bt}+1}-l)\times (v_{\mathrm{bt}}-l)}{\left|\right|\underset{t=1}{\overset{m}{\Sigma }}(v_{\mathrm{bt}+1}-l)\times (v_{\mathrm{bt}}-l)\left|\right|}$>

步骤3：计算各邻接网格点在上述法向量n_a方向投影的平均值其中v_b为v_a的邻接点，共有m个；

步骤4：按照下式计算各邻接边的权重w_ab，以及各边夹角的余弦值cos_ab：

$>w_{\mathrm{ab}}=\frac{\tan ({\gamma }_{\mathrm{ab}}/2)+\tan ({\delta }_{\mathrm{ab}}/2)}{l_{\mathrm{ab}}}$>

$>{\mathrm{ct}}_{\mathrm{ab}}=\frac{(v_a-v_b)·n}{\left|\right|v_a-v_b\left|\right|},$>$>{\cos }_{\mathrm{ab}}=\frac{{\mathrm{ct}}_{\mathrm{ab}}}{\sqrt{1-c_{\mathrm{ab}}^2}}$>

其中，在法向量垂直的投影平面上，三维网格点v_a与v_b的投影分别为v_a′和v_b′，则γ_ab与δ_ab表示投影边(v_a′,v_b′)与相邻投影边的夹角，l_ab表示投影边(v_a′,v_b′)的长度，m为与三维网格点v_a相邻接的三维网格点数量，三维网格点v_a的所有相邻网格点按照逆时针顺序标记为{v_b1,v_b2,...,v_bm}，参见图2a和图2b。

步骤5：按照下式计算该三维模型网格点v_a的均值编码坐标：

$>v_a=\underset{(a,b)\in E}{\Sigma }{w}_{\mathrm{ab}}(v_b+|\left|N_a\underset{(a,b)\in E}{\Sigma }{w}_{\mathrm{at}}(v_t-v_b)\right|\left|{\cos }_{\mathrm{ab}}{n}_a\right),N_a=I^3-n_a{n}_a^T,$>

其中，(a,b)∈E表示网格点v_a和v_b是相邻的，其中E为三维人体姿态模型M_o的边集，w_ab为相邻三维模型网格点v_a和v_b之间边的权重，co_ab为边(a,b)边a和边b相邻夹角的余弦值，n_a为各三维模型网格点的均值编码法向量，v_a为当前计算三维模型网格点的坐标，v_t为与v_a相邻的三维模型网格点，I³为三阶单位矩阵。各变量值定义为：

$>w_{\mathrm{ab}}=\frac{\tan ({\gamma }_{\mathrm{ab}}/2)+\tan ({\delta }_{\mathrm{ab}}/2)}{l_{\mathrm{ab}}},$>$>{\mathrm{ct}}_{\mathrm{ab}}=\frac{(v_a-v_b)·n}{\left|\right|v_a-v_b\left|\right|},$>$>{\cos }_{\mathrm{ab}}=\frac{{\mathrm{ct}}_{\mathrm{ab}}}{\sqrt{1-c_{\mathrm{ab}}^2}},$>

$>n_a=\frac{\underset{t=1}{\overset{m}{\Sigma }}(v_{\mathrm{bt}+1}-l)\times (v_{\mathrm{bt}}-l)}{\left|\right|\underset{t=1}{\overset{m}{\Sigma }}(v_{\mathrm{bt}+1}-l)\times (v_{\mathrm{bt}}-l)\left|\right|},$>$>l=\frac{1}{m}\underset{(a,b)\in E}{\Sigma }{v}_b,$>

其中，在法向量垂直的投影平面上，三维网格点v_a与v_b的投影分别为v_a′和v_b′，则γ_ab与δ_ab表示投影边(v_a′,v_b′)与相邻投影边的夹角，l_ab表示投影边(v_a′,v_b′)的长度，m为与三维网格点v_a相邻接的三维网格点数量，三维网格点v_a的所有相邻网格点按照逆时针顺序标记为{v_b1,v_b2,...,v_bm}，各参数定义如图2a和图2b所示。

2)网格形变坐标求解：根据三维人体姿态模型的三维模型网格点在xy平面的位移参数，对加权后的三维人体网格模型M_o(δ′,α₀′)求解一个最小二乘问题，即可得到形变后的三维人体网格模型M_R(δ′,α₀′)，其计算流程如下：

步骤1：将网格特征点的位移参数P_D={v_a=v_def|v_a∈M_o(δ′,α₀′)}作为优化问题的硬约束；

步骤2：利用Levenberg-Marquadt算法按照下式求解最小二乘问题：

$>\arg \underset{V^{\prime }}{\min }G\left(V^{\prime }\right)=\frac{1}{2}\underset{v_a\in V}{\Sigma }{q}_a{(v_a-F(v_b,n_a\left(v_b\right)))}^2$>

步骤3：解上述最小二乘问题所得结果即为形变过后的三维人体姿态模型的网格点坐标。

图3a、图3b、图3c示出了从单幅手绘人体特征草图创建三维人体网格模型的实例效果。图3a为用户绘制的人体特征线草图，图3b为初始人体姿态模型，图3c为生成的人体模型以及与原始草图的对比，可以看到用户的绘制意图在结果模型中得到了体现。由于图3b、图3c为实体图，因此必须使用色块表示。