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

Abstract

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

Description

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

〔従来技術〕

本出願人は、特願昭第５９−２０２８２２号。

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

この多層方向ヒストグラム法によるパターン認識方式に
おいては１文字などのパターンの輪郭画素に方向コード
を付け、そのパターンの枠の各辺から対向する辺に向か
ってパターンを走査して白画素（背景）の次に出現する
方向コードを検出し。

その方向コードをそれが走査線上で何番目に検出された
かによって複数の層に層別する。そして、パターンの枠
内の分割領域毎に、ある層までの層別の方向コードのヒ
ストグラムを求め、それぞれのヒストグラムを成分（特
徴量）としたベクトルを、パターンの特徴ベクトルとし
て用いる。

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

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

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

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

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

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

〔目　的〕

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

〔構　成〕

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

次元数を２として多層方向ヒストグラム法による辞書を
作成した場合、″文″′、″字″、“認″。

１１　ｍ　ｌ＋のそれぞれの辞書パターンの特徴ベクト
ルは、それぞれ第５図のｇ工ｒ　ｇｚｒ　ｇｚｒ　ｇ４
のようになる。この例では１図から明らかなように、各
特徴ベクトルは成分（特徴量）Ａのほうが、成分（特徴
量）Ｂよりも分散（または標準偏差）が大きい。換言す
れば、成分Ａのほうが、未知パターンに対する識別能力
が高い。

未知パターンと辞書パターンとのマツチングは。

基本的には、未知パターンと辞書パターンの特徴ベクト
ルの対応次元成分の距離または類似度を求め、その距離
の総和が最小または類似度の総和が最大の辞書パターン
を認識結果とするものである。

こ＼で、前記のような特徴ベクトルの性質に着目すれば
、パターン識別能力の高い部分から優先的に距離または
類似度を演算することにより、パターン識別能力の高い
一部の成分について距離または類似度を演算した段階で
、候補となり得ない辞書パターンを排除し、候補となり
得る辞書パターンを早い段階で絞り込むことができるで
あろう。

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

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

例えば、多層方向ヒストグラム法により作成されたある
辞書パターンの特徴ベクトルが第６図の（ａ）に示すよ
うであったとする。そして、全標準パターンについて計
算された標準偏差または分散の大きい次元順がＸ　４．
　Ｘｌ、　Ｘ、、　Ｘ７．　Ｘ、。

Ｘ２．Ｘ、、ＸＧ、・・・であるとする。そうすると、
この特徴ベクトルは、その各次元Ｘ□ｊ　ｘ２．　ｘ、
。

・・の成分が第６図の（ｂ）に示すように並べ替えられ
て辞書に登録される。つまり、元の特徴ベクトルの次元
ｘ４の成分が並べ替え後の特徴ベクトルの最上位の次元
Ｙ□の成分、次元Ｘ□の成分が次位の次元Ｙ２の成分、
というように並べ替えられる。

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

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

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

〔実施例〕

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

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

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

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

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

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

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

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

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

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

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

このようにして、同−文字織のＭ個の文字パターンに対
する次元並べ替え後のＮ次元の特徴ベクトルが辞書作成
部２０に蓄積されると、辞書作成部２０は、そのＭ個の
特徴ベクトルの平均を求め。

それを文字種にの辞書パターンの特徴ベクトル（Ｎ次元
ベクトル）ｆｋｎとして１文字コードを付加し辞書２２
に登録する（ステップ１ｏ８）。

次に、文字種番号ｋが更新され（ステップ１１０）、ス
テップ１００に戻り、次の文字種について同様の辞書作
成処理が実行される６ 最後の文字種（ｋ＝ｋ）まで処理が実行されると、ステ
ップ１１２により処理終了と判断され、処理を完了する
。

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

認識対象の文字パターン（未知文字パターン）はパター
ン読み取り部１ｏから入力され（ステップ２００）、前
処理部１２により前処理を受け（ステップ２０２）、特
徴抽出部１４に入力され、そこで多層方向ヒストグラム
法により特徴ベクトルｘｎ（例えば２５６次元ベクトル
）を抽出される（ステップ２０４）。

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

マツチング部２４においては、っぎのようにして未知入
カバターンと辞書パターンとのマツチングが行われる（
ステップ２０８）。

それぞれの文字種にの辞書パターンの特徴ベクトルｆｋ
ｎと未知文字パターンの特徴ベクトルＹｎとの距離Ｄｋ
を次式 ：１ によって計算する。そして、その距離のソートを行い、
距離が最小の辞書パターンを候補文字として決定するに の候補文字の文字コードは、未知文字パターンに対する
認識結果として出力される（ステップ２１０）。

このように、この実施例では、辞書パターンの特徴ベク
トルは標準偏差または分散の大きい次元順、つまりパタ
ーン識別能力の高い次元順に成分が並べ替えられ、かつ
上位Ｎ次元以外のパターン識別能力の低い成分を捨てた
形で辞書に登録されており、また未知入カバターンの特
徴ベクトルは辞書パターンと同じ次元順の成分が並べ替
えられ。

辞書パターンと未知文字パターンとのマツチングは、Ｎ
次元のベクトル間の距離または類似度に演算によって行
われる。

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

次に、本発明の他の実施例について説明する。

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

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

まず、上位Ｎ２次元（Ｎよ＜Ｎ）までについて、その辞
書パターンの特徴ベクトルｆｋｎと未知文字パターンの
特徴ベクトルＹ。どの距離の総和ｄ、が計算される（ス
テップ３ｏ２）。そして、その距離の総和ｄ工と閾値Ｔ
ｈ１との比較判定が行われる（ステップ３０４）。

ｄ工＞Ｔｈ１であれば、その辞書パターンは距離が大き
過ぎて候補パターン（候補文字）とはなり得ないから、
そのマツチングをこの段階で打切り。

辞書パターン番号ｋをインクリメントしくステップ３０
６）、ステップ３０２に戻る。

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

ステップ３０４においてｄ１≦Ｔｈ１であれば、全次元
Ｎまでの距離を総和ｄ２が求められる（ステップ３１０
）。そして、その距離ｄ２と、その直前までの候補パタ
ーンと未知文字パターンとの距離とが比較され、小さい
ほうの候補パターンと距離が保存され（ステップ３１２
）、ステップ２０６を介してステップ３０２に戻る。

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

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

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

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

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

また１本発明は文字パターンに限らす、音声などパター
ン全般の認識に同様に適用できるものである、 〔効　果〕 以上の説明から明らかなように、本発明によれば、多層
方向ヒストグラム法によるマツチング効率を大幅に向上
してパターン認識時間を短縮できると＼もに、辞書容量
を大幅に削除できるなどの効率が得られる。

【図面の簡単な説明】

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

Claims (2)

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