印刷体数学公式符号切分的研究
|
摘要
目前主流OCR (Optical Character Recognition,光学字符识别)技术虽然能够高速、自动地将印刷体文字信息输入计算机,但对于结构复杂、符号多变的数学公式仍然无能为力。数学公式是科技文献的重要组成部分,因此,数学公式识别问题已经成为模式识别领域炙手可热的课题。
印刷体数学公式识别系统包括公式抽取、公式符号识别、公式结构分析和公式重构四个组成部分。其中,数学公式符号识别是公式识别系统的核心部分,分为符号切分和符号识别两个阶段,而符号切分又是关键的一个环节。本文针对印刷体数学公式符号切分展开研究。首先设计并实现了一个能够处理公式二维嵌套结构的符号切分算法；然后基于识别结果以及粘连符号的特点,给出了一种基于轮廓特征的印刷公式粘连符号切分方法,通过检测粘连符号的凹凸轮廓以及轮廓的宽高比,并结合给出的粘连符号切分算法对粘连符号进行切分。通过对不同印刷质量文档的实验表明,本文设计的符号切分方法能够取得较高的切分正确率和令人满意的处理速度。
At present, the OCR system can input the ordinary text into computer quickly and automatically, but they cannot deal with mathematical formulas because of the complicated structures and various symbols. Mathematical formulas are the important components of the scientific documents. Therefore, mathematical formula recognition has become a hotspot in the area of pattern recognition.
Mathematical formula recognition typically consists of four major stages:mathematical formula extraction, mathematical symbol recognition, formula structural analysis and formula reconstruction. The mathematical symbol recognition is the core of the system, it consists of two steps:symbol segmentation and symbol recognition. The symbol segmentation is a key part, we do research work on the segmentation of printed formulas. Firstly, an algorithm that designed and implemented to deal with a nested structure of the two-dimensional symbol segmentation to handle mathematical formulas symbol segmentation, secondly, a method which is using contour feature is designed for segmenting touching symbols in mathematical formulas based on recognition result and touching characteristic, through examining the concave-convex contour of touching symbols and the beam-to-depth ratio of the contours, and using the algorithm to segment touching symbols. The experiments on different quality documents show that these methods can obtain satisfactory segmentation accuracy with a high speed.
印刷体数学公式识别系统包括公式抽取、公式符号识别、公式结构分析和公式重构四个组成部分。其中,数学公式符号识别是公式识别系统的核心部分,分为符号切分和符号识别两个阶段,而符号切分又是关键的一个环节。本文针对印刷体数学公式符号切分展开研究。首先设计并实现了一个能够处理公式二维嵌套结构的符号切分算法；然后基于识别结果以及粘连符号的特点,给出了一种基于轮廓特征的印刷公式粘连符号切分方法,通过检测粘连符号的凹凸轮廓以及轮廓的宽高比,并结合给出的粘连符号切分算法对粘连符号进行切分。通过对不同印刷质量文档的实验表明,本文设计的符号切分方法能够取得较高的切分正确率和令人满意的处理速度。
At present, the OCR system can input the ordinary text into computer quickly and automatically, but they cannot deal with mathematical formulas because of the complicated structures and various symbols. Mathematical formulas are the important components of the scientific documents. Therefore, mathematical formula recognition has become a hotspot in the area of pattern recognition.
Mathematical formula recognition typically consists of four major stages:mathematical formula extraction, mathematical symbol recognition, formula structural analysis and formula reconstruction. The mathematical symbol recognition is the core of the system, it consists of two steps:symbol segmentation and symbol recognition. The symbol segmentation is a key part, we do research work on the segmentation of printed formulas. Firstly, an algorithm that designed and implemented to deal with a nested structure of the two-dimensional symbol segmentation to handle mathematical formulas symbol segmentation, secondly, a method which is using contour feature is designed for segmenting touching symbols in mathematical formulas based on recognition result and touching characteristic, through examining the concave-convex contour of touching symbols and the beam-to-depth ratio of the contours, and using the algorithm to segment touching symbols. The experiments on different quality documents show that these methods can obtain satisfactory segmentation accuracy with a high speed.
引文
[1]R. H. Anderson. Syntex-directed recognition of hand-printed two-dimensional mathematics. In Interactive Systems for Experimental Applied Mathematics, Academic Press, New York,1968, 436-459.
[2]A. Belsid and J. P. Haton. A syntactic approach for handwritten mathematical formula recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence,1984,105-110.
[3]Z. X. Wang and C. Faure. Structural analysis of handwritten mathematical expressions. In Proceedings of 9th International Conference on Pattern Recognition, Rome, Italy,1988,32-34.
[4]R. J. Fateman, T. Tokuyasu, B. P. Berman, et al. Optical character recognition and parsing of typeset mathematics. Journal of Visual Communication and Image Representation,1996,7(1): 2-15.
[5]R. J. Fateman and T. Tokuyasu. Progress in recognizing typeset mathematics. In Proceedings of the SPIE Conference on Document Recognition, San Jose, CA,1996,2660:37-50.
[6]S. Lavirotte and L. Pottier. Optical formula recognition. In Proceedings of 4th International Conference on Document Analysis and Recognition, Germany,1997,357-361.
[7]Stewart and M. E. M. An experiment in scientific program understanding. The Fifteenth IEEE International Conference on Automated Software Engineering, ASE2000,2000,281-284.
[8]Y. Eto and M. Suzuki. Mathematical formula recognition using virtual link network. Proceedings of 6th International Conference on Document Analysis and Recognition, Seattle, Washington, USA, 2001,762-767.
[9]K. Toyozumi, T. Suzuki, K. Mori, et al. A system for real-time recognition of handwritten mathematical formulas. Proceedings of 6th International Conference on Document Analysis and Recognition, Seattle, Washington, USA,2001,1059-1063.
[10]K. F. Chan and D. Y. Yeung. Pen Calc:A novel application of on-Line mathematical expression recognition technology. Sixth International Conference on Document Analysis and Recognition, 2001,774-778.
[11]A. Vasserman. Identifying chemical names in biomedical text:an investigation of the substring co-occurrence based approaches. HLT/NAACL 2004 Student Research Workshop May 2nd,2004, 7-12.
[]2] 王科俊.林桂芳,王黎斌.数学表达式识别方法综述.自动化技术与应用,2003,22(8)：1-6.
[13]陈洪波.王强,许晓蓉.等.数学表达式的自动识别.广西科学.2004.11(1)：20-26.
[14]林桂芳.印刷体数学公式识别中符号识别技术的研究.哈尔滨工业大学.2004.2-0.
[15]吴俊飞.基于特征字符的印刷体公式识别研究.哈尔滨工业大学,2006.36-49.
[16]R. G Casey and E Lecolinet. A survey of methods and strategies in character segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence,1996,18 (7):690-706.
[17]U. Pal, A. Belaid and C. Chosiy. Touching numeral segmentation using water reservoir concept. International Journal of Pattern Recognition and Artificial Intelligence,1999.13 (6):833-858.
[18]K. F. Chan and D. Y. Yeung. Mathematical expression recognition:a survey. International Journal on Document Analysis and Recognition,2000,3 (1):3-15.
[19]H. J. Lee and J. S. Wang. Design of mathematical expression recognition system. In Proceedings of International Conference on Document Analysis and Recognition, Canada,1995,1084-1087.
[20]M. Suzuki, F. Tamari. R. fukada, et al. INFTY-an integrated OCR system for mathematical documents. The 2003 ACM Symposium on Document Engineering Table of Contents. France. 2003,95-104.
[21]M. Okamoto and B. Miao. Recognition of mathematical expressions by using the layout structures of symbols. In International Conference on Document Analysis and Recognition,1991.242-250.
[22]M. Okamoto and A. Miyazawa. An experimental implementation of a document recognition system for papers containing mathematical expressions. Structured Document Image Analysis. Springer-Verlag, Berlin.1992.36-53.
[23]J. Ha, R. M. Haralick and I. T. Phillips. Understanding mathematical expressions from document images. In International Conference on Document Analysis and Recognition,1995.956-959.
[24]李宁.印刷体数学表达式识别实现方法研究.广西师范大学,2005.11-58.
[25]U. Garain. B. B. Chaudhuri and R. P. Ghosh. A multiple-classifier system for recognition of printed mathematical symbols. Proceedings of the 17th International Conference on Pattern Recognition. University of Cambridge, UK, August 23-26,2004,380-383.
[26]U. Garain and B. B. Chaudhuri. Segmentation of touching symbols for OCR of printed mathematical expressions:an approach based on multifactorial analysis. Eighth International Conference on Document Analysis and Recognition,2005,177-181.
[27]J. Wang. Segmentation of merged characters by neural network and shortest path. Pattern Recognition,1994,27 (5):649-658.
[28]A. Nomura, K. Michishita, S. Uchida, et al. Detection and segmentation of touching characters in mathematical expressions. International Conference on Document Analysis and Recognition,2003, 126-130.
[29]胡小锋,陈超,叶庆泰.图书索书号粘连字符的切分.上海交通大学学报,2005,38(4)：553-556.
[30]Y. Lu, B. Haist, L. Harmon, J. Trenkle, et al. An acute and efficient system for segmenting machine-printed text. U.S. Postal Service 5th Advanced Technology Conference, Washington D.C., 1992,93-105.
[31]章毓晋.图像处理和分析基础.北京：高等教育出版社,2002,189.
[32]刘立波.图像分割方法探讨.宁夏农学院学报,2001,22(4)：51-56.
[33]杨述斌.图像边缘检测技术概述.武汉化工学院学报,2003,25(1)：73-76.
[34]Y. Lu. On the segmentation of touching characters. Int'l Conference on Document Analysis and Recognition'93. Tsukuba, Japan:IEEE Press,1993,440-443.
[35]S. Liang, M. Ahmadi and M. Shridhar. Segmentation of touching characters in printed document recognition. Int'l Conference on Document Analysis and Recognition'93. Tsukuba, Japan:IEEE Press,1993,569-572.
[36]S. Tsujimoto and H. Asada. Major components of a complete text reading system. Proceeding of the IEEE,1992,80 (7):1133-1149.
[37]G. Seni and E. Cohen. External word segmentation of off-line handwritten text lines. Pattern Recognition,1994,27 (1):41-52.
[38]R. G. Casey and G. Nagy. Recursive segmentation and classification of composite patterns. Proceedings of the 6th Int'l Conference on Pattern Recognition. Munich, Germany,1982,
1023-1026.
[39]T. Bayer, U. KreBel and M. Hammelsbeck. Segmenting merged characters. Pattern Recognition, 1992,25 (2):346-349.
[40]L. Heutte, T. Paquet, J. V. Moreau. et al. A structural/statistical feature based vector for handwritten character recognition. Pattern Recognition Letters,1998,19 (7):629-641.
[2]A. Belsid and J. P. Haton. A syntactic approach for handwritten mathematical formula recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence,1984,105-110.
[3]Z. X. Wang and C. Faure. Structural analysis of handwritten mathematical expressions. In Proceedings of 9th International Conference on Pattern Recognition, Rome, Italy,1988,32-34.
[4]R. J. Fateman, T. Tokuyasu, B. P. Berman, et al. Optical character recognition and parsing of typeset mathematics. Journal of Visual Communication and Image Representation,1996,7(1): 2-15.
[5]R. J. Fateman and T. Tokuyasu. Progress in recognizing typeset mathematics. In Proceedings of the SPIE Conference on Document Recognition, San Jose, CA,1996,2660:37-50.
[6]S. Lavirotte and L. Pottier. Optical formula recognition. In Proceedings of 4th International Conference on Document Analysis and Recognition, Germany,1997,357-361.
[7]Stewart and M. E. M. An experiment in scientific program understanding. The Fifteenth IEEE International Conference on Automated Software Engineering, ASE2000,2000,281-284.
[8]Y. Eto and M. Suzuki. Mathematical formula recognition using virtual link network. Proceedings of 6th International Conference on Document Analysis and Recognition, Seattle, Washington, USA, 2001,762-767.
[9]K. Toyozumi, T. Suzuki, K. Mori, et al. A system for real-time recognition of handwritten mathematical formulas. Proceedings of 6th International Conference on Document Analysis and Recognition, Seattle, Washington, USA,2001,1059-1063.
[10]K. F. Chan and D. Y. Yeung. Pen Calc:A novel application of on-Line mathematical expression recognition technology. Sixth International Conference on Document Analysis and Recognition, 2001,774-778.
[11]A. Vasserman. Identifying chemical names in biomedical text:an investigation of the substring co-occurrence based approaches. HLT/NAACL 2004 Student Research Workshop May 2nd,2004, 7-12.
[]2] 王科俊.林桂芳,王黎斌.数学表达式识别方法综述.自动化技术与应用,2003,22(8)：1-6.
[13]陈洪波.王强,许晓蓉.等.数学表达式的自动识别.广西科学.2004.11(1)：20-26.
[14]林桂芳.印刷体数学公式识别中符号识别技术的研究.哈尔滨工业大学.2004.2-0.
[15]吴俊飞.基于特征字符的印刷体公式识别研究.哈尔滨工业大学,2006.36-49.
[16]R. G Casey and E Lecolinet. A survey of methods and strategies in character segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence,1996,18 (7):690-706.
[17]U. Pal, A. Belaid and C. Chosiy. Touching numeral segmentation using water reservoir concept. International Journal of Pattern Recognition and Artificial Intelligence,1999.13 (6):833-858.
[18]K. F. Chan and D. Y. Yeung. Mathematical expression recognition:a survey. International Journal on Document Analysis and Recognition,2000,3 (1):3-15.
[19]H. J. Lee and J. S. Wang. Design of mathematical expression recognition system. In Proceedings of International Conference on Document Analysis and Recognition, Canada,1995,1084-1087.
[20]M. Suzuki, F. Tamari. R. fukada, et al. INFTY-an integrated OCR system for mathematical documents. The 2003 ACM Symposium on Document Engineering Table of Contents. France. 2003,95-104.
[21]M. Okamoto and B. Miao. Recognition of mathematical expressions by using the layout structures of symbols. In International Conference on Document Analysis and Recognition,1991.242-250.
[22]M. Okamoto and A. Miyazawa. An experimental implementation of a document recognition system for papers containing mathematical expressions. Structured Document Image Analysis. Springer-Verlag, Berlin.1992.36-53.
[23]J. Ha, R. M. Haralick and I. T. Phillips. Understanding mathematical expressions from document images. In International Conference on Document Analysis and Recognition,1995.956-959.
[24]李宁.印刷体数学表达式识别实现方法研究.广西师范大学,2005.11-58.
[25]U. Garain. B. B. Chaudhuri and R. P. Ghosh. A multiple-classifier system for recognition of printed mathematical symbols. Proceedings of the 17th International Conference on Pattern Recognition. University of Cambridge, UK, August 23-26,2004,380-383.
[26]U. Garain and B. B. Chaudhuri. Segmentation of touching symbols for OCR of printed mathematical expressions:an approach based on multifactorial analysis. Eighth International Conference on Document Analysis and Recognition,2005,177-181.
[27]J. Wang. Segmentation of merged characters by neural network and shortest path. Pattern Recognition,1994,27 (5):649-658.
[28]A. Nomura, K. Michishita, S. Uchida, et al. Detection and segmentation of touching characters in mathematical expressions. International Conference on Document Analysis and Recognition,2003, 126-130.
[29]胡小锋,陈超,叶庆泰.图书索书号粘连字符的切分.上海交通大学学报,2005,38(4)：553-556.
[30]Y. Lu, B. Haist, L. Harmon, J. Trenkle, et al. An acute and efficient system for segmenting machine-printed text. U.S. Postal Service 5th Advanced Technology Conference, Washington D.C., 1992,93-105.
[31]章毓晋.图像处理和分析基础.北京：高等教育出版社,2002,189.
[32]刘立波.图像分割方法探讨.宁夏农学院学报,2001,22(4)：51-56.
[33]杨述斌.图像边缘检测技术概述.武汉化工学院学报,2003,25(1)：73-76.
[34]Y. Lu. On the segmentation of touching characters. Int'l Conference on Document Analysis and Recognition'93. Tsukuba, Japan:IEEE Press,1993,440-443.
[35]S. Liang, M. Ahmadi and M. Shridhar. Segmentation of touching characters in printed document recognition. Int'l Conference on Document Analysis and Recognition'93. Tsukuba, Japan:IEEE Press,1993,569-572.
[36]S. Tsujimoto and H. Asada. Major components of a complete text reading system. Proceeding of the IEEE,1992,80 (7):1133-1149.
[37]G. Seni and E. Cohen. External word segmentation of off-line handwritten text lines. Pattern Recognition,1994,27 (1):41-52.
[38]R. G. Casey and G. Nagy. Recursive segmentation and classification of composite patterns. Proceedings of the 6th Int'l Conference on Pattern Recognition. Munich, Germany,1982,
1023-1026.
[39]T. Bayer, U. KreBel and M. Hammelsbeck. Segmenting merged characters. Pattern Recognition, 1992,25 (2):346-349.
[40]L. Heutte, T. Paquet, J. V. Moreau. et al. A structural/statistical feature based vector for handwritten character recognition. Pattern Recognition Letters,1998,19 (7):629-641.