徐云云+江玉清

摘 要： 服裝排料是將衣片在滿足一定約束下，將衣片盡量緊湊地排放在布料上。衣片多邊形是排料算法的基本輸入對(duì)象，工業(yè)上通常從PLT文件中獲得衣片多邊形信息。PLT文件是一個(gè)面向打印機(jī)的繪圖文件，常在服裝排料中得到應(yīng)用，但它僅包含打印機(jī)的動(dòng)作信息，沒有衣片信息。因此提出一種面向服裝排料的自動(dòng)衣片多邊形算法研究，根據(jù)PLT文件構(gòu)造圖G=（V，E），對(duì)圖中的環(huán)進(jìn)行提取過濾，得到衣片的邊緣邊框，最后尋找衣片的附加信息。通過上述方法最終實(shí)現(xiàn)了衣片及其附加信息的提取。

關(guān)鍵詞： 服裝排料系統(tǒng)； 衣片樣板； 深度遍歷； 最短路徑； Floyed算法

中圖分類號(hào)： TN919?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）16?0084?04

Research on polygon extraction algorithm of automatic apparel pieces for

apparel marking

XU Yunyun， JIANG Yuqing

（VCC Division， School of Computer and Information， Hefei University of Technology， Hefei 230009， China）

Abstract： The apparel marking is to put the apparel pieces as compactly as possible in the layout space under a certain constraint. Polygon of apparel pieces is a basic input object of apparel marking algorithm. In the field of industry， the polygon information apparel pieces is usually got from PLT file which is a drawing file for the printer and is often applied to the apparel marking， but it only contains the operation information of printer and has no information of apparel pieces. A polygon algorithm for automatic apparel pieces of the apparel marking is proposed in this paper. The graph G = （V， E） is structured according to the PLT file， and then the ring in the graph is extracted and filtered to get the edge border of apparel piece and search for the additional information of apparel piece. With the method mentioned above， the goal to extract the apparel piece information and its additional information was achieved.

Keywords： apparel marking system； apparel piece pattern； depth traversal； shortest Path； Floyed algorithm

0 引 言

服裝排料又稱排版，是指將服裝的衣片樣板在規(guī)定的面料幅寬內(nèi)合理排放的過程[1?2]，即將紙樣依工藝要求（正反面，倒順向，對(duì)條、格、花等）形成能緊密嚙合的不同形狀的排列組合，以期望使用布料利用率最大化，達(dá)到降低產(chǎn)品成本的目的。衣片是一款衣服上的一塊面片，通過打板系統(tǒng)[3]構(gòu)造出來，為了方便服裝的生產(chǎn)。

PLT文件是利用HPGL（Hewlett Packard Graphics Language）[4?5]語言模擬繪圖操作，用戶可以快捷地得到圖形的矢量信息，準(zhǔn)確地解析PLT文件是一項(xiàng)基礎(chǔ)卻很重要的任務(wù)。PLT文件由于其獨(dú)特的優(yōu)點(diǎn)：文件指令豐富、易于讀/寫、構(gòu)圖靈活性較大、設(shè)備之間的兼容性強(qiáng)、內(nèi)存占用較少、輸入/輸出調(diào)用效率高等，越來越受到工業(yè)界的歡迎，成為工業(yè)服裝排料的主要輸入文件之一。

在服裝排料的過程中以衣片為對(duì)象進(jìn)行排放[6?7]，那么能否正確從排料輸入文件中提取出衣片將直接影響最終的排料結(jié)果。鑒于此，本文提出了一種能夠快速高效的提取PLT中衣片樣板的方法，詳細(xì)說明了其實(shí)現(xiàn)過程，并給出了其基本實(shí)現(xiàn)方法。

1 問題分析

排料系統(tǒng)的PLT文件由衣片信息組成，其中衣片信息主要由2個(gè)部分組成：衣片的邊緣邊框和衣片的說明信息。具有以下特點(diǎn)：

（1） 封閉性：衣片樣板的邊緣為封閉的閉合曲線，由一系列的頂點(diǎn)構(gòu)成，如圖1所示的衣片起邊緣邊框均是封閉的。

圖1 褲子款式中的部分衣片

（2） 不包含性：所有的衣片之間不存在相互包含的情況，即一個(gè)衣片不可能存在于另一個(gè)衣片的內(nèi)部。

（3） 其他信息：每個(gè)衣片有其所屬的附加信息且位于衣片的內(nèi)部，這些信息說明衣片的尺寸以及名稱，如圖2所示，衣片和其附加信息均為于邊框內(nèi)部。

圖2 衣片與其說明信息之間的關(guān)系

上述衣片的特點(diǎn)可以作為尋找衣片的有力根據(jù)，下文中關(guān)于衣片提取的具體方法就是基于衣片此3個(gè)特點(diǎn)展開的。

2 衣片自動(dòng)提取方法

根據(jù)上文對(duì)PLT文件中衣片的特點(diǎn)分析，本文歸結(jié)出找出衣片樣板的一般性方法。衣片樣板由最外層邊緣閉合曲線和內(nèi)部的文字說明信息構(gòu)成。所以本文提出首先找出衣片樣板中的所有環(huán)，由于得到的環(huán)只是衣片的候選項(xiàng)，可能存在非法環(huán)的現(xiàn)象，所以需要對(duì)所有環(huán)進(jìn)行過濾處理，得到所有衣片樣板的邊緣邊框。最后找出衣片的所有衣片的附加信息。上述方法的關(guān)鍵在于尋找衣片的邊緣邊框，即尋找環(huán)的問題。對(duì)于一個(gè)圖G=（V，E），可以利用深度遍歷算法[8]快速找出其中所包含的環(huán)。由上述PLT文件特點(diǎn)，可以在初步提取出PLT文件中邊的信息后，構(gòu)造出圖的數(shù)據(jù)結(jié)構(gòu)。根據(jù)以上分析，本文提出首先根據(jù)PLT文件快速構(gòu)圖，然后對(duì)生成的圖的數(shù)據(jù)結(jié)構(gòu)采用深度遍歷算法獲得圖中的所有環(huán)，進(jìn)而對(duì)所得環(huán)進(jìn)行過濾處理，最后尋找衣片文字說明信息的一般性方法。具體實(shí)現(xiàn)流程如圖3所示。

2.1 由PLT文件構(gòu)圖

通過對(duì)樣板衣片的PLT文件測試可知，文件具有頂點(diǎn)多，頂點(diǎn)之間的關(guān)聯(lián)度小的特點(diǎn)，屬于稀疏圖。所以本文提出的方法采用鄰接表的數(shù)據(jù)結(jié)構(gòu)保存圖的信息，以節(jié)省空間。

圖3 尋找衣片樣板的工作流程

在將PLT文件構(gòu)成圖G=（V，E）時(shí)，對(duì)PLT文件中的每一個(gè)點(diǎn)將對(duì)應(yīng)于圖G中的一個(gè)頂點(diǎn)，對(duì)PLT文件中由指令之間的組合所構(gòu)成的邊將看作圖G中的一條邊，經(jīng)過對(duì)PLT文件進(jìn)行解析處理便可得到圖的數(shù)據(jù)結(jié)構(gòu)G=（V，E），下面以此作為對(duì)象，展開環(huán)的提取操作。

2.2 衣片樣板的提取

按照前文提出的總體方針，關(guān)于衣片樣板的提取，主要分為2步實(shí)現(xiàn)：首先提取出圖中的所有環(huán)路；其次對(duì)所得的所有環(huán)路進(jìn)行過濾，排除掉不是衣片邊緣邊框的非法環(huán)路，并加以處理。其中第1步可以通過改進(jìn)的深度遍歷算法實(shí)現(xiàn)。第2步實(shí)現(xiàn)后得到的所有環(huán)路中的非法環(huán)路可分為以下2種情況：

（1） 附加信息中的環(huán)路，例如：“0”；

（2） 如圖4所示的2個(gè)衣片邊緣邊框相接的情況，即實(shí)際abcg和cdef分別為兩個(gè)衣片，但在尋找環(huán)的過程中按照abcdefcg的順序得到了非法環(huán)路。

圖4 兩個(gè)邊緣邊框相接的非法衣片

在算法實(shí)現(xiàn)上前面第1步采用深度遍歷算法實(shí)現(xiàn)，第2步采用Floyed處理非法環(huán)，由文獻(xiàn)[9]可知Floyed算法同樣可以用來尋找圖中的環(huán)路。本文之所以在第1步中利用深度遍歷，而在第2步中采用Floyed算法，是因?yàn)镕loyed算法處理的時(shí)間復(fù)雜度遠(yuǎn)大于深度遍歷，特別是在像PLT文件數(shù)據(jù)量大的情況下更為明顯。所以首先使用深度遍歷實(shí)現(xiàn)，而第2步對(duì)部分環(huán)過濾處理時(shí)針對(duì)圖4所示的情況只是少數(shù)現(xiàn)象，采用Floyed算法在整體時(shí)間上影響不會(huì)很大。

2.2.1 衣片的初提取

本文采用改進(jìn)的深度遍歷算法，即：以某點(diǎn)為起點(diǎn)的深度序列中，當(dāng)訪問到某點(diǎn)與第一個(gè)點(diǎn)相同時(shí)，且該序列中頂點(diǎn)的個(gè)數(shù)大于2的時(shí)候，即找到了環(huán)。由于根據(jù)PLT文件生成的圖的連通分量可能不止一個(gè)，需要多次采用深度遍歷。在深度遍歷的過程中需要利用以下數(shù)據(jù)結(jié)構(gòu)對(duì)訪問過程中的信息進(jìn)行保存。其中利用棧的結(jié)構(gòu)，存放每次訪問到的頂點(diǎn)。采用容器結(jié)構(gòu)，存放訪問過的邊，在尋找環(huán)失敗的時(shí)候利用其還原圖中相關(guān)點(diǎn)的度的信息和其邊的訪問信息。

（1） 從圖的數(shù)據(jù)結(jié)構(gòu)的頂點(diǎn)表的第一個(gè)節(jié)點(diǎn)開始，依次向后遍歷，當(dāng)頂點(diǎn)v0的度數(shù)大于1的時(shí)候，則以該頂點(diǎn)為起點(diǎn)進(jìn)行深度遍歷；當(dāng)完成所有頂點(diǎn)的遍歷之后，算法結(jié)束。

（2） 從圖中某個(gè)頂點(diǎn)x出發(fā)，首先訪問x，將x頂點(diǎn)的度減1。找出x頂點(diǎn)的第一個(gè)未被訪問的相鄰邊，將該邊的訪問位置true；由于在無向圖的鄰接表中，一條邊存在于兩個(gè)頂點(diǎn)的邊表中，需要將該邊所指向點(diǎn)的度數(shù)減1，同時(shí)將該頂點(diǎn)中指向x的邊的訪問位置true點(diǎn)。重復(fù)此步驟，直到剛訪問過的頂點(diǎn)沒有未被訪問的鄰接點(diǎn)，轉(zhuǎn)步驟（3）；或是訪問到的點(diǎn)等于深度序列的第一個(gè)點(diǎn)，轉(zhuǎn)步驟（4）。

（3） 返回前一個(gè)訪問過的頂點(diǎn)，找出該頂點(diǎn)的下一個(gè)未被訪問的鄰接點(diǎn)x，訪問該頂點(diǎn)，轉(zhuǎn)步驟（2）；若返回的是深度序列的第一個(gè)點(diǎn)，且該點(diǎn)的所有鄰接點(diǎn)均被訪問過，說明由該點(diǎn)出發(fā)尋找環(huán)失敗，對(duì)相應(yīng)的頂點(diǎn)的度和其邊的訪問信息進(jìn)行還原。

（4） 此時(shí)說明找到了環(huán)，輸出環(huán)。并將所得的環(huán)壓入多邊形序列中，轉(zhuǎn)步驟（1）。

2.2.2 衣片的過濾

對(duì)一個(gè)無向圖經(jīng)過上述處理之后，得到了一系列的環(huán)，但是這些環(huán)不一定滿足封閉多邊形條件，需要這些多邊形進(jìn)行過濾和再處理。

針對(duì)衣片說明信息中的環(huán)路，可以利用其上的一個(gè)點(diǎn)是否在衣片內(nèi)部進(jìn)行快速判斷，并將其加入衣片的數(shù)據(jù)結(jié)構(gòu)中。

針對(duì)2個(gè)衣片邊緣邊框相接的情況，可以利用下述判斷多邊形是否為最小環(huán)的公式進(jìn)行過濾。設(shè)一個(gè)多邊形的邊數(shù)為m，頂點(diǎn)的個(gè)數(shù)為n，若m-（n-1）>1，那么該多邊形不是最小封閉多邊形，如圖5所示的環(huán)的邊數(shù)m=8，頂點(diǎn)數(shù)n=7，則m-（n-1）=2>1。本文就是利用上述條件，將不滿足最小環(huán)的多邊形找出來進(jìn)行再處理。按照上述條件對(duì)上操作獲得的環(huán)進(jìn)行過濾，得到需要再處理的環(huán)。采用如下方法獲得封閉多邊形：

（1） 對(duì)于任意一個(gè)需要再處理的環(huán)，首先在其上尋找一組相鄰的頂點(diǎn)；

（2） 在該環(huán)中這2個(gè)頂點(diǎn)之間除了直接相連的邊以外的最短路徑[10]。采用Floyed算法尋找2個(gè)點(diǎn)的最短路徑算法，屬于經(jīng)典算法，文獻(xiàn)[11]中做了比較詳細(xì)的說明，此處不做過多說明。

至此經(jīng)過上述2步對(duì)所有非法封閉環(huán)的處理，便可獲得所有最小環(huán)。

2.3 尋找排料衣片附加信息

尋找排料衣片附加信息，是排料系統(tǒng)不可或缺的一個(gè)部分，主要利用衣片樣板附加信息的內(nèi)部性，即所有文字說明信息均存在于衣片樣板的內(nèi)部。其具體實(shí)現(xiàn)可從2個(gè)方面進(jìn)行，從包容性考慮凡是在衣片邊緣邊框內(nèi)部的均是衣片的邊緣信息。從速度上考慮，對(duì)提取出衣片邊緣邊框后的圖進(jìn)行再處理，找出圖中的最小子圖，每一個(gè)最小子圖為衣片附加信息中的一部分。所以在判定其是否為某塊衣片的附加信息的時(shí)候，只需對(duì)該子圖上的一個(gè)點(diǎn)進(jìn)行判斷即可。若該點(diǎn)在某塊衣片邊緣邊框的內(nèi)部，則可說明該最小子圖為衣片的附加信息，并將其加入該衣片所屬的數(shù)據(jù)結(jié)構(gòu)中。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)的配置環(huán)境如下： 2.93 GHz Intel I3 CPU，2.0 GB內(nèi)存，NVIDIA GeForce GTS450 GPU，編程環(huán)境為Microsoft Visual Studio 2008，程序主框架采用C++編寫，使用了stl等函數(shù)庫。

本文實(shí)驗(yàn)所用的PLT文件包含5套衣片信息，總共包含衣片個(gè)數(shù)為87塊。在經(jīng)過初步提出所有環(huán)后顯示的部分衣片如圖5所示，可知存在非法衣片。

圖5 初步提取后的所有環(huán)序列

對(duì)上面出現(xiàn)的情況繼續(xù)處理，經(jīng)過過濾操作后，執(zhí)行Floyed算法后可得到正確的衣片，如圖6所示。

圖6 過濾操作后的正確衣片

經(jīng)過過濾操操作，對(duì)所有衣片樣板進(jìn)行排料，最后顯示附加信息如圖7所示。

圖7 衣片樣板進(jìn)行排料最終結(jié)果圖

4 結(jié) 語

本文提出面向服裝的自動(dòng)衣片多邊形提取算法研究與應(yīng)用，首先將PLT文件解析成邊的結(jié)構(gòu)，其次根據(jù)這些邊之間的關(guān)系，構(gòu)造圖的鄰接表數(shù)據(jù)結(jié)構(gòu)，接著在圖的鄰接表數(shù)據(jù)結(jié)構(gòu)中根據(jù)DFS算法尋找環(huán)，最后過濾環(huán)尋找衣片的附加信息。經(jīng)過這些步驟后，使之能夠從僅僅包含頂點(diǎn)間矢量關(guān)系的PLT文件，讀取出衣片樣板的信息，供排料系統(tǒng)使用。

本文采用方法在對(duì)非法環(huán)進(jìn)行處理的時(shí)候采用Floyed算法來尋找圖中2點(diǎn)之間的最短路徑來獲得最終的最小封閉多邊形，由于Floyed算法的時(shí)間復(fù)雜度比較大。如何快速的從非法環(huán)中獲得正確的最小封閉多邊形成為下一步的研究方向。

參考文獻(xiàn)

[1] 李旭，嚴(yán)寒冰，羅戎蕾.服裝CAD中衣片設(shè)計(jì)和排料模塊技術(shù)的研究[J].浙江工程學(xué)院學(xué)報(bào)，2000，17（3）：166?172.

[2] 陸美琴.服裝排料技術(shù)的研究[D].上海：東華大學(xué)，2006.

[3] 陳義華.服裝CAD的打板模式及其應(yīng)用分析[D].北京：北京服裝學(xué)院，2008.

[4] 蔡明.基于HPGL文件的圖元優(yōu)化排序[J].計(jì)算機(jī)系統(tǒng)應(yīng)用， 2013（5）：203?206.

[5] 王建軍.服裝切割系統(tǒng)的軟件研究與設(shè)計(jì)[D].杭州：浙江工業(yè)大學(xué)，2012.

[6] 湯躍忠.HPGL/2及RTL繪圖儀語言編程指南[M].北京：清華大學(xué)出版社，1994.

[7] 張書偉，劉建群，施為，等.數(shù)控系統(tǒng)中HPGL圖形文件識(shí)別與圖形處理研究[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2013（2）：84?87.

[8] 田翠華，許衛(wèi)平，陳玉明.深度優(yōu)先遍歷算法、隨機(jī)布點(diǎn)法及回溯法在迷宮游戲中的應(yīng)用[J].河北北方學(xué)院學(xué)報(bào)：自然科學(xué)版，2013（3）：19?24.

[9] 劉萍，馮桂蓮.圖的深度優(yōu)先搜索遍歷算法分析及其應(yīng)用[J].青海師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007（3）：41?44.

[10] 賀鵬，殷亞君.最短路徑算法淺析[J].甘肅科技，2010（2）：42?43.

[11] 陸鋒.最短路徑算法：分類體系與研究進(jìn)展[J].測繪學(xué)報(bào)， 2001（3）：269?275.