JPH0366703B2 - - Google Patents

Description

【発明の詳細な説明】 (1) 発明の属する分野の説明 本発明は、誤筆順あるいは誤画数によつても文
字識別能力が低下しないオンライン手書き文字認
識方式に関するものである。

(2) 従来の技術の説明 従来のオンライン手書き文字認識方式において
は、CRの場合と異なり、入力パターンが画数
（ストローク数）情報を含んでいることを利用し
て、認識すべき入力パターンは、これと画数の等
しい標準パターンとの間でだけ照合を行つて認識
する手法を採つていた。この場合、画数は正しく
筆記せねばならないという制約があつた。しか
し、画数の多い漢字など、形状が複雑になるほ
ど、画数を誤ることは多くなり、画数を正しく守
るという制約条件は、筆記者にとつて大きな負担
となつていた。

これを解決する１つの方法としては、画数を誤
りやすい文字について、画数の異なる様々な筆記
のしかたをすべて標準パターンとして登録してお
くことが考えられる。しかし、１つ１つの文字に
ついて画数の異なる書き方をすべて列挙すること
は実際上不可能であり、仮にそれらの一部だけを
標準パターンとして登録したとしても、標準パタ
ーン数が膨大なものとなるため、認識に要する計
算処理量が急増する上、登録してない誤画数で筆
記された場合は必ず誤認識になるという欠点があ
つた。

もう１つの解決方法として、画数は正しく様々
な筆順の標準パターンを登録しておき、入力パタ
ーンが誤画数で筆記されることを想定し、入力パ
ターンおよび標準パターンとも一筆書きに変換し
認識を行うことが考えられたが、一筆書きパター
ンは手書き変形に敏感で誤認識を生じ易く、登録
されてない筆順には全く対処できないという欠点
があつた。

さらにもう１つの解決方法として、正しい筆
順・画数のもののみ標準パターンに登録してお
き、入力パターンが誤筆順、誤画数で筆記された
場合も、標準パターンとの間で画数の少ない方の
パターンのストロークを相手パターンのストロー
クにすべて対応させ画数の多い方のパターンの未
反応ストロークをそれぞれ筆順で先行する既対応
ストロークに結合し画数をそろえてから認識を行
うことが考えられた（特願昭57−46080）が、誤
画数で筆記した際に生じる特有の手書き変形のた
めに前段のストローク対応を誤ると後段での筆順
に従うストロークの結合も誤り、そのために誤認
識を生じるという欠点を持つていた。

(3) 発明の目的 本発明は、上述した従来の問題点を解決して、
標準パターンとしては正しい筆順・画数のものの
み登録しておくだけで誤筆順、誤画数の筆記を許
し、とくに誤画数での筆記に伴う手書き変形に対
処して文字認識能力を低下させることのないオン
ライン手書き文字認識方式を提供することを目的
とする。

(4) 発明の構成および作用の説明 以下に、本発明の詳細を実施例によつて説明す
る。

第１図は本発明の１実施例に使用する装置の機
能ブロツク図であつて、１は文字情報入力装置、
２は前処理装置、３はストローク特徴点抽出装
置、４は標準パターン格納装置、５はストローク
間距離算出装置、６はストローク対応づけ装置、
７は選択的ストローク結合装置、８はパターン間
距離計算装置、９は最小距離値検出装置であり、
以下各装置の動作について具体的に説明する。

文字情報入力装置１は、既存のタブレツトから
構成され、入力パターンの各ストロークの筆跡の
Ｘ、Ｙ座標を一定時間間隔で入力し、その筆点列
を前処理装置２に送出する。

前処理装置２は文字情報入力装置１から送出さ
れた筆点列に、公知の技術に基づき雑音除去や平
滑化や位置・大きさの正規化などを施し、その結
果得られる筆点列をストローク特徴点抽出装置３
に送出する。

ストローク特徴点抽出装置３は、前処理装置２
から送出された各ストロークの筆点列に対し、ス
トローク上で曲線に沿う長さをあらかじめ定めた
刻み距離値△で等間隔に刻んでその位置に最も近
い筆点を順次選出して、各ストロークを代表する
特徴点列を抽出する。

入力パターンをS〓と記し、S〓はＮ個のストロー
クS₁、…、S_i…、S_Nから成つており、各ストロー
クの特徴点はＸ、Ｙ座標を連ねてS_i＝（x_1i、y_1i、
…、x_oi、y_oi）と表わされる。ここでｎはS_iに含
まれる特徴点の個数で、ｉは１≦ｉ≦Ｎで筆順を
表わし、正しい筆順とは異なつていても構わな
い。入力パターンS〓より抽出したストローク特徴
点列は、ストローク間距離算出装置５と選択的ス
トローク結合装置７に送出される。

標準パターン格納装置４は、照合すべきすべて
の文字カテゴリーについて、正しい筆順・画数で
筆記されたおのおのの平均パターンから上述の刻
み距離値△を用いて各ストローク上で等間隔に抽
出したストローク特徴点のＸ、Ｙ座標値系列を格
納しており、正しい筆順・画数を持つ該ストロー
ク特徴点列は、標準パターンとしてストローク間
距離算出装置５と選択的ストローク結合装置７に
送出される。

ストローク間距離算出装置５はストローク特徴
点抽出装置３から送出された入力パターンS〓の特
徴点列と標準パターン格納装置４から送出された
標準パターンの特徴点列との間ですべてのストロ
ーク対についてストローク間距離を算出する。

標準パターンR〓と記し、R〓はＭ個のストローク
R₁、…、R_j、…R_Mから成つており、第ｊストロ
ークR_jは特徴点のＸ、Ｙ座標を連ねてR_j＝（x_1j、
y_1j、…、x_nj、y_nj）で表わすものとする。ここで
ｍはR_jに含まれる特徴点の個数で、ｊは１≦ｊ
≦Ｍで正しい筆順を表わす。入力パターンS〓の第
ｉストロークS_i（x_1i、y_1i、…、x_oi、y_oi）（１≦ｉ
≦Ｎ）と標準パターンR〓の第ｊストロークR_j＝
（x_1j、y_1j、…、x_nj、y_nj）との少ない方の特徴点
数に基づくストローク間距離d_ijは、例えば２乗距
離を用いると、ｍ≧ｎの場合には、 d_ij＝α_ij・min ０≦Ｒ≦ｍ−ｎ _N 〓ⁱ⁼¹ ｛（x_k+p,i−x_kj）²＋（y_k+p,i−y_kj）²｝(1) により算出される。ここでα_ijは特徴点数の違い
を評価する因子で、例えばα_ij＝ｍ／ｎを用いる。
ｍ＜ｎの場合のd_ijの算出式は、上記式(1)でｍとｎ
及びｘとx′とそれぞれ交換したものになる。な
お、式(1)においてmin操作を行わず、始点あるい
は終点を合わせた２乗距離を用いることもでき
る。式(1)によりすべてのストローク対についてd_ij
を算出し、総数Ｍ・Ｎ個のストローク間距離値を
ストローク対応づけ装置６に送出する。

ストローク対応づけ装置６は、ストローク間距
離算出装置５から送出されたＭ・Ｎ個のストロー
ク間距離値を用いて、ストローク数の少ない方の
パターンのすべてのストロークに対して相手パタ
ーンの中から同数のストロークを選出し、それぞ
れ対応づける。具体的にはストローク数Ｍ、Ｎの
大小に応じて、Ｍ≧Ｎのときは入力パターンの第
ｉストロークS_iの対応ストロークを標準パターン
の第j_iストロークとして、_M 〓^j=1 d_ijiを最小としかつ
j₁、j₂、…、j_Nに重複がないという条件を満たす
Ｎ個のストローク対を決定し、Ｍ＜Ｎのときは標
準パターンの第ｊストロークR_jの対応ストロー
クを入力パターンの第i_jストロークとして、_N 〓ⁱ⁼¹ d_ijj
を最小としかつi₁、i₂、…、i_Mに重複がないＭ個
のストローク対を決定する。ストローク対応の決
定結果は、選択的ストローク結合装置７へ送出さ
れる。

第２図に、５画で筆記された誤画数・誤筆順の
入力パターン「字」と正しく６画で筆記された標
準パターンの「字」とのストローク対応の例を示
す。丸印が対応を表わす。標準パターンの第５ス
トロークR₅が未対応である。図中、ストローク
上の黒丸は特徴点の位置を表わす。

選択的ストローク結合装置７は、ストローク特
徴点抽出装置３から送出された入力パターンのス
トローク特徴点および標準パターン格納装置４か
ら送出された標準パターンのストローク特徴点を
一時格納し、スローク対応づけ装置６より送出さ
れたストローク対応結果に基づき、ストローク数
の多いパターンの中で未対応として残つたストロ
ークについてそれぞれ筆順で前後する該パターン
の２本の既対応ストロークのいすれかとの結合の
うち相手パターン中の対応ストロークとの間で特
徴点列に基づく始点・終点を合せたストローク間
距離を計算し、該距離が小さくなる方の結合を選
択して実行する装置である。

以下、選択的ストローク結合装置７の具体的動
作について、Ｍ≧ＮとＭ＜Ｎの場合に分けて詳述
する。

Ｍ≧Ｎの場合、スローク対応づけ装置６により
標準パターンと入力パターンの間でＮ個のストロ
ーク対が決定されている。標準パターン内のそれ
らＮ本のストロークをRp₁、Rp₂、…、Rp_k、…、
Rp_Nと記し、添字は次式により筆順の若い順に付
す。

１≦p₁＜p₂＜…＜p_K＜…＜p_N≦Ｍ (2) また、Rp_k（１≦ｋ≦Ｎ）はそれぞれ入力パタ
ーン内のSq_k（１≦ｋ≦Ｎ）と対応づけられてい
るものとする。本装置は、標準パターン内のＭ−
Ｎ本の未対応ストロークを順に既対応ストローク
に選択的に結合していく。いま、標準パターン内
の着目する未対応ストロークをRtと記す。ｉ＜
ｔを満たす未対応ストロークR_iについては既に結
合相手が決定しているものとして、Rtの結合相
手の決定を次のようにして行う。

() ｔ＜p₁の場合 式(2)により、この場合はRtに筆順で先行す
る既対応ストロークが存在しない。従つて、無
条件でRp₁を結合相手とする。

() p_k＜ｔ＜p_k+1（１≦ｋ≦Ｎ−１）の場合 Rp_k自身およびRp_kを結合相手とする未対応
ストローク群を合わせた中で、最も筆順の若い
ストロークをRuと記す。一般にｕ≦p_kである。
ここで次に示す２種類の結合ストロークを生成
する。但し、〜は生起順にストロークを結合す
る操作を表わす。

Rt′＝Ru〜…〜Rp_k〜…〜Rt−１〜Rt Rt″＝Rt〜Rt＋１〜…〜Rp_k+1 第３図に、Rp_k、Sq_kの対応関係、および
Rt′とRt″の生成の概念図を示す。

第３図に示したように、Rt′は入力パターン
内のSq_kに対応すべきストロークである。一
方、Rt″はSq_k+1に対応すべきストロークであ
る。そこで、Rt′とSq_kおよびRt″とSq_k+1との間
でそれぞれストローク間距離を算出して、その
値の小さい方の結合のしかたを選択する。すな
わち、次式により、Rtの結合相手を決定する。

a′・d^*q_k，t′≦a″・d^*q_k+1，t″ →RtをRp_kに結合 a′・d^*q_k，t′＞a″・d^*q_k+1，t″ →RtをRp_k+1に結合 但し、a′、a″は特徴点数の違いを評価する因
子（≧１）である。また、ストローク間距離
d^*としては、公知の技術である、始点・終点
をそれぞれ対応づけた、DPマツチングによる
２乗距離を採用すればよい。その場合、Si＝
（x_1i、y_1i、…、x_oi、y_oi）とRj＝（x′_1j、y′_1j、
…、x_nj、y′_nj）の距離d^* _ijは次式で算出される。

d^* _ij＝min τ _o 〓^k=1 ｛（x_ki−x′〓_(k)j）²＋（y_ki−y′〓_(k)j）²｝(3) 但し、τはτ(1)＝１、τ(n)＝ｍを満たす単調
非減少の対応づけ関数である。

ここで、始点・終点を合わせたDPマツチン
グを用いるのは、結合により生成されたストロ
ークが入力パターン内の対応する１本のストロ
ークと全体で重なり合うべきであるとの要請に
基づく。

() p_N＜ｔの場合 式(2)により、この場合はRtに筆順で後行す
る既対応ストロークが存在しない。従つて、無
条件でRp_Nを結合相手とする。

以上、（）、（）、（）に分けた手順により、
標準パターンの未対応ストロークはすべて結合相
手を決定され、それら結合を実行してＮ画のパタ
ーンに変換する。

一方、Ｍ＜Ｎの場合、ストローク対応づけ装置
６により標準パターンと入力パターンの間でＭ個
のストローク対が決定されている。入力パターン
内のそれらＭ本のストロークをSq₁、…、Sq_k、
…、Sq_Mと記し、添字は次式により筆順の若い順
に付す。

１≦q₁＜q₂＜…＜q_k＜…＜q_M≦Ｎ (2)′ また、Sq_k（１≦ｋ≦Ｍ）はそれぞれ標準パタ
ーン内のRp_k（１≦ｋ≦Ｍ）と対応づけられてい
るものとする。本装置は、入力パターン内のＮ−
Ｍ本の未対応ストロークを順に既対応ストローク
に選択的に結合していく。具体的手順はＭ≧Ｎの
場合と同様であり、着目する未対応ストロークを
Stと記すと、（）ｔ＜q₁、（）q_k＜ｔ＜q_k+1、
（）q_M＜ｔ、の場合に分けて結合相手が決定さ
れる。

上記処理により、選択的ストローク結合装置７
は、入力パターンおよび標準パターンのストロー
ク数をＫ＝（min（Ｍ，Ｎ））にそろえ、筆順およ
び画数のそろつたＫ個のストローク対を生成す
る。それらストローク対を改めてS_k、R_k（１≦ｋ
≦Ｋ）と記す。

この結果はパターン間距離計算装置８に送出さ
れる。

第４図、第２図に示した「字」の例で未対応と
なつた標準パターンの第５ストロークR₅が、選
択的ストローク結合によりR₄と結合される処理
の過程を示す。図中、ストローク上の黒丸は特徴
点の位置を表わす。

パターン間距離計算装置８は、選択的ストロー
ク結合装置７から送出されたストローク数および
筆順のそろつた該入力パターンと該標準パターン
の特徴点列を用いて、対応するストローク毎にス
トローク間距離を計算し、それらの加算結果をパ
ターン間距離として求める装置であり、ストロー
ク間距離としては公知の技術である始点・終点を
合せ、少ない方の特徴点数に基づくDPマツチン
グ手法を適用し、例えば式(3)を用い、上記Ｋ個の
ストローク対S_k、R_k（１≦ｋ≦Ｋ）の各対につい
てストローク間距離d^* _kkを算出し、そして該パタ
ーン間距離を_K 〓^k=1 d^* _kkとして計算する。算出され
た該パターン間距離は、最小距離値検出装置９に
送出される。

上述した装置５乃至８までの操作を、標準パタ
ーン格納装置４内に格納されているすべての標準
パターンについて行う。この操作が完了した時点
で、最小距離値検出装置９は、蓄積されたすべて
のパターン間距離のうち最小のものを検出し、こ
れに該当する標準パターンの文字カテゴリーを識
別結果として、当該装置から出力する。

(5) 効果の説明 以上詳細に説明したように、本発明によれば、
これまで不可能とされてきた誤筆順、誤画数での
筆記を許容してオンライン手書き文字の認識機能
を格段に向上させることができる。とくに、標準
パターンとしては正しい筆順・画数のもののみ登
録しておくだけでよく、誤筆順・誤画数の入力パ
ターンと標準アターンとの間で、まず少ない方の
ストローク数分の筆順をそろえたストローク対を
決定し、次いでストローク数の多い方のパターン
中の未対応ストロークを該パターン間での重なり
が良くなるように既対応ストロークに選択的に結
合し誤画数で筆記した際に生じる特有の手書き変
形を吸収し、同筆順、同画数にそろえた結果とし
て高い認識精度を実現できることから、様々な筆
順・画数による筆記が頻繁に発生する不特定多数
の筆記者を相手とするオンライン手書き文字認識
の分野において適用される場合に利点が大きい。

【図面の簡単な説明】

第１図は本発明の一実施例に使用する装置の機
能ブロツク図、第２図は第１図の装置６の動作を
説明するための具体例による概念図、第３図およ
び第４図はそれぞれ第１図の装置７の動作を説明
するための概念図および具体例による説明図であ
る。 図中、１は文字情報入力装置、２は前処理装
置、３はストローク特徴点抽出装置、４は標準パ
ターン格納装置、５はストローク間距離算出装
置、６はスローク対応づけ装置、７は選択的スト
ローク結合装置、８はパターン間距離計算装置、
９は最小距離値検出装置を示す。

Claims (1)

【特許請求の範囲】
1. １ 標準パターンとして各文字カテゴリーの正し
   い画数・筆順で筆記された平均パターンのすべて
   のストロークについてあらかじめ定めた刻み距離
   値で等間隔に特徴点列を抽出して格納しておく段
   階と、認識すべき入力パターンのすべてのストロ
   ークについて前記刻み距離値を用い等間隔に特徴
   点列を抽出し一時格納する段階と、該入力パター
   ンのすべてのストロークと一般にはストローク数
   の異なる標準パターンのすべてのストロークとの
   間でそれぞれ少ない方の特徴点数に基づきストロ
   ーク間距離を計算しておいてから該入力パターン
   と該標準パターンでストローク数の少ない方のパ
   ターンのすべてのストロークに対して相手パター
   ンの中からストローク間距離和を最小としかつ重
   複がない同数のストロークを選出しそれぞれ対応
   づける段階と、ストローク数の多い方のパターン
   の中で前記対応づけでは未対応として残つたスト
   ロークについてそれぞれ筆順で前後する該パター
   ンの２本の既対応ストロークいずれかとの結合を
   想定し該結合のうちストローク数の少ない方のパ
   ターン中の対応ストロークとの間で特徴点列に基
   づく始点・終点を合せたストローク間距離を計算
   し該距離が小さくなる方の結合を選択し実行する
   段階と、ストローク数が等しくなつた該入力パタ
   ーンと該標準パターンとの間で対応したストロー
   ク対毎に特徴点列に基づく始点・終点を合せたス
   トローク間距離を計算してそれらの加算結果を蓄
   積する段階と、前記照合すべき標準パターンのす
   べてについて上述のすべての段階を反復実行し前
   記加算結果を順次蓄積する段階と、該段階の終了
   後前記加算結果のうち最小のものを検出して該最
   小加算結果に該当する標準パターンの文字カテゴ
   リーを認識結果として出力する段階とを含むこと
   を特徴とするオンライン手書き文字認識方式。