(57)【特許請求の範囲】
【請求項１】
文書画像のテキスト部分のテキスト特徴を決定するための自動テキスト特徴決定システムであって、
前記テキスト部分を表すディジタルデータ信号を入力するための入力手段を有し、前記ディジタルデータ信号が複数の信号部分を備え、且つ各信号部分が前記文書画像の複数の画素の内の一つに対応しており、
前記複数の信号部分から複数の連結成分を生成するための連結成分生成手段を有し、
前記連結成分を解析軸と位置合わせするための位置合わせ手段を有し、位置合わせ手段はテキストの行ごとに決定される基線を解析軸と配向が一致するように位置合わせし、かつ、各行のワープされた連結成分を基線に位置合せする手段を含み、
複数の境界ボックスを生成するための境界ボックス生成手段を有し、各境界ボックスが前記複数の連結成分の内の対応する一つの連結成分を取り囲み、
前記テキスト部分のテキストの各行は前記複数の連結成分の内の少なくとも一つを備えていて、前記テキストの各行の空間特徴を決定するためのライン空間特徴決定手段を有し、ライン空間特徴決定手段は、テキスト部分から、垂直に収縮されたテキスト部分を生成する垂直収縮手段と、収縮されないテキスト部分の垂直プロファイルを生成する垂直プロファイル手段とを備える、
自動テキスト特徴決定システム。
【請求項２】
文書画像のテキスト部分のテキスト特徴を決定するための自動テキスト特徴決定システムであって、
前記テキスト部分を表すディジタルデータ信号を入力するための入力手段を有し、前記ディジタルデータ信号が複数の信号部分を備え、且つ各信号部分が前記文書画像の複数の画素の内の一つに対応しており、
前記複数の信号部分から複数の連結成分を生成するための連結成分生成手段を有し、
前記連結成分を解析軸と位置合わせするための位置合わせ手段を有し、位置合わせ手段はテキストの行ごとに決定される基線を解析軸と配向が一致するように位置合わせし、かつ、各行のワープされた連結成分を基線に位置合せする手段を含み、
複数の境界ボックスを生成するための境界ボックス生成手段を有し、各境界ボックスが前記複数の連結成分の内の対応する一つの連結成分を取り囲み、
前記テキスト部分のテキストの各行は前記複数の連結成分の内の少なくとも一つを備えていて、前記テキストの各行の空間特徴を決定するためのライン空間特徴決定手段を有し、ライン空間特徴決定手段は、各行の文字とワードのスペースを決定するワードスペース決定手段を備える、
自動テキスト特徴決定システム。
【請求項３】
前記ワードスペース決定手段は、テキスト部分の各行を水平に収縮する水平収縮手段を備える、請求項２記載の自動テキスト特徴決定システム。
【請求項４】
前記ワードスペース決定手段は、水平に収縮されたテキストのテキスト部分の各行内に少なくとも１つの文字セルを生成するための文字セル生成手段を備え、各文字セルは、テキスト部分の少なくとも１つの垂直に位置合わせされた連結成分のグループを含む、請求項３記載の自動テキスト特徴決定システム。
【請求項５】
文書画像のテキスト部分のテキスト特徴を決定するための自動テキスト特徴決定システムであって、
前記テキスト部分を表すディジタルデータ信号を入力するための入力手段を有し、前記ディジタルデータ信号が複数の信号部分を備え、且つ各信号部分が前記文書画像の複数の画素の内の一つに対応しており、
前記複数の信号部分から複数の連結成分を生成するための連結成分生成手段を有し、
前記連結成分を解析軸と位置合わせするための位置合わせ手段を有し、前記位置合わせ手段は、
前記テキスト部分の連結成分の主テキスト方向を決定するためのテキスト配向決定手段と、
前記テキスト部分の連結成分の主テキスト方向を解析軸に位置合せし、それによりテキスト配向を解析軸に位置合わせするための軸位置合せ手段と、
前記テキスト部分の連結成分のスキューした部分およびワープした部分を解析軸に位置合せするためのライン位置合せ手段とを有しており、
複数の境界ボックスを生成するための境界ボックス生成手段を有し、各境界ボックスが前記複数の連結成分の内の対応する一つの連結成分を取り囲み、
前記テキスト部分のテキストの各行は前記複数の連結成分の内の少なくとも一つを備えていて、前記テキストの各行の空間特徴を決定するためのライン空間特徴決定手段を有し、ライン空間特徴決定手段は、テキスト部分から、垂直に収縮されたテキスト部分を生成する垂直収縮手段と、収縮されないテキスト部分の垂直プロファイルを生成する垂直プロファイル手段とを備える、
自動テキスト特徴決定システム。
【請求項６】
文書画像のテキスト部分のテキスト特徴を決定するための自動テキスト特徴決定システムであって、
前記テキスト部分を表すディジタルデータ信号を入力するための入力手段を有し、前記ディジタルデータ信号が複数の信号部分を備え、且つ各信号部分が前記文書画像の複数の画素の内の一つに対応しており、
前記複数の信号部分から複数の連結成分を生成するための連結成分生成手段を有し、
前記連結成分を解析軸と位置合わせするための位置合わせ手段を有し、前記位置合わせ手段は、
前記テキスト部分の連結成分の主テキスト方向を決定するためのテキスト配向決定手段と、
前記テキスト部分の連結成分の主テキスト方向を解析軸に位置合せし、それによりテキスト配向を解析軸に位置合わせするための軸位置合せ手段と、
前記テキスト部分の連結成分のスキューした部分およびワープした部分を解析軸に位置合せするためのライン位置合せ手段とを有しており、
複数の境界ボックスを生成するための境界ボックス生成手段を有し、各境界ボックスが前記複数の連結成分の内の対応する一つの連結成分を取り囲み、
前記テキスト部分のテキストの各行は前記複数の連結成分の内の少なくとも一つを備えていて、前記テキストの各行の空間特徴を決定するためのライン空間特徴決定手段を有し、ライン空間特徴決定手段は、各行の文字とワードのスペースを決定するワードスペース決定手段を備える、
自動テキスト特徴決定システム。
【請求項７】
前記ワードスペース決定手段は、テキスト部分の各行を水平に収縮する水平収縮手段を備える、請求項６記載の自動テキスト特徴決定システム。
【請求項８】
前記ワードスペース決定手段は、水平に収縮されたテキストのテキスト部分の各行内に少なくとも１つの文字セルを生成するための文字セル生成手段を備え、各文字セルは、テキスト部分の少なくとも１つの垂直に位置合わせされた連結成分のグループを含む、請求項７記載の自動テキスト特徴決定システム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は自動文書認識のための方法及び装置に係り、特に、文書内のテキストラインの空間特徴を自動的に決定するための改良された方法に関する。とりわけ、本発明は、これらのテキストラインが特に迅速且つロバスト（堅牢）に識別されるように、スキュー（傾斜）され且つ歪んだ又は低解像度の文書画像を、利用可能な画像ソースへ変換するための方法に関する。この方法は、スキューやラインワープ（ラインの曲がり）の存在においてロバストであり且つフォトコピー（写真複写）誘導雑音に対して耐性を有する。本発明は更に、テキストのスプレイイング（拡げること）をテキストの収縮と置き換えることによって計算やメモリのデマンド（要求）をより一層減少する。
【０００２】
【従来の技術】
走査された画像データをディジタルコンピュータに使用するのに適したテキストデータへ変換するための光学的文字認識とその使用は周知である。さらに、走査された画像データをテキストデータへ変換するための方法と、このような方法が発生するエラーのタイプも周知である。走査された画像データをテキストデータへ変換する時に生じる様々な問題は、テキストの個々のラインを互いに識別できること、テキストの単一ライン内の複数ワードのグルーピングを識別できること、テキストの単一ライン内の文字セルの垂直及び水平の拡がり（エクステント）を決定すること、及びテキストの単一ライン内の連結成分間のリガチュア（合字、抱き字）又はカーン（kerns ）（はみ出し又は食い込み文字）を適切に分離することにある。
【０００３】
これらの問題は単独で解決するのは難しく且つ認識されるべき画像の実際のテキストラインがスキューされ、ワープされ（曲がり）、且つ雑音で一杯になった時は度々解決が不可能となる。従って、以下のような場合、テキストラインを検出することが難しい。
１）ラインが文書上の画像の軸と位置合わせされていない、つまり互いに平行でない（スキュー）場合。
２）ラインが直線でない（ワープしている）場合。又は、
３）ラインが認識しようとする画像の一部ではない画像成分を含む場合、又はラインの文字が歪んでいる（雑音がある）場合。
【０００４】
本明細書中に参照することによって組み込まれているスピッツ（Spitz ）に与えられた日本特許第6-70294 号において、テキストラインのボトム（下部）、トップ（上部）、ベースライン、及びｘ−ライン位置を識別するための方法が開示されている。この出願は、概して、個々のラインを識別するためにフルサイズの連結成分を垂直にスプレイし（拡げ）、次いで連結成分の個々の文字及びワードのグルーピングを識別するために水平のスプレイイングを用いることによって、画像のライン、ワード、及び文字を分離した。
【０００５】
スピッツの日本特許第6-70294 号において説明された方法に従って、文書の画像のテキスト部分の複数の連結成分を取り囲む複数の境界ボックスが生成される。これらの境界ボックス（及び連結成分）は、現在ライン（行）の境界ボックスと該現在ラインに垂直に隣接しているラインの境界ボックスのあらゆるオーバーラップ（重なり）を分離するために垂直方向にスプレイされる。各ラインの連結成分の垂直プロファイルが生成され且つトップとボトムのピーク（頂点）が検出される。連結成分のボトムとトップの領域の個々の垂直プロファイルが生成されて、且つベースラインとｘ−ラインの位置をそれぞれ決定する。テキスト部分の各ラインが一旦識別されると、境界ボックス（及び連結成分）は次いで水平にスプレイされて、且つ現在ライン内の境界ボックスのあらゆるオーバーラップ（重なり）を取り除く。ラインごとに、そのラインの連結成分のモーダル（様相又は形式的）（modal ）ストローク幅の値が決定される。連結成分の実際のストローク幅がこのモーダルストローク幅と比較される。あらゆる連結成分が、モーダルストローク幅の所定の倍数より大きな実際のストローク幅を有している場合、このような連結成分の各々は二つ又はそれより多くの独立した連結成分の可能性のあるリガチュア（抱き字又は合字）であると考えられる。この場合において、連結成分は分割されてもよい。このようなリガチュアは、これ以上の分割がもうできないというまで再帰的に分割される。一旦全ての可能性のある分割が行われると、隣接する連結成分の間の空間が各ラインのワード及び文字の空間を決定するために解析される。
【０００６】
連結成分が周囲の連結成分から垂直に及び水平に明確に分割されるように、一旦画像のテキスト部分がスプレイされると、各ラインのトップとボトムの位置の間にあり且つ垂直に位置合わせされた連結成分の各グループは１文字として一つの文字セル内に共にグルーピングされる。
【０００７】
しかしながら、この方法は、スキューされ、ワープされ、且つ雑音のあるテキスト画像を処理する時に、充分にロバストではない。このような画像はオリジナル画像を写真複写する時に度々生成される。コピー（複製）画像は、形成されるシートの軸に対して度々スキューされる。さらに、オリジナル画像を書籍から取った場合は、（本の）背（スパイン）に近い部分で、ラインがガッタ歪みとして知られる特徴的な湾曲によってワープする。結局、写真複写プロセスは多数の異なる種類の雑音を生じ得る。第１に、コピーの解像度はオリジナル画像に比べて極めて低いかもしれない。従って、コピー画像内の文字の外郭は歪み、且つ文字内で偶発的に（又は意図的に）損失した又は加わった画像の画素による雑音を有することになる。第２に、コピー処理は、コピーウィンドウ上のデブリス（残がい）又は複写機の受光体（又は感光体含む）若しくは他の要素の疵によって画像画素の完全な擬似グループを追加するかもしれない。
【０００８】
【発明が解決しようとする課題】
本発明は、従って、テキストライン、ワード及び文字セルの特徴認識能力を有する改良された光学的文字認識システムを提供する。
【０００９】
本発明はまた、テキストラインが一つ又はそれより多くのスキュー、ワープ、又は雑音によって歪んだ時の文書のテキストライン、ワード及び文字セルの空間特徴を自動的に決定する。
【００１０】
本発明はまた、スキューされ又はワープされたラインが画像軸と位置合わせされるのを可能とするシステムを提供する。
【００１１】
本発明はまた、計算量及びメモリに対する要求が少ない、画像ライン、画像ワード、及び画像文字を識別するシステムをさらに提供する。
【００１２】
本発明は、連結成分の周りに形成される境界ボックスの中心の周りの画像の連結成分の大きさを選択的に収縮することによって計算量やメモリに対する要求を減少することをさらに提供する。
【００１３】
【課題を解決するための手段】
本発明の第１の実施例において、画像のビットマップは連結成分のリストへ変換される。次いで、画像の優先直交軸が決定され、且つ画像の軸が解析軸に位置合わせされる。次に、画像の優先軸に対してスキューされたあらゆる残りのラインが画像軸と位置合わせされるように移動される。
【００１４】
次に、同様に、ワープされたあらゆるライン部分は、画像の軸と位置合わせするように移動する。連結成分が位置合わせするように移動した時は常に、小さな回転がこれらの連結成分に加えられる。このシステムは小さな回転に一般にあまり感応しないが、回転された連結成分は連結成分が画像軸と最適に位置合わせされるように補償され得る。
【００１５】
連結成分の全てが画像軸に位置合わせされると、境界ボックスは各連結成分の周りに生成され且つこれらの境界ボックスの中心が検出される。次いで、各境界ボックスはその中心の周りを垂直方向に収縮されて、且つ画像を個々のラインへ分離する。次いで各ラインに属する連結成分が識別される。
【００１６】
次いで、ラインごとにモーダルベースラインが決定され、且つそのラインの各ベースラインの連結成分がモーダルベースラインと位置合わせされる。これは、もしあれば、ディセンダ（下に出る部分）をマスクして行われる。全ての連結成分が一旦ベースラインに位置合わせされると、ディセンダはベースラインから適切に下に出るようにマスクが取られ且つ再度位置合わせされる。この時点で、各ラインに対するｘ−ライン、ボトムライン、及びトップラインのパラメータが既に決定されたベースラインに相対して決定される。
【００１７】
次に、連結成分のワードグルーピング及び文字グルーピングが決定される。最初に、現在ラインの各境界ボックスが境界ボックスを互いに分離するためにその中心の周りで水平方向に収縮される。次いで、境界ボックス同士間の異なるサイズを有するレディング（leading)（白色空間）のロケーション（位置）及び相対数が一つ又はそれより多くのワード内空間（スペース）又はワード間空間を示す一つ又はそれより多くのピークを見つけるために解析される。
【００１８】
ワード内及び／又はワード間空間が一旦見つかると、あらゆる充分にワイドな連結成分が偶発的又は意図的にカーンド文字（隣合う文字同士を互いにくい込ませ、詰めた文字）を分離するために解析される。
【００１９】
本発明は、文書画像のテキスト部分のテキスト特徴を決定するための自動テキスト特徴決定システムであって、前記テキスト部分を表すディジタルデータ信号を入力するための入力手段を有し、前記ディジタルデータ信号が複数の信号部分を備え、且つ各信号部分が前記文書画像の複数の画素の内の一つに対応しており、前記複数の信号部分から複数の連結成分を生成するための連結成分生成手段を有し、前記連結成分を解析軸と位置合わせするための位置合わせ手段を有し、位置合わせ手段はテキストの行（ライン）ごとに決定される基線を解析軸と配向が一致するように位置合わせし、各行（ライン）のワープされた連結成分を基線に位置合せする手段を含み、複数の境界ボックスを生成するための境界ボックス生成手段を有し、各境界ボックスが前記複数の連結成分の内の対応する一つの連結成分を取り囲み、前記テキスト部分のテキストの各行（ライン）は前記複数の連結成分の内の少なくとも一つを備えていて、前記テキストの各行（ライン）の空間特徴を決定するためのライン空間特徴決定手段を有する。
また、本発明は、文書画像のテキスト部分のテキスト特徴を決定するための自動テキスト特徴決定システムであって、前記テキスト部分を表すディジタルデータ信号を入力するための入力手段を有し、前記ディジタルデータ信号が複数の信号部分を備え、且つ各信号部分が前記文書画像の複数の画素の内の一つに対応しており、前記複数の信号部分から複数の連結成分を生成するための連結成分生成手段を有し、前記連結成分を解析軸と位置合わせするための位置合わせ手段を有し、前記位置合わせ手段は、前記テキスト部分の連結成分の主テキスト方向を決定するためのテキスト配向決定手段と、前記テキスト部分の連結成分の主テキスト方向を解析軸に位置合せし、それによりテキスト配向を解析軸に位置合わせするための軸位置合せ手段と、前記テキスト部分の連結成分のスキューした部分およびワープした部分を解析軸に位置合せするためのライン位置合せ手段とを有しており、複数の境界ボックスを生成するための境界ボックス生成手段を有し、各境界ボックスが前記複数の連結成分の内の対応する一つの連結成分を取り囲み、前記テキスト部分のテキストの各行（ライン）は前記複数の連結成分の内の少なくとも一つを備えていて、前記テキストの各行（ライン）の空間特徴を決定するためのライン空間特徴決定手段を有する。
さらに、ライン空間特徴決定手段は、テキスト部分から、垂直に収縮されたテキスト部分を生成する垂直収縮手段と、収縮されないテキスト部分の垂直プロファイルを生成する垂直プロファイル手段とを備える。
また、ライン空間特徴決定手段は、各行の文字とワードのスペースを決定するワードスペース決定手段を備える。
【００２０】
【実施例】
図１に示したように、本発明の光学的文字認識システムは電荷結合素子（ＣＣＤ）又はその他同種のものを有するスキャナ１１０を備える。スキャナ１１０は画像を有する文書を走査し、且つこの画像は未知の活字書体や言語のテキスト部分を備える。スキャナ１１０は、オリジナル文書の画像を備える複数の画素のロケーション（場所）や画像濃度を表すディジタルデータ信号を出力する。このディジタルデータ信号はメモリ１１２へ送られて且つメモリ１１２へ一時的及び無期限で記憶される。メモリ１１２から出力されると、ディジタルデータ信号は汎用ディジタルコンピュータ１１４へ入力される。コンピュータ１１４へ入力されると、ディジタルデータ信号は、画像のあらゆるノンテキスト部分を除去することによりクリーンアップ（整理）されて、テキスト部分を残す。クリーンアップされたディジタルデータ信号は次いでメモリ１１２へ戻されるか又はコンピュータ１１４のメモリ内に記憶される。
【００２１】
図１に示したように、本発明の汎用ディジタルコンピュータ１１４は、コントロールプログラムを記憶するためのメモリ２２と、メモリ１１２からディジタルデータ信号を入力し且つテキスト部分の決定された文字セルを表す信号を出力するための入力／出力回路２４を備える。汎用ディジタルコンピュータ１１４はまた、ディジタルデータ信号を記憶するための画像ＲＡＭ（ランダムアクセスメモリ）２６と、ディジタルデータ信号から連結成分を生成するための連結成分生成手段２８と、境界ボックスの座標を決定し且つ連結成分ごとに境界ボックス内のディジタル化された画像の画素を決定するための境界ボックス生成手段３０と、テキスト部分を垂直に収縮するための垂直収縮手段３２と、非収縮テキスト部分の垂直プロファイルを生成するための垂直プロファイル手段３４と、テキスト部分を水平に収縮するための空間特徴決定手段３６と、連結成分を文字セルへグルーピングし且つ文字とワード（単語）の分割を識別するための文字セル生成手段３８と、画像の複数の主軸を解析軸と位置合わせするための画像軸検出手段４０と、連結成分移動回転手段４２、及びラインの連結成分をそのラインのベースライン（基線）位置へ位置合わせして、且つ必要となれば、連結成分上に与えられた回転を取り除くためのベースライン位置合わせ手段４４と、画像の複数の主軸の配向を決定するためのテキスト配向決定手段４６と、を備える。垂直プロファイル手段３４は、テキスト部分と、テキスト部分の各ラインと、各ラインの部分の垂直プロファイルを生成するための垂直プロファイル生成手段３４２と、各ラインの少なくともトップ、ボトム、及びｘ−ラインの位置を決定するための垂直位置決定手段３４０を備える。ライン空間特徴決定手段３６は、テキスト部分の各ラインを水平に収縮するための水平収縮手段３６０と、テキスト部分の各ライン内にワード内空間とワード間空間を決定するための空間決定手段３６２と、テキスト部分の各ラインのモードストローク幅と、連結成分ごとに実際のストローク幅を決定するためのストローク幅決定手段３６４と、を備える。コントロールプログラムを記憶するためのメモリ２２はＲＯＭ（リードオンリーメモリ）２２ａ又はＲＡＭ２２ｂを備えていてもよい。
【００２２】
動作上は、画像を含む文書が設置され且つのスキャナ１１０によって走査されて、且つ直列又は並列のディジタルデータ信号を生成する。ディジタルデータ信号は、各部分がオリジナル文書の対応画素を表す複数の信号部分を備える。画像の各画素は画像内のロケーションと画像濃度を有する。従って、ディジタルデータ信号の各信号部分は対応画素のロケーションと画像濃度を表すデータを含む。
【００２３】
スキャナ１１０によって出力されたディジタルデータ信号は次いでメモリ１１２に記憶される。メモリ１１２は、ＲＡＭ、フラッシュメモリ、ディスクメモリなどを備えていてもよい。メモリ１１２のタイプに関わらず、ディジタルデータ信号は各信号部分内のロケーション及び画像濃度に応答して、メモリ１１２に記憶される。ディジタルデータ信号が中間メモリ１１２ではなくて汎用ディジタルコンピュータ１１４へ直接入力され得ることが当然理解されよう。或いは、メモリ１１２が汎用ディジタルコンピュータ１１４へ組み込まれ得る。あらゆるケースにおいて、メモリ１１２が画像の長期記憶を提供するために使用されることが理解されよう。
【００２４】
オペレータがスキャナ１１０への文書入力を終了するか、そうでなければ、システムが、メモリ１１２に記憶された画像を表すディジタルデータ信号がテキストデータへ変換されるべきであることを決定するか若しくは（そのように）命令されると、画像を表すディジタルデータ信号はメモリ１１２から汎用コンピュータ１１４へ出力される。特殊目的のディジタルコンピュータ又はハードワイヤード論理回路が汎用ディジタルコンピュータ１１４に代わって使用され得ることは当然理解されよう。
【００２５】
メモリ１１２に記憶されたディジタル画像データ信号は、汎用コンピュータ１１４へ出力され、且つここで入力／出力手段２４を介して画像メモリ２６へ入力される。ディジタルデータ信号が画像メモリ２６に完全に記憶されると、画像を表すディジタルデータ信号は連結成分生成手段２８へ出力される。連結成分生成手段２８は、位置合わせされた画像を表すディジタルデータ信号を複数の連結成分へ分割し、且つ各連結成分は一つ又はそれより多くの信号部分を備える。各連結成分はある最小画像濃度を有し且つ連続パス（経路）を形成する位置合わせされた画像の画素に対応する信号部分を備える。各活字書体文字は、図３の（ａ）に示したように、"Fuji"の"F" におけるように、一般に一つの連結成分に対応するか、又は"Fuji"の"j" 又は"i" におけるように、一つより多くの連結成分に対応する。連結成分生成手段２８によって生成された連結成分のリストは、画像メモリ２６及び／又はメモリ１１２に記憶される。
【００２６】
連結成分生成手段２８がディジタルデータ信号からの位置合わせされた画像に対して複数の連結成分を生成すると、画像メモリ２６に記憶された画像と連結成分生成手段２８によって生成された連結成分のリストに対応するディジタルデータ信号が境界ボックス生成手段３０へ出力される。
【００２７】
境界ボックス生成手段３０は位置合わせされた画像を表すディジタルデータ信号を複数の境界ボックスへ再分割して、且つ各境界ボックスは一つの連結成分と、その連結成分を有する信号部分に隣接するように又は近傍に位置されたディジタル信号のゼロ、１つ又はそれより多くの信号部分を含む。テキスト部分の画素に対応するこれらの更なる信号部分は各連結成分を取り囲む。各境界ボックスの大きさは対応する連結成分を有する最左、最右、最上、及び最下の信号部分のロケーション（位置）データによって決定される。従って、境界ボックス内の信号部分は、連結成分を備える信号部分であり且つ均一に黒即ち画素で表された境界ボックスの内容を示す図３の（ｂ）に示したように、それらの画像濃度データとは無関係に、境界ボックスの境界内にそれらを配置するロケーションデータを有する信号部分である。
【００２８】
境界ボックスと各境界ボックスを有する信号部分のリストが境界ボックス生成手段３０によって一旦生成されると、境界ボックスのリストは画像メモリ２６又はメモリ１１２へ入力される。次いで、画像は画像の第１の（主）配向を決定するテキスト配向決定手段４６へ出力される。
【００２９】
テキスト配向決定手段４６は「ライン」方向が水平（又は縦向き）か否か又は垂直（又は横向き）か否かを決定する。水平方向は画像を含むページの短い側と平行であると定義される。即ち、アジア系（アセンダ部分又はディセンダ部分をもたない活字）テキストは、テキストのラインを水平に延ばし且つ画像のラインを垂直に延ばすことによって水平にセットされるか、又はテキストのラインを垂直に延ばし且つ画像のラインを水平に延ばすことによって垂直にセットされる。同様に、ローマン体（欧文活字書体）テキストは、水平にセットされたアジア系テキストのように縦向きにセットされ得るか又は垂直にセットされたアジア系テキストのように横向きにセットされ得る。
【００３０】
好ましい実施例においては、Proceedings of the Symposium on Document Analysis and Information Retrieval （文書解析及び情報検索のシンポジウム議事録）の中のイットナー(Ittner ）の"Automatic Inference of Text line Orient-ation（テキストライン配向の自動推論）" に記述されている技術の変更を用いて、テキスト配向決定手段４６が画像が水平にセットされるか否かを決定する。イットナーのシステムは文字間のスペーシングがライン間のスペーシングより小さいことを示すことによって文書のテキストライン配向を決定する。イットナーは次いで、連結成分の中心の最小全域木（スパニングツリー）を組み立てることによってテキストラインの配向を見つける。テキスト文書においては、相当多くの木の枝が異なるライン上の隣接文字間でよりもテキストライン内の隣接文字同士の間で見られる。木の枝が主要（ドミナント）方向を有する場合、テキストラインの配向はそれに従って表される。イットナーのシステムにおいて、最小全域木は（ヴォロノイ図式（Voronoi ）に基づいて）ドローネ（Delaunay）の三角測量を構成することによって組み立てられる。本発明のシステムにおいてはこのステップが省略され、代わりに、プリム（Prim）のアルゴリズムが最小全域木を形成するために使用される。プリムのアルゴリズムは既に木に存在している節（ノード）と木に存在していない節の間に最短の枝を追加することによって作用する。概して、これは計算コストが非常に高い。従って本発明のシステムは閾値ヒューリスティックを使用して、コストを最小にする。しかしながら、これは真の全域木より、むしろ近傍の最小全域木を生成する。この閾値ヒューリスティックは各ペア（対）のポイント（点）間の距離を決定する。この距離が多数の連結成分に依存するカットオフ（削除）の値より大きな場合、この距離は無視される。従って、連結成分のペアは距離によって分類される。この近傍の最小全域木は少なくとも一つの部材がこの木に未だ追加されていない第１のｎ−１個のペアを追加することによって構成される。
【００３１】
このように、テキスト配向決定手段４６は、解析軸を画像の主軸に対して大雑把に位置合わせする。しかしながら、画像の主軸の配向を決定するだけでは、解析軸を画像軸と位置合わせするのに充分ではないかもしれない。図２の（ａ）に示したように、水平画像から全体画像のグローバル（広域的）スキュー（傾斜）角度を補償することが必要であるかもしれない。これを行うために、画像軸検出（配置）手段４０が画像軸と解析軸の間でこれらが位置合わせされるように回転を与える。これは概念的には画像が適切な軸と位置合わせするまでページ全体を回転させることに等しい。しかしながら、たとえページ画像全体において主要スキュー角度を補償したとしても、それが正確なテキストのパラメータ化を可能にするのに充分な調整ではないかもしれない。従って、個々のライン又はラインの小さなグループがページ全体の一般的な配向に相対してスキュー角度を有している。
【００３２】
図２の（ａ）に再び戻って、図２の（ａ）に示したテキストのスキューラインが全体画像ではなく、画像の一部分だけを備え、画像の残りの部分をページ画像の主軸と位置合わせされている場合、連結成分移動及び回転手段４２は個々のスキューラインを主軸と位置合わせされるまで回転する。図２の（ｂ）に示したように、連結成分移動及び回転手段４２によって与えられた回転により画像の連結成分が画像の主軸に相対してわずかに回転する。美的な見地から、個々の連結成分の回転を補償することが所望されるかもしれない。これが所望されれば、それも連結成分移動及び回転手段４２によって実行され得る。しかしながら、実施上、ページ画像に用いられる大部分のアルゴリズムは、グローバルスキューとは対照的に、少量の局所的回転に対する許容度が極めて高い。
【００３３】
連結成分移動及び回転手段４２は、スキュー角度を検出することによって起こり得るスキューを検出し且つ補正するが、これは１９８７年の「写真科学とエンジニア社会」会議議事録に"The Skew Angle of Printed Documents" と題してベアド（Baird ）が記載した技術に基づく。スキュー角度が検出されると、個々の連結成分はそれらの原点が画像座標システムに適切に位置合わされるように移動されるが、上記に示したように個々の連結成分のあらゆる回転を残し続ける。
【００３４】
位置合わされ、移動され、且つ恐らくは回転された境界ボックスは、次いで、垂直収縮手段３２へ出力される。この垂直収縮手段３２は、画像内の各境界ボックスの多数の水平に広がる画素の行（ロー）を除去することにより画像を垂直に収縮する。境界ボックスを垂直に拡げるのではなく、境界ボックスの垂直な拡がりを収縮することにより、境界ボックスの中心は変位しないが、垂直に位置合わされた連結成分同士の間に異常に大量の白色空間（レディング）を創成する。次いで、垂直収縮手段は、スプレイイングの場合のように、別の座標系に頼ることを必要とせずに、画像のラインを分離することができる。さらに、垂直収縮手段は、垂直スプレイイング手段のように、このようなスプレイイングが必要とされるか否かによって動作する。収縮が必要とするメモリ及び計算の資源はスプレイイングより相当少ないので、システムは一層効率的となる。
【００３５】
即ち、文書のテキスト部分内のラインが白色空間又はレディングの可変量だけ分離され、且つレディングは現在ラインの文字と垂直に隣接するラインの文字と間で、線形の水平の白色パスとして画定される。概して、アジア系活字書体は巧く作用して、且つ連結成分の上に出るアセンディング部分と下に出るディセンディング部分を持たない。従って、アジア系活字書体におけるテキストのラインを収縮せずに明確に検出することが通常は可能である。これとは反対に、欧州系活字書体は巧く作用せず、通常は、アセンディング部分とディセンディング部分を有している。図３の（ａ）と（ｂ）に示したように、これらのアセンディング部分とディセンディング部分が、しばしば、接触したり又は単に水平に重なったりするので、これらの部分を垂直方向に最初に収縮しないで、欧州系活字書体の文書のテキストのラインを曖昧でなく検出するのは難しい場合が多い。
【００３６】
しかしながら、収縮のコストは、消費する時間や必要とされる処理能力の点で非常に低い（且つスプレイイングよりもっと低い）ので、活字書体及び／又は収縮を必要とする特定のラインを決定しようと試みるより、活字書体に関わらず（且つ好ましくは活字書体を最初から決定しないで）全てを垂直に収縮する方がもっと簡単である。当然、収縮コストが高くなるようならば、本発明は画像の一部の収縮が必要か否かを決定するための手段を含むように容易に改良され得る。
【００３７】
図３は、（ａ）において、サンプルテキスト部分を示し、（ｂ）において、サンプルテキスト部分の各連結成分を取り囲む境界ボックスを示し、且つ（ｃ）において、境界ボックスの垂直に収縮された部分を示す。図３の（ａ）及び（ｂ）から、"Fuji"の"j" の周りの境界ボックスが、"3400"内の最初の"0" の境界ボックスと接触しているのが明らかである。しかしながら、"j" と"0" の連結成分の拡がりを垂直方向に減少するために垂直収縮を用いた後、図３の部分（ｃ）に示したように、各ペア（対）の垂直な隣接ライン同士の間に中断されない白色空間が生じる。
【００３８】
メモリ資源における計算量の減少や、別の座標空間の使用を回避すること以外に、垂直収縮手段は、特定の画像に対する境界ボックスに適用されるべき収縮の量や限界を調整することもでき、これによって垂直収縮手段３２は異なる書体サイズに容易に適合できる。さらに、垂直収縮手段３２は、一般に、各境界ボックスの高さを約１０％収縮しようと試みる。垂直収縮手段３２は、収縮が中心の位置に影響を与えないように、残っている画素の数が奇数であることを確実にしようと試みる。さらに、いくかの画素のロー（行）が除去される場合、最低三つのローが除去されるが、結果的に生じる収縮された境界ボックスは、垂直な拡がりにおいて３画素未満に縮退されることは決して許容されない。従って、たとえ、第１のラインの"j" の境界ボックスが第２のラインの"0" の境界ボックスに食い込んだとしても、図３の（ｃ）に示したように、今度は、図３の（ａ）及び（ｂ）の第１のテキストラインと第２のテキストラインの間に線形の水平線を引くことが可能である。
【００３９】
画像を垂直に収縮した後で、垂直収縮手段３２はどの連結成分及び境界ボックスがテキストの各ラインを備えるかを決定する。即ち、垂直中心が垂直に収縮されたラインプロファイルによって形成されたテキストラインの境界内のあらゆる連結成分はそのラインの中に含まれている。これは、当然、その連結成分の全てを完全に包含するためにラインの拡大に帰着する。従って、図３の（ａ）及び（ｂ）における第１と第２のラインと同様に、テキストラインのトップ位置とボトム位置が重なったとしても、それらは正確に且つ明確に決定され得る。ラインと対応する連結成分のリストは次いで画像メモリ２６及び／又はメモリ１１２に記憶される。
【００４０】
ラインと対応する連結成分のリスト、及び画像を有する元の収縮されない信号部分は、次いで、ベースライン位置合わせ手段４４へ出力される。ライン見当合わせ又は位置合わせはテキストラインの文字のベースラインを位置合わせするための処理である。実際の所望されるベースラインは、通常、文字"g" におけるようなディセンダ（下に出る部分）やコンマのような句読点の存在のために、特徴付けることが難しい。従って、ベースライン位置合わせ手段４４は、最初に、それらの各文字セルのボトムに置かれていない成分のためのラインの連結成分に対するモーダルボトム位置を計算する。次いで、ベースライン位置合わせ手段４４はベースラインの連結成分を位置合わせする。例えば、アクセント、"i" や"j" の上の点（ドット）、疑問符、感嘆符、セミコロン、及びコロンの上部成分がノン・ベースライン成分として分類される。即ち、他の連結成分が所与の連結成分より下に置かれている時、所与の連結成分はノン・ベースライン成分として分類される。
【００４１】
これの一つの結果として、下に垂直に位置合わせされた成分を全く持たない引用符やアポストロフィ（’）が、ベースラインの成分であると考えられることが理解されよう。これは反直感的に思えるかもしれないが、この分類はシステムの性能上何ら悪影響を与えない。
【００４２】
ベースライン位置合わせ手段４４は、文字セル同士間のベースライン位置における小さな変化（ばらつき）を除去しながら、ノン・ディセンディング（下に垂れない）文字に隣接しているディセンディング（下に出る）文字によって、尖った非連続性を許容する点において高域フィルタと類似的に動作する。ベースライン位置合わせ手段４４は、ベースラインの成分ごとに、連結成分のボトムとその左に隣接するベースライン成分の近傍の間の相対的垂直オフセットを計測し且つ記憶する。ラインの始まりにおいて、ベースライン位置合わせ手段４４は、欠けている左側に隣接するベースラインの近傍の代わりに、モーダルボトム位置を使用する。
【００４３】
次いで、ベースライン位置合わせ手段４４は、モーダルベースラインへベースラインの連結成分を引き寄せて、完全なベースライン位置合わせを提供するが、アセンディング（上に出る）文字やアポストロフィのボトムをモーダルベースラインへ一時的に位置合わせするにすぎない。一方、ノン・ベースライン成分はそれらの境界ボックスのそれらの対応するベースライン成分に等しい距離を移動される。この処理は図４の（ａ）乃至（ｃ）に示されている。図４の（ａ）は、終りが自明的に垂れ下がるワープした（歪んだ）テキストのラインを示す。上記に述べたように、図４の（ｂ）に示したように、テキストのラインを備える文字のボトム位置の全てがモーダル位置へ位置合わせされる。図４の（ｃ）に示したように、隣接文字間の相対的垂直オフセットが、ディセンダ（下に出る部分）を下へ移動し且つアポストロフィや疑問符を上へ移動するために呼び戻され且つ使用される。連結成分移動及び回転手段４２を用いると、個々の連結成分が座標軸に相対して回転されることは理解されよう。ベースライン位置合わせ手段４４と垂直収縮手段３２の動作がシステムの動作に影響を与えずに反転され得ることもまた理解されよう。
【００４４】
一旦、境界ボックスが収縮され且つあらゆるワープが除去されると、画像は垂直プロファイル手段３４へ出力される。垂直プロファイル手段３４は、収縮されない画像に対してテキストの各ラインのトップとボトムの位置及び最右及び最左位置を決定する。垂直プロファイル手段３４は、最初に、テキストの各ラインの連結成分の垂直分布プロファイルを生成する。垂直分布プロファイルから、図８に示したようにテキストの一つのラインのトップとボトムの位置が明確に設定され得る。
【００４５】
垂直プロファイル手段３４は、次いで、既に決定されているベースライン位置に相対するテキストのライン毎に垂直プロファイルの最も上と最も下の位置を決定する。図８に示したようにテキストラインのボトムポイント、垂直分布プロファイルの最下点であるが、図８に示したようにテキストラインのトップポイントは垂直プロファイルの最上点である。垂直プロファイル手段３４は次いでラインの連結成分のトップ位置だけの一つの追加垂直部をテキストのラインごとに生成する。このｘ−ライン位置は、一般に、トップ位置垂直分布プロファイルのピーク（頂点）の垂直位置である。アセンディング又はディセンディング連結成分を持たないテキストラインにおいて、トップとｘ−ラインの位置は一致するであろう。さらに、高い割合のアッパーケース（大文字を収納するケース）又はアセンディング文字を有するテキストラインにおいて、ｘ−ラインの位置を正確に決定することは可能ではないかもしれない。全てのラインが一旦垂直プロファイル手段によって動作されると、ラインと、各ラインに対応しているベースラインに相対するボトム、トップ、ベースライン、及びｘラインの位置のリストは、画像メモリ２６へ出力される。テキストの一つのラインと対応している連結成分は、全体的にトップとボトムの位置の間に収容されるような連結成分である。
【００４６】
全てのラインがｘ−ハイト（高さ）のアセンダ及びディセンダ文字のミックス（混合）を含むわけではないことが理解されるべきである。これを補償するため、均一のラインサイズの領域において、垂直プロファイル手段３４は全てのラインに対するモーダルディセンダレングス（長さ）、モーダルｘ−ハイト、及びモーダルアセンダハイトを計算する。次いで垂直プロファイル手段は全ての含まれるラインに対してこれを反復する。ラインの測定されたディセンダサイズが、モーダルディセンダレングスの半分より少ないか又は等しい場合、そのラインのディセンダレングスはモーダルディセンダレングスへセットされる。さらに、ラインのモーダルアセンダハイトが、モーダルアセンダハイトと２０％も違わず（即ち、モーダルアセンダハイトの８０％乃至１２０％）且つそのラインのｘ−ハイトがモーダルｘ−ハイトの７０％より下か又は等しい場合、垂直プロファイル手段はそのラインのｘ−ハイトをモーダルｘ−ハイトに等しくセットする。特に、これは、"DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS" （全て大文字）のようなテキストのラインにおけるようにディセンダを持たないライン及びｘ−ハイト文字を持たないラインを処理するときに非常に良好に作用する。
【００４７】
次いで、複数の信号部分と、画像の各ラインに対応する連結成分及び境界ボックスのリストが空間特徴決定手段３６へ出力される。空間特徴決定手段３６の水平収縮手段３６０は、二つ又はそれより多くの独立した連結成分に対応する二つ又はそれより多くの境界ボックスのあらゆるオーバーラップ（重なり）（又は偶発的合字）を取り除くため、図３の（ｂ）に示したように、単一ラインの非収縮境界ボックスを水平に収縮する。
【００４８】
水平収縮手段３６０は垂直収縮手段３２と同様に動作するが、画像のテキストの各ラインの各境界ボックスの垂直の寸法ではなく水平の寸法において動作する。
【００４９】
一般に、テキストのライン内の文字と文字は白色空間の可変量によって分離され、且つ白色空間は現在ライン内の線形垂直白色パスとして画定されている。また、アジア系の活字書体は通常、良好に作用するので、文字の間にこのような白色空間が存在することを確実とするためにアジア系の活字書体文書のラインを水平に収縮することはあまり必要ではない。対照的に、相対的に離間される欧州系の活字書体において、文字とワードは通常白色空間によって分離されるが、ワード内及びワード間の白色空間の量と分布が非常に変化しやすい。それはしばしば使用されるフォント（字体）により、人間によって認識できるほど正確に垂直である必要はなく、且つ意図的に省略されてもよい。極めて低コストの収縮のお陰で、概して、画像の活字書体や特定のラインの収縮が必要か否かを決定することは必要がないばかりか所望されもしない。しかしながら、上記のように、収縮のコストが高くなるような場合、このような情報を得ることができる。
【００５０】
概して、ラインの最左から最右までの広がりは、ワードデリミタ（区切り記号）であると仮定される。ハイフォン付のワードは必要ならば下流処理によって再度組み立てられなければならないことが理解されるべきである。ラインの中で、有効な横幅の空間は、最初にライン内の成分の位置を見ることによって発見される。連結成分間の空間の分布は一般にバイモーダル（二つのモーダル）である。即ち、より少ないピークは文字間スペースと対応するが、より高いピークはワード間スペースと対応する。これらのピークの内の一つ又は両方が欠けることもあることが理解されよう。第１のケースにおいて文字間スペース（又はワード間スペース）が欠けている時、テキストはセットタイト（"set tight" ）にセット（狭い範囲で設定）されてもよい。つまり、テキストはカーニング（はみ出し文字）又は乏しい品質の画像によって文字と文字の間で検出可能なスペースを有さない。これは水平に収縮された境界ボックスの検査によって解決され得る。概して、水平収縮の処理に適用されるヒューリスティックは垂直収縮に対して上記の説明したものと全く同じである。第２のケースにおいて、ワード間スペースは単一ワードを含むライン上又はモノスペースで設定されるアジア系の活字書体のみからなるライン内には存在しない。
【００５１】
次いで、空間（スペース）決定手段３６２は水平に収縮された連結成分において検出可能なスペースの分布を検査する。検出された最も高いピークは最も広いスペースを表す。そのスペースの水平位置が最初の（収縮される前の）連結成分内で発見された文字間（又はワード間）のピークの位置と対応しない場合、それがワードスペースである。それが文字間ピークの位置に対応する場合、ワードスペースがなく、そのラインがライン境界によって区切られた単一ワードを含むと仮定される。ワード境界間のスペースは、それがライン座標か又は連結成分の間隙のいづれから導出されようと、前準備のワードの寸法として使用される。上記に説明したライン境界決定に直接類似している処理において、ワード境界座標は、中心が前準備のワードの寸法内にある連結成分の全てを含むことによって決定される。
【００５２】
画像のテキスト部分の各ラインが解析された後で、ワードスペース決定手段３６２は画像のテキストの各ラインにおける文字とワードのスペースを決定する。ワードスペース決定手段３６２は、各ラインの左右エッジを決定するためのライン拡がり決定手段３６２０、決定されたスペースの幅の分布を生成するためのスペース幅分布決定手段３６２２、及びスペースの幅の分布を解析するためのスペース幅分布解析手段３６２４を備える。スペース幅分布解析手段３６２４は、スペース幅分布内にピークを検出するための分布ピーク検出手段３６２６とワード間又はワード内スペースを表す検出されたピークを決定するための分布ピーク解析手段３６２８を備える。
【００５３】
動作上、ラインの始まりと終りはワードの始まりと終りであると仮定される。次いで、ラインの中では、連結成分同士の間の水平に収縮されたテキスト内のスペースが検出され、且つスペースの幅の分布曲線が生成される。スペースの幅は左に隣接した連結成分の最右エッジと右に隣接した連結成分の最左エッジの間の距離として測定される。概して、分布曲線は、ワード内の文字間の狭いスペースと、ワード間の広いスペースを表すピークを有するバイモーダルである。勿論、一つのピーク又は両ピークが欠けていることも可能である。ワード内スペースを表すより低いピークが見つからない場合、テキストは「セットタイト」されてもよい。スプレイされない（拡げられない）テキスト部分の分布曲線の最も高いピークは水平にスプレイされたテキスト部分の分布曲線と比較される。そのピークが文字間セルスペースと対応していない場合、それはワードスペースである。トップピークが欠けている場合即ちワード間スペースと対応している場合、それはテキストのラインが単一ワードから成ることを意味する。
【００５４】
各ワードの空間的境界内で文字セルが分離される。収縮された境界ボックスの水平プロファイルが生成される。収縮された境界ボックス同士の間の白色空間の垂直パスは、ワードをラインボトムからライントップへ延出し且つ文字間スペースによって左及び右側へ境界付けされた前準備用文字セルへ分割する。これらの前準備用セルは後で要素連結成分を含むように拡大されることが理解されよう。ダブルクォーツ文字、漢字、及びハングル文字のように文字が水平に離されている少数の例において、１文字当たり一つより多くの文字セルが生成されることが理解されよう。水平収縮後の境界ボックスが図５に示されている。図３の（ａ）〜（ｃ）と比較すると、"Avenue"における"Av"におけるように、先にはみ出したペア（kerned pair ）の分割が簡単に実行されることが容易に判断できる。
【００５５】
図３の（ａ）及び（ｂ）のサンプルテキストに示したように、"Fuji"の"uj"や"Avenue"の"Av"のような境界ボックスのオーバーラップ（重なり）を生じるペアカーン（対のはみ出し文字）が頻繁に発生し且つ簡単に補正される。しかしながら、幾つかのフォント（字体）において、図６の（ａ）の"Confidence"における"fi"のような意図的な合字（リガチュア）又は連結成分のオーバーラップが生じる。本発明の好ましい実施例においては、水平収縮手段３６０は隣接境界ボックスの間のあらゆるオーバーラップを取り除くためにテキスト部分の各ラインを水平に収縮する。次いで、各水平に収縮されたラインは、図６の（ｂ）に示したように、ライン内に存在する残りのリガチュアを検出するために解析される。検出されたリガチュアが識別された後、これらは多くても一つの分割点を検出するように解析される。連結成分内の分割点が検出されたら、リガチュアは二つの連結成分へ分割される。これらの二つの新しい連結成分をさらに収縮した後、現在ラインの連結成分が再チェックされて、他にリガチュアが残っているか否かを決定する。
【００５６】
境界ボックスの意図的でないオーバーラップは単に収縮することによって取り去られるが、水平収縮は連結成分間の意図的又は非意図的なリガチュアを取り去ることが不可能である。これらのリガチュアは、これらが単一の連結成分であると識別されると、単一境界ボックスによって表現される。
【００５７】
リガチュアを分離するため、ストローク（線）幅決定手段３６４は、テキストのライン毎にそのラインに対する表現的ストローク幅Ｓw を決定する。平均ストローク幅は特定のテキストラインと対応する複数の連結成分内に存在するランレングスのモーダル値を検出することによって決定される。ストローク幅決定手段３６４は、所定の幅に渡って広い連結成分を検出するためのワイド連結成分検出手段３６４０と、各ワイド連結成分のコスト分布を生成するためのコスト分布生成手段３６４２と、コスト分布内で最小値を検出するためのコスト最小値検出手段３６４４と、単一連結成分を検出された最小値において二つの連結成分へ分割するための連結成分分割手段３６４６を備える。
【００５８】
動作上、代表的ストローク幅Ｓw の３倍を超える幅ＣW を有するライン内の各連結成分が識別され且つ処理される。ストローク幅Ｓw の少なくとも３倍の幅ＣW を有する連結成分を処理するため、この連結成分の各コラム（列）が各隣接コラムとＡＮＤ演算され、且つＡＮＤ演算されたコラムの「オン」画素の数が決定されて、且つ連結成分より１画素狭いコスト分布を生成する。コスト分布は次いで最小値を検出するために解析される。代表的ストローク幅Ｓw より少ない値を有し且つストローク幅Ｓw の１．５倍を超えて対応する境界ボックスの左境界の右側であって右境界の左側へ位置された多くとも最小値１（同じ値を有する二つの又はそれより多くの最小値がある場合、最も左の最小値が好ましい）に対して連結成分は二つの連結成分へ分割される。これは、全ての断片が再チェックされ且つ必要ならば再分割されるまで、結果的に生じた断片ごとに再帰的に用いられる。図７の（ｂ）に示したように、"Confidence"における"fi"のようにリガチュアが意図的である場合、最小値が発見されないことが頻発する。この場合、リガチュアは単一文字として処理される。
【００５９】
本発明の方法及び装置が統計に基づいているので、これらは非常にロバストであり且つ非常に低い品質で印刷され及び／又は走査された文書にも耐えることができる。即ち、ディジタルデータ信号又はこのディジタル信号から生成された連結成分が、文書の全ての文字を完全に表現することは必要ではない。本発明は、むしろ、単一連結成分の文字を二つ又はそれより多くの連結成分へ分割したり又は二つ又はそれより多くの分離した連結成分を単一連結成分へ併合したりするような一般的な走査エラーに耐えることが可能である。
【００６０】
水平に収縮されたテキストは、次いで、テキストの各ライン内に文字セルを生成するための文字セル生成手段３８へ出力される。一つ又はそれより多くの垂直に位置合わせされた（即ち水平にオーバーラップしている）連結成分のセット毎に、収縮されない連結成分を囲む文字セルが、文字セル生成手段３８によって形成される。各文字セルの寸法は、テキストの対応するラインのトップ位置からボトム位置まで、即ち図１１に示したように文字セルの連結成分の最も左の位置から文字セルの連結成分の最も右の位置まで拡がる。
【００６１】
上記に説明された活字書体（スクリプト）決定システムの動作の単純化されたフローチャートが図９及び図１０に示されている。ステップＳ１００において、システムがスタートし、且つステップＳ１１０において文書が走査されて、ディジタルデータ信号を発生する。ステップＳ１２０において、ディジタル画像データ信号の連結成分が識別される。ステップＳ１３０において、決定された各連結成分ごとに境界ボックスが生成される。ステップＳ１４０においてテキスト配向を決定し且つステップＳ１５０において主要画像軸を決定することによって、画像がクリーンアップされる。次いで、ステップＳ１６０において、主要画像軸とスキューしているあらゆる残りのラインが主要画像軸と位置合わせされる。さらに、ステップＳ１７０において、回転による補正を必要とするあらゆる文字が、これらの文字は主要画像軸と最大限に位置合わせされるように回転される。次いで、ステップＳ１８０において、あらゆるワープされたテキストラインがモーダルベースラインと反復的に位置合わせされる。
【００６２】
ステップＳ１９０において、テキスト部分は垂直に収縮される。ステップＳ２００において、テキストのラインは収縮されたテキストから識別される。ステップＳ２１０において、各ラインの垂直プロファイルが生成され、且つステップＳ２２０において、トップ、ボトム、最左、最右、及び（恐らくは）ｘ−ハイトの位置が既に決定されたベースラインに相対して決定される。ステップＳ２３０において、各ラインに対応する連結成分と境界ボックスが識別される。
【００６３】
次いで、ステップＳ２４０において、オリジナル画像の各ラインが水平に収縮される。ステップＳ２５０においてモーダルストローク幅がライン毎に決定され、且つステップＳ２６０においてテキスト部分内の可能性のあるリガチュアが検出される。ステップＳ２７０において、検出されたリガチュアは、それらの要素の独立連結成分へ再帰的に分割される。ステップＳ２８０において、各ライン内の文字及びワードのスペースが識別される。ステップＳ２９０において、各ラインの文字セルが識別され且つそれらの寸法が決定される。ステップＳ３００においては、文字セル、対応境界ボックス、及び連結成分のリストが出力される。次いで、ステップＳ３１０において処理が終了する。
【００６４】
【発明の効果】
本発明はテキストライン、ワード、及び文字セルの特徴認識能力を有する改良された光学的文字認識システムを提供する。
【図面の簡単な説明】
【図１】光学的文字認識システムを示すブロック図である。
【図２】図２の（ａ）は、スキューが取り除かれる前のスキューされたサンプルテキスト部分を示す図である。
図２の（ｂ）は、スキューが取り除かれた後のスキューされたサンプルテキスト部分を示す図である。
【図３】図３の（ａ）は、サンプルテキスト部分を示す図である。
図３の（ｂ）は、境界ボックスへ変換された後のサンプル部分を示す図である。
図３の（ｃ）は、垂直収縮後のサンプル部分を示す図である。
【図４】図４の（ａ）は、ワープが最初に取り除かれる前のワープされたサンプルテキスト部分を示す図である。
図４の（ｂ）は、ワープが最初に取り除かれた後のワープされたサンプルテキスト部分を示す図である。
図４の（ｃ）は、ディセンダがベースラインに位置合わされた後のワープされたサンプルテキスト部分を示す図である。
【図５】水平収縮後の図３の（ｂ）のサンプルテキスト部分を示す図である。
【図６】図６の（ａ）は、水平収縮前の第２のサンプルテキスト部分を示す図である。
図６の（ｂ）は、水平収縮後の第２のサンプルテキスト部分を示す図である。
【図７】図７の（ａ）は、連結成分の分割前の第２のサンプルテキスト部分を示す図である。
図７の（ｂ）は、連結成分の分割後の第２のサンプルテキスト部分を示す図である。
【図８】テキストラインの相対位置を表すテキストストリングを示す図である。
【図９】本発明の空間特徴決定方法を示すフローチャートである。
【図１０】本発明の空間特徴決定方法を示すフローチャートである。
【図１１】文字セルや境界ボックスが表示されている図６のテキストサンプルを示す図である。
【符号の説明】
１１０  スキャナ
１１２  メモリ
１１４  汎用ディジタルコンピュータ
【図１】
0003796276.tif 000002
【図２】
0003796276.tif 000003
【図３】
0003796276.tif 000004
【図４】
0003796276.tif 000005
【図５】
0003796276.tif 000006
【図６】
0003796276.tif 000007
【図７】
0003796276.tif 000008
【図８】
0003796276.tif 000009
【図９】
0003796276.tif 000010
【図１０】
0003796276.tif 000011
【図１１】
0003796276.tif 000012