Document image segmentation based on pixel classification

• US 9,715,624 B1
• Filed: 03/29/2016
• Issued: 07/25/2017
• Est. Priority Date: 03/29/2016
• Status: Active Grant

• Current Assignee: Konica Minolta Laboratory U.S.A., Inc. (Konica Minolta Inc.)
• Original Assignee: Konica Minolta Laboratory U.S.A., Inc. (Konica Minolta Inc.)
• Inventors: Fang, Gang
• Primary Examiner(s): Chawan, Sheela C
• Application Number:
  US15/084,353
• Time in Patent Office: 483 Days
• Field of Search: 382100, 382128, 382173, 382176, 382155, 382159, 382156, 382232, 382181, 382190, 382195, 382199, 382236, 382224, 382239, 382180, 382233, 382228, 382238, 382254, 382270, 382235, 358448, 358462, 358464, 358 301, 358 19, 358 306
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

In a document image segmentation method, pixels of the image are classified into different types such as background, text, table, etc., to generate an initial segmentation map. The initial segmentation map is processed multiple rounds. In each round, a working map is divided into 2×2 pixel blocks; based on pixel types in the block, a corresponding pixel in a combined map is assigned a type, and pixels in a corresponding block in the segmentation map are modified either to change some background pixels to other types or keep them unchanged. The initial segmentation map is used as the working map in the first round, and the combined map of the last round is used as the working map for the next round. After a number of rounds, remaining background pixels of the segmentation map are changed to other types based on the types of their neighboring areas.

Claims

1. A method implemented in a data processing apparatus for segmenting a document image containing a plurality of types of contents into multiple image segments, each image segment containing only one type of content, the method comprising:

(a) initializing a segmentation map having a size identical to that of the document image, by classifying each pixel of the document image into one of a plurality of pixel types based on content of the document image and assigning each pixel of the segmentation map a pixel type identical to the pixel type of the corresponding pixel of the document image, wherein the plurality of pixel types include at least a background pixel type, a first pixel type, and a second pixel type;

(b) defining a working map, the working map being identical to the segmentation map as initialized in step (a);

(c) for each of a plurality of pixel blocks in the working map, evaluating the pixels in the block, and based on the evaluation, assigning a pixel value to a pixel of a combined map corresponding to the block of the working map and assigning pixel values to pixels of a pixel block of the segmentation map that corresponds to the pixel of the combined map, including;

(c1) when the plurality of pixels in the block of the working map include only the background pixel type, assigning the background pixel type to the corresponding pixel of the combined map, and keeping the pixel type of each pixel in the corresponding block of the segmentation map unchanged,

(c2) when the plurality of pixels in the block of the working map include only the first pixel type or include only the first pixel type and the background pixel type, assigning the first pixel type to the corresponding pixel of the combined map, and assigning the first pixel type to each pixel in the corresponding block of the segmentation map,

(c3) when the plurality of pixels in the block of the working map include only the second pixel type or include only the second pixel type and the background pixel type, assigning the second pixel type to the corresponding pixel of the combined map, and assigning the second pixel type to each pixel in the corresponding block of the segmentation map, and

(c4) when the plurality of pixels in the block of the working map include both the first pixel type and the second pixel type or include an unknown pixel type, assigning the unknown pixel type to the corresponding pixel of the combined map, and keeping the pixel type of each pixel in the corresponding block of the segmentation map unchanged,

whereby the combined map is generated and the segmentation map is modified;

(d) repeatedly performing step (c) a number of rounds, each round using the combined map obtained from the last round as the working map, wherein in each round that step (c) is performed, the combined map is smaller in size than in the last round and each pixel block of the segmentation map that corresponds to a pixel of the combined map is larger in size than in the last round;

(e) after step (d), changing pixel types of any pixels of the segmentation map that have the background type to one of the other types of the plurality of pixel types; and

(f) segmenting the document image into the multiple image segments based on the segmentation map obtained in step (e), wherein each image segment corresponds to an area in the segmentation map that has only one type of pixels.

2. The method of claim 1, wherein in step (c), each of the plurality of pixel blocks in the working map is a p by q pixel block, and

wherein in an n-th time that step (c) is performed, each pixel in the combined map corresponds to a pⁿ by qⁿ pixel block of the segmentation map.

3. The method of claim 2, wherein step (c) includes generating p by q sub-maps from the working map, each sub-map being p by q times smaller than the working map, wherein each p by q block of pixels of the working map is distributed to the p by q sub-maps and are located at identical positions in the sub-maps, and

wherein the step of evaluating the pixels in a pixel block of the working map includes evaluating the pixels located at the corresponding identical positions in the p by q sub-maps.

4. The method of claim 2, wherein step (c) is repeated until the combined map is incapable of being divided into a plurality of p by q pixel blocks.

5. The method of claim 2, wherein p=2 and q=2.

6. The method of claim 1, wherein step (e) comprises:

grouping pixels in the segmentation map that have the background type into one or more contiguous groups; and

for each contiguous group;

examining neighboring pixels along an entire border of the contiguous group to determine a pixel type that is the most common among the neighboring pixels; and

assigning the most common pixel type to all pixels of the contiguous group in the segmentation map.

7. The method of claim 1, wherein the first pixel type and the second pixel type include two pixel types selected form a group consisting of a text type, a table type, a flowchart type and an other type.

8. A computer program product comprising a computer usable non-transitory medium having a computer readable program code embedded therein for controlling a data processing apparatus, the computer readable program code configured to cause the data processing apparatus to execute a process for segmenting a document image containing a plurality of types of contents into multiple image segments, each image segment containing only one type of content, the process comprising:

(a) initializing a segmentation map having a size identical to that of the document image, by classifying each pixel of the document image into one of a plurality of pixel types based on content of the document image and assigning each pixel of the segmentation map a pixel type identical to the pixel type of the corresponding pixel of the document image, wherein the plurality of pixel types include at least a background pixel type, a first pixel type, and a second pixel type;

(b) defining a working map, the working map being identical to the segmentation map as initialized in step (a);

(c) for each of a plurality of pixel blocks in the working map, evaluating the pixels in the block, and based on the evaluation, assigning a pixel value to a pixel of a combined map corresponding to the block of the working map and assigning pixel values to pixels of a pixel block of the segmentation map that corresponds to the pixel of the combined map, including;

(c1) when the plurality of pixels in the block of the working map include only the background pixel type, assigning the background pixel type to the corresponding pixel of the combined map, and keeping the pixel type of each pixel in the corresponding block of the segmentation map unchanged,

(c2) when the plurality of pixels in the block of the working map include only the first pixel type or include only the first pixel type and the background pixel type, assigning the first pixel type to the corresponding pixel of the combined map, and assigning the first pixel type to each pixel in the corresponding block of the segmentation map,

(c3) when the plurality of pixels in the block of the working map include only the second pixel type or include only the second pixel type and the background pixel type, assigning the second pixel type to the corresponding pixel of the combined map, and assigning the second pixel type to each pixel in the corresponding block of the segmentation map, and

(c4) when the plurality of pixels in the block of the working map include both the first pixel type and the second pixel type or include an unknown pixel type, assigning the unknown pixel type to the corresponding pixel of the combined map, and keeping the pixel type of each pixel in the corresponding block of the segmentation map unchanged,

whereby the combined map is generated and the segmentation map is modified;

(d) repeatedly performing step (c) a number of rounds, each round using the combined map obtained from the last round as the working map, wherein in each round that step (c) is performed, the combined map is smaller in size than in the last round and each pixel block of the segmentation map that corresponds to a pixel of the combined map is larger in size than in the last round;

(e) after step (d), changing pixel types of any pixels of the segmentation map that have the background type to one of the other types of the plurality of pixel types; and

(f) segmenting the document image into the multiple image segments based on the segmentation map obtained in step (e), wherein each image segment corresponds to an area in the segmentation map that has only one type of pixels.

9. The computer program product of claim 8, wherein in step (c), each of the plurality of pixel blocks in the working map is a p by q pixel block, and

wherein in an n-th time that step (c) is performed, each pixel in the combined map corresponds to a pⁿ by qⁿ pixel block of the segmentation map.

10. The computer program product of claim 9, wherein step (c) includes generating p by q sub-maps from the working map, each sub-map being p by q times smaller than the working map, wherein each p by q block of pixels of the working map is distributed to the p by q sub-maps and are located at identical positions in the sub-maps, and

wherein the step of evaluating the pixels in a pixel block of the working map includes evaluating the pixels located at the corresponding identical positions in the p by q sub-maps.

11. The computer program product of claim 9, wherein step (c) is repeated until the combined map is incapable of being divided into a plurality of p by q pixel blocks.

12. The computer program product of claim 9, wherein p=2 and q=2.

13. The computer program product of claim 8, wherein step (e) comprises:

grouping pixels in the segmentation map that have the background type into one or more contiguous groups; and

for each contiguous group;

examining neighboring pixels along an entire border of the contiguous group to determine a pixel type that is the most common among the neighboring pixels; and

assigning the most common pixel type to all pixels of the contiguous group in the segmentation map.

14. The computer program product of claim 8, wherein the first pixel type and the second pixel type include two pixel types selected form a group consisting of a text type, a table type, a flowchart type and an other type.