JPH06508465A - 文字ビットマップにおける終点特性を測定する手段を用いる文字認識システム及び方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 文字ビットマツプにおける終点特性を測定する手段を用いる文字認識システム及 び方法 発明の技術分野 本発明は文字認識技術に関する。より詳細には、活字体文字の機械認識における 誤りの発生する余地を効果的に改良するためのシステム及び方法に関する。

背景技術 手書き文字の機械認識のためのコンピュータ技術は、近年著しく進歩している。

特定の文字認識手順（ｃｈａｒａｃｔｅｒ　ｒｅｃｏｇｎｉｔｉｏｎ　ｐｒｏｃ ｅｄｕｒｅ　）による誤り率と人間による誤り率の発生の差が縮小し続けている ことから、この誤り率をさらに縮小することは達成がより困難になってきている 。例えば、二二一うルーネソトワークに基づくアルゴリズム（ｎｅｕｒａ＋−ｎ ｅｔｗｏｒｋ−ｂａｓｅａ　ａｌｇｏｒｉｔｈｍｓ　）の場合、この困難さのた めに、今までよりも大きいトレーニングデータを用いても誤り率の向上はごくわ ずかである。

この現象に鑑み、機械に基づく認識プロセスの誤り率を低減させるための１つの 技術として、相関性のない誤りを有する（つまり、異なる種類の誤りを生じる） 複数の認識手順を同時に用いて、全体の性能を強化してきた。この異なる手順は 、完全に異なる（それゆえに共有不可能な）中間ステップを有することがよくあ り、そのすべてのステップがそれぞれの文字に対して行われなければならないた め、この技術にはかなり苛酷にコンピューターに負担（ｐｅｎａｌｔｙ　）が要 求される。

より有効的な技術としては、はとんどの文字に対しては１つまたは２．３の独立 した手順を同時に用い、低基準の信頼を育する文字に対してのみ、さらに独立し た手順を用いてきた。この技術は認識誤り率を改善するが、これに関連するコン ビ二一夕の負担もかなりある。さらに、この技術は、相当に正確な信頼度基準供 する手順と共にしか効果的に使用することができない。

より詳細には、従来の光学的文字認識（ＯＣＲ）システムは、通常、認識しよう とする文字と同数の出力を有する。人力された文字は、通常、出力の値を調べる ことにより識別される。もっとも簡単な方法の１つは、最大（最小）値を存する 特定の出力に対応すると認識される人力文字に対して文字を選ぶ方法である。

信頼度基準もまたこの出力値の関数である。その最も基本的な形においては、最 大（または最小）出力値が信頼度の基準となる。これよりわずかに性能の良い信 頼度基準が最大出力とその次に高い出力の間の割合として決定できる。しかし、 信頼度基準の正確さは、測定方法の間で、及び異なるＯＣＲ手順の間で大幅に変 わる。

このように、この技術分野においては、特定のＯＣＲ手順の誤り率と人間による 誤り率の間の発生余地の差を低減するより効果的な技術が必要とされている。

発明の開示 従って、本発明の目的は、文字認識システム及び方法の誤り率を効果的に低減す るための技術を提供することである。

別の目的は、「最適な」信頼度基準が低いときにのみ新たな文字特性を測定する ことにより、特性に基づく文字認識システムの性能を向上することである。

本発明のさらに別の目的は、文字ビットマツプからストローク終点の位置及び方 向をすばやくかつ効果的に獲得することである。

上記の及びその他の目的は、本発明の教示に従い下記の方法により達成される： 光学的文字認識（ＯＣＲ）手順により生成された信頼度基準が低い場合にのみ、 迅速に計算可能な特性に基づき、認識されるべき入力文字のそれぞれから簡単な 符号（ｓｉｇｎａｔｕｒｅ　）を効果的に構成し、この符号を用いてその文字に 対する改良された選択を行う。本発明のアプローチの成功への鍵となるのは、Ｏ ＣＲ手順と共に用いた場合のこの符号の質と手順の信頼度基準の正確さである。

物体における不連続な湾曲（ｃｕｒｖａｔｕｒｅ　ｄｉｓｃｏｎｔｉｎｕｉｔｉ ｅｓ　）は、人間の知覚に対して強い影響を有する。この概念を手書き文字にま で拡張することにより、ストローク終点の位置及び方向が文字識別に対して非常 に価値のある特性であることが判明した。このように、本発明ではこの情報を認 識のプロセスに組み込んでいる。

より詳細には、本発明は画素の電荷モデル（ｃｈａｒｇｅ　ｍｏｄｅｌ）に基づ く、文字−特性ａ＋定技術を利用する。文字の終点は、各画素の「電位」を計算 し、しきい値を供給することにより位置決めされる。２値符号（ａ　ｂｉｎａｒ ｙ　ｓｉｇｎａｔｕｒｅ）はこの情報から構成される。それにより、符号及び関 連する文字のデータベースが、文字ビットマツプの大きいトレーニングセットを 用いて構成される。実際の使用の間は、ＯＣＲ手順からの低い信頼度基準により 、符号発生プロセスが開始される。

この符号は、すてに作成されたデータベースから可能性のある文字のリストを呼 び出すのに用いられる。この文字リストを用いて、ＯＣＲ手順によって発生した 第１と第２の選択の間の決定がなされる。

詳細には、トレーニング段階（ｔｒａｉｎｉｎｇ　ｐｈａｓｅ）においては、既 知のビ・ノトマソブされた文字は終点位置決め手順に供給される。終点位置及び 方向情報が検出され、処理されて、各文字の符号を構成する２値列（ｂｉｎａｒ ｙ　Ｓｔｒｔｎｇ　）　（１と０の列）を生じる。各エントリーが１つの符号及 び候補になる可能性のある文字の関連する列を構成している、データベースが形 成される。

本発明の１つの特徴は、人力された文字を、定められた文字セットのうちの特定 の要素であると識別する文字認識システム及び方法に向けられたものである。

より詳細には、文字入力装置は、入力された文字の文字ビットマツプを生成する 。

文字認識手順はこの文字ビットマツプを処理し、信頼度基準のセットを発生する 。

すなわち、文字セットのそれぞれの要素に対して信頼度基準を生成する。この信 頼度基準は、人力された文字が、文字セットの要素に対応する信頼度の程度を表 す。この信頼度基準がテストされ、最高程度の信頼を有する信頼度基準が受け入 れ可能な信頼度基準であるかが判断される。第１出力装置は、受は入れ可能な信 頼度基準を有する文字セットの要素を、出力文字として報告する。受は入れ可能 な信頼度基準がない場合は、拡大器（ａｕｇＩＩｅｎｔｅｒ　）が（Ｎ）番目ま での最高信頼度基準を有する（Ｎ）個の要素を候補として識別し、さらにビット マツプを処理する。この拡大器はビットマツプの文字特性を測定する。第２出力 装置は、この文字特性の測定に基づき、（Ｎ）個の要素のうちの１つを出力文字 として報告する。

本発明の別の特徴によれば、文字ビットマツプは拡大器によって分析され、スト ローク終点情報が得られる。ストローク終点情報は文字列−符号の複数の対を有 する学習された終点データベース（ａ　１ｅａｒｎｅｄ　ｅｎｄｐｏｉｎｔ　ｄ ａｔａｂａｓｅ　）と比較される。データベースの文字列と候補文字が一致すれ ば、この一致したものが用いられ出力文字を報告する。終点位置及び方向は、ビ ットマツプを電荷分布（ｃｈａｒｇｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ　）として形 成することにより得られる。電位プロファイル（ｐ。

ｔｅｎｔｊａｌ　ｐｒｏｒｉｌｅ　）が構成され、しきい値が定められ（ｔｈｒ ｅｓｈｏｌｄｅｄ　）　、その結果がある領域に結集され、終点位置が得られる 。電位プロファイルの勾配を用いて終点の方向が得られる。

図面の簡単な説明 本発明の教示は、添付の図面に関連して以下の詳細な説明を考慮することにより 容易に理解することができる。図面において、図１は本発明の教示に従って組み 立てられたＯＣＲシステムの好適な実施例のブロック図である。

図２は図１のＯＣＲシステムのフローチャートである。

図３は２次元の文字ビットマツプの概略図である。

図４は図２のフローチャートの終点拡大器部分を詳細に示したコンピュータフロ ーチャートである。

図５は図３に示されるタイプの文字ビットマツプの計算された電位プロファイル を示した３次元のグラフである。

図６は図３の文字ビットマツプのストローク終点と識別された領域を示す、図３ と同様の概略図である。

図７は本発明の理解に役立つ空間及び方向のビン（ｂｉｎ　）を示した３次元の 図である。

理解を容易にするために、可能な場合は、図面を通して同一符号は同一要素を示 す。

発明の実施様態 図１について説明する。　図１は、文字入カシステム１８を有する光学的文字認 識（ＯＣＲ）システム１５を示す。文字入カシステム１８は、従来の光学的走査 システム、ディジタイザ／ペンシステム、またはその他の文字入力装置でもよい 。入カンステム１８はディジタルコンピュータ１７に接続される。本発明に従っ て組み立てられた文字認識プロセッサ２０が、コンピュータ１７に内蔵されてい る。適当な出力装置１６がコンピュータ１７の出力に接続されている。出力装ｒ Ｉ１１６は、プリンタ、ディスク記憶装置、表示装置、データ送信器またはプロ セッサ２０によって出力された文字を表示し、記憶し、または送信するための同 様の装置である。

一般的に、ＯＣＲシステム１５の動作は次の通りである。このシステムは、第１ に、入力システム１８によって、従来の方法で文字を読み取る。入力文字は、通 常、機械プリントのまたは手書きの文字と数字の組み合わせによるテキストのグ レースケールイメージである。コンピュータ１７への入力は、通常、人力システ ム１８内に生成されたグレースケールイメージデータをしきい値決めすることに よって得られる２値列である。プロセッサ２ｏは、この２値列をビットマツプの セットとして、つまり走査された各文字に対して１つのビットマツプを記憶する 。プロセッサは次にこのビットマツプを処理し、内部に格納された文字のデータ ベースから出力文字を選択する。選択された出力文字は出力装置１６に送信され る。

図２において、通常はソフトウェアによって実現されるプロセッサ２ｏが詳細な フローチャートに示される。ビットマツプ作成ステップ１９において、プロセッ サ２０はシステム１８によって入力される２値列からビットマツプを作成する（ 図１参照）。ビットマツプは、コンピュータ１７の適当な記憶位置（例えばディ スクファイル）に記憶される。

図３は、多数の画素位置において活字のまたは手書きの文字ｒＡＪを走査した結 果得られるタイプのビットマツプ３０を概略的に示したものである。ビットマツ プ３０は、ここでは、縦行Ｘ及び横列ｙに並べられた画素位置の方形アレイとし て示され、各画素位置は黒または白の画素のどちらかにより占められている。

図３においては画素はドツト（黒点）またはダッシュ（点線）のアレイとして示 されている。

より詳細には、図３に示される例では、ビットマツプ３ｏは全体で３９縦行、６ ０横列を構成する。従って、ビットマツプ３ｏは２．３４０の画素位置を有する 。白の画素はダッシュによって示され（占められていない画素位置）、黒の画素 はドツト（占められている画素位置）によって示される。ビットマツプ３ｏにお ける文字ｒＡＪは、ストローク終点３２−３５を含む多数の文字特性を育する。

当然ながら、文字ビットマツプ３０は２．３４０ビツトの２値列（「１」とｒＯ Ｊの列）としてコンピュータ１７に記憶してもよい。

図２に示されるように、ビットマツプを形成し記憶した後、プロセッサ２ｏは読 み取りステップ２１において、ビットマツプされた文字をその記憶位置から呼び 出す。フォーマットステップ２２において、ビットマツプを標準サイズにデスキ ューイング（ｄｅ−ｓｋｃｗｉｎｇ）及び標準化する従来の機能を行うことによ り、呼び出されたビットマツプデータは処理の準備がされる。次に、プロセッサ ２ｏはＯＣＲステップ２３において、ＯＣＲ手順に従ってビットマツプデータを 処理する。

説明のために、ＯＣＲ手順は、こ二ではビットマツプ３ｏの２．３４０画素に対 応する２、３４０の入力と、読み取られる可能性のある文字の総数、つまりアル ファベットの２６の大文字と０から９までの１０のディジットに対応する例えば ３６の出力を有する従来のニューラルネットワーク（ｎｅｕｒａｌ　ｎｅｔ警ｏ ｒｋ）と想定される。

信頼度基準ステップ２４においては、ＯＣＲステップ２３においてＯＣＲ手順に より生成された３６の出力を用いて、この可能性のある３６文字のそれぞれに対 する信頼度基準を獲得する。前述のように、従来のＯＣＲシステムの多くが、信 頼度基糸として二の３６の出力自体を使用している。例えば、ＯＣＲステップ２ ３におけるビットマツプの処理と同時に、ＯＣＲ手順はある数、通常は０と１の 間の数を、この可能性のある３６文字のそれぞれに割り当てる。これらの割り当 てられた数の値は、通常、ＯＣＲ手順によって用いられた基準に基づき、処理さ れたピントマツプがさまざまな文字のそれぞれに対応する程度を示す。このよう に、これらの３６の割り当てられた数が信頼度基準として直接用いられても良い 。その他のＯＣＲ手順では、より正確な信頼度基準が生成されることがよくある 。例えば、信頼度基準は、３６の割り当てられた数の複素数関数のセットを計算 することによって生成することもてきる。相当に正確な信頼度基準を確保するこ とにより、出力文字の最終的な選択において、かなりの正確さが得られたことが 確認される。

より詳細には、ＯＣＲステップ２３からの割り当てられた数の少なくとも１つは 、多くの場合、相対的に高い値を有する。したがって、特に、その割り当てられ た数がその次に高い割り当てられた数よりもかなり高い数値である場合、すなわ ち、最高値を割り当てられた２つの数の割合が１に近くない場合は、その対応す る文字は通常出力文字として選択される。しかしながら、他の状況においては、 割り当てられた３６の数のすべてが非常に低かったり、または、２つ以上の割り 当てられた数が、高くはあるが、非常に近い数値で、それらの割合が１に非常に 近いという場合が起こり得る。このような場合には、出力文字の選択は明確では ない。実際に、最も高い割り当てられた数を有する文字は正しい選択ではない場 合がある。このような問題のある場合においては、最終選択の正確さは、本発明 を用いてビットマツプを処理し、ＯＣＲステップ２３において識別された２、３ の最適な候補の中からさらに選択を行うことにより改善される。

判断ステップ２５において、プロセッサ２０は、前述の所定の基準に従って、「 最適な」信頼度基準か受け入れ可能であるか、つまりｒＯＫＪであるかを判断す る。「最適な」信頼度基準が受け入れ可能であれば、その「最適な」信頼度基準 を有する文字が、出力ステップ２６において、出力文字として報告される。一方 、「最適な」信頼度基準がｒｏＫｌてない場合は、例えば最も高い割り当てられ た数を有する２つ以上の文字が候補として識別され、拡大器ステップ２７におい て、異なる基準（例えば、終点位置及び方向）を用いてビットマツプがさらに処 理され、現在認識されている文字に対する適切な出力文字を選択する。出力ステ ップ２６、あるいは拡大器ステップ２７において出力文字が選択されると、判断 ステップ２８を介して、すべてのビットマツプが処理されるまで、プロセスステ ップが繰り返される。

前述のように、ＯＣＲ手順の多くはストローク終点情報を直接利用しないため、 その他の特性だけに基づいて識別できる文字を、誤って識別する二とが多い。多 くの手書き文字のストローク終点の位置及び方向は、文字４鷹において非常に価 値のある特性であることが判明した。

図４は、図２に示された拡大器ステップ２７において用いられる終点拡大器４０ のフローチャートである。終点拡大器４０の具体的な実施は付録Ａに示される。

付録Ａは、ＵＮＩＸオペレーティングシステムを実行するＳｕｎ　５ＰＡＲＣｓ ｔａｔｉｏｎのコンピュータ言語“Ｃ゛で書かれたコンピュータプログラムのリ ストである。（“５ＰＡＲＣｓｔａｔ　ｉｏｎ”はサンマイクロシステム株式会 社の登録商標であり、“ＵＮＩＸ’は、アメリカン電信電話会社の登録商標であ る。

）以下の記述及び図４は、四角枠に囲まれたプログラムラベルによって付録Ａの プログラムセクションを説明している。

終点拡大器４０は、文字ビットマツプの終点の位置及び方向を測定する、特性に 基づく手順である。（例えば、図３の終点３２−３５参照。）判断ステ・ツブ２ ５によって開始された（図２参照）終点拡大器４０は、図４の読み取りステ・ノ ブ４１において、ビットマツプ形成ステップ１９（図２参照）で形成されたと・ ノドマツプを読み取る。読み取りステップ４１は、プログラムセクション［ｇｅ ｔ−ｐａｉｎｔ　１ｉｓｔ（）コにおいて行われる（付録Ａ参照）。

次に、終点拡大器４０は、ストローク終点の位置及び方向をめてビットマ・ツブ を分析する。この機能を行うために、終点拡大器４０はまずビットマ・ツブをポ イント分布関数（ｐｏｉｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｒｕｎｃｔｉｏｎ　 ）として処理し、次にその電位プロファイル（ｐｏｔｅｎｔｉａｌ　ｐｒｏｆｉ ｌｅ　）　Ｖ　（ｘ、ｙ）を検出する。ここで、Ｘ及びｙはビットマツプにおけ る画素位置の直交座標である。これらの機能は電位プロファイルステップ４２（ 図４膠照）において行われる。電位プロファイルステ・ノブ４２は、プログラム セクション［５ｅｔｕｐ　ｄｅｌｔａ　ｖ　０１　［ｃｏｍｐｕｔｅ　ｐｏｔｅ ｎｔｉａｌｓ　Ｏコ　（付録Ａ）に対応する。

より詳細には、ビットマツプ３０（図３参照）の黒の画素（ドツト）のセ・ソト が、ボワソン微分方程式により電位関数Ｖ　（ｘ、ｙ）に関連するポイント分布 関数を構成する。プロセスを簡略化するために、ビットマツプ３０の黒の画素の それぞれは静電荷（例えば負の電荷）として形成される。ビットマップ３０全体 は、誘電体表面上の電荷分布として形成される。このモデルを用いることにより 、電位関数Ｖ　（ｘ、ｙ）は電荷分布により生成される電位（ボルト）に対応す る。ビットマツプ３０に対する電位Ｖの電位プロファイルは、下記に示す式（１ ）のボワソン微分方程式を用いて計算される。

上記の式において、Ｖ−Ｖ（ｘ、ｙ）（電位プロファイル）ρは任意のポイント における電荷密度、εは比誘電率。

実際には静電荷は含まれていないので、いくつかの簡略仮定がこのモデルに対し 行われる。第１に、式（１）の右辺には、黒の画素位置における定数及びそれ以 外の位置におけるゼロ（白の画素）を代入できる。さらに、電位Ｖ　（ｘ、ｙ） に対する正確な解答は要求されないので、各電荷（黒の画素）はその周辺にわす かな影響力しか持たないと仮定される。これらの仮定により、この電荷に基づく モデルを使用した場合、電位プロファイルＶ　（ｘ、ｙ）を得るためのプロセス かかなり加速される。

図５は、図４の電位プロファイルステップ４２において計算される通常の電位プ ロファイルＶ　（ｘ、ｙ）を示す。図５から、端部方向に位置する黒の画素が比 較的低い電位Ｖを有することが明らかである。さらに、文字の末端部（例えば、 ストローク終点３２−３５）に位置する端部画素は、最も低い電位Ｖを有し、し きい値決めによりビットマツプから孤立される（ｉｓｏｌａｔｅａ）。しきい値 決めは、しきい値決めステップ４３（図４２照）及びプログラムセクション［ｂ ｅｌｏｎｇｓ　ｔｏ　ｃｏｒｎｅｒ　（）：において行われるプロセスである。

図６は、図３のビットマツプ３０のしきい値決めされた画素を示す。

通常は、４つの終点３２−３５のように複数の終点があり、さらに、各終点は複 数の画素を含むので（図６参照）、図４に示される終点拡大器４０のしき（旭値 決めステップ４３を行うたけては不十分である。つまり、しきい値決めされた画 素の隣接する領域が集結され、集合領域が形成されなければならない。集合領域 は領域形成ステップ４４に及びプログラムセクション［ｂｕｉｌｄ　ｃｏｎｔｉ ｇｕｏｕｓ　ｒｅｇｉｏｎｓ　（）１　、［ｍａｒｋ　ｒｅｇｉｏｎｓＯＪｌこ お（）で配置される。この領域形成機能は、しきい値決めされた画素のｘ−ｙ位 置を検出し、互いに隣接する画素を配置することにより行われる。続いて、隣接 する画素が領域に結集される。図６には、４つの領域が例示されている。

このように、領域の位置が図４に示される領域位置ステ・ツブ４５にお０て決定 される。ステップ４５は、プログラムセクション［ｇｅｔ　ｒｅｇｉｏｎ　１ｎ ｔｏ　Ｏ］において行われる。領域位置は、その平均性−列座［ｘｉ及びｙｉを 次のように検出することにより決定される。ｎ個の領域と、１番目の領域におけ るｋｌ＠のポイントがある場合、下記の式（２）及び（３）によってめられる。

次に、領域方向が領域方向ステップ４６において決定される。領域方向ステ・ノ ブ４６は、プログラムセクション［ｇｅｔ　ｒｅｇｉｏｎ　１ｎｆｏ　Ｏ］及び ［ｇｒａｄｉｅｎｔ　０１に対応する。領域方向は、まず電位Ｖの勾配Ｆを検出 することにより決定される。すなわち、Ｆ　（ｘ、Ｙ）−ｇｒａｄ　Ｖ　（ｘ、 ｙ）である。静電荷モデルを用いることにより、Ｆはポイント（ｘ、ｙ）におけ る電界に対応する。Ｆのｘ−ｙ要素を用いることにより、領域方向が式（４）に よって次のように与えられる。

上式において、呼及び　Ｆγ　は、それぞれ、その勾配のＸ及びｙ要素であり、 θは、Ｘ軸から左回りに測定された角度である。

図６は、グラフにより、図２の手書き文字“Ａ”の終点３２−３５に対して生成 された領域の空間的位置、及び終点３２−３５が方向づけられる角度θ１を示す 。具体的には、終点３２は２６９度で下方に方向付けられる。終点３２とほぼ平 行位置にある終点３３は、２７１度に方向付けられる。終点３５は６０度に、終 点３４は３４２度に方向付けられる。

次に、処理されているビットマツプの終点位置及び方向の２値符号が、図４の符 号ステップ４７において計算される。このステップ４７は、プログラムセクショ ン［ｈｃ　ｐａｃｋｅｄ　ｂｉｎ　ｆｉｌｔｅｒＯ］　［ｇｅｔ　ｐａｃｋｅｄ 　ｂｉｎａｒｙ　ｆｅａｔｕｒｅｓ　０１及び［ｇｅｔ　ｐａｃｋｅｄ　ｂｉｎ ａｒｙ　ｆｖＯ］に対応する。２値符号は、空間的及び方向の広がり（ｄｉｍｅ ｎｓｉｏｎｓ）を、ここではＸビン、Ｘビン、及びθビンと定められる多数のビ ンに分割することにより形成される。（付録Ａのプログラムの被定義定数（ｄｅ ｆｉｎｅｄ　ｃ。

ｎ５ｔａｎｔ）　ＸＢ　Ｉ　ＮＳ、　ＹＢ　ＩＮＳ及びＴＨＥＴＡ　ＢＩＮＳ参 照。）図６に示されるように、ビットマツプ３０の領域は、Ｘおよびｙビンに対 応する９の領域に分割される。Ｘ及びｙビンの境界は、それぞれｘ−１，１３， ２６，３９、ｙ−１，２０，４０，６０の位置である。

Ｘビン、ｙビン、及びθビンのそれぞれは、終点位置及び方向の特定の組み合わ せを表す。図７には、３個のＸビン、３個のｙビン、及び４個のθビンがある状 況が例示される。少なくとも１つの領域がその範囲内に当たれば単位元の値（１ ）が割り当てられ、そうでない場合はＯが割り当てられる。この規則に基づき、 図７のビン３５′　には次の理由から１が割り当てられる＝　（１）図６の対応 するＸ及びｙのビンが終点３５を含む。（２）終点３５は６０度の方向を有する 。

同様に、終点３２．３３．３４の位置及び方向にそれぞれ対応するので、ビン３ ２’　、３３’　、３４°には全て１が割り当てられる。その他の終点が配置さ れていないので、その他のビンのそれぞれには０が割り当てられている。最終的 に、これらの１及び０を所定の方法で配列し、図７に示されるような２値打号ベ クトルを形成する。

この符号ベクトルは、図４に示される比較ステップ４８において、符号ベクトル 及びそれに関連する文字列の記憶データベースに比較され、この文字列の要素と 「最適な」信頼度基準を有する識別された候補文字の間で文字の一致を行う。

一致するものが１つだけの場合、出力ステップ４９において、その一致した候補 文字が出力文字として報告される。複数の一致する候補文字がある場合は、最高 値の信頼度基準を有する一致文字が出力ステップ４つにおいて出力文字として報 告される。

符号データベースはトレーニング段階（ｔｒａｉｎｉｎｇ　ｐｈａｓｅ）の間に 生成される。

このデータベースは、構造体のアレイとして（ａｓ　ａｎ　ａｒｒａｙ　ｏｆ　 ５ｔｒｕｃｔｕｒｅｓ　）　：１ンピユータ１７に記憶される。これに関し、プ ロセッサ２０はトレーニングセット、すなわち多数の既知の文字ビットマツプに より訓練される。プロセッサ２０は既知のビットマツプのこのトレーニングセッ トを終点拡大器４０に供給し、ここで処理する。符号ステップ４７において各符 号ベクトルが形成されると、このベクトル及び関連する文字が符号データベース に記憶される。符号データベースは、符号−文字列の対のリストから成る。さら に、各符号がトレーニングセットの処理中に発生した（ｅｎｃｏｕｒ＋ｔｅｒ　 ）回数も含まれている。符号−文字列の６対において、文字列は対応する符号を 発生したトレーニングセットのすべての文字を含んでいる。

以下に示す表Ａは、さまざまなソース（ディジタイザ、スキャナ、及びその他） から収集した大きいトレーニングセット（約１０，０００文字）を用いて作成さ れたデータベースのセクションを列挙したものである。簡潔性のために、ここで 示すデータベースセクションには９要素（３ｘ　３　ｘ　１）の２値符号が示さ れている。この符号には位置情報は示されていない。表Ａの第１エントリーは、 このトレーニングセットが、同じ符号を２１回発生した文字０，２．４、ＣＳＧ のビットマツプを含むことを示している。第２エントリーは、文字セットの全て の要素（３６文字）を含む文字セットが２．３８４回、終点を生成することに失 敗したことを示す。この点に関し、終点を得られないのには多くの理由が考えら れる。

たとえば、文字にはしばしば終点がない（たとえばＯ）、あるいは、終点のスト ロークが読みとるのに十分な大きさでなかったなどである。

表Ａ 訓練データベース ｏｌｏｏｏｌｏｏ。

０１２３４５６７Ｂ９ＡＢＣＤＥＦＧＨＩＪＫＬＭＮＯＰＱＲＳＴＵＶＷＸＹＺ 　２３８４ｏｏｏｏｏｏｏｏ。

０２３４５６７８ＢＤＦＧＨＪＫＬＭＮＯＰＲＴＵＶＷＸＹＺ　４０５１ｏｏｏ ｏｏｏｏ。

０１５６９ＰＧＵＫＭＮＳＴＷＸＹ　４６１０１４５６８９ＣＥＦＧ工ＪＫＭＩ ＮＰＲ５ＸＹ　４１６ｏｏ１ｏｏｏｏｏ。

０２３５９ｋＢＤＥＦＧ工ＪＫＸＮＰＲ５ＸＹ　５６０ｏｏｏｏｏｏ１ｏ。

０１２４５６８ＡＢＣＤＥＦＧＨ工、７ＫＬＭＮＯＰＱＲ５ＵＷＸＹ　５５９０ ４８ＨＪＫＭＮＵＷＹ　コロ ０ＣＥＦＧＸ　４５ １４６Ｈ工ＪＫＳＹ　７２ １４５７８９ＡＢＣＤＦＧ、ＴＬＰＱＳＴＵＶＹ　１８１ｏｏｏｏｏｏｏ１゜ ＩＫＴＷ　５８ １７Ａ工ＫＸ　８ １２ＡＢぴＸα　３２０ １３７ＢＤＪＫＰＴＹ　１０７ ００００１０１３５６７ＡＢＤＨＩＪＫ　１２３１２７Ｅ１（ＫＬＭＲＵＸＺ　 ２９０ １２ＡｃＥＧＨＫＬＭＱＵＺ　１４１ ２ＡＢＤＥＦＴＸ　１２ ２ＥＧＭＱＲＤ ｏｏｏｏｏｏｏｌｌ ２ＡＢＣＥＦＧＬＺ　５３ ｏｏｏｏｏｔｏｏ。

２ＥＨＬＵＺ　１２２ ２Ｍ　７ １００００１００１゜ ２７９ＡＣＤＥＧＨＫＬＭＮＱＲＴＵＺ　コ２ｏｏｏ１ｏｏｏｏ。

２６７ＥＧＺ　１３ ２７ＡＱＲＴＵＺ　２０ ２Ｅと　６ ２Ｈ工ＫＭＲＸＹＺ　６９ ２３５６７ＢＤＥＦＨ工、：ＴＫＫＰＲＸＹＺ　２２３付録Ａの複数のプログラ ムセクションが図４の比較ステップ４８に対応する。

プログラムセクション［ｈｃ　ｐａｃｋｅｄ　ｂｉｎ　１ｏａｄ　□コは、デー タベースをファイルからロードする。　１ｍ５ｅａｒｃｈ□］及び［ｍｆｉｎｄ Ｏコのセクションは、データベースのメトリックサーチ（ｍｅｔｒｉｃ　５ｅａ ｒｃｈ　）を行うことにより符号を調べ、次に特定の一致基準に見合った要素の リストを戻すために用いられる。この場合、相対的なハミング距離メトリック法 が用いられる。

（プログラムセクション［５ｕｂｓｅｔｈｏｏｄ　Ｏ］　［ｒｅｌａｔｉｖｅ　 ｈａｍｍｉｎｇ　ｄｉｓｔａｎｃｅ　Ｏ］　［ｎｕｍ　ｏｎｅｓ　Ｏ］　［ｘｏ ｒ　０１［ａｎｄＯ］参照。）出力ステップ４９はプログラムステップ［ｇｅｔ 　１ｎｄｅｘＯコに対応する。

多項式に基づ＜ＯＣＲ手順が用いられ、ＤＥＣｓｔａｔｉｏｎ　３１００タイプ ワークステーシヨンに取り付けられたＧＴＣディジタイザ／ベンによって発生す る３６００文字ビットマツプに関するプロセッサ２０の性能がテストされた。

（“ＤＥＣｓｔａｔｉｏｎ”は、ワークステーションも製造するディジタル　イ クワイブメント　コーポレーシヨンの商漂である。）多項式アルゴリズムは、終 点拡大器４０を使用せずそれだけで用いた場合、９２．４２％の正確さを得た。

終点拡大器４０と組み合わせると、正確さは９４．１４％にまで向上し、エラー を２２．７％低減できる。

上記の教示を鑑みて本発明の多くの修正及び変更が可能であることは明かである 。従って、本発明は、添付のクレームの範囲内で、前述の特定の方法以外でも実 行できることが了解されよう。

産業上の応用及び利点 本発明は、光学的文字認識（ＯＣＲ）システムとの関連において有益である。

詳細には、そのようなシステムとともに用いられた場合、本発明は、従来の技術 において獲得可能であった以上に、文字４歳の正確さを有利に増加できる。

付録Ａ この付録は、ＵＮＩＸオペレーティングシステムを実行するＳｕｎ　５ＰＡＲＣ ｓｔａｔｉｏｎの、コンピュータ言語“Ｃ２で書かれたコンピュータプログラム リストから成る。（“５ＰＡＲＣｓｔａｔｉｏｎ”はサンマイクロシステム株式 会社の登録商標であり、“ＵＮＩＸ”は、アメリカン電信電話会社の登録商標で ある。） このプログラムリストは終点セグメンタ４０の実施である。

図１ 図２ 図４ ン ［ｇｅｔＪｏｉｎｔ−１ｉｓｔ（］］ ［ｃｏｍＦｅ」ａｔｅｎｔｉａｌｓＯ］ｄｅｌｔａ３０１ しきい値決め　４３ ［ｂｅｌｏｎｇｓ　Ｊｏ　ｃｏｒｎｅｒ　Ｑ　］図７

Claims (1)

1. 【特許請求の範囲】 １　入力された文字を、定められた文字セットの特定の要素として識別する文字 認識システムであり、 入力された文字の文字ビットマップを生成するためのビットマップ手段と、前記 文字ビットマップを処理し、前記文字セットの各要素に対し１つづつの信頼度基 準のセットを生成し、前記信頼度基準は前記入力文字が前記文字セットの要素に 対応する程度を表す文字認識手段と、最高程度の信頼を有する信頼度基準が受け 入れ可能な信頼度基準であるかを判断する判断手段と、 前記受け入れ可能な信頼度基準を有する前記文字セットの要素を、出力文字とし て報告するための第１出力手段と、 前記判断手段が受け入れ可能な判断基準がないと判断した場合、前記要素のうち のＮ番目までの最高信頼度基準値を有するＮ個の要素を識別し、前記ビットマッ プを処理し、前記ビットマップの文字特性を測定するための測定手段と、前記文 字特性の前記測定に基づき、前記Ｎ個の要素のうちの１つを出力文字として報告 するための第２出力手段と、を有する拡大器手段と、によって特徴づけられる文 字認識システム。 ２　請求項１記載のシステムにおいて、前記拡大器手段は、文字列のデータベー スを有するデータベース手段により特徴づけられ、各前記文字列は前記文字セッ トのサブセットを含み、各前記サブセットの要素は前記測定手段により測定され た前記特性を共通に有するシステム。 ３　請求項２記載のシステムにおいて、前記測定手段は前記ビットマップのスト ローク終点の位置を測定することを特徴とするシステム。 ４　請求項３記載のシステムにおいて、前記測定手段は前記ストローク終点の方 向を測定することを特徴とするシステム。 ５　請求項４記載のシステムにおいて、前記データベース手段は、それぞれが前 記文字列の１つに関連する独自のデータベース符号により特徴づけられ、前記測 定手段は前記ストローク終点の前記位置及び方向に関する検索符号を生成するた めの手段から成り、前記拡大器手段は、前記検索符号に応じて前記データベース 符号を検索し出力文字列を識別し、前記出力文字列とＮ番目までの最高信頼度基 準値を有するＮ個の要素との間の一致を行うための検索手段から成ることを特徴 とするシステム。 ６　請求項５記載のシステムにおいて、第２出力手段は次の規則に従い前記Ｎ個 の要素の１つを出力文字として報告することを特徴とする；前記Ｎ個の要素のう ちのただ１つと前記出力文字列の間に一致がある場合、その一致した要素を出力 文字として報告する；前記Ｎ個の要素の２つ以上と前記出力文字列の間に一致が ある場合、最高信頼度基準値を有する一致した要素を出力文字として報告する； 前記Ｎ個の要素と前記出力文字列の間に一致がない場合、最高信頼度基準値を有 する要素を出力文字として報告する。 ７　請求項６記載のシステムにおいて、Ｎは２と同値であることを特徴とするシ ステム。 ８　請求項６記載のシステムにおいて、前記測定手段は、前記ビットマップの電 荷分布モデルに基づき電位プロファイルを形成するための電荷モデル手段と、前 記電位プロファイルをしきい値決めし、前記しきい値決めされたプロファイルを 結集して前記ストローク終点の位置を決定するための位置手段とにより特徴づけ られるシステム。 ９　請求項８記載のシステムにおいて、前記測定手段は、前記電位プロファイル の勾配を獲得し前記ストローク終点の前記方向を決定するための勾配手段により さらに特徴づけられるシステム。 １０　Ｎ個の候補文字のうちのどれが定められた文字セットのうちの特定の要素 を表すかを識別するストローク終点検出器であり、入力されたビットマップを読 み出すためのビットマップ手段と、文字列のデータベースを有するデータベース 手段であり、前記文字列のそれぞれが前記文字セットのサブセットから成り、各 前記サブセットの要素が共通ストローク終点特性を有するデータベース手段と、 前記文字ビットマップのストローク終点特性を測定するための測定手段と、前記 測定手段に対応し、前記データベースを検索し、出力文字列を識別し、前記出力 文字列と前記Ｎ個の候補文字をの間の一致を行うための検索手段と、前記検索手 段に対応し、一致する候補文字を出力文字として報告するための出力手段と、 により特徴づけられるストローク終点検出器。 １１　請求項１０記載の検出器において、前記測定手段は、前記ビットマップの 前記ストローク終点の位置を測定する手段により特徴づけられる検出器。 １２　請求項１１記載の検出器において、前記測定手段は前記ストローク終点の 方向を測定するための手段から成ることを特徴とする検出器。 １３　請求項１２記載の検出器において、前記データベース手段はそれぞれが前 記文字列の１つに関連する独自のデータベース符号により特徴づけられ、前記測 定手段は前記ストローク終点の前記位置及び方向に関連する検索符号を生成する 手段から成り、前記検索手段は、前記検索符号に応じて前記データベース符号を 検索して前記出力文字列を識別し、前記出力文字列と前記Ｎ個の候補文字の間の 一致を行うための手段から成ることを特徴とする検出器。 １４　請求項１３記載の検出器において、前記Ｎ個の候補文字はそれぞれ関連す る重み関数（ｗｅｉｇｈｔｉｎｇｆａｃｔｏｒ）を有し、前記出力手段は次の規 則に従い前記Ｎ個の候補文字の１つを出力文字として報告するための手段により 特徴づけられる：前記Ｎ個の要素のうちのただ１つと前記出力文字列の間に一致 がある場合、その一致した要素を出力文字として報告する；前記Ｎ個の要素の２ つ以上と前記出力文字列の間に一致がある場合、最高値の重み関数を有する一致 した要素を出力文字として報告する；前記Ｎ個の要素と前記出力文字列の間に一 致がない場合、最高値の重み関数を有する要素を出力文字として報告する。 １５　請求項１４記載の検出器においてＮは２と同値であることを特徴とする検 出器。 １６　請求項１４記載の検出器において、前記測定手段は、前記ビットマップの 電荷分布モデルに基づき電位プロファイルを形成するための電荷モデル手段と、 前記電位プロファイルをしきい値決めし、前記しきい値決めされたプロファイル を結集して前記ビットマップの前記ストローク終点の領域の位置を決定するため の位置手段とにより特徴づけられるシステム。 １７　請求項１６記載のシステムにおいて、前記測定手段は、前記電位プロファ イルの勾配を獲得し前記ストローク終点の方向を決定するための勾配手段により さらに特徴づけられるシステム。 １８　入力された文字を、定められた文字セットの特定の要素であると識別する ための文字認識方法であり、 入力された文字の文字ビットマップを生成するステップと、前記文字ビットマッ プを文字認識手順により処理し、前記入力文字が前記文字セットの前記要素に対 応する程度を表す信頼度基準を、前記文字セットの各要素に対し１つづつ生成し 、信頼度基準のセットを生成するステップと、最高程度の信頼を有する信頼度基 準が受け入れ可能な信頼度基準であるかを判断するステップと、 受け人れ可能な信頼度基準がある場合、前記受け入れ可能な信頼度基準を有する 前記文字セットの要素を、出力文字として報告するステップと、受け入れ可能な 信頼度基準がない場合、Ｎ番目までの最高信頼を有するＮ個の前記要素を識別し 、前記ビットマップを分析して前記ビットマップの文字特性を測定するステップ と、 前記文字特性の測定に基づき前記Ｎ個の要素のうちの１つを出力文字として報告 するステップと、 により特徴づけられる文字認識方法。 １９　請求項１８記載の方法において、文字列のデータベースを形成するステッ プによってさらに特徴づけられ、各前記文字列は前記文字セットのサブセットを 含み、前記サブセットの要素は共通の文字特性を有し、前記分析ステップは前記 データベースを検索するステップを有することを特徴とする方法。 ２０　請求項１９記載の方法において、前記文字特性は前記ビットマップのスト ローク終点の位置を特徴づけることを特徴とする方法。 ２１　請求項２０記載の方法において、前記文字特性は前記ストローク終点の方 向を特徴づけることを特徴とする方法。 ２２　請求項２１記載の方法において、それぞれが前記文字列の１つに関連する 特定の符号を有する前記データベースを形成し、前記分析ステップにおいて検索 符号を生成して前記ストローク終点の位置及び方向を決定するステップと、 前記検索ステップにおける前記検索符号を用いて前記データベース符号を検索し て出力文字列を識別し、前記出力文字列とＮ番目までの信頼度基準を有する前記 Ｎ個の要素との間の一致を行うステップと、によりさらに特徴づけられる方法。 ２３　請求項２２記載の方法において次の規則に従い前記Ｎ個の要素の１つを出 力文字として報告するステップによりさらに特徴づけられる方法：前記Ｎ個の要 素のうちのただ１つと前記出力文字列の間に一致がある場合、その一致した要素 を出力文字として報告する；前記Ｎ個の要素の２つ以上と前記出力文字列の間に 一致がある場合、最高値の信頼度基準を有する一致した要素を出力文字として報 告する；前記Ｎ個の要素と前記出力文字列の間に一致がない場合、最高値の信頼 度基準を有する要素を出力文字として報告する。 ２４　請求項２３記載の方法において、Ｎは２と同値であることを特徴とする方 法。 ２５　請求項２３記載の方法において、前記分析ステップは、前記ビットマップ の電荷分布モデルに基づき電位プロファイルを形成するステップと、 前記電位プロファイルをしきい値決めし、しきい値決めされたプロファイルを形 成するステップと、 前記しきい値決めされたプロファイルを結集して前記ビットマップの前記ストロ ーク終点の領域の位置を決定するためのステップと、によりさらに特徴づけられ る方法。 ２６　請求項２５記載の方法において、前記分析ステップは前記電位プロファイ ルの勾配を獲得して前記ストローク終点の方向を決定するステップを特徴とする 方法。 ２７　Ｎ個の候補文字のうちのどれが定められた文字セットの特定の要素を表す かを識別するストローク終点検出方法であり、入力ビットマップを読みとるステ ップと、文字列の学習されたデータベースを形成するステップであり、各前記文 字列は前記文字セットのサブセットから成り、前記各サブセットは共通のストロ ーク終点特性を有するステップと、 前記文字ビットマップのストローク終点特性を測定するステップと、前記データ ベースを検索して出力文字列を識別し、前記出力文字列と前記Ｎ個の候補文字の 間の一致を行うステップと、前記一致のうちの１つを出力文字として報告するス テップと、から成るストローク終点検出方法。 ２８　請求項２７記載の方法であり、前記測定ステップは前記ビットマップの前 記ストローク終点の位置を測定するステップを特徴とする方法。 ２９　請求項２８記載の方法であり、前記測定ステップは前記ストローク終点の 方向を測定するステップを特徴とする方法。 ３０　請求項２９記載の方法であり、 それぞれが前記文字列の１つに関連する独自の符号により前記学習されたデータ ベースを形成するステップと、 前記分析ステップにおいて検索符号を生成して前記ストローク終点の位置及び方 向を決定するステップと、 前記検索ステップにおいて前記検索符号を用いて前記データベース符号を検索す るステップと、 によりさらに特徴づけられる方法。 ３１　請求項３０記載の方法において、前記Ｎ個の候補文字はそれぞれ関連する 重み関数（ｗｅｉｇｈｔｉｎｇｆａｃｔｏｒ）を有し、前記報告ステップは次の 規則に従い前記Ｎ個の候補文字の１つを出力文字として報告することを特徴とす る：前記Ｎ個の要素のうちのただ１つと前記出力文字列の間に一致がある場合、 その一致した要素を出力文字として報告する；前記Ｎ個の要素の２つ以上と前記 出力文字列の間に一致がある場合、最高値の重み関数を有する一致した要素を出 力文字として報告する；前記Ｎ個の要素と前記出力文字列の間に一致がない場合 、最高値の重み関数を有する要素を出力文字として報告する。 ３２　請求項３１記載の方法において、Ｎは２と同値である方法。 ３３　請求項３１記載の方法において、前記測定ステップは電荷モデルを用いて 前記ビットマップの電荷分布モデルに基づき電気プロファイルを形成するステッ プと、 前記電位プロファイルをしきい値決めし、しきい値決めされたプロファイルを形 成するステップと、 前記しきい値決めされたプロファイルを結集して前記ビットマップの前記ストロ ーク終点位置の領域の位置を決定するステップと、をさらに特徴とする方法。 ３４　請求項３３記載の方法において、前記測定ステップは前記電位プロファイ ルの勾配を獲得し前記ストローク終点の方向を決定するステップによりさらに特 徴づけられる方法。