Alignment and reflow of displayed character images

• US 9,734,132 B1
• Filed: 12/20/2011
• Issued: 08/15/2017
• Est. Priority Date: 12/20/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kothandapani Shanmugasundaram, Satishkumar, Sankaranarayanan, Viswanath
• Primary Examiner(s): Paula, Cesar
• Assistant Examiner(s): Blackwell, James H
• Application Number:
  US13/332,088
• Time in Patent Office: 2,065 Days
• Field of Search: 715201, 715210, 715238, 715243, 715244-245, 715247, 715253, 715255-256, 715258, 715262, 715273, 715815, 715864, 382168, 382171, 382177-179, 382185-187, 382298, 345468, 345472, 358 111
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/109 Font handling; Temporal or kinetic typography
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion
• CPC Class Codes: G06V 30/1478 of characters or characters lines
• CPC Class Codes: G06V 30/287 of Kanji, Hiragana or Katakana characters
• CPC Class Codes: G06V 30/293 of characters other than Kanji, Hiragana or Katakana
• 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

Determination of an underlying grid structure that facilitates layout of East Asian text is disclosed. The underlying grid structure includes both a size of character frames and a size of a text block frame. The East Asian text may be obtained from a scan of printed material that has the text formatted according to layout conventions established by the publisher. The text may be reformatted to appear on a display of an electronic device in a manner similar to the formatting in the original scanned document. Reformatting may include reflowing the text in order to fit a greater or lesser number of characters on a line. The reflowing may maintain character spacing from the original document and follow formatting rules against locating certain characters at the start or end of a line.

Claims

1. A system comprising:

one or more processors;

computer-readable media coupled to the one or more processors;

a character spacing module, stored in the computer-readable media and executed by the one or more processors, configured to determine, from a page image of text, a character spacing including (i) a trailing edge character spacing of an end-of-line character of a first line, the trailing edge character spacing corresponding to a first spacing between a trailing edge of the end-of-line character and an end-of-line edge of a character frame associated with the end-of-line character and (ii) a leading edge character spacing of a start-of-line character of a next line subsequent to the first line, the leading edge character spacing corresponding to a second spacing between a leading edge of the start-of-line character and a start-of-line edge of a character frame associated with the start-of-line character, the trailing edge character spacing separate from the leading edge character spacing;

a character location module, stored in the computer-readable media and executed by the one or more processors, configured to identify characters that are not to be placed at a start of a line and characters that are not to be placed at an end of a line of text from the page image of text; and

an alignment and reflow module, stored in the computer-readable media and executed by the one or more processors, configured to generate an initial layout of the text for display on an electronic display that maintains the character spacing from the page image of text between the end-of-line character and the start-of-line character when displayed on a same line of text.

2. The system of claim 1, wherein the character spacing module is configured to determine horizontal offsets and vertical offsets of characters in the page image of text from centers of character frames surrounding the characters in the page image of text.

3. The system of claim 1 further comprising an optical character recognition module, stored in the computer-readable media and executed by the one or more processors, configured to convert a scan of text into the page image of text.

4. The system of claim 1, wherein the character location module is configured to:

identify locations to move the characters that are not to be placed at the start of the line from a line start or move the characters that are not to be placed at the end of the line from a line end; and

instruct the alignment and reflow module to generate a regenerated layout of the text when the initial layout places characters that are not to be placed at the start of the line at the line start or places characters that are not to be placed at the end of the line at the line end.

5. The system of claim 1 further comprising a line start and line end character alignment module, stored in the computer-readable media and executed by the one or more processors, configured to align centers of characters that occupy an initial position in a line with each other and align centers of characters that occupy a final position in a line with each other.

6. The system of claim 1, wherein the alignment and reflow module is configured to calculate a number of character frames to be included in a line of text based at least in part on dimensions of the electronic display and a level of zoom associated with the electronic display.

7. A computer-implemented method comprising:

under control of one or more computer systems configured with specific executable instructions,

determining a character frame size, the character frame size based at least in part on at least one distance between centers of at least two full-width characters;

calculating a first distance between a trailing edge of a final character in a line of characters and a trailing edge of a first character frame having the character frame size and surrounding the final character;

calculating a second distance between a leading edge of an initial character in a next line of characters and a leading edge of a second character frame having the character frame size and surrounding the initial character, wherein the first distance is different than the second distance; and

setting a spacing between the final character and the initial character as the sum of the first distance and the second distance for a layout in which the final character and the initial character are adjacent characters in a same line of characters.

8. The computer-implemented method of claim 7, further comprising determining an end-grid center line, wherein the end-grid center line passes through the final character and other final characters that occupy final positions of other lines and a location of the end-grid center line is based at least in part on locations of centers of the final character and the other final characters.

9. The computer-implemented method of claim 8, wherein a center of the first character frame surrounding the final character is aligned with the end-grid center line.

10. The computer-implemented method of claim 7, further comprising determining a start-grid center line, wherein the start-grid center line passes through the initial character and other initial characters that occupy initial positions of other lines and a location of the start-grid center line based at least in part on locations of centers of the initial character and the other initial characters.

11. The computer-implemented method of claim 10, wherein a center of the second character frame surrounding the initial character is aligned with the start-grid center line.

12. The computer-implemented method of claim 7, further comprising:

determining that the final character is a hanging punctuation character; and

aligning the first character frame surrounding the final character directly after a character frame surrounding a previous character in the same line as the final character.

13. The computer-implemented method of claim 12, wherein a center of the character frame surrounding the previous character is aligned with an end-grid center line, and wherein the end-grid center line passes through the previous character and other characters that occupy final positions of other lines and are not hanging punctuation.

14. The computer-implemented method of claim 7, further comprising generating a representation of the final character and the initial character adjacent to each other on the same line with spacing between the final character and the initial character as the sum of the first distance and the second distance.

15. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed on one or more processors, cause a computing device to perform acts comprising:

identifying a character at a start of a line of text as a character that is not to be placed at the start of the line;

determining if the character that is not to be placed at the start of a line is hanging punctuation that may be hanged beyond an edge of a text bock frame;

when the character that is not to be paced at the start of the line is the hanging punctuation, moving the hanging punctuation to a location directly following an end of a previous line of text that is beyond the edge of the text bock frame and adjusting spacing between characters in the line of text in response to the moving of the character that is not to be placed at the start of the line; and

when the character that is not to be paced at the start of the line is not the hanging punctuation, moving a final character of the previous line, of text to the start of the line of text and adjusting spacing between characters in the previous line of text based as least in part on moving the final character.

16. The one or more non-transitory computer-readable media of claim 15, wherein identifying a character at the start of the line of text as the character that is not placed at the start of the line is based at least in part on optical character recognition and a list of characters that are not placed at the start of the line.

17. The one or more non-transitory computer-readable media of claim 15, wherein when the character that is not placed at the start of the line is the hanging punctuation, the adjusting spacing between characters in the line of text comprises:

aligning a first character in the line of text with a start-grid center line,

aligning a last character in the line of text with an end-grid center line, and

distributing other characters in the line of text between the first character and the last character.

18. The one or more non-transitory computer-readable media of claim 15, wherein when the character that is not placed at the start of the line is not the hanging punctuation, the adjusting spacing between characters in the previous line of text comprises:

aligning a first character in the previous line of text with a start-grid center line,

aligning a last character in the previous line of text with an end-grid center line, and

distributing other characters in the previous line of text between the first character and the last character.

19. The one or more non-transitory computer-readable media of claim 15, the acts further comprising:

identifying a character at an end of another line of text as a character that is not placed at an end of a line;

moving the character that is not placed at the end of the line to a start of a following line of text; and

adjusting spacing between characters in the following line of text based at least in part on moving the character that is not placed at the end of a line.