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

李治江，崔廣勛，王嵩

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

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

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

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

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

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

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

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

1　引言

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

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

2　頁(yè)面模型

2.1基于矩形Packing問(wèn)題的求解模型

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

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

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

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

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

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

2.2頁(yè)面模型要素及操作定義

定義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與容器中已有矩形塊（本文將初始版面定義為由頁(yè)邊距參數(shù)形成的四個(gè)矩形塊包圍而成的版心）中的某兩塊Ri和Rj的不同方向邊有重疊，且重疊長(zhǎng)度大于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)度）對(duì)于一般填角動(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í)，通過(guò)圖文混排各條件參數(shù)的中值計(jì)算得到每個(gè)矩形塊的近似折中面積S'i。再按下述公式（8）求得矩形塊的近似面積Si。式中，S為初始頁(yè)面待排區(qū)域面積，λ為權(quán)重調(diào)節(jié)因子，針對(duì)算法不同調(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　頁(yè)面自動(dòng)布局的最優(yōu)化求解

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

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

矩形塊面積是頁(yè)面局部?jī)?yōu)化過(guò)程中重要的決定參數(shù)，論文引入霍夫曼樹模型對(duì)信息塊面積進(jìn)行帶權(quán)分級(jí)。同時(shí)，本文將版面分割過(guò)程霍夫曼樹模型進(jìn)行關(guān)聯(lián)對(duì)應(yīng)，通過(guò)分割方向與分割比例參數(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）對(duì)于每個(gè)待排的矩形塊，計(jì)算其所有的合法填角動(dòng)作的優(yōu)度；

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

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

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

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

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

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

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

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

對(duì)本文提出的方法，用如圖6所示的測(cè)試數(shù)據(jù)進(jìn)行測(cè)試。對(duì)于該待排的報(bào)紙版面，共有11個(gè)矩形塊組成：其中矩形塊S3、S5、S7是圖片和文字一體的，S1、S2和S11分別代表報(bào)紙頁(yè)面的報(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　測(cè)試數(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　測(cè)試數(shù)據(jù)矩形塊填入面積（mm2）Table 1 Areas of test data filled in rectangular blocks

為了驗(yàn)證本文方法，針對(duì)同一實(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é)果并沒(méi)有考慮空白區(qū)合并的優(yōu)化策略；

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

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

4　結(jié)語(yǔ)

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

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

［2］肖洋.我國(guó)數(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］.中國(guó)科技期刊研究，2012，23（6）：1036-1039

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

［7］肖建國(guó).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)排版方法：中國(guó)，200710121797.0［P］.2008-02-13

［11］王罡，彭國(guó)華，余遷.模擬退火算法在圖片優(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)布局問(wèn)題求解［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問(wèn)題的純粹擬人算法［D］.武漢：華中科技大學(xué)，2007

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

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

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