Reconnaissance manuscrite sans IA : DTW sur les kana

Dans Sumi, mon app iOS pour apprendre les kana japonais, vous dessinez un caractère au doigt et l'app vous dit, trait par trait, si votre tracé est correct. Le tout hors-ligne, sans compte, sans appel au cloud et sans modèle de machine learning. Ce post a pour but de vous expliquer, le plus simplement possible, comment c'est possible grâce à un algorithme classique : le DTW (Dynamic Time Warping).

Pourquoi pas un modèle de machine learning ?

Le réflexe moderne serait d'entraîner un petit réseau de neurones. Mais ici, c'était disproportionné, pour trois raisons :

On a déjà la vérité terrain. Chaque kana possède un tracé canonique fourni par KanjiVG : l'ordre des traits, leur forme, leur sens. Inutile d'apprendre ce qu'on connaît déjà.
Les contraintes produit. 100 % sur l'appareil, hors-ligne, déterministe et debuggable. Un modèle, ce sont des poids à embarquer, une boîte noire et des faux positifs difficiles à expliquer.
Le problème est géométrique. « Ce trait ressemble-t-il à celui-là ? » est une question de comparaison de courbes, pas de classification.

Le vrai défi n'est donc pas de deviner quel caractère, mais de mesurer à quel point le tracé de l'utilisateur ressemble au modèle. Et c'est là que ça se complique : deux tracés de la même forme ne sont jamais échantillonnés pareil. On dessine plus ou moins vite, avec plus ou moins de points. C'est exactement ce que le DTW sait gérer.

Le principe en quatre étapes

Tout vit dans un seul fichier, strokeMatch.ts, et le flux se résume ainsi :

Rééchantillonner chaque trait à un nombre fixe de points le long de sa courbe → invariance à la vitesse.
Normaliser dans le carré unité [0,1] → invariance à la taille du canvas.
Aligner chaque trait de l'utilisateur avec son trait canonique via le DTW → un coût de ressemblance.
Convertir ce coût en score 0–100, avec une pénalité si le nombre de traits est faux.

Voyons chaque étape :)

Étape 1 : rééchantillonnage par longueur d'arc

L'utilisateur dessine peut-être 80 points, le modèle en a 40, répartis irrégulièrement. On reprojette donc tout sur 32 points équidistants le long de la courbe :

const RESAMPLE_N = 32;

export function resamplePath(points: Point[], n: number): Point[] {
  const total = pathLength(points);          // longueur d'arc totale
  const step = total / (n - 1);              // espacement cible
  const out: Point[] = [points[0]];
  // ... on avance le long des segments, en posant un point tous les `step`
  out.push({ ...points[points.length - 1] });
  return out;
}

Résultat : deux tracés de la même forme deviennent comparables point à point, quelle que soit la vitesse de dessin.

Étape 2 : normalisation

Le canvas mobile fait, disons, 300 px ; KanjiVG, 109. On ramène les deux dans [0,1] avec un bord de référence fixe :

export function normalizePoints(points: Point[], edge: number): Point[] {
  return points.map((p) => ({ x: p.x / edge, y: p.y / edge }));
}

Étape 3 : le cœur, le DTW

Le DTW aligne deux séquences qui « racontent la même chose » mais à un rythme différent. Par programmation dynamique, il cherche le chemin d'appariement de coût minimal entre les deux suites de points, en autorisant qu'un point de l'une corresponde à plusieurs points de l'autre : c'est le warping.

Le mieux est de le voir. Ci-dessous, le tracé canonique (orange) et celui de l'utilisateur (crème), décalés dans le temps. Les pointillés sont les appariements trouvés par le DTW :

Alignement DTW entre deux tracés

Quand les pointillés ne sont pas verticaux, c'est le DTW qui « étire » le temps pour faire coïncider deux formes décalées. Sans garde-fou, il peut produire des alignements absurdes (le début de l'un collé à la fin de l'autre). On ajoute donc une bande de Sakoe-Chiba : on n'autorise l'appariement de i et j que si |i − j| reste dans une bande de 25 % de la longueur. Assez large pour absorber les différences de rythme, assez serrée pour pénaliser les formes globalement fausses.

export function dtwDistance(a: Point[], b: Point[]): number {
  const n = a.length, m = b.length;
  const band = Math.max(2, Math.floor(Math.min(n, m) * 0.25)); // Sakoe-Chiba
  const dp = new Float64Array(n * m).fill(Infinity);

  dp[0] = distance(a[0], b[0]);
  for (let i = 0; i < n; i++) {
    const jStart = Math.max(0, i - band);
    const jEnd = Math.min(m - 1, i + band);
    for (let j = jStart; j <= jEnd; j++) {
      if (i === 0 && j === 0) continue;
      const cost = distance(a[i], b[j]);
      let best = Infinity;
      if (i > 0) best = Math.min(best, dp[(i - 1) * m + j]);
      if (j > 0) best = Math.min(best, dp[i * m + (j - 1)]);
      if (i > 0 && j > 0) best = Math.min(best, dp[(i - 1) * m + (j - 1)]);
      dp[i * m + j] = cost + best;
    }
  }
  return dp[n * m - 1] / Math.max(n, m); // coût moyen par échantillon
}

Étape 4 : du coût au score

Le DTW rend une distance moyenne par échantillon. On la transforme en score 0–100 avec une fonction linéaire par morceaux, calée empiriquement : un tracé « correct » tombe entre 0.05 et 0.15, un bâclé vers 0.2, une forme clairement fausse au-delà de 0.3.

const PERFECT_THRESHOLD = 0.08; // ≤ → 100
const FAIL_THRESHOLD = 0.30;    // ≥ → 0

function scoreFromDistance(distance: number): number {
  if (distance <= PERFECT_THRESHOLD) return 100;
  if (distance >= FAIL_THRESHOLD) return 0;
  const range = FAIL_THRESHOLD - PERFECT_THRESHOLD;
  return Math.round(100 * (1 - (distance - PERFECT_THRESHOLD) / range));
}

Enfin, on assemble tout. Les traits sont appariés par index (trait 1 contre trait 1 canonique…), et dessiner la bonne forme avec le mauvais nombre de traits est plafonné durement, car en japonais l'ordre et le nombre de traits font partie de la justesse :

let similarity = scoreFromDistance(avgDistance);

if (!strokeCountMatch) {
  const diff = Math.abs(userStrokes.length - data.strokes.length);
  if (diff === 1) similarity = Math.min(similarity, 40); // un trait d'écart : indulgent
  else similarity = Math.min(similarity, 20);            // pire : plafond bas
}

const isCorrect = similarity >= 55; // seuil d'auto-acceptation, prudent

Points clés à comprendre

Rééchantillonnage : on fixe le nombre de points (32) le long de la courbe pour neutraliser la vitesse de dessin.
Normalisation : on ramène tout dans [0,1] pour comparer un canvas mobile à un viewBox KanjiVG de 109.
DTW + bande de Sakoe-Chiba : l'alignement de coût minimal mesure la ressemblance de forme, la bande (25 %) empêche les appariements absurdes.
Score + pénalité de traits : la distance moyenne devient un score 0–100, plafonné si le nombre de traits ne correspond pas.

Ce que ça permet côté UX

Comme le DTW rend une distance par trait (et pas juste un score global), on peut faire beaucoup :

Repeindre chaque trait en vert, neutre ou rouge selon sa distance, une fois le tracé terminé.
Rejouer uniquement le trait fautif pour montrer le bon geste.
Brancher le résultat directement dans le moteur de répétition espacée, sans rien demander à l'utilisateur dès que le seuil de 55 est franchi.

Pas besoin d'IA quand on a déjà la vérité terrain : KanjiVG plus un bon vieil algorithme géométrique battent un modèle à entraîner, pour une fraction de la complexité. Le DTW a un demi-siècle (popularisé pour la reconnaissance vocale dans les années 70), et c'est un bel exemple qu'un algorithme classique, bien appliqué, reste souvent la solution la plus simple et la plus explicable. À vous de jouer :)