經編提花鞋材的自動排版及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.