Handwriting recognition without AI: DTW on kana strokes

In Sumi, my iOS app for learning Japanese kana, you draw a character with your finger and the app tells you, stroke by stroke, whether your tracing is correct. All of it offline, with no account, no cloud call, and no machine learning model. This post aims to explain, in the simplest way possible, how that works thanks to a classic algorithm: DTW (Dynamic Time Warping).

Why not a machine learning model?

The modern reflex would be to train a small neural network. But here it was overkill, for three reasons:

1. We already have the ground truth. Every kana has a canonical tracing provided by KanjiVG: the stroke order, their shape, their direction. No need to learn what we already know.

2. The product constraints. 100% on-device, offline, deterministic, and debuggable. A model means weights to bundle, a black box, and false positives that are hard to explain.

3. The problem is geometric. "Does this stroke look like that one?" is a question of curve comparison, not classification.

So the real challenge isn't guessing which character, but measuring how closely the user's tracing matches the model. And that's where it gets tricky: two tracings of the same shape are never sampled the same way. We draw faster or slower, with more or fewer points. That's exactly what DTW is good at.

The idea in four steps

Everything lives in a single file, strokeMatch.ts, and the flow boils down to this:

1. Resample each stroke to a fixed number of points along its curve → invariance to speed.
2. Normalize into the unit square [0,1] → invariance to canvas size.
3. Align each user stroke with its canonical stroke via DTW → a similarity cost.
4. Convert that cost into a 0–100 score, with a penalty if the stroke count is wrong.

Let's go through each step :)

Step 1: arc-length resampling

The user might draw 80 points, the model has 40, spread out unevenly. So we reproject everything onto 32 evenly spaced points along the curve:

const RESAMPLE_N = 32;

export function resamplePath(points: Point[], n: number): Point[] {
  const total = pathLength(points);          // total arc length
  const step = total / (n - 1);              // target spacing
  const out: Point[] = [points[0]];
  // ... walk along the segments, placing a point every `step`
  out.push({ ...points[points.length - 1] });
  return out;
}

The result: two tracings of the same shape become comparable point by point, no matter the drawing speed.

Step 2: normalization

The mobile canvas is, say, 300 px; KanjiVG is 109. We bring both into [0,1] using a fixed reference edge:

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

Step 3: the core, DTW

DTW aligns two sequences that "tell the same story" but at a different pace. Through dynamic programming, it finds the minimum-cost matching path between the two point sequences, allowing one point of the first to match several points of the second: that's the warping.

The best way is to see it. Below, the canonical tracing (orange) and the user's (cream), shifted in time. The dashed lines are the matches found by DTW:

When the dashed lines aren't vertical, that's DTW "stretching" time to make two shifted shapes line up. Without a guardrail, it can produce absurd alignments (the start of one stuck to the end of the other). So we add a Sakoe-Chiba band: we only allow matching i and j if |i − j| stays within a band of 25% of the length. Wide enough to absorb pacing differences, tight enough to penalize globally wrong shapes.

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); // average per-sample cost
}

Step 4: from cost to score

DTW returns an average per-sample distance. We turn it into a 0–100 score with a piecewise-linear function, tuned empirically: a "correct" tracing lands between 0.05 and 0.15, a sloppy one around 0.2, a clearly wrong shape above 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));
}

Finally, we put it all together. Strokes are matched by index (stroke 1 against canonical stroke 1, etc.), and drawing the right shape with the wrong number of strokes is capped hard, because in Japanese the stroke order and count are part of correctness:

let similarity = scoreFromDistance(avgDistance);

if (!strokeCountMatch) {
  const diff = Math.abs(userStrokes.length - data.strokes.length);
  if (diff === 1) similarity = Math.min(similarity, 40); // off by one: forgiving
  else similarity = Math.min(similarity, 20);            // worse: hard cap
}

const isCorrect = similarity >= 55; // auto-accept threshold, conservative

Key Points to Understand

1. Resampling: we fix the number of points (32) along the curve to cancel out drawing speed.

2. Normalization: we bring everything into [0,1] to compare a mobile canvas against a 109 KanjiVG viewBox.

3. DTW + Sakoe-Chiba band: the minimum-cost alignment measures shape similarity, and the band (25%) prevents absurd matches.

4. Score + stroke penalty: the average distance becomes a 0–100 score, capped when the stroke count doesn't match.

What it unlocks in the UX

Because DTW returns a per-stroke distance (and not just a global score), you can do a lot:

• Repaint each stroke green, neutral, or red based on its distance, once the tracing is done.
• Replay only the wrong stroke to show the correct gesture.
• Feed the result straight into the spaced-repetition engine, with nothing to ask the user as soon as the 55 threshold is crossed.

No need for AI when you already have the ground truth: KanjiVG plus a good old geometric algorithm beat a model to train, at a fraction of the complexity. DTW is half a century old (popularized for speech recognition in the 70s), and it's a great reminder that a classic algorithm, well applied, is often the simplest and most explainable solution. Now it's your turn :)