Document page analyzer and method

• US 5,848,184 A
• Filed: 06/30/1995
• Issued: 12/08/1998
• Est. Priority Date: 03/15/1993
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Lipshutz, Mark, Taylor, Suzanne Amy
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/496,917
• Time in Patent Office: 1,257 Days
• Field of Search: 364/419.06, 364/419.05, 364/419.08, 364/419.1, 364/419.19, 395/144-148, 395/100, 395/116, 382/173, 382/176, 382/177, 382/178, 382/180, 382/284, 382/305, 382/312, 382/321, 707/500, 707/513-514, 707/517-525, 358/462
• US Class Current: 382/173
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Apparatus and method are provided which determine the geometric and logical structure of a document page from its image. The document image is partitioned into regions (both text and non-text) which are then organized into related "article" groups in the correct reading order. The invention uses image-based features, text-based features, and assumptions based on knowledge of expected layout, to find the correct reading order of the text blocks on a document page. It can handle complex layouts which have multiple configurations of columns on a page and inset material (such as figures and inset text blocks). The apparatus comprises two main components, a geometric page segmentor and a logical page organizer. The geometric page segmentor partitions a binary image of a document page into fundamental units of text or non-text, and produces a list of rectangular blocks, their locations on the page in points (1/72 inch), and the locations of horizontal rule lines on the page. The logical page organizer receives a list of text region locations, rule line locations, associated ASCII text (as found from an OCR) for the text blocks, and a list of text attributes (such as face style and point size). The logical page organizer groups appropriately the components (both text and non-text) which comprise a document page, sequences them in a correct reading order and establishes the dominance pattern (e.g., find the lead article on a newspaper page).

Claims

1. A method for analyzing a digital image of a document page, comprising the steps of:

detecting and removing one or more lines from the digital image, if any are present;

segmenting the line-removed image into one or more coarse blocks;

performing run-length smoothing on the coarse blocks;

performing connected component analysis on each of the smoothed coarse blocks to produce at least one connected component;

determining a bounding box for each of the connected components;

merging any overlapping bounding boxes to produce one or more finer blocks;

finding the block features of the digital image;

finding the page features of the digital image;

creating a geometric structure tree for the digital image;

said step of creating further comprising;

a) grouping the coarse blocks produced by said segmenting step into horizontal bands;

b) first determining column boundaries of each of the horizontal bands;

c) assigning finer blocks produced by the merging step to the horizontal bands;

d) second determining a geometric structure tree for all of the finer blocks in each of the horizontal bands;

e) merging the geometric structure trees producesd by the second determining step; and

logically transforming the geometric structure to produce a rearranged page image arranged in a proper reading order.

2. A method as defined in claim 1 wherein the second determining step comprises the steps of:

identifying which of the finer blocks, produced by the merging step, are column-aligned or non-column aligned;

creating a column-aligned geometric structure tree for the column-aligned finer blocks;

creating a non-column aligned geometric structure tree for the non-column aligned finer blocks; and

combining the non-column aligned geometric tree with the column-aligned geometric tree.

3. A method as defined in claim 2 wherein said step of creating the column-aligned geometric structure tree comprises the steps of:

creating a synthetic block which spans the top of the digital image and has zero height;

defining the synthetic block as the root node; and

finding the children of the root node.

4. A method as defined in claim 2 wherein said step of creating the non-column aligned geometric structure tree comprises the steps of:

creating a synthetic block which spans the top of the digital image and has zero height;

defining the synthetic block as the root node; and

finding the children of the root node.

5. The method as defined in claim 1 wherein said segmenting step comprises an X-Y tree segmentation.