Script-agnostic text reflow for document images

• US 8,542,926 B2
• Filed: 11/19/2010
• Issued: 09/24/2013
• Est. Priority Date: 11/19/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Panjwani, Saurabh, Uppal, Abhinav
• Primary Examiner(s): Wang, Claire X
• Assistant Examiner(s): JAMES, THOMAS AIDEN
• Application Number:
  US12/950,598
• Publication Number:
  US 20120128249A1
• Time in Patent Office: 1,040 Days
• Field of Search: None
• US Class Current: 382/176
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

Script-agnostic text reflow technique embodiments are presented that generally reflow text found in an image of a document in a manner that functions across multiple scripts, multiple fonts of a script and multiple languages using the same script. This generally involves segmenting regions of text in a document image into individual words and doing this without relying on any script-specific characteristics or requiring any form of character recognition. While segmenting text, the possible presence of accents, diacritics and punctuation marks is considered.

Claims

1. A computer-implemented process for reflowing a binarized region of text from a document image into a specified-width display area on an electronic display in a script-agnostic manner, comprising:

using a computer to perform the following process actions;

segmenting the text region into candidate lines of text, said candidate lines of text comprising at least one line of text comprising substantially only accent or diacritic marks, or both;

merging candidate lines of text comprising substantially only accent or diacritic marks, or both, into the closest adjacent candidate text line;

designating each remaining candidate text line as a final text line;

segmenting each final text line into candidate text words;

identifying inter-word punctuation and diacritic marks, if any, and merging each identified mark into the closest adjacent candidate text word;

designating final text words based on the remaining candidate text words;

segmenting the final text lines into paragraphs; and

for each paragraph, reflowing the final text words found therein so as to fit into said specified-width display area while maintaining the original sequential order.

2. The process of claim 1, wherein the text region comprises rows of pixels each pixel of which is either a black pixel or a white pixel, and wherein the process action of segmenting the text region into candidate text lines, comprises the actions of:

for each respective row of pixels in the text region, summing the number of black pixels to produce a horizontal black pixel profile for the text region;

establishing a horizontal black pixel threshold number based on the horizontal black pixel profile, said horizontal black pixel threshold number representing the number of black pixels below which a row of pixels is deemed to be a non-text row;

identifying candidate line boundary rows based on the horizontal black pixel profile, wherein a candidate line boundary row is a pixel row that may be the first row of pixels or may be the last row of pixels in a set of consecutive pixel rows comprising a line of text; and

identifying candidate text lines, wherein a candidate text line comprises a set of consecutive pixel rows bounded on the top and bottom respectively by one of the identified candidate line boundary rows and whose rows collectively exhibit a height and black pixel density indicative of text.

3. The process of claim 2, wherein the process action of identifying candidate line boundary rows, comprises the actions of:

finding local minima rows in the horizontal black-pixel profile of the text region; and

for each of the minima rows discovered,

determining if the number of black pixels in the minima row falls below the horizontal black pixel threshold number, and

whenever the number of black pixels in the minima row falls below the horizontal black pixel threshold number, designating the minima row as a boundary row.

4. The process of claim 2, wherein the process action of identifying candidate text lines, comprises the actions of:

for each pair of consecutive candidate line boundary rows,

determining if a set of consecutive rows between and including the pair of consecutive candidate line boundary rows has an average black pixel count that exceeds the horizontal black pixel threshold number, and

whenever the set of consecutive rows between and including the pair of consecutive candidate line boundary rows has an average black pixel count that exceeds the horizontal black pixel threshold number, designating the set of consecutive rows as a candidate line of text.

5. The process of claim 2, wherein the process action of merging candidate lines of text comprising substantially only accent or diacritic marks, or both, into the closest adjacent candidate text line, comprises the action of:

for each candidate text line,

determining if the text line has a height that is no more than a prescribed accent and diacritic threshold percentage of the height of the other text lines in the text region, and

whenever the candidate text line has a height that is no more than the prescribed accent and diacritic threshold percentage of the height of the other text line of the pair,

merging the candidate text line with the closest adjacent candidate text line by removing the candidate status of the candidate line boundary rows lying between them, and

re-designating the merged candidate text lines as a single candidate text line.

6. The process of claim 2, further comprising performing prior to performing the process action of merging candidate lines of text comprising substantially only accent or diacritic marks, or both, into the closest adjacent candidate text line, a process action of removing the candidate status from each candidate text line that is attributable to inter-line black pixel noise rather than to text.

7. The process of claim 6, wherein the process action of removing the candidate status from each candidate text line that is attributable to inter-line black pixel noise rather than to text, comprises the actions of:

for each of the candidate text lines;

determining if the candidate text line has a height that is no more than a prescribed noise threshold percentage of the average line height of the other text lines in the text region that the candidate text line belongs to, and

whenever it is found that the candidate text line has a height that is no more than a prescribed noise threshold percentage of the average line height of the other text lines in the text region that the candidate text line belongs to,

designating the candidate text line to be a noise line, and

removing the candidate status from the candidate text line boundary rows flanking the candidate text line and the candidate status from the candidate text line.

8. The process of claim 2, further comprising, prior to performing the process action of designating each remaining candidate text lines as a final text line, performing the process actions of:

ascertaining the height of the tallest final text line in the text region, and

expanding the height of each of the final lines in the text region that are shorter than the tallest final text line equally in both directions until their height equals the tallest final text line.

9. The process of claim 1, wherein the text region comprises columns of pixels each pixel of which is either a black pixel or a white pixel, and wherein the process action of segmenting each final text line into candidate text words, comprises the actions of:

for each final text line in the text region,

respectively summing the number of black pixels in each column of pixels in the final text line to produce a vertical black pixel profile for the final text line,

identifying candidate word boundary columns based on the vertical black pixel profile for the text line, wherein a candidate word boundary column is a pixel column that can be the first column or can be the last column in a set of consecutive pixel columns comprising a text word and which exhibits a zero black pixel density, and

removing the candidate designation from each candidate word boundary column that is attributable to inter-word black pixel noise rather than text.

10. The process of claim 9, further comprising, after performing the process action of designating final text words based on the remaining candidate text words, performing the actions of:

for each final text word in each final text line,

determining if a number of consecutive pixel rows residing immediately above the word under consideration that have black pixels therein exhibit a height that exceeds a prescribed noise threshold percentage of the average line height of the other text lines in the text region under consideration,

whenever it is determined the prescribed noise threshold percentage is exceeded above the word, expanding an upper line boundary row of the final text line under consideration vertically upward to include said number of consecutive pixel rows residing above the selected word,

determining if a number of consecutive pixel rows residing immediately below the word under consideration that have black pixels therein exhibit a height that exceeds the prescribed noise threshold percentage of the average line height of the other text lines in the text region under consideration, and

whenever it is determined the prescribed noise threshold percentage is exceeded below the word, expanding a lower line boundary row of the final text line under consideration vertically downward to include said number of consecutive pixel rows residing below the selected word.

11. The process of claim 9, wherein the process action of removing the candidate designation from each candidate word boundary column that is attributable to inter-word black pixel noise rather than text, comprises the actions of:

for each column,

applying a weighting factor to the black pixel count of the column under consideration and that of each neighboring column on both sides up to a prescribed number of columns, wherein the value of the weighting factor is dependent on how far the column is from the column under consideration,

summing the weighted black pixel counts of the column under consideration and each neighboring column on both sides up to the prescribed number of columns,

dividing the summed weighted black pixel counts by the number of columns involved in the summing action to establish a smoothed black pixel count for the column under consideration,

ascertaining if the smoothed black pixel count computed for the column under consideration exceeds a prescribed smoothed column noise threshold, and

whenever the smoothed black pixel count computed for the column under consideration does not exceed the prescribed smoothed column noise threshold, deeming that column to be part of a space between words and whenever that column is a candidate word boundary column, removing the candidate designation from the column.

12. The process of claim 11, wherein the process action of applying a weighting factor to the black pixel count of the column under consideration and that of each neighboring column on both sides up to a prescribed number of columns, comprises the actions of:

applying a weighting factor of 1.0 to the column under consideration and that of a first prescribed number of neighboring columns on both sides of the column under consideration;

for a second prescribed number of neighboring columns lying outside the first prescribed number of neighboring columns on a first side of the column under consideration, applying a weighting factor to each of the second prescribed number of neighboring columns which decays linearly the further away the neighboring column is from the column under consideration; and

for the second prescribed number of neighboring columns lying outside the first prescribed number of neighboring columns on a second side of the column under consideration, applying a weighting factor to each of the second prescribed number of neighboring columns which decays linearly the further away the neighboring column is from the column under consideration.

13. The process of claim 9, wherein the process action of identifying inter-word punctuation and diacritic marks, if any, and merging each identified mark into the closest adjacent candidate text word, comprises the action of:

for each candidate text word,

ascertaining if the candidate text word exhibits a vertical black pixel distribution pattern with respect to a centrally-located pixel row of the candidate text word that is indicative of it being a punctuation or diacritic mark,

whenever the candidate text word is found to exhibit a vertical black pixel distribution pattern with respect to the centrally-located pixel row of the candidate text word that is indicative of it being a punctuation or diacritic mark,

designating the candidate text word to be a mergeable mark,

identifying the candidate text word that is physically closest to the mergeable mark, and

removing the candidate designation from each of the candidate word boundary columns located between the identified candidate text word, which is physically closest to the mergeable mark, and the mergeable mark, to create a single candidate text word comprising the identified candidate text word and the mergeable mark.

14. The process of claim 9, wherein the process action of designating final text words based on the remaining candidate text words, comprises the actions of:

identifying the spaces between the remaining candidate text words;

clustering the identified spaces by width into one or two groups;

whenever the identified spaces are clustered into two groups, designating the spaces in the cluster of spaces exhibiting larger widths than the spaces in the other cluster to be inter-word spaces and the spaces in the cluster of spaces exhibiting smaller widths than the spaces in the other cluster to be intra-word spaces;

whenever the identified spaces are clustered into one group, designating the spaces in the cluster to be inter-word spaces;

designating the candidate word boundary columns adjacent each end of each of the designated inter-word spaces as final word boundary columns and remove the candidate designation from all other candidate word boundary columns; and

designating each set of consecutive pixel columns that are bounded at each end by a final word boundary column, and which are not designated as an inter-word space, as a final text word.

15. The process of claim 14, further comprising the process actions of:

(a) identifying the widest intra-word space and narrowest inter-word space in each respective text line in the text region under consideration;

(b) for each final text line,

(i) determining if the narrowest inter-word space found in the final text line is greater than the width of the widest intra-word space across all the final text lines,

(ii) whenever it is determined that the narrowest inter-word space found in the final text line is not greater than the width of the widest intra-word space across all the final text lines,

(iii) re-classifying the currently identified narrowest inter-word space found in the final text line under consideration as an intra-word space, and

(iv) identifying the inter-word space in the final text line under consideration that is currently the narrowest, and

(v) repeating actions b(i) through b(iv) until it is determined the currently identified narrowest inter-word space found in the final text line is greater than the width of the widest intra-word space across all the final text lines,

(vi) determining if the widest intra-word space found in the final text line is less than the width of the narrowest inter-word space across all the final text lines,

(vii) whenever it is determined that the widest intra-word space found in the final text line under consideration is not less than the width of the narrowest inter-word space across all the final text lines,

(viii) re-classifying the currently identified widest intra-word space found in the final text line under consideration as an inter-word space, and

(ix) identifying the intra-word space in the final text line under consideration that is currently the widest, and

(x) repeating actions b(vi) through b(ix) until it is determined the currently identified widest intra-word space found in the final text line is less than the width of the narrowest inter-word space across all the final text lines.

16. The process of claim 1, wherein an indentation space exists either at the left or right side of a text line to indicate the start of a new paragraph having a length of two or more text lines, and wherein the process action of segmenting the final text lines into paragraphs, comprises the actions of:

starting with the first final text line and proceeding in a downward vertical order, ascertaining if an indentation space exists either at the left or right side of the final text line under consideration which has a width exceeding a prescribed indentation threshold, wherein an indentation space comprises a set of consecutive columns preceding the leftmost final text word in the final text line under consideration if at the left side of that line, and a set of consecutive columns following the rightmost final text word in the final text line under consideration if at the right side of that line,

whenever no indentation space is found, designating the entire text region as a paragraph,

whenever one or more indentation spaces are found, identifying if the first indentation space found was on the left or right side of a final text line,

whenever the first indentation space found was on the left side of a final text line,

designating that the text flows from left to right,

designating text lines, if any, preceding the text line where the first indentation space was found as a paragraph,

for each text line where an indentation space was found on the left side of a final text line, collectively designating that line and the final text lines following that line, up to the next final text line, if any, where an indentation space was found on the left side, as a paragraph,

whenever the first indentation space found was on the right side of a final text line,

designating that the text flows from right to left,

designating text lines, if any, preceding the text line where the first indentation space was found as a paragraph,

for each text line where an indentation space was found on the right side of a final text line, collectively designating that line and the final text lines following that line, up to the next final text line, if any, where an indentation space was found on the right side, as a paragraph.

17. The process of claim 1, wherein the process action of, for each paragraph, flowing the final text words found therein so as to fit into said specified-width display area while maintaining the original sequential order, comprises the actions of:

for each paragraph,

initiating a specified reflow procedure;

whenever one or more final text words are moved from one final text line to the next final text line during the reflow procedure, aligning the final text word or words being moved with the final text words in the final text line receiving the word or words being moved, said aligning comprising,

identifying the pixel row in the word or words being moved that exhibits the highest black pixel count among the pixel rows making up the final text line the word or words being moved come from,

identifying the pixel row in the final text line receiving the word or words being moved that exhibits the highest black pixel count among the pixel rows making up that final text line, and

vertically aligning the identified pixel row associated with the word or words being moved with the identified pixel row associated with the final text line receiving the word or words being moved.

18. A computer-implemented process for segmenting a binarized region of text from a document image in a script-agnostic manner, comprising:

using a computer to perform the following process actions;

segmenting the text region into candidate lines of text, said candidate lines of text comprising at least one line of text comprising substantially only accent or diacritic marks, or both;

merging candidate lines of text comprising substantially only accent or diacritic marks, or both, into the closest adjacent candidate text line;

designating each remaining candidate text lines as a final text line; and

segmenting each final text line into text words.

19. The process of claim 18, further comprising an action of identifying inter-word punctuation and diacritic marks and merging each identified mark into the closest adjacent candidate text word.

20. A computer-implemented process for reflowing a binarized region of text comprising black pixels representing text and white pixels representing non-text areas from a document image into a specified-width display area on an electronic display without the need for information about the script employed for the text, comprising:

using a computer to perform the following process actions;

segmenting the text region into candidate lines of text;

removing the candidate designation from each candidate text line that is attributable to inter-line black pixel noise rather than to text;

merging candidate lines of text comprising substantially only accent or diacritic marks, or both, into the closest adjacent candidate text line;

designating each remaining candidate text line as a final text line;

segmenting each final text line into candidate text words;

removing the candidate designation from each candidate text word that is attributable to inter-word black pixel noise rather than text;

identifying inter-word punctuation and diacritic marks, if any, and merging each identified mark into the closest adjacent candidate text word;

designating final text words based on the remaining candidate text words;

segmenting the final text lines into paragraphs; and

for each paragraph, reflowing the final text words found therein so as to fit into said specified-width display area while maintaining the original sequential order, wherein said reflowing comprises vertically aligning word or words being moved from one final text line to the next with the words associated with the final text line receiving the word or words being moved.