《Active Layout Engine Algorithms and Applications in Variable Data Printing.pdf》由会员分享，可在线阅读，更多相关《Active Layout Engine Algorithms and Applications in Variable Data Printing.pdf（33页珍藏版）》请在三一文库上搜索。
1、 Active Layout Engine: Algorithms and Applications in Variable Data Printing Xiaofan Lin Digital Printing and Imaging Laboratory HP Laboratories Palo Alto HPL-2005-6(R.1) December 8, 2005* automatic document layout, constraint solving, table formatting, Simplex, variable data printing Variable Data
2、Printing (VDP) provides a huge opportunity for HPs imaging and printing business. A core technology required by highly customized VDP applications is the automatic layout engine, whose task is to adjust the original design or generate a new layout to present variable contents. A brand-new layout eng
3、ine, called Active Layout Engine (ALE), has been designed and implemented. “Active“ reflects several unique features of the engine: First, through (multi)linear text block modeling and two-pass constraint solving algorithm, it supports a rich set of layout operations, such as simultaneous optimizati
4、on of text block width and height, integrated image cropping, and non-rectangular text wrapping. Second, it does not rely on a particular layout description language and thus can actively pursue emerging formats and standards. This report describes the various technical aspects of ALE: Linearization
5、 of the text block modeling, two-pass constraint solving algorithm, format-neural Active Layout Template (ALT), system optimization, and typical VDP applications around the core engine. * Internal Accession Date Only To be published in Computer-Aided Design, 2006. Approved for External Publication C
6、opyright 2005 Elsevier Ltd. 1 Active Layout Engine: Algorithms and Applications in Variable Data Printing Xiaofan Lin Hewlett-Packard Laboratories 1501 Page Mill Rd MS 1203, Palo Alto, CA 94304 Email: Abstract Variable Data Printing (VDP) refers to the process of generating and printing dynamic or
7、personalized contents. A core technology required by highly customized VDP applications is the automatic document layout design engine, whose task is to adjust the original design or generate a new layout to present variable contents. This paper presents a novel document layout design engine, called
8、 Active Layout Engine (ALE). “Active” reflects several unique features of the engine: First, through linear text block modeling and two-pass constraint solving algorithm, it supports a rich set of layout operations, such as simultaneous optimization of text block width and height, integrated image c
9、ropping, and non-rectangular text wrapping. Second, it does not rely on a particular layout description language and thus can actively pursue emerging formats and standards. This paper describes the various technical aspects of ALE: linearization of the text block modeling, two-pass constraint solvi
10、ng algorithm, format-neutral Active Layout Template (ALT), system optimization, and typical VDP applications around the core engine. Key words: automatic document layout, constraint solving, table formatting, Simplex, variable data printing 2 1. Introduction Automatic layout and composition technolo
11、gy is of great value to end-to-end digital publishing solutions because it can relieve or eliminate the bottleneck of creating documents composed of highly customized text and image contents. It is also a very challenging technical problem since it involves 2-D optimization of positions and dimensio
12、ns of multiple types of contents: images, texts, and vector graphics. Thus, there has been extensive research in this area. One of earliest efforts may be attributed to the Juno-2 constraint-based drawing editor, developed by Heydon and Nelson in the early 1990s 1. Badros et al 2 proposed a constrai
13、nt extension to Scalable Vector Graphics (SVG) to enable interactive graphics on the Web. Jacobs et al 3 introduced an adaptive document layout system that automatically selects the best template for given contents. Purvis et al 4 formalized the creation of personalized documents as a multi- objecti
14、ve optimization problem and used a genetic algorithm to automatically assemble such documents. Johari et al 5 created a specialized pagination and layout system for yellow pages. Berkner et al 6 introduced a method to intelligently scale picture and text portions of an image by utilizing information
15、 available in the JPEG2000 file. Atkins 7 proposed an image layout algorithm to automate the design of photo albums. Agrawala 8 described a heuristic search- based layout algorithm for placing labels on maps to improve the usability of route maps. In addition, many placement and routing algorithms d
16、eveloped for electronic and mechanic CAD can be also leveraged for document layout design. Obviously, automatic document layout is a very wide area and no single algorithm can solve all of the challenges. Figure 1 shows the taxonomy of various document layout algorithms in terms of template flexibil
17、ity and content flexibility. The left side corresponds to the fixed copy 3 hole fitting, in which variable contents (for example, names, addresses, etc.) are simply filled into fixed copy holes where each object has predefined size and location. On the far right are template-free approaches, in whic
18、h there are no predefined relative positions among the objects. In the middle, existing templates are needed to define the relative positions among the objects, but they are allowed substantial flexibility with regard to the absolute positions and dimensions of the individual objects. Another criter
19、ion of the taxonomy is the content flexibility. At the very bottom, the contents are restrained to only pure image/text/graphic type. In the middle, different types of contents are allowed but they are kept largely static throughout the layout algorithms (for example, the text block width and the im
20、age aspect ratio are fixed). On the top, the contents can actively morph in the layout process to achieve the best overall layout. For example, the text blocks can take different widths, the images can be cropped to various aspect ratios, and the vector graphics can scale within a certain range. One
21、 possibility of content adaptation is to select the appropriate image and text contents in order to achieve good layouts 3. As shown in Figure 1, Active Layout Engine (ALE), the subject of this paper, depends on existing flexible templates, supports mixed types of contents, and allows a very high de
22、gree of content flexibility (mixed contents, variable aspect ratios of text and image blocks, non-rectangular text wrapping, etc.). 4 Figure 1: Taxonomy of document layout algorithms based on template and content flexibility ALE systematically calculates out the layout through mathematical optimizat
23、ion instead of trying out the layout. Along this direction, constraint solving is adopted. On the other hand, conventional constraint solving methods such as Simplex can only handle linear constraints. So a number of key innovations are introduced into ALE: Linear text block modeling enables the use
24、 of Simplex rather than other less efficient nonlinear constraint solving methods. Two-pass constraint solving algorithm effectively compensates for the inaccuracy introduced by linearization. Active Layout Template (ALT) provides a format-neural schema of describing adjustable layouts. Fixed copy h
25、ole Flexible template Template-free Content flexibility Pure image/text/ graphics Image, text, graphics Adaptive image, text, and graphics Template flexibility Photo Book Layout Simple Mail Merger Active Layout Engine 5 Section 2, 3, and 4 discuss the three key techniques in detail. Section 5 presen
26、ts several applications of ALE: document versioning, template-specific new layout generation, table formatting, and template-free catalog creation. Section 6 is devoted to the system optimization. Section 7 summarizes the paper and points out future research directions. 2. Linear text block modeling
27、 Different from many previous methods, we want to allow the individual text blocks to have variable widths in order to obtain the optimal layouts. On the other hand, such freedom in text block width poses a difficult technical challenge. When the text content in a rectangular block is fixed, the blo
28、cks width (w) and height (h) roughly follow w*h=a (a is a constant), which is a nonlinear relationship between w and h. The exact relationship is even more complex. h is not a continuous function of w and it instead follows a stepwise pattern, as shown in Figure 2. Figure 2: Non-linear relationship
29、between the width and height of a rectangular text block, given the text content This nonlinear relationship renders many efficient constraint solving methods such as Simplex useless. So our first strategy is to build linear models for the text block height-width 6 relationship. Based on the targete
30、d applications, there are two cases. For minor layout adjustment, we can use a single linear model to approximate the height-width function of a text block. For more dramatic layout modification or new layout generation, we have to use a cluster of linear models for each text block. 2.1. Use a singl
31、e linear model Let us assume the original width of a text block is 0 W and the original height is 0 H . Then we attempt another width 1 W. By accessing the line-breaking function of the rendering engine (for example, FOP 15, an open source software package that can parse and render XSL- FO documents
32、, is used in the current implementation), we can get the new height 1 H. In this way we have a linear approximation of the relationship between the width and height: H= 0 H+k*(W- 0 W) (1) where k=( 1 H- 0 H)/( 1 W- 0 W) 2.2. Use multiple linear models In minor layout adjustment, we can use a single
33、linear function to approximate the width- height function around the original layout. The situation is quite different in generating completely new layouts. Because we do not have any knowledge on the widths of the text blocks, using one linear function will result in intolerable errors (see Figure
34、3). 7 Figure 3: Using one linear segment to approximate the text block height-width relationship can result in large errors In order to reduce estimation errors, we use a cluster of linear functions to approximate the original nonlinear function. The following several steps are involved: Render the
35、text content at several different widths 1 w, 2 w, , n w and get corresponding heights 1 h, 2 h, , n h respectively. In the current implementation, five (w,h) combinations are sufficient. Fit the data points ( 1 w, 1 h), ( 2 w, 2 h), ( n w, n h) to a hyperbolic function h(w)=k/w+b (k and b are const
36、ant for given text content and format). k and b can be calculated using statistical regression method to achieve the least mean square error (LMS). Locate a number of sampling points on h(w)=k/w+b across the maximal allowed range of w. For example, we can find twenty sampling points with w in 50 poi
37、nts, 500 points. It is also preferred that the intervals between the heights of the sampling points are constant. Append a number of linear constraints for each text block to the existing constraints: This curve is approximated as a straight line based on samples around Point A Linear estimate will
38、have a large error at Point B, which is far away from Point A A B width height 8 height= hi+(hi-hi-1)*(width-wi-1)/(wi-wi-1), i=1, 19 (2) Figure 4 shows how a cluster of linear functions are used to approximate the hyperbolic function. It can be seen that if Equation 2 is satisfied for all of the ni
39、neteen linear functions, the original nonlinear constraint heightk/width+b will be fulfilled at a very high precision. It is worth noting that the convex nature of the hyperbolic function plays an important role. Otherwise we cannot approximate the nonlinear constraint with a cluster of linear const
40、raints. This is also why we first model the original nonlinear function as a hyperbolic function using regression and then sample the hyperbolic function to get the linear constraints instead of directly sampling the original nonlinear function. width height starty endy F(width,1) F(width,2) F(width
41、,m) Figure 4: Create a cluster of linear functions to cover the hyperbolic function One common text layout feature in professional designs is hyphenation. Both the single linear model and the multi-linear model can be applied when hyphenation is used by the text rendering engine. Of course, the para
42、meters k and b will be slightly different from those without hyphenation. 9 3. Two-pass constraint solving The linear models are just estimates and cannot guarantee completely correct layouts. Thus, we run two passes of constraint solving. Using the linear models of the text blocks, the first pass d
43、ecides the optimal width for each text block. Then through actual line-breaking, we can calculate the exact height for each text block. In the second pass, we fix the dimension of each text block and decide the final positions of the text blocks as well as the positions and sizes of the image blocks
44、. Figure 5 shows the workflow of the ALE. Figure 5: Workflow of Active Layout Engine The following example illustrates why the two-pass algorithm is necessary and how it works. The left side is the document containing the original contents. Then more text contents have been added to the two text blo
45、cks. The layout after the first pass is shown in the middle. As can be seen, this layout is roughly good with Block A expanded horizontally and Block B expanded vertically. The only problem is that the bottom of Block A overlaps with the title text under it. This is due to the approximate nature of
46、the linear models used in the first pass. After the second pass, the overlap problem has been corrected and the bottom image is cropped a little to make the extra room for the text content. In comparison, Figure 7 shows the result if the width of each text block is fixed. The text in Block B runs ou
47、t of space and is forced to occlude part of the image at the bottom. Active Layout Template Text Content and Style Linear Modeling 1st Pass Simplex Dimension Adjustment 2nd Pass Simplex 10 Layout with original Layout with original content Overlap due to estimate error of the linear model After the f
48、irst pass After the second pass A BB A Text block height is increased Image cropped to make extra room for the text Text block width is increased Overlap is fixed A B C D 11 Figure 6: Example of the two-pass constraint solving algorithm Figure 7: Result without adjusting text block widths 3.1. Const
49、raint solver We have chosen Cassowary solver 9 because of its several attractive features. First, it supports non-required constraints, such as “strong” and “weak” constraints, in addition to the conventional required constraints. This feature is very convenient in auto-layout systems. In layout adjustment, we can formulate “weak” constraints saying that the position of each object after adjustment should be the same as the original position, and “strong” constra