一种针对3维人体冗余扫描模型的压缩方法

滕 毅,王若梅,焦 姣,马焯文,姜永生

(1.广东第二师范学院计算机学院,广东 广州 510303;2.中山大学计算机学院,广东 广州 510275;3.香港浸会大学许士芬博士体康研究中心,香港 999077)

0 引言

3维服装CAD设计、热功能性服装工程设计[1-2]、服装功效学[3]、虚拟试穿[4]和立体剪裁[5]的出现和不断发展,为服装设计提供了新的技术手段[6].热功能性服装工程设计是建立在3维人体模型的基础上,通过将热湿属性映射到3维人体表面,显示着装人体在运动过程中热湿状态的变化过程,从而进一步对着装人体的舒适度进行评价[1-2].在以上应用中,3维人体模型是关键的支持技术.3维人体模型是通过3维激光扫描技术,对人体进行全方位扫描获取的[7].随着3维扫描设备精度的不断提高,通过扫描设备所获取的3维点云数据也越来越多、越来越复杂,这给3维点云模型在网络资源有限的情况下,对其存储、传输、处理带来了较大困难,因此,关于3维点云数据的高效压缩编码方案一直被国内外学者广泛关注[8-9].为了满足热功能性服装工程设计的需要,本文提出了新颖的3维人体模型压缩算法对3维扫描人体模型进行压缩.首先应用2维轮廓关键点提取算法,采用区域覆盖和平滑处理方法分组提取在横截面上的轮廓关键点,再应用3维人体三角面片重构算法对压缩的顶点集重构3维人体模型.

1 相关工作

各个相关领域的国内外学者对点云数据精简问题进行了大量的研究,3维点云数据压缩主要有如下3种方法:(i)网格法.将空间点进行均匀小立方体划分,以每个小立方体的重心代替该立方体以达到精简点云的目的.刘佳[10]使用改进的3维栅格法做点云精简,针对人体点云数据的特点对数据进行分块稀疏变换,利用正交匹配追踪算法重建原始模型.杨焕宇[11]设计了重采样的改进的3维点云数据增强方法,利用k邻域以及相邻点的法向量夹角的计算对3维点云模型的数据进行采样,降低了单次迭代计算的数据量.黄承亮等[12]提出了2种数据压缩方法,分别为区域重心数据压缩法和基于3维TIN数据的共顶点数据压缩法.(ii)曲率法.该方法适用于表面曲率起伏较大的模型,根据表面曲率大小变化进行点云精简,但对于较平坦的模型数据,该方法会造成点云数据的大量缺失,难以保证模型特征细节[13].李金涛等[14]提出了一种基于曲率分级的点云数据压缩方法.该方法通过计算曲率反映点云数据中特征的分布情况,采用对数函数对归一化后的曲率值进行分级,对不同等级的点进行空间网格划分,再根据点的曲率等级实现点云的分级压缩.贾高杰等[15]提出基于八叉树均匀化的压缩算法.李订芳等[16]针对压缩感知模型,讨论了基于正则化的正交匹配追踪算法.王甲福等[17]提出了一种基于八叉树的k均值聚类点云精简算法.(iii)机器学习算法与传统的方法相结合的方法,该方法属于探索阶段.谢旻钊[18]提出了基于卷积神经网络的点云分类模型,使用特定的编码,将点云数据转化为矩阵,使得卷积神经网络可以处理点云数据.律帅[19]提出一种基于最小生成树的点云无损压缩算法,改进了传统最小生成树算法,根据点云等级和最大限制树长的组合对单元点云模型进行精简.以上算法是对3维点云模型进行处理.本文主要针对3维人体扫描数据进行处理,具有很明显的冗余扫描的特征,提出了一种专门针对3维人体冗余扫描模型的压缩算法.

2 3维人体文件压缩算法设计

2.1 问题与数据

本文的人体模型数据是利用美国TC2公司的3维无接触人体测量系统对真实人体(中国16～65岁女性志愿者)扫描生成的3维人体文件,同时记录了扫描人体对应的3维测量数据和人口统计信息(如年龄和身高).每个3维人体模型的原始数据是来自多台3维人体激光摄像机的多次扫描,并将重叠这些从不同角度获得的3维数据叠加生成3D身体表面,因此扫描的原始文件包含300 000～450 000个顶点和超过100 000个三角面片的身体模型文件.如图1所示,3维扫描人体表面由来自不同角度的相机生成7个3维人体表面组成,将这些3维表面重叠用以生成整个3维人体扫描文件,这导致占用大量的存储空间.

这些扫描的人体数据包含大量冗余数据,因此在工程项目应用这些扫描数据之前,必须先压缩再重构3维人体.先分析3维人体扫描文件的结构,该文件包含所有顶点和三角面片.如图2所示,3维扫描人体由12个部分组成(阿拉伯数字标记),每个部分都由顶点和三角形面片组成.以腿部为例(见图2(a)),同一高度的横截面由多层顶点环绕形成,而纵向横截面由三角形网格组成(见图2(b)).

图1 3维人体扫描文件表面构成示意图

图2 3维人体扫描模型构成图

2.2 算法总体架构

在分析3维人体模型结构后,设计了2维轮廓关键点提取算法和3维人体三角面片重构算法来压缩原始的3维人体扫描文件,3维人体扫描模型压缩算法的主要过程如图3所示.首先,将3维人体模型映射到3维空间坐标系中,在人体高度方向(z轴),由下至上按一定步长(dz)将人体模型做高度切分,切分后在每个单位高度上形成顶点集;然后,针对每个高度的每组顶点集采用2维轮廓关键点提取算法提取每层的关键轮廓顶点集并使其平滑,再用3维面片构建算法针对相邻层压缩后的顶点集进行3维三角面片的构造;最后,由简化后的顶点集和三角面片形成压缩后的3维人体模型.

2.3 2维轮廓关键点识别算法

设人体模型最初由n个顶点和m个三角面片组成.令Pi=(xi,yi,zi)为任意顶点,则在3维人体模型的横截面上所有顶点集表示为OLi={Pi|zi=h}.3维人体模型顶点集由所有横截面的顶点集组成,并描述为OC={OLi}.预先定义参数k,该参数表示要保留的分割顶点的层数.分割过程参考所有顶点集z坐标将人体模型在z轴方向上均匀地分为k层,分层的伪代码如算法1所示.

算法13维人体分层算法.

1)sort byzvalue;//将所有顶点按z值大小进行排序;

2)findz_max和z_min;//找最大的和最小的z值;

3)step size=(z_max-z_min)/k;//计算每层步长;

4)z_lower=z_min;

5)For (i=1;i≤k;i++);

6)z_upper=z_lower+step size;

7)for each verticej,ifz_jis in the range[z_lower,z_upper),include verticejto layerI;

8)z_lower=z_upper;

9)end for.

在分层后,将属于同一层的所有顶点投影到x-y平面系统,并识别在x-y平面系统中顶点的轮廓.不仅图层可能包含具有不同z值坐标的顶点,并且顶点可能会重复,而且几个顶点可能非常接近,这种情况会导致大量的冗余数据.由合并多个人体表面模型而导致的噪声或位移误差,使顶点集轮廓可能不够平滑. 因此,本文提出了一种2维压缩轮廓识别算法以克服这些问题,将平面数据压缩并重塑为平滑轮廓.算法的压缩示意图如图4所示.

图4 2维轮廓冗余压缩示意图

2维轮廓识别算法主要包含2个步骤:(i)将顶点分为s组,使每组由顶点集构成1～h层圈,每组都对应一个身体部位(如头、躯干、手臂或腿);(ii)用区域覆盖算法来识别一组顶点的关键点轮廓.如图5所示,将最邻近算法与区域覆盖法结合使用,得到压缩后的轮廓点.

图5 区域覆盖法

设采用区域覆盖法使用的矩形2条边长分别设置为L1、L2,包含的顶点集合记为G.起始顶点集合赋值为空,记为G:={}.假设轮廓现在在顶点(xi,yi)上追踪,然后尝试在G中包含(xi,yi),从而得出集合G′.若G′的长和宽均不大于L1和L2,则只需设置G:=G′,标记顶点(xi,yi)属于G,然后继续跟踪,否则,应将顶点(xi,yi)从当前覆盖范围中排除.将这些顶点包括在G中,以确定G的中心,这由Cr(G)=(avg{xi},avg{yi})给出.该中心也被视为轮廓上的关键点.设置G:={}并继续跟踪.

算法2轮廓关键点提取算法.

输入:n//单层顶点集顶点数量.

(xi,yi):coordinate of the vertex//顶点集坐标.

输出:C:contour//轮廓关键点集合.

1)setk:=1 andi:=1;

2)start from an upper most vertex (x0,y0) and mark (x0,y0);

3)setG={},rect_min_x:=rect_min;_y:=无穷大;rect_max_x:=rect_max;y:=无穷小;

4)find a vertex (xi,yi) which is closet to (xi-1,yi-1) and (xi,yi) has not yet been marked;

5)min_x:=min(rect_min_x,xi);max_x:=max(rect_max_x,xi);min_y:=min(rect_min_y,yi);max_y:=max(rect_max,yi);

6)if (i=n+1) or (perimeter of rectangle (min_x,min_y,max_x,max_y) is bigger thanL) then

7)G=G+(X,Y) only if (X,Y) is unmarked and lies in rectangle(rect_min_x,rect_min_y,rect_max_x,rect_max_y);

8)mark previous included vertex (x,y);

9)Ck:=Cr(G) andk:=k+1;

10)goto step 3;

11)else if

12)rect_min_x:=min_x;rect_ max_x:=max_x;rect_min_y:=min_y;rect_max_y:=max_y;

13)G:=G+(xi,yi);and mark (xi,yi);

14)end if

15)i:=i+1;

16)ifi≤nthen goto step 4;otherwise terminate the algorithm.

算法2提供了轮廓关键点提取算法,该算法与关键点提取结合在一起,应用矩形区域覆盖方法.需注意的是:算法(rect_min_x,rect_min_y)表示由G给出的矩形的左下角,(rect_max_x,rect_max_y)表示右上角.若包含新顶点,则可以立即更新矩形.

在获得轮廓后,将执行检测平滑过程以平滑轮廓.对于一般的人体模型,如图6所示,由3个相邻顶点产生的夹角记为∠ABC.若∠ABC过小,则该点人体模型会导致阴暗点.因此,本文提出针对3维人体表面阴暗点问题的轮廓平滑算法来处理该问题.表面平滑算法的基本思想是检测外轮廓点相邻的3个顶点连接后构成的角度范围,若夹角范围小于α,则用A点和C点的中心点替代B点.本文根据经验取α=120°.

图6 由相邻3个点组成的夹角示意图

使用1次平滑算法不一定能够消除所有的锐角,因为新加入的点与左右相邻的2个点形成的夹角也可能小于α,所以需要多次使用该平滑算法,直到所有相邻3个点的夹角均大于或等于α,这样就使该组顶点集平滑.如图7所示,在获得关键轮廓点之后,应用平滑算法的效果可以生成新的平滑的顶点集.

图7 平滑算法效果示意图

2.4 3维人体三角面片重构算法

在把人体模型每层的顶点集按照算法2处理完之后,完成了顶点集的压缩,为了生成压缩后的3维人体模型,还需要找到一种方法来构造三角面片将所有顶点连接起来.本文采用3维人体三角面片重构算法,通过顶点集构造3维三角面片连接相邻层每组顶点集,重新生成3维人体模型.该算法自下而上,由最底层的顶点集开始,分组构建三角面片连接最近2层顶点,在处理相邻2层顶点时,需要分为2层顶点总数相同和不相同2种情形来处理.算法3提供了适用于在相邻2层顶点数目相同的情况下构造三角面片的算法.

算法33维人体模型重构算法(适用于相邻的2个顶点层,且每层的顶点数目相同).

1)find the nearest two layers (i,j);

2)for (k=1,k≤ node number in layeri;i++);

3)pick the first vertexPkin the layeri,find the nearestPk+1 in layerj;

4)for all the nodes without noted,calculate the total distance toPk,andPk+1;

5)find the node with the shortest distance toPk,andPk+1,and noted it asPk+2.End for;

6)draw a triangle with nodesPk,Pk+1 andPk+2,and markedPk;

7)repeat and draw triangle with two nodes in layerj,and one node in layeri;

8)end for.

图8显示了在做好每层顶点压缩及平滑之后,3维人体模型采用算法3对3维人体顶点集构造三角面片将相邻的2层顶点集连接起来的过程. 首先,在第1层中任意选取一个顶点P1,并确定第2层中最近的P4.然后,计算除P1外的所有节点到P1和P4的距离,并标记最短距离点P2(第1层中的节点),将节点P1、P2和P4构造一个三角形,再标记节点P1并将节点P2和P4设置为基本节点;用相同的方法寻找P2和P4的最短距离的点,再确定第2层中的下一个节点以构造另一个三角形.最后,若2层具有相同数量的节点,则可以通过重复此过程来连接2层.

图8 三角面片构造示意图

算法43维人体模型重构算法(适用于相邻的2个顶点层,且每层的顶点数目不同).

1)find all the nodes without marked in Algorithm 3;

2)find two nodes and connect to the nearest node in the other layer;

3)construct triangle with the three nodes;

4)mark the two nodes,and find the next two nodes in the same layer;

5)repeat and draw triangles.

对于顶点数量不同的顶点集,采用算法4构建三角面片.最终,只需要从最底层到最高层根据相邻2层每组顶点集数量是否相同,有选择地采用算法3或算法4,就可以构建压缩后的3维人体模型.

3 实验

将该压缩算法应用于4个不同尺寸的3维人体扫描模型,并分析该算法的压缩效率.

如表1所示,压缩文件的顶点数急剧减少到原始文件的4.7%,压缩文件的三角形数量是原始文件的27%.此外,压缩后3维人体模型总文件大小约为原始扫描文件的10%.图9为原始扫描文件和压缩文件之间的文件大小比较结果.

表1 3维人模压缩算法效果统计表

图9 3维人体模型压缩前后文件大小对比

在对3维人体模型进行压缩之后,会担心压缩是否影响文件的呈现效果.图10显示了原始物体与重建物体之间的外观比较.确定3维人体模型的外部形状与原始模型几乎相同.压缩后3维人体模型的文件大小、顶点数量和三角形数量明显减少.压缩算法的压缩率均接近10%,压缩后的人体模型外观几乎与原始扫描的人体模型相同.这意味着该方法适用于处理冗余扫描,对叠加扫描导致的冗余特别有效.

原始图 压缩后

4 结论

本文提出一种新颖的针对3维人体冗余扫描模型的压缩算法,对在扫描过程中多个扫描曲面叠加产生的冗余效果较好.该算法首先应用2维轮廓关键点提取算法采用区域覆盖和平滑处理方法分组提取在横截面上的轮廓关键点,再应用3维人体三角面片重构算法对压缩的顶点集重构3维人体模型.实验结果表明:在保留人体扫描的轮廓特征的同时,压缩率约为10%,满足热功能性服装工程应用的需要.