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

Abstract

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

Description

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具体的には本発明は、あるパターンに対して多数のサン
プルを作成し、各サンプルにおけるパターンの特徴点を
抽出し、 パターンが描かれる平面領域にａ×ｂ個（ａ。

ｂは整数）のメツシュ領域を割り当てると共に、これに
対応して辞書記憶部内にメツシュ領域を設定し、このメ
ツシュ領域内の各メツシュ毎に前記特徴点の出現回数で
ある出現頻度を求めて、メツシュ領域に対応する出現頻
度分布を作成し、前記出現頻度分布上の各頻度を基準頻
度を用いることにより正規化してこの正規化した値をメ
ンバーシップ値とし、このメンバーシップ値にもとづい
て、辞書記憶部内のメツシュ領域の各メツシュにメンバ
ーシップ値を割り当てて２次元ファジィ辞書を作成し、
こうして得られる２次元ファジィ辞書を特徴点の基準個
数ｊと共に予めパターン毎に辞書記憶部内に登録してお
き、 認識対象であるパターンについて特徴点を抽出し、その
特徴点の総数ｍと各特徴点のメツシュ領域におけるメツ
シュ位置（ｘｌ、ｙ、）（１≦ｉ≦ｍ）とを求め、 辞書記憶部内のあるパターンＰ　Ｔ　ｈを照合対象とし
て、これの２次元ファジィ辞書の前記メツシュ位置（ｘ
ｌ、ｙＩ）に対応するメンバーシップ値ｒ　ｋ（ｘ　ｒ
、　ｙ　１）を求め、 各メンバーシップ値ｆ　ｋ（ｘ　ｒ、　ｙ　１）を確信
度ｒｋｃｘ、、　ｙｔ）　）と前記特徴点の基準個数」
と前記特徴点の総数ｍとにもとづいて、認識対象のパタ
ーンと照合対象のパターンＰＴｋとの離れている度合い
に相当する距離Ｄｋを演算し、この距離Ｄｋを辞書記憶
部内の総てのパターンについて計算し、そのうちの小さ
い値から順にパターンを適数選んで認識結果とすること
を特徴とする。

ここで前記距離Ｄｋの意味について説明する。

今認識対象であるパターン（人カバターン）の特徴点の
総数がｍ、各特徴点のメツシュ位置が（ｘｌ、　ｙＩ）
　、　Ｃｘｔ、　ｙｔ）・・・・・・（ｘａ、ｙａ）で
あったとする。先ず辞書記憶部内に登録されているある
パターンＰＴｋを照合対象として、その２次元ファジィ
辞書について前記メツシュ位置（ｘｔ、ｙａ　（ただし
■≦ｉ≦ｍ）に対応するメンバーシップ値ｆｈ（ｘｔ、
ｙＩ）を拾い出す。このｆｈ（ｘｌ、ｙｉ）は、（ｘｔ
、ｙＩ）に位置する人カバターンの特徴点がパターンＰ
Ｔｋのひとつの特徴点であることの確信度を示すもので
ある。そこで本発明では、例えば確信度！、０からｆｈ
（ｘｉ。

ｙｌ）を差し引いた値を人カバターンの全特徴点数ｍあ
るいはパターンＰＴ、に係る特徴点の基準個数ｊで割っ
た値を、（ｘ　ｌ、　ｙ　ｔ）に位置する特徴点とパタ
ーンＰＴ、との距離という概念で捉え、そして人カバタ
ーンの全特徴点についての前記距離の合計値を当該パタ
ーンと照合対象であるパターンＰＴ、との距離Ｄｋとし
て捉える。このＤｋの演算式の一例を示すと、ｊとｍが
等しいときには Ｄｈ＝Σ（１，Ｏｆｋ（ｘｔ、　ｙ□）　）／ｍ１＝１ となる。また」と【ｎとが５′４なるときはｊ＞ｍで、 １）ｈ　＝　（Σ（１，Ｏｆｋ（ｘｌ、ｙＩ））　＋（
ｊ　　ｍ））／ｊｒｎ　＞　ｊで １）ｋ−Σ（１，０−ｆｋ（ｘｌ、ｙＩ））／ｍとなる
。これらの式をまとめると次式となる。

Ｄｈ−（ｗａｘ（ａ、ｊ）−Σ　ｆｈ（Ｘ＋、ｙａ）　
／ｍａｘ（ａ＋、ｊ）　　−（１）ｉ−ま ただしＩｌａｘ（ｍ、Ｄはｍ、ｊの大きい方の値である
。

Ｆ　、実施例 本発明方法の具体的手順を以下に説明する。

（１）辞書作成部端 辞書を作成するため、同一の文字、または、図杉に対し
て複数のサンプルを檗備する。

それらはあるひとつの辞書を作成するときの辞書作成用
パターンとなる。

（２）特徴点出現頻度分布（２次元ヒストグラム）の作
成 サンプルを繰り返し人力して、それぞれ特徴点を抽出す
る。一方、パターンが描かれる平面領域にａ×ｂ個（ａ
、ｂは整数）のメツシュ領域を割り当てると共に、これ
に対応して辞書記憶部内にメツシュ領域を設定する。そ
してこのメツシュ領域内の各メツシュ毎に前記特徴点の
出現回数である出現頻度を求めて、第１図に示すように
メツシュ領域に対応する出現頻度分布を作成する。

例えば、パターンが描かれる平面領域にｌ０Ｘ１０のメ
ツシュ領域を割り当てたとき、辞書記憶部内にも１０ｘ
ｌＯのメツシュ領域を設定する。

このとき、ある特徴点の位置がｚ（ｘ、ｙ）−（５゜３
）と得られた場合には、ヒストグラム上の位置Ｚ（５，
３）の頻度に１を加えたものとなる。

特徴点位置をｚ　（ｘ、ｙ）とすれば、２次元ヒストグ
ラム上で対応する位置Ｚ（ｘ、ｙ）における頻度Ｐ（ｘ
、ｙ）は、次式で示される。

Ｐ　（ｘ、ｙ）　−Ｐ　（ｘ、ｙ）＋　１（Ｐ（ｘ、ｙ
）の初期値０） （３）２次元ファジィ集合におけるメンバーシップ値の
定義と辞書の作成 上で求めた特徴点出現頻度分布は、特徴点がどの様な位
置に出現しゃすいかという傾向を示している。つまり、
同一の文字、または、図形に対して、複数のサンプルに
よる頻度分布を取ると、似通った位置に特徴点が出現し
ゃすく、その付近にピークが存在することが多いことを
示している。

このことから逆に、ピーク位置を抽出することで特徴点
位置を推定することができる。

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

さて、頻度分布は、ひとつのパターンに対するサンプル
数が多ければ多いほど、全体の頻度が高くなり、客観的
な判断をすることがむずかしくなるため、頻度分布の正
規化が必要である。

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

メンバーシップ値の定義は、［０，Ｉ］区間の実数領域
をヒントに、また、特徴点が頻度分布のピークに対応す
る場合が多いことをヒントにしている。

つまり、頻度分布のピーク値は特徴点位置というあいま
いな尺度を示す指標となりうるため、０〜１の実数区間
で正規化すればそのまま２次元のファジィ集合に関する
メンバーシップ値として用いることができることになる
。

そこで、特徴点出現頻度の正規化と辞書記憶部への登録
を次のように行う。

全サンプルの特徴点数をＫとしたとき、ある−定の割合
Ｃｋを乗じたものを基準点までのピーク数にとして求め
る。

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

Ｐｋをもとに、特徴点頻度分布を次式により正規化を行
う。

分布上の頻度をＰ１正規化後の頻度をＭとすれば、 Ｍ＝１．０　　　　・・・・・・Ｐ≧Ｐ、のときＰ／Ｐ
ｋ　　　・・・・−・Ｐ＜Ｐｋのとき分布上の全ての頻
度について行うことで、正規化した結果が得られる。こ
の結果は、０〜１区間にあり、２次元ファジィ辞書とし
て辞書記憶部に登録する。

以上で、ひとつのパターンに対する辞書作成手続きが終
了する。

このようにして得られた２次元ファジィ辞書の一例を図
示すると、第３図は文字ｒＡＪの特徴点頻度分布を示す
図、第４図は第３図に示す分布を正規化したものを示す
図であり、この例ではある領域に９×９のメツシュ領域
をとっている。ここで特徴点とは、例えば黒画素に接す
る白画素を輪郭画素として抜き出し、これらを直線近似
処理等を行って情報圧縮化し、こうして得られた輪郭画
素に相当するものである。

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

先ずパターン人力部２にてパターンを人力し、特徴点個
数加算部３により当該パターンの特徴点の総数（全特徴
点数）ｍを求める。続いてメンバーシップ値加算部４に
より辞書記憶部ｌ内のあるパターンＰＴ、について、パ
ターン入力部２に入力したパターン（認識対象のパター
ン）の特徴点のメッンユ位置（ｘ、、ｙＩ）（１５１６
ｍ）に対応するメンバーシップ値ｆ　−（ｘ　ｉ、　ｙ
　１）　’ｆｔ求メ、これらｆｍ（ｘ＋、Ｙｉ）の総て
を加算し、そのる。そして最大値検出部６によりｊｌｍ
のうちの大きい方５ａｘ（ｊ、ｓ）を出力し、距＃１演
算部５にて先述した（１）式の演算を実行して距＃Ｄ、
を求める。

こうした試行を登録されているすべてのパターンについ
て行い、近距離判定部７にてＤｋの小さい順に２個のパ
ターンを取り出し、これを認識結果として認識結果出力
部８より出力する。

以上において、２次元ファジィ辞書としては、第３図に
示す出現頻度分布を正規化して得られた第４図に示すメ
ンバーシップ値の配列をそのまま用いてもよいが、次の
ような処理を施して得られたものを用いてらよい。

先ず各メツシュの出現頻度のうち最大値をとるメツシュ
を第１の領域の探索開始点として予め定めた規則に従い
第１の領域に含まれるメッ７ュを探索し、次いで第１の
領域以外のメツシュの中から出現頻度の最大値をとるメ
ツシュを第２の領域の探索開始点として、同様に第２の
領域に含まれるメツシュを探索し、こうした処理を繰り
返すことにより前記メツシュ領域を１以上の領域に分離
する。一方出現頻度を正規化するために例えば出現頻度
の総数にもとづいて基準頻度を求める。

続いて分離領域毎にその分離領域のみを含む前記メツシ
ュ領域について各出現頻度を基準頻度を用いて正規化し
てメンバーシップ値を求め、その後当該メツシュ領域の
各メッツュの１行づつについてその行に含まれるメンバ
ーシップ値の中から最大値を求めると共に、１列づつに
ついてその列に含まれるメンバーシップ値の中から最大
値を求め、これら最大値を分離領域毎に組にして第６図
に示すような！次元ファジィ辞書を作成する。

次いでメツシュ領域の端からｉ番目のメツシュ列にＸ座
標ｘｌを、端からｊ番目の行にＹ座標ｙ。

を夫々割り当てると共に、分離領域毎に作成した１次元
ファジィ辞書について、Ｘ　ｈ　＋　３’　Ｊに夫々対
応するメンバーシップ値をＸ（ｉ）、Ｙ（ｊ）と表示し
たとき、分離領域毎に（ｘ　ｉ、　ｙ　Ｊ）のメツシュ
位置における２次元のメンバーシップ値ｒ（ｉ、ｊ）に
対してＸ（ｉ）、Ｙ（ｊ）のうちの小さい方の値を割り
当てて、分離領域に対する２次元のメンバーシップ値の
集合を得る。

次いでメツシュ位置（ｘ　ｉ、　ｙ　、１）におけるメ
ンバーシップ値Ｆ（ｉ、ｊ）に対して、各分離領域のｆ
（ｉ、ｊ）のうちの最大値を割り当て、このＦ（ｉ、ｊ
）の集合によって第７図に示すように各分離領域の全領
域に対する２次元ファジィ辞書を得る。

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

更に辞書空間としては、表示のための文字フォントの１
．２倍〜１．５倍程度のメツシュ空間があれば十分認識
できる。例えば英数字の場合９×９程度、複雑な漢字の
場合３２Ｘ３２程度のメツシュ空間で済む。そして例え
ばメンバーシップ値を、０〜ｌまでを０．！で刻んだ値
により表現した場合、データ表現としてはθ〜ｌＯの整
数で持てばよいから４ビツトで構成することができる。

従ってメモリ量としては漢字ｉ文字当たり３２Ｘ３２×
４ビット−５１２バイトとなり、従来必要であった２に
バイトと比較してＩ／４程度で済み、記憶容量の低減化
を図ることができる。

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

【図面の簡単な説明】

第１図は特徴点出現頻度を示す概念図、第２図は特徴点
のあいまい性を示す説明図、第３図は特徴点出現頻度分
布を示すデータ図、第４図は正規化後の特徴点出現頻度
分布を示すデータ図、第５図は本発明の実施例を実行す
る回路のブロック図、第６図は１次元ファジィ辞書のデ
ータ図、第７図は２次元ファジィ辞書のデータ図である
。 １・・・辞書記憶部、３・・・特徴点個数加算部、４・
・・メンバーシップ値加算部、５・・・距離演算部。 第２図 特徴点のあいまい性の説明図 第１図 ｅｆ散点出現頑度今布印 第３図 特徴点出現頻度分布図 第４図 ２次元ファジィ辞書のデータ×

Claims (1)

【特許請求の範囲】
1. （１）文字や図形等のパターンを、照合対象となる辞書
   を用いて認識する方法において、あるパターンに対して
   多数のサンプルを作成し、各サンプルにおけるパターン
   の特徴点を抽出し、パターンが描かれる平面領域にａ×
   ｂ個（ａ、ｂは整数）のメッシュ領域を割り当てると共
   に、これに対応して辞書記憶部内にメッシュ領域を設定
   し、このメッシュ領域内の各メッシュ毎に前記特徴点の
   出現回数である出現頻度を求めて、メッシュ領域に対応
   する出現頻度分布を作成し、前記出現頻度分布上の各頻
   度を基準頻度を用いることにより正規化してこの正規化
   した値をメンバーシップ値とし、このメンバーシップ値
   にもとづいて、辞書記憶部内のメッシュ領域の各メッシ
   ュにメンバーシップ値を割り当てて２次元ファジィ辞書
   を作成し、こうして得られる２次元ファジィ辞書を特徴
   点の基準個数ｊと共に予めパターン毎に辞書記憶部内に
   登録しておき、 認識対象であるパターンについて特徴点を抽出し、その
   特徴点の総数ｍと各特徴点のメッシュ領域におけるメッ
   シュ位置（ｘ＿１、ｙ＿１）（１≦ｉ≦ｍ）とを求め、 辞書記憶部内のあるパターンＰＴ＿ｋを照合対象として
   、これの２次元ファジィ辞書の前記メッシュ位置（ｘ＿
   １、ｙ＿１）に対応するメンバーシップ値ｆ＿ｋ（ｘ＿
   １、ｙ＿１）を求め、 各メンバーシップ値ｆ＿ｋ（ｘ＿１、ｙ＿１）を確信度
   １．０から差し引いた値の合計値Σ（１．０−ｉ＝１ ｆ＿ｋ（ｘ＿１、ｙ＿１）と前記特徴点の基準個数ｊと
   前記特徴点の総数ｍとにもとづいて、認識対象のパター
   ンと照合対象のパターンＰＴ＿ｋとの離れている度合い
   に相当する距離Ｄ＿ｋを演算し、 この距離Ｄ＿ｋを辞書記憶部内の総てのパターンについ
   て計算し、そのうちの小さい値から順にパターンを適数
   選んで認識結果とすることを特徴とするパターン認識方
   法。