(57)【特許請求の範囲】
【請求項１】
入力された文書イメージ内に含まれる表イメージを識別する表イメージ識別工程と、
前記表イメージ内に存在するテキストの領域を示す複数のテキストブロックを識別するテキストブロック識別工程と、
前記識別された各テキストブロックの水平方向位置情報に基づいて、前記複数のテキストブロックを水平方向でグループ分けする水平グループ分け工程と、
前記識別された各テキストブロックの垂直方向位置情報に基づいて、前記複数のテキストブロックを垂直方向でグループ分けする垂直グループ分け工程と、
前記水平グループ分け工程により水平方向でグループ分けされた結果と、前記垂直グループ分け工程により垂直方向でグループ分けされた結果とに基づいて、前記複数のテキストブロックそれぞれに対して、表における行アドレスと列アドレスとを割り当てる第１のアドレス割当工程と、
前記行アドレスと列アドレスとの少なくともいずれかにアドレス範囲が割り当てられたテキストブロックについて、細分することができるか否か判定する細分判定工程と、
前記細分判定工程で細分可能と判定されたテキストブロックを細分する細分工程と、
前記細分工程で細分されたテキストブロックに対して、新たな行アドレスと列アドレスとを割り当てる第２のアドレス割当工程と、
前記細分工程で前記テキストブロックが細分されなかった場合、前記テキストブロックそれぞれに対して前記第１のアドレス割当工程で割り当てられた行アドレスと列アドレスとを記憶し、前記細分工程で前記テキストブロックが細分された場合、当該細分されたテキストブロックに対して前記第２のアドレス割当工程で割り当てられた新たな行アドレスと列アドレスとを記憶する記憶工程と
を備えることを特徴とするイメージ処理方法。
【請求項２】
前記記憶工程では、前記文書イメージ内の区分されたブロックをノードとして有する階層木構造において、前記各テキストブロックに対応するノードに当該割り当てられた行アドレスと列アドレスとを記憶することを特徴とする請求項１に記載のイメージ処理方法。
【請求項３】
入力された文書イメージ内に含まれる表イメージを識別する表イメージ識別手段と、
前記表イメージ内に存在するテキストの領域を示す複数のテキストブロックを識別するテキストブロック識別手段と、
前記識別された各テキストブロックの水平方向位置情報に基づいて、前記複数のテキストブロックを水平方向でグループ分けする水平グループ分け手段と、
前記識別された各テキストブロックの垂直方向位置情報に基づいて、前記複数のテキストブロックを垂直方向でグループ分けする垂直グループ分け手段と、
前記水平グループ分け手段により水平方向でグループ分けされた結果と、前記垂直グループ分け手段により垂直方向でグループ分けされた結果とに基づいて、前記複数のテキストブロックそれぞれに対して、表における行アドレスと列アドレスとを割り当てる第１のアドレス割当手段と、
前記行アドレスと列アドレスとの少なくともいずれかにアドレス範囲が割り当てられたテキストブロックについて、細分することができるか否か判定する細分判定手段と、
前記細分判定手段で細分可能と判定されたテキストブロックを細分する細分手段と、
前記細分手段で細分されたテキストブロックに対して、新たな行アドレスと列アドレスとを割り当てる第２のアドレス割当手段と、
前記細分手段で前記テキストブロックが細分されなかった場合、前記テキストブロックそれぞれに対して前記第１のアドレス割当手段で割り当てられた行アドレスと列アドレスとを記憶し、前記細分手段で前記テキストブロックが細分された場合、当該細分されたテキストブロックに対して前記第２のアドレス割当手段で割り当てられた新たな行アドレスと列アドレスとを記憶する記憶手段と
を備えることを特徴とするイメージ処理装置。
【請求項４】
前記記憶手段は、前記文書イメージ内の区分されたブロックをノードとして有する階層木構造において、前記各テキストブロックに対応するノードに当該割り当てられた行アドレスと列アドレスとを記憶することを特徴とする請求項３に記載のイメージ処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ブロック選択処理を使用して文書頁内の異なるタイプのイメージデータを弁別するために文書頁を分析し、該分析したイメージデータに基づいて更に処理するために文書頁内のイメージデータを抽出するイメージ処理方法及び装置に関し、特に、イメージデータを表として識別すると、表として識別されたイメージデータ内の行及び列を規定し、表内のテキストブロックに行及び列のアドレス座標を割り当て、必要に応じて、あるテキストブロックを更に小さなテキストブロックに細分し、行及び列のアドレス座標を用いて後処理として表からのテキストデータの抽出を行うために階層木構造に座標を記憶するイメージ処理方法及び装置に関する。
【０００２】
【従来の技術】
従来の特徴抽出装置では、文書内の異なるタイプのイメージデータは、まずイメージタイプに従って識別され、次にタイプに基づいてグループ分けされる。特に、従来の特徴抽出装置は、テキストデータ、表データ、またはグラフデータ等の文書内のイメージデータを識別するためにブロック選択ルーチンを実行する。識別されたイメージデータは、イメージタイプ、好ましくは、ブロック矩形フォーマットに従ってグループ分けされる。イメージデータがブロック矩形フォーマットでグループ分けされると、当該ブロック内のイメージデータは、そのイメージタイプに基づいて更に処理するために抽出される。
【０００３】
米国特許出願第０７／８７３、０１２号及び米国特許出願第０７／３８８、７８１号に記載された技術等の最近開発されたブロック選択技術が、文書頁内の異なるタイプのイメージデータを弁別するために文書頁内のイメージの自動分析を行う特徴抽出装置に採用されている。このようなブロック選択技術により得られた結果は、光学式文字認識（OCR）、データ圧縮、データルーチング、データ抽出などのような、イメージに対して行うその後の処理の種類を決定するために使用される。たとえば、テキストデータとして指定されたイメージデータはOCR処理にかけられるが、ピクチャデータとして指定されたイメージデータはOCR処理にはかけられない。その結果、複数の異なるタイプのイメージデータを入力して、オペレータの介入なしに自動処理することができる。
【０００４】
上述のようなブロック選択技術の動作例を、図１〜３を参照して下記に述べる。
【０００５】
図１は代表的な文書の頁を示す。文書頁１は、２コラムフォーマットで配列されている。頁１は、題名２、水平線３、テキストデータの線を含むテキスト領域４、５及び６、ハーフトーンピクチャ領域７、フレーム領域８、及び表１０を有する。米国特許出願第０７／８７３、０１２号及び米国特許出願第０７／３８８、７８１号に記載されたブロック選択技術によると、文書頁１の各領域が、その中に位置するイメージデータのタイプに従って指定され、次いでイメージデータがその各々のタイプに基づいて区分される。ブロック選択アプリケーションが文書頁を処理すると、図２に示すように階層木構造が生成される。
【０００６】
図２において、階層木構造２０は、文書頁１のイメージデータの区分されたブロックを表す複数のノードを有する。木構造の各ノードは、処理された文書頁のイメージデータの各ブロックの特徴を規定する特徴データを有する。たとえば、特徴データは、ブロック位置データ、サイズデータ、属性データ（テキスト、ピクチャ、表等のイメージタイプ）、サブ属性データ、子ノード及び親ノードのポインタを含むことができる。この点に関し、子すなわち「子孫」ノードは、イメージデータのより広いブロック内に全て存在するイメージデータを表す。たとえば、表内に位置するテキストブロックは、表ブロックの子ノードとして指定される。子ノードは、階層木構造では、親ノードすなわち根ノード２１から分岐するノード２２と同一レベルにあるノードのように、親ノードから分岐するノードとして描かれる。
【０００７】
階層木構造２０のような階層木構造は一旦生成されると、メモリに記憶される。文書イメージ内のイメージデータの処理要求を受けると、階層木構造２０はメモリから検索され、ブロック化されたイメージデータが対応するノードに記憶された特徴データに従って処理される。たとえば、ユーザは更にデータを処理するために表の種々のテキストブロック内のデータを抽出することができる。文書頁のイメージデータを処理するために階層木構造を使用するほかに、図３に示すブロックテンプレート４０のディスプレイのように文書頁の広範なフォーマットを生成して表示するために階層木構造が使用される。図２に示される階層木構造に記憶された特徴データに基づいて文書頁のブロックテンプレート４０が生成され、ユーザに表示される。
【０００８】
文書頁のブロックテンプレートは、階層木構造と、階層木構造の各ノードに記憶された特徴データとを直接反映している。ノード内の特徴データは、ブロックの形状、位置、サイズを生成するために使用される。更に、各ノード内の特徴データは、ブロック内に含まれるイメージデータのタイプを識別するために使用される。たとえば、図３に示すように、ブロックテンプレート４０はテキストブロック４１、４２及び４３を有し、各テキストブロックはそれぞれノード２８、３１及び３２に対応する。また、表ブロック４８も図示されており、該表ブロック４８はそれぞれノード３９Ａ−３９Ｎに対応するテキストセル４９を有する。
【０００９】
【発明が解決しようとする課題】
しかしながら、上述したブロック選択技術には不具合があった。たとえば、ブロック選択技術のエラーのため、あるいは、分析した文書頁のスキャンや印刷が不十分であるため、表内のテキストデータが別々のグループにあるいは同一のグループにグループ分けされるときに、表として識別されるイメージデータのブロック選択処理に誤まりが生じることがある。この結果、表イメージデータ及びその中のテキストデータの後処理が不十分になる。すなわち、イメージデータが表として識別されるときは、その表が有するテキストデータは、表内の行及び列の位置に基づいて表内で同一のグループにあるいは別々のグループにグループ分けされなければならない。このため、テキストデータがそのブロック内に含まれるべきでない他のテキストデータと同一のグループまたはブロックに水平方向あるいは垂直方向にグループ分けされブロック化されるとき、または、テキストデータが表内の他のテキストデータと同一のグループまたはブロックに水平方向あるいは垂直方向にグループ分けされブロック化されるときに、問題が生じる。
【００１０】
本発明は、上述の不具合を解消するために、表イメージデータ及びその中のテキストデータの後処理が不十分にならないように、表内のイメージデータを適切に抽出することができるイメージ処理方法及び装置を提供することを目的とする。
【００１１】
【課題を解決するための手段】
本発明は、上記目的を達成するため、入力された文書イメージ内に含まれる表イメージを識別する表イメージ識別工程と、前記表イメージ内に存在するテキストの領域を示す複数のテキストブロックを識別するテキストブロック識別工程と、前記識別された各テキストブロックの水平方向位置情報に基づいて、前記複数のテキストブロックを水平方向でグループ分けする水平グループ分け工程と、前記識別された各テキストブロックの垂直方向位置情報に基づいて、前記複数のテキストブロックを垂直方向でグループ分けする垂直グループ分け工程と、前記水平グループ分け工程により水平方向でグループ分けされた結果と、前記垂直グループ分け工程により垂直方向でグループ分けされた結果とに基づいて、前記複数のテキストブロックそれぞれに対して、表における行アドレスと列アドレスとを割り当てる第１のアドレス割当工程と、前記行アドレスと列アドレスとの少なくともいずれかにアドレス範囲が割り当てられたテキストブロックについて、細分することができるか否か判定する細分判定工程と、前記細分判定工程で細分可能と判定されたテキストブロックを細分する細分工程と、前記細分工程で細分されたテキストブロックに対して、新たな行アドレスと列アドレスとを割り当てる第２のアドレス割当工程と、前記細分工程で前記テキストブロックが細分されなかった場合、前記テキストブロックそれぞれに対して前記第１のアドレス割当工程で割り当てられた行アドレスと列アドレスとを記憶し、前記細分工程で前記テキストブロックが細分された場合、当該細分されたテキストブロックに対して前記第２のアドレス割当工程で割り当てられた新たな行アドレスと列アドレスとを記憶する記憶工程とを備えることを特徴とするイメージ処理方法を提供する。
【００１２】
また、本発明は、上記目的を達成するため、入力された文書イメージ内に含まれる表イメージを識別する表イメージ識別手段と、前記表イメージ内に存在するテキストの領域を示す複数のテキストブロックを識別するテキストブロック識別手段と、前記識別された各テキストブロックの水平方向位置情報に基づいて、前記複数のテキストブロックを水平方向でグループ分けする水平グループ分け手段と、前記識別された各テキストブロックの垂直方向位置情報に基づいて、前記複数のテキストブロックを垂直方向でグループ分けする垂直グループ分け手段と、前記水平グループ分け手段により水平方向でグループ分けされた結果と、前記垂直グループ分け手段により垂直方向でグループ分けされた結果とに基づいて、前記複数のテキストブロックそれぞれに対して、表における行アドレスと列アドレスとを割り当てる第１のアドレス割当手段と、前記行アドレスと列アドレスとの少なくともいずれかにアドレス範囲が割り当てられたテキストブロックについて、細分することができるか否か判定する細分判定手段と、前記細分判定手段で細分可能と判定されたテキストブロックを細分する細分手段と、前記細分手段で細分されたテキストブロックに対して、新たな行アドレスと列アドレスとを割り当てる第２のアドレス割当手段と、前記細分手段で前記テキストブロックが細分されなかった場合、前記テキストブロックそれぞれに対して前記第１のアドレス割当手段で割り当てられた行アドレスと列アドレスとを記憶し、前記細分手段で前記テキストブロックが細分された場合、当該細分されたテキストブロックに対して前記第２のアドレス割当手段で割り当てられた新たな行アドレスと列アドレスとを記憶する記憶手段とを備えることを特徴とするイメージ処理装置を提供する。
【００１５】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して詳細に説明する。
【００１６】
図４は、本発明のブロック選択に基づいた表操作及びテキストデータ抽出装置を組み込んだ代表的なコンピュータ機器の外観を示す図である。
【００１７】
図４には、マイクロソフトＷｉｎｄｏｗｓ  ＯＳ等のウインドウ型オペレーションシステムを有するＩＢＭ  ＰＣまたはＰＣ互換機等のコンピュータ機器４１０が示してある。コンピュータ機器４１０には、モノクロまたはカラーディスプレイモニタ４１２が設けられ、ユーザに対しイメージを表示する。コンピュータ機器４１０には更に、データファイル及びアプリケーションプログラムファイルを記憶する固定ディスクドライブ４１１と、テキストデータを入力し、モニタ４１２の表示画面に表示される対象を操作するキーボード４１３と、ディスプレイ画面に表示される対象を指示したり操作したりするための、マウス等のポインティング・デバイス４１４とが設けられる。
【００１８】
複数頁を有する文書はスキャナ４１６によって入力される。スキャナ４１６は文書の各頁または他のイメージをスキャンして、これらの頁のビットマップイメージデータをコンピュータ機器４１０に供給する。該イメージデータは、圧縮または非圧縮フォーマットでディスク４１１に記憶される。
【００１９】
コンピュータ機器４１０が処理した文書を出力するために従来のカラープリンタ４１８が設けられる。
【００２０】
更に、ローカル・エリア・ネットワークとインターフェースするためのネットワーク・インターフェース４２４、及びファクシミリ／モデムを介してファクシミリ・メッセージ及び他のデータファイルを送受信するためのファクシミリ／モデム・インターフェース４２６が設けられる。
【００２１】
オペレータの指示に従って且つウインドウ型オペレーションシステムの制御のもとで、デスクトップ・パブリッシング・プログラム、ドローイング・アプリケーション・プログラム、ブロック選択アプリケーション等の記憶されたアプリケーション・プログラムが選択的に起動され、データを処理したり操作したりする。また、オペレータの指示に従って且つこれらの記憶されたアプリケーション・プログラムに基づいて、イメージをモニタ４１２に表示したり、モニタ４１２に表示されているイメージをプリンタ４１８で印刷するようにコマンドが発せられる。  最も典型的には、本発明のブロック選択プログラムを含むコンピュータディスク４１１に記憶されたアプリケーションは、フロッピィディスク、ＣＤ−ＲＯＭ、またはコンピュータ掲示板などのコンピュータ読み出し可能媒体から各アプリケーションをダウンロードしてディスク４１１に記憶されたものである。
【００２２】
図５は、コンピュータ機器４１０の内部構成を示す詳細ブロック図である。図５に示すように、コンピュータ機器４１０は、コンピュータバス５２１に接続された、プログラム式マイクロプロセッサ等から成る中央演算処理装置（ＣＰＵ）５２０を有する。また、スキャナ・インターフェース５２２、プリンタ・インターフェース５２３、ネットワーク・インターフェース５２４、ファックスモデム・インターフェース５２６、ディスプレイ・インターフェース５２７、キーボード・インターフェース５２８、及びマウス・インターフェース５２９が、コンピュータバス５２１に接続されている。
【００２３】
ＣＰＵ５２０がアクセスできるように、ランダム・アクセス・メモリ（ＲＡＭ）等の主メモリ５３０がコンピュータバス５２１に接続されている。特に、ディスク４１１に記憶されたアプリケーション・プログラムに関連する命令等、記憶されたアプリケーション・プログラムの命令列を実行するときに、ＣＰＵ５２０は、これらの命令列を、ディスク４１１（またはネットワーク・インターフェース５２４を介してまたはフロッピィ・ディスク・ドライブ（図示せず）を介してアクセスされる媒体等の他の記憶媒体）から主メモリ５３０にロードして、主メモリ５３０からこれらの記憶されたアプリケーション・プログラムの命令列を読み出して実行する。
【００２４】
[ブロック選択を使用した表及びテキストブロックの識別]
簡潔に述べると、本発明は、表として識別されたイメージデータ内の各テキストブロック内のテキストの表セルの位置を求めてこれを識別し、テキストブロック内のテキストの表セルの位置によってそのテキストブロックが更に１つ以上の行及び列に細分することができるか否かを決定するコンピュータで実行される方法を提供する。
【００２５】
本発明によると、イメージデータ内における表の位置が求められると、そのイメージデータ内のテキストブロックは、前述したような公知のブロック選択技術を使用して識別される。テキストブロックを識別すると、そのテキストブロックは文書頁内の水平方向位置情報及び垂直方向位置情報に基づいて区分け（ソート）され、次いで表内の行及び列の位置に基づいてアドレス座標を割り当てられる。アドレス座標が割り当てられると、各テキストブロックは更に分析されて、行アドレス範囲、列アドレス範囲、あるいはその双方等のアドレス範囲を有するテキストブロックの位置が求められる。アドレス範囲を有するテキストブロックは、テキストブロック内のテキストの表セルの間に行及び列区切り線を挿入することによってそのテキストブロックを更に小さなテキストブロックに細分することができるか否かを決定するために、アドレス範囲のタイプに基づいて垂直方向または水平方向の区切り処理にかけられる（たとえば、列アドレス範囲は垂直方向区切り処理を受ける）。細分された各テキストブロックは、新たに位置決めされた行及び列区切り線に基づいて表内のアドレス座標が割り当てられる。次いで、全てのテキストブロックのアドレス座標は、公知のブロック選択技術に従って階層木構造を更新するために記憶される。
【００２６】
図６及び図７は、本発明のブロック選択アプリケーションを使用して表識別、並びにテキストブロックの細分及びテキストブロックのアドレス指定を実行する方法を示すフローチャートである。図６及び図７に示された処理ステップは、ディスク４１１に記憶されたコンピュータ処理ステップに従ってＣＰＵ５２０によって実行される。
【００２７】
ステップＳ６００において、文書頁内のピクセルイメージデータは装置内に入力され、ディスク４１１に記憶される。イメージデータは、イメージをピクセル単位で表したものであり、好ましくは、ピクセルデータはバイナリピクセルデータであり、すなわち、スキャナ４１６、ネットワーク・インターフェース４２４、またはモデム・インターフェース４２６を介して入力された白黒イメージデータである。ステップＳ６０１においてブロック選択アプリケーションが開始される。簡潔のために、異なるイメージタイプの文書頁全体のブロック選択の開始及び処理はここでは説明せず、イメージデータの選択及び分析によってどのように表が識別されるかについて説明する。文書頁全体におけるイメージデータを弁別するブロック選択技術の詳細に関しては、米国特許出願第０７／８７３、０１２号及び米国特許出願第０７／３８８、７８１号に開示されたブロック選択技術を参照すべきである。本発明は、イメージデータを表として識別して、必要に応じて、ブロック選択処理により１つのテキストブロックを細分したときに、表の１つ以上の行及び／または列にまたがるテキストブロックを更に小さなテキストブロックに細分することを対象とする。
【００２８】
[表識別］
ステップＳ６０３において、ブロック選択によりブロック化領域を表として識別する方法について簡単に説明する。この処理の詳細については米国特許出願第０７／８７３、０１２号に開示されたブロック選択技術を参照すべきである。
【００２９】
このように、ステップＳ６０３において、上述のブロック選択技術の１つを使用してフレーム化データの位置が求められたとき、該データは、そのフレームが「フレーム表」であるか「フレーム・ハーフトーン」であるかを判別するために分析される。従って、フレームデータは、黒ピクセルではなく白ピクセルであると検出された白輪郭を得るために、接続要素の内部を調べることによって表または表状に組織されたデータを含むか否かを判別するために更に分析される。この点に関して、非テキストユニットの内部は、非テキストユニットの内部の底部右側部分から上部左側部分に向う第１方向でスキャンされる。最初の白ピクセルに遭遇すると、該分析された白ピクセルに隣接するピクセルは、たこ足パターンに類似した状態にある。従って、たこ足パターンに従って白輪郭を追跡することが４方向ベクトルで実行される。白輪郭追跡は、全ての白輪郭が黒ピクセルに囲まれるかまたは追跡されるまで４方向で継続される。各白輪郭の位置が求められると、非テキスト対象物内に囲まれた全ての白輪郭が追跡されるまで上述のように前記第１の方向でスキャンされる。
【００３０】
このとき、非テキストユニットの密度が、接続要素内の黒ピクセルを計数し黒ピクセルの数を矩形フォーマットで囲まれたピクセルの全数で割ることによって算出される。非テキストユニット内で見出された白輪郭の数が調べられる。白輪郭の数が予め規定された数よりも多いかまたは等しい場合は、その非テキストイメージは、実際に、表または一連の表状に配置されたテキストブロックである可能性がある。
【００３１】
次に、白輪郭の充填率が決定される。白輪郭の充填率は、白輪郭が非テキストイメージによって囲まれた領域を充填する度合いである。充填率が高ければ、非テキストイメージが表または表状に配置されたテキストデータの連続である可能性がある。しかし、充填率が低ければ、非テキストイメージが表または表状に配置されたテキストデータの連続ではない可能性が大きい。
【００３２】
充填率が高ければ、非テキストイメージが表または表状に配置されたテキストデータの連続である可能性がある。この決定の確信を高めるために、白輪郭が水平方向及び垂直方向の双方に延びる格子状構造を形成しているか否かを判別するために白輪郭を調べる。具体的には、非格子状に配置された白輪郭は、それらの境界が少なくとも２つの輪郭を横切って水平方向及び垂直方向に延びているのでなければ、再結合される。表を表す白輪郭は再結合されにくい一方、表ではない、たとえば、ハーフトーンイメージまたは線画用の白輪郭は再結合されやすい。従って、再結合率を調べる。
【００３３】
再結合率が高ければ、すなわち、再結合後に残っている白輪郭の数が所定の数よりも多ければ、この非テキストユニットはハーフトーンイメージまたは線画であるとされる。しかし、再結合率が所定の数よりも少なければ、非テキストイメージは「表」であるとされる。
【００３４】
[テキストブロック識別、細分化、アドレス指定]
フレーム領域が表であると指定されると、ステップＳ６０５において、表であると指定された領域内のテキストブロックの位置が求められる。すなわち、接続要素を検出して８方向に分類するように新たに指定された表領域の内部が検査される。表内にテキストブロックの位置を求める処理は、米国特許出願第０７／８７３、０１２号に詳細に記載されている。
【００３５】
ブロック選択処理の後、識別された表は表内に複数のテキストブロックを含むことがある。しかし、テキストブロックは無作為に処理され、文書頁内の位置に基づいて位置情報を割り当てられる。その結果、テキストブロックは表内の行／列順に位置せず、階層木構造に記憶されるときに表ノードから無作為に分岐する。このことは、表内の各テキストブロックにとっては、編集スタイルのため、または印刷や文書頁のスキャンが不十分であるため、他のテキストブロックが同一の個別の白領域内に位置されることがあることを意味する。従って、テキストブロックは、水平方向、垂直方向、または双方向に２つ以上のテキストの表セルを含むことがある。すなわち、ブロック選択の後では、表内の各テキストブロックは１つの表セルのみに対応すべきである。しかし、上述のように、１つのテキストブロックは、水平方向、垂直方向、または双方向に２つ以上の表セル項目を含むことがある。また、１つの表セル項目は２つ以上のテキストブロックに分割されることがある。
【００３６】
後処理のために表から特定のテキストデータを適切に抽出するために、本発明は、表セル構造を分析し、テキストブロックに行及び列のアドレス座標を割り当て、次いで、１つ以上の表セルを有するテキストブロックを更に小さなテキストブロックに細分できるか否かを判別するためにテキストブロックを分析する。
【００３７】
こうして、ステップＳ６０６において、表構造の分析が実行される。しかし、表構造を分析する前に、表の定義を説明する。基本的な表構造は図１０に示すように定義される。図１０に示すように、表６００は５本の格子線で規定され、５本の格子線は４つの行及び３つの列を形成する。各テキストブロックはブロック選択処理により位置情報を割り当てられる。位置情報は、表に相対する位置ではなく、分析された文書頁内のテキストブロックの位置に関する。更に、図１０に示すように表６００は列２及び列３において複数のテキスト線を有する。従って、本発明によらなければ、複数線を有する列の１つの線のみ、たとえば、表セル６０１を抽出して後処理するためには、表セル全体またはテキストブロック全体を抽出しなければならない。しかし、本発明の方法を適用すると、表セル６０１のみならず列２及び列３の残りのテキスト線も、個々の列またはテキストブロックに細分され、それによって１つの列内の個々の線の抽出が可能となる。
【００３８】
このようにして、ステップＳ６０６において、識別された表内の全てのテキストブロックは水平方向位置情報に基づいて区分けされる。たとえば、第１行にある全てのテキストブロックは同一グループに分けられる。このタスクを実行するために、最も左側の座標を有するブロックをグループ１に入るものとして選択する。次いで、全ての他のテキストブロックを、最大水平方向重複法を使用して、現在形成されているグループと比較する。すなわち、現在形成されたグループと選択されたテキストブロックとの最大水平方向重複率を所定の閾値"t_h"と比較する。最大水平方向重複率は次の式で求められる。
【００３９】
最大水平方向重複＝最大（水平方向重複領域／現在形成されたグループの幅、水平方向重複領域／選択されたテキストブロックの幅）
最大水平方向重複が"t_h"よりも大きいときは、選択されたテキストブロックは現在形成されたグループ内に置かれ、グループの水平方向範囲は更新される。重複が起こらないとき、すなわち、最大重複が"t_h"よりも小さいときは、選択されたテキストブロックは別のグループ内に置かれる。表内の全てのテキストブロックは同一の方法で分析される。
【００４０】
水平方向位置に従って全てのテキストブロックが同様のグループ内に区分けされると、ステップＳ６０６では、テキストブロックの１つのグループが、表での当該グループの順序を決定するために区分けされる。これは、水平方向位置情報を分析することにより実行される（ステップＳ６０８）。
【００４１】
ステップＳ６０８で実行された区分けに基づいて、ステップＳ６０９では、各テキストブロックグループ内の距たりまたはギャップに基づいて、表用の行が算出される。具体的には、各グループ内のテキストブロックは、位置情報に基づいて１つの行領域に属すると仮定され、表の１つの行内にあると決定される。しかし、たとえば、図１１及び図１２に示すように、同一グループ内のテキストブロックが２つ以上の行領域に属しており、１つ以上の行に亘るため容易に区切ることができない状況もある。
【００４２】
そのような場合には、本発明のブロック選択処理は、テキストブロックの開始位置と終了位置を判別するために行領域が重なり合うテキストブロックの位置を求める。このタスクを実行するために、１つまたは複数の行が２つ以上の行領域に亘るテキストブロックとどこで交差できるかを判別する。この判別に基づいて、行範囲を決定することができる。行領域が重なり合う各テキストブロックの位置が求められ分析されると、該各テキストブロックには、その各ブロックとその両側に隣接するグループとの間の相対位置に基づいて行アドレス範囲が割り当てられる。同様に、複数行に亘らない残りのテキストブロックに行アドレスが割り当てられる。たとえば、図１１に示すように、テキストブロック７０１は同一グループ内の隣り合うテキストブロックの２つの行の間のギャップにまたがり、従って、行アドレス範囲がテキストブロック７０１に割り当てられる。すなわち、テキストブロック７０１は、（ｎ，ｎ＋１）という行アドレス範囲が割り当てられ、但し、ｎ−１は前のグループの最後の行の番号である。
【００４３】
水平方向位置に基づいたテキストブロックの区分けの仕方（Ｓ６０６）及びテキストブロックのグループの区分けの仕方（Ｓ６０８）、及び行アドレスの計算及び割り当ての仕方（Ｓ６０９）については、図８に関連して下記により詳細に説明する。
【００４４】
図８は、ステップＳ６０６〜Ｓ６０９で実行される処理を詳細に説明するフローチャートである。
【００４５】
図８を参照すると、表構造に対するブロック選択を実行し表内にテキストブロックが規定された後、ステップＳ６３０において前記各テキストブロックの座標を使用してその水平方向位置に従って全てのテキストブロックを区分けする。具体的には、どのブロックが表内で最もその左側にあるかを決定するために、表内の各テキストブロックの左側座標を調べる。最も左側の位置を有するテキストブロックを区分けリストの開始点に置く。その後、前記各テキストブロックを左側座標に基づいて分析して、区分けリスト内の位置を決定する。たとえば、（１、１）という座標を有するテキストブロックはリストの開始点に置かれ、一方、（３、５）という座標を有するテキストブロックは区分けリストの中間または終点に置かれる。従って、各テキストブロックはその水平方向位置に基づいて区分けされる。
【００４６】
ステップＳ６３１において、区分けリストの第１のテキストブロックが検索され、第１グループ（行）内に置かれる。ステップＳ６３２で第１のテキストブロックの座標を使用して、第１グループの水平方向範囲が第１ブロックとして初期設定され、残りのテキストブロック間の比較処理の開始に使用される。ステップＳ６３４において表内に他のテキストブロックがあるか否かが判別され、もしあるならば、ステップＳ６３５において次のテキストブロックの座標が検索され、該次のテキストブロックが直前のテキストブロックと同一のグループであるか否かを判別するために、現在形成されているグループの水平方向範囲と比較される。この比較を実行するために、現在のグループと次のテキストブロックとの最大水平方向重複率を調べる。
【００４７】
最大水平方向重複が所定の閾値"t_h"よりも大きい場合は、ステップＳ６３６において分析された前記次のテキストブロックの右側座標に基づいて右側水平方向範囲すなわち右側座標がリセットされる。すなわち、前記分析された次のテキストブロックの右側座標を使用して、当該グループの新たな水平方向範囲を決定することができる。他方、ステップＳ６３６において最大水平方向重複が所定の閾値"t"よりも大きくない場合は、フローはステップＳ６３２に戻り、前記次のテキストブロックは新たなグループを開始し、新たなグループ及び新たなグループ水平方向範囲がステップＳ６３２において初期設定される。
【００４８】
ステップＳ６３４に戻って、表内にテキストブロックが残っていない場合は、フローはステップＳ６４０に進み、テキストブロックのグループが水平方向に配列される。ステップＳ６４１において、重なり合うグループが存在すれば、それらは結合される。具体的には、隣り合うグループが予め規定された閾値"x-h"だけ水平方向に重複する場合は、これらのグループは１つのグループに結合される。ステップＳ６４２では、テキストブロック割り当てに基づいてグループ間に、及び必要に応じていくつかのグループ内に行区切り線が引かれる。具体的には、ステップＳ６４２において、ギャップの幅及び長さを調べる。すなわち、ギャップの幅が予め規定された基準"w"に合致し且つギャップの長さが予め規定された基準"l"に合致する場合、行区切り線をグループ内に挿入することができると判別される。他方、ギャップが幅及び長さの基準の一方または双方に合致しなければ、グループ内部に行区切り線は挿入されない。ステップＳ６４５において、行区切り線に基づいて行アドレスがテキストブロックに割り当てられる。この点に関して、行区切り線はデフォルトでグループ間に置かれ、また、行計算（ステップＳ６０９）の結果２つ以上の行に亘ると判別されたグループの内部に行区切り線を置くこともできる。
【００４９】
図６に戻って、ステップＳ６１０において、ステップＳ６０９で全ての可能な行が計算されると、全てのテキストブロックは垂直方向位置情報に従って列グループに区分けされる。列分析は、ステップＳ６０６〜Ｓ６０９で実行された行分析と同様に実行される。具体的にはステップＳ６１０において、全てのテキストブロックは垂直方向位置情報に従ってグループに区分けされる。再びテキストブロックは各テキストブロックがその右側あるいは左側に近接した同一グループ内の別のテキストブロックと垂直方向に重なり合う複数の異なるグループに置かれる。前述したように、テキストブロックと現在形成されたグループとの最大垂直方向重複率を所定の閾値"t_v"と比較する。
【００５０】
最大垂直方向重複＝最大（垂直方向重複領域／現在形成されたグループの幅、垂直方向重複領域／選択されたテキストブロックの幅）
ステップＳ６１１において、テキストブロックのグループは各グループの垂直方向範囲に基づいて区分けされる。列区切り線は各グループ毎に計算され、再び各グループ内のテキストブロックが１つの列領域に属すると仮定され、その中の各テキストブロックはステップＳ６１２で列アドレスが割り当てられる。再び１つの列区切り線と重なり合う複数のテキストブロックに列アドレス範囲が割り当てられる。
【００５１】
垂直方向位置によるテキストブロック区分けの仕方（ステップＳ６１０）及びテキストブロックのグループの区分けの仕方（ステップＳ６１１）、及び新たなアドレスの計算及び割り当ての仕方（ステップＳ６１２）については、図９に関連して下記に詳細に説明する。
【００５２】
図９はステップＳ６１０〜Ｓ６１２に規定された処理を詳細に説明するフローチャートである。
【００５３】
図９を参照すると、行分析の後テキストブロック座標は列分析用に使用される。具体的には、ステップＳ６５０において、どのブロックが表の頂部に最も近いかを判別するために頂部座標を調べることによって、列分析が開始される。表の頂部に位置するテキストブロックは、区分けリストの開始点に置かれる。その後、各テキストブロックをその頂部座標に基づいて分析し、その区分けリスト内の位置を求める。たとえば、（１、１）という座標を有するテキストブロックはリストの開始点に置かれ、一方、（３、５）という座標を有するテキストブロックは区分けリストの中間または終点に置かれる。従って、各テキストブロックはその垂直方向位置に基づいて区分けされる。
【００５４】
ステップＳ６５１において、区分けされたリスト中の第１のテキストブロックが検索され、第１グループ（列）内にあると判別される。ステップＳ６５２で、第１テキストブロックの座標を使用して第１グループの垂直方向範囲が第１ブロックとして初期設定され、表内の残りのテキストブロックの間の比較処理の開始に使用される。ステップＳ６５４において、表内に他のテキストブロックがあるか否かが判別され、もしあるならば、ステップＳ６５５で次のテキストブロックの座標が検索され、該次のテキストブロックが最後のテキストブロックと同一グループ内にあるか否かを判別するために、現在形成されたグループの垂直方向範囲と比較される。この比較を実行するために、現在形成されたグループと該次のテキストブロックとの間の最大垂直方向重複を調べる。
【００５５】
最大重複が所定の閾値"t-v" よりも大きい場合は、ステップＳ６５６において分析される前記次のテキストブロックに基づいて垂直方向範囲すなわち底部座標をリセットするようにしてもよい。すなわち、前記分析された次のテキストブロックの底部座標を使用して、グループの新たな垂直方向範囲を決定することができる。他方、ステップＳ６５６において最大重複が所定の閾値"t-v" よりも大きくない場合は、フローはステップＳ６５２に戻り、前記次のテキストブロックは新たなグループを開始し、新たなグループの垂直方向範囲はステップＳ６５２において新たなテキストブロックとして初期設定される。
【００５６】
ステップＳ６５４に戻って、表内にテキストブロックが残っていない場合は、フローはステップＳ６６０に進み、テキストブロックのグループが垂直方向に配列される。ステップＳ６６１において、重なり合ったグループが存在すれば、それらは結合される。具体的には、隣り合うグループが予め規定された閾値"x-v"だけ垂直方向に重なり合う場合は、これらのグループは１つのグループに結合される。ステップＳ６６２では、割り当てられたテキストブロックに基づいて、グループ間に、及び、必要に応じて、いくつかのグループ内に列区切り線が引かれる。ステップＳ６６５において、各グループの列計算が実行されると、グループ間の列区切り線の数に従って列アドレス割り当てが行われる。
【００５７】
行及び列分析により、各テキストブロックには行及び列のアドレス座標が割り当てられたことになる。たとえば、図１３の表８００において、ブロック８０１には列／行アドレス（１、１）が割り当てられ、ブロック８０２には列アドレス、行アドレス、アドレス範囲（１、２−４）が割り当てられ、ブロック８０３には（２、１）が割り当てられ、ブロック８０４には列／行アドレス（２、２）が割り当てられ、ブロック８０５には列／行アドレス（２、３）が割り当てられ、ブロック８０６には列／行アドレス（２、４）が割り当てられる。更に、広いテキストブロック８０８には列及び行双方のアドレス範囲（４−７、２−４）が割り当てられる。
【００５８】
テキストブロックの行及びアドレス座標が割り当てられると、ステップＳ６１５において、本発明のブロック選択処理を実行して、複数ギャップにまたがり且つ行アドレス範囲または列アドレス範囲のいずれかを有するテキストブロックの位置を求める。これらのテキストブロックは、行または列の区切り線をテキストブロックの範囲アドレス内に挿入することができるか否かを判別するために行及び列の区切り処理を使用して、細分することができるか否かを決定するために再び分析される。具体的には、ステップＳ６１７において、図１５に示すように行区切り線の回りに大きな水平方向ギャップがあるか否か、または、図１６に示すように行区切り線の回りに不完全な垂直方向格子線があるか否かを判別する。同一処理を列区切り線についても実行する。
【００５９】
このように、ステップＳ６１７において、アドレス範囲を有するテキストブロックに区切り線を挿入することができるか否かを決定する。列または行の区切り線を適用することができる場合は、ステップＳ６１８においてテキストブロックは更に小さいテキストブロックに分割される。すなわち、テキストブロック自体が少なくとも２つの行または列に分割される。行区切り線または列区切り線が適用された後、各新たなテキストブロックにアドレスが割り当てられる。図１１に示す例において、グループ７００のテキストブロック７０１はグループ内の狭いギャップにまたがる。行または列区切り線法を使用して、行区切り線７１０をその中に置くことができるか否かを判別するために、ギャップの幅と長さを分析する。ギャップの幅が予め規定された基準に合致しないため行区切り線７１０をその中に置くことができない場合は、テキストブロックは行区切り線によって細分することができない。図１１において、行区切り線７１１及び７１２は、グループ７００を別のグループから区切る行を示す。これらの区切り線を行の境界として使用して、グループ７００の各テキストブロックへの行アドレス割り当てが行われる。
【００６０】
図１２に示す別の例では、テキストブロックのグループ７１６の２つの垂直方向線７２０の間にギャップが存在する。この状況では、ギャップを分析した後、このギャップの幅と長さが予め規定された基準と等しいかあるいは大きいと判別される。従って、（Ｙ−Ｙ＋１）（但し、Ｙ−１は前のグループの最後の行の番号である）という行アドレス範囲を有する各テキストブロックは、各ブロック内に行区切り線の回りに広いギャップが存在するので、２つの更に小さなテキストブロックに区切ることができる。すなわち、破線で示される行区切り線７２２は各テキストブロックを更に小さなテキストブロックに区切るために挿入される。その後、この細分に基づいて各テキストブロックに新たな行アドレスが割り当てられる。
【００６１】
図１３において、テキストブロック８０８は行及び範囲アドレスの双方を有し、２つ以上の表セルを含む。従って、このタイプのテキストブロックは、行及び列処理を使用して更に細分するための良い候補である。このように、行及び列処理を適用した後、図１４に示すように、テキストブロック８０８は１２の新たなテキストブロックに細分される。各新たなテキストブロックは、新たに分割された表８００の行及び列に基づいてアドレスが割り当てられる。
【００６２】
ステップＳ６１８において、行アドレス範囲を有するテキストブロックがｎ個の行区切り線を有する場合、このテキストブロックは実際には多くても（ｎ＋１）個の項目を含むと判別される。たとえば、図１５及び図１６に示すように、テキストブロックが２つ以上の行区切り線を有する場合、該行区切り線は、テキストブロックを異なる複数の行に切り離すために使用され、更に小さなテキストブロックが形成される。図１５に示す例では、広いギャップが存在する。この例では、このギャップは幅基準と合致し、その結果、３つの行を形成するために行区切り線９０１及び９０２が挿入される。従って、テキストブロック９０３は、図１５に例示された行区切り線に基づいて３つのテキストブロックに分割される。各新たなテキストブロックの行アドレスは、行ｎ、行ｎ＋１及び行ｎ＋２とアドレス指定される。
【００６３】
同様に、図１６に示す例では、テキストブロック９１３は、行区切り線９１２の近傍に存在する不完全な線９１１を有する。この場合、テキストブロック９１３は、行区切り線９１２を使用して２つのテキストブロックに分割される。各新たなテキストブロックは、行ｎ及び行ｎ＋１という行アドレスが割り当てられる。
【００６４】
範囲を有する全てのテキストブロックが更に小さなテキストブロックに分割されると、ステップＳ６１９において、同一の行及び列アドレスを有するテキストブロックは１つのテキストブロックに結合される。これは、前述したように、グループが結合されたとき、またはギャップが予め規定された基準に合致しないときに起こる。
【００６５】
ステップＳ６２０において、表の行及び列アドレス座標は、階層木構造を更新するためにメモリ内に記憶される。表８００の階層木構造を更新する前では、図１７に示すように階層木構造１１００は、頁ノード、該頁ノードから分岐する表ノード、及び該表ノードから分岐する１５テキストブロックノードを有する。表８００が本発明の処理を施されると、テキストの各表セルは行及び列に細分され、記憶されたアドレス座標を使用して、文書頁の階層木構造を図１８に示すように更新することができる。
【００６６】
図１８は、本発明のブロック選択処理を図１３に示した表８００に適用した後の階層木構造を示す。階層木構造１１００は、図１４に示した表８００の階層を示す。頁内に位置する他のタイプのイメージデータも同様に示されるが、これらのノードは簡潔及び明瞭のために図示していない。このように、階層木構造１１００は表ノード１１０３を示す。表ノード１１０３からテキストブロック１〜２６が分岐するが、テキストブロック１、テキストブロック５、テキストブロック１０、テキストブロック１５、テキストブロック２０、テキストブロック２５及びテキストブロック２６のみを示してある。
【００６７】
上述のように、テキストブロック１５はテキストブロックの個別セルを複数個有していたが、それらは、行／列区切り処理を施されたときに更に小さなテキストブロックに細分されたものである。テキストブロックを処理した結果として、個別アドレス座標を割り当てられる更に小さなテキストブロックが生じる。この結果は、階層木構造１１００の表ノード１１０３から分岐する２６個のテキストブロックとして、図１８に示される。
【００６８】
以上の説明から容易に理解できるように、本発明を使用して表を処理した結果として、文書頁の表イメージデータを後処理するために使用される表の論理的に規定された階層木構造が得られる。たとえば、階層木構造１１００に記憶されたテキストブロックの行及び列情報を使用して、特定の行及び列アドレス座標に基づいてテキストデータを適切に抽出することができる。特定のアドレス座標が１つの行及び列アドレスを有するテキストブロックに関する場合は、該テキストブロックの内部イメージが抽出される。しかし、テキストブロックの特定のアドレスが行アドレス範囲または列アドレス範囲を有する場合は、該テキストブロック内のテキストのセルが全て抽出される。図１３に示すように、テキストブロック８０４または８０５と同様であるテキストブロック８０３が要求された場合は、該テキストブロックの項目全体が抽出される。しかし、セル８０８が更に分割できない場合は、ブロック８０８内のテキストの全てのセルが抽出される。他方、図１４の場合、ステップＳ６１８を実行した結果、テキストブロック８０８は更に小さな１２のテキストブロックに細分され、各々が順に、（４、２）−（４、４）、（５、２）−（５、４）、（６、２）−（６、４）、及び（７、２）−（７、４）とアドレス指定される。この点に関しては、テキストブロック８０２はテキストデータ間にギャップを含んでいないため、行または列区切り線をブロック内のテキストデータ間に挿入することはできないので、ブロック８０２は変化しない。
【００６９】
以上、本発明を特定の態様に関して説明したが、本発明は上記記載に限定されることはなく、表イメージデータのみならず全てのタイプのイメージデータに適用されることができるものと理解されるべきものである。更に、発明の精神及び範囲から逸脱することなく、当業者によって種々の変更や修正が可能である。
【００７０】
【発明の効果】
以上に説明したように、本発明によれば、表イメージデータ及びその中のテキストデータの後処理が不十分にならないように、表内のイメージデータを適切に抽出することができる。
【図面の簡単な説明】
【図１】文書頁の代表的な図である。
【図２】図１で示した文書頁に対するブロック選択処理の結果得られた階層木構造の代表的な図である。
【図３】図２で示した階層木構造に基づいて生成される文書頁が、どのようにディスプレイ画面に表示されるかを示す図である。
【図４】本発明の装置の外観を示す斜視図である。
【図５】図１の装置のブロック図である。
【図６】本発明のブロック選択技術を使用して表分析及び操作を実行するための方法を示すフローチャートである。
【図７】本発明のブロック選択技術を使用して表分析及び操作を実行するための方法を示すフローチャートである。
【図８】ステップＳ６０６〜Ｓ６０９で簡単に説明した処理の詳細を示すフローチャートである。
【図９】ステップＳ６１０〜Ｓ６１２で簡単に説明した処理の詳細を示すフローチャートである。
【図１０】基本的な表構造の例を表す図である。
【図１１】表内に２つのフォーム行に分割し得るテキストブロックのグループを示す概念図である。
【図１２】表内に２つのフォーム行に分割し得るテキストブロックのグループを示す概念図である。
【図１３】本発明の行及び列分析処理を施す前の表の概念図である。
【図１４】行及び列分析処理を施した後の同表の概念図である。
【図１５】行アドレス範囲を有し、別個の行に細分し得るテキストブロックのグループを示す概念図である。
【図１６】行アドレス範囲を有し、別個の行に細分し得るテキストブロックのグループを示す概念図である。
【図１７】図１３に示した表に対するブロック選択処理の結果得られた階層木構造の概念図である。
【図１８】図１４の表に行及び列分析を行って更新された後の同階層木構造の概念図である。
【符号の説明】
４１０  コンピュータ機器
４１１  固定ディスクドライブ
４１２  カラーディスプレイモニタ
４１３  キーボード
４１４  ポインティング・デバイス
４１６  スキャナ
５２０  中央演算処理装置（ＣＰＵ）
５３０  主メモリ
６００，８００  表
６０１  表セル
７００  グループ
１１００  階層木構造
１１０３  表ノード
【図１】
0003847856.tif 000002
【図２】
0003847856.tif 000003
【図３】
0003847856.tif 000004
【図４】
0003847856.tif 000005
【図５】
0003847856.tif 000006
【図６】
0003847856.tif 000007
【図７】
0003847856.tif 000008
【図８】
0003847856.tif 000009
【図９】
0003847856.tif 000010
【図１０】
0003847856.tif 000011
【図１１】
0003847856.tif 000012
【図１２】
0003847856.tif 000013
【図１３】
0003847856.tif 000014
【図１４】
0003847856.tif 000015
【図１５】
0003847856.tif 000016
【図１６】
0003847856.tif 000017
【図１７】
0003847856.tif 000018
【図１８】
0003847856.tif 000019