Method and apparatus for generating layout-preserved text

Methods and apparatus for generating layout-preserved text output from portable document format (PDF) input are described. A layout-preserved text generation method may generate layout-preserved text output from PDF input that includes the text along with indentations, spaces, newlines, and paging and that thus preserves the global document layout view of the original PDF input document. The layout-preserved text generation method may transform the PDF (X, Y) document space into a text file grid space while preserving a similar global view of the text and layout from the PDF (X, Y) document space. This transformation may include determining a base size per grid that may produce accurate layout in the text output from the PDF input.

BACKGROUND

Description of the Related Art

Documents are generally formatted according to some layout pattern, whether the pattern is a simple block format or a more complex multi-column format. In many documents, metadata may be indicated by the document layout pattern. For example, the title of a document typically starts from the beginning of the document, and is typically presented in the center and top of the page. As another example, page number and publisher information is often presented in the center bottom of the page or in the top left or right corner of the page. The layout of a document may thus provide important key features that indicate useful metadata information of the document.

As an example of a document format that indicates metadata, movie scripts have a script layout format that is recognized as a film industry standard. The standard has evolved over decades in the industry, and has become a universal standard script format for writers in the film medium worldwide, from short dramas through feature-length films. Movie scripts have specific format requirements according to the evolved standard such as “There should be 2× returns between Scene Description and Dialogue (and vice versa)” and “Dialogue should be indented (tabbed but not centered) so that accurate script timings can be made.” By using this standard, it is straightforward for a viewer, for example, to identify scene descriptions and dialogues from movie scripts.

Portable Document Format (PDF)

Adobe System's Portable Document Format (PDF) is a platform-independent format for representing documents, and has become a standard for electronic document storage and exchange. Text in PDF is represented by text elements in page content streams. A text element specifies that characters should be drawn at certain positions indicated by spatial coordinates. The characters are specified using the encoding of a selected font resource. Text in PDF documents may be considered similar to a drawing, with X and Y axes in the document, and X and Y coordinates for each of the text elements that indicate the locations of the elements in the document.

Many documents, for example movie scripts, are scanned or otherwise processed to generate PDF documents for storage and exchange. For example, a movie script may be converted to a PDF document, stored, and later retrieved. As another example, a movie script in PDF format may be downloaded or emailed. However, it is often necessary or desired to extract the text from a PDF document, such as a movie script preserved, downloaded, or emailed in PDF format. Conventional methods for extracting text from PDF documents, however, generally do not preserve formatting/page layout information. Therefore, for many documents, such as movie scripts, extracting text using these conventional methods may lose valuable metadata indicated by the formatting/page layout when extracting text from PDF documents.

Adobe and Adobe PDF are either registered trademarks or trademarks of Adobe Systems Incorporated in the United States and other countries.

SUMMARY

Various embodiments of methods and apparatus for generating layout-preserved text output from portable document format (PDF) input are described. Using embodiments of a layout-preserved text generation method as described herein, layout-preserved text output may be generated from PDF input that includes the text along with indentations, spaces, newlines, and paging and that thus preserves the global document layout view of the original PDF input document. Embodiments of the layout-preserved text generation method may transform the PDF (X, Y) document space into a text file grid space while preserving a similar global view of the text and layout from the PDF (X, Y) document space. This transformation may include determining a base size per grid that may produce accurate layout in the text output from the PDF input.

In some embodiments of a layout-preserved text generation method, a PDF document is obtained. Text, spatial information, font information, and possibly other information may be obtained from the PDF document. Base width and height values for the text document may be determined from the text and font information from the PDF document. The base width and height values may be designated as (Wb, Hb). If the PDF document uses the same font style and size across the entire document, the average width and height values of this font may be determined and used as (Wb, Hb). In some embodiments, the average width value of the font may be calculated as the average of the widths of all the characters of the particular font. The average height value may be similarly calculated, or determined using some other method. If the PDF document includes text elements in two or more different font styles and/or different font sizes, in some embodiments, the smallest font style/size may be selected and used to determine (Wb, Hb) for the text document.

A next text element to be processed may be obtained. A space and line value (SN, LN) may be calculated for the text element in the text document from the base width and height values (Wb, Hb) and the spatial information corresponding to the text element. In some embodiments, to calculate (SN, LN) for a text element N, the following formulas may be used:
SN=XN/Wb
LN=YN/Hb
where (XN, YN) are the coordinates of the text element N in the (X, Y) space of the PDF document, (Wb, Hb) are the base width and height being used for the transformation, and (SN, LN) are the calculated spacing and newline values for the text element in the grid space of the layout-preserved text document. The text from the text element may be written to the output text document according to the space and line values (SN, LN) corresponding to the text element to thus preserve the layout represented in the input PDF document. If there are more text elements to be processed, then the method gets and processes the next text element. If there are no more text elements to be processed, then the method is done.

A PDF document may include more than one page. In some embodiments, each page may be separately processed according to the above method. Text and spatial information, and possibly other information such as font information may be obtained for a page of the PDF document. (Wb, Hb) may be determined for the page. The text elements on the page may then be processed accordingly. The method may then proceed to the next page.

Some PDF documents or some pages of a PDF document may include two or more columns of text elements. In some embodiments, if it is determined that a current text element is located in a column after a previously processed text element, the spacing CSof the current text element in this column from the text in the preceding column may be calculated as follows:Get a value for I. In some embodiments, (SN, LN) may be calculated for the current text element, and the calculated value for SNmay be used as the value for I.Get a value for J. In some embodiments, J may be calculated as the total number of character spaces on the current line up to and including the last character of the previously written text element.Calculate CSas I−J.

The above calculations for column spacing may be expressed more generally as:
CSn=IN−JN
which may be more fully expressed as:
CSn=SN−(SN-1+NumChars(N−1))
where CSnrepresents the column spacing being calculated for the current column, SNis the spacing calculated for the current text element according to the (X,Y) spatial information from the PDF document, SN-1is the spacing calculated for the previous text element according to the (X,Y) spatial information from the PDF document, and NumChars(N−1) represents the number of characters in the previous text element.

DETAILED DESCRIPTION OF EMBODIMENTS

Various embodiments of methods and apparatus for generating layout-preserved text output from portable document format (PDF) input are described. PDF documents are formatted according to a document format that specifies locations of elements within the source document in (X, Y) spatial coordinates. The output text documents are formatted according to a grid space in which text is located horizontally on lines according to character spacing and vertically according to line spacing. Using embodiments of a layout-preserved text generation method as described herein, layout-preserved text output may be generated from PDF input; the text output includes the text from the PDF document along with indentations, spaces, newlines, and paging that preserve the global document layout view of the original PDF input. Embodiments of the layout-preserved text generation method provide text extraction from PDF documents that preserves or closely approximates the layout of text in the original PDF document. Embodiments of the layout-preserved text generation method may transform the PDF (X, Y) document space into the text file grid space while preserving a similar global view of the text and layout from the PDF (X, Y) document space. This transformation may include determining a base width and height size per grid that may produce accurate layout in the text output from the PDF input. Embodiments may produce more accurate layout preserved text when compared to output produced by conventional text extraction methods.

Embodiments of the layout-preserved text generation method as described herein may, for example, be applied to augment methods for reading-order text extraction such as described in U.S. patent application Ser. No. 12/130,607 entitled “EXTRACTING READING ORDER TEXT AND SEMANTIC ENTITIES” whose inventors are Walter Chang and Eunyee Koh, the content of which is incorporated by reference herein in its entirety.

While embodiments are described as being applied to the extraction of text from PDF documents, embodiments may be adapted for use with other document formats including other document formats that store text in a similar manner to PDF. In addition, while embodiments are described as being applied to the extraction of text from documents, embodiments may be adapted for use in extracting other document elements than text.

Some embodiments may include a means for obtaining text and other information from a PDF document and a means for transforming the text into a layout-preserved text document. For example, a toolkit, application, or library may include a PDF document parsing module for parsing PDF documents to obtain text and other information from the PDF documents and a transformation module for transforming the text into a layout-preserved text document. Alternatively, some embodiments may provide a single module that performs both the PDF document parsing and the transformation. The module(s) may in some embodiments be implemented by a computer-readable storage medium and one or more processors (e.g., CPUs) of a computing apparatus. An example computer system in which embodiments of the module(s) may be implemented is illustrated inFIG. 10. The computer-readable storage medium may store program instructions executable by the one or more processors to cause the computing apparatus to perform PDF document parsing to obtain text and other information from a PDF document and transformation of the text to generate a layout-preserved text document. Other embodiments of the module(s) may be at least partially implemented by hardware circuitry and/or firmware stored, for example, in a non-volatile memory. Embodiments of the PDF document parsing module, embodiments of a transformation module, or embodiments of a single module that performs both PDF document parsing and transformation, may be implemented, for example, as stand-alone applications, modules in other applications, modules in libraries, modules in toolkits, and so on.

FIG. 1is a block diagram that illustrates components of and dataflow in a layout-preserved text generation method according to some embodiments. A PDF document100is input to an implementation of the layout-preserved text generation method110. In some embodiments, the layout-preserved text generation method110may be implemented as or by a PDF document parsing module112and a transformation module120. The PDF document parsing module112extracts or reads information from the PDF document and provides the information to the transformation module120. This information may include, but is not limited to, one or more text elements114, and bounding box, or spatial, information116for the text elements. In some embodiments, font information118for the text elements may also be read or extracted. A text element114may be a single character, a string of characters, a word, a phrase, a sentence, or in general any string of one or more characters. Generally, however, a text element114may be the content of one line or portion of one line in the PDF document100. The characters in a text element114may include any displayable character, including alphanumeric characters, symbols, punctuation marks, and spaces. See, for example,FIG. 4A, in which “Example text 1,” “Example text 2,” and “Example text 3” are shown as three illustrative text elements114in PDF document100. While examples provided herein show English words using the conventional English alphabet/character set, embodiments may be applied to documents including other alphabets, writing systems, or symbol sets, such as Hebrew, Arabic, Greek, Cyrillic, Kanji, Chinese, mathematical expressions, and so on.

Spatial information116indicates the PDF document (X,Y) spatial information for corresponding text elements114. See, for example,FIG. 4A, in which (X1,Y1), (X2,Y2), and (X3,Y3) are the spatial coordinates of the top, left corner of bounding boxes for corresponding text elements “Example text 1,” “Example text 2,” and “Example text 3” in the (X,Y) space of PDF document100.

Font information118may include font style, font size, and other font information for corresponding text elements114. WhileFIG. 4Adoes not explicitly show font information118for the text elements114, note that “Example text 1,” “Example text 2,” and “Example text 3” are each shown in a different font size or font style: “Example text 1” is shown in Arial font, size 12; “Example text 2” is shown in Arial font, size 14; and “Example text 3” is shown in Times New Roman font, size 18.

Transformation module120receives the text elements114, spatial, information116, and possibly font information118from PDF document parsing module112and applies a text transformation method as described herein to generate a layout-preserved text document130from the text according to the spatial and font information. In some embodiments, rather than receiving font information118from PDF document parsing module112, the transformation module may instead read the font information directly from the PDF document100. Text document130may, for example, be stored to a local or network storage medium140, such as system memory, a local or network disk drive or other storage system, DVD, CD, etc. Instead, or in addition, text document130may be displayed to a display device150, or provided to one or more other modules160for additional processing.

FIG. 2is a high-level flowchart of a layout-preserved text generation method according to some embodiments. As indicated at200, a PDF document is obtained. As indicated at202, text and spatial information, and possibly other information such as font information may be obtained from the PDF document. As indicated at204, the extracted text is transformed according to the spatial and font information to generate a layout-preserved text document.

A PDF document may include more than one page. In some embodiments, elements202and204ofFIG. 2may be performed for each page in an input PDF document.

FIG. 3is a flowchart of a method for transforming text from a PDF document according to spatial and font information of the PDF document to generate a layout-preserved text document, according to some embodiments.FIG. 3expands on element204ofFIG. 2, and represents a method that may be implemented by embodiments of a transformation module120as illustrated inFIG. 1.

As indicated at300, base width and height values for the text document may be determined from the text and font information. For the purpose of this document, the base width and height values may be designated as (Wb, Hb). If the PDF document uses the same font style and size across the entire document, the average width and height values of this font may be determined and used as (Wb, Hb). In some embodiments, the average width value of the font may be calculated as the average of the widths of all the characters (a-z, A-Z, etc.) in the character set of the particular font. The average height value may be similarly calculated, or determined using some other method. In various embodiments, other methods for obtaining the average width and height values may be used, and other values than the average width and height of the font may be used for (Wb, Hb).

If the PDF document includes text elements in two or more different font styles and/or different font sizes, in some embodiments, the smallest font style/size may be selected and used to determine (Wb, Hb) for the text document. As an example, inFIG. 4A, “Example text 1” is shown in Arial font, size 12; “Example text 2” is shown in Arial font, size 14; and “Example text 3” is shown in Times New Roman font, size 18. Thus, in this example, the font used for “Example text 1” may be used to determine (Wb, Hb).

A PDF document may include more than one page. In some embodiments, (Wb, Hb) may be determined separately for each page. In these embodiments, the method may find the font styles and sizes used on a current page and select the smallest font style and size that has been used on the page. The smallest font style/size may then be used in determining (Wb, Hb) for the page. Other methods may be used to determine (Wb, Hb) for documents or pages of documents in some embodiments.

As indicated at302, a next text element to be processed may be obtained. A text element may be a single character, a string of characters, a word, a phrase, a sentence, or in general any string of one or more characters. Generally, however, a text element may be the content of one line or portion of one line in the PDF document. The characters in a text element may include any displayable character, including alphanumeric characters, symbols, punctuation marks, and spaces. See, for example,FIG. 4A, in which “Example text 1,” “Example text 2,” and “Example text 3” are shown as three illustrative text elements114in PDF document100.

As indicated at304, a space and line value (SN, LN) may be calculated for the text element in the text document from the base width and height values (Wb, Hb) and the spatial information corresponding to the text element. In some embodiments, to calculate (SN, LN) for a text element N, the following formulas may be used:
SN=XN/Wb
LN=YN/Hb
where (XN, YN) are the coordinates of the text element N in the (X, Y) space of the PDF document, (Wb, Hb) are the base width and height being used for the transformation, and (SN, LN) are the calculated spacing and newline values for the text element in the grid space of the layout-preserved text document.

As indicated at306, the text from the text element may be written to the output text document according to the space and line values (SN, LN) corresponding to the text element to thus preserve the layout represented in the input PDF document. SeeFIGS. 4A through 4Dfor an example of writing text elements to a layout-preserved text document.

At308, the method determines if there are more text elements to be processed. If there are more text elements to be processed, then the method returns to302to begin processing the next text element. If there are no more text elements to be processed, then the method is done. Note that, in some embodiments, elements300through308may be performed for each page in the PDF document if the PDF document is a multi-page document. Thus, in these embodiments, if there are more pages to be processed, then the method returns to element300to begin processing the next page.

In some embodiments, the text content of all of the text elements may be written to the text document in the font type and size that corresponds to (Wb, Hb). In other words, the font type and size used to calculate (Wb, Hb) may be used to write all the text to the text document, or to the current page of the text document if the PDF document includes multiple pages and the pages are being processed separately. Thus, in these embodiments, while the page layout is preserved, font characteristics may not be preserved for at least some text elements.

FIGS. 4A through 4Dillustrate determining spaces and lines for example text elements in an example PDF document from the calculated (Wb, Hb) values and the spatial information corresponding to the text elements, according to some embodiments.FIG. 4Ashows an example input PDF document100. InFIG. 4A, “Example text 1,” “Example text 2,” and “Example text 3” are shown as three illustrative text elements in PDF document100. (X1,Y1), (X2,Y2), and (X3,Y3) are the spatial coordinates of the top, left corner of bounding boxes for the corresponding text elements “Example text 1,” “Example text 2,” and “Example text 3” in the (X,Y) space of PDF document100. These (X, Y) values may be obtained from the PDF document, or alternatively may be determined from other spatial information, such as bounding box coordinates, obtained from the PDF document.

FIGS. 4B through 4Dshow an example layout-preserved text document120being generated according to the text transformation method from the example PDF input document100ofFIG. 4A, and illustrate a method that may be used in some embodiments to calculate the space and line values (SN, LN) for each text element to be written to the text document120. In some embodiments, the text elements obtained from the PDF document100may be processed and written to the layout-preserved text document120sequentially according to respective spatial information obtained from the PDF document, from the top or beginning of the PDF document100downward, and from the left of the PDF document100to the right.FIGS. 4B through 4Dshow the sequential processing and writing of the text elements from the top of the document. Other embodiments may process the text elements according to other orders or methods.

In some embodiments, to calculate (SN, LN) for a text element N, the following formulas may be used:
SN=XNWb
LN=YN/Hb
where (XN, YN) are the coordinates of the text element N in the (X, Y) space of PDF document100, (Wb, Hb) are the base width and height being used for the transformation, and (SN, LN) are the calculated spacing and newline values for the text element in the grid space of the layout-preserved text document120.

InFIG. 4B, (S1, L1) are calculated for the text element “Example text 1” as:
S1=X1/Wb
L1=Y1/Hb
“Example text 1” is then written to the text document120at location (S1, L1). InFIG. 4C, (S2, L2) are calculated for the text element “Example text 2” as:
S2=X2/Wb
L2=Y2/Hb
“Example text 2” is then written to the text document120at location (S2, L2). InFIG. 4D, (S3, L3) are calculated for the text element “Example text 3” as:
S3=X3/Wb
L3=Y3/Hb
“Example text 3” is then written to the text document120at location (S3, L3).

In some embodiments, the text content of all of the text elements is written to the text document in the font type and size that corresponds to (Wb, Hb). In other words, the font type and size used to calculate (Wb, Hb) is used to write all the text to the text document120. Thus, in these embodiments, while the page layout is preserved, font characteristics may not be preserved for at least some text elements.

Processing Columnar Data

Some PDF documents may include two or more columns that include text elements. See, for example,FIGS. 6A and 8A. In some embodiments, columnar text may be processed by the method illustrated inFIG. 3to determine the location in the text document at which the columnar text is to be written. However, in practice, calculating the spacing for the columns according to the method ofFIG. 3may not properly space the columns; for example, successive columns may be slightly misaligned. Therefore, in some embodiments, a different calculation may be used to determine the spacing between columns of text.

FIG. 5is a flowchart of a method for transforming text from a PDF document that may include columns according to spatial and font information of the PDF document to generate a layout-preserved text document, according to some embodiments.

FIG. 5expands on element204ofFIG. 2, and represents a method that may be implemented by embodiments of a transformation module120as illustrated inFIG. 1.FIG. 5differs fromFIG. 3in that columnar data are detected and the spacing between columns (referred to as CS) is calculated differently than the calculation for SN, and CSis used to horizontally position columnar text elements in the layout-preserved text document instead of SN. Note that SNmay be used to horizontally position the text elements in the first column, and CS, calculated separately for each text element may be used in horizontally positioning text elements in subsequent columns. Further, LNmay be calculated for each text element as inFIG. 3and used to position the respective text elements vertically.

As indicated at400, base width and height values for the text document may be determined from the text and font information. For the purpose of this document, the base width and height values may be designated as (Wb, Hb). If the PDF document uses the same font style and size across the entire document, the average width and height value of this font may be determined and used as (Wb, Hb). In some embodiments, the average width value of the font may be calculated as the average of the widths of all the characters (a-z, A-Z, etc.) in the character set of the particular font. The average height value may be similarly calculated, or determined using some other method. In various embodiments, other methods for obtaining the average width and height values may be used, and other values than the average width and height of the fond may be used for (Wb, Hb). If the PDF document includes text elements in two or more different font styles and/or different font sizes, in some embodiments, the smallest font style/size may be selected and used to determine (Wb, Hb) for the text document. In some embodiments, (Wb, Hb) may be determined separately for each page of a multi-page document.

As indicated at402, a next text element to be processed may be obtained. See, for example,FIG. 6A, in which “Example text 4” and “Example text 5” are shown as illustrative text elements in PDF document100.

As indicated at404, a check may be made to determine if the current text element is located in a column after the previously processed text element. Various methods may be used to determine if a text element is in a column after a previously processed text element. For example, in some embodiments, the (X, Y) spatial information for the text elements may be compared. If the Y values for the text elements are the same or within a specified threshold, then this may indicate that the text elements are (or begin) at the same or approximately the same vertical position, and thus it may be determined that the current text element is to be processed as columnar data.

At404, if it is determined that the text element is not located in a column after the previously processed text element, then the text element may be processed as indicated at406and408ofFIG. 5. For example, as shown inFIGS. 6A and 6B, “Example text 4” is not located in a column after previously processed data, and thus may be processed as follows. As indicated at406, a space and line value (SN, LN) may be calculated for the text element in the text document from the base width and height values (Wb, Hb) and the spatial information corresponding to the text element. In some embodiments, to calculate (SN, LN) for a text element N, the following formulas may be used:
SN=XN/Wb
LN=YN/Hb
where (XN, YN) are the coordinates of the text element N in the (X, Y) space of the PDF document, (Wb, Hb) are the base width and height being used for the transformation, and (SN, LN) are the calculated spacing and newline values for the text element in the grid space of the layout-preserved text document.

As indicated at408, the text from the text element may be written to the output text document according to the space and line values (SN, LN) corresponding to the text element to thus preserve the layout represented in the input PDF document. SeeFIGS. 6A and 6Bfor an example of writing a text element to a layout-preserved text document according to406and408.

At404, if it is determined that the text element is located in a column after the previously processed text element, then the text element may be processed as indicated at410and412ofFIG. 5. For example, as shown inFIGS. 6A through 6C, “Example text 5” is located in a column after previously processed data (“Example text 4”), and thus may be processed as follows.

As indicated at410, the spacing of the current text element in this column from the text in the preceding column may be calculated. This spacing may be designated as CS. In some embodiments, the calculation to find a value for (CS) for the current text element may be performed as follows. Refer toFIG. 6Cfor an illustrative example:Get a value for I. In some embodiments, to calculate I, (SN, LN) may be calculated for the current text element, for example as described above in reference to element406. Thus, the calculated value for SN(XN/Wb) may be used as the value for I.Get a value for J. In some embodiments, J may be calculated as the total number of character spaces used so far on this line, or as the total number of character spaces on the current line up to and including the last character of the previously written text element. For example, referring toFIGS. 6B and 6C, J is calculated as S4(calculated for the text element “Example text 4”) plus the number of characters in the text element “Example text 4” (14).Calculate CS. In some embodiments, CS=I−J.

As indicated at412, the text from the current text element may be written to the output text document according to the calculated column spacing CSnand the LNvalue calculated for this text element to thus preserve the layout represented in the input PDF document. In some embodiments, the current text element may be written to the text document at CSnspaces from the end of the previously written text element on this line, with the vertical spacing (newlines) determined by LN. SeeFIGS. 6A,6C,7A, and7B for examples of writing columnar text elements from a PDF document to a layout-preserved text document according to410and412ofFIG. 5.

At414ofFIG. 5, the method determines if there are more text elements to be processed. If there are more text elements to be processed, then the method returns to402to begin processing the next text element. If there are no more text elements to be processed, then the method is done. Note that, in some embodiments, elements400through412may be performed for each page in the PDF document if the PDF document is a multi-page document. Thus, in these embodiments, if there are more pages to be processed, then the method returns to element400to begin processing the next page.

FIGS. 6A through 6Cillustrate determining spacing for columns of text in an example PDF document according to some embodiments.FIG. 6Ashows an example input PDF document100. InFIG. 6A, “Example text 4” and “Example text 5” are shown as illustrative text elements formatted in two columns in PDF document100. (X4,Y4), and (X5,Y5) are the spatial coordinates of the top, left corner of bounding boxes for the corresponding text elements in the (X,Y) space of PDF document100. These (X,Y) values may be obtained from the PDF document, or alternatively may be determined from other spatial information obtained from the PDF document.

FIGS. 6B and 6Cshow an example layout-preserved text document120being generated according to the text transformation method from the example PDF input document100ofFIG. 6A, and illustrate a method that may be used in some embodiments to calculate the horizontal and vertical location for each text element to be written to the text document120. In some embodiments, the text elements from the PDF document100may be processed and written to the layout-preserved text document120sequentially according to respective spatial information from the PDF document, from the top or beginning of the PDF document100downward, and from the left of the PDF document100to the right.FIGS. 6B and 6Cshow the sequential processing and writing of the text elements from the top of the document. Other embodiments may process the text elements according to other orders or methods.

FIG. 6Billustrates the calculations for determining a location for writing the first text element on a line, “Example text 4”, which is in a first column of the line to be processed. In some embodiments, when processing the text elements, a determination may be made as to whether a current text element is in a column after a previous text element on the line. “Example text 4” appears in the first column, and so there is no previous text element in a previous column on the line. Therefore, the location for “Example text 4” may be determined as follows:
S4=X4/Wb
L4=Y4/Hb
where (X4, Y4) are the coordinates of the text element “Example text 4” in the (X, Y) space of PDF document100, (Wb, Hb) are the base width and height being used for the transformation, and (S4, L4) are the calculated spacing and newline values for the text element “Example text 4” in the grid space of the layout-preserved text document120.

FIG. 6Cillustrates the calculations for determining a location for writing a text element that appears in a column after a text element in a previous column. The text element “Example text 5” is in a second column of the line to be processed. Instead of calculating the location as indicated above for the text element “Example text 4”, the spacing of “Example text 5” in this column from “Example text 4” in the first column (CS) may be calculated. In some embodiments, this calculation may be performed as follows:Get a value for I. In some embodiments, to calculate I, (S5, L5) may be calculated for “Example text 5”. The calculated value for S5may be used as the value for I.Get a value for J. In some embodiments, J may be calculated as the total number of character spaces used so far on this line, or as the total number of character spaces on the current line up to and including the last character of the previously written text element. For example, J may be calculated as S4(calculated for the text element “Example text 4”) plus the number of characters in the text element “Example text 4”.Calculate CS. In some embodiments, CS=I−J.

There may be more than two columns in a document. A similar calculation may be performed for additional columns to find the column spacing CSnbetween columns.FIGS. 7A and 7Billustrate determining spacing for multiple columns of text in an example PDF document according to some embodiments.FIG. 7Ashows an example input PDF document100that includes three columns. InFIG. 7A, “Example text 4”, “Example text 5”, and “Example text 6” are shown as example text elements formatted in columns in PDF document100. (X4,Y4), (X5,Y5), and (X6,Y6) are the spatial coordinates of the top, left corner of bounding boxes for the corresponding text elements in the (X,Y) space of PDF document100. Spacing of the first two columns inFIGS. 7A-7Bmay be calculated as shown inFIGS. 6A through 6C. The calculated spacing between the first two columns is represented as CS1inFIG. 7B, and I and J used in calculating CS1are represented as h and JI. The spacing between the second and third columns (CS2) may be calculated as follows:Get a value for I2. In some embodiments, to calculate I2, (S6, L6) may be calculated for the current text element (“Example text 6”), and the value for S6may be used as the value for I2.Get a value for J2. In some embodiments, J2may be calculated as the total number of character spaces used so far on this line, or as the total number of character spaces on the current line up to and including the last character of the previously written text element. Referring toFIG. 7B, J2may be calculated as I1(S5) plus the number of characters in the text element “Example text 5”. Alternatively, J2may be calculated as (J1+CS1) plus the number of characters in the text element “Example text 5”.Calculate CS2as (I2−J2).

The above calculations for column spacing may be expressed more generally as:
CSn=IN−JN
which may be more fully expressed as:
CSn=SN−(SN-1+NumChars(N−1))
where CSnrepresents the column spacing being calculated for the current column, SNis the spacing calculated for the current text element according to the (X,Y) spatial information from the PDF document, SN-1is the spacing calculated for the previous text element according to the (X,Y) spatial information from the PDF document, and NumChars(N−1) represents the number of characters in the previous text element. Again, as an alternative, (JN-1+CS(n-1)) may be used in the calculation instead of SN-1.

FIGS. 8A and 8Bshow an example of generating a layout-preserved text document from an input PDF document according to some embodiments.FIG. 8Ashows an example first page of a script formatted according to a conventional “movie script” standard layout as the page appears in a PDF document. An implementation of an embodiment of a layout-preserved text generation method as described herein, for example implemented as illustrated inFIG. 1, may be used to generate a layout-preserved text document from the input PDF document ofFIG. 8A.FIG. 8Bshows an example output first page of the layout-preserved text document generated from the input PDF document ofFIG. 8Aby an implementation of an embodiment of the layout-preserved text generation method. Note that the layout/formatting of the page is preserved, thus preserving metadata indicated by the “movie script” standard layout.

FIGS. 9A and 9Bshow an example of generating a layout-preserved text document from an input PDF document that includes columnar data, according to some embodiments.FIG. 9Ashows a page of an example PDF document that includes two columns. Note that, in the PDF document, the columns include both text and images, and that other elements (e.g., a vertical line separating the columns) are included on the page. Further note that different types of text elements, e.g. a Title, Subtitle, Footnote, column headings, and column content, are included on the page. Further note that different font styles and/or sizes are used for different text elements.

An implementation of an embodiment of a layout-preserved text generation method as described herein, for example implemented as illustrated inFIG. 1, may be used to generate a layout-preserved text document from the input PDF document ofFIG. 9A.FIG. 9Bshows an example output layout-preserved text document generated from the input PDF document ofFIG. 9Aby an implementation of an embodiment of the layout-preserved text generation method.

The PDF document ofFIG. 9Aincludes text elements in different font styles and sizes. In some embodiments, the smallest font style/size is determined and used to determine the (Wb, Hb) values to be used in generating the text document. As an example, inFIG. 9A, “Footnote” is in Arial font, size 9, which is determined as the smallest font size, and (Wb, Hb) is determined from Arial font, size 9. InFIG. 9B, the font used for the text written to the text document is Arial font, size 9.

In some embodiments, only text elements are processed from the input PDF document and written to the layout-preserved text document by the layout-preserved text generation method. Thus, images and other non-text content that appear in the example PDF document ofFIG. 9Aare absent from the output layout-preserved text document ofFIG. 9B. Note, however, that the text elements inFIG. 9Bare appropriately spaced so that blank spaces appear where the non-text elements are located in the PDF document. In some embodiments, methods or techniques may be applied to copy non-text elements from the input PDF document to the output document.

Example System

Various components of embodiments of a layout-preserved text generation method as described herein may be executed on one or more computer systems, which may interact with various other devices. One such computer system is illustrated byFIG. 10. In the illustrated embodiment, computer system700includes one or more processors710coupled to a system memory720via an input/output (I/O) interface730. Computer system700further includes a network interface740coupled to I/O interface730, and one or more input/output devices750, such as cursor control device760, keyboard770, audio device790, and display(s)780. In some embodiments, it is contemplated that embodiments may be implemented using a single instance of computer system700, while in other embodiments multiple such systems, or multiple nodes making up computer system700, may be configured to host different portions or instances of embodiments. For example, in one embodiment some elements may be implemented via one or more nodes of computer system700that are distinct from those nodes implementing other elements.

In various embodiments, computer system700may be a uniprocessor system including one processor710, or a multiprocessor system including several processors710(e.g., two, four, eight, or another suitable number). Processors710may be any suitable processor capable of executing instructions. For example, in various embodiments, processors710may be general-purpose or embedded processors implementing any of a variety of instruction set architectures (ISAs), such as the x86, PowerPC, SPARC, or MIPS ISAs, or any other suitable ISA. In multiprocessor systems, each of processors710may commonly, but not necessarily, implement the same ISA.

System memory720may be configured to store program instructions and/or data accessible by processor710. In various embodiments, system memory720may be implemented using any suitable memory technology, such as static random access memory (SRAM), synchronous dynamic RAM (SDRAM), nonvolatile/Flash-type memory, or any other type of memory. In the illustrated embodiment, program instructions and data implementing desired functions, such as those described above for a layout-preserved text generation method, are shown stored within system memory720as program instructions725and data storage735, respectively. In other embodiments, program instructions and/or data may be received, sent or stored upon different types of computer-accessible media or on similar media separate from system memory720or computer system700. Generally speaking, a computer-accessible medium may include storage media or memory media such as magnetic or optical media, e.g., disk or CD/DVD-ROM coupled to computer system700via I/O interface730. Program instructions and data stored via a computer-accessible medium may be transmitted by transmission media or signals such as electrical, electromagnetic, or digital signals, which may be conveyed via a communication medium such as a network and/or a wireless link, such as may be implemented via network interface740.

In one embodiment, I/O interface730may be configured to coordinate I/O traffic between processor710, system memory720, and any peripheral devices in the device, including network interface740or other peripheral interfaces, such as input/output devices750. In some embodiments, I/O interface730may perform any necessary protocol, timing or other data transformations to convert data signals from one component (e.g., system memory720) into a format suitable for use by another component (e.g., processor710). In some embodiments, I/O interface730may include support for devices attached through various types of peripheral buses, such as a variant of the Peripheral Component Interconnect (PCI) bus standard or the Universal Serial Bus (USB) standard, for example. In some embodiments, the function of I/O interface730may be split into two or more separate components, such as a north bridge and a south bridge, for example. In addition, in some embodiments some or all of the functionality of I/O interface730, such as an interface to system memory720, may be incorporated directly into processor710.

Input/output devices750may, in some embodiments, include one or more display terminals, keyboards, keypads, touchpads, scanning devices, voice or optical recognition devices, or any other devices suitable for entering or retrieving data by one or more computer system700. Multiple input/output devices750may be present in computer system700or may be distributed on various nodes of computer system700. In some embodiments, similar input/output devices may be separate from computer system700and may interact with one or more nodes of computer system700through a wired or wireless connection, such as over network interface740.

As shown inFIG. 10, memory720may include program instructions725, configured to implement embodiments of a layout-preserved text generation method as described herein, and data storage735, comprising various data accessible by program instructions725. In one embodiment, program instructions725may include software elements of a layout-preserved text generation method illustrated in the above Figures. Data storage735may include data that may be used in embodiments, for example input PDF documents or output layout-preserved text documents. In other embodiments, other or different software elements and/or data may be included.

CONCLUSION

The various methods as illustrated in the Figures and described herein represent examples of embodiments of methods. The methods may be implemented in software, hardware, or a combination thereof. The order of method may be changed, and various elements may be added, reordered, combined, omitted, modified, etc.