JPS63778A

JPS63778A - パターン認識方法

Info

Publication number: JPS63778A
Application number: JP61144486A
Authority: JP
Inventors: Michiyoshi Tachikawa; 道義立川
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1986-06-20
Filing date: 1986-06-20
Publication date: 1988-01-05
Anticipated expiration: 2010-02-08
Also published as: JPH0711819B2

Abstract

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

Description

【発明の詳細な説明】［技術分野］本発明は手書き漢字などのパターンの認識方式に関し、
さらに詳細には、多層方向ヒストグラム法による特徴ベ
クトルを用いるパターン認識方式％式％］本出願人は、特願昭第５９−２０２８２２号、特願昭５
８−２０２８２５号になどによって、多層方向ヒストグ
ラム法によるパターン認識方式を既に提案している。本
発明は、このようなパターン認識方式の改良に関するも
のである。

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

そし、て、パターンの枠内の分割領域毎に、ある層まで
の層別の方向コードのヒストグラムを求め、それぞれの
ヒストグラムを成分（特徴量）としたベクトルを、パタ
ーンの特徴ベクトルとして用いる。

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

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

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

このパターン認識方式にも同様に適用できるものである
。

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

さて、このような多層方向ヒストグラム法によるパター
ン認識方式においては、未知パターンから抽出された特
徴ベクトルと、辞書パターンの特徴ベクトルとのマツチ
ング距離を演算することによって、未知パターンのパタ
ーン種を同定する（未知パターンを認識する）。

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

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

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

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

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

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

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

以上のような点に着目し、本発明にあっては、多層方向
ヒストグラム法によって全パターン種の仮辞書パターン
の特徴ベクトルを得て、その特徴ベクトルの成分を標準
偏差または分散の大きい次元順の並べ替えたベクトルを
辞書パターンの特徴ベクトルとして辞書に登録してする
。

そして、パターン認識は次のようにして行う。

未知パターンから多層方向ヒストグラム法によって特徴
ベクトルを抽出し、その成分を前記標準偏差または分散
の大きい次元順に並べ替えたベクトルと、各パターン種
の辞書パターンの特徴ベクトルとのマツチングを上位Ｎ
次元まで行い、そのマツチング距離と当穫パターン種に
対応した閾値とを比較し、その比較結果によって当該パ
ターン種に関するマツチングを中断するか、さらに下位
次元までの詳細マツチングを行うか否かの判定を行う。

また、その閾値は次のようにして決定する。パターン種
毎に複数のパターンから多層方向ヒストグラム法によっ
て特徴ベクトルをそれぞれ抽出して、その成分を前記標
準偏差または分散の大きい次元順に並べかえたベクトル
と、同一パターン種の前記辞書パターンの特徴ベクトル
との上位Ｎ次元までのマツチング距離の標準偏差または
分散を求め、この標準偏差または分散に基づいて前記パ
ターン種毎の閾値を決定する。

このようなパターン認識方式によれば、未知パターンの
候補となり得ないような辞書パターンとのマツチング処
理が早期に中断するので、マツチング効率が向上してパ
ターン認識速度が上がる。

また、マツチング中断の判定用閾値を前記のようにパタ
ーン種別に管定するので、候補から排除すべきでない辞
書パターンとのマツチングが誤って中断するエラーも確
実に防止できるため、多層方向ヒストグラム法によるパ
ターン認識方式の本質的な利点は損なわれず、高い認識
率を達成できる。

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

第１図は２本発明の一実施例の機能的構成を簡略化して
示す概略ブロック図である。なお、この実施例において
は、認識対象のパターンとして手書き漢字などの文字パ
ターンを想定している。

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

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

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

一つの文字種について、Ｍ個の文字パターンがパターン
読み取り部１０より順次入力される（ステップ５０）。

その入力文字パターンは前処理部１２で前処理を受け（
ステップ５２）、特徴抽出部１４に入力されて多層方向
ヒストグラム法による特徴ベクトル（例えば２５６次元
のベクトル）を抽出される（ステップ５４）。抽出され
た特徴ベクトルは並べ替え部１６を介して辞書作成部２
０に入力される。この辞書作成部２０により２Ｍ個の入
力文字パターンから抽出された特徴ベクトルを平均した
ベクトルが求められ（ステップ５６）、その平均ベクト
ルは、その文字種の仮辞書パターンの特徴ベクトルとし
て辞書２２に仮登録される（ステップ５８）。

辞書作成部２０により、最後の文字種まで処理が終了し
たか調べられ（ステップ６０）、未処理の文字種が残っ
ていれば、ステップ５１に戻り、次の文字種に対する同
様の処理が行われる。

全ての文字種について処理が終ると、並べ替えテーブル
作成部２６において、辞書２２に仮登録されている全仮
辞書パターンの特徴ベクトルの、次元毎の標準偏差また
は分散が計算される（ステップ６２）。そして、もとの
特徴ベクトルを標準偏差または分散の大きい次元順に並
べ替えるための並べ替えテーブルが作成され、並べ替え
テーブル１８に登録される（ステップ６４）。

こ＼までは、並べ替えテーブルを作成するための処理段
階であり、この後に実際の辞書作成処理が始まる。

一つの文字種ｋについて、Ｍ個の文字パターンがパター
ン読み取り部１ｏより順次入力される（ステップ６６）
。その入力文字パターンは前処理部１２で前処理を受け
（ステップ６８）、特徴抽出部１４に入力されて多層方
向ヒストグラム法による特徴ベクトルを抽出される（ス
テップ７０）。

抽出された特徴ベクトルの尾成分は、並べ替え部１６に
よって、並べ替えテーブル部１８に登録されている並べ
替えテーブルに従い、前記標準偏差または分散の大きい
次元順に並べ替えられる（ステップ７２）。このように
成分の並べ替え後のＭ個の特徴ベクトルは辞書作成部２
ｏに送られ。

それらの平均ベクトルが、その文字値にの辞書パターン
の特徴ベクトルとして辞書２０に本登録される（ステッ
プ７４）。

辞書作成部２０により、全部の文字種（Ｋ種）について
辞書作成処理が終了したか調べられ（ステップ７６）、
未処理の文字種が残っているならば、未処理の文字種に
ついてステップ６６から同様の処理が行われる。

全文字種について処理が完了すると、辞書そのもの＼作
成は終わりであるが１次に閾値決定の処理が行われる。

この処理においては、文字種毎に辞書作成に用いられた
と同様なＭ個の文字パターンが入力され（ステップ７８
）、前処理（ステップ８０）の後。

それぞれ多層方向ヒストグラム法による特徴ベクトルを
抽出される（ステップ８２）。このＭ個の文字パターン
の特徴ベクトルはそれぞれ、並べ替え部１６によって並
べ替えテーブルに従い成分が並べ替えられ（ステップ８
４）、マツチング部２４に入力される。

次にマツチング部２４および閾値決定部２８の起動によ
り、閾値決定が行われる。すなわち、マツチング部２４
により、その各特徴ベクトルと文字種にの辞書パターン
の特徴ベクトルとのマツチング距離が上位に次元まで演
算され、閾値決定部２８において、その演算結果から、
上位Ｎ次元までのマツチング距離の標準偏差が求められ
る（ステップ８６）。そして、その標準偏差が文字種に
の閾値として閾値テーブル部３０に登録される（ステッ
プ８８）。

同様にして、他の文字種の閾値が決定され、閾値テーブ
ル部３０に登録される。

全文字種について閾値の決定登録が完了したと判定され
る（ステップ９０）、辞書作成モードの処理全体が終了
する。

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

認識対象の未知文字パターンは、パターン読み取り部１
０より入力され（ステップ１００）、前処理部１２によ
る前処理（ステップ１０２）の後。

特徴抽出部１４で多層方向ヒストグラム法によって特徴
ベクトル（たとえば２５６次元のベクトル）を抽出され
る（ステップ１０４）。

この特徴ベクトルは、並べ替え部１６によって並べ替え
テーブルに従い成分が並べ替えられ、その並べ替え後の
特徴ベクトルＹｎがマツチング部２４に入力される（ス
テップ１０６）。

マツチング部２４において、文字種にの辞書パターンの
特徴ベクトルＦｋｎと、未知パターンの特徴ベクトルＹ
ｎとの上位Ｎ次元までのマツチング距離ｄが演算される
（ステップ１０８）。そして、そのマツチング距離ｄと
、閾値テーブル部３０に登録されている対応文字種にの
閾値Ｔｈｋとの比較判定が行われる（ステップ１１０）
。

ｄ＞Ｔｈｋであれば、その未知パターンの文字種と現在
の文字種にである可能性はないので、その辞書パターン
とのマツチング処理を中断し、終了判定を行う　（ステ
ップ１１６）。

ｄ≦Ｔｈｋであれば、現在の文字種は未知文字パターン
の文字種である可能性が高いので、詳細マツチングが行
われる。すなわち、全次元についてマツチング距離りが
演算される（ステップ１１２）。そして、その距離りと
、それまでの候補の距離とが比較され、距離が小さいほ
うの文字種が新しい候補として残され（ステップ１１４
）、終了判定のステップ１１６に進む。

ステップ１１６において、マツチングすべき文字種が残
っていると判定されると、次の文字種についてステップ
１０８以降のマツチング処理が行われる。

すべての文字種についてマツチング処理が行われると、
ステップ１１６で終了と判定され、最終的に残った候補
の文字種の文字コードが認識結果として出力される。こ
れで、一つの未知文字パターンの認識処理を完了する。

さて１手書き漢字などの文字の変形の傾向や程度は、記
入者（認識システムの使用者）によって様々である。こ
れに対処するために、様々な文字変形を考慮した文字パ
ターンを用意し、辞書作成に用いる。

しかし、そのようにしても、使用者によって、その手書
き文字パターンと辞書パターンとのマツチングの良し悪
しがある。また、同一の使用者でも、認識システムに対
し慣れるに従い、辞書とのマツチング性が向上し、認識
率が高く成る傾向が認められる。

このような点に着目すると、詳細マツチングを行うか否
かの判定のための閾値を変更できると好都合である。す
なわち、辞書とのマツチングの長使用者の場合または慣
れた使用者の場合１判定閾値を下げて詳細マツチングの
頻度を下げることにより、認識率を下げることなく、認
識速度を上げることができる。

次に、このような閾値の調整を可能とした本発明の第２
実施例について説明する。なお、この実施例の機能的構
成は前記実施例と同様であるので、そのブロック図は省
略し、以下の説明において必要に応じ第１図を参照する
。

この実施例においては、辞書作成モードにおいて、前記
実施例と同様に、並べ替えテーブルと辞書が作成される
。たゾし、詳細マツチングを行うか否かの判定のための
閾値が１文字種毎に複数種類決定される。

この点について、前記第１実施例に関連した第２図のフ
ローチャートを参照して説明すれば、ステップ８８にお
いて決定される閾値をＴｈｋとすれば、この実施例にあ
っては、Ｔｈｋ／１．Ｔｈｋ／２〜Ｔｈｋ／Ｌ　（Ｌは
正の整数）の値が、それぞれ文字種にの閾値Ｔｈｋ　（
１）、Ｔｈｋ　（２）〜Ｔｈｋ（Ｌ）として閾値決定部
２８により決定され、閾値テーブル部３０に登録される
６第４図は、この実施例におけるパターン認識モードの
概略フローチャートである。この図を参照し、この実施
例におけるパターン認識モードについて説明する。

この実施例においては、閾値の選択のためのパラメータ
であるユーザレベルＵＬ　（＝１．２，３゜・・・、Ｌ
）が最初のステップ２００で設定される。

このユーザレベルＵＬは、この実施例に係るパターン認
識システムの使用者側で指定できるものである。

ステップ２０２からステップ２１０までは、第３図のス
テップ１００からステップ１０８までと同一内容である
。ステップ２１４からステップ２２０までは、第３図の
ステップ１１２からステップ１１８までと同一内容であ
る。

ステップ２１２は、上位Ｎ次元までのマツチング距離か
ら詳細マツチングを行うか否かを判定するためのステッ
プであり、第３図のステップ１１Ｏと対応する。この実
施例の場合、文字種にの複数の閾値Ｔｈ　（１）〜Ｔｈ
　（Ｌ）の中から、ユーザレベルＵＬに対応する一つの
閾値Ｔｈ　（ＵＬ）が、その判定の閾値として用いられ
る。

つまり、この実施例に係わるパターン認識システムに慣
れた使用者の場合、ユーザレベルＵＬを高いレベル（最
高はＬ）に指定すれば、より小さい閾値（最低はＴｈ（
Ｌ））が選択されて判定に用いられるから、詳細マツチ
ング（ステップ２１４）に進む頻度が少なくなり、それ
だけマツチング効率が向上して文字認識速度が上がる。

逆に、慣れていない使用者または辞書とのマツチングの
良くない使用者の場合、低いユーザレベルＵＬ（最低は
１）を指定すれば、大きい閾値（最高はＴｈｋ　（１）
）が選択されて判定に用いられ、詳細マツチングの頻度
が上がるから、認識速度は落ちるが認識率を上げること
ができる。

さて、前述のように、認識率は使用者によって変動する
が、さらに文字種によっても変動する。

これは、辞書作成用のパターンとして、ある癖を持った
パターンが用いられた場合などに顕著であるが、このよ
うな点は漢字のように文字種が多い場合、辞書作成段階
ではチエツクが困難である。

そのような文字種ごとの認識率の変動を吸収することが
できる０本発明の第３実施例について以下に説明する。

なお、この実施例に係るパターン認識システムの機能的
構成は航記第１実施例と同様である。また、辞書作成モ
ードの処理は前記第２実施例と同様であり、文字種毎シ
Ｊ複数種類の判定用閾値ｒｈ　（１）〜Ｔｈ　（Ｌ）が
決定される。

第５図は、この実施例におけるパターン認識モードの処
理の概略フローチャートである。この図において、ステ
ップ３００〜３０８は第４図のステップ２０２〜２１０
と同一内容であり、ステップ３１４〜３２０も第４図の
ステップ２１４〜２２０と同一内容である。

ステップ３１０では、文字種毎のレベルＬＶ（ｋ）が、
閾値選択用のパラメータＶとして設定される。このレベ
ルＬＶ　（ｋ）は１例えばパターン認識システムの運用
中に文字種にのリジェクト・認識率Ｒｋを蓄えておき、
そのＰｋ値をある定数で割り算した値として与えられる
。

そして、ステップ３１２は第４図のステップ２１２に対
応するステップであり、文字種にの複数の閾値Ｔｈｋ　
（１）〜Ｔｈ　（Ｌ）の中から、パラメータＶに対応す
る一つの閾値Ｔｈｋ（Ｖ）を選択し、距離ｄと比較する
ことにより詳細マツチング（ステップ３１４）に進むか
否かを判定する。

なお、この実施例と、前記第２実施例とを組み合わせた
第４の実施例について１便宜上、第５図のフローチャー
トを参照して説明する。

この実施例にあっては、ステップ３００の前にユーザレ
ベルＵＬの設定ステップ（第４図のステップ２００に相
当）が追加される。また、ステップ３・１０において、
文字種にのレベルＬＶ　（ｋ）とユーザレベルＵＬとの
和がパラメータＶとして設定される。そして、ステップ
３１２において、パラメータＶに対応する閾値Ｔｈｋ（
Ｖ）が判定に用いられる。

これ以外は、前記各実施例と同様である。

この実施例によれば、使用者および文字種による変動要
因を吸収し、最適な閾値を用いて詳細マツチングを行う
か否かの判定を行うことができるので、前記第２実施例
と第３実施例の両方の利点が得られる。

以上、本発明の実施例について説明したが、本発明はそ
れだけに限定されるものではなく、その要旨を逸脱しな
い範囲内で種々変形して実施し得るものである。

また、前記各実施例は１文字パターンを認識対象とした
が、本発明は文字パターンに限らず、音声などパターン
全般の認識に同様に適用できることは、以上の説明から
明らかである。

〔効　果〕

以上の説明から明らかなように５本発明によれば、多層
方向ヒストグラム法によるマツチング効率を大幅に向上
し、パターン認識時間を短縮できるなどの効果が得られ
る。

【図面の簡単な説明】

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

Claims

【特許請求の範囲】

（１）多層方向ヒストグラム法によって全パターン種の
仮辞書パターンの特徴ベクトルを得て、その仮辞書パタ
ーンの特徴ベクトルの成分を標準偏差または分散の大き
い次元順に並べ替えたベクトルを辞書パターンの特徴ベ
クトルとし、パターン種毎に複数のパターンから多層方向ヒストグラ
ム法によって特徴ベクトルをそれぞれ抽出して、その成
分を前記標準偏差または分散の大きい次元順に並べかえ
たベクトルと、同一パターン種の前記辞書パターンの特
徴ベクトルとの上位Ｎ次元までのマッチング距離の標準
偏差または分散に基づいてパターン種毎の閾値を決定し
、未知パターンから多層方向ヒストグラム法によって抽
出した特徴ベクトルの成分を前記標準偏差または分散の
大きい次元順に並べ替えたベクトルと、各パターン種の
前記辞書パターンの特徴ベクトルとのマッチングを上位
Ｎ次元まで行い、そのマッチング距離と当該パターン種
の前記閾値とを比較し、その比較結果によって当該パタ
ーン種に関してさらに下位次元までの詳細マッチングを
行うか否かを判定することを特徴とするパターン認識方
式。
（２）パターン種毎の閾値は複数個決定され、その中の
一つの閾値が選択されて、詳細マッチングを行うか否か
の判定に用いられることを特徴とする特許請求の範囲第
１項に記載のパターン認識方式。
（３）判定に用いられる閾値の選択は、全パターン種に
共通のパラメータに従って行われることを特徴とする特
許請求の範囲第２項に記載のパターン認識方式。
（４）判定に用いられる閾値の選択は、パターン種毎の
パラメータに従って行われることを特徴とする特許請求
の範囲第２項に記載のパターン認識方式。
（５）判定に用いられる閾値の選択は、全パターン種に
共通のパラメータおよびパターン種毎のパラメータに従
って行われることを特徴とする特許請求の範囲第２項に
記載のパターン認識方式。