JPH0143353B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、パターンマツチング法による手書き
の文字、記号、あるいは図形等のパターンを認識
するための方式に関し、特に、本発明者が先に発
明し、本出願人により出願されている特願昭54−
90272の発明“文字・記号認識方式”（特開昭56−
16271、以後「先行発明」と呼ぶ）の改良に関す
るものであつて、ブレインパターンマツプを用い
て行なわれる定義パターンと入力パターンとの間
の歪み距離の計算方式を更に改善し、認識効率の
向上を図つたものである。

〔技術の背景〕

手書き文字の認識手法を概念的に分類すると、
文字の位相構造（例えばストロークの組み合わさ
り方）によるものと、定義パターン（辞書パター
ン）とのマツチングによる方法とがあるが、前者
はストロークの抽出が面倒であり、後者は文字の
変形があつたときの処理が難しいという欠点があ
る。本発明の基礎となつている前記先行発明は、
後者に属するが、手書きによつて生ずる変形も線
の太さ、細さも制約条件とならない統一的な手法
を提供している。以下に、前記先行発明につい
て、その概要を説明する。

定義パターンと入力パターンとのマツチングの
度合いを示す測度として、入力パターンの歪量Ｄ
を定義し、これを定義パターン毎に計算して、入
力パターンに対する歪み量Ｄが最小となる定義パ
ターンを、認識パターンとするものである。これ
は、各定義パターンを歪ませて（変形させて）入
力パターンに一致させたとき、必要とした歪み量
が最小のもの、すなわち変形量が最小で済む定義
パターンを選択することを意味する。

一般に、認識問題とは、「観測したパターンが
あらかじめ定められているいずれの定義パターン
に最も似ているかを決定することである」と規定
される。従来のこのような認識系を概念的に例示
すると、第１図のようになる。

第１図において、１１−１，１１−２，…，１
１−ｎは基準となる定義文字・記号のパターンで
あり、例えば“Ａ”，“Ｂ”…“＋”等について示
してある。これら定義文字・記号のパターンは例
えば磁気デイスク装置等からなる定義ライブラリ
に予め格納されている。１２は入力された被認識
文字・記号のパターンであり、例えばスキヤナー
などの光学読取り手段で検出されたものである。
この被認識文字・記号パターン１２は、類似判定
部１３−１，１３−２，…，１３−ｎにおいて、
それぞれ対応する定義パターン１１−１，１１−
２，…，１１−ｎと比較されて類似度が算出さ
れ、類似量R₁、R₂、…Rnが出力される。判定部
１４は、これらの類似量の中の最大の類似量を判
定し、この最大類似量に対応する定義パターンを
もつて、被認識パターンを読取るものである。こ
れは典型的なパターン・マツチング方式であつ
て、手書き文字・記号が有する歪みに対処するこ
とが困難であり、結局高精度な文字・記号認識が
できないという問題をもつていた。

このため、前記先行発明は、手書き文字・記号
に現われる歪みに起因して正確な読取りができな
いという従来方式の問題を効果的に解決したもの
であり、認識問題を次のように置きかえている。

「パターンＸを観測したとき、それが各定義パ
ターンが歪んだものとして歪み量Ｄを求め、Ｄの
最も小さい定義パターンに決定する。」 これは、「どれだけ似ているか」という事を
「どれだけ歪んでいるか」という問題に転換した
ものであるが、その本質的な違いは、後者では、
歪みによつてどのようなパターンでも作る事がで
きるという事実にもとずいて、「観測パターンは
定義パターンが歪んだものだ」という仮定を置い
た事である。

具体的には、基準となる複数の定義文字・記号
について、そのパターンの各画素より遠ざかるの
に比例して、重みづけ値すなわち歪み度が増大す
るように、一定の規則性に従つて、予め定義文
字・記号パターンの歪みパターン・マツプを生成
する。他方、入力された被認識文字・記号のパタ
ーンについても、同様に前記一定の規則性に従つ
て歪みパターン・マツプを生成する。そして前記
定義パターンおよび前記被認識パターンそれぞれ
の歪みパターンマツプの、相互に対応する部分が
有するそれぞれの前記重みづけ値の差を変数とし
て、評価関数の値を求め、すなわちマツチングを
とり、該評価関数の値が最小となる定義パターン
の文字・記号をもつて、認識を確定するようにし
たものである。

第２図は先行発明に係る方式の概念図である。
本図において、２１−１，２１−２，…２１−ｎ
は、基準となる定義文字・記号のパターンであ
る。これらのパターンは、定義文字・記号から生
成された歪みパターンマツプ形式のものであり、
第１図のパターン１１−１，１１−２，…１１−
ｎとは全く異なつている。他方、２２は入力され
た被認識文字・記号のパターンであるが、これも
歪みパターンマツプ形式のものであり、第１図の
パターン１２とは全く異なつている。これらのパ
ターン２１−１，…，２１−ｎ，２２が第１図の
パターン１１−１，…，１１−ｎ，１２と異なる
のは、該先行発明方式には、認識のパラメータと
して“歪み量”の概念が導入されていることにあ
る。この被認識文字・記号パターン２２は、歪み
量計算部２３−１，２３−２，…，２３−ｎにお
いて、それぞれ対応するパターン２１−１，２１
−２，…，２１−ｎの間で各歪み量が算出され、
歪み量D₁、D₂、…Dnが出力される。そして判定
部２４において最小の歪み量が決定され、この最
小歪み量に対する定義パターンをもつて被認識パ
ターンの読取りが行なわれる。

第３図は該先行発明の実施例のブロツク構成図
である。本図において、３１はパターン入力部、
３２はパターン規格化部、３３はブレインパター
ンマツプ生成部、３４は歪み量計算部、３５は定
義パターン記憶部、３６は最小値選択部を表わ
す。

パターン入力部３１は、認識すべき文字、記
号、図形等のパターン、たとえば“Ａ”をスキヤ
ナで光学的に読取り、電気信号に変換して、メツ
シユ状の画素情報としてパターン規格化回路３２
に出力する。

パターン規格化回路３２は、入力されたパター
ンを、認識処理のための一定のサイズに規格化し
てブレインパターンマツプ生成部３３に出力す
る。なおこの規格化処理では、パターンの線幅は
変更されない。

ブレインパターンマツプ生成部３３は、任意の
入力パターンについて、その各画素毎に画素から
遠ざかるにつれて重み、すなわち歪み度が増大す
るブレーン（Brain）パターンと呼ばれる歪みパ
ターンのマツプを生成する。

ブレインパターンマツプは、一定の数学的規
則、たとえば第４図ａ，ｂに示すように、各画素
について、ａの４方向およびｂの８方向にある画
素を順次交互に選択して順序数の重み付けを行な
う手法により、同図ｃに例示されるように生成さ
れる。なお、上記した数学的規則は、
“Octagonal Distance”と呼ばれている。

後述される第５図ａ，ｂは、文字“Ａ”につい
て生成されたブレインパターンマツプの例を示し
ている。ａが定義パターン、ｂが入力パターンで
ある。

このブレインパターンマツプでは、白地に黒文
字のパターンの場合、白黒境界部の総ての黒画素
に重み“１”が設定され、該黒画素から遠ざかる
方向に、２、３、４、…のように増大する順序数
の重みが設定される。なお第５図のブレインパタ
ーンマツプ例では、文字“Ａ”の線幅が１画素の
単位幅となつているが、複数の画素幅をもつ太い
線の場合には、線の内側へ向つて、０、−１、−
２、…、のように負方向の重み付けがなされる。
このようなブレインパターンマツプを用いること
により、任意の崩れた手書き文字について、定義
文字からの歪み距離を簡単に求めることができ
る。たとえば重み“１”をもつ黒画素が、手書き
によつて歪んで重み“５”の画素位置に書かれた
場合には、その間の歪み距離を、５−１＝４ある
ものと計算する。

第３図の歪み量計算部３４は、定義パターン記
憶部３５に記憶されている予め作成された複数の
定義パターンのブレインパターンマツプ（以後定
義ブレインパターンマツプと呼ぶ）と、ブレイン
パターンマツプ生成部３３から出力された入力パ
ターンのブレインパターンマツプ（以後入力ブレ
インパターンマツプと呼ぶ）との間で、上記した
ような歪み距離の計算を行ない、各定義パターン
を歪ませて入力パターンに一致させたとしたとき
の、各定義パターン毎の歪み量を求める。

次に第５図ａ，ｂに示す双方のブレインパター
ンマツプを用いて、歪み量の計算処理方式を説明
する。歪み量を表わす評価関数は、両ブレインパ
ターンマツプの対応する画素同士の間の重み値の
差（ｄとする）の２乗和で与えられるが、その算
出方法は、定義ブレインパターンマツプの重み
“１”の黒画素から入力ブレインパターンマツプ
の対応画素へ、および入力ブレインパターンマツ
プの重み“１”の黒画素から定義ブレインパター
ンマツプの対応画素への２方向について行なわれ
る。これは双方のパターンの相違点を、評価関数
に強く反映させるためである。たとえば前者の場
合、第５図の矢印Ａで示すように、定義ブレイン
パターンマツプａの黒画素は、入力ブレインパ
ターンマツプｂのと比較され、同様に後者の場
合、矢印Ｂで示すように、マツプｂの黒画素
は、マツプａのと比較され、以下、双方のマツ
プにおいて、重み“１”をもつ黒画素の総てが、
相互に相手方マツプの対応画素と比較される。

ここで、一般的に定義ブレインパターンマツプ
の画素の重みをd_aとし、入力ブレインパターンマ
ツプの対応画素の重みをd_bとし、更に定義パター
ンから入力パターンへ向つて算出される歪み量を
d₁、そしてその逆方向の入力パターンから定義パ
ターンへ向つて算出される歪み量をd₂とする。d₁
およびd₂は、それぞれパターン中の重み“１”の
総ての黒画素について算出される歪み距離（d_b−
d_a）あるいは（d_a−d_b）の２乗和として次式で与
えられる。

d₁＝Σ（d_b−d_a）２ d₂＝Σ（d_a−d_b）２ この総計Ｄ＝d₁＋d₂が評価関数であり、歪み量
計算部３４は、この評価関数Ｄにより、各定義パ
ターン毎に、入力パターンに対する歪み量を計算
する。

最小値選択部３６は、歪み量計算部３４が計算
した各定義パターン毎の歪み量の中の最小値を検
出し、当該定義パターンを認識結果として出力す
る。

以上述べた先行発明方式は、手書き文字のよう
な歪みの大きいパターンの認識にきわめて有効な
ものであり、これまでに実施されたものは良好な
成績を上げている。しかし本方式は、歪み量の計
算を定義パターンと入力パターンとの間で双方向
にマツチングをとつて行なつており、そのため両
パターン間の差異が大きいものでは、歪みの情報
量が増大するので認識精度を高めることができる
が、両パターン間に一致部分が多いものでは、歪
みの情報が重複して計算されることになるため、
各定義パターン毎の歪み量の較差を縮めて曖昧さ
を助長するように作用し、認識精度を低下させる
という欠点をもつていた。

〔発明の目的および構成〕

本発明の目的は、上記先行発明方式の欠点を改
善するため、パターンの歪み量を与える評価関数
を改良し、パターン認識の精度および認識処理効
率の向上を図ることにある。

本発明は、そのための構成としてパターンマツ
チング法により、文字、記号、図形等のパターン
を認識するシステムであつて、複数の定義パター
ンおよび入力パターンのそれぞれについて画素毎
の歪み分布を表わすブレインパターンマツプを作
成する手段と、該ブレインパターンマツプを用い
て各定義パターンと入力パターンとの間の画素毎
の歪み距離を計算し、それに基づき入力パターン
に対する各定義パターンの歪み量を求める手段
と、入力パターンに対して最小の歪み量を与える
一つの定義パターンを選択し、入力パターンに対
応づける手段とをそなえたものにおいて、上記入
力パターンに対する定義パターンの歪み量を各定
義パターン毎に求める手段は、定義パターンから
見た入力パターンの対応画素間の距離計算を双方
のブレインパターンマツプを用いて行なう第１段
階と、該第１段階で距離計算が行なわれた入力パ
ターンの画素を重複しないように排除した残りの
入力パターンの画素について、入力パターンから
見た定義パターンの対応画素間の距離計算を双方
のブレインパターンマツプを用いて行なう第２段
階との二つの実行段階を有することを特徴として
いる。

〔発明の実施例〕

以下に、本発明を実施例にしたがつて説明す
る。

本発明は、前述した先行発明方式における定義
パターンと入力パターンとの間の双方マツチング
による歪み量計算において、定義パターンから入
力パターンへ向う方向のマツチングで計算の済ん
でいる入力パターンの対応黒画素を、入力パター
ンから定義パターンへのマツチングの際に計算対
象から外すことにより、パターン間の一致部分が
２重に計算されないようにする。そのため、たと
えば第５図の矢印Ａで示すマツチングの場合のよ
うに、定義ブレインパターンマツプａ上の重み
の黒画素が、入力ブレインパターンマツプｂ上の
重みの画素に対応づけられたとき、この重み
の画素が、その基点となる入力パターン中のどの
黒画素の重み、すなわち歪みを表わしているもの
であるかが識別できなければならない。この基点
となつている黒画素を識別することができてはじ
めて、次に逆方向にマツチングをとるときに当該
黒画素を計算から外すことが可能となるのであ
る。

本発明実施例では、上記したようなブレインパ
ターンマツプ中の各重みについて、その基点黒画
素を表示するため、第８図に例示される黒画素対
応パターンを使用する。なお、第８図については
後述される。

第６図は、本発明方式を実施したパターン認識
システムの概略構成図である。本図において、６
１はパターン入力部、６２はパターン規格化部、
６３はブレインパターンマツプ生成部、６４は黒
画素対応パターン生成部、６５はメモリ、６６は
歪み量計算部、６７は定義パターンライブラリ、
６８は最小値選択部であり、これらの基本構成
は、上記した双方向マツチングにおける重複計算
を排除するために設けられた手段を除き、第３図
で説明した先行発明の実施例システムと同じであ
る。

黒画素対応パターン生成部６４は、ブレインパ
ターンマツプに分布されている各画素の重みが、
どの黒画素を基点にしているかを表わす黒画素対
応パターンを生成する。

メモリ６５はパターン認識処理のための作業領
域を提供するとともに、各種の処理プログラム、
すなわち規格化プログラム、ブレインプログラ
ム、黒画素対応プログラム、歪み計算プログラム
などを保持している。メモリ内に設置されている
テーブルおよびテーブルは、入力ブレインパ
ターンマツプを生成するために使用される作業テ
ーブルであり、またテーブルＰは入力パターンの
各黒画素を識別するための番号付けテーブル、そ
してテーブルＱは黒画素対応パターンを示すテー
ブルである。これらのテーブルを使用する処理に
ついては、後述される。

定義パターンライブラリ６７には、各定義パタ
ーン毎のブレインパターンマツプと黒画素対応パ
ターンとが格納されている。

第７図は、本実施例システムの概略的な処理フ
ローを示す。以下に第７図のフローａ乃至ｇにし
たがつて、第６図の実施例システムの動作を説明
する。

(a) パターン入力部６１は、スキヤナ等で読み取
つた被認識文字、記号、図形を、一単位ずつ切
り出し、パターン規格化部６２に供給する。

(b) パターン規格化部６２は、切り出された各パ
ターンをＮ×Ｍドツトの大きさに規格化し、ブ
レインパターンマツプ生成部６３に供給する。
なお、ここで規格化されたパターンは、メモリ
６５中に蓄積されている。

(c) ブレインパターンマツプ生成部６３は、規格
化された入力パターンの線部分における白黒境
界域にある総ての黒画素の座標をテーブルに
設定し、その重み値Ｊを“１”にする。次にこ
のテーブルから１画素ずつ取り出して、その
４方向距離にある白画素（“０”の画素）の値
を、重みＪ＋１（Ｊ＝１）にし、その座標をテ
ーブルに格納する。この動作を、テーブル
の総ての画素について実行する。次に、テーブ
ルから１画素ずつ取り出して、８方向にある
白画素のみについてその値をＪ＋１（Ｊ＝２）
にし、その画素の座標をテーブルに入れる。
これをテーブルの画素がなくなるまで繰り返
す。

ブレインパターンマツプ生成部６３は、以上
のテーブル、を使用した処理を、必要な回
数だけ交互に実行することにより、各黒画素を
基点として、Ｊ＝Ｊ＋１による順序数の重みづ
けを行ない、入力パターンに対するブレインパ
ターンマツプを生成する。

(d) 黒画素対応パターン生成部６４は、上記(c)の
処理と平行して、黒画素対応パターンの生成処
理を行なう。そのために、まず境界上の総ての
黒画素、すなわち重み値Ｊ＝１をもつ画素の座
標に、順番に番号ｋ（ｋ＝１、２、３、…）を
振り、テーブルＰに格納する。そして(c)での白
画素に対する順次的な重み値Ｊの付与（Ｊ＝Ｊ
＋１）に応じて、当該白画素の座標に、その重
みＪの基点となつている黒画素の番号ｋを振
り、第８図ａ，ｂに示すような黒画素対応パタ
ーンを生成して、テーブルＱに格納する。

第８図は第５図に示すブレインパターンマツ
プに対応する黒画素対応パターンを表わし、(a)
は定義パターンライブラリ６７に予め格納され
ている定義パターン「Ａ」の黒画素対応パター
ンの１例を示し、(b)は黒画素対応パターン生成
部６４で生成された入力パターン「Ａ」に対す
るものの１例を示す。前者では黒画素に１から
29までの番号が振られ、後者では黒画素に１か
ら27までの番号が振られ、それぞれ、第５図
ａ，ｂのブレインパターンマツプ上の対応画素
について、その基点となる黒画素の番号を示し
ている。

(e) 歪み量計算部６６は、まず第５図の矢印Ａで
示されるような、定義パターンから入力パター
ンへのマツチング処理を行なう。その際、第８
図ｂに示すような入力パターンに対する黒画素
対応パターンを参照して基点黒画素番号を求
め、第９図に示すような計算が行なわれたかど
うかをチエツクするための表を作成する。計算
が行なわれた場合には、上記チエツク表の該当
黒画素番号のチエツクの有無欄に“１”がたて
られる。

(f) 歪み量計算部６６は、次に第５図の矢印Ｂで
示されるような逆方向マツチング処理を行な
う。このとき、入力パターンの黒画素として、
第９図のチエツク表に“１”がたてられていな
い未チエツクの黒画素番号のもののみを選択し
て、歪み量の計算を行うようにする。この結
果、定義パターンと入力パターンとの間で一致
性の高い、換言すれば歪みの少い画素間では、
双方向マツチングにおいて重複計算がなされる
ことはほとんどなくなり、歪み量に含まれる冗
長な要素を減少させることができる。

(g) 最小値選択部６８は、上記(f)により冗長さが
改善された歪み量を各定義パターン間で比較
し、最小値を求めて認識結果とし、出力する。

〔発明の効果〕

以上のように、本発明によれば、前記先行発明
方式に較べて、評価関数によるパターン弁別性能
が向上して、エラー率を数分の一にまで小さくす
ることができ、著しい改善効果が得られた。

【図面の簡単な説明】

第１図は従来の一般的なパターン認識方式の概
念図、第２図は先行発明方式の概念図、第３図は
先行発明方式の実施例のブロツク図、第４図ａ乃
至ｃはブレインパターンマツプの説明図、第５図
ａ，ｂはブレインパターンマツプの例を示す図、
第６図は本発明実施例の構成図、第７図はその処
理フロー図、第８図は黒画素対応パターンの例を
示す図、第９図は重複計算を避けるためのチエツ
ク表の説明図である。 図中、６１はパターン入力部、６２はパターン
規格化部、６３はブレインパターンマツプ生成
部、６４は黒画素対応パターン生成部、６５はメ
モリ、６６は歪み量計算部、６７は定義パターン
ライブラリ、６８は最小値選択部を表わす。

Claims (1)

1. 【特許請求の範囲】 １ パターンマツチング法により、文字、記号、
   図形等のパターンを認識するシステムであつて、 複数の定義パターンおよび入力パターンのそれ
   ぞれについて画素毎の歪み分布を表わすブレイン
   パターンマツプを作成する手段と、該ブレインパ
   ターンマツプを用いて各定義パターンと入力パタ
   ーンとの間の画素毎の歪み距離を計算し、それに
   基づき入力パターンに対する各定義パターンの歪
   み量を求める手段と、入力パターンに対して最小
   の歪み量を与える一つの定義パターンを選択し、
   入力パターンに対応づける手段とをそなえたもの
   において、 上記入力パターンに対する定義パターンの歪み
   量を各定義パターン毎に求める手段は、定義パタ
   ーンから見た入力パターンの対応画素間の距離計
   算を双方のブレインパターンマツプを用いて行な
   う第１段階と、該第１段階で距離計算が行なわれ
   た入力パターンの画素を重複しないように一度計
   算された対応画素を排除した残りの入力パターン
   の画素について、入力パターンから見た定義パタ
   ーンの対応画素間の距離計算を双方のブレインパ
   ターンマツプを用いて行なう第２段階との二つの
   実行段階を有することを特徴とするパターン認識
   方式。