(57)【要約】【課題】クラス毎のプロトタイプの分布が線形分離不可能、かつ、分散が互いに異なるスパースな分布のプロトタイプにおいても、入力パターンの高精度な識別を行う。【解決手段】入力したパターンのデータを識別する場合において、予め用意されたプロトタイプのデータを使用して、入力パターンデータのクラス毎の最近傍プロトタイプを決定し、その決定した最近傍プロトタイプと所定範囲の近傍のプロトタイプの集合を決定し、クラス毎の最近傍プロトタイプと所定範囲の近傍のプロトタイプにおける平均を算出し、入力したパターンとクラス毎の最近傍プロトタイプとの平均により重み付けした距離を算出し、算出した距離に基づいて入力パターンデータのプロトタイプを決定するようにした。【選択図】図３
2007226662.tif 000002
【特許請求の範囲】
【請求項１】
入力したパターンのデータを識別するパターン識別方法において、
予め用意されたプロトタイプのデータを使用して、入力パターンデータのクラス毎の最近傍プロトタイプを決定し、
前記決定した最近傍プロトタイプと、所定範囲の近傍のプロトタイプの集合を決定し、
前記クラス毎の最近傍プロトタイプと、前記所定範囲の近傍のプロトタイプにおける平均を算出し、
入力したパターンとクラス毎の最近傍プロトタイプとの平均により重み付けした距離を算出し、
算出した距離に基づいて、前記入力パターンデータのプロトタイプを決定することを特徴とするパターン識別方法。
【請求項２】
請求項１記載のパターン識別方法において、
前記平均は、ノルム平均であることを特徴とするパターン識別方法。
【請求項３】
請求項１記載のパターン識別方法において、
前記入力パターンは、文字又は数字のパターンであることを特徴とするパターン識別方法。
【請求項４】
請求項１記載のパターン識別方法において、
前記入力パターンは、個人認証用の画像のパターンであることを特徴とするパターン識別方法。
【請求項５】
請求項１記載のパターン識別方法において、
前記入力パターンは、音声認識用のパターンであることを特徴とするパターン識別方法。
【請求項６】
入力したパターンのデータを識別するパターン識別装置において、
プロトタイプのデータが予め用意されたプロトタイプ記憶部と、
前記プロトタイプ記憶部に用意されたプロトタイプのデータを使用して、入力パターンデータのクラス毎の最近傍プロトタイプを決定し、その最近傍プロトタイプと、その所定範囲の近傍のプロトタイプの集合を得る集合判定部と、
前記集合判定部で得られた、前記クラス毎の最近傍プロトタイプと、前記所定範囲の近傍のプロトタイプにおける平均を算出し、入力したパターンとクラス毎の最近傍プロトタイプとの平均により重み付けした距離を算出する距離算出部と、
前記距離算出部で算出した距離に基づいて、前記入力パターンデータのプロトタイプを決定する識別部とを備えることを特徴とするパターン識別装置。
【請求項７】
入力したパターンのデータを識別するパターン識別処理をデータ処理装置で実行するプログラムにおいて、
予め用意されたプロトタイプのデータを使用して、入力パターンデータのクラス毎の最近傍プロトタイプを決定する最近傍プロトタイプ決定ステップと、
前記最近傍プロトタイプ決定処理で決定した最近傍プロトタイプと、所定範囲の近傍のプロトタイプの集合を決定する集合決定ステップと、
前記クラス毎の最近傍プロトタイプと、前記所定範囲の近傍のプロトタイプにおける平均を算出する平均算出ステップと、
入力したパターンとクラス毎の最近傍プロトタイプとの平均により重み付けした距離を算出する距離算出ステップと、
前記距離算出ステップで算出した距離に基づいて、前記入力パターンデータのプロトタイプを決定するプロトタイプ決定ステップとを備えることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばスキャナやデジタルカメラで取り込まれた画像中の文字パターンから文字を識別する場合や、デジタルカメラやビデオカメラで取り込まれた画像中から個人認証を行う場合に適用して好適なパターン識別方法及びパターン識別装置、並びにその方法を実行するプログラムに関する。
【背景技術】
【０００２】
近年、デジタルカメラやカメラ付き携帯電話などのデジタル撮影機器の普及に伴い、文字認識の対象が従来のスキャナで入力された品質のよい文字画像から、カメラで撮った品質のよくない文字画像へ広がってきた。撮影画像の品質は、カメラのセンサの高性能化と共に大きく向上したが、撮影時の条件に大きく影響されるため、撮影距離、コントラスト、手ぶれなどの条件によっては、十分な品質が得られない場合が多い。このような低品質の画像に対し、いかにして認識精度を向上させるかが大きな課題となっている。
【０００３】
低品質文字の高精度な認識手法としては、複数枚の入力画像を用いて解像度を向上させる手法、つぶれ領域の影響を低減するように動的に重み付けを行う方法、つぶれに応じて認識辞書を補正する方法、文字の輪郭画像を利用してつぶれにより失われた輪郭を補完する手法、入力文字画像から推定した劣化状態により辞書を選択する方法、劣化モデルをもとに学習パターンを生成する方法など、多くの提案がなされている。一方、文字の変形に有効である識別法としては、未知パターンとカテゴリカル近傍平均パターンとの距離に基づくＣＡＰ法も報告されている。非特許文献１には、文字パターンの識別を、ｋ近傍決定則（以下ｋ−ＮＮ法と称する）で行うことについての開示がある。
【０００４】
ｋ−ＮＮ法について説明すると、この認識法では、予め画像のパターンをクラス分けして記憶しておく。例えば０から９までの数字を認識する例を想定する。この場合には、０から９までの数字のサンプル画像を予め複数個用意しておき、それぞれのサンプル画像がどの数字の画像であるか、クラス分けしておく。その際に、クラス分けされた各パターンについて、複数の特徴事項についての数値（特徴量）を抽出しておく。特徴の最も簡単な例としては、例えばパターンの幅と高さが考えられる。その他にも、パターン内の各部の曲がり具合などパターンを分類する上で必要な様々な特徴事項についての特徴量を抽出する。
【０００５】
このようにしてクラス分けされたパターン（プロトタイプ）が用意された状態で、認識したい画像である入力パターンが入力されると、その入力パターンとの特徴量の距離が小さい順に、予め決めた個数（この個数をｋ個と称する）のプロトタイプを選択する。次に、このｋ個のプロトタイプの中で、クラス毎に多数決をとり、最大数となったクラスを入力パターンが属するクラスとする。
【０００６】
図１１は、ｋ−ＮＮ法によるパターン認識処理の概念を説明する図である。この例では、パターン（数字）が「１」及び「３」の特徴の分布を示してあり、特徴としては、パターンの高さを縦軸に、幅を横軸にして、２次元で示してある。丸印は「１」のパターンの分布であり、三角印は「３」のパターンの分布であり、「３」の特徴を持つパターンの方が幅が広くなり、２つのクラスが異なる分布となっている。このような分布状態となっているときに、図１１中に四角印で示す位置の幅及び高さの未知パターンａが入力すると、そのｐターンは「３」の分布に近いため、未知パターンａは「３」のクラスのパターンであると認識される。
【０００７】
この図１１の例は、パターン認識処理の概念を示したもので、実際には、２つの特徴量だけでなく、より多くの数の特徴から判断するようにして、パターン認識精度を上げるようにした場合もある。例えば、３つの特徴量から判断することで、３次元的に分布が判断されるようにする場合もある。
【非特許文献１】電子情報通信学会論文集Vol.J88-D-II NO.8 第1357頁から第1366頁  ２００５年８月発行
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ところで、ｋ−ＮＮ法によるパターン認識処理では、各クラスのプロトタイプの分布が密である時には、入力パターンと最小距離となる各クラスにおけるプロトタイプ(クラス毎の最近傍プロトタイプ)による識別境界が、正解の識別境界に近似するため、最近傍決定則(k=1)により、高精度な識別が可能である。
【０００９】
即ち、例えば、第１のクラスのプロトタイプＣ１の分布（四角印の分布）と、第２のクラスのプロトタイプＣ２の分布（丸印の分布）とが、図１２に示す状態であるとする。ここでは、それぞれの分布は比較的密であるとする。このような密な状態では、両クラスの正確な境界Ｘ１と、プロトタイプＣ１，Ｃ２の分布から識別された境界Ｘ２とは、殆ど一致する。従って、このような状態では、三角で示す入力パターンＣ０が、いずれのクラスに属するかが、プロトタイプＣ１，Ｃ２の分布から識別されたクラスの境界Ｘ２を使用して、簡単にほぼ正確に判定できる。
【００１０】
しかしながら、分布が疎（スパース）な状態ではこのような正確な境界の設定は困難である。例えば、第１のクラスのプロトタイプＣ１の分布と、第２のクラスのプロトタイプＣ２の分布とが、図１３に示すように疎な状態であるとする。このとき、プロトタイプＣ１，Ｃ２の分布から識別されたクラスの境界Ｘ２は、ほぼ分布の中間をとるようになり、正確な境界Ｘ１から大幅にずれた位置となる可能性がある。この図１３に示した状態のときには、三角で示す入力パターンＣ０が、本来第１のクラスのプロトタイプＣ１と認識する必要があるのに、第２のクラスのプロトタイプＣ２と誤認識してしまう。このような誤認識があると、識別精度が大きく低下する恐れがある。
【００１１】
このようなプロトタイプの粗密を考慮した識別手法としては、従来、マハラノビス距離に基づく手法が提案されている。この手法は、各クラスの平均ベクトルと入力パターンとの距離を各クラス全体の共分散行列により重み付けを行う手法である。このマハラノビス距離に基づく手法は、プロトタイプの分布が楕円状である場合は識別精度の向上が期待できるが、楕円以外の任意形状で分布する場合には、識別精度が低下する可能性が高い。
【００１２】
なお、ここまでの問題点は、文字パターンを識別する場合の問題について説明したが、線形分離困難な状態で分布するパターンから識別する場合には、文字以外であっても同様の問題がある。
【００１３】
本発明はかかる点に鑑みてなされたものであり、クラス毎のプロトタイプの分布が線形分離不可能、かつ、分散が互いに異なるスパースな分布のプロトタイプにおいても、入力パターンの高精度な識別を行うことを目的とする。
【課題を解決するための手段】
【００１４】
本発明は、入力したパターンのデータを識別する場合において、予め用意されたプロトタイプのデータを使用して、入力パターンデータのクラス毎の最近傍プロトタイプを決定し、その決定した最近傍プロトタイプと所定範囲の近傍のプロトタイプの集合を決定し、クラス毎の最近傍プロトタイプと所定範囲の近傍のプロトタイプにおける平均を算出し、入力したパターンとクラス毎の最近傍プロトタイプとの平均により重み付けした距離を算出し、算出した距離に基づいて入力パターンデータのプロトタイプを決定するようにしたものである。
【発明の効果】
【００１５】
本発明によると、入力したパターンのデータの近傍のプロトタイプが比較的疎な状態であっても、正確にプロトタイプを決定することができ、認識率を効果的に向上させることができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の一実施の形態を、図１〜図１０を参照して説明する。
【００１７】
まず、本発明のパターン認識処理の概要について説明すると、本発明においては、スパースなプロトタイプの分布における、クラス毎の最近傍プロトタイプによる識別境界に注目する。この場合、正解の識別境界に対して、クラス毎の最近傍プロトタイプによる識別境界は、広範囲に分布するクラスのプロトタイプ側に移動する傾向がある。したがって、入力パターンと各クラスにおけるプロトタイプとの距離に基づく識別を行う際に、あるクラスにおけるプロトタイプの分散が大きいほど、入力パターンとそのクラスのプロトタイプの距離を短くするような重み付けを行うことにより、高精度な識別が可能となることが期待できる。このことから、本発明では、入力パターンとクラス毎の最近傍プロトタイプの距離を、クラス毎の最近傍プロトタイプとそのｋ近傍のプロトタイプにおける平均ベクトルと、この平均ベクトルの算出に用いた各プロトタイプとのノルムの平均に基づき重み付けを行い、最近傍決定則により識別を行うようにした。
【００１８】
次に、本発明の一実施の形態による具体的な処理例を説明する。図１は、本例の文字識別処理を行う文字識別装置の構成例を示したものである。ここでは、文字識別装置は、例えばコンピュータ装置とその周辺機器で構成してあり、コンピュータ装置に接続されたカメラ又はスキャナなど構成される画像取り込み部１１で、文字画像を取り込むようにしてあり、識別結果をディスプレイ２１に表示するようにしてある。コンピュータ装置には、文字識別装置として機能させるためのソフトウェア（プログラム）がインストールしてある。そのソフトウェアは、後述する図３のフローチャートに示す動作処理などを実行させるものであり、文字認識を行う上で必要な参照用のデータであるプロトタイプのデータについても予め用意されている。操作については、例えばコンピュータ装置に接続されたキーボード１７を使用する。
【００１９】
画像取り込み部１１で取り込まれた画像データは、データ処理部１２に送られ、制御部１５の制御で所定のデータとされる。このデータ処理時には、画像データ内の文字パターンから複数（ｎ個：ｎは２以上の自然数）の特徴についての量（特徴量）が抽出される。
【００２０】
抽出された特徴量のデータは、データメモリ１３に記憶される。また、プロトタイプのデータなどを記憶する記憶手段で構成されるデータベース１４を備える。データベース１４に記憶されるデータとしては、それぞれの文字について、複数種類用意されたデータであり、その文字データの特徴量などがデータベース化されている。なお、未知パターンを認識する処理を行った際には、その認識されたパターンを、新たな参照用のデータとして登録してもよい。データメモリ１３に記憶されたデータは、プログラムメモリ１６に記憶された文字認識用プログラムの指示に従って、制御部１５の制御で、データ処理部１２などでそのプロトタイプであるか（即ちどの文字であるか）認識処理される。認識処理結果は、例えば表示制御部１８に送られて、ディスプレイ２１に認識結果としての文字などを表示させる。
【００２１】
図２は、クラス分けされた参照用のプロトタイプの実例を示したものである。図２例は０から９までの数字の例としてあり、プロトタイプの種類（即ちどの数字であるか）を示すクラス番号が、数字ごとに付与してある。このクラス番号ごとに、パターン番号１，２，３・・・と、用意されたプロトタイプ数だけ番号を付与してある。
【００２２】
次に、このような装置構成で文字認識を行う処理例を、図３のフローチャートを参照して説明する。まず、入力した文字パターンがあると、その入力パターンについて、クラス毎の最近傍プロトタイプを決定する（ステップＳ１）。このクラス毎の最近傍プロトタイプの決定処理としては、例えば、識別する入力パターンをｉ，クラスｃにおけるｍ番目のプロトタイプをＰc(m)とする。ただし、クラスｃにおけるプロトタイプ数をnumcとし、ｉ，Ｐc(m)は、それぞれｒ次元の列ベクトルとする。ここで，各クラスｃにおいて、次式（１）を満たすプロトタイプＰc(m)を各クラスｃにおけるクラス毎の最近傍プロトタイプとして決定する。
【００２３】
【数１】
2007226662.tif 000003
【００２４】
次に、クラス毎の最近傍プロトタイプとそのｋ近傍のプロトタイプの集合を決定する（ステップＳ２）。ここでは、各クラスｃのプロトタイプＰc(ａc)に対するｋ近傍のプロトタイプを以下のように決定する。
【００２５】
まず、プロトタイプＰc(ａc)とそのｋ近傍のプロトタイプの集合を、Ｓck（＝｛Φ｝）とし、Ｐc(ａc)∈Ｓckとする。次に、クラスｃにおける全プロトタイプの集合Ｓcに対して、次式（２）を満たすプロトタイプＰc(j)を決定する。
【００２６】
【数２】
2007226662.tif 000004
【００２７】
さらに、プロトタイプの集合Ｓcから（２）式で決定したＰc(j)を除外し、Ｐc(j)∈Ｓckとする。再びプロトタイプの集合Ｓcから（２）式を満たすＰc(j)を決定する。この処理をｋ回繰り返すことにより、各クラスｃにおけるクラス毎の最近傍プロトタイプとそのｋ近傍のプロトタイプの集合Ｓckを決定する。
【００２８】
次に、クラス毎の最近傍プロトタイプとそのｋ近傍のプロトタイプにおける平均とノルム平均の算出を行う（ステップＳ３）。ここでは、まず、クラス毎の最近傍プロトタイプとそのｋ近傍のプロトタイプの集合Ｓckに含まれるプロトタイプの平均ベクトルｍｃを次式（３）により算出する。
【００２９】
【数３】
2007226662.tif 000005
【００３０】
次に、算出した平均ベクトルｍｃを用いて、プロトタイプの集合Ｓckに含まれるプロトタイプのノルム平均Ｃｃを次式（４）により算出する。
【００３１】
【数４】
2007226662.tif 000006
【００３２】
そして、入力パターンとクラス毎の最近傍プロトタイプとのノルム平均により重み付けした距離の算出を行う（ステップＳ４）。ここでは、各クラスｃにおいて、ｉとＰc(ａc)とのノルム平均Ｃｃにより重み付けした距離ｄｃを次式（５）により算出する。
【００３３】
【数５】
2007226662.tif 000007
【００３４】
そして、算出した距離に基づく入力パターンの識別を行う（ステップＳ５）。ここでは、算出した距離ｄｃを次式（６）で評価する。
【００３５】
【数６】
2007226662.tif 000008
【００３６】
この（６）式を満たすｄｇを算出したｇクラスを、ｉの属するクラスとして決定する。但し、全クラス数をｎｃとする。
【００３７】
図４は、ここまで説明した文字認識処理で認識した例を示した図である。この図４は、［発明が解決しようとする課題］の欄で説明した図１３（ｋ−ＮＮ法によるパターン認識処理）と同じ、疎（スパース）な状態のプロトタイプ分布での認識状態の例である。図１３の場合と同様に、第１のクラスのプロトタイプＣ１の分布（四角印の分布）と、第２のクラスのプロトタイプＣ２の分布（丸印の分布）とが、疎な状態となっていて、三角で示す入力パターンＣ０が何れのクラスに属するかが判定される。
【００３８】
この判定を行うために、図３のフローチャートに示す処理で、ノルム平均により重み付けした距離を算出することで、第１のクラスと第２のクラスと境界Ｘ０は、疎（スパース）な状態のプロトタイプ分布であっても、ほぼ実パターンのクラス境界と一致するようになり、いずれのプロトタイプに属するかがほぼ正確に判定できる。図４の例では、入力パターンＣ０は、第１のクラスに属することが認識される。
【００３９】
なお、図４の例では、縦軸に１つの特徴量をとり、横軸にそれとは別の特徴量をとり、２種類の特徴量を使用した２次元の分布として示してある。より多くの特徴量を使用して、より次元数（ｎ次元数）の高い分布から識別処理を行うことが可能である。
【００４０】
次に、本例の識別処理を実際に行って、ｋ−ＮＮ法によるパターン認識処理と比較した実験例について説明する。人工パターンに適用した例と実パターンに適用した例について説明する。
まず、人工パターンに適用した例について説明する。ここでは、２クラスのパターンの識別を行う。２クラスの線形分離不可能な人工パターンを生成するために、まず、以下の（７）式で示される超半球を考える。
【００４１】
【数７】
2007226662.tif 000009
【００４２】
ただし、ｘ１，ｘ２，・・・，ｘｎは、ｎ次元のパターンのベクトル成分とし、ｒｃは各クラスにおける超半球の半径とする。各クラスにおけるパターンのベクトルは、（７）式のｘ１，ｘ２，・・・，ｘｎを満たすランダムに与えたｎ次元のベクトル（ｘ１，ｘ２，・・・，ｘｎ）Ｔの各成分に、（８）式で示される確率分布を満たすｄをおのおの付加し、生成した。
【００４３】
【数８】
2007226662.tif 000010
【００４４】
なお、ここでは、パターンのベクトルの次元数ｎは２、クラス１，クラス２における（７）式ｒｃは、それぞれｒ１＝3.5、ｒ２＝１、また、（８）式におけるσは、それぞれ、0.70，0.15とした。
また、ここでの識別率Ｃｒは、（９）式で示される。
【００４５】
【数９】
2007226662.tif 000011
【００４６】
但し、Ｃnumはクラスの数、Ｐnumは、各クラスにおける入力パターンの数、Ｐｊ（ｉ）は、クラスの番号がｉであり，入力パターンの識別順番号がｊの入力パターンのベクトル、Ｄ（ｐｊ（ｉ））は、入力パターンＰｊ（ｉ）が、正解ならば１、不正解ならば０とする。ここでは、Ｃnum＝２、Ｐnum＝２００とする。
【００４７】
この人工パターンを使用した識別率を図５に示す。図５（ａ）は、従来手法（ｋ−ＮＮ法）による識別率を示し、図５（ｂ）は、本例の処理による識別率を示す。それぞれ、縦軸が識別率で、横軸は各クラスのプロトタイプ数を示し、ｋの数を１，３，５，７，９の例を示してある。
【００４８】
図５（ａ）に示すｋ−ＮＮ法の場合には、プロトタイプ数が増加するにつれ、識別率が向上していることが分かる。これは、プロトタイプ数が増加するにしたがって、プロトタイプによる識別境界が正解の識別境界に近似すること、また、入力パターンと最小距離となる各クラスにおけるプロトタイプ近傍のプロトタイプの粗密の差が各クラスで小さいことにより、識別率が高くなったと考える。また、プロトタイプ数が少ない、つまり、プロトタイプの分布がスパースであるとき、入力パターンと最小距離となる各クラスにおけるプロトタイプによる識別境界が正解の識別境界から大きく逸脱すること、また、入力パターンと最小距離となる各クラスにおけるプロトタイプ近傍のプロトタイプの粗密の差が各クラスで大きくなることにより、識別率が低くなったものと想定される。
【００４９】
これに対して、図５（ｂ）に示す本例の処理による識別率は、ｋ−ＮＮ法による識別率を上回っていることが分かる。さらに、プロトタイプ数が少ない、つまり、プロトタイプの分布がスパースであるほど、ｋ−ＮＮ法と本例との識別率の差が大きいことが分かる。これは、各クラスのプロトタイプの中で入力パターンと最短距離のプロトタイプと入力パターンとの距離を、各クラスのプロトタイプの中で入力パターンと最短距離のプロトタイプとそのプロトタイプと同じクラスの近傍のプロトタイプにおけるノルム平均で重み付けしたことにより、入力パターンと最小距離となる各クラスにおけるプロトタイプによる識別境界を正解の識別境界に近似できたためと想定される。
【００５０】
次に，次元数に対する各手法の識別率を示す。ここでの各クラスにおけるプロトタイプ数は２０個、入力パターンは各クラス１００個とした。
図６（ａ）は、従来手法（ｋ−ＮＮ法）による識別率を示し、図６（ｂ）は、本例の処理による識別率を示す。ｋ−ＮＮ法の場合には、次元数が上がる程、識別率が低下することが分かる。これは、次元数が上がるほど、プロトタイプ間の密度がスパースになることが原因であると考える。これに対して本例の場合では、次元数が増加しても、識別率は、高精度に保たれていることが分かる。
【００５１】
次に、実パターンに対して、本例の識別処理を適用した場合の例について説明する。ここでの実データとしては、文字識別用のデータベースであるMNIST[10]を用いた。ここでは、数字の0から9までの10クラスとし、それぞれ２８×２８[pixel]サイズで8[bit/pixel]階調の画像に対して、ラスタスキャンによりベクトル化し、識別処理を行った例としてある。この実データは、図２に示した実データに相当する。ここでは、パターンの次元数は、画像の画素数２８×２８=７８４とし、プロトタイプ数を変化させた場合の識別率により、ｋ−ＮＮ法と本例の手法を比較した。
【００５２】
図７は、プロトタイプ数10から100までの各手法における識別率を示す。Ｐrop．として示すのが本例の識別手法であり、ｋＮＮとして示すのがｋ−ＮＮ法による識別である。表１は、本例の識別手法とｋ−ＮＮ法の各プロトタイプ数における最適なｋの値を示す。この図７の識別結果により、本例の識別率はｋ−ＮＮ法の識別率を上回っていることが分かる。
【００５３】
【表１】
2007226662.tif 000012
【００５４】
図８に、プロトタイプ数785から1200までの各手法における識別率を示す。Ｐrop．として示すのが本例の識別手法であり、ｋＮＮとして示すのがｋ−ＮＮ法による識別であり、Maha.として示すのが、マハラノビス距離に基づく手法である。表２は、本例の識別手法とｋ−ＮＮ法の各プロトタイプ数における最適なｋの値を示す。
【００５５】
【表２】
2007226662.tif 000013
【００５６】
識別結果により、本例の識別手法とｋ−ＮＮ法の識別率は、マハラノビス距離に基づく手法による識別率を大きく上回っていることが分かる。また本例の識別手法とｋ−ＮＮ法の識別率は、ほぼ同等程度であることが分かる。このことから本例の識別処理は，プロトタイプ数の少ないスパースな場合において特に有効であることが分かる。
【００５７】
ここで、クラス１を「１」の文字、クラス２を「９」の文字とし、各クラスのプロトタイプ数をそれぞれ10個，1000個とした場合の各クラスの最近傍プロトタイプとそのｋ近傍(k=2)のパターンを図９及び図１０にそれぞれ示す。この例での各クラスのプロトタイプ数をそれぞれ10個とした場合の各クラスの最近傍プロトタイプとそのｋ近傍(k=2)のパターンのノルム平均は、クラス１のとき702.0であり、クラス２のとき814.0である。また、各クラスのプロトタイプ数をそれぞれ1000個とした場合の各クラスの最近傍プロトタイプとそのｋ近傍(k=2)のパターンのノルム平均は、クラス１のとき375.5であり、クラス２のとき635.3である。なお、ここでの各クラスの最近傍プロトタイプは、お互いのプロトタイプに対して、ユークリッド距離が最短となるパターンとした。
【００５８】
図９及び図１０に示されるように、各クラスのプロトタイプ数が、多い場合、各クラスの最近傍プロトタイプとそのｋ近傍のプロトタイプの類似性が高いことがわかる。また、上述したノルム平均の値より、各クラスのプロトタイプ数が1000個の場合に比べ10個の場合、各クラスにおけるノルム平均が増加することがわかる。これは、各クラスの最近傍プロトタイプとそのｋ近傍のプロトタイプの類似性が低くなるためである。またこの場合、ノルム平均の増加率が、クラス毎に異なることが分かる。これは、プロトタイプ数が低下すると各パターンによりプロトタイプの粗密の差が大きくなることが原因である。よって、入力パターンと各クラスにおける最近傍プロトタイプとの距離をノルム平均で重み付けし、入力パターンを識別することは、非常に有効である。
【００５９】
以上説明したように、本例によると、クラス毎の最近傍プロトタイプとそのｋ近傍のプロトタイプにおけるノルム平均に基づく最近傍決定則によるパターン識別を行うことで、クラス毎のプロトタイプの分布が線形分離不可能、かつ、分散が互いに異なるスパースな分布のプロトタイプにおいても、入力パターンの高精度な識別を行うことができる。
【００６０】
上述したように、人工パターンに対して本例の識別処理を適用したことで、従来手法に比べ、プロトタイプ数を変化させた場合、次元数を変化させた場合、共に識別率が向上する効果を有する。特に、プロトタイプの分布がスパース（疎）な場合において、識別率の向上が顕著である。また、実パターンに適用した場合においても、本例の識別処理は、他の手法に比べ、識別率が向上する効果を有する。
【００６１】
なお、ここまで説明した認識率などのデータについては一例を示したものであり、未知パターンの状態や学習データなどにより変わるものである。
【００６２】
また、上述した実施の形態では、文字識別装置は、コンピュータ装置を使用して構成させる例を示したが、専用の文字識別装置として構成させるようにしてもよい。また、コンピュータ装置を使用する場合に必要なソフトウェア（プログラム）については、ディスクなどの各種記憶媒体に記憶させて配布する他に、インターネットなどを経由して配布するようにしてもよい。
【００６３】
また、ここまでの説明では、本発明の認識処理を印刷文字（未知パターン）の認識に適用した例について説明したが、その他の未知パターンの認識処理に適用してもよい。例えば、ビデオカメラで撮影された顔画像や表情の認識処理に適用してもよい。このような顔画像の場合、サンプル画像の数が少ないことが想定されるので、本発明を適用することで良好な認識が期待できる。顔画像認識装置の応用としては、ロボットにおける視覚認識処理、モンタージュ画像などとの比較処理、ホテルや商店での顧客管理処理、交通システムでの画像認識処理などに適用可能である。
【図面の簡単な説明】
【００６４】
【図１】本発明の一実施の形態によるシステム構成例を示す構成図である。
【図２】本発明の一実施の形態による識別処理で使用されるパターンの例を示す説明図である。
【図３】本発明の一実施の形態による識別処理例を示すフローチャートである。
【図４】本発明の一実施の形態による識別境界の例を示す説明図である。
【図５】従来のｋ−ＮＮ法（ａ）と、一実施の形態による識別処理法（ｂ）の識別率を示す説明図である。
【図６】従来のｋ−ＮＮ法（ａ）と、一実施の形態による識別処理法（ｂ）の次元数に対する識別率を示す説明図である。
【図７】本発明の一実施の形態によるプロトタイプ数１０から１００までの各手法による識別率の例を示す説明図である。
【図８】本発明の一実施の形態によるプロトタイプ数７８５から１２００までの各手法による識別率の例を示す説明図である。
【図９】本発明の一実施の形態による識別処理を適用した場合のｋ近傍のパターンの例（プロトタイプ数１０個の例）を示す説明図である。
【図１０】本発明の一実施の形態による識別処理を適用した場合のｋ近傍のパターンの例（プロトタイプ数１０００個の例）を示す説明図である。
【図１１】従来のｋ−ＮＮ法によるパターン認識の概念を示す説明図である。
【図１２】従来のプロトタイプの分布が密な場合の識別例を示す説明図である。
【図１３】従来のプロトタイプの分布が疎な場合の識別例を示す説明図である。
【符号の説明】
【００６５】
１１…画像取り込み部、１２…データ処理部、１３…データメモリ、１４…データベース、１５…制御部、１６…プログラムメモリ、１７…キーボード、１８…表示制御部、１９…ディスプレイ
【図１】
2007226662.tif 000014
【図２】
2007226662.tif 000015
【図３】
2007226662.tif 000016
【図４】
2007226662.tif 000017
【図５】
2007226662.tif 000018
【図６】
2007226662.tif 000019
【図７】
2007226662.tif 000020
【図８】
2007226662.tif 000021
【図９】
2007226662.tif 000022
【図１０】
2007226662.tif 000023
【図１１】
2007226662.tif 000024
【図１２】
2007226662.tif 000025
【図１３】
2007226662.tif 000026