JP2853169B2 - パターン認識装置 - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は文字や図形等のパターンを認識する装置に関
するものである。

B.発明の概要 本発明は、文字や図形等のパターンを、照合対象とな
る辞書を用いて認識する装置において、 パターンの特徴点の位置的特徴及び方向的特徴をあい
まい集合（ファジイ集合）で表した辞書を用い、認識対
象のパターンの特徴点の位置及び方向に対応するメンバ
ーシップ値について演算を行い、演算結果にもとづいて
認識結果を得ることによって、 パターンの認識を高い精度でかつ高速に実行できるよ
うにしたものである。

C.従来の技術 文字や図形等のパターン認識する場合、例えば、書類
や図面等をイメージスキャナ等の入力装置で操作して得
られる黒と白の２値画像データ（入力パターン）に基づ
いて、予め記憶されている文字や図形の標準パターン
（辞書パターン）と位置等を照合し、辞書パターンの中
から最も重なり合うものを最終的に認識結果として求め
ている。

認識方法の具体例として、例えば、入力パターンと辞
書パターンをそれぞれ小さな正方格子状（メッシュ）に
区切り、格子点が文字や図形である場合には黒（１）、
そうでないときは（０）と表す場合において、入力と辞
書の２つのパターンの重なりの程度をハミング距離を用
いて求めることができる。これは、入力と辞書が黒と黒
または白と白の場合には０、黒と白または白と黒の場合
には１とおき、その総和を求めるものである。つまり、
黒と黒、白と白のように重なり合っていればいるほど、
その総和（ハミング距離）が小さくなる。この性質によ
り、多数の辞書パターンの中から入力パターンと最も重
なり合っているもの、すなわち、ハミング距離が最も小
さいものを認識結果とするものである。

D.発明が解決しようとする課題 この方法だと入力パターンの位置が辞書パターンの位
置とずれていたり、大きさが異なっていたり、傾きが異
なっていたりすると、重なりの程度が変わってしまい、
認識の誤りが生じやすい欠点がある。

また記憶容量の点でも問題がある。１文字あるいは１
図形パターンの必要空間は表示のための文字フォントの
ように８×８画素（英数字）や24×24画素（漢字）の空
間では済まず、線の切れやつぶれを極力避けるため少な
くともその３〜５倍の空間を必要とする。特に、漢字や
複雑な図形の場合128×128画素程度以上確保しないと安
定な処理が望めないことになる。

文字や図形パターンの辞書種別は漢字の場合第二水準
を含めると6000字種以上に及び、図形の場合でも多いと
きには1000字種以上になる。

このような膨大な辞書種別に対して、１辞書毎に128
×128画素を確保するとすれば、メモリとして2Kバイト
が必要となる。つまり、先の漢字では12Mバイト以上、
図形で2Mバイト以上もの記憶領域が必要となる。

ハードウェア構成上この容量は無視できないほど大き
く、また、辞書の探索や整合処理にも処理時間などで影
響を与えることになる。

更に、辞書種別の点からいえば、上述の膨大な種別に
ついてひとつひとつ辞書をマニュアルで登録する作業が
必要とされており、そのための作業時間も膨大となる問
題点がある。

以上まとめると、従来技術には以下の大きな３つの課
題が残されている。

認識精度の高い認識手法の確立 記憶容量低減のための辞書構成方法の確立 辞書の自動生成方法の確立 本発明は、このような課題を解決することを目的とす
る。

E.課題を解決するための手段及び作用 文字や図形パターンは人間の歴史的または経験的規則
に従って記述された位置関係にあるが、パターンを特徴
づける点（特徴点）そのものはあいまい性を有してい
る。

例えば、第３図ａの○印で示す文字“A"の代表的な特
徴点の場合（これを頂点と呼ぶものとする）、頂点の位
置そのものは他の特徴点からみて左に振れたり（同図
ｂ）、右に振れたり（同図ｃ）する。また、頂点のとこ
ろで切れたり（同図ｄ）もする。

しかし、同図ｅのように、頂点の部分だけが他の特徴
点より下の方に位置することはありえない。

結局、文字“A"の頂点というものは、他の特徴点より
位置関係で言うと上の方でかつ真ん中付近にある、とい
う極めてあいまいな尺度で規則性を持っているというこ
とになる。

本発明は、このように文字や図形パターンの特徴点の
位置関係にあいまい性があることを考慮して、その位置
関係をあいまい集合（ファジイ集合）の概念を取り入れ
て表現することによりパターン毎にファジイ辞書を登録
し、認識対象のパターンと各パターンのファジイ辞書と
を比較してその比較結果にもとづいて認識結果を得よう
とするものである。

第１図に本発明装置のうちファジイ辞書作成のフロー
を示すと、先ずあるパターンに対して多数のサンプルを
作成し、各サンプル毎に光学的走査によりパターンを入
力する。

次いでこの入力したパターン即ち画像情報に対してノ
イズ処理等の前処理を行う。続いてこの画像情報にもと
づいて例えば白画素に隣接する黒画素群を輪郭画素群と
して抜き出し、これらについて直線近似処理等の情報圧
縮化を行った後、各輪郭画素群を例えば右回りに結合し
て隣接画素同士P_n，P_n+1を結ぶベクトルを抽出し、この
ベクトルを画素P_nの位置とベクトルの方向とにより特定
して記憶する。ここでP_nの位置についてはX,Y座標によ
り表され、方向については、次のように量子化した方向
コードθとして表される。一般に座標点ａ（X_s，Y_s）を
始点とし、座標点ｂ（X_e，Y_e）を終点とする線分の方向
αは次式で表される。

α＝tan^-1｛（Y_e，Y_s）／（X_e，X_s） ここに方向コードθは例えば方向αを45度単位に量子
化したものであり、第２図（ａ）に示すようにθ＝0,1,
2……７としたとき、次の条件を満たすときのθを求め
ることにより得られる。

（２θ−１）π/8≦α≦（２θ＋１）π/8 なお向きを考慮しない場合には第２図（ｂ）に示すよ
うにθ＝0,1,2,3の４つのコードとして取り扱うことも
できる。

一方、パターンが描かれる領域をａ×ｂ（a,bは整
数）のメッシュに区分して、このメッシュ群よりなる領
域（メッシュ領域）に対応する領域を方向コードの数だ
けメモリ内に確保し、確保したメッシュ領域に夫々方向
コードを割り当てる。例えば方向コードθが第２図
（ａ）に示すように０〜７までの８通りある場合、メモ
リ内にａ×ｂのメッシュ領域を８個確保し、そのうちの
１つをθ＝０に対応したメッシュ領域、他の１つをθ＝
１に対応したメッシュ領域、………といった具合に割り
当てる。

次に各サンプルにおけるパターンの特徴点例えば先述
した輪郭画素群を抽出し、メモリ内の８つのメッシュ領
域の中でその特徴点の位置及び方向コードに対応するメ
ッシュ位置（メッシュ領域内のメッシュの位置）に出現
頻度つまり出現回数を書き込む。例えばサンプルの数が
100個あり、そのうちの１個についてのみメッシュ位置
（2,3）にθ＝０の特徴点が現れた場合、θ＝０の方向
コードにおけるメッシュ領域のメッシュ位置に出現回数
（出現頻度）１が書き込まれる。出現頻度の計算は、特
徴点の位置を特定するＸ座標及びＹ座標と方向コードと
により規定される３次元空間つまりａ×ｂ×ｋ（ｋは方
向コードの数）のメッシュ空間において、あるサンプル
についてメッシュ位置（X₁，Y₁，θ₁）に特徴点が現れ
たとすると、当該メッシュ位置における今までの出現頻
度に１を加えることによって実行される。

例えばパターンが描かれる領域５×５のメッシュ群に
分割し、θを第２図（ａ）のように８つに規定した場
合、５×５×８のメッシュ空間をとる。そしてある特徴
点の位置（メッシュ領域のメッシュに対応する位置）の
Ｘ座標,Y座標が（5,3）、その方向コードがθ＝６であ
る場合には、メッシュ空間上の位置（5,3,6）に対応す
る頻度に１を加えたものとなる。特徴点の位置のＸ座
標,Y座標を（X,Y）、方向コードをθとすれば、メッシ
ュ空間上のメッシュ位置（X,Y,θ）における出現頻度Ｐ
（X,Y,θ）は次式のようにカウントアップされる。

Ｐ（X,Y,θ）＝Ｐ（X,Y,θ）＋１ ただしＰ（X,Y,θ）の初期値は０である。

こうして前記メッシュ空間の各メッシュ位置毎に特徴
点の出現頻度を求め、出現頻度分布を作成する。第４図
は、作成された出現頻度分布の一例を示す分布図であ
る。

こうして求めた特徴点出現頻度分布は、特徴点がどの
様な位置に出現し、どの様な方向性を持っているかとい
う傾向を示している。つまり、同一の文字、または、図
形に対して、複数のサンプルによる頻度分布を取ると、
似通った位置と似通った方向性を持って特徴点が出現し
やすく、その付近にピークが存在することが多いことを
示している。

本発明は、この考え方をファジイ集合におけるメンバ
ーシップ値の設定に応用したものである。

ファジイ集合におけるメンバーシップ値は、あいまい
な尺度のものを［0,1］区間の実数領域における主観的
な量として表現したものである。

メンバーシップ値の定義は、［0,1］区間の実数領域
をヒントに、また、特徴点が頻度分布のピーク値周辺に
現れやすいことをヒントにしている。

つまり、頻度分布は出現しやすい位置と方向性を、特
徴点の評価に反映した指標となりうるため、０〜１の実
数区間で正規化すればそのままメンバーシップ値として
用いることができることになる。本発明ではこのように
して正規化した特徴点頻度分布をファジイ辞書としてパ
ターン毎に辞書記憶部に登録しておく。またこの辞書記
憶部には、パターン毎に特徴点の基準個数ｊを登録して
おく。この基準個数ｊとは、例えば各サンプルにおける
パターンの特徴点の平均個数である。

そして認識対象であるパターンについて特徴点を抽出
し、その特徴点の総数ｍと各特徴点のメッシュ領域にお
けるメッシュ位置（X_i，Y_i，θ_i）（１≦ｉ≦ｍ）とを
求め、 辞書記憶部内にあるパターンPT_kを照合対象として、
これのファジイ辞書の前記メッシュ位置（X_i，Y_i，
θ_i）に対応するメンバーシップ値f_k（X_i，Y_i，θ_i）を
求め、 各メンバーシップ値f_k（X_i，Y_i，θ_i）を確信度1.0か
ら差し引いた値の合計値 と前記特徴点の基準個数ｊと前記特徴点の総数ｍとにも
とづいて、認識対象のパターンと照合対象のパターンPT
_kとの離れている度合いに相当する距離D_kを演算し、 この距離D_kを辞書記憶部内の総てのパターンについて
計算し、そのうちの小さい値から順にパターンを適数選
んで認識結果とする。

ここで前記距離D_kの意味について説明する。今認識対
象であるパターン（入力パターン）の特徴点の総数が
ｍ、各特徴点のメッシュ位置が（X₁，Y₁，θ₁），
（X₂，Y₂，θ₂）……（X_m，Y_m，θ_m）であったとする。
先ず辞書記憶部内に登録されているあるパターンPT_kを
照合対象として、その２次元ファジイ辞書について前記
メッシュ位置（X_i，Y_i，θ_i）（ただし１≦ｉ≦ｍ）に
対応するメンバーシップ値f_k（X_i，Y_i，θ_i）を拾い出
す。このf_k（X_i，Y_i，θ_i）は、（X_i，Y_i，θ_i）に位置
する入力パターンの特徴点がパターンPT_kのひとつの特
徴点であることの確信度を示すものである。そこで本発
明では、例えば確信度1.0からf_k（X_i，Y_i，θ_i）を差し
引いた値を入力パターンの全特徴点数ｍあるいはパター
ンPT_kに係る特徴点の基準個数ｊで割った値を、（X_i，Y
_i，θ_i）に位置する特徴点とパターンPT_kとの距離とい
う概念で捉え、そして入力パターンの全特徴点について
の前記距離の合計値を当該パターンと照合対象であるパ
ターンPT_kとの距離D_kとして捉える。このD_kの演算式の
一例を示すと、ｊとｍとが等しいときには となる。またｊとｍとが異なるときは となる。これらの式をまとめると次式となる。

ただしmax（m.j）はm.jの大きい方の値である。

F.実施例 第５図は辞書記憶部に登録すべきデータを作成するた
めの回路のブロック図である。この例における特徴点出
現頻度分の正規化の方法についてはじめに述べておく
と、全サンプルの特徴点数をＮとしたとき、次式に示す
ようにある一定の割合C_nを乗じたものを基準点までのピ
ーク抽出数ｎとして求める。

ｎ＝C_n・Ｎ 次に、特徴点出現頻度分布において、頻度の大きいも
のから順に捜していき、ｎ番目の頻度の値を取るものを
求め、これを基準点の頻度P_nとする。

P_nをもとに、特徴点頻度分布を次式により正規化す
る。分布上の頻度をＰ、正規化後の頻度をＭとすれば、 Ｍ＝1.0 ……Ｐ≧P_nのとき P/P_n ……Ｐ＜P_nのとき 分布上の全ての頻度について行うことで、正規化した結
果が得られる。

第５図中１は文字や図形等のサンプルパターンであ
り、このサンプルパターン１に対して走査回路２により
走査が行われ、次いでその走査結果に対してノイズ処理
や大きさの正規化といった前処理が前処理回路３により
施される。なお走査回路２はコントローラ６の制御の下
に多数のサンプルについて走査を行う。前処理回路３か
ら出力されたデータは特徴点抽出回路４に入力され、特
徴点抽出回路４は、文字や図形の黒白境界に沿って輪郭
画素群を抽出し、これらを直線近似処理等により情報圧
縮化し、こうして得られた特徴点群を、文字，図形を常
に右側（または左側）に見るようにして輪郭ベクトルと
して結合する。第６図は文字「Ａ」について得られた輪
郭ベクトルを示す図であり、ベクトル群より構成される
閉じた線分を１つの輪郭ベクトル系列と呼ぶならば、こ
の例では２つの輪郭ベクトル系列A₁，A₂を有している。
更に特徴点抽出回路４は、特徴点の位置を正規化すると
共に当該特徴点を始点とする輪郭ベクトルの方向コード
を求め、その結果を特徴点出現頻度分布作成器５に出力
すると共に、特徴点数を特徴点数カウンタ回路７に渡
す。特徴点出現頻度分布作成器５では、特徴点抽出回路
４によって得られる特徴点出現位置及びその方向コード
にもとづき、一時記憶メモリ5₁に記憶された頻度をカウ
ントアップして第７図に示すような特徴点出現頻度分布
を作成する。コントローラ６は、辞書のサンプル数によ
って走査回路２への入力を繰り返し、特徴点出現頻度分
布の作成処理をコントロールすると共に、作成処理終了
後基準頻度検出回路８に処理を進める。基準頻度検出回
路８では、特徴点数カウンタ回路７から得られる全特徴
点数（出現頻度の合計値）とコントローラ６から与えら
れる設定値により、基準頻度を求めるためのピーク数を
決定し、そのピーク数をもとに一時記憶メモリ5₁に記憶
されている特徴点出現頻度分布からピーク頻度を順次大
きいものから読み出すとともに、与えられたピーク数に
達した頻度を基準頻度として検出する。基準頻度検出回
路８における処理が終了したのち、特徴点出現頻度分布
正規化回路は、一時記憶メモリ5₁に記憶されている特徴
点出現頻度分布を基準頻度検出回路８で検出された基準
頻度を用いて第８図に示すように正規化された頻度分布
をメンバーシップ値としてファジイ辞書10に記憶する。

以上において特徴点数カウンタ回路７にて求める全特
徴点数としては、方向コードθ＝０〜８毎に特徴点数を
合計した値であってもよいし、あるいは各合計値を合計
した値であってもよく、前者の場合全特徴点数が方向コ
ード毎に独立した値となる。

次に認識対象であるパターンを入力して、辞書記憶部
内のパターン群と照合する手段の一例について述べる。
第９図中辞書記憶部11内にはパターン毎にファジイ辞書
と特徴点の基準個数ｊとが登録されている。特徴点の基
準個数ｊは、例えばファジイ辞書を作成するときに用い
たパターンのサンプルの特徴点の平均個数である。

先ずパターン入力部12にてパターンを入力し、特徴点
個数加算部13により当該パターンの特徴点の総数（全特
徴点数）ｍを求める。続いてメンバーシップ値加算部14
により辞書記憶部１内のあるパターンPT_kについて、パ
ターン入力部12に入力したパターン（認識対象のパター
ン）の特徴点のメッシュ位置（X_i，Y_i，θ_i）（１≦ｉ
≦ｍ）に対応するメンバーシップ値f_k（X_i，Y_i，θ_i）
を求め、これらf_k（X_i，Y_i，θ_i）の総てを加算し、そ
の加算値 を距離演算部15に出力する。そして最大値検出部16によ
りj,mのうちの大きい方max（j.m）を出力し、距離演算
部15にて先述した（１）式の演算を実行して距離D_kを求
める。こうした試行を登録されているすべてのパターン
について行い、近距離判定部17にてD_kの小さい順にｌ個
のパターンを取り出し、これを認識結果として認識結果
出力部18より出力する。

G.発明の効果 本発明によれば、文字や図形等のパターンの特徴点の
出現頻度分布を、多数のサンプルを用意することにより
作成し、この出現頻度分布の各頻度を正規化して、その
値をメンバーシップ値として登録するようにしているた
め、辞書を自動的に作成することができると共に辞書登
録のためのマニュアル作業が大幅に低減し、また入力パ
ターンの位置や傾きにばらつきがあっても認識の誤りが
生じにくい。

しかも特徴点の位置的特徴に加えて方向特徴の考え方
を導入したものであるため、ａ×ｂ×ｋのメッシュ空間
で辞書を構成することからメッシュのとり方によっては
大きな辞書構成となるが、実際には方向的特徴を加えた
ことで、a,bのメッシュのとり方は可成り粗くとっても
問題なく、英数字で５×５×８メッシュ，漢字でも15×
15×８メッシュ程度で十分である。この場合漢字１文字
当たり15×15×８×４ビット＝900バイトとなり、従来
の技術における2Kバイトと比較して1/2程度以下であ
る。従って辞書の記憶容量の低減化を図ることができ
る。

また入力パターンを認識するにあたっては、入力パタ
ーンの特徴点のメッシュ位置に対応するメンバーシップ
値を辞書より求めるだけで確信度が得られ、その確信度
を確信度1.0から差し引いた値を特徴点個々の照合対象
であるパターンとの距離として捉え、この距離を用いて
例えば（１）式により２つのパターンの距離D_kを演算
し、その値が小さい程パターンのマッチングの程度が高
いとして認識しているため、演算が簡単であって、高速
なパターン認識を実現できる。そして辞書そのものにあ
いまい性があるので、位置ずれに極めて強い特性があ
る。

【図面の簡単な説明】

第１図は本発明装置のフローを示すフローチャート図、
第２図は方向コードを示す説明図、第３図は特徴点のあ
いまい性を示す説明図、第４図は特徴点出現頻度分布
図、第５図は本発明の実施例の一部に係る回路のブロッ
ク図、第６図は輪郭ベクトル系列を示す説明図、第７
図，第８図は夫々正規化前後の特徴点出現頻度分布図、
第９図は本発明の実施例の一部に係る回路のブロック図
である。 １…パターン、２…走査回路、４…特徴点抽出回路、５
…特徴点出現頻度分布作成器、８…基準頻度検出回路、
９…特徴点出現頻度分布正規化回路、11…辞書記憶部、
13…特徴点個数加算部、14…メンバーシップ値加算部、
15…距離演算部。

フロントページの続き (56)参考文献 特開 平３−3091（ＪＰ，Ａ) 特開 平３−3089（ＪＰ，Ａ) 特開 平１−290090（ＪＰ，Ａ) 特開 昭63−108480（ＪＰ，Ａ) 特開 昭62−192886（ＪＰ，Ａ) 特開 昭64−15885（ＪＰ，Ａ) 特許2643293（ＪＰ，Ｂ２) 特許2643294（ＪＰ，Ｂ２) 特公 平７−104938（ＪＰ，Ｂ２) (58)調査した分野(Int.Cl.⁶，ＤＢ名) G06K 9/68 G06K 9/62 特許ファイル（ＰＡＴＯＬＩＳ) ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】文字や図形等のパターンを照合の対象とな
   る辞書を用いて認識する装置において、 あるパターンに対する多数のサンプルを作成し、各サン
   プルにおけるパターンについて特徴点群P₁，P₂…P_N（Ｎ
   は整数）を抽出するとともに、隣接する特徴点P_i，P_i+i
   （ｉ≧１）を結ぶ線分の方向を量子化してその値を特徴
   点P_iの方向コードとして求める特徴点抽出回路と、 パターンが描かれる平面領域に横縦ａ×ｂ（a,bは整
   数）個のメッシュ領域を割り当てるとともに、メッシュ
   領域の横方向、縦方向の座標をメッシュに対応させて
   （Ｘ（１≦Ｘ≦ａ）,Y（１≦Ｙ≦ｂ））とし、また方向
   コードの数及び値をそれぞれk,θとし、 メモリにａ×ｂ×ｋのメッシュ空間に対応する領域を設
   定するとともに、当該メッシュ空間におけるメッシュ位
   置を（X,Y,θ）とし、前記特徴点抽出回路から出力され
   た特徴点をX,Y,θにより特定してその特徴点の出現をメ
   ッシュ位置（X,Y,θ）における出現とし、 各メッシュ位置毎に特徴点の出現回数である出現頻度
   を、前記特徴点抽出回路の出力から求めて出現頻度分布
   を作成するとともに、作成された出現頻度分布を前記メ
   モリに記憶させる特徴点出現頻度分布作成器と、 前記メモリに記憶されている出現頻度分布を、前記特徴
   点抽出回路から得られた特徴点と設定値とにより求めた
   基準頻度から正規化する特徴点出現頻度分布正規化回路
   と、 この特徴点出現頻度分布正規化回路により正規化された
   出現頻度分布をメンバーシップ値として自動的に登録す
   るファジイ辞書と、 このファジイ辞書として特徴点の基準個数ｊと共に予め
   パターン毎に登録され、パターンが描かれる平面領域に
   メッシュ領域を割り当てるとともに、これに対応してメ
   ッシュ領域が設定された辞書記憶部と、 パターン入力部に入力された認識対象パターンの特徴点
   の個数を加算して総数ｍを求める特徴点個数加算部と、 前記辞書記憶部内の、あるパターンについて、前記パタ
   ーン入力部に入力されたパターンの特徴点のメッシュ位
   置に対応するメンバーシップ値f_Kを求め、これらf_Kを総
   てを加算した加算値を求めるメンバーシップ値加算部
   と、 メンバーシップ値加算部で求められた加算値と、前記基
   準個数ｊと総数ｍのうち最大値検出部で得た大きい方の
   出力とが供給され、両者から下記式の演算を実行して認
   識対象パターンと照合対象パターンとの離れている度合
   いに相当する距離D_Kを求める距離演算部と、 この距離演算部で演算された距離D_Kを前記辞書記憶部内
   に登録されている総てのパターンについて演算し、その
   うちの小さい値から順にパターンを適数選んで認識結果
   として取り出す近距離判定部とを備えたことを特徴とす
   るパターン認識装置。 ただしmax（m.j）はm,jの大きい方の値