(57)【特許請求の範囲】
【請求項１】
表文書中のコラムを検出する方法であって、
文書スキャナによって前記表文書をコンピュータのメモリに読み込み、
前記コンピュータによって、同一行で隣接するイメージ断片同士間のスペースインターバルを決定し、決定した前記スペースインターバルを前記メモリに記憶し、
前記コンピュータによって、前記メモリに記憶されたスペースインターバルと前記メモリに記憶された別のスペースインターバルとの交わりに基づいて、交わりインターバルを形成し、形成された交わりインターバルを前記メモリに記憶し、
前記コンピュータによって、前記メモリに記憶されたスペースインターバルと前記メモリに記憶された交わりインターバルとの交わりに基づいて、別の交わりインターバルを形成し、形成された別の交わりインターバルを前記メモリに記憶し、
前記コンピュータによって、スペースインターバル及び交わりインターバルの交わりの頻度に基づいて、スペースインターバル及び交わりインターバルをランク付けし、
前記コンピュータによって、前記ランク付けに基づいて、スペースインターバル及び交わりインターバルをコラム離間インターバルとして選択し、
前記コンピュータによって、前記コラム離間インターバルにより離間されるコラムを検出し、
検出の結果を前記コンピュータから出力手段に出力する、
方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、表文書中のコラムを見出すことにおける改良に関する。さらに詳細には、本発明は、コラムを離間するものを検索するとともに、表中の語句片を離間するラインインターバルのみを処理する。
【０００２】
【従来の技術及び発明が解決しようとする課題】
表文書は、単純なライン（線）による束縛（制約）に基づくレイアウト構造に対してマッピングされる論理関連エンティティ（構成要素）の組織的構造である。各エンティティの配置及びフォーマットを制御することによって、このような束縛は、表の内容の組織化即ち論理構造の識別を助ける視覚的な手引きを提供する。表上に施される基礎的な幾何学的束縛は、関連エンティティを線形に配置するものである。その他の束縛として、表をタイプセッティングする場合のモノスペースフォントの整合及び使用がある。
【０００３】
多くの類似する記録を含む文書では、同じ論理見出し（論理的同一性）（logical identity）のエンティティが、格子状の構造のコラムに沿って配置されるのが一般的である。コラムの位置を決定するために、従来技術では、ビットマップのヒストグラムを作成し、ヒストグラムのピークを検索する。この方法では、文字やその他のものをビットマップへ処理することが必要である。
【０００４】
本発明では、ビットマップを復号化することなく、このようなタイプの文書のコラム構造を決定することができる。本発明は、表中の語句片を離間するラインインターバルを調べることによって、コラムを離間するものを検索する。この方法は、より信頼性が高いとともに、コンピュータ処理の見地からみても効果的である。この方法は、ライン交わり演算の下で、ラインインターバルの集合の順序付けされた閉包を生成し且つ維持する。多くの語句片離間インターバルの交わりであるコラム離間インターバルは、この技術により容易に識別される。
【０００５】
【課題を解決するための手段】
本発明の一態様は、表文書中のコラムを検出する方法であって、ワード断片間のスペースインターバルを決定するステップと、交わりインターバルを形成するために前記スペースインターバルを交差させるステップであり、該スペースインターバルも追加の交わりインターバルを形成するために先に形成された交わりインターバルと交差させる、該ステップと、前記スペースインターバルと前記交わりインターバルとの間の交わりの頻度に従って、該スペースインターバルと該交わりインターバルとをランク付けするステップと、ランク付けに基づいて、スペースインターバルと交わりインターバルとを選択するステップと、を含む。
【０００６】
本発明の別の態様は、表文書中のコラムを検出する装置であって、表文書をイメージ断片に符号化するコーダと、表文書中のコラムを検出するコンピュータと、を含み、前記コンピュータが、イメージ断片同士間のスペースインターバルを決定する決定器と、交わりインターバルを形成するためにスペースインターバルを交わらせる交差装置であり、スペースインターバルが、以前に形成された交わりインターバルと交わると、追加的に交わりインターバルを形成する前記交差装置と、スペースインターバルと交わりインターバルとの間の交わりの頻度に従って、スペースインターバルと交わりインターバルとをランク付けするランク付け器と、ランク付けに基づいて、スペースインターバルと交わりインターバルとを選択する選択器と、を含み、前記コラム検出装置が、表文書中のコラムの検出を出力する出力手段と、を含む。
【０００７】
本発明を図面をともなって説明する。図面では、同一又は類似部分を示すために同一の参照番号を用いる。
【０００８】
【実施例】
本発明の好適実施例を説明することを目的とし、本発明を制限するものではない図面を参照する。本発明は、文字をビットマップに復号化することなく表文書中でコラムを見出す方法を提供する。コラムが検出された後、パターンマッチャー（パターン整合装置）を使用して、各論理フィールドのシンタックスを判断することができるとともに、ＯＣＲ（optical character recognition 、光学的文字認識）モジュールが、文書中の各文字を読むことができる。
【０００９】
図１は、本発明の方法を使用する典型的なセットアップを示す。文書スキャナ１０を用いて、画像を処理する。文書が既にコード化されている場合には、文書をコンピュータ１２に直接入力することができる。入力は、文字境界ボックスを容易に利用できる（書物の）追記（postscript）等のＰＤＬ（Page Description Language 、ページ記述言語）であることも可能である。コンピュータ１２は、本発明の方法を用いることにより、表のエンティティを離間するインターバルの検出を行う。表のコラムの検出は、モニタ１４上にディスプレイされたり、プリンタ１６を使用して印刷されたりすることができる。表中のコラムの検出は、本文の場合のように、コンピュータ１２によるさらなる処理のために使用されることが可能である。
【００１０】
図２では、モノスペースタイプフォント（これは、本発明の方法が適用可能であるための必要条件ではない）を有するとともに、多様なコラム整頓線（配列）を呈する上記タイプの文書として、電話料金記録を例にとる。その他の例としては、保険の書類、財務諸表、銀行の経済報告書、税金の書類、及び診断書等が含まれる。このような文書のコラム構造を識別するための視覚的合図は、コラムを離間する空白のスペース及び／又はラインである。罫線を引かれた表は、ライン構造を見出すことにより認識されることができるので、本発明の方法では処理されない。罫線を引かれた表は、罫線を除去されれば、本発明の技術によって処理されることが可能である。アルゴリズムを適用するために、（罫線を除去した後に）残った空白のスペースを用いることができる。
【００１１】
図３は、図２の文書の骨組みを示すものであるが、文字を語句片境界ボックスに置き換えられている。コンピュータは、ビットマップかＰＤＬかのどちらかから、語句片境界ボックスを抽出することができる。表のレイアウト特質の多くは、表中のコラムの境界を形成する空白スペースに注意力を集中させることによって、容易に識別されることが可能である。本発明の方法は、コラムの境界を識別することによって、表のコラム構造を見い出す。
【００１２】
従来の方法では、イメージを水平軸上に射影し、その射影に沿って低濃度のインターバルを検索することによって、表のコラム境界を見出すことが可能である。コラム離間インターバルに対応するこれらのインターバルは、コラムの境界の幅に対応する長さを有する。本発明では、コラム離間インターバルを、連続する語句片同士間の空白スペースの大きさ（範囲）を示すインターバルから計算することが可能である。本発明の方法は、語句片を離間するインターバルに基づいて、コラム離間インターバルを見出す。文書認識アプリケーションにおいて語句片を自由に認識することができることを考えると、この方法は、ビットマップレベルで射影を行い検索する方法より、コンピュータ処理の見地から見て、より安価である。さらに、本発明の方法は、コラムの境界は、一般的な表文書内に占める空間が少なく、表文書内により均一に置かれるので、コラムを見出すことに対して、より信頼性が高い。
【００１３】
本発明の第１の実施例を図４〜図６に関して述べる。図４を参照すると、語句片境界ボックスは、語句片を囲む小さな矩形ボックスである。語句片離間インターバルは、同じ行の２つの連続する語句片境界ボックスを離間する、ｘ軸に沿った大きいインターバルと定義される。図４は、語句片ボックス３０と、単純な２コラムの表の語句片離間インターバルＩ1−Ｉ5とを示す。例えば、コラム境界ボックス３２は、コラム中の全てのエントリを囲む最も小さい矩形である。コラム離間インターバルは、２つの連続するコラム境界ボックス３２を離間するｘ軸に沿う最小のインターバルＪである。
【００１４】
図４で示すコラム離間インターバルであるべきインターバルＪに関して言えば、インターバルＪは、２つの連続するコラムから同じ行のエントリを離間する全ての語句片離間インターバルのサブセットであるということが必要である。よって、インターバルＪは、全ての語句片離間インターバルの交わりの中に含まれなければならない。従って、本発明の方法は、ラインインターバルの交わりの演算の下で、ラインインターバル（例えば、語句片離間インターバル）の集合の閉包を作り出すことによって、コラム離間インターバルの候補であることの可能な全てのラインインターバルを見出す。ラインインターバルの集合は、その集合中のいかなる２つの要素の交わりもまたその集合中にある場合に閉包である。インターバルＩは、Ｉ＝［ａ，ｂ］と定義され、ａ＜ｂであるとともに、ａはインターバルの左端点を示し、ｂはインターバルの右端点を示す。インターバルの長さはＩlength＝（ｂ−ａ）である。２つのインターバルＩj とＩk とのオーバーラップしたインターバルを示す交わりＩj ∩Ｉk は、長さゼロであることもある。閉包の各要素に対して、そのインターバルによって離間される語句片のペア数である対応ランキングが決定される。図４では、インターバルＪはＲ（Ｊ）＝５というランキングを有する。ランキングが５であるということは、インターバルＪが、表中の５つの列に対してコラムセパレータ（コラムを離間するもの）として使用されることが可能であるということである。
【００１５】
よって、本発明の方法は、次の３つの業務、即ち、語句片離間インターバルの集合の閉包を見出すという第１の業務、コラム離間インターバルが離間する語句片のペア数に基づいて閉包の各要素のランク付けを行うという第２の業務、そして、最高のランクを有する最小のインターバルを求めて閉包を検索するという第３の業務、によって、コラム離間インターバルを見出すプロセスを定義する。
【００１６】
語句片離間インターバルの集合の閉包Ｇを見出すために、閉包Ｇは、新たに見出された語句片離間インターバルと、閉包に既存する全要素とその新しい語句片離間インターバルとの交わりと、を閉包に追加されることによって、反復的に更新される。次に、閉包Ｇ中の各インターバルをランク付けする。これは、語句片離間インターバルの集合の全てのインターバルＩを、その閉包Ｇの全ての要素ｇと比較することによって達成され得る。ｇ⊆Ｉであれば、ｇがＩの代わりに離間インターバルとして使用されることが可能であるということを示すので、ｇのランクが１だけ増され得る。重複するインターバルは、閉包に新たな要素を加えることなく、閉包Ｇ中のインターバルのランキングを増分する。
【００１７】
別法としては、これら２つのステップを１つのステップにすることが可能である。各々の新しいインターバルＩi+1 に対して、全要素ｇ⊆Ｇi との交わりが決定され、ここで、Ｇi は、最初のｉ個のインターバルを処理した後で得られた閉包である。ｇ⊆Ｉi+1 であれば、ｇのランクを増分する。Ｉi+1 が唯一つである（ＵＮＩＱＵＥである）場合には、閉包Ｇi にＩi+1 を加える。そのランクは、Ｉi+1 を含む最小の要素ｇのランクに１を追加することによって決定されることができる（Ｉi+1 がｎ個のインターバルの中に含まれる場合には、Ｉi+1 は、それらの交わりの中にも含まれるということに注目する。この交わりは、Ｉi+1 を含む閉包中の最小のインターバルである。それはなぜなら、Ｉi+1 を含む閉包の中にさらに小さいインターバルがあるとすれば、それがｎ個のインターバルの交わりであろうからである）。また、Ｉi+1 が、あるインターバルｇと交わる場合に、その交わりは、それが唯一つしかない場合にのみ閉包Ｇに追加されるべきである。この交わりのランクはまた、それを含む最小の要素のランクに１を加えることによって見出される。
【００１８】
上記方法の各反復において、重複するインターバルを閉包に追加することを回避するために検索が必要である。ランキングに対しても検索が必要である。これらの検索の複雑さは、閉包の大きさが大きくなると増大する。さらに、全ての反復は、全閉包を検索する。しかしながら、コラムを見出す際にインターバルが自然状態であるために、インターバルは領域中に集まるように配置されているのが一般的である。よって、閉包のサブセットの検索のみが必要とされ得る。
【００１９】
本発明では、非構造閉包を、以下のスキームを用いて、インターバル集合にグループ分けする。図５では、全インターバルの右端のアドレスを含むハッシュテーブル（表）４０が作成される。ハッシュテーブル４０は、ビン構造４２への索引付けを行うために使用される。ビン構造４２は、分類された昇順で共にリンクされている多くの格納ビンからなる。ハッシュテーブル４０中の各キー値ペアは、ビン構造４２中の格納ビンと対応している。ビンは、同じ右端アドレスを有する全てのインターバルの左端アドレスを保持する。各左端アドレスと関連するものは、インターバルのランキングである。各ビンはまた、ハッシュテーブルのアドレスを含む最右インターバルの右端アドレスを示す最右アドレスを割り当てられている。各ビンにおける左端アドレスは、右−左の順、即ち最大インターバル−最小インターバルの順で維持される。
【００２０】
ハッシュテーブルの目的は、適切な格納ビンへの素早い索引付けを提供することである。アレイ構造は、ハッシュテーブルと、リンクされたリストとの両方に取って代わることが可能である。その場合には、同じ右端点を有するインターバルは、右端点の値によって索引付けされたアレイエレメントにおいて格納されるであろう。もちろん、多くのアレイエレメントが空であろう。
【００２１】
ハッシュテーブルを用いる格納の例を、図６で示すインターバルの小さな集合に対して図５で示す。図６では、インターバルＡは８という右端アドレスを有し、インターバルＢ及びＤは、１２という右端アドレスを有し、そして、インターバルＥは、２２という右端アドレスを有する。従って、ビン構造４２は、少なくともこれら３つのアドレスを含まなければならない（アドレス１５を、例を説明するために示す）。図５では、インターバルＡは、１というランクで格納ビン８において記憶される。インターバルＣは、インターバルＡと交わっているので、アドレス８を含む最右インターバルの右端アドレスは、アドレス１２である。
【００２２】
ビン構造４２のアドレス１２は、２つのエントリを有する。まず、唯一つしかないインターバルＢが、ランク１でビンに加えられる。これはまず、ビンにおいて（１０．１）によって示される。次に、これもまた唯一つしかないインターバルＣがビンに追加される。それは、１というランキングを有する新たな要素（４．１）で示される。インターバルＢ及びＣの交わり演算が実行され、それは結果的にインターバルＢとなる。インターバルＢはすでにビン中に存在するので、そのランクのみが増されることになる。よって、（１０．１）が（１０．２）に変わる。従って、インターバルＢのランキングが１だけ増される。次に、インターバルＤが処理される。インターバルＤは唯一無二ではない、即ち、それはインターバルＢと同じであるので、インターバルＤを含む閉包の中のそれらのインターバルのランクが増分される。インターバルＤを含む唯一のものはインターバルＢであり、従ってそのランクが３に増される。よって、（１０．２）が（１０．３）に変更される。ビン１２の最右アドレスはゼロである、なぜなら、アドレス１２を含むその右より右の端を有するインターバルはないからである。
【００２３】
インターバルＥを処理する。このインターバルは、他のどのインターバルとも交わらないので、ランクを１として格納ビン２２の中に入れられる。
【００２４】
いくつかの表文書は、数個のコラムを含むことがある。本発明の第２の実施例は、閉包Ｇi 中の各インターバルをチェックする必要をなくす。インターバルＩの左端アドレスを含むビンにおいて検索を開始することによって、所定のインターバルＩと交わるインターバルの集合を見出すことを実行する。このビンアドレスは、インターバルＩの左端アドレスより大きい又はそれに等しい右端アドレスを有する全てのインターバルｇを含む。
【００２５】
ｒｉｇｈｔ（ｇ）≧ｌｅｆｔ（Ｉ）  （式１）
ここで、ｒｉｇｈｔ（ｇ）は、インターバルｇの右端アドレスであり、ｌｅｆｔ（Ｉ）は、インターバルＩの左端アドレスである。
【００２６】
インターバルｇ及びＩのこの関係は、インターバルＩと交わるどのインターバルｇに対しても存在しなければならない。
【００２７】
交わりを有するインターバルの検索は、各ビンを右に連続的に処理することによって続けられる。検索は最後のビンまで継続することが可能である；しかし、別法では、最後に処理されるビンが以下の条件、即ち、そのビンのアドレスが、インターバルＩの右端に対応する格納ビンの最右アドレスと同じであることを満足する場合に、検索を終えることができる。換言すれば、このビンは、インターバルＩと交わる最右インターバルを保持する。
【００２８】
各ビンにおいて、ビン中の分類された左端リストを順にあたる、即ち最小のインターバルから最大インターバルまで順に進む、ことによって、そして、以下の条件を満足するようなインターバルｇを考慮するだけで、インターバルＩと交わるインターバルが見出される。
ｌｅｆｔ（ｇ）≦ｒｉｇｈｔ（Ｉ）    （式２）
ここで、ｒｉｇｈｔ（Ｉ）は、インターバルＩの右端アドレスであり、ｌｅｆｔ（ｇ）は、インターバルｇの左端アドレスである。
【００２９】
最悪の場合には全てのビンが検索されることもあるが、検索の長さは一般に、インターバルにあるビンの数に比例する。検索の間、格納ビンが次のような場合、即ち、（１）そのアドレスが、いかなるインターバルの右端点にも一致しない、即ちビンが空であること、（２）ビン中の全ての要素が、選択されたインターバルＩの右にある、即ちビン中の最後の要素（最大のもの）の左端が、インターバルＩの右端より大きい、といった場合に、即座に放棄され得ることに注目することが重要である。
【００３０】
上記構造に従って構成される閉包Ｇi のインターバルｇと新たなインターバルＩi+1 が交わる場合に、交わりＩi+1 ∩ｇによって形成される空でない交わりＩg のランクは、インターバルｇのランクに１を足すことにより単純に決定される。交わりを生じるインターバルｇが、交わりＩg を含む最小の要素であるので、このことが起こる。これは単に、インターバルを記憶し検索する方法の結果である。
【００３１】
新たな交わりが形成される時に発生する２つの可能なケースがある。図７（Ａ）で第１のケースを示す。インターバルＩi+1 は、ｇ1 から始まってｇ4 で終わるビンＸの要素と交わる。インターバルＩg は、Ｉi+1 ∩ｇ2 の交わりから生じる。インターバルＩg は、インターバルｇ2 即ち交わりを生じるインターバルの右端と、Ｉi+1 の左端とを有する。よって、インターバルＩg を含み、且つ同じ右端を有する最小のインターバルは、インターバルＩg と同じビンにあるであろう。ビンＸ中のインターバルは、右に合わせて左を分類されている、即ち、インターバルｇ2 の左端アドレスは、インターバルｇ3 の左端アドレスより大きいので、インターバルＩg の左端アドレスより左に左端アドレスを有する最小のインターバルが、交わりを生じるものである。さらに、以下の２つの条件、即ち、
ｒｉｇｈｔ（Ｉs ）＞ｒｉｇｈｔ（Ｉg ）    （式３）
ｌｅｆｔ（ｇ3 ）＜ｌｅｆｔ（Ｉs ）＜ｌｅｆｔ（Ｉg ）      （式４）
を満たすＩg を含むインターバルＩs はない。インターバルＩs が存在したならば、インターバルｇ2 とＩs との交わりは、ビンに別の要素を追加したであろう。このことは、Ｇi が閉包であるとともに、それを含んでいたに違いないので、発生することができない。
【００３２】
図７の（Ｂ）は、第２のケースを示す。Ｉg を含むあらゆるインターバルが、ｇ5 の左端及びＩi+1 の右端を含まなければならない。しかし、このようなインターバルＩs は、次の条件、即ち、
ｒｉｇｈｔ（Ｉs ）＜ｒｉｇｈｔ（ｇ5 ）        （式５）
ｌｅｆｔ（Ｉs ）＝ｌｅｆｔ（ｇ5 ）            （式６）
を満足しない。インターバルがこれらの条件を満足していたら、そのインターバルは、処理が以前のビンに及んでいた間に交わりを生じていたであろう。このことは、インターバルＩg が新たな交わりであるので、発生することができない。
【００３３】
図８は、本発明の第１実施例の方法のフローチャートを示す。ステップ１００において、語句境界ボックスをアクセスする。これは、コンピュータプログラムにより実行することができる。フローはステップ１０２に進み、そこでは、語句境界ボックスの間のスペース（余白）インターバルが決定される。これらのインターバルはメモリに記憶される。
【００３４】
ステップ１０４では、メモリをチェックして、全てのインターバルが処理されたことを確認する。記憶されたインターバルのいずれかが処理されていなければ、ステップ１０６において次のインターバル（新しいインターバル）がメモリから選出される。フローはステップ１０８に進み、全てのビン要素が現インターバルとともに処理されたかどうかが決定される。
【００３５】
ステップ１０８が、現インターバルを処理するビン要素が他にあるということを決定すると、フローはステップ１１０に進み、次のビン要素を選択する。ステップ１１２は、選択されたビン要素が現インターバルに含まれるかどうかをチェックする。選択されたビン要素が、現インターバルに含まれる場合には、選択されたビン要素のランクはステップ１１４において１を増される。フローはステップ１０８に戻る。
【００３６】
選択されたビン要素が現インターバルに含まれないことをステップ１１２が決定した場合には、選択されたビン要素と現インターバルの交わりが、ステップ１１６で決定される。ステップ１１８は、交わりが空でない場合、その交わりがビン要素であるかどうかを決定する。交わりがビン要素でない場合には、ステップ１２０で、その交わりがビン構造に加えられ、そのランクは、選択されたビン要素のランクに１を足されたものと等しくなる。ステップ１１８において、交わりが、選択されたビン要素である場合か、又はステップ１２０の実行が完了した場合には、フローはステップ１０８に戻る。
【００３７】
全てのビン要素がステップ１０８で処理された後、フローはステップ１２２に進行し、現インターバルが唯一つ（ＵＮＩＱＵＥである）かどうかをチェックする。現インターバルが唯一つである場合には、ステップ１２４が実行されて、ランクを１としてビン構造に現インターバルを追加する。現インターバルがＵＮＩＱＵＥではない場合か、又はステップ１２４の実行が完了した場合には、フローはステップ１０４に戻り、処理される別のインターバルがメモリに存在するかどうかを決定する。全てのインターバルが処理された後、フローはステップ１２６に進み、最高ランクを有するビンを選択する。
【００３８】
ステップ１０４を実行する前に、ステップ１００及び１０２を実行する必要はない。別法では、ステップ１０４で、次の集合の語句境界ボックス間の、次のスペースインターバルを決定することができる。ビン構造を充足するための各反復に対して、ステップを修正して、別のスペースインターバルが存在するかどうかを決定し且つスペースインターバルを検出する機能が実行されるであろう。
【００３９】
図９〜図１６で、本発明の方法を用いる例を示す。図９では、文書の骨組みを示し、語句片境界ボックスのみを示す。図９からわかるように、０〜３、５〜９、１１〜１５を範囲とする３つの異なるコラムがある。境界ボックス内にあるテキスト（文字、数字等）の幅がそれぞれ違う６つのデータ列がある。図１０では、Ｉ0 〜Ｉ20とマーク付けられた境界ボックス間インターバルを有する６つの列（横列）が示される。図１０からわかるように、列１は、テキストを含まない４つの離間インターバルを有する。
【００４０】
列１を最初に処理する。図１３では、１５の位置を有するアレイを用いて、ビン構造を作成する。別法では、必要な場合に新たなアドレスを追加してハッシュテーブルを使用することができる。４つのインターバルの各々を、適切なビンに置く。インターバルＩ0 は、０〜１間にアドレス位置を有する。従って、インターバルＩ0 は、ビン１において、小数点の左の数字がインターバルの左端点を示すようにして示される。小数点の右の数字は、そのインターバルのランキングを示す。従って、インターバルＩ0 は、（０．１）という表示によりビン１に配置される。同様に、Ｉ1 は、アドレス位置２〜５の範囲である。従って、インターバルＩ1 は（２．１）という表示でビン５の中に入れられる。同様に、７〜１２のアドレス位置を有するインターバルＩ2 は、（７．１）という表示でビン１２に配置される。インターバルＩ3 は、（１３．１）という表示でビン１５に配置される。これらのインターバルのうちのいずれも互いに交わっていないので、この列は完了である。
【００４１】
列２を次に処理する。インターバルＩ4 は３〜６間に位置している。交わりは、インターバルＩ4 と、ビン構造中に既存している全てのインターバルとの間で決定される。インターバルＩ4 は、既存するどのインターバルとも重複しておらず、インターバルＩ1 と交わっているだけであるということが図１０から明白である。インターバルＩ1 及びＩ4 の交わりはビン要素ではない。従って、新たなインターバルＩ21を次の式を用いて作成する。
【００４２】
Ｉ4 ∩Ｉ1 ＝［３，５］＝Ｉ21      （式７）
【００４３】
図１４では、ビン５は、インターバルＩ21を示す（３．２）という表示を含む。そのインターバルのランクは２である、なぜなら、ランクは、交わりを生じる２つのインターバル、即ちインターバルＩ1 及びＩ4 、のランクの合計であるからである。インターバルＩ4 はまた、（３．１）という表示でビン６に追加される。ビン５は、その中に２つの要素を有することとなり、１番上に最も高いランクのものを置く。
【００４４】
次に、インターバルＩ5 を処理する。図１０では、インターバルＩ5 はインターバルＩ2 及びＩ3 の両方と交わる。これらの交わりは、インターバルＩ22及びＩ23を作り出し、それらは次の式から決定される。
【００４５】
Ｉ5 ∩Ｉ2 ＝［９，１２］＝Ｉ22        （式８）
Ｉ5 ∩Ｉ3 ＝［１３，１４］＝Ｉ23      （式９）
【００４６】
各インターバルＩ22及びＩ23のランキングは、それらのランクが２となるようにして前と同じように決定される。この列が完了したので、ビン構造を更新して図１４で示す。図１４からわかるように、ビン１２は新しいインターバルＩ22に対する表示（９．２）を含み、また、新たなＩ23を表示（１３．２）でビン１４内に配置する。インターバルＩ5 はまた、ランクを１としてビン１４に追加され、（９．１）という表示によって示される。
【００４７】
図１１では、ビンにおけるインターバルを示す。ランク２のインターバルは、Ｉ21、Ｉ22、Ｉ23であり、ランク１のインターバルはＩ0 〜Ｉ5 である。また、列３には、インターバルＩ6 〜Ｉ9 を示す。
【００４８】
図１１からわかるように、インターバルＩ6 は他のどのインターバルとも交わらない。従って、図１５で示すようにビン２に加えられる。
【００４９】
インターバルＩ7 は、３つのインターバルＩ21、Ｉ1 、Ｉ4 と交わる。これらのインターバルのインターバルＩ7 との交わりは、以下の式により決定される。
【００５０】
Ｉ7 ∩Ｉ4 ＝［３，６］＝Ｉ4   （式１０）
Ｉ7 ∩Ｉ21＝［３，５］＝Ｉ21  （式１１）
Ｉ7 ∩Ｉ1 ＝［３，５］＝Ｉ21  （式１２）
【００５１】
式１０の交わりは単純にＩ4 である。このようにインターバルＩ4 はインターバルＩ7 に含まれている。従って、新たなインターバルはビン構造に追加されないが、インターバルＩ4 のランクに１が増される。図１５では、ビン６内に配置されるインターバルＩ4 は、更新された表示（３．２）を有する。従って、式１１は、新たな要素をビン構造に追加しないが、インターバルＩ21のランクを３に増す。Ｉ7 とＩ1 との交わりは、ビン構造に既存するインターバルＩ21であるので、何も実行されない。インターバルＩ7 は、１というランクを付けられてビン７に加えられる。
【００５２】
図１１では、インターバルＩ8 は、インターバルＩ22、Ｉ2 、及びＩ5 と交わる。これらの交わりは、以下のインターバルを生成する。
【００５３】
Ｉ8 ∩Ｉ22＝［９，１１］＝Ｉ8   （式１３）
Ｉ8 ∩Ｉ2 ＝［９，１１］＝Ｉ8   （式１４）
Ｉ8 ∩Ｉ5 ＝［９，１１］＝Ｉ8   （式１５）
【００５４】
第１の交わりである式１３は、３とランク付けしてビン構造にインターバルＩ8 を加える、なぜなら、インターバルＩ22のランク２に１が加えられるからである。インターバルＩ8 はビン構造に既に追加されているので、式１４及び式１５における交わりは、何の影響も及ぼさない。
【００５５】
図１１では、インターバルＩ9 が、インターバルＩ23、Ｉ3 、及びＩ5 と交わる。以下の式により、これらの交わりを決定する。
【００５６】
Ｉ9 ∩Ｉ23＝［１３，１４］＝Ｉ23  （式１６）
Ｉ9 ∩Ｉ3 ＝［１３，１５］＝Ｉ3   （式１７）
Ｉ9 ∩Ｉ5 ＝［１３，１４］＝Ｉ23  （式１８）
【００５７】
インターバルＩ23及びＩ3 のランキングは、各々がインターバルＩ9 に含まれるので、１を増される。式１８は、インターバルＩ23がビン構造に既存するので、何の影響も及ぼさない。図１５は、列３が処理された後のビン構造を示す。
【００５８】
列４〜６は、同じように処理されて、図１６で示す最終的なビン構造が形成される。ビン５が表示（３．６）を有し、ビン１１が表示（９．６）を有することに注目したい。従って、最高ランキングのインターバルは、６というランクを有する。よって、この処理を用いたコラム離間インターバルは、［３，５］及び［９，１１］の長さを有するインターバルであると決定される。図９からわかるように、これは、インターバル０〜３、５〜９、１１〜１５の範囲にあるコラム間の最小インターバルである。
【００５９】
式１及び式２を用いて交わりを決定するうちに、等しい現象が現れた場合には、本発明の方法は、幅ゼロのコラムセパレータを作成することができる。例えば、図１６の格納ビン１４は、要素（１３．５）を有する。これは、図９のコラム位置１３〜１４間の幅ゼロのコラムセパレータに相当する。
【００６０】
コンピュータプログラムは、ビン構造のその他のインターバルと交わる現インターバルを可視化しない。従って、本発明の方法は、現インターバルと交わらないビンインターバルの処理を除去する方法を含む。
【００６１】
例えば、図１１のインターバルＩ7 と交わる全要素を見ると、インターバルＩ7 の左端は３である。インターバルＩ7 との交わりを決定する処理は、ビン３で開始されるとともに、右のビンまで続く。処理は、インターバルＩ7 と関連する最右インターバルの右端を含むビンまで続く。例えば、ビン７内に配置されるインターバルＩ7 と関連する最右インターバルは、インターバルＩ2 である。インターバルＩ2 の右端は１２である。従って、処理はビン３からビン１２まで続く。
【００６２】
本発明の方法を使用する単純なプログラムを以下に示す。第１のｉ個のインターバルの閉包をＧi とし、Ｉi+1 を新たなインターバルとする。
【００６３】
【外１】
0003917196.tif 000002
【００６４】
このプログラムは、実に単純であり、その他のプログラムを使用して本発明のステップを実行することが可能である。
【００６５】
好適実施例に対するその他の変更をなすことが可能である。例えば、左端アドレスをハッシュテーブル内に記憶することができる。従って、上記方法と同じようにして右〜左へと検索を実行することができる。
【００６６】
表文書がスキューしている場合には、別の変更をなすことが可能である。コラムのスキューが測定される場合には、境界ボックスを決定し、且つこれらの境界ボックスのみをスキュー解除することにより、上記好適実施例が変更される。この方法は、全ビットマップを処理することに対して好ましい。残りの処理は、先に述べたものと同じように実行されることができる。
【００６７】
【発明の効果】
本発明では、ビットマップを復号化することなく、表文書のコラム構造を決定することができる。また本発明は、表中の語句片を離間するラインインターバルを調べることによって、コラムを離間するものを検索するが、本発明のこの方法は、より信頼性が高いとともに、コンピュータ処理の見地からみても効果的である。本発明は、ライン交わり演算の下で、ラインインターバルの集合の順序付けされた閉包を生成し且つ維持する。多くの語句片離間インターバルの交わりであるコラム離間インターバルを、本発明の技術により容易に識別することができる。
【図面の簡単な説明】
【図１】本発明の方法を使用する装置である。
【図２】多様なコラム配列を有する表文書の例である。
【図３】図２の表文書の骨組みであり、語句片境界ボックスにより示されている。
【図４】語句片離間インターバルとコラム離間インターバルを示す２つのコラムを有する単純な表を示す。
【図５】単純なラインインターバル集合のビン構造である。
【図６】図５のビン構造において格納されるラインインターバルの単純な集合を示す。
【図７】（Ａ）及び（Ｂ）は、ビン中のインターバルと新たなインターバルとの交わりの例を示す。
【図８】本発明の方法のフローチャートである。
【図９】本発明の方法を用いた例を示す。
【図１０】本発明の方法を用いた例を示す。
【図１１】本発明の方法を用いた例を示す。
【図１２】本発明の方法を用いた例を示す。
【図１３】本発明の方法を用いた例を示す。
【図１４】本発明の方法を用いた例を示す。
【図１５】本発明の方法を用いた例を示す。
【図１６】本発明の方法を用いた例を示す。
【符号の説明】
１０    文書スキャナ
１２    コンピュータ
１４    モニタ
１６    プリンタ
３０    語句片境界ボックス
３２    コラム境界ボックス
４０    ハッシュテーブル
４２    ビン構造
【図１】
0003917196.tif 000003
【図２】
0003917196.tif 000004
【図３】
0003917196.tif 000005
【図４】
0003917196.tif 000006
【図５】
0003917196.tif 000007
【図６】
0003917196.tif 000008
【図７】
0003917196.tif 000009
【図８】
0003917196.tif 000010
【図９】
0003917196.tif 000011
【図１０】
0003917196.tif 000012
【図１１】
0003917196.tif 000013
【図１２】
0003917196.tif 000014
【図１３】
0003917196.tif 000015
【図１４】
0003917196.tif 000016
【図１５】
0003917196.tif 000017
【図１６】
0003917196.tif 000018