JPS63268081A

JPS63268081A - 文書の文字を認識する方法及び装置

Info

Publication number: JPS63268081A
Application number: JP62093435A
Authority: JP
Inventors: 真野　隆司
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1987-04-17
Filing date: 1987-04-17
Publication date: 1988-11-04
Also published as: EP0287027A3; EP0287027B1; US4926490A; DE3883578T2; DE3883578D1; EP0287027A2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】」朶上の利月公夏本発明は、イメージ走査装置に対して傾けられた文書の
文字を認識する方法に関する。

従来舊術及び間叫博２文書上の文字を認識するために光字的文字認識（ＯＣＲ
）技法が用いられてきた。ＯＣＲ技法は。

文書のイメージを走査し、走査動作により発生されたア
ナログ信号を閾値と比較して文書のイメージを表わす２
通信号を発生し、２通信号をイメージ・バッファに記憶
し、文字イメージを切出し即ち文書のイメージを各文字
の個別イメージに切出し、そして切出された文字イメー
ジを認識して、認識結果を出力する工程を含む。

切出しは、各文字行を分けることを含む、第１Ｂ図を参
照するに、イメージ・バッファ２０２に記憶されている
文書２０１のイメージが示されている。第１Ｂ図は、文
書２０１が走査装置に対して傾かないで走査されたこと
を示している０文字行を互いに分離するために射影技法
が、用いられてきた。全文字の影が射影されて射影２０
３及び２０４を発生する射影２０３及び２０４は、イメ
ージ・バッファ２０２のＹ軸方向における第１及び第２
文字行の位置を表わす。第１Ｃ図に示すように、文書が
走査装置に対して傾けられた場合に問題が生じる１文書
２０５が傾けられると、第１及び第２文字行を含む長い
射影２０７が生じる。この場合、第１文字行の文字は第
２文字行の文字から分離されておらず、２つの文字行は
単一文字行として扱われ両文字行の文字は互いに混合さ
れ、そしてこの文４！２０５のＯＣＲの結果を示す出カ
ブリント・アラ上に単一文字行内に印刷される。

文字行相互間の分離を確実にするには、標準のＡ４サイ
ズの文書の最大傾き角度は約１°である。

更に傾いた文書の文字行の分離を行なうために、特願昭
５６−２０４６３６号は、第１Ｃ図の垂直方向の点線２
０６で示すように文字行を複数個のブロック２０９，２
１０に分け、各ブロック毎にブロック射影２０８を発生
し、ブロック２０９の文字の切出しをブロック射影２０
８に基づいて行なう技法を開示している。更に、１文字
行の文字を認識するために、１つのブロック２０９と次
のブロック２１０の連続性が調べられる。この特願昭５
６−２０４６３６号は上記問題をいくらか解決はするが
、ブロック相互間の連続性を見出すのに複雑なプロセス
を必要とする。射影を用いる技法の固有的な問題点は、
文書の水平方向において文字及び写真が混在する時に十
分に動作しないということである。

ＩＢＭ　Ｊｏｕｒｎａｌ　ｏｆ　Ｒｅ５ｅａｒｃｈ　ａ
ｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ、　１９７１年第１５巻
の第１５３−１６５頁のＲ，Ｌ。

Ｈｏｆｆｍａｎ及びＪ、ＷｏＭｃＣｕｌｌｏｕｇｈの論
文“Ｓｅｇｍｅｎｔａｔｉｏｎ　Ｍｅｔｈｏｄｓ　ｆｏ
ｒ　Ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆＭａｃｈｉｎｅ−Ｐ
ｒｉｎｔｅｄ　Ｃｈａｒａｃｔｅｒｓ”は、近接してい
る文字を分離するアルゴリズムを説明している。走査さ
れた文字の垂直密度即ち各垂直走査線の黒画素の数が調
べられ、そして低密度の走査線が文字相互間の境界とし
て選択される。従って、この論文の方法は本発明のもの
と明らかに相違する。

ＩＢＭ　Ｊｏｕｒｎａｌ　ｏｆ　Ｒｅ５ｅａｒｃｈ　ａ
ｎｄ　Ｄｅｖｅ、ｌｏｐｍｅｎｔ、　１９８２年第２６
巻の第６４７−６５６頁ノに、　Ｙ。

Ｖｏｎｇ、　Ｒ，Ｇ、　Ｃａ５ｅｙ及びＦ、　Ｍ、　Ｗ
ａｈｌの論文“Ｄｏｃｕ＋１ｅｎｔ　Ａｎａｌｙｓｉｓ
　Ｓｙｓｔｅｍ”は、文書のためのオフィス・システム
の概念を示している。ここには、前述の投影法を用いて
文字を切り出すことが示されており、従って、この論文
の概念は、本発明のものとは明らかに相違する。

１９８２年のＰｒｏｃｅｅｄｉｎｇｓ　ｏｆ　６ｔｈ　
ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ　ｏ
ｎ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎにおける
Ｒ、　Ｇ、　Ｃａ５ｅｙ及びＧ、　Ｎａｇｙによる論文
“Ｒｅｃｕｒｓｉｖｅ　Ｓｅｇｍｅｎｔａｔｉｏｎ　ａ
ｎｄ　Ｃ１ａｓｓｉｆｉｃａｔｉｏｎｏｆ　Ｃｏｍｐｏ
ｓｉｔｅ　Ｃｈａｒａｃｔｅｒ　Ｐａｔｔｅｒｎｓ”は
、数個の文字が接続されてしまった場合の切り出しの方
法を説明している。切り出しの最初のステップとして上
記１ｉ１ｏｎｇの論文の方法が用いられる。そして、切
り出されたブロックがいくつかの接続された文字のもの
であると思われる場合に用いるアルゴリズムが示されて
いる。この論文の概念は、本発明のものとは明らかに相
違する。

ＩＢＭ　Ｊｏｕｒｎａｌ　ｏｆ　Ｒｅ５ｅａｒｃｈ　ａ
ｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ、　１９８３年の第２７
巻の第３８６−３９９頁のＲ，Ｇ。

Ｃａ５ｅｙ及びＣ，Ｒ，Ｊｉｈによる論文“Ａ　Ｐｒｏ
ｃｅｓｓｏｒ−Ｂａｓｅｄ　ＯＣＲＳｙｓｔｅｍ”はＯ
ＣＲシステムの一般的方法を説明している。このアルゴ
リズムでは、基線の検出後に文字が切り出される。又、
決定クリ−のアルゴリズムが示されている。この論文は
、本発明の考えを示していない。

１９８４年のＰｒｏｃａｅｄｉｎ’ｇｓ　ｏｆ　ＩＥＥ
Ｅ７ｔｈＩｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅ
ｎｃｅ　ｏｎ　ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ
におけるＲ、　Ｇ、　Ｃａ５ｅｙ、　Ｓ、　Ｋ、　Ｃｈ
ａｉ及びに、　Ｙ、　Ｖｏｎｇによる論文“Ｕｎｓｕｐ
ｅｒｖｉｓｅｄＣｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　Ｄｅ
ｃｉｓｉｏｎ　Ｎｅｔｗｏｒｋｓ　ｆｏｒＰａｔｔｅｒ
ｎ　Ｃ１ａｓｓｉｆｉｃａｔｉｏｎ”は認識アルゴリズ
ムを示すに留まり、切り出しについては述べていない。

問題、べを　決する手段従って１本発明の主な目的は、文書の文字及び記号を認
識する方法及び装置を提供する事である。

本発明の他の目的は、イメージ走査装置に対して傾けら
れた文書の文字及び記号を認識する方法及び装置を提供
することである。

文書はイメージ走査装置により走査され、そして文書の
イメージを表わすイメージ・データはイメージ記憶手段
に記憶される。イメージ記憶手段内の複数文字行の各イ
メージの外側境界に接してこれを囲む矩形が発生され、
そしてイメージ記憶手段のＸＹ座標における矩形の４つ
の辺の位置が検出される。この検出された４つの辺の位
置に基づいて矩形の寸法が計算され、そして各矩形の寸
法が、認識されるべき文字及び記号に対して予期される
寸法のレンジと比較される。この寸法のレンジ内に入る
矩形の位置が位置データとして第１テーブルに記憶され
、この時複数文字行に亘る文字及び記号の矩形の位置デ
ータは、ＸＹ座標のＸ軸の方向に沿う一端の矩形から他
端の矩形の順序で第１リストに配列される。

第１リストの矩形の位置データが上記配列順序で逐次的
に取出されて各矩形の寸法が調べられそして全矩形の平
均寸法が調べられる。再び第１リストの矩形の位置デー
タが上記配列の順序で逐次的に取出され上記平均寸法を
基にして設定された寸法レンジに入る第１矩形が見い出
される。この取り出し動作は続けられ、第１矩形の左下
角からのＸ及びＹ方向の予定距離内に左下角がある第２
の矩形が見い出される。この取り出し動作が続けられ、
第２矩形の左下角からのＸ及びＹ方向の予定距離内に左
下角がある第３矩形が見い出される。

この条件を満たす１文字行の予定数の矩形を見い出すよ
うに上記動作が続けられる。予定数の矩形が見い出され
ると、これらの矩形の左下角の位置に基づいてＸＹ座標
におけるこの文字行の傾きが計算され、そしてこの検出
された傾きを文書の傾きとして扱う。

再び第１リストの矩形の位置データが上記配列の順序で
逐次的に取り出されそしてＹ軸における各矩形の下辺の
位置が上記文書の傾き分だけ補正される。この補正され
た位置を本明細書では板想位置と呼ぶ、この取り出し動
作の間に計算された板想位置のうち、文書上の一番高い
位置にある板想位置が検出され、そしてこの検出された
一番高い板想位置がレジスタに記憶される。

再び、第１リストの矩形の位置データが上記配列順序で
逐次的に取り出され、そして各矩形の板想位置が再び計
算される。そして、各矩形の位想位置が、上記レジスタ
に記憶されている最も萬い位置からの予定レンジ内に入
るか否かの比較が行なわれる。このレンジは、例えば小
文字のｐ、　ｙの如く文字の基線よりも下に延びる脚部
を有する文字の矩形を補えるように選択される。この取
り出し及び比較動作の間、上記レンジ内に入る矩形の位
置データが第１リストから第２リストに移され、そして
この動作の終了時には、第１文字行の矩形の位置データ
が、第１文字の矩形から最後の文字の矩形の順番で第２
リストに記憶され終えている。

認識ユニットは第２リストに記憶されている矩形の位置
データを逐次的に取り出し、これらの位置データにより
指定される矩形により囲まれている上記イメージ記憶手
段内のイメージ・データを読出し、そしてこのイメージ
・データを認識する。

ヌー施夛−の一説−功− 第１Ａ図を参照するに、複数文字行を含む文書１が示さ
れている。図を簡単にするために、３文字行だけが示さ
れている。更に、本発明の理解を容易にするために、文
書上の文字の間隔は水平及び垂直の両方向において実際
の文書の場合よりも広げられている。従って、各文字行
は第１Ａ図に示されたよりも多い文字を含む。

文書はＸＹ座標において傾斜角度θだけ傾けられて示さ
れている。

文書１は第２図に示す文書走査装置２１により走査され
る。文書走査袋＠２１には、光源、光学的センサ・アレ
イ及びこれらに対して文書１を相対的に移動させる手段
が設けられている。光学的センサ・アレイは、２．５４
ｃｎ当り２４０画素の密度即ち解像度で配列された例え
ばＣＣＤ素子の如き複数個の光学的感知素子を含む。例
えば２１０ｍの幅のＡ４サイズの文書を走査するには２
０１６個の光学的センサ素子を水平方向に配列すること
が必要であり、そして各素子は１画素を形成する。光源
からの光は文書１により反射され、そして文書のイメー
ジを表わす反射光が光学的センサ・アレイにより検出さ
れ、画素のアナログ信号が発生される。アナログ信号は
第２図の閾値回路２２に供給され、そしてこの回路は、
アナログ信号を閾値レベルと比較する。もしもアナログ
信号が閾値レベルを超すならば閾値回路２２は白レベル
を表わす２進０信号を発生する。もしもアナログ信号が
閾値レベルを超えないならば、閾値回路２２は黒レベル
を表わす２進１信号を発生する。

水平方向に１列で配列された光学的センサ素子は第１Ａ
図の走査線２を規定する。文書１が光学的センサ素子に
関して相対移動されるにつれて、走査線２は文書１の上
をＹ方向に下方に移動し、そして文書１のイメージは逐
次イメージ・バッファ２３に記憶される。

第２図に制御ユニット２０が示されている。制御ユニッ
ト２ｏは、第２図の全ブロックの動作を制御する。図面
を簡略にするために、制御ユニット２０及びブロックの
間の接続は第２図に示されていない。

本発明に従う処理動作は概略的に次のように分けられる
。

（Ａ）文書のイメージの走査及び記憶。

（Ｂ）テーブル・メモリ２５に第１リストを作成するた
めの文字イメージの切出し、及びこれの位置の検出。

（Ｃ）文書の傾き角度の検出。

（Ｄ）テーブル・メモリ２５の第１リストの内容の配列
を変えてテーブル・メモリ３０に第２リストを作成。

（Ｅ）第２リストの内容により指定される文字イメージ
の認識。

上記（Ａ）乃至（Ｅ）について次に詳述する。

−（−Ａ−Σ−匁井Φ／−ん−−２１と走査−及Ｌ１回
憶イメージ・バッファ２３は、文書１の一部分例えば傾
いた文書の３文字行分を記憶する小さな記憶容量２３Ａ
を有するものと仮定する。

制御ユニット２０は、操作者により走査装置２１の開始
スイッチの押し下げ、又は後述する工程（Ｅ）の処理の
終了に応答してイメージ・バッファ２３の記憶動作を開
始する。第１Ａ図に示されているのは文書１の開始部で
あるので、開始スイッチの押し下げｌこより制御ユニッ
ト２０は動作を開始する。制御ユニット２０は走査装置
２１、閾値回路２２及びイメージ・バッファ２３を制御
し。

走査動作を開始し、走査装置２１からの電気的信号を閾
値回路２２に送り、そして閾値回路２２からのイメージ
・データをイメージ・バッファ２３に記憶する。制御ユ
ニット２０は、走査及び記憶動作をモニタし゛、そして
イメージ・バッファ２３がイメージ・データで満たされ
た時に上記動作を停止し、そして次の動作（Ｂ）を開始
する。これらの動作は第３図のブロック３０１及び３０
２として示されている。

Ｂ　テーブル２５に　１リストを作成するため制御ユニ
ット２０は、文字位置検出装置２４を付勢する。これは
、イメージ・バッファ２３をアクセスして上部から下部
に向う順番で水平ビット線のデータを逐次的に取出す。

この動作の目的は、（ｉ）各文字イメージを囲む矩形を
発生することにより各文字イメージを切出すこと即ち走
査された文書のイメージを各文字の個別イメージに分け
ること、（…）イメージ・バッファ２３のＸＹ座標にお
ける各矩形の位置を検出すること、並びに（ｉｉｉ）各
矩形の位置を表わすデータをテーブル２５（第２図）に
記憶して第１リストを作成することである。この動作Ｃ
Ｂ）は第３図でブロック３０３として示されている。上
記（ｉ）、（ｉｉ）及び（ｉｉｉ）の動作の詳細な説明
は次の通りである。

（ｉ）文字位置検出装置２４によって、イメージ・バッ
ファ２３の水平データ・ビット線が上部から下部に向っ
て逐次取出される１文字位置検出装置２４は各ビット線
におけるビット１即ち黒画素の存在を調べ、黒画素のパ
ターンの外側エツジに接する矩形を発生し、そしてＸＹ
座標における矩形の位置を計算する０文字１は、予期さ
れる文字及び記号の寸法よりも小さく若しくは大きい写
真、こすれた黒い痕跡、長い線等を含むことがある６文
字位置検出装置２４は、これ等を検出して、そして無視
する。第１Ａ図及び第４図を参照して詳細に説明すると
、走査線２は、イメージ・バッファ２３のデータ・ビッ
ト線に対応する。ビット線２Ａが文字位置検出装置２４
に送られると、これは文字Ａの上部の黒画素を検出する
。連続するビット線グループ４１が文字位置検出装置２
４に送られるにつれて、この装置は矩形４２を発生する
。文字位置検出装置２４は、供給されるビット線におけ
る黒画連部ちイメージの連続性を調べ、そして連続性を
検出したならば矩形を成長させる。

第４図を参照するに、４３及び４４により示されるよう
にビット線グループ４５及び４６における黒画素の連続
性の存在に基づき矩形は次第に成長される。ビット線２
Ｇはビット線グループ４６の最後のビット線である０文
字位置検出装置２４は、ビット線２Ｃ＋１即ちビット線
２Ｃの次のビット線を調べることによりＹ方向における
黒画素の連続性の欠如を検出する。同様に、文字位置検
出装＠２４はＸ方向における連続性の欠如を検出する。

次いで、文字位置検出装＠２４は、ビット線２Ｂにおい
てＸ方向における黒画素の終端を検出し、そして線２Ｃ
においてＹ方向における黒画速の終端を検出し、そして
矩形の成長を止めて固定し。

これにより文字Ａの連続黒画素グループの外側エツジに
接する矩形４４が発生される。

（ｉｉ）文字位置検出装置２４が矩形４４を完成すると
、これは第４図に示すように、この文字Ａを囲む矩形４
４のＸＹ座標における次の位置を計算する。

ＹＴＡ・・・・イメージ・バッファ２３のＹ軸における
文字Ａの矩形の上のエツジの位置。

ＹＢＡ・・・・イメージ・バッファ２３のＹ軸における
文字Ａの矩形の下のエツジの位置。

ＸＬＡ・・・・イメージ・バッファ２３のＸ軸における
文字Ａの矩形の左エツジの位置。

ＸＲＡ・・・・イメージ・バッファ２３のＸ軸における
文字Ａの矩形の右エツジの位置。

ここで第１番目の文字はＸ若しくはＹ軸を表わし、第２
番目の文字は上、下、左若しくは右のエツジを表わし、
そして第３番目の文字は、完成した矩形により囲まれる
文字を表わす。

ここで１文字位置検出装置２４は、連続した黒画素グル
ープが文字Ａを表わすか否かの識別は行なわないことに
注目されたい。文字位置検出装置２４は、連続した黒画
素グループの夫々に接する矩形並びにこれの位置及び寸
法を検出するだけである。

次に、文字位置検出装置２４は、矩形のＸ及びＹ方向の
寸法が、認識されるべき文字及び記号の予期される寸法
に対して設定された範囲内に入るか否かを調べる。前述
の如く、これの目的は文字及び記号の寸法以外の寸法の
黒点、長い線、写真等を無視することである６文字位置
検出装置２４が上記寸法以外の矩形を見い出した時には
、この装＠２４は、この矩形の位置データを次の工程（
ｉｉｉ）で記憶することなく無視する。

（ｉｉｉ）文字位置検出装＠２４は、下記表１に示すよ
うな第１リストを作成するために位置データＹＴＡ、Ｙ
ＢＡ、ＸＬＡ及びＸＲＡをテーブル・メモリ２５のアド
レス２のエントリイに記憶する。

エントリイ・アドレス１は、テーブル・アクセスが開始
する時の初期エントリイである。文字位置検出装置２４
は、エントリイ１のポインタにアドレス２を記憶する。

このポインタのアドレス２は次にアクセスされるべきエ
ントリイが２であることを示す。エントリイ２のポイン
タＯはこのエントリイ２が最後のエントリイであること
を表わす。そしてテーブル・アクセス動作は終了する。

同様にして文字位置検出装＠２４は、第１Ａ図に示すよ
うに文字１１　ｒＩ＋を囲む矩形４５を完成してそして
位置データＹＴｒ、ＹＢｒ、ＸＬｒ及びＸＲｒを計算す
る。矩形４５の下エツジはビット線２Ｄ上にある。文字
位置検出装置２４は、位置データＹＴｒ、ＹＢｒ、ＸＬ
ｒ及びＸＲｒを表２に示すようにエントリイ３に記憶し
、そしてＸＬｒをＸＬＡに比較して、どちらの矩形が値
ｘ＝Ｏに近いかを調べる。この場合には、文字“Ａ”の
矩形が文字１（ｒＩ＋の矩形の左側にあるので、文字位
置検出装置２４はエントリイ２のポインタとしてアドレ
ス３を記憶する。

文字“Ａ”、“ｒ”′Ｂ”及び“Ｃ”が処理され終えた
時のテーブル・メモリ２５内の第１リストの内容は次の
通りである。

表３＝第１リスト処理が進むにつれ、エントリイのポインタが、ＩＩ　Ｃ
ＩＩ、ＩＩ　Ｂ　Ｈｌ”Ａ”及び”ｒ”の順番で即ち文
書１の左から右へ向う方向で位置データをアクセスする
ように変えられることに注目されたい。

即ち、テーブル・エントリイ１はポインタ５を記憶し、
これはエントリイ５をアクセスする。そしてここには文
字“ＣＩＩの矩形の位置データ及びポインタ４が記憶さ
れているので次にエントリイ４をアドレスしそしてここ
には文字“Ｂ　ＴＪの矩形の位置データ及びポインタ２
が記憶されているので次にエントリイ２をアドレスし、
エントリイ２は文字“Ａ”の矩形の位置データ及びポイ
ンタ３を記憶し、そして文字“ｒ”の矩形のエントリイ
３をアドレスする。

文字位置検出装置２４が新たな矩形を完成する毎に、こ
の装置２４は、この新たな矩形のＸ軸の位置を既に第１
リストに記憶されている古い矩形のＸ軸の位置と比較し
、そしてこれら新たな矩形及び古い矩形のポインタを、
これら矩形に対するアクセス動作がＸ軸の方向の左端の
矩形から右端の矩形へ順序でなされるように修正できる
ことが明らかである。イメージ・バッファ２３に記憶さ
れている全ての文字イメージが処理され終えた時のテー
ブル・メモリ２５内の第１リストの内容を次の表４に示
す。

４：　１リストテーブル・メモリ２５の第１リストのポインタは、第１
リストへの初期アクセスはエントリイ・アドレス１へな
され、そして残りのエントリイは第１Ａ図の下側部分に
示されている順序でアクセスされる。即ち、表４に示す
第１リストにおいて、複数個の矩形の位置データは、イ
メージ・バッファ２３のＸＹ座標のＸ軸の方向において
最も左の矩形から最も右の矩形へ向う順番で配列されて
いる。そして制御ユニット２０は、動作ＣＢ）の終了を
検知しそして次の動作（Ｃ）を開始する。

（Ｃ文書の傾きの検この動作においては文書１の１つの文字行に属する矩形
が取り出され、そしてＸＹ座標における文書１の傾きが
検出される。

詳細な動作は次の通りである。

（ｉ）制御ユニット２０は傾き計算装置２６（第２図）
を付勢する。傾き計算装置２６はテーブル・メモリ２５
の第１リスト（表４）の全てのエントリイをポインタが
示す順番でアクセスして、各矩形の位置データ即ち上下
左右のエツジの値を取出し、そしてＸ及びＹ軸方向にお
ける各矩形の寸法を計算する。そして傾き計算装置２６
は全ての矩形の平均寸法を計算する。この動作は第３図
でブロック３０４として示されている。

（ｎ）値き計算装置２６は再び第１リスト（表４）をポ
インタが示す順序でアクセスして平均寸法から成る許容
範囲内にある第１番目の矩形を見い出す。第１番目の矩
形を見い出すと、傾き計算装置２６はこの矩形の下エツ
ジ及び左エツジのデータ即ち左下角のデータをレジスタ
（図示せず）に記憶する。

説明中の例では、第１矩形は文字りの矩形である。そし
て傾き計算装置２６は第１リストのアクセスを続け、第
１矩形の右側に位置され且つ次の条件（１）及び（２）
を満足し且つ上記許容範囲内にある第２番目の矩形を見
い出す。

Ｘｆ＋Ｘ、≦Ｘｓ≦ｘ　ｆ＋　ｘ、　　−・−・（１）
ｙｔ−ｙ１≦Ｙｓ≦Ｙｆ＋Ｙ、　　・−・・（２）これ
らの値は第５Ａ図で示す位置及び距離を表わす。

Ｘｆ、Ｙｆ・・・・第１矩形５１の左下角の位置。

Ｘｓ、Ｙｓ・・・・第２矩形５２の左下角の位置。

ｘｌ・・・・Ｘｆからの予定距離。

ｘ２・・・・Ｘｆからの予定距離。

Ｙｌ・・・・Ｙｆからの予定距離。

値Ｘ１は、第１矩形が例えば“Ｑ″のように幅の狭い文
字の矩形である場合に対応できるように実験的に選択さ
れる。値ｘ２も、第２矩形が第１矩形からダブル・スペ
ースだけ離れている場合に対応できるように実験的に選
択される。同様に、値Ｙ１及びＹ２も、文書１の最大傾
斜角度５°の場合に対応できる様に実験的に選択される
。値Ｙ２の選択に当って他の考慮すべき点は、文字のベ
ース・ラインよりも下の延長部を有する例えばｉｔ　Ｐ
ｌ＃の如き文字を排除することである。これの理由は、
文書１の傾きが下記に説明する如く、複数個の矩形の左
下角の位置に基づいて決定されるからである。

値Ｘ１、ｘ２、Ｙｌ及びＹ２は、第５Ａ、５Ｂ及び５０
図に示す領域５３を規定する。上述の条件（１）及び（
２）は第２矩形の左下角（Ｘｓ、Ｙｓ）が領域５３内に
入るか否かを決定する。第５Ａ図の第２矩形５２は条件
（１）及び（２）を満足する。第５Ｂ図の第２矩形５５
は条件（１）及び（２）を満足しない。第５Ｃ図の矩形
５７は条件（１）を満足するが、条件（２）を満足しな
い。

傾き計算装置２６が条件（１）及び（２）を満足する第
２矩形（第１Ａ図の場合には文字ｔｉｃ″′の矩形）を
見い出すと、この第２矩形の左下角の位置データを前述
のレジスタ（図示せず）に記憶する。今やこの傾き検出
装置２６のレジスタは第１及び第２矩形の左下角の位置
データを記憶していることに注目されたい。そして傾き
計算装置２６は、第１リスト（表４）のアクセスをつづ
けて第２矩形の領域５３内に左下角が入る第３矩形を見
い出す。第３矩形を見い出すと、傾き計算装置２６は、
この第３矩形（説明中の例では文字“Ｂ”の矩形）の左
下角の位置データを上記レジスタに記憶する。このよう
にして、傾き計算装置２６は、先行矩形の領域５３内に
左下角が位置する一連の矩形を見い出し、そしてこれら
見い出された矩形の数が予定の数、例えば１５に達した
か否かを調べる。この数１５は、標準フォーマットの標
準英文レターは１文字行内に少なくとも１５個の平均寸
法の文字を有するという仮定に基づいて選択された。他
の数を用いることも可能である。　文字りの矩形を第１
矩形として指定することにより開始した上記第１リスト
の第１サーチの終了時には、傾き計算装置２６は、文字
り、Ｃ，Ｂ及びＡの４つの矩形を見い出し終えている。

この数は１５よりも小さいので、傾き計算装置２６は上
記レジスタの値をリセットし、文字Ｃを第１矩形として
指定して第１リストの第２のサーチを開始する。しかし
ながら１文字Ｃ，Ｂ及びＡの夫々の矩形を第１矩形とし
て指定してつづいて３回行なわれるサーチでは、領域５
３に入る即ち条件（１）及び（２）を満足する矩形を１
５個見い出すことはできない。傾き計算装置２６は文字
Ｑを第１矩形として指定することにより第５番目のサー
チを開始する。ここで第１Ａ図の文書１の文字Ｑで始ま
る第２文字行が図では７文字しか含まないように示され
ているが１５個の平均的寸法の文字を含んでいると仮定
する。第５番目のサーチの終了時に、傾き計算装＠２６
は、１５個の矩形が見い出されたことが判る。そして見
い出された１５個の矩形の左下角を表わす位置データは
前記レジスタに記憶されている。傾き計算装置２６はレ
ジスタ内のこれら位置データを取り出し、そしてこの分
野で周知の最小二乗法を用いることにより第２文字行の
傾き角度θを発生する。そして傾き計算装＠２６はこの
傾き角度θを文書１の傾き角度として後の処理で使用す
るために保持する。これらの動作は第３図でブロック３
０５として示されている。

制御ユニットは動作（Ｃ）の終了を検出しそして次の動
作（Ｄ）を開始する。

第１リストの内容の再配列の目的は、第１リストに記憶
されている全ての矩形の中から１文字行に属する文字及
び記号の矩形を見い出して、これらの矩形の位置データ
を取出し、そしてこれらをテーブル・メモリ３０に記憶
して第２リストを作成することである。次の詳細な説明
は、第１Ａ図に示す文ｊｖ１の第１文字行に属する文字
り、Ｃ１Ｂ、Ａの矩形の位置データをテーブル・メモリ
３０に記憶して第２リストを作成する動作に関する。

詳細な説明は次の如くである。

（ｉ）制御ユニット２０は第２図の１行選択装置２７を
付勢する。１行選択袋＠２７は傾き計算装置２６から前
記傾き角度θの値を受けとり、これをレジスタ２８に記
憶する。１行選択装置２７は表４のテーブル・メモリ２
５内の第１リストをアクセスし、ポインタが示す順番に
即ち第１Ａ図の下側部分に示す文字の順番に各矩形の下
エツジ及び左エツジの値を逐次取出す。第１リストから
最初に取出される値ＹＢＤ及びＸＬＤは、ＸＹ座標にお
ける文字りの矩形の左下角の位置を表わす。

１行選択袋＠２７は次の計算を行なう。

ＹＢ＝　（ＸＬＤ　　Ｘ　ｔａｎ　θ）　十Ｙ　Ｂ　Ｄ
・・−・（３）この値ＹＢは、第６図に示す如く、傾き
角度θを補正するように文書上が時計方向に回転された
時のＹ軸方向における矩形の左下角の板想位置を表わす
。この板想位置ＹＢは１行選択装置２７のレジスタ２７
に記憶される。次に、１行選択装置２７は、文字Ｑの矩
形の位置データＹＢＱ及びＸＬＱを取り出しそしてこの
矩形に対する左下角に対する仮想位＠ＹＢを発生し、そ
して文字ａの矩形に対する板想位置ＹＢと文字りの矩形
に対する板想位置ＶＢとを比較して、どちらの値が小さ
いかを調べる。この場合には、文字りの矩形に対する値
ＹＢが選択されそしてレジスタ２９の内容即ち文字りの
矩形に対する値ＹＢは変更されない。

このようにして１行選択装置２７は第１リスト（表４）
の全ての位置データを連続的にアクセスして各矩形毎に
板想位置ＹＢを計算し、そしてレジスタ２９内の古い値
ＢＹに対して新たな値ＹＢを比較し、そしてもしも新た
な値が古い値よりも小さければレジスタ２９内の値を新
たな値に取替える。この結果、全ての矩形のうちで最も
小さい値ＹＢがレジスタ２９に記憶される。最小値ＹＢ
は、第６図に示す如く、文書１上で最も上の位置にある
第１文字行の矩形の値ＹＢを表わす。この動作は第３図
でブロック３０６として示されている。

（…）１行選択装置２７は、テーブル・メモリ２５内の
第１リスト（表４）を、ポインタで指定される順序で即
ち第１Ａ図の下側部分に示す順序で再びアクセスする。

１行選択袋＠２７は、文字りの矩形の位置データＹＢＤ
及びＸＬＤを取出しそして上述の計算（３）を行なう。

そして、１行選択装置２７は、この計算された値ＹＢが
第６図に示すレンジ６１に入るか否かを調べる。レンジ
６１の下限は、基線よりも下に延長部を有する文字例え
ば小文字のｐ及びｙの矩形を補えるように選択されてい
る。この場合、答はイエスであるので、即ち文字りは第
１文字行に属すると判断して、１行選択装置２７は、文
字りの矩形の４つの位置データ即ちテーブル・メモリ２
５の第１リスト（表４）のエントリイアのＹＴＤ、ＹＢ
Ｄ、ＸＬＤ及びＸＲＤを取り出し、テーブル・メモリ３
０の第２リストのエントリイ１に記憶する。又、１行選
択装置２７は、第１リストのエントリイ１のポインタ７
を文字りの矩形のエントリイアのポインタ１３に取替え
、そしてこのエントリイアの内容を消去する。

このポインタの変′更は、消去されたエントリイアをス
キップして次の文字Ｑのエントリイを指すためである。

次に、１行選択装置２７は、第１リストのエントリイ１
３の文字Ｑの矩形の４つの位置データを取出しそして上
述の計算及び比較を行なう。この比較は、文字ａの矩形
に対して計算された値ＹＢが第１文字行に対して設定さ
れたレンジ６１に入らないことを示す。即ち文字Ｑが第
１文字行に属さないことを示す。１行選択装置は文字α
の矩形についてはこれ以上何も行なわず、そしてエント
リイ１３のポインタにより指定されるエントリイ１８を
アクセスし上記の計算及び比較を繰返す。

比較は、文字“ｔ”の矩形の計算値ＹＢがレンジ６１に
入らないことを示し、従って１行選択装置２７は、文字
“ｔ　７１の矩形の処理を終了して、エントリイ１８の
ポインタ５により指定されるエントリイ５をアクセスす
る。エントリイ５は、第１文字行の文字Ｃの矩形の４つ
の位置データを記憶している。比較は文字Ｃの矩形の計
算値ＢＹがレンジ６１に入ることを示し、そして１行選
択装置２７は、文字Ｃが第１文字行に属すると判断する
。

１行選択装置２７は、文字Ｃの矩形の４つの位置データ
即ち第１リストのエントリイ５のＹＴＣｌＹＢＣ，ＸＬ
Ｃ及びＸＲＣを取出してテーブル・メモリ３０の第２リ
ストのエントリイ２に記憶する。又、１行選択装置２７
は、第１リストのエントリイ１８のポインタ５をエント
リイ５のポインタ１２に取替えそしてエントリイ５の内
容を消去する。これによりエントリイ５は後の動作でス
キップされ、文字“ｔ”の矩形の後に文字“ｍ　”の矩
形がつづく。このようにして１行選択装置２７は、第１
リストの各矩形について上述の動作を繰り返し行なう。

第１リストの全エントリイについて上述の動作を終了し
た時点における変更後の第１リスト及び新しい第２リス
トの内容は次の表５及び表６に夫々示す通りである。

第２リストの作成及び第１リストの修正は第３図でブロ
ック３０７として示されている６制御ユニツト２０は動
作（Ｄ）を終了しそして次の動作（Ｅ）を開始する。

一５＝修正ｔの、１リスト壱」−り剃ヱ」ジ（旦各ニーえの一契庫− 第２リストに記憶されている位置データ即ち、ＹＴＤ、
ＹＢＤ、ＸＬＤ、ＸＲＤ、・・・・、ＹＴＡ。

ＹＢＡ、ＸＬＡ、ＸＲＡは、イメージ・バッファ２３内
に記憶されている文字イメージＤ、Ｃ，Ｂ、Ａを夫々囲
む矩形の位置を示すことに注目された゛い。

制御ユニット２０は、認識ユニット３１を付勢すること
により動作（Ｅ）を開始する。認識ユニット３１には、
この分野で周知の文字イメージを認識するための決定ツ
リーが設けられている。この決定ツリーについては詳述
しない。認識ユニット３１は、テーブル・メモリ３ｏの
第２リストのエントリイ１をアクセスして１文字りを囲
む矩形の位置を表わす位置データＹＴＤ、ＹＢＤ、ＸＬ
Ｄ及びＸＲＤを取出す。そして認識ユニット３１は、イ
メージ・バッファ２３のうちこの矩形により囲まれてい
るイメージ・データを取出す。認識ユニット３１は、決
定ツリーを用いて文字りのイメージを認識しそして結果
を出力バッファ３２に記憶する。次に、認識ユニット３
１は、第２リストのエントリイ２の位置データＹＴＣ，
ＹＢＣ１ＸＬＣ及びＸＲＣを取出しそして上述の動作を
行ないそして文字Ｃの認識結果を出力バッファ３２゛に
記憶する。認識ユニット３１は、第２リストに記憶され
ている全ての位置データが使用され終える迄上述の動作
を繰り返す。この動作は第３図でブロック３０８として
示されている。

制御ユニット２０は動作（Ｅ）の終了を検出し、そして
出力バッファ３２の内容を出力装置に供給する。第１Ａ
図に示す文書１の第１文字行の４文字が認識され終えた
ことに注目されたい、制御ユニット２０は、第１リスト
の文字の矩形のうちの最も高い上辺の位置即ち文字ｒの
矩形の上辺の位置を調べる。第１Ａ図を参照するに、こ
の上辺はビット線２Ｂに位置づけられている。制御ユニ
ット２０は、イメージ・バッファ２３の一番上のビット
線とビット線２Ｂとの間の上側記憶領域が、次の文字イ
メージを記憶するのに利用できることが判る。制御ユニ
ット２０は走査装置２１を付勢して上記法の文書イメー
ジを上側記憶領域に記憶し、そしてこの上側記憶領域の
ビット線のアドレスを、最初に記憶された文字イメージ
の最後のビット線２３Ｂに連続するように修正する。即
ち、上側記憶領域の一番上のビット線にはアドレス２３
Ｂ＋１が割当てられ、第２＃ｆｉ目のビット線にはアド
レス２３Ｂ＋２が割当てられ、以下向じようになされ、
その結果イメージ・バッファ２３内において最初に記憶
された文書イメージに対するこの新たに記憶された文書
イメージの連続性が保たれる。

イメージ・バッファ２３が新たな文書イメージで満たさ
れると、制御ユニット２０は動作（Ｂ）乃至（Ｅ）を行
なう。

動作（Ｅ）が終了した時、制御ユニット２０は、文書１
の全文字が認識され終える迄上述の動作を繰返す。各文
字行の認識の終了時に、制御ユニット２０は、例えばプ
リンタ、表示装置等の出力装置に出力バッファ３２の内
容を供給し、これにより操作者は文書１の文字認識の結
果を得ることができる。

反時計方向に傾けられた文書１を用いて本発明を説明し
たが１本発明は時計方向に傾けられた文書の文字を認識
出来ることが明らかである。

実施例においては１文字及び記号の切出しは、ワードの
文字が左から右へ書かれている文書について説明された
。本発明は、第１リストのポインタを文字行の右側から
左端へ向う順序で配列し、そして第５Ａ図の領域５３を
矩形５１の左側に配置することにより反対方向即ち、右
から左に向って書かれている文字及び記号を切出すこと
が可能である。

套Ｊゆ拗ｉ− ３種類のフォント即ちＣｏｕｒｉｅｒ　１０、Ｃｏｕｒ
ｉｅｒ　１２及びＰｒｅｓｔａｇｅ　ｅｌｉｔｅ　１２
を用いそして文字行和瓦間がシングル・スペースの文書
を認識するために本発明を用いた実験は、時計若しくは
反時計方向に最大６″の角度だけ傾斜された文書の文字
が。

文字行の明確な分離を示して、即ち、第２文字行の文字
が第１及び第３文字行に現われることなく認識された。

【図面の簡単な説明】

第１Ａ図は本発明に従って認識されイメージ・バッファ
２３に記憶された傾いた文書のイメージを示す図、第１
Ｂ及び第１Ｃ図は文書の文字イメージを切出す従来技法
を示す図、第２図は本発明の方法を行なう回路構成のブ
ロック図、第３図は本発明の方法のフロー・チャート、
第４図は文字Ａの外側境界に接する矩形の４つのエツジ
の位置の検出を示す図、第５Ａ図、第５ＢＬｉ！ｌ及び
第５Ｃ図は先行する矩形の左下角からＸ及びＹ軸方向の
所定距離内に左下角が位置する矩形の検出を示す図、第
６図は矩形の板想位置の発生を示す図。１・・・・文書、２０・・・・制御ユニット、２１・・
・・走査装置、２２・・・・閾値回路、２３・・・・イ
メージ・バッファ、２４・・・・文字位置検出装置、２
５・・・・テーブル・メモリ、２６・・・・傾き計算装
置、２７・・・・１行選択装置、３１・・・・認識ユニ
ット、３２・・・・出力バッファ。出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション代理人　　弁理士　　岡　　１）　次　　生（外１名）第１Ｃ図第１Ｂ図ＹＸＬＡ　　　　　　　　　ＸＲＡ第４図第５Ａ図

Claims

【特許請求の範囲】

（１）文書のイメージをイメージ記憶手段に記憶し、上
記イメージ記憶手段に記憶されている複数文字行の各文
字イメージの外側境界に接する矩形の上記イメージ記憶
手段のＸＹ座標内の位置を検出して上記矩形の位置を表
わす位置データを発生し、上記ＸＹ座標のＸ軸の方向の
一端から他端に向う順序で複数個の上記矩形の位置デー
タを配列したリストを作成し、上記リスト内の上記位置データのＹ座標情報に基づいて
１文字行のＹ座標レンジを検出し、上記Ｙ座標レンジに
入る矩形の位置データを用いて上記イメージ記憶手段か
ら上記文字イメージを読出し認識することを特徴とする
文書の文字を認識する方法。
（２）文書のイメージを表わすイメージ・データをイメ
ージ記憶手段に記憶し、上記イメージ記憶手段に記憶されている複数文字行の各
文字イメージ・データの外側境界に接する矩形の上記イ
メージ記憶手段のＸＹ座標の位置を検出し、上記矩形の
位置を表わす位置データを発生し、上記矩形の位置データを記憶して、上記複数個の上記矩
形の位置データを、上記ＸＹ座標のＸ軸の方向の一端か
ら他端に向う順序で配列した第１リストを形成し、上記第１リストの矩形のうち１文字行に属する予定数の
矩形を選択して該矩形の位置データを調べ、上記ＸＹ座
標における上記文書の傾きを検出し、上記第１リストの各矩形のＹ座標位置を上記傾きだけ補
正した板想位置を発生し、第１文字行に属する矩形の位
置データを上記第１リストから第２リストに移し、上記第２リスト内の上記位置データにより指定される矩
形により囲まれたイメージ・データを上記イメージ記憶
手段から文字認識手段に供給する工程を含む、文書の文
字を認識する方法。
（３）上記矩形の位置を検出する工程は、上記イメージ
記憶手段に記憶された上記文書の個別イメージの外側境
界に接する複数個の矩形を発生する工程と、各矩形が、
認識されるべき文字及び記号に対して予じめ設定された
大きさの範囲に入るか否かを調べる工程を含むことを特
徴とする特許請求の範囲第（２）項記載の文書の文字を
認識する方法。
（４）上記位置データは、上記ＸＹ座標における上記矩
形の上辺、下辺、左辺及び右辺の位置を表わすことを特
徴とする特許請求の範囲第（２）項記載の文書の文字を
認識する方法。
（５）上記位置データを調べる工程は、上記第１リスト
を探索して、先行矩形の左下角からＸ及びＹ軸方向の予
定距離内に存在する矩形を予定の数だけ検出する工程と
、該検出された矩形の左下角の位置の計算を行ない上記
文書の傾きを検出する工程とを含むことを特徴とする特
許請求の範囲第（２）項記載の文書の文字を認識する方
法。
（６）上記仮想位置を発生する工程は、上記第１リスト
の上記矩形の位置データを上記配列の順序で逐次的に読
出す工程と、各矩形のＹ座標位置を上記傾きだけ補正し
た仮想位置を発生する工程、上記文書上の一番高い位置
にある仮想位置をレジスタに記憶する工程と、上記第１
リストの上記矩形の位置データを再び逐次読出す工程と
、該読出された矩形の仮想位置を発生する工程と、該発
生された仮想位置が、上記レジスタ内の上記仮想位置か
らの予定範囲内にあるか否かを調べる工程と、仮想位置
が上記予定範囲内にある矩形の位置データを上記第１リ
ストから上記第２リストに移す工程とを含むことを特徴
とする特許請求の範囲第（２）項記載の文書の文字を認
識する方法。
（７）文書のイメージを記憶する記憶手段と、上記記憶
手段に記憶されている複数の文字の夫々のイメージの外
側境界に接する矩形の位置を検出してその位置データを
発生する手段と、上記位置データのＸ座標情報に基づいて上記矩形をＸ軸
の方向の一端から他端に向けて順序づける手段と、上記順序づけられた矩形のＹ座標情報に基づいて文字行
に属する矩形を選択する手段と、該矩形の位置データを用いて上記記憶手段から文字イメ
ージを取出し該文字イメージを認識する手段とを備えた
文字認識装置。
（８）上記位置データを発生する手段は、各矩形が認識
されるべき文字及び記号の大きさの範囲に入るか否かを
調べ、上記大きさの範囲に入る矩形の位置データを発生
することを特徴とする特許請求の範囲第（７）項記載の
文字認識装置。
（９）上記位置データは、上記イメージ記憶手段のＸＹ
座標における上記矩形の上辺、下辺、左辺及び右辺の位
置を表わすことを特徴とする特許請求の範囲第（７）項
記載の文字認識装置。
（１０）上記順序づける手段は、上記文字の複数文字行
の矩形の位置データを上記ＸＹ座標のＸ軸の方向の一端
から他端に向かう順序で配列して記憶する第１リストを
記憶する第１テーブル・メモリを有することを特徴とす
る特許請求の範囲第（７）項記載の文字認識装置。
（１１）上記矩形を選択する手段は、上記第１リストの
上記矩形の位置データを上記配列の順序で逐次的に読出
し、先行矩形の左下角からＸ及びＹ軸方向の予定距離内
に左下角が存在する矩形を予定の数だけ検出し、該検出
された矩形の左下角の位置に基づいて上記文書の傾きを
検出し、上記第１リストの上記矩形の位置データを上記
順序で再び読出して、各矩形のＹ座標位置を上記傾きだ
け補正した仮想位置を発生し、上記文書上の一番高い位
置にある仮想位置をレジスタに記憶し、上記第１リスト
の上記矩形の位置データを上記順序で再び読出して各矩
形のＹ座標位置を上記傾きだけ補正した仮想位置を発生
し、該発生された仮想位置が上記レジスタ内の仮想位置
からの予定範囲内にあるか否かを調べ、仮想位置が上記
予定範囲内にある矩形の位置データを上記第１リストか
ら第２リストに移すことを特徴とする特許請求の範囲第
（７）項記載の文字認識装置。
（１２）上記認識手段は、上記第２リストの矩形の位置
データを逐次的に読出し該矩形により囲まれたイメージ
・データを上記記憶手段から読出して認識することを特
徴とする特許請求の範囲第（７）項記載の文字認識装置
。