面向服裝排料的自動衣片多邊形提取算法研究與應用

徐云云+江玉清

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

關鍵詞： 服裝排料系統； 衣片樣板； 深度遍歷； 最短路徑； Floyed算法

中圖分類號： TN919?34 文獻標識碼： A 文章編號： 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 引 言

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

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

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

1 問題分析

排料系統的PLT文件由衣片信息組成，其中衣片信息主要由2個部分組成：衣片的邊緣邊框和衣片的說明信息。具有以下特點：

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

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

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

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

圖2 衣片與其說明信息之間的關系

上述衣片的特點可以作為尋找衣片的有力根據，下文中關于衣片提取的具體方法就是基于衣片此3個特點展開的。

2 衣片自動提取方法

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

2.1 由PLT文件構圖

通過對樣板衣片的PLT文件測試可知，文件具有頂點多，頂點之間的關聯度小的特點，屬于稀疏圖。所以本文提出的方法采用鄰接表的數據結構保存圖的信息，以節省空間。

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

在將PLT文件構成圖G=（V，E）時，對PLT文件中的每一個點將對應于圖G中的一個頂點，對PLT文件中由指令之間的組合所構成的邊將看作圖G中的一條邊，經過對PLT文件進行解析處理便可得到圖的數據結構G=（V，E），下面以此作為對象，展開環的提取操作。

2.2 衣片樣板的提取

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

（1） 附加信息中的環路，例如：“0”；

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

圖4 兩個邊緣邊框相接的非法衣片

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

2.2.1 衣片的初提取

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

（1） 從圖的數據結構的頂點表的第一個節點開始，依次向后遍歷，當頂點v0的度數大于1的時候，則以該頂點為起點進行深度遍歷；當完成所有頂點的遍歷之后，算法結束。

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

（3） 返回前一個訪問過的頂點，找出該頂點的下一個未被訪問的鄰接點x，訪問該頂點，轉步驟（2）；若返回的是深度序列的第一個點，且該點的所有鄰接點均被訪問過，說明由該點出發尋找環失敗，對相應的頂點的度和其邊的訪問信息進行還原。

（4） 此時說明找到了環，輸出環。并將所得的環壓入多邊形序列中，轉步驟（1）。

2.2.2 衣片的過濾

對一個無向圖經過上述處理之后，得到了一系列的環，但是這些環不一定滿足封閉多邊形條件，需要這些多邊形進行過濾和再處理。

針對衣片說明信息中的環路，可以利用其上的一個點是否在衣片內部進行快速判斷，并將其加入衣片的數據結構中。

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

（1） 對于任意一個需要再處理的環，首先在其上尋找一組相鄰的頂點；

（2） 在該環中這2個頂點之間除了直接相連的邊以外的最短路徑[10]。采用Floyed算法尋找2個點的最短路徑算法，屬于經典算法，文獻[11]中做了比較詳細的說明，此處不做過多說明。

至此經過上述2步對所有非法封閉環的處理，便可獲得所有最小環。

2.3 尋找排料衣片附加信息

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

3 實驗結果與分析

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

本文實驗所用的PLT文件包含5套衣片信息，總共包含衣片個數為87塊。在經過初步提出所有環后顯示的部分衣片如圖5所示，可知存在非法衣片。

圖5 初步提取后的所有環序列

對上面出現的情況繼續處理，經過過濾操作后，執行Floyed算法后可得到正確的衣片，如圖6所示。

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

經過過濾操操作，對所有衣片樣板進行排料，最后顯示附加信息如圖7所示。

圖7 衣片樣板進行排料最終結果圖

4 結 語

本文提出面向服裝的自動衣片多邊形提取算法研究與應用，首先將PLT文件解析成邊的結構，其次根據這些邊之間的關系，構造圖的鄰接表數據結構，接著在圖的鄰接表數據結構中根據DFS算法尋找環，最后過濾環尋找衣片的附加信息。經過這些步驟后，使之能夠從僅僅包含頂點間矢量關系的PLT文件，讀取出衣片樣板的信息，供排料系統使用。

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

參考文獻

[1] 李旭，嚴寒冰，羅戎蕾.服裝CAD中衣片設計和排料模塊技術的研究[J].浙江工程學院學報，2000，17（3）：166?172.

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

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

[4] 蔡明.基于HPGL文件的圖元優化排序[J].計算機系統應用， 2013（5）：203?206.

[5] 王建軍.服裝切割系統的軟件研究與設計[D].杭州：浙江工業大學，2012.

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

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

[8] 田翠華，許衛平，陳玉明.深度優先遍歷算法、隨機布點法及回溯法在迷宮游戲中的應用[J].河北北方學院學報：自然科學版，2013（3）：19?24.

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

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

[11] 陸鋒.最短路徑算法：分類體系與研究進展[J].測繪學報， 2001（3）：269?275.