Cell identification in table analysis

• US 6,006,240 A
• Filed: 03/31/1997
• Issued: 12/21/1999
• Est. Priority Date: 03/31/1997
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Handley, John C.
• Primary Examiner(s): Fetting, Anton W.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/828,847
• Time in Patent Office: 995 Days
• Field of Search: 707/510, 707/504, 707/503, 707/509, 707/500, 382/173
• US Class Current: 715/220
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables

Abstract

The present invention handles fully-lined, semi-lined and line-less cell tables by identifying the cells and cell separators during page recomposition processes as part of optical character recognition processes. The invention accomplishes such by iteratively identifying cell separators and cells. The processes accomplishes this by iteratively merging word boxes into cells, iteratively finding separators, and iteratively merging cells bounded by the same separators, and repeating these steps until the correct cell structure is found. With this method, rows are estimated, close words are merged into cells, columns are then estimated, cells within columns are merged, columns re-estimated, cells in the same row and column are merged into bigger cells, and then rows and cells are merged according to the detection of various table styles. This invention handles large complex tables with multiple lines of symbols per cell. This method handles multiple line cells in lined, semi-lined and line-less tables.

Claims

1. A method of identifying, during page recomposition, cells in a table scanned by optical character scanning means as part of an optical character recognition process, comprising the steps of:

segmenting said table into tabular region of rows and columns of individual cells;

merging individual cells which share the same row and column;

determining a plurality of vertical and horizontal rulings;

combining adjacent vertical and horizontal rulings to form vertical and horizontal frames;

merging cells which share the same horizontal and vertical frame expanding cells to fit within the nearest vertical and horizontal frame; and

returning said table to the page recomposition process.

2. A method as defined in claim 1, wherein said step of combining vertical rulings further comprises the step of combining vertical rulings which are within 4.5 mm horizontally and which overlap vertically to form vertical frames.

3. A method as defined in claim 1 wherein said step of combining horizontal rulings further comprises the step of combining horizontal rulings which are within 1.5 mm vertically and which overlap horizontally to form horizontal frames.

4. A method as defined in claim 1 wherein said step of determining vertical rulings comprises the step of determining midpoints of the gaps between said columns to form the vertical rulings.

5. A method as defined in claim 1 wherein said step of determining horizontal rulings comprises the step of determining midpoints of gaps between said rows to form the horizontal rulings.

6. A method of identifying, during page recomposition, cells in a table scanned by optical character scanning means as part of an optical character recognition process, comprising the steps of:

segmenting said table into tabular region of rows and columns of individual cells of words;

merging cells of individual words which share the same row and column;

determining midpoints of gaps between said columns to form vertical rulings;

determining midpoints of gaps between said rows to form horizontal rulings;

combining vertical rulings which are within 4.5 mm horizontally and which overlap vertically to form vertical frames;

combining horizontal rulings which are within 1.5 mm vertically and which overlap horizontally to form horizontal frames;

merging cells which share the same horizontal and vertical frame expanding cells to fit within the nearest vertical and horizontal frame; and

returning said table to the page recomposition process.

7. A method as defined in claim 6 wherein said cell comprises a data structure consisting of a pointer to a linked list of individual cell'"'"'s, frame coordinates, and coordinates of said cell'"'"'s column and row location in said tabular region.

8. A method as defined in claim 6 wherein a skew correction is applied to said merged cells using a skew estimate to determine a y-offset for each y-coordinate to correct its skew.

9. A method as defined in claim 6 wherein cells are deemed to be in the same column by determining if midpoints of two cells are both within the same column.