JPH0740287B2 - パターン認識方法 - Google Patents

Description

【発明の詳細な説明】 〔技術分野〕 本発明は文字などのパターンの認識方法に関し、さらに
詳細には、多層方向ヒストグラム法によるパターン認識
方法に関する。

〔従来技術〕

本出願人は、特願昭第59−202822号、特願昭第58−2028
25号などによって、多層方向ヒストグラム法によるパタ
ーン認識方法を既に提案している。本発明は、このよう
なパターン認識方法の改良に関するものである。

この多層方向ヒストグラム法によるパターン認識方法に
おいては、文字などのパターンの輪郭画素に方向コード
を付け、そのパターンの枠の各辺から対向する辺に向か
ってパターンを走査して白画素（背景）の次に出現する
方向コードを検出し、その方向コードをそれが走査線上
で何番目に検出されたかによって複数の層に層別する。
そして、パターンの枠内の分割領域毎に、ある層までの
層の方向コードのヒストグラムを求め、それぞれのヒス
トグラム成分（特徴量）としたベクトルを、パターンの
特徴ベクトルとして用いる。

例えば、方向コードとして８種類のコードを付け、パタ
ーン枠内４×４のメッシュ領域に分割し、第１層および
第２層の方向コードまでを対象とすると、特徴ベクトル
の次元数は256（＝４×４×２×８）となる。

辞書に関しては、同一パターンとしての複数のパターン
から同様の特徴ベクトルを抽出し、その平均を辞書パタ
ーン（標準パターン）の特徴ベクトルとして登録する。

また、本出願人は、層別のための走査方向も加味してさ
らに詳細に方向コードを層別する同様のパターン認識方
法に既に提案している。本発明は、このパターン認識方
法にも同様に適用できるものである。

さらに、パターン枠内の領域分割の方法は、前記先願の
明細書および図面に開示した方法に限らない。例えば、
前記先願のパターン認識方法と同様に、方向コードが均
等に分配されるようにパターン枠内をメッシュ分割し、
そのメッシュ領域を予め設定されたパラメータに従って
部分的に重ね合わせて、少ない領域に統合するような方
法を採用してもよい。このような領域分割方法を採用し
た多層方向ヒストグラム法によるパターン認識方法は、
本出願人により提案済みであるが、このようなパターン
認識方法にも、本発明は同様に適用し得るものである。

さて、このような多層方向ヒストグラム法によるパター
ン認識方法においては、未知パターンから抽出された特
徴ベクトルと、辞書パターンの特徴ベクトルとの対応次
元成分の距離または類似度の演算によって未知パターン
と辞書パターンとのマッチングを行い、距離の総和が最
小の辞書パターンまたは類似度の総和が最大の辞書パタ
ーンを認識結果とする。

しかし、前記のように特徴ベクトルの次元数が大きくな
ると、距離または類似度の演算量が多く、マッチング時
間が長くなり、また辞書容量が大きくなるという問題が
あった。

〔目 的〕

したがって本発明の目的は、多層方向ヒストグラム法に
よるパターン認識方法において、マッチングの効率化お
よび辞書容量の削除を図ることにある。

〔構 成〕

多層方向ヒストグラム法による特徴ベクトルは、パター
ン識別効果の大きい次元の成分と、その効果がそれほど
顕著でない次元の成分とがある。これに関し、説明を簡
単にするために、２次元の特徴ベクトルを考える。

次元数を２として多層方向ヒストグラム法による辞書を
作成した場合、“文",“字",“認",“識”のそれぞれの
辞書パターンの特徴ベクトルは、それぞれ第５図のg₁,g
₂,g₃,g₄のようになる。この例では、図から明らかなよ
うに、各特徴ベクトルは成分（特徴量）Ａのほうが、成
分（特徴量）Ｂよりも分散（または標準偏差）が大き
い。換言すれば、成分Ａのほうが、未知パターンに対す
る識別能力が高い。

未知パターンと辞書パターンとのマッチングは、基本的
には、未知パターンと辞書パターンの特徴ベクトルの対
応次元成分の距離または類似度を求め、その距離の総和
が最小または類似度の総和が最大の辞書パターンを認識
結果とするものである。こゝで、前記のような特徴ベク
トルの性質に着目すれば、パターン識別能力の高い部分
から優先的に距離または類似度を演算することにより、
パターン識別能力の高い一部の成分について距離または
類似度を演算した段階で、候補となり得ない辞書パター
ンを排除し、候補となり得る辞書パターンを早い段階で
絞り込むことができるであろう。

また、多層方向ヒストグラム法による特徴ベクトルは、
その各次元成分の順番を入れ替えてもパターンの特徴は
保存されるという性質がある。

以上のような点に着目し、本発明にあっては、辞書作成
に際し、辞書パターンの特徴ベクトルの各次元毎の標準
偏差または分散を求め、各辞書パターンの特徴ベクトル
の成分を標準値または分散の大きい順に並べ替え、その
ような並べ替え後の特徴ベクトルを辞書に登録してお
く。

例えば、多層方向ヒストグラム法により作成されたある
辞書パターンの特徴ベクトルが第６図の（ａ）に示すよ
うであったとする。そして、全標準パターンについて計
算された標準偏差または分散の大きい順がX₄,X₁,X₃,X₇,
X₅,X₂,X₈,X₆,…であるとする。そうすると、この特徴ベ
クトルは、その各次元X₁,X₂,X₃,…の成分が第６図の
（ｂ）に示すように並べ替えられて辞書に登録される。
つまり、元の特徴ベクトルの次元X₄の成分が並べ替え後
の特徴ベクトルの最上位の次元Y₁の成分、次元X₁の成分
が次位の次元Y₂の成分、というように並べ替えられる。

そして、未知パターンから抽出された特徴ベクトルを、
辞書パターンの特徴ベクトルの成分の並べ替え順に従っ
て成分の並べ替えをおこなったのち、辞書パターンの特
徴ベクトルの対応次元成分との距離または類似度の演算
を行うことにより、未知パターンと辞書パターンとのマ
ッチングを行う。

こゝで、手書き漢字など多くの種類のあるパターンの認
識の場合は、次元数の多い特徴ベクトルを用いて詳細マ
ッチングを行う必要がある。しかし、ANSK文字のように
種類の少ない文字のようなパターンの認識を対象とした
場合、前記のように標準パターン偏差または分散の大き
い順つまりパターン識別能力の高い順に辞書パターンお
よび未知パターンの成分を並べ替えれば、その上位の比
較的少ない次元数（ANSK文字の場合、例えば20次元、24
次元など）だけのマッチングで十分な認識率を達成でき
ることが確認できた。

この点に着目し、本発明にあってはさらに、前記のよう
に次元並べ替え後の辞書パターンの特徴ベクトルの上位
Ｎ次元だけを残し、下位の次元をすてたベクトルを、最
終的に辞書パターンの特徴ベクトルとして辞書に登録す
ることにより、辞書容量の削除とマッチング効率の一層
の向上を達成する。

〔実施例〕

以下、本発明の実施例について図面を参照し説明する。

第１図は、本発明の一実施例の機能的構成を簡略化して
示す概要ブロック図である。なお、この実施例において
は、認識対象のパターンとしてANSKの文字のような比較
的種類の少ない文字パターンを想定している。

図において、10は原稿から文字パターンを読み取り、文
字パターン情報を前処理部12に入力するパターン読み取
り部である。前処理部12は、入力文字パターンの文字切
り出し、正規化などの前処理を行い、処理後の文字パタ
ーンを１字毎に特徴抽出部14に入力する部分である。

特徴抽出部14は、入力文字パターンから前記多層方向ヒ
ストグラム法により特徴ベクトルを抽出する部分であ
る。

こゝで、この実施例においては、動作モードとして辞書
作成モードとパターン認識モードとがある。まず、辞書
作成モードの場合について以下に説明する。また、この
モードにおける辞書作成処理の概略フローチャートを第
２図に示し、以下の説明において対応するステップ番号
を（ ）内に示す。

辞書作成のためには、各文字種について、Ｍ個の文字パ
ターンがパターン読み取り部10より順次入力される（ス
テップ102）。その入力文字パターンは前処理部12で前
処理を受け（ステップ102）、特徴抽出部14に入力され
て多層方向ヒストグラム法による特徴ベクトル（例えば
256次元のベクトル）を抽出される（ステップ104）。抽
出された特徴ベクトルは並べ替え部16に入力される。

18は並べ替え部16によって参照される並べ替えテーブル
部であり、これには予め作成された並べ替えテーブルが
登録されている。

この並べ替えテーブルは次のようにして作成される。各
文字種について、複数の文字パターンから多層方向ヒス
トグラム法により特徴ベクトル（例えば256次元のベク
トル）を抽出し、その平均を、その文字種の標準パター
ンの特徴ベクトルとする。このようにして得た前文字種
（全体でＫ種）の標準パターンの特徴ベクトルの各次元
ｎ毎の標準偏差δ_knは次式 により計算する。こゝで、ｋは文字種の番号であり、g
_knは文字種ｋの次元ｎの成分（特徴量）であり、また
_knは次元ｎの成分の全文字種の平均である。

なお、標準偏差の代わりに、その平方である分散を求め
てもよい。

そのようにして計算した標準偏差または分散の大きい順
に次元番号を並べ、その次元番号と対応する元の次元番
号との対応テーブルを、上位のＮ次元まで作る。この対
応テーブルが前記並べ替えテーブルである。

辞書作成モードの説明に戻る。並べ替え部16において、
入力文字パターンから抽出された特徴ベクトルg_knmは各
次元成分が並べ替えテーブル部18の並べ替えテーブルに
従って並べ替えられ、並べ替え後の上位Ｎ次元の成分か
らなる特徴ベクトルg_knが辞書作成部20に入力される
（ステップ106）。

このようにして、同一文字織のＭ個の文字パターンに対
する次元並べ替え後のＮ次元の特徴ベクトルが辞書作成
部20に蓄積されると、辞書作成部20は、そのＭ個の特徴
ベクトルの平均を求め、それを文字種ｋの辞書パターン
の特徴ベクトル（Ｎ次元ベクトル_knとして、文字コー
ドを付加し辞書22に登録する（ステップ108）。

次に、文字種番号ｋが更新され（ステップ110）、ステ
ップ100に戻り、次の文字種について同様の辞書作成処
理が実行される。

最後の文字種（ｋ＝ｋ）まで処理が実行されると、ステ
ップ112により処理終了と判断され、処理を完了する。

つぎに、パターン認識モードの場合について以下に説明
する。また、このモードにおける処理の概略フローチャ
ートを第３図に示し、以下の説明において対応するステ
ップ番号を（ ）内に示す。

認識対象の文字パターン（未知文字パターン）はパター
ン読み取り部10から入力され（ステップ200）、前処理
部12により前処理を受け（ステップ202）、特徴抽出部1
4に入力され、そこで多層方向ヒストグラム法により特
徴ベクトルX_n（例えば256次元ベクトル）を抽出される
（ステップ204）。

この特徴ベクトルX_nは並べ替え部16に入力され、並べ替
えテーブルに従って標準偏差または分散の大きい順に成
分が並べ替えられ、その上位Ｎ次元の成分からなる特徴
ベクトルY_nに変換された後、マッチング部４に送られる
（ステップ206）。

マッチング部24においては、つぎのようにして未知入力
パターンと辞書パターンとのマッチングが行われる（ス
テップ208）。

それぞれの文字種ｋの辞書パターンの特徴ベクトル_kn
と未知文字パターンの特徴ベクトルY_nとの距離Dkを次式 によって計算する。そして、その距離のソートを行い、
距離が最小の辞書パターンを候補文字として決定する。

この候補文字の文字コードは、未知文字パターンに対す
る認識結果として出力される（ステップ210）。

このように、この実施例では、辞書パターンの特徴ベク
トルは標準偏差または分散の大きい順つまりパターン識
別能力の高い順に成分が並べ替えられ、かつ上位Ｎ次元
以外の、パターン識別能力の低い成分を捨てた形で辞書
に登録されており、また未知入力パターンの特徴ベクト
ルは辞書パターンと同じ順に成分が並べ替えられ、辞書
パターンと未知文字パターンとのマッチングは、Ｎ次元
のベクトル間の距離または類似度に演算によって行われ
る。

したがって、距離または類似度の演算量が少なく高いマ
ッチング効率を達成でき、しかも、パターン識別能力の
高い次元を利用しているため十分な識別率を達成でき
る。さらに、次元数の減少により、辞書容量の大幅な削
除を達成できる。

次に、本発明の他の実施例について説明する。この実施
例の全体的な機能的構成は前記実施例と同様であり、マ
ッチング部24におけるマッチングが一部相違するだけで
ある。そこで、そのマッチング部24の処理についてだ
け、第４図のフローチャートを参照し、説明する。

成分の並べ替え後の未知文字パターンのＮ次元特徴ベク
トルがマッチングに入力されると、文字種つまり辞書パ
ターンの番号が１にセットされ（ステップ300）、その
辞書パターンと未知文字パターンとのマッチングが行わ
れる。

まず、上位N₁次元（N₁＜Ｎ）までについて、その辞書パ
ターンの特徴ベクトルｆ_ｎと未知文字パターンの特徴
ベクトルY_nとの距離の総和d₁が計算される（ステップ30
2）。そして、その距離の総和d₁と閾値Th₁との比較判定
が行われる（ステップ304）。

d₁＞Th₁であれば、その辞書パターンは距離が大き過ぎ
て候補パターン（候補文字）とはなり得ないから、その
マッチングをこの段階で区切り、辞書パターン番号ｋを
インクリメントし（ステップ306）、ステップ306に戻
る。

つまり、上位N₁次元までの距離演算によって、未知文字
パターンの大分類（候補パターンの絞り込み）が行わ
れ、こゝで排除された辞書パターンのマッチングは、こ
の段階で終了する。

ステップ304においてd₁≦Th₁であれば、全次元Ｎまでの
距離を総和d₂が求められる（ステップ310）。そして、
その距離d₂と、その直前までの候補パターンと未知文字
パターンとの距離とが比較され、小さいほうの候補パタ
ーンと距離が保存され（ステップ312）、ステップ206を
介してステップ302に戻る。

最終の辞書パターンまでマッチングが終了すると、ステ
ップ308にて終了と判定され、最終的に残っていた候補
パターンの文字コードが出力され（ステップ314）、未
知文字パターンの認識処理が完了する。

このように、この実施例では特徴ベクトルの上位次元か
ら優先的に距離を演算し、ある次元までの演算結果によ
って候補パターンとなる得ない辞書パターンを早期に排
除し、候補パターンとなり得る辞書パターンについてだ
け全次元の距離演算を行って詳細マッチングを行う。し
たがって、前記実施例におけるよりも無駄な距離演算が
減少し、マッチング効率がさらに向上する。

このような段階的な候補パターンの縦り込みを２段階以
上行ってもよい。例えば、各辞書パターンについて、上
位N₁（たゞしN₁＜Ｎ）次元までの距離を演算することに
より、未知文字パターンの大分類を行う。そこで排除さ
れなかった場合に、その辞書パターンについて上位N
₂（たゞし、N₁＜N₂＜Ｎ）次元までの距離を演算して未
知文字パターンの中分類を行う。この中分類でも排除さ
れない場合、上位_３（たゞしN₂＜N₃＜Ｎ）次元までの距
離演算によって未知文字パターンの小分類を行う。この
小分類でも排除されない場合、全次元についての距離演
算による未知文字パターンの詳細マッチングを行う。

このようにすれば、候補となり得ない辞書パターンとの
マッチング演算を一層早期に中止し、マッチング時間を
一層短縮することができる。

なお、前記各実施例においては、未知パターンと辞書パ
ターンとのマッチングに距離を用いたが、類似度を求め
て同様のマッチング処理を行ってもよいことは当然であ
る。

また、本発明は文字パターンに限らず、音声などパター
ン全般の認識に同様に適用できるものである。

〔効 果〕

以上の説明から明らかなように、本発明によれば、多層
方向ヒストグラム法によるマッチング効率を大幅に向上
してパターン認識時間を短縮できるとゝもに、辞書容量
を大幅に削除できるなどの効率が得られる。

【図面の簡単な説明】

第１図は本発明の一実施例の機能的構成を簡略化して示
す簡略ブロック図、第２図は同実施例における辞書作成
処理の概略フローチャート、第３図は同実施例における
パターン認識処理の概略フローチャート、第４図は本発
明の法の実施例におけるマッチング処理の概略フローチ
ャート、第５図は多層方向ヒストグラム法における特徴
ベクトルの性質を説明するためのベクトル図、第６図は
特徴ベクトルの成分並べ替えの説明図である。 10……パターン読み取り部、12……前処理部、14……特
徴抽出部、16……並べ替え部、18……並べ替えテーブル
部、20……辞書作成部、22……辞書。

Claims (2)

【特許請求の範囲】
1. 【請求項１】多層方向ヒストグラム法によるパターン認
   識方法において、多層方向ヒストグラム法によって得ら
   れた標準パターンの特徴ベクトルの成分を標準偏差また
   は分散の大きい順に予め並べ替えたのち、その上位Ｎ次
   元の成分だけからなるベクトルを辞書パターンの特徴ベ
   クトルとして辞書に登録しておき、多層方向ヒストグラ
   ム法により未知パターンから抽出した特徴ベクトルの成
   分を、辞書パターンの特徴ベクトルの成分の並べ替え順
   に従って並べ替え、その成分並べ替え後の特徴ベクトル
   と辞書パターンの特徴ベクトルとの対応次元成分の距離
   または類似度を演算することにより、未知パターンと辞
   書パターンとのマッチングを行うことを特徴とするパタ
   ーン認識方法。
2. 【請求項２】特徴ベクトルの距離または類似度の演算を
   上位次元の成分から優先的に行い、その演算の結果によ
   って、さらに下位次元の成分の距離または類似度の演算
   を行うか否かを判定することを特徴とする特許請求の範
   囲第１項に記載のパターン認識方法。