JP2000512046A

JP2000512046A - 統計に基づくパターン識別のための方法及び装置

Info

Publication number: JP2000512046A
Application number: JP10501110A
Authority: JP
Inventors: ブロイアートーマス; ハニッシュヴィルフリート; フランケユルゲン
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 1996-06-08
Filing date: 1997-05-23
Publication date: 2000-09-12
Also published as: US6205247B1; WO1997048069A1; EP0978088B1; EP0978088A1; TW344063B; DE59705593D1; DE19623033C1

Abstract

(57)【要約】本発明は統計に基づくパターン識別のための方法及び装置に関し、この方法では、識別すべき対象に対して２クラスクラシフィケータ又はマルチクラスクラシフィケータの完全な集合に基づいてクラス集合の各目標クラスへの所属度を数値によって推定し、この数値は多項クラシフィケータの縦続的な適用によって得られる。本発明では、全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの中から、これら全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定ベクトルスペクトラムを介して、全ての識別すべきクラスパターンが十分に存在している学習標本検査において、次のような２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択を行う、すなわちこれら２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定が推定ベクトルスペクトラムを介して計算される分離する上で重要なスカラー値の最小化に最も強く寄与するような２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択を行う。次いで選択された２クラスクラシフィケータ又はマルチクラスクラシフィケータを用いて拡大された学習標本検査を介して推定ベクトルを形成し、この推定ベクトルから多項式による結合によって展開された特徴ベクトルを生成し、この特徴ベクトルに基づいて全目標クラスに対する推定のために評価クラシフィケータを形成する。

Description

【発明の詳細な説明】統計に基づくパターン識別のための方法及び装置記述パターン識別は電子データ処理の時代においてますます重要性を増している。その適用領域は自動化技術から機械的な画像及びテクスト処理にまで広がり、この機械的な画像及びテクスト処理ではパターン識別は自動手紙分配（住所読み取り）のために又は書式又は文書の評価のために使用されている。この場合パターン識別の目的は、電子的に事前処理された画像情報にパターンの真の意味内容と一致する標識を高い確実性で割り当てることである。統計的に基礎付けられたパターン識別方法はデジタル化された画像情報を推定する。この推定からパターンのクラスへのこのパターンの所属度を読みとることができる。目標クラスがＫ個与えられている場合、一般的に次のようなクラスが選ばれる。すなわちこのクラスの推定結果が全Ｋ個の推定の最大値に相応するようなクラスが選ばれる。最大値と推定された目標クラスが真の目標クラス（意味内容）に頻繁に一致すればするほど、識別システムはそれだけ信頼性が高いと見なされる。２クラスクラシフィケータ（Zweiklassen-Klassifikator）の完全な集合から成るこれまで使用されてきたネットクラシフィケータ（Netzklassifikator）は、全ての可能なＫ＊（Ｋ−１）/２個のクラスペアに対してそれぞれ２クラスクラシフィケータを計算することから発生する。上記ネットクラシフィケータはＫ個の目標クラスを決定しなくてはならない。読み取り動作においては、存在するパターンにおいて２クラスクラシフィケータの各々が、基礎となる２つの目標クラスのうちの１つへのこのパターンの所属度推定を送出する。Ｋ＊（Ｋ−１）/２個の推定が発生し、これらＫ＊（Ｋ−１）/２個の推定は互いに独立している。これらＫ＊（Ｋ−１）/２個の推定からＫ個の推定が、つまり各目標クラス毎に１つの推定が形成される。この理論はこの点においてWojciech W.SiedleckiのA formula for multiclass distributed classifie rs,Pattern Recognition Letters 15 (1994)に記載の数学的規則を提示する。これらのクラシフィケータの実用は、この規則の適用可能性が不十分にしか満たされないことを示す。というのも、２クラスクラシフィケータがその適応されたクラス領域には所属しない未知のパターンを推定するやいなや、この２クラスクラシフィケータは統計的な事後確率を与えないからである。実際にはこれはスイッチメカニズムができるだけ早期にこのパターンに所属しないクラシフィケータを非活性化しなくてはならないことを意味する。これまで実際に使用されてきたスイッチ規則はかなりヒューリスティックな特徴を帯びていた。従って、ネットクラシフィケータの処理には統計学的には制御できない恣意の要素が入り込んでいる。測定可能な統計的な特性を免れないパラメータのこの規則に基づいた処理によって、分類結果は本質的に劣化する。さらにネットクラシフィケータの規則に基づいた処理は、変更された標本検査によってこのクラシフィケータシステムを効果的に再トレーニングする可能性を妨げる。決定すべきクラスが３０又はそれより多くある場合、さらにネットクラシフィケータの使用は次のような原理的な問題に直面する：１．記憶すべき成分（ペアクラシフィケータ（Paarklassifikator））の総数がクラス総数（Ｋ＊（Ｋ−１）/２）の２乗に従って増える。２．成分に関する推定の評価及びこの成分に関する推定を信頼できる全体的推定にまとめあげることは、クラス数の増加に伴ってますます不確実になる。３．ネットクラシフィケータをその地方固有の書体に適合させることにより適応動作に多額のコストがかかってしまう。請求項１及び８に記載の本発明の課題は統計学に基づくパターン識別方法及びこの方法を実現するための装置を提供することであり、この方法は、クラス数が多い場合の前述した従来技術の困難を回避しつつ、是認できるコストで普遍的な識別という課題がリアルタイムで可能なように解決することであり、さらにネットクラシフィケータの規則に基づく処理を回避することである。本発明により得られる利点はとりわけヒューリスティックなスイッチ規則を回避することによって識別の確実性を大きく高めることである。２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択及び評価クラシフィケータの生成の後で、適用の全統計がこの評価クラシフィケータに基づくモーメント行列で表現される。評価クラシフィケータに結合した２クラスクラシフィケータ又はマルチクラスクラシフィケータの縮小された系列を記憶しさえすればよいので、非常に経済的なメモリの利用が達成される。画像特徴処理に関連して多項クラシフィケータは全ての演算を加算、乗算及び自然数の配置によって実施するので、目標ハードウェアにおいて浮動小数点シミュレーションのような比較的複雑な計算を完全に削除できる。またメモリコストのかかるテーブル装置の設置も行わない。これらの事情により目標ハードウェアのデザインの際には実行時間の最適化に全力をかければよい。本発明の有利な実施形態は、従属請求項から得られる。請求項２記載の実施形態では、スカラー分離値（分類値）として判定空間における２乗誤差の和が選択される。この場合の利点は、線形クラシフィケータの計算によって現れる線形回帰の経過に明らかに残差の最小化への寄与に応じて成分の間に順位が構成されることである。この順位は自由に使用可能な２クラスクラシフィケータ又はマルチクラスクラシフィケータから選択するために利用される。この選択は結果的にペアクラシフィケータの縮小された集合を形成する。残差を最小化するための方法は詳しくはSchuermann,Statistischer Polynomklassifikator,R.Oldenburg Verlag,1 977に記述されている。請求項３記載の実施形態はスカラー分離値として推定ベクトルの分布空間におけるエントロピーを使用する。エントロピーの評価のためにこの場合全ての状態の集合に亘って全てのペアクラシフィケータ推定の各状態の出現頻度を算出する。次いで最小エントロピーを作り出すような部分系を求める。請求項４記載の実施形態では、比較的大きい目標クラス集合を複数の目標クラス集合に分割する。これら複数の目標クラス集合のに対してそれぞれ２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択を行ないそこから評価クラシフィケータを生成する。評価クラシフィケータの結果から次いで最終的な全体推定を求める。最終的な全体推定は様々な方式で計算できる：１．請求項５記載の実施形態では、評価クラシフィケータの結果ベクトルから直交座標に拡張された積ベクトルが形成される。この積ベクトルから次いで全体推定を算出する最終的な２乗評価クラシフィケータが形成される。２．請求項６記載の実施形態では、同様に直交座標の積ベクトルが形成される。これは部分空間変換Ｕを用いて縮小されたベクトルに変換され、この縮小されたベクトルの中から変換行列Ｕの固有値分布に従って最も重要な成分だけが２乗クラシフィケータの適応に使用される。この２乗クラシフィケータは次いで変換されかつ縮小されたベクトルを目標クラスの評価ベクトルに写像する。３．請求項７記載の実施形態では、クラス集合のグループに関して学習を行ったメタクラスクラシフィケータが、２クラスクラシフィケータ又はマルチクラスクラシフィケータの各選択の活性化の前にこれらグループに関して推定を行う。次いで、所定の閾値を越える推定値を有する、グループの記号に対する２クラスクラシフィケータ又はマルチクラスクラシフィケータが活性化される。次いで全体推定を求めるために、グループ評価と記号目標クラスに対してそれぞれ所属の記号評価クラシフィケータの評価が統一的な規則に則って結合され、この結果、このように得られる全記号推定に亘る和が１に正規化可能な数を生ずる。第１の方法は最も精確な結果を与えるが、最も大きな計算技術コストがかかる。他方で第２及び第３の方法は計算技術コストの低減に寄与する。本発明の変換は５つのフェーズに分かれる。本発明の各フェーズを次に実施例によって図面を参照しつつ詳しく説明する。図１はネットクラシフィケータのペアクラシフィケータの完全な集合を生成する際の経過を示す。図２はペアクラシフィケータの縮小された集合を生成する際の経過を示す。図３は評価クラシフィケータの生成の際の経過を示す。図４は本発明の装置におけるパターン識別の経過を示す。図５はメタクラスクラシフィケータを使用して大きなクラス総数を有するパターン識別の際の経過を示す。本発明を以下に２クラスクラシフィケータ（ペアクラシフィケータ）の集合に基づいて説明する。しかし、本発明は原理的にこの限定に制限されない。ネットクラシフィケータの生成図１によればプロセスステップはバイナリ画像により開始される。学習標本検査の各画像に対してバイナ像の黒色ピクセルは１で表され、他方で白色ピクセルは０で符号化されている。付加的に各パターンには人によって行われる基準識別が実施される。この基準識別はパターンの意味内容を一義的に検出する。正規化は局所的及び大局的なピクセルの割合の測定に基づいてバイナリ画像をグレイスケール画像に変換する。こじ、各成分はスケーリング範囲［０，２５５］の中のグ主軸変換される。この行列ベクトル乗算の結果は画像る。２次元Ｗベクトル（Ｗ₁,Ｗ₂）に対して例えば結合規則は：ＰＳＬ１＝ＬＩＮ１，２ＱＵＡＤ１１,１２,２２であり、これは次のｘベクトルを生成する：後で生成される推定値が和において１に正規化されるように、第１の成分にはいつも１を予め割り当てる。スの各ペア(i,j)に対して生成される。クラスiはこの場合人がクラスiに所属すると見なす記号のみを含む。各モーメント行列にはSchuermann J.,Polynomklass ifikatoren fuer die Zeichenerkennungに記述された方法に従って回帰が行われる。公式（１）に従って次いられる。ネットクラシフィケータとしてはこれによりＫ＊（Ｋ−１）/２個のペアクラシフィケータの集合が成立する。これらペアクラシフィケータの各々（２クラス判定子）は相応のパターンデータに亘って学習しているので、これらペアクラシフィケータの各々（２クラス判定子）は自由に処理できるＫ個の目標クラスから精確に２個の目標クラスを識別する。次の関係式が成り立つ：値ベクトルであり、p(i)はクラスiの出現頻度である。はクラスiに対する値d(i,j)を推定し、この場合次式が成り立つ：クラシフィケータ係数A(i,j)[l]はこの場合常に次式が成り立つように調整される： d(i,j)＋d(j,i)＝l （４）ペアクラシフィケータの総数の縮小このプロセスステップは図２に概略的に図示されている。ネットクラシフィケータの生成後、このネットクラシフィケータの推定ベクトルスペクトラム｛d(i, j)｝は、クラス別に近似的に均一に分布された学習標本検査を介して検出される。この学習標本検査には識別される全てのクラスパターンが十分に入っている。分類の集合である。この集合は全てのペアクラシフィケータを有する学習標本検査の分類によって得られる。個々のｄベクトルは、学習標本検査の記号の展開された、次いでこのスカラー積の結果をペアクラシフィケー。次に特徴集合{d(i,j)}に対する統計的な操作を介して、目標条件として分離する上で大いに重要なスカラーを求める。例として次の２つのスカラー分類値に基づいて説明する：Ｄ（Ｉ）判定空間における２乗誤差の和Ｓ² この場合クラシフィケータA^Linは式（１）により生成される。それ故このクラシフィケータA^Linは線形である。というのも、式（２）によるモーメント行列の計算のためにはｘベクトルとして第１の位置において d(i,j)から構成されている。この変形実施形態は次の様な利点を有する。すなわち、線形クラシフィケータらかに残差の最小化への寄与に応じて順位が成分d(i,j)の中に構成されるという利点である。この順位はＫ＊（Ｋ−１）/２個の使用可能なペアクラシフィケータの中から選択するために利用される。この選択は結果的にペアクラシフィケータの縮小された集合を形成する。残差を漸減するための方法にはことではもはやくわしく説明する必要はない。詳細にSchuermann J.,Polynomklassifikatoren f uer die Zeichenerkennung,Kapital 7に記述されている。選択の際には現在順位によって７５個の最重要な成分に限定している。この限定は適応に使用される計算機のメインメモリ容量に依存しており、従って原理上の限定ではない。従って、特徴集合{d(i,j)に亘る線形回帰の結果はペアクラシフィケータの配列された集合{A(i_α，j_α)}_α=1,..._,75であり、これらペアクラシフィケータでは変化するインデックスαによって２乗残差の縮小への寄与が相対的に落ちて行く。さらに別の適応経過ではこの選択された集合がペア分類にさらに使用される。 d(i,j)分布空間におけるエントロピー２クラス判定子の構造化されていない集合のエントロピーＨを形成するためには次の表現を計算する必要がある：表現p(I|d(i,j))は、語の定義通り、クラシフィケータA(i,j)が所定の推定ｄ( i,j)においてクラスIのパターンを分類したことに対するベイズの事後確率である。ベイズの公式：を使用し、そして次の定義：を使用すれば、エントロピーＨを経験的なエントロピーＨ^*によって任意に精確に近似することもできる。パラメータ：ＵＲ：＝下限推定閾値ＯＲ：＝上限推定閾値ＭＡＸ：＝ヒストグラムの区画の総数は推定ベクトルスペクトラムに基づいて定められる。次いでパラメータN_i,j, _α, _J がパターンの学習標本検査を介して選択される。N_i,j, _α,Jを求めた後で次のパラメータが得られる：計算を実施するとエントロピーに結びついた全ての統計的パラメータが求められる。今や次のような部分系を定めることができる。すなわち、１．この部分系の個々のエントロピーの和において最小の全体エントロピーが生成され、さらに２．この部分系の成分が相互に統計的にできるだけ小さい相関を有するような部分系を定めることができる。上記２つの要求は次の選択規準に従うことによって計算される：１．エントロピー順位：同一のエントロピーのクラシフィケータに至るまで一義的な系列A(i_α,j_α)をによって定める。２．帰納法の開始：れは最小のエントロピーのクラシフィケータである。３．ｋからｋ＋１までの帰納法：自由な角度パラメータΘ_critは勾配法によって所定の総数の選択された成分が成立するように調整される。選択規準をより細かくすることは相関係数COR(i.j; k,l)の最小化によって達成される。フィルタ条件（２５）はこの場合：となる。よって、それぞれ２個のペアクラシフィケータの間の許容される最大相関係数はχ_critによって制限される。さらに相関係数は対称性条件：を満たす。この方法は上述の分類値に対して実施されるが、原理的にはこれに限定されない。本発明の従属請求項は他の分類値に基づく方法の特徴に関連する。評価クラシフィケータの生成このプロセスステップは図３に示されている。図３では（ＲＮＫ）と記されているペアクラシフィケータ定クラス毎に少なくとも９０００パターンを含む拡張された学習標本検査を介して推定ベクトルの計算に使用される。次元７５の個々のベクトルから構成される特徴集合{d(i_α,j_α)}が成立し、各パターンに対して目標識別子（パターンの意味内容）が画像特徴集合から同時に記入されている。各特徴ベクトルを介して多項式にみ付け平均によって生成される。次いで回帰法がクラス毎の評価クラシフィケータを次式によって生成する：ここでP(I)はクラスIの出現頻度である。これによって、ペアクラシフィケータ推定と個々のクラスに対する全体推定との間の関係に関する他の仮定なしにこの関係をd(i,j)空間における近似的な統計的分布から計算するインスツルメントが作られる。ペアクラシフィケータ推定と全体推定との間の最適な関係に対する計算上の近似は、基礎となる学習標本検査が全体的なものになればなるほど良好になる。この方法の成果は、とりわけ適当な学習標本検査の選択の際の恣意の程度が仮説的数学的関連の構築の際に行われる恣意の程度よりも制限されることに現れる。ペアクラシフィケータの縮小された集合及びこの集合に結合された評価クラシフィケータの生成によって適応フェーズは完了する。この適用の全統計は今や評価クラシフィケータの基礎となるモーメント行列に表現されている。このモーメント行列は次の適応過程のためにアーカイブに保管される。適当な評価クラシフィケータと結びついたペアクラシフィケータの縮小された系列のみが統合されて積になる。よって、この方法は極端に圧縮された情報単位（モーメント行列）を生成できる。この情報単位はパターン識別の所与の適用を表し、将来の反復（地方固有の適合）のためのスタート対象として使用可能である。本発明の方法の相応の装置での使用法このプロセスステップは図４に概略的に示されている。この方法は、リアルタイムシステムにおいて配列され縮小されたペアクラシフィケータの系列を適用すること及びそれぞれの適用に適合した評価クラシフィケータを使用することを許す。どの評価クラシフィケータが適用事例にとって最高の成果をもたらすのか不十分にしか分からない場合に使用の申し出が多くなり、読み出しテストは最適な評価クラシフィケータを示す。目標ハードウェアへの最小限の要求は、次のコンポーネントが存在していることを条件とする：１．ＮＯＲＭ：バイナリ化された特徴ベクトルを従来技術に応じた正規化方法によって変換し、一定の長さの入力ベクトル（ｖベクトル）に格納するモジュール。２．ＰＯＬＹ：一定の写像規則に従って、正規化されたｗベクトルを、分類のための入力ベクトルとして使用される多項式展開されたｘベクトルに変換するモジュール。３．ＭＡＴ：外部マイクロプログラムを介して制御された、整数ベクトル間のスカラー積を計算する行列乗算装置。４．ＳＴＯＲＥ：中間値を格納しクラシフィケータ係数をアドレス指定するためのメモリ。５．ＡＬＧＯ：制御命令乃至は実施可能なマシーンコードを格納するための命令レジスタ。メモリは、中間結果の格納及び読み出しのためのユニットＳＴＯＲＥＩ及び不変の値を読み出すためのユニットＳＴＯＲＥ２に分割される。上述の方法に対して図４に記載された操作が必要である。この場合命令レジスタＡＬＧＯによって制御されて順番に次のようなステップが実施される：１．識別プロセスがピクセル画像の読み込みによってスタートする。パターン走査の後でこのパターンがれる。原則的にバイナリの１には黒色ピクセルが対応し、０には白色ピクセルが対応する。ＮＯＲＭは行及び列毎のピクセル密度の測定に基づいてバイナリ画素を組み替えて、結果として１６×１６画像行列に相応レースケール画像の各画素は２５６個のグレースケール段でスケーリングされている。ＮＯＲＭはこのベク出す。この主軸変換行列は、適応フェーズにおいて特される。行列ベクトル乗算が実施される。結果は変換ＳＴＯＲＥ１に格納される。ＴＯＲＥ１から読み出し、リストＰＳＬ１をＳＴＯＲのように結合すべきか、という制御情報を含んでいる。ｘベクトルがＳＴＯＲＥ１に格納される。４．モジュールＭＡＴがＳＴＯＲＥ１からｘベクトルを読み出し、ＲＮＫの行列要素を読み出す。このＲ納されている。ＭＡＴは各Ａベクトル毎にｘベクトルとのスカラー積を形成する。よって、Ａベクトルと同数のスカラー積が成立する。これらスカラー積はＡベクトルの順番でｄベクトルになる。これらをＭＡＴはＳＴＯＲＥ１に格納する。５．モジュールＰＯＬＹがＳＴＯＲＥ１からｄベクトルを読み出し、ＳＴＯＲＥ２からＰＳＬ２を読み出す。ＰＳＬ２をｄベクトルに適用することによって、ＰＯＬＹは今やＸベクトルを構成する。ＸベクトルをＳＴＯＲＥ１に格納する。６．ＸベクトルがモジュールＭＡＴによってＳＴＯＲＥ１から読み出され、他方でＭＡＴは今度は評価クラシフィケータのＡ行列をＳＴＯＲＥ２から読み出す。この行列は評価クラシフィケータがクラスを推定するのと同数のＡベクトルを含む。ＭＡＴは読み出しの後で各Ａベクトルに対してＸベクトルとのスカラー積を実施する。このスカラー積はＡベクトルの順番でＤベクトルに束ねられる。これらをＭＡＴはＳＴＯＲＥ１に書き込む。このループが経過するとＳＴＯＲＥ１に結果としてＤベクトルがいつでも使用可能状態で存在する。このＤベクトルは、判定問題のＫ個のクラスの各々に対して数字間隔[０，１]の推定を含んでいる。最大推定値に対応するクラシフィケータの評価を受け入れるか拒否するかは後続処理モジュールの問題である。分類による後続処理の支援は次のことによって保証されている。すなわち、適応フェーズから評価クラシフィケータの連続推定スペクトラムが周知であり、この連続推定スペクトラムからコストモデルの適用の際に推定の拒否乃至は受け入れに対して統計的に防護された閾値が導出されうる。さらに推定ベクトル統計が読み出し動作の際に周期的に検出されるならば、閾値の動的な事後調整に関する統計的な予想が導出される。普遍的な文字数字併用識別（アルファアニューメリック・リコグニション）への応用１０個の数字、３０個の大文字、３０個の小文字及び２０個の特殊記号から構成される一般的なクラス集合の識別の際には、全体として少なくとも９０個のクラスを判別しなくてはならない。識別問題を完全なネットクラシフィケータによって解決するつもりならば、これら９０個のクラスには４００５個のペアクラシフィケータが相応するだろう。従って、従来の読み取り電子装置のメモリ容量も計算能力にも過負荷となる。９０個の意味内容クラスの代わりに、識別理論的な理由から、同一の記号クラスのそれぞれ典型的な書体形式を表すいわゆるゲシュタルトクラス（Gestaltkla ssen）を導入するすれば、この問題はますます厳しくなる。ゲシュタルトクラスを基礎とすれば、２００クラスまで分割される。この問題は、グループネットクラシフィケータ及びグループ評価クラシフィケータからなるメタクラスクラシフィケータが学習することにより解決される。このクラシフィケータ系は図５に図示されている。メタクラスクラシフィケータはこの場合記号のグループを識別する。グループに対するクラスタリングは距離（ Metrik）を介して実施される。この距離は個々のゲシュタルトクラスのモーメント行列に基づいて計算される。この場合、グループは互いに類似したゲシュタルトクラスが同一のグループに入るように構成される。グループのモーメント行列はグループの中にあるゲシュタルトクラスの全てのモーメント行列に亘る重み付け平均によって得られる。それぞれせいぜい３０個のゲシュタルトクラスを含む例えば８個のグループがある場合、メタクラスクラシフィケータ自体はネットクラシフィケータと本発明により生成される評価クラシフィケータとの結合として実現される。その後で各グループペアに対してペアクラシフィケータが得られる。グループネットクラシフィケータはこの場合２８個８個のペアクラシフィケータに基づいてグループ評価ラシフィケータはクラスとして８個のグループを推定する。次のステップでは、ゲシュタルトクラスの各グ方法に従って学習する。読み取りフェーズでまず最初にグループ評価クラシフィケータは、当該記号がどのグループに所属するのかを判定する。続いて判定された１つ又は複数のグループに対応する縮小された記号ネットクラシフィケータが閾値に依存して活性化される。この縮小された記号ネットクラシフィケータはグループにおいて代表的な各ゲシュタルトクラス毎に推定値を生成する。統計的基礎に基づいて各グループ毎に閾値τ_Iが調整される。この閾値τ_Iは、グループ評価クラシフィケータのどの推定品質（Schaetzguete）D_I以上の相応の縮小された記号ネットクラシフィケータ計算コストでこれら縮小された記号ネットクラシフィケータのうちの少なくとも１つがいつも高い確実性で正しい識別結果を有するように、これら閾値は調整される。複数の記号評価クラシフィケータの結果が存在する場合、活性化された記号評価クラシフィケータとの乗算の前に活性化されなかった記号評価クラシフィケータの推定値に１/クラス総数を予め掛けることによって、正規化された全体結果を得る。この分類手順によって普遍的な文字数字併用識別問題は本発明の方法に完全に基づいて構成できる。さらに別の解決方法を以下に挙げる：１．基本クラシフィケータとしてマルチクラス判定子を取り入れること本発明の方法は、原理的に２クラス判定子の集合を介する評価クラシフィケータの適応に限定されるものではなく、マルチクラス判定子の集合にまで拡張される。よって、ｎ個のクラス判定子から成る集合において、ｎ番目のクラスが、全ての存在するクラスに関して同一の判定子の残りの（ｎ−１）個のクラスに対する補完クラスとなりうる。２．本発明のクラシフィケータによるカスケードシステム自動的な読み取り動作を実施してみると、すでに存在するパターンに対して比較的弱く構築された識別モジュールがあまりにも低い推定品質を示す場合にのみコントロール構造体が高度に構築された識別モジュールを呼び出すことによって、一定の読み取り性能の場合には相当なコスト低減が可能であることがわかる。本発明のクラシフィケータはこの戦略に完璧に組み込まれる。同一の基本クラシフィケータに基づいて構成され縦続的に分類を行う本発明のクラシフィケータのシステムが構成される。この場合、（ｎ＋１）番目の評価クラシフィケータはｎ番目の評価クラシフィケータがあまりよく推定できなかったパターンによってトレーニングされる。実際の読み取り動作ではこのカスケードは一般に最初の評価クラシフィケータの後で打ち切られるが、しかし珍しく難しいパターンの場合には引き続き継続され、これにより計算負荷上昇が小さくても読み取り率は高まる。

【手続補正書】特許法第１８４条の８第１項【提出日】平成１０年５月２９日（１９９８．５．２９）【補正内容】請求の範囲１．統計に基づくパターン識別のための方法であって、該方法は識別すべき対象に対して２クラスクラシフィケータ又はマルチクラスクラシフィケータの完全な集合に基づいてクラス集合の各目標クラスへの所属度を数値によって推定し、該数値は多項クラシフィケータの縦続的な適用によって得られる、統計に基づくパターン識別のための方法において、全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの中から、これら全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定ベクトルスペクトラムを介して、全ての識別すべきクラスパターンが十分に存在している学習標本検査において、次のような２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択を行い、すなわちこれら２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定が推定ベクトルスペクトラムを介して計算される分離する上で重要なスカラー値の最小化に最も強く寄与するような２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択を行い、さらに選択された２クラスクラシフィケータ又はマルチクラスクラシフィケータを用いて拡大された学習標本検査を介して推定ベクトルを形成し、該推定ベクトルから多項式による結合によって展開された特徴ベクトルを生成し、該特徴ベクトルに基づいて全目標クラスに対する推定のために評価クラシフィケータを計算することを特徴とする、統計に基づくパターン識別のための方法。２．スカラー分離値として判定空間における２乗誤差の和を選択することを特徴とする請求項１記載の方法。３．スカラー分離値として分布空間におけるエントロピーを選択し、２クラスクラシフィケータ又はマルチクラスクラシフィケータ推定の各特徴状態の出現頻度は全ての特徴状態の集合に亘って求められることを特徴とする請求項１記載の方法。４．比較的大きな目標クラス集合を複数の目標クラス集合に分割し、該複数の目標クラス集合に対してそれぞれ２クラスクラシフィケータ又はマルチクラスクラシフィケータを選択し、そこから評価クラシフィケータを生成し、該評価クラシフィケータの結果から最終的な全体推定を求めることを特徴とする請求項１〜３記載の方法。５．評価クラシフィケータの結果ベクトルから直交座標に拡張された積ベクトルを形成し、該積ベクトルから全体推定を算出する最終的な２乗評価クラシフィケータを形成することを特徴とする請求項４記載の方法。６．評価クラシフィケータの結果ベクトルから直交座標に拡張された積ベクトルを形成し、該積ベクトルを部分空間変換を用いて変換されたベクトルにし、該変換されたベクトルの中で変換行列の固有値分布に相応して最も重要な成分のみを２乗クラシフィケータの適応のために使用し、該２乗クラシフィケータは、変換され縮小されたベクトルを目標クラスに対する推定ベクトルに写像することを特徴とする請求項４記載のパターン識別方法。７．クラス集合のグループに亘ってトレーニングされる２クラスクラシフィケータ又はマルチクラスクラシフィケータのそれぞれの選択の活性化の前に、前記グループに亘る推定値を生成し、その後で、前記グループの記号に対する次のような２クラスクラシフィケータ又はマルチクラスクラシフィケータを活性化し、すなわち推定値が一定の閾値より上にあるような２クラスクラシフィケータ又はマルチクラスクラシフィケータを活性化し、次いで、全体推定を求めるために、各グループに含まれる記号クラスに対してそれぞれ所属の記号評価クラシフィケータの推定値とグループ推定値とを統一的な規則に従って結合し、このように結合された記号推定値の和が１に正規化可能な数を生ずることを特徴とする請求項４記載の方法。８．統計に基づくパターン識別のための装置であって、該装置は識別すべき対象に対して２クラスクラシフィケータ又はマルチクラスクラシフィケータの完全な集合に基づいてクラス集合の各目標クラスへの所属度を数値によって推定し、該数値は多項クラシフィケータの縦続的な適用によって得られる、統計に基づくパターン識別のための装置において、全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの完全な集合の中から、これら全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定ベクトルスペクトラムに基づいて、全ての識別すべきクラスパターンが十分に存在している学習標本検査を介して、２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定が推定ベクトルスペクトラムを介して計算される分離する上で重要なスカラー値の最小化に最も強く寄与するような２クラスクラシフィケータ又はマルチクラスクラシフィケータの統計的に最適な選択を行うための手段を有し、多項式に展開される特徴ベクトルを生成するための手段を有し、該特徴ベクトルは選択された２クラスクラシフィケータ又はマルチクラスクラシフィケータの系の構造を表し、さらに前記特徴ベクトルは拡大された学習標本検査を介して形成され、評価クラシフィケータの計算のための手段を有し、該評価クラシフィケータは前記選択された２クラスクラシフィケータ又はマルチクラスクラシフィケータの系の多項式による結合によって展開された特徴ベクトルから推定ベクトルを計算し、該推定ベクトルは、各目標クラス毎に、パターンの前記クラスへの分類されたパターンの所属度の近似的な事後確率としての数値を含む、統計に基づくパターン識別のための装置。

───────────────────────────────────────────────────── 【要約の続き】ケータを用いて拡大された学習標本検査を介して推定ベクトルを形成し、この推定ベクトルから多項式による結合によって展開された特徴ベクトルを生成し、この特徴ベクトルに基づいて全目標クラスに対する推定のために評価クラシフィケータを形成する。

Claims

【特許請求の範囲】１．統計に基づくパターン識別のための方法であって、該方法は識別すべき対象に対して２クラスクラシフィケータ又はマルチクラスクラシフィケータの完全な集合に基づいてクラス集合の各目標クラスへの所属度を数値によって推定し、該数値は多項クラシフィケータの縦続的な適用によって得られる、統計に基づくパターン識別のための方法において、全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの中から、これら全ての２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定ベクトルスペクトラムを介して、全ての識別すべきクラスパターンが十分に存在している学習標本検査において、次のような２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択を行い、すなわちこれら２クラスクラシフィケータ又はマルチクラスクラシフィケータの推定値が推定ベクトルスペクトラムを介して計算される分離する上で重要なスカラー値の最小化に最も強く寄与するような２クラスクラシフィケータ又はマルチクラスクラシフィケータの選択を行い、さらに選択された２クラスクラシフィケータ又はマルチクラスクラシフィケータを用いて拡大された学習標本検査を介して推定ベクトルを形成し、該推定ベクトルから多項式による結合によって展開された特徴ベクトルを生成し、該特徴ベクトルに基づいて全目標クラスに対する推定のために評価クラシフィケータを計算することを特徴とする、統計に基づくパターン識別のための方法。２．スカラー分離値として判定空間における２乗誤差の和を選択することを特徴とする請求項１記載の方法。３．スカラー分離値として分布空間におけるエントロピーを選択し、各特徴状態の出現頻度は全ての特徴状態の集合に亘って求められることを特徴とする請求項１記載の方法。４．比較的大きな目標クラス集合を複数の目標クラス集合に分割し、該複数の目標クラス集合に対してそれぞれ２クラスクラシフィケータ又はマルチクラスクラシフィケータを選択し、そこから評価クラシフィケータを生成し、該評価クラシフィケータの結果から最終的な全体推定を求めることを特徴とする請求項１３記載の方法。５．評価クラシフィケータの結果ベクトルから直交座標に拡張された積ベクトルを形成し、該積ベクトルから全体推定を算出する最終的な２乗評価クラシフィケータを形成することを特徴とする請求項４記載の方法。６．評価クラシフィケータの結果ベクトルから直交座標に拡張された積ベクトルを形成し、該積ベクトルを部分空間変換を用いて変換されたベクトルにし、該変換されたベクトルの中で変換行列の固有値分布に相応して最も重要な成分のみを２乗クラシフィケータの適応のために使用し、該２乗クラシフィケータは、変換され縮小されたベクトルを目標クラスに対する推定ベクトルに写像することを特徴とする請求項４記載のパターン識別方法。７．クラス集合のグループに亘ってトレーニングされる２クラスクラシフィケータ又はマルチクラスクラシフィケータのそれぞれの選択の活性化の前に、前記グループに亘る推定値を生成し、その後で、前記グループの記号に対する次のような２クラスクラシフィケータ又はマルチクラスクラシフィケータを活性化し、すなわち推定値が一定の閾値より上にあるような２クラスクラシフィケータ又はマルチクラスクラシフィケータを活性化し、次いで、全体推定を求めるために、各グループに含まれる記号クラスに対してそれぞれ所属の記号評価クラシフィケータの推定値とグループ推定値とを統一的な規則に従って結合し、このように結合された記号推定値の和が１に正規化可能な数を生ずることを特徴とする請求項４記載の方法。８．請求項１記載の方法を適用してパターン識別をするための装置において、可変的な長さのバイナリ化された入力ベクトルをグレースケール段に従ってスケーリングされた一定の長さの出力ベクトルに変換するための手段（ＮＯＲＭ）、正規化された入力ベクトルを多項式によって拡張されたベクトルに変換するための手段（ＰＯＬＹ）、整数ベクトル間のスカラー積を計算するために行列乗算を実施するための手段（ＭＡＴ）、中間値を格納するための記憶のための及びクラシフィケータ係数をアドレス指定するための手段（ＳＴＯＲＥ）、制御命令を格納するための手段及び実施可能なマシーンコード命令レジスタを特徴とする請求項１記載の方法を適用してパターン識別をするための装置。