基于顶点链编码的表格图像分析
|
摘要
顶点链编码是数字图像处理领域非常重要的工具。链编码的优点是十分明显的。它把二维图像的存储和处理变为一维链上的问题。对于大尺度的图像，链编码可以大幅度地节省存储空间并提高处理速度。该算法对推动顶点链编码在图像处理领域的应用，起到了重要作用。
表格文档分析与识别是计算机文档处理中的一个重要项目。表格是文档中常用的数据资料载体，因而表格图像分析技术的研究具有很大的潜在的应用价值。本文基于顶点链编码技术，提出了一种新的表格图像分析算法，并发展了一种自定义的表格文件格式，对丰富表格文档的分析手段，减小表格图像的存储空间都有很大的作用。
由于在用扫描仪和数字照相机获得表格文档时，倾斜总是难免的，因此表格图像的倾斜探测和矫正是表格图像分析的第一步，也是表格分析及以后各项识别工作准确性的保证。物体在数字图像中占据的面积在图像分析和识别中具有重要的作用。通常采用的方法是积分法，但对于各种极其复杂的图像形状，该算法不一定适用。因此，人们对具体对象研究了不少其他算法。但是这些算法普遍存在的问题就是运算量较大，计算时间长。
本文针对这两个问题，提出了新的算法。首先，根据表格图像中，表格的框线或悬线具有最长的边界，以及边界标定自动机能获得区域边界的优点，提出了一种新的表格图像文件倾斜矫正的方法。该方法使用简便，而且在大噪声的背景下也能使用。其次，提出直接从顶点链编码计算封闭边界所围区域的面积的方法，对于正方形、正三边形和正六边形点阵上的图形，都有直接从链编码计算区域面积的方法。最后，通过实验证明了两个算法的有效性。
本文在研究算法的同时，在windows平台下，使用Visual C斗¨}编程工具，对涉及的算法进行了系统开发和实现。
The form recognition is important in document processing by computer. We often take the forms as the carriers of data and information, so there is great potential value in the research of the form analysis and form recognition. Based on the Vertex Chain Code, in this paper, we propose a new algorithm for form-analysis and develop a new format of form file, which is very important for form analysis and saving considerable memory space for form image.
When we get image from scanner or digital camera, the image is often skew, so skew detection and skew correction of images for text documents and form documents is the first step for optical character recognition and form analysis. The areas of objects in digital images play an important role in image analysis and pattern recognition. We usual use the method of integral, but for some complicated images and figures, the method may not work well. So many algorithms have proposed to solve this question. But there are some universal problems in these algorithms, for example, long time of calculation.
To solve the two questions mentioned above, our group propose two new algorithms, which have been validated by test. One is the skew detection and skew correction of images. The other is the calculation of area of object in digital image.
While researching algorithms, we use the Visual C++ developing tool to accomplish the related algorithms on the Windows platform.
表格文档分析与识别是计算机文档处理中的一个重要项目。表格是文档中常用的数据资料载体，因而表格图像分析技术的研究具有很大的潜在的应用价值。本文基于顶点链编码技术，提出了一种新的表格图像分析算法，并发展了一种自定义的表格文件格式，对丰富表格文档的分析手段，减小表格图像的存储空间都有很大的作用。
由于在用扫描仪和数字照相机获得表格文档时，倾斜总是难免的，因此表格图像的倾斜探测和矫正是表格图像分析的第一步，也是表格分析及以后各项识别工作准确性的保证。物体在数字图像中占据的面积在图像分析和识别中具有重要的作用。通常采用的方法是积分法，但对于各种极其复杂的图像形状，该算法不一定适用。因此，人们对具体对象研究了不少其他算法。但是这些算法普遍存在的问题就是运算量较大，计算时间长。
本文针对这两个问题，提出了新的算法。首先，根据表格图像中，表格的框线或悬线具有最长的边界，以及边界标定自动机能获得区域边界的优点，提出了一种新的表格图像文件倾斜矫正的方法。该方法使用简便，而且在大噪声的背景下也能使用。其次，提出直接从顶点链编码计算封闭边界所围区域的面积的方法，对于正方形、正三边形和正六边形点阵上的图形，都有直接从链编码计算区域面积的方法。最后，通过实验证明了两个算法的有效性。
本文在研究算法的同时，在windows平台下，使用Visual C斗¨}编程工具，对涉及的算法进行了系统开发和实现。
The form recognition is important in document processing by computer. We often take the forms as the carriers of data and information, so there is great potential value in the research of the form analysis and form recognition. Based on the Vertex Chain Code, in this paper, we propose a new algorithm for form-analysis and develop a new format of form file, which is very important for form analysis and saving considerable memory space for form image.
When we get image from scanner or digital camera, the image is often skew, so skew detection and skew correction of images for text documents and form documents is the first step for optical character recognition and form analysis. The areas of objects in digital images play an important role in image analysis and pattern recognition. We usual use the method of integral, but for some complicated images and figures, the method may not work well. So many algorithms have proposed to solve this question. But there are some universal problems in these algorithms, for example, long time of calculation.
To solve the two questions mentioned above, our group propose two new algorithms, which have been validated by test. One is the skew detection and skew correction of images. The other is the calculation of area of object in digital image.
While researching algorithms, we use the Visual C++ developing tool to accomplish the related algorithms on the Windows platform.
引文
[1] 顾国庆，陈可．Region-Labeling-Automata for Images in Square, Triangular and Hexagonal Lattice, Advances in Computer and Information Technology, The Journal of Three Dimensional Images, 17 (2003)161-165.
[2] 顾国庆，陈可．Region-Labeling-Automata for Images in Square, Triangular and Hexagonal Lattice, Advances in Computer and Information Technology, The Proceedings of 2002 International Conference on Computer and Information Technology, (Aizu-Wakamatsu City, Japan, Sept. 11-14, 2002) 134-138.
[3] 顾国庆，许彦冰．数字图像区域标定的方法．上海理工大学学报，Vol．23，No．4，2001：295-299．
[4] 许彦冰，顾国庆．Method to generate vertex chain code and the calculation of geometric quantities. Journal of Shanghai University, Vol. 5 Suppl. (Sep. 2001) 144-146.
[5] 许彦冰．表格图像的模式识别算法研究．上海理工大学硕士学位论文，2001．
[6] 张昆，顾国庆．二值图像的一种倾斜调整方法．计算机与现代化，1999(2)：45-50．
[7] 何斌，马天予，王运坚，朱红莲．Visual C++数字图像处理．北京：人民邮电出版社，2001：4-674．
[8] 沈庭芝，方子文．数字图像处理及模式识别．北京：北京理工大学出版社，1998：1-214．
[9] David F. Rogers．计算机图形学的算法基础．北京：机械工业出版社，2002．1：77-105．
[10] 陈传波等．计算机图形学基础．北京：电子工业出版社，2002：122-132．
[11] David J. Kruglinski, Scot Wingo, George Shepherd. Programming Visual C++ 6.0技术内幕(第五版)．北京：北京希望电子出版社，1999．
[12] 史文革．微机图像格式大全．北京：海洋大学出版社，1996．
[13] 罗希平，田捷，诸葛婴等．图像分割方法综述．模式识别和人工智能，1999：300-304
[14] 勒宏磊，朱蔚萍，李立源等．二维灰度直方图的最佳分割方法．模式识别与人工智能，Vol．12，No．3，Sept 1999．
[15] 李于剑．Visual C++实践与提高 图形图像编程篇．北京：中国铁道出版社，2001．
[16] 王润生．图像理解．北京：国防科技大学出版社，1995：50-234．
[17] 赵荣椿等．数字图像处理导论．西安：西北工业大学出版社，1999：30-231．
[18] 林沛源，蒲和平．计算机图形图像处理应用技术．电子科技大学出版社，1997：1-63．
[19] 徐建华．图像处理与分析．北京：科学出版社．1992：1-53．
[20] 潘武模，焦扬，王庆人．Hough变换在中文名片图像倾斜校正中的应用．中文信息学报，Vol．15．No．3．
[21] 张纯，张涛，黄笑．中文商务名片识别系统的实现．中文信息学报，Vol．14，No．2．
[22] 许长安．现代图像编码方法．安庆师范学院学报(自然科学版)，Vol．5，No．4，Nov 1999．
[23] 张雪松，倪国强，周立伟，金伟其．图像编码技术发展综述．光学技术，No．3，May 1997．
[24] 王碧泉，陈祖荫．模式识别理论、方法和应用．北京：地震出版社，1989：21-126．
[25] 傅京孙．模式识别及其应用．上海科技出版社，1983．
[26] 鸿志创作组．Visual C++5.0编程指南．北京：科学出版社，1998．4．
[27] Kenneth R. Castleman. Digital Image Processing. Prentice Hall, 1996．北京：清华大学出版社，1998．3：492-451．
[28] Freeman H. Computer processing of line-drawing images. Computing Surveys, 1974, 6 (1):57-97.
[29] Freeman H. On the encoding of arbitrary geometric configuration. IRE Trans, 1961, EC-10 (2):260-268.
[30] Freeman H. Techniques for the digital computer analysis of chain-encoded arbitrary plane curves. Proc. Natl. Elect. Conf., 1961, 17 (Oct.):421-432.
[31] Freeman H. A technique for the classification and recognition of geometric patterns. Proc. 3rd. Intl. Congress on Cybernetics Namtur, 1961 (Belgium):348-368.
[32] Sidhu G S, Boute R T. Property encoding: applications in binary picture encoding and boundary following. IEEE Trans. Comp., 1972, C-21 (11):1206-1216.
[33] Merrill R. D. Representation of contours and regions for efficient computer search. Comm. ACM, 1973, 16(2):69-82.
[34] Bribiesca E. A new chain code. Pattern Recognition. 1999, 32: 235-251.
[35] Ari Gross, Longin Jan hatecki. Digital geometric methods in document image analysis. Pattern Recognition, 32 (1999) 407-424.
[36] Won Pil Yu, Gil Whoan Chu, Myung Jin Chung. A robust line extraction method by unsupervised line clustering. Pattern Recognition, 32 (1999) 529-546.
[37] Antoine Ting, Maylor K.H. Leung. Form recognition using linear structure. Pattern Recognition, 32 (1999) 645-656.
[38] S. Messelodi, C.M, Modena. Automatic identification and skew estimation of text lines in real scene images. Pattern Recognition, 32 (1999) 791-810.
[39] Y-K. Chen, J-F. Wang. A document skew detection method. Pattern Recognition, 33 (2000) 195-208.
[40] Jinhui Liu, A.K. Jain. Image-based form document retrieval. Pattern Recognition, 33 (2000)503-513.
[41] 张永．基于编译的RTF算法研究及其在排版系统中的应用．上海理工大学硕士学位论文，2002．
[42] 李国强，张薇，顾国庆．顶点链编码和区域面积的计算方法．上海理工大学学报，267-270，Vol．25 No．3 2003
[43] 高永英，张利，吴国威．一种基于灰度期望值的图像二值化算法．中国图像图形学报，Vol．4(A)，No．6，June 1999．
[44] 吴伟．数字图像处理算法研究及其在名片识别系统中的应用．上海理工大学硕士学位论文，2003．
[45] 王厚大 一种计算任意封闭形状面积的方法 南京邮电学院学报 第17卷第4期1997年12月
[46] Y.Y. Tang, C.Y. Suen, Document structures: a survey, Int. J. Pattern Recognition Artif Intell. 8 (5) (1994) 1081-1111.
[47] Y.Y. Tang, C.D. Yah, C.Y. Suen, Document processing for automatic knowledge acquisition, IEEE Trans. Knowledge Data Engrs 6 (1) (1994) 3-21.
[48] Y.Y. Tang, C.D. Yah, M. Cheriet, C.Y. Suen, Automatic analysis and understanding of documents, in Handbook of Pattern Recognition and Computer Vision, C.H. Chen, L.F. Pau and P.S.P. Wang, eds, pp. 625-654, World Scientific, Singapore (1993).
[49] T. Watanabe, Q. Luo, N. Sugie, Structure recognition methods for various documents, Machine Vision Appl. 6, (1993) 163-176.
[50] R. Haralick, Document image understanding, Proc. ICCV, (1994) 385-390.
[51] A. Pizano, M.I. Tan, N. Gambo, A business form recognition system, Proc. COMPSAC, (1991) pp. 626-632.
[52] R. Casey, D. Ferguson, K. Mohiuddin, E. Walach, Intelligent forms processing system, Machine Vision Appl, 5 (1992) 143-155.
[53] S.W. Lam, L. Javanbakht, S.N. Srihari, Anatomy of a form reader, Proc. 2nd ICDAR, (1993) pp. 506-509.
[54] S. Leibowitz Taylor, R. Fritzson and J.A. Pastor, Extractionof data from preprinted forms, Machine Vision Appl. 5, (1992) 211-222.
[55] D.S. Doermann, A. Rosenfeld, The processing of form documents, Proc. 2nd ICDAR, (1993) pp. 497-501.
[56] D. Wang, S. N. Srihari, Analysis of form images, Int. J. Pattern Recog. Artificial Intell. 8 (5), (1994) pp. 1031-1052.
[57] Antoine Ting, Maylor K. H. Leung. Form recognition using linear structure. Pattern Recognition, 32 (1999) 645-656.
[58] 张圣希，张薇，李国强，顾国庆．利用顶点链编码探测表格的斜率．华东师范大学学报，己录用，待发表．
[2] 顾国庆，陈可．Region-Labeling-Automata for Images in Square, Triangular and Hexagonal Lattice, Advances in Computer and Information Technology, The Proceedings of 2002 International Conference on Computer and Information Technology, (Aizu-Wakamatsu City, Japan, Sept. 11-14, 2002) 134-138.
[3] 顾国庆，许彦冰．数字图像区域标定的方法．上海理工大学学报，Vol．23，No．4，2001：295-299．
[4] 许彦冰，顾国庆．Method to generate vertex chain code and the calculation of geometric quantities. Journal of Shanghai University, Vol. 5 Suppl. (Sep. 2001) 144-146.
[5] 许彦冰．表格图像的模式识别算法研究．上海理工大学硕士学位论文，2001．
[6] 张昆，顾国庆．二值图像的一种倾斜调整方法．计算机与现代化，1999(2)：45-50．
[7] 何斌，马天予，王运坚，朱红莲．Visual C++数字图像处理．北京：人民邮电出版社，2001：4-674．
[8] 沈庭芝，方子文．数字图像处理及模式识别．北京：北京理工大学出版社，1998：1-214．
[9] David F. Rogers．计算机图形学的算法基础．北京：机械工业出版社，2002．1：77-105．
[10] 陈传波等．计算机图形学基础．北京：电子工业出版社，2002：122-132．
[11] David J. Kruglinski, Scot Wingo, George Shepherd. Programming Visual C++ 6.0技术内幕(第五版)．北京：北京希望电子出版社，1999．
[12] 史文革．微机图像格式大全．北京：海洋大学出版社，1996．
[13] 罗希平，田捷，诸葛婴等．图像分割方法综述．模式识别和人工智能，1999：300-304
[14] 勒宏磊，朱蔚萍，李立源等．二维灰度直方图的最佳分割方法．模式识别与人工智能，Vol．12，No．3，Sept 1999．
[15] 李于剑．Visual C++实践与提高 图形图像编程篇．北京：中国铁道出版社，2001．
[16] 王润生．图像理解．北京：国防科技大学出版社，1995：50-234．
[17] 赵荣椿等．数字图像处理导论．西安：西北工业大学出版社，1999：30-231．
[18] 林沛源，蒲和平．计算机图形图像处理应用技术．电子科技大学出版社，1997：1-63．
[19] 徐建华．图像处理与分析．北京：科学出版社．1992：1-53．
[20] 潘武模，焦扬，王庆人．Hough变换在中文名片图像倾斜校正中的应用．中文信息学报，Vol．15．No．3．
[21] 张纯，张涛，黄笑．中文商务名片识别系统的实现．中文信息学报，Vol．14，No．2．
[22] 许长安．现代图像编码方法．安庆师范学院学报(自然科学版)，Vol．5，No．4，Nov 1999．
[23] 张雪松，倪国强，周立伟，金伟其．图像编码技术发展综述．光学技术，No．3，May 1997．
[24] 王碧泉，陈祖荫．模式识别理论、方法和应用．北京：地震出版社，1989：21-126．
[25] 傅京孙．模式识别及其应用．上海科技出版社，1983．
[26] 鸿志创作组．Visual C++5.0编程指南．北京：科学出版社，1998．4．
[27] Kenneth R. Castleman. Digital Image Processing. Prentice Hall, 1996．北京：清华大学出版社，1998．3：492-451．
[28] Freeman H. Computer processing of line-drawing images. Computing Surveys, 1974, 6 (1):57-97.
[29] Freeman H. On the encoding of arbitrary geometric configuration. IRE Trans, 1961, EC-10 (2):260-268.
[30] Freeman H. Techniques for the digital computer analysis of chain-encoded arbitrary plane curves. Proc. Natl. Elect. Conf., 1961, 17 (Oct.):421-432.
[31] Freeman H. A technique for the classification and recognition of geometric patterns. Proc. 3rd. Intl. Congress on Cybernetics Namtur, 1961 (Belgium):348-368.
[32] Sidhu G S, Boute R T. Property encoding: applications in binary picture encoding and boundary following. IEEE Trans. Comp., 1972, C-21 (11):1206-1216.
[33] Merrill R. D. Representation of contours and regions for efficient computer search. Comm. ACM, 1973, 16(2):69-82.
[34] Bribiesca E. A new chain code. Pattern Recognition. 1999, 32: 235-251.
[35] Ari Gross, Longin Jan hatecki. Digital geometric methods in document image analysis. Pattern Recognition, 32 (1999) 407-424.
[36] Won Pil Yu, Gil Whoan Chu, Myung Jin Chung. A robust line extraction method by unsupervised line clustering. Pattern Recognition, 32 (1999) 529-546.
[37] Antoine Ting, Maylor K.H. Leung. Form recognition using linear structure. Pattern Recognition, 32 (1999) 645-656.
[38] S. Messelodi, C.M, Modena. Automatic identification and skew estimation of text lines in real scene images. Pattern Recognition, 32 (1999) 791-810.
[39] Y-K. Chen, J-F. Wang. A document skew detection method. Pattern Recognition, 33 (2000) 195-208.
[40] Jinhui Liu, A.K. Jain. Image-based form document retrieval. Pattern Recognition, 33 (2000)503-513.
[41] 张永．基于编译的RTF算法研究及其在排版系统中的应用．上海理工大学硕士学位论文，2002．
[42] 李国强，张薇，顾国庆．顶点链编码和区域面积的计算方法．上海理工大学学报，267-270，Vol．25 No．3 2003
[43] 高永英，张利，吴国威．一种基于灰度期望值的图像二值化算法．中国图像图形学报，Vol．4(A)，No．6，June 1999．
[44] 吴伟．数字图像处理算法研究及其在名片识别系统中的应用．上海理工大学硕士学位论文，2003．
[45] 王厚大 一种计算任意封闭形状面积的方法 南京邮电学院学报 第17卷第4期1997年12月
[46] Y.Y. Tang, C.Y. Suen, Document structures: a survey, Int. J. Pattern Recognition Artif Intell. 8 (5) (1994) 1081-1111.
[47] Y.Y. Tang, C.D. Yah, C.Y. Suen, Document processing for automatic knowledge acquisition, IEEE Trans. Knowledge Data Engrs 6 (1) (1994) 3-21.
[48] Y.Y. Tang, C.D. Yah, M. Cheriet, C.Y. Suen, Automatic analysis and understanding of documents, in Handbook of Pattern Recognition and Computer Vision, C.H. Chen, L.F. Pau and P.S.P. Wang, eds, pp. 625-654, World Scientific, Singapore (1993).
[49] T. Watanabe, Q. Luo, N. Sugie, Structure recognition methods for various documents, Machine Vision Appl. 6, (1993) 163-176.
[50] R. Haralick, Document image understanding, Proc. ICCV, (1994) 385-390.
[51] A. Pizano, M.I. Tan, N. Gambo, A business form recognition system, Proc. COMPSAC, (1991) pp. 626-632.
[52] R. Casey, D. Ferguson, K. Mohiuddin, E. Walach, Intelligent forms processing system, Machine Vision Appl, 5 (1992) 143-155.
[53] S.W. Lam, L. Javanbakht, S.N. Srihari, Anatomy of a form reader, Proc. 2nd ICDAR, (1993) pp. 506-509.
[54] S. Leibowitz Taylor, R. Fritzson and J.A. Pastor, Extractionof data from preprinted forms, Machine Vision Appl. 5, (1992) 211-222.
[55] D.S. Doermann, A. Rosenfeld, The processing of form documents, Proc. 2nd ICDAR, (1993) pp. 497-501.
[56] D. Wang, S. N. Srihari, Analysis of form images, Int. J. Pattern Recog. Artificial Intell. 8 (5), (1994) pp. 1031-1052.
[57] Antoine Ting, Maylor K. H. Leung. Form recognition using linear structure. Pattern Recognition, 32 (1999) 645-656.
[58] 张圣希，张薇，李国强，顾国庆．利用顶点链编码探测表格的斜率．华东师范大学学报，己录用，待发表．