JPH04248687A - 文書画像のレイアウト解析方法及びシステム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【産業上の利用分野】本発明は、レイアウトモデルを用
いた文書画像のレイアウト解析方法及びシステムに関す
る。

【０００２】

【従来の技術】大容量光デイスクを用いた文書ファイリ
ングシステムが実用化されている。電子化された文書画
像のデータベースは、従来の紙をベースにしたファイリ
ングに比べて、省スペース、分類、検索の容易性という
点で優れているのみならず、個々の情報を互に関連付け
たり情報の概念体系を構築することにより、より高度な
情報検索を行うことができるという利点を有する。しか
し、現在の市場に出回っているファイリングシステムは
、必ずしもこれらの要求を満たしているわけではない。 多くのシステムではページ単位で２値画像を格納し、オ
ペレータが個々の画像にインデックス、キーワードをつ
けるというのが一般的である。したがって、情報を体系
化して蓄積する機能としては、従来の紙をベースにした
ファイリングとなんら変わるところがない。各々の文書
画像は、情報の集積としてではなく、単なる絵として蓄
えられているにすぎない。

【０００３】より高度なファイリングシステムを構築す
るためには、文書画像から文書の内容を抽出することが
必要である。いわゆる文字認識の技術は既に成熟期にさ
しかかっており、かな漢字を含んだ印刷文書の認識では
マルチフォントの読み取りを完全に行えるシステムこそ
まだないけれども、ある程度機能を限定すれば９８％を
越える高率で読み取ることが可能な商用機が出回ってい
る。しかし、印刷文書の読み取りに関しては、認識以前
に文字部分と図表部分を分離し、読み取り順序を決定す
るセグメンテーションが重要かつ困難な問題である。さ
らに高度な情報検索を可能にするためには、単なる文字
部分と図表の分離にとどまらず、文書画像を意味的に一
様な領域に切り分け、かつ個々の領域が表題、著者名、
本文といった紙面の構成要素のうちのどれであるかを識
別するレイアウト理解が必要である。

【０００４】レイアウト理解の研究については、次のよ
うな方法が従来研究されている。 （Ａ）文書画像から特徴量を抽出しそれらの分布、規則
性から文字領域と図表領域を分離する方法や新聞記事等
の特殊な規則に則って書かれた文書について、その規則
を利用して記事を切り分ける（例えば、Ｋ．Ｉｎａｇａ
ｋｉ，　Ｔ．Ｋａｔｏ，　Ａ．Ｈｉｒｏｓｈｉｍａ，ａ
ｎｄ　Ｔ．Ｓａｋａｉ：　”ＭＡＣＳＹＭ：　Ａ　Ｈｉ
ｅｒａｒｃｈｉｃａｌ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉ
ｎｇ　Ｓｙｓｔｅｍ　ｆｏｒ　Ｅｖｅｎｔ−Ｄｒｉｖｅ
ｎ　Ｐａｔｔｅｒｎ　Ｕｎｄｅｒｓｔａｎｄｉｎｇ　Ｓ
ｙｓｔｅｍ，”　Ｐｒｏｃ．　７ｔｈ　Ｉｎｔ．　Ｃｏ
ｎｆ．　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，　
ｐｐ．６１２−６１４，　１９８４）。

【０００５】（Ｂ）文字領域をさらに構成要素に細分化
するために、書式定義言語を開発しこれを利用する（例
えば、東野、藤沢、中野、江尻：”矩形領域の集合表現
に基づく知識表現言語ＦＤＬと文書画像理解への応用，
”　信学技法、ＰＲＵ８６−３１、１９８６）。

【０００６】（Ｃ）構成要素の位置等の幾何的情報を盛
りこんだ木構造モデルとのすり合せによって構成要素の
認識を行う（例えば、Ａ．Ｄｅｎｇｅｌ　ａｎｄ　Ｇ．
Ｂａｒｔｈ：　”Ｈｉｇｈ　Ｌｅｖｅｌ　Ｄｏｃｕｍｅ
ｎｔ　Ａｎａｌｙｓｉｓ　Ｇｕｉｄｅｄ　ｂｙ　Ｇｅｏ
ｍｅｔｒｉｃ　Ａｓｐｅｃｔｓ，”　Ｉｎｔ．　Ｊｏｕ
ｒｎａｌ　ｏｆ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉ
ｏｎ　ａｎｄ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉ
ｇｅｎｃｅ，　２，４，　ｐｐ．６４１−６５５，　１
９８８、　　西村、高橋、小林　”木構造モデルによる
文書画像からの検索情報抽出，”　　信学技法、ＰＲＵ
８９−３４，　１９８９）。

【０００７】（Ｄ）ルールベースのエキスパートシステ
ムを枠組みとして用いる（例えば、黄瀬、杉山、馬場口
、手塚：　　”レイアウトモデルに基づく文書構造解析
，”信学論、７２−Ｄ２，７，ｐｐ１０２９−１０３９
、Ｄ．Ｎｉｙｏｇｉ　ａｎｄ　Ｓ．Ｎ．Ｓｒｉｈａｒｉ
：　”Ａ　Ｒｕｌｅ−Ｂａｓｅｄ　Ｓｙｓｔｅｍ　ｆｏ
ｒＤｏｃｕｍｅｎｔ　Ｕｎｄｅｒｓｔａｎｄｉｎｇ　Ｓ
ｙｓｔｅｍ，”　Ｐｒｏｃ．　ＡＡＡＩ，　ｐｐ．７８
９−７９３，　１９８６）。

【０００８】新聞という特殊な対象に特化した解析手法
を用いている（Ａ）の方式は、新聞固有のルールにこだ
わりすぎたために，一般文書に拡張するのは困難である
。 特に、過去において行われた新聞を対象としたレイアウ
ト理解は、新聞作成が写植から電算化される時代になっ
た現在では、実用性を全く失っている。書式言語を定義
した（Ｂ）の方式や構成要素の配置、抽出方法等を全て
ルールで書き下だす（Ｄ）の方式は、それぞれ書式言語
やル−ルを書けばどのような文書も解析することができ
、汎用的な手法といえる。しかし、書式の定義が大変煩
雑かつ柔軟性に乏しく、したがって文書の各ページにつ
いてこのような細かい記述をするのでは実用的とは言い
難い。

【０００９】（Ｃ）のＤｅｎｇｅｌの方式では、ユーザ
がレイアウトに関する知識として、簡単な木構造の構成
要素モデルを与え、システムがそれを基に解析を行うも
のである。多種類の文書に適用でき、かつモデルの記述
は（Ｂ）、（Ｄ）の方式より容易である。しかし、紙面
上で占める位置座標の情報を木構造モデルに組み込み、
それを積極的に利用しているので、構成要素の大きさの
変動や位置ずれに弱く、同一種類の文書でも場合によっ
ては複数のモデルが必要になる。

【００１０】同様に、西村らの方式でも構成要素の出現
が予想される場所の座標情報をモデルに与えており、上
記Ｄｅｎｇｅｌの方式と同様の問題点を持つ。さらに、
モデルとのすり合せの段階でＤＰマッチングを使ってお
り、構成要素の配置が１次元的な順序関係の部分（論文
のタイトル、著者名等）だけを解析対象としている。こ
の方式を表や特許公報のように構成要素が２次元的に配
置されている文書の解析に拡張すると、膨大な計算が必
要となる。

【００１１】すべてのレイアウト理解方式に共通して言
えることは、解析にあたって文書の構成要素に関する知
識（モデル）を与えてやらなければならないということ
である。そして、全ての文書に対処できるだけの膨大な
モデルを予め用意することは不可能なので、処理対象と
なる文書に応じてユーザにモデルを記述してもらうこと
を念頭におく必要がある。そこで、上記（Ｂ）、（Ｃ）
、（Ｄ）の方法は、書式が不定形な一般文書から、表の
ような特殊な書式を持ったものまで、様々な文書画像に
対し、構成要素を検出するために同一の手法を適用しよ
うとして、構成要素の位置情報を含む多くの情報を与え
て１つのモデルを指定しようとした。しかし、指定しな
ければならない情報が多いほど、ユーザはモデルを簡単
に指定できなくなる。

【００１２】また、実際の文書では、たとえ同一種類の
ものであっても、構成要素の位置や大きさが変動するこ
とが十分予想される。しかし、従来の方式のようにモデ
ルの記述が詳しくなると、１つのモデルでカバーできる
文書画像の範囲が狭まる。そこで、従来の方式では、そ
ういった変動に対応するために、同一種類の文書のため
に２以上のモデルを指定しなければならなかった。

【００１３】

【発明が解決しようとする課題】したがって、本発明の
目的は、モデルとしてトップダウンに与える情報が少な
くても、文書画像から構成要素を正確に検出することに
ある。

【００１４】本発明の他の目的は、１つのモデルでもっ
て、構成要素の位置または大きさの変動に十分対応する
ことのできるレイアウト解析方式を提供することにある
。

【００１５】本発明のさらに他の目的は、全く書式の異
なる文書であっても、与えるモデルを変えるだけで、レ
イアウトの解析を可能にすることにある。

【００１６】本発明のさらに他の目的は、機械の行う計
算量の増加を抑制しつつ、ユーザの負担を減少させるこ
とにある。

【００１７】

【課題を解決するための手段】本発明は、紙面の構成要
素が木構造で表わされる階層関係をなす文書画像のレイ
アウトを解析する方法であって、（ａ）構成要素相互の
位置関係データ、各構成要素の紙面上での存否に関わる
データ、各構成要素が含む文字列または直接の下位構成
要素の数に関するデータを含むレイアウトモデルを作成
し、（ｂ）文書の画像データを入力し、（ｃ）上記画像
データに基づいて文字列領域と一定の条件を満たす白ま
たは黒領域たるセパレータとを検出し、それらの位置デ
ータを発生させ　、（ｄ）上記文字列領域とセパレータ
の位置関係を制約として用い、上記レイアウトモデルが
含むデータと矛盾しないように、各文字列領域に最適な
構成要素名を割り当てるステップを含む。

【００１８】この方法では、文書画像から得られるボト
ムアップの情報を十分に利用しているので、モデルとし
てトップダウンに与える情報を少なくしても解析が可能
である。したがって、モデルの記述は非常に容易なもの
となり、記述が少ない分１つのモデルで広い範囲の文書
画像をカバーできる。

【００１９】また、画像の解析のために、区切りである
信頼性の高いセパレータと、信頼性の低いサブセパレー
タを区別して抽出している。そして、明確な区切りと考
えられるセパレータの情報を使いて文字列領域に割り当
てる構成要素名の候補を絞ることにより、文字列領域へ
の構成要素名の割当パターンが爆発的に発生するのを防
ぎ、要素の区切りを最終的に確定する段階でサブセパレ
ータの情報を取り込んだコスト関数を用いるという方式
により、レイアウト理解の効率の良さと正確さの両面を
実現する。

【００２０】極端な例では文書画像からセパレータが検
出されない場合も考えられるが、その場合でもレイアウ
トモデルとサブセパレータのデータから（弛緩法の効率
は悪くとも）正しい解析結果を得ることができる。

【００２１】

【実施例】１．レイアウトモデル 一般に、レイアウト理解において、紙面の各構成要素は
、文字列を内包する矩形として扱われる。そして、文書
画像のレイアウトを記述するのには、水平または垂直方
向に並んだ矩形の階層構造モデルを用いることが多い。 実施例でも、そのような従来の紙面の構成要素の扱い方
及びモデルの記述方法に基本的には従う。

【００２２】図１に論文第１ページのレイアウトモデル
の例を示す。各ノードは、論文第１ページの構成要素の
１つに対応し、当該構成要素の名前を割り当てることの
できる矩形の属性データを格納する。図１の木において
、同じレベルにあるノードは、その表わす構成要素の紙
面での上下または左右方向の順序にしたがって並べられ
ている。子であるノードは、親であるノードに対応する
矩形を水平又は垂直方向に切り分けた結果得られる矩形
に対応する。

【００２３】同じ種類の文書では、構成要素（表題、著
者名、本文等）の論理的な配置は変わらないが物理的な
位置、サイズはページによって異なる可能性がある。そ
こで、特定の構成要素が実際のページであったりなかっ
たりするような変動を吸収するために、ノードごとに、
そのノードの表わす構成要素が、モデルが表わすレイア
ウト中に必ず現れるか否かのデータを記憶しておく。さ
らに、実際のページで表題、著者名等の構成要素の行数
が変動するのを吸収するために、非ターミナルノード（
例えば図１の’Ｈｅａｄｅｒ’）ごとにその子ノードの
表わす構成要素が水平または垂直何れの方向に配置され
るかとその数の最小最大値についてのデータを記憶し、
かつターミナルノード（葉ノード、例えば図１の’Ｂｏ
ｄｙ’）ごとに、そのノードの表わす構成要素が内包す
る文字列が水平または垂直何れの方向に並ぶかとその数
の最小最大値についてのデータを記憶する。また、文字
列領域への構成要素の割り当て（ラベル付け）を正確か
つ迅速に行うためには、ターミナルノードごとに、その
ノードの表わす構成要素の上下左右に明らかに他の構成
要素との境となるセパレータが必ず存在するか否かのデ
ータを記憶しておくことが望ましい。

【００２４】以上、モデルが持つ情報をまとめると、次
のようになる。 （１）　　構成要素の紙面上での相対的位置関係（レイ
アウト木） （２）　　構成要素が必ず存在するか否か（３）　　非
ターミナルノードの子ノードの表わす、下位の構成要素
数の最大値と最小値、及びターミナルノードの表わす構
成要素が包含する文字列の数の最大値と最小値（４）　
　ターミナルノードの表わす構成要素の上下左右にセパ
レータがあるかどうか（ただし、たとえこのデータが全
くなくても、ラベル付けは可能である。）

【００２５】
図２は、図１のモデルの各ノードにセットされる情報を
表形式で表わしたものである。Ｎｅｓｔは木の深さ、Ｍ
ａｎ．は、そのノードの表わす構成要素がレイアウト中
に必ず存在するか（Ｙｅｓ）否か（Ｎｏ）を表わす。Ｄ
ｉｒ．は、非ターミナルノードについてはその子ノード
の表わす構成要素の配置が横並びか（Ｈｏｒ）縦並びか
（Ｖｅｒ）を表わし、ターミナルノードについてはその
ノードの表わす構成要素の包含する文字列の配置が横並
びか（Ｈｏｒ）縦並びか（Ｖｅｒ）を表わす。また、Ｅ
ｌｅｍｅｎｔは、そのノードがレイアウト木の非ターミ
ナルノードか（Ｄｕｍｍｙ）ターミナルノードか（Ｓｔ
ｒｉｎｇ）を表わし、Ｍｉｎ．Ｍａｘ．は、非ターミナ
ルノードについてはその子ノードの表わす構成要素の最
小、最大個数、ターミナルノードについてはそのノード
の表わす構成要素の包含する文字列の最小、最大個数を
表わす。ただし、実施例では後述するようにして文字列
数をカウントするので、Ｍｉｎ．Ｍａｘ．は、ターミナ
ルノードについては実質的にその対応する構成要素が紙
面で占める行の数の最小、最大値を表わす。Ｓｅｐａｒ
．は、そのノードの構成要素の左右上下（Ｌ，Ｒ，Ｔ，
Ｂ）にセパレータが必ず存在するか否かを示す。セパレ
ータのデータは、最低限ターミナルノードに格納してお
けばよいけれども、実施例では、非ターミナルノードに
も格納してある。非ターミナルノードのセパレータのデ
ータは、その直接または間接の子ノードであるターミナ
ルノードのセパレータのデータによって自動的に決定さ
れる関係にある。

【００２６】実施例では、上記（１）ないし（４）のデ
ータのほかに、ノードごとに、Ｒｅｃｏ．という項目の
データが記憶される。これは、レイアウト解析が終った
後で、そのノードの表わす構成要素に文字認識処理を施
すべきか（Ｙｅｓ）否か（Ｎｏ）を表わす。

【００２７】このように、本発明のモデルでは、構成要
素の紙面での位置、サイズについての座標情報を特に規
定する必要はない。勿論、紙面上の位置の具体的情報、
文字サイズや字体といった構成要素の内容についての情
報が与えられればより正確なラベル付け（矩形への構成
要素名の割り当て）ができるが、先に示した情報だけで
ほとんどの場合ラベル付けが可能である。モデルの定義
を極力簡単にして、できる限り少ない情報、すなわち構
成要素または文字列の並び方向とその数だけで矩形のラ
ベル付けができるようにするのが、本発明のポイントで
ある。

【００２８】木構造データの作成には、例えば、グラフ
ィックエディタを使って木構造を記述する公知の方法を
採用することができる。ノードに以上のデータをセット
した木構造は、記憶装置中に形成され、保持される。

【００２９】２．解析方法 図３にレイアウト理解のプロセスの概要を示す。まず、
文書画像データをレイアウト解析のためのシステムに入
力する（ステップ１０）。文書画像データは、スキャナ
を使って発生させてもよいし、既存の画像データベース
から取り出してもよい。次に、文書画像から、文字列、
縦横罫線、その他の黒画素領域が矩形として検出され、
その座標データが発生される（ステップ１２）。これ以
降の処理は、抽出されたこれら矩形の座標データを基に
行なわれる。発生された矩形の座標データから、構成要
素の区切り（セパレータ）となる長く幅のある白領域や
長い黒罫線を抽出する（ステップ１４）。図形領域を除
いた後に、抽出されたセパレータを用いて文字領域をお
おまかに区分けする（ステップ１６）。さらに、分割に
よって形成された個々の文字領域内で、行ピッチや文字
サイズの変化から構成要素の切れ目の候補（サブセパレ
ータ）を検出し、その座標データを求めておく（ステッ
プ１８）。ここまでの処理は、モデルに関係なく全ての
文書画像について共通に行なわれる。このようにして画
像から直接得られた情報とレイアウトモデルをもとに各
文字列矩形に構成要素名を表わすラベルをつけていく。 ラベル付けの時点で、先に求めた領域のおおまかな構成
と明らかに矛盾するようなラベル付けが生じた場合には
、該当するラベル及び関連するパスを弛緩法を用いて削
除する（ステップ２０）。整合性のあるラベル付けが終
わった時点でまだ複数ラベルが同一矩形に割り当てられ
ている時には、可能なラベルの割当パターンごとに、そ
の確信度をコスト関数により求め、最適な割当パターン
を決める（ステップ２２）。もし、文書画像とのすり合
わせの対象となるモデルが複数あるならば、モデルごと
にステップ２０と２２を実行して最適なラベルの割当パ
ターンとその確信度を求め、しかる後、求まった割当パ
ターンの中から、最も確信度の高いものを決定する。以
下、プロセスのステップ１２ないし２２について次に詳
しく述べる。

【００３０】・文字列抽出（ステップ１２）既に知られ
ている連結黒画素領域追跡法や黒ランレングス組み合わ
せ法によれば、文書画像から文字列、罫線、その他の黒
画素領域をすべて矩形で表現して抽出し、その座標デー
タを発生させることが可能である。例えば、特開平１ー
２５３０７７号公報及びＴ．Ａｍａｎｏ　ｅｔ．　ａｌ
，　”Ｍｅｔｈｏｄ　ｆｏｒｃｈａｒａｃｔｅｒ　ｓｔ
ｒｉｎｇ　ｄｅｔｅｃｔｉｏｎ”，　ＩＢＭ　Ｔｅｃｈ
ｎｉｃａｌ　Ｄｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ
　Ｖｏｌ．３３，　Ｎｏ．４，　ｐｐ．１４１−１４２
　（Ｓｅｐｔ．　１９９０）に開示された方法を使えば
、抽出された矩形のうち、（縦方向の）幅と（横方向の
）長さがそれぞれある最大値と最小値の間にあるという
条件を満たすものが文字列領域として、幅がある閾値以
下で長さがある閾値以上のものが横罫線領域として、幅
がある閾値以上で長さがある閾値以下のものが縦罫線領
域として認識される。

【００３１】・セパレータ抽出（ステップ１４）文字列
、縦横罫線等の矩形データを基に、白画素領域を囲む矩
形集合を求める。近接し、高さがほぼ同じ白画素矩形同
志は統合した後に、長さと幅がそれぞれ所定の基準に達
する矩形の全てを縦或は横のセパレータとして登録する
。具体的には、まず画像の上端から下端まで延びる縦の
セパレータを検出し、その位置データを求め、登録する
。次に、そのようにして抽出された縦のセパレータに両
端が接する横のセパレータを検出し、その位置データを
求め、登録する。次に、そのようにして抽出された横の
セパレータに両端が接する縦のセパレータを検出し、そ
の位置データを求め、登録する。以下、縦と横のセパレ
ータを交互に抽出することを繰り返す。例えば、図４に
示すページからは、便宜上太線でその概略的位置を示す
セパレータが抽出される。以上の過程に続けて、または
それと並行して、一定長さ以上の縦または横の黒罫線も
セパレータとして登録される。

【００３２】抽出されるセパレータは、続けて行われる
領域分割の誤りを防ぐために、構成要素の区切りである
信頼性の高い（幅が広く長い）ものであることが要請さ
れる。幅や長さの閾値は、そういった観点から選ばれる
ものであり、同じ種類に属する文書画像中の白画素矩形
の大きさの分布を調べて、最適な値を定めるのが望まし
い。

【００３３】・おおまかな領域分割（ステップ１６）縦
横のセパレータのデータを基にして、文字領域の切り分
けを行う。分割に先立って、抽出されたセパレータと文
字列等の矩形の分布から、図形領域を特定し処理対象か
ら除く。既に知られているように、黒画素分布の複雑さ
等の特徴量を使って、図形領域を文字領域と分離するこ
とがが可能である。

【００３４】文字領域の分割は、次のようにして行われ
る。まず、図形領域を除いた画像全体を２以上の領域に
分割する縦のセパレータが存在すれば、これを用いて画
像を分割する。次に、分割により形成された領域の何れ
かに、それを２以上の領域に再分割できる横のセパレー
タがあれば、その領域をさらに小さな領域に分割する。 このように、縦と横のセパレータを交互に使いながら再
帰的に分割を繰り返し、画像全体を木構造を成す領域群
に分ける。図４に示される例では、まずセパレータＳ１
を用いて、文字領域が領域Ａ、Ｂ、Ｃ、Ｄに分割される
。次に、セパレータＳ２を用いて、領域Ｃが領域Ｃ１と
Ｃ２に再分割される。

【００３５】・サブセパレータ検出（ステップ１８）こ
こでは、まず、分割により形成された領域ごとに、当該
領域に属する各文字列矩形について、当該文字列矩形の
文字サイズ及び当該文字列矩形を代表する線であるベー
スラインのデータを発生させる。次に、文字サイズが直
上の文字列のそれと異なる文字列を検出する。そして、
検出された文字列の上にある白領域を横のサブセパレー
タとして検出し、その位置データを登録する。それに続
いて、またはそれと並行して、縦方向に関して相隣接す
る文字列同士の間の白領域ごとに、ピッチデータを発生
させ、直前のピッチと異なるピッチを持つ白領域を横の
サブセパレータとして検出し、その位置データを登録す
る。また、縦方向に規則正しくならんだ二つの文字列群
を分離する、セパレータよりは小さいけれども一定の大
きさ以上の白領域が検出された場合にはそれを縦のサブ
セパレータして登録しておく。例えば、図４に示すペー
ジからは、便宜上破線でその概略的位置を示すサブセパ
レータが抽出される。サブセパレータは、構成要素の区
切りとしてセパレータを補完するという性格を持つ。し
たがって、セパレータのように検出条件が厳格である必
要はなく、冗長な候補が登録されても構わない。

【００３６】・弛緩法を用いたラベリング（ステップ２
０） ここでは、抽出された文字列矩形の相対的な位置関係と
セパレータを制限条件として、レイアウトモデルに従っ
て、可能なラベルを、各文字列につけていく。具体的な
制限は、以下の通りである。

【００３７】（ａ）ラベル間の相対的位置関係及びラベ
ルの数は、レイアウトモデルのノード相互の配置関係及
びＭｉｎ．Ｍａｘのデータと矛盾しない。

【００３８】（ｂ）セパレータを越えて同じラベルが連
続することはない。（ただし、セパレータの誤検出に対
処するため、他に適当なラベルが付けられない場合には
、セパレータを越えて同一ラベルが連続することも可能
とする。）

【００３９】（ｃ）構成要素の周囲にセパレータが必須
であるか否かに関わるデータがモデルに含まれる場合に
は、そのデータと矛盾しない。

【００４０】一般に、離散的弛緩法では、始めに単項制
限条件を満たす可能な全てのラベルを各対象に付け、そ
の後で関連制限条件を用いて整合性の無いラベルの組合
せを刈っていくけれども、ここではラベルづけの時点か
ら上記条件（ａ）ないし（ｃ）のすべてを満足するラベ
ルだけを、文字列矩形に付けていく。

【００４１】図５と図６を使って、縦方向のラベリング
の具体例を説明する。実際に論文の第１ページの画像か
ら得られた文字列矩形を図５に、論文第１ページのため
のレイアウトモデルのデータの一部を図６に示す。（図
５では、文字列１の上等の位置にある、ページ全体を囲
んでいるセパレータの図示を省略している。）レイアウ
トモデルの木構造の左上ノードから順に、該当する文字
列矩形にラベルを割り当てる。具体的には、次のように
して割当が行われる。

【００４２】（ｉ）モデルから、紙面の最も上にある、
ｄｕｍｍｙでない構成要素は’Ｔｉｔｌｅ’であり、そ
れに含まれる文字列は、最大３個で、縦方向に並ぶこと
がわかる。したがって、文字列１、２、３にＴｉのラベ
ルをつける。

【００４３】文字列４へのラベル付けについて説明する
。文字列４は、今ラベルＴｉを付けた文字列３の右に位
置する。’Ｔｉｔｌｅ’の親である’Ｐａｐｅｒ’のノ
ードを調べると、その’Ｄｉｒ’のデータは’Ｖｅｒ’
であるので、その下位の構成要素である’Ａｕｔｈｏｒ
’は、’Ｔｉｔｌｅ’に対して下にしか位置し得ない。 よって、この場合、文字列４は、Ｔｉのラベルを付けざ
るを得ない。これは、文字列４は、本来、文字列３と統
合されるべきであったことを意味する。したがって、文
字列４にＴｉのラベルを付すけれども、ラベルＴｉを付
けた文字列のカウントは増やさない。このように、文字
列の（仮想的な）統合可能性を、モデルとセパレータの
データに基づいて的確に判断できることが、本発明の大
きなメリットである。

【００４４】（ｉｉ）モデルから、次の構成要素’Ａｕ
ｔｈｏｒ’は、’Ｔｉｔｌｅ’より下にあり、その含む
文字列は最大３個で、縦方向に並ぶことがわかる。Ｔｉ
が文字列４までつく可能性があるので、ラベルＡｕを文
字列２、３、４、５につける。文字列３にラベルＡｕを
付けたなら、文字列４にも同じラベルを付けざるを得な
いこと、そして文字列は１つと数えることは、（ｉ）の
場合と同じである。相対的な位置関係から言えば、もう
一行下の文字列６、７にもＡｕのラベルを付け得るけれ
ども、ここではセパレータによって領域が変わっており
、セパレータを挟んで同じラベルが続かないという規則
（ｂ）にしたがい、文字列６，７にはＡｕのラベルを付
けない。

【００４５】（ｉｉｉ）同様に、その次の構成要素’Ａ
ｆｆｉｌｉａｔｉｏｎ’のラベルＡｆは、文字列３、４
、５に付けられる。ラベルＡｕが文字列５についている
ので、構成要素’Ａｕｔｈｏｒ’がそこで終り、セパレ
ータで隔てられた別の領域である文字列６、７から構成
要素’Ａｆｆｉｌｉａｔｉｏｎ’が始まる可能性を、検
討しなければならない。そこで、次のターミナルノード
を調べると、構成要素’Ｂｏｄｙ−Ｃｏｌｕｍｎ’の上
にはセパレータがなければならない、つまり、構成要素
’Ｔｉｔｉｌｅ’から’Ａｆｆｉｌｉａｔｉｏｎ’まで
は、横セパレータでその下が仕切られた１つの領域に収
っていなければならないことがわかる。そこで、ラベル
Ａｆを付けるのは、文字列５までとする。

【００４６】さて、ラベル付けは続いて構成要素’Ｂｏ
ｄｙ−Ｃｏｌｕｍｎ’に関して行われるわけだが、上記
制限条件（ｃ）を満足するためには、紙面上で最も左に
ある’Ｂｏｄｙ−Ｃｏｌｕｍｎ’（そのラベルをＢＣ１
とする）は文字列６から始まるしかない。したがって、
文字列６のラベルはこの時点でＢＣ１に決定する。文字
列６のラベル決定にともなって、既にラベルをつけた文
字列１−５についても関連条件によりさらにラベルを絞
りこむことができる。このように、ラベルが一意に決定
した文字列が現れた時点で関連条件を逐次伝搬させ、弛
緩法によりラベル刈りを行う。図５の例では、文字列６
のラベルがＢＣ１に決定したことにより、文字列５のラ
ベルはＡｆに決定する。さらに、構成要素’Ａｕｔｈｏ
ｒ’は必ず存在するから、文字列３、４のラベルがＴｉ
でないことが決定される。このようにして、ラベル付け
と弛緩法を繰り返しながら、整合性のとれたラベルが全
文字列に対して付けられる。次に、図７と図８を使って
、縦方向のラベリングの具体例を説明する。実際の文書
画像から得られた文字列矩形を図７に、そのページのた
めのレイアウトモデルのデータの一部を図８に示す。（
図７では、文字列１、２、３、４の上等の位置にある、
ページ全体を囲んでいるセパレータの図示を省略してい
る。）

【００４７】モデルから、文字列を直接の下位要素とす
る構成要素は３つあって、横方向に並び、何れもその右
と左にセパレータを持つことがわかる。しかし、この画
像からは、文字列同士の間にセパレータが全く抽出され
ていない。そこで、このようにあるべき数のセパレータ
が抽出されていない場合には、構成要素の切れ目として
サブセパレータを使うことにする。

【００４８】今、図７のサブセパレータ（ＳＳＰ）Ａ、
Ｂ、Ｃのうち、Ｃだけは一定値を越える幅（横方向の長
さ）を持っており、ＡとＢの幅はその一定値に達してい
ないとする。このとき、サブセパレータＣは他のサブセ
パレータよりも構成要素の区切りである蓋然性が高い。 そして、サブセパレータＣを確定的にセパレータとして
扱っても、図７に示す画像の中でセパレータが多すぎる
ことにはならない。そこで、以下の処理では、サブセパ
レータＣをセパレータとみなすことにする。

【００４９】さて、モデルから、構成要素’Ｉｔｅｍ１
’は、必ず存在し、かつ他の構成要素’Ｉｔｅｍ２’、
’Ｉｔｅｍ３’よりも左に位置する。しかも、サブセパ
レータＡをセパレータとして扱うことは可能であるから
、’Ｉｔｅｍ１’のラベルＩｔ１を文字列１、５、９に
対して付け得ることがまずわかる。しかし、サブセパレ
ータＡまたはＢをセパレータとして扱うことの可否は、
この時点では確定していない。 つまり、文字列２、３は、本来文字列１とともに１つの
文字列矩形として認識されるべきであった可能性が存在
する。そこで、文字列２、３にもラベルＩｔ１を付けて
おく。そのようなラベル付けが許されることは、上記（
ｉ）で説明したとおりである。同様に、文字列６、７、
１０にもラベルＩｔ１を付けておく。上記規則（ｂ）か
ら、文字列４、８、１１にラベルＩｔ１を付けることは
しない。次に、構成要素’Ｉｔｅｍ２’についてモデル
を調べると、これは必ず構成要素’Ｉｔｅｍ１’の右に
登場することがわかる。 よって、まずラベルＩｔ２を文字列２、６と文字列３、
７、１０に付ける。また構成要素’Ｉｔｅｍ１’が文字
列３、７、１０まで続く場合には、文字列４、８、１１
が構成要素’Ｉｔｅｍ２’に含まれる可能性もあるので
、それらにラベルＩｔ２を割り当てておく。次に、構成
要素’Ｉｔｅｍ３’についてモデルを調べると、これは
必ず’Ｉｔｅｍ２’の右に登場することがわかる。よっ
て、ラベルＩｔ３を割り当てることができるのは、文字
列３、７、１０、４、８、１１であることがまずわかる
。次に、ラベルＩｔ３の右横に続くラベルのないことが
レイアウトモデルからわかるので、上記規則（ｂ）も考
慮すると、ラベルＩｔ３は文字列４、８、１１だけに割
り当てられることがわかる。その結果、Ｉｔ３の直ぐ左
にＩｔ１のラベルがつくことはモデルと矛盾するので、
ただちに弛緩法によって文字列３、７、１０はＩｔ２に
決定する。

【００５０】・優先順位の決定（ステップ２２）レイア
ウトモデルのデータとの整合性だけからでは、必ずしも
どの文字列矩形についてもそれに付すラベルを１つに絞
りこめるわけではない。図５と図７の例でも、ある文字
列については複数のラベルがついたままである。 そこで、可能なラベルの割当パターンのそれぞれについ
て、ラベルの変化点とセパレータ、サブセパレータがど
れ位一致しているかを評価するコスト関数を導入し、割
当パターンの順位付けを行う。例えば、図５に示す文字
列１、２、３、４、５に関して、可能な割当パターンは
、 Ｔｉ−Ｔｉ−（Ａｕ−Ａｕ）−Ａｆ　　（１）　Ｔｉ−
Ａｕ−（Ａｕ−Ａｕ）−Ａｆ　　（２）　Ｔｉ−Ａｕ−
（Ａｆ−Ａｆ）−Ａｆ　　（３）　　　　（）内は同一
行を示すの３通りである。いま、例えば次のようなコス
ト関数を考える。

【００５１】 ＝＝　　：　イコール ！＝　　：　ノットイコール ｎ　　　：　ｎ番目の文字列 Ｆｎ　　：　コスト関数 Ｃｎ　　：　ｎ番目と（ｎ＋１）番目の文字列について
のコストＬｎ　　：　ｎ番目の文字列に対するラベルＳ
ｅｐ　：　ｎ番目と（ｎ＋１）番目の文字列との間にサ
ブセパレータが存在する Ｎｏｎｅ：　ｎ番目と（ｎ＋１）番目の文字列との間に
サブセパレータが存在しない Ｓａｍｅ：　ｎ番目と（ｎ＋１）番目の文字列とが同一
行に存在するｗ　　　：　横（或は縦）のサブセパレー
タの幅ｐ　　　：　ペナルティー

【００５２】図５に示すように、文字列２、３の間にサ
ブセパレータ（高さｗ１とする）があり、さらに文字列
３、５の間にサブセパレータ（高さｗ２とする）がある
場合、各割当パターンのコスト関数の値は、 （１）　＋ｐ　＋ｗ１　＋０　＋ｗ２　＝　＋ｗ１＋ｗ
２＋ｐ（２）　−ｐ　−ｗ１　＋０　＋ｗ２　＝　−ｗ
１＋ｗ２−ｐ（３）　−ｐ　＋ｗ１　＋０　−ｗ２　＝
　＋ｗ１−ｗ２−ｐである。したがって、割当パターン
（１）が最も確からしいことがわかる。

【００５３】図７の場合も、全く同様にして縦のサブセ
パレータの存在と幅をもとにコスト関数が定義される。 そのコスト関数を用いれば、文字列２、６がＩｔ１とＩ
ｔ２のどちらであるかを決定することができる。

【００５４】文字列２、６のラベルがＩｔ２に決定され
た場合、後の文字認識処理では、構成要素’Ｉｔｅｍ１
’に関して、当然のことながら、文字列１、５、９の順
で行われる。これに対し、文字列２、６のラベルがＩｔ
１に決定された場合には、後の文字認識処理は、構成要
素’Ｉｔｅｍ１’に関して、文字列１、２、５、６、９
の順で行われる。

【００５５】最後に、日本国特許庁発行の公開特許公報
の第１ページについて行ったレイアウト理解の実験デー
タを紹介する。使ったレイアウトモデルが含むデータは
、図９に示す通りである。パーソナルコンピュータ（Ｃ
ＰＵはインテル社の８０３８６　　２０ＭＨｚ）による
処理速度は、３００ｐｅｌ／ｉｎｃｈでスキャンした２
４００ｘ３６００ドットの画像について、文字列領域抽
出に約１０秒を要し、それ以降の処理（セパレータとサ
ブセパレータの抽出、領域分割、ラベル付けと弛緩、優
先順位付け）には平均約１秒弱を要しただけであった。

【００５６】

【発明の効果】本発明によれば、モデル上で構成要素の
座標位置等の厳密な指定を行わなくても、文書画像の構
成要素への切り分けが可能である。したがって、モデル
の記述が容易である。しかも、１つのモデルでもって、
構成要素の位置または大きさの変動に十分対応すること
ができる。したがって、同一種類の文書が１つのモデル
で解析できることは勿論、構成要素の順序、相対的な位
置関係さえ同じであれば、同じモデルで異なる種類の文
書画像も処理可能である。また、モデルさえ記述できれ
ば、縦横いかなる構成要素の並びを持つ文書画像でも処
理することができる。

【図面の簡単な説明】

【図１】レイアウトモデルのノードの配置例を示す図で
ある。

【図２】図１の各ノードに格納されるデータの説明図で
ある。

【図３】レイアウト理解のプロセスを示す流れ図である
。

【図４】セパレータとサブセパレータの説明図である。

【図５】縦方向のラベリングの説明図である。

【図６】図５の画像を解析するためのレイアウトモデル
の説明図である。

【図７】横方向のラベリングの説明図である。

【図８】図７の画像を解析するためのレイアウトモデル
の説明図である。

【図９】実験で用いたレイアウトモデルの説明図である
。

【符号の説明】

Ｓ１、Ｓ２　　セパレータ

Claims (29)

【特許請求の範囲】
1. 【請求項１】紙面の構成要素が木構造で表わされる階層
   関係をなす文書画像のレイアウトを解析する方法であっ
   て、（ａ）構成要素相互の位置関係データ、各構成要素
   の紙面上での存否に関わるデータ、木構造の葉に位置す
   る構成要素のそれぞれごとの、当該構成要素が含む文字
   列の数に関するデータ、及び木構造の節点に位置する構
   成要素のそれぞれごとの、直接の下位構成要素の数に関
   するデータを含むレイアウトモデルを作成し、（ｂ）文
   書の画像データを入力し、（ｃ）上記画像データに基づ
   いて文字列領域と一定の条件を満たす白または黒領域た
   るセパレータとを検出し、それらの位置データを発生さ
   せ、（ｄ）上記文字列領域とセパレータの位置関係を制
   約として用い、上記レイアウトモデルが含むデータと矛
   盾しないように、各文字列領域に最適な構成要素名を割
   り当てるステップを含む方法。
2. 【請求項２】上記ステップ（ｄ）では、同じ構成要素名
   を持つ文字列領域は、セパレータを越えて続かないとい
   う制約にしたがう請求項１記載の方法。
3. 【請求項３】上記レイアウトモデルは、木構造の葉に位
   置する構成要素のそれぞれごとの、当該構成要素がその
   周囲にセパレータを必ず持つか否かに関わるデータを含
   み、上記ステップ（ｄ）では、かかるデータにも矛盾し
   ないように、各文字列領域に最適な構成要素名を割り当
   てる請求項１記載の方法。
4. 【請求項４】セパレータとは異なる一定の条件を満たす
   白領域をサブセパレータとして検出し、その位置データ
   を発生するステップを含み、上記ステップ（ｄ）は、（
   ｄ１）検出されたセパレータと上記レイアウトモデルに
   含まれるデータを制約条件として用いて、文字列領域に
   対して割り当てることの可能な構成要素名の割当パター
   ンデータを発生させ、（ｄ２）１のレイアウトモデルに
   ついて複数の割当パターンが発生されたことに応答して
   、割当パターンごとに、構成要素とサブセパレータの位
   置関係に着目してコストを計算し、計算結果に基づいて
   最適な構成要素名の割当パターンを決定するステップを
   含む請求項１ないし３記載の方法。
5. 【請求項５】上記ステップ（ｄ１）では、離散的弛緩法
   を用いる請求項４記載の方法。
6. 【請求項６】上記ステップ（ｄ２）では、同じ構成要素
   名を割り当てられた文字列領域がサブセパレータを越え
   て続くことに応答して、ペナルティを課すことを特徴と
   する請求項４記載の方法。
7. 【請求項７】文書画像にあるべき数のセパレータが検出
   されないことに応答して、上記ステップ（ｄ１）でサブ
   セパレータをセパレータとして扱うことを特徴とする請
   求項４記載の方法。
8. 【請求項８】紙面の構成要素が木構造で表わされる階層
   関係をなす文書画像のレイアウトを解析するシステムで
   あって、（ａ）構成要素相互の位置関係データ、各構成
   要素の紙面上での存否に関わるデータ、木構造の葉に位
   置する構成要素のそれぞれごとの、当該構成要素が含む
   文字列の数に関するデータ、及び木構造の節点に位置す
   る構成要素のそれぞれごとの、直接の下位構成要素の数
   に関するデータを含むレイアウトモデルを記憶する手段
   、（ｂ）文書の画像データに基づいて文字列領域と一定
   の条件を満たす白または黒領域たるセパレータとを検出
   し、それらの位置データを発生させる手段、及び（ｃ）
   上記文字列領域とセパレータの位置関係を制約として用
   い、上記レイアウトモデルが含むデータと矛盾しないよ
   うに、各文字列領域に最適な構成要素名を割り当てる手
   段を含むシステム。
9. 【請求項９】上記手段（ｃ）は、同じ構成要素名を持つ
   文字列領域は、セパレータを越えて続かないという制約
   にしたがう請求項８記載のシステム。
10. 【請求項１０】上記レイアウトモデルは、木構造の葉に
    位置する構成要素のそれぞれごとの、当該構成要素がそ
    の周囲にセパレータを必ず持つか否かに関わるデータを
    含み、上記手段（ｃ）は、かかるデータにも矛盾しない
    ように、各文字列領域に最適な構成要素名を割り当てる
    請求項８記載のシステム。
11. 【請求項１１】セパレータとは異なる一定の条件を満た
    す白領域をサブセパレータとして検出し、その位置デー
    タを発生する手段を含み、上記手段（ｃ）は、（ｃ１）
    検出されたセパレータと上記レイアウトモデルに含まれ
    るデータを制約条件として用いて、文字列領域に対して
    割り当てることの可能な構成要素名の割当パターンデー
    タを発生させる動作と、（ｃ２）１のレイアウトモデル
    について複数の割当パターンが発生されたことに応答し
    て、割当パターンごとに、構成要素とサブセパレータの
    位置関係に着目してコストを計算し、計算結果に基づい
    て最適な構成要素名の割当パターンを決定する動作を実
    行する、請求項８ないし１０記載のシステム。
12. 【請求項１２】上記動作（ｃ１）では、離散的弛緩法を
    用いる請求項１１記載のシステム。
13. 【請求項１３】上記動作（ｃ２）では、同じ構成要素名
    を割り当てられた文字列領域がサブセパレータを越えて
    続くことに応答して、ペナルティを課す、請求項１１記
    載のシステム。
14. 【請求項１４】文書画像にあるべき数のセパレータが検
    出されないことに応答して、上記手段（ｃ）がサブセパ
    レータをセパレータとして扱うことを特徴とする請求項
    １１記載のシステム。
15. 【請求項１５】レイアウトモデル作成手段を含む、請求
    項８ないし１４記載のシステム。
16. 【請求項１６】文書画像を入力する手段を含む、請求項
    ８ないし１５記載のシステム。
17. 【請求項１７】文字認識手段を含み、上記レイアウトモ
    デルには、文字認識処理が必要な構成要素を示すデータ
    が含まれる、請求項８ないし１６記載のシステム。
18. 【請求項１８】文書画像から文字列領域を抽出し、抽出
    された文字列領域を紙面での構成要素相互の位置関係を
    表すレイアウトモデルとすり合わせることによって、文
    書画像から構成要素を抽出する方法であって、（ａ）文
    書画像から一定の条件を満たす白または黒領域たるセパ
    レータを検出し、その位置データを発生させ、（ｂ）上
    記セパレータのデータにしたがって、上記文書画像を木
    構造領域に区分し、（ｃ）上記区分の結果形成された領
    域ごとに、セパレータとは異なる一定の条件を満たす白
    領域たるサブセパレータを検出し、その位置データを発
    生させ、（ｄ）上記セパレータのデータを構成要素の区
    切りとし、上記サブセパレータを構成要素の区切りの候
    補として、上記文字列領域とレイアウトモデルのすり合
    わせを行うステップを含む方法。
19. 【請求項１９】上記ステップ（ｃ）では、文字列領域ご
    とに文字サイズデータを発生させ、文字サイズが直上の
    文字列領域のそれと異なる文字列領域を検出し、その文
    字列領域の上の白領域をサブセパレータとして検出する
    、請求項１８記載の方法。
20. 【請求項２０】上記ステップ（ｃ）では、縦方向に関し
    て相隣接する文字列領域同士の間の白領域ごとに、ピッ
    チデータを発生させ、直前のピッチと異なるピッチを持
    つ白領域をサブセパレータとして検出する、請求項１８
    記載の方法。
21. 【請求項２１】上記ステップ（ｄ）では、離散的弛緩法
    を用いる、ステップ１８記載の方法。
22. 【請求項２２】上記ステップ（ｄ）は、１のレイアウト
    モデルについて、上記文字列に対して割り当てることの
    可能な構成要素名のパターンが複数発生されたことに応
    答して、パターンごとに、構成要素とサブセパレータの
    位置関係に着目してコストを計算し、計算結果に基づい
    て最適な構成要素名の割当パターンを決定するステップ
    を含む請求項１８ないし２１記載の方法。
23. 【請求項２３】上記コスト計算ステップでは、同じ構成
    要素名を割り当てられた文字列領域がサブセパレータを
    越えて続くことに応答して、ペナルティを課すことを特
    徴とする請求項２２記載の方法。
24. 【請求項２４】文書画像にあるべき数のセパレータが検
    出されないことに応答して、上記ステップ（ｄ）でサブ
    セパレータをセパレータとして扱うことを特徴とする請
    求項１８記載の方法。
25. 【請求項２５】文書画像から文字列領域を抽出し、抽出
    された文字列領域を紙面での構成要素相互の位置関係を
    表すレイアウトモデルとすり合わせることによって、文
    書画像から構成要素を抽出するシステムであって、（ａ
    ）文書画像から一定の条件を満たす白または黒領域たる
    セパレータを検出し、その位置データを発生させる手段
    、（ｂ）上記セパレータのデータにしたがって、上記文
    書画像を木構造領域に区分する手段、（ｃ）上記区分の
    結果形成された領域ごとに、セパレータとは異なる一定
    の条件を満たす白領域たるサブセパレータを検出し、そ
    の位置データを発生させる手段、及び（ｄ）上記セパレ
    ータのデータを構成要素の区切りとし、上記サブセパレ
    ータを構成要素の区切りの候補として、上記文字列領域
    とモデルのすり合わせを行う手段を含むシステム。
26. 【請求項２６】上記レイアウトモデルを記憶する手段を
    含む、請求項２５記載のシステム。
27. 【請求項２７】上記レイアウトモデルを作成する手段を
    含む、請求項２５または２６記載のシステム。
28. 【請求項２８】上記文書画像を入力する手段を含む、請
    求項２５ないし２７記載のシステム。
29. 【請求項２９】文字認識手段を含み、上記レイアウトモ
    デルには、文字認識処理が必要な構成要素を示すデータ
    が含まれる、請求項２５ないし２８記載のシステム。 【０００１】