(57)【特許請求の範囲】
【請求項１】
入力パターンから抽出した特徴量を複数の参照パターンの特徴量とそれぞれ比較して複数の候補パターンを選択し、該選択した各候補パターンを前記入力パターンと照合してパターン認識をおこなうパターン認識装置において、
前記入力パターンと参照パターンをユークリッド距離を用いて照合して複数の候補パターンを選択する候補パターン選択手段と、
前記候補パターン選択手段により選択された各候補パターンそれぞれについてカテゴリーの情報を多く含む順に特徴量の部分空間の射影軸を選択し、その上位の射影軸から順次該射影軸に入力パターンの特徴量を射影して各候補パターンの補正値を算出しつつ該算出された補正値を用いて各候補パターンの入力パターンと射影軸の距離を示す修正距離を求める処理を各射影軸に対して繰り返す際に、繰り返し途中の段階で第１の候補パターンの修正距離が最小値となる第２の候補パターンの修正距離よりも所定以上大きい場合に該第１の候補パターンを前記複数の候補パターンから除外して候補パターン数を絞り込む候補パターン絞込手段と
を備えたことを特徴とするパターン認識装置。
【請求項２】
入力パターンから抽出した特徴量を複数の参照パターンの特徴量とそれぞれ比較して複数の候補パターンを選択し、該選択した各候補パターンを前記入力パターンと照合してパターン認識をおこなうパターン認識方法において、
前記入力パターンと参照パターンをユークリッド距離を用いて照合して複数の候補パターンを選択する候補パターン選択工程と、
前記候補パターン選択工程により選択された各候補パターンそれぞれについてカテゴリーの情報を多く含む順に特徴量の部分空間の射影軸を選択し、その上位の射影軸から順次該射影軸に入力パターンの特徴量を射影して各候補パターンの補正値を算出しつつ該算出された補正値を用いて各候補パターンの入力パターンと射影軸の距離を示す修正距離を求める処理を各射影軸に対して繰り返す際に、繰り返し途中の段階で第１の候補パターンの修正距離が最小値となる第２の候補パターンの修正距離よりも所定以上大きい場合に該第１の候補パターンを前記複数の候補パターンから除外して候補パターン数を絞り込む候補パターン絞込工程と
を含んだことを特徴とするパターン認識方法。
【請求項３】
前記請求項２に記載された方法をコンピュータに実行させるプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、入力パターンから抽出した特徴量を複数の参照パターンの特徴量とそれぞれ比較して複数の候補パターンを選択し、該選択した各候補パターンを入力パターンと照合してパターン認識をおこなうパターン認識装置、パターン認識方法およびその方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体に関し、特に、手書き文字などのパターンを認識する際に、高速かつ効率良く候補パターンを絞ることができるパターン認識装置、パターン認識方法および記録媒体に関する。
【０００２】
【従来の技術】
従来、手書き文字などを認識する場合に、認識対象文字の画像情報から複数種の特徴を抽出し、これをあらかじめ登録した各参照パターンの各特徴と順次比較して文字候補を決定する文字認識技術が知られている。
【０００３】
たとえば、特開平５−１２０４８６号公報（従来技術１）には、各参照パターンの各特徴と比較する前に比較後の比較結果の累積値を推定し、推定した値と基準値とを比較して処理を続行するか否かを判断するよう構成した文字認識装置が開示されている。
【０００４】
また、「木村義政他，”拡張ＰＤＣ特徴を用いた手書き漢字認識ソフトウエア”，NTT R&D VOL.47 No.6，1998」（従来技術２）には、特徴の次元数を変化させながら多段にわたって分類をおこなう階層的分類法を採用することにより処理を高速化する技術が開示されている。具体的には、この従来技術２のものは、シティ・ブロック距離で低い次元数の特徴量を用いて候補を決定し、それ以降段階的に使用する特徴次元を増やしながら候補を絞り込み、最終的に詳細識別のより結果を出力する。
【０００５】
【発明が解決しようとする課題】
しかしながら、上記従来技術１のように基準値を設けて処理を打ち切って候補を決定する場合には、演算における順序が問題となり、演算の順序によっては識別能力が低下する可能性がある。たとえば、縦横の成分から演算をおこなう場合、識別における各成分の重要度（情報量）を全く考慮していないため基準値をいくらうまく設定しても十分に高速化できないという問題がある。
【０００６】
また、従来技術２によれば、シティ・ブロック距離を用いて低い次元数の特徴量から徐々に高い次元数の特徴量を用いて候補を決定することにより高速化を図ることができるものの、詳細判定をおこなう情報とは別に、段階的におこなう分類処理の特徴量を各段階毎に持つ必要があるという問題がある。
【０００７】
これらのことから、手書き文字などのパターン認識をおこなう際に、いかに高速かつ効率良く、パターンの候補を絞るかが極めて重要な課題となっている。特に、認識に用いる特徴量が増えれば増えるほど、かかる課題をいかに解決するかが深刻な問題となる。
【０００８】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、手書き文字などのパターンを認識する際に、高速かつ効率良く候補パターンを絞ることができるパターン認識装置、パターン認識方法およびその方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【０００９】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、請求項１の発明に係るパターン認識装置は、入力パターンから抽出した特徴量を複数の参照パターンの特徴量とそれぞれ比較して複数の候補パターンを選択し、該選択した各候補パターンを前記入力パターンと照合してパターン認識をおこなうパターン認識装置において、前記入力パターンと参照パターンをユークリッド距離を用いて照合して複数の候補パターンを選択する候補パターン選択手段と、前記候補パターン選択手段により選択された各候補パターンそれぞれについてカテゴリーの情報を多く含む順に特徴量の部分空間の射影軸を選択し、その上位の射影軸から順次該射影軸に入力パターンの特徴量を射影して各候補パターンの補正値を算出しつつ該算出された補正値を用いて各候補パターンの入力パターンと射影軸の距離を示す修正距離を求める処理を各射影軸に対して繰り返す際に、繰り返し途中の段階で第１の候補パターンの修正距離が最小値となる第２の候補パターンの修正距離よりも所定以上大きい場合に該第１の候補パターンを前記複数の候補パターンから除外して候補パターン数を絞り込む候補パターン絞込手段とを備えたことを特徴とする。
【００１３】
また、請求項２の発明に係るパターン認識方法は、入力パターンから抽出した特徴量を複数の参照パターンの特徴量とそれぞれ比較して複数の候補パターンを選択し、該選択した各候補パターンを前記入力パターンと照合してパターン認識をおこなうパターン認識方法において、前記入力パターンと参照パターンをユークリッド距離を用いて照合して複数の候補パターンを選択する候補パターン選択工程と、前記候補パターン選択工程により選択された各候補パターンそれぞれについてカテゴリーの情報を多く含む順に特徴量の部分空間の射影軸を選択し、その上位の射影軸から順次該射影軸に入力パターンの特徴量を射影して各候補パターンの補正値を算出しつつ該算出された補正値を用いて各候補パターンの入力パターンと射影軸の距離を示す修正距離を求める処理を各射影軸に対して繰り返す際に、繰り返し途中の段階で第１の候補パターンの修正距離が最小値となる第２の候補パターンの修正距離よりも所定以上大きい場合に該第１の候補パターンを前記複数の候補パターンから除外して候補パターン数を絞り込む候補パターン絞込工程とを含んだことを特徴とする。
【００１７】
また、請求項３の発明に係る記録媒体は、請求項２に記載された方法をコンピュータに実行させるプログラムを記録したことで、そのプログラムを機械読み取り可能となり、これによって、請求項２の動作をコンピュータによって実現することができる。
【００１８】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係るパターン認識装置、パターン認識方法およびその方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体の好適な実施の形態を詳細に説明する。なお、本実施の形態では、本発明を文字認識装置に適用した場合を示すこととする。
【００１９】
まず最初に、本実施の形態で用いる文字認識装置の構成について説明する。図１は、本実施の形態で用いる文字認識装置の構成を示す機能ブロック図である。同図に示すように、この文字認識装置１０は、画像入力部１１と、前処理部１２と、特徴抽出部１３と、参照データ管理部１４と、参照データ記憶部１５と、候補選択部１６と、候補絞込処理部１７と、認識処理部１８とからなる。
【００２０】
ここで、請求項１の候補パターン選択手段は候補選択部１６に対応し、請求項１の候補パターン絞込手段は候補絞込処理部１７に対応する。
【００２１】
画像入力部１１は、文字の画像を光学的に読み取るスキャナなどの入力デバイスであり、この画像入力部１１によって読み取られた画像データは前処理部１２に出力される。
【００２２】
前処理部１２は、画像入力部１１から受け取った画像データの前処理をおこなう処理部であり、具体的には、この画像データを平滑化処理してノイズを除去した後に、これを所定のしきい値で二値化して二値画像を取得し、この二値画像から文字を切り出した後に、これを正規化する処理部である。
【００２３】
特徴抽出部１３は、前処理部１２が前処理をおこなった正規化された文字データから特徴量を抽出する処理部であり、具体的には、図２に示すような文字の画像データを５×５にメッシュ割りし、各メッシュについての輪郭の方向を求めることになる。ここで、輪郭の方向は図３に示すような８方向とすると、５×５×８＝２００次元の特徴空間が形成されることになる。
【００２４】
参照データ管理部１４は、入力データの比較の対象となる参照データを管理する管理部であり、参照データ記憶部１５は、かかる参照データを記憶する記憶部である。なお、この参照データとしては、参照文字の文字パターン（参照パターン）と該参照パターンの特徴量などが含まれ、これらの参照データを文字のカテゴリーに対応づけて参照データ記憶部１５に記憶する。
【００２５】
候補選択部１６は、認識対象となる入力文字の文字パターン（入力パターン）を受け付けた際に、この入力パターンと参照データ管理部１４が管理する参照パターンとをユークリッド距離を用いて照合し、候補カテゴリーを選択する処理部である。
【００２６】
候補絞込処理部１７は、特徴空間から各カテゴリーの情報が多く現れる部分空間を作成し、情報がより多く現れる順に軸を選択して射影し、この射影により求められる累積値を用いて候補カテゴリーを絞り込む処理部である。かかる処理を繰り返すことにより最終的に候補を数個出力する。
【００２７】
ここで、かかる繰り返し処理は、出力する候補数、候補１位の累積値で割った値の何倍までという形でしきい値を定めることによりおこなう。すなわち、この候補絞込処理部１７では、従来の部分空間を用いた詳細判定で用いる特徴量以外の特徴量を別に持つ必要がなく、詳細判定の過程を分割して段階的に候補の絞り込みをおこなっている。
【００２８】
認識処理部１８は、候補絞込処理部１７により絞り込まれた候補カテゴリーが入力された画像データに含まれる文字のカテゴリーであるか否かを判定して、文字認識をおこなう処理部である。
【００２９】
次に、図１に示した候補絞込処理部１７による候補カテゴリーの絞り込みの概念について説明する。図４は、図１に示した候補絞込処理部１７による候補カテゴリーの絞り込みの概念を説明するための説明図である。なお、各カテゴリーの平均パターンである参照ベクトル（２００次元（５×５×８））とは別に、各カテゴリーごとにそのカテゴリーの特徴を最もよく表す射影軸を主成分分析により算定し、その上位４０個を持っているものとする。
【００３０】
同図に示すように、まず最初に候補選択部１６がユークリッド距離を用いて候補カテゴリーを選択する（ステップＳ４０１）。たとえば、全カテゴリーの中から１５００個の候補カテゴリーを選択することになる。
【００３１】
その後、各カテゴリーについて各々４０個の射影軸のうちの上位１０個の射影軸を選んで次を絞り（ステップＳ４０２）、残ったものに対して上位２０個の射影軸を選んで次を絞る（ステップＳ４０３）。この際、上位１０個分はステップＳ４０２により処理済みであるので、残り１０個のみを計算すれば良い。
【００３２】
同様に、残ったものに対して上位３０個の射影軸を選んで次を絞り（ステップＳ４０４）、残ったものに対して上位４０個の射影軸を選んで次を絞る（ステップＳ４０５）。
【００３３】
このように、候補絞込処理部１７では、各カテゴリーの特徴を最もよく表す射影軸を用いて絞り込みをおこなっており、特に、従来から詳細判定で使用していた特徴量を用いて候補を絞っているため辞書に要するメモリ容量の累増を防止することができ、また、詳細判定を分割して候補を絞りながらおこなっているので、高速で高精度な認識をおこなうことができることになる。
【００３４】
次に、図１に示した文字認識装置１０の処理手順について説明する。図５は、図１に示した文字認識装置１０の処理手順を示すフローチャートであり、図６は、図１に示した候補絞込処理部１７の処理概念を説明するための説明図である。ただし、ここでは参照データがすでに参照データ記憶部１５に記憶されているものとする。
【００３５】
また、以下では、カテゴリー番号をｉ、射影軸の番号をｊとし、カテゴリーＣiの共分散行列をΣiとし、Σiの固有値をλijとし（λij≧λij+1）、Σiの固有ベクトルをＰijとし、カテゴリーＣiの平均パターンをｕiとし、学習サンプルから求められるカテゴリーＣiの射影軸Ｐijの重みをｗijとする。図６に示すように、この平均パターンｕiは、カテゴリーＣiの分布の中心に位置し、このｕiは射影軸Ｐij上に位置することになる。
【００３６】
図５に示すように、この文字認識装置１０では、画像入力部１１により文字の画像データが入力されると、この画像データを平滑化した後二値化して、文字を切り出した後に正規化する前処理をおこなう（ステップＳ５０１）。その後、特徴抽出部１３が、文字を５×５のメッシュに分割し、各メッシュに対して輪郭の方向を求める特徴抽出処理をおこなう（ステップＳ５０２）。
【００３７】
その後、候補選択部１６がユークリッド距離により候補カテゴリーを選択する（ステップＳ５０３）。このユークリッド距離は、
ｇi0（ｘ）＝｜ｘ−ｕi｜2
の算定式から算定される。
【００３８】
その後、累積値の相対値ｄikがＤ未満のものを候補カテゴリーとし（ステップＳ５０４）、候補カテゴリー数がＭ個以下となっている場合（ステップＳ５０５肯定）または候補カテゴリー数がＭ個を越えているが（ステップＳ５０５否定）、変数ｋが終了値に達している場合には（ステップＳ５０６肯定）、候補カテゴリーを出力して（ステップＳ５１０）、処理を終了する。
【００３９】
これに対して、候補カテゴリー数がＭ個を越えているが（ステップＳ５０５否定）、変数ｋが終了値に達していない場合には（ステップＳ５０６否定）、各候補カテゴリーに対して軸の補正量Ｑik（ｘ）を計算し、この補正量を用いてＱik（ｘ）候補カテゴリーに対して相対値ｄikを算定し（ステップＳ５０７）、この相対値ｄikを用いて修正距離の相対値を求める（ステップＳ５０８）。
【００４０】
具体的には、
ｑij（ｘ）＝ｗij（（ｘ−ｕi）tＰij）2
によって図６に示した射影軸Ｐij上の距離ｑijを求め、このｑijを用いて射影軸の補正量Ｑik（ｘ）を
Ｑik（ｘ）＝Σｑij（ｘ）
により求める。なお、Σの範囲は、ｊ＝ｋ×１０〜（ｋ＋１）×１０である。
【００４１】
その後、漸化式
ｇik+1（ｘ）＝ｇik（ｘ）−Ｑik（ｘ）
により、図６に示した部分空間への修正距離ｇik（ｘ）（図６ではｇi1）を求める。
【００４２】
そして、候補カテゴリーにおいて最も小さい修正距離をｇMINk（ｘ）とすると、修正距離の相対値ｄik（ｘ）は、
ｄik（ｘ）＝ｇik（ｘ）／ｇMINk（ｘ）
により算定される。
【００４３】
その後、変数ｋをインクリメントした後に（ステップＳ５０９）、ステップＳ５０４に移行して同様の処理（ステップＳ５０４〜Ｓ５０９）を繰り返し、候補カテゴリー数がＭ個以下となった場合（ステップＳ５０５肯定）または変数ｋが終了値に達した場合（ステップＳ５０６肯定）に処理を終了する。
【００４４】
上記一連の処理をおこなうことにより、特徴空間から各カテゴリーの情報がより多く現れるような部分空間を形成する軸に情報量が多い順に射影し、内積演算から得られる累積値に基づいて候補を削減する処理を指定した候補数まで繰り返している。このため従来の部分空間による詳細判定手法において用いられた特徴量とは別に特徴量を持つ必要がなく、段階的に累積値の相対値を比較するため認識精度が低下することなく、高速に識別を行うことができる。
【００４５】
上述してきたように、本実施の形態によれば、画像入力部１１で入力した画像データを前処理部１２により前処理した後に特徴抽出部１３で特徴抽出し、候補選択部１６により、ユークリッド距離を用いて候補カテゴリーを選択し、候補絞込処理部１７により、射影軸を用いて候補カテゴリーを絞り込み、認識処理部１８により文字認識をおこなうよう構成したので、手書き文字などのパターンを認識する際に、高速かつ効率良く候補パターンを絞りつつ文字認識をおこなうことができる。
【００４６】
特に、従来から詳細判定で使用していた特徴量を用いて候補を絞っているため辞書に要するメモリ容量の累増を防止することができ、また、詳細判定を分割して候補を絞りながらおこなっているので、高速で高精度な認識をおこなうことができる。
【００４７】
なお、本実施の形態では、本発明を文字認識装置に適用した場合を示したが、本発明はこれに限定されるものではなく、部分空間を用いた認識であれば文字認識に限る必要はなく、他のパターン認識に広く適用することができる。
【００４８】
【発明の効果】
以上説明したように、請求項１の発明によれば、入力パターンと参照パターンをユークリッド距離を用いて照合して複数の候補パターンを選択し、選択された各候補パターンそれぞれについてカテゴリーの情報を多く含む順に特徴量の部分空間の射影軸を選択し、その上位の射影軸から順次該射影軸に入力パターンの特徴量を射影して各候補パターンの補正値を算出しつつ該算出された補正値を用いて各候補パターンの入力パターンと射影軸の距離を示す修正距離を求める処理を各射影軸に対して繰り返す際に、繰り返し途中の段階で第１の候補パターンの修正距離が最小値となる第２の候補パターンの修正距離よりも所定以上大きい場合に該第１の候補パターンを複数の候補パターンから除外して候補パターン数を絞り込むよう構成したので、手書き文字などのパターンを認識する際に、従来技術のように全ての候補パターンに対する射影軸を用いた修正距離の算出をそれぞれ最後まで行うのではなく、その途中の段階で候補パターン相互間の修正距離の相互関係を利用して明らかに候補パターンから除外すべきものを除外することになり、もって高速かつ効率良く候補パターンを絞り込むことが可能なパターン認識装置が得られるという効果を奏する。
【００５２】
また、請求項２の発明によれば、入力パターンと参照パターンをユークリッド距離を用いて照合して複数の候補パターンを選択し、選択された各候補パターンそれぞれについてカテゴリーの情報を多く含む順に特徴量の部分空間の射影軸を選択し、その上位の射影軸から順次該射影軸に入力パターンの特徴量を射影して各候補パターンの補正値を算出しつつ該算出された補正値を用いて各候補パターンの入力パターンと射影軸の距離を示す修正距離を求める処理を各射影軸に対して繰り返す際に、繰り返し途中の段階で第１の候補パターンの修正距離が最小値となる第２の候補パターンの修正距離よりも所定以上大きい場合に該第１の候補パターンを複数の候補パターンから除外して候補パターン数を絞り込むよう構成したので、手書き文字などのパターンを認識する際に、従来技術のように全ての候補パターンに対する射影軸を用いた修正距離の算出をそれぞれ最後まで行うのではなく、その途中の段階で候補パターン相互間の修正距離の相互関係を利用して明らかに候補パターンから除外すべきものを除外することになり、もって高速かつ効率良く候補パターンを絞り込むことが可能なパターン認識方法が得られるという効果を奏する。
【００５６】
また、請求項３の発明によれば、請求項２に記載された方法をコンピュータに実行させるプログラムを記録したことで、そのプログラムを機械読み取り可能となり、これによって、請求項２の動作をコンピュータによって実現することが可能な記録媒体が得られるという効果を奏する。
【図面の簡単な説明】
【図１】この発明の実施の形態に係る文字認識装置の構成を示す機能ブロック図である。
【図２】図１に示した特徴抽出部がおこなうメッシュ割りを説明するための説明図である。
【図３】図２に示した各メッシュ内の輪郭方向を説明するための説明図である。
【図４】図１に示した候補絞込処理部による候補カテゴリーの絞り込みの概念を説明するための説明図である。
【図５】図１に示した文字認識装置の処理手順を示すフローチャートである。
【図６】図１に示した候補絞込処理部の処理概念を説明するための説明図である。
【符号の説明】
１０  文字認識装置
１１  画像入力部
１２  前処理部
１３  特徴抽出部
１４  参照データ管理部
１５  参照データ記憶部
１６  候補選択部
１７  候補絞込処理部
１８  認識処理部
【図１】
0004215385.tif 000002
【図２】
0004215385.tif 000003
【図３】
0004215385.tif 000004
【図４】
0004215385.tif 000005
【図５】
0004215385.tif 000006
【図６】
0004215385.tif 000007