JPS5945500A - パタンマツチング装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は文字認識等のバタン認識システムの中心鼾成要
素であるバタンマツチング装置に関する。

文字認識等のバタン認識システムにお°いては紹紹原理
と［７てバタンマツチング法が多用されている。バタン
マツチング法とは、認識対象どなる各文字に対して標準
とたるバタン（以下標準バタンと呼ぶ）を予かじめ用意
しそおき、未知バタン（以後人力バタンと呼ぶ）が入力
されると、標準バタンとの比較操作を行なって、最も！
１′１似した標準バタンを選択することによって判定を
行なうものである。乙のバタンマツチング法はＷ、！！
がｉ）単で庚。

り比較的性能が良いので、広く利用されているが手書き
文字のようにバタン変動がとし７いイ）のを対象とする
場合にｉ、ｔ　ｉｇ　脆性能が劣化するという欠点があ
った。詔職性能劣化の対策とＬ７てに、椋々の変形文字
バタンを総て用意する方法がどられるがその場合には標
準バタンの記憶容量が大きくなる点と、比較操作の１１
１数が増加するという点が欠点となっていた。

本発明の目的Ｑよ、’ｆｌ：乎基１１イ、の有する上記
欠点を除き、バタンの変形奢・吸収でき、しかも株準バ
タン記へ′ｈｋが小さく、かつ比較操作の処理ｈＥも少
ないバタンマツチング装置を実現し、高精）ザでたつ低
価格なタ：字詔網システム（さらには、一般的なバタン
認本システム）を拐供することにある。

本発明によるバタンマツチング装置は、特徴の時系列中
に分岐開始記号、分岐区切り記号、分岐終了記号及び省
略開始記号、省略終了記号等の制御記号を含んで成る標
準バタンを記憶する標準バタン記憶部と、特徴の時系列
として記述される入力バタンを保持する入力バタンバッ
ファと、」二記標準バタン中の各要素を制御記号と特徴
とに分類するデコーダと複数の記憶番地を層として多層
構成すｆ］るスタックメモリーと、」；記入カバタンの
特徴と標準バタンの特徴間の距離を算出する距離計算部
と、上記スタックメモリより読み出される複数個の数値
を比較し、それらの最小値に前記中離計算部よりの出力
を加算し、前記スタックメモリに書き込むという動的計
画演算を行なうマツチング処理部と、前記デコーダーよ
りの制御信号に応じて前記スタックメモリーをプツシ−
、ポツプ各層間の最小値選択、各層間のデーター転送を
行なうスタック演算部とより構成される。

以下に図面を引用しつつ実施例に基づいて本発明の原理
を詳述する。なお、以下の実施例は本発明をオンライン
文字認識装置に適用した場合のものである。オンライン
文字認識とは「情報処理ｖｏｌ−１１Ａ　１０　（１９
７０年１０月）に１遠隔端末からの実時間文字認識″と
頌して発表された論文」に記載されている如く、タブレ
ット上に記される文字の筆線の動きの情報を検定するこ
とにより認識を行なう文字認識装置である。

第１図は文字バタン糸“の筆跡を示したものである。筆
線上の矢印は筆点の移動方向を示し、破線は画から画に
移る（ペンがタブレットから離れている）筆点移動を示
す仮想の筆線である。

上記文献に示される如く、このような文字バタンの筆跡
は等間隔に標本化され、各時刻における筆線方向が特徴
として抽出される。この筆線方向は第２図に示されるよ
うに０から１５までの数値として表わされる。結局、文
字バタンは第３図に示すような方向を示すコードたる特
徴の時系列として表現される。いま、このパターンを一
般的にＡ−ａ　１　＋　　ａ　２　・・・・・・・・・
ａｉ・・・・・曲ａＩ　　　　　（１）と示す。

バタンマツチング法に基づく文字認識では、各文字に標
準バタンか用意される。いま、文字に番号ｎを対応させ
てこの番号で文字を指定することにする。文字ｎの標準
バタンを と特徴ｂｊの時系列として示す。

認識は上記人力バタンＡと各標準バタンＢとの比較、す
なわち、バタンマツチングを行ない距離Ｄ（Ａ、Ｂ）　
　　　　　　　　　　　　　（３）を算出し、その最小
となる番号ｎを定めることによって行なわれる。

ここで問題なのは、ＡとＢ′の比較をいかに行なうかと
いう事である。すなわち、バタンマツチング処理の結果
得られる距＃ｌ！Ｄ（Ａ、１３）が文字の変形に対して
安定でないと、高精度な手内文字１１，３識は不可能で
ある。文字の変形としては、字形が歪む程度の軽度のも
のと、例えば第４図（ａ）、　（ｂ）に示すように一部
が本質的に異なるものとがある。前者に関しては例えば
「昭和４９年度電子通信学会論文集１５５２（第１４０
３頁に１非線形マツチングによる手１−５文字詔識′と
題して発表された論文」に記載されているＤＰマツチン
グ法によって対処することが可能である。すなわち、文
字の歪は文字バタンＡとＢの間の伸縮となって表われる
ので、特願昭４５−５３８９６号明細書（特公昭５０−
２３９４１号公報）に記載された動的計画法ｃ以下ＤＰ
と呼、ｇ）に基づいたＤＰマツチ、レグ法で除去するこ
とができる。

本発明で対象とするのは、主として後者、すなわち本質
的な字体変形である。今ここで・糸・という字を例にと
って字体の変形を考えて見ると第５図に示すような各種
変形が考えられる。

第５図（ａ）は標準の占法による字形であって６画で書
力＼れだものである。図で破線で示した線分は画と画の
間を結ぶ架空の筆線である。この架空の筆線も以ドでは
単に画あるいは筆線と呼ぶことにする。また、参照数字
は各画の筆順番号に対応している。

第５図（ｂ）は第１筆線と第３筆線が連続したもので、
これに従って第２筆線が消滅している。

同図（Ｃ）は、第３筆線と第５筆線も接続したものでさ
らに第９から第１１筆線までが、参照数字１３−Ｊｂ−
、ら１６で示すように変形してぼる。

この様な各局所での変形は相互に独立な事象であるので
、これらの組合せとして多数の変形バタンか存在するこ
とになる。これらの変形バタンを総て標準バタンとして
用意するのは、標準バタンの記慟容量の点でも、バタン
マツチングの計算量の点でも不利である。

本発明では、標準バタンの中に分岐開始記号・（″９分
岐終了記号１）ｐ１分岐区切り記号゛／″、省略開始記
号゛〔ｒ、及び省略終了記号゛〕″なる制御記号を導入
する。例えば、・・・・・・・・・・・・（ｘ、／ｙ／
ｚ）・・・・・・・・・・・・なる記述ばｘ、ｙ、ｚの
中のいずれか一方のみが選択されることを意味する。ま
だ、 ・・・・・・・・・・・・〔ｘ〕・・・・・・・・・・
・・なる記述はＸが省略されても良いことを念味する。

これらの制御コードは多重に使用されても良い。

例えば、 ・・・・・・・・・・・・（ｘ（ｙ、ｚ）、ｗ）のよす
な用法が許されるものとする。このような制御コードを
（２）式の標準バタンに導入する。

第５図の３種の変形を許容する標準バタンは次のように
書かれる。

１３−１０．１４．　（２〕、　１１．　Ｏ，（２）、
　１３゜（７，１２，６，１０，１／９．１３．３．１
３．３）、　１３　　　　（４）この式中の数字は第２
図で定義した方向を示す特徴である。実際の文字バタン
では同一方向の筆線が続く場合が有って、結果として同
一の特徴が２回以上継続することが有るが、（４）式の
標準バタンでは同一方向の特徴は１回だけに限定してい
る。

このように圧縮された標準バタンであっても、ＤＰマツ
チングを用いると実際の文字バタンと良好な一致を得る
ことができる。

ここで、制御信号を含まなｐ（２）式の標準バタンと（
１）式の入力バタンとの間のＤＰマツチングを従来技術
として説明しておく。今、入力バタンの特徴ａ・と標準
バタンの特徴ｂ￥との間の距離をｄ（ｊ、ｊ）で示す。

ｄ（Ｌ　ｊ）−ｍｒｎ（Ｉａｉ−ｂｒｉｌ、　１６−１
ａｉ−ｂ７１　）　　（５）すなわち、特徴ａｉの示す
方向と特徴ｂｉの示す方向との実効的な差をｄ（ｉ、ｊ
）としている。

Ｄ　Ｐマツチングは次の漸化式計算で定義される。

で繰り返される。この結果、入力バタンＡと標準ハ’Ｘ
　ンＢ’　ト（Ｄ距ｍ、Ｄ　（Ａ、　Ｂ”）は、Ｄ　（
Ａ、　Ｂ”）−ｇ　（Ｉ、　Ｊ”）と得られる。

第６図は以上のＪＪ　Ｐマツチング演算を行なうための
装置概念を示すブロック図である。演９にメモリ２０は
入力バタンの特徴番号１によってアドレス指定されるよ
うになっており、初期条件どしてｉ−１の位置に（６）
式のｇ（１，１＞が記入され、ｌ１１）。

の番地には十分大きな数値■が記入さｔじＣいるとする
。以後ｊ−１としてｉ−２，３・・・・・・・・・・・
・■と変化される毎に（７）式の計算が行なわれ、さら
にｊ−２，３・・・・・・・・・Ｊ″と変化される各ｊ
の値に対してｉ−１，２・・・・・・・・・■と変化さ
れ、各（ｉ、ｊ）の組合せに対して（７）式が計算され
る。

ここで、一般的に（ｉ、ｊ）の時点において、どのよう
な計算がなされるカ・を説明する。ｇ（ｉ、　’ｊ　）
の計算が始まる時点でレジスタ２２にはｇ（ｉｌ。

ｊ−１）が、レジスタ２３にはｇ（ｉ−１，ｊ）が入っ
ている。このようになっている理由は、後で明らかにす
る。最初に演算メモリ２０よ９ｇ（ｉ、ｊ−１）が読み
出されレジスタ２１に記入される。比較器２４では信号
線ｇ、より与えられる前記レジスタ２２の内容と、信号
線ｇ、を経由して与えられる前記レジスタ２３の内容と
が比較され、その最小値が信号線ｇ４に出力される。か
くして（７）式のｍＪｇ（ｉ−１，ｊ　）、　ｇ（ｉ−
１，ｊ−１））の部分が計算されだことになる。他方信
号＋腺ａとｂには入力バタンのｑ′ｉ徴ａｉと標準バタ
ンの特徴ｂｊが与えられる。

距ｐｔｓｗｒｎ部２６では、これらをもとに（５）式の
距離ｄ（ｉ、ｊ）が算出され、信号線ｄに出力される。

加算器２５ではこの信号ｄと前記信号ｇ４の加算が行乞
われる。これによって（７）式の計算が終了したことに
なる。この結果は信号ｇ、として演算記憶２０の第ｉ番
、地とレジスタ３２に記憶される。

′まゾζ、同時にレジスタ２１の内容すなわちｇ（ｔ。

ｊ−１）はレジスタ２２に転送される。

かくして（７）の漸化式計算が、この時点のｉに関して
終了したことになる。この時点でｉを１だけ増加するこ
とによって、次のｉに関するサイクルに入る。この新し
７いｉを基準に考えるとレジス、り２２にはｇ　（ｉ−
１，ｊ−ｒ　）、　ｔたレジスタ２３にはｇ（ｉ−１゜
ｊ）が入っていることになる。これが前に予告し７たこ
とであって、かくして新しいｉに関する処理が可能にな
った。

以上の如く計算を進めると、レジスタ２１と２２の動作
によりて、ｇ（ｉ、ｊ）とｇ（ｉ、ｊ−１）の演算メモ
リを共通化できるという利点がある。

本発明は上記のようなＩ）Ｐマツチング過程に制御記号
゛（，゛）、゛／　＃９％〔“、〕″による制則を組み
込むことを特徴としている。

以下ｔま第７図以下の一実Ｍｊｉ例に基づいて本発明に
ついて説明奮進める。

；π７図は本発明によるバタンマツチング装置の一構成
例を示すブロック図である。仁の中の各部は制ｆｆＵ部
８０よりの制御信号に基づいて動作する。

入力バタンバッファ３０には、（１）式の入力バタンＡ
が保持される。標準バタン記憶４０には（４）式に例示
しだ様な標準バタンＢ”を保持する。議論を一般化する
だめに標準バタンの例として、 Ｂ−ｂｙ　ｂｔ＋　（ｂ４〕、ｂａｓ　ｂ７ｓ　（ｂｏ
’３＋　ｂ＞１ｍ＜　ｂａｓ　＊　ｂｕｎ　ｂｊ５．　
ｂＩａ、ｔ）ｒｒ／ｂｔ。、ｂ、。ｔ　ｂ２１　ｌ　ｂ
２□、へ、）、賜（８）記号となっていると考える。

なお、各文字ｎに対して別個の標準バタンＢ”が与えら
れ、それぞれが入力バタンと比較されるのであるが、各
ａ準バタンに関して繰り返される以下の比較処理は本質
的に同一であるので、ｎを省略して、一般的に説明する
。

スタックメモリー７０は、第６図の演算メモリー２０に
対応するものであるが、本発１ノ１１の実施例である第
７図では第８図（ａ）に示すように多層構造になってい
る。すなわち、入カッ°＜タンの翳・徴番号ｉの他に、
スタック演７α部からの層１（択信号ｋによって層の１
１１＝号が指定上れるようになっている。

なお、（６）式の初期条ｌ／Ｉ：設定は第１層に対して
なされる。制御部よりのアドレス信号ｊが１からＪまで
変化される。一般的には、アドレスイ８号ｊに対１もし
て標準バタン記憶４０よりｂｊが信号Ｘとして出力され
る。との信号又はデコーダ部５０に入力され、標準バタ
ン中の特徴か、制御信号かの判定がなされる。信号Ｘと
して与えられるｂｊが特徴であった場合には、次のよう
な処理が行なわれる。

スタック演算部６０には、初期値１と設定されル眉カウ
ンタｋが内蔵さ）している。、とのカウンタの出力信号
・第１＜とＩＩ″Ｐぶことにする。この信号にはａＳ図
に関連して述べた層選択信＠にと外るｌ、のである。（
二のＭａ択イ言＠ｋによって指定される層を第６図の演
算メモ＋１２０と同一として、距離計算部２６とマツチ
ング処即部２７が作動１）Ｃ％　：ｒ−ｓ　６図の時と
同様にして（７）式の漸化式計算が実行される。女お、
第７図の距離Ｒ［腔部２６とマツチング処胛部２７は第
６図のそれぞれと同一の・ムのである。とれら１１ζよ
＝）て（７）式の計ｐがｉ−１ビ・１ら［まで実行され
ると、ｊが１だけ増加されて新だなｊに（！ηする処理
に移る。

欧にデコーダ部５０で、信号Ｘと］−て与、ｔられ一６
ｂｊが料量１ｎ号であると判定された時の処理にζつい
て述べる。制御記号が検出されると制御漸令Ｃがスタッ
ク演算部６りに送られる。百ｍのだめ４・Ｃ制ｆａｌ指
令も制御信号と同じく゛（・、゛）・、／・。

゛〔“、１〕“で示すことにする。

分岐開始記号１（“が検出された時の処理（ｄ、次の通
りである。

最切に、スタックメモリー７０の第に層に記憶されてい
るｇ（ｉ、ｊ）が信号線Ｇ　ｓ　’ｆｃ経出して、総て
読み出され、舘次、信じ・腺Ｇ２を経由してスタック演
算り７０の第（ｋ−ｉ４　）層に転送さ７Ｌ記１意され
る。

結局、スタックメモリ７０の第に層温１到目のデータを
−Ｇ（ｉ、ｋ）で辰わｔことにすると、Ｇ（ｉ、ｋ）→
Ｇ（ｉ、　ｋ＋１）、　ｉ−１，２・・・・・・・・・
工（９）なる操作が行なわれることに、繁る。

この転写操作にわＩＬ、い゛〔、次の処理が行表われる
。

スタック演算部６０の内部には第５ｉｐ（ｂ）に示す／
スタックレジスタが用意さルーこおり、層選択信号ｋに
よってｊ（）指定されるように２Ｊ、っている。

それぞれの第ｋｔＭの内容なｓ’ｒｇ（ｋ）と示す。

この時、′（“ｉｓ　’ｉ’　ｉむ（ｋ）　　、　　　
　　　　　（ｔｏ）なる代入処理が行なわれる。最後に ｋ　十゛ｌ　−＋　ｋ　　　　　　　　　　　　　　　
　（１１）なるカウンタ増加の処理がイｊなわれて分岐
開始記号゛（″に対応した処理が終了する。以上の処理
はブツシュダウンオートマトンにＪ、？けるブツシュの
処理に）ｉ４　貝し−Ｃいるので、プツシ５．処理と呼
ぶ。

次に分岐区切り記号゛／″が検出さ江た時の処理を述べ
る。忙νＩにヌタック＃節部６ｏ内で、前記スタックレ
ジスタの内容Ｓ　Ｔ　１１−　（ｋ　　１　）がＸべら
れろ。と、１１が分岐３ｒ１始記号１（“である）も、
フト１区切り記号゛／″でろるｔ）によ−・て以後の２
１（興が異２ｒってくる。

まず、５ＴＲ（Ｉｃ−］）−・（“でちった時の動作か
ら８ｈ′明する。この時はスタックメモリ７ｏの第（ｋ
−７，）Δ・ｉの内容：が消（ｋ＋１）層に宏寛さ１１
．ろ。

Ｇ（ｉ、に−１）→Ｇ（ｉｓ　ｌｃ　＋Ｉ　Ｌ　”１．
２・・・・・・・・・Ｉ　　（１２）なる処理が行かわ
れる。続いて、 ・／・ｉｓ　’ｒ几（１０（１３） なる代入処理が行なわれ、その後、 ｌ（＋１→Ｉ（（１４） なるカラン々の増加処理が行なわれＡ、。

ＳＴ几（ｋ−１）−′″／＃で奎り／ζ８時は次のよう
な１５作が行なわ１する。

間（（’＋（ｉ、　ｋ　）、　Ｇ（ｉ−に−１））→０
（ｉ、　Ｉｃ−１）　（１５）ｉ−１，２・・・・・・
・・・・・・■すなわち、第に層と第（ｋ−１）層を比
較してその小な方の値を第（ｋ−１）層に保存する。

次に、 Ｑ（ｉ、に−２）→Ｇ　（ｉｓ　ｋ　）　＊　ｉ−１，
２・・・・・・・・・・・・Ｉ　　（１６）なる転写が
行なわれる。

分岐終了記号゛）″が与えられた時には、次の処理がス
タック演算部により行なわれる。

すなわち、（１５）式と同じ、 ｍ１ｘ（Ｇ（ｉ、　ｋ　）、　Ｇ（ｉ、　ｋ−１）　）
−）Ｇ（ｉ、　ｋ−２）　（１７）ｉ　−１，２，・・
・・・・・・・・・・Ｉなる最小値選択保存の処理が行
なわれる。続いて、ｋ−２→ｋ　　　　　　　　　　　
　　　　（１８）なるカウンタ減算処理が行なわれる。

この分岐終了記号゛）“に対応した処理は、ブツシュダ
ウンオートマトンにおけるポツプの処理に類似している
のでポツプ処理と呼ぶ。

次に省略開始記号１〔″に対応した処理について説明す
る。この時、 Ｇ（ｉ、ｋ）→Ｇ（ｉ、　ｋ−Ｈ）　　　　　　　　　
　（１９）なる転送処理と、 ｋ＋１→ｋ　　　　　　　　　　　　　　　　　　（２
Ｄ）なるカウンタ増加処理が行なわれる。この処理もプ
ツシ瓢処理と呼ぶ。

最後に省略終了記号゛〕・に対する処理について説明す
る。この時は、 ｍｍ　（Ｇ（ｉ、　ｋ　）、　Ｇ（ｉ、　ｋ−１））→
Ｇ（ｉ、　ｋ−１）　（２１）ｉ−１，２，・・・・・
・・・・工 なる最小値化へ処理と、 ｋ　−１−）　ｋ　　　　　　　　　　　　　　　　（
２２）なるカウンタ減算処理が行なわれる。この処理も
ポツプ処理と呼ぶことにする。

次に以上のスタック演算がどのように機能するかを（４
）式の標準バタンＢにっｐて説明する。

以下の説明を容易にするためにｂｊなる記法と次のよう
な対応を与える。

第９図は第８図と同様にスタックメモリ７０とスタック
レジスタの内容を示す図である。図において左方にある
矢印は層カウンタｋが指定している層である。なお、ス
タックメモリの内容は数値例であって厳密な意味のある
ものでは無い。

第９図の（ａ）から（ｔりまでは、（２３）式の標準バ
タンの入力によってスタック演算が進行する梯子を示は
ものである。

同図（ａｉｒ土す、が入力された場合で、（７）式のＤ
Ｐ漸化式計算が行われ、結果のｇ（ｉ、１）が第１層に
保持されている。同様にす、ｔでは制御記号が無いので
（７）式のＤＰ漸化式計算が行なわれ、結果のｇ（ｉ、
２）が第１層にＧ（ｉ、ｉ）として保持されている。

この時点の一例を第９図（ｂ）に示す。ここでｂ３とし
て省略開始記号゛〔″が与えられると（１９）　（２）
）式が行なわれる。すなわち、第１層の内容が第２層に
転写され、層カウンタにも１だけ増加される。かくして
同図（Ｃ）の如くなる。続いて、ｂ４が与えられると瀉
２層上で（７）式のＪ）Ｐ漸化式計算が行なわれる。

その結果例を同図（ｄ）に示す。ｂ、−〕が与えられる
と（２１）　（２２）式が実行される。この時に−２で
あるので、−第２層と第１層の内容が個々に比較され、
小さい方が第１層に書き込まれる。層カウンタには１だ
け減算される。結果は同図の（ｅ）の如くなる。

ここで省略開始記号゛〔″と省略終了記号゛〕″で行な
われた処理の意味を説明しておく。

まず、省略開始記号１〔“によって第１層の複写が第２
層に作られる。第１層はｂ４の省略が生じたと想定した
時の順化式値を保存するのである。

第２層ではｂ４の省略が生じなカ）っだとして（力式の
ＤＰ漸化式計算が実行される。省略終了記号゛〕“が与
えられると、第１層に保存されている。省略が生じた場
合の順化式値と、第２層に保持されてのる省略が生じな
かった場合の漸化式値とを比較して小さい方、すなわち
最適なものを第１層に残している。

すなわち、以上の処理が終った後のＧ（ｉ、１）。

ｉ−１，２，・・・・・・・・・１は、それぞれ、省略
を生じるべきか、生ぜざるべきかに関して最適な判断を
行なった結果の順化式値になっている０ １）ａトｌ）ｒに対シてはスタックメモリの第１層を使
用して（７）式のＩ）Ｐｉ化式計算が行なわれる。

ｂｓ−（−ｂｏ　”　２−　ｂ＋ｏ−）に対しては、ｂ
３とす、に関する省略処理と同様なＩＩＩ！理が行なわ
れる。

かくして、ｂｌｌまでの処理が終了した時点でスタック
メモリの内容が第９図（ｆ）の如きであったとする。

ｂｕ−（が与えられると（１２）、　（１３）、　（１
４＞の処理が行なわれて結果ケよ、同図（ｇ）の如くな
る。以下、ｂｉｌｌからｂ１７までは、第２層に対して
（７）式のＤＰ漸化式が繰返される。その結果、同図（
ｈ）の如くなったとする。

ここで、分岐区切り記号ｂｕｓ−／が与えられたとする
。このとき層カウンタはに−２となっているが、Ｓ　Ｔ
　１（（ｋ−１）−８’ｒＲ（１）−’（”　ｆＴｈル
（７）ｆ（１２）、　（１３）、　（１４）式の処理が
行なわれる。すなわち、第１層の内容が第３層に転写さ
れ、かつ、Ｓ　’［”　１（（ｋ）とｌ〜て１″が書き
込まれた後、ｋが１だけ増加され、ｋ−３となる。すな
わち、第９１Ｊ（ｉ）の知くなる。

以下、ｂ＋ｐ　ｆｙ’らｂ２３までに対して（・よ第３
層を使用して（７）式のＩｔ）　ｐ　ｔｕｒ化式計算が
行なわれる。その結果が同図（ｊｌの１１１１１　＜で
ちっだとする。

この時点で第２層には、ｂｌｌｌからｂ１７の部分を１
吏用してＩ）　Ｐ漸化式計算を行なったイｊｑ果が、ま
だ第３層にはｂｌＯｈらｂ２ｇまでを使用してＤ１？漸
化式計算を行なった結果が、それぞれ渫持さノシている
。分岐終了記号１）２．−　）が与えられると、これら
がそれぞれ比較されて小さい方、すなわち加点に関して
最適な順化式値が選択されて第１層に沓き込まれる。ま
だ、ｋは２だけ減算されるので、結局第９図（ｋ）の如
くなる。

最後のｂｔｓに対しては、第’　Ｉｊｎ上で（７）式の
順化式ｉｆｆ’　算がなされる。その結果が同図（ｌり
に例示されている。第一層の１−Ｉ−１１に対応ず′る
数値゛５″が（Ｚｌ）式の標準バタンとの距ｒＪＤ　（
Ａ−、Ｈ）となる。

カ・くシて、制御記号゛（，゛１″、゛）、゛〔“。

：ビを２；む標準バタンに対してＤＰマツチングを行な
う方法が明らかにされた。

（７３）式の標準バタンの例で１」、　ｊ　％二Ｊ　−
２５−ｔで変化させんことによって比較処理が終了した
が、これｔま省略や分１ｕｋに関する変形奮すべて用短
して比Ｅｉジ処理４行なうのに比して（１耐めで少ない
。

すなわち、（２３）式の中の省略や分岐によって生じる
変形ＱＪ２全１１シで８極になり、それらのバタンの特
徴数Ｊ’　＆よ平均約１７である。しだがって、これら
のバタンを総≠て標準バタンとして比較（ｃ　４５４り
返す場合には、」に関して約１３６回の繰りｊｉｉＬ、
’ｒ行なうことになる。

以上、本発明の原理を実施例に基づいて説明したが、こ
れらの記載りよ本発明の権利範囲を１耐足するものでは
ない。

特に、不明ｍｌでｅよ、支竿バタン缶対象とした場合の
例忙説明し７ｙが、本発明の原理は音声バタンのように
時系列的に示されるバタンには普ｉ→的に適用ｉｆ能な
ものであぷ。

【図面の簡単な説明】

第１図から第５図までは、本発明の原理説明図第６図は
従来技術の説明をするだめのＵ　Ｐマツチング演？に装
置のブロック図、第７図は本発明の一実）、’ｉｌｉ　
、ｊ’５１Ｊを示すブロック図、第ｓ　＋：ａ（ａ）（
ｂ）ＨメモＩ＋の４Ｍ成例を示す概念図。第９１図の（
ａ）から＜ｅ＞までｔ↓動作例説明図である。 ２０、演算メモリ、２１．２２．２３．　　レジスタ、
２４、比市交器、２Ｆ５．加算器、２６．距離計針部、
２７、マツチング処理部、３０．入力バタンバッファ４
０、標準バタン記１、は、５０．デジーダ、６０．スタ
ック演′も℃部、７０．スタックメモリー、８０．制御
部をそれぞれ示す。 第１図 第２図 く 鐘 （Ｃ） ６７２− 四　−　　　　　　　　　　； （ （ｉ　　〜 恍 ＩＪ　　　　　　　　　　　　　　　　　　　　　　　
”ＲＣ＞　、　　　　　　　　　　　　　　　　　　　
　　、邂 皆　−− （蓋 尖 う− 舜 浄 手続補正書（方式） １１’　ｉ’ｉ’１″庁長官　殿 ■、事ｆ’ｌの表示　　　昭和５７年　　特杵願第１５
６４１３号２、発明の名称　　　パタンマ・ソチング装
置３、補正をする者 事件との関係　　　　　　　出　願　人東京都港区芝ｔ
；、　ｒ　＋　１３３爵１号（４２３）　　　日本電気
株式会社 代表者　関本忠弘 ４、代理人 〒１０８　　東ｊニジ都港区芝＋１−１’１１３７計８
′１Ｊｆ１：友二１１１ビル５　補正命令のトコ付 昭和５７年１１月３０日（発送日） ６　補正の対象 明卸１書の発明の名称の欄、、 明細書の特許請求の範囲の欄。 明細書の発明の詳細な説明の欄。 ７　補正の内容 明細書第１頁及び第２頁を、別紙のとおり補正する。 代理人　弁理士　内　原　　晋 明　　　細　　　書 発明の名称　　バタンマツチング装置 特許請求の範囲 特徴の時系列中に分岐開始記号１分岐区切り記号、分岐
終了記号、及び省略開始記号、省略終了記号等の制御記
号を含んでなる標準バタン記憶部と１％徴の時系列とし
てなる入力バタンを保持する入カバタンパソファと、上
記標準バタン中の各要素を特徴と各制御記号とに分類す
るデコーダと複数の記憶番地を層とし多層構成されるス
タックメモリと上記人力バタンの特徴と標準バタンの特
徴間の距離を言１算する距離計算部と上記スタックメモ
リの一層より読み出される各データを比較しそれらの最
小値に前記距離唱腔部よりの出力を加算し、前記スタッ
クメモリに記入するという動的計画演算を実行するマツ
チング処理部と前記デコーダよりの制御信号に応じて前
記スタックメモリの層間の最小値検出１層間のデータ転
送を行なうスタック演算部とより構成されることを特徴
とするバタンマツチング装置 発明の詳細な説明 本発明は文字認識等のバタン認識システムの中心構成要
素であるバタンマツチング装置に関する。 文字認識等のバタン認識システムにおいては認、を原理
としてバタンマッヂン、グ法が多用されている。バタン
マツチング法とは、認識対象となる各文字に対して標準
となるバタン（以下標準バタンと呼ぶ）を予かしめ用意
しておき、未知バタン（以後入力バタンと呼ぶ）が入力
されると、標準バタンとの比較操作を行なって、最も類
似した標準バタンを選択することによって判定を行なう
ものである。このバタンマツチング法は原理が簡単であ
り比較的性能が良いので、広く利用されているが手書き
文字のようにバタン変動が激しいものを対象とする場合
には認識性能が劣化するという欠点があった。認識性能
劣化の対策としては１種々の変形文字バタンを総て用意
する方法がとられるが手続袖止書 ＋１を付１１５８年６月２２１ｊ 才）、１乍　庁　長　ｔ″１　　　　ル（ン１、・１１
件の表示　　昭和５７年特　許　順光１５６４．１３号
２、発明の名称ｌクタンマッチング装置３、補正をする
台 事件との関係　　　　　　　出　願　人東京都港区芝五
丁口３３辱１　＞、’ （４２３）　　　日本電気株式会社 代表と　関本忠弘 ４、代理人 〒１０８　　東市部港閤芝五丁目３７番８号　ｒ主役三
田ヒル小話　重信（０３）４５６−３１１１（大代表）
５、補正の対象 明細書の発明の詳細な説明の０４４ ６、補正の内容 （１）明細書第２３頁第１９行目に続けて次の文を挿入
する。 ［また、以上の実１４ｈ例の説明でｒよ簡単の／ζめに
Ｉ）Ｐ順化式として最も簡Ｑｔな（７）式を用いだが、
これに限定されるものではない。例えば、音声認識の分
野では、次のような順化式が多用されている。 を用いたＪ）Ｐマツチングが可能である。その１易合に
（ｌ−１：第８図のスタック７ｏの各層をそれぞれ２屯
にして、Ｇ（ｉ、ｋ）の場所に２１固のＶｉ１直ＯＩ（
ｒ、　ｋ　）と０２（ｉ、ｋ）と金肥１意できるように
する。 このスタックの層上でＩ）Ｐ　＃化成（２／Ｉ）を計算
する直前には、（）＋　（ｒ−ｋ　）　Ｋはｇ４　ｉ−
］、、　ｊ　−１）がＧ２ｒｉ、ｋ）にはｇ（ｉ−１，
Ｊ−２）が記ｔＳされている。この層でＤＰ漸化式が計
算され終こた時点ではＧ、　（ｉ、　ｋ）ニｇ（ｒ＝＞
カ、Ｇ２　（＋、ｋ　）　ｋ＝−はｇ（ｉ、ｊ−ｚ）が
保Ｊ’Ｎれるものとする。このように２東の記憶よりな
る層で（２４）式を実行するだめの処理は、（７）式を
１屯の記憶のみよりなる層で実行した第６図の回路構成
で行ったのと同様の考えで実現できる。 層間のデータ転送や最小値検出の処理は、２重の記憶よ
りなる層を単位として行うことになる。 例えば、（９）式のデータ転送は、 Ｇ、、　（ｉ、　Ｉｃ　）−Ｇ、、　（ｉ、　ｋｌ１　
）なる処理に置換えればよい。また、（２］）式の最小
値検出はｍｉｙ＋　（Ｇ、（ｉ、　ｋｌ、　Ｇ、（ｉ、
　ｋ−１））−＝Ｇ、　（ｉ、　ｋ−１）ｍｍ（Ｇ２（
ｉ、　ｋｌ、　Ｇ２（ｉ、　ｋ−１））−”０２　（ｉ
、　ｋ−１）　　　　（％）ｉ−１，２・・・・・・・
・・・・・■なる処理に置換えればよい。 この他にも、Ｉ’ＩＥＩコＥＴＨＡＮＳＡＣ’Ｌ”ＩＯ
Ｎ　ＯＮ　ＡＣＯＵＳＴＩ−Ｃ８ＳＰＬ’ＥＣＨＡＮＩ
）　５ＩＧＮＡＬ　ＰＩＭ）ＣＩ８ＳＳＩＮＧ　、　Ｖ
ｏｌ。 ＡＳＳＩ）−２６ＮＯ，１（１９７８年２月発行）Ｐ４
３〜Ｐ４９に”Ｉ）ｙｎａｍｉ　ｃ　Ｐｒｏｇｒａｍｍ
ｉ　ｎｇＡｌ　ｇｏｒ　ｉ　ｔｈ＋ｎ　Ｏｐｔ　１ｍ−
１ｚａｔｉｏｎ　　ｆｏｒ　５ｐｏｋｅｎ　ｗｏｒｄ　
ｌＬｅｃｏｇｎｉＬｉｏｎ”と題して発表された論文」
には；）ｐ　ｔ・１重７化式の多くの変形が記載されて
いるが、これらの１ｌｌｌ’を住人の場合でもスタック
の層を多重構成として、しかるべき処理を行うことによ
って本発明の原理を実１ｉｆｌＩできる。」代献弁即１
　臼ノ１ｎ　　　　買値

Claims (1)

【特許請求の範囲】
1. 特徴の時系列中に分岐開始記号、分岐区切シ記号、分岐
   終了記号、及び省略開始記号、省略終了記号等の制御記
   号を含んでなる標準バタン記憶部と、特徴の時系列とし
   てなる入力バタンを保持する入力バタンバッファと、上
   記標準バタン中の各要素を特徴と各制御記号とに分類す
   るデコーダと複数の記憶番地を層とし多８５構成される
   スタックメモリと上記人力バタンの特徴と標準バタンの
   射それらめ最小値に前記距離計算部よりの出力を加算し
   、前記スタックメモリに記入するという動的計画演算を
   実行するマツチング処理部と前記デコーダよりのｔｌＪ
   　ＩＩＩ　ｔ＃号に応じて前記スタックメモリの層間の
   最小値検出、居間のデータ転送を行なうスタック演算部
   とより構成されることを特徴とするバタンマツチソゲ装
   置