Borderless table detection engine

1. A borderless table detection method for detecting a borderless table contained in data parsed from a fixed format document, said method comprising the steps of:

grouping whitespaces having vertical overlap with each other into a whitespace group having a top border and a bottom border;

collecting text located between a top border and a bottom border of said whitespace group as collected text;

creating column separators positioned at a right edge of each whitespace detected within a table candidate comprising said collected text and having an upper border, a lower border, a left border, and a right border, each said column separator defining a pair of endpoints;

creating a first set of row separators comprising a row separator located at selected said endpoints to form a plurality of individual cells;

creating a second set of row separators between successive lines of text in said table candidate based on a rendering order of the text obtained from the fixed format document when the rendering order of the text is available from the fixed format document;

discarding said row separator from said second set of row separators when the maximum vertical position or rendering order of the text of said collected text above said row separator is greater than the minimum vertical position or the rendering order of the text of said collected text below said row separator;

discarding a first said row separator from said first set of row separators when said first row separator is collinear with a second said row separator from said second set of row separators; and

assigning collected text to a corresponding one of said plurality of individual cells.

2. The borderless table detection method of claim 1 characterized in that each said whitespace detected within said table candidate has a height exceeding a threshold height corresponding to substantial portion of the height of said table candidate.

3. The borderless table detection method of claim 1 characterized in that said threshold height varies as a function of the height of the table candidate and the average height of said collected text.

4. The borderless table detection method of claim 1 characterized in that said step of creating a first set of row separators further comprises the steps of:

drawing a horizontal line extending to the left from said each said endpoint that does not lie on either said upper border or said lower border until said horizontal line meets another said column separator or said left border; and

drawing a horizontal line extending to the right from said each said endpoint that does not lie on either said upper border or said lower border until said horizontal line meets another said column separator or said right border.

5. The borderless table detection method of claim 1 further comprising the steps of:

calculating a text coverage percentage corresponding to the area of said table candidate covered by said collected text; and

discarding said table candidate if said text coverage percentage is less than a selected text coverage threshold.

6. The borderless table detection method of claim 1 , further comprising the steps of:

detecting bulleted and/or numbered lists within said table candidate; and

discarding said table candidate if said table candidate contains only a single said bulleted and/or numbered list.

7. The borderless table detection method of claim 1 characterized in that each row defined by said row separators has a first cell and a last cell, said method further comprising the step of discarding rows where said collected text is assigned to only said first cell or said last cell of that row.

8. The borderless table detection method of claim 1 further comprising the step of discarding tables containing only a single column.

9. A system for detecting a borderless table appearing in a fixed format document, said system comprising:

a hardware memory device that stores programmed instructions; and

a computing device that executes the stored programmed instructions, the execution of the stored programmed instructions causing the computing device to operate as a borderless table detection engine application operable to:

detect whitespaces on a page using a first minimum whitespace width threshold;

group said whitespaces having vertical overlap with each other into a whitespace group having a top border and a bottom border;

collect text located between a top border and a bottom border of said whitespace group as collected text;

create a bounding box around said collected text to form a table candidate, said bounding box having an upper border, a lower border, a left border, and a right border;

detect whitespaces within said table candidate using a second minimum whitespace width threshold, said second minimum whitespace width threshold being smaller than said first minimum whitespace width threshold;

create column separators positioned at a right edge of each said whitespace within said table candidate, each said column separator defining a pair of endpoints;

create a first set of row separators comprising a row separator located at each said endpoint that does not lie on either said upper border of said bounding box or said lower border of said bounding box to form a plurality of individual cells;

create a second set of row separators between successive lines of text in said table candidate based on a rendering of the text obtained from the fixed format document when the rendering order of the text is available from the fixed format of the document;

discard said row separator from said second set of row separators when the maximum vertical position or rendering order of the text of said collected text above above said row separator is greater than the minimum vertical position or the rendering order of said collected text below said row separator;

discard a first row separator form said first set of row separators when said first row separator is collinear with a second row separator from said second set of row separators; and

assign collected text to a corresponding one of said plurality of individual cells wherein each row defined by said row separators has a first cell and a last cell.

10. The system of claim 9 characterized in that said borderless table detection engine application is operable to create column separators from whitespaces detected within said table candidate that have a height exceeding a variable threshold height corresponding to substantial portion of the height of said table candidate and varying as a function of the height of the table candidate and the average height of said collected text.

11. The system of claim 9 characterized in that said borderless table detection engine application is operable to draw a horizontal line extending to each side of each said endpoint that does not lie on either said upper border of said bounding box or said lower border of said bounding box until said horizontal line meets another said column separator on each side of said endpoint.

12. The system of claim 9 characterized in that said borderless table detection engine application is operable to discard said table candidate if a text coverage percentage corresponding to the area of said table candidate covered by said collected text is less than a selected text coverage threshold.

13. The system of claim 9 further comprising the steps of creating row separators positioned a vertical position selected from the group consisting of each said endpoint that does not lie on either said upper border of said bounding box or said lower border of said bounding box and successive lines of text in said table candidate determined using rendering order information obtained from the fixed format document to form a cell layout containing a plurality of individual cells.

14. The system of claim 9 characterized in that said borderless table detection engine application is operable to discard rows where said collected text is assigned to only said first cell or said last cell of that row.

15. A computer readable hardware medium containing computer executable instructions which, when executed by a computer, perform a method to detect borderless tables when converting a fixed format document to a flow format document, said method comprising the steps of:

detecting whitespaces on a page using a first minimum whitespace width threshold;

grouping said whitespaces having vertical overlap with each other into a whitespace group having a top border and a bottom border;

collecting text located between a top border and a bottom border of said whitespace group as collected text;

creating a bounding box around said collected text to form a table candidate, said bounding box having an upper border, a lower border, a left border, and a right border;

detecting whitespaces within said table candidate using a second minimum whitespace width threshold, said second minimum whitespace width threshold being smaller than said first minimum whitespace width threshold;

creating column separators positioned at a right edge of each said whitespace within said table candidate, each said column separator defining a pair of endpoints;

creating a first set of row separators comprising drawing a horizontal line extending to the left from said each said endpoint that does not lie on either said upper border of said bounding box or said lower border of said bounding box until said horizontal line meets another said column separator or said left border and to the right from said each said endpoint that does not lie on either said upper border of said bounding box or said lower border of said bounding box until said horizontal line meets another said column separator or said right border to form a first set of row separators;

creating a second set of row separators between successive lines of text in said table candidate based on rendering order of the text obtained from the fixed format document when the rendering order of the text is available from the fixed format document;

discarding said row separator from said second set of row separators when the maximum vertical position or rendering order of the text of said collected text above said row separator is greater than the minimum vertical position or rendering order of the text of said collected text below said row separator;

discarding a first said row separator from said first set of row separators when said first row separator is collinear with a second said row separator from said second set of row separators; and

assigning collected text to a corresponding one of said plurality of individual cells wherein each row defined by said row separators has a first cell and a last cell.

16. The computer readable hardware medium of claim 15 characterized in that said method further comprises the step of discarding said table candidate if a text coverage percentage corresponding to the area of said table candidate covered by said collected text is less than a selected text coverage threshold.

17. The computer readable hardware medium of claim 15 characterized in that said method further comprises the step of discarding rows where said collected text is assigned to only said first cell or said last cell of that row.