---
title: "CTC decoding"
url: https://recursiveai.org/oneocr/docs/decoding/
description: "Input: per-step class scores (logits, T steps of C classes, class 0 the CTC blank) from a recognizer, and the charset. Output: text and a confidence.…"
version: "1.0.0"
source: https://github.com/recursive-ai-oss/oneocr-csharp/blob/8db430fb77c4d86d51686f15dfd9b5ccc20c99a7/docs/spec/decoding.md
---

# CTC decoding

Input: per-step class scores (`logits`, `T` steps of `C` classes, class 0 the CTC blank) from a recognizer, and the charset.
Output: text and a confidence. Every mode gives the same bits on every CPU path, OS and degree of parallelism.

## Greedy (default)

Arg-max per step (lowest index on ties), merge repeats, drop blanks (Graves et al. 2006, sec. 3.1). Confidence: mean over
emitted characters of the largest softmax probability seen while that character was the winning class (0 for empty text).

## Beam search

Prefix beam search over CTC alignments (Graves et al. 2006; Hannun et al. 2014, "First-pass large vocabulary continuous speech
recognition using bi-directional recurrent DNNs").

### Arithmetic

All beam arithmetic is IEEE double precision with `+ - * /` and comparisons only, evaluated in the order written here, no fused
multiply-add. The exponential and logarithm are our own:

* `exp(x)`: `x <= -700` (or NaN) gives 0, `x > 700` is clamped to 700; `k = floor(x * 1.4426950408889634 + 0.5)`;
  `r = (x - k * 6.93147180369123816490e-01) - k * 1.90821492927058770002e-10`; the degree-13 Taylor polynomial of exp in Horner form
  with coefficients `1/n!` (`n = 13 … 0`), each step `p = p * r + c`; the result is `p * 2^k` built from the exponent bits.
* `ln(x)`: `x = m * 2^e` with `m` in `[1, sqrt 2)` (halve `m` and add 1 to `e` when it is above `sqrt 2`);
  `s = (m - 1) / (m + 1)`, `z = s * s`, `q` the Horner form of `1 + z/3 + z²/5 + … + z⁹/19` (coefficients `1/(2j+1)`), result
  `e * 0.6931471805599453 + 2 * s * q`.
* `logadd(a, b) = a + ln(1 + exp(b - a))` for `a >= b`; `a` when `b` is minus infinity or `b - a < -40`.

Log probabilities of classes: `lp(j) = (z_j - max) - ln(S)`, with `z` the float logits, `max` their largest, `S` the float sum
of `exp(z_j - max)` accumulated as in `numerics.md` (the same 16-lane order as the softmax elsewhere). The `float` subtraction
is exact; the rest is double.

### Steps

State: a set of prefixes (at most `BeamWidth`), each with `pb` and `pnb`, the log probabilities of the steps so far with the
prefix emitted and the last step blank / non-blank. Start: the empty prefix with `pb = 0`, `pnb = -inf`.

For each step `t`:

1. Candidates: the classes `j >= 1` whose logit is within 9.2 of `max`, at most 8, best first (equal logits keep the lower class).
2. For each prefix `p` with `total = logadd(pb, pnb)` and last class `c` (none for the empty prefix), in beam order:
   * `p` gets `pb += total + lp(0)`;
   * if `c` exists and `pnb` is not `-inf`: `p` gets `pnb += pnb + lp(c)` (the run of `c` continues);
   * for each candidate `j`, the extended prefix `p·j` gets `pnb += (pb if j == c else total) + lp(j)`.
   Contributions to the same prefix are combined with `logadd`; new prefixes are listed in creation order.
3. Rank the resulting prefixes by `logadd(pb, pnb) + R(prefix)` (below), best first, ties to the prefix created earlier, and keep
   the first `BeamWidth`.

After the last step each kept prefix gets `final = logadd(pb, pnb) + R_end(prefix)`; the best (ties: created earlier) is the
text. If a language model is set (whether or not a script fits the line), the best prefix whose code words (below) match the greedy
reading's is taken, and the greedy reading if none does.

Confidence: `exp(logadd(pb, pnb) / n)` of the chosen text with `n` emitted characters, clamped to `[0, 1]` (0 for empty text).
It is the per-character geometric mean of the probability of the text over all alignments, and is not calibrated.

### Prefix score `R`

A *word* is a run of non-space characters in the prefix (the space is the charset entry `" "`). `R` is the sum of a part for the
finished words, `InsertionBonus` per character, and a part for the open word.

* **Language model** (when set): for a script chosen once per line (the model whose alphabet contains the most letters of the
  greedy text's characters; the first on ties; none if no letter fits), each character `s` of a word that is not *protected*
  adds `LanguageModelWeight * max(LogProb(context, fold(s)) - mean, -1)`, where `fold` is the simple lowercase mapping (see
  `char-lm-v1.md`), `mean` is the file's mean and the context is the word's earlier symbols led by the word start. A finished word additionally adds the same for the word end. The open word counts
  without the word end in `R` and with it in `R_end`.
* **Protected words**: a word is protected, and gets no language-model score, if it contains a decimal digit, one of
  `@ # _ / \ = % + * ~ ^ | < > [ ] { }`, or a character whose folded form is outside the script's alphabet.
* **Lexicon** (when set): the open or finished word adds `LexiconBoost` when it spells a lexicon word exactly (same code points)
  and `LexiconBoost / 2` when it is a proper prefix of one and at least two characters long; nothing otherwise. Words with
  characters not in the charset are dropped from the lexicon.

### Code words

The code words of a text are its space-delimited words that contain a decimal digit or one of the symbols above, in order.
Beam search with a language model returns a reading only if its code words are those of the greedy reading, position by position,
except that a word listed in the lexicon may stand in for the one it replaces. Numbers, identifiers, amounts and dates are
therefore read exactly as greedy decoding reads them; the language model only changes the other words.

## Parameters

| name | default | meaning |
|---|---|---|
| mode | greedy | greedy or beam |
| BeamWidth | 8 | 1 to `OcrLimits.MaxBeamWidth` (64) |
| LanguageModelWeight | 0.8 | at least 0 |
| LexiconBoost | 2 | at least 0 |
| InsertionBonus | 0 | per emitted character |

The candidate count (8), the 9.2 window and the −1 floor were chosen on held-out synthetic lines (see the decoding evaluation in
`bench/README.md`) and are part of this version.

## Limits

Before the search starts, `steps * BeamWidth * 9 + 1` (the most prefixes it can create) is compared with
`OcrLimits.MaxBeamNodes` (default 2^22), and `BeamWidth` with `OcrLimits.MaxBeamWidth`.

## Words and approximate boxes (greedy only)

Words, their raw and calibrated confidences and their script are defined in [model-container-v1.md](https://recursiveai.org/oneocr/docs/model-container/#calibration-version-1). Boxes come from the greedy alignment: a character occupies the steps `[first, last]` of its run, and a step is `width / T` pixels of the line image (`width` the scaled line's width, `T` the number of steps). A word's left edge is the first step of its first run, or halfway across the gap to the previous run when there is one: `(prev.last + 1 + first) / 2`, in steps; its right edge is `last + 1` of its last run, or halfway to the next run, `(last + 1 + next.first) / 2`. Neighbouring words therefore tile the line, and the line's first and last word stop where the network first and last fired. Edges are computed in double precision, scaled by `width / T`, mapped back to page pixels by the crop's own ratio and rounded to float32. Vertical edges are those of the whole line's ink. These boxes are approximate and flagged so; beam search keeps no alignment, so words are always read greedily.