JPH0313629B2 - - Google Patents
Info
- Publication number
- JPH0313629B2 JPH0313629B2 JP56022563A JP2256381A JPH0313629B2 JP H0313629 B2 JPH0313629 B2 JP H0313629B2 JP 56022563 A JP56022563 A JP 56022563A JP 2256381 A JP2256381 A JP 2256381A JP H0313629 B2 JPH0313629 B2 JP H0313629B2
- Authority
- JP
- Japan
- Prior art keywords
- similarity
- signal
- degree
- output
- difference
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/30003—Arrangements for executing specific machine instructions
- G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
- G06F9/30021—Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06V10/00—Arrangements for image or video recognition or understanding
- G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
- G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
- G06V10/75—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06V10/00—Arrangements for image or video recognition or understanding
- G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
- G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
- G06V10/75—Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
- G06V10/751—Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Computer Vision & Pattern Recognition (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Computing Systems (AREA)
- Medical Informatics (AREA)
- General Health & Medical Sciences (AREA)
- Evolutionary Computation (AREA)
- Databases & Information Systems (AREA)
- Artificial Intelligence (AREA)
- Multimedia (AREA)
- Health & Medical Sciences (AREA)
- Computer Hardware Design (AREA)
- Character Discrimination (AREA)
- Complex Calculations (AREA)
Description
【発明の詳細な説明】
本発明は文字認識装置に関し、さらに詳しく
は、入力パターンと各標準パターンの間で求めた
類似度又は相違度を比較し、入力パターンの識別
を行う類似度比較回路に関するものである。
は、入力パターンと各標準パターンの間で求めた
類似度又は相違度を比較し、入力パターンの識別
を行う類似度比較回路に関するものである。
文字認識装置の内部で入力文字を認識する方法
の１つとして次の方法が良く知られている。それ
は、まず最初に入力パターンと内部に記憶されて
いる各標準パターンの間で類似度を求め、次にそ
れらの類似度の中から最も大きいものを捜し出
し、最後にその類似度が一定値以上であり、かつ
他の類似度との間に一定値以上の差があるか否か
を調べて、これらの条件が満足されたときに、そ
の最大の類似度を与えた標準パターンと入力パタ
ーンとが一致したとみなして、その標準パターン
に対応したカテゴリーを出力する方法である。印
字文字認識装置で良く用いられるパターン・マツ
チング法の場合は、このようにして文字認識を行
うのが最も一般的である。
の１つとして次の方法が良く知られている。それ
は、まず最初に入力パターンと内部に記憶されて
いる各標準パターンの間で類似度を求め、次にそ
れらの類似度の中から最も大きいものを捜し出
し、最後にその類似度が一定値以上であり、かつ
他の類似度との間に一定値以上の差があるか否か
を調べて、これらの条件が満足されたときに、そ
の最大の類似度を与えた標準パターンと入力パタ
ーンとが一致したとみなして、その標準パターン
に対応したカテゴリーを出力する方法である。印
字文字認識装置で良く用いられるパターン・マツ
チング法の場合は、このようにして文字認識を行
うのが最も一般的である。
第１図はこのようにして文字認識を行う場合に
用いられていた従来の回路の一例を示すものであ
る。レジスタ１，２に書き込まれた２つの類似度
は、比較器３で比較され、２つの類似度の大小関
係が出力される。このようにして、類似度を２つ
ずつ比較してゆく事により、最大の類似度と次に
大きな類似度を求め、最後に最大の類似度が一定
値以上であり、かつ次に大きな類似度との差が一
定値以上であるか否かを調べて、これらの条件が
満足されたときに認識出力を出すのである。この
ような比較は、第１図に示したようなハードウエ
アを作つて行うのではなく、文字認識装置内に組
み込まれた計算機を用いて行う場合も多い。しか
し、このように類似度を２つずつ比較していくや
り方では、標準パターンの数と、類似度の比較に
要する時間がほぼ比例するので、数字だけでな
く、カタカナや漢字まで認識する装置になつてく
ると、この比較に要する時間が大変長くなり、文
字認識装置の認識速度に大きな影響を与え、その
高速化を阻む事になる。
用いられていた従来の回路の一例を示すものであ
る。レジスタ１，２に書き込まれた２つの類似度
は、比較器３で比較され、２つの類似度の大小関
係が出力される。このようにして、類似度を２つ
ずつ比較してゆく事により、最大の類似度と次に
大きな類似度を求め、最後に最大の類似度が一定
値以上であり、かつ次に大きな類似度との差が一
定値以上であるか否かを調べて、これらの条件が
満足されたときに認識出力を出すのである。この
ような比較は、第１図に示したようなハードウエ
アを作つて行うのではなく、文字認識装置内に組
み込まれた計算機を用いて行う場合も多い。しか
し、このように類似度を２つずつ比較していくや
り方では、標準パターンの数と、類似度の比較に
要する時間がほぼ比例するので、数字だけでな
く、カタカナや漢字まで認識する装置になつてく
ると、この比較に要する時間が大変長くなり、文
字認識装置の認識速度に大きな影響を与え、その
高速化を阻む事になる。
本発明の目的は、従来の類似度比較法のこのよ
うな欠点を除去し、文字認識装置の認識対象文字
数が多くなつても類似度の比較が高速で行え、装
置の高速化を可能ならしめる回路を提供する事に
ある。
うな欠点を除去し、文字認識装置の認識対象文字
数が多くなつても類似度の比較が高速で行え、装
置の高速化を可能ならしめる回路を提供する事に
ある。
本発明によれば、標準パターンの数と同数個あ
り、各標準パターンと入力パターンとの類似度又
は相違度を記憶し、この記憶内容があらかじめ定
められた値に達成しているか否かを検出しあらか
じめ定められた値に達成すると判定信号を出力す
る類似度判定手段と、前記判定信号により、前記
類似度判定手段の出力信号を変更する手段と、前
記類似度判定手段の出力線上の信号全部のOR演
算を行うか、又はこれと同等の処理を行つてOR
演算結果を出力する手段と、前記類似度判定手段
の出力線上の信号全部より２つずつ取り出す、す
べての組合せについて、AND演算を行つた後、
そのAND演算結果全部のOR演算を行うか、また
はこれと同等の処理を行つてAND−OR演算結果
を出力する手段と、前記類似度判定手段の記憶内
容に同時に一定値を加算又は演算する手段と、前
記OR演算結果が“１”であり、かつ前記AND−
OR演算結果が“０”である期間を計数する手段
と、前記計数期間に出力信号を出している、前記
類似度判定手段の位置を記憶する手段とを具備す
る事を特徴とする類似度比較回路が得られる。
り、各標準パターンと入力パターンとの類似度又
は相違度を記憶し、この記憶内容があらかじめ定
められた値に達成しているか否かを検出しあらか
じめ定められた値に達成すると判定信号を出力す
る類似度判定手段と、前記判定信号により、前記
類似度判定手段の出力信号を変更する手段と、前
記類似度判定手段の出力線上の信号全部のOR演
算を行うか、又はこれと同等の処理を行つてOR
演算結果を出力する手段と、前記類似度判定手段
の出力線上の信号全部より２つずつ取り出す、す
べての組合せについて、AND演算を行つた後、
そのAND演算結果全部のOR演算を行うか、また
はこれと同等の処理を行つてAND−OR演算結果
を出力する手段と、前記類似度判定手段の記憶内
容に同時に一定値を加算又は演算する手段と、前
記OR演算結果が“１”であり、かつ前記AND−
OR演算結果が“０”である期間を計数する手段
と、前記計数期間に出力信号を出している、前記
類似度判定手段の位置を記憶する手段とを具備す
る事を特徴とする類似度比較回路が得られる。
以下本発明について、実施例を示す図面を参照
して説明する。
して説明する。
第２図〜第５図は本発明の一実施例を示す回路
図である。
図である。
第２図において１０〜１９は類似度判定回路で
あり、比較すべき10個の標準パターンと入力パタ
ーンの類似度又は相違度を記憶する記憶手段（カ
ウンタ手段）と、記憶された内容があらかじめ定
められた値であるか否かを調べあらかじめ定めら
れた値に達成すると判定信号を出力する手段によ
り構成されている。尚ここで、類似度と相違度と
は、同じ内容をそれぞれ逆の立場から調べた時の
値であり、類似度が大きいという事と、相違度が
小さいという事とは同じ意味である。文字認識方
式としてパターン・マツチング法を用いた場合、
２枚の図形を重ね合せた後、一致点の数を数えれ
ば類似度が求められ、不一致点の数を数えれば相
違度が求められる。同一出願人による特開昭53−
133335号の特許出願では、パターン・マツチング
法を用いて、入力パターンと複数の標準パターン
との相違度を、同時に求める事ができる１つの方
法を提案しているが、このように、一般に文字認
識装置の内部では、類似度よりも相違度の方が多
く用いられるので、以下の説明では、類似度の代
りに相違度を用いる事にする。類似度判定回路１
０〜１９内の記憶手段（カウンタ手段）には、上
記同一出願人による特開昭53−133335号の特許出
願で提案した方法を用いれば、入力パターンと各
標準パターンとの相違度を同時に並列に求め、か
つ記憶する事ができるが、１つずつ順番に求めな
がら、それらの値を順次前述の記憶手段（カウン
タ手段）に書き込んでゆく方法を用いてもよい。
次に特開昭53−133335号の特許出願で提案した方
法の出力内容について、第８図を用いて簡単に説
明する。図においてメモリ６０には入力文字の量
子化図形が記憶される。メモリ６０で斜線を施し
たメツシユは黒であることを示す。メモリ６１，
６２，６３にはそれぞれ数字の“０”，“１”，
“２”の標準パターンが記憶されるが、この標準
パターンは認識すべきカテゴリーの数だけ用意さ
れる。数字だけを識別する場合は10個となる。メ
モリ６１〜６３で黒丸（●）で示したメツシユは
黒であるべきメツシユ、三角（△）で示したメツ
シユは白であるべきメツシユを示す。相違度計数
回路６４，６５，６６はメモリ６０とメモリ６
１，６２，６３の内容を比較することによりそれ
ぞれ入力図形と“０”，“１”，“２”の標準パター
ンとの相違度を計算する。図の場合“０”の標準
パターンとの相違度はメモリ６１で＊を記入した
メツシユの数で９、“１”の標準パターンとの相
違度は０、“２”の標準パターンとの相違度はメ
モリ６３で＊を記入したメツシユの数で３であ
る。これらの相違度は、それぞれカウンタ６７，
６８，６９に記憶されるが、これらのカウンタは
第２図における類似度判定回路１０，１１，１２
内の記憶手段（カウンタ手段）に相当する。従つ
て類似度判定回路１０〜１９の記憶手段には例え
ば入力パターンと０から９までの標準パターンと
の相違度が記憶されていると考えてもよい。
あり、比較すべき10個の標準パターンと入力パタ
ーンの類似度又は相違度を記憶する記憶手段（カ
ウンタ手段）と、記憶された内容があらかじめ定
められた値であるか否かを調べあらかじめ定めら
れた値に達成すると判定信号を出力する手段によ
り構成されている。尚ここで、類似度と相違度と
は、同じ内容をそれぞれ逆の立場から調べた時の
値であり、類似度が大きいという事と、相違度が
小さいという事とは同じ意味である。文字認識方
式としてパターン・マツチング法を用いた場合、
２枚の図形を重ね合せた後、一致点の数を数えれ
ば類似度が求められ、不一致点の数を数えれば相
違度が求められる。同一出願人による特開昭53−
133335号の特許出願では、パターン・マツチング
法を用いて、入力パターンと複数の標準パターン
との相違度を、同時に求める事ができる１つの方
法を提案しているが、このように、一般に文字認
識装置の内部では、類似度よりも相違度の方が多
く用いられるので、以下の説明では、類似度の代
りに相違度を用いる事にする。類似度判定回路１
０〜１９内の記憶手段（カウンタ手段）には、上
記同一出願人による特開昭53−133335号の特許出
願で提案した方法を用いれば、入力パターンと各
標準パターンとの相違度を同時に並列に求め、か
つ記憶する事ができるが、１つずつ順番に求めな
がら、それらの値を順次前述の記憶手段（カウン
タ手段）に書き込んでゆく方法を用いてもよい。
次に特開昭53−133335号の特許出願で提案した方
法の出力内容について、第８図を用いて簡単に説
明する。図においてメモリ６０には入力文字の量
子化図形が記憶される。メモリ６０で斜線を施し
たメツシユは黒であることを示す。メモリ６１，
６２，６３にはそれぞれ数字の“０”，“１”，
“２”の標準パターンが記憶されるが、この標準
パターンは認識すべきカテゴリーの数だけ用意さ
れる。数字だけを識別する場合は10個となる。メ
モリ６１〜６３で黒丸（●）で示したメツシユは
黒であるべきメツシユ、三角（△）で示したメツ
シユは白であるべきメツシユを示す。相違度計数
回路６４，６５，６６はメモリ６０とメモリ６
１，６２，６３の内容を比較することによりそれ
ぞれ入力図形と“０”，“１”，“２”の標準パター
ンとの相違度を計算する。図の場合“０”の標準
パターンとの相違度はメモリ６１で＊を記入した
メツシユの数で９、“１”の標準パターンとの相
違度は０、“２”の標準パターンとの相違度はメ
モリ６３で＊を記入したメツシユの数で３であ
る。これらの相違度は、それぞれカウンタ６７，
６８，６９に記憶されるが、これらのカウンタは
第２図における類似度判定回路１０，１１，１２
内の記憶手段（カウンタ手段）に相当する。従つ
て類似度判定回路１０〜１９の記憶手段には例え
ば入力パターンと０から９までの標準パターンと
の相違度が記憶されていると考えてもよい。
第２図の出力信号である信号線３１上の
“OR”と信号線３２上の“AND−OR”第３図〜
第５図で示す、認識に必要な情報を作成する回路
の入力信号となるもので、その値は信号線３３上
のクロツクパルスCLKによつて変化する。つま
りこれらの信号は、類似度判定回路１０〜１９の
記憶手段（カウンタ手段）の中に既定値に達しな
いものがいくつあるかを、カウンタ手段に“１”
が加えられる毎にANDゲートやORゲートを用い
て出力するものである。類似度判定回路１０〜１
９内の記憶手段の種類や大きさは特に限定される
ものではないが、ここでは４ビツトの２進カウン
タであるとする。類似度判定回路１０〜１９内の
記憶手段の内容は、あらかじめ定められた値に達
しているか否かを検出する手段によつて常時調べ
られ、その結果がインバータI1〜I9を通して信号
線２０〜２９へ類似度判定回路の出力判定信号Ａ
０〜Ａ９として出力される。ここでは判定信号と
して、２進カウンタの記憶手段の内容が15のとき
に発生するCARRY信号をインバータI1〜I9で反
転したものを用いているので、記憶手段の内容が
15になるとその類似度判定回路に対応した類似度
判定回路の出力信号が“１”から“０”に変更さ
れるが、この類似度判定回路の出力信号を“１”
から“０”に変更する閾値としては任意の数値を
用いることができるのは言うまでもない。類似度
判定回路１０〜１９内の記憶手段のクロツク入力
端子１０ａ〜１９ａには信号線３３が接続されて
おり、この上に発生するクロツクパルスCLKに
同期して、２進カウンタの各記憶手段に同時に
“１”が加算される。ただし２進カウンタの記憶
手段がCARRY信号を出しているときは、記憶手
段の禁止信号入力端子１０ｂ〜１９ｂへCARRY
信号がフイード・バツクされているので加算は行
われない。このクロツクパルスCLKが少なくと
も15回発生すれば全類似度判定回路の記憶手段の
内容は15となり、あらかじめ定められた値“15”
に達したか否かを検出する手段によつて出力信号
Ａ０〜１９はすべて“１”から“０”に変更され
た状態すなわち全て消去された状態となる。
“OR”と信号線３２上の“AND−OR”第３図〜
第５図で示す、認識に必要な情報を作成する回路
の入力信号となるもので、その値は信号線３３上
のクロツクパルスCLKによつて変化する。つま
りこれらの信号は、類似度判定回路１０〜１９の
記憶手段（カウンタ手段）の中に既定値に達しな
いものがいくつあるかを、カウンタ手段に“１”
が加えられる毎にANDゲートやORゲートを用い
て出力するものである。類似度判定回路１０〜１
９内の記憶手段の種類や大きさは特に限定される
ものではないが、ここでは４ビツトの２進カウン
タであるとする。類似度判定回路１０〜１９内の
記憶手段の内容は、あらかじめ定められた値に達
しているか否かを検出する手段によつて常時調べ
られ、その結果がインバータI1〜I9を通して信号
線２０〜２９へ類似度判定回路の出力判定信号Ａ
０〜Ａ９として出力される。ここでは判定信号と
して、２進カウンタの記憶手段の内容が15のとき
に発生するCARRY信号をインバータI1〜I9で反
転したものを用いているので、記憶手段の内容が
15になるとその類似度判定回路に対応した類似度
判定回路の出力信号が“１”から“０”に変更さ
れるが、この類似度判定回路の出力信号を“１”
から“０”に変更する閾値としては任意の数値を
用いることができるのは言うまでもない。類似度
判定回路１０〜１９内の記憶手段のクロツク入力
端子１０ａ〜１９ａには信号線３３が接続されて
おり、この上に発生するクロツクパルスCLKに
同期して、２進カウンタの各記憶手段に同時に
“１”が加算される。ただし２進カウンタの記憶
手段がCARRY信号を出しているときは、記憶手
段の禁止信号入力端子１０ｂ〜１９ｂへCARRY
信号がフイード・バツクされているので加算は行
われない。このクロツクパルスCLKが少なくと
も15回発生すれば全類似度判定回路の記憶手段の
内容は15となり、あらかじめ定められた値“15”
に達したか否かを検出する手段によつて出力信号
Ａ０〜１９はすべて“１”から“０”に変更され
た状態すなわち全て消去された状態となる。
信号線３１に出力される信号“OR”は、OR
ゲートOR１〜OR９を用いてカウンタ出力信号
Ａ０〜Ａ９全てのORを演算した、OR演算結果
である。信号線３２に出力される信号“AND−
OR”は、カウンタ出力信号Ａ０〜Ａ９全てより
２つずつ取り出す全ての組み合せについてAND
演算を行つた後、そのAND演算結果全てのOR演
算を行つた場合に得られる、AND−OR演算結果
と同じ信号を、最少のANDゲートAND１〜
AND９とORゲートOR１０，OR１１で求めた
ものである。カウンタ出力信号Ａ０〜Ａ９の中に
“１”が２つ以上あればOR演算結果とAND−OR
演算結果の両方が“１”となり、“１”が１つの
時はOR演算結果のみが“１”となり“１”がな
くなると両方共“０”となる。
ゲートOR１〜OR９を用いてカウンタ出力信号
Ａ０〜Ａ９全てのORを演算した、OR演算結果
である。信号線３２に出力される信号“AND−
OR”は、カウンタ出力信号Ａ０〜Ａ９全てより
２つずつ取り出す全ての組み合せについてAND
演算を行つた後、そのAND演算結果全てのOR演
算を行つた場合に得られる、AND−OR演算結果
と同じ信号を、最少のANDゲートAND１〜
AND９とORゲートOR１０，OR１１で求めた
ものである。カウンタ出力信号Ａ０〜Ａ９の中に
“１”が２つ以上あればOR演算結果とAND−OR
演算結果の両方が“１”となり、“１”が１つの
時はOR演算結果のみが“１”となり“１”がな
くなると両方共“０”となる。
第３図において、レジスタ３４，３５は信号
ORが“１”の間クロツク・パルスCLKに同期し
て信号Ａ０〜Ａ９を記憶するので、最終的には信
号ORが“０”になる直前の信号Ａ０〜Ａ９を記
憶する事になる。従つて、最小の相違度を記憶し
ていたカウンタの位置は、これらのレジスタの内
容を調べ、“１”である所を捜せば判明する。
ORが“１”の間クロツク・パルスCLKに同期し
て信号Ａ０〜Ａ９を記憶するので、最終的には信
号ORが“０”になる直前の信号Ａ０〜Ａ９を記
憶する事になる。従つて、最小の相違度を記憶し
ていたカウンタの位置は、これらのレジスタの内
容を調べ、“１”である所を捜せば判明する。
第４図において、カウンタ３６は最初“０”に
クリアーされ、その後信号AND−ORが“０”
で、信号ORが“１”の間クロツク・パルスCLK
に同期して“１”が加えられるので、最終的には
最小の相違度と次に小さな相違度との差を記憶す
る事になる。なお、この値が“０”のときは、最
小の相違度をとるカウンターが２つ以上あつたと
いう事であり、それらの位置はレジスタ３４，３
５の内容を調べ、“１”である所を捜せば知る事
ができる。ここで、信号AND−ORはインバータ
I10を通してANDゲートAND１０の一方の入力
端に入力し、信号ORはANDゲートAND１０の
他方の入力端に入力するもので、ANDゲート
AND１０はカウンタ３６に接続している。
クリアーされ、その後信号AND−ORが“０”
で、信号ORが“１”の間クロツク・パルスCLK
に同期して“１”が加えられるので、最終的には
最小の相違度と次に小さな相違度との差を記憶す
る事になる。なお、この値が“０”のときは、最
小の相違度をとるカウンターが２つ以上あつたと
いう事であり、それらの位置はレジスタ３４，３
５の内容を調べ、“１”である所を捜せば知る事
ができる。ここで、信号AND−ORはインバータ
I10を通してANDゲートAND１０の一方の入力
端に入力し、信号ORはANDゲートAND１０の
他方の入力端に入力するもので、ANDゲート
AND１０はカウンタ３６に接続している。
第５図において、カウンタ３７は最初１５がプ
リセツトされ、その後信号ORが“１”の間クロ
ツク・パルスCLKに同期して“１”が引かれて
いくので、最終的には、カウンタ１０〜１９の中
の最小の値、つまり最小の相違度を記憶する事に
なる。
リセツトされ、その後信号ORが“１”の間クロ
ツク・パルスCLKに同期して“１”が引かれて
いくので、最終的には、カウンタ１０〜１９の中
の最小の値、つまり最小の相違度を記憶する事に
なる。
以上で求めた情報を用いると、文字認識結果は
次のようにして出す事ができる。つまり、最小の
相違度があらかじめ定められた値以下であるとい
う条件が満足されているか否かは、カウンタ３７
の内容を調べれば判り、最小の相違度と次に小さ
な相違度の差があらかじめ定められた値以上であ
るという条件が満足されているか否かは、カウン
タ３６の内容を調べれば判るので、これらの条件
が満足されているときは、レジスタ３４，３５の
内容を調べ最小の相違度を与えたカウンターの位
置を知り、そのカウンターに対応した標準パター
ンを調べ、そのカテゴリーを認識結果として出力
すべく、上記の条件が満足されていなかつたとき
は読取不能の出力を出せばよい。
次のようにして出す事ができる。つまり、最小の
相違度があらかじめ定められた値以下であるとい
う条件が満足されているか否かは、カウンタ３７
の内容を調べれば判り、最小の相違度と次に小さ
な相違度の差があらかじめ定められた値以上であ
るという条件が満足されているか否かは、カウン
タ３６の内容を調べれば判るので、これらの条件
が満足されているときは、レジスタ３４，３５の
内容を調べ最小の相違度を与えたカウンターの位
置を知り、そのカウンターに対応した標準パター
ンを調べ、そのカテゴリーを認識結果として出力
すべく、上記の条件が満足されていなかつたとき
は読取不能の出力を出せばよい。
以上の説明から明らかなように、第２図〜第５
図で示した回路を用いると、類似度判定回路１０
〜１９に相違度を書き込んだ後、クロツク・パル
スCLKを15回発生させれば文字認識に必要な相
違度の比較情報がすべてカウンタとレジスタに求
められるので、相違度の比較をきわめて高速に行
う事ができる。又、この比較に要する時間は、標
準パターン数、つまり相違度を記憶するカウンタ
ー数には殆ど影響されない。
図で示した回路を用いると、類似度判定回路１０
〜１９に相違度を書き込んだ後、クロツク・パル
スCLKを15回発生させれば文字認識に必要な相
違度の比較情報がすべてカウンタとレジスタに求
められるので、相違度の比較をきわめて高速に行
う事ができる。又、この比較に要する時間は、標
準パターン数、つまり相違度を記憶するカウンタ
ー数には殆ど影響されない。
なお、類似度判定回路１０〜１９に記憶さる相
違度に上限値があり、その上限値が文字認識結果
を出すときの条件の１つ、つまり最小の相違度が
あらかじめ定められた値以下であるという条件で
用いられている、定められた値よりも小さいか又
は等しい時は、第５図に示した回路は不要であ
る。
違度に上限値があり、その上限値が文字認識結果
を出すときの条件の１つ、つまり最小の相違度が
あらかじめ定められた値以下であるという条件で
用いられている、定められた値よりも小さいか又
は等しい時は、第５図に示した回路は不要であ
る。
以上の説明では、類似度判定回路１０〜１９に
相違度を記憶する場合について述べたが、類似度
を記憶する場合も同様にして類似度の比較結果を
求める事ができる。つまり、類似度判定回路１０
〜１９に類似度を記憶する場合は、類似度判定回
路出力信号Ａ０〜Ａ９としては類似度判定回路の
記憶手段の内容が“０”の時に発生する
BORROW信号をそのまま用い、クロツク・パル
スCLKに同期して、類似度判定回路１０〜１９
の記憶手段より“１”を同時に引いてゆく。カウ
ンタ３７は最初“０”にクリアーし、その後、信
号ORが“１”の間、クロツク・パルスCLKに同
期して“１”を加えてゆく。このようにして、ク
ロツク・パルスCLKを15回発生させると、レジ
スタ３４，３５には最大の類似度を与えた類似度
記憶カウンタの位置が記憶され、カウンタ３６に
は、最大の類似度と次に大きな類似度の差が求め
られ、カウンタ３７には、最大の類似度の値が求
められる。文字認識結果は、これらの情報を用い
て、相違度を用いた場合と同様に容易に求める事
ができる。
相違度を記憶する場合について述べたが、類似度
を記憶する場合も同様にして類似度の比較結果を
求める事ができる。つまり、類似度判定回路１０
〜１９に類似度を記憶する場合は、類似度判定回
路出力信号Ａ０〜Ａ９としては類似度判定回路の
記憶手段の内容が“０”の時に発生する
BORROW信号をそのまま用い、クロツク・パル
スCLKに同期して、類似度判定回路１０〜１９
の記憶手段より“１”を同時に引いてゆく。カウ
ンタ３７は最初“０”にクリアーし、その後、信
号ORが“１”の間、クロツク・パルスCLKに同
期して“１”を加えてゆく。このようにして、ク
ロツク・パルスCLKを15回発生させると、レジ
スタ３４，３５には最大の類似度を与えた類似度
記憶カウンタの位置が記憶され、カウンタ３６に
は、最大の類似度と次に大きな類似度の差が求め
られ、カウンタ３７には、最大の類似度の値が求
められる。文字認識結果は、これらの情報を用い
て、相違度を用いた場合と同様に容易に求める事
ができる。
第６図と第７図は本発明の他の実施例を示す回
路図である。
路図である。
第６図は、第２図における記憶手段として２進
カウンタを用いた類似度判定回路１０〜１９の代
りに相違度記憶シフトレジスタ４０〜４９を用い
た場合である。今、シフトジスタ４０〜４９がそ
れぞれ15ビツトのシフトレジスタであるとし、各
シフトレジスタに記憶する相違度の数だけ左端の
ビツトから“０”を記憶し、他のビツトを“１”
とした後、信号線５０上にクロツクパルスCLK
を15回与えて、各シフトレジスタの内容を順次右
シフトすれば、シフトレジスタ４０〜４９の右端
の出力信号Ｂ０〜Ｂ９の変化の様子は、第２図に
おけるカウンタ１０〜１９に、クロツクパルス
CLKを15回与えた時の出力信号Ａ０〜Ａ９の変
化の様子と全く同じである。従つて、信号Ｂ０〜
Ｂ９を処理する回路を、第２図〜第５図で示し
た、信号Ａ０〜Ａ９を処理する回路と同一にすれ
ば、最終の相違度比較情報としては、第２図〜第
５図で示した回路で得られる情報と同一のものが
得られる事になる。記憶すべき相違度の上限値が
小さい時は、第６図に示した回路を用いた方が、
回路の規模が小さくなるが、上限値が大きい時は
逆に、第２図で示した回路を用いた方が回路の規
模が小さくなる。
カウンタを用いた類似度判定回路１０〜１９の代
りに相違度記憶シフトレジスタ４０〜４９を用い
た場合である。今、シフトジスタ４０〜４９がそ
れぞれ15ビツトのシフトレジスタであるとし、各
シフトレジスタに記憶する相違度の数だけ左端の
ビツトから“０”を記憶し、他のビツトを“１”
とした後、信号線５０上にクロツクパルスCLK
を15回与えて、各シフトレジスタの内容を順次右
シフトすれば、シフトレジスタ４０〜４９の右端
の出力信号Ｂ０〜Ｂ９の変化の様子は、第２図に
おけるカウンタ１０〜１９に、クロツクパルス
CLKを15回与えた時の出力信号Ａ０〜Ａ９の変
化の様子と全く同じである。従つて、信号Ｂ０〜
Ｂ９を処理する回路を、第２図〜第５図で示し
た、信号Ａ０〜Ａ９を処理する回路と同一にすれ
ば、最終の相違度比較情報としては、第２図〜第
５図で示した回路で得られる情報と同一のものが
得られる事になる。記憶すべき相違度の上限値が
小さい時は、第６図に示した回路を用いた方が、
回路の規模が小さくなるが、上限値が大きい時は
逆に、第２図で示した回路を用いた方が回路の規
模が小さくなる。
第７図は第２図における信号Ａ０〜Ａ９を処理
して信号ORと信号AND−ORを求めるORゲー
ト11個とANDゲート９個の代りに、１ビツトの
加算器５１〜５５と２個のORゲートOR１２，
OR１３を用いた場合である。このような回路を
用いても、信号線５６と５７の上に得られる信号
ORと信号AND−ORは、第２図における信号線
３１と３２の上で得られる信号と全く同じであ
る。このような回路を汎用ICを用いて構成した
場合は、第７図で示した回路を用いた方がICの
個数が少し少なくなるが、専用のLSIを製造する
場合は、第２図で示した回路を用いた方が集積度
が高くなる。
して信号ORと信号AND−ORを求めるORゲー
ト11個とANDゲート９個の代りに、１ビツトの
加算器５１〜５５と２個のORゲートOR１２，
OR１３を用いた場合である。このような回路を
用いても、信号線５６と５７の上に得られる信号
ORと信号AND−ORは、第２図における信号線
３１と３２の上で得られる信号と全く同じであ
る。このような回路を汎用ICを用いて構成した
場合は、第７図で示した回路を用いた方がICの
個数が少し少なくなるが、専用のLSIを製造する
場合は、第２図で示した回路を用いた方が集積度
が高くなる。
以上で本発明による相違度又は類似度比較回路
について、詳しく説明したが、本発明のような回
路を用いると、従来の相違度又は類似度を２つず
つ比較してゆく方法に比べて相違度又は類似度の
比較に要する時間を大幅に短縮する事ができる。
又、この比較に要する時間は、従来の方法の場合
は、標準パターン数にほぼ比例していたが、本発
明による回路を用いた場合は、標準パターン数に
あまり影響されないので、カタカナや漢字まで読
むOCRのように、標準パターン数が多い文字認
識装置においては時間短縮の効果が特に顕著にな
る。又、本発明による回路は、このまま汎用の
ICで構成してもICの個数はあまり多くならない
が、同一形式の回路が多数含まれており、入力信
号と出力信号が単純である為、LSI化に適してお
り、LSI化によるICの個数の大幅な低減を図る事
も可能である。
について、詳しく説明したが、本発明のような回
路を用いると、従来の相違度又は類似度を２つず
つ比較してゆく方法に比べて相違度又は類似度の
比較に要する時間を大幅に短縮する事ができる。
又、この比較に要する時間は、従来の方法の場合
は、標準パターン数にほぼ比例していたが、本発
明による回路を用いた場合は、標準パターン数に
あまり影響されないので、カタカナや漢字まで読
むOCRのように、標準パターン数が多い文字認
識装置においては時間短縮の効果が特に顕著にな
る。又、本発明による回路は、このまま汎用の
ICで構成してもICの個数はあまり多くならない
が、同一形式の回路が多数含まれており、入力信
号と出力信号が単純である為、LSI化に適してお
り、LSI化によるICの個数の大幅な低減を図る事
も可能である。
第１図は従来の方式で類似度を比較する一例の
回路図、第２図〜第５図は本発明の一実施例を示
す回路図、第６図と第７図はそれぞれ本発明の他
の実施例に示す回路図、第８図は本発明と類似度
算出回路との接続関係を説明するための図であ
る。 図において、１０〜１９は類似度判定回路、２
０〜２９，３１〜３３は信号線、３４，３５はレ
ジスタ、３６，３７はカウンタ、４０〜４９はシ
フトレジスタ、５０は信号線、５１〜５５は１ビ
ツトの加算器、５６，５７は信号線である。
回路図、第２図〜第５図は本発明の一実施例を示
す回路図、第６図と第７図はそれぞれ本発明の他
の実施例に示す回路図、第８図は本発明と類似度
算出回路との接続関係を説明するための図であ
る。 図において、１０〜１９は類似度判定回路、２
０〜２９，３１〜３３は信号線、３４，３５はレ
ジスタ、３６，３７はカウンタ、４０〜４９はシ
フトレジスタ、５０は信号線、５１〜５５は１ビ
ツトの加算器、５６，５７は信号線である。
Claims (1)
- １ 標準パターンの数と同数個あり、各標準パタ
ーンと入力パターンとの類似度又は相違度を記憶
し、この記憶内容があらかじめ定められた値に達
しているか否かを検出しあらかじめ定められた値
に達成すると判定信号を出力する類似度判定手段
と、前記判定信号により前記類似度判定手段の出
力信号を変更する手段と、前記類似度判定手段の
出力線上の信号全部のOR演算を行うか、又はこ
れと同等の処理を行つてOR演算結果を出力する
手段と、前記類似度判定手段の出力線上の信号全
部より２つずつ取り出す、すべての組み合せにつ
いて、AND演算を行つた後、そのAND演算結果
全部のOR演算を行うか、またはこれと同等の処
理を行つてAND−OR演算結果を出力する手段
と、前記類似度判定手段の記憶内容に同時に一定
値を加算又は減算する手段と、前記OR演算結果
が“１”であり、かつ前記AND−OR演算結果が
“０”である期間を計数する手段と、前記計数期
間に出力信号を出している、前記類似度判定手段
の位置を記憶する手段とを具備する事を特徴とす
る類似度比較回路。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56022563A JPS57137977A (en) | 1981-02-18 | 1981-02-18 | Similarity degree comparing circuit of character recognizing device |
| US06/350,037 US4498189A (en) | 1981-02-18 | 1982-02-18 | Comparator suitable for a character recognition system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56022563A JPS57137977A (en) | 1981-02-18 | 1981-02-18 | Similarity degree comparing circuit of character recognizing device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS57137977A JPS57137977A (en) | 1982-08-25 |
| JPH0313629B2 true JPH0313629B2 (ja) | 1991-02-22 |
Family
ID=12086333
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP56022563A Granted JPS57137977A (en) | 1981-02-18 | 1981-02-18 | Similarity degree comparing circuit of character recognizing device |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US4498189A (ja) |
| JP (1) | JPS57137977A (ja) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4783830A (en) * | 1987-03-24 | 1988-11-08 | American Electronics, Inc. | Pattern recognizing content addressable memory system |
| JPH03238567A (ja) * | 1990-02-15 | 1991-10-24 | Eastman Kodatsuku Japan Kk | パターン認識装置 |
| JP3046111B2 (ja) * | 1991-11-08 | 2000-05-29 | キヤノン株式会社 | 文字認識方法及びその装置 |
| US6075876A (en) * | 1997-05-07 | 2000-06-13 | Draganoff; Georgi Hristoff | Sliding yardsticks fingerprint enrollment and verification system and method |
| US8004714B2 (en) * | 2007-04-17 | 2011-08-23 | Xerox Corporation | System for replacing a portion of an image data stream in an ink jet printer |
| CN106484360B (zh) * | 2015-08-28 | 2019-05-07 | 华为技术有限公司 | 相似度检测装置 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US2984824A (en) * | 1959-01-02 | 1961-05-16 | Hughes Aircraft Co | Two-way data compare-sort apparatus |
| US3273127A (en) * | 1962-09-04 | 1966-09-13 | Philip N Armstrong | Digital sorting system |
| US3329938A (en) * | 1964-02-24 | 1967-07-04 | Philip N Armstrong | Multiple-bit binary record sorting system |
| US3428946A (en) * | 1965-08-26 | 1969-02-18 | Goodyear Aerospace Corp | Means for merging data |
| GB1248681A (en) * | 1969-01-08 | 1971-10-06 | Int Computers Ltd | Improvements in or relating to digital electrical information processing apparatus |
| US3760356A (en) * | 1971-12-17 | 1973-09-18 | Honeywell Inf Systems | Technique for determining the extreme binary number from a set of binary numbers |
| US4288782A (en) * | 1979-08-24 | 1981-09-08 | Compression Labs, Inc. | High speed character matcher and method |
-
1981
- 1981-02-18 JP JP56022563A patent/JPS57137977A/ja active Granted
-
1982
- 1982-02-18 US US06/350,037 patent/US4498189A/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS57137977A (en) | 1982-08-25 |
| US4498189A (en) | 1985-02-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US3849762A (en) | Digital information processing apparatus for pattern recognition | |
| US4484346A (en) | Neighborhood transformation logic circuitry for an image analyzer system | |
| US5287193A (en) | Parallel processing architecture of run-length codes | |
| US4395698A (en) | Neighborhood transformation logic circuitry for an image analyzer system | |
| EP0127988B1 (en) | A normalizing circuit | |
| EP0886207A2 (en) | Longest coincidence data detection using associative memory units having interleaved data | |
| US3760356A (en) | Technique for determining the extreme binary number from a set of binary numbers | |
| JPH0313629B2 (ja) | ||
| US3434109A (en) | Multifield comparator adjustable to compare any combinations of fields and to provide selectable bases of comparison | |
| US3942169A (en) | Pattern recognition system | |
| US3167740A (en) | Data comparison system utilizing a universal character | |
| JP3012357B2 (ja) | シフト量検出回路 | |
| US4185271A (en) | Character reading system | |
| US5438682A (en) | Data processing system for rewriting parallel processor output data using a sequential processor | |
| JP3124318B2 (ja) | 論理回路設計装置 | |
| KR960028176A (ko) | 고속 디지탈 영상 패턴 매칭 회로 | |
| US6405231B1 (en) | Method and apparatus for rounding intermediate normalized mantissas within a floating-point processor | |
| GB2209418A (en) | Analysing transitions in finite state machines | |
| JP2504162B2 (ja) | 障害処理装置 | |
| JPS646508B2 (ja) | ||
| SU962921A1 (ru) | Устройство дл анализа и обработки знаковых разр дов | |
| JPS5816556B2 (ja) | エラ−検出方式 | |
| SU798819A1 (ru) | Устройство дл нормализации чисел | |
| JPS5844417Y2 (ja) | チエンジデイテクタ入力モジユ−ル | |
| JPS60175435A (ja) | 回路パタ−ンのパタ−ン幅検査方法 |