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

Abstract

(57)【要約】 【課題】帳票等のように特定のレイアウトを有する文書
に対して適用可能な新規なフォーマットにより、効率的
に文書を処理できる文書のレイアウト解析システムを提
供することである。 【解決手段】記憶装置に記憶されたフォーマット・デー
タを参照することにより、複数のセルがある規則に従っ
て配置されている文書のレイアウト解析方法に関する。
まず、文書のイメージ・データから複数のセルを抽出す
ると共に、セル間の隣接関係を求める。次に、文書にお
けるセル間の隣接関係を、フォーマット・データが規定
するセル間の隣接関係と比較し、文書におけるセルが対
応しているフォーマット・データが規定するセルを特定
することにより、文書中の情報の配置を特定する。この
ようなレイアウト解析結果に基づき、セル中に存在する
情報のタイプを特定した上で、文字認識技術を用いて情
報の読取を行うため、効率的に帳票の処理が可能とな
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する利用分野】本発明は文書のレイアウト解
析方法及びシステムに係り、特に、記入領域等のセルが
ある規則に従って配置されている帳票のレイアウトを、
フォーマットを参照して解析するものに関する。

【０００２】

【従来の技術】事務処理の効率化のために、帳票の処理
は急速にコンピュータ化されている。帳票（フォーム）
には多数の罫線が縦横に引かれており、これらの罫線で
囲まれた領域はセルと呼ばれている。セルは、例えば
「氏名」のように帳票自身に予め印刷されている領域
（ヘッダ・フィールド）であったり、実際に記入者の氏
名や住所等を具体的に記入する記入領域（テキスト・フ
ィールド）であったりする。これらのフィールドは、何
らかの決まりに基づいて、帳票上にレイアウトされてい
る。

【０００３】一般に、帳票を処理するシステムは以下の
ような構成を有している。帳票処理システムが帳票から
必要な情報を抽出するために、まず、読取装置（ＯＣＲ
等）によって帳票の画像イメージ（ビット・マップ）を
得る。この画像イメージを、システムのメモリ中に予め
記憶されているフォーマットに基づいて、解析すること
により、帳票のレイアウトを把握する。この解析によ
り、帳票中のどの位置にどのような情報（例えば、住所
または名前等）が存在するのかを特定した上で、その位
置に実際に存在するイメージとしての文字、数字、記号
等を、よく知られた文字認識技術を用いることで、テキ
ストとして認識していく。これにより、その位置に記入
された情報がテキストとして認識される。ここで、フォ
ーマットとは、帳票のレイアウトを解析するためのモデ
ルであって、帳票のレイアウトはこのひな形を比較参照
することで解析される。

【０００４】従来から知られている最も簡単なフォーマ
ットは、帳票に予め印刷される罫線の位置や長さ、及び
予め印刷される文字（ヘッダ）に基づいて規定されるも
のである。つまり、フォーマットは何も記入されていな
い帳票（ブランク・フォーム）である。このようなフォ
ーマットに基づいて、読取装置で実際に読み込まれた帳
票のビット・マップからブランク・フォームが消し去ら
れ、かつ帳票のレイアウトが解析される。つまり、帳票
中のどの部分にどのような情報が記入されているかが特
定されるのである。

【０００５】図１は、具体的な帳票のサンプルを示す図
である。これらの３つのサンプルＡ，Ｂ，Ｃは、どれも
サンプル中に存在する罫線の位置や長さが異なってい
る。上記の従来技術において、一つのフォーマットで対
応できる帳票は、帳票中に存在する罫線の位置や長さ等
がフォーマットが有する情報と厳密に一致しているもの
に限られるため、一つのフォーマットで３つのサンプル
のレイアウトを解析することはできない。従って、サン
プルＡ，Ｂ，Ｃに対応したフォーマットをそれぞれ別々
に用意しておかなければならない。この場合、それぞれ
のフォーマットのデータを記憶するメモリ領域が拡大す
るため、システムのメモリ領域を有効に活用できなくな
る。また、このようなフォーマットを用いた帳票処理シ
ステムは、帳票を受け付ける度に、その帳票に対応する
フォーマットがどれであるかを照合しなければならない
ので、帳票の処理速度が低下するおそれがある。この処
理速度の低下は、処理しようとする帳票の枚数が増加す
るに従って顕著になる。

【０００６】そこで、一つのフォーマットでレイアウト
の異なる複数の帳票に対応できるようにするために、罫
線の位置、長さ等の厳密な一致を基準とするのではな
く、帳票中に存在する罫線の線引きの順序に基づいてフ
ォーマットを規定する技術も提案されている。例えば、
サンプルＢでは、帳票全体をまず横に切ることで（罫線
１）、帳票を上下の二つのエリアに分割する。次に切り
とられた上下部分をさらに縦に切ることにより（罫線
２、３）、上部が「Nameエリア」と「Zipエリア」に、
下部が「Addressエリア」と「Telエリア」に分割され
る。さらに、４つのエリアをそれぞれ縦に切ることによ
り（罫線４、５、６、７）、それぞれのエリアがヘッダ
・フィールドとテキスト・フィールドに分割される。

【０００７】このように帳票中の罫線の線引きの順序に
基づいて規定されたサンプルＢ用のフォーマットは、例
えば、図１（ｂ）の罫線５が罫線５’に変わっている帳
票に対しても適用することができる。罫線の線引きの順
序は変わらないからである。しかしながら、このフォー
マットは、この順序がサンプルＢとは相違するサンプル
Ｃに対しては適用することができない。サンプルＣで
は、帳票全体をまず縦に切り（罫線１）、帳票を左右の
二つのエリアに分割する。次に切り取られた左右部分を
横に切る（罫線２、３）。つまり、図１（ｂ）及び
（ｃ）の帳票は罫線の引き方が相違するため、異なるフ
ォーマットで表現しなければならない。従って、この方
法でも、やはり、一つのフォーマットで、図１に示す３
つのサンプルに対応できないということになる。また、
実際の帳票からのフォーマットの構築や、新たな帳票に
よる更新する場合においても専門的な知識を必要として
おり、一から作り直す必要が生じている。

【０００８】

【発明が解決しようとする課題】上記の問題点に鑑み、
本発明の目的は、帳票等のように特定のレイアウトを有
する文書に対して適用可能な新規なフォーマットを提供
することである。具体的には、罫線などのセパレーター
によってセルが区切られていて、セルの配置の順序は変
わらないがその位置・大きさがさまざまであるような文
書に対応可能なフォーマットを提供することである。

【０００９】また、本発明の別の目的は、効率的に書面
を処理できる文書のレイアウト解析システムを提供する
ことである。

【００１０】

【課題を解決するための手段】上記課題を解決するため
に、第１の発明は、記憶装置に記憶されたフォーマット
・データを参照することにより、複数のセルがある規則
に従って配置されている文書のレイアウト解析方法にお
いて、文書のイメージ・データから複数のセルを抽出す
ると共に、セル間の隣接関係を求めるステップと、文書
におけるセル間の隣接関係を、フォーマット・データが
規定するセル間の隣接関係と比較し、文書におけるセル
が対応するフォーマット・データが規定するセルを特定
することにより、文書中の情報の配置を特定するステッ
プとを有する方法を提供する。

【００１１】ここで、フォーマット・データは、それぞ
れのセルに存在する情報のタイプを規定すると共に、セ
ル間の隣接関係を規定したものであって、予め用意され
ていることが好ましい。具体的には、少なくとも１つの
サンプルを予め用意しておき、これらのサンプルごと
に、複数のセルを抽出すると共に、、複数のセル間の隣
接関係を求める。そして、複数のセルを頂点に対応付け
ると共に、隣接関係のうちサンプルに共通するものを辺
に対応付けることでフォーマット・データを作成する。

【００１２】また、特定された情報の配置に従って、前
記文書に含まれる情報を認識するステップをさらに有し
ていてもよい。

【００１３】上記の隣接関係は、一のセルと他のセルと
が隣接している場合、これらのセルが共有する罫線を用
いて表現してもよい。

【００１４】第２の発明は、記憶装置に記憶されたフォ
ーマット・データを参照することにより、複数のセルが
ある規則に従って配置されている文書のレイアウトを解
析するシステムにおいて、それぞれのセルに存在する情
報のタイプを規定すると共に、セル間の隣接関係を規定
したフォーマット・データを記憶する手段と、文書のイ
メージ・データを抽出する手段と、文書のイメージ・デ
ータから複数のセルを抽出すると共に、セル間の隣接関
係を求める手段と、文書におけるセル間の隣接関係を、
フォーマット・データが規定するセル間の隣接関係と比
較し、文書におけるセルが対応するフォーマット・デー
タが規定するセルを特定することにより、文書中の情報
の配置を特定する手段と、特定された情報の配置に従っ
て、文書に含まれる情報を認識する手段とを有するシス
テムを提供する。

【００１５】また、第３の発明は、セルの配置が異なる
複数の文書のレイアウトを解析するためのフォーマット
・データを作成する方法において、複数のセルがある規
則に従って配置されているサンプルを少なくとも１つ用
意するステップと、少なくとも１つのサンプルの各々ご
とに、複数のセルを抽出するステップと、少なくとも１
つのサンプルの各々ごとに、複数のセル間の隣接関係を
求めるステップと、複数のセルを頂点に対応付けると共
に、隣接関係のうち前記サンプルに共通するものを辺に
対応付けたフォーマット・データを生成するステップと
を有する方法を提供する。。

【００１６】さらに、第４の発明は、セルの配置が異な
る複数の文書のレイアウトを解析するためのフォーマッ
ト・データを作成する方法において、複数のセルがある
規則に従って配置されているサンプルを少なくとも１つ
用意するステップと、少なくとも１つのサンプルの各々
ごとに、複数のセルを抽出し、複数のセル間の隣接関係
を求めるステップと、少なくとも１つのサンプルの各々
ごとに、複数のセルを頂点に対応付けると共に、隣接関
係を辺に対応付けた下位フォーマット・データを生成す
るステップと、複数のセルを頂点に対応付けると共に、
それぞれの下位フォーマット・データに共通する隣接関
係を辺に対応付けたフォーマット・データを生成するス
テップとを有する方法を提供する。

【００１７】

【発明の実施の形態】本発明によりレイアウトを解析で
きる文書は、複数のセル（文書中の所定領域）がある規
則に従って配置されているものであり、典型的には、帳
票が挙げられる。通常、セルは、罫線や空白等のセパレ
ータ(separator)で区切られている。帳票においては、
「氏名」と予め記入されたヘッダ領域や、具体的に氏名
を記入するテキスト領域がセルである。以下、本発明の
典型的な適用例として、帳票のレイアウトの解析につい
て説明する。

【００１８】フォーマットの生成 フォーマットとは、文書のレイアウトを解析するための
ひな形（モデル）であって、文書のレイアウトはこのひ
な形を参照することで解析される。このフォーマット
は、セルに存在する情報のタイプを規定すると共に、セ
ル間の隣接関係を規定している。基本的に、フォーマッ
トは、まず一意に記述されること、そしてフォーマット
中のフィールド等のセルの関係をたどることによって、
文書中のすべてのセルを特定できることが重要である。
本実施例におけるフォーマットは、帳票中のセルの隣接
関係に基づいて記述されている点に特徴がある。セル間
の隣接関係に着目することで、罫線の長さや位置が相違
する帳票に対しても一つのフォーマットで対応すること
ができ、具体的には、図１に示す３つのサンプルに対し
て同一のフォーマットを適用することが可能となる。

【００１９】フォーマットは、具体的には、有向グラフ
で表現され、グラフの頂点を帳票中のセルに対応付ける
と共に、グラフの辺をセル間の隣接関係に対応付けてい
る。このフォーマットは罫線によって囲まれた矩形であ
るセルの集合である帳票を一意に表現することができ
る。図２は、本実施例におけるフォーマットを生成する
手順を示すフロー図である。以下、それぞれのステップ
を図１に示したサンプルＡ，Ｂ，Ｃを例に説明する。

【００２０】サンプルからセルを抽出（ステップ２０
１） 本実施例で処理することができる帳票は、罫線によって
フィールドが囲まれ、区切られているものである。ま
た、帳票中に存在する罫線で囲まれている最小単位の領
域をセルといい、各セルは四角形であり、かつ、隣合う
セル間にすき間（非セル領域）がないことが好ましい。

【００２１】なお、以下の説明では、セルが物理的に隣
接している場合を例に説明するが、本発明における「隣
接」は上記場合に限定されず、セルが離れている場合に
おいても一定の条件を満たす限り「隣接」した状態であ
るとみなすことができる。すなわち、本発明でいう「隣
接」とは、ある一つの罫線または一直線上にある複数の
罫線に対して、同じ側でセルが直接接触している状態ま
たは同じ側で他のセルを介することなくセルが離れてい
る状態をいうものと定義する。

【００２２】まず、サンプルから、グラフの頂点（ノー
ド）に対応するセルを抽出する。サンプルＡでは８つの
セル、すなわち、「Name(H)」、「Name(T)」、「Zip
(H)」、「Zip(T)」、「Address(H)」、「Address
(T)」、「Tel(H)」、及び「Tel(T)」が得られる。ここ
で、（Ｈ）は帳票中に予め印刷されているヘッダを示
し、（Ｔ）は記入されるべきテキストを示している。例
えば、セル「Name(H)」は、帳票中に予め印刷された文
字「Name」が存在する矩形領域を指し、また、セル「Na
me(T)」はその右側の空欄であり、実際に氏名が記入さ
れる記入欄である。

【００２３】下位フォーマットの生成（ステップ２０
２） ステップ２０１より得られたセルに関して、それらの隣
接関係に基づいた下位フォーマットを生成する。下位フ
ォーマットはサンプルごとに生成される。これらの下位
フォーマットの生成は、最終的に必要な上位フォーマッ
トを生成するための前処理に当たる。下位フォーマット
は、有向グラフで表現され、グラフの頂点をステップ２
０１で求めたセルに対応付け、その辺をセル間の隣接関
係に対応付ける。

【００２４】この隣接関係について図３を参照しつつ詳
述する。隣接関係に関する情報は、一のセルと他のセル
が隣接しているかどうかという点、及び隣接しているな
らば、上下左右のどこで隣接しているかを示す情報であ
る。図３（ａ）及び（ｂ）のようにセルＡ及びセルＢが
配置されている状態を、「セルＡ及びセルＢは隣接関係
にある」という。このようにセルが隣接している場合、
「セルＡ及びセルＢが罫線１を共有している」という。
なお、罫線２に関しては、セルＡとセルＢが対向する側
で罫線２と接しているので、罫線２をセルＡとセルＢが
共有しているとはいわない。同様に、同図（ｃ）に示す
セルＡとセルＢは隣接していない。

【００２５】隣接関係に関する情報としては、セルがど
の罫線を共有しているかという情報も含まれる。すなわ
ち、あるセルが他のセルと共有する罫線が、左側の罫
線、右側の罫線、上側の罫線、または下側の罫線のうち
のどれであるかが特定されている。例えば、図１のサン
プルＡについては、セル「Name(H)」及びセル「Name
(T)」は、上側の罫線及び下側の罫線の両方を共有して
いる。また、セル「Name(H)」及びセル「Address(H)」
は、左側及び右側の罫線を共有している。図４（ａ）
は、このようにサンプルＡ中のすべてのセルの隣接関係
をまとめた表である。この表において、記号「Ｒ」は二
つのセルが右側の罫線を共有していることを意味してい
る。同様に、記号「Ｌ」、「Ｔ」、「Ｂ」はそれぞれ、
左側の罫線、上側の罫線、下側の罫線を共有しているこ
とを意味している。

【００２６】サンプルＡの下位フォーマットは、有向グ
ラフとして表現されるが、これは図４（ａ）の表と等価
である。グラフの頂点をセルに対応付ける。また、グラ
フの有向辺は、始点を表の左端の列のセルに対応付け、
終点を表の上端の行のセルに対応付ければよい。なお、
表中T,B,L,Rは共有辺である。有向グラフで表現するよ
りも、図４のような、それと等価な一覧表の方が、セル
間の関係を容易に把握できるため、以下の説明において
も、便宜上、フォーマットをこのような表で記述する。

【００２７】すべてのサンプルの下位フォーマットを生
成（ステップ２０３） すべてのサンプルについて下位フォーマットを生成す
る。すべてのサンプルを処理していない場合には、未処
理のサンプルについて、ステップ２０１、２０２を実行
する。従って、図１に示したサンプルＢ、Ｃについて
も、サンプルＡの場合と同様に、下位フォーマットを生
成する。図４（ｂ）、（ｃ）は、それぞれサンプルＢま
たはＣの下位フォーマットである。

【００２８】上位フォーマットの生成（ステップ２０
４） 複数の帳票を一つのフォーマットで処理するために帳票
に共通した情報をとり出す。そのために、ステップ２０
３で得られた複数の下位フォーマットに対して、共通し
た隣接関係のみを抽出していくことで、上位フォーマッ
トを求める。サンプルＡ，Ｂ，Ｃは、図４の表による
と、セル「Name(H)」及びセル「Name(T)」との関係は、
すべて「ＴＢ」で共通であるから、すべてのサンプルで
頂部及び下側の罫線を共有していることが分かる。ま
た、セル「Name(H)」及びセル「Addr(H)」は、「Ｌ」の
み共通しているから、すべてのサンプルは左側の罫線を
共有していることが分かる。このようにして、すべての
下位フォーマットの共通した情報のみを取り出すことに
より、上位フォーマットを生成する。図５は、図４の下
位フォーマットを元に生成された上位フォーマットを示
す表である。

【００２９】上位フォーマットの検証（ステップ２０
５） ステップ２０４により生成された上位フォーマットが、
すべてのサンプルに対して適用できるものであるかどう
かを、セルの連結性の確認することで検証する。すなわ
ち、上位フォーマットを表す有向グラフを無向グラフに
変換した場合に、それが連結グラフであるかどうかを確
認する。サンプルＡ、Ｂ、Ｃより得られた上位フォーマ
ット（図５）の無向グラフを図６に示す。このグラフは
連結グラフであるから、この上位フォーマットは、これ
らのサンプルに適用可能なフォーマットである。

【００３０】本実施例におけるフォーマットは、セルの
隣接関係を用いたものであるから、あるセルは、他のセ
ルとの隣接関係で必ずトレースできることが必要であ
る。上位フォーマットが連結グラフであるということ
は、ある任意のセルを基準にして、他のセルとの隣接関
係をたどっていけばすべてのセルをトレースすることが
できるということである。従って、この上位フォーマッ
トは、すべてのサンプルに適用が可能であるということ
になる。

【００３１】もし、上位フォーマットが連結グラフでな
ければ、このフォーマットは、セルを特定するのに必要
が情報が不足しているため、上記の隣接関係では特定で
きないセルが生じる。生成されたフォーマットがこのよ
うに不完全な場合には、サンプルＣを対象からはずすな
どしてサンプルの数を減らして、再度、上記ステップを
実行し完全なフォーマットが生成する必要がある。この
場合、サンプルＣに対しては別のフォーマットを生成す
る。

【００３２】一つのフォーマットにより処理可能な帳票
の種類について説明する。まず、図４の表で表現されて
いるフォーマットを図で表現すると図７のようになる。
この図において、「○」という表記は、その交点の周り
でセルが隣接していないことを示す。この交点を「非隣
接点」と呼ぶ。従って、セルが共有する罫線が非隣接点
を介しているため、「Name(T)」は「Address(T)」と隣
接していないし、「Zip(H)」も「Tel(H)」と隣接してい
ない。この非隣接点以外の交点を「隣接点」とよぶ。図
７で表される一つのフォーマットで図１に示す３つの帳
票のサンプルを表現することができる。これら３つのサ
ンプルの違いは、セルの入り組み方の違いであり、ここ
ではこれらを「セル・レイアウトの違い」とよぶ。つま
り、一つの非隣接点で３通りのセルのレイアウトを表現
できるということを意味している。従って、フォーマッ
ト中に非隣接点がｎ個ある場合には、その一つのフォー
マットで3ⁿ通りのセルのレイアウトの帳票を処理できる
ということになる。

【００３３】図６のような連結グラフとなる上位フォー
マット（図５）を用いることにより、すべてのサンプル
Ａ，Ｂ，Ｃのレイアウトを一のフォーマットで解析する
ことができる。このようなフォーマットに基づいて、読
み取り装置で実際に読み込まれた帳票のビット・マップ
から、帳票中のどの位置にどのような情報が存在するか
を特定することができる。その後、文字認識技術を用い
て、その位置に存在するイメージとしての文字や記号の
認識を行うことにより、抽出すべき情報であるテキスト
が抽出される。

【００３４】なお、図１に示すサンプルＡ，Ｂ，Ｃ以外
のレイアウトを有する帳票であっても、セルの隣接関係
が上位フォーマットと一致する限り、このフォーマット
でレイアウトを解析することができる。

【００３５】フォーマットを用いた実際の帳票の処理 基本的に、フォーマットはセルの隣接関係を元にしたグ
ラフにより規定されている。このフォーマットを用いて
実際の帳票を処理する場合には次のような手順になる。 （１）文書解析により帳票のイメージから罫線を抽出す
る。 （２）罫線に囲まれた領域を探して、セルを抽出する。 （３）実際のセルとフォーマットのセル情報とを比較す
ることによりセルであると認定する。

【００３６】セルの隣接関係に基づいて記述されたフォ
ーマットは、基本的には、帳票のイメージ・データから
セルが特定されていることを前提として適用されるもの
である。従って、フォーマットの適用のためには、ま
ず、罫線で囲まれたセルが特定されていることが前提と
なっている。しかしながら、実際の帳票を処理する場合
には、かすれによる罫線の消失や汚れによる罫線の過剰
抽出が生じうる。これにより、本来罫線で囲まれること
でセルとして認識されるべき領域が、罫線のかすれ等で
完全に囲まれておらず、セルとして認識できない場合が
生じ得る。そこで、実際に帳票を処理する際に、セルを
正しく認識し、効果的にフォーマットを適用することが
できるように、フォーマットにおけるセルの記述を罫線
で表現することが好ましい。すなわち、隣接セルフォー
マットをセル間の隣接情報による表現をそれと等価な罫
線による表現に変換する。

【００３７】隣接関係に関する情報は、隣接している一
対のセル、共有している罫線、セル間に存在する罫線の
４つである。例えば、図３（ａ）に示す状態について
は、セルＡ、セルＢ、罫線１、罫線２である。これらの
セルの隣接関係に基づいて、各罫線について次のような
情報が得られる。 （１）罫線２の上端は罫線１上にある（罫線１に接続し
ている）。 （２）罫線２の下端の位置は未定である。 （３）罫線１の左右端の位置は未定である。

【００３８】また。図３（ｂ）に示す状態については、
各罫線について次のような情報が得られる。 （１）罫線２の左端は罫線１上にある（罫線１に接続し
ている）。 （２）罫線２の右端の位置は未定である。 （３）罫線１の上下端の位置は未定である。

【００３９】未定の端の位置については他のセル間の隣
接関係に関する情報により決定される。このように、セ
ルを罫線の集合として表現するように変換する。

【００４０】この変換をフォーマット全体に適用し、罫
線およびその端点の情報を取り出す。ただし、取り出す
罫線・端点情報は、以下の規則に従うものとする。 （１）取り出された罫線が既存の罫線の延長である場合
には新しい罫線を作成せず、既存の罫線を延長する。 （２）罫線の端点を決定する場合、すでにその罫線が端
点の情報を持っている場合でも新たな端点を加え、複数
の端点情報を持たせる。

【００４１】このような規則に従うと、図７のフォーマ
ットは、図８に示すように４本の水平線（罫線Ａ乃至
Ｄ）と８本の垂直線（罫線ａ乃至ｈ）で表現できる。な
お、罫線Ｂと罫線Ｃは、既存の罫線の延長であるにも拘
わらず、非隣接点を介しているため、別の罫線としてい
る点に留意されたい。罫線ｃと罫線ｆについても同様で
ある。

【００４２】図５のフォーマットの表を、このような罫
線（図８）による表現に変換すると図９に示す表にな
る。ここで、「N()」、「A()」、「Z()」、「T()」とい
う表記はそれぞれ「Name()」、「Address()」、「Zi
p()」、「Tel()」を示しており、かっこ内のH、Tという
表記はそれぞれ、ヘッダ、テキストを示している。例え
ば、横罫線Ａは、セルN(H)を構成するために、その下側
で縦罫線ｂ、ａと接している。また、横罫線Ｂは、セル
N(T)を構成するために、その上側で縦罫線ａ、ｃと接し
ている。一方、縦罫線ａは、セルN(H)を構成するため
に、その左側で横罫線Ａ、Ｂと接すると共に、セルN(T)
を構成するために、その右側で横罫線Ａ、Ｂと接してい
る。

【００４３】さらに、フォーマットは、これらの罫線の
依存関係をも規定しておくことが好ましい。それぞれの
罫線はその端点で他の罫線に接続している。実際の帳票
における一の罫線を探索する場合、一の罫線の端点で接
する他の罫線の位置が先に特定されていれば、この一の
罫線の端点の位置をある程度特定することができる。例
えば、縦罫線の上端が横罫線と接続されている場合、横
罫線の位置が特定されていれば、縦罫線の上端のＹ座標
の値は特定される（ここで、横方向をＸ座標、縦方向を
Ｙ座標とする）。図２（ａ）、（ｂ）の例では、罫線２
が罫線１に依存している。

【００４４】図９のフォーマットにおける罫線に関し、
罫線の端点の接続関係に基づいて、罫線の依存関係を求
める。図９の表から得られる依存グラフを表形式で表す
と、図１０に示す表のようになる。この表中の左端の列
にある罫線が上端の行にある罫線に依存している場合
に"X"マークを付けている。

【００４５】罫線の依存関係を生成するにあたって、縦
罫線及び横罫線は区別せずに扱う。また、外周の罫線
（罫線Ａ、Ｄ、ｂ、ｈ）は、他の罫線に依存しないもの
として扱う。外周の罫線とは、縦罫線（罫線ｂ、ｈ）に
関しては、左右のどちらか一方の側で他の罫線に接続さ
れておらず、接触セルの情報を有さないものをいい、横
罫線（罫線Ａ、Ｄ）に関しては、上下のどちらか一方の
側で他の罫線に接続されておらず、接触セルの情報を有
さないものをいう。但し、罫線の依存関係がループして
いる場合は、適当な場所で依存関係を切って閉路をなく
す。

【００４６】このようにフォーマット中のセルの隣接関
係を、罫線により記述し、罫線の依存関係を求めておく
ことにより、実際の帳票から抽出された罫線がかすれて
いたり、汚れている場合においても、有効に罫線を抽出
でき、セルを特定することができる。なぜなら、ある罫
線の長さは依存関係のある両端の罫線の位置で決まるか
らである。従って、その罫線がかすれていても両端の罫
線からその長さ、位置を推定することができる。このこ
とは、罫線がかすれているだけでなく、交点がかすれて
取り出せない場合にも正確に罫線を抽出することを可能
にする。

【００４７】図１１は、抽出された罫線がかすれている
場合の処理を説明するための図である。同図（Ａ）は、
フォーマットの一部分を示している。横罫線Ａは、縦罫
線ａ、罫線ｃに依存している。また、同図（Ｂ）は、実
際の帳票から抽出された実際の罫線の成分を示してい
る。抽出された横罫線１はかすれていて縦罫線２、４に
まで到達していない。また、抽出された縦罫線４も、横
罫線１との交点付近でかすれている。このような場合、
フォーマット中の罫線の依存関係を参照することによ
り、帳票から抽出された罫線の位置や長さをある程度特
定できるため、同図（ｃ）のような罫線が存在するもの
と判断することが可能となる。

【００４８】また、本方法ではフォーマット上での罫線
に接続している他の罫線の数と、抽出された罫線の接続
数との差をもとにコストを計算し、それが最小になるよ
うな組合せを最終結果とすることもできる。従って、汚
れなどにより余計な線分が抽出されても全体として最も
影響が少ない場合を探索することができる。従来は余計
な線分によって余計な交点、セルが抽出されてしまうと
その後の解析に大きな影響を及ぼしてしまうことがあっ
たが、本方法では局所的な汚れの影響は最小限に押える
ことができる。

【００４９】図１２は、本実施例における帳票処理シス
テムのブロック図である。フォーマット記録部１１に
は、セルの隣接関係に基づいたフォーマットの情報が記
憶されている。この情報は、それぞれのセルにどのよう
な情報（例えば、住所、氏名、電話番号等）が存在する
かということ及びセル間の隣接関係である。上述のよう
に、セル間の隣接関係は罫線で表現されていてもよい。
フォーマット生成部１２は、帳票のサンプルからフォー
マットを生成し、セルの連結性を確認するためのもので
ある。さらにフォーマット生成部１２は、新たなレイア
ウトを有する帳票のサンプルに基づいて、既存のフォー
マットを更新する機能も有している。新たなサンプルに
よって生成されたフォーマットが、セルの連結性を確保
できない場合には、生成されたフォーマットは不完全で
ある。従って、この場合には、フォーマットを更新せず
に、新たなサンプルに適合するフォーマットを新たに生
成して、これをフォーマット記録部１１に記憶しなけれ
ばならない。

【００５０】読取装置１３は、帳票をスキャンすること
により、帳票のイメージデータを生成する。このイメー
ジデータはイメージ記憶部１４に記憶される。セル抽出
部１５は、帳票のイメージデータからセル（縦横の罫
線）を抽出すると共に、イメージデータから帳票のセル
間の隣接関係を求める。レイアウト解析部１６は、セル
抽出部１５により抽出された帳票のセル間の隣接関係
と、フォーマット記憶部１１に記憶されているフォーマ
ットが規定する隣接関係とのマッチングを行い、これら
を比較することにより、帳票中のあるセルがフォーマッ
トのどのセルに対応するのかを特定する。これによっ
て、レイアウト解析部１６は、帳票中のある位置にどの
ような情報（例えば、住所）が存在するかを特定する。
レイアウト解析部１６による帳票のレイアウトの解析結
果に従って、認識装置１７は帳票中のある位置に存在す
る情報（例えば、住所として記入者が帳票中に具体的に
記入した文字、数字、記号等）を文字認識技術を用いて
認識する。

【００５１】図１３は、帳票処理の手順を示す流れ図で
ある。まず、帳票中の各セルにどのような情報が存在す
るかを規定すると共に、セル間の隣接関係を規定したフ
ォーマットを用意する（ステップ１０１）。このフォー
マットは、フォーマット記憶部１１中に記憶されてい
る。次に、帳票から複数のセルを抽出すると共に、前記
セル間の隣接関係を求める（ステップ１０２）。帳票に
おけるセル間の隣接関係を、フォーマットが規定するセ
ル間の隣接関係と比較し、帳票におけるあるセルがフォ
ーマットのどのセルに対応するのかを特定することによ
り、帳票中のある位置にどのような情報が存在するかを
特定する（ステップ１０３）。そして、特定された位置
に存在する情報を認識する（ステップ１０４）。各ステ
ップの詳細は、上述したとおりである。

【００５２】なお、上記の実施例は、セルが罫線で区切
られている例について説明したが、本発明は、罫線以外
の区切り（separator）でセルが仕切られている文書に
対しても適用が可能である。例えば、一定の幅以上の空
白がセル間に存在する場合には、この空白を区切りとみ
なし、この空白を上記の罫線と同様に取り扱うことがで
きる。

【００５３】

【発明の効果】このように本発明は、セルの隣接関係
（罫線によるセルの表現も含む）に基づいてフォーマッ
トを規定している。従って、処理対象である文書中のセ
ルの隣接関係がフォーマットに規定するものと同一であ
る限り、セルの位置や大きさが相違しても、一のフォー
マットで統一して処理することのできる。特に、セルの
隣接関係を罫線で表現することにより、文書中の罫線
が、かすれていたり、汚れていたりする場合において
も、効果的に文書のレイアウトを解析することができ
る。

【図面の簡単な説明】

【図１】具体的な帳票のサンプルを示す図である。

【図２】本実施例におけるフォーマットを生成する手順
を示すフロー図である。

【図３】セル間の隣接関係を説明するための図である。

【図４】サンプル中のすべてのセルの隣接関係をまとめ
た表である。

【図５】図４の下位フォーマットを元に生成された上位
フォーマットを示す表である。

【図６】図５の上位フォーマットの連結性を示す無向グ
ラフである。

【図７】図５の上位フォーマットを示す図である。

【図８】図７の図を罫線で表現した図である。

【図９】図５のフォーマットの表を罫線による表現に変
換した表である。

【図１０】罫線の依存関係を示した表である。

【図１１】抽出された罫線がかすれている場合の処理を
説明するための図である。

【図１２】帳票処理システムのブロック図である。

【図１３】帳票処理の手順を示す流れ図である。

【符号の説明】

１１・・・フォーマット記録部 １２・・・フォーマット生成部 １３・・・読取装置 １４・・・イメージ記録部 １５・・・セル抽出部 １６・・・レイアウト解析部 １７・・・認識装置

Claims (16)

【特許請求の範囲】
1. 【請求項１】記憶装置に記憶されたフォーマット・デー
   タを参照することにより、複数のセルがある規則に従っ
   て配置されている文書のレイアウト解析方法において、 前記文書のイメージ・データから複数のセルを抽出する
   と共に、当該セル間の隣接関係を求めるステップと、 前記文書における前記セル間の隣接関係を、前記フォー
   マット・データが規定するセル間の隣接関係と比較し、
   前記文書におけるセルが対応する前記フォーマット・デ
   ータが規定するセルを特定することにより、前記文書中
   の情報の配置を特定するステップとを有することを特徴
   とする方法。
2. 【請求項２】それぞれのセルに存在する情報のタイプを
   規定すると共に、当該セル間の隣接関係を規定したフォ
   ーマット・データを予め用意するステップをさらに有す
   ることを特徴とする請求項１に記載の方法。
3. 【請求項３】前記特定された情報の配置に従って、前記
   文書に含まれる情報を認識するステップをさらに有する
   ことを特徴とする請求項１に記載の方法。
4. 【請求項４】前記隣接関係は、一のセルと他のセルとが
   隣接している場合、これらのセルが共有する罫線を用い
   て表現されていることを特徴とする請求項１に記載の方
   法。
5. 【請求項５】上記フォーマット・データを用意するステ
   ップは、 少なくとも１つのサンプルを用意するステップと、 前記少なくとも１つのサンプルの各々ごとに、複数のセ
   ルを抽出するステップと、 前記少なくとも１つのサンプルの各々ごとに、前記複数
   のセル間の隣接関係を求めるステップと、 前記複数のセルを頂点に対応付けると共に、前記隣接関
   係のうち前記サンプルに共通するものを辺に対応付けた
   フォーマット・データを作成するステップとを有するこ
   とを特徴とする請求項２に記載の方法。
6. 【請求項６】前記フォーマット・データ中のすべての前
   記頂点は前記辺で連結されていることを特徴とする請求
   項１に記載の方法。
7. 【請求項７】前記フォーマット・データにおけるセルを
   罫線の集合で表現することにより、前記フォーマット・
   データは罫線の接続関係に基づいて記述されていること
   を特徴とする請求項１に記載の方法。
8. 【請求項８】前記フォーマット・データは、罫線間の依
   存関係をさらに規定していることを特徴とする請求項７
   に記載の方法。
9. 【請求項９】記憶装置に記憶されたフォーマット・デー
   タを参照することにより、複数のセルがある規則に従っ
   て配置されている文書のレイアウトを解析するシステム
   において、 それぞれのセルに存在する情報のタイプを規定すると共
   に、当該セル間の隣接関係を規定したフォーマット・デ
   ータを記憶する手段と、 前記文書のイメージ・データを抽出する手段と、 前記文書のイメージ・データから複数のセルを抽出する
   と共に、当該セル間の隣接関係を求める手段と、 前記文書における前記セル間の隣接関係を、前記フォー
   マット・データが規定する前記セル間の隣接関係と比較
   し、前記文書におけるセルが対応する前記フォーマット
   ・データが規定するセルを特定することにより、前記文
   書中の情報の配置を特定する手段と、 前記特定された情報の配置に従って、前記文書に含まれ
   る情報を認識する手段とを有することを特徴とするシス
   テム。
10. 【請求項１０】少なくとも１つのサンプルにおけるセル
    の隣接関係に基づいてフォーマット・データを生成する
    手段をさらに有することを特徴とする請求項９に記載の
    システム。
11. 【請求項１１】上記フォーマット・データを生成する手
    段は、新たなサンプルに基づいて、既存のフォーマット
    ・データを更新する機能を有していることを特徴とする
    請求項１０に記載のシステム。
12. 【請求項１２】セルの配置が異なる複数の文書のレイア
    ウトを解析するためのフォーマット・データを作成する
    方法において、 複数のセルがある規則に従って配置されているサンプル
    を少なくとも１つ用意するステップと、 前記少なくとも１つのサンプルの各々ごとに、複数のセ
    ルを抽出するステップと、 前記少なくとも１つのサンプルの各々ごとに、前記複数
    のセル間の隣接関係を求めるステップと、 前記複数のセルを頂点に対応付けると共に、前記隣接関
    係のうち前記サンプルに共通するものを辺に対応付けた
    フォーマット・データを生成するステップとを有するこ
    とを特徴とする方法。
13. 【請求項１３】セルの配置が異なる複数の文書のレイア
    ウトを解析するためのフォーマット・データを作成する
    方法において、 複数のセルがある規則に従って配置されているサンプル
    を少なくとも１つ用意するステップと、 前記少なくとも１つのサンプルの各々ごとに、複数のセ
    ルを抽出し、当該複数のセル間の隣接関係を求めるステ
    ップと、 前記少なくとも１つのサンプルの各々ごとに、前記複数
    のセルを頂点に対応付けると共に、前記隣接関係を辺に
    対応付けた下位フォーマット・データを生成するステッ
    プと、 前記複数のセルを頂点に対応付けると共に、それぞれの
    前記下位フォーマット・データに共通する前記隣接関係
    を辺に対応付けたフォーマット・データを生成するステ
    ップとを有することを特徴とする方法。
14. 【請求項１４】前記隣接関係は、一のセルと他のセルと
    が隣接している場合、これらのセルが共有する罫線を用
    いて表現されていることを特徴とする請求項１２または
    １３に記載の方法。
15. 【請求項１５】前記フォーマット・データ中のすべての
    前記頂点が前記辺で連結されているかどうかを検証する
    ステップをさらに有することを特徴とする請求項１２ま
    たは１３に記載の方法。
16. 【請求項１６】前記フォーマット・データにおけるセル
    は、罫線の集合として表現されていることを特徴とする
    請求項１２または１３に記載の方法。