# Module 27: Recognition: OCR and Speech With CTC

> Text and speech recognition without alignments: PP-OCR and SVTR, the CTC loss and its recursion worked by hand, speech recognition and error rates.

- Part VII: Beyond Text · elective · Specialized · 3 hours
- By the end you can train a sequence recognizer without alignments, and compute CTC by hand.
- Builds on: [Module 4: How a Model Learns From Data](https://transformers-and-math.drmhse.com/md/04-how-a-model-learns.md), [Module 6: Attention](https://transformers-and-math.drmhse.com/md/06-attention.md)
- Web page (interactive figures, labs and equation explainers): https://transformers-and-math.drmhse.com/modules/27-recognition-with-ctc
- From *Transformers & Math* by Mike Chumba: https://transformers-and-math.drmhse.com

Reading text from images and transcribing speech share a shape: a long sequence of frames (pixel columns or audio slices) in, a shorter sequence of characters or words out, and no labels saying which frames belong to which character. This module covers a production OCR system built on a vision transformer, the loss that trains without alignments, the same idea in speech, and how recognizers are scored.

## 27.1 PP-OCR and SVTR

PP-OCR is Baidu's open-source optical character recognition (OCR) system, widely used on servers and small devices. A detector finds each text line, and a recognizer reads one cropped line at a time. The recognizer, **SVTR** ("Single Visual model for scene Text Recognition", Du et al., 2022), is a vision transformer alone, with no language model. Like ViT (section 25.2) it attends over patches, but a text line is short and very wide and must become a left-to-right sequence, so SVTR shrinks the height step by step to a single row of vectors.

```mermaid
graph TD
    TextLine["Cropped text line image, H x W x 3 (e.g. 32 x 320 x 3)"] --> PatchPart["Patch embedding: each vector covers 4 x 4 pixels -> 8 x 80 grid"]
    PatchPart --> Stage1["Stage 1: local and global mixing blocks (8 x 80)"]
    Stage1 --> Merging1["Patch merging: halve the height, keep the width (4 x 80)"]
    Merging1 --> Stage2["Stage 2: local and global mixing blocks (4 x 80)"]
    Stage2 --> Merging2["Patch merging: halve the height again (2 x 80)"]
    Merging2 --> Stage3["Stage 3: mixing blocks (2 x 80)"]
    Stage3 --> Combine["Combining: pool the height to 1 -> a sequence of 80 vectors"]
    Combine --> CTCHead["Linear layer: one character distribution per position, trained with CTC"]
    CTCHead --> TextOutput["Recognized text: 'Attention Is All You Need'"]
```

> **In words.** A 32 by 320 crop becomes an 8 by 80 patch grid; two merges halve the height, and pooling squeezes it to one row of 80 vectors. A linear layer gives each a character distribution, and CTC (section 27.2) turns the 80 guesses into a transcript.

> **Interactive figure** `svtr-shapes`, on the web page: https://transformers-and-math.drmhse.com/modules/27-recognition-with-ctc#figure-svtr-shapes
>
> **Try:** A 32 × 320 crop becomes an 8 × 80 grid of patches. Before stepping through the stages, predict how many output positions are left at the end, and why the width is never reduced.
>
> **What happens:** 80 positions, one per 4-pixel-wide column. The height shrinks to 1 so each position describes one vertical slice of the line; the width is kept so neighbouring letters stay in separate positions, which the CTC decoder needs to spell them out.

> **In words.** The tensor's shape through SVTR, each stage drawn as a labelled grid: crop, eight-by-eighty patches, two height-halving merges, and a final row of eighty vectors.

### Key Ideas in SVTR

1. **Local and global mixing.** Characters are small strokes (a bar, a loop, a dot), but words need context along the line. *Local mixing* attends within a small window to pick up strokes; *global mixing* attends across the line to relate characters.
2. **Shrinking the height, not the width.** After the patch embedding, SVTR never reduces the width of its $1:10$ input, so neighboring letters stay in separate positions: 80 for a 320-pixel line, plenty for one line's characters.

## 27.2 The Alignment Problem and the Blank

The model produces $T$ outputs, one per **frame** (an image column position or an audio slice), for a target of $U < T$ labels: say $T = 80$ frames for $U = 15$ characters. Nobody labels "the letter a spans frames 12 to 15".

**Connectionist Temporal Classification (CTC)** (Graves et al., 2006) adds one output symbol, the **blank** $\epsilon$ ("no character here"), defines a rule turning frame-by-frame outputs into a transcript, and trains the model to make the correct transcript likely, summed over every frame-by-frame output that produces it.

### The Collapsing Operator $\mathcal{B}$

An **alignment** (or path) $\pi = (\pi_1, \dots, \pi_T)$ has one character or blank per frame. The collapsing operator $\mathcal{B}$ turns it into a label sequence $\mathbf{l}$ in two steps, in order:

1. Merge runs of the same symbol into one: $(a, a, b) \to (a, b)$.
2. Delete every blank: $(a, \epsilon, b) \to (a, b)$.

For example, both $(c, c, \epsilon, a, t)$ and $(\epsilon, c, \epsilon, a, a, t)$ collapse to `"cat"`.

The order makes double letters possible: $(c, c, a, t) \to$ `"cat"` but $(c, \epsilon, c, a, t) \to$ `"ccat"`. Adjacent identical symbols always merge, so a double letter needs a blank between, and without blanks "book" could never be written. Hence a minimum length: one frame per label plus one per double letter, so "cat" needs $T \ge 3$ and "book" $T \ge 5$.

```mermaid
graph LR
    P1["Alignment 1: [c, c, ε, a, t]"] --> B(("Collapsing operator B"))
    P2["Alignment 2: [ε, c, a, a, t]"] --> B
    P3["Alignment 3: [c, ε, a, ε, t]"] --> B
    B --> Word["Target word: 'cat'"]
```

> **In words.** Three alignments collapse to the same word; the loss adds up the probability of every alignment that does.

## 27.3 The CTC Objective and Its Recursion

With $y_k^t$ the probability of symbol $k$ (blank included) at frame $t$, and frames independent given the input $\mathbf{x}$, an alignment's probability is the product over frames, and the transcript's is the sum over alignments that collapse to it:

$$
P(\mathbf{l} \mid \mathbf{x}) = \sum_{\pi \in \mathcal{B}^{-1}(\mathbf{l})} P(\pi \mid \mathbf{x}) = \sum_{\pi \in \mathcal{B}^{-1}(\mathbf{l})} \prod_{t=1}^T y_{\pi_t}^t
$$

$\mathcal{B}^{-1}(\mathbf{l})$ is the set of alignments that collapse to $\mathbf{l}$. The loss is the negative log-likelihood (section 3.4):

$$
\mathcal{L}_{\text{CTC}} = -\ln P(\mathbf{l} \mid \mathbf{x})
$$

There are $K^T$ paths for $K$ symbols, so CTC computes the sum by dynamic programming, filling a table of partial sums so each shared piece is computed once: the **forward-backward algorithm**. The forward half:

1. Put a blank before, between and after the labels. For "cat" this gives $\epsilon\, c\, \epsilon\, a\, \epsilon\, t\, \epsilon$, which has $2|\mathbf{l}| + 1 = 7$ positions.
2. Let $\alpha_t(s)$ be the total probability of all partial alignments that cover frames 1 to $t$ and end at position $s$ of that extended sequence.
3. To get $\alpha_t(s)$, add up the ways to arrive: stay at $s$, step from $s-1$, or jump from $s-2$ over a blank. The jump is allowed only when the labels on either side of that blank differ, which is the double-letter rule again. Multiply the sum by $y^t$ for the symbol at $s$.
4. At the end, add $\alpha_T$ at the last two positions (the final label, and the final blank).

> **Interactive figure** `ctc-trellis`, on the web page: https://transformers-and-math.drmhse.com/modules/27-recognition-with-ctc#figure-ctc-trellis
>
> **Try:** Fill in the table for "cat" over 5 frames. Before stepping, predict which cells can never be reached, whatever the probabilities.
>
> **What happens:** Cells too far from the start to reach in time (a path can move at most two rows per frame) and cells too far from the end to finish in time. The reachable cells form a band down the table; every path from the top-left corner to the last two rows of the last column is one alignment of "cat".

> **In words.** The CTC table for a short word, rows the word with blanks inserted and columns the frames. Each step fills a column from the same row, the row above, or two above when the skip is allowed, times the frame's probability for that symbol. The last two cells of the last column sum to the word's probability.

The table costs $\mathcal{O}(T \cdot |\mathbf{l}|)$ instead of exponential. The backward half runs the same recursion from the end, and together they give the gradient.

> **Measured** (lab 7, `experiments/ctc_alignment.py`). Two checks. First, for every $T$ from 3 to 8, listing every path by brute force and adding up the ones that collapse to `"cat"` gives exactly the same probability as the recursion, to the last bit. Second, counting those paths separately shows how fast they multiply: $1, 7, 84, 462, 1716, 5005$ of them at $T = 3, 4, 6, 8, 10, 12$, out of $4^T$ possible paths in total. At $T = 100$ with $|\mathbf{l}| = 20$, brute force would list $10^{134.2}$ paths, while the recursion fills in $4{,}100$ table entries.

## 27.4 The Same Idea in Speech

Speech is cut into overlapping frames, typically 25 milliseconds every 10, each a vector (often a mel-spectrogram slice, section 28.1). A minute of speech is 6,000 frames and perhaps 150 words, with no word boundaries labelled.

CTC was used for speech first. A *CTC acoustic model* is an encoder, now usually a transformer or a convolution-augmented Conformer, with a linear layer giving a distribution over characters or subword tokens, plus blank, per frame, trained with section 27.3's loss. With frames independent given the input, it decodes fast and can stream, emitting text while the speaker talks.

That independence is also its weakness: it cannot use its own output so far, so it has no built-in language model. *Transducers* (RNN-T) add a small prediction network over the output so far; *encoder-decoder* models (section 8.3) such as Whisper attend over the whole audio and write autoregressively, more accurate but hard to stream. Many production systems train a CTC loss alongside an attention decoder to get both.

## 27.5 Measuring Recognition: Error Rates

The *edit distance* is the fewest single-symbol substitutions $S$, deletions $D$ and insertions $I$ turning the output into the reference transcript. Divided by the reference length $N$:

$$
\text{ER} = \frac{S + D + I}{N}
$$

Over characters it is the *character error rate* (CER), usual for OCR; over words, the *word error rate* (WER), usual for speech. One wrong letter is one character error but a whole word error, so WER is typically several times CER, and insertions let either exceed 100%.

Both texts are first *normalized* for case, punctuation, spacing and number formats, so "3" for "three" is not penalized unless it matters. As with benchmark prompts (section 13.2), the rules change the score, so error rates are comparable only under the same rules.

> **Browser lab** `error-rate`: an experiment that runs in the reader's browser on the web page: https://transformers-and-math.drmhse.com/modules/27-recognition-with-ctc#lab-error-rate

## Exercises

**Exercise (check).** What does the CTC blank symbol mean, and why is it needed even for a word with no repeated letters?

*Solution:* It means "no character at this frame". Besides separating doubled letters, it lets frames between characters, and before and after the word, map to nothing, so a long frame sequence can collapse to a short transcript.

**Exercise (apply).** Collapse the alignment $(\epsilon, b, b, \epsilon, o, o, \epsilon, o, k)$ with the CTC rule.

*Solution:* First merge runs: $(\epsilon, b, \epsilon, o, \epsilon, o, k)$. Then delete blanks: $(b, o, o, k)$, which is "book". The blank between the two runs of $o$ kept them as separate letters.

**Exercise (apply).** What is the minimum number of frames needed to output "letter"?

*Answer:* 7 (within 0)

*Solution:* "letter" has six labels, so at least six frames, plus one blank between each pair of identical neighbouring labels. Only the "tt" pair qualifies, so the minimum is $6 + 1 = 7$ frames.

**Exercise (apply).** A reference has 10 words. The output substitutes one word, drops one, and adds one extra word. What is the WER?

*Answer:* 0.3 (within 0.0001)

*Solution:* $(S + D + I)/N = (1 + 1 + 1)/10 = 0.3$, or 30%.

**Exercise (extend).** Why can a CTC model stream its transcript while the speaker is still talking, while an encoder-decoder model like Whisper usually cannot?

*Solution:* A CTC model predicts each frame's symbol from the encoder's output at that frame, independently of the other predictions, so as soon as the encoder has processed some audio (with limited look-ahead) the corresponding text can be emitted. An encoder-decoder model's decoder attends over the encoded whole utterance before writing, so it normally waits for the audio to finish, or needs special chunking to approximate streaming.

### Core Academic References
- **Du et al. (2022)**: *SVTR: Scene Text Recognition with a Single Visual Model*. IJCAI 2022. [arXiv:2205.00159](https://arxiv.org/abs/2205.00159)
- **Du et al. (2020)**: *PP-OCR: A Practical Ultra Lightweight OCR System*. [arXiv:2009.09941](https://arxiv.org/abs/2009.09941)
- **Graves et al. (2006)**: *Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks*. ICML 2006.
- **Graves (2012)**: *Sequence Transduction with Recurrent Neural Networks* (RNN-T). [arXiv:1211.3711](https://arxiv.org/abs/1211.3711)
- **Gulati et al. (2020)**: *Conformer: Convolution-augmented Transformer for Speech Recognition*. Interspeech 2020. [arXiv:2005.08100](https://arxiv.org/abs/2005.08100)
- **Radford et al., OpenAI (2023)**: *Robust Speech Recognition via Large-Scale Weak Supervision* (Whisper). ICML 2023. [arXiv:2212.04356](https://arxiv.org/abs/2212.04356)
- **Levenshtein (1966)**: *Binary Codes Capable of Correcting Deletions, Insertions, and Reversals*. Soviet Physics Doklady, 10(8): 707–710.