(57)【特許請求の範囲】
【請求項１】
画像データにおける黒画素の連続成分を検出する連続成分検出工程と、
前記検出された連続成分を、サイズ及び他の連続成分との相対的位置に基づいて、テキスト又は非テキストに分類する分類工程と、
少なくとも一部が前記分類工程で分類された非テキストの連続成分のエッジに沿っており且つ当該非テキストの連続成分に隣接する領域へ延びる不可視の直線をサーチするサーチ工程と、
前記分類工程で分類されたテキストの連続成分の相対的位置に基づいて、テキストブロックを形成するテキストブロック形成工程と、
前記テキストブロック形成工程で形成されたテキストブロックを、前記非テキストの連続成分の可視線または前記サーチ工程でサーチされた不可視の直線が横切っている場合、当該テキストブロックを当該可視線または不可視の直線で分割する分割工程と、
前記分割工程で分割されたテキストブロックに対して、所定の後処理を実行する後処理工程とを備えることを特徴とするブロック選択方法。
【請求項２】
前記画像データを入力する入力工程を更に備え、該入力工程は、前記画像データが２値画像データではない場合に、当該画像データを２値画像データに変換してから入力することを特徴とする請求項１に記載のブロック選択方法。
【請求項３】
前記連続成分検出工程で検出された連続成分の階層ツリーを、各連続成分の位置に基づいて形成するツリー形成工程を更に備えることを特徴とする請求項１に記載のブロック選択方法。
【請求項４】
前記後処理工程では、前記テキストブロックにおける文字画像を文字認識することを特徴とする請求項１に記載のブロック選択方法。
【請求項５】
前記後処理工程では、前記テキストブロックをデータ圧縮することを特徴とする請求項１に記載のブロック選択方法。
【請求項６】
前記分類工程で分類された非テキストの連続成分について、少なくとも可視のラインであるか否かに分類する非テキスト連続成分分類工程を更に備えることを特徴とする請求項１に記載のブロック選択方法。
【請求項７】
前記非テキスト連続成分分類工程では、ライン、中間調画像、線画、フレーム、未知のいずれかに分類することを特徴とする請求項６に記載のブロック選択方法。
【請求項８】
画像データにおける黒画素の連続成分を検出する連続成分検出手段と、
前記検出された連続成分を、サイズ及び他の連続成分との相対的位置に基づいて、テキスト又は非テキストに分類する分類手段と、
少なくとも一部が前記分類手段で分類された非テキストの連続成分のエッジに沿っており且つ当該非テキストの連続成分に隣接する領域へ延びる不可視の直線をサーチするサーチ手段と、
前記分類手段で分類されたテキストの連続成分の相対的位置に基づいて、テキストブロックを形成するテキストブロック形成手段と、
前記テキストブロック形成手段で形成されたテキストブロックを、前記非テキストの連続成分の可視線または前記サーチ手段でサーチされた不可視の直線が横切っている場合、当該テキストブロックを当該可視線または不可視の直線で分割する分割手段と、
前記分割手段で分割されたテキストブロックに対して、所定の後処理を実行する後処理手段とを備えることを特徴とするブロック選択装置。
【請求項９】
前記画像データを入力する入力手段を更に備え、該入力手段は、前記画像データが２値画像データではない場合に、当該画像データを２値画像データに変換してから入力することを特徴とする請求項８に記載のブロック選択装置。
【請求項１０】
前記連続成分検出手段で検出された連続成分の階層ツリーを、各連続成分の位置に基づいて形成するツリー形成手段を更に備えることを特徴とする請求項８に記載のブロック選択装置。
【請求項１１】
前記後処理手段では、前記テキストブロックにおける文字画像を文字認識することを特徴とする請求項８に記載のブロック選択装置。
【請求項１２】
前記後処理手段では、前記テキストブロックをデータ圧縮することを特徴とする請求項８に記載のブロック選択装置。
【請求項１３】
前記分類手段で分類された非テキストの連続成分について、少なくとも可視のラインであるか否かに分類する非テキスト連続成分分類手段を更に備えることを特徴とする請求項８に記載のブロック選択装置。
【請求項１４】
前記非テキスト連続成分分類手段では、ライン、中間調画像、線画、フレーム、未知のいずれかに分類することを特徴とする請求項１３に記載のブロック選択装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、例えば文字認識に先立って行なわれる文字ブロックの処理のための方法及び装置に関する。さらに詳しくは、認識に先立ち、画像データのブロックが画像データの文字に基づいて分類され選択される、文字ブロック処理方法及び装置に関するものである。例えば、画像データがテキスト画像データ（水平及び／または垂直）か、それとも中間調（またはグレイスケール）画像、線画、表、垂直または水平線、フレーム等の非テキスト画像データのいずれであるかに基づいて、画像データブロックが選択されて分類される。
【０００２】
【従来の技術】
近年、テキストデータの画像を分析して、テキストデータ内の個々の文字を認識したり、認識した文字に対応する、コンピュータが読み取れる文字コードファイルを作成することが可能になった。そうしたファイルは、ワードプロセッシングや、データ圧縮、あるいはデータ処理プログラムで操作することができる。そうしたシステムは、以下「文字認識システム」と称されるが、リタイプもしくはテキストデータの再入力の必要がなくなるため有益である。例えば、ファクシミリ送信されたり複写機やマイクロフィルムで再現された文書に対して文字認識を行なって、その文書の文字や数字の文字コード（例えばＡＳＣＩＩコード）を含むコンピュータファイルを作成し、リタイプや文書の再入力を必要とせずに、更なるワードプロセッシングまたはデータ処理を文書に対して行なうことが可能である。
【０００３】
文字認識される文書は、しばしば多くの異なるタイプの画像データを含んでおり、それらの全てが認識できるわけではない。例えば、現在、テキスト画像データの認識が可能だとすると、一方で、非テキスト画像データの認識は非常に困難である。通常、文字認識対象の文書はテキスト画像データブロックと、中間調画像、線画、線等の非テキスト画像データブロックとを含んでいる。さらに、文書は表や、枠組があったり、または枠組みは無いがテーブル状に配置されたデータも含んでいる場合もある。従って、文字認識処理の前に、文書内の個々のブロックをブロックの画像データのタイプに基づいて分類し、テキストタイプのブロックを画像データから選択することが必要である。
【０００４】
図１は代表的な文書の１ページを示している。図１において、文書ページ１０１は２欄形式に構成されている。ページには、タイトルに適切な大きいサイズのフォントのテキスト情報を含むタイトルブロック１０２と、テキストデータのラインを含むテキストブロック１０４と、非テキストのグラフィック画像を含むグラフィックブロック１０５と、表のテキストまたは数字情報を含む表ブロック１０６と、グラフィックまたは表情報のブロックの説明文（caption）である小サイズのテキストデータを含むキャプションブロック１０７とが含まれている。各情報のブロックはそこに含まれる情報のタイプに基づいて分類され、その分類に応じて分割される。
【０００５】
【発明が解決しようとする課題】
予め、画像データのテキストタイプのブロックを検出するために、画像データにおける黒画素を水平及び垂直に展開して、水平及び垂直に隣接する単数または複数の白画素に展開することで画素画像データをにじませる（スミアー技術）ことが考えられた。こうしたスミアー技術は、スミアーパラメータを適切に選択することができる様に、テキストタイプ画像データの文字の予備知識（例えばフォントサイズ）に依存しているため、不十分である。さらに、スミアーパラメータの小さな変化で選択結果に大きな変化が生じる。スミアー技術はまた、必ず原稿文書の内部構造を保持できるわけではない。例えば、スミアーにより２欄形式の原稿が１欄に変わってしまうことがある。このような状況は、テキストデータが格納されている順序を狂わせ、原稿テキストの正確な再構成を不可能にしてしまうことから、不都合である。さらに、スミアー技術では、時折テキストタイプデータを非テキストタイプデータ中ににじませ、全体の領域がテキストタイプデータとして誤認識されることが知られている。
【０００６】
同出願人による、１９９２年４月２４日出願の米国特許出願第０７／８７３、０１２号では、格納された文書内の文字ブロックを選択するための他の方法が提案されている。そこでは、格納された文書に対し、最初に所謂「結合成分（connected components）」のサーチが行なわれる。これは、各画素の周囲の８方向のいずれかに存在する、２つ以上の画素が結合されたものである。次に、テキスト結合成分は非テキスト結合成分から分離されて、非テキスト結合成分は、例えば、表、中間調画像、線画等として分類される。次に、文書の何らかの歪みの方向が検出され、もし歪みが垂直ならば画像は９０度回転され、結合成分のサーチが再び行なわれる。歪みの補正の後、テキストの適切なブロック、例えば欄が識別される様に、非テキスト成分のエッジに添った目に見えない白ラインがサーチされる。その後、水平テキスト列とタイトル列が形成され、水平テキスト列はグループ化されて四角形に配置されたテキストブロックになる。そして、後処理が行なわれて、更なる文字認識処理のために、識別されたテキストブロックが準備される。０７／８７３、０１２号は参照により本願に併合されている。
【０００７】
上記のブロック選択技術は水平文書（例えば英語文書）に適切であるが、１ページが水平及び垂直テキストブロック（２方向）を含んでいる場合にも適用可能である。例えば、日本語の文書は垂直な漢字文字と表や数字記号などの水平な文字との組み合わせを含んでいる。また、ある種の英語文書は特定の情報を強調したり、所望の効果を提供するために、垂直に配置された文字を含んでいる。
【０００８】
さらに、スキャンされたページ自体はしばしば歪んでおり、上記のブロック選択技術では、最初に歪みを識別して、テキストブロックを形成する前に画像を回転させることでこの問題に対処している。この技術を実用化する際には、処理速度と正確さにおいて２つの実質的な問題となる。さらに詳しくは、上記のブロック選択技術では、ブロック領域は四角形で表され、非テキストブロックの境界もまた記録される。しかし、歪んだ文書の場合、四角形はテキストブロック間の分離を不明瞭にして、実際重なることもある。これにより、ブロック内のデータの誤分類が起こり、文字認識のエラーとなることもある。
【０００９】
従って、垂直及び水平テキストブロックが認識され、テキストブロック形成の前に歪んだ文書を回転させる必要の無い、格納文書におけるテキスト及び非テキストブロックを効果的に且つ効率的に選択するための方法及び装置が求められている。これにより、処理時間を節約し、認識精度を向上させる、より柔軟なブロック選択技術が提供される。
【００１２】
【課題を解決するための手段】
上記の目的を達成する本発明の一つの態様によるブロック選択方法は、
画像データにおける黒画素の連続成分を検出する連続成分検出工程と、
前記検出された連続成分を、サイズ及び他の連続成分との相対的位置に基づいて、テキスト又は非テキストに分類する分類工程と、
少なくとも一部が前記分類工程で分類された非テキストの連続成分のエッジに沿っており且つ当該非テキストの連続成分に隣接する領域へ延びる不可視の直線をサーチするサーチ工程と、
前記分類工程で分類されたテキストの連続成分の相対的位置に基づいて、テキストブロックを形成するテキストブロック形成工程と、
前記テキストブロック形成工程で形成されたテキストブロックを、前記非テキストの連続成分の可視線または前記サーチ工程でサーチされた不可視の直線が横切っている場合、当該テキストブロックを当該可視線または不可視の直線で分割する分割工程と、
前記分割工程で分割されたテキストブロックに対して、所定の後処理を実行する後処理工程とを備える。
【００１３】
また、上記の目的を達成するための本発明の他の態様によるブロック選択装置は以下の構成を備える。即ち、
画像データにおける黒画素の連続成分を検出する連続成分検出手段と、
前記検出された連続成分を、サイズ及び他の連続成分との相対的位置に基づいて、テキスト又は非テキストに分類する分類手段と、
少なくとも一部が前記分類手段で分類された非テキストの連続成分のエッジに沿っており且つ当該非テキストの連続成分に隣接する領域へ延びる不可視の直線をサーチするサーチ手段と、
前記分類手段で分類されたテキストの連続成分の相対的位置に基づいて、テキストブロックを形成するテキストブロック形成手段と、
前記テキストブロック形成手段で形成されたテキストブロックを、前記非テキストの連続成分の可視線または前記サーチ手段でサーチされた不可視の直線が横切っている場合、当該テキストブロックを当該可視線または不可視の直線で分割する分割手段と、
前記分割手段で分割されたテキストブロックに対して、所定の後処理を実行する後処理手段とを備える。
【００１７】
なお、これらの及び他の本発明の特徴及び有利な点は、以下の添付の図面に従う好適な実施例の詳細な説明を参照することにより、さらに容易に理解されるであろう。
【００１８】
【実施例】
以下に添付の図面を参照して本発明の好適な実施例を説明する。
【００１９】
本発明は、複写機、ファクシミリ装置、ビデオまたはスチルビデオカメラ、レーザビームプリンタ等の、文字認識処理が望まれる画像処理または画像再生装置などの様々な装置において実現される。そうした装置では、文字画像を含む画像は、文字画像が文字認識処理される様に処理または再生される。必要であれば、認識された文字画像を標準化された文字セットまたはフォントに換えて、原稿の文字画像ではなく標準化された文字を再送信したり再生したりすることもできる。本発明はまた、汎用コンピュータや、パーソナルコンピュータ、ワードプロセッシングまたはデータ処理機器等のオフィス機器、複数のビジネス機器ツールを１つの統合パッケージにおいて結合した統合オフィスオートメーション機器等においても実現され得るものである。
【００２０】
図２は本発明の代表的な実施例の外観を示す図である。図２において、ＩＢＭ−ＰＣ（商標）またはＰＣ互換性を持つコンピュータ等のコンピュータ１０が示されており、コンピュータ１０は、マイクロソフトウインドウズ・オペレーティングシステム（商標）等のグラフィカル・ユーザインタフェース・オペレーティングシステムを備えている。コンピュータ１０にはカラーモニタ等の表示画面１１が設けられている。コンピュータ１０は、さらに、白黒、中間調、カラービットマップ画像等のデータファイルを格納したり、コンピュータ１０がデータファイルを操作したり、表示画面１１を通じてデータをオペレータにファイルの形で提示するためのプログラム・インストラクション・シーケンスを含むアプリケーションプログラムファイルを格納するための、コンピュータディスクドライブ１４等のマスク格納装置を備えている。例えば、ディスクドライブ１４上のアプリケーションプログラムは、光ディスク上のデータにアクセスするアプリケーションプログラムや、他の情報処理プログラムを含むものである。
【００２１】
テキストデータ入力や、オペレータが表示画面１１に表示されたデータの選択や操作を行なうためのキーボード１５がコンピュータ１０に接続されている。さらに、表示画面１１上で処理対象物の選択や操作を行なうための、マウス等のポインティングデバイス１６が設けられている。スキャナ１８は文書または他の画像を走査して、例えば、それらの文書のビットマップ画像をコンピュータ１０に提供する。それらの画像はコンピュータ１０により直ちに使用されるか、あるいはコンピュータ１０はこれらの画像をディスクドライブ１４へ格納したり、または光ディスクドライブ２０を介してディスク１９等の光ディスクに格納する。引き続くコンピュータ１０による処理のために、ビットマップ画像データはディスク１９またはコンピュータディスクドライブ１４から検索される。電話リンク２１またはネットワーク２２を介して、コンピュータ１０内の不図示のモデムを通じて、ビットマップ画像データ及び他のデータを供給するための他の手段も設けることができる。さらに、取り外し可能なフロッピーディスクドライブを設けることも可能であり、または、不図示のビデオインタフェースを介して、デジタルまたはアナログのビデオ情報をコンピュータ１０に入力してもよい。
【００２２】
コンピュータ１０により処理された情報を出力するために、プリンタ２４が設けられている。
【００２３】
コンピュータオペレータ命令に従って、そしてオペレーティングシステムの制御下で、格納されたアプリケーションプログラムが選択的に作動され、入力されたデータの処理や操作を行なう。例えば、以下に詳細に説明する様に、文字認識プログラムは、オペレータがスキャナ１８を介して文書画像をスキャン入力し、スキャンされた画像を光ディスク１９へ格納するために動作する。オペレータはオペレーティングシステム及びアプリケーションプログラムに従って、スキャン入力した文書を光ディスク１９から検索することができる。
【００２４】
図３は本発明の１実施例の詳細なブロック図であり、スキャニング、ファクシミリ、情報送信及び受信、そして情報処理能力を有し、情報処理能力としては選択的にワードプロセッシング及びデータ処理能力を有する統合オフィスオートメーション機器に関するものである。
【００２５】
図３の装置において、画像はファクシミリ送信や、原稿のスキャン入力や、モデムを介した遠隔受信等によって入力される。本実施例によれば、画像中の文字を認識して、認識された文字のコンピュータテキストファイルを作成し、装置のワードプロセッシング、スプレッドシートプロセッシングまたは他の情報処理能力を使用してテキストファイルを修正することができる。修正されたテキストファイル（または修正を行なっていないテキストファイル）は再送信されたり、あるいは、例えばテキストファイルをスピーカまたは通常の音声電話機により音声再生するスピーチ合成技術を用いて出力することができる。
【００２６】
図３では、プログラム可能なマイクロプロセッサ等の中央処理装置（ＣＰＵ）３０がバス３１と接続されている。さらにバスには、画像を画素単位で画像メモリ（例えば下記のＲＡＭ３２）へスキャン入力するスキャナ１８、デジタルデータをアナログ形式で電話線２１ａを介して送受信するモデム３３、及び画像を電話線２１ｂを介して送受信するファクシミリ装置３４（所望により不図示の電話を含む）が接続されている。電話線２１ａ、２１ｂは同じ線でもよいし、不図示のネットワーク制御部を通じて統合されていてもよい。バス３１には、さらに、ＣＰＵ３０に実行される単数または複数のコンピュータプログラムを格納する読み取り専用メモリ（ＲＯＭ）３５、認識処理の間に入力された文字が参照される文字の辞書を格納する文字ディクショナリ３６、入力された画像データ、処理された画像データ、画像構造に関する情報等を格納するランダムアクセスメモリ（ＲＡＭ）３２、文字認識処理の間に認識された文字の識別が出力される出力装置３７（ディスクメモリまたはスピーカ／音声電話線インタフェースを有するスピーチ合成装置）、本装置によって処理された画像を表示するプリンタ／表示装置２４、及びオペレータが装置を制御するためのキーボード１５が接続されている。
【００２７】
バス３１に接続された装置は１つの統合オフィスオートメーションツールに収納されているが、これらの装置の幾つかあるいは全てが選択的にスタンドアロン形式で提供され得ることも明らかである。
【００２８】
スキャナ１８、モデム３３、ファクシミリ３４は、画像データを装置へ入力する選択的な形の入力手段を構成している。スキャナ１８を使用した場合、原稿はライン単位、画素単位でスキャンされて、そしてＣＰＵ３０の制御下で、画像データの画素がＲＡＭ３２の画像メモリにビットマップメモリ形式で格納される。モデム３３を使用した場合、画像データは電話線２１ａよりアナログ形式で受信され、モデム３３によりデジタル画素形式に変換され、ＲＡＭ３２の画像メモリに格納される。ファクシミリ３４を使用した場合、画像データは修正ハフマンランレングス符号化方式等で圧縮または符号化された形で、電話線２１ｂより受信される。圧縮画像データは、ファクシミリ３４によって公知の技術によりデジタル画像画素データに伸張（uncompressed）され、ＣＰＵ３０は画像データの画素をビットマップ形式でＲＡＭ３２の画像メモリに格納する。他の入力手段も勿論使用可能である。例えば、画像データは、ディスクメモリ等の大型記憶装置から簡単に検索して獲得することができ、また、ビデオまたはスチルビデオカメラから得ることもできる。
【００２９】
ファクシミリ３４と出力装置３７は、文字認識された画像データを装置から出力するための選択的な出力手段を構成している。ファクシミリ３４を使用した場合、本実施例に従って認識処理された文字画像は標準文字セットまたはフォントに変換され、装置から送信することができる。これにより、例えば、文字画像を含む画像の受信、文字画像の文字認識、再送信前に行なう認識された文字の標準文字フォントへの変換が可能となり、劣化した画像品質を向上させる。
【００３０】
モデム３３及び出力装置３７は、画像データの認識された文字の識別を、例えばＡＳＣＩＩコードで出力したり格納するための選択的な手段である。文字の識別は装置内に（ディスクメモリ内等に）格納され、または送信のためにモデム３３を介して遠隔ロケーションへ出力される。ＡＳＣＩＩコード等の文字の識別をファクシミリ互換性のある形式へと形式再変換するための手段を設けることも可能で、ファクシミリ３４を起動することなく、モデム３３を通じて離れて位置するファクシミリ装置へ送信することができる。
【００３１】
プリンタ／表示装置２４は、文字認識のいずれかのステップのための恒久的な記録を出力及び形成するだけではなく、文字認識処理の過程を監視するための手段である。キーボード１５は、オペレータが図３の装置の操作を制御するためのものである。
【００３２】
図４は本実施例によるブロック選択技術が有益に使用される１方法を理解するのに役立つ、全体的な文字認識処理を示すフローチャートである。図４の処理ステップは、プログラムＲＯＭ３５に格納されたコンピュータプログラムに従ってＣＰＵ３０により実行される。
【００３３】
ステップＳ４０１では、画素画像データが装置へ入力されＲＡＭ３２へ格納される。画像データは画像を画素単位で表現している。好ましくは、画素データは２値画素データ、つまり白黒画像データである。しかし、画像データは、各画素が複数のグレイスケールレベルの内の１つで表現される中間調画像データであってもよいし、各画素が、その色を符号化するマルチビットワードで表現されるカラー画像データであってもよい。それらの場合または画素データが２値画素データではない他のいずれの場合でも、ＲＡＭ３２へ格納する前に、非２値画素データを２値画素データへ変換するための閾値処理が行なわれる。
【００３４】
好ましくは、ステップＳ４０１で入力された画素画像データはポートレートタイプの画像、つまり左上隅から右下隅まで読んだ画像である。もし画像がその様に構成されてない場合、例えば、ランドスケープタイプの画像である場合、画素画像データは、ポートレートタイプの画像を表現する様に翻訳される。翻訳は、画像データを翻訳することを命じる、キーボード１５を介したオペレータ入力の命令に従って行なわれる。
【００３５】
ステップＳ４０２では、画像データが前処理される。通常、劣化した文字や画像を向上させること等により画像データを補強する様に前処理フィルタが使用される。適切な画像補強技術は、同出願人による、１９９１年１０月４日出願の審査中の米国特許出願第０７／７７１、２２０号で説明されている。
【００３６】
ステップＳ４０２で、必要であれば、認識処理の速度を上げるために、可能な程度に精度とコストを落として、画素画像データの画素数を減らすか、圧縮を行なってもよい。例えば、ｍ×ｎブロックの画素（ｍとｎは異なる）の画素値を平均して、そのｍ×ｎブロックの平均値の単一の画素に変換することを行ってもよい。
【００３７】
ステップＳ４０３では、画像の各セグメントにおける画像データのタイプを特徴付け、テキスト情報、グラフィックス情報、ライン画像情報、写真情報等の情報のブロックを指定して識別するために、ブロック選択が行なわれる。さらに、ステップＳ４０３のブロック選択では、画像の各部分が、後述のステップＳ４１２で説明される様な適切な順序に再構成される様に、階層的ツリー構造への画像の配置も行なわれる。例えば、階層的ツリー構造には、２つの欄の画像データが、欄１よりのテキストが欄２よりのテキストへ読み込まれるのを防止する様に、欄１のテキストを欄２のテキストに先行して再構成する情報が含まれている。ステップＳ４０３によるブロック選択を以下に詳細に説明する。
【００３８】
最初の情報のブロックがＲＡＭ３２に格納された画像から選択され、ステップＳ４０４では、それがステップＳ４０３で決定されたブロック識別に基づいてテキストブロックか否かが決定される。その最初のブロックがテキストブロックではない場合、ステップＳ４０５へ進み、次のブロックが選択されて、ステップＳ４０４へ戻る。
【００３９】
ステップＳ４０４で、ブロックがテキストブロックである場合はステップＳ４０６へ進み、テキストブロックに対しライン分割が行なわれる。ライン分割では、テキストブロックにおけるテキストの個々のラインがテキストブロックのテキストの他のラインから分割されて、分割されたラインは、次に詳細に説明される様に順次処理される。
【００４０】
ステップＳ４０７では、あるラインの各文字が、そのラインの他の文字から切り離しあるいは分割され、個々の文字が次に詳細に説明される認識処理ルーティンに提供される。
【００４１】
ステップＳ４０８において、各文字に対して認識処理が文字単位で行なわれ、各文字は、文字ディクショナリ３６に格納された標準文字と公知の技術で比較される。文字ディクショナリ３６のエントリは、通常単一の文字に対するものであるが、ある文字の連続は切り分けるのが困難であり（例えば「ｆｉ」）、また単一の文字も時折不用意に切れるので（例えば「ｊ」）、文字ディクショナリは一文字以外の他のエントリも有している。得に、ディクショナリは切り離しが困難な接触文字の組のためのエントリを有している。さらに、ティクショナリはしばしば不用意に切れる文字の部分のためのエントリも有している。
【００４２】
比較に基づいて、文字画像に対してある識別が選択されて、ＲＡＭ３２へ格納されるか、または出力装置３７へ出力される。また、所望により、識別された文字をプリンタ／表示装置２４上で表示してもよい。
【００４３】
ステップＳ４０９では、テキストブロックに対する処理が完了したかどうかを判定する。処理が完了していない場合は、ステップＳ４０６（または、ステップＳ４０７が適切ならばステップＳ４０７）へ戻り、更なるライン分割または文字分割処理を行なう。ブロック処理が完了すると、ステップＳ４１０へ進んで、ページに対する処理が完了したかどうかを判定する。ページの処理が完了していない場合は、ステップＳ４０５へ戻り、そこで同じページの次のブロックが処理のために選択される。
【００４４】
ページの処理が完了すると、ステップＳ４１０からＳ４１１へ進み、後処理が行なわれる。後処理にはコンテクストチェッキングやスペルチェッキング等の技術が含まれ、ステップＳ４０８において実行された処理の様に個々の文字に基づくよりはむしろ、それらの文字の識別が生じるコンテクスト（全体的観点）に基づいて、ステップＳ４０８の認識処理で認識された文字の識別結果が修正される。
【００４５】
ステップＳ４１２では、画像データはブロック選択ステップＳ４０３で規定されたツリー構造に基づいて再構成される。ページ再構成により、画像データは、適切な順序に変換される。例えば、脚注は本文テキストから切り離され、欄は他の欄と混合されるというよりは、むしろその欄の後へと続き、グラフィックまたは線画データはページの認識された文字テキストにおける適切な位置へ挿入される。
【００４６】
上述のグラフィック画像または線画像に関連する説明文（caption）はそれらの画像に隣接して挿入される。他のルールも適用可能である。例えば、ページの物理的再構成は必要ではない場合に、ページからテキストを抽出するために再構成を行なう、ということも可能である。
【００４７】
ステップＳ４１３では、再構成されたページは例えば出力装置３７に格納される。そして、ＲＯＭ３５に格納された他のアプリケーションプログラムに従い、ＣＰＵ３０により実行される形で、スプレッドシートやワードプロセッシング等の情報処理が行なわれる。続いて、処理された情報（または必要であれば処理を行なっていない情報）は、様々な手段により、例えばファクシミリ３４、モデム３５、またはコンピュータテキストファイルを音声再生するスピーチ合成装置による通常の音声電話機により、再送信される。
【００４８】
図５は図４のステップＳ４０３におけるブロック選択処理を説明するための全体的なフローチャートである。ただし、ブロック選択処理は文字認識システムとは別に使用される。例えば、画像再生機器において、あるタイプのブロックに用いられる第１の画像再生方法を生じ、次のタイプのブロックに用いられる第２の画像再生方法を生じるため、またはデータ圧縮方式におけるブロック選択を使用するために、ブロック選択処理を用いることが可能である。
【００４９】
ステップＳ５０では、ブロック選択処理速度を上げることが必要であれば、画像補強及び／またはデータ縮小を行なうことができる。データ縮小が行なわれると、ブロック選択は縮小された画像に対して行なわれる。しかし、図４の文字認識処理（つまりステップＳ４０４〜Ｓ４１３）に影響を与えない様に、ブロック選択処理の終了時点で、選択されたブロックは縮小されていない画素画像データに対して適用される。
【００５０】
画像データ縮小はｍ×ｍ画素ブロック毎に黒画素の連続性を評価することにより進められる。例えば、３×３画素のブロックにおいて２つの連続する黒画素が存在すれば、その３×３画素ブロックは単一の黒画素に縮小される。逆に、３×３画素ブロックに２つの連続する黒画素が存在しなければ、その３×３画素ブロックは単一の白画素に縮小される。好ましくは、４×４画素ブロックの黒画素の評価が行なわれる。この原理は原画像の連続性を保持するためのものである。
【００５１】
ステップＳ５１では、画素画像が分析された、連続成分が検出され、その大きさ及び他の連続成分との相対的位置に基づいて、検出された連続成分が分類される。連続成分は白画素によって完全に囲まれた黒画素のグループである。従って、連続成分は、少なくとも１つの白画素によって他の黒画素のグループから分離された黒画素のグループである。図６を参照して詳細に後述するが、ステップＳ５１では連続成分（各画素を囲む８方向の内いずれかで連続した成分）の検出が行なわれる。ステップＳ５２では、連続成分から得られたサイズ情報及びある統計上の値（下記に詳説する）に基づいて、各連続成分に分類が割り当てられる。詳細は後述するが、各連続成分はテキストユニットまたは非テキストユニットとして分類される。ステップＳ５３において、非テキストユニットは更なる分類に掛けられ、フレームデータか、中間調画像か、線画か、表かまたは他のテーブル状の構造のテキストデータか、垂直線か、水平線か、垂直または水平な斜線であるか、または未知の分類に相当するかどうかが、その厚さや黒画素の割合に基づいて判定される。連続成分の組織的データを提供し、ステップＳ４１２で前述した様にデジタルデータの再構成を助成するために、各連続成分に対して階層ツリー構造が展開される。
【００５２】
ステップＳ５４では、非テキスト連続成分のエッジに沿って不可視線（白線）がサーチされる。このような不可視線を使用する理由は、テキスト欄の間の距離が、同じページの大抵の欄の隙間よりも例外的に狭いものがあるためである。こうした不可視線の検出は、後で隣接するテキスト連続成分が実際は同じブロック内にグループ分けされるべきかどうかを判定するのに役立つ。
【００５３】
ステップＳ５５では、ステップＳ５１で分類することができなかった非テキストユニットが分析されて、大きいフォントサイズのタイトルであるかどうかが判定される。タイトルである場合は、ユニットは適切に再指定されて、ツリー構造が更新される。タイトルはステップＳ４１２におけるページ再構成に役立つものである。未知の非テキスト及びステップＳ５２、Ｓ５３で識別されたテキスト成分をグループ化することにより、水平または垂直方向にタイトルラインが形成される。このグループ化の前に、グループ化されると想定される成分の間の距離と、タイトルが水平または垂直である場合に可能なタイトルの長さとに基づいて、グループ化の方向が決定される。
【００５４】
ステップＳ５６では、後述するが、テキストブロックがテキスト連続成分から形成される。ステップＳ５７では、形成されたテキストブロックを可視線または不可視線が横切っていた場合、テキストブロックは分割される。これらの線を使用する理由は、極端に狭い欄間の隙間のためだけではなく、異なるブロックのテキスト連続成分の間の距離が、斜めの場合に、特に不可視または可視線がそれらを分けている場合に、それらの成分が１グループにするのに十分に短くできるためである。
【００５５】
ステップＳ５８では、各テキストブロックの方向が検出される。この様に、本実施例によれば、テキストブロックが形成される前には歪み検出も画像回転も行なわれることはない。こうして、一般のブロック選択アルゴリズムとは異なり、本実施例は予め歪み検出や画像回転を行なうことなく、ページ画像に直接テキストブロックを形成する。これにより、画像回転に費やされる時間が節約され、歪み検出による不正確さを避けることができる。さらに、ある特殊な視覚効果を達成するために、同じページのテキスト領域の幾つかを、特別に斜めに編集することも可能である。こうした場合、歪み検出及び画像回転は、ページ画像を直立スタイルに修正するのに役立つことになる。こうして、本実施例によれば、テキスト及び非テキストブロックは、スキャンされたページの歪みに係わり無くサーチされる。テキストブロックが形成された後、各テキストブロックの歪み方向が個別に識別される。
【００５６】
ステップＳ５９では、テキストブロックの方向に基づいて、各テキストブロックのテキストラインが形成される。ステップＳ６０では、テキスト及び非テキストブロック表現をより簡潔で明瞭にするために後処理が行なわれる。例えば、以前のブロック選択アルゴリズムは四角形で表現されたテキストブロックを形成するものであった。しかし、歪んだ文書の場合、そうした四角形ではテキストブロックの分離が不明瞭になる。テキストブロックの四角形領域が重なる場合にテキストブロック間の分離を明白にするために、本実施例では各テキストブロックをより簡潔に囲む不規則な形状の曲線を提供するものである。この曲線による囲みは表示効果を補強するだけではなく、ブロック画像の抽出にも有効である。テキストブロックを囲む不規則形状の曲線は、テキストブロック形成ステップＳ５６でテキストブロックが新たに形成または更新される度に形成することができる。
【００５７】
図６Ａ、図６Ｂ、図６Ｃ、図６Ｄは、上述のステップＳ５１〜Ｓ５３の処理を詳細に示すフローチャートである。このフローチャートには、画素画像データの連続成分がどの様にして検出されるか、またそれらの連続成分がどの様にして分類されるかが示されている。図６Ａ〜図６Ｄの各処理ステップは、プログラムＲＯＭ３５に格納されたプログラムステップに従ってＣＰＵ３０により実行されるものである。
【００５８】
ステップＳ６０１では、輪郭トレーシングにより画素画像データの連続成分が検出される。輪郭トレーシングは図７Ａに示す様な画像データをスキャンすることにより行なわれる。スキャニングは矢印Ａで示される様に画像の右下部から左へと進み、画像の右の境界に到達するまで続く。スキャニングは、例えば左上から右下へ向けたり、他の方向へも行なうことができる。黒画素があると、隣接する画素が符号７１で示される様な放射状のパターンになった順序で調べられ、黒画素の隣接画素も黒画素であるかどうかが判定される。放射状パターン７１は共通の中心から延びる８つの番号の付いたベクトルを持つので、以下この輪郭トレーシングは「８方向」トレーシングと称される。隣接する黒画素が見つかると、処理は上述の様に画像の外郭のトレースが終わるまで進められる。こうして、図７Ｂに示す様に、矢印Ａの方向のスキャニングは文字「Ｑ」の尾の部分に対応する点７２を突き止める。隣接画素の捜査は、文字「Ｑ」の外郭がトレースされてしまう様に、放射状パターン７１に従って進められる。閉じた輪郭の内側の部分はトレースが行なわれない。
【００５９】
１つの連続成分が検出され、その輪郭が８方向トレーシングによりトレースされた後、スキャニングは次の黒画素が見つかるまで進められる。こうして、例えば、完全に黒く塗りつぶされた領域を表すオブジェクト７４が８方向トレースされる。同様に、単語「non-text」を示す手書き文字の非テキストオブジェクト７５が、単語「text」を形成する個々の文字からなるテキストオブジェクト７６における個々の単語と同様にトレースされる。図７Ａに示すスキャニングは画素データの全ての連続成分が検出されてその輪郭が８方向トレースされるまで続けられる。
【００６０】
そして、ステップＳ６０２に進み、各連続成分が四角形化される。詳しくは、各連続成分の周りに最小の可能な四角形が描かれる。こうして、図７Ｂに示す様に、四角形７７がオブジェクト７２の周りに、四角形７９がオブジェクト７４の周りに、四角形８０がオブジェクト７５の周りに、そして四角形８１ａ、８１ｂ、８１ｃ、８１ｄがテキストオブジェクト７６ａ、７６ｂ、７６ｃ、７６ｄの周りに夫々描かれる。
【００６１】
ステップＳ６０３では、ツリーの位置が各四角形に割り当てられる。殆どの部分について、ステップＳ６０３で得られたツリー構造は画素画像における各オブジェクトに対し直接ツリーの根から進んでいる。これは、連続成分の外郭のみがトレースされ、閉じた輪郭の内側の部分はトレースされないためである。この様に、図７Ｃに示す様に、連続成分７２に相当する四角形７７はページの根から直接進んでいる。しかし、非テキストオブジェクト７５に相当する四角形８０や、テキストオブジェクト７６ａ、７６ｂに相当する四角形８１ａ、８１ｂの様な、その四角形が他の連続成分の四角形の中にすっかり収まっている連続成分については、そうした連続成分を囲んでいる成分（この場合成分７４）からの末裔として指定されている。さらに、少なくとも１つの枝分れ成分を持つ各連続成分については、その成分自身からの「主末裔成分」として指定されている。この様に、成分７９は他の末裔成分８０、８１ａ、８１ｂの中に自身７９からの主末裔成分として指定されている。
【００６２】
ステップＳ６０４では、ツリーの最初のレベルにある連続成分が、テキストユニットまたは非テキストユニットに分類される。分類は２つのステップで進む。最初のステップでは、連続成分の四角形が所定の大きさの閾値と比較される。連続成分を囲む四角形の高さ及び幅が最大フォントサイズに相当する第１の所定閾値より大きい場合、連続成分は非テキストユニットと分類されて「非テキスト」属性がユニットに与えられる。
【００６３】
第２のステップでは、全てのユニット、つまりまだ非テキストとして分類されていないユニットが、残りの全ての連続成分の集合的なサイズに基づいて適応的に決定された閾値と比較される。詳しくは、非テキストの指定がされていない全ての四角形のうちで通常のテキストサイズの大きい方（１２ｐｔ）及び中間のサイズ（中間の高さと中間の幅のうち小さい方の四角形が選択される。選択された値はスカラーで乗算され（説明の都合で、１．５として選択されている）、高さ及び幅について適応的に決定された閾値とされる。決定された閾値より大きい全てのユニットは非テキストであると推定され、その様に分類される。一方、適応的に決定された閾値のいずれかより小さく所定のテキスト特性に合うユニットはテキストと推定される。ユニットはこの様に分類され適切な属性が与えられる。これらの分類は図６Ａ〜図６Ｄの残りで述べられる様な精密な分類であり、下記により詳細に説明する。
【００６４】
ツリーの第１のレベルの各ユニットがテキストまたは非テキストとして分類された後、テキストユニットの主末裔成分を含む全ての末裔成分がテキストユニットとして分類される。非テキストユニットの主末裔成分は非テキストとして分類されるが、非テキストユニットの他の末裔成分はテキストユニットとして分類される。
【００６５】
ステップＳ６０６では、最初のユニットが選択される。ステップＳ６０６で、そのユニットがテキストユニットである場合は、ステップＳ６０７へ進んで次のユニットが選択される。非テキストユニットが選択されるまでステップＳ６０６〜Ｓ６０７が繰り返され、非テキストユニットが選択された時点でステップＳ６０８へ進む。
【００６６】
ステップＳ６０８では、非テキストユニットが調べられ、そこからの末裔が存在するかどうかが判定される。例えば、図７Ｃに示す様に、非テキストユニット７９は非テキスト主末裔７９とテキスト末裔８０、８１ａ、８１ｂを含んでいる。
【００６７】
ステップＳ６０８において何らかの末裔が存在する場合、ステップＳ６０９へ進み、そのユニットがフィルタ処理され、そのユニットが中間調（またはグレイスケール）ユニットであるかどうか決定する。中間調フィルタリングでは、ユニットの末裔が調べられ、「ノイズサイズ」ユニットより小さいサイズの末裔の数が決定される。「ノイズサイズ」ユニットは、画像データについて予測された最小フォントサイズよりも小さい高さ及び幅を持つユニットである。ノイズサイズより小さいサイズの末裔の数が末裔の総数の過半数である時、ユニットは中間調画像であると判定される。従って、ステップＳ６１０よりＳ６１１へ進んで、「中間調」の属性が当該ユニットに与えられる。そしてステップＳ６０７へ戻り、処理のために次のユニットが選択される。
【００６８】
ステップＳ６０９の中間調フィルタリングでユニットが中間調画像ではないと判定されると、ステップＳ６１０からＳ６１３へ進んで、ユニットからの主末裔が更なる処理のために選択される。そしてステップＳ６１４へ戻る。
【００６９】
ステップＳ６０８で非テキストユニットに末裔が存在しないと判定されると、あるいはステップＳ６１３で主末裔が更なる処理のために選択されると、ステップＳ６１４でその主末裔にフレームフィルタリングが行なわれる。フレームフィルタリングは、問題のユニットがフレームであって、ユニットを囲む四角形の幅及び／または高さと夫々ほぼ等しい平行な水平線及び平行な垂直線を含んでいるかどうかを判定する様に設計される。特に、連続成分が調べられて、画素の各列について、ユニット内の連続成分の内側の部分をつなぐ最長の距離が決定される。こうして、図８Ａに示す様に、非テキストユニット８２は連続成分８３を含み、その輪郭は８４で示される様に８方向トレースされている。列「ｉ」については、連続成分の内部をつなぐ最長距離は輪郭の左の境界８５ａから右の境界８５ｂまでの距離Ｘiである。一方、列「ｊ」については、連続成分の内部をつなぐ２つの距離が存在する。つまり連続成分の境界上の点８６ａ、８６ｂ間の距離と、点８７ａ、８７ｂ間の距離である。点８６ａ、８６ｂ間の距離の方が点８７ａ、８７ｂ間の距離よりも長いため、距離Ｘiは列ｊに関する連続成分の内部をつなぐ最長距離である。
【００７０】
非テキストユニット８２におけるｎ個の列の各々について、「ｘ」距離が求められ、非テキストユニットがフレームであるかどうかを判定するために次の不等式がテストされる。
【００７１】
【数１】
0003754716.tif 000002
【００７２】
ここでＸkはｋ番目の列に関し連続成分の内部をつなぐ最長の距離であり（上記の通りである）、Ｗは四角形ユニット８２の幅であり、Ｎは列数であり、そしてたとえ画像においてフレームが歪んでいたり斜になっていてもフレームの検出ができる様に、閾値が予め算出されている。１°の歪みまたは傾斜角度を許容するためには、「ｓｉｎ（１°）×Ｌ＋ステップＳ６０４で計算された平均テキスト高さに等しいオフセット」で満足な結果が得られることがわかる。
【００７３】
上記の不等式が満足された場合、ユニットはフレームデータと判定され、ステップＳ６１５からＳ６１６へと進み、「フレーム」属性が当該ユニットに与えられる。
【００７４】
ステップＳ６１６の後、フレームデータが表またはテーブル状に組織されたデータを含んでいる可能性を検討する。こうして、ステップＳ６１７（図６Ｂ）で、連続成分の内部が調べられて白輪郭が得られる。
【００７５】
白輪郭はステップＳ６０１で検出された輪郭と同様であるが、黒画素よりも白画素が調べられる。こうして、図９Ａに示す様に、非テキストユニットの内部が、矢印Ｂの方向に右下部から左上に向けてスキャンされる。最初の白画素が見つかると、その隣接画素が放射状パターン９１に示される順序で調べられる。ただし、放射状パターン９１は１から４まで番号が付けられたベクトルを有している。従って、このステップに従った白輪郭トレーシングは以下「４方向」白輪郭トレーシングと称される。白輪郭トレーシングは、黒画素に囲まれた全ての白輪郭がトレースされるまで４方向に行なわれる。例えば、白輪郭トレーシングは、９６で示される、一般に指定された黒画素の様な、内部の他の黒画素に加えて黒画素セグメント９２、９３、９４、９５の内部輪郭を形成している画素に続くものである。白輪郭が見つかる度に、非テキストオブジェクトに囲まれた全ての白輪郭がトレースされるまで、スキャニングが上述の様に矢印Ｂの方向に進められる。
【００７６】
ステップＳ６１８では、非テキストユニットの密度が計算される。密度は、連続成分の黒画素数を数えて、その黒画素数を四角形に囲まれた画素の総数で除算することにより求められる。
【００７７】
ステップＳ６１９では、非テキストユニット内で見つかった白輪郭の数が調べられる。白輪郭数が４以上の場合は、非テキストユニットは実際は、表またはテーブル状に配置されたテキストブロックの連続である可能性がある。従って、ステップＳ６２０（図６Ｄ）で、白輪郭フィリング率が決定される。白輪郭フィリング率は、白輪郭が非テキスト画像で囲まれた領域を埋める度合いである。図９Ａに示す様に、白輪郭フィリング率は、黒画素が見つかる白空間である１００や１０１の様な領域に加えて、完全に空白の空間である９７や９９の様な斜線領域を含んでいる。フィリング率が高いと、非テキスト画像が表またはテーブル状に配されたテキストデータのシーケンスである可能性がある。従って、ステップＳ６２１でフィリング率が調べられる。フィリング率が高いと、非テキスト画像が表またはテーブル状に配されたテキストデータのシーケンスである可能性がある。この判定の信頼度を増すためには、白輪郭が調べられて、それらが水平及び垂直に拡がるグリッド状の構造を形成しているかどうかが判定される。詳しくは、ステップＳ６２２では、非グリッド配列の白輪郭は、その境界が少なくとも２つの輪郭を横切って水平及び垂直に延びていない場合は再結合される。例えば、図９Ａに示す様に、白輪郭９９の左の境界１０２と右の境界１０３は、白輪郭１００の左の境界１０４と右の境界１０５に一致する様に垂直に拡がっている。従って、これらの白輪郭はグリッド構造に配置されているので、これらの白輪郭は再結合されない。同様に、白輪郭１０３の上部の境界１０６と下部の境界１０７は、白輪郭１１０の上部の境界１０８と下部の境界１０９に一致する様に水平に拡がっている。従って、これらの白輪郭はグリッド状構造に配置されているので、これらの白輪郭は再結合されない。
【００７８】
図９Ｂ〜図９Ｃは、白輪郭が結合される状態を説明するための図である。図９Ｂは、例えば、ステップＳ４０１において前述した様に中間調画像を２値画像に変換する閾値計算を通じて形成される、非テキストユニット１１１を示している。非テキスト画像１１１は、白領域１１４、１１５、１１６、１１７、１１８、１１９に加えて黒領域１１２を含んでいる。推定上、これらの白領域のフィリング率は、ステップＳ６２１から再結合ステップＳ６２２へ進める様に、十分に高くなっている。最初に、図９Ｂに示す様に、白輪郭１１５の上下境界が白輪郭１１７の上下境界と比較される。これらの上下境界は一致しないので、図９Ｃに示す様に白輪郭１１５は白輪郭１１６と再結合されて、結合された白輪郭１１６’を生成する。図９Ｃにおいて、白輪郭１１７の左右境界が白輪郭１１８の左右境界と比較される。これらの境界は同じではないため、図９Ｄに示す様に、白輪郭１１７と１１９は単一の白輪郭１１７’に再結合される。
【００７９】
再結合が生じなくなるまで、この処理が水平及び垂直に反復される。
【００８０】
こうして、上述した様に、表に関する白輪郭は再結合される可能性が低く、非テーブルの白輪郭、例えば中間調画像または線画は再結合される可能性がより高い。従って、ステップＳ６２３で、再結合率が調べられる。再結合率が高い場合、またはステップＳ６２１でフィリング率が低い場合、非テキストフレームユニットは斜線、未知の画像（an unknown）、中間調画像または線画である可能性があり、ステップＳ６２８へ進んで非テキストユニットは表ではないとの指定がされて、後述のステップＳ６４２Ａ（図６Ｂ）へ進む。
【００８１】
ステップＳ６２３で再結合率が高くない場合は、ステップＳ６２４へ進み、非テキスト画像は「表類」として指定される。ステップＳ６２５では、８方向に連続成分を検出して分類する様に、新たに指定された表の内部が調べられる。ステップＳ６２６では、新しい内部の連続成分に基づいて、階層構造が更新される。ステップ６２７では、内部の連続成分はテキストまたは非テキストとして再分類され、ステップＳ６０２〜Ｓ６０４で前述した様に、適切な属性が与えられる。ステップＳ６２７の後、表内部のテキスト連続成分が線描画、中間調画、または未知の画であるかがサイズ、密度等に基づいて更に分類される。フレーム内部の非テキスト連続成分及び線描画内部の非テキスト連続成分も、ステップＳ６０８以降に説明した様に、更に分類される。
【００８２】
ステップＳ６２１、Ｓ６２３において、ステップＳ６２１でフィリング率が高くない場合、またはステップＳ６２３で再結合率が高い場合は、非テキストフレームユニットは斜線、未知の画像、中間調画像または線画、つまり表ではない可能性がある。
【００８３】
ステップＳ６１９において、白輪郭の数が４より少なければ、フレームユニットは表ではないと考えられる。従って、ステップＳ６４２Ａへ進んで、フレーム及び密度が約０．５に等しい閾値より小さいかどうかが判定される。閾値は、フレーム内部のテキストユニットまたは線画が画素の半分より少ないとの推測に基づいて選択されたものである。フレーム及び密度が閾値より小さい場合、上述のステップＳ６２５〜Ｓ６２７へ戻り、その後、ステップＳ６０７へ進んで、次のユニットの選択が行なわれる。
【００８４】
ステップＳ６４２Ａにおいて、フレーム及び密度が所定の閾値より小さい場合、ステップＳ６４２へ進み、フレームユニットが線画または中間調画像に分類できるかどうか、あるいはフレームは分類できないか（つまり、フレームは「未知の画像」である）どうかが、より詳細に後述される様に決定される。
【００８５】
ステップＳ６１５（図６Ａ）に戻って、ステップＳ６１４におけるフレームフィルタリングで非テキストユニット内のフレームが検出されなかった場合、ステップＳ６３５（図６Ｂ）へ進み、非テキストユニットがラインを含んでいるかどうかが判定される。ラインはテキスト境界を表す有用な非テキストユニットである。しかし、そうしたラインにより境界が引かれているテキストは、しばしばラインと近接しているため、そのテキストをラインに結びつけることが可能である。従って、テキストが近接した、またはテキストが近接していないラインを検出する様に、ライン検出が指定される。
【００８６】
ラインを単独で検出するためには、ユニットの長さ方向で非テキストユニットのヒストグラムが計算される。図８Ｂに示す様に、あるラインのヒストグラム８８は、ライン幅にほぼ等しい高さの、明らかに均一な分配を示している。ラインの幅は非テキストユニットの幅（Ｗ）にほぼ等しい。いずれの差異も、画素画像が形成される時に原稿文書が歪んでいた場合に結果として生じる傾斜角度θsによるものである。従って、非テキストユニットがラインを含んでいるかどうかを判定するためには、ヒストグラムにおける各ｃｅｌｌkが、非テキストユニットの幅Ｗと比較される。次に示す様に、これらの値の二乗平均の平方根の差が、閾値と比較される。
【００８７】
【数２】
0003754716.tif 000003
【００８８】
閾値は、非テキストユニット内のラインの歪みまたは傾斜角度θsを許容するために算出されるものである。１°の歪みまたは傾斜角度に対しては、
【００８９】
【数３】
0003754716.tif 000004
【００９０】
の閾値で満足な結果が得られることがわかる。
【００９１】
上記の式に従って近接物の無いラインが見つからない場合、そのユニットがテキスト近接ラインを含んでいるかどうかが判定される。テキスト近接ラインが非テキストユニットに含まれているかどうかを判定するにために、テキストユニットが調べられて、あるラインがユニット境界に沿って縦に延びているかどうかが判定される。詳しくは、もしあるラインがユニットの縦方向に延びていれば、図８Ｃに示す様に、ユニットを囲む四角形の境界がそのラインの非常に近くにあるということになる。従って、四角形の境界内にある最初の複数の黒画素における均一性が、境界からの距離の二乗の数の合計を計算することによって調べられる。このように、図８Ｃを参照すると、次の不等式がテストされる。
【００９２】
【数４】
0003754716.tif 000005
【００９３】
二乗の合計が所定の閾値より小さければ、テキストが接着したラインが見つかったことになる。接着物の無いラインに対して得られた閾値と同じ閾値で、満足する結果を得ることができる。
【００９４】
ステップＳ６３５でラインが検出されると、ステップＳ６３６からＳ６３７Ａへ進んで、「ライン」の属性が非テキストユニットに与えられる。そしてステップＳ６０７（図６Ａ）へ戻り、次のユニットが選択される。
【００９５】
一方、ステップＳ６３５でラインが検出されない場合、ステップＳ６３６からＳ６３７へ進んで、非テキストユニットの大きさが調べられる。サイズが所定の閾値より大きくなければ、非テキストユニットの分類は決定できない。閾値は最大フォントサイズ及び文書タイプ（水平、垂直、または両者混合）によって設定される。最大フォントサイズの半分だと満足な結果が得られる。従って、ステップＳ６３８へ進んで「未知」の属性が非テキストユニットに与えられ、ステップＳ６０７（図６Ａ）へ戻って、次のユニットが選択される。
【００９６】
ステップＳ６３７でサイズが所定閾値より大きければ、ステップＳ６１７、Ｓ６１８、Ｓ６１９へ進み、前述の様に、非テキストユニットの内部の白輪郭がトレースされ、非テキストユニットの密度が計算され、白輪郭数が調べられる。
【００９７】
ステップＳ６１９で白輪郭数が４より大きくなければ、上述の様にステップＳ６４２Ａ、Ｓ６４２へ進む。ステップＳ６４２ではユニットのサイズが計算されて、線画または中間調画像を構成できる程大きいかどうかが判定される。このサイズ判定は、黒画素の最大ランレングスに加えて、非テキストユニットの高さ及び幅と文書タイプ、に基づいて行なわれる。例えば、非テキストユニットの高さ及び幅が最大フォントサイズより大きくない場合は、その非テキストユニットは中間調画像または線画になる程大きくはないため、ステップＳ６４３へ進み、「未知」の属性が与えられる。さらに、非テキストユニットの幅は最大フォントサイズより大きいが黒画素の最大ランレングスは最大フォントサイズより大きくない場合も、ステップＳ６４３へ進み、「未知」の属性が与えられる。そしてステップＳ６０７（図６Ａ）へ戻り、新たなユニットが選択される。
【００９８】
ステップＳ６４２で、非テキストユニットが線画または中間調画像になる程大きい場合、ステップＳ６４３Ａへ進み、非テキストユニットが水平または垂直の傾斜したラインであるかどうかが判定される。その後、ステップＳ６４４へ進み、非テキストユニットが線画か中間調画像であるかが判定される。ユニットが線画として、または中間調画像として分類されるかどうかは、ユニット内の黒画素の平均水平ランレングス、ユニット内の白画素の平均水平ランレングス、白画素対黒画素の比、及び密度に基づいて判定される。一般に、非常に暗い画像は中間調画像と考えられ、明るい画像は線画と考えられる。
【００９９】
詳しくは、白画素の平均ランレングスがゼロにほぼ等しく（つまり、暗い部分が優勢または点描画の様な場合）、ステップＳ６１８で算出される様な密度が、ユニットが白より黒の方が強く（つまり、約１／２に等しい第１の閾値より密度が高い）、そして殆どの列が長い黒ランレングスを含んでいることを示す場合は、フレームユニットは中間調画像であると判定される。密度が第１の閾値よりも高くない場合は、ユニットは線画であると判定される。
【０１００】
白画素の平均ランレングスがゼロにほぼ等しくはなく、白画素の平均ランレングスが黒画素の平均ランレングスより大きく、そして殆どの列に長い黒ランレングスが含まれていない場合は、フレームユニットは線画であると判定される。しかし、白画素の平均ランレングスが黒画素の平均ランレングスより大きくない（つまり、再び、暗い部分が優勢な画像である）場合、更なるテストが必要である。
【０１０１】
詳しくは、黒画素数が白画素数より大幅に少ない場合（つまり、白画素数で割った黒画素数が、２に等しい第２の閾値より大きい場合）、フレームユニットは中間調のユニットであると判定される。一方、白画素数で割った黒画素数は第２の閾値より大きくないが、ステップＳ６１８で求めた密度が第１の閾値より大きい場合は、ユニットは中間調画像であると判定される。そうでなければ、ユニットは線画であると判定される。
【０１０２】
従って、ステップＳ６４４でユニットが線画であると判定されると、ステップＳ６４５へ進み、「線画」の属性が与えられ、ステップＳ６４６で全ての末裔成分が現在の親成分から移動されて、２代前の親の直接の末裔とされる。詳しくは、一度ユニットが線画であると判定されると、文字認識のためにいずれのブロックも線画から選択されることはない。その後、ステップＳ６２５、Ｓ６２６、Ｓ６２７へ戻り、それからステップＳ６０７で次のユニットが選択される。
一方、ステップＳ６４４でユニットが線画ではないと判定されると、ステップＳ６４７へ進み、「中間調」の属性が与えられ、ステップＳ６４８で全ての末裔成分が現在の親成分から移動されて、２代前の親の直接の末裔とされる。そして、ステップＳ６０７へ戻り、次のユニットが選択される。
【０１０３】
本実施例は、上述のように判定された非テキストユニットに加えて、傾斜した垂直ライン及び水平ラインを、その厚さや完全性に基づいて識別する。
【０１０４】
ステップＳ５３に２つの付加的機能を取り入れることも可能である。詳しくは、テキスト文字が下線より分離されるような、ライン近接物分離機能の実行が可能である。２番目の機能としては、点線、破線、または装飾された線（直線でも斜線でも）の検出が実行可能である。
【０１０５】
ライン近接物分離機能は、テキスト（あるいは他のテキストのサイズの近接物）が、何らかの非テキスト成分（直線、水平線、フレーム等）に付随しているように見える所に取り入れることができる。例えば、テキスト文字が下に引かれた水平線に近接しているように見える場所では、テキスト文字がテキスト連続成分として特徴付けられ、ライン画素が非テキスト連続成分として検出される様に、テキスト文字をラインから切り離す必要がある。
【０１０６】
テキストとラインの近接状態を分離する方法は、まずそうした近接物の存在を検出することで実行される。ラインの場合、ラインの片側のエッジはスムーズであると判定され、しかし反対側のエッジはスムーズではないと判定された場合、そのスムーズでない方のエッジに何らかの付着物が存在している。フレームの場合、外郭のエッジのいずれかがスムーズでない場合、そうしたフレームエッジに何らかの付着物が存在していることになる。
【０１０７】
次に、付着されたライン（またはフレームのエッジ）の２つの端点が算出されるが、これらの２つの端点の位置は非スムーズ側の画像アウトラインに基づいている。そして、「分離線」が算出された２つの端点の間を通って形成され、付着物は分離線に沿った線から切り離される。付着物はラインから「分離線」に沿って切り離され、付着物とラインはそれぞれ処理されて、付着物がテキスト連続成分か非テキスト連続成分かが判定されるが、好ましい形では、分離された付着物はテキスト連続成分として分類される。
【０１０８】
点線、破線、また装飾された線の存在を検出する方法は、垂直線、水平線、水平斜線、垂直斜線のいずれかの属性を各検出された線に与えることで実行される。そうした非連続線を検出するために、水平及び／または垂直な小さいサイズの（ピリオドの大きさと同様である）テキスト連続成分が収集される。次に、収集された成分は、それらの相対的な距離に基づいて異なるグループに分配される。各グループについては、そのサイズが水平、垂直、または斜線として十分かどうかが判定される。十分でなければ、そのグループが点線であり得るかどうかがチェックされる。対象のグループがラインとして可能であれば、グループはサイズとグループ間の間隙の明瞭度とに基づいて再編成される。その後、グループは再びチェックされて点線であるかどうか判定される。
【０１０９】
グループの幅が垂直線と同様であって、対象のラインの周辺に垂直なラインが存在し、グループとラインの間の間隙が明瞭であれば、グループは垂直線と考えられる。そうでない場合は、グループの長さが水平線と同じであるか、周辺に水平なラインが存在し、グループとこのラインの間の間隙が明瞭であるかどうかが判定される。そうである場合には、検出された非連続ラインは水平線であると決定される。
【０１１０】
画素画像における全ての連続成分が検出され、図６（図５のステップＳ５３）で説明した様に分類されると、図１０に示されるような修正されたツリーが得られる。図示の様に、ツリーの根は画素画像データのページに相当する。根から出ているのはテキストブロック、内容の不明な非テキストブロック、フレーム、写真、及び線の分類である。フレームから出ているのはテキストブロック、未知の非テキストデータ、写真や線のテキストブロックを含む表である。
【０１１１】
図５に戻り、ステップＳ５３で全ての非テキスト連続成分が分類されると、ステップＳ５４では非テキスト連続成分のエッジに沿った不可視線（白線）がサーチされる。そうした不可視線は（ステップＳ５２で求められた不可視線も合わせて）、ステップＳ５７で、可視または不可視線がテキストブロックを横切っている場合に、テキストブロックを分離するのに使用される。この手順は後で詳細に説明する。
【０１１２】
ステップＳ５５で、ステップＳ５３で分類された未知の非テキスト連続成分を用いて、水平及び垂直タイトルラインが形成される。これらの未知の非テキスト連続成分は、グループと想定される成分間の距離と、タイトルが水平または垂直である場合に可能なタイトルな長さとに基づいて、名目上垂直、水平、または傾斜のタイトルの方向を検出するのに使用される。この方法を用いて、各タイトル連続成分が水平及び垂直方向の非常に近接したブロックと比較され、より近いブロックに水平または垂直タイトルが添付される。
【０１１３】
ステップＳ５６では、テキスト連続成分はテキストブロックを形成するのに用いられる。簡潔に述べると、各テキスト連続成分に対し、周辺にある近い水平及び垂直の成分がサーチされて、集成プロセスで、テキストブロックとしてグループ化される。プロセスを図１１に従って詳細に説明する。
【０１１４】
図１１において、ステップＳ５２で識別されたテキスト連続成分を用いて、ステップＳ５６１でＨ−ＧＡＰ及びＶ−ＧＡＰが計算される。これらはそれぞれ、隣接するテキスト連続成分間の水平及び垂直中央間隙部である。ステップＳ５６２では、全てのテキスト連続成分が、その垂直な位置によりソートされる。ステップＳ５６３では、現在のテキストブロックの形成が開始される。ステップＳ５６４では、ソート順に連続成分が抽出され、値Ｖ−ＤＩＳＴ及びＨ−ＤＩＳＴとが計算される。これらの値はそれぞれ、抽出された連続成分と現在のテキストブロックの間の垂直及び水平距離である。利用可能な連続成分が存在しなければ、ステップＳ５６３へ戻り、次のテキストブロックが形成される。
【０１１５】
ステップＳ５６５では、抽出された連続成分について、Ｖ−ＤＩＳＴがＶ−ＧＡＰより大きいかどうか、またはＨ−ＤＩＳＴがＨ−ＧＡＰより大きいかどうかが判定される。ステップＳ５６５でいずれかに該当すれば、抽出された連続成分は現在のテキストブロック内には存在しないことになるので、ステップＳ５６４へ戻り、ソート順に次の連続成分が抽出される。一方、ステップＳ５６５でいずれにも該当しない場合は、抽出された連続成分は現在のテキストブロック内に存在することになるので、ステップＳ５６６へ進む。
【０１１６】
ステップＳ５６６では、抽出された連続成分と、現在のテキストブロックに既に含まれている連続成分とが、所定の条件を満たすかどうかが判定される。好適な実施例では、所定条件は図１２に示される通りである。
【０１１７】
図１２において、ステップＳ５６６１では、抽出された連続成分が現在のテキストブロックに既に含まれている連続成分と比較される。ステップＳ５６６２では、値ｈ−ｄｉｓｔ及びｖ−ｄｉｓｔが計算される。これらの値はそれぞれ、抽出された連続成分とステップＳ５６６１で識別された１つの連続成分（テキストブロックに含まれている連続成分）との間の水平及び垂直距離を表している。
【０１１８】
ステップＳ５６６３では、ｖ−ｄｉｓｔがＶ−ＧＡＰより小さいかどうか、そしてｈ−ｄｉｓｔがＨ−ＧＡＰより小さいかどうかが判定される。ステップＳ５６６３の条件に該当しない場合は、テキストブロックに含まれている連続成分は抽出された連続成分に十分に近似していないことになるため、ステップＳ５６６１へ戻って、現在のテキストブロック内の次のテキスト連続成分が抽出された連続成分と比較される。
【０１１９】
ステップＳ５６６３で条件に該当すれば、ステップＳ５６６４へ進み、抽出された連続成分がテキストブロックに含まれている連続成分とどのような垂直関係にあるのかが判定される。３つの関係が可能である。つまり、（１）抽出された連続成分が垂直にテキストブロックに含まれている連続成分の上にある、（２）抽出された連続成分は垂直にテキストブロックに既に含まれている連続成分の上ではなく、水平方向にある、（３）抽出された連続成分は垂直にテキストブロックに既に含まれている連続成分の上ではなく、斜め下方向にある、という関係である。条件（１）が満たされる場合、ステップＳ５６６５へ進むが、条件（２）または（３）が満たされる場合は、ステップＳ５６６７へ進む。
【０１２０】
ステップＳ５６６５では、現在のテキストブロック内に、抽出された連続成分に近い他の連続成分が存在するかどうかが判定される。これは、ｈ−ｄｉｓｔがＷ−ＧＡＰより小さいかどうか（Ｗ−ＧＡＰはＨ−ＧＡＰより僅かに広い）を判定することにより確認される。該当しない場合は、ステップＳ５６６１へ戻って、現在のテキストブロック内の次の連続成分を用いて比較を行なう。しかし、ステップＳ５６６５において該当する場合は、ステップＳ５６６７へ進み、何らかの線描オブジェクト（例えば、ライン、線描画等）が抽出された連続成分とテキストブロックに含まれている連続成分の間に存在するかどうかが判定される。そのような線描オブジェクトが存在する場合は、ステップＳ５６４へ戻り、次の連続成分がパート順に抽出される。しかし、ステップＳ５６６７でそうしたオブジェクトが存在しないと判定された場合は、図１１のステップＳ５６７へ戻る。
【０１２１】
図１１に戻り、ステップＳ５６７では、ちょうど処理されたばかりの、抽出された連続成分が、ステップＳ５２で識別された最後のテキスト連続成分であるかどうかが判定される。抽出された連続成分が最後の成分でない場合は、ステップＳ５６８で、その連続成分は現在のテキストブロックに挿入され、ステップＳ５６４へ戻って、ソート順に次の連続成分が抽出される。一方、ステップＳ５６７で最後の連続成分と判定された場合は、その成分は現在のテキストブロックに既に挿入されているので、図５のステップＳ５７へ戻る。
【０１２２】
図５に戻って、ステップＳ５７では、ステップＳ５６で形成されたテキストブロックが単一のテキストブロックであるかどうか、または形成されたテキストブロックを横切る可視線または不可視線により、複数のテキストブロックに分割されるべきであるかどうかが判定される。例えば、図１３Ａはテキストブロック１３１を示し、テキストブロック１３１内には複数の連続成分１３２が配されている。テキストブロックに隣接するのは非テキストブロック１３３、１３４である。非テキストブロックの間にはステップＳ５４で述べた不可視（白）線が存在している。例えば、非テキストブロック１３３、１３４が各々写真を含み、ブロックの間に不可視線が引かれている場合は、非テキストブロック１３３に隣接するテキスト連続成分は非テキストブロック１３３にのみ関係し、非テキストブロック１３４に隣接するテキスト連続成分は非テキストブロック１３４にのみ関係している。ステップＳ５７で形成されたテキストブロック１３１が単一のテキストブロックである場合は、後に行なわれる文字認識処理で、非テキストブロック１３３、１３４を文字として誤認識する可能性がある。
【０１２３】
図１３Ｂに示すように、不可視線１３５（または可視線）が先に形成されたテキストブロック１３１を横切っている場合において、テキストブロックは２つのテキストブロック１３６、１３７に分割される。そして、非テキストブロック１３３、１３４のそれぞれのテキスト連続成分が適切に処理される。ステップＳ５７の後、ステップＳ５８へ進み、各テキストブロックの方向が検出される。テキストブロックの方向の検出は、テキストブロック内のテキスト連続成分の長さ及び幅、連続成分間の水平及び垂直の間隙、及びそれらの位置に依存して行なわれる。図１４Ａ、及び、図１４Ｂは、この処理を詳細に説明したフローチャートである。
【０１２４】
図１４Ａにおいて、まずステップＳ５８０１で、ステップＳ５６で形成されたテキストブロック内の全てのテキスト成分について、様々な値が計算される。ただし、幅は水平寸法に相当し、長さは垂直寸法に相当するものである。値ＭＡＸ−ＬＥＮ及びＭＡＸ−ＷＩＤが計算されるが、これらはそれぞれ、テキストブロック内のテキスト連続成分間の最長の長さ及び最大の幅を表している。また値ＡＶＧ−ＬＥＮ及びＡＶＧ−ＷＩＤが計算されるが、これらはそれぞれ、テキストブロック内の全ての連続成分の平均の長さと幅を表している。最後に、値ＳＴＤ−ＬＥＮ及びＳＴＤ−ＷＩＤが計算されるが、これらはそれぞれ、テキストブロック内の全ての連続成分の長さ及び幅の標準的な偏差を表している。
【０１２５】
その後、複数の処理ステップが実行されてテキストブロックが水平テキストブロックか垂直テキストブロックかが判定される。ステップＳ５８０２では、ＳＴＤ−ＬＥＮがＳＴＤ−ＷＩＤ以下かどうか、ＭＡＸ−ＷＩＤがＭＡＸ−ＬＥＮより大きいかどうか、そしてＭＡＸ−ＷＩＤが１２ｐｔのプリントサイズ、もしくは１．５×ＭＡＸ−ＬＥＮよりも大きいかどうかが判定される（ここで、１２ｐｔ値は通常のテキストサイズに基づいている。勿論、これより大きいまたは小さいテキストサイズの場合は、好ましくはダイナミックに調整できる異なる値が必要とされる）。これらの関係に該当すると、テキストブロックは水平テキストブロックであると決定される。これらの関係に該当しない場合は、ステップＳ５８０３へ進む。
【０１２６】
ステップＳ５８０３では、ＳＴＤ−ＷＩＤがＳＴＤ−ＬＥＮ以下であるかどうか、ＭＡＸ−ＬＥＮがＭＡＸ−ＷＩＤより大きいかどうか、そしてＭＡＸ−ＬＥＮが１２ｐｔ、または１．５×ＭＡＸ−ＷＩＤより大きいかどうかが判定される。これらの関係に該当すると、テキストブロックは垂直テキストブロックであると決定される。これらの関係に該当しない場合は、ステップＳ５８０４へ進む。
【０１２７】
ステップＳ５８０４では、各連続成分について、値Ｈ−ＳＨＯＲＴ及びＶ−ＳＨＯＲＴが決定される。これらの値はそれぞれ、各連続成分及びその周辺の連続成分からの最短の水平及び垂直の間隙を表している。
【０１２８】
そしてステップＳ５８０５（図１４Ｂ）へ進み、テキストブロック内の大抵の連続成分について、Ｈ−ＳＨＯＲＴがＶ−ＳＨＯＲＴより小さいかどうかが判定される。この関係に該当すると、テキストブロックは水平テキストブロックであると決定される。この関係に該当しない場合は、ステップＳ５８０６へ進んで、テキストブロック内の大抵の連続成分について、Ｖ−ＳＨＯＲＴがＨ−ＳＨＯＲＴより小さいかどうかが判定される。この関係に該当すると、テキストブロックは垂直テキストブロックであると決定され、該当しない場合は、ステップＳ５８０７へ進む。
【０１２９】
ステップＳ５８０７では、テキストブロック内の連続成分間の水平及び垂直の間隙の数が計算される。その後、ステップＳ５８０８では、水平間隙の数が垂直間隙の数より多いかどうか、またテキストブロックの幅が１２ｐｔ×２より大きいかどうかが判定される。この関係に該当すると、テキストブロックは水平テキストブロックであると決定され、該当しない場合は、ステップＳ５８０９へ進む。ステップＳ５８０９では垂直間隙数が水平間隙数より多いかどうか、またテキストブロックの長さが１２ｐｔ×２より大きいかどうかが判定される。この関係に該当すると、テキストブロックは垂直テキストブロックであると決定され、該当しない場合は、ステップＳ５８１０へ進む。
【０１３０】
ステップＳ５８１０では、テキストブロックの長さが１２ｐｔ×２より小さく、全ての連続成分が同一の水平ライン上にあるかどうかが判定される。これに該当する判定であれば、テキストブロックは水平テキストブロックであり、該当しない判定の場合は、ステップＳ５８１１へ進む。ステップＳ５８１１では、テキストブロックの幅が１２ｐｔ×２より小さく、全ての連続成分が同一の垂直線上にあるかどうかが判定される。この関係に該当すると、テキストブロックは垂直テキストブロックであると決定され、該当しない場合は、ステップＳ５８１２へ進む。
【０１３１】
ステップＳ５８１２では、テキストブロック内の全ての連続成分が垂直にソートされて、最初の連続成分と最後の連続成分が、重なる垂直領域を有しているかどうか検出される。それらが重なっていれば、テキストブロックは水平テキストブロックであると決定され、重なっていない場合は、ステップＳ５８１３へ進む。
ステップＳ５８１３では、テキストブロック内の全ての連続成分が水平にソートされて、最初の連続成分と最後の連続成分が、重なる水平領域を有しているかどうか検出される。それらが重なっていれば、テキストブロックは垂直テキストブロックであると決定され、重なっていない場合は、テキストブロックは未知のブロックである。
【０１３２】
識別された全てのテキストブロックの方向が一度決定されると、ステップＳ５９へ進み、ステップＳ５８で識別された方向に基づいて、各テキストブロックに関するテキストラインが形成される。図１５はこの処理を詳細に示すフローチャートである。
【０１３３】
図１５は水平テキストブロック内のテキスト連続成分の処理を示している。垂直テキストブロック内の連続成分の処理も同様であるので、詳細な説明は省略する。ステップＳ５９１では、水平テキストブロック内のテキスト成分が、その水平位置に従ってソートされる。その後、ステップＳ５９２では、ソーティングリストの次の連続成分が抽出され、その連続成分が既に存在しているいずれかのテキストラインに嵌入するかどうか検出される。この判定の詳細な処理は、図１６Ａ〜図１６Ｅで示されるフローチャートを参照して説明する。
【０１３４】
図１６Ａでは、ステップＳ５９２１で、ステップＳ５９２で抽出した連続成分を用いて、値Ｃ−ＬＩＮＥ１及びＣ−ＢＬＯＣＫ１が計算される。Ｃ−ＬＩＮＥ１は、抽出された連続成分と現在のテキストラインとの間のパーセントの垂直領域重畳部分を表し、Ｃ−ＢＬＯＣＫ１は、抽出された連続成分と現在のテキストラインの末尾連続成分との間のパーセントの垂直領域重畳部分を表している。図１６ＡのステップＳ５９２１は現在のテキストライン、その末尾の連続成分、抽出された連続成分、及びそれらの垂直領域重畳部分の関係を示している。
【０１３５】
ステップＳ５９２２では、Ｃ−ＬＩＮＥ１がゼロより大きいかどうかが判定される。ゼロより大きくなければ、図１６Ｅに従ってより詳細に説明されるステップＳ５９３６へ進む。一方、ステップＳ５９２２で、Ｃ−ＬＩＮＥ１がゼロより大きいと判定されると、３つの値ｈ−ｄｉｓｔ１、  ｖ−ｄｉｓｔ１、ＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥが決定される。ｈ−ｄｉｓｔ１は、抽出された連続成分と現在のテキストラインの末尾連続成分との間の水平距離である。ｖ−ｄｉｓｔ１は、抽出された連続成分と現在のテキストラインの末尾連続成分との間の垂直距離である。ＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥは、（ｉ）現在のラインの下にあり、（ｉｉ）その末尾連続成分が抽出された連続成分に最も近接しており、末尾連続成分と抽出された連続成分の間の距離は所定の距離内である、テキストラインである。そして、図１６ＢのステップＳ５９２４へ進む。
【０１３６】
ステップＳ５９２４では、値Ｃ−ＬＩＮＥ２、Ｃ−ＢＬＯＣＫ２、ｈ−ｄｉｓｔ２、及びｖ−ｄｉｓｔ２が決定される。Ｃ−ＬＩＮＥ２は、抽出された連続成分とＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥとの間のパーセントの垂直領域重畳部分である。Ｃ−ＢＬＯＣＫ２は、抽出された連続成分とＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥの末尾連続成分との間のパーセントの垂直領域重畳部分である。ｈ−ｄｉｓｔ２は、抽出された連続成分とＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥの末尾連続成分との間の水平距離である。ｖ−ｄｉｓｔ２は、抽出された連続成分とＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥの末尾連続成分との間の垂直距離である。
【０１３７】
その後、ステップＳ５９２５へ進み、Ｃ−ＬＩＮＥ１が５０％未満でＣ−ＬＩＮＥ２が５０％以上であり、そして現在のラインが上方向に傾き、ＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥが上方向に傾いているかどうかが判定される。この関係に該当すると、ステップＳ５９２６へ進み、次の水平テキストラインが選択されて、図１５のステップＳ５９２へ戻る。一方、この関係に該当しない場合は、図１６ＣのステップＳ５９２７へ進む。
【０１３８】
図１６Ｃにおいて、ステップＳ５９２７では、８つの関係が存在するかどうかが判定される。それらの関係は次の通りである。即ち、
(1) C-LINE2=0%
(2) C-LINE1≧50%、C-LINE2≦50%、
C-BLOCK1≧0%、C-BLOCK1>C-BLOCK2
(3) h-dist1>0、h-dist2>0、
(h-dist1<12pt、又はh-dist1<h-dist2)、
C-BLOCK1>0%、C-BLOCK1>C-BLOCK2
(4) h-dist1>0、h-dist2>0、
(h-dist1<12pt、又はh-dist1<h-dist2)、
C-BLOCK1>0%、現在のラインは下方向に傾き、
NEXT-CLOSEST-LINEも下方向に傾いている
(5) h-dist1>0、h-dist2>0
(h-dist1<12pt、又はh-dist1<h-dist2)、
C-BLOCK1=0%、C-BLOCK2=0%、
v-dist1<h-dist2
(6) h-dist1≧0、h-dist1<12pt、
C-BLOCK1>0%、h-dist2<0
(7) h-dist1<0、h-dist2<0、
v-dist1>v-dist2
(8) C-BLOCK1>C-BLOCK2
である。
【０１３９】
そしてステップＳ５９２８へ進み、（１）〜（８）の関係のいずれかに該当するかどうかが判定される。該当するものが無いと、ステップＳ５９２９へ進んで、次の水平テキストラインが選択され、図１５のステップＳ５９２へ戻る。ステップＳ５９２８で（１）〜（８）の関係のいずれかに該当すると、ステップＳ５９３０へ進んで、抽出された連続成分の水平位置が、現在のテキストラインの末尾連続成分と重畳するかどうかが判定される。重畳部分が存在すれば、ステップＳ５９３１へ進み、重畳部分が存在しなければ、ステップＳ５９３２へ進む。
【０１４０】
図１６Ｄにおいて、ステップＳ５９３１では、抽出された連続成分と現在のテキストラインの末尾連続成分を合計した長さが、１文字の長さと同じであるかどうかが判定される。合計の長さが１文字の長さと同じである場合は、ステップＳ５９３５へ進み、抽出された連続成分は現在のテキストラインに嵌入される。一方、合計の長さが１文字の長さと同じでない場合には、ステップＳ５９３１’へ進んで、Ｃ−ＢＬＯＣＫ１が５０％より大きいかどうか、またはｖ−ｄｉｓｔ１が１ドットサイズより小さいかどうかが判定される。いずれかの関係に該当すると、ステップＳ５９３５へ進んで、抽出された連続成分は現在の水平テキストラインへ嵌入される。しかし、ステップＳ５９３１’のいずれの関係にも該当しない場合は、ステップＳ５９３３へ進み、次の水平テキストラインが選択されて、その後、図１５のステップＳ５９２へ戻る。
【０１４１】
ステップＳ５９３２では、ｈ−ｄｉｓｔ１が１２ｐｔ×２より小さく、（Ｃ−ＬＩＮＥ１が０％より大きいか、またはＣ−ＢＬＯＣＫ１が０％より大きい）かどうか、あるいは、ＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥが存在しないかどうか、またはｖ−ｄｉｓｔ１がｖ−ｄｉｓｔ２より小さいかどうかが判定される。これらの条件が満たされると、抽出された連続成分は現在のテキストライン内に当て嵌まると決定され、ステップＳ５９３５を介して図１５のステップＳ５９２へ進む。ステップＳ５９３２の関係に該当しない場合は、ステップＳ５９３４で次のテキストラインが選択され、再び図１５のステップＳ５９２へ戻る。
【０１４２】
図１６Ａへ戻り、ステップＳ５９２２で、Ｃ−ＬＩＮＥ１が０％より大きくないと判定されると、図１６ＥのステップＳ５９３６へ進む。ステップＳ５９３６では、ステップＳ５９２３、Ｓ５９２４で概略を述べたように、ＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥ、ｈ−ｄｉｓｔ１、ｈ−ｄｉｓｔ２、ｖ−ｄｉｓｔ１、及びｖ−ｄｉｓｔ２が決定される。
【０１４３】
ステップＳ５９３７では、ＮＥＸＴ−ＣＬＯＳＥＳＴ−ＬＩＮＥが存在し、ｖ−ｄｉｓｔ１がｖ−ｄｉｓｔ２より大きいかどうかが判定される。該当する場合、ステップＳ５９３９へ進み、次のテキストラインが選択され、そして図１５のステップＳ５９２へ戻る。しかし、ステップＳ５９３７の関係が存在しなければ、ステップＳ５９３８へ進み、ｈ−ｄｉｓｔ１がゼロ未満でｖ−ｄｉｓｔ１が１ドットサイズ以下であり、抽出された連続成分と末尾連続成分の合計の長さが１文字の長さと同じであるかどうかが判定される。これらの関係に該当すると、ステップＳ５９４１で、抽出された連続成分は現在の水平テキストライン内に当て嵌まると決定され、図１５のステップＳ５９２へ戻る。ステップＳ５９３８の関係に該当しない場合は、ステップＳ５９４０へ進み、ｈ−ｄｉｓｔ１がゼロ以上で、抽出された連続成分が末尾連続成分の上にあり、抽出された連続成分の垂直位置が末尾連続成分の垂直位置に近いかどうかが判定される。これらの関係に該当すると、ステップＳ５９４１へ進み、抽出された連続成分は現在の水平テキストライン内に当て嵌まると判定され、図１５のステップＳ５９２へ戻る。これらの関係に該当しない場合は、ステップＳ５９４２へ進み、次の水平テキストラインが選択され、図１５のステップＳ５９２へ戻る。
【０１４４】
図５のステップＳ５９において各テキストブロックについて全てのテキストラインが形成されると、ステップＳ６０へ進み、ブロックの後処理が行なわれる。後処理は、文字認識、データ圧縮等の、特定の後続する手順を適用するようにしてもよい。この応用の目的で、後続する文字認識をブロックに対する後処理として行なう場合を説明する。こうした後処理の目的は、テキスト及び非テキストブロック表現をより簡潔にすることである。後処理において、必要であれば、テキストブロックは他のテキストブロックと結合され、非テキストブロックは他の非テキストブロックと結合されて、文字認識等の更なる処理を容易にする。まず、例えば、最小二乗法を用いて、形成されたテキストライン（ステップＳ５９で決定された）に含まれる連続成分に基づいて、そのテキストラインの歪み角度を概算し、全体のページの歪みが計算される。ページの歪みは、ページのテキストラインの歪み角度の平均値となる。
【０１４５】
ページが僅かに歪んでいるだけであると（例えば、図１７に示すように、各テキストを囲む四角形または不規則な曲線の間の間隙が明確である）判定された場合は、様々な処理ステップが実行できる。始めに、テキスト（またはタイトル）ブロックと、タイトルブロックが、重畳する四角形または不規則な曲線の囲みが存在するかどうか、それらの方向（orientation）等に基づいて結合できる。次に、ある小さいテキストブロックが実際にテキストブロックであるか、それとも写真等の非テキストブロックの一部であるかを判断するために、ある中間調（またはグレイスケール）画像が四角い領域を占めているかどうかが判定できる。３番目に、欄の分析を行い、欄情報に基づいて、テキストブロックが結合できる。こうした結合は、基本的に、ブロックが同一の欄内にあるかどうか、お互いに近接しているかどうか、その結合が他のブロックに重なるかどうか、及びそれらのブロックが同一の傾斜を持っているかどうかに基づいて行なわれる。
【０１４６】
ページの歪みがいくらか大きい場合は、歪みページのケースにおいて上記の３つの処理ステップは抜かされる。そして、小さいテキストブロックがその近接ブロックと結合されるステップが実行される。この結合は、近接ブロックの属性、近接ブロックの近接度、及びテキストブロック自身の特性に基づいて行なわれる。こうした結合の後、結合されたテキストブロックの属性は、結合された近接テキストブロックと一致するように変えられる。
【０１４７】
また、複数のテキストブロックは、複数のタイトルブロックまたは未知の連続成分を１つ含んだ複数ブロックと結合することができる。この結合は、その相対的な位置、ブロックの方向、ブロックの相対的なサイズ等に元づいて行なわれる。
【０１４８】
最後に、ブロックの後処理として、幾つかの非テキストブロックの結合を行なうこともできる。こうした結合は、非テキストブロックの相対的位置、ブロックの属性等に基づいて行なわれる。例えば、幾つかの写真ブロックは、それらが同一の写真に属しているということが検出されれば結合される。こうした後処理を、後続の文字認識処理を容易にするために実行することが可能である。
【０１４９】
このように、格納された文書において効果的及び効率的にテキスト及び非テキストブロックを選択する方法及び装置であって、垂直及び水平テキストブロックが認識され、テキストブロックの形成の前に文書の回転を必要としない、方法及び装置を説明した。
【０１５０】
図面のブロックで概略が示され、または指定された個々の成分は、文字認識の分野では公知のものであり、その特定の構成及び動作は、本実施例の操作または実行の最良の形態において重要なものではない。
【０１５１】
本発明は好適な実施例について説明されたが、本発明は開示された実施例に限定されるものではないことが理解されるべきである。反対に、発明の精神と範囲内に含まれる、様々な修正や同等の変形が可能であるよう意図されている。特許請求の範囲の記載は、そうした修正及や同等の構成及び機能の全てに渡るように最大の解釈が与えられるものである。
【０１５２】
尚、本発明は、複数の機器から構成されるシステムに適用しても１つの機器からなる装置に適用しても良い。また、本発明はシステム或いは装置に本発明により規定される処理を実行させるプログラムを供給することによって達成される場合にも適用できることはいうまでもない。
【０１５３】
【発明の効果】
以上説明したように、本発明によれば、テキストブロックを非テキストブロックの不可視線、非テキストブロックのエッジに沿った不可視線により分割することにより、より確実にテキストブロックを抽出でき、非テキストブロックを文字とするような誤認識の発生を低減できる。
【０１５４】
【図面の簡単な説明】
【図１】文字認識される文書の一般的な１ページを示す図である。
【図２】本発明の一実施例に係わる装置の斜視図である。
【図３】本発明の一実施例に係わる装置のブロック図である。
【図４】本実施例のブロック選択の特徴がどの様に文字認識のプロセスに組み込まれているかを示す、一般化されたフローチャートである。
【図５】本発明に係わるブロック選択技術を示す全体的なフローチャートである。
【図６Ａ】図５のステップＳ５１〜Ｓ５３の詳細を示すフローチャートである。
【図６Ｂ】図５のステップＳ５１〜Ｓ５３の詳細を示すフローチャートである。
【図６Ｃ】図５のステップＳ５１〜Ｓ５３の詳細を示すフローチャートである。
【図６Ｄ】図５のステップＳ５１〜Ｓ５３の詳細を示すフローチャートである。
【図７Ａ】輪郭トレースを説明するための図である。
【図７Ｂ】輪郭トレースを説明するための図である。
【図７Ｃ】輪郭トレースを説明するための図である。
【図８Ａ】非テキストユニットに対する分類処理を説明するための図である。
【図８Ｂ】非テキストユニットに対する分類処理を説明するための図である。
【図８Ｃ】非テキストユニットに対する分類処理を説明するための図である。
【図９Ａ】白輪郭処理を説明するための図である。
【図９Ｂ】白輪郭処理を説明するための図である。
【図９Ｃ】白輪郭処理を説明するための図である。
【図９Ｄ】白輪郭処理を説明するための図である。
【図１０】本実施例における、テキスト及び非テキスト文字を決定するためのルートまたはツリー階層構造を概略的に示す図である。
【図１１】図５のステップＳ５６を示すフローチャートである。
【図１２】図１１のステップＳ５６６を示すフローチャートである。
【図１３Ａ】図５のステップＳ５７を概略的に示す図である。
【図１３Ｂ】図５のステップＳ５７を概略的に示す図である。
【図１４Ａ】図５のステップＳ５８を示すフローチャートである。
【図１４Ｂ】図５のステップＳ５８を示すフローチャートである。
【図１５】図５のステップＳ５９を示すフローチャートである。
【図１６Ａ】図１５のステップＳ５９２を示すフローチャートである。
【図１６Ｂ】図１５のステップＳ５９２を示すフローチャートである。
【図１６Ｃ】図１５のステップＳ５９２を示すフローチャートである。
【図１６Ｄ】図１５のステップＳ５９２を示すフローチャートである。
【図１６Ｅ】図１５のステップＳ５９２を示すフローチャートである。
【図１７】不規則な形状のテキストブロックを概略的に示す図である。
【図１】
0003754716.tif 000006
【図２】
0003754716.tif 000007
【図３】
0003754716.tif 000008
【図４】
0003754716.tif 000009
【図５】
0003754716.tif 000010
【図６Ａ】
0003754716.tif 000011
【図６Ｂ】
0003754716.tif 000012
【図６Ｃ】
0003754716.tif 000013
【図６Ｄ】
0003754716.tif 000014
【図７Ａ】
0003754716.tif 000015
【図７Ｂ】
0003754716.tif 000016
【図７Ｃ】
0003754716.tif 000017
【図８Ａ】
0003754716.tif 000018
【図８Ｂ】
0003754716.tif 000019
【図８Ｃ】
0003754716.tif 000020
【図９Ａ】
0003754716.tif 000021
【図９Ｂ】
0003754716.tif 000022
【図９Ｃ】
0003754716.tif 000023
【図９Ｄ】
0003754716.tif 000024
【図１０】
0003754716.tif 000025
【図１１】
0003754716.tif 000026
【図１２】
0003754716.tif 000027
【図１３Ａ】
0003754716.tif 000028
【図１３Ｂ】
0003754716.tif 000029
【図１４Ａ】
0003754716.tif 000030
【図１４Ｂ】
0003754716.tif 000031
【図１５】
0003754716.tif 000032
【図１６Ａ】
0003754716.tif 000033
【図１６Ｂ】
0003754716.tif 000034
【図１６Ｃ】
0003754716.tif 000035
【図１６Ｄ】
0003754716.tif 000036
【図１６Ｅ】
0003754716.tif 000037
【図１７】
0003754716.tif 000038