Electronic book pagination

• US 8,798,366 B1
• Filed: 12/28/2010
• Issued: 08/05/2014
• Est. Priority Date: 12/28/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Jones, Derek T., Berezhnyy, Oleksandr Y.
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Niu, Feng
• Application Number:
  US12/979,971
• Time in Patent Office: 1,316 Days
• US Class Current: 382/177
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/114 Pagination
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images

Abstract

An electronic book can be paginated by reference to a print version of the same book. Pages of the print version are scanned to obtain text strings and page labels corresponding to each of the pages. The text strings are then compared to the electronic book to find the best matching positions within the electronic book. The matching positions within the electronic book are then associated with the page numbers of the pages from which the matching text strings were obtained. Autocorrelation can be used to determine matching positions.

Claims

1. A computer-implemented method of paginating an electronic book, the method comprising:

under control of one or more processors configured with executable instructions,

capturing images of pages of a print version of the electronic book;

performing optical character recognition on the images;

based at least in part on the optical character recognition, identifying page text strings and associated page labels corresponding to individual pages;

for an individual page text string, autocorrelating with at least a portion of the electronic book to determine a plurality of candidate matching positions within the electronic book;

at each respective candidate matching position within the electronic book, comparing the individual page text string to a respective text string of the electronic book corresponding to the respective candidate matching position determined from the autocorrelating;

selecting a page position from the plurality of candidate matching positions based at least in part on the comparing; and

mapping between the selected page position and the page label associated with the individual page text string.

2. The computer-implemented method of claim 1, wherein the mapping further comprises:

creating a page/position map that indicates correspondences between page labels of the print version and positions within the electronic book; and

associating the page/position map with the electronic book.

3. The computer-implemented method of claim 1, further comprising normalizing the page text strings and text of the electronic book before the autocorrelating, wherein the normalizing comprises at least one of:

removing extraneous characters;

or

converting characters to a single case.

4. The computer-implemented method of claim 1, wherein the comparing is based at least in part on edit distance.

5. The computer-implemented method of claim 1, wherein the autocorrelating comprises performing a bitwise calculation.

6. The computer-implemented method of claim 1, wherein the autocorrelating comprises summing a product of individual bit positions.

7. A computer-implemented method comprising:

under control of one or more processors configured with executable instructions,

performing machine-based optical character recognition on individual pages of a print version of a book to obtain page labels and page text from the individual pages;

finding positions within an electronic version of the book that correspond to individual pages of the print version, wherein the finding is based at least in part on;

autocorrelation between the page text and the electronic version to identify a plurality of candidate positions for respective ones of the individual pages, and

comparing the page text and text of the electronic version at the plurality of candidate positions to select found positions from the plurality of candidate positions determined from the autocorrelation; and

associating the found positions within the electronic version with the page labels of the corresponding individual pages of the print version.

8. The computer-implemented method of claim 7, wherein the associating comprises:

creating a page/position map that indicates correspondences between page labels of the print version and positions within the electronic version; and

associating the page/position map with the electronic version.

9. The computer-implemented method of claim 7, wherein the associating comprises revising the electronic book to indicate page numbering.

10. The computer-implemented method of claim 7, wherein the autocorrelation comprises summing products of individual bit positions of the page text and at least a portion of the electronic version.

11. The computer-implemented method of claim 7, wherein the finding is further based at least in part on edit distances between the page text and the electronic version.

12. The computer-implemented method of claim 7, further comprising, in response to user entry of a page number, navigating to a corresponding position within the electronic version based at least in part on the associating.

13. The computer-implemented method of claim 7, further comprising, in response to user specification of a particular position within the electronic version, citing the page label associated with the particular position based at least in part on the associating.

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

creating a page/position map table that indicates correspondences between page labels of the print version and positions within the electronic version; and

in response to user entry of a page number, referencing the page/position map table to find the corresponding position within the electronic version.

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

creating a page/position map table that indicates correspondences between page labels of the print version and positions within the electronic version; and

in response to user specification of a particular position within the electronic version, referencing the page/position map table to find the corresponding page of the print version.

16. A system comprising:

one or more processors;

one or more computer-readable media containing instructions that are executable by the one or more processors to perform actions comprising;

obtaining page text and corresponding page labels from individual pages of a print version of a book;

determining a page-to-label mapping between the individual pages and the page labels obtained from the print version;

comparing the page text of the individual pages to an electronic version of the book to determine the positions of the individual pages within the electronic version;

creating, based at least in part on the comparing and the page-to-label mapping, a page/position map as a data object separate from content of the electronic version, wherein the page/position map indicates correspondences between the page labels obtained from the print version and positions within the electronic version; and

paginating the electronic version in accordance with the comparing.

17. The system of claim 16, wherein the page labels obtained from the print version comprise at least two different types of page labels.

18. The system of claim 16, wherein the comparing comprises:

performing autocorrelation to identify a plurality of candidate matching positions for the page of text;

calculating edit distances between the page of text and substrings corresponding to the candidate matching positions; and

selecting one of the candidate matching positions as the matching position based at least in part on the edit distances.

19. The system of claim 16, wherein the obtaining comprises machine-based optical character recognition.

20. The system of claim 16, wherein the positions within the page/position map are expressed as at least one of:

a number of bytes from a beginning of the electronic version;

a number of characters from the beginning of the electronic version;

or

a number of words from the beginning of the electronic version.

21. A computer-implemented method comprising:

under control of one or more processors configured with executable instructions,

autocorrelating a first character string against substrings at different positions within a second character string to produce autocorrelation scores corresponding to the substrings;

selecting a matching position within the second character string based at least in part on the autocorrelation scores corresponding to the substrings, the matching position corresponding to a first substring of the substrings; and

subsequent to autocorrelating the first character string, autocorrelating a third character string against the substrings of the second character string, wherein at least one of the substrings is at a position within the second character string that is prior to the matching position of the first substring.

22. The computer-implemented method of claim 21, wherein autocorrelating the first character string against a particular substring comprises summing bitwise products of the first character string and the particular substring.

23. The computer-implemented method of claim 21, wherein autocorrelating the first character string against a particular substring comprises:

bitwise ANDing the first character string and the particular substring to produce bitwise results; and

summing the bitwise results.

24. The computer-implemented method of claim 21, further comprising normalizing the first character string and the second character string before the autocorrelating.

25. The computer-implemented method of claim 21, wherein the selecting is further based at least in part on calculating edit distances between the first character string and the substrings.

26. The computer-implemented method of claim 21, wherein the selecting further comprises:

identifying a plurality of candidate matching positions based at least in part on the autocorrelating;

calculating edit distances between the first character string and each of the substrings corresponding to the candidate matching positions; and

selecting one of the candidate matching positions as the matching position based at least in part on the calculated edit distances.

27. A method comprising:

determining, by one or more processors, page text corresponding to individual pages of a print version of a book;

determining, by the one or more processors, page labels included on the individual pages of the print version;

determining, by the one or more processors, a page-to-label mapping between the individual pages and the page labels from the print version;

determining, by the one or more processors, positions within an electronic version of the book that correspond to the individual pages of the print version, wherein the determining is based at least in part on comparing the page text of the individual pages of the print version to text of the electronic version; and

generating, by the one or more processors, based at least in part on the page-to-label mapping and the comparing, a page/position map, wherein the page/position map indicates correspondences between the page labels from the print version of the book and the positions within the electronic version of the book.

28. The method of claim 27, further comprising based at least in part upon the page/position map, revising content of the electronic book to indicate page numbering corresponding to the page labels from the print version.

29. The method of claim 27, further comprising:

generating the page/position map as a data object separate from content of the electronic version of the book; and

sending the page/position map to a user device, wherein in response to user entry of a page label, the page/position map is configured to indicate a corresponding position within the electronic version.