(57)【要約】【課題】入力画像に対してパターン認識を実行するパターン認識プログラム、装置、及び方法に関し、学習サンプルがある範囲を特徴空間上に記述する際の正確性を向上させる。【解決手段】特徴空間において、学習サンプルのパターンを種別する各カテゴリＡ、Ｂ、Ｃ等の分布形状に合わせた軸群（軸１、２、３、４）が設定される。次に、カテゴリ毎に、カテゴリの学習サンプルから抽出される特徴ベクトルに対応する特徴空間上の特徴点を設定された軸群の各軸に投影して得られるカテゴリ範囲とカテゴリとを対応付けた辞書が作成される。そして、与えられた未知のパターンから抽出される特徴ベクトルに対応する特徴空間上の特徴点を設定された軸群の各軸に投影して得られる位置が含まれるカテゴリ範囲が抽出され、抽出されたカテゴリ範囲に対応するカテゴリの集合が出力されることにより、与えられたパターンが属するカテゴリが例えば大分類される。【選択図】図６
2019096118.tif 000002
【特許請求の範囲】
【請求項１】
学習サンプルのパターンを種別する各カテゴリの特徴空間内の分布形状に合わせた軸群を設定し、
前記カテゴリ毎に、前記カテゴリの学習サンプルから抽出される特徴ベクトルに対応する前記特徴空間上の特徴点を前記軸群の各軸に投影して得られるカテゴリ範囲に基づいて、与えられたパターンを分類する、
処理をコンピュータに実行させるためのパターン認識プログラム。
【請求項２】
前記カテゴリ毎に、前記カテゴリの学習サンプルから抽出される特徴ベクトルに対応する前記特徴空間上の特徴点を前記軸群の各軸に投影して得られるカテゴリ範囲と前記カテゴリとを対応付けた辞書を作成し、
与えられたパターンから抽出される特徴ベクトルに対応する前記特徴空間上の特徴点を前記軸群の各軸に投影して得られる位置が含まれる前記カテゴリ範囲を抽出し、前記抽出したカテゴリ範囲に対応するカテゴリの集合を出力することにより、前記与えられたパターンが属するカテゴリを分類する、
処理を更に前記コンピュータに実行させるための請求項１に記載のパターン認識プログラム。
【請求項３】
前記軸群を設定する処理において、
前記カテゴリ毎に前記学習サンプルの特徴ベクトルから固有ベクトルを算出し、その結果得られる全ての固有ベクトルをクラスタリングして、類似している固有ベクトル同士が同一のクラスタに分類されたクラスタ集合を出力する処理と、
前記クラスタ集合中で固有ベクトル数が最も多いクラスタを選択しながら、前記選択したクラスタの代表ベクトルを含み、相互に所定の誤差内で直交する代表ベクトルを前記クラスタ集合から算出して軸候補として軸候補群に順次追加する処理と、
前記軸候補群に含まれる前記軸候補の数が所定の閾値を超えるまで、又は前記各カテゴリの学習サンプルに対応する前記特徴空間上の特徴点を前記軸候補群に含まれる各軸候補に投影して得られるカテゴリ範囲の前記特徴空間内の交差領域に前記特徴点が存在しない領域が無くなるまで、前記軸候補を前記軸候補群に順次追加する処理を繰り返し実行した後に、前記軸候補群を前記軸群として出力する処理と、
を実行する請求項１又は２に記載のパターン認識プログラム。
【請求項４】
前記軸群を設定する処理において、
全ての前記カテゴリの全ての前記学習サンプルの特徴ベクトルから所定個数の固有ベクトルを共通軸として求める処理と、
前記カテゴリ毎に、前記カテゴリの学習サンプルに対応する前記特徴空間上の特徴点を前記各共通軸に投影することにより前記共通軸上のカテゴリ範囲を抽出する処理と、
前記各共通軸を軸候補群に含ませた後、前記カテゴリ毎に、前記各共通軸上のカテゴリの範囲の前記特徴空間内の交差領域に前記カテゴリの学習サンプルに対応する特徴点が１つもない領域がある場合に、前記カテゴリの学習サンプルの特徴ベクトルのみから固有値と固有ベクトルを算出し、前記固有値の大きい順に前記固有ベクトルを新たな追加軸として前記軸候補群に追加する処理を、前記軸候補群内の軸で定義される前記特徴空間内の前記カテゴリの範囲に前記カテゴリの学習サンプルに対応する特徴点が１つもない領域がなくなるまで繰り返す処理と、
を実行する請求項１又は２に記載のパターン認識プログラム。
【請求項５】
コンピュータが
特徴空間において、学習サンプルのパターンを種別する各カテゴリの分布形状に合わせた軸群を設定し、
前記カテゴリ毎に、前記カテゴリの学習サンプルから抽出される特徴ベクトルに対応する前記特徴空間上の特徴点を前記軸群の各軸に投影して得られるカテゴリ範囲に基づいて、与えられたパターンを分類する、
パターン認識方法。
【請求項６】
特徴空間において、学習サンプルのパターンを種別する各カテゴリの分布形状に合わせた軸群を設定する設定部と、
前記カテゴリ毎に、前記カテゴリの学習サンプルから抽出される特徴ベクトルに対応する前記特徴空間上の特徴点を前記軸群の各軸に投影して得られるカテゴリ範囲に基づいて、与えられたパターンを分類する分類部と、
を備えるパターン認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力画像に対してパターン認識を実行するパターン認識プログラム、装置、及び方法に関する。
【背景技術】
【０００２】
入力画像に対するパターン認識の例としては、文書画像上の各文字の種別（文字コード）を認識する文字認識がある。このようなパターン認識では、認識精度を高精度に保ったまま、認識処理にかかる時間を削減して高速化することが求められている。
【０００３】
パターン認識において、認識対象のことをパターンと呼び、すべてのパターンの作る集合のことをパターン空間と呼ぶ。パターンに対して特徴抽出を行うことにより得られる１つ以上の特徴量の組を特徴ベクトルと呼び、特徴ベクトルの要素の数を特徴ベクトルの次元と呼ぶ。特徴ベクトルのそれぞれの要素の値（特徴量）の組を特徴ベクトルの値と呼び、すべての特徴ベクトルの値の作る集合のことを特徴空間と呼ぶ。特徴空間の次元は、特徴空間の要素である特徴ベクトルの次元と等しい。同一種類とみなすことのできるパターンあるいは特徴ベクトルの集合をカテゴリと呼ぶ。パターン認識のために入力される未知のパターンあるいは未知のパターンから求められた特徴ベクトルが、どのカテゴリに属するのかを決定することを、パターン認識と呼ぶ。
【０００４】
例えば未知の文字画像に対して文字認識を行うパターン認識処理では、入力された文字画像から特徴ベクトルが生成され、メモリ上の辞書に保持されている複数の特徴ベクトルとの間でマッチングが行われる。マッチング処理では、入力文字画像の特徴ベクトルと、辞書内の各特徴ベクトル間で距離（例えばユークリッド距離）が計算される。この計算を行う処理を、マッチング処理という。この結果、辞書中の特徴ベクトル数分の距離値が得られ、その中で、最小の距離値となる特徴ベクトルに対応付けられている文字コードが、入力文字画像に対する文字の認識結果（パターン認識結果）として出力される。
【０００５】
このような例のパターン認識処理において、未知の入力画像の特徴ベクトルと辞書内の全ての特徴ベクトルとの間のマッチング処理には、多くの処理時間が必要となる。そこで、マッチング処理の高速化のために、大分類、詳細分類の２段階処理が用いられる。大分類とは、辞書の中の特徴ベクトルの集合から、認識対象である入力文字画像から生成した特徴ベクトルに近い特徴ベクトルを抽出し、詳細分類をする際の対象を絞り込む処理である。絞り込んだ文字コードだけを対象として詳細分類をすると、従来のマッチング処理時間を大幅に削減することが可能になる。
【０００６】
パターン認識のための大分類技術として、例えば次のような従来技術が知られている（例えば特許文献１）。この従来技術では、学習用の各文字画像から得た特徴ベクトルが、特徴空間の各次元の軸（直交軸）に投影されて、各軸上に文字のカテゴリ（文字の種別＝文字コード）の存在範囲を記録した辞書が作成される。大分類時には、未知の入力画像の特徴ベクトルが各軸に投影され、各軸で求めた文字カテゴリ集合との論理ＡＮＤがとられ、その結果が大分類結果とされる。
【０００７】
パターン認識のための他の大分類技術として、例えば次のような従来技術が知られている（例えば非特許文献１、２）。この従来技術は、Ｈａｓｈ法の一つであるＬＳＨ（Ｌｏｃａｌｉｔｙ  Ｓｅｎｓｉｔｉｖｅ  Ｈａｓｈｉｎｇ）を用いた大分類技術である。ＬＳＨは、直交軸ではなく、ランダムに生成した軸を使用してＨａｓｈｉｎｇにより大分類を行う技術である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１１−１００２４５号公報
【非特許文献】
【０００９】
【非特許文献１】P. Indyk and R. Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality.”, STOC, pp.604-613, 1998.
【非特許文献２】A. Gionis, P. Indyk and R. Motwani, "Similarity Search in High Dimensions via Hashing," Proceedings of the 25th International Conference on Very Large Database (VLDB), pp.518-529, 1999.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述の直交軸を用いた大分類技術は、他の手法と比較して、分類正解率、絞り込み能力、処理速度の点から性能の良い大分類技術である。しかし、この従来技術は、全カテゴリで共通の直交座標系を使用しているため、特徴空間上で学習サンプルが無い領域が、辞書上で学習サンプルがあるように扱われてしまう。
【００１１】
一方、ＬＳＨを用いた従来技術では、ランダムな多数軸を使用するので、特徴空間上の学習サンプルの分布は正確にとらえられるため、絞り込み精度は高くなる傾向にある。しかし、軸数の決め方がランダムなので、精度の保証がなく、多くの軸を使用するので、処理時間がかかってしまう。
【００１２】
そこで、本発明の１つの側面では、学習サンプルがある範囲を特徴空間上に記述する際の正確性を向上させることを目的とする。
【課題を解決するための手段】
【００１３】
態様の一例のパターン認識プログラムは、特徴空間において、学習サンプルのパターンを種別する各カテゴリの分布形状に合わせた軸群を設定する処理を、コンピュータに実行させる。次に、パターン認識プログラムは、カテゴリ毎に、カテゴリの学習サンプルから抽出される特徴ベクトルに対応する特徴空間上の特徴点を軸群の各軸に投影して得られるカテゴリ範囲に基づいて、与えられたパターンを分類する処理を、コンピュータに実行させる。
【発明の効果】
【００１４】
学習サンプルがある範囲を特徴空間上に記述する際の正確性を向上させることが可能となる。
【図面の簡単な説明】
【００１５】
【図１】画像からの文字認識における特徴ベクトルと特徴空間の関係、及び特徴ベクトルを説明する図である。
【図２】特許文献１に係る本出願人によるパターン認識のための大分類技術の説明図である。
【図３】ハッシュテーブルを用いた辞書の表現形式及び大分類方式の説明図である。
【図４】特許文献１に係る本出願人によるパターン認識のための大分類技術の問題点の説明図である。
【図５】パターン認識装置の第１の実施形態のブロック図である。
【図６】第１の実施形態の説明図である。
【図７】特徴抽出部及び固有ベクトル抽出部の処理例を示すフローチャートである。
【図８】階層的クラスタリングの説明図である。
【図９】階層的クラスタリング部の処理例を示すフローチャートである。
【図１０】クラスタ選択部、直交軸決定部、及び軸出力判定部の処理例を示すフローチャートである。
【図１１】直交軸決定部の詳細処理例を示すフローチャートである。
【図１２】パターン認識装置の第２の実施形態のブロック図である。
【図１３】第２の実施形態の説明図（その１）である。
【図１４】第２の実施形態の説明図（その２）である。
【図１５】第２の実施形態の説明図（その３）である。
【図１６】第２の実施形態の処理例を示すフローチャートである。
【図１７】実施形態のパターン認識装置を実現可能なコンピュータのハードウェア構成例を示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。まず本実施形態の詳細について説明する前に、その前提となる特徴ベクトル及び特徴空間について説明する。
【００１７】
図１は、画像からの文字認識における特徴ベクトルと特徴空間の関係を説明する図である。パターン認識では、辞書または認識対象の画像は、その画像から抽出した特徴量の数値を並べたベクトルである特徴ベクトルで表現される。１つの文字画像は、特徴ベクトルで表現されるので、ベクトルの次元数の軸数を持つ特徴空間を考えると、１つの特徴ベクトルは、特徴空間内の１点として表現される。例えば、パターン認識の一例として文字認識が実行される場合、図１に例示される文字画像１０１（ここでは「あ」という文字が表示されている）が入力されたら、それが図１に例示されるｎ個の要素値からなる特徴ベクトル１０２＝（ｖ1 ，ｖ2 ，・・・，ｖn ）で表現される。
【００１８】
図１の１０５及び１０６は、文字画像からの特徴ベクトルの抽出方式を示す図である。この例では、以下の手続きに従い、「方向指数ヒストグラム」を用いた特徴ベクトル１０２が抽出される。
【００１９】
手続１：文字画像１０５から輪郭を構成する各画素を抽出する。
手続２：輪郭画素を、「｜」「／」「―」「＼」の４方向の何れかに分類する。
画素の分類方法としては、注目する画素の８近傍画素のどの方向に
輪郭画素値が存在するかによって分類する。
【００２０】
手続３：文字画像１０５をｎ×ｎ（図１の例では３×３）の領域に分割し、
各分割された領域内の方向毎の画素数を求める。
１０６として示される方向毎の画素数を「方向指数ヒストグラム」と呼ぶ。
手続４：分割領域の順番（領域１から９）に、方向指数の数値を並べて、
特徴ベクトル１０２とする。図１１０５及び１０６の例では、
９領域×４方向＝３６個の方向指数を要素値とする特徴ベクトル１０２
＝（ｖ1 ，ｖ2 ，・・・，ｖ36 ）が得られる。
【００２１】
特徴ベクトル１０２の次元数がｎ次元である場合、図１に例示される文字画像１０１内の１つの文字は、図１に例示されるようなｎ次元の特徴空間１０３の中の１点１０４で表すことができる。
【００２２】
次に、本実施形態の基礎技術となる、本出願人が先に出願したパターン認識のための大分類技術について説明する。図２は、特許文献１に係る本出願人によるパターン認識のための大分類技術の説明図である。学習用の全画像のサンプルパターンから直交軸が決定される。図２では、説明を簡単にするために、Ｘ軸とＹ軸の２次元の直交軸が決定されている。次に、各カテゴリ（例えば文字認識だったら文字種別）の学習用の各サンプルパターンの特徴ベクトルが、上記直交軸で定まる特徴空間の各次元の軸（例えばＸ軸及びＹ軸）に投影されて、各軸上に文字のカテゴリ（文字の種別＝文字コード）の存在範囲を記録した辞書が作成される。そして、パターン認識の大分類時には、未知の入力画像の特徴ベクトルが各軸に投影され、各軸で求めた文字カテゴリ集合との論理ＡＮＤがとられ、その結果が大分類結果とされる。
【００２３】
上記大分類処理の具体的な処理について以下に説明する。まず、１つのカテゴリ（例えば１つの文字種別）の１つの学習用サンプルパターンの特徴ベクトルの要素（例えば図１のｖ1 ，ｖ2 ，・・・，ｖn の何れか）（図２の例の場合は２次元なのでｖ1 ，ｖ2 の何れか）が１つ抽出される。そして、抽出された要素に対応する軸上の位置が算出される。例えば、要素ｖ1 については、その要素のＸ軸上の値（位置）が算出される。同様に、要素ｖ2 については、その要素のＹ軸上の値（位置）が算出される。
【００２４】
次に、上記１つのカテゴリ（例えば１つの文字種別）について、パターンの形が細かく変形した他の全ての学習用サンプルパターンについても同様の処理が実行される。例えば文字認識の場合、同じ文字「あ」でも、様々に変形された「あ」が存在する。これらがそれぞれ、学習用サンプルパターンとして与えられる。この結果、１つのカテゴリについて、各軸上の範囲が決定される。なお、各範囲の両端には、所定のマージン（ｍａｒｇｉｎ）が加えられる。例えば図２の例では、カテゴリＡの特徴空間内での特徴点が「Ａ」で示される３つの位置にあったとする。このとき、各特徴点「Ａ」の特徴ベクトルについて、その特徴ベクトルのｘ要素値がＸ軸上の位置に投影され、ｙ要素値がＹ軸上の位置に投影されることにより、カテゴリＡの各特徴ベクトルに関して、Ｘ軸上の範囲２０１ＡｘとＹ軸上の範囲２０１Ａｙが算出される。これらの結果に各軸毎にマージンが加えられることにより、カテゴリＡについて、Ｘ軸上の範囲２０２ＡｘとＹ軸上の範囲２０２Ａｙが算出される。
【００２５】
以上と同様の処理が他のカテゴリについても実行される。図２の例において、他のカテゴリＢの特徴空間内での特徴点が「Ｂ」で示される３つの位置にあったとする。このとき、特には図示しないが、各特徴点「Ｂ」の特徴ベクトルについて、Ｘ軸上の範囲２０１ＢｘとＹ軸上の範囲２０１Ｂｙが算出される。これらの結果に各軸毎にマージンが加えられることにより、特には図示しないが、カテゴリＢについて、Ｘ軸上の範囲２０２ＢｘとＹ軸上の範囲２０２Ｂｙが算出される。
【００２６】
更に同様に、図２において、カテゴリＣの特徴空間内での特徴点が「Ｃ」で示される３つの位置にあったとする。このとき、特には図示しないが、各特徴点「Ｃ」の特徴ベクトルについて、Ｘ軸上の範囲２０１ＣｘとＹ軸上の範囲２０１Ｃｙが算出される。これらの結果に各軸毎にマージンが加えられることにより、特には図示しないが、カテゴリＣについて、Ｘ軸上の範囲２０２ＣｘとＹ軸上の範囲２０２Ｃｙが算出される。
【００２７】
以上の動作が繰り返されることにより、各カテゴリ毎に、特徴空間内の各直交軸上の範囲の値を構成要素とする辞書が作成される。この場合、特徴空間内での各カテゴリの特徴点の範囲は、そのカテゴリの各直交軸上の範囲の交差部分領域として定義される。図２の例では、Ｘ軸とＹ軸とで定義される特徴空間内でのカテゴリＡの特徴点の範囲は、カテゴリＡについて、Ｘ軸上の範囲２０２ＡｘとＹ軸上の範囲２０２Ａｙとが交差する実線の四角で囲まれた４つの領域として定義される。また、上記特徴空間内でのカテゴリＢの特徴点の範囲は、カテゴリＢについて、Ｘ軸上の範囲２０２ＢｘとＹ軸上の範囲２０２Ｂｙ（共に図示せず）とが交差する細かい破線の四角で囲まれた１つの領域として定義される。更に、上記特徴空間内でのカテゴリＣの特徴点の範囲は、カテゴリＣについて、Ｘ軸上の範囲２０２ＣｘとＹ軸上の範囲２０２Ｃｙ（共に図示せず）とが交差する粗い破線の四角で囲まれた１つの領域として定義される。
【００２８】
以上のようにして作成された辞書を用いて、未知のパターン（例えば入力文字）ｘを大分類する場合の処理は、以下の通りとなる。未知パターンｘの特徴ベクトルの各要素、図２の例ではｘ要素値とｙ要素値がそれぞれ、Ｘ軸及びＹ軸のどのカテゴリの範囲に対して重なるか又は最も近いかが判定される。図２の例では、未知パターンｘの特徴点「Ｘ」は、Ｘ軸では、カテゴリＣの範囲に重なり、カテゴリＡの範囲に近い。また、Ｙ軸では、カテゴリＡ及びＣの各範囲に重なる。これより、未知パターンｘは、カテゴリＡ及びＣに大分類される。
【００２９】
図３は、ハッシュテーブルを用いた上記辞書の表現形式及び大分類方式の説明図である。各軸Ｋ（Ｋ＝１〜ｎ）（ｎは次元数）毎に、各カテゴリＡ、Ｂ、Ｃ等毎に、軸Ｋ上の各値に対応するｉ＝１〜最大値までのインデックス値毎に、各カテゴリの範囲が存在するか（＝１）否か（＝０）が設定された辞書ビット列ｂｉｔ１AK、ｂｉｔ１BK、ｂｉｔ１CK等からなる、ハッシュテーブル辞書３０１が作成される。未知パターンｘが入力されたとき、その特徴ベクトルのｋ番目の要素値の軸Ｋ上での位置に対応する各辞書ビット列ｂｉｔ１AK、ｂｉｔ１BK、ｂｉｔ１CK等の各ｋビット目の値の集合として、未知パターンｘの軸Ｋに対するマッチング結果ビット列ｂｉｔ２xKが得られる。このようにして得られる全ての軸Ｋ（Ｋ＝１〜ｎ）毎のマッチング結果ビット列ｂｉｔ２xKについて、ビット位置毎にＡＮＤ積が演算されることにより、最終マッチング結果ビット列ｂｉｔ３x （図示せず）が得られる。このｂｉｔ３x 中で値１が設定されているビット位置に対応するカテゴリが、大分類結果とされる。
【００３０】
上述した大分類手法は、高速な大分類処理を可能とする技術であるが、実際には特徴点が存在しないカテゴリ範囲が指定されてしまう場合がある。図２の例では、カテゴリＡについて、４つの実線枠で示される特徴空間上のカテゴリ範囲のうち、左上の実線枠２０３Ａと右下の実線枠２０４Ａの範囲には実際にはカテゴリＡの特徴点は存在しないにもかかわらず、カテゴリＡの範囲と判定されてしまう。例えば、図４において（見方は図２と同様）、未知パターンｘの特徴点「Ｘ」が、特徴空間内のカテゴリＡに対応する実線枠で囲まれた４つの領域のうちの右下の領域２０４Ａ内に存在する場合を想定する。未知パターンｘの特徴ベクトルの各要素値をＸ軸及びＹ軸に投影させたときの位置は、共にまずカテゴリＢのＸ軸上の範囲及びＹ軸上の範囲に含まれる。このため、上記未知パターンｘはまず、カテゴリＢに大分類される。これと共に、未知パターンｘの特徴ベクトルの各要素値をＸ軸及びＹ軸に投影させたときの位置は、カテゴリＡのＸ軸上の範囲２０２Ａｘ及びＹ軸上の範囲２０２Ａｙにも含まれる。このため、上記未知パターンｘは、カテゴリＡにも大分類されてしまう。しかし実際には、図４に示されるように、未知パターンｘの特徴点「Ｘ」は、カテゴリＡの特徴点「Ａ」が実際に存在する領域には含まれておらず、正解の大分類結果はカテゴリＢのみである。従って、この大分類手法では、カテゴリＡが余計に選択されてしまっているため、大分類処理の絞り込み能力が低下している。
【００３１】
上記大分類手法において、「学習サンプルが無い領域」だけを削除する手法が考えられる。しかし、このような領域は図３で説明したような辞書の記述では削除できないため、大分類処理の中でチェック処理を行うことになる。このため、大分類処理が遅くなる課題がある。
【００３２】
以下に説明するパターン認識装置の第１及び第２の実施形態は、上記課題を解決する技術である。各実施形態の手法は、処理時間をかけて特徴分布を正確に反映する辞書を作成し、精度を落とさずに大分類処理を高速化する手法である。具体的には、学習サンプルの各カテゴリの特徴の分布に合わせて、なるべく少ない軸数で各カテゴリの分布形状を識別できるような軸が設定される。軸は直交する軸セットを基本とし、互いに直交しない複数のセットで構成する。これにより、特徴空間上に学習サンプルがある範囲がより忠実に辞書に記述できるようになる。未知パターン（例えば未知入力文字）は、図２から図４で説明した大分類手法よりも狭いカテゴリの範囲にプロットされるため、より正確に大分類結果のカテゴリを絞り込むことが可能となる。
【００３３】
図５は、パターン認識装置の第１の実施形態のブロック図である。第１の実施形態は、特徴抽出部５０１、固有値・固有ベクトル抽出部５０２、階層的クラスタリング部５０３、クラスタ選択部５０４、直交軸決定部５０５、及び軸出力判定部５０６を含む。５０１から５０６の各部は、特徴空間において、学習サンプルのパターンを種別する各カテゴリの分布形状に合わせた軸群を設定する設定部に対応する。また、パターン認識装置は、分類部（不図示）をさらに含む。
【００３４】
特徴抽出部５０１は、カテゴリ１からカテゴリＮのＮ個のカテゴリ毎に用意されるそれぞれ複数サンプルからなる学習サンプルの文字画像５１０から、それぞれ特徴量を抽出する。これにより、特徴抽出部５０１は、カテゴリ１からカテゴリＮのＮ個のカテゴリ毎にそれぞれ複数組ずつの特徴ベクトル５１１を出力する。
【００３５】
固有ベクトル抽出部５０２は、カテゴリ毎に、そのカテゴリに対応する複数組の特徴ベクトル５１１から固有ベクトルを算出し、その結果得られる全ての固有ベクトルを、軸の候補として第１軸集合５１２に含ませる。
【００３６】
階層的クラスタリング部５０３は、第１軸集合５１２に含まれる固有ベクトルをクラスタリングして、類似している固有ベクトル同士が同一のクラスタに分類されたクラスタ集合５１３を出力する。
【００３７】
クラスタ選択部５０４は、クラスタ集合５１３中で構成要素の固有ベクトル数が最も多い未選択のクラスタを選択する（以下「選択クラスタ」と記載）。
【００３８】
直交軸決定部５０５は、選択クラスタの代表ベクトルを含み、相互にほぼ直交する代表ベクトルが格納された第３軸集合５１５を、クラスタ集合５１３から算出する。
【００３９】
軸出力判定部５０６は、第３軸集合５１５中の各代表ベクトルを第２軸集合５１４（軸候補群）に追加する。軸出力判定部５０６は、第２軸集合５１４に含まれる代表ベクトルの数が所定の閾値を超えるまで、又は学習サンプルが無い領域（図４参照）が無くなるまで、クラスタ選択部５０４及び直交軸決定部５０５による処理を繰り返し実行させる。軸出力判定部５０６は、上記条件が判定された時点で第２軸集合５１４に含まれる各代表ベクトルを各出力軸として含む出力軸集合５１６（軸群）を出力する。
【００４０】
その後、カテゴリ１からカテゴリＮのそれぞれ毎に、複数組ずつの特徴ベクトル５１１によって決まる各特徴点を、出力軸集合５１６中の各軸に投影させることにより、そのカテゴリの各軸上の範囲がマージン付きで決定された辞書が作成される。辞書データの表現形式は、前述した図３の場合と同様のハッシュデータ形式である。そして、このような辞書を用いて、与えられたパターンから抽出される特徴ベクトルに対応する特徴空間上の特徴点を出力軸集合５１６中の各軸に投影して得られる位置が含まれるカテゴリ範囲が抽出され、その範囲に対応するカテゴリの集合が出力される。これらの処理を実行する部分は、カテゴリ毎に、カテゴリの学習サンプルから抽出される特徴ベクトルに対応する特徴空間上の特徴点を軸群の各軸に投影して得られるカテゴリ範囲に基づいて、与えられたパターンを分類する分類部の一部に対応する。
【００４１】
上述の第１の実施形態で作成された出力軸集合５１６中の各軸を用いることにより、図２から図４で説明した従来の大分類手法と比較して、大分類した集合の中に正解が入る精度は変えないまま、絞り込み能力をより向上させることが可能となる。図４で説明したように、従来の大分類手法では、カテゴリによっては特徴空間上で、学習サンプルがない無駄なカテゴリ領域が生じていた。これにより、図４では未知パターンｘはカテゴリＢに加えてカテゴリＡにも大分類されてしまっていた。これに対して、第１の実施形態では、出力軸集合５１６から得られる例えば図６に示されるような軸１から軸４が用いられることにより、上記無駄なカテゴリ領域が生じることを回避することができる。そのため、無駄なカテゴリ領域が減るので、大分類時に入力した未知パターンと近くないカテゴリが選択されることを防ぐことができる。その結果、大分類の精度は変えずに、処理時間を短縮することが可能となる。図６の例では、例えばカテゴリＡについて、軸１のカテゴリＡの範囲と軸２のカテゴリＡの範囲とから６０１Ａとして示される領域が定まり、軸３のカテゴリＡの範囲と軸４のカテゴリＡの範囲とから６０２Ａとして示される領域が定まる。この結果、軸１から４で定義される特徴空間上のカテゴリＡの範囲は、領域６０１Ａと６０２Ａが重なる領域６００Ａとして決まる。このカテゴリＡの範囲６００Ａには、カテゴリＡの特徴点が１つも存在しない領域は無い。カテゴリＢとカテゴリＣについても同様に、各カテゴリの特徴点が１つも存在しない領域が除去された、細かい破線で示される領域と粗い破線で示される領域がそれぞれ、カテゴリＢ及びＣの各範囲として定まる。このようなカテゴリ範囲から作成された辞書を用いることで、未知パターンｘの特徴空間内の特徴点「Ｘ」を軸１、軸２、軸３、及び軸４に投影した結果、各投影結果のＡＮＤ積が正しくカテゴリ「Ｂ」のみと重なるように大分類を行うことができる。
【００４２】
図７は、図５の特徴抽出部５０１及び固有ベクトル抽出部５０２の処理例を示すフローチャートである。まず、特には図示しない制御部が、第１軸集合５１２を空集合に設定する（ステップＳ７０１）。
【００４３】
次に、図５において、制御部が、カテゴリ１からカテゴリＮのうち、未処理のカテゴリ（以降「選択カテゴリ」と記載）を１つ選択する（ステップＳ７０２）。
【００４４】
次に、特徴抽出部５０１が、選択カテゴリに対する図５の文字画像５１０の集合を入力する（ステップＳ７０３）。更に、特徴抽出部５０１が、ステップＳ７０３で入力した選択カテゴリの文字画像５１０の集合からそれぞれ、特徴ベクトル５１１の集合を抽出する（ステップＳ７０４）。特徴ベクトル５１１としては例えば、図１の１０５及び１０６で説明した「方向指数ヒストグラム」を用いたベクトルが採用される。
【００４５】
続いて、固有ベクトル抽出部５０２が、ステップＳ７０４で算出された選択カテゴリの特徴ベクトル５１１の集合から、固有ベクトルの集合を抽出する（ステップＳ７０５）。固有ベクトルは、例えば以下のようにして算出される。
【００４６】
いま１つのカテゴリ（文字認識の場合は例えば「あ」などの１種類の文字）について、ｍ個の文字画像を収集して、それらを全てｎ次元の特徴ベクトルに変換するとする。
【００４７】
このとき、第ｋ番目のベクトルを、下記（１）式で定義する。
【００４８】
【数１】
2019096118.tif 000003
【００４９】
このカテゴリの平均ベクトルは、下記（２）式で表される。
【００５０】
【数２】
2019096118.tif 000004
【００５１】
このとき、上記平均ベクトルの第i要素は、下記（３）式で定義される。
【００５２】
【数３】
2019096118.tif 000005
【００５３】
（１）式で表現される各ベクトル（ｋ番目のベクトル）と、（２）式及び（３）式で表現される平均ベクトルの各要素から、共分散行列Σが算出される。この共分散行列Σの第i行、第j列の要素σijは,下記（４）式により算出される。
【００５４】
【数４】
2019096118.tif 000006
【００５５】
次にｎ×ｎの共分散行列Σを対象に、下記（５）式で示される固有方程式を作成する。ここで、Ｅはｎ×ｎの単位行列である。
【００５６】
【数５】
2019096118.tif 000007
【００５７】
次に（５）式の方程式を解くことにより、固有値λを求める。λはｎ個の解を持つ。
更に、上記固有値の解の中の１つのλの値を使って、下記（６）式で示される方程式を解くことにより、ｎ次元の固有ベクトルxを１つ求める。この計算を各固有値の解について繰り返すことにより、ｎ個の固有値と固有ベクトルの組を求める。
【００５８】
【数６】
2019096118.tif 000008
【００５９】
固有ベクトル抽出部５０２は、このようにして抽出した固有ベクトルの集合を第１軸集合５１２に追加する（ステップＳ７０６）。
【００６０】
制御部は、カテゴリ１からカテゴリＮのうちの全てのカテゴリについて選択が終了したか否かを判定する（ステップＳ７０７）。制御部は、ステップＳ７０７の判定がＮＯならば、ステップＳ７０２の処理に戻って、次の選択カテゴリに対する上記ステップＳ７０２からＳ７０６の一連の処理を実行する。
【００６１】
制御部は、ステップＳ７０７の判定がＹＥＳになると、第１軸集合５１２を出力する（ステップＳ７０８）。その後、制御部は、図７のフローチャートで例示される特徴抽出部５０１と固有ベクトル抽出部５０２による上記繰返し処理を終了する。
【００６２】
以上のようにして、図７のフローチャートで例示される図５の特徴抽出部５０１及び固有ベクトル抽出部５０２の処理により、選択カテゴリ毎に特徴ベクトル５１１及び固有ベクトルが算出され、その固有ベクトルによって定義される選択カテゴリに対する特徴空間の軸が第１軸集合５１２に得られる。
【００６３】
次に、図５の階層的クラスタリング部５０３の処理例について説明する。階層的クラスタリング処理では、第１軸集合５１２として得られている固有ベクトルについて、重心に近いものは重心に集めてクラスタにまとめ、重心と重心との距離が離れていれば、別クラスタになるようなクラスタリングが行われる。階層的クラスタリングは、最も似ている組み合わせから順番にまとまり（クラスタ）にしていく方法である。例えば、階層的クラスタリング処理の一手法である凝集型（ａｇｇｌｏｍｅｒａｔｉｖｅ）では、Ｎ個の対象からなるデータが与えられたとき、１個の対象だけを含むＮ個のクラスタがある初期状態が、最初に生成される。この初期状態から、クラスタ間の距離（非類似度）ｄ（Ｃ１，Ｃ２）が計算され、最もこの距離の近い２つのクラスタが逐次的に１つのクラスタにまとめられる。この処理が、全ての対象が１つのクラスタにまとめられるまで繰り返されることで、階層構造が獲得される。
【００６４】
図８は、階層的クラスタリング処理の説明図である。図８は、説明の簡単のために、各カテゴリＡ、Ｂ、Ｃの各固有ベクトルが、２次元の特徴空間上に存在している例を示している。図８の特徴空間において、第１軸集合５１２中のカテゴリＡの軸ベクトル（固有ベクトル）が、１、２、３、及び４番の特徴点（記号「Ａ」からの矢印で指し示される部分）で示されている。また、カテゴリＢの軸ベクトルが、５、６、７、及び８番の特徴点（記号「Ｂ」からの矢印で指し示される部分）で示されている。更に、カテゴリＣの軸ベクトルが、９、１０，１１、及び１２番の特徴点（記号「Ｃ」からの矢印で指し示される部分）で示されている。上述の階層的クラスタリング処理において、初期状態は、１から１２までの全ての１つの番号をそれぞれ１つずつ含む１２個のクラスタからスタートする。そして、最終的には、カテゴリＡの２番とカテゴリＣの９番及び１１番とが１つのクラスタにまとめられる。また、カテゴリＡの１番とカテゴリＣの１０番及び１２番とが１つのクラスタにまとめられる。更に、カテゴリＢの５、８、７番が１つのクラスタにまとめられる。カテゴリＡの４番、カテゴリＡの３番、及びカテゴリＢの６番は、それぞれ単独のクラスタを形成する。以上の階層的クラスタリング処理により、それぞれのカテゴリから第１軸集合５１２に得られる軸ベクトル（固有ベクトル）のうち、似た軸同士が１つの軸（＝クラスタ）で代表されることになる。
【００６５】
図９は、上述の階層的クラスタリング処理の手法に基づく図５の階層的クラスタリング部５０３の処理例を示すフローチャートである。まず、階層的クラスタリング部５０３は、固有ベクトル抽出部５０２が出力した第１軸集合５１２中の各固有ベクトルをそれぞれ１クラスタの代表ベクトルとみなしてクラスタ集合５１３を作成し、全クラスタ間の距離を算出する(ステップＳ９０１)。距離としては例えば、各２つのクラスタの代表ベクトル間のユークリッド距離が算出される。
【００６６】
次に、階層的クラスタリング部５０３は、ステップＳ９０１で算出した距離のうち、最も小さい距離Ｄｍｉｎを算出した２つのクラスタを求める（ステップＳ９０２）。
【００６７】
次に、階層的クラスタリング部５０３は、上記最小距離Ｄｍｉｎが、所定の閾値よりも小さいか否かを判定する（ステップＳ９０３）。ステップＳ９０３の判定がＹＥＳならば、階層的クラスタリング部５０３は、ステップＳ９０２で算出した２つのクラスタを統合して１つの新クラスタとする(ステップＳ９０４)。
【００６８】
次に、階層的クラスタリング部５０３は、ステップＳ９０４で生成した新クラスタに属する固有ベクトルの数を、新クラスタを生成した２つのクラスタにそれぞれ属する固有ベクトルの数の合計の値とする（ステップＳ９０５）。また、階層的クラスタリング部５０３は、ステップＳ９０４で生成した新クラスタを生成した元の２つのクラスタを、クラスタ集合５１３から削除する（ステップＳ９０６）。更に、階層的クラスタリング部５０３は、ステップＳ９０４で生成した新クラスタを、クラスタ集合５１３に追加する（ステップＳ９０７）。
【００６９】
続いて、階層的クラスタリング部５０３は、ステップＳ９０４で生成した新クラスタを生成した元の２つのクラスタの代表ベクトルの例えば平均又は重心を算出することにより、上記新クラスタの代表ベクトルを算出する。そして、階層的クラスタリング部５０３は再び、ステップＳ９０１の場合と同様にして、クラスタ集合５１３内の全クラスタ間の距離を算出する(ステップＳ９０８)。その後、階層的クラスタリング部５０３は、ステップＳ９０３の処理に戻り、クラスタリングを繰り返す。
【００７０】
以上の繰返し動作の結果、階層的クラスタリング部５０３は、クラスタ集合５１３中の各クラスタ間の距離が十分に離れて、ステップＳ９０３で最小距離Ｄｍｉｎが所定の閾値よりも小さくなったと判定すると、ステップＳ９０９の処理に進む。ステップＳ９０９において、階層的クラスタリング部５０３は、ステップＳ９０２からＳ９０８の一連の処理の繰返しによる階層的クラスタリング処理を終了し、作成したクラスタ集合５１３を出力する。その後、階層的クラスタリング部５０３は、図９のフローチャートで例示される処理を終了する。
【００７１】
図１０は、図５のクラスタ選択部５０４、直交軸決定部５０５、及び軸出力判定部５０６の処理例を示すフローチャートである。まず、クラスタ選択部５０４は、第２軸集合５１４を空集合に設定する（ステップＳ１００１）。
【００７２】
次に、クラスタ選択部５０４は、階層的クラスタリング部５０３が出力したクラスタ集合５１３の中で、選択済み以外で、構成要素の固有ベクトル数が最も多いクラスタを選択する（以降このクラスタを「選択クラスタ」と記載）。クラスタ選択部５０４は、クラスタ集合５１３において選択クラスタを選択済みとする（以上、ステップＳ１００２）。
【００７３】
次に、直交軸決定部５０５が、ステップＳ１００２で選択した選択クラスタの代表ベクトルを含み、相互にほぼ直交する代表ベクトルが格納された第３軸集合５１５を、クラスタ集合５１３から算出する（ステップＳ１００３）。この処理の詳細については、図１１のフローチャートを用いて後述する。
【００７４】
次に、軸出力判定部５０６は、第３軸集合５１５中の各代表ベクトルを第２軸集合５１４に追加し、第３軸集合５１５中の各代表ベクトルのクラスタを、クラスタ集合５１３で選択済みとする（ステップＳ１００４）。
【００７５】
次に、軸出力判定部５０６は、第２軸集合５１４中の代表ベクトルの数が、所定の閾値よりも大きくなったか否かを判定する（ステップＳ１００５）。
【００７６】
軸出力判定部５０６は、ステップ９０５の判定がＹＥＳになったら、第２軸集合５１４内の各代表ベクトルを辞書で用いられる出力軸として、それらの軸が格納された出力軸集合５１６を出力する（ステップＳ１０１０）。その後、軸出力判定部５０６は、図１０で例示されるフローチャートの処理を終了する。
【００７７】
軸出力判定部５０６は、ステップＳ１００５の判定がＮＯの場合、学習サンプルから得られたカテゴリ１からＮのそれぞれ毎に、そのカテゴリ内の複数組ずつの特徴ベクトル５１１（図５参照）によって決まる各特徴点を、第２軸集合５１４中の全ての軸に投影させる。これにより、軸出力判定部５０６は、図２の場合と同様にして、各カテゴリの第２軸集合５１４中の各軸上の範囲を、マージンを付加して算出する（以上、ステップＳ１００６）。
【００７８】
その後、軸出力判定部５０６は、ステップＳ１００７からＳ１００９の一連の処理を繰り返し実行する。まず、軸出力判定部５０６は、図５のカテゴリ１からＮのうちの一つを選択する（ステップＳ１００７）。
【００７９】
次に、軸出力判定部５０６は、第２軸集合５１４内の全軸で構成される特徴空間上の、ステップＳ１００７で選択したカテゴリの存在範囲内に、学習サンプルの特徴点が無い領域（図４参照）があるか否かを判定する（ステップＳ１００８）。
【００８０】
軸出力判定部５０６は、ステップＳ１００８の判定がＮＯの場合、カテゴリ１からＮのうちの全てのカテゴリを選択したか否かを判定する（ステップＳ１００９）。
【００８１】
軸出力判定部５０６は、ステップＳ１００９の判定がＮＯならば、ステップＳ１００７の処理に戻って、次のカテゴリを選択し捨てＳ１００８の判定を繰り返す。
【００８２】
軸出力判定部５０６は、ステップＳ１００９の判定がＹＥＳになると、第２軸集合５１４内の各代表ベクトルを辞書で用いられる軸データとして、それらの軸データが格納された出力軸集合５１６を出力する（ステップＳ１０１０）。その後、軸出力判定部５０６は、図１０で例示されるフローチャートの処理を終了する。
【００８３】
軸出力判定部５０６は、ステップＳ１００７からＳ１００９の繰返し処理で、第２軸集合５１４内の全軸の特徴空間上の選択カテゴリの存在範囲内に、学習サンプルの特徴点が無い領域がある（ステップＳ１００８の判定がＹＥＳ）と判定すると、ステップＳ１００２に戻る。このようにして、軸出力判定部５０６は、クラスタ選択部５０４及び直交軸決定部５０５による処理を繰り返し実行させる。ステップＳ１００２からＳ１００９の一連の動作は、第２軸集合５１４中の代表ベクトル数が閾値を超えるまで（ステップＳ１００５の判定がＹＥＳ）、又は学習サンプルが無い領域（図４参照）が無くなるまで（ステップＳ１００９の判定がＹＥＳ）、繰り返し実行される。ここで、クラスタ選択部５０４で最初に選択された選択クラスタと、ステップＳ１００８の後に次に選択された選択クラスタとは、互いに直交するとは限らない。従って、最終的に、出力軸集合５１６に含まれる軸は非直交軸を含んでもよい。
【００８４】
図１１は、図１０のステップＳ１００３の、直交軸決定部５０５の詳細処理例を示すフローチャートである。まず、直交軸決定部５０５は、図５で、特徴ベクトル５１１の次元数を変数ｄにセットする。また、直交軸決定部５０５は、階層的クラスタリング部５０３が出力したクラスタ集合５１３と、クラスタ選択部５０４が図１０のステップＳ１００２で選択した選択クラスタの代表ベクトルを入力する（以上、ステップＳ１１０１）。
【００８５】
次に、直交軸決定部５０５は、第３軸集合５１５に選択クラスタの代表ベクトルのみを格納し、第３軸集合５１５の代表ベクトルの数を示す変数ｎに値「１」をセットする（ステップＳ１１０２）。
【００８６】
更に、直交軸決定部５０５は、クラスタ内固有ベクトル数最大値Ｍａｘを０にリセットし、クラスタ選択フラグＴに未選択状態を示す値「−１」をセットする（ステップＳ１１０３）。
【００８７】
その後、直交軸決定部５０５は、クラスタ集合５１３から、図１０のステップＳ１００２、Ｓ１００４、又は後述する図１１のステップＳ１１１０で選択済みとされたクラスタ以外の、１つのクラスタ（以降「クラスタＣ」と記載）を選択する（ステップＳ１１０４）。
【００８８】
次に直交軸決定部５０５は、クラスタＣの代表ベクトルと第３軸集合５１５内の全ての代表ベクトルとの内積値を計算し、その内積値が所定の閾値よりも小さいか否か、すなわち２つの代表ベクトルがほぼ直交しているか否かを判定する（ステップＳ１１０５）。
【００８９】
直交軸決定部５０５は、ステップＳ１１０５の判定がＹＥＳの場合、クラスタＣの構成要素である固有ベクトルの数がクラスタ内固有ベクトル数最大値Ｍａｘよりも大きいか否かを判定する（ステップＳ１１０６）。
【００９０】
直交軸決定部５０５は、クラスタＣの固有ベクトル数がいままでの最大値Ｍａｘよりも大きければ（ステップＳ１１０６の判定がＹＥＳなら）、ステップＳ１１０７の処理を実行する。直交軸決定部５０５は、ステップＳ１１０７で、クラスタ選択フラグＴにクラスタＣのクラスタ番号をセットし、クラスタ内固有ベクトル数最大値ＭａｘにクラスタＣを構成する固有ベクトルの数をセットする。直交軸決定部５０５は、クラスタＣの固有ベクトル数がいままでの最大値Ｍａｘよりも大きくなければ（ステップＳ１１０６の判定がＮＯなら）、ステップＳ１１０７の処理はスキップする。
【００９１】
その後、直交軸決定部５０５は、クラスタ集合５１３内で、図１０のステップＳ１００２、Ｓ１００４、又は後述する図１１のステップＳ１１１０で選択済みとされたクラスタ以外の未選択クラスタを全て調査したか否かを判定する（ステップＳ１１０８）。
【００９２】
直交軸決定部５０５は、ステップＳ１１０８の判定がＮＯならば、ステップＳ１１０４の処理に戻って、次の未選択クラスタの調査を繰り返し実行する。
【００９３】
直交軸決定部５０５は、ステップＳ１１０８の判定がＹＥＳとなると、クラスタ選択フラグＴの値が「−１」でないか否か、即ち第３軸集合５１５内の全ての代表ベクトルとほぼ直交する代表ベクトルが得られたか否かを判定する（ステップＳ１１０９）。
【００９４】
直交軸決定部５０５は、ステップＳ１１０９の判定がＹＥＳならば、クラスタ集合５１３中で、クラスタ選択フラグＴに設定されている番号のクラスタの代表ベクトルを第３軸集合５１５に追加する。また、直交軸決定部５０５は、クラスタ集合５１３で、上記番号のクラスタを選択済みとする（ステップＳ１１１０）。
【００９５】
このようにして、第３軸集合５１５内の全ての代表ベクトルとほぼ直交し、かつ構成要素である固有ベクトルの数が最大のクラスタが１つ選択されて、第３軸集合５１５に新たに追加されることになる。
【００９６】
更に、直交軸決定部５０５は、第３軸集合５１５内の代表ベクトルの数を示す変数ｎの値を＋１する（ステップＳ１１１１）。
【００９７】
その後、直交軸決定部５０５は、クラスタ内固有ベクトル数最大値Ｍａｘを０にリセットし、クラスタ選択フラグＴに未選択状態を示す値「−１」をセットする（ステップＳ１１１２）。
【００９８】
直交軸決定部５０５は、第３軸集合５１５内の代表ベクトルの数を示す変数ｎの値が、特徴ベクトル５１１の次元数を示す変数ｄの値よりも小さいか否かを判定する（ステップＳ１１１３）。
【００９９】
直交軸決定部５０５は、ステップＳ１１１３の判定がＹＥＳならば、ステップＳ１１０４の処理に戻って、第３軸集合５１５内の全ての代表ベクトルとほぼ直交し、かつ構成要素である固有ベクトルの数が次に多いクラスタの選択及び第３軸集合５１５への追加が繰り返し試みられる。
【０１００】
直交軸決定部５０５は、上述の繰返し処理で、次の条件が満たされた場合に、第３軸集合５１５を出力して（ステップＳ１１１４）、図１１のフローチャートで例示される図１０のステップＳ１００３の処理を終了する。この終了条件は、第３軸集合５１５内の全ての代表ベクトルとほぼ直交する代表ベクトルが得られなくなった（ステップＳ１１０９の判定がＮＯ）と判定された場合である。又は、第３軸集合５１５内の代表ベクトルの数ｎが特徴ベクトル５１１の次元数ｄに達した（ステップＳ１１１３の判定がＮＯ）と判定された場合である。
【０１０１】
図１０及び図１１のフローチャートの処理では、できるだけ多くの固有ベクトルが含まれるクラスタが選択され、その代表ベクトルを含み相互にほぼ直交する代表ベクトルが選択されるときにもできるだけ多くの固有ベクトルが含まれるクラスタが選択される。この処理により、できるだけ多くのカテゴリの範囲を無駄なく包含できる代表ベクトルからなる出力軸集合５１６を取得することができる。このようにして作成された出力軸集合５１６中の各軸を用いることで、特徴空間上で学習サンプルがない無駄なカテゴリ領域を除くことができ、大分類時に、精度は変えずに処理時間を短縮でき、絞り込み能力の向上が実現される。
【０１０２】
図１２は、パターン認識装置の第２の実施形態のブロック図である。第２の実施形態は、特徴抽出部５０１、共通軸抽出部１２０１、各カテゴリ範囲抽出部１２０２と、軸追加カテゴリ判定部１２０３と、軸追加部１２０４、及び軸出力判定部１２０５を含む。
【０１０３】
特徴抽出部５０１は、図５の特徴抽出部５０１と同じであり、カテゴリ１からカテゴリＮのＮ個のカテゴリ毎に用意されるそれぞれ複数サンプルからなる学習サンプルの文字画像５１０から、それぞれ特徴量を抽出する。これにより、特徴抽出部５０１は、カテゴリ１からカテゴリＮのＮ個のカテゴリ毎にそれぞれ複数組ずつの特徴ベクトル５１１を出力する。文字画像５１０及び特徴ベクトル５１１はそれぞれ、図５の文字画像５１０及び特徴ベクトル５１１と同じものである。
【０１０４】
共通軸抽出部１２０１は、カテゴリ １からＮの全てのカテゴリの全ての学習サンプルの特徴ベクトル５１１から、固有ベクトルを共通軸として規定個求め、共通軸集合１２１０を作成する。
【０１０５】
カテゴリ範囲抽出部１２０２は、カテゴリ１からＮ毎に、当該カテゴリ内の全ての学習サンプルの特徴ベクトル５１１に対応する特徴空間内の特徴点を、共通軸集合１２１０中の各共通軸に投影して各共通軸上の値を求め、一定のマージンを加える。これにより、カテゴリ範囲抽出部１２０２は、カテゴリ毎に、各共通軸上のカテゴリ範囲を作成する。
【０１０６】
軸追加カテゴリ判定部１２０３は、カテゴリ１からＮを１つずつ指定しながら、各共通軸の指定されたカテゴリの範囲から得られる特徴空間内のカテゴリの範囲に、指定されたカテゴリの学習サンプルの特徴点が１つもない領域があるか否かを判定する。軸追加カテゴリ判定部１２０３は、学習サンプルの特徴点が１つもない領域があるカテゴリを、軸を追加すべきカテゴリとして判定する。
【０１０７】
軸追加部１２０４は、軸追加カテゴリ判定部１２０３で判定されたカテゴリの学習サンプルの特徴ベクトル５１１のみから固有値と固有ベクトルを算出する。軸追加部１２０４は、固有値の大きい順に、固有ベクトルを新たな追加軸として追加軸集合１２１１（初期値は共通軸集合１２１０）に１つずつ追加する。軸追加部１２０４は、追加軸集合１２１１によって定義される特徴空間内の上記判定されたカテゴリの範囲にそのカテゴリの学習サンプルの特徴点が１つもない領域がなくなるまで、上記固有ベクトルを１つずつ追加する処理を繰り返す。
【０１０８】
軸出力判定部１２０５は、上記軸追加カテゴリ判定部１２０３及び軸追加部１２０４による処理を、繰り返す。軸出力判定部１２０５は、全てのカテゴリについての処理が終了した時点で、追加軸集合１２１１内の各軸を出力軸とする出力軸集合１２１２を出力する。
【０１０９】
図１３、図１４、及び図１５は、第２の実施形態の説明図である。上述した第２の実施形態において、共通軸抽出部１２０１及びカテゴリ範囲抽出部１２０２は、図２から図４で説明した従来の大分類手法と同様にして、共通軸集合１２１０中の各共通軸上の各カテゴリ範囲を抽出している。軸追加カテゴリ判定部１２０３は、各共通軸上のカテゴリ範囲から求まる特徴空間上のカテゴリ範囲において、そのカテゴリの全学習サンプルの特徴ベクトル５１１から求まる特徴点が１つも存在しない領域があるか否かを判定する。例えば、図１３の例において、共通軸１及び共通軸２のカテゴリ範囲から求まる特徴空間上のカテゴリＡの範囲は、１３０１Ａ及び１３０２Ａで示される領域となる。このうち、領域１３０１Ａには、学習サンプルのカテゴリＡの特徴ベクトル５１１から求まる特徴点「Ａ」が存在する。しかし、図４の場合と同様に、領域１３０２ＡにはカテゴリＡの特徴点「Ａ」は１つも存在しない。軸追加カテゴリ判定部１２０３は、カテゴリＡについて、カテゴリＡの特徴点が１つも存在しない領域１３０２Ａがあることを判定する。この判定結果に基づいて、軸追加部１２０４が、領域１３０２Ａが無くなるまで、学習サンプルのカテゴリＡのみの特徴ベクトル５１１から固有ベクトルとして求まる追加軸１及び追加軸２を固有値の大きい順に追加する。この結果、例えばカテゴリＡについて、共通軸１のカテゴリＡの範囲と共通軸２のカテゴリＡの範囲とから１３０１Ａ及び１３０２Ａとして示される領域が定まる。また、追加軸１のカテゴリＡの範囲と追加軸２のカテゴリＡの範囲とから１３０３Ａとして示される領域が定まる。この結果、共通軸１及び２と追加軸１及び２とで定義される特徴空間上のカテゴリＡの範囲は、領域１３０１Ａと１３０３Ａが重なる領域１３００Ａとして決まる。このカテゴリＡの範囲１３００Ａには、カテゴリＡの特徴点が１つも存在しない領域は無い。
【０１１０】
図１４に例示されるように、カテゴリＢとカテゴリＣについても同様に、追加軸１及び２により、各カテゴリの特徴点が１つも存在しない領域が除去された、細かい破線で示される領域と粗い破線で示される領域がそれぞれ、カテゴリＢ及びＣの各範囲として定まる。なお、カテゴリＢとカテゴリＣについて、追加軸１及び２だけでは各カテゴリの特徴点が１つも存在しない領域を除去しきれないときには、更に追加軸が追加されてよい。このようなカテゴリ範囲から作成された辞書を用いることで、未知パターンｘの特徴空間内の特徴点「Ｘ」を共通軸１、共通軸２、追加軸１、及び追加軸４に投影した結果、各投影結果のＡＮＤ積が正しくカテゴリ「Ｂ」のみと重なるように大分類を行うことができる。
【０１１１】
図１５に示されるように、例えばカテゴリＡ、Ｂ、Ｃのそれぞれに対しては、Ａの軸１、２、Ｂの軸１、２、Ｃの軸１、２というように、それぞれのカテゴリの分布に沿った最適な軸がある。ここで、カテゴリＡとカテゴリＣは、近い分布を示しているため、カテゴリＡとＣから求まる軸１、２が採用されるようにすることもできる。
【０１１２】
図１６は、図１２に示される第２の実施形態における共通軸抽出部１２０１、カテゴリ範囲抽出部１２０２、軸追加カテゴリ判定部１２０３、軸追加部１２０４、及び軸出力判定部１２０５の処理例を示すフローチャートである。
【０１１３】
まず、共通軸抽出部１２０１は、特徴抽出部５０１が抽出しているカテゴリ１からＮの全カテゴリの全学習サンプルの特徴ベクトル５１１から、固有ベクトルを共通軸として規定個求め、共通軸集合１２１０を作成する（ステップＳ１６０１）。
【０１１４】
次にカテゴリ範囲抽出部１２０２は、カテゴリ１からＮ毎に、当該カテゴリ内の全ての学習サンプルの特徴ベクトル５１１に対応する特徴空間内の特徴点を、共通軸集合１２１０中の各共通軸に投影して各共通軸上の値を求め、一定のマージンを加える。これにより、カテゴリ範囲抽出部１２０２は、カテゴリ毎に、各共通軸上のカテゴリ範囲を作成する。カテゴリ範囲抽出部１２０２は、共通軸集合１２１０を追加軸集合１２１１の初期値とする（以上、ステップＳ１６０２）。
【０１１５】
次に、軸出力判定部１２０５が、カテゴリ１からＮのうち未処理のカテゴリを１つ指定する（以降このカテゴリを「指定カテゴリ」と記載）（ステップＳ１６０４）。
【０１１６】
次に、軸追加カテゴリ判定部１２０３が、追加軸集合１２１１中の各軸の指定カテゴリの範囲から得られる特徴空間内のカテゴリの範囲に、指定カテゴリの学習サンプルの特徴点が１つもない領域があるか否かを判定する（ステップＳ１６０５）。ステップＳ１６０５の判定がＮＯならば、軸出力判定部１２０５によるステップＳ１６１０の処理に移行する。
【０１１７】
ステップＳ１６０５の判定がＹＥＳの場合、軸追加部１２０４が、指定カテゴリの学習サンプルの特徴ベクトル５１１のみから固有値と固有ベクトルを算出し、各固有ベクトルを対応する各固有値の大きい順に並び替える（ステップＳ１６０６）。
【０１１８】
軸追加部１２０４は、並び替えた順に、１つの固有ベクトルを選択し、その固有ベクトルで定義される追加軸を、追加軸集合１２１１に追加する（ステップＳ１６０７）。ここで追加される追加軸は、共通軸及び既に追加されている追加軸と、互いに直交するとは限らない。従って、最終的に、出力軸集合１２１２に含まれる軸は非直交軸を含んでもよい。
【０１１９】
軸追加部１２０４は、追加軸集合１２１１中の各軸の指定カテゴリの範囲から得られる特徴空間内のカテゴリの範囲に、指定カテゴリの学習サンプルの特徴点が１つもない領域があるか否かを判定する（ステップＳ１６０８）。
【０１２０】
ステップＳ１６０８の判定がＹＥＳの場合、軸追加部１２０４は、追加軸集合１２１１中の軸数が所定の閾値よりも大きくなったか否かを判定する（ステップＳ１６０９）。
【０１２１】
ステップＳ１６０９の判定がＮＯの場合、軸追加部１２０４は、ステップＳ１６０７の処理に戻り、更に並び替えられた順に次の固有ベクトルを選択して、その固有ベクトルで定義される追加軸を追加軸集合１２１１に追加する。そして、軸追加部１２０４は、あらたな追加軸集合１２１１から定まる特徴空間について、ステップＳ１６０８の判定を繰り返す。
【０１２２】
ステップＳ１６０７からＳ１６０９の一連の処理が繰り返される結果、特徴空間上で指定カテゴリの学習サンプルの特徴点が１つもない領域がなくなってステップＳ１６０８の反映がＮＯとなった場合、軸出力判定部１２０５によるステップＳ１６１０の処理に進む。また、追加軸集合１２１１の軸数が所定の閾値を超えてステップＳ１６０９の判定がＹＥＳとなった場合も、軸出力判定部１２０５によるステップＳ１６１０の処理に進む。
【０１２３】
ステップＳ１６１０において、軸出力判定部１２０５は、カテゴリ１からＮの全てのカテゴリの処理が終了したか否かを判定する（ステップＳ１６１０）。
【０１２４】
軸出力判定部１２０５は、ステップＳ１６１０の判定がＮＯならば、ステップＳ１６０４の処理に戻り、未処理の新たなカテゴリを１つ指定し、その指定カテゴリについて、ステップＳ１６０５からＳ１６０９の一連の処理を実行する。
【０１２５】
軸出力判定部１２０５は、ステップＳ１６１０の判定がＹＥＳになると、追加軸集合１２１１中に得られている各軸を辞書で用いられる出力軸として含む出力軸集合１２１２を出力する。その後、軸出力判定部１２０５は、図１６のフローチャートで例示される処理を終了する。
【０１２６】
図１６のフローチャートの処理で作成された出力軸集合１２１２中の各軸を用いることで、特徴空間上で学習サンプルがない無駄なカテゴリ領域を除くことができ、大分類時に、精度は変えずに処理時間を短縮でき、絞り込み能力の向上が実現される。
【０１２７】
図１７は、図５の第１の実施形態又は図１２の第２の実施形態のパターン認識装置を実現可能なコンピュータ１７０１のハードウェア構成の一例を示す図である。図１７に示されるコンピュータ１７０１は、プロセッサ１７０５、メモリ１７０６、ハードディスク装置（半導体ディスク装置でもよい）１７０７、及び入出力インタフェース１７０８を含む。更に、コンピュータ１７０１は、ＤＶＤディスクなどの可搬型記録媒体１７１１が挿入される光学ドライブ装置１７０９を有する。これらの構成要素は、バス１７１０により相互に接続されている。入出力インタフェース１７０８には、外部に、スキャナ１７０２やカメラ１７０３が接続されて、文字画像５１０（図５又は図１２参照）を読み込むことができる。図１７に示される構成は上記パターン認識装置を実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【０１２８】
メモリ１７０６は、例えば、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）、フラッシュメモリ等の半導体メモリであり、処理に用いられるプログラム及びデータを格納する。
【０１２９】
プロセッサ１７０５は、例えば、メモリ１７０６を利用して、図７、図９から図１１又は図１６のフローチャートの処理に対応するプログラムを実行することにより、図５又は図１２に示される各ブロックとして動作する。
【０１３０】
ハードディスク装置１７０７は例えば、図５又は図１２の文字画像５１０や特徴ベクトル５１１、図５の第１軸集合５１２、クラスタ集合５１３、第２軸集合５１４、第３軸集合５１５、出力軸集合５１６、図１２の共通軸集合１２１０、追加軸集合１２１１、又は出力軸集合１２１２などを記憶する。
【０１３１】
また、図５又は図１２のパターン認識装置は、ハードディスク装置１７０７に図７、図９から図１１又は図１６のフローチャートの処理に対応するプログラム及びデータを格納しておき、それらをメモリ１７０６にロードして使用することができる。
【０１３２】
光学ドライブ装置１７０９は、可搬型記録媒体１７１１を駆動し、その記録内容にアクセスする。オペレータ又はユーザは、この可搬型記録媒体１７１１に上述のプログラム及びデータを格納しておき、メモリ１７０６にロードして使用することができる。
【０１３３】
このように、上述のプログラム及びデータを格納するコンピュータ読取り可能な記録媒体は、メモリ１７０６、ハードディスク装置１７０７、又は可搬型記録媒体１７１１のような、物理的な（非一時的な）記録媒体である。
【０１３４】
なお、上述のプログラム又はデータを外部の装置から特には図示しないネットワークインタフェースを介して受信し、それらをメモリ１７０６にロードして使用するようにしてもよい。
【０１３５】
なお、図５又は図１２のパターン認識装置の全ての構成要素を含む必要はなく、用途又は条件に応じて一部の構成要素を省略することも可能である。
【０１３６】
以上、開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができる。
【０１３７】
その他、本発明は上述した実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、上述した実施形態で実行される機能は可能な限り適宜組み合わせて実施しても良い。上述した実施形態には種々の段階が含まれており、開示される複数の構成要件による適宜の組み合せにより種々の発明が抽出され得る。例えば、実施形態に示される全構成要件からいくつかの構成要件が削除されても、効果が得られるのであれば、この構成要件が削除された構成が発明として抽出され得る。
【符号の説明】
【０１３８】
５０１  特徴抽出部
５０２  固有ベクトル抽出部
５０３  階層的クラスタリング部
５０４  クラスタ選択部
５０５  直交軸決定部
５０６  軸出力判定部
５１０  文字画像
５１１  特徴ベクトル
５１２  第１軸集合
５１３  クラスタ集合
５１４  第２軸集合
５１５  第３軸集合
５１６、１２１２  出力軸集合
１２０１  共通軸抽出部
１２０２  カテゴリ範囲抽出部
１２０３  軸追加カテゴリ判定部
１２０４  軸追加部
１２０５  軸出力判定部
１２１０  共通軸集合
１２１１  追加軸集合
【図１】
2019096118.tif 000009
【図２】
2019096118.tif 000010
【図３】
2019096118.tif 000011
【図４】
2019096118.tif 000012
【図５】
2019096118.tif 000013
【図６】
2019096118.tif 000014
【図７】
2019096118.tif 000015
【図８】
2019096118.tif 000016
【図９】
2019096118.tif 000017
【図１０】
2019096118.tif 000018
【図１１】
2019096118.tif 000019
【図１２】
2019096118.tif 000020
【図１３】
2019096118.tif 000021
【図１４】
2019096118.tif 000022
【図１５】
2019096118.tif 000023
【図１６】
2019096118.tif 000024
【図１７】
2019096118.tif 000025