JPS6033676A - パタ−ンマツチング方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、パターン認識、特に文字など２次元図形の
認識におけるパターン間の相違性の度合をめるパターン
マツチング方式に＠ｊる。

〔背景技術とその問題点〕

２次元図形、音声等のパターン認識において、パターン
から抽出された２つの特徴ベクトルの集合、 Ａ二（Ａｌ　＋　ＡＨ＋・・・・・・、Ａｌｌ　・・・
・・・・・・・・・（１）Ｂ”　（ｎ、＋　Ｂｌ　＋　
・・・・・・、Ｂ１）　・・・・・・・・・・・・（２
）の類似性または相違性の度合（以下相違度とｎｔぶン
を評価することは、その中核的な問題である。

例えば、文字認識のためのパターン整合法においては、
標準ノ（ターン（マスク）の各点Ｚｌ＝（ｘ＋　ｒ　ｙ
ｔ　）の濃度値の集合Ａ”（ｐ（Ｚｔ月と、未知式カバ
ターンの濃度値の集合Ｂ＝（ｑ（Ｚｌ）］との重ね合わ
せの差 ＤＩ（Ａ、Ｂ）＝ΣＩｐ（Ｚθ−ｑ（Ｚ＋）ｌ　−−−
（３）を相違度とすることにより、入力文字と各文字概
念間の近さの評価が行われる。なお、相関値Σｐ（２，
）・ｑ（Ｚ、）を類似度に用いたり、この相関値や第（
３）式の値を、ＡとＢの平均濃度で正規化する場合もあ
るが、いずれも重ね合わせの量をめるという意味で基本
的な立場は同じである。このパターン整合法は論理が単
純であるため、印刷文字認識の手法として広く用いられ
てきたが、本質的忙標本点の位置は固定であるとして重
ね合せているため、手書き文字のように標本点の位置が
変動する対象に対しては、その適用は困難である。

このため、このような対象に対しては、入力とマスクと
の間で特徴の塊の対応づけを行う、いわゆる構造解析法
の立場が必要となる。

この構造解析法の一つとして、特徴が時系列である音声
認識の分野忙おいては、標本点（時間軸）を逐次的に非
線形に伸縮させて最適な対応づけを行５ＤＰ　（動的計
画法：　Ｒ，Ｂｅｌｌｍａｎ　”ＤｙｎａｍｉｃＰｒｏ
ｇｒａｍｍｉｎｇ”＋　Ｐｒ１ｎｃｅｔｏｎ　Ｕｎｉｖ
ｅｒｓｉｔｙＰｒｅｓｓ＋１９５７）の形式を用いるも
のが、マツチングの標準的な手法として定着している。

テなわら、音声のように特徴が系列化されている場合、
第１図のように非線形如対応させるための第（１）式お
よび第（２）式のＡの標本点１とＢの標本点ｊの組合せ
をＣ（ｋ）＝　（１（ｋ）、　ｊ　（ｋ）　）　・・・
・・・・・・・・・・・（４）任意の標本点ｌとｊの特
徴間の距離を ｄ　（ｃ）＝ｄ　（１，ｊ）＝ｌＡ＋　Ｊｌ　・・・・
・・・・・（５）とし、標本点ＡとＢの相違度を とそれぞれ定義する。第（６）式は、ＡとＢの対応、の
組合せを種々にとり、その中で和が最小なものを全体の
尺度とするものである。ｗ（ｋ）は、システムを柔軟に
するために導入された非負の重み係数である。

ここで、ＡとＢの対応を１対２筺で許し、歪Ｃ＝　（ｉ
　、　ｊ　）を、Ａ側のみからの関数（ｌ、ｊ（１））
にするという、いわゆる非対称（Ａｓｙｍｍｅｔｒｉｃ
）プｊ立場をとり、１点の標本化間隔（後述の輪郭線分
の例では線分長ンをｌ、とすると、ｗ　（ｋ）　＝　ｗ
（ｉ）＝ｌ、と書け、Ｄ！をめる問題は、・・・・・・
・・・・・・・・・（７）なる漸化式を、下記のｊ　（
１）に関する拘束条件（１ン。

（２ン　、（３） （１）ｊ（１）は、連続的な単調増加関数である（２１
ｊ（１ン　＝１．ｊ（Ｉン　＝　Ｊ（３）ｊ（ｉ）の値
はｌ付近にある のもとで、順次計算し、第１段での漸化的評価量ｇ（１
，１）をめるＤＰの問題忙帰着する。最終的な相違度Ｄ
２は でめらｊる。すなわち、第（７）式の逐次的な最適化に
より、最終的には目的とする第（６）式の大局的な最適
解を第（８ン式でめられる相違度り。

として高速に得ることができる。

なお、等間隔（’、＝１）の標本化で、特徴間の距離を ｄｉ　（ｔ、ｊ）＝ａ（ｔ、ｊ） ｄａ　（ｉｌｊ　１．ｊ）＝（ｄ（ｉ、ｊ−１）＋ｄ（
１，ｊンン／セｄ　、　（１−１，ｌ、　ｊン＝（ｄ（
ｉ−１，ｊ）＋ｄ（１，Ｊ）　ン／２・・・・・・・・
・・・・・・・・・・・・・（９）としたものは Ｈ，５ａｋｏｅ　ａｎｄ　Ｓ、Ｃｈｉｂａ　”Ｄｙｎａ
ｍｉｃ　ｐｒｏｇｒａｍｍ−１ｎｇ　ａｌｇｏｒｔｈｍ
　ｏｐｔｉｍｉｚａ口ｏｎ　ｆｏｒ　ｓｐｏｋｅｎｗｏ
ｒｄ　ｒｅｃｏｇｎｉｔｉｏｎ″ＩＥＥＥ　Ｔｒａｎｓ
ａｃｔｉｏｎｓｏｎ　ＡｃｏｕｓｔｉｃＩＩＳｐｅｅｃ
ｈ　ａｎｄ　Ｓｉｇｎａｌ　Ｐｒｏｃｅ１１ｓｌｎｇ＋
Ｖｏ１．　Ａｓ　５Ｐ−２６，Ｎｏ、　１．　ＰＰ、　
４３−４９（１９７８）に示されている。

また、文字認識の分野においても、特徴が時系列である
オンライン形ではＤＰが利用されやすい。

しかし、オフライン形の文字認識では、特徴が２次元的
に分布するため、ＤＰの適用は容易ではない。２次元図
形の特徴の場合、２次元的な近さの関係を保持てること
が重要であるが、この関係を保持したま〜１次元的に系
列化するのが困難なためである。

この問題について具体的忙説明する前に、この発明の２
次元図形のＤＰマツチングで用いる特徴ベクトルと言葉
・記法の定義について述べる。まず、白黒の２値図形の
境界の黒点を＠郭点、輪郭点の一繋がりの閉ループを輪
郭と呼ぶ。次に、第２図（ａ）のよ５に、白点を左に見
て廻る方向に輪郭を直線近似した時のその線素を輪郭線
分または単に線分（矢印及び符号１−１２で示すン、各
線分の最初（矢の印のない側）及び最後（印のある対す
る最初及び最後の線分を始線及び絡線と靜ぶ。

始線の始点と絡線の終点とは一欽する。

このように輪郭を線分近似すると、全ての線分ｌは、１
の始点を終点とする線分１′を持つが、このｌ′を１の
直前の線分と呼び １’＝Ｐ（ｉ）　・・・・・・・・・・・・・・・・・
・・・（１０）で表わす。

また、第３図の線分１の特徴ベクトル定義図に示される
ように、線分ｌの属性としては、始点および終点座標’
１２　＋　Ｚ”ｌ　、始点から終点への方向ａｌ　、長
さｌｌ　が掲げられ、それぞれ下記のように定義される
。

最後に、ある線分ＩＫ″先行可能”な線分の集合Ｑ　（
ｉ）を次のよ５に定義する。

Ｑ　（１）　＝　（自条件ｌかつ条件２かつ条件３を満
足する）　・・・・・・・・・・・・・（１２）条件（
１）　：　ｌＺ’ｉ−Ｚフ・１≦δ（例ｔば３）条件（
２）　：、＋ｚ２−　ｚｉｐ　＋≦β（Ｎえば３２）ま
たはｌ　ａｌ　−ａ、ｌ　ｌ　＞π／２ｆ７．：ｉ！　
（Ｚ’ｉ　、−ｚ、−）　・（ｚ？’−Ｚ’ｒ　）　≧
０Ｉｆ−件（３）　：　ｌＺ’１−ｚｒ−１りｌｚ’ｉ
　Ｚ；（白１カッ、ｌ　Ｚ’ｉ　Ｚ’（ｒ　ｌ　りｌ　
ＺｌｉＺ”ｌ〃ｌ、　ｉ’＝＝Ｐ（１’　）すなわち、
条件（１）、（２）は第３図において斜線の内部に終点
がくる線分、あるいは、半径βの円内に終点があり角度
差がπ／２以上の線分を意味する。ただし、ベクトルに
対する絶対値の定義第（１１）式から実際は円ではな（
菱形（正方形を４５゜回転させたもの）である。条件（
３）は、上記条件（１）、（２）の線分のうち、前後で
１との距離が極小になるものだけを残すことを意味する
。

この集合は、線分１′の終点の次に線分ｌを接続して対
応させることを許容させるＴこめのものであり、この発
明のパターンマツチング方式において重要な役割を果た
すものである。

以上の定義のもとで、マスク側の特徴Ａ二（Ａ、）と入
力側の特徴Ｂ＝（Ｂｊ）のＤＰＩＣよる対応づけを考え
るが、轍初に、マス）り側の特徴（Ａ＋　Ｊに系列を与
える。これには前述の輪郭線分の順序をそのまま利用す
る。

次に、入力側も追跡の順とい５意味では系列化されてい
るが、マスク側との対応づけにこの系列をそのまま用い
ることはできない。それは、第２図（ｂ）　Ｉ’（示さ
れるように、線に切れが生ずると、輪郭の系列が変化し
てしまつ（線分ｌ〜１４で示ｊ）。この現象は、特に手
書漢字のように多数の”画”から構成される文字の場合
、ある画の開始点や終了点と他の線との間で起き易い。

例えば、手書漢字の”田”の場合、標準的には線によっ
て区切ら才する白地の数（ループ数２は４と考えられる
が、現在標準的な実験用データベースとして用いられる
電子技術総合研究所手書教育漢字データベースＥＴＬ８
の解析によれば、ループ数は０〜４まではｙ平均的に分
布することが報告されている。

このことは、手書漢字のように複雑で変形の激しい２次
元図形の相違度の好例において、系列化さ第１た特徴ベ
クトル間での対応づけという仮定が成り立てないことを
示している。

〔発明の目的〕

この発明は、上記の問題を解決するためになさ４だもの
で、系列化さ４ていない特徴ベクトル集合間の類似度を
、ＤＰｑ−法を用いて高速匠！１１ｆできるようにした
パターンマツチング方式を提供するものである。

〔発明の概安〕

この発明は、上ｎＢの目的を達成するため、下記（１）
　＋　（２）　、（３）の機能を有するパターンマツチ
ング方式である。

（１）入力側、マスク側双方共、白と黒の境界部の直線
近似（輪郭、線分）を用いることにより、＃ｌｌＩ線化
図形に比べす）ｖ報の歪みを少なくすると共に。

原図形に比べ対応候補点を減少させる。また、輪郭線分
の方向性を距離評価に用いることにより、評価関数の精
度向上を図る。

（２）　マスク側特徴は、（輪郭の順序性をそのまま用
いてン系列化されているのに対し、入力つ１り待機は基
本的には順序性がないものとして対応させることにより
、線の切断に対しても強いマツチングを行い、同時に、
入力側の各輪郭線分ＶＣ″先行可能”′な線分の集合を
定義することにより、ＤＰの持つ処理の高速性を生かし
、不自然な対応を防ぐ。

（３）単に輪郭線分間の距離だけでなく前後の輪８１ｖ
ｊＩ分のつながり方も評価することにより、重ねを 合ぜの址だけでなく、空岬扉線形に歪ませた時の歪み量
も評価に入れる。

〔発明の原理〕

次に、この発明のパターンマツチング方式の原理につい
て説明１−る。

まず、マスク側特徴の記法け、第Ｑｌ）式の通りとし、
入力側特徴に対しては、始点座標ω）、終点座標ωＴ、
方向α４．長さλ、なる記号を用いる。なお、前述の説
明では、マスク（ｔｉｌｌ　Ｋ対して先行可能な線分の
集合を定義したが、実際のマツチングでは、入力側のみ
にこの集合Ｑを定義する。

以上の＄備のもとで、上記第（７）式に相肖する漸化式
を、 ｇ　（ｉ、ｊ　）＝ｍｌｎ（ｈｉ（１，ｊ）、ｈ２（Ｌ
ｊ）、ｈａ（Ｌ　ｊ　月・・・・・・・・・・・・Ｃ３
） ・・・・・・・・・・・・・・・・・（１４）と表現す
る。第Ｃ１３）式のｈｉ　、ｈｚ　、ｈｓは第４図のマ
スク線分１と入力線分ｊとの対応図に示さ才する（ａ）
、　（ｂ）、（ｃ）の対応評価量であり、（ａ）は１対
１（ｉ二１′対ｊ　＝　ｊ’ン、（ｂ）は１対２　（１
＝１’対ｊ””ｊ　１．ｊ　）　、　（ｃ）は２対１　
（ｉ’＝　１−１゜ｌ対ｊ’＝ｊ）を、また、Ｍはマス
ク、Ｎは入力を示す。

こ五で、第（７ン式のｍｉｎの中の第１項と、第（１４
）式のｈｌ　をめる式を比較してみると、相違の第１点
は、第（１４）式でり、をめる場合、ｊ′ＣＱ（ｊ’）
ＶＣ対してのｍ１ｎ（Ａ＋小化）処理が行われている。

こねに対し、第（７）式ではｊ〃＝ｊ−１に対する計算
項はただ１つである点である。これは、１次元に系列化
さ４ている場合は、ｉ−１の次Ｋｉ、ｊ−１の次Ｋｊが
生起てることが保障さ４ているため、ｉＫｊが対応する
時、１−ＩＩＬ対応する相手をｊ−１だけにすればよい
ためである。

一方、系列化さねてぃない場合、ｉＫｊが対応する時、
１−ＩＫ対応する相手として全てのｊ′を考慮しな１す
ればならないので、Ｊ　ｅ　Ｑ　（ｊ’）　という条件
が必要となる。こ〜で、Ｑ（ｊ’）は、Ａｉｒ述した先
行可能な線分の集合である。Ｑ　（ｊ’）　として全て
の線分の集合ではなくとのよ５な部分集合を用いること
により、計算が高速化されると共に、不自然な対応が除
去される。

相違の第２点は、γの項が存在する点である、第（７）
式では対応づけられた特徴間の距離は訂制されているが
、（’−（ｉ、ｊ）の歪に関する評価は行われていない
。Ｃ＝（１，ｊ）を歪ませた結果、完全に合致するにし
ても、歪の獄が多げｊば評価は下がると考えるのが自然
である。そこで、各時点での評価において、マスク側の
１’−１から１への遷移に対応する入力側のｆからｊ′
への遷移の差次に、上記特徴（輪郭線分）間の距離を下
記１ｋ・・・・・・・・・・・・・・・（１５）上記第
（］５ノ式中の、ｄ＋における記号〜は角度差の演算で
、結果は−πからπの間にｋ）す、係数２／πは、角脱
差がπ／２になった時、単位長の差と同じ評１＋ｌｔｉ
　ｉｔに１°るための係数である。また、長さは、２倍
まＣの差を評価０でｔ′「＊　ｉ−る。ｄ２＋ｄ３の場
合、上記の距離を長さで比例配分し・（いる。

また、γθ項につい又は、対工６をとる１′α分ＣＡ側
はｉ′、Ｂ１１１ｌｌはｊ’　）の他点と、その一つの
前の線分（Ａ側はｉ’−１，Ｂ側はｊ＃　＞の終点の間
の位置関係から歪み盪を評価−ｆるものであり、ｒ（ｔ
’　ｌ＋１’；ｊ＃＋ｊ’）＝１１＋ｚ’ｆｆ’−ω’
ｙｌ　ＩＺＹ’　Ｚ’ｔ−＋ｌ　１・・・・・・・・・
　・・・・・・（ｉ６ンで定ｔｋさＪする。

通常、マスク側線分は連続しているから＋　Ｚ〒’　−
ｚｉ＋−＋　ｌ　＝　。

であるが、ある輪郭から次の輪郭に移る時はＯでない。

初期榮件は、 とする。

上記第（８）式に相当するマスク１１１１１　Ａと人力
ｎ１ｌＪ　Ｂの全体としての最適対応による相違度は、
Ｄｓ　（Ａ、　Ｂ　）　＝−」−−ｍｉｎ（ｇ（１，ｊ
　）　ｌ　−−−・−（１Ｂ）Σｌ、ｊ でめられる。

このよう（／ｃして第（１８）式で示される相違度Ｄ３
の計算を行うと、系列の順序が変ってしまった入力側に
対してもマスク側との対応をとることかでき、かつ、線
の！７Ｉれの段を考広に入Ｊまた評価量をＤＰ千手法用
いて高速にイ）Ｉることが出来る。

〔発明の実施例〕

第５図はこの発明の一実施例のマツチングの手順を説明
するためのブロック図である。

同図におい工、ｈ、、ｈ、、ｈ３はそれぞれ第（１４）
式の計算ブロックでｋ）る。用゛算フロック１１１に人
力さｊるデークレＪ１マスクｌｅ　ｉ、ｉｉ暫１（Ａの
特徴ａ１１１（＋　ｌＺ’ｊ　Ｚニー＋ｌ、入カバソフ
ァ部Ｂの特徴α、。

λｊ、１ωンーω１・・１、および第１−１段の漸化的
評価量Ｈ（ｌ　ＩＩＪ’　）、ｊ’６Ｑ　（ｊ）である
。ｇ（１−１，３）は、一時記憶ブロックｇ−＋に貯え
られている。筐１こ、計算グ１１ツク１１２に人力さ１
するデータハ、ａｌ　ｌ　ｌしｌ　ＺＹ　ＺＹ−＋　ｌ
　ｒ　α、（Ｄ、２両。

α４．λｊ、１ωド（１）−ωｊ・１．コ　ｃＱ　（ｐ
（ｊ）　）およびブロックｇ−＋からのｇ（ｌ−１，ｊ
’、）である。そして、計算ブロックｈａ　Ｉｃ入力さ
才するデータは、マスク側のＡの特徴−８＋−１＋　ｌ
Ｉ−＋＋　Ｋｌ　＊　ｌ、　ｌ　ｌ　Ｚ’Ｈ−＋−Ｚ”
１−霊ｌ　ト入力側Ｂ　（’）　’ｎ徴αｊ、λＩ　ｒ
　Ｋ）ニー（１）”、ｔｒ　。

および第１−２段の漸化的評価−ｔ　ｇ　（＋　−２，
ｊ’ン。

ｊ’ｅＱ（ｊ）　であり、ｇ（１−２，ｊ’）は、一時
記憶プｐツクｇ−２ＦＣ貯えられている。

Ｉｔｓグロ７りり、　＊　ｈｚ　＊　ｈｓ　テＭＩ′算
すｔｌｆ、＝第（１４）式の値は、第０３）式の最小値
針別−グロンクｍｉｎ。

に送られ、第１段における各ｊとの漸化的評価量が計算
さ第１、一時記憶ブロックｇ。Ｋ送らｊ第１段の計算が
完了する。

次に、第ｉ＋１段の計算の準備として、まず、ｇ−１の
内容を全てｇ−、ＩＦ−送り、その後ｇ。の内容準備を
完了する。

以上が、この発明の要部をなすＤＰによる反復ｔｒｉ　
ｘ部分に関−「る動作であるが、処理の全てを説明する
には、第（１７）式の初期値設定と、第０８２式の相違
度に関して補足する必要がある。そこで、第１段から順
に説明する。なお、■〜■は各処理を示している。そし
て、■〜■は繰返しである。

まず、処理に先立って、初期値設定ブロックエＮＩＴＶ
ｃより、ｇ−＋の全ての値に零が設定される■。これは
第（１７）式の第２式に相当する。そして最初のマスク
線分１＝１に対する計算では、ブロック１１１＋１１３
　に対し、ｒの値として零が供給さｆｔ、、ｈ、　から
は■が出力さ第１る■。丁なゎちブロックｈ、からは ｈＩ（１＋　ｊ　）　”’ｌ　・ｄ、（１，ｊ）を出力
し、ブロックｈ、がらは ｈｚ　（１，ｊ　）　＝１１・ｄ、（ｌ、Ｐ（ｊ）、ｊ
）が出方され■、その最小値がブロックｍ　ｌ　ｎ□で
計算される■。

なお、処理■の時、ブロックｈ、からωが出方されるの
は、ｈ、の値がｍｌ］１の出力として選ばれないように
するためである。次に、処理■で計算された各」ｋ対す
る第１段での漸化的評価値ｇ（１、ｊ）は全てブロック
ｇ０に送られ記憶され■、第１段の計算が完了し、ｇ−
ｒがｇ−２に送られ■。

ｇｏがｇ−＋に送られる■０ ２番目のマスク線分１＝２ＶＣ対する第２段のｉｔ算に
おいては、ブロックｈ１およびブロックｈオでは上記の
通常の反復計算時の値が計算さ才する。

これに対し、ブロックｈ、では、まず、第１段に先立っ
てブロックｇ−ｓに設定された値がブロックｇ、に移さ
れてきているためブロックｇ−２の値は全て零である■
（第（１７）式の中段の式）。また第（１７）式の第３
式より、ｒの値も全て零として計算する。そして、ｈｌ
、ｈ２．ｈ３の結果がブロックｍｉｎ、　ＶＣ送られ■
、各ｊに対する第２段目の漸化的評価値ｇ　（２，ｊ　
）　が計算さ才１、ブロックｇ。

に貯えら１１■、第２段の処理を完了し、ｇ−１からｇ
−２■＋　ｇｏ　からｇ−１■・＼のデータの移動を経
て第３段の準備を完了する。

第３段取持の反復処理は上記した通りである。

最後に、第１段でのｇ（Ｉ、ｊ月＝１〜Ｊか■。

■、■のｊＫ関する繰返しで計１．され、ブロックｍ１
ｎ２に送られ第（１８）式のｊに関する最小値がめられ
■、Σ輪　で除され“〔最適対応による全体の相違度Ｄ
ｓ（Ａ、Ｂ）がめられる■。

なお、上記はこの発明の一実施例であって、以下の（１
）〜（５１に述べるような変更、およびそれらの複合的
変更は容易に可能である。

（１）第（１４）式では、全ての線分で前との接続が切
断可能として、ｍｉｎの範囲な　ｊ’ｅＱ（ｊ’）　と
しているが、切断される可能性のない点では、ｊ″二Ｐ
ｊ’）　として計算丁れば、ｉＪ　（１４）式の最小化
を行う必要がなくなり、計算が晶速化される。具体的に
は、第２図（ａ）をマスクと考えた時、切断の（２）第
（１４）式、第（１５）式において、各線分σ」°長さ
１１を可変長にしたため、ｌ、の重みが計鰭゛式５゜の
中で用いられているが、固定長に゛するか、または線分
近似しないで、各輪郭点をそのま〜用いるかすれば、長
さを考慮する必要がなくｌよる。

すなわち、第（１５）式のｄ＋　、ｄ２１．ｄｓは第（
９）式で書換えられ、ｄは、 ｄ（ｔ、ｊ）＝−ｌα、〜ａｌｌ π と書け、計算が単線化できる。

（３）第（１３）式、第（１４）式を変形すると、とな
る。すなわち、第１段と第ｉ−１段の間で、途中結果と
してｇ’　（１’ｌ　ｊ’　）を計算することによりγ
の計算とｄの計算が分離できる。

（４）特徴として、輪郭ではなく、例えば中心線を用い
る。また、第（１５）式の特徴間の評価ｄを、角度差以
外の例えば、位置情報、線と腺の関係などの高次特徴な
とを加えて行う。

（５）上記実施例で説明したＤＰによる処理は、線分と
線分の対応付けのためだけに用い、パターン間の識別は
別の評価関数で行う。また、輪郭全体でなく、その一部
分毎ＫＤＰによる処理を適用する。

〔発明の効果〕

以上詳細に説明したようＫ、この発明によれば、系列化
されていない特徴ベクトル間に対し、線の切れなど位相
的変形を許容し、大局的最適評価を行う相違度を、ＤＰ
の手法を用いて高速にめることができる。さら匠、特徴
間の距離だけでな（、全問の歪も評価量に加えるととも
に、６先行可能”な線分の集合を定義することにより、
不自然な対応を排除しつＸ処理の高速化をはかることが
できる。また、この発明は、単に文字認識の輪郭特徴ベ
クトル間の相違度として用いられるに止まらず、広＜ハ
ターン認識に適用できる優れたものである。

【図面の簡単な説明】

第１図は音声のように系列化された特徴ベクトル間のＤ
Ｐマツチングの原理説明図、第２図（ａ）。 （ｂ）はこの発明で用いられる輪郭線分特徴と線の切れ
により線分の系列が変化することを説明するための図、
第３図は輪郭線分の特徴とその輪郭線分に”先行可能”
な輪郭線分の説明図、第４図（ａ）。 （ｂ　）＋　（ｃ　）はこの発明のＤＰマツチングの各
段における動作を説明するための図、第５図はこの発明
の一実施例のマツチングの手順を説Ｆ！Ａするだめの管 は計算ブロック、ｇｏ　＋　ｇ−ｒ　＋　ｇ−４は漸化
的畔価量の一時記憶ブロック、ＩＮＩＴは初期値設門ブ
ロック、ｍｉｎＩｙｍｌｎｌ　は最小値ＩＩ算ラフロッ
ク（、′　・□　、） 第１図 第２図 （ａ）　’　（ｂ） 第３図 第４図 第５図

Claims (1)

【特許請求の範囲】
1. 標準パターンのＩＰ＃微の集合Ａ　＝　（Ａｘ　、Ａｌ
   　−・・・・・・、Ａ９．・・・・・・、ａＸ）　を記
   憶するマスク記憶部と、未知入カバターンの特徴の集合
   Ｂ　＝　（Ｂ１．Ｂｌ−・・・・・・、Ｂ３．・・・・
   ・・、ｎ、）　を保持する入力バッファ部とを持ち、前
   記Ａ側の１′＝１の１点、もしくは１′＝１−１および
   １の２点と、前記Ｂ側のｊ’−ｊｃ１点、もしくはｊの
   前の点ｊ′およびｊの２点の特徴間の距離の評価Ｍｄを
   演算する手段と；前記ｉ′とｊ′が対応するとき、＋Ｉ
   Ｊ記ｊ’−１，に対応すべきＪ’としてあらかじめ前記
   Ｂのうらの一部を各ｊ′に対して定義する手段と；前記
   １’−１からｉ′への遷移と、同じりｊ′からｊ′への
   遷移との差に関１−る評価量ｒを演算する手段と７備え
   ；第１（１＝１，２゜・・・・・・、Ｉ）段における動
   的計画法による漸化的評価量の演算の際に；前記ｄ、こ
   のｄの計ＩＩＩＫおける前記ｌ′およびｊ′と前記定義
   １−る手段により前記ｊ′九対してあらかじめ定められ
   たｊ′により定まる前記ｒ、および前記ｄおよびｒの計
   ｎにおける（　ｌ’−１，りに関する漸化的評価量ｇ（
   １’−１，ｊ’）、を加算し；前記、Ｚ　ｊＪ、ｊ′ｇ
   の前記手段および定義の範囲忙おける前記加算値の最小
   値を前記ＩＫおける最適対応の漸化的評価量ｇ（ｉ、ｊ
   ）とすることを特徴とするパターンマツチング方法。