(57)【特許請求の範囲】
【請求項１】
入力された原稿のページ画像データを記憶する記憶装置と、当該ページ画像データを処理する処理手段とを有するコンピュータ装置において、前記処理手段が前記ページ画像データを解析するように制御するためのページ解析方法であって、
前記ページ画像データのタイプが垂直方向であるか水平方向であるか混合方向であるかについてユーザにより入力された場合、当該入力された方向を前記ページ画像データのタイプとして格納し、一方、ユーザにより前記タイプが入力されなかった場合、予め設定されている混合方向を前記ページ画像データのタイプとして前記記憶装置に格納するタイプ格納工程と、
前記タイプ格納工程で前記記憶装置に前記ページ画像データのタイプが垂直方向あるいは水平方向であると格納された場合、前記ページ画像データに存在する連結成分の中でサイズが大きい連結成分に基づいて前記ページ画像データの方向を検出し、一方、前記タイプ格納工程で前記記憶装置に前記ページ画像データのタイプが混合方向であると格納された場合、前記ページ画像データにおける各テキストブロック内の連結成分に基づいてテキストブロック毎に方向を検出する検出工程と、
前記検出工程で検出された方向に基づいてテキストラインを形成し、前記ページ画像データを解析する解析工程と、
前記解析工程で解析した結果を前記記憶装置に格納する結果格納工程と、
の各工程を、前記処理手段が実行するように制御する
ことを特徴とするページ解析方法。
【請求項２】
前記検出工程で検出される方向情報は、前記連結成分のサイズに基づいて判定される方向である
ことを特徴とする請求項１に記載のページ解析方法。
【請求項３】
前記ページ解析方法は、前記ページ画像データの解析結果を階層ツリー構造に格納する方法であって、
前記タイプ格納工程では、前記ページ画像データのタイプを前記階層ツリー構造のルートノードに格納する
ことを特徴とする請求項１に記載のページ解析方法。
【請求項４】
前記解析工程は、前記形成されたテキストラインに基づいて前記ページ画像データの傾き角度を算出する算出工程と、
前記算出工程で算出された傾き角度と所定の最大傾き角度とを比較し、前記算出された傾き角度が前記所定最大傾き角度よりも大きいか否かを判定する判定工程と、
前記判定工程で前記算出された傾き角度が前記所定最大傾き角度よりも大きいと判定された場合、画像をタイプ毎の領域に分割するブロックセレクション処理を中断するように制御し、一方、前記判定工程で前記算出された傾き角度が前記所定最大傾き角度よりも大きくないと判定された場合、前記ブロックセレクション処理を続行するように制御する制御工程と
を含むことを特徴とする請求項１に記載のページ解析方法。
【請求項５】
前記ページ解析方法は、前記ページ画像データの解析結果を階層ツリー構造に格納する方法であって、
前記解析工程は、前記ページ画像データにおいて分割された領域のうち、合成されるべき複数の領域が存在するか否か判定する判定工程と、
前記判定工程で合成されるべき複数の領域が存在すると判定した場合、該複数の領域を包含する合成領域を作成する作成工程と、
前記分割された領域に基づいて生成された階層ツリー構造を、前記合成されるべき複数の領域に対応するノードを子孫とした前記合成領域に対応するノードを付加した階層ツリー構造に変更する変更工程と
を含むことを特徴とする請求項１に記載のページ解析方法。
【請求項６】
前記合成されるべき複数の領域とは、所定タイプの領域とそのキャプションであるテキスト領域である
ことを特徴とする請求項５に記載のページ解析方法。
【請求項７】
入力された原稿のページ画像データを記憶する記憶装置と、
前記ページ画像データのタイプが垂直方向であるか水平方向であるか混合方向であるかについてユーザにより入力された場合、当該入力された方向を前記ページ画像データのタイプとして格納し、一方、ユーザにより前記タイプが入力されなかった場合、予め設定されている混合方向を前記ページ画像データのタイプとして格納するタイプ格納手段と、
前記タイプ格納手段で前記ページ画像データのタイプが垂直方向あるいは水平方向であると格納された場合、前記ページ画像データに存在する連結成分の中でサイズが大きい連結成分に基づいて前記ページ画像データの方向を検出し、一方、前記タイプ格納手段で前記ページ画像データのタイプが混合方向であると格納された場合、前記ページ画像データにおける各テキストブロック内の連結成分に基づいてテキストブロック毎に方向を検出する検出手段と、
前記検出手段で検出された方向に基づいてテキストラインを形成し、前記ページ画像データを解析する解析手段と、
前記解析手段で解析した結果を格納する結果格納手段と、
を有することを特徴とするページ解析システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ブロックセレクション処理を利用して、ページ単位で原稿を解析するページ解析システムに関するものである。特に、ブロックセレクション処理で表現される複数のパラメータ、例えば、原稿のタイプ、記憶容量、画像原稿の部分解析等のパラメータを用いることで、よりブロックセレクション処理の精度が向上するものである。
【０００２】
【従来の技術】
米国特許出願第０７／８１３，０１２号には、文字認識装置及びその方法、また、米国特許出願第０８／１７１，７２０号には、読取原稿のテキスト／非テキスト選択装置及びその方法が記載されている。
従来の米国特許出願第０７／８１３，０１２号、０８／１７１，７２０号に記載されているようなブロックセレクション処理は、原稿から得られる複数種類の画像データのタイプを区別するために、１ページ単位で自動的に画像原稿の解析を行うページ解析システムが用いられていた。
【０００３】
上述のブロックセレクション処理の処理単位は、光学的文字認識（ＯＣＲ）、データ圧縮、データ等で得られるイメージを、以下説明される処理によって複数のタイプに区別される単位が処理単位として用いられる。例えば、ＯＣＲによって認識されるテキストデータと、認識されない図形データとしてのイメージが、その処理単位である。その結果、ユーザによる操作を必要とすることなく異なるタイプの画像データが入力可能であり、また、自動的に処理が実行される。
【０００４】
以下、ブロックセレクション処理の一手順を図１〜３を参照して説明する。
図１は１ページの原稿の代表的な例を示す図である。
原稿１０１は、２つの段落から構成されており、タイトル１０２、水平線１０４、複数のテキストデータの行からなるテキスト領域１０５〜１０７、非テキストであるグラフィックを含むハーフトーン図形領域１０８、テキストデータを含む表１１０、枠１１６、キャプション１２６を持つハーフトーン図形領域１２１、キャプション１３７を持つ図形領域１３２、１３５からなる。
【０００５】
米国特許出願第０７／８７３，０１２号、０８／１７１，７２０号に記載されるブロックセレクション処理によれば、原稿１０１を構成する各領域は、画像データのタイプ毎に分類される。そして、ページ単位の原稿に関する、ブロックセレクション処理により、図２に示すような、階層ツリー構造が生成される。
図２に示すように、階層ツリー構造２００は、画像データを複数のブロックに分割される各ブロックが１つのノードである複数のノードから構成されている。各ノードは、ブロックセレクション処理によって得られる各ブロックの特徴を示す特徴データが付加されている。例えば、特徴データとしては、ブロック位置データ、サイズデータ、属性データ（例えば、テキスト、絵、表等の図形タイプ）、副属性データ、子ノードあるいは親ノードポインタがある。
【０００６】
また、子ノードあるいは子孫ノードが、階層が上のブロックの下に存在する。子ノードは、階層ツリー構造の親ノードから分岐するノードとして示される。例えば、図２において、子ノードは、親ノードあるいはルートノード２１１から分岐するノード２１１と同レベルのノードが子ノードとなる。また、テキストブロックとなるノードには、その処理方向と処理順序（図に「ＲＯ＝」が示す番号）を示す特徴データが付加される。
【０００７】
例えば、階層ツリー構造２００に示されるような階層ツリー構造が生成されたとすると、それはメモリに格納される。また、原稿より画像データを要求する処理において、メモリより階層ツリー構造が検索されブロック化された画像データに対応するノードの特徴データが生成される。
また、原稿１０１に対する画像データを処理し、更に原稿１０１の簡単な構成を生成し、その結果を表示するために階層ツリー構造が用いられる。例えば、図３に示されるようなディスプレイ３００に、簡単な構成であるブロックテンプレート３０１が表示される。また、ブロックテンプレート３０１は、図２の階層ツリー構造で示される特徴データに基づいて生成され表示される。
【０００８】
１ページの原稿に対応するブロックテンプレートは、階層ツリー構造ばかりでなく、階層ツリー構造の各ノードの特徴データに直接反映する。各ノードの特徴データは、ブロックの外枠、位置、サイズを生成することで利用される。また、各ノードの特徴データは、ブロックに含まれる画像データのタイプ、可能な割当、処理順、処理方向を認識するために用いられる。
【０００９】
例えば、図３に示されるブロックテンプレート３０１において、テキストブロック３０２〜３０５、３０９は、それぞれ図２のノード２０２〜２０５、２０９に対応している。また、それぞれのテキストブロックには、各テキストブロックの処理順、処理方向である特徴データを含んでいる。
尚、図のＴ１〜Ｔ１４はそれぞれがテキスト１〜テキスト１４を示しており、また、ＰＩＣＴ．１〜ＰＩＣＴ．４は図形１〜図形４を示している。
【００１０】
【発明が解決しようとする課題】
しかしながら、上述のブロックセレクション処理は、以下に説明される不意の処理に遭遇すると以下のような問題点が発生していた。
例えば、精度の悪いＯＣＲによって得られるテキストデータおけるブロックセレクション処理は、エラーを含む処理結果が生じてしまっていた。また、線の結合（９０度に交差する線、また枠でない線の結合）処理において、その線の抽出に際し、ＯＣＲの精度が悪いと正確な位置関係の線を抽出することができないために、エラーを含む処理結果が生じてしまうという問題点があった。更に、歪んだ原稿あるいは外部装置から入力される歪んで画像データのように、ブロックセレクション処理でエラーを生じる原稿あるいは画像データを事前に解析し、そのエラーを抑止するようなアプリケーションは存在しなかった。
【００１１】
本発明は上記の問題点に鑑みてなされたものであり、ブロックセレクション処理の処理対象である原稿のデータ量と歪みを監視し、監視の結果に基づいて処理の実行の有無を指示することで、精度の良いブロックセレクション処理を実行できるページ解析システムを提供することを目的としている。
【００１４】
【課題を解決するための手段】
上記の目的を達成するための本発明によるページ解析方法は以下の構成を備える。即ち、
入力された原稿のページ画像データを記憶する記憶装置と、当該ページ画像データを処理する処理手段とを有するコンピュータ装置において、前記処理手段が前記ページ画像データを解析するように制御するためのページ解析方法であって、
前記ページ画像データのタイプが垂直方向であるか水平方向であるか混合方向であるかについてユーザにより入力された場合、当該入力された方向を前記ページ画像データのタイプとして格納し、一方、ユーザにより前記タイプが入力されなかった場合、予め設定されている混合方向を前記ページ画像データのタイプとして前記記憶装置に格納するタイプ格納工程と、
前記タイプ格納工程で前記記憶装置に前記ページ画像データのタイプが垂直方向あるいは水平方向であると格納された場合、前記ページ画像データに存在する連結成分の中でサイズが大きい連結成分に基づいて前記ページ画像データの方向を検出し、一方、前記タイプ格納工程で前記記憶装置に前記ページ画像データのタイプが混合方向であると格納された場合、前記ページ画像データにおける各テキストブロック内の連結成分に基づいてテキストブロック毎に方向を検出する検出工程と、
前記検出工程で検出された方向に基づいてテキストラインを形成し、前記ページ画像データを解析する解析工程と、
前記解析工程で解析した結果を前記記憶装置に格納する結果格納工程と、
の各工程を、前記処理手段が実行するように制御する。
【００１９】
上記の目的を達成するための本発明によるページ解析システムは以下の構成を備える。即ち、
入力された原稿のページ画像データを記憶する記憶装置と、
前記ページ画像データのタイプが垂直方向であるか水平方向であるか混合方向であるかについてユーザにより入力された場合、当該入力された方向を前記ページ画像データのタイプとして格納し、一方、ユーザにより前記タイプが入力されなかった場合、予め設定されている混合方向を前記ページ画像データのタイプとして格納するタイプ格納手段と、
前記タイプ格納手段で前記ページ画像データのタイプが垂直方向あるいは水平方向であると格納された場合、前記ページ画像データに存在する連結成分の中でサイズが大きい連結成分に基づいて前記ページ画像データの方向を検出し、一方、前記タイプ格納手段で前記ページ画像データのタイプが混合方向であると格納された場合、前記ページ画像データにおける各テキストブロック内の連結成分に基づいてテキストブロック毎に方向を検出する検出手段と、
前記検出手段で検出された方向に基づいてテキストラインを形成し、前記ページ画像データを解析する解析手段と、
前記解析手段で解析した結果を格納する結果格納手段と、
を有する。
【００２４】
【発明の実施の形態】
以下、実施の形態の概要を説明する。
本実施の形態に従うページ解析システムは、複数ページの原稿の画像データを解析する。上述のシステムは、複数ページの原稿の１ページ分の画像データを第１の記憶領域に読み込み格納する。そして、第１の記憶領域に格納された原稿１ページ分の画像データに対してブロックセレクション処理が実行される。
【００２５】
また、第１の記憶領域に格納された１ページ分の画像データに対して実行されたブロックセレクション処理の処理結果が、第２の記憶領域に読み込まれ格納される。そして、第１の記憶領域（ブロックセレクション処理の処理対象となる１ページ分の画像データを読み込み格納する領域）と、第２の記憶領域（第１の記憶領域に記憶される画像データに対して実行されたブロックセレクション処理によって得られる複数の処理結果を読み込み格納する領域）に対し、以下に説明される場合に、各記憶領域の記憶容量不足を示すエラーコードを出力する。
【００２６】
第１の記憶領域で生じる記憶容量不足は、複数ページの原稿の１ページ分を越える画像データが読み込まれた場合に、第１の記憶領域の記憶容量不足を示す第１エラーコードが出力される。また、第２の記憶領域で生じる記憶容量不足は、第２の記憶領域に読み込み格納可能なブロックセレクション処理の有効な処理結果を記憶する記憶領域が存在しない場合、第２の記憶領域の記憶容量不足を示す第２エラーコードが出力される。
【００２７】
また、他の実施の形態によれば、ページ解析システムは、原稿１ページ分の画像データを解析し、少なくとも、その原稿ページの一部分の領域が解析対象として選択される。原稿ページは、画像データとして処理され表示される。その際、座標指定装置によって、少なくとも解析対象である原稿の一部分の領域に座標が指定される。そして、選択された原稿ページの一部分の領域を含む原稿ページの画像データが抽出され、少なくともその抽出された領域の画像データを解析するために、ブロックセレクション処理が実行される。
【００２８】
また、他の実施の形態によれば、ページ解析システムは、原稿１ページ分の画像データに対し、少なくとも１つの方向を解析する。原稿１ページ分の画像データが入力されると、その画像データの方向情報が獲得される。そして、その方向情報が獲得されたか否かを判定する。判定の結果、方向情報が獲得された場合、その獲得された方向情報によって方向が選択され、その選択された方向に従って画像データが解析される。一方、方向情報が獲得されない場合、予め設定されている所定方向に従って画像データが解析される。
【００２９】
また、他の実施の形態によれば、ページ解析システムは解析対象として原稿１ページ分の画像データを入力し、その原稿ページの傾き角度の算出を含むブロックセレクション処理の実行を開始する。そして、算出された傾き角度と予め設定されている所定の傾き角度を比較し、算出された傾き角度が所定の傾き角度よりも大きいか否かを判定する。算出された傾き角度が所定の傾き角度よりも小さい場合、ブロックセレクション処理が完了する。一方、算出された傾き角度が所定の傾き角度よりも大きい場合、ブロックセレクション処理は中断される。
【００３０】
また、他の実施の形態によれば、ページ解析システムは、複数ページの原稿の１ページ分の画像データを入力し、その画像データを同じタイプの画像データのブロックに分割し、各ブロックの認識を行う。そして、同じタイプの画像データのブロックを持つ複数のブロックの少なくとも１つのブロックに対して、そのブロックの認識を行う。
【００３１】
尚、本実施の形態によれば、同じタイプの画像データのブロックは合成ブロックとして結合される。例えば、合成ブロックとしては、キャプションを含む図形等が合成ブロックとなる。また、合成ブロックは、階層ツリー構造において、同じタイプの画像データのブロックとして構成されるノードを下方に持つルートノードとして構成される。
【００３２】
また、他の実施の形態によれば、ページ解析システムは、複数ページの原稿の１ページ分の画像データを入力し、その画像データを同じタイプの画像データのブロックに分割し、各ブロックの認識を行う。そして、図形情報を含む画像データのブロックの認識を行う。
尚、本発明によれば、図形情報を持つ画像データのブロックとしては、ハーフトーン図形、線画、折れ線、それ以外のタイプの図形がそのブロックの図形情報となる。そして、その図形と認識されたブロックは、そのブロックに対応する階層ツリー構造のノードに図形情報が付加された形で、そのノードが構成される。
【００３３】
尚、これらの本発明の特徴及び有利な点は、以下の添付の図面に従う好適な実施の形態の詳細な説明を参照することにより、更に容易に理解されるであろう。
図４は本発明を適用する実施の形態の外観図である。
以下に図４の構成を説明する。４１０はコンピュータ装置であり、MacIntosh、IBM PCまたはMicroSoft社製Windowsのようなウィンドウズ環境を備えたＰＣ互換コンピュータからなる。コンピュータ装置４１０には、カラーモニター等のディスプレイ４１２、ユーザコマンド等を入力するためのキーボード４１３、そして、ディスプレイ４１２上に表示される事象を指示し操作するためのマウス等のポインティングデバイス４１４が接続されている。
【００３４】
コンピュータ装置４１０は、大容量記憶装置として、イメージファイルを含むデータファイルを記憶するためのディスク４１１を備えている。ディスク４１１は、圧縮、あるいは無圧縮のイメージファイルや、本実施の形態で説明されるブロックセレクション処理を実行するためのためのアプリケーションプログラムを含む情報処理プログラムを記憶している。また、ディスク４１１には、１ページ分の画像原稿のそれぞれがブロックセレクション処理によって表現される階層ツリー構造の各データも記憶している。
【００３５】
複数ページの画像原稿は、スキャナ４１６によってスキャンされる。スキャナ４１６によって、スキャンされた各ページを構成する文書あるいはイメージは、ビットマップ画像データとしてコンピュータ装置４１０へ展開される。また、画像データは、ネットワークインターフェース４２４またはファクシミリ／モデムインターフェース４２６を介して、他の外部装置からコンピュータ装置４１０へ入力してもよい。
【００３６】
プリンタ４１８は、コンピュータ装置４１０によって処理された画像原稿の出力のために備えられている。
尚、図４では、プログラム可能な汎用コンピュータ装置としてその外観を示したが、専用、あるいは独立したコンピュータ装置、または他のタイプのデータ処理装置であっても本発明の実施の形態に適用できることは言うまでもない。
【００３７】
図５は実施の形態のコンピュータ装置４１０の詳細な内部構造を示すブロック図である。
以下に図５の構成を説明する。図中、コンピュータ装置４１０は、コンピュータバス４２１によって、中央処理ユニット（ＣＰＵ）５２０を含む各ユニットが相互に接続さている。コンピュータバス４２１に接続される各ユニットは、スキャナインタフェース５２２、プリンタインタフェース５２３、ネットワークインタフェース５２４、ファックス／モデムインタフェース５２６、ディスプレイインターフェース２７、キーボードインタフェース５２８、マウスインタフェース５２９、メインメモリ５３０、そしてディスク４１１からなっている。
【００３８】
メインメモリ５３０は、コンピュータバス５２１に接続され、ＲＡＭを備えている。ＲＡＭは、ＣＰＵ５２０で実行される各種処理（例えば、ブロックセレクション処理）を実行するための作業領域である。また、メインメモリ５３０では、ＣＰＵ５２０によってディスク４１１に記憶された各種処理を実行するためのプログラムが読み込まれ、読み込まれた各種プログラムによって各種処理が実行される。
【００３９】
ユーザの操作によって、画像データを処理するためのアプリケーションプログラムが読み込まれ、その処理が実行される。例えば、ウインドウズ版WordPerfectのようなデスクトップ処理プログラムが操作することで画像データが処理され、また、ブロックセレクション処理前後の画像原稿の処理状況を表示する。同様にして、ページ解析プログラムが、ブロックセレクション処理を実行することで処理対象の１ページ分の画像原稿に複数種類の画像データの属性を入力する。そして、その１ページ分の画像原稿の処理結果がウインドウ環境を介してディスプレイに表示される。
【００４０】
図６Ａ〜６Ｄは本実施の形態のブロックセレクション処理によるページ解析の方法を示すフローチャートである。
尚、図６Ａ〜６Ｄで説明される各処理のステップは、ディスク４１１によって読み込まれるコンピュータプログラムに従って、ＣＰＵ５２０によって実行される。
【００４１】
ステップＳ６０１では、画素画像データがシステムへ入力されディスク４１１へ格納される。画像データは画像を画素単位で表現している。好ましくは、画素データは２値画素データ、つまり白黒画像データである。しかし、画像データは、各画素が複数のグレイスケールレベル内の１つで表現される中間調画像データであっても良いし、各画素が、その色を符号化するマルチビットワードで表現されるカラー画像データであっても良い。それらの場合、または画素データが２値画素データでない他のいずれの場合でもディスク４１１へ格納する前に、非２値画素データを２値画素データへ変換するための閾値処理が行われる。
【００４２】
ステップＳ６０２で、ブロックセレクション処理プログラムが、そのプログラムと変数によって生成される複数の内部変数がセットされることによって初期化される。ステップＳ６０３で、ユーザによって、ブロックセレクション処理によって解析される１ページ分の原稿が入力されたか否かが確認される。ブロックセレクション処理による解析が原稿ページの一部分の領域だけしかない場合、ステップＳ６０４で、その解析する領域の調整を行う。
【００４３】
ここで、ステップＳ６０４において、解析される原稿ページの少なくとも一部分の領域の選択方法の概略について、図７Ａ、図７Ｂを用いて説明する。
図７Ａは本実施の形態の原稿１ページの一部分の領域の解析処理の詳細な処理フローを示すフローチャートである。
ステップＳ７０１で、原稿１ページ分の画像データを入力する。例えば、図７Ｂに示されるような原稿ページ７５０を入力すると、入力される原稿ページ７５０の画像データが読み取られディスク４１１に格納される。ステップＳ７０２で、入力された原稿ページの画像データがディスク４１１から検索され、その検索結果がユーザへと表示される。
【００４４】
ステップＳ７０３で、入力された画像データの一部分の領域を解析するのｘｙ座標の入力がユーザによって要求される。例えば、原稿ページ７５０のテキスト領域７５１を解析するために、ユーザは座標（ｘ1，ｙ1）、（ｘ2，ｙ2）、（ｘ3，ｙ3）、（ｘ4，ｙ4）を入力する。
ステップＳ７０５で、ユーザによるｘｙ座標の入力後、ページ解析プログラムは、ステップＳ７０３で入力した座標が原稿ページの境界線内に含まれているか否かを判定する。例えば、図７Ｂに示すような原稿ページ７５０に対し、その原稿ページ７５０の境界線内に入力された座標が含むか否かがステップＳ７０５において判定される。原稿ページの境界線内に入力された座標が含まない場合は、ステップＳ７０３に戻る。そして、原稿ページの境界線内に含む座標が得られるまでユーザは座標の入力を繰り返す、あるいはユーザが解析対象にすべての原稿ページが入力されたことを指示するまで座標の入力を繰り返す。一方、原稿ページの境界線内に入力した座標が含む場合は、ステップＳ７０６に進む。
【００４５】
ステップＳ７０６で、入力した座標によって定義される原稿ページの一部分の領域の画像データの抽出を行う。抽出された画像データは、ステップＳ７１０のブロックセレクション処理における処理対象となる。
ここで、再びステップＳ６０５に戻る。
１ページ分の原稿の入力処理が終了するか、あるいはステップＳ６０４で原稿ページの一部分の領域の選択されると、ステップＳ６０５に進む。
【００４６】
ステップＳ６０５で、１ページ分の原稿あるいはステップＳ６０４選択された原稿ページの一部分の領域に対し、ブロックセレクション処理を実行するための記憶領域を確保する。また、原稿ページの解析によって得られる階層ツリー構造の結果を格納するための記憶領域を確保する。
ここで、ステップＳ６０５における記憶領域の確保する方法の概略について、図８を用いて説明する。
【００４７】
図８は本実施の形態のブロックセレクション処理のための記憶領域の確保する方法と、階層ツリー構造を算出する処理のための記憶領域の確保する方法を説明するための図である。
例えば、原稿ページ８００は共通原稿ページ記憶領域が入力されている原稿ページである。共通原稿ページ記憶領域は、ＣＰＵ５２０の制御のための作業領域であり、その制御とは、原稿ページをスキャンして得る画像データを記憶する記憶領域（図の記憶領域８０１ａ）を読み込む際の制御と、ブロックセレクション処理を実行するための作業領域（図の記憶領域８０１ｂ）を確保するための制御である。
【００４８】
尚、ＣＰＵ５２０が生成するこの記憶領域は、原稿ページの画像データを読み込むための記憶領域ばかりでなく、ブロックセレクション処理の中間処理結果を読み込むための記憶領域になっている。
記憶領域８０３は、複数ページからなる記憶領域で構成されている。図に示されるように、８０４、８０５、８０６の各ページには、原稿ページ８００のブロックセレクション処理によって得られる複数の階層ツリー構造が格納される。
【００４９】
尚、各ページの階層ツリー構造は異なるタイプの構造（あるページは単純な構造、また、あるページは複雑な構造）から構成されているため、各ツリー構造を記憶するための記憶容量は異なる。
尚、初期化の際、共通原稿ページ記憶領域８０１と階層ツリー構造記憶領域８０３は、ブロックセレクション処理プログラムに設定されている変数に基づいて、充分な所定記憶容量の記憶領域が確保される。但し、ブロックセレクション処理プログラムによって確保される共通原稿ページ記憶領域８０１と階層ツリー構造記憶領域８０３の記憶領域はの記憶容量はユーザによって変更しても良い。また、１０ページだけといった所定数のページ数に基づいて記憶領域を確保したり、所定の変数に基づいて記憶領域を確保しても良い。
【００５０】
ステップＳ６０５における記憶領域が確保されると、ステップＳ６０７で、入力された原稿ページのタイプがユーザによって判定される。例えば、ステップＳ６０１でスキャンされた原稿ページの画像データが、英語原稿ページのような横書き原稿ページ、即ち水平であるか、あるいは日本原稿ページのような縦書き原稿ページ、即ち垂直であるか等が判定される。また、原稿ページが、縦書き横書きの両方から構成される場合は、その際は複数の方向を含む混合タイプとしての処理が必要となる。いずれの場合にしても、ユーザは、所定方向、垂直方向、水平方向、あるいは複数の方向を含む混合方向の４つのいずれかの方向を判定する。
【００５１】
尚、「混合」タイプの原稿ページは予め設定されたタイプであり、混合タイプの原稿ページが選択されても、ユーザはそれに伴う特別な処理は必要とされない。
ステップＳ６０８で、ユーザは入力した原稿ページのタイプが既に設定されているタイプであるかを判定する。入力した原稿ページのタイプが既に入力された原稿ページのタイプである場合、ステップＳ６０９で、そのタイプの情報が原稿ページのルートノードに格納される。また、原稿ページのタイプは、原稿ページに対して実行される処理に渡って、変数として用いられ、また、その変数は正確な処理結果を出力するための要素となっている。例えば、スキャンした原稿ページにおいて、テキストデータがＯＣＲプログラムによって光学的に認識された場合、そのテキストデータの方向として水平方向がセットされる。
【００５２】
一方、ステップＳ６０８で、入力された原稿ページのタイプが既に設定されているタイプでない場合は、ステップＳ６１１で、その原稿ページのタイプを設定する。
尚、本発明では、上述のステップＳ６０８で設定される原稿ページのタイプを「混合」タイプの原稿ページとして扱う。
【００５３】
そして、設定された原稿ページのタイプの情報が原稿ページのルートノードに格納される。また、原稿ページのタイプは、原稿ページに対して実行される処理に渡って、変数として用いられる。
そして、原稿ページのタイプがセットされると、ステップＳ６１５からステップＳ６３５で説明されるブロックセレクション処理が実行される。
【００５４】
ブロックセレクション処理について簡単に説明する。ブロックセレクション処理は、２値画像の原稿ページにおいて、以下の異なるタイプのブロックに分割する。
（１）テキストデータとして、テキストデータを含む段落、タイトルテキストデータ、表の中のテキストデータ、キャプションとしてのテキストデータ
（２）線として、水平線、垂直線、ドットからなる線、斜線
（３）互いに直交する線分
（４）ハーフトーン画像、連続調、グレイスケール等
（５）線画
（６）例えば、箱型の枠、枠である領域として認識されるもの（例えば、図１の枠１１６）
（７）表（例えば、図１の表１１０）
（８）枠や線画の中の空白領域から独立して存在する空白領域
更に、従来のブロックセレクション処理とページ分割は、傾きのない原稿ページであることを前提に処理を行うブロックセレクション処理とページ分割であった。しかし、本発明によれば、後述するステップにおいて、原稿ページの傾きを検知し、傾きのある原稿ページ、傾きのない原稿ページのいずれにおいてもそれぞれに対応する処理を実行することで、傾きのある原稿ページに対する処理が保証されている。この保証の方法としては、原稿ページに傾きがある場合、ステップＳ６１５からステップＳ６３５で説明される処理によって分割される各ブロックが長方形であるブロックは重なって表示されてしまう。また、原稿ページに傾きがない場合は、それらの長方形であるブロックは重ならない。この事実をふまえて、原稿ページを処理する際に生じる長方形であるブロックの重なりの有無によって、原稿ページが傾いているか否かを知る。そして、原稿ページに傾きがある場合は、その原稿ページに対するブロックの抽出する際にその旨を示す情報を与えることで、傾きのある原稿ページに対する処理が保証される。
【００５５】
ステップＳ６１５からステップＳ６３５の処理の概要を説明する。
ステップＳ６１５からステップＳ６３５で説明される処理によって、階層ツリー構造は原稿ページの画像データを表現するために用いられる。また、階層ツリー構造のルートノードは原稿ページの含むすべてのテキストブロック、非テキストブロックを表現し、それらのノードはルートノードの直接の子孫あるいはその子孫の子孫としてつながったノードの状態で表現される。
【００５６】
一方、原稿ページをブロックに分割するために、原稿ページの画像データの結合成分が検索され、その結合成分によってテキスト部と非テキスト部の結合成分に区別される。そして、テキスト部と非テキスト部の結合成分はおおまかにかつ簡単にグループ化される。例えば、いくつかの段落によって構成されるテキスト部の結合成分が集められてテキストブロックが生成される。また、例えば、一つの絵として存在する結合成分が集められることによって絵ブロックが生成される。
【００５７】
ここより、ステップＳ６１５からステップＳ６３５の詳細な処理について説明する。
ステップＳ６１５で、画像データが縮小された処理が実行される。ブロックセレクション処理の処理速度を上げるために画像データの縮小は必要であるが、光学的文字認識（ＯＣＲ）に影響しないような画像データの縮小を行う。画像データの縮小方法としては、例えば、解像度が４００ｄｐｉの原稿ページを４画素毎に１画素間引いて２００ｄｐｉの解像度にする程度の間引きは、画像の結合性が保証されることが経験的に証明されている。また、他の間引き方法としては、異なる解像度を持つ画像を用いる方法である。例えば、解像度５０ｄｐｉの画像と、解像度７５ｄｐｉの画像を生成し、その２つの結果を用いることで、正確でかつ高速に画像の間引きが実現されることが経験的に知られている。
【００５８】
ステップＳ６１６で、画素画像データが解析された連結成分が検出され、その大きさ及び他の連結成分との相対的な位置び基づいて、検出された連結成分がテキストであるか非テキストであるかが区別される。連結成分は、米国特許出願第０７／８１３，０１２号、０８／１７１，７２０号に記載されているように、白画素によって完全に囲まれた黒画素のグループである。連結成分の検出は、例えば、図９Ａに示すように連結成分９０２の輪郭９０１を検索することによって、連結成分の検出が開始される。この検出は、図９Ａに示されるような所定８方向の各方向に存在する連結成分の輪郭の画素成分を検出することで行う。輪郭９０１に囲まれる連結成分９０１を構成する内側の各画素は、後述するステップＳ６１８で区別されるテキストあるいは非テキストに基づいて、その画素が飛ばされて解析される。そして、各連結成分は、各連結成分の周りに構成することができる最小の長方形を使うことによって、各連結成分を長方形化する。
【００５９】
ステップＳ６１７で、連結成分のサイズに基づいて、各連結成分はおおまかにテキスト部と非テキスト部に区別される。
尚、一般的には、非テキスト部の方がテキスト部よりも大きくなる。
ステップＳ６１７の区別で誤った区別がされてしまった場合、以下に説明されるステップで補正される。その補正方法としては、テキストと非テキストを区別するために、各連結成分のサイズと所定のサイズの閾値を比較することで、その区別を行うための判定が行われる。また、その所定のサイズの閾値は、各連結成分に基づいて得られる適応的に決定された閾値である。
【００６０】
詳細に説明すると、ステップＳ６１７のテキスト部と非テキスト部の区別は２つのステップで行われる。最初のステップで、極端に大きい連結成分は非テキスト成分として区別される。第２のステップで、区別されていない各連結成分を囲む長方形の高さと幅の平均値を算出する。算出した平均値に基づいて、適応的なサイズ（即ち、テキストを囲む長方形のサイズである垂直方向のテキストのサイズあるいは水平方向のテキストのサイズ）が算出され、その算出されたサイズが上述のテキスト／非テキストの区別のための閾値として用いられる。
【００６１】
ステップＳ６１７の処理によって得られたテキストと非テキストの連結成分それぞれは、階層ツリー構造のルートノードの直接の子孫のノードとして割り当てられる。テキスト連結成分と非テキスト連結成分の区別は、それぞれ同レベルのツリー構造のノードに対して行われる。また、その際、子孫レベルの連結成分の処理の過程で得られる統計的な値に従って、その区別は行われる。この区別は、より多くの階層ツリー構造がある場合に、より重要な処理となる。例えば、枠の外側と内側にサイズの一致しないテキストがある場合、枠の内側がの区別が枠の外側の区別からにおける処理は、異なる子孫レベルに移る処理となるため、同じ枠に対してその枠の内側の区別とその枠の外側の区別を別々に行うことになるからである。
【００６２】
ステップＳ６１８で、非テキスト連結成分は、それらが線（水平線、垂直線、ドット線あるいは斜線）、折れ線、絵、線画、枠、表あるいは未知（即ち、どれにも属さない）のいずれかに判定される。また、階層ツリー構造のルートノードの子孫のその下の子孫である表、枠、線画、絵に含まれる非テキスト連結成分は、上述のステップＳ６１７、ステップＳ６１８を繰り返すことによって区別され判定される。そのため、各連結成分とその連結成分の種類に対して階層ツリー構造が展開される。しかしながら、枠や表に含まれる連結成分の区別は、８方向の検索（図９Ａを参照）における黒画素の検索は実行されない。そのかわりに、４方向の検索による白画素の検索が実行される。その検索方向は図９Ｂに示されるような方向であり、例えば、画素枠９０４で囲まれる白輪郭９０３に関して、４方向の検索を行う。この白輪郭の４方向の検索を行うのは、囲まれ輪郭の内側にある連結成分の検索と区別を行うのに役立つからである。
【００６３】
ステップＳ６１８における非テキスト連結成分の区別、つまり、線、折れ線、枠、表、絵、線画、未知のいずれかのタイプとして区別される手順の好適な処理フローを図１０に示す。図１０に示されるような処理が、各非テキスト連結成分に対して実行される。また、非テキスト連結成分の各タイプの区別を実行する処理が、図１０に示されるようなシーケンシャルな処理で実行される。
【００６４】
例えば、図１０において、早い処理の段階で処理が実行される非テキスト連結成分は、ハーフトーン画像と認識される。このように、非テキスト連結成分毎に処理が進む。また、図１０で実行される処理の処理対象である非テキスト連結成分は、図１０の各ステップの処理の実行の有無を基準となる閾値を比較することで決定する。その基準となる閾値は、数学的に公式化された計算によって、直接各連結成分を囲む長方形のサイズと幅に基づいて算出される。
【００６５】
図１０の処理フローについて説明する。
ステップＳ１００１で、非テキスト連結成分は、ハーフトーン画像（あるいは連続画像）であるか否かが判定される。ハーフトーン画像であるか否かの判定は、その非テキスト連結成分の画像エリアに関し、白と黒画素のそれぞれの連続成分の比較と黒画素密度に基づいて行われる。その画像エリアに関し、黒画素成分が白画素成分よりも長い場合、また、黒画素密度が高い、あるいはその画像エリア内に多くのノイズのような連結成分がある場合は、その非テキスト連結成分はハーフトーン画像連結成分と判定される。そして、ステップＳ１００２に進み、その非テキスト連結成分に対応するノードに補助属性として「ハーフトーン」が格納される。
【００６６】
一方、非テキスト連結成分がハーフトーン画像連結成分と判定されない場合、ステップＳ１００３に進み、その非テキスト連結成分が枠であるか否かが判定される。枠であるか否かの判定は、非テキスト連結成分の高さがテキストサイズよりも長く、その非テキスト連結成分が、平行である水平な２本の境界線と平行である垂直な２本の境界線が、長方形を構成する境界線と一致する場合、その非テキスト連結成分は枠と判定される。また、非テキスト連結成分の黒画素密度がテキストデータ構成される段落の密度と近似あるいはそれよりも少ない場合（ステップＳ１０００１にお凍て、非常に高い黒画素密度を持つ非テキスト連結成分と判定される非テキスト連結成分）、枠と判定される。非テキスト連結成分が枠と判定された場合、ステップＳ１００４に進み、その非テキスト連結成分に対応する階層ツリー構造のノードに補助属性として「枠」を格納する。
【００６７】
ステップＳ１００３で、非テキスト連結成分が枠と判定されなかった場合、ステップＳ１００５で非テキスト連結成分が水平線であるいは垂直線であるか否かが判定される。水平線あるいは垂直線であるか否かの判定は、その非テキスト連結成分の幅と高さの割合が大きい場合や、また、階層ツリー構造の同じレベルのノードのテキスト連結成分の細さよりも非テキスト連結成分のの細さの方が細い場合、その非テキスト連結成分は水平線と垂直線と判定される。更に、非テキスト連結成分に占める黒画素成分の密度がとても高い場合に、その非テキスト連結成分は水平線あるいは垂直線と判定される。水平線あるいは垂直線と判定される非テキスト連結成分の両側は真っ直ぐになっているべきであるが、その非テキスト連結成分の片側だけが真っ直ぐで、また非テキスト連結成分の細さがテキスト連結成分の細さと近似している場合は、下線である非テキスト連結成分と判定される。この場合、下線が引かれているテキスト連結成分と下線である非テキスト連結成分は互いに分割され、それぞれステップＳ６１７とステップＳ６１８による処理を改めて実行する。このようにして、非テキスト連結成分が水平線あるいは垂直線と判定された場合は、ステップＳ１００６に進み、その非テキスト連結成分に対応する階層ツリー構造のノードに補助属性として「水平線」あるいは「垂直線」を格納する。
【００６８】
ステップＳ１００５で、非テキスト連結成分が水平線あるいは垂直線と判定されない場合は、ステップＳ１００７で非テキスト連結成分が表であるか否かが判定される。表であるか否かの判定は、非テキスト連結成分内の白輪郭を４方向による検索によって判定される。４方向の白輪郭が存在する場合、または、水平線と垂直線によって囲まれる白輪郭であるような表を構成する格子の中の白輪郭の配列である場合は、その非テキスト連結成分は表と判定される。
このようにして、非テキスト連結成分が表と判定された場合は、ステップＳ１００８に進み、その非テキスト連結成分に対応する階層ツリー構造のノードに補助属性として「表」を格納する。また、表の内部にテキスト連結成分と非テキスト連結成分が認識された場合、その区別をするためにステップＳ６１７とステップＳ６１８による処理を再び実行し、区別されたテキスト連結成分あるいは非的連結成分に対応する階層ツリー構造のノードを付加する。
【００６９】
ステップＳ１００７で、非テキスト連結成分が表と判定されなった場合、ステップＳ１００９で非テキスト連結成分が斜線であるか否かが判定される。斜線であるか否かの判定は、非テキスト連結成分の長さと細さの割合が大き場合に、斜線と判定される。但し、その非テキスト連結成分の細さは、テキストサイズの細さよりも決して細くならない。また、非テキスト連結成分に占める黒画素密度が高密度で、そのエッジが斜めに並んでいる場合に斜線と判定される。このようにして、非テキスト連結成分が水平線あるいは垂直線と判定された場合は、ステップＳ１０１０に進み、その非テキスト連結成分に対応する階層ツリー構造のノードに補助属性として「斜線」を格納する。
【００７０】
尚、斜線の傾き角度は、周知の角度検出処理によって判定される。また、斜線の傾き角度は、後述する処理に用いるための属性情報として、階層ツリー構造の対応するノードに格納される。
ステップＳ１００９で、非テキスト連結成分が斜線と判定されない場合は、ステップＳ１０１１で非テキスト連結成分が線画あるいは折れ線であるか否かが判定される。線画あるいは折れ線であるか否かの判定は、非テキスト連結成分のサイズが前の処理で設定されているサイズよりも長い場合、例えば、ステップＳ１００１で得られるハーフトーン画像のサイズよりも長い場合に、線画あるいは折れ線と判定される。また、線画はハーフトーン画像と比べて、白輪郭の連続成分が輪郭の内側における黒画素連結成分よりもかなり長い。加えて、黒画素密度が低い。このような条件を満たす場合、ステップＳ１０１２において、線画と折れ線を区別する処理が実行される。
【００７１】
図１２Ａは、折れ線と線画の違いを説明するための図である。
図１２Ａにおいて、原稿ページ１０５０は、タイトル１０５１、テキスト領域１０５２、１０５３、絵１０５５からなる。テキスト領域１０５２、１０５３は、折れ線１０５４によって、絵１０５５から互いの分割されている。
尚、一般的に折れ線は、図１２Ｃ、図１２Ｄに示す２つのグループからなる形状をもつものを折れ線と区別される。図１２Ｃに示されるような折れ線は、改めて折れ線として選択され、図１２Ｄに示されるような折れ線は、改めて枠として区別される（即ち、ステップＳ１００３では枠として完全には選択されていない）。そして、それぞれの区別は、その構成要素の長さと細さと互いに交差する角度（水平成分の鏡像、垂直成分の鏡像、対角線の鏡像でも許される）に基づいて行われる。
【００７２】
図１２Ａにおいて、折れ線１０５４は図１２Ｃに示される折れ線に相当するので、この場合、ステップＳ１０１２からステップＳ１０１４に進む。このようにして、非テキスト連結成分が折れ線と判定された場合は、ステップＳ１０１４に進み、その非テキスト連結成分に対応する階層ツリー構造のノードに補助属性として「折れ線」を格納する。
【００７３】
一方、非テキスト連結成分が図１２Ａに示される折れ線（「折れ線」の属性を付加するグループ）、あるいは図１２Ｂに示される折れ線（「枠」の属性を付加するグループ）のどちらにも相当しない場合、ステップＳ１０１２からステップＳ１０１３に進み、非テキスト連結成分は線画と判定される。このようにして、非テキスト連結成分が線画と判定された場合は、ステップＳ１０１３に進み、その非テキスト連結成分に対応する階層ツリー構造のノードに補助属性として「線画」を格納する。
【００７４】
図１２Ｂは、図１２Ａに示される様々な画像データが本発明のブロックセレクション処理による処理結果を示す図である。
図１２Ａに示されるタイトル１０５１、テキスト領域１０５２、１０５３、絵１０５５は、図１２Ｂにおいて、それぞれブロック１０６０、１０６１、１０６２、１０６３に対応する。また、図１２Ａに示される折れ線１０５４は、ブロック１０６３にブロック１０６１、１０６２が重なることで示されている。このように、それぞれのブロックの属性と調整結果は、階層ツリー構造に対応するノードに格納され、それに基づいて後述する画像データの抽出処理が実行される。
【００７５】
再び、図１０の説明に戻る。ステップＳ１０１１で、非テキスト連結成分が線画あるいは折れ線と判定されない場合は、ステップＳ１０１５で非テキスト連結成分は未知のタイプとして判定される。このようにして、非テキスト連結成分が未知のタイプと判定された場合は、ステップＳ１０１５に進み、その非テキスト連結成分に対応する階層ツリー構造のノードに補助属性として「未知」を格納する。
【００７６】
更に、図６の説明に戻る。ステップＳ６１８による非テキスト連結成分の区別処理後、ステップＳ６１９に進み、ドットラインの検出が実行される。
尚、一般的に連結成分が形成するドットラインの各ドットの検出は困難とされており、これらの連結成分は各ドットのサイズが同じであるテキスト連結成分とみなされる。
【００７７】
このようにドットラインの検出においては、水平成分あるいは垂直成分により近いサイズのドットサイズを持つテキスト連結成分が選択される。選択されたテキスト連結成分は各々の相対的な位置関係に基づいて異なるグループに区別される。区別されるそれぞれのグループは、サイズと付近のラインの囲みに基づくドットのラインが、垂直、水平、斜めの成分が正確に現れているか否かが確認される。それぞれ検出されるドットラインは、すべてのドットラインの要素に囲まれる輪郭を持つ連結成分で生成される。また、それぞれ検出されるドットラインは、階層ツリー構造の対応するノードに、水平、垂直、斜めのいずれかのドットラインとしての属性が新しいユニットとして付加されて用いられる。
【００７８】
また、ステップＳ６１９では、折れ線であるドットラインの検出を行う。特に、グループ化された連結成分が水平なドットラインと垂直なドットラインが直角あるいは直角に近いかたちで交差している場合、そのグループ化された連結成分は、折れ線であるドットラインとして区別される。そして、検出される折れ線であるドットラインは、階層ツリー構造の対応するノードに、折れ線であるドットラインとしての属性が付加される。
【００７９】
ステップＳ６２０で、非テキスト連結成分のエッジに沿って不可視線が検索される。このような不可視線は欄の間にある白線であり、この不可視線を検出することで、テキスト連結成分がグループ化されるべきかあるいは欄から区別されるブロックにすべきかを判定するの役立つ。
ステップＳ６２１で、ステップＳ６０７からステップＳ６１１の処理によって格納された原稿ページが「単一方向」をである原稿ページのタイプに対し、その原稿ページの方向を検出する（図のステップＳ６２１ａ）。原稿ページの方向の検出は、原稿ページに存在する複数の連結成分において、その各連結成分の中でサイズが大きい連結成分のサイズに基づいて行う。例えば、水平方向である原稿ページの連結成分は、高さよりより同一の幅を持つことが多い。加えて、水平線と垂直線の数の差とサイズは、原稿ページの方向を判定するための付加的な要因になっている。そして、ステップＳ６２１ａで検出される方向は階層ツリー構造のルートノードに格納される。なぜなら、単一方向である原稿ページは、グローバル変数となるからである。
【００８０】
ステップＳ６２２で、ステップＳ６１８で区別できなかった非テキスト連結成分（即ち、「未知」のタイプを持つ非テキスト連結成分）が解析される。そして、大きいフォントサイズのタイトルラインであるかどうかが判定される。テキストあるいは未知のユニットを持つグループ化された「未知」のタイプの非テキスト連結成分によって、水平または垂直方向にタイトルラインが形成される。グループ化されたタイトルの方向は、グループ化されると想定される連結成分の間の距離と可能なタイトルの長さに基づいて判定される。
【００８１】
ステップＳ６２３で、テキストブロックがテキスト連結成分から形成される。こここでのステップでは、テキストあるいは非テキストブロックが形成される前には原稿ページの傾き検出も画像回転も行われることはない。この結果、画像回転に費やされる時間が節約され、原稿ページの傾き検出によって生じる不確かさ（文字認識処理（ＯＣＲ）によって生じる不良）を避けることができる。更に、ある特殊な視覚効果を達成するために、同じ原稿ページのテキスト領域のいくつかを、特別に斜めに編集することも可能である。このため、原稿ページに傾き角度がある場合でも傾き角度のない原稿ページと同様な効果得られるので、原稿ページを直立に補正するための原稿ページの傾きの検出は役に立たない。それゆえ、ステップＳ６２１では、原稿ページの傾き角度に関わりなく直接、テキスト及び非テキストブロックが形成される。
【００８２】
特に、それぞれのテキスト連結成分に対し、そのテキスト連結成分の近傍に存在する水平あるいは垂直である別のテキスト連結成分が検索され、その検索されるテキスト連結成分がテキストブロックとして集められる。この検索によってテキストブロックを集めるか否かの決定方法は、まず、このテキスト連結成分に対応する階層ツリー構造のノードと同じレベルにおいて、近傍にあるテキスト連結成分の水平あるいは垂直方向の隙間を統計的解析によって算出する。そして、算出れた値と、所定の基準値である閾値とを比較することによって集めるか否かを決定する。それゆえ、各テキスト連結成分の接近の度合いが、原稿ページとその原稿ページ内で分割される領域に基づいて直接判定される。
【００８３】
ステップＳ６２４で、ステップＳ６２３の処理の際に集められてしまったテキストブロックに対し、そのテキストブロックに可視線または不可視線が横切っている場合、そのテキストブロックは分割される。特に、ステップＳ６２０で検出される不可視線は、原稿ページに存在する極端に狭い欄間の隙間によるものである。例えば、その隙間は図形領域の近くにテキスト欄が続く場合に生じる。
【００８４】
また、テキストブロックと非テキストブロックの間にある可視線の分割は実行されない。しかし、そのような可視線に対しては、ステップＳ６２０において適切な分割が実行される。もちろん、物理的な分割も存在するが、その場合、水平成分、垂直成分、斜めの成分のいずれかを持つテキストブロックにおいては、ステップＳ６２４で集められたテキストブロックは分割される。
【００８５】
ステップＳ６２５で、ステップＳ６０７からステップＳ６１１の処理によって格納された各テキストブロックの方向が混合方向を持つ原稿ページであるか否かを判定する。特に、混合方向を持つ原稿ページのタイプである場合、ステップＳ６２５ａで、その原稿ページの各テキストブロックの方向が水平、垂直あるいはそれ以外の方向であるか否かが判定される。この方向（ステップＳ６２１ａで判定された方向あるいは、ステップＳ６０９でユーザによって入力された方向）は、後述するステップにおいて、各テキストブロックのテキストラインを形成するために用いられる。更に、テキストブロックの方向は、近傍にある２つのテキストブロックが結合可能であるか否かを判定するために役立つ。例えば、その２つのテキストブロックの方向が一致しない場合、通常はその２つのテキストブロックは結合されてしまうからである。
【００８６】
テキストブロックの方向の判定は、そのテキストブロックのサイズと、そのテキストブロックの中の連結成分のサイズとそのサイズに加算して得られるテキストブロックのサイズの加算量に基づいて行う。例えば、水平方向の連結成分を持つテキストブロックは一定の高さより幅を持っている。更に、水平方向と垂直方向の隙間の数とそのサイズは、テキストブロックの方向を判定するための付加要素として考慮される。
【００８７】
ステップＳ６２６で、各テキストブロックのテキストラインを形成する。例えば、テキストブロックの方向が水平である場合、各連結成分の水平方向の距離が接近していて、また、垂直方向に位置する近傍の連結成分と所定角度で重なっている連結成分は水平方向のテキストラインとして集められる。同様にして、テキストブロックの方向が垂直である場合、各連結成分の垂直方向の距離が接近していて、また、水平方向に位置する近傍の連結成分と所定角度で重なっている連結成分は垂直方向のテキストラインとして集められる。テキストラインの構成は、真っ直ぐな原稿ページばかりでなく、ある傾き角度を持つ原稿ページに対しても考慮する。
【００８８】
ステップＳ６２７で、原稿ページの傾き角度を検出する。原稿ページの傾きは、ステップＳ６２６で形成された各テキストラインの傾きに対し、最小２乗法を用いて算出する。原稿ページの傾きは、その原稿ページの各テキストラインの傾き角度に対し最小２乗法を用いて算出される平均の傾き角度である。
ステップＳ６２７で算出された傾き角度は、その原稿ページの階層ツリー構造のルートノードにグローバル変数として格納される。ステップＳ６０７からステップＳ６１１の処理を通して格納される原稿ページのタイプと同様に、その原稿ページの傾き角度は、例えば、画像データの処理過程に必要な情報として光学的認識（ＯＣＲ）処理あるいは他のタイプの処理が実行される際に、グローバル変数として用いられる。
【００８９】
ステップＳ６２８で、ステップＳ６２７で算出された傾き角度が所定最大傾き角度を越えるか否かを判定する。特に、ステップＳ６２８では、傾き角度はブロックセレクション処理で設定される。また、傾き角度が所定最大傾き角度を越える場合、ステップＳ６２８で、原稿ページの傾きが大きすぎることをユーザに報知する信号としてのエラーコードが、ブロックセレクション処理によって出力される。
【００９０】
ステップＳ６２９で、後処理が実行される。後処理は、簡潔で明瞭にブロックを表現するために実行される。また、後処理は、キャラクタ認識やデータ圧縮等の追加処理に適用させることもできる。更に、後処理において、テキストブロックは、他のテキストブロックあるいは非テキストブロックを結合し、また、他の非テキストブロックあるいはテキストブロックも結合する。
【００９１】
後処理は、ステップＳ６２７で獲得される原稿ページの傾き角度に基づいて適用される。例えば、原稿ページの欄の隙間がほんのわずかだけ傾いている原稿ページは更に明瞭にされる。つまり、それらのブロック（欄）は積極的に結合される。一方、例えば、原稿ページの傾き角度が大きく、複数のブロックの長方形領域が重なっている場合、それらのブロックはより控えめに結合される。特に、原稿ページの傾き角度が小さい程、テキストブロックはそのテキストブロックの一部の領域に基づいて解析された欄情報に従って結合される。テキストブロックの結合は、基本的には同じ欄に含むテキストブロックであるかどうかに依存する。つまり。例えば、それらのテキストブロックが互いに接近しているか、それらのテキストブロックの方向が一定であるか、それらのテキストブロックの結合が他のテキストブロックとの重なりを生じるか等によって結合の実行の有無を決定する。
【００９２】
一方、非テキストブロックの結合は非テキスト成分を含む主要な複数の非テキストブロックの部分に依存する。例えば、いくつかの図形は、いくつかの非連結成分によって形成される。これらのいくつかの非連結成分が同一の図形と判定されると、階層ツリー構造のダミーノードとして新たな合成領域が描画される。つまり、この合成領域はすべての非連結成分を包含するために生成される。更に、いくつかのテキストブロックが、同一図形として判定される場合、例えば、キャプションのようなテキストブロックの場合、それらのキャプションは合成領域として生成される。また、その合成領域は図形とテキスト領域を包含するダミーノードとして階層ツリー構造で用いられる。合成領域における処理の詳細は、後述のステップＳ６３４で説明する。
【００９３】
後処理が実行されると、テキストブロック、線ブロック、図形ブロック、枠ブロック、非テキストブロック、合成領域ブロック、表ブロックのいずれかのブロックに従う特定処理のための第１ブロック情報が選択される。本実施の形態によれば、特定処理は図形あるいは合成領域のブロックに対して必要とし、それ以外の他のブロックでは特定処理は行わない。何故なら、図形あるいは合成領域以外の他のブロックは、ブロックセレクション処理によって必要とされる処理が完了するからである。図形と合成領域における特定処理について以下に説明する。
図１１は、処理対象のブロックが図形情報を持つ画像データとして認識された場合（ステップＳ６３２）に、実行される特定処理の処理フロー示すフローチャートである。
【００９４】
ブロックセレクション処理によって、画像データが図形情報を持つ画像データであると、その画像データが、ハーフトーン、線画、折れ線等の図形タイプの認識を試みる。そのため、それらの図形ブロックは上述のような認識ができないので、図１１に示される特定処理は、それらの図形ブロックを「未知図形」として表現する。
【００９５】
ステップＳ１１０１で、特定処理を実行するための図形タイプのブロックが選択される。ステップＳ１１０２で、そのブロックの図形タイプの補助属性が格納されている場合、選択された図形タイプのブロックの特定処理が実行される（ステップＳ１１０２）。このように、「ハーフトーン」、「線画」、「折れ線」のいずれかの補助属性が格納されている場合（即ち、図１０に示されるような処理によって補助情報が格納されている）、その図形タイプのブロックの特定処理は完了する。
【００９６】
一方、画像データが、ハーフトーン、線画、折れ線のいずれかとして認識されない場合、そのブロックの図形タイプは未知として認識され、「未知」である補助属性をそのブロックに対応するノードに格納する（ステップＳ１１０４）。ステップＳ１１０４で、図形情報を持つ画像データの特定処理を中断する。
図１３は、処理対象のブロックが複数の画像データのタイプを含む合成領域持つ画像データとして認識された場合（ステップＳ６３４）に、実行される特定処理の処理フロー示すフローチャートである。
【００９７】
つまり、ブロックセレクション処理によって、そのブロックは２つ以上の画像データのタイプを持つ画像データのブロックとして認識される。本発明の実施の形態によれば、複数の画像データのタイプを持つ画像データの認識を行うために合成領域がブロックセレクション処理の処理過程に適用される。
ステップＳ１３０１で、ブロックの中に同一タイプの画像データを持つブロックが存在するか否かが判定される。例えば、図１４Ａに示されるように、原稿ページ１３００には、タイトル１３０１、テキスト領域１３０２、１３０３、図形領域１３０５、１３０７、１３０９を含む。また、テキストキャプション１３０６も含んでいる。このような図１４Ａに示されるような原稿ページにおいて、ブロックセレクション処理を実行すると、図１５Ａに示されるような階層ツリー構造を持つ、分割された各領域のブロックが生成される。
【００９８】
また、図１４Ｂに示すように、タイトル１３００とテキスト領域１３０２、１３０３、可視ブロック１３１９、１３２０、１３２１として扱われる。しかしながら、テキストキャプション１３０６を持つ図形領域１３０５、１３０７、１３０９は、２つ以上の画像データのタイプを持つ画像データである「合成領域」１３２３としてグループ化される。
【００９９】
ステップＳ１３０１で、同一ブロックが存在しないと認識された場合、ステップＳ１３０２に進む。しかしながら、同一ブロックが認識された場合、ステップＳ１３０３に進み、そのブロックは「合成領域」として認識され、合成領域ノードが階層ツリー構造に付加される（ステップＳ１３０４）。
ステップＳ１３０５で、それぞれの同一ブロックに対し、それらのブロックに対応する階層ツリー構造のノードの位置が変更され、「合成領域」ノードの下に付加される。図１５Ｂは、上述の変更によって、合成領域ノード１３２３より分岐して生成されるテキスト１３０６、図形１３０５、１３０７、１３０９のノードを示す図である。
【０１００】
再び、図６Ｃの説明に戻る。
原稿ページの階層ツリー構造が生成されると、ステップＳ６４０で、ステップＳ６０５で格納された確保された階層ツリー構造の記憶領域にその生成された階層ツリー構造が格納される。
尚、各ブロックを表現するための最も簡単な方法は長方形であり、時にはブロックは孤立する長方形領域に存在しない。また、長方形のブロックの重なりが生じたりする。このブロックの重なりは、画像データのブロックの抽出の際にユーザを混乱させてしまう。そのため、長方形の使用するために、各ブロックを表現するために他の表現方法を提供する。他の表現方法は、連結成分の輪郭検索によって行われる。但し、輪郭のデータは簡潔化された連続する輪郭の組あるいは後述の連続する重ならない各ブロックの長方形であるとする。このように作られた輪郭は、ブロックの中に２つ以上の連結成分が存在する場合のそのすべてを含む連結成分から生成される。この方法は、連続する輪郭の組あるいは連続する重ならない長方形によって簡潔に、各ブロックを表現することができる。このような簡潔にブロックを表現する方法に基づいて、各ブロックの画像データは、各輪郭の組あるいは長方形の領域より直接抽出することができる。
【０１０１】
ステップＳ６４１で、ブロックセレクション処理プログラムはユーザに対し次の原稿ページの解析を行うか否かを要求する。入力された原稿ページがない場合、ステップＳ６４２で、ブロックセレクション処理を中断する。一方、次の原稿ページの解析の指示がユーザからある場合、ステップＳ６４３で、階層ツリー構造の格納するために割り当てられた記憶領域に、充分な次の原稿ページの階層ツリー構造を格納する領域があるか否かを判定する。
【０１０２】
階層ツリー構造の格納するために割り当てられた記憶領域に、充分な次の原稿ページの階層ツリー構造を格納する記憶領域がある場合、ステップＳ６０３に戻って、次の原稿ページのブロックセレクション処理を実行する。一方、階層ツリー構造の格納するために割り当てられた記憶領域に、充分な次の原稿ページの階層ツリー構造を格納する記憶領域がない場合、ステップＳ６４６で、エラーコードがユーザに対して出力される。
【０１０３】
以上説明したように、本実施の形態によれば、ブロックセレクション処理プログラムは、入力した原稿の有無に応じて処理を自動的に中断したり、階層ツリー構造の格納するために割り当てられた記憶領域に、充分な次の原稿ページの階層ツリー構造を格納する記憶領域がある場合、次の原稿ページの階層ツリー構造を格納する記憶領域を割り当てることができる。
【０１０４】
尚、光学的文字認識（ＯＣＲ）は、上述のブロックセレクション処理による出力を得るための、テキストブロックを読み取るために必要なアプリケーションとして限定されない。原稿の画像データを得ることのできる他のアプリケーションを用いて、例えば、原稿の格納と伝送、ブロックの認識と実行、原稿認識、原稿検索等のブロックセレクション処理を実行しても良い。
【０１０５】
例えば、ブロックセレクション処理を使用する際に、より効率的に原稿の格納と伝送を実現するために、複数の画像データの圧縮方法を用いることでそれが実現できる。このように、例えば、テキストブロックは２値圧縮によって格納し、図形ブロックは、複数レベルの図形圧縮によって格納することができる。
また、ブロックの認識と実行は、ある形と他の形を区別するために各形に特定点を配置する必要をなくすためにブロックセレクション処理が生成される。ブロックセレクション処理を用いることで、ブロックの認識と実行は、上述のようなより一般的な方法で実行され、ブロックセレクション処理後、階層ツリー構造によって表現される。その階層ツリー構造は、新たな階層ツリー構造が存在する毎に、その内容が更新される階層ツリー構造の辞書を比較することによって認識される。
【０１０６】
また、原稿の認識は論理的な解析によって実行される。基本的には、原稿認識は、所定の規則に従って原稿の１ページ分の画像データに分類する。そのため、ブロックセレクション処理の階層的な特徴により、ページ単位の物理的な解析を手伝うために原稿の構造的な基礎が獲得される。
また、原稿の検索と格納は、上述のブロックセレクション処理に最大限使用することができる。ブロックセレクション処理を用いることで、原稿１ページ分の画像データは、上述の図３に示されるような形式で、その原稿画像よりもむしろ複数のブロックで表示される。その結果、ユーザは原稿に対するブロックの形式を一瞥することで、原稿の構成で必要とされるか否かについての視覚的な見当を与えるレイアウト情報を獲得することができる。そのため、ユーザは予め設定されている原稿の形式やある特定の要求の基づいて、テキストあるいは非テキストブロックの情報を獲得することができる。例えば、図１６に示されるような標準ビジネスメモには、「To」領域、「From」領域、「CC」（カーボンコピー）領域のようなメモから構成されている。図３の原稿において、各ブロックに対して特定の処理を指示する方法として、このビジネスメモを用いると、ユーザは、「３番目の線」に「CC」を指示するというような、各ブロックの位置情報に基づいく要求の仕方が可能である。尚、本実施の形態では、ブロックの位置の情報によって処理対象のブロックを特定しているが、これに限定されず様々なブロックを特定できる情報によってブロックを特定しても良い。例えば、ユーザは、「３番目の線」と指示するかわりに、「原稿を半分にした時の、その原稿の上部の最終線よりも上に位置する水平線」というような特定方法で、対象とするブロックに「CC」を指示することができる。このように、ユーザによるブロックの特定は、自動的にブロックを抽出できる領域として解釈される。
【０１０７】
尚、本発明は好適な施の形態について説明されたが、本発明は開示された実施の形態に限定されるものではないことが理解されるべきである。逆に、発明の精神と範囲内に含まれる、様々な修正や同等の変形が可能であるよう意図されている。特許請求に範囲の記載は、そうして修正及び同等の構成及び機能の全てに渡るように解釈が与えられるものである。
【０１０８】
尚、本発明は、複数の機器から構成されるシステムに適用しても、１つの機器からなる装置に適用しても良い。また、本発明はシステム或は装置にプログラムを供給することによって実施される場合にも適用できることは言うまでもない。この場合、本発明に係るプログラムを格納した記憶媒体が、本発明を構成することになる。そして、該記憶媒体からそのプログラムをシステム或は装置に読み出すことによって、そのシステム或は装置が、予め定められた仕方で動作する。
【０１０９】
【発明の効果】
以上の説明からも明らかなように、本発明によれば、 ブロックセレクション処理の処理対象である原稿のデータ量と歪みを監視することで、処理精度が向上するブロックセレクション処理を実行できるページ解析システムを提供できる。
【図面の簡単な説明】
【図１】原稿ページの一例を示す図である。
【図２】図１の原稿ページに関して、ブロックセレクション処理の処理結果より得られる階層ツリー構造の一例を示す図である。
【図３】図２の階層ツリー構造に基づいて生成される原稿ページの表示例を示す図である。
【図４】本発明を適用する実施の形態の装置の外観図である。
【図５】図５の装置の構成を示すブロック図である。
【図６Ａ】本発明のブロックセレクション処理において生成されるページ解析システムの処理フローを示すフローチャートである。
【図６Ｂ】本発明のブロックセレクション処理において生成されるページ解析システムの処理フローを示すフローチャートである。
【図６Ｃ】本発明のブロックセレクション処理において生成されるページ解析システムの処理フローを示すフローチャートである。
【図６Ｄ】本発明のブロックセレクション処理において生成されるページ解析システムの処理フローを示すフローチャートである。
【図７Ａ】入力原稿ページも一部分の領域の解析方法の処理フローを示すフローチャートである。
【図７Ｂ】解析された原稿の各領域の一例を示す図である。
【図８】解析対象のピクセル画像データを格納する記憶領域の割当方法を説明するための図である。
【図９Ａ】連結成分の８方向検索を示す図である。
【図９Ｂ】白輪郭の４方向検索を示す図である。
【図１０】非テキスト連結成分の区別の処理フローを示すフローチャートである。
【図１１】図形ブロックの図形タイプの判定方法の処理フローを示すフローチャートである。
【図１２Ａ】折れ線を含む原稿ページの一例を示す図である。
【図１２Ｂ】折れ線を含む原稿ページの一例を示す図である。
【図１２Ｃ】折れ線の一例を示す図である。
【図１２Ｄ】折れ線の一例を示す図である。
【図１３】合成領域の処理方法の処理フローを示す図である。
【図１４Ａ】合成領域を含む原稿ページの一例を示す図である。
【図１４Ｂ】合成領域の含む原稿ページの一例を示す図である。
【図１５Ａ】図１４Ａの原稿ページの階層ツリー構造を示す図である。
【図１５Ｂ】図１４Ｂの原稿ページの階層ツリー構造を示す図である。
【図１６】原稿からテキストを抽出するための標準的なメニューの一例を示す図である。
【符号の説明】
５２０  ＣＰＵ
５２１  コンピュータバス
５２２  スキャナインタフェース
５２３  プリンタインタフェース
５２４  ネットワークインタフェース
５２６  ＦＡＸ／モデムインタフェース
５２７  ディスプレイインタフェース
５２８  キーボードインタフェース
５２９  マウスインタフェース
５３０  メインメモリ
【図１】
0003825820.tif 000002
【図２】
0003825820.tif 000003
【図３】
0003825820.tif 000004
【図４】
0003825820.tif 000005
【図５】
0003825820.tif 000006
【図６Ａ】
0003825820.tif 000007
【図６Ｂ】
0003825820.tif 000008
【図６Ｃ】
0003825820.tif 000009
【図６Ｄ】
0003825820.tif 000010
【図７Ａ】
0003825820.tif 000011
【図７Ｂ】
0003825820.tif 000012
【図８】
0003825820.tif 000013
【図９Ａ】
0003825820.tif 000014
【図９Ｂ】
0003825820.tif 000015
【図１０】
0003825820.tif 000016
【図１１】
0003825820.tif 000017
【図１２Ａ】
0003825820.tif 000018
【図１２Ｂ】
0003825820.tif 000019
【図１２Ｃ】
0003825820.tif 000020
【図１２Ｄ】
0003825820.tif 000021
【図１３】
0003825820.tif 000022
【図１４Ａ】
0003825820.tif 000023
【図１４Ｂ】
0003825820.tif 000024
【図１５Ａ】
0003825820.tif 000025
【図１５Ｂ】
0003825820.tif 000026
【図１６】
0003825820.tif 000027