wikillm

Paper · 2018-05-09 · cs.CV

Edit Probability for Scene Text Recognition

Scores a scene-text attention decoder by edit probability: the total probability, over all keep, drop and insert edit paths, that its per-step outputs spell the label. Training on its negative log avoids the damage that missing or extra characters do to frame-wise losses. Author-reported: a ResNet-based model with EP reaches 73.9% lexicon-free on ICDAR 2015, up from 63.3%.

Optical character recognitionAttention mechanismSequence-to-sequence learningscene-text-recognitionattentionloss-functionsequence-alignmentlexicon-decoding

arXivPDFMarkdown12 min read

AI-compiled by claude-haiku-5-5 on 2026-11-22, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

A scene-text reader looks at a cropped picture of a word and outputs one letter per step. Training usually compares each output step with the letter at the same position in the correct word. If the reader skips a letter or invents an extra one, every later comparison is shifted by one, and the training signal blames the wrong steps.

The idea here is to score the whole word instead. The model's per-step guesses can be turned into the correct word by keeping a guess, dropping one, or inserting a missing letter. Adding up the probabilities of all such edit routes gives one number for how likely the correct word is. Training on that number lets the error land on the missing or extra letter, not on the letters that were read correctly around it.

The authors report that this improves accuracy on several standard scene-text benchmarks, with and without a list of allowed words.

TL;DR

  • Attention-based scene-text readers are usually trained with a frame-wise likelihood, which breaks when characters are missing or extra §1 fig. 1.
  • Edit probability (EP) sums the probabilities of all keep, delete and insert edit paths that turn the decoder's per-step outputs into the label §3.2.
  • A dynamic programme computes it in O(|T|·|y|) time eq. 14. Training minimises the negative log of EP §3.3.
  • The authors report the best numbers on unconstrained benchmarks with a ResNet-based encoder; several details that an implementation needs are not stated §4.2 tab. 1.

Problem

Attention decoders emit one probability vector per output step. The label and the output can be misaligned when the reader misses a character or outputs a superfluous one. The frame-wise loss then propagates error to correctly read steps that come after the mismatch §1 fig. 1. The authors also report that misalignment makes the training less efficient and degrades accuracy §1 §4.4 fig. 4.

Method

The method keeps a standard attention decoder and adds three learned outputs. It then defines EP over edit operations on the output sequence §3.1 §3.2.

  1. Attention decoder. An LSTM with attention over encoder features h produces, at each step j, a probability vector y_j over the alphabet including EOS (written #) §3.1 eq. 1.
  2. Extra heads. From the same LSTM state s_j, a three-way softmax gives R_j = (R^C, R^I, R^D), the probabilities of consumption, insertion and deletion at step j. A second softmax I_j gives a character distribution for an inserted character. The weights W_R and W_I are trained §3.1 eq. 2.
  3. Edit operations at state (T_{1:i}, y_{1:j}), where T_{1:i} is the label prefix and y_{1:j} the output prefix §3.2:
    • Consumption: T_i is aligned to y_j. Probability R^C_j · y_j(T_i) §3.2 eq. 3 eq. 4.
    • Deletion: y_j is superfluous. Probability R^D_j, except that after EOS it is 1 §3.2 eq. 5 eq. 6.
    • Insertion: T_i is missing before y_j. Probability R^I_j · I_j(T_i) for j < |y|, and I_j(T_i) for j = |y| §3.2 eq. 7 eq. 8.
  4. Path probability. The probability of an edit path is the product of its operation probabilities §3.2 eq. 9.
  5. Edit probability. EP of a label T is the sum over all edit paths that turn the empty string and the empty output into (T, y). The authors state that EP is the sum of these path probabilities §3.2 eq. 10 eq. 11.
  6. Recursion. Concatenating an operation with a path gives the rule in eq. 12 and eq. 13. Summing over the last operation gives the three-term recursion in eq. 14. The authors state the cost as O(|T|·|y|) §3.2.
Pseudocode
# Edit probability by dynamic programming  [eq. 14] [§3.2]
# Paper indices are 1-based; lists are 0-based: T_i is target[i - 1].
# target: label symbols, ending with EOS '#'  [§3.2]
# y_R: per step (R^C, R^I, R^D)  [eq. 2]
# y_I: per step character distribution I_j  [eq. 2]
# y_pd: per step output distribution y_j  [eq. 1]
def edit_probability(target, y_R, y_I, y_pd):
    # Table: one row per label prefix, one column per output prefix
    num_chars = len(target)
    num_steps = len(y_pd)
    ep = zeros(num_chars + 1, num_steps + 1)
    # Base case: empty label from empty output  [eq. 14]
    ep[0][0] = 1.0
    for i in range(num_chars + 1):
        for j in range(num_steps + 1):
            if i == 0 and j == 0:
                continue
            total = 0.0
            # Deletion of output j  [eq. 6] [eq. 14]
            if j > 0:
                total += delete_prob(target, y_R, i, j) * ep[i][j - 1]
            # Insertion of target[i] before output j  [eq. 8] [eq. 14]
            if i > 0:
                total += insert_prob(target, y_R, y_I, i, j) * ep[i - 1][j]
            # Consumption of output j as target[i]  [eq. 4] [eq. 14]
            if i > 0 and j > 0:
                total += (consume_prob(target, y_R, y_pd, i, j)
                          * ep[i - 1][j - 1])
            ep[i][j] = total
    return ep[num_chars][num_steps]

The three helper functions below are the operation probabilities used by the recursion above. They are shown separately to keep lines short.

Pseudocode
# Deletion probability at state (i, j)  [eq. 6]
def delete_prob(target, y_R, i, j):
    # After EOS, remaining outputs are ignored: probability 1  [eq. 6]
    if target[i - 1] == EOS:
        return 1.0
    return y_R[j - 1][2]  # R^D_j  [eq. 2]

# Insertion probability at state (i, j)  [eq. 8]
def insert_prob(target, y_R, y_I, i, j):
    char = target[i - 1]
    # j = 0 has no decoder output in §3.1; convention needed (see Pitfalls)
    if j == 0:
        raise ValueError("R_0 and I_0 are not defined by the paper")
    # Last output: only the character term  [eq. 8]
    if j == len(y_I):
        return y_I[j - 1][char]
    return y_R[j - 1][1] * y_I[j - 1][char]  # R^I_j I_j(T_i)

# Consumption probability at state (i, j)  [eq. 4]
def consume_prob(target, y_R, y_pd, i, j):
    char = target[i - 1]
    return y_R[j - 1][0] * y_pd[j - 1][char]  # R^C_j y_j(T_i)
  1. Training. The objective is the sum over training pairs of the negative log of EP, minimised by back-propagation §3.3 eq. 15. Whether the sum is over a batch or averaged is not stated.
Pseudocode
# EP training loss over a batch  [eq. 15] [§3.3]
def ep_loss(batch):
    loss = 0.0
    for image, target in batch:
        # Decoder outputs for this image  [eq. 1] [eq. 2]
        y_R, y_I, y_pd = decoder(image)
        # Negative log of EP of the label  [eq. 15]
        loss -= log(edit_probability(target, y_R, y_I, y_pd))
    # Sum versus mean over the batch: not stated  [§3.3]
    return loss
  1. Prediction without a lexicon. Exact search over all strings is too costly eq. 16. The authors instead build a greedy string 𝒯, which is mostly a prefix of the best output, and score each prefix ending in EOS with EP §3.4 eq. 17 eq. 18 eq. 19. The greedy step picks the most probable deletion or consumption at each output step, and never an insertion of a non-EOS character §3.4.
Pseudocode
# Lexicon-free decoding  [§3.4] [eq. 17] [eq. 18] [eq. 19]
# j in the loop is 0-based here; the paper's j is j + 1.
def predict_without_lexicon(y_R, y_I, y_pd):
    # Greedy pass: delete each output, or consume its best non-EOS char
    prefix = []
    for j in range(len(y_pd)):
        best_char = argmax_excluding(y_pd[j], EOS)
        consume_score = y_R[j][0] * y_pd[j][best_char]
        # Reading of §3.4: compare deletion with consumption  [§3.4]
        if y_R[j][2] > consume_score:
            continue
        prefix.append(best_char)
    # Candidates: every prefix of the greedy string, ended by EOS  [eq. 18]
    candidates = [prefix[:k] + [EOS] for k in range(len(prefix) + 1)]
    # Return the candidate with the highest EP  [eq. 19]
    return max(candidates,
               key=lambda c: edit_probability(c, y_R, y_I, y_pd))
  1. Prediction with a lexicon. Candidates are the greedy set B and the lexicon D. Each candidate's EP is weighted by λ if it is in D and by 1 − λ otherwise, with 0.5 ≤ λ ≤ 1 §3.4 eq. 20. The authors add an EP-Trie: a prefix tree whose nodes store the EP vector for that prefix; a child's vector is computed from its parent's in O(|y|) time §3.4.
Pseudocode
# Lexicon-weighted score, lam in [0.5, 1]  [eq. 20] [§3.4]
def lexicon_score(word, lexicon, lam, y_R, y_I, y_pd):
    ep_value = edit_probability(word, y_R, y_I, y_pd)
    if word in lexicon:
        return lam * ep_value
    return (1 - lam) * ep_value

Hyperparameters

NameValueWhereNotes
OptimiserADADELTA§4.2Learning rate, decay, epochs and schedule: not stated
Batch size75§4.4Stated only for the timing measurement; not stated as a training setting
λ (lexicon trust)0.5 ≤ λ ≤ 1§3.4 eq. 20Experiments vary λ from 0.5 to 1 §4.5; the useful range for the Hunspell lexicon is 0.9–0.98 §4.5; the best λ per dataset is only plotted fig. 5
Lexicon for ground-truth-unrelated testHunspell 50k, more than 50k words§4.5Used for the λ sweep and the EP-Trie timing
Training data8M synthetic images (Jaderberg et al.) and 4M cropped from 800k images (Gupta et al.)§4.2The 4M set excludes words with non-alphanumeric characters
EncoderShi et al.'s 7-conv CNN, or Cheng et al.'s ResNet§4.2Architectures are only named and cited, not described
DecoderLSTM attention decoder; hidden size, attention size not stated§3.1Dimensions not stated
Alphabet and EOSEOS written #; alphabet not listed§3.2 fig. 2Alphabet and maximum output length: not stated
Input resolutionnot stated§4.2
FrameworkCaffe, CUDA backend§4.2
HardwareIntel Xeon E5-2650 2.30 GHz, NVIDIA Tesla P40, 128 GB RAM§4.2Single workstation
Timing per iterationShi: 170.5 ms baseline, +6.8 ms EP; Cheng: 536.0 ms baseline, +7.0 ms EP§4.4Batch size 75
EP-Trie timing0.11 s per image (EP-Trie) vs 2.566 s (enumeration)§4.550k lexicon; the paper states the two predict the same result
IC03 filterkeep images without non-alphanumeric characters and with at least three characters; 867 images§4.1Follows Wang et al.
IC15 filter2077 images, 1811 kept§4.1Non-alphanumeric images discarded

Results

Author-reported. Setup: models trained on the synthetic data in §4.2 with the Shi and Cheng structures; test sets IIIT5K, SVT, IC03, IC13 and IC15 §4.1. Baseline numbers are copied from the cited papers tab. 1 caption. Columns give word accuracy; "–" means the paper does not report the value tab. 1.

MethodIIIT5K 50IIIT5K 1kIIIT5K NoneSVT 50SVT NoneIC03 50IC03 FullIC03 NoneIC13 NoneIC15 None
ABBYY24.3––35.0–56.055.0–––
Wang et al.–––57.0–76.062.0–––
Mishra et al.64.157.5–73.2–81.867.8–––
Wang et al. (2012)–––70.0–90.084.0–––
Goel et al.–––77.3–89.7––––
Bissacco et al.–––90.478.0–––87.6–
Alsharif and Pineau–––74.3–93.188.6–––
Almazán et al.91.282.1–89.2––––––
Yao et al.80.269.3–75.9–88.580.3–––
Rodríguez-Serrano et al.76.157.4–70.0––––––
Jaderberg et al. (key jaderberg2014deep, row 1)–––86.1–96.291.5–––
Su and Lu–––83.0–92.082.0–––
Gordo93.386.6–91.8––––––
Jaderberg et al. (jaderberg2016reading)97.192.7–95.480.798.798.693.190.8–
Jaderberg et al. (jaderberg2014deep, row 2)95.589.6–93.271.797.897.089.681.8–
Shi et al. (shi17end)97.694.478.296.480.898.797.689.486.7–
Shi et al. (shi2016robust)96.293.881.995.581.998.396.290.188.6–
Lee et al.96.894.478.496.380.797.997.088.790.0–
Cheng et al. (FAN)99.397.587.497.185.999.297.394.293.370.6
Shi et al. (baseline)96.592.879.796.181.597.896.488.787.5–
Cheng et al. (baseline)98.996.883.795.782.298.596.791.589.463.3
Shi's + EP (ours)99.197.385.096.386.298.497.093.793.068.1
Cheng's + EP (ours)99.597.988.396.687.598.797.994.694.473.9

tab. 1. Bold marks the best value per column in the source. The EP models use the same structures as their baselines, with the loss and prediction replaced §4.2 §4.3.

Points the authors make in the text:

  • With both structures, the EP variant beats its frame-wise baseline on every benchmark in tab. 1; the authors call the gain significant, but no statistical test or variance is reported §4.3.
  • Unconstrained cases: Cheng's + EP is reported to outperform all existing methods in tab. 1 §4.3.
  • Constrained cases: it beats all existing methods on IIIT5K, and is comparable to FAN on SVT and IC03 §4.3 tab. 1. FAN is trained with word-level and character-level box annotations; the EP models use word-level labels only §4.3.
  • The authors note that Jaderberg et al. report the best IC03 Full result, but that method cannot read words outside its training set §4.3 tab. 1.
  • EP training versus frame-wise training: in the examples, EP localises the error to the missing or superfluous character, while FP error spreads to correctly read outputs §4.4 fig. 4.
  • Lexicon sweep (Hunspell 50k): accuracy rises as λ goes from 0.5 to about 0.98 and falls sharply near 1; at λ = 0.5 it equals lexicon-free accuracy §4.5 fig. 5. The plotted values are not given in the text.
  • EP-Trie predicts the same words as enumeration, at 0.11 s versus 2.566 s per image with the 50k lexicon §4.5.

Paper vs code

No official code.

Searched: the paper text and the arXiv abstract page (no code link; the page has no comments field; the only URL in the bibliography is the Hunspell project); GitHub repository search for edit probability scene text (no results) and edit probability (99 results, none by the authors). The one repository whose name matches the title, HannaRiver/EditProbability4TextRecognition, is a third-party repository and was not used. Only part of the 99-result list was read directly.

Pitfalls

  • Index convention for insertion. The text says the missing character sits before y_{j+1} and is T_{i+1} §3.2, while Eq. 8 uses R_j, I_j and T_i eq. 8. Section 3.1 defines the decoder outputs from step j on, and the recursion (Eq. 14) and Fig. 2 count from j = 0 §3.1 eq. 14 fig. 2. At j = 0 the insertion term needs R_0 and I_0, which no equation defines. The implementer must choose a convention for this boundary.
  • Normalisation not discussed. The operation probabilities at a state are not shown to sum to one. The paper does not show that EP sums to one over all label strings, so the training loss (Eq. 15) is the negative log of an unnormalised score eq. 15. This is an observation from the equations, not a claim the authors make.
  • Numerical range not discussed. EP is a sum of products over O(|T|·|y|) states. The paper does not say whether the recursion is run in log space or how underflow is avoided, and it does not give the length of y or T.
  • Greedy decoding is a heuristic. The paper says the best string is "mostly" a prefix of the greedy string 𝒯 §3.4. The greedy step is a per-step rule; the paper does not show it finds the maximising string. The reading of "most probable deletion or consumption" as a comparison of R^D_j with the best consumption is this card's reading of §3.4.
  • EOS handling. The label must contain exactly one EOS, at the end §3.2. After EOS, outputs are removed with probability 1 in both training and prediction eq. 6.
  • Baselines are copied. The frame-wise baseline numbers are taken from the cited papers tab. 1 caption. The EP models are trained by the authors, and the training schedule is not stated §4.2. The table is therefore not a controlled comparison beyond the paper's own runs.
  • Duplicate citation key. Two rows of Table 1 use the same key (jaderberg2014deep) tab. 1. From the source alone, it is not possible to tell which Jaderberg paper each row reports.
  • Statistics. The text says "significantly" §4.3; no test, seed count or variance is given.
  • Cost. The overhead is measured per iteration at batch size 75 on one Tesla P40 §4.4. The per-sample cost is O(|T|·|y|) §3.2. The paper gives no memory figures.
  • Lexicon λ. The best λ per dataset is only in Fig. 5 and is not given numerically §4.5 fig. 5.
  • Encoders and decoder size. The CNN and ResNet encoders are not described beyond their names §4.2. The LSTM size and the attention dimension are not stated §3.1.

Lineage

  • Builds on: the attention decoder of Bahdanau et al., cited for the decoder recurrence §3.1 eq. 1. Shi et al. (CVPR 2016, "Robust Scene Text Recognition with Automatic Rectification") gives the 7-conv structure and the baseline, cited as shi2016robust §4.2 tab. 1. No card exists for either paper.
  • Builds on: the ResNet-based structure from Cheng et al., "Focusing attention" (ICCV 2017): see FAN card §4.2.
  • Compared against: the methods listed in tab. 1.
  • Superseded by: not known from the content of this wiki.

Source and license

Adapted from “Edit Probability for Scene Text Recognition” by Fan Bai, Zhanzhan Cheng, Yi Niu, Shiliang Pu, Shuigeng Zhou (arXiv:1805.03384), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.