# US 2020/0401798 A1 · Data structure generation for tabular information in scanned images

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0401798 A1
- Document ID: US20200401798A1
- Status: Published application
- Kind: A1
- Application number: 16/450,078
- Filed: 2019-06-24
- Published: 2020-12-24
- Earliest claimed: 2019-06-24
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Antonio Foncubierta Rodriguez; Maria Gabrani; Waleed Farrukh
- Web page: https://patentgrep.com/patent/US20200401798A1

## CPC

- G06F 16/51: Indexing; Data structures therefor; Storage structures
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/583: using metadata automatically derived from the content
- G06F 40/137: Hierarchical processing, e.g. outlines
- G06F 40/18: of spreadsheets (form-filling G06F40/174)
- G06F 40/258: Heading extraction; Automatic titling; Numbering
- G06N 5/025: Extracting rules from data
- G06N 20/20: Ensemble learning
- G06T 7/70: Determining position or orientation of objects or cameras (camera calibration G06T7/80)
- G06V 30/412: Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables
- G06V 30/413: Classification of content, e.g. text, photographs or tables
- G06F 16/9027: {Trees}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06T 2207/20072: Graph-based image processing
- G06T 2207/20081: Training; Learning
- G06T 2207/30176: Document
- G06V 10/426: Graphical representations
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

Computer-implemented methods are provided for generating a data structure representing tabular information in a scanned image. Such a method can include storing image data representing a scanned image of a table, processing the image data to identify positions of characters and lines in the image, and mapping locations in the image of information cells, each containing a set of the characters, in dependence on said positions. The method can also include, for each cell, determining cell attribute values, dependent on the cell locations, for a predefined set of cell attributes, and supplying the attribute values as inputs to a machine-learning model trained to pre-classify cells as header cells or data cells in dependence on cell attribute values.

## Claims

### Claim 1

A computer-implemented method for generating a data structure representing tabular information in a scanned image, the method comprising:
storing image data representing a scanned image of a table;
processing the image data to identify positions of characters and lines in the image;
mapping locations in the image of information cells, each containing a set of said characters, in dependence on said positions;
for each cell, determining cell attribute values, dependent on said locations, for a predefined set of cell attributes and supplying the attribute values as inputs to a machine-learning model trained to pre-classify cells as header cells or data cells in dependence on cell attribute values;
applying predefined rules to the pre-classified cells to identify a corner data cell marking a transition between a region containing data cells and edge regions containing header cells in the image, and defining row and column header cells in dependence on location of cells in said edge regions;
for each of the set of row header cells and the set of column header cells, defining a hierarchy tree, indicating hierarchical structure of the header cells, in dependence on relative locations of those cells in the image;
using the hierarchy trees to generate a data structure mapping each data cell to corresponding row and column header cells in said hierarchical structure; and
storing the data structure to provide a queryable representation of said table.

### Claim 2 (depends on 1)

A method as claimed in claim 1 including, in response to receipt, after storing said data structure, of a request for information in said table:
extracting data corresponding to the requested information from the data structure; and
outputting the extracted data.

### Claim 3 (depends on 1)

A method as claimed in claim 1 wherein:
said rules are defined, over predicates relating to cells, by a Markov logic network with pre-trained rule weights indicating importance of respective rules for identification of a corner data cell; and
the step of applying said rules comprises applying the Markov logic network to the pre-classified cells to identify said corner data cell.

### Claim 4 (depends on 1)

A method as claimed in claim 1 including, for at least one of the sets of row and column header cells, defining said hierarchy tree by:
generating a weighted graph comprising nodes which represent the header cells, their neighboring data cells and a predefined root cell in the image, the node for each cell being interconnected by edges to at least a set of said nodes representing neighboring cells in the image, wherein the edge between each pair of nodes has a weight dependent on relative position in the image of the cells represented by those nodes; and
selecting an optimal path, dependent on said weights, between each node representing a data cell and the node representing said root cell to define branches of the hierarchy tree.

### Claim 5 (depends on 4)

A method as claimed in claim 4 including:
defining a Voronoi diagram for locations in the image of the header cells, said neighboring data cells and said root cell; and
generating the weighted graph with edges determined by paths in the Voronoi diagram between each data cell location and the root cell location.

### Claim 6 (depends on 1)

A method as claimed in claim 1 including, for at least one of the sets of row and column header cells:
determining if each cell has any of a predetermined set of format properties; and
if the set of header cells includes cells with differing format properties, defining said hierarchy tree in dependence on the format properties of the cells.

### Claim 7 (depends on 6)

A method as claimed in claim 6 wherein said set of format properties comprises at least one of bold text, italic text, indented text and upper-case text.

### Claim 8 (depends on 1)

A method as claimed in claim 1 wherein said predefined set of cell attributes comprises a plurality of attributes selected from: number of neighboring cells; number of neighboring cells to the right; number of neighboring cells above; having a line on the right; having a line on the left; having a line above; having a line below; and the area occupied by the cell.

### Claim 9 (depends on 8)

A method as claimed in claim 8 wherein said set of cell attributes includes a subset of attributes, dependent on character strings in cells, selected from: characters are bold; characters are italic; proportion of numeric characters; proportion of alphabetic characters; and proportion of non-alphanumeric characters.

### Claim 10 (depends on 1)

A method as claimed in claim 1 wherein said machine-learning model comprises a Random Forest model.

### Claim 11 (depends on 1)

A method as claimed in claim 1 wherein, in the step of mapping location of information cells, each information cell contains a set of horizontally-aligned characters in the image.

### Claim 12

A computer program product for generating a data structure representing tabular information in a scanned image, said computer program product comprising a computer readable storage medium having program instructions embodied therein, the program instructions being executable by a computing apparatus to cause the computing apparatus to:
store image data representing a scanned image of a table;
process the image data to identify positions of characters and lines in the image;
map locations in the image of information cells, each containing a set of said characters, in dependence on said positions;
for each cell, determine cell attribute values, dependent on said locations, for a predefined set of cell attributes and supply the attribute values as inputs to a machine-learning model trained to pre-classify cells as header cells or data cells in dependence on cell attribute values;
apply predefined rules to the pre-classified cells to identify a corner data cell marking a transition between a region containing data cells and edge regions containing header cells in the image, and define row and column header cells in dependence on location of cells in said edge regions;
for each of the set of row header cells and the set of column header cells, define a hierarchy tree, indicating hierarchical structure of the header cells, in dependence on relative locations of those cells in the image;
use the hierarchy trees to generate a data structure mapping each data cell to corresponding row and column header cells in said hierarchical structure; and
store the data structure to provide a queryable representation of said table.

### Claim 13 (depends on 12)

A computer program product as claimed in claim 12, said program instructions being further executable, in response to receipt, after storing said data structure, of a request for information in said table, to cause the computing apparatus to:
extract data corresponding to the requested information from the data structure; and
output the extracted data.

### Claim 14 (depends on 12)

A computer program product as claimed in claim 12, said program instructions being executable such that:
said rules are defined, over predicates relating to cells, by a Markov logic network with pre-trained rule weights indicating importance of respective rules for identification of a corner data cell; and
the step of applying said rules comprises applying the Markov logic network to the pre-classified cells to identify said corner data cell.

### Claim 15 (depends on 12)

A computer program product as claimed in claim 12, said program instructions being executable to cause the computing apparatus to define said hierarchy tree, for at least one of the sets of row and column header cells, by:
generating a weighted graph comprising nodes which represent the header cells, their neighboring data cells and a predefined root cell in the image, the node for each cell being interconnected by edges to at least a set of said nodes representing neighboring cells in the image, wherein the edge between each pair of nodes has a weight dependent on relative position in the image of the cells represented by those nodes; and
selecting an optimal path, dependent on said weights, between each node representing a data cell and the node representing said root cell to define branches of the hierarchy tree.

### Claim 16 (depends on 15)

A computer program product as claimed in claim 15, said program instructions being executable to cause the computing apparatus to:
define a Voronoi diagram for locations in the image of the header cells, said neighboring data cells and said root cell; and
generate the weighted graph with edges determined by paths in the Voronoi diagram between each data cell location and the root cell location.

### Claim 17 (depends on 12)

A computer program product as claimed in claim 12, said program instructions being executable to cause the computing apparatus to define said hierarchy tree, for at least one of the sets of row and column header cells, by:
determining if each cell has any of a predetermined set of format properties; and
if the set of header cells includes cells with differing format properties, defining said hierarchy tree in dependence on the format properties of the cells.

### Claim 18 (depends on 12)

A computer program product as claimed in claim 12, said program instructions being executable such that:
said predefined set of cell attributes comprises a plurality of attributes selected from: number of neighboring cells; number of neighboring cells to the right; number of neighboring cells above; having a line on the right; having a line on the left; having a line above; having a line below; and the area occupied by the cell; and
the set of cell attributes includes a subset of attributes, dependent on character strings in cells, selected from: characters are bold; characters are italic; proportion of numeric characters; proportion of alphabetic characters; and proportion of non-alphanumeric characters.

### Claim 19 (depends on 12)

A computer program product as claimed in claim 12, said program instructions being executable such that said machine-learning model comprises a Random Forest model.

### Claim 20

Apparatus for generating a data structure representing tabular information in a scanned image, the apparatus comprising:
memory for storing image data representing a scanned image of a table;
image processing logic adapted to process the image data to identify positions of characters and lines in the image;
cell-detection logic adapted to map locations in the image of information cells, each containing a set of said characters, in dependence on said positions;
cell pre-classification logic adapted, for each cell, to determine cell attribute values, dependent on said locations, for a predefined set of cell attributes and to supply the attribute values as inputs to a machine-learning model trained to pre-classify cells as header cells or data cells in dependence on cell attribute values;
cell analysis logic adapted to apply predefined rules to the pre-classified cells to identify a corner data cell marking a transition between a region containing data cells and edge regions containing header cells in the image, and to define row and column header cells in dependence on location of cells in said edge regions;
hierarchy extraction logic adapted, for each of the set of row header cells and the set of column header cells, to define a hierarchy tree, indicating hierarchical structure of the header cells, in dependence on relative locations of those cells in the image;
data mapping logic adapted to use the hierarchy trees to generate a data structure mapping each data cell to corresponding row and column header cells in said hierarchical structure, and to store the data structure in said memory to provide a queryable representation of said table.