文書レイアウト解析

文書レイアウト解析 (英:Document layout analysis) は、コンピュータビジョンまたは自然言語処理では、テキスト文書のスキャン画像内の関心領域を識別および分類するプロセスである。読み取りシステムでは、テキスト領域を非テキスト領域からセグメント化し、正しい読み取り順序で配置する必要がある。文書に埋め込まれたテキスト本文、イラスト、数学記号、および表としてのさまざまな領域（またはブロック）の検出とラベル付けは、幾何学的レイアウト解析と呼ばれる。 ただし、テキストゾーンは、文書内でさまざまな論理的役割（タイトル、キャプション、脚注など）を果たし、この種のセマンティックラベリングが論理レイアウト解析の範囲です。

文書レイアウト解析は、幾何学的および論理的なラベル付けの組み合わせである。これは通常、文書画像がOCRエンジンに送信される前に実行されるが、大規模なアーカイブ内の同じ文書の重複コピーを検出したり、構造や画像コンテンツによって文書にインデックスを付けたりするためにも使用できる。

文書のレイアウトは、国際規格ISO 8613-1：1989で正式に定義されている。

方法の概要

文書レイアウト解析には、主に2つのアプローチがある。一つ目は、生のピクセルデータに基づいて文書を繰り返し解析するボトムアップアプローチである。このアプローチでは通常、最初に文書の白黒の境界領域を見つけ、領域を単語でグループ化し、次にテキスト行で、最後にテキストブロックでグループ化する。 もう一つのアプローチは、空白と幾何学的情報に基づいて文書を列とブロックに繰り返し分割するトップダウンアプローチである。

ボトムアップアプローチは従来のアプローチであり、文書の全体的な構造の仮定を必要としない利点がある。一方、ボトムアップアプローチでは、セグメンテーションとクラスタリングを繰り返す必要があり、時間がかかる可能性がある。 トップダウンアプローチはより新しく、文書の全体構造を直接解析するという利点がある。したがって、文書に表示される数百または数千もの文字/記号を繰り返しクラスター化する必要がない。このアプローチはより高速になる傾向があるが、それらが堅牢に動作するためには、通常、文書のレイアウトについていくつかの仮定を行う必要がある。 文書レイアウト解析のアプローチには、共通するノイズと回転という2つの課題がある。ノイズとは、ごま塩ノイズやガウスノイズなどの画像ノイズを指す。回転とは、テキスト行が完全に水平ではなく、文書画像を回転させる余地があることを指す。文書レイアウト解析アルゴリズムも光学式文字認識アルゴリズムも、文書画像内のテキスト行が水平であることを仮定している。したがって、回転が存在する場合は、文書画像を回転させて水平にすることが重要である。

したがって、文書レイアウト解析コードの最初のステップは、画像ノイズを除去し、文書の回転角度の推定値を作成することである。

ボトムアップアプローチの例

このセクションでは、1993年にO`Gormanによって開発されたボトムアップの文書レイアウト解析アルゴリズムの手順を説明する。 このアプローチの手順は次の通りである。

1. 画像を前処理して、ガウスノイズとごま塩ノイズを除去する。一部のノイズ除去フィルターは、コンマとピリオドをノイズと見なす場合があるため、注意が必要である。
2. 画像をバイナリ画像に変換する。つまり、各ピクセル値を完全に白または完全に黒に変換する。
3. 画像を黒いピクセルの連結成分に分割します。これらは画像のシンボルです。シンボルごとに、境界ボックスと図心を計算する。
4. 各シンボルについて、 k最近傍を決定します。ここでkは4以上の整数です。 O`Gormanは、堅牢性と速度の間の適切な妥協点として、彼の論文でk = 5を提案しています。少なくともk = 4を使用する理由は、文書内のシンボルの場合、最も近い2つまたは3つのシンボルが、同じテキスト行のすぐ隣にあるシンボルであるからである。 4番目に近いシンボルは通常、真上または真下の線上にあり、以下の最近傍計算にこれらのシンボルを含めることが重要である。
5. シンボルの各最近傍ペアは、一方のシンボルの重心からもう一方のシンボルの重心を指すベクトルによって関連付けられます。これらのベクターは、最近傍のシンボルのすべてのペアのためにプロットされている場合、その一つは、文書のためのdocstrum（以下を参照の数字）と呼ばれているものを取得する。また、水平からの角度Θと2つの最近傍シンボル間の距離Dを使用して、最近傍角度と最近傍距離のヒストグラムを作成することもできる。
6. 最近傍角度ヒストグラムを使用して、文書の回転を計算できる。回転が許容できる程度に小さい場合は、次の手順に進む。そうでない場合は、画像を回転させて回転を取り除き、手順3に戻る。
7. 最近傍距離ヒストグラムにはいくつかのピークがあり、これらのピークは通常、文字間間隔、単語間間隔、および行間間隔を表す。ヒストグラムからこれらの値を計算し保持しておく。
8. 各記号について、最も近い隣接記号を調べ、文字間間隔距離または単語間間隔距離の許容範囲内にある距離にある記号にフラグを付ける。フラグが立てられた最近傍シンボルごとに、それらの重心を結ぶ線分を描画する。
9. 線分によって隣接するシンボルに接続されたシンボルは、テキスト行を形成する。テキスト行のすべての重心を使用して、線形回帰でテキスト行を表す実際の線分を計算できる。テキスト行のシンボルのすべての重心が実際に同一線上にある可能性は低いため、これは重要である。
10. テキスト行の各ペアについて、対応する線分の間の最小距離を計算できる。この距離がステップ7で計算された行間間隔の許容範囲内にある場合、2つのテキスト行は同じテキストブロックにグループ化される。
11. 最後に、各テキストブロックの境界ボックスを計算でき、文書レイアウト解析が完了する。

レイアウト解析ソフトウェア

• OCRopus – C ++とPython、およびFreeBSD、Linux、Mac OS X用に実装された無料の文書レイアウト解析とOCRシステム。このソフトウェアは、ユーザーが様々な文書レイアウト解析やOCRアルゴリズムから選択できるプラグインアーキテクチャをサポートする。
• OCRFeeder – Pythonで記述されたLinux用のOCRスイートで、文書レイアウト解析もサポートしている。このソフトウェアは活発に開発されており、自由でオープンソースである。

関連項目

• 文書処理
• オープンドキュメントアーキテクチャ
• ページレイアウト

外部リンク

• Thomas M. Breuelによる高性能ドキュメントレイアウト分析、PARC、パロアルト、カリフォルニア、米国、2003年
• ドキュメント画像を理解するための幾何学的レイアウト分析手法：レビュー、ITC-irstテクニカルレポートTR＃9703-09、1998 。

脚注

• O'Gorman, L. (1993). “The document spectrum for page layout analysis”. IEEE Transactions on Pattern Analysis and Machine Intelligence 15 (11): 1162–1173. doi:10.1109/34.244677.