動的計画法に基づく単調連続2次元ワープ法に関する 研究

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

動的計画法に基づく単調連続2次元ワープ法に関する 研究

内田, 誠一

九州大学システム情報知能システム工学

https://doi.org/10.11501/3150878

出版情報：Kyushu University, 1998, 博士（工学）, 課程博士 バージョン：

権利関係：

‑︽

o a ω R o s v

n 二 山 ω 一 ︒

。 z a

嬰・ 鍵園 田吋 吋霊 一 TP Ha s‑

両

: t  

盟国』

M 

ω 

4

 

切

。

雲

、

ー園晶4

‑ι 

∞ 

̲"， 

c o  

動的計画法に基づく単調連続 2 次元ワープ法に関する研究

内田誠 一

1 9 9 9 年 1 月

目 次

4 4 5 6 i O  

T貝

沖ア

分の法フ

ワ

次 一 冗

つ ﹄

百 て

・

・ ノ

¥

死 一

••

づ

川 一 一 基

't'十l

干

﹂

7 b

穿l

J

方 成 究 法

? の 構 研 画 元 究 の の 計 火 研 文 来 的 ふ 本 論 従 動

会問

4

‑ 1 1 2 3 4 5  

Fト

' 1 1 ム11ム11よ1

﹃ ム 噌

ai

Ti 

2 単調達続2次元ワープ決定問題 12 

2.1 2次元ワープ決定問題の定式化 • • • • • • • • • • • • • • • • . • • • • 12  2.2 単調連続性条件と境界条件.• • • • • • • • • • • • • •• ••• • ••• 13 

3 動的計画法 15 

3.1  動的計画法の概要.• . • • • • • • . . • • • • • • • • • • • • • • • • •• 15 

3 . 2  

多段決定過程 • • • • • • • • • . . • • • • • . • • • • • • • • • • • •

1 7  

3.3  ビームサーチ • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 19 

4 動的計画法による解法 1ーカ ラ ム ワ イ ズD Pアルゴリス‑ム 21  .

J.1 まえがき.• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 21 

.

J.2 列を処理単位とする多段決定過程による問題表現 21 

‑‑1

. 3 

カラムワイズ

DP

アルゴリズム • • • • • • • • • • • • • • • • • • . • •

2 3  

‑‑1..J  計算量の評価 ^{・ ・ ・ ー . . . . .  . .}  25 

4 . 5  

近 似 ア ル ゴ リ ズ ム ーカ ラ ム ワ イ ズ ビ ー ム サ ー チ

DP

アルゴリズム •

2 6  

1 

<

:1:.6  計算量の評価 4.7  まとめ

30  31 

9 結論 77 

謝 辞 79 

5 動的計画法による解法 2‑ピクセルワイズDPアルゴリス、ム 32  5.1  まえがき.• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 32  5.2  画素を処理単位とする多段決定過程による問題表現.• • • • • • • • • 32  5.3  ピクセルワイズDPア ル ゴ リ ズ ム .• • • • • • • • • • • • • • • • • • . 37  5.4  計算量の評価 • • • • • • • • • • • • • • • • • • • • • • • . • • • • • •• 38  5.5  近似アルゴリズムーピクセルワイズビームサーチ DPア ル ゴ リ ズ ム . 39  5.6  計 算 量 の 評 価 .• . • • • • • • • • • • . • • • • • • • • • • • • • • • •• <:1:3 

参考文献 79 

A DP 漸化式の導出

A.1  カラムワイズ DPアルゴリズムが基づく DP漸化式の導出 A.2 ピクセルワイズDPアルゴリズムが基づく DP漸化式の導出

円t Q υ n u n δ o o n u d  

5.7  まとめ ^. j.

A 

6 アルゴリズムの比較 6.1  まえがき.

6.2  DPアルゴリズムの比較

PO

ハハリハOA叫

I f

せtJ1

6.3  ビームサーチ DPアルゴリズムの比較 6.4  まとめ

47  52 

7 不自然なワープの回避 7.1 まえがき.

53  53  7.2 ペ ナ ル テ イ . ・ ー ・ ・ ^{ゐ . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .}  53  7.3 整合窓 チー 一一ー・ ・・ ・・ ・・ ...57 7.4まとめ ー一ゐ .. . . . . . . . . . . . . . . . . . 58 

8 評価実験 59 

8.1  まえがき • • • • • • • • • • • . • • • • . 59 

8.2  単調連続2次元ワープの結果例とその定性的評価 • • • • . • • • • • 59  8.3  変形追従能力の定量的評価 .

8.<:1:  手書きひらがな認識による評価 8.5  まとめ

67  71  i5 

2  ₃ 

第 1 章 序論

1 . 1   2 次元ワープの概要

本論文では， 2画像の最大一致を与える画素問のノンパラメトリックなマッピン グを 2次元ワープと呼ぶ1 2次元ワープは画像中のパターンの変形に適応可能な弾 性マッチング処理と見なすことができる.また一方の画像を，画素をプリミテイブ

とするモデルと考えると 構造解析処理にもなっている.

2次元ワープを決定する問題は一種の最適化問題であり，その定式化には二通り のアプローチがある.第一は，画像を画素の集合と見なし， 2集合の要素問の最適 対応関係を求める組合せ最適化問題

[ 2 ]

，

[ 3 ]

として定式化するものである.多くの組 合せ最適化問題は組合せ爆発の問題を抱えているので

[ 4 ]

，アルゴリズムの検討にあ たっては計算量的考察が重要となる.また場合によっては近似アルゴリズムの検討 も必要となる.第二は，画像を 2次元連続信号と見なし，汎関数を極小(大)化する 変関数を求める変分問題として定式化するものである.この場合，R²から R²への 連続関数として表現される 2次元ワープが変関数であり，画像の一致度を評価する 目的関数が汎関数である.計算機上では，極値の必要条件であるオイラー・ラグラ ンジュ方程式を離散近似したものを反復法により解くことになる.誤差の発生要因 が多いため，解の安定性を保つための配慮が必要となる.

2次元ワープの性質は，ワープによる変形の局所的自由度と，最適性の有無に よって特徴付けられる .2次元ワープの自由度は，ワープに対する制約条件によっ て規定される.このため制約条件は対象画像の変形特性を反映していることが望ま しい.例えば対象の変形がいわゆるゴム膜変形で近似できる場合，位相構造を保存 する制約条件が適している.一方，ワープの最適性の有無はワープの変形適応能力

1事前に与えられた幾つかの画素対応関係を内挿する関数も 2次元ワープと呼ばれている [1].本 論文で扱う 2次元ワープとは，そのような事前知識は用いずにすべての画素対応を自動決定するも

のを指す.

4 

の安定性を左右する.すなわち，最適性が保証されていれば，制約条件を満たす範 囲内で常に最大限の変形適応能力が発揮される.ワープの最適性の有無は前述の定 式化と関連し，そこで用いる最適化手法によって規定される.

1 . 2   本研究の方針

本研究は，以下の基本方針に則しながら，適正な自由度を有し，かつ最適性が保 証される 2次元ワープアルゴリズムの実現，および実用を目指したアルゴリズムの 改良を目的として行なったものである.

(1 )位相構造を保存する一般的なワーフ。モデルの定式化: 画像の位相構造を保存す る範囲での最大の自由度を考え，それに応じた制約条件を使用する. 多くの 場合，対象に非単調な変形や不連続な変形が生じないことを考えると，これは 妥当な方針と言える.対象固有の変形特性を詳細に反映した制約条件の利用は 先の問題とする.

(2)最適ワープを求める DPアルゴリズムの確立: 最適性が保証されたワープを与 えるアルゴリズムの実現は，理論的に興味深いだけでなく，高精度なワープを 志向する意味で実用的にも意義がある.前述のように 2次元ワープ決定問題 には組合わせ最適化問題と変分問題の二つの見方があるが後者では一般に局 所解しか求まらないので，前者の枠組での動的計画法(clynamicprogra.mming  : DP) [5]"'[7]に基づくアルゴリズムを設計することとする.

(3)2次元的自由度を堅持した上で、の効率化: 前項 (2)に従って 2次元ワープ決定 問題を組合わせ最適化問題として扱う場合，前述のように組合せ爆発の問題が 危慎される.実用を目指した計算量の低減には，ワープの自由度に対する制約 を強めることで探索空間を圧縮する方向と 最適ワープが得られる可能性の低 い探索を途中で打ち切る方向が考えられる.本研究ではワープの自由度に直接 影響を与えない後者を基本とする.

υ 「

1 . 3   ^{論文の構成}

本論文は，前節の方針に従い，単調連続性を制約条件とする 2次元ワープについ てDPに基づくアルゴリズムを提案し，その基礎的な検討を行なったもので，9章 より構成される.

本章の残りでは， 2次元ワープに関する従来の研究を概観する.特に DPに基づ くアルゴリズムについては，ワープに対する制約条件とワープの最適性の有無を基 準とした分類を試み，それらの問題点を明らかにする.

第 2章では単調連続性を制約条件とする 2次元ワープの決定問題の定式化を行な う.単調達続性とは隣接画素間の上下左右関係と近傍関係をワープ後も保存するた めの条件であり，これにより画像の位相構造を保存する 2次元ワープが実現される.

第3章では以後の議論の準備として DPの概要を述べる. DP と密接な関係のあ る多段決定過程と， DPアルゴリズムの計算量低減手法であるビームサーチについ ても言及する.

第4章では単調連続2次元ワープ決定問題の最適解を与えるアルゴリズムとして，

カラムワイズDPアルゴリズムを提案する.画像サイズを JVX iVとすると，このア ルゴリズムは画像の列を処理単位とする N段の多段決定過程に基づいている.各列 のワープに単調達続性を保証し，かつ列聞の遷移に単調連続性を保証するため，段 あたり 2入?の指数オーダーの探索 rll~ を持つ計算量的に困難な問題となる. この問題 に対して， DPアルゴリズムにビームサーチを適用した近似アルゴリズムを提案す る.ビームサーチを DPアルゴリズムに組み込むことで最適性の保証はなくなるが，

ワープの 2次元的自由度を保ったまま計算量を多項式オーダーに低減できる.

第5章では最適ワープを与えるもう 一つのアルゴリズムとして，ピクセルワイズ DPアルゴリズムを提案する.このアルゴリズムは各画素のワープをラスタスキャ ンJII買に決定していく iV²段の多段決定過程に基づいている.各段での決定は 2次元 的単調達続性制約により λ7段前の決定に依存する.ピクセルワイズ DPアルゴリズ ムはカラムワイズ DPアルゴリズムを計算量の点で改良したものであるが，この N 次マルコフ性を扱っているために段あたり八'の指数オーダーの探索幅を持つ.この

ため，前章と同様にビームサーチを適用した近似アルゴリズムを提案する.

第6章ではまずカラムワイズ DPアルゴリズムとピクセルワイズ DPアルゴリ ズムの計算量の比較を行なう.次にそれぞれの近似アルゴリズムに関しても計算効 率の実験的および理論的な比較を行う.

第 7章では，単調連続性の局所性やビームサーチの副作用に起因した不自然な ワープを回避する方法として，ペナルティと整合窓の適用を検討する.

第8章ではピクセルワイズビームサーチ DPアルゴリズムを用いた幾つかの実験 により単調連続 2次元ワープの精度の定性的および定量的な評価を行なう.

最後に第 9章では論文のまとめと今後の課題について述べる.

1 . 4   従来の研究

画像の弾性マッチングに関する最初の試みは B.¥Vidrowによるラパーマスク法[8] と言われる.ラパーマスク法では一方の画像を幾つかのパラメータを持つ関数によ り変形し， 最大一致が得られるまでパラメータを繰り返し修正する.このようなパ ラメ トリ ックな弾性マッチングを決定する問題は目的関数の極値問題として最小 2 乗法や勾配法などにより解くことができる.若原による LAT[9]では，ワープ全体

を部分的なアフィン変換に分解して捉え，各領域において最適なアフィン変換のパ ラメータを最小 2乗法により決定する.A.K..Jainらにより提案された clcfonnable t

.ernpla.tes [10]では，調波構造を持つ正弦関数の重ね合わせによってワープを表現し ており，各正弦関数の振幅パラメータを勾配法により求めている.他のパラメトリ ッ クな弾性マッチング法として，アフィン変換のパラメータを少しずつ変化させて生 成した変形画像を予め数多く用意しておく方法 [11]~[13] があり ， 文字認識に応用さ れている.

ノンパラメ トリ ックな弾性マッチング，すなわち 2次元ワープに関しても多くの 研究がなされている.最適化手法をキーとして分類すれば，それらは決定論的弛緩 法 [1~]， [15] などの反復法に基づく方法 [16]~[21]， 摂動法に基づく方法 [22]"， [26]，お よびDPに基づく方法

[ 2 i ]

^{" ，}

[ 3 8 ]

の3種類に大別される.

決定論的弛緩法に基づく方法

[ 1 6 ] " ‑ ' [ 2 0 ]

では変分法の枠組で

2

次元ワープを求め る.計算機上では，オイラー ・ラグランジュ方程式の差分近似により構成される大 型の非線形連立方程式を Gall出‑Seiclcl法などの反復法により解くことになる.過変 形を回避するために，正則化や多重スケールを用いた階層的な解法が用いられる.

これらの万法の欠点は，オイラー・ラグランジュ方程式が最適解の必要条件である ために，たとえ反復計算が収束しでも一般に局所解しか得られない点である.また ワープが実数値関数として扱われるために，計算途中で整数座標以外の点の輝度値 を参照しなくてはならない点も問題である.決定論的弛緩法以外の反復法に基づく 方法として，弾性膜のポテンシャル場への落ち込みを運動方程式で表現し，系の平 衡状態を反復法により求めるワープ法

[ 2 1 ]

が提案されているが，これも同様の欠点

を持つ.

摂動法(ずらし)に基づく方法

[ 2 2 ] r v [ 2 6 ]

では，各画素(も しくは部分領域)毎に 最も一致する画素を独立に探索するこ とでワープを決定する.これらの方法は最適 性を度外視した代償として計算量が他の組合わせ最適化手法よりも格段に少なくて 済むという特長がある. しかし探索の独立性と局所性のために，多重スケールを用 いた階層的な探索法を用いたとしても，過変形が生じる可能性が高く，加えて大き な変形にも対応できないという欠点を持つ.また同じ理由により制約条件や正則化 手法が導入できないこともこの欠点の克服を困難なものにしている.

DP

は変分問題の数値解法であると同時に，組合せ最適化問題の代表的な解法で もある.

DP

は，

1 )

解の最適性が保証される，

2 )

目的関数の微分可能性の制約が無 い， 3)様々な制約条件を取り扱える， 4)演算誤差の集積による不安定性が無い，な どの特長を持つ.

DP

に基づく 2次元ワープ法は，音声認識における時間歪み整合 (1次元ワープ)問題の

DP

による解決

[ 3 9 ]

，

H O ]

に刺激を受け，これまでにも幾っか 検討されている. しかし本来 1次元的な問題を扱う

DP

を2次元な問題を扱えるよ

うに拡張するのは容易ではないため，いずれも自由度もしくは最適性を犠牲にした り，あるいは問題の本質を見失った方法になっており， 1.

2

の方針

( 1 ) ( 2 )

を同時に満 たす方法は知られていない.

DP

に基づく従来の 2次元ワープ法の例として，画像の縦横の周辺分布について

8 

独立にそれぞれ

1

次元

DP

を施す方法

[ 2 i ， ]

縦方向を固定して横方向に

l

次元

DP

を 施す方法

[ 2 8 ] r v [ 3 0 ]

，縦方向の

DP

の内部で横方向の

DP

を行なう方法

[ 3 1 卜 [ 3 6 ]

が挙 げられる.これらはいずれも特定方向の伸縮は吸収可能であるが，傾きや回転には 対応できず，その意味では完全な 2次元的自由度を持たない.このため，ステレオ マッチング

[ 3 0 ]

やスペクトログラムのマッチング

[ 3 1 ] .[ 3 2 ]

などの特殊な変形を扱う 場合を除いて，画像マッチング問題への有効性はあまり期待できないと考えられる.

2次元的な自由度を持つ2次元ワープ法としては，杉村らの方法

[ 3 i ]

がある.こ の方法では画像の位相構造を保存するワープを実現しているが，ある列の

DP

によ る対応付けの結果を固定して次の列の対応付けの制約とするために，行方向に関す る最適性が無い.このため画像の周辺部に複雑なパターンや雑音が存在する場合に は特に不利である.一方，磯道ら

[ 3 8 ]

は，まず縦方向を固定し各行について

1

次元

DP

を施し，その結果得られた変形画像に対し今度は横方向を固定して各列につい て 1次元

DP

を施すという，

2

段階のアルゴリズムを提案している.この方法もワー プの最適性は保証されない.

Levinら[33]は， 2次元的な自由度を持ち，かつ画像全体で最適性が保証される 2次元ワープ法を提案した.しかし用いている制約条件が単調性だけであるために，

過変形と計算量の問題が深刻であり，文献

[ 3 3 ]

ではアルゴリズムの記述に終わって いる2

本論文が扱う 2次元ワープ決定問題の枠組には直接当てはまらないが，同じく

DP

を用いた画像マッチング法として，対角方向に対応済みの矩形領域を拡張して いく方法 [~1]rv[~5] がある.これらの方法は Le引1、v噌引，でe引I叫1

て提案されたものであるが，文献

[ 3 i ]

，

[ 4 6 ]

でも指摘されているように， 画像マッチ ング法としては不自然な定式化がなされており，有効な応用は見当たらない.

2Levinらの方法については， 6.2で計算量を考察し，8.2.2でそのワープによる過変形の実例を示 す.

9 

1 . 5   動的計画法に基づく 2 次元ワープ法の分類

表1.1:DPに基づく 2次元ワープ法の2次元的自由度による分類 前節で述べた DPに基づく従来の2次 元 ワ ー プ 法[27]rv[38]を， 2次 元 的 自 由 度

を基準として分類した結果を表 1.1に示す.表中の制約条件 (i)rv(i¥')は，いずれも 4 隣接する 2画素のワープ後の位置関係に対する制約を表している.その項目 に 三円 や山二円があるものは 2次元的な自由度が無いことを意味し，

" 0 "

が あ る も の は そ の方向に関する過変形が危倶される.表中の最適性は，この制約条件の下で最適な ワープが求まるアルゴリズムとなっている場合を ~'Ol'とし，そうでなければ“×刊 としている.

各クラス (a)rv(f)に属する 2次 元 ワ ー プ の 例 を 正 方 格 子 (5

x 

5)の変形として図 1.1 に示す.なお同図の各例 で は ， 範 囲 制 約 (">")として， (i )(i¥")の場合土l画素，

(ii)(iii)の場 合

o

rv +2画素が便宜上仮定されている.

クフス 制約条件 文 献 応用例 最適性 時間計算量

(i) 

I 

(日)I (iii) I (iv) 

(a)  >  >  ^{[27]  印刷漢字認識 ×} 

。

^(N2)

(b)  >  _一 ^{日 [28 ，][29]  手書き漢字認識}

。 _。

(N3)

(c)  >  > ^{[30]  ステレオマッチング ×} 

。

^(N2)

(d)  >  >  ^{日 [31 ，][32] 不特定話者単語音声}

。 _。

(N4)

認 識 (freqnencywarp) 

[33]rv[36]  手書き英文字(列)認識

。

O(N4) 

(e)  >  >  >  > ^{[37]  ×} 

。 ^υ

^V3)

[38]  ^× 

。

^(N2)

本 論 文

。 _。

(N2₉2N)

本 論 文

。 。

^(N3gN)

(f)  日 >  > 

。

[33] 

。

O(N4N) 

制約条件:ワープ前に4隣接関係にある画素において

(i)  横に隣接する 2画素のワープ後の縦方向の位置関係の制約 (ii ) 横に隣接する 2画素のワーフ。後の横方向の位置関係の制約 (iii)  縦に隣接する 2画素のワープ後の縦方向の位置関係の制約 (iv)  縦に隣接する 2画素のワープ後の横方向の位置関係の制約 三:絶対位置 の 維 持 ， 前 関 係 の 維 持 ， >範囲制約，

o :

無制約

(a)  ^{z︐ ︐ ・ ︑ ‑ D}   (c) 

(d)  (e)  ^{︐ ︐ ︐ . ︑ ''E・︑ ︑ ︐ ︐ EE}

図1.1:各クラスの2次元ワープの例

M 

y  B

ニ

{ b ( x ，

y)}

A  = 

{a(i，j)} 

N 

第 2 章

単調連続 2 次元ワーフ決定問題

2 次元ワープ決定問題の定式化

2 . 1  

デイジ夕ル画像 A

二 { い

^α(i

ω 九

^，]ρ)

い

1t'Jj=l?2，え.一ぺ..ぺ，iY}およびB = 

い {

b引(.T、う

， y ) 川

1え;I、1νうJ = 1，2丸，.一ぺ，

1 ' 1 }

を考える1人.ここで

α ( い

，うt人]ρ)，b(:爪l1

E

亘亘とする.画像 Aから Bへの画素聞のマッピングを表す関数

‑ M   N 

X 

図 2.1:2次元ワープ {1，2， ・・)JV} x {1うえ .， iV} → {1，2・， ，jH} 

{ 1，え・ ・，iY}x {1，2， ・，iV}→ {1，2，・・， i¥l} 

ぇ : (

i， j) 

ν (

人j)

単調連続性条件と境界条件 2.2 

ワープ関数に対する制約として単調達続性条件を用いる.ここでは単調性および 連続性を，それぞれ隣接画素の上下左右関係および近傍関係がワープ後も保存される

こと と定義する(図2.2(

a ) ( b ) ) .

この単調達続性条件は次式で、与えられる(図2.2(c)). このとき 2次元ワープ決定問題は，何らかの制約条

(2.1 )  D=

I : I : I α

(i

，

j) ‑bCr(i

，

j)

， 

y(i

，

j)) 

1 

の最小値を与えるワープ関数の決定問題と して定式化される. をワープ関数と呼ぶ(図 2.1). 

件下で目的関数

このように 2次 元

(2.3 ) 

( 2

...1 ) 

。三 r(i

，

J)‑:1、

( i

‑1

，

j)三2 0三y

， i (

j) ‑y( i

， 

j ‑1)三2 また画素対応関係

ワープ決定問題はワープ関数を変関数とする変分問題であり，

(2.5) 

(2.6) 

l

: r ( i ，

j)

一的， j‑

1)1三1 Iy

， i (

j) ‑y(i ‑l

，

j)1 :::;  1  このワープ関数により変形された画像

{ b ( . l

・

( i

j，)y

( i ， j ) )

I ~'， j = 1;2・ぅ

. . N }

を

B

と表す.

目的関数 Dの最小値を

D ( A ， B )

と表す.

なお， の組合せ最適化問題にもなっている.

D ( A ， B ) 

= ，  ，" ，  " ~l~n ， ， ^，，' 

L ^乞

^￨α

^{， i (}

^j)‑b(:r(i

^，

^j)

^， 

^y(i

^，

^j 

{~:(i，j)，y('i ，j) I i

，

j二1"・3N}i=lj=1  多くの場合 Blf'V B3の

うちでA との距離を最も小さくしたいものは A と同相な B3であると考えられる.

しかし，連続性が単独で用いられると ，Aが部分的に反転したパターンである Bl 単調連続性の効果を図 2，3の画像を例として説明する.

(2，2) 

また，構造 パターンマッチングの立場から見る と，

D ( A ，  B )

は，2次元ワープによって変形さ れた画像BのうちでAに最も近いものと ，画 像Aとの距離に相当する.

また単調性が単独で用いられると，不連続に変形さ との距離も 0に近い値となる.

モデルBによるA この時のワープ関数(:r(i

， j ) ，

y(i

， j ) )

は，

解析の立場から見れば，

このように，いずれの場合も過変形の れている

B

₂との距離が Oに近い値となる²

28.2.2では単調性のみを制約とする 2次元ワープによる過変形の例を示す.

13  の一つの解釈を与えている.

1以後の議論を縦横の長さの異なる画像に一般化することは容易である.

12 

A  B 

^{B  B} 

第 3章

弓^{ι t"} 

忌

i 周

告挙

~

3 . 1   動的計画法の概要

動的計画法

(a) monotonicity  (b) continuity  (c) monotonicity 

+ continuity  動的計画法 (DP)[5]"'[7]は変分問題の数値解法として重要であると同時に，巡 回セールスマン問題 (TSP)などの組合わせ最適化問題の代表的な解法でもある [2

， ]

[3

  ， ] [ 6   ， ] [ 4 7 ] .  

DPの特長については1.

4

でも簡単に触れたが，変分問題の数値解法と

して近年注目されている決定論的弛緩法[14]，[15]に対する DPの利点を表3.1にま とめて示す.

DPアルゴリズムは問題を漸化式により表現することで構成される.ここでは DPの応用としてよく知られた音声認識における時間軸整合のための 1次元ワー プ決定問題[39

， ]

[40]を例として，漸化式の導出法を説明する.2つの 1次元系列 {α(i)

い =

^{1・，・，・JY}および} {l{r)¹ :r 

= 

1，・・・，J¥1}が与えられた時，その聞の最適 l次元ワープ関数 :r(i): {1，2，... JY}→ {1， 2，.・.jl}は次の制約付き最小化問題の解 図2.2:単調性・連続性条件

。

^4時噂惨

A  8

₁ 

‑

‑

^・・圃・

• 、 、 ー ‑ '

B 

₂ 

B 

₃ 

図 2.3:単調連続性の効果を説明するための例

問題が生じる.これに対し単調性と連続性を併せ考えると，そのような過変形を回 避することができ パターンの位相構造を近似的に保存する 2次元ワープが構成で

きる3

単調連続性条件に加えて次の境界条件を用いる.

以上の条件 (2.3)"，(2.1)は等方性を持つ.すなわち，目的関数 (2.1)が最小化さ れる保証があれば，A^，B^{の縦横を同時に t}←→ 7，，r←→

u

と交換しでも原理的に同じ

ワープが求まる.

:

1厳 密 に 言 え ば，連続性を図 2.2(b)のように 1画素分の跳びを許すように定義しているため，B

上の 2値パターンと忌上の2値パターンは4近傍や8近傍の意味で同相にはならない.

:r(l，

j )  

= 

y ( i

， 1) = 1

， 

として与えられる.

1 

) 川

^11川

^{7 j E ￨ α} ( i ) ー 川 i ) ) 1

^{つd 1lA} 

/l

︑ ︑ ︑

単調連続性条件:

境界条件:

0三.I'('i)‑，/'(i ‑1)三2 .r(l) = 1

， 

.r(lY) =λf 

(3.2)  (3.3 ) 

ここで :1:(入ij) 

= 

^y 

( ' i  ， 

1V) 

= 

Jl  (2.7) 

〆︐tEE︑︑

f11︑ ︑

︐hu 

M ∞ 

f i l l

‑ ‑ 一 一

守﹄ム

/l

︑

' a  

〆︐

︐ 目 .

︑

〆 /

︐l l t ¥7α 

otherwise 

if

市)

a凶 .r(i‑1) satisfy  (3.2 ，)(3.3) 

を考えると，上の制約付き最適化問題は，次の無制約最適化問題

N 

(i)，H L(;Njzd(k:71(k)バ:(k:

‑ 1 ) )

^(3A) 

l，j..

  15 

I D P

^の利点

表 3.1:決定的弛緩法に対する

DP

の利点

￨決定的弛緩法の欠点

解の最適性が保証される. Eular‑Lagrange方程式は極値の必要条件ではあ るが十分条件ではない.また変数の定義域の端 点、で、最大最小となる場合には対応できない.

目的関数の微分可能性の制約が無い. 目的関数が微分可能でないと， Eular‑Lagrange  方程式が導き出せない.

様々な制約条件の取り扱いが可能. 制約条件の取り扱いは不可能ではないが，未定 定数や，スラック変数の導入が必要になり，結 果として計算量が増加する.

演算誤差の集積による不安定性が無 本来は整数値変数であっても反復計算中には実

しヨ 数値変数と見なされるため補間誤差が生じる.

に書き直すことができる.ただし

: r ( O ) =  1

とする.この問題を総当たり法で解こう とすれば，O(J¥IN ) (制約条件を考慮しでもO(3^tv.))の時間計算量が必要となる.

(3.4)式は以下のように書き直せる.

N 

(l)HUvjzd(k:、r

( k :  

)，  ::r(k ‑1)) 

一

( ♂ J 円 2 ;

^{門州?円円月}

r 州 h F r !

^守弘

h

^?

! ?

^{九 川 川?王し(小川」」}

J 4

入

上

N)^，り川^¥')

J ^{ふ [ ト ド 1} h ^{[ 刊 て R l}

^{v : R}

^{弘 出 1 ! 出 l j 1}

二 d叫心J

♂ ♂

d;J?r!?!2d

二 二 叫

J 川 J r )

^{「「門?一一}

J ! l 川 ! ‑ ^{1 弘 ? 弘} ?

^?日(Rし‑

=  .  . = : T f 1 ^{問 ; 馬} i 汚 W v

^号

g ^以

^{(凡にλN:) :}

^{; ， パ (}

^1川V)リ) 

ここで

g (  

i

・ ? の

))=JJJIll)190‑132(i‑1))+d(

い(ん : 1 : ( ' 1‑

1))]  (3.5) 

である.この (3.5)式は一般に DP漸化式と呼ばれる.この DP漸化式を i二 lから 順に i= Nまですべての

: r (

i)に つ い て 計 算 す る と い う 手 続 き に よ り ， 目 的 関 数 の 最

小値を得るアルゴリズムが構成される. (3.5)式 の 1回あたりの計算量が高々O(lIl)

で あ る こ と か ら ， こ の

DP

ア ル ゴ リ ズ ム 全 体 の 時 間 計 算量は

O ( l Y A I

²)で済むこと がわかる.

(3.2)式のゴ:('1‑1)と:r('i)の相互関係を考慮すれば，

DP 

漸 化 式(3.5)は次のよう に簡略化できる.

g ( i ・ ，

:r(i)) ニ min ̲， 

[ g ( i  

‑l

，

:r(i ‑1)) +rl('i，.r (iL~r(i ^‑1))] 

x(i-l)ξ{x(i)，~:(i)-1，J:( i. )-2}

= 1α(1)‑b(20))￨+Hmg(t‑l?:170‑1))(36) 

x(i‑l)ε{.t'( i )，:1・(i)一1，x('i)‑2}

これにより更に精密な計算量オーダーO(3NJ¥I)二 O(JYi¥l)が得られる.

ここで注意すべきは同じ問題でもその

DP

漸化式は一意でない点である.例えば 同じ 1次 元 ワ ー プ 決 定 問 題 に つ い て 次 の

DP

漸化式も考えられる.

g ( i ， 

:r(i)， J:

( ' i   ‑

1)) 

=  1α(i) ‑

b (

コ('1:))1+1α

( ' i .‑

1) ‑b(:l・(i‑1))1

min  ̲g

( ' i

‑2

，

:r(i‑2)

，

x(i‑3)) 

工(i‑2)ε{x(i‑l)，x(i‑l)一1，x(i‑l)‑2}

x(i‑3)ε{x(i‑2)，x(i‑2)一1，x( iー2)‑2}

(3.7) 

この

D P

漸化式を 'i= 2から Nまで lつおきに計算すれば， (3.6)式を用いた場合と 同一の解が求まる.

3 . 2   多段決定過程

多 段 決 定 過 程 (multistageclecision proccss)は

DP

と 密 接 な 関 係 を 持 つ 概 念 の 1 つである.Bellman [5]流 の 用 語 に 従 え ば ， 多 段 決 定 過 程 は 段 (stage)，状態 (stat.e)，  決 定 (clecision)，状 態 遷 移(statetは nsition)，および遷移コスト (transitiollcost)に

よ っ て 記 述 さ れ ， ま た 一 般 に 有 限 状 態 オ ー ト マ ト ン の よ う に 状 態 図 表 現 さ れ る . 前 節 の よ う な 手 続 き に よ り あ る 問 題 に つ い て そ れ を 解 く

DP

漸 化 式 が 得 ら れ れ ば，その問題を多段決定過程により直ちに表現できる.例えば前出の 1次 元 ワ ー プ 決 定問題の場合，

DP 

漸 化 式 と し て (3.6)式を用いると

，

i = 

1

ぃ .

，

i¥ずが段に対応する.

第1段 で はα(7)のマッピング

c ( i )

が決定される.この 、r(1')として許されるものの集

transition cost : la(i)ーb(x(i))I 

XニMt

三 三

^ヂすヂOOO 

? 

O st ate x ( i 1 )ヂヂ0Ooι4

テ ‑

t

L

^く

^{1 ー}

^{j90O O st ate x (} 

l  ) 

。

^. 

x=1 I 0ι

一 一

0ι²  =‑‑0³ 

話

^{i N‑1  N} 

state transition 

図 3.1:1次元ワープ決定問題[39]，[40]を表現する多段決定過程

合 {:l・

( ' i )

}が第i段に属する状態の集合となる.すなわち，第 i段 で の 決 定t→

: r ( i )

の結果，状態は ::1

( ' i )

へ遷移する1 第i‑1段の状態;r(i‑1)と第t段 の 状 態:r(i)が 制約条件 (3.2)を満たす場合，

川

l'‑1)からえ:(i)へ状態遷移で、きる.最後に状態

: r ( ' i) 

への遷移に遷移コスト

α( ￨ 1 : )‑ b ( : r ( i

))1を加法的に与える.こうして定義された 1次 元ワープ決定問題を表現する多段決定過程を図 3.1に示す.

以上の DP漸化式と多段決定過程の対応関係より明らかなように，多段決定過程 の各状態について，そこに遷移可能な前段の状態のうち累積コストの最小のもの選 択しそれに遷移コストを加算することでDP漸化式計算が実現する.この処理を初 期状態から最終状態まで行なえばその最少累積コストとして目的関数の最小値が得 られ，さらにパックトラック処理により最適状態遷移系列(決定列)が与えられる.

DPアルゴリズムの計算量は対応する多段決定過程の規模から見積もることがで きる.DPアルゴリズムの時間計算量はその多段決定過程中の総状態遷移数に比例 する.これは段数 l段当たりの状態数， 1状 態 か ら 可 能 な 遷 移 数 の 積 で 与 え ら れ

lこの場合，決定と状態は同一視できる.しかし5章のピクセルワイズDPアルゴリズムのように，

決定と状態が同一視できない場合もある.

る.一方，空間計算 量は総状態数(バックトラ ック処理が不要な場合， 1段あたりの 状態数)に比例する.これは段数と 1段当たりの状態数の積で与えられる.

ある問題に対する DP漸 化 式 が一意でないことから明らかなように，多段決定過 程も一意ではない.例えば(3.7)式の DP漸化式に対する (JV/2段の)多段決定過程

も構成することができる.

本論文では多段決定過程を用いて DPアルゴリズムの説明を行なう.DPアルゴ リズムの議論をする上で多段決定過程を用いることの利点は，状態図表現により問 題の構造の見通しがよくなる点と，以上に述べたようにアルゴリズムの時間および 空間計算量の見積りが容易になるという点である.

なお，多段決定過程はDPに固有の概念ではなく，問題を木探索や総当たり法で 解く場合も構成することができる. 例えば木探索の場合の多段決定過程は木構造と

なり，図 3.1のようないわゆるトレリス構造にはならない.

3.3  ビームサーチ

DPアルゴリズムは計算量が多いことが欠点と言われる.もちろん総当たり法に 比べると DPは洗練された方法ではあるが，

I

次元の呪い (c川 seof climcnsionality) 

J 

と言われるように その計算量は問題のある種の困難さに鋭敏に反応し，結果とし て指数オーダーの計算量を持つアルゴリズムとなる場合がある.このためDPを用 いる場合には，その計算量を常に考慮する必要がある.

解 の 最 適 性 を 保 っ た ま ま 計 算 量 を 減 ら す 方 法 と し て は ， 分 校 限 定 法 の 限 定 操 作 の概念を採り入れ 最適状態系列に含まれる可能性が完全に無い状態を除外する方 法

[ 2 ， ] [ 4 8 ]

がある. しかし計算量の少なくて済む単純な下界値関数では効率のよい 限定操作は期待できず，大きな改善は見込めない.

一方，解の最適性をあきらめ， DPの 近 似 ア ル ゴ リ ズ ム が 検 討 さ れ る こ と も 多 い

[ 4 7 ， ]

[.J:

9 ] r v [ 5 6 ] .

それら近似アルゴリズムのうち一般的なものとしてビームサーチ DPアルゴリズム [53]，[54]が挙げられる.ビームサーチ (heamsは rch)とは，局所的 な判定基準により最適決定系列に含まれる可能性が低いと判断された状態を以後の

処理から除外するという，いわゆる枝刈処理 (pruning)を各段で行なうことにより 探索空間を圧縮し，計算量の低減を実現する効率化手法である.このビームサーチ

と DPアルゴリズムを組合せはビームサーチ DPアルゴリズムと呼ばれる.ビーム サーチの適用により解の最適性の保証はなくなるが， 実用的にはその近似解で十分 なことが多い

[ 4 7 ， 1 [ 5 3 ]

^r‑‑;

[ 5 6 ] .  

ビームサーチ DPアルゴリズムでは ビームサーチを効率的なものとするため に，動的リストとビーム内データ駆動方式が用いられることが多い

[ 5 3 ]

^r‑‑;

[ 5 5 ] .

^動的

リストとは，枝刈の結果残った状態だけをメモリ上にリスト化して格納する方法で， これにより空間計算量を大幅に低減することができる.ビーム内データ駆動方式と は，リスト上に残った状態から DP漸化式を駆動する手法で，これにより時間計算 亘を削除することができる.

ビームサーチ DPアルゴリズムで用いられる枝刈判定処理としてはしきい値処 理 が一般的である.ここで用いるしきい値としては， (a)固定値， (b)その段の累積 コストの最小値に余裕定数を加えたもの， (c)その段の累積コストのうち R番目に 小さい値

e

^，のいずれかが用いられる.本研究では (c)を用いた.この理由は， (a)  や (b)のしきい値では計算量の見積りが難しく，また状態が非常に多くなる問題に おいては実行可能な程度まで校刈が行なわれない場合が発生するためである.以下，

Rをビーム径:と日乎ぶ.

近似アルゴリズムは精度保証

H ]

^，

^{[ 5 7 ]}

ができることが望ましいが，ビームサーチ DPアルゴリズムではビーム径 Rと近似精度の間に単調な関係は保証されない. し かし平均的にはビーム径が大きいほど近似精度は高くなると考えられる.実際，本 論文で示す実験結果(4.6.2，5.6.3， 8.3)もその傾向を示している.

2 0  

第 4 章

動的計画法による解法 1 ‑ カラムワイズ D P アルゴリズム

4 . 1   まえが 、 き

本章では，第 2章で定義した単調連続2次元ワープ決定問題，すなわち (2.2)^r‑‑; (2.7)の最適化問題の DPによる解法を検討する.多段決定過程としての定式化が必 要になるが，そこでは段，状態，状態遷移をどのように考えるかが問題となる.こ れに対し，ワープ全体の決定問題を列単位の部分問題に分解して捉えるという一つ の自然な考え方から，列の推移の各段で各列のマッピングを決定するという逐次過 程としての定式化が可能となる.この場合，列内の単調連続性制約が各段に属する 状態を規定し，また列間の単調連続性制約が可能な状態遷移を規定することになる.

本章で提案するカラムワイズ DPアルゴリズムは，こうして定義される多段決定過 程の最適状態遷移系列を与えるものである.

なお，付録A.lに，カラムワイズ DPアルゴリズムが正しく単調達続 2次元ワー プ決定問題を解くことの証明を与えた.

4.2  ヲIjを処理単位とする多段決定過程による問題表現

4 . 2 . 1   段司決定および状態

画像Aの第

t

列を

α

( 1 " )  

= α( ，i(1)

，  • • • ; 

a( i，j)ー・α3(i，lV))  (4.1 ) 

21 

状態遷移

N 

cost:

エ ^{4 . 2 . 2}  

XY(N 

上述のように，状態xy

( i )

とxy(i‑1)はそれぞれ α(i)とα

( ' 1

‑1)の1つのマツ よって状態 xy(i) とxy(i)へ遷移可能な状態 xy(i‑1)は互い に単調連続性 (2.3)，(2.6)を満たす必要がある. 例えば，図 4.2(a)のxy(i)を同図

( b )

のように:1:および

U

方向へ分解したものをx

( ' i ) ，

y(i)とすれば，同図 (c)の灰色 の部分に含まれる x(i‑1)，

ν

(i‑1)をム

y

成分とする xy(i‑1)が，x

ν

(i)へ遷移可 能な状態である.以下 xy(i)に遷移可能な xy

( i‑

1)の集合を XY(x

ν

(i))と表す.

ピングに対応する.

la(i，j)‑b(x(i，j)  ，y(i，j))I  XY(i 

ω ω H U

V ω  

状態 xy(i)への遷移は， α(i)を局所ひずみパターン xy(i)により B上へのマッ ピングすることの決定に相当する.よって， (2.2)の目的関数を考慮すれば状態 xy('i) への遷移に対するコストは次式で与えられる.

遷移コスト 4 . 2 . 3 

~

^̲a(i) 

/ / ? 

~

^a(i・1) 

d シ

G 

ゾ /

d

， i ( 仰ぐ

i))

= 乞 ￨ α (

人j)‑

b ( : r (

人j)， y

  ， i (

j) ) I  図 4.1:単調達続2次元ワープ決定問題を表現するカラムワイズな多段決定過程

(4.3)  その第 i段で、はα(1:)の

マッピングが決定されるとする.決定が列 (column)を単位としてなされるので，こ 図 4.1にこの多段決定過程の状態図表現 ここで i= 1から JVまでの N段の決定過程を考え，

と表す.

第l段から第JV段までのある状態、遷移系列(決定列)に対してこの遷移コストを累積 れをカラムワイズな多段決定過程と呼ぶ.

的関数値D を計算 その状態遷移系列に対応する単調達続2次元ワープの

することができる.

すれば，

を示す.

このため決定と状 第 i段に属する各状態は α(i)の lつのマッピングに対応し，

このマッピングによる α(i)の B上での像を局所ひ

カラムワイズ D Pアル ゴ リズム

態、は同一視することができる.

4.3 

( 4.2)  xy

( ' i  )

で表す(図 4.2(a)).

ずみパターンと呼び，

最適な単調連続2次元ワープは，以上で定義された多段決定過程上のすべての状 態遷移系列のうち最小累積コストを持つものに対応する.図 4.3にその最適状態遷

x 

y ( 1:) 

=  ( ( . r  ( 

i ⁱ 1 ) ) Y ('I; 1 )) ， • •

. 、 ( r   .

(i ) j)， y ( i ， j ) ) ， • • • ， 

( : r  ( 

i， N  ，)y( i， N") ) )  以下では記号 xy(i)により，その局所ひずみパターンが対応する状態も表わす.図

4.1の状態図では，各状態をその局所ひずみパターンにより具体的に表現している. 図中

最適状態遷移系 移系列を探索する DPアルゴリズム(カラムワイズDPアルゴリズム)を示す.

の

g (

人xy)は，ある初期状態xy(l)から状態xyE X Y

( i )

までの，

列に対する累積コストを表す.Step 5がDP漸化式に相当する.

局所ひずみパターン

z ν

('i)としては，単調連続性条件 (2.4)， (2.5)， 

条件 (2.7)を満たす範囲で様々な形状が選べる.その集合を XY(i)

= 

{xy(i)}と表 なお，残りの単調連続性条件 (2.3)，(2.6)は，次節で述べるように状態遷移に および境界

なお

D(A

，

B )

だけ この他にパックポ でなく最適2次元ワープ関数を具体的に求める必要がある場合，

それらの実装は容易である. インタやパックトラック処理が必要になるが，

す.

対する制約となる.

I U  X Y ( i ) 1   10

³⁰ 

Monotonic 2DW (Levin et a.l) 

10

²⁵ 

10

²⁰ 

10

¹⁵ 

M 

N  M  B 

a(i)  N  A 

Monotonic and continuous  2DW (columnwise 

[ ) E 2   10

¹⁰ 

10

⁵ 

立竺盟主^blex(iイ)

j  N 

(c) 

︑

FI N 

・ D

・‑ ( M  X 

N  X 

(a) 

10  12  14  16  image s i z e  N (=M)  6  8 

zν(i)の例，(b)その :r，y方向への分解， (c)  y方向での領域

(a)局所ひずみパターン

支Y(xy

( 1 : ) )

に含まれる xy(i‑1)の :r， 図 4.2:

図 4.4:局所ひずみパターンの総数

I

Ui X Y(i)1 

計算量の評価 4 . 4  

/

本

hatuLluat'iO'rl，

本 /

for all xy

ε

X Y(l) do  ク(1

，

xy) 

= 

rl(l

， 

xν)  1 

2  本節では， λ λ Jの場合の，カラムワイズ DPアルゴリズムの時間計算量およ

び空間計算量を考察する.3.2で述べたように，

算 量は多段決定過程中の総遷移数に比例し，

数(パック トラックを必要しない場合は 1段当たりの状態数)に比例する.

まず l段当たりの状態数 IXY(i)1を見積もる.局所ひずみパターンをその絶対 DPに基づくアルゴリズムの時間計 空間計算量は多段決定過程中の全状態

j * 

Re氏印cC仰.'，^，

for i :二 2to 1λi¥，f do 

for all x

ν ε

X Y(i) do 

gU i 

xy) = d

  ， i (

x

ν ) +

^包Il

g (  

i ‑1，可 )

五百ξXy(.x引)

3 4 5  

位置(:じ

， i (

l)

，

y

( ' i

、1))と形状に分離して考える.境界条件 (2.7)により y(i

， 

1) = 1で あることを考えれば，取り得る

( . t

^、(i

， l

，)y

( i ， l ) )

の数は

N

ニ

O (

入T)となる.また局所

j * 

'nε引r.，.'(，川f

D(A

， 

B) =  mi山n g

ぱ ( 民 Z ν

糾) 

2官εXY(.N・)

6 

歪みパターンの形状は単調達続性条件 (2.‑1)， (2.5)により O(gN)通りの可能性があ よって IX Y(i)1二 O(iV)X O(gN) = O

( l

VgN)が得られる.参考のため， 図‑1

A

る.

にU^五IXY

( i

)1の数値シミュレーシヨンによる実現JI値を示す.

図 4.3:カラムワイズ DPアルゴリスム

24 

次に 1つの状態から可能な遷移数 ¥XY(xy('i))¥を見積もる.単調連続性により，

xy(i‑1)とそれに隣接可能なxy(i)のjにおける差分(:r(i

，

j)‑:r

( 1 :  

‑l

，

j)

，

y(i

，

j)‑

y( i ‑

1

， j))は，xy

( ' i   ‑ 1 )

， x

ν

(i・)の形状とは無関係に

( { 2

，

1

^ぅ

O }

，

{ 1

， 

0

，ー

1 } )

で表され る9種類のいずれかとなる.逆にこの差分N個の列とxy

( 1 :

‑1)を用意すれば，隣接 可能な

ν z

(i)が 1つ定まる(図.f.2(c))・こうした差分の列の全部は，各ノードがそれ ぞれ9種類の差分の lつに対応する子ノードを持つような深さ Nの9分木によって 表現できる.すなわちこの 9分木の根から葉までのgN本の道により ，xy(i‑1)に 隣接可能なxy(Oの全部が表現される.よって ￨玄Y(xy(i))¥= O(gN)が得られる.

以 上 の 見 積 り と 段 数 がNであることより，カラムワイズ DPアルゴリズムの時 間 計 算 量 と し て jYX O(iVgN) X O(gN)ニ O(λ

r

²g2N)が 得 ら れ る . ま た 空 間 計 算 亘として，バックトラックにより最適ワープ関数を求める必要がある場合について jV X O(iVg^{N )} = O(ly²gN)，パックトラックを必要しない場合について O(lVg^N)が 得られる.

j *  

S'lLb‑t^'rrL肌 t'lO

凡

'1

。 = ^{1 )   * j}  

1 l:= 1 

2 for t := 1 to ¥L1 STi‑_1¥ do begin  3 

百 ， (

xy) := L1STi‑1 

[ t ]  

4  (b:r

， 

null) :=自rstelement of 王宮 5  for :r := b:r to u:r + 2 do begin 

6  NODE

I [

l]  ^:= 

( 互 (

+¥α(人

1 ) ‑

b(:r， 

1 )  

¹ )，川

1 )

null， t)  7  l := l 

+ 

1 

8  end  9 end 

/ 本

Sω‑tnLns'It'lons  (j 

= 

2， • • • ， JY 

) α

nd p^'r'un'ing 

*  1 

10  for j :二 2to lV do begin 

1 1  

l := 

1 

12   )(:= R山 smallestcost g in NOD鳥‑1

1 *  

Deciding pr^'Uηing t}^附 shold

*  j 

4 . 5   近似アルゴリズムーカラムワイズビームサーチ D P アルゴリズム

円 べ U

4

斗ムピリ

可l ム 1 1 ム 寸

tム

j *  

Scαnning NODEj‑1

本 /

for k:= 1 to 1 NODEj̲1¹ do begin 

(

万

?α:r

，

αy

，

null

， 

t) := NODEj‑dk] 

if豆 >()  then continue 

1

^牢 Prun'tng

本 /

前 節 で 述 べ た よ う に ， カ ラ ム ワ イ ズ DPア ル ゴ リ ズ ム の 時 間 空 間 量 お よ び 空 間 計算量は，共に入?に関して指数オーダーで増加する.このためカラムワイス DPア

ルゴリズムをそのまま現実的なサイズの画像に適用することは事実上不可能である.

そこで，ビームサーチの適用による近似アルゴリズムを検討する.

3.3で述べたように，ビームサーチは基本的に各段で最適状態系列に含まれる可

能性の低い状態を校刈により除外する処理により計算量を低減する方法である. し かしこの定義に従ってビームサーチをカラムワイズ DPア ル ゴリズムにそのまま適 用しても多項式時間計算量を持つビームサーチDPアルゴリズムは得られない1 こ れは各状態が遷移可能な状態数

l

XY(x

ν

(i))¥が指数オーダーであることに因る.

1明らかに，多項式時間アルゴリズムの空間計算量は多項式オーダーである.ただし逆は成り立た ない.

1 *

^{キ C附 伽}Lg^"礼I札 附L

16  (null

，  x 百 )

:= L1STi^ー

I [

t] 17  (u.r， uy) := jth clement of xy 

18  for all (:r

， 

y) ¥vhi:ch satisfy rnonoto山 .ity

，

co山 nni.tyand bounclary  conclitions with respect to (α川αy)ancl (u:r， by) do begin  19  NODE_j[l]  := 

( 万 ( + 1 α ( i ， j )  ‑

b(:川y)I)

，:   ， : 1

y

， 

k

，  t )  

20  l := l 

+ 

1  21  end 

22  end  23  end 

図 4.5:カラムワイズビームサーチ DPアルゴリズムの第 j段 で の 処 理