JPS6339093A - 辞書検索方式 - Google Patents

Abstract

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

Description

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

〔従来技術〕

光学的文字認識装置においては、未知入力文字パターン
から抽出したパラメータのベクトルと。

辞書のテンプレートのベクトルとの各次元の要素の積和
計算を行って、両ベクトル間つまり未知入力文字パター
ンとテンプレートとの距離を求め、その距離が最小のテ
ンプレートを候補として検索する。

具体的には、未知入力文字パターンのパラメータ（未知
入力パラメータ）のベクトルの各次元主の要素をＸｉ、
テンプレートｊの次元ｉの要素をＴｊ　ｉ、ベクトル次
元数を１２８とすると、距離Ｄｊは式 ％式％ しかし従来は、すべてのテンプレートに関して。

このような積和計算を最終次元の要素まで行っていた＼
め、その演算時間が長く、検索処理に長い時間を必要と
していた。

〔目　的〕

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

〔構　成〕

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

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

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

つまり、その段階で候補から排除し、その距離演算を途
中で打ち切ることができる。

本発明は、このようなベクトルの性質に着目して、候補
となり得ないようなテンプレートに関する距離演算を早
い段階で打ち切ることにより、辞書検索の効率化を達成
しようとするものである。

すなわち、本発明による辞書検索方式は、打切判定用閾
値を保持する手段と、各テンプレートのベクトルの各次
元までの積和計算値を前記閾値と比較する手段とを有し
、各テンプレートに関する距離計算の途中で積和計算値
が打切判定用閾値を超えた場合に当該テンプレートに関
する距離計算を打ち切り、当該テンプレートを検索候補
から排除することを特徴とするものである。

〔実施例〕

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

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

この図において、１０はメモリであり、これには第２図
に示すような構造の辞書テーブル１１および未知文字テ
ーブル１２が格納される。こ−では文字認識を目的とし
ているので、辞書テーブル１１には各文字毎に、そのテ
ンプレートのベクトルの要素と文字コードが記憶される
。また、未知文字テーブル１２には、未知入力文字パタ
ーンから抽出されたパラメータ、つまりベクトルの要素
が記憶される。

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

１３は辞書検索処理の制御などを行うための制御部であ
る。

１４は制御部１３による制御下で、未知入力パラメータ
のベクトルと辞書のテンプレートのベクトルとの積和演
算を行うための演算器である。

１５！は制御部１３より設定される打切判定用閾値ＴＨ
を保持するためのレジスタである。

１６は制御部１３より設定される候補文字コードと距離
を保持するためのレジスタである。

１７は比較器であり、そのＡ入力には演算器１４の出力
値が与えられる。この比較器１７のＢ入力には、セレク
タ１８を介して、レジスタ１５から打切判定用閾値また
はレジスタ１５から候補文字の距離が与えられる。この
レジスタ１８による選択は制御部１３によって制御され
る。

なお、制御部１３、演算器１４、および比較器１７はマ
イクロプロセッサによって実現してもよい。また、レジ
スタ１５．１６はマイクロプロセッサ内のレジスタまた
はメモリ１１上の特定領域として実現してもよい。

次に、辞書検索動作について説明する。制御部１３の制
御によって、辞書テーブル１１から最初の文字から、一
つのテンプレートのベクトルの要素が次元順に読み出さ
れ、同時に未知文字テーブル１２からベクトルの要素が
、次元順に順次読み出され、それぞれ演算器１４に入力
される。

演算器１４によって両ベクトルの同一次元要素の積和計
算が行われるが、一つの次元の積和計算が終了する度に
、比較器１７はＡ、Ｂ入力の値の比較を行う、なお、一
つのテンプレートに関する距離計算の途中においては、
セレクタ１８はレジスタ１５側を選択しており、Ｂ入力
には打切判定用閾値が与えられている。

比較器１７による比較結果がＡ≦Ｂならば、制御部１３
は引き続き次の次元の要素を読み出して演算器１４に入
力する。

あるテンプレートｂ”−関する距離演算の途中において
、比較Ｗ１７の比較結果がＡ＞Ｂとなると、つまり積和
計算値が打切判定用閾値を超えた場合。

そのテンプレートに関する距離演算を打ち切って、その
テンプレートを候補から除外し、次のテンプレートとの
距離計算に移行する。

あるテンプレートに関して、最終次元（この実施例では
次元１２８）まで距離演算が進んだ段階で、比較器１７
の比較結果がＡ≦Ｂの場合、制御部１３はセレクタ１８
をレジスタ１６側に切り替える。これにより、比較器１
７のＢ入力にそれまでの候補文字を未知入力文字との距
離が与えられる。

この比較結果がＡｊＢならば１次のテンプレートに関す
る距離計算に進む。

比較結果がＡ＜Ｂならば、現在のテンプレートを新しい
候補として、その文字コードと距離（演算器１４の出力
値）をレジスタ１６に改めて設定し、次のテンプレート
との距離計算に進む。

このようにして、最後のテンプレートとの距離計算が完
了すると、最終的な候補文字コードと距離がレジスタ１
６に得られ、辞書検索処理を終了する。

なお、辞書検索処理の開始に先立って、レジスタ１６は
リセットされることは当然である。

こ＼まで説明したように、候補となり得ないテンプレー
トに関しては、距離計算の途中で積和値が打切判定用閾
値を超え、その距離計算が打ち切られる。したがって、
候補となり得ないテンプレートに関する無駄な演算時間
が節約されるので、辞書検索処理全体の時間を大幅に短
縮できる。

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

例えば辞書の形態は適度変形することができる。

また、距離も１例えば次の式 によって計算してもよい。

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

〔効　果〕

以上の説明から明らかなように、本発明によれば、候補
となり得ないテンプレートの距離演算は途中で打ち切ら
れるから、辞書検索時間を大幅に短縮し効率的な辞書検
索が可能となる。

【図面の簡単な説明】

第１図は本発明の一実施例の機能的構成を簡略化して示
すブロック図、第２図は辞書テーブルおよび未知文字テ
ーブルの構造説明図である。 １１・・・辞書テーブル、 １２・・・未知文字テーブル、 １３・・・制御部、　１４・・・演算器、１５・・・打
切判定用閾値保持レジスタ、１７・・・比較器。

Claims (1)

【特許請求の範囲】
1. （１）未知入力パラメータによるベクトルと辞書のテン
   プレートのベクトルとの同一次元の要素の積和計算を順
   次行って両ベクトル間の距離を算出し、距離が最小のテ
   ンプレートを検索する辞書検索方式において、打切判定
   用閾値を保持する手段と、各テンプレートのベクトルの
   各次元までの積和計算値を前記閾値と比較する手段とを
   有し、各テンプレートに関する距離計算の途中で積和計
   算値が打切判定用閾値を超えた場合に当該テンプレート
   に関する距離計算を打ち切り、当該テンプレートを検索
   候補から排除することを特徴とする辞書検索方式。