Динамічна трансформація часу (DTW) вимірює, наскільки схожі два часові ряди, навіть коли вони йдуть із різною швидкістю або зсунуті у часі. Вона розтягує й стискає вісь часу, щоб сумістити подібні форми.

Матриця вартостей

Для рядів x (довжина n) та y (довжина m) задаємо локальну вартість d(i,j) = (x_i − y_j)². Накопичена вартість задовольняє рекурентність динамічного програмування

D(i,j) = d(i,j) + min( D(i−1,j), D(i,j−1), D(i−1,j−1) )

із D(0,0)=d(0,0). Теплова карта праворуч показує D; яскрава лінія — це найдешевший шлях деформації з кута в кут, відновлений трасуванням мінімальних попередників назад.

DTW проти евклідової

Звичайна евклідова відстань порівнює x_i з y_i на однаковому індексі, тож невеликий зсув у часі виглядає як величезна різниця. DTW натомість дозволяє індексу i зіставлятися з кількома індексами j, тож дві копії однакової форми з різною швидкістю дають малу відстань — саме це потрібно для розпізнавання мовлення, рукопису та жестів.

Смуга Сакое–Чіба

Необов'язкова смуга змушує шлях триматися в межах |i − j| ≤ r. Це пришвидшує DTW і запобігає патологічним деформаціям ціною заборони дуже великих зсувів у часі.