# US 2015/0178256 A1 · Method and system for page construct detection based on sequential regularities

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

- Number: US 2015/0178256 A1
- Document ID: US20150178256A1
- Status: Published application
- Kind: A1
- Application number: 14/140,075
- Filed: 2013-12-24
- Published: 2015-06-25
- Earliest claimed: 2013-12-24
- Assignees: Xerox Corporation
- Applicants: Xerox Corporation
- Inventors: Harvé Déjean
- Web page: https://patentgrep.com/patent/US20150178256A1

## CPC

- G06F 40/114: Pagination
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed is a method and system that generates a page construct structure associated with a sequentially-ordered set of pages, each being characterized by a set of page construct features. N-grams, i.e., a sequence of n features, are computed from a set of page construct features for n contiguous pages, and n-grams which are repetitive are selected. Pages matching the most frequent repetitive n-ram are grouped together under a new node, and a new sequence is created. The method is iteratively applied to this new sequence. The output is an ordered set of trees.

## Claims

### Claim 1

A computer implemented method of generating a page construct sequential hierarchical structure associated with a sequence of pages associated with a digital version of a document comprising:
a) obtaining a sequence of pages representing the document;
b) defining a set of page construct features associated with each page of the sequence of pages, each page construct feature defined as a document element which recurrently occurs at regular positions outside a running content of the sequence of pages, the construct feature defined by a feature value types;
c) computing a set of feature values associated with the set of page construct features for each page of the sequence;
d) generating a set of n-grams from the sequence of pages, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages;
e) electing sequential n-grams from the set of n-grams, the sequential n-grams defined as similar contiguous n-grams;
f) selecting the most frequent sequential n-gram from the elected sequential n-grams; and
g) generating a new sequence of the pages by matching the selected most frequent sequential n-gram against the sequence of pages associated with the document, replacing matched pages of the sequence of pages with a respective node, and associating the matched pages of the sequence of pages as children of the respective node, the new sequence of pages representing the page construct hierarchical sequential structure associated with the document.

### Claim 2 (depends on 1)

The computer implemented method according to claim 1, further comprising:
h) iteratively repeating steps d)-g) on the new sequence of pages generated in step g) until all sequential n-grams associated with the sequence of pages are matched against the sequence of pages associated with the document, the respective matched pages of the sequence of pages are replaced with a respective node, and the respective matched pages of the sequence of pages are associated as children of the respective node.

### Claim 3 (depends on 1)

The computer implemented method according to claim 1, wherein steps d)-g) are iteratively repeated for the new sequence of the pages as long as step f) can select a most frequent sequential n-gram from the elected sequential n-g rams.

### Claim 4 (depends on 2)

The computer implemented method according to claim 2, wherein step d) comprises:
d1) calibrating the set of page construct feature values for each page of the sequence by assigning equal feature values to page features which are fuzzily equal; and
d2) generating a set of n-grams from the sequence of pages and calibrated set of page construct feature values, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages.

### Claim 5 (depends on 1)

The computer implemented method according to claim 1, wherein fuzzily equal page construct feature values are associated with feature values which are within a pre-determined range of value differences and a most frequent feature value is considered a canonical feature value for the page construct features which are fuzzily equal.

### Claim 6 (depends on 1)

The computer implemented method according to claim 1, wherein step g) comprises:
g1) matching the selected most frequent sequential n-gram against the sequence of pages to determine all sub-sequences of n contiguous page constructs which are matched by the selected n-gram;
g2) enriching the determined sub-sequences by generating n-grams for each sub-sequence; and
g3) generating a new sequence of page constructs by replacing each sub-sequence of contiguous matched page constructs with a respective node and associating the matched page constructs of the sequence of page constructs as children of the respective node.

### Claim 7 (depends on 1)

The computer implemented method according to claim 1,
step d) comprising:
d1) calibrating the set of page construct feature values for each page of the sequence by assigning equal feature values to page construct features which are fuzzily equal; and
d2) generating a set of n-grams from the sequence of page constructs and calibrated set of page construct feature values, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages;
step g) comprising:
g1) matching the selected most frequent sequential n-gram against the sequence of pages to determine all sub-sequences of n contiguous pages which are matched by the selected n-gram;
g2) enriching the determined sub-sequences by generating n-grams for each sub-sequence; and
g3) generating a new sequence of pages by replacing each sub-sequence of contiguous matched elements with a respective node and associating the matched pages of the sequence of pages as children of the respective node; and
h) iteratively repeating steps d)-g) on the new sequence of pages generated in step g) until all sequential n-grams associated with the sequence of pages are matched against the sequence of pages associated with the document, the respective matched pages of the sequence of pages are replaced with a respective node, and the respective matched pages of the sequence of pages are associated as children of the respective node.

### Claim 8 (depends on 1)

The computer implemented method according to claim 1, wherein the page construct features include a position of one or more of a left margin, a right margin, a top margin, a bottom margin, a header and a footer.

### Claim 9 (depends on 1)

The computer implemented method according to claim 1, further comprising:
h) generating a page construct object associated with each page, the page construct fields representing one or more of position, width, left margin, right margin, height, top margin and bottom margin.

### Claim 10 (depends on 9)

The computer implemented method according to claim 9, further comprising:
i) performing steps d)-g), wherein the page construct features are the page construct objects generated in step h).

### Claim 11 (depends on 1)

The computer implemented method according to claim 1, further comprising:
associating with each page of the document a coordinate system.

### Claim 12 (depends on 1)

The computer method according to claim 1, further comprising:
h) generating a page construct object associated with each page, the page construct fields representing one or more of position, width, left margin, right margin, height, top margin and bottom margin; and
associating with each page of the document a coordinate system.

### Claim 13

An image processing system comprising:
a controller configured to receive a digital version of a document, the controller configured to execute instructions to perform a method of generating a page construct hierarchical sequential structure associated with a digital version of the document comprising:
a) obtaining a sequence of pages representing the document;
b) defining a set of page construct features associated with each page of the sequence of pages, each page construct feature defined as a document element which recurrently occurs at regular positions outside a running content of the sequence of pages, the construct feature defined by a feature value types;
c) computing a set of feature values associated with the set of page construct features for each page of the sequence;
d) generating a set of n-grams from the sequence of pages, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages;
e) electing sequential n-grams from the set of n-grams, the sequential n-grams defined as similar contiguous n-grams;
f) selecting the most frequent sequential n-gram from the elected sequential n-grams; and
g) generating a new sequence of the pages by matching the selected most frequent sequential n-gram against the sequence of pages associated with the document, replacing matched pages of the sequence of pages with a respective node, and associating the matched pages of the sequence of pages as children of the respective node, the new sequence of pages representing the page construct hierarchical sequential structure associated with the document.

### Claim 14 (depends on 13)

The image processing system according to claim 13, the controller configured to execute instructions to perform the method further comprising:
h) iteratively repeating steps d)-g) on the new sequence of pages generated in step g) until all sequential n-grams associated with the sequence of pages are matched against the sequence of pages associated with the document, the respective matched pages of the sequence of pages are replaced with a respective node, and the respective matched pages of the sequence of pages are associated as children of the respective node.

### Claim 15 (depends on 14)

The image processing system according to claim 14, wherein step d) comprises:
d1) calibrating the set of page construct feature values for each page of the sequence by assigning equal feature values to page construct features which are fuzzily equal; and
d2) generating a set of n-grams from the sequence of pages and calibrated set of page construct feature values, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages.

### Claim 16 (depends on 13)

The image processing system according to claim 13,
step d) comprising:
d1) calibrating the set of page construct feature values for each page of the sequence by assigning equal feature values to page construct features which are fuzzily equal; and
d2) generating a set of n-grams from the sequence of pages and calibrated set of page construct feature values, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages;
step g) comprising:
g1) matching the selected most frequent sequential n-gram against the sequence of pages to determine all sub-sequences of n contiguous pages which are matched by the selected n-gram;
g2) enriching the determined sub-sequences by generating n-grams for each sub-sequence; and
g3) generating a new sequence of pages by replacing each sub-sequence of contiguous matched pages with a respective node and associating the matched pages of the sequence of pages as children of the respective node; and
h) iteratively repeating steps d)-g) on the new sequence of pages generated in step g) until all sequential n-grams associated with the sequence of pages are matched against the sequence of pages associated with the document, the respective matched pages of the sequence of pages replaced with a respective node and the respective matched pages of the sequence of pages associated as children of the respective node.

### Claim 17 (depends on 13)

The image processing system according to claim 13, wherein the page construct features include a position of one or more of a left margin, a right margin, a top margin, a bottom margin, a header and a footer.

### Claim 18 (depends on 13)

The image processing system according to claim 13, further comprising:
h) generating a page construct object associated with each page, the page construct fields representing one or more of position, width, left margin, right margin, height, top margin and bottom margin.

### Claim 19 (depends on 13)

The image processing system according to claim 13, further comprising:
associating with each page of the document a coordinate system.

### Claim 20 (depends on 13)

The image processing system of claim 13, further comprising:
h) generating a page construct object associated with each page, the page construct fields representing one or more of position, width, left margin, right margin, height, top margin and bottom margin; and
associating with each page of the document a coordinate system.

### Claim 21

A computer program product comprising a non-transitory recording medium storing instructions, which when executed on a computer cause the computer to perform a method of generating a page construct hierarchical sequential structure associated with a digital version of a document comprising:
a) obtaining a sequence of pages representing the document;
b) defining a set of page construct features associated with each page of the sequence of pages, each page construct feature defined as a document element which recurrently occurs at regular positions outside a running content of the sequence of pages, the construct feature defined by a feature value types;
c) computing a set of feature values associated with the set of page construct features for each page of the sequence;
d) generating a set of n-grams from the sequence of pages, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages;
e) electing sequential n-grams from the set of n-grams, the sequential n-grams defined as similar contiguous n-grams;
f) selecting the most frequent sequential n-gram from the elected sequential n-grams; and
g) generating a new sequence of the pages by matching the selected most frequent sequential n-gram against the sequence of pages associated with the document, replacing matched pages of the sequence of pages with a respective node, and associating the matched pages of the sequence of pages as children of the respective node, the new sequence of pages representing the page construct hierarchical sequential structure associated with the document.

### Claim 22 (depends on 21)

The computer program product according to claim 21, the method further comprising:
h) iteratively repeating steps d)-g) on the new sequence of pages generated in step g) until all sequential n-grams associated with the sequence of pages are matched against the sequence of pages associated with the document, the respective matched pages of the sequence of pages are replaced with a respective node, and the respective matched pages of the sequence of pages are associated as children of the respective node.

### Claim 23 (depends on 22)

The computer program product according to claim 22, wherein step d) comprises:
d1) calibrating the set of page construct feature values for each page of the sequence by assigning equal feature values to page name features which are fuzzily equal; and
d2) generating a set of n-grams from the sequence of pages and calibrated set of page construct feature values, an n-gram including an ordered sequence of n page construct features provided by a sequence of n pages.

### Claim 24 (depends on 23)

The computer program product according to claim 23, wherein step g) comprises:
g1) matching the selected most frequent sequential n-gram against the sequence of pages to determine all sub-sequences of n contiguous pages which are matched by the selected n-gram;
g2) enriching the determined sub-sequences by generating n-grams for each sub-sequence; and
g3) generating a new sequence of pages by replacing each sub-sequence of contiguous matched pages with a respective node and associating the matched pages of the sequence of pages as children of the respective node.

### Claim 25 (depends on 21)

The computer program product according to claim 21, wherein the page construct features include a position of one or more of a left margin, a right margin, a top margin and a bottom margin.
