Active Document Layout Synthesis [Lin, 2005]

Active Document Layout Synthesis [Lin, 2005] を読みました。
論文は http://www.hpl.hp.com/techreports/2005/HPL-2005-106.html から読むことができます。

前回の記事に引き続き、Document Layoutの自動生成についての論文です。
形式も前回の記事を踏襲していきます。

[Abstruct]

• 文書レイアウト解析は長年研究されているが、その逆である文書レイアウト合成はあまり研究されていない
• テキストブロックの高さと幅のトレードオフを最適に調節するようなレイアウト合成方法を提案する

[1. Introduction]

• 文書レイアウト解析 (Documet Layout Analysis, or DLA) では、まずテキストブロックの場所を特定し、その後各ブロック内の単語をOCRで認識する
• DLAの逆のタスクである文書レイアウト合成 Documet Layout Synthesis, or DLS)も面白いのではないか
• 文書のテキストと画像が与えられた時、それらを含むブロックの適切なサイズや位置はどのようなものか？
• DLSの目標は論理的に正しく(logically correct)、綺麗な見た目(aesthetically appealing)のレイアウトを作ること
• 先行研究([Jacobs et al., 2003], [Badros et al., 2001])では、テキストブロックの幅は固定 or テンプレートで決まる
• 提案手法では、ブロックの幅は固定しない。テンプレートは相対的な幅だけを定義する。

[2. Multi-linear Text Modeling]

• ページにn個の矩形ブロック B1, B2, ..., Bn があるとする
• S(Bi): Biの幾何学的性質（e.g., 高さや幅）
• P(Bi): Biの左上の角
• S(Bi)を固定する場合 (passive DLS) は、P(Bi)のみを調整してlayout quality functionを最適化すればよく、シンプレックス法で解ける
• 論文中でのlayout quality functionの具体的な実装については4章を参照
• S(Bi)も調整する場合 (active DLS) の難しさは、高さと幅の関係の非線形性にある
• ブロックの幅を連続的に狭くしていくと、ある時行数が増え、ブロックの高さが一気に（一文字分）増えるので、横軸に幅、縦軸に高さを取ると、幅と高さの関係は階段状になる（Figure 3）
• そこで、まずはシンプレックス法が使えるようにするため、高さと幅の関係を多重線形制約条件でモデル化する
• 経験上、高さ(h)と幅(w)の関係は双曲線関数のように振る舞い、レンダリングエンジンのデータなどをもとにすると h = k/w + b と表せる。ただし、k = 8360.6, b = -1.04
• 双曲線上にいくつかのサンプリングポイントを置いて、双曲線をカバーするような直線群を求める(Figure 4)

[3. Two-pass Constraint Solving]

• 2章にて幅と高さの関係を多重線形モデルに落とし込んだので、シンプレックス法が使える
• パラメタは各ブロックの幅、高さ、左端、上端
• レイアウトは2ステップで計算する
• i) 各テキストブロックの最適な幅をシンプレックス法で計算する　→　line-breakingをしてブロックの高さを得る
• ii) テキストブロックの高さと幅を固定してもう一度シンプレックス法を実行することで、各ブロックの最適な位置を得る

[4. Experimental Results]

• 実験で用いたテンプレートが要求する条件：
• 1) B2はB1の右側にある
• 2) 画像ブロックB1とテキストブロックB2の高さは同じ
• 3) B3の高さと幅は同じ
• 4) B3, B4, B5はB1, B2よりも下にある
• 5) B3, B4, B5の上端は揃っている
• 6) B3とB6は垂直方向に並んでいる (horizontally aligned)
• 7) 画像はアスペクト比が崩れないようにスケーリングできる
• 8) コンパクトなページを目指すため、全てのブロックが占めるスペースの高さを最小化する (これが2章で触れた layout quality function ですね)
• Figure 5, 6にこの手法を適用する過程が示されています

[5. Application to Table Formatting]

• Table Formatting とは、文書中の表のグリッドと内容が与えられた時に、表の各セルのサイズを決定する問題
• 今回のactive DLSの手法がTable formattingに応用できる
• 表をXML形式で記述する
• XMLの記述から制約条件を抜き出してテンプレートを作る
• active DLSの手法を適用する

[6. Conclusions]

5章までを簡単にまとめた感じなので省略します。

こんな感じでしょうか。シンプレックス法とか細かいこと忘れてたので思わずググってしまいました。

授業で習った時も嫌いだったなーこのあたりは…なんて思いながら…。

前回の記事の論文でも言えることですが、手法のしっかりとした評価がされていませんね。

私も文書レイアウトをするようなアルゴリズムを考えてみたいのですが、その際にそのレイアウトがどれほど良い物なのかを定量的に評価する方法は無いものでしょうか。