(57)【特許請求の範囲】
【請求項１】
入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字の参照ベクトルとの距離を比較して文字認識を行う文字認識システムであって、
前記既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書記憶装置およびコンピュータを備え、
前記コンピュータは、
前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出し、
前記クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択し、
前記入力パターンから得られる特徴ベクトルの特徴を、多数の参照ベクトルの特徴の距離平均値の大きさ順を示すリストに従って距離平均値の大きい順に並べ替えた後、まずｎ番目の特徴までについて前記参照ベクトルのうちの１つについてその対応する特徴との距離を計算し、
（１）前記距離を文字候補選択しきい値と比較し、（２）前記しきい値より大きくなければ次のｎ個の特徴を含めた距離を計算する手順を繰り返して距離が前記文字候補選択しきい値を超えると、次の参照ベクトルとの比較に移る
ようプログラムされている文字認識システム。
【請求項２】
請求項１に記載のシステムであって、
前記コンピュータは、全特徴に基づく距離値が前記文字候補選択しきい値を超えないとき、比較対象となった参照ベクトルに対応する文字を文字候補としてメモリに記憶するようプログラムされている
前記システム。
【請求項３】
請求項２に記載のシステムであって、
前記コンピュータは、ｍ番目に小さい距離値の文字候補の距離値を文字候補選択しきい値として動的に設定するようプログラムされており、
ｍは、選択される文字候補の数である
前記システム。
【請求項４】
請求項３に記載のシステムであって、
前記コンピュータは、前記最も文字の出現頻度の高いクラスに属するすべての参照ベクトルに対する前記特徴ベクトルの距離の計算が完了したとき、これらの距離の１つまたは複数が前記クラスに対して定められたしきい値より小さいとき、小さい方から前記ｍ番目までの距離の参照ベクトルに対応するｍ個の文字を文字候補として選択するようプログラムされている
前記システム。
【請求項５】
入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字の参照ベクトルとの距離を比較して文字認識を行う文字認識システムであって、
前記既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書記憶装置およびコンピュータを備え、
前記コンピュータは、
前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出し、
前記クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択し、
複数の前記文字候補が選択されることに応答して、任意の文字について類似関係にある文字を規定する類似文字辞書からそれぞれの文字候補に類似する文字を取り出し、
認識すべき前記特徴ベクトルと前記類似する文字の参照ベクトルとの距離を計算し、
前記複数の文字候補の距離値および前記類似する文字の距離値をソートし、
距離値が最も小さい予め定めた数の文字を認識文字候補として選択する
ようプログラムされている文字認識システム。
【請求項６】
入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字の参照ベクトルとの距離を比較して文字認識を行う文字認識システムであって、
前記既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書記憶装置およびコンピュータを備え、
前記コンピュータは、
前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出し、
前記クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択し、
前記クラスしきい値より小さい距離が存在しないとき、２番目に文字の出現頻度が高いクラスに属する複数の文字の参照ベクトルに対する前記特徴ベクトルの距離を算出し、
前記クラスに対して定められた第２のクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択し、
複数の前記文字候補が選択されることに応答して、任意の文字について類似関係にある文字を規定する類似文字辞書からそれぞれの文字候補に類似する文字を取り出し、
認識すべき前記特徴ベクトルと前記類似する文字の参照ベクトルとの距離を計算し、
前記複数の文字候補の距離値および前記類似する文字の距離値をソートし、
距離値が最も小さい予め定めた数の文字を認識文字候補として出力する
ようプログラムされている文字認識システム。
【請求項７】
入力文字のパターンから得られる特徴ベクトルと、予め格納されている既知の文字のパターンの参照ベクトルとの距離を比較して文字認識を行う文字認識システムであって、
前記既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、この分類情報とともに前記参照ベクトルを格納する辞書記憶装置と、
入力文字の前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出する距離算出手段と、
前記最も文字の出現頻度の高いクラスに属する１つまたは複数の文字について前記距離算出手段により算出される距離が所定のしきい値よりも小さいとき、前記最も文字出現頻度の高いクラスに属する文字の参照ベクトルとの距離計算に基づいて文字候補を選択する選択手段と、
を備え、
前記距離算出手段は、
前記入力パターンから得られる特徴ベクトルの特徴を、多数の参照ベクトルの特徴の距離平均値の大きさ順を示すリストに従って距離平均値の大きい順に並べ替えた後、まずｎ番目の特徴までについて前記参照ベクトルのうちの１つについてその対応する特徴との距離を計算し、
（１）前記距離を文字候補選択しきい値と比較し、（２）前記しきい値より大きくなければ次のｎ個の特徴を含めた距離を計算する手順を繰り返して距離が前記文字候補選択しきい値を超えると、次の参照ベクトルとの比較に移る
文字認識システム。
【請求項８】
既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書記憶装置を備えるコンピュータを使用して、入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字のパターンの参照ベクトルとの距離を比較して文字認識を行う文字認識方法であって、
（ａ）前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出するステップと、
（ｂ）前記クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択するステップと、
（ｃ）前記入力パターンから得られる特徴ベクトルの特徴を、多数の参照ベクトルの特徴の距離平均値の大きさ順を示すリストに従って距離平均値の大きい順に並べ替えた後、まずｎ番目の特徴までについて前記参照ベクトルのうちの１つについてその対応する特徴との距離を計算するステップと、
（ｄ）(ｄ−１)前記距離を文字候補選択しきい値と比較するステップと、(ｄ−２)前記しきい値より大きくなければ次のｎ個の特徴を含めた距離を計算するステップとを繰り返して距離が前記文字候補選択しきい値を超えると、次の参照ベクトルとの比較に移るステップと
を含む方法。
【請求項９】
請求項８に記載の方法であって、
すべての特徴を含めた距離が前記文字候補選択しきい値を超えないとき、比較対象となった前記参照ベクトルに対応する文字を文字候補としてメモリに記憶する
方法。
【請求項１０】
請求項９に記載の方法であって、
ｍ番目に距離値の小さい文字候補の距離値を文字候補選択しきい値として動的に設定するステップ
を含み、
ｍは出力される文字候補の数である
方法。
【請求項１１】
請求項１０に記載の方法であって、
前記最も文字の出現頻度の高いクラスに属するすべての参照ベクトルに対する前記特徴ベクトルの距離の計算が完了したとき、これらの距離の１つまたは複数が前記クラスに対して定められたしきい値より小さいとき、小さい方から前記ｍ番目までの距離の参照ベクトルに対応するｍ個の文字を文字候補として選択する
方法。
【請求項１２】
既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書記憶装置を備えるコンピュータを使用して、入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字のパターンの参照ベクトルとの距離を比較して文字認識を行う文字認識方法であって、
（ａ）前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出するステップと、
（ｂ）前記クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択するステップと、
（ｃ）複数の前記文字候補が選択されることに応答して、任意の文字について類似関係にある文字を規定する類似文字辞書からそれぞれの文字候補に類似する文字を取り出すステップと、
（ｄ）認識すべき前記特徴ベクトルと前記類似する文字の参照ベクトルとの距離を計算するステップと、
（ｅ）前記複数の文字候補の距離値および前記類似する文字の距離値をソートするステップと、
（ｆ）距離値が最も小さい予め定めた数の文字を認識文字候補として出力するステップと
を含む方法。
【請求項１３】
既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書記憶装置を備えるコンピュータを使用して、入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字のパターンの参照ベクトルとの距離を比較して文字認識を行う文字認識方法であって、
（ａ）前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出するステップと、
（ｂ）前記クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択するステップと、
（ｃ）前記クラスしきい値より小さい距離が存在しないとき、２番目に文字の出現頻度が高いクラスに属する複数の文字の参照ベクトルに対する前記特徴ベクトルの距離を算出するステップと、
（ｄ）前記クラスに対して定められた第２のクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択するステップと、
（ｅ）複数の前記文字候補が選択されることに応答して、任意の文字について類似関係にある文字を規定する類似文字辞書からそれぞれの文字候補に類似する文字を取り出し、認識すべき前記特徴ベクトルと前記類似する文字の参照ベクトルとの距離を計算するステップと、
（ｆ）前記複数の文字候補の距離値および前記類似する文字の距離値をソートし、距離値が最も小さい予め定めた数の文字を認識文字候補として出力するステップと
を含む方法。
【請求項１４】
既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書と、コンピュータ・プログラムとを格納するコンピュータ読み取り可能な記憶媒体であって、
前記コンピュータ・プログラムは、
（ａ）入力パターンから抽出される特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離値を算出するステップと、
（ｂ）前記最も文字の出現頻度の高いクラスに対して定められたクラスしきい値よりも小さい距離値が存在するとき、前記距離値をもつ参照ベクトルの文字を文字候補として選択するステップと、
（ｃ）前記入力パターンから得られる特徴ベクトルの特徴を、多数の参照ベクトルの特徴の距離平均値の大きさ順を示すリストに従って距離平均値の大きい順に並べ替えた後、まずｎ番目の特徴までについて前記参照ベクトルのうちの１つについてその対応する特徴との距離を計算するステップと、
（ｄ）(ｄ−１)前記距離を文字候補選択しきい値と比較するステップと、(ｄ−２)前記しきい値より大きくなければ次のｎ個の特徴を含めた距離を計算するステップとを繰り返して距離が前記文字候補選択しきい値を超えると、次の参照ベクトルとの比較に移るステップと
をコンピュータに実行させる
コンピュータ読み取り可能な記憶媒体。
【請求項１５】
入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字の参照ベクトルとの距離を比較することによる文字認識を、コンピュータに実行させるプログラムと、前記既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、前記クラスごとに前記参照ベクトルを格納する辞書とを格納するコンピュータ読み取り可能な記憶媒体であって、
前記プログラムは、
前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出するステップと、
前記クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、前記距離に対応する参照ベクトルの文字を文字候補として選択するステップと、
複数の前記文字候補が選択されることに応答して、前記類似文字辞書からそれぞれの文字候補に類似する文字を取り出すステップと、
認識すべき前記特徴ベクトルと前記類似する文字の参照ベクトルとの距離を計算するステップと、
前記複数の文字候補の距離値および前記類似する文字の距離値をソートし、
距離値が最も小さい予め定めた数の文字を認識文字候補として選択するステップと
をコンピュータに実行させる
コンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、日本語、中国語、韓国語その他多数の文字を含む言語の文字認識に関する。
【０００２】
【従来の技術】
日本語、中国語、韓国語など多数の文字を含む言語の文字認識においては、入力パターンから特徴を抽出して特徴ベクトルを求め、認識対象となるすべての文字について予め用意された参照ベクトルとの距離を求めて、距離値の最も小さい参照ベクトルに対応する文字を認識文字として出力することが行われている。
特開平2-186490号公報には、入力された文字のパターンから得られるベクトルと予め記憶されている既知の文字のパターンから得られる参照ベクトルとの距離を計算して文字認識を行うシステムが記載されている。このシステムでは、入力パターンのベクトルと参照ベクトルとの間のユークリッド距離を計算し、予め定められたしきい値と比較して文字認識を行っている。
また、特開平4-286087号公報には、入力された文字パターンから特徴ベクトルを抽出し、特徴辞書に格納されている参照ベクトルとのユークリッド距離を求めて文字認識を行うシステムにおいて、特徴辞書を類似文字カテゴリごとにクラスタに分け、入力パターンの特徴ベクトルとそれぞれのクラスタを代表する参照ベクトルとの距離を調べ、距離が最も近いクラスタに属する類似文字の参照ベクトルについて詳細な識別処理を行うことが記載されている。
【０００３】
一般に、日本語、中国語、韓国語など文字数の多い言語においては、識別能力を高めるために、数百、数千といった非常に多くの特徴が用いられる。各候補文字に対する参照ベクトルとの距離に基づく文字認識システムにおいては、一般に、候補文字数と特徴数に比例した計算時間が必要となり、認識速度の低下が問題となる。具体的には、距離としてユークリッド距離、重み付きユークリッド距離、シティブロック距離などがあるが、
ユークリッド距離              Σi=1m(xi-ri)2
重み付きユークリッド距離      Σi=1mwi(xi-ri)2
シティブロック距離            Σi=1m|xi-ri|
ただし、
X=(x1,...,xm)      :入力パターンの特徴ベクトル
Rj=(rj1,...,rjm)    :候補文字ｊの参照ベクトル
W=(w1,...,wm)    :特徴の重みベクトル
ｍ                :特徴の数
ｎ                :対象文字数
いずれも、各特徴に関する距離成分(xi-ri)2, |xi-ri| の計算が n × m 回、つまり、（候補文字数）×（特徴数分）だけ必要になる。
上述の特開平4-286087号公報のものは、ユークリッド距離の計算対象を類似文字クラスタに限定することにより、処理速度を向上させている。しかしながら、類似文字クラスタを選択する基準となる代表ベクトルを適正に設定することには困難が予測され、代表ベクトルの品質によっては認識精度が低下することが予測される。
【０００４】
【発明が解決しようとする課題】
この発明は、候補文字数の多い言語において、利用する特徴の数が多い場合にも認識精度の低下をもたらすことなく文字認識の速度を向上させることを目的とする。
【０００５】
【課題を解決するための手段】
この発明は一面において次の構成の文字認識システムを提供する。すなわち、入力パターンから得られる特徴ベクトルと、予め格納されている既知の文字の参照ベクトルとの距離を比較して文字認識を行う文字認識システムであって、前記既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、該クラスごとに前記参照ベクトルを格納する辞書記憶装置およびコンピュータを備え、前記コンピュータは、前記特徴ベクトルと前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の前記参照ベクトルとの距離を算出し、該クラスに対して定められたクラスしきい値よりも小さい距離が存在するとき、該距離に対応する参照ベクトルの文字を文字候補として選択するようプログラムされている。参照ベクトルとの距離としてユークリッド距離、重み付きユークリッド距離、シティブロック距離などが用いられるが、ここでは一般に距離と呼ぶ。
【０００６】
また、既知の文字の出現頻度は、過去のニュース記事などの大量のテキスト形式の文書集合（これをテキストコーパスと呼ぶ）から統計情報として抽出されるものであり、発明者らは各言語ごとに約２０００万文字程度からなるテキストコーパスからこの出現頻度の統計値を求め利用している。この発明によると、既知の文字の出現頻度に基づいてすべての文字を複数のクラスに分類し、該クラスごとに参照ベクトルを辞書に格納しておき、前記複数のクラスのうち最も文字の出現頻度の高いクラスに属する複数の文字の参照ベクトルと入力文字パターンから抽出された特徴ベクトルとの距離計算を行い、基準を満たす値の距離値が得られるときは、その文字を文字候補として選択する。発明者が求めた統計によると、たとえば日本語の場合、出現頻度の最上位に属する３８２文字がテキストコーパスの約８０％を占める。従って、対象文書中においても約８０％の文字が、この出現頻度最上位３８２文字に含まれていることが期待できる。本発明はこのような統計的な文字出現頻度の偏りを利用するものであり、まず出現頻度最上位クラスに属する文字集合のみを候補文字集合とし、良好な認識結果が得られた場合に残りの低頻度文字集合の認識処理を省くことで文字認識処理の速度の向上を図る。実際には、候補文字集合は複数の候補文字集合に分割され、頻度順に認識処理が行われ、良好な結果が得られた集合より低頻度の集合の認識処理を省略するようにプログラムされている。
【０００７】
この発明は、さらに他の面において、前記クラスしきい値より小さい距離が存在しないとき、２番目に文字の出現頻度が高いクラスに属する複数の文字の参照ベクトルに対する該特徴ベクトルの距離を算出し、該クラスに対して定められた第２のクラスしきい値よりも小さい距離が存在するとき、該距離に対応する参照ベクトルの文字を文字候補として選択する。
また、もう一つの面によると、この発明のシステムは、前記参照ベクトルのうちの１つについての距離計算においても速度を向上させるために、全ての特徴に関する距離成分を累積して距離値を求める過程を、ｎ個の特徴成分を累積して累積距離値を計算するものとし、（１）該累積距離値を文字候補選択閾値と比較し、（２）該しきい値より大きくなければ次のｎ個の特徴成分の距離成分を累積計算し、（１）および（２）の手順を繰り返して累積距離値が前記文字候補選択閾値を超えると、当該参照ベクトルは候補外であると判断して次の参照ベクトルとの比較に移ることにより処理時間の短縮を図る。さらにこの発明によると、累積する距離成分の順番を変えることで、前記累積距離値に基づく距離計算過程の省略を効率よく行う。具体的には、全文字カテゴリの全訓練パターンを用いて、各特徴に関する距離成分の分布を求め、その平均値の高い順に距離成分の累積を行う。このような距離成分の並べ替えとしては、全候補文字の参照ベクトルに対して共通の並べ替えを行う方法と、各参照ベクトルごとに、距離成分の分布平均の大きい順に並べ替えを行う方法などがある。
【０００８】
参照ベクトルは、認識対象の全ての文字についての訓練パターンから特徴ベクトルを抽出して、例えば日本語については数百次元のベクトルとして作成される。全ての文字について各次元ごとに（つまり各特徴ごとに）距離成分の分布を見ると、この距離成分の平均が大きいことは、その次元の特徴は全体の距離値を大きくするように寄与することを意味する。正解文字である場合、距離値は小さくなることが期待されるので、このような次元の特徴は候補外であることを早期に判断するのに有効な特徴であると言うことができる。したがって、参照ベクトルを構成する全ての文字について次元ごとの距離成分の平均を予め訓練データから求め、この平均値の大きい順に各参照ベクトルの特徴値を並べ替えたベクトルを作成する。そして入力パターンから抽出される特徴ベクトルも、この順に並べ替えたベクトルを作成し、１つの参照ベクトルと特徴ベクトルとの距離計算において、距離成分の累積をこの順に行う。例えばまず、５０次元までの距離成分を累積した累積距離値を求め、これでしきい値に達すれば、この参照ベクトルは候補外文字であると判定して次の参照ベクトルとの比較に移る。こうすることにより、数百次元全てについて距離成分を計算することなく、認識処理を進めることができるので、認識処理の時間を短縮することができる。
【０００９】
さらにこの発明の一面によると、前記コンピュータは、ｍ番目（ｍは、選択される文字候補の数）に距離値の小さい文字候補の距離値を文字候補選択しきい値として動的に設定するようプログラムされている。
また、この発明は、他の面によると、さらに任意の文字について類似関係にある文字を規定する類似文字辞書を備え、前記コンピュータは、複数の前記文字候補が選択されることに応答して、前記類似文字辞書からそれぞれの文字候補に類似する文字を取り出し、認識すべき前記特徴ベクトルと前記類似する文字の参照ベクトルとの距離を計算し、前記複数の文字候補の距離値および前記類似する文字の距離値をソートし、距離値が小さい方から予め定めた数の文字を認識文字候補として選択するようプログラムされている。これにより、省略された低頻度文字候補クラスに正解が存在する場合にも、類似文字として候補に含めなおすことが可能となり、認識精度の低下を抑えることが可能となる。
【００１０】
【発明の実施の形態】
次に図面を参照して、この発明の実施形態を説明する。図１は、この発明を利用する日本語文字認識システムの１例の全体的構成を示す機能ブロック図である。このシステムは、汎用のパーソナルコンピュータまたはワークステーションの上で走るプログラムで実現される。一般にこのようなプログラムは、ＯＣＲ（Optical Character Recognition）プログラムと呼ばれる。システムへの代表的な入力パターンは、文書を光学的スキャナで走査して得られるイメージデータである。
入力パターンを受け取ると、ＯＣＲプログラムの文字切り出し部11がビットマップ形式のデータから文字を切り出す。文字の切り出し自体は、従来のＯＣＲプログラムに組み込まれている機能である。文字単位に切り出されたイメージデータが特徴抽出部１２に送られ、文字線の傾き、幅、曲率、面積、その他の特徴(features)が抽出される。この実施例では、日本語については一つの文字あたり200の特徴を抽出する。したがって、入力パターンは、次の式のような200次元のベクトルｘで表され、特徴ベクトル(feature vector)と呼ばれる。
【００１１】
【数１】
x=(x1,x2,・・・,x200)
こうして得られた特徴ベクトルが特徴の並べ替え部13に送られて、後に説明する距離成分平均順リストにしたがって特徴の並べ替えを行って新たなベクトルを生成し、文字候補選択部14に送られ、参照文字辞書15に格納されている複数の既知の文字の参照ベクトルのそれぞれに対する重み付ユークリッド距離が計算される。
ここで図２を参照して参照文字辞書15について説明する。ある一つの文字に対する参照ベクトルは、その文字の様々な書体や大きさのイメージパターンについて特徴ベクトルを抽出し、平均をとることによって得られる。このとき、特徴値ごとの分散を算出し、その逆数を重み係数とする重み付きユークリッド距離計算に使用する。
【００１２】
この手法自体は従来から使われている。認識対象となるすべての文字について参照ベクトルおよび重みベクトルを辞書23に格納する。こうして格納された辞書２３のすべての参照ベクトルにわたって、全ての訓練パターンを用いて各特徴成分ごとに距離成分の平均を求め、その大きい順に特徴の次元を並べ替えた距離成分平均順特長リスト２４を作る。辞書２３に格納されたそれぞれの参照ベクトル、重みベクトルの各特徴成分は、このリストに従って距離成分平均の大きい順に並べ替えられる。距離成分平均が大きいことは、候補文字においてその特徴成分における距離成分値が大きくなることが期待されるので、後に説明する距離計算においてこの距離成分平均の大きい順に距離計算を実行する。この目的のため、入力パターンから抽出された特徴ベクトルは、特徴の並べ替え部１３においてこの距離成分平均順特徴リストに従ってその特徴成分が並べ替えられる。
【００１３】
図２のテキスト・コーパスは、社会一般で使われる文書のテキスト形式化された集合であり、たとえばオンラインニュースなどの情報源から文書を蓄積したものである。この文書の集合からそれぞれの文字の出現頻度を算出し、出現頻度に応じて文字を３つのクラスに分類する。発明者の観測によると、中国語、日本語および韓国語は、各言語約２０００万文字からなるテキストコーパスを利用して次の表のように分類することができる。
【００１４】
【表１】
0004674778.tif 000002
すなわち、日本語について述べると、クラス１に分類される最も出現頻度の高い382の文字がテキスト・コーパスの80.01%を占め、これに次に出現頻度の高いクラス２の1126文字を加えると、テキスト・コーパスの99.00%を占める。さらにこれにクラス３に分類される出現頻度の低い1459の文字を加えると、テキストコーパスを９９．９６％カバーすることができる。これはＪＩＳ第２水準まで入れると約６０００文字程度存在する日本語の文字認識システムを構築する上で、そのうちの２９６７文字のみを対象としても高々０．０４％の候補外文字が存在するだけで実害が少ないことを意味する。また、対象とする２９６７文字においてもかなりの統計的頻度の偏りがあることが分かる。これは中国語、韓国語についても同様の観測が見られる。
【００１５】
この発明は、一実施形態において、このような観測に基づいて、参照ベクトルの辞書15に含まれる参照ベクトルを表１に従って３つのクラスに分ける。入力パターンの特徴ベクトルとの距離計算にあたっては、まずクラス１の参照文字のそれぞれとの距離を求め、十分距離の小さい、すなわち近似度が十分高い参照ベクトルが存在するときは、クラス１の参照ベクトルに対する距離計算で認識処理を終了し、クラス２およびクラス３の参照ベクトルに対する距離計算は行わない。この場合、382の参照ベクトルとの距離計算で距離計算を終了し、クラス２の1126の参照ベクトルおよびクラス３の1459の参照ベクトルに対する距離計算を省略するので、その特徴ベクトルについて実行する距離計算の時間を大幅に短縮することができる。
入力パターンの特徴ベクトルとクラス１の382個の参照ベクトルとの距離計算の結果、十分小さい距離値の参照ベクトルが存在しないときは、クラス２の1508個の参照ベクトルとの距離計算を実行し、十分小さい距離値の参照ベクトルがあるときには、クラス２の参照ベクトルに対する距離計算で計算を終了し、クラス３の参照ベクトルに対する距離計算は、行わない。これによって、距離計算の時間を短縮することができる。
【００１６】
クラス２の文字まででテキスト・コーパスの99%を占めるから、クラス１およびクラス２の参照ベクトルとの距離計算で適切な文字候補を見つけることができない文字は、所与のテキストに約１%存在すると期待される。この約1%の入力パターンの特徴ベクトルについては、クラス１およびクラス２の参照ベクトルとの距離計算を経てクラス３の参照ベクトルとの距離計算に入る。こうしてクラス３の参照ベクトルのうち距離が小さいものが文字候補として選択される。
このようにして文字候補選択部14で文字候補が選択されると、プロセスは、類似文字処理部16に移る。類似文字処理部16は、類似文字辞書17を参照して文字認識の精度を向上させる。類似文字辞書には、それぞれの文字について、文字認識上混同しやすい文字のリストが用意されている。類似文字処理部16は、文字候補選択部14から１つまたは複数の文字候補を受け取ると、それぞれの文字候補について類似文字辞書を参照して類似文字を読み出し、この類似文字の参照ベクトルを参照ベクトル辞書15から読み出す。
【００１７】
入力パターンから抽出された特徴ベクトルと複数の類似文字の参照ベクトルとの距離計算を実行し、文字候補および類似文字を含めた集合の中で最も距離値が小さい所定数の文字を最終的な文字候補として出力する。ここで、最終的というのは、距離計算による文字認識段階を終了することを意味する。実際の文字認識プログラムでは、この後、一般に後処理と呼ばれるプロセスが実行される。後処理は、文脈の分析、連接関係の分析、文字相互間の出現確立などに基づいて文字候補の優先順位を決める処理である。後処理自体は、従来から使われている技術なので、詳細な説明は省略する。
【００１８】
クラス１文字候補選択プロセス
次に図３を参照して、この発明の一実施例の文字認識システムのプロセスの流れを説明する。これはクラス１の候補文字集合から１０個の候補文字を選択するプロセスである。スキャナによって文書を走査して得られる入力パターンがこの発明の一実施例の文字認識プログラムに渡されると（301）、文字切り出し部11（図１）において、イメージデータから個々の文字領域が切り出され、個々の文字領域について特徴抽出部12（図１）で前述したように特徴抽出が行われる（302）。こうして得られた特徴ベクトルは、特徴の並べ替え部13に送られ、図２に関連して説明した距離成分平均順特徴リストにしたがって特徴が並べ替えられる（303）。次に最初の１０個の参照ベクトルのそれぞれについて全次元にわたる１０個の距離値が算出され（304）、しきい値Thがこうして得られた１０個の距離値のうち最も大きい距離値にセットされる（314）。距離値は、重み付ユークリッド距離値を用い、下に示す数２において、j=1〜200として計算される。ついで参照ベクトル辞書15から読み出すクラス１参照ベクトルの番号ｉを11と、変数の初期値をｋ＝０、ｍ＝０に設定し（305）、距離計算に含める特徴ベクトルおよび参照ベクトルの次元ｊ＝ｍ＋５０×ｋ、として、ｍを１〜５０まで変化させる（306）。こうして参照ベクトルと特徴ベクトルとの次元１から50までの距離Ｄiが次の式によって計算される（307）。
【００１９】
【数２】
Ｄi=Σｗj（xj-ｒj）2
（j=1〜50）
ここで、ｗjは、図２の参照ベクトル辞書２３に関連して説明したそれぞれの参照ベクトルにおける重みベクトルの各成分である。xjが入力パターンから得られる特徴ベクトルの各成分を表し、ｒjが参照ベクトルの各成分を表す。数２で得られる値の平方根をとった値が重み付きユークリッド距離と呼ばれる距離値である。ここでは、簡単のために平方根をとる前の値を重み付ユークリッド距離の目安として使用し、距離と呼んでいる。参照ベクトルとの距離Ｄiがしきい値Thを超えるときは(321)、この参照ベクトルはこの特徴ベクトルに対する文字候補として不合格と判定する。そのとき、ステップ312でクラス１の382個のすべての参照ベクトルについて距離の比較が終わったかどうか判定し、終わっていなければｉをインクリメントして次の参照ベクトルとの距離Ｄiの計算を行う（307）。参照ベクトルとの距離Ｄiがしきい値(Th)以下であると(321)、次元ｊが200に達したかどうか点検し（308）、達していなければ、ｋをインクリメントして（309）、jを次の5１〜100次元の距離を求める。こうして、j=51〜100について距離を計算して、先にj=1〜50について計算した距離に加算し、j=1〜100についての距離Ｄiを算出する（307）。
【００２０】
この結果、ＤiがThを超えると、ステップ312を経てiをインクリメントし、次の参照ベクトルとの比較に移る。ＤiがTh以下であれば、ステップ309を経てさらに、ｋをインクリメントして、距離Ｄi、すなわちj=100〜150についての距離Ｄiを算出する（307）。この処理を繰り返してＤiがTh以下の状態でj=200に達すると、すなわちすべての次元を含めた距離Ｄiがしきい値以下であると、そのときの参照ベクトルに対応する文字をシステムの出力の候補となる文字候補としてメモリに記憶する（310）。このメモリには、プロセスの最初に参照された１０個の参照ベクトルの文字コードおよびその距離値が記憶されている。新しい文字候補をこのメモリに入れるとともに先に記憶されている文字コードのうち最も距離値の大きい文字をメモリから削除する。こうして、メモリには最も距離値が小さい順に10個の文字候補が記憶されるようにする。そして、10個の文字候補の距離値のうち、最も大きい値を新たなしきい値Thとして設定する（311）。後続の参照ベクトルとの比較の結果、新たな文字候補がメモリに渡されると、それまでにメモリに記憶されていた10個の文字候補のうち最も距離値の大きい文字候補がメモリから削除され、新たな文字候補がメモリに追加される。そして新たな１０個の文字候補のうちの最大の距離値がしきい値Thとしてセットされる。
【００２１】
このように文字候補の数が１０個に達した後は、ブロック307で判定に使われるしきい値は動的に変更される。ブロック312においてi=382が満足され、すなわちクラス１の参照ベクトルすべてについての距離計算が終了すると、メモリに記憶された10個の文字候補の距離値のうち最も小さい距離値Dbestがクラス１の文字候補選択用に予め設定されたクラスしきい値Thstage1よりも小さいかどうか判定する（318）。Thstage1は、この実施例ではたとえば120,000に設定する。この条件を満足する文字候補があることは、クラス１における文字候補選択処理において十分近似度の高い文字候補が得られたことを意味する。したがって、この場合、メモリに記憶された10個の文字候補を類似文字処理部16に渡し、この入力パターンの特徴ベクトルについての文字候補選択処理(14)を終了する。
【００２２】
クラス２文字候補選択プロセス
ブロック318の条件が満足されないときは、クラス２の参照ベクトルから文字候補を選択するプロセスに入る（320）。図４を参照してクラス２の文字候補選択プロセスを説明する。いま日本語の文字認識を行っているので、参照ベクトル辞書15には、クラス２の参照ベクトルとして1126個の既知の文字に対する参照ベクトルおよび重みベクトルが格納されている。クラス２の文字候補選択プロセスに入ると、iを１、ｋ＝０、ｍ＝０に初期設定し（502）、距離計算の対象となる特徴ベクトルおよび参照ベクトルの次元ｊをｊ＝ｍ＋５０×ｋ、として、ｍを1から50まで変化させ(503)、第ｉ参照ベクトルと入力パターンから抽出された特徴ベクトルとの距離値Ｄiの計算を実行する（504）。距離値Ｄiがしきい値Thより大きく(515)、かつｉ＝1126に達していない時には(510)、iをインクリメントして（511）、次の参照ベクトルに対する距離値の計算に移る。
【００２３】
距離値Ｄiがしきい値Th以下であるときは、ｋをインクリメントして次の50次元、すなわちj=51〜100として距離値を計算し、その値を先に求めたj=1〜50についての距離値に加算してj=1〜100についての距離値Ｄiを求める（504）。距離値ＤiがThを超え、かつｉ＝1126に達していない時には（510）、ｉをインクリメントして次の参照ベクトルとの距離値計算に移る（511）。ＤiがThを超えていないときは、ｋをインクリメントして、ｊを次の50次元にインクリメントし、前述したのと同様のプロセスによりj=1〜150についての距離値Ｄiを求める（504）。このプロセスを繰り返し、ＤiがThを超えない状態でj=200に達すると（505）、この参照ベクトルに対応する文字コードをメモリに入れる（508）。メモリには先のクラス１の文字候補選択プロセスで選ばれた文字候補が記憶されている。文字候補の数が１０個に達していれば、距離値が最も大きい文字候補をメモリから削除し、新たな文字候補を加えて、文字候補の数を１０個に維持する。そして、１０個の文字候補の距離値のうち最も大きい距離値を新たなしきい値Thとする（509）。
【００２４】
その後は、参照ベクトルがブロック515のテストを通り、メモリに入れられると（508）、上述したのと同様の文字候補の入れ替えが行われ、しきい値Thが動的に変更される。ブロック510でi=1126が満足されるとき、すなわちクラス２の1126個すべての参照ベクトルについて文字候補選択プロセスが実行されると、メモリに記憶された10個の文字候補の距離値のうち最小のものがクラス２のクラスしきい値Thstage2より小さいかどうか判定され（512）、小さければ文字候補選択プロセス(14)を終了して、この10個の文字候補を類似文字処理部16（図１）に渡す。Th stage2は、この実施例ではたとえばThstage1よりも大きい150,000に設定する。すなわちクラス２のクラスしきい値は、クラス１のクラスしきい値よりも緩いものにする。ブロック512の条件が満足されないときは、クラス３の参照ベクトルに対する文字候補選択プロセスに移る。
【００２５】
クラス３文字候補選択プロセス
図５は、クラス３の1459個の参照ベクトルに対する文字候補選択プロセスを示す。ブロック602から610は、ブロック610での判定がクラス３の参照ベクトルの数1459であることを除いて図４のブロック502から510と同じである。したがって、これらのブロックの機能についての説明は省略する。ブロックで610でi=1459が満足され、クラス３の1459個すべての参照ベクトルについて文字候補選択プロセスが終了すると、文字候補選択処理を終わり、メモリに記憶された10個の文字候補を類似文字処理部16に渡す。このとき、メモリに蓄積された文字候補の数が１０個に満たないときは、そのすべての文字候補を類似文字処理部16に渡す。
【００２６】
類似文字処理
次に図６を参照して類似文字処理のプロセスを説明する。図１の類似文字処理部16は、文字候補選択部14から10個の文字候補を受け取ると、それぞれの文字候補について類似文字辞書を参照し、類似文字を読み出す（41）。この類似文字の参照ベクトルおよび重みベクトルを参照ベクトル辞書15から読み出して、入力パターンから抽出された特徴ベクトルとの距離値を算出する（42）。読み出したすべての類似文字について重み付ユークリッド距離値を算出した後、10個の文字候補およびこれらの類似文字の距離値をソートして距離値が小さい順に10個の文字を選ぶ（43）。
【００２７】
こうして得られた10個の最終候補のうち距離値が最小のものを認識文字として出力し、残りの9個の文字を代替候補として出力する。ここでは、文字候補の選択を既知の文字についての参照ベクトルとの比較だけに基づいて行っているが、文字候補選択の途中の段階、あるいは文字候補の選択が完了した段階で、テキストの文法的解析、単語の連接関係、文字相互間の依存関係などに基づいて文字候補の優先度を変更する、いわゆる後処理と呼ばれる処理を実行することが好ましい。
ＯＣＲプログラムの出力としてユーザにはこうして得られた最高位の優先度の文字の集合としてテキストが提示される。ユーザは、テキストの文脈からＯＣＲ出力に認識誤りを見つけることがある。この場合、ユーザがエラー文字をクリックすると、プルダウンの形態で９個の代替文字が表示され、ユーザがそのうちの一つをクリックすると、その文字がエラー文字を置き換える。
以上にこの発明を特定の実施例について説明したが、この発明は、このような実施例に限定されるものではない。
【図面の簡単な説明】
【図１】この発明の一実施例の文字認識システムの全体的な構成を示す機能ブロック図である。
【図２】この発明の一実施例で使用する辞書の概念を説明するためのブロック図である。
【図３】クラス１の参照ベクトルから文字候補を選択するプロセスを示すフローチャートである。
【図４】クラス２の参照ベクトルから文字候補を選択するプロセスを示すフローチャートである。
【図５】クラス３の参照ベクトルから文字候補を選択するプロセスを示すフローチャートである。
【図６】類似文字処理のプロセスを示すフローチャートである。
【符号の説明】
１０  文字切り出し部
１２  特徴抽出部
１３  特徴の並べ替え部
１４  文字候補選択部
１５  参照ベクトル辞書
１６  類似文字処理部
１７  類似文字辞書
【図１】
0004674778.tif 000003
【図２】
0004674778.tif 000004
【図３】
0004674778.tif 000005
【図４】
0004674778.tif 000006
【図５】
0004674778.tif 000007
【図６】
0004674778.tif 000008