Layout analysis

• US 7,392,472 B2
• Filed: 04/25/2002
• Issued: 06/24/2008
• Est. Priority Date: 04/25/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Simard, Patrice Y., Rinker, James Russell
• Primary Examiner(s): DESAI, RACHNA SINGH
• Application Number:
  US10/133,939
• Publication Number:
  US 20030204816A1
• Time in Patent Office: 2,252 Days
• Field of Search: 715/517, 715/530, 715/243, 715/255, 345/440, 345/467
• US Class Current: 715/243
• 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 system and method facilitating layout analysis is provided. The invention includes a layout analyzer having a connected component organizer, a connected joiner, a word organizer and a word joiner. The invention provides for the connected component organizer to organize connected components based upon color, horizontal position and/or vertical position. The invention provides for the connected component joiner to join connected components based, at least in part, upon color, vertical position, horizontal position, a distance between the connected components, height of the connected components and/or width of the connected components. The word organizer organizes words and the word joiner joins words into lines. The joining of words into lines can cause the connected component joining to attempt to further join connected components into words.

Claims

1. A computer-implemented layout analyzer that is recorded on computer storage media and capable of execution by a computer, comprising the following computer-executable components:

a connected component organizer that organizes connected components by color, vertical position and horizontal position;

a connected component joiner that joins connected components into words, based on statistics from groups comprising connected components and at least one of color, vertical position, horizontal position, height of connected components, or width of connected components;

a word organizer that organizes words by at least one of color, vertical position, horizontal position, or length, or combinations thereof; and

a word joiner that joins words into lines, based on statistics from groups comprising words and at least one of color, vertical position, horizontal position, height, width, angle, or length of words;

wherein after each joining operation, the statistics from groups comprising the connected components and from groups comprising words are re-computed and output as revised statistics, each joining operation comprises joining components into words and joining words into lines and producing a respective list of potential connected components and words to be revisited for further joining by the component joiner and word joiner utilizing the revised statistics;

wherein the word joiner provides the output to the connected component joiner to initiate further attempted joining of connected components based in part upon the list of potential connected components and upon the revised statistics from previously joined connected components and words;

wherein the layout analyzer outputs layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device; and

wherein the output from the encoder is then stored for use by a user.

2. The layout analyzer of claim 1, the connected component joiner providing an output to the word joiner to initiate further attempted joining of words based, at least in part, upon revised statistics from groups comprising words.

3. The layout analyzer of claim 1, further comprising:

a line organizer that organizes lines by at least one of color, vertical position, horizontal position, or length, or combinations thereof; and

,

a line joiner that joins lines into block, based at least in part upon at least one of color, vertical position, horizontal position, height, width, angle, or length of line;

wherein the line joiner provides an output to at least one of the connected component joiner to initiate further attempted joining of connected components based, at least in part, upon revised statistics from groups comprising the connected components,

and the word joiner to initiate further attempted joining of words based, at least in part,

upon revised statistics from groups comprising words.

4. The layout analyzer of claim 3, the connected component joiner providing an output to the line joiner to initiate further attempted joining of lines.

5. The layout analyzer of claim 3, the connected component joiner further joins connected components if a height of a first connected component is within a first height range of the height of a second connected component and a width of the first connected component is within a width range of the second connected component.

6. The layout analyzer of claim 1, the connected component organizer receiving connected component information comprising at least one of color, horizontal size, vertical size, horizontal position and vertical position of the connected components.

7. The layout analyzer of claim 1, the connected component joiner joins connected components if the connected components are within a join distance of each other.

8. A photocopier employing the layout analyzer of claim 1.

9. A document scanner employing the layout analyzer of claim 1.

10. An optical character recognition system comprising a processor and employing the layout analyzer of claim 1.

11. A personal digital assistant employing the layout analyzer of claim 1.

12. A fax machine employing the layout analyzer of claim 1.

13. A digital camera employing the layout analyzer of claim 1.

14. A digital video camera employing the layout analyzer of claim 1.

15. A tablet personal computer employing the layout analyzer of claim 1.

16. A segmented layered image system comprsing a processor and employing the layout analyzer of claim 1.

17. A method for layout analysis that is recorded on a computer storage media and capable of execution by a computer, comprising the following computer-executed acts:

organizing connected components by color, vertical position and horizontal position;

joining connected components into at least one word based on at least one of color, vertical position and horizontal position, a distance between the connected components, height of the connected components or width of the connected components

producing a list of potential connected components to be revisited for further joining into words;

re-computing statistics after each joining operation;

utilizing the statistics and the list of potential connected components to initiate further joining of the connected components;

outputting layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device; and

storing the output information from the encoder for use by a user.

18. The method of claim 17, joining of connected components being based, at least in part, upon whether the connected components are within a join distance of each other and a height of a first connected component is within a first height range of the height of a second connected component and a width of the first connected component is within a width range of the second connected component.

19. A layout analysis system that is recorded on a computer storage media and capable of execution by a computer, comprising the following computer-executable components:

a connected component store storing information associated with a plurality of connected components; and

a layout analyzer comprising a connected component organizer adapted to organize connected components by at least one of color, vertical position or horizontal position, or combinations thereof, the layout analyzer further comprising a connected component joiner adapted to join connected components into words, based on statistics from groups comprising connected components and at least one of color, vertical position, horizontal position, height of connected components, or width of connected components the layout analyzer further comprising a word organizer adapted to organize words by at least one of color, vertical position, horizontal position, or length, or combinations thereof, the layout analyzer further comprising a word joiner adapted to join words into lines, based on statistics from groups comprising words and at least one of color, vertical position, horizontal position, height, width, angle, or length of words,

wherein after each joining operation, the statistics are re-computed and output as revised statistics from groups comprising the connected components and from groups comprising words, each joining operation comprises joining components into words and joining words into lines and producing a respective list of potential connected components and words to be revisited for further joining by the component joiner and word joiner utilizing the revised statistics,

wherein the word joiner provides the output to the connected component joiner to initiate further attempted joining of connected components based in part upon the list of potential connected components and upon the revised statistics from previously joined connected components and words,

wherein the layout analyzer outputs layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device, and

wherein the output from the encoder is then stored for use by a user.

20. The layout analysis system of claim 19, the connected component store storing at least one of horizontal size, vertical size, horizontal position and vertical position associated with the plurality of connected components.

21. A method for layout analysis that is recorded on a computer storage media and capable of execution by a computer, comprising the following computer-executed acts:

organizing connected component information;

joining connected components into words;

producing a list of potential connected components to be revisited for further joining into words;

joining words into a line;

producing a list of potential words to be revisited for further joining into lines;

re-computing statistics after joining each word into a line;

utilizing the statistics to attempt further joining of connected components into words based, at least in part, upon revised statistics generated by the joining of words into lines and upon the list of potential connected components;

joining lines into a block;

re-computing statistics after joining each line into a block;

utilizing the statistics to attempt further joining of connected components into words based, at least in part, upon revised statistics generated by the joining of lines into the block and upon the list of potential connected components;

re-computing statistics after joining each connected component into a word;

utilizing the statistics to attempt further joining of words into lines based, at least in part, upon revised statistics generated by the joining of lines into the block and upon the list of potential words;

outputting layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device; and

storing the output information from the encoder for use by a user.

22. A segmented layered image system that is recorded on a computer storage media and capable of execution by a computer, comprising the following computer-executable components:

a mask separator adapted to assign pixels of a document image into at least one of a foreground and a background, the assignment information stored in a mask;

a layout analyzer comprising a connected component organizer adapted to organize connected components by at least one of color, vertical position or horizontal position, or combinations thereof the layout analyzer further comprising a connected component joiner adapted to join connected components into words, based on statistics from groups comprising connected components and at least one of color, vertical position, horizontal position, height of connected components, or width of connected components, the layout analyzer further comprising a word organizer adapted to organize words by at least one of color, vertical position, horizontal position, or length, or combinations thereof, the layout analyzer further comprising a word joiner adapted to join words into lines, based on statistics from groups comprising words and at least one of color, vertical position, horizontal position, height, width, angle, or length of words,

wherein after each joining operation, the statistics from groups comprising the connected components and from groups comprising words are re-computed and output as revised statistics, each joining operation comprises joining components into words and joining words into lines and producing a respective list of potential connected components and words to be revisited for further joining by the component joiner and word joiner utilizing the revised statistics,

wherein the word joiner provides the output to the connected component joiner to initiate further attempted joining of connected components based in part upon the list of potential connected components and upon the revised statistics from previously joined connected components and words,

wherein the layout analyzer outputs layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device, and

wherein the output from the encoder is then stored for use by a user; and

a mask encoder operative to encode the mask into a mask bit stream.

23. A system for layout analysis that is recorded on a computer storage media and capable of execution by a computer, comprising:

a data packet adapted to be transmitted between two or more computer components that facilitates layout analysis, the data packet comprising;

layout information comprising data identifying at least two connected components as joined to each other, joining being based, at least in part, upon at least one of color, vertical position, horizontal position, a distance between the connected components, height of the connected components or width of the connected components;

wherein after each joining operation, the layout information is re-computed and output as revised statistics from groups comprising the connected components and from groups comprising words, each joining operation comprises joining components into words and joining words into lines and producing a respective list of potential connected components and words to be revisited for further joining utilizing the revised statistics;

wherein providing the output to the connected component to initiate further attempted joining of connected components based in part upon the list of potential connected components and upon the revised statistics from previously joined connected components and words;

wherein the layout analyzer outputs layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device; and

wherein the output from the encoder is then stored for use by a user.

24. A computer storage media storing computer executable components of a system for layout analysis, comprising:

a connected component organizer that organizes connected components by at least one of color, vertical position or horizontal position, or combinations thereof;

a connected component joiner that joins connected components into words, based on statistics from groups comprising connected components and at least one of color, vertical position, horizontal position, height of connected components, or width of connected components;

a word organizer that organizes words by at least one of color, vertical position, horizontal position, or length, or combinations thereof; and

a word joiner that joins words into lines, based on statistics from groups comprising words and at least one of color, vertical position, horizontal position, height, width, angle, or length of words;

wherein after each joining operation, the statistics from groups comprising the connected components and from groups comprising words are re-computed and output as revised statistics, each joining operation comprises joining components into words and joining words into lines and producing a respective list of potential connected components and words to be revisited for further joining by the component joiner and word joiner utilizing the revised statistics;

wherein the word joiner provides the output to the connected component joiner to initiate further attempted joining of connected components based in part upon the list of potential connected components and upon the revised statistics from previously joined connected components and words;

wherein the layout analyzer outputs layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device; and

wherein the output from the encoder is then stored for use by a user.

25. A method for layout analysis that is recorded on a computer storage media and capable of execution by a computer, comprising:

organizing connected component information;

joining connected components into words;

producing a list of potential connected components to be revisited for further joining into words;

joining words into a line;

producing a list of potential words to be revisited for further joining into lines;

re-computing statistics after joining each word into a line;

utilizing the statistics to attempt further joining of connected components into words based, at least in part, upon revised statistics generated by the joining of words into lines and upon the list of potential connected components;

joining lines into a block;

re-computing statistics after joining each line into a block;

utilizing the statistics to attempt further joining of connected components into words based, at least in part, upon revised statistics generated by the joining of lines into the block and upon the list of potential connected components;

re-computing statistics after joining each connected component into a word;

utilizing the statistics to attempt further joining of words into lines based, at least in part, upon revised statistics generated by the joining of lines into the block and upon the list of potential words;

outputting layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device; and

storing the output information from the encoder for use by a user.

26. A computer-implemented layout analyzer that is recorded on a computer storage media and capable of execution by a computer, comprising:

computer-implemented means for organizing connected components by at least one of color, vertical position or horizontal position, or combinations thereof;

computer-implemented means for joining connected components into words, based on statistics from groups comprising connected components and at least one of color, vertical position, horizontal position, height of connected components, or width of connected components;

computer-implemented means for organizing words by at least one of color, vertical position, horizontal position, or length, or combinations thereof;

computer-implemented means for joining words into lines, based on statistics from groups comprising words and at least one of color, vertical position, horizontal position, height, width, angle, or length of words;

wherein after each joining operation, the statistics from groups comprising the connected components and from groups comprising words change and are re-computed and output as revised statistics, each joining operation comprises joining components into words and joining words into lines and producing a respective list of potential connected components and words to be revisited for further joining by the component joiner and word joiner utilizing the revised statistics; and

wherein the computer-implemented means for joining words provides the output to the computer-implemented means for joining connected components to initiate further attempted joining of connected components based in part upon the list of potential connected components and upon the revised statistics from previously joined connected components and words;

computer-implemented means for outputting layout information to be used by an encoder to enable data compression and to enable reflow of connected components on an output device; and

computer-implemented means for storing the output information from the encoder for use by a user.