基于矩形Packing問題求解的頁面自動排版方法

李治江，崔廣勛，王嵩

1.武漢大學印刷與包裝系，湖北武漢430079

2.高德軟件有限公司數據研發中心，北京102200

基于矩形Packing問題求解的頁面自動排版方法

李治江1，崔廣勛1，王嵩2

1.武漢大學印刷與包裝系，湖北武漢430079

2.高德軟件有限公司數據研發中心，北京102200

為了較好地實現頁面的自動排版，本文提出了基于矩形Packing問題求解的頁面自動排版方法。該方法采用結構化描述語言來分析描述版面的圖文內容及排版樣式，通過構建頁面模型把頁面自動排版問題抽象為關于圖文混排矩形塊的版面布局自動規劃問題，根據矩形塊面積排序，判斷約束信息，定位步驟和回溯步驟，得到最終的頁面自動排版效果。通過頁面數據排版實驗進行測試，實驗驗證該方法能較好地符合條件要求。

自動排版；矩形Packing

1　引言

隨著互聯網的發展，信息量的膨脹，電子設備的普及和環保無紙化觀念的推廣，網絡出版以其效率更高、價位更低、檢索快捷、避免絕版等優點不斷沖擊著傳統出版市場，傳統出版向網絡出版轉型是出版行業發展的趨勢［1-3］，自動排版的實現將縮短排版工序用時，為出版行業帶來產業化的效益提升。

近年來不少學者對排版問題進行了研究，取得了一些成績［4-11］。如張金美介紹了CorelDRAW12在排版中的應用和技巧［4］；王勇等分析比較了LaTeX和方正書版2種軟件排版數學論文的特點［5］；李金城等利用JavaScript在Indesign中實現基于XML結構化文檔的自動排版［6］；肖建國等關注XML技術在跨媒體領域的應用［7-9］；蘇勇的專利根據給定的固定欄數、欄距、頁面區域面積等信息進行自動圖文排版，不適用于頁面含有多個信息塊的復雜情況［10］；王罡等在圖片排版中使用了模擬退火算法進行迭代優化［11］。針對矩形Packing NP完全問題的現實應用實例，還有許多學者也做出了相關研究［12-14］。現有的研究部分關注CorelDRAW、word等軟件的排版，不具有普適性；部分關注圖片或文字的單獨排版，容易出現圖文版面尺寸不匹配等問題，同時調整的影響面比較大，效率較低。受以上研究啟發，本文對頁面自動排版方法進行研究，提出一個基于矩形Packing問題求解的自動排版的算法。

2　頁面模型

2.1基于矩形Packing問題的求解模型

矩形Packing問題是一類特殊的Packing問題，是面向貨物裝載、木材下料等現實應用的問題抽象。求解矩形Packing問題的常見優化算法主要包括遺傳算法、模擬退火算法、動態規劃與啟發式算法等［15］。常見的矩形Packing問題有矩形背包、裝填、布局問題［15］。自動排版問題與矩形塊布局問題最為相似。

對頁面元素進行結構化表達，可以將圍繞某一主題的圖文信息塊抽象為矩形塊，由此可得到n個矩形塊Ri（i=1，2，...，n）。假設已知寬度為w高度為h的待排矩形版面區域R0，頁面自動排版的目的是以矩形塊面積為排序依據，根據面積大小進行定序，以不同填角動作的優度高低進行定位，將這n個矩形塊互不重疊地放入待排矩形版面中。此問題可以形式化地描述為：將二維笛卡爾坐標系的原點取在待排區域的左上角，（0，h）為待排區域的左下角坐標，（w，0）為待排區域的右上角坐標，求n個四元組的集合，即

使這n個矩形塊的最小外包矩形的面積最小，生成樣式美觀、留白均勻的頁面。其中，（xli，yli）表示矩形塊i的左上角坐標，（xri，yri）表示右下角坐標，且對于任意的矩形塊i，其坐標滿足如下條件約束：

（1）矩形塊的每條邊均與平面直角坐標系的x軸或y軸平行（或重合）；

（2）任意兩矩形塊互不重疊；

（3）任意矩形塊均在待排區域內，即0≤xli＜xri＜w，并且0≤yli＜yri＜h。

2.2頁面模型要素及操作定義

定義1（角區）由于本文探討的是矩形圖文信息塊，因此兩相鄰矩形塊所形成的夾角必為直角，角區即為兩相鄰矩形塊與空白區域形成的直角范圍，使用五元組表示：

式中，x，y表示角區所處直角頂點的坐標，R1，R2表示直角兩邊所在的矩形塊，角區的type共分為四種：└、┘、┌、┐。如圖1所示a、b、c、d四個直角標注為各種角區情況。

圖1　角區和填角動作Fig.1Cornerareas and action to fillthem

圖2　一般填角動作的優度Fig.2Optimalaction to fill cornerareas

圖3　面積權重的霍夫曼樹構建Fig.3Construction of Huffman tree of area weight

定義2（填角動作）在某一布局之下，若放入的矩形塊R與容器中已有矩形塊（本文將初始版面定義為由頁邊距參數形成的四個矩形塊包圍而成的版心）中的某兩塊Ri和Rj的不同方向邊有重疊，且重疊長度大于0，則矩形塊R占據了由矩形塊Ri和Rj形成的一個角區，此時稱該矩形塊的放入動作為一個填角動作。使用二元組（Corner，R）表示一個填角動作，表示將矩形塊R填入Corner的角區。

如圖1所示，現要將矩形塊R3放入已放入R1R2R4R6的布局中（邊界矩形為RTRBRLRR），當前布局共有7個角區。圖中3-1的填角動作表示為（Corner1，R3），3-2為（Corner4，R3），3-3為（Corner5，R3），3-4為（Corner6，R3）。其中，合法填角動作為3-1、3-3、3-4。

定義3（合法填角動作的優度）對于一般填角動作（Corner，Ri），其優度γ計算表達式為：

式中，dmin為Ri與所有已填入當前布局的矩形塊（包括構成排版區域的4塊邊界矩形塊RTRBRLRR但不包括構成此角的矩形塊RL和R2）距離中最小的，wi和hi分別為矩形塊Ri的寬度和高度，如圖2所示。

定義4（矩形塊距離）給定矩形塊Ri和Rj，其距離dij表達式為：

式中，（xci，yci）和（xcj，ycj）分別為矩形塊Ri與Rj的中心點坐標；wi、wj分別為寬，hi、hj分別為高。

（1）矩形塊內不分欄情況下，圖片繞排方式為嵌入型時第i個矩形塊面積Si表達式為：

式中，Nm表示正文字數，Nt表示標題字數，Iw表示圖像寬度，Ih表示圖像高度，Rd表示圖像繞排間距。

（2）矩形塊內分欄情況下，矩形塊的面積分為最小占用面積Smin、最大占用面積Smax和平均占用面積，由欄寬很大程度決定，因此將矩形塊面積表達式視為與分欄數ni相關的函數式Si=f（ni），其中

初始計算時，通過圖文混排各條件參數的中值計算得到每個矩形塊的近似折中面積S'i。再按下述公式（8）求得矩形塊的近似面積Si。式中，S為初始頁面待排區域面積，λ為權重調節因子，針對算法不同調節初始計算信息塊面積占總面積的權重比。

定義6（霍夫曼樹面積權重分級）在以面積作為節點權值構成的霍夫曼樹中，我們根據葉子節點的起止深度定義其權重級別。如圖3所示的霍夫曼樹，S4與S1，在霍夫曼樹中為第二層，在面積權重分級中則為第一級，S7、S2與S6為樹的第三層，面積權重為第二級，S3與S5為樹的第四層，面積權重為第三級。

3　頁面自動布局的最優化求解

本文將頁面中各矩形塊描述為固定模板和可變數據兩部分［16］，分別進行處理。定序過程中，先判斷其約束信息，優先填入固定模板。此時，位置約束下的版面分割問題即可轉化為一個初始布局為已在中間位置填入部分內容的一般版面布局自動規劃問題，本文采用貪心算法進行最優化求解。

3.1基于霍夫曼樹的版面分割

矩形塊面積是頁面局部優化過程中重要的決定參數，論文引入霍夫曼樹模型對信息塊面積進行帶權分級。同時，本文將版面分割過程霍夫曼樹模型進行關聯對應，通過分割方向與分割比例參數控制所生成的版面，如圖4圖5所示，然后再使用二叉樹進行表達，其表達效果如圖3所示。

3.2基于貪心算法的最優化求解

基于貪心算法，本文采用限制條件約束的遞歸回溯算法，依照優先順序逐個遍歷尚未放入的矩形塊，根據本文定義的操作，根據面積，優先放入角區，若有放置不下或是使全局留白均衡度超限的情況則進行回溯放置，直至所有矩形塊全部放入。基本算法描述如下：

（1）在當前布局狀態下，枚舉出待排區域的所有合法填角動作；

（2）對于每個待排的矩形塊，計算其所有的合法填角動作的優度；

（3）將優度最大的合法填角動作對應的矩形塊放入待排區域內；

（4）更新當前布局，得到新的布局。

回溯過程是指在矩形塊沒有能夠全部排入待排區域的情況下，進行回溯操作，具體步驟主要包括：

（1）選擇排版步驟中合法填角動作的優度次之的角區進行填角動作；

（2）選擇排入順序優先度次之的矩塊進行排入。

空白區合并的步驟為：

首先遍歷空白區的各邊，計算與之相鄰的矩形的重疊邊長，根據重疊比例及是否為端線進行優先級排序，并按優先級進行空白區并入。

4　實驗與分析

對本文提出的方法，用如圖6所示的測試數據進行測試。對于該待排的報紙版面，共有11個矩形塊組成：其中矩形塊S3、S5、S7是圖片和文字一體的，S1、S2和S11分別代表報紙頁面的報眼、頭版和導讀信息，具有位置約束信息，需要優先排入。由公式（6）和公式（7）計算的矩形塊的分欄面積。

圖4　待軸分版面Fig.4 Page layout waiting for partition by axis

圖5　軸分版面效果Fig.5 Effect of page layout parting by axis

圖6　測試數據原始版面Fig.6 Initial page layout of test data

圖7　位置約束Fig.7 Constraint location

圖8　初始版面Fig.8 Initial page layout

圖9　空白區合并Fig.9 Merged blank areas

圖10　最終布局結果Fig.10 The final page layout

圖11　GA布局結果Fig.11 GA page layout

表1　測試數據矩形塊填入面積（mm2）Table 1 Areas of test data filled in rectangular blocks

為了驗證本文方法，針對同一實驗數據，采用遺傳算法（Genetic algorithms，GA）進行了版面自動布局實驗，實驗結果如圖11所示。根據實驗結果，能夠發現：

（1）GA算法的處理結果并沒有考慮空白區合并的優化策略；

（2）本文方法采用的回溯策略能夠更好地得到最優解。

（3）本文算法的時間復雜度為O（n*logn），GA的時間復雜度為O（T*n2），實驗過程亦能驗證本文方法的處理效率更優。

4　結語

本文僅對以矩形信息塊構成的布局較為方正規整、留白較為均勻的版面自動排布問題進行討論，對版面風格相對歡快，會有超出一般矩形塊的表達方式，如傾斜矩形、梯形乃至不規則多邊形等，暫未給出解決方案。該算法可以較好地應用于要求整版分欄線區分明顯且無優先序的版面布局，也可應用于頁面中有固定矩形塊內容與位置關聯的版面布局。

［1］程維紅，任勝利，路文如，等.我國科技期刊由傳統出版向數字出版轉型的對策建議［J］.中國科技期刊研究，2011，22（4）：467-474

［2］肖洋.我國數字出版產業發展戰略研究——基于產業結構、區域、階段的視角［D］.南京：南京大學，2013

［3］齊福斌.數字出版與傳統出版數字化轉型［J］.印刷世界，2012（1）：4-10

［4］張金美.CorelDraw12在報紙排版設計中的應用［J］.硅谷，2014（21）：229，212

［5］王勇，姚萍，王嵐，等.LaTeX與方正書版排版數學論文探討［J］.中國科技期刊研究，2012，23（6）：1036-1039

［6］李金城，余方，方婷云.利用JavaScript編程在Indesign中實現基于XML結構化文檔的自動排版［J］.中國科技期刊研究，2015（2）：172-175

［7］肖建國.XML和DAM技術與跨媒體出版［J］.印刷世界，2001（4）：6-7

［8］郭穎妤.XML在跨媒體出版中的應用［J］.印刷雜志，2004（11）：46-48

［9］Li Shuwei，You FuCheng.Research on XML Digital Signature Application in the Log Protection of Typesetting on Web.2012 International Conference on Control Engineering and Communication Technology，2012（15）：619-623

［10］蘇勇.一種圖文的自動排版方法：中國，200710121797.0［P］.2008-02-13

［11］王罡，彭國華，余遷.模擬退火算法在圖片優化排版中的應用［J］.西南民族大學學報：自然科學版，2006（3）：586-590

［14］Hopper E，Turton B.An Empirical Investigation of Meta-heuristic and Heuristic Algorithm for a 2D Packing Problem［J］. European Journal of Operational Research，2001，128（1）：34-57

［15］周紹梅，趙苗，吳悅成.基于單親遺傳算法的最優布局問題求解［J］.計算機與現代化，2007（11）：40-42

［16］Jansen K，Solis-Oba R.Rectangle packing with one-dimensional resource augmentation［J］.Discrete Optimization，2009，6（3）：310-323

［16］陳端兵.求解矩形Packing問題的純粹擬人算法［D］.武漢：華中科技大學，2007

［17］李治江，林武，王強.可變數據出版系統的設計與實現［J］.中國印刷與包裝研究，2009（1）：75-80

Automatic Page Layout Based on Solution for Rectangular Packing Problem

LI Zhi-jiang1，CUI Guang-xun1，WANG Song2
1.Department of Printing and Packaging/Wuhan University，Wuhan 430079，China
2.Data Research and Development Center/AutoNavi Software Co.Ltd.，Beijing 102200，China

In order to realize automatic page layout，a method based on rectangular packing problem was proposed.It was described the graphics，texts and layout style of pages through the Structural language.The automatic page layout problem was formalized as a rectangle packing blocks with image-text contents to obtain the final automatic page layout effect according to sorting the areas of rectangles，judging constraint information，positioning each rectangles and backtracking algorithm.Experiment was carried out by using the page layout data and the result was able to well match the requirements.

Automatic page layout；rectangle Packing

TS812+.2

A

1000-2324（2016）02-0264-05

2015-04-03

2015-05-10

國家科技支撐計劃：跨媒體數字出版平臺標準及規范研究（2012BAH91F03）；武漢大學自主科研項目：基于多源數據融合快速檢索（2042014gf013）

李治江（1977-），男，博士，副教授，研究方向為視覺分析與檢測、數字出版技術.E-mail：lizhijiang@whu.edu.cn