方琦 孙光武 陈郁

摘 要：面向人体三维轮廓测量的凸包算法是确定服装截面围度尺寸的有效工具。为了减少耗时提高计算效率，引入了Quickhull凸包算法，根据人体具有20的凹凸对称性特征，在构建初始凸包前进行了对已知凹点直接删除的改进，并通过对女性最大胸围截面为例进行了说明，与Graham凸包算法精度和效率的比较，结果表明：采用Quickhull算法可获得与Graham算法相同的尺寸精度，但耗时明显减少，而通过对人体已知凹点的直接删除则可进一步减少计算的耗时。

关键词：人体围度;凸包算法;Quickhull算法

中图分类号： TS941.17

文献标志码：A

文章编号：1009-265X（2021）04-0081-05

Abstract： The convex hull algorithm for measuring the three-dimensional contour of human body is an effective tool to determine the size of the clothing section. In order to reduce time consumption and improve computational efficiency， this paper introduced the Quickhull convex hull algorithm. Before constructing the initial convex hull， the method of directly deleting the known concave points was improved according to the concave-convex symmetry of the human body. The method is illustrated by an example of the maximum female chest section. The result of comparison with the accuracy and efficiency of Graham convex hull algorithm showed that， Quickhull algorithm could be used to obtain the same dimensional accuracy as the Graham algorithm， while the time consumption of the Quickhull algorithm decreased significantly. The time consumption could be further reduced by directly deleting the known concave points of human body.

Key words： body girth; convex hull algorithm; Quickhull algorithm

準确的人体轮廓尺寸是服装设计的基础，对于服装的结构和号型确定，款式和穿着舒适度都极为重要[1-3]。这些如围度、高度和相应角度等必要的数据，传统上主要采用手工测量的方法获取[4]。随着科学技术的进步，三维扫描的测量方法得到发展并获得越来越多的应用[5-6]，与手工测量方法相比，这种非接触式的测量方法具有数据更多、尺寸更准和简便快捷的优势[7]。

非接触式的测量方法通过高精度扫描仪获得的人体点云数据还需要进一步采用凸包算法对围度尺寸加以确定。凸包算法是一种广泛用于图形处理方法，常用的有二等分法[8]、曲线定向法[9]、Graham算法[10]和Quickhull算法[11]等。目前服装业中应用的主要是Graham算法，这种方法在人体扫描获得的各截面点云数据基础上，通过对轮廓点单向递推和回溯的计算，逐步扣除凹点，最终获得可用于服装设计的各人体截面围度凸包[12-13]。这一算法虽然具有原理简单、结果准确的特点和优势，但却存在点云数据中凹点多时因回溯验证次数增加而耗时剧增的不足，特殊情况下甚至会出现为1个点的回归而对点集中近50%的点进行回溯处理的现象[14]。尽管已提出了如分区域删除非单调点等的改进，能够通过减少计算量而降低耗时，但回溯验证的次数仍然较多。

与Graham算法相比，Quickhull算法是一种更为高效和快捷的凸包计算方法，由于可以省去大量的回溯验证过程，以及在计算之前自动删除初始凸包中的冗余点，能够减少计算量从而降低耗时[15]。事实上，Quickhull算法得到许多工程应用[16-17]，更在图像处理[18]和模式识别[19]等领域起到重要作用，然而这一算法却较少在服装领域得到推广应用。本研究将把Quickhull凸包算法应用于服装领域，并基于人体对称性进行改进，可提高算法鲁棒性。

1 实 验

以女性的最大胸围横截面为例对Quickhull算法进行介绍，使用Human Solution的Vitus Smart XXL型号的三维人体扫描仪配合Anthroscan（Scanworx）数据处理软件获取人体点云数据，并手工测量其胸围、腰围和臀围。

1.1 坐标系建立

将扫描得到的女性三维人体点云置于三维直角坐标系中，Z轴为人体的高度方向，X和Y轴分别为人体的侧面和正面，三维坐标系的原点取在人体腰椎的肚脐平面上。图1示出了最大胸围处X-Y截面的轮廓点云，此轮廓图基本以Y轴对称。

1.2 搜索极值点并删除凹点

虽然基于Quickhull的基本算法可以建立多种多边形的初始凸包，考虑到四边形凸包有计算效率较高的优势[20]，本研究也采用四边形的初始凸包。在X-Y截面上，通过对轮廓点云数据的搜索和比较，分别在四个象限中各取一个最大Y值（或负Y值）的点作为极值点，如图2所示的A、B、C、D。虽然可以以这4个点建立的四边形初始凸包直接进行Quickhull的计算，但可以基于人体围度尺寸确定时内点的无效性而进行直接删除的改进。例如，在第I，Ⅱ象限内A、B两极值点均为乳凸点，其间的乳沟轮廓点都具有X的绝对值小于这两极点的特征，可简单地直接删除。同理，处于第Ⅲ，Ⅳ象限两背凸极点间的背沟点也可根据其X的绝对值小于C、D两极点的特征直接删除。图2示出了被删除点处于4个极点分别与X和Y轴所确定的矩形之中。由图2还可见，A、B两个极值点的Y值并不完全相同，C、D两个极值点的Y值也不相同。

1.3 建立初始凸包

连接A、B、C、D4个极值点获得一个乳沟点和背沟点均已被删除的四边形的初始凸包，如图3所示。显然，这一四边形的初始凸包具有上下两边基本平行于X轴的特征（因为乳凸点和背凸点存在很小的高低差）。由于四边形上下两条边（AB和CD）已无相应的外点，因而随后的凸包计算只需针对左右的AD和BC两条边的外点进行即可。

1.4 凸包计算和围度确定

如图4所示，采用由AD和BC两线段与所属各外点组成三角形，通过比较各三角形面积的方法分别确定出两个三角形面积最大的外点S1和S2。进一步以S1、S2和A、B、C、D4个极点连接，形成第一轮扩展的六边形凸包（圖4（a））。由此递归反复，直至用尽所有多边形凸包各边所属的外点，完成这一截面凸包的计算（图4（b）），这一凸包的周长即为该女性人体的胸围尺寸。同理，可分别计算出人体的各特征截面，如腰部（图5（a））、臀部（图5（b））的围度尺寸。对于要求高的服装可增加更多的特征截面围度尺寸计算。

2 结果与讨论

采用以上改进的Quickhull凸包算法能够与手工测量法和Graham扫描法获得相同水平的尺寸精度，但具有计算时间较短的优势，比较如下。

2.1 精度比较

表1列出了本研究算法与Graham扫描法和改进前的Quickhull算法及手工测量法对几个特征截面所得围度计算结果。由表1可见，这3种方法在特征截面所获得的围度尺寸基本相同，并一致于手工测量法，误差均小于0.5%。

在算法的精度方面，采集了22位女性的点云数据，将计算所得的三围尺寸与手工测量结果进行了对比，表2列出了它们之间的误差，可见，平均误差和最大误差均不超过国标GB/T 23698—2009《三维扫描人体测量方法的一般要求》中小于等于0.9 cm的要求，最大标准差值也低于一些报道[21]的0.21的值，体现了这一算法很好的鲁棒性。

2.2 耗时比较

对3种算法进行了耗时的实验比较，实验硬件为CPUIntel i7 8550U，RAM 8G，硬盘SSD-256G，显卡NVIDIA GeForce 940MX;操作系统Windows 10，编程软件Visual C++ 6.0。分别采用3种算法对由三维扫描仪获得的同一成年女性最大胸围截面进行了计算，图5示出了各算法耗时随点云数据数变化。

由图6可见，随着点云数量的增加各算法所耗的时间都呈现增加的趋势，其变化趋势与点云数N存在NlogN的关系。对比3种算法，Graham算法所需耗时多于Quickhull算法，对Quickhull进行改进后耗时还可减少。

已有的研究发现，Graham耗时较多的原因在于这种方法需做较多的回溯验证操作[15]。随着点云数量增加，回溯次数的比例也增加。表3比较了这种回溯次数的比例。对于Graham算法，当点云数据为149时，其回溯次数为75，回溯次数与点云数的比为75/149≈0.50，而当点云数据为1 269时，这一比值就增加至930/1 269≈0.73。回溯验证点的增加是由于扫描仪精度的提升后，人体表面细微的凹凸也被记录下来并需计算处理所致。在采用Quickhull算法时，由于无需对人体表面的细微凹凸做额外的回溯验证处理，耗时因而相应降低。在凸包建立前对凹点采用直接删除的改进措施后还可使Quickhull算法的耗时进一步减少。由图6可知，对于点云数据量为1 269时，改进的Quickhull算法可比Quickhull少用19.57%的时间，更可比Graham算法少用34.32%的时间。

实际上，采用对Quickhull算法在凸包建立前就对已知无效凹点直接删除的改进具有不误删有效点的优势，这种优势在耗时上对于凹点较多的胸部截面较为明显，可提高时间效率约17%，而对于腰臀部截面的计算耗时提高较少，为3%～5%。尽管如此，对于须进行大量计算的人体点云数据仍具有优势。

还需要说明的是，作为已在其他领域广泛应用的Quickhull算法具有较强鲁棒性[22-24]，而在删除已知凹点的改进中并不会降低这种凸包算法的鲁棒性，相反还会对其鲁棒性有一定的提高。

3 结 语

本研究将Quickhull算法拓展用于服装的人体尺寸围度确定，并根据人体尺寸特征进行了在基本凸包建立前对凹点直接删除的改进。对女性最大胸围截面的计算和比较表明：a），Quickhull算法与手工测量法和广泛Graham算法具有相同的尺寸精度;b）采用Quickhull算法可减少计算耗时;c）对凹点直接删除的改进更可进一步提高计算的时间效率。这种计算方法的推广将有助于促进服装设计和制作的数字化技术的发展。

参考文献：

[1]应欣，程碧莲，刘正，等.体表形态凸角对腰围间隙量的影响[J].纺织学报，2019，40（10）：152-157.

[2]徐继红，张文斌，肖平.人体与服装特征曲面间面积松量的影响因素[J].天津工业大学学报，2009，28（1）：27-32.

[3]LAGE A， ANCUTIENE K. Virtual try-on technologies in the clothing industry. Part 1： investigation of distance ease between body and garment[J]. Journal of the Textile Institute，2017，108（10）：1787-1793.

[4]KIM D E. Analysis of body shape and anthropometric measurements of US middle-aged women using 3D body scan data[J]. The Research Journal of the Costume Culture，2015，23（4）：726-736.

[5]BEZERRA G， CARVALHO M， ARAUJO A， et al.Analysis of body differences for the design of children's clothing[J]. IOP Conference Series Materials ence and Engineering，2018，459（1）：012073.

[6]YAN S， WIRTA J， KMRINEN J K. Anthropometric clothing measurements from 3D body scans[J]. Machine Vision and Applications，2020，31（1）：7.

[7]PARK S J， MIN S N， LEE H， et al. 3D hand anthro-pometry of korean teenagers and comparison with manual method[C]//International Conference on Human-Computer Interaction. Springer， Cham，2014：491-495.

[8]LINH N K. A convex Hull algorithm for solving a location problem[J]. RAIRO-Operations Research，2015，49（3）：589-600.

[9]AN P T. Method of orienting curves for determining the convex hull of a finite set of points in the plane[J]. Optimization，2010，59（2）：175-179.

[10]GRAHAM R L. An efficient algorithm for determining the convex hull of a finite planar set[J]. Information Processing Letters，1972，1（4）：73-82.

[11]SINGH N， ARYA R， AGRAWAL R K. A convex hull approach in conjunction with Gaussian mixture model for salient object detection[J]. Digital Signal Processing，2016，55：22-31.

[12]賴军.基于点云模型的人体尺寸自动提取方法[J].中南大学学报（自然科学版），2014（45）：2676-2683.

[13]葛宝臻，郭华婷，彭博，等.基于人体特征提取的模特体型尺寸自动测量方法[J].纺织学报，2012，33（4）：129-135.

[14]李晓志，李晓久，刘皓.基于人体截面点云的围度尺寸计算[J].纺织学报，2019，40（7）：128-132.

[15]CADENAS J O， MEGSON G M， LUENGO H C L， et al. Preconditioning 2D integer data for fast convex hull computations[J]. PLOS ONE，2016，11（3）：0149860.

[16]刘凯，夏苗，杨晓梅.一种平面点集的高效凸包算法[J].工程科学与技术，2017，49（5）：109-116.

[17]李必栋，闫浩文，王中辉，等.坐标排序的离散点凸包生成算法[J].测绘科学，2017，42（2）：14-17.

[18]NGUYEN L K， SONG C， RYU J， et al. QuickhullDisk： A faster convex hull algorithm for disks[J]. Applied Mathematics and Computation，2019，363：124626.

[19]LIU R， TANG Y Y， CHAN P P K. A fast convex hull algorithm inspired by human visual perception[J]. Multimedia Tools and Applications，2018，77（23）：31221-31237.

[20]陈明晶，方源敏，陈杰.初始凸包对改进快速凸包算法效率的影响[J].测绘科学，2016，41（7）：23-27.

[21]温佩芝，马超，胡俊榕，等.基于国家标准的三维扫描人体尺寸提取技术[J].计算机工程与科学，2014，36（6）：1114-1119.

[22]BARBER C B， DOBKIN D P， HUHDANPAA H. The quickhull algorithm for convex hulls[J]. ACM Transactions on Mathematical Software （TOMS），1996，22（4）：469-483.

[23]杨世伟.基于GPU的稀疏矩阵向量乘和凸包算法研究[D].南京：南京邮电大学，2019.

[24]武伟璐.基于快速凸包算法的4D航迹规划研究[D].天津：中国民航大学，2019.