Review of Automatic Document Formatting [N. Hurst et al., 2009]

Review of Automatic Document Formatting [N. Hurst et al., 2009] を読みました。
論文は http://dl.acm.org/citation.cfm?id=1600217 から読むことができます。

前回、前々回と文書レイアウトをどのように自動で生成するかということを論じた論文を読んできましたが、この分野を概観するのによさそうな論文を見つけたので、早速読んでみました。

[Abstruct]

• 文書自動整形の一般的な解決法は、制約最適化問題に落としこむことである
• 決定変数は要素の配置や幾何的関係の制約などをエンコードしたもの
• 目的関数はレイアウトのクオリティの基準となる
• 本論文では、上記テクニックを使った文書整形にフォーカスを当てる
• 関連した問題である自動テーブルレイアウトも扱う

[1. Introduction]

• World Wide Web (WWW) とVariable Data Printing (VDP) によって、文書自動整形の関心は line breaking などのミクロのものから、ページレイアウトのようなマクロのものへと移っている
• 文書を読む媒体の多様性が増している　→　文書自動形成の需要は高まっていくだろう
• 本論文で扱う問題: テキストの文書レイアウト、テーブルレイアウト
• 扱わない問題: ウィジェットレイアウト、ダイアグラムレイアウト、画像のリサイズなどの一時的な問題
• 文書自動形成は、次の3つの点で難しい
• 良いデザインの定量化
• レイアウトの計算は難しい (サブタスクであるテーブルレイアウトですらNP-hard)
• レイアウトツールのデザインと実装が複雑
• 文書自動整形と解く良い方法は制約最適化問題に違いない (Abstruct参照)

[2. Constrained Optimization]

• この章では、文書自動整形で用いられる制約最適化問題の解法を見ていく
• 変数の変域が実数である連続問題と、離散値をである離散問題、実数と離散値のどちらも取れる混合問題を分けて考える

2.1 Continuous problems

• 主な解法は変数消去法(Variable elimination)と反復法(Iterative techniques)
• 変数消去法
• 線形制約のような簡単な問題には適する、複雑な非線形問題には適さない
• 例: ガウス・ジョルダン法、シンプレックス法
• 反復法
• 極小値が最小値と保証されている凸包問題などに使われる
• 例: 最急降下法

2.2 Descrete problems

• 主な解法は Constructive Search と Local Search
• Constructive Search
• 参考文献: Artificial Intelligence: a Modern Approach [S. Russell and P. Norving, 2002]
• 例: A*アルゴリズム
• Local Search
• 参考文献: Handbook of metaheuristics [F. Glover and G. Kochenberger, 2003]
• 例: Trajectory method
• 上の2つの解法の詳細は、理解できていません。必要なら参考文献を読んだほうがいいかも。

[3. Micro-typography]

• カーニング、行分割、justificationなど、低レベルな構成のレイアウト
• 自動化された技術が実用化されている

3.1 Kerning

• 隣接文字との距離をどの程度取るかという問題
• 文字の Bounding Box だけを使って等間隔に配置すると、視覚的には文字間の距離が一定には見えないので、文字の見た目も考慮に入れる
• 文字間の距離を教えてくれるフォントも存在する
• しかし、以下のような理由で、カーニングを自動で行う需要はある
• 全てのフォントが、全てのフォントサイズでの文字間の距離を提供しているわけではない
• 提供された文字間隔では、矩形でなカットアウトに対処できない
• 提供された文字間隔では、複数のフォントが混ざったテキストに対処できない
• hz typesetting の kf-module や Adobe InDesign が自動カーニングを提供している
• 参考文献: 論文 References の [46, 81, 53, 32]

3.2 Line breaking

• どの単語（ハイフネーションが可能な場合は単語の途中も可）を行の終わりに置くかという問題
• first-fit 戦略
• 行に限界まで単語を順に詰めていく (Constructive Search の一種)
• Knuth-Plass アルゴリズム
• 参考文献: Breaking paragraphs into lines [D. Knuth and M. Plass]
• 行分割とハイフネーションを最適化問題として定式化し、動的計画法で解く
• TeXでも使われている (Knuthさんは、御存知の通りTeXの開発者です）
• 段落ごとに適用し、行の長さを均等にする
• ワード数がnで、1行に入る最大ワード数がkの時、最悪計算量 O(kn)

3.3 Line justification

• 行分割が決まったら、行の中での文字や単語の位置の微調整が必要（行の長さが多少は違っても良い場合はこのステップは省略可）
• フォントの大きさを変える、単語間/文字間のスペースの大きさを変える、alternative ligatures and glyphsを使う（？）、などの方法がある
• 一次元の連続最適化問題としてモデル化される
• TeXの場合、行はglue glopで仕切られたboxで構成されていると仮定
• 行に入る単語の長さに多じて、glue glopが伸び縮みする

[4. Macro-typography]

• レイアウトの見た目すべてを決める
• 文書の要素の配置方法、コンテンツの選び方、カラムの位置やサイズなど

4.1 Document and page layout models

• 閲覧メディアの違いにより、文書レイアウトのモデルも異なってくる
• 本論文では、次の4つのモデルを考える
• 固定サイズの1ページに使われるレイアウト（例：ポスター）
• 固定サイズで、枚数制限のないページに使われるレイアウト（例：ＰＤＦ文書）
• 固定幅、自由な高さの1ページに使われるレイアウト（例：HTML）
• 固定高さ、自由な幅の1ページに使われるレイアウト
• ページレイアウトモデルは、要素がとれる配置を規定する
• 座標(Coordinate)：各要素の位置を座標で指定。postscript, pdfなどで使われている。
• Flow：ページ上の一つのストリームに順に要素を置いていくモデル。
• Grid：テンプレートによって規定される軸に沿ったグリッドラインを使って各要素が配置される。雑誌やMicrosoft PowerPointなどで使われている。
• VH=Box：階層モデル。Boxは単純なオブジェクトか、垂直スタック、水平なシーケンスのいずれかとなる（？）。TeXで使われている。
• Guillotine：直交空間分割木(orthogonal space partition tree)という構造を使う。
• Box：ページを矩形領域の集合で表現する。VH=Box, Guillotine, Gridモデルの一般化。5章で扱うテーブルも、Boxレイアウトとみなされる。
• Macro-typographは2つのタスクで構成される
• ページレイアウトを選ぶ(つまり、ページに含まれる要素と、要素間の関係を選ぶ)
• レイアウトの微調整

4.2 Fine-tuning

• 基本的なページレイアウトが与えられた時に、それをどのように調整して違うコンテンツや違うスタイル、違うページサイズに適用させるか
• 連続的最適化が使われる
• One-way constraints
• $ x = f_x (y_1, \cdots, y_n) $
• Hierarchical multi-way propagation constraints [78, 79, 28]
• Linear arithmetic constraints [12, 43, 3, 4, 58]
• ... and so on... （すいません、よくわかんなかったです）
• イメージとしては、[Lin, 2005] のように工夫してページ内での制約を解くんだけど、その工夫の仕方はいろいろあるよ、ってことを言ってる？

4.3 Choosing a page layout

• ページにどのような要素を、どのようなレイアウトで配置するかを決める問題
• ページレイアウトの部分問題の中で一番難しい。離散的な問題。
• この節では、ページレイアウト選択の様々な方法が紹介されていますが、私の理解が追いついていいないこともあり、以下かなりかいつまんだまとめになっていますので、興味の有る方は是非元論文をあたってください。
• 浮動的な図をどう配置するか？
• 本文の参照箇所の近くに配置したい
• グリーディーに、一番最初に配置できる箇所に配置（TeXやHTMLで使われている）
• 図が参照と同じページに、無理な場合は次のページのなるべく近い位置に表示されるように最適化する方法も提案されている
• Optimal pagination techniques for automatic typesetting system [M. Plass, 1981]
• Pagination reconsidered [A. Bruggemann-Klein et al., 1995]
• 多段組での図の配置方法
• Automatic float placement in multi-column documents [K. Marriott et al., 2007]
• グリッドを用いた自動レイアウト
• A grid-based approach to automating display layout [S. Feiner, 1988]
• グリッドのようなレイアウトのテンプレートから良いものを選ぶ
• Adaptive grid-based document layout [C. Jacobs et al., 2003]
• 遺伝的アルゴリズムを使ったGuillotineページレイアウトの自動生成
• Automatic layout of variable-content print data [E. Goldenberg, 2002]
• ページレイアウトを記述する文法 [79, 44, 6, 51, 21]

4.4 Retargeting a page layout

• モバイル端末の発展により、小型ディスプレイ向けにページレイアウトを再描画する問題が生じてきている
• 主に2つの解決方法がある
• 全体のレイアウトを保ったまま、小さいバージョンを作る
• 全く新しいレイアウトを作りなおす
• レイアウトを作りなおす場合は、小型デバイス向けのレイアウトが用意されていることが多いので、そのレイアウトで作りなおす
• 元のページの見た目だけを手がかりにするのではなく、Document Object Model (DOM)などを用いた意味構造も参考にしてレイアウトを作りなおす
• Detecting web page structure for adaptive viewing on small form factor devices [Y. Chen et al., 2003]
• West: a web browser for small terminals [S. Bjork et al., 1999]
• 最近のシステムは文字色やフォントなどもレイアウトの参考にする [5, 80]
• 小さいバージョンを作るアプローチでは、スケーリングされたページが元のページと同じように見えるように頑張る
• 単純に小さくすると、テキストや画像などの要素が見えにくくなる
• スケーリングしたサムネイルと、ズーム領域を使う(Supporting memory for spatial location while reading from small displays [K. O'Hara et al., 1999])などの工夫が必要。

[5. Table Formatting]

• テーブル整形も、文書整形と同様に2ステップで考える
• 1. 多次元データから、テーブルの論理構造を決める
• 行や列の数、各セルの内容など
• 2. テーブルのレイアウトを決める
• 列の幅、行の高さなど。この時、2つの列の幅は同じ、などといった制約条件を課す。
• テーブルの自動レイアウトは、セルにテキストが含まれると計算量が多くなる（どこで開業するかで幅や高さが変わるから）　→　列の幅を決めてしまうことが多いが、決められないような状況もある

5.1 Column-driven layout

• Line justificationのTeXのアルゴリズムを使って、固定されてない列の幅の比率を決定
• 列の幅が決まると、各セルにコンテンツを置いてセルの高さも決定できる
• HTMLのテーブルの作成にはこのアルゴリズムが使われている
• HTML 4.01 SPecifiation, section 'Autolayout Algorithm'. http://www.w3.org/TR/html4/appendix/notes.html#h-B.5.2 [D. Raggett et al., 1999]

5.2 Cell-driven layout

• この節も全然理解できていないので、読む方は注意してください。
• 制約最適化の観点でテーブルレイアウトを捉える [8]
• セル中のテキストの行数が複数パターンある場合も考慮 [77]
• 高さが最小のテーブルレイアウトを見つける問題はNP完全 [1]
• ...他にもいろいろ紹介されていますが、よくわからないので省略させていただきます…。

5.3 Mininmal configurations

• セル中のテキストをどのように行分割するか？という話。

[6. Conclusions]

• micro-typographyの問題に対する最適化手法は実用化できるほど効率的
• 一方、macro-typographyの問題に対するそれは、まだ実用段階とは言えない
• ミクロとマクロのtypographicな問題をどう自動で組み合わせるかは今後の課題
• レイアウトの問題は相互に依存しあい、その計算量はとんでもないものになってしまう
• 良い自動レイアウトが利用できるような文書作成支援が必要

5章あたりは体力が切れてる感が否めませんね。

必要に迫られたら読みなおして、その部分を書き直したいと思います。

でもまあ、この分野を概観することはできたのではないでしょうか。

細かい手法などは全然理解していませんが、マクロなレイアウトとミクロなレイアウトがあるということ、それらのレイアウトを整形する際には制約最適化問題を解くことが多い、など、ざっくりしたことが分かっただけでもよかったです。

今回分かったアウトラインをもとに、次回以降、個別のレイアウト合成方法の論文を読んでみたいなーと思います。
今回出てきた最適化をどのように組み合わせているかを気にしながら読みたいですね。