JPH0727543B2

JPH0727543B2 - 文字認識装置

Info

Publication number: JPH0727543B2
Application number: JP63104469A
Authority: JP
Inventors: 洋治中村; リチャード・ジイ・ケーシ; 和治豊川
Original assignee: インターナシヨナル・ビジネス・マシーンズ・コーポレーション
Priority date: 1988-04-28
Filing date: 1988-04-28
Publication date: 1995-03-29
Anticipated expiration: 2010-03-29
Also published as: JPH01277981A; EP0343786A2; EP0343786A3; CA1317377C; US5394484A

Description

【発明の詳細な説明】産業上の利用分野本発明は、パターン認識装置に関する。更に具体的に言
うならば、本発明は、パターン若しくは文字のイメージ
を認識している間に、誤って認識されたパターン若しく
は文字のイメージに基づいて文字認識手順を修正する装
置に関する。

従来技術及び問題点イメージ走査装置により読取られた文書の印刷文字のイ
メージをパーソナル・コンピュータに入力して文字認識
アルゴリズムにより文字認識を行なうシステムが開発さ
れてきた。このシステムにおいては、高速の文字認識が
望まれるので、文字イメージの特定な画素即ちペルを逐
次的にサンプルし、サンプルされた画素が白であるか若
しくは黒であるかに応じて複数のノードをたどるいわゆ
るポイント・サンプリング型の文字認識ツリーが用いら
れる。この文字認識ツリーはタイプ・フォント毎に用意
される。一且完成した文字認識ツリーを他のフォントの
文字を認識するように修正することは非常に困難なの
で、頻繁に用いられるタイプ・フォントの種類の数だけ
文字認識ツリーを予じめ用意しておく。例えば30種類の
フォントの文字認識ツリーを予じめメモリに記憶するこ
とが、行なわれる。従って、記憶されたツリーのフォン
ト以外のフォントの文字が文書に含まれる場合は認識率
は著しく低下する。

IBMジャーナル・オブ・リサーチ・デベロップメント、1
983年７月、第27巻、第４号号の第386−399頁のR.G.Cas
ey及びC.R.Jikによる論文“A processor-based OCR sys
tem"は３つのツリーを１組として用い、そして各ツリー
からの結果を如何に組合わせるかを示している。

コンピュータ・グラフィックス及びイメージ・プロセッ
シング1982年第20巻の第375−390頁のF.M.Wahl、K.Y.Wo
ng及びR.G.Caseyによる論文“Block Segmentation and
Text Extraction in Mixed Text/Image Documents"は、
印刷文書のテキスト領域及び非テキスト領域を自動的に
区別する方法を示している。

The 6th International Conference on Pattern Recogn
ition、1982年10月のR.G.Casey及びG.Nagyによる論文
“Recursive segmentation and classification of com
posite character patterns"は、文字を効率的に切出し
そして認識するために如何に決定ツリ方法を用いるかを
示している。

IEEE Transaction on Information Theory、1984年１
月、第IT30巻第１号の第93−99頁のR.G.Casey及びG.Nag
yによる論文“Decision Tree Design Using a Probabil
istic Model"及びIBMテクニカル・ディスクロジャ・ブ
リティン、1979年８月第22巻、第３号の第1189頁のR.G.
Caseyによる論文“Automatic generation of OCR logic
from scanned characters"は、画素の確率から決定ツ
リーの数学的モデルを作ることを示している。

IEEE 6th International Conference on Pattern Recog
nition、1982年10月のK.Y.Wong、R.G.Casey及びF.Wahl
による論文“Document Analysis System"は、文書をテ
キスト領域及び非テキスト領域に区切って読取る適応性
OCRを示している。

IEEE 7th International Conference on Pattern Recog
nition、1984年８月のR.G.Casey、S.K.Chai及びK.Y.Won
gによる論文“Unsupervised construction of decision
networks for pattern classification"並びにR.G.Cas
ey及びT.D.Friedmanによる米国特許第4499596号は共
に、全体のパターンを比較する前にテキスト文字の画素
のいくつかを前以って調べることにより認識の速度を高
めることを示している。

IBMテクニカル・ディスクロジャ・ブリティン、1987年
８月、第30巻第３号の第112−1114頁の論文“Automatic
Font Selection for Chanacter Recognition"は、文書
の文字が複数個のタイプ・フォントのうちどのフォント
で印刷されているかを調べることを示している。

問題点を解決するための手段パターン若しくは文字認識アルゴリズム即ち文字認識手
段の制御のもとに文書走査装置は、文書上のパターン若
しくは文字のイメージを光学的に走査し、そしてこのイ
メージを表わす２進１若しくは０のイメージ・データを
発生する。本明細書では説明を簡略化するために、この
２進１若しくは０のイメージ・データを単にパターン若
しくは文字のイメージと呼ぶ。文書１ページのパターン
若しくは文字のイメージは文字認識アルゴリズムの制御
のもとにイメージ・バッファに記憶される。そして個々
のパターン若しくは文字のイメージが切出されて作業バ
ッファに記憶される。文字認識アルゴリズムは作業バッ
ファ内のイメージを認識しそしてその結果を結果バッフ
ァに記憶する。文字認識アルゴリズムは、認識の確率の
高い文字に対してはこれの文字コードを結果バッファに
記憶し、認識の確率の低い文字に対してはこれの文字コ
ード及びイメージを、確率の低いことを表わすフラグと
共に結果バッファに記憶する。そして文字認識アルゴリ
ズムは結果バッファの内容を表示装置の表示スクリーン
上に表示する。操作者は表示された認識結果を見て、そ
して誤って認識された文字の文字コードをキーボードを
介して指摘しそして結果バッファの文字コードを正しい
文字コードに訂正することができる。ここから認識結果
に基づくツリーの修正動作が始まる。文字認識アルゴリ
ズムは、上記誤って認識された文字のイメージ及び正し
い文字コードを学習バッファに記憶する。

文字認識アルゴリズムは、学習バッファの文字イメージ
の各ペルを、走査ウィンドウを用いることにより逐次的
に走査する。このウィンドウの大きさは例えば３×３ペ
ルである。ウィンドウの中心ペルは文字イメージの処理
されるべきペルに位置決めされる。文字認識アルゴリズ
ムは中心ペルの周辺の近隣ペルのビット・パターンをア
ドレスとして用いて統計テーブルの１つのエントリィを
アクセスする。アクセスされたエントリィには処理中の
ペルの黒の確率値が記憶されている。文字認識アルゴリ
ズムはこの確率値を取出しそしてこの確率値を、確率マ
ップのうち上記中心ペルに対応する記憶位置に記憶す
る。文学認識アルゴリズムは、確率マップの値を文字認
識ツリーに入力として与えて、高い確率値を生じる葉ノ
ードを検出し、この巻ノードに割当てられている文字コ
ードの文字イメージを取出し、この文字イメージの確率
マップを形成する。次に、文字認識アルゴリズムは、各
記憶位置毎に、両確率マップの値を比較し、一方の確率
値が高くそして他方の確率値が低い記憶位置を検出し、
上記検出された葉ノードに最初に割当てられた文字コー
ドを、上記検出された記憶位置のアドレスに代え、この
葉ノードから２つのノードを延長し、この延長されたノ
ードの一方に上記葉ノードに最初に割当てられた文字コ
ードを割当て、そして他方のノードに学習バッファの文
字イメージの文字コードを割当てる。文字認識アルゴリ
ズムは結果バッファの文字コードをデータ処理装置等に
送ると共に、修正された文字認識ツリーをツリー・メモ
リに新たに記憶する。従ってこの新たなツリーは以後の
文字認識動作において用いられる。

実施例の説明第１図及び第２図を参照するに、第１図は学習機能によ
って文字認識ツリーを修正するための本発明に従がう回
路ブロツク図を示し、第2A乃至第2E図は第１図の回路ブ
ロツクの動作を示すフローチャートである。

文書走査装置１は、文書給送機構、光源、レンズ、１列
に配列された複数個の光学的感知素子及び閾値回路を含
む従来から知られている装置である。光学的感知素子の
数は例えば1mm当り８個である。即ち、主走査方向の画
素（ペル）密度は200ペル/2.5cmであり、又主走査方向
と交差する副走査方向の画素密度も例えば200ペル/2.5c
mである。１つの光学的感知素子は１つのペルのアナロ
グ信号を発生し、そしてこのアナログ信号は閾値回路に
印加され、アナログ信号が所定閾値よりも低い場合には
黒ペルを表わす２進１信号が発生され、そしてアナログ
信号が閾値よりも高い場合には白ペルを表わす２進０信
号が発生される。これらの動作は第2A図のブロツク21及
び22により行なわれる。文書は複数の文字行を有し、１
文字行は例えば平均的に50個の印刷英数字を含む。文書
の読取動作は１行づつ行なわれ、１頁分の文字イメージ
がイメージ・バッファ２に記憶される。この動作は第2A
図のブロツク23により行なわれる。文字切出し論理回路
３も又従来の型のもので、イメージ・バッファを走査し
て第１番目の行の各文字に外接する四角形を見い出すこ
とにより第１番目の各文字を切出す。１行の文字全てが
切出され、そして作業バッファ４の９×11ペルのフレー
ムに記憶され、この時文字イメージの中心が９×11ペル
のフレームの中心に合わされる。これらの動作は第2A図
のブロツク24及び25により行なわれる。例えばマイクロ
プロセッサ等の制御装置５が上記の動作を制御する。

次の動作の説明を行なう前に文字のタイプ・フォント及
びツリー・メモリ６について説明する。文書の文字は種
々なタイプ・フォントで印刷される。タイプ・フォント
は例えば10ピッチ・グループ、12ピッチ・グループ、レ
ター・ゴシック・グループ、オレータ・グループ及びプ
ロポーショナル・グループに分けられ、そして10ピッチ
・グループは、クーリエ10、パイカ10、プリステージ・
パイカ10、タイタン10のタイプ・フォントを含み、12ピ
ッチ・グループはクーリエ12、エリート12、プリステー
ジ・エリート12、OCR B12のタイプ・フォントを含み、
レター・ゴシック・グループはオレータ、プリゼンタの
タイプ・フォントを含み、そしてプロポーショナル・グ
ループは、ボールド、キュービック／トライアード、ロ
ーマン、タイトルのタイプ・フォントを含む。ツリー・
メモリ６は上記18種類のタイプ・フォント毎の文字認識
ツリー、文字イメージ及び文字コードを記憶している。
第１図を参照するに、ツリー・メモリ６は18個のメモリ
・スペースに分けられている。１つのタイプ・フォント
に１つのメモリ・スペースが割当てられている。第１図
では、４つのメモリ・スペース6A、6B、6C及び6Dだけが
示されている。メモリ・スペース6Aはタイプ・フォント
“クーリエ10"のための１組の文字認識ツリー即ち３つ
の文字認識ツリー6E、6F及び6G、このタイプ・フォント
の全文字のイメージ及び文字コードを記憶している。同
様に、メモリ・スペース6B、6C及び6Dもパイカ10、エリ
ート10及びオレータの夫々の文字認識ツリー、全文字イ
メージ及び全文字コードを記憶している。

さて、前記第2A図のブロツク25の動作を後に、制御回路
５は文字認識論理回路10を動作させる。文字認識論理回
路10は、ブロツク26において、ツリー・メモリ６の任意
のメモリ・スペースから１組の文字認識ツリーを及び全
文字コードを取出す。例えば、メモリ・スペース6Aのク
ーリエ10用の文字認識ツリー6E、6F及び6G及び全文字コ
ードが取出されるとする。動作はブロツク27に進み、文
字認識論理回路10は作業バッファの最初のフレームをア
クセスして第１番目の文字行の最初の文字イメージを取
出し、この第１番目の文字イメージを第１番目の文字認
識ツリー6Eを用いて認識し結果を補助バッファ（図示せ
ず）に記憶する。次に、文字認識論理回路10は、第２番
目の文字認識ツリー6Fを用いて第１番目の文字イメージ
を認識し、結果を上記補助バッファに記憶する。次に文
字認識論理回路10は、第３番目の文字認識ツリー6Gを用
いて第１番目の文字イメージを認識し、結果を上記補助
バッファに記憶する。次に、文字認識論理回路10は補助
バッファの３つの結果を調べ、その中から第１文字の最
終結果を決定する。これはIBMジャーナル・オブ・リサ
ーチ・デベロップメイト、1983年７月、第27巻、第４号
の第394頁ないし第399頁に記載されたBayesianの決定規
則に従って行うことができる。

１つの入力文字イメージを３種の文字認識ツリーで判定
し、それぞれ結果X₁（c₁，e₁），X₂（c₂，e₂）およびX₃
（c₃，e₃）が得られたものとし、これをＸで表すものと
する。ここで、c_jは認識した文字を表し、e_jはツリーｊ
による認識文字c_jが誤りである確率を表す。Bayesianの
規則により、Ｘが与えられたときに認識文字C_Nが生起す
る確率は、ここでC_tはＮ個の認識文字のセットのｔ番目のものであ
る。

C_t＝c_jのとき、Pr（X_j｜C_t）＝１−e_j C_t≠c_jのとき、Pr（X_j｜C_t＝e_jPr（c_j｜C_t）であるか
ら、上記の式の対数S_Nをとると、 S_N＝Σ log（１−e_j）＋Σ［log e_j＋log Pr（c_j｜
C_N）］＋Ｋここで第１の総和はc_j＝C_Nであるｊについて取り、第２
の総和は、 c_j≠C_Nであるｊについて取る。Ｋは上式の分母の対数を
表す。

３つの認識結果を比較するのであるから、Pr（C_N|X）の
絶対値は重要でない。ここで得られた３つのS_N値を比較
して次のように最終結果を決定する。

場合1:最も大きいS_N値２つの間の差が所定値以上であれ
ば、最も大きいS_Nを有する結果が最終結果となる。

場合2:最も大きいS_N値２つの間の差が所定値より小であ
れば、結果バッファに認識結果である文字コード及びこ
の文字のイメージを記憶し、更にフラグを１にセットす
る。フラグ１はリジェクト文字であることを表わす。

上記の文字イメージの認識動作の例を第3A、3B及び3C図
を参照して説明する。第１文字行の第２及び３番目の文
字“B"及び“M"例えばクーリエ10のタイプ・フォントで
タイプされ第１番目の文字“A"は異なるタイプ・フォン
トでタイプされたものと仮定する。これらの文字イメー
ジ31−33は作業バッファ４の３つのフレームに記憶され
終えている。

第3B図は、第１図に示したクーリエ10のメモリ・スペー
ス6Aの３つの文字認識ツリー6E、6F及び6Gのうちツリー
6Eを簡略化して示す。文字認識ツリーはフレームのうち
の所定のペル位置が黒か白のどちらであるかを判別して
その結果に応じて次のペル位置が黒か白のどちらである
かを判別してツリーをたどり最終結果を得る。即ち、ツ
リー6Eは最初の根ノード301においてフレームのペル・
アドレス（４、６）を選択し、このアドレスのペルが黒
であるか白であるかを調べ、その結果に基づいて次の枝
ノード302又は303に進む。この場合答は白なので枝ノー
ド302に進みこのノード302でアドレス（４、０）のペル
を選択しそしてこのペルが黒であるか白であるかを調べ
る。答は黒なので次の枝ノード304に進み、アドレス
（８、５）のペルの白黒を調べる。答は白なので葉ノー
ド305に進み認識結果Ｂを得る。即ち、第１文字は“A"
であるにもかかわらず文字認識ツリー6Eはこの第１文字
を“B"と認識したことになる。この第１文字が第３図の
参照番号34で示すクーリエ10のタイプ・フォントである
ならばツリー6Eはノード301からノード303及びノード30
6を経て葉ノード307に進み答“A"を生じる。実際の認識
結果は上述の如く“B"であるので文字認識論理回路10
は、文字“B"の文字コード及び正確度を補助バッファ
（図示せず）に記憶する。

次に文字認識論理回路10はツリー6Fを用いて第１文字
“A"を再び認識し結果を補助バッファに記憶し、次いで
ツリー6Gを用いて第１文字“A"を再び認識し、結果を補
助バッファに記憶し、これらの３つの結果に基づいて最
終結果を生じる。尚、３種類のツリーを用いて文字を認
識することは前述の文献（１）に更に詳細に示されてい
る。

上記第１文字の最終結果が“B"であるとする。文字認識
論理回路10は、第１図の結果バッファ７の領域7Aの第１
文字の位置に文字“B"の文字コードを記憶する。同様に
して、文字認識論理回路10は作業バッファ４の第２番目
のイメージ“B"を取出し、文字認識ツリー6E、6F及び6G
を用いることにより順次認識して最終結果を生じてこれ
を結果バッファ７の領域7Aの第２番目の文字の列に記憶
する。このようにして第１番目の文字行の全文字即ち約
50文字のイメージを認識して夫々の最終結果を結果バッ
ファ７の領域7Aに記憶する。第3B図の文字認識ツリー6E
は簡略化して示してあるが、実際のツリーは例えば10−
11の決定ステップを含み、総ノード数が2999の時葉ノー
ドの数は1500である。ここで第１文字行を認識した結果
第４番目の実際の印刷文字が“Q"であるにもかかわら
ず、認識の最終結果が０でありそしてその正確度が低
く、そして第25番目の実際の印刷文字が“P"であるにも
かかわらず、認識の最終結果が“R"でありそしてその正
確度が低かったものと仮定する。この場合、文字認識論
理回路10は第１図の結果バッファ７の領域7Aの第４文字
の位置にフラグ１をセットし、文字“O"の文字コード、
及び実際の印刷文字“Q"のイメージを記憶し、そして第
25文字の位置にフラグ１をセットし、文字“R"の文字コ
ード及び実際の印刷文字“P"のイメージを記憶する。そ
して、文字認識論理回路10は領域7Aのフラグの数に基づ
いてリジェクト率を計算して記憶する。図示の例では50
文字のうち２つの文字についてフラグ１がセットされて
いるのでリジェクト率は４％であり、この４％が記憶さ
れる。

次に、ブロツク28において全フォント即ち説明中の例で
は18種類のフォントの全てが用いられたか否かが調べら
れる。もしも答がノーであるならばブロツク26に戻りツ
リー・メモリ６のうち次のフォントのメモリ・スペース
がアクセスされて上述の動作を繰返す。又、ブロツク28
は前文字行の処理中に学習バッファ９に文字コード及び
文字イメージが記憶されている時にイエスの出力を生じ
る。

18種類のタイプ・フォントのためのツリーを用いて第１
文字行の認識が終るとブロツク28の答えはイエスとな
り、そして第１図の結果バッファの18の領域7A、7B、…
…7Nには認識の結果が記憶されている。尚、簡略化のた
めに領域7B、7Nにはリジェクト率のみが示されている。

次に、動作は第2B図のブロツク29に進み、文字認識論理
回路10は、結果バッファ７の18の領域7A……7Nの夫々の
リジェクト率を調べ、リジェクト率が最も低いフォント
を選択し、このフォントのツリーを以下の処理において
使用する。

第１図の結果バッファ７に示されているように、領域7A
即ちクーリエ10のリジェクト率が最も低いものとする。
次に、文字認識論理回路10は第2B図のブロツク30におい
てクーリエ10のリジェクト率４％が０％に等しいか否か
を調べる。答はノーなので動作はブロツク31に進む。も
しもブロツク30の答がイエスならば、動作は第2A図のブ
ロツク24に戻り次の文字行の文字イメージの処理を開始
する。

ブロツク31において、結果バッファ７の領域7Aに記憶さ
れている第１文字行の文字コードを文字発生回路（図示
せず）に送り、文字発生回路からの文字イメージを第１
図の表示スクリーン８の表示領域に表示し、そしてフラ
グ１がセットされている第４文字及び第25文字をブリン
ク又はハイライトで表示する。更に、作業バッファ４に
記憶されている第１文字行の全文字のイメージを表示ス
クリーン８の表示領域8Bに表示する。従って、操作者は
表示スクリーン８の表示領域8Aの認識結果と表示領域8B
の文書の実際の文字イメージとを比較することができ、
そして第１番目の文字にカーソルを位置づけてキーボー
ド（図示せず）から文字“A"の文字コードを入力して結
果バッファ７の領域7Aの第１文字の文字コードを“B"か
ら“A"に修正し、次に第４番目の文字の下にカーソルを
位置づけて文字“Q"の文字コードを入力して領域7Aの第
４文字の文字コードを“O"から“Q"に修正し、そして第
25番目の文字にカーソルを位置づけて文字“P"の文字コ
ードを入力して領域7Aの第25文字の文字コードを“R"か
ら“P"に修正することができる。即ち、この段階で、結
果バッファ７には１行の全文字の正しい文字コードが記
憶されている。第2B図のブロツク32は、上記の操作者に
よる入力が行なわれた否かを調べ、もしも答がノーであ
ればブロツク34に進み、そしてもしも答がイエスであれ
ば、ブロツク33に進む。

ブロツク33では、最初、結果バッファ７の領域7Aの第１
文字の修正された文字コードＡ及び作業バッファ４の第
１文字のイメージＡを学習バッファ９の最初の位置に図
示のように記憶し、次に領域7Aの第４文字の修正された
文字コードＱ及び文字イメージＱを学習バッファ９の次
の位置に記憶し、そして領域7Aの第25文字の修正された
文字コードＰ及び文字イメージＰを学習バッファ９の次
の位置に記憶する。即ち、１文字行の認識が終る毎に、
操作者による修正が行なわれたか否かを調べ、修正が行
なわれるとその内容を学習バッファ９に記憶していく。
もしも新たに修正された文字が既に学習バッファ９にあ
る文字と同じなら、新たな文字を記憶しない。そして更
に、結果バッファ７の１文字行の文字コードを記憶する
出力バッファ13には１文字行の処理が終了する毎に正し
い文字コードが記憶される。このようにしてブロツク33
の動作が終了すると、動作はブロツク34に進む。ブロツ
ク33において、学習バッファ９に文字コード及びイメー
ジが記憶された後は、以下の文字行即ち説明中の例では
第２番目の文字行以降の処理においては第１文字行の認
識で用いたツリーを用いる。即ち、ブロツク34の答がノ
ーとなって、そして動作がブロツク24に戻り次にブロツ
ク25を介してブロツク26に進んだ時、次の１組のツリー
を取出すのではなく、前文字行（即ち第１文字行）で用
いた１組のツリーを用いて認識を行なう。更に、ブロツ
ク28はイエスの出力を生じる。

ブロツク34は文書１ページの全文字行が処理され終えた
か否かを調べ、もしもノーであれば第2A図のブロツク24
に戻り残りの文字行の処理を行ない、もしもイエスであ
るならば第2C図のブロツク35へ進む。

ブロツク35において、文字認識論理回路10は学習バッフ
ァ９の最初の位置から文字コードＡ及び文字イメージＡ
を取出し、そしてブロツク36の動作に進む。

ブロツク36の動作を説明する前にこのブロツク36で用い
る３×３ペル・ウィンドウ41（第４図）、統計テーブル
11（第１図）及びマップ・バッファ12（第１図）を説明
する。

３×３ペル・ウィンドウ41のペル位置のうち周辺の８は
第５図に示すようにペル・アドレスが割当てられ、この
３×３ペル・ウィンドウ41はこれの中心ペルＸが第４図
に示すように文字イメージの左上角のペルに重なるよう
に位置づけられる。統計テーブル11は表１に示すよう
に、３×３ペル・ウィンドウ41の中心ペル即ち処理され
つつある現ペルＸの黒の確率を記憶している。アドレス
１のビットは最上位ビット（MSB）でありアドレス８の
ビットは最下位ビット（LSB）である。マップ・バッフ
ァ12は領域12A及び12Bを有し、これら領域の夫々の大き
さは、第１図の作業バッファ４のフレームと同じ寸法、
即ち９×11ペルである。即ち、領域12A及び12Bの寸法は
第3A図のイメージ31、32及び33と同じである。

さて、ブロツク36の動作を説明すると、文字認識論理回
路10は、３×３ペル・ウィンドウ41の現ペルＸを第４図
に示すように文字“A"の文字イメージ31の左上角のペル
に位置決めする。ここで第４図の２進０、１のパターン
は第3A図のイメージ31を表わす。イメージ31の外側にあ
る３×３ペル・ウィンドウ41のアドレス１、２、３、
４、８の２進値は０である。この場合、ウィンドウ41の
アドレス１〜８は２進値00000000で表わされる。文字認
識論理回路10は上記２進値をアドレスとして統計テーブ
ル11をアクセスする。次に、表１を示す。

前述の如く、３×３ペル・ウィンドウ41の現ペルＸが第
４図の文字イメージ31の左上角（０、０）のペルに位置
決めされている時、この現ペルＸの周辺ペル即ちペル・
アドレス１−８のペルは00000000である。文字認識論理
回路10は、上記ビット・パターン00000000をアドレスと
して用いることにより統計テーブル11のエントリィ０を
アクセスして、この現ペルＸが黒である確率値０％を読
出し、そしてこの値０を、第６図に示すように、マップ
・バッファ12の領域12Aの左上角（０、０）の位置に書
込む。

次に、文字認識論理回路10は、第４図のイメージ31上で
ウィンドウ41を右方向に１ペル位置だけペル・アドレス
（１、０）に動かす。この場合、ウィンドウ41のアドレ
ス１−８のビット・パターンは00000000であり、文字認
識論理回路10はこのビットパターンをアドレスとして用
いて統計テーブル11をアクセスして確率値０を領域12A
のペル・アドレス（１、０）に書込む。このようにし
て、文字認識論理回路10はウィンドウ41を右方向に順次
シフトしてイメージ31の第１ペル行の各ペル位置の黒の
確率をマップ・バッファ12の領域12Aに順次書込む。第
１行の処理を終了した後、文字認識論理回路10はウィン
ドウ41を第２ペル行の最初のペル位置（０、１）に位置
づけ、第２ペル行の処理を行ない。以下、同様にして全
ペル行の処理を行なう。第６図は文字“A"のイメージ31
の各ペル位置の黒の確率値を示す。

例えば第４図のペル位置（４、０）にウィンドウ41の現
ペルＸが位置づけられた時には、周囲ペルのパターンは
10001101であり、そして統計テーブル11のエントリィ14
1がアクセスされ、確率値95％が第６図の領域12Aのペル
位置（４、０）に書込まれる。又、第４図のペル位置
（２、２）にウィンドウ41の現ペルＸが位置づけられた
時には、周囲ペルのパターンは00010010であり、そして
統計テーブル11のエントリィ18がアクセスされ、そして
確率値26％が第６図の領域12Aのペル・アドレス（２、
２）に書込まれる。

次に、動作は、第2C図のブロツク37に進み、文字認識論
理回路10は、第2B図のブロツク29で選択した文字認識ツ
リー即ち、クーリエ10の３つのツリー6E、6F及び6Gの夫
々に、領域12Aの確率値を入力する。この動作を第3B図
のツリー6Eについて説明する。ツリー6Eの根ノード301
はペル位置（４、６）を選択する。従って第６図の領域
12Aの位置（４、６）の確率値70が取出される。この確
率値70は、第3A図の文字“A"のイメージを100回文書上
の異なる位置に印刷した場合、紙の表面の状態、インク
・リボンのインク分布等に起因して、100個のうち70個
即ち70％の文字のペル位置（４、６）が黒として印刷さ
れ、そして30個即ち30％の文字のペル位置（４、６）が
白として印刷されることを表わす。この確率値を入力し
た時の動作を第3D図を参照して説明する。上述の説明か
ら、根ノード301の白出力の確率は30％であり、そして
黒出力は70％である。次に、枝ノード302及び303で同じ
動作が行なわれる。枝ノード302において第６図の領域1
2Aの位置（４、０）の確率値95％が取出される。従っ
て、枝ノード302の白出力の確率は30％×５％＝1.5％で
あり、そして黒出力の確率は30％×95％＝28.5％であ
る。次に、枝ノード308において領域にＡの位置（１、1
0）の確率68％が取出される。枝ノード308の黒出力の確
率は、1.5％×68％＝1.02％であり、これが葉ノード311
の確率値である。そして白出力の確率は、1.5％×32％
＝0.48％であり、これが葉ノード310の確率値である。

枝ノード304において領域12Aの位置（８、５）の確率０
％が取出される枝ノード304の黒出力の確率は、28.5％
×０％＝０％であり、そしてこれが葉ノード312の確率
値である。枝ノード304の白出力の確率は、28.5％×100
％＝28.5％であり、そしてこれが葉ノード305の確率値
である。同様の動作が枝ノード303、306及び309、並び
に葉ノード307及び313で行なわれて、そして第3D図に示
す確率値が発生される。ここで、枝ノード309へ与えら
れる確率値は０％であることに注目されたい。枝ノード
に与えられる確率値が０％の場合には、この枝ノードの
黒及び白出力の確率値は両方共０％であるので、動作は
この枝ノードで終了する。次に動作はブロツク38に進
み、文字認識倫理回路10は、各葉ノードの確率値を予定
の閾値例えば２％と比較し、この閾値よりも高い確率値
を有する葉ノードを選択し、更にこれら選択した葉ノー
ドのうち１つを選択する。説明中の例では、第3D図の葉
ノード305及び307が選択され更にこのうち葉ノード305
が最初に選択される。説明中の例では２つの葉ノードだ
けが選択されたが、実際のツリーは前述の如く、例えば
1500の葉ノードを有するので、閾値よりも大きい確率値
を有する葉ノードの数は10−20となる。

次に動作はブロツク39に進み、文字認識論理回路10は、
現在処理中の学習バッファ９内の文字コードＡが葉ノー
ド305の文字コードＢと同じであるかどうかを調べる。
答はノーであるので動作は第2D図のブロツク40に進む。
もしも答がイエスであれば、現在処理中の葉ノードを更
に処理することなく後述のブロツク44に進む。

ブロツク40では、文字認識論理回路10は、葉ノード305
の文字イメージをツリー・メモリ６から取出す。説明中
の例では葉ノード305の文字Ｂの文字イメージがツリー
・メモリのメモリ・スペース6Aから取出される。動作は
ブロツク41に進み、文字認識論理回路10は、ブロツク40
で取出した文字Ｂの文字イメージの全ペルの黒の確率を
計算してマップ・バッファ12の領域12Bに書込む。この
ブロツク41の動作は、ブロツク36の動作と同じである。
即ち、第５図の３×３ペル・ウィンドウ41を用いて、第
４図の動作と同様にして、文字Ｂの文字イメージを走査
する。そしてウィンドウ41のペル・アドレス１−８のビ
ット・パターンをアドレスとして用いて統計テーブル11
をアクセスして確率値をマップ・バッファ12の領域12B
に書込む。第７図はこのようにして領域12Bに書込まれ
た文字Ｂの各ペル位置の確率を示す。

次に、動作はブロツク42に進み、文字認識論理回路10
は、マップ・バッファ12の領域12A及び12Bの同じペル位
置の確率値を位置（０、０）から順次比較して、一方が
低く例えば０％であり、他方が高く例えば100％である
位置を見出す。即ち、２つの値の差が最大値となる位置
を検出する。説明中の例では文字認識論理回路10は、位
置（１、１）において、領域12Aの確率値は０％であ
り、他方領域12Bの確率値は10％であることを見出す。

動作はブロツク43に進み、文字認識論理回路10は、上記
ブロツク38で選択した最初の葉ノード305の文字コード
を消去して、そしてブロツク42で見出した位置アドレス
（１、１）を書込み、そしてこの葉ノード305から第3E
図に示すようにノード316及び317を延長する。そして文
字認識論理回路10は、ノード305の黒出力に接続されて
いる延長ノード317に、位置（１、１）の確率値が高い
方の文字即ち文字Ｂのコードを書込み、そしてノード30
5の白出力に接続されている延長ノード316に、位置
（１、１）の確率値が低い方の文字即ち文字Ａの文字コ
ードを書込む。

次に動作はブロツク44に進み、文字認識論理回路10は、
ブロツク38で見出した全ノードの処理が終了したか否か
を調べる。説明中の例では、またノード307の処理が終
了していないのでブロツク44の答はノーであり、動作の
第2C図のブロツク38へ戻る。ブロツク38において、文字
認識論理回路10は、未処理の葉ノード307を選択し、ブ
ロツク39において、葉ノード307の文字Ａの文字コード
が学習バッファ９の文字Ａの文字コードと同じかどうか
を調べる。ブロツク39の答はイエスなので、第2D図のブ
ロツク44に進み、全ての葉ノード即ち305及び307の処理
を終了したことを検出する。そして動作は第2E図のブロ
ツク45に進み、一組のツリー6E、6F及び6Gのうち全ての
ツリーの処理が終了したかどうかが調べられる。説明中
の例では、ツリー6F及び6Gがまた処理されていないので
動作はブロツク37に戻る。３つのツリー全ての修正が行
なわれるとブロツク45の答はイエスとなり、ブロツク46
に進む。ブロツク46において、文字認識論理回路10は、
学習バッファ９の全ての文字が処理され終えたかどうか
即ち文書１ページで見出された修正されるべき文字の全
てが処理され終えたかを調べる。ブロツク46の答がノー
であれば、動作はブロツク35に戻り、そして答がイエス
であれば動作はブロツク47に進む。ブロツク47におい
て、文字認識論理回路10は、１ページ分の認識結果即
ち、出力バッファ13の全文字コードを出力し、そして修
正された一組のツリー、全文字コード及び全文字イメー
ジをツリー・メモリ６の空のメモリ・スペースに記憶す
る。そしてブロツク48において認識及びツリー修正動作
を終了する。

第８図は、第3B、3D及び3E図に示されたノードにおける
動作を示す。マップ・バッファ12の確率値をツリー6Eの
例えば第3D図の枝ノード302の動作を第８図を参照して
説明する。枝ノード302への入力である確率値は30％で
あるので第８図のブロツク81への入力確率値Ｐは30％で
ある。ブロツク81において、このノード302が指定する
アドレス即ち（４、０）のペルに対応する確率値Ｑ即ち
95％が第６図の領域12Aから取出される。次に、ブロツ
ク82においてＰ×Ｑの値即ち30×95％＝28.5％が計算さ
れて閾値例えば１％と比較される。この場合、ブロツク
82の答はイエスなのでこのノード302はブロツク83にお
いてＰ×Ｑ＝28.5％を第3D図に示すように黒出力に生じ
る。次に、ブロツク84においてＰ×（100−Ｑ）即ち30
×（100−95）＝1.5％を閾値１％と比較する。この場
合、ブロツク84の答はイエスなのでノード302の白出力
に1.5％が発生される。

次に、２進１（即ち黒100％）若しくは２進０（黒０
％）で各ペルが表わされそして作業バッファ４に記憶さ
れている文字イメージの認識動作について説明する。

ノードが前のノードの黒出力に接続されているとすると
このノードへの入力確率Ｐは100％である。ブロツク81
における確率値Ｑは文字認識時には100％か０％であ
る。確率値Ｑが100％であるとするとブロツク82のＰ×
Ｑは100％となりブロツク83においてこのノードの黒白
出に100％を生じる。ブロツク84の答はノーであるので
このノードの白出力には何も発生されない。

第2D図のブロツク43は次のような附加的動作を行なう。
即ち、延長した葉ノード316及び317に文字Ａ及びＢの文
字コードを夫々割当てた後に、文字Ａ及びＢの認識確率
をこれらのノードに記憶しておく、これは次のようにし
て計算される。

修正される前のノード305の文字Ｂの認識確率が40％で
あるとする。このノード305から延長された最終ノード
である葉ノード316及び317の文字認識確率は、ノード30
5の文字Ｂの認識確率40％、ノード305への入力確率28.5
％、マップ・バッファ12の領域12A及び12Bのうちノード
305に新たに割当てられたアドレス（１、１）の確率値
により決められる。葉ノード316の認識確率は次のよう
にして計算される。ノード305における文字Ａのペル位
置が黒となる確率は第６図のアドレス（１、１）から明
らかなように０％である。即ち、白となる確率が100％
である。従って、葉ノード316で文字Ａを認識する確率
は、28.5％×100％＝28.5％であり、一方文字Ｂを認識
する確率は40％×０％＝０となる。

葉ノードの認識確率は次のようにして計算される。ノー
ド305における文字Ｂが黒となる確率は第７図のアドレ
ス（１、１）から明らかなように100％である。従っ
て、葉ノード317で文字Ｂを認識する確率は、40％×100
％＝40％であり、一方文字Ａを認識する確率は28.5％×
０％＝０％となる。これらのノード316及び317に新たに
与えられた認識確率は、第2A図のブロツク27において用
いられる。

説明を簡単化するために、作業バッファ４のフレームは
９×11ペルの寸法を有するとして説明したが、実際には
大きな寸法例えば32×40ペルを有する。

実施例の説明は、文字認識ツリーの学習動作即ちツリー
の修正動作に向けられたが、本発明は、文字の特徴を抽
出してこの特徴を表わす特徴リストを文字毎に記憶して
おくことによって文字認識を行なうアルゴリズムにおい
て用いられることができる。

又、パターンとして絵数字のパターンの認識及び学習動
作を説明したが、英数字の代わりに日本字又は指紋を用
いることができる。

実施例では、１文字行の認識毎に誤って認識された文字
の文字コードを正しい文字コードに訂正したが、この動
作は複数行おきに行なわれることができる。又、１ペー
ジの文書の認識終了毎にツリーを修正したが、この動作
は複数ページ終了毎に行なわれることができる。

発明の効果本発明の作用効果は、文字認識ツリーを修正する時間が
短かいこと、修正に要する記憶領域が少ないこと、操作
者の介存が最小であること、本来の認識動作を行なって
いる間にツリーの修正が行なわれること、学習及び修正
を行なうのに最小数のサンプルしか必要としないことで
ある。

【図面の簡単な説明】

第１図は本発明の文字認識装置のブロツク図、第2A図、
第2B図、第2C図、第2D図及び第2E図は、本発明の文字認
識方法の認識及びツリー修正工程を示すフローチャー
ト、第３図及び第3A図は文字イメージを示す図、第3B図
は文字認識ツリーを示す図、第3C図はツリー・メモリの
１つのメモリ・スペースに記憶される一組のツリーを示
す図、第3D図は第3B図のツリーにマップ・バッファの確
率値を入力する動作を示す図、第3E図は、ツリーの１つ
の葉ノードを延ばす動作を示す図、第４図は文字イメー
ジをウィンドウにより走査する動作を示す図、第５図は
ウィンドウのアドレスを示す図、第６図及び第７図は文
字Ａ及びＢのイメージの各ペル位置の確率値を記憶する
マップ・バッファの２つの領域を示す図、第８図はツリ
ーのノードの動作を示すフローチャートである。１……文書走査装置、２……イメージ・バッファ、３…
…文字切出論理回路、４……作業バッファ、５……制御
装置、６……ツリー・メモリ、6A、6B、6C、6D……メモ
リ・スペース、７……結果バッファ、８……表面スクリ
ーン、９……学習バッファ、10……文字認識論理回路、
11……統計テーブル、12……マップ・バッファ、13……
出力バッファ。

Claims

【特許請求の範囲】

【請求項１】文書の文字のイメージを記憶する手段と、上記文字のイメージを認識する文字認識ツリーであっ
て、文字のイメージの複数の画素に対応する根ノード、
枝ノードおよび文字コードが割り当てられている複数の
葉ノードのツリーから成るものと、高い確率で認識された文字の文字コード並びに低い確率
で認識された文字の文字コード及びイメージを記憶する
結果バッファと、低い碓率で認識された文字の文字コードを正しい文字コ
ードで置換する手段と、上記低い確率で認識された文字の上記正しい文字コード
及びイメージを記憶する学習バッファと、上記学習バッファに記憶された文字のイメージの各画素
の位置に黒が現われる確率を表わす第１の値を計算する
手段と、上記第１の値を上記文字認識ツリーのノードに供給し、
上記学習バッファに記憶されたイメージを高い確率で認
識する上記認識ツリーの葉ノードを検出する手段と、上記検出された葉ノードに割当てられた文字コードのイ
メージの各画素の位置に黒が現われる確率を表わす第２
の値を計算する手段と、上記学習バッファに記憶された文字のイメージ及び上記
葉ノードに最初に割当てられた文字のイメージの同じ画
素位置の上記第１及び第２の値を比較し、一方の値が大
きくそして他方の値が小さい画素位置を検出する手段
と、上記検出された葉ノードの文字コードを上記検出された
画素位置のアドレスに代え、上記葉ノードから２つのノ
ードを延長し、該延長されたノードに上記最初に割当て
られた文字コード及び上記学習バッファの文字コードを
夫々割当てる手段とを有する文字認識装置。
【請求項２】上記認識ツリーの根ノードおよび枝ノード
は、上記文字のイメージの選択された画素のアドレス・
データを記憶し、後続ノードに夫々接続された２つの出
力を有し、そして上記選択された画素に黒が現われる確
率を表わす値に依存する出力を発生することを特徴とす
る請求項第１記載の文字認識装置。
【請求項３】上記文字のイメージの画素の夫々は２進１
若しくは０により表わされることを特徴とする請求項２
記載の文字認識装置。
【請求項４】文書の文字のイメージを記憶するイメージ
・バッファ、１文字行の複数文字のイメージを個別の文
字イメージに区切る手段、上記１文字行の上記区切られ
た文字のイメージを記憶する作業バッファを含むことを
特徴とする請求項１記載の文字認識装置。
【請求項５】上記第１の値を計算する手段は、上記文字
のイメージの各画素及び該画素の近隣画素を逐次的に走
査し、該近隣画素の文字をアドレスとして用いることに
より統計テーブルのエントリィをアクセスし、上記近隣
画素により囲まれた上記中心画素に黒が生じる確率を表
わす値を上記エントリィから取出し、該取出した値を、
上記確率マップのうち上記中心画素の位置に対応する記
憶位置に記憶することを特徴とする請求項１記載の文字
認識装置。
【請求項６】上記第２の値を計算する手段は、上記文字
のイメージの各画素及び該画素の近隣画素を逐次的に走
査し、該近隣画素の文字をアドレスとして用いることに
より統計テーブルのエントリィをアクセスし、上記近隣
画素により囲まれた上記中心画素に黒が生じる確率を表
わす値を上記エントリィから取出し、該取出した値を、
上記確率マップのうち上記中心画素の位置に対応する記
憶位置に記憶することを特徴とする請求項１記載の文字
認識装置。