基于传播算法的三维人体模型识别方法
2016-10-14陈郁
陈郁
基于传播算法的三维人体模型识别方法
陈郁
在三维人体网格模型的测量和建模过程中，人体部位（如手臂，躯干）的识别是非常基础且重要的。利用网格模型特点而设计的传播算法能够快速地对人体的一些部位进行自动的识别。该方法不仅代码简单易用，而且对于残缺粗糙模型的识别率也很高。
传播算法；人体部位识别；三维人体网格模型；
0 引言
当前，在产业的改造升级中，尤其是在服务行业的改造升级中，高端化、精细化、个性化和私人定制的需求不断涌现，成为创新产业、新兴产业中的重要一支。因此，在计算机上创建更接近实体、更精准、更具特点的三维人体模型[1]，配合人体工学解决广泛的与人体相关的问题，也越来越受到行业的重视。其三维人体模型的测量、建模和运用中的问题也常常成为热点。
尽管有许多方法可用来采集三维人体的数据[2][3]，但是目前主流的方法是利用三维扫描仪采集数据，建立三维人体网格模型。由于人体是一个复杂的三维曲面，而且腋窝裤裆等部位比较难以被扫描仪扫描到，因此会产生很多残缺的粗糙的模型。对于这些残缺粗糙的模型，一些基于人体比例和特征点的识别方法很难处理好。
为此我们利用三维网格模型网格点线间可传播信息的特点而设计的三维人体模型传播算法识别法，经近一万次的运用证明，可以较好的解决这类问题。本文谨以此种方法的原理和实践为基础作以下论述。
1 三维网格模型简介
三维网格模型通常是利用三维扫描仪扫描和采集人体或物体的数据，并将采集的数据以点云的形式储存[4]，然后将其转换成为一个整体的三维网格模型[5][6]。这些三维网格模型的表面上有着网格点（Vertex），网格点之间相互有网格线（Edge）相连，以网格点、线组成的面为网格面（Facet），如图1所示：
图1 三维网格模型示意图
这种通用的三维网格模型（3D Mesh）的形式能被绝大多数三维软件所识别和读取，因此通用性和易读性非常好。可以被计算机方便的用来储存和作多种处理。
三维人体模型在三维坐标系中摆放的位置如图2所示：
图2 三维人体模型所在的坐标系
在三维坐标系的中间。X轴表示人体自右至左的方向，Y轴表示人体自下至上的方向，Z轴表示人体自后向前的方向。
2 网格点的传播和传播算法
在图1中我们可以看到网格点之间是由网格线进行连接的，每个网格点可以通过网格线找到她最邻近的几个网格点，即相邻网格点，而这几个相邻网格点又有它们各自的相邻网格点。如果我们把一个网格中的任意一网格点打上已经被感染的标记（或称感染点，如传染病的感染源），它就会把该标记通过网格线传播给它的相邻网格点，而被感染的相邻网格点也会被打上已经被感染的标记又会成为新的传播源，把标记传播给它所有的相邻网格点。整个过程就像传染病的扩散过程，直到碰到设置的隔离板（通常是一个平面，无网格，在三维直角坐标系中的方程为AX + BY + CZ + D = 0 [7]），或者把整个网格上所有的网格点都传染后才会停止。整个传播过程的示意图如图3所示：
（a） （b）
图3a 将网格上的一网格点设置成传染源
图3b 传染源将邻近的网格点传染
（c） （d）
图3c 因为有了隔离板网格点M没有被感染
图3d 黄色三角形内网格点因为隔离板而未被感染
图3 网点传播示意图
图3a：被标注为黑色圆点的网格点是设置的传染源。图3b：传染源的相邻网格点因被传染也变成黑色圆点，这些变成黑色圆点的网格点又变成为新的传染源。图3c：传染源继续传染，但是网格点M因为在隔离板之上而免于被传染。图3d：传染过程因为隔离板的作用而未能继续向上进行。
利用网格模型的这一特点，我们设计了能够快速对人体的一些部位进行自动识别的传播算法。它是通过设置传染源点和隔离板，让传染源在隔离板以下区域内传播，调整隔离板，并对由此产生的传染和未被传染的网格点的传播形态进行比较计算，以求证、识别网格模型中一些部位的算法，定名为传播算法。
图3系列示意图片给出了传播的过程和隔离板的作用（黑色圆点为感染点）。
3 利用传播算法寻找手臂部分
要准确的找到手臂部分的范围和尺寸，首先要定位出人体腋窝的位置，但是人体腋窝处的位置通常三维扫描仪很难扫描清楚，因而腋窝部分的网格经常会出现残缺或者重叠，而一般的人体部位识别办法很难进行识别。下面用手臂为案例，具体介绍传播算法的应用。
3.1传播算法的具体操作
腋窝裤裆等部位正是人体上两个独立肢体的连接部位。这些部位有让两个独立肢体连通，并会引发感染网格点数目突变的网格线、点。通过传播算法寻找识别身体上这样的特征点，我们可以找出手臂的范围、位置和尺寸。基本方法是：通过设置隔离区将三维人体网格模型分成手臂和身体两个部分。不断地扩大隔离区的范围直到手臂和身体这两个部分的连接处，即两个独立肢体上网格线的连通处。这样就找到了腋窝的高度，从而找出手臂的范围。我们先看一下该方法的伪代码：
CList
CList
CPlane bndPlane; //设置隔离板
CPosition armholePos; //被传染的网格点的边界位置
GetSeed(vArm) 得到传播源
Init（bndPlane） // 初始化隔离板
do
{
//应用传播算法找到隔离板内所有能被传染的网格点
Propagate(vArms);
// 检查每一个被传染的点，将在隔离板以外的网格点删除
For (each vertex in vArms)
{
If (vertex OVER bndPlane)
vArms.Delete(vertex)
}
//记住被传染的网格点的边界位置
SetArmPosition(armholePos);
//隔离板内所有的点
VerticesInBoundaryPlane(vBnds);
bndPlane.Step(); //向上提升隔离板
}
While(vArms.Num / vBnds.Num < threshold)
下面我们根据图示再来看一下具体的步骤。
3.2 基本步骤和计算
3.2.1寻找确定传播源
在网格模型上寻找手臂上的任何一网格点或者特征网格点，即X值最大（左手臂）或者最小的网格点（右手臂），将其定为源传播点，如图4a所示：
（a） （b）
3.1.2 设置隔离区
按照人体的通常比例，将隔离板的起始高度设置在手肘的高度。这个时候我们可以看到隔离板将网格模型分割成了两个独立的部分，手臂部分和身体部分。如图4a，图4b中的蓝色线条（隔离板方程 Y + hElbow = 0，hElbow, height of elbow手肘的高度）。
3.1.3 应用传播算法
应用传播算法，统计被传染的网格点的数目nDiff（图4B中被打上粗斜线传染区内的网格点的数目），并记住被传染的网格点的范围。计算nDiff和隔离区内网格模型上所有网格点的数目nMesh的比例diffRatio =nDiff / nMesh * 100%。
如果该比例diffRatio远小于100%，说明手臂部分和身体部位还未连通，则将隔离区的高度上移一步后如图5所示：
（a） （b）
再计算nDiff和隔离区内模型上所有网格点的数目nMesh的比例diffRatio ，如此重复该步骤，直到diffRatio接近并等于100%。这说明隔离区内的手臂部分和身体部分有网格边线（edge）相连接，或者说这两部分相互连通了。
两部分相互连通的网格边线即是我们要找的腋窝部分如图6所示：
（a）第N-1次 （b）第N次
该次循环中3.1.2内设置的隔离板的高度就是腋窝部分的高度，腋窝的X位置则是上次循环中手臂部分的最小X值（左手）、或最大X值（右手）。这样腋窝部分就可以被定位了，有了腋窝的位置我们就能够比较容易的找到整个手臂部分。
4 案例及结果
该种方法已经应用于专业的三维人体测量建模软件中。该软件已经处理了近一万个三维人体网格模型，均能自动、准确、快速地找出手臂、腋窝、裤裆等部位的范围和尺寸。
下面以手臂为例，我们选取了3个较为典型的三维人体网格模型作为案例对象：
完整的网格模型
腋窝处缺损比较严重的网格模型
腋窝处有重叠部分的网格模型
应用传播算法寻找手臂部分后的结果，灰黑色的部分就是该方法自动找到的手臂的结果，如图7~图9所示：
（a） （b）
（c） （d）
（a） （b）
（c） （d）
图8 缺损比较严重模型对象，该网格模型共有13845个网格点，其中2113个网格点在手臂部分
（a） （b）
（c） （d）
从图中可以看到3个网格模型的手臂部分均被自动找到，且找到的位置也正确。
5 总结
本文提出了以传播算法寻找识别身体上特征点的方法，并付诸了实践。通过近一万个人体网格模型的验证，该方法能处理残缺的或者重叠的以及部分特殊的网格模型。且实现的方法相对简单，准确、效率也高。
本方法除了应用解决以上举例的三维人体网格模型的测量和建模过程中的问题外，也能够应用于其他方面，例如一些扫描所得的机器零部件的三维网格模型中的缺损、重叠等问题的解决。
参考文献：
[1] 余詠文,三维身体测量及合身裁剪服装[J].纺织学报,1999,20(3):156-159.
[2] 李勇，付小莉，尚会超. 三维人体测量方法的研究[J]，纺织学报, 2001,22(4): 261-263.
[3] 甘应进，陈东生，孟爽，白越.《非接触式三维人体计测现状》[J].纺织学报，2005年6月，第26卷第3期: 145-146
[4] Rusinkiewicz, S. and Levoy, M. 2000. QSplat: a multiresolution point rendering system for large meshes. In Siggraph 2000[C]. ACM , New York, NY, 343–352
[5] Colin Smith,On Vertex-Vertex Meshes and Their Use in Geometric and Biological Modeling,http://algorithmicbotany.org/papers/smithco.dis2006.pdf
[6] Tobler & Maierhofer, A Mesh Data Structure for Rendering and Subdivision. WSCG '2006: Short Papers Proceedings: The 14-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2006: University of West Bohemia, Plzen, Czech Republic, January 31 - February 2, 2006, p. 157-162.
[7] http://mathworld.wolfram.com/Plane.html
Body Part Recognition Method of 3D Human Polygon Meshes Based on Diffusion Algorithm
Chen Yu
(TPC (HK) Limited Technical Fashion Consultancy, Hongkong 999077, China)
Body parts recognition is very basic and important in the process of measuring and modeling 3D human polygon meshes. A Diffusion algorithm can distinguish body parts quickly and automatically. This method is not only simply to use but also can process raw polygon meshes.
Diffusion Algorithm; Body Parts Recognition; 3D Human Polygon Mesh;
章编号：1007-757X(2016)04-0071-03
TP311
A
（2015.09.07）
陈 郁（1977-），男，香港TPC(HK)三维软件开发公司，技术总监，法国里尔科技大学博士，研究方向：图像识别与处理，上海，200030
