Analyzing lines to detect tables in documents

• US 7,707,488 B2
• Filed: 02/09/2006
• Issued: 04/27/2010
• Est. Priority Date: 02/09/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Foehr, Oliver H., Lopez, Rodrigo, Sedky, Khaled S., Liu, Ming, Dunietz, Jerry J., Leese, Eric S., Gurcan, Ahmet, Brown, Jeffrey G., McGatha, Jesse D.
• Primary Examiner(s): Basehoar; Adam L
• Assistant Examiner(s): PATTERSON, YASIN K
• Application Number:
  US11/350,614
• Publication Number:
  US 20070186152A1
• Time in Patent Office: 1,538 Days
• Field of Search: 382/180, 715/227, 715/228
• US Class Current: 715/227
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191

Abstract

Various technologies and techniques detect tables in vector graphics based documents and use them in meaningful ways. The system detects at least one table in a vector graphics based document using a set of rules. The rules include analyzing a set of content representing horizontal and vertical lines to find intersections and identifying table cells based on the intersections. Once identified, the table content is translated into a modified format. The content can be output to a destination application in the modified format that is more suitable for output or use by the destination application.

Claims

1. A method for recognizing tables in vector graphics based documents comprising:

receiving a document in an original format, the original format having at least a set of table rendering instructions for at least one table in the document;

parsing the document to determine that the document comprises at least one table and at least one nested table and to identify a set of contents for the table; and

outputting the table and the nested table to an output medium, the output medium presenting the table in a modified format, where determining that the document comprises at least one nested table comprises;

analyzing a first cell of the table to determine whether the first cell comprises lines therein that do not intersect borders of the first cell, and

upon analyzing the first cell and finding a first nested cell, utilizing the first nested cell as a reference and determining if a second nested cell occurs adjacent to or below the first nested cell.

3. The method of claim 1, wherein the output medium comprises a screen reader, and wherein a set of contents in the table are described audibly to a user.

4. The method of claim 1, comprising regarding double lines as a single line and not regarding spacing between the double lines as a cell.

5. The method of claim 1, wherein the document comprises an XML paper specification format.

6. The method of claim 1, wherein parsing the document comprises:

analyzing a set of text representing a plurality of horizontal and vertical lines to find intersections, and identifying a plurality of table cells based on the intersections.

8. The method of claim 1, wherein receiving the document is performed when receiving an input to copy a section of content to a destination application;

wherein the receiving and parsing are performed by a source application;

wherein the modified format is created by the source application and transmitted to the destination application for outputting to the output medium; and

wherein the modified format comprises a format used by the destination application.

9. A computer-readable storage medium having computer-executable instructions for causing a computer to perform the steps recited in claim 1.

2. A method for recognizing tables in vector graphics based documents comprising:

receiving a document in an original format, the original format having at least a set of table rendering instructions for at least one table in the document;

parsing the document to determine that the document comprises at least one table and at least one nested table and to identify a set of contents for the table; and

upon determining that the document comprises at least one table, determining that the table does not comprise a false positive, comprising;

verifying that the table comprises a first cell and a second cell;

confirming that the table comprises text;

checking that column edges of the table align; and

checking that rows of the table share top and bottom edges.

7. A method for recognizing tables in vector graphics based documents comprising:

receiving a document in an original format, the original format having at least a set of table rendering instructions for at least one table in the document; and

parsing the document to determine that the document comprises at least one table and at least one nested table and to identify a set of contents for the table, where parsing the document comprises;

grouping a plurality of horizontal lines together, grouping a plurality of vertical lines together, looking for intersections that are present between the horizontal lines and the vertical lines, and identifying a plurality of table cells based on the intersections and where identifying a plurality of table cells comprises;

determining whether intersecting horizontal and vertical lines form a first table cell; and

using the first table cell as a reference cell to determine if a same pattern occurs adjacent to the first table cell or below the first table cell.

10. A computer-readable storage medium having computer-executable instructions for causing a computer to perform a method comprising:

detecting at least one table within a vector graphics based document using a set of rules, the rules comprising;

analyzing a set of content representing at least one horizontal and vertical line to find intersections; and

identifying a plurality of table cells based on the intersections;

determining that the document comprises at least one nested table comprising;

analyzing a first cell of the table to determine whether the first cell comprises lines therein that do not intersect borders of the first cell, and

upon analyzing the first cell and finding a first nested cell, utilizing the first nested cell as a reference and determining if a second nested cell occurs adjacent to or below the first nested cell;

translating the at least one table to a modified format; and

outputting the modified format to an output medium.

11. The computer-readable storage medium of claim 10, wherein the document comprises an XML document.

12. The computer-readable storage medium of claim 10, wherein the document comprises an XML paper specification format.

13. The computer-readable storage medium of claim 10, wherein the output medium is selected from a group comprising a display device, a file, a screen reader, and a separate application.

14. The computer-readable storage medium of claim 10, wherein the output medium comprises a screen reader, and wherein a set of table contents are described audibly to a user.

15. A method for interpreting vector graphics based documents comprising the steps of:

receiving an input from a user to copy a section of content, the content having an original format that includes a set of table rendering instructions;

interpreting the table rendering instructions to detect that the document comprises at least one table;

upon determining that the document comprises at least one table, determining that the table does not comprise a false positive, comprising;

verifying that the table comprises a first cell and a second cell;

confirming that the table comprises text;

checking that column edges of the table align and checking that rows of the table share top and bottom edges;

translating the content including the at least one table into a modified format; and

providing the content in the modified format to the destination application for output.

16. The method of claim 15, wherein the section of content is selected from a document comprising an XML based format.

17. A computer-readable storage medium having computer-executable instructions for causing a computer to perform the steps recited in claim 15.