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

• US 7,257,253 B2
• Filed: 01/24/2003
• Issued: 08/14/2007
• Est. Priority Date: 06/28/2002
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Takebe, Hiroaki, Naoi, Satoshi, Fujimoto, Katsuhito, Ozawa, Noriaki
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US10/350,180
• Publication Number:
  US 20040001628A1
• Time in Patent Office: 1,663 Days
• Field of Search: 382175-180
• US Class Current: 382/176
• 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 computer-readable medium storing instructions for analyzing a layout of a document, which, when executed by a computer, causes the computer to perform operations comprising:

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

setting a circumscribed rectangle for each of the black pixel components, the circumscribed rectangle being circumscribed to each of the black pixel components and used as a character candidate;

classifying character sizes for each of the circumscribed rectangles into three categories of large, standard and small based on a value of a long side thereof;

integrating a first circumscribed rectangle having a small character size with a second circumscribed rectangle having a different character size from the first circumscribed rectangle when the first circumscribed rectangle and the second circumscribed rectangle overlap each other, and when a circumscribed rectangle formed from the first circumscribed rectangle and the second circumscribed rectangle is determined to be approximately square;

selecting two circumscribed rectangles having a shortest Euclidian distance between barycenters of the two circumscribed rectangles from a group of circumscribed rectangles;

setting integration of the two selected circumscribed rectangles as a character candidate element when the integration of the two circumscribed rectangles is determined to be approximately square;

extracting character candidate elements from the black pixel linkage components;

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

generating a line rectangle as a line candidate in the line orientation based on the extracted character candidate elements; and

segmenting the line rectangle into two line rectangles, in response to the line rectangle overlapping another line rectangle, before and after the another line rectangle.

2. The computer-readable medium according to claim 1, wherein the operation of extracting the line element includes classifying the character elements aligned in the line orientation by character sizes, and extracting character candidate elements as a line element, each amount of displacement of the extracted character candidate elements in the orientation perpendicular to the line orientation being smaller than or equal to the threshold value.

3. The computer-readable medium according to claim 1, the instructions further including an operation of integrating two adjacent line elements extracted in the operation of extracting the line element 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 computer-readable medium according to claim 3, the instructions further including an operation of segmenting a line element into two at a position at which an interval between character candidate elements included in the line element integrated is not less than a predetermined value.

5. The computer-readable medium according to claim 4, wherein the operation of segmenting the line element includes segmenting a line element into two when the line element overlaps any other line element but a character candidate element included in the line element does not overlap the other line element in the orientation perpendicular to the line orientation.

6. The computer-readable medium according to claim 3, wherein the operation of extracting the line element includes integrating two adjacent line elements in the line orientation into one line element when a length of the adjacent two line elements is approximately the same as a length of another line element adjacent to these two line elements in the orientation perpendicular to the line orientation.

7. The computer-readable medium according to claim 1, further including an operation 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.

8. The computer-readable medium according to claim 7, wherein the operation of extracting the paragraph element includes integrating 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 computer-readable medium according to claim 7, wherein the operation 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.

10. The computer-readable medium according to claim 1, wherein the operation of extracting the line element includes extracting a line element in horizontal orientation and vertical orientation, respectively.

11. The computer-readable medium according to claim 7, wherein the operation of extracting the paragraph element includes extracting 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 circumscribed rectangle setting unit that sets a circumscribed rectangle for each of the black pixel components, the circumscribed rectangle being circumscribed to each of the black pixel components and used as a character candidate;

a character size classifying unit that classifies character sizes for each of the circumscribed rectangles into three categorizes of large, standard and small based on a value of a long side thereof;

an integrating unit that integrates a first circumscribed rectangle having a small character size with a second circumscribed rectangle having a different character size from the first circumscribed rectangle when the first circumscribed rectangle and the second circumscribed rectangle overlap each other, and when a circumscribed rectangle formed from the first circumscribed rectangle and the second circumscribed rectangle is determined to be approximately square;

a selecting unit that selects two circumscribed rectangles having a shortest Euclidian distance between barycenters of the two circumscribed rectangles from a group of circumscribed rectangles;

a setting unit that sets integration of the two selected circumscribed rectangles as a character candidate element when the integration of the two circumscribed rectangles is determined to be approximately square;

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

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

a line rectangle generating unit that generates a line rectangle as a line candidate in the line orientation based on the extracted character candidate elements; and

a line rectangle segmenting unit that segments the line rectangle into two line rectangles, in response to the line rectangle overlapping another line rectangle, before and after the another line rectangle.

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 candidate elements as a line element, each amount of displacement of the extracted character candidate 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 candidate 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 candidate 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;

setting a circumscribed rectangle for each of the black pixel components, the circumscribed rectangle being circumscribed to each of the black pixel components and used used as a character candidate;

classifying character sizes for each of the circumscribed rectangles into three categories of large, standard and small based on a value of a long side thereof;

integrating a first circumscribed rectangle having a small character size with a second circumscribed rectangle having a different character size from the first circumscribed rectangle when the first circumscribed rectangle and the second circumscribed rectangle overlap each other, and when a circumscribed rectangle formed from the first circumscribed rectangle and the second circumscribed rectangle is determined to be approximately square;

selecting two circumscribed rectangles having a shortest Euclidian distance between barycenters of the two circumscribed rectangles from a group of circumscribed retangles;

setting integration of the two selected circumscribed rectangles as a character candidate element when the integration of the two circumscribed rectangles is determined to be approximately square;

extracting character candidate elements from the black pixel linkage components;

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

generating a line rectangle as a line candidate in the line orientation based on the extracted character elements; and

segmenting the line rectangle into two line rectangles, in response to the line rectangle overlapping another line rectangle, before and after the another line rectangle.

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 candidate 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 candidate 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 candidate 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.