经编提花鞋材的自动排版及CUDA的并行实现

吴妙缘 张爱军 张燕婷

摘要： 经编提花鞋材具有良好的性能，被广泛应用于运动鞋的鞋面。鞋材产品开发时为提高面料利用率工艺人员需对鞋材进行排版，但手工排版效率低下。为了实现经編提花鞋材的快速精准排版和提高面料的利用率，文章介绍了3种常见的鞋材排版方式，给出了基于边界碰撞检测的排版算法。根据排版算法可并行的特征，基于统一计算设备构架（CUDA）实现了算法。实验结果表明，CUDA并行处理的执行速度明显快于CPU串行处理，这一算法实现了鞋材排版的快速化与自动化，同时鞋材位置的精准放置也使织物利用率得到了提升。

关键词： 经编鞋材;贾卡提花;排版;面料利用率;并行算法;CUDA

中图分类号： TS943.68

文献标志码： A

文章编号： 1001-7003（2021）12-0126-07

引用页码： 121303

DOI： 10.3969/j.issn.1001-7003.2021.12.020（篇序）

Abstract： The warp-knitted jacquard shoe upper has been widely used in the upper of sports shoes due to its excellent performance. In order to improve fabric utilization during shoe product development， shoe upper layout needs to be conducted by technology personnel， but manual layout is inefficient. In order to achieve fast and accurate layout of warp-knitted jacquard shoe uppers and improve fabric utilization， three common shoe layout methods were introduced in this paper， and a layout algorithm based on boundary collision detection was provided. According to the parallel feature of the layout algorithm， the algorithm was implemented based on CUDA. The experiment results show that the speed of parallel execution of CUDA is significantly faster than that of CPU serial execution. The algorithm has realized the high-speed and intelligent layout of shoe uppers. At the same time， the precise placement of shoe upper has also improved fabric utilization.

Key words： warp-knitted shoe upper; jacquard; layout; fabric utilization; parallel algorithm; CUDA

经编提花鞋材是在带有贾卡装置的经编机上编织的一类织物，常用做运动鞋鞋面。经编提花鞋材具有丰富的花纹效应和良好的透气性，且生产效率高，因而占有较高的市场份额。在经编织物上，一幅布中会排列多个鞋面，合理地排列既可以节省原料，又可以提高编织效率。但在织物CAD中手动拖动鞋面进行排列的方式较为烦琐，因而需要研究计算机自动排列的算法。

目前在服装面料裁剪、板材加工等领域已有较多的排版算法研究。梁建军等[1]在关于服装CAD软件技术研究现状方面阐述了计算机辅助服装排料的3种方法，目前实用排料系统均采用自动排料与交互式排料相结合的方法;卓开霞[2]基于皮革服装CAD技术，采用QPSO算法模型，来对服装矩形样板的优化排样进行比较分析研究，该算法性能稳定，计算量较小，对不同灰度级范围的皮革面料图像处理非常适合，但存在材料利用率低的缺陷;汪朋朋等[3]给出一种基于最小重力势能原理与遗传算法的服装排料算法，利用遗传算法求解不同顺序下的排料结果，通过全局优化概率搜索来产生最佳排料顺序;肖友清等[4]则基于服装CAD的排版系统实现了碰撞检测，利用CRgn类中的函数来判断两个多边形即衣片是否相交，实现了使衣片排得紧密又不重合。以上研究有效提高了服装排料的自动化程度，但由于经编织物不能任意旋转图案，无法完全适用现有方法，所以本文研究了经编提花鞋材的排版方法，并基于统一计算设备构架（Computer Unified Device Architecture，CUDA）实现了算法。

1 经编提花鞋材的排列方式

最小势能法[3]等算法在排料时会对样片进行旋转、平移，使得材料的利用率达到最高。但在经编织物中，纱线总体沿纵向编织，横移仅在小范围内发生，因此旋转被排列的对象会改变织物的外观。图1（a）为原始意匠图，图1（b）（c）为旋转180°和90°后的意匠图。图1（d）—（f）分别为图1（a）—（c）垫纱效应图局部，三者在白色区域均通过贾卡偏移形成了网眼组织。但图1（d）—（e）的“A”中间的横杠由三个小网孔组成，而图1（f）中间的横杠则由一个纵向大网孔组成。因此，在实际生产时只可对鞋材做180°的旋转，以保证生产与原始效应相似的织物外观。其他角度的旋转会产生期望外的外观，通常不采用[5]。

基于以上分析，经编提花鞋材不具备各向同性的特征，排版时不能像其他材料为了提高利用率而进行任意角度的旋转，还应考虑各图案排列后效应是否与原图一致。结合编织工艺和后整理工序的要求，生產中常用的排版方法可分为3种：规则正排（图2（a）），交替正排（图2（b）），交替对排（图2（c））。如图2所示，规则正排的第一排为左脚鞋材，第二排为右脚鞋材，即每两排一个循环;交替正排与交替对排的第一、二排为左脚鞋材，第三、四排为右脚鞋材，即每四排一个循环。为了方便描述，本文将排列同只脚的鞋材定义为一行。

经编鞋材在编织时已确定好鞋码，织物尺寸的稳定性非常重要，而经编织物编织时会产生弓形斜，后整理时的张力也会引起线圈的倾斜。因而各工序需检查织物的倾斜情况并及时调整，以获得高品质织物。为方便观察，通常会在排列一定数量的鞋材之后插入一个不同组织的分隔区作为参考线，如图3（以规则正排为例）所示。

2 经编提花鞋材的面料利用率

面料利用率是指面料上鞋材区域面积占总面积的比例。鞋材排版的目的是获得较高的利用率，减少裁剪废料的面积。经编机较宽，通常多布幅同时编织。生产经编提花鞋材时，一幅布的幅宽是预先确定的常量，一般为1.2 m左右。为给工艺设计人员提供更直观的数据，本文不采用面积比率表示利用率，而是将480横列中的鞋材双数作为面料利用率高低的衡量依据，单位为双/腊克。在相同宽度的一幅布上，排列一定数量的同款鞋材，480横列中排列的鞋材越多则表明面料利用率越高，即可以用较少的横列编织较多的鞋材。鞋材在进行排版时，各个鞋材之间不宜相隔太近，否则会影响裁剪;也不宜相隔太远，否则会降低面料的利用率[6-8]。

式中：U表示面料的利用率，M表示一个高度循环中鞋子的双数，H表示一个高度循环中的横列数。

3 鞋材排版算法

鞋材的排列过程是不断调整待排列鞋样位置，使其最大程度靠近已排列鞋样，但不发生碰撞。本文的碰撞检测通过判断待排列鞋样的边界点是否位于已排列鞋样区域实现。

3.1 提取鞋材区域和边界

经编提花鞋材图案的设计采用意匠图进行绘制。通常情况下，一个意匠格表示一枚贾卡导纱针在两个横列中的动作。意匠图中0号色的意匠格为背景色，非0号色的部分为鞋材区域，可以对不同的色号定义动作，使其代表不同的组织结构。

绘制后的一只鞋为一个连通区域，使用扫描线填充算法可以提取出鞋材图案，同时获得鞋材的边界点。为了方便后续算法的实现，将边界点按行优先排列存储，同时保存每个边界点的边界特征[9]。记录边界点的特征时，将被记录的边界点作为参考点，用一个字节记录参考点周围8个意匠格是否为0号色，字节中每一位代表的值如图4（a）所示。图4（b）为意匠图中左下角两个边界点的特征值，分别为0XE9和0XF0。多数鞋的左右脚是对称的，因此只需要提取一只鞋的区域和边界即可。

3.2 鞋材排列的流程

为方便成品的裁剪，鞋材在排列时相邻的鞋材之间要间隔指定针数和横列数。用Wdis表示鞋材之间最小间隔针数，常规情况下，工艺中一个意匠格表示两个横列，如下式所示：

3.2.1 规则正排的排列流程

在规则正排的排列方式中，第一排放置左脚鞋材，第二排放置右脚鞋材，则每一排鞋材数量为：

鞋材的放置位置用鞋材最小外接矩形左下角意匠格在意匠图上的位置表示。第一排鞋材放置在意匠图上第一行，第二排鞋材放置的位置则需要通过计算得到。鞋材排放的具体流程为：先放置好第一排的鞋材，第二排的鞋材在第一排的基础上采用碰撞检测的方法对其边界点逐一进行判断，检测到碰撞后则将第二排鞋材向上移动一行，直到找到与第一排距离最近且不发生碰撞即为最佳的放置位置，如图6所示。

图6中，碰撞检测即为检查第二排鞋材各边界点与第一排鞋材的距离是否满足最小间隔针数和最小意匠格数的要求。本文通过对第一排鞋材进行膨胀预处理代替距离的计算，第二排鞋材的边界点位置如存在膨胀后第一排鞋材的意匠格，则表明发生了碰撞。

膨胀处理使用菱形结构，菱形的水平对角线长度为2Wdis+1，垂直对角线高度为2Hdis+1。图7为两种不同Wdis和Hdis构成的膨胀结构。膨胀在第3.1节获得的第一排鞋材边界点上进行，逐边界点生成膨胀边缘。

图8（a）为膨胀前的第一排鞋材，图8（b）为膨胀边界和原鞋材的并集。碰撞检测时只需要判断第二排的边界点是否与图8（b）重叠即可，不需计算距离。为了减少工作量提高效率，在对鞋材的边界进行膨胀时，对其边界的第一点进行膨胀后，在后续的操作中仅需对与前一边界点操作中的不重复部分进行填充即可[10]。

3.2.2 交替正排与交替对排的排列流程

交替正排和交替对排算法基本一致，区别在于交替对排中第二排和第四排的鞋材需要旋转180°。交替正排和交替对排均需要分为排列数量为奇数双鞋和偶数双鞋两种情况。当排列鞋材的数量为奇数双鞋时，第一排相邻两只鞋之间横向允许的最大间隔距离为：

此种情况下，第一排相邻鞋子按最大距离Xdis排放，则第二排横向可移动范围E=Wshoe+Xdis。由此可得第二排鞋材的放置流程为：首先放置在第一行第一列的意匠格，如有碰撞则继续检查第一行第二列，如不发生碰撞则为可放置的位置，具体流程与图6类似，但放置位置除了在纵向上移动，还需范围E内横向移动搜索，直到找到不发生碰撞的位置为止（图9），此时高度H为排下两排鞋材所占用的最小高度。

当排列鞋材数量为偶数双鞋时，第一排鞋子以最大间隔距离放置不一定是最优解，因此应对每种允许的间隔距离做一次排版运算，选取面料利用率最高的。对某一种间隔距离，第二排鞋横向可移动范围为：

偶数双鞋排版时，除第二排鞋可以横向移动外，第一排鞋也可以在范围E内横向移动、即第一排的第一只鞋可以不贴近布边放置。故在排版时存在三个移动，第一排鞋的横向移动、第二排鞋的横向移动和第二排鞋的纵向移动。给定鞋材双数后，最多存在T种放置情况：

由式（6）可知，在偶数双鞋交替排列时，时间复杂度较高，这是因为鞋材在移动范围E中，上下两排鞋材会重复出现很多次相对位置相同的情况。例如图11（a）（b）移动了不同的距离即S1与S2不相等，但是鞋材的相对位置没有发生改变，它们的计算结果是相同的，即若图11（a）不满足排版要求则图11（b）同样不满足。

这种情况增加了碰撞检测的次数，若所有相对位置相同的情况都只需执行一次检测，省掉重复操作会大大提升鞋材排版的效率。图11（c）的方法可以解决这一问题，将布幅宽度增加E，第一排的鞋材固定在布面中间，第二排鞋的移动范围变为2E，可以得到最多有种情况，明显少于式（6）得到的情况。按下式计算完成后，根据第一、二排鞋材的位置从布幅两侧减掉宽度E。

在第一排和第二排的左脚鞋材排列好后，水平翻转即得到第三排和第四排的右脚鞋材。将第一、二排和第二、四排分别作为整体，与上述类似的方法执行碰撞检测，可得到两行鞋的放置位置。如果在一个循环中有更多行鞋，则可以按同样的方法处理。

因为同一排中的鞋材之间的距离总是相等的，所以当一排的鞋多于2只时，可以省略掉中间的，只取最左和最右的鞋材进行计算，从而减少运算量。计算过程中，意匠图某一行上多个意匠格位置都能够放置第二排的鞋材时，应使第二排鞋与第一排左右尽可能等间距，从而使鞋材在布面上排列整体更均匀，有利于送经量的调节，提高布面质量。

4 排列算法的并行实现

在鞋材排列算法中，为找到最高利用率的排列方式，每一种放置鞋材的位置都要进行一遍碰撞检测，计算量大。分析可知，某一放置位置的检测与其他位置无关，某一边界点的碰撞检测与其他边界点无关，因而可以方便地进行并行实现。

并行处理是相对于串行处理，是指用多个计算资源来协同解决同一个计算问题，该问题被分解成若干个部分，可以同时进行处理。每部分都用一系列指令来完成，每部分在不同处理器上同时执行。它的目的是提高计算速度，将复杂任务进行拆分，从而来提高解决问题的效率[10]。本文针对鞋材排版问题进行并行计算的设计，确保运行的流畅和效率。

并行算法基于英伟达公司的通用并行计算架构CUDA实现，它借助GPU解决大规模的计算问题。CUDA是层次化线程的集合，可以实现存储共享和数据同步进行[11]。CUDA的最小执行单位是线程thread，若干个线程组成了线程块block，若干个线程块又组成了线程网格grid。基于GPU上的CUDA执行命令的函数称为核函数kernel[12]。在每个核函数中包含了两个并行层次即各线程块之间的并行和各线程之间的并行，当核函数进行并行计算时，线程网格上的线程块都使用不同的数据来计算同一指令[13]。若将鞋材排版中的碰撞检测这一过程视为核函数，则核函数如下：

__global__ void detectKernel （…）

{

int y = threadIdx.x;

//在较低意匠行上已有可放置位置，结束线程

if （y > selY） return;

int x = blockIdx.x;

//遍历边界点，检查是否与已排的鞋相撞

for （int p = 0; p < borderPtNum; p++）

{

int posX = x + borderPt[p].x;

int posY = y + borderPt[p].y;

if （bgColor[posX *paperHeight + posY]！= 0）

return;

}

//将当前意匠格置为可放置位置

placeFlag[y*E + x] = 1;

atomicMin（&selY， y）;

}

用detectKernel <<< 2*E， Hshoe+Hdis>>>（…）調用核函数，block数量取为3.2节中2E的大小，每个block中的线程thread数量为Hshoe+Hdis。为使线程能够连续读取global memory中的数据，bgColor以列优先方式存储。因为并行线程同步执行，不能确定哪一个先执行完成，当在意匠图的某一行上取得了可放置位置，应设置一个状态标志，以便高于该行的线程能快速退出工作。CUDA的atomicMin可在一次原子事务中读取存储器地址中的值，与输入值比较，将较小的值存入存储器地址。本文使用这一原子操作将状态标志设置为较低的意匠行。经编提花鞋材意匠高度通常在1 200以内，宽度在500以内，所以边界点数据borderPt大小不超过64 kB，能够存储在GPU中的constant memory中，有利于提高读取速度。

5 结果与分析

本文实验平台硬件环境为英特尔公司发布的Intel Core I7-6700HQ和英伟达公司发布的NVIDIA Quadro M1000M;软件环境为Windows 10，CUDA 10.0。选用的经编机机宽为140英寸（约为355.6 cm），机号为E24，编织幅数为3幅，布边宽度为40针。通过计算可得，每幅布为1 120针，鞋材放置区域可用针数为1 040针。

设置鞋材之间的最小间隔参数，左右最小针数Wdis为10，上下相隔意匠格数Hdis为10。图12、图13是两个实例的排版结果。表1为常规鞋材A，意匠图宽230格，高234格。表2为倾斜鞋材B，意匠图宽209格，高475格。

表1、表2列出了各排版方式的利用率，观察数据可以得出，利用率最高的分别为A-i和B-f。若以最容易手工排版的规则正排为参考标准，A-i的利用率提高了4%，B-f的利用率提高了23%。表1中A-b、A-c、A-d、A-f、A-g和表2中B-b、B-c、B-d的利用率比规则正排低，由此可见交替正排和交替对排不总是优于规则正排。

表3为本文算法的3个应用实例，展示了不同形状鞋材的排版结果。

实例1交替对排的利用率比规则正排提高了8.9%，实例2交替正排的利用率比规则正排提高了6.4%，实例3交替对排的利用率比规则正排提高了25%。实验结果表明，通常情况下规则正排并不是最优的排列方法，根据鞋材的形状交替正排与交替对排或成为最优的排列方法，使得布料的利用率达到最高。

表4为相同的排版方法使用CPU单线程实现和使用CUDA实现的耗时对比。不同形状和大小的鞋材排版时耗时不同，从表4可知，鞋材B的耗时总体大于A。在单线程实现时排版B比排版A多耗时8秒，但并行实现时因为主要的计算可由GPU加速，所以增加的时间不多。从表4还可发现，CUDA实现时，核函数实际耗时较少，而大部分的时间消耗在数据的准备和传输过程中。

6 结 论

本文介绍了经编提花鞋材的排版方法，给出了规则正排、交替正排和交替对排的算法流程。通过CUDA并行化，提高了经编提花鞋材排版时的执行效率，实现了排版的自动化，通过程序计算得到鞋材精确的放置位置提高了织物原料的利用率。基于经编提花鞋材的特点，本文以两款鞋材为例，经过实验得出，鞋材大小、排列方法等因素都会影响最终利用率。规则正排不一定是最优的排版方法，但其他两种方法也不总优于规则正排，实际生产中应根据具体情况来选择排版方法。

本文实现的排版算法在企业应用后发现，在一些情况下，因鞋材放置组合很多，仍然需要消耗数秒才能执行完成，因此后续需要进一步来优化算法，减少用户的等待时间，提升使用体验。

参考文献：

[1]梁建军， 冯毅力， 李汝勤. 服装CAD技术研究的现状与方向[J]. 纺织学报， 2003， 24（6）： 104-106.

LIANG Jianjun， FENG Yili， LI Ruqin. Clothing CAD technology research status and direction[J]. Journal of Textile Research， 2003， 24（6）： 104-106.

[2]卓开霞. 皮革服装 CAD 矩形件样板的优化排样探究[J]. 皮革科学与工程， 2019（3）： 74-79.

ZHUO Kaixia. Research on the optimal layout of leather garment CAD rectangular parts[J]. Leather Science and Engineering， 2019（3）： 74-79.

[3]汪朋朋， 施群， 谢云斌， 等. 基于最小重力势能原理与遗传算法的服装排料算法[J]. 现代纺织技术， 2018， 26（3）： 53-61.

WANG Pengpeng， SHI Qun， XIE Yunbin， et al. Garment discharge algorithm based on minimum gravitational potential energy principle and genetic algorithm[J]. Advanced Textile Technology， 2018， 26（3）： 53-61.

[4]肖友清， 高成英， 王栋. 碰撞检测在服装CAD排版系统中的实现[J]. 现代计算机， 2001（9）： 93-96.

XIAO Youqing， GAO Chengying， WANG Dong. Realization of collision detection in garment CAD layout system[J]. Modern Computer， 2001（9）： 93-96.

[5]高雅， 蒋高明， 张爱军， 等. 双针床纱架贾卡鞋材的设计与仿真[J]. 丝绸， 2020， 57（3）： 113-117.

GAO Ya， JIANG Gaoming， ZHANG Aijun， et al. Design and simulation of Jaka shoes with double needle bed frame[J]. Journal of Silk， 2020， 57（3）： 113-117.

[6]萬志琴. 服装批量定制中面料利用率与省布率的关系[J]. 纺织学报， 2005， 26（4）： 124-125.

WAN Zhiqin. Relationship between fabric utilization rate and cloth saving rate in garment mass customization[J]. Journal of Textile Research， 2005， 26（4）： 124-125.

[7]陈梦佳， 蒋高明， 张燕婷， 等. 经编鞋材的双色贾卡提花工艺研究[J]. 现代纺织技术， 2020， 28（1）： 36-41.

CHEN Mengjia， JIANG Gaoming， ZHANG Yanting， et al. Study on two-color jacquard processes for wrap-knitting shoe fabric[J]. Advanced Textile Technology， 2020， 28（1）： 36-41.

[8]张家琪， 夏风林. 经编双贾卡提花间隔鞋材生产工艺[J]. 现代纺织技术， 2019， 27（4）： 28-32.

ZHANG Jiaqi， XIA Fenglin. Manufacturing technology of vamp material by warp knitted double jacquard spacing fabrics[J]. Advanced Textile Technology， 2019， 27（4）： 28-32.

[9]鄧仕超， 黄寅. 二值图像膨胀腐蚀的快速算法[J]. 计算机工程与应用， 2017， 53（5）： 207-211.

DENG Shichao， HUANG Yin. The fast algorithm of binary image expansion corrosion[J]. Computer Engineering and Applications， 2017， 53（5）： 207-211.

[10]曾浩洋， 张红英. 天空区域分割的图像去雾及CUDA并行实现[J]. 小型微型计算机系统， 2019， 40（3）： 655-659.

ZENG Haoyang， ZHANG Hongying. Image defogging and CUDA parallel implementation of sky region segmentation[J]. Journal of Chinese Computer Systems， 2019， 40（3）： 655-659.

[11]李建江， 张磊， 李兴钢， 等. CUDA架构下的灰度图像匹配并行算法[J]. 电子科技大学学报， 2012， 41（1）： 110-113.

LI Jianjiang， ZHANG Lei， LI Xinggang， et al. Parallel gray image matching algorithm under CUDA architecture[J]. Journal of University of Electronic Science and Technology of China， 2012， 41（1）： 110-113.

[12]LI Dong， HUANG Shaohui， HUANG Xiaoyang， et al. An improved fuzzy connected image segmentation method base on CUDA[J]. Journal of Computer-Aided Design & Computer Graphics， 2016， 28（2）： 295-300.

[13]XUE Y， REN J， SU H， et al. Parallel implementation and optimization of haze removal using dark channel prior based on CUDA[J]. Communications in Computer & Information Science， 2013， 207（1）： 99-109.