JPH11203415A - 類似パターンカテゴリ識別辞書作成装置および方法 - Google Patents

Abstract

(57)【要約】 【課題】 少ない特徴量次元数で高い精度と少ない計算
コストとを両立することを可能にする識別辞書を作成す
ることを目的とする。 【解決手段】 識別辞書作成に必要なパターンの学習サ
ンプルがあらかじめ用意されているとし、そのパターン
情報を類似パターンカテゴリ作成手段に入力する。類似
パターンカテゴリ作成手段１では、類似するパターンを
求めてこれらをまとめる。カテゴリ分割手段２は作成さ
れた類似パターンカテゴリを誤認識が少なくなるような
カテゴリに細分割する。そして、再統合カテゴリ作成手
段３が分割されたカテゴリを改めて類似したカテゴリに
統合する。これにより、分割カテゴリと再統合カテゴリ
との階層的な辞書が作成され、これを類似パターンカテ
ゴリ識別処理で再統合カテゴリへの認識、分割カテゴリ
への認識の順に使うことにより、高い認識精度と認識の
ための計算量の削減を得ることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は類似パターンカテゴ
リ識別辞書作成装置および方法に関し、特に画像特徴
上、形状が類似しているパターンまたは文字をあらかじ
めまとめて同一のカテゴリとして分類しておき、未知の
パターンまたは文字画像から抽出した特徴量をこれらの
類似パターンカテゴリまたは類似文字カテゴリのいずれ
に属するものであるかを識別するための、類似パターン
カテゴリ識別辞書作成装置および方法に関する。

【０００２】

【従来の技術】ハードコピー文書をイメージスキャナで
画像に変換して電子的に蓄積し、後から検索することを
可能とする文書ファイリング装置が実用化されている。
しかしながら、その多くは入力した画像１枚ごとにキー
ワードなどの検索のための属性を人手で付与しなければ
ならず、非常に労力を要していた。本来、文書の検索で
はテキスト内容によるフルテキスト検索が望ましい。し
かし、これはＤＴＰ（DeskTop Publishing）などによっ
て作成された電子文書に対しては可能であるが、文書画
像に対しては直接に行うことができない。このため、特
開昭６２−４４８７８号公報では、文書中のテキスト部
分に対して文字認識を行い、コード化されたテキスト内
容でフルテキスト検索を可能にしている。しかしなが
ら、文字認識、特に多くの文字種を持つ日本語などにお
いては一般的に、数百次元の特徴量ベクトルを求め、３
０００文字種以上との特徴量の照合を行なうため、特徴
ベクトルの照合処理に非常に多大な計算機パワーが必要
であった。また、その文字認識率も高くないため、検索
すべきキーワードが誤認されてしまう可能性があるとい
う問題点もあった。

【０００３】特開昭６２−４４８７８号公報に記載の電
子ファイリングシステムでは、文字認識処理中に得られ
た各文字の候補を保持しておき、誤認による検索の洩れ
を減少させている。しかしながら、基本的には文字認識
処理を行うために文書登録時に多大な計算機パワーを要
し、最終的に得たいものが検索時に指定した単語を含む
文書画像であるとするならば、文字認識された結果はほ
とんどが無駄なものとなってしまう。

【０００４】文献（田中他、「日本語文書画像に対する
文字列検索機能の実現」、情報処理学会情報メディア研
究会資料１９−１、１９９５年１月）では、各文字画像
から得られる特徴量を取り出し、文字認識するのではな
く、特徴量をそのまま３６ビットのコードに変換する。
次に、検索キーワード画像のとの特徴量のマッチングに
よって文字列検索を実現している。しかし、検索キーワ
ードを画像として入力するか、あるいは文字フォントイ
メージによって画像を生成する必要があり、フォントの
変動には弱いという欠点があった。

【０００５】また、別の文献（Reynar, J. et al, ”Do
cument Reconstruction: A Thousand Words from One P
icture”, in Proc. of 4th Annual Symposium on Docu
mentAnalysis and Information Retrieval, Las Vegas,
April 1995）には、ヨーロッパ系言語（英語）のテキ
スト画像中の文字をその大きさ、位置によって少数のカ
テゴリに分類し、その並びによって単語として識別しよ
うとする試みが開示されている。しかしながら、日本語
や中国語などの多くの文字種を含む言語に対して、手掛
かりとするような特徴を直感的に設定することは困難で
ある。また、ヨーロッパ系の言語と異なり、単語間のス
ペースが存在しないので単語単位で画像中から直接得る
ことができない。このため、直接的には開示されている
手法を用いて日本語などのテキストを単語で識別するこ
とは困難であった。

【０００６】既に出願人は上記の問題点を解決するため
に、特願平８−２７４７３２号明細書において、次のよ
うな手法を開示している。その手法は、以下のようなも
のである。まず、あらかじめ形状の類似している字種
（たとえば、「道」と「通」、数字の「０」とローマン
アルファベットの「Ｏ」）を１つのカテゴリとしてまと
めておく。実際の画像の解析時には、各文字画像をこれ
らの類似文字カテゴリで識別し、その類似文字カテゴリ
列から、日本語のテキストから単語を抽出する技術であ
る形態素解析によって単語として確定できるもののみを
取り出し、曖昧性の残る文字についてのみ、詳細に識別
することを行う。効果としては、文字認識における大分
類に用いられている程度の少ない特徴量次元数で、かつ
少ない類似文字カテゴリとの照合で済むため、大幅に計
算コストが削減できること、および形態素解析を利用し
た場合、単語として許容できるもののうち、曖昧性のあ
るものだけについて詳細識別を実施するので、詳細識別
における特徴量照合の計算コストも削減することができ
ることにある。この発明では、特徴空間内での字種の代
表ベクトルによるクラスタリング、すなわち字種の代表
ベクトル（平均ベクトル）間の距離が小さいもの同士を
統合していくことで、そのクラスタ中心を代表ベクトル
として類似文字カテゴリを形成し、未知文字サンプルは
それらの代表ベクトルとの最短距離識別で識別を行うこ
ととなっていた。しかしながら、この開示している手法
における類似文字カテゴリへの識別方法は必ずしも精度
が高いものにはならなかった。実際の文字の特徴量ベク
トルの分布は、類似文字カテゴリを形成するに従って特
徴量空間内で広がることになり、代表ベクトルから距離
の離れた、分布の端に位置するようなサンプルの場合に
は、他の類似文字カテゴリに誤識別されることが増える
ためであると考えられる。その状況を図１６を参照して
説明する。

【０００７】図１６は類似文字カテゴリ識別での問題点
を説明する図である。図１６では、説明を簡単にするた
め、特徴量空間を二次元に設定して模式的に示してい
る。一つの類似文字のカテゴリのサンプルは特徴量空間
内である分布をしており、ここでは例として三つの分布
Ａ，Ｂ，Ｃを示し、各分布Ａ，Ｂ，Ｃをたとえば楕円で
近似している。各分布Ａ，Ｂ，Ｃの代表ベクトルはその
平均値、すなわち、ここでは楕円の中心のところにある
とする。最短距離識別では、これらの代表ベクトルを結
ぶ垂直二等分線が識別境界になり、この識別境界を越え
て分布するサンプルが誤認識の要因となる。たとえば、
ある類似文字カテゴリの分布Ａでは、これを表す楕円の
長軸の両端が別の類似文字カテゴリの分布との識別境界
を越えているので、このような位置にあるサンプルの場
合には、他の類似文字カテゴリに誤識別されることにな
る。

【０００８】文献（伊藤、遠藤他、「階層的印刷漢字シ
ステムにおける字種を複数クラスタに登録する辞書構成
法」、電子通信学会論文誌D-II, Vol.J78-D-II, No.6,
pp.896-905, １９９５年６月）では、上述と同様に文字
認識の計算コストを削減するために、あらかじめ特徴量
空間で近い、すなわち形状が類似している字種をクラス
タリングによって、カテゴリを作成しておき、これを階
層的に構成し、順に類似文字候補を絞っていく手法を提
案している。ここでも、上述と同様の文字サンプルの分
布の広がりによる誤認の問題を指摘しており、これを解
決するために階層の途中段階では、学習文字サンプルを
用いて、誤識別が発生する可能性を調べ、可能性がある
場合は、その字種を誤識別するカテゴリへ重複して登録
することを行っている。しかしながら、この手法では最
終段階の照合で正解字種に高い精度で識別できることが
前提となっている。本願の類似パターンカテゴリへの識
別では、前述したように類似文字カテゴリの代表ベクト
ルと総当たりで照合を実施しても、精度はさほど良くな
いため、その前提は用いることができない。このとき、
最終段階で他の次元数の多い特徴量を用いて類似文字カ
テゴリを識別することも可能であるが、増加した次元数
分の照合と特徴量抽出のための計算コストが新たに必要
となる。ユークリッド距離を用いずに、マハラノビス距
離など統計的な距離計算を行うことも考えられるが、こ
れも計算コストの増大を招く。精度を向上させる別の方
法として、誤認しやすい字種を複数のカテゴリに登録す
ることを最終段階で許容することが考えられる。しか
し、この場合、後段での単語抽出での問題が生じる。た
とえば、字種「ａ」が、類似文字カテゴリ「Ａ」、
「Ｂ」に重複して登録され、字種「ｂ」がカテゴリ
「Ｃ」、「Ｄ」に登録されている場合、類似文字カテゴ
リ列ＡＣ、ＡＤ、ＢＣ、ＢＤはすべてａｂという単語と
なる可能性があることになり、形態素解析を行う場合
は、単語辞書のエントリが大幅に増えることになる。ま
た、二つの文字の並びをすべてインデックスとして登録
するｂｉ−ｇｒａｍを用いる場合は、検索時に１つの検
索単語を、複数の類似文字カテゴリ列それぞれに検索し
なければならなくなり、検索時の計算コストの増加を引
き起こす。したがって、ある字種が属する類似文字カテ
ゴリは単一であることが望ましい。

【０００９】その他、いくつか類似した文字を含むカテ
ゴリへ識別する手法が開示されている。たとえば、特開
昭６３−２６３５９０号公報では、階層的に類似した文
字サンプルをグループ化しておき、段階的に識別してい
く方法を示している。この中では類似文字のグループ間
での誤認の対処のために複数の候補を選択して、その下
位グループすべてとの識別を行っている。しかし、この
手法では、字種を単位とするのではなく、文字サンプル
を単位として類似文字グループを形成しているので、最
終的に同一字種が異なる分類に属する可能性がある。特
開平４−３３７８８８号公報、特開平５−１７４１９３
号公報では、２分木、３分木を用いて階層的に文字種を
絞っていくことを実施しているが、いずれも同一字種が
異なる分類に属する可能性があり、その救済は最終的に
次元数の多い特徴量での詳細識別を前提としている。こ
のため、前述の理由と同様に後段での計算コスト増加を
招く。

【００１０】したがって、字種が重複していないよう
な、類似文字カテゴリに未知文字を識別する際に、識別
精度を確保しつつ、かつ計算コストが少ない手法が必要
となっていた。

【００１１】

【発明が解決しようとする課題】従来のいずれにおいて
も、類似文字カテゴリへの識別方法に識別精度や計算コ
ストの点で問題があった。

【００１２】本発明は以上のような点に鑑みてなされた
ものであり、あらかじめ定めている字種の重複を許さな
いような類似文字カテゴリへ一意に識別するために、少
ない特徴量次元数で高い精度と少ない計算コストとを両
立することを可能にする識別辞書を作成するための類似
パターンカテゴリ識別辞書作成装置および方法を提供す
ることを目的とする。

【００１３】

【課題を解決するための手段】本発明では上記問題を解
決するために、画像情報に含まれるパターンを類似パタ
ーンカテゴリに識別するときの照合に使用する類似パタ
ーンカテゴリ識別辞書を作成する類似パターンカテゴリ
識別辞書作成装置において、画像に含まれるパターンの
特徴量を抽出したパターン情報からパターン間の類似性
を求め、類似したパターンをまとめて類似パターンカテ
ゴリを作成する類似パターンカテゴリ作成手段と、作成
された類似パターンカテゴリに属するパターンの学習サ
ンプルの誤認の状況を調べ、その状況に基づいて前記類
似パターンカテゴリを分割して分割カテゴリからなる詳
細分類の識別辞書を作成するカテゴリ分割手段と、前記
分割カテゴリの代表ベクトルを求め、分割カテゴリを改
めて類似したものに再統合した再統合カテゴリからなる
大分類の識別辞書を作成し、前記詳細分類の識別辞書と
ともに階層構造を持った類似パターンカテゴリ識別辞書
を構築する再統合カテゴリ作成手段と、を備えているこ
とを特徴とする類似パターンカテゴリ識別辞書作成装置
が提供される。

【００１４】このような類似パターンカテゴリ識別辞書
作成装置によれば、あらかじめ画像からこれに含まれる
パターンの特徴量を抽出しておいたパターン情報を入力
し、まず、類似パターンカテゴリ作成手段が類似するパ
ターンを求めてこれらをまとめることで類似パターンカ
テゴリを作成する。この作成された類似パターンカテゴ
リはカテゴリ分割手段により誤認識が少なくなるような
カテゴリに細分割される。このようにして分割されたカ
テゴリは、再統合カテゴリ作成手段によって、改めて類
似したカテゴリに統合される。これにより、分割カテゴ
リと再統合カテゴリとの階層的な辞書が作成され、これ
を類似パターンカテゴリ識別処理に使うときは、再統合
カテゴリの中から画像から抽出した特徴量ベクトルと最
短距離にある再統合カテゴリを得、その再統合カテゴリ
に属する分割カテゴリの中から最短距離にある分割カテ
ゴリを得るようにすることで、高い認識精度が得られる
とともに認識のための計算量が大幅に削減される。

【００１５】また、本発明では、画像情報に含まれるパ
ターンを類似パターンカテゴリに識別するときの照合に
使用する類似パターンカテゴリ識別辞書を作成する類似
パターンカテゴリ識別辞書作成方法において、画像情報
を入力し、前記画像情報に含まれるパターンの特徴量を
抽出して学習サンプルを蓄積し、前記学習サンプルのパ
ターン間の類似性を調べて、類似したパターンをまとめ
た類似パターンカテゴリを作成し、作成された前記類似
パターンカテゴリに属するパターンの学習サンプルに基
づいて、誤識別が少なくなるよう、各類似パターンカテ
ゴリを分割して分割カテゴリを作成し、前記分割カテゴ
リを改めて類似したカテゴリにまとめて、前記分割カテ
ゴリとともに階層的な識別辞書を構成する再統合カテゴ
リを作成する、ことからなる類似パターンカテゴリ識別
辞書作成方法が提供される。

【００１６】このような類似パターンカテゴリ識別辞書
作成方法によれば、まず、辞書作成に必要な学習サンプ
ルを画像情報から抽出しておき、これを類似したパター
ンを持つカテゴリにまとめて類似パターンカテゴリを作
成する。次に、その学習サンプルに基づいて、誤認が少
なくなるよう、各類似パターンカテゴリを分割し、分割
カテゴリからなる詳細分類の辞書を作成する。そして、
この分割カテゴリを改めて少数の類似したカテゴリにま
とめて、再統合カテゴリからなる大分類辞書を作成す
る。これによって、階層的な識別辞書が構築され、識別
処理時には、構築された階層的な識別辞書によって、最
終的に重複したパターンのない類似パターンカテゴリに
一意に識別することが可能になる。

【００１７】

【発明の実施の形態】以下、本発明の実施の形態を図面
を参照して説明する。図１は本発明の原理図である。本
発明による類似パターンカテゴリ識別辞書作成装置は、
画像に含まれるパターンの特徴量を抽出したパターン情
報を受ける類似パターンカテゴリ作成手段１と、この類
似パターンカテゴリ作成手段１の出力を受けるカテゴリ
分割手段２と、このカテゴリ分割手段２の出力を受けて
類似パターンカテゴリ識別辞書を出力する再統合カテゴ
リ作成手段３とから構成されている。

【００１８】類似パターンカテゴリ作成手段１は、入力
されたパターン情報からパターン間の類似性を調べ、類
似したパターンをまとめて類似文字カテゴリを作成する
ものである。カテゴリ分割手段２は、類似パターンカテ
ゴリ作成手段１によって作成されたカテゴリに属するパ
ターンの学習サンプルに基づいて、誤識別が少なくなる
よう、各類似パターンカテゴリを分割するものであっ
て、カテゴリに属するサンプルを主成分分析し、主成分
軸上での端点ベクトルを求め、その端点ベクトルが、他
のカテゴリに誤識別されるものは、そのカテゴリをクラ
スタリングし、誤識別がなくなるまで、分割する。この
とき、他のカテゴリに誤識別される主成分軸上での端点
ベクトルのうち、固有値の大きなものから分割するよう
にしている。再統合カテゴリ作成手段３は、分割された
カテゴリを改めて類似したカテゴリにまとめて、階層的
な識別辞書を構築するものであって、カテゴリ分割手段
２によって分割されたカテゴリの代表ベクトルをクラス
タリングして代表ベクトルを求めておき、得られた代表
ベクトルとの照合で学習サンプルが誤識別された場合
は、その学習サンプルが属する分割カテゴリを誤識別さ
れたカテゴリに登録することで識別辞書を構築してい
く。

【００１９】このようにして作成された類似パターンカ
テゴリ識別辞書は、たとえばイメージスキャナなどから
入力された文書画像から、たとえば文字あるいは単語情
報を抽出するために、画像中の文字の領域を、形状が類
似している字種をまとめた類似文字カテゴリに識別する
処理に使用される。

【００２０】次に、類似パターンカテゴリ識別辞書作成
装置を文字認識用の類似文字カテゴリ識別辞書の作成に
適用した場合を例に説明する。図２は本発明を実施する
ハードウェア構成を示す図である。本発明を実施する装
置は、一般的なパーソナルコンピュータ１０とその周辺
機器とから構成されている。パーソナルコンピュータ１
０は中央演算装置（ＣＰＵ）１１と、主記憶メモリ１２
と、周辺機器コントローラ１３とから構成されており、
その周辺機器コントローラ１３には、外部記憶装置１
４、ディスプレイ１５、キーボード１６、マウスなどの
ポインティングデバイス１７、画像入力装置であるイメ
ージスキャナ１８、およびネットワーク１９が接続され
ている。

【００２１】本発明装置の処理はすべてソフトウェアで
構成され、外部記憶装置１４に格納されていて、必要に
応じて主記憶メモリ１２にロードされ、随時ＣＰＵによ
って実行される。

【００２２】図３は類似文字カテゴリ識別辞書を作成す
る処理の流れを示すフローチャートである。類似文字カ
テゴリ識別辞書の作成にあたって、まず、イメージスキ
ャナ１８の原稿台の上に置かれた原稿を二値画像として
読み取り、二値画像を文字ごとに切り出し、大きさの正
規化などの前処理を施した後、対応する字種とともに外
部記憶装置１４に格納するという画像入力処理を行う
（ステップＳ１）。次に、外部記憶装置１４に格納され
た学習用の文字画像それぞれについて、特徴量を多次元
のベクトルで表現し、それを外部記憶装置１４に保存す
るという特徴量抽出処理が行われる（ステップＳ２）。
次に、それぞれの字種の学習サンプルの平均ベクトルを
計算してその字種の代表ベクトルとしておき、得られた
代表ベクトルをクラスタリング処理を施して類似文字カ
テゴリを作成する（ステップＳ３）。次に、作成された
類似文字カテゴリごとの学習サンプルの分布をもとに、
他のカテゴリへの誤認が少なくなるようカテゴリを分割
し、分割された類似文字カテゴリの代表ベクトルを、そ
のカテゴリを代表する文字とともに番号を付けて外部記
憶装置１４に格納する処理を行う（ステップＳ４）。そ
して、分割された類似文字カテゴリの代表ベクトルを改
めてクラスタリングし、少数のカテゴリに統合し、その
代表ベクトルと、それぞれに属する分割された類似文字
カテゴリの番号を登録することで再統合カテゴリを作成
する処理を行う（ステップＳ５）。以下、辞書作成処理
を処理の流れに沿ってさらに詳細に説明する。

【００２３】図４は画像入力処理の流れを示すフローチ
ャートである。まず、イメージスキャナ１８から学習用
の原稿を読み込む（ステップＳ１１）。原稿は文字の書
体、大きさを変化させておくことが幅広いサンプルを入
手するためには望ましい。単純に固定的なしきい値によ
って二値化してもよいし、グレースケールの多値画像と
して取り込み、しきい値処理によって二値化してもよ
い。後者の場合はいくつかの二値化しきい値によって、
つぶれ、かすれのある画像を収集することができるの
で、サンプル数を増やすのには効果的である。本実施の
形態では、しきい値をいくつか変えて異なるサンプル画
像を作成している（ステップＳ１２）。次に、得られた
二値画像から文字ごとに領域を切り出す（ステップＳ１
３）。切り出された文字画像は、そこから文字を構成し
ないと思われる小さな孤立点ノイズの除去が施され（ス
テップＳ１４）、文字の外接矩形をもとに大きさの正規
化が行われる（ステップＳ１５）。ここでは、１文字を
６４×６４画素の画像の大きさに正規化するものとす
る。ノイズ除去、大きさの正規化などは、いくつかの公
知の技術があるので、そのうちの適当なものを利用すれ
ばよい。これらの前処理が施された画像はその対応する
字種を与えて、外部記憶装置１４に格納される（ステッ
プＳ１６）。なお、ステップＳ１４〜Ｓ１６は切り出さ
れた文字画像ごとに繰り返され、ステップＳ１３〜Ｓ１
６は異なるしきい値ごとに繰り返し処理される。

【００２４】次の特徴量抽出の処理は、本実施の形態で
は、次元数の少ないペリフェラル特徴を用いている。こ
のペリフェラル特徴を図５を参照して説明する。図５は
ペリフェラル特徴の説明図である。ペリフェラル特徴
は、外接矩形の各辺から最初に黒画素が現れる所（１次
ペリフェラル）、および一旦白画素になり、再び黒画素
になる所（２次ペリフェラル）までの画素数を特徴量と
するものである。この１次ペリフェラルおよび２次ペリ
フェラルを各辺６４画素それぞれについて調べ、８画素
ずつ平均し、それを特徴量ベクトルの各要素とする。し
たがって、各辺８次元で、２次ペリフェラルまでを取る
とすると、合計６４次元の特徴量ベクトルが得られる。
この特徴量ベクトルを外部記憶装置１４にその字種に対
応させて格納する。この処理によって、準備したすべて
の書体、大きさの学習用の文字画像に対して、特徴量ベ
クトルが計算される。

【００２５】この特徴量抽出の処理が終了すれば、次
に、類似文字カテゴリ生成の処理が起動される。類似文
字カテゴリ生成処理は、まず、外部記憶装置１４から、
字種ごとに学習サンプルすべてを取り出し、それらの平
均ベクトルを計算し、これを字種の代表ベクトルとす
る。これをすべての字種について求めたならば、それら
をクラスタリング処理する。クラスタリングは文献（Du
da, Hart著”Pattern Classification and Scene Analy
sis ”, Wiley-Interscience社刊）に記載されている方
法を用いる。この方法はまず、初めに階層的クラスタリ
ングを施し、これを最初のクラスタとしてクラスタごと
の中心と各学習サンプルの特徴量ベクトルとの自乗誤差
の総和が最小になるように最適化を行なうものである。

【００２６】階層的クラスタリングは、実際には以下の
ようなステップから構成される。 （１）所望のクラスタ数をｍ、文字種の総数をｎ、初期
クラスタをＣ＝｛ｃ_1,ｃ_2,ｃ_3,．．．_,c_n｝とし、ｃ_i
は類似している文字種の代表特徴ベクトルである。初期
値としては、各文字種の代表特徴ベクトルを１つずつ入
れられる。

【００２７】（２）もし、現在のクラスタの数がｍに等
しければ、その時点のＣをクラスタリングの結果として
処理を終わる。そうでない場合は次に進む。 （３）特徴空間におけるクラスタの距離ｄが最も小さい
二つのクラスタの組を見つけ出し、これを一つのクラス
タに統合し、（２）に戻る。

【００２８】ここで、所望のクラスタ数ｍは任意に与え
る。また、この処理の中でクラスタ間の距離ｄの計算方
法には種々のものが考えられるが、ここでは重心法と呼
ばれる２つのクラスタ中心間の距離を二つのクラスタの
距離ｄとする。

【００２９】この階層的クラスタリングの結果は最適な
クラスタリングとはいえないため、これを出発点とし
て、クラスタの最適化を行う。最適化は各クラスタ内の
特徴ベクトルの平均値と各特徴ベクトルとの距離の二乗
和をとり、すべてのクラスタについての総和を評価関数
とする。この評価関数の値が小さいほどクラスタ内の特
徴ベクトルが密集しており、より良いクラスタリングで
あるといえる。これを最小とするようなクラスタリング
を見つけることは一般的には困難であるが、疑似的に最
適化を施すことが可能である。これは以下のステップで
行われる。

【００３０】（１）任意の特徴ベクトルｘを取り出す。 （２）ｘが現在属しているクラスタをｃ_i として、そこ
に登録されている特徴ベクトルがｘのみである場合は
（１）へ戻る。そうでない場合は、すべてのクラスタｃ
_j に対して以下の計算を行う。

【００３１】すなわち、ｊ≠ｉの時は、

【００３２】

【数１】

【００３３】の計算を行い、ｊ＝ｉの時は、

【００３４】

【数２】

【００３５】の計算を行う。ただし、ｎ_j はｃ_j に登録
されているベクトルの個数、Ｍ_j はｃ _j に属する特徴ベ
クトルの平均である。上記の式はｘをｃ_j に移動させた
時の判定関数の変化量を示している。

【００３６】（３）ａが最小となるｊがｉ以外である場
合はｘをクラスタｃ_j へ移動し、（４）へ戻る。 （４）次の特徴ベクトルをｘとして（２）から繰り返
す。もし、すべての特徴ベクトルについてクラスタの移
動ができなくなった場合は、その時点でのクラスタを結
果として処理を終了する。

【００３７】このようにして類似文字のクラスタリング
が行われる。この操作のうち（１）の任意の文字を取り
出す方法をさまざまに変えて同様の処理を施し、評価関
数（各クラスタ内の特徴ベクトルの平均値と各特徴ベク
トルとの距離の二乗和の総和）を最小とするものを結果
として採用する。

【００３８】それぞれのクラスタは類似文字カテゴリテ
ーブルとして記憶され、文書の登録の際に用いられる。
ここで、記憶されるテーブルの例を図６に示す。図６は
類似文字カテゴリ生成処理により作成されるテーブルの
例を示す図であって、（Ａ）は類似文字カテゴリテーブ
ルの例を示し、（Ｂ）は文字コード・カテゴリ対応テー
ブルの例を示している。類似文字カテゴリテーブルは、
その一部を（Ａ）に示したように、各カテゴリごとに、
属する文字の文字コード（類似文字）、カテゴリ特徴の
代表ベクトル（代表ベクトル）、およびカテゴリを代表
する文字コード（代表文字）から構成され、記憶装置１
４に蓄えられる。カテゴリ代表ベクトルは属する文字の
特徴ベクトルの平均ベクトルである。カテゴリを代表す
る文字コードはそのカテゴリに属する文字の文字コード
のうち、任意の１つが当てられる。なお、検索処理にお
いて、検索キーワードを類似文字カテゴリ列に変換する
ために、類似文字カテゴリテーブルの逆引きテーブルと
して（Ｂ）に示すような、文字コードと対応するカテゴ
リの代表文字コードとを組にした文字コード・カテゴリ
対応テーブルが同時に作成される。

【００３９】類似文字カテゴリが作成されたならば、次
に、カテゴリ分割処理が起動される。この処理は、類似
文字カテゴリに含まれる字種の学習サンプルから、その
カテゴリに含まれるものの分布を仮定し、その分布の分
散が大きい方向に分布の端点、すなわち統計的に現れ得
る代表ベクトルから最も距離の離れた点を仮定し、それ
が該当カテゴリの代表ベクトルよりも他のカテゴリの代
表ベクトルに近い場合は、そのカテゴリを分割するもの
である。

【００４０】カテゴリの分割は、基本的には文献（大
町、孫他、「カテゴリー間分布を考慮した文字認識用マ
ルチテンプレート辞書の構成法」、電子情報通信学会論
文誌D-II, Vol.J79-D-II, No.9, pp.1525-1533）に開示
されている手法を用いる。これは、文字認識の精度の向
上を目的としたもので、各字種の学習サンプルをいくつ
かのクラスタに分割し、同一字種に複数の代表ベクトル
を与えることによって、計算コストの増加はあるもの
の、誤認を少なくするための手法である。実際の処理の
フローを図７に示す。

【００４１】図７はカテゴリ分割処理の流れを示すフロ
ーチャートである。まず、この処理に対する前処理とし
て、一つの類似文字カテゴリに注目し、これに属する字
種の学習サンプルに対して主成分分析を実施し、上位ｌ
位の主成分に対応する固有値、固有ベクトルを保存する
（ステップＳ２１）。固有値、固有ベクトルは特徴ベク
トルの次元数、または学習サンプルの数−１の小さい方
だけ得られ、固有ベクトルは固有値の大きな順に分散が
大きな方向を示す。ここでは、次元数より多くの学習サ
ンプルが得られていると仮定している。ｌは固有値の大
きな順にいくつ調べるかを示す定数で、辞書作成時に与
えられる。通常、誤認は分散の大きい軸上で発生すると
考えられるので、ｌ＝５くらいで十分である。

【００４２】前処理が終了したならば、各類似文字カテ
ゴリごとに、特徴量空間内でｌ個の主成分軸方向それぞ
れに中心から最も離れて現れ得る二つのサンプル端点を
仮定する（ステップＳ２２）。端点ベクトルｐは次式で
得られる。

【００４３】

【数３】

【００４４】ただし、ｍはカテゴリの代表ベクトル、ａ
は定数、λ_i 、Φ_i はｉ番目の固有値、固有ベクトルで
ある。ａは定数で正の実数である。すなわち、このｐ
は、主成分軸上での代表ベクトルから最も離れたサンプ
ルの特徴空間内での位置を意味する。この式の意味を、
図８に模式的に２次元の特徴量空間で示す。

【００４５】図８は端点ベクトルの式の特徴量空間での
意味を説明するための図である。図８において、小さな
黒丸は類似文字カテゴリ内のサンプルを表し、その分布
は主成分分析という統計上の処理により楕円で近似され
ている。この楕円の中心が分布の平均である代表ベクト
ルｍ、長軸上の第１主成分方向に示した矢印が固有ベク
トルΦ₁ 、短軸上の第２主成分方向に示した矢印が固有
ベクトルΦ₂ であり、×で示した長軸の両端点が式
（３）で表される端点ベクトルｐである。主成分分析で
得られた主成分軸は、特徴量空間で互いに直交してお
り、かつ共分散がないことが知られている。したがっ
て、各主成分軸では、統計的に独立に扱うことができ
る。定数ａはその主成分軸の標準偏差の何倍までを分布
の範囲とみなすかを示す。正規分布を仮定した場合、ａ
＝３．５とすると、９９．９６％の分布がこの中に含ま
れることになる。

【００４６】この端点ベクトルｐがそれぞれの主成分軸
上で求まったならば、そのそれぞれについて最短距離に
あるカテゴリの代表ベクトルを取り出す（ステップＳ２
３）。もし、最短距離にある代表ベクトルが、現在注目
しているカテゴリ、あるいはすでに分割されている同一
カテゴリの代表ベクトルであれば、何もしない（ステッ
プＳ２４、Ｓ２５）。それら以外であれば、誤認が生じ
るカテゴリとして、分割候補としてその主成分次数、対
応する固有値、固有ベクトルとともに保存する（ステッ
プＳ２６）。以上のステップＳ２１〜Ｓ２６までの検査
をすべての類似文字カテゴリについて実施した中で、最
も大きな固有値を持つ分割候補を取り出し、分割を行う
（ステップＳ２８）。分割は、その類似文字カテゴリに
属するすべての字種の学習サンプルをクラスタリングす
ることによって行われる。ここでのクラスタリングは、
ユークリッド距離を用いたｋ−平均法を用いる。ｋ−平
均法を用いる理由は、誤認が発生している主成分軸上に
沿ってサンプルを分割するように制御するためである。
したがって、与える初期クラスタ中心として、分割対象
となる類似文字カテゴリの二つの端点ベクトルｐに最も
近い学習サンプルを与える。これは文献（大町、孫他、
「カテゴリー間分布を考慮した文字認識用マルチテンプ
レート辞書の構成法」、電子情報通信学会論文誌D-II,
Vol.J79-D-II, No.9, pp.1525-1533）とは異なり、より
確実に端点を含む領域を分割することができる。なお、
すでにその類似文字カテゴリがいくつかに分割されてい
るものの一つである場合は、対象クラスタだけでなく、
元の類似文字カテゴリすべてを対象としてクラスタリン
グを実施する。そのときの初期クラスタ中心には、分割
対象カテゴリは端点ベクトルに最も距離の小さい学習サ
ンプル、それ以外はその代表ベクトルを与える。図９に
その例を模式的に示す。

【００４７】図９はｋ−平均法によるカテゴリ分割を説
明する図であって、（Ａ）は類似文字カテゴリの最初の
分割例を示し、（Ｂ）は分割された類似文字カテゴリの
さらなる分割例を示している。最初に類似文字カテゴリ
をｋ−平均法により分割する場合、まず、長軸の端点に
最も近いサンプルを初期クラスタ中心とする。このサン
プルは、（Ａ）に示した分割前の左側の図では白丸で示
してある。このサンプルを初期クラスタ中心としてｋ−
平均法のクラスタリングの手法を使うことにより最終的
に分割されたクラスタが、右側の図である。これによ
り、長軸の端点が最も距離が長く誤認が生じる可能性が
高かったクラスタが、それぞれ短い長軸を有するクラス
タに分割されたことになる。そして、各クラスタについ
て主成分分析をすることにより、新たに代表ベクトル、
固有ベクトル、端点ベクトルが求められる。（Ｂ）は、
既に二つに分割された類似文字カテゴリの一方が、分割
対象となる場合で、（Ａ）と同様に、左側の白丸が初期
クラスタ中心を示し、結果は右側のようになる。

【００４８】このようにしてクラスタリングによる分割
が終了したならば、分割されたそれぞれのクラスタの代
表ベクトルを求めた後、主成分分析を実施し、上位ｌ個
の主成分の固有値、固有ベクトルを求め、記憶してお
く。これをすべての分割されたカテゴリについて、ｌ個
すべての主成分について繰り返し、分割候補が得られな
くなるまで続ける（ステップＳ２７）。終了したなら
ば、分割された類似文字カテゴリ（以下、分割カテゴリ
と呼ぶ）の代表ベクトル、類似文字代表文字コードを組
にして識別辞書を作成し、外部記憶装置に登録する。

【００４９】図１０はカテゴリ分割による識別辞書のデ
ータ構造を示す図である。この識別辞書はカテゴリ番
号、類似文字代表文字コード、および代表ベクトルから
構成されている。ここで、カテゴリ番号は、後で述べる
再統合カテゴリ作成処理で作成される再統合カテゴリに
属する分割カテゴリを識別するために用いられる。

【００５０】なお、分割途中にサンプル数が少ないカテ
ゴリが生成されることがある。このような場合、主成分
分析を実施した場合、誤差が大きくなる可能性がある。
このため、一定個数以下のサンプルしか含まない分割カ
テゴリについては、分割対象としないようにする。この
ようにすることで、無意味な分割を防ぐことができる。
本実施の形態では、サンプル数のしきい値は、主成分分
析の次数が特徴量次元６４次元以下にならないように、
６５と設定している。

【００５１】このように得られた分割カテゴリによる識
別辞書を用いて、未知文字の識別には最短距離識別を行
うことによって、誤認を減少させることができる。しか
しながら、当然ながらカテゴリの分割によって照合すべ
き代表ベクトルの数が増加し、元の字種数以上に大きく
なる場合がある。本来、字種数より少ない数の類似文字
カテゴリに識別することで計算コストの削減を実現して
いる意味がなくなってしまう。これを解決するために、
分割された類似文字カテゴリの再クラスタリングを実施
し、少ないカテゴリへ改めて統合する。これが再統合カ
テゴリ作成処理である。実際の識別の際には、まず、こ
の再クラスタリングで得られた少ないカテゴリと照合を
行い、最良のものを取り出し、それに属する分割クラス
タの代表ベクトルと照合を行うことで、計算量の削減を
行う。再統合カテゴリ作成処理は、最初に字種の代表ベ
クトルをクラスタリング処理して類似文字カテゴリを構
築した重心法と最適化手法をそのまま用いる。ここで、
元々同一の類似文字カテゴリを分割したかどうかはまっ
たく関係なく、分割結果として得られているものを区別
なく扱う。この処理によって得られたクラスタを再統合
カテゴリと呼ぶ。

【００５２】この処理で得られた再統合カテゴリとの最
短距離識別だけでは、最初に類似文字カテゴリの代表ベ
クトルで最短距離識別した場合と同様、誤認が発生す
る。これを避けるために、分割カテゴリごとに学習サン
プルを用い、誤認が発生したものについては、誤認が発
生している再統合カテゴリに重複して登録するようにす
る。この処理フローを図１１に示す。

【００５３】図１１は再統合カテゴリ作成処理の流れを
示すフローチャートである。この再統合カテゴリ作成処
理では、まず、カテゴリ分割処理で得られた分割カテゴ
リごとに、属する学習サンプルすべてを取り出し（ステ
ップＳ３１）、その一つを取り出し、最短距離にある、
再統合カテゴリの代表ベクトルを得る（ステップＳ３
２）。そのカテゴリが、いま注目している分割カテゴリ
の属する再統合カテゴリであれば、何もせずに次のサン
プルを調べる（ステップＳ３３）。異なる再統合カテゴ
リであれば、その再統合カテゴリに、現在注目している
分割カテゴリを登録する（ステップＳ３４）。すなわ
ち、注目している分割カテゴリは複数の再統合カテゴリ
に属することになる。この操作をすべての分割カテゴリ
のすべてのサンプルについて行い、終了したならば、再
統合カテゴリをその代表ベクトルと、それに属している
分割カテゴリの番号とを組にして大分類辞書として外部
記憶装置に格納する（ステップＳ３５）。そのデータ構
造を図１２に示す。

【００５４】図１２は再統合カテゴリ作成処理による大
分類辞書のデータ構造を示す図である。再統合により作
成された大分類辞書のデータはその代表ベクトルと、そ
れに属している分割カテゴリの番号とから構成されてお
り、この例からは、分割カテゴリ番号に重複して登録さ
れている分割カテゴリが存在することが分かる。なお、
ここでは、最短距離にある分割カテゴリにのみ登録する
ことを行ったが、サンプルから見た最短距離にある値を
加えた距離にあるすべての再統合カテゴリに、注目して
いる分割カテゴリを登録することを実施すれば、未知文
字の変動に対処することができる。

【００５５】このようにして、再統合カテゴリ作成処理
で得られた結果の再統合カテゴリの代表ベクトルを大分
類辞書とし、分割クラスタの代表ベクトルを詳細分類辞
書として、未知文字の照合時には、二段階の照合を実施
する。類似文字カテゴリへの識別を実施する疑似文字認
識処理のフローチャートを図１３に示す。

【００５６】図１３は類似文字カテゴリ識別処理の流れ
を示すフローチャートである。まず、イメージスキャナ
から文書画像（二値画像）を入力する（ステップＳ４
１）。入力画像から文字ブロックを抽出し、各文字を切
り出す（ステップＳ４２）。文字ブロックの切り出し処
理は、文献（秋山、増田、「周辺分布、線密度、外接矩
形特徴を併用した文書画像の領域分割」電子情報通信学
会論文誌D-II, Vol.J69,No.8 ）などに開示されている
周辺分布による領域分割手法を用いることができる。切
り出された文字画像について、ペリフェラル特徴量ベク
トルを計算する（ステップＳ４３）。この特徴量ベクト
ルに対して、まず、大分類として再クラスタリングで得
られた再統合カテゴリの代表ベクトルと最初に照合し、
最短距離にあるものを取り出し、そのクラスタに属する
分割カテゴリの代表ベクトルを得る（ステップＳ４
４）。次に、その分割カテゴリの代表ベクトルとの照合
を行い、最短距離にあるのものを取り出し（ステップＳ
４５）、それに対応する類似文字カテゴリの代表文字を
出力する（ステップＳ４６）。以上のステップＳ４３〜
Ｓ４６の処理を切り出された文字ごとに順次繰り返し行
われる。

【００５７】なお、本実施の形態では２段階の識別辞書
を作成したが、これをさらに多くの階層にすることも可
能である。すなわち、分割カテゴリの再統合を行い、そ
れをさらに少ないカテゴリ数で再統合を行うということ
を行えばよい。段数が増えると誤認が生じる可能性が増
えるので、どれくらいの段数が妥当かについてはカテゴ
リ数、段数をいくつか変化させて実験的に確かめればよ
い。

【００５８】この変形例として、大分類時に最短距離に
あるものだけではなく、距離の小さなものから、数個カ
テゴリを取り出しておき、それらに属する分割カテゴリ
とのマッチングを行うことで、誤識別を少なくすること
ができる。この場合、照合回数は増加するが、精度は当
然向上する。いくつまで候補をとるかについては、候補
数を変換させて実験的に確かめればよい。

【００５９】この結果、得られた類似文字カテゴリ代表
コード列は、特願平８−２７４７３２号明細書で示され
ているように、後で検索が容易となるようにｂｉ−ｇｒ
ａｍを取り出して登録する処理、あるいは類似文字カテ
ゴリ列の形態素解析を実施し、単語として許容できるも
のを抽出して登録する処理に渡される。この時、必要で
あれば、単語を確定するために文字候補の詳細識別を実
施する。これら類似文字カテゴリ列が得られた後の処
理、さらに文字の切り出し位置が複数ある場合の処理に
ついても、特願平８−２７４７３２号明細書に開示して
いる処理をそのまま利用することができる。

【００６０】本発明は、特願平８−２７４７３２号明細
書で開示した類似文字カテゴリ列から単語を抽出する処
理において、精度と速度を両立させる類似文字カテゴリ
識別手法を実現するものであるが、従来手法である文字
認識における大分類処理と置き換えて利用することも可
能である。

【００６１】いま、総字種Ｎ個について総当たりで代表
ベクトルとの照合による大分類を行い、上位ｎ個を詳細
分類する従来手法の文字認識の場合と、本発明によって
大分類処理を置き換えた場合との比較を行う。従来手法
での大分類の特徴量次元数をｘ、詳細分類の特徴量次元
数をｙとする。識別は、ユークリッド距離で最短距離識
別とする。計算量は、乗算の回数すなわち、距離計算の
回数と次元数の積にほぼ比例する。したがって、これを
計算量の指標として考えた場合、一つの未知文字につい
ての計算量はＮｘ＋ｎｙである。これに対して、本手法
での、類似文字カテゴリ数をＭとすると、各類似文字カ
テゴリには平均Ｎ／Ｍ個の字種が含まれることになる。
再クラスタリングするときのクラスタ数をＬ、再クラス
タリングされた各クラスタに平均Ｋ個の分割カテゴリが
含まれているとし、類似文字カテゴリへの識別の特徴量
次元数、詳細識別の次元数を従来手法と同様にｘ、ｙと
すると、計算量は、（Ｌ＋Ｋ）ｘ＋（Ｎ／Ｍ）ｙとな
る。なお、ここでは各字種の出現確率はすべて等しいと
仮定している。

【００６２】実際に実験を実施して得られた数値によ
り、その効果を示す。ここで、総字種をＪＩＳ第１水準
の約１／４個の字種を対象とした。用いた特徴量はペリ
フェラル特徴で、次元数は６４である。これを各字種に
ついて、いくつかのフォント、大きさを変化させ、学習
サンプルを４００程度作成した。与えたパラメータは、
Ｎ＝８３５、Ｍ＝５００、Ｌ＝１００である。結果とし
て、分割クラスタ総数は３３３９、Ｋ＝１０３．５とな
った。実際に学習サンプルを識別させたところ、類似文
字カテゴリへの識別率９９．３％と十分な精度を達成し
た。従来手法での大分類特徴量次元数ｘを６４、詳細分
類次元数ｙを２５６、大分類での候補数ｎ＝２０と仮定
し、これを計算量の指標に当てはめると、従来手法で
は、８３５×６４＋２０×２５６＝５８５６０となる。
これに対して本手法では、（１００＋１０３．５）×６
４＋８３５／５００×２５６＝１３４５１．５２とな
る。したがって、計算量は約１／４以下となり、大幅に
削減されていることがわかる。仮に、精度を向上させる
ために類似文字カテゴリへの識別結果の上位１０カテゴ
リを取り出し、それに含まれている字種すべてを詳細識
別するとした場合、（１００＋１０３．５）×６４＋８
３５／５００×２５６×１０＝１７２９９．２となり、
これでもまだ１／３以下の計算量となる。類似文字カテ
ゴリに識別された場合に、特願平８−２７４７３２号明
細書で開示している類似文字カテゴリ列を形態素解析す
る手法を用いて、さらに詳細分類の回数を減らすことが
できる。また、識別された類似文字カテゴリに単一の字
種しか登録されていない場合（実験で得られた類似文字
カテゴリ５００個のうち、一つの字種しか登録されてい
ないカテゴリは３１７個であった）、あるいは形態素解
析によって字種が一つに特定できる場合は、その文字に
ついての詳細分類の必要がなくなるので、詳細分類のた
めの特徴量抽出処理と、その照合処理は不要になる。し
たがって、計算量の差はさらに大きくなる。

【００６３】次に、カテゴリ分割処理の別の実施の形態
について説明する。類似文字カテゴリ識別辞書を作成す
る第２の実施の形態においても、基本的な処理は図３に
示した流れに沿って実施され、その詳細はカテゴリ分割
処理を除き同じであるので、省略し、カテゴリ分割処理
だけを説明する。

【００６４】図１４は第２の実施の形態におけるカテゴ
リ分割処理の流れを示すフローチャートである。まず、
一つの類似文字カテゴリに注目し、その類似文字カテゴ
リに属する字種すべての学習サンプルを取り出す（ステ
ップＳ５１）。次に、その学習サンプルの中の一つのサ
ンプルに注目し、最短距離にある類似文字カテゴリを得
る（ステップＳ５２）。その類似文字カテゴリは、現在
注目している類似文字カテゴリ、あるいはすでに分割さ
れている同一の類似文字カテゴリであれば、何もしない
（ステップＳ５３、Ｓ５４）。それ以外であれば、その
中で誤識別が発生しているので、誤識別されたカテゴリ
ごとに学習サンプルをまとめておく。

【００６５】図１５は第２の実施の形態におけるカテゴ
リ分割の説明図である。図１５に示すように、たとえ
ば、類似文字カテゴリＡ，Ｂ，Ｃ，Ｄがあって、類似文
字カテゴリＡにおけるサンプルのいくつかがカテゴリ
Ｂ，Ｃ，Ｄとの識別境界面を越えて分布しているとする
とき、類似文字カテゴリＡに属するサンプルの一部はカ
テゴリＢ，Ｃ，Ｄの３つに誤識別されていることにな
る。このような場合、それぞれ誤識別している学習サン
プルをまとめ、図示のように、類似文字カテゴリＡを四
つに分割する。

【００６６】ただし、この時点では、分割を行わず、そ
の誤識別されたサンプルと最短距離カテゴリとの対応を
記憶しておくだけとする（ステップＳ５５）。以上のス
テップＳ５２〜Ｓ５５までの検査をすべてのサンプルに
対して実施し、さらにステップＳ５１〜Ｓ５５までの検
査をすべての類似文字カテゴリについて実施した後、実
際に分割を行う。すなわち、誤識別されたカテゴリごと
にサンプルの平均ベクトルを計算し（ステップＳ５
７）、注目しているカテゴリの代表ベクトルと誤識別さ
れたカテゴリのサンプルの平均ベクトルとを初期クラス
タとしてクラスタを分割する（ステップＳ５８）。分割
が終了すれば、分割カテゴリに促するサンプルの平均ベ
クトルを求め、代表ベクトルとする。これを誤識別され
たサンプルを含むすべての類似文字カテゴリについて行
い、同様の処理を誤識別がなくなるまで繰り返す（ステ
ップＳ５６）。

【００６７】分割は、ｋ−平均法を用いる。初期クラス
タ中心は、誤識別されたサンプルを誤識別対象類似文字
カテゴリごとに集めて、その平均ベクトルと、注目して
いる類似文字カテゴリの代表ベクトルとする。これによ
って、図１５の右側のように、識別平面が移動し、誤識
別が少なくなる。

【００６８】

【発明の効果】以上説明したように本発明では、類似パ
ターンカテゴリ識別辞書を、一旦作成した類似パターン
カテゴリを分割し、これらの分割カテゴリの代表ベクト
ルを詳細分類辞書とし、さらに分割カテゴリを再統合し
て、その再統合カテゴリの代表ベクトルを大分類辞書と
する二段階の構成にするようにした。これにより、未知
パターンの照合時に、大分類および詳細分類の二段階の
照合が可能な類似パターンカテゴリ識別辞書になる。こ
のような辞書を使用することにより、再統合カテゴリへ
の識別率は、最初に作成した類似パターンカテゴリへの
識別率の約９２％の場合に比較して９９．３％と向上し
ており、かつ、計算量は総当たりの照合の場合に比較し
て約１／４以下となって、識別速度を向上させることが
できる。

【図面の簡単な説明】

【図１】本発明の原理図である。

【図２】本発明を実施するハードウェア構成を示す図で
ある。

【図３】類似文字カテゴリ識別辞書を作成する処理の流
れを示すフローチャートである。

【図４】画像入力処理の流れを示すフローチャートであ
る。

【図５】ペリフェラル特徴の説明図である。

【図６】類似文字カテゴリ生成処理により作成されるテ
ーブルの例を示す図であって、（Ａ）は類似文字カテゴ
リテーブルの例を示し、（Ｂ）は文字コード・カテゴリ
対応テーブルの例を示している。

【図７】カテゴリ分割処理の流れを示すフローチャート
である。

【図８】端点ベクトルの式の特徴量空間での意味を説明
するための図である。

【図９】ｋ−平均法によるカテゴリ分割を説明する図で
あって、（Ａ）は類似文字カテゴリの最初の分割例を示
し、（Ｂ）は分割された類似文字カテゴリのさらなる分
割例を示している。

【図１０】カテゴリ分割による識別辞書のデータ構造を
示す図である。

【図１１】再統合カテゴリ作成処理の流れを示すフロー
チャートである。

【図１２】再統合カテゴリ作成処理による大分類辞書の
データ構造を示す図である。

【図１３】類似文字カテゴリ識別処理の流れを示すフロ
ーチャートである。

【図１４】第２の実施の形態におけるカテゴリ分割処理
の流れを示すフローチャートである。

【図１５】第２の実施の形態におけるカテゴリ分割の説
明図である。

【図１６】類似文字カテゴリ識別での問題点を説明する
図である。

【符号の説明】

１ 類似パターンカテゴリ作成手段 ２ カテゴリ分割手段 ３ 再統合カテゴリ作成手段 １０ パーソナルコンピュータ １１ 中央演算装置（ＣＰＵ） １２ 主記憶メモリ １３ 周辺機器コントローラ １４ 外部記憶装置 １５ ディスプレイ １６ キーボード １７ ポインティングデバイス １８ イメージスキャナ １９ ネットワーク

Claims (7)

【特許請求の範囲】
1. 【請求項１】 画像情報に含まれるパターンを類似パタ
   ーンカテゴリに識別するときの照合に使用する類似パタ
   ーンカテゴリ識別辞書を作成する類似パターンカテゴリ
   識別辞書作成装置において、 画像に含まれるパターンの特徴量を抽出したパターン情
   報からパターン間の類似性を求め、類似したパターンを
   まとめて類似パターンカテゴリを作成する類似パターン
   カテゴリ作成手段と、 作成された類似パターンカテゴリに属するパターンの学
   習サンプルの誤認の状況を調べ、その状況に基づいて前
   記類似パターンカテゴリを分割して分割カテゴリからな
   る詳細分類の識別辞書を作成するカテゴリ分割手段と、 前記分割カテゴリの代表ベクトルを求め、分割カテゴリ
   を改めて類似したものに再統合した再統合カテゴリから
   なる大分類の識別辞書を作成し、前記詳細分類の識別辞
   書とともに階層構造を持った類似パターンカテゴリ識別
   辞書を構築する再統合カテゴリ作成手段と、 を備えていることを特徴とする類似パターンカテゴリ識
   別辞書作成装置。
2. 【請求項２】 画像情報に含まれるパターンを類似パタ
   ーンカテゴリに識別するときの照合に使用する類似パタ
   ーンカテゴリ識別辞書を作成する類似パターンカテゴリ
   識別辞書作成方法において、 画像情報を入力し、前記画像情報に含まれるパターンの
   特徴量を抽出して学習サンプルを蓄積し、 前記学習サンプルのパターン間の類似性を調べて、類似
   したパターンをまとめた類似パターンカテゴリを作成
   し、 作成された前記類似パターンカテゴリに属するパターン
   の学習サンプルに基づいて、誤識別が少なくなるよう、
   各類似パターンカテゴリを分割して分割カテゴリを作成
   し、 前記分割カテゴリを改めて類似したカテゴリにまとめ
   て、前記分割カテゴリとともに階層的な識別辞書を構成
   する再統合カテゴリを作成する、 ことからなる類似パターンカテゴリ識別辞書作成方法。
3. 【請求項３】 前記分割カテゴリを作成するステップ
   は、前記類似パターンカテゴリに属するサンプルを主成
   分分析し、主成分軸上での端点ベクトルを求め、その端
   点ベクトルが他の類似パターンカテゴリに誤識別される
   ときは、当該類似パターンカテゴリをクラスタリングす
   ることによって分割し、前記クラスタリングを誤識別が
   なくなるまで繰り返すことを特徴とする請求項２記載の
   類似パターンカテゴリ識別辞書作成方法。
4. 【請求項４】 前記分割カテゴリを作成するステップ
   は、前記類似パターンカテゴリに属するサンプルを主成
   分分析し、特徴量空間での主成分軸上でのサンプル分布
   の端点を求め、前記端点における端点ベクトルが他の類
   似パターンカテゴリに誤識別されるもののうち、固有値
   の大きなものから、当該類似パターンカテゴリに属する
   サンプルをクラスタリングによって分割し、誤識別がな
   くなるまで分割を繰り返すことを特徴とする請求項２記
   載の類似パターンカテゴリ識別辞書作成方法。
5. 【請求項５】 前記再統合カテゴリを作成するステップ
   は、前記分割カテゴリの代表ベクトルを求めておき、前
   記学習サンプルが先に求めた代表ベクトルとの照合で誤
   識別された場合は、当該学習サンプルが属する分割カテ
   ゴリを誤識別されたカテゴリに登録することで再統合し
   ていくことを特徴とする請求項２記載の類似パターンカ
   テゴリ識別辞書作成方法。
6. 【請求項６】 前記再統合カテゴリを作成するステップ
   は、前記分割カテゴリの代表ベクトルを求めておき、前
   記学習サンプルが先に求めた代表ベクトルとの照合で誤
   識別された場合は、当該学習サンプルが属する分割カテ
   ゴリを誤識別されたカテゴリに登録することでカテゴリ
   数の多い再統合カテゴリを作成し、さらにその結果を入
   力として順に少ないカテゴリ数の再統合カテゴリを再帰
   的に作成することによって多段の識別辞書を作成するこ
   とを特徴とする請求項２記載の類似パターンカテゴリ識
   別辞書作成方法。
7. 【請求項７】 前記分割カテゴリを作成するステップ
   は、類似パターンカテゴリに属する学習サンプルが、属
   するカテゴリ以外のカテゴリの代表ベクトルに誤識別さ
   れる場合、当該サンプルを誤識別されるカテゴリごとに
   まとめて新たなクラスタとして分割し、誤識別がなくな
   るまで分割を行うことを特徴とする請求項２記載の類似
   パターンカテゴリ識別辞書作成方法。