李治江，崔廣勛，王嵩

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

2.高德軟件有限公司數(shù)據(jù)研發(fā)中心，北京102200

基于矩形Packing問題求解的頁面自動(dòng)排版方法

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

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

2.高德軟件有限公司數(shù)據(jù)研發(fā)中心，北京102200

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

自動(dòng)排版；矩形Packing

1　引言

隨著互聯(lián)網(wǎng)的發(fā)展，信息量的膨脹，電子設(shè)備的普及和環(huán)保無紙化觀念的推廣，網(wǎng)絡(luò)出版以其效率更高、價(jià)位更低、檢索快捷、避免絕版等優(yōu)點(diǎn)不斷沖擊著傳統(tǒng)出版市場，傳統(tǒng)出版向網(wǎng)絡(luò)出版轉(zhuǎn)型是出版行業(yè)發(fā)展的趨勢［1-3］，自動(dòng)排版的實(shí)現(xiàn)將縮短排版工序用時(shí)，為出版行業(yè)帶來產(chǎn)業(yè)化的效益提升。

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

2　頁面模型

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

矩形Packing問題是一類特殊的Packing問題，是面向貨物裝載、木材下料等現(xiàn)實(shí)應(yīng)用的問題抽象。求解矩形Packing問題的常見優(yōu)化算法主要包括遺傳算法、模擬退火算法、動(dòng)態(tài)規(guī)劃與啟發(fā)式算法等［15］。常見的矩形Packing問題有矩形背包、裝填、布局問題［15］。自動(dòng)排版問題與矩形塊布局問題最為相似。

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

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

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

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

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

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

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

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

圖1　角區(qū)和填角動(dòng)作Fig.1Cornerareas and action to fillthem

圖2　一般填角動(dòng)作的優(yōu)度Fig.2Optimalaction to fill cornerareas

圖3　面積權(quán)重的霍夫曼樹構(gòu)建Fig.3Construction of Huffman tree of area weight

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

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

定義3（合法填角動(dòng)作的優(yōu)度）對于一般填角動(dòng)作（Corner，Ri），其優(yōu)度γ計(jì)算表達(dá)式為：

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

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

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

（1）矩形塊內(nèi)不分欄情況下，圖片繞排方式為嵌入型時(shí)第i個(gè)矩形塊面積Si表達(dá)式為：

式中，Nm表示正文字?jǐn)?shù)，Nt表示標(biāo)題字?jǐn)?shù)，Iw表示圖像寬度，Ih表示圖像高度，Rd表示圖像繞排間距。

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

初始計(jì)算時(shí)，通過圖文混排各條件參數(shù)的中值計(jì)算得到每個(gè)矩形塊的近似折中面積S'i。再按下述公式（8）求得矩形塊的近似面積Si。式中，S為初始頁面待排區(qū)域面積，λ為權(quán)重調(diào)節(jié)因子，針對算法不同調(diào)節(jié)初始計(jì)算信息塊面積占總面積的權(quán)重比。

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

3　頁面自動(dòng)布局的最優(yōu)化求解

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

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

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

3.2基于貪心算法的最優(yōu)化求解

基于貪心算法，本文采用限制條件約束的遞歸回溯算法，依照優(yōu)先順序逐個(gè)遍歷尚未放入的矩形塊，根據(jù)本文定義的操作，根據(jù)面積，優(yōu)先放入角區(qū)，若有放置不下或是使全局留白均衡度超限的情況則進(jìn)行回溯放置，直至所有矩形塊全部放入?；舅惴枋鋈缦拢?/p>

（1）在當(dāng)前布局狀態(tài)下，枚舉出待排區(qū)域的所有合法填角動(dòng)作；

（2）對于每個(gè)待排的矩形塊，計(jì)算其所有的合法填角動(dòng)作的優(yōu)度；

（3）將優(yōu)度最大的合法填角動(dòng)作對應(yīng)的矩形塊放入待排區(qū)域內(nèi)；

（4）更新當(dāng)前布局，得到新的布局。

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

（1）選擇排版步驟中合法填角動(dòng)作的優(yōu)度次之的角區(qū)進(jìn)行填角動(dòng)作；

（2）選擇排入順序優(yōu)先度次之的矩塊進(jìn)行排入。

空白區(qū)合并的步驟為：

首先遍歷空白區(qū)的各邊，計(jì)算與之相鄰的矩形的重疊邊長，根據(jù)重疊比例及是否為端線進(jìn)行優(yōu)先級(jí)排序，并按優(yōu)先級(jí)進(jìn)行空白區(qū)并入。

4　實(shí)驗(yàn)與分析

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

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

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

圖6　測試數(shù)據(jù)原始版面Fig.6 Initial page layout of test data

圖7　位置約束Fig.7 Constraint location

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

圖9　空白區(qū)合并Fig.9 Merged blank areas

圖10　最終布局結(jié)果Fig.10 The final page layout

圖11　GA布局結(jié)果Fig.11 GA page layout

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

為了驗(yàn)證本文方法，針對同一實(shí)驗(yàn)數(shù)據(jù)，采用遺傳算法（Genetic algorithms，GA）進(jìn)行了版面自動(dòng)布局實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖11所示。根據(jù)實(shí)驗(yàn)結(jié)果，能夠發(fā)現(xiàn)：

（1）GA算法的處理結(jié)果并沒有考慮空白區(qū)合并的優(yōu)化策略；

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

（3）本文算法的時(shí)間復(fù)雜度為O（n*logn），GA的時(shí)間復(fù)雜度為O（T*n2），實(shí)驗(yàn)過程亦能驗(yàn)證本文方法的處理效率更優(yōu)。

4　結(jié)語

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

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

［2］肖洋.我國數(shù)字出版產(chǎn)業(yè)發(fā)展戰(zhàn)略研究——基于產(chǎn)業(yè)結(jié)構(gòu)、區(qū)域、階段的視角［D］.南京：南京大學(xué)，2013

［3］齊福斌.數(shù)字出版與傳統(tǒng)出版數(shù)字化轉(zhuǎn)型［J］.印刷世界，2012（1）：4-10

［4］張金美.CorelDraw12在報(bào)紙排版設(shè)計(jì)中的應(yīng)用［J］.硅谷，2014（21）：229，212

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

［6］李金城，余方，方婷云.利用JavaScript編程在Indesign中實(shí)現(xiàn)基于XML結(jié)構(gòu)化文檔的自動(dòng)排版［J］.中國科技期刊研究，2015（2）：172-175

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

［8］郭穎妤.XML在跨媒體出版中的應(yīng)用［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］蘇勇.一種圖文的自動(dòng)排版方法：中國，200710121797.0［P］.2008-02-13

［11］王罡，彭國華，余遷.模擬退火算法在圖片優(yōu)化排版中的應(yīng)用［J］.西南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，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］周紹梅，趙苗，吳悅成.基于單親遺傳算法的最優(yōu)布局問題求解［J］.計(jì)算機(jī)與現(xiàn)代化，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］.武漢：華中科技大學(xué)，2007

［17］李治江，林武，王強(qiáng).可變數(shù)據(jù)出版系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［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

國家科技支撐計(jì)劃：跨媒體數(shù)字出版平臺(tái)標(biāo)準(zhǔn)及規(guī)范研究（2012BAH91F03）；武漢大學(xué)自主科研項(xiàng)目：基于多源數(shù)據(jù)融合快速檢索（2042014gf013）

李治江（1977-），男，博士，副教授，研究方向?yàn)橐曈X分析與檢測、數(shù)字出版技術(shù).E-mail：lizhijiang@whu.edu.cn