JPS61163479A - 分類処理回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は分類処理回路のパターン認識処理に関し、特に
多数カテゴリのなかから抽出された特徴値に対して最も
マツチングのとれた複数の上位カテゴリを求める分類処
理に関する。

（従来の技術） 従来から一般に、分類処理を行うためには各カテゴリご
とに相違度Σｆ　（：ｔ　＊　ｙ　）の演算を行い、全
カテゴリ分の演算が終った後に全カテゴＩＪ　Ｋ対応す
る相違度を探索し、最も小さな相違度のカテゴリを求め
て第１位のカテゴリとしていた。ここで、ｆｃａｅ、ｙ
）は、例えば、ｆ（ｚ）＝特徴値であり、ｆ（ｙ）はｆ
（ｒ）に対する比較データであって、ｆ　（ｚ　、ｙ　
）＝Ｉ　ｆ（ｇ）　−ｆ（ｙ）ｌまたは（ｆ　（ｇ）　
−ｆ　（ｙ）　）”　　などによって与えられるもので
ある。さらに、上式において第１位を除くカテゴリにつ
いて相違度を探索し、最も小さい相違度のカテゴリを第
２位のカテゴリとして設定していた。このような一連の
処理を順番に分類後のカテゴリ数だけ縁返して実行し、
上位のカテゴリを選び出していた。

しかし、この方法で分類処理を行うと対象カテゴリが多
く、例えば、漢字のように数千字種のカテゴリがある場
合には、非常に長い処理時間が必要であった。

例えば、−例を挙げれば、分類に要する処理時間Ｔは次
の第（１）式によって与えられる。

Ｔ＝ｎｋｔｌ　＋１ｋｔｌ　　　＠　１１１１１１１こ
こで、ｎは特徴数、ｋは分類前のカテゴリ数、ｌは分類
後である。また、ｔｌは一つの特徴に対する演算時間、
ｔｌは距離の探索を行う時の一回分の比較時間である。

第１１１式において、ｎｋｔｌは必要最低限の処理時間
であり、これを減少させることができないが分類方法に
よってはｌｋｔ、は減少させることができるという性質
を有する。

（発明が解決しようとする問題点） 一方、第１１１式から明らかなように、分類前カテゴリ
数にと分類後の上位カテゴリ数ｌとが共に大きくなると
１１ｋｔ！が大きくなって処理時間Ｔも美大になるとい
う欠点があった。

本発明の目的は、カテゴリごとの相違度を演算する演算
部に対して分類後の上位カテゴリ数（１）に対応する４
個の演算結果を格納しておき、最大値メモリの内容のな
かで最も大きな演算結果を求め、最大値と分類結果との
両者を共にアドレシングできるようＫして、演算処理と
上位カテゴリ選別処理とを同時に実行すると共に、演算
処理中区演算徐中の結果と最大値メモリの最大値とを比
較してオーバーフロ一時には演算処理を打切ることによ
って上記欠点を除去し、多数カテゴリから上位のカテゴ
リ群を選び出す分類処理を高速で実行できるように構成
した分類処理回路を提供することにある。

（問題点を解決するための手段） 本発明による分類処理回路は、辞書メモリとミ特徴メモ
リと、演算回路、最大値メモリと、最大値検出回路と、
比較回路と、オーバーフロー検出回路と、分類結果メモ
リと、カウンタ回路とを具備し、上位カテゴリを順次高
速に選び出すように構成したものである。

辞書メモリは、各特徴に対応するカテゴリごとの正解値
を格納するだめのものである。

特徴メモリは、入力パターンから抽出された特徴値を格
納するためのものである。

演算回路は、入力パターンから抽出された特徴値と、各
特徴に対応するカテゴリごとの正解値との相違度を上位
カテゴリから順次計算するためのものである。

最大値メモリは、分類後の上位カテゴリ数に対応して特
徴メモリの内容の最大値を格納するためのものである。

最大値検出回路は、最大値メモリの内容のなかから最も
大きな値を検出するためのものである。

比較回路は、演算回路の出力と最大値検出回路の出力と
を比較して、選択すべきカテゴリを決定するためのもの
である。

オーバーフロー検出回路は、演算処理中に演算途中の結
果と最大値メモリの最大値とを比較するためのものであ
る。

分類結果メモリは、分類処理の結果を格納するためのも
のである。

カウンタ回路は辞書メモリ、特徴メモリ、ならびに最大
値メモリに対して同時にアドレシングを行うためのもの
である。

（実施例） 次に、本発明の実施例について図面を参照して詳細に説
明する。

第１図は、本発明による分類処理回路の一実施例を示す
ブロック図である。分類処理回路を示す第１図において
、１は各特徴に対応する正解値を格納するための辞書メ
モリ、２は入力パターンから抽出された特徴値を格納す
るための特徴メモリ３は特徴メモリ２の出力と辞書メモ
リ１の出力とを入力して距離計算を行うための演算回路
、４は各種メモリのアドレシングを同時に行うためのカ
ウンタ回路、５は特徴メモリ３の内容の最大値を格納す
るための最大値メモリ、６は上記最大値を検出するため
の最大値検出回路、７はカテゴリを決定するための比較
回路、８は全体の制御を行うための制御回路、９は分類
処理の結果を格納するための分類結果メモリ、１０は演
算処理中にオーバーフローを検出するためのオーバーフ
ロー検出回路である。

最初に、演算回路３の動作について説明する。

演算回路Ｓは、特徴メモリ２から信号線１０２を介して
送出された入力バター、ンによシ抽出された特徴値と、
各特徴に対応して信号線１０１へ送出されるカテゴリご
との辞書メモリーの内容との間で相違度を計算する部分
であり、Σｆ　ｉ　（ｚ　＊　ｙ　）ｉヨ１ により示される距離計算を行う。ここで、ｎは特徴数、
Ｘは特徴値、ｙは辞書出力値である。

既に説明したように、本来、分類処理では、冬ｆｉ（ｓ
、ｙ）により示される計算をすべての力１　ｗ＝　１ テゴリについて実行し、その結果のなかで計算値、すな
わち相違度が最も小さいカテゴリから順に選び出してい
る。ζこで、単に全カテゴリについて距離計算を行い、
全カテゴリ分の距離結果から上位候補を選び出すものと
仮定すると、美大な処理時間が必要となる。

そこで、本実施例においては、最大値メモリ６ならびに
最大値検出回路６によって分類処理時間を大幅に短縮す
ることができるわけである。最大値メモリ６には分類処
理の前にすべての大きな値を初期値として書込んでおき
、各カテゴリごとに実行する距離計算ごとに最大値メモ
リ５から最大値を検出し、この最大値と単位カテゴリの
距離結果との大きさについて比較回路７によって比較す
る。距離値の方が最大値検出値よりも大きい場合には、
次のカテゴリの距離の演算処理を実行し、逆に距離値が
最大値検出値よりも小さい場合には、その距離値を最大
値メモリ５のなかの最大値と入換える。このとき、同時
に最大値メモリ５のなかの最大値の距離値に対応するカ
テゴリ番号（分類結果メモリ９の内容）と現在のカテゴ
リ番号とを入換える。

上記の処理を単位カテゴリごとに行って順番に最大値メ
モリ６の内容を更新してゆくと、最終カテゴリの距離計
算を行った後には最大値メモリ６には最終的に上位のカ
テゴリの距離計算値、すなわち相違度、Σｆ　ｔ　（ｓ
　ｖ　ｙ　）が残シ、分類結果メモｍｌ す９には上位候補カテゴリのカテゴリ番号が残ることに
なる。すなわち、多数のカテゴリのなかから相違度の少
ない上位のカテゴリ群が選び出され、分類処理が完了し
たことくなる。

次に、第１図におけるカウンタ回路４の役割と高速分類
処理との関係を説明する。

本発明では、辞書メモリ１ならびに特徴メモリ２のアド
レシングと、最大値メモリ５のアドレシングとに対して
カウンタ回路４を使用し、距離演算を行うと同時に最大
値メモリ６の内容を探索し、最大値の検出処理を行って
いる。このため、カテゴリの順位の並べかえ処理に要す
る時間は零となる。すなわち、分類処理に要する処理時
間は、距離計算の処理時間にカテゴリ数をがけた積の時
間とほぼ等しくなるため、高速の分類処理を実行するこ
とが可能になる。

オーバーフロー検出回路１０では、単位カテゴメモリ６
のなかの最大値とを常に比較し、演算処理の途中で距離
値Σｉｃｓ、ｙ）が最大値メモリｌ禦１ ５の最大値よ〕も大きくなった時にはオーバーフロー信
号を送出し、制御回路８に伝えている。オーバーフロー
を検出した場合に制御回路８では該当カテゴリでの演算
処理を打切り、次のカテゴリの演算処理を実行させる。

すなわち、単位カテゴリの演算処理時間内でオーバー７
ａ−が検出され九場合には、分類処理時間が減少させる
ことになって分類処理が高速化されることになる。

高速処理は、次のようにして詳細に説明できる。

すなわち、既に説明したように距離値の探索を距離計算
の実行中に同時に行うこと罠より、第１１；式における
ｌｋｔ、を無視できるように構成することができる。す
なわち、単位カテゴリ分の演算時間ｎｔ１の期間にｌｔ
２を割当ててしまうわけである。ｎ＞Ｊであシ、且つ、
１．　＝１．に設定することができるため、本発明では
実質的なｌｋｔ！は無視できる。したがって、分類処理
時間Ｔは’Ｉ’＝ｎｋＪ　　　　　＊＊・（２１となっ
て大幅に短縮される。

さらに１オ一バーフロー検出回路１０の動作により第（
２１式によって定義される分類処理時間Ｔはｎｋｔｌ　
よりも減ぜられる。すなわち、各カテゴリの演算処理の
途中で演算途中経過の距離値と最大値メモリ５のなかの
最大値とを常に比較し、オーバーフローを検出した時点
で演算処理を打切ると、単位カテゴリ分の処理時間ｎｔ
１はｎｔｌ（ｎｔ！、となる。ここで、ｔｌ／ｌｌの比
率は条件によって変化するが、一般にカテゴリ数ｋが大
きいとほぼ５０％となり、かなりの効果が見込まれる。

ｔ１／ｌ＋　＝０．５とすると、分類処理時間ＴはＴ＝
０．５ｎｋｔ１　となる。

（発明の効果） 本発明は以上説明したように、最大値メモリと最大値検
出回路とを利用して演算処理と上位カテゴリの選別処理
とを同時に実行することＫよシ、高速で分類処理を実行
することができるという効果がある。

【図面の簡単な説明】 第１図は、本発明による分類処理回路の一実施例を示す
ブロック図である。 １・・・辞書メモリ ２・０・特徴メモリ ３・・自演算回路 ４・・瞼カウンタ回路 ５・・・最大値メモリ ６・・・最大値検出回路 ７・・・比較回路 ８・・自制御回路 ９・・・分類結果メモリ １０・・・オーバーフロー検出回路 １０１〜１０１・・・信号線

Claims (1)

【特許請求の範囲】
1. 各特徴に対応するカテゴリごとの正解値を格納するため
   の辞書メモリと、入力パターンから抽出された特徴値を
   格納するための特徴メモリと、前記入力パターンから抽
   出された特徴値と前記各特徴に対応するカテゴリごとの
   正解値との相違度を上位カテゴリから順次計算するため
   の演算回路と、分類後の上位カテゴリ数に対応して前記
   特徴メモリの内容の最大値を格納するための最大値メモ
   リと、前記最大値メモリの内容のなかから最も大きな値
   を検出するための最大値検出回路と、前記演算回路の出
   力と前記最大値検出回路の出力とを比較して選択すべき
   カテゴリを決定するための比較回路と、演算処理中に演
   算途中の結果と前記最大値メモリの最大値とを比較する
   ためのオーバーフロー検出回路と、分類処理の結果を格
   納するための分類結果メモリと、前記辞書メモリ、前記
   特徴メモリ、ならびに前記最大値メモリに対して同時に
   アドレシングを行うためのカウンタ回路とを具備し、上
   位カテゴリを順次高速に選び出すように構成したことを
   特徴とする分類処理回路。