(57)【特許請求の範囲】
【請求項１】
各クラス毎の統計量をクラス標本数に応じた加重平均を用いて級内変動および級間変動を算出する算出手段を備えた正準判別分析装置であって、前記算出手段は、前記クラス標本数に応じた加重平均の代わりに、前記統計量の重みなし平均を用いることを特徴とする正準判別分析装置。
【請求項２】
学習パターンから抽出される第１の特徴ベクトルを標本として、請求項１記載の正準判別分析装置によって正準判別分析を行ない変換行列を求める手段と、未知のパターンが入力されたときには、該未知パターンから抽出される前記第１の特徴ベクトルに対して前記変換行列を作用させ、前記第１の特徴ベクトルより少ない次元数を持つ第２の特徴ベクトルに変換する手段を備えたことを特徴とする特徴抽出装置。
【請求項３】
各クラス毎の統計量を算出する手段と、クラス毎の統計量の重みなし平均を用いて級内変動および級間変動を算出する手段とを含む正準判別分析手段と、前記正準判別分析手段で得られる変換行列を保存する手段と、入力パターンから第１の特徴ベクトルを抽出する手段と、前記第１の特徴ベクトルに対して前記変換行列を作用させ、前記第１の特徴ベクトルより少ない次元数を持つ第２の特徴ベクトルに変換する手段とを備えたことを特徴とする特徴抽出装置。
【請求項４】
請求項１記載の正準判別分析装置の各手段として、コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項５】
請求項２または３記載の特徴抽出装置の各手段として、コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パターン認識に関し、特にパターンの次元数を削減し適切な変換行列を生成できる正準判別分析装置、該分析装置を用いた特徴抽出装置および記録媒体に関する。
【０００２】
【従来の技術】
一般に、パターン認識手法とは、入力パターンから特徴ベクトルを抽出し、これをあらかじめ用意した辞書の中の標準特徴ベクトルと照合し、最も整合するクラス（カテゴリ）を認識結果として出力する方法である。
【０００３】
例えば、若林他：「非線形正規化と特徴量の圧縮による手書き漢字認識の高精度化」，信学論Ｄ−ＩＩ，Ｖｏｌ．Ｊ７９−Ｄ−ＩＩ，Ｎｏ．５，ｐｐ．７６５−７７４（１９９６）では、手書き文字パターンを複数の小領域に分割し、各小領域中に存在する、方向別の文字輪郭画素数を重みつきでカウントし、それらの値を要素として持つ特徴ベクトルに対して、擬似ベイズ識別関数によるクラス分類を行なっている。
【０００４】
ここで特徴ベクトルは、パターンの形状に関する情報を効率良く含まなければならないが、一方でベクトルの要素間に強い相関があったり、分類に寄与しない冗長な要素をも含むのが普通である。
【０００５】
そこで前掲した文献では、学習データから抽出される特徴ベクトルを標本として、正準判別分析（重判別分析ともいう）を適用している。正準判別分析により、元の特徴ベクトルをさらに少数次元のベクトルへ変換する行列が得られる。変換後のベクトル要素が（級間変動／級内変動）比を最大にするように、すなわち同一クラスの標本同士をなるべく近く、異なるクラス同士をなるべく引き離すように選ばれているため、次元数削減による処理量の軽減のみならず、パターン認識精度の改善も期待できる。
【０００６】
【発明が解決しようとする課題】
前記変換行列を求めるには、級内変動Ｗと級間変動Ｂを用いた一般固有値問題を解く必要がある。従来の一般的な定式化にしたがうと、鳥脇著：「認識工学−パターン認識とその応用」，コロナ社（１９９３），ｐｐ．１０５−１０８で述べられているように、ＷやＢは各クラスに関する統計量の加重平均を用いて表され、その重みはそれぞれのクラスの標本数に依存する。具体的には次式となる。
【０００７】
【数１】
0004049288.tif 000002
ここでＣはクラス数、Ｎｉはクラスｉの標本数、Ｎは全クラスにわたる全標本数、ｍｉはクラスｉの学習データから抽出される特徴ベクトルの平均ベクトル、Ｓｉはクラスｉの標本分散行列である。上式で和Σの後にあるＮｉ／Ｎが重みということになる。
【０００８】
この方法では、級内変動や級間変動への各クラスの寄与は、その標本数が多いほど大きくなるが、正準判別分析の結果を未知パターンの認識へ応用する観点からいうと、あまり望ましいことではない。
【０００９】
例えば、手書き数字は日常のあらゆる場面でまんべんなく現れるので、多くの学習パターンを集めることができる。一方、手書き漢字は普段書かないような種類の字を多く含むことから、数字ほど多くの学習パターンを集めることは難しいのが実状である。
【００１０】
このように、数字の標本数と漢字の標本数に大きな違いがある場合に、前述の正準判別分析をそのまま行なうと、数字の寄与が大きくなりすぎてしまう。かわりに漢字の統計情報が考慮されなくなり、漢字のクラス分類には向かない結果が得られるであろう。
【００１１】
帳票の住所欄のように、記入される未知パターンが数字か漢字かわからないとき、あるいは数字よりも漢字の方が多く現れることがあらかじめわかっているとき、従来の方法では十分なクラス分離性を持つベクトルへの変換行列が得られないという問題があった。
【００１２】
本発明の目的は、クラス間で学習パターン数に差があっても、適切な変換行列を生成することのできる正準判別分析装置と、これを利用した特徴抽出装置および記録媒体を提供することにある。
【００１３】
【課題を解決するための手段】
本発明の正準判別分析装置では、各クラスの学習パターンから抽出される特徴ベクトルの統計量（各クラスの平均ベクトルと標本分散行列）を求め、級内変動および級間変動を、前記統計量の重みなし平均、または前記統計量の所定の重みにしたがった加重平均を用いて求める。また、第１の特徴ベクトルを標本として本発明の正準判別分析を行って変換行列を求め、未知パターンから抽出される第１の特徴ベクトルに対して変換行列を作用させることにより、少ない次元数の第２の特徴ベクトルに変換する。
【００１４】
【発明の実施の形態】
以下、本発明の一実施例を図面を用いて具体的に説明する。
（実施例１）
図１は、本発明の正準判別分析部の第１の構成を示す。図において、１０１は学習パターンから抽出された特徴ベクトルに関する各クラスの平均ベクトルや標本分散行列を算出する統計量算出部、１０２は統計量算出部で求められた各クラスの標本分散行列から級内変動を算出する級内変動算出部、１０３は統計量算出部で求められた各クラスの平均ベクトルから級間変動を算出する級間変動算出部であり、重み記憶部を持たない第１の構成の場合、重みなし平均をとる。級内変動および級間変動は一般固有値問題解法部１０４へ送られ、そこで求められた固有ベクトルから変換行列が生成される。
【００１５】
図４は、本発明の実施例１に係る正準判別分析処理のフローチャートを示す。本実施例では３クラスの場合について説明する。まず、統計量算出部１０１は各クラスの学習パターンから抽出される特徴ベクトルの統計量を求める。具体的には、それぞれのクラスの平均ベクトル、および標本分散行列を求める。
【００１６】
クラスＡのサンプル数をＮＡ（ステップ２０２），第ｉ番目のサンプルから抽出される特徴ベクトルをｘA（ｉ）とすると（ステップ２０３）、平均ベクトルは
【数２】
0004049288.tif 000003
標本分散行列は
【数３】
0004049288.tif 000004
となる（ステップ２０６）。クラスＢ，Ｃの平均ベクトルｍB、ｍCと標本分散行列ＳB、ＳCも同様に求められる（ステップ２０７，２０８）。
【００１７】
本実施例の級内変動算出部１０２および級間変動算出部１０３では、級内変動および級間変動を、前記統計量の重みなし平均を用いて求める。級内変動は
Ｗ＝（ＳA＋ＳB＋ＳC）／３                            式（５）
級間変動は
Ｂ＝｛（ｍA−Ｍ）（ｍA−Ｍ）t＋（ｍB−Ｍ）（ｍB−Ｍ）t＋（ｍC−Ｍ）
（ｍC−Ｍ）t｝／３                                      式（６）
（Ｍ＝（ｍA＋ｍB＋ｍC）／３）
から得られる（ステップ２０９，２１０）。この場合、クラス間の学習サンプル数に違いがあっても（例えばＮA：ＮB：ＮC＝１００：５００：１００００のように大きな隔たりがあっても）、各クラスの標本分散行列や平均ベクトルがＢ、Ｗに与える寄与は等しくなる。
【００１８】
続いて、一般固有値問題解法部１０４では、前記級内変動と級間変動を用いて一般固有値問題
Ｂａ＝λＷａ                                          式（７）
を解く（ステップ２１１）。互いに一次独立な固有ベクトルａは（クラス数−１）個得られるので、それ以下の適当な数の固有ベクトルを固有値λの大きい順に選択し、それらを行に並べたものが求める変換行列である（ステップ２１２）。
【００１９】
本実施例では２個の固有ベクトルを選択する。特徴ベクトルの次元数を２００，第ｉ固有ベクトルを
ａｉ＝（ａi,1,ａi,2,・・・,ａi,200）
とすると、２×２００の変換行列となり、その各成分は
【数４】
0004049288.tif 000005
となる。なお、クラス数や特徴ベクトルの次元数、選択する固有ベクトルの数が変わっても、本実施列と全く同様の手順で適切な変換行列を求めることができるのは明らかである。
【００２０】
（実施例２）
図２は、本発明の正準判別分析部の第２の構成を示す。図１の構成にさらに、あらかじめ定められた重みを保存する重み記憶部１０５が追加されている。統計量算出部１０１で求められた各クラスの標本分散行列から級内変動を算出する級内変動算出部１０２と、統計量算出部１０１で求められた各クラスの平均ベクトルから級間変動を算出する級間変動算出部１０３は、重み記憶部１０５から読み出された重みにもとづく加重平均をとる。
【００２１】
図５は、本発明の実施例２に係る正準判別分析処理のフローチャートを示す。実施例２では、級内変動、級間変動を求めるのに、各クラスの統計量をあらかじめ与えられた重み（重み記憶部１０２に保存）にしたがって加重平均する。実施例１と同じ状況を考えると、異なるのは式（５），（６）の定義だけである。
【００２２】
本実施例では、重みを、パターン認識対象におけるそれぞれのクラスの出現率とする。例えば、認識対象の原稿においてクラスＡが２０％，クラスＢが５０％，クラスＣが３０％の割合で出現し、他のクラスは現れないことがわかっているならば、級内変動は
Ｗ＝０．２ＳA＋０．５ＳB＋０．３ＳC                式（９）
級間変動は
Ｂ＝０．２（ｍA−Ｍ）（ｍA−Ｍ）t＋０．５（ｍB−Ｍ）（ｍB−Ｍ）t
＋０．３（ｍC−Ｍ）（ｍC−Ｍ）t                    式（１０）
（Ｍ＝０．２ｍA＋０．５ｍB＋０．３ｍC）
から得られる（ステップ３０９，３１０）。以降は実施例１と同じ手順によって２×２００の変換行列を得る（ステップ３１２）。
【００２３】
本実施例によれば、クラス間の学習サンプル数に違いがあっても（例えばＮA：ＮB：ＮC＝１００：５００：１００００のように大きな隔たりがあっても）、それとは関わりなく、出現率の高い重要なクラスほど級内変動や級間変動に対する寄与が大きくなるようにできる。
【００２４】
なお、本実施例で述べた出現率を重みとする他、実験的に最もパターン認識精度が高くなるような重み等、別の重みを用いることができるのは言うまでもない。
【００２５】
（実施例３）
本実施例は、実施例１または２によって求められた変換行列を、特徴ベクトル変換に適用した実施例である。図３は、本発明の特徴抽出装置を含むパターン認識装置の構成を示す。図において、１１１はスキャナー等で構成されるパターン入力部、１１２はパターンの正規化やノイズ除去等の画像処理を行なう前処理部、１１３はパターンから特徴ベクトルを抽出する特徴ベクトル抽出部であり、学習時には前述の正準判別分析部１１４へ特徴ベクトルが送られ、得られた変換行列が変換行列記憶部１１５に保存される。特徴ベクトルは特徴ベクトル変換部１１６へも送られ、ここで先に求められた変換行列を変換行列記憶部１１５から読み出し、特徴ベクトルに作用させ、より少ない次元数を持つベクトルに変換する。また、学習時には該ベクトルから標準特徴ベクトルを作成し、辞書１１７に保存しておく。
【００２６】
１１８は認識時に変換後の特徴ベクトルと辞書中の標準特徴ベクトルとのマッチングを行ない、クラス分類を決定するマッチング部、１１９は認識結果をディスプレイや記憶装置、通信装置、プリンタ等に出力する認識結果出力装置である。
【００２７】
図６は、特徴ベクトル変換処理のフローチャートを示す。特徴ベクトル抽出部１１３では、学習時に学習パターンから２００次元の特徴ベクトルを抽出し、これを標本として、正準判別分析部１１４において実施例１または２に述べた正準判別分析を行なって、２×２００の変換行列Ａを求め、変換行列記憶部１１５に格納しておく。
【００２８】
認識時に未知パターンが入力されると、特徴ベクトル抽出部１１３では、まず学習時と同じ２００次元の特徴ベクトルｘ＝（ｘ1,ｘ2,・・・,ｘ200）を抽出する（ステップ４０１）。この特徴ベクトルは特徴ベクトル変換部１１６に送られ、ここで先に求められた変換行列Ａを変換行列記憶部１１５から読み出す（ステップ４０２）。
【００２９】
次いで、特徴ベクトル変換部１１６は、特徴ベクトルｘに先の変換行列Ａを作用させる（ステップ４０５）。すなわち、Ａを左から掛けることにより、クラスＡ，Ｂ，Ｃを分類するための２次元の特徴量ｙ＝（ｙ1，ｙ2）に変換される（ステップ４１０）。
ｙ1＝ａ1,1ｘ1＋ａ1,2ｘ2＋・・・ａ1,200ｘ200
ｙ2＝ａ2,1ｘ1＋ａ2,2ｘ2＋・・・ａ2,200ｘ200            式（１１）
変換後の特徴ベクトルは次元数が少なくなるばかりでなく、同じクラスのベクトル同士は近くなるように、異なるクラスの平均ベクトルは互いに遠くなるように変換されているので、クラス分類に適しており、ひいてはパターン認識精度の向上にも寄与することができる。
【００３０】
（実施例４）
本発明はソフトウエアによっても実現することができる。本発明をソフトウエアによって実現する場合には、図７に示すように、ＣＰＵ、ＲＯＭ、ＲＡＭ、表示装置、ハードディスク、キーボード、ＣＤ−ＲＯＭドライブ、通信装置、スキャナなどからなる汎用の処理装置を用意する。ＣＤ−ＲＯＭなどのコンピュータ読み取り可能な記録媒体には、本発明に関わる正準判別分析処理機能、特徴抽出処理機能を実現するプログラムが記録されている。該プログラムが起動されると、スキャナからパターンを画像データとして入力するか、もしくはあらかじめハードディスクに保存されている画像データを読み出してＲＡＭ上に配置し、該データに対して正準判別分析処理や特徴抽出処理を実行する。
【００３１】
【発明の効果】
以上、説明したように、本発明によれば、正準判別分析において級内変動および級間変動を、各クラスの学習パターンから抽出される特徴ベクトルの統計量の重みなし平均、または前記統計量の所定の重みに基づく加重平均を用いて求めているので、各クラスの標本数に依存しないようにすることが可能である。また、未知パターンから抽出される特徴ベクトルを、パターン認識に適した少数次元の特徴ベクトルに変換することができる。
【図面の簡単な説明】
【図１】  本発明の正準判別分析部の第１の構成を示す。
【図２】  本発明の正準判別分析部の第２の構成を示す。
【図３】  本発明の特徴抽出装置を含むパターン認識装置の構成を示す。
【図４】  本発明の実施例１に係る正準判別分析処理のフローチャートを示す。
【図５】  本発明の実施例２に係る正準判別分析処理のフローチャートを示す。
【図６】  本発明の特徴ベクトル変換処理のフローチャートを示す。
【図７】  本発明をソフトウェアによって実現する場合の構成例を示す。
【符号の説明】
１０１  統計量算出部
１０２  級内変動算出部
１０３  級間変動算出部
１０４  一般固有値問題解法部
１０５  重み記憶部
１１１  パターン入力部
１１２  前処理部
１１３  特徴ベクトル抽出部
１１４  正準判別分析部
１１５  変換行列記憶部
１１６  特徴ベクトル変換部
１１７  辞書
１１８  マッチング部
１１９  認識結果出力部
【図１】
0004049288.tif 000006
【図２】
0004049288.tif 000007
【図３】
0004049288.tif 000008
【図４】
0004049288.tif 000009
【図５】
0004049288.tif 000010
【図６】
0004049288.tif 000011
【図７】
0004049288.tif 000012