グラフィカルタイムワーピング（GTW）は、複数の時系列またはシーケンスのペアを共同で整列させるためのフレームワークである。動的タイムワーピング（DTW）が各ペアを独立に整列させ、与えられたペア内の2つのシーケンス間の距離のみを最小化するのとは異なり、GTWは各シーケンスペアの整列精度とペア間の類似性の両方を考慮する。この共同最適化により、GTWはペア間の類似性が期待される場合により良い整列性能を達成でき、DTWを特殊なケースとして一般化する。
このフレームワークは、相互依存する時系列またはシーケンスで構成される任意のデータに適用可能である。応用には、タイムラプス生体イメージングデータにおける信号伝播解析、署名識別、両眼立体視による深度計算、およびプロテオミクスデータ解析における液体クロマトグラフィー質量分析法（LC-MS）プロファイル整列が含まれる。これらの設定では、隣接または関連するシーケンスがしばしば類似したワーピングパターンを示すことがあり、GTWはこれを利用して整列品質を向上させる## 定式化
GTWは、ワーピングパスの集合に対する最小化問題として共同整列問題を定式化する。\(N\)個の時系列ペア\((x_n, y_n)\)（\(n = 1, 2, ..., N\)）が与えられ、各ペアには対応するワーピングパス\(P_n\)がある。一部のワーピングパスペアは類似していることが既知であり、集合\(Neib\)で表される。。目的関数は次の最小化である:
\[\min_{\{P_n\}} \left( \sum_{n=1}^{N} cost(P_n) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
ここで、\(cost(P_n)\)は、ワーピング関数\(P_n\)で整列した後の\(x_n\)と\(y_n\)の間の距離である。。項\(dist(P_m, P_n)\)は、2つのワーピングパス間の距離を測定し、\(P_m\)と\(P_n\)によって囲まれた領域の面積として定義される。。ハイパーパラメータ\(\kappa\)は、整列コスト項とワーピング関数距離項のバランスを取る。。類似性の強さはアプリケーション固有であり得る；異なる関連ペア\((m, n)\)に対して、異なるパラメータ\(\kappa_{(m,n)}\)を設定できる。
動的タイムワーピングとの関係
動的タイムワーピングは、累積距離を最小化する最適なワーピングパスを見つけることで2つの時系列を整列させる古典的な手法である。。DTWは各ペアを独立に扱い、グリッド内の最短経路問題を解く。。GTWは、ワーピングパスのペアワイズ距離に対するペナルティを通じて複数のワーピングパスを結合することでこれを拡張する。。\(\kappa = 0\)の場合、GTWは各ペアの独立したDTWに還元される。。\(\kappa > 0\)の場合、ワーピングパスは類似するように促され、これは基礎となるシーケンスが共通の時間的歪みを共有する場合に有益である。
最大フローによる解法
GTWは、DTWと同等の最短経路問題を双対グラフ内の最大フロー問題に変換する。。ワーピングパス間の制約または類似性は、追加のエッジまたは容量としてモデル化される。。この双対グラフ定式化により、共同最適化は標準的な最大フローアルゴリズムを使用して解くことができる。。しかし、大規模データセットでは、汎用の最大フローアルゴリズムは時間とメモリの消費が大きくなる。
スケーラビリティに対処するため、GTW専用に設計された効率的なアルゴリズムであるBidirectional pushing with Linear Component Operations（BILCO）が開発された。。BILCOは双対グラフの構造を活用し、GTWアプリケーションにおける最先端の汎用最大フローアルゴリズムと比較して、計算時間とメモリ使用量の両方で平均10倍の改善を達成する。
GTWは、相互依存する時系列が発生するいくつかの領域で応用されている:
- タイムラプス生体イメージングにおける信号伝播解析: 隣接ピクセルはしばしば類似した伝播パターンを示すため、GTWは波面や細胞シグナルの追跡に適している。
- 署名識別: 手書き署名はシーケンスとして扱うことができ；複数の署名を共同で整列させることで認識が向上する。
- 両眼立体視による深度計算: 左画像と右画像からの視差マップはGTWで整列させ、深度推定を改善できる。
- プロテオミクスにおけるLC-MSプロファイル整列: 複数サンプルからのクロマトグラフィーおよび質量分析プロファイルは、保持時間のずれを補正するための共同整列の恩恵を受ける。