Background-based image segmentation

• US 6,973,213 B2
• Filed: 10/12/2001
• Issued: 12/06/2005
• Est. Priority Date: 10/12/2001
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Fan, Zhigang, Cheng, Hui
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/977,186
• Publication Number:
  US 20030072487A1
• Time in Patent Office: 1,516 Days
• Field of Search: 382173-179, 382164-165, 382170-171, 382254-260, 382298-300, 382/101, 382180-187, 382224-225, 382190-208, 358/1.9, 358/2.1, 358/296, 358462-467
• US Class Current: 382/176
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20156 Automatic seed setting
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/155 involving morphological operators
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• 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

A method for segmenting an image using a background-based segmentation process is provided. A document image (102) is low-pass filtered and decimated. The decimated image is processed at low resolution by a low-resolution segmentation (104) stage. Segmentation results include identification of a main background and one or more objects. Objects that cannot be classified in text or picture classes are further segmented into a local background and smaller objects. This process is reiterated until all objects are classified in text or picture classes. The results are overlaid on the image (102) during an original-resolution refinement (106) stage to refine the segmentation.

Claims

1. An image segmentation process comprising the following steps:

a) segmenting an image into a main background, a first local background, and a first object, wherein the first object is on either the main background or the first local background;

b) classifying the first object into one class of a group of classes consisting of a text object, a picture object, and a composite object;

c) if the first object is classified as a composite object, identifying a second local background for the first object; and

d) segmenting a next object on the second local background.

2. The process set forth in claim 1, further comprising the following steps:

e) classifying the next object into one class of a group of classes consisting of a text object, a picture object, and a composite object; and

f) if the next object is classified as a composite object, performing steps c) through e) for the next object.

3. The process set forth in claim 1, step a)further comprising the following steps:

e) identifying one or more block of pixels in the image, wherein the dynamic ranges of each of the three color channels are less than a predetermined threshold for the block;

f) applying a region growing algorithm to each uniform block, wherein adjacent pixels with a color difference from the uniform block less than a predetermined threshold are marked as belonging to the region;

g) calculating a mean color for each grown region;

h) combining regions of similar mean color; and

i) identifying the region with the largest bounding area as the main background for the image.

4. The process set forth in claim 1, step a) further comprising the following steps:

e) detecting edges in the main background in both vertical and horizontal directions;

f) removing the edge pixels from the main background;

g) identifying a non-text object on the main background using a connect component analysis; and

h) segmenting the non-text object on the main background.

5. The process set forth in claim 1, wherein the first object is classified as a composite object, step c) further comprising the following steps:

e) detecting edges in the first object;

f) removing the edge pixels from the first object;

g) applying a region growing algorithm to each pixel on the outer boundary of the removed edge pixels, wherein adjacent pixels with a color difference from the region less than a predetermined threshold are marked as belonging to the region; and

h) identifying the region with the largest bounding area;

i) comparing the dimensions of the largest region to a predetermined threshold; and

j) if the dimensions of the largest region are greater than the predetermined threshold, identifying the region as the second local background for the first object, otherwise, reclassifying the first object as a picture object.

6. The process set forth in claim 2, steps d) and e) further comprising the following steps:

g) applying a one-dimensional morphological algorithm to the second local background in the horizontal direction to segment the next object and classifying the next object as a text object if the width of the elements detected by the algorithm is less than a maximal width; and

h) applying a one-dimensional morphological algorithm to the second local background in the vertical direction to segment the next object and classifying the next object as a text object if the width of the elements detected by the algorithm is less than a maximal width.

7. The process set forth in claim 1, step d) further comprising the following steps:

e) detecting edges in the second local background in both vertical and horizontal directions;

f) removing the edge pixels from the second local background; and

g) segmenting the next object on the second local background using a connect component analysis.

8. A method for segmenting an image, comprising the following steps:

a) identifying a main background for the image;

b) identifying a first object on the main background;

c) classifying the first object into one class of a group of classes consisting of a text object, a picture object, and a composite object;

d) if the first object is classified as a composite object, identifying a local background for the first object;

e) if the first object is classified as a composite object, identifying a second object on the local background;

classifying the second object into one class of a group of classes consisting of a text object, a picture object, and a composite object; and

if the second object is classified as a composite object;

identifying a local background for the second object.

9. The method set forth in claim 8, further comprising the following steps:

h) if the second object is classified as a composite object, identifying a third object on the local background of the second object;

i) classifying the third object into one class of a group of classes consisting of a text object, a picture object, and a composite object; and

j) if the third object is classified as a composite object, identifying a local background for the third object.

10. The method set forth in claim 8, further comprising the following steps:

i) if the second object is classified as a composite object, identifying a third object on the local background of the second object;

j) classifying the third object into one class of a group of classes consisting of a text object, a picture object, and a composite object; and

k) if the third object is classified as a composite object, identifying a local background for the third object.

11. A method for segmenting an image, comprising the following steps:

a) identifying a main background for the image;

b) identifying a first object on the main background;

c) classifying the first object into one class of a group of classes consisting of a text object, a picture object, and a composite object; and

d) if the first object is classified as a composite object, identifying a local background for the first object;

e) if the first object is classified as a composite object, determining if the dimensions of the local background of the first object are greater than a predetermined threshold; and

f) if the dimensions are not greater than the predetermined threshold, reclassifying the first object as a picture object.