JPS5854432B2 - パタ−ン認識処理方法 - Google Patents

Description

【発明の詳細な説明】 本発明は、パターン認識処理方法、特に光学式文字読取
装置等のパターン認識装置に於いて、入カバターンに含
まれる雑音・変形の検出及び除去吸収するパターン認識
処理方法に関するものである。

手書き文字などを対象とする文字認識装置では、パター
ンに雑音や変形（以後、単に雑音とよぶ）が含まれる可
能性が高く、誤読やりジエクト文字を減して識別能力を
向上させるためには、充分な雑音処理を行なうことが必
要である。

従来のこの種の装置の雑音処理法としては、（［）前処
理時に、孤立点やある基準以下の長さの孤立枝及びヒゲ
の除去、欠けの補充を行なうなどの一括処理、（１ｉ）
上記雑音に対処する多数標準パターンを用意する、（ｉ
ｉｉ）識別系をトリーで構成する場合にそのトリーを冗
長にする、などがある。

まずｍの方法では、残すべき枝が除去されたり、比較的
長いヒゲや欠けに対処出来ない。

また（１１）の方法では、パターンの欠けは、どの部分
に現われるか予測出来ないこととのために、多様な雑音
を吸収するためには、非常に多くの標準パターンが必要
になる。

更に（ｉｉｉ）の方法では、冗長性のため識別力を大き
く出来ないか、その冗長性をカバーするためにトリーが
複雑になりカテゴリの増加に対処出来ないなどの欠点が
ある。

本発明は、入カバターンの雑音処理に関する上述の様な
欠点を解消し、パターン認識装置の識別能力を向上させ
ることを目的としたもので、以下図面について詳細に説
明する。

第１図は、本発明を取入れたパターン認識装置の構成例
であって、１は光電変換部、２は前処理部、３は特徴抽
出部、４は雑音処理部、５は判定部である。

まず紙上に書かれた入カバターンは、光電変換部１で電
気信号に変換され、前処理部２で２値化やスムーズイン
グや大きさの正規化等の処理を受ける。

％徴抽出部３では細線化、特徴点抽出、方向コード化、
枝抽出、枝の結合関係を示す情報の抽出、位相幾何的特
徴抽出などの各処理を行なう。

本発明の特徴的部分である雑音処理部４では、入カバタ
ーンを枝単位に標準パターンと比較しながら雑音を検出
し、除去吸収しなから入カバターンを標準パターンと対
応づける。

判定部５では、雑音処理部４で対応付けられた入カバタ
ーンと標準パターンの間の類似性（あるいは相違性）を
示す値を求め、この値を最大にする標準パターンのカテ
ゴリを判定結果とする。

本発明の特徴的部分である雑音処理部４の具体的な説明
に入る前に、標準パターン及び特徴抽出部３で作成され
る入カバターンの表現形式について述べておく。

入カバターン及び標準パターンは、細め処理によって太
さ−０の細線化パターンにされ、これをもとに以下第４
．６．７図に示すパターン情報が抽出される。

第２図は、入カバターンの一例、第３図は標準パターン
の一例を示したもので、６は入カバターン、１は標準パ
ターン、ｍ！（ｉ＝１．２．３・・・）は入カバターン
の特徴点、ｌ！（ｊ−１，２，３，・・・）は入カバタ
ーンの枝、ｍ、ｚ（ｉ’＝１．２．３、−・−）は標準
パターンの特徴点％ １８／（ｊ’＝１．２，３．・・
・）は標準パターンの枝である。

第４図は、第２図の入カバターン６に関する特徴点テー
ブルの一例で、各特徴点ｍ１（１＝１ｔ２．３・・・）
における分岐点数（１：端点、２：中間点、３：３分岐
点、４：４分岐点）、Ｘ座標、ｙ座標、隣接する特徴点
等を示している。

特徴点の順序は、たとえば第２図の入カバターン６また
は第３図の標準パターンＴの上方左側から特徴点を探索
し見出される順にＩ’ｌｌ”１ ＋ ｒｎｉ ｔ ｒｎ
”３・・・・・・２ｍ青。

Ｉｎ ’２ ｙ ｒｎ ”’３・・・・・・とする事に
より決める。

枝については、最初の特徴点Ｉｎ ’１１ ｒｎ １を
一端とする枝をｌｆ。

ｌ青として、文字線にそって例えば反時計方向に文字線
を辿ることによりそれぞれ１２，１３，１４桔ｔ １３
ｔ ！ｌ ”４ ”・・”と順序づける。

第５図は、微小線分方向コードの一例を示し、各数字Ｏ
〜７は、各方向に対応するコードを示す。

一般に２次元の細線化パターンを構成する直線または曲
線は、方向コードの列として記述できるから、入カバタ
ーン及び標準パターンの各校は第６図に実施例を示すよ
うに、方向コード列で表現できる。

第６図は、第２図の入カバターン６に関する枝テーブル
の一例であって、各校ｌ↓（ｊ＝１ 、２ 。

３・・・）の始点および終点の特徴点番号、長さ、第５
図の方向コードを用いて枝を表現した方向コード列など
からなる。

第７図は、第２図の入カバターン６に関する位相幾何的
特徴を示すテーブルの一例で、添え字■は入カバターン
を示し、Ｅは端点数、Ｂ４は４分岐点数、Ｌはループ数
、Ｎは連結成分数（即ち互に独立したストローク数）を
表わす。

第８図は雑音処理部４の構成例を示し、８はスキャンパ
ラメータ、９は標準パターン特徴テーブル、１０は人カ
バターン特徴テーブル、１１はメモリ、４１は雑音情報
計算部、４２は開始枝設走部、４３は雑音検出除去部、
４４は枝対応付は部、４５は枝探索部、４６は雑音情報
、４７は対応付はテーブルである。

雑音処理部４の入力は、開始点探索用のスキャンパラメ
ータ８、上述の特徴点テーブル（第４図）と枝テーブル
（第６図）と位相幾何的特徴を示すテーブル（第７図）
とその他校の結合関係を示す情報から成る標準パターン
特徴テーブル９、及び入カバターン特徴チーフル１０の
３種類である。

従って標準パターン及び入カバターンは、２次元のパタ
ーンとしてではなく、取扱い上便利な特徴テーブルの形
で表現されている。

まず雑音情報計算部４１では、メモリ１１より第７図に
示した位相幾何的特徴（Ｅ 、 Ｂ４． Ｌ 。

Ｎ）を読み出し、それぞ゛れについて入カバターンと標
準パターンの差（△Ｅ＝Ｅ”−Ｅ”’；△Ｂ４＝Ｂ４Ｂ
４．△Ｌ＝ＬＬ、ΔＮ＝Ｎ Ｎここで■は入カバタ
ーン、Ｓは標準パターン）を計算し、これらを雑音情報
４６として一時記憶する。

第２図の入カバターン６を例にとれば△Ｅ＝０、ΔＢ、
＝−１、△Ｌ＝Ｏ１ΔＮ＝Ｏである。

次に、開始枝設走部４２では、スキャンパラメータ８で
決定される走査方向から走査して最初に見出される特徴
点を、第４図に示す様な特徴点テーブルの各特徴点の座
標から決め開始点とする。

更に、メモリ１１を参照して、開始点を一端とする開始
枝とこの開始枝の終点を求め、対応付けの初期値とする
。

第２図の入カバターン６を例にとり、枝１１を開始枝と
すると、開始点、開始枝、開始枝の終点は、枝の方向を
考慮して、それぞれ（ｍ ！ｉ ｐ−ｌ”３ ｐ ｍい
、第３図の標準パターン７では（ｍξ、−１宝２ｍ雪）
となる。

次に雑音検出除去部４３について述べる前に、雑音につ
いて説明する。

ここで雑音と呼ぶものは、標準パターンを基準として位
相幾何的に一致しない入カバターンの部分のことである
。

第９図は、数字に関する標準パターンの例と雑音を含む
入カバターンの例を示している。

第１０図は、第９図に示される様な様々な雑音をその雑
音による位相幾何的特徴の増減（雑音情報４６：△Ｅ・
、ΔＢ４ｔ△Ｌ、ΔＮ）によって分類したもので、ａ＝
ｉは雑音の種類で、それぞれの雑音をもった入カバター
ンの例を示している。

例えば「微小枝（ヒゲ）」が存在している場合（△Ｅ、
−ΔＢ４ ｔ△Ｌ、−ΔＮ）として（１，０゜０．０）
なる雑音情報が現われることから「微小枝」として分類
する。

雑音検出除去部４３では、まず着目している枝の終点の
位相幾何的性質Ｔｓ、Ｔ４（Ｓ ：標準パターン、■二
人カバターン）によって、雑音候補を絞る。

第１１図はこのＴｓ、ＴＩによる雑音候補を示しており
、記号ａ ＝ ｉは第１０図に示す雑音の種類、記号の
上の「−」はその記号の雑音と位相幾何的に逆符号の雑
音、また＊は雑音がないことを示しＴｓ＝ＴＩの時のみ
に現われている。

この様にして得られた雑音候補からいずれの雑音である
か、または雑音がないとするかの判断は、第１１図の各
（ＴＳ＝ＴＩ）の組合わせごとに用意する論理によって
行なう。

第２図の入カバターン６を例にとれば上述のように標準
パターンと入カバターンの開始枝の終点は、（ｍｇ２ｍ
りであり、その位相幾何的性質は、それぞれＴＳ ＝４
。

ＴＩ＝３となるから、雑音候補は、第１１図よりａ、■
、ｂの３種類である。

第１２図は、（Ｔｓ、ＴＩ）＝（４，３）の場合の雑音
を決定する流れ図の一例であり、４３１は、雑音候補、
４３２，４３３は判断を示す。

まず候補４３１はａ、ａ、ｂの３種類からなるが、最初
の判断４３２で雑音情報４６のうちΔＢ４がＯかどうか
を判断し、ΔＢ４４０なら雑音すと決定し、ΔＢ４＝Ｏ
なら第１２図で右へ進み判断４３３に移る。

これは、第１０図かられかる様に、雑音候補４３１（ａ
、ａ、ｂ）のうちで雑音すのみがΔＢ４ＮＯとなり、雑
音ａは（１，０，０，０）であり、雑音ｉは（−ｉ、ｏ
、ｏ、ｏ）であることから、ΔＢ４＝Ｏとなるためであ
る。

次の判断４３３では、入カバターンの着目している枝の
終点から他端が端点である微小枝つまり雑音ａと見なせ
る枝があるかでうかを入カバターン特徴テーブル１０（
第４図）を参照して判断し、あれば雑音ａ、なければ雑
音丁と決定する。

上述の入カバターン６の例では、上述の様にΔＢ４ＮＯ
であるから判断４３２より直ちに雑音すと決定され、雑
音枝は入カバターン特徴テーブル１０を参照して枝ｌＴ
、となる。

見出された雑音枝は、例えば第６図の枝テーブル上の始
点番号をＯに書きかえる等の方法により、その枝が除去
されたことを枝探索部４５に伝える。

ここに示した（Ｔｓ、ＴＩ）＝（４，３）の例は、第１
２図の２つの判断４３２及び４３３から雑音が決定出来
る比較的簡単な例で、次の例で示す枝の幾何的な相違度
あるいは類似度は判断に用いていない。

第１３図は（ＴＳ、ＴＩ）＝（３，３）の場合の雑音を
決定する流れ図の一例で、４３４は雑音候補、４３５−
４３８は判断である。

（ＴＳ、ＴＩ）＝（３，３）の場合雑音候補４３４は、
第１１′図より＊ ｙ ａ ｐ ａ Ｉ Ｃの４種であ
り、判断４３５は例えば雑音情報４６のうち△Ｌ＜０な
ら当該終点に関して雑音なしの＊、△Ｌ＞０なら雑音Ｃ
１△Ｌ＝０なら判断４３６へ進む。

判断４３６は、△Ｅ＝−１かどうかを判断し、△Ｅ＝−
１なら雑音１１△Ｅ＃−ｉなら判断４３７へ進む。

判断４３７は、△Ｅ≧１かどうかを判断し、△Ｅ＜１な
ら雑音なし△Ｅ≧１なら判断４３８へ進む。

判断４３８は、標準パターンと入カバターンのそれぞれ
着目する枝の次の枝について、以下に述べる幾何的相違
度（あるいは類似度）を求め、相違度がある閾値６以上
（あるいは類似度がある閾値δ′以下）であれば雑音α
、閾値δ以下（類似度であれば閾値６７以上）であれば
雑音なしとする。

ここで枝の幾何的相違度および類似度について説明する
。

雑音の決定のためには、相違度、類似度のうち倒れか一
方をもちいる。

まず、相違度の実施例を示すと、枝の幾何的な性質とし
て、方向、屈曲、長さを考え、それぞれに関する標準パ
ターンと入カバターンの差を以下の様に定義する。

Ｄｌ：両パターンの平均方向の差 ここでＤｌ、Ｄ２．Ｄ３はそれぞれ枝の方向、屈曲、長
さに関する差、■は入カバターン、Ｓは標準パターンを
示す。

幾何的相違度りは、重みづけ定数α、β、γを用いて と表わす。

一方、類似度については、 定義することができる。

Ｔ１れ 一例として次の様に ｙ Ｔ２ ｙ Ｔ３をそれぞ 以上の様な方法によって雑音の種類を決定するが、ここ
で第１０図に示したａ ＝ ｉの各雑音の吸収法につい
て順に説明する。

雑音ａ：着目する入カバターンの枝の終点（３分岐点）
から出る枝のうち、他端が端点である最も短い枝を除去
する。

雑音ｉ：標準パターンの枝について、雑音ａと同様の処
理を行なう。

雑音ｂ＝着目する入カバターンの枝の終点（３分岐点）
から出る枝のうち、他端が３分岐点である最も短い枝を
除去し、２つの３分岐点を１つの４分岐点に統合する。

雑音ｉ：標準パターンの枝について雑音すと同様の処理
を行なう。

雑音Ｃ：着目する入カバターンの枝の終点（３分岐点）
から出る枝のうち、他端が３分岐点である最も短い枝を
除去する。

雑音ｄ：着目する入カバターンの枝の終点（４分岐点）
から出る枝のうち、他端が端点である最も短い枝を除去
する。

雑音ｅ：着目する入カバターンの枝の終点（４分岐点）
から出る枝のうち、他端が端点である２本の短い枝を除
去する。

雑音ｆ：着目する入カバターンの枝の終点（端点）と終
点から最も近い距離にある端点をつなぎ統合する。

雑音ｇ：着目する標準パターンの枝の終点（３分岐点）
を分離する。

雑音ｈ：着目する入カバターンの枝の終点（端点）と終
点から最も近い距離にある端点をつなぎ統合する。

雑音ｉ：着目する入カバターンの枝の終点（４分岐点）
を切断して３分岐点とする。

以上のような各雑音の吸収の際には、これらの位相幾何
的修正の他に、第１０図に示す各雑音による位相幾何的
特徴の増減分だけ雑音情報４６を修正し、他の雑音の検
出にｔｌＪ用する。

例えば、上述の入カバターン６では△Ｅ＝０、ΔＢ、＝
−１、△Ｌ＝０、ΔＮ＝０から、△Ｅ＝ΔＢ４＝△Ｌ＝
ΔＮ＝Ｏと修正される。

枝対応付は部４４では、雑音板を除く入カバターンと標
準パターンの対応する枝番者を対応材はテーブル４７に
書き込み、判定部５で参照する。

以上の様な手順で、入カバターンと標準パターンの一組
の枝の対応付けが終り、枝探索部４５に入る。

枝探索部４５では、たとえば左回りに入カバターンと標
準パターンの文字線を辿り新らたな枝番者とその終点番
号の値を設定して雑音検出除去部４３にもどり、すべて
の枝が対応づくまで処理をくりかえす。

第１４図は、以上の様な処理によって作成された上述の
入カバターン６と標準パターン７の対応付はテーブルの
例で、第１回目の対応付けでは、ＩＢ、と−０１第２回
目はｌ♀とｄ１１第３目はｌ量とｌ五、第４回目は−４
９と−ｌ”１ｓ第５回目はＩＢ、と氾がそれぞれ対応付
いており、枝ＩＩ。

は雑音枝として除かれている。

以上説明した如く、本発明によれば、枝単位に標準パタ
ーンを基準として、雑音の有無、雑音がある時にはその
種類と除去すべき枝番を検出するようにしているため、
比較的長いヒゲや欠けがあっても正しい対応付けが可能
となり、比較的少ないカテゴリ当りの標準パターン数で
足りる。

【図面の簡単な説明】

第１図は本発明を取入れたパターン認識装置の一実施例
構成、第２図は細線化された入カバターンの一例、第３
図は細線化された標準パターンの一例、第４図は特徴点
テーブルの一例、第５図は微小線分方向コードの一例、
第６図は枝テーブルの一例、第１図は入カバターンの位
相幾何的特徴を示すテーブルの一例、第８図は雑音処理
部４の一実施例構成、第９図は数字（１〜０）について
の標準パターンの例と雑音をもった入カバターンの例、
第１０図は雑音の種類とその位相幾何的特徴の増減との
対応を表わす説明図、第１１図は枝の終点の位相幾何的
性質による雑音候補を説明する説明図、第１２図、第１
３図は雑音を決定する流れ図の一例、第１４図は対応付
はテーブルの一例を示す。 図中１は光電変換部、２は前処理部、３は特徴抽出部、
４は雑音処理部、５は判定部、６は細線化された入カバ
ターンの例、１は細線化された標準パターンの例、８は
スキャンパラメータ、９は標準パターン特徴テーブル、
１０は入カバターン特徴テーブル、１１はメモリ、４１
は雑音情報計算部、４２は開始枝設走部、４３は雑音検
出除去部、４４は枝対応付は部、４５は枝探索部、４６
は雑音情報、４１は対応付はテーブル、４３１は雑音候
補、４３２，４３３は判断、４３４は雑音候補、４３５
〜４３８は判断処理を示す。

Claims (1)

1. 【特許請求の範囲】 １ パターンを構成する直線または曲線を多方向をとり
   得る微小線分の方向コード列として記述し、標準パター
   ンと入カバターンとを対応付けの開始点から枝の順序関
   係を維持しながら枝ごとに対応づけ、標準パターンと入
   カバターンとの類似性又は差異を示す量によって識別を
   行なうパターン認識装置において、標準パターンと入カ
   バターンとの枝を対応付ける際に、パターンの位相幾何
   的特徴により入カバターンに含まれる雑音・変形の種類
   を絞り、枝の幾何的相違度又は類似度と枝の終点の位相
   幾何的性質とにより、着目する枝とその周りの雑音・変
   形の有無と該雑音・変形がある時には該雑音・変形の種
   類とを決定し、標準パターンまたは入カバターンに、前
   記雑音・変形に応じて枝の除去、特徴点の分離、統合を
   含む位相幾何的な修正を加えることによって該雑音・変
   形を吸収し標準パターンと入カバターンとの対応づけを
   行なうことを特徴とするパターン認識処理方法。 ２ 上記パターンの位相幾何的特徴は、ループ数、端点
   数、３分岐点数、４分岐点数、および連結成分数のうち
   少なくともいずれか４個を選んで抽出されることを特徴
   とする特許請求の範囲第１項記載のパターン認識処理方
   法。 ３ 上記各校の終点の位相幾何的性質は、端点、中間点
   、３分岐点、４分岐点のいずれかを抽出することによっ
   て決定されることを特徴とする特許請求の範囲第１項ま
   たは第２項記載のパターン認識処理方法。