定式化 テストパターン : T 参照パターン : {R_1, R_2, ... R_V} テストフレームインデックス : m (1 <= m <= M) 参照パターン R_v のインデックス : n (1 <= n <= N_v) R_v におけるフレームのインデックス n (1 <= n <= N_v) テストパターンのフレーム t(m) と参照パターンのフレーム r_v(n) の 局所的な距離 : d(m, n, v) 各テストフレームに対する累積距離 : d_A(m, n, v) 仮定 - 最大のpath伸縮を2倍までとする n = 1 の場合 d_A(m, 1, v) = d(m, 1, v) + min | min [d_A(m-1, N_r, r)] | | 1 <= r <= V | | | | d_A(m-1, 1, v) | - すべての参照パターンの最終状態からの遷移の最小コスト候補 - 同じ参照の先頭フレームを繰り返しマッチングさせる場合 n >= 2 の場合 d_A(m, n, v) = d(m, n, v) + min (d_A(m-1, j, v)) n-2 <= j <= n - j のループは,(m-1, n-2), (m-1, n-1), (m-1, n) のそれぞれから (m, n) に遷移するパスを比較することに対応する - 実際には argmin のインデックスも保存する必要がある 最終解 D^* = min [ d_A(M, N_v, v) ] 1 <= v <= V テストパターンの最終フレームに対して, すべての参照パターン v について、 参照パターンの最終フレームに対応する累積コストの最小値を求める。 実際にはそのような解が得られる添字を「最後のラベル」とする。 バックトレースして,テストパターン全体と、参照パターンの アラインメントを求める。