JPS62208190A - 画数別ソ−トによる手書き文字認識方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 手書き文字認識において、画数の異なった辞書パターン
が認識候補に選択された場合に画数情報を用いて候補順
位を決定する方式である。

０産業上の利用分野〕 本発明は、画数の異なった辞書パターンが認識候補に選
択された場合に、辞書パターンと入力パターンの画数を
用いて認識候補の順位を決定する方式に関する。

〔従来の技術〕

従来の文字認識方式としては、（イ）入カバクーンの画
数情報を用いない方式と、（ロ）入力パターンと同じ画
数を持つ辞書パターンの中から認識候補を選択する方式
とがある。

〔発明が解決しようとする問題点〕

前者の方式では、画数情報を用いないため、入力パター
ンも辞書パターンも一筆書きで表現され、入力パターン
と辞書パターンは字形のみで比較される。このため、例
えば「牛」も「午」も「令」と表現されるので、誤読が
増える欠点がある。後者の方式では、入力パターンと同
じ画数を持つ辞書パターンのみが認識候補となる。この
ため、例えば「は」と言う文字が「１３．Ｊと入力され
た場合、三直の辞書には「１１」と言うパターンが登録
されていない限り、この文字は正しく認識されない。

この方式では「１よ」のように画数変動のあるパターン
を正しく認識するためには、認識辞書が大きくなると言
う欠点がある。

本、発明は、この点に鑑みて創作されたものであって、
画数情報を用いない方式で認識候補を選択した場合に、
候補の順位を画数によって決定する方式を提供すること
を目的としている。

〔問題点を解決するための手段〕

要約すると、本発明の画数別ソートによる手書き文字認
識方式は、画数情報を用いない方式で認識候補を選択し
た場合に、認識候補と入力パターンの画数差によって候
補をソート（並び変え）することにより、「４」と「＋
」のような文字の識別を行なえるようにしたものである
。

第１図は本発明のオンライン手書き文字認識装置の原理
図である。第１図において、■はタブレット、２は候補
選択回路、３は認識辞書、４は画数別ソート回路をそれ
ぞれ示している。タブレット１上に文字が書かれると、
文字の座標点系列及びペンの上げ／下げ情報がが候補選
択回路２に入力される。候補選択回路２については後述
する。

認識辞書３には、候補文字の特徴点列が格納されている
。画数別ソート回路４は、候補選択回路２から出力され
る候補文字群に含まれる各候補文字の画数と入力文字の
画数の差を求め、求めた差に従って候補文字群をソート
するものである。

タブレフｌ−１上に手書きで入力された文字パターンは
、候補選択回路２において認識辞＠３内の辞書パターン
と比較される。候補選択回路２で選択された候補は画数
別ソート回路４でソートされ、認識順位が決定される。

第２図は第１図の画数別ソート回路４内におけるソート
実行例を示す図である。入力パターン「奉」に対して、
候補選択回路２は従来の画数情仰を用いない方式で「千
」、「４」、「＋」を候補として選択したとする。画数
別ソート回路４においては、入力パターンの画数と候補
パターンの画数の差が計算され、この値によって従来の
ソート方式で認識候補の画数別ソートが行われる。ソー
トの結果、画数差が０の「４」と「＋」の順位が上がり
、画数差が１の「千」の順位が下がる。このため、入力
パターン「＋」の１位の認識候補は「“４」になる。

第３図は候補選択回路２の１例の概要を示す図である。

なお、候補選択回路２については、本出願人が先に出願
した特願昭６０−４８７４６号に詳細に説明されている
。第３図において、５は特徴点抽出回路、６は入力パタ
ーン格納回路、７は標準パターン格納回路、８は特徴点
対応付は回路、９は対応結果格納回路、１０は信号線、
１１はパターン間類似度計算回路、１２はソーティング
回路をそれぞれ示している。第３図において、タブレフ
）１から入力された手書き文字データは特徴点抽出回路
５によってストロークの両端点と屈曲点からなる特徴点
列に変換され、入力パターン格納回路６に送られる。認
識辞書３には、同様な特徴点列で表現された標準パター
ン・データが多数個記憶され、その中からマツチングを
行う標準パターン・データが順々に取り出される。この
状態において、特徴点の対応付けを行う特徴点対応付は
回路８が起動される。特徴点対応付は回路８は、距乱計
算部、スタック及び次対応特徴点決定回路を備えており
、距離計算を行って特徴点対を順々に決定して行く。そ
して、その対応付けの結果が対応結果格納回路９に送ら
れる。信号ｖＡ１０は、特徴点対応付は回路８からパタ
ーン間類似度計算回路１１へ送られるもので、対応付け
が最後まで終了したか、途中で中止したかを示す制御信
号である。信号＊１０が対応付けが最後まで終了したこ
とを示す場合のみ、パターン間類似計算回路１１が起動
されて、対応付けを基にパターン間の距離計算が行われ
る。距離計算の結果はソーティング回路１２に送られ、
認識辞書３から送られて来た文字コードが距離の小さい
順番に並び変えられ、認識結果として出力される。上記
処理の間、特徴点対応付は回路８において対応付けが行
われた候補点対については、特徴点対応付は回路８のス
タック内に保持され、必要に応じてバンク・トラックが
行われる。

第４図は特徴点列を説明する図である。第４図Ａは入力
パターンを示し、第４図Ｂは入力パターンを表現する特
徴点列を示す。文字の特徴点は、両端点と複数の屈曲点
とを持つストローク特徴点列の集合で表現される。なお
、黒丸は端点を、白丸は屈曲点を示している。対応付け
る２つの特徴点列を Ａ”　（ａ　Ｉｔ　ａ２．−”、　　ａ、　ＩＢ＝　（
ｂｌ、ｂ２．・・・、ｂ８） とするとき、第１の特徴点ａｌ＋　　ｂｊを強制的に対
応付けてから終点ａＮｒ　　ｂＨに至るまで、筆順通り
に先に対応付けた特徴点対を利用して、順番に次に対応
する特徴点対を決定して行くようにする。

文字全体の対応付けを厳密且つ安定に行うために以下の
第（１１項ないし第（３）項に示す特徴を持っている。

（１）対応付けを厳密に行うために複数の特徴量による
距離計算を基に対応を決定すること。

前対応特徴点を（ａｉ、ｂＪ）とする特徴点（ａＫ、ｂ
Ｌ）に対する対応付は距離りを、第５図を参照すると明
瞭になるように、次のように定義する。

Ｄ＝　（ｄ、−ｗ、＋ｄ２−ｗ２　＋ｄ：ｌ　−ｗ、）
／（ｗ、＋ｗ２　＋ｗ３） 一−−→　　−一→ 但し、ｄ、はａｉ　ａｋとｂＪｂ、のなす角度であり、
ｄ２は ｄ　　２　＝　　　いｉ−ン−８１−ｌｂｉ　　　ｂｔ
＋ｌ＋　　（Ｌ＋　　　−ｌａ；　　　ａｈａ）＋　（
Ｌ２−１ｂＪ　ｂ、ｌ） である。ここで に−１−一一− Ｌ＋＝Σ　ｌａ　、　　ａ　Ｍｅ　ｌ　１Ｌ２＝！“１
Ｇτ＝１ である。

また、ｄ３はａｋ　ａｋ＋Ｉ　とす、ｂｌ−１とのなす
角度であり、重みＷに関しては、 Ｗｇ　　＝　　γ Ｗ３　”β・ｍｉｎ　（ｌａｗ　ａ、、、ｌ、　ｌｂｔ
　　ｂ、、、ｌ）である。但し、β、γは成る定数であ
る。

ここで、ａｋ＋　　ｂＬのうち一方もしくは両方が特徴
点列Ａ、Ｂの最終点である場合には、距離ｄ、と加重値
Ｗ３とは不定になるが、その場合には次のように定義す
る。

（ａｌａｋ、ｂ、両方が最終点の場合 ｄ、　＝Ｑ　’、　Ｗ３　＝δ（定数）（ｂｌａ、、、
ｂ、の一方のみが最終点の場合ｄ：＋　＝１８０　’、
　ｗ、　＝δ（定数）上記距離計算において、後述する
第（２）項で言う対応付は範囲の中で対応付ける距離が
ある闇値以下のものがあれば、それを対応候補点対とし
、なければバンク・トラックを行って先にスタックして
置いた他の候補に戻って対応付けを行うようにする。こ
のために対応候補点対が複数個存在する場合には、距離
最小のものを当面の次対応特徴点対とし、その他のもの
は前対応点対と共にスタックに退避して置くようにする
。

（２）計算量を低減し、不自然な対応を許さないように
すること。

第６図のように、黒丸で示す前対応点（ａｔ。

ｂ、）に対し、次対応点（ａう、ｂ、）は図示斜線に示
す次のような条件を満たす範囲から選ばれる。即ち、 ｋ≧ｉ＋１で且つｌａｊ＋１ であって、且つ に＝ｉ＋ｌまたはｆｆ１＝ｊ＋１ の範囲から選ばれる。

その際に、計算量を低減すると共に、不自然な対応付け
が行われないように対応範囲を次のように制限する。

（ａ）　　長さによる制限 ｂＬをｂｊ。１に固定して、ａｉからａ、に至るの定数
倍を越えた場合には、ａ５．、以降との対応付けは行わ
れない。

同様に、ａ、をａ　ｉ、ｌに固定してす、からｂＬに至
るベクトルの長さの総和Σ　ｌｂ、ｂ、。、１が１ａ４
ａｌ。１１の長さが定数倍を越えた場合には、ｂ、。１
以降との対応付けは行われない。

（ｂｌ　　省略不能点による制限 ａ、（ｋ≧ｉ＋１）が省略不能点ならばａ　ｋ、を以降
との対応付けは行われない。同様に、ｂｔ　　（！≧ｊ
＋１）が省略不能点ならばＩ）　、＋　１以降との対応
付けは行われない。但し、特徴点ａｋは次の条件を満た
すときに省略不能点であると定義する。

■　ａ、がストロークの始点又は終点であり、−一一一
一一一つ　　　−−−−−→ ■　ａｋ−１ａ、とａｌＨａｋ＋＋のなす角度が成る闇
値を越えており　（鋭角）、 ■　ａ、が始点ならばａｋ−１ａｋの長さが、ａ。

が終点ならばａｋａ＋＋＋＋の長さが成る闇値を越えて
いる（十分長い）。

また、ａｋが標準パターンを構成する特徴点である場合
には、それが省略不能であるか否かは予め人為的に設定
する場合もある。

（Ｃ）　　特徴点の種類による制限 ■　ストロークの始点と終点とは対応付けない。

■　ｂ、をｂｌ、１に固定してｂ　ｊ＋＋　とａｋが共
にストロークの始点ならば、ａ　ｉ＋＋ｚ以降とは対応
付けない。同様に、ａｋをａ、。、に固定してａ８．。

とｂｌが共にストスークの始点ならばす４，２以降との
対応付けは行わない。これらの制限は、実際のストロー
クをストロークとストロークとの間を結ぶ仮想的なスト
ローク（オフ・ストローク）に対応付けるような不自然
な対応を抑制するためである。

（３）局所的な誤りを全体に波及させないため、適時ハ
ック・トラックを行う。

対応付は範囲内において対応付は距離が闇値内の特徴点
対が一つも存在しない場合には、スタックに退避されて
いる特徴点対を用いてバック・トラックが行われる。ス
タックが空である場合には対応付けは中止される。この
場合、バック・トランクによる計算量が指数関数的に増
大しないように次の工夫を行っている。

（ａ）　　一般に複数個存在する対応候補点対をスタッ
クに退避する順番を、対応付は距離が大きいものが先に
なるようにする。こうすることによって、対応付は距離
の小さい（即ち可能性が高い）対応付けが先に評価され
ることになり、対応付けが正常に終了する場合には、よ
り少ない計算量で最終的な対応付は結果が得られる。

（ｂｌ　　先に対応付けを行い、失敗した経路を記憶し
、再び同じ経路を通らないようにする。具体的には、前
対応点（ａｉ、ｂｊ）に対し、次対応点（ａｋ＋ｂｔ）
を記憶するＭＸＮの配列バフ！、（ＰＡＴＨ）を用いて
次の■ないし■のような処理を行う。

■　配列ＰＡＴＨを（０，Ｏ）に初期化する。

■　前対応点（ａｉ　、ｂｊ）に対し、ＰＡＴＨ（ｉ、
ｊ）の値が（−０，０）でなければ、これは先に対応付
けを行った結果失敗したＰ　Ａ　Ｔ　Ｈであるので、直
ちにバンク・トラックを行う。

■　前対応点（ａ　ｔ　、ｂ；　）に対し、次対応点（
ａｋ、ｂ、）が定まればＰＡＴＨ（ｔ、ｊ）　に（ｋ、
１）を代入する。

■　バンク・ｌ・ラックが行われた場合には、スタック
には次対応候補点対（ａ、ＩＩ’＋　　ｂｔ’）の外に
その時の前対応点対（”＝’＋　　ｂｊ’）も退避され
ていルノテ、ＰＡＴＨ（ｔ’、　ｊ’　）　＝　（ｋ’
、　（！’　）　トして配列ＰＡＴＨを書き替える。次
に、特徴点対（ａｋ’、ｂご）を前対応点対として次対
応点対を決定して行く。

（Ｃ１標準パターンを構成する特徴点列に部首の切れ自
情報を付加し、その部首の切れ目まで正常に対応付けが
進めば、その時点で強制的にスタックをクリアする。

このようにすることにより、対応付けが十分光に進んだ
時の非所望なバック・トラックを抑制することが出来る
。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、画数
情報を用いないで認識候補が選択された場合に、画数情
報を用いて候補の順位を決定するので、より適切な認識
が行なえると言う効果が得られる。

【図面の簡単な説明】

第１図は本発明のオンライン手書き文字認識装置の原理
図、第２図は第１図の画数別ソート回路４内におけるソ
ート実行例を示す図、第３図は候補選択回路２の１例の
概要を示す図、第４図は入力パターンと特徴点とを示す
図、第５図は対応付は距離を説明する図、第６図は対応
付は範囲を説明する図である。 ■・・・タブレット、２・・・候補選択回路、３・・・
認識辞書、４・・・画数別ソート回路、５・・・特徴点
抽出回路、６・・・人カバターン格納回路、７・・・標
準パターン格納回路、８・・・特徴点対心付は回路、９
・・・対応結果格納回路、１０・・・信号線、１１・・
・パターン間類似度計算回路、１２・・・ソーティング
回路。

Claims (1)

【特許請求の範囲】
1. 手書き入力された文字パターンと予め認識辞書（３）に
   登録された辞書パターンとを比較して認識を行う手書き
   文字認識方式において、画数の異なった辞書パターンが
   認識候補に選択された場合に入力パターンの画数と候補
   となった辞書パターンの画数の差によって候補をソート
   して認識候補の順位を決定する手段（４）を持つことを
   特徴とした画数別ソートによる手書き文字認識方式。