# US 2021/0240932 A1 · Data extraction and ordering based on document layout analysis

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

- Number: US 2021/0240932 A1
- Document ID: US20210240932A1
- Status: Published application
- Kind: A1
- Application number: 16/776,721
- Filed: 2020-01-30
- Published: 2021-08-05
- Earliest claimed: 2020-01-30
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Erhan Erdemir; Kenneth James Peterka
- Web page: https://patentgrep.com/patent/US20210240932A1

## CPC

- G06F 40/289: Phrasal analysis, e.g. finite state techniques or chunking
- G06V 30/413: Classification of content, e.g. text, photographs or tables
- G06V 30/414: Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
- G06V 30/416: Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors
- G06V 30/10: Character recognition
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

The embodiments disclosed herein relate to identifying phrases in an electronic document, where each token is one or more characters. Phrases are formed from the tokens, based on a position of each token relative to other tokens in the document. If the horizontal space between two tokens is less than a threshold, the two tokens are identified as a phrase. Information identifying phrases and tokens can be stored in a marked-up document. Value phrases can be identified by the content of the phrase. Thereafter, a label phrase can be identified based on proximity to the value phrase and/or the presence of an association symbol in the phrase. The label phrase and value phrase can be identified as a label-value pair, where the label identifies the type of content in the value phrase. A reading order of the document can be determined through the use of a binary tree.

## Claims

### Claim 1

One or more non-transitory computer readable media comprising instructions which, when executed by one or more hardware processors, causes performance of operations comprising:
identifying a plurality of phrases in an electronic document;
identifying a first phrase, of the plurality of phrases, that comprises a digit;
determining that a second phrase, of the plurality of phrases, (a) does not include any digit and (b) is within a threshold distance of the first phrase;
responsive at least to determining (a) and (b), assigning both the first phrase and the second phrase to a same group in a plurality of groups;
storing or presenting information identifying members of each group of the plurality of groups.

### Claim 2 (depends on 1)

The media of claim 1, wherein the assigning operation is further responsive to determining that the second phrase ends in an association symbol.

### Claim 3 (depends on 2)

The media of claim 2, wherein the association symbol comprises a colon.

### Claim 4 (depends on 1)

The media of claim 1, wherein the assigning operation is further responsive to determining that the second phrase is one of:
a left-neighbor of the first phrase such that the first phrase and second phrase (a) include overlapping ranges of corresponding vertical positions in the electronic document and (b) the second phrase's horizontal position is to the left of the first phrase's horizontal position in the electronic document;
an above-neighbor of the first phrase such that the first phrase and second phrase include overlapping ranges of corresponding horizontal positions in the electronic document.

### Claim 5 (depends on 4)

The medium of claim 4, wherein determining that the second phrase is a left-neighbor of the first phrase comprises:
determining an absolute height difference between a (a) first height corresponding to a tallest character in the first phrase and (b) a second height corresponding to a tallest character in the second phrase;
dividing the absolute height difference by a lowest value of the first height and the second height to compute a normalized height;
determining that the normalized height is less than a threshold value.

### Claim 6 (depends on 4)

The medium of claim 4, wherein the assigning operation is further responsive to determining that the second phrase is a closest phrase of a pair of phrases neighboring the first phrase as a left-neighbor and an above-neighbor.

### Claim 7 (depends on 4)

The medium of claim 4, wherein the assigning operation is further response to determining that the second phrase is an only phrase of a pair of phrases, neighboring the first phrase as a left-neighbor and an above-neighbor, that comprises an association symbol.

### Claim 8 (depends on 1)

The medium of claim 1, wherein the assigning operation is further responsive to determining that no other phrases are located between the first phrase and the second phrase in the electronic document.

### Claim 9 (depends on 1)

The medium of claim 1, wherein the further operations further comprise:
responsive to determining that horizontal spacing between a pair of tokens is less than a threshold value: assigning both tokens in the pair of tokens to a same third phrase.

### Claim 10 (depends on 9)

The medium of claim 9, wherein the threshold value is computed by multiplying the average character width of characters in the third phrase with a horizontal tolerance factor.

### Claim 11 (depends on 1)

The medium of claim 1, wherein storing or presenting the information identifying members of each group of the plurality of groups comprises:
determining an order for the groups in the plurality of groups;
storing or presenting the groups, in the plurality of groups, based on the order determined for the groups.

### Claim 12 (depends on 11)

The medium of claim 11, wherein determining the order for the groups in the plurality of groups is based at least on distances between pairs of groups in the plurality of groups.

### Claim 13 (depends on 12)

The medium of claim 12, wherein the distances between pairs of groups comprise a Cartesian distance between closest corners of respective bounding boxes corresponding to the groups in the pairs of groups.

### Claim 14 (depends on 11)

The medium of claim 11, wherein the operations further comprise:
creating a binary tree by recursively grouping the plurality of groups until each group of the plurality of groups are grouped into a same group corresponding to a root node of the binary tree:
determining a Cartesian distance between each pair of groups of the plurality of groups to determine a set of Cartesian distances;
assigning phrase groups to nodes of the binary tree at least by:
identifying a particular pair of phrase groups, of the pairs of phrase groups, with a smallest Cartesian distance of the set of Cartesian distances;
assigning each phrase group in the particular pair of phrase groups to a respective child node of a same parent node;
grouping each phrase group in the particular pair of phrase groups into a same phrase group for the recursive grouping of the plurality of groups.

### Claim 15 (depends on 14)

The medium of claim 14, wherein the operations further comprise:
traversing the binary tree to determine the order for the groups in the plurality of groups.

### Claim 16 (depends on 15)

The medium of claim 15, wherein the operations further comprise:
selecting a current node based on the current node being associated with a group, of the subset of groups, with a highest vertical position;
traversing the binary tree from the current node at least by:
responsive to determining that the current node has children nodes:
identify vertical positions of a subset of groups, of the plurality of groups, corresponding to any indirect or direct children nodes of the current node;
responsive to determining that the current node does not have any children node:
(a) adding the current node to an ordered list of groups in the plurality of groups;
(b) adding any sibling node of the current node to the ordered list of groups in the plurality of groups subsequent to ordered list of groups subsequent to the current node, wherein the sibling node of the current node is a node that shares a same parent as the current node;
(c) select a sibling node of the current node's parent node as the current node and repeat the traversing operation.

### Claim 17 (depends on 1)

The medium of claim 1, wherein the threshold distance is based on an average character height of characters in the first phrase.

### Claim 18 (depends on 1)

The medium of claim 1, wherein identifying a third phrase, of the plurality of phrases, comprises:
detecting an indication of currency in the electronic document;
identifying a numerical value closest to the indication of currency;
assigning the indication of currency and the numerical value closest to the indication of currency symbol to the same third phrase.

### Claim 19 (depends on 1)

The medium of claim 1, wherein storing the groups comprises writing information describing the groups in a second document formatted using a markup language.

### Claim 20

A method comprising:
identifying a plurality of phrases in an electronic document, wherein text corresponding to each phrase, in the plurality of phrases, are on a same text line in the first electronic document;
identifying a first phrase, of the plurality of phrases, that comprises a digit;
determining that a second phrase, of the plurality of phrases, (a) does not include any digit and (b) is within a threshold distance of the first phrase;
responsive at least to determining (a) and (b), assigning both the first phrase and the second phrase to a same group in a plurality of groups;
storing information identifying members of each group of the plurality of groups;
determining an order for the groups in the plurality of groups;
storing or presenting the groups, in the plurality of groups, based on the order determined for the groups,
wherein the method is executed by at least one device including a hardware processor.

### Claim 21

A system comprising:
at least one device including a hardware processor;
the system being configured to perform operations comprising:
identifying a plurality of phrases in an electronic document, wherein text corresponding to each phrase, in the plurality of phrases, are on a same text line in the first electronic document;
identifying a first phrase, of the plurality of phrases, that comprises a digit;
determining that a second phrase, of the plurality of phrases, (a) does not include any digit and (b) is within a threshold distance of the first phrase;
responsive at least to determining (a) and (b), assigning both the first phrase and the second phrase to a same group in a plurality of groups;
storing information identifying members of each group of the plurality of groups;
determining an order for the groups in the plurality of groups;
storing or presenting the groups, in the plurality of groups, based on the order determined for the groups.