JPH0628526A

JPH0628526A - 手書き文字認識法

Info

Publication number: JPH0628526A
Application number: JP4243101A
Authority: JP
Inventors: Charles Carson Tappert; チャールズ、カーソン、テーパート
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-10-30
Filing date: 1992-09-11
Publication date: 1994-02-04
Also published as: EP0539740A2; EP0539740A3

Abstract

(57)【要約】【目的】コーナ及び先端における改良された弾性マッ
チング及び手書文字認識システムを提供する。【構成】弾性マッチング認識装置内におけるコーナス
キップコスト関数はプロトタイプのコーナ或は先端がス
キップされたとき、未知の文字とプロトタイプ文字との
間の一致距離を増加させる。コーナの識別は文字のライ
ンセグメント上のあるポイントの所の角度変化の尺度に
基づく。ポイントの生の角度変化測定値は現ポイントか
ら次のポイントまでのラインセグメントの方向角度から
前のポイントから現ポイントまでのラインセグメントの
方向角度を引いた値である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、信号処理の分野、より
詳細には、手書き文字の認識に関する。より具体的に
は、本発明は、弾性(elastic) マッチングオンライン文
字認識システムにおけるコーナ及び先端の所のマッチン
グを向上させることを意図する。

【０００２】

【従来の技術】手書き文字認識においては、文字を認識
するに当っての困難さが伴い、これはコーナ及び先端の
所で増加する。手書き文字の認識を目的とする複数の特
許が存在し、それぞれ、幾つかの長所及び短所を持つ。

【０００３】バック（Buck）に交付された合衆国特許第
４，８１７，１７９号はデジタルマトリックス、例え
ば、デジタル化されたイメージに向けられるが、これら
イメージは、向上されるべきマトリックスをマトリック
スの個々の要素のマトリックス内の個々の位置において
複数の向上パータン（enhancement pattern ）と比較
し、向上パターンとの一致度に比例するパターンコード
を生成することによって向上される。これらパターンコ
ードがマトリックスの個々の要素に対する複数の向上決
定（enhancement decision）を生成するために使用さ
れ、これら向上決定が結合され、マトリックスの個々の
要素に対する単一の向上動作（enhancement action）が
取られる。但し、コーナ及び先端の処理に関しての教示
はない。

【０００４】エロジー（Ellozy）らに交付された合衆国
特許第５，００５，２０５号は第一の文字を類似する特
性を持つ第二の文字から弁別するための方法を含む手書
き文字識別システムを開示する。この方法は、トレーニ
ングセッションにおいて、第一の文字及び第二の文字と
関連する少なくとも一つのペアの弁別尺度（discrimina
nt measure）を決定するステップを含む。この決定ステ
ップは、潜在的な弁別尺度にて、複数のプロトタイプの
第二の文字を評価するステップを含む。その後、手書き
文字識別セッションにおいて、この方法は、セットの弁
別尺度から選択された少なくとも一つ前に決定された弁
別尺度にて第一のプロトタイプ文字或は第二のプロトタ
イプ文字のいずれかとして識別される入力文字を評価す
る。この評価ステップは、入力文字と関連する一つ或は
複数のストロークをセットの弁別尺度から選択された一
つ或は複数のペアの識別尺度に従って分析し、個々の弁
別尺度分析の結果を総和して、これらペアの弁別尺度と
関連するペアの文字の各々に対する結果を得、このペア
から最大値の結果を与える文字を選択するステップを含
む。但し、コーナ及び先端の処理に関する教示は含まれ
ない。

【０００５】リップスコム（Lipscomb）に交付された合
衆国特許第５，０２３，９１８号はライティングタブレ
ット上のライティング器具のストロークを表わすベクト
ルの終点を表わすデジタル値のシーケンスをフィルタリ
ングするための装置及び方法を開示する。ストロークを
構成するベクトルのクロス積及びドット積がストローク
が実質的に直線である互いに接近したポイントのサンプ
ルを生成するために計算される。ここでは、コーナ及び
先端の処理に関しての教示はあるが、認識プロセスにお
けるコーナ及び先端と関連しての教示はない。

【０００６】Ｊ．Ｍ．クルツベルグ（Kurtzberg ）及び
Ｃ．Ｃ．タパート（Tappert ）によって、ＩＢＭ技術小
冊子、Ｖｏｌ．２４、Ｎｏ．６、ページ２８９７−２９
０２、１９８１年号に掲載の論文『弾性マッチングによ
る記号認識システム（SymbolRecognition System by El
astic Matching ）』は、記号を認識するために弾性マ
ッチングを使用するための技術を開示する。但し、ここ
でも、コーナ及び先端に関する教示はない。

【０００７】Ｃ．Ｃ．タパートによって、ＩＢＭ技術開
示小冊子、Ｖｏｌ．２４、Ｎｏ．１１Ａ、ページ５４０
４−５４０７に掲載の論文『弾性マッチングによる続き
書き文字認識システム（Cursive Script Recognition S
ystem By ELastic Matching）』は、続き文字を認識す
るために弾性マッチングを利用する技術を開示する。但
し、ここでも、コーナ及び先端の処理に関する教示はな
い。

【０００８】

【発明の概要】本発明の一つの目的は、改良された手書
き文字認識システムを提供することにある。

【０００９】本発明のもう一つの目的は、改良された弾
性マッチング手書き文字認識システムを提供することに
ある。

【００１０】本発明のさらにもう一つの目的は、コーナ
及び先端における改良された弾性マッチング及び手書き
文字認識システムを提供することにある。

【００１１】本発明によると、弾性マッチング認識装置
の向上がキーポイント、例えば、コーナ及び先端の所で
達成される。プロトタイプ文字のコーナ或は先端がスキ
ップされた場合、未知の文字とプロトタイプ文字との間
の一致距離（match distance）を増加させるためにコー
ナスキップコスト関数が弾性マッチヤー（elastic matc
her ）に加えられる。

【００１２】弾性マッチング認識装置内におけるコーナ
スキップコスト関数はプロトタイプのコーナ或は先端が
スキップされたとき、未知の文字とプロトタイプ文字と
の間の一致距離を増加させる。コーナの識別は文字のラ
インセグメント上のあるポイントの所の角度変化の尺度
に基づく。ポイントの生の角度変化測定値は現ポイント
から次のポイントまでのラインセグメントの方向角度か
ら前のポイントから現ポイントまでのラインセグメント
の方向角度を引いた値である。

【００１３】

【実施例】本発明は手書き文字の認識に適用される弾性
マッチング（elastic matching）アルゴリズムの改良を
意図する。最初に典型的な弾性マッチングアルゴリズム
について説明する。図１に示されるように、未知の文字
をプロトタイプと一致するか比較する（マッチングす
る）場合、未知の文字内の任意のポイントｉとｋ番目の
プロトタイプ内のポイントｊとを比較するために距離メ
トリック（distance metric ）が使用される。一般的な
ポイント距離（point distance）はユークリッド距離で
ある。

【００１４】ポイント距離が未知の文字をプロトタイプ
と比較するための総距離（overalldistance）を得るた
めに使用される。この総距離はプロトタイプの部分につ
いての非線型弾性（non-linear elasticty）を可能にす
る。つまり、これを２倍にまで拡張し、また、２分の１
にまで圧縮することを可能にする。これは書く速度の通
常の差を考慮するものである。つまり、この速度の差に
よって同一の文字を反復して書いた場合、長さに変動が
起こり、また文字の形状に非線型の時間変動が起こる。
数学的には、未知の文字とプロトタイプとの間の総距離
は、以下の式に示されるように、ウォーピング関数（wa
rping function）の全ての可能な選択に対するｄ（ｉ，
ｊ；ｋ）の総和の最小値を計算することによって見出さ
れる。

【００１５】

【数１】ここで、Ｎは未知の文字の長さであり、ｗは未知の文字
の時間インデックスをプロトタイプの時間インデックス
にマッピングするウォーピング関数であり、Ｄ_kはプロ
トタイプｋと未知の文字との間の総距離である。境界条
件ｗ（１）＝１及びｗ（Ｎ）＝Ｍ_k、（ここでＭ_kはプ
ロトタイプの長さを表わす）は、プロトタイプの最初及
び最後のポイントがそれぞれ未知の文字のこれらポイン
トにマッチすることを表わす。さらに、連続条件ｗ（ｉ
＋１）−ｗ（ｉ）＝０、１、２；（ｉ＝１、．．．．．
Ｎ−１に対して）は、ウォーピング関数を単調的に増加
する関数に制限し、時間的に永久に増加する通常の概念
を保存し、拡張及び圧縮の程度を制限する。

【００１６】この距離は以下の反復的な関係を使用する
ダイナミックプログラミングによって効率的に計算され
る。

【００１７】

【数２】ここで、Ｄ（ｉ，ｊ；ｋ）は（１，１）から（ｉ，ｊ）
までの累積距離である。Ｄ（１，１；Ｋ）＝ｄ（１，
１；ｋ）から開始して、それよりも（無限に大きな）ど
こかＤ（ｉ，ｊ；ｋ）まで継続することにより、この累
積距離反復関係はモデルを通じての全ての可能な経路に
対してプロトタイプｋと未知の文字との間の最小距離Ｄ
_k＝Ｄ（Ｎ，Ｍ_k；ｋ）を得るために使用される。ここ
で、Ｎは未知の文字の長さを表わし、Ｍ_kはプロトタイ
プｋの長さを表わす。

【００１８】認識は以下のように実行される。未知の文
字が同数のストロークを持つ個々のプロトタイプに対し
てストローク対ストロークベースにて比較される。つま
り、未知の文字の第一のストロークがプロトタイプの第
一のストロークと比較され、第二のストロークが第二の
ストロークと比較される。一つのストロークはペンを降
ろした時からペンを上げる時までの書き込みである。未
知の文字には最も小さな総距離を与えるプロトタイプの
ラベルが割り当てられる（として認識される）。弾性マ
ッチング手順のフローチャートは図６に示されるもの
と、スキップコスト（SkipCost）項目がないことを除い
て同一である。

【００１９】上に説明されるような弾性マッチング認識
装置が手書き文字の認識に使用される場合、コーナ及び
先端等のようなキーポイントにおいて正しいマッチング
を達成することに関しての本質的な問題が存在する。先
端（cusp）は方向が反転するポイントである。このマッ
トング問題はプロトタイプ内のポイントが現存の弾性マ
ッチング手順ではコスト無しにスキップできると言う事
実に起因する。コーナ及び先端をスキップすることによ
って、未知の文字が正しくない文字クラスのプロトタイ
プと良く一致することがしばしばある。例えば、‘Ｌ’
のコーーがスキップされると、これは‘Ｃ’のように丸
く見える。また、‘ｋ’の先端がスキップされると、こ
れは、図２に示されるように‘ｈ’のように見える。

【００２０】ここでは、プロトタイプのコーナ或は先端
がスキップされたときの未知の文字とプロトタイプとの
間の一致距離を増加するために弾性マッチャ（elastic
matcher ）に追加されるコーナスキップ（corner-skip
）コスト関数（cost function ）が開示される。コー
ナの識別はあるポイトンにおける角度変化の測定に基づ
く。ポイトンの生の角度変化測定は現ポイントから次の
ポイントまでのラインセグメントの方向角度から前のポ
イトンから現ポイントまでのラインセグメントの方向角
度を引いた値である。角度変化が０（角度変化無し）か
ら１８０度（最大の方向反転）までのレンジ内の負でな
い値に“正規化”される。以降、正規化された角度変化
が単に“角度変化”と呼ばれる。

【００２１】コーナスキップコスト関数は以下のように
計算される。コーナスキップコスト関数にはプロトタイ
プの個々のポイントに対して一つの値が割り当てられ
る。コスト関数はゼロに初期設定される。そのポイント
がストロークエッジの付近でない場合（例えば、開始或
は終端の２点内にない場合）、そして、ポイントの角度
変化が大きな場合、つまり、好ましくは４２度である３
０度から５５度のレンジ内のある閾値よりも大きな場
合、及びこれが好ましくは２の係数とされる１．５から
３．０のレンジ内の係数だけ隣接する角度変化よりも十
分に大きな場合、コーンースキップコスト関数がある定
数に角度変化を掛けた値にセットされる。

【００２２】このアルゴリズムには４つの重要なパラメ
ータが存在する。第一は、ストロークエッジ付近でコス
ト関数をゼロにセットすることによってスキッピングフ
ック（skipping hook ）に対するコストがゼロとなるこ
とが確保される。“フック（hook）”はペンの上げ／下
げのレコーディングの不正確さに起因するストロークエ
ッジ（始端或は終端）の所で記録されるフック状の外観
を持つ余分なデータである。第二に、角度変化は大きく
なければならない。第三に、その角度変化がそれと隣接
する角度変化より十分に大きなことをチェックすること
によって、これがキーポイントであり、単なる曲線領域
の一点でない確率が向上される。曲線領域内のポイン
ト、例えば、手書き文字のループの最も上の所のこれら
ポイントは、例えば、‘ｅ’の場合のように、これら領
域の比較を助けるためにコスト無しでスキップすること
が望ましい。第四に、コーナスキップコスト関数をその
ポイントの所の角度変化に比例させることによって、コ
ストをコーナの鋭さに比例して増加できるが、これは望
ましい特徴である。

【００２３】図３には、本発明に従って構成及び動作さ
れる手書き文字認識システム１０の概要が示される。シ
ステム１０は書き込み手段、例えば、スタイラス１４を
持つ電子タブレット及びディスプレイ１２から成る手書
きトランスジューサを含む。手書き文字に応答して、ト
ランスジューサはタブレット１２の座標系に対するスタ
イラス１４の位置に対応する（ｘ、ｙ）座標ペアのシリ
アル流を出力する。この座標ペアはストロークセグメン
ト化器(stroke segmenter)１６に供給され、個々の手書
きストロークの開始及び終端が識別される。ストローク
は文字マッチャ(matcher) １８に提供される。文字マッ
チャ１８は所定の文字プロトタイプのメモリ２０に結合
され、入りストロークのポイントが格納された文字プロ
トタイプのポイントに対して比較され、結果として、あ
る確率の範囲内で、入りストローク或はストロークの組
立が特定の文字を表わすものと識別される。認識された
文字はマッチャ１８からライン１９を介してタブレット
及びティスプレイ１２に出力され、こうして認識された
文字が表示されるか、或はディスプレイ、ワード処理プ
ログラム等のような利用デバイス２１に供給される。幾
つかのシステムにおいては、セグメント化器１６及び文
字マッチャ１８の機能が一つの手書きストローク処理ユ
ニット内に結合される。

【００２４】文字プロトタイプはメモリ２０にシステム
１０のユーザによって行なわれるトレーニングセッショ
ンの際に供給される。文字プロトタイプはシステムの特
定のユーザによって入力され、その後、その特定のユー
ザが手書き文字を入力した時にのみ使用される。また、
複数のユーザによって使用するために、共通或は普遍セ
ットの文字プロトタイプを生成することもできる。

【００２５】これに関して、開始プロトタイプセットを
システム１０を最初に使用するときユーザによって使用
されるべき初期プロトタイプセットとして設計すること
もできる。必要であれば、ユーザは彼／彼女自身の書き
込みスタイルに文字プロトタイプを加えることによって
そのユーザ専用のプロトタイプセットを得ることもでき
る。これは、ここでは、個人用プロトタイプセットと呼
ばれる。開始プロトタイプセットは、典型的には、手書
き文字認識システムの専門家によって生成されるという
点で、システム１０のユーザには書く上での示唆或は制
約に従うと言った負担は課せられない。

【００２６】いずれのケースにおいても、トレーニング
セッションの際に文字マッチャ１８からの文字は物理的
或は論理的スイッチ２２を通じてプロトタイププロセッ
サ２４に送られるが、これは、例えば、インテル社の３
８６プロセッサであり得る。プロトタイププロセッサ２
４の出力は、一連の平均されたプロトタイプ文字であ
り、これらは、メモリ２０に供給され、その後、システ
ム１０のユーザによって実行される手書き文字認識セッ
ションにおいて使用される。

【００２７】本発明においては、プロトタイププロセッ
サ２４を動作するための方法が開示されるが、これによ
ってコーナスキップコスト関数を使用して認識精度を向
上するための文字プロトタイプが生成される。

【００２８】図４には、コーナスキップコスト関数の計
算のフローチャートが示される。ブロック５０におい
て、コスト関数SKIPCOST（ｊ）がプロトタイプの全ての
ポイントに対してゼロに初期設定され、ｊがＣ１に初期
設定される。ブロック５２において、ｊが１だけ増分さ
れる。ブロック５４において、ｊが（プロトタイプ長−
Ｃ１）を超えるか否かを決定するためのテストが行なわ
れる。テストの結果が肯定であるときは、計算は、ブロ
ック５６に示されるように終了する。超えないときは、
計算はブロック５８へと続き、ここで、ポイントｊにお
ける角度変化が閾値Ｃ２を超えるか否かのテストが行な
われる。超えないときは、計算はブロック５２に戻る。
超えるときは、計算はブロック６０に進み、ここで、角
度変化が前及び次の角度変化にＣ３の係数を掛けた値を
超えるか否かのテストが行なわれる。超える場合は、計
算は、ブロック５２に戻る。超える場合は、計算は、ブ
ロック６２に進み、ポイントｊの所のスキップコストSK
IPCOST（ｊ）がＣ４に角度変化を掛けた値に指定され
る。計算は、次に、ブロック５２に戻る。

【００２９】図６には、コーナスキップコスト関数を持
つ弾性マッチングの計算のフローチャートが示される。
これは、図５に示される弾性マッチングに対する計算領
域を使用する。この計算においては、プロトタイプの個
々のポイントに対してアレイの距離、つまり、Dist
（ｊ）が使用される。ブロック７０において、アレイの
Dist （ｊ）がプロトタイプ内の個々のポイントに対し
てゼロに初期設定され、ｉがゼロに初期設定される。ブ
ロック７２において、JTop及びJBotが計算領域（図５）
の境界から計算され、MinDist がDist(JTop ）に初期設
定され、Dist1 がDist(JTop-１）に初期設定され、Dist
2 がDist(JTop-2 ）に初期設定され、ｊがJTopに初期設
定される。ブロック７４において、MinDist がMinDist
、Dist1 及びDist2 SKIPCOST（ｊ−２）の最小として
計算される。ブロック７６において、ポイントからポイ
ントまでの距離ｄ（ｉ，ｊ）が指定される距離メトリッ
クを使用して計算され、MinDist に加えられ、Dist
（ｊ）が得られる。ブロック７８において、MinDist が
Dist1 にリセットされ、Dist1 がDist2 に等しくセット
され、Dist2 がDist(j-3) に等しくセットされる。ブロ
ック８０において、ｊがJBotに等しいか否か決定され
る。等しくないときは、ブロック８２において、ｊが減
分され、計算はブロック７４に戻る。等しい場合は、ブ
ロック８４において、ｉが未知の文字の長さに等しいか
否か決定するためのテストが遂行される。等しくないと
きは、ブロック８６においてｉが増分され、計算はブロ
ック７２に戻る。等しい場合は、ブロック８８におい
て、このプロトタイプに対する未知の文字のマッチング
距離がＤ（長さプロトタイプ）として決定され、計算は
終了する。

【００３０】このアルゴリズムの拡張は、反復、つま
り、同一のプロトタイプポイントが未知の文字内の一連
のポイントに対して比較されることを罰するためにもう
一つのコスト関数を加えることから成る。これは図６の
ブロック７４の式の左側で反復コストRepeatCost（ｊ）
と言う項目をMinDist に加えることによって達成され
る。但し、手書き文字の認識のためには、コーナスキッ
プコスト関数の方が反復コスト関数よりも精度を向上す
るためにより重要である。

【００３１】

【発明の効果】以上説明したように本発明の手書き文字
認識法においては、特に、手書文字のコーナ及び先端に
おける改良された弾性マッチングが得られる手書文字認
識システムが提供されて好ましい。

【図面の簡単な説明】

【図１】未知の文字“３”とプロトタイプ文字“３”と
の弾性マッチを示す図面である。

【図２】文字“ｋ”と“ｈ”との弾性マッチングを示す
図面である。

【図３】本発明に従って構成及び動作される手書き認識
システムの簡略ブロック図である。

【図４】プロトタイプ文字の個々のポイントに対するコ
ーナスキップコストの計算を詳細に示すフローチャート
である。

【図５】弾性マッチング計算領域を示す図面である。

【図６】コーナスキップコスト関数を含む弾性マッチン
グ手順を詳細に示すフローチャートである。

Claims

【特許請求の範囲】

【請求項１】手書き文字認識システムに使用されるスト
ローク内の鋭いコーナをテストするための方法におい
て、前記ストロークをポイント毎にサンプリングするステッ
プと、個々のポイントの所の角度変化を測定するステップと、任意のポイントにおける角度変化が所定の閾値より大き
いか否かを決定するステップと、前記角度変化が前記任意のポイントに隣接する少なくと
も二つのポイントの所の角度変化よりも所定の係数だけ
大きいか否かを決定するステップと、コーナスキップコスト関数を、角度変化が前記所定の角
度よりも大きく、前記角度変化が前記所定の係数より大
きな場合、定数に前記任意のポイントの所の決定された
角度変化を掛けた値に等しく計算し、そうでないとき
は、ゼロに計算するステップと、を含むことを特徴とする方法。
【請求項２】前記閾値が３０°から５５°の範囲内であ
ることを特徴とする請求項１記載の方法。
【請求項３】前記所定の係数が１．５から３．０の範囲
内であることを特徴とする請求項２記載の方法。
【請求項４】手書き文字認識システムに使用されるプロ
トタイプ文字を形成する個々のストローク内の鋭いコー
ナをテストするための方法において、前記個々のストロークをポイント毎にサンプリングする
ステップと、個々のポイントの所の角度変化を測定するステップと、任意のポイントにおける角度変化が所定の閾値より大き
いか否かを決定するステップと前記角度変化が前記任意
のポイントの少なくともいずれかの側に隣接する複数の
ポイントの所の角度変化よりも所定の係数だけ大きいか
否かを決定するステップと、（ａ）角度変化が前記所定の角度よりも大きく、かつ、
（ｂ）前記角度変化が前記所定の係数より大きい場合に
定数に、前記任意のポイントの所で決定された角度変化
を掛けた値であるコーナスキップコスト関数を計算する
ステップと、を含むことを特徴とする方法。
【請求項５】未知の文字の個々のストロークをポイント
毎にサンプリングするステップと、前記未知の文字と前記プロトタイプ文字とをポイント毎
にマッチングするステップと、前記コーナスキップコスト関数の計算に応答して前記プ
ロトタイプ文字上の前記任意のポイントと前記未知の文
字上の対応するポイントとの間のマッチ距離を増加させ
るステップと、が含まれることを特徴とする請求項４記載の方法。
【請求項６】（ａ）角度変化が前記所定の角度よりも大
きくない場合、或は、（ｂ）前記角度変化が前記所定の
係数より大きくない場合、前記コーナスキップコスト関
数をゼロにセットするステップを含むことを特徴とする
請求項５記載の方法。
【請求項７】前記閾値が３０°から５０°の範囲内であ
ることを特徴とする請求項６記載の方法。
【請求項８】前記所定の係数が１．５から３．０の範囲
内であることを特徴とする請求項７記載の方法。