Apparatus and method of analyzing layout of document, and computer product

• US 20040001628A1
• Filed: 01/24/2003
• Published: 01/01/2004
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Takebe, Hiroaki, Naoi, Satoshi, Fujimoto, Katsuhito, Ozawa, Noriaki
• Granted Patent: US 7,257,253 B2
• Time in Patent Office: Days
• US Class Current: 382/187
• 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

In an apparatus for analyzing a layout of a document, a character candidate element generator generates character candidate elements from black pixel linkage components of a document image. A horizontally oriented line rectangle generator sets a plurality of character candidate elements as a line candidate rectangle, among character candidate elements aligned in horizontal line orientation, when each amount of displacement of the set character candidate elements in a vertical orientation with respect to the horizontal line orientation, is smaller than or equal to a threshold value. A horizontally oriented paragraph-box generator sets a plurality of line candidate elements having approximately the same length as each other in the vertical orientation, as a paragraph candidate element.

Claims

1. A program for analyzing a layout of a document for allowing a computer to function as:

a black pixel linkage component extracting unit that extracts continuous black pixels as black pixel linkage components based on data for an image of the document;

a character element extracting unit that extracts character elements from the black pixel linkage components; and

a line element extracting unit that extracts a plurality of character elements as a line element, among character elements aligned in line orientation, each amount of displacement of the extracted character elements in orientation perpendicular to the line orientation being smaller than or equal to a threshold value.

2. The program according to claim 1, wherein the line element extracting unit classifies the character elements aligned in the line orientation by character sizes, and extracts character elements as a line element, each amount of displacement of the extracted character elements in the orientation perpendicular to the line orientation being smaller than or equal to the threshold value.

3. The program according to claim 1 for allowing the computer to further function as a line element integrating unit that integrates adjacent two line elements extracted by the line element extracting unit into one line element, when each amount of displacement of the two line elements in the orientation perpendicular to the line orientation is smaller than or equal to the threshold value.

4. The program according to claim 3 for allowing the computer to further function as a line element segmenting unit that segments a line element into two at a position at which an interval between character elements included in the line element integrated by the line element integrating unit, is not less than a predetermined value.

5. The program according to claim 4, wherein the line element segmenting unit segments a line element into two when the line element overlaps any other line element but a character element included in the line element does not overlap the other line element in the orientation perpendicular to the line orientation.

6. The program according to claim 3, wherein the line element integrating unit integrates adjacent two line elements in the line orientation into one line element when length of the adjacent two line elements is approximately the same as length of other line element adjacent to these two line elements in the orientation perpendicular to the line orientation.

7. The program according to claim 1 for allowing the computer to further function as a paragraph element extracting unit that extracts a plurality of line elements having approximately the same length as each other in the orientation perpendicular to the line orientation, as a paragraph element.

8. The program according to claim 7, wherein the paragraph element extracting unit integrates the paragraph element and a line element adjacent to the paragraph element so as to extract the two elements as a new paragraph element, when the new paragraph element does not overlap any other line element.

9. The program according to claim 7, wherein the paragraph element extracting unit extracts a plurality of line elements as a paragraph element, when the plurality of line elements adjacent to each other in the orientation perpendicular to the line orientation are aligned center.

10. The program according to claim 1, wherein the line element extracting unit extracts a line element in horizontal orientation and vertical orientation, respectively.

11. The program according to claim 7, wherein the paragraph element extracting unit extracts a paragraph element in horizontal orientation and vertical orientation, respectively.

12. An apparatus for analyzing a layout of a document comprising:

a black pixel linkage component extracting unit that extracts continuous black pixels as black pixel linkage components based on data for an image of the document;

a character element extracting unit that extracts character elements from the black pixel linkage components; and

a line element extracting unit that extracts a plurality of character elements as a line element, among character elements aligned in line orientation, each amount of displacement of the extracted character elements in orientation perpendicular to the line orientation being smaller than or equal to a threshold value.

13. The apparatus according to claim 12, wherein the line element extracting unit classifies the character elements aligned in the line orientation by character sizes, and extracts character elements as a line element, each amount of displacement of the extracted character elements in the orientation perpendicular to the line orientation being smaller than or equal to the threshold value.

14. The apparatus according to claim 12, further comprising:

a line element integrating unit that integrates adjacent two line elements extracted by the line element extracting unit into one line element, when each amount of displacement of the adjacent two line elements in the orientation perpendicular to the line orientation is smaller than or equal to the threshold value.

15. The apparatus according to claim 14, further comprising:

a line element segmenting unit that segments a line element into two at a position at which an interval between character elements included in the line element integrated by the line element integrating unit, is not less than a predetermined value.

16. The apparatus according to claim 15, wherein the line element segmenting unit segments a line element into two when the line element overlaps any other line element but a character element included in the line element does not overlap the other line element in the orientation perpendicular to the line orientation.

17. The apparatus according to claim 14, wherein the line element integrating unit integrates adjacent two line elements in the line orientation into one line element when length of the adjacent two line elements is approximately the same as length of other line element adjacent to these two line elements in the orientation perpendicular to the line orientation.

18. The apparatus according to claim 12, further comprising:

a paragraph element extracting unit that extracts a plurality of line elements having approximately the same length as each other in the orientation perpendicular to the line orientation, as a paragraph element.

19. The apparatus according to claim 18, wherein the paragraph element extracting unit integrates the paragraph element and a line element adjacent to the paragraph element so as to extract the two elements as a new paragraph element, when the new paragraph element does not overlap any other line element.

20. The apparatus according to claim 18, wherein the paragraph element extracting unit extracts a plurality of line elements as a paragraph element, when the plurality of line elements adjacent to each other in the orientation perpendicular to the line orientation are aligned center.

21. The apparatus according to claim 12, wherein the line element extracting unit extracts a line element in horizontal orientation and vertical orientation, respectively.

22. The apparatus according to claim 18, wherein the paragraph element extracting unit extracts a paragraph element in horizontal orientation and vertical orientation, respectively.

23. A method of analyzing a layout of a document comprising steps of:

extracting continuous black pixels as black pixel linkage components based on data for an image of the document;

extracting character elements from the black pixel linkage components; and

extracting a plurality of character elements as a line element, among character elements aligned in line orientation, each amount of displacement of the extracted character elements in orientation perpendicular to the line orientation being smaller than or equal to a threshold value.

24. The method according to claim 23, wherein the step of extracting the line element includes classifying the character elements aligned in the line orientation by character sizes, and extracting character elements as a line element, each amount of displacement of the extracted character elements in the orientation perpendicular to the line orientation being smaller than or equal to the threshold value.

25. The method according to claim 23, further comprising a step of:

integrating adjacent two line elements extracted in the step of extracting the line element into one line element, when each amount of displacement of the adjacent two line elements in the orientation perpendicular to the line orientation is smaller than or equal to the threshold value.

26. The method according to claim 25, further comprising a step of:

segmenting a line element into two at a position at which an interval between character elements included in the line element integrated in the step of integrating the line elements, is not less than a predetermined value.

27. The method according to claim 26, wherein the step of segmenting the line element includes segmenting a line element into two, when the line element overlaps any other line element but a character element included in the line element does not overlap the other line element in the orientation perpendicular to the line orientation.

28. The method according to claim 25, wherein the step of integrating the line elements includes integrating adjacent two line elements in the line orientation into one line element, when length of the adjacent two line elements is approximately the same as length of other line element adjacent to these two line elements in the orientation perpendicular to the line orientation.

29. The method according to claim 23, further comprising a step of:

extracting a plurality of line elements having approximately the same length as each other in the orientation perpendicular to the line orientation, as a paragraph element.

30. The method according to claim 29, wherein the step of extracting the paragraph element includes integrating the paragraph element and a line element adjacent to the paragraph element so as to extract the elements as a new paragraph element, when the new paragraph element does not overlap any other line element.

31. The method according to claim 29, wherein the step of extracting the paragraph element includes extracting a plurality of line elements as a paragraph element, when the plurality of line elements adjacent to each other in the orientation perpendicular to the line orientation are aligned center.

32. The method according to claim 23, wherein the step of extracting the line element includes extracting a line element in horizontal orientation and vertical orientation, respectively.

33. The method according to claim 29, wherein the step of extracting the paragraph element includes extracting a paragraph element in horizontal orientation and vertical orientation, respectively.