JPS62216092A - オンライン手書文字認識装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔目　次〕 概要 産業上の利用分野 従来の技術 発明が解決しようとする問題点 問題点を解決するための手段 作用 実施例 標準パターンおよび入力パターンの形式ノード対の対応
づけ方法　（第４図） 実施例の構成　　　　　　（′ｆｉＪ５図）発明の効果 ［概　要］ オンライン手書文字認識において、特徴点をノードとす
るＤＡＣ（有向非巡回グラフ）構造で表現された標準パ
ターンと、ノードの対応範囲を決定する手段と、ノード
間の距離を計算して対応の可否を判定する手段と、対応
可能なノード対の候補を保持するスタックとを備え、逐
次的に筆順を選択しながら、画数によらずに、入力パタ
ーンと標準パターンとの特徴点を厳密に対応づけるよう
にして認識を行うものであり、これにより画数や筆順の
変動に対しても誤読の少ない認識が可能となった。

［産業上の利用分野コ 本発明はオンライン手書文字認識方式に係わり、特に人
カバターンを構成する特徴点列と標準パターンを構成す
る特徴点列を対応づける方式に関する。

オンライン手書文字認識は、人間とコンピュータ間のイ
ンタフェースにおけるデータ、特に日本語を入力する手
段として、キーボードによる仮名漢字変換方式などに比
較して、人間にとって自然で、素人でも教育なしにすぐ
に使える方式として注目されている。

素人向きの日本語入力方式としては、画数や筆順といっ
た運筆上の要素が変化しても認識可能で、且つ誤読の少
ない認識方式が要望されている。

［従来の技術］ オンライン手書文字認識では、入力パターンと標準パタ
ーンを構成するそれぞれの特徴点列の対応を適切に決定
することができれば、単純な距離計算のアルゴリズムで
容易に高い認識率を得ることができる。

入力パターンと標準パターンが同じ筆順と画数で書かれ
たものならば、両パターンの各ストローク（文字の一画
に相当）を固定数の特徴点で近似し、筆順や異なる画数
の異なるパターンは別パターンとして辞書に登録してお
くことにより、ある程度の筆順・画数変動を吸収するが
、辞書に登録されていない筆順・画数で書かれた文字を
認識することはできない。

このような単純な対応づけを行う方式では、Ｎ通りの筆
順とＭ通りの画数があればＭＸＮ通りの標準パターンが
必要になり、認識時間も必要なメモリ容量もパターン数
に比例して大きくなるため、実用的に十分な認識性能を
得ることは難しかった。

少ない標準パターンで十分な認識性能を得るためには、
画数、筆順の少なくとも一方の変動をアルゴリズムで吸
収する必要がある。

画数変動を吸収する方式としては、パターンを一筆書き
にした後ＤＰマツチングにより特徴点または特徴点を結
ぶベクトルを伸縮させて対応づける方式が知られている
。

筆順変動を吸収する方式としては、入力パターンと標準
パターンの総てのストロークの間でストローク間距離を
計算し、ストローク間距離の総和を最小とするようにス
トロークの対応を決定して認識を行う方式が古くから知
られている。

これらの方式のうち、本発明に比較的近いものとして、
スタック上でＤＰマツチングを行うことにより画数変動
と筆順変動を吸収しようとする「スタックＤＰマツチン
グによる認識方式」　（信学技報Ｖｏ１．８３　Ｎｏ、
１３９　ＰＲＬ８３−２９参照）について説明する。

この方式では、入力された文字パターンは特徴点間を結
ぶベクトルの時系列に変換され、文字の変形や複数の筆
順を時系列中の分岐として表現した標準パターンとの間
で、スタックを用いたＤＰマツチングを行い、文字を認
識する。

時系列の構成要素となるベクトルは、角度と、長さと、
ペンの状態（オン／オフ）の３要素で次のように表現さ
れる。

（ａ＋　１＋　ｐ）　　ａ：角度、ｌ：長さ、ｐ：ペン
の状態ＤＰマツチングはベクトル間の距離を角度の差と
して定義し、次の漸化式を解くことにより実行される。

ここで、ｄ　（ＩＩＪ）は入力パターンのｉ番目のベク
トルと標準パターンのｊ番目のベクトルの距離、１ｉ、
　ｎｊはそれぞれのベクトルの長さである。

スタックは標準パターンの時系列の分岐を処理するため
に用いられ、基本的には各分岐のなかで最小のｇ（ｉ、
ｊ）を与えるものが選択される。

第６図はスタックＤＰマツチングによるオンライン手書
文字認識方式の構成を示すブロック図である。

図中、１６は入力パターンをベクトルの時系列に変換す
る前処理部、１７は標準パターンを格納する辞書、１８
はスタックＤＰマツチングを実行するスタックＤＰマツ
チング部、１９は途中結果を保持すオンライン手書文字
認識方式には、特徴点或いはストロークのような基本要
素に成る距離を定義し、その距離の総和が最小となるよ
うに要素間の対応を決定するため、局所的な対応は必ず
しも厳密ではない。

また対応に対し画一的な制限しか設けることができない
ため、本来はあり得ないような不自然な対応を許してし
まうことがある。

このため従来の方式では、局所的に文字が崩れて入力さ
れた場合にも、ある程度の認識が可能である反面、認識
された文字と異なる文字の標準パターンとの距離も小さ
くなり、誤読、即ち別の文字に読み間違うことが多いと
いう欠点があった。

このような問題点を解決するため、我々は先に、■スト
ロークの端点と屈曲点を含む特徴点列で表現された入力
パターンと標準パターンに対し、■先に対応づいた特徴
点対をもとに次に対応するか否かをチェックされる特徴
点列に対し距離を計算する手段と、■特徴点対を保持す
るスタックと、バックトラックの機能を有する次対応特
徴点決定部を備えることを特徴とする「オンライン手書
文字特徴点の対応づけ処理方式」を提案し、本出願人よ
り出願している。

この方式では、特徴点列を局所的な形状をもとに、厳密
に、且つ余裕を持って対応づけることができるので、続
は字で画数が予期しない変動をした場合でも、誤読の少
ない認識を行うことができたが、筆順の異なるパターン
を認識するためには、予め複数の別筆順の標準パターン
を必要とするという問題点があった。

本発明は、上記のような従来の問題点を解消した新規な
オンライン手書文字認識方式を提供しようとするもので
ある。

［問題点を解決するための手段］ 第１図は本発明のオンライン手書文字認識方式の原理ブ
ロック図を示す。

図中、１はＤＡＣ（Ｗ問罪巡回グラフ）と呼ばれる構造
で表現された入力パターンを格納する人カバターン格納
部であり、２はＤＡＣ構造で表現された標準パターンを
格納する標準パターン格納部である。

ＤＡＣ構造は、ストロークの端点および屈曲点を含む特
徴点をノードとし、筆順により前後する特徴点列を結ん
だ形で表現するものである。

筆順によっである特徴点の次にくる特徴点が複数存在す
る場合には、標準パターンは、その特徴点に対応するノ
ードが複数のノードと結ばれた構造として格納される。

このように、パターンをＤＡＣ構造で表現することによ
り、複数の筆順をひとつの標準パターンにより表現する
ことができる。

３は対応したノード対を格納するレジスタであり、４は
先に対応したノード対をもとにして次に対応するノード
対を選ぶ範囲を決定する対応範囲決定部であり、５は選
ばれた範囲の各ノード対に対し距離を計算する対応づけ
距離計算部であり、６は計算された距離をもとに次に対
応するノード対を決定する対応ノード対決定部である。

また、７は次に対応するノード対に選ばれなかった他の
ノード対を格納するノード対格納スタックであり、８は
終了判定を行う終了判定部である。

［作用］ 第２図は、標準パターンを表現するデータ構造を説明す
る図であって、（ａ）木構造および（ｂ）　ＤＡＣ構造
により複数の筆順を表現した例である。

木構造はＤＡＣ構造の特殊な場合で、あるノードに複数
の下位のノード（子供）がつながることはあるが、その
ノードにつながる上位のノード（親）は一つに制限され
るが、ＤＡＣでは上位のノードも複数であることが許さ
れる。

各ノードは文字を構成する特徴点に対応し、二次元の位
置座標値と特徴点の種類（始点、終点）が格納される。

入力パターンを表現する特徴点列も、各特徴点をノード
として筆順で前後する特徴点を結び、ＤＡＣ構造の特殊
の場合として表現する。

あるノードＡに接続する下位のノードの集合をＳ　（Ａ
）で表せば、２つのノードＡ、Ｂ間に関係（〉）が次の
ように再帰的に定義できる。

（１１Ｂｕｓ　（Ａ）→Ａ＞Ｂ （２）ＡεＣ１且つ　Ｂ〔５（Ｃ）→Ａ＞ＢＤＡＧ構造
では、ノードＡ、Ｂ間に関係Ａ＞Ｂ。

ＢＡＡが共に成り立つことはない。

即ち、ノードＡから子供のノードを順番に辿っていって
も再びＡに戻ることはない。

このような構造で表現される標準パターンは、予め第１
図に示す標準パターン格納部２にセットさせておく。同
様な構造で表現される入力パターンが入力パターン格納
部１にセントされると、両方のパターンのノード間の対
応づけが行われる。

以下に、その対応づけの手順を、第１図を参照して説明
する。

（１）書き始めの第１のノード同士を対応させる。

（２）現在対応しているノード対をレジスタ３にセント
する。現在対応しているノード対を（Ｎｏ、ＭＯ）とす
る。　（ＮＯは入力パターン中のノード、ＭＯは標準パ
ターン中のノード）。

（３１（ＮＯ，ＭＯ）がセットされると、対応範囲決定
部４は次に対応するノード対を選ぶ範囲を決定し、この
範囲に含まれるノード対（Ｎ、Ｍ）の集合を次の対応づ
け距離計算部５へ送る。ただし、ＮＯ＞Ｎ、ＭＯ＞Ｍで
ある。

（４）対応づけ距離計算部５では、各ノード対（Ｎ。

Ｍ）に対し、（Ｎ、　Ｍ）と（ＮＯ，ＭＯ）によって計
算される対応づけ距離を計算し、その距離がある闇値以
内であるノード対の集合を決定し、その集合とその対応
づけ距離の値を対応ノード対決定部６に送る。

（５）対応ノード対決定部６では、送られたノード対の
集合の中から対応づけ距離が最小のノード対を次に対応
づけるノード対として終了判定部８に送り、残りのノー
ド対をスタック７に退避させる。対応づけ距離計算部５
より送られたノード対の集合が空集合の場合は先の操作
で退避させたノード対をスタック７から取り出し、それ
を終了判定部８に送る。スタック７が空の場合には、そ
の時点で対応づけ処理を中止する。

（６）終了判定部８では、送られたノード対（Ｎ、Ｍ）
に対し、ノードＮの入力パターン中での位置、およびノ
ードＭの標準パターン中の位置を調べ、対応づけを進め
るかどうかを決定する。対応づけを進める場合にはノー
ド対をレジスタ３へ送り、制御を（２）へ戻す。

対応範囲決定部４は、不自然な対応を許さないよう、対
応範囲を限定するために使用されるものである。

この対応づけ方式は、先に対応づいた結果をもとに逐次
的に対応づけを進めるため、ある段階で誤った対応づけ
を行うと、それ以降の対応づけが困難になってくるが、
スタック７はそのような場合に対応づけを元に戻すため
に使用されるものである。

［実施例］ 以下第３図〜第５図に示す実施例により、本発明をさら
に具体的に説明する。

〔標準パターンおよび入力パターンの形式〕第３図は、
本発明の実施例によるＤＡＣ構造の標準パターンの形式
を示す図である。

図の（ａ）は標準パターンの内部表現を示す図であり、
（ｂ）はこのパターンの構成要素である各ノードの内部
表現を示す図であり、（ｃ）はこのノードの構成要素の
うち特徴点情報の内部表現を示す図である。

第３図（ａ）において、標準パターンの第一のノードに
は「ルート」と呼ばれる仮想的なノードが割り当てられ
る。

一般に筆順によって文字の書出し位置が異なるパターン
をＤＡＣで表現すると、自分より上位のノードを持たな
いノードが複数個存在することになるが、このようなノ
ードの親として「ルート」を導入することにより構造が
単純になる。ＤＡＧ中のすべてのノードは「ルート」か
ら順番に辿って行くことによりアクセスが可能である。

入力パターンも基本的に同じ形式で表現されるが、標準
パターンと比べて次の点が異なる。

■各ノードに接続するノードの個数がＯ（最終点）また
は１　（それ以外）である。

■文字コードの部分が未定義である。

■「ルート」ノードが省略される。

第３図（ｃ）に示す特徴点情報のうち、省略不能点の情
報とは、そのノード（特徴点）が続は書きなどをして字
形が崩れても消滅しないようなノードか否かを示す情報
のことである。この省略不能点の情報が“１″であるノ
ードを省略不能ノードと呼ぶ。

省略不能の情報は対応づけの範囲を小さく制限するため
に使用される。第１図の対応範囲決定部４では、あるノ
ードが省略不能である場合にはそのノードより下位のノ
ードは対応範囲に加えない。

標準パターンでは、この情報は文字の性質を考慮して作
為的に決定する。

一方、入力パターンでは次の各条件を充たす点として、
自動的に決定する。

■ストロークの端点（始点、終点）である。

■特徴点とその前後の特徴点を結んでできる角度が６０
度未満である。

■特徴点がストロークの始点ならば前の特徴点、終点な
らば後ろの特徴点とのユークリッド距離が入力文字の外
接長方形の長辺の５％よりも大きい。

〔ノード対の対応づけ方法〕

以下、ステップ順に従って、本実施例によるノードの対
応づけの処理方法を説明する。ここで、ノードｎの子供
のノードの集合をＳ　（ｎ）で表すこととする。

ステップ１　（第一ノード対を対応させる）標準パター
ンの文字書き始めの点（ノード）の集合Ｓ　（ＲＯＯＴ
）　　の各要素　ｎｉ　と入力パターンの第一のノード
ｍ１との間で、対応する特徴点間のユークリッド距離を
計算し、距離最小の対を第一対応ノード対とする。他の
ノード対はスタック（第１図の７）の中に退避させる。

ステップ２（現対応ノード対のセット）現在対応づいて
いるノード対を（ｎＯ，ｍｏ）とする。

ステップ３　（対応範囲の決定） ノード対（ｎｏ、ｍｏ）の次に対応するノード対は、次
のような集合Ａから選ばれる。

Ａ＝　（Ｓ（ｎＯ）ＸＴ（ｍｏ））　　Ｕ　（Ｔ（ｎＯ
）ＸＳ（ｍＯ））式中の記号Ｕは和集合を示し、×は面
相を示す。

Ｔ　（ｎ）はノードｎの次に対応するノードの候補の集
合を表すもので、次のような手順で決定される。

■　　Ｗ−Ｓ＜口） ■　Ｔ４−３（ｎ） ■　Ｗが空集合ならば■へ ■　Ｔ４−ＴｕＮ（Ｗ） ■　Ｗ←Ｎ（−）として■へ ■　Ｔ　（ｎ）−Ｔ ここで集合ｗ−ｗ　（ｔｙｉ＋ｗ２＋、、、＋ｗｉ＋）
より定まる集合Ｎ　（Ｗ）は、第４図のフローチャート
により計算される。

Ｎ　（Ｗ）はＷの要素から、自分自身が省略不能でない
ノードを選び、選ばれたノードの子供ノードの集合の和
集合を表すものである。

このようにして計算された集合Ｔ　（ｎ）は、省略不能
ノードに至るまでノードｎの下位のノードを集めたもの
である。

ステップ４（対応づけ距離の計算） 対応範囲Ａが決定されると、Ａに含まれる各ノ−ド対（
ｎ、　ｍ）に対して対応づけ距離りが次のように計算さ
れる。

Ｄ＝ａｌ−ＤＩ＋ａ２・Ｄ２ ここで、 Ｄ１＝Ｊ　Ｘｎ　−Ｘｍ　　＋　　Ｙｎ　−Ｙｍａｌ、
ａ２　は定数 ただし、 ノードｎ、ｍの位置座標を（ｘｎ、Ｙｎ）。

（Ｙｍ、Ｙｍ） ノードｎｏ、ｍｏの位置座標を（ＸｎＯ，ＹｎＯ）。

（ＹｍＯ，Ｙｎ＋０） （ｘ、　　ｙ）　”　（Ｘｎ−ＸｎＯ，Ｙｎ−ＹｎＯ）
（Ｘ、　Ｙ）　ｉｉｉ　（Ｘｍ−ＸｍＯ，Ｙｍ−ＹｍＯ
）とする。

対応づけ距離計算部では、対応範囲への部分集合として
対応づけ距離が闇値Ｄｔｈ以下のノード対の集合Ｂを決
定する。Ｂを候補集合と呼ぶ。Ｂは空集合のこともある
。

ステップ５　（対応ノードの決定） （１１候補集合Ｂが空集合でない場合 集合Ｂに含まれる各ノード対に対し対応づけ距離が最小
であるノードを次に対応するノード対とする。集合Ｂに
含まれる他のノード対は対応づけ距離の大きい順番にス
タックに退避させる。

（２）候補集合Ｂが空集合の場合 ■スタックが空でない場合 スタックからノード対を取り出し、次に対応するノード
対とする。これは、対応づけを途中からやり直すことで
、一般にバックトラックと呼ばれる。

■スタックが空の場合 対応づけを中止する。（対応づけ不可能）ステップ６（
終了判定） ステップ５で決定された次に対応するノード対（ｎ、ｍ
）に対し、対応づけを終了するか継続するかを、次のよ
うに判定する。

■ノード対ｎ、ｍが共に子供のノードを持つ、即ち最終
ノードでないならば、対応づけを継続する。

■ノード対ｎ、ｍが共に最終ノードならば、対応づけを
終了する。

■ノードｎ、ｍの何れかが最終ノードである場合には、
そうでない方のノードをｐとして、ｐが下位に省略不能
ノードを持たない場合には対応づけを終了する。

■それ以外の場合には対応づけをｍ続する。この場合、
ノードｎ、ｍの何れか一方は最終ノードであり、次に（
ｎ、　ｍ）で定まる対応範囲Ａは空集合となり、従って
候補集合Ｂも空集合になるので、バックトラックが行わ
れることになる。

〔実施例の構成〕

第５図は、本発明の実施例の全体構成を示すブロック図
である。

図中、９は認識を行う文字を入力するためのタブレット
である。

１０は入力パターンを特徴点をノードとするＤＡＣ構造
に変換する前処理ブロック図である。

１１は標準パターン取り出し部であり、標準パターン記
憶部１２に記憶されているＤＡＣ構造で表現された標準
パターンを、ひとつづつ取り出して１３へ送る。

１３は、本発明の基本となる構成要素を備えたノード対
応づけ部であり、■対応範囲決定部、■滞納づけ距離計
算部、■対応ノード決定部、および■対応候補ノード対
を保持するスタックの各機能をマイクロプロセッサで実
現したものである。

１４は対応結果をもとにパターン間の距離Ｄｐａｔを計
算するパターン間距離計算部であり、次のように計算す
る。

■対応づけが終了した場合 Ｄｐａｔ　＝　（対応したノード間のユークリッド距離
の総和）／対応づいたノード数 ■対応づけが中止された場合 Ｄｐａｔ　＝閃 １５はソーティング回路であり、標準パターンに格納さ
れている文字コード（第３図（ａ）参照）をパターン間
距離Ｄｐａｔの小さい順番に並べ換え、距離最小の文字
コードを認識結果として出力する。

［発明の効果コ 以上説明のように本発明によれば、前対応特徴点対によ
り対応範囲を動的に制限しながら、スタックを用いて対
応づけを進めるので、安定且つ厳密な対応づけを行うこ
とができ誤読の少ない認識を実現でき、また標準パター
ンをＤＡＧ構造で記述することにより、複数の筆順を一
つのパターンで表現できるため、少ない記憶量で高速な
認識を実現することが可能で、その実用上の効果は極め
て大である。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は標準パターンを表現するデータ構造を説明する
図、 第３図は本発明の実施例によるＤＡＣ構造の標準パター
ンの形式を示す図、 第４図は本発明の実施例におけるＮ　（Ｗ）を計算する
フローチャート、 第５図は本発明の実施例のブロック図、第６図はＤＰマ
ツチングによるオンライン手書文字認識のブロック図で
ある。 図面において、 ｌは入力パターン格納部、 ２は標準パターン格納部、 ３はレジスタ、 ４は対応範囲決定部、 ５は対応づけ距離計算部、 ６は対応ノード対決定部、 ７はノード対格納スタック、 ８は終了判定部、　　９はタブレット、１０は前処理部
、　　　１１は標準パターン取出し部、１２は標準パタ
ーン記憶部、 １３はノード対応づけ部、 １４はパターン間距離計算部、 １５はソーティング回路、 １６は前処理部、　　　　　　　１７は辞書、１８はス
タックＤＰマツチング部、 １９はスタック、　　　　　　　　２０は詳細識別部、
をそれぞれ示す。 本発明の〈（理ブロック図 第　１　図 、卯−一■−−−−−−←■・−・・・−←■）−■・
・−・−）−←鉦″ パ舎−■−・・・・←■−・−）−七 （ａ）　Ｔｒｅｅ　（木構造）による表現、ｐ−→■−
・・−■−−■ ひ−■−・・・・・ト←■ｊ、″←■ ゛゛ト■・・・・・・←■ （ｂ）　ＤＡＣ（Ｄｉｒｅｃｔｅｄ　Ａｃｙｃｌｉｃ　
Ｇｒａｐｈ：有向非巡回グラフ）による表現標準パター
ンを表現するデータ構造を説明する同第　　２　　図 （ａ）標準パターンの内部表現　　　　　　　　　（ｂ
）各ノードの内部表現（ｃ）特徴点情報の内部表現（３
ビツト）本発明の実施例によるＤＡＣ構造の標準パター
ンの形式を示す図Ｎ（−）を計算するフローチャート 第４図 本発明の実施例のブロック図 第５図

Claims (1)

1. 【特許請求の範囲】 ストロークの端点と屈曲点を含む特徴点をノードとし、
   筆順で前後するノードを結んだ有向非巡回グラフ構造で
   文字を表現した辞書パターンを格納する標準パターン格
   納手段（２）と、 同じく有向非巡回グラフ構造で入力文字を表現したパタ
   ーンを格納する入力パターン格納手段（１）と、 先に対応づいた入力パターンのノードと標準パターンの
   ノードとのノード対をもとに、次に対応するノード対の
   範囲を決定する対応範囲決定手段（４）と、 ノード対間の距離を計算する対応づけ距離計算手段（５
   ）と、 ノード対を保持するノード対格納スタック（７）とを備
   え、 前対応ノード対により対応範囲を動的に制限しつつ、ス
   タックを用いて逐次的に筆順を選択して、入力パターン
   と標準パターンのノードの対応づけを進めるよう構成し
   たことを特徴とするオンライン手書文字認識方式。