完整搜尋頁面 →

CTC 前綴束搜尋,一步一步來

選讀・DLCV 06・影像中的文字:OCR 與文件理解 的補充資料(第 1/5 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

本頁內容

補充資料 · 5

  1. CTC 前綴束搜尋,一步一步來
  2. 縮小與放大文字多邊形
  3. 語言模型在辨識器裡的位置
  4. 閱讀直排與混合方向的文字
  5. 評估協定的細節

論文導讀 · 4

  1. 現代觀點綜述導讀
  2. Baek 等人:What Is Wrong With Scene Text Recognition Model Comparisons?(ICCV 2019)
  3. DBNet 導讀
  4. Donut 導讀

電腦視覺深度學習

  1. 02 · 深度影像分類
  2. 03 · 物件偵測:從 R-CNN 到 DETR
  3. 09 · 深度影像復原:低階視覺
查看完整課程樹 →

這則補充說明 CTC 解碼器怎麼找到可能的文字而不是可能的路徑:它搜尋的是前綴,而不是對齊。

搜尋的是什麼。 前綴 ℓ\ell 是一段部分轉錄,例如「ca」。讀完畫格 1,…,t1, \dots, t 之後,許多對齊會合併成同一個前綴。前綴束搜尋為每個前綴保留兩個數字:

  • pb(ℓ,t)p_b(\ell, t):畫格 1..t1..t 中,合併成 ℓ\ell 且結尾是空白的對齊的總機率;
  • pnb(ℓ,t)p_{nb}(\ell, t):其中結尾是 ℓ\ell 最後一個標籤的對齊的總機率。

兩者之和,就是前 tt 個畫格讀成 ℓ\ell 的機率。需要拆開,是因為下一個符號在兩種情況下的行為不同。

更新規則。 對每個保留的前綴 ℓ\ell 與畫格 t+1t+1 的每個符號 ss,令 q=qt+1(s)q = q_{t+1}(s) 為網路給 ss 的機率:

  1. 空白(s=∅s = \varnothing):前綴不變,而且對齊現在以空白結尾:把 (pb+pnb) q(p_b + p_{nb})\,q 加到 pb(ℓ,t+1)p_b(\ell, t+1)。
  2. 重複最後一個標籤(ss 等於 ℓ\ell 的最後一個標籤):如果前一個符號就是那個標籤,重複會被合併,前綴仍是 ℓ\ell:把 pnb qp_{nb}\,q 加到 pnb(ℓ,t+1)p_{nb}(\ell, t+1)。如果前一個符號是空白,重複就開啟一個新的副本:把 pb qp_b\,q 加到 pnb(ℓs,t+1)p_{nb}(\ell s, t+1)。「aa」就是這樣寫成「a-a」的。
  3. 其他任何標籤:延伸前綴:把 (pb+pnb) q(p_b + p_{nb})\,q 加到 pnb(ℓs,t+1)p_{nb}(\ell s, t+1)。

每個畫格之後,只保留 pb+pnbp_b + p_{nb} 最大的 BB 個前綴(束寬,beam width)。最後回傳最好的前綴。束寬不受限時,結果對 CTC 模型是精確的;B=1B = 1 時,行為幾乎和貪婪解碼一樣。

程式碼 · Python · 33 行
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))

輸出

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

在本篇的玩具範例上,束寬 1 回傳「ca」,和貪婪解碼一樣。束寬 3 已經找到「cat」,只是機率略低(0.344),因為它的某些對齊經過了被剪掉的前綴。束寬 20 在這裡保留了每個前綴,並重現暴力加總得到的精確值 0.363。

陷阱。 序列很長時要在對數空間計算,因為連乘會下溢。不要依路徑去重,只依前綴去重。加入詞典或語言模型時,它的分數通常在前綴被某個標籤延伸時套用,乘上調好的係數,並常搭配每輸出一個字元的獎勵,免得搜尋偏好短輸出;這些權重要在保留的資料上調整,而且正文中描述的同一種過度修正風險依然適用。

參考文獻

  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