Shared-Stroke Program Synthesis for Cursive Handwriting

In cursive writing, the stroke that joins one letter to the next usually belongs to both letters. The tail of an "o" is also the lead-in of the "n" that follows. Recognizers that work by cutting the ink into pieces must decide which letter owns that stroke, and any hard cut damages at least one of them. We propose treating handwriting recognition as program synthesis, meaning the automatic construction of a small executable program that explains the observed data. Here the program draws the observed pen trajectory. It is written in a tiny drawing language whose operator for joining two glyphs lets a stretch of ink be claimed by two letter subprograms at once. Recognition then proceeds by divide and conquer. First, many short candidate glyph programs are fitted to local windows of ink. Second, they are stitched into one global program that must re-draw the whole word. Boundaries are never cut in advance. They come out of the stitching step, and shared spans are recorded as shared.

The value is not a better black-box recognizer. Implicit sequence models may well match us on raw accuracy. What we aim for is recognition that stays accurate and also gives an explicit, editable alignment of strokes to characters, including on connected script. Current structural systems cannot provide that alignment because they assume each stroke belongs to exactly one symbol. Implicit models cannot provide it because they have no stroke-to-symbol alignment at all. The proposal also gives a clean test of a question from program synthesis: can the chicken-and-egg problem of segmenting versus recognizing be removed simply by making sharing expressible in the language, rather than by designing cleverer segmenters?

Core Claim

Our claim is that ambiguous character boundaries are a limit on what the language can express, not a failure of segmentation. A drawing language in which each ink fragment maps to exactly one glyph cannot represent a ligature correctly, so no search over it can succeed on such inputs. A language with an explicit join operator can represent the ligature. With that operator, a divide-and-conquer synthesizer can fit local glyph programs and then unify them under overlap constraints. The claim predicts three things. It should recover character boundaries on connected cursive markedly better than the same system restricted to one-to-one assignment. It should lose nothing on largely disconnected input such as math expressions. It should work without a lexicon, because verification comes from re-drawing the ink rather than from dictionary lookup.

Relation to Prior Work

Three lines of work supply the method. Synthesis through unification (Alur et al.) and N-PEPS (Learning to Combine Per-Example Solutions for Neural Program Synthesis) find partial programs for pieces of a specification and then combine them. N-PEPS partitions the examples, and its per-example snippets never compete for the same input. We partition a single input along time, and neighbouring pieces explicitly contest the same ink. BEN (A Divide, Align and Conquer Strategy For Program Synthesis) is the closest synthesis ancestor. It splits each example into components (delimited substrings, connected pixel objects), aligns them, and solves each by shallow search. It reports 22.5% of ARC tasks solved with 11 primitives. However, it assumes crisp component boundaries and independent components, and the paper names overlap and overpainting as failure modes. Our join operator is aimed at exactly that assumption.

Handwriting work motivates the gap and also constrains the design. Flann's recognition-based segmentation (Recognition-Based Segmentation of On-Line Cursive Handwriting) is structurally the nearest system. It splits ink at points of zero vertical velocity, scores every grouping of 1 to 6 strokes with neural classifiers that include an "other" class, and searches for a non-overlapping partition that spells a word in a 10,748-word lexicon. We differ in three ways: overlap is allowed, verification comes from re-drawing rather than classification, and the lexicon is replaced by a character language model. The structural math recognizer of The Return of Structural Handwritten Mathematical Expression Recognition shows that modular, interpretable pipelines can be competitive: 74.14% expression accuracy and 98.22% symbol segmentation on CROHME-2023. Its authors state that it enforces a one-to-one trace-to-symbol constraint that breaks on ligatures, and that constraint is what we relax. Evidence against hard geometric cuts comes from The Neural-based Segmentation of Cursive Words using Enhanced Heuristics and from the centered-window recognizer COISR. Both rule out a design that segments first and synthesizes second. DeepWriting models ink generatively with end-of-character markers and reports fully connected cursive as unsolved. We reuse its character-annotated IAM-OnDB data for evaluation. Radical trees for Chinese (Chinese character recognition with radical-structured stroke trees) show that a fixed hierarchical grammar reduces confusions but fails when strokes fuse. That result is another instance of the expressivity limit we target, and we leave it as a follow-up domain.

From the literature on language expressivity, we take the lesson that restricting a language keeps search tractable (NoFAQ). That lesson pushes us to add only one operator, rather than a general spline language. From HYSYNTH we take the finding that neural models struggle to emit valid programs in unfamiliar languages. This is why a neural model only proposes glyph candidates, and symbolic unification assembles and checks them.

Research Program

The drawing language has three constructs. Glyph(c, θ) draws character class c as a short parametric curve with style parameters θ (a few control points, slant, and scale). Join(g1, g2, s) places g2 after g1 so that the final portion of g1, of length s, and the initial portion of g2 both explain the same ink span. We use s = 0 for touching glyphs and s > 0 for shared ligatures. Seq concatenates glyphs across pen lifts. For math, relation constructors for superscript, subscript, and fraction layouts wrap subprograms, mirroring the relation stage of the structural pipeline of Seitz et al.

The divide phase slides over the time-ordered ink. At each candidate window a neural proposer, trained on character-annotated ink, suggests the top-$k$ glyph classes, and a few gradient steps fit θ so the rendered glyph matches the window. The windows are deliberately overlapping and over-complete. The conquer phase runs beam search, which is effectively a dynamic program along the time axis. It chains glyph candidates with Join and selects the program $P$ that minimizes

$$ E(P) = D(\mathrm{render}(P), x) - \lambda \log p_{\mathrm{LM}}(\mathrm{chars}(P)) + \mu \, |P| , $$

where $x$ is the observed pen trajectory. $D$ is a time-aligned trajectory distance that charges for both unexplained ink and hallucinated ink, which guards against the over- and under-parsing that CoMER documents for implicit decoders. $p_{\mathrm{LM}}$ is a character-level language model, which does not restrict the output to a vocabulary. $|P|$ is program size, and the weights $\lambda$ and $\mu$ are tuned on validation data. The output is a program. Reading off its glyphs gives the transcription, and reading off the Join spans gives an alignment in which a ligature is attributed to both of its letters.

Two secondary questions come from the synthesis side. The first is how to split a fixed compute budget between proposing and fitting local candidates and running the global beam. N-PEPS leaves this trade-off open, and we will sweep it. The second is how sensitive the method is to a larger language. Following BEN's test of injecting irrelevant primitives, we will add distractor glyph variants and measure how accuracy and search time degrade.

Baselines

The naive reference is a segment-first pipeline. It cuts the ink at zero vertical velocity, assigns each fragment to one character with the same proposer network, and decodes with the same character language model. It shares our components but has no overlap and no re-drawing check, so it shows what the synthesis machinery adds over classification.

The strongest existing competitor for math is the structural recognizer of Seitz et al., which reports 74.14% expression accuracy and 98.22% symbol segmentation accuracy on CROHME-2023. The strongest implicit competitor is CoMER, which reports an expression recognition rate of 59.33%, 59.81% and 62.97% on CROHME 2014, 2016 and 2019. On math we do not expect to beat Seitz et al. on expression accuracy. Most math traces are disconnected, so the one-to-one constraint rarely binds. Matching them within about one point while keeping full alignment would support the claim that the join operator costs nothing where it is not needed. Where these systems are reproducible, we will retrain or re-evaluate them on our splits rather than rely only on reported numbers.

For connected cursive words, the strongest competitor is an implicit online recognizer, a Transformer with CTC (connectionist temporal classification, a loss that trains a sequence model to emit labels without explicit alignment). It will be trained on the character-annotated IAM-OnDB data of DeepWriting with the same training data, the same character language model, and a matched tuning budget. No reported result was found on Lacuna for online word recognition on the DeepWriting-annotated IAM-OnDB split. The offline IAM character error rate of 5.14% in Rethinking HTG Evaluation comes from a different modality and will not be used as a comparison. We count as beating this baseline either of two outcomes: character error rate within 10% relative of it together with substantially lower boundary error, or strictly lower character error rate on the out-of-vocabulary split. For boundary error we extract timings from the CTC model's peak alignments, which is the best alignment such a model can offer.

A Flann-style baseline reimplements his method (Flann): non-overlapping groupings of 1 to 6 strokes, an "other" class, and bidirectional best-first search. It is run once with a lexicon built from the training vocabulary and once with our character language model. His own reported mean errors, 6.2% for writers seen in training and 10.8% for unseen writers, are on a private 10-writer set and are not directly comparable.

The key ablation removes Join and keeps everything else, which yields a one-to-one synthesizer. A second ablation keeps Join but drops the re-drawing term $D$, which tells us whether the gain comes from expressing overlap or from verifying by reconstruction.

Why not just…?

Why not just train an end-to-end sequence model? On transcription accuracy this is a serious threat, and we expect it to be competitive or better on in-vocabulary words. Its weaknesses are the missing stroke-to-character alignment, which the structural HMER work identifies as blocking pen-based editing, and the coverage errors on long inputs that CoMER needed a dedicated module to fix. The cursive experiment measures boundary error and out-of-vocabulary error directly. If the CTC model matches us on both, the proposal's case reduces to interpretability alone, and we will report that plainly.

Why not just over-segment finely and keep a one-to-one assignment with an "other" class for ligature pieces? This is the most dangerous alternative, because Flann's "other" class already absorbs connecting ink. It may turn out that shared spans can always be handed to one side or discarded without loss. The ablation with Join removed, run over the same fine windows, tests this exactly. We predict the gap will appear on letter pairs whose joining stroke is also part of a letter's shape, such as "o", "v" and "w" into the next letter. If no gap appears, we will conclude that sharing need not be expressible and that the benefit comes from verification by re-drawing. The second ablation isolates that alternative explanation.

Why not just use a generative ink model like DeepWriting for analysis-by-synthesis? Its end-of-character signal gives exactly one boundary point per character, so it cannot represent a span that belongs to two characters. Its authors also report that fully connected cursive fails. Nothing constrains its samples to a checkable structure. We will still use its annotated data, and we will use its predicted end-of-character timings as one more point of comparison for boundary error.

Proposed Experiments

The decisive experiment uses the character-annotated IAM-OnDB. We derive a "connected" test subset of words in which the annotated end of one character and the start of the next fall within a single pen-down trace. We report character error rate, mean absolute boundary error in timesteps (where a shared span counts as correct if both of its endpoints are covered), and out-of-vocabulary character error rate on words absent from training. The comparison covers the full system, the Join ablation, the ablation without re-drawing, the CTC model, and the Flann-style search. The core claim holds if the full system beats the Join ablation on boundary error on the connected subset, with a clearly larger gap there than on disconnected words.

The no-harm check runs on CROHME-2023 and CROHME 2014/2016/2019, with stroke-level ground truth from CROHME+ and MathWriting+. It reports expression accuracy and symbol segmentation against the numbers of Seitz et al. and CoMER. The synthesis-side analyses measure accuracy against the fraction of compute spent on local proposals versus global unification, and robustness when 25% and 50% distractor glyph variants are added to the language. The result that would sink the proposal is the over-segmented one-to-one ablation matching the full system on the connected subset, since that would show the join operator adds nothing.