1 次元パターンの解析的 DP マッチング
内田誠一†

迫江博昭†

† 九州大学大学院システム情報科学研究院〒 812–8581 福岡市東区箱崎 6–10–1
E-mail: †{uchida,sakoe}@is.kyushu-u.ac.jp
あらまし パターン認識・画像処理において多用される弾性マッチング手法に動的計画法によるマッチング，いわゆる DP マッチングがある．DP マッチングは離散化された最適化問題の幅優先探索に基づく解法であり，従って探索の幅が非常に大きくなる問題に対しては適用困難であった．この問題を解決すべく本論文では解析的 DP マッチングを提案する．本手法では，マッチングの評価に用いられる局所的な誤差関数を 2 次関数近似表現することで，幅優先探索なしに厳密解を解析的に与えることができる．本論文では 1 次元パターンに対するマッチングアルゴリズムを導出し，さらに実際の問題に適用し得ることをオンライン文字データを用いて実験的に検証する．
キーワード

動的計画法，DP マッチング，解析的解法，オンライン文字認識

Analytical DP Matching for One-Dimensional PatternSeiichi UCHIDA† and Hiroaki SAKOE†† Faculty of Information Science and Electrical Engineering, Kyushu University
Hakozaki 6–10–1, Higashi-ku, Fukuoka-shi, 812–8581 Japan
E-mail: †{uchida,sakoe}@is.kyushu-u.ac.jp
Abstract DP (dynamic programming) matching is one of the most fundamental techniques for various problemsof pattern recognition and image processing. In this paper a novel DP matching algorithm, called analytical DPmatching, is proposed. Conventional DP matching is organized as a breadth-ﬁrst search algorithm. Thus, its computational complexity depends on the search width. In contrast, analytical DP matching has a diﬀerent organization;
speciﬁcally, it is an analytical solution method and can provide optimal matching with computational complexity
which does not depend on the search width. The derivation of the algorithm and performance evaluation results
are discussed in this paper.
Key words dynamic programming, DP matching, analytical solution, on-line character recognition

1. ま え が き求まる．この計算量の少なさが，DP マッチングが広く利用されてきたことの一つの理由でもある．

動的計画法に基づくパターンマッチング法 — DP マッチン

しかし，このことは I や J が非常に大きな問題には DP マッグ — は，音声パターンの非線形対応付け (弾性マッチング) をチングを事実上適用できないことを意味する．例えば，2 次元目的として 1970 年代に開発された [1]〜[3]．その後応用範囲はパターンの弾性マッチング問題を DP で解く場合，J は画像の広がり，今ではパターン認識・画像処理における基本的道具のサイズ (画素数) に対して指数的に増加する [5], [6]．このためこ一つとなっている [4]．特に，音声をはじめとする 1 次元時系列れまで 2 次元パターンの弾性マッチング問題を DP で解く場合，パターン (オンライン文字パターン，ジェスチャパターン) の弾マッチング自由度の部分的な制約や，ビームサーチなどの近似性マッチング問題に対しては，ほとんどすべての場合において解法が援用されてきた．

DP マッチング (もしくはその確率的拡張である HMM) が適用されていると言っても過言ではない．

本論文では，従来扱いにくかった問題にも適用し得る新しいDP マッチングアルゴリズム — 解析的 DP マッチング — を

この DP マッチングの特徴は，長さ I と J の 2 つの 1 次元提案する．本手法では，原問題を一部連続近似して微分可能とパターンに対し，それらの大局的に最適な非線形対応付けをなるように工夫する．その結果，最適対応付けが微分に基づいO(IJ) の計算量で求める点にある．オンライン文字パターンをて解析的に計算できるようになり，さらにその計算量は J に依例にすると，パターン長は文字パターンを表現する筆点数に相存しない．本論文では 1 次元パターンを対象とした解析的 DP当し，高々10∼100 程度である．従って非常に高速に最適解がマッチングアルゴリズムを導出し，さらに実際の問題に適用し

J

con
tinu
ous

(a)

discrete

J(a)

j=ui

1

1i-1i

1

I

discrete

j=ui

local
dist.
di(j)

1i-1i

discreteI

1i-1i

discrete

I

local
dist.
di(j)

(b)

(b)
1i-1iIdiscrete

図 1 従来の DP マッチング．(a) 最適経路探索空間としてのトレリス．

図 2 解析的 DP マッチング．(a) 最適経路探索空間．(b) 局所距離．

(b) 局所距離．

第 1 項は局所距離の累積値である．また，第 2 項 (ui − ui−1 )2得ることをオンライン文字データを用いて実験的に検証する．

は対応付けの連続性評価項であり，λ は重み係数である（注 1）．境

2. 従来の DP マッチング

界条件として，u1 = 1, uI = J を仮定する．以下では，F を2 つの 1 次元パターン X = x1 , x2 , . . . , xi , . . . , xI , Y =仮定されることの多い単調性 ui−1 <= ui は保証されない．

y1 , y2 , . . . , yj , . . . , yJ 間の弾性マッチングを考える．ここで xiと yj は特徴ベクトルである．弾性マッチングは，X の第 i 要最小化する ui を ui と表記する．なお，この定式化では，従来

3. 2 局所距離の関数近似表現
本 手 法 で は ，最 適 化 に 先 立 ち ，第 i 段 で の 局 所 距 離

素 xi と Y の第 j 要素 yj との対応付け j = ui (i = 1, . . . , I)di (1), . . . , di (j), . . . , di (J) を次のように 2 次関数で近似表現を最適化する問題である．

しておく．

従来の DP マッチング (以下，従来法) でこの最適化問題を解く場合，図 1(a) のような I × J 個の格子点を持つトレリスを考える．これを I 段 J 状態の多段決定過程 [7] と見なす．そして各状態 j での局所的な経路選択を i = 1 から I まで順に繰り返すことで，最終的にトレリス上の最適経路 u1 , . . . , ui , . . . , uIとして 2 パターン間の最適弾性マッチングを求める．この最適経路はマッチングパスや歪み関数とも呼ばれる．以上の処理は探索幅 J ，深さ I の幅優先探索と見ることもでき，従って計算量は O(IJ) となる．

di (j) = αi j 2 + βi j + γi(3)すなわち各 i で 1 つの 2 次関数を定義し，そのパラメータαi , βi , γi をあらかじめ定めておくことになる．従来法では局所距離 (1) が整数格子点 (i, j) において離散的に定義されていたのに対し，解析的 DP マッチングにおいては，非整数の j においても di (j) が与えられることになる．従って，(2) の最小化において ui が整数値である必要がなくなる．
図 2 は解析的 DP マッチングの概要を表したものである．上経 路 す な わ ち マッチ ン グ は ，各格 子 点 (i, j) の局 所 距 離(図 1(b))

述のように，局所距離は 2 次関数として各 i 毎に定義される．
本手法の目的は，連続性評価項 (ui − ui−1 )2 に配慮しながら，di (j) = |xi − yj |(1)

なるべくこの 2 次関数の頂点に近いところを通過するようなマッチングパスを求めることになる．従来法 (図 1) においてこを，その経路が通過する格子点 (i, ui ) について累積した値

Ii=1

di (ui ) により評価される．局所距離は局所的なマッチング誤差，すなわち対応付けられる 2 つの特徴ベクトルの差異であり，その累積値は X と Y 全体でのマッチング距離となる．

析的 DP マッチングにおいては，上述の通り j および ui は実数であり，整数格子点を通過する必要はない．
局所距離を 2 次関数近似する場合，下に凸なものに限定する必要がある (すなわち αi >= 0)．上に凸の 2 次関数を用いると，

3. 解析的 DP マッチング

j = ui が ±∞ に近づくことで di (j) の値はいくらでも小さく

3. 1 問題の定式化
解析的 DP マッチングは次の目的関数の最小化問題として定式化される．

F (u1 , . . . , uI ) =のパスは整数格子点 (i, j) を通過する必要があった．一方，解なり，結果的に ui = ±∞ となり不都合である．
（注 1）：単調増加性に配慮し，連続性評価項を (ui − ui−1 − 1)2 と定義してIi=1di (ui ) +I
i=2もよい．ただし，u1 = 1, uI = J という境界条件の下では，実質的にはλ(ui − ui−1 )2(2)(ui − ui−1 )2 との差はほとんどない．実際，後述する認識実験において両者に大きな差異は認められなかった．

上式は DP 漸化式 (もしくは関数方程式，関数再帰方程式) とInput:呼ばれ，i に関する再帰的関係を表現している．

Coeﬃcients of local distance funcitons:{αi , βi , γi | i = 1, . . . , I}

従来法では，この DP 漸化式に基づいた幅優先探索を行なう．
すなわち，ui−1 を整数とし，各 ui−1 ∈ [1, 2, . . . , J] について

Boundary condition: u1 = 1, uI = J
Weight: λ ∈ R+fi (ui−1 ) の値を求め，テーブル化しておく．そして次に，このOutput:fi (ui−1 ) の値を用いながら，やはり J 通りの ui−2 について，

Optimal correspondence: {ui ∈ R | i = 1, . . . , I}

fi−1 (ui−2 ) の値を求め，テーブル化する．この処理を i = I かMinimum distance min F

ら 1 まで (逆も可) 続けることで，最小値 f2 (u1 ) を求めること

Step 1: Initial conditionになる．これに対し本手法では，このような幅優先探索は行な
aI = λわず，微分により最適な ui = ui を ui−1 により一意的かつ解bI = −2λuI析的に求める．以下にその詳細を述べる．

cI = dI (uI ) + λu2I

3. 4 解析的解法
関数 fi (ui−1 ) は，その 2 次関数的性質から，変数 ai , bi , ci を

Step 2: DP recursion

用いて

for i = I − 1 downto 2 doai =λ(αi + ai+1 )αi + λ + ai+1bi =λ(βi + bi+1 )αi + λ + ai+1ci = −fi (ui−1 ) = ai u2i−1 + bi ui−1 + ciと書ける．この正当性については付録 1. で証明する．上式 (8)を (7) の右辺に代入すると，(βi + bi+1 )2+ γi + ci+14(αi + λ + ai+1 )fi (ui−1 ) = min αi u2i + βi ui + γi + λ(ui − ui−1 )2ui

Step 3: Terminaiton+ ai+1 u2i + bi+1 ui + ci+1min F = d1 (u1 ) + a2 u21 + b2 u1 + c2for i = 2 to I − 1 doui =λβi + bi+1ui−1 −αi + λ + ai+12(αi + λ + ai+1 )λβi + bi+1ui−1 −αi + λ + ai+12(αi + λ + ai+1 )fi (ui−1 ) =3. 3 DP 漸化式

F (u1 , . . . , uI ) = d1 (u1 )

(4)

ai

=

λ(αi + ai+1 )αi + λ + ai+1bi=

λ(βi + bi+1 )αi + λ + ai+1ci=−i=2Angel [8] に従い，ここで次のような関数を考える．
fi (ui−1 )minui ,...,uI−1(βi + bi+1 )2+ γi + ci+14(αi + λ + ai+1 )I (βi + bi+1 )2+ γi + ci+14(αi + λ + ai+1 )⎫⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎭

αk u2k + βk uk + γk + λ(uk − uk−1 )2 (5)k=i算する方法を与えている．
この逐次計算の開始値 (aI , bI , cI ) は，(5) 式において i = Iとすることで求まる．すなわち，

min F = d1 (u1 ) + f2 (u1 )(6)fI (uI−1 ) = αI u2I + βI uI + γI + λ(uI − uI−1 )2= λu2I−1 − 2λuI uI−1 + dI (uI ) + λu2Iとなる．
これと，(8) において i = I とした

最適性の原理から (5) は次のように表せる．

= min αi u2i + βi ui + γi + λ(ui − ui−1 )2 + fi+1 (ui ) (7)ui(12)となる．上式 (12) は，ai+1 , bi+1 , ci+1 から ai , bi , ci を逐次計

この定義より，F の最小値はfi (ui−1 )(11)が得られる．この (11) と (8) の比較により，は以下のように書き換えられる．

=λ(αi + ai+1 ) 2λ(βi + bi+1 )
ui−1 +ui−1αi + λ + ai+1αi + λ + ai+1−

前節で与えた局所距離の 2 次関数表現により，目的関数 (2)αi u2i + βi ui + γi + λ(ui − ui−1 )2(10)

この ui = ui を (9) に代入して整理すると，

図 3 解析的 DP マッチングのアルゴリズム

I


(9)

∂Q/∂ui = 0 を満たす必要がある．これを解いて，

u1 = u1 = 1+となる．右辺 [ ] 内を Q とおくと，Q を最小にする ui = ui は，Step 4: Backtrack

ui =(8)fI (uI−1 ) = aI u2I−1 + bI uI−1 + cIを比較することで，次のように (aI , bI , cI ) が求まる．

di(j)

approx.

λ=1000Ωiorig.
||xi-yj||10010

図50j

局所距離の 2 次関数近似

X(input):"0"Y(ref.): "0"

1ww~
j iJ/I

X: "0"
Y: "2"

X: "0"
Y: "3"

(a)

ji
図4aI

=λbI

=−2λuI=dI (uI ) + λu2IcI(b)シミュレーション実験の結果

⎫⎪
⎬
⎪
⎭

(13)

以上により，(4) の最適化問題が解けたことになる．すなわ
ち，(13) の後に (12) を反復適用することで a2 , b2 , c2 を求め，(c)ji

さらにそれを (6) に代入することで，目的関数の最小値
図 6 3 組のオンライン文字データの解析的 DP マッチング結果．(a)min F = d1 (u1 ) + f2 (u1 )= d1 (u1 ) + a2 u21 + b2 u1 + c2

真の局所距離．(b)2 次関数近似した局所距離．(c)(b) 上にマッ(14)が求まる．また，X と Y 間の最適対応 ui = ui については，境界条件 u1 ならびに (10) から求まる．
図 3 はこうして導出された解析的 DP マッチングのアルゴリズムである．注意すべきは，このアルゴリズムで求まるのは，目的関数 (4) の大局的最適解であるという点である．すなわち，目的関数を (2) から (4) に書き換える時点で局所距離 di (j) の2 次関数近似が行なわれているが，その後の計算過程において一切近似は無く，(4) の厳密な最適解を求めている．

4. 実

験

4. 1 シミュレーション実験
図 4 は，人工的に生成した局所距離 di (j) に対して解析的 DPマッチングを行なった結果である．同図は各 (i, j) での di (j) の値を表した濃淡画像の上に，マッチングパス u1 , . . . , ui , . . . , uIを黒い点列として表したものである．濃淡画像の各画素は白いほど di (j) の値が小さいことを意味する．
まず λ = 0 の場合，連続性評価項が無くなるため，パスは各i で常に di (j) の極小点を通過し，不連続なものとなっている．
一方，λ が大きくなると，連続性評価項が支配的になるため，パスは直線的になっている．その中間の λ では，di (j) の極小点付近を滑らかに通過できていることがわかる．

チングパスを重畳したもの．

4. 2 オンライン文字認識
解析的 DP マッチングの実パターンへの応用可能性を示すことを目的として，オンライン文字認識実験を行なった．Ethem

Alpaydin Digit [9] のオンライン孤立数字データセット (全 10文字種) のうち，テストパターン全 3498 サンプルを認識対象 Xとした．各テストパターンについて，1 画化，線形正規化ならびにリサンプリングを行った．また手動で合計 21 個 (各文字種に 1∼4 個) の標準パターン Y を準備した．各入力パターン Xと標準パターン Y について解析的 DP マッチングを行い，得られた min F に基づく最短距離識別を行なった．

4. 2. 1 局所距離の 2 次関数近似
局所距離 di (j) を 2 次関数近似する際，オンライン文字認識という問題の性質を考慮した．すなわち，正解標準パターンとのマッチングにおいては，X ∼ Y であるため，マッチングパスは直線的になるべき，すなわち ui が区間 Ωi = [iJ/I −w, iJ/I +w]内に存在するべきと考えた．ここで w は区間幅を表す正定数である．この考えに基づき，区間 Ωi 内の真の (すなわち 2 次関数近似前の) 局所距離値 xi − yj  を重視して，2 次関数 di (j) を定めることにした．
具体的には，図 5 に示す方法で各 i の 2 次関数 di (j) を決定した．まず Ωi の両境界点および Ωi 内で最小の局所距離を持の下，この長さを 10 から 10000 まで変えながら，1 回のマッcomputation time (ms)104

チングに要する平均計算時間を計測した．プログラムは C 言語

103102で実装され，1.7GHz CPU 搭載の計算機上で実行された．

conventional DP matching

結果を図 7 に示す．比較を容易にするために，本図の計算時101間には局所距離の計算時間を含めていない．これは，4. 2. 1 の1002 次関数近似を採用する場合，w = W ならば局所距離計算に10-1要する時間は両マッチング法でほぼ同じ (O(IW ) = O(Iw)) と10-3なるためである．また，従来法については整合窓を用いていな

analytical DP matching

10-2

い場合 (すなわち W = J) の計算時間を示している．従来法で
10100

1000

10000

pattern length (= I = J)は整合窓を用いることで計算量を W/J = W/I 倍に低減できる．ただし，多くの場合 W = 0.1I 程度が最小幅であり，従っ

図 7 計算時間の比較て整合窓による計算量低減効果は高々1/10 程度である．
図 7 より，本手法の計算量的優位性がわかる．ただし，上述

つ点 j̃ の合計 3 点を決める．次にそれら 3 点で真の局所距離値のように整合窓を用いることで従来法の計算量を 1/10 にできxi − yj  を持つ 2 次関数 di (j)，すなわち αi , βi , γi を求めた．

ることを考えると，I = J ∼ 100 程度までならば，両手法に大2 次関数近似のパラメータ w は，従来法の整合窓と同じく実験きな計算量の差は無いと言える．しかしながら，それ以上のパ的に定められるべき性質のものである．本実験では 3 とした．

ターン長では，J 状態の幅優先探索を行なう必要がある従来法

4. 2. 2 マッチング結果に比べ，その必要のない本手法のほうが格段に少ない計算量で

図 6 に本手法による 3 組のオンライン文字パターンのマッチ済むことがわかる．このように 1 次元パターンのマッチング問ング結果を示す．連続性評価項の重み λ は，実験的に 10 とし題においても本手法の計算量的優位性が実証されたことは，状た．正解標準パターンとのマッチング (同図左列) では，(i, j)-態数が指数的に増加する 2 次元パターンのマッチング問題に対平面の対角線付近に 2 次関数近似された局所距離の鋭いピークして，本手法がさらに有力な解法となりうることを示唆してい(白に近い領域) が現れている．最適化されたマッチングパスはる．なお，局所距離計算 (本手法の場合 {αi , βi , γi } の決定) をこのピーク付近を滑らかに通過していることがわかる．

除外した場合，本手法および従来法の計算量はそれぞれ O(I)

不正解標準パターンとのマッチング (同図中央および右列)でも同様にピーク付近を通過する滑らかなパスが求まっていと O(IJ) = O(I 2 ) であり，図 7 のグラフの傾きの差異を裏付けている．

る．ただし，ピークは鋭くなく，従ってパス通過点での局所距離 di (ui ) は比較的大きな値となっている．結果的に min J も大5. 議

論きくなるので，不正解標準パターンが認識結果として選出され5. 1 解析解法としての DPにくくなることがわかる．

DP の本質はその再帰的計算過程にあり，それは従来法のよ4. 2. 3 認 識 率

うな離散的な問題だけでなく，本手法のような連続的な問題に全テストサンプルに対する解析的 DP マッチングの認識率も適用しうるものである [10]．しかしながら，ディジタル化さは 93.5%であった．これに対し，線形伸縮マッチング (すなわれた対象が多いパターン認識・画像処理の分野において，DP は

ち λ = ∞) による認識率は 91.1%であった．このことから，解主として離散化された問題に適用されてきた．実際，連続的な析的 DP マッチングの実問題への有効性が確認できる．また，問題に対して DP に基づく解析的解法を与えた例は，1 次元おλ = 0 とした場合，すなわち ui が 2 次関数のピーク位置に一よび 2 次元データの最適補間問題への適用例 [8] 程度と少ない．

致する場合の認識率は 92.8%であった．このことから，連続性5. 2 マッチングにおける関数近似評価項の必要性がわかる．

マッチング問題を解析的 DP で解くために，本手法では局所比較のため従来法によるオンライン文字認識も行なった．重

距離を 2 次関数近似する．この考え方は Etoh [11] に着想を得

み λ は 0 とし，単調連続性条件 ui − ui−1 ∈ {0, 1, 2} によりている．同文献では，2 画像のアフィン変換マッチング問題をパスを直接制約した．また整合窓すなわち条件 i − ui  <=W

局所距離の 2 次関数近似により解析的に解く手法を提案していによる制約も併用した．その結果，整合窓幅 W = 5 の時に最る．局所距離すなわちマッチング誤差ではなく，パターンその高認識率 94.5%を得た．本手法の認識率のほうがやや低いが，ものを関数近似する試みもある [12], [13]．例えば大町らは [12]

厳密な単調連続性条件下での従来法と大きな差が無かったこと

パターンを多項式近似することで，線形伸縮を含むマッチングは，本手法で求まったマッチングパスが多くの場合良好なもの問題を効率的に解く方法を提案している．このように関数近似であったことを示唆している．の導入自体には従来より検討例があるが，対象としている問題

4. 3 計 算 時 間が非線形な弾性マッチングである点と，解法に DP を用いる点

解析的 DP マッチングおよび従来法により，2 つの 1 次元パで，本手法と従来の試みとは大きく異なっている．

ターン X , Y をマッチングするための時間を実測した．具体的

5. 3 連立解法との関係には，両パターンの長さは同じ (すなわち，I = J) という条件

目的関数 F の最小化問題は，解析的 DP 以外の方法でも解くことができる．すなわち，(4) で与えられる目的関数 F の極論文の議論を発展させ，指数関数的な状態数を要する 2 次元パ値条件 ∂F/∂ui = 0 を u1 , . . . , uI−1 について連立し，得られたターンの弾性マッチング問題を解析的 DP マッチングにより解(I − 1) 元一次連立方程式を解くという方法 (以下，連立解法とく予定である．また，5. 4 で述べたような，本手法を直接適用呼ぶ) が考えられる．詳細は略すが，この場合の連立方程式のし得る各種の正則化問題についても検討する予定である．
文

係数行列は 3 重対角になる．従って逆行列を求めることなく逐次代入処理で解くことができる [14]．

1 次元パターンを対象とすれば，連立解法と本手法の計算量はほぼ同じである．しかし 2 次元的な問題への拡張を考えた場合，両者の違いは顕著になる．すなわち，変数 ui が ui1 ,i2 のように 2 次元化し，さらに ui1 ,i2 が連続性評価等により近傍の変数 ui1 ±1,i2 ±1 と互いに影響するような場合，連立解法はもはや 3 重対角行列には基づかず，決定論的弛緩法 [15] に見られるような大規模な行列に基づくことになろう．一方，解析的 DPには，Angel [8] の例のように，問題のマルコフ性を活かして，ui1 ,i2 を i1 毎にまとめたカラムワイズな処理 (すなわち 2 次元パターンを列ベクトルの 1 次元系列と見なした処理) が適用できる．その結果大規模な逆行列計算が不要な最適化過程を実現できるものと考えられる．

5. 4 局所距離が本質的に 2 次関数となる場合以上では一貫して，解析的 DP マッチングを従来法の近似解法として扱ってきた．しかしながら，目的関数が元々(4) の形式で書ける問題，すなわち局所距離 di (j) が本質的に 2 次関数となる問題に対しては，本手法はもはや近似解法ではなく，その大局的最適解を与える有力な手法となる．例えば，2 パターン間に予め与えらた幾つかのラフな対応関係を最適補間する問題としてマッチング問題が定式化された場合，まさに (4) の形式の目的関数が直接導出され，本手法はその解法となる．
ところでこの補間問題は標準正則化理論 [15] に基づく一種の曲線当てはめの問題 (マッチングパスが曲線に相当) と等価である．この事実は，本手法が正則化理論に基づく様々な問題に適用可能なことを示唆する．すなわち，マッチング問題に限らずとも，事前知識によりペナルティ項が 2 次関数の和として定式

献[1] 迫江博昭, 千葉成美, “動的計画法を利用した音声の時間正規化に基づく連続音声認識,” 日本音響学会誌, vol. 27, no. 9,
pp. 483-490, 1971.
[2] H. Sakoe and S. Chiba, “A dynamic programming algorithm
optimization for spoken word recognition,” IEEE Trans.
Acoust. Speech and Sinal Proc., vol. ASSP-26, no. 1, pp. 4349, 1978.
[3] H. Sakoe, “Two-level DP-matching algorithm—a dynamicprogramming based pattern matching algorithm for continuous speech recognition,” IEEE Trans. Acoust. Speech andSinal Proc., vol. ASSP-27, no. 6, pp. 588-595, 1979.
[4] 大田友一, 山田博三, “動的計画法によるパターンマッチング,”
情報処理, vol. 30, no. 9, pp. 1058–1066, 1989.
[5] 内田誠一, 迫江博昭, “動的計画法に基づく単調連続 2 次元ワープ法の検討,” 信学論, vol. J81-D-II, no. 6, pp. 1251-1258, 1998.
[6] D. Keysers and W. Unger, “Elastic image matching is NPcomplete,” Pattern Recog. Lett., vol. 24, no. 1-3, pp. 445–453, 2003.
[7] 茨木俊秀, 組合せ最適化の理論, 電子情報通信学会, 1979.
[8] E. Angel, “Dynamic programming for noncausal problems,” IEEE Trans. Automatic Control, vol. AC-26, no. 5,pp. 1041-1047, 1981.
[9] ftp://ftp.ics.uci.edu/pub/machine-learning-databases/pendigits/[10] 鍋島一郎, 動的計画法, 数学ライブラリー 7, 森北出版, 1968.
[11] M. Etoh, “Promotion of block matching: parametricreprsentation for motion estimation,” Proc. ICPR, vol. 1of 2, pp. 282–285, 1998.
[12] 大町方子, 大町真一郎, 齋藤恒雄, “関数を用いた認識のためのパターン表現法,” 信学技報, PRMU2005-84, 2005.
[13] J. Kybic and M. Unser, “Fast parametric elastic imageregistration,” IEEE Trans. Image Proc., vol. 12, no. 11,pp. 1427–1442, 2003.
[14] J.R.Westlake 著, 戸川隼人訳, コンピュータのための線形計算
ハンドブック，培風館, 1972.
[15] 坂上勝彦, 横矢直和, “弛緩法と正則化,” 情報処理, vol. 30, no. 9,pp. 1047–1057, 1989.

化されるような正則化問題であれば，本手法と同様の考え方に付よりその大局的最適解を効率よく求めることができる．

6. む す び録

1. 式 (8) の妥当性
ここでは式 (8) のように fi (ui−1 ) が常に ui−1 に関する 2 次

解析的 DP マッチングを提案した．本手法は，幅優先探索に基づく従来の DP マッチングとは異なり，DP の解析的解法としての側面を利用した方法になっている．この解析的解法を可能としたのは，局所距離を 2 次関数近似し，それに応じて状態を連続化することで，これまでのような有限個の状態を個々に考える必要を無くしたためである．従って，従来の DP マッチングでは困難であった状態が非常に多い問題に対して本手法は式で表現できることを帰納法で証明する．まず i = I の時，fi (ui−1 ) の定義 (5) からfI (uI−1 ) = αI u2I + βI uI + γI + λ(uI − uI−1 )2であり，右辺は uI−1 に関する 2 次式となっている．
次に i + 1 (i < I) の時に成り立つと仮定して，i の時も成り立つことを示す．この仮定は fi+1 (ui ) が特に有効と思われる．本論文では 1 次元パターン間の弾性マッチング問題を用いて，本手法の基本的なアルゴリズムの導出をおこなった．また，オンライン文字パターンのマッチングを行なうことで，実際の問題に応用可能であることを示した．

1. でも述べたように，1 次元パターンの弾性マッチング問題
では状態はそう多くならない．従って本手法の計算量的な利点を示すのには不十分と考えている．今後は，[8] 等を参考に，本fi+1 (ui ) = ai+1 u2i + bi+1 ui + ci+1と表現できることを意味する．この式を (7) の右辺に代入すると，(9) が得られる．従って結局 fi (ui−1 ) は (11) に帰着し，これは ui−1 に関する 2 次式になっている．以上より，証明終．