Identifying table boundaries in digital documents via sparse line detection

ABSTRACT

Most prior work on information extraction has focused on extracting information from text in digital documents. However, often, the most important information being reported in an article is presented in tabular form in a digital document. If the data reported in tables can be extracted and stored in a database, the data can be queried and joined with other data using database management systems. In order to prepare the data source for table search, accurately detecting the table boundary plays a crucial role for the later table structure decomposition. Table boundary detection and content extraction is a challenging problem because tabular formats are not standardized across all documents. In this paper, we propose a simple but effective preprocessing method to improve the table boundary detection performance by considering the sparse-line property of table rows. Our method easily simplifies the table boundary detection problem into the sparse line analysis problem with much less noise. We design eight line label types and apply two machine learning techniques, Conditional Random Field (CRF) and Support Vector Machines (SVM), on the table boundary detection field. The experimental results not only compare the performances between the machine learning methods and the heuristics-based method, but also demonstrate the effectiveness of the sparse line analysis in the table boundary detection.

REFERENCES

• 1: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 2: H. Chao and J. Fan. Layout and content extraction for pdf documents. pages 213--224, 2004.
• 3: Hsin-Hsi Chen , Shih-Chung Tsai , Jin-He Tsai, Mining tables from large scale HTML texts, Proceedings of the 18th conference on Computational linguistics, p.166-172, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990845]
• 4: Jaekyu Ha , R. M. Haralick , I. T. Phillips, Recursive X-Y cut using bounding boxes of connected components, Proceedings of the Third International Conference on Document Analysis and Recognition (Volume 2), p.952, August 14-15, 1995
• 5: M. Hurst. Layout and language: Challenges for table understanding on the web, 2001.
• 6: N. G. J. Shin. Table recognition and evaluation. In In Proc. of the Class of 2005 Senior Conf., Computer Science Department, Swarthmore College, pages 8--13, 2005.
• 7: T. Joachims. Svm light. http://svmlight.joachims.org/.
• 8: Applying the T-Recs Table Recognition System to the Business Letter Domain, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.518, September 10-13, 2001
• 9: T. G. Kieninger. Table structure recognition based on robust block segmentation. In In Proc. Document Recognition V, SPIE, volume 3305, pages 22--32, January 1998.
• 10: Bernhard Krüpl , Marcus Herzog , Wolfgang Gatterbauer, Using visual cues for extraction of tabular data from arbitrary HTML documents, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062838]
• 11: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 12: Ying Liu , Kun Bai , Prasenjit Mitra , C. Lee Giles, TableSeer: automatic table metadata extraction and searching in digital libraries, Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries, June 18-23, 2007, Vancouver, BC, Canada [doi>10.1145/1255175.1255193]
• 13: Y. Liu, P. Mitra, and C. L. Giles. Improving the table boundary detection in pdfs by fixing the sequence error of the sparse lines. In Technical report, 2008.
• 14: A. McCallum. Efficiently inducing features of conditional random fields. In Nineteenth Conference on UAI, 2003.
• 15: A. McCallum and W. Li. Early results for named entity recognition with conditional random fields, 2003.
• 16: H. Ng, C. Lim, and J. Koo. Learning to recognize tables in free text, 1999.
• 17: Hwee Tou Ng , Chung Yong Lim , Jessica Li Teng Koo, Learning to recognize tables in free text, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.443-450, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034746]
• 18: G. Penn, J. Hu, H. Luo, and R. McDonald. Flexible web document analysis for delivery to narrow-bandwidth devices, 2001.
• 19: David Pinto , Andrew McCallum , Xing Wei , W. Bruce Croft, Table extraction using conditional random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860479]
• 20: S. Safavian and D. Landgrebe. A survey of decision tree classifier methodology. In SMC(21), No. 3, May 1991, pp. 660--674.
• 21: F. Sha and F. Pereira. Shallow parsing with conditional random fields, 2003.
• 22: John H. Shamilian , Henry S. Baird , Thomas L. Wood, A retargetable table reader, Proceedings of the 4th International Conference on Document Analysis and Recognition, p.158-163, August 18-20, 1997
• 23: Yalin Wang , Jianying Hu, A machine learning based approach for table detection on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511478]
• 24: Yalin Wang , Jianying Hu, Detecting Tables in HTML Documents, Proceedings of the 5th International Workshop on Document Analysis Systems V, p.249-260, August 19-21, 2002
• 25: Automatic Table Ground Truth Generation and a Background-Analysis-Based Table Structure Extraction Method, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.528, September 10-13, 2001
• 26: B. Yildiz, K. Kaiser, and S. Miksch. pdf2table: A >method to extract table information from pdf files. IICAI05, (Pune, India), 2005.
• 27: M. Yoshida, K. Torisawa, and J. Tsujii. A method to integrate tables of the world wide web, 2001.
• 28: Richard Zanibbi , Dorothea Blostein , R. Cordy, A survey of table recognition: Models, observations, transformations, and inferences, International Journal on Document Analysis and Recognition, v.7 n.1, p.1-16, March 2004 [doi>10.1007/s10032-004-0120-9]
• 29: Zijian Zheng, Naive Bayesian Classifier Committees, Proceedings of the 10th European Conference on Machine Learning, p.196-207, April 21-23, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries

General Terms:
Algorithms, Performance

Keywords:
conditional random field, sparse line property, support vector machine, table boundary detection, table data collection, table labeling