JPH01293491A - サブパターン作成方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、オンライン文字認識等における、標準パター
ンの記憶量削減や認識率向上を目的としたサブパターン
作成方式に関する。

（従来の技術） オンライン文字認識は、タブレット等からオンラインで
入力された筆跡データにより文字を認識するものであり
、現在商品化されている装置のほとんどは、パターンマ
ツチング法を原則としている。パターンマツチング法と
は、あらかじめ筆記された文字データを標準パターンと
して保持しておき、入力された文字パターンとのマツチ
ングを行い最も類似した標準パターンのカテゴリを認識
結果とする方法である。この原則による認識においては
、良質の標準パターンを作成することが必要となるが、
その手法の１つとして複数の文字の共通パターンをサブ
パターンとして共有するサブパターン化が知られている
。サブパターンを用いたオンライン文字認識については
、「スタックＤＰマツチングによるオンライン手書き文
字認識」電子通信学会技術報告ＰＲＬ８３−２９　　（
１９８３年９月）に述べられている。サブパターン化は
、共有化によって計算量を低減すると共に、手書きパタ
ーンの揺らぎによる誤認識を減少させることを目的とし
ている６手書きパターンの揺らぎによる誤認識とは、例
えば、入力された「儀」の「義」部分のパターンが、標
準パターンの「儀」における「義」パターンよりも「議
」におけるそれに類似している場合に、認識結果が「議
」となり誤認識になる現象を言う、上記のサブパターン
化の目的を考えると、サブパターンとしては、画数が多
く、なるべく多くの文字によって共有されるパターンを
求めることが必要である。

サブパターンを求める方法としては、辺、つくり、冠な
どの部首をもとに、共有化できると考えられるサブパタ
ーン候補を経験的に求めておき、それらのサブパターン
候補を含む文字が、標準パターン内に複数個存在するか
どうかを調べて、存在する場合にサブパターンとして登
録する方法がある。しかし、この方法では、求められる
サブパターン候補数に限りがある。特に、部首以外のサ
ブパターン候補をもらさず求めることは不可能であり、
有効なサブパターン候補を取りこぼす場合があった。従
って、計算量低減効果には限界があった。また、認識率
向上には、誤認識の原因となっていた「義」のような、
共有される文字数が少なくても画数が多いパターンが有
効と考えられるが、そのようなサブパターン候補を見つ
けることは困難であった。

この問題を解決する方法として、各文字パターンをサブ
パターン候補に分割し、得られたサブパターン候補のク
ラスタリングを行うことによりサブパターンを求める方
法が特願昭６３−６０９０５号に述べられている。この
方法では、まず、基本となる標準パターンの各文字パタ
ーンに対して１個ないし数個の分割点を与えて文字を複
数のパターンに分割し、分割されたパターンすべてをサ
ブパターン候補とする６分割点は、部４などのサブパタ
ーン候補を作る、などの基準を設けて与える。

分割されたパターンをすべてサブパターン候補とするた
め、部首以外のパターンも総てサブパターン候補となり
、サブパターン候補の取りこぼしがなくなる。特に、経
験的に得ることの器しいサブパターン候補を得ることが
できる。

基本となる標準パターンの全文字を対象にして分割を行
った後、求められた全サブパターン候補に対して、互い
に類似したパターンの集合（クラスタ）を求めるクラス
タリングを行う、クラスタリング法には、パターン間距
離などの類似性の尺度を計算して類似したパターンのク
ラスタを求める方法や目視によって類似したパターンを
選択してクラスタを求める方法がある。類似性の尺度に
よるクラスタリングには、階層的クラスタリング法、単
純クラスタリング法、Ｋ−ｍｅａｎｓ法などが知られて
おり、それらの方法については長尾真著、昭和５８年３
月コロナ社発行「パターン情報処理」の第１１３頁〜第
１２０頁に記載されている。

求められた各クラスタは、類似したパターンの集合であ
り、その中からサブパターンを決定する。

クラスタ内に同形のサブパターン候補が複数個存在する
場合は、そのサブパターン候補が複数の文字に共有化さ
れておりサブパターンとして有効と考えられる。そのた
め、そのサブパターン候補をサブパターンとして登録す
る。

（発明が解決しようとする課題） 従来方式では、分割された全サブパターン候補を対象と
してクラスタリングを行うが、サブパターン候補数は認
識装置の扱う文字数の増加に伴って増加する。さらに、
クラスタリングの演算量は、クラスタリングの対象とな
るパターン数の２乗に比例して増加するから、認識対象
文字数の増加はクラスタリング演ｘｉの膨大な増加につ
ながる。

これにより、認識対象文字が多い文字認識装置では、標
準パターン作成に多大な工数がかかっていた。

本発明の目的は、有効なサブパターン候補をもれなく求
めることができ、計算量低減効果を高め、かつ、認識率
を向上させることができるサブパターンを効率よく、少
ない演算量で求めることができる作成方式を提供するこ
とである。

（課題を解決するための手段） 本願における第１の発明によるサブパターン作成方式は
、各文字パターンに対して与えられた分割点に従って各
パターンをサブパターン候補に分割し、分割されたサブ
パターン候補に対して画数による大分類を行い、得られ
た同画数のサブパターン候補のクラスタリングを行うこ
とによりサブパターンを求めることを特徴とする。

本願における第２の発明によるサブパターン作成方式は
、各文字パターンに対して与えられた分割点に従って各
パターンをサブパターン候補に分割し、分割されたサブ
パターン候補に対して、サブパターン候補が文字に占め
る位置による大分類を行い、得られた同位置を占めるサ
ブパターン候補のクラスタリングを行うことによりサブ
パターンを求めることを特徴とする。

本願における第３の発明によるサブパターン作成方式は
、各文字パターンに対して与えられた分割点に従って各
パターンをサブパターン候補に分割し、分割されたサブ
パターン候補に対して、画数およびサブパターン候補が
文字に占める位置による大分類を行い、得らた同画数で
同位置を占めるサブパターン候補のクラスタリングを行
うことによりサブパターンを求め４ことを特徴とする。

（作用） クラスタリングの演ＬＪｉは、上述のようにクラスタリ
ングの対象となるパターン数によって増大する。従って
、クラスタリングの演算量を低減するには、あらかじめ
、別の方法でサブパターン候補を大ざっばに大分類して
おき、大分類により得られたパターン集合内でクラスタ
リングを行えば良い、しかしながら、大分類に誤りがあ
ると、最終的に得られる類似パターンの集合にも誤りを
含むことになるから、大分類の基準には、確実性の高い
ものを用いる必要がある。

本願における第１の発明によるサブパターン作成方式は
、大分類の基準として、画数を用いるものである。基本
となる標準パターンの文字を分割して求めたサブパター
ン候補に対して、画数による大分類を行って同画数の文
字の集合を求め、同画数の文字気合内で互いに類似した
パターンの集合（クラスタ）を求めるクラスタリングを
行う。

サブパターン候補の画数を例えば１画〜１５画の範囲と
すると、１５個の同画数のパターン集合が得られること
になり、１回のクラスタリングの対象となるサブパター
ン数は、平均して従来の１／１５となりクラスタリング
の演算量は低減される。

本願における第２の発明では、サブパターン候補が文字
において占める位置を大分類の基準とする。位置とは、
辺の場合は文字の左側半分、つくりは右側半分、冠は上
側半分、などとあらかじめ経験的に定めたものである０
位置は、分割の際に位置情報として各サブパターン候補
毎に与えても良いし、また、サブパターン候補のデータ
から計算によって求めても良い。この基準による大分類
の結果、辺などの文字の左側半分を占めるパターン集合
、つくりなどの右側半分を占めるパターン集合、など位
置別のパターン集合が得られる。クラスタリングは、位
置別の集合単位で行うため、対象となるサブパターン候
補数、クラスタリングの演算１ともに従来に比べて低減
される。

本願における第３の発明では、大分類の基準として、第
１の発明における画数と第２の発明における位置の両方
を用いる。すなわち、画数で分類した後に、各画数のパ
ターン集合内で位置による分類を行い、画数と位置が共
に同一であるパターン集合を求める１画数による分類と
位置による分類の順は、逆にしても良い。その後、求め
られたパターン集合内でそれぞれクラスタリングを行う
ことにより、類似パターンの集合を求めサブパターンを
求める。画数と位置の両者による分類により、クラスタ
リングを行う対象のサブパターン候補数を第１の発明、
第２の発明における候補数よりも更に減らすことができ
る。

（実施例） 以下に、本発明の実施例について図面を参照しながら詳
細に説明する。第１図は、本願における第１の発明によ
るサブパターン作成方式を実施したサブパターン作成部
のブロック図である。

基本標準パターン格納部１には、認識対象の全文字パタ
ーンがあらかじめ格納されているとする。オンライン文
字認識において、文字データはｘｙ座標や方向角などの
特徴量の時系列ベクトルとして表現されている。ここで
は、文字番号をｎ（ｎ＝１．・・・、Ｎ、Ｎ：認識対象
の文字数）、文字ｎのストローク番号を５ｎ（ｓｎ＝１
．・・・。

Ｓｎ）と表すことにする。第２図は、例として、文字「
清」のデータをグラフィック表示したものである。各ス
トロークに付いている番号は、ストローク番号であり、
書かれたストロークの順番を表している。

サブパターン候補作成部２では、基本標準パターン格納
部１の文字を一字ずつ読み込み、キーボードやファイル
など外部から与えられた分割情報にしたがって文字を分
割し、サブパターン候補を作成する０文字データは時系
列なので、分割される最終ストローク番号を、分割情報
として与えることにより複数のパターンに分割すること
ができる。第３図に、「清、＋（ｎ＝１０とする）の分
割例を示す、この例は、分割情報として、ストローク番
号′３”を与えた場合のもので、ストローク番号１　（
ｓ＝１＞からストローク番号３　（ｓ＝３）までのサブ
パターン候補とストローク番号４（ｓ＝４）から最終ス
トローク１１　（ｓ　＝１１）までのサブパターン候補
の２パターンに分割するものである１分割情報は、各文
字ｎに対して与えられる。

もちろん、文字によっては分割しないものもある。

分割情報を求める基準としては、さまざまなものが考え
られる。例えば、辺や冠や垂れなどの部首を区切りとし
て分割する方法、分割するパターンの大きさの範囲を決
めて分割するもの、分割するストローク数の範囲を決め
て分割する方法などがある。本発明においては、これら
のうちいずれの方法も用いることができるが、以後の説
明では部首を区切りとして分割する方法を用いることに
する。第４図は、その方法により分割した様子を示して
いる１分割の際、後の大分類のために、各サブパターン
候補の画数、また、サブパターン候補の最小画数と最大
画数を求めておく。

基本標準パターン格納部１の全ての文字に対してサブパ
ターン候補が作成された後、大分類部３において、画数
による大分類を行う０例えば、サブパターン候補の最小
画数が２、最大画数が１２とすると、２から１２まで、
それぞれの画数を持つサブパターン候補の集合を求める
。各サブパターン候補の画数は、分割の際に求めである
ので、画数ごとに、その画数を持つサブパターン候補を
選択してゆけば良い、第５図は、画数が３であるサブパ
ターン候補の集合を表している。

クラスタリング部４では、求められた全サブパターン候
補に対して類似したパターンの集合（クラスタ）を求め
るクラスタリングを行う。ここでは、単純クラスタリン
グ法を用いて説明する。

まず、ＡとＢの２つのパターン間の距離をＤ（Ａ、Ｂ）
とし、基本標準パターンの各文字ｎを分割したパターン
集合Ｘ−（ｘｉ、ｘ２．・・・。

ｘＮＸ）をクラスタリングすることを考える。始めに、
距離のしきい値Ｔを定め、任意の１パターン、例えばｘ
ｌを選び、これをクラスタ中心Ｚ１とする６次に−ｘｉ
以外のパターンｘｉを選び。

Ｄ（ｚｌ、ｘｉ）を計算する。Ｄ（ｚｌ、ｘｉ）≦Ｔな
らｘｉがＺｌを中心とするクラスタに属すると判定する
−　Ｄ（ｚ　１　ｒ　Ｘ　ｌ　）　＞　Ｔであれば、ｘ
ｉをあらたなりラスタ中心ｚ２とする。再び、残りのパ
ターンからｘｉをとり、距１１ＨｉＤ（ｚｌ。

ｘｉ）とＤ　（ｚ２．ｘｉ　）を計算し、どちらかがＴ
より小さい場合には、ｘｉをそのクラスタに属するとし
て、どちらもＴより大きい場合には、ｘｉを新たなりラ
スタ中心ｚ３とする。このようにして、全てのパターン
ｘｉに対して処理を行い、クラスタを求める。

サブパターン登録部５では、クラスタリング部４にて求
めたクラスタを基にして、サブパターンを作成し、サブ
パターン格納部６に格納する。第６図は、画数３のサブ
パターン候補内のクラスタリングにより求められたクラ
スタの例を示したものである。図に示したように、類似
したサブパターン候補の集合が得られている。このよう
に求められた各クラスタ内で、同形のサブパターン候補
が複数個存在する場合には、共有化が可能なので。

そのサブパターン候補群からサブパターンを作成する。

第６図の例では、「−」と層」のサブパターンを作成す
る。

サブパターンの作成は、サブパターン登録部５において
行われる。「−」の場合には、単語番号ｎ＝１３と２０
のサブパターン候補からサブパターンが作成される。サ
ブパターンの求め方として、両サブパターン候補の平均
パターンを求める方法、または、どちらかを選択する方
法を用いることができる９作成されたサブパターンは、
サブパターン１ｄ番号と共にサブパターン格納部６へ格
納される。

次に、本願における第２の発明について説明する。第２
の発明では、大分類部３における基準として、文字にお
いて占める位置を用いる。ここでは、文字構成を、゛例
えば、第７図のように定め、各構成要素に対してつけら
れた位置番号によって位置を表わすことにする。各サブ
パターン候補の位置を求める方法には、分割の際に、黙
視により与える方法、サブパターン候補のデータから位
置番号を求める方法がある。データから位置番号を求め
るには、例えば、位置番号の領域に含まれるデータ数を
位置番号毎に求め、それが最も多い位置番号をそのサブ
パターンの位置とすればよい。

第８図は、サブパターン候補「青」が各位置に含まれる
データ数を示したものである。図では、位置番号２が最
も多くデータを含むため、「青」の位置番号は２と決定
される。

大分類部３では、この様にして求められた位置番号によ
って、サブパターン候補の大分類を行う。

この場合も、位置番号ごとに、同じ位置番号を持つサブ
パターン候補を選択して行くことにより位置番号ごとの
パターン集合が得られる。第９図は、求められたパター
ン集合の例を位置番号１について示したものである。ク
ラスタリング部４では、このように得られた各位置番号
のパターン集合に対して従来と同様のやり方でクラスタ
リングを行い、求められたクラスからサブパターンを求
める。

本願における第３の発明について、以下に説明する。第
３の発明では、第１図の大分類部３における処理の基準
として、第１の発明における画数と、第２の発明におけ
る位置の両者を用いる。

画数による大分類の結果得られた各パターン集合におい
て、位置番号による大分類を行い、画数と位置番号が共
に同一であるサブパターン候補の集合を求める。このパ
ターン集合を求めるには、先に位置番号による分類を行
ってから画数による分類を行っても良い、第１０図は、
得られたパターン集合の例を示している。図は、位置番
号が１（文字の左側半分）で画数３のサブパターン候補
の集合である。

クラスタリング部４では、このようにして得られたサブ
パターン候補の集合毎に従来と同様にクラスタリングを
行い、求められたクラスタからサブパターンを求める。

（発明の効果） 本願における第１、第２の発明によるサブパターン作成
方式によれば、画数や位置による大分類を行うことによ
り、クラスタリングの対象となるサブパターン候補数を
減少させることができる。

そのため、クラスタリングの処理量が低減され、サブパ
ターン作成、標準パターンの作成のための処理を効率化
できる。

さらに、本願における第３の発明によれば、画数と位置
の両者を用いた大分類によって、クラスタリングの対象
となるサブパターン候補数を更に減少させることができ
る。そのため、サブパターン作成、標準パターン作成処
理をより効率的に行うことができる。

【図面の簡単な説明】

第１図は、第１の発明の一実施例を示すブロック図、第
２図は第１図の基本標準パターン格納部１に格納されて
いるパターンの例を示す図、第３図および第４図は第１
図のサブパターン候補作成部２における処理を説明する
ための図、第５図は第１図の大分類部３における処理結
果を示す図、第６図は第１図のクラスタリング部４にお
ける処理・結果を示す図、第７図は第２の発明における
大分類の基準である位置と位置番号の例を示す図、第８
図は第２の発明における位置番号の決定処理の例を示す
図、第９図は第２の発明における大分類部３における処
理結果を示す図、第１０図は第３の発明における大分類
部３における処理結果を示す図である。 １・・・基本標準パターン格納部、２・・・サブパター
ン候補作成部、３・・・大分Ｍ部、４・・・クラスタリ
ング部、５・・・サブパターン登録部、６・・・サブパ
ターン格納部。

Claims (1)

1. 【特許請求の範囲】 １、複数の文字パターンに共通する部分パターンである
   サブパターンを求めるサブパターン化において、各文字
   パターンに対して与えられた分割点に従って各パターン
   をサブパターン候補に分割し、分割されたサブパターン
   候補に対して画数による大分類を行い、得られた同画数
   のサブパターン候補のクラスタリングを行うことにより
   サブパターンを求めることを特徴とするサブパターン作
   成方式。 ２、複数の文字パターンに共通する部分パターンである
   サブパターンを求めるサブパターン化において、各文字
   パターンに対して与えられた分割点に従って各パターン
   をサブパターン候補に分割し、分割されたサブパターン
   候補に対して、サブパターン候補が文字に占める位置に
   よる大分類を行い、得られた同位置を占めるサブパター
   ン候補のクラスタリングを行うことによりサブパターン
   を求めることを特徴とするサブパターン作成方式。 ３、複数の文字パターンに共通する部分パターンである
   サブパターンを求めるサブパターン化において、各文字
   パターンに対して与えられた分割点に従って各パターン
   をサブパターン候補に分割し、分割されたサブパターン
   候補に対して、画数およびサブパターン候補が文字に占
   める位置による大分類を行い、得られた同画数で同位置
   を占めるサブパターン候補のクラスタリングを行うこと
   によりサブパターンを求めることを特徴とするサブパタ
   ーン作成方式。