JPH0527913B2 - - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明はオンラインで入力された文字の筆跡よ
り文字を認識するオンライン文字入力装置に関す
るものである。

（従来技術とその問題点） 従来、ストローク（タブレツトのペンがオンし
てからオフするまでの筆跡）数の変動や許し、か
つ筆順（ストロークの書かれる順序）に依存せず
に、オンラインで入力された文字を認識する方式
は存在した。たとえば、「電子通信学会論文誌」
Vol.J66−ＤNo.５（1983年５月）593〜600ページに
「選択的ストローク結合による画数・筆順に依存
しないオンライン文字認識」と題して発表された
論文には以下のような方式が示されている。

この方式では、入力された文字の筆跡（入力パ
ターンと呼ぶ）と、認識装置内にあらかじめ保持
されている標準パターンとの間でストロークの対
応付けを行う。まず、入力パターンと標準パター
ンのうちストローク数のより少ない方のパターン
（パターンＡと呼ぶ）の全てのストロークを、一
方のパターン（パターンＢと呼ぶ）中の最も距離
の小さいストロークに各々対応付ける。つづいて
パターンＢの対応付けられなかつたストロークを
筆順の相前後する２本の既に対応付けられている
ストロークとそれぞれ結合させ結合ストロークと
する。そしてこれらの結合ストロークとパターン
Ａの対応するストロークとの間の距離を求め、こ
の距離が小さくなる方の結合ストロークを選択す
る。この選択された結合ストロークとパターンＡ
のストロークを対応付ける。このようにしてパタ
ーンＡとパターンＢのストロークを全て対応付け
対応するストローク間の距離の合計をパターン間
距離とする。このパターン間距離が最小となる標
準パターンのカテゴリを認識結果とする。

この方式では、ストローク数の変動に対しては
筆順の相前後するストロークの結合により対処し
ている。しかし実際はストロークが連続する場合
は、単にストロークが結合されるだけでなくスト
ロークの形状がかわる場合も多い。たとえば第７
図は「口」という文字の標準的なパターンの例で
あり、第８図は「口」という文字のストローク数
が変動した場合のパターンの例である。第８図中
のストローク８２は、第７図中のストローク７２
とストローク７３が連続したものであるが、スト
ロークの形状はこれら２つのストロークを単に結
合したものとは異なる。このため本質的に異なる
形状パターン同士を比較することになり、誤認識
が生じやすいという欠点があつた。

さらに、ストロークの結合は筆順の相前後する
ストロークとしか行われないため、誤つた筆順で
ストロークを連続して書かれた場合、誤認識が生
じ易いという欠点もあつた。

（発明の目的） 本発明の目的は、ストローク数の変動に伴うス
トロークの変形、誤つた筆順でストロークが連続
されたストロークの変形、１つのストローク内の
ストロークの形状の変形などのストロークの変形
に対し、それぞれの変形ストロークを標準パター
ン中に組込み、標準パターンのストロークと入力
パターンのストロークを過不足なく対応付られる
ようにすることにより、高い認識性能を持つた筆
順に依存しないオンライン文字入力装置を実現す
ることにある。

（発明の構成） 本発明によるオンライン文字入力装置は、文字
を書く際の筆跡を検出し入力パターとして読み込
む筆跡検出部と、認識される文字の標準ストロー
クのパターンとストロークの結合を含む変形スト
ロークのパターンを、標準ストロークに対しては
ストローク番号、変形ストロークに対しては対応
する標準ストロークのストローク番号（ストロー
クの結合を含む場合は複数のストローク番号）と
共に標準パターンとして保持する標準パターンメ
モリと、前記入力パターンのストロークと前記標
準パターンのストロークを前記ストローク番号の
重複や余りが生じないように対応付けることによ
り求めたストローク間距離の累積値をもとに文字
を認識する認識部とにより構成される。

（発明の原理） ここで、本発明の原理について説明する。本発
明によるオンライン文字入力装置は、標準的な文
字のストロークである標準ストロークのパターン
の他に、変形ストロークのパターンを標準パター
ンとして持つている。変形ストロークは、ストロ
ーク数の変動に伴うストロークの変形、誤つた筆
順でストロークが連続されたストロークの変形、
１つのストローク内のストロークの形状の変形な
どにより変形したストロークである。

この標準パターンと入力パターンのストローク
を過不足なく対応付けた時のストローク間距離の
累積値として得られるパターン間距離をもとに文
字を認識する。以下本発明による認識の原理を、
例をもとに説明する。

第２図は「可」という文字のパターンの例であ
る。この例では文字は標準ストロークにより構成
されている。しかし図中、ストローク２２，２
３，２４で構成されている「口」というパターン
は、例えば第３図に示すような３通りの変形があ
りうる。図中ストローク３１はストローク２３，
２４が連続したものであり、ストローク３２及び
３３はストローク２２，２３，２４が連続したも
のである。本発明において、標準パターンはスト
ローク２１〜２５の標準ストロークと、ストロー
ク３１〜３３の変形ストロークのパターンより成
り立つものとする。

第４図は「可」という文字の入力パターンの例
であり、この文字パターンはストローク４１，４
２，４３から成り立つている。第５図は、第４図
の入力パターンと、第２図及び第３図に示した標
準パターンのストローク間距離の例を示す表であ
る。横方向に入力パターン、縦方向に標準パター
ンのストロークを並べ、入力パターン、標準パタ
ーンとして示されている数字は第２図〜第４図中
のストロークを示す。隣にそのストロークの形状
もあわせて示してある。ストローク２１〜２５の
標準ストロークに対して１〜５のストローク番号
が付けられており、ストローク３１〜３３の変形
ストロークに対しては対応する標準ストロークの
ストローク番号が付けられている。１つの変形ス
トロークに対応する標準ストロークが複数個存在
する場合は、その変形ストロークには３，４のよ
うに複数のストローク番号が付けられている。

ストローク間距離としては、例えば昭和60年１
月９日付出願特許願（29）（以下引用文献(1)と称
す）に述べられているような定義を用いる。すな
わちストロークを構成する筆点の座標値間のユー
クリツド距離の和をストローク間距離とする。こ
の他にも、引用文献(1)中に述べられているさまざ
まなストローク間距離の定義を用いることができ
る。

変形ストロークの例としては、ここではストロ
ーク数の変動に伴うストロークの変形（ストロー
ク３１，３２）、誤つた筆順でストロークが連続
されたストロークの変形（ストローク３３）が示
されている。１つのストローク内のストロークの
形状の変形を含む変形ストロークは、対応する標
準ストロークのストローク番号を付ける。

次に、第５図に示されているストローク間距離
をもとに、過不足なく入力パターンと標準パター
ンのストロークを対応付けるという条件で、対応
するストローク間距離の累積値が最小になるスト
ロークの対応付けを求める。このストロークの対
応付けを効率よく行う方法として、最良優先探索
法（人工知能、岩波講座、情報科学−22（1982
年）、35〜38ページ）を用いることができる。こ
の方法によれば、入力パターンのストロークに対
して、ストローク間距離の累積値が最小となる標
準パターンのストロークの対応付けを優先して最
適なストロークの対応付けを探索していく。

このとき、ストロークが過不足無く対応付けら
れたか否かの判断はストローク番号をもとに行
う。この例のように標準ストロークが５個の場合
は、５ビツトの対応メモリを用意する。探索を始
める前は対応メモリの全てのビツトは０にしてお
く。入力パターンのストロークを標準パターンの
ストロークに対応させる毎に、対応メモリのスト
ローク番号に対するビツトを１にする。ストロー
ク３２のように複数のストローク番号を持つスト
ロークは、対応する複数のビツトを１にする。入
力パターンのストロークは、対応メモリのビツト
がすでに１になつているストローク番号を含む標
準パターンのストロークとは対応付けないとす
る。入力パターンのストロークが全ていずれかの
標準パターンのストロークと対応付けられ、その
ときのストローク間距離の累積値が最小で、かつ
対応メモリのすべてのビツトが１のとき探索は終
了する。このときのストローク間距離の累積値が
パターン間距離となる。

第６図は、第５図に示されているストローク間
距離をもとに最適なストロークの対応付けを最良
優先探索法により求めた場合の探索木の例であ
る。節点を表す丸の中に書かれた数字はストロー
ク間距離の累積値である。このストローク間距離
の累積値が最小である節点から先に、探索木の枝
を伸ばし新たな節点を作成する。節点の左上には
その節点において対応付けられたストロークが示
されている。（ｉ，ｊ）は標準パターンのストロ
ークｉと入力パターンのストロークｊが対応付け
られたことを示す。節点の右下に書かれた５桁の
数字は、その節点における対応メモリの内容を示
す。左端のビツトがストローク番号１に対応す
る。たとえば10110はストローク番号１，３，４
のストロークが既に対応付けられたことを示す。

第６図中、最も右下の節点（３３，４３）では
ストローク間距離の累積値は８と探索すべき全節
点中で最小であり、対応メモリの全てのビツトが
１となつているので探索は終了し、このときのパ
ターン間距離は８となる。このパターン間距離を
全ての標準パターンに対して求め、最小のパター
ン間距離を与える標準パターンの文字カテゴリを
認識結果とする。この最良優先探索は、この例に
示すような標準パターン毎の探索のほかに、全て
の標準パターンに対して並行して行うこともでき
る。

このように本発明において、ストローク数の変
動に伴うストロークの変形、誤つた筆順でストロ
ークが連続されたストロークの変形、１つのスト
ローク内のストロークの形状の変形などのストロ
ークの変形に対し、それぞれの変形ストロークを
対応する標準ストロークのストローク番号と共に
標準パターン中に組込んでいる。そして、このス
トローク番号の重複や余りが生じないように標準
パターンのストロークと入力パターンのストロー
クを対応付けることにより、これらのストローク
は過不足なく対応付けられる。このときのストロ
ーク間距離の累積値をもとに文字を認識すること
により、高い認識性能を持つた筆順に存在しない
オンライン文字入力装置が得られる。ストローク
の対応付けはストロークの書かれた順序に依存し
ないので、本オンライン文字入力装置は筆順に依
存せずに文字を認識できる。

（実施例） 以下本発明の一実施例について図面を参照して
詳細に説明する。第１図は本発明の一実施例を示
す構成図である。

タブレツト１より入力された文字のパターン
は、入力パターンメモリ２に保持される。標準パ
ターンメモリ３には認識される文字の標準パター
ンが保持されている。標準パターンには標準スト
ロークのパターンの他に、変形ストロークのパタ
ーンも必要に応じて含まれている。制御信号ｊに
より入力パターンメモリ２からは入力パターンの
ｊ番目のストローク（１≦ｊ≦Ｊ Ｊ：入力パタ
ーンのストローク数）のパターンＳ(j)が読みださ
れ、制御信号ｋ，ｉにより標準パターンメモリ３
からは標準パターン番号ｋ（１≦ｋ≦Ｋ ただし
Ｋは標準パターン数）の標準パターンのｉ番目の
ストローク（１≦ｉ≦Ｉ(k) Ｉ(k)：標準パターン
番号ｋの標準パターンのストローク数。変形スト
ロークも含む）のパターンＭ（ｋ，ｉ）および、
ストロークマークＬ（ｋ，ｉ）が読みだされる。
ストロークマークＬ（ｋ，ｉ）は標準ストローク
数に等しいビツト数を持つデータで、前述したス
トローク番号に対するビツトが１、他のビツトは
０となつている。１つの変形ストロークに対する
標準ストロークが複数個存在する場合は、対応す
る複数のビツトが１となつている。

ストローク間距離計算部４では、入力パターン
Ｓ(j)と標準パターンＭ（ｋ，ｉ）の間のストロー
ク間距離ｄ（ｋ，ｉ，ｊ）が計算される。このス
トローク間距離ｄ（ｋ，ｉ，ｊ）は引用文献(1)に
述べられているようなユークリツド距離を用いる
とする。

節点リストメモリ５には、探索木の節点のデー
タNdがストローク間距離の累積値ｇ（ｋ，ｐ）の
小さい順にリスト形式で保持されている。ストロ
ーク間距離の累積値ｇ（ｋ，ｐ）は、 ｇ（ｋ，ｐ）＝_p 〓^j=1 ｄ（ｋ，Ｔ（ｋ，ｊ），ｊ） (1) である。ここで、ｐは探索の深さ（１≦ｐ≦Ｊ）、
Ｔ（ｋ，ｊ）は入力パターンのｊ番目のストロー
クに対応付けられるＫ番目の標準パターンのスト
ロークを示す。

節点のデータNdにはストローク間距離の累積
値ｇ（ｋ，ｐ）の他に、標準パターン番号Ｋ、探
索の深さｐ及び対応メモリＣ（ｋ，ｐ）が含まれ
る。初期状態において、節点リストメモリ５には
ストローク間距離の累積値ｇ（ｋ，ｐ）の値が十
分大きい節点のデータNdが保持されている。

つぎに、ｐ＝１における節点が節点作成部６に
より作成される。節点作成部６から制御信号Ｋ，
ｉ，ｊがｊ＝１，１≦ｋ≦Ｋ，１≦ｉ≦Ｉ(k)なる
値をとり順次出力される。これらの制御信号によ
り、入力パターンメモリ２からはパターンＳ(j)、
標準パターンメモリ３からはパターンＭ（ｋ，ｉ）
が出力れ、ストローク間距離計算部４によりスト
ローク間距離ｄ（ｋ，ｉ，ｊ）が求められる。同
時に標準パターンメモリ３からは、ストロークマ
ークＬ（ｋ，ｉ）も出力される。

節点作成部６で新しい節点のデータNdnewが
作成される。ここで作成される新しい節点のデー
タNdnewは、 探索の深さ：ｐ＝１ 標準パターン番号：ｋ（１≦ｋ≦Ｋ） 累積値：ｇ（ｋ，ｐ）＝ｄ（ｋ，ｉ，ｊ） 対応メモリ：Ｃ（ｋ，ｐ）＝Ｌ（ｋ，ｉ） なるデータより成り立つている。

リスト作成部７では、新しい節点のデータ
Ndnewを節点リストメモリ５の節点リストに付
け加える処理が行われる。すなわち、新しい節点
のデータNdnew中のストローク間距離の累積値
ｇ（ｋ，ｐ）を節点リストの先頭から節点リスト
中の節点データNdのストローク間距離の累積値
ｇ（k′，p′）と比較していき、 ｇ（ｋ，ｐ）＜ｇ（k′，p′） を満たす節点データNdの前に新しい節点データ
Ndnewを付加する。

続いて、ｐ＞１における節点が作成される。節
点作成部６は、まず節点リストメモリ５の節点リ
ストの先頭にある（ストローク間距離の累積値ｇ
（k′，p′）の最も小さい）節点のデータNdを読み
だす。この節点のデータNdをもとに、制御信号
ｋ，ｉを標準パターンメモリ２に出力する。ここ
で、ｋは節点データNd中の標準パターン番号
k′の値、ｉは１≦ｉ≦Ｉ（k′）なるｉの値を順次
出力する。

標準パターンメモリ３からストロークマークＬ
（ｋ，ｉ）が出力されると、節点作成部６では対
応メモリＣ（k′，p′）の内容とＬ（ｋ，ｉ）andC
（k′，p′）なる論理積演算が行われる。この結果
が０以外であつたならストロークが重複すること
になるので、なにも処理を行わず次のｉを出力す
る。結果が０の時は、新しい節点Ndnewが作成
される。

新しい節点Ndnewを作成する場合、まず制御
信号ｊが節点作成部６から入力パターンメモリ２
へ出力される。制御信号ｊの値は節点データNd
中の探索の深さp′より、ｊ＝p′＋１とする。この
制御信号ｊにより入力パターンメモリ２からはパ
ターンＳ(j)が出力され、既に節点作成部６から出
力されている制御信号ｋ，ｉにより標準パターン
メモリ３からはパターンＭ（ｋ，ｉ）が出力され、
ストローク間距離計算部４によりストローク間距
離ｄ（ｋ，ｉ，ｊ）が求められる。

続いて、これらの値をもとに新しい節点のデー
タNdnewが求められる。すなわち、 探索の深さ：ｐ＝p′＋１ 標準パターン番号：ｋ＝k′ 累積値：ｇ（ｋ，ｐ） ＝ｇ（k′，p′）＋ｄ（ｋ，ｉ，ｊ） 対応メモリ：Ｃ（ｋ，ｐ） ＝Ｃ（k′，p′）orL（ｋ，ｉ） である。ただし、orは論理和演算を表す。この新
しい節点のデータNdnewは、リスト作成部７に
出力される。リスト作成部７では、すでに述べた
ような処理により新しい節点のデータNdnewを
節点リストメモリ５中の節点リストに付け加え
る。

節点リストの先頭の節点データNdの探索の深
さp′がＪと等しく、かつ対応メモリＣ（k′，p′）
の全てのビツトが１の時、探索は終了する。この
節点データNd中の標準パターン番号ｋが認識結
果として出力される。

（発明の効果） 本発明によれば、ストローク数の変動に伴うス
トロークの変形、誤つた筆順でストロークが連続
されたストロークの変形、１つのストローク内の
ストロークの形状の変形などのストロークの変形
に対し、それぞれの変形ストロークを標準パター
ン中に組込み、標準パターンのストロークと入力
パターンのストロークを過不足なく対応付けられ
るため、変形した文字に対しても高い認識性能を
持つた筆順に依存しないオンライン文字入力装置
が得られる。

【図面の簡単な説明】

第１図は本発明の一実施例を示す構成図、第２
図〜第６図は本発明の原理を説明するための図、
第７図、第８図は従来技術の問題点を説明するた
めの図である。 図において、１……タブレツト、２……入力パ
ターンメモリ、３……標準パターンメモリ、４…
…ストローク間距離計算部、５……節点リストメ
モリ、６……節点生成部、７……リスト作成部、
をそれぞれ示す。

Claims (1)

【特許請求の範囲】
1. １ 文字を書く際の筆跡を検出し入力パターンと
   して読み込む筆跡検出部と、認識される文字の標
   準ストロークのパターンとストロークの結合を含
   む変形ストロークのパターンと、標準ストローク
   に対してはストローク番号、変形ストロークに対
   しては対応する１又は複数の標準ストロークのス
   トローク番号を共に標準パターンとして保持する
   標準パターンメモリと、前記入力パターンのスト
   ロークと前記標準パターンのストロークを前記ス
   トローク番号の重複や余りが生じないように対応
   付けることにより求めたストローク間距離の累積
   値をもとに文字を認識する認識部とを有して成る
   オンライン文字入力装置。