Full search page →

CTC prefix beam search, step by step

Optional · supplementary note 1 of 5 for DLCV 06 · Text in Images: OCR and Document Understanding. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.

Navigate: this page and this track: Navigate: this page and this track

On this page

Supplementary notes · 5

  1. CTC prefix beam search, step by step
  2. Shrinking and expanding text polygons
  3. Where the language model sits in a recognizer
  4. Reading vertical and mixed-direction text
  5. Evaluation protocols in detail

Paper guides · 4

  1. Guide to the Modern view surveys
  2. Baek et al., “What Is Wrong With Scene Text Recognition Model Comparisons?” (ICCV 2019)
  3. DBNet: a reading guide
  4. Donut: a reading guide

Deep Learning for Computer Vision

  1. 02 · Deep Image Classification
View the whole course tree →

This note explains how a CTC decoder finds a likely text rather than a likely path, by searching over prefixes instead of alignments.

What is searched. A prefix ℓ\ell is a partial transcription, such as “ca”. After reading frames 1,…,t1, \dots, t, many alignments collapse to the same prefix. Prefix beam search keeps, for each prefix, two numbers:

  • pb(ℓ,t)p_b(\ell, t), the total probability of alignments of frames 1..t1..t that collapse to ℓ\ell and end in a blank;
  • pnb(ℓ,t)p_{nb}(\ell, t), the total probability of those that end in the last label of ℓ\ell.

Their sum is the probability that the first tt frames read as ℓ\ell. The split is needed because the next symbol behaves differently in the two cases.

Update rules. For each kept prefix ℓ\ell and each symbol ss at frame t+1t+1, with q=qt+1(s)q = q_{t+1}(s) the network’s probability of ss:

  1. Blank (s=∅s = \varnothing): the prefix does not change, and the alignment now ends in a blank: add (pb+pnb) q(p_b + p_{nb})\,q to pb(ℓ,t+1)p_b(\ell, t+1).
  2. Repeat of the last label (ss equals the last label of ℓ\ell): if the previous symbol was that label, the repeat merges and the prefix stays ℓ\ell: add pnb qp_{nb}\,q to pnb(ℓ,t+1)p_{nb}(\ell, t+1). If the previous symbol was a blank, the repeat starts a new copy: add pb qp_b\,q to pnb(ℓs,t+1)p_{nb}(\ell s, t+1). This is how “aa” can be written as “a-a”.
  3. Any other label: extend the prefix: add (pb+pnb) q(p_b + p_{nb})\,q to pnb(ℓs,t+1)p_{nb}(\ell s, t+1).

After each frame, keep only the BB prefixes with the largest pb+pnbp_b + p_{nb} (the beam width). At the end, return the best prefix. With an unlimited beam the result is exact for the CTC model; with B=1B = 1 it behaves almost like greedy decoding.

Code · Python · 33 lines
import numpy as np

alphabet = ["-", "c", "a", "t"]
probs = np.array([[0.10, 0.80, 0.05, 0.05],
                  [0.20, 0.05, 0.70, 0.05],
                  [0.60, 0.05, 0.30, 0.05],
                  [0.55, 0.02, 0.03, 0.40],
                  [0.55, 0.02, 0.03, 0.40]])

def prefix_beam_search(probs, beam=3):
    # Each prefix keeps two numbers: p_b (all its alignments end in blank)
    # and p_nb (they end in the prefix's last label).
    beams = {(): (1.0, 0.0)}
    for frame in probs:
        nxt = {}
        def add(prefix, pb, pnb):
            ob, onb = nxt.get(prefix, (0.0, 0.0))
            nxt[prefix] = (ob + pb, onb + pnb)
        for prefix, (pb, pnb) in beams.items():
            add(prefix, (pb + pnb) * frame[0], 0.0)              # emit blank
            for s in range(1, len(frame)):
                p = frame[s]
                if prefix and prefix[-1] == s:
                    add(prefix, 0.0, pnb * p)                    # repeat merges
                    add(prefix + (s,), 0.0, pb * p)              # blank separated
                else:
                    add(prefix + (s,), 0.0, (pb + pnb) * p)      # new label
        beams = dict(sorted(nxt.items(), key=lambda kv: -sum(kv[1]))[:beam])
    return [("".join(alphabet[s] for s in k), sum(v)) for k, v in beams.items()]

for B in [1, 3, 20]:
    top = prefix_beam_search(probs, beam=B)[:2]
    print(f"beam={B:2d}: " + ", ".join(f"{t!r} p={p:.3f}" for t, p in top))

Output

beam= 1: 'ca' p=0.155
beam= 3: 'cat' p=0.344, 'ca' p=0.179
beam=20: 'cat' p=0.363, 'ca' p=0.179

On the chapter’s toy, a beam of 1 returns “ca”, like greedy decoding. A beam of 3 already finds “cat”, with a slightly low probability (0.344) because some of its alignments passed through prefixes that were pruned. A beam of 20 keeps every prefix here and reproduces the exact value 0.363 from the brute-force sum.

Pitfalls. Work in log space for long sequences, since the products underflow. Do not deduplicate by path, only by prefix. When a lexicon or language model is added, its score is usually applied when a prefix is extended by a label, weighted by a tuned factor, and often combined with a bonus per emitted character so that the search does not favor short outputs; the weights are tuned on held-out data, and the same over-correction risk described in the main text applies.

References

  1. S. Long, X. He and C. Yao, “Scene text detection and recognition: The deep learning era,” International Journal of Computer Vision, vol. 129, pp. 161–184, 2021. doi
  2. X. Chen, L. Jin, Y. Zhu, C. Luo and T. Wang, “Text recognition in the wild: A survey,” ACM Computing Surveys, vol. 54, no. 2, 2021. doi
  3. L. Cui, Y. Xu, T. Lv and F. Wei, “Document AI: Benchmarks, models and applications,” arXiv:2111.08609, 2021. arXiv
  4. Q. Zhang, B. Wang, V. S.-J. Huang, J. Zhang, Z. Wang, H. Liang, C. He and W. Zhang, “Document parsing unveiled: Techniques, challenges, and prospects for structured information extraction,” arXiv:2410.21169, 2024. arXiv
  5. D. Karatzas, F. Shafait, S. Uchida, M. Iwamura, L. Gomez i Bigorda, S. Robles Mestre, J. Mas et al., “ICDAR 2013 Robust Reading Competition,” in Proc. International Conference on Document Analysis and Recognition (ICDAR), pp. 1484–1493, 2013. doi
  6. D. Karatzas, L. Gomez-Bigorda, A. Nicolaou, S. Ghosh, A. Bagdanov, M. Iwamura, J. Matas et al., “ICDAR 2015 competition on Robust Reading,” in Proc. International Conference on Document Analysis and Recognition (ICDAR), pp. 1156–1160, 2015. doi
  7. J. Baek, G. Kim, J. Lee, S. Park, D. Han, S. Yun, S. J. Oh and H. Lee, “What is wrong with scene text recognition model comparisons? Dataset and model analysis,” in Proc. IEEE/CVF ICCV, pp. 4714–4722, 2019. doi
  8. N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, no. 1, pp. 62–66, 1979. doi
  9. J. Sauvola and M. Pietikäinen, “Adaptive document image binarization,” Pattern Recognition, vol. 33, no. 2, pp. 225–236, 2000. doi
  10. C. K. Ch’ng and C. S. Chan, “Total-Text: A comprehensive dataset for scene text detection and recognition,” in Proc. ICDAR, pp. 935–942, 2017. doi
  11. Y. Liu, L. Jin, S. Zhang, C. Luo and S. Zhang, “Curved scene text detection via transverse and longitudinal sequence connection,” Pattern Recognition, vol. 90, pp. 337–345, 2019. doi
  12. X. Zhou, C. Yao, H. Wen, Y. Wang, S. Zhou, W. He and J. Liang, “EAST: An efficient and accurate scene text detector,” in Proc. IEEE CVPR, pp. 2642–2651, 2017. doi
  13. W. Wang, E. Xie, X. Li, W. Hou, T. Lu, G. Yu and S. Shao, “Shape robust text detection with progressive scale expansion network,” in Proc. IEEE/CVF CVPR, pp. 9328–9337, 2019. doi
  14. M. Liao, Z. Wan, C. Yao, K. Chen and X. Bai, “Real-time scene text detection with differentiable binarization,” in Proc. AAAI Conference on Artificial Intelligence, vol. 34, pp. 11474–11481, 2020. doi
  15. Y. Baek, B. Lee, D. Han, S. Yun and H. Lee, “Character region awareness for text detection,” in Proc. IEEE/CVF CVPR, pp. 9357–9366, 2019. doi
  16. B. Shi, X. Bai and C. Yao, “An end-to-end trainable neural network for image-based sequence recognition and its application to scene text recognition,” IEEE TPAMI, vol. 39, no. 11, pp. 2298–2304, 2017. doi
  17. A. Graves, S. Fernández, F. Gomez and J. Schmidhuber, “Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks,” in Proc. ICML, pp. 369–376, 2006. doi
  18. B. Shi, M. Yang, X. Wang, P. Lyu, C. Yao and X. Bai, “ASTER: An attentional scene text recognizer with flexible rectification,” IEEE TPAMI, vol. 41, no. 9, pp. 2035–2048, 2019. doi
  19. M. Li, T. Lv, J. Chen, L. Cui, Y. Lu, D. Florencio, C. Zhang, Z. Li and F. Wei, “TrOCR: Transformer-based optical character recognition with pre-trained models,” in Proc. AAAI Conference on Artificial Intelligence, vol. 37, pp. 13094–13102, 2023. doi
  20. D. Bautista and R. Atienza, “Scene text recognition with permuted autoregressive sequence models,” in Proc. ECCV, pp. 178–196, 2022. doi
  21. S. Fang, H. Xie, Y. Wang, Z. Mao and Y. Zhang, “Read like humans: Autonomous, bidirectional and iterative language modeling for scene text recognition,” in Proc. IEEE/CVF CVPR, pp. 7094–7103, 2021. doi
  22. Y. Liu, Z. Li, M. Huang, B. Yang, W. Yu, C. Li, X.-C. Yin, C.-L. Liu, L. Jin and X. Bai, “OCRBench: On the hidden mystery of OCR in large multimodal models,” Science China Information Sciences, vol. 67, 2024. doi
  23. M. Jaderberg, K. Simonyan, A. Vedaldi and A. Zisserman, “Synthetic data and artificial neural networks for natural scene text recognition,” arXiv:1406.2227, 2014. arXiv
  24. A. Gupta, A. Vedaldi and A. Zisserman, “Synthetic data for text localisation in natural images,” in Proc. IEEE CVPR, pp. 2315–2324, 2016. doi
  25. X. Liu, D. Liang, S. Yan, D. Chen, Y. Qiao and J. Yan, “FOTS: Fast oriented text spotting with a unified network,” in Proc. IEEE/CVF CVPR, pp. 5676–5685, 2018. doi
  26. P. Lyu, M. Liao, C. Yao, W. Wu and X. Bai, “Mask TextSpotter: An end-to-end trainable neural network for spotting text with arbitrary shapes,” in Proc. ECCV, pp. 71–88, 2018. doi
  27. Y. Liu, H. Chen, C. Shen, T. He, L. Jin and L. Wang, “ABCNet: Real-time scene text spotting with adaptive Bezier-curve network,” in Proc. IEEE/CVF CVPR, pp. 9806–9815, 2020. doi
  28. X. Zhong, J. Tang and A. Jimeno Yepes, “PubLayNet: Largest dataset ever for document layout analysis,” in Proc. ICDAR, pp. 1015–1022, 2019. doi
  29. B. Pfitzmann, C. Auer, M. Dolfi, A. S. Nassar and P. Staar, “DocLayNet: A large human-annotated dataset for document-layout segmentation,” in Proc. ACM SIGKDD, pp. 3743–3751, 2022. doi
  30. Y. Xu, M. Li, L. Cui, S. Huang, F. Wei and M. Zhou, “LayoutLM: Pre-training of text and layout for document image understanding,” in Proc. ACM SIGKDD, pp. 1192–1200, 2020. doi
  31. R. Smith, “An overview of the Tesseract OCR engine,” in Proc. ICDAR, vol. 2, pp. 629–633, 2007. doi
  32. Y. Huang, T. Lv, L. Cui, Y. Lu and F. Wei, “LayoutLMv3: Pre-training for document AI with unified text and image masking,” in Proc. ACM International Conference on Multimedia, pp. 4083–4091, 2022. doi
  33. G. Jaume, H. K. Ekenel and J.-P. Thiran, “FUNSD: A dataset for form understanding in noisy scanned documents,” in Proc. ICDAR Workshops (OST), 2019. doi
  34. G. Kim, T. Hong, M. Yim, J. Nam, J. Park, J. Yim, W. Hwang, S. Yun, D. Han and S. Park, “OCR-free document understanding transformer,” in Proc. ECCV, pp. 498–517, 2022. doi
  35. K. Lee, M. Joshi, I. R. Turc, H. Hu, F. Liu, J. M. Eisenschlos, U. Khandelwal, P. Shaw, M.-W. Chang and K. Toutanova, “Pix2Struct: Screenshot parsing as pretraining for visual language understanding,” in Proc. ICML, PMLR vol. 202, pp. 18893–18912, 2023. PMLR
  36. L. Blecher, G. Cucurull, T. Scialom and R. Stojnic, “Nougat: Neural optical understanding for academic documents,” in Proc. ICLR, 2024. OpenReview · arXiv
  37. U.-V. Marti and H. Bunke, “The IAM-database: An English sentence database for offline handwriting recognition,” International Journal on Document Analysis and Recognition, vol. 5, pp. 39–46, 2002. doi
  38. C.-L. Liu, F. Yin, D.-H. Wang and Q.-F. Wang, “CASIA online and offline Chinese handwriting databases,” in Proc. ICDAR, pp. 37–41, 2011. doi
  39. B. Shi, C. Yao, M. Liao, M. Yang, P. Xu, L. Cui, S. Belongie, S. Lu and X. Bai, “ICDAR2017 competition on reading Chinese text in the wild (RCTW-17),” in Proc. ICDAR, pp. 1429–1434, 2017. doi · arXiv
  40. T.-L. Yuan, Z. Zhu, K. Xu, C.-J. Li, T.-J. Mu and S.-M. Hu, “A large Chinese text dataset in the wild,” Journal of Computer Science and Technology, vol. 34, pp. 509–521, 2019. doi · arXiv
  41. F. Xue and R. Ishida (eds.), “Requirements for Chinese Text Layout,” W3C Group Note (draft of 7 October 2026). W3C
  42. N. Nayef, Y. Patel, M. Busta, P. N. Chowdhury, D. Karatzas, W. Khlif, J. Matas et al., “ICDAR2019 Robust Reading Challenge on multi-lingual scene text detection and recognition — RRC-MLT-2019,” in Proc. ICDAR, pp. 1582–1587, 2019. doi · arXiv
  43. R. A. Wagner and M. J. Fischer, “The string-to-string correction problem,” Journal of the ACM, vol. 21, no. 1, pp. 168–173, 1974. doi
  44. M. Mathew, D. Karatzas and C. V. Jawahar, “DocVQA: A dataset for VQA on document images,” in Proc. IEEE/CVF WACV, pp. 2199–2208, 2021. doi
  45. A. Mishra, K. Alahari and C. V. Jawahar, “Scene text recognition using higher order language priors,” in Proc. BMVC, 2012. doi
  46. K. Wang, B. Babenko and S. Belongie, “End-to-end scene text recognition,” in Proc. IEEE ICCV, pp. 1457–1464, 2011. doi
  47. L. Ouyang, Y. Qu, H. Zhou, J. Zhu, R. Zhang, Q. Lin, B. Wang, Z. Zhao et al., “OmniDocBench: Benchmarking diverse PDF document parsing with comprehensive annotations,” in Proc. IEEE/CVF CVPR, pp. 24838–24848, 2025. CVF
  48. H. Wei, C. Liu, J. Chen, J. Wang, L. Kong, Y. Xu, Z. Ge, L. Zhao et al., “General OCR theory: Towards OCR-2.0 via a unified end-to-end model,” arXiv:2409.01704, 2024. arXiv
  49. J. Poznanski, A. Rangapur, J. Borchardt, J. Dunkelberger, R. Huff, D. Lin, C. Wilhelm et al., “olmOCR: Unlocking trillions of tokens in PDFs with vision language models,” arXiv:2502.18443, 2025. arXiv
  50. H. Wei, Y. Sun and Y. Li, “DeepSeek-OCR: Contexts optical compression,” arXiv:2510.18234, 2025. arXiv
  51. C. Wolf and J.-M. Jolion, “Object count/area graphs for the evaluation of object detection and segmentation algorithms,” International Journal of Document Analysis and Recognition, vol. 8, pp. 280–296, 2006. doi