proposed method that allocates parts to each spread and determines their positions on a page. Finally, experimental results and concluding remarks are

Size: px

Start display at page:

Download "proposed method that allocates parts to each spread and determines their positions on a page. Finally, experimental results and concluding remarks are"

あゆみやたけ
6 years ago
Views:

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

Because these books are mainly prepared by volunteers and almost all steps in the preparation process are performed manually, they cannot be mass-produced.

1 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 896, Ikoma-shi, Nara , Japan Abstract Large-print textbooks are used by low vision students in school. Because these books are mainly prepared by volunteers 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 textbook involves () converting the size of figures and characters in the original textbook to one suitable for low vision students and (2) positioning them appropriately on the pages. In this paper, we propose a novel method for automatically optimizing a layout by employing a context structure. 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 sequencepair 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 preserved in the large-print textbook prepared. 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[] (Figure ). 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 chronical shortage of these books has been a social problem, especially in Japan. The procedure for preparing a LPT can be roughly divided into three steps: () extracting different parts, i.e., (a) Original Textbook (b) Large-Print Textbook Figure. Large-Print Textbook figures, tables, and text, from the original textbook (Figure (a)), (2) enlarging and highlighting the parts so that low vision students can easily read them, and (3) arranging 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 elaborate operations by well-trained volunteers are required. In this paper, we propose an automatic layout optimization method that can be used for preparing LPTs. The proposed method mainly substitutes step (3). Before applying the proposed method, we carry out the steps () 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 determined can be considered as a type of combinational optimization 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 introduces 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 provided in Section 3, and in Sections and, we describe the

2 proposed method that allocates parts to each spread and determines their positions on a page. Finally, experimental results and concluding remarks are presented in Sections 6 and 7. Original Textbook Context Structure Graph 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 proposed method. (a) Assign Parts to Each Spread Spread Spread 2 (b) Assign Parts to Left and Right Pages 2. Requirements Before introducing the requirements of layout optimization, 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 rectangles, 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 following characteristics have to be taken into account: The shape and size of figures and tables must be preserved 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.. 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.. Related parts should be placed near each other.. The positional relationship between parts should be determined by considering the context in the original textbook. Requirements and 2 are quite essential requirements, while requirements 3 - are natural requirements and are particularly very important for textbooks for children. (c) Determine Layout on Each Page Figure 2. Overview of Proposed Method 2.2 Related Studies Studies on automatic document layouts have been carried out in the past. Some of them employ a predetermined 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 arbitrary 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 context 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.. We introduce a context structure graph which represent 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 reduces the computational cost of optimization. 2

3 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 Section 3. Then, we conduct hierarchical optimization: (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 = {p i } and E = {e ij } denote a group of nodes and edges, respectively. Here, P corresponds to the parts in a textbook and E represents the contextual relationship between parts. We associate a weight w(i, j) with e ij. If the weight takes a high value, it means p i and p j are strongly related. An example of a context structure graph is shown in Figure 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) =.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. 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 beginning 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 appropriately. Subsequently, Step (b) is performed on the basis of the following formulation: minimize E = w(l, r)m(l, r) () l P L,r P R subject to a(i) A, a(i) A, (2) i P L i P R where P L and P R denote a group of parts on the left and right pages, respectively; a(i) and A denote the size of p i and each page, respectively. m(l, r) indicates the inappropriateness of the assigning of the parts: it takes a high value when p l and p r are interchanged. Because the number of parts in one spread is not large, typically to 20 parts, the number of all possible combinations 2 ( P L + P R ) is not large. Therefore, we search for the best combination from all possible combinations. Layout Optimization in Page Space The next step is to determine the position of the individual parts on a page, i.e., Step (c) in Figure 2. Similar to the previous section, we define an objective function that quantifies 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 concept of sequence-pair is discussed in Sections.2 and.3.. Objective Function As for the optimization of the layout of a page, we formulate the problem as follows: minimize E 2 = w(i, j)d(i, j), (3) (i, j) P age subject to Requirements and 2 in Section 2.. () In Equation 3, w(i, j) is the weight that indicates the strength of the relationship between p i and p j, and d(i, j) denotes the spatial distance between p i and p j in a page space. E 2 becomes small when related components are placed near each other. 3

Seq Generator 2 Layer Containing The Parts OK A L U R Rectangular Layer Vertical Constraint Graph Horizontal Constraint Graph B D Figure. Sequence Generator Figure.

The sequence-pair represents the relative positional relationship between rectangles by using a pair of character strings Γ +, Γ.

4 Seq Generator 2 Layer Containing The Parts OK A L U R Rectangular Layer Vertical Constraint Graph Horizontal Constraint Graph B D Figure. Sequence Generator Figure. Layout Generation Using Sequence- Pair[].2 Sequence-Pair For efficient optimization, we employ the sequence-pair proposed by Murata et al[]. 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 position of the parts, as shown in Figure. We can then position all the parts appropriately so that they meet the constraints. Originally the sequence-pair was used for LSI design and it was applicable only to a set of rectangles. In order to treat components with non-rectangular shapes, Murata et al. extended the method so that it could handle parts that consist of two or more rectangles[]. Because we assume that each part consists of two or more rectangles, we employ a sequence-pair in which each symbol corresponds to a rectangle..3 Sequence Generator The sequence-pair is a compact representation of the layout in a page space. However, we still have a problem: in order to find a suitable layout, we have to generate a variety of sequence-pairs, and there are some pairs that do not meet the requirements. To overcome this problem, we propose 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 relationships. One is about relationship between parts and is derived 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 layout optimization. In order to apply both constraints, the sequence generator has two layers: a layer containing parts and a rectangular layer. Figure 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 () generating a sequence-pair using the sequence generator, (2) computing the objective function E 2, and (3) iteratively performing Steps () and (2) until E 2 becomes sufficiently small. 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 original textbook, there were ten layouts of LPTs, each with a different value of E 2. Each of them were evaluated by teachers at a school for the blind. The teachers had considerable experience in teaching low vision students. In the evaluation, the teachers give a score to each layout. Scores 0 and 0 are the best and the worst scores, respectively. Figure 8 shows the relation between the score given by the teachers and E 2. The horizontal axis of the graphs indicates the average score of the teachers. As for page B, we can observe a positive correlation Note that we can have several possible results of the optimization, because 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 E 2 values.

線こうのけむりの動きから, ものが燃え続けているときには, たえず, びんの中に空気が流れこみ, びんの外に空気が出て燃え続けるように, 空いくことがわ気が, 入って出ていくかるようになっているものが燃え続けるには, たえず空気が入れかわる必要がある二酸化炭素によって白くにごった石灰水石灰水に, 二酸化炭素を少量ずつ入れて, 変化を確かめるアルコールランプの火が消えるの

5 線こうのけむりの動きから, ものが燃え続けているときには, たえず, びんの中に空気が流れこみ, びんの外に空気が出て燃え続けるように, 空いくことがわ気が, 入って出ていくかるようになっているものが燃え続けるには, たえず空気が入れかわる必要がある二酸化炭素によって白くにごった石灰水石灰水に, 二酸化炭素を少量ずつ入れて, 変化を確かめるアルコールランプの火が消えるの木や紙などが燃えるときにも, 二酸化炭素ができるか, 調べてみよう木や紙などに火をつけて, 石灰水を入れた集気びんに入れ, ふたをする 2 火が消えたらとり出して, 集気びんをふる石灰水は, 変化するかキャンプファイヤーの木の組みか 2 ものを燃やすはたらきがあるのは空気中のなにか空気は, ちっ素や酸素などの気体が混じり合ってできている空気の, およそはちっ素で, およそは酸素であるたは線こうのけむりの動きから, ものが燃え続けているときには, たえず, びんの中に空気が流れこみ, びんの外に空気が出ていくことがわかる燃え続けるように, 空気が, 入って出ていくようになっている石灰水に, 二酸化炭素を少量ずつ入れて, 変化を確かめるろうそくが燃えたあとの空気には, 石灰水を白くにごらせる気体ができているこの気体は, 二酸化炭素である二酸化炭素には, ものを燃やすはたらきはない二酸化炭素によって白くにごった石灰水ものが燃え続けるには, たえず空気が入れかわる必があるアルコールランプの火が消えるのはキャンプファイヤーの木の組みかたは 2 ものを燃やすはたらきがあるのは空気中のなにか木や紙などが燃えるときにも, 二酸化炭素ができるか, 調べてみよう木や紙などに火をつけて, 石灰水を入れた集気びんに入れ, ふたをする 2 火が消えたらとり出して, 周気びんをふる石灰水は, 変化するか線こうのけむりの動きから, ものが燃え続けているときには, たえず, びんの中に空気が流れこみ, びんの外に空気が出ていくことがわかるものが燃え続けるには, たえず空気が入れかわる必要がある燃え続けるように, 空気が, 入って出ていくようになっている石灰水に, 二酸化炭素を少量ずつ入れて, 変化を確かめる二酸化炭素によって白くにごった石灰水ろうそくが燃えたあとの空気には, 石灰水を白くにごらせる気体ができているこの気体は, 二酸化炭素である二酸化炭素には, ものを燃やすはたらきはないアルコールランプの火がキャンプファイヤーの, 木の組みかたは空気は, ちっ素や酸素などの気体が混じり合ってできている空気の, およそは木や紙など二度に火をつけて, 石灰水を入れた集気びんに入れ, ふたをする 2 火が消えたら取り出して, 集気びんをふる石灰水は変化するか Original A は空気は, ちっ素や酸素などの気体が混じり合ってできている空気の, およそはちっ素で, およそは酸素である A0 A02 A0 消えるのは 2 ものを燃やすはたらきがあるのは空気中のなにかちっ素で, およそは酸素である Objective Function E2 Page A ろうそくが燃えたあとの空気には, 石灰水を白くにごらせる気体ができているこの気体は, 二酸化炭素である二酸化炭素には, ものを燃やすはたらきはない木や紙などが燃えるときにも, 二酸化炭素ができるか調べてみよう Original B B0 B02 B0 Figure 6. Examples of Prepared Large-Print Textbooks Good Subjective Evaluation of Layout (a) Page A Page B Bad Objective Function E2 Figure 7. Layouts Evaluated as Being Poor by Teachers between E 2 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 () 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 effectiveness of the proposed method; the latter could not be discussed in this paper because of page limitation. Good Subjective Evaluation of Layout (b) Page B Figure 8. Relation between Subjective Evaluation and Objective Function Future work should focus on developing a fully automated system for the preparation of LPTs, that is, a system 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 suggestions 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 [] K. Fujiyoshi and H. Murata. Arbitrary convex and concave rectilinear block packing using sequence-pair. IEEE Trans. CAD, 9(2):22 233, [2] C. Jacobs, W. Li, E. Schrier, D. Bargeron, and D. Salesin. Adaptive grid-based document layout. ACM Transactions on Graphics, 22(3):838 87, [3] K. Marriott, P. Moulder, and N. Hurst. Automatic float placement in multi-column documents. In DocEng 07, pages 2 3, [] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. Rectangle-packing-based module placement. In Proc. IC- CAD, pages 72 79, 99. [] N. I. of Special Needs Education. A manual for making largeprint textbook (in Japanese) [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, Bad

Bull. of Nippon Sport Sci. Univ. 47 (1) Devising musical expression in teaching methods for elementary music An attempt at shared teaching

Bull. of Nippon Sport Sci. Univ. 47 (1) 45 70 2017 Devising musical expression in teaching methods for elementary music An attempt at shared teaching materials for singing and arrangements for piano accompaniment