JPH0136151B2 - - Google Patents

Description

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

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

２次元図形、音声等のパターン認識において、
パターンから抽出された２つの特徴ベクトルの集
合、 Ａ＝｛A₁、A₂、……、A_I｝ ……(1) Ｂ＝｛B₁、B₂、……、B_J｝ ……(2) の類似性または相違性の度合（以下相違度と呼
ぶ）を評価することは、その中核的な問題であ
る。

例えば、文字認識のためのパターン整合法にお
いては、標準パターン（マスク）の各点Z_i＝（x_i、
y_i）の濃度値の集合Ａ＝｛ｐ（Z_i）｝と、未知入力
パターンの濃度値の集合Ｂ＝｛ｑ（Z_i）｝との重ね
合わせの差 D₁＝（Ａ，Ｂ）＝ 〓^zi ｜ｐ（Z_i）−ｑ（Z_i）｜ ……(3) を相違度とすることにより、入力文字と各文字概
念間の近さの評価が行われる。なお、相関値Σp
（Z_i）・ｑ（Z_i）を類似度に用いたり、この相関値
や第(3)式の値を、ＡとＢの平均濃度で正規化する
場合もあるが、いずれも重ね合わせの量を求める
という意味で基本的な立場は同じである。このパ
ターン整合法は論理が単純であるため、印刷文字
認識の手法として広く用いられてきたが、本質的
に標本点の位置は固定であるとして重ね合せてい
るため、手書き文字のように標本点の位置が変動
する対象に対しては、その適用は困難である。こ
のため、このような対象に対しては、入力とマス
クとの間で特徴の塊の対応づけを行う、いわゆる
構造解析法の立場が必要となる。

この構造解析法の一つとして、特徴が時系列で
ある音声認識の分野においては、標本的（時間
軸）を逐次的に非線形に伸縮させて最適な対応づ
けを行うDP（動的計画法：R.Bellman“Dynamic
Programming”、Princeton University Press、
1957）の形式を用いるものが、マツチングの標準
的な手法として定着している。すなわち、音声の
ように特徴が系列化されている場合、第１図のよ
うに非線形に対応させるための第(1)式および第(2)
式のＡの標本点ｉとＢの標本点ｊの組合せを Ｃ（ｋ）＝（ｉ（ｋ）、ｊ（ｋ）） ……(4) 任意の標本点ｉとｊの特徴間の距離を ｄ（ｃ）＝ｄ（ｉ、ｊ）＝｜A_i−B_j｜ ……(5) とし、標本点ＡとＢの相違度を とそれぞれ定義する。第(6)式は、ＡとＢの対応の
組合せを種々にとり、その中で和が最小なものを
全体の尺度とするものである。ｗ（ｋ）は、シス
テムを柔軟にするために導入された非負の重み係
数である。

ここで、ＡとＢの対応を１対２まで許し、歪Ｃ
＝（ｉ、ｊ）を、Ａ側のみからの関数（ｉ，ｊ
（ｉ））にするという、いわゆる非対称
（Asymmetric）な立場をとり、ｉ点の標本化間
隔（後述の輪郭線分の例では線分長）をl_iとする
と、ｗ（ｋ）＝ｗ（ｉ）＝l_iと書け、D₂を求める問題
は、 ｇ(i、j) ＝minｇ (i‐1、j‐1)＋l_i・d₁（ｉ、ｊ） ｇ (i‐1、j‐2)＋l_i・d₂ (i、j‐1、j) ｇ (i‐2,j‐1)＋（l_i-1＋l_i）・d₃ (i‐1、i、j) ……(7) なる漸化式を、下記のｊ（ｉ）に関する拘束条件
(1)、(2)、(3) (1) ｊ（ｉ）は、連続的な単調増加関数である (2) ｊ(1)＝１、ｊ（Ｉ）Ｊ (3) ｊ（ｉ）の値はｉ付近にある のもとで、順次計算し、第ｉ段での漸化的評価量
ｇ（ｉ、ｊ）を求めるDPの問題に帰着する。最終
的な相違度D₂は D₂（Ａ、Ｂ）＝１／Σl₁ｇ（Ｉ，Ｊ） ……(8) で求められる。すなわち、第(7)式の逐次的な最適
化により、最終的には目的とする第(6)式の大局的
な最適解を第(8)式で求められる相違度D₂として
高速に得ることができる。

なお、等間隔（l_i＝１）の標本化で、特徴間の
距離を d₁（ｉ、ｊ）＝ｄ（ｉ、ｊ） d₂（ｉ、ｊ−１、ｊ）＝（ｄ（ｉ、ｊ−１）＋ｄ
（ｉ、ｊ））／２ d₃（ｉ−１、ｉ、ｊ）＝（ｄ（ｉ−１、ｊ）＋ｄ
（ｉ、ｊ））／２ ……(9) としたものは Ｈ・Sakoe and S.Chiba“Dynamic
programming algorthm optimization for
spoken word recognition”IEEE Transactions
on Acoustics Speech and Signal Processing、
Vol.ASSP―26、NO.1、PP.43―49（1978）に示
されている。

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

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

このように輪郭を線分近似すると、全ての線分
ｉは、ｉの始点を終点とする線分i′を持つが、こ
のi′をｉの直前の線分と呼び i′＝Ｐ（ｉ） ……(10) で表わす。

また、第３図の線分ｉの特徴ベクトル定義図に
示されるように、線分ｉの属性としては、始点お
よび終点座標Z^b _i、Z^o _i、始点から終点への方向a_i、
長さl_iが掲げられ、それぞれ下記のように定義さ
れる。

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

Ｑ（ｉ）＝｛i′｜条件１かつ条件２かつ条件３を
満足する｝ ……(12) 条件(1)：｜Z^b _i−Z^o _i′｜≦δ（例えば３） 条件(2)：｜Z^b _i−Z^o _i′｜≦β（例えば32） または｜a_i〜a_i′｜＞π／２ または（Z^b _i−Z^o _i′）・（Z^o _i−Z^b _i′）≧０ 条件(3)：｜Z^b _i−Z^o _i′｜｜Z^b _i−Z^o _p（1′）｜ かつ、｜Z^b _i−Z^o _i′｜｜Z^b _i−Z^o _i″｜、i′＝Ｐ（i″
） すなわち、条件(1)、(2)は第３図において斜線の
内部に終点がくる線分、あるいは、半径βの円内
に終点があり角度差がπ／２以上の線分を意味す
る。ただし、ベクトルに対する絶対値の定義第(11)
式から実際は円ではなく菱形（正方形を45゜回転
させたもの）である。条件(3)は、上記条件(1)、(2)
の線分のうち、前後でｉとの距離が極小になるも
のだけを残すことを意味する。

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

以上の定義のもとで、マスク側の特徴Ａ＝｛A_i｝
と入力側の特徴Ｂ＝｛B_j｝のDPによる対応づけを
考えるが、最初に、マスク側の特徴｛A_i｝に系列
を与える。これには前述の輪郭線分の順序をその
まま利用する。

次に、入力側も追跡の順という意味では系列化
されているが、マスク側との対応づけにこの系列
をそのまま用いることはできない。それは、第２
図ｂに示されるように、線に切れが生ずると、輪
郭の系列が変化してしまう（線分１〜14で示す）。
この現象は、特に手書漢字のように多数の“画”
から構成される文字の場合、ある画の開始点や終
了点との他の線との間で起き易い。例えば、手書
漢字の“田”の場合、標準的には線によつて区切
られる白地の数（ループ数）は４と考えられる
が、現在標準的な実験用データベースとして用い
られる電子技術総合研究手書教育漢字データベー
スETL８の解析によれば、ループ数は０〜４ま
でほゞ平均的に分布することが報告されている。

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

〔発明の目的〕

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

〔発明の概要〕

この発明は、上記の目的を達成するため、下記
(1)、(2)、(3)の機能を有するパターンマツチング方
式である。

(1) 入力側、マスク側双方共、白と黒の境界部の
直線近似（輪郭線分）を用いることにより、細
線化図形に比べ情報の歪みを少なくすると共
に、原図形に比べ対応候補点を減少させる。輪
郭線分の方向性を距離評価に用いることによ
り、評価関数の精度向上を図る。

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

(3) 単に輪郭線分間の距離だけでなく前後の輪郭
線分のつながり方も評価することにより、重ね
合せの量だけでなく、空間を非線形に歪ませた
時の歪み量も評価に入れる。

〔発明の原理〕

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

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

以上の準備のもとで、上記第(7)式に相当する漸
化式を、 ｇ（ｉ、ｊ）＝min｛h₁（ｉ、ｊ），h₂（ｉ、ｊ），
h₃（ｉ、ｊ）｝ ……（13） と表現する。第（13）式のh₁，h₂，h₃は第４図の
マスク線分ｉと入力線分ｊとの対応図に示される
ａ，ｂ，ｃの対応評価量であり、ａは１対１（ｉ
＝i′対ｊ＝j′）、ｂは１対２（ｉ＝i′対j′＝ｊ−１
，
ｊ），ｃは２対１（i′＝ｉ−１、ｉ対j′＝ｊ）を、
また、Ｍはマスク、Ｎは入力を示す。

こゝで、第(7)式のminの中の第１項と、第
（14）式のh₁を求める式を比較してみると、相違
の第１点は、第（14）式でh₁を求める場合、j″∈
Ｑ（j′）に対してのmin（最小化）処理が行われて
いる。これに対し、第(7)式ではj″＝ｊ−１に対す
る計算項はただ１つである点である。これは、１
次元に系列化されている場合は、ｉ−１の次に
ｉ，ｊ−１の次にｊが生起することが保障されて
いるために、ｉにｊが対応する時、ｉ−１に対応
する相手をｊ−１だけにすればよいためである。

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

相違の第２点は、γの項が存在する点である、
第(7)式では対応づけられた特徴間の距離は評価さ
れているが、Ｃ＝（ｉ、ｊ）の歪に関する評価は
行われていない。Ｃ＝（ｉ、ｊ）を歪ませた結果、
完全に合致するにしても、歪の量が多ければ評価
は下がると考えるのが自然である。そこで、各時
点での評価において、マスク側のi′−１からi′へ
の遷移に対応する入力側のj″からj′への遷移の差
の関数γを定義し、この歪み量を特徴間の距離に
加算したものを総合評価値とする。

次に、上記特徴（輪郭部分）間の距離を下記の
ように定義する。

上記第（15）式中の、d₁における記号〜は角度
差の演算で、結果は−πからπの間にあり、係数
２／πは、角度差がπ／２になつた時、単位長の
差と同じ評価量にするための係数である。また、
長さは、２倍までの差を評価０で許容する。d₂、
d₃の場合、上記の距離を長さで比例配分してい
る。

また、γの項については、対応をとる線分（Ａ
側はi′、Ｂ側はj′）の始点と、その一つの前の線
分（Ａ側はi′−１、Ｂ側はj″）の終点の間の位置
関係から歪み量を評価するものであり、 γ（i′−１、i′；j″、j′）＝｜｜ω^b _j′−ω^e _j″
｜−｜Z^b _i′
−Z^e _i′_-1｜｜ ……（16） で定義される。

通常、マスク側線分は連続しているから ｜Z^b _i′−Z^e _i′_-1｜＝０ であるが、ある輪郭から次の輪郭に移る時は０で
ない。

初期条件は、 h₃（ｉ、ｊ）＝∞ ｇ（i′−１、j″）＝０ γ（i′−１、i′、j″、j′）＝０ ｉ＝１ i′＝１ i′＝１ ……（17） とする。

上記第(8)式に相当するマスク側Ａと入力側Ｂの
全体としての最適対応による相違度は、 D₃（Ａ，Ｂ）＝１／Σl_imin ｊ｛ｇ（Ｉ，ｊ）｝ ……（18） で求められる。

このようにして第（18）式で示される相違度
D₃の計算を行うと、系列の順序が変つてしまつ
た入力側に対してもマスク側との対応をとること
ができ、かつ、線の切れの量を考慮に入れた評価
量をDP手法を用いて高速に得ることが出来る。

〔発明の実施例〕

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

同図において、h₁，h₂，h₃はそれぞれ第（14）
式の計算ブロツクである。計算ブロツクh₁に入力
されるデータは、マスク記憶部Ａの特徴a_i，l_i，｜
Z^b _i−Z^e _i-1｜、入力バツフア部Ｂの特徴α_j，λ_j，｜
ω^b _j−ω^e _j″｜、および第ｉ−１段の漸化的評価量ｇ
（ｉ−１、j″），j″∈Ｑ（ｊ）である。ｇ（ｉ−１、
j″）は、一時記憶ブロツクg_-1に貯えられている。
また、計算ブロツクh₂に入力されるデータは、
a_i，l_i，｜Z^b _i−Z^e _i-1｜，α_p(j)，λ_p(j)，α_j，λ_j，
｜ω^b _p(j)−
ω^e _j″｜，j″∈Ｑ（Ｐ（ｊ））およびブロツクg_-1から
のｇ（ｉ−１、j″）である。そして、計算ブロツ
クh₃に入力されるデータは、マスク側のＡの特徴
a_i-1，l_i-1，a_i，l_i，｜Z^b _i-1−Z^e _i-2｜と入力側Ｂの特
徴α_j，λ_j，｜ω^b _j−ω^e _j″｜およびｉ―２段の漸化的
評
価量ｇ（ｉ−２、j″）、j″∈Ｑ（ｊ）であり、ｇ（ｉ
−２、j″）は、一時記憶ブロツクg_-2に貯えられ
ている。

計算ブロツクh₁，h₂，h₃で計算された第（14）
式の値は、第（13）式の最小値計算ブロツク
min₁に送られ、第ｉ段における各ｊとの漸化的
評価量が計算され、一時記憶ブロツクg₀に送られ
第ｉ段の計算が完了する。

次に、第ｉ＋１段の計算の準備として、まず、
g_-1の内容を全てg_-2に送り、その後g₀の内容を全
てg_-1に送る。この段階で記憶ブロツクg_-1にはｇ
（ｉ，ｊ）の値が、記憶ブロツクg_-2にはｇ（ｉ−
１，ｊ）の値が入り、第ｉ＋１段の計算のための
準備を完了する。

以上が、この発明の要部をなすDPによる反復
計算部分に関する動作であるが、処理の全てを説
明するには、第（17）式の初期値設定と、第
（18）式の相違度に関して補足する必要がある。
そこで、第１段から順に説明する。なお、〜
は各処理を示している。そして、〜は繰返し
である。

まず、処理に先立つて、初期値設定ブロツク
INITにより、g_-1の全ての値に零が設定される
。これは第（17）式の第２式に相当する。そし
て最初のマスク線分ｉ＝１に対する計算では、ブ
ロツクh₁，h₂に対し、γの値として零が供給さ
れ、h₃からは∞が出力される。すなわちブロツ
クh₁からは h₁（ｉ、ｊ）＝l₁・d₁（１、ｊ） を出力し、ブロツクh₂からは h₂（ｉ、ｊ）＝l₁・d₂（１、Ｐ（ｊ）、ｊ）が出力
され、その最小値がブロツクmin₁で計算され
る。なお、処理の時、ブロツクh₃から∞が出
力されるのは、h₃の値がmin₁の出力として選ば
れないようにするためである。次に、処理で計
算された各ｊに対する第１段での漸化的評価量ｇ
（１，ｊ）は全てブロツクg₀に送られ記憶され、
第１段の計算が完了し、g_-1がg_-2に送られ、g₀
がg_-1に送られる。

２番目のマスク線分ｉ＝２に対する第２段の計
算においては、ブロツクh₁およびブロツクh₂では
上記の通常の反復計算時の値が計算される。これ
に対し、ブロツクh₃では、まず、第１段に先立つ
てブロツクg_-1に設定された値がブロツクg_-2に移
されてきているためブロツクg_-2の値は全て零で
ある（第（17）式の中段の式）。また第（17）
式の第３式より、γの値も全て零として計算す
る。そして、h₁，h₂，h₃の結果がブロツクmin₁に
送られ、各ｊに対する第２段目の漸化的評価量
ｇ（２、ｊ）が計算され、ブロツクg₀に貯えられ
、第２段の処理を完了し、g_-1からg_-2，g₀か
らg_-1へのデータの移動を経て第３段の準備を
完了する。

第３段以降の反復処理は上記した通りである。
最後に、第Ｉ段でのｇ（Ｉ、ｊ）ｊ＝１〜Ｊが，
，のｊに関する繰返しで計算され、ブロツク
min₂に送られ第（18）式のｊに関する最小値が
求められ、Σl_iで除されて最適対応による全体
の相違度D₃（Ａ、Ｂ）が求められる。

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

(1) 第（14）式では、全ての線分で前との接続が
切断可能として、minの範囲をj″∈Ｑ（j′）とし
ているが、切断される可能性のない点では、
j″＝Ｐ（j′）として計算すれば、第（14）式の最
小化を行う必要がなくなり、計算が高速化され
る。具体的には、第２図ａをマスクと考えた
時、切断の可能性のあるi′＝２、４、９では、
j″∈Ｑ（j′）を用いるが、その他の線分ではj″＝
Ｐ（j′）を用いることを意味する。

(2) 第（14）式、第（15）式において、各線分の
長さl_iを可変長にしたため、l_iの重みが計算式の
中で用いられているが、固定長にするか、また
は線分近似しないで、各輪郭点をそのまゝ用い
るかすれば、長さを考慮する必要がなくなる。

すなわち、第（15）式のd₁，d₂，d₃は第
（９）式で書換えられ、ｄは、 ｄ（ｉ，ｊ）＝２／π｜α_j〜a_i｜ と書け、計算が単純化できる。

(3) 第（13）式、第（14）式を変形すると、 ｇ(i、j) ＝ming′(i、j)＋l_id₁(i、j) g′(i、P(j))＋l_id₂(i、j′、j) g′ (j‐1、j)＋（l_i′＋l_i）d₃(i′、i、j) g′（i′、j′）＝min j″∈Ｑ（j′）｛ｇ（i′−１、j″）＋γ（i′−
１、i′；j″j′）｝ となる。すなわち、第ｉ段と第ｉ−１段の間で、
途中結果としてg′（i′，j′）を計算することにより
γの計算とｄの計算が分離できる。

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

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

〔発明の効果〕

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

【図面の簡単な説明】

第１図は音声のように系列化された特徴ベクト
ル間のDPマツチングの原理説明図、第２図ａ，
ｂはこの発明で用いられる輪郭線分特徴と線の切
れにより線分の系列が変化することを説明するた
めの図、第３図は輪郭線分の特徴とその輪郭線分
に“先行可能”な輪郭線分の説明図、第４図ａ，
ｂ，ｃはこの発明のDPマツチングの各段におけ
る動作を説明するための図、第５図はこの発明の
一施例のマツチングの手順を説明するためのブロ
ツク図である。 図中、Ｍはマスク、Ｎは入力、h₁，h₂，h₃は計
算ブロツク、g₀，g_-1，g_-2は漸化的評価量の一時
記憶ブロツク、INITは初期値設定ブロツク、
min₁，min₂は最小値計算ブロツクである。

Claims (1)

【特許請求の範囲】
1. １ 標準パターンの特徴の集合Ａ＝｛A₁、A₂、…
   …A_i、……、A_I｝を記憶するマスク記憶部と、
   未知入力パターンの特徴の集合Ｂ＝｛B₁、B₂、…
   …B_j、……、B_J｝を保持する入力バツフア部と
   を持ち、前記Ａ側のi′＝ｉの１点、もしくはi′＝
   ｉ−１およびｉの２点と、前記Ｂ側のj′＝ｊの１
   点、もしくはｊの前の点j′およびｊの２点の特徴
   間の距離の評価量ｄを演算する手段と；前記i′と
   j′が対応するとき、前記i′−１に対応すべきj″とし
   てあらかじめ前記Ｂのうちの一部を各j′に対して
   定義する手段と；前記i′−１からi′への遷移と、
   同じくj″からj′への遷移との差に関する評価量ｒ
   を演算する手段とを備え；第ｉ（ｉ＝１、２、…
   …、Ｉ）段における動的計画法による漸化的評価
   量の演算の際に；前記ｄ、このｄの計算における
   前記i′およびj′と前記定義する手段により前記j′に
   対してあらかじめ定められたj″により定まる前記
   ｒ、および前記ｄおよびｒの計算における（i′−
   ｉ、j″）に関する漸化的評価量ｇ（i′−１、j″）、
   を加算し；前記i′、j′、j″の前記手段および定義の
   範囲における前記加算値の最小値を前記ｉにおけ
   る最適対応の漸化的評価量ｇ（ｉ、ｊ）とするこ
   とを特徴とするパターンマツチング方法。