Optical character recognition (text recognition)

Deep dive

How it works

Parts:

• Preprocessor — upright, evenly lit page (document image preprocessing).
• Text detector — pixels to line or word polygons: segmentation maps (DB, CRAFT) or box regression (EAST), then NMS or contour grouping; see object detection.
• Cropper — rectifies each polygon to a fixed-height strip, rotating flipped or vertical lines.
• Recogniser — CNN (+ BiLSTM) giving T frames x V symbols for CTC, or an encoder with an autoregressive decoder.
• Decoder — greedy or beam search, optionally with an n-gram LM.
• Corrector and scorer — lexicon or format rules, per-line confidence.
• Orderer — lines into reading order and blocks (layout analysis, table structure).

1. Detect. Run the detector on the downscaled page; threshold the text map, extract polygons, drop tiny or low-score ones.
2. Crop. Warp each polygon to the model's input height; batch strips of similar width.
3. Recognise. A CTC head gives one softmax row per image column; an attention decoder (TrOCR-style) emits tokens one by one and can skip or repeat text.
4. Decode. Collapse repeats and blanks; character confidence is the peak probability of its frame run (code below).
5. Correct. Replace a word by the unique nearest dictionary word within 1-2 edits; leave numbers, codes and names alone and validate formats (dates, check digits) instead.
6. Score. Line confidence = min or mean of character confidences; below a threshold, send the line to a person (human-in-the-loop).
7. Order. Sort lines by layout block, column and baseline; normalise Unicode.
8. Evaluate. CER = (substitutions + insertions + deletions) / reference characters; WER the same over words (edit distance).

page -> [preprocess] -> [detector] -> polygons -> [crop] -> strips
                                                             |
text, boxes, conf <- [order] <- [correct] <- [decode] <- [recogniser: T x V]
                                                             |
                                          low conf -> review queue

Scene text (curved, arbitrary fonts) wants a segmentation-style detector; document text is straight lines; handwriting needs line models plus a language model. Right-to-left scripts are read in visual order and reordered with the Unicode bidirectional algorithm; vertical text is rotated into a strip or read column-wise. A Latin-only model on another script gives confident garbage, so route by script (language identification).

Code

Post-model core, std only: greedy CTC decode with per-character confidence, unique-nearest lexicon correction under a distance cap, CER, and a throughput run on synthetic matrices.

/// Greedy CTC decode of softmax rows `p[t]` (symbol 0 = blank). Returns text and, per char,
/// the peak probability inside its run of frames.
fn ctc_greedy(p: &[Vec<f32>], alpha: &[char]) -> (String, Vec<f32>) {
    let (mut s, mut conf, mut prev) = (String::new(), Vec::<f32>::new(), 0usize);
    for row in p {
        let (k, &pk) = row.iter().enumerate()
            .max_by(|a, b| a.1.partial_cmp(b.1).unwrap()).unwrap();
        if k != 0 && k == prev {
            let c = conf.last_mut().unwrap();
            *c = c.max(pk); // same run: keep the highest frame
        } else if k != 0 {
            s.push(alpha[k]);
            conf.push(pk);
        }
        prev = k; // a blank resets prev, so "l _ l" stays two chars
    }
    (s, conf)
}
/// (min, mean) of char confidences; an empty line scores 0 and goes to review.
fn line_conf(c: &[f32]) -> (f32, f32) {
    if c.is_empty() { return (0.0, 0.0); }
    (c.iter().cloned().fold(1.0, f32::min), c.iter().sum::<f32>() / c.len() as f32)
}
/// Levenshtein distance, two rows; None once it must exceed `max`.
fn lev(a: &[char], b: &[char], max: usize) -> Option<usize> {
    if a.len().abs_diff(b.len()) > max { return None; }
    let mut prev: Vec<usize> = (0..=b.len()).collect();
    for (i, &ca) in a.iter().enumerate() {
        let mut cur = vec![i + 1];
        for (j, &cb) in b.iter().enumerate() {
            cur.push((prev[j] + (ca != cb) as usize).min(prev[j + 1] + 1).min(cur[j] + 1));
        }
        if *cur.iter().min().unwrap() > max { return None; }
        prev = cur;
    }
    Some(prev[b.len()]).filter(|&d| d <= max)
}
/// Unique nearest lexicon word within `max` edits; digits, no match and ties stay unchanged.
fn correct<'a>(w: &'a str, lex: &'a [&'a str], max: usize) -> &'a str {
    if w.chars().any(|c| c.is_ascii_digit()) { return w; }
    let wc: Vec<char> = w.chars().collect();
    let (mut best, mut bd, mut tie) = (w, usize::MAX, false);
    for &cand in lex {
        let cc: Vec<char> = cand.chars().collect();
        if let Some(d) = lev(&wc, &cc, max.min(bd)) {
            if d < bd { (best, bd, tie) = (cand, d, false); } else if d == bd { tie = true; }
        }
    }
    if tie || bd == usize::MAX { w } else { best }
}
fn cer(reference: &str, hyp: &str) -> f64 {
    let (r, h): (Vec<char>, Vec<char>) = (reference.chars().collect(), hyp.chars().collect());
    lev(&r, &h, r.len().max(h.len())).unwrap() as f64 / r.len().max(1) as f64
}
fn read_line(p: &[Vec<f32>], alpha: &[char], lex: &[&str]) -> (String, f32) {
    let (raw, conf) = ctc_greedy(p, alpha);
    let fixed: Vec<&str> = raw.split(' ').map(|w| correct(w, lex, 1)).collect();
    (fixed.join(" "), line_conf(&conf).0)
}
fn matrix(path: &[usize], v: usize, peak: f32) -> Vec<Vec<f32>> {
    path.iter().map(|&k| (0..v).map(|i| if i == k { peak } else { (1.0 - peak) / (v - 1) as f32 }).collect()).collect()
}
fn main() {
    let alpha: Vec<char> = "_ abcdefghijklmnopqrstuvwxyz0123456789".chars().collect(); // 0 = blank
    let ix = |c: char| alpha.iter().position(|&a| a == c).unwrap();
    let path = |s: &str| -> Vec<usize> { // each char 2 frames, a blank after every char
        s.chars().flat_map(|c| [ix(c), ix(c), 0]).collect()
    };
    let v = alpha.len();
    let (t, c) = ctc_greedy(&matrix(&path("hello"), v, 0.9), &alpha);
    assert_eq!(t, "hello"); // repeats merged inside a run, "ll" kept via blank
    assert!(c.len() == 5 && c.iter().all(|&x| (x - 0.9).abs() < 1e-6));
    let mut m = matrix(&path("ab"), v, 0.9);
    m[1] = matrix(&[ix('a')], v, 0.6).remove(0); // weakest frame of 'a' is not its peak
    let (min, mean) = line_conf(&ctc_greedy(&m, &alpha).1);
    assert!((min - 0.9).abs() < 1e-6 && (mean - 0.9).abs() < 1e-6); // run keeps the peak frame
    let lex = ["cat", "dog", "table", "total", "tonal"];
    assert_eq!(correct("cot", &lex, 1), "cat"); // 1-edit misread fixed
    assert_eq!(correct("4821", &lex, 1), "4821"); // number untouched
    assert_eq!(correct("xyzzy", &lex, 1), "xyzzy"); // beyond max distance
    assert_eq!(correct("toal", &lex, 1), "toal"); // ties: total/tonal -> ask a human
    assert!((cer("kitten", "sitting") - 0.5).abs() < 1e-12); // 3 edits / 6 chars
    assert_eq!(read_line(&matrix(&path("a cot 42"), v, 0.8), &alpha, &lex).0, "a cat 42");

    // throughput: 120 frames x 38 symbols, ~40 chars, 1,000-word lexicon
    let mut seed = 7u64;
    let mut rnd = move || { seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407); (seed >> 33) as usize };
    let words: Vec<String> = (0..1000).map(|_| (0..3 + rnd() % 6).map(|_| alpha[2 + rnd() % 26]).collect()).collect();
    let lex: Vec<&str> = words.iter().map(|s| s.as_str()).collect();
    let lines: Vec<(String, Vec<Vec<f32>>)> = (0..200).map(|_| {
        let s: String = (0..8).map(|_| words[rnd() % 1000].clone()).collect::<Vec<_>>().join(" ");
        let mut p = path(&s); p.truncate(120); p.resize(120, 0);
        (s, matrix(&p, v, 0.8))
    }).collect();
    let time = |f: &dyn Fn(&str, &[Vec<f32>]) -> String| { // lines/s over 20 passes
        let t0 = std::time::Instant::now();
        for _ in 0..20 { for (r, p) in &lines { std::hint::black_box(cer(r, &f(r, p))); } }
        20.0 * lines.len() as f64 / t0.elapsed().as_secs_f64()
    };
    let d = time(&|_, p| ctc_greedy(p, &alpha).0);
    let k = time(&|_, p| read_line(p, &alpha, &lex).0);
    println!("decode+CER {d:.0} lines/s; decode+lexicon+CER {k:.0} lines/s");
}

Complexity and constants

• Detection O(pixels); recognition O(lines x width) through the CNN/LSTM; decode O(T·V); naive lexicon correction O(W·D·l²) for W words, a D-word dictionary, word length l.
• Memory: a T x V float matrix per line, order of 120 x 100 x 4 B = 48 kB; model weights dominate.
• Measured (Apple M4 Pro, one thread, --release, 200 synthetic peaked lines of 120 frames x 38 symbols, ~40 chars, 20 passes, shared Mac): decode + CER 58,000-69,000 lines/s (14-17 µs per line); decode + 1,000-word lexicon + CER 1,450-1,520 lines/s (0.66-0.69 ms per line), 9 runs.

Efficiency

• Cost: the neural pass dominates, not the 14-17 µs decode above: a CNN/LSTM pass per line costs order of milliseconds on a CPU core (not measured here). Bound: compute for detection (pixels), compute plus padding waste for recognition. Docling's benchmark in PDF text extraction reports EasyOCR over 30 s/page on CPU.
• Levers:
  • Batch crops sorted by width — less padding waste (order of, not measured) — many lines per page.
  • Detect on a downscaled page (long side about 1,000 px, order of), recognise from full-resolution crops — fewer pixels to detect — 300 dpi scans.
  • Skip OCR when a text layer exists — saves the whole pipeline — mixed PDF batches.
  • Index the lexicon (BK-tree, deletion index, trie with an edit budget) — replaces the O(D) scan, the 45x decode cost measured above — dictionaries above a few thousand words.
  • Smaller or quantised recognisers — fewer FLOPs for some accuracy — phones and edge devices.
• Naive → standard → state of the art:
  • Binarise, segment characters, classify each · fails on touching or broken glyphs (legacy Tesseract engine)
  • Detector + CRNN with CTC + lexicon · ms per line on CPU, strong on printed text
  • Detector + transformer recogniser, or a vision-language model reading the page · better on hard scripts and layouts, much more compute per page

Implementation notes

• Match the training input height and normalisation; keep blank index and character set identical in training and decoding.
• Line-level min confidence is stricter than mean: one weak digit routes an amount to review. Softmax scores are usually overconfident, so fit the threshold on held-out lines against true CER (calibration).
• Synthetic lines (many fonts, backgrounds, blur; TextRecognitionDataGenerator is used by EasyOCR, TrOCR pre-trains on synthetic data) give the base; fine-tune on a few thousand real lines of your domain with augmentation.

Pitfalls

• Lexicon over-correction turns rare names into common words: skip tokens with digits, cap distance at 1-2, leave ties alone.
• CER hides reading-order and layout errors; score fields and order separately.
• Detection recall bounds everything: a missed line never reaches the recogniser.
• Rotated or 180-degree-flipped pages read as garbage: orient first.

Variants and alternatives

In production

• Tesseract (printed text, library and CLI), EasyOCR (CRAFT detector + CRNN recogniser), docTR (default db_resnet50 + crnn_vgg16_bn), PaddleOCR (PP-OCR series, 100+ languages claimed in its README).

Implementations

Sources

• Shi, Bai, Yao, An End-to-End Trainable Neural Network for Image-based Sequence Recognition and Its Application to Scene Text Recognition (CRNN), 2015. paper
• Li et al., TrOCR: Transformer-based Optical Character Recognition with Pre-trained Models, 2021. paper
• Smith, An Overview of the Tesseract OCR Engine, ICDAR 2007, pp. 629-633. paper
• Liao et al., Real-time Scene Text Detection with Differentiable Binarization (DB), 2019. paper
• Baek et al., Character Region Awareness for Text Detection (CRAFT), CVPR 2019. paper · code
• Zhou et al., EAST: An Efficient and Accurate Scene Text Detector, 2017. paper
• Kim et al., OCR-free Document Understanding Transformer (Donut), 2021. paper · code