A hierarchical, HMM-based automatic evaluation of OCR accuracy for a digital library of books

ABSTRACT

A number of projects are creating searchable digital libraries of printed books. These include the Million Book Project, the Google Book project and similar efforts from Yahoo and Microsoft. Content-based on line book retrieval usually requires first converting printed text into machine readable (e.g. ASCII) text using an optical character recognition (OCR) engine and then doing full text search on the results. Many of these books are old and there are a variety of processing steps that are required to create an end to end system. Changing any step (including the scanning process) can affect OCR performance and hence a good automatic statistical evaluation of OCR performance on book length material is needed. Evaluating OCR performance on the entire book is non-trivial. The only easily obtainable ground truth (the Gutenberg e-texts) must be automatically aligned with the OCR output over the entire length of a book. This may be viewed as equivalent to the problem of aligning two large (easily a million long) sequences. The problem is further complicated by OCR errors as well as the possibility of large chunks of missing material in one of the sequences. We propose a Hidden Markov Model (HMM) based hierarchical alignment algorithm to align OCR output and the ground truth for books. We believe this is the first work to automatically align a whole book without using any book structure information. The alignment process works by breaking up the problem of aligning two long sequences into the problem of aligning many smaller subsequences. This can be rapidly and effectively done. Experimental results show that our hierarchical alignment approach works very well even if OCR output has a high recognition error rate. Finally, we evaluate the performance of a commercial OCR engine over a large dataset of books based on the alignment results.

REFERENCES

• 1: H. Alshawi, S. Bangalore, and S. Douglas. Learning phrase-based head transduction models for translation of spoken utterances. In Proceedings of the fifth International Conference on Spoken Language Processing (ICSLP98), Sydney, 1998.
• 2: X. Chen and A. Yuille. Detecting and reading text in natural scenes. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition., pages 366--373, Washington, DC, USA, 2004.
• 3: Y. Deng and W. Byrne. Hmm word and phrase alignment for statistical machine translation. In Proceedings of HLT-EMNLP, 2005.
• 4: Gutenberg Website:. http://www.gutenberg.com.
• 5: T. Ho and H. Baird. Evaluation of ocr accuracy using synthetic data. In Proceedings of 4th UNLV Symp. on Document Analysis and Information Retrieval, Las Vegas, Nevada, USA, April 1995.
• 6: J. Hobby. Matching document images with ground truth. International Journal on Document Analysis and Recognition, 1(1):52--61, 1997.
• 7: Photina Jaeyun Jang , Alexander G. Hauptmann, Learning to Recognize Speech by Watching Television, IEEE Intelligent Systems, v.14 n.5, p.51-58, September 1999 [doi>10.1109/5254.796090]
• 8: Tapas Kanungo , Robert M. Haralick , Werner Stuezle , Henry S. Baird , David Madigan, A Statistical, Nonparametric Methodology for Document Degradation Model Validation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.11, p.1209-1223, November 2000 [doi>10.1109/34.888707]
• 9: Martin Kay , Martin Röscheisen, Text-translation alignment, Computational Linguistics, v.19 n.1, March 1993
• 10: E. Micah Kornfield , R. Manmatha , James Allan, Text Alignment with Handwritten Documents, Proceedings of the First International Workshop on Document Image Analysis for Libraries (DIAL'04), p.195, January 23-24, 2004
• 11: A. Krogh, M. Brown, I. Mian, K. Sjolander, and D. Haussler. Hidden markov models in computational biology: Applications to protein modeling. Journal of Molecular Biology, 235:1501--1531, 1994.
• 12: F. Malfrre, O. Deroo, and T. Dutoit. Phonetic alignment: Speech synthesis based vs. hybrid hmm/ann. In Proceedings of the ICSLP, pages 1571--1574, 1998.
• 13: S. Needleman and C. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443--53, 1970.
• 14: L. Rabiner and B. Juang. An introduction to hidden Markov models. IEEE ASSP Magazine, pages 4--15, January 1986.
• 15: J. Rothfeder, T. Rath, and R. Manmatha. Aligning transcripts to automatically segmented handwritten manuscripts. In to appear in Proceedings of the Seventh International Workshop on Document Analysis Systems, DAS'06, Nelson, New Zealand, 2006.
• 16: D. Roy , C. Malamud, Speaker Identification Based Text to Audio Alignment for an Audio Retrieval System, Proceedings of the 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '97)-Volume 2, p.1099, April 21-24, 1997
• 17: T. Smith and M. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(3):195--197, 1981.
• 18: A. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE transactions on Information Theory, 13:260--267, April 1967.
• 19: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 20: Victor Wu , Raghavan Manmatha , Edward M. Riseman, Sr., TextFinder: An Automatic System to Detect and Recognize Text In Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.11, p.1224-1229, November 1999 [doi>10.1109/34.809116]
• 21: Yihong Xu , George Nagy, Prototype Extraction and Adaptive OCR, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.12, p.1280-1296, December 1999 [doi>10.1109/34.817408]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Documentation

Keywords:
OCR evaluation, book alignment, digital libraries