Page decomposition using local orthogonal transforms and a map optimization

• US 20030088825A1
• Filed: 09/30/2002
• Published: 05/08/2003
• Est. Priority Date: 10/02/2001
• Status: Active Grant

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Chakraborty, Amit
• Granted Patent: US 7,248,737 B2
• Time in Patent Office: Days
• US Class Current: 715/500
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

Document processing and understanding can be important for a variety of applications such as office automation, creation of electronic manuals, online documentation and annotation, etc. The first step towards this process can involve the decomposition of a page into separate units describing the text, graphics, pictures etc. Towards that end, a method of page decomposition comprises segmenting an image into a plurality of blocks according to an amount of information contained in each block, classifying each block according to a corresponding frequency spectrum, and refining a classification of each block.

Claims

1. A method of page decomposition comprising the steps of:

segmenting an image into a plurality of blocks according to an amount of information contained in each block;

classifying each block according to a corresponding frequency spectrum; and

refining a classification of each block.

2. The method of claim 1, wherein the step of segmenting an image further comprises the steps of:

dividing, iteratively, the plurality of blocks into a plurality of child blocks, wherein each of the plurality of blocks has a set of corresponding child blocks;

determining an entropy for each of the plurality of blocks and the set of corresponding child blocks; and

performing a further iteration upon determining the entropy of each of the plurality of blocks is greater than the entropy of the set of corresponding child blocks.

3. The method of claim 2, further comprising the steps of:

folding each block along at least one edge, wherein each block comprises a plurality of edges; and

determining a discrete cosine transform of each block prior to determining the entropy of the block.

4. The method of claim 1, wherein the step of classifying each block further comprises the steps of:

determining, for each block a plurality of probabilities according to the frequency spectrum of each block, wherein each probability corresponds to a content type;

determining for each block a maximum a posteriori probability; and

classifying each block within a Bayesian framework comprising block values and neighborhood values.

5. The method of claim 4, wherein the frequency spectrum of each block is classified according to a concentration of frequency content and variance of the frequency spectrum.

6. The method of claim 1, wherein an initial segmentation of the image is performed according to a predefined block size.

7. The method of claim 6, wherein the predefined block size is 256 pixels by 256 pixels.

8. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for page decomposition, the method steps comprising:

segmenting an image into a plurality of blocks according to an amount of information contained in each block;

classifying each block according to a corresponding frequency spectrum; and

refining a classification of each block.

9. The method of claim 8, wherein the step of segmenting an image further comprises the steps of:

dividing, iteratively, the plurality of blocks into a plurality of child blocks, wherein each of the plurality of blocks has a set of corresponding child blocks;

determining an entropy for each of the plurality of blocks and the set of corresponding child blocks; and

performing a further iteration upon determining the entropy of each of the plurality of blocks is greater than the entropy of the set of corresponding child blocks.

10. The method of claim 9, further comprising the steps of:

folding each block along at least one edge, wherein each block comprises a plurality of edges; and

determining a discrete cosine transform of each block prior to determining the entropy of the block.

11. The method of claim 8, wherein the step of classifying each block further comprises the steps of:

determining, for each block a plurality of probabilities according to the frequency spectrum of each block, wherein each probability corresponds to a content type;

determining for each block a maximum a posteriori probability; and

classifying each block within a Bayesian framework comprising block values and neighborhood values.

12. The method of claim 11, wherein the frequency spectrum of each block is classified according to a concentration of frequency content and variance of the frequency spectrum.

13. The method of claim 8, wherein an initial segmentation of the image is performed according to a predefined block size.

14. The method of claim 13, wherein the predefined block size is 256 pixels by 256 pixels.

15. A system adapted to decompose a page comprising:

a segmenting module for excepting an image, and dividing the image into a plurality of blocks according to an entropy of each block; and

a classifying module coupled to the segmenting module for excepting the plurality of blocks, wherein each block is classified according to a concentration component and a variance component of the frequency spectrum, and wherein a resulting classified image comprising a plurality of classified blocks is output.