[發明專利]排版方法和排版裝置

有效

• 申請號: 201210080373.5
• 申請日: 2012-03-23
• 公開（公告）號: CN103324606A
• 公開（公告）日: 2013-09-25
• 發明（設計）人: 陳新武;高拯
• 申請（專利權）人: 佳能株式會社
• 主分類號: G06F17/25
• 分類號: G06F17/25
• 代理公司: 中國國際貿易促進委員會專利商標事務所 11038
• 代理人: 陳芳

技術領域

本發明涉及排版方法和排版裝置，具體地涉及能夠通過調節塊的排版順序并對組合過程進行限制來實現較少的差的排版效果并進一步降低材料的浪費率的排版方法和排版裝置。所述排版方法和裝置可被用于諸如印刷、切割和包裝等的各種領域中。

背景技術

排版是印刷過程中的重要階段，它是指根據某些規則將(文本和圖像的)各種塊放置在印刷材料片材上。圖1(a)和圖1(b)示出排版的例子。圖1(a)示出要在具有固定寬度和可變高度的一張紙上排版的五個原始矩形塊R1、R2、R3、R4和R5。這里，寬度是沿水平方向的尺寸，高度是沿垂直方向的尺寸。圖1(b)示出通過對這五個原始矩形塊進行排版而獲得的排版結果。在圖1(b)中，H是要從紙上切割的高度，并且圖中示出的陰影區域被浪費。排版的一個目標是使高度H最小化，從而降低紙的浪費率。然后，將從紙上切出五個原始矩形塊R1、R2、R3、R4和R5。

在圖2的流程圖200中示出一種常規的排版方法，該排版方法是基于P.Y.Wang的標題為“Two?Algorithms?for?Constrained?Two-Dimensional?Cutting?Stock?Problems”的文章，Operations??Research，Vol.31，No.3，PP.573-586(1983)。在該方法中，在準備塊集合(步驟210)之后，反復地執行塊集合中的塊的自由組合(步驟220)，以獲得并輸出部分解(步驟230和240)。這里，術語“自由組合”是指包含圖3所示的水平組合(即，沿水平方向組合塊)和垂直組合(即，沿垂直方向組合塊)的組合過程。在圖3中，兩個塊A和B分別被水平組合和垂直組合以產生新的塊C，并且圖中示出的陰影區域被浪費。術語“部分解”是指通過對原始塊進行組合而獲得的滿足某些條件(例如，其浪費面積小于給定的閾值等)的塊，但是該塊不包含所有的原始塊。在找到并輸出部分解之后，確定所有的原始塊是否都被輸出(步驟250)。如果在步驟250中確定并非所有的原始塊都被輸出，那么對剩余的原始塊重復上述步驟S210至240。相反，如果在步驟250中確定所有的原始塊都被輸出，那么本過程結束。

在中國專利申請No.200910158406.1中公開了另一種常規的排版方法。圖4是示出該常規的排版方法的一般過程的流程圖400。在步驟410中，準備塊集合。該步驟對于輸入的原始塊執行預先處理并形成塊集合。然后，在步驟420中，反復執行塊集合中的原始塊的自由組合。如上所述，在該步驟中可執行水平組合和垂直組合兩者。接下來，在步驟430中，反復執行原始塊的垂直組合。請注意，在該步驟中只執行垂直組合。與圖2中所示的步驟230一樣，在步驟440中，獲得滿足某些條件的部分解。在步驟450中，輸出獲得的部分解。與圖2中所示的步驟250一樣，在步驟460中，確定是否所有的原始塊都被輸出。如果在步驟460中確定并非所有的原始塊都被輸出，那么對于剩余的原始塊重復上述步驟410至450。相反，如果在步驟460中確定所有的原始塊都被輸出，那么本過程結束。

與圖2中的常規排版方法相比，圖4中的常規排版方法涉及兩階段的組合過程，該組合過程包括自由組合和垂直組合。使用包括自由組合和垂直組合的排版方法，可以減少材料片材的浪費，由此可以降低成本，并且/或者，可以提高排版速度，從而可以改善效率。一般來說，這些排版方法還可以應用于切割和包裝行業。

從成本的觀點看，理想的排版方法可使材料片材的浪費最小化；從效率的觀點看，理想的排版方法不依賴于人工干預，并且使用很少的時間。當前的所有排版方法都朝著這兩個方向進行改進，但是當前的排版方法中很少有令人滿意的。

常見的排版方法由于片面追求最優而往往會在初期能得到很好的結果。但是，這些排版方法全部使用小塊填充空隙，從而在后期大塊造成的空隙很難得到填補。結果，排版效果變差，并且浪費大量的材料。

因此，需要可以實現較少的差的排版效果并進一步降低材料的浪費率的排版方法和排版裝置。

發明內容

鑒于上述情形而作出了本發明，并且，本發明的目的在于提供一種能夠通過調節塊的排版順序并對組合過程進行限制來實現較少的差的排版效果并進一步降低材料的浪費率的排版方法和排版裝置。