人工知能Ｂ

Transcription

1 音声言語処理特論 第 2 回音声認識の基礎 DP マッチングの基礎 山本一公

2 先週の残りから 音声言語処理特論 第 2回 2

3 音声信号のディジタル化 空気中を伝搬している音声信号はアナログ信号 即ち 連続信号 マイクロホンで受音した後に得られる信号電圧もアナログ信号 離散信号にしないと コンピュータ上で上手く扱うことができない ディジタル化が必要 音声言語処理特論第 回 3

4 ディジタル信号 ディジタル信号とは? 時刻パラメータが離散値 標本化 ( サンプリング ) 振幅パラメータが離散値 量子化 離散値でなければ 計算機では扱えない 離散時間信号 時刻パラメータだけが離散値 離散振幅信号 振幅パラメータだけが離散値 おそらく扱うことはない 音声言語処理特論 第 回 4

5 ディジタル化 この連続信号をディジタル化しよう 音声言語処理特論第 回 5

6 サンプリング () 時間軸方向の離散化 音声言語処理特論第 回 6

7 サンプリング (2) どのぐらいの時間間隔で離散化すれば良いのか? 間隔が広すぎると 元の波形が再現できない 間隔が狭すぎると 無駄にデータ量が多くなってしまう 元の波形に含まれる周波数成分がナイキスト周波数 ( サンプリング周波数の半分 ) 以下に帯域制限されていれば 元の波形が完全に再現可能 ( 標本化定理 ) x( t) = π sin ( t T x( it ) π i= t it ) it ) サンプリング周波数 = 標本化間隔の逆数 T ( 音声言語処理特論第 回 7

8 サンプリング (3) 簡単に言えば,000Hz の信号は 2,000Hz より大きいサンプリング周波数でサンプリングしろ! ってこと 通常 サンプリング周波数が高いと高音質 実際 音声信号にはどれくらい高い周波数が含まれているのか? 理論的には無限大まで入っているけど 高い周波数成分は人間には聴こえない ( よく聴こえる人で 20,000Hz ぐらいまでだ ) し 大きさも小さいから観測できない マイクロホンにも録音できる限界 ( 周波数特性 ) がある 実際に使われるサンプリング周波数 8kHz: 普通の携帯電話 ( 固定電話帯域 (0.3~3.4kHz)) 6kHz: VoLTE の携帯電話, PHS 44.kHz: 音楽 CD 48kHz: DVD-Video 96kHz, 92kHz: DVD-Audio 通常 ナイキスト周波数 ( サンプリング周波数の /2 の周波数 ) をカットオフ周波数とするローパスフィルタを掛けることで サンプリング時に起きる誤差 ( 折り返し歪 ) を小さくするので 音として聞こえるのはナイキスト周波数まで 204/9/3-4 TUT Jr. 技術科学教育プロジェクト 8

9 量子化 () 振幅軸方向の離散化 音声言語処理特論第 回 9

10 量子化 (2) 誤差特性 量子化特性 音声言語処理特論 第 回 0

11 量子化ビット数の決め方 SQR (Signal-to-Quantization noise Ratio) 信号対量子化雑音比 量子化誤差を雑音と看做して求めたSNR 変換範囲のフルスケールを最大振幅とする正弦波の場合 SQR 0log 2 = 6b +.8 [db] 2 b = + 実用的には 6bit か 24bit (CD-DA は 6bit DVD-Audio は 24bit) 音声言語処理特論 第 回

12 ディジタル化された音声波形の例 時間音声処理で使われる一般的なサンプリング :6bit, 6kHz 音声言語処理特論第 回 2

13 スペクトル分析 音声波形 ( 上 ) とスペクトログラム ( 下 ) 音声言語処理特論第 回 3

14 フーリエ級数展開 () あらゆる周期信号は 周波数と位相が変更できる無限個の正弦波発振器により合成可能 周期的な連続信号は その信号の基本周波数の整数倍の正弦波に分解できる 音声言語処理特論第 回 4

15 5 フーリエ級数展開 (2) [ ] ),2,3, ( )sin ( 2 ),2,3, ( )cos ( 2 ) ( sin cos ) ( ),0,,2, 2,, ( ) ( ) ( 2 / 2 / 0 2 / 2 / 0 2 / 2 / = = = = = + + = = + = = n Tdt n t x T B n Tdt n t x T A dt t x T A T n B T n A A t x m mt t x t x T T n T T n T T n n n ω ω ω ω 音声言語処理特論第 回

16 6 複素フーリエ級数 () = = = + = = = 2 / 2 / * 0 0 ) ( ) ( 2, 2 T T t jn n n t jn n n n n n n n n dt e t x T C e C t x jb A C C jb A C ω ω 音声言語処理特論第 回

17 複素フーリエ級数 (2) 正の周波数と負の周波数 正の周波数と負の周波数を合成したものが正弦波 虚部は打ち消し合い 実部だけが残る 実部は実軸上で正弦振動を行う 音声言語処理特論第 回 7

18 正の周波数 負の周波数と オイラーの公式と時間波形 204/9/3-4 TUT Jr. 技術科学教育プロジェクト 8

19 振幅スペクトル 位相スペクトル () 複素フーリエ係数の極座標表現 C n = C n e jφ n 振幅スペクトル C n = 2 A 2 n + B 2 n 位相スペクトル φ n = tan B A n n 音声言語処理特論第 回 9

20 振幅スペクトル 位相スペクトル (2) x( t) π π = 2 sin t sin( 3t ) + sin 4t = sin t + cost + 0.5sin 3t + 0.2cos3t + cos 4t 音声言語処理特論第 回 20

21 振幅スペクトル 位相スペクトル (3) 線スペクトル ( 離散スペクトル ) 振幅スペクトル 位相スペクトル x( t) π π = 2 sin t sin( 3t ) + sin 4t = sin t + cost + 0.5sin 3t + 0.2cos3t + cos 4t 音声言語処理特論第 回 2

22 フーリエ変換 周期 T を無限大にした孤立波形に対して フーリエ級数の周期を無限として極限を取る フーリエ変換対 X ( ω ) = x( t) e jωt dt x( t) = X ( ω ) e jωt d ω 式としては 両側ラプラス変換で s=σ+jω を σ=0 とした場合と同じ 音声言語処理特論 第 回 22

23 フーリエ変換のスペクトル 連続スペクトル 時間領域波形 周波数スペクトル 音声言語処理特論 第 回 23

24 24 離散フーリエ変換 離散フーリエ変換は ( 連続 ) フーリエ変換を離散化したもの というよりは フーリエ級数を離散化したもの ( 離散フーリエ級数 ) だと考える ( ) ( ) N j N N k nk N N n nk N e W N n W k X N n x N k W n x k X 2π ) ( ) ( 0 ) ( ) ( = = = = = ただし 音声言語処理特論第 回

25 高速フーリエ変換 離散フーリエ変換は結構計算量が多い 計算量 O(n 2 ) フレームの長さ ( ポイント数 ) をべき数に限定することで 計算を簡略化 高速フーリエ変換 (Fast Fourier Transform; FFT) 広く用いられているものは 基数を 2 とする場合 ポイント数は 2 のべき乗 サンプリング周波数 8kHz ならば 256 ポイント サンプリング周波数 6kHz ならば 52 ポイントで 32ms 計算量 O(nlog 2 (n)) 音声言語処理特論第 回 25

26 窓掛け ( フレーム化処理 )() サンプリング点毎に特徴量を抽出すると データ量が多くなりすぎる 音声は20~30ms 程度の区間であれば 定常信号と見なすことができる ( 準定常 ) 音声波形を短い区間 (20~30ms) 毎に切り出して 分析する 各区間をフレームと呼び 短時間スペクトル分析などの単位となる 音声言語処理特論 第 2回 26

27 窓掛け ( フレーム化処理 )(2) フレームは /2~/3 程度重ねて処理していく 分析 標準的なフレーム長 :20~30ms 程度サンプリング周波数 6kHz の場合 25ms で 400 点 音声言語処理特論 第 2回 27

28 窓掛け ( フレーム化処理 )(3) 窓掛けの目的は 波形の切り出し 連続波形の有限長化 切り出してから 離散フーリエ変換 (DFT FFT) DFT では 切り出した区間がちょうど 周期 であると見なして 分析してしまう ちょうど 周期 窓長が基本周期 切り出した区間の始端と終端が繋がっていると仮定 実際には 切り出した区間が 実際の波形の周期と一致しない 切り出した区間の始端と終端は繋がっていない 音声言語処理特論 第 2回 28

29 窓掛け ( フレーム化処理 )(4) 窓関数を掛けることで 波形の両端の振幅を小さくする 時間領域での掛け算 ( m; l) = w( m) s( l m) s w + 音声波形 s 窓関数 ( ハミング窓 ) w l l+n- m 音声言語処理特論 第 2回 29

30 窓掛け ( フレーム化処理 )(5) ハミング窓を掛けた例 それぞれを DFT して分析していく 音声言語処理特論 第 2回 30

31 時間窓関数の種類 () 窓の両端が減衰しており 実効窓長が短くなっている 窓を重ねて処理する理由 ハミング窓 W H 2nπ ( n) = cos N ハニング窓 ( ハン窓 ) W N 2nπ ( n) = cos N 矩形窓 スペクトルのメインローブが狭く サイドローブが小さい窓が使われる 音声言語処理特論 第 2回 3

32 時間窓関数の種類 (2) 様々な時間窓関数の時間波形 音声言語処理特論 第 2回 32

33 時間窓関数の種類 (3) 様々な時間窓関数の周波数スペクトル 音声言語処理特論 第 2回 33

34 窓関数の種類 (4) 時間領域での掛け算 周波数領域での畳み込み演算 s w ( m; l) = w( m) s( l + m) S W ( k; l) = W ( k) S( k; l) = W ( j) S( k j; l) メインローブの幅が広いと 分析したい周波数 k の周辺の周波数を分離して分析できない ( 周波数分解能が低い ) 狭い方が良い 窓幅を長くすればメインローブの幅は狭くなるが 時間分解能が下がる サイドローブの振幅が大きいと 離れた周波数の成分の影響を受けてしまう 小さい方が良い 不確定性原理 これらを同時に満たす窓は 周波数領域ではインパルスとなるため 長さ無限大の矩形窓 (= 窓掛けしない ) となる 周波数分解能と時間分解能を同時に高くできる窓は 存在しない 用途によって複数の窓を使い分けるしかない j= 音声言語処理特論 第 2回 34

35 音響特徴量 音声言語処理特論 第 2回 35

36 フレームだけの分析 スペクトルの例 () 36

37 スペクトルの例 (2) 連続するフレームを 3D 表示 37

38 スペクトルの例 (3) 連続するフレームを濃淡表示 38

39 スペクトル表現のための音響特徴量 スペクトルそのものは特徴量としては冗長 ベクトルの次元数が多いのはモデルパラメータの推定や計算量の面で問題が出やすい より次元数の少ないスペクトル表現が求められる 現在の音声認識では MFCC が代表的な特徴量 線形予測分析に基づく特徴量も 音声波形 振幅スペクトル フィルタバンク出力 MFCC ケプストラム 39

40 音声生成の信号モデル 音源 ( ソース ) フィルターモデル 時間 パルス系列 ( 声帯振動 ) 周波数 g(n) 調音フィルタ h(n) s(n) 調音器官 ( 舌, 顎, 口蓋, 唇など ) 音声 時間 周波数 周波数 周波数 =音声言語処理特論 第 2回 40

41 スペクトル包絡と微細構造 スペクトル包絡 周波数とともに緩やかに変化する成分 音源のスペクトル概形 声道の共振 反共振特性 放射特性などを表現 微細構造 音源の周期性 スペクトル包絡が欲しい! 音素の種類を決定づけるのは 基本的に声道形状である! 4

42 スペクトル分析の方法 窓掛けして区切られた音声波形の区間 ( フレーム ) ごとに スペクトル包絡 を求める ケプストラム (cepstrum) 法 微細構造を数値処理で削り落とす モデルを仮定しない ノンパラメトリック分析 cepstrum は spectrum をもじって作られた造語 LPC 法 線形予測符号化 (Linear Predictive Coding) に基づく方法 モデルを仮定する パラメトリック分析 滑らかな関数でスペクトルを近似する 42

43 ノンパラメトリックな分析 - ケプストラム分析 - x(n) DFT Log IDFT DFT 対数スペクトル包絡 時間窓 ケプストラム窓 スペクトルのギザギザを波形とみなしてフーリエ変換し 高周波成分を取り除いてから逆変換している と考えると分かり易い ケプストラム窓 ピッチ ( 微細構造成分 ) ケフレンシー quefrency 43

44 ケプストラム分析 s( t) = S( ω) g( t) h( t) log S( ω) = c( τ ) = = G( ω) H ( ω) = ~ S ( ω) = FFT FFT - - FFT フーリエ変換 log G( ω) + log H ( w) ( log S( ω) ) - ( log G( ω) ) + FFT ( log H ( w) ) ~ ( ( c τ )) 対数変換 低次のみ取り出し (= リフタをかける ) フーリエ変換 逆フーリエ変換 44

45 パラメトリックな分析 - LPC 分析 ( 線形予測分析 ) - パルス系列 ( 声帯振動 ) インパルス系列 ( 破裂音 ) ノイズ ( 乱流 ) 音源信号 H g(n) z) 調音フィルタ h(n) 調音器官 ( 舌, 顎, 口蓋, 唇など ) z ( = 2 p a z a a pz 2 X(z) s(n) 音声信号 = F(z) F( z) + - ^ X(z) E(z) 45

46 LPC 合成フィルタ 予測残差を入力して 波形を合成する X ( z) = E( z) = F( z) p i= a i z i E( z) 46

47 スペクトル包絡の分析例 47

48 MFCC の分析手順 Mel Frequency Cepstrum Coefficients メル周波数ケプストラム係数 MFCC は メルフィルタバンクの出力を対数化したものに対して DCT( 離散コサイン変換 ) を掛けたものとして定義される 理論的な定義ではなく 実用的なもの フーリエ変換 (FFT) フィルタバンク分析対数化 離散コサイン変換 (DCT) 窓掛け音声波形 メル周波数化 スペクトル包絡 スペクトル 対数フィルタバンク出力 MFCC スムージング 直交化 次元圧縮 48

49 フィルタバンク法 周波数方向に平均化して滑らかにする 周波数 フィルタバンク番号 49

50 聴覚を考慮した分析 - メルスケールとメルフィルタバンク - mel f = 27 ln 人の耳の聴覚特性 : 低い周波数では分解能が細かい 高い周波数では分解能が粗いメルスケールに変換するとよい メルスケールへの変換関数 周波数 周波数 50

51 聴覚を考慮した分析 - メルスケールとメルフィルタバンク - メルスケールへの変換関数 メルフィルタバンク スケールは他に Bark や ERB も フィルタ形状も三角形だけではない 横軸は ( 線形 ) 周波数メル周波数で考えると フィルタは等間隔に配置されている 5

52 MFCC の分析手順 フレーム分の波形 窓掛け波形 スペクトル フィルタバンク出力 対数化フィルタバンク出力 ケプストラム (MFCC) 52

53 MFCC の分析例 フーリエ変換 (FFT) フィルタバンク分析 離散コサイン変換 (DCT) 音声波形 スペクトル フィルタバンク出力 c MFCC ( c ( k), c ( k), c ( k),, c ( k ) T ( ) = 2 n k ) N k: フレーム番号 N: ケプストラムの次元数 (2 程度 ) 53

54 その他よく使われる特徴量 音声パワー 音量を表すパラメータ. 対数で表現する p( k) ( k + ) T = log x( t) t= kt ケプストラムの 0 次項 ( 対数スペクトルの直流成分 ) を用いることもある 回帰係数 時間軸方向に回帰分析を行うことで求められる係数 ( 次頁 ) 2 54

55 動的特徴量 ( 回帰係数 ) フレーム間での動きを表現 c(t-2) c(t-) c(t) c(t+) c(t+2) c 線形 ( 次 ) 回帰係数 (Δ ケプストラム ) n ( t) = K k = K kw c K k k = K k n 2 ( t + k) w k 傾きが計算されるケプストラムの時間的変化の速さ Δ ケプストラムの回帰係数 (=2 次回帰係数 ΔΔ ケプストラム ) までがよく使われる 55

56 その他の特徴量 音声言語処理特論 第 2回 56

57 フォルマント () 母音によって声道の共振周波数が異なる この声道の共振周波数を フォルマント (formant) という 周波数の低い方から 第 フォルマント 第 2フォルマント と呼ぶ 個人差はあるが 同じような周波数になっている 日本語の母音は 第 フォルマンと第 2フォルマントでほぼ決定される 母音の多い言語は第 3フォルマントも重要 東北弁は第 3 フォルマントも重要? あいうえお と発声したスペクトル 57

58 フォルマント (2) フォルマントは 音声の現象を説明するために便利な特徴 フォルマント ( の中心周波数 ) は変動が比較的大きいため パターン認識の特徴量としては あまり有用でない フィルタバンク分析で似たようなものが得られると考えられる 58

59 基本周波数とピッチ () 基本周波数 音声波形の 物理的 な高さを表す 声帯の振動周期に対応 無声音の場合 基本周波数はない ( 声帯が振動しないため ) ピッチ 音声波形の 心理的 な高さを表す 有声音の場合は 基本周波数に同じ 無声音の場合は 前後の有声音区間のピッチから補間的に決まる 普通の会話の場合 成人男性で 00~50Hz 成人女性で 200~300Hz 程度 59

60 基本周波数とピッチ (2) /a/ この間隔が基本周波数 第 フォルマント この間隔が基本周期 第 2 フォルマント 調波構造 ( 基本周波数とその整数倍の周波数成分からなる構造 ) 60

61 基本周期とピッチ (3) /a sh i t a/ 青線が基本周波数 /sh/ と /t/ は無声音のため基本周波数は検出されない 聴覚的には /a/ の基本周波数と同じピッチとして知覚される /a/ /sh/ /t/ /a/ 6

62 基本周波数とピッチ (4) ピッチそのものよりも 対数ピッチが使われる 変動が指数関数的なため ピッチは基本周波数と関連しており 個人による変動が大きいので 音声認識の特徴量としては ( 今のところ ) あまり有用ではない 同音異義語判別等には役立つ ( はず ) 62

63 音の強さ 大きさ () 音の 物理的 な強さ 音圧レベル (Sound Pressure Level; SPL) 6 基準値 ( 20 0 [Pa]) の何倍か ( 単位 :db SPL) 音の 聴覚的 な強さ ラウドネス 単位 : ホン (phon) フォン ホーンとも 同じ音圧レベルでも 周波数によって感じる強さが異なる 等ラウドネス曲線 ( 次ページ ) 周波数重みづけ音圧レベル 人間の感じる うるささ に近い A 特性の場合 単位は dba 63

64 音の強さ 大きさ (2) 等ラウドネス曲線 64

65 音の強さ 大きさ (3) PLP Perceptual Linear Prediction 窓かけ FFT 等ラウドネス曲線による重み付け パワースペクトル 自己相関係数 線形予測分析 線形予測係数というやり方で求める特徴量 PLP 以外でも 等ラウドネス曲線による重み付けは用いられる MFCC に用いても良いが あまり使われていない 65

66 テンプレートマッチングによる 音声認識 音声言語処理特論 第 2回 66

67 音声認識 問題の枠組み 部分的な音声特徴量時系列パターンからモデルを学習 その部分パターンを何らかの規則に基づいて組み合わせる ( 並べる ) スコアが最も高くなる組合せ ( 並べ方 ) を認識結果とする 問題の難しさ 時系列パターンを表すのにどのようなモデルを用いれば良いか? パターンの組み合わせをどのように決定するか? 規則をどのように学習するか? 時系列パターンの変動にどのように対処するか? 音声言語処理特論 第 2回 67

68 音声パターンの多様化の原因. 発声者による変動 ( 個人差 ) 2. 調音結合による変動 3. 発声時期差による変動 4. 音声速度の変動 5. アクセント イントネーション 6. 有声無声 母音 鼻音 破裂 摩擦の混在 7. その他の要因 声帯振動数 声道形等の発声器官の構造差方言 発声習慣などの調音法の相違 発声器官の連続運動 変化による音声生成 ( ディジタル音韻列 アナログ音声 ) 発声器官の生理変化 調音法の変化 ( かぜ 脱歯 疲労など ) 音韻 音節などの離散記号の非線形時間軸変換 韻律情報の音声への付与 種々の調音機構への依存 ノイズ ( 背景雑音 電子ノイズ ) 伝送歪 68

69 テンプレートマッチングによる 音声認識 認識する単語の標準パターンを用意しておく 入力音声をすべての標準パターンと比較して最も 似ている パターンを認識結果とする 今回は 孤立単語発声 を考える 長さの異なる発声も伸縮して比較できなければならない 動的計画法 (Dynamic Programming) によるマッチング (DP マッチング ) Dynamic Time Warping(DTW) とも呼ばれる 69

70 テンプレートマッチングの概念 入力音声パターン 比較して近いものを認識結果とする 標準パターン 標準パターン 2 標準パターン 3 標準パターン N 70

71 長さの違うパターンの比較 入力パターン a a 2 a 3 a I 長さが違う どうやって比較するか? b b 2 b 3 b J 標準パターン 標準パターン N b N b N 2 b N 3 b N JN 7

72 パターンの比較 - step - 特徴ベクトル時系列 ( 音声認識なら ケプストラムベクトル時系列 ) 間の比較 入力パターン 標準パターン a a 2 a 3 a I b b 2 b 3 b J a 3 = (a 3,a 32,, a 3D ) b 2 = (b 2,b 22,, b 2D ) 例えば ユークリッド距離 d D ( ) ( a = a ) 3,b 2 3i b 2i i= 2 72

73 パターンの比較 step2 - 特徴ベクトル時系列間の対応付け 入力パターン 標準パターン a a 2 a 3 a I b b 2 b 3 b J フレームを重複させたり飛ばしたりしながら 全体の対応をとる 73

74 DP マッチングの概念図 () - うまくいく例 - 標準パターン 入力パターン 線形伸縮マッチング 標準パターン 入力パターン 非線形伸縮 (DP) マッチング 74

75 DP マッチングの概念図 (2) - うまくいかない例 - 標準パターン 入力パターン 許されない対応 対応の前後関係の入換え禁止 実際の対応 標準パターン 入力パターン 大きく隔たった対応は禁止

76 標準パターン:BDP マッチングの原理 F は (,) から (I,J) へ至る経路 b J b j j = i + r warping function C = ( i, j) 整合窓 C x = ( I, J ) D( A, B) = min 対称形 F 2 w( k) d( i( k), w( k) j( k)) w( k) = i( k) i( k ) + j( k) j( k ) b 2 b C 2 a C 4 C 3 C = (,) a 2 C 5 a i 入力パターン :A j = i r ai D( i, j) + d( i, j) D( i, j) = min D( i, j ) + d( i, j) D( i, j ) + 2d( i, 非対称形 j) w( k) = i( k) i( k ) 76

77 DP マッチングのポイント ある格子点において その格子点にたどり着いた時の最小累積距離 2 最小距離になるとき どっちの方向からその格子点にたどり着いたのかこの2 点だけを記憶する 結果として得られる 出発点から到着点までの最短経路がその格子点を通るかどうかは分からないが 仮に通るとすれば 出発点からその格子点までの最短距離と その格子点から到着点までの最短距離の合計になるはずである その格子点にたどり着くための経路は何種類もあるが 直前に通る格子点だけを考えればよい 全ての格子点について 最短経路がそこを通るかもしれない と思って そこに至る最短経路を計算しておく 開始点から順番に計算していくと 最短経路が計算される! 77

78 DP マッチングのやり方 () 2 b5 b4 b3 g(0,x)=g(x,0)= b2 b g(0,0)=0 g(,)=d(a,b) a a2 a3 a4 a5 a6 a7 78

79 DP マッチングのやり方 (2) 2 b5 b4 b3 b2 b g(,2)=d(a,b2)+g(,) g(,)=d(a,b) a a2 a3 a4 a5 a6 a7 79

80 DP マッチングのやり方 (3) 2 b5 b4 b3 b2 b g(,2)=d(a,b2)+g(,) g(2,)=d(a2,b)+g(,) a a2 a3 a4 a5 a6 a7 80

81 DP マッチングのやり方 (4) 2 b5 b4 b3 b2 b g(2,2)=min{ d(a2,b2)+g(,2), d(a2,b2)+g(2,), 2 d(a2,b2)+g(,) } b(2,2)=argmin{ d(a2,b2)+g(,2), d(a2,b2)+g(2,), 2 d(a2,b2)+g(,) } a a2 a3 a4 a5 a6 a7 DP 距離 ( 累積距離 ) バックポインタ ( どっちから来たか ) 8

82 DP マッチングのやり方 (5) 2 b5 b4 b3 g(,3)=d(a,b3)+g(,2) b2 b a a2 a3 a4 a5 a6 a7 82

83 DP マッチングのやり方 (6) 2 b5 b4 b3 b2 b g(2,3)=min{ d(a2,b3)+g(,3), d(a2,b3)+g(2,2), 2 d(a2,b3)+g(,2) } b(2,3)=argmin{ d(a2,b3)+g(,3), d(a2,b3)+g(2,2), 2 d(a2,b3)+g(,2) } DP 距離 バックポインタ a a2 a3 a4 a5 a6 a7 83

84 DP マッチングのやり方 (7) 2 b5 b4 b3 b2 b g(3,3)=min{ d(a3,b3)+g(2,3), d(a3,b3)+g(3,2), 2 d(a3,b3)+g(2,2) } b(3,3)=argmin{ d(a3,b3)+g(2,3), d(a3,b3)+g(3,2), 2 d(a3,b3)+g(2,2) } a a2 a3 a4 a5 a6 a7 84

85 DP マッチングのやり方 (8) 2 b5 b4 g(7,5) DP 距離 b(7,5) バックポインタ b3 b2 b a a2 a3 a4 a5 a6 a7 85

86 DP マッチングのやり方 (9) 2 b5 b4 b3 b2 g(7,5) DP 距離 b(7,5) バックポインタ バックトレース b a a2 a3 a4 a5 a6 a7 86

87 DP マッチングのやり方 (0) バックトレースの結果から 入力パターン 標準パターン a a 2 a 3 a 4 a 5 a 6 a 7 b b 2 b 3 b 4 b 5 このようなフレームの対応のときに最小距離となることが分かる 87

88 DP パス ある格子点に至る経路を制限するためのもの 対称形 2 非対称形 上に行き続けたり 横に行き続けたりできる そんな極端なフレーム対応になることは少ない 不都合な場合が多い そうできないようにしたい! 88

89 傾斜制限付き DP パスの例 整合窓の範囲を変える ( 傾斜制限 ) (i,j) g( i-2, j-) + 2 d(i-, j) + d(i, j) g(i, j) = min g( i-, j-) + 2 d(i, j) g( i-, j-2) + 2 d(i, j-) + d(i, j) j (i,j) i (i,j) g( i-2, j-) + d(i-, j) + d(i, j) g(i, j) = min g( i-, j-) + d(i, j) g( i-, j-2) + d(i, j) フレームスキップを含む場合 g( i-2, j-) + d(i, j) g(i, j) = min g( i-, j-) + d(i, j) g( i-, j-2) + d(i, j-) + d(i, j) 89