Method for graph-based table recognition

DETAILED DESCRIPTION The present invention is directed to a method for document structure recognition based on a graph rewriting paradigm.
Document recognition is a process by which the information regarding the organization of the document content, i.
e.
its structure, is extracted from the document image.
The structure identifies document entity types (e.
g.
paragraphs, figures and tables), their properties (e.
g.
the number of columns in a table), and their interrelations (e.
g.
, a figure is above a caption).
Although Optical Character recognition (OCR) is an inherent part of this process, it is not intended as an aspect of the present invention.
The present invention is directed to document structure recognition beyond a character level.
Indeed, the methodology presented here is equivalently applicable to any of a number of document types, including documents described by a Page Description Language (PDL) such as Postscript.
TM.
or Xerox Interpress.
TM.
.
Graphs are known to be powerful tools for document structure analysis.
They provide a compact computational abstraction for representing the complex multidimensional information embedded in a document structure.
In this abstraction, document entities and the inter-relations between these entities can be represented by elements of graphs, namely graph nodes and links respectively.
Manipulation of these nodes and links results in a change in the topology of the graph that consequently provides a new interpretation of the document structure.
As a result, the tools for graph manipulation become the basis for a computational document structure analysis framework.
The use of graphs for document recognition has classically been limited to academic and experimental systems due to the computational complexity of graph manipulation.
A notable exception is the work of Fahmy and Blostein "A Graph Grammar Programming Style for Recognition of Music Notation, " Machine Vision and Applications, Vol.
6 (1993).
This work provides a comprehensive computational framework for document recognition