TEXT SEGMENTATION OF A DOCUMENT

• US 20120102388A1
• Filed: 09/07/2011
• Published: 04/26/2012
• Est. Priority Date: 10/26/2010
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Fan, Jian
• Application Number:
  US13/227,136
• Publication Number:
  US 20120102388A1
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/151 Transformation

Abstract

A system and method are provided for segmenting text from a portable document format (PDF) document. The system includes a memory for storing computer executable instructions and a processing unit for accessing the memory and executing the computer executable instructions. The computer executable instructions include an engine to group line segments into text blocks using a homogeneity measure based on relative line space difference between line segments and a homogeneity measure based on difference in font size between line segments, where the line segments comprise text elements extracted from the PDF document.

Claims

1. A system to segment text from a portable document format (PDF) document, the system comprising:

memory for storing computer executable instructions; and

a processing unit for accessing the memory and executing the computer executable instructions, the computer executable instructions comprising;

an engine to group line segments into text blocks using a homogeneity measure based on relative line space difference between line segments and a homogeneity measure based on difference in font size between line segments, wherein the line segments comprise text elements extracted from the PDF document.

2. The system of claim 1, wherein the computer executable instructions further comprise instructions to extract the text elements of the PDF document.

3. The system of claim 2, wherein the computer executable instructions to extract the text elements comprise instructions to:

determine quads of the PDF document, wherein the quads are determined based on the text elements; and

retrieve visual attributes of the quads, wherein the visual attributes are selected from the group consisting of font family, font size, font color and bounding box.

4. The system of claim 3, wherein the computer executable instructions further comprise instructions to merge the quads into line segments based on the visual attributes.

5. The system of claim 4, wherein the visual attributes comprise bounding boxes, and wherein the computer executable instructions to merge the quads into line segments comprise instructions to:

sort the quads in the order of top-down and left-to-right based on vertical center positioning of the bounding boxes of the quads; and

grow each line segment by a method comprising;

selecting a quad that has not been assigned a line identification to start a line segment;

extending the line segment by grouping qualified quads to the left or to the right, wherein a candidate quad is determined as a qualified quad if the candidate quad and the previously added quad meet a predetermined criterion; and

ceasing to extend the line segment if no other qualified quads are identified.

6. The system of claim 5, wherein the predetermined criterion is a vertical overlap, a font size difference, or a space between the candidate quad and the previously added quad.

7. The system of claim 1, wherein the line space is determined as a distance between vertical center lines, wherein each vertical center line is associated with a respective line segment, and wherein the vertical center line provides an indication of the position and extent of the respective line segment.

8. The system of claim 7, wherein the homogeneity measure based on relative line space difference is determined as a relative line space difference (Δ

(d_i,j, d_i,h)), wherein to group the line segments into text block, the engine determines block boundaries of the text block by comparing the relative line space difference using a predetermined threshold k_dl, wherein a line segment i is determined as a block boundary of a text block if Δ

(d_i,j, d_i,h)>

k_dl, wherein d_i,h is a distance between line segment h and line segment i, and wherein d_i,j is a distance between line segment j and line segment i.

9. The system of claim 8, wherein the homogeneity measure based on difference in font size is determined as a relative difference of font sizes Δ

(f₁, f₂), wherein to group the line segments into text block, the engine determines a line segment i as a block boundary if Δ

(f_i, f_j)>

k_fl or Δ

(f_i, f_h)>

k_fl, where f_i is the weighted average of font sizes within the line segment i, wherein f_j is the weighted average of font sizes within the line segment j, wherein f_h is the weighted average of font sizes within the line segment h, and wherein k_fl is a predetermined threshold.

10. The system of claim 9, wherein the engine comprises computer executable instructions to determine a block boundary of the text blocks using the homogeneity measure and the font measure according to an expression:

11. The system of claim 9, wherein, to group line segments into text blocks, the engine comprises computer executable instructions to:

apply a predetermined growing criterion to neighboring line segments, wherein the growing criterion determines if the neighboring line segments having non-zero horizontal overlap and no other text between them are to be merged; and

merge the neighboring line segments into a text block if the neighboring line segments meet the predetermined growing criterion.

12. The system of claim 1, wherein, to group line segments into text blocks, the engine comprises computer executable instructions to:

determine candidate lines of block boundaries of the text blocks;

apply a predetermined growing criterion to neighboring candidate line segments, wherein the growing criterion determines if the neighboring candidate line segments having non-zero horizontal overlap and no other text between them are to be merged; and

merge the neighboring candidate line segments into a text block if the neighboring candidate line segments meet the predetermined growing criterion.

13. A method performed using at least one processor of a computer system, the method comprising:

determining, using at least one processor, line segments of a portable document format (PDF) document, wherein the line segments comprise text elements extracted from the PDF document;

grouping, using at least one processor, the line segments into text blocks using a homogeneity measure based on relative line space difference between line segments and a homogeneity measure based on difference in font size between line segments, wherein the line space is determined as a distance between vertical center lines, wherein each vertical center line is associated with a respective line segment, and wherein the vertical center line provides an indication of the position and extent of the respective line segment.

14. The method of claim 13, wherein determining the line segments of the PDF document comprises:

determining quads of the PDF document, wherein the quads are determined based on the text elements;

retrieving visual attributes of the quads, wherein the visual attributes are selected from the group consisting of font family, font size, font color and bounding box; and

merging the quads into line segments based on the visual attributes.

15. The method of claim 14, wherein the visual attributes comprise bounding boxes, and wherein merging the quads into line segments comprises:

sorting the quads in the order of top-down and left-to-right based on vertical center positioning of the bounding boxes of the quads; and

growing each line segment by a method comprising;

selecting a quad that has not been assigned a line identification to start a line segment;

extending the line segment by grouping qualified quads to the left or to the right, wherein a candidate quad is determined as a qualified quad if the candidate quad and the previously added quad meet a predetermined criterion; and

ceasing to extend the line segment if no other qualified quads are identified.

16. The method of claim 15, wherein the predetermined criterion is a vertical overlap, a font size difference, or a space between the candidate quad and the previously added quad.

17. The method of claim 13, wherein grouping the line segments into text blocks comprises:

determining candidate line segments of block boundaries of the text blocks;

applying a predetermined growing criterion to neighboring candidate line segments, wherein the growing criterion determines if the neighboring candidate line segments having non-zero horizontal overlap and no other text between them are to be merged; and

merging the line segments between the neighboring candidate line segments into a text block if the neighboring candidate line segments meet the predetermined growing criterion.

18. A non-transitory computer-readable medium having code representing computer-executable instructions encoded thereon, the computer executable instructions comprising instructions executable to cause one or more processors:

determine line segments of a portable document format (PDF) document, wherein the line segments comprise text elements extracted from the PDF document; and

group the line segments into text blocks using a homogeneity measure based on relative line space difference between line segments and a homogeneity measure based on difference in font size between line segments, wherein the line space is determined as a distance between vertical center lines, wherein each vertical center line is associated with a respective line segment, and wherein the vertical center line provides an indication of the position and extent of the respective line segment.

19. The computer-readable medium of claim 18, wherein the computer executable instructions executable to cause one or more processors to determine the line segments of the PDF document comprises instructions executable to cause the one or more processors to:

determine quads of the PDF document, wherein the quads are determined based on the text elements;

retrieve visual attributes of the quads, wherein the visual attributes are selected from the group consisting of font family, font size, font color and bounding box; and

merge the quads into line segments based on the visual attributes.

20. The computer-readable medium of claim 18, wherein the computer executable instructions executable to cause one or more processors to group the line segments into text blocks comprises instructions executable to cause the one or more processors to:

determine candidate line segments of block boundaries of the text blocks;

apply a predetermined growing criterion to neighboring candidate line segments, wherein the growing criterion determines if the neighboring candidate line segments having non-zero horizontal overlap and no other text between them are to be merged; and

merge the line segments between the neighboring candidate line segments into a text block if the neighboring candidate line segments meet the predetermined growing criterion.