Method and apparatus for document segmentation by background analysis

• US 5,555,556 A
• Filed: 09/30/1994
• Issued: 09/10/1996
• Est. Priority Date: 09/30/1994
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ozaki, Masaharu
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/315,875
• Time in Patent Office: 711 Days
• Field of Search: 382/9, 382/21, 382/22, 382/8, 382/25, 382/49, 382/55, 382/24, 382/48, 382/203, 382/302, 382/173, 382/174, 382/175, 382/176, 382/190, 382/193, 382/198, 382/202, 382/203, 382/204, 235/375
• 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
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

A system for extracting document elements from a document using major white regions includes an input port for inputting a signal representing the document image, a connected component generator for generating connected components from the document image, a bounding box generator for generating a bounding box around each connected component, a major white region extractor for extracting major white regions from the document image, and a document element extractor for extracting the document elements from the document image. The method for extracting document elements comprises identifying primitive white areas laying between the bounding boxes, grouping the primitive white areas into groups, identifying the primitive white areas and groups which are major white regions, identifying closed loops of major white regions, segmenting the major white regions, locating closed loops of the segments, and identifying each portion of the document image enclosed by one of the closed loops of document segments as a document element.

Claims

1. A method for extracting document elements from a document image, comprising the steps of:

identifying at least one connected component in the document image;

generating a minimum bounding box for each at least one connected component in the document image;

identifying primitive background areas surrounding the at least one bounding box for the at least one connected component;

selectively eliminating the primitive background areas such that each remaining primitive background area exceeds a minimum threshold;

selectively combining the remaining primitive background areas in the document image which uniquely share a common edge to form major background regions;

determining at least one set of major background regions based on intersection points between the major background regions;

segmenting the document image into document elements based on the at least one set of determined major background regions; and

extracting the document elements segmented by the at least one set of determined major background regions.

2. The method of claim 1, wherein the step of forming major background regions comprises the steps of:

forming major background regions whose longitudinal axes are parallel to a first axis, said first axis comprising one of a horizontal axis and a vertical axis; and

forming major background regions whose longitudinal axes are parallel to a second axis, said second axis orthogonal to said first axis and comprising another of the horizontal axis and the vertical axis.

3. The method of claim 1, wherein the step of selectively eliminating the primitive background regions comprises the steps of:

extracting the identified primitive background areas;

comparing a width of each of the primitive background areas to a width threshold value; and

eliminating each of the primitive background areas having a width smaller than the width threshold value.

4. The method of claim 3, wherein the step of extracting primitive background areas includes the steps of:

forming a gap list;

forming a primitive background area list;

locating a top, a bottom, a leftmost side, and a rightmost side for the document image;

locating a first scanline as a current scanline at the top of the document image;

scanning the document image along the current scanline;

locating top edges of bounding boxes appearing in the current scanline;

establishing new primitive background areas and new primitive background gaps based on the located top edges of the appearing bounding boxes;

locating bottom edges of bounding boxes appearing in the current scanline;

establishing new primitive background areas and new primitive background gaps based on the located bottom edges of the appearing bounding boxes;

selecting a next scanline below the current scanline in the document image as the current scanline; and

repeating the scanning through selecting steps for each scanline of the document image until the current scanline is a last scanline of the document image;

locating bottom positions for primitive background gaps on the gap list at the bottom of the document image;

removing the primitive background gaps which have established bottoms from the gap list; and

adding new primitive background areas to the primitive background area list corresponding to the removed primitive white gaps.

5. The method of claim 4, wherein the step of establishing new primitive background areas and new primitive background gaps based on the located top edges of the bounding boxes comprises the steps of:

identifying primitive background gaps which touch the located top edges;

locating bottom positions for the primitive background gaps which touch a located top edge at a position corresponding to the located top edge;

removing the primitive background gaps which have established bottoms from the gap list;

adding new primitive background areas to the primitive background area list corresponding to the removed primitive background gaps;

establishing new primitive background gaps, each new primitive background gap having a top position at the located top edge, and a leftmost portion and a rightmost position located at sides of bounding boxes touching the new primitive background gap; and

adding the new primitive background gaps to the gap list.

6. The method of claim 4, wherein the step of establishing new primitive background areas and new primitive background gaps based on the located bottom edges of the bounding box comprises the steps of:

identifying primitive background gaps which touch sides of the bounding boxes whose bottom edge has been located;

locating a bottom position for the primitive background gaps which touch the sides of a bounding box whose bottom edge has been located, at the bottom edge of the bounding box;

removing primitive background gaps which have established bottoms from the gap list;

listing new primitive background areas on the primitive background area list corresponding to the removed primitive background gaps;

establishing new primitive background gaps, each new primitive background gap having a top portion located at the located bottom edge of the bounding box, and a leftmost portion and a rightmost portion located at sides of bounding boxes touching the new primitive background gaps; and

adding the new primitive background gaps to the gap list.

7. The method of claim 1, wherein the step of selectively combining the remaining primitive background areas comprises the steps of:

examining each of the plurality of primitive background areas, starting with primitive background areas located at the top of the document image and progressing to the bottom of the document image;

labeling each one of the plurality of primitive background areas;

assembling groups of primitive background areas, the groups of primitive background areas comprising primitive background areas having a common label;

comparing a height of each group of primitive background areas to a height threshold;

removing too-small groups of primitive background areas which have a height smaller than the height threshold and touch no other group;

removing branched groups of primitive background areas which have a height smaller than the height threshold and touch other groups only on one of a bottom of the branched group and a top of the branched group;

examining the groups of primitive background areas remaining after the too-small and branched groups removing steps to combine some of the remaining groups into a single group;

trimming short ends of selected primitive background areas in each one of the remaining groups;

merging primitive background areas, within each group of primitive background areas, which touch and have common left and right edges, into one primitive background area;

re-examining each of the removed primitive background area of those groups whose height is smaller than the height threshold;

merging re-examined removed primitive background areas into other primitive background areas;

comparing the height of each primitive background area to the height threshold; and

identifying primitive background areas which have a height greater than the height threshold as major background regions.

8. The method of claim 7, wherein the step of labeling each one of the primitive background areas comprises the steps of:

selecting a first primitive background area as the current primitive background area;

determining if the current primitive background area has already been labeled;

determining, when the current primitive background area is not labeled, if exactly one other primitive background area touches a top edge of the current primitive background area;

labeling the current primitive background area with a same label as the single primitive background area touching the top edge of the current primitive background area;

labeling the current primitive background area with a new label when other than exactly one other primitive background area touches the top edge of the current primitive background area;

determining if a plurality of primitive background areas touch a bottom edge of the current primitive background area;

labeling each one of the plurality of primitive background areas touching the bottom edge of the current primitive background area with a new label;

determining if any unlabeled primitive background areas remain;

selecting a next unlabeled primitive background area as the current primitive background area; and

repeating the exactly one touching area determining step through the remaining unlabeled areas determining step until no unlabeled primitive background areas remain.

9. The method of claim 7, wherein the step of examining groups of primitive background areas for regrouping comprises the steps of:

selecting a first labeled group as a current group;

determining if a single group touches a bottom edge of the current group;

determining if only the current group touches a top edge of the single group touching the bottom edge of the current group;

assigning, if a single group touches the bottom edge of the current group and only the current group touches the top edge of the single group, the label of the current group to the single group;

determining if any group has not been examined; and

repeating all of the steps until all of the groups have been examined.

10. The method of claim 7, wherein the trimming step comprises the steps of:

selecting a first group as the current group;

locating a leftmost side of the primitive background areas in the current group as the current leftmost side;

comparing a height of the current leftmost side of the primitive background areas to the height threshold;

determining if the current leftmost side height exceeds the height threshold;

selecting a next leftmost side as the current leftmost side;

repeating the comparing, determining and selecting steps until the height threshold is exceeded by the height of the current leftmost side;

removing ends of primitive background areas in the current group extending to the left of the next leftmost side which has a height greater than the height threshold;

identifying a rightmost side of primitive background areas in the current group as the current rightmost side;

comparing a height of the current rightmost side of the primitive background areas to the height threshold;

determining if the current rightmost side height exceeds the height threshold;

selecting a next rightmost side as the current rightmost side;

repeating the comparing, determining and selecting steps until the height threshold is exceeded by the height of the current rightmost side;

removing ends of primitive background areas extending to the right of the current rightmost side which has a height greater than the height threshold;

selecting a next group as the current group; and

repeating the leftmost side comparing step through the next group selecting step until no untrimmed groups remain.

11. The method of claim 7, wherein the merging step comprises the steps of:

selecting a first primitive background area as a current background area;

determining if a height threshold of the current primitive background area is less than a predetermined height threshold;

forming a list of primitive background areas which touch the current background area when the height threshold of the current primitive background area is less than the predetermined height threshold;

locating each pair of the touching primitive background areas on the list which touch a common portion of the current background area;

determining, for each such pair of two touching primitive background areas, if right and left edges of the pair of touching primitive background areas are sufficiently aligned;

removing each such pair of sufficiently aligned areas from the list of touching areas;

merging, for each such pair of sufficiently aligned touching areas, the pair of touching areas and the common portion of the current area into a combined area;

locating a widest one of the touching areas remaining on the list;

removing the widest area from the list of touching areas;

merging a touched portion of the current background area into the widest area;

removing any other touching areas from the list of touching areas which also touch the touched portion of the current background area;

repeating the widest area locating step through the any other touching area removing step until no areas remain on the list of touching areas;

selecting a next primitive background area as the current background area; and

repeating the height threshold determining step through selecting a next primitive background area step until no additional primitive background areas need to be compared to the height threshold.

12. The method of claim 1, wherein the step of determining at least one set of major background regions comprises the steps of:

locating intersection points where two major background regions intersect;

removing major background regions which do not form closed loops of major background regions;

dividing remaining ones of the major background regions into segments, each segment bounded by a pair of the located intersection points;

forming a list of segments;

selecting a first segment from the list of segments as a current segment;

generating a closed loop of intersecting segments, the closed loop including the current segment;

revising the list of segments;

outputting a portion of the document image enclosed by the closed loop as a current document element;

determining if any segments remain on the list of segments;

selecting a next segment from the list of segments as the current segment if the list of segments is not empty; and

repeating the generating through next segment selecting steps until the list of segments is empty.

13. The method of claim 12, wherein the removing step comprises the steps of:

locating any major background regions which intersect at most one other major background region;

removing the located major background regions;

determining if any major background regions which intersect at most one other major background region remain; and

repeating the locating, removing and determining steps until no major background regions intersecting less than two other major background regions remain.

14. The method of claim 12, wherein the dividing step comprises the steps of:

selecting a first major background region as a current region;

locating intersection points where other major background regions intersect the current region;

dividing the current region at each intersection point;

removing segments of the current region bounded by only one intersection point;

determining if any undivided major background region remains;

selecting a next undivided major background region as the current region; and

repeating the locating through the next undivided major background region selecting step until no undivided major background regions remain.

15. The method of claim 12, wherein the closed loop generating step comprises the steps of:

selecting a first intersection point of the current segment as a current intersection point;

moving from the current intersection point to a next intersection point of the current segment in a first one of a clockwise direction and a counterclockwise direction;

circling about the next intersection point in a second one of the clockwise direction and the counterclockwise direction until a next segment is located, wherein the second direction is opposite to the first direction;

determining if the next segment is the first segment;

selecting the next segment as the current segment and the next intersection point as the current intersection point if the next segment is not the first segment; and

repeating the moving step through the next segment selecting step until the next segment is the first segment.

16. An apparatus for segmenting a document image into at least one document element, the document image represented by a plurality of pixels, the plurality of pixels represented by portions of an image signal, the apparatus comprising:

input means for inputting the image signal;

memory means for storing the image signal;

connected component identifying means for identifying at least one connected component from the plurality of pixels forming the document image;

bounding box generating means for generating a minimum bounding box around each one of the at least one connected component;

background area identifying means for identifying background areas surrounding the at least one bounding box for the at least one connected component;

background area eliminating means for selectively eliminating background areas such that each remaining background area exceeds a minimum threshold;

major background region extraction means for selectively combining the remaining background areas of the document image which uniquely share a common edge to form major background regions;

determining means for determining at least one set of major background regions that segment the document image into at least one document element based on intersection points between the major background regions;

document element extraction means for extracting the at least one document element segmented by the at least one set of determined major background regions; and

control means for controlling the input means, the memory means, the connected component identifying means, the bounding box generating means, the background area identifying means, the background area eliminating means, the major background region extraction means, the determining means and the document element extraction means.

17. The apparatus of claim 16, wherein the major background region extraction means comprises a vertical extraction section and a horizontal extraction section.

18. The apparatus of claim 17, wherein the vertical and horizontal extraction sections each comprise:

primitive background area extraction means;

comparison means for comparing dimensions of the primitive background areas against predetermined dimension thresholds;

elimination means for eliminating primitive background regions based on an output of the comparison means; and

grouping means for grouping and merging remaining primitive background areas.