Context-oriented Layout Optimization of Large-Print Textbooks
Itaru Tatsumi
Hitoshi Habe
Masatsugu Kidode
Graduate School of Information Science, Nara Institute of Science and Technology
Takayama 8916–5, Ikoma-shi, Nara 630–0192, Japan
habe@computer.org
Abstract
Large-print textbooks are used by low vision students in school. Because these books are mainly prepared by vol-unteers and almost all steps in the preparation process are performed manually, they cannot be mass-produced. The chronic shortage of these books has been a social problem in Japan. The procedure for preparing a large-print text-book involves (1) converting the size of figures and char-acters in the original textbook to one suitable for low vi-sion students and (2) positioning them appropriately on the pages. In this paper, we propose a novel method for auto-matically optimizing a layout by employing a context struc-ture. We represent the context structure by using a graph called a context structure graph. The proposed method first allocates each material to an appropriate page, and then optimizes the layout of each page by using the sequence-pair method. Throughout these operations, we employ an objective function derived from the context structure graph to ensure that the context in the original textbook is pre-served in the large-print textbook prepared.
1
Introduction
When students with low vision read textbooks, they need to use assistive devices such as magnifiers, monoculars, telescopes, and video magnifiers. However it is quite hard for the students to look into these devices for long time. Therefore large-print textbooks (LPTs) are often used in schools in order to teach the students[5] (Figure 1). The figures and characters in the original textbook are enlarged and highlighted and then arranged on the pages of a LPT. These operations require highly contextual knowledge on the contents of the textbook. Since all LPTs are prepared by volunteers, they cannot be mass-produced. The chroni-cal shortage of these books has been a social problem, es-pecially in Japan.
The procedure for preparing a LPT can be roughly di-vided into three steps: (1) extracting different parts, i.e.,
(a) Original Textbook (b) Large-Print Textbook
Figure 1. Large-Print Textbook
figures, tables, and text, from the original textbook (Fig-ure 1 (a)), (2) enlarging and highlighting the parts so that low vision students can easily read them, and (3) arrang-ing these parts on the pages of the LPT so that the context of the original one is preserved in the LPT. Because each student has different levels of vision, operations (2) and (3) should be adaptively carried out for each student. All the above-mentioned steps are difficult to carry out and elabo-rate operations by well-trained volunteers are required.
In this paper, we propose an automatic layout optimiza-tion method that can be used for preparing LPTs. The pro-posed method mainly substitutes step (3). Before applying the proposed method, we carry out the steps (1) and (2) and represent the context structure of the original textbook, e.g., contextual relevance between a paragraph and a figure, by using a graph called a context structure graph. The final step in which the appropriate position of each part is de-termined can be considered as a type of combinational op-timization problem, and it requires volunteers to devote a lot of time and effort. If we achieve fully automated layout optimization, it will simplify the preparation of LPTs and their delivery to low vision students who are keen to study as non-handicapped students.
This paper is organized as follows. Section 2 first intro-duces the requirements for automatic layout optimization and related studies and presents an overview of the proposed method. The definition of the context structure graph is pro-vided in Section 3, and in Sections 4 and 5, we describe the
proposed method that allocates parts to each spread and de-termines their positions on a page. Finally, experimental results and concluding remarks are presented in Sections 6 and 7.
2
Automatic Layout of Large-Print Textbook
This section first discusses the requirements for the preparation of a LPT since our method should be designed so as to satisfy the requirements. Then, we discuss some related studies and finally provide an overview of the pro-posed method.
2.1
Requirements
Before introducing the requirements of layout optimiza-tion, we define some terms. The contents of a textbook can be divided into text, figures, and tables. Hereinafter let the word “parts” denote all of them. The shape of each part can be regarded as a combination of one or more rectan-gles, without loss of generality. Therefore, our problem is to determine the positions of these rectangles.
After a user determine the size of figures, tables, and text areas and when we optimize the position of them, the fol-lowing characteristics have to be taken into account:
• The shape and size of figures and tables must be pre-served during the layout optimization. If they consist of two or more rectangles, we cannot change the size of each rectangle and the positional relationship between them.
• The shape of the text can be changed as long as all the characters fit within the text area.
In order to prepare a reader-friendly textbook, we have the following requirements.
1. All parts must fit into the page space. 2. Each part must not overlap with another part. 3. Related parts should be positioned on a single page. 4. Related parts should be placed near each other. 5. The positional relationship between parts should be
determined by considering the context in the original textbook.
Requirements 1 and 2 are quite essential requirements, while requirements 3 - 5 are natural requirements and are particularly very important for textbooks for children.
Original Textbook
Context Structure Graph
(a) Assign Parts to Each Spread
Spread 1 Spread 2
(b) Assign Parts to Left and Right Pages
(c) Determine Layout on Each Page
Figure 2. Overview of Proposed Method
2.2
Related Studies
Studies on automatic document layouts have been car-ried out in the past. Some of them employ a predeter-mined guideline and roughly determine the position of each part[2, 3]. However, because textbooks for children have various kinds of layouts, it is difficult to determine and employ such information in our problem. Purvis et al. proposed an optimization method that generates an ar-bitrary layout that satisfies readers’ demand[6]; however, it requires a considerable amount of computational time because it involves solving a combinational optimization problem. This method does not take into account the con-text structure of an original document explicitly.
2.3
Overview of Proposed Method
In contrast to the method of Purvis et al., proposed method has the following two features.
1. We introduce a “context structure graph” which repre-sent the context structure of the original textbook. We also define an objective function that determines the quality of a designed layout.
2. We employ a “sequence-pair,” which efficiently re-duces the computational cost of optimization.
Original Textbook
Context Structure Graph G(P, E)
Paragraph Figure and Table
Caption
Figure 3. Context Structure Graph
Figure 2 presents an overview of the proposed method. First, we create the context structure graph discussed in Sec-tion 3. Then, we conduct hierarchical optimizaSec-tion: (a) we assign parts to each spread, (b) assign parts to the left and right pages, and (c) determine the layout, i.e., the position and shape (of text), on each page. This method efficiently solves a complex combination optimization problem.
We have to note that, in our current implementation, the size of all parts is manually determined beforehand. When we determine it, various factors including color, font and contrast should be taken into account in order for low vision students to read them easily.
3
Context Structure Graph
As discussed in the previous section, we introduce a graph that represents the context structure of the original textbook. Let G(P, E) denote the graph; P = {pi} and
E ={eij} denote a group of nodes and edges, respectively.
Here, P corresponds to the parts in a textbook and E rep-resents the contextual relationship between parts. We asso-ciate a weight w(i, j) with eij. If the weight takes a high
value, it means piand pjare strongly related.
An example of a context structure graph is shown in Fig-ure 3. In this example, we determined the weights of edges subjectively. For example, because we considered that all captions are strongly related with corresponding figures, we assigned w(i, j) = 1.0 for the edges which connects the captions and the figures. This weight assignment requires contextual knowledge about the original text and should be done manually. However, once we obtain the graph with weights, it can be applied to various situations, for example, even when we change the size of parts in order to provide a LPT for students with different level of vision, we can employ the same context structure graph.
Note that all the text nodes are connected by a single path, that is, there is no branch. The lack of branches allows easy reading for children, and therefore, no branches are introduced.
4
Alignment of Parts on Left and Right Pages
In our current implementation, Step (a) in Figure 2 is carried out by using a very simple method. From the begin-ning of the textbook, we trace edges that connect text nodes, and when the total size of traced text nodes and other nodes connected to the text nodes exceeds a certain threshold, we assign them to a spread. Then, we again resume tracing. Despite its simplicity, this method assigns parts appropri-ately.
Subsequently, Step (b) is performed on the basis of the following formulation: minimize E1= ∑ l∈PL,r∈PR w(l, r)m(l, r) (1) subject to ∑ i∈PL a(i)≤ A, ∑ i∈PR a(i)≤ A, (2) where PL and PR denote a group of parts on the left and
right pages, respectively; a(i) and A denote the size of pi
and each page, respectively. m(l, r) indicates the inappro-priateness of the assigning of the parts: it takes a high value when pland prare interchanged.
Because the number of parts in one spread is not large, typically 15 to 20 parts, the number of all possible combi-nations 2(|PL|+|PR|)is not large. Therefore, we search for
the best combination from all possible combinations.
5
Layout Optimization in Page Space
The next step is to determine the position of the individ-ual parts on a page, i.e., Step (c) in Figure 2. Similar to the previous section, we define an objective function that quan-tifies the appropriateness of the layout. However, because here we have a very large amount of possible layouts, that is, since we have a variety of combinations of all the parts, it is not practicable to determine the best combination from all possibilities. Therefore, we employ a sequence-pair that enables the efficient enumeration of the candidates; the con-cept of sequence-pair is discussed in Sections 5.2 and 5.3.
5.1
Objective Function
As for the optimization of the layout of a page, we for-mulate the problem as follows:
minimize E2=
∑
(i, j)∈P age
w(i, j)d(i, j), (3)
subject to Requirements 1 and 2 in Section 2.1. (4) In Equation 3, w(i, j) is the weight that indicates the strength of the relationship between piand pj, and d(i, j)
denotes the spatial distance between pi and pj in a page
space. E2 becomes small when related components are
Vertical Constraint Graph
Horizontal Constraint Graph
Figure 4. Layout Generation Using Sequence-Pair[4]
5.2
Sequence-Pair
For efficient optimization, we employ the sequence-pair proposed by Murata et al[4]. The sequence-pair represents the relative positional relationship between rectangles by using a pair of character strings Γ+, Γ−. For example,
(Γ+, Γ−) = (ab, ab) means that rectangle a is on the left
of b and (Γ+, Γ−) = (ab, ba) means that a is above b.
Once we have the sequence-pair of the given parts, we can obtain the vertical and horizontal constraints for the sition of the parts, as shown in Figure 4. We can then po-sition all the parts appropriately so that they meet the con-straints. Originally the sequence-pair was used for LSI de-sign and it was applicable only to a set of rectangles. In order to treat components with non-rectangular shapes, Mu-rata et al. extended the method so that it could handle parts that consist of two or more rectangles[1]. Because we as-sume that each part consists of two or more rectangles, we employ a sequence-pair in which each symbol corresponds to a rectangle.
5.3
Sequence Generator
The sequence-pair is a compact representation of the lay-out in a page space. However, we still have a problem: in order to find a suitable layout, we have to generate a vari-ety of sequence-pairs, and there are some pairs that do not meet the requirements. To overcome this problem, we pro-pose a method that generates sequence-pairs that satisfy the requirements. We call the method a sequence generator.
We have two kinds of constraints on locational relation-ships. One is about relationship between parts and is de-rived from the contextual flow of an original textbook. The other constraint is for the relation between rectangles in one part. These constraints have to be applied throughout the
Seq Generator U D R L
OK
NG
NG
NG
Layer Containing The Parts
Rectangular Layer
A
B 2
1
Figure 5. Sequence Generator
layout optimization. In order to apply both constraints, the sequence generator has two layers: a layer containing parts and a rectangular layer.
Figure 5 illustrates the basic concept of the sequence generator. On each layer, there are some queues. Suppose we have three parts A, B, and C and suppose that A has to be placed above B. In a sequence-pair, this is equivalent to the constraint pertaining to the order of A and B. We position such parts in a queue and preserve their order. When we generate a sequence-pair, we randomly select a part from the beginning of the queues. In this manner, sequence-pairs that satisfy the constraints can be generated.
In summary, our optimization algorithm involves (1) generating a sequence-pair using the sequence generator, (2) computing the objective function E2, and (3) iteratively
performing Steps (1) and (2) until E2becomes sufficiently
small1.
6
Evaluations
In this study, we evaluated our method. Here, because of page limitation, we demonstrate the validity of our objective function by comparing it with the result of the subjective evaluation performed by teachers.
We prepared LPTs, as shown in Figure 6. For one orig-inal textbook, there were ten layouts of LPTs, each with a different value of E2. Each of them were evaluated by
teachers at a school for the blind. The teachers had consid-erable experience in teaching low vision students.
In the evaluation, the teachers give a score to each layout. Scores 0 and 10 are the best and the worst scores, respec-tively. Figure 8 shows the relation between the score given by the teachers and E2. The horizontal axis of the graphs
indicates the average score of the teachers.
As for page B, we can observe a positive correlation
1Note that we can have several possible results of the optimization,
be-cause the sequence generator randomly chooses the order of parts. Hence, it would be more effective in practical applications that users choose the best layout from some candidates which have better E2values.
石灰水に，二酸化 炭素を少量ずつ入 れて，変化を確か める。 ろうそくが燃えたあとの空気には， 石灰水を白くにごらせる気体ができて いる。この気体は，二酸化炭素である 。二酸化炭素には，ものを燃やすはた らきはない。 二酸化炭素によって白 くにごった石灰水 木や紙などが燃えるときにも，二酸 化炭素ができるか，調べてみよう。 ① 木や紙などに火をつけて，石灰水を入れた集気び んに入れ，ふたをする。 ② 火が消えたらとり出して，周気びんをふる。 石灰水は，変化するか。 二酸化炭素によって白くに ごった石灰水 ろうそくが燃えたあとの空気には，石灰水を白 くにごらせる気体ができている。この気体は，二 酸化炭素である。二酸化炭素には，ものを燃やす はたらきはない。 石灰水に，二酸化炭素 を少量ずつ入れて，変 化を確かめる。 木や紙などが燃えるときにも，二 酸化炭素ができるか，調べてみよう。 ① 木や紙などに火をつけて，石灰水を入れた集気び んに入れ，ふたをする。 ② 火が消えたらとり出して，集気びんをふる。 石灰水は，変化するか。 石灰水に，二酸 化炭素を少量 ずつ入れて，変 化を確かめる。 二酸化炭素 によって白 くにごった 石灰水 ろうそくが燃えたあとの空気には ，石灰水を白くにごらせる気体が できている。この気体は，二酸化 炭素である。二酸化炭素には，も のを燃やすはたらきはない。 木や紙などが燃えるときにも，二酸 化炭素ができるか調べてみよう。 ① 木 や 紙 な ど 二 度 に 火 を つ けて，石灰水を 入 れ た 集 気 び んに入れ，ふた をする。②火が 消 え た ら 取 り 出 し て ， 集 気 びんをふる。 石灰水は変化 するか。 アルコールランプの火が 消えるのは・・・・・。 キャンプファイヤーの木の組 みかたは・・・・・。 ２・・ものを燃やす はたらきがあるのは 空気中のなにか 空気は，ちっ素や酸素などの気体が混 じり合ってできている。空気の，およそ はち っ素で， およ そ は酸素である。 5 4 51 線こうのけむりの動きか ら，ものが燃え続けてい るときには，たえず，び んの中に空気が流れこみ， びんの外に空気が出てい くことがわかる。 燃え続けるよう ものが燃え続け に，空気が，入 るには，たえず空 って出ていくよ 気が入れかわる必 うになっている がある。 。 線こうのけむ りの動きから， ものが燃え続 けているとき には，たえず ，びんの中に 空気が流れこ み，びんの外 に空気が出て 燃え続けるように，空 いくことがわ 気が，入って出ていく かる。 ようになっている。 ものが燃え続けるに は，たえず空気が入れ かわる必要がある。 アルコール ランプの火 が消えるの は・・・・。 キャンプフ ァイヤーの 木の組みか たは・・・。 ２・・ものを燃やすはたらきがある のは空気中のなにか 空気は，ちっ素や酸素などの気体 が混じり合ってできている。空気の， およ そ はちっ素で，およそ は 酸素である。 54 5 1
A01 A02 A10
B10 B02 B01 線こうのけむりの動きから，ものが 燃え続けているときには，たえず， びんの中に空気が流れこみ，びんの外に 空気が出ていくことがわかる。 ものが燃え続けるに は，たえず空気が入れ かわる必要がある。 燃え続けるように，空気 が，入って出ていくように なっている。 アルコールランプの火が 消えるのは・・・・。 キャンプファイヤーの， 木の組みかたは・・・。 ２・・ものを燃やすはたらきがあるのは空気 中のなにか 空気は，ちっ素や酸素などの気体が混じ り合ってできている。空気の，およそ は ちっ素で，およそ は酸素である。 54 5 1 ・・・・ ・・・・ Original B Original A
Figure 6. Examples of Prepared Large-Print Textbooks
Figure 7. Layouts Evaluated as Being Poor by Teachers
between E2 and the subjective evaluation. It implies that
our proposed objective function satisfactorily measures the quality of the designed layout.
In contrast, although we observe a positive correlation, there are two exceptions (enclosed within a red circle) in Figure 8 (a). There are two reasons for the bad score. Figure 7 shows them. First, two paragraphs, green boxes in Figure 7 (a), are placed next to each other. Because the readers can mistake these paragraphs to be a single paragraph, bad scores are given. Second, the width of one of the paragraphs is very narrow (see in Figure 7 (b)). Therefore, it is not easy to read the narrow paragraph.
Either the objective function or the sequence generator, or both, should be improved so that those factors can be considered in it.
7
Conclusions
We propose an automatic layout optimization method for preparing LPTs. It employs (1) a context structure graph for preserving the context of the original textbook and (2) a sequence-pair and a sequence generator for representing and designing possible layouts efficiently.
A subjective evaluation demonstrates the validity of the objective function and additional evaluations show the ef-fectiveness of the proposed method; the latter could not be discussed in this paper because of page limitation.
Page A
Subjective Evaluation of Layout
O b je ct ive F u n ct io n E2 Good Bad (a) Page A Page B
Subjective Evaluation of Layout
O b je ct ive F u n ct io n E2 Good Bad (b) Page B
Figure 8. Relation between Subjective Evalu-ation and Objective Function
Future work should focus on developing a fully auto-mated system for the preparation of LPTs, that is, a sys-tem that segments the parts from the original textbook and modifies them.
The authors thank Dr. Tetsuya Watanabe and Mr. Takeshi Kaneko of NISE, Japan, for their valuable sugges-tions and comments. The experiments discussed in Section 6 were conducted with the cooperation of teachers at the Nara Prefectural School for the Blind, Japan.
References
[1] K. Fujiyoshi and H. Murata. Arbitrary convex and concave rectilinear block packing using sequence-pair. IEEE Trans.
CAD, 19(2):224–233, 2000.
[2] C. Jacobs, W. Li, E. Schrier, D. Bargeron, and D. Salesin. Adaptive grid-based document layout. ACM Transactions on
Graphics, 22(3):838–847, 2003.
[3] K. Marriott, P. Moulder, and N. Hurst. Automatic float place-ment in multi-column docuplace-ments. In DocEng’07, pages 125– 134, 2007.
[4] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. Rectangle-packing-based module placement. In Proc.
IC-CAD, pages 472–479, 1995.
[5] N. I. of Special Needs Education. A manual for making
large-print textbook (in Japanese). 2005.
[6] L. Purvis, S. Harrington, B. O’Sullivan, and E. C.Freuder. Creating personalized documents: An optimization approach. In Proc. of 2003 ACM Symposium on Document Engineering, pages 68–77, 2003.
