JPS6339092A - 辞書検索方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔技術分野〕 本発明は、光学的文字認識装置などにおける辞書検索方
式に関する。

〔従来技術〕

光学的文字認識装置においては、未知入力文字パターン
から抽出した特徴ベクトルと、辞書のテンプレートのベ
クトルとの同一次元の要求の積和計算を行って、両ベク
トル間つまり未知入力文字パターンとテンプレートとの
距離を求め、その距離が最小のテンプレートを検索する
。

具体的には、未知入力文字パターンの特徴ベクトルの各
次元ｉの要素をＸｉ、テンプレートｊの次元ｉの要素を
Ｔｊｉ、ベクトル次元数を１２８とすると、距離Ｄｊは
式 ％式％ しかし従来は、すべてのテンプレートに関して、このよ
うな距離計算を最終次元の要求まで行っていたため、そ
の演算時間が長く、検索処理に長い時間を必要としてい
た。

〔目　的〕

したがって、本発明の目的は、そのような距離計算時間
を短縮して検索処理の効率化を図った辞書検索方式を提
供することにある。

〔構　成〕

文字認識などに用いられるベクトルは一般に、全ての次
元の要求が均等な識別力を持っているわけではなく、次
元によって識別力に違いがある。

例えば１本出願人は特願昭５９−２１７７６０号などに
よって多層方向ヒストグラム法による文字認識技術を提
案している。この多層方向ヒストグラム法は、手書き漢
字などの変形が大きく文字種の多い文字の認識に強いが
、ここで用いられるベクトルでは、そのような次元によ
る識別力の違いが顕著である。

したがって、テンプレートのベクトルの各要求を識別力
の大きな次元順、具体的には、分散または標準偏差の大
きな次元順に並べ替えておき、未知パターンのベクトル
の要求も同じ次元順で並べ替えて、テンプレートのベク
トルとの積和計算を次元順に順次行えば、候補となり得
ないテンプレートに関しては、比較的少ない次元数だけ
積和計算を行った手術で、その値が十分大きくなる。

このようなベクトルの性質を考慮し、距離計算の途中で
、その計算値とある閾値とを比較し、計算値がその閾値
を越えた場合に、その距離計算を途中で打ち切るように
すれば、無駄な距離計算時間を省き、辞書検索を効率化
することができるであろう。

しかし、そのような打切判定のための閾値を固定すると
、別の問題が起こりやすい。すなわち。

閾値を小さく設定すれば、距離計算の打切頻度が増加し
、また打切段階が早くなるが、候補文字が見つからない
リジェクトが発生しやすい。

逆に、閾値を大きな値に設定すれば、そのような問題は
起こらないが、距離計算の途中打切による時間節約効果
が減少してしまう。

他方、未知パターンとの距離が十分に小さくなるテンプ
レートは、全テンプレート中のごく一部のものに限られ
る。

本発明は、前記諸点を考慮してなされたものであり、リ
ジェクト発生の問題などを回避し、かつ辞書検索時間を
十分に短縮できる辞書検索方式を提供することを目的と
している。

この目的を達成するための本発明の辞書検索方式は、打
切判定用閾値を保持するための手段と、各テンプレート
に関する距離計算の途中でその計算値を前記打切判定用
閾値と比較する手段と、未知パターンの候補としてテン
プレートが選ばれる度にそのテンプレートに関する距離
を前記打切判定用閾値として改めて設定するための手段
を有し、各テンプレートに関する距離計算をその計算値
が前記打切判定用閾値を越えた段階で打ち切ることを特
徴とするものである。

〔実施例〕

以下、図面を参照して１本発明の一実施例について詳細
に説明する。

第１図は、本発明の一実施例の機能的構成を簡略化して
示すブロック図である。

この図において、１０はマイクロプロセッサである。後
述の距離計算、その計算値と打切判定用閾値との比軟判
定、その他の制御などの機能は。

このマイクロプロセッサ１０のハードウェアを利用して
プログラムにより実現される。

１１はメモリである。辞書テーブル２０、未知文字テー
ブル２１、打切判定用閾値を保持するためのＴＨレジス
タ２２、および候補文字コード保持用のＣＤレジスタ２
３は、このメモリ１１上に置かれる。また、前記プログ
ラムもこのメモリ１１に格納される。

ここでは文字認識を目的としているので、辞書テーブル
１１には各文字毎に、そのテンプレートのベクトルと文
字コードが記憶される。またご未知文字テーブル１２に
は、未知文字パターンから抽出された特徴ベクトルが記
憶される。

そして例えば、各ベクトルはそれぞれ前記多層方向ヒス
トグラム法によるベクトルであって、テンプレートのベ
クトルの要素はその分散または標準偏差の大きい次元順
に並べ替えられている。同様に、未知文字テーブル１２
のベクトルも予め同じ次元順が並べ替えられている。

また、辞書のテンプレートの配列順に関しては、打切判
定用閾値が早く減少するほど、それ以降のテンプレート
に関する距離計算の打切時点が早まるので、文字の出現
頻度順にテンプレートを並べると、検索時間の短縮効果
が増加する゛。

そこで、例えば英字の場合、小文字を優先し。

その出現頻度順にテンプレートが並べられている。

手書き文字の場合は様々の変形があるので、一つの文字
について複数のテンプレートが容易される。この場合、
出現頻度の大きいテンプレート（４１１準形に対応する
テンプレート）が先に並べられる。

追番による識別番号などの認識を行う場合は、上位桁の
数字の出現頻度などを考慮して、１，２゜３、・・・、
９，０の順にテンプレートが並べられる。

次に、辞書検索処理について説明する。第２図は、その
処理の概略フローチャートである。

まず準備処理のステップ１００，１０２において、テン
プレート番号ｊをカウントするためのｊカウンタ２４お
よび次元ｉをカウントするためのｉカウンタ２５（いず
れのカウンタもマイクロプロセッサ１０の内部レジスタ
）に初期値１がセットされ、ＴＨレジスタ２２に最大値
がセットされ、また距離計算用のＤレジスタ２６（マイ
クロプロセッサの内部レジスタ）がクリアされる。

次のステップ１０４において、テンプレートｊと未知文
字パターンのベクトルの次元ｉの要素がマイクロプロセ
ッサ１ｏに読み込まれ、その要素の差の絶対値が計算さ
れる。そして、その値とＤレジスタ２６の値とが加算さ
れ、その加算の結果値がＤレジスタ２６に改めてセット
される。

次のスタック１０６において、ｉカウンタ２５の値がベ
クトルの次元数（ここでは１２８）と比較される０等し
くなければ（ｉ＜１２８）ステップ１０８に進むが、ｉ
　＝　１２８ならばステップ１１０に進む。

ステップ１０８に進んだ場合、つまりテンプレートｊに
関する距離演算の途中の場合、Ｄレジスタ２６の値（そ
の時点までの距離計算値）とＴＨレジスタ２２の値（打
切判定用閾値）との比較判定が行われる。

この判定でＤ≦ＴＨならば、ステップ１１２によってｉ
カウンタ２５が１だけインクリメントされた後、ステッ
プ１０４に戻り、次の次元ｉに関する距離計算が行われ
る。

ステップ１０８においてＤ＞ＴＨの場合、つまり現次元
までの距離計算値りが打切判定用閾値ＴＨを越えた場合
、現テンプレートに関する距離計算がこの段階で打ち切
られ、ステップ１１４に進む。　ステップ１１４におい
て、ｊカウンタ２４の値が最終テンプレート番号と比較
される。最終テンプレート番号でなければ（未検査のテ
ンプレートが残っている）、ステップ１１６によりｊカ
ウンタ２４が１だけインクリメントされたのちステップ
１０２に戻り、次のテンプレートに関する距離計算が始
まる。

ステップ１０６からステップ１１０に進んだ場合、現テ
ンプレートに関する距離計算が途中で打ち切られず、ベ
クトルの最終次元まで行われたということである。

この場合、ステップ１１０において、Ｄレジスタ２６の
値（現テンプレートと未知パターンとの距離）とＴＨレ
ジスタ２２の値（それまでに距離が最小であった候補テ
ンプレートの距離）が比較される。

この比較でＤ＜ＴＨならば、ステップ１１８において、
現テンプレートが新しい候補となり、その文字コードが
ＣＤレジスタ２３にセットされ、また、その距離である
Ｄレジスタ２６の値が新しい打切判定用閾値としてＴＨ
レジスタ２２にセットされたのち、ステップ１１４に進
む。

ステップ１１０においてＤ≧ＴＨの場合、現テンプレー
トは新しい候補とはされない、したがって、この場合、
ステップ１１８はスキップされる。

このように、それまでの候補としてのテンプレートに関
する距離（ＴＨレジスタ値）よりも距離が小さいテンプ
レートが見つかる度に、そのテンプレートが新たに候補
とされ、その距離が改めて打切判定用閾値として設定さ
れる。

最後のテンプレートの検索が終わると、ステップ１１４
の条件が成立し、辞書検索処理を終了する。

このように、候補が見つかる度にそのテンプレートに関
する距離が打切判定用閾値として設定されるので、検索
の進行に従い打切判定用閾値が減少し、距離計算の途中
打切段階が早くなる。その結果、辞書検索時間が大幅に
短縮される。この時間短縮効果は、辞書のテンプレート
配列を前述のようにすれば、一層顕著となる。

また、打切判定用閾値を固定する場合と違い、その初期
値を十分大きな値に設定できるので、リジェクトの発生
を防止できるため、認識率の向上と辞書検索時間の短縮
を同時に達成できる。

以上、一実施例について説明したが、本発明はそれだけ
に限定されるものではない。

例えば、前記実施例においては、出現頻度の小さな文字
が入力された場合、打切判定用閾値の減少が遅くなる。

これに対処するために、打切判定用閾値の初期値として
最大値でなく小さい値を設定して辞書検索を行い、リジ
ェクトが発生した場合に、最大値を打切判定用閾値とし
て改めて設定して辞書検索を再度行うようにしてもよい
。

また、パターンマツチング方式の辞書の場合、一つのテ
ンプレートの要素が多く距離計算時間が長い。そして、
パターンマツチングのテンプレートは一般に各要素に重
みを付けて距離計算を行う。

したがって、パターンマツチング方式の辞書の場合、一
つのテンプレートの距離計算を行うに当たって、まず重
みがある値以上の要素だけΣｃｏｄｅ×にの演算を行う
、ここで、ｃｏｄｅはＸとＴの白黒の組合せで決まる符
号、ｋは重みである。

その計算値を打切判定用閾値と比較し、同閾値以上なら
ば演算を打ち切る。その計算値がその閾値より小さい場
合には、残りの要素についても距離計算を行い、最終的
な距離を求める。

このようにすれば、前記実施例と同様の効果を達成でき
る。

前記の変形例以外にも、本発明はその要旨を逸脱しない
範囲内で様々に変形して実施することができるものであ
る。

また、本発明は、文字認識以外のパターン認識などの分
野における辞書検索にも同様に適用できることは、勿論
である。

〔効　果〕

以上の説明から明らかなように、本発明によれば、候補
となり得ないテンプレートの距離演算は途中で打ち切ら
れるから、辞書検索時間を大幅に短縮し効率的な辞書検
索が可能であり、また打切判定用閾値を固定する場合に
おけるようなりジエクト発生などの問題も回避できる。

【図面の簡単な説明】

第１図は本発明の一実施例の機能的構成を簡略化して示
すブロック図、第２図は辞書検索処理の概略フローチャ
ートである。 １０・・・マイクロプロセッサ、　　１１・・・メモリ
、２０・・・未知文字テーブル、　２１・・・辞書テー
ブル、　２２・・・打切判定用閾値を保持するためのＴ
Ｈレジスタ。 第２図

Claims (1)

【特許請求の範囲】
1. （１）未知パターンのベクトルと辞書のテンプレートの
   ベクトルとの距離を算出し、距離が最小のテンプレート
   を検索する辞書検索方式において、打切判定用閾値を保
   持するための手段と、各テンプレートに関する距離計算
   の途中でその計算値を前記打切判定用閾値と比較する手
   段と、未知パターンの候補としてテンプレートが選ばれ
   る度にそのテンプレートに関する距離を前記打切判定用
   閾値として改めて設定するための手段を有し、各テンプ
   レートに関する距離計算をその計算値が前記打切判定用
   閾値を越えた段階で打ち切ることを特徴とする辞書検索
   方式。