虚拟试穿中的模型分割与碰撞检测

韩晓军，武嘉庆，王志宽

（天津工业大学 电子与信息工程学院，天津 300387）

关于三维服装的CAD设计有许多重大进展，但是CAD中虚拟试穿部分仍然存在问题，仿真的稳定性和速度都没有达到要求，性能与高效无法达到平衡.基于图像空间的碰撞检测算法[1]包括两类经典的算法：层级包围盒法与空间剖分法.空间剖分法[2]对同处于一个分割区域的对象进行检测.由于虚拟环境中物体数量增大，此类碰撞检测算法检测效率不高.层次包围盒算法[3]是用体积略大但几何特性简单的包围盒来替换复杂的几何对象，并通过构造层次包围盒树逼近真实物体，碰撞检测时通过遍历层次包围盒树来粗略地确定物体的相交状况[4].不少学者对传统的包围盒算法进行了改进，形成了双层树结构和分层树结构[5].双层树结构是在包围盒树的每个节点上构造双层结构，容易造成数据的冗余；分层树结构分别采用不同的包围盒，对不同类型包围盒间两两进行相交测试，计算开销很大，严重影响了碰撞检测的实时性.

为了克服上述碰撞检测算法效率低下的缺陷，本文提出基于纯粹的几何方法以解决模型碰撞问题，简化了几何位置点修正而产生的碰撞回响，不需要重新计算动态方程的碰撞模型也具有很好的稳定性；并提出一种三维人体模型区域生长的优化分割算法，使用椭圆体结构包围盒替换人体模型分割区域，提高了虚拟试穿过程中的碰撞检测效率，获得了满意的衣物虚拟试穿效果.

1 三维人体模型分割

本文使用的人体模型数据以点云或者表面网格的数据形式通过专业软件Makehuman获取.三维人体模型如图1所示.

图1 三维人体模型Fig.1 3D human body model

1.1 区域生长原理

区域生长的基本思想是将具有相似性质的像素集合起来构成区域.首先对每个需要分割的区域找一个种子点作为生长的起点，然后将种子点周围邻域中具有相同或相似性质的点合并到种子点所在的区域中，生成一个具有目标特征的区域[6].基于区域生长的方法对人体模型进行分割，将人体的骨骼信息作为分割最初的种子点.计算机动画里的骨骼通常定义为一组分层的骨架，制作标准的骨架需要20块骨头和与其相当数量的关节点[7].设计方案中，选取的种子点作为每块骨头的中心点，每个骨骼的信息都包括与其关联的骨骼和三维转换所需的位置、长度和方向信息.

第1阶段，种子点或者种子区域的选择以及阈值的设定.种子点位于待分割的区域内，由一个或者一系列体素点构成，同时建立一个空栈，并将种子点存入其中.

第2阶段，研究种子点邻域中尚未经过处理的体素点T，表示为

式中：N（x）表示点x的邻域；Ai表示被选取的种子点或者种子区域.按照相似性准则判断，将满足条件的体素归入栈中.相似性判据可表示为

式中：d（x，y）表示种子点x与待测体素点y之间的欧几里得距离；α为设定的阈值.将阈值参数化表示时，可将其表示为任一体素点与种子点欧几里得距离的值.设种子点所在骨骼为Bi，其长度为dBi，则α可表示为

第3阶段，随着迭代的进行，当模型内所有的体素都经过算法处理，则区域生长法结束.此时栈中所有体素构成的区域即为分割结果.

1.2 基于Span算法的模型分割实现

区域生长理论包括Floodfill（泛洪法）、Scanline（扫描法）、Span（区段法）3种算法.其中，Floodfill算法属于从图像中寻找连通区域的经典算法，其思路类似于洪水从一个区域扩散到所有都能到达的区域[8]，但它的分割效率较低.Scanline算法是Floodfill的改进算法，首先填充当前扫描线上的位于给定区域内的一个区段，然后确定与这一区段相邻的两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来.反复这个过程，直到所保存的各区段都填充完毕[9].

基于Span的算法本质思想和Scanline一样.Span即“区段”，表示图像上纵坐标相等的一段连续像素集合[10].其不同之处在于，基于Span的算法采用显式的区段数据结构作为填充和出入堆栈的单元，这样能够加快堆栈操作的效率，所以选择基于Span的算法来实现区域生长对人体模型的分割以提高时效.Span算法流程示意如图2所示.

图2 基于Span算法流程示意Fig.2 Span algorithm flow diagram

算法反复执行的操作步骤如下：①弹出区段；②区段伸展；③检查邻接区段并建立新区段入栈.循环一直持续到堆栈为空.

栈中已检测区段被弹出后，首先进行左右延伸到xleft和 xright；然后在延伸后形成的[xleft-xright，y]范围的上方区间[xleft-xright，y-1]进行考察，还要对 y+1、z-1、z+1方向区间进行考察；考察的过程中发现了3个新区段span1、span2和span3，将符合测度条件的区段压入堆栈.重复步骤（3），直至模型内没有未处理的区段.

在步骤（3）操作过程中，发现算法并不能避免重复检查已经访问过的或者已经被确认无所需点的区域，这样会导致一些无谓的计算.所以在原有的算法基础上，对每个访问过的区段都添加标记，这样可以有效地避开重复检查的情况.由此，在区段算法中，步骤（3）的操作每找到一个区段，就会为每个区段新建一个span结构，记录下其左右边界和Y坐标，同时对区段内的点做已访问标记，然后再推入堆栈.

新形成的span根据自己在区段 [xleft-xright，y-1]中的位置，赋予其4种标记：LeftRequired、Right Required、AllRez、UnRez.若产生新的span的左端接触左界，但右端不接触右界，这个span就属于Left Required；方向反过来的为RightRequired；两边都不接触左右界的为AllRez；两边都接触则为UnRez.

在定义了这些标记之后，根据不同的标记可以有效避开已经访问过的或者已经被确认无所需点的区域，避免了不必要的回溯，提高了算法的效率.

2 碰撞检测与响应

关于碰撞的检测和响应是非常重要的问题[11].一个粒子和一个对象之间的碰撞检测通常就是检测每个时间间隔中是否有碰撞发生[12].一旦检测到碰撞，响应的粒子的速度和加速度就会改变，以避免碰撞，这就需要重新计算动态方程[13-14].像这样的碰撞检测方案计算结果精确，但计算量巨大.为此，学者们提出了一些改进的方法，这些方法采用包围体来减少边界的交叉检测[15-16]，首先检测在边界的碰撞，然后检测粒子本身的碰撞[17].在此基础上，本文提出了更简洁有效的方法，利用椭圆体包围盒拟合人体模型分割区域，检测碰撞粒子是否在目标对象（椭圆体）里，如果在目标对象里面，粒子就会被移动到目标对象的表面，为了更简单和快速，粒子会从椭圆体的内部移动到正确的发生碰撞的椭圆体边界位置上.

当织物与环境中刚性物体发生碰撞时，两者之间接触产生摩擦，摩擦对于质点的运动速度起阻尼作用[18].假设质点P以速度v与物体在点Pc发生碰撞，物体表面在点Pc的单位法向量为n，可以将v分解为垂直于表面的速度vn和平行于表面的速度vt，即vn=（v·n）n，vt=v-vn.

设织物的摩擦系数为 Cf，如果‖vt‖≥Cf‖vn‖，质点会在物体表面上作水平摩擦运动，它的速度减小为

如果‖vt‖≥Cf‖vn‖，质点会在水平方向上保持静止.

摩擦系数Cf为织物的物理特性.当Cf=0时，质点会在物体表面上做无摩擦滑动；当Cf=∞时，质点在表面上不会滑动[19].

碰撞有两种形式：弹性碰撞和非弹性碰撞.弹性碰撞不会发生动能损失，将使质点以同样大小的速度沿相反方向运动，非弹性碰撞则会有动能的损失[20].为了增强仿真织物的真实性，采用非弹性碰撞响应，引入织物的反弹系数Cr（0≤Cr≤1），Cr的大小由织物的材料决定.不考虑摩擦因素，碰撞后质点的运动速度为

综上所述，质点P在碰撞前的速度为v，碰撞后的速度调整为

假设质点P以速度v从位置P0移动到P1，移动过程中与椭球O发生碰撞，如图3所示.

图3 点与椭圆体的碰撞Fig.3 Collision of point with ellipsoid

在检测到碰撞发生时，碰撞响应将需要强制修改质点位置为碰撞点位置.此处碰撞点位置是质点运动轨迹与椭球面的交点，需要求解非线性方程.为了简易处理，碰撞响应修改质点位置为P1在椭球表面上径向投影的位置，即将质点沿着P1和P0的连线方向移动到椭球表面，表示为

式中：Pc为质点调整后的位置.

根据方向P1P0，速度可以分解为平行于P1P0的方向vt和垂直于P1P0的方向vn，则有

将vt与vn的值分别代入式（6）可以得到碰撞后质点的运动速度.空间点与椭球体碰撞可能会发生的3种情况如图4所示.上述算法在只有一个椭圆体时可以实现预想结果.但是它不能在处理重叠层级的椭圆体时使粒子移动到正确的位置.

（1）第一种情况如图4蓝色所示，当检测到一个椭圆体的碰撞时，粒子被移动到椭圆体表面的位置，此时粒子和另一个椭圆体发生了碰撞，它又被移动到了第二个椭圆体表面的位置.然而，第二个椭圆体的部分在第一个椭圆体里，所以粒子在移动后有可能依然在第一个椭圆体内.

（2）第二种情况如图4绿色所示，粒子在2个或者更多椭圆体交叉的部分中.当依次对碰撞进行检测时，不同条件下的碰撞检测会生成不同的粒子正确的位置，这会造成系统的不稳定和混乱的结果.

图4 空间点与椭球体碰撞可能会发生的3种情况Fig.4 Three conditions may occur when space point collides with ellipsoid

（3）最后一种情况如图4所示橙色部分，粒子被准确地移动到了椭圆体表面.

为了解决以上问题，追踪了这些粒子位置和这些椭圆体表面的交叉部分的集合.不同于传统的对每个椭圆体的碰撞检测和响应方法，将碰撞处理过程分为2个独立的阶段：第1阶段，确定所有椭圆体上有碰撞的粒子，然后计算和记录每个碰撞点的位置；第2阶段，计算这些关联的点与点之间的距离，得到每一个碰撞点的起始位置A0，发生碰撞的位置在离A0最短的距离处.这种方法可以有效地使粒子远离椭圆体上的节点.碰撞检测和响应方法是纯粹的几何方法，比基于物理的方法更加有效率，避免了每个碰撞发生后动态方程都要重新修改和计算的问题.

3 分割算法的仿真模拟

实验模拟仿真选择在Open GL框架下，使用Visual Studio开发平台C#语言编程.人体模型是通过软件Makehuman获得的女孩模型，其中包含有15 976个顶点和不到30 000个三角形.分别对Floodfill算法、Scanline算法以及Span算法等3种实现区域生长分割三维人体模型的算法同时进行了测试与实验.根据人体的骨骼框架对三维人体模型进行了分割，并使用椭圆体来近似拟合人体模型的分割区域，实验结果如图5所示.

采用区域生长法分割人体模型的3种算法以及添加区段标记的Span算法对同一人体模型进行分割操作实验.通过在程序中插入计数变量记录下容器最大的容量，可以统计出相应的容器空间占有率比例，定义为容器的空间之和与图像空间的比值，测试结果如表1所示.

图5 三维人体模型的分割以及对分割区域的椭圆体近似拟合Fig.5 Segmentation result of 3D human model and approximate result of ellipsoid fitting in segmentation region

表1 不同算法的容器空间占有比例Tab.1 Ratio of container space in different algorithms

表1中的数值是按照计数变量所记录的容器最大元素容量乘以单位结构所占的字节数得到的，按照较小的空间占有计算（int16double，4字节），计算出的容器占空间大小是最小的可能情况.可以看出泛洪法的容器空间效率最差，1.98的数值说明假定输入模型为10 MB大小，则算法除了使用1 MB大小的标记表外，还需使用1.98×10 MB的内存用于存放算法执行中栈的最大扩张量.再考察其他方法的内存占用，发现其空间占用相比栈式泛洪法可忽略不计.

因为区域生长算法的效率很大程度上依赖于一些基本操作.为了对比这几种程序的效率，选择4个程序中的基本操作，包括对模型的GetPixel操作、对模型的CompPixel操作即对模型体素判定测度操作、对容器的Push和Pop操作，利用向算法运行的程序当中这些操作的位置添加计数变量，来统计这些操作的执行次数，并与结果点数相比，得出的测试结果如表2所示.表2中的算法运行时间不包含加载图像的时间，是准确的算法执行时间.所有的算法使用相同的标记表、容器等基本结构.算法运行时间的计算是“.NET运行库”中的System.Diagnotics.Stopwatch类完成的，算法运行经过多次重复，多次运行的时间和表中的时间均相差不超过2 ms，4种方法的运行时间充分说明了各自的执行效率.

由表2可以看出，扫描线算法相比于泛洪法，主要减少了对访问和对容器的操作，但同时增加了一部分对待测点的重复访问；原先的区段算法较扫描线法相比时间效率提高，但是仍然存在同样的问题；而本文提出的经过改进的区段算法，在区段算法的基础上进一步减少了对访问和对容器的操作时间，且避免了对待测模型的重复访问.从容器效率上来看，泛洪法与其他3种方法相比效率特别低；从时间效率上来看，扫描线法在访问与容器的操作上较泛洪法更有效，但是却增添了重复访问的问题，区段法在基本操作上较扫描线法时效更高，但是仍存在重复访问的问题.由此验证了本文提出的区段法优化算法无论从容器效率还是时间效率方面，都是实现区域生长的最佳三维人体分割算法.

表2 对不同算法程序的单元访问比例实验数据统计Tab.2 Experimental data of unit access ratio of different algorithms

4 虚拟试穿

虚拟试穿实验通过在采用Intel Core i7-4910处理器的PC机上对女性上衣、短裙以及长裤进行了模拟.图6所示为普通半袖与长裤的人体试穿效果，有3个方向的展示，分别为正面视角效果、侧面视角效果以及背面视角效果.

图6 普通半袖与长裤的人体试穿效果Fig.6 Virtual try-on of T-shirt and trousers

图7所示为立领上衣与百褶裙套装的人体试穿效果.

图7 立领上衣与百褶裙套装的人体试穿效果Fig.7 Virtual try-on of blouse and eight-panel skirt

由图6、图7可以看出，衣物试穿在人体模型上，可以很好地贴合在人体模型表面，衣物的碰撞处理效果与现实情况相近.在实时模拟中，通过记录的数据发现，碰撞处理速度与发生碰撞的质点数相关.表3总结了试穿过程中各不同衣物所需的碰撞处理用时.

表3 衣物试穿过程碰撞处理用时对比Tab.3 Comparison of collision treatment time in clothing fitting process

由表3可以看出，裤子的碰撞处理时间明显长于T恤和百褶裙，因为裤子与身体接触的面积更大，质点数量更多，需要处理的冲突碰撞的次数就更多.结果表明，本文方法能够较好地生成仿真模拟结果，效果逼真且鲁棒性好.同时由表3可以看出，与传统基于纯粹物理模型的碰撞检测与响应计算方法相比，本文方法运算时间减少了64%，具有一定的实时性.

5 结束语

采用基于Span的优化算法实现了由区域生长分割方法对人体模型的分割.使用椭圆体层级模拟模型，采用了基于几何位置的碰撞检测与响应计算方法，在保证计算结果准确的前提下，计算速度得到了很大的提升.由实验结果可以看出，相较于传统方法，本文方法在试穿过程中碰撞检测所用的时间非常短，具有很好的鲁棒性与实效性.但是还有一些问题尚待解决和完善，例如在整个系统中，衣物模型模块还需完善，目前主要模拟的是一些单薄的衣物，厚重服装如羽绒服、棉服等还需进一步研究效果良好的仿真方法；为了增加用户体验和结果能更符合用户要求，需增加用户交互模块等.